Generierung von Monte-Carlo-Enumerations-Reihenfolgen bei kombinatorischen Problemen

Betrachtet wird ein System, das n! verschiedene Zustände annehmen kann. Zudem sei eine Zielfunktion gegeben,die jedem System-Zustand einen Wert zuordnet. Gesucht sei der System-Zustand, bei dem der Zielfunktionswert minimal (bzw. maximal) wird. Es soll angenommen werden, daß benachbarte Systemzustände auch ähnliche Zielfunktionswerte besitzen.
Weiterhin soll das System hinreichend kompliziert sein, so daß sich der Zustand mit minimalem (bzw. maximalem) Zielfunktionswert auf analytischem Weg nicht oder nur mit großem Aufwand ermitteln läßt.
Eine Möglichkeit zur Ermittlung des optimalen Zustandes besteht in der Enumeration, d. h. die Systemzustände werden in einer bestimmten Reihenfolge erzeugt und die entsprechenden Zielfunktionswerte dazu berechnet. Nach genau n! Schritten ist die optimale Lösung mit Sicherheit gefunden. Diese Methode ist jedoch nur sinnvoll, wenn wirklich alle n! Zustände geprüft werden können. Falls n! sehr groß ist und die Enumeration wegen begrenzter Rechenzeit vorzeitig abgebrochen werden muß, kann die gefundene beste Lösung jedoch weit vom Optimum entfernt sein (siehe Abbildung weiter unten).
Eine andere häufig angewandte Methode bei Systemen mit großem n! besteht darin, eine Stichproben-Anzahl von Systemzuständen zufällig zu erzeugen und unter diesen den Zustand mit dem minimalen (bzw. maximalen) Zielfunktionswert als Lösung zu verwenden (Monte-Carlo-Methode). Bei dieser Methode wird jeder Systemzustand mit gleicher Wahrscheinlichkeit untersucht, d.h. selbst wenn die Stichprobenanzahl wesentlich kleiner als n! ist, wird eine Lösung ermittelt, die in der Regel nahe am Optimum liegt. Es kann aber bei dieser Methode nie mit absoluter Sicherheit gesagt werden, daß das Optimum gefunden wurde, selbst wenn die Stichprobenanzahl gleich n! oder größer als n! ist. Durch nachfolgende Herleitung und Tabelle wird dies verdeutlicht. Es sei:

N - Anzahl der möglichen Systemzustände (N>>1)
m - Stichprobenanzahl
u - Anzahl der ungeprüften Zustände

Es gilt:

u ( 0 ) = N
u ( m + 1 ) = u ( m ) - u ( m ) / N

u ( m ) / N ist dabei die Wahrscheinlichkeit, daß ein zufällig ausgewählter Zustand noch nicht geprüft worden ist. Bei differentieller Betrachtung ( gültig für N>>1 ) erhält man:

^du/_dm = - ^u/_N => ^du/_u = - ^dm/_N

Mit dem Ansatz u ( m ) = a · exp ( -b · m ) erhält man:

^du/_dm = -b · a · exp ( -b · m) = -b · u ( m ) = - ^u/_N
=> b = ¹/_N
u ( m ) = a · exp ( - ^m/_N )

Durch Einsetzen des Anfangswertes erhält man:

u ( 0 ) = a · exp ( 0 ) = N
=> a = N

Bei einer Stichprobenanzahl m beträgt die Anzahl der ungeprüften Zustände u demnach

u ( m ) = N · exp ( - ^m/_N )

Stichprobenanzahl	Anzahl der geprüften Zustände
0,1 · N	0,095 · N
0,2 · N	0,181 · N
0,5 · N	0,393 · N
1 · N	0,632 · N
2 · N	0,865 · N

Bei N Zuständen und N zufälligen Stichproben werden also mittels Monte-Carlo Methode nur 63,2% aller Zustände wirklich geprüft, da einige Zustände zufällig mehrfach geprüft werden. Ein weiterer Nachteil dieser Methode besteht darin, daß es zu Cluster-Bildung bei den untersuchten Zuständen kommen kann. Das ist dann bedeutsam, wenn mit einem Verbesserungsverfahren in der Nachbarschaft des bisher besten gefundenen Zustandes nach noch besseren Zuständen gesucht werden soll. Wenn der bisher beste gefundene Zustand Teil eines Clusters ist, dann sind einige oder alle benachbarte Zustände bereits untersucht worden und das Verbesserungsverfahren wird dort keine bessere Lösung finden. In der folgenden Abbildung wird dies veranschaulicht, die Menge aller Zustände wird dabei vereinfacht als ein zweidimensionales Gebiet aufgefaßt.

