- Source: Optimisasi multiobjektif
Optimisasi multiobjektif (juga dikenal dengan pemrograman multiobjektif, optimisasi vektor, optimisasi multikriteria, optimisasi multiatribut atau optimisasi Pareto) adalah sebuah bidang dalam Pengambilan Keputusan Banyak Kriteria. Optimisasi multiobjektif berurusan dengan masalah optimisasi yang melibatkan beberapa fungsi objektif untuk dioptimalkan secara bersamaan. Optimisasi multiobjektif telah diterapkan ke banyak bidang sains, termasuk teknik, ekonomi, dan logistik, dimana keputusan optimal yang diambil merupakan tarik-ulur beberapa objektif yang saling konflik. Meminimumkan biaya sambil memaksimumkan kenyamanan ketika membeli mobil; Memaksimumkan performa sekaligus meminimumkan konsumsi bahan bakar dan meminimumkan emisi polusi kendaraan, adalah contoh dari masalah optimisasi multiobjektif yang melibatkan dua dan tiga objektif, secara berurutan. Dalam masalah nyata, banyak objektif dapat lebih dari tiga.
Untuk masalah optimisasi multiobjektif yang nontrivial, tidak ada solusi yang secara bersamaan mengoptimalkan semua objektif. Dalam kasus ini, fungsi objektif dikatakan saling konflik. Sebuah solusi dikatakan tidak mendominasi, optimal Pareto (Pareto optimal), efisien Pareto, atau tidak inferior, jika tidak ada nilai fungsi objektif yang dapat ditingkatkan tanpa mengurangi nilai dari satu/beberapa fungsi objektif yang lain. Tanpa tambahan informasi preferensi subjektif, mungkin ada beberapa (atau tak hingga) solusi optimal Pareto, dan semua dianggap sama bagusnya. Peneliti mempelajari masalah optimisasi multiobjektif dari banyak sudut pandang. Akibatnya, model yang dirancang dan cara menyelesaikannya memiliki filosofi solusi dan tujuan akhir yang berbeda-beda. Beberapa tujuan diantaranya, mencari himpunan berisi solusi optimal Pareto yang representatif, dan/atau memberi penilaian terhadap setiap solusi optimal, atau mencari sebuah solusi yang memenuhi preferensi seorang/entitas pengambil keputusan (decision maker, DM).
Optimisasi bikriteria adalah kasus khusus ketika hanya ada dua fungsi objektif.
Pendahuluan
Masalah optimisasi multiobjektif adalah masalah optimisasi yang melibatkan beberapa fungsi objektif. Secara formal, masalah tersebut dapat diformulasikan dalam bentuk
min
(
f
1
(
x
→
)
,
f
2
(
x
→
)
,
…
,
f
k
(
x
→
)
)
s.t.
x
→
∈
X
,
{\displaystyle {\begin{aligned}\min &\left(f_{1}({\vec {x}}),f_{2}({\vec {x}}),\ldots ,f_{k}({\vec {x}})\right)\\{\text{s.t. }}&{\vec {x}}\in X,\end{aligned}}}
Dengan bilangan bulat
k
≥
2
{\displaystyle k\geq 2}
menyatakan banyak objektif dan himpunan
X
{\displaystyle X}
adalah himpunan feasibel berisi vektor keputusan (solusi) dan umumnya
X
⊆
R
n
{\displaystyle X\subseteq \mathbb {R} ^{n}}
. Himpunan feasibel biasanya didefinisikan lewat beberapa fungsi konstrain. Fungsi objektif bernilai vektor juga sering didefinisikan sebagai
f
→
:
X
→
R
k
,
f
→
(
x
→
)
=
(
f
1
(
x
→
)
,
…
,
f
k
(
x
→
)
)
⊺
{\displaystyle {\vec {f}}:X\to \mathbb {R} ^{k},\ {\vec {f}}({\vec {x}})=(f_{1}({\vec {x}}),\ldots ,f_{k}({\vec {x}}))^{\intercal }}
Memaksimumkan nilai sebuah fungsi objektif sama dengan meminimumkan negatif dari nilai fungsi tersebut. Citra dari
X
{\displaystyle X}
dinyatakan dengan
Y
⊆
R
k
{\displaystyle Y\subseteq \mathbb {R} ^{k}}
Sebuah elemen
x
→
∗
∈
X
{\displaystyle {\vec {x}}^{*}\in X}
disebut solusi feasibel (solusi yang mungkin) atau keputusan feasibel. Sebuah vektor
z
→
∗
:=
f
→
(
x
→
∗
)
∈
R
k
{\displaystyle {\vec {z}}^{*}:={\vec {f}}({\vec {x}}^{*})\in \mathbb {R} ^{k}}
untuk suatu solusi feasibel
x
→
∗
{\displaystyle {\vec {x}}^{*}}
disebut dengan vektor objektif atau sebuah hasil (outcome). Dalam optimisasi multiobjektif, umumnya tidak ada solusi feasibel yang meminimumkan nilai semua fungsi objektif secara bersamaan. Oleh karena itu, perhatian difokuskan pada solusi optimal Pareto; yakni, solusi yang tidak dapat meningkatkan nilai salah satu fungsi objektif lainnya tanpa mengurangi setidaknya satu fungsi objektif lainnya. Secara matematis, solusi feasibel
x
→
1
∈
X
{\displaystyle {\vec {x}}_{1}\in X}
dikatakan mendominasi (Pareto) solusi
x
→
2
∈
X
{\displaystyle {\vec {x}}_{2}\in X}
, jika
f
i
(
x
→
1
)
≤
f
i
(
x
→
2
)
{\displaystyle f_{i}({\vec {x}}_{1})\leq f_{i}({\vec {x}}_{2})}
, untuk semua indeks
i
∈
{
1
,
2
,
…
,
k
}
{\displaystyle i\in \left\{{1,2,\dots ,k}\right\}}
, dan
f
j
(
x
→
1
)
<
f
j
(
x
→
2
)
{\displaystyle f_{j}({\vec {x}}_{1})
, setidaknya untuk satu indeks
j
∈
{
1
,
2
,
…
,
k
}
{\displaystyle j\in \left\{{1,2,\dots ,k}\right\}}
.
Sebuah solusi
x
→
∗
∈
X
{\displaystyle {\vec {x}}^{*}\in X}
(dan hasil dari
f
→
(
x
→
∗
)
{\displaystyle {\vec {f}}({\vec {x}}^{*})}
) dikatakan optimal Pareto, jika tidak ada solusi lain yang mendominasi solusi tersebut. Himpunan hasil optimal Pareto umum disebut dengan batas Pareto.
Batas Pareto dari sebuah masalah optimisasi multiobjektif dibatasi (bounded) oleh sebuah vektor objektif nadir
z
→
n
a
d
{\displaystyle {\vec {z}}^{nad}}
dan sebuah vektor objektif ideal
z
→
i
d
e
a
l
{\displaystyle {\vec {z}}^{ideal}}
, jika nilai vektor-vektor tersebut terbatas. Vektor objektif nadir didefinisikan sebagai
z
→
n
a
d
∋
z
→
i
n
a
d
=
sup
x
∈
X
{
f
i
(
x
)
}
untuk setiap
i
=
1
,
…
,
k
,
{\displaystyle {\vec {z}}^{nad}\ni {\vec {z}}_{i}^{nad}={\underset {x\in X}{\sup }}\{f_{i}(x)\}{\text{ untuk setiap }}i=1,\ldots ,k,}
dan vektor objektif ideal
z
→
i
d
e
a
l
∋
z
→
i
i
d
e
a
l
=
inf
x
∈
X
{
f
i
(
x
)
}
untuk setiap
i
=
1
,
…
,
k
.
{\displaystyle {\vec {z}}^{ideal}\ni {\vec {z}}_{i}^{ideal}={\underset {x\in X}{\inf }}\{f_{i}(x)\}{\text{ untuk setiap }}i=1,\ldots ,k.}
Dengan kata lain, komponen-komponen dari vektor objektif nadir dan ideal, secara berurutan, menyatakan batas bawah dan batas atas nilai fungsi objektif dari solusi optimal Pareto. Dalam praktiknya, nilai vektor objektif nadir hanya dapat diperkirakan, karena himpunan optimal Pareto tidak diketahui secara keseluruhan. Sebagai tambahan, sebuah vektor objektif utopia
z
→
u
t
o
p
i
a
{\displaystyle {\vec {z}}^{utopia}}
umum didefinisikan karena alasan perhitungan numerik, yakni sebagai
z
→
i
u
t
o
p
i
a
=
z
→
i
i
d
e
a
l
−
ϵ
untuk setiap
i
=
1
,
…
,
k
,
{\displaystyle {\vec {z}}_{i}^{utopia}={\vec {z}}_{i}^{ideal}-\epsilon {\text{ untuk setiap }}i=1,\ldots ,k,}
dengan konstanta
ϵ
>
0
{\displaystyle \epsilon >0}
bernilai kecil.
Contoh penerapan
= Ekonomi
=Dalam ekonomi, banyak masalah yang melibatkan beberapa objektif, beserta batasan-batasan mengenai kombinasi objektif apa yang dapat dicapai. Sebagai contoh, permintaan konsumen akan barang-barang, merupakan proses memaksimumkan daya guna yang dapat dihasilkan oleh barang, dengan batasan besaran pendapatan yang tersedia untuk membeli barang dan harga barang tersebut. Batasan ini memungkinkan pembelian beberapa barang, namun dengan mengorbankan keinginan (dan kemampuan untuk) membeli barang-barang lain. Hal ini mengartikan semua objektif yang dimiliki konsumen saling konflik satu sama lainnya. Metode yang umum untuk menganalisis masalah seperti ini adalah dengan menggunakan grafik kurva indiferensi; grafik ini menyatakan preferensi, konstrain besar budget, dan tarik-ulur objektif yang dimiliki konsumen.
Contoh lainnya adalah membuat kurva kemungkinan produksi, yang menyatakan kombinasi berbagai barang yang dapat diproduksi masyarakat dengan menggunakan berbagai sumber daya. Kurva ini menunjukkan tarik-ulur yang dihadapi oleh masyarakat: jika masyarakat memaksimum penggunaan sumber daya, satu barang dapat dibuat lebih banyak, namun mengurangi jumlah barang lain yang dapat diproduksi. Masyarakat perlu menggunakan suatu proses untuk memilih kombinasi jumlah barang.
Pengambilan kebijakan makro ekonomi adalah konteks lainnya yang memerlukan optimisasi multiobjektif. Umumnya bank sentral perlu membuat kebijakan moneter yang menyeimbangkan objektif-objektif yang saling konflik -- tingkat inflasi yang rendah, tingkat pengangguran yang rendah, defisit neraca perdagangan yang rendah, dll. Untuk melakukan hal ini, bank sentral menggunakan model ekonomi yang menyatakan secara kuantitatif berbagai hubungan sebab-akibat dalam ekonomi. Model ini disimulasikan dalam berbagai skenario kebijakan moneter, untuk mendapatkan koleksi hasil yang mungkin terjadi. Secara prinsip, fungsi objektif dapat dibuat untuk memberi penilaian kuantitatif untuk setiap hasil simulasi. Namun pada praktiknya, bank sentral menggunakan proses kualitatif dan berdasarkan pertimbangan, untuk mengurutkan alternatif skenario dan membuat kebijakan.
= Keuangan
=Dalam bidang keuangan, sebuah masalah yang umum adalah bagaimana memilih fortofolio ketika terdapat dua objektif yang saling konflik — keinginan untuk mendapatkan ekspektasi pengembalian portofolio setinggi mungkin, juga keinginan untuk memiliki risiko keuangan (umumnya dinyatakan dalam standar deviasi dari pengembalian portofolio) sekecil mungkin. Masalah ini umum direpresentasikan dengan kurva portofolio yang menunjukkan kombinasi terbaik dari risiko dan ekspektasi pengembalian, dan preferensi dari investor terkait berbagai kombinasi risiko dan ekspektasi pengembalian. Masalah mengoptimisasi fungsi nilai ekspektasi (momen pertama) dan standar deviasi (akar kuadrat dari momen kedua) dari pengembalian portofolio dikenal dengan model keputusan dua-momen.
= Kontrol optimal
=Pada bidang teknik dan ekonomi, banyak masalah multiobjektif tidak dapat dideskripsikan sebagai masalah lebih-banyak-lebih-baik atau lebih-sedikit-lebih-baik. Namun, masalah tersebut adalah mencari solusi yang paling mendekati target nilai ideal dari setiap objektif. Sebagai contoh, sebuah sistem energi umumnya memiliki tarik-ulur antara peforma dan harga, atau seseorang ingin mengatur penggunaan bahan bakar dan orientasi roket agar mencapai suatu lokasi pada waktu yang ditentukan, Contoh lain adalah bank sentral yang ingin membuat kebijakan moneter dengan besar tingkat inflasi dan tingkat pengangguran semirip mungkin dengan suatu nilai yang diharapkan.
Umumnya masalah-masalah tersebut memiliki kendala yang menghalangi semua objektif dapat untuk dapat dioptimalkan secara bersamaan. Hal ini terlihat lebih jelas ketika banyak variabel bebas lebih sedikit ketimbang banyaknya objektif dan ketika keberadaan random shock menghasilkan ketidakpastian. Dalam hal ini, umum digunakan sebuah fungsi objektif kuadratik, dengan biaya yang diasosiasikan dengan setiap objektif meningkat secara kuadratik, proporsional dengan jarak nilai objektif dari nilai idealnya. Teknik optimisasi intertemporal umum digunakan, karena masalah ini umumnya melibatkan pengaturan nilai variabel dan/atau mengevaluasi nilai objektif pada setiap titik (waktu).
= Desain yang optimal
=Desain produk dapat jauh ditingkatkan dengan menggunakan teknik optimisasi, simulasi, dan permodelan yang modern. Pertanyaan utama dalam menemukan desain yang optimal adalah mengukur seberapa bagus atau seberapa menariknya suatu desain. Pencarian solusi dapat dipermudah dengan terlebih dahulu mengidentifikasi karakteristik yang berperan besar pada penilaian produk secara keseluruhan. Desain yang baik umumnya melibatkan kriteria/objektif seperti biaya pengembangan, biaya operasi, keuntungan, kualitas produk, efisiensi, keamanan ketika menggunakan, waktu operasi, dll. Objektif-objektif ini umumnya saling konflik, yakni mengoptimalkan sebuah objektif memerlukan kompromi dengan satu atau lebih objektif-objektif lain.
Sebagai contoh ketika mendesain pabrik kertas, seseorang ingin mengurangi banyak modal yang perlu diinvestasikan, sekaligus meningkatkan kualitas kertas. Jika desain dari pabrik dinyatakan dengan besar ukuran gudang penyimpanan, dan kualitas kertas dinyatakan dengan parameter-parameter kualitas, maka masalah menentukan desain yang optimal dari pabrik kertas dapat mengikutkan objektif seperti:
meminimumkan besar deviasi parameter-parameter kualitas dari nilai idealnya,
memaksimumkan jarak antar kerusakan mesin dan/atau meminimumkan waktu yang dibutuhkan untuk memperbaiki kerusakan mesin
meminimumkan besar biaya investasi dan perawatan untuk gudang penyimpanan
Optimisasi desain multiobjektif juga diterapkan pada sistem-sistem teknik seperti mengoptimasi tata letak kabinet kontrol, optimisasi bentuk airfoil, desain semikonduktor nano-CMOS, desain system on chip, desain sistem irigasi dengan tenaga (listrik) surya, optimisasi sistem dan bentuk cetakan pasir, desain mesin, juga desain penyebaran sensor dan desain controller yang optimal.
= Optimisasi proses
=Optimisasi multiobjektif semakin sering digunakan dalam teknik kimia dan manufaktur. Pada tahun 2009, Fiandaca dan Fraga menggunakan algoritma genetik multiobjektif (multi-objective genetic algorithm, MOGA) untuk mengoptimisasi proses adsorpsi ayunan tekanan. Masalah ini melibatkan proses memaksimumkan jumlah (recovery) nitrogen yang didapatkan sekaligus tingkat kemurnian nitrogen. Hasil yang didapatkan metode ini memberikan perkiraan batas Pareto yang bagus dengan tarik-ulur antar objektif yang dapat diterima. Beberapa masalah lain yang dikerjakan dengan menggunakan optimisasi multiobjektif diantaranya: pengawetan makanan secara termal, dan teknik pangan secara umum, ekstraksi bahan kimia, proses produksi bioetanol, juga masalah alokasi pembagian kerja bagi karyawan dan mesin.
= Manajemen sumber daya radio
=Tujuan dari manajemen sumber daya radio adalah untuk memenuhi tingkat permintaan data oleh pengguna-pengguna jaringan seluler. Sumber daya yang tersedia adalah interval waktu, blok frekuensi, dan daya transmisi. Di sisi lain, setiap [perangkat elektronik yang dimiliki] pengguna memiliki fungsi objektifnya, sebagai contoh, merupakan representasi kombinasi kecepatan data, jeda transfer (latency), dan efisiensi energi. Objektif-objektif ini saling konflik karena blok frekuensi yang dapat digunakan sangat terbatas, dan jika penggunaannya tidak dikontrol akan menyebabkan interferensi antar-pengguna. Teknik Multi-user MIMO saat ini digunakan untuk mengurangi interferensi dengan prakode adaptif. Operator seluler menginginkan sebaran sinyal yang luas dan kecepatan data yang tinggi, karenanya operator perlu menemukan solusi optimal Pareto yang menyeimbangkan total data yang disalurkan dan bagaimana cara membaginya ke setiap pengguna secara adil.
Manajemen sumber daya radio umum diselesaikan dengan skalarisasi; yakni menyusun setiap objektif ke sebuah fungsi utilitas dan menyederhanakan permasalahan menjadi masalah optimisasi satu-objektif. Pemilihan fungsi utilitas memiliki dampak yang besar terhadap kompleksitas komputasi dari masalah optimisasi satu-objektif yang muncul. Sebagai contoh, fungsi utilitas yang menghitung jumlah kecepatan berbobot (weighted sum rate) menghasilkan kompleksitas NP-hard yang meningkat secara eksponensial terhadap banyak pengguna, sedangkan fungsi utilitas keadilan max-min berbobot (weighted max-min fairness) merupakan masalah optimisasi kuasi-konveks yang hanya meningkat secara polinomial terhadap banyak pengguna.
= Inspeksi infrakstruktur
=Inspeksi infrastruktur secara otomatis memiliki potensi untuk mengurangi biaya, risiko dan dampak terhadap lingkungan, juga memastikan perawatan berkala bagi aset yang diperiksa. Umumnya, tugas inspeksi dianggap sebagai masalah optimisasi satu-objektif, dimana seseorang perlu meminimumkan energi atau waktu yang dibutuhkan dalam menginspeksi keseluruhan struktur. Namun pada struktur bangunan yang kompleks, melakukan pemeriksaan yang menyeluruh adalah hal yang sulit/tidak mungkin untuk dilakukan. Karenanya membuat rencana inspeksi lebih baik dianggap sebagai masalah optimisasi multiobjektif, dengan tujuan untuk memaksimumkan total daerah cakupan inspeksi sekaligus meminimumkan waktu dan biaya. Penelitian terkini menyimpulkan perencanaan inspeksi secara multiobjektif memiliki potensi memberikan solusi jauh lebih baik, ketimbang metode tradisional, pada infrastruktur yang kompleks.
Solusi
Umumnya ada beberapa solusi optimal Pareto untuk sebuah masalah optimisasi multiobjektif, hal ini menyebabkan penyelesaian masalah optimisasi tersebut tidak semudah kasus masalah optimisasi satu-objektif. Peneliti-peneliti mendefinisikan "menyelesaikan masalah optimisasi multiobjektif" dalam banyak sudut pandang. Bagian ini merangkum sebagian sudut pandang tersebut dan konteks dimana mereka digunakan. Banyak cara mengupayakan untuk menyusun semua objektif dalam sebuah fungsi objektif. Masalah yang diselesaikan dengan cara ini adalah masalah yang terskalarisasi.
Menyelesaikan masalah optimisasi multiobjektif terkadang dipahami sebagai mengaproksimasi, atau menghitung semua, atau mencari himpunan representatif, dari solusi optimal Pareto.
Ketika pengambilan keputusan lebih diutamakan, tujuan dari menyelesaikan masalah optimisasi multiobjektif adalah membantu pengambil keputusan untuk mencari solusi optimal Pareto terbaik menurut preferensi subjektifnya. Asumsi mendasar dari sudut pandang ini adalah sebuah solusi dari masalah perlu didapatkan untuk selanjutnya diimplementasikan. Dalam hal ini, pengambil keputusan (DM, decision maker) memiliki peran penting, dan umumnya merupakan ahli pada bidang permasalahan yang dikerjakan.
Solusi terbaik dapat ditemukan dengan menggunakan beberapa filosofi berbeda, yang dapat dikelompokkan menjadi empat kelompok.
Dalam metode tanpa preferensi pengambil keputusan tidak diharuskan ada, dan solusi ditemukan tanpa menggunakan infromasi preferensi. Kelompok yang lain merupakan metode interaktif yang melibatkan pengambil keputusan dalam cara yang berbeda.
Dalam metode a priori, informasi preferensi ditanyakan terlebih dahulu kepada the DM, kemudian mencari solusi yang memenuhi preferensi tersebut.
Dalam metode a posteriori, sebuah himpunan solusi optimal Pareto yang representatif dicari terlebih dahulu, kemudian DM perlu memilih salah satu solusi dari himpunan.
Dalam metode interaktif, DM dimungkinkan untuk mencari solusi terbaik secara iteratif. Dalam setiap iterasi, solusi-(solusi) optimal Pareto ditunjukkan kepada DM, beserta bagaiman (setiap) solusi dapat ditingkatkan. Informasi yang diberikan oleh DM digunakan untuk menemukan solusi-(solusi) optimal Pareto yang baru, dan digunakan dalam iterasi selanjutnya. Metode ini memungkinkan DM mempelajari batasan-batasan dari keinginannya, dan dapat berfokus untuk mencari solusi yang terbaik bagi dirinya. DM dapat menghentikan proses iterasi kapanpun ia menginginkannya.
Dalam perkembangannya, juga muncul metode hibrida yang menggabungkan beberapa algoritma/pendekatan untuk menyelesaikan masalah. Salah satu contoh metode ini adalah hibrida antara Pengambilan Keputusan Banyak Kriteria (MCDM) dengan optimisasi evolusioner multiobjektif (evolutionary multi-objective optimization, EMO). Hibrida ini menggunakan pendekatan MCDM sebagai operator pencarian lokal pada EMO untuk menemukan solusi. Operator pencarian lokal umumnya digunakan untuk mempercepat laju konvergensi algoritma EMO.
Informasi lebih lanjut mengenai keempat kelompok tersebut dan contohnya, dijelaskan di bawah ini.
Metode tanpa preferensi
Ketika pengambil keputusan tidak menyatakan secara eksplisit preferensi yang diinginkan, masalah optimisasi multiobjektif dapat diklasifikasikan dalam metode tanpa preferensi. Contoh terkenal kelompok ini adalah metode kriteria global (global criterion), yang menyelesaikan masalah optimisasi dalam bentuk terskalarisasi
min
‖
f
(
x
)
−
z
i
d
e
a
l
‖
s.t.
x
∈
X
{\displaystyle {\begin{aligned}\min &\|f(x)-z^{ideal}\|\\{\text{s.t. }}&x\in X\end{aligned}}}
Pada masalah di atas,
‖
⋅
‖
{\displaystyle \|\cdot \|}
dapat berupa norma
L
p
{\displaystyle L_{p}}
apapun, walau pada umumnya dipilih
L
1
{\displaystyle L_{1}}
,
L
2
{\displaystyle L_{2}}
, dan
L
∞
{\displaystyle L_{\infty }}
. Metode kriteria global sensitif terhadap skala yang digunakan oleh fungsi objektif. Hal umum diatasi dengan menormalisasi setiap objektif dalam skala yang uniform dan tidak berdimensi.
Metode a priori
Metode a priori membutuhkan informasi preferensi sebelum dapat menyelesaikan masalah. Beberapa contoh terkenal dari metode a priori adalah metode fungsi utilitas, metode leksikografik, dan pemrograman sasaran.
Metode fungsi utilitas mengasumsikan fungsi utilitas dari pengambil keputusan telah tersedia. Pemetaan
u
:
Y
→
R
{\displaystyle u\colon Y\rightarrow \mathbb {R} }
adalah sebuah fungsi utilitas jika setiap
y
1
,
y
2
∈
Y
{\displaystyle \mathbf {y} ^{1},\mathbf {y} ^{2}\in Y}
yang memenuhi
u
(
y
1
)
>
u
(
y
2
)
{\displaystyle u(\mathbf {y} ^{1})>u(\mathbf {y} ^{2})}
mengartikan solusi
y
1
{\displaystyle \mathbf {y} ^{1}}
lebih menyukai oleh pengambil keputusan ketimbang
y
2
{\displaystyle \mathbf {y} ^{2}}
, dan jika memenuhi
u
(
y
1
)
=
u
(
y
2
)
{\displaystyle u(\mathbf {y} ^{1})=u(\mathbf {y} ^{2})}
mengartikan kedua solusi
y
1
{\displaystyle \mathbf {y} ^{1}}
dan
y
2
{\displaystyle \mathbf {y} ^{2}}
sama baiknya. Fungsi utilitas menyatakan sebuah urutan dari vektor keputusan (ingat bahwa vektor dapat diurutkan dalam banyak cara). Setelah fungsi
u
{\displaystyle u}
didapatkan, solusi dapat ditemukan dengan cukup menyelesaikan
max
u
(
f
(
x
)
)
dengan kendala
x
∈
X
,
{\displaystyle \max \;u(\mathbf {f} (\mathbf {x} )){\text{ dengan kendala }}\mathbf {x} \in X,}
Namun pada praktiknya, sangat sulit untuk membuat fungsi utilitas yang secara akurat merepresentasikan preferensi dari pengambil keputusan - secara khusu karena batas Pareto tidak diketahui sebelum proses optimisasi dimulai.
Metode leksikografik mengasumsikan fungsi objektif dapat diurutkan berdasarkan prioritasnya. Kita mengasumsikan, tanpa mengurangi keumuman, bahwa
f
1
{\displaystyle f_{1}}
fungsi objektif terpenting dan
f
k
{\displaystyle f_{k}}
adalah objektif dengan prioritas terendah bagi pengambil keputusan. Metode leksikografik terdiri dari proses menyelesaikan sebuah urutan masalah optimisasi satu-objektif yang memiliki bentuk
min
f
l
(
x
)
s.t.
f
j
(
x
)
≤
y
j
∗
,
j
=
1
,
…
,
l
−
1
,
x
∈
X
,
{\displaystyle {\begin{aligned}\min &f_{l}(\mathbf {x} )\\{\text{s.t. }}&f_{j}(\mathbf {x} )\leq \mathbf {y} _{j}^{*},\;j=1,\dotsc ,l-1,\\&\mathbf {x} \in X,\end{aligned}}}
dengan
y
j
∗
{\displaystyle \mathbf {y} _{j}^{*}}
menyatakan nilai optimal dari bentuk di atas ketika
l
=
j
{\displaystyle l=j}
. Sebagai contoh,
y
1
∗
:=
min
{
f
1
(
x
)
∣
x
∈
X
}
{\displaystyle \mathbf {y} _{1}^{*}:=\min\{f_{1}(\mathbf {x} )\mid \mathbf {x} \in X\}}
. Perhatikan bahwa tujuan (sasaran) atau nilai yang ingin dicapai tidak dinyatakan secara eksplisit, hal ini menyebabkan metode ini berbeda dengan metode pemrograman sasaran leksikografik.
= Skalarisasi
=Menskalarisasi masalah optimisasi multiobjektif adalah proses memformulasikan masalah optimisasi satu-objektif sehingga solusi optimal yang didapat juga merupakan solusi optimal Pareto dari masalah optimisasi multiobjektif. Sebagai tambahan, umumnya setiap solusi optimal Pareto diharuskan dapat dicapai oleh dengan mengganti nilai parameter-(parameter) skalarisasi. Formulasi umum untuk skalarisasi optimisasi multiobjektif memiliki bentuk
min
g
(
f
1
(
x
)
,
…
,
f
k
(
x
)
,
θ
)
s.t
x
∈
X
θ
,
{\displaystyle {\begin{array}{ll}\min &g(f_{1}(x),\ldots ,f_{k}(x),\theta )\\{\text{s.t }}x\in X_{\theta },\end{array}}}
dengan
θ
{\displaystyle \theta }
menyatakan vektor parameter, himpunan
X
θ
⊆
X
{\displaystyle X_{\theta }\subseteq X}
adalah himpunan yang bergantung pada parameter
θ
{\displaystyle \theta }
, dan
g
:
R
k
+
1
→
R
{\displaystyle g:\mathbb {R} ^{k+1}\rightarrow \mathbb {R} }
adalah sebuah fungsi. Beberapa contoh terkenal dalam kelompok ini antara lain:
Skalarisasi linear
Skalarisasi ini menggabungkan semua objektif dalam bentuk
min
x
∈
X
∑
i
=
1
k
w
i
f
i
(
x
)
,
{\displaystyle \min _{x\in X}\sum _{i=1}^{k}w_{i}f_{i}(x),}
dengan bobot objektif
w
i
>
0
{\displaystyle w_{i}>0}
adalah parameter skalarisasi. Beberapa masalah lebih natural untuk diselesaikan dengan skalarisasi
∏
w
i
f
i
(
x
)
{\displaystyle \prod w_{i}f_{i}(x)}
. Skalarisasi ini dapat diubah menjadi serupa dengan skalarisasi linear, karena meminimumkan fungsi tersebut sama dengan meminimumkan
log
(
∏
w
i
f
i
(
x
)
)
=
∑
w
i
′
log
f
i
(
x
)
{\displaystyle \log {\Big (}\prod w_{i}f_{i}(x){\Big )}=\sum w_{i}'\log f_{i}(x)}
.
Metode konstrain-
ϵ
{\displaystyle \epsilon }
(lihat, e.g.)
min
f
j
(
x
)
s.t.
x
∈
X
f
i
(
x
)
≤
ϵ
i
for
i
∈
{
1
,
…
,
k
}
∖
{
j
}
,
{\displaystyle {\begin{array}{ll}\min &f_{j}(x)\\{\text{s.t. }}&x\in X\\&f_{i}(x)\leq \epsilon _{i}{\text{ for }}i\in \{1,\ldots ,k\}\setminus \{j\},\end{array}}}
dengan batas atas
ϵ
j
{\displaystyle \epsilon _{j}}
sebagai parameter dan
f
j
{\displaystyle f_{j}}
adalah fungsi objektif yang ingin diminimumkan.
Sedangkan beberapa metode yang lebih lanjut:
Masalah tentang skalarisasi pencapaian oleh Wierzbicki.
Beberapa masalah tentang skalarisasi pencapaian dapat diformulasikan sebagai
min
max
i
=
1
,
…
,
k
[
f
i
(
x
)
−
z
¯
i
z
i
nad
−
z
i
utopia
]
+
ρ
∑
i
=
1
k
f
i
(
x
)
z
i
n
a
d
−
z
i
utopia
dengan kendala
x
∈
S
,
{\displaystyle {\begin{array}{ll}\min &\max _{i=1,\ldots ,k}\left[{\frac {f_{i}(x)-{\bar {z}}_{i}}{z_{i}^{\text{nad}}-z_{i}^{\text{utopia}}}}\right]+\rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nad}-z_{i}^{\text{utopia}}}}\\{\text{dengan kendala }}&x\in S,\end{array}}}
dengan suku
ρ
∑
i
=
1
k
f
i
(
x
)
z
i
n
a
d
−
z
i
utopia
{\displaystyle \rho \sum _{i=1}^{k}{\frac {f_{i}(x)}{z_{i}^{nad}-z_{i}^{\text{utopia}}}}}
disebut sebagai suku augmentasi (augmentation term), konstanta
ρ
>
0
{\displaystyle \rho >0}
yang kecil,
z
nad
{\displaystyle z^{\text{nad}}}
dan
z
utopian
{\displaystyle z^{\text{utopian}}}
secara berurutan sebagai vektor nadir dan vektor utopia. Dalam formulasi di atas, parameter
z
¯
{\displaystyle {\bar {z}}}
disebut sebagai titik referensi (reference point) dan menyatakan nilai yang diharapkan oleh pengambil keputusan.
Metode a posteriori
Metode a posteriori bertujuan untuk menghasilkan semua -- atau subset yang merepresentasikan semua -- solusi optimal Pareto. Banyak dari metode a posteriori merupakan salah satu anggota dari dua kelompok berikut:
Optimisasi matematika yang menjalankan suatu algoritma secara berulang, dan pada setiap iterasi menghasilkan satu solusi optimal Pareto;
Algoritma evolusioner yang berisi algoritma untuk menghasilkan sebuah himpunan solusi optimal Pareto.
Beberapa contoh optimisasi matematika berlandaskan metode a posteriori antara lain: Model Normal Boundary Intersection (NBI), Modified Normal Boundary Intersection (NBIm) Normal Constraint (NC), Successive Pareto Optimization (SPO), dan Directed Search Domain (DSD). Model-model tersebut menyelesaikan masalah optimisasi multiobjektif dengan membangun beberapa skalarisasi. Solusi-solusi dari setiap skalarisasi merupakan solusi optimal Pareto, baik secara lokal atau secara global. Skalarisasi yang digunakan pada metode NBI, NBIm, NC, dan DSD, dikonstruksi untuk menemukan titik-titik Pareto yang terdistribusi secara merata. Titik-titik tersebut juga perlu menghasilkan aproksimasi bagus ke himpunan titik-titik Pareto asli yang terdistribusi secara merata.
Algoritma evolusioner merupakan pendekatan yang populer untuk menghasilkan solusi-solusi optimal Pareto. Saat ini, sebagian besar algoritma optimisasi multiobjektif evolusioner ( evolutionary multi-objective optimization, EMO) menerapkan skema pemeringkatan (ranking) secara Pareto. Algoritma seperti Non-dominated Sorting Genetic Algorithm-II (NSGA-II) dan Strength Pareto Evolutionary Algorithm 2 (SPEA-2) menjadi pendekatan yang standar, walau beberapa skema berdasarkan optimisasi kawanan partikel dan simulated annealing juga signifikan digunakan. Keuntungan utama dari algoritma evolusioner adalah fakta mereka umumnya menghasilkan himpunan-(himpunan) solusi, dan memungkinkan mengaproksimasi keseluruhan batas Pareto. Malangnya, proses algoritma evolusioner lebih lambat dan optimalitas Pareto dari solusi-solusi tidak dapat dipastikan. Solusi-solusi yang dihasilkan hanya diketahui untuk tidak mendominasi solusi yang lain.
Paradigma lain untuk optimisasi multiobjektif didasarkan pada cara baru dalam menggunakan algoritma evolusioner. Paradigma ini mencari solusi-solusi yang baru (novel) pada ruang objektif (contohnya, novelty search pada ruang objektif) disamping mencari solusi-solusi yang tak mendominasi. Metode seperti novelty search dapat dianggap sebagai menemukan batu pijakan untuk mencari di daerah yang belum tersentuh sebelumnya.
Beberapa metode a posteriori yang umum dikenal adalah:
metode konstrain-ε
Multiple-objective Branch-and-Bound
Normal Boundary Intersection (NBI)
Modified Normal Boundary Intersection (NBIm)
Normal Constraint (NC),
Successive Pareto Optimization (SPO)
Directed Search Domain (DSD)
NSGA-II
PGEN (Pareto surface generation for convex multi-objective instances)
Indirect Optimization on the basis of Self-Organization (IOSO)
S-Metric Selection Evolutionary Multi-Objective Algorithm (SMS-EMOA)
Approximation-Guided Evolution
Reactive Search Optimization (menggunakan pemelajaran mesin untuk mengubah strategi dan objektif), diterapkan dalam LIONsolver
Algoritma Benson untuk pemrograman linear multiobjektif dan untuk pemrograman konveks multiobjektif
Optimisasi kawanan partikel multiobjektif
Subpopulation Algorithm berdasarkan pada Novelty
Metode interaktif
Metode interaktif menyelesaikan masalah optimisasi multiobjektif secara iteratif, dan dengan melibatkan interaksi pengambil keputusan dalam mencari solusi terbaik. Dalam kata lain, pengambil keputusan diharapkan untuk menyampaikan preferensinya pada setiap iterasi (sesi) untuk mendapatkan solusi-(solusi) optimal Pareto yang bagus, dan juga mempelajari bentuk solusi seperti apa yang dapat dicapai/ditemukan. Tahapan berikut umum muncul dalam metode interaktif:
Inisialisasi (misal, menghitung vektor objektif ideal dan nadir, lalu menunjukkannya ke pengambil keputusan)
Membangun sebuah solusi optimal Pareto sebagai tahap permulaan (misal dengan metode tanpa preferensi atau solusi yang diberikan oleh pengambil keputusan)
Meminta informasi terkait preferensi dari pengambil keputusan (dapat berupa level aspirasi atau banyak solusi baru yang perlu dibuat)
Membangun solusi-(solusi) optimal Pareto yang baru berdasarkan informasi preferensi, lalu menunjukkan dan/atau menjelaskannya kepada pengambil keputusan
Jika ada beberapa solusi yang dihasilkan, minta pengambil keputusan untuk memilih solusi terbaik sejauh ini
Berhenti (jika pengambil keputusan menginginkannya; selain itu, ulangi proses dari tahap 3).
Level aspirasi di atas merujuk pada fungsi objektif-yang-diinginkan untuk membangun titik referensi. Metode interaktif menekankan konvergensi secara psikologis sebagai kriteria berakhirnya iterasi, berbeda dengan metode optimisasi matematika yang menggunakan konvergensi secara matematis. Secara umum, metode interaktif akan berakhir jika pengambil keputusan sudah percaya diri bahwa dia telah menemukan solusi terbaik yang paling sesuai.
= Tipe-tipe informasi preferensi
=Metode interaktif dapat melibatkan beberapa tipe informasi preferensi. Tipe-tipe tersebut dapat diidentifikasi berdasarkan pada
informasi tarik-ulur,
titik referensi, dan
klasifikasi fungsi-fungsi objektif.
Sebuah contoh metode interaktif yang menggunakan informasi tarik-ulur adalah metode Zionts-Wallenius. Pada setiap iterasi dalam metode ini, pengambil keputusan diberikan beberapa tarik-ulur beberapa objektif, dan untuk setiap tarik-ulur ia diminta untuk menyatakan kompromi mana yang disukai, tidak disukai, dan yang sama bagusnya.
Dalam penerapan metode yang menggunakan titik referensi, pada setiap iterasi pengambil keputusan diharapkan untuk menyatakan nilai-nilai yang diinginkan untuk setiap objektif. Selanjutnya solusi-(solusi) optimal Pareto yang bersesuaian dibentuk, lalu diberikan kepada pengambil keputusan untuk dianalisis.
Metode interaktif yang menerapkan klasifikasi mengharapkan pengambil keputusan untuk mengelompokkan objektif-objektif dari solusi optimal Pareto pada setiap iterasi. Pengelompokan tersebut menandakan bagaimana nilai-nilai setiap objektif perlu diubah untuk mencapai solusi yang lebih baik. Informasi ini selanjutnya diperhatikan dalam membangun solusi-(solusi) optimal Pareto yang baru. Metode seperti satisficing trade-off method (STOM) menggunakan tiga kelompok nilai objektif: 1) yang nilainya perlu ditingkatkan, 2) yang nilainya dapat disesuaikan, dan 3) yang nilainya sudah dapat diterima. Metode NIMBUS, menambahkan dua kelompok tambahan, yakni: 4) perlu ditingkatkan sampai suatu batas tertentu, dan 5) dapat disesuaikan sampai suatu batas tertentu.
Visualisasi batas Pareto
Visualisasi batas Pareto adalah salah satu teknik preferensi a posteriori (a posteriori preference techniques) dalam optimisasi multiobjektif. Teknik ini adalah sebuah kelas berisi beberapa teknik penting dalam optimisasi multiobjektif. Umumnya teknik preferensi ini terdiri dari empat tahap: (1) aproksimasi batas Pareto dengan komputer; (2) pengambil keputusan mempelajari solusi-(solusi) pada batas Pareto yang dihasilkan, (3) dan mengidentifikasi solusi terbaik; (4) komputer memberikan keputusan optimal Pareto, yang nilainya sama dengan solusi terbaik yang diidentifikasi oleh pengambil keputusan. Dari sudut pandang pengambil keputusan, tahap kedua teknik ini adalah yang paling rumit. Ada dua pendekatan utama untuk menginformasikan solusi kepada pengambil keputusan. Pertama, dengan menyajikan solusi-solusi pada batas Pareto dalam bentuk daftar, atau kedua, dengan menggunakan peta panas (heatmap).
= Visualisasi masalah biobjektif
=Untuk kasus masalah biobjektif (dua objektif), visualisasi batas Pareto umum digunakan untuk menginformasikan solusi kepada pengambil keputusan. Visualisasi ini umum dinamakan kurva tarik-ulur, dan digambarkan di atas bidang objektif. Kurva tarik-ulur memberikan informasi menyeluruh tentang nilai-nilai objektif, termasuk bagaimana meningkatkan nilai sebuah objektif berdampak ke bagaimana nilai objektif yang kedua akan berkurang. Pengambil keputusan menggunakan informasi ini untuk menemukan titik optimal Pareto yang disukai. S.Gass and T.Saaty memperkenalkan ide untuk mengaproksimasi dan memvisualisasikan batas Pareto pada masalah biobjektif linear. Ide ini selanjutnya dikembangkan dan diterapkan pada masalah bidang lingkungan oleh J.L. Cohon. Beberapa metode lain juga digunakan untuk mengaproksimasi batas Pareto untuk masalah dengan sedikit objektif (umumnya, dua objektif).
= Visualisasi masalah dengan objektif lebih dari dua
=Terdapat dua ide umum tentang memvisualisasikan batas Pareto untuk masalah optimisasi dengan jumlah objektif lebih dari dua. Cara yang pertama adalah menggunakan teknik-teknik visualisasi dalam statistika, dan dapat digunakan jika hanya terdapat sedikit objektif. Cara kedua diperkenalkan oleh W.S. Meisel pada tahun 1973, dengan menyajikan irisan-irisan dua-objektif dari batas Pareto. Walau cara ini dapat memberikan gambaran jelas mengenai tarik-ulur antar objektif, prosedur komputasi untuk membangun irisan-irisan tidak stabil (secara umum batas Pareto juga tidak stabil). Selain itu, cara ini sulit dikembangkan untuk jumlah objektif lebih dari tiga. Pada perkembangannya, teknik Interactive Decision Maps (IDM) dibuat sebagai implementasi yang baru dari ide W.S. Meisel. Ide lain diusulkan oleh N. Wesner, untuk menggunakan kombinasi diagram Venn dan beberapa diagram pencar untuk menyajikan ruang objektif dan eksplotasi batas Pareto.
Referensi
Pranala luar
International Society on Multiple Criteria Decision Making
Evolutionary Multiobjective Optimization, The Wolfram Demonstrations Project
A Tutorial on Multiobjective Optimization and Genetic Algorithms, Scilab Professional Partner
Tomoiagă, Bogdan; Chindriş, Mircea; Sumper, Andreas; Sudria-Andreu, Antoni; Villafafila-Robles, Roberto. 2013. "Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II." Energies 6, no. 3: 1439-1455.
List of References on Evolutionary Multiobjective Optimization
