Introdução ao Drools Planner

O Drools Planner é um framework Java para resolução de problemas de planejamento através de meta-heurísticas, voltado especialmente para problemas de grande porte e alta complexidade (um número grande de restrições), que inviabilizam uma abordagem exata.

Além de prover um framework que fatora partes comuns a essas meta-heurísticas, o que permite reuso de código, o grande atrativo do Drools Planner é sua integração com o sistema de regras do Drools, o Drools Expert, que permite incluir restrições através de uma linguagem de alto nível.

O Drools Planner também provê uma ferramenta de benchmark, possibilitando a comparação, através de gráficos, entre os diversos algoritmos implementados com parâmetros diferentes, de modo a se escolher aquele que mais se adequa ao problema em questão.

Atualmente o Drools Planner implementa apenas algoritmos de busca local, entre eles: busca tabu, simulated annealing e great deluge.

Nota: A versão do Drools descrita nesse post é a 5.3.0 Final. Vale ainda ressaltar que como o Drools Planner em particular está em um estágio inicial, a API ainda está mudando bastante. Portanto, parte do que está escrito aqui pode não fazer sentido para versões anteriores.

Conceitos Básicos

Vamos discutir agora as principais características do Drools Planner.

Interfaces a serem implementadas

Solução. A solução de um problema é uma classe que representa as possíveis soluções do problema e deve implementar a interface Solution. Nessa classe geralmente incluímos referências a todas as informações que podem ser utilizadas pelo algoritmo.

Vizinhos. Para implementar uma busca local precisamos gerar soluções vizinhas a partir de uma dada solução. Cada tipo de movimento para gerar uma solução vizinha deve implementar a interface Move.

Vizinhança. No Drools Planner existe o conceito de fábrica de movimentos que, dada uma solução S, gera um conjunto de Moves, que estarão disponíveis para o algoritmo utilizar. Uma fábrica de movimentos deve implementar a interface MoveFactory.

Avaliação de uma solução com Drools Expert

A grande sacada do Drools Planner é usar o Drools Expert para associar um valor numérico a uma solução. Basicamente, o Drools Expert é uma linguagem de programação baseada em regras. Existe o conceito de working memory, onde diversos objetos, denominados fatos, estão inseridos. Num arquivo .drl, definimos as regras.

Uma regra utiliza a seguinte sintaxe:

rule "Nome da regra"
when
    // Conjunto de condicionais
then
    // Ação a ser tomada (sintaxe Java)
end

Quando um dado conjunto de fatos passa a satisfazer as condições da regra, a ação definida é executada. A vantagem é que em geral restrições são bem fáceis de serem modeladas com regras.

A ideia é escrever um regra que seja satisfeita quando uma restrição é violada. A ação a ser tomada é basicamente somar uma pontuação proporcional à importância dessa restrição. O algoritmo tratará de minimizar essa pontuação através da busca local.

Entidades de Planejamento

No Drools 5.3.0 foram introduzidos conceitos como Planning facts, entities, variables e value range.

Planning fact. É uma classe de fatos que são usados para calcular a pontuação, mas não são modificados ao longo do algoritmo.

Planning entity. É uma classe de fatos que são usados para calcular a pontuação, mas podem ser modificados pelo algoritmo. Essa classe deve ser anotada com @ PlanningEntity.

Planning Variable. São os membros de uma planning entity que podem ser modificados pelo algoritmo. Os getters desses membros devem ser anotados com @PlanningVariable.

Planning Value Range. São os possíveis valores que uma dada planning variable pode assumir. Geralmente esses valores são os elementos de uma lista na classe representando uma solução e nesse caso o getter dessa planning variable também deve conter a anotação @ValueRangeFromSolutionProperty.

Mais informações no manual.

Heurísticas Construtivas

A definição das entidades de planejamento (planning entities) permitem automatizar a geração de uma solução inicial através de heurísticas construtivas padrões como First Fit e Best Fit.

