Lade Inhalt...

Evolutionärer Algorithmus zur Aufteilung von Erntemengen auf kundenspezifische Packungseinheiten

Lösen eines Packproblems für einen Gemüsehof

von Fabian Deitelhoff (Autor) Christof Geisler (Autor)

Ausarbeitung 2012 48 Seiten

Informatik - Angewandte Informatik

Leseprobe

Inhaltsverzeichnis

Abkurzungs- und FremdwOrterverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1. Abstract

2. Einleitung

3. Aufgabenstellung
3.1. Ist-Zustand
3.1.1. Problembeschreibung
3.1.2. Vorhandene Software
3.2. Soll-Zustand
3.2.1. Geplante Integration
3.2.2. Erkannte Probleme
3.2.3. Neuer Losungsansatz
3.3. Konkrete Problemdefinition
3.3.1. Beschreibung der Gemusekisten
3.3.2. Beschreibung der Kundenpraferenzen
3.3.3. Definition der Einheiten
3.3.4. Definition der konkreten Mengen

4. Entwicklungsumgebung
4.1. Auswahl der Programmiersprache
4.2. Integrierte Entwicklungsumgebung (IDE)
4.3. Datenbank
4.4. Versionsverwaltungssystem
4.5. Zusatzliche Zeichnungen
4.6. Eingesetzte Frameworks
4.7. Arbeitsumgebung
4.7.1. Hardware
4.7.2. Software

5. LOsungsstrategie
5.1. Genaue Problemanalyse
5.2. Bestimmung der Parameter
5.3. Konventioneller Losungsansatz
5.4. Evolutionarer Losungsansatz
5.4.1. Evolutionares Vorgehen
5.4.2. Allgemeine Packprobleme
5.4.3. Besonderheiten der Aufgabenstellung
5.4.4. Geschlossener Losungsraum
5.5. Gewahlte Strategie

6. Umsetzung
6.1. Implementierung des Algorithmus
6.1.1. Beschreibung wichtiger Objekte
6.1.2. Generieren der Startpopulation
6.1.3. Selektionsstrategie
6.1.4. Rekombinationsstrategien
6.1.5. Berechnung der Fitness
6.1.6. Umgang mit Zufallszahlen
6.2. Visualisierung der Berechnungsergebnisse
6.2.1. Generieren der Datenbasis
6.2.2. Speichern der Berechnungsergebnisse
6.2.3. Darstellung der Entwicklung der Gesamtfitness liber alle Generationen
6.2.4. Darstellung der Fitnesswerte pro Kiste einer Generation
6.2.5. Darstellung der Abweichung der Kistenpreise einer Generation
6.3. Auswahl der Startparameter und Anzeige der Datensatze

7. Untersuchung des Algorithmusverhalten
7.1. Eingrenzen der Auswahl von Startparametern
7.1.1. Startpopulation
7.1.2. Rekombination
7.1.3. Fitnessberechnung
7.2. Weitergehende Untersuchung
7.2.1. Festgelegte Parameter
7.2.2. Testlaufe mit 1-Punkt Crossover
7.2.3. Testlaufe mit 1-Punkt Crossover und zufalliger Mutation
7.3. Interpretation der Ergebnisse

8. Ausblick
8.1. Mogliche Anderungen am Algorithmus
8.1.1. Startpopulation
8.1.2. Rekombinationen
8.1.3. Fitness
8.1.4. Zulassen von Ubermengen
8.1.5. Einfugen weiterer Abbruchkriterien
8.1.6. Analyse der Kisteninhalte
8.1.7. Erweiterungen fur den produktiven Einsatz
8.1.8. Multithreading
8.2. Magliche Programmerweiterungen
8.2.1. Automatisierung der Testlaufe
8.2.2. Anpassen der Datenbasis

9. Fazit

10. Erkiarung

Literaturverzeichnis

A. Klassendiagramm der wichtigsten Objekte

B. Screenshots des Prototyps

C. Fitnesswerte aller Kisten der ersten und letzten Generation

D. Preisverteilung der Startpopulation

Abkurzungs- & Fremdworterverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

1. Schematischer Aufbau eines Individuums (eigene Darstellung)

2. Vorgehen beim 1-Punkt Crossover (eigene Darstellung)

3. Vorgehen beim Tauschen eines Allel an gleicher Stelle (eigene Darstellung)

4. Vorgehen beim Tauschen eines Allel an zwei verschiedenen Stelle (eigene

Darstellung)

5. Vorgehen beim 1-Punkt Crossover mit anschliefiender zufalliger Mutation (eigene Darstellung)

6. Vorgehen beim Aufheben einer Praferenzenverletzung (eigene Darstellung)

7. Auswahlmoglichkeiten der verschiedenen Parameter und der bereits durch gefuhrten Testlaufe (eigene Darstellung)

8. Klassendiagramm der wichtigsten Objekte des Prototypen (eigene Darstel­lung)

