MÉTODOS DE OTIMIZAÇÃO
BIOINSPIRADOS
1
Leandro M. Almeida
SISTEMAS COMPUTACIONAIS

Computação clássica tem dificuldade em lidar
com mudanças inesperadas

Entradas e interações devem ser cuidadosamente
gerenciadas


“Redoma de vidro”
Dispositivos computacionais interagem cada vez mais
com mundo real
Aberto
 Ruidoso
 Incontrolável


Necessidade de uma forma completamente diferente
de projetar e implementar programas.
2
SISTEMAS COMPUTACIONAIS

Computação Não-clássica

Permite construção de sistemas computacionais
complexos
Autônomos
 Adaptáveis
 Robustos


Sistemas devem ser executados corretamente e com
segurança em ambientes
Imprevisíveis
 Em constante mudança
 Hostis
 Por longos períodos de tempo

3
SISTEMAS COMPUTACIONAIS
Processos biológicos lidam bem com esses
problemas
 Criaturas vivas são robustas, autônomas e
adaptáveis
 Podem sobreviver a:

Machucados
 Danos
 Uso prolongado
 Ataques contínuos de outras criaturas


Adaptam-se ao ambiente de forma continuada;
4
SISTEMAS COMPUTACIONAIS - FUTURO
Deverão ser mais flexíveis e amigáveis;
 Robustos;
 Capazes de executar várias atividades sem
intervenção humana:

Configuração
 Otimização
 Manutenção
 Conserto




Detecção, diagnóstico, reparo
Diferenciação
Possíveis caminhos: orientação as aspectos,
reflexão computacional, etc.
5
BIOLOGIA

Biologia produz organismos complexos
adaptáveis, mesmo utilizando quantidades
enormes de componentes pouco confiáveis

Como é possível?
Auto-avaliação
 Auto-reparo
 Auto-configuração
 Vários níveis de redundância
 Vários níveis de defesa


Por que não modelos computacionais bio-inspirados?
6
RELACIONAMENTO NATURAL
Biologia
Engenharia
7
COMPUTAÇÃO BIOINSPIRADA



A natureza possui soluções elegantes e eficientes
para vários problemas;
Presentes nas mais diversas espécies de seres
vivos;
Inspira novas técnicas computacionais

Inspiração ≠ Cópia.
8
COMPUTAÇÃO BIOINSPIRADA

Biologia
Computação
Algoritmos evolucionários

 Inteligência de colônia de
formigas

 Inteligência de exames

 Sistemas imunes artificiais

 Redes neurais artificiais

 DNA computing

 Autômato celular

 Membrane computing
A maioria das abordagens computacionais bioinspiradas
resultam de modelos matemáticos projetados para melhor
compreender os sistemas naturais, e.g. por meio de
simulações

Evolução da espécies
Colônia de formigas
Enxames
Sistemas imunológicos
Cérebro
DNA
Células
Membranas biológicas


9
ALGORITMOS EVOLUCIONÁRIOS

Existem muitas variações de Algoritmos
Evolucionários (AE)
Dada uma população de indivíduos, a pressão
exercida pelo ambiente causa uma seleção natural
(sobrevivência dos mais aptos), a qual causa o
aumento da aptidão da população;
 Dada uma função de qualidade a ser maximizada,
podemos criar aleatoriamente um conjunto de
soluções candidatas;
 Com base na aptidão, alguns dos melhores candidatos
são escolhidos para serem a semente da nova
geração, através da recombinação e/ou mutação;
 O operador de recombinação pode ser aplicado a dois
ou mais pais, gerando um ou mais filhos;

10
ALGORITMOS EVOLUCIONÁRIOS
A mutação é aplicada em apenas um candidato
resultando em um novo candidato;
 Produção de novos candidatos que competem com
base na aptidão e/ou na idade para formar a nova
geração;
 O processo normalmente é iterativo até que uma
qualidade (soluções) seja alcançada ou então um
limite computacional, temporal, etc;
 Processos fundamentais dos sistemas
