Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidade Nove de Julho - Uninove
2020-11-01
|
| Series: | Exacta |
| Subjects: | |
| Online Access: | https://periodicos.uninove.br/exacta/article/view/15959 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850238575323381760 |
|---|---|
| author | Sidnei Alves de Araújo Stanley Jefferson Araujo Lima |
| author_facet | Sidnei Alves de Araújo Stanley Jefferson Araujo Lima |
| author_sort | Sidnei Alves de Araújo |
| collection | DOAJ |
| description |
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.
|
| format | Article |
| id | doaj-art-41be798b8ffa478092be46dedfa459f1 |
| institution | OA Journals |
| issn | 1678-5428 1983-9308 |
| language | English |
| publishDate | 2020-11-01 |
| publisher | Universidade Nove de Julho - Uninove |
| record_format | Article |
| series | Exacta |
| spelling | doaj-art-41be798b8ffa478092be46dedfa459f12025-08-20T02:01:25ZengUniversidade Nove de Julho - UninoveExacta1678-54281983-93082020-11-0118410.5585/exactaep.v18n4.15959Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluçõesSidnei Alves de Araújo0Stanley Jefferson Araujo Lima1Universidade Nove de JulhoUniversidade Nove de Julho 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. https://periodicos.uninove.br/exacta/article/view/15959Algoritmos GenéticosCodificação de soluçõesEspaço de soluçõesProblema de Roteamento de Veículos Capacitados. |
| spellingShingle | Sidnei Alves de Araújo Stanley Jefferson Araujo Lima Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções Exacta Algoritmos Genéticos Codificação de soluções Espaço de soluções Problema de Roteamento de Veículos Capacitados. |
| title | Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções |
| title_full | Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções |
| title_fullStr | Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções |
| title_full_unstemmed | Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções |
| title_short | Ferramenta computacional para análise do comportamento da população do algoritmo genético no espaço de soluções |
| title_sort | ferramenta computacional para analise do comportamento da populacao do algoritmo genetico no espaco de solucoes |
| topic | Algoritmos Genéticos Codificação de soluções Espaço de soluções Problema de Roteamento de Veículos Capacitados. |
| url | https://periodicos.uninove.br/exacta/article/view/15959 |
| work_keys_str_mv | AT sidneialvesdearaujo ferramentacomputacionalparaanalisedocomportamentodapopulacaodoalgoritmogeneticonoespacodesolucoes AT stanleyjeffersonaraujolima ferramentacomputacionalparaanalisedocomportamentodapopulacaodoalgoritmogeneticonoespacodesolucoes |