4.2.7.1 Optimale Anzahl an Hill-Climbing-Runden & Wahl des nächsten Teilbündels

Um zu ermitteln, wieviele Runden des Hill-Climbings bei welcher Wahl des nächsten Teilbündels den schnellsten Algorithmus ergibt, wurden Versuche gemacht. Der BranchSPMamp;
[4]Bound-Algorithmus wurde wie beschrieben implementiert. Bei der Berechnung der Startlösung wurde vorgegeben, wie oft eine zufällige Startlösung generiert werden soll, die dann per Hill-Climbing verbessert wird.

Da noch nicht klar ist, welche Reihenfolge der Festlegung der einzelnen Schlüsselfaktoren die Beste ist, werden für die folgenden Versuche zuerst die Schlüsselfaktoren mit weniger Projektionsmöglichkeiten festgelegt.

5000-mal wurden zufällige Konsistenzmatrizen erzeugt. Die Größe der Matrizen entspricht dabei Werten von praktischen Anwendungen des Szenario-Managements. Dazu wurden insgesamt 20 Schlüsselfaktoren benutzt. Davon haben 10 Schlüsselfaktoren zwei Projektionsmöglichkeiten und die anderen 10 Schlüsselfaktoren haben drei Projektionsmöglichkeiten. Insgesamt 12 Inkonsistenzen werden zufällig in die Konsistenzmatrix eingefügt.

   

Abbildung: durchschnittliche Laufzeiten des Branch&Bound-Algorithmus mit den zwei Methoden der Wahl des nächsten Teilbündels abhängig von der Zahl der Hill-Climbing-Runden

   

Abbildung: durchschnittlicher Fehler der Startlösung des Branch&Bound-Algorithmus abhängig von der Zahl der Hill-Climbing-Runden

   

Abbildung: durchschnittliche Anzahl berechneter Schranken des Branch&Bound-Algorithmus mit den zwei Methoden der Wahl des nächsten Teilbündels abhängig von der Zahl der Hill-Climbing-Runden

   

Abbildung: durchschnittliche maximale Größe der Menge der offenen Teilprobleme abhängig von der Zahl der Hill-Climbing-Runden bei der Best-First Strategie

iese zufälligen Konsistenzmatrizen wurden mit verschiedenen Anzahlen an Hill-Climbing-Runden bei der Startlösung und mit den zwei Methoden der Wahl des nächsten Teilbündels gelöst. Die durchschnittlichen Laufzeiten sind in Abbildung 4.6 dargestellt. Abbildung 4.7 zeigt den durchschnittlichen Fehler der Startlösung gegenüber der optimalen Lösung. Abbildung 4.8 zeigt schließlich die Anzahl an oberen Schranken, die berechnet werden. Diese Zahl entspricht genau der Zahl der Teilbündel, die vom Algorithmus untersucht werden.

Es ergeben sich daraus folgenden Schlüsse:

• Unabhängig von der Wahl des nächsten Teilbündels ergibt sich der gleiche Einfluß der Anzahl der Hill-Climbing-Runden auf die Laufzeit. Eine einzige Runde führt zu einer größeren Laufzeit. Mit etwas mehr Runden wird der Algorithmus schneller, bis die Laufzeit ein Minimum erreicht. Schließlich steigt die Laufzeit linear mit der Anzahl der Runden.
• Die Anzahl der Hill-Climbing-Runden hat fast keinen Einfluß auf die Zahl der berechneten Schranken, wenn immer das Teilbündel mit der besten Schranke als nächstes bearbeitet wird.
• Die optimale Zahl an Hill-Climbing-Runden bezüglich der Laufzeit des Algorithmus liegt bei den erzeugten Zufallsmatrizen bei 5 bzw. 3 Runden.
• Durch eine gute Startlösung läßt sich die maximale Größe der Menge der offenen Teilprobleme und damit der Speicherverbrauch des Algorithmus verringern.

  Dieser Effekt tritt nur auf, wenn das Teilbündel mit der besten Schranke als nächstes bearbeitet wird. Die andere Auswahlmethode hat den Vorteil, daß der Speicherverbrauch sehr gering ist, da die maximale Größe der Menge der offenen Teilprobleme der Tiefe des Baums entspricht.

• Die Methode, die das tiefste Teilbündel als nächstes bearbeitet, ist unabhängig von der Zahl der Hill-Climbing-Runden schneller als die Methode, die das beste Teilbündel als nächstes bearbeitet.

  Daraus kann man folgern, daß der Aufwand bei der Verwaltung der Teilbündel, wenn immer das beste als nächstes bearbeitet werden soll, größer ist als der Vorteil dieser Methode, daß weniger Schranken berechnet werden müssen.