University of Bielefeld - Faculty of Technology - Artificial Intelligence Group

Intelligente Algorithmen

Seminar im Hauptstudium, Wintersemester 2003/2004

Termin: Do 16-18
Raum: V2-213
Beginn: 16.10.2003
Veranstalter: Stefan Kopp, Nadine Leßmann, Alf Kranstedt

Termine
Literatur
Vorträge / Ausarbeitungen

Hilfen für die Erarbeitung von Vorträgen und Ausarbeitungen

Zum Runterladen gibt's hier eine Anleitung für die Erarbeitung von Vorträgen,
einen ausführlicheren "Speaker's Guide" aus dem Netz,
und unsere Vorstellungen über die Erstellung von Hausarbeiten
mit einer gesonderten Anleitung für die Gestaltung des Literaturverzeichnisses.
Desweiteren verweisen wir auf die Angebote des Schreiblabors der Universität.

Hier gibt's einen Text, den Ihr Euch für die Abschlussdiskussion ansehen solltet. Er vergleicht einige der im Seminar vorgestellten Verfahren hinsicht Adäquatheit und Effizienz.

Voraussetzungen/Vorkenntnisse:

Das Seminar ist als Ergänzung zur Vorlesung "Methoden der KI" gedacht und richtet sich an Studierende im Hauptstudium. Die Bereitschaft, sich auch mit abstrakteren mathematischen Formalismen auseinanderzusetzen wird vorausgesetzt.
Eine Teilnehmerliste hängt ab September in M4-122 aus. Es wird gebeten, sich dort vor Beginn des Semesters einzutragen.

Inhalt/Kommentar:

Unter intelligenten Algorithmen versteht man in der KI Verfahren, die gezielt Heuristiken einsetzen, um Probleme zu lösen, die ansonsten nur mit unverhältnismäßigen Aufwand (nicht effizienter als in exponentieller Zeit) vollständig lösbar wären. In diesem Seminar soll zunächst der Begriff der Problemkomplexität (P/NP) eingeführt werden. Anhand von ausgewählten Problemen (z.B. dem Traveling-Salesman-Problem aus dem Bereich Planen und Suchen, dem Subgraph-Matching aus der Graphentheorie und einem Problem aus der Spieltheorie) werden verschiedene algorithmische Lösungsansätze in Form ausgearbeiteter Vorträge vorgestellt. Dabei sollen verschiedene Ansätze wie z.B. heuristische Suchverfahren oder genetische Algorithmen erarbeitet, miteinander verglichen und auf ihre Anwendbarkeit für das konkrete Problem evaluiert werden. Auf Wunsch können ausgewählte Verfahren auch praktisch erarbeitet, implementiert und im Plenum demonstriert werden.

Terminübersicht

16.10.2003 Die Veranstalter Einführung und Organisatorisches

23.10.2003 Die Veranstalter Einführungsvortrag zur Problematik P/NP

30.10.2003 Die Veranstalter Suchverfahren

6.11.2003 Olaf Graeser Tabusuche

13.11.2003 Walli Hein Dynamisches Programmieren

20.11.2003 Adam El Sayed Auf / Kai Linnemann Genetische/Evolutionäre Algorithmen I

27.11.2003 Adam El Sayed Auf / Kai Linnemann Genetische/Evolutionäre Algorithmen II

4.12.2003 fällt aus

11.12.2003 Frank Schönmann Lineares Programmieren: Cutting-planes

18.12.2003 Jan Lümkemann Kooperatives Lernen: Ant Colonies

8.1.2004 Christoph Niehaus Randomisierte Verfahren: Simulated Annealing, Monte Carlo

15.1.2004 Tolga Dalman Quantencomputing

22.1.2004 fällt aus

29.1.2004 fällt aus

5.2.2004 Abschlußdiskussion

Literatur & Links

Diese Liste ist nicht statisch! Sie sollständig aktualisiert werden. Dabei nehmen wir gerne Anregungen von Euch auf!
Alle hier aufgeführten Texte sind, soweit nicht anders angegeben, über uns zu bekommen.

