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

Autores

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

Palavras-chave:

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

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.

Downloads

Não há dados estatísticos.

Biografia do Autor

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.

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.