ads:
LUÍS HENRIQUE MOEDINGER
ALGORITMOS EVOLUTIVOS E INTELIGÊNCIA
COLETIVA APLICADOS A PROBLEMAS DE
OTIMIZAÇÃO NÃO-LINEAR COM RESTRIÇÕES:
FUNDAMENTOS E ESTUDO COMPARATIVO
Curitiba, agosto de 2005.
Dissertação apresentada ao Programa de Pós-
Graduação em Engenharia de Produção e Sistemas
da Pontifícia Universidade Católica do Paraná como
requisito para obtenção do título de Mestre em
Engenharia de Produção e Sistemas.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
LUÍS HENRIQUE MOEDINGER
ALGORITMOS EVOLUTIVOS E INTELIGÊNCIA
COLETIVA APLICADOS A PROBLEMAS DE
OTIMIZAÇÃO NÃO-LINEAR COM RESTRIÇÕES:
FUNDAMENTOS E ESTUDO COMPARATIVO
Curitiba, agosto de 2005.
Dissertação apresentada ao Programa de Pós-
Graduação em Engenharia de Produção e Sistemas da
Universidade Católica do Paraná como requisito para
obtenção do título de Mestre em Engenharia de
Produção e Sistemas.
Área de Concentração: Automação e Controle de
Sistemas
Orientador: Prof. Dr. Leandro dos Santos Coelho
ads:
Agradecimentos
Agradeço a todos os que contribuíram para que este trabalho fosse possível,
incentivando e prestando suporte sempre que necessário. Agradeço em especial à minha
família, ao meu orientador e aos amigos que contribuíram neste trabalho.
Resumo
As técnicas de otimização bio-inspiradas têm estudado os comportamentos
encontrados na natureza, visando a concepção de heurísticas e métodos de otimização. O
desenvolvimento emergente de novas abordagens e aplicações de algoritmos evolutivos é
motivado principalmente devido à versatilidade destes algoritmos na resolução de
problemas de otimização não-linear, projeto em engenharia e métodos de aprendizado de
máquina. Este aspecto motivou a sua inclusão neste estudo, abrangendo otimização através
de algoritmos evolutivos em uma concepção híbrida de otimização denominada algoritmo
memético. Um algoritmo memético pode aliar as vantagens de uma busca global através de
algoritmos evolutivos associados à precisão de uma busca local, por exemplo, através da
utilização da técnica denominada simulated annealing. Os algoritmos genéticos são uma
metodologia eficiente de otimização baseada nos princípios da evolução natural de Darwin
e genética de Mendel. O algoritmo PBIL pertence a um conjunto denominado de algoritmos
de distribuição de estimativas. A última técnica de algoritmos evolutivos abordada é a
programação evolucionária que enfatiza a relação entre a geração de pais e a geração de
descendentes, ao invés de utilizar operadores genéticos. Em contra-partida, o simulated
annealing se caracteriza pela inspiração no resfriamento dos metais, que possuem a
tendência natural de se manterem em um estado com energia mínima para uma mesma
temperatura. Outra área de otimização que apresenta recente desenvolvimento e aplicação
são as técnicas de inteligência coletiva. As técnicas de inteligência coletiva abordadas,
neste trabalho, são: nuvem de partículas e colônia de bactérias. O método de otimização por
nuvem de partículas faz parte de uma categoria de inteligência coletiva para a resolução de
problemas de otimização global. A nuvem de partículas foi proposto inicialmente por
Eberhart e Kennedy como um simulador para o comportamento social, em 1995. A
otimização utilizando-se o método de colônia de bactérias simula o comportamento da
bactéria Escherichia Coli, que é a mesma presente em nossos intestinos. Através da
simulação do comportamento e busca por alimento desta bactéria obtém-se inspiração para
o desenvolvimento de um algoritmo de otimização. Baseando-se nestes métodos, este
trabalho objetiva o estudo de algumas abordagens de algoritmos evolutivos e inteligência
coletiva, realizando uma comparação entre elas e buscando melhorar seus desempenhos
quando aplicadas em problemas de teste conhecidos na literatura para otimização não-linear
com restrições.
Palavras-chave: algoritmos evolutivos, inteligência coletiva, otimização não-linear
com restrições.
Abstract
The nature is surrounded by examples of search and optimization. On several areas
of Biology, each creature tries to adapt itself to survive and evolve. Using this assumption,
the optimization techniques have been studying the pattern presents on the nature,
searching for heuristics and optimization methods. The increasing development of new
approaches and applications of the evolutionary algorithms is motivated, mainly, due to this
versatility on solving non-linear optimization problems, engineering projects and machine
learning methods. That is the reason which motivates its inclusion on this study,
considering optimization using evolutionary algorithms in a hybrid optimization concept
identified as memetic algorithm. A memetic algorithm might ally the advantages of a global
search, using the evolutionary algorithms, and the precision of the local search, this study
uses the simulated annealing to perform the local search. The genetic algorithm is an
efficient optimization methodology based on Darwin’s evolution theory and Mendel’s
genetic. The PBIL algorithm is a part of a group identified as estimation of distribution
algorithms. Finally the evolutionary programming focuses on parent and spring
generations, instead of the use of genetic operators. The simulated annealing is
characterized to be inspirited on metal cooling, which has the natural tendency of maintain
a minimal energy state at the same temperature. Another optimization method which
presents a recent improvement and applications is the collective intelligence. The
techniques shown on this study are: particle swarm optimization and bacterial foraging. The
particle swarm optimization is used on global optimization problems, and was proposed by
Eberhart and Kennedy in 1995 as a social behavior simulator. The bacterial foraging is
based on the behavior of the bacteria Escherichia Coli. The inspiration of an optimization
algorithm was the behavior and the search for food of these bacteria. Based on these
methods, this document intends to study these algorithms, collecting data to compare their
performance and trying to improve those results when applied to known non-linear test
cases with constraints.
Keywords: evolutionary algorithms, swarm intelligence, non-linear optimization
with constraint.
Lista de Acrônimos
AG – Algoritmo Genético
EDA – Algoritmos de distribuição de estimativas (Estimation of Distribution Algorithms)
FPGA – Field Programmable Gate Array
MPEG – Moving Picture Experts Group
PBIL – População baseada em aprendizado incremental (Population Based Incremental
Learning)
PSO – Otimização por nuvem de partículas (Particle Swarm Optimization)
SA – Simulated Annealing
Índice
Capítulo 1 - Introdução.......................................................................................................1
1.1. Motivação...........................................................................................................2
1.2. Objetivos.............................................................................................................4
1.3. Estado da arte......................................................................................................6
1.4. Organização da proposta...................................................................................10
Capítulo 2 - Fundamentos de algoritmos evolutivos e inteligência coletiva.......................11
2.1 Algoritmos evolutivos.......................................................................................11
2.1.1 Algoritmo genético....................................................................................12
2.1.1.1 Cromossomo e geração..............................................................................12
2.1.1.2 Função de fitness .......................................................................................13
2.1.1.3 Operador de mutação.................................................................................14
2.1.1.4 Operador de cruzamento (crossover)..........................................................15
2.1.1.5 Funcionamento do algoritmo genético.......................................................16
2.1.2 População baseada em aprendizado incremental (PBIL)............................18
2.1.3 Programação evolucionária........................................................................20
2.2 Inteligência coletiva..........................................................................................23
2.2.1 Nuvem de partículas (PSO)........................................................................24
2.2.2 Colônia de bactérias...................................................................................29
2.3 Métodos híbridos de otimização........................................................................31
2.3.1 Simulated annealing..................................................................................31
2.3.2 Algoritmos determinísticos combinados com algoritmos estocásticos........33
Capítulo 3 - Estudos de casos............................................................................................35
3.1 Projeto de um recipiente de pressão...................................................................35
3.2 Projeto de uma viga engastada...........................................................................37
3.3 Minimização do peso de uma mola de tensão/compressão.................................40
Capítulo 4 – Consideração sobre os resultados..................................................................42
Capítulo 5 – Discussão dos resultados...............................................................................46
5.1 Projeto de um vaso de pressão.................................................................................48
5.2 Projeto de uma viga engastada................................................................................56
5.3 Minimização do peso de uma mola de tensão/compressão.......................................64
Capítulo 6 – Conclusão e pesquisa futura..........................................................................72
Referências bibliográficas.................................................................................................74
Lista de Figuras
Figura 2.1 Exemplo de mutação ocorrida num cromossomo binário..............................................15
Figura 2.2 Exemplo da operação de crossover. .............................................................................16
Figura 2.3 Funcionamento de um algoritmo genético básico.........................................................18
Figura 3.1 Projeto de um recipiente de pressão.............................................................................35
Figura 3.2 Projeto de uma viga engastada.....................................................................................37
Figura 3.3 Mola de tensão e compressão.......................................................................................40
Figura 4.1 Espaço de busca restrito aos limites (x
1
-1)
2
- x
2
< 0 e x
2
- sen(3x
1
) - 0,5 < 0....................43
Figura 4.2 Espaço de busca abstrato com algumas regiões válidas....................................................43
Figura 5.1 Convergência do algoritmo genético aplicado ao projeto do vaso de pressão..............50
Figura 5.2 Convergência do PBIL aplicado ao projeto do vaso de pressão....................................51
Figura 5.3 Convergência da programação evolucionária aplicado ao projeto do vaso de pressão..52
Figura 5.4 Convergência da nuvem partículas aplicado ao projeto do vaso de pressão..................53
Figura 5.5 Convergência da colônia de bactérias aplicado ao projeto do vaso de pressão..............53
Figura 5.6 Convergência do algoritmo genético aplicado ao projeto da viga engastada.................58
Figura 5.7 Convergência do PBIL aplicado ao projeto da viga engastada.....................................59
Figura 5.8 Convergência da programação evolucionária aplicado ao projeto da viga engastada.....60
Figura 5.9 Convergência da nuvem de partículas aplicado ao projeto da viga engastada...............61
Figura 5.10 Convergência da colônia de bactérias aplicado ao projeto da viga engastada.............62
Figura 5.11 Convergência do algoritmo genético aplicado a minimização da massa da mola.........66
Figura 5.12 Convergência do PBIL aplicado a minimização da massa da mola.............................67
Figura 5.13 Convergência da programação evolucionária aplicado a minimização da mola...........67
Figura 5.14 Convergência da nuvem de partículas aplicado a minimização da massa da mola.......68
Figura 5.15 Convergência da colônia de bactérias aplicado minimização da massa da mola..........69
Lista de Tabelas
Tabela 2.1 Algoritmo PBIL..........................................................................................................20
Tabela 2.2 Algoritmo de programação evolucionária....................................................................23
Tabela 2.3 Modelo de algoritmo de nuvem de partículas...............................................................27
Tabela 2.4 Algoritmo de colônia de bactérias...............................................................................31
Tabela 2.5 Algoritmo de simulated annealing...............................................................................33
Tabela 3.1 Comparação de alguns resultados da literatura do problema do recipiente de pressão...36
Tabela 3.2 Comparação de alguns resultados da literatura para o projeto de um viga engastada.....39
Tabela 3.3 Alguns dos resultados para minimização do peso de uma mola de tensão/compressão..41
Tabela 5.1 Melhores resultados encontrados – vaso de pressão.....................................................48
Tabela 5.2 Comparativo entre os algoritmos para o problema do vaso de pressão..........................55
Tabela 5.3 Melhores resultados encontrados dos 30 experimentos – viga engastada......................56
Tabela 5.4 Comparativo entre os algoritmos para o problema de projeto de uma viga engastada...63
Tabela 5.5 Melhores resultados encontrados dos 30 experimentos – mola tensão / compressão.....64
Tabela 5.6 Comparativo entre os algoritmos para o problema de minimização da massa da mola..70
Tabela 5.7 Comparação de desempenho entre os algoritmos e os estudos de caso.........................71
1
Capítulo 1 - Introdução
A abordagem tradicional da produção de software, para a resolução de determinados
problemas, não pode, em geral, ser aplicada facilmente em áreas tais como: reconhecimento
de voz, sistema de visão computacional, robótica, controle avançado, entre outras. Estas
áreas requerem técnicas avançadas, a exemplo das metodologias da inteligência
computacional que abrange redes neurais artificiais, sistemas nebulosos, computação
evolutiva e inteligência coletiva.
A inteligência computacional difere da programação tradicional devido ao fato de
possuir métodos bio-inspirados para lidar com imprecisão, incertezas, verdade parcial ou
mesmo aproximações. É importante ressaltar é que a inteligência computacional não é uma
mistura de algoritmos, ao contrário é uma parceria de forma a ter cada membro
contribuindo em uma metodologia distinta e com diferentes potencialidades e limitações.
Sobre a computação evolutiva ou evolucionária, deve-se mencionar que esta associa
o poder da seleção natural para tornar computadores em ferramentas de projeto e resolução
de problemas complexos de otimização.
Existem três mecanismos que regem a evolução, estes são: a reprodução, a mutação
e o princípio de Darwin da sobrevivência do mais apto. Como na natureza, a computação
evolucionária segue o princípio de que a reprodução progressiva melhora o indivíduo com
o passar das gerações.
Na maioria das abordagens de algoritmos da computação evolucionária, a população
é iniciada, de forma aleatória com distribuição uniforme, e sues indivíduos (soluções) são
submetidos a uma análise de qualidade através do cálculo de uma função objetivo (fitness).
Esta função objetivo analisa e re-alimenta o sistema medindo quão bom é o resultado de
cada indivíduo da população. Os melhores indivíduos têm maior possibilidade de repassar
as suas características para a próxima geração. As regras de governam como os
descendentes são gerados a partir da geração pai estão codificadas nos operadores genéticos
2
de: reprodução-seleção, mutação e cruzamento. A escolha e/ou presença (ou não) destes
operadores é o que, basicamente, diferencia uma técnica da outra.
Em relação a outra área da inteligência computacional, à inteligência coletiva, pode-
se observar que existe uma tendência dos sistemas computacionais emergentes a se
comportarem de forma distribuída, composta por agentes ou entidades autônomas sendo
executadas em ambientes dinâmicos. Sendo assim, é observado uma tendência de
comportamento social, criando um comportamento com inspiração em um comportamento
de descoberta, negociação e cooperação. Os programas computacionais de processamento
distribuído têm um comportamento similar, ou seja, executando seus próprios processos,
interagindo com outras entidades quando necessário, mas cada elemento tem a sua
autonomia e um comportamento global é percebido através das suas interações, de forma
análoga ao comportamento social observado na natureza. Neste estudo objetiva-se analisar
alguns algoritmos que pertencem a área da inteligência coletiva. Estes algoritmos possuem
um comportamento social, e também cognitivos, sendo aplicados a de otimização de
funções, que serão posteriormente comparados aos algoritmos de computação evolutiva.
1.1. Motivação
O rápido desenvolvimento das técnicas evolutivas de otimização e a sua facilidade
de aplicação em projetos complexos são fatores que atraem à sua utilização. Neste
contexto, a análise, projeto e estudos comparativos entre algoritmos de otimização são
tópicos importantes a serem estudados.
O estudo comparativo é motivado devido fato de que as tarefas de otimização não-
linear com restrições envolvem, geralmente, a determinação de diversos coeficientes
simultaneamente em um espaço de busca multimodal, não sendo, muitas vezes, apropriado
à utilização de técnicas tradicionais de otimização (Michalewicz e Schoenauer, 1996).
Além disso, a utilização de técnicas de otimização baseadas em gradiente pode, facilmente,
se restringir a valores de mínimos locais e não globais em problemas multimodais.
3
Através da aplicação do princípio de Darwin da “sobrevivência do mais apto”
aplicado à seleção natural e a genética, os algoritmos evolutivos se mostram úteis e
eficientes na procura de espaços irregulares e/ou complexos, contudo estes algoritmos
apresentam alta complexidade computacional. Entre os algoritmos evolutivos existentes,
serão abordados neste trabalho o algoritmo genético, o algoritmo de população baseado em
aprendizado incremental (PBIL) e a programação evolucionária. A utilização de
modificações para estes algoritmos é vasta e possibilita a combinação com técnicas de
busca local. Neste trabalho, o algoritmo de busca local escolhido foi o simulated annealing
que, combinado com algoritmo evolutivo pertence a um grupo de algoritmos denominados
algoritmos meméticos ou sistemas híbridos de otimização.
Os algoritmos meméticos por suas vez buscam trazer a combinação do melhor de
duas (ou mais) concepções de otimização, ou seja, a eficiência de busca global dos
algoritmos evolutivos e a precisão das técnicas de busca local.
Outro ramo de pesquisa que também é amplamente utilizado são os algoritmos de
inteligência coletiva. Neste caso são abordadas duas técnicas: otimização por nuvem de
partículas e otimização por colônia de bactérias.
Os comportamentos de cardumes de peixes e enxames de abelhas deram origem à
técnica de nuvem de partículas. Baseado no movimento sem colisões entre cada indivíduo
esta técnica realiza tanto buscas globais, quanto locais, baseado em parâmetros de projeto.
A bactéria Escherichia Coli está presente nos nossos intestinos e tem um
mecanismo comum à praticamente todo os seres na busca por alimento. Através desta
análise pode-se estabelecer a teoria de busca pelo alimento pode, e ser analisada como um
procedimento de otimização.
Esta diversidade de técnicas disponíveis para otimizar problemas não-lineares
sujeitos à restrições traz a tona uma pergunta: Qual destas é a melhor? Existem diversas
análises que apontam para uma impossibilidade de se determinar qual heurística é a melhor,
entretanto é possível determinar quais as abordagens mais indicadas para um dado tipo de
problema.
A busca por métodos estocásticos eficientes motivam o enfoque desta dissertação.
Desta forma é realizada uma comparação entre os algoritmos evolutivos e de inteligência
4
coletiva mencionando-se suas características e potencialidades. Após a análise e
fundamentação de cada técnica, são aplicados problemas-teste, para analisar e comparar os
resultados obtidos entre as soluções apresentadas neste trabalho e presentes na literatura.
1.2. Objetivos
Considerando-se a relevância das técnicas citadas e as suas inúmeras aplicações,
pode-se submetê-las a problemas de difícil solução. Desta forma os problemas a qual os
algoritmos são avaliados nesta dissertação possuem características não-lineares e possuem
restrições.
Com base neste estudo e comparação dos algoritmos, busca-se contribuir com o
aprimoramento destas técnicas, e através da hibridização entre os algoritmos espera-se
encontrar um resultado ótimo (ou próximo a este). Esta análise e comprovação são
realizadas através da aplicação das técnicas propostas a problemas-teste (benchmarks).
Os problemas avalidos são conhecidos na literatura e servem de base para
comparação de resultados, desta forma, ao tentar melhorar um resultado já existente,
acredita-se estar contribuindo para o desenvolvimento das técnicas de otimização da
inteligência computacional hoje utilizadas.
Para esta análise são ajustados os parâmetros de configuração dos algoritmos. Cada
algoritmo possui uma quantidade variável de parâmetros. Estes parâmetros têm influência
direta no resultado da otimização. Os algoritmos genéticos, por exemplo, possuem taxas de
mutação que se mal ajustadas podem tornar a busca aleatória. O algoritmo de nuvem de
partículas possui, entre outros fatores, um parâmetro de projeto denominado fator de
inércia, este fator influencia diretamente no comportamento do algoritmo.
A utilização de heurísticas de algoritmos evolutivos e de inteligência coletiva está
cercada de diversas potencialidades. Sua aplicação é útil em diversos tipos de problemas
para o fornecimento de suporte à tomada de decisão. Algumas áreas onde a utilização
destes algoritmos é empregada são em:
5
• projetos em Engenharia;
• agendamento de recursos e cronogramas;
• geração de layout de estruturas;
• identificação de sistemas e modelagem de curvas de resposta;
• otimização de carregamentos e embalagens;
• minimização de utilização de materiais;
• resolução de problemas de roteamento de redes de tubos, energia, circuitos
impressos etc.
O sucesso da utilização das técnicas baseadas em transições aleatórias se torna claro
à medida que a sua utilização tem se expandido através de diversas áreas de aplicação,
trazendo benefícios, economia e oferecendo uma melhor compreensão dos problemas a que
são aplicados.
A busca pelo resultado promissor ou ótimo traz à tona uma discussão sobre qual
seria a melhor técnica de otimização. O teorema do “no free lunch” tem sido de impacto no
campo de pesquisa de otimização. Basicamente este teorema diz que nenhum algoritmo é
melhor que outro quando a comparação é realizada a todas as funções (Christensen e
Oppacher, 2001). Uma vez este teorema provado (Wolpert e Macready, 1995) e após toda a
análise dos algoritmos, ajuste de parâmetros, variáveis de projeto e aplicação em
problemas-teste, espera-se além de obter uma sólida comparação entre as técnicas e
melhorar os resultados existentes atualmente para estes problemas, fugir da busca da
“melhor heurística de todos os tempos”, pois, como já dito, é aceito a não existência da
“melhor” heurística que seja superior a todas as outras aplicadas a todos os problemas. Na
tentativa de responder a estas questões esta dissertação enfatiza dois campos da inteligência
computacional: algoritmos evolutivos e inteligência coletiva.
6
1.3. Estado da arte
O uso de algoritmos evolutivos para a resolução de problemas tem abrangido
diversas áreas de conhecimentos, entre as quais:
• programação embarcada em Field Programmable Gate Array (FPGA): através
deste recurso os algoritmos evolutivos são associados a equipamentos de
hardware, possibilitando a geração de hardware evolutivo;
• otimização evolutiva com múltiplos objetivos: otimização de sistemas complexos
que apresentam objetivos conflitantes (teoria de conjuntos de Pareto), ou seja, ao
alterar um parâmetro que melhora o desempenho de uma certa variável, o
desempenho de outra variável é piorado. Neste caso os algoritmos evolutivos se
mostram eficientes na busca global;
• problemas de otimização complexos e/ou combinatórios: problemas com muitas
variáveis e espaços de soluções de dimensões elevadas. Ex: problema do caixeiro
viajante, atribuição quadrática, gerenciamento de carteiras de fundos de
investimento;
• utilização em sistemas de visão computacional: na robótica móvel, os algoritmos
evolutivos têm se mostrado como uma ferramenta útil ao traçado de trajetórias,
auxiliando o sistema de tomada de decisão sobre a direção a ser seguida;
• projeto e sintonia de controladores: os algoritmos evolutivos são utilizados com
freqüência para projetar e modelar controladores adaptativos (Moedinger e
Coelho, 2003);
• ciências biológicas: modelagem de processos biológicos para o entendimento do
comportamento de estruturas genéticas.
Martin (2002) implementou em um chip de lógica programável, que consiste de um
sistema completo que utiliza algoritmos genéticos capazes de resolver problemas em um
7
menor espaço de tempo que sistemas serias devido à avaliação paralela do fitness. Este
programa utilizou uma linguagem de alto nível para ser compilada, o Handel-C.
Coelho e Moedinger (2002, 2003) utilizaram os algoritmos evolutivos para projetar
controladores adaptativos aplicados a sistemas não lineares.
Os algoritmos de cluster são associados aos algoritmos evolutivos para a
configuração, em tempo de execução, de alguns parâmetros, como por exemplo, a taxa de
mutação (Streichert et al., 2003), desta forma o resultado de convergência do algoritmo é
influenciado diretamente pela escolha do algoritmo de cluster.
Deb e Goyal (1998) utilizaram um algoritmo flexível, que foi capaz de otimizar
problemas utilizando três codificações diferentes de forma simultânea. Desta forma foi
possível projetar sistemas de engrenagens obtendo-se o resultado ótimo e com excelente
desempenho, pois neste estudo os soluções que não possuíam representações físicas eram
penalizadas e descartadas, e o algoritmo pode convergir com maior rapidez.
Em 2000, Coello propôs a utilização de uma estratégia co-evolutiva auto-adaptativa
para o tratamento de penalidades, desta forma o algoritmo genético possui uma segunda
otimização responsável pela indicação da penalidade a ser utilizada em uma determinada
circunstância. Neste estudo, após comparar diversos algoritmos, sobre as técnicas de
penalidades adotadas, foi proposta a estratégia da co-evolucão, que se mostrou
extremamente eficiente quanto a convergência e obtenção de um resultado melhor que os
demais. Entretanto a execução de dois algoritmos simultaneamente, (um para resolução do
problema e outro para o tratamento de restrições) tornou o seu custo computacional muito
elevado, ficando pendente a proposição de uma solução para este problema, possivelmente
utilizando-se uma arquitetura paralela de programação.
Coello e Cortés (2004) propuseram um modelo híbrido de otimização utilizando
algoritmos genéticos e o algoritmo de sistema imunológico artificial. Neste modelo foram
considerados problemas com restrições, onde foram discutidas as técnicas de tratamento de
penalidades estáticas, dinâmicas, annealing, adaptativas e fatal. Nesta publicação, o
objetivo principal foi o estudo de uma forma alternativa do tratamento de restrições
utilizados em algoritmos genéticos para a busca global.
8
O algoritmo padrão de retropropagação do erro (back-propagation) é um dos
métodos mais conhecidos para o treinamento de redes neurais artificiais. No entanto, este
algoritmo apresenta diversos problemas, tais como sensibilidade às condições iniciais e
baixa velocidade de convergência. Em Radi e Poli (1997) foi descrito como se utilizar à
programação genética para criar um novo método de aprendizado supervisionado para as
redes neurais artificiais, capaz de superar alguns destes problemas. Também está relatado a
comparação entre os dois métodos de treinamento, ficando claro que a alternativa proposta
é mais rápida e estável.
A otimização de problemas complexos reais pode ser beneficiada através de um
ajuste preciso dos parâmetros do algoritmo. Uma metodologia de ajuste de forma efetiva e
eficiente é proposta por Bartz-Beielstein e Markon (2004). Esta abordagem combina
métodos de modelagem estatística, análise e modelagem computacional através de
regressão. Também pode ser aplicado para analisar a influência de diferentes operadores ou
para comparar o desempenho de diferentes algoritmos.
Uma tarefa necessária para robôs móveis é a capacidade de tomada de decisão em
tempo real baseada em sensores de visão. O aprendizado em um ambiente
multidimensional, cria um problema considerável para a maioria dos algoritmos de
aprendizado, especialmente aqueles que sejam baseados em redes neurais. Em Lange e
Riedmiller (2004) foi investigada a utilização de técnicas evolutivas combinadas a sistemas
supervisionados de aprendizado de redes feedfoward para construir a melhorar
automaticamente camadas de pré-processamento, reduzindo a complexidade de
aprendizado do problema inicial. Desta forma o algoritmo proposto, seleciona e configura
automaticamente apenas os melhores parâmetros a serem considerados em aprendizado
supervisionado.
A análise de cronograma é um problema bastante conhecido de otimização
combinatória. Um algoritmo híbrido para este tipo de análise foi apresentado por Merlot et
al. (2002). Este algoritmo consiste em três fases: uma fase de programação das restrições
para desenvolver uma solução inicial, uma fase onde o algoritmo simulated annealing é
aplicado para melhorar a qualidade da solução e finalmente, a utilização de um algoritmo
de subida de encosta para realizar melhorias adicionais.
9
De forma análoga aos algoritmos evolutivos, as técnicas de inteligência coletiva
também possuem uma vasta gama de aplicações, entre as quais são destacadas as seguintes:
• capacidade de processamento paralelo: a utilização a síntese do algoritmo de
nuvem de partículas apresentada facilidades para distribuir o processamento
de forma paralela;
• otimização em um espaço com ruídos: as técnicas de inteligência coletiva
podem ser eficientes na busca de soluções ótimas em um espaço de busca
ruidoso.
Na teoria de jogos existe uma estratégia denominada Min-Max. Este algoritmo tem
sido adotado também para a otimização com múltiplos objetivos de forma eficiente. Rowe e
Maciejowski (2003) utilizaram uma configuração híbrida do algoritmo de nuvem de
partículas em conjunto com o Min-Max. Neste estudo, a função de fitness foi derivada a
partir do algoritmo Min-Max. Uma vantagem observada nesta análise é a não necessidade
de utilização de um outro algoritmo de cluster.
O registro de imagens médicas através da análise de imagens bi-dimensionais e tri-
dimensionais têm se tornado cada vez mais importante na elaboração de diagnósticos,
tratamento de doenças, estudos funcionais, terapias baseadas em computação e na pesquisa
biomédica. Os registros baseados em valores de intensidade freqüentemente necessitam de
alguma similaridade entre as imagens. As técnicas de otimização local costumam não ser
eficientes devido às funções que regem estas métricas serem, geralmente, não convexas e
irregulares. Desta forma, uma nova abordagem é proposta (Wachowiak et al, 2004) através
da utilização do algoritmo de nuvem de partículas com o auxílio inicial do usuário. Neste
caso, o algoritmo torna-se eficiente para a correta identificação do diagnóstico.
Parsopoulos e Vrahatis (2002) estudaram o método de otimização por nuvem de
partículas de forma a analisar as interações entre os parâmetros do algoritmo e seus ajustes.
10
1.4. Organização da proposta
Esta dissertação está organizada da seguinte forma: No capítulo 2 são apresentados
os fundamentos de cada uma das técnicas que são empregadas nesta dissertação, bem como
a descrição do funcionamento de cada algoritmo e os parâmetros relativos a cada um. No
capítulo 3 são indicados os problemas que compõe o estudo de caso, trazendo alguns
resultados presente na literatura. O capítulo 4 indica as considerações utilizadas para a
análise dos resultados de forma a propiciar uma base comum para realizar a comparação
dos resultados entre si, o capítulo 5 apresenta os resultados obtidos em cada um dos
problemas-teste e a comparação destes resultados com os apresentados no capítulo 3 e o
capítulo 6 traz a conclusão desta dissertação e as pesquisas futuras que pretende-se iniciar.
11
Capítulo 2 - Fundamentos de algoritmos evolutivos e
inteligência coletiva
Este capítulo visa retratar as técnicas de otimização propostas neste estudo. Nele os
algoritmos serão apresentados e o seu funcionamento é explicado.
2.1 Algoritmos evolutivos
Inspirados pelos princípios da evolução natural, vários pesquisadores estudaram de
forma independente os sistemas evolutivos, mantendo o foco em problemas de otimização
em engenharia, que podem ser solucionados inspirados pela simulação por processos da
evolução natural. Vários algoritmos evolutivos foram propostos desde os anos 60, tais
como estratégia evolutiva, programação evolutiva, algoritmos genéticos e evolução
diferencial.
A computação evolutiva começou a receber uma atenção significativa na última
década, devido principalmente a falta de plataformas suficientemente robustas para atender
as necessidades de processamento. Recentemente, este panorama tem sido alterado e é
observado um crescimento constante nas aplicações destas técnicas, demonstrado
claramente a relevância cientifica e econômica desta técnica.
Entre os benefícios da computação evolutiva que justificam o investimento nesta
área pode-se citar o ganho de flexibilidade e adaptação da técnica e a possibilidade e
facilidade de combiná-la com técnicas complementares. Neste contexto, a computação
evolutiva pode ser compreendida como um conceito geral para resolução de problemas,
especialmente aqueles problemas de difícil solução algébrica, não-lineares e não-convexos.
A maior parte dos atuais tipos de implementação dos algoritmos evolutivos derivam
de três abordagens: algoritmos genéticos, programação evolucionária e estratégias
evolutivas. Os algoritmos genéticos foram propostos por Holland (1962). A programação
evolucionária, introduzida por Fogel (1962), foi originalmente proposta para como uma
tentativa de criar métodos inteligentes. Esta abordagem visava utilizar máquinas de estado
finito para prever eventos baseados em observações prévias. Mas novamente a técnica se
12
mostrou útil para a resolução de problemas de otimização. A estratégia evolutiva
desenvolvida por Rechenberg (1973) foi inicialmente proposta com o objetivo de
solucionar problemas de otimização discreta e continua.
Durante a década de 80, os avanços realizados permitiram a aplicação dos
algoritmos evolutivos para a solução de problemas de otimização de empresas comerciais e
na indústria. A partir deste ponto iniciou-se uma convergência sobre as pesquisas relativas
aos algoritmos evolutivos.
2.1.1 Algoritmo genético
Embora os algoritmos genéticos não sejam considerados algoritmos guiados
matematicamente, um valor ótimo é obtido através das gerações sem a utilização de uma
formulação matemática, como na utilização de métodos baseados na informação do
gradiente. O algoritmo genético é probabilístico, onde o valor ótimo obtido é oriundo dos
melhores elementos das gerações anteriores, nas quais os atributos de um indivíduo mais
apto tende a ser transferido para as gerações futuras. Outra potencialidade na utilização dos
algoritmos genéticos é o fato de que eles não utilizam derivadas nem integrais, isto diminui
o seu custo computacional se comparado à algoritmos de subida de encosta.
As diversas etapas de processamento associadas a um algoritmo genético estão
explicadas a seguir. Estas etapas são repetidas diversas vezes até a obtenção de um
resultado adequado ao problema ou ao atingir um critério de parada, que pode ser desde
tempo de execução até valores de convergência do algoritmo. Desta forma o funcionamento
dos algoritmos genéticos pode ser compreendido considerando-se os seguintes aspectos: a
representação do problema, o uso dos três operadores (seleção, crossover e mutação) e a
aplicação de uma função de fitness para avaliar cada membro da população.
2.1.1.1 Cromossomo e geração
Um dos principais componentes dos algoritmos genéticos são os cromossomos. Ele
é quem contém os valores que serão avaliados em relação a uma função de fitness e são
13
submetidos às operações de mutação, crossover e seleção. Os cromossomos podem ser
representados em qualquer uma das bases numéricas, para este projeto estuda-se a
utilização da base binária devido à facilidade de trabalho com esta base. A utilização de
outra base pode ser útil em problemas específicos, porém, a sua implementação se torna
complexa e se faz necessário uma adequação das demais funções do algoritmo. Devido à
escolha da base binária, cada bit da população é denominado gene.
O conjunto de cromossomos forma a população que será avaliada. Esta população é
submetida ao seguinte ciclo: É avaliada a função de fitness e verificado quão próximo cada
cromossomo está em relação a um ponto ótimo, em seguida são realizadas as operações de
reprodução, acasalamento, crossover e mutação, que serão descritas mais adiante. Esta é a
ordem que foi adotada para este projeto. Também para neste caso deve ser determinado o
número de cromossomos para compor a população, este número pode variar, porém com o
aumento da população, aumenta também o custo computacional para a avaliação de cada
geração.
Uma geração é o conjunto de cromossomos presentes em cada interação do sistema.
Cada ciclo citado, no parágrafo anterior, corresponde a uma geração. Quanto maior o
número de gerações, maior será o custo computacional para a execução do algoritmo
genético.
Após a análise de diversas gerações o comportamento esperado do algoritmo é o
início da convergência da solução. Muitas vezes este é o critério escolhido para determinar
o final da execução do algoritmo. Também deve-se considerar este ponto, ou seja, após a
análise de cada geração, como ponto de início para a utilização de um algoritmo de busca
local. Uma hibridização deste algoritmo é apresentada na seqüência deste capítulo.
2.1.1.2 Função de fitness
A função de fitness, geralmente vinculada a minimização (ou maximização) de uma
função objetivo, é utilizada para a determinação de quão bom é o resultado obtido. Cada
um dos cromossomos é submetido a esta função, quando todos os membros da população
14
forem avaliados pode-se comparar qual deles é o que possui o melhor resultado. Entre uma
geração e outra, a informação de qual o melhor membro da população é utilizado para
aumentar a probabilidade da geração seguinte possuir cromossomos parecidos com o
melhor cromossomo da população atual. Quando a população estiver na última geração que
se deseja avaliar, o membro da população que possuir o melhor fitness é a melhor resposta
do método de otimização projetado.
Para cada problema de otimização devemos escolher as variáveis a serem
otimizadas. Com estas variáveis será elaborada a função de fitness do problema, que serve
para realizar a análise de desempenho cada cromossomo (quando usada a codificação
binária). Como exemplo, ao assumir que cada caminho possível na resolução do problema
do caixeiro viajante é uma solução provável, o caminho que apresentar a menor distância é
considerado com o melhor fitness.
Devido ao algoritmo genético buscar melhores soluções através da alteração de sua
população, pode-se incorrer no encontro de uma solução que seja inválida. Esta solução
pode apresentar este resultado inválido devido aos mais diversos motivos, desde a não
existência do resultado fisicamente até a apresentação de um resultado fora do intervalo de
busca. Isto caracteriza uma restrição as possíveis soluções apresentadas para o problema.
Quando existirem restrições de respostas válidas ao problema, pode-se adotar diversos
posicionamentos, desde penalizar um resultado fora do esperado até descartá-lo
completamente. Esta análise é apresentada no capítulo 4, seção 4.1.
2.1.1.3 Operador de mutação
A operação de mutação é a responsável pela troca aleatória de cada gene do
cromossomo no algoritmo genético com representação binária (canônica). Esta alteração
aleatória pode evitar que o algoritmo genético fique restrito a um espaço de mínimo local,
porém se a probabilidade de mutação for elevada, o algoritmo poderá passar a se comportar
de forma aleatória, o que não é desejado na maioria das vezes. Goldberg (1989) sugere a
utilização do valor 0,05 (5%) para a variável P
m
(probabilidade de mutação). Desta forma a
15
mutação introduz novas informações na da população, permitindo que novos pontos sejam
testados, aumentado assim, a probabilidade de se encontrar o ótimo global. A seguir na
figura 2.1 é apresentado um exemplo de mutação em um cromossomo com codificação
binária:
Figura 2.1 Exemplo de mutação ocorrida num cromossomo binário.
2.1.1.4 Operador de cruzamento (crossover)
Analogamente ao que ocorre na natureza, a operação de crossover (representação
binária), ou recombinação (representação real ou de ponto flutuante), é a responsável pela
troca de genes entre cromossomos diferentes, através desta troca são gerados novos
membros da população. O ponto de corte é aleatório e a recombinação poderá ocorrer ou
não, a ocorrência do crossover está condicionada a P
c
(probabilidade de crossover).
Goldberg (1989) sugere a utilização de um valor superior a 0,60 (60%) de probabilidade de
cruzamento. Desta forma ocorre a troca material genético entre os indivíduos da população.
Dada a sua alta probabilidade de ocorrência, este é o operador responsável pela criação de
novos indivíduos. Desta recombinação resultam dois novos indivíduos descendentes dos
primeiros.
Um outro aspecto importante dos algoritmos genéticos diz respeito à substituição da
população antiga pela nova população. Esta substituição pode ser total ou parcial. No
último caso, apenas os piores indivíduos são substituídos, recebendo a denominação de
reprodução steady-state.
Uma ilustração deste processo pode ser observada na figura 2.2.
16
Figura 2.2 Exemplo da operação de crossover.
2.1.1.5 Funcionamento do algoritmo genético
Com a associação dos elementos descritos anteriormente, é obtido um algoritmo
genético. Através do princípio da seleção natural, que faz com que os melhores indivíduos
sobrevivam, obtém-se a evolução, que é iniciada com o material genético (cromossomo) de
dois outros cromossomos são recombinados durante a reprodução (operação de crossover),
em seguida ocorre a mutação, que causa uma alteração aleatória e esporádica nos genes de
um cromossomo. Para problemas de minimização, a mutação re-insere o material genético
perdido, isso propicia a busca de um ponto de mínimo global, fugindo dos mínimos locais.
O funcionamento dos algoritmos genéticos pode ser descrito da seguinte forma: O
algoritmo é iniciado com N indivíduos que são, geralmente, gerados aleatoriamente ou
através de algum processo heurístico. Como no caso do mundo biológico não há evolução
sem variedade, desta forma é importante que a população inicial cubra a maior área
possível do espaço de busca.
Depois de gerada a população os algoritmos genéticos precisam da informação da
função objetivo (função de fitness) para cada membro da população. A função objetivo
define, para cada membro da população, uma medida de quão bem adaptado ao ambiente
ele está, ou seja, quando maior o valor da função objetivo, maiores são as chances de
sobrevivência no ambiente e de reprodução do indivíduo, passando parte do seu material
genético para as gerações posteriores. A próxima fase é a seleção. Nesta etapa o algoritmo
genético simula a seleção natural, onde indivíduos com baixos valores de fitness tem uma
17
alta probabilidade de desaparecer enquanto indivíduos adequados tem uma grande chance
de sobreviver. Seguindo o processo natural tem-se o processo de recombinação, este
processo envolve dois indivíduos que emula o fenômeno de crossover, efetuando a troca de
material genético entre os cromossomos.
A última etapa para uma geração é a mutação, nesta operação, seleciona-se uma
posição em um cromossomo e se altera o valor do gene correspondente para um outro valor
permitido. Com isso se completa uma geração do algoritmo genético, na seqüência é
reiniciado o processo até que uma condição de parada seja satisfeita, esta condição pode ser
um número definido de gerações ou uma variância mínima entre os membros da população.
Graças a não utilização de gradientes ou derivadas, o algoritmo genético é pode ser
eficiente para a realização de buscas globais, embora o resultado obtido não seja
necessariamente o valor ótimo, tem-se um valor próximo deste.
O funcionamento do algoritmo também pode ser visualizado através do diagrama da
figura 2.3.
18
Figura 2.3 Funcionamento de um algoritmo genético básico.
2.1.2 População baseada em aprendizado incremental (PBIL)
Durante a década de 90, problemas complexos de otimização foram resolvidos com
sucesso pelos algoritmos genéticos. Mas a existência de alguns problemas específicos, onde
o desempenho destes algoritmos é deficiente, motivou a busca por novas técnicas de
otimização. Para superar estas dificuldades, alguns pesquisadores propuseram a utilização
de novos algoritmos denominados de algoritmos de distribuição de estimativas (EDA).
Os EDA são um exemplo de heurística baseada na população indivíduos, onde cada
indivíduo contém uma provável solução para o problema (González et al., 2000). Esta
19
população é evoluída através de varias gerações na busca de um resultado. A diferença
entre o EDA e os algoritmos genéticos é a substituição dos operadores de mutação e
crossover, por operadores de estimativas e amostragens aplicados a uma distribuição
probabilística para a produção da nova geração de possíveis soluções.
O algoritmo PBIL é considerado como um EDA (Baluja, 1994) e supõe que as suas
variáveis sejam independentes. De forma resumida tem-se que a cada passo do algoritmo
um vetor de probabilidades é mantido. Este vetor é amostrado λ vezes de forma a obter-se λ
novas soluções. As µ ≤ λ melhores soluções são selecionadas e utilizadas para modificar o
vetor de probabilidades.
Ao detalhar-se o funcionamento do algoritmo pode-se observar que ele é baseado na
idéia de substituir os indivíduos da população por um conjunto de soluções submetidas a
uma operação estatística. Se é suposta uma função de otimização definida em um espaço
binário Ω = {0,1}
L
com |Ω| = 2
L
= n e dada uma população, um conjunto estatístico
representado por um vetor de probabilidades P=(p
1
, ... , p
m
, ... , p
L
), onde p
m
representa a
probabilidade de se possuir o valor “1” na posição m.
A cada passo o vetor P é aplicado a população de forma a se obter λ novos
indivíduos. As µ melhores soluções, sendo µ ≤ λ, y
1
, y
2
, ... , y
µ
são selecionadas e serão
responsáveis por modificar o vetor de probabilidade P. A regra utilizada para atualizar o
vetor é:
∑
=
+
+−=
µ
λ
µ
αα
1
)(
:
)()1(
1
)1(
k
t
k
tt
ypp
(2.1)
onde P
(t)
é o vetor probabilidade no passo t, e α
∈
(0,1] é um parâmetro do algoritmo.
Desta forma o algoritmo PBIL pode ser descrito conforme a tabela 2.1.
20
Tabela 2.1 Algoritmo PBIL.
1: Obter o vetor de probabilidade inicial P
(0)
2: Enquanto não convergir ou número de iterações faça
3: Usando P
(t)
obtenha λ novos elementos y
1
(t)
, y
2
(t)
, ... , y
λ
(t)
4: Avalie e ordene y
1
(t)
, y
2
(t)
, ... , y
λ
(t)
5: Selecione os µ ≤ λ melhores indivíduos y
1: λ
(t)
, y
2: λ
(t)
, ... , y
µ:λ
(t)
6:
∑
=
+
+−=
µ
λ
µ
αα
1
)(
:
)()1(
1
)1(
k
t
k
tt
ypp
7: Fim Enquanto
8: Retorna resultado
2.1.3 Programação evolucionária
A programação evolucionária foi inicialmente proposta por Laurence Fogel em
1962, como uma ferramenta estocástica de otimização similar aos algoritmos genéticos,
entretanto enfatiza a relação entre a geração de pais e a geração de descendentes, ao invés
de utilizar operadores genéticos.
A programação evolucionária é um método de otimização, capaz de resolver
problemas onde a resolução analítica encontra dificuldade para solucionar o problema.
Como os algoritmos genéticos, existe a premissa da análise do fitness para a obtenção da
melhor solução.
O problema de otimização pode ser formulado de forma a minimizar uma função
objetivo. Desta forma o problema de minimização global pode ser formulado como um
par(S, ƒ) onde S
⊆
R
n
é o conjunto limitado em R
n
e ƒ: S à R é uma função de valores
reais n-dimensional. O problema é a determinação do ponto x
min
∈
S tal que ƒ(x
min
) é o
mínimo global de S. Mais especificamente, é necessário encontrar x
min
∈
S tal que:
21
ƒ:Sx
∈
∀
(x
mín
) ƒ
≤
(x)
(2.2)
onde ƒ não precisa ser contínua, mas precisa ler limitada.
Bäck e Schwefel (1993) demonstram que o algoritmo de programação evolucionária
com taxa de mutação adaptativa possui um melhor desempenho em relação ao algoritmo
com taxa de mutação constante. Deve-se enfatizar que a programação evolucionária não
utiliza nenhum operador de crossover como operador evolutivo.
Existem dois pontos relevantes que diferenciam os algoritmos genéticos da
programação evolucionária: primeiro a representação das soluções não são codificadas, no
caso dos algoritmos genéticos canônicos (representação binária ou genotípica) a análise é
realizada em cromossomos codificados, geralmente de forma binária. Na programação
evolutiva, a representação segue de acordo com o problema (representação fenotípica), por
exemplo, uma rede neural pode ser representada da mesma forma que é implementada. E
em segundo, o operador de mutação modifica a solução de acordo com uma distribuição
estatística, de forma a existir uma pequena variação entre gerações.
O algoritmo apresentado abaixo representa o algoritmo de programação
evolucionária com taxa de mutação adaptativa (Yao et al., 1999):
1. Gerar a população inicial com µ indivíduos e k = 1. Cada indivíduo é
escolhido como um par de vetores reais, (x
i
,
i
η ),
∀
i
∈
{1, ..., µ}, onde x
i
são as variáveis objetivos e
i
η são os desvios padrão para a mutação.
2. Avaliar o resultado do fitness para cada indivíduo (x
i
,
i
η ),
∀
i
∈
{1, ..., µ},
da população baseado no função objetivo ƒ(x
i
).
3. Cada elemento pai (x
i
,
i
η ), i = 1, ..., µ, cria um descendente ),(
''
ii
x η . Para
j = 1, ..., n. Tem-se que:
)1,0()()()(
'
jiii
Njjxjx η+=
(2.3)
))1,0()1,0(exp()()(
''
jii
NNjj ττηη +=
(2.4)
22
onde )(),(),(
'
jjxjx
iii
η e )(
'
j
i
η representam o j-ésimo componente do vetor
iii
xx η,,
'
e
'
i
η ,
respectivamente. N(0,1) indica a geração de um número aleatório de distribuição normal e
média zero e desvio padrão igual a 1; N
j
(0,1) indica a geração de um número aleatório com
distribuição normal para cada j. os fatores
τ
e
'
τ são geralmente designados como
1
)2(
−
n e
1
)2(
−
n .
4. Calcular o fitness de cada membro da nova geração ),(
''
ii
x η ,
∀
i
∈
{1, ..., µ}.
5. Conduzir uma comparação de cada par entre a geração pai (x
i
,
i
η ) e a
geração descendente ),(
''
ii
x η ,
∀
i
∈
{1, ..., µ}. Para cada elemento, q
oponentes são escolhidos de forma aleatória entre todos os elementos da
geração pai e geração descendente. Para cada comparação, se o fitness
individual é maior que o do oponente, ele recebe uma “vitória”.
6. Selecionar os µ indivíduos de (x
i
,
i
η ) e ),(
''
ii
x η ,
∀
i
∈
{1, ..., µ}, que
possuem maior número de “vitórias” para formarem a próxima geração pai.
7. Suspender o algoritmo se um critério de parada for alcançado, caso contrário
k = k+1 e retorna-se ao passo 3.
Pode-se resumir o algoritmo de programação evolucionária a uma seqüência simples
de passos, conforme mostrado na tabela 2.2 na seqüência.
23
Tabela 2.2 Algoritmo de programação evolucionária.
1: Gerar a população inicial
2: Enquanto não atingir o critério de parada faça
3: Avaliar o fitness de cada elemento da população
4: Cada elemento pai gera um descendente utilizando as equações (2.3) e (2.4)
5: Avaliar o fitness de cada elemento da nova geração
6: Cada elemento da geração pai é comparado algumas vezes com alguns elementos da
iiiinova população, o elemento com o melhor fitness, a cada comparação, acumula uma
iiiivitória
7: Selecionar os elementos com o maior número de vitórias para compor a nova geração
8: Fim Enquanto
9: Retorna resultado
2.2 Inteligência coletiva
Muitas pesquisas têm se inspirado nos processos do mundo biológico para o
desenvolvimento de métodos de otimização. Estas técnicas têm se mostrado mais eficiente
do que a heurística clássica ou baseada em métodos de otimização baseados em gradiente,
especialmente quando aplicadas a problemas de otimização multi-modal, não-
diferenciáveis ou a funções descontinuas, que necessitam de comparação entre indivíduos
para a obtenção da primeira solução aceitável.
A inteligência coletiva é parte de um sistema onde o comportamento coletivo, e não
sofisticado, de agentes interagindo localmente dentro de seu ambiente, propiciam o
aparecimento de um modelo funcional e coerente. A inteligência coletiva provê uma base
de forma a possibilitar a exploração coletiva ou distribuída, para a resolução de problemas
sem um controle centralizado ou a necessidade de um modelo global.
.
24
2.2.1 Nuvem de partículas (PSO)
O método de otimização por nuvem de partículas (particle swarm optimization) faz
parte de uma grande categoria de inteligência coletiva para a resolução de problemas de
otimização global. Este método foi proposto inicialmente por Eberhart e Kennedy (1995)
como um simulador para o comportamento social.
O algoritmo clássico não requer nenhuma informação sobre o gradiente da função
objetivo avaliada, requer apenas o valor da função objetivo, desta forma, utiliza apenas
operações aritméticas simples. Isto o torna um método eficiente para problemas de busca
global e em alguns casos não é afetado por algumas das principais dificuldades encontradas
por métodos de computação evolutiva.
Historicamente as regras implícitas ao comportamento de um conjunto de aves ou
peixes, e que possibilitam o seu movimento sincronizado sem colisões, foi estudado por
vários pesquisadores (Heppner e Grenander, 1990; Reynolds, 1987). Nas simulações, o
movimento do conjunto é o resultado da atuação de cada indivíduo para manter a distância
ótima entre seus vizinhos (Eberhart et al., 1996).
O comportamento social entre os animais, e em alguns casos dos humanos, é
governado por regras similares. Entretanto, o comportamento social humano é mais
complexo que apenas o conjunto de peixes ou aves. Além do movimento físico, seres
humanos possuem opinião, movimento, tendências, num mesmo ambiente. Embora duas
pessoas não possam ocupar o mesmo lugar no espaço no ambiente físico ao mesmo tempo,
elas podem ter as mesmas opiniões, ocupando a mesma posição no ambiente, sem
entretanto se chocarem. Existe um consenso, e inúmeros exemplos vindos da natureza, que
o compartilhamento da informação entre os indivíduos de uma população podem prover
uma vantagem evolutiva, e está é a idéia central na qual se baseia o desenvolvimento do
algoritmo de nuvem de partículas (Eberhart et al., 1996). Neste algoritmo o termo partícula
é associado ao indivíduo, enquanto o termo nuvem (enxame ou bando) é empregado para
designar a população.
Efetuando a análise do algoritmo tem-se que o precursor do PSO era um simulador
de comportamento social, que era utilizado para visualizar o movimento de aves. Várias
25
versões do modelo de simulador foram desenvolvidas e bem como conceitos foram
incorporados. Quando se percebeu que a simulação poderia ser utilizada como uma
ferramenta de otimização, foram omitidos alguns destes parâmetros, resultando na primeira
versão do algoritmo PSO (Eberhart et al., 1996).
PSO é similar às técnicas de computação evolutiva devido ao conjunto de soluções
em potencial para o problema em questão ser utilizado para testar o espaço de busca.
Entretanto, no PSO, cada indivíduo da população possui uma velocidade variável de acordo
com a movimentação pelo espaço de busca. Além disso, cada indivíduo possui memória,
armazenando a melhor posição já visitada. Assim, o movimento se dá em direção a melhor
posição já visitada pelo conjunto, levando-se em consideração a melhor posição visitada
pelo indivíduo anteriormente (Lechuga, 2002).
Supondo que o espaço de busca seja D-dimensional, então a i-ésima partícula da
nuvem pode ser representada por um vetor D-dimensional, X
i
= (x
i1
, x
i2
, ... , x
iD
)
T
. A
velocidade desta partícula pode ser representada por outro vetor D-dimensional V
i
=(v
i1
, v
i2
,
... , v
iD
)
T
. A melhor posição previamente visitada da i-ésima partícula é definida como P
i
=
(p
i1
, p
i2
, ... , p
iD
)
T
. Definindo-se b como o índice da melhor partícula, então a nuvem pode
ser manipulado de acordo com as seguintes equações:
(2.5)
(2.6)
onde
t
∆
= 1, d = 1,2, ... , D; i = 1, 2, ... , N, sendo N o tamanho da nuvem; c é uma
constante positiva, denominada constante de aceleração; r
1
e r
2
são números aleatórios
uniformemente distribuídos no intervalo [0,1]; e n = 1, 2, ... , determina a iteração atual.
As equações (2.5) e (2.6) definem a versão inicial do algoritmo PSO. Pode-se
observar que não existe um mecanismo de controle da velocidade de cada partícula, desta
forma se faz necessário a imposição de um valor máximo V
máx
. Se a velocidade exceder o
)()(
21
1 n
id
n
bd
nn
id
n
id
nn
id
n
id
xpcrxpcrvv −+−+=
+
tvxx
n
id
n
id
n
id
∆+=
++
.
11
26
limite estipulado por V
máx
, automaticamente V
máx
é assumido como o valor da velocidade.
Este parâmetro se mostrou imprescindível para se obter um desempenho satisfatório do
algoritmo, pois, para valores elevados da velocidade as partículas se deslocam através de
soluções boas, sem no entanto as considerar e, para valores pequenos de velocidade, ocorre
uma busca insuficiente do espaço a ser explorado. A falta de um mecanismo de controle
para a velocidade resulta em uma baixa eficiência do algoritmo se comparar as demais
técnicas de computação evolutiva (Angeline, 1998). Especificamente, o algoritmo de
nuvem de partículas localiza o mínimo global mais facilmente, porém, após isto, não
consegue ajustar a velocidade para realizar uma pesquisa mais detalhada.
Para a resolução deste problema, foi incorporado um fator de ponderação em
relação à velocidade anterior da partícula. Desta forma, as atuais versões modificaram as
equações (2.1) e (2.2) para as seguintes (Eberhart e Shi, 1998):
(2.7)
(2.8)
onde
t
∆
= 1;
w
é um fator de inércia; c
1
e c
2
são constantes positivas, denominadas
parâmetro cognitivo e social, respectivamente;
O algoritmo de nuvem de partículas contempla os cinco princípios básicos da
inteligência coletiva definidas por (Eberhart et al., 1996; Millonas, 1994):
• proximidade: a nuvem precisa considerar um espaço simples e computar tempo;
• qualidade: a nuvem precisa responder aos fatores qualitativos do ambiente;
• resposta diversificada: a nuvem não deve comprometer-se explorando caminhos
muito específicos;
• estabilidade: a nuvem não deve alterar seu comportamento a cada alteração do
ambiente;
)()((
2211
1 n
id
n
bd
nn
id
n
id
nn
id
n
id
xprcxprcwvv −+−+=
+
tvxx
n
id
n
id
n
id
∆+=
++
.
11
27
• adaptação: a nuvem deve ser capaz de alterar o seu comportamento caso o custo
computacional seja proibitivo.
O algoritmo responde a fatores de qualidade inerentes a melhor posição de cada
partícula e a melhor partícula de todo a nuvem, considerando estas respostas de forma a
garantir diversidade. Além disto, a nuvem altera o seu comportamento somente quando a
melhor partícula da nuvem se altera, então, ele pode ser considerado tanto adaptativo
quanto estável (Eberhart et al., 1996).
O algoritmo de nuvem de partículas pode ser estruturado através do modelo de
algoritmo exposto na tabela 2.3.
Tabela 2.3 Modelo de algoritmo de nuvem de partículas.
1: Gerar população aleatória
2: Avaliar cada partícula da nuvem
3: Definir o valor inicial de
w
, c
1
, c
2
4: Encontrar o índice de b, que é a melhor partícula da nuvem
5: Enquanto objetivo não encontrado faça
6: iteração = iteração + 1
7:
w
=
w
-
w
d
, onde
w
d
é um valor previamente definido
8: Atualizar nuvem e velocidades de acordo com as equações (2.7) e (2.8)
9: Atualizar a melhor partícula e o índice de b
10: Fim Enquanto
11: Retorna resultado
28
Realizando uma análise dos parâmetros do algoritmo tem-se o papel da inércia
w
na
equação (2.7), é considerado crítico para a convergência da nuvem. A inércia é aplicada
para controlar o impacto do histórico das velocidades em relação à velocidade atual. O
parâmetro
w
regula o compromisso entre a busca global e a local da nuvem. Um valor
grande para a inércia facilita a busca global através da análise de regiões distintas através
do espaço de busca, enquanto valores menores auxiliam em uma busca local, realizando um
ajuste fino no atual espaço de busca. Um valor apropriado para este parâmetro deve
ocasionar um equilíbrio entre a busca local e a busca global e, conseqüentemente, resulta
em um menor número de iterações necessárias para se localizar a solução ótima.
Inicialmente a inércia era adotada como uma constante. Entretanto, resultados
experimentais indicam que é melhor utilizar um valor maior de
w
no início da busca,
promovendo uma pesquisa em um espaço mais amplo, e gradualmente diminuindo este
valor para realizar uma busca mais precisa (Shi e Eberhart, 1998). Um valor inicial para
w
de 1,2 com um gradual decremento até próximo de 0 pode ser considerado um valor
adequado para
w
.
Os parâmetros c
1
e c
2
, na equação (2.7), não são críticos para a convergência do
algoritmo. Entretanto, um ajuste preciso pode resultar em uma convergência mais rápida ao
mínimo local. Um estudo realizado em sua primeira versão (Kennedy, 1998), indica os
valores propostos como c
1
= c
2
= 2, mas resultados experimentais indicam que c
1
= c
2
= 0,5
podem prover melhores resultados. Recentemente Carlisle e Dozier (2001) indicam que
pode ser melhor escolher um valor maior para o parâmetro cognitivo, c
1
, em relação ao
social, c
2
, mas respeitando a premissa que c
1
+ c
2
≤
4.
Os parâmetros r
1
e r
2
são utilizados para manter a diversidade da população, e são
gerados com distribuição uniforme no intervalo [0,1].
A abordagem de nuvem de partículas e computação evolutiva diferem nas seguintes
características: Na computação evolutiva, três operações principais são utilizadas:
cruzamento ou recombinação, mutação e seleção. A nuvem de partículas não possui uma
operação de recombinação. Entretanto, a aceleração da partícula em direção à melhor
posição, bem como à melhor partícula da nuvem, se assemelha a função de recombinação
29
da computação evolutiva. Na nuvem de partículas a troca de informação esta relacionada
apenas à própria partícula e à melhor partícula da nuvem, ao invés de considerar
informações do fitness relativos aos pais similar aos algoritmos genéticos.
2.2.2 Colônia de bactérias
A teoria de foraging é baseada na suposição de que os seres vivos procuram obter
nutrientes de uma forma que o gasto de energia seja mínimo, e a absorção da energia seja
máxima. Desta forma tenta-se buscar uma maneira de maximizar a absorção de energia por
unidade de tempo gasta na procura.
A maximização de tal função fornece fontes de nutrientes para sobreviver e energia
adicional para demais atividades importantes, como, por exemplo, lutar, fugir, reproduzir,
abrigar-se. As atividades de foraging são diferentes entre as espécies, para os herbívoros, o
alimento é, geralmente, encontrado facilmente, entretanto deve ser consumido em grande
quantidade. Para os carnívoros costuma-se encontrar dificuldade para achar o alimento, mas
ele não é necessário em grande quantidade desde que possua valores elevados de energia
(Passino, 2002).
O ambiente estabelece o teste padrão dos nutrientes que estão disponíveis e as
restrições para obtê-los, sendo que as características necessárias para o sucesso na busca
dependem diretamente de quem procura o alimento. Para muitos animais, os nutrientes
estão distribuídos em locais específicos, por exemplo, em lagos, campos, arbustos, árvores
frutíferas, nestes casos o foraging envolve encontrar tais locais e, durante esta procura,
decidir se o atual local é adequado ou se deve procurar um local com maior qualidade e
quantidade de alimentos. Geralmente estes locais são encontrados seqüencialmente, e o
esforço e os riscos envolvidos são fatores considerados no momento de decidir pela procura
de um outro local de alimentação. Costumeiramente, se um animal encontrar um local de
alimentação pobre, mas baseado na experiência passada, espera encontrar um local com
melhores condições para alimentação, então os riscos e os esforços são considerados e, caso
aceitável, irá procurar um outro local para se alimentar. Isto também é válido se, durante o
período de permanência em uma localidade, o alimento começar a se tornar escasso, neste
30
caso, ele considera um novo deslocamento para buscar uma melhor região de alimentação.
Neste caso existe um conflito, o recurso disponível prontamente não deve ser desperdiçado,
mas também não se deve perder tempo em uma região com poucos recursos (Passino,
2002).
Uma possível teoria de otimização inspirada em colônia de bactérias formula o
problema de foraging como um problema de otimização, baseado no comportamento da
bactéria Escherichia Coli que encontra-se presente em nossos intestinos. Neste caso
métodos computacionais ou analíticos podem ser utilizados para formular “políticas” de
foraging, que específica as variáveis já citadas e como as decisões devem ser tomadas.
Existem quantificações das decisões de foraging, precisam ser definidos os benefícios e as
restrições na parametrização da otimização. Por exemplo, existem estudos de como
maximizar a taxa média de energia absorvida em longo prazo onde apenas certas decisões
de restrições são permitidas (Stephens e Krebs, 1986). Essencialmente, esta abordagem de
otimização procura obter uma política de controle eficiente para realizar as decisões de
foraging. Alguns biólogos, entretanto, questionam a validez de tal aproximação,
argumentando que nenhum animal pode tomar decisões ótimas, porém a formulação do
“foraging ótimo” significa apenas um modelo que detalha qual deveria ser o
comportamento ótimo a ser adotado. A heurística de foraging é utilizada de forma eficaz
para aproximar políticas de otimização, sugerindo restrições físicas as quais as bactérias
estão expostas. A tabela 2.4 mostra um algoritmo simplificado para a otimização
utilizando-se esta técnica.
31
Tabela 2.4 Algoritmo de colônia de bactérias.
1: Definir parâmetros iniciais do algoritmo
2: Enquanto Eliminação- Dispersão menor que limite faça
3: Enquanto Reprodução menor que limite faça
4: Enquanto Chemotaxis loop (vida da bactéria)
5: Executar seqüência de tumble e movimento, até o limite de profundidade para cada
iiiiibactéria
6: Se Chemotaxis maior que limite, execute passo 7, senão retorna para 4.
7: Executa a reprodução das bactérias mais saudáveis (melhores valores de fitness) e
iiiiielimina as bactérias menos saudáveis (piores valores de fitness)
8: Fim Enquanto Reprodução
9: Executa a eliminação e a dispersão das bactérias
10: Fim Enquanto Eliminação-Dispersão
11: Retorna resultado
2.3 Métodos híbridos de otimização
Os métodos híbridos consistem na utilização de um algoritmo de busca global
associado a um outro de busca local. Para este trabalho será utilizado o algoritmo simulated
annealing como elemento de busca local. Este algoritmo será associado aos outros criando
assim uma técnica de otimização híbrida.
2.3.1 Simulated annealing
O algoritmo simulated annealing (SA), ou têmpera simulada, é uma variação de
algoritmos de subida de encosta, onde o objetivo é a minimização de uma função objetivo
(nível de energia).
32
O simulated annealing baseia-se em uma analogia com a mecânica estatística de
resfriamento dos materiais, onde substâncias físicas tais como os metais são levados a altos
níveis de temperatura e posteriormente são gradualmente resfriadas até alcançar um estado
mínimo de energia (Kirkpatrick et al., 1983). Sob outras condições, menos cuidadosas de
resfriamento, o material se cristalizaria com uma energia “localmente mínima”, o que
freqüentemente se traduz em imperfeições estruturais. A esse processo cuidadoso de
resfriamento denomina-se annealing.
A abordagem do simulated annealing é probabilística. O algoritmo não requer
informação de derivadas e não é afetado por descontinuidades e não-linearidades. Ele é um
procedimento de descida de encosta, mas configurado de forma modificada, desta forma
realiza pequenos passos de busca em uma topografia local. Se o passo resulta em uma
melhora na solução, a nova solução é aceita, caso contrário, a probabilidade da
configuração ser aceita será dada pela equação (2.9).
(2.9)
onde K
b
é a constante de Boltzmann e T é a temperatura.
Contudo, com o progresso das iterações o SA é reduzida a probabilidade de aceitar
uma nova solução, através da redução da temperatura, desta forma para a utilização do
simulated annealing, de forma eficiente, em problemas de otimização, deve-se tomar
cuidado com o parâmetro T, que caso possua um valor demasiadamente elevado, implicará
na aceitação de um grande número de resultados, e caso seja possua um valor muito
pequeno, terá dificuldade em escapar de mínimos locais (Saramago, 2003).
A idéia do simulated annealing origina-se numa combinação das observações sobre
a física dos materiais, com procedimento computacional tendo por finalidade a simulação
do comportamento de uma coleção de átomos (variáveis do problema) em condições de
temperatura fixa.
O algoritmo simulated annealing pode ser descrito com na tabela 2.5.
)(
)(
TK
E
b
eEP
∆−
=∆
33
Tabela 2.5 Algoritmo de simulated annealing.
1: Definir parâmetros iniciais do algoritmo
2: Enquanto objetivo não encontrado faça (ou critério de parada)
3: Aumentar temperatura para buscar melhores soluções
4: Se melhor solução encontrada, passo 6, senão
5: Aceita a solução pior com a probabilidade expressa pela equação (2.9)
6: Assume novo valor
7: Fim Enquanto
8: Retorna resultado
2.3.2 Algoritmos determinísticos combinados com algoritmos
estocásticos
Os métodos de otimização têm duas formas de configuração: os métodos
determinísticos e os métodos estocásticos (abordados nesta proposta de dissertação). As
técnicas determinísticas buscam um ponto de mínimo, baseado na informação dada pelo
negativo do gradiente da função objetivo. A eficiência destas técnicas depende de diversos
fatores, tais como: a solução inicial, a precisão da avaliação da direção descendente e o
método utilizado para executar, além do critério de parada. A solução obtida é geralmente
um ponto de mínimo (ou máximo) local, que pode ser mínimo global se a função apresentar
apenas uma moda. As duas desvantagens principais são a necessidade de avaliações do
gradiente e falta da garantia do mínimo global. Os métodos estocásticos, dos quais os
algoritmos evolutivos fazem parte, não necessitam do cálculo do gradiente e são aptos a
encontrar a solução global. Contudo, o número de avaliações da função objetivo,
necessárias para encontrar a solução, é normalmente maior que o número requerido pelos
métodos determinísticos.
A configuração de abordagens compostas por técnicas determinísticas, estas
hibridizadas, com técnicas estocásticas, é uma alternativa. Para obter os benefícios da
34
configuração híbrida, uma forma eficiente é executar, inicialmente, um algoritmo evolutivo
para localizar a região de ótimo global e após aplicar-se outra metodologia de otimização
para a busca local. A vantagem da utilização de um método de busca direto em relação à
busca local está na melhoria da velocidade de convergência pela avaliação da função
objetivo. O valor final obtido pelo método de busca direto provavelmente será mais preciso
que o obtido pelo algoritmo evolutivo ou outro método da inteligência computacional.
35
Capítulo 3 - Estudos de casos
Para testar e avaliar cada uma das técnicas propostas, bem como responder algumas
perguntas, como as apresentadas no objetivo deste trabalho, são propostos alguns
problemas-teste, necessários para comparar as diversas técnicas apresentadas na dissertação
a ser desenvolvida.
3.1 Projeto de um recipiente de pressão
O objetivo deste primeiro problema é o de minimizar o custo total do desenho de um
recipiente de pressão conforme a figura 3.1.
Figura 3.1 Projeto de um recipiente de pressão.
Existem quatro variáveis no projeto: x
1
(T
s,
espessura do invólucro), x
2
(T
h,
espessura da tampa), x
3
(R, raio interno) e x
4
(L, comprimento da secção cilíndrica do
recipiente), R e L são contínuos. O problema pode ser descrito conforme segue:
T
h
R
L
R
T
s
36
Minimizar:
f(X) = 0,6224x
1
x
3
x
4
+ 1,7781x
2
x
3
2
+ 3,1661x
1
2
x
4
+ 19,84x
1
2
x
3
(3.1)
Sujeito a:
g
1
(X) = -x
1
+ 0,0193x
3
≤
0 (3.2)
g
2
(X) = -x
2
+ 0,00954x
3
≤
0 (3.3)
g
3
(X) = -
π
x
3
2
x
4
– 4/3
π
x
3
3
+ 1296000
≤
0 (3.4)
g
3
(X) = x
4
- 240
≤
0 (3.5)
Os seguintes limites das variáveis x = [x
1
, x
2
, x
3,
x
4
] serão utilizados:
1
≤
x
1
≤
99, 1
≤
x
2
≤
99, 10
≤
x
3
≤
200, 10
≤
x
4
≤
200.
Na tabela 3.1 são apresentados alguns resultados encontrados na literatura para a
resolução do problema de recipiente de pressão.
Tabela 3.1 Comparação de alguns resultados da literatura do problema do recipiente de pressão.
Algumas soluções presentes na literatura
Variáveis
do projeto
Hu et al.(2003) Coello (2000) Deb (1997)
x
1
(T
s
) 0,8125 0,8125 0,9375
x
2
(T
n
) 0,4375 0,4375 0,5000
x
3
(R) 42,09845 40,3239 48,3290
x
4
(L) 176,6366 200,0000 112,6790
g
1
(X) 0,0 -0,034324 -0,004750
g
2
(X) -0,03588 -0,052847 -0,038941
g
3
(X) -5,820e-11 -27,10584 -3652,876
g
4
(X) -63,3624 -40,0000 -127,3210
f(X) 6059,1312 6288,7445 6410,3811
37
3.2 Projeto de uma viga engastada
O objetivo é minimizar o custo de uma viga com as limitações de tensão de
cisalhamento, tensão de dobramento na viga, esforço de carga na barra, reflexão final da
viga e restrições laterais, conforme expresso na figura 3.2.
Figura 3.2 Projeto de uma viga engastada.
O problema pode ser expresso como:
Minimizar:
f(X) = 1,10471x
1
2
x
2
+ 0,04811x
3
x
4
(14,0 +
x
2
) (3.6)
sujeito a:
g
1
(X) =
max
)( ττ −X
≤
0
(3.7)
g
2
(X) =
−
)(X
σ
max
σ
≤
0
(3.8)
g
3
(X) = x
1
– x
4
≤
0 (3.9)
P
L
b
t
h
l
38
g
4
(X) = 0,10471x
1
2
+ 0,04811x
3
x
4
(14,0 +
x
2
) - 5
≤
0 (3.10)
g
5
(X) = 0,125 – x
1
≤
0 (3.11)
g
6
(X) =
max
)( δδ −X
≤
0
(3.12)
g
7
(X) = P – P
c
(X)
≤
0 (3.13)
onde:
)(X
τ
=
2''
2
2'
)(
2
'''2)( ττττ ++
R
x
(3.14)
21
2
'
xx
P
=τ
(3.15)
J
MR
=''τ
(3.16)
)
2
(
2
x
LPM +=
(3.17)
2
31
2
2
)
2
(
4
xxx
R
+
+=
(3.18)
+
+=
2
31
2
2
21
212
22
xx
x
xxJ
(3.19)
2
34
6
)(
xx
PL
X =σ
(3.20)
4
3
3
3
4
)(
xEx
PL
X =δ
(3.21)
−=
G
E
L
x
L
xx
E
XP
c
42
1
36
013,4
)(
3
2
6
4
2
3
(3.22)
39
onde:
P = 6000 lb, L = 14 in, E = 30.10
6
psi
G = 12.10
6
psi, psi13600
max
=τ
25,0,30000
maxmax
== δσ psi in.
Os seguintes limites das variáveis x = [x
1,
x
2,
x
3,
x
4
] serão utilizados:
0,1
≤
x
1
≤
2,0, 0,1
≤
x
2
≤
10,0, 0,1
≤
x
3
≤
10,0, 0,1
≤
x
4
≤
2,0.
Na tabela 3.2 são apresentados resultados encontrados na literatura.
Tabela 3.2 Comparação de alguns resultados da literatura para o projeto de um viga engastada.
Algumas soluções presentes na literatura Variáveis
do projeto
Hu et al. (2003) Coello (2000) Deb (1997)
x
1
(h) 0,20573 0,20880 0,2489
x
2
(l) 3,47049 3,42050 6,1730
x
3
(t) 0,03662 8,99750 8,1739
x
4
(b) 0,20573 0,21000 0,2533
g
1
(X) 0,0 -0,337812 -5758,603
g
2
(X) 0,0 -353,9026 -255,5769
g
3
(X) -5,551e-17 -0,001200 -0,004400
g
4
(X) -3,432983 -3,411865 -2,982866
g
5
(X) -0,080729 -0,083800 -0,123900
g
6
(X) -0,235540 -0,235649 -0234160
g
7
(X) -9,094e-13 -363,2323 -4465,270
f(X) 1,7248508 1,7483094 2,433116
40
3.3 Minimização do peso de uma mola de tensão/compressão
O problema consiste na minimização do peso de uma mola de tensão/compressão,
ilustrada na figura 3.3, sujeita a restrições de desvio mínimo, tensão de cisalhamento,
freqüência de onda, limites de diâmetro externo e variáveis de projeto. As variáveis do
projeto são o diâmetro interno D, o diâmetro do fio d e o número de espiras ativas N.
Figura 3.3 Mola de tensão e compressão.
O problema pode ser expresso como segue:
Minimizar:
2
)2()( DdNxf +=
(3.23)
sujeito a:
g
1
(X) =
4
3
71785
1
d
ND
−
≤
0
(3.24)
g
2
(X) =
1
5108
1
)(12566
4
243
2
−+
−
−
ddDd
dDD
≤
0
(3.25)
P
P
d
D
41
g
3
(X) =
N
D
d
2
45,140
1−
≤
0
(3.26)
g
4
(X) =
1
5,1
−
+
dD
≤
0
(3.27)
Os seguintes limites das variáveis x = [x
1,
x
2,
x
3
] serão utilizados:
0,05
≤
x
1
≤
2,0; 0,25
≤
x
2
≤
1,3; 2,0
≤
x
3
≤
10,0.
Na tabela 3.3 são apresentados resultados encontrados na literatura.
Tabela 3.3 Alguns dos resultados para minimização do peso de uma mola de tensão/compressão.
Algumas soluções presentes na literatura
Variáveis do
projeto
Hu et
al.(2003)
Ray e Liew
(2003)
Coello
(2000)
Arora
(1989)
x
1
(d) 0,05146636 0,0521602 0,051480 0,053396
x
2
(D) 0,35138383 0,3681587 0,351661 0,399180
x
3
(N) 11,6086592 10,648442 11,632201 9,185400
g
1
(X) -0,00333661 -7,4527e-9 0,002080 0,000019
g
2
(X) -1,09701e-4 -0,1314 -0,000110 -0,000018
g
3
(X) -4,02631809 -4,0758 -4,026318 -4,123842
g
4
(X) -0,73123933 -0,7198 -0,731239 -0,698283
f(X) 0,01266614 0,01266924 0,01270478 0,01273027
42
Capítulo 4 – Consideração sobre os resultados
Após a implementação dos algoritmos propostos, estes foram submetidos ao
problemas-teste expostos no capítulo anterior. Para a análise dos algoritmos, duas
abordagens foram utilizadas: análise de desempenho on-line a análise de desempenho off-
line.
A análise on-line de uma estratégia de busca, representada por s, em uma superfície
de resposta, indicada por e, é definida por:
))((),( tumédiaTsU
ete
= ,
(4.1)
onde t = 0, 1, ..., T e u
e
(t) é a média do desempenho do algoritmo avaliado no tempo t. Ou
seja, a análise de desempenho on-line é a análise média do algoritmo em uma determinada
geração.
A análise off-line de uma estratégia de busca, representada por s, em uma superfície
de resposta, indicada por e, é definida por:
))((),(
**
tumédiaTsU
ete
= ,
(4.2)
onde t = 0, 1, ..., T e u
*
e
(t) é o melhor valor do algoritmo avaliado no tempo t. Ou seja, a
análise de desempenho off-line é a indicação do melhor valor de fitness do algoritmo s em
uma dada geração.
4.1 Tratamento de restrições
Outro aspecto que foi considerado para a determinação dos resultados foi a tratativa
dada as restrições de cada problema. Ao considerar-se todo o espaço de busca de um
problema, pode-se encontrar regiões dentro do intervalo de busca que não contenham
soluções válidas para o caso que está sendo analisando. Estas regiões são comumente
representadas através de equações matemáticas que delimitam o espaço de busca válido e
43
que precisam ser respeitadas quando considera-se o resultado final obtido após a execução
do algoritmo de busca.
Desta forma as soluções que respeitam os critérios de restrições fornecidos, são
consideradas soluções válidas para o problema, e as soluções que não são validadas pelas
restrições são consideradas soluções inválidas para o problema.
Um exemplo simples de restrição pode ser observado figura 4.1 e 4.2 (Ursem, 2003).
Figura 4.1 Espaço de busca restrito aos limites (x
1
-1)
2
- x
2
< 0 e x
2
- sen(3x
1
) - 0,5 < 0.
Figura 4.2 Espaço de busca abstrato com algumas regiões válidas.
As restrições freqüentemente são associadas a limitações físicas e práticas de
sistemas reais. Por exemplo, não é possível possuir resistores com um valor negativo de
resistência. Em outros casos as restrições podem ser utilizadas para atender a requisitos de
área válida
área válida
Espaço de busca
44
regulamentos ou normas, como taxa de emissão de raios-x, raios eletromagnéticos, etc.
Uma aplicação óbvia do tratamento destas restrições é a sua utilização objetivando
direcionar o algoritmo para regiões válidas no espaço de busca.
Para resolver esta questão foram propostas várias alternativas para o tratamento de
restrições. Dentre as diversas técnicas desenvolvidas, as funções de penalidades são as
mais empregadas atualmente. O método de penalidades é baseado na idéia de transformar o
problemas com restrição em problemas sem restrições através da adição ou subtração de
valores na função objetivo, tomando como base a quantidade de restrições violadas por uma
determinada solução proposta.
Um desafio está na determinação de quanto uma determinada solução que violou
uma restrição deve ser penalizada. Valores muito altos de penalização tendem a concentrar
o algoritmos de busca em pontos distantes dos limites do espaço válido. E valores muito
pequeno tendem a fazer com que o algoritmo perca muito tempo em regiões que não são
consideradas válidas como solução. O problema é que muitas vezes o valor da solução
ótima pode estar na região limítrofe do espaço que contempla os valores válidos de
resposta, tornando a escolha do quanto penalizar uma determinada solução um problema a
ser considerado com muito cuidado. Esta necessidade de se manter o valor da penalização
logo acima do limite das soluções válidas é denominada regra de menor penalização. Esta é
ma regra conceitualmente bastante simples, porém possui muitas vezes uma implementação
extremamente complexa, uma vez que os limites do espaço de busca são desconhecidos ou
de difícil identificação.
Entre as formas de penalização foram consideradas a penalização estática, dinâmica
e a eliminação do resultado inválido. Na penalização estática são definidos diversos níveis
de violação da restrição e associado um coeficiente de penalização para cada nível de
violação de forma que quando maior for a violação, maior será a penalização.
Esta abordagem tem início com a geração de uma população de indivíduos, validos
ou não. Cada indivíduo é analisado utilizando-se da seguinte equação:
∑
=
×+=
m
i
iik
xgmáxRxfxfitness
1
2
,
))](,0[()()(
rrr
(4.3)
45
onde R
k,i
são os coeficientes de penalização utilizados, m é o total de restrições, f(x) é a
função objetivo não penalizada e k = 1, 2, ..., l, onde l é o número de níveis de violação
definidos pelo usuário.
A penalização dinâmica é aquela em que a busca realizada no passado influência no
resultado futuro. Nesta proposta os membros da população são analisados (em uma geração
t) utilizando:
),()()()( xSVCtCxfxfitness
r
r
r
β
α
××+=
(4.4)
onde C, α, β, são constantes e ),( xSVC
r
β
é definido por:
∑∑
==
+=
n
i
p
j
ji
xDxDxSVC
11
)()(),(
rrr
β
β
(4.5)
e
0 gi(x) ≤ 0
Di(x) = 1 ≤ i ≤ n
|gi(x)| caso contrário
0 -
ε
≤ hj(x) ≤
ε
Dj(x) = 1 ≤ j ≤ p
| hj(x)| caso contrário
onde
ε
é um valor muito pequeno. Neste caso a função aumenta o valor de penalização a
medida que se progride através das gerações do algoritmo.
A penalização de eliminação é aquela onde os membros da população são rejeitados
caso uma das restrições seja violada, sendo o fitness deste membro designado como 0, esta
técnica é a de implementação mais simples entretanto corre-se o risco de que todos os
membros rejeitados em um determinado momento, o que forçaria a adotar membros
aleatórios para continuar a execução do algoritmo. Embora estudada, esta técnica não foi
utilizada nos problemas propostos.
46
Capítulo 5 – Discussão dos resultados
Neste tópico, o resultado dos algoritmos aplicados aos problemas-teste são
apresentados. Para a obtenção destes resultados, todos os algoritmos consideraram a
população contendo 30 elementos e o número de gerações para cada experimento foi
mantido em 1000. Outro ponto relevante é a aplicação do algoritmo simulated annealing,
como algoritmo de busca local, sendo este algoritmo aplicado apenas ao melhor membro de
cada geração, e caso o resultado fosse melhorado este novo membro era adicionado a
população, caso contrário nenhuma alteração era realizada.
Cada um dos três estudos de caso foi resolvido utilizando-se os seguintes
parâmetros nos algoritmos:
• Algoritmo genético, definidos de acordo com Goldberg (1989):
o P
c
= 0,80;
o P
m
= 0,07.
• PBIL, onde µ segue a análise de Ganzález et al., (2000) e os demais parâmetros
através de tentativa e erro:
o α = 0,3;
o µ = 1;
o p
m
= 0,4.
• Programação evolucionária, este parâmetro segue a sugestão de Bäck e Schwefel
(1993):
o
i
η = 3.
• Nuvem de partículas, os parâmetros foram retirados de Eberhart e Shi (2001):
o c
1
= 1,49445;
o c
2
= 1,49445;
o
w
= valor aleatório com distribuição uniforme no intervalo [0,5 ; 0,7];
47
o V
máx
= 1,1·V, onde V é a velocidade da partícula.
• Colônia de bactérias, para a seleção dos parâmetros foi seguido a sugestão de
Passino (2002):
o N
c
= 100;
o N
s
= 4;
o N
re
= 4;
o N
ed
= 10;
o P
ed
= 0,25;
o C(i) = 0,1.
O algoritmo simulated annealing teve os seus parâmetros ajustados de acordo com a magnitude
das respostas esperadas, através de tentativa e erro, de forma a realizar uma busca local. Os
seguintes valores foram utilizados para cada problema:
• Vaso de pressão:
o T
máx
= 10;
o T
min
= 0,0;
o ΔT = 0,5.
• Viga engastada:
o T
máx
= 0,5;
o T
min
= 0,0;
o ΔT = 0,05.
• Mola:
o T
máx
= 0,01;
o T
min
= 0,0;
o ΔT = 0,001.
48
5.1 Projeto de um vaso de pressão
Não foi possível superar o melhor resultado existente na literatura, mas foi possível
obter resultados satisfatórios conforme mostra a tabela 5.1.
Como mostrado, o algoritmo de nuvem de partículas híbrido com simulated
annealing foi o que apresentou o melhor resultado geral, pode-se observar também que
todas as soluções apresentadas respeitam os limites impostos devido às restrições do
problema. Neste problema o algoritmo genético utilizando simulated annealing também
apresentou uma resposta adequada para o problema. A melhor resposta apresentada nesta
dissertação é a indicada por Hu et al. (2003).
Em todos os casos o algoritmo simulated annealing foi utilizado para realizar a
busca local, como se fosse um “ajuste fino”, esta abordagem melhorou o resultado
alcançado pelo algoritmo não-híbrido em todos os casos. O algoritmo genético e o PBIL
tiveram uma melhora de 0,3% no resultado após a execução do simulated annealing, a
programação evolucionária e a colônia de bactérias tiveram um ganho de 0,5% e a nuvem
de partículas um ganho de 1,7%.
Tabela 5.1 Melhores resultados encontrados – vaso de pressão.
Melhor solução encontrada dos 30 experimentos
Variáveis do
projeto
Algoritmo
Genético
Algoritmo
Genético
com SA
PBIL
PBIL com
SA
Programação
evolucionária
x
1
(T
s
) 0,8574 0,8564 0,8674 0,8644 0,8350
x
2
(T
n
) 0,5055 0,5045 0,6572 0,6561 0,6420
x
3
(R) 43,5600 43,5402 44,5500 44,4510 43,1640
x
4
(L) 159,6000 159,6280 148,6829 149,5140 167,7380
g
1
(X) -0,0167 -0,0161 -0,0076 -0,0065 -0,0019
g
2
(X) -0,0899 -0,0891 -0,2321 -0,2321 -0,2302
g
3
(X) -1712,5301 -440,0319 -1423,5145 -2,8478 -5107,4580
g
4
(X) -80,3828 -80,3720 -91,3171 -90,4860 -75,2620
f(X) 6422,4345 6409,5646 6914,2106 6893,4688 6782,9325
49
Tabela 5.1 Melhores resultados encontrados – vaso de pressão (cont.).
Melhor solução encontrada dos 30 experimentos (cont.)
Variáveis do
projeto
Programação
evolucionária
com SA
Nuvem de
partículas
Nuvem de
partículas
com SA
Colônia de
bactérias
Colônia de
bactérias
com SA
x
1
(T
s
) 0,8275 0,8873 0,8863 0,8873 0,8873
x
2
(T
n
) 0,6410 0,5459 0,5156 0,6167 0,6066
x
3
(R) 42,7680 45,8370 45,8271 45,9360 45,9360
x
4
(L) 168,5601 135,2403 135,5092 134,2671 134,3826
g
1
(X) -0,0021 -0,0027 -0,0019 -0,0008 -0,0008
g
2
(X) -0,2330 -0,1087 -0,0784 -0,1785 -0,1684
g
3
(X) -272,5314 -65,7667 -1193,2754 -94,3465 -860,0105
g
4
(X) -71,4399 -104,7597 -104,4908 -105,7329 -105,6000
f(X) 6744,0753 6516,2562 6402,4791 6772,4317 6737,7171
Realizando a análise dos resultados obtidos, pode-se observar que o algoritmo
genético foi o melhor algoritmo evolutivo e também o melhor algoritmo evolutivo híbrido.
A sua população converge para uma resposta (figura 5.1), e a partir da 300
a
geração o
algoritmo esta praticamente estabilizado, sendo que o valor do melhor membro da
população é coletado como resposta do algoritmo na 1000
a
geração (e foi apresentado na
tabela 5.1), logo em seguida, o algoritmo é reiniciado e desta vez o algoritmo de busca local
é executado, ao término de sua execução tem-se a resposta do algoritmo genético utilizando
o simulated annealing. Em seguida o processo recomeça e é executado um total de 30
vezes. Pode-se observar também que o algoritmo utilizando a busca local teve um melhor
desempenho de forma constante. Deve-se destacar que este algoritmo foi o que obteve o
melhor desempenho desconsiderando-se a busca local realizada pelo simulated annealing.
A sua forma híbrida supera o resultado apresentado por Deb (1997) em 0,01%.
50
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
147101316192225301004007001000
geração
fitness
desempenho online
desempenho offline
desempenho offline SA
Figura 5.1 Convergência do algoritmo genético aplicado ao projeto do vaso de pressão.
O próximo algoritmo executado foi o PBIL (figura 5.2), a sua convergência ocorreu
em torno da 400
a
geração, os ganhos apresentados pela utilização em conjunto com o SA
foram expressivos em algumas gerações específicas, como por exemplo na geração 12.
Entretanto a resposta ao final da 1000
a
geração foi a pior entre todos os algoritmos testados
nesta dissertação para este estudo de caso. O desempenho do PBIL, comparado ao melhor
algoritmo evolutivo apresentado na tabela 5.1, foi 7,29% pior que o obtido pelo algoritmo
genético com SA e o PBIL com busca local utilizando o SA foi 7,01% pior que o algoritmo
genético utilizando o SA. Em relação ao resultado encontrado por Hu et al. (2003) o
resultado foi 12,36% e 12,10% pior para o PBIL e PBIL com SA, respectivamente. Em
relação a Coello (2000) o desempenho foi 9,04% (PBIL) e 8,77% (PBIL com SA) pior. E
em relação a Deb (1997) o resultado foi 7,28% e 7,00% pior.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
51
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
Geração
Fitness
desempenho online
desempenho offline
desempenho offline SA
Figura 5.2 Convergência do PBIL aplicado ao projeto do vaso de pressão.
A figura 5.3 apresenta a convergência do algoritmo de programação evolucionária.
Seu desempenho foi intermediário se comparado aos demais resultados de algoritmos
evolutivos apresentados nesta dissertação, sendo a sua forma não-híbrida 5,31% e 5,50%
pior que o algoritmo genético e a sua variação com o simulated annealing, respectivamente,
e 1,89% e 1,60% melhor em relação ao PBIL e PBIL com SA, respectivamente.
A sua versão híbrida com o simulated annealing foi, se comparado ao algoritmo
genético, 4,76% pior (e 4,96% com a versão híbrida do algoritmo genético) e foi 2,46% e
2,16% melhor em relação ao PBIL e PBIL com SA, respectivamente..
Pode-se observar um ganho constante proporcionado pelo algoritmo de busca local
se comparado as demais técnicas de algoritmos evolutivos. Um ponto interessante é que
esta técnica foi a que convergiu mais cedo, por volta da geração 150, entretanto este fator
não garantiu a melhor resposta apresentada.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
52
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
1
4
7
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
Geração
Fitness
desempenho online
desempenho offline
desempenho offline SA
Figura 5.3 Convergência da programação evolucionária aplicado ao projeto do vaso de pressão.
A abordagem de nuvem de partículas apresentou o melhor resultado desta
dissertação para o problema do vaso de pressão (figura 5.4). Seu desempenho foi 5,36%
pior que o resultado encontrado por Hu et al. (2003), 1,77% pior que o resultado indicado
por Coello (2000) e 0,01% melhor que o valor apresentado por Deb (1997). O ganho da
busca local foi constante ao longo de todo o espaço de busca, e a sua convergência se deu
próximo a geração 500.
Ao comparar-se o resultado com a outra técnica de inteligência coletiva o resultado
encontrado pelo algoritmo de nuvem de partículas é 5,46% melhor que a colônia de
bactérias e 4,97% melhor que a versão híbrida da colônia de bactérias com o simulated
annealing.
Deve-se ressaltar também que o algoritmo de nuvem de partículas utilizando o
simulated annealing foi o que apresentou o menor valor para o desempenho online para
este estudo de caso. Isto indica que este algoritmo foi o que apresentou a melhor
convergência entre todas as técnicas estudadas para este problema.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
53
0
20000
40000
60000
80000
100000
120000
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
Geração
Fitness
desempenho online
desempenho offline
desempenho offline SA
Figura 5.4 Convergência da nuvem partículas aplicado ao projeto do vaso de pressão.
O algoritmo de colônia de bactérias teve um bom desempenho, encontrando o terceiro
melhor resultado para este problema, sua população convergiu próximo a 500
a
geração
(figura 5.5), e o simulated annealing conseguiu melhorar o resultado de forma constante,
sendo 2,25% melhor que o PBIL e 4,97% pior que o algoritmo de nuvem de partículas.
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
Geração
Fitness
desempenho online
desempenho offline
desempenho offline SA
Figura 5.5 Convergência da colônia de bactérias aplicado ao projeto do vaso de pressão.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
54
Outro indicativo de desempenho dos algoritmos pode ser observado na tabela 5.2.
Nela podem-se verificar o melhor valor obtido , na coluna Mínimo, e o “pior” valor
fornecido como solução após a execução de cada algoritmo, na coluna Máximo. Ao
término das 30 execuções de cada algoritmo, tem-se uma média dos melhores resultados
fornecidos e o desvio padrão, que indicam a convergência dos membros da população para
um valor comum.
Pode-se verificar que o algoritmo que apresentou o menor desvio padrão foi a
programação evolucionária com o simulated annealing, com o valor de 6,0931. O
algoritmo que apresentou a menor média foi o de nuvem de partículas hibridizado com o
simulated annealing, com o valor de 6412,9514.
Outro informação importante é o fato de que todos os algoritmos apresentados
tiveram um melhor desempenho quando utilizando de forma conjunta com um algoritmo de
busca local, neste caso o algoritmo simulated annealing foi configurado de forma a realizar
esta busca. O algoritmo genético e o PBIL tiveram uma melhora de 0,3% no resultado após
a execução do simulated annealing, a programação evolucionária e a colônia de bactérias
tiveram um ganho de 0,5% e a nuvem de partículas foi quem obteve a maior melhora,
possuindo um ganho de 1,7% em relação a sua versão não-hibridizada.
O algoritmo que apresentou o pior desempenho foi o PBIL, tanto na sua forma
original, quanto na forma associada ao algoritmo de busca local. Este algoritmo convergiu
como pode ser observado na tabela 5.2, mas não foi capaz de apresentar um resultado tão
bom quantos os demais algoritmos para este estudo de caso.
55
Tabela 5.2 Comparativo entre os algoritmos para o problema do vaso de pressão.
Algoritmo Mínimo Máximo Média Desvio Padrão
Algoritmo
Genético
6422,4345 6441,3156 6429,1364 7,1326
Algoritmo
Genético com
SA
6409,5646
6438,1329 6427,9543 7,0364
PBIL
6914,2106
6960,7167 6927,1985 12,8431
PBIL
com SA
6893,4688
6972,5568 6934,3698 12,7316
Programação
Evolucionária
6782,9325
6799,3124 6786,4986 6,1164
Programação
Evolucionária
com SA
6744,0753
6798,1220 6786,1006 6,0931
Nuvem de
partículas
6516,2562
6540,3197 6421,8521 6,8569
Nuvem de
partículas com
SA
6402,4791
6437,1486 6412,9514 6,5130
Colônia de
bactérias
6772,4317
6798,3579 6781,9951 8,1359
Colônia de
bactérias com
SA
6737,7171
6779,8912 6752,5511 8,0951
56
5.2 Projeto de uma viga engastada
Novamente não foi possível superar o melhor resultado existente na literatura,
conforme mostra a tabela 5.3.
O algoritmo de nuvem de partículas híbrido com simulated annealing foi o que
apresentou o melhor resultado geral novamente, pode-se observar também que todas as
soluções apresentadas respeitam os limites impostos devido às restrições do problema, o
que indica que todos os algoritmos apresentam resultados válidos como resposta.
Tabela 5.3 Melhores resultados encontrados dos 30 experimentos – viga engastada.
Melhor solução encontrada dos 30 experimentos
Variáveis do
projeto
Algoritmo
Genético
Algoritmo
Genético
com SA
PBIL
PBIL com
SA
Programação
evolucionária
x
1
(h) 0,2201 0,2109 0,2511 0,2499 0,2471
x
2
(l) 4,4159 4,3821 5,1580 5,1540 6,1545
x
3
(t) 8,2154 8,2057 8,4589 8,4149 8,3149
x
4
(b) 0,3114 0,3111 0,2670 0,2680 0,2582
g
1
(X) -2223,5582 -1634,5661 -4969,5924 -4884,4679 -5790,0733
g
2
(X) -6019,7061 -5939,7988 -3618,9855 -3441,8497 -1766,7914
g
3
(X) -0,0913 -0,1002 -0,0159 -0,0181 -0,0111
g
4
(X) -2,7283 -2,7377 -2,9117 -2,9153 -2,9119
g
5
(X) -0,0951 -0,0859 -0,1261 -0,1249 -0,1221
g
6
(X) -0,2372 -0,2372 -0,2364 -0,2363 -0,2352
g
7
(X) -13505,2804 -13432,9246 -6546,1431 -6642,2435 -5215,4863
f(X) 2,5029 2,4729 2,4409 2,4337 2,4968
57
Tabela 5.3 Melhores resultados encontrados dos 30 experimentos – viga engastada (cont.).
Melhor solução encontrada dos 30 experimentos (cont.)
Variáveis do
projeto
Programação
evolucionária
com SA
Nuvem de
partículas
Nuvem de
partículas
com SA
Colônia de
bactérias
Colônia de
bactérias
com SA
x
1
(h) 0,2465 0,2108 0,2106 0,2259 0,2248
x
2
(l) 6,1492 3,6421 3,6358 3,4863 3,4857
x
3
(t) 8,3131 9,5135 9,4267 9,4785 9,4179
x
4
(b) 0,2571 0,2110 0,2108 0,2300 0,2281
g
1
(X) -5764,2344 -1343,8335 -1226,0763 -1737,5132 -1616,5347
g
2
(X) -1633,7158 -3608,2957 -3094,5316 -5609,3445 -5088,3948
g
3
(X) -0,0106 -0,0002 -0,0002 -0,0041 -0,0033
g
4
(X) -2,9218 -3,2916 -3,3093 -3,1607 -3,1876
g
5
(X) -0,1215 -0,0858 -0,0856 -0,1009 -0,0998
g
6
(X) -0,2351 -0,2379 -0,2376 -0,2388 -0,2385
g
7
(X) -5068,1302 -691,4426 -633,7085 -2646,5247 -2399,6339
f(X) 2,4846 1,8825 1,8642 2,0305 2,0017
O algoritmo genético foi o que apresentou o pior resultado neste estudo de caso,
com um valor de fitness igual a 2,5029, um desempenho 31,08% pior do que foi indicado
por Hu et al. (2003), que é o melhor resultado apresentado nesta dissertação. Deve-se citar
que não houve nenhuma mudança na estrutura ou configuração de nenhum dos algoritmos.
Isto indica que o algoritmo genético não conseguiu obter uma boa resposta neste caso e que
algumas das demais técnicas, como a nuvem de partícula ou o PBIL, tiveram uma melhor
adaptação a este problema.
A melhor resposta encontrada, obtida pelo algoritmo de nuvem de partículas
utilizando o simulated annealing, foi 7,47% pior que a indicada no estudo de caso por Hu et
al. (2003), 6,21% pior que a encontrada por Coello (2000) e superou em 23,38% a resposta
58
apresentada por Deb (1997). Ao comparar este resultado com o melhor resultado
apresentado por um algoritmo evolutivo estudado nesta dissertação, o resultado é 23,40%
melhor que o algoritmo PBIL híbrido.
O algoritmo simulated annealing novamente foi capaz de melhorar todos os
resultados, o ganho foi de 1,19% para o algoritmo genético, 0,29% para o PBIL e 0,48%
para o algoritmo de programação evolucionária. Entre os algoritmos de inteligência coletiva
os ganhos foram de 0,97% e 1,41% para os algoritmos de nuvem de partículas e colônia de
bactérias, respectivamente.
A figura 5.6 mostra que a população do algoritmo genético convergiu apenas por
volta da 700
a
geração, isto pode ser um indicador do motivo do porque esta técnica não
obteve um bom desempenho para este problema, lembrando que no problema anterior o seu
desempenho havia sido satisfatório. Mesmo assim o algoritmo convergiu e apresentou uma
resposta ao problema. A utilização do algoritmo simulated annealing trouxe um ganho
constante nesta configuração. Seu resultado foi 2,76% (versão não-híbrida) e 1,58% (versão
híbrida) pior que o PBIL que foi melhor técnica evolutiva para este estudo de caso e
25,51% e 24,61%, nas versões não-híbrida e híbrida, respectivamente, pior que o algoritmo
de nuvem de partículas híbrido.
0
10
20
30
40
50
60
70
80
90
1
4
7
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.6 Convergência do algoritmo genético aplicado ao projeto da viga engastada.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
59
O algoritmo PBIL também teve a convergência ocorrendo nas proximidades da 700
a
geração (figura 5.7), este algoritmo teve o seu desempenho online muito próximo do offline
ao longo de todo o tempo, isto pode indicar que uma eventual falta de diversidade na
população inicial ou a dificuldade do algoritmo fugir de regiões de mínimo local.
O PBIL com simulated annealing foi o melhor algoritmo evolutivo apresentado
nesta dissertação para este estudo de caso. Seu resultado foi 1,58% melhor que o algoritmo
genético utilizando a busca local e 2,04% melhor que o algoritmo de programação
evolucionária utilizando simulated annealing. Em relação aos resultados indicados no
capítulo 3, seção 3.2, o seu desempenho foi 29,12% pior que o resultado encontrado por Hu
et al. (2003) e 28,16% pior que o encontrado por Coello (2000). Em relação ao resultado
encontrado por Deb (1997) o seu resultado foi 0,0038 pior, ou seja, um resultado inferior a
0,01% de diferença.
0
10
20
30
40
50
60
70
80
90
100
1
4
7
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.7 Convergência do PBIL aplicado ao projeto da viga engastada.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
60
O algoritmo de programação evolucionária sofreu pouca influência do simulated
annealing, sua população convergiu lentamente (figura 5.8) de forma que este algoritmo
não apresentou um bom desempenho para este problema, sendo a sua versão híbrida com
simulated annealing 2,04% pior do que o melhor algoritmo evolutivo apresentado nesta
dissertação para este problema (PBIL) e 24,96% pior que o melhor algoritmo de
inteligência coletiva (nuvem de partículas).
0
10
20
30
40
50
60
70
80
90
1
4
7
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.8 Convergência da programação evolucionária aplicado ao projeto da viga engastada.
O algoritmo de nuvem de partículas novamente apresentou o melhor resultado. Para
este problema a sua convergência se deu de forma mais acentuada a partir da 100
a
geração,
sendo que convergiu completamente ao redor de 550
a
geração (figura 5.9). O simulated
annealing apresentou um contribuição constante ao longo das gerações. Como no problema
do vaso de pressão, a nuvem de partículas utilizando o simulated annealing conseguiu
superar o resultado apresentado no capítulo 3 por Deb (1997) em 23,38%, sendo superado
em 7,47% por Hu et al. (2003) e em 6,21% por Coello (2000).
Ao comparar o resultado com o algoritmo PBIL, melhor algoritmo evolutivo
encontrado nesta dissertação para este problema, o seu desempenho foi 23,40% melhor.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
61
0
10
20
30
40
50
60
70
80
90
1
4
7
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.9 Convergência da nuvem de partículas aplicado ao projeto da viga engastada.
Embora o algoritmo de colônia de bactérias tenha apresentado valores próximos de
desempenho online e offline (figura 5.10), o algoritmo utilizando o simulated annealing
convergiu a partir da 200
a
geração e também superou o resultado apresentado por Deb
(1997) em 17,73%. Ao realizar-se a comparação com os resultados encontrados por Hu et
al. (2003) e Coello (2000) os valores são 13,83% e 12,65% piores, respectivamente.
Na comparação com o algoritmo PBIL híbrido, o desempenho da colônia de
bactérias foi 16,56% melhor e foi 17,75% melhor ao comparar-se com a colônia de
bactérias utilizando o simulated annealing.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
62
0
10
20
30
40
50
60
70
80
90
100
1
4
7
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.10 Convergência da colônia de bactérias aplicado ao projeto da viga engastada.
Novamente um dos indicadores de desempenho dos algoritmos pode ser observado
na tabela 5.4. Nela pode-se verificar o melhor valor obtido , na coluna Mínimo, e o “pior”
valor fornecido como solução após a execução de cada algoritmo, na coluna Máximo. Ao
considerar-se as 30 execuções de cada algoritmo, tem-se uma média dos melhores
resultados fornecidos e o desvio padrão, que indicam a convergência dos membros da
população para um valor comum.
Deve-se observar também que o menor, e melhor, valor das colunas Mínimo,
Máximo, Média e Desvio Padrão pertencem ao mesmo algoritmo, que é o de nuvem de
partículas utilizando o simulated annealing, desta forma pode-se afirmar que este foi quem
apresentou a melhor convergência para este problema.
Como citado no início desta seção, o algoritmo simulated annealing foi capaz de
melhorar todos os resultados, o ganho foi de 1,19% para o algoritmo genético, 0,29% para
o PBIL e 0,48% para o algoritmo de programação evolucionária. Entre os algoritmos de
inteligência coletiva os ganhos foram de 0,97% e 1,41% para os algoritmos de nuvem de
partículas e colônia de bactérias, respectivamente.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
f
itness
63
Tabela 5.4 Comparativo entre os algoritmos para o problema de projeto de uma viga engastada.
Algoritmo Mínimo Máximo Média Desvio Padrão
Algoritmo
Genético
2,5029 2,5168 2,5062 0,0186
Algoritmo
Genético com
SA
2,4729
2,4863 2,4780 0,0181
PBIL
2,4409
2,4499 2,4440 0,0156
PBIL
com SA
2,4337
2,4484 2,4437 0,0155
Programação
Evolucionária
2,4968
2,5017 2,4983 0,0168
Programação
Evolucionária
com SA
2,4846
2,4906 2,4867 0,0165
Nuvem de
partículas
1,8825
1,8903 1,8860 0,0132
Nuvem de
partículas com
SA
1,8641
1,8725 1,8668 0,0129
Colônia de
bactérias
2,0305
2,0397 2,0340 0,0142
Colônia de
bactérias com
SA
2,0017
2,0101 2,0038 0,0139
64
5.3 Minimização do peso de uma mola de tensão/compressão
Conforme pode ser observado na tabela 5.5, o algoritmo PBIL foi o que apresentou
o melhor resultado para este problema, novamente as soluções respeitam as restrições, e
fornecem apenas resultados válidos para o problema. Outro algoritmo que apresentou bons
resultados foi o de nuvem de partículas, embora não tenho sido o melhor para este
problema, foi o melhor algoritmo de inteligência coletiva para este estudo de caso.
Em todos os casos o algoritmo simulated annealing foi utilizado para realizar a
busca local e melhorou os resultados encontrados pelos algoritmos não-híbridos. Entre os
algoritmos evolutivos a melhora no desempenho foi de 0,05% para o algoritmo genético,
0,54% para o PBIL e a programação evolucionária teve um ganho de 0,36%. Para os
algoritmos de inteligência coletiva o ganho foi de 0,11% para a nuvem de partículas e
0,51% para a colônia de bactérias.
Tabela 5.5 Melhores resultados encontrados dos 30 experimentos – mola tensão / compressão.
Melhor solução encontrada dos 30 experimentos
Variáveis do
projeto
Algoritmo
Genético
Algoritmo
Genético
com SA
PBIL
PBIL com
SA
Programação
evolucionária
x
1
(d) 13,5100 13,5000 12,0501 12,0002 12,4732
x
2
(D) 0,3260 0,3259 0,3457 0,3453 0,3400
x
3
(N) 0,0505 0,0505 0,0512 0,0512 0,0510
g
1
(X) -0,0026 -0,001 -0,0068 -0,0007 -0,0095
g
2
(X) -0,0067 -0,0075 -0,0002 -0,0001 -0,0009
g
3
(X) -3,9400 -3,9476 -3,9964 -4,0269 -3,9677
g
4
(X) -0,7490 -0,7491 -0,7354 -0,7357 -0,7393
f(X) 0,012895 0,012888 0,012747 0,012678 0,012799
65
Tabela 5.5 Melhores resultados encontrados dos 30 experimentos – mola tensão / compressão (cont.).
Melhor solução encontrada dos 30 experimentos (cont.)
Variáveis do
projeto
Programação
evolucionária
com SA
Nuvem de
partículas
Nuvem de
partículas
com SA
Colônia de
bactérias
Colônia de
bactérias
com SA
x
1
(d) 12,4202 11,7299 11,7281 11,6003 11,5901
x
2
(D) 0,3401 0,3502 0,3501 0,3550 0,3548
x
3
(N) 0,0510 0,0514 0,0514 0,0518 0,0517
g
1
(X) -0,0052 -0,0023 -0,0029 -0,0041 -0,0093
g
2
(X) -0,0009 -0,0013 -0,0004 -0,0098 -0,0049
g
3
(X) -3,9890 -4,0222 -4,0240 -3,9766 -3,9769
g
4
(X) -0,7393 -0,7322 -07323 -0,7288 -0,7290
f(X) 0,012752 0,012723 0,012708 0,012955 0,012888
O algoritmo genético teve o pior desempenho entre os algoritmos evolutivos para a
resolução deste problema. A sua convergência se deu em torno da 700
a
geração, conforme
pode ser observado na figura 5.11.
O simulated annealing contribuiu para o aumento do desempenho do algoritmo,
embora o resultado não tenha sido tão bom, apenas de 0,05% de melhoria após a execução
do simulated annealing.
Novamente o desempenho online esta muito próximo do desempenho offline, o que
pode indicar pouca variedade na população, talvez com o ajuste das probabilidade de
mutação e de crossover o resultado pudesse ter sido melhorado.
Seu desempenho, considerando a busca local foi 1,56% pior que o PBIL com
simulated annealing, que foi o melhor algoritmo evolutivo nesta dissertação para este
problema e 1,39% pior que a nuvem de partículas com busca local, melhor algoritmo de
inteligência coletiva para este problema.
66
0
0,1
0,2
0,3
0,4
0,5
0,6
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.11 Convergência do algoritmo genético aplicado a minimização da massa da mola.
O algoritmo PBIL utilizando o simulated annealing foi o que obteve o melhor
resultado para a resolução deste problema, a população convergiu por volta da 200
a
geração
(figura 5.12), e melhorou 2 dos resultados apresentados no estudo de caso, tanto o resultado
obtido por Coello (2000) como o resultado obtido por Arora (1989) foram superados em
0,21% e 0,41%, respectivamente, e foi superado por Hu et al. (2003) e Ray e Liew (2003)
em 0,009% e 0,007%, respectivamente. Lembrando que no problema do vaso de pressão
este algoritmo foi o que apresentou o pior desempenho.
Ao realizar a comparação com o algoritmo de nuvem de partículas com busca local,
que foi o melhor algoritmo de inteligência coletiva para este problema nesta dissertação, o
desempenho do PBIL com simulated annealing foi 0,23% melhor. Este foi o único caso em
que o algoritmo evolutivo apresentou um resultado melhor a um dos algoritmos de
inteligência coletiva.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
67
0
0,1
0,2
0,3
0,4
0,5
0,6
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.12 Convergência do PBIL aplicado a minimização da massa da mola.
Por volta da 500
a
geração começou a convergência do algoritmo de programação evolutiva
(figura 5.13). O seu desempenho foi intermediário para a resolução deste problema, embora
o simulated annealing tenha contribuído bastante com o resultado do algoritmo nas
primeiras gerações, seu resultado, considerando a busca local, foi 0,58% pior que o PBIL
(com SA) e 1,05% melhor que o algoritmo genético (com SA).
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.13 Convergência da programação evolucionária aplicado a minimização da mola.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
68
O algoritmo de nuvem de partículas teve melhor desempenho entre os algoritmo de
inteligência coletiva, chegando a superar o resultado obtido por Arora (1989) em 0,17%.
Seu resultado foi também 1,39% melhor que o algoritmo de colônia de bactérias, sendo
superado em 0,32%, 0,30% e 0,02% em relação a Hu et al. (2003), Ray e Liew (2003) e
Coello (2000), respectivamente.
Sua convergência iniciou a partir da 300
a
geração (figura 5.14). O simulated
annealing não propiciou nenhuma grande melhora, entretanto apresentou uma contribuição
pequena e constante ao longo das gerações.
0
0,1
0,2
0,3
0,4
0,5
0,6
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.14 Convergência da nuvem de partículas aplicado a minimização da massa da mola.
O algoritmo de colônia de bactérias foi o que apresentou o pior resultado
considerando-se apenas busca global, ao utilizar o simulated annealing o seu desempenho
se iguala ao algoritmo genético. A convergência para este problema ocorreu na 200
a
geração (figura 5.15).
Seu desempenho foi 1,39% pior que o melhor algoritmo de inteligência coletiva e
1,62% pior que o melhor algoritmo evolutivo, que é o PBIL com simulated annealing para
esta dissertação neste estudo de caso.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
69
0
0,1
0,2
0,3
0,4
0,5
0,6
147
1
0
1
3
1
6
1
9
2
2
2
5
2
8
1
0
0
4
0
0
7
0
0
1
0
0
0
geração
fitness
Desempenho online
Desempenho offline
Desempenho offline SA
Figura 5.15 Convergência da colônia de bactérias aplicado minimização da massa da mola.
A tabela 5.6 apresenta o resultado da comparação dos algoritmos implementados
para a confecção desta dissertação. Pode-se notar que os pequenos valores de desvio padrão
indicam a convergência da população em cada um dos algoritmos executados. O algoritmo
PBIL híbrido foi o que apresentou o melhor resultado para este estudo de caso, este
algoritmo também apresentou a menor Média, o que indica a melhor convergência entre
todos os algoritmos. O algoritmo de nuvem de partículas com simulated annealing obteve o
melhor resultado e também a menor média considerando-se apenas as técnicas de
inteligência coletiva.
Em todos os casos o algoritmo simulated annealing foi utilizado para realizar a
busca local e melhorou os resultados encontrados pelos algoritmos não-híbridos. Entre os
algoritmos evolutivos a melhora no desempenho foi de 0,05% para o algoritmo genético,
0,54% para o PBIL e a programação evolucionária teve um ganho de 0,36%. Para os
algoritmos de inteligência coletiva o ganho foi de 0,11% para a nuvem de partículas e
0,51% para a colônia de bactérias.
desempenho online
desempenho offline
desempenho offline SA
1 4 7 10 13 16 19 22 25 30 100 400 700 1000
geração
fitness
70
Tabela 5.6 Comparativo entre os algoritmos para o problema de minimização da massa da mola.
Algoritmo Mínimo Máximo Média Desvio Padrão
Algoritmo
Genético
0,012895 0,012943 0,012909 0,000079
Algoritmo
Genético com
SA
0,012888
0,012951 0,012912 0,000078
PBIL
0,012747
0,012799 0,12763 0,000051
PBIL
com SA
0,012678
0,012729 0,012698 0,000049
Programação
Evolucionária
0,012799
0,012861 0,012823 0,000066
Programação
Evolucionária
com SA
0,012752
0,012803 0,012776 0,000066
Nuvem de
partículas
0,012723
0,012801 0,012755 0,000059
Nuvem de
partículas com
SA
0,012708
0,012784 0,012734 0,000057
Colônia de
bactérias
0,012955
0,013002 0,012978 0,000034
Colônia de
bactérias com
SA
0,012888
0,012934 0,012903 0,000033
A tabela 5.7 mostra uma comparação entre todos os algoritmos aplicados para todos
os problemas apresentados nesta dissertação.
71
Tabela 5.7 Comparação de desempenho entre os algoritmos e os estudos de caso
Algoritmo Vaso de pressão Viga engastada Mola
Algoritmo genético 3
o
10
o
9
o
Algoritmo genético
com SA
2
o
7
o
7
o *
PBIL 10
o
6
o
4
o
PBIL com SA 9
o
5
o
1
o
Programação
evolucionária
8
o
9
o
6
o
Programação
evolucionária com
SA
6
o
8
o
5
o
Nuvem de partículas 4
o
2
o
3
o
Nuvem de partículas
com SA
1
o
1
o
2
o
Colônia de bactérias 7
o
4
o
10
o
Colônia de bactérias
com SA
5
o
3
o
8
o *
*
O desempate aconteceu na casa decimal seguinte.
72
Capítulo 6 – Conclusão e pesquisa futura
Um ponto que pode ser observado é a não alteração do desempenho online quando o
algoritmo é submetido a sua variação utilizando o simulated annealing. Este fato pode ser
explicado devido à não relevância que um único elemento teria sobre o resultado da média
global, pois o conjunto de elementos submetidos ao simulated annealing se limita ao
melhor membro de cada geração da população.
A utilização de heurísticas de algoritmos evolutivos e de inteligência coletiva está
cercada de diversas potencialidades e limitações, como o custo computacional. Sua
aplicação é útil em diversos tipos de problemas para o fornecimento de suporte à tomada de
decisão. As aplicações destas técnicas têm se expandido através de diversas áreas do
conhecimento, trazendo benefícios, economia e oferecendo uma melhor compreensão dos
problemas a que são aplicados.
Tendo em vista as potencialidades apresentadas pelos algoritmos, deseja-se no
futuro aprimorar o estudo dos algoritmos evolutivos e inteligência coletiva hoje existentes
de forma a melhorar os resultados apresentados na literatura. Outra contribuição desejada é
a apresentação de novas formas de penalizações para os algoritmos apresentados nesta
dissertação, de forma a se obter uma melhor convergência.
Para o problema do vaso de pressão, o melhor algoritmo foi o de nuvem de
partículas utilizando a busca local com o simulated annealing. Este mesmo algoritmo
também apresentou o melhor dos “piores” resultados. O menor desvio padrão foi obtido
pelo algoritmo de programação evolucionária utilizando simulated annealing.
Para o problema da viga engastada o algoritmo de nuvem de partículas utilizando o
simulated annealing apresentou o melhor resultado deste trabalho para o problema e
também os melhores valores para o “pior” dos melhores resultados, menor média e menor
desvio padrão.
Para o problema de massa da mola, o melhor resultado foi obtido pelo algoritmo
PBIL com simulated annealing, que também apresentou o melhor resultado para o “pior”
valor de resposta encontrado e a menor média. O algoritmo de colônia de bactéria
73
utilizando o simulated annealing foi o que apresentou o menor desvio padrão para o
problema.
Após a análise de todos os algoritmos espera-se ter contribuído no conhecimento
das potencialidades e limitações de cada técnica apresentada, bem como com a análise do
algoritmo de nuvem de partículas associado ao simulated annealing, que até este momento
não possuía resultado prévio na literatura consultada.
Futuramente pretende-se também analisar questões importantes, tais como: por que
uma determinada heurística possui melhor desempenho para um dado conjunto de
problemas do que as outras? Quais fatores apresentados em um problema o tornam
complexos para determinadas heurísticas? Como se pode utilizar algum dado do problema
para moldar um algoritmo mais eficiente para resolvê-lo? Na tentativa de responder a estas
questões pretende-se iniciar novas pesquisas.
74
Referências bibliográficas
Angeline, P. J. (1998) “Evolutionary optimization versus particle swarm
optimization: philosophy, and performance differences”, Evolutionary Programming VII,
pp. 601–610.
Arora, J.S. (1989) “Introduction to optimum design” New York. McGrow-Hill.
Bäck, T.; Schwefel, H. P. (1993) “An overview of evolutionary algorithms for
parameter optimization”, Evolutionary Computation, vol. 1, pp. 1-23. The MIT Press.
Baluja, S. (1994) “Population-based incremental learning: a method for integrating
genetic search based function optimization and competitive learning”, Technical Report
CMU-CS-94-163.
Bartz-Beielstein, T.; Markon, S. (2004) “Tuning search algorithms for real-world
applications: a regression tree based approach”, Evolutionary Computation, 2004. Seattle,
Washington
Carlisle, A.; Dozier G. (2001) “An off-the-shelf PSO”, Proceedings of the Particle
Swarm Optimization Workshop, pp. 1–6. Indianapolis, Indiana.
Coelho, L. dos S.; Moedinger, L. H. (2002) “Projeto e sintonia de controle PID
baseado em programação evolutiva e redes neurais”, XIV Congresso Brasileiro de
Automática, 2002, Natal, RN, p. 1-6.
Coelho, L. dos S.; Moedinger, L. H. (2003) “Algoritmo genético híbrido aplicado à
otimização de um controlador com escalonamento de ganhos”, VI Congresso Brasileiro de
Redes Neurais, 2003, São Paulo, SP.
Coello C. A. C. (2000) “Use of a self-adaptive penalty approach for engineering
optimization problems” Computers in Industry, vol. 41, no. 2, pp. 113-127.
Coello C. A. C.; Cortés, N. C. (2004) “Hybridizing a genetic algorithm with an
artificial immune system for global optimization” , Engineering Optimization, vol. 36, no.
5, pp. 607-634.
75
Christensen, S.; Oppacher, F. (2001) “What can we learn from no free lunch? A first
attempt to characterize the concept of a searchable function”, Genetic and Evolutionary
Computation Conference (GECCO), pp. 1219-1226. vol. 10, no. 3: 263-282. San Francisco,
California.
Deb, K. (1997) “GenaAS: a robust optimal design technique for mechanical
component design”, Dasgupta, D. and Michalewicz 2 (eds). Evolutionary Algorithms in
Engineering Applications Berlin, pp. 497-514.
Deb, K.; Goyal, M. (1998) “A robust optimization procedure for mechanical
component design based on genetic adaptive search” Transactions of the ASME: Journal of
Mechanical Design, vol. 120, no. 2, 162 -164.
Eberhart, R.C.; Kennedy, J (1995) “A new optimizer using particle swarm theory”,
Proceedings 6 Symposium on Micro Machine and Human Science, pp. 39-43.
Eberhart, R.C., Simpson, P. e Dobbins, R. (1996) “Computational intelligence PC
tools”. Academic Press Wilson EO Sociobiology: The New Synthesis. Belknap Press,
Cambridge.
Eberhart R. C. e Shi Y. (1998) “Comparison between genetic algorithms and
particle swarm optimization” , Evolutionary Programming VII, pp. 611–616.
Eberhart, R. C. e Shi, Y. (2001) “Tracking and optimizing dynamic systems with
particle swarms”. Proc. Congress on Evolutionary Computation 2001, Seoul, Korea.
Piscataway, NJ: IEEE Service Center. (in press)
Fogel, L. J. (1962) “Autonomous automata” , Ind. Res., vol. 4, pp. 14–19.
Goldberg, D. E. (1989) “Genetic algorithms in search, optimization, and machine
learning”, Addison-Wesley, Reading, Mass.
González, C.; Lozano, J. A.; Larrañaga, P. (2000), “Analyzing the PBIL algorithm
by means of discrete dynamical systems”, Complex Systems vol. 12, no. 4, pp.465-479.
Heppner, F.; Grenander, U. (1990) “A stochastic nonlinear model for coordinate
bird flocks”. in: Krasner The Ubiquity of Chaos. AAAS Publications, Washington, DC.
76
Holland, J. H. (1962) “Outline for a logical theory of adaptive systems,” J. Assoc.
Comput. March., vol. 3, pp. 297–314.
Hu, X.; Eberhart, R.; Shi, Y. (2003) “Engineering optimization with particle
swarm”, IEEE Conference on Swarm Intelligence, Indianapolis, Indiana.
Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (1983) “Optimization by simulated
annealing”, Science, vol. 220, no. 4598, pp. 671-680.
Lange, S.; Riedmiller, M. (2004) “Evolution of computer vision subsystems in robot
navigation and image classification tasks” in RoboCup-2004: Robot Soccer World Cup
VIII, Lisboa, Portugal.
Lechuga, M. S. (2002) “Resolución de problemas multi-objetivo a través de
optimización mediante cúmulos de partículas” Master's Thesis, Maestría en Inteligencia
Artificial, Universidad Veracruzana, Xalapa, Veracruz, México.
Martin, P. (2002) “A pipelined hardware implementation of genetic programming
using FPGAs and Handel-C”, Eurogp, Kinsale, Ireland.
Merlot, L. T. G.; Boland, N.; Hughes, B. D.; Stuckey, P. J. (2002) “A hybrid
algorithm for the examination timetabling problem”, PATAT, Gent, Belgium.
Michalewicz, Z e Schoenauer, M; (1996) “Evolutionary algorithms for constrained
parameter optimization problems”, Evolutionary Computation, vol. 4, no. 1, pp 32-42.
Millonas, M. M. (1994) “Swarms, phase transitions, and collective intelligence” in:
Computational Intelligence: A Dynamic System Perspective, pp. 137–151.
Parsopoulos, K. E.; Vrahatis, M. N. (2002) “Particle swarm optimization method for
constrained optimization problems”, Proceedings of the Euro-international Symposium on
Computational Intelligence, Koçice – Slovakia.
Passino, K.M. (2002) “Biomimicry of bacterial foraging for distributed optimization
and control”, IEEE Control Systems Magazine, vol. 22, no. 3, pp. 52-67.
Radi, A. M.; Poli, R. (1997) “Neuro-Symbolic and Neural Networks with Parallel
Distributed Genetic Programming” , 3rd International Conference on Artificial Neural
Networks and Genetic Algorithms, pp. 419-423, Norwich, UK.
77
Ray, T; Liew, K. M. (2003) “Society and civilization: na optimization algorithm
based on simulation of social behavior”. IEEE Transactions on Evolutionary Computation
vol. 7, no. 4, pp. 386-396.
Rechenberg, I. (1973) “Evolutionsstrategie: optimierung technischer systemenach
prinzipien der biologischen evolution”. Stuttgart, Germany: Frommann-Holzboog.
Reynolds, C. W. (1987) “Flocks, herds, and schools: a distributed behavioral
model”. Computer Graphics vol. 21, no. 4, pp 25–34.
Rowe, C.; Maciejowski, J. (2003) “Min-max moving horizon estimation for a class
of hybrid systems” IEEE xplore, vol.1, pp.149- 154.
Saramago, S. F. P. (2003) “Métodos de otimização randômica: algoritmos genéticos
e simulated annealing”, Minicurso do XXVI CNMAC, São José do Rio Preto.
Shi, Y.; Eberhart R. C. (1998) “A modified particle swarm optimizer”. Proceedings
of the IEEE Conference on Evolutionary Computation. Anchorage, Alaska.
Stephens, D.; Krebs; J. (1986) “Foraging theory”, Princeton, NJ: Princeton Univ.
Press.
Streichert, F.; Stein, G.; Ulmer, H.; Zell, A. (2003) “A clustering based niching
method for evolutionary algorithms” Center for Bioinformatics Tubingen, University of
Tubingen, Germany.
Ursem, R. K. (2003) “Models for evolutionary algorithms and their applications in
system identification and control optimization”, PhD Thesis. Department of Computer
Science, University of Aarhus, Denmark.
Wachowiak, M. P; Smolkov, R.; Zheng, Y.; Zurada, J. M.; Elmaghraby, A. S.
(2004) “An approach to multimodal biomedical image registration utilizing particle swarm
optimization” IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, pp. 289-301.
Wolpert, D. H.; Macready W, G. (1995) “No free lunch theorems for search”,
Technical Report: Santa Fe Institute. USA.
Yao, X.; Liu, Y.; Lin, G. (1999) “Evolutionary programming made faster” IEEE
Transactions on Evolutionary Computation, vol. 3, no. 2, pp.82-102.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
