PENGGUNAAN GRAF DALAM ALGORITMA SEMUT UNTUK MELAKUKAN OPTIMASI Presented by : Frisal Argha Kusumah Nurandito Vidyawan
PENGGUNAAN GRAF DALAMALGORITMA SEMUT UNTUK
MELAKUKAN OPTIMASI
Presented by :Frisal Argha Kusumah Nurandito Vidyawan
“Sesungguhnya dalam penciptaan langit dan
bumi, dan silih bergantinya malam dan siang
terdapat tanda-tanda bagi orang-orang yang
berakal,” (QS 3:190)
Latar Belakang
Optimisasi
Seiring berkembangnya pemikiran, banyak sekaliditemukan sejumlah algoritma dalam AI(Artifical Intelligence) yang mendapat inspirasidari alam. Salah satu diantaranya adalah :
Algoritma semut
Men
gg
un
akan
GR
AF
Latar Belakang
Optimisasi ialah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai efektif yang dapat dicapai).
Nilai optimal adalah nilai yang didapat dengan melalui suatu proses dan dianggap menjadi suatu solusi jawaban yang paling baik dari semua solusi yang ada.
TujuanAlgoritma semut merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik (solusi terbaik -nilai optimal) melalui grafik .
Kasus Seputar Optimasi1. Menentukan lintasan terpendek
[Traveling Salesman Problem (TSP)]
2. Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu proses produksi [Quadratic Assignment Problem (QAP)]
3. Mengatur jalur kendaraan umum agar semua lokasi dapat dijangkau.
4. Job-shop Scheduling Problem (JSP)
5. Mengatur routing jaringan kabel telepon. Dll
Sejarah Algoritma Semut
Algoritma semut diperkenalkan oleh Moysondan Manderick dan secara meluas dikembangkan oleh Marco Dorigo. Algoritma ini terinspirasioleh perilaku semut dalam menemukan jalur darikoloninya menuju makanan.
Pada tahun 1996, dunia AI pun ikut belajar dari semut dengan diperkenalkannya algoritma semut, atau Ant Colony Optimization.
SARANG
Cara kerja semut mencari jalur optimal
Pada awalnya, semut berkeliling secara acak, hingga menemukan makanan.
Cara kerja semut mencari jalur optimal
SARANG
FEROMON
Feromon 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.
Feromon, berasal dari bahasa Yunani ‘phero’ yang artinya ‘pembawa’ dan ‘mone’ ‘sensasi’
Ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon.
Cara kerja semut mencari jalur optimal
SARANG (KOLONI)JEJAK
FEROMON
JEJAK FEROMON
JEJAK FEROMON
Jika semut-semut lain menemukan jalur tersebut, mereka tidak akan bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut.
Cara kerja semut mencari jalur optimal
SARANG
Semut-semut itu kembali ke sarang dan menguatkannya (jejak feromon) jika pada akhirnya mereka pun menemukan makanan.
Cara kerja semut mencari jalur optimal
SARANG
Seekor semut yang secara tidak sengajamenemukan jalur optimal akan
menempuh jalur ini lebih cepat darirekan-rekannya, melakukan round-trip
lebih sering, dan dengan sendirinyameninggalkan feromon lebih banyak
dari jalur-jalur yang lebih lambatditempuh.
Cara kerja semut mencari jalur optimal
SARANG
Feromon yang berkonsentrasi tinggipada akhirnya akan menarik semut-semutlain untuk berpindah jalur, menuju jalur paling optimal, sedangkan jalur lainnya akan ditinggalkan.
Cara kerja semut mencari jalur optimal
SARANG
FERONMON KONSENTRAS
I TINGGI
Pada akhirnya semua semut yangtadinya menempuh jalur yang berbeda-beda akan beralih ke
sebuah jalurtunggal yang ternyata paling
optimaldari sarang menuju ke tempat
makanan.
Cara kerja semut mencari jalur optimal
SARANG
Definisi Graf
Graf G = (V, E), yang dalam hal ini:V = himpunan tidak-kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn }E = himpunan sisi (edges) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }
Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
Definisi Graf
G adalah graf denganV = { 1, 2, 3, 4 }E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3,4) } = { e1, e2, e3, e4, e5, e6, e7}
Definisi Graf
Macam-macam Graf Berdasarkan orientasi arah
pada sisi
Graf tak-berarah
(undirected graph)
Graf berarah (directed
graph atau digraph)
Macam-macam Graf Graf berarah
(directed graph atau digraph)
Graf tak-berarah (undirected graph)
Macam-macam Graf
Graf Hamilton
Untuk mencarijumlah sirkuit Hamilton di dalam graf lengkapdengan n simpul adalah: (n - 1)!/2.
Analisis Algoritma Semut untuk Mencari Nilai Optimal Menggunakan Graf
?START
Analisis Algoritma Semut….
1. Lingkungan yang digunakan adalah sebuah graf
yang fully connected dan bidirectional.2. Sistem multi agen (mengerahkan seluruh
koloni semut) dan disebar di setiap node secara merata.
3. Agen menggunakan jalur Hamilton.4. Agen (semua semut) mengunjungi semua
node.
SYARAT DAN
KETENTUAN
Tahapan-tahapan algoritma… 1. Setiap semut (ant) memulai turnya melalui sebuah kota yang dipilih secara acak. Secara berulang kali, satu-persatu kota yang ada dikunjungi oleh ants dengan tujuan untuk menghasilkan tur yang lengkap (yaitu mengunjungi masing-masing kota sekali saja).
2. Pemilihan kota-kota yang akan dilalui ant didasarkan pada suatu fungsi probabilitas, dinamai aturan transisi status (state transition rule), dengan mempertimbangkan visibility (invers dari jarak) kota tersebut dan jumlah pheromone yang terdapat pada ruas yang menghubungkan kota tersebut.
Tahapan-tahapan algoritma…
3. Ants lebih suka untuk bergerak menuju ke kota-kota yang dihubungkan dengan ruas yang pendek dan atau memiliki tingkat pheromone yang tinggi [Dorigo danGambardella, 1997].
Tahapan-tahapan algoritma…
4. Setiap kota yang disinggahi oleh ant akan disimpan dalam ingatannya yang disebut dengan tabu list. Dengan mengeksplorasi memori yang dimiliki oleh setiap semut maka setiap semut dapat membangun solusi yang mungkin.
Tahapan-tahapan algoritma…
5. Setelah semua ants menyelesaikan tur mereka dan tabu list mereka menjadi penuh, sebuah aturan pembaruan pheromone global (global pheromone updating rule) dilaksanakan pada setiap semut.
Tahapan-tahapan algoritma…
Penguapan pheromone pada semua ruas dilakukan, dankemudian setiap semut menghitung panjang tur yang telah mereka lakukan lalu menaruh sejumlah pheromone pada ruas-ruas yang merupakan bagian dari tur mereka
Tahapan-tahapan algoritma… Semakin pendek sebuah tur yang dihasilkan oleh seekor semut, jumlah pheromone yang diletakkan pada ruas-ruas yang dilaluinya pun semakin besar. Hal ini menyebabkan ruas-ruas yang diberi pheromone lebih banyak akan lebihdiminati/dipertimbangkan pada tur-tur selanjutnya, dan sebaliknya ruas-ruas yang tidak diberi pheromone menjadi kurang diminati.Jalur terpendek yang ditemukan oleh ants disimpan dan semua tabu list yang ada dikosongkan kembali.
Tahapan-tahapan algoritma… 1
Tahapan-tahapan algoritma…
2
Tahapan-tahapan algoritma…
3
Tahapan-tahapan algoritma…
4
Tahapan-tahapan algoritma…
5
Aplikasi Algoritma semutTravelling Salesman Problem (TSP) adalah suatu masalah yang ditemukan oleh pedagang yang harus bepergian dan singgah di beberapa kota hingga kembali ke kota semula.
Aplikasi TSP diantaranya pada persoalan perencanaan pembangunan, perencanaan produksi, rute pengambilan surat dari kotak pos, rute pengisian uang pada ATM, rute patroli polisi, rute pesawat terbang dsb.
Traveling Salesman Problem
Graf di atas memiliki (4 – 1)!/2 = 3 sirkuit Hamilton yaitu:I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang= 10 + 12 + 8 + 15 = 45I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang= 12 + 5 + 9 + 15 = 41I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang= 10 + 5 + 9 + 8 = 32
Traveling Salesman Problem
Jadi, sirkuit Hamilton terpendek adalah I3 = (a,c,b,d,a)atau(a,d,b,c,a) dengan panjang sirkuit= 10 + 5 + 9 + 8 = 32.
Penyelesaian TSP menggunakanalgoritma semut
Pada simulasi algoritma semut, diperlukan tiga tabel besar (dengan dimensi n x n dimana n adalah banyaknya kota) untuk mencari lintasan optimal. Tabel pertama adalah tabel jarak (distance array),tabel kedua adalah tabel feromon (pheromone array), tabel ketiga adalah tabel delta feromon (delta pheromone array).
Penyelesaian TSP menggunakanalgoritma semut
Penyelesaian TSP menggunakanalgoritma semut
Sekian Terima kasih