9. Entwicklung der Gesamtfitness uber alle Generationen hinweg (eigene Dar­stellung)

10. Fitnessentwicklung der Gemusekisten einer Generation (eigene Darstellung)

11. Preisentwicklung aller Gemusekisten einer Generation (eigene Darstellung)

12. Fitnesswerte aller Kisten der ersten Generation (eigene Darstellung). .

13. Fitnesswerte aller Kisten der letzten Generation (eigene Darstellung). .

14. Preisverteilung fur die Methode Lineare Verteilung von vorne beginnend (eigene Darstellung)

15. Preisverteilung fur die Methode Lineare FUllung mit durchlaufender GemUseverteilung (eigene Darstellung)

16. Preisverteilung fur die Methode Zufallige Kistenverteilung (eigene Dar­stellung)

17. Preisverteilung fur die Methode Zufallige Kistenverteilung mit zufalliger Gemuseauswahl (eigene Darstellung)

Tabellenverzeichnis

1. Testlaufe zur Auswahl der besten Funktion zur Bildung der Startpopulation.

2. Testlaufe zur Auswahl der besten Rekombinationsfunktion

3. Testlaufe zum Ermitteln der durchschnittlichen Laufzeit der 1-Punkt Crossover Strategie

4. Testlaufe zum Ermitteln der durchschnittlichen Laufzeit der Strategie 1-Punkt Crossover mit einer zufalligen Mutation

5. Testlauf mit erhohter Generationenanzahl

1. Abstract

This elaboration dedicates the development of an algorithm that handles a modified mul­tiple knapsack problem. The background for this topic is a real practical optimization scenario. The goal is to fill 20 different vegetables with a different total quantity into a high amount of vegetable boxes. Every box has a maximum price the customer has to pay for. So there is no big variance to fit the customer’s desired price. Furthermore the algo­rithm must consider the customer preferences concerning the different vegetables. Every customer can mark every vegetable as allowed or not allowed.

As this is a NP-complete problem, there is probably no efficient way to solve this task directly.

2. Einleitung

Die vorliegende Ausarbeitung wurde als Klausurleistung fur das Modul Softcomputing im Studiengang Angewandte Informatik der Fachhochschule Sudwestfalen erstellt. Sie entstand auf Basis einer aus der Praxis bekannten Problemstellung beim optimalen Packen von Gemusekisten.

Wir mochten uns an dieser Stelle herzlich fur die gute Betreuung und das Engagement von Herrn Prof. Dr. JOrg Krone bedanken. Durch sein Engagement haben wir nicht nur die Moglichkeit erhalten ein Problem zu bearbeiten, dass fur uns einen realen praktischen Bezug hat, sondern auch den Grundstein fur die Weiterentwicklung einer existierenden Softwarelosung zu legen.

Unser Dank gilt auch Herrn Prof. Dipl.-Ing. Dipl.-Ing. Ulrich Lehmann fur die Kooperation bei der Auswahl des vom Standard abweichenden Themas und fur die Ko- ordination der sehr interessanten Ringvorlesung.

3. Aufgabenstellung

3.1. Ist-Zustand

3.1.1. Problembeschreibung

Hintergrund dieser schriftlichen Ausarbeitung ist ein Optimierungsproblem aus dem tag- lichen Geschaft eines Gemusehofs. Zu den Dienstleistungen eines nach dem Demeter- Prinzip arbeitenden Gemusehofs gehdrt es, Kunden Gemusekisten im Abo anzubieten. Der Kunde hat dabei die Wahl zwischen drei Gemusekisten zu jeweils 10,- EUR, 15,- EUR und 20,- EUR. Diese Gemusekisten werden vom Erzeuger je nach Jahreszeit und vorhandenen Gemusemengen zusammengestellt und beinhalten eine ausgewogene Stan- dardzusammenstellung von Gemusesorten. Zusdtzlich hat jeder Kunde die Mdglichkeit, Prauferenzen auf die vom Gemuusehof angebotenen Gemuusesorten zu vergeben. So kounnen die individuellen Wuunsche des Kunden beruucksichtigt werden. Sei es aus Gruunden des Geschmacks oder wegen Unvertrdglichkeiten.

Hauptproblem bei der Zusammenstellung von Gemusekisten sind die sehr gegensatzlichen Parameter Gesamtmenge an Gemiise, Anzahl GemUsekisten und Kundenpraferenzen. Diese Parameter gilt es zu optimieren. Durch den Einsatz einer Software mit einem geschickt implementierten Algorithmus kounnen zusautzlich der Mitarbeiteraufwand, die anfallenden Kosten und die Qualitat der Zusammenstellung der einzelnen Gemusekisten optimiert werden. Letztes kann zu einem gesteigerten Kundenaufkommen und damit zum Wachstum des Gemusehofs beitragen.

3.1.2. Vorhandene Software