É possível definir sua própria heurística para construir a solução inicial. Para isso, basta o algoritmo implementar a interface CustomSolverPhaseCommand.

Arquivo de Configuração

Um outro item essencial do Drools Planner é o arquivo de configuração. Esse arquivo é no formato XML e define diversas características do algoritmo. Vamos destacar algumas delas.

Estrutura básica do arquivo de configuração

Ambiente de execução

A propriedade environmentMode define o ambiente de execução em que o algoritmo executará. Isso afeta o nível das mensagens de log e a checagem ou não de assertivas. Alguns valores mais comuns dessa propriedade são: DEBUG, REPRODUCIBLE e PRODUCTION.

Para mais informações, consulte o manual.

Classes da solução e da entidade de planejamento

É preciso informar qual classe implementa a solução do problema e qual representa a entidade de planejamento através das propriedades solutionClass e planningEntityClass, respectivamente.

Arquivo de regras

Através da propriedade scoreDrl, informamos o caminho para o arquivo de regras do Drools Expert.

Definição do tipo de pontuação

É possível trabalhar com diferentes tipos de pontuação especificando a propriedade scoreDefinition. As principais são SIMPLE e HARD_AND_SOFT. O primeiro é simplesmente um inteiro e o segundo um par de inteiros, sendo que um representa a parte “hard” e a outra “soft”. Uma pontuação “hard” não nula representa uma solução inviável e portanto tem peso infinitamente maior do que a pontuação “soft”.

A ideia de ter uma pontuação “hard” é permitir que o algoritmo trabalhe com soluções inviáveis e dessa forma conseguir escapar de ótimos locais no espaço de soluções viáveis.

Critério de Parada

A propriedade termination define as condições de parada do algoritmo, como por exemplo tempo de execução, número de iterações sem melhoria da solução, valor de solução alcançado, etc. Para mais detalhes, consulte o manual.

Escolha da heurística construtiva

Através da propriedade constructionHeuristic podemos definir as heurísticas usadas para a construção da solução inicial. Como dito anteriormente, algumas delas são FIRST_FIT e BEST_FIT. Mais informações no manual.

Se você optou por implementar sua própria heurística, a propriedade customSolverPhase deve ser utilizada. Mais detalhes no manual.

Configuração da Busca Local

Há três propriedades principais que precisamos para configurar a busca local: selector, acceptor e forager.

Selector. Define quais fábricas de movimentos serão utilizadas

Acceptor. Define qual algoritmo utilizar, bem como possíveis parâmetros do algoritmo escolhido. Por exemplo, o seguinte trecho de configuração:

<acceptor>
  <completeSolutionTabuSize>
    100
  </completeSolutionTabuSize>
</acceptor>

especifica que usaremos uma busca tabu que possui um conjunto de soluções tabu de tamanho 100 (ou seja, guarda as últimas 100 soluções encontradas e não deixa o algoritmo voltar nelas).

Forager. Especifica a escolha do movimento. As fábricas de movimentos gerarão muitos movimentos a partir da solução corrente. A propriedade minimalAcceptedSelection define que apenas um subconjunto desses movimentos sejam analisados para melhorar a eficiência.

Já a propriedade pickEarlyType permite parar de analisar os vizinhos assim que encontrar um satisfazendo alguma condição (como por exemplo algum que tenha pontuação melhor que a solução corrente).

Para mais detalhes sobre essas três propriedades, consulte no manual.

Conclusão

Pelo que estudei do Drools Planner até agora, consigo ver as seguintes vantagens:

* Parte comum das meta-heurísticas já está implementada
* Sistema de regras é escalável
* Fácil adicionar novas restrições se não precisar mudar as entidades

Já as desvantagens:

* Debugar código Drools é mais difícil do que debugar código Java (principalmente a parte do “when“)
* Paradigma diferente (programação declarativa)

Os comentários estão fechados.

%d bloggers like this: