Pendahuluan
Komunitas ilmu komputer dan riset operasi telah berupaya memecahkan masalah dunia nyata yang kompleks dan berskala besar. Pada artikel sebelumnya (Musim Gugur 2020), saya menjelaskan algoritma dasar yang mengubah komputasi ilmiah dalam matematika, ilmu komputer, dan riset operasi. Saat memecahkan masalah berskala besar, penting untuk menemukan solusi yang layak dan meningkatkan solusi agar menyatu dengan solusi global yang optimal. Namun, menemukan solusi yang tepat sulit dilakukan karena sumber daya terbatas, dan sebagian besar masalah optimasi bersifat kompleks. Metaheuristik dapat mengatasi kesulitan ini dengan menawarkan solusi perkiraan .
Memahami kompleksitas komputasi sangat penting untuk mendapatkan manfaat metaheuristik. Dalam teori kompleksitas komputasi, kita hanya mengetahui beberapa algoritma yang dijamin akan menyatu ke optimalitas dalam waktu proses yang wajar (algoritma waktu polinomial). Namun, banyak permasalahan dunia nyata yang bersifat NP (non-deterministik). yaitu, dengan adanya solusi terhadap masalah tersebut, kita dapat memverifikasi solusi tersebut dalam jangka waktu yang wajar. Apakah P ≠ NP? Pencarian algoritma waktu polinomial untuk permasalahan NP-complete masih dalam proses. Masalah NP-complete adalah yang tersulit di NP. Jika ada masalah NP-complete yang dapat diselesaikan dalam waktu P, maka semua masalah dalam NP dapat diselesaikan dalam waktu p.
Artikel ini terinspirasi dari artikel sebelumnya tentang "Algoritma yang mengubah dunia" pada edisi Musim Gugur 2020. Melanjutkan ini, saya membagikan lima algoritma meta-heuristik teratas (Algoritma Genetika, Simulated Annealing, Tabu Search, Swarm Intelligence Algorithm, Variable Neighborhood Search) untuk menyelesaikan masalah optimasi kompleks yang sulit diselesaikan secara optimal menggunakan teknik optimasi tradisional.
Algoritma metaheuristik
Algoritma metaheuristik adalah prosedur pencarian yang dirancang untuk menemukan, solusi yang baik terhadap masalah optimasi yang kompleks dan sulit diselesaikan secara optimal. Sangat penting untuk menemukan solusi yang mendekati optimal berdasarkan informasi yang tidak sempurna atau tidak lengkap di dunia nyata dengan sumber daya yang terbatas (misalnya, daya dan waktu komputasi). Munculnya metaheuristik untuk memecahkan masalah optimasi tersebut adalah salah satu pencapaian paling menonjol dalam dua dekade terakhir dalam riset operasi.
Terdapat tantangan yang memerlukan perhatian untuk mengembangkan solusi yang lebih baik dibandingkan pendekatan tradisional yang ada. Algoritma metaheuristik yang berbeda dijelaskan oleh penulis yang cukup luas untuk berbagai aplikasi untuk menyelesaikan masalah optimasi non-linier non-cembung. Dalam optimasi kombinatorial, tidak mungkin untuk memecahkan masalah spesifik yang bersifat NP-hard (yaitu, dalam jangka waktu yang wajar). Dengan demikian, metaheuristik seringkali dapat menemukan solusi yang baik dengan upaya komputasi yang lebih sedikit dibandingkan algoritma optimasi, metode iteratif, dan heuristik serakah sederhana. Ada berbagai jenis masalah yang tidak praktis untuk diselesaikan menggunakan algoritma optimasi menuju optimalitas global. Misalnya, masalah optimasi menjadi kompleks ketika terdapat variabel acak stokastik dalam tujuan atau batasan. Oleh karena itu, tidak mudah untuk menyelesaikan program stokastik skala besar menggunakan pemrograman stokastik atau teknik optimasi yang kuat.
Metaheuristik dapat memainkan peran kunci dalam domain yang berbeda. Intinya, banyak masalah optimasi yang merupakan fungsi multi-tujuan dengan batasan non-linier. Misalnya, sebagian besar masalah optimasi teknik sangat non-linier sehingga memerlukan solusi terhadap masalah multi-tujuan. Di sisi lain, masalah kecerdasan buatan dan pembelajaran mesin sangat bergantung pada kumpulan data yang besar, dan sulit untuk merumuskan masalah pengoptimalan yang harus diselesaikan agar optimal. Oleh karena itu, metaheuristik memainkan peran penting dalam memecahkan masalah praktis yang sulit diselesaikan dengan metode optimasi konvensional.
Algoritme metaheuristik diklasifikasikan berdasarkan cara mereka beroperasi pada ruang pencarian [3] seperti pencarian yang terinspirasi dari alam vs. yang terinspirasi dari alam, pencarian berbasis populasi vs. titik tunggal, fungsi tujuan dinamis vs. statis, struktur satu vs. berbagai lingkungan. , penggunaan memori vs. metode tanpa memori. Tujuan artikel ini bukan untuk membandingkan teknik pencarian dan optimasi. Namun demikian, penting untuk mempertanyakan apakah metode pencarian konvensional memenuhi persyaratan ketahanan. Metaheuristik cocok untuk eksploitasi dan eksplorasi ruang solusi.
Sekarang, mari kita jelajahi beberapa algoritma metaheuristik. Selain perspektif algoritmiknya, skenario kehidupan nyata dari alokasi tanggap darurat kecelakaan laut dan penerapan metaheuristik akan dicontohkan.
Algoritma genetika
Algoritma Genetika (GA) merupakan suatu metaheuristik yang dimotivasi oleh proses evolusi seleksi alam dan genetika alam. Algoritma [9] menggabungkan kelangsungan hidup yang terkuat di antara struktur string dengan pertukaran informasi yang terstruktur namun acak untuk membentuk algoritma pencarian. Aspek kunci dari algoritma genetika adalah keseimbangan antara efisiensi dan kemanjuran yang diperlukan untuk bertahan hidup dalam berbagai lingkungan persaingan yang keras.
Algoritma genetika terbukti secara teoritis dan empiris memberikan pencarian yang kuat dalam ruang yang kompleks. Di GA, kumpulan rangkaian solusi awal dihasilkan dan disimpan dalam kumpulan populasi. Urutan ini mewakili representasi genetik dari domain solusi. Fungsi kebugaran yang menggambarkan nilai solusi dari fungsi tujuan ditentukan. Dengan menggunakan operator seleksi, solusi dua orang tua dari populasi menjalani operator genetik seperti persilangan dan mutasi dengan probabilitas yang terkait. Kromosom induk menghasilkan kromosom keturunan melalui operator crossover untuk mewakili solusi anak, yaitu anak1 dan anak2. Kromosom keturunan ini mengalami mutasi (pertukaran alel) operator. Fungsi kesesuaian (objektif) dievaluasi untuk solusi anak-anak, dan populasi diperbarui berdasarkan keunggulan (Elitisme) dari fungsi kesesuaian. Algoritma ini diulangi hingga generasi maksimum atau hingga kondisi berhenti. Umumnya, urutan solusi dikodekan dalam struktur biner atau bit string untuk mewakili solusi.
Perhatikan contoh pengalokasian wadah respons (misalnya r v 1 , r v 2 , r v 3 , r v 4 , dan r v 5 ) pada beberapa lokasi kecelakaan, misalnya s 1 , s 2 , s 3 , s 4 dan hal 5 . Representasi kromosom urutannya adalah [ s 1 − s 3 − s 4 − s 2 − s 5 ] . " Anak " mewakili usulan "Adegan Kecelakaan" untuk menetapkan "Kapal Respons". Ada beberapa jenis operator crossover yang digunakan di GA. Operator crossover seperti crossover titik tunggal, crossover dua titik, crossover k-point, pengkodean berbasis prioritas, dan crossover seragam banyak digunakan. Contoh persilangan satu titik ditunjukkan di bawah ini yang dapat membelah kromosom induk pada titik tertentu.
Kapal Responr v 1r v 2r v 3r v 4r v 5
Induk (Adegan Kecelakaan)hal 1hal 2hal 3hal 4hal 5
Anakhal 4hal 5hal 1hal 2hal 3(Persilangan)Anakhal 4hal 5hal 3hal 2hal 1(Mutasi)
Dalam mutasi, salah satu urutan anak ditukar, misalnya s 1 ditukar dengan s 3 . Kondisi penghentian bergantung pada jenis masalah optimasi kombinatorial. Umumnya, generasi maksimum dan waktu berjalan maksimum dianggap sebagai kriteria penghentian. Namun, kondisi penghentian dapat didasarkan pada waktu penghentian dan generasi penghentian maksimum. Alur proses umum pengembangan Algoritma Genetika ditunjukkan pada Algoritma 1.
Beberapa penerapan GA adalah pemilihan fitur dan penyetelan hyperparameter dalam pembelajaran mesin, aplikasi teori permainan, masalah penjadwalan, optimasi struktur molekul, pemrograman non-linier, dan matematika keuangan. Model alokasi kapal respons menggunakan GA diusulkan pada [14] untuk mendukung rencana kontinjensi tumpahan minyak.
Algoritma 1: Algoritma genetika
Sumber:https://www.informs.org
Simulated annealing
Simulated annealing (SA) [12] terutama terinspirasi oleh anil: operasi pemanasan dan pendinginan terkontrol dalam metalurgi.
Alur proses umum dari algoritma SA ditunjukkan pada Algoritma 2. Solusi lingkungan dihasilkan menggunakan prosedur pencarian lokal menggunakan benih awal ( s 0 ) dan suhu. Nilai kesesuaian fungsi tujuan dievaluasi untuk solusi benih dan lingkungan ini. Misalkan δ adalah selisih antara nilai fungsi kebugaran. Jika δ < 0 , solusi tetangga diterima, jika tidak, solusi tetangga diterima dengan kepadatan probabilitas Boltzmann $e^{(\frac{-\delta}{T})}$ . Dengan demikian, eksploitasi (pencarian ekstensif dalam ruang pencarian yang telah diketahui sebelumnya) dan eksplorasi (menjelajahi peluang baru dalam ruang pencarian yang lebih luas) diterapkan pada ruang pencarian. Dalam proses pendinginan, algoritma dikonvergensi ke solusi perkiraan, keluar dari local optima untuk menemukan solusi yang mendekati optimal. Pendinginan lambat yang diimplementasikan dalam algoritma SA diinterpretasikan sebagai proses eksplorasi yang melibatkan sedikit penurunan kemungkinan menerima solusi yang lebih buruk ketika ruang solusi dieksplorasi. Singkatnya, algoritma SA berperilaku seperti heuristik pendakian bukit tetapi dengan kekuatan lebih besar untuk tidak terjebak dalam local optima [19].
Algoritma 2: Algoritma Simulasi Annealing
Sumber:https://www.informs.org
Meskipun SA biasanya mencapai solusi perkiraan minimum global, SA mungkin cukup untuk menyelesaikan banyak masalah praktis dan implementasi. Penerapan SA mencakup masalah penjual keliling, masalah pewarnaan grafik, perutean dan perluasan kendaraan, integrasi skala sangat besar dan desain komputer, serta masalah penjadwalan. Beberapa varian SA yang dikemukakan penulis adalah quantum annealing, dual-phase Evolution, stochastic tunneling, dan parallel tempering. Perutean kapal yang optimal dapat diusulkan dengan menggunakan SA [13] yang meminimalkan waktu pelayaran dan memaksimalkan keselamatan pelayaran.
Tabu search
Tabu search (TS), algoritma metaheuristik lainnya, didasarkan pada struktur memori dan menggunakan metode pencarian lokal untuk menemukan solusi potensial dengan memeriksa tetangganya untuk menemukan solusi yang lebih baik [8]. Umumnya, metode pencarian lokal terjebak di wilayah suboptimal. TS meningkatkan proses pencarian dengan membatasi (selanjutnya disebut Tabu) pengulangan solusi yang sama agar tidak kembali ke solusi yang dikunjungi sebelumnya. TS memiliki banyak kesamaan dengan SA, dan keduanya melibatkan pendakian bukit dan kemungkinan eksplorasi. Struktur memori mendefinisikan seperangkat aturan yang digunakan untuk memfilter solusi dari pencarian lingkungan. Lebih umum lagi, daftar Tabu terdiri dari solusi yang ditentukan oleh tenurial Tabu (jumlah iterasi) dimana solusi tersebut tetap berada dalam keranjang solusi. Struktur memori yang digunakan dalam TS dapat dibagi menjadi tiga kategori [7]:
-
Memori jangka pendek: Jika solusi potensial muncul dalam daftar Tabu, solusi tersebut tidak dapat ditinjau kembali hingga mencapai masa berlaku Tabu
-
Memori perantara: Aturan intensifikasi digunakan untuk meningkatkan ruang pencarian
-
Memori jangka panjang: Aturan diversifikasi yang mendorong pencarian ke wilayah baru. Penyetelan ulang diterapkan jika solusi terhenti di wilayah dataran tinggi atau sub-optimal
Algoritma pencarian lokal sederhana ditunjukkan di bawah ini dalam Algoritma 3. TS menggunakan pencarian lokal atau prosedur pencarian lingkungan terdekat (serakah) untuk berpindah dari satu solusi potensial secara iteratif, s 0 ke solusi yang lebih baik s dengan operasi sederhana σ di lingkungan s 0 , hingga beberapa kriteria penghentian terpenuhi. Banyak heuristik pencarian lokal yang tersedia dalam praktiknya, termasuk penurunan paling curam, 2-opt, 3-opt, R-opt, tetangga terdekat, dan penurunan acak.
Algoritma 3: Algoritma Pencarian Lokal [19]
Sumber:https://www.informs.org
Algoritme ini dimulai dengan inisialisasi dan solusi acak. Dalam setiap iterasi, solusi baru ditemukan dengan melakukan pergerakan lokal terhadap solusi saat ini. Solusi tetangga adalah yang terbaik di antara semua (atau sebagian) solusi yang mungkin dalam lingkungan tersebut dengan menggunakan operator N ( σ ) . Dalam proses eksplorasi, solusi yang baru-baru ini dikunjungi tidak boleh dikunjungi, sehingga mempertahankan daftar tabu untuk membatasi pergerakan solusi dalam proses pencarian lokal. Oleh karena itu, kami memiliki lingkungan dinamis dibandingkan dengan lingkungan statis yang diperoleh dari algoritma pencarian lokal lainnya. Biasanya, ada tiga jenis daftar tabu yang dikelola menggunakan struktur memori: 1) Memori jangka panjang yang menyimpan riwayat melalui seluruh proses eksplorasi dan mengatur ulang proses pencarian yang terjebak dalam optima lokal, 2) memori perantara untuk meningkatkan ruang pencarian dan 3) memori jangka pendek untuk menyimpan solusi yang paling baru dikunjungi sebagai gerakan tabu.
Pencarian Tabu sangat efisien dan keluar dari solusi lokal untuk menemukan solusi yang mendekati optimal. Beberapa aplikasi penyelesaian masalah kombinatorial menggunakan Tabu search adalah Penjadwalan, penetapan jalur komunikasi, pewarnaan graf, partisi graf, penjadwalan job shop, pengenalan pola jaringan syaraf tiruan, dan masalah perutean [7]. Alokasi tempat berlabuh yang optimal, mirip dengan tempat parkir mobil , untuk kapal diusulkan pada [4] menggunakan algoritma Tabu Search.
Algoritma 4: Algoritma Pencarian Tabu
Sumber:https://www.informs.org
Algoritma kecerdasan kawanan
Algoritma Kecerdasan Kawanan terinspirasi oleh perilaku sosial kawanan burung, penggembalaan hewan, pertumbuhan bakteri, dan kawanan ikan. Sistem intelijen gerombolan, awalnya dikembangkan dalam sistem robot seluler [1], biasanya terdiri dari populasi agen sederhana yang berinteraksi secara lokal satu sama lain dan dengan lingkungannya. Para peneliti mengusulkan beberapa algoritma kecerdasan gerombolan yang terinspirasi dari alam untuk memecahkan masalah kombinatorial hingga mencapai solusi yang mendekati optimal. Algoritma seperti optimasi koloni semut [5], optimasi kawanan partikel (PSO) [11], optimasi koloni lebah, pencarian kukuk adalah beberapa algoritma terkenal di bawah kecerdasan gerombolan.
PSO [11] adalah algoritma evolusioner berbasis populasi di mana solusi terbaik dapat direpresentasikan sebagai vektor dalam ruang berdimensi n. Dalam setiap iterasi, kecepatan ( vi j ) dan posisi ( xi ) partikel dikontrol agar menyatu ke solusi mendekati optimal yang memaksimalkan atau meminimalkan fungsi tujuan. Partikel bergerak melalui ruang solusi dan dievaluasi berdasarkan fungsi kebugaran. Pada setiap iterasi, partikel diupdate dengan dua nilai yaitu p B e s t dan g B e s t . p B e s t ( y i j ) adalah solusi terbaik yang dicapai sejauh ini, sedangkan g B e s t ( ŷ j ) adalah nilai terbaik kedua yang diperoleh partikel mana pun dalam populasi. Representasi skematis dari p Best dan g Best ditunjukkan pada Gambar 1. Dengan demikian , eksplorasi terjadi dengan pencarian lingkungan dan mengurangi kerentanan PSO untuk masuk ke dalam local optima tetapi memperlambat kecepatan konvergensi.
Sumber:https://www.informs.org
Gambar 1: Konstruksi komponen kecepatan segerombolan partikel
Posisi partikel diubah dengan menambahkan kecepatan, v i ( t ) , ke posisi saat ini, seperti pada Persamaan di bawah, dengan x i (0) ∼ U( x m i n , x m a x ).
x saya ( t + 1) = x saya ( t ) + vi ( t + 1)
Untuk g B e s t PSO, kecepatan partikel i dihitung seperti pada Persamaan di bawah, dimana c 1 dan c 2 adalah konstanta percepatan. Algoritma PSO ditunjukkan di bawah ini pada Algoritma 5.
v i j ( t + 1) = v i j ( t ) + c 1 r 1 j ( t )[ y i j ( t ) − x i j ( t )] + c 2 r 2 j ( t )[ ŷ j ( t ) − x saya j ( t )]
Algoritma 5: Algoritma Particle Swarm Optimization
Sumber:https://www.informs.org
PSO dapat diterapkan pada berbagai masalah optimasi [20], termasuk sistem infrastruktur sipil, perkiraan kecelakaan lalu lintas, rekayasa struktural, modalitas multi-ambang batas untuk deteksi wilayah mencurigakan pada mammogram, konfigurasi ulang susunan fotovoltaik, sistem tenaga, dan perakitan sistem robot angkutan kereta api. Beberapa aplikasi menarik termasuk investigasi teknologi gerombolan NASA untuk pemetaan planet, film 'Batman Returns' yang menggunakan teknologi gerombolan untuk rendering, menggambarkan pergerakan penguin, dan trilogi film 'Lord of the Rings' yang memanfaatkan teknologi serupa selama adegan pertempuran .
Sebagai gambaran, dalam kasus sistem tanggap darurat tumpahan minyak di laut, alokasi dan pengerahan kapal tanggap (misalnya kapal penyelamat) dapat dioptimalkan dengan menggunakan PSO, seperti yang diusulkan dalam [21]. Dalam operasi pemulihan minyak, tujuan utamanya adalah mengumpulkan minyak sebanyak mungkin, dan ini merupakan operasi yang bergantung pada waktu. Rencana respons optimal (dengan mempertimbangkan alokasi sumber daya, perilaku pemulihan skimmer, ruang untuk membawa peralatan transportasi kapal, dan pemanfaatan sumber daya dari pusat respons) yang diusulkan dalam penelitian ini memulihkan sekitar 80,28% minyak yang tumpah dalam 48 jam respons pertama.
Sumber:https://www.informs.org
Gambar 2: Tanggap Darurat Kecelakaan Laut, menggunakan PSO [21]
Variable neighborhood search
Algoritma Variable Neighborhood Search (VNS) [16] mengeksplorasi lingkungan yang jauh dari solusi awal dan berpindah ke solusi baru yang lebih baik. Mirip dengan pencarian Tabu, metode pencarian lokal diterapkan berulang kali untuk mendapatkan solusi di lingkungan sekitar ke local optima dan keluar dari lembah yang menampung solusi tersebut. Karakteristik ini membantu VNS dalam menyelesaikan program linear, non-linear, integer, dan mixed-integer. VNS menggunakan pencarian lokal sederhana ditambah dengan algoritma heuristik perbaikan pertama dan perubahan lingkungan; ia memiliki proses eksploitasi dan eksplorasi yang mirip dengan metaheuristik lainnya.
Detail dari algoritma VNS ditunjukkan pada Algoritma 10. Mula-mula, heuristik perbaikan pertama dipanggil untuk mencari local optima, dengan mempertimbangkan wilayah solusi yang layak, seperti pada Algoritma 6. Kemudian, heuristik lingkungan dipanggil untuk keluar dari lokal. optima untuk menemukan solusi yang lebih baik di area kelayakan baru, seperti pada Algoritma 7. Algoritma ini diulangi hingga iterasi maksimum yang telah ditetapkan dan waktu pengoperasian CPU. Selain heuristik perbaikan pertama, pencarian lokal sederhana dapat digunakan untuk operasi pencarian lokal, seperti pada Algoritma 3.
Algoritma 6: Heuristik perbaikan pertama [10]
Algoritma 7: Heuristik perubahan lingkungan [10]
Algoritma 8: Algoritma Variable Neighborhood Search [10]
Sumber:https://www.informs.org
Varian dari VNS [6] menggunakan pencarian lingkungan deterministik, tidak seperti struktur lingkungan tunggal. 'Shaking' merupakan langkah tambahan yang dilakukan untuk mencari alternatif solusi terbaik dari lingkungan k secara acak. Demikian pula, VNS tereduksi, VNS miring, dekomposisi pencarian variabel, VNS paralel adalah teknik yang banyak digunakan untuk menyelesaikan masalah pemrograman matematika [10]. Secara keseluruhan, VNS sederhana dan dapat diterapkan secara luas. Lebih efisien untuk menghasilkan kualitas solusi yang baik dalam waktu CPU yang wajar. Penerapan VNS meliputi teori lokasi, desain jaringan, ukuran lot, masalah pengumpulan, keandalan, geometri, dan desain telekomunikasi.
Ringkasan ringkasnya
Metaheuristik digunakan untuk menemukan solusi yang cukup baik untuk masalah optimasi. Metaheuristik lebih sederhana untuk dirancang dan diimplementasikan [17]. Beberapa algoritma metaheuristik mapan yang dapat menyelesaikan masalah optimasi dalam jangka waktu yang wajar dijelaskan dalam artikel ini. Pengembangan algoritma yang efektif adalah proses perbaikan yang berkelanjutan. Beberapa prosedur pencarian, algoritma yang terinspirasi dari alam sedang dikembangkan untuk memecahkan berbagai masalah optimasi yang kompleks.
Mengingat kelebihannya, metaheuristik adalah strategi yang memandu proses pencarian. Ada teknik pencarian lokal sederhana hingga proses pembelajaran kompleks yang tersedia dalam bentuk algoritma berulang. Metaheuristik adalah metode solusi perkiraan dan biasanya bersifat non-deterministik [3]. Aspek penting dari metaheuristik bukanlah masalah yang spesifik, dan karenanya masalah optimasi apa pun dapat diselesaikan dengan mudah untuk dipahami. Namun demikian, meskipun popularitas dan kemanjuran praktisnya, metode metaheuristik memberikan kualitas solusi yang tidak memadai. Ini sangat bergantung pada implementasi yang tepat dan penyetelan hyperparameter, yang merupakan lanskap pengoptimalan lainnya [2].
Mempertimbangkan platform implementasi metaheuristik untuk memecahkan masalah dunia nyata, MATLAB [15] memiliki algoritma GA, SA, dan gerombolan partikel bawaan. Demikian pula, banyak paket dikembangkan menggunakan berbagai bahasa pemrograman seperti C ++ , Java, dan Python (misalnya, [18]) untuk memecahkan masalah optimasi.
Disadur dari: informs.org