Multikriteryong Optimisasyon

Multikriteryong optimisasyon (kilala rin bilang multikriteryong programming, Ingles: multi-objective optimization, multi-criteria optimization) — ito ay isang sangay ng matematikal na optimisasyon na nag-aaral ng mga problemang nangangailangan ng sabay-sabay na optimisasyon ayon sa dalawa o higit pang mga layunin (pamantayan), na karaniwang nagtatunggali sa isa't isa. Pormal na nakasulat ang problema bilang minimisasyon ng isang vector na layunin sa hanay ng mga pinahihintulutang solusyon.

Kahulugan at terminolohiya

Ang problema ng multikriteryong optimisasyon sa pangkalahatang anyo ay nakasulat tulad ng sumusunod: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ kung saan ang $S\subseteq {ℝ}^n$ — isang hindi-walang hanay ng mga pinahihintulutang solusyon, at ang $f_i:S\to ℝ$ — mga layunin ($k\ge 2$). Ang vector $f(x)=(f_1(x),\dots ,f_k(x))$ ay tinatawag na target na vector.

Kaiba sa scalar na optimisasyon, sa multikriteryong pagbabalangkas ay karaniwang walang natatanging solusyon na nagpapabuti ng mga halaga ng lahat ng pamantayan nang sabay-sabay. Kaya naman, ang klasikong konsepto ng optimum ay pinalalawak gamit ang konsepto ng Pareto optimality.

• Solusyon ng Pareto (Pareto-optimal o epektibong solusyon): isang pinahihintulutang solusyon $x^{\ast }\in S$, kung saan walang ibang solusyon $x\in S$ na nagbibigay ng $f_i(x)\le f_i(x^{\ast })$ para sa lahat ng $i=1,\dots ,k$, at $f_j(x)<f_j(x^{\ast })$ para sa kahit isang indeks $j$. Sa madaling salita, ang isang solusyon ay Pareto-optimal kung ang anumang halaga ng pamantayan ay hindi mapabuti nang hindi pinapasama ang kahit isang ibang pamantayan.
• Pareto front (o Pareto set): ang hanay ng lahat ng target na vector na naaayon sa mga Pareto-optimal na solusyon.
• Mahina Pareto-optimal na solusyon: isang solusyon $x^{\ast }\in S$, kung saan walang ibang solusyon $x\in S$ na nagbibigay ng $f_i(x)<f_i(x^{\ast })$ para sa lahat ng $i$.

Mga pangunahing katangian at teorema

• Teorema ng weighted sum: Sa mga convex na problema (kung saan ang lahat ng function $f_i(x)$ at ang hanay $S$ ay convex), ang anumang Pareto-optimal na solusyon $x^{\ast }$ ay solusyon ng scalar na problema ng minimisasyon ng weighted sum ng mga pamantayan $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ para sa ilang hanay ng mga hindi-negatibong timbang $w_i\ge 0$. Gayunpaman, sa mga hindi-convex na problema, ang pamamaraang ito ay maaaring hindi mahanap ang ilang bahagi ng Pareto front.

• Mga kondisyon ng optimalidad ng Karush-Kuhn-Tucker (KKT): Ang mga kinakailangang kondisyon ng optimalidad para sa maayos na mga problema ay pinalalawak sa multikriteryong kaso. Sa punto ng Pareto optimum, mayroon nang hindi-zero na hanay ng mga hindi-negatibong multiplier (timbang), kung saan ang mga gradient ng mga layunin at aktibong limitasyon ay linearly dependent.

• Mga katangian ng hanay ng mga solusyon: Ang Pareto front ay nagtataglay ng ilang mahahalagang kalidad na katangian. Ang hangganan nito ay limitado ng ideal na punto (na binubuo ng element-wise na minimum ng lahat ng pamantayan) at ng nadir na punto (mula sa element-wise na maximum sa front).

Mga halimbawa

• Linear na problema: I-minimize ang $f_1(x)=-x_1$ at $f_2(x)=-x_2$ sa limitasyong $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Dito, ang pagpapabuti ng isang pamantayan (halimbawa, ang pagtaas ng $x_1$) ay hindi maiiwasang nagdudulot ng pagkasama ng isa pa (pagbaba ng $x_2$). Ang hanay ng mga Pareto-optimal na solusyon ay isang segment ng linya $x_1+x_2=1$.
• Hindi-convex na problema: I-minimize ang $f_1(x)=x^2$ at $f_2(x)=(x-2{)}^2$ sa segment $[0,2]$. Ang Pareto front ay hindi-convex. Ang paraan ng weighted sum na may mga positibong timbang ay hindi makakakita ng mga solusyon sa loob ng segment na ito (halimbawa, sa punto $x=1$), dahil ang linear na kumbinasyon ng mga pamantayan ay makakamit lamang ang minimum sa mga dulo $x=0$ o $x=2$.

Mga kaugnay na konsepto at mga aplikasyon

Ang multikriteryong optimisasyon ay malapit na nauugnay sa multi-criteria decision making (MCDM), na nag-aaral ng pagpili ng pinakamabuting alternatibo na isinasaalang-alang ang mga kagustuhan ng taong gumagawa ng desisyon. Ang mga pangunahing pamamaraan ng pagsasalin ng multikriteryong problema sa scalar (scalarization) ay kinabibilangan ng:

• Paraan ng weighted sum.
• Paraan ng $\epsilon$-limitasyon: Ini-optimize ang isang pamantayan, at ang iba ay ginagawang mga limitasyon ng uri $f_i(x)\le {\epsilon }_i$. Ang pamamaraang ito ay kayang mahanap ang mga solusyon sa mga hindi-convex na bahagi ng front.

Ang multikriteryong optimisasyon ay malawakang ginagamit sa engineering design, ekonomiya (halimbawa, portfolio optimization), pamamahala at ekolohiya.

Tingnan din

• Pareto optimality
• Vector optimization
• Teorya ng paggawa ng desisyon
• Mga sistema ng suporta sa paggawa ng desisyon
• Operations research