Computational tool for analysis of the behavior of genetic algorithm population in the solution space
DOI:
https://doi.org/10.5585/exactaep.v18n4.15959Keywords:
Genetic Algorithms, Solution encoding, Solution space, Capacitated Vehicle Routing Problem.Abstract
Genetic Algorithm (GA) is an optimization method inspired by the theory of evolution of species that has been widely used to solve problems classified as NP-Hard (Non-deterministic Polynomial Time), among which are the Job Shop Scheduling Problem (JSP) and the Vehicle Routing Problem (VRP). However, finding solutions to any optimization problem using GA presupposes the adoption of a solution encoding scheme and the configuration of genetic operators. Different schemes and configurations may produce different behaviors in the GA population, but observing such behaviors is not an easy task and, for this reason, has attracted the attention of many researchers over the last years. This work proposes a computational tool that allows to analyze how the encoding scheme and genetic operators affect the behavior of the GA population in the solution space, by visualizing the individuals projected to a two-dimensional space and performance measures implemented in the tool. In the experiments conducted we analyzed the behavior of the GA population adopting three coding schemes of solutions for the Capacitated Vehicle Routing Problem (CRVP). As a result, besides a discussion about the behavior analysis of the GA, it was found that the performance measures provided by the developed computational tool can help in the proposition and/or choice of heuristics that aim to support the refinement of the solutions generated by GA, improving its performance.
Downloads
References
Andrade, M. M. (2001). Como Preparar Trabalhos para Cursos de Pós Graduação. 4. ed. São Paulo: Atlas.
Ben-Romdhane, H., Alba, E., & Krichen, S. (2013). Best practices in measuring algorithm performance for dynamic optimization problems. Soft Computing, 17(6), 1005-1017. https://doi.org/10.1007/s00500-013-0989-7
Boese, K. D., Kahng, A. B., & Muddu, S. (1994). A new adaptive multi-start technique for combinatorial global optimizations. Operations Research Letters, 16(2), 101-113. https://doi.org/10.1016/0167-6377(94)90065-5
Brooker, R. J. (2012) Concepts of genetics. New York: McGraw-Hill.
Christofides, N. (1985). Vehicle Routing. In: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Lawer, E.L., Lenstra, J.K., kan, A.H.G.R., Shmoys, D.B (eds), Great Britain.: John Wiley & Sons Ltd,
Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations research, 22(2), 340-349. https://doi.org/10.1287/opre.22.2.340
Goldberg, D. E. (1989) Genetic Algorithms in search, optimization and machine learning. U.S.A., Addison-Wesley Publishing Company,
Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
Kumar, A. (2013). Encoding schemes in genetic algorithm. International Journal of Advanced Research in IT and Engineering, 2(3), 1-7.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3), 345-358. https://doi.org/10.1016/0377-2217(92)90192-C
Lima S.J.A., & Araújo S.A. (2018) A New Binary Encoding Scheme in Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem. In: Bioinspired Optimization Methods and Their Applications. BIOMA 2018. Korošec P., Melab N., Talbi EG. (eds) Lecture Notes in Computer Science, 10835, 174-184. https://doi.org/10.1007/978-3-319-91641-5_15.
Lima, S. J. A., SANTOS, R., & ARAÚJO, S. (2015). Otimização do problema de roteamento de veículos capacitado usando Algoritmos Genéticos e as heurísticas de Gillet e Miller e descida de encosta. Anais do XXXV Encontro Nacional de Engenharia de Produção. Rio de Janeiro: ABEPRO, 1, pp. 1-15.
Linden, R. (2012). Algoritmos Genéticos. Editora Ciência Moderna, 3. ed.
Lu, H., Shi, J., Fei, Z., Zhou, Q., & Mao, K. (2018). Analysis of the similarities and differences of job-based scheduling problems. European Journal of Operational Research, 270(3), 809-825. https://doi.org/10.1016/j.ejor.2018.01.051
Merz, P., & Freisleben, B. (1998, September). Memetic algorithms and the fitness landscape of the graph bi-partitioning problem. In: International Conference on Parallel Problem Solving from Nature, pp. 765-774, Springer, Berlin, Heidelberg.
Nazif, H., & Lee, L. S. (2012). Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36(5), 2110-2117. https://doi.org/10.1016/j.apm.2011.08.010
Rosa, A. F. C. (2019). Algoritmo Genético híbrido baseado na análise de componentes principais co Fitness Landscape para O Job Shop Scheduling Problem. São Paulo: UNINOVE, 2019. 91p. Tese (Doutorado em Informática e Gestão do Conhecimento) – Programa de Pós-graduação em Informática e Gestão do Conhecimento, Universidade Nove de Julho, São Paulo.
Rothlauf, F. (2011). Design of modern heuristics: principles and application. Springer Science & Business Media.
Vieira, H. P. (2013). Metaheuristica para a solução de problemas de roteamento de veículos com janela de tempo. Campinas: UNICAMP, 2013. 108p. Dissertação (Mestrado em Matemática Aplicada) – Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas, Campinas.
Watson, J. P. (2010). An introduction to fitness landscape analysis and cost models for local search. In: Handbook of metaheuristics, pp. 599-623. Springer, Boston, MA.
Weicker, K. (2002, September). Performance measures for dynamic environments. In: International Conference on Parallel Problem Solving from Nature, pp. 64-73. Springer, Berlin, Heidelberg.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Exacta
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Autores que tiverem artigos aceitos para publicação na Revista Exacta concordam com os seguintes termos:
- A Cessão dos Direitos Autorais da publicação do artigo à Revista Exacta;
- Os autores que tiverem seus trabalhos aceitos e publicados na Revista Exacta estão sujeitos a Política de Direitos Autorais CC BY NC SA https://creativecommons.org/licenses/by-nc-sa/4.0/;
- A publicação do artigo pela Revista Exacta, em caráter de exclusividade e em meio eletrônico;
- A indexação do artigo em bases de dados nacionais e internacionais, diretórios, bibliotecas digitais e bases bibliométricas em que a Revista estiver e vir a estar indexada.
