Monografia Santos, Mayckerson A.F.

Prévia do material em texto

UNIVERSIDADE FEDERAL DO MARANHÃO 
CENTRO DE CIÊNCIAS EXATAS E TECNOLOGIA 
CURSO DE CIÊNCIA DA COMPUTAÇÃO 
 
 
 
 
 
 
 
 
 
MAYCKERSON ALEXANDRE FRANCO SANTOS 
 
 
 
 
 
 
 
 
 
COMPUTAÇÃO NATURAL APLICADA À OTIMIZAÇÃO CONTÍNUA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
São Luís 
2008 
1 
 
 
MAYCKERSON ALEXANDRE FRANCO SANTOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
COMPUTAÇÃO NATURAL APLICADA À OTIMIZAÇÃO CONTÍNUA 
 
 
 
Monografia apresentada ao Curso de Ciência 
da Computação da Universidade Federal do 
Maranhão, para obtenção do grau de 
Bacharel em Ciência da Computação. 
 
 
Orientador: Prof. Dr. Alexandre César Muniz 
de Oliveira 
 
 
 
 
 
 
 
 
 
 
São Luís 
2008 
2 
 
 
 
Santos, Mayckerson Alexandre Franco 
Computação natural aplicada à otimização contínua / 
Mayckerson Alexandre Franco Santos – São Luís, 2008. 
 
 85 folhas. 
 
 Orientador: Alexandre César Muniz de Oliveira. 
 Monografia (Graduação) – Universidade Federal do 
Maranhão, Curso de Ciência da Computação, 2008. 
 
1. Ciência da Computação. 2. Métodos. 3. Otimização. 
4. Funções Contínuas. 5. Algoritmos. I. Título. 
CDU 004 
3 
 
 
MAYCKERSON ALEXANDRE FRANCO SANTOS 
 
 
 
 
 
COMPUTAÇÃO NATURAL APLICADA À OTIMIZAÇÃO CONTÍNUA 
 
 
 
Monografia apresentada ao Curso de Ciência 
da Computação da Universidade Federal do 
Maranhão, para obtenção do grau de 
Bacharel em Ciência da Computação. 
 
 
Aprovada em 14 / 07 /2008 
 
 
 
 
 
 
BANCA EXAMINADORA 
 
 
 
 
__________________________________________________ 
Prof. Alexandre César Muniz de Oliveira (Orientador) 
Doutor em Computação Aplicada 
Departamento de Informática (DEINF) 
 
 
 
__________________________________________________ 
Prof. Alexandre César Tavares Vidal 
Doutor em Engenharia Elétrica 
Departamento de Informática (DEINF) 
 
 
 
__________________________________________________ 
Prof.ª Valeska Martins de Souza 
Doutora em Engenharia da Informação 
Departamento de Matemática (DEMAT) 
4 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A Deus, fonte da vida. 
A minha esposa, pelo amor incondicional. 
A meus pais, pela educação. 
A meus sogros, pelo apoio em todas as 
horas. 
5 
 
 
 
 
 
 
AGRADECIMENTOS 
 
A Deus, pela força e coragem que me proporcionou em todos os 
momentos de minha vida. 
A minha esposa Karla, pelo amor e incentivo constantes. 
Aos meus pais, Isaias e Marú, pela vida e por tudo o que fizeram por mim. 
Aos meus sogros, Furtado e Silene, pelo apoio e cuidado. 
Aos meus irmãos, cunhados e cunhadas, tios e tias, e todos os familiares 
pelo apoio recebido. 
Ao professor Alexandre César Muniz de Oliveira, pela valiosa orientação e 
amizade. 
E a todos os demais professores e colegas que contribuíram para a 
realização desse trabalho. 
6 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
“Não tenho dúvida alguma de que qualquer 
homem ou mulher pode atingir o que eu 
atingi, se ele ou ela fizerem o mesmo 
esforço e cultivarem a fé e a esperança. 
Trabalho sem fé é como a tentativa de 
alcançar o fundo de um buraco sem fundo.” 
(Mahatma Gandhi) 
7 
 
 
 
 
 
RESUMO 
 
Este trabalho traz um estudo sobre otimização de parâmetros de funções contínuas no 
qual são apresentados algoritmos que utilizam diferentes estratégias de busca, desde 
algoritmos simples como o de Busca Aleatória até algoritmos mais elaborados como o 
Algoritmo Genético com Fitness Sharing. Apresentam-se os algoritmos destacando 
suas características principais e suas diferenças com relação aos demais. Para efeito 
comparativo dos algoritmos é aqui apresentada a ferramenta OAT (Optimization 
Algorithm Toolkit), software livre que possui grande potencial para o uso em testes e 
experimentos de algoritmos. Destaca-se ainda o framework OAT com o objetivo de 
estendê-lo futuramente, agregando novos algoritmos e problemas, com a ampla 
reutilização de suas classes. 
 
Palavras-chave: Ciência da computação. Métodos. Otimização. Funções contínuas. 
Algoritmos. 
8 
 
 
 
 
 
ABSTRACT 
 
 
This work brings a study on optimizing parameters of continuous functions for which are 
presented algorithms that use different strategies for searching, from simple algorithms 
such as Random Search ones to more elaborate as the Fitness Sharing Genetic 
Algorithm. These algorithms are presented highlighting its main characteristics and their 
differences with each other. For purposes of comparative algorithms, a tool is presented: 
OAT (Optimization Algorithm Toolkit), a free software that has great potential for use in 
experiments and tests of algorithms. This work further highlights the framework OAT 
aiming to extend it in future, adding new algorithms and problems with wide reuse of 
their classes. 
 
Keywords: Computer Science, Methods, Optimization, Continuous Functions, 
Algorithms. 
9 
 
 
SUMÁRIO 
 
 LISTA DE SIGLAS .................................................................................. 11 
 LISTA DE FIGURAS .............................................................................. 12 
 LISTA DE TABELAS .............................................................................. 14 
1 INTRODUÇÃO ........................................................................................ 15 
2 COMPUTAÇÃO NATURAL ................................................................... 17 
2.1 Computação Inspirada na Natureza .................................................... 20 
2.2 Estudo sobre a Natureza através da Computação ........................... 20 
2.3 Computação com Mecanismos Naturais ............................................ 22 
3 FORMULAÇÃO MATEMÁTICA DO PROBLEMA DE OTIMIZAÇÃO ... 23 
4 MÉTODOS PARA OTIMIZAÇÃO DE FUNÇÕES .................................. 24 
4.1 Busca Aleatória (Random Search) ...................................................... 26 
4.2 Subida de Encosta com Mutação (Mutation Hill Climber) ............... 26 
4.3 Simulated Annealing ............................................................................ 27 
4.4 Otimização Extrema Generalizada ...................................................... 29 
4.5 Nuvem de Partículas (Particle Swarm) ............................................... 32 
4.6 CLONALG ……………………………...................................................... 35 
4.7 OptaiNET ……………………………...................................................... 39 
4.8 Algoritmo Genético com Fitness Sharing .......................................... 44 
5 OAT – OPTIMIZATION ALGORITHM TOOLKIT .................................. 47 
5.1 Diagramas de Classes ......................................................................... 54 
5.2 Simulações e experimentos ............................................................... 58 
5.2.1 Comportamento dos algoritmos ......................................................... 60 
10 
 
 
5.2.2 Comparação de desempenho .............................................................. 70 
6 CONCLUSÃO ....................................................................................... 80 
 REFERÊNCIAS ......................................................................................82 
 
 
 
11 
 
 
 
 
 
LISTA DE SIGLAS 
 
2D - Duas dimensões 
3D - Três dimensões 
AG - Algoritmo Genético 
BFO - Binary Function Optimization 
CFO - Continuous Function Optimization 
FSGA - Fitness Sharing Genetic Algorithm 
GEO - Generalized Extremal Optimization 
GUI - Graphic User Interface 
OAT - Optimization Algorithm Toolkit 
PSO - Particle Swarm Optimization 
SA - Simulated Annealing 
SIA - Sistema Imunológico Artificial 
TSP - Traveling Salesman Problem 
12 
 
 
LISTA DE FIGURAS 
 
Figura 2.1 Integração de linhas de pesquisa para o advento da 
 computação natural .............................................................................. 18 
Figura 2.2 Três principais ramos da computação natural ..................................... 19 
Figura 4.1 Representação do epítopo e paratopo ................................................. 41 
Figura 5.1 Tela inicial do OAT ............................................................................... 48 
Figura 5.2 Screenshot da tela do Explorer ............................................................. 49 
Figura 5.3 Diagrama de Classes do domínio CFO................................................. 55 
Figura 5.4 Diagrama de Classes do Problema da Função Ackley ......................... 56 
Figura 5.5 Diagrama de Classe do Algoritmo de PSO .......................................... 57 
Figura 5.6 Gráficos das Funções Contínuas ..........................................................58/59 
Figura 5.7 Forma de apresentação dos experimentos de comportamento ........... 60 
Figura 5.8 Snapshots da Execução do FSGA sobre a Função Ackley .................. 61 
Figura 5.9 Snapshots da Execução do FSGA sobre a Função Rastringin ............. 61 
Figura 5.10 Snapshots da Execução do FSGA sobre a Função de Jong 4 ............ 62 
Figura 5.11 Snapshots da Execução do FSGA sobre a Função de Jong 5 ............ 62 
Figura 5.12 Snapshots da Execução do Mutation Hill Climbing 
 sobre a Função Ackley.......................................................................... 63 
Figura 5.13 Snapshots da Execução do Mutation Hill Climbing 
 sobre a Função Rastringin .................................................................... 64 
Figura 5.14 Snapshots da Execução do Mutation Hill Climbing 
 sobre a Função de Jong 4 .................................................................... 64 