evolucionários

Operadores de variação (recombinação e mutação)
 Ação de seleção como força que pressiona a qualidade

11
ALGORITMOS EVOLUCIONÁRIOS
A evolução é visto com um processo de adaptação
 Necessidade de manutenção da diversidade de
indivíduos;
 Procedimentos de seleção contam com mecanismos
baseados em aleatoriedade e elitismo;

12
ALGORITMOS EVOLUCIONÁRIOS
AE são baseados em populações, processam
simultaneamente uma coleção de soluções;
 AE freqüentemente usam recombinação para
mesclar informações de mais de uma solução
candidata para a criação de uma nova solução;
 AE são estocásticos;

Inicialização
Seleção de pais
Pais
Recombinação
População
Mutação
Seleção de sobreviventes
Termino
Prole
13
EXEMPLOS DE APLICAÇÃO – REDES MLP
14
EXEMPLOS DE APLICAÇÃO – REDES SOM
15
COMPORTAMENTO TÍPICO DE UM AE

Fases da otimização de um problema
unidimensional
Fase inicial:
Distribuição quase aleatória da população
Fase mediana:
População disposta nas encostas
Fase final:
População concentrada no alto das colinas
16
OUTRAS CARACTERÍSTICAS
DOS
AE
Possuem uma fase de exploração e outra
chamada de explotação;
 Podem sofrer problemas de convergência
prematura, ou seja, perda acelerada da
diversidade da população;
 Possuem um “anytime behaviour”, ou seja,
conseguem apresentar uma solução a qualquer
momento da busca;
 Freqüentemente chamados de métodos de
otimização global;
 Englobam um conjunto de algoritmos que diferem
em alguns detalhes.

17
FAMÍLIA DE AE

Normalmente são classificados de acordo com a
forma de representação das soluções candidatas
Genétic Algorithms (GA) – cadeia de caracteres sob
um alfabeto finito;
 Evolution Strategies (ES) – vetores de valores reais;
 Evolutionary Programming (EP) – máquinas de
estados finitos;
 Genetic Programming (GP) – estrutura de árvores.


Essas diferenças possuem uma origem
principalmente histórica.
18
FAMÍLIA DE AE
Componente/
Característica
Dialetos dos AE
GA
ES
EP
GP
Problemas
típicos
Otimização
combinatória
Otimização
contínua
Otimização
Modelagem
Representação
típica
Cadeia de caracteres
sob um alfabeto finito
Vetores de números
reais
Freqüente
utilização do
formato de ES
Árvores
Papel da
recombinação
Operador de variação
primário
Importante, mas
secundário
Nunca aplicado
Primário/somente
um operador de
variação
Papel da
mutação
Operador de variação
secundário
Importante, mas as
vezes é o único
operador
Somente um
operador de
variação
Secundário, as
vezes não usado por
completo
Seleção de
pais
Aleatória, guiada pela
aptidão
Aleatória, uniforme
Cada indivíduo cria
um filho
Aleatória, guiada
pela aptidão
Seleção de
sobreviventes
Generational e Steadstate
Determinística,
guiada pela aptidão
Aleatória, guiada
pela aptidão
Aleatória, guiada
19
pela aptidão
POR QUE UTILIZAR AE PARA RESOLVER
PROBLEMAS DE OTIMIZAÇÃO?

Propriedades das funções


Embora as considerações sobre
convexidade/concavidade e continuidade não sejam
necessariamente um fundamento de AE, esse é o real
propósito das maioria das técnicas de programação
matemática. Embora ambos os domínios
compartilhem o mesmo conceito de algoritmos “gerare-testar”, procedimentos de busca evolucionários não
são diretamente comparáveis as técnicas de busca
convencionais.
Uma única solução

Técnicas de programação matemáticas fornecem uma
única “melhor” solução que não é interessante para
muitas tomadas de decisão. AE são várias “melhores”.
20
POR QUE UTILIZAR AE PARA RESOLVER
PROBLEMAS DE OTIMIZAÇÃO?

