Capítulo I



Baixar 111,68 Kb.
Encontro26.05.2017
Tamanho111,68 Kb.

Busca Multimodal Utilizando Algoritmos Evolutivos

UNIVERSIDADE ESTADUAL DE CAMPINAS

Faculdade de Engenharia e Elétrica e de Computação

IA 707 – Computação Evolutiva


REVISÃO BIBLIOGRÁFICA: BUSCA MULTIMODAL UTILIZANDO ALGORITMOS EVOLUTIVOS

Profs.: Leandro N. de Castro & Fernando J. Von Zuben.

Alunos: Andréa Leda R. de Oliveira Ojima - 015015

Evandro José Theodoro - 018-78



SUMÁRIO


1 Introdução 4

Referências 4



2 Conceitos e APLICAÇÕES 5

Referências 7

2.1 Método de Niching 8

Referências 9



2.1.1 Fitness Sharing 11

Referências 12



2.1.2 Crowding 13

Referências 14

2.2 Evolução Cooperativa 15

Referências 16

2.3 Abordagens Híbridas 16

Referências 17

2.4 modificações em algoritmos evolutivos aplicados em otimização multimodal 17

Referências 20

2.5 Otimização Multimodal e Estratégias Evolutivas 20

Referências 21





  1. Introdução

O processo de otimização esta relacionada com a busca da melhor solução para problemas em um conjunto finito ou infinito de soluções. A busca se dá por uma solução inicial ou um conjunto delas, realizando melhoras até chegar a um outro conjunto que tenha uma ou todas as melhores soluções possíveis dentro do espaço de busca.

A otimização pode ser vista como a minimização de custos ou maximização de receitas obtendo pontos de mínimo ou máximo para uma função qualquer. Uma vez sujeito a condições de restrição temos um problema restrito.

Uma função pode apresentar um ou muitos pontos de mínimos, o que define se ela é unimodal ou multimodal. Uma função unimodal apresenta apenas um ponto de mínimo ou máximo. Uma função multimodal, por sua vez, possui várias inflexões de sua superfície, o que caracterizam múltiplos pontos de mínimo ou máximo.

Cada tipo de algoritmo é adequado para uma classe de problemas. Existem os algoritmos que possuem comportamento determinísticos quanto à previsão dos passos de uma configuração inicial. Por outro lado, existem os chamados algoritmos estocásticos cujos passos não podem ser previstos a partir de uma configuração inicial.

Estão dentro da classe de algoritmos estocásticos, os chamados busca tabu (tabu search), algoritmo evolutivo (evolutionary algorithm) e recozimento simulado (simulated annealing), entre outros.


