Métodos Heurísticos Métodos Heurísticos Genéricos:Genéricos:

Meta-heurísticas e Hiper-heurísticasMeta-heurísticas e Hiper-heurísticas

Igor Ribeiro Sucupira(Mestrando em Ciência da Computação pelo IME-USP)

Orientador: Prof. Dr. Flávio S. C. da Silva

Meta-heurísticas e hiper-heurísticasMeta-heurísticas e hiper-heurísticas

São métodos heurísticos que podem lidar São métodos heurísticos que podem lidar com qualquer problema de otimização, ou com qualquer problema de otimização, ou seja, que não estão atrelados a um seja, que não estão atrelados a um problema específico.problema específico.

Neste seminárioNeste seminário

Meta-heurísticas:Meta-heurísticas:– Definição.Definição.– Tipos.Tipos.– Uma meta-heurística clássica.Uma meta-heurística clássica.– Uma meta-heurística recente.Uma meta-heurística recente.

Hiper-heurísticas:Hiper-heurísticas:– Definição.Definição.– Exemplos concretos.Exemplos concretos.

Meta-heurísticasMeta-heurísticas

Do sítio Do sítio www.metaheuristics.netwww.metaheuristics.net : :

““Uma meta-heurística é um conjunto de Uma meta-heurística é um conjunto de conceitos que podem ser utilizados para conceitos que podem ser utilizados para definir métodos heurísticos aplicáveis a um definir métodos heurísticos aplicáveis a um extenso conjunto de problemas.”extenso conjunto de problemas.”

Tipos de meta-heurísticasTipos de meta-heurísticas

Uma possível divisão, por Melián et al. Uma possível divisão, por Melián et al. ((Universidad de La LagunaUniversidad de La Laguna - Espanha): - Espanha):– Meta-heurísticas de busca por entornosMeta-heurísticas de busca por entornos: percorrem o : percorrem o

espaço de busca levando em conta, fundamentalmente, a espaço de busca levando em conta, fundamentalmente, a “vizinhança” da solução em mãos, definida como o conjunto “vizinhança” da solução em mãos, definida como o conjunto de soluções que podem ser obtidas a partir da aplicação de de soluções que podem ser obtidas a partir da aplicação de algum operador à solução atual.algum operador à solução atual.

– Meta-heurísticas de relaxaçãoMeta-heurísticas de relaxação: simplificam o problema : simplificam o problema (criando um (criando um problema relaxadoproblema relaxado) e utilizam a solução ) e utilizam a solução encontrada como guia para o problema original.encontrada como guia para o problema original.

– Meta-heurísticas construtivasMeta-heurísticas construtivas: definem de forma : definem de forma meticulosa o valor de cada componente da solução.meticulosa o valor de cada componente da solução.

– Meta-heurísticas evolutivasMeta-heurísticas evolutivas: lidam com uma população : lidam com uma população de soluções, que evolui, principalmente, através da interação de soluções, que evolui, principalmente, através da interação entre seus elementos.entre seus elementos.

Exemplos (busca por entornos)Exemplos (busca por entornos)

GLS (GLS (Guided Local SearchGuided Local Search): busca monotônica. ): busca monotônica. Porém, altera a função objetivo ao encontrar um Porém, altera a função objetivo ao encontrar um ótimo local.ótimo local.

Simulated Annealing Simulated Annealing : não monotônica. : não monotônica. Probabilidade de “movimentos ruins” decresce Probabilidade de “movimentos ruins” decresce exponencialmente com o aumento na diferença exponencialmente com o aumento na diferença de custo.de custo.

Busca Tabu: não monotônica. Classifica como Busca Tabu: não monotônica. Classifica como tabutabu os componentes de soluções adicionados os componentes de soluções adicionados ou removidos recentemente.ou removidos recentemente.

Busca Reativa: Busca Tabu com detecção de Busca Reativa: Busca Tabu com detecção de ciclos.ciclos.

Exemplo (construtiva)Exemplo (construtiva)

GRASP (GRASP (Greedy Randomized Adaptive Greedy Randomized Adaptive Search ProcedureSearch Procedure): cada iteração é ): cada iteração é composta por uma fase construtiva e uma composta por uma fase construtiva e uma fase de busca por entornos. Em cada passo fase de busca por entornos. Em cada passo da fase construtiva:da fase construtiva:– Selecionam-se os componentes que causam Selecionam-se os componentes que causam

melhor efeito se adicionados à solução atual.melhor efeito se adicionados à solução atual.– Acrescenta-se um desses elementos Acrescenta-se um desses elementos

