Methoden der Optimierung bei mehrfacher

Zielsetzung

Mike Huftle

31. Juli 2006

Inhaltsverzeichnis

1 Optimierung bei mehreren Zielen 21.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Losungsansatze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Losungsansatze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Zielprogrammierung 52.1 Methodenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Methodenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Varianten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Lexikographische Ordnung von Zielen 103.1 Methodenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Methodenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.4 Varianten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.5 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4 Methoden der Zielgewichtung 154.1 Methodenbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . 154.2 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.3 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5 Interaktive Methoden 185.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.2 STEM-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 195.3 Weitere Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . 205.4 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1

6 Metaheuristiken fur die Optimierung bei mehreren Zielen 226.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226.2 Genetische Algorithmen . . . . . . . . . . . . . . . . . . . . . . . 236.3 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . 246.4 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256.5 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2

1 Optimierung bei mehreren Zielen

1.1 Problemstellung

Optimierungsproblememit mehreren

Zielen

Bei der Losung realer Optimierungsprobleme ist es oftmals erforderlich, gleich-zeitig mehrere Ziele zu berucksichtigen.Auch bei Problemen mit nur einer Zielsetzung kann die Anwendung von Mo-dellen mit mehreren Zielen sinnvoll sein, wenn beispielsweise mehrere Umwelt-zustande berucksichtigt werden mussen kann jeder dieser Zustande in einer ei-genen Zielfunktion abgebildet werden.Auch konnen statt einer stochastischen Zielfunktion mehrere deterministischeErsatzzielfunktionen eingesetzt werden.

Optimierungbei mehreren

Zielen

Im Rahmen einer Optimierung bei mehrfacher Zielsetzung soll der Entscheiderbei der Suche nach einer Losung unterstutzt werden. Eine solche Losung istmeist eine Kompromisslosung, d.h. es konnen nicht alle Ziele des Entschei-ders optimal erreicht werden, sondern der Zielerreichungsgrad einiger Ziele wirdbesser, der anderer Ziele schlechter sein.

Von einer Pareto-optimalen Losung spricht man, wenn man sich bei einerVerbesserung in einem Ziel in den anderen Zielen nur noch verschlechtern kann.Die meisten Probleme unter mehreren Zielen besitzen eine große Zahl solcherPareto-optimaler Losungen.Ziel der Losungsverfahren ist es, die Pareto-optimale Losung zu finden, welchedie Zielpraferenzen des Entscheiders am besten widerspiegelt.

3

1.2 Losungsansatze

Zielpraferen-zen und

Losungs-ansatze

Die Losungsfindung muss daher je nach den vorhandenen Informationenuber die Zielpraferenzen des Entscheiders auf unterschiedliche Weise erfolgen:

VektormaximummodelleBei einem Vektormaximummodell sind uber Praferenzen des Entscheidersnur wenig Informationen bekannt. Es wird angenommen, dass der Entscheiderbei allen Zielfunktionen hohere Zielfunktionswerte gegenuber niedrigeren bevor-zugt.

Durch die Bestimmung von so genanntenfunktional-effizienten Losungen konnenin einigen Entscheidungsproblemen dem Entscheider Losungsalternativen zurAuswahl angeboten werden. In seltenen Fallen besitzt das Problem eine perfek-te Losung, bei der alle optimalen Losungen der einzelnen Zielfunktionen zusam-menfallen.Zur Losung von Vektormaximumproblemen werden die Zielprogrammierungund Nutzenmodelle eingesetzt.

4

1.3 Losungsansatze

KompromissmodelleBei vielen Problemen ist jedoch die Berechnung aller funktional-effizienten Losun-gen nicht moglich oder es existiert eine fur den Entscheider nicht mehr uber-schaubar Anzahl solcher Losungen. Dann muss der Entscheider zusatzliche In-formationen uber seine Zielvorstellungen in den Losungsprozess einbringen.Dies fuhrt auf ein Kompromissmodell bei dem die einzelnen Ziele gewichtetund zu einer Kompromisszielfunktion zusammengefasst werden. Diese Zielfunk-tion hat den Vorteil, dass sie immer zu einer effizienten Losung fuhrt.

Bei interaktiven Verfahren mit Trade-off gibt der Entscheidungstrageriterativ uber seine Zielvorstellungen Auskunft. Sind diese ausreichend um ei-ne optimale oder eine Kompromisslosung berechnen zu konnen, so bricht dasVerfahren ab. Im anderen Fall muss der Entscheider weitere Informationen ein-bringen.

