MAKALAH OPTIMASI

Abstrak

Sebuah prosedur optimasi lengkap untuk masalah multi-tujuan essen-tially terdiri dari pencarian dan pengambilan keputusan. Tergantung pada bagaimana pencarian dan pengambilan keputusan tugas terintegrasi, algoritma dapat diklasifikasikan-fied ke dalam berbagai kategori. Setelah 'pengambilan keputusan setelah pencarian' pendekatan, yang umum dengan evolusi algoritma optimiza-tion multi-tujuan, memerlukan untuk menghasilkan semua alternatif mungkin sebelum keputusan dapat diambil. Ini, dengan kerumitan yang terlibat dalam memproduksi seluruh Pareto-depan, bukan pendekatan yang bijaksana untuk masalah tujuan tinggi. Sebaliknya, untuk masalah seperti jenis, titik paling disukai di bagian depan harus target. Dalam penelitian ini kami mengusulkan dan mengevaluasi algoritma mana pencarian dan pengambilan keputusan tugas bekerja di tandem dan solusi yang paling disukai adalah hasilnya. Untuk dua tugas untuk bekerja simultan-menerus, interaksi dari pengambil keputusan dengan algoritma yang diperlukan, oleh karena itu, informasi preferensi dari pembuat keputusan diterima pe-riodically oleh algoritma dan kemajuan menuju titik yang paling disukai dibuat.

Dua prosedur interaktif progresif yang berbeda telah diusulkan dalam disertasi yang dapat diintegrasikan dengan algoritma optimasi multi-tujuan evolusi-ary yang ada untuk meningkatkan efektivitas dalam menangani masalah obyektif tinggi dengan membuatnya mampu untuk menerima lebih-ence informasi di tangga menengah algoritma. Sejumlah

tinggi tujuan un-dibatasi serta masalah dibatasi telah berhasil diselesaikan dengan menggunakan prosedur. Salah satu domain kurang dieksplorasi dan sulit, yaitu, bilevel optimasi multi-tujuan juga telah ditargetkan dan metodologi solusi telah diusulkan. Awalnya, masalah optimasi multi-tujuan bilevel telah diselesaikan dengan mengembangkan-ing algoritma optimasi hybrid bilevel evolusi multi-tujuan. Setelah itu, prosedur interaktif progresif telah dimasukkan dalam algoritma yang mengarah ke akurasi meningkat dan penghematan biaya compu-tational. Khasiat menggunakan pendekatan interaktif progresif untuk memecahkan masalah yang sulit multi-tujuan telah, oleh karena itu, lanjut dibenarkan.

Kata kunci umum: algoritma optimasi multi-tujuan Evolusioner, beberapa kriteria pengambilan keputusan, algoritma optimasi multi-tujuan interaktif, optimasi bilevel

Kata kunci tambahan: Pilihan berdasarkan optimasi multi-tujuan, algoritma evolusioner hy-brid, algoritma diri adaptif, pemrograman kuadratik berurutan, pengembangan algoritma, pengembangan masalah uji

Ucapan Terima Kasih

Disertasi telah selesai di Departemen Bisnis Tek-nology, Aalto University School of Economics. Pekerjaan telah per-dibentuk di bawah pengawasan Prof. Kalyanmoy Deb, Prof. Pekka Ko-rhonen dan Prof. Jyrki Wallenius. Saya ingin menyampaikan tulus Grati-tude dan terima kasih kepada supervisor saya untuk inspirasi dan dukungan mereka yang memotivasi saya untuk mulai bekerja pada disertasi dengan antusiasme maksimal dan telah menjadi kekuatan pendorong untuk berhasil menyelesaikan tugas. Dukungan terus-menerus dan diskusi berbuah mendorong pemikiran dan ide-ide yang berperan dalam melaksanakan pekerjaan baru. Saya menganggap diri saya beruntung untuk menerima bimbingan terbaik dan mentoring dari para peneliti terkemuka di bidang Keputusan Evolusioner Multi-tujuan Opti-mization dan Multi Kriteria Pembuatan.

Saya berterima kasih kepada pra-penguji skripsi ini, Prof. Juergen Branke dan Prof. Lothar Thiele untuk umpan balik yang berharga mereka yang membantu dalam meningkatkan dis-sertation. Saya juga akan berterima kasih kepada semua rekan-rekan saya di departemen, di par-TERTENTU, Antti Saastamoinen, Pekka Malo dan Oskar Ahlgren untuk menyediakan lingkungan kerja yang ramah. Saya mengucapkan terima kasih kepada para sekretaris berangkat-ment itu, Helena Knuuttila, Merja Makinen dan Jutta Heino bantuan tanpa syarat dan dukungan

Aku anggun mengucapkan terima kasih kepada sekolah pascasarjana di 'Sistem Analisis, Pengambilan Keputusan dan Manajemen Risiko', yayasan HSE dan Akademi Fin-lahan untuk mendukung secara finansial penelitian ini. Saya ingin mendedikasikan ini-sis untuk orang tua saya karena saya tidak bisa menyelesaikan tugas dengan sukses tanpa berkat mereka. Akhirnya, saya ingin memberikan menyebutkan khusus untuk istri saya, Parul, yang cinta, kasih sayang dan dukungan terus saya diremajakan bahkan menuju penyelesaian disertasi saya.

1. Perkenalan

Banyak aplikasi dunia nyata dari optimasi multi-tujuan melibatkan sejumlah besar tujuan. Ada evolusi algoritma Opti-mization multi-tujuan [7, 34] telah diterapkan untuk masalah memiliki tujuan mul-tiple untuk tugas mencari satu set baik-wakil dari solusi Pareto-optimal [6, 4]. Metode ini telah berhasil memecahkan berbagai masalah dengan dua atau tiga tujuan. Namun, metodologi ini cenderung gagal untuk tingginya jumlah sasaran (lebih dari tiga) [8, 22]. Rintangan utama dalam menangani tingginya jumlah sasaran berhubungan dengan stagnasi dalam pencarian, peningkatan dimensi dari depan Pareto-optimal, biaya komputasi besar, dan kesulitan dalam visualisasi ruang ob-jective. Kesulitan-kesulitan ini melekat ke masalah multi-tujuan memiliki sejumlah besar dimensi dan tidak bisa dihilangkan; bukan, prosedur untuk menangani kesulitan tersebut perlu dieksplorasi.

Dalam banyak metodologi yang ada, informasi preferensi dari pembuat keputusan digunakan sebelum awal proses pencarian atau pada akhir proses pencarian untuk menghasilkan solusi yang optimal (s) dalam masalah multi-tujuan. Beberapa pendekatan berinteraksi dengan pengambil keputusan dan iterate proses elisitasi dan mencari sampai solusi yang memuaskan ditemukan. Namun, tidak banyak penelitian telah dilakukan di mana informasi preferensi menimbulkan selama proses pencarian dan infor-masi digunakan untuk semakin melanjutkan ke arah solusi yang paling disukai.

Disertasi ini merupakan upaya menuju pembangunan prosedur progresif di-teractive untuk menangani masalah multi-tujuan yang sulit, konsep combin-ing dari bidang Optimization Evolusi Multi-tujuan (EMO) dan Multi Criteria Decision Making (MCDM). Bidang Evolu-tionary Optimization Multi-tujuan dan Keputusan Kriteria multi Pembuatan memiliki tujuan yang sama, namun para peneliti telah menunjukkan hanya suam-suam kuku antar-est, sampai saat ini, dalam menerapkan prinsip-prinsip satu bidang yang lain. Dalam disertasi, penekanan telah ditempatkan pada integrasi metode dan pengembangan prosedur hybrid yang membantu dalam perpanjangan algoritma yang ada untuk menangani masalah yang menantang dengan beberapa objektifikasi inisiatif-inisiatif. Utilitas dari prosedur juga telah ditampilkan pada masalah optimasi multi-tujuan bilevel. Penggabungan ide memiliki konsekuensi pro-ditemukan dan alamat tantangan yang ditimbulkan oleh masalah optimasi multi-tujuan.

Disertasi terdiri dari lima makalah yang telah summa-disahkan dalam bab pendahuluan ini. Sebelum memberikan ringkasan, review singkat dari konsep dasar yang diperlukan untuk memahami makalah akan diberikan dalam bagian berikut.

1.1 Optimasi Multi-tujuan

Dalam masalah optimasi multi-tujuan [30, 19, 6] ada dua atau lebih saling bertentangan tujuan yang seharusnya secara bersamaan dioptimalkan tunduk himpunan kendala. Masalah-masalah ini biasanya ditemukan di bidang ilmu pengetahuan, teknik, ekonomi atau bidang lain di mana keputusan yang optimal harus diambil dengan adanya trade-off antara dua atau lebih saling bertentangan tujuan. Biasanya masalah seperti tidak memiliki solusi tunggal yang secara bersamaan akan memaksimalkan / meminimalkan setiap tujuan; sebaliknya, ada satu set solusi yang optimal. Solusi-solusi yang optimal disebut solusi Pareto-optimal. Seorang jenderal masalah multi-tujuan (M

1) dapat digambarkan sebagai berikut:

