Optimization

Question 1

COSA erklären

Answer 1

Cooperative Simulated Annealing (COSA) übernimmt von Genetischen Algorithmen die Idee einer Population und den Informationsaustausch zwischen Individuen. Von Simulated Annealing werden die ausschließliche Verwendung von Mutationsnachbarschaft und die Wahrscheinlichkeit der Transition mit p = e^(-DeltaE/T) übernommen. Anschaulich laufen mehrere SA Prozesse parallel ab, die durch cooperative transitions miteinander verbunden sind.

Question 2

0-1 Knapsack mit A*

Answer 2

Als Schätzer h’ nimmt man den Zielfunktionswert den man erhielte, wenn x1 … xn nicht ganzzählig sein müssten, d.h. xi wird zu 0 <= xi <= 1 relaxiert. Damit wurde der Schätzer optimistisch gewählt und eine Optimallösung wird garantiert.

Question 3

VNS erklären (wenn mithilfe Pseudo Codes, muss er erklärt werden)

Answer 3

Bei der Initialisierung wird das set of neighborhood structures N_k für k = 1 bis k_max festgelegt. Es wird eine Initiallösung generiert und eine Endbedingung festgelegt.

Bis die Endbedingung erfüllt ist wird folgendes wiederholt:

1) Setze k = 1
2) solange k < k_max wiederhole:
2a) Es wird durch Shaking ein zufälliger Punkt x’ in der Nachbarschaft von x erzeugt
2b) x’ dient als Initiallösung für die lokale Suche. x’’ ist das lokale Optimum der lokalen Suche
2c) Wenn x’’ besser als x ist, so wird x zu x’’ aktualisiert und die Suche wird mit N1(k

Question 4

Nenne 2 Arten von VNS und ihre Funktionsweise

Answer 4

Reduced VNS (RNS) verhält sich wie VNS, nur ohne die lokale Suche

Skewed VNS, welches schlechtere Lösungen in einem vorgegeben Intervall akzeptiert um weiter entfernte Täler zu untersuchen (und aus eventuellen Sackgassen auszubrechen)

Question 5

Variable Neighborhood Search for Vehicle Routing Problems with Drones (VNS for VRPD)

Answer 5

repeat
k t_max
return x;

Question 6

Wie können sich BNN in Abhängigkeit der Beweislage ändern und was sind Beliefs?

Answer 6

Die P(x | e), welche dem Knoten zugeordnet werden, ändern sich in Abhängigkeit der Beweislage. Die beweisabhängigen Wahrscheinlichkeiten eines Knoten x, auch Beliefs genannt, schreibt man als BEL(x). Bei neuer Beweislage werden die Wahrscheinlichkeiten mittels PI- und LAMBDA-Nachrichten geupdated.

PI: Kausalinformationen, die sich in Richtung der Kanten ausbreiten

LAMBDA: Diagnostische Informationen, die sich entgegen der Kantenrichtung ausbreiten