In einer Zeit, in der modernste Technologie allgegenwärtig und alltäglich geworden ist, verändern sich Märkte in rasanter Geschwindigkeit. Das Internet ermöglicht schnellsten Informationsaustausch und schnellste Reaktionsfähigkeit. Damit werden Märkte dynamischer und Wettbewerbsvorteile können von Konkurrenten rasant aufgeholt werden. Vor kurzer Zeit waren nur Branchen betroffen, die hochtechnisiert waren. Heute stehen alle Branchen und Märkte im Einfluss des Internets. Damit nicht genug, das Internet ist mobil geworden, Blackberry, IPhone oder GPRS-Karte gehören zur Grundausstattung eines modernen Geschäftsmannes. Damit wächst für Unternehmen der Druck, Wettbewerbsvorteile auszubauen und zu halten. In Unternehmen mit eigener Produktion aber auch im Dienstleistungsbereich werden Schnittstellen zur Kommunikation zwischen Unternehmen immer wichtiger. Innerhalb von Unternehmen wurde in den letzen Jahren kräftig „aufgeräumt“. Effizienzsteigerung, Prozessoptimierung, oder „Lean Production“ sind nur einige Schlagwörter, die zu einer Verschlankung der Unternehmen geführt haben. Prozesse oder ganze Teile des Unternehmens wurden outgesourced, viel Potential für Verbesserungen ist nicht geblieben, außer an den Schnittstellen zwischen Unternehmen. Dort ist noch einiges an Verbesserungspotential vorhanden. Eine unternehmensübergreifende Kommunikation kann zahlreiche Vorteile mit sich bringen. Dabei können Unternehmen sowohl im Rahmen der Kooperation, der Coopetition5 oder einfach als Lieferant und Kunde miteinander zusammenarbeiten und ihre Prozesse optimieren. Die Kommunikation läuft nicht nur in eine Richtung, sondern auch gegenläufig und erstreckt sich über viele Unternehmen entlang einer Lieferkette hinweg. Eine solche Lieferkette ist meist eine Wertschöpfungskette, da jedes beteiligte Unternehmen einen Mehrwert in seiner Stufe der Kette generiert. Die Koordination und Kommunikation in einer solchen Kette umfasst ein ganzes Fachgebiet in der Betriebswirtschaftslehre. Dieses Fachgebiet hat sich zu einem Managementkonzept, genannt „Supply Chain Management“, entwickelt. Es hat als Aufgabe die Koordination der einzelnen Unternehmen, um die Wertschöpfungskette zu optimieren. Dies ist auch das Thema dieser Fallstudie.
Inhaltsverzeichnis
Abbildungsverzeichnis
Tabellenverzeichnis
Abkürzungsverzeichnis
1 Einleitung
1.1 Problemstellung und Zielsetzung
1.2 Vorgehensweise
1.3 Notenverrechnung
2 Evolutionäre Algorithmen
3 Supply Chain Management
4 Theoretische Abhandlung der Genetischen Algorithmen
4.1 Selektion
4.2 Rekombination
4.3 Mutation
5 Umsetzung des Genetischen Algorithmus
5.1 Selektion
5.2 Rekombination
5.3 Mutation
5.4 Grafische Benutzeroberfläche
6 Evaluation & Optimierung der Genetischen Operationen
6.1 Selektion
6.2 Rekombination
6.3 Mutation
6.4 Optimierungs-Szenario für den Grundalgorithmus
7 Dezentraler Ansatz
7.1 Varianten eines Dezentralen Ansatzes
7.2 Struktogramme der umgesetzten Ansätze
7.3 Evaluation des Dezentralen Ansatzes
8 Fazit
Anhang
Anhang 1: Aufgabenverteilung
Anhang 2: Ergebnisse der ersten Phase
Anhang 2: Ergebnisse der zweiten Phase
Quellenverzeichnis
Abbildungsverzeichnis
Abb. 1: Prinzipieller Ablauf Evolutionärer Suchverfahren
Abb. 2: Aufbau einer Supply Chain
Abb. 3: Grafische Darstellung der Rekombination
Abb. 4: Rekombination - Einpunktkreuzung
Abb. 5: Rekombination - Mehrpunktkreuzung
Abb. 6: Rekombination - Gleichmäßige Kreuzung
Abb. 7: Bit-Flipping
Abb. 8: Struktogramm ‚Bit-Flipping’
Abb. 9: Swap-Mutation
Abb. 10: Struktogramm ,Swap-Mutation’
Abb. 11: Struktogramm ‚Ablauf des Evolutionären Algorithmus’
Abb. 12: Quelltext ‚Erzeugung der Binärmatrix’
Abb. 13: Zusammenspiel der genetischen Operationen
Abb. 14: Roulette-Rad mit Sektorenzuweisung je Individuum entsprechend der Fitness
Abb. 15: Struktogramm ‚Ablauf der Selektion’
Abb. 16: Übertragung int[][] in String[]
Abb. 17: Erzeugung der Kindgeneration durch zufällige Trennung der Elternindividuen
Abb. 18: Struktogramm ‚Ablauf der Rekombination’
Abb. 19: Struktogramm ‚Ablauf der Mutation’
Abb. 20: Screenshot der grafischen Benutzeroberfläche
Abb. 21: Bestenselektion
Abb. 22: Struktogramm ‚Bestenselektion’
Abb. 23: Werteverlauf Bestenselektion (Instanz 1 Phase 1, 100 Generationen)
Abb. 24: Wettkampfselektion
Abb. 25: Struktogramm ‚Wettkampfselektion’
Abb. 26: Werteverlauf Wettkampfselektion (Instanz 1 Phase 1, 100 Generationen)
Abb. 27: Einfache Rekombination mit fester Trennstelle in der Mitte
Abb. 28: Struktogramm ‚Einfache Rekombination mit fester Trennstelle in der Mitte’
Abb. 29: Werteverlauf Rekombination - Feste Trennstelle Mitte (Instanz 1 Phase 1, 1000 Generationen)
Abb. 30: Gleichmäßige Rekombination
Abb. 31: Struktogramm ‚Gleichmäßige Rekombination’
Abb. 32: Rekombination mit zwei zufälligen Trennstellen - Ablauf
Abb. 33: Struktogramm ‚Rekombination mit zwei zufälligen Trennstellen’
Abb. 34: Werteverlauf Rekombination - Zwei Trennstellen (Instanz 1 Phase 1, 1000 Generationen)
Abb. 35: Flip-Mutation an einer Stelle
Abb. 36: Struktogramm ‚Flip-Mutation an einer Stelle’
Abb. 37: Werteverlauf Flip-Mutation an einer Stelle (Instanz 1 Phase 1, 100 Generationen)
Abb. 38: Flip-Mutation an zwei Stellen
Abb. 39: Struktogramm ‚Flip-Mutation an zwei Stellen’
Abb. 40: Werteverlauf Flip-Mutation an zwei Stellen (Instanz 1 Phase 1, 100 Generationen)
Abb. 41: Swap-Mutation
Abb. 42: Struktogramm ‚Swap - Mutation’
Abb. 43: Werteverlauf Swap-Mutation (Instanz 1 Phase 1, 100 Generationen)
Abb. 44: Struktogramm ,Bewerten() - Border 1’
Abb. 45: Struktogramm ,Selektion - Border 1’
Abb. 46: Struktogramm ,Bewerten() - Border 2'
Abb. 47: Werteverlauf Border 1 (Instanz 1 Phase 1, 100 Generationen)
Abb. 48: Werteverlauf Border 1 (Instanz 1 Phase 1, 100 Generationen)
Abb. 49: Abweichungsanalyse Optimierungs-/ Grundalgorithmus und X-Men (Instanzen Phase 1)
Tabellenverzeichnis
Tab. 1: Vor- und Nachteile eines Evolutionären Algorithmus
Tab. 2: Gegenüberstellung Roulette- und Bestenselektion (Instanz 1 Phase 1)
Tab. 3: Gegenüberstellung Roulette- und Bestenselektion (Instanz 1 Phase 2)
Tab. 4: Gegenüberstellung Roulette- und Wettkampfselektion (Instanz 1 Phase 1)
Tab. 5: Gegenüberstellung Roulette- und Wettkampfselektion (Instanz 1 Phase 2)
Tab. 6: Gegenüberstellung Besten- und Wettkampfselektion
Tab. 7: Gegenüberstellung Besten- und Wettkampfselektion (Instanz 1 Phase 2)
Tab. 8: Gegenüberstellung Rekombination mit variabler/ fester Trennstelle
Tab. 9: Gegenüberstellung Rekombination mit variabler Trennstelle/ gleichmäßige Rekombination
Tab. 10: Gegenüberstellung Einfache/ Zweifache Rekombination mit einer/ zwei variablen Trennstellen
Tab. 11: Gegenüberstellung Flip-Mutation mit Mutationswahrsch./ Flip-Mutation an einer Stelle
Tab. 12: Gegenüberstellung Flip-Mutation mit Mutationswahrsch./ Flip-Mutation an zwei Stellen
Tab. 13: Gegenüberstellung Flip-Mutation mit Mutationswahrsch./ Swap-Mutation
Tab. 14: Kombinationsmöglichkeiten für Szenarien
Tab. 15: Übersicht über ausgewählte Szenarien
Tab. 16: Ergebnisse der ersten zehn Instanzen mit verschiedenen Szenarien
Tab. 17: Vergleich dezentrale Ansätze (Phase 1, Instanz 1)
Tab. 18: Abweichungsanalyse für Phase 1
Tab. 19: Leistungsvergleich
Tab. 20: Abweichungsanalyse für Phase 2
Abkürzungsverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
1 Einleitung
In einer Zeit, in der modernste Technologie allgegenwärtig und alltäglich geworden ist, verändern sich Märkte in rasanter Geschwindigkeit. Das Internet ermöglicht schnellsten Informationsaustausch und schnellste Reaktionsfähigkeit. Damit werden Märkte dynamischer und Wettbewerbsvorteile können von Konkurrenten rasant aufgeholt werden. Vor kurzer Zeit waren nur Branchen betroffen, die hochtechnisiert waren. Heute stehen alle Branchen und Märkte im Einfluss des Internets. Damit nicht genug, das Internet ist mobil geworden, Blackberry1, IPhone2oder GPRS-Karte3 gehören zur Grundausstattung eines modernen Geschäftsmannes. Damit wächst für Unternehmen der Druck, Wettbewerbsvorteile auszubauen und zu halten. In Unternehmen mit eigener Produktion aber auch im Dienstleistungsbereich werden Schnittstellen zur Kommunikation zwischen Unternehmen immer wichtiger.
Innerhalb von Unternehmen wurde in den letzen Jahren kräftig „aufgeräumt“. Effizienzsteigerung, Prozessoptimierung, oder „Lean Production“4 sind nur einige Schlagwörter, die zu einer Verschlankung der Unternehmen geführt haben. Prozesse oder ganze Teile des Unternehmens wurden outgesourced, viel Potential für Verbesserungen ist nicht geblieben, außer an den Schnittstellen zwischen Unternehmen. Dort ist noch einiges an Verbesserungspotential vorhanden. Eine unternehmensübergreifende Kommunikation kann zahlreiche Vorteile mit sich bringen. Dabei können Unternehmen sowohl im Rahmen der Kooperation, der Coopetition5 oder einfach als Lieferant und Kunde miteinander zusammenarbeiten und ihre Prozesse optimieren. Die Kommunikation läuft nicht nur in eine Richtung, sondern auch gegenläufig und erstreckt sich über viele Unternehmen entlang einer Lieferkette hinweg. Eine solche Lieferkette ist meist eine Wertschöpfungskette, da jedes beteiligte Unternehmen einen Mehrwert in seiner Stufe der Kette generiert. Die Koordination und Kommunikation in einer solchen Kette umfasst ein ganzes Fachgebiet in der Betriebswirtschaftslehre. Dieses Fachgebiet hat sich zu einem Managementkonzept, genannt „Supply Chain Management“, entwickelt. Es hat als Aufgabe die Koordination der einzelnen Unternehmen, um die Wertschöpfungskette zu optimieren. Dies ist auch das Thema dieser Fallstudie.
1.1 Problemstellung und Zielsetzung
Optimierungsprobleme im Bereich des Supply Chain Managements sind aufgrund ihrer unzähligen Variablen oft hoch komplex. Ob Tourenplanungen oder Kostenoptimierung: mathematische Verfahren, die sich in vielen Problemstellungen bewährt haben, stoßen hierbei an ihre Grenzen. An der Theorie hapert es dabei nicht, die meisten Problemstellungen lassen sich lösen, der kritische Faktor ist jedoch die Zeit. Trotz hoch modernen Rechenzentren mit Prozessoren, die sich jährlich übertreffen und einer „Top - 100 - Liste“ von Supercomputern, die ständig aktualisiert werden muss, ist Rechenzeit bei der Lösung vieler Optimierungen der Faktor, an der die Anwendung von herkömmlichen Verfahren scheitert. Viele Problemstellungen würden über einhundert Jahre Rechenzeit benötigen, damit ist die Anwendung herkömmlicher Verfahren unmöglich. Eine Lösungsmöglichkeit für diese Probleme sind Heuristiken, die mit verschiedenen Verfahren versuchen, eine gute Lösung zu finden. Verblüffend ist dabei, dass sich ab und zu nicht nachvollziehen lässt, wie die Lösung entstanden ist. Es ist aber beweisbar, wie gut eine solche Lösung im Vergleich zu anderen bekannten Lösungen ist. In diesem Bereich lassen sich Evolutionäre Algorithmen einsetzen, die im nachfolgenden Kapitel näher beschrieben werden.
Diese Fallstudie verfolgt das Ziel, die Möglichkeiten Evolutionärer Algorithmen aufzuzeigen, um ein betriebswirtschaftliches Optimierungsproblem aus dem Bereich Supply Chain Management zu lösen.
1.2 Vorgehensweise
Nach einer Einführung in die Welt der evolutionären Algorithmen wird das Supply Chain Management näher dargestellt. Die wesentlichen Bestandteile von Evolutionären Algorithmen, also Mutation, Rekombination und Selektion, werden im darauf folgenden Kapitel detailliert erklärt. Anschließend wird die praktische Umsetzung eines betriebswirtschaftlichen Optimierungsproblems aus dem Bereich Supply Chain Management mit Hilfe evolutionärer Algorithmen aufgezeigt. Dabei werden die zuvor theoretisch erklärten Bestandteile evolutionärer Algorithmen angewendet. Eine solche Anwendung macht eine nachfolgende Optimierung notwendig, um die erzielten Ergebnisse zu verbessern. Es wird die Anwendung verschiedener Optimierungsvarianten und deren Ergebnisse präsentiert. Im letzten Kapitel wird ein dezentraler Ansatz vorgestellt, mit dem sich ein solches Optimierungsproblem ebenfalls lösen lässt, allerdings ohne zentrale Koordination, d.h. ohne die Berücksichtigung der Gesamtkosten.
1.3 Notenverrechnung
Bezüglich der Notenverrechnung möchten wir Einzelnoten ausgewiesen bekommen. Bitte beachten Sie hierzu die Anlage6, in der die Einzelleistungen dargestellt werden.
2 Evolutionäre Algorithmen
Das Verfahren:
Der Evolutionäre Algorithmus ist ein Optimierungsverfahren7, das bereits zu Beginn der sechziger Jahre von verschiedenen Forschergruppen entwickelt wurde.8Beim EA werden die Abläufe einer biologischen Evolution als Vorbild gesehen und in einem Algorithmus benutzt. Das Ziel eines EA ist es, eine möglichst gute Lösung zu einem bestimmten Problem, also unter bestimmten Bedingungen, zu finden. In der Natur entsprechen diese Bedingungen bzw. Probleme den Lebensbedingungen an die sich ein Individuum anpassen muss. Die optimale Lösung stellt in der Natur ein Individuum dar, welches sich sehr gut an die Bedingungen angepasst hat und somit überlebensfähig ist.
Die Natur greift hierbei auf drei biologische Prinzipien zurück, um aus einer Startpopulation Individuen zu entwickeln, die bestmöglich an die Bedingungen angepasst sind. Dieser Vorgang lässt sich so auch auf einen EA übertragen:9
- Mutation/Nachkomme(n):1011
Die Mutation des Erbgutes soll dazu dienen, Alternativen und Varianten zu erzeugen. Dies entspricht beim EA der Überwindung des lokalen Optimums, um die Chance zu steigern, ein globales Optimum zu finden.
- Rekombination/Nachkomme(n):1213
Bei der Rekombination werden die Gene zweier Individuen nach einem vordefinierten Schema miteinander kombiniert. Welche Individuen für diesen Vorgang verwendet werden, ist jedoch dem Zufall überlassen. Bei der Rekombination im Rahmen eines EAs werden Populationen miteinander kombiniert, um hieraus neue Populationen zu erzeugen.
- Selektion/Partnerwahl:14
In der Natur legt die Selektion fest, welche Individuen sich stärker vermehren. Beim EA beinhaltet die Selektion die Auswahl der Individuen, die später im Rahmen der Rekombination verstärkt gebraucht werden.
Der Ablauf eines EA lässt sich somit in folgendem Schema darstellen:15
Abbildung in dieser Leseprobe nicht enthalten
Abb. 1: Prinzipieller Ablauf Evolutionärer Suchverfahren16
Anwendungsgebiete
EA dienen der Lösung von Optimierungsproblemen bei denen traditionelle Optimierungsverfahren auf Grund von Nichtlinearitäten17und Diskontinuitäten18zur Findung einer optimalen Lösung nicht mehr benutzt werden können.19
Vor- und Nachteile
Abbildung in dieser Leseprobe nicht enthalten
Tab. 1: Vor- und Nachteile eines Evolutionären Algorithmus
Teilbereiche
Zu dem Themengebiet der EA zählen auch die Themengebiete der genetischen Programmierung, genetische Algorithmen, Evolutionsstrategien und der Evolutionären Programmierung. Diese Verfahren haben alle das Prinzip der biologischen Evolution zum Vorbild und dienen alle der Findung von Lösungen von Optimierungsproblemen.
3 Supply Chain Management
Die aktuelle Situation für Unternehmen auf gesättigten Märkten zwingt sie zur Konzentration auf ihre Kernkompetenzen. Dafür ist vor allem bei Produktionsunternehmen eine enge Verflechtung und Vernetzung mit und zwischen Zulieferbetrieben und Betrieben, die Waren abnehmen, erforderlich. Diese Koordinationsaufgabe nennt sich Supply Chain Management und bedeutet konkret die Planung, Koordination und Steuerung der Material- und Informationsströme in Unternehmensnetzwerken.20
Supply Chain
Der Ausdruck „Supply Chain“ kann mit den Begriffen „logistische Kette, Lieferkette, Versorgungskette oder Leistungswirtschaft“ übersetzt werden. In der Literatur ist häufig die Bezeichnung „Wertschöpfungskette“ zu finden. Die Supply Chain beschreibt den Weg eines Produktes oder einer Dienstleistungen innerhalb mehrerer Unternehmen von der Herstellung des Produktes mit den einzelnen Zwischenschritten entlang einer Kette von Produktionsstufen bis zum Endverbraucher.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2: Aufbau einer Supply Chain21
Wesentlich ist dabei, dass während der Produktion des Produktes oder der Ausführung der Dienstleistung ein Mehrwert gegenüber dem vorhergegangenen Produktionsschritt entsteht. Daher der Name Wertschöpfungskette.
Die Idee und das Konzept einer solchen Kette wurde als erstes von dem Wirtschaftswissenschaftler Michael E. Porter im Jahr 1985 vorgestellt.22 Warenströme fließen in einer Supply Chain vom Hersteller zu den Endverbrauchern, Geldströme fließen in die Gegenrichtung. Dabei ist zu beachten, dass es zusätzliche Informationsströme gibt, die die Waren - und Geldströme begleiten wie z.B. Lieferscheine. Eine Supply Chain muss nach Auffassung von Porter von einer „Value Chain“ abgegrenzt werden. Bei einer „Value Chain“ handelt es sich um eine Kette der Organisation innerhalb eines Unternehmens, eine „Supply Chain“ erstreckt sich über mehrere Unternehmen hinweg. Eine Supply Chain ist also ein virtuelles Organisationsgebilde über Unternehmen hinweg. Der Extremfall einer Supply Chain geht von der Rohstoffgewinnung bis zum Recycling eines Produktes.
Supply Chain Management
Der Ausdruck des Supply Chain Management, meist abgekürzt mit „SCM“, wird analog zur Supply Chain mit „Versorgungskettenmanagement“ oder „Lieferkettenmanagement“ übersetzt.
Ziel des SCM ist die nahtlose Integration der einzelnen Partner einer Lieferkette untereinander mit dem Hauptziel der Steigerung der Effektivität und Effizienz in der gesamten Lieferkette. SCM bedeutet weiter die Unterstützung und Optimierung von Informations- und Kommunikationsflüssen unter den beteiligten Unternehmen zur Abstimmung von Warenbewegungen. SCM ist ein Managementkonzept, das sich mit logistischen Fragestellungen beschäftigt.23
Abgrenzung zur Logistik
Die Begriffe SCM und Logistik werden oft synonym verwendet, haben genau genommen aber unterschiedliche Bedeutung. Die Logistik befasst sich mit gleichen Themen wie das SCM, der Unterschied liegt darin, dass sich die Logistik primär mit den Warenflüssen etc. eines Unternehmens befasst, das SCM jedoch unternehmensübergreifend agiert.
Supply Chain Management wird als ein neues Teilgebiet der Betriebswirtschaftslehre angesehen, das sich über die Grenzen des Betriebes hinaus erstreckt und dabei nicht nur die Logistik, sondern auch alle anderen Felder der Betriebswirtschaftslehre wie z. B. Marketing und Controlling beinhaltet.
Zielsetzungen des SCM
Zusätzlich zu den genannten Hauptzielen des SCM werden weitere Zielsetzungen verfolgt:24 SCM kann dazu beitragen, Lieferzeiten zu reduzieren und damit die Kundenzufriedenheit zu steigern. Verbesserte Kommunikation zwischen den Partnern in der Supply Chain kann eine schnellere Anpassung an Marktveränderungen und damit Kostenvorteile ermöglichen. Ein sehr wichtiger Punkt ist die Reduzierung der Lagerbestände der Beteiligten der Supply Chain und die Vermeidung von Lieferengpässen. Weiter gilt es den „Peitscheneffekt“25zu verhindern, der Schwankungen von Bestellmengen und die damit verbundene unerwünschte Aufschaukelung von Bestellmengen entlang einer Lieferkette beschreibt. Als fast selbstverständlich kann angesehen werden, dass durch Optimierung des Gesamtprozesses über mehrere Stufen hinweg große Kostenvorteile erzielt werden können. Insgesamt soll eine Win-Win-Situation26für alle Beteiligten entstehen.
SCM - Modelle
In der Literatur27finden sich verschiedene Modelle, nach denen eine Wertschöpfungskette organisiert werden kann.
Das Modell der zentralisierten Supply-Chain benötigt eine neutrale Instanz, die die Koordination der Wertschöpfungskette übernimmt. Diese Stelle sammelt von den beteiligten Unternehmen Informationen wie Kapazitätsbelegungen, Auftrags- und Materialbestände. Die Zentrale führt die zentrale Planung durch und stellt den beteiligten Unternehmen die Ergebnisse zur Verfügung.
Beim dominierten Modell wird die Koordination der Material- und Informationsflüsse in Anlehnung an das zentralisierte Modell umgesetzt. Allerdings übernimmt hier die Koordinationsaufgabe ein Teilnehmer der Supply Chain, meist der stärksten Partner der Wertschöpfungskette, also der Hersteller des Endprodukts.
Das koordinierte Modell basiert auf verteilter Koordination, wobei die Planung dezentral erfolgt. Dabei stellen sich die Teilnehmer der Supply Chain die benötigten relevanten Informationen gegenseitig zur Verfügung. Erforderliche Informationen sind z.B. freie Kapazitäten, Lagerbestände, Bedarfsprognosen und Markteinschätzungen.
Das SCOR Referenzmodell für SCM
Supply-Chain-Lösungen eignen sich für die unterschiedlichsten Unternehmensbereiche und Branchen. Soll eine solche Lösung erfolgreich werden, ist ein gemeinsames Prozessverständnis28bei den Partnern unabdingbar. Hier setzt das vom Supply Chain Council (SCC)29entwickelte Supply-Chain-Operations-Reference-Modell (SCOR)30an. Es definiert die wesentlichen Geschäftsprozesse einer Supply Chain und verknüpft diese mit verwendbaren Erfolgsmethoden (Best Practices) und weiteren Informationen. Das SCOR - Modell besteht aus vier Leveln, die Prozesse und Schnittstellen weiter definieren.
4 Theoretische Abhandlung der Genetischen Algorithmen
4.1 Selektion
Nachdem die Anfangspopulation erzeugt und hinsichtlich ihrer Fitness bewertet wurde, erfolgt als erste Phase der Generationserzeugung die Auswahl der Eltern, welche zur Rekombination der Nachkommen verwendet werden. Da von der Selektion entscheidend die Bandbreite der entstehenden Lösungen abhängt, ist es wichtig, bereits hier einen guten Algorithmus anzusetzen.31 Hierbei gibt es verschiedene Möglichkeiten und Konzepte, von welchen nachfolgend einige vorgestellt werden.
Wird die Population der nächsten Elternindividuen erstellt, so soll einerseits eine möglichst breite Lösungsvielfalt erreicht werden, andererseits sollten die tatsächlich besten Individuen aufgenommen werden. Hier kann es mitunter zu Konflikten kommen, weshalb eine reine Auswahl der Besten zu einem Verlust der Vielfalt führt. Man muss sich also entscheiden, ob man die besten Individuen auswählt oder bei der zufälligen Auswahl die Wahrscheinlichkeit auf der Fitness der Individuen basieren lässt.
Selektiert zu werden sollte jedoch allen Elternindividuen zumindest möglich sein, da ansonsten der Aufwand ihrer Verwaltung fragwürdig ist. Dies kann entweder erreicht werden, indem jedes Eltern-Individuum garantiert mindestens einen Nachkommen hat oder, um Selektionsdruck zu erzeugen, jedes Elternteil eine individuelle Selektionswahrscheinlichkeit hat.
Zum anderen kann man sich dazu entscheiden, die Eltern durch die Kinder komplett zu ersetzen oder die Eltern zusätzlich zur neuen Kindgeneration beizubehalten und ebenfalls mit in die Selektion aufzunehmen. Von „überlappenden Populationen“ spricht man, wenn z.B. die neue Population aus allen Kindern und dem besten Elternindividuum besteht.32
Besten-Selektion
Am einfachsten und effektivsten erscheint die Selektion der besten Individuen einer jeden Generation. Dazu erfolgt zuerst eine Bewertung der Fitness der Eltern, anschließend wird ein festgelegter Teil dieser Elterngeneration zur Rekombination ausgewählt, z.B. die bessere Hälfte.
Bei diesem Verfahren erreicht man schnell optimierte Werte, jedoch ist dies mit einigen Problemen verbunden. Zahlreiche Untersuchungen haben gezeigt, dass die so erzeugten Populationen sehr schnell konvergieren33 und zum Ende einer Iteration immer das gleiche Elternindividuum genutzt wird.34 Liegt ein lokales Optimum vor, kann keine Verbesserung mehr erreicht werden. Deshalb führt die Besten-Selektion nicht zwingend zu den besten Ergebnissen.
Wettkampfselektion
Die Wettkampf oder auch Tunierselektion ist weniger zielorientiert als die Besten-Selektion. Da bei diesem Verfahren auch schlechtere Lösungen eine Chance haben, liegt eine nichtdiskriminierende Selektion vor. Bei der sogenannten q-stufigen zweifachen Tunierselektion werden für jedes Individuum gegen q andere, zufällig ausgewählte Individuen direkte Duelle abgehalten. Dabei wird die Fitness der Kontrahenten verglichen und die Anzahl der Siege jedes Individuums vermerkt. Anschließend wird eine Rangfolge nach dieser Siegesanzahl erstellt und deterministisch diejenigen mit den meisten Siegen ausgewählt. Um Selektionsdruck zu erzeugen, muss q mindestens 1 betragen. Dieser Operator ist probabilistisch, aber trotzdem Duplikatfrei.35
Fitnessproportionale Selektion (Roulette)
Ein anderer Ansatz ist die so genannte fitnessproportionale Selektion. Da hier „mit Zurücklegen“ gezogen wird, ist es möglich, dass zweimal das gleiche Individuum ausgewählt wird. Die Selektionswahrscheinlichkeit hängt hier direkt mit der Fitness zusammen. Je größer die Fitness, umso wahrscheinlicher die Selektion. Die Wahrscheinlichkeit lässt sich als Quotient von Individualfitness dividiert durch die Gesamtfitness der Population berechnen. Da alle Individuen eine Chance auf Auswahl haben, liegt wie bei der Turnier-Selektion ebenfalls eine nicht diskriminierende Selektion vor.
Anschaulich kann man sich die Auswahl wie ein Roulettspiel vorstellen. Jedes Individuum hat einen bestimmten Bereich auf dem Roulettrad, dessen Größe seiner Selektionswahrscheinlichkeit entspricht. Nun wird am Rad „gedreht“ und das Individuum ausgewählt, bei welchem der Zeiger stehen bleibt.36
Bei der technische Umsetzung wird das Intervall [0, 1[ in soviele Abschnitte aufgeteilt, wie es Elternindividuen gibt. Jedes erhält einen Abschnitt zugewiesen, dessen Größe genau seiner Selektionswahrscheinlichkeit entspricht. Nun wird eine Zufallszahl erzeugt, welche aus dem gleichen Intervall kommen muss. Das Individuum wird gewählt, in dessen Bereich die Zufallszahl fällt. Dies wird so oft durchgeführt wie Eltern ausgewählt werden müssen.37
4.2 Rekombination
Das folgende Kapitel soll sich mit dem Thema Rekombination von Individuen beschäftigen. Den Begriff Rekombination finden wir in der Literatur häufig unter dem Namen Kreuzung oder Cross-over.
Die Hauptaufgabe der Rekombination stellt die Erstellung eines neuen Phänotyps, oder auch nachfolgend Kind bzw. Nachkommen genannt, aus der Elternpopulation dar. Hierbei sollen die Genome zweier Eltern miteinander kombiniert werden, so dass daraus ein bestmöglicher Erbnachfolger generiert wird.38
Abbildung in dieser Leseprobe nicht enthalten
Abb. 3: Grafische Darstellung der Rekombination
Die vorhandenen Informationen werden neu angeordnet. Dadurch ist es möglich auf einfache Weise eine Vielzahl von Kombinationen zu erproben. Programmiertechnisch ist die Rekombination auch äußerst einfach realisierbar. Die Rekombination lässt sich in die folgenden Verfahren gliedern:
Einpunktkreuzung:
Über ein Selektionsverfahren (z.B. der Wettkampfselektion) werden zwei geeignete Individuen ausgewählt und an einer bestimmten Stelle durchtrennt. Dann werden die beiden Teilstücke getauscht, so dass jeder Nachkomme aus seinem Vorderteil und dem Hinterteil des anderen Individuums besteht.
[...]
1Vgl. http://www.blackberry.com/de/.
2Vgl. http://www.apple.com/de/iphone/.
3GPRS ermöglicht mobilen Internetzugang in Verbindung mit einem GPRS-fähigen Endgerät.
4Schlanke Produktion, Produktionsorganisation.
5 Wertschöpfung aus „Cooperation“ und „Competition“, meint die Kooperation von Konkurrenten.
6 siehe Anhang 1: Aufgabenverteilung.
7Vgl. http://www.tu-chemnitz.de/informatik/ModSim/Software/leo.html.
8Vgl. http://ls2-www.cs.uni-dortmund.de/~storch/documents/DiplomArbeit.pdf.
9Vgl. http://www.fh-meschede.de/public/willms/ea/simu.html.
10Vgl. http://www.guidobauersachs.de/genetik/muta.html.
11Vgl. http://www.informatikdidaktik.de/HyFISCH/Spitzenforschung/Wegener.htm.
12Vgl. http://www.biosicherheit.de/de/lexikon/#R.
13Vgl. http://www-ti.informatik.uni-tuebingen.de/~heim/lehre/proseminar_ss99/ausarbeitung /andreas_korsten/node10.html.
14 Vgl. http://fbim.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k040401.html.
15Vgl. http://www.iai.fzk.de/www-extern/index.php?id=237.
16http://www.iai.fzk.de/www-extern/uploads/pics/Evo-Ablauf.gif.
17Jedes System, welches nicht in jedem Bereich proportional auf das Eingangssignal (Systemreiz) antwortet.
18Diskontinuität bezeichnet eine Funktion, die nicht stetig ist.
19 Vgl. http://ls2-www.cs.uni-dortmund.de/~jansen/EvoAlg2004/.
20Vgl. Böhnlein, Claus-Burkard (2005), S. 92.
21 Vgl. Schinzer, Heiko (1999), S. 857.
22Vgl. Werner, Hartmut (2007), S.5.
23 Vgl. Melzer-Ridinger, Ruth (2007), S.9.
24Vgl. Schinzer, Heiko (1999), S. 858.
25Vgl. Straube, Frank; Butz, Christian: (2005), S. 673.
26Vgl. Böhnlein, Claus-Burkard: (2005), S.225.
27 Vgl. Böhnlein, Claus-Burkard: (2005), S. 94.
28Schinzer, Heiko: (1999), S. 860.
29Vgl. http://www.supply-chain.org.
30 Vgl. http://www.supply-chain.org/cs/root/scor_tools_resources/scor_model/scor_model.
31 Vgl. Nissen, V. (1994), S. 46.
32 Vgl. Weicker, K. (2007), S. 66ff.
33 Eine Population wird als konvergiert bezeichnet, wenn alle Individuen gleich sind.
34 Vgl. Weicker, K. (2007), S. 64ff.
35 Vgl. Weicker, K. (2007), S. 68f.
36 Vgl. Nissen, V. (1994), S .44f.
37 Vgl. Nissen, V. (1997), S.37f.
38 Vgl. http://ls2-www.cs.uni-dortmund.de/~jansen/pg427/rekombination.pdf , S. 3.
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.