In den Jahren 2006 bis 2007 wurde durch den Autor Fabian Deitelhoff eine Softwa- relosung fur das oben beschriebene Problem implementiert. Diese Software arbeitet mit einem konventionellen Algorithmus und ist seitdem im begleitenden produktiven Ein- satz. Unter einem konventionellen Algorithmus ist hier die Art der Implementierung zu verstehen. Sie baut auf der logischen Auswertung der einzelnen Gemusekisten auf und ist aus technischer Sicht durch verschachtelte if-else-Abfragen realisiert. Diese Losung hat gleich mehrere Nachteile. Zum einen wird der Entwicklungsaufwand in die Hohe getrieben, weil jede zusatzliche oder geanderte if-Abfrage Auswirkungen auf die bereits vorhandene Implementierung hat. Es ist schwer, hier eine geeignete Testuberdeckung zu finden, die gewahrleistet, dass keine ungewollten Nebenlaufigkeiten auftreten. Ein erhohter Entwick­lungsaufwand fuhrt zudem zu gesteigerten Kosten. Ein anderes Problem ist die mangelnde Flexibilitat fur Erweiterungen. Ein komplexes Konstrukt von verschachtelten Abfragen und Bedingungen, die grofitenteils zusatzlich untereinander Abhangigkeiten aufweisen, kann nur mit viel Muhe und Aufwand uberhaupt an neue oder geanderte Anforderungen angepasst werden.

Ziel dieser Ausarbeitung ist daher die Entwicklung eines besser strukturierten und leich- ter anderbaren Algorithmus, der zukunftig in die bereits vorhandene Software eingebaut werden kann.

3.2. Soll-Zustand

3.2.1. Geplante Integration

Die zurzeit vorhandene Ldsung setzt auf die Microsoft Windows Plattform und ist unter Windows XP bis Windows 7 lauffahig. Entwickelt wurde sie mit dem .NET-Framework in der Version 2.0. Im Hintergrund kommt eine Microsoft SQL Server 2005 Datenbank zum Einsatz, die alle anfallenden Stamm- und Bewegungsdaten erfasst. Konzipiert ist die­se Ldsung als Client-/Server-Anwendung. Der Fat-Client kann dabei auf beliebig vielen Clients installiert und genutzt werden, wenn der dedizierte Datenbankserver beispielswei- se uber ein firmeninternes Netzwerk erreichbar ist. Zusatzlich werden alle Benutzer des Systems durch verschiedene Logins voneinander unterschieden.

Urspruanglich gehoarte zu den Hauptzielen dieser schriftlichen Ausarbeitung, neben der Entwicklung eines neuen Algorithmus, auch die Integration in dieses bereits vorhandene Softwareprodukt. Es war das Ziel, die praktische Einsetzbarkeit der vorhandenen Software weiter zu erhohen, ohne viel Aufwand in die Portierung auf eine andere Plattform oder gar eine Neuentwicklung des Algorithmus zu investieren.

3.2.2. Erkannte Probleme

Wahrend der Bearbeitung sind allerdings Schwierigkeiten bei dieser Strategie aufgefallen. Diese Schwierigkeiten hatten mehrere Grande. Zum einen ist der vorhandene Zeitrahmen fur eine schriftliche Ausarbeitung stark beschrankt. Grofie Teile dieser Zeit wurden mit der notwendigen Einarbeitung in das Themengebiet der evolutionaren Algorithmen und der Klassifizierung des vorhandenen Problems investiert. Es wurde zudem schnell klar, dass es keinen Sinn macht, diese Einarbeitungszeit zu verkurzen, da sie die Grundlage fur die gesamte Ausarbeitung ist.

Zusatzlich ist bei der Analyse des vorhandenen Softwareprodukts aufgefallen, dass ei­ne Integration weit umfangreicher ist als zunachst angenommen. Der aktuell verwendete konventionelle Algorithmus bedient sich einer Vielzahl von Vereinfachungen der Problem- domane, damit die initiale Umsetzung gelingen konnte. Diese Vereinfachungen sollten in spaateren Versionen kontinuierlich abgebaut und der Algorithmus sowie das gesamte Softwareprodukt verbessert werden.

3.2.3. Neuer Losungsansatz

Aufgrund der erkannten Probleme war eine geaanderte Priorisierung notwendig. Statt den neu entwickelten Algorithmus in die bestehende Software zu integrieren, sollte die Aus- arbeitung die Grundlagen im Bereich der evolutionaren Algorithmen legen, um einen prototypisch entwickelten intelligenten Algorithmus zu konzipieren und zu implementie- ren. Auf Basis dieser Arbeit ist dann eine Integration in die bestehende Software zu einem spaateren Zeitpunkt moaglich.