Dalam formulasi di atas, x merupakan variabel keputusan yang terletak di ruang keputusan. Ruang keputusan adalah ruang pencarian diwakili oleh kendala dan batas variabel dalam multi-tujuan pernyataan prob-lem umum. Ruang f Tujuan (x) adalah gambar dari ruang keputusan di bawah fungsi tujuan f. Dalam optimasi tujuan tunggal (M = 1) masalah set layak benar-benar memerintahkan sesuai dengan fungsi tujuan f (x) = f1 (x), sehingga untuk solusi, x (1) dan x (2) di ruang keputusan, baik f1 (x (1)) f1 (x (2)) atau f1 (x (2)) (x () 1) f1. Oleh karena itu, untuk dua solusi dalam ruang obyektif ada dua kemungkinan berkenaan dengan relasi.

Namun, ketika beberapa tujuan (M 2) yang terlibat, layak set belum tentu benar-benar memerintahkan, tetapi sebagian memerintahkan. Dalam masalah multitujuan, untuk setiap dua vektor obyektif, f (x (1)) dan f (x (2)), yang hubungan =,> dan dapat diperpanjang sebagai berikut, Sementara membandingkan skenario multi-tujuan dengan kasus tujuan tunggal [5], berbeda kita menemukan bahwa untuk dua solusi di ruang obyektif ada tiga kemungkinan sehubungan dengan relasi. Possibili- ini ikatan adalah: f (x (1)) f (x (2)), f (x (2)) f (x (1)) atau f (x (1)) f (x (2)) ^ f ( x (2)) f (x (1)). Jika ada dua yang pertama kemungkinan terpenuhi, hal itu memungkinkan untuk peringkat atau memesan solusi independen informasi preferensi apapun (atau pembuat deci-sion). Di sisi lain, jika dua yang pertama kemungkinan tidak terpenuhi, solusi tidak dapat peringkat atau memerintahkan tanpa menggabungkan informasi lebih-ence (atau melibatkan pembuat keputusan). Menggambar analogi dari pembahasan di atas, hubungan <dan dapat diperpanjang dengan cara yang sama.

1.2 Dominasi Konsep dan optimalitas

1.2.1 Dominasi Konsep

Berdasarkan hubungan biner ditetapkan untuk dua vektor pada bagian sebelumnya, konsep dominasi berikut [14] dapat dibentuk, x (1) sangat mendominasi x (2), f (x (1))> f (x (2)), x (1) lemah mendominasi x (2), f (x (1)) f (x (2 )), x (1) dan x (2) adalah non-didominasi dengan menghormati satu sama lain, f (x (1)) f (x (2)) ^ f (x (2)) f (x (1)). Konsep dominasi atas juga dijelaskan pada Gambar 1.1 untuk kasus tujuan maksimalisasi dua. Dalam Gambar 1.1 dua daerah yang diarsir telah ditunjukkan dalam referensi ke titik A. daerah yang diarsir di utara-timur sudut (tidak termasuk garis) adalah wilayah yang sangat mendominasi titik A, daerah yang diarsir di sudut selatan-barat (tidak termasuk baris) sangat didominasi oleh titik A dan daerah unshaded adalah non-didominasi re-gion. Oleh karena itu, titik A sangat mendominasi titik B, poin A, E dan D yang non-didominasi dengan menghormati satu sama lain, dan titik A lemah mendominasi titik C.

Sebagian besar yang ada evolusi multi-tujuan optimasi algo-rithms menggunakan prinsip dominasi untuk berkumpul menuju set optimal solusi. Konsep ini memungkinkan kami untuk memesan dua vektor keputusan berdasarkan vektor tujuan yang sesuai dengan tidak adanya preferensi apapun

Gambar 1.1: Penjelasan untuk konsep dominasi untuk masalah maksimalisasi mana A sangat mendominasi B; Sebuah lemah mendominasi C; A, D dan E adalah non-didominasi.

Gambar 1.2: Penjelasan untuk konsep satu set non-didominasi dan depan Pareto-optimal. Pref-perbedaan-perbedaan Keputusan pembuat hy-pothetical untuk pasangan biner juga ditampilkan

Informasi. Algoritma yang beroperasi dengan satu set jarang solusi dalam ruang keputusan dan gambar yang sesuai di ruang obyektif biasanya mengutamakan solusi yang mendominasi solusi lain. Solusi yang tidak didominasi sehubungan dengan solusi lain di set jarang disebut sebagai solusi non-didominasi.

Dalam kasus satu set diskrit solusi: subset yang solusi tidak didominasi oleh solusi di set diskrit disebut sebagai non-didominasi set dalam set diskrit. Non-didominasi set terdiri dari solusi terbaik yang tersedia dan membentuk depan disebut front non-didominasi. Ketika set dalam pertimbangan adalah seluruh ruang pencarian, hasil-ing non-didominasi set disebut sebagai set Pareto-optimal dan depan disebut sebagai front Pareto-optimal. Untuk secara resmi menentukan set Pareto-optimal, mempertimbangkan satu set X, yang merupakan seluruh ruang keputusan dengan begitu-lutions x 2 X. bagian X: XX, yang berisi solusi x, yang tidak didominasi oleh x di seluruh ruang keputusan membentuk satu set Pareto-optimal.

Konsep depan Pareto-optimal dan depan non-didominasi diilustrasikan pada Gambar 1.2. Wilayah yang diarsir pada gambar mewakili f (x): x 2 X. Ini adalah gambar dalam ruang tujuan seluruh wilayah layak dalam ruang keputusan. Kurva tebal mewakili depan Pareto-optimal untuk masalah maksimisasi. Secara matematis, kurva ini f (x): x 2 X yang semua poin optimal untuk kedua optimasi tujuan prob-lem. Sejumlah poin juga diplot pada gambar, yang merupakan himpunan berhingga. Di antara set poin, poin dihubungkan dengan garis putus adalah poin yang tidak didominasi oleh setiap titik di set terbatas. Oleh karena itu, titik-titik ini merupakan set non-didominasi dalam set fi-nite. Poin lain yang tidak termasuk ke dalam non-didominasi set didominasi oleh setidaknya salah satu poin di set non-didominasi. Di bidang Keputusan Multi-Kriteria Pembuatan, terminologi sedikit berbeda. Untuk satu set poin dalam ruang obyektif, poin yang tidak didominasi oleh titik lain milik set disebut sebagai titik non-didominasi, dan gambar yang sesuai mereka dalam ruang keputusan disebut sebagai efisien. Berdasarkan definisi dominasi lemah dan kuat untuk sepasang poin, konsep efisiensi lemah dan efisiensi yang kuat dapat dikembangkan untuk titik dalam satu set. Sebuah titik x 2 X, adalah lemah efisien jika dan hanya jika ada tidak ada x lain 2 X sehingga fi (x)> fi (x) untuk i 2 f1; 2; :::; Mg. Efisiensi lemah harus dis-tinguished dari efisiensi yang kuat yang menyatakan bahwa titik x 2 X, adalah sangat efisien jika dan hanya jika ada tidak ada x lain 2 X sehingga fi (x) fi (x) untuk semua i dan fi (x)> fi (x) untuk setidaknya satu i.

Terminologi, efisiensi dan non-dominasi, yang digunakan berbeda di berbagai bidang. Para peneliti di bidang Data Envelopment Anal-ysis cenderung untuk memanggil poin di ruang obyektif efisien atau tidak efisien. Beberapa peneliti lebih suka menyebutnya poin hanya pareto optimal yang efisien atau non-didominasi poin. Untuk menghindari kebingungan, kita tidak akan berbeda-entiating antara efisiensi dan non-dominasi dan terminologi akan digunakan hanya mengacu pada poin milik satu set. Dua ter-minologies akan digunakan secara sinonim untuk poin di ruang obyektif serta ruang keputusan, berdasarkan perbandingan dominasi yang dilakukan di ruang obyektif. Jika set di mana perbandingan dominasi dibuat, meliputi seluruh wilayah layak di ruang obyektif, maka poin yang efisien atau non-didominasi untuk set yang akan disebut sebagai titik pareto optimal. Pada Gambar 1.3, untuk satu set poin f1; 2; 3; 4; 5; 6; 7; 8; 9; 10g, poin f1; 2; 3; 4; 5; 6; 7; 8; 9g yang lemah efisien dan poin f1; 2; 3; 4; 5g yang sangat efisien. Perhatikan bahwa himpunan semua titik kuat efisien adalah sub-set dari himpunan semua titik lemah efisien. Titik f10g tidak efisien karena didominasi oleh setidaknya satu titik lainnya di set. Perlu dicatat bahwa gagasan efisiensi timbul sementara membandingkan poin dalam satu set. Berikut set dalam pertimbangan terdiri dari 10 jumlah poin dengan beberapa sebagai

