streamalism.org

1. Úvod do programu OptaPlanner

V tomto výučbe sa pozrieme na riešenie problémov s obmedzením jazyka Java s názvom OptaPlanner.

OptaPlanner rieši problémy s plánovaním pomocou sady algoritmov s minimálnym nastavením.

Pochopenie algoritmov môže poskytnúť užitočné podrobnosti, zatiaľ čo rámec za nás vykonáva tvrdú prácu.

2. Závislosť od Maven

Najskôr pridáme závislosť Maven pre OptaPlanner:

 org.optaplanner optaplanner-core 7.9.0.Final 

Vyhľadáme najnovšiu verziu programu OptaPlanner z úložiska Maven Central.

3. Trieda problému / riešenia

Na vyriešenie problému určite potrebujeme konkrétny príklad.

Harmonogram prednášok je vhodným príkladom z dôvodu ťažkostí s vyvážením zdrojov, ako sú miestnosti, čas a učitelia.

3.1. Rozvrh kurzu

Rozvrh kurzu obsahuje kombináciu našich problémových premenných a plánovacích entít, takže je to trieda riešenia. Vo výsledku tak nakonfigurujeme niekoľko anotácií.

Pozrime sa na každú z nich bližšie:

@PlanningSolution verejná trieda CourseSchedule {private List roomList; private List periodList; private List lectureList; súkromné ​​skóre HardSoftScore;

The Plánovacie riešenie anotácia hovorí OptaPlanneru, že táto trieda obsahuje údaje, ktoré zahŕňajú riešenie.

OptaPlanner očakáva tieto minimálne komponenty: entitu plánovania, fakty o problémoch a skóre.

3.2. Prednáška

Prednáška, POJO, vyzerá ako:

@PlanningEntity verejná trieda Prednáška {public Integer roomNumber; verejné celé číslo; verejný učiteľ reťazca; @PlanningVariable (valueRangeProviderRefs = {"availablePeriods"}) public Integer getPeriod () {návratové obdobie; } @PlanningVariable (valueRangeProviderRefs = {"availableRooms"}) verejné celé číslo getRoomNumber () {return roomNumber; }}

Používame Prednáška triedy ako plánovacia entita, takže pridáme ďalšiu anotáciu k getru dovnútra Rozvrh kurzu:

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

Naša plánovacia entita obsahuje obmedzenia, ktoré sa stanovujú.

The Premenná plánovania anotácia a valueRangeProviderRef anotácie spájajú obmedzenia s problémovými faktami.

Tieto obmedzenia budú zaznamenané neskôr vo všetkých plánovacích entitách.

3.3. Fakty o probléme

The číslo izby a obdobie premenné pôsobia ako obmedzenia podobne navzájom.

OptaPlanner skóre riešení ako výsledok logiky pomocou týchto premenných. K obom pridávame anotácie getter metódy:

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

Tieto zoznamy sú všetky možné hodnoty použité v Prednáška polia.

OptaPlanner ich obsadzuje do všetkých riešení v rámci vyhľadávacieho priestoru.

Nakoniec nastaví skóre pre každé z riešení, takže potrebujeme pole na uloženie skóre:

@PlanningScore public HardSoftScore getScore () {návrat skóre; }

Bez skóre nemôže OptaPlanner nájsť optimálne riešenie, a preto zdôraznil význam skôr.

4. Bodovanie

Na rozdiel od toho, na čo sme sa doteraz pozreli, vyžaduje bodovacia trieda viac vlastného kódu.

Je to tak preto, lebo kalkulačka skóre je špecifická pre daný problém a model domény.

4.1. Vlastná Java

Na vyriešenie tohto problému používame jednoduchý výpočet skóre (aj keď sa to nemusí zdať):

verejná trieda ScoreCalculator implementuje EasyScoreCalculator {@Override verejné skóre CalcScore (CourseSchedule courseSchedule) {int hardScore = 0; int softScore = 0; Nastaviť obsadenéRoomy = nový HashSet (); for (Lecture lecture: courseSchedule.getLectureList ()) {String roomInUse = lecture.getPeriod () .toString () + ":" + lecture.getRoomNumber (). toString (); if (employedRooms.contains (roomInUse)) {hardScore + = -1; } else {employedRooms.add (roomInUse); }} vratit HardSoftScore.valueOf (hardScore, softScore); }}

Ak sa bližšie pozrieme na vyššie uvedený kód, dôležité časti sa stanú jasnejšími. Vypočítame skóre v cykle, pretože Zoznam obsahuje konkrétne nie jedinečné kombinácie miestností a období.

The HashSet sa používa na uloženie jedinečného kľúča (reťazca), aby sme mohli penalizovať duplikované prednášky v tej istej miestnosti a období.

Vo výsledku dostávame jedinečné súbory miestností a období.

4.2. Sliny

Súbory Drools nám poskytujú rýchly spôsob, ako zmeniť pravidlá týkajúce sa súborov. Aj keď môže byť syntax niekedy mätúca, súbor Drools môže predstavovať spôsob, ako spravovať logiku mimo skompilovaných tried.

Naše pravidlo zabrániť neplatným položkám vyzerá takto:

globálny HardSoftScoreHolder scoreHolder; pravidlo "noNullRoomPeriod", keď Prednáška (roomNumber == null); Prednáška (obdobie == null); potom scoreHolder.addHardConstraintMatch (kcontext, -1); koniec

5. Konfigurácia riešiteľa

Ďalším nevyhnutným konfiguračným súborom je súbor XML, ktorý slúži na konfiguráciu riešiteľa.

5.1. XML konfiguračný súbor

    org.baeldung.optaplanner.ScoreCalculator 10 

Kvôli našim anotáciám v Rozvrh kurzu triedy, používame scanAnnotatedClasses prvok tu na skenovanie súborov na ceste triedy.

The scoreDirectorFactory obsah prvkov nastavil našu ScoreCalculator triedy, aby obsahovala našu logiku skórovania.

Ak chceme použiť súbor Drools, nahradíme obsah prvku:

courseScheduleScoreRules.drl

Naše konečné nastavenie je ukončovací prvok. Namiesto nekonečného hľadania optimalizovaného riešenia, ktoré možno nikdy nebude existovať, toto nastavenie zastaví vyhľadávanie po uplynutí časového limitu.

Desať sekúnd je viac ako dosť pre väčšinu problémov.

6. Testovanie

Nakonfigurovali sme naše triedy riešení, riešení a problémov. Poďme to vyskúšať!

6.1. Nastavujeme náš test

Najprv urobíme nejaké nastavenie:

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

Po druhé, vyplníme údaje do zbierky plánovacej entity a problému Zoznam predmety.

6.2. Vykonanie a overenie testu

Nakoniec to otestujeme zavolaním vyriešiť.

CourseSchedule identifiedCourseSchedule = solver.solve (unsolvingCourseSchedule); assertNotNull (řešenéCourseSchedule.getScore ()); assertEquals (-4, vyriešenéCourseSchedule.getScore (). getHardScore ());

Skontrolujeme, či vyriešenýCourseSchedule má skóre, ktoré nám hovorí, že máme „optimálne“ riešenie.

Pre bonus vytvoríme metódu tlače, ktorá zobrazí naše optimalizované riešenie:

public void printCourseSchedule () {lectureList.stream () .map (c -> "Prednáška v miestnosti" + c.getRoomNumber (). toString () + "počas obdobia" + c.getPeriod (). toString ()) .forEach (k -> logger.info (k)); }

Táto metóda zobrazuje:

Prednáška v miestnosti 1 v období 1 Prednáška v miestnosti 2 v období 1 Prednáška v miestnosti 1 v období 2 Prednáška v miestnosti 2 v období 2 Prednáška v miestnosti 1 v období 3 Prednáška v miestnosti 2 v období 3 Prednáška v miestnosti 1 v období 1 Prednáška v miestnosti 1 v období 1 Prednáška v miestnosti 1 v období 1 Prednáška v miestnosti 1 v období 1

Všimnite si, ako sa opakujú posledné tri záznamy. Stáva sa to preto, lebo náš problém neexistuje optimálnym riešením. Vybrali sme si tri obdobia, dve učebne a desať prednášok.

Existuje len šesť možných prednášok kvôli týmto fixným zdrojom. Prinajmenšom táto odpoveď ukazuje používateľovi, že nie je dostatok miestností alebo období na to, aby sa v nich mohli konať všetky prednášky.

7. Extra funkcie

Náš príklad pre OptaPlanner, ktorý sme vytvorili, bol jednoduchý, avšak rámec pridal funkcie pre rozmanitejšie prípady použitia. Možno budeme chcieť implementovať alebo zmeniť náš algoritmus na optimalizáciu a potom určiť rámec, ktorý ho bude používať.

Vďaka nedávnym vylepšeniam možností Java pre viacvláknové spracovanie dáva OptaPlanner vývojárom tiež možnosť používať viacnásobné implementácie viacvláknového spracovania, ako je fork and join, prírastkové riešenie a multitenancy.

Ďalšie informácie nájdete v dokumentácii.

8. Záver

Rámec OptaPlanner poskytuje vývojárom výkonný nástroj na riešenie problémov so spokojnosťou s obmedzeniami, ako je plánovanie a prideľovanie zdrojov.

OptaPlanner ponúka minimálne využitie zdrojov JVM, ako aj integráciu s Jakarta EE. Autor naďalej podporuje tento rámec a Red Hat ho pridal ako súčasť svojej sady Business Rules Management Suite.

Ako vždy, kód nájdete na Githube.