Die Abbildung gibt einen Uberblick uber wichtige Methoden der Optimierungbei mehreren Zielen. Diese lassen sich danach klassifizieren, welche Informatio-nen der Entscheider preisgibt und wie Angaben uber mogliche Kompromisse desEntscheiders modelliert werden konnen.

5

2 Zielprogrammierung

2.1 Methodenbeschreibung

Die Zielprogrammierung (goal programming) ist die wohl bekannteste Methodezur Optimierung bei mehrfacher Zielsetzung. Sie wurde erstmals von Charnesund Cooper 1961 fur lineare Programme eingesetzt und basiert auf der Mini-mierung einer Abstandsfunktion als Ersatzzielfunktion.

MethodenbeschreibungDie Zielprogrammierung wird zur Losung von Vektormaximumproblemeneingesetzt. Bei einem Vektormaximumproblem sind uber die Praferenzen desEntscheiders nur wenig Informationen vorhanden. Es wird angenommen, dassder Entscheider bei allen Zielfunktionen hohere Zielfunktionswerte gegenuberniedrigeren bevorzugt.

Durch die Bestimmung von so genannten funktional-effizientenLosungen konnendem Entscheider Losungsalternativen zur Auswahl angeboten werden. In selte-nen Fallen besitzt das Problem eine perfekte Losung, bei der die optimalenLosungen der einzelnen Zielfunktionen zusammenfallen.

6

2.2 Methodenbeschreibung

VektormaximummodellDie Zielprogrammierung lost Vektormaximummodelle der allgemeinen Form:

max z(x) |x ∈ Xs. d. Ax ≤ b , x ≥ 0, X konvex

Abstandsmaße z(x) ist ein Vektor von Zielfunktionen (z1(x), z2(x), ... zp(x))T mit p > 1,wobei jedeszk(x) konkav auf Xsei.Mittels der Zielprogrammierung wird versucht, einen Kompromiss zwischen denindividuellen Optima der p Zielfunktionen zu finden.Hierzu wird ein Abstandsmaß dq definiert, welches die Summe der Abwei-chungen der Zielfunktionswerte zk(x) einer zulassigen Losung von den optima-len Zielfunktionswerten zk ∗ (x) misst.

dq = (∑p

k=1 |zk(x) − zk ∗ (x)|q)1/q

Das Abstandsmaß kann auf vielfaltige Weise definiert werden. Im einfachstenFall wird die l1-Norm (q = 1) verwendet. Eine alternative Formulierung, welchedie positiven und negativen Abweichungen der Zielfunktionswerte addiert undauf ein lineares Programm fuhrt ist:

d=∑p

k=1(d+k + d−k )

Modell derZielprogram-

mierung

Das allgemeine Modell der Zielprogrammierung kann wie folgt formuliert wer-den:

min ds. d. Ax ≤ b, x ≥ 0, X konvex

Simplexmethodezur Zielpro-

grammierung

Aufgrund der Voraussetzungen Linearitat und Konvexitat der zulassigen Men-ge kann zur Losung das Simplex-Verfahren eingesetzt werden. Zur Anwendungdes Simplex-Verfahrens vergleiche die ausfuhrlichen Erlauterungen von Chan-kong/Haimes [2](S. 307-315).

7

2.3 Varianten

Varianten derZielprogram-

mierung

Es existiert eine große Zahl von Varianten der oben dargestellten Methode.Die wichtigste Variante ist die Gewichtung der Abweichungen. Wenn einEntscheider die positiven Abweichungen der Zielfunktionswerte von den Opti-malwerten starker (bzw. schwacher) gewichten will als die negativen Abweichun-gen, so fuhrt dies auf folgendes Problem, welches mit dem Simplex-Verfahrengelost werden kann (vgl. [2], S. 304 ff.).

min d =∑p

k=1(w+k d+

k + w−k d−k )s. d. Ax≤ b, x ≥ 0

zk ∗ (x) − zk(x) = d−k − d+k , d−k , d+

k ≥ 0

InteraktiveVarianten

Lee [5] stellt eine interaktive Methode fur die Zielprogrammierung vor,bei welcher der Entscheider jeweils auf die mit dem Simplex-Verfahren generier-ten Losungen reagiert.Aus dem Simplex-Tableau konnen hierzu Trade-off-Informationen bezuglich derZielerreichung abgelesen werden. D.h. dem Entscheider ist ersichtlich, um wie-viel er sich in den anderen Zielen verandert, wenn er sich in einem bestimmtenZiel verbessern will. Anhand dieser Information soll er entscheiden, welche Zielebevorzugt verfolgt werden sollen.