Gambar 1.3: Penjelasan untuk efisiensi sangat efisien. Poin efisien tidak selalu Pareto-optimal karena jelas dari gambar. Perbatasan ABCD diwakili dalam ara-ure adalah lemah Pareto-perbatasan dan BC bagian ditampilkan dalam huruf tebal adalah Pareto-perbatasan yang kuat.

1,3 Pembuatan Keputusan

Meskipun ada beberapa solusi yang optimal untuk multi-tujuan prob-lem, sering ada hanya satu solusi yang menarik bagi pengambil keputusan; ini disebut sebagai solusi yang paling disukai. Cari dan pengambilan keputusan dua seluk-beluk [18] terlibat dalam menangani masalah multi-tujuan. Cari membutuhkan eksplorasi intensif di ruang keputusan untuk mendekati solusi optimal; di sisi lain, pengambilan keputusan kembali quired untuk memberikan informasi preferensi untuk solusi non-didominasi menurut solusi yang paling disukai.

Dalam konteks pengambilan keputusan solusi dapat dibandingkan dan atau--tanya berdasarkan informasi preferensi, meskipun bisa ada situasi di mana preferensi ketat satu solusi atas yang lain tidak diperoleh dan pemesanan adalah parsial. Misalnya, pertimbangkan dua vektor, x (1) dan x (2), di ruang keputusan memiliki gambar mereka, f (x (1)) dan f (x (2)), di tujuan ruang. Struktur preferensi dapat didefinisikan dengan menggunakan tiga hubungan biner, dan k, x (1) x (2), x (1) lebih disukai daripada x (2), x (1) x (2), x (1) dan x (2) sama-sama disukai, x (1) kx (2), x (1) dan x (2) yang tak tertandingi, di mana hubungan preferensi,, asimetris, hubungan ketidakpedulian,, adalah refleksif dan simetris dan hubungan incomparability, k, adalah ir-refleksif dan simetris. Sebuah hubungan preferensi yang lemah dapat ditetapkan sebagai = [seperti itu, x (1) x (2), x (1) adalah baik lebih disukai daripada x (2) atau mereka sama-sama disukai. Seperti telah disebutkan, preferensi dapat dengan mudah dibentuk untuk pasangan di mana salah satu solusi mendominasi yang lain. Namun, untuk pasangan yang non-didominasi dengan menghormati satu sama lain, keputusan diperlukan untuk pem-lish preferensi. Berikut ini adalah kesimpulan untuk pilihan preferensi yang dapat ditarik dari dominasi:

• Jika x (1) sangat mendominasi x (2)) x (1) x (2), jika x (1) lemah mendominasi x (2)) x (1) x (2).
• Hubungan biner, dan k, juga dijelaskan pada Gambar 1.2 untuk dua kasus obyektif. Beberapa poin telah ditunjukkan dalam ruang obyektif dan ketika perbandingan yang dibuat antara solusi berpasangan maka salah satu hubungan biner akan terus. Misalnya, poin 1 dan 2 yang dekat satu sama lain; Oleh karena itu, pembuat keputusan mungkin acuh tak acuh antara dua titik. Hai 3 dan 4 berbaring di ekstrem dan jauh dari satu sama lain; Oleh karena itu, pembuat keputusan dapat menemukan titik-titik tersebut incompara-ble. Ketika poin 2 dan 5 dianggap, pembuat keputusan tidak diperlukan sebagai 2 mendominasi angka 5; bisa langsung disimpulkan bahwa pembuat keputusan rasional akan memilih 2 lebih dari 5 Hal ini umum untuk meniru pembuat keputusan dengan non-penurunan fungsi nilai, V (f (x)) = V (f1 (x);:::; fM (x)), yang merupakan skalar di alam dan memberikan nilai atau ukuran kepuasan untuk masing-masing poin solusi. Untuk dua solusi, x (1) dan x (2), Jika x (1) x (2), V (f (x (1)))> V (f (x (2))), jika x (1) x (2), V (f (x (1) )) = V (f (x (2))).

1.4 Evolusi Optimization Multi-tujuan (EMO) Algoritma

