Swarm Optimization [PDF]

Citation preview

Swarm Intelligence



The Family Tree



2020/2/8



2



optimization • optimization didefinisikan sebagai proses pemilihan sebuah solusi dari sejumlah alternative solusi dengan memenuhi sejumlah batasan (contstraints). • Misalkan pada pencarian rute untuk mengunjungi sejumlah kota. • Pada kasus ini tentu saja terdapat banyak alternative pilihan rute (solusi). • Solusi yang dipilih disesuaikan dengan tujuan (objective) dari permasalahan ini, misalkan memilih rute terpendek atau rute dengan waktu tempuh tercepat. • Batasan yang ada misalkan setiap kota harus dikunjungi tepat satu kali.



Stochastic optimization • Stochastic optimization menggunakan bilangan acak (random) dalam pencarian solusi. • Sebagai konsekuensinya, sebuah algoritma dalam kelas ini setiap dijalankan akan menghasilkan solusi akhir yang berbeda, meskipun diterapkan dalam permasalahan yang sama • Sebuah algoritma meta-heuristic bertindak sebagai ‘manajer’dari beberapa algoritma heuristic untuk secara terorganisir mencari solusi dari sebuah permasalahan. • Misalkan metode Variable Neighborhood Search (VNS) yang me-manage sebuah teknik local search (LS). • VNS secara sistematis meng-iterasi LS untuk mencari solusi dari titik awal yang berbeda serta mencakup area pencarian yang lebih luas .



Stochastic optimization • Contoh lainnya adalah algoritma genetika yang memanage beberapa genetic operator seperti crossover, mutation, dan selection • Evolutionary computing merujuk kepada berbagai teknik penyelesaian masalah yang berbasis proses evolusi biologi seperti seleksi alam (natural selection) dan penurunan sifat genetis (genetic inheritance).



Algoritma Evolusi • Algoritma Evolusi (evolutionary algorithms, EAs) merupakan teknik optimasi yang meniru proses evolusi biologi. • Menurut teori evolusi terdapat sejumlah individu dalam populasi. • Dari generasi ke generasi, individu-individu ini berperan sebagai induk (parent) yang melakukan reproduksi menghasilkan keturunan (offspring). • Individu-individu ini (beserta offspring) berevolusi dan individu-individu yang lebih baik (mampu beradaptasi dengan lingkungannya) mempunyai peluang lebih besar untuk melewati seleksi alam (natural selection) dan bertahan hidup. • Individu yang lebih baik juga cenderung (tidak selalu tapi mempunyai kemungkinan lebih besar) menghasilkan keturunan yang lebih baik sehingga dari generasi ke generasi akan terbentuk populasi yang lebih baik.



Algoritma Evolusi • Individu-individu dalam populasi di EAs merepresentasikan solusi dari masalah yang akan diselesaikan. • Sebuah fungsi fitness digunakan untuk mengukur seberapa baik suatu individu. • Individu terbaik di akhir generasi bisa didekodekan sebagai solusi terbaik yang bisa diperoleh. • EAs bisa dikelompokkan dalam algoritma ‘generate and test’ yang berbasis populasi (population based). • EA juga bersifat stochastic, setiap kali dijalankan untuk masalah yang sama ada kemungkinan menghasilkan solusi yang berbeda (Smith & Eiben 2003).



Algoritma Evolusi • Algoritma genetika (Genetic Algorithms, GAs), merupakan tipe EAs yang paling popular dan banyak diterapkan pada masalah-masalah kompleks. • Evolution Strategies (ES), representasi solusi biasanya menggunakan vektor bilangan pecahan. Mutasi merupakan operator reproduksi utama. Mekanisme self-adaptation digunakan untuk mengontrol perubahan nilai parameter pencarian. • Genetic Programming (GP), digunakan untuk mengoptimasi rangkaian program komputer yang direpresentasikan dalam bentuk struktur data pohon (tree). • Evolutionary Programming (EP), mempunyai tujuan seperti GP tapi prinsip kerjanya seperti ES. Finite State Machines (FSM) digunakan untuk merepresentasikan program komputer



Swarm Intelligence • Swarm Intelligence adalah salah satu teknik kecerdasan buatan yang berlandaskan kepada perilaku kolektif (collective behaviour) pada sistem yang terdesentralisasi dan dapat mengatur dirinya sendiri (self-organizing). • Sistem yang memanfaatkan Swarm Intelligence biasanya merupakan sebuah populasi yang terdiri atas anggota berupa agen-agen yang sederhana, yang berinteraksi secara lokal dengan sesama anggota, dan juga berinteraksi dengan lingkungan. • Walaupun pada umumnnya tidak ada struktur kendali secara terpusat (centralized) yang mendikte bagaimana masingmasing individu bertindak, namun interaksi secara lokal (di antara anggota) seringkali menuju pada pembentukan (emergence) perilaku global



Particle Swarm Optimization (PSO)



pendahuluan • Particle swarm optimization, disingkat sebagai PSO, didasarkan pada perilaku sebuah kawanan serangga, seperti semut, rayap, lebah atau burung. • Algoritma PSO meniru perilaku sosial organisme ini. • Perilaku sosial terdiri dari tindakan individu dan pengaruh dari individu-individu lain dalam suatu kelompok. • Kata partikel menunjukkan, misalnya, seekor burung dalam kawanan burung. • Setiap individu atau partikel berperilaku secara terdistribusi dengan cara menggunakan kecerdasannya (intelligence) sendiri dan juga dipengaruhi perilaku kelompok kolektifnya. • Dengan demikian, jika satu partikel atau seekor burung menemukan jalan yang tepat atau pendek menuju ke sumber makanan, sisa kelompok yang lain juga akan dapat segera mengikuti jalan tersebut meskipun lokasi mereka jauh di kelompok tersebut



pendahuluan Meskipun setiap burung mempunyai keterbatasan dalam hal kecerdasan, biasanya ia akan mengikuti kebiasaan (rule) seperti berikut : • Seekor burung tidak berada terlalu dekat dengan burung yang lain • Burung tersebut akan mengarahkan terbangnya ke arah rata-rata keseluruhan burung • Akan memposisikan diri dengan rata-rata posisi burung yang lain dengan menjaga sehingga jarak antar burung dalam kawanan itu tidak terlalu jauh



pendahuluan Perilaku kawanan burung akan didasarkan pada kombinasi dari 3 faktor simpel berikut: • Kohesi - terbang bersama • Separasi - jangan terlalu dekat • Penyesuaian (alignment) - mengikuti arah bersama



pendahuluan Jadi PSO dikembangkan dengan berdasarkan pada model berikut: • Ketika seekor burung mendekati target atau makanan (atau bisa mnimum atau maximum suatu fungsi tujuan) secara cepat mengirim informasi kepada burung-burung yang lain dalam kawanan tertentu • Burung yang lain akan mengikuti arah menuju ke makanan tetapi tidak secara langsung • Ada komponen yang tergantung pada pikiran setiap burung, yaitu memorinya tentang apa yang sudah dilewati pada waktu sebelumnya.



pendahuluan • PSO memiliki banyak persamaan dengan teknik Evolutionary Computation seperti Genetics Algorithm (GA). • Sistem ini diinisialisasi dengan sekumpulan solusi random yang kemudian mencari optima dengan cara memperbaharui generasi berikutnya. • PSO tidak memiliki operator evolusi seperti crossover dan mutasi, tetapi PSO memiliki update kecepatan dan memory yang penting bagi sebuah algoritma. • Jika dibandingkan dengan GA, keuntungan PSO adalah lebih mudah diimplementasikan dan hanya memiliki sedikit parameter yang perlu untuk disesuaikan.



Topologi Jaringan Topologi star • Pada topologi ini tiap partikel dapat saling berkomunikasi dengan individu lainnya dan membentuk sebuah jaringan sosial yang terkoneksi secara penuh • Partikel yang memiliki nilai fitness terbaik dari seluruh partikel yang ada disebut global best (gbest). • Karena terkoneksi secara penuh, informasi nilai gbest akan dirambatkan lebih cepat ke semua indivudu partikel.



Topologi Jaringan Topologi ring • Masing-masing partikel hanya dapat berkomunikasi dengan partikel yang berada disebelahnya • Tiap partikel akan berusaha bergerak mengikuti individu terbaik tetangganya yang disebut dengan local best (lbest).



Topologi wheel • Pada topologi ini hanya sebuah partikel yang terkoneksi, sedangkan partikel yang lain akan terisolasi



Topologi Jaringan



(a) topologi star



(b) topologi ring



(c) topologi wheel



Algoritma Particle Swarm Optimization • Algoritma PSO dimulai dengan membangkitkan sejumlah nilai awal acak. • Jika xi(t) menyatakan posisi partikel i dalam ruang pencarian pada timestep; kecuali dinyatakan lain, t menunjukkan langkah-langkah waktu diskrit. • Posisi partikel diubah dengan menambahkan kecepatan, vi(t), untuk posisi saat ini 𝑥𝑖 𝑡 = 𝑥𝑖 𝑡 − 1 + 𝑣𝑖 (𝑡)



Algoritma Particle Swarm Optimization • Untuk global best PSO, atau gbest PSO, lingkungan untuk setiap partikel adalah keseluruhan kawanan (swarm). • Jaringan sosial yang digunakan oleh gbest PSO mencerminkan topologi star. • Untuk topologi lingkungan star, komponen sosial dari update kecepatan partikel mencerminkan informasi yang diperoleh dari semua partikel dalam kawanan tersebut. • Dalam hal ini, informasi sosial adalah posisi terbaik yang ditemukan oleh kawanan, disebut sebagai. • Untuk gbest PSO, kecepatan partikel i dihitung sebagai: 𝑣𝑖𝑗 𝑡 + 1 = 𝑣𝑖𝑗 𝑡 + 𝑐1 𝑟1𝑗 𝑡 𝑦𝑖𝑗 𝑡 − 𝑥𝑖𝑗 𝑡 +𝑐2 𝑟2𝑗 𝑡 𝑦𝑗 𝑡 − 𝑥𝑖𝑗 𝑡



