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 planning values. Essa informação é útil para que alguns tipos de algoritmos possam ser mais performáticos. Como todas as restrições do nosso problema de planejamento (e da maioria dos casos de uso) são negativas, então o valor correto a ser informado é ONLY_DOWN.

A terceira e última parte é certamente a mais importante do arquivo, pois refere-se à configuração dos algoritmos de otimização.

Neste momento, no entanto, não vamos nos preocupar com otimização, mas sim em conseguirmos executar nosso exemplo o quanto antes e da forma mais simples possível. Por essa razão, vamos utilizar um algoritmo de busca exaustiva, o Brute Force.

Ao fazermos isso, não teremos muito ganho ao utilizar o OptaPlanner. No entanto, conseguiremos ver nosso exemplo funcionando e atingindo um resultado previsível. Ao usar o algoritmo de força bruta, o leitor também vai poder observar a degradação do tempo de resposta se adicionar novos valores ao problema (não deixe de fazer esse teste!). Mas não se preocupe, pois na sequência veremos como selecionar outros algoritmos para tornar nosso exemplo mais eficiente.

Listagem 1. Arquivo de configuração do solver (solverConfig.xml).

  <?xml version="1.0" encoding="UTF-8"?>
  <solver>
      <!-- Modelo de domínio -->
      <solutionClass>br.com.devmedia.agenciaturismo.planejamento.AlocacaoPassageiros</solutionClass>
      <entityClass>br.com.devmedia.agenciaturismo.dominio.Grupo</entityClass>
  
      <!-- Score -->
      <scoreDirectorFactory>
          <scoreDefinitionType>HARD_MEDIUM_SOFT</scoreDefinitionType>
          <scoreDrl>solver/alocacaoPassageirosScoreRules.drl</scoreDrl>
          <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
      </scoreDirectorFactory>
   
      <!-- Algoritmos de otimização -->
      <exhaustiveSearch>
          <exhaustiveSearchType>BRUTE_FORCE</exhaustiveSearchType>
      </exhaustiveSearch>
  </solver>

Executando a aplicação

Neste momento já temos quase tudo preparado para resolver o ...