Sebuah algoritma evolusioner adalah populasi umum optimasi berdasarkan al-gorithm yang menggunakan mekanisme terinspirasi oleh evolusi biologis, yaitu, seleksi, mutasi, crossover dan penggantian. Umum ide mendasari-ing belakang teknik evolusi adalah bahwa, untuk diberikan populasi-tion individu, tekanan lingkungan menyebabkan seleksi alam yang mengarah ke kenaikan kebugaran dari populasi. Sebuah komprehensif dis-discussion dari prinsip-prinsip algoritma evolusioner dapat dengan ditemukan di [16, 24, 12, 1, 25]. Berbeda dengan algoritma klasik yang iterate dari satu titik solusi yang lain sampai terminasi, sebuah evolusi algo-rithm bekerja dengan populasi poin solusi. Setiap iterasi dari hasil algoritma evolusioner di update dari populasi sebelumnya dengan menghilangkan poin solusi inferior dan termasuk yang unggul. Dalam terminologi algoritma evolusioner iterasi umumnya kembali ferred sebagai generasi dan titik solusi sebagai individu. Sebuah pseudo kode untuk algoritma evolusioner generik disediakan berikutnya:

• Langkah 1: Buat populasi awal random
• Langkah 2: Evaluasi individu dalam populasi dan menetapkan kebugaran
• Langkah 3: Ulangi sampai pemutusan generasi

Sub-langkah 1: Pilih individu yang paling cocok (orang tua) dari popu-lation untuk reproduksi

Sub-langkah 2: Menghasilkan individu baru (keturunan) melalui Crossover dan Mutasi operator

Sub-langkah 3: Evaluasi individu baru dan menetapkan kebugaran

Sub-langkah 4: Ganti anggota kebugaran rendah dengan anggota kebugaran tinggi dalam populasi

Langkah 4: OutputSeiring dengan kode pseudo disajikan di atas, diagram alir untuk algoritma evolusioner umum juga telah disajikan dalam Gambar 1.4. Sebuah kolam individu yang dihasilkan oleh acak menciptakan poin dalam ruang pencarian yang disebut populasi. Setiap anggota dalam populasi adalah evalu-diciptakan dan ditugaskan kebugaran. Misalnya, sementara memecahkan satu tujuan

masalah maksimisasi, titik solusi dengan nilai fungsi yang lebih tinggi lebih baik dari titik solusi dengan nilai fungsi yang lebih rendah. Oleh karena itu, dalam kasus tersebut, individu dengan nilai fungsi yang lebih tinggi ditugaskan lebih tinggi fit-ness. Nilai fungsi sendiri bisa diperlakukan sebagai nilai fitness dalam hal ini, atau mereka dapat diubah melalui fungsi kualitas untuk memberikan ukuran kebugaran. Demikian pula, untuk masalah maksimalisasi multi-tujuan titik solusi yang mendominasi titik solusi lain dianggap lebih baik. Ada juga ukuran untuk kesesakan [6] yang digunakan untuk individu yang tidak dapat dipesan berdasarkan prinsip dominasi. Sebuah prosedur evolusi multi-tujuan, oleh karena itu, memberikan kebugaran untuk masing-masing titik solusi berdasarkan keunggulan mereka atas solusi poin lain dalam hal dominasi dan kesesakan. Algoritma yang berbeda menggunakan pendekatan yang berbeda untuk menetapkan kebugaran untuk individu dalam suatu populasi. Setelah populasi Suami-esensial yang dihasilkan dan kebugaran ditugaskan, beberapa calon yang lebih baik dari populasi yang dipilih dengan orang tua. Crossover dan mu-tasi dilakukan untuk menghasilkan solusi baru. Crossover adalah operator diterapkan untuk dua atau lebih yang dipilih individu dan hasil dalam satu atau lebih individu baru. Mutasi diterapkan pada satu individu dan menghasilkan satu individu baru. Pelaksana crossover dan mutasi menyebabkan keturunan yang bersaing, berdasarkan kebugaran mereka, dengan individu-individu dalam populasi-tion, untuk sebuah tempat di generasi berikutnya. Iterasi dari proses ini menyebabkan kenaikan kebugaran rata-rata populasi.