Um die Ergebnisse des evolutionaaren Algorithmus darstellen und uaberpruafen zu koannen, ist die Entwicklung einer Testanwendung beschlossen worden. Sie uabernimmt das Ausfuah- ren des eigentlichen Algorithmus und das Speichern der dadurch erzeugten Ergebnisdaten. Diese konnen dann zusatzlich uber die Oberflache visualisiert werden, so dass zwischen verschiedenen Testlaufen ein einfacher Vergleich stattfinden kann.

3.3. Konkrete Problemdefinition

3.3.1. Beschreibung der Gemusekisten

Die Gemtisekisten sollen in der Art gefullt werden, dass sie keine Praferenzen der Kun- den verletzen und das die Gesamtmenge des gewunschten Inhalts nicht uber- oder un- terschritten wird. Die insgesamt zur Verfugung stehende Menge an Gemtise soll auf die gewuanschten Kisten verteilt werden.

3.3.2. Beschreibung der Kundenpraferenzen

Der Kunde kann zu seiner Gemuasekiste angeben, welche Gemuasesorten er nicht enthalten haben mbchte. Eine differenziertere Auswahl, z.B. durch die Angabe gewtinschter Mindest- und Maximalmengen, ist fur diese Ausarbeitung nicht vorgesehen. Praferenzen werden fur alle mbglichen Gemusesorten erfasst und in den zugehbrigen Objekten abgespeichert.

3.3.3. Definition der Einheiten

Eine Gemiisereihenfolge ist die festgelegte Reihenfolge aller zum Packen zur Verfligung stehenden Gemusesorten. Diese Gemiisereihenfolge ist in jedem Kistenobjekt vorhanden. In der einzelnen Kiste nicht vorhandenes Gemlise besitzt die Menge Null.

Die Grofie der Kisten wird in Eurobetragen angegeben. Um die Berechnung der Gemusekis- ten zu vereinfachen wird die Einheit des Gemuses ebenfalls in Euro angegeben. Diese Angabe enthalt implizit auch die Menge des Gemuses. Zur konkreten Zusammenstellung ist natlirlich noch eine Liste notig, welche den Wert eines Gemuses in Abhangigkeit vom Gewicht angibt. Da diese eigentliche Menge fur die Berechnung des Kisteninhalts durch den Algorithmus nicht notig ist, wurde auf die Erstellung einer solchen Liste verzichtet. Fur den Produktiveinsatz ist diese selbstverstandlich zu implementieren.

3.3.4. Definition der konkreten Mengen

Fur den Prototyp des Algorithmus werden Kisten zu 10,- EUR, 15,- EUR und 20,- EUR vorgesehen. Dies sind ubliche Kistengrofien bei dem Handel mit Abo-Kisten. Grofiere Mengen koinnen durch die Bestellung mehrerer Kisten erreicht werden.

Die Gemuisemengen werden in Mengen von Vielfachem von einem Euro angegeben. Eine Unterteilung in kleinere Mengen ist in diesem Prototyp noch nicht vorgesehen. Um die Gemusesorten auf die Kisten verteilen zu klnnen werden Packungsgrlfien festgelegt. Diese ergeben sich aus dem festgelegten Wert einer Packungseinheit und aus der vorhandenen Gesamtmenge an dem einzelnen Gemuse.

Es wird eine Gesamtmenge an zu befullenden Gemusekisten festgelegt. Die Gesamtmenge des zur Verfugung stehenden Gemuses ergibt genau den Wert der Summe aller bestellten Gemusekisten. Diese Vereinfachung zur Programmentwicklung soll in spateren Versionen natuirlich aufgehoben werden.

4. Entwicklungsumgebung

4.1. Auswahl der Programmiersprache

Die Auswahl der Programmiersprache wurde auf Basis der bereits bestehenden Softwa- relosung getroffen. Da eine Integration in das vorhandene Softwareprodukt zwar verscho- ben aber immer noch erklartes Ziel ist, sollte eine spatere Portierung oder Neuentwicklung vollstandig vermieden werden. Ausgewahlt wurde daher das .NET-Framework in der Ver­sion 4.0. Konkret entwickelt wurde in der Programmiersprache C#. Die aktuell verwendete Version 4.0 und die im Jahr 2006 benutzte Version 2.0 sind weitestgehend kompatibel zu- einander. In Version 4.0 neu eingefuhrte Sprachfunktionen konnen zwar nicht in der alteren Version genutzt werden, allerdings ist es kein Problem, die vorhandene Softwarelosung mit der neuen Framework-Version zu kompilieren. Das wurde in ausgiebigen Tests vor dem Start der Entwicklung sichergestellt.

4.2. Integrierte Entwicklungsumgebung (IDE)

Durch den Einsatz der Programmiersprache C# des .NET-Frameworks und durch die Ziel- plattform Microsoft Windows ist die Auswahl der Integrierten Entwicklungsumgebung stark eingeschrankt. Aufgrund von Erfahrungen in vergangenen Projekten sollte entweder die von Microsoft entwickelte IDE Visual Studio in der Version 2010 zum Einsatz kommen, oder auf die freie Software SharpDevelop in Version 4.2 gesetzt werden. Die Entscheidung ist letztendlich auf Visual Studio 2010 gefallen, da die bisherige Losung auch mit dieser Entwicklungsumgebung erstellt wurde. So wird zusatzlicher Aufwand fur den Wechsel der IDE bei der zuktinftigen Integration vermieden.

