Bab 11 Pengantar Particle Swarm Optimization dan Ant Colony Optimization

Pengantar Particle Swarm Optimization dan Ant Colony Optimization

A. Optimasi Kawanan Partikel

Particle swarm optimization (PSO) adalah teknik optimisasi stokastik berbasis populasi yang dikembangkan oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995, yang terinspirasi oleh perilaku sosial pengelompokan burung atau pendidikan ikan. PSO memiliki banyak kesamaan dengan teknik komputasi evolusioner seperti Genetic Algorithms (GA). Sistem diinisialisasi dengan populasi solusi acak dan mencari optima dengan memperbarui generasi. Namun, tidak seperti GA, PSO tidak memiliki operator evolusi seperti crossover dan mutasi. Di PSO, solusi potensial, yang disebut partikel, terbang melalui ruang masalah dengan mengikuti partikel optimal saat ini.

Latar Belakang Pengoptimalan Kawanan Partikel

Particle swarm optimization (PSO) adalah suatu bentuk kecerdasan segerombolan dan diilhami oleh burung-burung, sekolah-ikan dan pertanian-serangga, burung-burung, ikan-ikan, dan-sekawanan serangga seperti yang ditunjukkan pada Gambar 11.1.

Ini dilakukan oleh partikel dalam ruang multidimensi yang memiliki posisi dan kecepatan. Partikel-partikel ini terbang melalui hyperspace (mis., N) dan memiliki dua kemampuan penalaran penting: ingatan mereka tentang posisi terbaik dan pengetahuan mereka tentang bidadari terbaik, "terbaik" hanya berarti tentang posisi dengan nilai obyektif yang paling kecil.sesuaikan posisi dan kecepatan mereka sendiri berdasarkan posisi yang baik ini. 

Ada dua cara utama ini dilakukan: 

• terbaik global yang diketahui oleh semua dan segera diperbarui ketika posisi terbaik baru ditemukan oleh setiap partikel di kawanan 

• “lingkungan” terbaik di mana masing-masing partikel hanya segera berkomunikasi dengan subset dari berkerumun tentang posisi terbaik

Pengoperasian Partikel Swarm Optimization

PertimbangkanSarmarmartikel terbang melaluiparametermencariuntuk optimal. Setiap partikel ditandai oleh,

Vektor posisi ..... xi (t) 

Vektor kecepatan ...... vi (t)

seperti yang ditunjukkan pada Gambar. 11.2. Selama proses tersebut, setiap partikel akan memiliki pengetahuan individual masing-masing, yaitu yang terbaik sejauh ini dalam posisi dan pengetahuan sosial yang terbaik, yaitu, tetangga terbaik yang ditunjukkan pada Gambar 11.3. Melakukan pembaruan kecepatan, menggunakan rumus yang diberikan di bawah ini,

vi(t +1) = αv i +c1 ×rand×(pbest(t)-xi(t))+c2 ×rand×(gbest(t)-xi(t)) (11.1)

di mana α adalah bobot inersia yang mengontrol eksplorasi dan eksploitasi ruang pencarian. c1 dan c2, komponen kognisi dan sosial masing-masing adalah konstanta percepatan yang mengubah kecepatan partikel menuju pbest dan gbest. rand adalah angka acak antara 0 dan 1. Biasanya nilai c1 dan c2 diatur ke 2. Pembaruan kecepatan didasarkan pada parameter seperti yang ditunjukkan pada Gambar 11.4.

Sekarang, lakukan pembaruan posisi,

Xi(t +1) = Xi(t)+Vi(t +1) 

Proses pembaruan posisi adalah seperti yang ditunjukkan pada Gambar. 11.5

Tanpa syarat kedua dan ketiga, sang agen akan memanggil "terbang" di tempat yang ditentukan untuk sampai ke batas. Yaitu, ia mencoba untuk menjelajahi daerah baru dan, oleh karena itu, istilah pertama sesuai dengan diversifikasi dalam prosedur pencarian. Di sisi lain, tanpa istilah pertama, kecepatan agen "terbang" hanya ditentukan dengan menggunakan posisi saat ini dan posisi terbaiknya dalam sejarah. Yaitu, agen-agen akan mencoba untuk mempertukarkan hama dan / atau gbest mereka dan, oleh karena itu, istilah-istilah tersebut sesuai dengan intensifikasi dalam prosedur pencarian.

Aliran Dasar dari Optimasi Kawanan Partikel

Operasi dasar PSO diberikan oleh,

Langkah 1: Inisialisasi gerombolan dari ruang solusi. 

