Apresentao do PowerPoint

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos1Algoritmos Evolucionrios Hbridos (Memticos)Caio Fleming Ferreira de Carvalho Cunha

Fellipe de Oliveira Pinto

16 de Maio de 2012

1EmentaObjetivosMotivaes para hibridizao dos AEs.Introduo aos algoritmos memticos.Busca local: Adaptao de Lamarck vs. de Baldwin.Estrutura de um algoritmo memtico.Problemas de design para algoritmos memticos: Diversidade, escolha de operadores e uso de conhecimento.Exemplo de aplicao: Problema Timetabling Referncias bibliogrficas.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos22ObjetivosDiscutir algoritmos baseados em AE, os quais so incorporados a outros mtodos ou estruturas de dados incorporados a eles, denominados Algoritmos Memticos (MA);Explicitar o raciocnio por trs dos MAs;Mostrar as possveis combinaes dos AEs com outras tcnicas;Fornecer os pontos para projetar adequadamente um Algoritmo Hibrido;

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos3Motivaes para Hibridizao de AEsProblemas complexos podem ser decompostos em sub-problemas, os quais podem ser resolvidos com mtodos apropriados para cada um deles;

Na verdade o AE puro no exibe uma performance uniforme para uma ampla faixa de problemas.

Pode-se combinar heursticas especficas a um AE formando modelos hbridos, alterando a performance global do mtodo; Pode-se obter melhores resultados quando se possui conhecimentos especficos do problema.

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos4Motivaes para Hibridizao de AEsO conhecimento especfico no algoritmo hbrido varivel, podendo ser ajustada;UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos5Faixa de problemasPerformance do mtodoMtodos adaptadosEA puroEA enriquecido com conhecimento Motivaes para Hibridizao de EAsAEs no so bons em encontrar a soluo final, pois evoluem lentamente devido a natureza estocstica dos operadores.

Pode-se melhorar o algoritmo incorporando um passo de busca local.

A combinao de AEs com operadores de busca local que atuam dentro do lao AE ou entregam conhecimento especfico de instncias do problemas denominado Algoritmo Memtico;UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos6Algoritmos Memticos Memes Genes

Ideia de meme como agente que pode transformar um candidato a soluo.A adio de uma fase de aprendizagem (desenvolvimento) ao ciclo evolucionrio pode ser vista como uma interao meme-gene.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos7

Unidades de transmisso culturalUnidades de transmisso biolgica

Busca LocalBusca local um processo iterativo para examinar o conjunto de pontos na vizinhana da soluo atual e a substituir por um vizinho melhor, caso exista.

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos8

Busca LocalComponentes que afetam o algoritmo: Regra de pivoteamento (lao interno) :steepest ascent busca entre todos os vizinhos o mais apto, contar = n(i);greedy ascent busca o primeiro vizinho que se mostra mais rpido, (contar = |n(i)|) ou (melhor!= i);

Regra de profundidade (lao externo):determina nmero de iteraes da busca local;Pode ser aplicado a uma nica iterao (iteraes = 1) ou contnua (contar = |n(i)| e melhor =i) ;Efeitos na performance do algoritmo, tempo e qualidade; UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos9Busca LocalFuno geradora de vizinhana:

n(i) - conjunto de pontos que podem ser alcanados atravs da aplicao de algum operador de movimento ao ponto i. Representao equivalente: Grafo no direcionado G(v,e) v o conjunto de vrtices que representa todos pontos no espao de busca, as solues em potencial. e o conjunto de arestas que representa as possveis transies que podem ocorrer a partir da aplicao de um nico operador. As arestas podem ser direcionadas e ponderadas.

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos10Busca Local Definida pela combinao de vizinhana, n(x), e regra de pivoteamento. Em que n(x) constitui o conjunto de pontos alcanveis com aplicao do operador de movimento (fitness landscapes), os quais afetam a eficincia e efetividade da busca local. v = {a, b , c, d, e, f, g, h} n(g) = {c, f, h}e1 = {ab, ad, ae, bc, bf, cd, cg, dh, fg, fe, gh, eh} simtrica e valores equiprovveisUFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos11abcdefghBusca LocalPontos localmente timos para uma estrutura de vizinhana podem no ser para outra, exceto se localmente timo.Variaes: Pode-se aplicar a busca ao espao de busca ou espao de solues; Ajustando o nmero de iteraes a serem realizadas pela busca local; Busca local pode ser aplicada:- a populao total; - para o indivduo mais apto; - para o indivduo menos apto;UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos12Lamarckianismo e Efeito BaldwinLamarckiano se as caractersticas adquiridas durante seu tempo de vida so herdadas por sua prole. ex: substituir o indivduo com vizinho mais apto.

