Perbandingan Kompleksitas Algoritma Ant Colony Optimization dengan Simulated Annealing pada kasus TSP

Abstrak

Ant Colony Optimization adalah sebuah algoritma pencarian rute terpendek yang dapat digunakan untuk berbagai kasus optimasi kombinatorial seperti pencarian rute GPS, Travelling Salesman Problems, dan lain-lain. Algoritma ini juga digunakan oleh perusahaan besar Google untuk mengoptimasi mesin pencariannya. Ant Colony Optimization (ACO) ini dikembangkan melalui algoritma meta-heuristic yang mencontoh perilaku semut dalam mencari rute. Dalam kasus ini heuristic-nya adalah pheromone dari semut yang menandakan rute yang sudah dilalui. Menurut beberapa penelitian algortima ini lebih cepat daripada Algoritma Geetika untuk kasus yang banyak node (Peter Kohout : www.codeproject.com). membandingan antara ACO dengan Simulated Annealing (SA) pada kasus TSP (Travelling Salesman Problems) dari sisi optimasi dan waktu prosesnya.

Kata kunci: Ant Colony Optimization, meta-heuristic, Optimasi Kombinatorial, ACO, TSP (Travelling Salesman Problems), Simulated Annealing (SA)

1. Pendahuluan

1.1.  Latar Belakang

Ant Colony Optimization adalah algoritma meta-heuristik yang digunakan untuk pemecahan masalah optimasi kombinatorial yang sulit untuk dikomputasi. Salah satu contohnya adalah masalah Travelling Salesman Problem dan Mesin Pencarian Google. Algoritma ini memiliki karakteristik pencarian yang dapat membuatnya dapat lebih cepat dari Genetic Algoritma, tetapi hasil yang didapat bukan yang paling optimal. Ant Colony Optimization ini ditemukan oleh Marco Dorigo dan Christian Blum pada akhir tahun 90-an.

1.2.  Tujuan

-          Membuktikan perhitungan kompleksitas Ant Colony Optimization

-          Membandingkan dengan metode lain

1.3.  Identifikasi Masalah

Menurut M. Dorigo dan Christian Blum, Ant Colony Optimization memiliki pseudo code seperti dibawah ini :
input: An instance PofaCOproblem model P = (S,f,).

InitializePheromoneValues(T )

sbs ß NULL

while termination conditions not met do

Siter ß Ø

for j = 1,…,na do

S ßConstructSolution(T )

if S is a valid solution then

s ßLocalSearch(s) {optional}

if(f(s)<f(sbs))or (sbs = NULL)then sbs ß s

Siter ß Siter Union s}

end if

end for

ApplyPheromoneUpdate(T ,Siter,sbs)

end while

output: The best-so-far solution sbs

Dengan Algoritma Masalah seperti dibawah ini :

1. Semut pertama menemukan sumber makanan (F), melalui segala kemungkinan Rute, kemudian kembali ke sarang (N), meninggalkan jejak dengan pheromone (b)
2. Semut selanjutnya mengikuti kemungkinan jalan yang dilalui semut 1, berdasarkan pheromone dari semut pertama dengan indikasi bahwa pheromone terkuat adalah rute yang sudah dilalui lebih banyak (berkali-kali).
3. Semut mengambil rute singkat, sebelum kehilangan jejak pheromones.

1.4.  Metoda Penelitian

-          Perhitungan dengan Teori dari Pseudo Code

-          Perbandingan RunTime dengan Graphical melalui source code yang telah tersedia. Dalam hal ini kami menggunakan java applets dari web :
http://www.math.tu-clausthal.de/Arbeitsgruppen/Stochastische-Optimierung/index.php?id1=lehre&id2=tsp&page=applet

-          Perbandingan dengan metoda SA (Simulated Anealling)

2. Pembahasan penelitian

2.1.  Konsep

Pseudo Kode :

input: An instance PofaCOproblem model P = (S,f,).

InitializePheromoneValues(T )

sbs ß NULL

while termination conditions not met do

Siter ß Ø

for j = 1,…,na do

S ßConstructSolution(T )

if S is a valid solution then

s ßLocalSearch(s) {optional}

if(f(s)<f(sbs))or (sbs = NULL)then sbs ß s

Siter ß Siter Union s}

end if

end for

ApplyPheromoneUpdate(T ,Siter,sbs)

end while

output: The best-so-far solution sbs

Kompleksitas :

C(T) =  ∑ d(P_ik,P_ik+1 )+d(P_ik,P_i1)

t(one iteration of pACS) = 2m·O(n²)+O(n) = O(n²),

t(one iteration of ACS) = m·O(n²)+(m+1)O(n) = O(n²).

