Ans  ätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren  I

Inhaltsverzeichnis

1.  Einleitung  1

2.  Gegenüberstellung von ein- und mehrdimensionalen Optimierungsproblemen  3

3.  Das Instrument zur interaktiven mehrdimensionalen Entscheidungsfindung  5

3.1  Prozedurinteraktivität  5

3.2  Die Alternativenauswahl bei Mehrdimensionalität  6

3.2.1  Probleme bei der Alternativenauswahl  6

3.2.2  Mehrfache Nutzenmerkmaltheorie und Familie der  7

Indifferenzmethoden   

  (Multiple Attribute Utility  

Theory  and family of outranking methods)  

3.2.3  Das Axiom der begrenzten Vergleichbarkeit  8

  (axiom of limited comparability)  

3.2.4  Das verdichtete System der Präferenzverhältnisse  9

  (consolidated system of preference relations CSPR)  

4.  The Light Beam Search  10

4.1  Entstehungsgeschichte  10

4.2  Methodik  11

4.2.1  Problemstellung und Definitionen  12

4.2.2  Optimierungsprozedur  13

4.3  Vergleich mit anderen Verfahren  18

5.  Schlussbetrachtung  20

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 1

1. Einleitung

Entscheidungsprobleme treffen den Menschen in allen Lebensphasen und -lagen. Entscheidungen lenken sowohl das individuelle als auch das kollektive Verhalten einzelner Personen und Gruppen, ja ganzer Gesellschaftssysteme. Das Vorbereiten, das Treffen und nichtzuletzt das Verantworten der Konsequenzen von Entscheidungen wird in der Wissenschaft als ein typisch menschliches Problemfeld gesehen und behandelt. „Das Entscheidungsproblem hebt den Menschen einerseits von den übrigen Lebewesen und

andererseits von noch so intelligenten Maschinen ab“ ¹ . Noch schwerwiegender als obengenannte Entscheidungen einzelner, sind die Entscheidungen sozialer Systeme, also dem Zusammenschluss von mehr oder weniger umfangreichen Personenmehrheiten, wie etwa Unternehmungen. „Die Konsequenzen versäumter oder sachlich verfehlter Entscheidungen von sozialen Systemen wirken in der

Regel massiver und nachhaltiger als die Fehl-Entscheidungen eines einzelnen“ ² . Die extremste Folge eines kollektiven Irrtums auf Unternehmensbasis ist der Zusammenbruch der Unternehmung. Entscheidungen sind also in der Unternehmung von existentieller Bedeutung und eng mit dem Wohlergehen der Unternehmung verbunden. Deshalb ist eine systematische Entscheidungsfindung für solche sozialen Systeme von großer Bedeutung. Bei der Betrachtung des Gesamtaufgabenkomplexes einer Unternehmung ist zu unterscheiden zwischen sog. Entscheidungsaufgaben und Ausführaufgaben. Der Bearbeiter ist genau dann zur Entscheidung gezwungen, wenn das Mittel zur definierten Zielerreichung bei gegebener unternehmensexterner bzw. -interner Bedingungslage noch nicht eindeutig als

Ausführungsvorgabe definiert ist, also eine Wahlhandlung vonnöten ist. ³ Da heutige Entscheidungsprobleme in ihrer Art und ihrem Umfang immer komplexer und schwerwiegender werden, ist ein systematisches Vorgehen bei der Suche nach dem realisierbaren Optima unumgänglich. Thema dieser Seminararbeit ist der „Light Beam Search“ (LBS) , ein interaktives Optimierungsverfahren, erarbeitet von Andrzej Jaszkiewicz und Roman Slowinski. Es hilft dem Bearbeiter eines Optimierungsproblems beim Auffinden des Punktes, in dem eingesetzte Produktionsfaktoren und Produktionsergebnis ein Optimum ergeben. Bei Betrachtung der Entwicklung der interaktiven Prozeduren zeigt sich ein wachsendes Interesse an Verfahren, die dem Optimierer in jeder Entscheidungsphase eine Handvoll von unabhängigen Punkten, anstelle eines einzelnen Punktes zur Auswahl stellt.

¹ vgl. Bronner, S. 9

² vgl. Bronner, S. 11

³ vgl. Porzelt, S. 29

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 2

Dies rührt von der Absicht her, eine immer größere Vielfalt an Informationen in die Suche nach dem Optimum mit einzubeziehen, die der vorher gemachten Definition der

Präferenzinformation willkürlich innewohnen ⁴ . Das LBS-Verfahren baut auf diesen Anforderungen auf.

Der erste Teil dieser Arbeit beschäftigt sich mit der Gegenüberstellung von ein- und mehrdimensionalen Optimierungsproblemen, so dass die Problematiken der Mehrdimensionalität und der mit ihr verbundenen Wahlmöglichkeit erkannt und beschrieben werden können.

Es wird fortgefahren mit der Abhandlung über mehrdimensionale Entscheidungsfindungsinstrumente. Im Laufe dieser Abhandlung wird eine interaktive Prozedur vorgestellt, um dem Leser die namensgebende „Interaktivität“ zu verdeutlichen. Desweiteren geht dieses Kapitel auf die Alternativenauswahl und die mit ihr verbundene Problematik ein. Im Zuge dessen werden sukzessiv Lösungsmöglichkeiten für auftretende Probleme vorgestellt, so z.B. das Axiom der begrenzten Vergleichbarkeit (axiom of limited comparability). Die Vorstellung dieser Verfahren mündet in der Feststellung einer begrenzten Anwendbarkeit, die die Autoren zur Erarbeitung des „Light Beam Search“ Verfahren veranlasste.

Der dritte Abschnitt widmet sich dem oben genannten „Light Beam Search“ Verfahren. Es werden seine Entstehungsgründe dargestellt und in aller Ausführlichkeit das Verfahren erklärt. Fortgefahren wird mit einem Vergleich zwischen dem LBS Verfahren und anderen populären Verfahren der mehrdimensionalen Optimierungsproblematik. Der letzte Abschnitt beinhaltet die Schlussbetrachtung. Hier wird ein Fazit gezogen, das vorgestellte Verfahren kritisiert und ein Ausblick auf mögliche Weiterentwicklungen gegeben.

Allgemein ist beim Verfassen der Arbeit darauf geachtet worden, mathematische Formeln, die für das Verfahren eine große Bedeutung besitzen, zu erwähnen, da sie das Verständnis für das Verfahren verbessern.

⁴ vgl. Jaszkiewicz / Slowinski, S.300

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 3

2. Gegenüberstellung von ein- und mehrdimensionalen Optimierungsproblemen

Es stellt sich die Frage, was der Unterschied zwischen ein- und mehrdimensionalen Optimierungsproblemen ist.

Zu eindimensionalen Optimierungsproblemen kann gesagt werden, dass sie die einfachste Form des Entscheidungsproblems darstellen, wie sie einem Menschen tagtäglich begegnen können. So ist z.B. die Entscheidung beim Einkauf zwischen zwei gleichwertigen Produkten mit unterschiedlichem Preis ein eindimensionales Entscheidungsproblem, wenn der Käufer nur Wert auf die Preise als Entscheidungskriterium legt. Dem Entscheidungsträger, hier der Einkäufer, stehen eindeutige Entscheidungsdaten zur Verfügung: die Preise der Produkte. Ist eines der sonst gleichwertigen Produkte billiger, wird die Entscheidung zugunsten dieses Produkts ausfallen. Es gibt für den Entscheidungsträger also nur ein einziges Kriterium, das ausschlaggebend für die Wahl ist, in diesem Fall der Preis. Diese Eindimensionalität ist aber die Ausnahme.