13 
 
 
Figura 5.15 Snapshots da Execução do Mutation Hill Climbing 
 sobre a Função de Jong 5 .................................................................... 65 
Figura 5.16 Snapshots da Execução do CLONALG sobre a Função Ackley .......... 66 
Figura 5.17 Snapshots da Execução do CLONALG sobre a Função Rastringin .... 66 
Figura 5.18 Snapshots da Execução do CLONALG sobre a Função de Jong 4 ..... 67 
Figura 5.19 Snapshots da Execução do CLONALG sobre a Função de Jong 5 ..... 67 
Figura 5.20 Snapshots da Execução do GEO sobre a Função Ackley ................... 68 
Figura 5.21 Snapshots da Execução do GEO sobre a Função Rastringin .............. 69 
Figura 5.22 Snapshots da Execução do GEO sobre a Função de Jong 4............... 69 
Figura 5.23 Snapshots da Execução do GEO sobre a Função de Jong 5 .............. 70 
Figura 5.24 1º Gráfico de Desempenho em Melhor Solução do Experimento 1 ..... 72 
Figura 5.25 2º Gráfico de Desempenho em Melhor Solução do Experimento 1 ..... 72 
Figura 5.26 Gráfico de Desempenho em Tempo de Execução do Experimento 1 .. 73 
Figura 5.27 1º Gráfico de Desempenho em Melhor Solução do Experimento 2 ..... 74 
Figura 5.28 2º Gráfico de Desempenho em Melhor Solução do Experimento 2 ..... 75 
Figura 5.29 Gráfico de Desempenho em Tempo de Execução do Experimento 2 .. 76 
Figura 5.30 1º Gráfico de Desempenho em Melhor Solução do Experimento 3 ..... 77 
Figura 5.31 2º Gráfico de Desempenho em Melhor Solução do Experimento 3 ..... 78 
Figura 5.32 Gráfico de Desempenho em Tempo de Execução do Experimento 3 .. 79 
 
14 
 
 
 
 
 
 
 
LISTA DE TABELAS 
 
Tabela 5.1 Especificação das Funções Avaliadas .................................................. 59 
Tabela 5.2 Tabela de Valores de Melhor Solução do Experimento 1 ..................... 72 
Tabela 5.3 Tabela de Valores de Tempo de Execução do Experimento 1 ............. 73 
Tabela 5.4 Tabela de Valores de Melhor Solução do Experimento 2 ..................... 74 
Tabela 5.5 Tabela de Valores de Tempo de Execução do Experimento 2 ............. 75 
Tabela 5.6 Tabela de Valores de Melhor Solução do Experimento 3 ..................... 77 
Tabela 5.7 Tabela de Valores de Tempo de Execução do Experimento 3 ............ 78 
15 
 
 
1 INTRODUÇÃO 
 
Os problemas de otimização são focados, em sua essência, na busca por 
maximizar ou minimizar uma função numérica de várias variáveis, num contexto em que 
podem existir restrições. Estas funções e restrições estão intimamente ligadas aos 
valores assumidos, durante a execução da otimização, pelas variáveis do projeto. 
Entre as vantagens dos processos de otimização destacam-se: 
• Diminuição do tempo dedicado ao projeto; 
• Obtenção de algo melhor; 
• Tratamento simultâneo de grande quantidade de variáveis; 
• Menor custo. 
Cientistas e engenheiros computacionais vêm buscando, em diversas linhas 
de pesquisa, formas de implementar algoritmos para otimização. Nesta busca, diversos 
já foram desenvolvidos. 
Este trabalho está focado em estudar alguns destes algoritmos e fazer um 
comparativo entre estes. Para o estudo comparativo será utilizada a ferramenta OAT 
(Optimization Algorithm Toolkit). 
Os algoritmos foram selecionados de forma que representassem a 
diversidade de teorias que estão sendo desenvolvidas, principalmente na área da 
Computação Natural. Incluiu-se ainda o algoritmo de busca aleatória, este selecionado 
apenas para base de comparação de um algoritmo simples com os demais. 
A ferramenta OAT foi desenvolvida por Jason Brownlee buscando juntar em 
um só lugar diferentes tipos de abordagens, com funcionalidades para execução de 
16 
 
 
simulações e experimentos científicos. Esta ferramenta possui ainda o condão de tirar 
da obscuridade métodos não conhecidos, servindo como meio verificação de quais 
destes valem a pena ser estudados e quais áreas ainda estão abertas, sem pesquisa e 
projetos em andamento. Ela foi escolhida para o desenvolvimento deste trabalho graças 
a tais funcionalidades e no intuito de, através do estudo da estrutura de classes, fazer 
extensões da mesma com métodos desenvolvidos em nosso meio. 
Este trabalho está dividido em capítulos, sendo este o primeiro e os demais 
como se segue. No capítulo 2 será apresentada uma visão geral da Computação 
Natural. O capítulo 3 traz a formalização matemática do problema de Otimização. No 
capítulo 4 serão mostrados métodos aplicados à otimização baseados em Busca Global 
e em princípios de Computação Natural. O capítulo 5 traz a apresentação da 
ferramenta OAT – Optimization Algorithm Toolkit com seus principais diagramas de 
classes, descritos para o devido entendimento do funcionamento do mesmo e para dar 
base a uma posterior reutilização de seu código visto que é um software livre. O 
capítulo 5 apresenta ainda, experimentos com os algoritmos de otimização expostos no 
Capítulo 3 realizados com o OAT, assim como um comparativo de seus resultados e 
comportamentos. No capítulo 6 serão descritas as conclusões do trabalho realizado e 
sugestões de trabalhos futuros. 
17 
 
 
2 COMPUTAÇÃO NATURAL 
 
A terminologia computação natural vem sendo empregada na literatura para 
descrever todos os sistemas computacionaisdesenvolvidos com inspiração ou 
utilização de algum mecanismo natural ou biológico de processamento de informação 
(Ballard, 1999; Gramß et al., 2001; Flake, 2000; Paton et al., 2003; de Castro e Von 
Zuben, 2004). 
A computação natural é a forma computacional dos processos de análise e 
síntese da natureza para o desenvolvimento de sistemas “artificiais”, ou ainda como a 
utilização de meios e mecanismos naturais para realizar computação. Importando 
ressaltar que o termo “artificial” serve apenas para diferenciar que o objeto de estudo 
fora desenvolvido por seres humanos e não pela evolução das espécies. 
Tem-se que a computação natural é constituída, em seus fundamentos, por 
novas abordagens computacionais caracterizadas por uma maior proximidade com a 
natureza. E os principais objetivos desta proximidade são: desenvolver novas 
ferramentas matemáticas e computacionais para resolução de problemas complexos 
das mais diversas áreas do conhecimento; projetar dispositivos para emulação, 
simulação, modelagem e descrição de sistemas e fenômenos naturais; sintetizar novas 
formas de vida (vida artificial); e a utilização de mecanismos naturais para o 
desenvolvimento de um novo paradigma da computação conhecido como wetware1, 
este vindo para complementar e/ou suplementar as atuais arquiteturas baseadas em 
silício e arquitetura de Von Newmman (Vargas, 2005; de Castro, 2004). 
 
 
1
 Wetware é um tipo novo de hardware desenvolvido com o uso de matéria-prima biológica. 
18 
 
 
A computação natural geralmente enfatiza modelos altamente simplificados e 
abstratos da natureza (A lâmina de Occam - Occam’s razor2). As razões para um 
tratamento simplificado são várias, das quais podemos destacar: 
• Muitas simplificações são necessárias para tornar a computação 
tratável; 
• Pode ser vantajoso destacar as características mínimas de um 
sistema que permitem o uso de algum de seus aspectos particulares; 
• O uso de ‘modelos’ simplificados é suficiente para atingir os objetivos 
esperados; e 
• Nem sempre são conhecidos os detalhes do fenômeno/sistema 
natural observado/estudado. 
 
 
 
 
 
 
 
 
 
Figura 2.1: Integração de linhas de pesquisa para o advento da computação natural. 
 
 
2
 Princípio proposto por William Occam, filósofo e teólogo franciscano, nascido em 1285, na Inglaterra, 
que diz que a teoria mais simples é normalmente a mais correta. 
Es
tu
do
s 
e
xp
e
rim
en
ta
is 
Es
tu
do
s 
te
ór
ico
s 
Observações 
empíricas 
 
Computação 
Natural 
 
Outras linhas de 
pesquisa 
 
Síntese de 
fenômenos 
Novas formas 
de resolver 
problemas 
Novos 
paradigmas de 
computação 
19 
 
 
Pode-se dividir a computação natural em três grandes sub-áreas (de Castro 
e Von Zuben, 2004): 
• Computação inspirada na natureza; 
• Estudo da Natureza através da computação; e 
• Computação com mecanismos naturais. 
Estas sub-áreas da computação natural tem proporcionado grandes 
descobertas em ferramentas computacionais para a solução de problemas complexos 
de engenharia e permitindo a geração de novos paradigmas de computação. 
A computação natural é uma linha de pesquisa promissora, não só por já 
mostrar resultados concretos e convincentes pela aplicação de ferramentas criadas 
exclusivamente com base em seus princípios, mas porque diversos aspectos da 
biologia podem ser mais bem tratados tendo em mãos ferramentas computacionais 
apropriadas. 
 
 
 
 
 
Figura 2.2: Três principais ramos da computação natural 
 
Nos subitens que seguem será tratado cada ramo da Computação Natural de 
forma separada. 
 
 
Computação Natural 
 
PARTE I 
Computação Inspirada 
na Natureza 
PARTE II 
Estudo sobre a 
Natureza Através da 
Computação 
 
PARTE III 
Computação com 
Mecanismos Naturais 
20 
 
 
2.1 Computação Inspirada na Natureza 
 
