Genetic Algorithm Optimazation Problems
Optimalisasi pada proses optimal untuk mengatasi masalah yang menjadi pertimbangan utama. Optimalisasi Optimal dan Ant Colony Optimization mencapai solusi optimal untuk masalah pencarian dengan menggunakan perilaku sosial organisme hidup. Pengoptimalan partikel partikel adalah bentuk kecerdasan swarm dan pengoptimalan koloni Ant adalah metaheuristik berbasis populasi yang dapat digunakan untuk mengatasi masalah hidrodinamika sehingga dapat memecahkan masalah optimasi.
Partikel swarm optimization (PSO) adalah teknik optimasi stokastik berbasis populasi yang dikembangkan oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995, terinspirasi oleh perilaku sosial aliran burung atau sekolah ikan. PSO memiliki banyak kesamaan dengan teknik komputasi evolusioner seperti Genetic Algorithms (GA). Sistem ini diinisialisasi dengan populasi solusi acak dan pencarian optima dengan memperbarui generasi.
Pada PSO, partikel-partikel tersebut, disebut partikel, melewati ruang masalah dengan mengikuti partikel optimum saat ini.
Partikel swarm optimasi telah digunakan untuk pendekatan yang dapat digunakan di berbagai aplikasi, serta untuk aplikasi tertentu difokuskan pada persyaratan tertentu.
11.2.1 Latar Belakang Optimasi Swarm Partikel
Partikel swarm optimization (PSO) adalah bentuk kecerdasan swarm dan terinspirasi oleh aliran burung, bulu tangkis dan serangga.
Perhatikan Gambar 11.1 dan bayangkan segerombolan serangga atau sekolah ikan. Jika seseorang melihat jalur yang diinginkan untuk dikunjungi (mis., Untuk makanan, perlindungan, dll.), Kawanan lainnya akan dapat mengikuti dengan cepat meskipun mereka berada di sisi yang berlawanan dari kawanan.
Ada dua cara utama yang harus dilakukan:
• terbaik global yang diketahui semua dan segera diperbarui saat posisi terbaik baru ditemukan oleh partikel manapun di kawanan
• "lingkungan" paling baik dimana masing-masing partikel segera berkomunikasi dengan subset kawanan tentang posisi terbaik
Setiap partikel melacak koordinatnya di ruang masalah yang dikaitkan dengan solusi terbaik (kesesuaian) yang telah dicapai sejauh ini. (Nilai ketahanan juga disimpan.) Nilai ini disebut pbest. Nilai "terbaik" lain yang dilacak oleh optimizer partikel adalah nilai terbaik, sejauh ini diperoleh partikel partikel tetangga. Lokasi ini disebut lbest.
11.2.2 Pengoperasian Optimasi Partikel Swarm
Sebaiknya perhatikan bagian-bagian yang ada di bawah batas-batas yang dicari untuk optimum. Setiap partikel dicirikan oleh,
Vektor posisi ..... xi (t)
Vektor kecepatan ...... vi (t)
seperti ditunjukkan pada Gambar 11.2.
Selama proses berlangsung, masing-masing partikel memiliki pengetahuan masing-masing, yaitu, best-so-far terbaiknya di posisi dan pengetahuan sosial, yang paling baik dari tetangganya yang terbaik ditunjukkan pada Gambar 11.3.
Update kecepatan didasarkan pada parameter seperti yang ditunjukkan pada Gambar 11.4.
Sekarang, melakukan update posisi,
Proses update posisi seperti ditunjukkan pada Gambar 11.5
Proses di atas dibahas berulang-ulang untuk setiap partikel evry yang dipertimbangkan dalam perhitungan dan solusi optimal terbaik diperoleh.
11.2.3 Arus Dasar Pengoptimalan Partikel Swarm
Operasi dasar PSO diberikan oleh,
Langkah 1: Inisialisasi kawanan dari ruang solusi
Langkah 2: Evaluasi kesesuaian masing-masing partikel
Langkah 3: Ubah gbest, pbest dan velocity
Langkah 4: Pindahkan setiap partikel ke posisi baru
Langkah 5: Goto langkah 2, dan ulangi sampai konvergensi menghentikan kondisi terpenuhi
11.2.4 Perbandingan antara PSO dan GA
Kekuatan GA adalah sifat paralel pencarian mereka. GA menerapkan bentuk pendakian bukit yang kuat yang mempertahankan banyak solusi, menghapus solusi yang tidak menjanjikan, dan memberikan solusi yang masuk akal. Melalui operator genetika, solusi yang lemah bahkan bisa terus menjadi bagian dari solusi kandidat masa depan. Operator genetik yang digunakan sangat penting bagi keberhasilan pencarian. Semua GA memerlukan beberapa bentuk rekombinasi, karena ini memungkinkan terciptanya solusi baru yang dimiliki, berdasarkan keberhasilan orang tua mereka, probabilitas yang lebih tinggi untuk menunjukkan kinerja yang baik.
Sebagian besar teknik evolusioner memiliki prosedur sebagai berikut:
1. Generasi acak dari populasi awal
2. Menghitung nilai kesesuaian untuk setiap subjek. Ini akan langsung tergantung dari jarak ke optimum.
3. Reproduksi penduduk berdasarkan nilai kesesuaian.
4. Jika persyaratan dipenuhi, maka berhentilah. Jika tidak, kembali ke 2.
11.2.5 Aplikasi PSO
PSO telah berhasil diterapkan di banyak bidang: optimasi fungsi, pelatihan jaringan syaraf tiruan, kontrol sistem fuzzy, dan area lain dimana GA dapat diterapkan. Berbagai area aplikasi Particle Swarm Optimization meliputi:
• Operasi dan kontrol Sistem Daya
• Masalah kombinatorial NP-Hard
• Masalah Penjadwalan Pekerjaan
• Masalah Routing Kendaraan
• Jaringan Mobile
• Pemodelan parameter optimal
• Penjadwalan proses batch
• Masalah optimasi multi obyektif
• Pengolahan citra dan masalah pengenalan pola dan sebagainya.
Pada PSO, partikel-partikel tersebut, disebut partikel, melewati ruang masalah dengan mengikuti partikel optimum saat ini.
Partikel swarm optimasi telah digunakan untuk pendekatan yang dapat digunakan di berbagai aplikasi, serta untuk aplikasi tertentu difokuskan pada persyaratan tertentu.
11.2.1 Latar Belakang Optimasi Swarm Partikel
Partikel swarm optimization (PSO) adalah bentuk kecerdasan swarm dan terinspirasi oleh aliran burung, bulu tangkis dan serangga.
Perhatikan Gambar 11.1 dan bayangkan segerombolan serangga atau sekolah ikan. Jika seseorang melihat jalur yang diinginkan untuk dikunjungi (mis., Untuk makanan, perlindungan, dll.), Kawanan lainnya akan dapat mengikuti dengan cepat meskipun mereka berada di sisi yang berlawanan dari kawanan.
Ada dua cara utama yang harus dilakukan:
• terbaik global yang diketahui semua dan segera diperbarui saat posisi terbaik baru ditemukan oleh partikel manapun di kawanan
• "lingkungan" paling baik dimana masing-masing partikel segera berkomunikasi dengan subset kawanan tentang posisi terbaik
Setiap partikel melacak koordinatnya di ruang masalah yang dikaitkan dengan solusi terbaik (kesesuaian) yang telah dicapai sejauh ini. (Nilai ketahanan juga disimpan.) Nilai ini disebut pbest. Nilai "terbaik" lain yang dilacak oleh optimizer partikel adalah nilai terbaik, sejauh ini diperoleh partikel partikel tetangga. Lokasi ini disebut lbest.
11.2.2 Pengoperasian Optimasi Partikel Swarm
Sebaiknya perhatikan bagian-bagian yang ada di bawah batas-batas yang dicari untuk optimum. Setiap partikel dicirikan oleh,
Vektor posisi ..... xi (t)
Vektor kecepatan ...... vi (t)
seperti ditunjukkan pada Gambar 11.2.
Selama proses berlangsung, masing-masing partikel memiliki pengetahuan masing-masing, yaitu, best-so-far terbaiknya di posisi dan pengetahuan sosial, yang paling baik dari tetangganya yang terbaik ditunjukkan pada Gambar 11.3.
Update kecepatan didasarkan pada parameter seperti yang ditunjukkan pada Gambar 11.4.
Sekarang, melakukan update posisi,
Proses update posisi seperti ditunjukkan pada Gambar 11.5
Proses di atas dibahas berulang-ulang untuk setiap partikel evry yang dipertimbangkan dalam perhitungan dan solusi optimal terbaik diperoleh.
11.2.3 Arus Dasar Pengoptimalan Partikel Swarm
Operasi dasar PSO diberikan oleh,
Langkah 1: Inisialisasi kawanan dari ruang solusi
Langkah 2: Evaluasi kesesuaian masing-masing partikel
Langkah 3: Ubah gbest, pbest dan velocity
Langkah 4: Pindahkan setiap partikel ke posisi baru
Langkah 5: Goto langkah 2, dan ulangi sampai konvergensi menghentikan kondisi terpenuhi
11.2.4 Perbandingan antara PSO dan GA
Kekuatan GA adalah sifat paralel pencarian mereka. GA menerapkan bentuk pendakian bukit yang kuat yang mempertahankan banyak solusi, menghapus solusi yang tidak menjanjikan, dan memberikan solusi yang masuk akal. Melalui operator genetika, solusi yang lemah bahkan bisa terus menjadi bagian dari solusi kandidat masa depan. Operator genetik yang digunakan sangat penting bagi keberhasilan pencarian. Semua GA memerlukan beberapa bentuk rekombinasi, karena ini memungkinkan terciptanya solusi baru yang dimiliki, berdasarkan keberhasilan orang tua mereka, probabilitas yang lebih tinggi untuk menunjukkan kinerja yang baik.
Sebagian besar teknik evolusioner memiliki prosedur sebagai berikut:
1. Generasi acak dari populasi awal
2. Menghitung nilai kesesuaian untuk setiap subjek. Ini akan langsung tergantung dari jarak ke optimum.
3. Reproduksi penduduk berdasarkan nilai kesesuaian.
4. Jika persyaratan dipenuhi, maka berhentilah. Jika tidak, kembali ke 2.
11.2.5 Aplikasi PSO
PSO telah berhasil diterapkan di banyak bidang: optimasi fungsi, pelatihan jaringan syaraf tiruan, kontrol sistem fuzzy, dan area lain dimana GA dapat diterapkan. Berbagai area aplikasi Particle Swarm Optimization meliputi:
• Operasi dan kontrol Sistem Daya
• Masalah kombinatorial NP-Hard
• Masalah Penjadwalan Pekerjaan
• Masalah Routing Kendaraan
• Jaringan Mobile
• Pemodelan parameter optimal
• Penjadwalan proses batch
• Masalah optimasi multi obyektif
• Pengolahan citra dan masalah pengenalan pola dan sebagainya.
Ant Colony Optimization (ACO) berbasis isapopulasi, bersifat umum untuk mengatasi masalah evolusi atau masalah kultivator, yang biasanya disebabkan oleh jejak gembala yang meletakan perilaku koloni semut yang sesungguhnya. Di ACO, satu set agen perangkat lunak yang disebut semut buatan mencari solusi yang baik untuk masalah optimasi yang diberikan. Untuk menerapkan ACO, masalah optimasi ditransformasikan menjadi masalah untuk menemukan jalur terbaik pada grafik tertimbang.
11.3.1 Inspirasi Biologis
Pada tahun 40an dan 50an abad ke-20, ahli entomologi Prancis Pierre-Paul Grass mengamati bahwa beberapa spesies rayap bereaksi terhadap apa yang dia sebut "rangsangan yang signifikan". Dia mengamati bahwa efek dari reaksi ini dapat bertindak sebagai rangsangan baru yang signifikan bagi serangga yang menghasilkannya dan serangga lainnya di koloni tersebut. Rumput menggunakan istilah stigmergy untuk menggambarkan jenis komunikasi tertentu di mana "pekerja dirangsang oleh kinerja yang telah mereka capai".
Dua karakteristik utama stigmergy yang membedakannya dari bentuk komunikasi lainnya adalah sebagai berikut.
• Stigmergy adalah bentuk komunikasi tidak langsung dan tidak simbolik yang dimediasi oleh lingkungan: serangga bertukar informasi dengan memodifikasi lingkungan mereka;
• Stigmergicinformationis lokal: hanya dapat diakses oleh serangga yang mengunjungi lokus tempat pelepasannya (atau lingkungan terdekatnya).
Stigmergy adalah bentuk komunikasi tidak langsung dan asinkron dimana serangga memanipulasi lingkungan untuk mengangkut informasi ke serangga lainnya, yang kemudian merespons perubahan tersebut.
Unsur-unsur utama dari sistem stigmergik biologis ditunjukkan pada Gambar 11.7:
• Serangga sebagai individu yang bertindak.
• Feromon merupakan pembawa informasi, yang digunakan untuk membuat medan disipasi.
• Lingkungan adalah mekanisme display dan distribusi informasi.
Perhatikan Gambar 11.8 berikut dimana semut bergerak pada garis lurus, yang menghubungkan sumber makanan ke sarang:
Sudah diketahui dengan pasti bahwa sarana utama yang digunakan oleh semut untuk membentuk dan memelihara garis adalah jalur feromon. Semut menyimpan sejumlah feromon sambil berjalan, dan setiap semut secara probabilistik lebih memilih mengikuti arah yang kaya pheromonerather daripada yang lebih buruk. Perilaku dasar semut asli ini dapat digunakan untuk menjelaskan bagaimana mereka dapat menemukan jalan terpendek, yang menghubungkan kembali garis putus-putus setelah munculnya rintangan tak terduga, telah mengganggu jalur awal (Gambar 11.9).
Sebenarnya, begitu rintangan telah muncul, semut-semut itu, yang berada tepat di depan rintangan, tidak dapat terus mengikuti jejak feromon dan oleh karena itu mereka harus memilih antara belok kanan atau kiri. Dalam situasi ini kita bisa mengharapkan setengah semut untuk memilih berbelok ke kanan dan separuh lainnya berbelok ke kiri. Situasi yang sama dapat ditemukan di sisi lain dari hambatan (Gambar 11.10).
Karena proses umpan balik positif ini (autocatalytic), segera semut semua semut akan memilih jalan yang lebih pendek (Gambar 11.11).
11.3.2 Kesamaan dan Perbedaan Antara Semut Nyata dan Semangat Artistik
Ada beberapa perbedaan dan persamaan antara semut asli dan buatan yang dapat dinyatakan sebagai berikut: 11.3.2.1 Kesamaan
• Koloni individu yang bekerja sama - Baik koloni semut asli dan algoritma semut terdiri dari populasi, atau koloni agen individu independen.
• Pheromonetrailandstigmergy-Likerealan, pecandu artifisial saling berbagi tentang lingkungan mereka yang dideritanya.
• Gerakan lokal dan pencarian jalur terpendek-Meskipun semut nyata berjalan melalui negara-negara yang berdekatan dan semut buatan melompat dari satu ke yang lain keadaan berdekatan dari masalah yang dipertimbangkan, baik jalan kaki maupun lompatan memiliki tujuan yang sama, yaitu menemukan saluran yang paling tepat antara titik pusat dan titik temu.
• Kebijakan transisi - Baik semut dan buatan asli akan membangun solusi dengan menerapkan prosedur pengambilan keputusan untuk bergerak melalui negara-negara yang berdekatan.
11.3.2.2 Perbedaan
Perbedaannya sebagai berikut:
• Semut-semut artistik tinggal di dunia yang terpisah. Semua gerakan mereka melompat dari satu keadaan diskrit ke sisi yang lain.
• Semut artistik memiliki ingatan, mereka dapat mengingat keadaan yang telah dikunjungi (daftar tabu dalam model ini).
• Metodologi deposit feromon secara signifikan berbeda antara semut asli dan buatan. Waktu dalam pheromonelaying adalah masalah tergantung dan sering tidak memiliki kesamaan dengan metodologi deposit feromon semut yang sesungguhnya.
• Untuk meningkatkan kinerja secara keseluruhan, algoritma AS dapat diperkaya dengan beberapa kemampuan tambahan yang tidak dapat ditemukan di koloni semut yang sebenarnya.
11.3.3 Karakteristik Ant Colony Optimization
Karakteristik optimasi koloni semut adalah sebagai berikut:
• Algoritma alami karena didasarkan pada perilaku semut nyata dalam membangun jalur dari koloni mereka menjadi sumber makanan dan kembali.
• Paralel dan terdistribusi karena menyangkut populasi agen yang bergerak secara bersamaan, mandiri dan tanpa atasan.
• Koperasi karena masing-masing agen memilih jalur berdasarkan informasi, jalur feromon yang diletakkan oleh agen lainnya, yang sebelumnya telah memilih samepath.
• Serbaguna bahwa hal itu dapat diterapkan pada versi yang sama dari masalah yang sama;
• Kuat bahwa hal itu dapat diterapkan dengan sedikit perubahan pada masalah optimasi kombinatorial lainnya seperti masalah penugasan kuadrat (QAP) dan masalah penjadwalan jobshop (JSP).
11.3.4 Algoritma Optimasi Koloni
Algoritma optimasi koloni semut yang berbeda telah diusulkan. Algoritma optimasi koloni semut asli dikenal sebagai Sistem Ant dan diusulkan pada awal tahun 90an. Sejak itu, sejumlah algoritma ACO lainnya diperkenalkan. Tabel 11.1 memberikan daftar varian Algoritma Optimasi Ant Colony yang berhasil.
Gambar 11.14 memberikan gambaran sempit tentang Algoritma Optimasi Ant Colony.
ACO adalah kelas algoritma, yang anggota pertamanya, yang disebut Ant System, awalnya diusulkan oleh Colorni, Dorigo dan Maniezzo.
11.3.4.1 Sistem Semut
Sistem yang diterapkan pada masalah Sales Man dibicarakan di sini. Ciri utamanya adalah bahwa, pada setiap iterasi, pheromonevalues diperbarui oleh semut m yang telah membangun solusi dalam iterasi itu sendiri.
11.3.4.2 Sistem Koloni Ant
Sumbangan ACS yang paling menarik adalah pengenalan pembaruan pheromone di samping update pheromone yang dilakukan pada akhir proses konstruksi (disebut feromon flut). Feromon lokal dilakukan oleh semua semut setelah setiap tahap konstruksi. Setiap semut menerapkannya hanya pada tepi terakhir yang dilalui:
11.3.4.3 Arus Dasar ACO
Arus operasional dasar dalam Ant Colony Optimization adalah sebagai berikut: Langkah 1: Mewakili ruang solusi dengan grafik konstruksi
Langkah 2: Inisialisasi parameter ACO
Langkah 3: Menghasilkan solusi acak dari setiap perjalanan acak semut
Langkah 4: Update pheromoneintensities
Langkah 5: Goto Langkah 3, dan ulangi sampai convergenceor kondisi berhenti puas.
Algoritma semut generik diberikan seperti ditunjukkan pada Gambar 11.15,
Algoritma Optimalisasi Optimalisasi Teorema Primer seperti ditunjukkan pada Gambar 11.16.
Prosedur langkah demi langkah untuk mengatasi masalah optimasi kombinatorial menggunakan ACO secara singkat adalah:
• Mewakili masalah dalam bentuk kumpulan komponen dan transisi atau dengan cara grafik tertimbang yang dilakukan oleh semut untuk membangun solusi.
• Menentukan dengan tepat arti jalur feromon, yaitu jenis keputusan yang mereka bias. Ini adalah langkah penting dalam implementasi algoritma ACO. Definisi jalur feromon yang baik bukanlah tugas sepele dan biasanya memerlukan pemahaman tentang masalah yang dipecahkan.
• Secara tepat menentukan preferensi heuristik terhadap setiap keputusan yang harus diambil seekor semut saat membangun solusi, yaitu, menentukan informasi heuristik yang terkait dengan setiap transisi komponen. Perhatikan bahwa informasi heuristik sangat penting untuk kinerja yang baik jika algoritma pencarian lokal tidak tersedia atau tidak dapat diterapkan.
• Jika memungkinkan, terapkan algoritma pencarian lokal yang efisien untuk masalah yang sedang dipertimbangkan, karena hasil banyak aplikasi ACO pada masalah optimalisasi kombinatorial NP-load menunjukkan kinerja terbaik dicapai saat menggabungkan ACO dengan pengoptimalan lokal.
• Pilihlah algoritma keamanan dan dapatkan penyelesaian masalah, pertimbangkan aspek-aspek sebelumnya.
• Tune parameter dari algoritma ACO. Titik awal yang baik untuk penentuan parameter adalah dengan menggunakan parameterettings yang ternyata bagus saat menerapkan algoritma ACO pada masalah yang sama atau berbagai masalah lainnya.
Algoritma ACO iteratively melakukan loop yang berisi dua prosedur dasar, yaitu:
• Prosedur yang menentukan bagaimana semut membangun / memodifikasi solusi dari masalah yang harus dipecahkan;
• Prosedur untuk memperbarui pheromonetrails.
11.3.5 Aplikasi Ant Colony Optimization
Ada banyak implementasi meta ACO-heuristik yang diterapkan pada sejumlah masalah optimasi kombinatorial yang berbeda. Aplikasi meliputi:
• Traveling Salesman Problem, di mana seorang salesman harus menemukan rute terpendek yang dengannya ia dapat mengunjungi sejumlah kota, masing-masing kota persis satu kali.
• Masalah Penugasan Kuadrat, masalah penetapan n fasilitas ke n lokasi sehingga biaya penugasan diminimalkan.
• Masalah Penjadwalan Job-Shop, di mana satu set mesin dan satuan kerja tertentu harus diberikan pada interval waktu sedemikian rupa sehingga tidak ada dua pekerjaan yang diproses pada waktu yang sama pada mesin yang sama dan waktu penyelesaian maksimum dari semua operasi diminimalkan
• Masalah Routing Kendaraan, tujuannya adalah untuk menemukan rute kendaraan dengan biaya minimum sehingga:
(a) Setiap pelanggan dikunjungi tepat satu kali dengan satu kendaraan;
(b) Untuk setiap kendaraan, permintaan total tidak melebihi kapasitas kendaraan;
(c) Panjang tur total setiap kendaraan tidak melebihi batas yang ditentukan;
(d) Setiap kendaraan memulai dan mengakhiri turnya pada posisi yang sama.
• Urutan urutan super terpendek yang biasa, jika diberi satu set string di atas alfabet - string dengan panjang minimal yang merupakan urutan super dari setiap string dari rangkaian yang diberikan harus ditemukan (urutan super S dari string A dapat diperoleh dari A dengan memasukkan karakter nol atau lebih dalam A).
• Graph-Coloring Problem, yang merupakan masalah untuk menemukan pewarnaan grafik sehingga jumlah warna yang digunakan minimal.
• Masalah Pengurutan Berurutan, yang terdiri dari menemukan bobot minimum, yang tunduk pada batasan pendahuluan di antara nodus.
• Connection-Oriented Network Routing, dimana semua paket dari sesi yang sama mengikuti jalur yang sama yang dipilih oleh tahap penyiapan awal.
• Connectionless Network Routing dimana paket data dari sesi yang sama dapat mengikuti jalur yang berbeda (Internet-typenetworks).
Tabel11.2 Gambaran umum keseluruhan aplikasi adalah optimalisasi dan peneliti kutu yang dilakukan.
11.3.1 Inspirasi Biologis
Pada tahun 40an dan 50an abad ke-20, ahli entomologi Prancis Pierre-Paul Grass mengamati bahwa beberapa spesies rayap bereaksi terhadap apa yang dia sebut "rangsangan yang signifikan". Dia mengamati bahwa efek dari reaksi ini dapat bertindak sebagai rangsangan baru yang signifikan bagi serangga yang menghasilkannya dan serangga lainnya di koloni tersebut. Rumput menggunakan istilah stigmergy untuk menggambarkan jenis komunikasi tertentu di mana "pekerja dirangsang oleh kinerja yang telah mereka capai".
Dua karakteristik utama stigmergy yang membedakannya dari bentuk komunikasi lainnya adalah sebagai berikut.
• Stigmergy adalah bentuk komunikasi tidak langsung dan tidak simbolik yang dimediasi oleh lingkungan: serangga bertukar informasi dengan memodifikasi lingkungan mereka;
• Stigmergicinformationis lokal: hanya dapat diakses oleh serangga yang mengunjungi lokus tempat pelepasannya (atau lingkungan terdekatnya).
Stigmergy adalah bentuk komunikasi tidak langsung dan asinkron dimana serangga memanipulasi lingkungan untuk mengangkut informasi ke serangga lainnya, yang kemudian merespons perubahan tersebut.
Unsur-unsur utama dari sistem stigmergik biologis ditunjukkan pada Gambar 11.7:
• Serangga sebagai individu yang bertindak.
• Feromon merupakan pembawa informasi, yang digunakan untuk membuat medan disipasi.
• Lingkungan adalah mekanisme display dan distribusi informasi.
Perhatikan Gambar 11.8 berikut dimana semut bergerak pada garis lurus, yang menghubungkan sumber makanan ke sarang:
Sudah diketahui dengan pasti bahwa sarana utama yang digunakan oleh semut untuk membentuk dan memelihara garis adalah jalur feromon. Semut menyimpan sejumlah feromon sambil berjalan, dan setiap semut secara probabilistik lebih memilih mengikuti arah yang kaya pheromonerather daripada yang lebih buruk. Perilaku dasar semut asli ini dapat digunakan untuk menjelaskan bagaimana mereka dapat menemukan jalan terpendek, yang menghubungkan kembali garis putus-putus setelah munculnya rintangan tak terduga, telah mengganggu jalur awal (Gambar 11.9).
Sebenarnya, begitu rintangan telah muncul, semut-semut itu, yang berada tepat di depan rintangan, tidak dapat terus mengikuti jejak feromon dan oleh karena itu mereka harus memilih antara belok kanan atau kiri. Dalam situasi ini kita bisa mengharapkan setengah semut untuk memilih berbelok ke kanan dan separuh lainnya berbelok ke kiri. Situasi yang sama dapat ditemukan di sisi lain dari hambatan (Gambar 11.10).
Karena proses umpan balik positif ini (autocatalytic), segera semut semua semut akan memilih jalan yang lebih pendek (Gambar 11.11).
11.3.2 Kesamaan dan Perbedaan Antara Semut Nyata dan Semangat Artistik
Ada beberapa perbedaan dan persamaan antara semut asli dan buatan yang dapat dinyatakan sebagai berikut: 11.3.2.1 Kesamaan
• Koloni individu yang bekerja sama - Baik koloni semut asli dan algoritma semut terdiri dari populasi, atau koloni agen individu independen.
• Pheromonetrailandstigmergy-Likerealan, pecandu artifisial saling berbagi tentang lingkungan mereka yang dideritanya.
• Gerakan lokal dan pencarian jalur terpendek-Meskipun semut nyata berjalan melalui negara-negara yang berdekatan dan semut buatan melompat dari satu ke yang lain keadaan berdekatan dari masalah yang dipertimbangkan, baik jalan kaki maupun lompatan memiliki tujuan yang sama, yaitu menemukan saluran yang paling tepat antara titik pusat dan titik temu.
• Kebijakan transisi - Baik semut dan buatan asli akan membangun solusi dengan menerapkan prosedur pengambilan keputusan untuk bergerak melalui negara-negara yang berdekatan.
11.3.2.2 Perbedaan
Perbedaannya sebagai berikut:
• Semut-semut artistik tinggal di dunia yang terpisah. Semua gerakan mereka melompat dari satu keadaan diskrit ke sisi yang lain.
• Semut artistik memiliki ingatan, mereka dapat mengingat keadaan yang telah dikunjungi (daftar tabu dalam model ini).
• Metodologi deposit feromon secara signifikan berbeda antara semut asli dan buatan. Waktu dalam pheromonelaying adalah masalah tergantung dan sering tidak memiliki kesamaan dengan metodologi deposit feromon semut yang sesungguhnya.
• Untuk meningkatkan kinerja secara keseluruhan, algoritma AS dapat diperkaya dengan beberapa kemampuan tambahan yang tidak dapat ditemukan di koloni semut yang sebenarnya.
11.3.3 Karakteristik Ant Colony Optimization
Karakteristik optimasi koloni semut adalah sebagai berikut:
• Algoritma alami karena didasarkan pada perilaku semut nyata dalam membangun jalur dari koloni mereka menjadi sumber makanan dan kembali.
• Paralel dan terdistribusi karena menyangkut populasi agen yang bergerak secara bersamaan, mandiri dan tanpa atasan.
• Koperasi karena masing-masing agen memilih jalur berdasarkan informasi, jalur feromon yang diletakkan oleh agen lainnya, yang sebelumnya telah memilih samepath.
• Serbaguna bahwa hal itu dapat diterapkan pada versi yang sama dari masalah yang sama;
• Kuat bahwa hal itu dapat diterapkan dengan sedikit perubahan pada masalah optimasi kombinatorial lainnya seperti masalah penugasan kuadrat (QAP) dan masalah penjadwalan jobshop (JSP).
11.3.4 Algoritma Optimasi Koloni
Algoritma optimasi koloni semut yang berbeda telah diusulkan. Algoritma optimasi koloni semut asli dikenal sebagai Sistem Ant dan diusulkan pada awal tahun 90an. Sejak itu, sejumlah algoritma ACO lainnya diperkenalkan. Tabel 11.1 memberikan daftar varian Algoritma Optimasi Ant Colony yang berhasil.
Gambar 11.14 memberikan gambaran sempit tentang Algoritma Optimasi Ant Colony.
ACO adalah kelas algoritma, yang anggota pertamanya, yang disebut Ant System, awalnya diusulkan oleh Colorni, Dorigo dan Maniezzo.
11.3.4.1 Sistem Semut
Sistem yang diterapkan pada masalah Sales Man dibicarakan di sini. Ciri utamanya adalah bahwa, pada setiap iterasi, pheromonevalues diperbarui oleh semut m yang telah membangun solusi dalam iterasi itu sendiri.
11.3.4.2 Sistem Koloni Ant
Sumbangan ACS yang paling menarik adalah pengenalan pembaruan pheromone di samping update pheromone yang dilakukan pada akhir proses konstruksi (disebut feromon flut). Feromon lokal dilakukan oleh semua semut setelah setiap tahap konstruksi. Setiap semut menerapkannya hanya pada tepi terakhir yang dilalui:
11.3.4.3 Arus Dasar ACO
Arus operasional dasar dalam Ant Colony Optimization adalah sebagai berikut: Langkah 1: Mewakili ruang solusi dengan grafik konstruksi
Langkah 2: Inisialisasi parameter ACO
Langkah 3: Menghasilkan solusi acak dari setiap perjalanan acak semut
Langkah 4: Update pheromoneintensities
Langkah 5: Goto Langkah 3, dan ulangi sampai convergenceor kondisi berhenti puas.
Algoritma semut generik diberikan seperti ditunjukkan pada Gambar 11.15,
Algoritma Optimalisasi Optimalisasi Teorema Primer seperti ditunjukkan pada Gambar 11.16.
Prosedur langkah demi langkah untuk mengatasi masalah optimasi kombinatorial menggunakan ACO secara singkat adalah:
• Mewakili masalah dalam bentuk kumpulan komponen dan transisi atau dengan cara grafik tertimbang yang dilakukan oleh semut untuk membangun solusi.
• Menentukan dengan tepat arti jalur feromon, yaitu jenis keputusan yang mereka bias. Ini adalah langkah penting dalam implementasi algoritma ACO. Definisi jalur feromon yang baik bukanlah tugas sepele dan biasanya memerlukan pemahaman tentang masalah yang dipecahkan.
• Secara tepat menentukan preferensi heuristik terhadap setiap keputusan yang harus diambil seekor semut saat membangun solusi, yaitu, menentukan informasi heuristik yang terkait dengan setiap transisi komponen. Perhatikan bahwa informasi heuristik sangat penting untuk kinerja yang baik jika algoritma pencarian lokal tidak tersedia atau tidak dapat diterapkan.
• Jika memungkinkan, terapkan algoritma pencarian lokal yang efisien untuk masalah yang sedang dipertimbangkan, karena hasil banyak aplikasi ACO pada masalah optimalisasi kombinatorial NP-load menunjukkan kinerja terbaik dicapai saat menggabungkan ACO dengan pengoptimalan lokal.
• Pilihlah algoritma keamanan dan dapatkan penyelesaian masalah, pertimbangkan aspek-aspek sebelumnya.
• Tune parameter dari algoritma ACO. Titik awal yang baik untuk penentuan parameter adalah dengan menggunakan parameterettings yang ternyata bagus saat menerapkan algoritma ACO pada masalah yang sama atau berbagai masalah lainnya.
Algoritma ACO iteratively melakukan loop yang berisi dua prosedur dasar, yaitu:
• Prosedur yang menentukan bagaimana semut membangun / memodifikasi solusi dari masalah yang harus dipecahkan;
• Prosedur untuk memperbarui pheromonetrails.
11.3.5 Aplikasi Ant Colony Optimization
Ada banyak implementasi meta ACO-heuristik yang diterapkan pada sejumlah masalah optimasi kombinatorial yang berbeda. Aplikasi meliputi:
• Traveling Salesman Problem, di mana seorang salesman harus menemukan rute terpendek yang dengannya ia dapat mengunjungi sejumlah kota, masing-masing kota persis satu kali.
• Masalah Penugasan Kuadrat, masalah penetapan n fasilitas ke n lokasi sehingga biaya penugasan diminimalkan.
• Masalah Penjadwalan Job-Shop, di mana satu set mesin dan satuan kerja tertentu harus diberikan pada interval waktu sedemikian rupa sehingga tidak ada dua pekerjaan yang diproses pada waktu yang sama pada mesin yang sama dan waktu penyelesaian maksimum dari semua operasi diminimalkan
• Masalah Routing Kendaraan, tujuannya adalah untuk menemukan rute kendaraan dengan biaya minimum sehingga:
(a) Setiap pelanggan dikunjungi tepat satu kali dengan satu kendaraan;
(b) Untuk setiap kendaraan, permintaan total tidak melebihi kapasitas kendaraan;
(c) Panjang tur total setiap kendaraan tidak melebihi batas yang ditentukan;
(d) Setiap kendaraan memulai dan mengakhiri turnya pada posisi yang sama.
• Urutan urutan super terpendek yang biasa, jika diberi satu set string di atas alfabet - string dengan panjang minimal yang merupakan urutan super dari setiap string dari rangkaian yang diberikan harus ditemukan (urutan super S dari string A dapat diperoleh dari A dengan memasukkan karakter nol atau lebih dalam A).
• Graph-Coloring Problem, yang merupakan masalah untuk menemukan pewarnaan grafik sehingga jumlah warna yang digunakan minimal.
• Masalah Pengurutan Berurutan, yang terdiri dari menemukan bobot minimum, yang tunduk pada batasan pendahuluan di antara nodus.
• Connection-Oriented Network Routing, dimana semua paket dari sesi yang sama mengikuti jalur yang sama yang dipilih oleh tahap penyiapan awal.
• Connectionless Network Routing dimana paket data dari sesi yang sama dapat mengikuti jalur yang berbeda (Internet-typenetworks).
Tabel11.2 Gambaran umum keseluruhan aplikasi adalah optimalisasi dan peneliti kutu yang dilakukan.
0 komentar:
Posting Komentar