Algoritmos Genticos

Algoritmos Genticos

ElitismoA maior parte dos algoritmos usam elitismoPode causar convergncia prematura

Nuvem de PartculasPSO - Particle Swarm Optimization (1995)Desenvolvida por James Kennedy (psiclogo) e Russell Eberhart (engenheiro), com base no comportamento de pssaros em revoadas modelado pelo bilogo Frank Heppner.Inspirado no comportamento e na dinmica dos movimentos dos pssaros, insetos e peixes;Originalmente desenvolvido para problemas de otimizao com variveis contnuas;Desempenho similar ao dos Algoritmos Genticos;

7

Otimizao Nuvem de Partculas

Otimizao Nuvem de Partculas

PSOElementos do algoritmo:A : populao de agentes.xi : posio do agente ai no espao de solues.f : funo de avaliao.vi : velocidade do agente ai.V(ai) : conjunto fixo de vizinhos do agente ai.Todos os agentes esto conectados, direta ou indiretamente

Otimizao Nuvem de Partculas VantagensInsensvel a mudana de escala das variveis;Implementao simples;Adaptvel a computadores paralelos;No requer clculo de derivadas;Poucos parmetros para serem definidos pelo usurio;Bom para encontrar o mnimo global;DesvantagensRpido para localizar a bacia de atrao das boas solues, mas lento no ajuste fino da soluo (como nos algoritmos genticos).

Baseia-se no comportamento social dos pssaros em revoadas, cardumes de peixes e enxames de abelhas Algoritmicamente, tem-se um conjunto de partculas que percorrem o espao de busca apresentando comportamentos aleatrios em relao individualidade e sociabilidade A individualidade de uma partcula est relacionada nfase dada, em seus movimentos, melhor soluo j encontrada por ela mesma, enquanto sua sociabilidade reflete o grau de importncia dado por ela melhor soluo j encontrada por seus vizinhos O conceito de vizinhana em PSO no o mesmo utilizado pelas meta-heursticas de busca por entornos, pois cada partcula, associada a uma soluo que evolui, vizinha de um conjunto de partculas que nunca alterado A estrutura de vizinhanas construda de forma que os progressos obtidos em cada regio tenham influncia, potencialmente, em todas as partculas

Aplicaes de PSOAplicaes comuns:Evoluo de redes neurais artificiaisExtrao de regras de RNAsEscalonamento de tarefas (Multi-objective Job shop scheduling)Roteamento de veculos (Capacitated Vehicle Routing)Aplicao recente:Bandwidth Minimization Problem - BMP (2003).Algumas aplicaes recentes (2004):Caminho timo para operaes de perfurao automatizadas.Minerao de dados para tarefas de classificao.Posicionamento de bases em computao mvel.Aproximao poligonal tima de curvas digitais.

Separao: usada para evitar aglomeraes de partculasAlinhamento: encaminhar a busca para a partcula representante do grupoCoeso: uma partcula movimenta-se na mdia dos seus vizinhosImitando a natureza

PSO um mtodo baseado em populao, como o Algoritmo GenticoEntretanto, o conceito bsico cooperao em vez da rivalidade Apesar da semelhana com AG, esta tcnica no usa operadores genticos (crossover, mutao, etc) Uma partcula movimenta-se com velocidadeUsando a prpria experinciaAlm da experincia de todas as partculasA idia similar ao bando de pssaros (ou cardume de peixes ou enxame de abelhas) procurando comidaHabilidade de troca de informaes entre vizinhosHabilidade de memorizar uma posio anteriorHabilidade de usar informaes para tomada de decises

Notao

Notao

Fora a partcula a mover-se na mesma direoTendncia para seguir a prpria direo com a mesma velocidadeAtualizao da velocidadeTrs termos definem uma nova velocidade para uma partcula:

1. Termo de inrcia

2. Termo cognitivo

3. Termo de aprendizado socialMelhora o indivduoFora a partcula a voltar a uma posio anterior que seja melhor do que a atualTendncia conservativaFora a partcula a seguir a direo de seus melhores vizinhosComo em todo rebanho, mas seguindo os melhores

Idia bsica: comportamento cognitivoUm indivduo lembra do conhecimento passado

Qual a melhor direo?

comida: 10

comida: 8

comida: 5

Idia bsica: comportamento socialUm indivduo adquire conhecimento dos demais membros do grupoQual a melhor direo?

pssaro 1comida: 1

pssaro 2comida: 3

pssaro 3comida: 2

pssaro 4comida: 4

aprendizado social

PSO tradicional Eberhart, R. C. and Kennedy, J. (1995)Atualizao de velocidade e posio

inrcia

cognitivoPara cada agente ai :

vi = wvi + 1.rand().(pbesti - xi) + 2.rand().(gbesti - xi)xi = xi + vionde:pbesti a melhor posio em que a partcula ai j estevegbesti a melhor posio em que algum vizinho de ai j esteve.w o peso de inrcia

Inicialize as partculas com posies aleatrias e velocidades nulasCalcular os valores fitnessCompare os fitness com os melhores valores do indivduo (pbest) e dos demais (gbest)O critrio de parada est satisfeito?Atualize velocidades e posiesIncioFimSIMNO

123Problema de minimizao

melhor partcula

outra partcula

Inicializao as posies Criando o vetor de velocidadesExemplo: 1 Iterao

1123

Exemplo: 2 IteraoProblema de minimizao

melhor partcula

outra partculaAtualizando as posies Modificando o vetor de velocidades