Impraticabilidade


Conhecimento do domínio


Não é difícil utilizar AE, não requerem um
conhecimento rico do domínio.
Robustez


Normalmente não tratável com técnicas de
programação matemáticas, já com AE o problema
pode vir a tornar-se tratável.
Uma mesma estrutura pode ser utilizada para
resolver vários problemas.
Manipulação de restrição e métodos de
penalidade

A função de pênalti é facilmente implementável
assim como a mudança de seus parâmetros.
21
POR QUE UTILIZAR AE PARA RESOLVER
PROBLEMAS DE OTIMIZAÇÃO?

Exploração e explotação


Tempo computacional


Provêm rápidas aproximações a funções, nearoptimal
Otimização multiobjetivo


AE são de propósito geral, independente de domínio e
possuem características de exploração e explotação.
Conseguem trabalhar muito bem em problemas com
objetivos conflitantes.
Soluções iniciais

Não requerem um método especializado para gerar as
soluções iniciais.
22
POR QUE UTILIZAR AE PARA RESOLVER
PROBLEMAS DE OTIMIZAÇÃO?

Problemas árduos


Devido ao paralelismo inerente dos AE os problemas
árduos passam ser menos árduos se comparados
quando do uso de técnicas clássicas.
Otimização sob mudança do ambiente

Em muitos problemas de otimização do mundo real, o
ambiente flutua, provocando mudanças dramáticas
na aptidão dos indivíduos. Otimização sob mudanças
no ambiente (dinâmica, não-estacionária ou on-line)
podem ser manipuladas eficientemente através do
uso de AE.
23
QUANDO É RECOMENDÁVEL USAR AE?

Otimização do conhecimento

Mesmo pesquisadores/profissionais com um pobre ou
nenhum conhecimento matemático a respeito do
problema de otimização ainda podem resolver o
problema usando uma metodologia baseada em AE;
Quando soluções ranked como 2ª, 3ª, etc.
melhores são desejadas;
 Para solucionar problemas multimodais;
 Para uma rápida aproximação de soluções;
 Para solucionar problemas multiobjetivos;
 Otimização sob mudanças no ambiente;

24
QUANDO É RECOMENDÁVEL USAR AE?
Para a construção de sistemas inteligentes
híbridos;
 Se AE são computacionalmente menos custosos
que outras técnicas, devem então ser preferidos;
 Se o tempo computacional não é uma
preocupação, métodos baseados em AE podem ser
empregados para encontrar soluções quaseótimas;
 Problemas envolvendo características complexas
como multi-objetividade, multimodalidade,
mudanças no ambiente, etc. torna-se útil a
aplicação de AE.

25
DESVANTAGENS DO USO DE AE

Técnicas baseadas em AE são reconhecidas com
algoritmos de busca heurísticos.


Os parâmetros usados pelas técnicas baseadas em AE
são orientadas ao problema.



Não há garantia de “ótimalidade” quando aplicados a solução
de problemas de otimização;
Não é uma tarefa fácil a determinação de parâmetros
apropriados para um problema;
O padrão de convergência e complexidade de tempo
também são dependentes do problema;
Não ajudam a examinar a percepção matemática de
problemas de otimização, onde pode haver informações
adicionais úteis para a tomada de decisão.
26
DESVANTAGENS DO USO DE AE
A análise de sensibilidade pode ser executada,
para todo o tipo de modelo, na escala desejada,
embora não seria tão eficiente quanto a
sensibilidade do LP (Linear Programming);
 Em alguns casos não são úteis para o ajuste fino
de soluções (busca local, explotação);
 Alto custo computacional na avaliação do
indivíduo (dependente do problema);
 Convergência prematura (manutenção da
diversidade);
 Ausência de um mecanismo explicativo.

27
POR QUE HIBRIDIZAR AE?

