Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções

Sidnei Alves de Araújo; Stanley Jefferson Araujo Lima

doi:10.5585/exactaep.v18n4.15959

Authors

Sidnei Alves de Araújo Universidade Nove de Julho
Stanley Jefferson Araujo Lima Universidade Nove de Julho

DOI:

https://doi.org/10.5585/exactaep.v18n4.15959

Keywords:

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

Download data is not yet available.

Author Biographies

Sidnei Alves de Araújo, Universidade Nove de Julho

Doutor em Engenharia Elétrica pela Escola Politécnica da Universidade de São Paulo (2009), mestre em Engenharia Elétrica pela Universidade Presbiteriana Mackenzie (2002). Possui especialização em Análise de Sistemas (1995) e em Administração de Negócios (1999), graduação em Processamento de Dados (1994) e em Licenciatura Plena (1998), todos pela Universidade Presbiteriana Mackenzie. Atualmente é docente permanente do Programa de Mestrado e Doutorado em Informática e Gestão do Conhecimento (PPGI) e docente do curso de Bacharelado em Ciência da Computação da Universidade Nove de Julho - UNINOVE, onde atua em regime de dedicação exclusiva. É Pesquisador Associado do Laboratório de Processamento Digital de Sinais da Escola Politécnica da Universidade de São Paulo. Foi bolsista de Produtividade em Desenvolvimento Tecnológico e Extensão Inovadora do CNPq (DT-Nível 2) e tem atuado nos seguintes temas de pesquisa: Processamento de Imagens e Visão Computacional, Inteligência Computacional, Algoritmos Metaheurísticos, Aprendizagem de Máquina e Otimização de Sistemas e Processos.

Stanley Jefferson Araujo Lima, Universidade Nove de Julho

Graduado em Administração com habilitação em Sistemas de Informação (2007), Mestre em Engenharia de Produção (2015) e Doutorando em Informática e Gestão do Conhecimento na Universidade Nove de Julho.

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.