Authors: Leonardo Guerra de Rezende Guedes & Gabriel Reis

Abstract. Daily population mobility – an important dimension of urban dynamics – directly impacts the distribution of economic activity in the city. This work of the Travel Determination Problem, solved, in this case, through the in-depth search of the sub-optimal solution by genetic algorithms. The implementation of a genetic algorithm sought to find the path between two terminals previously defined in a Petri network. It was concluded that a genetic algorithm is able to search and find a sub-optimal path between two terminals in the Petri net, the performance of which depends on the composition of the initial population.

Introdução

A mobilidade populacional diária – uma dimensão importante da dinâmica urbana e interurbana – impacta diretamente na distribuição da atividade econômica na cidade. A distribuição espacial dos postos de trabalho, por exemplo, é tipicamente de acentuada concentração nas áreas centrais das cidades. Esta distribuição gera os deslocamentos pendulares – movimentos diários de pessoas que residem fora do centro da cidade ou mesmo fora da cidade. (Antico, 2016).

Neste trabalho estudamos solucionar, por meio de técnicas de busca em profundidade e do método dos algoritmos genéticos, o clássico Problema de Determinação das Viagens, neste caso tendo as rotas, origem e destino modelados por rede de Petri. Uma rede de Petri é um sistema composto por transições, estados e fichas que possibilitam uma representação matemática e possui mecanismos de análise poderosos. (ROMERO, & ROBERTO, 1996). As redes de transporte urbano apresentam a propriedade de possuir grupos de estados (lugares, representado tipicamente por um círculo) altamente relacionados. Neste trabalho, os estados estão associados a pontos de um trajeto – terminais, e as transições representam a distância entre os estados.

Para buscar soluções aproximadas do ótimo para problemas de busca e de otimização o algoritmo genético se apresenta com uma boa alternativa e é geralmente utilizada em problemas de complexidade exponencial. Assim, a busca, inspirada no mecanismo da seleção natural, advém de um processo evolutivo que resulta em uma solução adequada partindo de uma população inicial de possíveis soluções e, então, combinando os elementos da população em uma nova geração de possíveis soluções, com a expectativa de uma população de soluções melhore (de Lima Galvão, Lamar, & Taco, 2014). Os “indivíduos” mais adaptados possuem mais chances de gerar descendentes. O objetivo é que no decorrer de várias gerações, as melhores características sejam selecionadas, assim como ocorre no meio biológico.

Objeto de Estudo

O objetivo deste trabalho é construir um algoritmo genético que seja capaz de encontrar um caminho entre os Estados (terminais) de uma rede de Petri. Para este estudo de caso, propomos o resolver a rota entre o estado 1 (um) e o estado 8 (oito) modelado como Rede de Petri representando um conjunto de Terminais.

Neste caso, o cromossomo foi representado por um vetor de 9 posições (quantidade de transições presentes na rede em estudo), onde cada posição é destinada a salvar um ponto de acionamento que ocorreu na rede. Já a função de avaliação, a qual define o valor para a aptidão de um indivíduo a partir da soma das distâncias das transições representadas, leva a atribuir um bônus para os cromossomos que apresentem características desejáveis à obtenção do objetivo, estas são aplicadas para os cromossomos que comecem com a transição 1 (um)  e que consigam atingir o destino.

Para o processo de seleção utilizou-se o método da roleta, atribuindo uma fatia de uma roleta para cada indivíduo, e tendo o tamanho desta fatia diretamente proporcional à avaliação do indivíduo (Silva, 2017). Para o processo de Crossover, definiu-se que cada cromossomo filho terá os genes do pai fora do intervalo entre os números selecionados e os genes da mãe para o intervalo entre os números. Já o operador de mutação, ao inserir variedade genética na população, selecionou um ponto aleatório e realizou a troca do gene contido na posição indicada pelos ponto.

Neste Estudo do Caso, definiu-se como constantes genéticas:

(i) a Taxa de Mutação em 0.1%;

(ii) o Número de Gerações em 200;

iii) os Indivíduos por Geração: em 20; e

(iv) o Número de Genes por cromossomo em 6.

Adotou-se o Algoritmo Genético em pseudocódigo ilustrado na Figura 2, no qual o critério de parada considera um número máximo de gerações com X e a mutação é aplicada a apenas um descendente do cruzamento, com a probabilidade θ.

Resultados e Discussão

Este trabalhou avaliou duas possibilidades de População Inicial. A primeira totalmente aleatória em que a população inicial foi gerada de forma aleatória, sem a preocupação de se definir cromossomos com trajetos válidos para que o algoritmo consiga atender ao objetivo. E a segunda com população inicial aleatória com “cromossomos válidos”, ou seja, a população inicial foi gerada de forma aleatória, mas com a preocupação de que cada cromossomo apresente um caminho possível no grafo para que o algoritmo consiga atender ao objetivo.

A. População Inicial Aleatória

Para uma população inicial aleatório sem preocupação com “cromossomos válidos”, o método da roleta apresentou falhas. Isto era esperado vez que nas primeiras gerações é comum que nenhum indivíduo não apresente nenhum percurso válido, possuindo avaliação igual a zero; a solução adotada para este caso foi selecionar um indivíduo qualquer da população. A única solução foi encontrada na 31º geração: 0→1→4→8.

B. População Inicial Aleatória com Cromossomos Válidos

Quando a população inicial é gerada de forma aleatória, mas com a preocupação de que cada cromossomo apresente um caminho possível no grafo, o algoritmo também consegue atender o objetivo. A solução pode ser encontrada já na primeira geração e, a partir de então, as gerações tendem a convergir para a solução de melhor adaptação vez que o método da roleta seleciona indivíduos de maior aptidão, não permitindo que convirja para a solução de menor caminho. Logo obteve-se como soluções: 0→1→4→8; 0→1→4→5→7→8; 0→2→5→7→8 e 0→3→6→8.

Conclusão

A partir dos dois resultados, percebe-se a necessidade de melhorias na função objetivo a fim de buscar o menor caminho entre os estados; e também melhorias no operador de seleção, pois esta primeira implementação se mostrou incapaz de lidar com populações em que todos os indivíduos possuam aptidão igual a zero.

Referências

Antico, C. (2016). Deslocamentos pendulares nos espaços sub-regionais da Região Metropolitana de São Paulo. Anais, 1-16.

de Lima Galvão, M., Lamar, M. V., & Taco, P. W. G. (2014). Desenho automático de mapas octalineares de rede de transporte público utilizando algoritmo genético. TRANSPORTES, 22(1), 21-30.

Godinho, J. M., & Miranda, L. M. (2014). Aplicação de Método de Análise Multicritério na Escolha de Traçado de Linhas de Onibus de Transporte Público Utilizando Sistema de Informação Geográfica. E&S Engineering and Science, 1(1), 89-102.

Silva, J. G. D. S. (2017). Algoritmos de solução para o problema do caixeiro viajante com passageiros e quota (Master’s thesis, Brasil).

ROMERO,P.M.M; Dueire R.Lins;ROBERTO,P.R.F.C. |(1996) Introdução ás Redes de Petri e Aplicações. Campinas-SP.

Leonardo Guedes* & Gabriel Reis**

*Professor do Programa de Pós-Graduação em Desenvolvimento e Planejamento Territorial da Pontifícia Universidade Católica de Goiás – PUC Goiás. Professor Titular da Escola de Engenharia Elétrica, Mecânica e de Computação da Universidade Federal de Goiás. https://orcid.org/0000-0002-7854-1558

**Acadêmico do Curso de Engenharia de Computação da Pontifícia Universidade Católica de Goiás – PUC Goiás.