Ganzzahligeund

nichtlineareVarianten

Lee und Morris [3] modifizierte die Zielprogrammierung dahingehend, dass auchganzzahlige Variablen im Modell berucksichtigt werden konnen, indem dasmodifizierte Simplex-Verfahren mit Ansatzen der ganzzahligen Optimierungkombiniert wird. Die Losung nichtlinearer Probleme wird beispielsweise in[3] oder [2] behandelt.

8

2.4 Anwendung

Vorteile derZielprogram-

mierung

• Die Methode verlangt nur wenig Informationen bezuglich der Prafe-renzen des Entscheiders.

• Der zeitliche Aufwand fur den Entscheider ist gering.

• Wenn es eine perfekte Losung gibt, so wird sie mit der Zielprogrammierunggefunden.

• Es konnen auch ganzzahlige und nichtlineare Probleme gelost wer-den.

Nachteile derZielprogram-

mierung

• Die Methode ist nicht einsetzbar bzw. erfordert weitere Analysen, wenndas zu losende Problem viele funktional-effiziente Losungen besitzt.

• Der Entscheider ist nicht in den Losungsprozess eingebunden.

• Fur großere Probleme ist die Methode sehr rechenaufwandig.

Anwendungder Zielpro-

grammierung

Die Zielprogrammierung ist im wesentlichen fur Probleme mit mehreren Ziel-funktionen geeignet, die relativ klein sind, d.h. nur wenige Zielfunktionenund eine uberschaubare Anzahl von Variablen besitzen.Andernfalls wird der Rechenaufwand zur Losungsfindung sehr groß. Auch solltedie Zahl der funktional-effizienten Losungen uberschaubar sein bzw. das Pro-blem eine perfekte Losung besitzen.Ansonsten mussen weitere Verfahren eingesetzt werden, die dem Entscheider dieAuswahl zwischen den einzelnen Losungen erleichtern.

Literaturverzeichnis

Einfuhrende Literatur

Chankong, V./Haimes, Y.Y.: Multiobjective Decision Making - Theo-ry and Methodology, North-Holland, Amsterdam 1983. Cohon, J.L.:Multiobjective Programming and Planning. Academic Press, New YorkSan Francisco London 1978. Hwang, C.L./Masud, A.S.M.: MultipleObjective Decision Making - Methods and Applications, Springer, Berlin1979. Isermann, H.: Optimierung bei mehrfacher Zielsetzung, in: Gal, Th.(Hrsg.): Operations Research - Bd. 2. 2. Aufl., Springer, Berlin HeidelbergNew York 1989, S. 420-489. Lee, S.M.: Goal Programming for DecisionAnalysis, Auerbach, Philadelphia 1972.

9

Literaturverzeichnis

Weiterfuhrende Literatur

Charnes, A./Cooper, W.: Management Models and Industrial App-lications of Linear Programming, Wiley, New York 1961. Ignizio, J.P.:Goal Programming and Extensions, Lexington Books, Massachusetts1976. Lee, S.M./Morris, R.L.: Integer goal programming methods, inStarr, M.K./Zeleny, M (eds.): Multiple Criteria Decision Making - TIMSStudies in the Management Sciencees. North Holland, Amsterdam 1977,pp. 272-290.

10

3 Lexikographische Ordnung von Zielen

3.1 Methodenbeschreibung

Die Methode der lexikographischen Ordnung von Zielen wurde erst-mals in den 50er Jahren von Geogescu-Roegen (1954) und Debreu (1954) po-stuliert. Sie gehort zu den Methoden der sequentiellen Elimination, d.h. es wer-den zulassige Losungen berechnet und diese sequentiell gemaß der vorgegebenenPraferenzordnung des Entscheiders eliminiert.

MethodenbeschreibungVerfahren mit lexikographischer Ordnung der verschiedenen Ziele optimieren dieeinzelnen Ziele in einer vom Entscheider festgelegten Reihenfolge.Zunachst wird versucht nach dem Ziel bzw. der Zielfunktion mit der hochstenPrioritat des Entscheiders zu optimieren. Existieren mehrere Optima dieser Ziel-funktion, so wird das zweitwichtigste Ziel zur Entscheidungsfindung herangezo-gen und nur die Losungen weiter betrachtet, welche den Zielfunktionswert inHinblick auf das zweite Ziel verbessern.

