Una guida a OptaPlanner

1. Introduzione a OptaPlanner

In questo tutorial, esaminiamo un risolutore di soddisfazione dei vincoli Java chiamato OptaPlanner.

OptaPlanner risolve i problemi di pianificazione utilizzando una suite di algoritmi con una configurazione minima.

Sebbene la comprensione degli algoritmi possa fornire dettagli utili, con il framework che esegue il duro lavoro per noi.

2. Dipendenza da Maven

Innanzitutto, aggiungeremo una dipendenza Maven per OptaPlanner:

 org.optaplanner optaplanner-core 7.9.0.Final  

Individuiamo la versione più recente di OptaPlanner dal repository Maven Central.

3. Classe problema / soluzione

Per risolvere un problema abbiamo sicuramente bisogno di uno specifico come esempio.

L'orario delle lezioni è un esempio adatto a causa della difficoltà di bilanciare risorse come aule, tempo e insegnanti.

3.1. Orario del corso

CourseSchedule contiene una combinazione delle nostre variabili problema ed entità di pianificazione, di conseguenza è la classe della soluzione. Di conseguenza, utilizziamo più annotazioni per configurarlo.

Diamo un'occhiata più da vicino a ciascuno separatamente:

@PlanningSolution public class CourseSchedule { private List roomList; private List periodList; private List lectureList; private HardSoftScore score;

L' annotazione PlanningSolution indica a OptaPlanner che questa classe contiene i dati per comprendere una soluzione.

OptaPlanner si aspetta questi componenti minimi: l'entità di pianificazione, i fatti del problema e un punteggio.

3.2. Conferenza

Lecture, un POJO, assomiglia a:

@PlanningEntity public class Lecture { public Integer roomNumber; public Integer period; public String teacher; @PlanningVariable( valueRangeProviderRefs = {"availablePeriods"}) public Integer getPeriod() { return period; } @PlanningVariable( valueRangeProviderRefs = {"availableRooms"}) public Integer getRoomNumber() { return roomNumber; } }

Usiamo la classe Lecture come entità di pianificazione, quindi aggiungiamo un'altra annotazione sul getter in CourseSchedule :

@PlanningEntityCollectionProperty public List getLectureList() { return lectureList; }

La nostra entità di pianificazione contiene i vincoli che vengono impostati.

L' annotazione PlanningVariable e le annotazioni valueRangeProviderRef collegano i vincoli ai fatti del problema.

Questi valori di vincolo verranno valutati successivamente in tutte le entità di pianificazione.

3.3. Fatti problematici

Le variabili roomNumber e period agiscono come vincoli in modo simile tra loro.

OptaPlanner assegna un punteggio alle soluzioni in base alla logica che utilizza queste variabili. Aggiungiamo annotazioni a entrambi i metodi getter :

@ValueRangeProvider(id = "availableRooms") @ProblemFactCollectionProperty public List getRoomList() { return roomList; } @ValueRangeProvider(id = "availablePeriods") @ProblemFactCollectionProperty public List getPeriodList() { return periodList; } 

Questi elenchi sono tutti i possibili valori utilizzati nei campi Lecture .

OptaPlanner li popola in tutte le soluzioni nello spazio di ricerca.

Infine, imposta quindi un punteggio per ciascuna delle soluzioni, quindi abbiamo bisogno di un campo per memorizzare il punteggio:

@PlanningScore public HardSoftScore getScore() { return score; }

Senza un punteggio, OptaPlanner non riesce a trovare la soluzione ottimale da qui l'importanza sottolineata in precedenza.

4. Punteggio

A differenza di quanto visto finora, la classe di punteggio richiede più codice personalizzato.

Questo perché il calcolatore del punteggio è specifico del problema e del modello di dominio.

4.1. Java personalizzato

Usiamo un semplice calcolo del punteggio per risolvere questo problema (anche se potrebbe non sembrare):

public class ScoreCalculator implements EasyScoreCalculator { @Override public Score calculateScore(CourseSchedule courseSchedule) { int hardScore = 0; int softScore = 0; Set occupiedRooms = new HashSet(); for(Lecture lecture : courseSchedule.getLectureList()) { String roomInUse = lecture.getPeriod() .toString() + ":" + lecture.getRoomNumber().toString(); if(occupiedRooms.contains(roomInUse)){ hardScore += -1; } else { occupiedRooms.add(roomInUse); } } return HardSoftScore.valueOf(hardScore, softScore); } }

Se diamo uno sguardo più da vicino al codice sopra, le parti importanti diventano più chiare. Calcoliamo un punteggio nel ciclo perché l' elenco contiene combinazioni specifiche non univoche di stanze e periodi.

L' HashSet viene utilizzato per salvare una chiave univoca (stringa) in modo da poter penalizzare le lezioni duplicate nella stessa stanza e nello stesso periodo.

Di conseguenza, riceviamo set unici di stanze e periodi.

4.2. Sbava

I file Drools ci offrono un modo rapido per modificare le regole per l'applicazione ai file. Sebbene la sintassi a volte possa creare confusione, il file Drools può essere un modo per gestire la logica al di fuori delle classi compilate.

La nostra regola per evitare voci nulle è simile a questa:

global HardSoftScoreHolder scoreHolder; rule "noNullRoomPeriod" when Lecture( roomNumber == null ); Lecture( period == null ); then scoreHolder.addHardConstraintMatch(kcontext, -1); end

5. Configurazione del risolutore

Un altro file di configurazione necessario, abbiamo bisogno di un file XML per configurare il risolutore.

5.1. File di configurazione XML