Allgemein ist über Entscheidungsmodelle zu sagen, dass sie eine formale Darstellung eines Entscheidungsproblems darstellen, dass wenigstens eine Alternativenmenge X und wenigstens eine auf diese definierte Zielfunktion z enthält. Die Elemente x ∈ X sind die zur

Auswahl stehenden Alternativen. Diese Alternativenmenge heißt auch Zulässigkeitsbereich. Sie wird durch Gleichungen und/oder Ungleichungen beschrieben, den sogenannten

Nebenbedingungen. 5

Handelt es sich bei den oben genannten Alternativen um Vektoren, so liegt eine Mehrdimensionalität vor. Genauer gesagt heißt das, wenn bei einem Optimierungsproblem mehr als ein Kriterium mit zur Entscheidung beiträgt, dann handelt es sich um ein mehrdimensionales Optimierungsproblem. Bezogen auf einen Automobilbauer könnte ein stark vereinfachtes mehrdimensionales Optimierungsproblem z.B. den Preis eines Stoßdämpfers und den mit diesem Modell verbundenen Komfort in Betracht ziehen. Aufgabe des Entscheidungsträgers ist es nun, ein Optimum aus Preis und Komfort, sprich durch den Fahrer empfundener Qualität des Autos, zu finden. „Die Beschäftigung der Entscheidungstheorie mit Entscheidungsproblemen bei mehrfacher Zielsetzung resultiert aus der Tatsache, dass die Suche nach einer Entscheidung in realen Entscheidungssituationen sich häufig nicht nur an einer einzigen Zielgröße orientiert. Folglich verlangt eine realitätsnähere

⁵ vgl. Dinkelbach, S. 1

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 4

Abbildung des Entscheidungsproblems im Modell die Berücksichtigung des gesamten

Katalogs der verfolgten Zielsetzungen.“ 6

Bei typischen Entscheidungsproblemen werden häufig Parameter miteinander verglichen, die zunächst als nicht vergleichbar eingestuft würden. Der Entscheidungsträger verfolgt bei seinem Optimierungsproblem K Zielsetzungen. Werden die K Zielfunktionen zu

der vektorwertigen Zielfunktion (z 1 (x), ... , z k (x)) ^T zusammengefasst, so lässt sich das Entscheidungsproblem bei mehrfacher Zielsetzung durch die Aufgabe

darstellen. Wenn nun für dieses Problem eine Lösung x ^o ∈ X existiert, reduziert sich das x ^o ∈ X heißt genau dann Entscheidungsproblem auf eine Aufgabe mit einer Zielsetzung.

perfekte Lösung zum obigen Vektormatrixproblem, wenn für jedes k = 1, ... , k die Beziehung

gilt.

Interessant im Rahmen der Entscheidungstheorie mit mehrfacher Zielsetzung sind aber diejenigen Fälle, bei denen mindestens zwei der K Ziele konkurrieren, d.h. „falls für mindestens zwei der K Zielfunktionen die zugehörigen Mengen der Optimallösung disjunkt

sind“. ⁷ Dies ist z.B. der Fall bei umwelttechnischen Optimierungsproblemen, wenn es um die Abwägung zwischen Umweltverträglichkeit und Effektivität der Anlage geht. In diesen Fällen hat der Entscheidungsträger zwischen verschiedenen ihm unterbreiteten Möglichkeiten zu wählen. Er wird eine Handlungsalternative x aber nur dann als Lösung des Entscheidungsproblems anerkennen, falls kein Zielfunktionswert ohne Verschlechterung der anderen Zielfunktionswerte verbessert werden kann.

Die oben beschriebenen Optimierungsprobleme lassen sich erweitern, indem man davon ausgeht, dass die Werte der Zielfunktionen z k , k = 1, ... , K, nicht nur von der Wahl der

⁶ vgl. Wolf, S. 14

⁷ ebenda, S. 15

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 5

Lösung x abhängen, sondern noch eine zweite Variable Einfluss nimmt auf die

Zielfunktionswerte, und zwar die Faktorenumwelt. ⁸ Nimmt man z.B. an, dass die Variable S diese erfolgswirksamen Zustände der Umwelt charakterisiert, dann ergibt sich für die k-te Zielsetzung die Formulierung:

Die weitere Behandlung des Problems soll hier nicht näher beschrieben werden.

3. Das Instrument der mehrdimensionalen Entscheidungsfindung

3.1 Prozedurinteraktivität

Die Interaktivität spielt bei den Entscheidungsprozessen eine große Rolle. Sie ist es, die dem Entscheidungsträger die Möglichkeit gibt, Einfluss zu nehmen auf den weiteren Verlauf des Entscheidungsprozesses. Interaktivität ist laut Duden definiert als Dialog zwischen Computer

und Benutzer. ⁹ Lässt man zunächst einmal die praktische Durchführung von Entscheidungsprozessen mittels Computerunterstützung außen vor und betrachtet nur den prinzipiellen Aufbau einer solchen Prozedur, so ist mit Interaktivität der Dialog zwischen Entscheidungsträger und Prozedur gemeint, also die Miteinbeziehung des Entscheidungsträgers in die Suche nach dem Optimum für ein Optimierungsproblem. Einstiegspunkt einer interaktiven Entscheidungsprozedur ist die Definition von Präferenzinformationen, also solchen Definitionen, die nach Ansicht des

Entscheidungsträgers erfüllt sein müssen, damit das Ergebnis überhaupt realisierbar bzw. sinnvoll ist. Als Beispiel sollen hier die für den Bau einer chemischen Anlage vorgegebenen Präferenzinformationen herangezogen werden. Es gibt in diesem Beispiel genau 4 Variablen, die zur Betrachtung herangezogen werden müssen: Als erstes ist das Reaktorvolumen V zu nennen, das minimiert werden soll. Die zweite Variable ist das Gewicht des Katalysators W ct , welches ebenfalls zu minimieren ist. Als dritte Variable ist die Produktionsmenge P A des eigentlichen Endproduktes p-xyclene, einem chemischen Basisstoff, zu nennen, welche zu maximieren ist. Abschließend soll noch die Konzentrationsrate CR zwischen p-xylene und o-

⁸ ebenda,S. 29

⁹ vgl. ebenda

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 6

xylene maximiert werden. ¹⁰ Die Konzentrationsrate ist ausschlaggebend für die Qualität des Endproduktes und für den Umwandlungsgrad von o-xylene, d.h. mit der Effizienz des Prozesses. Anhand dieser Präferenzinformationen ist ein Optimierungspunkt zu bestimmen, der alle vorgegebenen Bedingungen bestmöglich erfüllt. Charakterisiert werden interaktive Prozeduren durch die Einteilung des Entscheidungsprozesses in verschiedene Entscheidungsphasen, in denen dem Entscheidungsträger jeweils ein Zwischenergebnis präsentiert wird. Das Problem, das bei dieser Vorgehensweise auftritt, ist die Tatsache, dass vom Entscheidungsträger in jeder Entscheidungsphase erwartet wird, ein mehrdimensionales Optimierungsunterproblem aus einem explizit gegebenem Alternativenset zu lösen.

3.2 Die Alternativenauswahl bei Mehrdimensionalität

3.2.1 Probleme bei der Alternativenauswahl

Bisherige interaktive Optimierungsverfahren basieren auf der stillen Annahme, dass ein Entscheidungsträger einen paarweisen Vergleich zwischen den Punkten eines Alternativsets ohne weitere Informationen durchführen kann. Diese Vorgehensweise führt aber schon bei kleinen Alternativsets zu Problemen. Zahllose psychologische Untersuchungen zeigen immer wieder die begrenzte Fähigkeit des Entscheidungsträgers, mehrere gleichzeitig gegebene Informationen aufzunehmen und zu verarbeiten.

Verdeutlicht werden soll das Problem der Informationsverarbeitung an einem Beispiel

