{"id":17,"date":"2019-09-11T23:40:21","date_gmt":"2019-09-12T02:40:21","guid":{"rendered":"https:\/\/leonardoguedes.com.br\/lg\/?p=17"},"modified":"2023-09-08T14:38:00","modified_gmt":"2023-09-08T17:38:00","slug":"mobilidade","status":"publish","type":"post","link":"https:\/\/leonardoguedes.com.br\/lg\/2019\/09\/11\/mobilidade\/","title":{"rendered":"Uma Solu\u00e7\u00e3o Sub\u00f3tima para o Problema de Determina\u00e7\u00e3o de Viagens usando Algoritmos Gen\u00e9ticos em Redes de Petri"},"content":{"rendered":"\n

Authors: Leonardo Guerra de Rezende Guedes<\/a> & Gabriel Reis<\/em><\/strong><\/p>\n\n\n\n

Abstract.<\/strong> 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.<\/p>\n\n\n\n

Introdu\u00e7\u00e3o<\/h3>\n\n\n\n

A mobilidade populacional di\u00e1ria \u2013 uma dimens\u00e3o importante da din\u00e2mica urbana e interurbana \u2013 impacta diretamente na distribui\u00e7\u00e3o da atividade econ\u00f4mica na cidade. A distribui\u00e7\u00e3o espacial dos postos de trabalho, por exemplo, \u00e9 tipicamente de acentuada concentra\u00e7\u00e3o nas \u00e1reas centrais das cidades. Esta distribui\u00e7\u00e3o gera os deslocamentos pendulares \u2013 movimentos di\u00e1rios de pessoas que residem fora do centro da cidade ou mesmo fora da cidade. (Antico, 2016).<\/p>\n\n\n\n

Neste trabalho estudamos solucionar, por meio de t\u00e9cnicas de busca em profundidade e do m\u00e9todo dos algoritmos gen\u00e9ticos, o cl\u00e1ssico Problema de Determina\u00e7\u00e3o das Viagens, neste caso tendo as rotas, origem e destino modelados por rede de Petri. Uma rede de Petri \u00e9 um sistema composto por transi\u00e7\u00f5es, estados e fichas que possibilitam uma representa\u00e7\u00e3o matem\u00e1tica e possui mecanismos de an\u00e1lise poderosos. (ROMERO, & ROBERTO, 1996). As redes de transporte urbano apresentam a propriedade de possuir grupos de estados (lugares, representado tipicamente por um c\u00edrculo) altamente relacionados. Neste trabalho, os estados est\u00e3o associados a pontos de um trajeto \u2013 terminais, e as transi\u00e7\u00f5es representam a dist\u00e2ncia entre os estados.<\/p>\n\n\n\n

Para buscar solu\u00e7\u00f5es aproximadas do \u00f3timo para problemas de busca e de otimiza\u00e7\u00e3o o algoritmo gen\u00e9tico se apresenta com uma boa alternativa e \u00e9 geralmente utilizada em problemas de complexidade exponencial. Assim, a busca, inspirada no mecanismo da sele\u00e7\u00e3o natural, adv\u00e9m de um processo evolutivo que resulta em uma solu\u00e7\u00e3o adequada partindo de uma popula\u00e7\u00e3o inicial de poss\u00edveis solu\u00e7\u00f5es e, ent\u00e3o, combinando os elementos da popula\u00e7\u00e3o em uma nova gera\u00e7\u00e3o de poss\u00edveis solu\u00e7\u00f5es, com a expectativa de uma popula\u00e7\u00e3o de solu\u00e7\u00f5es melhore (de Lima Galv\u00e3o, Lamar, & Taco, 2014). Os “indiv\u00edduos\u201d mais adaptados possuem mais chances de gerar descendentes. O objetivo \u00e9 que no decorrer de v\u00e1rias gera\u00e7\u00f5es, as melhores caracter\u00edsticas sejam selecionadas, assim como ocorre no meio biol\u00f3gico.<\/p>\n\n\n\n

Objeto de Estudo<\/h3>\n\n\n\n

O objetivo deste trabalho \u00e9 construir um algoritmo gen\u00e9tico 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.<\/p>\n\n\n\n

Neste caso, o cromossomo foi representado por um vetor de 9 posi\u00e7\u00f5es (quantidade de transi\u00e7\u00f5es presentes na rede em estudo), onde cada posi\u00e7\u00e3o \u00e9 destinada a salvar um ponto de acionamento que ocorreu na rede. J\u00e1 a fun\u00e7\u00e3o de avalia\u00e7\u00e3o, a qual define o valor para a aptid\u00e3o de um indiv\u00edduo a partir da soma das dist\u00e2ncias das transi\u00e7\u00f5es representadas, leva a atribuir um b\u00f4nus para os cromossomos que apresentem caracter\u00edsticas desej\u00e1veis \u00e0 obten\u00e7\u00e3o do objetivo, estas s\u00e3o aplicadas para os cromossomos que comecem com a transi\u00e7\u00e3o 1 (um)  e que consigam atingir o destino.<\/p>\n\n\n\n

Para o processo de sele\u00e7\u00e3o utilizou-se o m\u00e9todo da roleta, atribuindo uma fatia de uma roleta para cada indiv\u00edduo, e tendo o tamanho desta fatia diretamente proporcional \u00e0 avalia\u00e7\u00e3o do indiv\u00edduo (Silva, 2017). Para o processo de Crossover, definiu-se que cada cromossomo filho ter\u00e1 os genes do pai fora do intervalo entre os n\u00fameros selecionados e os genes da m\u00e3e para o intervalo entre os n\u00fameros. J\u00e1 o operador de muta\u00e7\u00e3o, ao inserir variedade gen\u00e9tica na popula\u00e7\u00e3o, selecionou um ponto aleat\u00f3rio e realizou a troca do gene contido na posi\u00e7\u00e3o indicada pelos ponto.<\/p>\n\n\n\n

Neste Estudo do Caso, definiu-se como constantes gen\u00e9ticas:<\/p>\n\n\n\n

(i) a Taxa de Muta\u00e7\u00e3o em 0.1%;<\/em><\/p>\n\n\n\n

(ii) o N\u00famero de Gera\u00e7\u00f5es em 200;<\/em><\/p>\n\n\n\n

iii) os Indiv\u00edduos por Gera\u00e7\u00e3o: em 20; e<\/em><\/p>\n\n\n\n

(iv) o N\u00famero de Genes por cromossomo em 6.<\/em><\/p>\n\n\n\n

Adotou-se o Algoritmo Gen\u00e9tico em pseudoc\u00f3digo ilustrado na Figura 2, no qual o crit\u00e9rio de parada considera um n\u00famero m\u00e1ximo de gera\u00e7\u00f5es com X<\/em><\/strong> e a muta\u00e7\u00e3o \u00e9 aplicada a apenas um descendente do cruzamento, com a probabilidade \u03b8<\/em><\/strong>.<\/p>\n\n\n\n

Resultados e Discuss\u00e3o<\/h3>\n\n\n\n

Este trabalhou avaliou duas possibilidades de Popula\u00e7\u00e3o Inicial. A primeira totalmente aleat\u00f3ria em que a popula\u00e7\u00e3o inicial foi gerada de forma aleat\u00f3ria, sem a preocupa\u00e7\u00e3o de se definir cromossomos com trajetos v\u00e1lidos para que o algoritmo consiga atender ao objetivo. E a segunda com popula\u00e7\u00e3o inicial aleat\u00f3ria com \u201ccromossomos v\u00e1lidos\u201d, ou seja, a popula\u00e7\u00e3o inicial foi gerada de forma aleat\u00f3ria, mas com a preocupa\u00e7\u00e3o de que cada cromossomo apresente um caminho poss\u00edvel no grafo para que o algoritmo consiga atender ao objetivo.<\/p>\n\n\n\n

A. Popula\u00e7\u00e3o Inicial Aleat\u00f3ria<\/h4>\n\n\n\n

Para uma popula\u00e7\u00e3o inicial aleat\u00f3rio sem preocupa\u00e7\u00e3o com \u201ccromossomos v\u00e1lidos\u201d, o m\u00e9todo da roleta apresentou falhas. Isto era esperado vez que nas primeiras gera\u00e7\u00f5es \u00e9 comum que nenhum indiv\u00edduo n\u00e3o apresente nenhum percurso v\u00e1lido, possuindo avalia\u00e7\u00e3o igual a zero; a solu\u00e7\u00e3o adotada para este caso foi selecionar um indiv\u00edduo qualquer da popula\u00e7\u00e3o. A \u00fanica solu\u00e7\u00e3o foi encontrada na 31\u00ba gera\u00e7\u00e3o: 0\u21921\u21924\u21928.<\/p>\n\n\n\n

B. Popula\u00e7\u00e3o Inicial Aleat\u00f3ria com Cromossomos V\u00e1lidos<\/h4>\n\n\n\n

Quando a popula\u00e7\u00e3o inicial \u00e9 gerada de forma aleat\u00f3ria, mas com a preocupa\u00e7\u00e3o de que cada cromossomo apresente um caminho poss\u00edvel no grafo, o algoritmo tamb\u00e9m consegue atender o objetivo. A solu\u00e7\u00e3o pode ser encontrada j\u00e1 na primeira gera\u00e7\u00e3o e, a partir de ent\u00e3o, as gera\u00e7\u00f5es tendem a convergir para a solu\u00e7\u00e3o de melhor adapta\u00e7\u00e3o vez que o m\u00e9todo da roleta seleciona indiv\u00edduos de maior aptid\u00e3o, n\u00e3o permitindo que convirja para a solu\u00e7\u00e3o de menor caminho. Logo obteve-se como solu\u00e7\u00f5es: 0\u21921\u21924\u21928; 0\u21921\u21924\u21925\u21927\u21928; 0\u21922\u21925\u21927\u21928 e 0\u21923\u21926\u21928.<\/p>\n\n\n\n

Conclus\u00e3o<\/h3>\n\n\n\n

A partir dos dois resultados, percebe-se a necessidade de melhorias na fun\u00e7\u00e3o objetivo a fim de buscar o menor caminho entre os estados; e tamb\u00e9m melhorias no operador de sele\u00e7\u00e3o, pois esta primeira implementa\u00e7\u00e3o se mostrou incapaz de lidar com popula\u00e7\u00f5es em que todos os indiv\u00edduos possuam aptid\u00e3o igual a zero.<\/p>\n\n\n\n

Refer\u00eancias<\/h4>\n\n\n\n

Antico, C. (2016). Deslocamentos pendulares nos espa\u00e7os sub-regionais da Regi\u00e3o Metropolitana de S\u00e3o Paulo<\/strong>. Anais, 1-16.<\/p>\n\n\n\n

de Lima Galv\u00e3o, M., Lamar, M. V., & Taco, P. W. G. (2014). Desenho autom\u00e1tico de mapas octalineares de rede de transporte p\u00fablico utilizando algoritmo gen\u00e9tico<\/strong>. TRANSPORTES, 22(1), 21-30.<\/p>\n\n\n\n

Godinho, J. M., & Miranda, L. M. (2014). Aplica\u00e7\u00e3o de M\u00e9todo de An\u00e1lise Multicrit\u00e9rio na Escolha de Tra\u00e7ado de Linhas de Onibus de Transporte P\u00fablico Utilizando Sistema de Informa\u00e7\u00e3o Geogr\u00e1fica<\/strong>. E&S Engineering and Science, 1(1), 89-102.<\/p>\n\n\n\n

Silva, J. G. D. S. (2017). Algoritmos de solu\u00e7\u00e3o para o problema do caixeiro viajante com passageiros e quota<\/strong> (Master’s thesis, Brasil).<\/p>\n\n\n\n

ROMERO,P.M.M; Dueire R.Lins;ROBERTO,P.R.F.C. |(1996) Introdu\u00e7\u00e3o \u00e1s Redes de Petri e Aplica\u00e7\u00f5es<\/strong>. Campinas-SP.<\/p>\n\n\n\n

Leonardo Guedes<\/strong>* & <\/em>Gabriel Reis<\/em><\/strong>**<\/em><\/pre>\n\n\n\n
*<\/strong>Professor do Programa de P\u00f3s-Gradua\u00e7\u00e3o em Desenvolvimento e Planejamento Territorial da Pontif\u00edcia Universidade Cat\u00f3lica de Goi\u00e1s \u2013 PUC Goi\u00e1s. Professor Titular da Escola de Engenharia El\u00e9trica, Mec\u00e2nica e de Computa\u00e7\u00e3o da Universidade Federal de Goi\u00e1s. https:\/\/orcid.org\/0000-0002-7854-1558<\/a><\/pre>\n\n\n\n
**<\/strong>Acad\u00eamico do Curso de Engenharia de Computa\u00e7\u00e3o da Pontif\u00edcia Universidade Cat\u00f3lica de Goi\u00e1s \u2013 PUC Goi\u00e1s.<\/pre>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":242,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[16,4],"class_list":["post-17","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-engenharia-inocavao","tag-gabriel-reis","tag-leonardo-guerra-de-rezende-guedes"],"_links":{"self":[{"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/posts\/17","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/comments?post=17"}],"version-history":[{"count":14,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/posts\/17\/revisions"}],"predecessor-version":[{"id":517,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/posts\/17\/revisions\/517"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/media\/242"}],"wp:attachment":[{"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/media?parent=17"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/categories?post=17"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/leonardoguedes.com.br\/lg\/wp-json\/wp\/v2\/tags?post=17"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}