Monitavoite optimointi

Moniehtoinen optimointi tai ohjelmointi ( englanniksi Multi-objective optimization ) [1] [2] on prosessi, jossa optimoidaan samanaikaisesti kaksi tai useampi ristiriitainen tavoitefunktio tietyllä määritelmäalueella.

Monikriteerien optimointiongelmia löytyy monilta tieteen, teknologian ja talouden aloilta.

Määritelmä

Monitavoiteoptimoinnin ongelma on muotoiltu seuraavasti: [3]

\min _{\vec {x}}\{f_{1}({\vec {x}}),f_{2}({\vec {x}}),\dots ,f_{k} ({\vec {x)))\},

{\vec {x}}\in S

missä on ( ) tavoitefunktiot. Päätösvektorit viittaavat ei-tyhjään määritelmäalueeseen . $f_{i}:R^{n}\to R$ $k$ $k\geqslant 2$ ${\vec {x}}=(x_{1},x_{2},\dots ,x_{n})^{T}$ $S$

Monikriteerioptimoinnin ongelmana on löytää kohdemuuttujien vektori, joka täyttää asetetut rajoitukset ja optimoi vektorifunktion, jonka elementit vastaavat kohdefunktioita. Nämä funktiot muodostavat matemaattisen kuvauksen tyytyväisyyskriteeristä ja ovat pääsääntöisesti ristiriidassa keskenään. Näin ollen " optimoi " tarkoittaa sellaisen ratkaisun löytämistä, jossa tavoitefunktioiden arvot olisivat hyväksyttäviä tehtävän aloittajalle. [neljä]

Viitepisteet

Jotta löydettyjen ratkaisujen laatua voidaan arvioida, tavoitefunktion arvon alueella otetaan yleensä huomioon seuraavat seikat:

täydellinen pointti , $y^{I}$
utopistinen pointti , $y^{U}$
aliarvo . $y^{N}$

Joissakin tapauksissa nämä kohdat voivat olla ratkaisuja.

Ideaalipiste määritellään vektoriksi , jonka jokaisella koordinaatilla on tavoitefunktion vastaavan komponentin optimaalinen arvo: [5] $y^{I}=(y_{1}^{I},\dots ,y_{p}^{I})$

y_{k}^{I}=\min _{x\in X}f_{k}(x)=\min _{y\in Y}y_{k}.

Matalin piste määritellään vektoriksi: $y^{N}=(y_{1}^{N},\pisteet ,y_{p}^{N})$

y_{k}^{N}=\max _{x\in X_{E}}y_{k}(x)=\max _{y\in Y_{N}}y_{k},\ qquad k=1,\pisteet ,p.

Utopistinen piste lasketaan ihanteellisen perusteella: [6] $y^{U}$

y^{U}=y^{I}-\varepsilon U,

missä , on yksikkövektori . $\varepsilon > 0$ $U$

Optimaalisuuskriteerit

Pareto-kriteeri

Ratkaisuvektoria kutsutaan Pareto-optimaaliseksi, jos sellaista ei ole , että kaikille ja ainakin yhdelle . Pareton optimiratkaisujen joukko voidaan merkitä . Kohdevektori on Pareto-optimaalinen, jos vastaava aluevektori on myös Pareto-optimaalinen. Paretooptimaalisten kohdevektorien joukko voidaan merkitä . ${\vec {x}}'\in S$ ${\vec {x}}\in S$ $f_{i}({\vec {x}})\leqslant f_{i}({\vec {x}}')$ $i=1,\pisteet ,k$ $f_{i}({\vec {x}})<f_{i}({\vec {x}}')$ $i$ $P(S)$ $P(Z)$

Pareton optimaalisten vektorien joukko on Pareton optimaalisten vektorien osajoukko heikossa merkityksessä. Vektori on heikko Pareto-optimi, kun ei ole sellaista vektoria , että kaikille . ${\vec {x}}'\in S$ ${\vec {x}}\in S$ $f_{i}({\vec {x}})<f_{i}({\vec {x}}')$ $i=1,2,\pisteet ,k$

Pareton optimaalisten ratkaisujen arvoalue hyväksyttävien arvojen alueella antaa hyödyllistä tietoa tutkittavasta ongelmasta, jos tavoitefunktiot ovat määrittelyalueen rajoittamia. Pareton optimijoukon alarajat esitetään "ideaalikohdevektorissa" . Sen komponentit saadaan minimoimalla jokainen tavoitefunktio määrittelyalueen sisällä. ${\vec {z}}\in R^{k}$ $z_{i}$

Pareto-optimaalisten ratkaisujen joukkoa kutsutaan myös Pareto-frontiksi ( englanniksi Pareto-frontier ).

Leksikografinen järjestys

Jos jotkin tavoitefunktiot ovat tärkeämpiä kuin toiset, optimaalisuuskriteeri voidaan määrittää leksikografisen järjestyksen mukaan.

