Betriebswirtschaftliche Anwendungen für Ameisen-Systeme

  Betriebswirtschaftliche Anwendungen für Ameisen-Systeme  1

Inhaltsverzeichnis

Inhaltsverzeichnis.......................................................................................................   1

1  Einführung in das Ameisen-System  2

1.1  Vorgehensweise in der Natur  2

1.2  Übertragung des Ameisen-Systems in die Informatik  3

2  Algorithmen  5

2.1  Ameisen-System  7

2.2  Ameisen-System mit Q-Lernen  13

2.3  Ameisen-System mit unterschiedlichen Ameisen  20

2.4  Parallelisierung  25

2.5  Zusammenstellung  28

3  Betriebswirtschaftliche Anwendungen  29

3.1  Rundreisen- und Tourenprobleme  30

3.1.1  Travelling Salesman Problem  30

3.1.2  Vehicle Routing Problem  32

3.1.3  Dependent Vehicle Routing Problem  38

3.2  Zuordnungsprobleme  41

3.2.1  Ameisen-Algorithmen für das Quadratic Assignment Problem  43

3.2.2  Quadratic Assignment Problem als Graph für Ameisen-Systeme  50

3.3  Reihenfolgeprobleme  55

3.3.1  Total Tardiness Problem  59

3.3.2  Sequential Ordering Problem  61

3.3.3  Open Shop Problem  64

3.3.4  Flow Shop Problem  65

3.3.5  Job Shop Problem  71

4  Ausblick  74

  Abbildungsverzeichnis  II

Variablen,  Parameter und Abkürzungen  III

  Literaturverzeichnis  IV

Versicherung..............................................................................................................  V  V

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 2

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 3

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 4

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 5

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 6

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 7

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 8

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 9

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 10

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 11

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 12

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 13

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 14

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 15

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 16

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 17

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 18

Dichte der Wahr-

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 19

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 20

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 21

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 22

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 23

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 24

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 25

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 26

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 27

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 28

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 29

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 30

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 31

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 32

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 33

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 34

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 35

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 36

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 37

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 38

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 39

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 40

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 41

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 42

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 43

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 44

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 45

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 46

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 47

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 48

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 49

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 50

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 51

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 52

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 53

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 54

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 55

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 56

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 57

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 58

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 59

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 60

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 61

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 62

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 63

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 64

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 65

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 66

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 67

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 68

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 69

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 70

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 71

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 72

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 73

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 74

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 75

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme 76

  Betriebswirtschaftliche Anwendungen für Ameisen-Systeme  II

  Abbildungsverzeichnis  

  Abbildung 1 1 : Ameisen finden den kürzesten Weg  3

  Abbildung 1 2 : künstliche Ameisen  3

  Abbildung 2 1 : Kategorisierung von Ameisen-Algorithmen  6

  Abbildung 2 2 : Ant-Q bei Oliver30 für verschiedene Übergangszustandsregeln  15

  Abbildung 2 3 : Zeit, in der kooperative bzw. nicht-kooperative Ameisen das  

  Optimum finden (aus DORIGO/GAMBARDELLA (1996c), Seite 11 )  18

  Abbildung 2 4 : Kooperative Ameisen finden bessere Lösungen in kürzerer Zeit (aus  

  DORIGO/GAMBARDELLA (1996c), Seite 11 )  18

  Abbildung 2 5 : Anzahl der Zyklen, um ein lokales Optimum zu erreichen mit  

verschiedener  Anzahl an elitären Ameisen (aus DORIGO ET AL. (1991 ), Seite 15 )  21

  Abbildung 2 6 : Synchrone und asynchrone Parallelisierung (aus BULLNHEIMER ET  

  AL. (1998 ), Seite 5 und TALBI ET AL. (2001 ), Seite 5 )  27

  Abbildung 2 7 : Übersicht über die verschiedenen Ameisen-Algorithmen  28

  Abbildung 3 1 : Behandelte Probleme aus der kombinatorischen Optimierung  29

  Abbildung 3 2 : Konstruktion des multiplen Ameisen-Kolonie Systems für das VRP  

  mit Zeitfenstern (aus GAMBARDELLA ET AL. (1999 ) S. 6 )  35

  Abbildung 3 3 : Verlauf der Geschwindigkeit (aus DONATI ET AL. (2002 ), Seite 4 )  38

  Abbildung 3 4 : Reisezeit für eine Kante der Länge 2 (aus DONATI ET AL. (2002 ),  

  Seite 5 )  39

  Abbildung 3 5 : Lineares dynamisches Angleichen bei der Spurenverstärkung (aus  

  MANIEZZO (1998 ), Seite 7 )  47

  Abbildung 3 6 : Disjunktiver Graph für ein Quadratisches Zuordnungsproblem  50

  Abbildung 3 7 : Disjunktives Bogenpaar zwischen Maschine M 3 und Ort O 2  51

  Abbildung 3 8 : Disjunktiver Graph für 4 Maschinen und 6 Orte  54

  Abbildung 3 9 : Disjunktiver Graph für ein allgemeines Maschinenbelegungsmodell  

  mit 4 Aufträgen und 3 Maschinen  57

  Abbildung 3 10 : Disjunktiver Teilgraph für Maschine 2  58

  Abbildung 3 9 : Graph für ein SMTTP mit 3 Aufträgen (aus BAUER ET AL. (2000 ),  

  Seite 6 )  59

  Abbildung 3 10 : Sequential Ordering Problem, Instanz mit 4 Aufträgen  62

  Abbildung 3 11 : Graph für ein OSP mit 4 Aufträgen und 3 Maschinen  64

  Abbildung 3 12 : Disjunktiver Graph für ein FSP mit 4 Aufträgen und 3 Maschinen65  

  Abbildung 3 13 : Teilgraph für die Reihenfolgen der Aufträge an den Maschinen  66

  Abbildung 3 14 : Disjunktiver Graph für ein JSP mit 4 Aufträgen und 3 Maschinen  71

  Abbildung 3 15 : Beispiel für eine Reihenfolge der Aufträge für ein JSP mit  4

  Aufträgen und 3 Maschinen  73

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme III

Variablen, Parameter und Abkürzungen

A Menge an Kanten A Kopplungsmatrix Element aus Kopplungsmatrix A a ij

Zeitpunkt für den Beginn eines Zeitfensters b ⁱ C Kostenmatrix Fertigstellungszeitpunkt insgesamt C ^j c Konstante c’ veränderbarer Faktor Kosten c ^ij Distanzmatrix D d Distanzvektor Element aus Vektor d d i

Distanz zwischen Knoten i und j d ^ij E Menge an Kanten e Anzahl an elitären Ameisen Zeitpunkt für das Ende eines Zeitfensters e ⁱ e ij Kante aus der Menge E Flussmatrix F F(j) Menge an Knoten, die besucht werden können FZ j Fertigstellungszeitpunkt von Auftrag j Flussvektor f Element aus Vektor f f ^j f ij Fluss zwischen Objekt i und j Funktion für zweifache Spurenaktualisierung g ^ij h, i, j, l Laufindex J Anzahl an Aufträgen K Gesamtkapazität des Fahrzeugs gesamte Nachfrage einer Tour K ⁱ k Index für die Ameisen

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme

Betriebswirtschaftliche Anwendungen für Ameisen-Systeme

IV

Literaturverzeichnis

Albayrak, S.; Garijo, F. J. (1998); Intelligent Agents for Telecommunication Applications, Second International Workshop, IATA ’98; Paris, France, Springer 1998

Alspector, J.; Goodman, R.; Brown, T. X. (1995); Application of Neural Networks to Telecommunications 2; Lawrence Erlbaum Publishing, Hillsdale, NJ, 1995

AntOptima (2004); http://www.antoptima.com, Aktualisierung vom 20.07.04

Bauer, A.; Bullnheimer, B.; Hartl, R. F.; Strauss, C. (1999); An ant colony optimization approach for the single machine total tardiness problem; Proceedings of the 1999 Congress on Evolutionary Computation (CEC ’99); IEEE Press, Piscataway, NJ, 1999, Seite 1445-1450

Bauer, A.; Bullnheimer, B.; Hartl, R. F.; Strauss, C. (1999); Applying Ant Colony Optimization to solve the Single Machine Total Tardiness Problem; Report Series SFB “Adaptive Information System and Modelling in Economics and Management Science”; Volume 42, SFB Adaptive Information Systems and Modelling in Economics and Management Science, 1999

Bauer,A; Bullnheimer, B.; Hartl, R. F.; Strauss, C. (2000); Minimizing total tardiness an a single machine using ant colony optimization; Central European Journal of Operations Research; Volume 8, Issue 2, 2000, Seite 125-141

BBT (2003); Machen wir’s wie die Ameisen: Ameisenalgorithmen als Problemlöser; Bundesamt für Berufsbildung und Technologie, http://www.bbt.admin.ch/print/kti/success/archiv/fh/d/idsia.htm, Aktualisierung vom 20.07.04

Besten, M. den; Stützle, T.; Dorigo, M. (2000); Ant Colony Optimization for the Total Weighted Tardiness Problem; Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature; Schoenhauer, M.; Deb, K.; Rudolph, G.; Yao, X.; Lutton, E.; Merelo, J. J.; Schwefel, H.-S. (Eds.); Volume 1917 of Lecture Notes in Computer Science, Springer Verlag Berlin, 2000, Seite 611-620

Bianchi, L.; Gambardella, L. M.; Dorigo, M. (2002a); An Ant Colony Optimization Approach to the Probabilistic Traveling Salesman Problem; Proceedings of PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature; Volume 2439 of Lecture Notes in Computer Science. Springer, Berlin, Germany, 2002

Bianchi, L.; Gambardella, L. M.; Dorigo, M. (2002b); Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic; Proceedings of the Third International Workshop on Ant Algorithms; Lecture Notes In Computer Science, 2002, Seite 176 - 187

Bonabeau, E.; Henaux, F.; Guérin, S.; Snyers, D.; Kuntz, P.; Theraulaz, G. (1998); Routing in telecommunications networks with „smart“ ant-like agents; Intelligent Agents for Telecommunication Applications, Second International Workshop, IATA ’98, Albayrak, S.; Garijo, F. J.(Eds.); Paris, France, Springer 1998, Seite 60 - 71

Bonabeau, E.; Meyer, C. (2001); Schwarm-Intelligenz: Unternehmen lernen von Bienen und Ameisen; Harvard Business Manager; Volume 6, 2001, Seite 38-49

Bonabeau, E.; Dorigo, M.; Theraulaz, G. (2000); Inspiration for optimization from social insect behaviour; Nature; Volume 406, 2000, Seite 39-42

Bonabeau, E.; Dorigo, M.; Theraulaz, G. (1999); Swarm Intelligence: From Natural to Artificial Systems; Santa Fe Institute studies in the science of complexity, Oxford University Press, New York, NY, 1999

Botee, H. M.; Bonabeau, E. (1998); Evolving Ant Colony Optimization; Advances in Complex Systems; Stadler, P. F. (Ed.), Volume 1, Hermes Verlag, 1998, Seite 149 - 159

Brélaz, D. (1979); New Methods to Color the Vertices of a Graph; Management Science/Operations Research; Volume 22, Issue 4, 1979, Seite 251-256

Brucker, P. (1998); Scheduling Algorithms; 2. Auflage, Springer-Verlag Berlin Heidelberg 1998

Bullnheimer, B.; Hartl, R. F.; Strauß, C. (1997a); A new rank based version of the ant system - a computational study; Central European Journal of Operations Research and Eco- nomics, Volume 1, 1999, Seite 25 - 38

Bullnheimer, B.; Hartl, R. F.; Strauss, C. (1997b); An improved ant system algorithm for the vehicle routing problem; Annals of Operation Research: Nonlinear Economic Dynamics and Control, Volume 89, 1999, Seite 319 - 328

Bullnheimer, B. F.; Hartl, R. F.; Strauss, C. (1997c); Applying the Ant System to the Vehicle Routing Problem; Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization; Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C. (Eds.); Kluwer, 1999, S. 285 - 296

Bullnheimer, B. F.; Kotsis, G.; Strauß, C. (1998); Parallelization Strategies for the Ant System; High Perfomance Algorithms and Software in Nonlinear Optimization; Leone, R. De; Murli, A.; Pardalos, P.; Toraldo, G. (Eds.); Volume 24, Kluwer, 1998, Seite 87 - 100

Burkard, R. E.; Cela, E.; Pardalos, P. M.; Pitsoulis, L. S. (1998); The Quadratic Assignment Problem; Handbook of combinatorial optimisation; Kluwer Academic Publishers, 1998, Seite 241-337

Burkard, R. E. (2000); Zuordnungsprobleme - ein Streifzug durch die kombinatorische Optimierung; Zur Kunst des formalen Denkens; Burkard, R. E.; Maas, W.; Weibel, P. (Eds.), Passagen Verlag Wien, 2000, Seite 193-207

Burkard, R. E.; Fincke, U. (1983); The Asymptotic Probabilistic Behaviour of Quadratic Sum Assignment Problems; Zeitschrift für Operations Research; Volume 27, 1983, Seite 73-

81

Burkard, R. E.; Maas, W.; Weibel, P. (2000); Zur Kunst des formalen Denkens; Passagen Verlag Wien, 2000

Chiarandini, M.; Stützle, T. (2002); An application of Iterated Local Search to Graph Col-oring Problem; Proceedings of the Computational Symposium on Graph Coloring and its Generalization; Johnson, D. S.; Mehrotra, A.; Trick, M. (Eds.); Ithaca, New York, USA, 2002, Seite 112-125

Colorni, A.; Dorigo, M.; Maniezzo, V. (1992a); An investigation of some properties of an “Ant algorithm”; Proceedings of the Parallel Problem Solving from Nature Conference;

Männer, R.; Manderick, B. (Eds.); Elsevier Publishing, Brussels, Belgium, 1992, Seite 509-520