Termo de inrcia

Melhor posio individual (pbest)

Posio atual (x)

Melhor posio do indivduo (pbest)

Posio atual (x)

Melhor posio do indivduo (pbest)

Melhor posio global (gbest)Melhor posio global (gbest)

Melhoramentos e VariantesReduo linear da ponderao de inrcia;Fator de constrio;Modelos com Vizinhanas.

Fator de ConstrioFator de Constrio foi introduzido por Clerc e Kennedy (2002).Tornou-se muito popular nos algoritmos recentes de nuvem de partcula.

Modelos com VizinhanasA cada partcula atribudo uma vizinhana;As vizinhanas tornam mais lento a transmisso da melhor posio atrves da nuvem;Converge mais lentamente, mas melhora a diversificao.

Armadilhas da tcnica PSOAs partculas tendem a se agrupar, ou seja, devido a uma convergncia rpida demais, a soluo fica presa em um ponto timo localO movimento de alguma partcula pode ser levado a um ponto de soluo infactvelAs partculas poder mapear um espao inapropriado de solues factveis

Problema: Partculas tendem a se agrupar, reduzindo a capacidade de movimentos da nuvem para solues melhores.

Soluo: reiniciar algumas partculas em novas posies, as quais podem mover-se para reas com solues melhores. As demais partculas podem mover-se para estas reas.

!

Inicialize as partculas em posies aleatrias e velocidades nulasCalcule os valores fitnessAchou um critrio de busca local?Compare/atualize os valores dos fitness pbest e gbestCritrio de parada?Atualize velocidades e posies das partculasCritrio de reinicializao?IncioFimBusca localReinicialize algumas partculasSIMSIMSIMNONONO

Restries da tcnicaMapeamento das partculas em direo s soluesDimensesFuno de fitnessNmero de partculasEstrutura do aprendizado socialValores dos parmetros (1 2 w)Como eliminar partculas em regies infactveisCritrio de parada

Principais elementosIntensificao a explorao das solues encontradas em procuras anterioresDiversificao a busca por solues ainda no visitadasEncontrar o equilbrioIntensificaoDiversificaoIdentifica rapidamente regies com potencial para melhores soluesEncontra rapidamente a melhor soluo de uma regio

Exemplo

Utilizar o algoritmo de PSO para encontrar pontos de mnimo da funo abaixo, usando as 3 partculas dadas abaixo:

pso

Pesquisas atuais de PSOPSO com termos sociais mltiplosDiferentes ndices de medidas para PSOPartculas heterogneasPSO hierrquicoPSO para o problema de escalonamento de tarefas(JSS)PSO para roteamento de veculosPSO para extrao de regras de RNAPSO para problemas com restries de recursos

Adaptaes da PSO para o PCV [M. Clerc, 2004; T. R. Machado e H. S. Lopes, 2005]PartculasEm PCV procuramos ciclos com N+1 vrtices. Logo uma partcula consiste em um ciclo com as cidades do PCV:x = (n1, n2, , nN, nN+1)Esta partcula somente aceita se todos os arcos (ni, ni+1) existemFuno de fitness

VelocidadeDefinir um operador v que quando aplicado a uma partcula retorna uma outra posio.

Definimos ento uma lista de transposies de elementos da partcula. Estas transposies so trocas de 2 a 2:v = {(ik, jk)}, onde ik, jk {1, 2,, N} que significa: troque os elementos (i1, j1), depois (i2, j2), at k.MovimentoO movimento da partcula obtido aplicando-se a velocidade partcula: x=x + v.Exemplo: x=(1, 2, 3, 4, 5, 1), v={(1, 2), (2, 3)}com a primeira troca (1, 2), temos: x=(2, 1, 3, 4, 5, 2)com a segunda troca (2, 3), temos x=(3, 1, 2, 4, 5, 3)SubtraoA diferena xi xj definida como a velocidade que deve ser aplicada na posio xj para obter a posio xi. Quando xi = xj, temos v = 0AdioO resultado da soma de duas velocidade vi + vj a lista de transposies primeiro de vi, depois de vj.

Multiplicao de escalar por vetorquando c = 0, temos cv =quando c [0, 1], trunca-se v.Exemplo:c = 0,6; e v = {(1, 2), (3, 5), (17, 23), (7, 3), (8, 19)}logo, cv = {(1, 2), (3, 5), (17, 23)}quando c > 1, defina c = k + c, onde k N, e c [0, 1]. logo, cv = v + v ++ v + cv k vezesvi = wvi + 1.rand().(pbesti - xi) + 2.rand().(pgbesti - xi)xi = xi + vi

A combinao dos vetores pbest, pgbest, lbest e nbest direciona uma partcula para melhores posies do que um PSO padro.

pbest

pgbest

PSO padro

pbest

pgbest

nbest

lbest

PSO com mltiplasestruturas sociaisPSO com estruturas de mltiplos grupos sociais [Pongchairerks, Kachitvichyanukul, 2006]

Mais aplicaesPSO trata-se de uma tcnica atrativa, porque : computacionamente baratarobustasimplesOutras aplicaes:Controle de veculos por controle remotoControle para detectar e eliminar tumoresO filme da Disney O Rei Leo foi o primeiro a usar tecnologia de nuvem de partculas para fazer a cena da debandada de pssaros. O filme da New Line Cinema O Senhor dos Anis tambm utilizou tcnicas semelhantes nas cenas de batalhas. Rplica de dados em grade

53