Como escolher o algoritmo mais eficiente com OptaPlanner – Parte 2

Artigo no estilo: Curso

A primeira parte do artigo introduziu ao leitor o universo dos problemas de planejamento e mostrou o quão difícil é resolvê-los. Vimos que mesmo problemas de dimensões pequenas podem gerar uma quantidade gigantesca de combinações possíveis, tornando-se inviável ou impossível testar todas as possibilidades até encontrar a solução ótima.

Nesse contexto, o OptaPlanner foi apresentado como uma alternativa aos métodos de busca exaustiva para resolver problemas de planejamento (como o bin packing). O OptaPlanner reúne um conjunto de algoritmos de otimização (heurísticas e meta-heurísticas) que são empregados para percorrer de forma eficiente o altíssimo número de soluções possíveis e retornar um resultado bom em tempo viável.

Para explorar suas funcionalidades e comprovar sua eficiência, demos início na primeira parte do artigo à implementação de um exemplo de código que utiliza o OptaPlanner para resolver um problema de planejamento baseado em um cenário do mundo real. O cenário descreve um problema enfrentado por uma empresa de turismo para alocar eficientemente seus passageiros em sua frota de veículos.

Até o momento passamos pela definição das classes do modelo de domínio, identificamos as restrições de negócio e implementamos as regras para cálculo do score utilizando o Drools.

Nesta segunda parte, daremos continuidade ao exemplo e finalmente veremos o OptaPlanner em funcionamento. Além disso, o artigo abordará conceitualmente alguns dos algoritmos de otimização implementados na solução da Red Hat e mostrará como utilizar a ferramenta de benchmarking para comparar diferentes algoritmos/configurações e escolher o mais eficiente para o nosso caso de uso.

Configuração do solver

Dando continuidade à implementação do exemplo, iremos agora configurar o componente de mais alto nível da API do OptaPlanner, com o qual aplicações interagem para resolver problemas de planejamento: o solver.

A configuração do solver pode ser feita de duas maneiras: estática (via arquivo XML) ou dinâmica (via API Java). A segunda opção é muito útil quando alguns dos parâmetros de configuração (como tempo máximo de execução, etc.) puderem ser informados dinamicamente por usuários ou aplicações clientes.

Em nosso exemplo, utilizaremos a opção de configuração via arquivo XML, uma vez que todos os parâmetros serão pré-definidos. Sendo assim, crie um novo arquivo na pasta src/main/resources/solver do projeto chamado solverConfig.xml. A Listagem 1 mostra o código completo do arquivo.

O conteúdo do arquivo de configuração do solver está dividido em três partes (observe os comentários deixados na listagem): modelo de domínio, score e algoritmos de otimização.

Na parte referente ao modelo de domínio, temos de informar o nome qualificado das classes planning entity e planning solution do problema.

No segundo bloco de elementos, definimos alguns aspectos referentes ao cálculo do score, como o tipo de score sendo usado e o caminho para o arquivo de regras do Drools no classpath da aplicação. Se o leitor optar por não escrever as regras no Drools, mas sim por utilizar uma das implementações em Java, informe o nome qualificado da classe através dos elementos <easyScoreCalculatorClass> ou <incrementalScoreCalculatorClass> (dependendo de qual das duas interfaces decidir implementar).

O último elemento do bloco, <initializingScoreTrend>, especifica como o score evolui à medida que as planning variables do problema vão sendo inicializadas com os pl ...