Algoritma Particle Swarm Optimization • dengan vij(t) adalah kecepatan partikel i dalam dimensi j = 1,. . . , nx pada timestep t, • xij(t) adalah posisi partikel i dalam dimensi j pada timestep, • c1 dan c2 adalah konstanta percepatan positif yang digunakan untuk skala kontribusi dari masing-masing komponen kognitif dan sosial, dan • r1j(t), r2j(t) ~ U(0, 1) adalah nilai acak dalam rentang [0, 1], sampel dari distribusi seragam. • Nilai-nilai acak memperkenalkan elemen stokastik untuk algoritma.



Algoritma Particle Swarm Optimization • Posisi terbaik pribadi, yi, terkait dengan partikel i adalah posisi terbaik partikel yang ada sejak langkah pertamanya. • Mempertimbangkan masalah minimisasi, posisi terbaik pribadi pada langkah waktu berikutnya, t + 1, dihitung sebagai: 𝑦𝑖 𝑡 + 1 =



𝑦𝑖 𝑡



𝑗𝑖𝑘𝑎 𝑓 𝑥𝑖 𝑡 + 1



𝑥𝑖 𝑡 + 1 𝑗𝑖𝑘𝑎 𝑓 𝑥𝑖 𝑡 + 1



≥ 𝑓(𝑦𝑖 𝑡 ) < 𝑓(𝑦𝑖 𝑡 )



• dengan f: R → Rnx adalah fungsi fitness. • Seperti EA, fungsi fitness mengukur seberapa dekat solusi yang sesuai adalah dengan optimal, yaitu fungsi fitness mengkuantifikasi kinerja, atau kualitas, dari partikel (atau solusi).



Algoritma Particle Swarm Optimization • Posisi terbaik secara global, didefinisikan sebagai: 𝑦 𝑡 ∈ 𝑦0 𝑡 , … , 𝑦𝑛 𝑠 𝑡



𝑓 𝑦 𝑡



𝑦(𝑡)



, pada timestep,