Menggunakan kerangka evolusi dijelaskan, sejumlah algoritma telah dikembangkan yang berhasil memecahkan berbagai optimasi masalah. Kekuatan mereka sangat diamati dalam menangani masalah optimasi multi-tujuan dan menghasilkan seluruh Pareto depan. Tujuan dari sebuah evolusi optimasi multi-tujuan (EMO) algoritma untuk menghasilkan solusi yang (idealnya) Pareto-optimal dan merata ke seluruh Pareto-depan sehingga representasi lengkap disediakan. Dalam domain algoritma EMO tujuan ini sering disebut sebagai konvergensi dan keragaman. Para peneliti di EMO com-kemasyarakatan sejauh ini dianggap suatu pendekatan posteriori menjadi ideal ap-proach mana satu set perwakilan dari solusi Pareto-optimal ditemukan dan kemudian pembuat keputusan diundang untuk memilih titik yang paling disukai. Penegasan adalah bahwa hanya pembuat keputusan yang baik informasi adalah dalam posisi untuk mengambil keputusan yang tepat. Sebuah keyakinan umum bahwa keputusan mak-ing harus didasarkan pada pengetahuan lengkap tentang alternatif yang tersedia; penelitian saat ini di bidang algoritma EMO telah mengambil inspirasi dari keyakinan ini. Meskipun keyakinan ini benar sampai batas tertentu, ada kesulitan inher-ent terkait dengan memproduksi seluruh set alternatif dan melakukan pengambilan keputusan setelahnya, yang banyak kali membuat pendekatan efektif.

1,5 Mengintegrasikan Cari dan Pengambilan Keputusan

Cari dan Pengambilan Keputusan dapat dikombinasikan dalam berbagai cara untuk menghasilkan prosedur yang dapat diklasifikasikan ke dalam tiga kategori besar [19]. Masing-masing dari pendekatan untuk mengintegrasikan pencarian dan pengambilan keputusan akan dis-mengumpat dalam sub-bagian berikut.

1.5.1 Pendekatan posteriori

Dalam pendekatan ini, setelah satu set (perkiraan) solusi Pareto-optimal diperoleh menggunakan algoritma optimasi, pengambilan keputusan dilakukan untuk mencari solusi yang paling disukai. Gambar 1.5 menunjukkan proses diikuti untuk sampai pada solusi akhir yang paling disukai untuk pembuat keputusan. Pendekatan ini didasarkan pada asumsi bahwa pengetahuan yang lengkap dari semua alternatif membantu dalam mengambil keputusan yang lebih baik. Penelitian di bidang evolusi optimasi multi-tujuan telah diarahkan sepanjang pendekatan ini, di mana tujuannya adalah untuk menghasilkan semua alternatif yang mungkin untuk pembuat keputusan untuk membuat pilihan. Masyarakat telah mengabaikan aspek pengambilan keputusan, dan telah berjuang untuk memproduksi semua solusi optimal mungkin.

Ada kesulitan besar dalam menemukan depan Pareto-optimal seluruh untuk masalah tujuan tinggi. Bahkan jika diasumsikan daripada algoritma rithm dapat mendekati depan Pareto-optimal untuk tinggi tujuan prob-lem dengan satu set besar poin, tugas Hercules memilih titik terbaik dari set masih tetap. Selama dua dan tiga tujuan mana-tions solu di ruang obyektif dapat diwakili secara geometris, membuat keputusan mungkin mudah (meskipun bahkan sebuah contoh bisa, pada kenyataannya, tugas yang sulit untuk pembuat keputusan). Bayangkan masalah multi-tujuan dengan lebih dari tiga tujuan yang algoritma multi-tujuan evolusi mampu menghasilkan seluruh depan. Depan didekati dengan akurasi tinggi dan tingginya jumlah poin. Karena represen-tasi grafis tidak mungkin untuk Pareto-poin, bagaimana pembuat keputusan akan memilih titik yang paling disukai? Ada keputusan tentu saja membantu berhasil-mampu, tapi akurasi terbatas dengan yang pilihan akhir bisa dibuat dengan menggunakan alat bantu ini, pertanyaan tujuan memproduksi seluruh depan dengan akurasi yang tinggi. Perbandingan biner dapat menjadi solusi untuk memilih titik terbaik dari set, tetapi ini hanya dapat dimanfaatkan jika poin sangat sedikit jumlahnya. Oleh karena itu, menawarkan seluruh himpunan Pareto-poin tidak harus dianggap sebagai solusi lengkap untuk masalah ini. Namun, diffi-kesulitan-terkait dengan pengambilan keputusan telah direalisasikan oleh peneliti EMO hanya setelah penelitian berlebihan telah pergi untuk memproduksi seluruh Pareto-depan untuk banyak masalah tujuan.