Modelos híbridos cujos AEs…
são parte de um sistema maior ou
 têm outros métodos ou estruturas de dados
incorporados a eles.


Objetivos da hibridização:
Modelos híbridos para melhorar desempenho de
técnicas já existentes.
 Modelos híbridos para melhorar a busca por boas
soluções.
 Modelo híbridos para resolver os pontos negativos dos
AE.

28
POR QUE HIBRIDIZAR AE?


Muitos problemas complexos podem ser
decompostos em sub-problemas a serem
resolvidos com técnicas distintas.
Não existe um método de propósito geral
totalmente bem sucedido ou eficiente.
Pode-se combinar AEs com heurísticas específicas.
 Deve-se ter cautela para não fazer a busca local
inviabilizar a geração de novas soluções.
 Busca-se solução híbrida por ser melhor que cada um
dos algoritmos que compõe o modelo híbrido.

29
NO FREE LUNCH (NFL) TEOREMA

A quantidade de conhecimento específico no
algoritmo híbrido é variável e pode ser ajustada.
30
ALGORITMOS MEMÉTICOS

AEs podem explorar melhor que explotar:

Em parte devido à natureza aleatória dos operadores
de variação.
Pode-se adicionar uma etapa de busca local para
melhorar explotação.
 A combinação de AEs com operadores de busca
local que atuam dentro do laço do AE é chamada
de Algoritmo Memético.


O termo memético também é usado para AEs cujos
operadores empregam conhecimento específico de
instâncias do problema.
31
BUSCA LOCAL

Busca local é um processo iterativo para
examinar o conjunto de pontos na vizinhança da
solução atual e a substituir por um vizinho
melhor, caso exista.
32
BUSCA LOCAL

Componentes principais que afetam o algoritmo:

Regra de pivoteamento (encerra o laço interno):

Condição de profundidade (encerra o laço externo):


Determina o número de interações da busca local.
Escolha da função geradora de vizinhança
33
BUSCA LOCAL

Escolha da função de vizinhança:


N(i) é freqüentemente definida como um conjunto de
pontos que podem ser alcançados através da
aplicação de algum operador de movimento ao ponto
i.
Representação equivalente: grafo não direcionado

G(v,E):
v é o conjunto de vértices que representa todos os pontos
representáveis, as soluções em potencial.
 E é o conjunto de arestas que representa as possíveis
transições que podem ocorrer a partir da aplicação de um
único operador. As arestas podem ser direcionadas e
ponderadas.

34
BUSCA LOCAL

Em resumo:
É definida pela combinação de vizinhança, N(x), e
regra de pivoteamento.
 É relacionada a metáfora da paisagem (landscape).
 N(x) é definida como o conjunto de pontos que podem
ser alcançados a partir da aplicação de um operador
de movimento.
 Exemplo: Busca bit flipping em problemas binários.

35
LAMARCKIANISMO E EFEITO BALDWIN

Herança das mudanças feitas ao indivíduo
(características adquiridas):

Um AM é dito Lamarckiano se o indivíduo resultante
da busca local substitui o original. Isto é, as
características são herdadas.
Um AM é dito Baldwiniano se o processo
evolucionário for guiado pelas adaptações
favoráveis sem modificações nas aptidões dos
indivíduos, devido a aprendizagem ou
desenvolvimento, refletindo em mudanças de
características genéticas.
 Abordagem Baldwiniana ou uma combinação
probabilística dos dois mecanismos.

36
TWO MODELS OF LIFETIME ADAPTATION

Lamarkian
traits acquired by an individual during its lifetime
can be transmitted to its offspring
 e.g. replace individual with fitter neighbour


Baldwinian
traits acquired by individual cannot be transmitted to
its offspring
 e.g. individual receives fitness (but not genotype) of
fitter neighbour

37
ESTRUTURA DE UM ALGORITMO
MEMÉTICO

Possíveis pontos onde se pode hibridizar
38
ESTRUTURA DE UM AM - INICIALIZAÇÃO
39
ESTRUTURA DE UM AM - INICIALIZAÇÃO

