Experimental Research on Evolutionary Path Planning Algorithm with Fitness Function Scaling for Collision Scenarios

ABSTRACT: This article presents typical ship collision scenarios, simulated using the evolutionary path planning system and analyses the impact of the fitness function scaling on the quality of the solution. The function scaling decreases the selective pressure, which facilitates leaving the local optimum in the calcula-tion process and further exploration of the solution space. The performed investigations have proved that the use of scaling in the evolutionary path planning method makes it possible to preserve the diversity of solu-tions by a larger number of generations in the exploration phase, what could result in finding better solution at the end. The problem of avoiding collisions well fitted the algorithm in question, as it easily incorporates dy-namic objects (moving ships) into its simulations, however the use scaling with this particular problem has proven to be redundant.

KEYWORDS: Anti-Collision, Evolutionary Algorithms, Experimental Research, Collision Scenario, Fitness Function, Fitness Function Scaling, Evolutionary Path Planning Method, Trajectory Planning

REFERENCES

Goldberg D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1989

Farzad A. Sadjali, Comparison of fitness scaling functions in genetic algorithms with applications to optical processing, , Proc. of SPIE Vol. 5557, pp. 358

Hopgood A., Mierzejewska A., Transform Ranking: a New Method of Fitness Scaling in Genetic Algorithms, Research and development in intelligent systems XXV: proceedings of AI-2008, pp.349-355.

Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs. Spriger-Verlang, 3rd edition, 1996.

Śmierzchalski R., Trajectory planning for ship in collision situations at sea by evolutionary computation, In Proceedings of the IFAC MCMC'97, Brijuni, Croatia, 1997.

Śmierzchalski R., Ships’ domains as collision risk at sea in the evolutionary method of trajectory planning, Computer Information and Applications Vol II, 2004, pp. 117 – 125.

Śmierzchalski R. and Michalewicz, Z., Adaptive Modeling of a Ship Trajectory in Collision Situations at Sea, In Proccedings of the 2nd IEEE World Congress on Computational Intelligence, ICEC'98, Alaska, USA 1998, pp. 364 - 369.

Śmierzchalski R. and Michalewicz, Z., Modeling of a Ship Trajectory in Collision Situations at Sea by Evolutionary Algorithm, IEEE Transaction on Evolutionary Computation, Vol.4, No.3, 2000, pp.227-241.

Śmierzchalski R., Michalewicz, Z., Path Planning in Dynamic Environments, chapter in Innovations in Machine Intelligence and Robot Perception, Springer-Verlag, 2005. pp.135-154.

Tidor B., Michael de la Maza, Boltzmann Weighted Selection Improves Performance of Genetic Algorithms, MIT, Artificial Intelligence Laboratory, December 1991, pp. 1-18.

Wall Mathew, GAlib: A C++ Library of Genetic Algorithm Components, MIT 1996

Yap, C.-K., Algorithmic Motion Planning, In Advances in Robotics, Vol.1: Algorithmic and Geometric Aspects of Robotics}, J.T. Schwartz and C.-K. Yap Ed., , Lawrence Erlbaum Associates, 1987, pp.95 - 143.

Eiben E.A., Smith J.E.: Introduction to evolutionary computing, Springer 2003

P. Kolendo, R. Śmierzchalski, B. Jaworski: Scaling Fitness Function in Evolutionary Path Planning Method, 20th IEEE International Symposium on Industrial Electronics IEEE-ISIE 2011

Young-Il Lee, Yong-Gi Kim: A Fuzzy Collision Avoidance Technique for Intelligent Ship.

Citation note:

Kolendo P., Śmierzchalski R., Jaworski B.: Experimental Research on Evolutionary Path Planning Algorithm with Fitness Function Scaling for Collision Scenarios. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 5, No. 4, pp. 489-495, 2011

BibTeX EndNote