Überblicksliteratur: Komplexitätstheorie, NP-Vollständigkeit und kombinatorische Optimierung

Michael Garey and David Johnson: Computers and Intractability - A Guide to the Theory of NP-completeness; Freeman, 1979. (Semesterapparat)
John E. Hopcroft: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie, München: Pearson Studium, 2002. (Semesterapparat)
A. Asteroth and C. Baier: Theoretische Informatik, München: Pearson Studium, 2002. (in der AG)
U. Schöning: Algorithmik, Spektrum-Verlag 2001. (Sehr gutes Buch, aber leider in der Bib und bei uns nicht verfügbar!)
E. Aarts, J.K. Lenstra: Local Search in Combinatorial Optimization, Wiley, 1997 (mit Fernleihe über HBZ (Nordrhein-Westf.) verfügbar)
Z. Michalewicz, D.B. Fogel: How to Solve It: Modern Heuristics, Springer, 1999. (Semesterapparat)
C. Reeves (ed.): Modern Heuristic Techniques for Combinatorial Problems, McGraw-Hill, 1995. (Semesterapparat)
Eine strukturierte Sammlung NP-vollständiger Probleme findet sich im compendium of NP optimization problems
Für einen ersten Überblick reicht vielleicht auch die Annotated List of Selected NP-complete Problems

Das Traveling Salesman Problem

E.L. Lawler: The traveling salesman problem: A guided tour of combinatorial optimation, Wiley '85. (Semesterapparat)
Solving Traveling Salesman Problems ist eine sehr umfangreiche und informative Seite zur Geschichte des TSP und seiner Lösung mittels der Cutting-Plane Methode.
Die TSPLIB ist eine Sammlung repräsentativer Instanzen verschiedener Unterklassen von TSP und jeweils eine Zusammenstellung der besten bekannten Lösungen (die meisten sind inzwischen gelöst, Stand Dez. 2001).

Suchverfahren (Tabu Search)

M. Zachariasen and M. Dam: Tabu Search on the Geometric Traveling Salesman Problem, Meta-heuristics: Theory and Applications (editors I.H. Osman and J.P. Kelly), Kluwer Academic Publishers, Boston, 571-587, 1996.
C.-N. Fiechter: A parallel tabu search algorithm for large traveling salesman problems, Discrete Applied Mathematics 51 (1994) 243-267.
P. Caricato, G. Ghiani, A. Grieco, and E. Guerriero: Parallel tabu search for a pickup and delivery problem under track contention, Parallel Computing 29 (2003) 631-639
Learning Evaluation Functions to Improve Optimization by Local Search, Journal of Machine Learning Research 1 (2000) 77-112.
S. K. Lau, L.-Y. Shue: Solving Traveling Salesman Problems with an Intelligence Search Approach, APORS 2000, Singapore.

Graphentheorie: Branch and Bound

E. Bales, P. Toth: Branch and bound methods, in E.L. Lawler: The traveling salesman problem: A guided tour of combinatorial optimation, Wiley '85.
D. R. Smith: Random Trees and the Analysis of Branch and Bound Procedures, Journal of the ACM, Vol. 31, 1984, pp. 163-188
W. Zhang: Truncated Branch-and Bound: A Case Study on the Asymmetric TSP, Proc. AAAI-93 Spring Symp. on AI and NP-Hard Problems, pp. 160-166.

Randomisierte Verfahren: Simulated Annealing, Monte Carlo