Langkah 2: Mengevaluasi kecocokan partikel individu.

Langkah 3: Memodifikasi gbest, pbest, dan kecepatan. 

Langkah 4: Pindahkan setiap partikel ke posisi baru.

Kode pseudo dari prosedur adalah sebagai berikut :

Sementara iterasi maksimum atau kriteria kesalahan minimum tidak tercapai kecepatan Partikel pada setiap dimensi dijepit ke Vmax kecepatan maksimum. Jika jumlah akselerasi akan menyebabkan kecepatan pada dimensi itu melebihi Vmax, yang merupakan parameter yang ditentukan oleh pengguna. Maka kecepatan pada dimensi itu terbatas pada Vmax. 

Bagan dasar dari optimasi Partikel Swarm adalah seperti yang ditunjukkan pada Gambar. 11.6. Dalam Repositori itu mengacu pada lokasi memori masing-masing partikel.

Sebagian besar teknik evolusi memiliki prosedur berikut: 

1. Pembangkitan acak populasi awal 

2. Perhitungan nilai kecocokan untuk setiap subjek. Ini akan langsung tergantung pada jarak ke optimal. 

3. Reproduksi populasi berdasarkan nilai-nilai kebugaran. 

4. Jika persyaratan terpenuhi, maka berhentilah. Kalau tidak kembali ke 2. 

Dari prosedur, orang dapat mengetahui bahwa PSO berbagi banyak poin umum dengan GA. Kedua algoritma dimulai dengan sekelompok populasi yang dihasilkan secara acak; keduanya memiliki nilai kecekatan untuk mengevaluasi populasi. Keduanya memperbarui populasi dan mencari yang optimal dengan teknik acak. Kedua sistem tidak menjamin kesuksesan. Namun, PSO tidak memiliki operator genetik seperti crossover dan mutasi. Partikel memperbarui diri dengan kecepatan internal. Mereka juga memiliki memori, yang penting bagi algoritma. Dibandingkan dengan algoritma genetika (GAs), mekanisme berbagi informasi dalam PSO sangat berbeda.

Aplikasi PSO

PSO telah berhasil diterapkan di banyak bidang: optimasi fungsi, pelatihan jaringan saraf tiruan, kontrol sistem fuzzy, dan area lain di mana GA dapat diterapkan. Berbagai area aplikasi dari Particle Swarm Optimization meliputi: 

• Operasi dan kontrol Sistem Daya 

• Masalah kombinatorial NP-Hard 

• Masalah Penjadwalan Pekerjaan 

• Masalah Rute Kendaraan 

• Jaringan Seluler 

• Pemodelan parameter yang dioptimalkan 

• Penjadwalan proses batch 

• Masalah optimasi multi-tujuan 

• Masalah pengoptimalan gambar multi

B. Optimalisasi Koloni Semut

Ant Colony Optimization (ACO) adalah berbasis populasi, penelitian umum tentang teknik pemecahan masalah kultivatori, yang dipicu oleh jejak feromon perilaku peletakan koloni semut nyata. Di ACO, satu set agen perangkat lunak yang disebut semut buatan mencari solusi yang bagus untuk masalah optimisasi tertentu. Untuk menerapkan ACO, masalah optimisasi ditransformasikan ke dalam masalah menemukan jalur terbaik pada grafik berbobot. Semut buatan (selanjutnya disebut semut) secara bertahap membangun solusi dengan bergerak pada grafik. Proses konstruksi solusi bersifat stokastik dan bias oleh model feromon, yaitu, seperangkat parameter yang terkait dengan komponen grafik (baik node atau tepi) yang nilainya dimodifikasi pada saat runtime oleh semut.

Latar Belakang Partisipasi Kawanan Partikel

Particle swarm optimization (PSO) adalah suatu bentuk kecerdasan segerombolan dan diilhami oleh burung-burung, sekolah-ikan dan pertanian-serangga, burung-burung, ikan-ikan, dan-sekawanan serangga seperti yang ditunjukkan pada Gambar 11.1. 

Pertimbangkan Gambar 11.1 dan bayangkan segerombolan serangga atau sekolah ikan. Jika seseorang melihat jalan yang diinginkan untuk pergi (mis., Untuk makanan, perlindungan, dll.), Segerombolan segerombolan akan dapat mengikuti dengan cepat bahkan jika mereka berada di sisi yang berlawanan dari segerombolan.

Anggota segerombolan berkomunikasi posisi yang baik satu sama lain dan sesuaikan posisi dan kecepatan mereka sendiri berdasarkan posisi yang baik ini. Ada dua cara utama ini dilakukan: 