von Hahneman ¹¹ : Es werden zwei Gruppen gebildet, denen jeweils eine Zahlenreihe vorgelegt wird, die es zu multiplizieren gilt. Der ersten Gruppe wird das Produkt in absteigender, der zweiten Gruppe in aufsteigender Reihenfolge vorgelegt. Beiden Gruppen bleiben 5 Sekunden, das Endergebnis abzuschätzen.

Die Erfahrung zeigt, dass es eine typische Vorgehensweise ist, die ersten Rechenschritte durchzuführen und aufgrund dieses Ergebnisses eine Schätzung des eigentlichen Wertes durchzuführen. Diese Schätzung beruht auf Extrapolation. Da diese Abschätzungen prinzipiell

¹⁰ vgl. Jaszkiewicz / Slowinski, S. 311

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 7

unzureichend sind, führt dieses Verfahren aber erfahrungsgemäß zu einer Unterschätzung des wahren Ergebnisses. Desweiteren sollte die Abschätzung der ersten Gruppe größer ausfallen als die der zweiten Gruppe, da, ausgehend von Berechnungen von links nach rechts, die Rechenschritte der ersten Gruppe ein höheres Ergebnis haben als die der zweiten Gruppe. Eine Untersuchung bestätigte diese Annahme. Der durchschnittliche Schätzwert der aufsteigenden Reihe ist 512, wohingegen der durchschnittliche Schätzwert der Gruppe mit der absteigenden Zahlenreihe bei 2250 lag. Beide Ergebnisse liegen weit unter dem eigentlichen Ergebnis von 40320. Dieses Phänomen ist auch bekannt unter dem Namen anchoring. Diese Beispiel zeigt deutlich, dass nicht nur die Anzahl der zu verarbeitenden Informationen für den Entscheidungsträger ein Problem darstellt, sondern auch die Art und Weise der Präsentation, die aufgrund unbewusst angewandter Lösungs- und Abschätzungsverfahren zu verschiedenen Ergebnissen führen kann.

3.2.2 Mehrfache Nutzenmerkmaltheorie und Familie der Indifferenzmethoden

Nach Jaszkiewicz und Slowinski kann dem Entscheidungsträger bei lokalen Entscheidungsproblemen durch die beiden folgenden Verfahren geholfen werden: Der mehrfachen Nutzenmerkmaltheorie und der Familie der Indifferenzmethoden. Die mit und in diesen Methoden verwendeten Präferenzmodelle unterstützen den Entscheidungsträger bei seinem lokalen multikriteriellen Vergleich, indem Präferenzinformationen ausgewertet werden. Diese Informationen sind vom Entscheidungsträger formuliert bzw. angegeben worden. Eine bei der ´Mehrfachen Nutzenmerkmaltheorie´ häufig kritisierte Eigenschaft ist ihre Transitivität in Bezug auf die Indifferenzbeziehung. Transitivität ist wie folgt definiert: Ÿ a < c a < b b < c

Diese Transitivität ist es, die der Existenz einer Indifferenzregion im Wege steht. Die Indifferenz wird durch ein unzureichendes Modell oder die Unfähigkeit des Entscheidungsträgers hervorgerufen, marginale Unterschiede, d.h. eventuelle Vor- und

Nachteile eines Kriteriums, zu erkennen. ¹² Desweiteren gibt es in diesem Modell keinen Bereich der Schwachen Präferenz (weak-preference). In diesem Bereich kann der Entscheidungsträger nicht genau zwischen Indifferenz und Präferenz unterscheiden, er schwankt folglich zwischen beiden Zuständen. Eine weitere realistische, aber durch dieses Modell nicht darstellbare Situation ist die der Nichtvergleichbarkeit (incomparability)

¹¹ vgl. ebenda, S.14f

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 8

aufgrund eines Mangels an Präferenzinformationen. Diese Unterscheidungen bzw. Relationen sind aber bei der Suche nach Optimalpunkten von erheblicher Bedeutung, weshalb eine Möglichkeit gefunden werden muss, die vier Konfliktsituationen Indifferenz, absolute Präferenz, schwache Präferenz und Nichtvergleichbarkeit wahrnehmen und unterscheiden zu können. Natürlich ist bei diesen Verfahren auch Vorsicht geboten: Bernard Roy, der das unter 3.2.3 beschriebene ´Axiom der begrenzten Vergleichbarkeit´ formulierte, warnt auch vor den Nachteilen der Indifferenzmethoden. „Je allgemeiner eine Indifferenzrelation gehalten ist, desto risikoreicher. Es besteht die Gefahr, dass die eigentlichen Präferenzen des Entscheidungsträgers misinterpretiert und falsch gedeutet werden und folglich falsche oder

unzureichende Hilfestellung bei der Entscheidungsfindung gegeben werden.“ ¹³ Das oben beschriebene Fehlen der Indifferenzmethoden macht die Mehrfache Nutzenmerkmaltheorie für eine Lösung von Optimierungsproblemen im Sinne von Jaszkiewicz und Slowinski unbrauchbar.

3.2.3 Axiom der begrenzten Vergleichbarkeit

Um eine korrekte Verarbeitung der Präferenzinformationen des Entscheidungsträgers zu gewährleisten, hat Bernard Roy das ´Axiom der begrenzten Vergleichbarkeit´ formuliert, welches die Mängel der ´Mehrfachen Nutzenmerkmaltheorie´ beseitigt. Bei Roy´s Methode gibt es 4 Konfliktsituationen:

Sie ermöglichen dem Entscheidungsträger eine sehr viel genauere Differenzierung seiner Präferenzinformationen. Auf Roy´s Axiom der begrenzten Vergleichbarkeit baut deshalb auch die Europäische Schule der mehrdimensionalen Entscheidungshilfe (MCDA (MultiCriterial Decision Aiding)) auf. Das eigentlich besondere an Roy´s Methode ist nicht nur die Existenz dieser 4 Konfliktsituationen, sondern die Möglichkeit, einem Präferenzmodell bis zu 3 der 4 Konfliktsituationen zuzuordnen, je nachdem, ob der Entscheidungsträger aufgrund der gegebenen Präferenzinformationen „nicht kann, will oder weiß, wie in der gegebenen

¹² vgl. Jaszkiewicz / Slowinski, S. 301

¹³ Roy, S. 184

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 9

Situation zu entscheiden ist“. ¹⁴ Das Axiom nach Roy stellt also für den Entscheidungsträger eine Möglichkeit dar, ein Präferenzmodell zu erstellen, ohne vor die teilweise unlösbare Aufgabe gestellt zu werden, zwei gegebene Modellpunkte miteinander zu vergleichen und direkt als besser oder schlechter für das zu lösende Optimierungsproblem gegeneinander abzuschätzen.

3.2.4 Das verdichtete System der Präferenzverhältnisse

Um diese Präferenzmodelle, die mehreren Konfliktsituationen zugeordnet werden können, muss ein System definiert werden, welches sowohl Indifferenz I (indifference) absolute Präferenz P (strict preference), schwache Präferenz Q (weak preference) und Nichtvergleichbarkeit R (incomparability) beinhaltet. Diese Gruppierung kann nach verschiedenen Methoden vorgenommen werden, den sog. verdichteten Systemen der Präferenzverhältnisse CSPR (consolidated system of preference relations). Die am häufigsten verbreiteten CSPR´s sind diejenigen, die zur Gruppierung die Höherwertigkeits-Relation S (outranking relation) benutzen. Da die Höherwertigkeits -Relation S sowohl I, Q, P und R repräsentiert, steht sie nicht im Widerspruch zum Axiom der begrenzten Vergleichbarkeit nach Roy (s. 3.2.3).

