Die vorigen Teile dieser Serie haben beschrieben, wie das Optimierungsproblem modelliert und das Modell mit Hilfe von OptaPlanner umgesetzt wird. Dieser Teil beschäftigt sich mit dem eigentlichen Lösungsverfahren des Problems.
Ablauf der Optimierung
Der Solver übernimmt die Optimierung des Problems und durchläuft dabei mindestens zwei Phasen. In der ersten Phase wird eine Ausgangslösung erstellt. Diese wird in der oder den darauf folgenden Phase(n) inkrementell optimiert. Für beide Phasen stellt OptaPlanner unterschiedliche Heuristiken zur Verfügung, die je nach Art des Optimierungsproblems auszuwählen sind. OptaPlanner bietet zudem eine Benchmarkingfunktionalität, welche die Evaluation verschiedener Heuristiken durch automatische Läufe und Gegenüberstellung verschiedener Konfigurationen des Solvers mit grafischen Reports zu Performance und Skalierbarkeit unterstützt.
In unserem Beispiel entfällt die erste Phase des Solvers. Aus den Eingangsdaten können wir bereits einen validen Stundenplan (CourseSchedule) erstellen und müssen keine Ausgangslösung generieren. In der Konfiguration unseres Solvers geben wir neben SolutionClass, entityClass und der Konfiguration der Bewertungsfunktion nur eine weitere Phase an.
Die Optimierung findet mittels einem Verfahren der lokalen Suche statt. Im Rahmen der lokalen Suche werden von OptaPlanner verschiedene Moves generiert. Ein Move verändert dabei eine bestehende Lösung durch das Verändern verschiedener Elemente der Lösung. Wir nutzen eine Kombination aus OptaPlanners generischem SwapMove, dieser vertauscht die Werte der Planungsvariablen von zwei Planungsentitäten, und einem selbst implementierten Custom Move.
Custom Moves
Im Stundenplan des ONG finden die meisten Kurse in einem Block von mehreren Unterrichtsstunden statt, ebenso müssen bestimmte Kurse zeitlich parallel (gekoppelt) stattfinden (z.B. der Sportunterricht für Mädchen und für Jungen). Diese Einschränkungen sind zu Beginn der Optimierung bekannt und so kann OptaPlanner dabei geholfen werden mehr gültige Moves zu erzeugen und dadurch die Rechenzeit zu minimieren.
Der von uns implementierte LectureChangeMove ändert die Schulstunden aller Unterrichtsstunden eines Blockes und nicht nur die einer einzelnen Unterrichtsstunde. Außerdem werden die Schulstunden der parallel stattfindenden Unterrichtsstunden im gleichen Zug entsprechend geändert:
[code language=”java”]
public class LectureChangeMove implements Move {
…
@Override
public void doMove(ScoreDirector scoreDirector) {
for (int i = 0; i < lectures.size(); i++) {
Lecture left = lectures.get(i);
scoreDirector.beforeVariableChanged(left, "period");
left.setPeriod(toPeriods.get(i));
scoreDirector.afterVariableChanged(left, "period");
for(Lecture coupled : left.getCoupledLectures())
{
scoreDirector.beforeVariableChanged(coupled, "period");
coupled.setPeriod(toPeriods.get(i));
scoreDirector.afterVariableChanged(coupled, "period");
}
}
}
…
}
[/code]
Generiert werden neue Moves vom SubsequentLecturesChangeMoveIterator. Ausgangspunkt für einen Move ist eine, aus der Menge aller Fakten im Arbeitsspeicher der Regelengine, ausgewählte Unterrichtsstunde. Die Planungsvariable (Schulstunde) der ausgewählten Unterrichtsstunde wird neu gesetzt. Bei der Erstellung des Moves wird überprüft, ob ausgehend der zufällig ausgewählten Schulstunde des der Unterrichtsstunde, auch alle weiteren mit dieser im Block stattfindenden Unterrichtsstunden innerhalb der 10 Schulstunden des Tages Platz finden (ab Zeile 9). Es werden also keine Moves erstellt, die Blöcke auseinander reißen und damit eine ungültige Lösung erzeugen würde.
[code language=”java”]
private class SubsequentLecturesChangeMoveIterator implements Iterator<Move> {
…
@Override
public Move next() {
final Lecture left = blocks.get(workingRandom.nextInt(totalSize));
List<Lecture> leftSubsequent = new ArrayList<>();
leftSubsequent.addAll(left.getSubsequentLectures());
leftSubsequent.add(left);
Period newStartPeriod = startPeriodsOddTimeslotIndex
.get(workingRandom.nextInt(startPeriodsOddTimeslotIndex.size()));
while (10 – newStartPeriod.getTimeslot().getTimeslotIndex() < 10 – leftSubsequent.size()) {
newStartPeriod = startPeriodsOddTimeslotIndex
.get(workingRandom.nextInt(startPeriodsOddTimeslotIndex.size()));
}
List<Period> newPeriods = new ArrayList<>();
newPeriods.add(newStartPeriod);
while (newPeriods.size() < leftSubsequent.size()) {
Period last = newPeriods.get(newPeriods.size() – 1);
Period nextPeriod = periods.stream()
.filter(p -> p.getDay() == last.getDay() && p.getTimeslot().getTimeslotIndex() == last.getTimeslot()
.getTimeslotIndex() + 1).collect(Collectors.toList()).get(0);
newPeriods.add(nextPeriod);
}
return new LectureChangeMove(leftSubsequent, newPeriods);
}
}
[/code]
Konfiguration des Solvers
Der Solver kann über eine XML Datei konfiguriert werden. In der Konfiguration werden OptaPlanner die Bestandteile des Modells bekannt gemacht, sowie Einstellungen zum Lösungsverfahren vorgenommen.
In unserem Beispiel wird eine Solverphase konfiguriert (localsearch, Zeile 10-27). Diese nutzt eine Kombination aus dem generischen SwapMove und unserem zuvor beschriebenen LectureChangeMove (Zeile 11-18). Der acceptor legt fest, welche Moves akzeptiert werden sollen. In diesem Beispiel lassen wir nur Moves zu, die zu einer besseren Lösung als die letzten 900 führen (lateAcceptanceSize) und die nicht die letzten fünf veränderten Planungsentitäten betreffen (entityTabuSize). Der forager sammelt alle akzeptierten Moves und wählt aus welche durchgeführt werden. Pro Schritt werden hier nur sechs Moves ausgewertet (acceptedCountLimit). Ein Move, der die letzte beste Lösung verbessert, wird sofort ausgewählt (pickEarlyType).
[code title=”solverConfig.xml”]
<solver>
<!–<environmentMode>FULL_ASSERT</environmentMode>–>
<solutionClass>de.akquinet.untis.planner.domain.CourseSchedule</solutionClass>
<entityClass>de.akquinet.untis.planner.domain.Lecture</entityClass>
<scoreDirectorFactory…>
<–!<constructionHeuristic></constructionHeuristic>–>
<localSearch>
<unionMoveSelector>
<swapMoveSelector>
<filterClass>de.akquinet.untis.planner.solver.move.filter.SwapMoveFilter</filterClass>
</swapMoveSelector>
<moveIteratorFactory>
<moveIteratorFactoryClass>de.akquinet.untis.planner.solver.move.factory.LectureChangeMoveIteratorFactory</moveIteratorFactoryClass>
</moveIteratorFactory>
</unionMoveSelector>
<acceptor>
<lateAcceptanceSize>900</lateAcceptanceSize>
<entityTabuSize>5</entityTabuSize>
</acceptor>
<forager>
<pickEarlyType>FIRST_BEST_SCORE_IMPROVING</pickEarlyType>
<acceptedCountLimit>6</acceptedCountLimit>
</forager>
</localSearch>
</solver>
[/code]
Mit diesem Teil der Serie sind die Schritte zu einem, hinsichtlich der Fahrtzeiten, optimierten Stundenplan komplett.
Der abschließende letzte Teil stellt die Ausführung der Optimierung und die dabei erreichten Ergebnisse vor.