Eine Anleitung zu OptaPlanner

1. Einführung in OptaPlanner

In diesem Tutorial sehen wir uns einen Java-Constraint-Zufriedenheitslöser namens OptaPlanner an.

OptaPlanner löst Planungsprobleme mithilfe einer Reihe von Algorithmen mit minimalem Setup.

Obwohl ein Verständnis der Algorithmen hilfreiche Details liefern kann, führt das Framework die harte Arbeit für uns aus.

2. Maven-Abhängigkeit

Zunächst fügen wir eine Maven-Abhängigkeit für OptaPlanner hinzu:

 org.optaplanner optaplanner-core 7.9.0.Final  

Wir suchen die neueste Version von OptaPlanner aus dem Maven Central-Repository.

3. Problem- / Lösungsklasse

Um ein Problem zu lösen, brauchen wir sicherlich ein bestimmtes als Beispiel.

Der Stundenplan für Vorlesungen ist ein geeignetes Beispiel, da es schwierig ist, Ressourcen wie Räume, Zeit und Lehrer auszugleichen.

3.1. CourseSchedule

CourseSchedule enthält eine Kombination unserer Problemvariablen und Planungsentitäten, daher ist es die Lösungsklasse. Daher verwenden wir mehrere Anmerkungen, um es zu konfigurieren.

Schauen wir uns jedes einzeln genauer an:

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

Die PlanningSolution- Annotation teilt OptaPlanner mit, dass diese Klasse die Daten enthält, die eine Lösung umfassen sollen.

OptaPlanner erwartet diese Mindestkomponenten: die Planungseinheit, Problemfakten und eine Bewertung.

3.2. Vorlesung

Vortrag, ein POJO, sieht aus wie:

@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; } }

Wir verwenden die Lecture- Klasse als Planungsentität, daher fügen wir dem Getter in CourseSchedule eine weitere Anmerkung hinzu :

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

Unsere Planungsentität enthält die Einschränkungen, die festgelegt werden.

Die Annotation PlanningVariable und die Annotationen valueRangeProviderRef verknüpfen die Einschränkungen mit den Problemfakten.

Diese Einschränkungswerte werden später für alle Planungseinheiten bewertet.

3.3. Problem Fakten

Die Variablen roomNumber und period wirken ähnlich wie Einschränkungen.

OptaPlanner bewertet die Lösungen anhand der Logik anhand dieser Variablen. Wir fügen beiden Getter- Methoden Anmerkungen hinzu :

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

Diese Listen sind alle möglichen Werte, die in den Vorlesungsfeldern verwendet werden.

OptaPlanner füllt sie in allen Lösungen im Suchbereich.

Schließlich wird für jede der Lösungen eine Punktzahl festgelegt, sodass wir ein Feld zum Speichern der Punktzahl benötigen:

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

Ohne eine Bewertung kann OptaPlanner nicht die optimale Lösung finden, daher die betonte Bedeutung früher.

4. Wertung

Im Gegensatz zu dem, was wir bisher gesehen haben, erfordert die Bewertungsklasse mehr benutzerdefinierten Code.

Dies liegt daran, dass der Score-Rechner spezifisch für das Problem und das Domänenmodell ist.

4.1. Benutzerdefiniertes Java

Wir verwenden eine einfache Punkteberechnung, um dieses Problem zu lösen (obwohl es möglicherweise nicht so scheint):

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); } }

Wenn wir uns den obigen Code genauer ansehen, werden die wichtigen Teile klarer. Wir berechnen eine Punktzahl in der Schleife, da die Liste bestimmte nicht eindeutige Kombinationen von Räumen und Zeiträumen enthält.

Das HashSet wird verwendet, um einen eindeutigen Schlüssel (String) zu speichern, damit doppelte Vorlesungen im selben Raum und in derselben Periode bestraft werden können.

Als Ergebnis erhalten wir einzigartige Sätze von Räumen und Perioden.

4.2. Sabber

Drools-Dateien bieten uns eine schnelle Möglichkeit, Regeln für die Anwendung auf Dateien zu ändern. Während die Syntax manchmal verwirrend sein kann, kann die Drools-Datei eine Möglichkeit sein, Logik außerhalb der kompilierten Klassen zu verwalten.

Unsere Regel zur Verhinderung von Null-Einträgen sieht folgendermaßen aus:

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

5. Solver-Konfiguration

Eine weitere notwendige Konfigurationsdatei, wir benötigen eine XML-Datei, um den Solver zu konfigurieren.

5.1. XML-Konfigurationsdatei

    org.baeldung.optaplanner.ScoreCalculator    10   

Aufgrund unserer Anmerkungen in der CourseSchedule- Klasse verwenden wir hier das Element scanAnnotatedClasses , um Dateien im Klassenpfad zu scannen.

Der Inhalt des scoreDirectorFactory- Elements legt fest, dass unsere ScoreCalculator- Klasse unsere Bewertungslogik enthält.

Wenn wir eine Drools-Datei verwenden möchten, ersetzen wir den Elementinhalt durch:

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.

Weitere Informationen finden Sie in der Dokumentation.

8. Fazit

Das OptaPlanner-Framework bietet Entwicklern ein leistungsstarkes Tool zur Lösung von Problemen bei der Erfüllung von Einschränkungen wie Zeitplanung und Ressourcenzuweisung.

OptaPlanner bietet eine minimale Nutzung der JVM-Ressourcen sowie die Integration in Jakarta EE. Der Autor unterstützt das Framework weiterhin und Red Hat hat es als Teil seiner Business Rules Management Suite hinzugefügt.

Wie immer ist der Code auf Github zu finden.