Mit Hilfe diese Systems ist es dem Entscheidungsträger nun erlassen, bei jedem Verfahrensschritt zur Optimierung ein multikriterielles Subproblem zu lösen, da er nun nicht mehr entscheiden muss, ob ein Punkt a indifferent zu einem Punkt b ist, wenn von a angenommen wird, gleichwertig zu b zu sein. Stattdessen kann nun gesagt oder formuliert a S b. werden:

Das bedeutet, dass a und b in einem unter S formulierten Zusammenhang stehen. Der Entscheidungsträger muss bei dieser Formulierung aber nicht entscheiden, ob der Punkt a dem Punkt b immer oder schwach vorgezogen wird, oder ob beide Punkte indifferent sind. Folglich wird mit dem Gebrauch des CSPR erreicht, dass Punkte in eine Beziehung gesetzt werden, ohne schon eine direkte Wertung vorzunehmen. Da S, wie oben beschrieben, sowohl Indifferenz I, schwache Präferenz Q, absolute Präferenz P und Nichtvergleichbarkeit R repräsentiert, ergibt sich folgende Logik-Tabelle:

¹⁴ vgl. Jaszkiewicz / Slowinski, S. 301

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 10

Tabelle 1: System of preference relation

Die erste Zeile der Tabelle sagt aus, dass b in einer outranking-relation zu a steht und a ebenfalls in einer ebensolchen zu b, folglich sind a und b indifferent (I). Genauso sind die weiteren Angaben der Tabelle zu interpretieren. Jaszkiewicz und Slowinski betonen ausdrücklich, dass vom Entscheidungsträger in der Praxis nicht verlangt wird, über den Wahrheitsgehalt der Indifferenzrelation für jedes Alternativenpaar zu urteilen. Vielmehr wird die Indifferenzrelation auf dem verfügbaren Alternativenset mit Hilfe der verfügbaren Präferenzinformationen aufgebaut, um schließlich Antworten auf das Entscheidungsproblem zu geben. Jaszkiewicz und Slowinski wollen das verdichtete System der Präferenzverhältnisse dahingehend abgeändert sehen, dass die vom System gegebenen Untersuchungspunkte einige Bedingungen erfüllen. So sollen die Punkte, die in das System aufgenommen werden für den Entscheidungsträger nicht unvergleichbar sein und außerdem sollen nicht alle Punkte indifferent sein. Wenn diese Bedingungen nämlich nicht eingehalten werden, kann es dazu führen, dass der Entscheidungsträger sich für eine Lösung entscheidet, die weit entfernt ist von der bestmöglichen Lösung.

4. The Light Beam Search

4.1 Entstehungsgeschichte

Die Entstehungsgeschichte der interaktiven Prozeduren zeigt einen Trend hin zu Verfahren, die den Entscheidungsträger ein Bündel von Optimalpunkten präsentiert. Diese Optimalpunkte sind qualitativ alle gleichwertig, können sich in ihren quantitativen Ausprägungen aber unterscheiden. Da der Entscheidungsträger im Zuge dieser Entwicklung

immer mehr vor das Problem gestellt wird, mehrdimensionale Unterprobleme zu lösen ¹⁵ , mussten ihm Hilfsmittel zur Hand gegeben werden, die ihn bei diesen Entscheidungen unterstützen. Jaszkiewicz und Slowinski halten das unter 3.2.2 beschriebene Verfahren der ´Familie der Indifferenzmethoden´ bei der Entscheidungsfindung für hilfreich. Entstanden ist

¹⁵ vgl. Jaszkiewicz / Slowinski, S.301

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 11

es aus dem ´Axiom der begrenzten Vergleichbarkeit´ (axiom of limited comparability), das den Vergleich zweier Alternativen, wie unter 3.2.3 beschrieben, erheblich vereinfachte. Der ´Light Beam Search´ (LBS) ist also ein zwar selbständiges

Entscheidungsinstrument, aber aus bestehenden Verfahren abgeleitet zu einem nach Meinung der Autoren anwendungsfreundlichem Instrument, das dem Entscheidungsträger hilft, den bestmöglichen Kompromiss aus Leistungsfähigkeit und Wirtschaftlichkeit zu finden.

4.2 Methodik

Aus den in Kapitel 3 beschriebenen Vor- und Nachteilen der jeweiligen Methoden haben Jaszkiewicz und Slowinski die nach ihrer Meinung wichtigen und entscheidenden Punkte als Anforderung an ein System zur Unterstützung bei mehrdimensionalen

Optimierungsproblemen formuliert. Demnach ist die Untersuchung des nicht-dominierten Sets, also dem Bereich, der für die Lösung des Problems in Frage kommt, gekennzeichnet durch die Betrachtung der Umgebung des momentanen Mittelpunkts, einem vom Optimierer ausgewähltem Punkt, der sich mit seinen Ansprüchen deckt. Dieser Mittelpunkt kann sich aus 2 Gründen verschieben, entweder bei Änderung der durch den Entscheidungsträger an diesen Punkt gestellten Anforderungen, oder aufgrund einer Verbesserungsmöglichkeit, die sich innerhalb des betrachteten Sets erreichen lässt. Der neue Optimalpunkt bildet dann den Mittelpunkt. Ein weiteres grundlegendes Merkmal des von Jaszkiewicz und Slowinski entwickelte Light Beam Search Verfahrens ist die sogenannte Indifferenz-Relation (outranking-relation), also die Bewertungsrelation zweier Punkte, die hier als lokales Präferenzmodell benutzt wird. Sie basiert allerdings auf, wie unter 3.2.4. beschrieben, relativ schwachen Präferenzinformationen. Die Nachbarschaft des momentanen Mittelpunkts besteht aus nicht-dominierten, also unbeeinflussten Punkten, die dem Mittelpunkt gleichzustellen sind, also qualitativ mit ihm vergleichbar sind. Punkte außerhalb der Nachbarschaft sind entweder nicht vergleichbar oder werden vom momentanen Mittelpunkt mit seinen

Eigenschaften als Lösung des Optimierungsproblems übertroffen. ¹⁶ Nachfolgend wird expliziter auf die Verfahrensweise eingegangen.

¹⁶ vgl. Jaszkiewicz / Slowinski, S. 302

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 12

4.2.1 Problemstellung und Definitionen

Um das Verfahren des ´Light Beam Search´ genau erläutern zu können, müssen zunächst einige Begriffe eingeführt und definiert werden. Ein allgemeines mehrdimensionales Optimierungsproblem kann folgendermaßen beschrieben werden:

Tabelle 2: Optimierungsproblem

Dabei ist x = [x 1 ,...,x j ] ein Vektor von Entscheidungsvariablen und die Funktionen f j , j=1,...,j sind stetig und differenzierbar. Ziel dieses Optimierungsproblems ist es also, diejenige Situation zu bestimmen, die einen Maximalwert für das Optimierungsproblem darstellt. Wie unter 4.2 angedeutet, wird dem Entscheidungsträger bei seiner Suche nach einem Optimalpunkt ein Set von Punkten präsentiert, die alle qualitativ gleichwertig sind, sich vom Rest der möglichen Punkte aber dadurch unterscheiden, dass sie nicht-beeinflusst sind. Ein Punkt z´ ∈ Z gilt als nicht-beeinflusst, wenn es kein z ∈ Z gibt, so dass z j t z j ´ ∀ j , und

z i > z i ´ für wenigstens ein i. Die Sammlung aller nicht-beeinflussten Punkte heißt nicht-beeinflusstes Set. 17

Ein weiteres Hilfsmittel zur Optimalpunktbestimmung ist die ´Wertungstabelle´ (pay-off table). Sie ermöglicht es, einen Überblick über die dem Entscheidungsträger präsentierten Optimalpunkte zu gewinnen, indem alle Punkte in einer Tabelle dargestellt werden:

Tabelle 3: pay-off table