O O O O O O O O O            O O O o o o O O O            X X X X X X X X X            
O X O X O X O X O            O X O O O O O X O            X X X X X X X O O            
O O O O O O O O O            O O O X O O X O O            O O O O O O O O o            
O X O X O X O X O            o O x O O O O O o            o o o o o o o o o            
O O O O O O O O O            O O O O O X O O o            o o o o o o o o o            
O X O X O X O X O            O X O O X X x O o            o o o o o o o o o            
O O O O O O O O O            O O O O O X X O o            o o o o o o o o o            
O X O X O X O X O            o O X O O O O O o            o o o o o o o o o            
O O O O O O O O O            o O O O O X O o o            o o o o o o o o o

Von 81 möglichen Zuständen wurden 16 Stichproben geprüft (Symbol X). Links (Auswahl vorgegeben) wurde jeder Zustand höchstens einmal geprüft, jeder ungeprüfte Zustand (Symbol O) befindet sich in unmittelbarer Nachbarschaft eines geprüften Zustandes. In der Mitte (Auswahl mittels Monte-Carlo-Methode) wurden 2 Zustände zufällig zweimal geprüft (Symbol x), 6 Zustände bilden einen Cluster (fett) und 13 ungeprüfte Zustände (Symbol o) befinden sich nicht in unmittelbarer Nachbarschaft eines geprüften Zustandes. Rechts (Auswahl durch herkömmliche Enumeration) gehören alle geprüften Zustände zu einem Cluster, dabei wurde kein Zustand zweimal geprüft, 55 ungeprüfte Zustände (Symbol o) liegen dabei nicht in unmittelbarer Nachbarschaft eines geprüften Zustandes.

Im folgenden wird eine Methode vorgestellt, die die Vorteile von Enumeration und Monte-Carlo-Methode verbindet und die Nachteile vermeidet. Es handelt sich dabei um eine Enumerations-Reihenfolge für Systeme mit n! Zuständen, so daß bei einer kleinen Stichprobenanzahl die geprüften Zustände zufällig verteilt erscheinen. Es wird jedoch kein Zustand zweimal geprüft. Nach genau n! Schritten sind wie bei der herkömmlichen Enumeration alle Zustände geprüft.
Systeme mit genau n! Zuständen sind z. B. Systeme, die durch die Reihenfolge von n Elementen gekennzeichnet sind. Ein System mit n = 3 (1, 2, 3) kann dabei 3! = 1 · 2 · 3 = 6 Zustände (1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1) annehmen. Ein anderes (aber äquivalentes) Beispiel sind Zuordnungen. Bei der paarweisen Zuordnung der Elemente der Mengen {1, 2, 3} und {a, b, c} gibt es 3! = 6 Zustände (1-a, 2-b, 3-c), (1-a, 3-b, 2-c), (2-a, 1-b, 3-c), (2-a, 3-b, 1-c), (3-a, 1-b, 2-c) und (3-a, 2-b, 1-c). Allgemein kann jeder Zustand eines Systems, das n! Zustände besitzt, durch eine n×n-Zuordnungsmatrix repräsentiert werden. Das Problem des Findens einer Enumerations-Reihenfolge mit den gewünschten Eigenschaften entspricht damit dem Problem des Findens einer Folge von entsprechenden n×n-Zuordnungsmatrizen. Zu einer dem Problemtyp angemessenen Beschreibungsform gelangt man durch die Verwendung kombinatorischer Zahlen. Jede Zuordnungsmatrix läßt sich genau durch eine kombinatorische Zahl darstellen und umgekehrt.

Das kombinatorische Zahlensystem

Das im alltäglichen Gebrauch verwendete Zahlensystem ist das Dezimalsystem. Eine nichtnegative ganze Zahl besteht dabei aus einer Folge von n Ziffern c_n-1c_n-2... c₁c₀ , die jeweils 10 Werte (0 bis 9) annehmen können. Der Wert der Zahl beträgt dabei c_n-1 · 10^n-1 + c_n-2 · 10^n-2 + ... + c₁ · 10¹ + c₀ · 10⁰. In analoger Weise verwendet wird (z. B. bei digitaler Rechentechnik) das duale Zahlensystem mit Ziffern, die 2 Werte (0 und 1) annehmen können und das hexadezimale Zahlensystem mit Ziffern, die 16 Werte (0 bis 9 und A bis F) annehmen können. Zur Unterscheidung vom Dezimalsystem ist es sinnvoll, Zahlen anderer Zahlensysteme durch ein vorangestelltes Symbol zu kennzeichnen, z. B. die Dualzahl 10011 als d10011 und die Hexadezimalzahl A72 durch hA72. Für die Werte dieser Zahlen erhält man im Dezimalsystem:

d10011 = 1 · 2⁴ + 0 · 2³ + 0 · 2² + 1 · 2¹ + 1 · 2⁰ = 16 + 0 + 0 + 2 + 1 = 19
hA72 = 10 · 16² + 7 · 16¹ + 2 · 16⁰ = 2560 + 112 + 2 = 2674

