ALGORITMO GENÉTICO EM PESOS SINÁPTICOS DE REDES NEURAIS ARTIFICIAIS APLICADO NO PROBLEMA DO CAIXEIRO VIAJANTE Fabriciu Alarcão Veiga Benini Instituto Federal de Educação, Ciência e Tecnologia de São Paulo Câmpus São Carlos, professor doutorando Email:
[email protected] Área: Ciências tecnológicas
RESUMO Esse trabalho tem como objetivo usar múltiplos agentes com variabilidade na carga genética para resolver o Problema do Caixeiro Viajante através de Algoritmo Genético (AG) para treinar os pesos sinápticos de uma Rede Neural Artificial (RNA) do tipo Perceptron. Cada agente é composto por uma RNA diferente. Podem existir diversos no algoritmo formando então uma população, aqui denominado de Agente Inteligente (AI). Cada uma das RNAs, ou AI, possui uma cadeia de código genético que compõe uma matriz, sendo que essa sequência genética constitui os próprios pesos sinápticos da RNA. O presente trabalho tem como objetivo minimizar o efeito estocástico nas decisões dos AI, potencializando a característica da rede neural para identificar algum tipo de padrão no problema proposto, associando também a isso a adaptabilidade do AG. Os resultados obtidos foram satisfatórios demonstrando que a técnica é apropriada para resolver esse tipo de problema combinacional de forma eficiente.
ABSTRACT This paper aims to use multiple agents to solve the problem of a Salesman by Genetic Algorithm (GA) to train the synaptic weights of an Artificial Neural Network (ANN) type Perceptron. Each agent is composed of an ANN. There may be many in the algorithm then forming a population, here called Intelligent Agents (IA). Each of the ANNs, or IA has a string of genetic code that makes up a matrix, and this genetic sequence is their own synaptic weights of ANN. This study aims to minimize the stochastic effect on the decisions of IA, enhancing the characteristic of neural network to identify some kind of pattern in the proposed issue by associating also that the adaptability of the GA. The results were satisfactory, showing that the technique is suitable to solve such a combinational problem efficiently.
Palavraschave: problema do caixeiro viajante, algoritmo genético, rede neural artificial.
Introdução Problemas de cobrimento de nós têm aplicações práticas no dia a dia da sociedade. Um veículo de coleta de lixo, por exemplo, precisa traçar um itinerário para coletar os tambores de lixo sem repetir a passagem pelo ponto já visitado, para depois levar os resíduos para o depósito. Quanto menor o caminho traçado, menos desperdício de recursos e tempo haverá para se executar a tarefa. A mesma regra vale para o carteiro entregar as correspondências. Ele parte da central entregando as correspondências e no final retorna para o mesmo ponto. Em problemas de produção, onde o sequenciamento de n tarefas em uma única máquina visa minimizar o tempo total de execução das mesmas, assim como na linha de montagem de componentes eletrônicos, buscase encontrar o roteiro de mínima distância para um equipamento cuja tarefa é soldar todos os componentes de uma placa eletrônica. O menor percurso total do equipamento para percorrer todos os pontos da placa está diretamente associado à produtividade da linha [1]. Por outro lado, problemas combinatórios têm ampla aplicação no campo computacional. São usados, por exemplo, em problemas de agrupamento (clustering) para classificação de dados e na recuperação de informações a partir de análises efetuadas em bases de dados. Um algoritmo de agrupamento procura grupos naturais inerentes aos dados, usando medidas de distâncias entre si com similaridades entre eles individualmente [2]. Algoritmos de criptografia também usam largamente sistemas combinatórios para codificar e decodificar dados. O Problema do Caixeiro Viajante (PCV) emprega otimização combinatória e sua dificuldade está no número elevado de soluções existentes. Ele pertence à categoria conhecida como NPdifícil, que significa que possui ordem de complexidade exponencial. Assumindo que a distância de uma cidade i a outra j seja simétrica, isto é, que dij = dji , o número total de soluções possíveis é dado conforme a equação (1):
C = (n – 1)! / 2
(1)
Desta forma, a resolução do PCV por enumeração completa é inviável para valores elevados de n. Em outras palavras, o esforço computacional para a sua resolução cresce exponencialmente com o tamanho do problema. Pela sua definição singela e o grau de abrangência que pode ser aplicado, tornouse um dos problemas mais estudados em otimização combinatória. Centenas de artigos têm sido publicados sobre o PCV [3]. O estudo do PCV desperta atenção pela possibilidade de aplicação em diferentes campos, tais como
pesquisa operacional, matemática, física, biologia e, no caso deste artigo, inteligência artificial com foco em RNA. Consequentemente, o mesmo tem sido usado como benchmark para avaliação de novos algoritmos e estratégias de solução que envolvem busca e otimização. O PCV apresentado aqui consiste em fazer um “viajante” passar por todas as cidades ou nós uma única vez, percorrendo ainda a menor distância possível. O algoritmo desenvolvido no Matlab gera um mapa onde as localizações das cidades são colocadas em posições aleatórias a cada vez que se inicia uma nova otimização. Essa particularidade permite analisar a adaptabilidade do algoritmo a diferentes distribuições e, consequentemente, a diferentes padrões de posicionamento dos nós.
1. Metodologia A posição de n nós, representando as cidades, são realizadas aleatoriamente. Duas tabelas na forma matricial de ordem n são geradas para representar esses nós, uma simétrica contendo as distâncias entre eles, cuja diagonal vale zero e outra, aqui denominada de matriz dos pesos de passagens (MPP), contendo valores proporcionais ao número de passagens dos Agentes Inteligentes (AI), sendo seu valor inicial igual a zero, desse modo é possível conhecer as rotas mais utilizadas pelos diferentes entes. A MPP é atualizada a cada iteração dos AI. Tanto o número relativo à posição da linha quanto a da coluna representam o número do nó, enquanto que a célula referente ao ponto de intersecção entre o número da linha com o da coluna está a distância entre os dois nós, o mesmo vale para a MPP. Todo AI possui uma tabela exclusiva, atualizada, informando quais nós foram visitados e consequentemente quais não, essa tabela atualizada é utilizada pelo algoritmo como entrada das diversas RNA que constitui um AI, com isso a cada passo as entradas das RNAs são atualizadas apenas com os nós que restam serem visitados, completando com zero as demais entradas. Podemos dividir um AI em duas partes, ambas baseadas em RNA. Essas duas partes são aqui denominadas por módulo intuitivo e módulo cognitivo.
Figura 1 Rede perceptron de uma camada e três entradas que constitui o módulo intuitivo. Esse módulo possui n RNA como esse, um para cada possível próximo nó. Os pesos sinápticos são a própria cadeia genética.
Primeiro é executado o módulo intuitivo, ele gera algumas sugestões de próximo nó, a partir da localização atual, para se deslocar. Essa lista pode conter desde zero sugestões até o número de nós ainda não visitados. Aqui ilustrado na Figura 1, este é composto por n RNA de uma camada e três entradas que são, uma bias com valor fixo igual a 1, a segunda é a entrada da distância entre o nó atual até um ainda não visitado e a terceira entrada é para o peso da MPP, dessa forma o módulo cognitivo só irá utilizar essa distância quando a saída for maior que zero [4,5]. A sequência das distâncias para as entradas das respectivas redes perceptrons deve ser disposta em ordem crescente, tal como ilustrado na Figura 2. O módulo intuitivo ajusta seus pesos sinápticos por meio de um algoritmo genético [6][8], onde os próprios pesos constitui o código genético. A premiação é inversamente proporcional à distância percorrida por todos os nós até o nó original, quanto menor a distância percorrida maior será o prêmio. O sistema de algoritmo genético adotado aqui privilegia os mais fortes,
com isso a herança genética tem mais chances de ser disseminada pela população e, assim, há uma evolução mais acelerada em relação aos AI mais bem adaptados ao contexto do problema onde se encontram. Todos os resultados das saídas, cujos valores são maiores que zero, são candidatos em potencial para ser o próximo nó a ser visitado, sendo então passados para o módulo cognitivo.
Figura 2 Rede de perceptrons do módulo intuitivo, as entradas e saídas dos neurônios perceptron são independentes uns dos outros e devem obedecer uma ordem crescente das distâncias para o resultado ser repassado para o próximo módulo na mesma sequência.
A lista de sugestões de próxima cidade é então repassada para o módulo cognitivo, o qual é baseado em um único neurônio cujo número de entradas é igual ao total de nós do problema menos o próprio nó em que o AI se encontra, conforme ilustrado na Figura 3. O processo de aprendizado deste módulo ocorre ajustando cada peso sináptico um a um, observando o desempenho final da distância percorrida. À medida que o conjunto de sugestões repassado pelo módulo intuitivo chegam, o resultado da saída faz com que o AI avance para o próximo nó. Após o último nó percorrido o algoritmo compara a distância total com a da iteração anterior e com base nisso decide se parte para uma próxima geração ou se é necessário ajustar os pesos sinápticos.
Figura 3 Módulo cognitivo composto de um neurônio com número de entradas igual ao total de nós menos um e saída igual à distância aproximada para o próximo nó onde o AI deve seguir.
O princípio de funcionamento do módulo cognitivo deve ser simples para minimizar o custo computacional. Como seria necessário escolher um desses nós préselecionados pelo módulo intuitivo através de mais processamento, testando cada um dos nós cuja saída do perceptron fosse maior que zero e, dentre essa lista de sugestões de próximo nó, o algoritmo genético acabaria convergindo para apenas um deles mais adiante, após testar todos, optouse em experimentar acelerar esse processo através do módulo cognitivo. Assim, antes que venha uma nova geração, o módulo cognitivo usa os nós sugeridos para determinar qual a distância mais conveniente entre o atual nó e o próximo através da tentativa e erro, ajustando um a um os pesos desse neurônio com uma resolução de ajuste inicialmente de 0,5, refinandose na medida em que venham novas gerações. Portanto, o processo de ajuste dos pesos sinápticos que compõe o módulo cognitivo seria feito em paralelo à evolução do módulo intuitivo à medida que novas gerações surgem. Inicialmente os pesos sinápticos são iguais a zero, sendo que o módulo começa ajustando inicialmente o peso do bias (cuja entrada é igual a menos um). O critério de ajuste dos pesos é o seguinte: a primeira vez o peso é incrementado com valor igual a um, sendo então que o AI executa uma viagem completa por todos os nós para computar a distância total armazenandoa. Na segunda iteração do peso, há o decremento em 0,5, e uma nova viagem é executada, a nova distância é comparada com a anterior, se o resultado for melhor, seguese decrementando o peso até se obter um resultado pior que o anterior. Nesse caso, restaurase o valor do peso anterior e passase a iterar com o peso da entrada seguinte, executandose os mesmos passos até chegar ao primeiro peso. Quando todos os pesos forem ajustados, uma nova geração de entes é iniciada e o ajuste dos pesos de cada ente continua do mesmo ponto da geração anterior, excetuandose o ente que desencadeou uma nova geração. O ajuste começa a partir do último peso sem zerar os ajustes já realizados na geração anterior, sendo que dessa vez a resolução de ajuste dos pesos são divididos ao meio, ou seja, ele incrementa em 0,5 na primeira iteração e depois começa a decrementar em 0,25, cuja resolução vai sendo reduzida à metade a cada nova geração. A Figura 4 ilustra uma curva típica de convergência utilizando algoritmo genético, relativa à evolução de um problema combinacional onde se tenta encontrar a solução ótima que tenha a menor distância percorrida. O eixo horizontal representa as épocas e o eixo vertical indica a distância [2]. Como o gráfico demonstra, existe um tempo de adaptação até que este comece a apresentar resultados viáveis.
Figura 4 Curva típica de convergência com o passar das gerações em um problema combinacional usando algoritmo genético.
Na Figura 5 os pontos representam AI pertencente a uma geração específica, o eixo das ordenadas contem o número de viagens necessárias antes de mudar para uma nova geração e a abscissa o número do AI ao longo das gerações. É possível notar que o processamento dos entes começa na região mais densa do gráfico, ou seja, na região otimizada, restando apenas fazer o refinamento através do módulo cognitivo.
Figura 5 Número de viagens executadas por geração em função de 20 Agentes Inteligentes em diferentes geração (cada ponto representa uma geração),
Como o problema do caixeiro viajante apresenta ordem exponencial, existem inúmeras soluções subótimas para o problema, sendo que o algoritmo genético tem uma tendência natural de convergir a
uma dessas soluções de modo que o código genético de toda população se homogeneíze. Mesmo acrescentando mutação, a variabilidade é pouca e geralmente insuficiente para melhorar a solução, o que nesse caso pode convergir para uma solução subótima. Uma alternativa usada aqui foi, após algumas iterações, uma parte da população começa o processo do zero. Gerase então uma nova população com cadeia cromossômica aleatória e os pesos do módulo cognitivo ficam novamente iguais a zero, fazendose que o sistema convirja para novas soluções, havendo assim uma melhor exploração do conjunto de soluções do sistema.
2. Resultados e discussão Tabela 1. Numeração e coordenadas dos nós do mapa de teste ilustrado na Figura 6.
Para testar a eficiência do sistema proposto, foi gerado um gráfico com 20 nós conforme ilustra a Figura 6, sendo que a Tabela 1 possui as coordenadas dos nós. Foi colocado basicamente 3 conjuntos de AI para testar o desempenho. Inicialmente, uma bateria de testes usando apenas 5 AI, seguindo com 30 AI e, finalmente, foi realizado mais uma bateria de testes com 50 AI, buscandose um caminho ótimo simultaneamente. Limitaramse todas as simulações em 350 gerações, a Tabela 2 mostra os resultados obtidos. O melhor desempenho com menor distância percorrida que se conseguiu obter foi após 2000 gerações usando 30 AI para o mapa da Figura 6, foi uma distância igual a 327,1235.
Figura 6 Mapa contendo 20 nós para ser otimizado pelos AI.
Através da Tabela 2 é possível observar que a melhor relação custo/benefício foi encontrada para 30 AI. Para 50 AI, temse resultados mais homogêneos, enquanto que para 5 AI, obtém muita dispersão nos resultados. A Figura 7 ilustra os respectivos melhores caminhos encontrados por cada bateria de testes com as 3 quantidades de AI. Observe que as aparências dos caminhos são similares. Tabela 2. Desempenho em relação ao número de formigas para o mapa da Figura 6 em 350 gerações.
Simulação número
Menor distância encontrada para 5 formigas
Menor distância encontrada para 30 formigas
Menor distância encontrada para 50 formigas
1
355.2919
338.7914
340.9970
2
359.3728
333.2395
340.9970
3
357.4098
333.3715
340.3058
4
362.7146
328.9515
340.3058
Figura 7 Gráficos dos caminhos com melhores resultados de cada bateria de testes para 5, 30 e 50 AI respectivamente.
Finalmente, para demonstração do potencial do algoritmo, tentouse otimizar um mapa contendo 200 nós, conforme ilustra a Figura 8. Utilizouse nesta simulação um total de 50 formigas, sendo que o mapa produzido fornece uma rota bem mais otimizada quando comparada ao estágio inicial da simulação.
(a)
(b) Figura 8 Primeiro caminho encontrado para um mapa com 200 nós (a) e um resultado intermediário antes da primeira geração terminar usando 50 formigas (b).
3. Conclusões Com base nos resultados, concluiuse que o algoritmo é eficiente para aplicações em problemas de otimização combinacional, sendo de fácil implementação e obtendo resultados satisfatórios. Vale também ressaltar o tempo de processamento relativamente reduzido. Para se obter os resultados da bateria de testes da Tabela 2 para 30 entes, por exemplo, foram necessários 3 minutos em um Pentium 4 de 2GHz. Foi observado uma complementação entre os módulos, fazendose o sistema convergir para a melhor sugestão proveniente do módulo intuitivo e frente ao peso das passagens que influencia no ajuste do peso sináptico e ao mesmo tempo não interfere na ação dos AI explorarem mais de um caminho subótimo. Evitouse assim dispersões, concentrando o processamento em uma direção específica sem deixar as possibilidades de novos caminhos ainda não detectados.
Referências [1] P. S. Souza, “Asynchronous organizations for multialgorithms problems,” Tese de Doutorado, University Carnegie Mellow, Department of Electrical and Computer Engineering, Pittsburgh, 1993. [2] J. C. Furtado, “Algoritmo Genético Construtivo na Otimização de Problemas Combinatoriais de Agrupamentos,” Tese de Doutorado em Computação Aplicada, INPE, 1998. [3] C. B. Cunha, U. O. Bonasser e F. T. M. Abrahão, “Experimentos Computacionais com Heurísticas de Melhorias para o Problema do Caixeiro Viajante,” Anais do XVI Congresso de Pesquisa e Ensino em Transportes, ANPET, Natal/RN, vol. 2, pp. 105117, 2002. [4] S. Haykin, Neural Networks: A Comprehensive Foundation, Prentice Hall, 2nd Edition, Upper Saddle River, NJ, USA, 1999.
[5] L. H. Tsoukalas, R. E. Uhrig, Fuzzy and Neural Approaches in Engineering, John Wiley, New York, USA, 1997. [6] D. Dasgupta, Z. Michalewicz, Evolutionary Algorithms in Engineering Applications, SpringerVerlag, Berlin, Germany, 1997. [7] D. E. Goldberg, The Design of Innovation (Genetic Algorithms and Evolutionary Computation, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002. [8] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, SpringerVerlag, 3rd Edition, Berlin, Germany, 1999.