Através da observação de descoberta de inúmeros princípios e teorias a 
respeito da natureza, como as Leis de Newton, com o desenvolvimento de modelos, os 
pesquisadores das áreas de engenharia e computação notaram o grande potencial 
destes para a implementação de sistemas computacionais para a resolução de 
problemas. 
Os principais segmentos desta subárea da computação natural são: sistemas 
imunológicos artificiais, algoritmos evolutivos, redes neurais artificiais e inteligência 
coletiva (swarm intelligence). 
Este tipo de computação será abordado com maiores detalhes no Capítulo 4 
com a demonstração de alguns de seus algoritmos. 
 
2.2 Estudo sobre a Natureza através da Computação 
 
Ao contrário da primeira, o estudo dos fenômenos naturais através da 
computação é uma abordagem sintética objetivando reproduzir ou criar padrões, 
formas, comportamentos e organismos que não necessariamente se assemelham à 
vida como nós a conhecemos. Esta abordagem pode gerar fenômenos nunca 
observados na natureza, mas que podem ser qualificados como “naturais” por possuir 
características suficientes para tal. O seu objetivo é usar a computação para simular e 
emular fenômenos naturais de forma não-determinística. 
O estudo da natureza através da computação possui duas áreas de estudo 
principais: vida artificial (ALife) e geometria fractal. 
21 
 
 
A Vida Artificial é definida como o estudo de sistemas feitos pelo homem, 
mas que exibem comportamentos característicos de sistemas naturais vivos. A Vida 
Artificial complementa as ciências biológicas tradicionais preocupadas com a análise de 
organismos vivos através da síntese em computadores ou outros meios artificiais de 
comportamentos similares àqueles observados em seres vivos. Através da extensão 
dos fundamentos empíricos sobre os quais a biologia está baseada para além da vida 
baseada em carbono que evoluiu na Terra, a Vida Artificial pode contribuir para a 
biologia teórica localizando a vida-como-nós-a-conhecemos dentro de um contexto 
maior da vida-como-ela-poderia-ser (Langton,1988; p.1). Ou seja, ALife é a abordagem 
sintética ou virtual para o estudo de padrões, comportamentos, sistemas e organismos 
que se assemelham à vida. 
Com relação à geometria fractal, esta resulta da visualização computacional 
de modelos de estruturas e de processos naturais, formando imagens, animações e 
sistemas interativos. E para tal pode-se usar diversas técnicas, entre elas: autômatos 
celulares (Ilachinski, 2001; Wolfram, 1994), sistemas de partículas (Reeves, 1983), 
sistemas de Lindenmayer ou sitemas-L (Lindenmayer, 1968), movimento Browniano 
(Fournier et al., 1982; Voss, 1985), etc. Um fractal ou uma estrutura fractal é por 
definição uma estrutura na qual partes da mesma se assemelham ao todo, ou seja, 
existem partes auto-similares, estatisticamente, dentro da estrutura global. Isto indica a 
presença do fenômeno de escala e de um nível de tendência, o qual pode ser medido 
através da dimensão fractal, que é uma medida de complexidade. (Rubi, 2007). 
 
 
 
22 
 
 
2.3 Computação com Mecanismos Naturais 
 
Na procura de formas alternativas à criação de chips em pastilhas de silício, 
que de acordo com as previsões esgotará seu potencial de miniaturização em no 
máximo 10 anos se for tomada por base a Lei de Moore que profere que a quantidade 
de transistores em um chip dobra a cada dois anos ou ano e meio, os cientistas e 
engenheiros computacionais estão buscando na natureza os meios para a criação de 
um novo paradigma computacional. 
Os meios encontrados, até agora, foram basicamente de dois tipos os 
baseados em biomoléculas e os baseados em bitsquânticos. O primeiro normalmente 
denominado computação molecular (Păun et al., 1998; Gramß et al., 2001; Calude e 
Păun, 2001; Păun e Cutkosky, 2002; Sienko et al., 2003) e o segundo conhecido como 
computação quântica (Hirvensalo, 2000; Nielsen e Chuang, 2000; Pittenger, 2000). 
Na computação molecular, as biomoléculas são usadas como meio para 
armazenar informação e as técnicas de engenharia molecular (genética) são usadas 
para manipular estas moléculas de forma a realizar processamento de informação. 
Cumpre observar que esta abordagem se baseia na sofisticação e eficiência das 
técnicas de engenharia genética. A computação quântica, por outro lado, armazena 
informação em bits quânticos e manipula esta informação usando princípios da 
mecânica quântica. 
 
 
 
 
23 
 
 
3 FORMULAÇÃO MATEMÁTICA DO PROBLEMA DE OTIMIZAÇÃO 
 
O problema de otimização consiste matematicamente na determinação do 
mínimo, ou máximo, do valor da função objetivo no espaço de projeto definido pelas 
restrições. Ele é tradicionalmente formulado como um problema de minimização sem 
perda de generalização, já que sempre é possível transformar um problema de 
maximização em um problema de minimização (Arora, 1989, Vanderplaats, 1998). 
Neste trabalho, a não ser que mencionado em contrário, o problema de projeto ótimo 
será sempre considerado como um problema de minimização. Para um problema onde 
há apenas uma função objetivo ele pode ser posto na forma de (Vanderplaats, 1998): 
 
Minimizar: F(x) (função objetivo) (1) 
Sujeito à: 
 gj(x) ≤ 0 j = 1, ..., m (restrições de desigualdade) (2) 
 hk(x) = 0 k = 1, ..., l (restrições de igualdade) (3) 
 xi_inf ≤ xi ≤ xi_sup i = 1, ..., n (restrições laterais) (4) 
Onde, xT = {x1 x2 x3 … xn} (variáveis de projeto) 
e xi_inf e xi_sup representam os limites inferior e superior, respectivamente, ao valor de 
cada variável de projeto xi. 
As funções definidas em (1), (2) e (3) podem ser lineares ou não, explícitas 
ou implícitas em x. 
 
 
 
24 
 
 
4 MÉTODOS PARA OTIMIZAÇÃO DE FUNÇÕES 
 
Nas últimas quatro décadas, foram desenvolvidas diversas técnicas 
numéricas baseadas em busca local para o problema do projeto ótimo, esta diversidade 
resulta de uma constatação teórica e prática: a eficiência de tais técnicas depende do 
problema a ser resolvido. Pode-se dizer que não há, entre estas técnicas, uma que se 
sobressaia às outras, mas sim uma que é mais adequada a determinado problema 
(Sousa, 2003). 
Técnicas clássicas de otimização são confiáveis, porém, quando 
confrontadas espaços complexos, como com funções não contínuas ou não convexas 
ou com diversas variáveis, as mesmas podem apresentar algumas dificuldades 
numéricas e problemas de robustez. 
Para o tratamento de espaços de projeto complexos, foram desenvolvidas 
técnicas de otimização baseadas em busca global, técnicas estas que possuem 
mecanismos capazes de escapar de ótimos locais, porém para que sejam eficazes 
necessitam de muitas chamadas à função objeto. Quando estas funções objeto 
possuem grande custo computacional, a técnica se torna impraticável. Nestes casos 
apesar de limitadas a sub-ótimos as técnicas de busca local são mais utilizadas. 
De forma geral, os métodos clássicos possuem como grande vantagem, o 
baixo número de avaliações da função objetivo, o que faz com que tenham 
convergência rápida. Contudo, estes métodos têm uma dificuldade para trabalhar com 
mínimos locais, ao se depararem com mínimos locais estes métodos não conseguem 
avançar na busca, convergindo prematuramente, sem encontrar o mínimo global. Em 
contraponto nos métodos de otimização baseados em busca global, a função objetivo é 
25 
 
 
avalizada várias vezes, sendo possível trabalhar com vários pontos ao mesmo tempo 
em uma iteração. Isto eleva o custo computacional destes métodos. Entretanto, este 
fato é compensado pela menor chance que estes métodos têm de serem limitados a 
mínimos locais, além de possuírem vantagens quanto à implementação, robustez e 
tratarem problemas não-contínuos. 
Devido ao grande custo computacional de se chegar na prática ao ótimo da 
função, foram desenvolvidos algoritmos que tem a capacidade de fornecer soluções 
satisfatórias, muito próximas do ótimo, a um custo computacional razoável. Estes 
algoritmos são chamados de heurísticas. Apesar de eficientes em suas funções, as 
heurísticas, são muito específicas, indicadas na resolução de um determinado problema 
e dependendo da sua forma de construção, também podem ficar estagnadas em ótimos 
locais. Em razão destas dificuldades, na década de 90 surgiu uma nova classe de 
métodos de otimização baseados em busca global, estes inspirados em eventos da 
natureza. Estes métodos, chamados de metaheurística, possuem a característica de ser 
flexíveis, podendo a partir de pequenas adaptações serem usados nos mais diversos 
tipos de problema, cada metaheurística pode conter diversas heurísticas trabalhando de 
forma independente em cada iteração. 
Para o devido entendimento do que foi dito, nos itens seguintes serão 
descritos métodos de otimização, o primeiro de busca aleatória servirá na verdade 
apenas como base de comparação devido a sua simplicidade. O segundo uma 
heurística de subida de encosta. Seguindo serão descritas metaheurísticas, iniciando 
com duas baseadas em fenômenos físicos e quatro bioinspiradas. Os métodos serão 
descritos de forma a destacar suas características para posterior comparação de 
comportamento e desempenho. 
26 
 
 
4.1 Busca Aleatória (Random Search) 
 
Os métodos de busca aleatória são considerados os menos eficientes, 
porém os de mais simples implementação. A quantidade de memória que é requerida 
para o código faz deste método um candidato ideal para o uso em ambientes 
computacionais limitados. A técnica é considerada como de busca global, pois devido a 
geração uniforme de variáveis aleatórias é possível explorar a totalidade da superfície 
ou função custo. 
 