Diese Vorgehensweise wird so lange fortgesetzt, bis entweder nach Eliminati-on nur noch eine Losung ubrig bleibt oder bis jede Zielfunktion einmalbetrachtet wurde. Wenn im letzteren Fall noch mehrere Losungen zur Aus-wahl stehen, so muss eine erganzende Auswahlmethode angewendet werden.

Wenn der Entscheider eine lexikographische Praferenzordnung seiner Ziele fest-gelegt hat kann ein Optimierungsproblem der Form lexmax {z(x)|x ∈ X} for-muliert werden [4]. Gesucht ist diejenige Losung x*, bei welcher der Zielwertvek-tor z(x) ein lexikographisches Maximum annimmt, d.h. z(x∗) ≥ z(x) ∀x ∈X.

11

3.2 Methodenbeschreibung

Mehrziel-Simplextableau

Jede Losung dieses Verfahrens entspricht einer funktional-effizienten Losung desVektormaximumproblems. Deshalb kann jedes lineare lexikographische Optimie-rungsproblem mit einem Mehrziel-Simplextableau gelost werden, bei dem dieAuswahlregel fur die Pivotspalte und das Optimalitatskriterium geandert wer-den. Ein Mehrziel-Simplextableau hat die folgende Form:

[1][2][3][4][5][1][2][3]

Das Mehrziel-Simplextableau besitzt q=1,..r Zielfunktionszeilen und somit auchdie aus der linearen Optimierung bekannten Hilfszeilen der Kriteriumselemente∆zq

l .Die hinreichende Optimalitatsbedingung fur dieses Mehrziel-Simplex-Tableaulautet:(∆z1

l , ∆z2l , ..., ∆zr

l )T ≥ 0 fur alle l=1, ..., n.Wenn fur mindestens einen Vektor (∆z1

l , ∆z2l , ..., ∆zr

l )T < 0gilt, so wird nachder Auswahlregel ∆z1

k

...∆zr

k

= lexmin

∆z1l | z1

l < 0·∆zr

l | z1r < 0

, l ∈ 1, ... n

der Spaltenindex k der Pivotspalte ausgewahlt und ein Pivotschritt durch-gefuhrt, wobei hier die Praferenzordnung des Entscheides berucksichtigt wird.

12

3.3 Beispiel

Beispiel Die Methode soll an einem Beispiel verdeutlicht werden (vgl. [4]): Gegeben istein lineares lexikographisches Maximierungsproblem

lexmax z(x) =

2x1 + x2 + 4x3 + x4

5x1 + 3x2 + 8x3 + 25x4

2x1 + x2 + x3 + 2x4

s. d. 4x1 + 2x2 + 8x3 + 16x4 + x5 = 64

2x1 + 4x2 + 7x3 + 10x4 + x6 = 98xl ≥ 0

Das Ausgangstableau sieht somit folgendermaßen aus:

Die zulassige Basislosung x1 = (0, 0, 0, 0, 64, 98)T genugt nicht dem hinreichen-den Optimalitatskriterium. Bei Anwendung der Auswahlregel erhalt man diePivotspalte k=3.

∆z13

∆z23

∆z33

=

−4−8−1

= lexmin

−2

−5−2

−1−3−1

−4−8−1

−1−25−2

Pivotisiert man die dritte Spalte mit y13 = 8als Pivotelement, so fuhrt das zufolgendem Tableau:

Dem zweiten Tableau entnimmt man, dass mit x2 = (0, 0, 8, 0, 0, 42)T die Ziel-funktion z1 ihr Maximum erreicht. Die Zielfunktionswerte von z2 und z3 konnenjedoch noch erhoht werden, ohne den Wert von z1 zu vermindern.Nach zwei weiteren Iterationen erhalt man das Tableau.

Mit der optimalen Losung x4 = (5, 22, 0, 0, 0, 0)T und den optimalen Zielfunkti-onswerten z1(x) = 32, z2(x) = 76, z3(x) = 32.

13

3.4 Varianten

Varianten Die Methode der lexikographischen Ordnung von Zielen kann mit anderen Me-thoden der Entscheidungstheorie kombiniert werden. Insbesondere Methodenzur Unterstutzung des Entscheiders bei der Ordnung der Zielpraferenzen kom-men hier zum Einsatz.

Vorteile derMethode

• Die Vorgehensweise ist ahnlich der menschlichen Entscheidungsfin-dung.

• Die Methode ist wenig rechenaufwandig, da nur ein kleiner Teil dermoglichen Losungen untersucht werden muss.

• Zur Losung kann das Simplex-Verfahren eingesetzt werden.

Nachteile derMethode

• Der Entscheider muss bereits eine Praferenzordnung bezuglich seiner Zielefestlegen. Dies kann relativ aufwandig sein.

