Last ned (Gratis)

Abstrakt

Abstract-This paper describes a genetic algorithm that was developed for optimizing plans in a robotic competition. The algorithm was used both as a static planner, making plans before matches, and as a dynamic replanner during matches, a task with much stricter demands of efficiency. The genetic algorithm was hybridized with a local search technique, which experiments proved essential to finding good solutions in this complex task. To enable rapid response under environmental changes, a heuristic for immediate response and a contingency planning module were also implemented. Experiments showed that the algorithm was able to handle a changing environment by revising its plan, but no conclusive results were obtained about the importance of contingency planning in this process.

Referanser

[1] E. Alba and B. Dorronsoro. Computing nine new best-so-far
solutions for capacitated VRP with a cellular genetic algorithm.
Information Processing Letters, 98(6):225–230, June 2006.


[2] Y. Chen, Y. Lu, and G. Yang. Hybrid evolutionary algorithm
with marriage of genetic algorithm and extremal optimization
for production scheduling. The International Journal of Advanced
Manufacturing Technology, 36(9):959–968, Apr. 2008.


[3] P. Larra ˜ naga, C. M. H. Kuijpers, and R. H. Murga. Tackling
the travelling salesman problem with evolutionary algorithms:
Representations and operators, 1994.


[4] Z. Liu and L. Kang. A hybrid algorithm of n-OPT and GA to solve
dynamic TSP. In Grid and Cooperative Computing, pages 1030–1033.
Springer Berlin Heidelberg, 2004.


[5] Z. Michalewicz and D. B. Fogel. How to solve it: modern heuristics.
Springer-Verlag New York, Inc., 2000.


[6] Plan´ete-Sciences. Eurobot 2010 - Feed the World.
http://www.eurobot.org/commonfiles/docs/2010/E2010
rules and drawing EN.pdf, Sept. 2010.


[7] C. Prins. A simple and effective evolutionary algorithm for
the vehicle routing problem. Computers & Operations Research,
31(12):1985–2002, Oct. 2004.


[8] M. F. Tasgetiren. A genetic algorithm with an adaptive penalty
function for the orienteering problem. Journal of Economic and
Social Research, 4(2):1–26, 2001.


[9] X. Wang, B. L. Golden, and E. A. Wasil. Using a genetic algorithm
to solve the generalized orienteering problem. In R. Sharda,
S. Voss, B. Golden, S. Raghavan, and E. Wasil, editors, The Vehicle
Routing Problem: Latest Advances and New Challenges, volume 43 of
Operations Research/Computer Science Interfaces Series, pages 263–
274. Springer US, 2008.


[10] A. Zhou, L. Kang, and Z. Yan. Solving dynamic TSP with
evolutionary approach in real time. In Evolutionary Computation,
2003. CEC ’03. The 2003 Congress on, volume 2, pages 951–957
Vol.2, 2003.








Forrige artikkel      Neste artikkel