Leksikografinen järjestyssuhde vektorien ja välillä täyttyy, jos , missä . Eli vektorin ensimmäinen komponentti on pienempi kuin vektorin komponentti ja komponentit ovat tasoja (jos sellaisia on). Reaalilukujen leksikografinen järjestys on lineaarinen . $<_{\mathrm {lex} }$ $\vec a$ ${\vec {b))$ ${\displaystyle a_{q}<b_{q))$ ${\displaystyle q=\min \left\{k:a_{k}\neq b_{k}\oikea\))$ $q$ $\vec a$ ${\vec {b))$ $q+1$

Vektori on leksikografinen ratkaisu, jos ei ole sellaista vektoria , että . ${\vec {x}}\in X$ ${\vec {x}}'\in X$ $f({\vec {x}}')<_{\mathrm {lex} }f({\vec {x}})$

Koska leksikografinen järjestyssuhde on lineaarinen, voidaan osoittaa, että vektori on leksikografinen ratkaisu, jos kaikille : ${\vec x}$ ${\vec {x}}'\in X$

{\vec {f}}({\vec {x}})<_{\mathrm {lex} }{\vec {f}}({\vec {x}}').

Leksikografisen järjestyksen mukaisten päätösten pääpiirre on valinnan olemassaolo kriteerien välillä. Leksikografinen järjestys vaatii sijoituskriteerit siinä mielessä, että kriteerin mukaan optimointi on mahdollista vasta, kun edellisten kriteerien optimi on saavutettu. Tämä tarkoittaa, että ensimmäisellä kriteerillä on korkein prioriteetti, ja vain jos tälle kriteerille on useita ratkaisuja, etsitään ratkaisuja toisen ja muiden kriteerien mukaan. $f_{k}$

Kriteerien hierarkian olemassaolo mahdollistaa leksikografisten ongelmien ratkaisemisen peräkkäin, minimoimalla askel askeleelta jokaiselle seuraavalle kriteerille ja käyttämällä alustavien kriteerien optimaalisia arvoja rajoitteina.

Skalarisointi

Skalaarisijoitus

Skalarisointimenetelmiä käytetään usein Pareton optimaalisten ratkaisujen saamiseksi. Koska monikriteerien optimointitehtävän tavoitefunktiolla on vektoriarvoja, se muutetaan funktioksi, jolla on skalaariarvo. Siten moniobjektiivisen optimoinnin ongelma on pelkistetty optimointiongelmaksi yhdellä skalaarisella tavoitefunktiolla. Skalarisointifunktion on täytettävä seuraavat ehdot.

Olkoon skalarisointifunktio, joka muuttaa vektorifunktion skalaarifunktioksi. Jos se säilyttää Pareto-järjestyksen , toisin sanoen, jos se on mielivaltainen, se sisältää: $F$ ${\vec {y}}={\vec {f}}({\vec {x}})$ $F$ ${\vec {y}}$ ${\vec {y}}^{1},{\vec {y}}^{2}\in {\vec {f}}(X)$

{\vec {y}}^{1}\leqslant {\vec {y}}^{2}\implies F({\vec {y}}^{1})<F({\vec { y}}^{2}),

silloin ratkaisu , joka minimoi , on Pareto-ratkaisu. [7] Jos se säilyttää järjestyssuhteen kohdassa , eli jos mielivaltaiselle se pätee: ${\vec {x}}^{0}$ $F$ $X$ $F$ $<$ ${\vec {y}}$ ${\vec {y}}^{1},{\vec {y}}^{2}\in {\vec {f}}(X)$

{\vec {y}}^{1}<{\vec {y}}^{2}\implies F({\vec {y}}^{1})<F({\vec {y }} }}^{2}),

silloin ratkaisu , joka minimoi on Pareto heikko . Jos on jatkuva päällä ja sillä on ainutlaatuinen minimipiste , niin on Pareto-ratkaisu. ${\vec {x}}^{0}$ $F$ $X$ $F$ ${\vec {y}}$ ${\vec {x}}^{0}$ $F$ $X$ ${\vec {x}}^{0}$

Painotettu summa

F_{1}({\vec {f}}({\vec {x))))=w_{1}f_{1}({\vec {x)))+\pisteet +w_{r }f_{r}({\vec {x}}).

Yllä oleva toiminto säilyttää Pareto-järjestyksen kohteelle . Siksi ratkaisut, jotka minimoivat mielivaltaiselle , ovat Pareto-optimaalisia. Se ei kuitenkaan säilytä Pareton järjestystä :lle , vaan säilyttää vain suhteen , joten for minimoivat ratkaisut ovat Pareton heikkoja. [7] $F_{1}$ $w>0$ $F_{1}$ $X$ $w>0$ $F_{1}$ $w\geqslant 0$ $<$ $F_{1}$ $X$ $w\geqslant 0$

Painotetun summan menetelmän haittana kohdefunktioarvojen kuperan joukon tapauksessa on mahdottomuus kattaa kaikkia Pareton optimaalisia pisteitä Pareto-rintamajoukosta. Kombinatorisissa multiobjektiivisissa optimointitehtävissä tavoitearvojen joukko ei ole kupera, joten painotettu summa -menetelmä ei sovellu näiden ongelmien kohdefunktioiden skalarisointiin.