Colorni, A.; Dorigo, M.; Maniezzo, V. (1992b); Distributed Optimization by Ant Colonies; Proceedings of the First European Conference on Artificial Life; Varela, F.; Bourgine, P. (Eds.); Elsevier Publishing, Paris, France, 1992, Seite 134-142

Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M. (1994); Ant system for Job-shop scheduling; JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science; Volume 34, Issue 1, 1994, Seite 39-53

Comellas, F.; Ozón, J. (1998); An Ant Algorithm for the Graph Colouring Problem; ANTS’98 - From Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization; Brussels, Belgium, 1998

Comellas, F.; Ozón, J. (1995); Graph Coloring Algorithms for Assignment Problem in Radio Networks; Application of Neural Networks to Telecommunications 2; Alspector, J.; Goodman, R.; Brown, T. X. (Eds.); Lawrence Erlbaum Publishing, Hillsdale, NJ, 1995, Seite 49-56

Corne, D.; Dorigo, M.; Glover, F. (1999); New Ideas in Optimization; McGraw-Hill, 1999

Corsten, H. (2000); Produktionswirtschaft: Einführung in das industrielle Produktionsmanagement; 9. Auflage, Oldenbourg Wissenschaftsverlag 2000

Costa, D.; Hertz, A. (1997); Ants Can Colour Graphs; The Journal of the Operational Research Society; Volume 48, Issue 3, 1997, Seite 295-305

Di Caro, G.; Dorigo, M. (1998); An adaptive multi-agent routing algorithm inspired by ants behavior; Proceedings of PERT98 - Fifth Annual Australasian Conference on Parallel and Real-Time Systems; Adelaide, Australia, 1998

Di Caro, G.; Dorigo, M. (1999); AntNet: A mobile agents approach to adaptive routing; A Quarterly in Artificial Intelligence; Volume 12, Issue 3-4, 1999, Seite 2-37

Diestel, R. (1996); Graphentheorie; Springer-Verlag Berlin Heidelberg 1996

Dörner, K.; Gronalt, M.; Hartl, R. F.; Reimann, M.; Strauss, C.; Stummer, M. (2002); SavingsAnts for the Vehicle Routing Problem; EvoWorkshop 2002, LNCS 2279; Springer-Verlag Berlin Heidelberg, 2002, Seite 11-20

Domschke, W. (1997); Logistik: Rundreisen und Touren; 4. Auflage, R. Oldenbourg Verlag München, 1997

Domschke, W.; Drexl, A. (1990); Logistik: Standorte; 3. Auflage, R. Oldenbourg Verlag München, 1990

Domschke, W. (1995); Logistik: Transport; 4. Auflage, R. Oldenbourg Verlag München, 1995

Donati, A. V.; Gambardella, L. M.; Rizzoli, A. E.; Casagrande, N.; Montemanni, R. (2002); Time Dependent Vehicle Routing Problem with an Ant Colony System; Technical Report IDSIA-02-03; Istituto Dalle Molle di Studi sull'Intelligenza Artficiale, 2002

Dorigo, M. (2001); Ant Algorithms Solve Difficult Optimization Problems; Advances in Artificial Life, Proceedings of the Sixth European Conference on Artificial Life, LNAI 2159; Springer-Verlag, 2001, Seite 11-22

Dorigo, M.; Di Caro, G. (1999); The Ant Colony Optimization Meta-Heuristic; New Ideas in Optimization; Corne, D.; Dorigo, M.; Glover, F. (Eds.); McGraw-Hill, 1999, Seite 11-32

Dorigo, M.; Di Caro, G.; Gambardella, L. M. (1998); Ant Algorithms for Discrete Optimization; Artificial Life; Volume 5, Issue 2, The MIT Press, 1999, Seite 137-172

Dorigo, M.; Di Caro, G.; Sampels, M. (2002a); Ant Algorithms, Third International Workshop, ANTS 2002; Lecture Notes in Computer Science, Volume 2463, Springer 2002

Dorigo, M.; Gambardella, L. M. (1996a); A study of some properties of Ant-Q; Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature; Voigt, H.-M.; Ebeling, W.; Rechenberg, I.; Schwefel, H.-S. (Eds.); Springer-Verlag, Berlin, Germany, 1996, Seite 656-665

Dorigo, M.; Gambardella, L. M. (1996b); Ant colonies for the traveling salesman problem; BioSystems, Volume 43, 1997, Seite 73-81

Dorigo, M.; Gambardella, L. M. (1996c); Ant colony system: A cooperative learning approach to the traveling salesman problem; IEEE Transactions on Evolutionary Computation; Volume 1, Issue 1, 1997, Seite 53-66