C. C. Skiscim, B. L. Golden: Optimization by Simulated Annealing: A Preliminary Computational Study for the TSP, Proceedings of the Winter Simulation Conference 1983.
L. Jelenkovic, J. Poljak: Multithreaded Simulated Annealing, Proc. 20th Int. Conference ITI'98, Pula, June 14-17 1998.
H. Sanvicente-Sanchez, J. Frausto-Solis: MPSA: A Methodology to Parallelize Simulated Annealing and its Application to the Traveling Salesman Problem, Lectures Notes on Computer Science, NY: Springer Verlag, 2002.
M. Miki, T. Hiroyasu, T. Yoshida, T. Fushimi: Parallel Simulated Annealing with Adaptive Temperature Determined by Genetic Algorithm, 2002 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS.
Zur Einführung in Monte Carlo: C. Theis, W. Kernbichler: Grundlagen der Monte Carlo Methoden, Institut für Theoretische Physik, Universität Graz.
Ebenso: Introduction to Monte Carlo Methods, Computational Science Education Project.
W. H. Wong, F. Liang: Dynamic weighting in Monte Carlo and optimization, Proc. Natl. Acad. Sci. USA, Vol.94, pp. 14220-14224, Dec. '97.
O. Martin: Large-Step Markov Chains for the Traveling Salesman Problem, Complex Systems, Vol. 5:3, 1991.

Dynamisches Programmieren

Auch für diesen Ansatz gibt's eine spezielle Website.
J. Fonlupt and A. Nachef: Dynamic Programming and the Graphical Traveling Salesman Problem, Journal of the ACM, Vol. 40, No. 5, November 1993, pp. 1165-1187.
N. Simonetti: Applications of a Dynamic Programming Approach to the Traveling Salesman Problem. Thesis.
N. Simonetti: Linear Time Dynamic Programming Algorithms for New Classes of Restricted TSPs: A Computational Study, INFORMS Journal on Computing 13:1 (2001), 56-75.

Lineares Programmieren: Die Cutting-Plane Methode

V. Chvátal: Linear Programming, New York: Freeman '83. (Semesterapparat Mashurian, selbes Regal wie unserer, unterste Reihe)
D. Applegate, R. Bixby, V. Chvátal, and W. Cook: On the solution of traveling salesman problems, Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians, pp645-656, 1998
(Lösung des TSP mittels "cutting-plane method", dazu gibt es auch Folien)
siehe dazu auch: Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions, Springer LNCS Vol.2241, 2001 (mit Fernleihe über SWB verfügbar)

Genetisches/Evolutionäres Programmieren

Volker Nissen: Einführung in Evolutionäre Algorithmen, Vieweg-Verlag, Wiesbaden, 1997. (Semesterapparat)
David B. Fogel: Evolutionary computation, IEEE Press 2000, Bib: HK450 F655
David B. Fogel: An Introduction to Simulated Evolutionary Optimization, Transaction on Neural Networks, Vol.5, No.1, Jan. '94. Bib.: HI000 I5N4N[5
John R. Koza: On the programming of computers by means of natural selection, MIT Press '98, Bib: HK450 K88
(Eine ältere Auflage unter dem Titel "Genetic Programming" bei HK310 K88)
K.A. de Jong and W.M. Spears: Using Genetic Algorithms to Solve NP-Complete Problems, Proceedings of the Third International Conference on Genetic Algorithms, pages 124-132, 1989.
K. Park, B. Carter: On the Effectiveness of Genetic Search in Combinatorial Optimization, Proceedings of the 10th ACM Symposium on Applied Computing 1995.
B. A. Julstrom: Very Greedy Crossover in a Genetic Algorithm for the Traveling Salesman Problem, Proceedings of the 1995 ACM symposium on Applied computing, Nashville, Tennessee USA.
J. Gottlieb, T. Kruse: Selection in Evolutionary Algorithms for the Traveling Salesman Problem, Proceedings of the ACM Symposium on Applied Computing 408 - 414, 2000.
J.T. Alander: An Indexed Bibliography of Genetic Algorithms and the Traveling Salesman Problem, Report No. 94-1, University of Vaasa, Finnland, December 2000.

Kombinierte Verfahren: Memetische Algorithmen

Zum Thema gibt's die Memetic Algorithms' Home Page mit sehr umfangreicher Bibliographie.
Mit diesem Artikel wurde der Begriff Memetic Algorithms angeblich eingeführt: P. Moscato: On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, C3P Report 826, 1989.
P. Merz and B. Freisleben, "Memetic Algorithms for the Traveling Salesman Problem," Complex Systems, vol. 13, no. 4, pp. 297-345, 2001 (weitere Arbeiten der Autoren zum Thema hier.)
N. Krasnogor, J. Smith: A Memetic Algorithm with Self-Adaptive Local Search: TSP as a case study, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000).

