Weitere Ansätze
Next: Unergiebige Ansätze Up: Lösungsansätze Previous: Negotiation
Weitere Ansätze
- Neuronale Netze:
- Wie in Kapitel 3.4 gezeigt wurde, kann das Suchproblem durch das Problem der minimalen unabhängigen Knotenmenge in einem Graphen modelliert werden. Dies ist einer Bearbeitung mit neuronalen Netzen unmittelbar zugänglich, indem das Netz isomorph zum Graphen aufgebaut wird und sämtliche Neuronen alle ihrer Nachbarn hemmen; für komplexere Fälle siehe z.B. [MM96]. Zur schnelleren Ermittlung eines möglichen stabilen Zustands des Netzes wird häufig das sogenannte mean field annealing eingesetzt, das aber [ECF97] gemäß nur für kleinere Problemstellungen geeignet ist. Beschreibungen derartiger Versuche finden sich in [GPS92].
- Beam Search
- ist ein Backtracking\ Verfahren, wobei jeweils eine Menge möglicher Lösungsansätze , der Beam, simultan untersucht wird ([CK93],[CK95b]). Die jeweils besten Kandidaten verbleiben im Beam. Das Verfahren stellt somit eine Kombination von Backtracking und Genetischen Algorithmen dar.
- Memetische Algorithmen
- basieren auf der Vorstellung daß Informationen von Person zu Person weitergegeben werden [BNW95]. In der konkreten Implementierung für das Timetabling-Problem wurde von obigen Autoren so vorgegangen, daß einem genetischen Algorithmus ein Abstiegsverfahren als Filterroutine zugeordnet wurde, so daß stets nur lokale Minima zur Weitervermehrung zur Verfügung stehen - also so, als ob vor Weitergabe der Information eine Person diese noch optimieren würde. Es bleibt allerdings fraglich, ob dieses Vorgehen die Funktion des Mutations-Operators nicht untergräbt.
- Goal Programming:
- Einige Autoren [WW98] verwenden diesen Begriff zur Beschreibung eines Optimierungsproblems,
bei dem Bedingungen zwischen Constraints und Zielfunktion ausgetauscht werden können. Dahinter verbirgt sich zumeist
normale lineare Programmierung.
(c) Martin Loehnertz 1999