4.3. Datenbank

Fur die Uberprufung und die Visualisierung der Testergebnisse ist eine persistente Spei- cherung der anfallenden Daten zwingend erforderlich. Alle bei einem Testlauf anfallenden Daten mussen auch im Nachhinein abgerufen und angezeigt werden konnen. Zu diesem Zweck kommt die Datenbank Microsoft SQL Server Compact Edition zum Einsatz. Der Vorteil der Compact Edition liegt darin, dass kein eigenstandiger Datenbankser- ver zur Verfugung stehen muss. Trotzdem ist diese einfachere Version fur die bei den Testlaufen anfallenden Datenmengen gewappnet.

4.4. Versionsverwaltungssystem

Grundlage fur die reibungslose Zusammenarbeit der Projektteilnehmer und den Aus- tausch von Projektdateien ist ein System zur Versionsverwaltung. Eingesetzt wird die freie Software Subversion, die unter der Apache-Lizenz 2.0 steht. Zur Verfugung steht das Repository auf dem Entwicklungssystem des Projektteilnehmers Fabian Deitelhoff.

Ins Repository eingecheckt werden alle Dateien, die wahrend der Projektarbeit entstanden sind. Dazu zahlt vor allem der Quelltext der Anwendung, der als vollstandiges Visual Studio 2010-Projekt eingecheckt wurde, und die Dokumentation, die als LTEX-Dokument erstellt wird. Bis auf eine aktuelle Version der Dokumentation sind grundsatzlich alle Dateien ausgenommen, die durch irgendeinen Prozess generiert werden kounnen.

Zusatzlich dazu werden noch ausgewahlte Zwischenstande der Datenbank mit den gene- rierten Testdaten eingecheckt. Diese dienten wahrend der Entwicklungsphase der Verifi- kation von Aa nderungen am evolutionaaren Algorithmus.

4.5. Zusatzliche Zeichnungen

Fur Abbildungen und Zeichnungen wird das Programm Microsoft Visio in der Ver­sion 2010 eingesetzt. Das Programm steht uns uber das MSDN Software Center zur Verfugung, fur dass die Fachhochschule Sudwestfalen die sogenannte Acedemic Alliance Licence besitzt. So kann es von Studierenden kostenlos aus dem Portal heruntergeladen werden.

Mit dem Programm wurden in der Vergangenheit bei anderen Ausarbeitungen schon gute Erfahrungen gesammelt.

4.6. Eingesetzte Frameworks

Fundament fur die Entwicklung des evolutionaren Algorithmus ist das Microsoft .NET- Framework in Version 4.0. Die Common Language Runtime (CLR) ist die Laufzeitumge- bung des Frameworks und stellt einen Interpreter fur den standardisierten Zwischencode, der Common Intermediate Language (CIL), dar.

Alle weiteren Hauptmerkmale der Testanwendung, wie der Datenbankzugriff auf die Micro­soft SQL Compact Datenbank und die Anzeige der Diagramme, konnen mit Funktionen realisiert werden, die schon durch das .NET-Framework bereitgestellt werden. Weitere Frameworks sind daher fur die Entwicklung oder den Betrieb der Testanwendung nicht notwendig.

4.7. Arbeitsumgebung

4.7.1. Hardware

Die Entwicklung des evolutionaren Algorithmus und der Testanwendung fanden immer auf der gleichen Hardware statt. Das diente dazu, die Laufzeit nicht von der verwendeten Hardware abhaangig zu machen und damit die Vergleichbarkeit der Ergebnisse zu verbes- sern. Zum Einsatz kam ein Desktop-System, ausgestattet mit einem Intel i7 2007K, der uber vier physisch vorhandene Kerne mit je 3,5 GHz Taktfrequenz verfugt. Die Gesamt- grofie des verfugbaren Arbeitsspeichers betragt 16 GB.

4.7.2. Software

Um die Entwicklung vom Host-System zu trennen, wurde eine virtuelle Maschine verwen- det. Zum Einsatz kam hier die Software Virtual Box von Oracle in der Version 4.1.8. Auf dem Host- als auch auf dem Gastsystem kamen Windows 7 64 bit zum Einsatz. Zusatzlich zu den bereits beschriebenen Softwarekomponenten Visual Studio 2010 und dem .NET-Framework 4.0.

5. Losungsstrategie

5.1. Genaue Problemanalyse