Referências


  • Bazaraa, M. S., Sheralli, H. D. e Shetty, C.M. Nonlinear Programming: Theory and Applications, second ed., John Whiley & Sons, 1993. keyword: otimização resolução problemas.

  • Luenberger, D., Linear and Nonlinear Programming. Addison-Wesley, 1984. keyword: otimização resolução problemas

  • Oliveira, A. C. M. Algoritmos Evolutivos para Problemas de Otimização com Variáveis Reais. São José dos Campos. Setembro/2001. Monografia (Computação Aplicada). Instituto Nacional de Pesquisas Espaciais (INPE), Ministério da Ciência e Tecnologia. 52p. Google keyword: multimodal optimization genetic algorithm. (http://www.lac.inpe.br/~lorena/pos-grad.html) em 09/09/2002.



  1. Conceitos e APLICAÇÕES

O conceito básico dos algoritmos evolutivos é o de manter uma população de indivíduos que indiquem soluções candidatas para problemas que evoluem ao longo de gerações através de um processo de competição, onde os mais aptos (melhores fitness) têm maiores chances de sobreviver e se reproduzir. A reprodução se baseia em um processo de seleção de indivíduos e modificação das soluções candidata que eles representam, através de operadores como cruzamento (ou crossover) e mutação.

Com relação ao processo de otimização, o processo de busca da solução está ligado na evolução da população ao longo das gerações. Assim, espera-se que o mais evoluído indivíduo represente a solução ótima.

Os algoritmos que se baseiam em população de soluções podem convergir para pontos isolados do espaço de busca que representem mínimos globais de funções multimodais. Entretanto, a evolução da população tende a excluir indivíduos com baixa aptidão, perdendo-se informação genética importante para a busca de outros mínimos globais.

Para tentar minimizar este problema alguns métodos podem ser utilizados em conjunto com algoritmos genéticos, como é o caso do método de Niching que engloba o Fitness Sharing e o Crowding, tendo ainda Speciation, Evolução Cooperativa, Hibridização, Algoritmos Genéticos Modificados, entre outros.

Os estudo realizados por Kennedy e Spears (1998) utilizam um gerador de problema multimodal para testar três versões de um algoritmo genético e um algoritmo de conjuntos binários em um experimento de séries temporais fatoriais, identificando vantagens e desvantagens dos vários algoritmos.

O estudo foi construído sob a forma de um experimento fatorial de repetidas medidas, trazendo resultados de análise multivariada das variâncias. As questões desse caso envolvem vários aspectos relacionados ao desempenho dos algoritmos binários e dos algoritmos genéticos com mutação ou crossover, ou ambos. Uma dificuldade com comparações empíricas de algoritmos de busca diz respeito à generalização, que não pode ir além dos problemas de prova usados. Há vários meios de fortalecer os resultados obtidos de estudos empíricos.

Uma vantagem de geradores de problema é que podem ser parametrizados, permitindo projetar experiências controladas no qual uma ou mais propriedades de uma classe de problemas podem ser variadas sistematicamente para estudar os efeitos em um algoritmo de busca.

A multimodalidade de um espaço de busca (número de picos) é uma importante característica do espaço de busca. Pode-se utilizar um gerador simples de problema, que produza problemas casuais com um grau de multimodalidade controlável.

A motivação para este gerador pode ser o interesse nas diferenças entre mutação e crossover em algoritmos genéticos. Considerando um problema simples de dois picos, com o ótimo em 000... 000 e 111... 111. Os indivíduos com 50% 1’s (uns) e 0’s (zeros) tem menores fitness, enquanto indivíduos com principalmente 1’s ( uns) ou principalmente 0’s (zeros) tem maiores fitness.

A mutação de qualquer indivíduo com alto fitness individual em qualquer pico tenderá a manter o indivíduo naquele pico. O crossover, entretanto, produz resultados bem diferentes, dependente da localidade dos pais. Se os dois pais estão no mesmo pico, a progênie também terá grande chance de estar naquele pico. Entretanto, se os dois pais estão em dois picos diferentes, a progênie terá chances de estar no vale entre os dois picos, onde o fitness é baixo.

Uma hipótese que pode ser considerada é que o crossover pode alterar o desempenho de um GA em problema de dois picos. E se caso houvesse mais de dois picos? Seria mais razoável a hipótese de que o crossover pode ser mais deletério, desde que os indivíduos estiverem em picos diferentes podendo produzir progênies com baixo fitness, até que a população tenha convergência a um pico. Para explorar estas hipóteses um gerador de problema multimodal pode ser criado, em que o número de picos (o grau de multimodalidade) pode ser controlado facilmente e metodicamente pelo experimento.


Referências


  • Bessaou, M, Siarry, P. A genetic algorithm with real-value coding to optimize multimodal continuous functions. Structural and Multidisciplinary Optimization 2001. pp. 63-74. Web of Science, keyword: evolutionary algorithm multimodal optimization em 13/09/2002.

  • GAGE PJ, BRAUN RD, KROO IM. Interplanetary Trajectory Optimization Using a Genetic Algorithm. Journal of the Astronautical Sciences. 43 (1): pp. 59-75 Jan-Mar 1995. Web of Science, keyword: evolutionary algorithm multimodal optimization em 13/09/2002.

  • Goldberg D. E., Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Inc. 1989. keyword: evolutionary algorithm multimodal optimization

  • kennedy j., spears w. m. Matching Algorithms to Problems: An Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimodal Problem Generator. Evolutionary Computation. IEEE 1995. pp. 78 – 83. keyword: evolutionary algorithm multimodal optimization

  • Hocaoglu C, Sanderson AC. Planning multiple paths with evolutionary speciation. IEEE Transactions on Evolutionary Computation. 5 (3) Jun 2001. pp.169-191, Web of Science, keyword: evolutionary algorithm multimodal optimization em 13/09/2002.

  • Louchet J. From Hough to Darwin: An individual evolutionary strategy applied to artificial vision. Artificial Evolution Lecture notes in Computer Science. 1829: pp. 145-161 2000. Web of Science, keyword: evolutionary algorithm multimodal optimization em 13/09/2002.

  • Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer - Verlag, New York. 1992. keyword: evolutionary algorithm multimodal optimization

  • MITCHELL M. Evolutionary Computation. (http://mit.edu/) keyword: evolutionary algorithm multimodal optimization (http://cognet.mit.edu/MITECS/Entry/mitchell) em 09/09/2002.

  • Oliveira, A. C. M. Algoritmos Evolutivos para Problemas de Otimização com Variáveis Reais. São José dos Campos. Setembro/2001. Monografia (Computação Aplicada). Instituto Nacional de Pesquisas Espaciais (INPE), Ministério da Ciência e Tecnologia. 52p. Google keyword: multimodal optimization “genetic algorithm”. (http://www.lac.inpe.br/~lorena/pos-grad.html) em 09/09/2002.

  • Pozo A. et. al. Computação Evolutiva. Universidade Federal do Paraná. Depto. de Informática. Apostila 61p. Google keyword: computação evolutiva. (http://www.inf.ufpr.br/~aurora/tutoriais/Ceapostila.pdf) em 09/09/2002

  • Schneider G, Schuchhardt J, Wrede P. Evolutionary optimization in multimodal search space. Biological Cybernetics 74 (3). Mar 1996. pp. 203-207. Web of Science, keyword: multimodal optimization genetic algorithm. em 13/09/2002.

  • Shazely S.; Baraka H.; Abdel-Wahab, A. Solving graph partitioning problem using genetic algorithms Circuits and Systems, 1998. Proceedings. 1998 Midwest Symposium on , 1999. pp. 302 –305. Web of Science keyword: genetic algorithm multimodal optimization em 13/09/2002.

  • Siarry p., petrowski a., bessaou m. A multipopulation Genetic Algorithm aimed at multimodal optimization. Advances in Engineering Software. 33 (4): 207-213 Apr. 2002. pp. 203-207. Web of Science, keyword: multimodal optimization genetic algorithm em 13/09/2002.



    1. Método de Niching

Os chamados métodos de Niching estendem os algoritmos evolutivos para domínios que requerem a localização e manutenção de soluções múltiplas. Tais domínios incluem aprendizado de máquina, classificação, otimização de funções multimodais e multi-objetivo.

Em analogia com a natureza, dentro de um mesmo ambiente existem diferentes nichos que podem suportar diferentes tipos de vidas (espécies ou organismos). O número de organismos contidos dentro de um nicho é determinado pela fertilidade do nicho e pela eficiência de cada organismo para explorar essa fertilidade.

Os métodos de Niching podem ser divididos em categorias baseados na estrutura e no comportamento, entre elas fitness sharing e crowding. As duas categorias contem os métodos que são capazes de encontrar e de manter soluções múltiplas dentro da população, mesmo que essas soluções tenham a aptidão idêntica ou não.


Referências


  • CEDENO W., VEMURI V. R. Analysis of speciation and niching in the multi-niche crowding GA. Theoretical Computer Science. 229 (1-2): pp. 177-197 Nov 6 1999. Web of Science, keyword: niching multimodal optimization em 13/09/2002.

  • Gan J.; Warwick K. Dynamic Niche Clustering: a fuzzy variable radius niching technique for multimodal optimization in GA’s Evolutionary Computation Congress, 2001. vol. 1 pp. 215-222. Web of Science, keyword: niching multimodal optimization em 13/09/2002.

  • GAN J., WARWICK K. Modeling niches of arbitrary shape in genetic algorithms using Niche Linkage in the Dynamic Niche Clustering framework Evolutionary Computation, 2002. CEC '02. Proceedings of the 2002 Congress. vol. 1 pp. 43-48. Web of Science, keyword: niching multimodal optimization em 13/09/2002.

  • Grueninger T., Wallace, D. Multi-modal optimization using genetic algorithms. Technical report. MIT CADlab.1996. (http://mit.edu/) keyword: genetic algorithm multimodal optimization (http://cadlab.mit.edu/publications/) em 09/09/2002.

  • KIM J., CHO D., JUNG H., LEE C. Niching genetic algorithm adopting restricted competition selection combined with pattern search method. IEEE Transactions March 2002. vol. 38, pp. 1001-1004. Web of Science, keyword: niching multimodal optimization em 13/09/2002.

  • LEE, C. G., CHO, D. H., JUNG, H. K. Niching genetic algorithm with restricted competition selection for multimodal function optimization. IEEE 35 (3), 1999. pp. 1722 – 1725. Web of Science, keyword: niching multimodal optimization em 13/09/2002.

  • Mahfound, S. W. “Niching Methods”, in Evolutionary Computation 2.– Advanced Algorithms and Operators, Back T., Foge, D. B., Hichatewicz Z. (orgs.). Inst. of Physics Publishing, Bristol and Philadelphia. cap 13. pp. 87 – 92. keyword: niching multimodal optimization

  • Miller B.L.; Shaw M.J. Genetic algorithms with dynamic niche sharing for multimodal function optimization IEEE International Conference. Evolutionary Computation, 1996. pp. 786-791. Web of Science, keyword: niching multimodal optimization em 13/09/2002.

  • Oliveira, A. C. M. Algoritmos Evolutivos para Problemas de Otimização com Variáveis Reais. São José dos Campos. Setembro/2001. Monografia (Computação Aplicada). Instituto Nacional de Pesquisas Espaciais (INPE), Ministério da Ciência e Tecnologia. 52p. Google keyword: multimodal optimization “genetic algorithm”. (http://www.lac.inpe.br/~lorena/pos-grad.html) em 09/09/2002.

  • PENG J. X., THOMPSON S., KANG L. A gradient-guided niching method in genetic algorithm for solving continuous optimization problems Intelligent Control and Automation, Proceedings of the 4th World Congress 2002. vol. 4 , pp. 3333-3338. Web of Science keyword: niching multimodal optimization em 13/09/2002.

  • Petrowski A. A clearing procedure as a niching method for genetic algorithms. Evolutionary Computation, 1996., IEEE International Conference 1996. pp. 798-803. Web of Science keyword: niching multimodal optimization em 13/09/2002.

  • Pozo A. et. al. Computação Evolutiva. Universidade Federal do Paraná. Depto. de Informática. Apostila 61p. Google keyword: computação evolutiva. (http://www.inf.ufpr.br/~aurora/tutoriais/Ceapostila.pdf). em 09/09/2002.

  • SARENI B., KRAHENBUHL L. Fitness sharing and niching methods revisited. Evolutionary Computation, IEEE Transactions Sept. 1998. vol.2 , pp. 97-106. Web of Science keyword: niching multimodal optimization em 13/09/2002.

  • Shazely S.; Baraka H.; Abdel-Wahab, A. Solving graph partitioning problem using genetic algorithms Circuits and Systems, 1998. Proceedings. 1998 Midwest Symposium on , 1999. pp. 302 –305. Web of Science keyword: sharing multimodal optimization em 13/09/2002.
      1. Fitness Sharing

Foi introduzido um mecanismo de compartilhamento de recursos, conhecido como sharing. Neste mecanismo, o objetivo é reduzir o valor de aptidão de indivíduos que têm membros altamente similares dentro da população.

Nesta técnica o algoritmo genético tradicional é modificado no módulo de avaliação de aptidão. Cada indivíduo tem seu valor de aptidão reduzido de acordo com a quantidade de indivíduos idênticos ou similares dentro da população. Com isto, o algoritmo tem uma menor probabilidade de que muitos indivíduos do mesmo nicho sejam selecionados, forçando uma maior diversidade populacional.

Em Genotypic Sharing, a função de distância d simplesmente é a distancia Hamming entre duas strings. (a distância Hamming é o número de bits que não emparelham quando comparamos duas strings.) Genotypic Sharing geralmente é empregado por falta ou como último recurso, quando nenhum fenótipo está disponível ao usuário.

Em Phenotypic Sharing, a função de distância d é definida usando um problema específico de conhecimento do fenótipo. Dado um problema de otimização de uma função que contém k variáveis, a escolha mais comum para uma função de distância de fenótipo é a função de distância Euclidiana. Dado um problema de classificação, a distância de fenótipo entre duas regras de classificação pode ser definida baseando-se nos exemplos em que ambas se aplicam.

O método fitness sharing foi usado largamente em algoritmos genéticos para otimização de funções multimodais, multi-objetivos e machine learning. São freqüentemente implementados com uma função de scaling, que ajusta um fitness sharing de um indivíduo jovem melhorando o desempenho do algoritmo genético. Entretanto, existe a dificuldade na escolha da função de scaling, sendo necessário um melhor embasamento científico.

Algumas evidências teóricas e empíricas indicam que uma grande população deve ser usada para aplicação de uma função de scaling em fitness sharing. O uso do algoritmo Hill-climbing com alguns ajustes, assim como também o algoritmo Simulated-annealing, pode melhorar a função de scaling durante o processo, obtendo-se melhores resultados.

Referências


  • darwen p., yao x. A Dilemma for Fitness Sharing with a Scaling Function. Evolutionary Computation. IEEE 1995. pp. 166 – 171. keyword: sharing multimodal optimization.

  • Mahfound, S. W. “Niching Methods”, in Evolutionary Computation 2.– Advanced Algorithms and Operators, Back T., Foge, D. B., Hichatewicz Z. (orgs.). Inst. of Physics Publishing, Bristol and Philadelphia. cap 13. pp. 87 – 92. keyword: sharing multimodal optimization.

  • EL IMRANI A., EL ABIDINE HZ., LIMOURI M. et al. Multimodal Optimization of Thermal Histories. pp. 573 – 577 1999. Web of Science, keyword: sharing multimodal optimization em 13/09/2002.

  • Gan J.; Warwick K. Dynamic Niche Clustering: a fuzzy variable radius niching technique for multimodal optimization in GA’s Evolutionary Computation Congress, 2001. vol. 1 pp. 215-222. Web of Science, keyword: sharing multimodal optimization em 13/09/2002.

  • Loughlin DH, Ranjithan SR, Brill ED, Baugh JW. Genetic algorithm approaches for addressing unmodeled objectives in optimization problems. Engineering Optimization. 33 (5): pp. 549-569 2001. Web of Science, keyword: sharing multimodal optimization em 13/09/2002.

  • Miller B.L.; Shaw M.J. Genetic algorithms with dynamic niche sharing for multimodal function optimization IEEE International Conference. Evolutionary Computation, 1996. pp. 786-791. Web of Science, keyword: sharing multimodal optimization em 13/09/2002.

  • QI H. A genetic algorithm with tabu list and sharing scheme for optimal design of electrical machines. Electric Machine and Power Systems. 27 (5): pp. 543-552 May 1999. Web of Science, keyword: sharing multimodal optimization em 13/09/2002.

  • SARENI B., KRAHENBUHL L. Fitness sharing and niching methods revisited. Evolutionary Computation, IEEE Transactions Sept. 1998. vol.2 , pp. 97-106. Web of Science keyword: sharing multimodal optimization em 13/09/2002.

  • Shazely S.; Baraka H.; Abdel-Wahab, A. Solving graph partitioning problem using genetic algorithms Circuits and Systems, 1998. Proceedings. 1998 Midwest Symposium on , 1999. pp. 302 –305. Web of Science keyword: sharing multimodal optimization em 13/09/2002.



      1. Crowding

Outro mecanismo denominado crowding foi proposto por De Jong (1975) para manter diversidade na população. Neste esquema, a substituição de indivíduos na população é modificada para fazer com que novos indivíduos substituam outros similares com menor valor para a função de aptidão dentro da população.

Para determinar semelhança, os métodos de crowding, assim os métodos de sharing, utilizam uma medida de distância, genotípica ou fenotípica. Os métodos de crowding tendem a distribuir os indivíduos entre os máximos locais do espaço de busca. Ao contrário dos métodos de sharing, os métodos de crowding não alocam os indivíduos com fitness semelhante nos mesmos máximos locais. Ao invés disso, o número de indivíduos que se concentra sobre um máximo, na maioria das vezes é determinado pela própria dimensão do pico de máximo para posterior crossover.

Substituindo elementos semelhantes, os métodos de crowding se esforçam a manter a diversidade preexistente na população. Porém, erros de substituição podem impedir alguns métodos de crowding de manter indivíduos na redondeza dos máximos globais. O algoritmo de Deterministic Crowding é projetado para minimizar o número de erros de substituição, e assim permite niching efetivo.

Para o desenvolvimento de trabalhos de Deterministic Crowding, deve-se primeiro agrupar os elementos dentro da população. Então todos os pares são cruzados e mutados para produzir descendentes. Cada descendência compete contra um dos pais que o produziu. Para cada par de descendentes, dois jogos de torneios de pais contra filhos são possíveis. Deterministic Crowding determina forças para os elementos mais semelhantes competirem.

Dois métodos de crowding semelhantes em operação e comportamento para deterministic crowding foram propostos (Cedeno 1999). Ele utiliza crossover de fenótipo e operadores de mutação, além de sharing phenotypic; isto resulta em redução adicional de erro de substituição.


Referências


  • CEDENO W., VEMURI V. R. Analysis of speciation and niching in the multi-niche crowding GA. Theoretical Computer Science. 229 (1-2): pp. 177-197 Nov 6 1999. Web of Science, key word: crowding multimodal optimization em 13/09/2002.

  • Grueninger T., Wallace, D. Multi-modal optimization using genetic algorithms. Technical report. MIT CADlab.1996. (http://mit.edu/) keyword: genetic algorithm multimodal optimization (http://cadlab.mit.edu/publications/) em 09/09/2002.

  • Miller B.L.; Shaw M.J. Genetic algorithms with dynamic niche sharing for multimodal function optimization IEEE International Conference. Evolutionary Computation, 1996. pp. 786-791. Web of Science, keyword: crowding multimodal optimization em 13/09/2002.

  • Mahfound, S. W. “Niching Methods”, in Evolutionary Computation 2.– Advanced Algorithms and Operators, Back T., Foge, D. B., Hichatewicz Z. (orgs.). Inst. of Physics Publishing, Bristol and Philadelphia. cap 13. pp. 87 – 92. keyword: crowding multimodal optimization.

  • SHAZELY S., BARAKA H., ABDEL-WAHAB A., KAMAL H. Genetic algorithms in solving graph partitioning problem. Multiple Approaches to Intelligent Systems, Proceedings Lecture Notes in Artificial Intelligence. 1611: pp. 155-164 1999. Web of Science, keyword: crowding multimodal optimization em 13/09/2002.

  • Shazely S.; Baraka H.; Abdel-Wahab, A. Solving graph partitioning problem using genetic algorithms Circuits and Systems, 1998. Proceedings. 1998 Midwest Symposium on , 1999. pp. 302 –305. Web of Science keyword: crowding multimodal optimization em 13/09/2002.



    1. Evolução Cooperativa

Os problemas complexos, como os multimodais, podem ser tratados através da evolução cooperativa, podendo ser modelados com uma abordagem similar a um ecossistema, consistindo de duas ou mais espécies geneticamente isoladas. As espécies interagem entre si dentro de um modelo de domínio compartilhado e têm um relacionamento cooperativo.

As espécies são evoluídas em sua própria população. Para avaliar uma população são escolhidos representantes de cada espécie. Em alguns casos é necessária a escolha do melhor indivíduo de cada população para a representação, em outros casos, pode-se optar por estratégias alternativas.

O algoritmo para a implementação é iniciado criando um número fixo de populações. O valor do fitness de cada membro de cada espécie é então avaliado. Se uma solução satisfatória para o problema objetivo não é encontrada inicialmente, todas as espécies são evoluídas. Para cada espécie, o algoritmo consiste em selecionar indivíduos para reprodução baseados em seu fitness, avaliando os descendentes e substituindo indivíduos da população anterior com novos indivíduos.

A avaliação dos indivíduos não é isolada, eles são combinados primeiro em algum domínio dependente com um representante de cada uma das outras espécies. Caso a evolução pare, pode ser que existam poucas espécies no ecossistema, então uma nova espécie será criada e sua população aleatoriamente inicializada.

No algoritmo, a cada geração é feita uma cooperação entre as populações, onde é atribuído um valor de aptidão para a população que está sendo avaliada. A cada n gerações, se a população que está sendo avaliada possui um valor de aptidão muito baixo, essa população é descartada, e então criada uma nova população, a qual irá substituí-la nas próximas gerações.


Referências


  • Srinivas M.; Patnaik L.M. Adaptive probabilities of crossover and mutation in genetic algorithms Systems, Man and Cybernetics, IEEE Transactions April 1994. vol. 24 pp. 656-667. Web of Science, key word: genetic evolution multimodal optmization em 13/09/2002.

  • POTTER, M. A.; DE JONG, K. Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1),2000, pp.1-29. Web of Science, key word: genetic evolution multimodal optmization em 13/09/2002.

  • Pozo A. et. al. Computação Evolutiva. Universidade Federal do Paraná. Depto. de Informática. Apostila 61p. Google keyword: computação evolutiva, (http://www.inf.ufpr.br/~aurora/tutoriais/Ceapostila.pdf) em 09/09/2002.



    1. Abordagens Híbridas

Segundo Pozo et al., “os algoritmos genéticos tradicionais, apesar de robustos, não são os algoritmos de melhor comportamento em otimização para qualquer domínio. Na hibridização algum outro método de otimização é utilizado em conjunto com GA’s, por exemplo, Hill-Climbing, Busca Tabu, etc”.

Segundo Kurahashi e Terano (2000) podem-se utilizar um algoritmo genético utilizando-se de múltiplas listas Tabu, auxiliando o algoritmo a chegar na solução em problemas multimodais ou com mais de uma função objetivo a otimizar. O trabalho propõe um novo algoritmo para, diretamente, armazenar indivíduos dentro de múltiplas listas.

A dinâmica dos algoritmos baseia-se na idéia que ao final de cada geração, o melhor indivíduo será armazenado em ambas as listas. Quando se inicia a próxima geração e novos indivíduos são selecionados para a reprodução, as listas de restrições não deixam que indivíduos similares presentes nas mesmas sejam selecionados. Estas listas de restrições podem ser aplicadas para somente um dos indivíduos escolhidos para gerar os descendentes.

Alguns testes de otimizações de funções realizados por este algoritmo foram feitos, conclusões parciais mostram que com esta estratégia o algoritmo genético utilizando listas de restrições conseguiu abranger uma área maior do espaço de busca, em relação a um algoritmo genético puro.

Para evitar que a convergência das soluções a um único pico em uma função multimodal, eles definem uma medida de distância entre um indivíduo na lista tabu e um novo candidato. São empregadas três medidas de distância, entre elas à distância de Hamming, onde é calculada a diferença de bits entre dois genótipos.


Referências


  • KURAHASHI, S.; TERANO, T. A genetic algorithm with Tabu search for multimodal and multiobjective function optimization. In: Proceedings International Conference on Genetic Algorithms, 2000, pp.291-298. Web of Science, key word: genetic algorithm multimodal optmization em 13/09/2002.

  • Lopes F. M.; Pozo A.T.R Genetic algorithm restricted by tabu lists in data mining. Computer Science Society, 2001. SCCC '01. Proceedings. XXI International Conference of the Chilean , 2001. pp. 178-185. Web of Science, key word: genetic algorithm multimodal optmization em 13/09/2002.

  • Pozo A. et. al. Computação Evolutiva. Universidade Federal do Paraná. Depto. de Informática. Apostila 61p. Google keyword: computação evolutiva em 09/09/2002. (http://www.inf.ufpr.br/~aurora/tutoriais/Ceapostila.pdf)

  • PARK C., LEE H., BANG H., TAHK M. Modified Mendel operation for multimodal function optimization. In: Proceedings Evolutionary Computation, 2001. v. 2 , pp. 1388 -1392. key word: genetic algorithm multimodal optmization em 13/09/2002.



    1. modificações em algoritmos evolutivos aplicados em otimização multimodal

Um GA simples já mostrou sua capacidade em uma variedade de problemas de otimização unimodal. Já com um problema de otimização multimodal há dificuldades para o GA simples, porque depois de um certo número de gerações a convergência da população em uma direção conveniente. Um meio de fazer a otimização multimodal se baseia na expectativa, de que um GA simples, que corra várias vezes, convirja para diferentes soluções. Para otimização multimodal, os GA’s simples devem ser modificados para obter todas soluções.

Um GA simples com uma população só converge a uma única solução. No começo da otimização cada sub-população é iniciada aleatoriamente. Então a otimização começa com cada sub-população isoladamente. Para reduzir a probabilidade que duas ou mais sub-populações venham a convergir para a mesma solução, dois operadores diferentes são usados: troca e migração.

Segundo Logot (1995), a aproximação geral para robôs de transformação inversa pode ser tratada como um problema de multimodal. Uma função que calcula o erro entre dois Tool Center Points (TCP’s), é minimizada por um algoritmo genético avançado. Este algoritmo genético de população múltipla usa troca e operadores de migração para calcular todas as soluções de problemas de otimização multimodal.

O uso de robôs na produção industrial cresce a cada dia, devido ao alto custo para a automação de produção industrial com robôs, a aptidão de um certo robô é verificada com estudos de simulação. Para a simulação de robôs pode-se avaliar a transformação da cinemática inversa.

Um método para a transformação da cinemática inversa foi desenvolvido tendo como base um algoritmo genético para otimização multimodal. Um algoritmo genético (GA) simples é modificado por múltiplas populações, com troca entre estas populações e migração entre estas populações. Baseado numa função, que calcula o erro entre dois TCP’s, toda população converge de uma para todas soluções da transformação cinemática inversa.

Dentro do operador de troca os melhores indivíduos de todas as sub-populações são comparados um com o outro. Se os dois melhores indivíduos de duas sub-populações são semelhantes entre si, em uma destas duas sub-populações os melhores indivíduos são repostos por novos indivíduos gerados aleatoriamente.

Dentro do operador de migração os indivíduos de diferentes sub-populações migram para outra, os indivíduos são escolhidos para migração por dois critérios: - os indivíduos são aleatoriamente escolhidos para migração; - os indivíduos com alto fitness também são escolhidos.

Estes dois operadores descritos causam o efeito desejado, no qual as sub-populações convergem para diferentes direções.

De acordo com Ronald (1995), outras modificações podem ser feitas em algoritmos genéticos, tendo–se uma nova técnica, multiple-solution-technique (MST), que pode ser empregada para resoluções de problemas em contraposição a alguns métodos como niche e speciation, tentando vencer as limitações e restrições desses métodos.

Este algoritmo genético que segue esta técnica une os pontos do de um problema multimodal em um genótipo e utiliza uma função fitness baseado nas distâncias de entre soluções e o fitness individual de solução. A técnica é demonstrada em um problema de prova de TSP de multimodal, indicando a eficiência em encontrar dois máximos distantes em soluções de ótimo próximo. A técnica pode ser usada com uma generalização ou modelo steady-state GA, e não depende do uso explícito de crossover ou uma codificação binária. Portanto, a técnica pode ser de interesse em outros modelos computacionais de população-base e outros algoritmos genéticos.

Foi visto também por Ohkura e Ueda (1995), que um algoritmo genético estendido foi utilizado em uma função multimodal. O GA proposto inclui duas características, uma que introduz redundância na representação da fileira, e outra que divide a população em sub-populações apenas para a etapa de seleção e reprodução de cada geração. O mecanismo desenvolve um comportamento para encontrar hiperplanos enganosos e escapar deles usando grandes transições genéticas na população. A influência genética é evitada adotando-se a estratégia de elitismo em cada sub-população.


Referências


  • logt g. v., walter m. Computing Robot Using a Genetic Algorithm for Multimodal Optimization. Evolutionary Computation. IEEE 1995. pp. 312 – 317. keyword: multimodal optimization.

  • ohkura k., ueda k. A Genetic Algorithm with a Neutral Mutations for Massively Multimodal Function Optimization. Evolutionary Computation. IEEE 1995. pp. 361 – 366. keyword: multimodal optimization.

  • ronald s. Finding Multiple Solutions with an Evolutionary Algorithm. Evolutionary Computation. IEEE 1995. pp. 641 – 646. keyword: multimodal optimization.
    1. Otimização Multimodal e Estratégias Evolutivas

A resolução de problemas de otimização de funções multimodais nesta aplicação se baseia na evolução em ambiente paralelo distribuído. Nesta aplicação várias populações evoluem em processadores separados e em determinadas épocas se produz um intercâmbio entre elas, além disso, são utilizadas Estratégias Evolutivas (EE´s) em ambiente distribuído, onde cada indivíduo gerado é uma solução em potencial do problema. Os operadores evolutivos de recombinação e mutação são aplicados a cada indivíduo com o objetivo de se obter uma evolução consistente de melhora das soluções candidatas. Todo processo é repetido sucessivamente até alcançar uma solução aceitável ou atingir algum critério de parada.

Em termos computacionais, esse processo pode ser demorado, ainda mais quando são utilizadas funções multimodais. Outro ponto importante que deve ser destacado é que a utilização da computação paralela oferece um potencial de busca muito maior no espaço de soluções do problema, onde populações que evoluem mais rápido ajudam de tempos em tempos as populações mais lentas, abrindo caminho para percorrer uma infinidade de trajetórias, que dificilmente são visitadas por um processo seqüencial clássico.

O algoritmo CLONALG foi implementado com o objetivo de se obter uma seleção clonal e maturação de afinidade. Podendo pode ser aplicado na aprendizagem de máquina, reconhecimento de padrões, otimização multimodal e combinatorial e aproximação de funções (SILVA, 2001).

O algoritmo pode ser caracterizado como uma estratégia evolutiva, apresentando um alto grau de paralelismo, o seu controle da taxa de mutação permite uma busca inicial por características abrangentes, e progressivamente aborda detalhes em escalas inferiores, os indivíduos da população são analisados localmente e existe a utilização de heurísticas para obtenção de ótimos globais para problemas específicos.

O algoritmo CLONALG reproduz aqueles indivíduos com altas afinidades e seleciona seus clones maturados de maior afinidade. Esta estratégia sugere um algoritmo capaz de realizar uma busca local em torno de cada indivíduo da população.

Segundo Silva (2001) quando se compara os algoritmos, principalmente o CLONALG com o método de fitness sharing (GAsh), verifica-se que o CLONALG aplicado a problemas de otimização multimodal é bastante eficiente na determinação de múltiplas soluções, enquanto o GAsh possui algumas limitações.

O algoritmo CLONALG é capaz de gerar diversidade, permitindo a determinação de todos os ótimos da função mesmo quando uma população inicial pequena e com baixa (ou nenhuma) diversidade é empregada.


Referências


  • silva L. N. c. Engenharia Imunológica: Desenvolvimentos e Aplicação de Ferramentas Computacionais Inspiradas em Sistemas Imunológicos. Faculdade de Engenharia Elétrica e de Computação. UNICAMP. DCA. Tese de Doutorado. 286p. keyword: multimodal optimization evolutionary techniques.

  • cortes o. a. c., saavedra o. r., pereira r. s. Resolução de Problemas de Otimização Multimodal através de Estratégias Evolutivas Paralelas. Universidade de São Paulo. Inst. de Ciências Matemáticas e de Computação 6p. Google, keyword: multimodal optimization “evolutionary techniques” em 09/09/2002. (www2.ing.puc.cl/iee/revista/vol1no1/CONT.pdf).

Andréa Leda Ojima / Evandro Theodoro /




©livred.info 2017
enviar mensagem

    Página principal