Add Thesis

Entwicklung eines genetischen Algorithmus für eine bestehende Ressourcenplanungssoftware

Written by Martin Pölzl

Paper category

Bachelor Thesis

Subject

Computer Science

Year

2017

Abstract

Bachelorarbeit: Analyse bestehender Implementierungen Dieses Kapitel beschäftigt sich mit dem in der Arbeit [Pöl11] entwickelten genetischen Algorithmus. Der Fokus liegt auf der Analyse bestehender Implementierungen, um das Verbesserungspotenzial zu ermitteln. Leiten Sie Maßnahmen aus der Analyse ab, um die Ergebnisse zu verbessern. 2.1 Funktionsanalyse Der implementierte genetische Algorithmus entspricht der Standardvariante von John Holland [Hol92], die aus Rekombination und Mutation besteht. Es wurden weitere Mechanismen hinzugefügt, die jedoch nur zur Fehlerkorrektur verwendet werden. Die ausgewählte Reorganisationsmethode generiert einen Lehrplan, indem geradzahlige Tage aus Elternplan A bzw. ungerade Tage aus Elternplan B ausgewählt werden. Dieses Verfahren hat jedoch zwei Nachteile. Durch eine Reorganisation kann sich die Gesamtzahl der Unterrichtseinheiten ändern. Abbildung 5 zeigt deutlich, dass hier Kurse „verloren“ gehen können. Da die Anzahl der Unterrichtseinheiten im Kurs nur geringfügig abweichen kann, müssen diese Schäden behoben werden. Diese Reparaturfunktion analysiert den Lehrplan und listet die tatsächliche Anzahl der Unterrichtseinheiten auf. Danach wurde die redundante Lehreinheit durch die fehlende Lehreinheit ersetzt. Das zweite Problem entsteht bei der Elite-Variante des genetischen Algorithmus aufgrund der fehlenden Durchmischung im Reorganisationsprozess. Bei dieser Variante wird in der nächsten Iteration die Lösung mit der besten Bewertung (dh der geringsten Strafe) verwendet. Es ist zu beobachten, dass bei fortgesetzter Optimierung alle bestehenden Lösungen der Population gleich sind, es also keine Verbesserung mehr gibt, da es aus evolutionärer Sicht kein alternatives genetisches Material mehr gibt [Pöl11]. Die Mutation ist hier offensichtlich zu klein. Um diese Konvergenz zu verhindern, wird eine Verschiebungsoperation eingeführt, um einen übergeordneten Plan vor jeder Reorganisation auf die nächsten n Tage zu verschieben. Die gewählte Reorganisationsmethode hat jedoch keinen Einfluss auf das Niveau der Unterrichtseinheit, sodass es nicht möglich ist, an einem Tag Fehler zu beheben. In der aktuellen Implementierung kann nur eine Mutation diese Aufgabe erfüllen. Dazu wurde eine Mutation des zufälligen Vertauschens von zwei Unterrichtseinheiten implementiert. Da Mutationsvarianten rein zufällig funktionieren, spricht man von einem Monte-Carlo-Prozess. Diese Art von Programm kennt ihre Vergangenheit nicht und kann daher bereits gemachte Fehler wiederholen [Klu09]. Bei zufälligen Mutationen ist jede ungefähr. 2.2 Laufzeitanalyse Die folgende Laufzeit wurde mit der Klasse "System.Diagnostic.Stopwatch" im .NET Framework im Debugmodus von Visual Studio 2010 Professional aufgezeichnet. Aufgrund des Debug-Modus entspricht die Zeit nicht der tatsächlichen Ausführungszeit, es reicht jedoch aus, den Engpass in der Ausführung zu identifizieren und verschiedene Implementierungen zu vergleichen. Die folgende Tabelle (Tabelle 2-1, Tabelle 2-2, Tabelle 2-3) listet die Ausführungszeit verschiedener Populationen auf. 2.3 Fazit und Maßnahmenliste Betrachtet man die Laufzeitanalyse, so besteht der größte Nachteil bestehender Implementierungen darin, dass sie viel Zeit für vermeidbare Maßnahmen aufwenden. Da die Auswertungsfunktion den größten Anteil der Dauer einnimmt, wird hier ein Programm vorgestellt, das sich an den bestehenden Stundenplan erinnert und somit den bekannten Stundenplan nicht auswertet. Außerdem ist der Quellcode für die Laufzeit optimiert. Die Reparaturfunktion ist notwendig und nimmt auch ca. 25 % der Laufzeit in Anspruch. Da es ohne Änderung des Reorganisationsprozesses nicht entfernt werden kann, werden hier keine Maßnahmen zur Verbesserung der Laufzeit abgeleitet. Stattdessen besteht das Ziel darin, diese Funktion vollständig aufzugeben. Abbildung 6 zeigt den automatisch generierten Studienplan für das 5. Semester. Die Kluft zwischen der Semesterend-Lehreinheit und der isolierten Lehreinheit ist gewaltig. Das verwendete Verfahren, sei es Rekombination oder Mutation, löst dieses Problem nicht endgültig. Tatsächlich kann nur eine Mutation einzelne Unterrichtseinheiten verändern, was an der NP-Komplexität des Problems liegt [Coo95] – der Lösungsraum enthält mindestens 350! Lösung - kann aber nicht zu einer Lösung führen. Daher ist ein Programm erforderlich, das separate Unterrichtseinheiten verhindert. Auch die als "frei" gekennzeichneten Tage sind offensichtlich. Heutzutage erhielten sie eine kostenlose Einschränkung, bevor sie erstellt wurden, was bei Verstößen zu vielen Strafen führte, sodass diese Lösung verworfen wurde. Dennoch ist es weiterhin möglich, diese Lösungen zu generieren und auszuwerten. Wenn Sie nun Ruhetage aus dem Suchbereich ausschließen, werden 72 Tage verkürzt! Lösung. Der neue Suchraum beträgt immer noch fast 300! Groß, aber Sie können alle Prüfverstöße löschen, die Termine verbieten. Folgende Punkte sind Maßnahmen zur Geschwindigkeitssteigerung: -Der Gedächtnisfunktionsplan im Kurs verhindert wiederholte Bewertungen Read Less