Dorigo, M.; Maniezzo, V.; Colorni, A. (1991a); Ant system: An autocalatytic optimizing prozess; Technical Report No. 91-016 Revised; Politencnico di Milano, Italy; 1991

Dorigo, M.; Maniezzo, V.; Colorni, A. (1991b); Positive feedback as a search strategy; Technical Report No. 91-016; Politecnico di Milano, Italy, 1991

Dorigo, M.; Maniezzo, V.; Colorni, A. (1996); The Ant System: Optimizaion by a colony of cooperating agents; IEEE Transactions on Systems, Man, and Cybernetics-Part B; Volume 26, Issue 1, 1996, Seite 29-41

Dorigo, M.; Stützle, T. (2001); An Experimental Study of the Simple Ant Colony Optimization Algorithm; Proceedings of 2001 WSES International Conference on Evolutionary Computation (EC’01); Mastorakis, N. (Ed.), WSES-Press International, 2001, Seite 253-258

Dorigo, M.; Zlochin, M.; Meuleau, N.; B. (2002b); Updating ACO Pheromones Using Stochastic Gradient Ascent and Cross-Entropy Methods; EvoWorkshops 2002, LNCS 2279; Springer-Verlag Berlin Heidelberg 2002, Seite 21-30

Escudero, L. F.(1988); An inexact algorithm for the sequential ordering problem; System Science; Forth EURO Summer Institute Special Issue; European Journal of Operations Research; Mercer, A.; C. Tilanus, B.; Zimmermann, H.-J. (Eds.); Volume 37; Elsevier Science Publishers, North Holland, 1988, Seite 236-249

Eiben, A. E.; Bäck, T.; Schoenauer, M.; Schwefel, H.-P. (1998); Proceedings of Parallel Problem Solving from Nature - PPSN-V; Volume 1498, Amsterdam, Springer-Verlag, 1998

FactumOnline (2001); Ameise als Vorbild; http://www.factum-

magazin.ch/whats_new/news.cgi?v=archive&c=Internet&id=12211004522.shtml, Aktualisierung vom 20.07.04

Fidanova, S. (2002); ACO Algorithm with Additional Reinforcement; Ant Algorithms, Third International Workshop, ANTS 2002; Dorigo, M.; Di Caro, G.; Sampels, M. (Eds.): Brus-

sels, Belgium, Lecture Notes in Computer Science, Volume 2463, Springer 2002, Seite 292-293

Finke, G.; Burkard, R. E.; Rendl, F.(1987); Quadratic Assignment Problems; Annals of Discrete Mathematics: Surreys in Combinatorial Optimization; Martello, S.; Caporte, G.; Minoux, M.; Riberio ,C. (Eds.); Volume 31, Elsevier Science Publishers, 1987, Seite 61-82

Gambardella, L. M.; Dorigo, M. (2000); An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem; INFORMS Journal on Computing; Volume 12, Issue 3, 2000, Seite 237-255

Gambardella, L. M.; Taillard, E. D. (1999); Dorigo, Marco; Ant Colonies for the Quadratic Assignment Problem; Journal of the Operational Research Society; Volume 50, 1999, Seite 167-176

Gambardella, L. M.; Dorigo, M. (1995); Ant-Q: A Reinforcement Learning approach to the traveling salesman problem; Twelfth International Conference on Machine Learning; Morgan Kaufmann, 1995, Seite 252-260

Gambardella, L. M.; Dorigo, M. (1997); HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem; Technical Report IDSIA; Volume 11, Lugano, Switzerland, 1997

Gambardella, L. M.; Dorigo, M. (1996); Solving Symmetric and Asymmetric TSPs by Ant Colonies; ICEC96, Proceedings of the IEEE Conference on Evolutionary Computation; Nagoya, Japan, 1996

Gambardella, L. M.; Taillard, E.; Agazzi, G.(1999); MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows; New Ideas in Optimization; Corne, D.; Dorigo, M.; Glover, F. (Eds.); McGraw-Hill, London, UK, 1999, Seite 63-76

Garey, M. R.; Johnson, D. (1979); Computers and Intractability: A Guide to the Theory of NP-Completeness; Bell Telephone Laboratories, 1979

Gillett, B. E.; Miller, L. R. (1974); A Heuristic Algorithm for the Vehicle-Dispatch Prob- lem; Operations Research; Volume 22, Issue 2, 1974, Seite 340-349

Glover, F. (1989); Tabu Search - Part I; ORSA Journal an Computing; Volume 1, Issue 3, 1989, Seite 190-206

Glover, F. (1990); Tabu Search - Part II; ORSA Journal on Computing; Volume 2, Issue 1, 1990, Seite 4-32

Günther, H.-O.; Tempelmeier, H. (2003); Produktion und Logistik; 5. Auflage, Springer-Verlag Berlin Heidelberg, 2003