Kooperatives Lernen: Ant Colonies

P. Tarasewich, P. R. McMullen: Swarm Intelligence: Power in Numbers, Communications of the ACM, Vol. 45, No. 8, August 2002.
M. Dorigo, L. M. Gambardella: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, 1996.
L. M. Gambardella, M. Dorigo: Ant-Q: A Reinforcement Learning approach to the traveling salesman problem, Proceedings of the Twelfth Intern. Conf. on Machine Learning, 1995, 252-260.
M. Dorigo, G. Di Caro, L. M. Gambardella: Ant Algorithms for Discrete Optimization, Proceedings of the Congress on Evolutionary Computation, Vol 2, pp. 1470-1477, IEEE Press, 1999.
T. Stützle, H. Hoos: Ameisenalgorithmen zur Lösung kombinatorischer Optimierungsprobleme, Künstliche Intelligenz, 1/01, pp. 45-51, 2001.
T. Stützle, H. Hoos: MAX-MIN Ant System, Future Generation Computer Systems. 16(8):889--914, 2000.
T. Stützle and M. Dorigo: ACO Algorithms for the Traveling Salesman Problem, Evolutionary Algorithms in Engineering and Computer Science, pages 163-183, Wiley, 1999.
T. Stützle, A. Grün, S. Linke, and M. Rüttger: A Comparison of Nature Inspired Heuristics on the Traveling Salesman Problem, Proceedings of PPSN-VI, Sixth International Conference on Parallel Problem Solving from Nature, volume 1917 of LNCS, pages 661-670, 2000.
O. Cordon, F. Herrera, and T. Stützle: A Review on the Ant Colony Optimization Metaheuristic: Basis, Models and New Trends. Mathware and Soft Computing, 9(2-3), pp. 141--175, 2002.
K. Krishnan, S. Hossein Cheraghi: Ant Algorithms: Review and Future Applications, IERC'02, Industrial Engineering Research Conference, 2002.

Vergleichende Literatur

Ein Kapitel von D. S. Johnson und L. A. Mc Geoch im oben aufgeführten Buch von Aarts und Lenstra (gibt's bei den Veranstaltern)
C. H. Papadimitriou, S. Vempala: On the Approximability of the Traveling Salesman Problem, extended abstract, STOC 2000, Portland Oregon USA.
I. Lee: Artificial Intelligence Search Methods for Multi-Machine Two-Stage Scheduling, SAC '99, San Antonio Texas USA.
S. Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems, Journal of the ACM, Vol. 45, No. 5, September 1998, pp753-782

Vorträge

Folien der schon gelaufenen Vorträge zum Downloaden:

Ausarbeitungen

Stefan Kopp,
Nadine Leßmann,
Alf Kranstedt,

13.11.2003

16.10.2003	Die Veranstalter	Einführung und Organisatorisches
23.10.2003	Die Veranstalter	Einführungsvortrag zur Problematik P/NP
30.10.2003	Die Veranstalter	Suchverfahren
6.11.2003	Olaf Graeser	Tabusuche
13.11.2003	Walli Hein	Dynamisches Programmieren
20.11.2003	Adam El Sayed Auf / Kai Linnemann	Genetische/Evolutionäre Algorithmen I
27.11.2003	Adam El Sayed Auf / Kai Linnemann	Genetische/Evolutionäre Algorithmen II
4.12.2003		fällt aus
11.12.2003	Frank Schönmann	Lineares Programmieren: Cutting-planes
18.12.2003	Jan Lümkemann	Kooperatives Lernen: Ant Colonies
8.1.2004	Christoph Niehaus	Randomisierte Verfahren: Simulated Annealing, Monte Carlo
15.1.2004	Tolga Dalman	Quantencomputing
22.1.2004		fällt aus
29.1.2004		fällt aus
5.2.2004		Abschlußdiskussion