Possíveis benefícios por iniciar AES com soluções
existentes:
Evitar a perda de esforço computacional refletindo
aumento de eficiência (velocidade).
 Direcionar busca para regiões promissoras do espaço
de busca levando a aumentar efetividade (qualidade
da solução final).
 Dividir o esforço computacional entre inicialização
heurística e busca evolucionária pode gerar melhores
resultados que gastar todo o esforço em busca
evolucionária apenas.

40
ESTRUTURA DE UM AM - INICIALIZAÇÃO

Maneiras de mudar a função de inicialização em
relação a um critério aleatório:

Semeadura (Seeding): Semeia a população com uma
ou mais soluções boas, vindas de outras técnicas:


Exemplos de emprego de informação específica do problema:
heurística do vizinho mais próximo para os problemas do
tipo TSP e agendamento do mais difícil em primeiro lugar
para problemas de agenda e planejamento.
Incialização Seletiva (Selective initialisation):
Cria-se grande número de soluções aleatórias e
seleciona-se a população inicial a partir delas:
Realizar N torneios de tamanho k;
 Selecionar baseando-se também na diversidade.

41
ESTRUTURA DE UM AM - INICIALIZAÇÃO

Ainda maneiras de mudar a função de
inicialização em relação a um critério aleatório:
Realizar busca local em cada membro da população
escolhido aleatoriamente. Produz-se um conjunto de
indivíduos localmente ótimos.
 Empregar um ou mais métodos anteriores para
identificar uma ou mais boas soluções:


Deve clonar e aplicar mutação com altas taxas (mass
mutation) nas soluções iniciais encontradas de forma a
gerar um número de indivíduos na vizinhança do ponto
inicial.
42
ESTRUTURA DE UM AM – OPERADORES
INTELIGENTES


Operadores inteligentes de variação: Incorporam
conhecimento específico da instância ou do
problema ao operador.
Introdução de viés (bias) nos operadores:
Exemplo 1: Aumentar a probabilidade de escolha de
características mais compactas para emprego em um
classificador.
 Exemplo 2: Genes codificando instruções de
microprocessador de modo a serem agrupados em
conjuntos de efeitos similares.

43
ESTRUTURA DE UM AM – OPERADORES
INTELIGENTES

Uso de conhecimento específico do problema:
Incorporação de uma fase de busca local dentro de um
operador de recombinação.
 Ex.: testar todas as possíveis orientações dos dois
fragmentos de estrutura de proteína “separados” pelo
ponto de cruzamento e pegar a energeticamente mais
favorável. Se nenhum ajuste possível for encontrado,
escolher outro ponto de cruzamento.


Uso de conhecimento específico da instância:
Operadores recebem heurística muito específica.
 Ex.: Merz and Friesleben’s distance-preserving
crossover (DPX) operator para o TSP.

44
ESTRUTURA DE UM AM – OPERADORES
INTELIGENTES

Busca local atuando sobre todas as soluções
criadas pelos operadores de variação.
É compatível com o conceito de meme, pois realiza
uma ou mais fases de melhorias de indivíduos
durante um ciclo do AE.
 É o tipo mais comum.

45
PROJETO DE AM


AMs não são “soluções mágicas” para problemas
de otimização.
Deve-se tomar cuidado com:
Diversidade da população.
 Escolha dos operadores.
 Uso do conhecimento adquirido durante o processo de
otimização.

46
PROJETO DE AM – PRESERVAÇÃO DA
DIVERSIDADE

O problema da convergência prematura.

Técnicas para combater este problema:
Usar somente uma proporção pequena de boas
soluções conhecidas na população inicial.
 Usar operadores de recombinação que são projetados
para preservar diversidade (como Merz’s DPX).
 Modificar operador de seleção para prevenir
duplicações.
 Modificar operador de seleção ou o critério de
aceitação da busca local para usar um método de
Boltzmann.

