Red Hat: Resolvendo problemas de planejamento com OptaPlanner – Parte 1
Artigo no estilo: Curso
O OptaPlanner é um framework que auxilia na resolução de problemas de planejamento. Ele reúne um conjunto de heurísticas e meta-heurísticas que podem ser aplicadas para encontrar, de forma eficiente, a melhor solução para um problema dentro de um período de tempo aceitável.
Nesta segunda e última parte do artigo daremos continuidade à implementação do exemplo que tem como objetivo resolver um caso de uso de uma empresa de turismo.
Conheceremos o funcionamento de alguns dos algoritmos de otimização implementados no OptaPlanner e como utilizar a ferramenta de benchmarking para escolher a configuração mais eficiente para cada caso de uso.
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 ...
Confira outros conteúdos:
Perguntas frequentes
Nossos casos de sucesso
Eu sabia pouquíssimas coisas de programação antes de começar a estudar com vocês, fui me especializando em várias áreas e ferramentas que tinham na plataforma, e com essa bagagem consegui um estágio logo no início do meu primeiro período na faculdade.
Estudo aqui na Dev desde o meio do ano passado!
Nesse período a Dev me ajudou a crescer muito aqui no trampo.
Fui o primeiro desenvolvedor contratado pela minha
empresa. Hoje eu lidero um time de desenvolvimento!
Minha meta é continuar estudando e praticando para ser um
Full-Stack Dev!
Economizei 3 meses para assinar a plataforma e sendo sincero valeu muito a pena, pois a plataforma é bem intuitiva e muuuuito didática a metodologia de ensino. Sinto que estou EVOLUINDO a cada dia. Muito obrigado!
Nossa! Plataforma maravilhosa. To amando o curso de desenvolvimento front-end, tinha coisas que eu ainda não tinha visto. A didática é do jeito que qualquer pessoa consegue aprender. Sério, to apaixonado, adorando demais.
Adquiri o curso de vocês e logo percebi que são os melhores do Brasil. É um passo a passo incrível. Só não aprende quem não quer. Foi o melhor investimento da minha vida!
Foi um dos melhores investimentos que já fiz na vida e tenho aprendido bastante com a plataforma. Vocês estão fazendo parte da minha jornada nesse mundo da programação, irei assinar meu contrato como programador graças a plataforma.
Wanderson Oliveira
Comprei a assinatura tem uma semana, aprendi mais do que 4 meses estudando outros cursos. Exercícios práticos que não tem como não aprender, estão de parabéns!
Obrigado DevMedia, nunca presenciei uma plataforma de ensino tão presente na vida acadêmica de seus alunos, parabéns!
Eduardo Dorneles
Aprendi React na plataforma da DevMedia há cerca de 1 ano e meio... Hoje estou há 1 ano empregado trabalhando 100% com React!
Adauto Junior
Já fiz alguns cursos na área e nenhum é tão bom quanto o de vocês. Estou aprendendo muito, muito obrigado por existirem. Estão de parabéns... Espero um dia conseguir um emprego na área.
Utilizamos cookies para fornecer uma melhor experiência para nossos usuários, consulte nossa política de privacidade.