4.2 Subida de Encosta com Mutação (Mutation Hill Climber) 
 
Hill climbing é um método de busca local que utiliza um procedimento de 
melhora iterativa (iterative improvement). A estratégia é aplicada a um único ponto x 
(solução candidata) no espaço de busca. 
Um Hill Climbing Padrão pode ter seu algoritmo descrito como segue: 
1. Inicialize (aleatoriamente) o ponto x na região factível do problema; 
2. A cada iteração um novo ponto x' é selecionado aplicando-se uma 
pequena perturbação no ponto atual, ou seja, selecionando-se um 
ponto x' que esteja na vizinhança de x, x' N(x); 
3. Se este novo ponto apresenta um melhor valor para a função de 
avaliação, então o novo ponto torna-se o ponto atual; 
27 
 
 
4. O método é terminado quando nenhuma melhora significativa é 
alcançada, um número fixo de iterações foi efetuado, ou um objetivo 
foi atingido. 
Como pode ser verificado, o algoritmo de hill climbing padrão realiza uma 
busca local em torno de seu ponto inicial. O algoritmo abordado, no entanto, foi 
implementado de uma forma ligeiramente diferente, a perturbação utilizada para gerar o 
novo ponto foi implementada na forma de mutação, daí o nome do algoritmo, esta 
mutação ocorre em nível de bits do ponto. 
 
4.3 Simulated Annealing 
 
O algoritmo de simulated annealing – SA proposto por Kirkpatrick et al. 
(1983) foi inspirado pelo processo de recozimento (annealing) de sistemas físicos. Este 
algoritmo é baseado no procedimento de Metropolis et al. (1953) originalmente proposto 
como uma estratégia de determinação de estados (configurações) de equilíbrio de uma 
coleção de átomos a uma dada temperatura. As idéias básicas têm suas origens em 
termodinâmica estatística, ramo dafísica responsável por apresentar predições teóricas 
sobre o comportamento de sistemas macroscópicos baseados nas leis que governam 
seus átomos. Kirkpatrick et al. (1983) perceberam que existe uma semelhança entre o 
procedimento de recozimento estudado com o algoritmo de Metropolis e processos de 
otimização combinatória. Uma analogia com o recozimento de sólidos poderia fornecer 
uma estrutura para o desenvolvimento de um algoritmo genérico de otimização capaz 
de escapar de ótimos locais. 
28 
 
 
 O algoritmo de simulated annealing foi desenvolvido baseado em um 
procedimento utilizado para levar um material a seu estado de equilíbrio máximo, ou 
seja, a um estado de energia mínima. 
O processo simulado neste algoritmo funciona da seguinte forma: um 
determinado material é inicialmente aquecido a uma alta temperatura, de forma que ele 
derreta e seus átomos possam se mover com relativa liberdade. A temperatura desta 
substância derretida é lentamente reduzida de forma que, a cada temperatura, os 
átomos possam se mover o suficiente para adotarem uma orientação mais estável. Se a 
substância derretida for resfriada apropriadamente, seus átomos serão capazes de 
atingir um estado de equilíbrio máximo (energia mínima), produzindo um cristal. Caso 
contrário, um vidro ou outra substância (quebradiça) semelhante será produzida. Ao 
processo de aquecimento seguido de um resfriamento lento denominamos de 
recozimento (annealing). 
Uma descrição do algoritmo do Simulated Annealing pode ser dada por: 
1. Inicialize (aleatoriamente) um ponto x na região factível do 
problema; 
2. A cada iteração um novo ponto x' é selecionado aplicando-se uma 
pequena perturbação ao ponto atual, ou seja, selecionando-se um 
ponto x' que esteja na vizinhança de x, x' N(x); 
3. Determine a energia de cada uma destas configurações, E(x) e 
E(x'), e verifique a variação na energia do sistema: ∆E = E(x') - 
E(x); 
29 
 
 
4. Se ∆E ≤ 0, então x' torna-se o ponto atual; senão, a probabilidade 
de x' ser aceito como o ponto atual é dada por um caso particular 
da distribuição de Boltzmann-Gibbs, ou seja, P(∆E) = exp(-∆E/T). 
5. O método é terminado quando nenhuma melhora significativa é 
alcançada, um número fixo de iterações foi efetuado, ou a 
temperatura T atingiu seu valor mínimo. 
O parâmetro T é iniciado com um valor elevado e é lentamente reduzido 
durante o processo de busca. Geralmente sendo implementado um decrescimento 
geométrico para T; T ← n.T. A seqüência de temperaturas e o número de rearranjos 
dos parâmetros até a chegada a um estado de equilíbrio a cada temperatura é 
denominado de seqüência de recozimento (annealing Schedule ) (Kirkpatrick et al., 
1983). 
 
4.4 Otimização Extrema Generalizada 
 
O algoritmo GEO (Generalized Extremal Optimization), é uma metaheurística 
de otimização global (Sousa e Ramos, 2002; Sousa et al., 2003a, 2003b) desenvolvida 
recentemente como uma proposta de generalização do algoritmo τ-EO (Boettcher e 
Percus, 2001). Assim como os métodos Simulated Annealing e os Algoritmos 
Genéticos, GEO é um algoritmo estocástico cuja inspiração origina-se na analogia de 
processos observados na natureza. 
GEO destina-se, primeiramente, a resolver problemas de otimização 
complexos, onde pouco ou nada se conhece a respeito do espaço de busca viável e 
30 
 
 
inviável da função a ser otimizada. Pode ser aplicados a praticamente qualquer 
problema de otimização contínua ou combinatória, não convexo ou disjunto, com ou 
sem restrições, podendo, inclusive, serem aplicados a problemas com miscelânea de 
variáveis reais, inteiras ou discretas. É de fácil implementação e usa apenas valores da 
função objetivo, sem derivadas. Não requer nem mesmo o fornecimento de um ponto 
de partida situado no espaço viável. Esta universalidade de aplicação, aliada ao fato do 
GEO possuir apenas um parâmetro de ajuste, τ, constitui-se numa de suas maiores 
virtudes. 
O algoritmo GEO é composto dos seguintes passos: 
1. Inicialize aleatoriamente uma seqüência binária de comprimento L que 
codifica N variáveis de projeto. Cada variável é codificada em uma 
“sub-seqüência” de comprimento lj (j = 1, N). Para uma configuração 
inicial de bits C, calcule o valor da função objetivo V e faça Cmelhor = C 
e Vmelhor = V. 
2. Para cada bit da seqüência, em uma dada iteração, faça: 
a. Mude o valor do bit (de 0 para 1 ou 1 para 0) e calcule o valor 
da função objetivo Vi, da configuração de bits Ci, 
b. Atribua ao bit um índice de adaptabilidade ∆V = (Vi – Vmelhor). 
Ele indica o ganho (ou perda) que se têm ao mudar o valor do 
bit, comparado com o melhor valor encontrado para a função 
objetivo até o momento. 
c. Retorne o bit ao seu valor original. 
3. Ordene os bits de acordo com os seus índices de adaptabilidade, de 
k = 1 para o menos adaptado à k = L, para o mais adaptado. Em um 
31 
 
 
problema de minimização valores altos de ∆Vi terão maior “rank”, 
enquanto que em problemas de maximização ocorre o oposto. Se 
ocorrer de dois ou mais bits apresentarem o mesmo valor para ∆Vi 
eles são ordenados aleatoriamente com distribuição uniforme. 
4. Escolha com igual probabilidade um bit candidato i para sofrer 
mutação (mudar de 0 para 1 ou de 1 para 0). Gere um número 
aleatório RAN, com distribuição uniforme, no intervalo [0,1]. Se Pi(k) = 
k-τ for maior ou igual à RAN, o bit é modificado. Se não, o processo se 
repete até que um bit seja confirmado para ser modificado. 
5. Para o bit escolhido para sofrer mutação faça C = Ci e V = Vi. 
6. Se V < Vmelhor ( V > Vmelhor para um problema de maximização) então 
faça Vmelhor = V e Cmelhor = C. 
7. Repita os passos 2 a 6 até que um dado critério de parada seja 
satisfeito. 
8. Retorne Cmelhor e Vmelhor. 
Restrições de igualdade e desigualdade são tratadas simplesmente 
atribuindo aos bits que, ao se modificarem, levarem a soluções inviáveis, um alto índice 
de adaptabilidade. 
No GEO bits que, ao se modificarem, levem a soluções inviáveis sempre 
serão mais aptos que bits que, ao se modificarem, levem a soluções viáveis, e a todos 
eles é atribuído o mesmo índice de adaptabilidade. Não é feita distinção entre os 
mesmos e assim o ordenamento desses bits é feito de maneira aleatória com igual 
probabilidade. 
32 
 
 
Note-se que o procedimento adotado para tratar as restrições não é o 
mesmo que o comumente usado em problemas de otimização, e tido como 
potencialmente gerador de soluções sub-ótimas: o uso de funções penalidade. A função 
objetivo no GEO não é modificada, apenas modificações em bits que levem a regiões 
inviáveis do espaço de projeto têm menos chance de ocorrer. É importante salientar 
que o GEO pode operar sem nenhum problema com soluções inviáveis. Durante a 
busca pelo ótimo o algoritmo pode se mover inclusive por regiões inviáveis do espaço 
de projeto e mesmo iniciar a busca a partir de uma solução inviável. Isto dá uma grande 
flexibilidade ao algoritmo que pode, por exemplo, ser aplicado a problemas onde o 
espaço de projeto apresente regiões viáveis desconectadas, como na otimização de 
estruturas submetidas a oscilações harmônicas (Johnson, 1976). 
 
4.5 Nuvem de Partículas (Particle Swarm) 
 
A proposta do algoritmo surgiu de alguns cientistas que desenvolveram 
simulações computadorizadas do movimento de organismos, tais como bandos de 
pássaros e cardumes de peixes. Estas simulações foram fortemente baseadas na 
manipulação das distâncias entre os indivíduos, ou seja, o sincronismo no 
comportamento do bando era compreendido como um esforço dos pássaros em manter 
uma distância “ótima” entre eles. O sócio-biologista E. O. Wilson fez a conexão entre 
estas simulações e os problemas de otimização (Brandstätter e Baumgartner,2002). 
Em teoria, ao menos, os membros individuais de um bando (ou nuvem) 
podem se aproveitar das descobertas e da experiência anterior de todos os outros 
membros do bando na busca por alimentos. O fundamento de desenvolvimento da 
33 
 
 
otimização por nuvem de partículas (Particle Swarm Optimization – PSO) é uma 
hipótese na qual a troca de informações entre seres de uma mesma espécie oferece 
uma vantagem evolucionária. 
Através destas simulações simplificadas de um comportamento social e, 
baseando-se nos estudos de Wilson, a técnica de PSO foi desenvolvida em 1995 por 
Kennedy e Eberhart (Kennedy e Eberhart, 1995). 
De forma semelhante aos algoritmos genéticos que veremos mais adiante, o 
PSO é baseado em uma população, sendo que cada elemento da população é 
denominado de partícula, ou seja, cada partícula é uma solução potencial. 
Entretanto, diferentemente dos algoritmos genéticos, o PSO não possui 
operadores como o cruzamento e a mutação. O PSO não implementa a sobrevivência 
do indivíduo mais adequado ao meio, mas, ao invés disso, implementa a simulação do 
comportamento social e cognitivo. Este algoritmo pode ser facilmente implementado e 
possui características de convergência estáveis com boa eficiência computacional. 
O sistema possui, inicialmente, uma população de soluções candidatas com 
posições aleatórias. A cada uma destas partículas é atribuída uma velocidade e as 
partículas passam a se movimentar pelo espaço de busca. As partículas possuem 
memória, armazenando nesta a sua melhor posição visitada (pbest) e também a 
adequabilidade desta posição. 
A melhor posição passada pela nuvem é denominada de melhor posição 
global da população (gbest). O conceito básico do algoritmo PSO é acelerar as 
partículas em direção às posições pbest e gbest, com um peso de aceleração aleatório 
a cada passo de tempo. 
34 
 
 
Para o cálculo da velocidade é utilizada a velocidade na iteração anterior, 
multiplicada pelo momento de inércia, como um fator que pondera sua velocidade. 
O algoritmo PSO pode ser descrito da seguinte forma: 
1. Inicie aleatoriamente as velocidades e as posições de todas as 
partículas; 
2. Avalie a aptidão de cada uma das partículas; 
2.1 Avalie a função objetivo de cada uma das partículas; 
i. Se a partícula x for melhor que pbest então atualize 
pbest com a posição corrente; 
ii. Se pbest for melhor que gbest então atualize o gbest 
com pbest corrente; 
3. Atualize a velocidade de cada uma das partículas; 
4. Atualize a posição de cada uma das partículas; 
5. Repita os passos 2 a 4 até que um dos critérios de parada seja 
alcançado. 
Como pode ser observado através do algoritmo mostrado, o funcionamento 
de um algoritmo PSO é simples, o qual é composto de uma seqüência determinada de 
passos. 
Inicialmente, cada partícula da população é iniciada com valores aleatórios, 
mas tomando o devido cuidado ao verificar se os valores aleatórios gerados pertencem 
às fronteiras de limites máximos e mínimos admissíveis para cada variável e se os 
valores arbitrados atendem às restrições que o problema pode apresentar. 
A seguir, inicia-se um ciclo (loop) contínuo que é executado enquanto o 
critério de parada não for atingido. Este critério de parada pode ser referente à 
35 
 
 
convergência do algoritmo, um número máximo de iterações a serem executadas ou 
mesmo outro critério imposto pelo projetista. 
Dentro deste ciclo, deve-se calcular o valor do fitness para cada uma das 
partículas pertencentes à população e também determinar a posição que possui o 
melhor fitness para cada uma das partículas, armazenando-a na variável pbest. Isto é 
realizado através de uma comparação entre o valor do fitness atual e o valor anterior de 
pbest. 
Uma vez que todas as partículas tenham sido analisadas, deve-se 
determinar a posição que possui o melhor valor global para o fitness, ou seja, qual o 
melhor ponto que qualquer uma das partículas já passou. Isto é feito através de uma 
comparação entre os valores de pbest, atribuindo a melhor posição à variável gbest. 
A seguir, o algoritmo faz a alteração da velocidade para cada uma das 
partículas e, utilizando este novo valor da velocidade, altera a posição de cada uma das 
partículas. Esta alteração de velocidade é feita com a soma da velocidade prévia da 
partícula ponderada pelo peso inercial, permitindo a diversificação do espaço de busca, 
com o saber individual e a cooperação entre as partículas (Shi e Eberhart, 1998). 
 
4.6 CLONALG 
 
Em 1993 Forrest et al. usaram um espaço de formas de Hamming para 
modelar a seleção clonal e maturação de afinidade com o objetivo de estudar 
reconhecimento de padrões e aprendizagem. Neste modelo, a população de 
36 
 
 
anticorpos3 se desenvolveu para reconhecer uma população de antígenos4 dada. Um 
algoritmo genético foi utilizado para estudar a capacidade de generalização e a 
diversidade do SIA. A função de afinidade entre o anticorpo e o antígeno foi avaliada, 
somando o número de bits complementares entre as strings de atributos (exemplo: 
distância Hamming). 
A Teoria da Seleção Clonal foi desenvolvida por Macfarlane Burnet e David 
Talmage em 1959, diz que quando o organismo é invadido por um patógeno, algumas 
células do sistema imunológico são capazes de reconhecê-lo e de fixar-se a ele para 
efetuar uma resposta imunológica. Esse antígeno reconhecido ativa determinada célula 
induzindo sua proliferação e diferenciação em plasmócitos ou células de memória. 
Sendo considerada a maturação de afinidade, a capacidade do sistema imunológico de, 
após estar exposto a um patógeno, assimilar sua estrutura e desenvolver um conjunto 
de células com alta afinidade ao mesmo. 
Como resultado de seu estudo, os autores propuseram um algoritmo 
imunológico que tem sido muito utilizado em aplicações de SIA. Eles propuseram o 
seguinte procedimento: 
1. Construa populações aleatórias de antígenos e anticorpos; 
2. Compare os anticorpos com os antígenos e determine as suas 
afinidades; 
3. Classifique os anticorpos de acordo com suas afinidades; 
4. Desenvolva o repertório de anticorpos usando um AG. 
 
3
 Invasores e agentes infecciosos do corpo humano. 
4
 São qualquer substância capaz de induzir uma resposta imunológica. 
37 
 
 
Os autores propuseram a utilização de um Algoritmo Genético (AG) com 
crossover, mas como foi sugerido por eles mesmos, um AG sem crossover pode ser 
considerado um modelo razoável de seleção clonal. Eles também fizeram testes com 
um AG sem crossover e concluíram que o desempenho foi similar ao de um AG com 
crossover. De qualquer forma, para desenvolver uma população de anticorpos que 
mantém a diversidade usando um AG algumas medidas de afinidades para os 
anticorpos foram propostas: 
1. Escolher um antígeno aleatoriamente. 
2. Escolher aleatoriamente uma amostra de µ anticorpos. 
3. Comparar cada anticorpo com o antígeno selecionado. 
4. Adicionar o resultado do anticorpo com maior afinidade ao seu fitness, 
mantendo o fitness de todos os outros anticorpos. 
5. Repetir esse processo para vários antígenos (normalmente três vezes 
o número de anticorpos). 
Os autores discutiram o fato de que esse modelo permite o estudo de como 
o sistema imunológico aprende quais anticorpos são úteis para reconhecer dados 
antígenos. 
Já em 2000, também baseado no princípio da seleção clonal, de Castro 
desenvolveu o CLONALG, ferramenta esta que foi inicialmente concebida para resolver 
problemas de aprendizagem de máquina e reconhecimento de padrões, posteriormente 
foi aperfeiçoada para utilização em problemas em otimização. Esta ferramenta leva em 
conta duas característicascentrais que não foram consideradas por Forrest ET al.: a 
mutação e a seleção proporcional à afinidade. 
38 
 
 
O algoritmo CLONALG para reconhecimento de padrões funciona da 
seguinte maneira. Os padrões a serem reconhecidos são representados por vetores de 
atributos que correspondem a uma população de antígenos (Ag) a ser reconhecida. 
Estes padrões são comparados a um conjunto de anticorpos (Ab) gerados 
aleatoriamente. 
Para cada antígeno: 
1. Calcula-se a afinidade em relação aos anticorpos. 
2. Selecionam-se os n1 anticorpos de maiores afinidades. 
3. Calcula-se o número de clones de cada um dos n1 anticorpos 
selecionados. 
4. Calcula-se uma taxa de mutação para cada anticorpo selecionado 
através da expressão: 
onde fi é a afinidade do anticorpo i, αi é a taxa de mutação deste 
anticorpo e ρ controla seu decaimento. 
5. Cria-se uma matriz de clones. 
6. A matriz de clones sofre mutação de acordo com a taxa de mutação 
que foi calculada anteriormente. 
7. De todos esses clones, o que possuir maior afinidade em relação ao 
antígeno será um candidato a entrar na matriz de memória. 
8. Os n2 anticorpos de menor afinidade são substituídos por outros 
gerados aleatoriamente. 
A combinação da clonagem, mutação e seleção pelo antígeno promovem 
uma melhoria média da população de anticorpos, até que eles reconheçam os 
antígenos. 
39 
 
 
Para resolver problemas de otimização foi necessário fazer algumas 
alterações no algoritmo de reconhecimento de padrões: 
• Não existe uma população de antígenos e sim uma função g(.) a ser 
otimizada. A afinidade de cada anticorpo passa a ser o valor da 
função g(.) avaliada para um dado anticorpo. 
• Não há mais necessidade de manter um conjunto de memória 
separado, já que não existe uma população específica de antígenos. 
Toda a população de anticorpos vai compor o conjunto de memória. 
• Ao invés de selecionar o melhor anticorpo para cada antígeno, n 
anticorpos são selecionados para compor o conjunto de anticorpos. 
Se o processo de otimização visa localizar múltiplos ótimos em uma 
população de anticorpos, então, devemos assumir que n1 = N, ou seja, toda a 
população de anticorpos será selecionada para reprodução, e o número de clones para 
cada anticorpo deverá ser o mesmo. Isso implica que cada anticorpo será avaliado 
localmente e terá o mesmo número de clones que os outros anticorpos, sem privilegiá-
los por sua afinidade. A afinidade só será útil para determinar a taxa de mutação de 
cada anticorpo, que é inversamente proporcional ao fitness. 
 