• Die Ergebnisse der lexikographischen Methode reagieren sehr sensibelauf die Festlegung der Prioritaten, dies kann zu problematischenEntscheidungen fuhren.

Anwendung Die Methode kann bei allen Problemen mit mehreren Zielen angewendet werden,bei denen der Entscheider seine Praferenzen eindeutig und sicher festlegenkann.

14

3.5 Literatur

Literaturverzeichnis

Einfuhrende Literatur

Duck, W.: Optimierung unter mehreren Zielen, Vieweg, Braunschweig1979. Isermann, H.: Optimierung bei mehrfacher Zielsetzung, in: Gal,T. (Hrsg.): Grundlagen des Operations Research Bd. 1, 2. Aufl., BerlinHeidelberg et al. 1989, S. 462 ff.

Literaturverzeichnis

Weiterfuhrende Literatur

Evans, J.P./Steuer, R.E.: A revised simplex method for linear mul-tiple objective programs, in: Mathematical Programming Vol. 5, 1973,pp. 54-72. Isermann, H.: Strukturierung von Entscheidungsprozessen beimehrfacher Zielsetzung, in: Operations Research Spektrum 1, 1979, S.3-26. Isermann, H.: Linear lexikographic optimization, in: OperationsResearch Spektrum 4, 1982, pp. 223-228.

15

4 Methoden der Zielgewichtung

4.1 Methodenbeschreibung

In der Betriebswirtschaft sind Methoden auf Grundlage einer konstanten Ziel-gewichtung weit verbreitet, da darauf basierende Verfahren intuitiv verstand-lich und relativ einfach zu losen sind.

MethodenbeschreibungBei Methoden der Zielgewichtung werden den Zielfunktionen zq(x)durch denEntscheider konstante positive Zielgewichte tq (q = 1, ..., r) zugeordnet unddem Kompromissmodell eine zu maximierende Zielfunktion zugrunde gelegt:

[1][2][1][2][3] max Φ(z(x)) =∑r

q=1 tq · zq(x)

Eine Zeilgewichtung bedeutet, dass der Entscheider (ausgehend von einem be-liebigen Niveau der Zielfunktionswerte) bereit ist, die Reduzierung des Werteseiner Zielfunktion durch die Erhohung des Wertes einer anderen Zielfunktion zukompensieren.Das Verhaltnis zweier Zielgewichte ti/tkentspricht somit der Grenzrate der Sub-stitution zwischen tiundtk.

Mit den Zielgewichten spezifiziert der Entscheider genau die Grenzraten, bei de-nen er sich indifferent zwischen den entsprechenden Zielfunktionswerten verhalt.

16

4.2 Anwendung

Vorteile derZielgewich-

tung

• Das Vorgehen ist fur den Entscheider intuitiv verstandlich.

• Das Kompromissmodell ist mit mathematischen Methoden losbar. (z.B.Methoden der linearen Optimierung oder nichtlinearen Optimierung).

Nachteile derZielgewich-

tung

• Die Methode der Zielgewichtung suggeriert dem Entscheider die Moglich-keit einer einfachen Losung des Problems. Diese Einfachheit ist jedochmeist nicht gegeben.

• Der Entscheider sollte eine Vorstellung daruber haben, welche Auswir-kungen unterschiedliche Gewichtungen haben konnen. Ansonstenkann dies zur Generierung vollig indiskutabler Alternativen fuhren.

• Bei großeren Problemen wird die Vorgehensweise leicht unubersichtlich.

Anwendung Die Methode der Zeilgewichtung eignet sich fur die Losung von Mehrziel-Optimierungsproblemen,die fur den Entscheider gut uberschaubar sind, und bei denen er bereits einegute Vorstellung vom zu losenden Problem hat.

17

4.3 Literatur

Literaturverzeichnis

Literatur

Isermann, H.: Otimierung bei mehrfacher Zielsetzung, in: Gal, Th:Grundlagen des Operations Research - Bd. 1, Springer, Berlin HeidelbergNew York 1986, S. 454-460.

18

5 Interaktive Methoden

5.1

Bei interaktiven Methoden werden dem Entscheider in jedem Schritt einessolchen Verfahrens Losungsvorschlage prasentiert, mit denen er sich auseinan-dersetzen muss. Findet er keinen Losungsvorschlag akzeptabel, so muss er wei-tere Informationen bereitstellen mittels derer neue Losungsvorschlage berechnetwerden.