(selecionado aleatoriamente) à solução.(selecionado aleatoriamente) à solução.

Exemplo (relaxação)Exemplo (relaxação)

Relaxação Lagrangeana: remove Relaxação Lagrangeana: remove algumas restrições de um problema de algumas restrições de um problema de programação linear, atribui um peso programação linear, atribui um peso (multiplicador de Lagrange) a cada (multiplicador de Lagrange) a cada uma delas e altera a função objetivo uma delas e altera a função objetivo para penalizar as soluções que seriam para penalizar as soluções que seriam inviáveis no problema original.inviáveis no problema original.

Exemplos (evolutivas)Exemplos (evolutivas)

Algoritmos genéticos.Algoritmos genéticos. Algoritmos meméticos: algoritmos genéticos que Algoritmos meméticos: algoritmos genéticos que

realizam otimização local.realizam otimização local. Estimação de distribuição: verificam a distribuição Estimação de distribuição: verificam a distribuição

dos componentes nas melhores soluções e criam a dos componentes nas melhores soluções e criam a geração seguinte aleatoriamente, segundo essa geração seguinte aleatoriamente, segundo essa distribuição.distribuição.

Busca dispersa e Busca dispersa e Path relinkingPath relinking : criam caminhos : criam caminhos entre soluções e geram a população seguinte a entre soluções e geram a população seguinte a partir das soluções que aparecem nesses partir das soluções que aparecem nesses caminhos.caminhos.

Outros exemplosOutros exemplos

Meta-heurísticas de decomposiçãoMeta-heurísticas de decomposição: indicam : indicam como decompor o problema em instâncias e utilizar como decompor o problema em instâncias e utilizar as soluções resultantes na construção da solução as soluções resultantes na construção da solução para o problema original.para o problema original.

Ant colony optimizationAnt colony optimization : formigas artificiais : formigas artificiais percorrem um grafo em que cada aresta representa percorrem um grafo em que cada aresta representa um componente de solução.um componente de solução.

Otimização extremaOtimização extrema: em cada iteração, remove o : em cada iteração, remove o pior componente.pior componente.

Particle swarm optimizationParticle swarm optimization.. Iterated local searchIterated local search : tenta realizar uma espécie : tenta realizar uma espécie

de busca por entornos nos ótimos locais.de busca por entornos nos ótimos locais.

Exemplos em detalhesExemplos em detalhes

Uma meta-heurística clássica:Uma meta-heurística clássica:– Algoritmo genético.Algoritmo genético.

Uma meta-heurística recente:Uma meta-heurística recente:– Particle swarm optimizationParticle swarm optimization (1995). (1995).

Algoritmo genéticoAlgoritmo genético

É uma meta-heurística evolutiva.É uma meta-heurística evolutiva. Cada elemento da população é uma Cada elemento da população é uma

seqüência de símbolos (“genes”), chamada seqüência de símbolos (“genes”), chamada cromossomo.cromossomo.

Exemplo simples: problema da mochila 0-1 Exemplo simples: problema da mochila 0-1 com com nn itens. Cromossomo tem itens. Cromossomo tem nn genes. genes. Cada Cada ii -ésimo gene é um bit, associado ao -ésimo gene é um bit, associado ao ii

-ésimo item.-ésimo item.

Algoritmo genéticoAlgoritmo genético Operador de mutação: escolhe aleatoriamente um Operador de mutação: escolhe aleatoriamente um

gene do cromossomo e o altera (para um valor gene do cromossomo e o altera (para um valor aleatório).aleatório).

TTmm ЄЄ [0, 1] [0, 1] é a é a taxa de mutaçãotaxa de mutação.. Operador de cruzamento: gera um par de Operador de cruzamento: gera um par de

cromossomos a partir dos genes de outro par.cromossomos a partir dos genes de outro par. TTcc ЄЄ [0, 1] [0, 1] é a é a taxa de cruzamentotaxa de cruzamento.. Função de aptidão: mede a qualidade de um Função de aptidão: mede a qualidade de um

indivíduo.indivíduo. Exemplo (mochila - Exemplo (mochila - ii -ésimo item tem valor -ésimo item tem valor vvii):):

n

iii penalidadevccf

