Algorithmen

beendete Branch-and-Bound-Verfahren

2.1.1Übergeordnet: Metaheuristiken
    Nachteil von lokalen Suchverfahren (Heuristiken) ist, dass diese nur die unmittelbare Nachbarschaft einer gegebenen Startlösung nach Verbesserungsmöglichkeiten durchsuchen. Diese lokale Suche führt oft dazu, dass ausschließlich ein lokales Optimum ermittelt wird. Um das zu vermeiden, werden häufig Metaheuristiken eingesetzt. Dabei handelt es sich um allgemeine, d. h. problemunabhängige Verfahrensansätze. Im Gegensatz zu den lokalen Suchverfahren lassen diese während des laufenden Suchprozesses auch Verschlechterungen der gefundenen (und im weiteren Suchprozess verwendeten) Lösungen im Bezug auf die Zielfunktion zu, um das Festlaufen in lokalen Optima zu vermeiden. Abbildung 2 verdeutlicht diesen Umstand. Dargestellt ist die grafische Repräsentation der Lösungswerte in Form einer Funktion. Das Ziel besteht darin, den minimalen Wert zu ermitteln. Dazu startet ein Verbesserungsverfahren mit der Ausgangslösung y1 ,das durch einen oder mehrere Züge zum lokalen Minimum y2 gelangt. Das globale Minimum y* wird jedoch nicht erreicht. Dazu kann es hilfreich sein, temporäre Verschlechterungen des Zielwerts zu akzeptieren (zum Beispiel den Wert y3 ) und von dort aus gegebenenfalls das globale Minimum y* zu erreichen. Da die Anwendung von Metaheuristiken nicht auf eine bestimmte Problemstellung beschränkt ist, bedienen sie sich problemspezifischer Heuristiken. Die Grundideen von Metaheuristiken sind oft bestimmten Vorgängen in der Natur nachempfunden. Bekannte Metaheuristiken sind der Ameisenalgorithmus , Genetische Algorithmen sowie das Simulated-Annealing und davon abgeleitete Verfahren. Wir werfen einen Blick auf diese Verfahren.

    Abbildung 2: Das Prinzip der Lösungssuche mittels Metaheuristiken [16]

2.1.2Evolutionäre Strategien und Genetische Algorithmen
    Die Überschrift verrät es bereits. Diese Klasse von Verfahrensansätzen wird direkt aus den natürlichen Prozessen der Natur abgeleitet. Eine Auffrischung der grundlegenden biologischen Kenntnisse ist daher hilfreich. Evolutionäre Strategien und Genetische Algorithmen gehören zu den so genannten Evolutionären Algorithmen. Beide sind populationsbasierte Verfahren, die sich am Vorbild natürlicher Fortpflanzungsprozesse und an Erkenntnissen der Vererbungslehre orientieren. Grundgedanke ist die Nachbildung der natürlichen Evolution (Weiterentwicklung, Verbesserung und Eliminierung von Arten), um diese für Optimierungsprobleme nutzbar zu machen. Auch die Terminologie wurde weitgehend aus der Biologie übernommen. Nachfolgend werden die Ideen der Genetischen Algorithmen und der Evolutionären Strategien vorgestellt. Die Konzeption der Genetischen Algorithmen geht auf Holland und Goldberg zurück [5], [6].
    Genetische Algorithmen werden zur Steuerung von Nachbarschaftssuchverfahren und Konstruktionsheuristiken eingesetzt. Konstruktionsheuristiken dienen dazu, eine erste zulässige Lösung zu erzeugen, die dann für eine spätere Verbesserung zur Verfügung steht. Nachbarschaftssuchverfahren durchsuchen den Lösungsraum nach verbesserten Ergebnissen mit Blick auf die Zielstellung (Zielfunktion) des Verfahrens. Für die Anwendung wird zunächst eine Ausgangspopulation (eine Menge von zulässigen aber verbesserungsbedürftigen Lösungen) benötigt. Diese kann beispielsweise mithilfe einer problemspezifischen Heuristik erzeugt werden. Die Individuen der Ausgangspopulation (Elterngeneration) werden durch eine Fitnessfunktion bewertet, die sich im Regelfall aus der Zielfunktion des Optimierungsproblems ableitet und den Grad der Zielerreichung angibt. Die Elterngeneration dient der Erzeugung von Nachkommen mithilfe der Operatoren Selektion , Rekombination und Mutation . Auf die erzeugten Nachkommen wird ebenfalls die Fitnessfunktion angewendet. Die Güte einer Lösung ist auch ausschlaggebend für den Einfluss der erzeugten Lösung auf den nachfolgenden Reproduktionsprozess. Ziel ist es, nach Möglichkeit erwünschte Eigenschaften zu vererben und nicht erwünschte Eigenschaften frühzeitig auszusortieren. Selektion, Reproduktion und Bewertung werden solange wiederholt, bis ein Abbruchkriterium erreicht ist. Das kann zum Beispiel eine bestimmte Anzahl von Iterationen, eine maximale Rechenzeit oder ein bestimmtes Niveau des Zielfunktionswerts sein.
    Im Unterschied zu Evolutionären Strategien arbeiten Genetische Algorithmen mit codierten Lösungen, die als Chromosomen bezeichnet werden.