Busca Local para o PQA-MO

Pseudo-código da busca

Um pseudo-código da busca segue abaixo. Uma observação importante é que, o fato de "adicionar" uma solução ao conjunto Pareto não significa que ele ficará pertencendo ao conjunto. O conjunto Pareto tem uma propriedade de manter sempre somente as soluções não-dominadas, o que quer dizer que, se tentarmos inserir uma solução que seja dominada por uma solução que já está no conjunto, ela não será inserida. Da mesma maneira, se inserirmos uma solução que domine soluções que estão no conjunto, as soluções dominadas serão automaticamente removidas.

ParetoHybridSearch
Entrada: A solução inicial da busca (S) e o número de iterações da busca (Profundidade)
Saída: retorna um conjunto Pareto com todas as soluções não-dominadas encontradas durante a busca

  1. Inicializar 3 conjuntos Pareto, atual, vizinho e final
  2. Coloca a solução S em atual
  3. Fazer, um número Profundidade de vezes:
    1. Para cada solução sol em atual, faça:
      1. Colocar todos os vizinhos de sol no conjunto Pareto vizinho
    2. Limpar o conjunto atual
    3. Calcular o valor do incremento da escalarização, $incr = \frac{1}{|vizinho|}$
    4. $\lambda = \{0,1\}$
    5. Para cada solução sol pertencente a vizinho, faça:
      1. Adicionar ao conjunto atual o resultado de BuscaLocalEscalarizada(sol,lambda)
      2. $\lambda = \lambda + \{ incr, -incr \}$
    6. Adicionar todas as soluções de atual a final
  4. Retornar o conjunto final

Estrutura geral do texto

  1. Introdução
    • Resumo geral
    • Justificativa da importância
    • Roteiro do restante do trabalho
  2. Otimização combinatória multi-objetivo
    • Falar um pouco sobre otimização combinatória mono-objetivo
    • O que é, problemas famosos, tecnicas heurísticas, buscas locais
    • Comparação de algoritmos multi-objetivo
      • Indicadores (unários, binários, pareto/não)
      • Funções de conquista
  3. O problema quadrático de alocação multi-objetivo
    • PQA mono-objetivo, definição, exemplos, porque é um problema interessante
    • Revisão de literatura do problema
      • Stutzle/Paquete (x 2)
      • Knowles/Corne (x 2)
      • Day/Lamont
      • Falar das instâncias
    • Buscas locais existentes
      • RoTS, II, PLS, TPLS, D-TPLS, PD-TPLS
      • Adaptação da busca PD-TPLS para >= 3 objetivos
  4. Uma nova busca local para o PQA-MO: Pareto Hybrid Search
    • Estratégias de archiving (PAES), pseudo-código, exemplo, variação RoTS/II
  5. Resultados computacionais
    • Instâncias, experimentos, tabelas, gráficos
  6. Conclusões

Resultados

  1. Dominance Rank
  2. Indicador Epsilon
  3. Indicador Hypervolume
  4. Indicador R2
  5. Funções de conquista

Gráficos dos tempos de execução

tempos.real.2.png

Instâncias estruturadas (reais), com 2 objetivos. Embaixo, temos, em ordem, as instâncias de tamanho 25 (da correção 0.75 até a correlação -0.75), as instâncias de tamanho 50 (da correção 0.75 até a correlação -0.75) e as instâncias de tamanho 75 (da correlação 0.75 até a correlação -0.75).

tempos.uniform.2.png

Instâncias não-estruturadas (aleatórias uniformes), com 2 objetivos. Embaixo, temos, em ordem, as instâncias de tamanho 25 (da correção 0.75 até a correlação -0.75), as instâncias de tamanho 50 (da correção 0.75 até a correlação -0.75) e as instâncias de tamanho 75 (da correlação 0.75 até a correlação -0.75).

Alguns conjuntos paretos encontrados pelos algoritmos

real.2obj.25.n75.png
real.2obj.50.p50.png
real.2obj.75.0.png
uniform.2obj.25.n25.png
uniform.2obj.50.p50.png
uniform.2obj.75.n50.png
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.