z erhält. j *j z stellt dabei einen Optimalpunkt dar, den man durch Einzelmaximierung von i z

i

bezeichnet den Wert des i-ten Objekts in Punkt *j z .

¹⁷ vgl. ebenda, S. 303

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 13

Ein weiteres wichtiges Instrument ist die ´Funktion zur Abschätzung der Verbesserung´ `Verbesserungsabschätzungsfunktion´(achievement scalarizing function):

Tabelle 4: achievement scalarizing function

[ ]

Dabei ist [ ]

Zahl ist. Die Verbesserungsfunktion hilft dem Entscheidungsträger beim Auffinden des Optimalpunktes, ist also ein Instrument zur Entscheidungsunterstüzung.

4.2.2 Optimierungsprozedur

Die eigentliche Prozedur der Optimierung, also vom definieren der Präferenzinformationen bis zum Auffinden des gesuchten Optimalpunkts, soll im nun folgenden Kapitel erklärt werden. Um einen Überblick über das Verfahren zu gewinnen, soll die von Jaszkiewicz und Slowinski erstellte Übersicht über das ´Light Beam Search´ Verfahren in einer der Programmiersprache PASCAL ähnlichen Form aufgegriffen und von dort aus erklärt werden. Ausgehend von den vom Entscheidungsträger vorab zu definierenden angestrebten Punkten (aspiration points) und denjenigen Punkten die erreichbar sind (reservation points), wird von der Prozedur der sog. Mittelpunkt errechnet, von dem ausgehend die weitere Optimierung stattfindet. Nun muss der Entscheidungsträger die lokalen

Präferenzinformationen festlegen, damit eine Indifferenzrelation (outranking-relation) erstellt werden kann. Repeat

Dem Entscheidungsträger ist der Mittelpunkt zu präsentieren, außerdem müssen die charakteristischen Nachbarn des Mittelpunkts bestimmt werden und dem Entscheidungsträger präsentiert werden. Der Entscheidungsträger erhält die Möglichkeit, die Nachbarschaft des präsentierten Mittelpunkts zu untersuchen. IF

Wenn der Entscheidungsträger den betrachteten Mittelpunkt für geeignet erachtet,

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 14

Then

kann er ihn zum Set der gespeicherten Punkte hinzufügen.

erreichbare Punkte definieren möchte, kann er dies nun tun. Der neue angestrebte Punkt wird dann auf das nicht-beeinflusste Set projiziert. Falls er einen neuen Mittelpunkt aus der Nachbarschaft wählen möchte, kann er dies nun tun.

Der Entscheidungsträger kann hier zu einem zuvor gespeicherten Punkt zurückkehren, dieser Punkt ist dann erneut Mittelpunkt. Der Entscheidungsträger kann an diesem Punkt aber auch die Präferenzinformationen ändern. End Until

Dieser Prozedurschritt wiederholt sich solange, bis der Entscheidungsträger mit dem während der interaktiven Prozedur gefundenen Ergebnis zufrieden ist, oder erkennt, dass unter den

gegebenen Rahmenbedingungen kein Kompromiss gefunden werden kann. 18

Diese Darstellung präsentiert aber nur einen Überblick über die Verfahrensweise des LBS. Im folgenden wird das Verfahren explizit beschrieben. In jeder Berechnungsphase der LBS Prozedur wird ein sog. nicht-beeinflusstes Set von Punkten generiert, das sich aus einem in einem vorherigen Prozedurschritt bestimmten Mittelpunkt und J nicht-beeinflussten, d.h. voneinander unabhängigen, Punkten zusammensetzt. Die unter 3.2.4 beschriebene Indifferenz-Relation (outranking relation) wird hierbei benutzt, um eine lokale Präferenzen zu definieren. Genauer gesagt bedeutet das, dass für einen momentanen Mittelpunkt die Nachbarschaft so definiert ist, dass sie qualitativ besser als der momentane Mittelpunkt ist, d.h. höherrangig ist. Die J Punkte aus dem Nachbarschafts-Set geben an, inwieweit die einzelnen Objekte der Punkte im Verhältnis zum momentanen Mittelpunkt verbessert werden können (vgl. pay-off Table). Sie werden die charakteristischen Nachbarn des Mittelpunkts genannt. Im Allgemeinen gibt es in der (qualitativ) höherwertigen Nachbarschaft nicht nur Punkte, die dem momentanen Mittelpunkt qualitativ überlegen sind, sondern auch solche, die mit ihm gleichzusetzen sind. Dies bedarf einer Erklärung: Angenommen die zwei Vektoren A und B werden miteinander verglichen.

¹⁸ vgl. Jaszkiewicz / Slowinski, S. 304 f

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 15

A ist der momentane Mittelpunkt der Optimierungsprozedur, und zwar im oben beschriebenen Sinne. Würde man nun sagen das Vektor B den Vektor A ´outrankt´, würde das bedeuten, dass Vektor B im Verhältnis zu Vektor A als qualitativ höherwertig, also als bessere Lösung für das Optimierungsproblem, angesehen wird. Würde nun aber zudem noch festgestellt, dass Vektor A den Vektor B ebenfalls ´outrankt´, wird davon ausgegangen, dass A und B indifferent sind, also qualitativ absolut gleichwertig. Keiner der beiden Vektoren würde dem anderen vorgezogen werden. Die übrigen Punkte der höherwertigen Nachbarschaft (outranking neighborhood) sind weiterhin als bevorzugt dem bestehenden Mittelpunkt gegenüber einzustufen. Der Entscheidungsträger hat beim ´Light Beam Search´ Verfahren also die Möglichkeit, zwischen 2 Punkten der Nachbarschaft, zu der auch der Mittelpunkt zählt, zu wechseln, und zwar auf den Zielfunktionstrajektorien, also den durch die Präferenzinformationen vorgegebenen Realisationswegen. Bei der Bewertung der Präferenzpunkte

kann der Entscheidungsträger auf die ´Wertungstabelle´ (pay-off table) zurückgreifen. Sie kann dem Entscheidungsträger, wie oben beschrieben, beim Vergleich der Optimalpunkte behilflich sein.

Den Anfangsmittelpunkt z c erhält man, indem man den Punkt z r in Richtung von z v in das nicht-beeinflusste Set projiziert, was prinzipiell nichts anderes bedeutet, als das Optimierungsproblem unter gegebenen Präferenzinformationen und Restriktionen durch Gebrauch eines Gewichtungsfaktors zu lösen. Wichtig zu erwähnen ist die Definition des

bereits unter 4.2.1 erwähnten Gewichtungsfaktors . Er wird von den beiden Punkten z r und z > . Daraus ergibt sich für den Gewichtungsfaktor ¹⁹ z v definiert, und zwar so, dass v r z

j j

¹⁹ vgl. . Jaszkiewicz / Slowinski , S. 304

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 16

Zur Bestimmung der höherrangigen Nachbarschaft werden lokale Präferenzinformationen bestehend aus dem Indifferenzschwellwert q i , dem Präferenzschwellwert p j und dem Vetoschwellwert v j herangezogen. Alle diese Schwellwerte sind Funktionen von z j , so dass bestimmte Schwellwerte charakteristisch sind für einen bestimmten Mittelpunkt. Die Existenz von Indifferenzschwellwert und Präferenzschwellwert erlaubt die Unterscheidung zwischen Indifferenz (indifference) und den Präferenzschwellwerten schwachem Vorzug (weakly preferred) und starkem Vorzug (strictly preferred). Der Vetoschwellwert ist hilfreich bei einem Vergleichsproblem zweier Alternativen, wenn eine der beiden in einem Punkt signifikant besser ist, aber in einem anderen Punkt sehr viel schlechtere Werte aufweist als die b a andere. Nach der Definition der Indifferenz-Relation (outranking relation) ist eine z S z + ≥ ^{a b} v z z falsche Aussage, wenn für wenigstens ein j gilt . Diese Situation wird

j j j

Vetopräferenz von z ^b über z ^a genannt. Im folgenden werden nun die Schwellwerte erklärt, die dann letztendlich in Verbindung mit der ´Höherwertigkeitsrelation´ (outranking relation)

definieren, wann ein Punkt z höherwertiger als der aktuellen Mittelpunkt z c ist. Dazu müssen zunächst folgende Funktionswerte berechnet werden:

Die Kardinalitätsfunktion card zählt dabei alle Elemente, die die angegebene Bedingung erfüllen. Nun muss aber noch festgelegt werden, welche Bedingungen erfüllt sein müssen,

damit ein Punkt z den Mittelpunkt z c outrankt, also höhergestellt ist als er. Diese ´Höherwertigkeitsrelation´ (outranking relation) wird hier folgendermaßen formuliert:

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 17

Tabelle 5: Definition der Höherwertigkeitsrelation

Diese Tabelle sagt aus, dass wir die Vetopräferenz bei der folgenden Bestimmung der Nachbarschaft des momentanen Mittelpunkts außen vor lassen. Wenn es dahingegen eine

starke Präferenz eines Punktes z gegenüber dem momentanen Mittelpunkt z c gibt, wird er diesem vorgezogen. Wenn aber keine starke Präferenz eines Punktes z über einen Punkt z c existiert, dann kann eine schwache Präferenz für einige Objekte durch eine größere Anzahl an Objekten, die den Punkt z bevorzugen, kompensiert, d.h. abgelöst werden. Um die

charakteristischen Nachbarn des momentanen Mittelpunkts z c festzustellen, werden Gradienten bestimmter Objektausprägungen auf eine lineare Approximation der im Punkt z c gültigen Bedingungen projiziert. ²⁰ Das bedeutet, dass diejenigen Punkte in der Nachbarschaft um z c ausfindig gemacht werden, die die Bedingungen und Einschränkungen des Mittelpunktes z c erfüllen. Dafür muss zunächst unter Zuhilfenahme einer Matrix A, die die Bedingungen und Einschränkungen beinhaltet, eine Projektionsmatrix P = I - A T (AA T ) -1 A errechnet werden. Diese Matrix liefert in Zusammenhang mit den Gradienten bestimmter ∆ innerhalb des Variablenraums, in der die größten j Objektausprägungen die Richtungen x

∆ werden weitergehend dazu benutzt, j Verbesserungen möglich sind. Diese Richtungen x

korrespondierende Richtungen V ^j zu ermitteln, in denen eine Verbesserung des momentanen Zustands im Objektraums erreicht werden kann. Dies bedeutet, dass man über die Veränderlichen des Prozesses Einfluss nimmt auf die Objektzustände. Wenn wir die einzelnen

Verbesserungsschritte, die erreicht werden können, wenn man z c in Richtung von V ^j verändert, als α bezeichnet, dann verbessert sich der Wert von z j für jeden Schritt, in dem α > 0 ist. Dabei muss aber beachtet werden, dass der Punkt z´ ^j = z ^c + α V ^j das Set der nicht-

beeinflussten Punkte verlassen kann. Es ist also Aufgabe des Entscheidungsträgers, das

optimale α zu finden, so dass gilt:

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 18

Es wäre dann gewährleistet, dass α einen Maximalwert darstellt, also ein Optimalpunkt

erreicht wäre, der aber wiederum im Bereich der realisierbaren Punkte liegt, also zulässig ist.

Die charakteristischen Nachbarn eines Mittelpunktes erhält man als Projektion des Punktes z´ ^j auf das nicht-beeinflusste Set nach Lösung des Minimierungsproblems

In der nun folgenden Entscheidungsphase werden dem Entscheidungsträger der Mittelpunkt und verschiedene charakteristische Nachbarn präsentiert. Desweiteren kann der Entscheidungsträger die höherwertige Nachbarschaft zwischen zwei charakteristischen Nachbarn und zwischen einem charakteristischem Nachbarn und dem Mittelpunkt betrachten. Jeder der Punkte, die dem Entscheidungsträger präsentiert werden, werden dem momentanen Punkt entweder vorgezogen oder sind gleichwertig zu ihm. Sobald einer der Punkte alle Forderungen des Entscheidungsträgers erfüllt, wird die Optimierungsprozedur angehalten. Wie oben beschrieben, kann der Entscheidungsträger bei Unzufriedenheit aber die Prozedur dahingehend fortführen, dass er neue angestrebte bzw. erreichbare Punkte definiert, so dass ihm neue Optimalpunkte präsentiert werden. Ein momentaner Mittelpunkt kann, bevor zu einem neuen Mittelpunkt übergegangen wird, gespeichert werden, damit eventuell zu einem späteren Zeitpunkt, falls sich der Entscheidungsträger mit dem neu gefundenen Mittelpunkt nicht zufrieden gibt, zu ihm zurückgekehrt werden kann. Zum Abschluss des LBS-Verfahrens, kann der Entscheidungsträger noch einmal die Präferenzinformationen jedes einzelnen Objekts, d.h. den Indifferenz-, Präferenz- und Vetoschwellwert (s.o.) verändern.

4.3 Vergleich mit anderen Verfahren

Das ´Light Beam Search´ Verfahren besitzt, im Gegensatz zu anderen Verfahren zur mehrdimensionalen Optimierung, zwei Freiheitsgrade, um die Suche nach dem Optimalpunkt zu überwachen. Der erste Freiheitsgrad ist die Möglichkeit, die angestrebten und überhaupt erreichbaren Punkte zu definieren. Der angestrebte Punkt wird dabei auf das nichtbeeinflusste Set projiziert. Ähnlich verfahren wird beim Interactive Goal Verfahren nach

²⁰ vgl. Jaszkiewicz / Slowinski, S. 306

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 19

Franz und Lee ²¹ und diversen anderen Verfahren. Was das LBS-Verfahren gegenüber diesen Verfahren auszeichnet, ist das Vorhandensein seines zweiten Freiheitsgrades, der den Entscheidungsträger während der Optimierungsprozedur aktiv unterstützt, wie z.B. auch beim Interval Criterion Weights method. Der zweite Freiheitsgrad erlaubt aus einer endlichen Menge nicht-beeinflusster Punkte die Auswahl eines neuen Mittelpunkts. Diese Kombination des ersten und zweiten Freiheitsgrades bringt Vorteile mit sich, die andere Verfahren der mehrfachen Optimierung nicht haben. Durch die Möglichkeit, die erreichbaren und angestrebten Punkte zu definieren, erlangt der Entscheidungsträger grundlegende Kontrolle über die Optimierungsprozedur. Der Entscheidungsträger kann durch dieses Verfahren den gesamten nicht-beeinflussten Raum, d.h. den gesamten Lösungsraum des Optimierungsproblems untersuchen. Dadurch hat er die Möglichkeit, das Problemfeld besser kennenzulernen und so eine nahezu optimale Lösung des Problems zu finden. Da der Entscheidungsträger seine Optimierung erst dann beenden wird, wenn er keine Möglichkeit zur Verbesserung mehr sieht, spricht man bei diesem, wie auch bei weiteren Verfahren, von einer intuitiven Konvergenz. Aufgrund des Aufbaus der Optimierungsprozedur ergibt sich somit eine nahezu hundertprozentige Annäherung an das Optimum. Diese Eigenschaft hat wie andere auch wiederum das Interval Criterion Weights Verfahren nach Steuer. Eine experimentelle Untersuchung bestätigt die Vorteile von Verfahren, die eine Kombination der 2 Freiheitsgrade benutzen. Buchanan, Daellenbach und Corner haben bei ihren

Untersuchungen festgestellt ²² , dass diejenigen Verfahren, die den Entscheidungsträger bei der Auswahl der bevorzugten Punkte unterstützen von den Teilnehmern bevorzugt wurden vor solchen, die dem Entscheidungsträger zwar ein Set von Alternativen präsentieren, ihm aber keine Informationen darüber liefern, welche zu bevorzugen sind. So wurden von den meisten Testteilnehmern das Naive Verfahren und das Interactive Weighted Tchebycheff Verfahren, beide geben den Benutzern die oben genannten 2 Freiheitsgrade, denjenigen Verfahren vorgezogen, die das utility function Verfahren, welches nur einen Freiheitsgrad gewährt, zur Annäherung an den Optimalpunkt verwendeten. Doch wurde an den beiden Verfahren auch kritisiert: So wurde zwar festgestellt, dass das Interactive Weighted Tchebycheff Verfahren leicht zu verstehen sei, einfach in der Anwendung und hohe Sicherheit gewährleistet, doch wurde bei den meisten Testpersonen im Verlauf des Tests festgestellt, dass sie sich scheuen, oder einfach nicht fähig sind, aus den konvergierenden Objektsets dasjenige auszuwählen, dass das vermeintlich Beste darstellt. Es wurde die Unterstützung des Entscheidungsträgers durch die Prozedur vermisst. Das Naive Verfahren führt zwar relativ schnell dem

²¹ vgl. Jaszkiewicz / Slowinski, S. 308

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 20

Optimallösungsbereich, doch beim Suchen des besten Kompromisses ist die Vorgehensweise doch eher planlos und die Entscheidungsträger tendieren dazu, bereits nach den ersten Verbesserungsschritten die Prozedur abzubrechen, das sog. anchoring. Diese Kritik verlangte also nach einem kombinierten Verfahren, dass anstatt den gesamten Lösungsbereich (nondominated set) zu präsentieren, nur die Nachbarschaft der momentanen Lösung als Auswahl vorschlägt. Das ´Light Beam Search´ Verfahren begegnet dem Vergleichsproblem beim Interactive Weighted Tchebycheff Verfahren aufgrund der oben beschriebenen Bedingung der Vergleichbarkeit der die dem Entscheidungsträger präsentierten Punkte unterliegen. Das beschriebene frühzeitige Festlegen (anchoring) (vgl. Kapitel 3.2.1) wird beim LBS Verfahren dadurch reduziert, dass dem Entscheidungsträger in jedem Prozedurschritt mehrere Nachbarschaftspunkte gleichzeitig präsentiert werden.

5. Schlussbetrachtung

Das ´Light Beam Search´ Verfahren ist entwickelt worden, um einen Entscheidungsträger beim Auffinden des besten Punktes eines Optimierungsproblems aktiv zu unterstützen. Ausschlaggebend für seine Entwicklung war die Erkenntnis, dass es für Menschen ein Problem darstellt, aus einer Menge von vorhandenen Punkten denjenigen auszuwählen, der für ein gegebenes Problem die Optimallösung darstellt. Die mehrdimensionale Zielsetzung stellt ein Problem dar, die eine eindeutige Lösung der Aufgabe nicht zulässt, da „die [...] interessantesten Fälle vorliegen, falls mindestens zwei der K Ziele untereinander konkurrieren, d.h. falls für mindestens zwei der K Zielsetzungen die zugehörigen Mengen der Optimallösungen disjunkt sind.[...]Es wird also angenommen, dasss keine perfekte Lösung für

das Vektormatrixproblem existiert.“ 23

Das LBS-Verfahren ist eine interaktive, lernorientierte Suche eines Kompromisses aus einer Menge unbeeinflusster Punkte, die alle eine mögliche Lösung eines Problems darstellen. Die Kombination aus herkömmlichen Suchverfahren und der erweiterten Betrachtung der Eigenschaften einer Alternative aufgrund der Höherwertigkeits-Relation (outranking relation) stellt die Neuerung des Verfahrens dar.

Durch die Kombination der oben erwähnten zwei Freiheitsgrade wird eine Einflussnahme des Entscheidungsträgers auf die Entwicklung der Optimierungsprozedur zugelassen, die bisher in keinem anderen Verfahren vorhanden war. Die Prozedur und das

²² vgl. Jaszkiewicz / Slowinski, S. 308f

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 21

Problem selbst werden für den Entscheidungsträger transparenter und die gefundenen Lösungen repräsentieren in einer stärker als bisher dagewesenen Weise ein Optimum. Die Formulierung einer Höherwertigkeits-Relation (outranking relation) bewahrt den Entscheidungsträger davor, sich für oder gegen eine Alternative auszusprechen, was ansonsten dem zu vermeidenden Lösungsversuch eines mehrdimensionalen Optimierungsproblems entsprechen würde.

Doch das ´Light Beam Search´ Verfahren ist nicht zur Lösung aller Optimierungsprobleme mit mehrdimensionaler Zielsetzung geeignet. Die Wahl des Lösungsverfahrens für ein Optimierungsproblem hängt vorwiegend von zwei Bedingungen ab: 1. Der mathematischen Beschaffenheit des Problems und

2. Der Bereitschaft des Entscheidungsträgers, das Problem mit diesem Verfahren zu lösen.

Das erste ist dabei als objektives Problem zu behandeln, wohingegen der zweite Punkte auf das Zusammenspiel zwischen Entscheidungsträger und Prozedur anspielt. Dieses Verhältnis ist ausschlaggebend für den Erfolg des Optimierungsprozesses. Wenn der Entscheidungsträger nämlich von den von der Prozedur vorgeschlagenen Alternativen und der Art und Weise, wie sie ermittelt wurden, nicht überzeugt ist, und Ergebnisse angezweifelt werden, dann verfehlt das Verfahren zum Teil sein Ziel, den Entscheidungsträger für das bestehende Problem zu sensibilisieren und Verständnis entstehen zu lassen. Fehlt jedoch dieses Verständnis sowohl für das Verfahren als auch für das Problem, kann das LBS-Verfahren nicht entsprechend arbeiten und das Ergebnis kann unzureichend sein. ²⁴ Und dort liegt auch die Schwachstelle des Verfahrens. Ein Entscheidungsträger kann leicht Zweifel bekommen über die Art und Weise, wie die ihm präsentierten Punkte überhaupt entstanden sind, das Prinzip der Höherwertigkeits-Relation (outranking relation) bedarf in allen Fällen einer Erklärung, da ansonsten die für das Verfahren wichtige Vertrauen in die Prozedur nicht aufgebaut werden kann. Es sind aber die oben beschriebenen positiven Merkmale der Höherwertigkeits-Relation, die letztendlich überwiegen. Sie ermöglicht eine sehr viel differenziertere Behandlung des Problems, als es mit anderen Verfahren, wie z.B. der Mehrfachen Nutzenmerkmaltheorie (Multiple Attribute Utility Theory), möglich ist.

²³ vgl. Wolf, S. 15

Ansätze des "Light Beam Search": Grundlagen und Überblick über bestehende Verfahren 22

Literaturverzeichnis

Bronner, Rolf: „Grundlagen der Entscheidungsfindung“ aus der Reihe Arbeitshefte Führungspraxis 5, Verlag der modernen Industrie, München 1980

Jaszkiewicz / Slowinski: „The Light Beam Search approach - an overview of methodology and applications, in European Journal of Operational Research 113 (1999)

Wolf, Hartmut: „Entscheidungsfindung bei der stochastischen linearen Optimierung durch Entscheidungsmodelle mit mehrfacher Zielsetzung“ aus der Reihe mathematical systems in economics, Verlagsgruppe Athenäum / Hain / Hanstein, Königstein/Ts., 1983

Dinkelbach, Werner: „Operations Research“, Heidelberger Lehrtexte, Springer Verlag Berlin Heidelberg 1992

DUDEN - Die deutsche Rechtschreibung, Bibliographisches Institut & F.A. Brockhaus AG, Mannheim, 1996

Kahnemann, D., Slovic, P., Tversky, A.: „Judgement under uncertainty: Heuristics and Biases“, Cambridge University Press, Cambridge, 1982

Roy, Bernard, „How outranking relation helps multiple criteria decision making“ in „multiple criteria decision making“ von James L. Cochrane, University of South Carolina Press, Columbia, South Carolina, 1973

Porzelt, Ulrich, Dr., „Universalmethoden der Entscheidungsfindung und die praxisorientierte Analyse ihrer Anwendbarkeit in absatzwirtschaftlichen Aufgabenstellungen“ in „betriebspolitische Schriften, Beiträge zur Unternehmenspolitik“ Band 25, herausgegeben von Prof. Dr. Carl W. Meyer, Würzburg, Verlag Duncker & Humblot, Berlin, 1982

²⁴ vgl. Jaszkiewicz / Slowinski

1

Stichworte aus ´The Light Beam Search´ - an overview of methodology and applications

1. Introduction and motivations

• LBS wurde zur Behandlung von Vielfachobjektanalysen von linearen und

nichtlinearen Programmen erfunden.

• Entwicklungsstand des LBS wird aufgezeigt an verschiedenen existierenden

interaktiven Prozeduren, zu denen auch der LBS gehört.

• Überblick über die Entwicklung der interaktiven Prozeduren zeigt ein wachsendes

Interesse an Prozeduren, die dem DM in jeder Entscheidungsphase eine handvoll von nicht-beeinflussten Punkten an die Hand gibt, anstelle eines einzelnen Punktes. Dies kommt von der Absicht, eine immer grössere Vielfalt an Informationen in die Entscheidungsfindung eines neuen Vorschlags/Entscheidungsrichtung mit

einzubeziehen, die der Definition der Präferenzinformation willkürlich innewohnen.

• Die Klasse der interaktiven Prozeduren, denen das iterative präsentieren von Bsp.

nicht-beeinflusster Punkte innewohnt, gehören folgende Verfahren an:

• In jeder Entscheidungsphase wird vom DM erwartet, eine Präferenzinformation basierend auf multikriterieller Entscheidungsfindung auszuwählen. « es wird der

vermeintlich beste Punkt in der Sammlung ausgewählt. Problem dabei: es wird vom DM erwartet, in jeder Entscheidungsphase ein multikriterielles

Entscheidungsfindungsproblem aus einer eingeschränkten Menge zu lösen.

Die oben genannten Verfahren basieren also auf der stillen Annahme, dass ein DM einen paarweisen Vergleich eines explizit gegebenen AlternativSets ohne weitere

Informationen durchführen kann. « führt schon bei kleinen Alternativsets zu

Problemen.

• Nach Meinung der Autoren kann dem DM bei diesem lokalen Entscheidungsproblem

durch folgende Verfahren geholfen werden:

• Das 1. Verfahren (Multiple Attribute Utility Theory) wird aufgrund seiner Annahme

kritisiert, da es keine Indifferenz-Region (indifference) zulässt. Sie „würde nur durch ein unzureichendes Modell oder die Unfähigkeit des DM hervorgerufen, die marginalen Unterschiede zu erkennen“. Desweiteren gibt es keinen Bereich des weakpreference, in dem der DM nicht genau zwischen Indifferenz und Präferenz unterscheiden kann, er schwankt zwischen beiden Zuständen. Desweiteren gibt es bei diesem Tool nicht die Möglichkeit der incomparability, aufgund des Mangels an Bewertungsmöglichkeit.

2

• Diese Mängel werden bei Roy´s Methode durch das axiom of limited comparability

abgedeckt (4 Konfliktsituationen: indifference I, strict preference P, weak preference Q, incomparability R). Auf diesem Axiom gründet sich die European school of MCDA.

Nach diesem Verfahren ist es möglich, einer Situation eine oder mehrere Eigenschaften zuzuordnen, je nachdem ob der DM nicht anders kann, oder will. Die Gruppierung kann nach verschiedenen Methoden vorgenommen werden, den sog. consolidated system of preference relations (CSPR). Am häufigsten sind CSPR´s die die outranking relation S benutzen. Da S sowohl I, Q, P und R repräsentiert, steht S im Einklang mit dem axiom of limited comparability.

• Das Problem bei diesem Verfahren ist der möglicherweise gezwungene Vergleich

zwischen Punkten, die eigentlich unvergleichbar sind. Dies führt zu möglichen Fehlinterpretationen und das interaktive Verfahren wird gestoppt, noch bevor der beste

Punkt erreicht worden ist. « all dies führt zum LBS

• Grundlegende Kennzeichen des LBS:

Diese Eigenschaften erinnern an eine Taschenlampe, dessen fokussierter Lichtstrahl auf den Mittelpunkt der betrachteten Ebene scheint. (daher LBS). Die ersten Entwürfe des LBS stammen von Jaskiewicz und Slowinski (1993, 1995).

• Die outranking relation wurde auch im Aspiration-Level interactive Model (Lofti et

al., 1992) benutzt. Sie ist allerdings beschränkt auf eine mehrfachobjekt Analyse mit einem begrenzten Alternativset. In diesem Fall kann dem DM die gesamte Nachbarschaft zur Entscheidungsfindung vorgelegt werden. Die Benutzung der outranking-relation zur interaktiven Untersuchung eines Sets multikriterieller Alternativen ist beschrieben bei Jaskiewicz und Slowinski (1997a).

3

3. Description of the LBS

• In jeder Berechnungs-/Bestimmungsphase der LBS-Prozedur wird eine endliche

Menge an non-dominated points generiert. Ausgangspunkt ist jeweils der sog. middlepoint, der aus einer vorherigen iterativen Annäherung stammt. Die Menge besteht sowohl aus diesem Mittelpunkt, als auch aus J non-dominated points aus der Nachbarschaft des Mittelpunkts. Diese Nachbarschaft (neighborhood) wird auch als outranking neighborhood bezeichnet und vereint Punkte, die nicht schlechter als der Mittelpunkt sind, d.h. ihn outranken. Die J Punkte dieser Menge zeigen an, zu welchen Zuständen die einzelnen Untersuchungsobjekte gelangen können; immer in bezug auf gleichbleibende Qualität im Sinne der duch den DM definierten Standards.

• In der sog. outranking neighborhood existieren aber auch Punkte, die vom Mittelpunkt

outgerankt werden. Diese Punkte sind indifferent zum Mittelpunkt, wohingegen die übrigbleibenden Punkte des neighborhood dem Mittelpunkt vorgezogen werden.

• Der DM hat beim LBS die Möglichkeit zwischen 2 Punkten der Nachbarschaft(hierzu

zählt auch der Mittelpunkt) zu switchen, indem er sich auf den Objektfunktionstrajektorien (und nur hier) zwischen zwei Punkten bewegen kann.

• Der LBS-Algorithmus kann in folgender Form beschrieben werden: s. S.304 f

• Bei der Feststellung der Präferenzpunkte kann der DM auf die Pay-off Tabelle

zurückgreifen.

• z r : starting aspiration point z v : reservation point z c : starting middle point

• den starting middle point erhält man, indem man den Punkt z ^r in das non-dominated Set in Richtung von z ^v projeziert.

• Das outranking neighborhood wird durch die vom DM vorgegebenen Präferenzen um den Punkt z ^c gebildet.

• Die vorgegebenen Präferenzen bestehen aus veschiedenen Schwellwerten:

• es wird angenommen, das die zu erfüllenden Einzelmerkmale alle mit demselben Grad

gewichtet werden. (s. S.305 rechtsmitte)