4.7 OptaiNET 
 
A teoria da rede imunológica foi proposta por Niels Kaj Jerne em 1974, 
sugere que todas as células e moléculas do sistema imunológico se reconhecem 
mesmo na ausência de antígenos. A característica principal desta teoria é a 
40 
 
 
manutenção de um sistema imunológico em que as células B são interconectadas para 
o reconhecimento de antígenos. As células B inibem ou estimulam outras de forma que 
o sistema se estabilize. Estas conexões ocorrem quando o grau de afinidade entre duas 
células excede um determinado limiar, sendo a força de conexão proporcional a esta 
afinidade (Alexandrino, 2007). 
Seguindo a proposta de Jerne (1974), vários modelos de redes foram 
introduzidos por pesquisadores interessados em modelar e estudar o sistema 
imunológico. Sob a perspectiva das redes, as células e moléculas do sistema 
imunológico são capazes de reconhecer umas as outras e assim apresentar uma 
dinâmica comportamental que independe de estímulos externos. Os primeiros modelos 
de redes imunológicas eram baseados em equações diferenciais. Esses modelos além 
de serem muito importantes na área de SIA, também serviram como base para a 
proposta de diversos algoritmos de redes imunológicas artificiais. 
A abordagem de redes imunológicas é muito interessante, pois considera 
diversas propriedades como, aprendizado, memória, tolerância ao próprio, tamanho e 
diversidade da população das células, e também interações entre os elementos da rede 
e entre eles e o ambiente. As redes imunológicas possuem dois modelos, discreto e 
contínuo, que tem em comum uma dinâmica que incorpora um ou mais dos seguintes 
itens: 
RPV = NSt - NSu + INE - DUE 
Onde RPV é a taxa da variação da população, NSt é o nível de estimulação 
da rede, NSu é o nível de supressão da rede, INE é o fluxo de novos elementos, e DUE 
é a morte de alguns elementos. Os primeiros dois termos do lado direito da equação 
41 
 
 
estão relacionados à dinâmica da rede, já os últimos dois correspondem à 
metadinâmica. 
 
4.7.1 Modelos Contínuos de Rede Imunológica 
 
O trabalho de Farmer et al. (1986) descreveu um modelo de dinâmica 
contínua para o sistema imunológico baseado na teoria das redes imunológicas. Este 
modelo consistiu em um conjunto de equações diferenciais para quantificar a dinâmica 
dos componentes da rede imunológica. 
Na proposta de Farmer et al. (1986), as células e moléculas do sistema 
imunológico são constituídas por cadeias binárias com comprimento variável. O epítopo 
(e), também chamado de idiotopo (i), é a parte do anticorpo que pode ser reconhecida 
por outra porção do anticorpo chamada de paratopo (p), como podemos ver na figura 
4.1. Neste modelo em particular, epítopos e paratopos são mutuamente exclusivos, no 
sentido de que um epítopo não é um paratopo e vice-versa. 
 
Figura 4.1: Representação do epítopo e paratopo. 
A dinâmica da rede considera eventos de estimulação e supressão. A 
estimulação acontece quando um paratopo reconhece um epítopo e resulta na 
proliferação de anticorpos. 
 
42 
 
 
4.7.2 Modelos Discretos de Rede Imunológica 
 
A principal diferença entre um modelo contínuo de rede imunológica e 
modelo discreto é que o primeiro baseia-se no uso de equações diferenciais enquanto o 
último pode usar tanto equações diferenciais quanto um processo iterativo. Modelos 
discretos geralmente consideram variações na concentração de anticorpos e nos seus 
atributos, o que significa que os elementos desse tipo de modelo podem aumentar e 
diminuir seu número, assim como alterar suas strings de atributos para melhorar a 
afinidade em relação aos antígenos. Existem várias propostas de redes imunológicas 
na literatura de SIA, mas será estudada neste trabalho uma única rede imunológica 
discreta proposta por de Castro e Von Zuben (2001), chamada de aiNet (artificial 
immune NETwork). 
A aiNet é um grafo ponderado composto por um conjunto de nós, 
denominados de anticorpos, e conjuntos pares de nós chamados de conexões, com um 
valor característico associado, chamado de peso (de Castro, 2002). Na aiNet, assume-
se uma população S de antígenos a ser reconhecida e gera-se aleatoriamente um 
conjunto P de células na rede. Cada elemento da rede corresponde a uma molécula de 
anticorpo. Um vetor de valores reais e um espaço de formas Euclidiano são usados 
para representar anticorpos e antígenos. Cada padrão antigênico é apresentado a cada 
célula da rede e sua afinidade é determinada usando a distância Euclidiana. Um 
número de anticorpos de maior afinidade é selecionado e se reproduz de acordo com a 
sua afinidade. Os clones gerados passam por um processo de mutação somática 
inversamente proporcional a afinidade. Alguns dos clones de maior afinidade são 
selecionados para serem mantidos na rede (memória). Calcula-se a afinidade entre os 
43 
 
 
anticorpos restantes e aqueles que possuírem uma afinidade menor do que um limiar 
estabelecido são eliminados da rede num processo chamado de supressão clonal. Os 
anticorpos em que a afinidade em relação ao antígeno for menor do que um limiar dado 
também são eliminados da rede. Depoisdesse processo, alguns anticorpos gerados 
aleatoriamente são incorporados à rede (metadinâmica). 
O algoritmo aiNet pode ser resumido da seguinte maneira: 
1. Inicialização: crie uma população P de anticorpos aleatoriamente 
2. Para cada padrão antigênico s do conjunto S, faça: 
2.1. Seleção clonal e expansão: determine a afinidade de cada 
elemento da rede em relação ao antígeno apresentado. 
Selecione N1 anticorpos de maior afinidade e reproduza-os 
proporcionalmente a sua afinidade. 
2.2. Maturação de afinidade: os clones passam por um processo de 
mutação inversamente proporcional a sua afinidade. Re-
selecione os anticorpos com as N2 maiores afinidades para 
entrar no conjunto de memória. 
2.3. Metadinâmica: elimine todas as células de memória que 
possuírem uma afinidade em relação ao antígeno menor do que 
o limiar ε. 
2.4. Interações Clonais: determine as interações entre todos os 
elementos do conjunto de memória. 
2.5. Supressão Clonal: elimine todas as células de memória em que 
a afinidade entre elas seja menor do que um limiar δs. 
44 
 
 
3. Interações da rede: determine a similaridade entre cada par de 
anticorpos da rede. 
4. Supressão da rede: elimine todos os anticorpos da rede em que a 
afinidade entre eles seja menor do que a constante δs. 
5. Diversidade: introduza na rede um número N3 de anticorpos gerados 
aleatoriamente. 
6. Ciclo: repita os passos 2 a 5 até que o número máximo de iterações 
seja atingido. 
 
4.8 Algoritmo Genético com Fitness Sharing (FSGA) 
 
Este método foi desenvolvido por (Goldberg e Richardson, 1987) , estudado 
em detalhes por Deb (1989), Horn (1997) e Mahfoud (1993) e desafiado por um 
problema massivamente multimodal por Goldberg, Horn e Deb em 1992. 
Trata-se de um método de niching que tem sido aplicado para classificação 
por vários autores, segundo Mahfoud (1996). Fitness sharing trabalha através da 
redução da fitness de elementos similares na população. 
Fitness sharing embute uma pressão para a diversidade através da função 
de fitness. No cálculo da função de fitness os indivíduos não podem usar o seu valor de 
fitness sozinho, eles devem compartilhá-lo com os demais indivíduos que estejam 
próximos. Especificamente, a nova fitness de um indivíduo é igual a sua fitness original 
dividida por sua niche count (conta de nicho). A niche count de um indivíduo é a soma 
dos valores da função de sharing entre ele e cada indivíduo na população (incluindo ele 
mesmo). A função de sharing é uma função entre dois elementos da população, que 
45 
 
 
retorna 1 (um) se os elementos forem idênticos, 0 (zero) se eles ultrapassarem algum 
threshold de não similaridade; e um valor intermediário para níveis intermediários de 
similaridade. O threshold de não similaridade é especificado pela constante sshare, que 
indica a distância máxima permitida para ocorrer um sharing distinto de zero (Mahfoud, 
1993). 
A analogia com um problema de otimização é que a localização de cada 
ponto de máximo representa um nicho e, a capacidade de compartilhar a fitness 
associada a cada nicho pode encorajar a formação de sub-populações estáveis em 
cada máximo. 
Sharing é baseado no princípio de que o payout (valor) da fitness dentro do 
nicho é finito e deve ser compartilhado entre todos os indivíduos que ocupam aquele 
nicho. Conseqüentemente, a fitness atribuída a um indivíduo será inversamente 
proporcional ao número de outros indivíduos no mesmo nicho. 
No método de fitness sharing, uma vez que a população comece a convergir 
para múltiplos picos, crossover entre diferentes picos pode ser improdutivo. Deb (1989) 
mostrou que com uma restrição que evite este problema era possível melhorar o 
método de fitness sharing. Se a combinação de indivíduos de diferentes picos for 
proibida, a performance poderá ser melhorada. 
Sharing pode ser implementado usando qualquer método de seleção, ainda 
que a seleção resto estocástico (stochastic remainder) tenha sido a mais popular nas 
primeiras implementações do método. 
Note que fitness sharing é um método computacionalmente caro, que requer 
a computação de N2 medidas de distância entre pares de indivíduos, onde N é o 
número de indivíduos da população. 
46 
 
 
A execução do algoritmo genético básico pode ser resumida nos seguintes 
passos: 
• Inicialmente escolhe-se uma população inicial, normalmente formada 
por indivíduos criados aleatoriamente; 
• Avalia-se toda a população de indivíduos segundo algum critério, 
determinado por uma função que avalia a qualidade do indivíduo 
(função de aptidão ou fitness); 
• Em seguida, através do operador de "seleção", escolhem-se os 
indivíduos de melhor valor (dado pela função de aptidão) como base 
para a criação de um novo conjunto de possíveis soluções, chamado 
de nova "geração"; 
• Esta nova geração é obtida aplicando-se sobre os indivíduos 
selecionados operações que misturem suas características (chamadas 
"genes"), através dos operadores de "cruzamento" (crossover) e 
"mutação"; 
• Estes passos são repetidos até que uma solução aceitável seja 
encontrada, até que o número predeterminado de passos seja atingido 
ou até que o algoritmo não consiga mais melhorar a solução já 
encontrada. 
 