• terbaik global yang diketahui oleh semua dan segera diperbarui ketika posisi terbaik baru ditemukan oleh setiap partikel di kawanan 

• “lingkungan” terbaik di mana masing-masing partikel hanya segera berkomunikasi dengan subset dari berkerumun tentang posisi terbaik

Pengoperasian Partikel Swarm Optimization

PertimbangkanSarmarmartikel terbang melaluiparametermencariuntuk optimal. Setiap partikel ditandai oleh,

Vektor posisi ..... xi (t) 

Vektor kecepatan ...... vi (t)

seperti yang ditunjukkan pada Gambar. 11.2. 

Selama proses tersebut, setiap partikel akan memiliki pengetahuan individual masing-masing, yaitu yang terbaik sejauh ini dalam posisi dan pengetahuan sosial yang terbaik, yaitu, tetangga terbaik yang ditunjukkan pada Gambar 11.3. 

Melakukan pembaruan kecepatan, menggunakan rumus yang diberikan di bawah ini,

vi (t +1) = αv i + c1 × rand × (pbest (t) -xi (t)) + c2 × rand × (gbest (t) -xi (t)) (11.1)

di mana α adalah bobot inersia yang mengontrol eksplorasi dan eksploitasi ruang pencarian. c1 dan c2, komponen kognisi dan sosial masing-masing adalah konstanta percepatan yang mengubah kecepatan partikel menuju pbest dan gbest. rand adalah angka acak antara 0 dan 1. Biasanya nilai c1 dan c2 diatur ke 2. 

Pembaruan kecepatan didasarkan pada parameter seperti yang ditunjukkan pada Gambar 11.4. 

Sekarang, lakukan pembaruan posisi,

Xi (t +1) = Xi (t) + Vi (t +1) (11.2) 

Proses pembaruan posisi adalah seperti yang ditunjukkan pada Gambar. 11.5 Proses di atas yang diulang diulang untuk masing-masing dan setiap partikel dipertimbangkan dalam perhitungan dan solusi optimal terbaik diperoleh.

Aliran Dasar dari Optimasi Kawanan Partikel

Operasi dasar PSO diberikan oleh,

Langkah 1: Inisialisasi gerombolan dari ruang solusi. 

Langkah 2: Mengevaluasi kecocokan partikel individu. 

Langkah 3: Memodifikasi gbest, pbest, dan kecepatan. 

Langkah 4: Pindahkan setiap partikel ke posisi baru.

Kode pseudo dari prosedur adalah sebagai berikut :

Sementara iterasi maksimum atau kriteria kesalahan minimum tidak tercapai kecepatan Partikel pada setiap dimensi dijepit ke Vmax kecepatan maksimum. Jika jumlah akselerasi akan menyebabkan kecepatan pada dimensi itu melebihi Vmax, yang merupakan parameter yang ditentukan oleh pengguna. Maka kecepatan pada dimensi itu terbatas pada Vmax. 

Bagan dasar dari optimasi Partikel Swarm adalah seperti yang ditunjukkan pada Gambar. 11.6. Dalam Repositori itu mengacu pada lokasi memori masing-masing partikel.

Perbandingan Antara PSO dan GA

Kekuatan GAS adalah dalam sifat paralel dari pencarian mereka. GA menerapkan bentuk panjat bukit yang kuat yang melindungi banyak solusi, menghilangkan solusi yang tidak menjanjikan, dan memberikan solusi yang masuk akal. Melalui operator genetik, bahkan solusi yang lemah dapat terus menjadi bagian dari susunan solusi kandidat di masa depan. Operator genetik yang digunakan adalah pusat keberhasilan pencarian. Semua GA memerlukan beberapa bentuk rekombinasi, karena hal ini memungkinkan terciptanya solusi baru yang, berdasarkan keberhasilan orang tua mereka, memiliki probabilitas yang lebih tinggi untuk menunjukkan kinerja yang baik. Dalam praktiknya, crossover adalah operator genetik utama, sedangkan mutasi sangat sering digunakan. Mutasi harus dilakukan untuk mempertahankan aspek manfaat dari solusi kandidat dan untuk menghilangkan komponen yang tidak diinginkan, sementara sifat mutasi acak mungkin lebih cenderung menurunkan solusi kandidat yang kuat daripada memperbaikinya. Sumber lain dari kekuatan algoritme adalah paralelisme implisit paralelnya dalam metafor revolusioner dengan perpisahan. Dengan membatasi produksi kandidat yang lemah, GAdapatdilakukan dengan cara yang sama hanya dengan solusi, tetapi juga semua keturunannya. Hal ini cenderung membuat algoritma cenderung bertemu ke solusi berkualitas tinggi dalam beberapa generasi.