Hinter der schriftlichen Ausarbeitung steht das konkrete praktische Problem, eine be- stimmte Gemusemenge auf eine bestimmte Anzahl von Gemusekisten verteilen zu mtissen. Die Menge an vorhandenem Gemuse ist dabei stark schwankend. Zum einen durch die konkrete Erntemenge und zum anderen durch die verfugbaren Gemusesorten, die je nach Jahreszeiten variieren. Die Anzahl an benotigten Gemusekisten unterliegt zwar ebenfalls Schwankungen, ist aber durch das angebotene Abo-System relativ konstant. Trotzdem ist es wunschenswert, so weit wie moglich von einer spezifischen Anzahl zu abstrahieren. Die benotigten Gemusekisten haben zusatzlich einen Maximalpreis, der nicht uberschritten werden darf, da er dem Kunden in Rechnung gestellt wird. Des Weiteren mussen Kun- denpraferenzen die Gemusesorten betreffend berucksichtigt werden.

Die fur die Implementierung des Algorithmus essentiellen Parameter sind demnach die Gesamtmenge an zur Verfugung stehenden Gemusesorten, die Anzahl der benotigten Gemuusekisten, der jeweils zugeordnete Maximalpreis, sowie die Prauferenzen der Kunden. Das macht schnell deutlich, wie stark gegensatzlich diese Parameter sind. Ab einer gewis- sen Anzahl an Gemusekisten und einer gewissen Unterschranke an vorhandenem Gemuse ist es nahezu unmoglich, alle Kundenpraferenzen zu erfullen. Andersherum bedarf es ei­ner gewissen Menge an uberschussigem Gemuse, um erfolgreich alle Kundenpraferenzen erfuullen zu kounnen.

Fur die Implementierung und den praktischen Einsatz mussen diese Parameter daher prio- risiert werden. Im Sinne der Kundenbindung haben die Prdferenzen auf die verschiedenen Gemusesorten die hbchste Prioritat. Es soll so gut wie mbglich vermieden werden, eine Gemusekiste mit einer Gemusesorte zu fullen, die vom Kunden nicht gewunscht ist. Erst danach soll der Preis der Gemusekiste eingehalten werden, indem sowohl Unter- als auch Uberschreitungen zu vermeiden sind. Grundsatzlich wird also davon ausgegangen, dass die Optimierung zum Vorteil der Kunden und zu Lasten des Erzeugers geht.

5.2. Bestimmung der Parameter

Aus der genauen Problemanalyse kounnen nun die konkreten Parameter fuur den Algo- rithmus abgeleitet werden. Zusdtzlich ist es moglich, Einschrankungen zu definieren, die sich entweder aus dem praktischen Einsatz und der Problemstellung ergeben oder fuur die vereinfachte Implementierung im ersten Prototypen gewuahlt wurden.

Da in der Praxis eine beliebige Anzahl von Gemusekisten notwendig sein kann, bei der Implementierung des Prototypen aber die Laufzeit und die Vergleichbarkeit gewdhrleistet sein muss, wurde eine fest definierte Anzahl von 500 Gemusekisten angenommen. Darauf sind die 20 Gemusesorten zu verteilen, die ebenfalls fest definiert und vorgegeben sind. Um die Komplexitat an dieser Stelle weiter zu reduzieren, wird keine Gewichtung der Gemusesorten nach Beliebtheit oder Wert vorgenommen.

5.3. Konventioneller Losungsansatz

Wie im Kapitel 3.1 schon kurz angedeutet, ist zurzeit eine Softwarelosung im Einsatz, die einen konventionellen Algorithmus verwendet. Dieser fullt die Gemlisekisten anhand der vorhandenen Gemusemengen und versucht, unter Einhaltung der Praferenzen, Gemusesor- ten zu tauschen. Aufgrund der hohen Komplexitat der Aufgabenstellung werden die Praferenzen in die drei Kategorien gerne, selten und gar nicht unterteilt. Basis fur diese Kategorisierung ist die Anzahl der Gemuasekisten eines Kunden beziehungsweise wie haufig eine Gemusesorte verwendet wurde. Die Praferenz selten gibt somit beispielsweise an, dass die so gewertete Gemusesorte bei jeder zweiten Bestellung entfernt wird. Das ist eine starke Abstraktion gegenuber der Praxis. Sie funktioniert zwar, soll aber durch einen besseren Ansatz ersetzt werden, der mehr Parameter berucksichtigen kann.

Aus der vergangenen Entwicklung der vorhandenen Softwarelosung ist bekannt, dass ein konventioneller Algorithmus, der alle Parameter berucksichtigen will, schnell so komplex und aufwandig zu implementieren ist, dass diese Herangehensweise in dieser schriftlichen Ausarbeitung nicht naher betrachtet wird. Es ist in jedem Fall das Ziel, einen konventio- nellen Algorithmus zu vermeiden.

5.4. Evolutionarer Losungsansatz

5.4.1. Evolutionares Vorgehen