Tšebyshevin skalarisointifunktio

F_{\infty }({\vec {f}}({\vec {x))))=\max _{1\leqslant i\leqslant r}w_{i}f_{i}({\ vec{x}}).

Painotettu Tšebyševin skalarisointifunktio säilyttää suhteet ja siksi minimi on Pareton heikko. [7] $<$ ${\displaystyle F_{\infty ))$

Rajoitusten (ε-rajoitusten) muuttamismenetelmä

Rajoitusten muuttamismenetelmän mukaan yksi tavoitefunktioista jätetään kohteeksi ja loput muutetaan rajoituksiksi. Eli olkoon se tavoite ja esittäkää loput epätasa-arvon rajoitteena: $f_{r}$ $f_{1},\dots ,f_{r-1}$

\min _{x}f_{r}({\vec {x)))

olosuhteissa

f_{i}({\vec {x)))\leqslant \varepsilon _{i},i=1,\dots ,r-1,

{\vec {x}}\in X.

Arvoja voidaan pitää kelvollisina tasoina . $\varepsilon _{1},\dots ,\varepsilon _{r-1}$ $f_{1},\dots ,f_{r-1}.$

Ratkaisumenetelmät

Interaktiivisuus

Usein monitavoiteoptimoinnin ongelman ratkaisu tapahtuu asiantuntijan - henkilön, joka valitsee ja tekee päätöksiä päätöksenteon tukijärjestelmän antamien tietojen perusteella, osallistuessa. Ehkä useiden asiantuntijoiden ryhmän osallistuminen. Jos ihminen osallistuu ratkaisun etsimiseen, algoritmeja ja menetelmiä kutsutaan interaktiivisiksi . [3]

Evoluutiomenetelmät

Viittaukset geneettisten algoritmien käyttöön moniobjektiivisen optimoinnin ongelman ratkaisemisessa juontavat juurensa 1960-luvun lopulta [8] .

Menetelmä parametriavaruuden tutkimiseksi

Menetelmä perustuu hyväksyttävien ja Pareto-optimaalisten ratkaisujoukkojen rakentamiseen. Mahdollistaa suunnittelun, tunnistamisen [9] ongelmien ratkaisemisen .

Katso myös

Muistiinpanot

↑ Steuer, RE Multiple Criteria Optimization : teoria, laskelmat ja sovellus . - New York: John Wiley & Sons, Inc, 1986. - ISBN 047188846X .
↑ Sawaragi, Y.; Nakayama, H. ja Tanino, T. Multiobjektiivisen optimoinnin teoria (osa 176 of Mathematics in Science and Engineering) (englanniksi) . - Orlando, FL: Academic Press Inc, 1985. - ISBN 0126203709 .
↑ 1 2 Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen ja Roman Slowinski. Monitavoite optimointi: Interaktiiviset ja evoluutionaariset lähestymistavat (tietotekniikan luentomuistiinpanot ) . - Springer. — ISBN 3-540-88907-8 .
↑ A. Osyzka. Monikriteerien optimointi tekniseen suunnitteluun (neopr.) // Suunnittelun optimointi. — Akateeminen lehdistö. - S. 193-227 .
↑ (Ehrgott, s. 34)
↑ (Jürgen et al, s. xi)
↑ 1 2 3 Nakayama, Hirotaka; Yun, Yeboon; Yoon, Min. Jaksollinen likimääräinen monitavoiteoptimointi laskennallisen älykkyyden avulla (vektorioptimointi ) . - Springer. - ISBN 978-3-540-88909-0 .
↑ RS Rosenberg. Geneettisten populaatioiden simulointi biokemiallisilla ominaisuuksilla . - Ann Harbor: Michiganin yliopisto, 1967.
↑ Sobol I.M. Optimaalisten parametrien valinta ongelmissa, joissa on monia kriteerejä. - M .: Bustard, 2006. - 175 s. — ISBN 5-7107-7989-X .

Kirjallisuus

Kini RL, Raifa H. Päätöksenteko useilla kriteereillä: mieltymykset ja korvaukset. - M . : Radio ja viestintä, 1981. - 560 s.
Lotov A. V. , Pospelova I. I. Luentomuistiinpanot monikriteerien optimoinnin teoriasta ja menetelmistä. Proc. ratkaisu M., 2005. 127 s.
Matthias Ehrgott. Multicriteria Optimization (uuspr.) . - Springer, 2005. - ISBN 3-540-21398-8 .
M. Ehrgott ja X. Gandibleux. Approximative Solution Methods for Multi Objective Combinatoral Optimization (englanniksi) // TOP : Journal. - Sociedad de Estadística e Investigación Operativa, 2004. - Voi. 12 , ei. 1 . Arkistoitu alkuperäisestä 23. heinäkuuta 2007.

Internet-resurssit

Trifonov A. G. Monikriteerien optimointi (rus.)