streamalism.org

1. Inleiding tot OptaPlanner

In deze zelfstudie kijken we naar een Java-probleemoplosser voor beperkingen, OptaPlanner genaamd.

OptaPlanner lost planningsproblemen op met behulp van een reeks algoritmen met minimale instellingen.

Hoewel een goed begrip van de algoritmen nuttige details kan opleveren, doet het raamwerk het harde werk voor ons.

2. Maven Afhankelijkheid

Eerst voegen we een Maven-afhankelijkheid toe voor OptaPlanner:

 org.optaplanner optaplanner-core 7.9.0.Final 

We vinden de meest recente versie van OptaPlanner uit de Maven Central-repository.

3. Probleem / Oplossingsklasse

Om een ​​probleem op te lossen hebben we zeker een specifiek probleem als voorbeeld nodig.

Het roosteren van colleges is een geschikt voorbeeld vanwege de moeilijkheid om middelen zoals kamers, tijd en docenten met elkaar in evenwicht te brengen.

3.1. Cursusschema

Cursusschema bevat een combinatie van onze probleemvariabelen en planningsentiteiten en is daarom de oplossingsklasse. Als gevolg hiervan gebruiken we meerdere annotaties om het te configureren.

Laten we elk afzonderlijk nader bekijken:

@PlanningSolution openbare klas CourseSchedule {privé List roomList; privélijst periodList; privélijst lectureList; privé HardSoftScore-score;

De Planning Oplossing annotatie vertelt OptaPlanner dat deze klasse de gegevens bevat om een ​​oplossing te omvatten.

OptaPlanner verwacht deze minimale componenten: de planningsentiteit, probleemfeiten en een score.

3.2. Lezing

Lezing, een POJO, ziet eruit als:

@PlanningEntity openbare klas Lezing {openbaar geheel getal roomNumber; openbare Integer-periode; openbare String leraar; @PlanningVariable (valueRangeProviderRefs = {"availablePeriods"}) openbaar geheel getal getPeriod () {retourperiode; } @PlanningVariable (valueRangeProviderRefs = {"availableRooms"}) openbaar geheel getal getRoomNumber () {return roomNumber; }}

We gebruiken Lezing class als de planningsentiteit, dus we voegen nog een annotatie toe aan de getter in Cursusschema:

@PlanningEntityCollectionProperty openbare lijst getLectureList () {terug lectureList; }

Onze planningsentiteit bevat de beperkingen die worden gesteld.

De Planning Variabel annotatie en de valueRangeProviderRef annotaties koppelen de beperkingen aan de probleemfeiten.

Deze beperkingswaarden zullen later worden gescoord voor alle planningsentiteiten.

3.3. Probleem feiten

De kamernummer en periode variabelen fungeren als beperkingen die vergelijkbaar zijn met elkaar.

OptaPlanner scoort de oplossingen op basis van logica met behulp van deze variabelen. We voegen aan beide annotaties toe getter methoden:

@ValueRangeProvider (id = "availableRooms") @ProblemFactCollectionProperty openbare lijst getRoomList () {return roomList; } @ValueRangeProvider (id = "availablePeriods") @ProblemFactCollectionProperty openbare lijst getPeriodList () {retour periodList; } 

Deze lijsten zijn alle mogelijke waarden die worden gebruikt in de Lezing velden.

OptaPlanner vult ze in alle oplossingen in de zoekruimte.

Ten slotte stelt het vervolgens een score in voor elk van de oplossingen, dus we hebben een veld nodig om de score op te slaan:

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

Zonder score kan OptaPlanner de optimale oplossing niet vinden, vandaar het eerder benadrukte belang.

4. Scoren

In tegenstelling tot waar we tot nu toe naar hebben gekeken, heeft de scoreklasse meer aangepaste code nodig.

Dit komt doordat de scorecalculator specifiek is voor het probleem en het domeinmodel.

4.1. Aangepaste Java

We gebruiken een eenvoudige scoreberekening om dit probleem op te lossen (hoewel het er misschien niet zo uitziet):

openbare klasse ScoreCalculator implementeert EasyScoreCalculator {@Override openbare score berekenenScore (CourseSchedule courseSchedule) {int hardScore = 0; int softScore = 0; Set bezetRooms = nieuwe HashSet (); voor (Hoorcollege: courseSchedule.getLectureList ()) {String roomInUse = lecture.getPeriod () .toString () + ":" + lecture.getRoomNumber (). toString (); if (bezetRooms.contains (roomInUse)) {hardScore + = -1; } anders {bezetRooms.add (roomInUse); }} retourneer HardSoftScore.valueOf (hardScore, softScore); }}

Als we de bovenstaande code nader bekijken, worden de belangrijke onderdelen duidelijker. We berekenen een score in de lus omdat de Lijst bevat specifieke niet-unieke combinaties van kamers en periodes.

De HashSet wordt gebruikt om een ​​unieke sleutel (string) op te slaan, zodat we dubbele colleges in dezelfde ruimte en periode kunnen bestraffen.

Hierdoor krijgen we unieke sets kamers en periodes.

4.2. Kwijlt

Drools-bestanden bieden ons een snelle manier om regels voor toepassing op bestanden te wijzigen. Hoewel de syntaxis soms verwarrend kan zijn, kan het Drools-bestand een manier zijn om logica buiten de gecompileerde klassen te beheren.

Onze regel om null-invoer te voorkomen ziet er als volgt uit:

wereldwijde HardSoftScoreHolder scoreHolder; regel "noNullRoomPeriod" wanneer Lecture (roomNumber == null); Hoorcollege (periode == null); dan scoreHolder.addHardConstraintMatch (kcontext, -1); einde

5. Oplosserconfiguratie

Een ander noodzakelijk configuratiebestand, we hebben een XML-bestand nodig om de oplosser te configureren.

5.1. XML-configuratiebestand

    org.baeldung.optaplanner.ScoreCalculator 10 

Vanwege onze annotaties in het Cursusschema klasse gebruiken we de scanAnnotatedClasses element hier om bestanden op het klassenpad te scannen.

De scoreDirectorFactory elementinhoud stelt ons in ScoreCalculator class om onze scorelogica te bevatten.

Als we een Drools-bestand willen gebruiken, vervangen we de inhoud van het element door:

courseScheduleScoreRules.drl

Onze laatste instelling is het afsluitelement. In plaats van eindeloos te zoeken naar een geoptimaliseerde oplossing die misschien nooit zal bestaan, stopt deze instelling het zoeken na een bepaalde tijdslimiet.

Voor de meeste problemen is tien seconden meer dan voldoende.

6. Testen

We hebben onze oplossings-, oplossings- en probleemklassen geconfigureerd. Laten we het testen!

6.1. Onze test opzetten

Eerst doen we wat instellingen:

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

Ten tweede vullen we gegevens in de verzameling van de planningsentiteit en het probleemfeit Lijst voorwerpen.

6.2. Testuitvoering en verificatie

Ten slotte testen we het door te bellen oplossen.

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

We controleren of het solvedCourseSchedule heeft een score die ons vertelt dat we de "optimale" oplossing hebben.

Als bonus creëren we een afdrukmethode die onze geoptimaliseerde oplossing laat zien:

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

Deze methode toont:

Lezing in zaal 1 tijdens periode 1 Hoorcollege in zaal 2 tijdens periode 1 Lezing in zaal 1 tijdens periode 2 Lezing in zaal 2 tijdens periode 2 Lezing in zaal 1 tijdens periode 3 Lezing in zaal 2 tijdens periode 3 Lezing in zaal 1 tijdens periode 1 Hoorcollege in Zaal 1 tijdens Periode 1 Lezing in Zaal 1 tijdens Periode 1 Lezing in Zaal 1 tijdens Periode 1

Merk op hoe de laatste drie vermeldingen zich herhalen. Dit gebeurt omdat er geen optimale oplossing is voor ons probleem. We kozen voor drie periodes, twee klaslokalen en tien lezingen.

Door deze vaste middelen zijn er maar zes mogelijke colleges. Dit antwoord laat de gebruiker op zijn minst zien dat er niet genoeg kamers of periodes zijn om alle colleges te bevatten.

7. Extra functies

Ons voorbeeld voor OptaPlanner dat we hebben gemaakt, was eenvoudig, maar het framework heeft functies toegevoegd voor meer uiteenlopende gebruiksscenario's. Mogelijk willen we ons algoritme voor optimalisatie implementeren of wijzigen en vervolgens het framework specificeren om het te gebruiken.

Vanwege recente verbeteringen in Java's multi-threading-mogelijkheden, geeft OptaPlanner ontwikkelaars ook de mogelijkheid om meerdere implementaties van multi-threading te gebruiken, zoals fork en join, incrementeel oplossen en multitenancy.

Raadpleeg de documentatie voor meer informatie.

8. Conclusie

Het OptaPlanner-framework biedt ontwikkelaars een krachtig hulpmiddel om problemen met tevredenheid van beperkingen op te lossen, zoals planning en toewijzing van middelen.

OptaPlanner biedt minimaal gebruik van JVM-bronnen en kan worden geïntegreerd met Jakarta EE. De auteur blijft het framework ondersteunen en Red Hat heeft het toegevoegd als onderdeel van zijn Business Rules Management Suite.

Zoals altijd is de code te vinden op Github.