Bei der Lasung von Problemen mit Hilfe von evolutionaren Algorithmen wird die Evoluti­on und damit die Veranderung von Lebewesen von Generation zu Generation als Vorbild genommen. Die Anderung ist dabei relativ gering und eine Entwicklung erst nach vielen Generationen bemerkbar. Hierbei wird als zuktinftiger Losungsraum eine zufallige Anord- nung der Allele anhand der vorhandenen Parameter festgelegt. Dieser Zustand entspricht der wenig perfekten Anfangspopulation zu Beginn der Evolution. Er wird im Zusammen- hang mit evolutionaren Algorithmen Startpopulation genannt. Diese Startpopulation wird nun in kleinen Bereichen wiederum zufallig verandert. Diese zufallige Veranderung kann zum Beispiel in Form einer Mutation oder einer Rekombination stattfinden. Eine Mutati­on entspricht dabei der zufalligen Anderung eines der Elemente des Losungsraums (in der Biologie werden diese Elemente Allele genannt) wie sie auch in der Biologie zum Beispiel durch Fehlentwicklung, Strahleneinwirkung oder sonstige zufallige und meist aufiere Ein- flusse entstehen kannen. Eine Rekombination entspricht der Veranderung beziehungsweise Verschmelzung verschiedener Elemente zu neu gestalteten Elementen. Dies entspricht der Verschmelzung durch Sexualitat beziehungsweise Vererbung in der Biologie.

Nur wenn diese durch Mutation oder Rekombination entstandenen neuen Elemente naher an dem zu erreichenden Loasungsraum liegen, alle sonstigen Bedingungen aber weiterhin erfullt sind, dann werden sie in die nachste Generation Ubernommen. Diese Uberprufung des Zustandes wird mit Hilfe einer fur den Algorithmus zu bestimmenden Fitnessfunktion festgelegt. Diese Fitnessfunktion bewertet den aktuellen Zustand der Generation. Die Auswahl der Elemente wird als Selektion bezeichnet. Viele Begriffe aus der biologischen Evolution werden zur Beschreibung von evolutionaren Algorithmen verwendet.

5.4.2. Allgemeine Packprobleme

Probleme, welche gerne und oft mit der Hilfe von evolutionaren Algorithmen gelost wer- den sind Packprobleme jeder Art. Dabei geht es darum, bestimmte Gegenstande nach be- stimmten Optimierungsbedingungen raumlich oder inhaltlich anzuordnen. Populare Pro- blemstellungen sind zum Beispiel das Rucksackproblem und das Problem beim Beladen von Laderaumen. Beim Rucksackproblem geht es darum, Gegenstande mit bestimmtem Gewicht und zugehorigem Wert derart in einen Rucksack zu packen, das mit minima- lem Gewicht unterhalb einer Hochstgrenze der grofitmogliche Gesamtwert gepackt wird. Beim Beladen von Laderaumen geht es entsprechend um eine optimierte Anordnung von mehreren Paketen innerhalb eines Laderaumes. So bestimmt z.B. die DIN 70020-1 bezie- hungsweise ISO 3832 das Volumen eines Auto-Kofferraums nach der Anzahl von Quadern einer bestimmten Grofie (5cm x 20cm x 10cm, entsprechend 1 Liter), die dieser Koffer- raum maximal aufnehmen kann. In der Praxis bedienen sich die Autohersteller bei dieser Berechnung evolutionarer Algorithmen [1].

Ein weiteres Beispiel, welches einen evolutionaren Algorithmus beim Losen eines Pack- problems verwendet, ist die Losung eines Programmierwettbewerb zur Anordnung von n Kreisscheiben innerhalb einer weiteren Scheibe. Die Grofie der umschliefienden Scheibe sollte dabei minimiert werden, der Radius der umschlossenen Kreisscheiben steigt mit deren Anzahl und ist jeweils gleich n. Dieser Programmierwettbewerb fand 2009 statt [1].

5.4.3. Besonderheiten der Aufgabenstellung

Bei der Befullung der Gemusekisten sind mehrere Kisten in Abhongigkeit voneinander optimal zu bepacken. Dies kann nach Prof. Dr. Marc Pfetsch [2] als mehrdimensionales Rucksackproblem aufgefasst werden. Somit handelt es sich bei dem zu losenden Problem um eine NP-Vollstandigkeit [3], welche sich vermutlich nicht effizient losen lasst.

5.4.4. Geschlossener LOsungsraum

Weiterhin kann bei dem bestehenden Problem keine Kiste aus der Population genommen werden, wenn diese nicht optimal gefullt ist. Die Gesamtmenge des Inhaltes darf nicht verandert werden. Es handelt sich bei der zu bestimmenden Losung um einen geschlosse- nen Losungsraum, welcher nur durch Umsortierung optimiert werden kann.

5.5. Gewahlte Strategie

Als Strategie zur Losung des Packproblems fur die Gemosekisten durch einen evolutio­naren Algorithmus wurde folgende Vorgehensweise gewahlt:

