Description:
In der Kombinatorischen Optimierung geht man von einer Problemstellung des folgenden Typs aus: Gegeben sei eine endliche Menge V sowie eine Abbildung f: V->R. Gesucht ist ein Element von V mit größtem f-Wert. Ist das Problem schwierig, etwa NP-vollständig, ist man gezwungen, Algorithmen zur exakten Lösung des Problems durch Heuristiken zur Bestimmung einer oder mehrerer suboptimaler Lösungen zu ersetzen. Statt der unabhängigen Ermittlung von k solchen Lösungen bietet sich die Alternative an, nur L=k-1 suboptimale Lösungen v1,vL in V unabhängig zu bestimmen und diese in die Ermittlung einer (L+1)-ten suboptimalen Lösung v(L+1) aus V miteinzubeziehen. Im Fall V={0,1}n und L ungerade besteht eine Möglichkeit hierfür darin, einen Konsens aus v1,vL mit vj = (v_1j,v_2j,v_nj) für j=1, L im folgenden Sinne zu bilden: In der i-ten Komponente (i=1,n) eines neuen Vektors v aus V wird der mehrheitlich vorkommende Eintrag aus v_i1, v_i2, v_iL übernommen (Mehrheitsbildung). Die Erwartung ist, dass die Heuristik bei Eingabe von v zu einer suboptimalen Lösung v(L+1) führt, die besser als v1,vL ist. Im Rahmen der Dissertation werden experimentelle Ergebnisse bei verschiedenen Optimierungsproblemen mit Lösungsraum {0,1}n vorgestellt. Mehrheitsbildung wird sowohl einstufig als auch wiederholt zur Rekombination in Genetischen Algorithmen untersucht. Ferner werden randomisierte Varianten der Mehrheitsbildung diskutiert. Bei Max-SAT-Problemen, Dynamischen Optimierungsproblemen, Ising-Spinglas-Problemen und Shiftregister-Problemen lässt sich beobachten, dass die verwendeten Heuristiken besonders bei großen Problemparametern von einem Einsatz der Mehrheitsbildung profitieren. Über die randomisierten Mehrheitsbildungen im {0,1}n hinaus wird eine spezielle Konsensbildung bei Scheduling-Problemen behandelt, nämlich die Mittelwertbildung der Anfangszeiten von Tasks. Auch bei dieser Art der Konsensbildung treten ähnliche Effekte wie bei der Mehrheitsbildung im {0,1}n auf.