Métodos de otimização bioinspirados

MÉTODOS DE OTIMIZAÇÃO BIOINSPIRADOSLeandro M. Almeida1

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


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


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 Evolução da

espécies Colônia de formigas Enxames Sistemas

imunológicos Cérebro DNA Células Membranas

biológicas

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

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


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

qualidade11


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


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;

População

Pais

Prole

Recombinação

Mutação

Seleção de pais

Seleção de sobreviventes

Termino

Inicialização

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


Seleção de sobreviventes

Generational e Stead-state

Determinística, guiada pela aptidão



19

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 “gerar-e-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


Impraticabilidade 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.

Conhecimento do domínio Não é difícil utilizar AE, não requerem um

conhecimento rico do domínio. Robustez

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


Exploração e explotação AE são de propósito geral, independente de

domínio e possuem características de exploração e explotação.

Tempo computacional Provêm rápidas aproximações a funções, near-

optimal Otimização multiobjetivo

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


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. Não há garantia de “ótimalidade” quando aplicados a

solução de problemas de otimização; Os parâmetros usados pelas técnicas baseadas em

AE são orientadas ao problema. 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


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


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


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


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


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

Documents

Métodos de otimização bioinspirados