Baldwiniano se o processo evolucionrio for guiado pelas adaptaes favorveis sem que as modificaes nas aptides dos indivduos, devido a aprendizagem ou desenvolvimento, se convertam em mudanas de caractersticas genticas. ex: indivduo recebe aptido (mas no gentipo) do vizinho mais apto.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos13Estrutura de um Algoritmo MemticoUFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos14POP. INICIALGRUPO DE REPRODUODESCENDENTEDESCENDENTE

-Solues conhecidas-Heurstica-Inicializao Seletiva-Busca LocalCruzamentoMutaoUso de informaes de um problema especficoNo operadorUso de informaes de um problema especficoNo operadorBusca LocalBusca LocalSeleo modificada de operadoresSeleoEstrutura de um Algoritmo Memtico Inicializao Heurstica ou InteligenteUm conhecimento existente pode ser incorporado ao AE na fase de inicializao. benefcios por iniciar AEs com solues existentes: Evitar a perda de esforo computacional refletindo aumento de eficincia (velocidade);

Direcionar busca para regies promissoras do espao de busca levando a aumentar efetividade;

Dividir o esforo computacional entre inicializao heurstica e busca evolucionria pode gerar melhores resultados do que gastar todo o esforo em busca evolucionria apenas;UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos15Estrutura de um Algoritmo Memtico Inicializao Heurstica ou InteligenteManeiras de se alterar a funo inicializao: Seeding (Semeadura): semeia a populao com uma ou mais solues boas a partir de outras tcnicas (tentativa e erro, heursticas usando informaes de instncia especfica);Inicializao seletiva: gera-se grande nmero de solues aleatrias e seleciona-se a populao inicial a partir delas: - Realizar N torneios de tamanho k; - Selecionar um conjunto baseado na fora e diversidade.Realizar busca local em cada membro da populao (aleatoriamente), formando um conjunto de indivduos localmente timos.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos16Estrutura de um Algoritmo Memtico Inicializao Heurstica ou InteligenteManeiras de se alterar a funo inicializao:Empregar um ou mais mtodos anteriores para identificar uma ou mais boas solues, e ento clonar e aplicar mutao com altas taxas (mass mutation) para formar um nmero de indivduos na vizinhana do ponto inicial.

Efeito de se variar a proporo da populao inicial :-Uso de pequena propores das solues na populao inicial auxilia na busca gentica;-Performance mdia melhora com o aumento da proporo;-Melhor performance vem de uma populao inicial mais aleatria.

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos17Operadores inteligentes de variao incorporam conhecimento especfico da instncia ou do problema, uma forma de introduzir tendncia dentro dos operadores:Exemplo 1: Aumentar a probabilidade de escolha de caractersticas mais compactas para emprego em um classificador.

Exemplo 2: Genes codificando instrues de microprocessador de modo a serem agrupados em conjuntos de efeitos similares.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos18Estrutura de um Algoritmo Memtico Hibridizao com Operadores de Variao Uso de conhecimento especfico do problema:Incorporao de uma fase de busca local dentro de um operador de recombinao.Ex.: Testar todas as possveis orientaes dos dois fragmentos de estrutura de uma protena separados pelo ponto de cruzamento e pegar a mais favorvel. Se nenhum ajuste possvel for encontrado escolhido outro ponto de cruzamento.

Uso de conhecimento especfico da instncia:Operadores recebem heurstica muito especfica.Ex.: Operador DPX para TSP, preserva a diversidade evitando convergncia prematura. UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos19Estrutura de um Algoritmo Memtico Hibridizao com Operadores de Variao Consiste de uma ou mais fases de melhora no indivduo da populao durante o ciclo AE;A busca Local atua sobre toda soluo criada pela mutao ou recombinao, pode ocorrer em fases distintas do ciclo;

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos20Estrutura de um Algoritmo Memtico Busca Local na Sada de Operadores de Variao

Krasnogor para reduzir o pior caso de execuo, preciso escolher uma busca local em que o operador movimento diferente dos operadores da recombinao e mutao. Implica em diversificao dos pontos gerados, a qual melhorada com altas taxas de mutao ou uso de operadores com estruturas de vizinhana distintasUFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos21Estrutura de um Algoritmo Memtico Busca Local na Sada de Operadores de VariaoUsado no mapeamento antes da avaliao da aptido;Ex: Uso de conhecimento especfico da instncia dentro do decodificador ou da funo de reparo. Problema da mochila.

Uma linha comum destas aproximaes fazer uso de heursticas existentes e informaes do domnio onde possvel.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos22Estrutura de um Algoritmo Memtico Hibridizao no Mapeamento gentipo - fentipoProblemas de Projetos em Algoritmos MemticosAMs no so solues mgicas para problemas de otimizao.