47 
 
 
5 OAT – OPTIMIZATION ALGORITHM TOOLKIT5 
 
O OAT é um projeto de software livre escrito em Java que fornece uma série 
de domínios, algoritmos e exemplos da Inteligência Computacional aplicada a 
problemas de otimização, os clássicos e os avançados, visualizações, gráficos, etc. 
Neste capítulo teremos uma visão geral do mesmo, assim como de sua implementação. 
Os princípios de projeto do OAT são fornecer uma estrutura para a execução 
e a verificação fáceis e rápidas de algoritmos de inteligência computacional para 
domínios específicos de problemas, tais que os produtos de interesse e de trabalho 
(principalmente os algoritmos) poderiam ser compartilhados e aplicados sem 
necessariamente estar relacionado com sua execução técnica. Para isto, os algoritmos 
foram projetados de forma independente tais que sua execução poderia ser adaptada e 
estendida para as necessidades específicas da aplicação. A filosofia da programação 
do software foi promovida sobre de forma que possuísse tanto recurso de 
aprendizagem como de extensibilidade. 
 
5
 Tradução: conjunto de ferramentas de algoritmos de otimização 
48 
 
 
 
Figura 5.1: Tela inicial do OAT 
O OAT possui uma interface inicial (figura 5.1), que fornece o acesso às duas 
funções principais do mesmo, o Explorer e o Experimenter. O primeiro fornece uma 
gama de problemas em diversas áreas, incluindo a Otimização de Funções Contínuas 
estudada neste trabalho (figura 5.2), neste módulo o OAT possui vários algoritmos e 
exemplos de problemas que podem ser configurados e executados conforme a opção 
do pesquisador. O segundo é uma ferramenta de experimentos, fornecendo facilidades 
na execução de experimentos com vários algoritmos e problemas, possuindo 
capacidade de comparação entre os mesmos, fornecendo relatórios estatísticos e 
interpretação de resultados. 
49 
 
 
 
Figura 5.2: Screenshot da tela do Explorer 
O software OAT fornece uma estrutura para implementar novos domínios de 
problemas, novas instâncias de problemas e novos algoritmos, bem como base para 
estas implementações. A biblioteca foi projetada para extensibilidade e as 
implementações de base são poucas, assim, pode-se adicionar um domínio 
inteiramente novo, com novos problemas e algoritmos. A seguir será fornecida uma 
resenha em alto-nível destas extensões, indicando as partes importantes da árvore de 
origem e convenções de código sugeridas conformenecessário. O OAT contém duas 
modalidades primárias: um Explorer GUI (Com.OAT.explorer.*) para exploração de 
experimentos e análise com instâncias de algoritmos e problemas com ferramentas de 
visualização, um Experimenter GUI (Com.OAT.experimenter.*) para experimentos 
50 
 
 
formais e análise com ferramentas de estatísticas e a integração de problemas, 
algoritmos e ferramentas para programas personalizados. 
O OAT e sua biblioteca são softwares do tipo open source, é possível 
estender o Framework OAT tanto operando diretamente sobre o código-base do OAT 
como criar um novo projeto que usa o OAT como uma biblioteca de origem. O primeiro 
caso pode ser usado para projetos pessoais ou por desenvolvedores no projeto OAT, a 
segunda ocorrência pode ser usada para os projetos a serem lançados publicamente 
como plug-ins ou extensões para a plataforma. 
Serão abordados dois tipos de expansão para o software OAT, estas 
abordagens explicitam a sua forma livre e seu modo de expansão que pode ser 
estendido aos demais módulos. 
O domínio (com.OAT.Domain) é uma construção que fornece um ponto de 
agregação para instâncias de algoritmos, problemas e outros aspectos relacionados à 
execução. Ela existe para fornecer acesso estruturado e ferramentas para esses 
objetos, facilitando a automação da GUI na execução em lotes de testes da unidade e 
experimentos incluindo os algoritmos, instância de problemas e condições de parada e 
run probes. Os domínios de problema são organizados dentro pacote de domínios 
(Com.OAT.Domains), exemplos são otimização da função contínua (CFO) 
(com.OAT.Domains.CFO) e o problema do caixeiro viajante (TSP) 
(com.OAT.Domains.tsp). 
Para implementar um novo domínio problema, estende a classe abstrata 
domínio (com.OAT.Domain) e implementam-se os métodos abstratos exigidos. Dois 
métodos abstratos importantes são aqueles que preparam as listas de algoritmos e 
problemas (loadAlgorithmList e loadProblemList). Esses métodos são usados no GUI’s 
51 
 
 
para permitir que o usuário escolha entre uma variedade de instâncias de problema e 
algoritmo. Para os domínios de base, esses métodos usam arquivos externos de 
propriedades que definem a extensão de instâncias de problema e algoritmo para se 
preparar para um determinado domínio. Por exemplo, o domínio CFO usa os arquivos 
Algorithms.CFO.Properties e Problems.CFO.Properties que definem nomes específicos 
classes de algoritmos e problemas para carregar para o domínio. Como alternativa, 
para domínios menores, estes podem listar explicitamente as instâncias de algoritmo e 
problema na implementação do domínio. Métodos de carregamento também são 
usados para domínio StopConditions e RunProbes (loadDomainStopConditions e 
loadDomainRunProbes), embora implementações padrão sejam fornecidas com 
implementações genéricas de cada um dos métodos, estes podem ser substituídos ou 
aumentados com listas de implementações específicas de um domínio adicional. Pode-
se implementar também, uma visualização específica para um domínio (Estendendo 
com.OAT.explorer.GUI.plot.GenericProblemPlot) que é exibida no Explorer GUI para 
fornecer uma indicação do usuário da natureza da instância-problema selecionada. 
Para explorar esse recurso, deve ser substituído o método de plotagem do problema e 
retornar uma instância da implementação de plotagem personalizado. Dois exemplos 
desse recurso são CFO que fornece uma visualização 3D das funções selecionadas 
(Com.OAT.explorer.Domains.CFO.GUI.plots.ThreeDimensionalFunctionPlot) e TSP que 
fornece uma visualização 2D dos caminhos ideais para conjuntos de dados 
selecionados (Com.OAT.explorer.Domains.tsp.GUI.plots.TourPanel). Finalmente, outro 
método importante para o Explorer GUI é para recuperar o painel do Explorer específico 
do domínio. Este painel, que deve estender um painel do Explorer genérico 
(Com.OAT.explorer.GUI.Panels.MasterPanel) fornece um espaço de trabalho no 
52 
 
 
Explorer para trabalhar com o domínio incluindo os elementos GUI para plotagem e 
visualização. Por exemplo o domínio CFO fornece um Painel mestre Explorer que 
fornece um gráfico 2D em tempo real de amostras no espaço da função 
(Com.OAT.explorer.Domains.CFO.GUI.Panels.CFOMasterPanel). O painel mestre 
Explorer fornece uma interface rudimentar e gráficos genéricos 
(Com.OAT.explorer.GUI.Panels.DefaultMasterPanel). 
O arquivo propriedades é usado para manter uma lista de todas as classes 
de domínio (domainlist.Properties). Essa lista é usada pelo iniciador OAT genérico para 
selecionar domínios e carregar o Explorer e pelo Experimenter para selecionar um 
domínio no qual fazer experimentos. Pode-se adicionar nomes de classe de domínio 
diretamente a esta lista mestre. Como alternativa, pode ser criada uma lista de domínio 
do usuário, que é carregada automaticamente pela lista de domínio mestre 
(userdomainlist.Properties). Esse segundo caso é útil para plug-ins do OAT que usam o 
software OAT como uma biblioteca e deseja que seus domínios personalizados estejam 
disponíveis na GUI da OAT. 
Uma instância de problema (Com.OAT.Problem) representa uma 
implementação reutilizável de uma definição de problema e é responsável por validar e 
avaliar as soluções do problema (Com.OAT.Solution). Como exemplos de instâncias de 
problema pode-se citar as definições de funções que avaliam vetores de números 
contínuos no domínio CFO (Com.OAT.Domains.CFO.Problems.*), e definições de 
funções que avaliam as seqüências de números binários e convertem vetores de 
números contínuos em seqüências de números binários para avaliação no domínio 
BFO (Com.OAT.Domains.bfo.Problems.*). 
53 
 
 
Para implementar uma instância problema é necessário estender os métodos 
e implementar a classe abstrata do problema (com.OAT.Problem). O método mais 
importante dessa classe é o método de custo (custo) que fornece um pipeline para 
validar e avaliar soluções e chama o método abstrato que define a lógica do problema 
específico para avaliá-lo (problemSpecificCost). Soluções tendem a ser atômicas e 
imutáveis após a sua criação, com relação aos dados específicos problema e a 
avaliação da solução atribuída, é necessário que se mantenham estáticos. Assim, o 
comportamento padrão serve para que a função de custo do problema atribua um custo 
para essas soluções que não são avaliadas de imediato. Essa funcionalidade pode ser 
modificada substituindo a função de custo genérico ou as questões de avaliação na 
classe solução (Com.OAT.Solution). O custo atribuído aos problemas é ordinal, assim o 
problema pode ser definido como custo de maximização ou minimização 
(isMinimization). Antes de soluções serem avaliadas, eles são validados para garantir 
que os dados específicos do problema contem, coincidem com a expectativa de 
definição do problema (checkSolutionForSafety). Por exemplo, no caso de CFO, uma 
instância problema CFO pai genérico (Com.OAT.Domains.CFO.CFOProblem) fornece a 
funcionalidade para garantir que uma solução enviada contém o número necessário de 
variáveis contínuas e que cada variável está dentro dos limites definidos. 
Tanto instâncias de problema como instâncias de algoritmo podem ter 
parâmetros modificáveis pelo usuário. 
Quando problemas são executados no pipeline de execução (consulte 
com.OAT.AlgorithmExecutor) funções genéricas para problemas são necessárias para 
a validação (uma implementação genérica do validateConfiguration é fornecida que 
chama o validateConfigurationInternal método Abstract), inicialização 
54 
 
 
(initialiseBeforeRun) e limpeza (cleanupAfterRun). O método de validação deve validar 
a definição do problema incluindo todos os parâmetros de usuário. A inicialização e a 
limpeza fornecem recurso para a alocação e desalocação derecursos, necessários 
quando uma instância problema está sendo usada em uma execução. Problemas de 
instâncias são reutilizáveis, assim a inicialização é necessária para garantir que 
determinada instância esteja pronta para uso. 
 
