Workshop Prático de Afinação de Algoritmos - LAE 2015.1

Informações gerais

Meta-heurísticas são ferramentas poderosas para a solução de problemas de otimização, mas a eficiência desse tipo de algoritmo está diretamente ligada à correta afinação de seus parâmetros. O esforço computacional necessário para realizar esta tarefa, no entanto, tem levado pesquisadores a desenvolver ferramentas heurísticas de afinação, reduzindo consideravelmente o número de experimentos necessários para obter-se uma configuração eficiente. Dentre os diversos afinadores existentes, neste workshop detalharemos o Iterated F-Race (irace). Na primeira parte, serão utilizados exemplos práticos para explicar o funcionamento dessa ferramenta. Na segunda parte, os participantes que apresentarem casos de uso poderão testar o irace diretamente nos seus algoritmos.

O workshop seguirá o seguinte cronograma:

Cronograma

09:00 - 09:20 Introdução à afinação automática de algoritmos
09:20 - 09:45 Exemplo #1 - Aprendendo a usar o irace
09:45 - 10:25 Exemplo #2 - Aplicando o irace ao seu problema
10:25 - 10:35 Encerramento

Instalando o irace

Warning Para instalar o irace, é necessário que você tenha o interpretador da linguagem R para computação estatística funcionando.

A instalação do irace é bastante simples. Basta iniciar o interpretador R em um terminal e solicitar a instalação do pacote, disponível através dos servidores CRAN:

     $ R
     > install.packages("irace")

Escolha um servidor próximo e a instalação deve continuar normalmente. Ao final do processo, teste a instalação com 

     > library(irace)

Warning Caso haja algum problema com o download ou a instalação do irace, avise imediatamente.

Uma vez que o irace tenha sido instalado, o último passo é configurar as variáveis de ambiente UNIX para que o seu sistema possa encontrar o wrapper do irace.

Warning O wrapper do irace ativa o interpretador R em modo linha de comando e executa o irace no diretório atual.

A primeira variável de ambiente a ser configurada é a variável IRACE_HOME, que deverá conter o diretório onde o irace foi instalado. Para localizar a instalação do irace, use o comando system.file(package="irace") do R:

    $ R
    > system.file(package="irace")
    > [1] "/diretorio/onde/esta/o/irace"

Uma vez localizada a instalação do R, adicione as linhas abaixo ao arquivo ~/.bash_profile para configurar a variável IRACE_HOME e adicioná-la à variável PATH.

    export IRACE_HOME=/diretorio/onde/esta/o/irace
    export PATH=${IRACE_HOME}/bin/:$PATH

Agora é só carregar as alterações efetuadas, abrindo uma nova aba/janela do terminal ou usando o comando source:

    $ source ~/.bash_profile

Para testar, execute o irace

    $ irace

Exemplo ACOTSP

Info Para baixar o material necessário para executar este exercício, clique aqui.

Após descompactar o arquivo acotsp-example.tar.gz, acesse o diretório ACOTSP-1.04-tuning e compile o ACOTSP usando o comando make:

     $ tar xzvf acotsp-example.tar.gz
     $ cd acotsp-example
     $ cd ACOTSP-1.04-tuning
     $ make

Retorne ao diretório onde o arquivo acotsp-example.tar.gz foi descompactado e execute o irace.

     $ cd ..
     $ irace --parallel 4

Info A opção --parallel faz com que o irace utilize múltiplos processadores. Caso seu computador seja dual core, use --parallel 2.

Acompanhe a execução do irace analisando as configurações selecionadas a cada iteração. Ao término da execução, compare as melhores configurações selecionadas e tente entender sua lógica.

Exemplo NSGA-II

Info Para baixar o material necessário para executar este exercício, clique aqui.

Após descompactar o arquivo nsga2-example.tar.gz, acesse o diretório nsga2-gnuplot-v1.1.6 e compile o NSGA-II usando o comando make:

     $ tar xzvf nsga2-example.tar.gz
     $ cd nsga2-example
     $ cd nsga2-gnuplot-v1.1.6
     $ make

Retorne ao diretório onde o arquivo nsga2-example.tar.gz foi descompactado. Agora será necessário compilar as ferramentas de avaliação multiobjetivo para o cálculo do hipervolume. Primeiro, compile a ferramenta nondominated, usada para normalizar e filtrar conjuntos de aproximação.

     $ cd ..
     $ cd mo-tools-1.0svn100-src
     $ make nondominated march=x86-64

Info A opção march adequa a compilação à sua arquitetura. Se seu computador não for 64-bits, use march=native.

A segunda ferramenta que deve ser compilada é o hipervolume:

     $ cd ..
     $ cd hv-2.0rc1-src
     $ make march=x86-64

Info A opção march adequa a compilação à sua arquitetura. Se seu computador não for 64-bits, use march=native.

Retorne ao diretório onde o arquivo nsga2-example.tar.gz foi descompactado e execute o irace.

     $ cd ..
     $ irace --parallel 4

Info A opção --parallel faz com que o irace utilize múltiplos processadores. Caso seu computador seja dual core, use --parallel 2.

Acompanhe a execução do irace analisando as configurações selecionadas a cada iteração. Ao término da execução, compare as melhores configurações selecionadas e tente entender sua lógica.

Usando um cálculo de hipervolume diferente

Agora que você já testou o irace usando o hipervolume com normalização, o próximo passo é testá-lo sem normalização. Abra o arquivo tune-conf no diretório onde você descompactou o arquivo nsga2-example.tar.gz e edite as duas linhas abaixo:

     #hookRun <- "./hook-run2"		# descomente esta linha
     hookEvaluate <- "./hook-evaluate"  # comente esta linha

Execute o irace novamente e compare os resultados.