Methoden, die auf diesem Ansatz basieren, fuhren zu einer Strukturierungdes Losungsprozesses und versetzen den Entscheider in die Lage, auch beikomplexen und unubersichtlichen Entscheidungssituationen eine Hand-lungsalternative finden zu konnen.

19

5.2 STEM-Verfahren

MethodenbeschreibungDas von Benayoun et al. [1]entwickelte STEM-Verfahren geht davon aus, dassder Entscheider sukzessiv fur jede der Zielfunktionen des Optimierungsproblemseine Untergrenze angeben kann. Aufgrund dieser Informationen des Entschei-ders erfolgt eine schrittweise Reduzierung der Alternativenmenge bis ereine funktional-effiziente Losung als Kompromisslosung akzeptieren kann.

Das STEM-Verfahren kann insbesondere zur Losung von linearen, ganzzahli-gen oder nichtlinear-konvexen Vektormaximumproblemen herangezogen werden[4].

In einem ersten Schritt werden fur alle Zielfunktionen zi(x), i = 1, ..., r dieindividuellen Optimallosungen xi∗ und die zugehorigen Losungsvektoren z(xi∗)berechnet (die bezuglich anderer Zielfunktionen nicht optimal sein mussen). Siewerden dem Entscheider in einer Ergebnistabelle vorgelegt.

Die Elemente auf der Hauptdiagonalen der Ergebnistabelle z1(x1∗), z2(x2∗), ..., zr(xr∗)ergeben den fiktiven, optimalen Vektor der Zielfunktionswerte fur das Mehrziel-Optimierungsproblem.

Das STEM-Verfahren generiert eine Folge von funktional-effizienten Losungs-vorschlagen mit Hilfe des folgenden Kompromissmodells:

min υ − ε∑r

i=1 zi(x)

s.d. λizi(x) + υ ≥ λizi∗ ∀i ∈ U

zi(x) ≥ z ∀i ∈ {1, ..., r}\Ux ∈ X

Die Variable υ steht fur die Minimierung der Abweichung der aktuellen Losungvon allen individuellen Optima der Zielfunktionen. zi(xi∗), λi sind Gewichtungs-faktoren, die nach verschiedenen Methoden berechnet werden konnen (vgl. z.B.[1]), ε ist eine sehr klein gewahlte Zahl und U ist die Indexmenge der Zielfunk-tionen, fur die der Entscheider bis zur (i-1)-ten Stufe des Losungsprozesses nochkeine Untergrenze des Zielfunktionswertes festgelegt hat.

Jede optimale Losung des obigen Gleichungssystems ist einefunktional-effizienteLosung des Mehrziel-Optimierungsproblems. In jedem Schritt des STEM-Verfahrensgibt der Entscheider eine Untergrenze eines Zielfunktionswertes als akzeptabelan. Mit dieser Information wird das Kompromissmodell erneut gelost.

20

5.3 Weitere Methoden

Beim modifizierten STEM-Verfahren [3] konnen einmal festgelegte Unter-grenzen vom Entscheider wieder revidiert werden.

Das Verfahren von Zionts und Wallenius [5]basiert auf einer Methode,welche explizite Trade-offs verwendet. Dieses Verfahren setzt ein lineares Vek-tormaximumproblem voraus (oder eines, das linear approximiert werden kann).

21

5.4 Literatur

Literaturverzeichnis

Literatur

Benayoun, R./ De Montgolfier, J./ Tergny, J./Laritchev, O. : Linearprogramming with multiple objective functions : Step method (STEM),in : Mathematical Programming, Vol. 1, 1971, pp. 366-375. Chankong,V./Haimes, Y.Y.: Multiobjective Decision Making - Theory and Me-thodology, North-Holland, Amsterdam 1983. Dinkelbach, W./Isermann,H.: Resource allocation of an academic department in the presence ofmultiple criteria - some experience with a modified STEM-method, in:Computers and Operations Research Vol. 7, 1980, pp. 99-106. Isermann,H.: Optimierung bei mehrfacher Zielsetzung, in: Gal, Th.: Grundlagendes Operations Research Bd. 1, 2. Aufl., Berlin Heidelberg New York1989. Zionts, S./Wallenius, J.: An interactive programming method forsolving the multiple criteria problem, in: Management Science, Vol. 22,1976, pp. 101-127.

22

6 Metaheuristiken fur die Optimierung bei meh-reren Zielen

6.1 Allgemeines

Bedeutungvon

Metaheristiken