Das kombinatorische Zahlensystem habe die folgenden Eigenschaften: Eine kombinatorische Zahl bestehe aus einer Folge von n Ziffern c_n-1c_n-2... c₁c₀. Dabei kann eine Ziffer c_i jeweils die i+1 Werte 0 bis i annehmen ( i = 0...n-1 ). Der Wert einer kombinatorischen Zahl beträgt c_n-1 · (n-1)! + c_n-2 · (n-2)! + ... + c₁ · 1! + c₀ · 0!. Zur Kennzeichnung wird einer kombinatorischen Zahl stets das Symbol k vorangestellt, z. B. wird die kombinatorische Zahl 31210 als k31210 gekennzeichnet. Der Wert dieser Zahl beträgt im Dezimalsystem:

k31210 = 3 · 4! + 1 · 3! + 2 · 2! + 1 · 1! + 0 · 0! = 72 + 6 + 4 + 1 + 0 = 83

Jede kombinatorische Zahl mit n Ziffern entspricht einer n×n-Zuordnungsmatrix. Der Wert der i-ten Ziffer dieser kombinatorischen Zahl ist dabei gleich der Anzahl der ausgelassenen Zeilen vor Belegung der i-ten Spalte der Zuordnungsmatrix, es wird dabei von links begonnen. Die folgenden drei Beispiele sollen dies verdeutlichen:

 o o o o x         x o o o o         o o o x o
 o x o o o         o x o o o         o x o o o
 o o o x o         o o x o o         x o o o o
 x o o o o         o o o x o         o o x o o
 o o x o o         o o o o x         o o o o x

  k31210            k00000             k21100

Generierung einer Monte-Carlo-Enumerations-Reihenfolge

Zur Ermittlung eines Nachfolgers einer kombinatorischen Zahl in einer Enumerations-Reihenfolge sei die Operation N( k ) = k⁽¹⁾ folgendermaßen definiert: k sei eine kombinatorische Zahl mit den n Ziffern c_n-1c_n-2... c₁c₀.
Die Ziffern der Zahl k' = k⁽¹⁾ = N ( k ) sind dann zu berechnen durch:

d := 1;
for i := n-1 downto 0 do begin
c'_i := c_i + d;
if ( c'_i > i ) then c'_i := 0 else d := 0;
end;

Wird die Operation N ( k ) mehrfach hintereinander ausgeführt, dann kann die folgende Schreibweise verwendet werden:
k^{( 0 )} = k und k^(m) = N ( k^(m-1) ) = N^m ( k ).
Die sich damit ergebende Reihenfolge wiederholt sich bei einem k mit n Ziffern nach genau m = n! Operationen. Die Reihenfolge besitzt jedoch noch nicht die Eigenschaft, daß die Zahlen wie Zufallszahlen verteilt sind. Das ist durch eine Transformation k => k_(o) zu erreichen. Die Transformation muß eineindeutig sein, so daß die k_(o) - Folge ebenfalls wie die k - Folge eine Periodenlänge von n! hat. Eine weitere notwendige Bedingung ist, daß die Transformation nichtlinear sein muß, da sich andernfalls nichts an der Verteilung ändern würde. Eine mögliche Transformation ist die Abwärtsmodulation A(k). k sei eine kombinatorische Zahl mit den n Ziffern c_n-1c_n-2... c₁c₀. Die Ziffern der Zahl k' = k₍₁₎ = A ( k ) sind dann zu berechnen durch:

c'_n-1 := c_n-1;
for i := n-1 downto 1 do c'_i-1 := ( c_i-1 + c'_i ) modulo ( i );

Um eine gute zufallsähnliche Verteilung zu erhalten, ist es ausreichend, die Operation A( k ) mehrfach hintereinander auszuführen (mindestens zweimal, öfter als ⁿ/₂ mal ist nicht sinnvoll). Für mehrfache Abwärtsmodulationen kann dabei die folgende Schreibweise verwendet werden:
k_{( 0 )} = k und k_(o) = A ( k_(o-1) ) = A^o ( k ).
Eine Folge mit den m = n! Gliedern A^o( k^{( 1 )} ) , A^o( k^{( 2 )} ) ... A^o( k^{( m )} ) (bei 1 < o < ⁿ/₂) entspricht einer Enumerations-Reihenfolge mit den gewünschten Eigenschaften. Als Startwert kann dabei für k eine beliebige kombinatorische Zahl mit n Ziffern gewählt werden. Eine kombinatorische Zahl A^o( k^{( i )} ) ist dann jeweils einem Systemzustand zuzuordnen und dieser entsprechend auszuwerten.
Es ist noch zu bemerken, daß die mit diesem Verfahren ermittelte Reihenfolge der Zustände an sich nicht einer Zufallsverteilung ähnelt (das ist hier auch nicht notwendig), sondern die Verteilung der m ausgewählten Zustände (bei m < n!) ähnelt einer Zufallsverteilung.

(c) Lutz Tautenhahn 1998, 1999