2.2.  Model Penelitian

1. Menggunakan Konsep Matematika

(ummi ama shinta yang analisis yah….. gw kagak ngerti) à ummim rapihin ato tulis ulang aja

t(one iteration of pACS) = 2m·O(n²)+O(n) = O(n²),

t(one iteration of ACS) = m·O(n²)+(m+1)O(n) = O(n²).

1. Menggunakan pendataan Runtime Program

Dengan menggunakan java applets pada web

http://www.math.tu-clausthal.de/Arbeitsgruppen/Stochastische-Optimierung/index.php?id1=lehre&id2=tsp&page=applet

kita membandingkan hasil perhitungan antara Simulated Annealing dengan Ant Colony Optimization untuk dicari hasilnya dengan membandingkan antar tiap waktu proses untuk tiap inputan titik/node tujuan.

Code Ant Colony Optimization :

while (!Finish){

if (!BestSolutions){

TspInstance.MyDraw.DrawAnts(MyEdges.TrailIntensity,MyEdges.MaximumTrail,MyEdges.MinimumTrail);

}else{

TspInstance.MyDraw.DrawConfiguration(BestConfig);

}

for (int i=0;i<MyCities.size()-1 && !Finish;i++){

for (int j=0;j<MyAnts.size() && !Finish;j++){

GetNextCity(j);

}

}

if( !Finish ){

for (int k=0;k<MyAnts.size();k++){

((aant)MyAnts.elementAt(k)).LastTourLength=TspInstance.MyCities.GetConfigurationDistance
(((aant)MyAnts.elementAt(k)).TabuList);

if (((aant)MyAnts.elementAt(k)).LastTourLength<BestConfigDistance){

BestConfigDistance=((aant)MyAnts.elementAt(k)).LastTourLength;

BestConfig=new Vector(((aant)MyAnts.elementAt(k)).TabuList);

SetBestConfigDistance();

SetPerConfigDistance();

}

}

}

2.3.  Data Hasil

Spesifikasi Hardware :

Processor               : Amd X2 3.06 GHz

Ram                       : Twin 2×1024 MB

Ant Colony Optimization
Node	Time	Jarak
10	0.001 s	1258
30	0.014 s	2008.048
50	0.062 s	2620.714
100	0.474 s	3491.922

Simulated Annealing
Node	Time	Jarak
10	16 s	1256.761
30	20 s	1938.408
50	25 s	2614.515
100	38 s	3477.064

2.4.  Analisis

Dari data hasil percobaan diatas didapat bahwa Algoritma Ant Colony Optimization memiliki waktu proses yang lebih cepat dibandingkand engan metode GA seperti Simulated Annealing, walaupun pada hasil diatas dilihat bahwa hasil optimasi ACO lebih jauh (sedikit) dibandingkan dengan SA.

Algoritma ACO memiliki kompleksitas yang lebih tinggi daripada algoritma SA (terlihat dari perbandingan waktu pada analisi diatas).

Secara Time Complexity dan Space Complexity algoritma ACO jauh lebih baik dibandingkan dengan SA.

3. Kesimpulan dan saran pengembangan.

3.1.  Kesimpulan

ACO adalah sebuah algoritma optimasi yang lebih baik dari GA (dalam hal ini SA) dalam hal time complexity dan space complexity. Walaupun hasil dari ACO bukan hasil yang paling optimal tetapi ACO memberikan kepastian bahwa selalu complete untuk kasus TSP. Dari segi penggunaannya ACO dipilih oleh Google untuk mesin pencariannya karena algoritma ini hanya memerlukan waktu kurang dari 1 detik untuk node kurang dari 100.

3.2.  Saran

Algoritma ini dapat digunakan untuk kasus pencarian rute yang tidak begitu banyak nodenya (asumsi node < 1000 pada komputer berspesifikasi biasa)

ACO sebaiknya bisa diperbaiki untuk hasil lebih optimal (jarak terdekat)

Daftar pustaka.

[1]	Bianchi, Leonora and Luca Maria Gambardella.2007. Ant Colony Optimization and Local Search based on Exact and Estimated Objective Values for the Probabilistic Traveling Salesman Problem. IDSIA / USI-SUPSI. Switzerland.Dalle Molle Institute for Artificial Intelligence Galleria 2, 6928 Manno
[2]	Dorigo, Marco and Christian Blum. 2005. Ant Colony Optimization Theory : A Survey. Belgium . IRIDIA,Université Libre de Bruxelles.
[3]	Kohout Peter. 13 November 2003. Genetic and Ant Colony Optimization Algorithm. Australia. (http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms.aspx : 25 Maret 2009)