1)( .)(

Passagem entre geraçõesPassagem entre gerações

mm : tamanho da população. : tamanho da população. Partindo de Partindo de M = {}M = {}, repetir , repetir mm vezes: vezes:

– Selecione aleatoriamente um indivíduo da população. Selecione aleatoriamente um indivíduo da população. Probabilidades são proporcionais às aptidões.Probabilidades são proporcionais às aptidões.

– Adicionar a Adicionar a MM o indivíduo selecionado. o indivíduo selecionado. Para formar a próxima população, repita Para formar a próxima população, repita m/2m/2

vezes:vezes:– Selecione um par de indivíduos de Selecione um par de indivíduos de MM e, com e, com

probabilidade probabilidade TTcc, realize cruzamento em um ponto , realize cruzamento em um ponto aleatório, gerando dois outros indivíduos.aleatório, gerando dois outros indivíduos.

– Adicione os dois indivíduos gerados à nova população.Adicione os dois indivíduos gerados à nova população.– Realize mutação nos indivíduos (probabilidade Realize mutação nos indivíduos (probabilidade TTmm).).

Algumas aplicaçõesAlgumas aplicações Problema da mochila (múltiplo e 0-1).Problema da mochila (múltiplo e 0-1). Problemas de agendamento.Problemas de agendamento. Problemas de coloração de vértices (ou arestas).Problemas de coloração de vértices (ou arestas). Terminal assignment problemTerminal assignment problem.. Problema da soma de subconjunto (Problema da soma de subconjunto (subset sumsubset sum).). Problema do corte máximo.Problema do corte máximo. Problema da cobertura por conjuntos (Problema da cobertura por conjuntos (set coveringset covering).). Conjunto independente máximo.Conjunto independente máximo. Problema da cobertura mínima de vértices.Problema da cobertura mínima de vértices. Codificação e decodificação de códigos de grupo.Codificação e decodificação de códigos de grupo. Problema da montagem de fragmentos de DNA Problema da montagem de fragmentos de DNA

((fragment assemblyfragment assembly).).

Particle Swarm OptimizationParticle Swarm Optimization

Desenvolvida por James Kennedy (psicólogo) e Desenvolvida por James Kennedy (psicólogo) e Russell Eberhart (engenheiro), com base no Russell Eberhart (engenheiro), com base no comportamento de pássaros em revoadas, comportamento de pássaros em revoadas, modelado pelo biólogo Frank Heppner.modelado pelo biólogo Frank Heppner.

Elementos do algoritmo:Elementos do algoritmo:– A A : população de : população de agentesagentes..– xxi i : : posiçãoposição do agente do agente aaii no espaço de soluções. no espaço de soluções.– f f : função de avaliação.: função de avaliação.– vvi i : velocidade do agente : velocidade do agente aaii..– V(aV(aii) ) : conjunto : conjunto fixofixo de de vizinhosvizinhos do agente do agente aaii..– Todos os agentes estão conectados, direta ou Todos os agentes estão conectados, direta ou

indiretamente.indiretamente.

IteraçãoIteração

Para cada agente Para cada agente aaii : :vvii := := ωω.v.vii + + ηη11.rand().(y.rand().(y i i - x- xii) + ) + ηη22.rand().(z.rand().(z i i - x- xii))xxii := x := xii + v + vii

Sendo:Sendo:– yyii : melhor posição em que : melhor posição em que aaii já esteve. já esteve.– zzii : melhor posição em que algum vizinho de : melhor posição em que algum vizinho de

aaii já esteve. já esteve.

Aplicações de PSOAplicações de PSO

Aplicações bem-sucedidas mais comuns:Aplicações bem-sucedidas mais comuns:– Evolução de redes neurais artificiais.Evolução de redes neurais artificiais.– Extração de regras de RNAs.Extração de regras de RNAs.

Aplicação recente:Aplicação recente:– Bandwidth Minimization ProblemBandwidth Minimization Problem (2003). (2003).

Algumas aplicações pontuais recentes (2004):Algumas aplicações pontuais recentes (2004):– Caminho ótimo para operações de perfuração Caminho ótimo para operações de perfuração

automatizadas.automatizadas.– Mineração de dados para tarefas de classificação.Mineração de dados para tarefas de classificação.– Posicionamento de bases em computação móvel.Posicionamento de bases em computação móvel.– Aproximação poligonal ótima de curvas digitais.Aproximação poligonal ótima de curvas digitais.

Motivação para as hiper-heurísticasMotivação para as hiper-heurísticas

Implementações de meta-heurísticas podem ser Implementações de meta-heurísticas podem ser algoritmos extremamente poderosos. Porém, algoritmos extremamente poderosos. Porém, normalmente isso exige alterações substanciais normalmente isso exige alterações substanciais para cada novo problema a ser tratado.para cada novo problema a ser tratado.

O objetivo das hiper-heurísticas é resolver esse O objetivo das hiper-heurísticas é resolver esse conflito entre facilidade de implementação e conflito entre facilidade de implementação e qualidade. Portanto, a idéia qualidade. Portanto, a idéia nãonão é é necessariamente superar a qualidade das outras necessariamente superar a qualidade das outras técnicas.técnicas.

Conceito de hiper-heurísticaConceito de hiper-heurística

O termo O termo hiper-heurísticahiper-heurística (2000) se refere aos (2000) se refere aos algoritmos heurísticos que operam em um alto algoritmos heurísticos que operam em um alto nível de generalidade. O domínio de uma hiper-nível de generalidade. O domínio de uma hiper-heurística é composto por conjuntos de heurística é composto por conjuntos de heurísticas (e não pelo conjunto das instâncias heurísticas (e não pelo conjunto das instâncias de um problema de otimização).de um problema de otimização).

Uma hiper-heurística encontra soluções Uma hiper-heurística encontra soluções indiretamente, utilizando de maneira inteligente indiretamente, utilizando de maneira inteligente as heurísticas que lhe foram fornecidas.as heurísticas que lhe foram fornecidas.

Ross et al. Ross et al. (Napier / (Napier /

Nottingham) - ) - 20032003

VantagensVantagens

Simplicidade: para adaptar uma hiper-heurística Simplicidade: para adaptar uma hiper-heurística a um novo problema, basta alterar o conjunto a um novo problema, basta alterar o conjunto de heurísticas simples de baixo nível.de heurísticas simples de baixo nível.

Vantagens potenciais:Vantagens potenciais:– Robustez: uma hiper-heurística é um algoritmo bem Robustez: uma hiper-heurística é um algoritmo bem

definido que, idealmente, apresenta eficiência e definido que, idealmente, apresenta eficiência e eficácia no tratamento de diversos problemas de eficácia no tratamento de diversos problemas de otimização, pois sua “inteligência” está implementada otimização, pois sua “inteligência” está implementada em um nível independente do domínio do problema.em um nível independente do domínio do problema.

– Os erros de decisão praticados por cada uma das Os erros de decisão praticados por cada uma das heurísticas pouco elaboradas são suprimidos em um heurísticas pouco elaboradas são suprimidos em um processo de intercalação. A hiper-heurística é, processo de intercalação. A hiper-heurística é, portanto, insensível a essas falhas.portanto, insensível a essas falhas.

Um exemplo concretoUm exemplo concreto

Hiper-heurística desenvolvida em 2002, por Hiper-heurística desenvolvida em 2002, por Cowling et al. (Cowling et al. (Bradford / Nottingham)..

A hiper-heurística é um algoritmo genético:A hiper-heurística é um algoritmo genético:– Cada cromossomo é uma seqüência de inteiros no Cada cromossomo é uma seqüência de inteiros no

intervalo [0, intervalo [0, nnhh -- 1], sendo 1], sendo nnhh o número de o número de heurísticas de baixo nível.heurísticas de baixo nível.

– A população inicial é criada com números aleatórios.A população inicial é criada com números aleatórios. Tamanho da população: 30.Tamanho da população: 30. Número de gerações: 200. Porém, 100 Número de gerações: 200. Porém, 100

gerações fornecem resultados semelhantes.gerações fornecem resultados semelhantes. Elitismo: população com os 30 melhores entre Elitismo: população com os 30 melhores entre

a população atual e a população gerada.a população atual e a população gerada.

Versões da hiper-heurísticaVersões da hiper-heurística

Oito versões:Oito versões:– Quatro com tamanho fixo de cromossomo.Quatro com tamanho fixo de cromossomo.– Quatro com tamanho adaptativo de cromossomo.Quatro com tamanho adaptativo de cromossomo.

2.2. Taxas fixas e função de aptidão simples.Taxas fixas e função de aptidão simples.3.3. Taxas adaptativas e função de aptidão simples.Taxas adaptativas e função de aptidão simples.4.4. Taxas fixas e função de aptidão com tempo de Taxas fixas e função de aptidão com tempo de

CPU.CPU.5.5. Taxas adaptativas e função de aptidão com Taxas adaptativas e função de aptidão com

tempo de CPU.tempo de CPU.

Características das versõesCaracterísticas das versões Versões com taxas fixas:Versões com taxas fixas:

– Taxa de cruzamento: 0,6.Taxa de cruzamento: 0,6.– Taxa de mutação: 0,1.Taxa de mutação: 0,1.

Taxas adaptativas: Taxas adaptativas: TmTm se eleva (e se eleva (e TcTc diminui) quando diminui) quando não há aumento na aptidão média por três gerações não há aumento na aptidão média por três gerações seguidas. O inverso ocorre quando há aumento de seguidas. O inverso ocorre quando há aumento de aptidão por três gerações. Aumento de uma taxa aptidão por três gerações. Aumento de uma taxa T := (T T := (T + 1) / 2+ 1) / 2. Diminuição: divisão por 2.. Diminuição: divisão por 2.

Função de aptidão simples: valor objetivo resultante da Função de aptidão simples: valor objetivo resultante da aplicação do cromossomo à melhor solução já aplicação do cromossomo à melhor solução já encontrada em todo o processo.encontrada em todo o processo.

Função de aptidão com tempo de CPU: o valor acima é Função de aptidão com tempo de CPU: o valor acima é dividido pelo tempo de CPU tomado na aplicação do dividido pelo tempo de CPU tomado na aplicação do cromossomo.cromossomo.

Número variável de genesNúmero variável de genes

Operadores adicionais, que lidam com Operadores adicionais, que lidam com subseqüências de genes:subseqüências de genes:– Um operador de cruzamento permuta a melhor Um operador de cruzamento permuta a melhor

seqüência de um cromossomo com a melhor seqüência de um cromossomo com a melhor seqüência do outro.seqüência do outro.

– Um operador de mutação remove a pior seqüência do Um operador de mutação remove a pior seqüência do cromossomo.cromossomo.

– Outro operador de mutação insere no cromossomo a Outro operador de mutação insere no cromossomo a melhor seqüência de um outro cromossomo melhor seqüência de um outro cromossomo (selecionado aleatoriamente).(selecionado aleatoriamente).

Cromossomos muito grandes são penalizados Cromossomos muito grandes são penalizados pela função de aptidão.pela função de aptidão.

AplicaçãoAplicação Problema: agendamento de cursos.Problema: agendamento de cursos. DD : conjunto de : conjunto de docentesdocentes.. LL : centros de treinamento ( : centros de treinamento (localidadeslocalidades), cada um com ), cada um com

um certo número de um certo número de salassalas.. PP : matriz de : matriz de penalidadespenalidades ( (DD xx LL).). nn : número de : número de vagasvagas na grade horária. na grade horária. CC : conjunto de : conjunto de cursoscursos. A cada curso . A cada curso cc estão associados: estão associados:

– Um conjunto de docentes competentes para ministrá-lo.Um conjunto de docentes competentes para ministrá-lo.– Um intervalo dentro do qual Um intervalo dentro do qual cc deve se iniciar. deve se iniciar.– Um conjunto de localidades.Um conjunto de localidades.– Uma duração (entre 1 e 5 vagas da grade horária).Uma duração (entre 1 e 5 vagas da grade horária).– Um valor que indica a sua Um valor que indica a sua prioridadeprioridade (importância). (importância).

Agendamento de cursosAgendamento de cursos

Objetivo: maximizar Objetivo: maximizar W - DW - D, sendo:, sendo:– WW : soma das prioridades dos cursos : soma das prioridades dos cursos

realizados.realizados.– DD : soma das penalidades aplicadas. : soma das penalidades aplicadas.

Restrições adicionais:Restrições adicionais:– Nenhum docente pode ministrar dois cursos Nenhum docente pode ministrar dois cursos

simultaneamente.simultaneamente.– Nenhum docente pode trabalhar em mais de Nenhum docente pode trabalhar em mais de

60% das vagas de horários.60% das vagas de horários.

Heurísticas de baixo nívelHeurísticas de baixo nível

Tipo 1 (5 heurísticas): escolhem um curso e Tipo 1 (5 heurísticas): escolhem um curso e tentam agendá-lo.tentam agendá-lo.

Tipo 2 (4 heurísticas): idem, mas, na presença Tipo 2 (4 heurísticas): idem, mas, na presença de conflitos, tentam trocar os dados entre o de conflitos, tentam trocar os dados entre o curso escolhido e outro curso já agendado. Pode curso escolhido e outro curso já agendado. Pode ser exaustivo.ser exaustivo.

Tipo 3 (3 heurísticas): agendam o curso de Tipo 3 (3 heurísticas): agendam o curso de maior prioridade que melhore a solução mesmo maior prioridade que melhore a solução mesmo após a remoção dos cursos conflitantes.após a remoção dos cursos conflitantes.

ExperimentosExperimentos

Para efeito de comparação, também foram Para efeito de comparação, também foram desenvolvidas duas meta-heurísticas, desenvolvidas duas meta-heurísticas, implementadas de forma não trivial: um implementadas de forma não trivial: um algoritmo genético e um algoritmo memético.algoritmo genético e um algoritmo memético.

As heurísticas de baixo nível da hiper-heurística As heurísticas de baixo nível da hiper-heurística foram utilizadas como operadores para o foram utilizadas como operadores para o algoritmo memético.algoritmo memético.

Heurísticas Heurísticas HH11, ..., H, ..., H55 : cinco execuções da : cinco execuções da hiper-heurística mais simples em uma instância hiper-heurística mais simples em uma instância complexa.complexa.

ExperimentosExperimentos

Todas as instâncias têm 25 professores, 10 Todas as instâncias têm 25 professores, 10 localidades e 60 vagas de horários. São localidades e 60 vagas de horários. São baseadas em um caso real ocorrido em uma baseadas em um caso real ocorrido em uma instituição financeira de grande porte.instituição financeira de grande porte.

Defeito: poucas instâncias (5).Defeito: poucas instâncias (5). Instâncias diferem na complexidade:Instâncias diferem na complexidade:

– Número médio de professores associados a cada Número médio de professores associados a cada curso.curso.

– Número médio de localidades associadas a cada Número médio de localidades associadas a cada curso.curso.

Instância mais complexa: para cada curso, 1 Instância mais complexa: para cada curso, 1 localidade e 5 docentes.localidade e 5 docentes.

Outro exemplo concretoOutro exemplo concreto Hiper-heurística desenvolvida em 2001 por Cowling et al. Hiper-heurística desenvolvida em 2001 por Cowling et al.

(Nottingham).(Nottingham). Seleciona uma heurística de baixo nível a cada iteração.Seleciona uma heurística de baixo nível a cada iteração. Recebe os componentes da função objetivo, com seus Recebe os componentes da função objetivo, com seus

respectivos pesos.respectivos pesos. ff1c1c(H(Hii)) : desempenho histórico de : desempenho histórico de HHii em relação ao em relação ao

componente componente cc.. ff2c2c(H(Hii, H, Hkk)) : desempenho histórico (em relação ao : desempenho histórico (em relação ao

componente componente cc) de ) de HHii quando executada logo após quando executada logo após HHkk.. ff33(H(Hii)) : tempo decorrido desde a última execução de : tempo decorrido desde a última execução de HHii.. ααcc, , ββcc e e δδ : pesos dos fatores históricos. : pesos dos fatores históricos.

Fatores históricosFatores históricos

ff11 e e ff22 são critérios de intensificação. são critérios de intensificação. ff33 é um critério de diversificação. é um critério de diversificação. IntensificaçãoIntensificação : : exploração do espaço de busca exploração do espaço de busca

através de componentes e de tipos de através de componentes e de tipos de movimentos que, historicamente, levam a movimentos que, historicamente, levam a soluções de boa qualidade.soluções de boa qualidade.

DiversificaçãoDiversificação : tentativa de construção de : tentativa de construção de soluções que pertencem a regiões não soluções que pertencem a regiões não exploradas do espaço de busca e diferem exploradas do espaço de busca e diferem significativamente das soluções já encontradas.significativamente das soluções já encontradas.

Iteração da hiper-heurísticaIteração da hiper-heurística

Seleciona aleatoriamente um Seleciona aleatoriamente um componente componente cc, com probabilidades , com probabilidades proporcionais aos pesos.proporcionais aos pesos.

HHkk : última heurística executada. : última heurística executada. Executar-se-á a heurística Executar-se-á a heurística HiHi que que

maximiza o valor:maximiza o valor:ffcc(H(Hii) = α) = αcc∙f∙f1c1c(Hi) + β(Hi) + βcc∙f∙f2c2c(H(Hii, H, Hkk) + δ∙f) + δ∙f33(H(Hii))..

VersõesVersões

1.1. Pesos fixos para os fatores históricos e função objetivo Pesos fixos para os fatores históricos e função objetivo atômica.atômica.

2.2. Pesos adaptativos e função objetivo atômica.Pesos adaptativos e função objetivo atômica.3.3. Pesos adaptativos e função objetivo decomposta.Pesos adaptativos e função objetivo decomposta. Adaptabilidade:Adaptabilidade:

– Quando a heurística selecionada aumenta a qualidade da Quando a heurística selecionada aumenta a qualidade da solução, o peso do maior fator de intensificação (solução, o peso do maior fator de intensificação (max{α, β}max{α, β}) ) sofre elevação proporcional.sofre elevação proporcional.

– O mesmo peso é reduzido quando não há ganho de qualidade.O mesmo peso é reduzido quando não há ganho de qualidade.– Quando não há progresso durante Quando não há progresso durante bb iterações, o fator de iterações, o fator de

diversificação se eleva (diversificação se eleva (bb é o número de heurísticas de baixo é o número de heurísticas de baixo nível).nível).

– Quando há progresso em Quando há progresso em bb iterações seguidas, o fator de iterações seguidas, o fator de diversificação é reduzido.diversificação é reduzido.

Quatro versões simplesQuatro versões simples Também foram desenvolvidas quatro hiper-heurísticas Também foram desenvolvidas quatro hiper-heurísticas

simples, semelhantes a meta-heurísticas de busca por simples, semelhantes a meta-heurísticas de busca por entornos.entornos.

2.2. SimpleRandomSimpleRandom : seleciona uma heurística : seleciona uma heurística aleatoriamente e a aplica à solução corrente.aleatoriamente e a aplica à solução corrente.

3.3. RandomDescentRandomDescent : seleciona uma heurística : seleciona uma heurística aleatoriamente e a aplica repetidamente até que não aleatoriamente e a aplica repetidamente até que não haja ganho de qualidade.haja ganho de qualidade.

4.4. RandomPermRandomPerm : cria aleatoriamente uma permutação : cria aleatoriamente uma permutação das heurísticas e a aplica.das heurísticas e a aplica.

5.5. RandomPermDescentRandomPermDescent : semelhante ao método acima, : semelhante ao método acima, mas cada heurística é aplicada, repetidamente, até que mas cada heurística é aplicada, repetidamente, até que não haja ganho de qualidade.não haja ganho de qualidade.

Aplicação a um problemaAplicação a um problema Problema real: feira comercial.Problema real: feira comercial. Companhia promove um evento que envolve Companhia promove um evento que envolve fornecedoresfornecedores e e

delegadosdelegados.. Fornecedores indicam os delegados que desejam encontrar, Fornecedores indicam os delegados que desejam encontrar,

classificando alguns encontros como classificando alguns encontros como prioritáriosprioritários.. Delegados também participam de Delegados também participam de semináriosseminários. Cada delegado indica . Cada delegado indica

os seminários de que gostaria de participar. Todas as participações os seminários de que gostaria de participar. Todas as participações são garantidas, para os delegados convidados.são garantidas, para os delegados convidados.

Cada encontro ocupa um horário na grade.Cada encontro ocupa um horário na grade. Cada seminário ocupa três horários.Cada seminário ocupa três horários. O objetivo é selecionar quais delegados serão convidados e agendar O objetivo é selecionar quais delegados serão convidados e agendar

encontros.encontros.

Feira comercialFeira comercial Um delegado não pode participar de mais de 12 Um delegado não pode participar de mais de 12

encontros.encontros. Um delegado não pode participar de duas atividades Um delegado não pode participar de duas atividades

(seminário ou encontro) ao mesmo tempo e um (seminário ou encontro) ao mesmo tempo e um fornecedor não pode participar de dois encontros ao fornecedor não pode participar de dois encontros ao mesmo tempo.mesmo tempo.

Restrições desejáveis (Restrições desejáveis (soft constraintssoft constraints):):– Cada fornecedor deve ter ao menos 20 encontros.Cada fornecedor deve ter ao menos 20 encontros.– Cada fornecedor deve ter ao menos 17 encontros prioritários.Cada fornecedor deve ter ao menos 17 encontros prioritários.

Função a ser minimizada: Função a ser minimizada: E = B + 0,05∙C + 8∙HE = B + 0,05∙C + 8∙H..– CC : penalidades pela não realização dos 20 encontros. : penalidades pela não realização dos 20 encontros.– BB : idem, para os encontros prioritários. : idem, para os encontros prioritários.– H = d - 72H = d - 72, onde , onde dd é o número de delegados convidados e 72 é é o número de delegados convidados e 72 é

um limite inferior (se cada fornecedor tem 20 encontros).um limite inferior (se cada fornecedor tem 20 encontros).

ResoluçãoResolução

Apenas a versão 3 da hiper-heurística foi Apenas a versão 3 da hiper-heurística foi utilizada.utilizada.

Solução inicial para a hiper-heurística: resultado Solução inicial para a hiper-heurística: resultado de um algoritmo guloso desenvolvido pelos de um algoritmo guloso desenvolvido pelos autores.autores.

Componentes da função objetivo: Componentes da função objetivo: (1, B)(1, B), , (0,05, (0,05, C)C), , (8, H)(8, H)..

10 heurísticas de baixo nível, que adicionam 10 heurísticas de baixo nível, que adicionam e/ou removem encontros ou delegados.e/ou removem encontros ou delegados.

ExperimentosExperimentos

Deixam a desejar:Deixam a desejar:– Não comparam as hiper-heurísticas com Não comparam as hiper-heurísticas com

outros métodos.outros métodos.– A instância é um caso real, mas foi a única A instância é um caso real, mas foi a única

utilizada. Dados:utilizada. Dados: 43 fornecedores.43 fornecedores. 99 potenciais delegados.99 potenciais delegados. 12 seminários.12 seminários. 24 horários disponíveis.24 horários disponíveis.

ResultadosResultados

Outro problemaOutro problema

Problema real: agendamento de Problema real: agendamento de apresentações de projetos em um apresentações de projetos em um curso de graduação.curso de graduação.

Apenas uma instância.Apenas uma instância. As três versões da hiper-heurística foram As três versões da hiper-heurística foram

utilizadas.utilizadas. 8 heurísticas de baixo nível.8 heurísticas de baixo nível.

Principais referências (meta-Principais referências (meta-heurísticas)heurísticas)

1.1. MELIÁN, B. et al. Metaheuristics: A Global View. In MELIÁN, B. et al. Metaheuristics: A Global View. In Revista Iberoamericana de Inteligencia ArtificialRevista Iberoamericana de Inteligencia Artificial . . Asociación Española de Inteligencia Artificial, 2003. v. 2, Asociación Española de Inteligencia Artificial, 2003. v. 2, n. 19.n. 19.

2.2. REEVES, C. R. Genetic Algorithms. In GLOVER, F., REEVES, C. R. Genetic Algorithms. In GLOVER, F., KOCHENBERGER, G. KOCHENBERGER, G. Handbook of MetaheuristicsHandbook of Metaheuristics. . Kluwer, 2003. Cap. 3.Kluwer, 2003. Cap. 3.

3.3. POMEROY, P. POMEROY, P. An Introduction to Particle Swarm An Introduction to Particle Swarm OptimizationOptimization. 2003. (. 2003. (http:http://www.adaptiveview.com/articles/ipsop1.html//www.adaptiveview.com/articles/ipsop1.html))

4.4. Metaheuristics NetworkMetaheuristics Network. (. (http:http://www.metaheuristics.ne//www.metaheuristics.nett))

Principais referências (hiper-Principais referências (hiper-heurísticas)heurísticas)

1.1. ROSS, P. et al. Hyper-heuristics: An Emerging Direction ROSS, P. et al. Hyper-heuristics: An Emerging Direction in Modern Search Technology. In in Modern Search Technology. In Handbook of Handbook of MetaheuristicsMetaheuristics. Kluwer, 2003.. Kluwer, 2003.

2.2. COWLING, P. et al. COWLING, P. et al. An Adaptive Length Chromosome An Adaptive Length Chromosome Hyperheuristic Genetic Algorithm for a Trainer Hyperheuristic Genetic Algorithm for a Trainer Scheduling ProblemScheduling Problem. Submitted to SEAL 2002 . Submitted to SEAL 2002 Conference). University of Nottingham.Conference). University of Nottingham.

3.3. COWLING, P. et al. Hyperheuristics: A Tool for Rapid COWLING, P. et al. Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimization. In Prototyping in Scheduling and Optimization. In LNCS LNCS 2279, Applications of Evolutionary Computing: 2279, Applications of Evolutionary Computing: Proceedings of Evo Workshops 2002Proceedings of Evo Workshops 2002..

Meta-referência:Meta-referência:

http://www.ime.usp.http://www.ime.usp.br/~igorrs/seminarios/metahiperbr/~igorrs/seminarios/metahiper..pptppt

Mais referências na minha monografia:Mais referências na minha monografia:

http://www.ime.usp.http://www.ime.usp.br/~igorrs/monografias/metahiperbr/~igorrs/monografias/metahiper..pdfpdf