47
PROJETO DE AM – PRESERVAÇÃO DA
DIVERSIDADE

Manutenção de diversidade em uma população é
o objetivo de algoritmos com algum sucesso:

O cruzamento DPX de Merz explicitamente gera
indivíduos que são eqüidistantes para cada pai, tendo
a mesma distância entre os pais.

Operador adaptativo de Boltzmann, por Krasnogor,
usa critério de aceitação de novo indivíduo baseado
no cozimento simulado. A temperatura é
inversamente proporcional à diversidade da
população.
48
PROJETO DE AM – ESCOLHA DOS
OPERADORES

O fator crucial no projeto de um AM é:

Escolha da heurística de melhoramento ou do
operador de movimento da busca local.



Merz e Freisleben mostram que a escolha do operador de
movimento pode ter efeito dramático na eficiência e na
efetividade da busca local.
Krasnogor mostrou vantagens em usar busca local com um
operador de movimento que é diferente dos operadores de
movimento usados pela mutação e pelo cruzamento.
Podem-se disponibilizar múltiplos operadores de busca
local, escolhendo-se qual a ser aplicado em cada caso.
49
PROJETO DE AM – USO DO
CONHECIMENTO

Como usar e reusar o conhecimento adquirido
durante o processo de otimização?
Na recombinação.
 De modo geral não são usados mecanismos explícitos.
 Uma possível hibridização – tabu search.
 Extensões dos esquemas de aceitação/seleção de
Boltzmann.


Uso de informação sobre os genomas da população atual
e/ou populações anteriores.
50
ALGUNS ARTIGOS...





Delgado M., Cuellar M.P., Pegalajar M.C. Multiobjective
hybrid optimization and training of recurrent neural
networks. In IEEE TRANSACTIONS ON SYSTEMS MAN AND
CYBERNETICS PART B-CYBERNETICS, vol. 38(2), pp. 381-403,
2008.
Petrovic N.I., Crnojevic V. Universal impulse noise filter
based on genetic programming. IEEE TRANSACTIONS ON
IMAGE PROCESSING, vol. 17(7), pp. 1109-1120, 2008.
Ben Ali, Y.M. Advances in evolutionary feature selection
neural networks with co-evolution learning . NEURAL
COMPUTING & APPLICATIONS, vol. 17(3), pp. 217-226, 2008.
Zhou, Y., He, J. A runtime analysis of evolutionary
algorithms for constrained optimization problems. IEEE
TRANSACTIONS ON EVOLUTIONARY COMPUTATION, vol.
11(5), pp. 608-619, 2007.
Droste, S., Jansen, T., Wegener, I. On the analysis of the (1 +
1) evolutionary algorithm. Theoretical Computer Science, 276,
pp. 51-81, 2002.
51
CONFERÊNCIAS E PERIÓDICOS SOBRE AE

Conferências
IEEE Conference on Evolutionary Computation
(CEC)
 Genetic and Evolutionary Computation Conference
(GECCO)
 Parallel Problem Solving from Nature (PPSN).


Periódicos
Evolutionary Computation,
 IEEE Transactions on Evolutionary Computation
 Genetic Programming and Evolvable Machines

52
REFERÊNCIAS






Eiben, A.E., Smith, J. E.. Introduction to Evolutionary
Computing. Berlin: Springer, 2003.
Linden, R. Algoritmos Genéticos: uma importante
ferramenta da inteligência computacional. Rio de
Janeiro: Brasoft, 2006.
Pal, S. k., Bandyopadhyay, S. Classification and
Learning using Genetic Algorithms. Berlin: Springer,
2007.
Haupt, R. L., Haupt, S.E. Practical Genetic Algorithms.
USA: Wiley, 1998.
Khosla, R., Dillon, Tharam. Engineering Intelligente
Hybrid Multi-Agente Systems. USA: KAP, 1997.
De Jong, K. A. Evolutionary Computation. London:
MIT, 2006.
53