= min⁡ {𝑓 𝑦0 𝑡 , … , 𝑓(𝑦𝑛 𝑠 (𝑡)}



• dengan ns adalah jumlah total partikel dalam kawanan tersebut. • Penting untuk dicatat bahwa definisi dalam persamaan menyatakan bahwa adalah posisi terbaik yang ditemukan oleh salah satu partikel, biasanya dihitung sebagai posisi terbaik dari personal terbaik. • Posisi global best juga dapat dipilih dari partikel kawanan saat ini, dalam hal ini:



𝑦 𝑡 = min⁡𝑓 𝑥0 𝑡



, … , 𝑓 𝑥𝑛 𝑠 𝑡



Ant Colony Optimization (ACO)



Pendahuluan • Ant Colony Optimization (ACO) diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut. • Semut mampu mengindera lingkungannya yang kompleks untuk mencari makanan dan kemudian kembali ke sarangnya dengan meninggalkan zat Pheromone pada rute-rute yang mereka lalui. • Pheromone adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama jenis, individu lain, kelompok, dan untuk membantu proses reproduksi. • Pheromone menyebar ke luar tubuh dan hanya dapat mempengaruhi dan dikenali oleh individu lain yang sejenis (satu spesies).



Pendahuluan • Proses peninggalan Pheromone ini dikenal sebagai stigmery, yaitu sebuah proses memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi dengan koloninya. • Seiring waktu, jejak Pheromone akan menguap dan akan mengurangi kekuatan daya tariknya. • Lebih cepat setiap semut pulang pergi melalui rute tersebut, maka Pheromone yang menguap lebih sedikit. • Begitu pula sebaliknya jika semut lebih lama pulang pergi melalui rute tersebut, maka Pheromone akan menguap lebih banyak.



Pendahuluan E



E



E



D



D



H



A



C



2



H



C



B



B



A



A



2 4



Ant System (AS) • Algoritma Ant System (AS) adalah algoritma Ant Colony Optimization (ACO) pertama yang dirumuskan dan diuji untuk menyelesaikan suatu masalah • Algoritma ini tersusun atas sejumlah m semut yang bekerja sama dan berkomunikasi secara tidak langsung melalui komunikasi Pheromone. • Secara informal, Ant System bekerja sebagai berikut : Setiap semut memulai tournya melalui sebuah titik yang dipilih secara acak (setiap semut memiliki titik awal yang berbeda). • Secara berulang kali, satu persatu titik yang ada dikunjungi oleh semut dengan tujuan untuk menghasilkan sebuah tour.



Ant System (AS) • Pemilihan titik-titik yang akan dilaluinya didasarkan pada suatu fungsi probabilitas, dinamai aturan transisi status (state transition rule), dengan mempertimbangkan visibility (invers dari jarak) titik tersebut dan jumlah Pheromone yang terdapat pada ruas yang menghubungkan titik tersebut. • Semut lebih suka untuk bergerak menuju ke titik-titik yang dihubungkan dengan ruas yang pendek dan memiliki tingkat Pheromone yang tinggi. • Setiap semut memiliki sebuah memori, dinamai tabulist, yang berisi semua titik yang telah dikunjunginya pada setiap tour.



Ant System (AS) • Tabulist ini mencegah semut untuk mengunjungi titiktitik yang sebelumnya telah dikunjungi selama tour tersebut berlangsung, yang membuat solusinya mendekati optimal. • Setelah semua semut menyelesaikan tour mereka dan tabulist mereka menjadi penuh, sebuah aturan pembaruan Pheromone global (global pheromone updating rule) diterapkan pada setiap semut. • Penguapan Pheromone pada semua ruas dilakukan, kemudian setiap semut menghitung panjang tour yang telah mereka lakukan lalu meninggalkan sejumlah Pheromone pada edge-edge yang merupakan bagian dari tour mereka yang sebanding dengan kualitas dari solusi yang mereka hasilkan.



Ant System (AS) • Semakin pendek sebuah tour yang dihasilkan oleh setiap semut, jumlah Pheromone yang ditinggalkan pada edgeedge yang dilaluinya pun semakin besar. • Dengan kata lain, edge-edge yang merupakan bagian dari tour-tour terpendek adalah edge-edge yang menerima jumlah Pheromone yang lebih besar. • Hal ini menyebabkan edge-edge yang diberi pheromone lebih banyak akan lebih diminati pada tour-tour selanjutnya, dan sebaliknya edge-edge yang tidak diberi Pheromone menjadi kurang diminati. • rute terpendek yang ditemukan oleh semut disimpan dan semua tabulist yang ada dikosongkan kembali.



Ant System (AS) • Peranan utama dari penguapan pheromone adalah untuk mencegah stagnasi, yaitu situasi dimana semua semut berakhir dengan melakukan tour yang sama. • Proses di atas kemudian diulangi sampai tour-tour yang dilakukan mencapai jumlah maksimum atau sistem ini menghasilkan perilaku stagnasi dimana sistem ini berhenti untuk mencari solusi alternatif.



Aturan Transisi Status • Aturan transisi status yang digunakan oleh Ant System (AS) dinamai random proportional rule • P merupakan probabilitas dari semut k pada titik r yang memilih untuk menuju ke titik s.   rs    k Prs   k rs jN  r 0



jika  N rk jika  N rk



• Dimana α adalah sebuah parameter yang mengontrol bobot (weight) relatif dari Pheromone. • Dan Nrk adalah himpunan titik yang akan dikunjungi oleh semut k yang sedang berada pada titik r (untuk membuat solusinya mendekati optimal).



MAX – MIN Ant System (MMAS) • Pertama penambahan Pheromone bisa dilakukan pada edge–edge yang merupakan bagian dari tour terbaik yang ditemukan sejak awal algoritma (best so-far-tour) atau pada tour terbaik yang ditemukan pada iterasi tersebut (iteration best-tour). • Bisa juga penambahan Pheromone pada keduanya, best so-far-tour dan iteration best-tour sekaligus. • Tetapi, strategi ini memungkinkan terjadinya stagnasi yang menyebabkan semua semut melalui jalur yang sama, karena pemberian Pheromone yang berlebihan pada edge, meskipun bagian dari tour yang terbaik.



MAX – MIN Ant System (MMAS) • Kedua, untuk mengatasi masalah pada perubahan pertama, maka Max-Min Ant System (MMAS) memberikan batasan dalam pemberian nilai Pheromone dengan interval [τmin, τmax]. • Ketiga, menginisialisasi Pheromone dengan batas atas nilai Pheromone, yang mana bersama dengan tingkat evaporasi Pheromone yang kecil, meningkatkan eksplorasi tour sejak dimulainya pencarian. • Keempat, Pheromone diinisialisasi kembali pada saat terjadi stagnasi atau ketika tidak ditemukan tour yang sesuai dengan iterasi yang diinginkan.



Ant Colony System (ACS) • Algoritma Ant Colony System (ACS) merupakan pengembangan dari Ant System (AS) selanjutnya, setelah beberapa algoritma diatas. • Algoritma ini tersusun atas sejumlah m semut yang bekerjasama dan berkomunikasi secara tidak langsung melalui komunikasi Pheromone. • Secara informal, Ant Colony System (ACS) bekerja sebagai berikut: pertama kali sejumlah m semut ditempatkan pada sejumlah n titik berdasarkan beberapa aturan inisialisasi (misalnya secara acak). • Setiap semut membuat sebuah tour (yaitu, sebuah solusi yang mungkin) dengan menerapkan sebuah aturan transisi status secara berulang kali.



Ant Colony System (ACS) • Selagi membangun tournya, setiap semut juga memodifikasi jumlah Pheromone pada edge-edge yang dikunjunginya dengan menerapkan aturan pembaruan Pheromone lokal. • Setelah semua semut mengakhiri tour mereka, jumlah Pheromone yang ada pada edge-edge dimodifikasi kembali (dengan menerapkan aturan pembaruan Pheromone global). • Seperti yang terjadi pada Ant System (AS), dalam membuat tour, semut ‘dipandu’oleh informasi heuristic (mereka lebih memilih edge-edge yang pendek) dan oleh informasi Pheromone.



Ant Colony System (ACS) • Sebuah edge dengan jumlah Pheromone yang tinggi merupakan pilihan yang diinginkan. • Kedua aturan pembaruan Pheromone itu dirancang agar semut cenderung untuk memberi lebih banyak Pheromone pada edge-edge yang harus mereka lewati.



Global Pheromone Update • Setelah semua semut menyelesaikan sebuah tour, tingkat Pheromone di-update dengan mengaplikasikan global updating rule menurut persamaan berikut: 𝜏𝑟𝑠 = 1 − 𝜌 𝜏𝑟𝑠 • Dengan f c best jika (r,s) lintasanterbaik keseluruhan   f worst bs Δτ rs    0 jika tidak



• Dimana fbest adalah nilai terbaik (terkecil) dari fungsi tujuan dan fworst nilai terjelek (terbesar) dari fungsi tujuan. • Sedangkan c adalah konstanta untuk updating global pheromone dan nol jika tidak.



Global Pheromone Update • Persamaan update jejak Pheromone secara offline ini, dilakukan pada akhir sebuah iterasi algoritma, saat semua semut telah menyelesaikan sebuah tour. • Persamaan diaplikasikan ke edge yang digunakan semut menemukan lintasan keseluruhan yang terbaik sejak awal percobaan. • Tujuan pemberian nilai ini adalah memberi sejumlah jejak Pheromone pada lintasan terpendek, dimana tour terbaik (lintasan dengan panjang terpendek) mendapat penguatan. • Bersama dengan pseudo random proportional rule dimaksudkan untuk membuat pencarian lebih terarah.



Global Pheromone Update beberapa parameter-parameter untuk menentukan jalur terpendek : • Parameter dan nilai pheromone awal. • Inisialisasi harga parameter–parameter algoritma: 1) Intensitas jejak semut antar titik dan perubahannya (τrs). Nilai (τrs) akan selalu diperbaharui pada setiap iterasi algoritma, mulai dari iterasi pertama sampai iterasi maksimum yang ditentukan atau telah mencapai hasil yang optimal. 2) Titik berangkat (awal) dan titik tujuan, titik awal dan titik tujuan adalah sama. 3) Tetapan iterasi semut (Q).