Applications of PSO

PSO telah berhasil diterapkan di banyak bidang: optimasi fungsi, pelatihan jaringan saraf tiruan, kontrol sistem fuzzy, dan area lain di mana GA dapat diterapkan. Berbagai area aplikasi dari Particle Swarm Optimization meliputi: 

• Operasi dan kontrol Sistem Daya 

• Masalah kombinatorial NP-Hard 

• Masalah Penjadwalan Pekerjaan 

• Masalah Rute Kendaraan 

• Jaringan Seluler 

• Pemodelan parameter yang dioptimalkan 

• Penjadwalan proses batch 

• Masalah optimasi multi-tujuan 

• Masalah pengoptimalan gambar multi

C. Optimalisasi Koloni Semut

AntColonyOptimization (ACO) adalah berbasis populasi, penelitian umum tentang teknik pemecahan masalah kultivator, yang dipicu oleh jejak feromon yang membentuk perilaku koloni semut nyata. Di ACO, satu set agen perangkat lunak yang disebut semut buatan mencari solusi yang bagus untuk masalah optimisasi tertentu. Untuk menerapkan ACO, masalah optimisasi ditransformasikan ke dalam masalah menemukan jalur terbaik pada grafik berbobot. Semut buatan (selanjutnya disebut semut) secara bertahap membangun solusi dengan bergerak pada grafik. Proses konstruksi solusi bersifat stokastik dan bias oleh model feromon, yaitu, seperangkat parameter yang terkait dengan komponen grafik (baik node atau tepi) yang nilainya dimodifikasi pada saat runtime oleh semut.

Inspirasi Biologis

Dua karakteristik utama dari stigmergy yang membedakannya dari bentuk komunikasi lainnya adalah sebagai berikut. 

• Stigmergy adalah bentuk komunikasi tidak langsung dan simbolis yang dimediasi oleh lingkungan: pertukaran informasi serangga dengan memodifikasi lingkungan mereka, dan 

• Informasi stigmergik adalah lokal: ia hanya dapat diakses oleh serangga yang mengunjungi tempat di mana ia dilepaskan (atau lingkungan terdekatnya). 

Stigmergy adalah bentuk komunikasi tidak langsung dan tidak sinkron di mana serangga memanipulasi lingkungan untuk mengirimkan informasi ke serangga lain, yang kemudian merespons perubahan tersebut.

Elemen utama dari sistem stigmergik biologis ditunjukkan pada Gambar. 11.7: 

• Serangga sebagai individu yang bertindak. 

• Pheromone sebagai pembawa informasi, digunakan untuk membuat bidang disipasi. 

• Lingkungan sebagai mekanisme tampilan dan distribusi untuk informasi. 

Contoh-contoh stigmergy dapat diamati pada koloni semut. Pada banyak spesies semut, semut berjalan ke dan dari sumber makanan di tanah, zat yang disebut feromon. Selain itu, ada kemungkinan kehadiran feromon dan cenderung mengikuti jalur yang lebih tinggi. Dengan mekanisme ini, semut mampu membawa makanan ke sarangnya dengan cara yang sangat efektif. Perilaku dasar semut dibahas sebagai berikut:

Semut sungguhan mampu menemukan jalur terpendek dari sumber makanan ke sarang tanpa menggunakan petunjuk visual. Juga, mereka mampu beradaptasi dengan perubahan di lingkungan, misalnya menemukan jalur terpendek baru setelah yang lama tidak lagi layak karena kendala baru. Pertimbangkan Gambar 11.8 berikut ini di mana semut bergerak pada garis lurus, yang menghubungkan sumber makanan ke sarang:

Diketahui bahwa cara utama yang digunakan oleh semut untuk membentuk dan memelihara garis adalah jejak feromon. Semut menyimpan feromon dalam jumlah tertentu sambil berjalan, dan setiap semut kemungkinan akan mengikuti arahan yang kaya akan feromon daripada yang lebih miskin. Perilaku dasar semut sungguhan ini dapat digunakan untuk menjelaskan bagaimana mereka dapat menemukan jalur terpendek, yang menghubungkan kembali garis putus setelah kemunculan tiba-tiba dari hambatan yang tak terduga, telah mengganggu jalur awal (Gbr. 11.9).