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.
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-devO 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.shTenha 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 buildCompila e instala os binários executáveis e das bibliotecas
make installProjeto compilado! :)
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
imageevolumenã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 volumeO 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 300Para ver as opção use python scrpits/experiment.py --help
This work is licensed under CC BY-NC-SA © Ronaldd Pinho