Global Pheromone Update 4) Tetapan pengendali intensitas jejak semut (α ). 5) Banyaknya semut (m). 6) Tetapan penguapan Pheromone (ρ ). Nilainya 0 < ρ ≤ 1, hal ini untuk mencegah jumlah Pheromone yang tak terhingga. 7) Jumlah iterasi maksimum (NC=max), bersifat tetap selama algoritma berjalan, sedangkan τrs akan selalu diperbaharui harganya pada setiap iterasi algoritma mulai dari ietrasi pertama (NC=1) sampai tercapai jumlah iterasi maksimum (NC = max) atau sampai terjadinya konvergen.



Global Pheromone Update • Inisialisasi titik pertama setiap semut. • Setelah inisialisasi (τrs) dilakukan, kemudian m semut ditempatkan pada titik pertama tertentu secara acak pada sejumlah n titik. • Hasil inisialisasi titik pertama setiap semut, diisikan sebagai elemen pertama tabulist. • Hasil dari langkah ini adalah terisinya elemen pertama tabulist setiap semut dengan indeks titik tertentu, yang berarti bahwa setiap tabu (i) k bisa berisi indeks titik antara 1 sampai n.



Cat Swarm Optimization (CSO)



Pendahuluan • Cat Swarm Optimization adalah algoritma yang diusulkan oleh Shu-Chuan Chu dan Pei-Wei Tsai pada tahun 2006, yang didapat melalui pengamatan terhadap perilaku sekumpulan kucing. • Dalam ACO semut digunakan sebagai agent, dan jalur yang dilalui oleh semut-semut tersebut adalah set solusinya. • Dalam PSO, posisi-posisi dari kawanan burung digunakan untuk menggambarkan set solusinya. • Dalam CSO, sekumpulan kucing dan model perilakunya digunakan untuk menyelesaikan permasalahan optimasi.