Seit Anfang der 90er Jahre gewinnt der Einsatz von Metaheuristiken, wie z.B.Simulated Annealing oder Evolutionare Algorithmen, bei der Losung von Opti-mierungsproblemn mit mehreren Zielkriterien zunehmend an Bedeutung.Diese Methoden generieren in jedem Schritt mittels eines untergeordnetenLosungsverfahrens oder einer Heuristik eine große Zahl von Losungen ausder Losungsmenge.Im Verlauf einer solchen Methode werden diese Losungen immer weiter verbes-sert.

MethodenbeschreibungAusfuhrliche Beschreibungen der wichtigsten Metaheuristiken finden Sie im Ka-pitel Heuristische Optimierungsverfahren. In diesem Abschnitt wird lediglichauf ihre Anwendung bei Problemen mit mehreren Zielen eingegangen.

23

6.2 Genetische Algorithmen

Genetische Algorithmen sind die wohl beliebteste Metaheuristik zur Losungvon Mehrziel-Probleme. Bei ihrer Anpassung auf die Mehrziel-Problematik istinsbesondere die Formulierung der Fitnessfunktion von Bedeutung.Je nach dem, wie viel Information des Entscheiders uber seine Praferenzeneinbezogen wird, kann die Fitnessfunktion gestaltet werden. Einen guten Uber-blick uber die Anwendung genetischer Algorithmen in der Mehrziel-Optimierunggeben Fonseca und Fleming [].

Fitnessfunktion Ist viel Information uber die Praferenzen bekannt, so konne die verschiedenenZielfunktionen zu einer, eventuell gewichteten, Fitnessfunktion zusam-mengefasst werden und es sind keine weiteren Informationen des Entscheidersim Verlauf des Losungsprozesses erforderlich. Wenn jedoch mit diesem Verfah-ren keine eindeutige oder keine fur den Entscheider akzeptable pareto-optimaleLosung gefunden werden kann, so muss das gesamte Verfahren wiederholt wer-den. Jakob et al. [4] und Jones et al. [5] beschreiben Verfahren, welche mit einergewichteten Fitnessfunktion arbeiten.

Nicht-pareto-Ansatze

Wenn die Praferenzen nur teilweise bekannt sind, kann die Suche auf einenbestimmten Teil der nicht dominierten Losungen eingegrenzt werden. So ge-nannte Nicht-pareto-Ansatze behandeln jede Zielfunktion separat, d.h. sieberechnen fur jede Zielfunktion einen eigenen Fitnesswert. Schaffer [7] normali-siert und aggregiert diese Fitnesswerte in seinem Vector Evaluated GeneticAlgorithm (VEGA) zur Bewertung einer Losung. Fourman [2] vergleicht dieLosungsindividuen paarweise anhand eines Fitnesswertes.

Pareto-basierteAuswahl

Liegen keine Informationen uber Praferenzen des Entscheiders vor, so wird eineso genannte Pareto-basierte Auswahl durchgefuhrt, d.h. die Fitness einesIndividuums wird gemaß seiner Pareto-Optimalitat bestimmt. Fonseca und Fle-ming []berechnen die Fitness eines Individuums nach der Anzahl von Losungsin-dividuen, von denen die betrachtete Losung dominiert wird. Horn und Nafpliotis[3]erortern eine auf der Pareto-Dominanz basierende Turnierselektion.

24

6.3 Simulated Annealing

SimulatedAnnealing

Der erste Simulated Annealing-Algorithmus fur Optimierungsprobleme bei mehr-facher Zielsetzung wurde 1992 von Serafini [] veroffentlicht und ist dem Algo-rithmus bei einfacher Zielsetzung ahnlich.Die Akzeptanz neuer Nachbarschaftslosungen wird durch Akzeptanzregelnbestimmt. Dies sind lokale, gewichtete Zielfunktionen.

In jeder Iteration des Simulated Annealing-Algorithmus werden die Gewichtezufallig innerhalb einer bestimmten Spannbreite geandert, um die Streuung derSuche uber die gesamte Menge der nicht dominierten Losungen sicherzustellen.Czyzak und Jaszkiewicz [1] beschreiben einen Pareto Simulated Annealing-Algorithmus, welcher ahnlich arbeitet wie der Algorithmus von Serafini.

PartikelschwarmeDer Einsatz von Partikelschwarmen bei der Optimierung unter mehreren Zie-len wurde von Parsopoulos und Vrahatis [] untersucht.Die Optimierung mit Partikelschwarmen ist eine Optimierungsmethode, welchedas soziale Verhalten von Schwarmen (z.B. Vogelschwarmen bei der Futtersu-che) nutzt, um die Suche nach optimalen Losungen in vielversprechende Re-gionen des Suchraums zu lenken. Parsopoulos und Vrahitis arbeiten mit einemahnlichen Ansatz wie Schaffer [7].

