Distributed Evolutionary Algorithm for Path Planning in Navigation Situation

• Autorzy: Śmierzchalski R. , Kuczkowski Ł. , Kolendo P. , Jaworski B.

Identyfikatory

DOI

10.12716/1001.07.02.17

• Języki publikacji: EN

Abstrakty

EN

This article presents the use of a multi‐population distributed evolutionary algorithm for path planning in navigation situation. The algorithm used is with partially exchanged population and migration between independently evolving populations. In this paper a comparison between a multi‐population and a classic single‐population algorithm takes place. The impact on the ultimate solution has been researched. It was shown that using several independent populations leads to an improvement of the ultimate solution compared to a single population approach. The concept was checked against a problem of maritime collision avoidance.

Słowa kluczowe

EN

evolutionary algorithm; path planning; simulation environment

• Wydawca: Faculty of Navigation, Gdynia Maritime University
• Czasopismo: TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
• Rocznik: 2013
• Tom: Vol. 7, no. 2
• Strony: 293--300
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Śmierzchalski R.

• Gdansk University of Technology, Gdansk, Poland

autor

Kuczkowski Ł.

• Gdansk University of Technology, Gdansk, Poland

autor

Kolendo P.

• Gdansk University of Technology, Gdansk, Poland

autor

Jaworski B.

• Gdansk University of Technology, Gdansk, Poland

Bibliografia

• [1] Belding T. C. (1995). “The Distributed Genetic Algorithms Revised.” Proc. of 6th Int. Conf. Genetic Algorithms: 114‐121.
• [2] Cantu‐Paz E. (1999). “Topologies, Migration Rates, and Multi‐Population Parallel Genetic Algorithms.” bProceedings of GECCO.
• [3] Cochran J.K., Horng S. and Fowler J.W. (2003). “A Multi‐ Population Genetic Algorithm to Solve Multi‐Objective Scheduling Problems for Parallel Machines.” Computers and Operations Research, Vol 30: 1087‐1102, Oxford, UK.
• [4] Forrest S. and Mitchell M. (1991). “The performance of genetic algorithms on Walsh polynomials: Some anomalous results and their explanation.” Proceedings of the Fourth International Conference on Genetic Algorithms, In Belew, R. & L. Booker (Eds.): 182‐189, San Mateo.
• [5] Forrest S. and Mitchell M. (1993). “Relative building‐block fitness and the Building Block hypothesis.” In Whitley L.D. (Ed.), Foundations of Genetic Algorithms 2: 109‐ 126, San Mateo, CA: Morgan Kauf‐mann.
• [6] Gehring H. and Bortfeldt A. (2002). “A parallel genetic algorithm for solving the container loading problem. International Transactions in Operational Research, Vol. 9, No. 4: 497–511.
• [7] Goldberg D.E. (1989). “Genetic Algorithms in Search, Optimization, and Machine Learning.” Boston: Addison‐Wesley Longman Publishing Co., Inc.
• [8] Lenart A.S. (1986). “Wybrane problemy analizy i syntezy okrętowych systemów antykolizyjnych.” Budownictwo okrętowe nr XLIV, Zeszyty naukowe Politechniki Gdańskiej nr 405, Gdańsk 1986.
• [9] Martikainen J. (2006). “Methods for Improving Reliability of Evolutionary Computation Algorithms and Accelerating Problem Solving.” Ph.D. Thesis, Helsinki University of Technology, Dep. of Electrical and Communications Engineering, Espoo.
• [10] Martikainen J. and Ovaska S.J. (2006). “Hierarchical twopopulation genetic algorithm.” International Journal of Computational Intelligence Research vol. 2, No. 4.
• [11] Michalewicz Z. (1996). “Genetic Algorithms + Data Structures = Evolution Programs.” Spriger ‐ Verlang.
• [12] Mitchell M., Forrest S. and Holland J. H. (1992). “The royal road for genetic algorithms: Fitness landscapes and GA performance.” In Proc. of the First European Conference on Artificial Life: 245‐254, Cambridge, MIT Press.
• [13] Mitchell M., Holland J.H. (1993). “When will agenetic algorithm outperform hill climbing?” Santa Fe Institute working paper 93‐06‐037, Santa Fe, NM: Santa Fe Institute.
• [14] Mitchell M., Holland J.H. and Forrest S. (1994). “When will a genetic algorithm outperform hill climbing?” Advances in Neural Information Processing Systems 6 San Mateo, CA: Morgan Kaufmann.
• [15] Śmierzchalski R. (1997). “Trajectory planning for ship in collision situations at sea by evolutionary computation.” In Proc. of the IFAC MCMCʹ97, Brijuni, Croatia.
• [16] Śmierzchalski R. (1998). “Synteza metod i algorytmów wspomagania decyzji nawigatora w sytuacji kolizyjnej na morzu.” DSc. dissertation, Gdynia.
• [17] Śmierzchalski R. and Michalewicz Z. (2000). “Modeling of a Ship Trajectory in Collision Situations at Sea by Evolutionary Algorithm.” IEEE Transaction on Evolutionary Computation, Vol.4, No.3.
• [18] Tanese R. (1989a). “Distributed Genetic Algorithms.” Proc. of 3rd Int. Conf. Genetic Algorithms: 432‐439.
• [19] Tanese R. (1989b). “Distributed Genetic Algorithms.” Ph.D. Thesis, University of Michigan, Ann Arbor.
• [20] Wall M. (1996). “GAlib: A C++ Library of Genetic Algorithm Components.” MIT.
• [21] Whitley D. (1997). “Island Model Genetic Algorithms and Linearly Separable Problems.” Proc. of AISB Workshop on Evolutionary Computation.
• [22] Xiao J. and Michalewicz Z. (1999). “An Evolutionary Computation Approach to Planning and Navigation.” Chapter in Soft‐Computing and Mechatronics, Physica‐ Verlag.