Set Solusi dalam Model • Tahap pertama dalam CSO adalah menentukan berapa banyak kucing akan digunakan dalam iterasi, kemudian menggunakan kucing dalam CSO untuk menyelesaikan permasalahan. • Setiap kucing masing-masing memiliki posisi yang tersusun dalam dimensi D, kecepatan untuk setiap dimensi, nilai kecocokan yang menunjukkan penyesuaian kucing dengan fungsi kecocokan, dan bendera untuk mengetahui apakah kucing berada dalam seeking mode atau tracing mode. • Solusi akhir adalah posisi terbaik dari salah satu kucing. • CSO akan menyimpan solusi terbaik hingga akhir iterasi.



Seeking Mode • Sub model ini digunakan untuk memodelkan situasi kucing ketika dalam keadaan beristirahat, melihat sekeliling dan mencari posisi berikutnya untuk bergerak. • Dalam seeking mode, didefinisikan empat faktor penting: seeking memory pool (SMP), seeking range of the selected dimension (SRD) atau mencari rentang dimensi terpilih, counts of dimension to change (CDC) atau menghitung dimensi yang akan berubah, dan selfposition considering (SPC) atau mempertimbangkan posisi.



Seeking Mode • SMP digunakan untuk mendefinisikan ukuran memori pencarian untuk masing-masing kucing, yang mengindikasikan titik-titik yang telah dicoba oleh kucing. • Kucing tersebut kemudian akan memilih titik dari kelompok memori berdasarkan aturan yang akan dijelaskan kemudian. • SRD menyatakan rentang perpindahan dalam dimensi terpilih. • Dalam seeking mode, jika suatu dimensi diputuskan berpindah, selisih antara nilai baru dengan yang lama tidak boleh melebihi suatu rentang, yaitu rentang yang didefinisikan oleh SRD.



Seeking Mode • CDC memperlihatkan berapa besar dimensi yang akan berubah. • Keseluruhan faktor inilah yang memegang peran penting dalam seeking mode. • SPC merupakan variabel Boolean (bernilai benar atau salah), untuk memutuskan apakah suatu titik, yang pernah menjadi posisi kucing, akan menjadi kandidat posisi untuk bergerak. • Bagaimanapun nilai SPC, entah benar ataupun salah, nilai SMP tidak akan terpengaruh. • Langkah-langkah seeking mode dapat dideskripsikan dalam 5 tahap.



Seeking Mode • Langkah 1: Bangkitkan j tiruan dari posisi saat ini kucing k, di mana j = SMP. Jika nilai SPC benar, maka j = (SMP–1), kemudian pertahankan posisi saat ini sebagai salah satu kandidat. • Langkah 2: Untuk setiap tiruan, disesuaikan dengan CDC, tambahkan atau kurangkan SRD persen dari nilai saat ini secara acak dan gantikan nilai yang sebelumnya. • Langkah 3: Hitung nilai kecocokan (FS) untuk semua titik kandidat. • Langkah 4: Jika semua FS tidak benar-benar sama, hitung probabilitas terpilih masingmasing titik kandidat dengan menggunakan (pers.2), sebaliknya atur probabilitas terpilih untuk semua titik sama dengan 1.



Seeking Mode • Langkah 5: secara acak pilih titik untuk bergerak dari titik-titik kandidat, dan pindahkan posisi kucing k. 𝑝𝑖 =



𝐹𝑆𝑖 − 𝐹𝑆𝑏 , 𝑑𝑖𝑚𝑎𝑛𝑎 0 < 𝑖 < 𝑗 𝐹𝑆𝑚𝑎𝑥 − 𝐹𝑆𝑚𝑖𝑛



• Jika tujuan fungsi kecocokan adalah untuk menemukan solusi minimal, FSb= FSmax, sebaliknya FSb= FSmin.



Tracing Mode • Tracing mode adalah sub model yang menggambarkan keadaan ketika kucing sedang mengikuti jejak targetnya. • Sekali kucing memasuki tracing mode, kucing tersebut akan bergerak sesuai dengan kecepatannya untuk tiap dimensi. • Tahapan tracing mode dapat dijabarkan dalam 3 langkah sebagai berikut: – Langkah 1: Perbarui nilai kecepatan untuk setiap dimensi (vk,d) berdasarkan (pers.3). 𝑣𝑘,𝑑 = 𝑣𝑘,𝑑 + 𝑟1 . 𝑐1 . 𝑥𝑏𝑒𝑠𝑡,𝑑 − 𝑥𝑘,𝑑



dimana xbest,d = 1,2,...,M, xbest,d adalah posisi kucing yang memiliki nilai kecocokan terbesar; xk,d adalah posisi kucing k. c1 adalah konstanta dan r1 adalah nilai acak dalam rentang [0,1].



Tracing Mode – Langkah 2: Periksa apakah kecepatan berada dalam rentang kecepatan maksimum. Jika kecepatan yang beru melebihi rentang, tetapkan nilai sama dengan batas. – Langkah 3: Perbarui posisi kucing k berdasarkan 𝑥𝑘,𝑑 = 𝑥𝑘,𝑑 +𝑣𝑘,𝑑