Guntsch, M.; Middndorf, M.; Schmeck, H. (2001); An Ant Colony Optimization Approach to Dynamic TSP; Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001); San Fransisco, Californien, Morgan Kaufmann, 2001, Seite 860 - 867

Johnson, D. S.; Mehrotra, A.; Trick, M. (2002); Proceedings of the Computational Symposium on Graph Coloring and its Generalization; Ithaca, New York, USA, 2002

Kawamura, H.; Yamamoto, M.; Suzuki, K.; Ohuchi, A. (2000); Multiple Ant Colonies Algorithm Based on Colony Level Interactions; IEICE Transactions on Fundamentals; Volume E83-A, Issue 2, 2000, Seite 371-379

Kindvater, G. A. P.; Lenstra, J. K. (1989); The Parallel Complexity of TSP Heuristics; Journal of Algorithms; Volume 10, 1989, Seite 249-270

Kistner, K.-P. (2003); Optimierungsmethoden, Einführung in die Unternehmensforschung für Wirtschaftswissenschaftler; 3. Auflage, Physica-Verlag Heidelberg, 2003

Kistner, K.-P.; Steven, M. (2001); Produktionsplanung; 3. Auflage, Physica-Verlag Heidelberg, 2001

Koopmans, T. C.; Beckmann M. (1957); Assignment Problems and the Location of Economic Activities; Econometrica; Volume 25, Issue 1, 1957, Seite 53-76

Latz, T. (1997); Entscheidungsmodelle der Ablaufplanung; Mathematische Programme für Shop-Scheduling-Probleme; Deutscher Universitäts-Verlag, Gabler Verlag Wiesbaden, 1997

Leone, R. De; Murli, A.; Pardalos, P.; Toraldo, G. (1998); High Perfomance Algorithms and Software in Nonlinear Optimization; Kluwer, 1998

Li, Y.; Gong, S. (2003); Dynamic ant colony optimisation for TSP; The International Journal of Advanced Manufacturing Technology; Volume 22, Issue 7-8, Springer-Verlag London, 2003, Seite 528 - 533

Männer, R.; Manderick, B. (1992); Proceedings of the Parallel Problem Solving from Nature Conference; Elsevier Publishing, Brussels, Belgium, 1992

Mainzer, K. (2003); Im Zeitalter der denkenden Maschinen; Technology Review; Volume 12, 2003, Seite 87-97

Malandraki, C.; Daskin, M. S. (1992); Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms; Transportation Science; Volume 26, Issue 3, Operations Research Society of America, 1992, Seite 185-200

Maniezzo, V. (1998); Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem; Technical Report CSR 98-1, C. L. In Science dell’Informtione; Bologna, Italy, 1998

Maniezzo, V.; Colorni, A. (1999); The ant system applied to the quadratic assignment problem; IEEE Transactions on Knowledge and Data Engineering; Volume11, Issue 5, 1999, Seite 769-778

Maniezzo, V.; Corloni, A.; Dorigo, M. (1994); The Ant System applied to the Quadratic Assignment Problem; Technical Report 94/28, IRIDIA; Université de Bruxelles, Bruxelles, Belgium, 1994

Maniezzo, V.; Gambardella, L. M.; Luigi, F. de (2004); Ant Colony Optimization; New Optimization Techniques in Engineering; Onwubolu, G. C.; Babu, B. V. (Eds.); Springer-Verlag Berlin Heidelberg, 2004, Seite 101-117

Martello, S.; Caporte, G.; Minoux, M.; Riberio ,C. (1987); Annals of Discrete Mathematics: Surreys in Combinatorial Optimization; Volume 31, Elsevier Science Publishers, 1987

Mastorakis, N. (2001); Proceedings of 2001 WSES International Conference on Evolution- ary Computation (EC’01); WSES-Press International, 2001

Mastrolilli, M.; Gambardella, L. M. (2000); Effective Neighborhood Functions for the Flexible Job Shop Problem; Journal of Scheduling, Volume 3, Issue 1, 2000, Seite 3-20

Matthäus, F. (1978); Tourenplanung: Verfahren zur Einsatzdisposition von Fuhrparks; Toeche-Mittler Verlag Darmstadt, 1978

Mercer, A.; C. Tilanus, B.; Zimmermann, H.-J (1988); System Science; Forth EURO Summer Institute Special Issue; European Journal of Operations Research; Volume 37; Elsevier Science Publishers, North Holland, 1988

Merkle, D.; Middendorf, M. (2000); An Ant Algorithm with a new Pheromone Evaluation Rule for Total Tardiness Problems; Real-World Applications of Evolutionary Computing: Proceedings of EvoWorkhops 2000; Springer Verlag, 2000, Seite 287 - 296

Mertens, P. (2001); Integrierte Informationsverarbeitung 1: Operative Systeme in der Industrie; 13. Auflage, Betriebswirtschaftlicher Verlag Gabler, Wiesbaden 2001

Middendorf, M.; Reischle, F.; Schmeck, H. (2000); Information Exchange in Multi Colony Ant Algorithm; Parallel and Distributed Computing: Proceeding of the Fifteenth IPDPS Workshop 2000; Springer Verlag, 2000, Seite 645-652

Montemanni, R.; Gambardella, L. M.; Rizzoli, A. E.; Donati, A. V. (2003); A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System; Proceedings of ODYSSEUS 2003, Palermo, Italy, 2003

Montgomery, J. (2002); Towards a Systematic Problem Classification Scheme for Ant Colony Optimisation; Technical Report TR02-15; Faculty of Information Technology, Bond University, Australia, 2002

Montgomery, J.; Randall, M. (2002a); Alternative Pheromone Applications for Ant Colony Optimisation; Technical Report TR02-07; Faculty of Information Technology, Bond University, Australia, 2002

Montgomery J.; Randall, M. (2002b); Anti-pheromone as a Tool for Better Exploration of Search Space; Proceedings of the Third International Workshop on Ant Algorithms, ANTS 2002; Brussels, Belgium, 2002

Morad, N. (2000); Genetic Algorithms Optimization for the Machine Layout Problem; International Journal of the Computer, the Internet and Management; Volume 8 Issue 1, 2000

Nawaz, M.; Enscore Jr., E. E.; Ham, I. (1983); A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem; OMEGA, The International Journal of Management Science; Volume 11, Issue 1, Pergamon Press Ltd. 1983, Seite 91-95

Neumann, K. (1996); Produktions- und Operations-Management; Springer-Verlag Berlin Heidelberg 1996

Oliver, I. M.; Smith, D.J.; Holland, J. R. C. (1987); A study of permutation crossover op-erators an the traveling salesman problem; Genetic Algorithms and their Applications: Proceedings of the Second International Conference an Genetic Algorithm; Camebridge, Massachusetts, 1987

Onwubolu, G. C.; Babu, B. V. (2004); New Optimization Techniques in Engineering; Springer-Verlag Berlin Heidelberg, 2004

Rajendran, C. (1993); Heuristic algorithm for scheduling in a flowshop to minimize total flowtime; International Journal of Production Economics; Volume 29, Elsevier Science Publishers, 1993

Rajendran, C.; Ziegler, H. (2004); Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs; European Journal of Operations Research; Volume 155, 2004, Seite 426-438

Randall, M.; Montgomery, J. (2002); Candidate Set Strategies for Ant Colony Optimisation; Proceedings of the Third International Workshop on Ant Algorithms, ANTS 2002; Brussels, Belgium, 2002

Reimann, M.; Doerner, K.; Hartl, R. F. (2003); Analyzing a Unified Ant System for the VRP and Some of Its Variants; Applications of Evolutionary Computing: EvoWorkshops 2003: EvoBIO, EvoCOP, EvolASP, EvoMUSART, EvoROB, and EvoSTIM. Proceedings; Essex, UK, Springer-Verlag, 2003, Seite 300-310

Russell, S.; Norvig, P. (2003); Artificial Intelligence, A Modern Approach; 2. Auflage, Pearson Education, Inc., Upper Soddle River, New Jersey, 2003

Sautter, U. (2004); Insect Power; http://www.time.com/europe/specials/ff/trip4/ants.html, Aktualisierung vom 20.07.04

Schmundt, H. (2000); Duft der Daten; Der Spiegel, Volume 46, 2000, Seite 264

Schoenhauer, M.; Deb, K.; Rudolph, G.; Yao, X.; Lutton, E.; Merelo, J. J.; Schwefel, H.-S. (2000); Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature; Volume 1917 of Lecture Notes in Computer Science, Springer Verlag Berlin, 2000

Smith, G. D.; Steele N. C.; Albrecht, R. F. (1998); Proceedings of Artificial Neural Nets and Genetic Algorithms 1997; Springer Verlag Wien, 1998

Stadler, P. F. (1998); Advances in Complex Systems; Volume 1, Hermes Verlag, 1998

Stamer, H. (2001); Ant Algorithmen für kombinatorische Optimierungsprobleme; Seminararbeit, Institut für Informatik, Universität Leipzig, 2001

Stamer, H. (2003); Recruiting Ant Colony System (RACS); http://gaos.org/~stamer/

Aktualisierung vom 24.03.04

Stützle, T. (1997a); An Ant Approach to the Flow Shop Problem; Proceedings of EUFIT’98; Aachen, 1998, Seite 1560-1564