    org.baeldung.optaplanner.ScoreCalculator    10   

A causa delle nostre annotazioni nella classe CourseSchedule , qui utilizziamo l' elemento scanAnnotatedClasses per analizzare i file sul classpath.

Il contenuto dell'elemento scoreDirectorFactory imposta la nostra classe ScoreCalculator per contenere la nostra logica di punteggio.

Quando vogliamo utilizzare un file Drools, sostituiamo il contenuto dell'elemento con:

courseScheduleScoreRules.drl

Our final setting is the termination element. Rather than search endlessly for an optimized solution that may never exist, this setting will stop the search after a time limit.

Ten seconds is more than enough for most problems.

6. Testing

We configured our solution, solver and problem classes. Let's test it!

6.1. Setting up Our Test

First, we do some setup:

SolverFactory solverFactory = SolverFactory .createFromXmlResource("courseScheduleSolverConfiguration.xml"); solver = solverFactory.buildSolver(); unsolvedCourseSchedule = new CourseSchedule();

Second, we populate data into the planning entity collection and problem fact List objects.

6.2. Test Execution and Verification

Finally, we test it by calling solve.

CourseSchedule solvedCourseSchedule = solver.solve(unsolvedCourseSchedule); assertNotNull(solvedCourseSchedule.getScore()); assertEquals(-4, solvedCourseSchedule.getScore().getHardScore());

We check that the solvedCourseSchedule has a score which tells us that we have the “optimal” solution.

For a bonus, we create a print method that will display our optimized solution:

public void printCourseSchedule() { lectureList.stream() .map(c -> "Lecture in Room " + c.getRoomNumber().toString() + " during Period " + c.getPeriod().toString()) .forEach(k -> logger.info(k)); }

This method displays:

Lecture in Room 1 during Period 1 Lecture in Room 2 during Period 1 Lecture in Room 1 during Period 2 Lecture in Room 2 during Period 2 Lecture in Room 1 during Period 3 Lecture in Room 2 during Period 3 Lecture in Room 1 during Period 1 Lecture in Room 1 during Period 1 Lecture in Room 1 during Period 1 Lecture in Room 1 during Period 1

Notice how the last three entries are repeating. This happens because there is no optimal solution to our problem. We chose three periods, two classrooms and ten lectures.

There are only six possible lectures due to these fixed resources. At the very least this answer shows the user that there are not enough rooms or periods to contain all the lectures.

7. Extra Features

Our example for OptaPlanner we created was a simple one, however, the framework has added features for more diverse use cases. We may want to implement or alter our algorithm for optimization and then specify the framework to use it.

Due to recent improvements in Java's multi-threading capabilities, OptaPlanner also gives developers the ability to use multiple implementations of multi-threading such as fork and join, incremental solving and multitenancy.

Fare riferimento alla documentazione per ulteriori informazioni.

8. Conclusione

Il framework OptaPlanner fornisce agli sviluppatori un potente strumento per risolvere i problemi di soddisfazione dei vincoli come la pianificazione e l'allocazione delle risorse.

OptaPlanner offre un utilizzo minimo delle risorse JVM oltre all'integrazione con Jakarta EE. L'autore continua a supportare il framework e Red Hat lo ha aggiunto come parte della sua Business Rules Management Suite.

Come sempre il codice può essere trovato su Github.