Download PDF
ads:
AVALIAÇÃO COMPARATIVA DE ALGORITMOS EVOLUTIVOS COM
OPERADORES ADAPTATIVOS
Paulo Terra Matias
DISSERTAÇÃO SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS
PROGRAMAS DE PÓS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS
NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM
ENGENHARIA CIVIL.
Aprovada por:
________________________________________________
Prof. Alexandre Gonçalves Evsukoff, Dr.
________________________________________________
Prof
a
Beatriz de Souza Leite Pires de Lima, D.Sc.
________________________________________________
Prof. Breno Pinheiro Jacob, D.Sc.
________________________________________________
Prof. Afonso Celso de Castro Lemonge, D.Sc.
________________________________________________
Prof. Carl Horst Albrecht, D.Sc.
RIO DE JANEIRO, RJ – BRASIL
JUNHO DE 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ii
MATIAS, PAULO TERRA
Avaliação Comparativa de Algoritmos
Evolutivos com Operadores Adaptativos
[Rio de Janeiro] 2008.
VII, 56 p. 29,7 cm (COPPE/UFRJ,
M.Sc., Engenharia Civil, 2008)
Dissertação - Universidade Federal do
Rio de Janeiro, COPPE
1. Algoritmos Evolutivos
2. Algoritmo Genético Adaptativo
3. Otimização
I. COPPE/UFRJ II. Título (série).
ads:
iii
Dedico à minha esposa Denize,
ao meu irmão Manuel e ao meu
sobrinho Daniel.
iv
Agradecimentos
À minha esposa Denize pelo apoio e compreensão durante os últimos meses de
dedicação à dissertação. Ao meu irmão Manuel e ao meu sobrinho Daniel pela
compreensão de minhas ausências e pelo apoio.
À minha orientadora Beatriz de S. L. P. Lima por ter acreditado em mim e pela
paciência com as minhas dúvidas.
À minhas chefas Maria das Graças, Marcela Neiva e Sinara por permitir assistir às aulas
durante o expediente de trabalho na FINEP, EDS e Petrobrás respectivamente.
A todos os professores que me capacitaram a chegar até aqui.
A todos os funcionários da Secretaria Acadêmica do Programa de Engenharia Civil da
COPPE/UFRJ por me ajudar em toda a burocracia necessária.
A COPPE/UFRJ pela estrutura do excelente programa de pós-graduação de engenharia.
A meus pais que devem estar muito felizes.
v
Resumo da Dissertação apresentada à COPPE/UFRJ como parte dos requisitos
necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)
AVALIAÇÃO COMPARATIVA DE ALGORITMOS EVOLUTIVOS COM
OPERADORES ADAPTATIVOS
Paulo Terra Matias
Junho/2008
Orientadora: Beatriz de Souza Leite Pires de Lima
Programa: Engenharia Civil
Os algoritmos evolutivos tem demonstrado grande eficiência em vários
problemas de otimização, porém, devem ser fixados vários parâmetros e operadores que
definem seu desempenho ao longo da busca. A escolha destes parâmetros, baseada
principalmente na experiência do especialista e também empiricamente, é feita no início
dos experimentos. O controle dos parâmetros durante a execução do algoritmo é
interessante porque permite um ajuste automático enquanto o problema é resolvido.
Nesta dissertação, emprega-se uma técnica de adaptação automática dos principais
operadores dos Algoritmos Genéticos baseada no desempenho do algoritmo e na
distribuição dos indivíduos da população no espaço de busca. A técnica estudada
permite ao Algoritmo Genético ajustar o valor dos operadores de forma a privilegiar
aqueles que podem produzir resultados melhores em um determinado momento da
busca. A avaliação da eficiência da técnica estudada e feita através de testes
comparativos em funções de benchmark assim como numa aplicação real de engenharia
que trata da otimização de sistemas de risers utilizados em exploração de petróleo
offshore.
vi
Abstract of Dissertation presented to COPPE/UFRJ as a partial fulfillment of the
requirements for the degree of Master of Science (M.Sc.)
BENCHMARKING OF ADAPTATIVE OPERATORS ON EVOLUTIONARY
ALGORITHMS
Paulo Terra Matias
June/2008
Advisor: Beatriz de Souza Leite Pires de Lima
Department: Civil Engineering
The evolutionary algorithms have shown great efficiency in a number of
optimization problems. However, various parameters and operators should be set to
define their performance during the search. The choice of these parameters based
mainly on the experience of specialist and also empirically, is made at the beginning of
the experiments. The parameters controlling during the algorithm run is interesting
because it allows an automatic adjustment while the problem is solved. In this
dissertation, an automatic adjustment technique of the Genetic Algorithms main
operators is applied, based on the performance of the algorithm and the distribution of
population individuals in the search area. The studied technique allows the genetic
algorithm adjust the operators values so as to favor those who can produce better results
in a specific search moment. The efficiency evaluation of the technique is made by
comparative benchmark function tests so as on a real engineering application that deals
with the risers systems optimization used in offshore oil exploitation.
vii
ÍNDICE
Capítulo 1: Introdução ................................................................................................... 1
1.1 – Contexto .............................................................................................................. 1
1.2 – Motivação ............................................................................................................ 2
1.3 – Objetivo ............................................................................................................... 3
1.4 – Organização do Trabalho ................................................................................... 4
Capítulo 2: Algoritmos Genéticos Clássicos e Adaptativos ........................................ 5
2.1 – Introdução ........................................................................................................... 5
2.2 – O Algoritmo ......................................................................................................... 5
2.3 – Algoritmo Genético Adaptativo .......................................................................... 9
Capítulo 3: Otimização por Enxame de Partículas - PSO ........................................ 12
3.1 – Introdução ......................................................................................................... 12
3.2 – A Evolução do algoritmo .................................................................................. 13
3.3 – Comparação ...................................................................................................... 16
Capítulo 4: AG com taxas adaptativas ....................................................................... 17
4.1 – Introdução ......................................................................................................... 17
4.2 – Estratégia de Adaptação ................................................................................... 19
4.2.1 – Cálculo do valor de bff ............................................................................. 19
4.2.2 – Cálculo do valor de sucesso de um operador ......................................... 21
4.2.3 – Cálculo do valor de diversidade de um operador .................................. 22
4.2.4 – Adaptação da taxa dos operadores ......................................................... 23
Capítulo 5: Ferramenta computacional de otimização: PROGOTIM .................... 26
5.1 – Introdução ......................................................................................................... 26
5.2 – Modelos de Otimização ..................................................................................... 26
5.3 – Acompanhamento da Evolução ....................................................................... 30
5.4 – Modelo de Sistemas de Risers ......................................................................... 31
5.4.1 – Introdução ................................................................................................. 31
5.4.2 – Representação matemática ...................................................................... 33
Capítulo 6: Adaptação do PROGOTIM ..................................................................... 35
6.1 – Introdução ......................................................................................................... 35
6.2 – Operador de Mutação Gaussiana .................................................................... 35
6.3 – Separação dos Operadores ............................................................................... 36
6.4 – Aumento do Vetor de Indivíduos ...................................................................... 37
6.5 – Criação dos Medidores de Sucesso e Diversidade ........................................... 37
6.6 – Comparação de Resultados .............................................................................. 37
6.7 – Alteração da Contagem de Número de Avaliações ......................................... 38
Capítulo 7: Estudo de casos ......................................................................................... 39
7.1 – Parâmetros dos Algoritmos .............................................................................. 39
7.2 – Descrição das Funções ..................................................................................... 41
7.2.1 – De Jong F1 ................................................................................................. 41
7.2.2 – Rosenbrock ................................................................................................ 41
7.2.3 – Rastrigin .................................................................................................... 42
7.2.4 – Griewank ................................................................................................... 42
7.2.5 – Riser ........................................................................................................... 43
7.3 – Resultados ......................................................................................................... 45
Capítulo 8: Conclusão .................................................................................................. 51
8.1 – Comentários gerais ........................................................................................... 51
8.2 – Trabalhos Futuros ............................................................................................ 51
Capítulo 10: Referências Bibliográficas ..................................................................... 53
1
Capítulo 1: Introdução
1.1 – Contexto
O problema de otimização de uma função consiste em encontrar um
ponto que maximize ou minimize seu valor. Há muitas técnicas possíveis para
resolver problemas de otimização, e algumas delas incluem métodos exatos e
eficientes de resolução. Porem, estes métodos se aplicam quando o problema é de
baixa complexidade. Em alguns problemas, é possível obter o ponto máximo ou
mínimo de uma função, também conhecido como ponto ótimo, utilizando métodos
de busca onde todo o espaço é investigado. São os chamados métodos de Busca
Exaustiva. Em outros casos, em funções mais complexas, mas que sejam contínuas e
diferenciáveis, é possível obter o ponto ótimo através do cálculo de suas derivadas.
Porém, dependendo da complexidade do problema, nem sempre é viável
encontrar as variáveis que geram este valor ótimo e atendam às restrições do
problema, pois seu custo pode ser muito alto. Em geral são problemas de
engenharia, com grandes espaços de busca, que não são contínuos, não são lineares
ou não diferenciáveis. Nestes casos não é viável a utilização de métodos exatos, pois
sua complexidade é alta, e nem é possível encontrar sua derivada.
Uma alternativa interessante para estes casos são os métodos heurísticos
de otimização onde não garantem que o ponto ótimo seja encontrado, mas
encontram uma boa solução que resolva o problema, em tempo razoável e a um
custo computacional não proibitivo. Estes métodos fazem parte de uma grande área
de pesquisa chamada Inteligência Computacional, e também de uma sub-área
chamada de Métodos computacionais inspirados na natureza, que incluem os
Algoritmos Genéticos [1], Estratégias Evolutivas (Rechenberg e Schwefel, 1975),
Inteligência Coletiva [2] [17], Sistemas Imunológicos Artificiais [3], etc. Estes
métodos podem ser considerados como algoritmos evolutivos pois um grupo de
agentes evoluem dentro de um espaço de busca. Cada algoritmo tem uma
característica própria para essa evolução, que segue uma inspiração biológica ou
natural.
2
Dentre os algoritmos evolutivos, o mais conhecido é, provavelmente, o
Algoritmo Genético que é baseado na teoria da evolução de Charles Darwin [4].
O trabalho de otimização de um problema utilizando um Algoritmo
Genético (AG) clássico passa pela configuração dos seus operadores, que é uma
importante etapa no processo de configuração do algoritmo na busca por uma
solução ótima. Esta configuração pode determinar se o AG é capaz de apresentar
uma solução satisfatória ou não. Porém esta importante etapa é, muitas vezes,
baseada em conhecimento empírico ou na semelhança entre o problema atual e
algum já resolvido no passado. Além disso, os parâmetros, uma vez estabelecidos,
permanecem os mesmos ao longo de todo o processo de busca. Dependendo do
problema a ser resolvido, um operador que é importante em um determinado estágio
da busca, não tem o mesmo desempenho em um outro estágio ou mesmo em um
outro problema.
Os métodos estudados nesta dissertação são o AG clássico e uma
variação deste que incorpora melhorias no desempenho do algoritmo, e outro
método bio-inspirado que faz parte do grupo de algoritmos de Inteligência Coletiva,
o Particle Swarm Optimization.
1.2 – Motivação
Em um AG clássico a população inicial é gerada aleatoriamente e sua
distribuição no espaço de busca pode ser classificada como dispersa. Com o passar
das gerações os indivíduos tendem a possuir características semelhantes a partir do
operador de crossover (cruzamento) tendendo a se aproximar de seus pais. Como os
melhores indivíduos têm mais chance de passar para as próximas gerações e de se
reproduzirem, este comportamento leva a explotação de um ótimo local nas
redondezas do melhor indivíduo. É possível dizer então que, o operador crossover é
importante no momento em que a população está dispersa e existe um ótimo local
ainda não alcançado.
Quando se atinge este ótimo local, ou próximo dele, os indivíduos
tendem a se tornar semelhantes entre si em termos de valores e conseqüentemente
de aptidão (fitness) e a população tende a convergir para um ponto. Neste momento
é mais interessante para a otimização que outras regiões sejam exploradas, pois esta
3
se encontra mapeada. Neste momento é fácil perceber que o operador de mutação
passa a ter uma importância maior que o operador de crossover na busca do ótimo
global.
Supondo que nas gerações seguintes uma modificação efetuada pelo
operador mutação seja bem sucedida, um novo individuo é gerado em algum ponto
do espaço de busca com fitness maior que a média dos outros indivíduos da
população. Neste momento passa a ser mais importante (novamente) que haja troca
genética, entre todos os indivíduos e este novo melhor, para que toda a população se
desloque para este novo ponto e o explore. Por esta abordagem, a busca do ótimo se
torna uma alternância entre a explotação da região local e a exploração em busca de
novas regiões promissoras.
Em um AG clássico esta mudança de necessidade do processo de busca
não é atendida, pois não há mudança nas taxas dos operadores durante a otimização.
1.3 – Objetivo
A proposta deste trabalho é criar sensores que identifiquem as
características da população, descritas acima, e ajustar as taxas dos operadores na
direção correta para aumentar as chances de gerar indivíduos melhores. Ela foi
baseada na técnica de adaptação dos parâmetros do AG descrita em [5] chamada
AORCEA (Adaptive Operator Rate Controlled Evolutionary Algorithm).
O programa utilizado para aplicar esta técnica é o Progotim que é um
programa de otimização de configurações de sistemas de risers desenvolvido por
Albrecht [6].
Os resultados desta técnica são comparados com um AG clássico e com
PSO (Particle Swarm Optimization – Otimização por Enxame de Partículas). As
funções utilizadas para comparação são funções de benchmark conhecidas e o
próprio problema de otimização de configurações de sistemas de risers que trata de
uma aplicação real de um problema complexo de engenharia na área da indústria do
petróleo. Todas as funções já se encontram implementadas no Progotim.
4
1.4 – Organização do Trabalho
O capítulo dois apresenta o Algoritmo Genético clássico, com suas
terminologias e operadores. Também são abordadas neste capítulo as classificações
dos Algoritmos Genéticos adaptativos.
O capítulo três faz uma breve apresentação da Otimização por Enxame
de Partículas – PSO, que é utilizada para comparar os resultados deste trabalho.
O capitulo quatro trata em detalhes a técnica de adaptação dos
operadores genéticos que foi implementada neste trabalho.
O quinto capítulo descreve o programa que foi objeto de modificação
deste trabalho (PROGOTIM) para a implementação do AG com taxas adaptativas.
No capítulo seis, são apresentadas as modificações realizadas no
programa para a implementação da técnica adaptativa. Também são narradas
algumas dificuldades durante o processo.
Os resultados dos testes são apresentados e comentados no capitulo sete.
Também neste capítulo são apresentadas as configurações utilizadas nos algoritmos
para a realização dos testes.
Os comentários sobre os resultados obtidos neste trabalho são
apresentados no capítulo oito assim como os possíveis trabalhos futuros que podem
ser realizados utilizando a técnica apresentada.
5
Capítulo 2: Algoritmos Genéticos Clássicos e
Adaptativos
2.1 – Introdução
Os Algoritmos Genéticos (AG) são métodos de otimização inspirados na
teoria da seleção natural dos indivíduos mais adaptados ao ambiente que foi
desenvolvida por Charles Darwin. Suas premissas são baseadas na evolução de uma
população através da reprodução, cruzamento (crossover) e mutação de seus
indivíduos [7].
A otimização de problemas complexos muitas vezes não tem como
objetivo a busca pelo ótimo global, mas sim um equilíbrio entre o custo da busca e
um ótimo satisfatório para o problema a ser resolvido. Algumas técnicas de
otimização, tais como derivada, programação linear e não linear, são capazes de
atender a esta necessidade para um grupo de problemas com características
específicas que contenham linearidade, que sejam diferenciáveis e haja
continuidade. Porém, para os diversos problemas de engenharia, que não contém
linearidade, continuidade ou não são diferenciáveis, essas técnicas se tornam
proibitivas devido ao seu custo computacional.
O sucesso do AG está justamente em sua robustez na solução de
problemas (com muitas variáveis, não lineares ou não diferenciáveis), em sua
flexibilidade de aplicação nos mais diversos problemas e na sua simplicidade de
entendimento e aplicação.
2.2 – O Algoritmo
Para a melhor compreensão do algoritmo implementado nesta dissertação
é necessária a apresentação da nomenclatura utilizada pelos Algoritmos Genéticos
clássicos. Esta terminologia é muito empregada na literatura e os aspectos principais
são listados a seguir assim como um breve resumo do funcionamento do algoritmo.
• Indivíduo – elemento da população que contém informação
referente a uma solução possível dentro do espaço de busca;
6
• População – conjunto de indivíduos;
• Crossover – operador genético responsável pelo cruzamento
(reprodução) entre dois indivíduos onde ocorre a troca de parte de
uma informação genética (parte de uma solução possível) entre
ambos gerando dois novos indivíduos;
• Mutação – operador genético que altera um indivíduo (altera a
solução representada por ele);
• Seleção – operador genético que seleciona os melhores
indivíduos (aqueles que possuem as melhores soluções para o
problema);
• Fitness – grau atribuído ao indivíduo que representa sua
capacidade de resolver o problema a ser otimizado. É utilizado
para a comparação entre os indivíduos e para a escolha dos
melhores para a reprodução (crossover);
• Geração – intervalo entre as aplicações dos operadores
genéticos. Também é atribuído ao conjunto de indivíduos que faz
parte da mesma iteração do algoritmo;
A figura 1 apresenta o fluxo básico de um AG. Inicialmente uma
população aleatória é gerada. Em seguida cada indivíduo é avaliado para que o
algoritmo entre no ciclo. Após a avaliação do critério de parada há o sorteio dos
indivíduos para a aplicação do operador crossover. Os indivíduos melhor adaptados
possuem maior chance de serem selecionados. Em seguida há um sorteio dos
indivíduos que serão modificados pelo operador de mutação. Após a aplicação dos
operadores é gerada uma população intermediária. Este novo grupo de indivíduos
será avaliado e os melhores serão selecionados para a próxima geração. O ciclo se
repete até que o critério de parada seja alcançado. Este critério pode ser o número de
gerações ou a diminuição da evolução da população.
7
Figura 1 – Fluxo de um AG básico
Neste trabalho foram utilizados os seguintes tipos de operadores de
crossover e mutação:
• Crossover de um ponto – Selecionam-se dois pais. Sorteia-se um
gen do cromossomo de ambos onde será trocada a informação
genética entre eles. Em seguida toda a informação genética
contida a partir deste gene (todos os alelos até o fim do
cromossomo) é concatenada com a parte inicial do outro
indivíduo pai. Desta forma são gerados dois novos indivíduos a
partir da informação genética dos pais originais.
• Crossover uniforme – O processo é semelhante ao crossover de
um ponto, porém não só uma, mas várias partes dos
cromossomos originais são trocadas entre si.
Gerar População Inicial
Crossover
Mutação
Seleção
Nova População
Avaliação dos Indivíduos
Parar?
Início
Fim Sim
Não
Avaliação dos Indivíduos
8
• Mutação uniforme – Após o sorteio do indivíduo que sofrerá a
mutação, o alelo que será modificado é sorteado. Em seguida o
novo valor do alelo é escolhido por um sorteio aleatório dentro da
faixa de valores possíveis que este alelo pode ter.
• Mutação gaussiana – O processo é semelhante à mutação
uniforme, porém o sorteio do novo valor para o alelo é feito
através de uma distribuição normal entre os valores que o alelo
pode assumir.
Durante o processo de busca os operadores atuam na modificação da
população de forma distinta. Enquanto um operador pode promover a busca de uma
solução ótima próximo dos melhores indivíduos (explotação) outro operador pode
beneficiar a busca em outras regiões distantes da região explorada pela população
(exploração). Estes dois operadores atuam com uma determinada taxa de ocorrência
ou probabilidade. Esta taxa é usualmente escolhida empiricamente ou seguindo
algumas sugestões de publicações anteriores.
A escolha destes parâmetros, probabilidades dos operadores, já tem sido
objeto de estudo em diversos artigos [8], [9] e [10]. Alguns estudos levaram a
conclusão que a probabilidade de crossover deve ser alta, entre 0,6 e 0,9. Já a
probabilidade de mutação deve ser baixa, assim como é na natureza, entre 0,001 e
0,01 ou 1 / comprimento do cromossomo. Porém, durante o processo de busca da
solução ótima a população pode apresentar (e efetivamente apresenta) características
distintas. Estas características baseiam-se na disposição de seus indivíduos no
universo de busca.
Por exemplo, durante as gerações iniciais, quando a disposição da
população ainda sofre influência forte da geração aleatória inicial dos indivíduos,
estes se encontram espalhados no universo de busca. Conforme as gerações vão se
sucedendo, e a troca de informação genética entre eles vai ocorrendo (através do
operador crossover), os indivíduos tendem a se tornar parecidos em torno dos
melhores indivíduos devido ao benefício que estes possuem na seleção para as
futuras gerações. Esse processo faz com que a busca comece a se concentrar em um
ponto, em busca do ótimo nas redondezas. Enquanto isso, as mutações genéticas
(operador mutação) que ocorrem aleatoriamente tendem a levar alguns indivíduos
9
para outras regiões em busca de algum ponto promissor. Se esse novo indivíduo
gerado em uma região distante do grupo for realmente promissor e for selecionado
para gerações futuras, outros indivíduos serão gerados nessa região através do
crossover.
É fácil perceber que em alguns momentos do processo de busca, um
operador tenha melhor desempenho que outro, dependendo da necessidade atual da
população (explorar novas regiões ou chegar ao topo ou fundo da região atual).
Considerando este aspecto, as probabilidades dos operadores
produziriam melhores resultados se fossem modificadas ao longo do processo de
busca de forma a otimizar o próprio processo. Esta abordagem levou ao estudo dos
Algoritmos Genéticos Adaptativos que será visto em detalhes a seguir.
2.3 – Algoritmo Genético Adaptativo
Para um Algoritmo Genético resolver um problema é necessário
selecionar entre algumas estratégias e configurar uma série de parâmetros. Essa
configuração é decisiva para o desempenho do algoritmo na busca da solução ótima.
Essas escolhas são feitas, em geral, a partir de dados empíricos baseados em
experiências anteriores. Além disso, os operadores e suas probabilidades são
escolhidos antes do início do processo de otimização e permanecem inalteradas até o
fim deste. Mesmo utilizando a experiência de problemas anteriores e a semelhança
entre os diversos problemas de otimização, para determinar o valor dos parâmetros a
serem utilizados, não foi possível, até o momento, chegar a um conjunto de valores
que se aplique a todos os tipos de problemas. Por estas razões, adaptar os parâmetros
do AG durante sua execução é uma área promissora para melhorar o desempenho da
otimização durante a busca.
Existem várias classificações para a adaptação que pode ocorrer durante
a execução de um algoritmo. A seguir são apresentadas algumas delas:
Angeline [11] classificou a adaptação quanto ao nível em que a mesma
atua:
10
• População – Adapta parâmetros que influenciam diretamente a
população e a distribuição dos indivíduos nas gerações seguintes.
Alguns exemplos são a ‘regra de sucesso 1/5 ’ de Rechenberg
[12] e as técnicas baseadas no sucesso e produtividade dos
operadores tais como as de Kakazu Y, Sakanashi H, Suzuki K
[13] e Freisleben [14]. Algumas técnicas que ajustam o tamanho
da população durante a execução do AG também são
classificadas como adaptação no nível de população.
• Indivíduo – São técnicas que possuem parâmetros diferentes
para cada indivíduo e que determinam como este será
modificado. Bäck [15] investigou a técnica de acrescentar bits
representando a taxa de mutação do indivíduo ao genótipo do
mesmo.
• Componente – Esta técnica consiste em associar a cada
componente de cada indivíduo um parâmetro que determina
como será sua mudança ao longo das gerações. Tanto o
componente quanto o valor do parâmetro associado a ele sofrem a
evolução do algoritmo. Bäck [15] também utilizou esta técnica
em sua pesquisa ao associar o valor de probabilidade de mutação
para cada componente de cada indivíduo.
Outra forma de classificação de adaptação de Algoritmos Genéticos foi
proposta por Angeline [11] que considera os quatro aspectos a seguir:
• O que é alterado – Representação, função de avaliação,
operadores genéticos, taxas dos operadores, seleção, substituição,
tamanho da população, etc.
• Como é alterado – Mecanismo de atualização determinístico,
adaptativo, ou auto-adaptativo.
• Em que nível é alterado - Nível de população, indivíduo ou
componente (de acordo com a classificação quanto ao nível).
• Em qual evidência a mudança é baseada - Desempenho dos
operadores, diversidade da população.
11
A classificação de como o AG é alterado merece uma explicação mais
detalhada:
• Determinístico – Determina a alteração do AG sem nenhuma
avaliação do estado da busca. Em [16] foi investigada a alteração
do parâmetro de mutação de forma decrescente em função do
número de gerações.
• Adaptativo – Sua adaptação é baseada em informações extraídas
da situação da população e do processo de busca. A direção e a
magnitude da alteração dependem estado da busca no momento
da alteração.
• Auto-adaptativo – Nesta estratégia, os parâmetros do AG são
codificados junto com a população e sofrem o processo de
evolução, assim como os indivíduos da população.
A estratégia desenvolvida neste trabalho, emprega a abordagem
apresentada em [5], denominada AORCEA (Adaptive Operator Rate Controlled
Evolutionary Algorithm). Esta abordagem é classificada como Adaptativa, no nível
da população e baseada no desempenho dos operadores.
12
Capítulo 3: Otimização por Enxame de
Partículas - PSO
3.1 – Introdução
A otimização por Enxame de Partículas ou PSO (Particle Swarm
Optimization), desenvolvida por Kennedy e Eberhardt [17], é uma técnica de
computação evolutiva inspirada no comportamento social de uma população de
indivíduos. Eles se basearam em simulações computacionais feitas sobre o vôo de
pássaros em busca de comida ou de um local de pouso. O objetivo desses estudos
era compreender como os indivíduos se interagem durante o vôo, apresentando uma
forma compacta e sincronizada.
PSO, apesar de recente, tem sido bastante estudada por ser robusta, fácil
de implementar e possuir custo computacional baixo.
Assim como Algoritmo Genético, PSO é baseado em uma população que
representa possíveis soluções em um espaço de busca. Porém, ao invés de gerações,
a evolução dos indivíduos se dá através de iterações onde cada partícula se
movimenta pelo espaço de busca. Da mesma forma como observado na natureza,
sua movimentação pelo espaço de busca é influenciada pelo próprio indivíduo e pelo
bando.
Também como Algoritmo Genético, as partículas são avaliadas por uma
função de fitness que lhes confere uma forma de comparar as diversas soluções
representadas por eles. Cada partícula armazena a posição de seu melhor fitness
histórico.
A função original formulada por Kennedy e Eberhardt [17] propôs que a
posição de uma partícula (que é um vetor que representa sua solução no espaço de
busca) fosse o resultado da posição anterior somada a sua velocidade atual. Já a
velocidade atual seria influenciada por três fatores: a velocidade anterior da
partícula, a força que leva a partícula de volta ao melhor lugar já visitado por ele e a
força que a leva ao melhor lugar já visitado por todo o grupo.
Kennedy e Eberhardt [17] formularam então as expressões a seguir (1)
que representam o método. Cada número aleatório, que varia de 0 a 1, é
multiplicado por 2 para que sua média seja 1:
13
x
i+1 =
x
i
+ v
i+1
v
i+1
= v
i
+ rnd() * 2 * (gbest - x
i
) + rnd() * 2 * (xbest - x
i
) (1)
Onde:
x = posição da partícula
v = velocidade da partícula
rnd() = número aleatório com intervalo [0,1]
gbest = melhor ponto já visitado pelo grupo
xbest = melhor ponto já visitado pela partícula
i = iteração atual
3.2 – A Evolução do algoritmo
A expressão (1) apresentou bons resultados em algumas funções de
benchmark [17], porém algumas melhorias foram propostas. Para evitar que a
velocidade das partículas crescesse indefinidamente, Kennedy e Eberhardt [18]
propuseram limitar a velocidade máxima da partícula à máxima variação da
variável. Esta modificação evita que a partícula acelere indefinidamente saindo do
espaço de busca.
Outra modificação foi proposta por Eberhardt e Shi [19]. Ao observarem
a necessidade de equilíbrio entre a busca local e a busca global, propuseram o
acréscimo de um peso de inércia chamado w que atua na velocidade atual da
partícula. A nova expressão é mostrada abaixo:
x
i+1 =
x
i
+ v
i+1
v
i+1
= w * v
i
+ rnd() * 2 * (gbest - x
i
) + rnd() * 2 * (xbest - x
i
) (2)
Onde:
w = inércia da partícula
Em [20] os testes mostraram que os melhores valores de inércia estão
entre 0,9 e 1,2. Porém, os melhores resultados foram obtidos com a inércia variando
linearmente de 1.4, no início da iteração até zero no fim da iteração. Esta alteração
14
possibilita eliminar o limitador de velocidade da partícula. Outra opção para esta
modificação é a inércia com uma variação não-linear [21] em função das iterações
conforme a função (3). Da mesma forma que a variação linear, a inércia também
diminui com o passar das iterações, porém de forma não-linear.
finfinini
n
n
www
N
tN
tw +−
−
= )(*
)(
)( (3)
Onde:
w=inércia
t = iteração corrente
N = número máximo de iterações
n = expoente de não-linearidade
w
ini
= inércia inicial
w
fin
= inércia final
Eberhardt e Shi [19] compararam o uso de constrição em lugar da
inércia.
x
i+1 =
x
i
+ v
i+1
v
i+1
= K * [ v
i
+ rnd() * c
1
* (gbest - x
i
) + rnd() * c
2
* (xbest - x
i
)] (4)
ϕϕϕ
42
2
2
−−−
=K onde 4,
21
>+=
ϕϕ
cc (5)
O fator de constrição é um caso particular da inércia quando K = w e
4,
21
>+=
ϕϕ
cc . Os resultados mostraram que utilizando o valor de constrição e
limitando a velocidade ao valor máximo da variável o desempenho do algoritmo
melhora muito.
A influência da população de partículas também foi estudada em [22]
que propôs uma influência local para as partículas chamada de Local Particle Swarm
Optimization. A diferênça está na referência que cada partícula tem do melhor lugar
visitado pelo grupo. Nesta proposta cada partícula é influenciada por um número L
15
de partículas próximas. Isto provoca subgrupos de busca de partículas no espaço de
busca.
Um outro modelo proposto para melhorar o desempenho do PSO feita
em [23] é um modelo híbrido de PSO e AG onde, a cada intervalo de iterações,
ocorre um cruzamento (crossover) entre as melhores partículas. A substituição das
antigas partículas pelas novas se dá por um fator acrescido chamado probabilidade
de morte que aumenta com o passar das iterações. Desta forma, as partículas mais
antigas e com menor fitness possuem maior chance de serem substituídas pelas
novas.
Uma outra abordagem é a congregação passiva desenvolvida em [24] que
mantém o grupo coeso. A congregação é uma atração que o indivíduo possui pelo
grupo. Ela é dada pelo acréscimo de mais um termo como mostrado abaixo:
c
3
* rnd() * (R - x
i
) (6)
Onde R é uma partícula escolhida aleatoriamente no grupo e c
3
é um
coeficiente de congregação.
Uma melhoria deste método também desenvolvida em [24] é a atração
social que usa, ao invés de uma partícula escolhida aleatoriamente, usa o centro de
massa do grupo:
c
3
* rnd() * (C - x
i
) (7)
onde
∑
∑
=
=
=
N
j
j
N
j
jj
f
xf
C
1
1
(8)
16
3.3 – Comparação
O PSO, apesar de ser uma técnica recente, foi escolhido por apresentar
ótimos resultados em problemas de otimização de funções contínuas. A expressão
utilizada no programa desenvolvido por Albrecht [6] é apresentada a seguir:
x
i+1 =
x
i
+ v
i+1
v
i+1
= w
i
* v
i
+ rnd() * c
1
* (gbest - x
i
) + rnd() * c
2
* (xbest - x
i
) + rnd()
* c
3
* (Cm - x
i
) (9)
Onde:
w
i
= Inércia com variação não linear
c
1,
c
2
e
c
3
= 1
Cm = Centro de massa
Esta expressão incorpora um novo termo C3 que mostrou algumas
melhoras no desempenho do algoritmo [6]. Este novo termo promove a transferência
de informações entre os indivíduos na medida em que há uma atração dos
indivíduos para o centro do grupo.
17
Capítulo 4: AG com taxas adaptativas
4.1 – Introdução
A estratégia de escolha das taxas dos operadores genéticos pode ser mais
eficiente do que a convencional, que é feita empiricamente. Neste trabalho foi
implementada uma nova estratégia adaptativa que aponta para resultados
promissores no desempenho de um AG. Esta estratégia, citada anteriormente e
chamada AORCEA, foi desenvolvida por M. Giger, D. Keller e P. Ermanni [5],
consiste em criar um módulo de adaptação do AG dentro do ciclo de busca do
algoritmo que ajuste os parâmetros de acordo com o situação da população. É
classificada como uma técnica adaptativa, no nível da população e baseada no
desempenho dos operadores.
A figura 2 mostra onde este módulo atua em um AG clássico.
Figura 2 – Esquema básico de um algoritmo genético adaptativo
A estratégia de adaptação é realizada no módulo Adaptação que avalia o
estado atual da população e ajusta os operadores de acordo com o resultado desta
avaliação.
A busca da solução ótima em um Algoritmo Genético consiste,
basicamente, na alternância entre a exploração de novas regiões do espaço de busca
Inicialização
População
Substit
uição
Descendentes
Reprodução
Seleção
Adaptação
Parar?
População Final
Solução
18
e a localização do ponto ótimo de uma região descoberta anteriormente. Desta
forma, a estratégia de adaptação proposta observa qual a situação atual da
população, segundo essa classificação, e decide quais operadores devem ser
favorecidos no sentido de proporcionar a exploração de novas regiões ou de buscar
o melhor ponto de uma área promissora recém descoberta. O objetivo é sempre
acelerar o processo de busca.
Após esta decisão os operadores são ordenados baseado em seus
desempenhos nas gerações imediatamente anteriores. Se, por exemplo, a situação
atual do processo de busca mostra que a população está estagnada em uma única
região e que aparentemente seu ótimo local já foi alcançado, é necessário descobrir
novas regiões promissoras. Assim, o módulo de adaptação avalia o resultado dos
operadores nas gerações anteriores e verifica quais tiveram melhor desempenho em
diversificar a população. Em seguida os operadores são ordenados de acordo com o
seu desempenho na necessidade atual, que no exemplo é diversificar a população.
Após a ordenação, o módulo de Adaptação ajusta os operadores aumentando a
probabilidade daqueles que são mais importantes no momento. Desta forma a
chance de encontrar uma outra região promissora aumenta. Da mesma forma, caso a
necessidade atual da população seja encontrar o ótimo local, analogamente ocorre o
privilégio aos operadores que tiveram melhor desempenho em descobrir indivíduos
melhores. A figura 3 mostra o esquema básico mostrado aqui.
Figura 3 – Esquema básico da estratégia adaptativa de um algoritmo genético
Determinação do estado atual da população
População aglomerada ou diversificada?
Calcula o desempenho
dos operadores em
diversificar a população
Calcula o desempenho
dos operadores em buscar
melhores indivíduos
Ordena os operadores
Adapta linearmente as taxas dos operadores
Aglomerada
Diversificada
19
4.2 – Estratégia de Adaptação
Para o módulo de Adaptação tomar a decisão de qual caminho tomar,
entre explorar novas regiões ou buscar o melhor ponto da região atual, é necessário
introduzir um sensor que represente a situação atual da população. Este sensor foi
chamado de bff (Best Fitness Frequency).
Uma forma de avaliar a situação atual da população é verificar a
distribuição dos indivíduos através de seus fitness. Se todos os valores de fitness da
população atual estiverem muito próximos, significa que, ou a população está
estagnada em torno de um ótimo local ou o espaço de busca é muito plano. Por
outro lado, se a população apresenta valores de fitness muito diferentes entre si
significa que tanto o espaço de busca não é plano como também o processo de busca
fatalmente irá encontrar indivíduos melhores que os atuais, isto é, a média do fitness
da população provavelmente irá melhorar.
4.2.1 – Cálculo do valor de bff
Para calcular o valor do bff é necessário dividir os valores de fitness em
classes a partir do melhor indivíduo. Cada faixa de valores é determinada por um
fator ε. A quantidade de indivíduos cujo fitness está na mesma faixa de valor do
melhor fitness determinará se os indivíduos estão aglomerados ou espalhados. Para
calcular o valor de bff da população, primeiro calcula-se o valor de bff para cada
indivíduo i:
⋅≤−
=
senão
fffse
BBi
bff
i
,0
||,1
ε
(10)
Onde
i
f é o valor de fitness do indivíduo i e
B
f é o fitness do melhor
indivíduo.
O valor de bff da população é dado pela equação:
20
∑
=
N
i
i
bff
N
bff
1
(11)
Onde N corresponde ao tamanho da população. Isto significa que o valor
do bff representa a freqüência relativa de indivíduos que se encontram na mesma
faixa de fitness onde se encontra o melhor indivíduo.
A figura 4 ilustra os diferentes estágios do processo de busca em um
problema de mínima que podem ocorrer em um AG e seus valores de bff
correspondentes.
Figura 4 – Esquema ilustrando diferentes estágios no processo de busca
Na figura 4.a o processo de busca caminha para um ótimo local. O valor
do bff é baixo (0,3), pois poucos são os indivíduos que se encontram próximos do
melhor indivíduo. Nas gerações seguintes a este estágio existe uma grande chance
Processo de busca,
bff
=
0,3
Estagnação local
,
bff
= 0,8
Explorando nova área, bff = 0,2
Estagnação final
,
bff
= 0,8
21
dos indivíduos seguirem para o vale onde se encontra um ótimo local. Já na figura
4.b os indivíduos se encontram aglomerados e o valor do bff é alto (0,8). Os
indivíduos possuem pequena diferença entre seus fitness. Se a população conseguir
sair deste ótimo local, o valor do bff cai novamente, como é mostrado na figura 4.c.
Finalmente, na figura 4.d, a busca alcança outro ótimo e a população fica estagnada
com valor de bff alto novamente.
Resumindo, valores baixos de bff indicam uma população com
características de exploração enquanto que valores altos de bff indicam estagnação
da busca. Ao introduzir o parâmetro l indicando o limiar entre exploração e
estagnação é possível criar uma estratégia de adaptação descrita a seguir:
• lbff
≤
: Aumentar a taxa dos operadores que mais contribuíram
recentemente para a melhora do fitness da população para tentar
alcançar o ótimo local. Para facilitar, este conceito será chamado
de sucesso.
• lbff
>
: Aumentar a taxa dos operadores que mais contribuíram
recentemente para a exploração do espaço de busca para tentar
escapar deste suposto ótimo local. Para facilitar, este conceito
será chamado de diversidade.
Agora é necessário avaliar o sucesso e a diversidade de cada operador ao
gerar seus descendentes.
4.2.2 – Cálculo do valor de sucesso de um operador
Em geral, o processo de busca de um AG tenta resolver um problema de
mínima. Desta forma, o cálculo do sucesso de um operador do tipo X na geração G
gerando um indivíduo i é definido como:
≤
−
−
=
senão
ffse
ff
ff
pici
Bpi
cipi
s
G
Xi
,0
,
,
(12)
22
Onde
pi
f é o fitness do melhor pai do indivíduo gerado,
ci
f é o fitness do
filho gerado pelo operador e
B
f é o fitness do melhor indivíduo da população na
geração corrente. Desta forma o maior valor de sucesso que um operador aplicado a
um indivíduo pode ter é 1. Isto ocorre quando ele gera o melhor indivíduo da
população atual.
Após a aplicação de cada operador à população, a taxa de sucesso deste
pode ser calculada da seguinte forma:
∑
=
G
Xi
X
G
X
s
N
s
,
1
(13)
Onde
X
N é o número de aplicações do operador do tipo X na geração G.
4.2.3 – Cálculo do valor de diversidade de um operador
O valor de diversidade de um operador avalia a distribuição dos
indivíduos no espaço de busca. A distância euclidiana de um indivíduo i gerado pela
aplicação de um operador do tipo X na geração G em relação ao melhor indivíduo b
é calculada da seguinte forma
∑
=
−=
n
j
jj
G
Xi
bid
1
2
,
)(
(14)
onde n é o número de genes do genótipo, e
j
i e
j
b são os componentes
dos correspondentes genótipos. A taxa de diversidade da aplicação de um operador
do tipo X aplicado na geração G gerando um indivíduo i é calculada da seguinte
forma:
23
+>
+
+≤
=
)1(,
1
1
)1(,0
max
,
,
ε
ε
B
G
G
Xi
B
G
Xi
ffse
a
d
d
ffse
t
(15)
Onde
G
d
max
é a maior distância euclidiana entre o melhor indivíduo atual e
todos os indivíduos da população. O fator a é introduzido por questões de escala e
possui valor a = 9. Indivíduos com valor de fitness melhor ou igual ao valor de
fitness do melhor indivíduo recebem diversidade zero por não contribuírem para sair
da região onde a população se encontra. A taxa de diversidade de um operador do
tipo X aplicado à população em uma geração G é calculada da seguinte forma:
∑
=
G
Xi
X
G
X
t
N
t
,
1
(16)
Onde
X
N é o número de aplicações do operador do tipo X na geração G.
4.2.4 – Adaptação da taxa dos operadores
O objetivo da adaptação da taxa dos operadores é garantir um equilíbrio
entre a exploração de novas áreas promissoras e a busca pelo melhor ponto da região
atual. Dependendo do valor atual do bff aplica-se a adaptação buscando sucesso ou a
diversidade. Se o valor atual do bff for inferior ao parâmetro l, os operadores são
ordenados segundo seu sucesso nas gerações anteriores para forçar o sucesso no
algoritmo. De forma análoga, caso o valor de bff seja superior ao parâmetro l os
operadores são ordenados com relação a sua capacidade de diversidade nas gerações
passadas. A figura 5 mostra como a adaptação atua nos operadores de acordo com o
valor do bff em relação ao parâmetro l.
O parâmetro δ que corresponde à taxa de adaptação que será aplicada aos
operadores é calculada da seguinte forma:
24
>−
−
≤−−
=
lbffselbff
l
lbffselbff
l
máx
máx
),(
1
),(
δ
δ
δ
(17)
O valor limite l e a máxima taxa de adaptação δ
máx
são configuráveis o
que permite controlar tanto a proporção entre sucesso e diversidade quanto a
magnitude da adaptação.
Figura 5 – Taxa de adaptação baseada no valor do bff
Com a taxa de adaptação calculada, basta aplicá-la aos operadores
ordenados segundo o sucesso ou diversidade, dependendo da situação da população.
Para isto é aplicada a seguinte função:
δ
−
−+
+=
+
1
21
1
No
RNo
pp
X
G
X
G
X
(18)
Onde
X
p é a taxa do operador do tipo X, G é a geração corrente, No é o
número de operadores utilizados no algoritmo evolutivo e
X
R é a posição do
operador do tipo X na ordenação. Na figura 6 é possível ver como a adaptação dos
operadores ocorre. O valor δ é aplicado em sua totalidade ao melhor operador,
aumentando sua taxa. No segundo melhor, um valor menor de δ é aplicado. No
exemplo, a partir do quarto operador, o valor de ajuste δ já é aplicado de forma
negativa, isto é, diminuindo a taxa do operador.
sucesso diversidade
0
l
1
bff
δ
máx
δ
25
Figura 6 – Adaptação linear das taxas dos operadores
Para obter um retrato melhor do desempenho dos operadores não basta
observar somente a geração imediatamente anterior, é necessário observar uma
média de desempenho para se obter um resultado mais confiável. Por outro lado,
observações de gerações muito antigas podem não refletir o desempenho do
operador na atual situação da busca. Por essas razões, e de forma empírica, foi
escolhido observar o comportamento dos operadores nas últimas cinco gerações.
taxas
ordenação
δ
taxas adaptadas
26
Capítulo 5: Ferramenta computacional de
otimização: PROGOTIM
5.1 – Introdução
O PROGOTIM é uma ferramenta computacional desenvolvida por
Albrecht [6] para executar programas de otimização empregando alguns métodos de
computação evolutiva. Foi concebido inicialmente para o estudo de métodos de
otimização, aplicados a projetos de ancoragem de plataformas petrolíferas,
permitindo soluções mais seguras e eficientes.
Com a participação de outros pesquisadores, foram implementadas novas
facilidades e interfaces para outros problemas de engenharia estrutural associados a
industria do petróleo. Sendo assim, encontra-se também neste programa, modelado
o problema de sistemas de Risers, desenvolvido por Vieira [25] que será utilizado na
comparação de performance do AG adaptativo desenvolvido aqui nesta dissertação.
5.2 – Modelos de Otimização
O programa possui um módulo de otimização onde foram
implementados os seguintes algoritmos de otimização:
• Algoritmo genético – Implementação básica de algoritmo genético com
mutação, crossover uniforme ou de um ponto, codificação binária ou real,
seleção por roleta, etc.
• Micro Algoritmo Genético – O Micro Algoritmo Genético implementado
utiliza as mesmas rotinas e as mesmas opções do algoritmo genético básico.
O único dado a mais é o número de iterações da fase 2, ou seja, o número de
vezes que processos com algoritmos genéticos básicos seqüenciais serão
utilizados.
O critério de parada para a fase 1, ou seja, uma realização do algoritmo
genético, também é diferenciado. O algoritmo pára quando a diferença entre
o material genético do melhor indivíduo e dos outros indivíduos for menor
27
do que 5%. Com esse nível de diversidade genética admite-se que o
algoritmo convergiu e não haverá mais melhora.
• Enxame de Partículas – O algoritmo de otimização por Enxame de
Partículas implementado no Progotim teve algumas alterações do algoritmo
original apresentado anteriormente. Este algoritmo modificado conta com a
estratégia global (GPSO) e com atualização da velocidade e posição dadas
pelas equações (12). Nesta equação foi acrescentado um novo termo que
considera também um centro de massa como uma outra parcela de atração.
Não foram implementados nem o fator de constrição, nem a estratégia local
(LPSO).
)(*()*3)(*()*2)(*()*1*
1 imiiiii
xCrndCxxbestrndCxGbestrndCvelwvel
−
+
−
+
−
+
=
+
11 ++
+
=
iii
velxx
(19)
Onde
C1, C2 e C3 = 1.
m
C
– Centro de massa, conforme equação:
∑
∑
=
=
=
N
j
j
N
j
jj
f
xf
C
1
1
(20)
i
w
– Inércia com variação não linear, conforme equação:
inifinini
n
n
i
www
N
iN
w +−
−
= )(*
)(
(21)
Onde
i
w
- Coeficiente de inércia para a iteração i
N
- Número máximo de iterações
28
i
- Iteração atual
ini
w
- Coeficiente inicial
fin
w
- Coeficiente final
n
- Expoente de não linearidade
• Estratégia Evolutiva – A Estratégia Evolutiva foi implementada de forma
simples, e somente na forma de multi membros (µ,λ), com λ = µ.
As opções disponíveis neste módulo são:
• Tamanho da população – Número de indivíduos para todos os métodos;
• Probabilidade de Cruzamento – Valor utilizado para decidir se um par de
cromossomos irá sofrer cruzamento. Se um valor sorteado for menor do que
este valor, o par sofrerá a operação de cruzamento;
• Probabilidade de Mutação – Valor utilizado para decidir se um
cromossomo irá sofrer mutação. Se um valor sorteado for menor do que este
valor, o cromossomo sofrerá mutação;
• Cruzamento Uniforme / Cruzamento de 1 ponto – Define o tipo de
operador de cruzamento que será utilizado: uniforme ou de um ponto;
• Geracional / Steady State / Elitismo – Seleciona o tipo de sobrevivência
que será utilizado. No caso do Elitismo é possível definir quantos indivíduos
passarão para a próxima geração (Elite);
• Seleção por Torneio – Se marcado, define o torneio como forma de seleção
para os indivíduos que irão participar do cruzamento e mutação. Nesta
implementação o torneio é sempre entre dois indivíduos escolhidos
aleatoriamente da população. Se não estiver marcada a forma de seleção
escolhida será a roda da roleta com “ranking”;
29
• Save / Restart – Permite salvar o estado de uma otimização e recomeçar o
processo mais tarde (ainda não operacional);
• Binário/Real – Define a forma de codificação do indivíduo. No caso de estar
selecionada a codificação real o cruzamento será do tipo média aritmética
ponderada;
• Usar Semente Fixa – Opção para utilizar sempre a mesma semente no
algoritmo de geração de números aleatórios. Com isso garante-se a repetição
dos valores entre duas otimizações, para efeito de verificação;
• Relatório Detalhado – Opção para imprimir, a cada geração, informação
detalhada de cada indivíduo como valor da função, coordenadas e
velocidade, cromossomo e outras observações.
• Critérios de parada:
o Número Máximo de Gerações – É o critério mais simples. O
processo é interrompido quando um número N de gerações é
atingido;
o Valor Limite para a função objetivo – Também conhecido como
valor de satisfação. Pode ser utilizado quando se conhece um valor da
função objetivo que satisfaça algum critério subjetivo. Além deste
valor a melhoria do sistema não terá significado prático;
o Média x Melhor – O processo de otimização será interrompido
quando o valor da média for maior que o valor do melhor indivíduo
multiplicado por um fator entre [0,1], durante um número pré-fixado
(n) de gerações.
30
o Média – O processo de otimização será interrompido quando a
variação do valor da média não for maior do que um fator entre [0,1],
durante n gerações. Ou seja, a média está estacionária;
o Duplo (Média) – Nesta opção os dois critérios anteriores são
aplicados simultaneamente, ou seja, o valor da média deve-se manter
próximo do valor do melhor indivíduo durante n gerações e a média
não deve variar além de um limite fixado entre [0,1] durante estas n
gerações.
5.3 – Acompanhamento da Evolução
Durante a execução do processo de otimização, algumas quantidades
relativas ao desenvolvimento da população são acompanhadas num gráfico como o
apresentado na figura 7. Os valores de fitness do melhor indivíduo são mostrados em
azul e do pior indivíduo em cinza. Os valores da média e do desvio padrão de fitness
da população, são mostrados, respectivamente em vermelho e rosa. E a margem k,
do critério de parada, em amarelo.
Além do gráfico, um relatório de acompanhamento da evolução é
impresso (figura 8), que mostra detalhes da população. Ao fim da otimização é
impresso um resumo contendo: o tempo total, número de indivíduos com problemas
de convergência e número de indivíduos penalizados. Além dos dados do melhor
indivíduo.
Figura 7 – Gráfico de acompanhamento da evolução
31
Figura 8 – Relatório de acompanhamento
Considerando-se que os métodos são aplicados a um processo
extremamente caro em termos de gasto computacional, como é a análise de sistemas
de risers, a cada geração são computados também o número de:
• Indivíduos efetivamente calculados, considerando-se que
indivíduos repetidos não são calculados duas vezes;
• Indivíduos penalizados;
• Indivíduos com falha de convergência.
5.4 – Modelo de Sistemas de Risers
5.4.1 – Introdução
Este módulo do programa trata da otimização de configurações de
sistemas de Risers. Como os sistemas de Risers de exploração de petróleo são
problemas complexos sua solução matemática é computacionalmente cara. Desta
forma foi desenvolvido por Vieira [25] um modelo matemático para que sua solução
fosse feita através de um Algoritmo Genético clássico.
Os risers podem ser rígidos ou flexíveis. Os rígidos são tubos de aço e os
flexíveis são mangotes especiais compostos por várias camadas de diferentes
materiais. Estes risers possuem configurações de linha tais como:
• Catenária Livre – Não utiliza flutuadores. É utilizado tanto com
risers rígidos quanto flexíveis.
• Lazy S / Step S – Configuração em que uma seção intermediária
passa por um arco flutuador que pode ser sustentado por um
tensionador (Lazy) ou o próprio riser é o tensionador (Step).
32
• Lazy Wave / Step Wave – O arco flutuador é substituído por
uma seção intermediária com flutuadores. Assim como a
configuração Lazy S / Step S, pode ser sustentado pelo próprio
riser (Step) ou não como mostrado na figura 9.
Figura 9: Ilustração de sistema de riser Lazy-wave
Os risers flexíveis tem sido empregados em águas profundas, mas eles
apresentam limitações técnicas e são muito custosos. Por esse motivo, tem-se
procurado alternativas a este tipo de risers. Uma alternativa promissora é o uso de
risers rígidos em catenária (SCR- Steel Catenary Riser). Atualmente a Petrobras tem
empregado navios para a exploração em águas profundas, são os FPSO’s (Floating
Production Storage and Offloading). Os sistemas de risers instalados nestas
unidades flutuantes apresentam problemas no comportamento estrutural dinâmico.
Estes problemas, associados à flexão excessiva e compressão dinâmica dos risers
podem ser aliviados usando-se flutuadores e não mais a configuração em catenária
livre. A busca de uma configuração ótima de um sistema de risers pode ser
exaustiva, pois envolve muitas variáveis. Este problema tem sido estudado por
outros pesquisadores [25] no Programa de Engenharia Civil da COPPE empregando
métodos de síntese e otimização por algoritmos inteligentes. Um dos objetivos
desta dissertação é melhorar um destes algoritmos, o Algoritmo Genético, através de
estratégias adaptativas nos operadores e comparar com os resultados obtidos em
trabalhos anteriores.
O problema de um sistema de risers é complexo, envolve inicialmente a
definição da configuração das linhas e dos materiais utilizados. A analise estrutural
inclui o modelo estático e o dinâmico, onde é necessário analisar o comportamento
33
dinâmico do sistema avaliando o mesmo sob influência de cargas ambientais e
movimentações do navio. Porém a análise dinâmica é muito mais complexa e
custosa computacionalmente, pois envolve características não lineares de todo o
sistema, como as não linearidades físicas e as não linearidades geométricas.
Esta dissertação emprega o mesmo modelo desenvolvido por Vieira [25]
para a otimização da configuração de risers, implementando-se o algoritmo
AORCEA citado anteriormente. São considerados na busca da configuração ótima
apenas os critérios de projeto baseados em análises globais, admitindo que algumas
características dos risers já haveriam sido previamente fixadas com base em análise
de colapso hidrostático, condições de temperatura extrema e outras condicionantes
locais.
5.4.2 – Representação matemática
Sem levar em consideração a composição dos materiais utilizados, a
configuração do sistema de riser em Lazy-Wave foi simplificada para a um
problema de apenas sete variáveis (figura 10) apresentadas a seguir:
Figura 10: Definição de uma configuração Lazy-wave
Sendo:
• L1: comprimento final, entre o final do trecho com flutuadores e
a conexão de fundo;
• L2: comprimento do trecho com flutuadores;
• L3: comprimento entre a conexão de superfície e o início do
trecho com flutuadores;
34
• α: ângulo de topo da configuração;
• H: lâmina d’água;
• z: profundidade da conexão;
• P: projeção horizontal.
Como os parâmetros H e z descrevem características do cenário do
problema, eles devem permanecer fixos durante o processo de otimização. Da
mesma forma, a projeção P e o ângulo α podem ser definidos pelos valores de L1,
L2 e L3. Logo estes parâmetros também podem permanecer fixos durante a
otimização.
As propriedades dos flutuadores são definidas a partir do riser
especificado, mas como admitem variações, eles podem ou não fazer parte do
modelo a ser otimizado. A figura 11 ilustra as características dos flutuadores.
Figura 11: Definição das características dos flutuadores
Onde:
• HDf – Diâmetro externo do flutuador
• Lf – Comprimento
• Esp – Distância entre os flutuadores
Assim, os parâmetros a serem otimizados pelo AG são: L1, L2, L3, HDf,
Lf e Esp.
35
Capítulo 6: Adaptação do PROGOTIM
6.1 – Introdução
Este capítulo descreve as alterações realizadas no programa PROGOTIM
para contemplar a implementação do AG com taxas adaptativas nos operadores
genéticos.
A alteração do programa foi dividida em sete partes:
• Criação do operador de mutação gaussiana
• Separação dos operadores
• Aumento do vetor de indivíduos
• Criação dos medidores de sucesso e diversidade
• Comparação de resultados
• Alteração da contagem de número de avaliações
A alteração do programa foi feita de forma que as características
originais do programa, que não impedissem o funcionamento da adaptação,
continuassem inalteradas.
6.2 – Operador de Mutação Gaussiana
Foi criada uma função dentro do programa que gera um número aleatório
com distribuição gaussiana. Esta função foi baseada no programa em FORTRAN
[26]. A figura 12 apresenta o trecho do programa em FORTRAN.
36
Figura 12 – Programa em FORTAN que gera um número com distribuição
gaussiana
6.3 – Separação dos Operadores
Para que a adaptação dos operadores seja feita corretamente, é necessário
que cada um deles seja avaliado separadamente. Isto significa que os descendentes
gerados pelos operadores devem ser avaliados antes que outro operador atue sobre
eles. Como o programa originalmente não previa esta situação, foi necessário
modificar as funções de mutação e crossover de forma que pudessem ser executadas
separadamente.
Outra modificação necessária foi alterar a forma como essas funções são
chamadas. Como há a necessidade de avaliar a população após cada operador, foi
necessário concentrar as chamadas dos operadores em um único ponto do programa
e avaliá-las logo em seguida de sua aplicação.
Desta forma o programa passou a contar com quatro operadores sujeitos
à adaptação: Mutação Gaussiana, Mutação Uniforme, Crossover de Um Ponto e
Crossover Uniforme. Após a aplicação de cada operador, a população gerada é
avaliada através dos medidores de sucesso e diversidade. Assim, cada operador tem
sua probabilidade de ocorrência independente dos outros operadores para que a
mesma possa ser controlada através do módulo de adaptação.
37
6.4 – Aumento do Vetor de Indivíduos
Originalmente o programa, ao gerar um novo indivíduo, sobrescrevia
aquele que o gerou. Por exemplo, se um novo indivíduo fosse gerado por mutação, o
indivíduo original era substituído pelo seu descendente. A proposta do novo AG
sugere que todos os indivíduos, novos e antigos, devam permanecer na população
intermediária até que sejam avaliados, ordenados e selecionados para a geração
seguinte.
Como foram escolhidos quatro operadores para sofrerem adaptação, a
população intermediária foi projetada para suportar um máximo de cinco vezes a
população inicial. Isto porque, caso cada operador gere o máximo possível de
descendentes, cada um criaria a mesma quantidade de indivíduos originais da
população. Estes, somados com a própria população original resulta em cinco vezes
o tamanho da população.
6.5 – Criação dos Medidores de Sucesso e Diversidade
A maior dificuldade para medir o sucesso e a diversidade é certificar que
um determinado indivíduo foi gerado através de um determinado operador. Para isso
optou-se por avaliar o novo indivíduo logo após sua criação ao contrário de esperar
para avaliar toda a população intermediária ao final da criação de todos os
indivíduos, como era feito no programa original. Foi necessário calcular o fitness de
cada indivíduo logo após sua criação e, logo em seguida, calcular seu sucesso e sua
diversidade.
6.6 – Comparação de Resultados
Para comparar a desempenho do programa com os resultados de [5], foi
necessário alterar a estrutura do programa de forma que ele alternasse entre resolver
um problema da máxima e de mínima de uma função. Para isso foi necessário
modificar alguns ordenadores, a forma de selecionar o melhor indivíduo, o cálculo
da média do fitness, o cálculo de bff e as medidas de sucesso e diversidade.
38
6.7 – Alteração da Contagem de Número de Avaliações
Com o aumento da população intermediária por conta da modificação
relatada na sessão 6.4 deste capítulo, houve um aumento significativo do número de
avaliações, produzindo um aumento no custo computacional de execução do
programa.
Após uma análise do processo de seleção dos indivíduos a serem
avaliados, verificou-se que este funcionava da seguinte forma: Antes de iniciar a
avaliação de cada indivíduo, verificava-se se este possuía o mesmo cromossomo de
algum indivíduo anteriormente avaliado na mesma geração. Caso existisse, este não
era avaliado e seu fitness recebia o mesmo valor do indivíduo encontrado. Desta
forma, os indivíduos iguais não eram avaliados duas vezes, visto que seu fitness já
era conhecido.
O problema desta estratégia é que, mesmo que um indivíduo já tenha tido
seu fitness calculado em uma geração anterior, ele é calculado novamente, a menos
que um outro indivíduo igual a ele já tenha sido avaliado anteriormente nesta
geração.
Como o número de indivíduos aumentou, o número de avaliações
também aumentou. Assim, optou-se por modificar a forma de verificar se um
indivíduo necessita de avaliação. Foi criada uma marcação para cada indivíduo,
indicando se este é novo (necessita avaliação de fitness) ou não é novo (não
necessita avaliação). Desta forma, mesmo aumentando o número de indivíduos, o
número de avaliações manteve-se na mesma faixa de valores.
39
Capítulo 7: Estudo de casos
7.1 – Parâmetros dos Algoritmos
De forma a se avaliar o desempenho do AG adaptativo, os resultados dos
casos analisados foram comparados com o AG clássico (sem adaptação) e o PSO.
A escolha dos parâmetros empregada no AG para a comparação foi a
mesma utilizada pelo artigo [5]:
• População: 20
• Gerações: 200
• Codificação: Real
• Critério de parada: Número máximo de gerações
• Probabilidade Crossover Uniforme: 0,35
• Probabilidade Crossover de Um Ponto: 0,35
• Probabilidade Mutação Uniforme: 0,15
• Probabilidade Mutação Gaussiana: 0,15
• Seleção: Roleta
• Substituição (geração): Elitismo de um
• Precisão: 1
Também foram feitos testes com as taxas usuais do AG:
• Probabilidade Crossover Uniforme: 0,8
• Probabilidade Crossover de Um Ponto: 0,8
• Probabilidade Mutação Uniforme: 0,01
• Probabilidade Mutação Gaussiana: 0,01
As taxas dos operadores genéticos (crossover e mutação), no AG
adaptativo, correspondem às taxas iniciais, já que elas mudam ao longo do processo
de otimização. Como o AG clássico utiliza uma única forma de crossover e de
mutação por vez, foram escolhidos para serem utilizados nos testes o Crossover
Uniforme e a Mutação Uniforme.
40
Para o algoritmo PSO foi utilizada a seguinte configuração de
parâmetros:
• População: 25
• Coeficiente da velocidade (C1, C2 e C3): Variando
• Global (C1): 1
• Local (C2): 1
• Social (C3): 1
• Controle de Inércia: Variação não linear
• K (expoente de não-linearidade): 1.2
• Precisão (dos parâmetros das funções): 0,01
• Velocidade máxima: 1
Para a otimização das funções Rosembrock e Griewank a velocidade
máxima do PSO foi configurada para 100, pois a velocidade 1 apresentou
performance muito baixa.
Como já explicado no capítulo cinco, os valores dos parâmetros
empregados no AG adaptativo δ
máx
, l e ε são configuráveis. Estes valores
determinam, respectivamente, a variação máxima da adaptação a cada geração, o
limite entre sucesso e diversidade ao qual o valor bff é comparado e o tamanho das
faixas de fitness. Foram utilizadas seis configurações diferentes (A1 a A6) de
combinações destes parâmetros para avaliar o resultado. Estas configurações são
mostradas na tabela 1:
Tabela 1
Combinações dos valores dos parâmetros do AG adaptativo
Configuração A
1
A
2
A
3
A
4
A
5
A
6
δ
máx
0,05
0,05
0,05
0,10
0,20
0,20
l 0,10
0,25
0,50
0,10
0,10
0,50
ε
0,01
0,01
0,01
0,01
0,01
0,01
Como já explicado no capítulo quatro, a observação do estado da
população deve ser feita através de uma média de resultados, para que esta seja
41
refletida de forma mais confiável. Porém, a observação de gerações muito antigas
pode representar de forma distorcida a situação atual da população. Por estes
motivos, e de forma empírica, em todas as configurações acima foram utilizadas as
últimas cinco gerações para avaliar o estado da população e efetuar a adaptação.
7.2 – Descrição das Funções
As funções utilizadas para comparar o desempenho entre o AG
adaptativo, o AG clássico e o PSO foram as seguintes:
7.2.1 – De Jong F1
A função de De Jong [27] utilizada neste trabalho é apresentada abaixo
(22). O mínimo global é igual a 0.0. A dimensão utilizada para esta função foi de 3
variáveis com limite configurado em [-5,12, 5,12].
∑
=
=
n
i
i
xxnf
1
2
),( (22)
Onde:
n – Número de dimensões (3)
x
i
– Valor do parâmetro i
7.2.2 – Rosenbrock
A versão da função de Rosenbrock [6] utilizada neste trabalho é
apresentada abaixo (23). O mínimo global é igual a 0.0. A dimensão utilizada para
esta função foi de 30 variáveis com limite configurado em [-30, 30].
7
1
1
222
1
10
)1()(*100
),(
∑
−
=
+
−+−
=
n
i
iii
xxx
xnf (23)
42
Onde:
n – Número de dimensões (30)
x
i
– Valor do parâmetro i
7.2.3 – Rastrigin
A versão utilizada da função de Rastrigin [6] neste trabalho é
apresentada abaixo (24). O mínimo global é igual a 0.0. A dimensão utilizada foi de
20 variáveis com seu limite ajustado para [-5,12, 5,12].
)*2cos(*1010),(
1
2
i
n
i
i
xxnxnf
π
∑
=
−+= (24)
Onde:
n – Número de dimensões (20)
x
i
– Valor do parâmetro i
7.2.4 – Griewank
Foi criada uma nova versão da função de Griewank [28] (25). Esta foi
alterada para se igualar à função apresentada no artigo AORCEA [5] (26). O
mínimo global é igual a 0.0, a dimensão empregada é igual a 10 e o limite utilizado
igual a [-600, 600].
∑
∏
=
=
+
−=
n
i
n
i
i
i
i
x
xxnf
1
1
2
1cos)(
4000
1
),( (25)
∑
∏
=
=
+
+
−
−−=
n
i
n
i
i
i
i
x
xxnf
1
1
2
1
1
100
cos)100(
4000
1
),( (26)
Onde:
n – Número de dimensões (10)
43
x
i
– Valor do parâmetro i
7.2.5 – Riser
A função objetivo (F
obj
) do sistema de risers ilustrado na figura 10 é
definida como produto do comprimento de cada comprimento de linha (L
i
) pelo seu
respectivo índice de custo unitário (IC
i
) somado ao produto do volume dos
flutuadores (V
flut
) também pelo seu índice de custo unitário (IC
flut
) conforme a
equação (27).
( )
flutflut
ni
iiobj
ICVLICF ×+
×=
∑
= ...1
(27)
Para que um problema de minimização seja resolvido por um algoritmo
de maximização, como é o Progotim, é necessário inverter a função objetivo. Porém,
como a ordem de grandeza entre as penalidades e a função objetivo pode diferir
muito, é necessário tornar a função objetivo adimensional utilizando como
referência os valores máximos de seus parâmetros, como apresentado na função
(28).
( )
( )
flutflut
ni
ii
flutflut
ni
ii
ICVLIC
ICVLIC
f
×+
×
×+
×
=
∑
∑
=
=
max
...1
max
...1
(28)
Assim, a função fitness, para um problema de minimização em um
algoritmo de maximização, é composta pelo inverso da soma da função (28) com as
penalidades relativas às restrições do problema, conforme a função (29).
∑
+
=
j
Pf
fitness
1
(29)
Onde P
j
são as respectivas penalidades.
44
Foi considerada a mesma função (30) de penalidades de Vieira [25]
conforme representada abaixo e exemplificado na figura 13:
[
]
≥
<−⋅
=
1,0
1,)1(
3
xse
xsexk
P
q
(30)
Onde k é um coeficiente que permite soluções não restritas quando o
valor de x é muito próximo de 1.
0 0.5 1 1.5
0
1
1.5
0
Pc x( )
1.50 x
Figura 13: Função cúbica de penalidade
Esta função de penalidade é aplicada a seis restrições: tensão ao longo do
riser, duas restrições ao ângulo de topo, uma restrição da variação do ângulo da
linha, uma restrição da tração de topo e uma restrição ao nível de tração ao longo do
riser. Existe ainda uma restrição absoluta que elimina as configurações em que a
menor distância entre o trecho inicial de catenária (entre a conexão de topo até o
início dos flutuadores) e o solo estejam abaixo de um limite mínimo pré-
estabelecido. Esta restrição impõe uma distancia mínima de qualquer ponto da linha
do riser ao fundo marinho.
45
7.3 – Resultados
Os experimentos computacionais foram realizados empregando-se as
funções descritas anteriormente: De Jong F1, Rosenbrock, Rastrigin, Griewank e a
função que descreve o problema de otimização de configurações de riser.
Para cada caso foram realizadas dez execuções de cada algoritmo de
otimização de forma a se obter uma boa estatística para efeitos de comparação dos
resultados.
Os resultados do valor final de fitness após 200 gerações, em termos de
melhor, mediana, média e desvio padrão, encontrados nas dez execuções para cada
função são apresentados nas tabelas 2 a 10. Nas tabelas de 2 a 6 são apresentados os
valores para as taxas de operadores recomendadas no artigo AORCEA [5]. No AG
clássico foram utilizados somente o crossover uniforme e a mutação uniforme. Para
o AG adaptativo essas taxas correspondem às taxas iniciais.
• Probabilidade Crossover Uniforme: 0,35
• Probabilidade Crossover de Um Ponto: 0,35
• Probabilidade Mutação Uniforme: 0,15
• Probabilidade Mutação Gaussiana: 0,15
Já nas tabelas de 7 a 10 são apresentados os valores para as taxas usuais
de crossover e mutação. No AG clássico foram utilizados somente o crossover
uniforme e a mutação uniforme e o critério de parada foi configurado para 200
gerações. Para o AG adaptativo essas taxas correspondem às taxas iniciais e o
critério de parada também foi configurado para 200 gerações:
• Probabilidade Crossover Uniforme: 0,8
• Probabilidade Crossover de Um Ponto: 0,8
• Probabilidade Mutação Uniforme: 0,01
• Probabilidade Mutação Gaussiana: 0,01
A coluna PSO é mantida igual para estes dois grupos de testes para que
seja feita a comparação.
46
Tabela 2
Resultados da maximização para a função De Jong F1
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,001
Mediana
0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,005
Média
0,000 0,000 0,000 0,003 0,001 0,000 0,001 0,006
Desvio Padrão
0,000 0,000 0,000 0,008 0,002 0,000 0,002 0,004
Tabela 3
Resultados da maximização para a função Rosenbrock
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
0,000 0,000 0,000 0,000 0,000 0,000 0,002 0,012
Mediana
0,017 0,002 0,001 0,002 0,000 0,000 0,011 0,026
Média
0,054 0,023 0,014 0,005 0,057 0,005 0,021 0,027
Desvio Padrão
0,075 0,055 0,026 0,007 0,116 0,013 0,030 0,011
Tabela 4
Resultados da maximização para a função Rastrigin
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
23,241 6,415 12,870 11,366 6,415 6,415 10,121 64,018
Mediana
23,241 12,780 29,146 14,195 11,981 39,018 14,034 70,950
Média
43,831 13,980 33,130 27,315 12,169 31,254 14,325 71,741
Desvio Padrão
29,118 6,848 14,851 20,942 4,943 18,448 2,278 6,857
Tabela 5
Resultados da minimização para a função Griewank
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
0,002 0,002 0,002 0,002 0,002 0,036 0,994 1,044
Mediana
0,589 1,215 0,393 0,991 0,583 0,516 1,253 1,838
Média
0,633 1,405 1,059 1,250 1,107 1,389 1,245 1,958
Desvio Padrão
0,549 1,366 1,337 1,174 1,312 1,775 0,142 0,813
47
Tabela 6
Resultados da maximização para a função Riser
Configuração
A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
1,538 1,607 1,549 1,511 1,512 1,499 1,560 1,634
Mediana
1,423 1,295 1,399 1,352 1,403 1,255 1,353 1,628
Média
1,336 1,257 1,331 1,254 1,359 1,226 1,293 1,624
Desvio Padrão
0,194 0,218 0,174 0,218 0,113 0,229 0,174 0,009
Tabela 7
Resultados da maximização para a função De Jong F1
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,001
Mediana
0,000 0,000 0,000 0,000 0,000 0,000 0,009 0,005
Média
0,029 0,006 0,001 0,000 0,001 0,002 0,048 0,006
Desvio Padrão
0,088 0,011 0,002 0,000 0,003 0,002 0,077 0,004
Tabela 8
Resultados da maximização para a função Rosenbrock
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
0,000 0,000 0,000 0,000 0,000 0,000 0,062 0,012
Mediana
0,006 0,064 0,012 0,021 0,002 0,001 0,460 0,026
Média
0,012 0,130 0,028 0,267 0,026 0,121 0,489 0,027
Desvio Padrão
0,013 0,185 0,042 0,548 0,055 0,241 0,227 0,011
Tabela 9
Resultados da maximização para a função Rastrigin
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor
6,415 6,415 6,415 21,051 6,415 6,415 32,522 64,018
Mediana
17,362 20,794 21,853 33,349 13,134 36,443 50,739 70,950
Média
22,691 23,766 19,190 37,753 23,645 33,711 49,818 71,741
Desvio Padrão
17,892 18,484 7,440 13,121 21,995 27,604 7,884 6,857
48
Tabela 10
Resultados da minimização para a função Griewank
Configuração A
1
A
2
A
3
A
4
A
5
A
6
AG PSO
Melhor 0,002 0,002 0,002 0,002 0,002 0,002 1,815
1,044
Mediana 0,002 0,728 0,002 0,816 0,231 0,002 3,581
1,838
Média 0,328 0,936 0,315 0,813 0,408 0,195 3,586
1,958
Desvio Padrão 0,674 0,908 0,566 0,799 0,400 0,320 0,931
0,813
Os resultados do AG adaptativo para as funções De Jong F1, Griewank,
Rosenbrock e Rastrigin foram bastante satisfatórios. Em algumas configurações do
AG adaptativo, os resultados foram muito melhores que o AG clássico em todos os
valores observados (melhor, mediana e média). Porém, algumas configurações do
AG adaptativo foram piores em termos de média e mediana que o AG clássico. Isto
mostra que, apesar de encontrar melhores resultados, o AG adaptativo não é
constante em seu desempenho. Comparado ao PSO, o AG adaptativo só mostrou
melhores resultados com a função Rosenbrock e Griewank.
Já nos testes com a função do Riser o resultado foi melhor somente para
a configuração A
2
em relação ao AG clássico. Na mediana e na média houve uma
superação em três configurações, A
1
, A
3
e A
5
. Isso mostra que, apesar de não ter
havido uma larga vantagem com relação ao AG clássico, ele se mostrou um pouco
melhor na média de resultados. Porém o PSO superou o desempenho do AG
adaptativo com larga vantagem em todos os itens comparados.
Na configuração do AG adaptativo, quando os valores de δ
máx
e l (que
correspondem respectivamente à variação máxima de um operador em uma
adaptação e o limite da faixa em que se encontra o melhor indivíduo) aumentam,
mostrou um desempenho um pouco pior. É possível supor que variações muito
grandes nas taxas dos operadores prejudicam seu ajuste. Além disso, com o valor de
l alto, e conseqüentemente muitos indivíduos na mesma faixa do melhor, é provável
que o algoritmo tente aumentar demasiadamente a mutação interpretando que estes
se encontram muito aglomerados em torno do melhor. Isto prejudica a exploração de
um ótimo local.
Um fato que esses números não revelam é que a velocidade de
convergência do AG adaptativo foi muito maior que a do AG clássico. Em alguns
49
casos, na metade do processo de otimização, por volta de 100 gerações, o AG
adaptativo já alcançava um valor maior que o AG clássico alcançou em 200
gerações, como pode ser visto nas figuras 14 e 15.
Nestas figuras, a cor azul representa o individuo com melhor fitness e a
cor vermelha representa a media da população corrente.
Figura 14 – Gráfico da evolução da função do sistema de riser no AG clássico
Figura 15 – Gráfico da evolução da função do sistema de riser no AG adaptativo
Uma característica interessante que pode ser vista nestes gráficos é que a
distância entre a média (na figura 15 ela aparece sinuosa) e o melhor, no AG
adaptativo, é bem pequena. Isso se deve ao fato de a população final de cada
geração no AG adaptativo ser resultado de uma população intermediária muito
maior neste algoritmo do que a população intermediaria no AG clássico. No AG
adaptativo, esta população é resultado da aplicação de todos os operadores sem que
haja substituição da população original. Como já explicado anteriormente, no AG
adaptativo, cada operador é aplicado à população da geração anterior e seus filhos
não substituem os pais de imediato. Eles se mantêm à parte até que todos os
operadores sejam aplicados, quando então formam a população intermediária junto
50
com os indivíduos originais, onde estão os pais. Esta característica é positiva, pois,
além de preservar um eventual pai promissor que tenha gerado um filho ruim (pois o
pai não é imediatamente substituído pelo filho, como no AG clássico), a população
intermediária é bem maior, aumentando a chance de uma nova população com
média melhor.
51
Capítulo 8: Conclusão
8.1 – Comentários gerais
A adaptação dos parâmetros do AG durante o processo de otimização
mostra ser uma área de pesquisa com retorno satisfatório. Os resultados mostram
que uma análise do estado da busca, mesmo que sobrecarregando
computacionalmente o algoritmo, melhora o desempenho da otimização.
Um ponto negativo do processo é que, ao invés de configurar as taxas
dos operadores, agora é necessário configurar os parâmetros de adaptação. Este
problema é minimizado pela melhora do desempenho do algoritmo.
Um ponto positivo deste método é sua facilidade de compreensão e
implementação. Além disso, o modelo apresentado é bastante interessante por usar
um módulo de adaptação que pode ser usado da forma apresentada aqui ou de uma
outra forma que por ventura seja criada posteriormente.
Outro fator interessante é a versatilidade do modelo apresentado. Não
existe restrição com relação ao operador empregado. Qualquer operador inserido no
processo pode fazer parte da adaptação e ser utilizado da mesma forma que os
outros operadores. Mesmo um operador que, aparentemente, não traga benefícios à
população, pode ser útil a uma determinada população, em um determinado estágio
de otimização para um determinado problema. Não há necessidade do usuário ter
controle sobre esta decisão, pois o programa se encarregará de tomá-la quando for
necessário.
8.2 – Trabalhos Futuros
Somente quatro operadores foram submetidos ao processo de adaptação
neste trabalho. Futuramente, seria interessante submeter outros operadores do AG à
adaptação, tais como a seleção, o elitismo, o tamanho da população, a penalidade e a
própria função de fitness. Avaliando os resultados gerados por estes parâmetros, é
possível ajustá-los permitindo a melhoria do desempenho da otimização, assim
como é feito com os operadores já utilizados neste trabalho.
52
Para melhorar o desempenho da técnica apresentada e evitar a
convergência prematura é necessário aumentar a diversidade da população. Se um
novo indivíduo é criado em uma região promissora, mas possui um fitness baixo ele
acaba não sendo selecionado para as gerações futuras. Somente se ele apresentar um
fitness que permita a ele ser selecionado é que ele irá contribuir para a população.
Esta característica empobrece a diversidade da população impedindo que indivíduos
não tão bons, mas que contenham informações genéticas promissoras, contribuam
para melhorar a performance. Uma forma de corrigir este problema seria uma troca
aleatória entre alguns indivíduos não selecionados e alguns indivíduos da população
final.
Seria interessante realizar testes com outras configurações do AG
adaptativo assim como realizar os testes em mais funções de benchmark para ter
uma análise mais completa da técnica apresentada.
Um outro teste comparativo interessante seria estabelecer como critério
de parada do algoritmo o número de gerações em que não existe ganho em relação
ao melhor indivíduo. Este teste permite diferenciar os algoritmos em sua capacidade
de sair de um ótimo local.
53
Capítulo 10: Referências Bibliográficas
[1] HOLLAND, J.H., Adaptation in Natural and Artificial Systems. The University
of Michigan Press, 1st. ed. 1975 (The MIT Press, 2nd. ed. 1992)
[2] BONABEAU E., M. DORIGO & T. THERAULAZ, Swarm Intelligence: From
Natural to Artificial Systems, New York: Oxford University Press, 1999.
[3] DE CASTRO, L. N. & TIMMIS, J., Artificial Immune Systems: A New
Computational Intelligence Approach, Springer-Verlag, 2002
[4] CHARLES R. DARWIN (1859), The Origin of Species, Wordsworth Editions
Limited (1998).
[5] M. GIGER, D. KELLER, P. ERMANNI “AORCEA - An adaptive operator rate
controlled evolutionary algorithm” Science Direct - Computers and
Structures 85, pp. 1547–1561, 2007.
[6] ALBRECHT, CARL HORST Algoritmos Evolutivos Aplicados à Síntese e
Otimização de Sistemas de Ancoragem. Tese de D.Sc., COPPE/UFRJ, Rio
de Janeiro, RJ, Brasil, 2005.
[7] GOLDBERG, DAVID E. Genetic Algorithms in Search Optimization and
Machine Learning, 23
rd
Printing, Addison Wesley Longman, 1989.
[8] D1E1 J1ONG K., The analysis of the behavior of a class of genetic adaptive
systems., PhD thesis, Department of Computer Science, University of
Michigan, Ann Arbor, Michigan, 1975.
[9] SCHAFFER JD, CARUANA R, ESHELMAN L, DAS R. “A study of control
parameters affecting online performance of genetic algorithms for function
optimization”, In: Schaffer JD, editor. Proceedings of the 3
rd
international
conference on genetic algorithms, Morgan Kaufman; 1989. p. 51–60.
54
[10] GREFENSTETTE J. “Optimization of control parameters for genetic
algorithms”, Transactions on Systems, Man and Cybernetics, pp. 122–128,
1986.
[11] ANGELINE PJ. “Adaptive and self-adaptive evolutionary computations”.,
Computational intelligence: a dynamic systems perspective. IEEE Press pp.
152–63, 1995.
[12] RECHENBERG, I. “Evolutionsstrategie: Optimierung Technischer Systeme
nach Prinzipien der Biologischen Evolution”, Fromann-Holzboog, Stuttgart-
Bad Cannstatt, 1973.
[13] KAKAZU Y, SAKANASHI H, SUZUKI K. Adaptive search strategy for
genetic algorithms with additional genetic algorithms., vol.2, North-
Holland, Amsterdam, pp. 311–20. 1992.
[14] FREISLEBEN B, HARTFELDER. Optimization of genetic algorithms by
genetic algorithms. In: Albrecht R, Reeves C, Steele N, editors. Artificial
neural nets and genetic algorithms. Springer-Verlag; p. 392–9, 1993.
[15] BÄCK T. “Self-adaptation in genetic algorithms”. Proceedings of the first
European conference on artificial life. Cambridge: MIT Press; pp. 263–71,
1992..
[16] EIBEN AE, HINTERDING R, MICHALEWICZ Z. “Parameter control in
evolutionary algorithms”. IEEE Trans. Evolution Comput. (2):124–41,
1999.
[17] KENNEDY, J.; EBERHARDT, R. “Particle Swarm Optimization”, proc. IEEE
Conference on Neural Networks, pp. 1942 – 1948, 1995
55
[18] KENNEDY, J.; EBERHARDT, R. “A New Optimizer Using Particle Swarm
Theory”, Sixth International Symposium on Micro Machine and Human
Science, IEEE., pp. 39 – 43, 1995a
[19] EBERHARDT, R.C.; SHI, Y. “Comparing Inertia Weights and Constriction
Factors in Particle Swarm Optimization”, IEEE International Conference on
Evolutionary Computation, San Diego, California, pp. 84 – 88, 2000.
[20] EBERHARDT, R.C.; SHI, Y. “A Modified Particle Swarm Optimization”,
IEEE, pp. 1677 – 1681, 1998.
[21] CHATTERJEE, A., SIARRY, P., Nonlinear Inertia Weight Variation for
Dynamic adaptation in Particle Swarm Optimization. Computers &
Operations Research, Elsevier, Article in Press, 2004.
[22] EBERHARDT, R.C.; SHI, Y. “Multiobjective Optimization Using Dynamic
Neighborhood Particle Swarm Optimization”, IEEE, pp. 1677 – 1681, 2002.
[23] SHI , X. H. ; LIANG, Y. C.; LEE, H.P.; LU, C.; WANG. L. M. “An improved
GA and a novel PSO-GA-based hybrid algorithm”, Information Processing
Letters, Elsevier, Article in press, 2004.
[24] HE, S.; WU, Q.H.;. WEN, J.Y; SAUNDERS, J.R., PATON, R.C. “A particle
swarm optimizer with passive congregation”, Elsevier BioSystems 78, pp.
135 –147, 2004.
[25] VIEIRA, L. T. Otimização de Sistemas de Risers para Explotação de Petróleo
Offshore Através de Algoritmos Genéticos Paralelos. Tese de D.Sc.,
COPPE/UFRJ, Rio de Janeiro, RJ, Brasil, 2008.
[26] YAO, XIN; LIU, YONG “Fast Evolution Strategies” vol. 1213 of Lecture
Notes in Computer Science, (Berlin), Springer–Verlag, pp.151-161, 1997.
56
[27] De Jong K., The analysis of the behavior of a class of genetic adaptive
systems., PhD thesis, Department of Computer Science, University of
Michigan, Ann Arbor, Michigan, 1975.
[28] THOMSEN R, KRINK T. “Self-adaptive operator scheduling using the
religion-based EA”. In: Merelo JJ, editor. Parallel problem solving from
nature – PPSN VII. Berlin: Springer, pp. 214–23, 2002.
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