Multi-path planning algorithm based on fitness sharing and species evolution

Abstract

A new algorithm is proposed for underwater vehicles multi-path planning. This algorithm is based on fitness sharing genetic algorithm, clustering and evolution of multiple populations, which can keep the diversity of the solution path, and decrease the operating time because of the independent evolution of each subpopulation. The multi-path planning algorithm is demonstrated by a number of two-dimensional path planning problems. The results show that the multi-path planning algorithm has the following characteristics: high searching capability, rapid convergence and high reliability.

Keywords

genetic algorithm / subpopulation evolution / fitness sharing / multi-path planning

References

[1] Hocaoglu C, Sanderson A C. Planning multiple paths with evolutionary speciation [J]. IEEE Transactions on Evolutionary Computation, 2001, 5(3): 169-191

[2] Pan Z J, Kang L S, Chen Y P. Evolutionary computation [M]. 1998, Beijing: Tsinghua University Press, (in Chinese)

[3] GOLDBERG D E, RICHARDSON J. Genetic algorithm with sharing for multimodal function optimization [A]. Proc 2^nd International Conf Genetic Algorithms [C]. Hillsdale, 1987.

[4] SPEARS W M. Simple Subpopulation Schemes [A]. Proc of the Third Annual Conference on Evolutionary Programming [C]. San Diego, 1994.

[5] Zhou M, Sun S D. Genetic algorithms: theory and applications [M]. 1999, Beijing: National Defense Industry Press, (in Chinese)

[6] Yu X J, Wang Z J. A new clustering method and its applications on multimodal optimization [J]. Journal of Tsinghua University (Sci & Tech), 2001, 41(4/5): 159-162 (in Chinese)

[7] Huang Z C, Chen S D, Li L. Population isolation and adaptive-gathering in evolutionary computation [J]. Journal of Software, 2000, 13(4): 827-832 (in Chinese)