Pada artikel ini, saya akan membagikan sedikit pemahaman mengenai salah satu algoritma yang digunakan dalam Artificial Intelligence (AI) atau yang dikenal dengan sebutan kecerdesan buatan yaitu Sistem Algoritma Semut (Ant System Algorithm).
> Pengenalan
Swarm intelligence merupakan pendekatan yang tergolong baru untuk menyelesaikan masalah. Swarm intelligence terinspirasi dari sejumlah perilaku sosial serangga dan hewan lainnya. Secara khususnya, semut telah menjadi inspirasi bagi sejumlah metode dan teknik sehingga menghasilkan salah satu algoritma yang paling banyak diteliti dan paling sukses dalam dunia swarm intelligence yang dinamakan Ant Colony Optimization (ACO).
Marco Dorigo adalah pencetus algoritma ACO untuk menyelesaikan beberapa masalah optimisasi dikrit. Secara umumnya algoritma ACO meniru cara semut nyata mencari rute terpendek antara sumber makanan dan sarang semut.Para semut berkomunikasi satu dengan
lainnya dengan perantara jalur feromon dan melakukan pertukaran informasi
secara tidak langsung mengenai jalan manakah yang harus diikuti. Jalur dengan
kadar feromon tinggi akan mendapat perhatian lebih sehingga semut-semut lainnya
akan menggunakan jalan tersebut. Akibat dari ini adalah peningkatan kadar
feromon pada jalan yang semakin sering digunakan semut. Jalur yang jarang
dilewati akan memiliki kadar feromon yang semakin menipis. Hal ini disebabkan
karena kecenderungan feromon untuk mengalami penguapan.
Komunikasi tak langsung seperti ini diistilahkan dengan kata stigmergi, dan menghasilkan kemampuan pencarian jalur terpendek bagi koloni semut. Algoritma pertama yang menggunakan prinsip dari ACO meta-heuristik adalah Ant System (AS) dimana para semut secara iteratif mengembangkan solusi dan menambahkan feromon pada jalur yang sesuai pada solusi tersebut. Pemilihan jalur adalah prosedur stokastik yang melibatkan 2 parameter yaitu nilai feromon dan nilai heuristik. Nilai feromon memberikan indikasi dari jumlah semut yang memilih jalur yang paling sering dilewati, sedangkan nilai heuristik bergantung pada masalah dan memiliki bentuk yang berbeda pada kasus yang berbeda pula.
ACO secara umum dapat dikembangkan sehingga dapat menyelesaikan beragam masalah seperti jalur kendaraan, penjadwalan, travelling salesman problem. Bahkan pada tahun 2007 mulai dikembangkan untuk topik data mining domain, clustering, klasifikasi.
> Ant System Algorithm
Algoritma Ant System (AS) adalah algoritma ACO pertama yang dirumuskan dan diuji untuk menyelesaikan kasus TSP (Dorigo, M., Maniezzo, V., dan Colorni, A., 1996). Algoritma ini tersusun atas sejumlah m semut yang bekerjasama dan berkomunikasi secara tidak langsung melalui komunikasi Pheromone. Secara informal, AS bekerja sebagai berikut: Setiap semut memulai tournya melalui sebuah titik yang dipilih secara acak (setiap semut memiliki titik awal yang berbeda). Secara berulang kali, satupersatu titik yang ada dikunjungi oleh semut dengan tujuan untuk menghasilkan sebuah tour. 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 (Dorigo, M., dan Gambardella, L. M., 1997). Setiap semut memiliki sebuah memori, dinamai tabulist, yang berisi semua titik yang telah dikunjunginya pada setiap tour. Tabulist ini mencegah semut untuk mengunjungi titik-titik 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.
Semakin pendek sebuah tour yang dihasilkan oleh setiap semut, jumlah Pheromone yang ditinggalkan pada edge-edge 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. Dan juga, rute terpendek yang ditemukan oleh semut disimpan dan semua tabu list yang ada dikosongkan kembali. 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.
Itulah sekilas artikel yang bisa saya muat mengenai Ant System Algorithm (Sistem Algoritma Semut), semoga dapat bermanfaat bagi kita semua :)
Referal :> Pengenalan
Swarm intelligence merupakan pendekatan yang tergolong baru untuk menyelesaikan masalah. Swarm intelligence terinspirasi dari sejumlah perilaku sosial serangga dan hewan lainnya. Secara khususnya, semut telah menjadi inspirasi bagi sejumlah metode dan teknik sehingga menghasilkan salah satu algoritma yang paling banyak diteliti dan paling sukses dalam dunia swarm intelligence yang dinamakan Ant Colony Optimization (ACO).
Marco Dorigo adalah pencetus algoritma ACO untuk menyelesaikan beberapa masalah optimisasi dikrit. Secara umumnya algoritma ACO meniru cara semut nyata mencari rute terpendek antara sumber makanan dan sarang semut.
Komunikasi tak langsung seperti ini diistilahkan dengan kata stigmergi, dan menghasilkan kemampuan pencarian jalur terpendek bagi koloni semut. Algoritma pertama yang menggunakan prinsip dari ACO meta-heuristik adalah Ant System (AS) dimana para semut secara iteratif mengembangkan solusi dan menambahkan feromon pada jalur yang sesuai pada solusi tersebut. Pemilihan jalur adalah prosedur stokastik yang melibatkan 2 parameter yaitu nilai feromon dan nilai heuristik. Nilai feromon memberikan indikasi dari jumlah semut yang memilih jalur yang paling sering dilewati, sedangkan nilai heuristik bergantung pada masalah dan memiliki bentuk yang berbeda pada kasus yang berbeda pula.
ACO secara umum dapat dikembangkan sehingga dapat menyelesaikan beragam masalah seperti jalur kendaraan, penjadwalan, travelling salesman problem. Bahkan pada tahun 2007 mulai dikembangkan untuk topik data mining domain, clustering, klasifikasi.
> Ant System Algorithm
Algoritma Ant System (AS) adalah algoritma ACO pertama yang dirumuskan dan diuji untuk menyelesaikan kasus TSP (Dorigo, M., Maniezzo, V., dan Colorni, A., 1996). Algoritma ini tersusun atas sejumlah m semut yang bekerjasama dan berkomunikasi secara tidak langsung melalui komunikasi Pheromone. Secara informal, AS bekerja sebagai berikut: Setiap semut memulai tournya melalui sebuah titik yang dipilih secara acak (setiap semut memiliki titik awal yang berbeda). Secara berulang kali, satupersatu titik yang ada dikunjungi oleh semut dengan tujuan untuk menghasilkan sebuah tour. 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 (Dorigo, M., dan Gambardella, L. M., 1997). Setiap semut memiliki sebuah memori, dinamai tabulist, yang berisi semua titik yang telah dikunjunginya pada setiap tour. Tabulist ini mencegah semut untuk mengunjungi titik-titik 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.
Semakin pendek sebuah tour yang dihasilkan oleh setiap semut, jumlah Pheromone yang ditinggalkan pada edge-edge 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. Dan juga, rute terpendek yang ditemukan oleh semut disimpan dan semua tabu list yang ada dikosongkan kembali. 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.
Itulah sekilas artikel yang bisa saya muat mengenai Ant System Algorithm (Sistem Algoritma Semut), semoga dapat bermanfaat bagi kita semua :)
An Improved Ant System Algorithm for the Vehicle Routing Problem
Ant colonies for the traveling salesman problem
A new rank based version of the Ant System
Tidak ada komentar untuk “Sistem Algoritma Semut (Ant System Algorithm)”
Posting Komentar