- Lineares oder zufolliges Befullen aller Kisten mit dem zur Verfugung stehenden Gemuse. Es werden mehrere Arten der Befullung implementiert, um durch Testlaufe zu ermitteln, welche Art der Generierung der Startpopulation das beste Ergebnis liefert.
- Zufallige Auswahl von zwei Gemtisekisten und Austausch von Gemlisesorten zwi- schen diesen beiden Kisten. Dieses Auswahlen wird fur alle Kisten vorgenommen, doppelte Auswahl einer Kiste ist dabei nicht vorgesehen.
- Bewertung der Kisten mit der Fitnessfunktion vor und nach dem Austausch des Gemuses. Ubernahme dieser beiden Kisten in die nachste Generation nur, wenn sich der Fitnesswert verbessert.
- Wiederholtes durchlaufen dieser Punkte uber eine festgelegte Anzahl von Genera- tionen.

Bei der Befullung werden zunachst vier verschiedene Vorgehensweisen implementiert:

1. Die in Einheiten (siehe Kapitel 3.3.4) aufgeteilten Gemusesorten werden in der vor- handenen Reihenfolge in die Kisten gefullt. Wird die letzte Kiste erreicht obwohl das Gemuse noch nicht komplett verteilt ist, so wird wieder bei der ersten Kiste mit fullen begonnen. Diese ersten Kisten enthalten somit die doppelte Menge von diesem Gemuse. Ist ein Gemuse verteilt, so wird mit der Verteilung des folgenden Gemuses wieder bei der ersten Kiste begonnen. Durch diese Art der Verteilung soll erreicht werden, dass Kisten unterschiedlicher Fullgrade entstehen. Auf den angestrebten Wert der einzelnen Kisten wird keine Rucksicht genommen.
2. Die Befullung geschieht ahnlich wie im zuvor beschriebenen Punkt. Allerdings wird bei kompletter Verteilung eines Gemuses mit der Verteilung des folgenden nicht bei der ersten Kiste begonnen, sondern bei der als nachstes folgenden. Dadurch soll erreicht werden, dass die Kisten gleichmafiig gefullt werden.
3. Jede Gemuseeinheit wird einer zufallig ausgewahlten Kiste zugewiesen. Die Gemuse- einheiten werden dabei in der Reihenfolge ihrer Speicherung abgearbeitet. Dies soll eine muglichst zufullige Verteilung der Gemusesorten auf alle Kisten ermoglichen.
4. Um die Zufalligkeit der Verteilung noch weiter zu erhuhen wird zusatzlich zur zufulligen Kistenauswahl die zu verteilende Gemuseeinheit zufallig ermittelt.

Zum Austausch von Gemusesorten zwischen den zufallig ausgewahlten Kisten werden funf verschiedene Rekombinationen implementiert:

1. Es wird eine zufallige Stelle in der Gemusereihenfolge der Kisten ausgewahlt. Das Gemuse an dieser Stelle wird komplett getauscht. Ist in einer Kiste eine der Gemuse­sorten nicht vorhanden, so entspricht dies einem umpacken von einer Kiste in die andere.
2. Es werden zwei Gemusesorten getauscht, die an verschiedenen Stellen in der Rei­henfolge stehen.
3. Wieder wird eine zufullige Stelle in der Gemusereihenfolge ausgewahlt. Bei diesem sogenannten 1-Punkt Crossover (siehe [4] Seite 124) werden alle Gemusesorten ab der gewuhlten Stelle ausgetauscht. Die Gemusesorten bis zu diesem Punkt werden nicht verandert.
4. Der Tausch erfolgt ebenfalls mit einem 1-Punkt Crossover. Zusutzlich wird nach dem Crossover eine zufullige Menge Gemuse an einer zufallig ausgewahlten Stelle in der Reihenfolge ausgetauscht. Diese zusutzliche Mutation ermoglicht das Aufteilen von Gemusemengen.
5. Bei der letzten Rekombinationsstrategie wird ermittelt, ob in einer Kiste eine Pra- ferenz verletzt ist. Ist dies der Fall, so wird gezielt ein die Praferenz verletzen-des Gemuse getauscht.

[...]

Details

Seiten
48
Jahr
2012
ISBN (eBook)
9783656415176
ISBN (Buch)
9783656415725
Dateigröße
1.4 MB
Sprache
Deutsch
Katalognummer
v197565
Institution / Hochschule
Fachhochschule Südwestfalen; Abteilung Iserlohn
Note
1,0
Schlagworte
Informatik Angewandte Angewandte Informatik Demeter Gemüsehof Evolutionärer Algorithmus Packproblem Erntemengen Evolution Allele Softcomputing Fitnesswert Rucksackproblem Nebenbedingungen

Autoren

Teilen

Zurück

Titel: Evolutionärer Algorithmus zur Aufteilung von Erntemengen auf kundenspezifische Packungseinheiten