25

6.4 Anwendung

Vorteile vonMetaheuristi-

ken bei derMehrziel-

Optimierung

[1][2][3][4][5]• Die oben genannten Methoden konne auch auf Probleme angewendet wer-den, die fur andere Methoden der Optimierung unter mehreren Zielennicht mehr effizient losbar sind.

• Die Praferenzen des Entscheiders konnen in unterschiedlichem Maße in derBewertungsfunktion fur die einzelnen Losungen berucksichtigt werden.

Nachteile vonMetaheuristi-

ken bei derMehrzielopti-

mierung

• Der Rechenaufwand kann betrachtlich sein.

• Die Losungsfindung ist kaum nachvollziehbar.

• Die mit diesen Methoden gefundene Losung ist nicht notwendigerweisedie beste Alternative, sondern meist eine sehr gute Naherung.

Anwendung Metaheuristiken werden bevorzugt zur Losung von Optimierungsproblemen beimehrfacher Zielsetzung eingesetzt, die einen sehr hohen Rechenaufwand er-fordern.Dies sind in der Regel kombinatorische oder sehr große Probleme. Zum Teil giltdies auch fur nichtlineare Optimierungsprobleme.

26

6.5 Literatur

Literaturverzeichnis

Einfuhrende Literatur

Fonseca, C.M./Fleming, P.J.: Genetic algorithms for multiob-jective optimization: Formulation, discussion and generalizati-on, in: Forrest, S. (ed.): Genetic Algorithms: Proceedings ofthe Fifth International Conference. Morgan Kaufmann, San Ma-teo 1993, pp. 416-423. Fonseca, C.M./Fleming, P.J.: An Over-view of Evolutionary Algorithms in Multiobjective Optimization,1995, auf URL: citeseer.ist.psu.edu/article/fonseca95overview.htmlParsopoulos, K.E./Vrahatis, M.N.: Particle Swarm Optimizati-on Method in Multiobjective Problems, 2002, auf URL: cite-seer.ist.psu.edu/parsopoulos02particle.html Serafini P.: Simulatedannealing for multiple objective optimization problems. In: Tzeng G.H./Wang H.F./ Wen V.P./ Yu P.L. (eds): Multiple Criteria Decision Making.Expand and Enrich the Domains of Thinking and Application, Springer,Heidelberg New York 1992, pp. 283-292.

Literaturverzeichnis

Weiterfuhrende Literatur

Czyzak, P./Jaskiewicz, A.: Pareto simulated annealing - a metaheu-ristic technique for multiple-objective Optimization, in: Journal ofMulti-Criteria Decision Analysis, Vol. 7, 1998, pp. 34-47. Fourman, M.P.:Compaction of symbolic layout using genetic algorithms, in: Grefenstette,J.J. (ed.): Genetic Algorithms and Their Applications: Proceedings ofthe First International Conference on Genetic Algorithms, LawrenceErlenbaum 1985, pp. 141-153. Horn, J./Nafpliotis, N.: Multiobjectiveoptimization using the niched Pareto genetic algorithm. IlliGAL Report93005, University of Illinois at Urbana-Champaign, Urbana, Illinois1993. Jakob, W./Gorges-Schleuter, M./Blume, C.: Application of geneticalgorithms to task planning and learning, in: Manner, R./Manderick, B.(eds.): Parallel Problem Solving from Nature, 2. North-Holland, Am-sterdam 1992, pp. 291-300. Jones, G./Brown, R.D./Clark, D.E./Willet,P./Glen, R.C.: Searching databases of two-dimensional and three-dimensional chemical structures using genetic algorithms, in: Forrest,S. (ed.): Genetic Algorithms: Proceedings of the Fifth InternationalConference. Morgan Kaufmann, San Mateo 1993, pp. 597-602. Kennedy,J./Eberhart, R.C.: Particle Swarm Optimization, in: Proceedings of theIEEE Int. Conf. of Neural Networks, 1995, pp. 1942-1948, auf URL:http://www.engr.iupui.edu/ shi/Coference/psopap4.html Schaffer, J.D.:

27

Multiple objective optimization with vector evaluated genetic algorithms,in: Grefenstette, J.J. (ed.): Genetic Algorithms and Their Applications:Proceedings of the First International Conference on Genetic Algorithms,Lawrence Erlenbaum 1985, pp. 93-100.

28