Algoritma CSO • Untuk mengkombinasikan kedua mode dalam satu algoritma, perlu didefinisikan rasio campuran/mixture ratio (MR) untuk menggabungkan seeking mode dan tracing mode. • Dengan mengamati perilaku kucing, dapat diketahui bahwa kucing menghabiskan sebagian besar waktunya untuk beristirahat. • Selama beristirahat, kucing mengubah posisinya perlahan dan berhati-hati, terkadang bahkan tetap pada tempatnya. • Untuk menerapkan perilaku ini ke dalam CSO, digunakan seeking mode.



Algoritma CSO • Perilaku mengejar target diaplikasikan dalam tracing mode. • Karena itu maka MR harus bernilai kecil untuk memastikan bahwa kucing menghabiskan sebagian besar waktu dalam seeking mode, seperti di kehidupan nyatanya. • Proses CSO dapat digambarkan dalam 6 langkah sebagai berikut: – Langkah 1: Bangkitkan N kucing dalam proses. – Langkah 2: Sebarkan kucing secara acak dalam ruang solusi berdimensi D dan secara acak pula pilih nilai dalam rentang kecepatan maksimum untuk menjadi kecepatan kucing. Kemudian pilih sejumlah kucing secara sembarang dan masukkan dalam tracing mode sesuai MR, sisanya dimasukkan dalam seeking mode.



Algoritma CSO – Langkah 3: Hitung nilai kecocokan masing-masing kucing dengan memasukkan nilai posisi kucing ke dalam fungsi kecocokan, yang menunjukkan kriteria tujuan, dan simpan kucing terbaik dalam memori. Perlu diingat bahwa yang perlu disimpan adalah posisi kucing terbaik (xbest) karena kucing terbaik sejauh ini mewakili solusi terbaik. – Langkah 4: Pindahkan kucing sesuai benderanya, jika kucing k berada dalam seeking mode, perlakukan sesuai proses seeking mode, sebaliknya perlakukan sesuai tracing mode.



Algoritma CSO – Langkah 5: Pilih lagi sejumlah kucing dan masukkan dalam tracing modesesuai MR, sisanya masukkan ke dalam seeking mode. – Langkah 6: Perhatikan terminating condition-nya. Jika telah memuaskan, hentikan program. Sebaliknya ulangi langkah 3 hingga 5.



Artificial Bee Colony (ABC)



pendahuluan • ABC adalah sebuah metode optimisasi yang terinspirasi oleh perilaku mencari makan lebah madu yang diperkenalkan oleh Karaboga pada tahun 2005. • Algoritma ini didasarkan pada perilaku nyata lebah untuk menemukan dan berbagi informasi sumber-sumber makanan kepada lebah lain di sarangnya. • Dalam model ABC algorithm, Artificial Bee Colony terdiri dari tiga kelompok lebah, yaitu: lebah pekerja, lebah onlooker dan lebah scout. – Lebah scout adalah lebah yang melakukan pencarian acak. – Lebah pekerja adalah lebah yang pergi ke sumber makanan yang pernah dikunjungi dirinya sebelunya.



pendahuluan – Lebah onlooker adalah lebah yang menunggu di dance area untuk membuat keputusan dalam memilih sumber makanan. • Lebah onlooker dan lebah scout adalah lebah unemployed. Lebah pekerja berkaitan dengan sumber makanan tertentu, lebah onlooker menyaksikan tarian lebah pekerja dalam sarang untuk memilih sumber makanan, dan lebah scout mencari sumber makanan secara acak • Tujuan dari lebah dalam model ABC adalah untuk menemukan solusi yang terbaik, posisi sumber makanan merupakan solusi untuk masalah optimasi dan jumlah nektar dari sumber makanan sesuai dengan kualitas (fitness) dari solusi terkait



Cara Kerja Artificinal Bee Colony (ABC)



• lebah scout bertugas untuk menemukan posisi dari semua sumber makanan. • Setelah itu, tugas dilanjutkan oleh lebah pekerja.



Cara Kerja Artificinal Bee Colony (ABC) • Seekor lebah pekerja buatan secara probalistik memperoleh beberapa modifikasi pada posisi dalam memori untuk menargetkan sumber makanan baru dan menemukan jumlah nektar atau nilai fitness dari sumber baru. • Kemudian, lebah onlooker mengevaluasi informasi yang diambil dari semua lebah pekerja dan kemudian memilih sumber makanan akhir dengan probabilitas tertinggi terkait dengan jumlah nektar nya. • Jika nilai fitness yang baru ini lebih tinggi dari yang sebelumnya, lebah melupakan yang lama dan menghafal posisi baru. • Hal ini disebut sebagai seleksi greedy.



Cara Kerja Artificinal Bee Colony (ABC) • Lebah pekerja yang sumber makanan telah habis akan menjadi lebah scout untuk mencari sumber makanan baru. • Dalam ABC, solusi merupakan sumber makanan dan kuantitas nektar dari sumber makanan bersesuaian dengan fitness dari solusi terkait. • Jumlah lebah pekerja dan lebah onlooker sama, dan jumlah ini sama dengan jumlah sumber makanan. • Lebah pekerja yang solusinya tidak dapat ditingkatkan melalui jumlah batas yang telah ditetapkan sebelumnya, yang ditentukan oleh pengguna dari algoritma ABC dan disebut limit, akan menjadi scout dan solusi mereka ditinggalkan.