Deve-se tomar cuidado com:Diversidade da populao.Escolha dos operadores.Uso do conhecimento adquirido durante o processo de otimizao.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos23Preservao de DiversidadeO problema da convergncia prematura.Tcnicas para combater este problema: - Usar somente uma proporo pequena de boas solues conhecidas na populao inicial. - Usar operadores de recombinao que so projetados para preservar diversidade (como Merzs DPX). - Modificar operador de seleo para prevenir duplicaes. - Usar um mtodo de Boltzmann (Simulated anneling) para o operador de seleo ou o critrio de aceitao da busca local.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos24Preservao de DiversidadeManuteno do sucesso de diversidade para populao pode ser justificado:O cruzamento DPX de Merz explicitamente gera indivduos que so eqidistantes para cada pai, tendo a mesma distncia entre os pais.

Operador adaptativo de Boltzmann, por Krasnogor, usa critrio de aceitao de novo indivduo baseado no cozimento simulado. A temperatura inversamente proporcional diversidade da populao.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos25Critrio de Boltzmann A dinmica induzida tal que:Populao diversa - espalhamento da aptido alto, portanto temperatura baixa, ento aceita apenas de movimentos melhores em relao aptido (Explotao).

Populao pouco dispersa, portanto, temperaturas altas, mais provvel a aceitao de movimentos que pioram a aptido (Explorao).UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos26Escolha dos operadoresO fator Principal no projeto de um AM : - Escolha da heurstica de melhoramento ou do operador de movimento da busca local. - A escolha do operador de movimento pode ter efeito dramtico na eficincia e na efetividade da busca local. - Vantagens em usar busca local com um operador de movimento que diferente dos operadores de movimento usados pela mutao e pelo cruzamento. - Podem-se disponibilizar mltiplos operadores de busca local, escolhendo-se qual a ser aplicado em cada caso.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos27Uso do Conhecimento AM concentram o uso e o reuso de conhecimento ganho durante o processo de otimizao (automtico ou no)Tabu search Lista de Pontos visitados mantido para proibir que o Algoritmo retorne a estes (mantm a diversidade).A seleo/aceitao de Boltzmann utiliza o espalhamento do gentipo da populao atual ou passada, para deciso de aceitao de novas indivduos.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos28Resumo sobre Algoritmos HbridoSo utilizados em diversos problemas ;Pode envolver operadores de outros algoritmos ou incorporar um domnio especfico do conhecimento do problema.AMs tm se mostrado mais rpidos e mais precisos do que os AGs sobre alguns problemasDeve-se controlar a escolha dos operadores e cuidar da preservao da diversidade com o objetivo de fugir de timos locais.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos29Exemplo: Problema Timetabling Atribuio de horrios e salas para cursos para restries: Hard:- Estudantes no podem ser atribudos a mais de um curso ao mesmo tempo;- A sala deve satisfazer caractersticas requeridas pelo curso;- O nmero de estudantes a capacidade da sala;- No mais do que um curso atribudo a um horrio por sala;Soft:- Um estudante tenha um curso no ltimo horrio;- Um estudante tem mais do que 2 cursos consecutivos;- Um estudante tem um nico curso em um dia;UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos30O problema possui:-Um conjunto de N cursos;-45 horrios -Um conjunto de R salas;-Um conjunto de F sala a-Um conjunto de M estudantes;

O objetivo do problema satisfazer a restrio hard e minimizar a violao das restries soft.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos31

Problema Timetabling Problema TimetablingA tcnica usada um operador de mutao leve (light) por um algoritmo de melhora interativa aleatria.Representao: direta, cada gene contm informao sobre horrio e sala para um curso particular (ci), i {1,..,N).Populao inicial: usa um algoritmo de construo que gera timetables aleatrios, 100 indivduos.Seleo de indivduos para nova populao: Roulette Wheel.Mutao: aleatria sobre 20% dos cursos de 20% dos indivduos selecionados.Busca Aleatria: Randomised Iterative Improvement Algorithm, sempre aceita uma soluo melhor e uma pior com certa probabilidade (critrio de monte carlo ).Condio de Terminao: Aps 200000 rodadas.

UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos32

Problema TimetablingAlgoritmo:UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos33POPULAOSELEOMUTAOROULETTE WHEELBUSCA LOCAL: Ramdomised iterative improvementGRUPO DE SELEOReferncia BibliograficaAbdullah, Salwani, Burke, E. K., and McCollum, Barry A Hybrid Evolutionary Approach to the University Course Timetabling Problem. IEEE Congress on Evolutionary Computation, pp. 1764 1768 (2007b). Burke, E. K., Newall, J. P. A multi-stage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, v. 3, n. 1, p. 63-74, April 1999.UFRJ COOPE 16/05/2012Algoritmos Evolucionrios Hbridos34