Crossovers Operators Comparisons

Este projeto é resultado da pesquisa conduzida no
Laboratory of Applied Artificial Intelligence (LAAI)
acerca de operadores de cruzamento em algoritmos genéticos (AG) aplicados a
alguns problemas NP-Completos de Karp, problemas clássicos de otimização
combinatória em ciência da computação e pesquisa operacional. O trabalho visa
conhecer mais sobre o efeito dos operadores de crossover mais usados no processo
de busca de um AG no tipo de problema abordado (otimização combinatória).

Os estudos foram executados para os seguintes problemas:

Árvore de Steiner
Clique Máximo
Mochila Multidimensional
Cobertura de Conjuntos

Os quatro problemas foram implementados e executados usando arquivos de
instâncias obtidas principalmente das bases de dados da
OR-Library
e do DIMACS.

Sumário

Instalando dependências externas
- Instalando o ParadisEO
Compilando o projeto
Imagem Docker

Instalação de dependências externas

Arch Linux:

sudo pacman -Sy --ignore cmake docker doxygen boost boost-libs vsqlite++

Debian:

sudo apt-get update
sudo apt-get install cmake docker doxygen libboost-graph-dev libvsqlitepp-dev

Instalando o ParadisEO

O ParadisEO é umm framework C++ para computação evolutiva, para que o projeto
seja compilado com sucesso é necessário a instalação do framework e no geral
ele não está presente de forma padrão nos repositórios de gerenciadores de
pacotes das distribuições Linux. Portanto é recomendado fazer a instalação a
partir do código fonte.

Um script é fornecido para automatizar o download e instalação da biblioteca no
sistema no Linux:

bash install-paradiseo.sh

Compilando o projeto

Tenha certeza de ter o cmake instalado na versão 3.6+. Use o comando
cmake --version para verificar.

Compilação do projeto inteiro

cmake -B build . && make -C build

Compila e instala os binários executáveis e das bibliotecas

make install

Projeto compilado! :)

Imagem Docker

OBS: Necessário ter o Docker instalado e 5GB de espaço em disco para
construir a imagem Docker.

Alvos para artefatos docker são configurados para fazer build da imagem docker
e criar o volume.

A aplicação fornece um Dockerfile para construção de uma imagem docker para
execução do algoritmo. O docker permite manipular e limitar recursos de hardware
para os contêineres.

Se o Docker estiver instalado no computador o comando CMake irá criar os seguintes
alvos para a build da imagem e do volume Docker: image e volume.

OBS: Requer o Docker instalado.

Se o Docker não for encontrado na máquina os alvos image e volume não serão
configurados, logo, os comandos abaixo não funcionarão.

# use "-C build" se no diretório raíz do projeto
sudo make image 
sudo make volume

Script experiment.py

O script scripts/experiment.py foi criado para automatizar a inicialização de
execuções em contêineres Docker. É necessário que a imagem crossoverstudy e o
volume studyvol tenham sido construídos seguindo os passos da
seção anterior.

O script usa um arquivo de configuração em formato YAML (config.yml) para
definir os argumentos para o comando a ser executado no contêiner. A configuração
permite que se possa passar uma lista de argumentos para uma mesma opção no
arquivo, o script se certificará de criar vários comandos combinando cada
argumento de listas com os argumentos das outras opções criando assim um conjunto
de várias combinações de parâmetros, sendo cada uma executada em um contêiner
diferente.

A opção -n define quantas vezes um comando deve ser executado dentro de um
contêiner. Isso é usado para fazer as várias execuções do algoritmo com uma mesma
configuração de parâmetros.

Com a opção --max-con o script define um número de contêineres máximo a serem
executados ao mesmo tempo, quando o número total de contêineres escalonados é
maior que o valor dessa opção o script espera até que algum contêiner rodando
termine de executar para então subir um novo. O valor padrão dessa opção é 2.

A opção --waittime ou -t do script define a quantidade de segundos o script
espera para verificar se há disponibilidade de executar um novo contêiner dado o
número máximo de contêineres permitido.

Uma dica como usar o script:

sudo python scripts/experiment.py "setcovering" -n 50 --waittime 300

Para ver as opção use python scrpits/experiment.py --help