Baixe Artigo - Algoritmos genéticos e problemas de transporte e outras Notas de estudo em PDF para Informática, somente na Docsity! ALGORITMOS GENÉTICOS E PROBLEMAS DE TRANSPORTE Rubens Gonçalves Feitosa1 Prof ª Elda Sena2 1Bacharelando em Sistema de Informação Centro Universitário do Maranhão – UniCEUMA – Campus Anil 2Professora especialista em educação pelo Centro Universitário do Maranhão – UniCEUMA Resumo: Apresenta-se neste artigo a relação entre algoritmos genéticos e problemas de transporte em que o número de parâmetros que influenciam no processo apresenta-se em quantidade relativamente elevado, onde as forma convencionais de computação mostram-se pouco eficientes, dada a complexidade do processamento a ser realizado e/ou a função definidora do problema não poder ser expressa analiticamente ou ser não-linear. Palavras-chave: Algoritmos, SIMPLEX, alocação de recursos, roteamento de transporte. Zusammenfassung: Es ist in diesem artikel vorgestellt wird die beziehung zwischen genetischen algorithmen und verkehr problemen, bei denen die anzahl der parameter, die einfluss auf den prozess kommt in den relativ hohen, in denen die konventionelle art der berechnung waren etwas wirksam, angesichts der komplexität der verarbeitung durchgeführt werden und/oder eine funktion zu definieren, kann das problem nicht analytisch ausgedrückt werden oder nicht-linear. Stichworte: Algorithmen, SIMPLEX, Ressourcenallokation, transport-routing. 1 INTRODUÇÃO O planejamento de custos de logística é uma das etapas mais complexas do processo administrativo, tanto na entrega de produtos e serviços quanto na distribuição das equipes de funcionários para realização de uma tarefa. Muitos administradores dão pouca importância a esse planejamento, contando com a improvisação ou “experiência”, sem que seja aplicada qualquer metodologia que otimize a distribuição de recursos de transporte, minimizando o custo final do produto ou serviço. Técnicas computacionais para análise de problemas de transporte que envolvem Pesquisa Operacional já são amplamente cobertas em vários estudos, mas se aplicam a questões com baixa complexidade, com pequena quantidade de variáveis e cuja função pode ser escrita linearmente. Por outro lado, há situações em que nem mesmo as funções que definem o problema podem ser expressas analiticamente ou, mesmo quando podem, a quantidade de parâmetros é relativamente elevada. Nestes casos, ferramentas computacionais comuns tendem a comportar-se apenas como sistemas de busca exaustiva. Nesses ambientes, a procura por alternativas automatizadas que gerem respostas satisfatórias com menor custo operacional é de extrema importância no planejamento orçamentário das instituições, principalmente aquelas que aplicam ou trabalham a logística. Uma dessas alternativas tem sido mais estudada e, consequentemente, mais aplicada, principalmente a partir da segunda metade da década de 1980. Trata-se dos algoritmos genéticos – AGs. Os AGs são implementados usando conceitos da biologia. Baseiam-se nos princípios da teoria da seleção natural de Darwin – sobrevivência dos mais adaptados – e nas leis de Mendell. Tais implementações tornam os algoritmos genéticos muito eficientes na resolução de problemas de otimização, nos quais a estatística, a probabilidade e a análise de dados formam o que chamamos de heurística. Tais características tornam os AGs mecanismos extremamente úteis no trabalho com modelos que envolvem estruturas com graus elevados de complexidade, que é o caso explicitado no início desse texto. Por esses motivos procuraremos mostrar, neste artigo, as relações dos algoritmos genéticos com a resolução de problemas de alocação de recursos com alta complexidade, como logística na entrega de combustíveis por uma distribuidora, distribuição de vendedores entre clientes e determinação de funcionários por setores e por tarefas, todos envolvendo uma gama elevada de variáveis. 2 ALGORITMOS GENÉTICOS (AGs) Algoritmos genéticos são formas de codificação inspirados nas teorias evolutivas de Darwin e foram introduzidos por John Holland e seus alunos em meados da década de 1970, o que resultou no livro “Adaption in Natural and Artifical Systems” publicado em 1975. Conceitos como evolução, cruzamento (crossover) e mutação são amplamente usados quando se lida com AGs. AGs podem ser usados para tratar problemas de diversos tipos e cujos parâmetros podem ser representados através de cadeias de caracteres, números reais ou sequências de bits. Pela própria forma como os computadores trabalham, a codificação binária é a preferida. 0 1 0 1 1 0 0 1 Figura 1: Representação de estrutura de dados no AG Quando estamos trabalhando na resolução de um problema complexo e – como acontece na maioria das aplicações de algoritmos genéticos – cuja representação funcional contém muitos parâmetros ou não pode ser expressa analiticamente, geralmente buscamos uma solução que seja melhor que as demais disponíveis. O conjunto formado por todas as possíveis respostas para um problema é chamado espaço de busca, de soluções ou de estados. O tratamento de um problema com algoritmos genéticos inicia-se com a determinação de um conjunto de soluções iniciais (escolhidas aleatoriamente, mas dentro de certas restrições) que forma o espaço de busca. Cada possível resposta dentro desse conjunto é um cromossomo, o qual é composto por genes. Esses genes representam parâmetros que devem ser ajustados para melhorar a solução e, consequentemente, aperfeiçoar a função analisada. A obtenção de valores melhores para resolver nossa questão, que é representada por uma função objetivo, dá-se através do uso de alguns operadores próprios dos AGs. Esses operadores são o cruzamento, a mutação e a seleção. Gene Cromossomo probabilidade de mutação, esta deve ser mantida num patamar relativamente baixo – menor que 5% –, pois sua utilidade é garantir que o AG não caia num extremo local muito rapidamente. Um fato relevante a ser analisado aqui é como evitar que boas soluções se percam durante os sucessivos cruzamentos e mutações em cada geração. Uma forma de conseguir isso é fazer com que indivíduos com alto grau de aptidão sejam inteiramente copiados para a próxima geração. A isso dá o nome de elitismo. Claramente devem ser feitas algumas escolhas iniciais para implementar nossos AGs. Primeiramente devemos considerar o tamanho de nossa população. Populações muito pequenas dão pouca margem para cruzamentos e o espaço de busca será pouco explorado. Usando populações muito grandes teremos um elevado consumo de processamento, visto que o número de interações cresce exponencialmente com a quantidade de cromossomos em cada geração. Pesquisas revelam que uma população composta por aproximadamente 30 membros são uma boa escolha para a maioria dos problemas. A forma como são escolhidos os cromossomos a serem cruzados em cada população varia de acordo com o problema, mas podemos citar seleção por roleta, Boltzman, campeonato, dentre outros. Analisaremos os métodos roleta e classificação. Na seleção por roleta, a escolha do indivíduo baseia-se na sua adequação. Quanto maior essa adequação, maior será a chance do mesmo ser escolhido para o cruzamento. Os cromossomos são divididos em grupos em que suas adaptações estão dentro de certas faixas. Por exemplo, digamos que as aptidões possam variar entre 1 e 10 e que a roleta é divida em intervalos de duas unidades e que cada um dessas fatias terá seu tamanho proporcional às aptidões. Quanto maior a quantidade de indivíduos na faixa 1-2, maior será sua fatia na roleta e, obviamente, maior será a chance se um elemento ser escolhido dentro daquela região. Figura 4: Seleção por roleta – Seleção proporcional a aptidão Fonte: http://www.cin.ufpe.br/~tbl/Aulas/SI/ag-tbl.ppt#270,21 Um problema enfrentado no uso do método da roleta surge quando há grande diferença de aptidão entre os grupos de indivíduos. Isso faz com que certos cromossomos tenham uma chance excessivamente baixa de serem escolhidos para cruzamento. Uma alternativa é usar o método de classificação para realizar o sorteio dos elementos dentro de cada geração. Nessa metodologia, os grupos são classificados em ordem decrescente de acordo com sua adequação. Assim, o grupo com menor adequação recebe a classificação 1, o segundo recebe 2 e assim sucessivamente até a última classe. As fatias de cada grupo são proporcionais às suas classificações. Observemos a diferença entre os dois métodos no estabelecimento das chances de escolha de cromossomos. Figura 5: Situação antes da Classificação (gráfico da adequação) Fonte: http://www.obitko.com/tutorials/genetic-algorithms/portuguese/selection.php Figura 6: Situação depois da Classificação (gráfico dos números de ordem) Fonte: http://www.obitko.com/tutorials/genetic-algorithms/portuguese/selection.php A forma básica de um algoritmo genético é a seguinte: 1 Início Criar uma população com n indivíduos (adequados ao problema) aleatoriamente. 2 Aptidão Avaliar a aptidão de cada cromossomo da população. 3 Nova geração Até que se tenha uma nova população, executar os passos seguintes. 3.1 Seleção Escolher dois cromossomos para serem pais de acordo com sua aptidão. 3.2 Crossover Com a probabilidade, cruzar os pais para obter-se a geração seguinte. Caso não haja cruzamento, a descendência será uma cópia dos pais. 3.3 Mutação Com a probabilidade, modificar os genes de um cromossomo para obter indivíduo alterado 3.4 Aceitação Por os novos indivíduos na nova geração. 4 Substituição Usar a nova geração na próxima execução do algoritmo. 5 Critério de parada Se a condição final for atingida, pare e devolva a melhor solução encontrada. 6 Repetir Retornar ao passo 2. O fluxograma representativo de um AG é dado a seguir, conforme a figura 7: Figura 7: Fluxograma de execução de um AG Fonte: http://www.geneticprogramming.com/Tutorial/index.html 3 ALGORITMOS GENÉTICOS E PROGRAMAÇÃO LINEAR Problemas de otimização combinatória são resolvidos por diversas técnicas, computacionais ou não. Os algoritmos genéticos são classificados na literatura como metaheurísticas e têm resolvido limitações históricas dos algoritmos convencionais de procura heurística, como, por exemplo, as interrupções antecipadas em máximos (ou mínimos) locais distantes da melhor resposta. Questões de otimização combinatória surgem quando se precisa escolher um subconjunto de dados que obedeça a certos critérios a partir de um conjunto com elementos discretos e finitos. Os problemas logísticos, tais como distribuição de mercadorias e transporte coletivo são encarados como de otimização combinatória, pois aparecem, de forma típica, em distribuições descontínuas, uma vez que estão em um espaço em que o número de locais e os caminhos entre eles são finitos. Uma grande motivação para os estudos nesse campo é a intratabilidade da maioria das questões que envolvem otimização combinatória. Não existem atualmente modelos gerais que os resolvam eficientemente, considerando fatores como memória e capacidade de processamento de sistemas computacionais. Tomadas de decisão são geralmente baseadas em alguma forma de busca em que se procura a melhor solução dentre as mais factíveis, isto é, que atendam certas condições. Um algoritmo cuja tomada de decisões é fundamentada em um resultado obtido aleatoriamente é dito probabilístico ou estocástico. Caso contrário é chamado determinístico. Desse modo, consideremos um problema de otimização combinatória – como a escolha da melhor distribuição de rotas de transporte com menor Figura 8: ArcView GIS Fonte: NARCICIO e LORENA, 2003 Neste artigo, temos como foco o roteamento de entregas de produtos/serviços de uma fonte a diversos destinatários, levando em consideração limitações como capacidade de carga do veículo transportador, consumo de combustível e tempo de entrega. Ignorar-se-á elementos como janelas de tempo causados por inatividade, congestionamento ou danos no veículo, por exemplo. Esse é, por conseguinte, uma questão muito semelhante ao clássico problema do caixeiro viajante, onde um indivíduo deve percorrer um certo número de cidades pela melhor trajetória possível e, consequentemente, consumindo menos recursos. Esse problema é uma típica aplicação cuja resposta não é obtida por algoritmos determinísticos, mas sim com algoritmos genéticos, pois o tamanho do espaço de buscas cresce exponencialmente, de acordo com o número de cidades, pois existem trajetórias possíveis a serem escolhidas, partindo de uma localidade qualquer, sendo n o número de nós. Um exemplo é ilustrado na figura 9 abaixo. Figura 9: Possíveis trajetos a partir da localidade 4 Fonte: http://pt.wikipedia.org De forma geral, o problema da menor distância a ser percorrida para atender a um certo número de clientes pode ser expresso pela seguinte configuração matemática: seja um conjunto C = {c1, c2, …, cn) das n localidades a serem visitadas e uma matriz de distâncias (ρij), sendo esta matriz expressa por ρij = ρ(ci, cj) (i, j ∈ {1, …, n}, ρij = ρji, ρii = 0). O problema consiste em encontrar a permutação π pertencente ao espaço de soluções Sn = {s: {1, …, n} {1, …, n}} que minimize a distância do trajeto representada pela função objetivo f: Sn IR simbolizada por A imagem seguinte (figura 10) mostra a determinação de um percurso de roteamento preferencial usando AGs, onde temos treze nós. A solução é apresentada em etapas (1 a 4) e ao final temos a que foi considerada ótima. Figura 10: Solução de um problema de transporte com AG Fonte: http://pt.wikipedia.org A título de comparação, há outras metaheurísticas que podem ser aplicadas a problemas de roteamento de entregas, mas cuja eficiência é inferior aos AGs. Assim, temos, por exemplo, as heurísticas de Clark e Wright e de Mole e Jameson (HEINEN & OSÓRIO, 2006). A heurística de Clark e Wright foi um dos primeiros algoritmos a solucionar o problema do roteamento de veículos, mas possui como desvantagem o fato de só levar em consideração caminhos que formam uma poligonal convexa, fazendo com que nós internos sejam excluídos no teste de economia. Sua importância diz respeito ao fato de ter aberto caminho para o desenvolvimento de algoritmos melhores. É o caso da heurística de Mole e Jameson, que é bem mais elaborada e obtém resultados muito superiores. Sua complexidade de implementação computacional é o principal obstáculo que este algoritmo enfrenta. 5 CONSIDERAÇÕES FINAIS Como tentamos mostrar nas discussões aqui apresentadas, os problemas de transporte representam uma faixa de questões muito importante nos dias atuais. Procurar a melhor forma de distribuir recursos de transporte de bens, serviços e pessoas é uma parte primordial no planejamento das organizações, seja em qual nível for. Uma vez que a complexidade de tais problemas consome uma grande quantidade de recursos computacionais e, na maioria dos casos, os mesmos não podem ser resolvidos usando ferramentas determinísticas que forneçam resultados exatos, a busca por outras formas de resolução é de suma importância. Como tais, os softwares que implementam a computação evolutiva, mais especificamente, os algoritmos genéticos, possuem grande vantagem nessa área, uma vez que trabalham com avaliações de soluções ótimas através de procedimentos de análise baseados em dados estatísticos e probabilidades. Partindo de um conjunto conhecido onde situam-se as melhores respostas, podem selecionar a que melhor se adapta ao contexto da questão. Uma proposta para um trabalho futuro centra-se em analisar o caso onde dar-se-á a utilização de uma ferramenta de visualização (um GIS, por exemplo) para analisar os dados obtidos a partir de uma ferramenta de otimização numérica aplicada a um problema de logística de entrega de recursos em trajetórias não-homogêneas, como é o caso, por exemplo, de um depósito que deve distribuir mercadorias entre vários clientes. REFERÊNCIAS ANDRADE, Eduardo Leopoldino de. Introdução a pesquisa operacional: métodos e modelos para análise de decisões. 3ª ed. Rio de Janeiro: LTC, 2004. CARVALHO, Marco Antonio Moreira de. SANTOS, André Gustavo dos. Algoritmo genético aplicado à seleção de colunas no problema de alocação de tripulações. Disponível em <http://www.bibl.ita.br/xiiencita/Comp-01.pdf>. Acessado em 11 de outubro de 2009. CHAKROBORTY, Partha. Optimal Routing and Scheduling in Transportation: Using Genetic Algorithm to Solve Difficult Optimization Problems. Disponível em <http://www.iitk.ac.in/directions/directsept04/partha~neww.pdf>. Acessado em 20 de novembro de 2009. FERREIRA, Tiago A. E. Computação evolutiva. Disponível em <http://200.17.137.109:8081/xiscanoe/courses-1/computacao-evolutiva/introducao-a-computacao- evolutiva>. Acessado em 13 de setembro de 2009. HAUPT, Randy L., WERNER, Douglas H. Genetic Algorithms in Electromagnetics. Disponível em <http://www.scribd.com/doc/13740062/Genetic-Algorithms-in-Electromagnetics>. Acessado em 14 de outubro de 2009. HEINEN, Milton R., OSÓRIO, Fernando Santos. Algoritmos genéticos aplicados a problemas de roteamento de veículos. Disponível em <http://revistaseletronicas.pucrs.br/faced/ojs/index.php/hifen/article/viewFile/3781/2893>. Acessado em 13 de setembro de 2009. HEINEN, Milton R., OSÓRIO, Fernando Santos. Uso de Algoritmos Genéticos para a Configuração Automática do Caminhar em Robôs Móveis. Disponível em <http://www.natalnet.br/sbc2006/pdf/arq0170.pdf>. Acessado em 13 de setembro de 2009. KOZA, John R. Genetic Programming: on the programming of computers by means of natural selection. Cambridge, MA: The MIT Press, 1992. KUMAR, A. John Sanjeev et alii. Intelligent transport route planning using genetic algorithms in path computation algorithms. Disponível em <http://www.eurojournals.com/ejsr_25_3_11.pdf>. Acessado em 14 de outubro de 2009. NARCISO, Marcelo Gonçalves. LORENA, Luiz Antônio Nogueira. Uso de algoritmos genéticos em sistema de apoio a decisão para alocação de recursos no campo e na cidade. Disponível em <http://www.sbiagro.org.br/pdf/iii_congresso/Artigo30.pdf>. Acessado em 25 de outubro de 2009. NEVES, Carolina de Lima. Calibração de parâmetros de modelos hidráulicos de redes de distribuição de água para estudos de operação de rede. Disponível em <http://biblioteca.universia.net/ficha.do?id=33723488>. Acessado em 14 de outubro de 2009.