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

Resumo


O Algoritmo Genético (AG) é um método otimização inspirado na teoria de evolução das espécies que tem sido largamente empregado na solução de problemas classificados como NP-Hard (Non-deterministic Polynomial Time), entre os quais estão o Problema de Sequenciamento da Produção (Job Shop Scheduling Problem - JSP) e o Problema de Roteamento de Veículos (PRV). Entretanto, encontrar soluções para qualquer problema de otimização empregando o AG pressupõe a adoção de um esquema de codificação das soluções e a configuração dos operadores genéticos. Diferentes esquemas e configurações podem produzir comportamentos diferentes na população do AG, mas observar tais comportamentos não é uma tarefa fácil e, por este motivo, vem atraindo a atenção de muitos pesquisadores ao longo dos últimos anos. Neste trabalho propõe-se uma ferramenta computacional que permite analisar como o esquema de codificação e os operadores genéticos afetam o comportamento da população do AG no espaço de soluções, por meio de visualização dos indivíduos projetados para um espaço bidimensional e de medidas de desempenho implementadas na ferramenta. Nos experimentos conduzidos analisou-se o comportamento da população do AG em função de três esquemas de codificação de soluções para o Problema de Roteamento de Veículos Capacitados (PRVC). Como resultados, além de uma discussão acerca da análise do comportamento do AG, pode-se constatar que as medidas de desempenho fornecidas pela ferramenta computacional desenvolvida podem auxiliar na proposição e/ou escolha de heurísticas que visem apoiar o processo de refinamento das soluções geradas pelo AG, melhorando o seu desempenho.


Palavras-chave


Algoritmos Genéticos; Codificação de soluções; Espaço de soluções; Problema de Roteamento de Veículos Capacitados.

Texto completo:

PDF

Referências


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.




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

Direitos autorais 2020 Exacta

Licença Creative Commons
Esta obra está licenciada sob uma licença Creative Commons Atribuição - Não comercial - Compartilhar igual 4.0 Internacional.

Tempo médio entre a submissão e primeira resposta de avaliação: 120 dias

Exacta – Engenharia de Produção

e-ISSN: 1983-9308
ISSN: 1678-5428
www.revistaexacta.org.br

Exacta  ©2020 Todos os direitos reservados.