1.5.2 Pendekatan A priori

Dalam pendekatan ini, pengambilan keputusan dilakukan sebelum dimulainya al-gorithm, maka algoritma optimasi dijalankan dengan memasukkan aturan preferensi, dan solusi yang paling disukai diidentifikasi. Gambar 1.6 menunjukkan proses diikuti untuk sampai pada solusi yang paling disukai. Pendekatan ini telah umum di antara praktisi MCDM, yang menyadari kompleksitas yang terlibat dalam pengambilan keputusan untuk masalah tersebut. Mereka ap-proach untuk masalah ini adalah dengan mengajukan pertanyaan sederhana dari pengambil keputusan sebelum memulai proses pencarian. Query awal biasanya meliputi arah pencarian, tingkat aspirasi untuk tujuan, atau preferensi infor-masi untuk satu atau lebih diberikan pasangan. Setelah memunculkan informasi tersebut dari pengambil keputusan, masalah multi-tujuan biasanya diubah menjadi masalah tujuan tunggal. Salah satu pendekatan awal, yaitu, Multi-Atribut Utilitas Teori (MAUT) [21] menggunakan informasi awal dari pengambil keputusan untuk membangun fungsi utilitas yang mengurangi prob-lem untuk masalah tunggal optimasi objektif. Fungsi Scalarizing (misalnya, [32]) juga sering digunakan oleh para peneliti di bidang ini untuk mengkonversi masalah multi-tujuan menjadi masalah tujuan tunggal. Teknik lain yang digunakan untuk memperoleh informasi dari pembuat keputusan dapat ditemukan di review [23] pada multi-kriteria pendukung keputusan.

Karena informasi ini ditimbulkan terhadap awal, solusi ob-tained setelah mengeksekusi algoritma biasanya solusi yang memuaskan dan mungkin tidak dekat dengan solusi yang paling disukai. Selain itu, preferensi pengambil keputusan 'mungkin berbeda untuk solusi dekat ke depan Pareto-optimal dan masukan awal yang diambil dari mereka mungkin tidak mengkonfirmasikannya. Oleh karena itu, akan sulit untuk mendekati solusi sebenarnya yang con-perusahaan dengan persyaratan pembuat keputusan. Pendekatan ini juga sangat rawan kesalahan karena bahkan sedikit penyimpangan dalam memberikan preferensi dalam formasi di awal dapat menyebabkan solusi yang sama sekali berbeda. Untuk menghindari kesalahan karena penyimpangan, peneliti di bidang EMO digunakan pendekatan dengan cara yang sedikit dimodifikasi. Mereka diproduksi beberapa solusi di wilayah yang menarik bagi pembuat keputusan [2, 11, 31, 17], bukan solusi dosa-gle, oleh karena itu, memberikan pilihan kepada pembuat keputusan pada akhir pencarian EMO. Namun, para peneliti di bidang MCDM diakui kemungkinan besar yang dapat menyebabkan hasil yang salah dan karena itu terdapat sekolah yang berbeda pemikiran yang memfokuskan pada ap-proaches interaktif.

1.5.3 Pendekatan Interaktif

Dalam pendekatan ini, pembuat keputusan berinteraksi dengan optimasi algo-rithm dan memiliki beberapa peluang untuk memberikan informasi preferensi untuk algoritma. Interaksi antara pembuat keputusan dan algoritma op-timization terus sampai solusi yang dapat diterima untuk pembuat keputusan diperoleh. Proses ini diwakili dalam Gambar 1.7. Berdasarkan jenis interaksi pembuat keputusan dengan algoritma optimasi, berbagai pendekatan interaktif bisa eksis. Disertasi membahas jenis khusus dari pendekatan interaktif disebut progresif Interac-tive Pendekatan.

Pendekatan interaktif progresif melibatkan elisitasi preferensi di-formasi berkala dari pembuat keputusan. Sementara optimasi al-gorithm sedang berlangsung, informasi preferensi diambil langkah-langkah menengah algoritma, dan algoritma bergerak menuju titik yang paling pra-ferred. Ini adalah integrasi yang lebih efektif dari proses pencarian dan pengambilan keputusan, karena keduanya bekerja secara simultan terhadap eksplorasi dari solusi.

Pendekatan ini mengatasi keterbatasan pendekatan dibahas sebelumnya karena memungkinkan interaksi yang sebenarnya dari pengambil keputusan dengan algoritma. Algoritma mengambil preferensi pembuat keputusan memperhitungkan