Langkah–langkah Artificial Bee Colony (ABC) • Langkah 1: – Inisialisasi posisi sumber makanan. – Letak atau posisi sumber makanan baru diperoleh dari lebah scout yang melakukan pencarian secara acak tanpa memori sebelumnya. • Langkah 2: – Gerakkan lebah pekerja menuju sumber-sumber makanan dan tentukan jumlah nektarnya. – Lebah pekerja bergerak untuk mendapatkan sumber makanan baru dengan rumus sebagai berikut :



𝑤𝑖 𝑐 + 1 = 𝑤𝑖 𝑐 + 𝜑𝑖 𝑤𝑖 𝑐 − 𝑤𝑘 𝑐



Langkah–langkah Artificial Bee Colony (ABC) • Langkah 3: – Gerakkan lebah onlooker menuju sumber-sumber makanan dan tentukan jumlah nektarnya. – Pada langkah ini, lebah onlooker memilih sebuah sumber makanan dengan memperhitungkan probabilitas sumber makan tersebut. – Asumsikan bahwa adalah posisi dari sumber makanan (solusi untuk masalah ini) dan f () merupakan jumlah nektar-nya (kualitas solusi). – Misalkan P(c) = {(c) | i = 1, 2,. . , s} (c menunjukkan siklus; s, jumlah sumber makanan di sekitar sarang) mewakili populasi posisi sumber makanan.



Langkah–langkah Artificial Bee Colony (ABC) – Jika jumlah nektar dari sumber makanan yang tinggi, probabilitas sumber yang dipilih oleh lebah onlooker menjadi tinggi secara proporsional. Probabilitas dapat didefinisikan sebagai :



𝑓(𝑤𝑖 ) 𝑝𝑖 = 𝑠 ∑𝑘=1 𝑓(𝑤𝑘 )



– dimana s adalah jumlah sumber makanan (sejumlah solusi dalam populasi) dan juga sama dengan jumlah lebah yang digunakan dalam koloni. – Sebuah lebah onlooker memilih daerah sumber makanan tergantung pada probabilitas yang dihitung.



Langkah–langkah Artificial Bee Colony (ABC) – Proses ini diulang sampai semua lebah onlooker didistribusikan di antara sumber-sumber makanan (solusi). – Dengan cara ini, para lebah onlooker merekrut sumber makanan dengan jumlah nektar yang tinggi (solusi dengan nilai fitness tinggi) yang telah ditentukan oleh lebah pekerja. – Dan onlooker juga mendapatkan sebuah sumber makanan baru dalam area sumber makanan yang telah dipilih. – Dengan mengasumsikan bahwa posisi sumber makanan adalah yang dipilih oleh lebah onlooker.



Langkah–langkah Artificial Bee Colony (ABC) – Posisi sumber makanan tetangga ditentukan dengan rumus (7), dimana φi adalah nomor acak dalam interval [-1, +1] dan k adalah indeks acak yang dihasilkan berbeda dari i. – Jika jumlah nektar f((c+1)) lebih besar dari f((c)), maka lebah menghafal (c+1) dan berbagi informasi dengan lebah lebah onlooker, dan posisi (c) sebagai sumber makanan i berubah menjadi (c+1), jika tidak (c) tetap sama. • Langkah 4: – Tentukan sumber makanan yang harus ditinggalkan dan alokasikan lebah pekerja sebagai scout untuk mencari sumber makanan baru berdasarkan pencarian secara acak.



Langkah–langkah Artificial Bee Colony (ABC) • Seperti disebutkan sebelumnya, setiap sumber makanan hanya memiliki satu lebah pekerja, sehingga jumlah lebah pekerja sama dengan sejumlah sumber makanan. • Jika posisi tidak dapat ditingkatkan melalui jumlah yang telah ditetapkan percobaan "limit" lebah, sumber makanan saya ditinggalkan dan lebah yang pekerja dan menjadi scout. • Scout mulai mencari sumber makanan baru secara acak, dan setelah menemukan sumber baru, posisi baru diterima menjadi (c+1). • Lebah scout bergerak mencari sumber makanan baru secara acak dengan rumus sebagai berikut :



𝑤𝑖𝑗 = 𝑤𝑗 𝑚𝑖𝑛 + 𝑟𝑎𝑛𝑑 . 𝑤𝑗 𝑚𝑎𝑥 − 𝑤𝑗 𝑚𝑖𝑛



Langkah–langkah Artificial Bee Colony (ABC) • Langkah 5: – Catat sumber makanan terbaik yang telah ditemukan sejauh ini. • Langkah 6: – Ulangi langkah 2 – 5 hingga kriteria yang diinginkan terpenuhi.