5.1 Diagramas de Classes 
 
De forma a demonstrar a forma de desenvolvimento do software OAT serão 
mostradas alguns diagramas de classes do mesmo. A forma de extração dos diagramas 
foi através da utilização do aplicativo NetBeans IDE 6.1 e de sua ferramenta de 
engenharia reversa, a qual gerou os diagramas das figuras 5.3, 5.4 e 5.5. Devido a 
grande extensão do aplicativo, foram selecionados três das classes mais importantes 
para serem exibidas. 
55 
 
 
 
Figura 5.3: Diagrama de Classes do domínio CFO 
56 
 
 
 
Figura 5.4: Diagrama de Classes do Problema da Função Ackley 
57 
 
 
 
Figura 5.5: Diagrama de Classe do Algoritmo de PSO 
58 
 
 
5.2 Simulações e experimentos 
 
Após a apresentação de diversos métodos de otimização de funções e da 
ferramenta OAT, será trazido agora um estudo experimental acerca dos algoritmos 
demonstrados. 
Para estes testes serão utilizadas funções contínuas bastante difundidas na 
literatura de otimização, são elas: Função Ackley, Funções de Jong 2 a 5, Função 
Rastringin e Função Schwefel. Estas possuem os seguintes gráficos: 
 
 (a) Gráfico da Função Ackley (b) Gráfico da Função de Jong 2 
 (c) Gráfico da Função de Jong 3 (d) Gráfico da Função de Jong 4 
 
Figura 5.6: Gráficos das Funções de (a) até (g) 
59 
 
 
 (e) Gráfico da Função de Jong 5 (f) Gráfico da Função Rastringin 
 (g) Gráfico da Função Schwefel 
 
Continuação da Figura 5.6: Gráficos das Funções de (a) até (g) 
Abaixo segue a tabela de ótimo e limites inferiores e superiores da funções 
estudadas. 
Função Ótimo Intervalos 
Ackley’s 4.440892098500626E-16 [0.0, 0.0] 
de Jong 2 0.0 [1.0, 1.0] 
de Jong 3 - - 
de Jong 4 - - 
de Jong 5 23.809436615621898 [32.0, 32.0] 
Rastringin’s 0.0 [0.0, 0.0] 
Schwefel's -837.965774544325 [420.9687, 420.9687] 
Tabela 5.1: Especificação das Funções Avaliadas 
 
60 
 
 
Para a demonstração do comportamento do algoritmos, serão usadas 
apenas duas variáveis nas funções, porém na comparação do desempenho, serão 
avaliadas funções com mais variáveis. 
 
5.2.1 Comportamento dos algoritmos 
 
Para avaliar o comportamento dos algoritmos descritos, foram selecionados 
quatro deles, cada um representando uma área de conhecimento: Algoritmo Genético 
com Fitness Sharing, Mutation Hill Climber, CLONALG e GEO. Estes algoritmos serão 
observados na otimização das funções de Ackley, Rastringin e De Jong’s 4 e 5. 
Os algoritmos executaram mediante uma condição de parada definida pela 
estagnação do algoritmo numa janela de 1000 (mil) iterações. Para a demonstração do 
comportamento de cada um, serão expostas duas Snapshots das soluções em tempo 
de execução, uma no início e outra no final da execução. 
Nas imagens que serão mostradas, as funções aparecem como figuras de 
duas dimensões, onde a tonalidade da cor relata a sua área de contorno. Possuindo 
ainda informações quanto ao posicionamento das possíveis soluções da função e a 
designação do ótimo da função quando conhecido. Nos algoritmos naturais estas 
soluções são chamadas de indivíduos. 
 
 
Figura 5.7: Forma de apresentação dos experimentos de comportamento 
 
Possíveis soluções / Indivíduos Ótimo da função 
61 
 
 
5.2.1.a Algoritmo Genético com Fitness Sharing 
Execução na Função Ackley: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.8: Snapshots da Execução do FSGA sobre a Função Ackley 
Execução na Função Rastringin: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.9: Snapshots da Execução do FSGA sobre a Função Rastringin 
 
62 
 
 
Execução na Função de Jong 4: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.10: Snapshots da Execução do FSGA sobre a Função de Jong 4 
Execução na Função de Jong 5: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.11: Snapshots da Execução do FSGA sobre a Função de Jong 5 
 
 
63 
 
 
Com a observação das imagens acima se pode constatar que o algoritmo 
genético com fitness sharing, busca ao ótimo porém sem deixar de preservar sub-
ótimos, espalhando sua população em diferentes pontos próximos ao ótimo da função. 
 
5.2.1.b Algoritmo Mutation Hill Climber 
Execução na Função Ackley: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.12: Snapshots da Execução do Mutation Hill Climbing sobre a Função Ackley 
 
64 
 
 
 
Execução na Função Rastringin: 
 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.13: Snapshots da Execução do Mutation Hill Climbing sobre a Função Rastringin 
Execução na Função de Jong 4: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.14: Snapshots da Execução do Mutation Hill Climbing sobre a Função de Jong 4 
65 
 
 
 
Execução na Função de Jong 5: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.15: Snapshots da Execução do Mutation Hill Climbing sobre a Função de Jong 5 
 
Este algoritmo como o próprio nome diz é de “Subida de Encosta”, quando 
uma de suas soluções encontra um “pico” ele sobe, porém, esta execução pode 
estagnar o algoritmo em solução não próxima do “ótimo”, como podemos observar no 
problema da função Rastringin. 
 
66 
 
 
 
5.2.1.c Algoritmo CLONALG 
Execução na Função Ackley: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.16: Snapshots da Execução do CLONALG sobre a Função Ackley 
Execução na Função Rastringin: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.17: Snapshots da Execução do CLONALG sobre a Função Rastringin 
67 
 
 
 
Execução na Função de Jong 4: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.18: Snapshots da Execução do CLONALG sobre a Função de Jong 4 
Execução na Função de Jong 5: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.19: Snapshots da Execução do CLONALG sobre a Função de Jong 5 
 
68 
 
 
O algoritmo do CLONALG busca o “ótimo” da função gerando pequenas 
mutações que a cada iteração se aproximam mais do ótimo, entretanto, como se vê nas 
execuções acima, ele também gera indivíduos de forma aleatória que podem ou não 
estar em um local promissor, buscando com isso não permitir que escape nenhum 
ótimo na função. 
 
5.2.1.d Algoritmo GEO 
 
Execução na Função Ackley: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.20: Snapshots da Execução do GEO sobre a Função Ackley 
69 
 
 
 
Execução na Função Rastringin: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.21: Snapshots da Execução do GEO sobre a Função Rastringin 
Execução na Função de Jong 4: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.22: Snapshots da Execução do GEO sobre a Função de Jong 4 
70 
 
 
 
Execução na Função de Jong 5: 
 
 (a) Início da Execução (b) Posição Final 
Figura 5.23: Snapshots da Execução do GEO sobre a Função de Jong 5 
 
Este algoritmo, assim como o Mutation Hill Climbing, tende a convergir ao 
primeiro ponto ótimo que encontra, recaindo no problema de sub-ótimos. 
 
5.2.2 Comparação de desempenho 
 
No comparativo de desempenho dos algoritmos foi utilizada a funcionalidade 
Experimenter disponível no OAT. O Experimenter fornece uma série de opções para 
gerar os testes com a escolha da quantidade de funções e suas variáveis assim como 
os algoritmos que irão