Stützle, T. (1998a); Applying Iterated Local Search to the Permutation Flow Shop Problem; Technical Report AIDA-98-04; Darmstadt University of Technology, Computer Science Department, Intellectics Group, 1998

Stützle, T. (1997b); MAX-MIN, Ant System for Quadratic Assignment Problems; Technical Report AIDA-97-04; Darmstadt University of Technology, Computer Science Department, Intellectic Group, 1997

Stützle, T. (1998b); Parallelization Strategies for Ant Colony Optimization; Proceedings of Parallel Problem Solving from Nature - PPSN-V; Eiben, A. E.; Bäck, T.; Schoenauer, M.; Schwefel, H.-P. (Eds.); Volume 1498, Amsterdam, Springer-Verlag, 1998, Seite 722-731

Stützle, T.; Dorigo, M. (1999a); ACO Agrithms for the Quadratic Assignment Problem; New Ideas in Optimization; Corne, D.; Dorigo, M. Glover, F. (Eds.); McGraw-Hill, 1999

Stützle, T.; Dorigo, M. (1999b); ACO Algorithms for the Traveling Salesman Problem; Evolutionary Algorithms in Engineering and Computer Science; 1999, Seite 163-183

Stützle, T.; Hoos, H. H. (1998a); Ameisenalgorithmen zur Lösung kombinatorischer Optimierungsprobleme; Leipziger Informatiktage (LIT’98); 1998

Stützle, T.; Hoos, H. (1996); Improving the Ant System: A Detailed Report on the MAX-MIN Ant System; Technical Report AIDA-96-12; Darmstadt University of Technology, Computer Science Department, Intellectics Group, 1996

Stützle, T.; Hoos, H. (1998b); Improvements on the Ant-System: Introducing the MAX-MIN Ant-System; Proceedings of Artificial Neural Nets and Genetic Algorithms 1997; Smith, G. D.; Steele N. C.; Albrecht, R. F. (Eds.); Springer Verlag Wien, 1998, Seite 245-249

Stützle, T.; Hoos, H. (1999); MAX-MIN Ant System; Future Generation Computer System; Volume 16, Issue 8, 2000, Seite 889-914

Stützle, T.; Hoos, H. (1997a); Max-Min Ant System and local search for the traveling salesman problem; Proceedings of the IEEE International Conference on Evolutionary Computation; Indianapolis, USA, 1997, Seite 308-313

Stützle, T.; Hoos, H. (1997b); Max-Min Ant system and local search for combinatorial optimization problems; Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization; Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C. (Eds.); Kluwer Acadamic Publishers, 1998, Seite 313-329

Sumpter, D. J. T.; Blanchard, G. B.; Broomhead, D. S. (2001); Ants and Agents: a Process Algebra Approach to Modelling Ant Colony Behaviour; Bulletin of Mathematical Biology; Volume 63, 2001, Seite 951-980

Taillard, E. D.; Gambardella, L. M. (1997); Adaptive Memories for the Quadratic As-

signment Problem; Technical Report IDSIA-87-97; IDSIA, Lugano, Switzerland, 1997

Talbi, E.; Roux, O.; Fonlupt, C.; Robillard, D. (2001); Parallel Ant Colonies for Combi-natorial Optimization Problems; Future Generation Computer Systems; Volume 17, 2001, Seite 441-449

Varela, F.; Bourgine, P. (1992); Proceedings of the First European Conference on Artificial Life; Elsevier Publishing, Paris, France, 1992

Voigt, H.-M.; Ebeling, W.; Rechenberg, I.; Schwefel, H.-S. (1996); Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature; Springer-Verlag, Berlin, Germany, 1996

Volkmann, L. (1991); Graphen und Digrapen: Eine Einführung in die Graphentheorie; Springer-Verlag Wien, 1991

Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C. (1999); Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization; Kluwer, 1999

Weiß, G.; Sen, S. (1996); Adaption and Learning in Multi-Agent Systems: IJCAI’95 Workshop, Montréal, Canada, 1995, Proceedings; Lecture notes in computer science; Volume 1042; Springer-Verlag Berlin Heidelberg, 1996

Weiß, G. (1999); Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence; Massachusetts Institute of Technology Press, Cambridge, Massachusetts, London, England, 1999

Zwaan, S. van der; Marques, C. (1999); Ant Colony Optimization for Job Shop Schedul- ing; Proceedings of the third Workshop on Genetic Algorithms and Artificial Life; 1999

V

Versicherung

Name: Kötter

Vorname: Philipp

Versicherung

Ich versichere, dass ich die Diplomarbeit selbständig und ohne Benutzung anderer als den angegebenen Quellen angefertigt habe.

Die den benutzten Quellen wörtlich oder inhaltlich entnommenen Stellen habe ich als solche kenntlich gemacht.

Bielefeld, den

Unterschrift