Download - algoritma semut

Transcript
Page 1: algoritma semut

MAKALAH KECERDASAN BUATAN

ALGORITMA SEMUT, GENETIKA DAN PARTICLE SWARM

Oleh :

Welly Nopi Healtanto

I0411041

JURUSAN TEKNIK MESIN FAKULTAS TEKNIK

UNIVERSITAS SEBELAS MARET

SURAKARTA

2015

Page 2: algoritma semut

A. Algoritma Semut (Ant Colony)

Algoritma semut diperkenalkan oleh Moyson dan Manderick dan secara meluas

dikembangkan oleh Marco Dorigo merupakan teknik probabilistik untuk

menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui

grafik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari

koloninya menuju makanan.

Pada dunia nyata, semut berkeliling secara acak, dan ketika menemukan makanan

mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. Jika

semut-semut lain menemukan jalur tersebut, mereka tidak akan bepergian dengan

acak lagi, melainkan akan mengikuti jejak tersebut, kembali dan menguatkannya jika

pada akhirnya merekapun menemukan makanan.

Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan

mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi melalui

jalur tersebut, lebih lama jugalah feromon menguap. Sebagai perbandingan, sebuah

jalur yang pendek akan berbaris lebih cepat, dan dengan demikian kerapatan feromon

akan tetap tinggi karena terletak pada jalur secepat penguapannya. Penguapan

feromon juga mempunyai keuntungan untuk mencegah konvergensi pada

penyelesaian optimal secara lokal. Jika tidak ada penguapan sama sekali, jalur yang

dipilih semut pertama akan cenderung menarik secara berlebihan terhadap semut-

semut yang mengikutinya. Pada kasus yang demikian, eksplorasi ruang penyelesaian

akan terbatasi.

Oleh karena itu, ketika seekor semut menemukan jalur yang bagus (jalur yang

pendek) dari koloni ke sumber makanan, semut lainnya akan mengikuti jalur tersebut,

dan akhirnya semua semut akan mengikuti sebuah jalur tunggal. Ide algoritma koloni

semut adalah untuk meniru perilaku ini melalui 'semut tiruan' berjalan seputar grafik

yang menunjukkan masalah yang harus diselesaikan.

Algoritma optimisasi koloni semut telah digunakan untuk menghasilkan penyelesaian

yang mendekati optimal pada masalah salesman yang melakukan perjalanan.

Algoritma semut lebih menguntungkan daripada pendekatan penguatan tiruan

(simulaten annealing) dan algoritma genetik saat grafik mungkin berubah secara

dinamis; algoritma koloni semut dapat berjalan secara kontinyu dan menyesuaikan

dengan perubahan secara waktu nyata (real time). Hal ini menarik

dalam routing jaringan dan sistem transportasi urban.

2

Page 3: algoritma semut

1. Pencarian jalur terpendek

Secara umum penyelesaian masalah pencarian jalur terpendek dapat dilakukan

menggunakan dengan dua metode, yaitu metode algoritma konvensional dan

metode heuristik. Metode algoritma konvensional diterapkan dengan cara

perhitungan matematis seperti biasa, sedangkan metode heuristik diterapkan

dengan perhitungan kecerdasan buatan dengan menentukan basis pengetahuan dan

perhitungannya.

a. Metode konvensional

Metode konvensional berupa algoritma yang menggunakan perhitungan

matematis biasa. Ada beberapa metode konvensional yang biasa digunakan

untuk melakukan pencarian jalur terpendek, diantaranya Djikstraa, Floyd-

Warshall, dan algoritma Bellman-Ford.

b. Metode heuristik

Adalah sub bidang dari kecerdasan buatan yang digunakan untuk melakukan

pencarian dan penentuan jalur terpendek. Ada beberapa algoritma pada

metode heuristik yang biasa digunakan dalam pencarian jalur terpendek. Salah

satunya adalah algoritma semut.

Gambar 1. Algoritma Koloni Semut

2. Prinsip Kerja Algoritma Semut

a. Cara kerja semut mencari jalur optimal

Semut mampu mengindera lingkungannya yang kompleks untuk mencari makanan

dan kemudian kembali ke sarangnya dengan meninggalkan zat feromon pada jalur-

jalur yang mereka lalui. 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.Berbeda dengan hormon,

3

Page 4: algoritma semut

feromon menyebar ke luar tubuh dan hanya dapat mempengaruhi dan dikenali oleh

individu lain yang sejenis (satu spesies).

Proses peninggalan feromon ini dikenal sebagai stigmergy, sebuah proses

memodifikasi lingkungan yang tidak hanya bertujuan untuk mengingat jalan

pulang ke sarang, tetapi juga memungkinkan para semut berkomunikasi

dengan koloninya.

Seiring waktu, bagaimanapun juga jejak feromon akan menguap dan akan

mengurangi kekuatan daya tariknya. Lebih lama seekor semut pulang pergi

melalui jalur tersebut, lebih lama jugalah feromon menguap.

Agar semut mendapatkan jalur optimal, diperlukan beberapa proses:

1. Pada awalnya, semut berkeliling secara acak, hingga menemukan

makanan. Lihat Gambar 2.

2. Ketika menemukan makanan mereka kembali ke koloninya sambil

memberikan tanda dengan jejak feromon.

3. Jika semut-semut lain menemukan jalur tersebut, mereka tidak akan

bepergian dengan acak lagi, melainkan akan mengikuti jejak tersebut.

4. Kembali dan menguatkannya jika pada akhirnya mereka pun menemukan

makanan.

5. Seekor semut yang secara tidak sengaja menemukan jalur optimal akan

menempuh jalur ini lebih cepat dari rekan-rekannya, melakukan round-trip

lebih sering, dan dengan sendirinya meninggalkan feromon lebih banyak

dari jalur-jalur yang lebih lambat ditempuh.

6. Feromon yang berkonsentrasi tinggi pada akhirnya akan menarik

semutsemut lain untuk berpindah jalur, menuju jalur paling optimal,

sedangkan jalur lainnya akan ditinggalkan.

7. Pada akhirnya semua semut yang tadinya menempuh jalur yang

berbedabeda akan beralih ke sebuah jalur tunggal yang ternyata paling

optimal dari sarang menuju ke tempat makanan. Lihat Gambar 3

Gambar 2. Lintasan Awal Semut Menuju Tempat Makanan

4

Page 5: algoritma semut

Keterangan Gambar 2:

A : Tempat awal koloni (sarang)

B : Tujuan koloni semut (makanan)

Jalur 1 (biru): Lintasan yang ditempuh oleh semut 1

Jalur 2 (hitam): Lintasan yang ditempuh oleh semut 2

Gambar 3.Lintasan Optimal Semut Menuju tempat Makanan

Keterangan Gambar 3:

A : Tempat awal koloni (sarang)

B : Tujuan koloni semut (makanan)

Jalur Optimal : Jalur yang dilewati semut setelah beberapa iterasi

Seluruh proses ini menunjukkan berlangsungnya optimisasi alami kaum semut

yang bisa kita tiru dalam kehidupan sehari-hari.

b. Algoritma Semut dalam Kecerdasan Buatan

Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah

untuk menentukan jalur terpendek, yaitu:

Langkah 1:

a. Inisialisasi harga parameter-parameter algoritma.

Parameter-parameter yang di inisialisasikan adalah:

1. Intensitas jejak semut antar kota dan perubahannya (τij)

2. Banyak kota (n) termasuk x dan y (koordinat) atau dij (jarak antar kota)

3. Penentuan kota berangkat dan kota tujuan

4. Tetapan siklus-semut (Q)

5. Tetapan pengendali intensitas jejak semut (α)

6. Tetapan pengendali visibilitas (β)

7. Visibilitas antar kota = 1/dij (ηij)

8. Jumlah semut (m)

9. Tetapan penguapan jejak semut (ρ)

5

Page 6: algoritma semut

10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma

dijalankan, sedangkan τij akan selalu diperbaharui harganya pada setiap

siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah

siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi.

b. Inisialisasi kota pertama setiap semut.

Setelah inisialisasi τij dilakukan, kemudian m semut ditempatkan pada

kota pertama yang telah ditentukan.

Langkah 2:

Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama

semut pada langkah 1 harus diisikan sebagai elemen pertama tabu list.

Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap

semut dengan indeks kota pertama.

Langkah 3:

Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut

yang sudah terdistribusi ke kota pertama akan mulai melakukan perjalanan

dari kota pertama sebagai kota asal dan salah satu kotakota lainnya

sebagai kota tujuan. Kemudian dari kota kedua, masing-masing koloni

semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-

kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya.

Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota

yang telah ditentukan. Jika s menyatakan indeks urutan kunjungan, kota

asal dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai

{N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan

probabilitas kota untuk dikunjungi sebagai berikut,

dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.

6

Page 7: algoritma semut

Langkah 4:

a. Perhitungan panjang jalur setiap semut. Perhitungan panjang jalur

tertutup (length closed tour) atau Lk setiap semut dilakukan setelah

satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan

berdasarkan tabuk masing-masing dengan persamaan berikut:

dengan dij adalah jarak antara kota i ke kota j yang dihitung

berdasarkan persamaan:

b. Pencarian rute terpendek.

Setelah Lk setiap semut dihitung, akan diperoleh harga minimal

panjang jalur tertutup setiap siklus atau LminNC dan harga minimal

panjang jalur tertutup secara keseluruhan adalah atau Lmin.

c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota.

Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar

kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut

yang lewat, menyebabkan kemungkinan terjadinya perubahan harga

intensitas jejak kaki semut antar kota. Persamaan perubahannya

adalah:

dengan k Δτij adalah perubahan harga intensitas jejak kaki semut antar

kota setiap semut yang dihitung berdasarkan persamaan

untuk (i,j) ∈ kota asal dan kota tujuan dalam tabuk

Δτij = , untuk (i,j) lainnya

Langkah 5:

7

Page 8: algoritma semut

a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus

selanjutnya.

Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota

ada kemungkinan berubah karena adanya penguapan dan perbedaan

jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan

melewati lintasan tersebut harga intensitasnya telah berubah. Harga

intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung

dengan persamaan:τij = ρ τ⋅ ij + Δτij

b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota.

Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota

perlu diatur kembali agar memiliki nilai sama dengan nol.

Langkah 6:

Pengosongan tabu list, dan ulangi langkah dua jika diperlukan. Tabu list

perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada

siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau

belum terjadi konvergensi. Algoritma diulang lagi dari langkah dua dengan

harga parameter intensitas jejak kaki semut antar kota yang sudah

diperbaharui.

3. Contoh Kasus

Jika diketahui suatu graph di bawah yang ingin diketahui jalur terpendek dari kota

A ke kota E:

Gambar 4. Ilustrasi Graph dengan 5 Kota

8

Page 9: algoritma semut

Dengan jarak antar kota (dij) sebagai berikut:

Parameter–parameter yang digunakan adalah:

α = 1.00

β = 1.00

ρ = 0.50

τij (awal) = 0.01

Maksimum siklus (NCmax) = 2

Tetapan siklus semut (Q) = 1

Banyak semut (m) = 4

Dari jarak kota yang telah diketahui dapat dihitung visibilitas antar kota (ηij) =

1/dij

9

Page 10: algoritma semut

Siklus ke-1:

Panjang jalur semut:

Siklus ke-2:

Panjang jalur semut:

Dari dua siklus diatas, diketahui lintasan terpendek diperoleh oleh semut ke-4

dengan jalur A-D-E dengan panjang lintasan 7.

10

Page 11: algoritma semut

B. Algoritma Genetika

Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer untuk

menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian.

Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan

menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan,

mutasi, seleksi alam dan rekombinasi (ataucrossover)

Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an

di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya

menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun

1975.

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah

populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut

individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi

yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai

string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian

(encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang

lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan

keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi

sekarang (current) tersebut secara stochastic(berdasarkan kemampuan mereka), lalu

dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang

menjadi populasi sekarang (current) pada iterasiberikutnya dari algoritma.

1. Teori Dasar Algoritma Genetika

Algoritma genetika yang dikembangkan oleh Goldberg adalah algoritma

komputasi yang diinspirasi teori evolusi Darwin yang menyatakan bahwa

kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat adalah yang

menang”. Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk

dapat dipertahankan melalui proses reproduksi, crossover, dan mutasi. Konsep

dalam teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma

komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih

“alamiah”.

Sebuah solusi yang dibangkitkan dalam algoritma genetika disebut sebagai

chromosome, sedangkan kumpulan chromosome-chromosome tersebut disebut

sebagai populasi. Sebuah chromosome dibentuk dari komponen-komponen

11

Page 12: algoritma semut

penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik,

biner, simbol ataupun karakter tergantung dari permasalahan yang ingin

diselesaikan.

Chromosome-chromosome tersebut akan berevolusi secara berkelanjutan yang

disebut dengan generasi. Dalam tiap generasi chromosome-chromosome tersebut

dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin

diselesaikan (fungsi_objektif) menggunakan ukuran yang disebut dengan fitness.

Untuk memilih chromosome yang tetap dipertahankan untuk generasi selanjutnya

dilakukan proses yang disebut dengan seleksi. Proses seleksi chromosome

menggunakan konsep aturan evolusi Darwin yang telah disebutkan sebelumnya

yaitu chromosome yang mempunyai nilai fitness tinggi akan memiliki peluang

lebih besar untuk terpilih lagi pada generasi selanjutnya.

Chromosome-chromosome baru yang disebut  dengan offspring, dibentuk dengan

cara melakukan perkawinan antar chromosome-chromosome dalam satu generasi

yang disebut sebagai proses crossover. Jumlah chromosome dalam populasi yang

mengalami crossover ditetukan oleh paramater yang disebut dengan

crossover_rate. Mekanisme perubahan susunan unsur penyusun mahkluk hidup

akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai

proses berubahnya satu atau lebih nilai gen dalam chromosome dengan suatu nilai

acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh

parameter yang dinamakan mutation_rate. Setelah beberapa generasi akan

dihasilkan chromosome-chromosome yang nilai gen-gennya konvergen ke suatu

nilai tertentu yang merupakan solusi terbaik yang dihasilkan oleh algoritma

genetika terhadap permasalahan yang ingin diselesaikan.

2. Komponen Algoritma Genetik

Parameter Genetic Algorithm

Dalam GA ada beberapa parameter yang menjadi acuan yang standar dalam

menentukan proses optimasi. Beberapa diantaranya adalah:

1. Ukuran populasi

2. Probabilitas CrossOver

3. Probabilitas Mutasi

12

Page 13: algoritma semut

Teorema Skema

Tahap1

Teorema skema merupakan dasar teory yang menjelaskan bagaimana Genetic

algorithm bekerja. Skema adalah keserupaan pola dalam mendeskripsikan suatu

himpunanan bagian dari beberapa string yang mempunyai kesamaan pada posisi

tertentu. Sebuah skema dibentuk dengan menambahkan sebuah simbol spesial,

yaitu sebuah simbol * (don’t care) dalam representasi biner(0 atau 1).

Contoh: *01 adalah 101 atau 001 yaitu 5 atau 1

Tahap2

Tingkatan dari sebuah skema S(dinotasikan denga o(S)) menunjukkan jumlah dari

posisi angka 0 atau 1 yang sudah tetap(Bukan posisi don’t care) yang ada dalam

skema. Tingkatan ini menunjukkan spesialisasi dari sebuah skema.

Contoh: S1=(* * * 0 0 1 * 1 1 0)

S2=(* * * * 0 0 * * 0 * )

S3=(1 1 1 0 1 * * 0 0 1)

Dimana

o(S1)= 6

o(S2)= 3

o(S3)= 8

Tahap3

Batasan panjang dari skema S (dinotasikan dengan δ(S)) adalah jarak antara posisi

angka 0 atau 1 yang pertama hingga terakhir. Angka ini menunjukkan kerapatan

informasi yang ada dalam sebuah skema.

Contoh: δ (S1)= 10-4=6; δ (S2)= 9-5 =4; δ (S3)= 10-1=9;

3. Contoh Aplikasi Algoritma Genetika

Berikut adalah contoh aplikasi algoritma genetika yang digunakan untuk

menyelesaikan masalah kombinasi. Misalkan ada persamaan a+2b+3c+4d = 30,

kita mencari nilai a, b, c, dan d yang memenuhi persamaan diatas. Kita mencoba

menggunakan algoritma genetika untuk menyelesaikan permasalahan diatas.

Penjelasan mengenai langkah-langkah penyelesaian permasalahan diatas

menggunakan algoritma genetika adalah sebagai berikut:

13

Page 14: algoritma semut

1. Pembentukan chromosome

Karena yang dicari adalah nilai a, b, c, d maka variabel  a, b, c, d dijadikan

sebagai gen-gen pembentuk chromosome. Batasan nilai variabel a adalah

bilangan integer 0 sampai 30. Sedangkan batasan nilai variabel b, c, dan d

adalah bilangan integer 0 sampai 10.

2. Inisialisasi

Proses inisialisasi dilakukan dengan cara memberikan nilai awal gen-gen

dengan nilai acak sesuai batasan yang telah ditentukan.

Misalkan kita tentukan jumlah populasi adalah 6, maka:

Chromosome[1] = [a;b;c;d] = [12;05;03;08]

Chromosome[2] = [a;b;c;d] = [02;01;08;03]

Chromosome[3] = [a;b;c;d] = [10;04;03;04]

Chromosome[4] = [a;b;c;d] = [20;01;10;06]

Chromosome[5] = [a;b;c;d] = [01;04;03;09]

Chromosome[6] = [a;b;c;d] = [20;05;07;01]

3. Evaluasi Chromosome

Permasalahan yang ingin diselesaikan adalah  nilai variabel a, b, c, dan d yang

memenuhi persamaan a+2b+3c+4d = 30, maka fungsi_objektif yang dapat

digunakan untuk mendapatkan solusi adalah  fungsi_objektif(chromosome) = |

(a+2b+3c+4d) – 30 |

Kita hitung fungsi_objektif dari chromosome yang telah dibangkitkan:

fungsi_objektif(chromosome[1]) = Abs(( 12 + 2*5 + 3*3 + 4*8 ) – 30) = 33

fungsi_objektif(chromosome[2]) = Abs(( 2 + 2*1 + 3*8 + 4*3 ) – 30) = 10

fungsi_objektif(chromosome[3]) = Abs(( 10 + 2*4 + 3*3 + 4*4 ) – 30) = 13

fungsi_objektif(chromosome[4]) = Abs(( 20 + 2*1 + 3*10 + 4*6 ) – 30) = 46

fungsi_objektif(chromosome[5]) = Abs(( 1 + 2*4 + 3*3 + 4*9 ) – 30) = 24

fungsi_objektif(chromosome[6]) = Abs(( 20 + 2*5 + 3*7 + 4*1 ) – 30) = 25

Rata-rata dari fungsi objektif adalah:

rata-rata = (33+10+13+46+24+25)/6 = 25.167

4. Seleksi Chromosome

Proses seleksi dilakukan dengan cara membuat chromosome yang mempunyai

fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar atau

mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan fungsi

14

Page 15: algoritma semut

fitness = (1/(1+fungsi_objektif)), fungsi_objektif perlu ditambah 1 untuk

menghindari kesalahan program yang diakibatkan pembagian oleh 0.

fitness[1]     = 1 / (fungsi_objektif[1]+1) = 0.0294

fitness[2]     = 1 / (fungsi_objektif[2]+1) = 0.0909

fitness[3]    = 1 / (fungsi_objektif[3]+1) = 0.0714

fitness[4]    = 1 / (fungsi_objektif[4]+1)= 0.0212

fitness[5]    = 1 / (fungsi_objektif[5]+1)= 0.0400

fitness[6]    = 1 / (fungsi_objektif[6]+1)= 0.0385

total_fitness  = 0.0294 + 0.0909 + 0.0714 + 0.0212 +  0.04 + 0.0385 = 0.2914

Rumus untuk mencari probabilitas: P[i] = fitness[i] / total_fitness

P[1]     = 0.0294 / 0.2914 = 0.1009

P[2]     = 0. 0909 / 0.2914 = 0.3119

P[3]     = 0. 0714 / 0.2914 = 0.2450

P[4]     = 0. 0212  / 0.2914 = 0.0728

P[5]     = 0.04  / 0.2914 = 0.1373

P[6]     = 0.0385 / 0.2914 = 0.1321

Dari probabilitas diatas dapat kita lihat kalau chromosome ke 2 yang

mempunyai fitness paling besar maka chromosome tersebut mempunyai

probabilitas untuk terpilih pada generasi selanjutnya lebih besar dari

chromosome lainnya. Untuk proses seleksi kita gunakan roulete wheel, untuk

itu kita harus mencari dahulu nilai kumulatif probabilitasnya:

C[1]     = 0.1009

C[2]    = 0.1009+ 0.3119 = 0.4128

C[3]     = 0.1009+ 0.3119 + 0.2450 = 0.6578

C[4]     = 0.1009+ 0.3119 + 0.2450 + 0.0728 = 0.7306

C[5]     = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 = 0.8679

C[6]     = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 + 0.1321 = 1

Setelah dihitung cumulative probabilitasnya maka proses seleksi

menggunakan roulete-wheel dapat dilakukan. Prosesnya adalah dengan

membangkitkan bilangan acak R dalam range 0-1.

Jika R[k] < C[1] maka pilih chromosome 1 sebagai induk, selain itu pilih

chromosome ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Kita putar

roulete wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acak

R) dan pada tiap putaran, kita pilih satu chromosome untuk populasi baru.

15

Page 16: algoritma semut

Misal:

R[1] = 0.201

R[2] = 0.284

R[3] = 0.009

R[4] = 0.822

R[5] = 0.398

R[6] = 0.501

Angka acak pertama R[1] adalah lebih besar dari C[1] dan lebih kecil daripada

C[2] maka pilih chromosome[2] sebagai chromosome pada populasi baru, dari

bilangan acak yang telah dibangkitkan diatas maka populasi chromosome baru

hasil proses seleksi adalah:

chromosome[1] = chromosome[2]

chromosome[2] = chromosome[2]

chromosome[3] = chromosome[1]

chromosome[4] = chromosome[5]

chromosome[5] = chromosome[2]

chromosome[6] = chromosome[3]

Chromosome baru hasil proses seleksi:

chromosome[1] = [02;01;08;03]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;08]

chromosome[4] = [01;04;03;09]

chromosome[5] = [02;01;08;03]

chromosome[6] = [10;04;03;04]

5. Crossover

Setelah proses seleksi maka proses selanjutnya adalah proses crossover.

Metode yang digunakan salah satunya adalah one-cut point, yaitu memilih

secara acak satu posisi dalam chromosome induk kemudian saling menukar

gen. Chromosome yang dijadikan induk dipilih secara acak dan jumlah

chromosome yang mengalami crossover dipengaruhi oleh parameter

crossover_rate  ( ρc ).

Pseudo-code untuk proses crossover adalah sebagai berikut:

begin

k← 0;

16

Page 17: algoritma semut

while(k<populasi) do

R[k] ← random(0-1);

if (R[k] < ρc ) then

select Chromosome[k] as parent;

end;

k = k + 1;

end;

end;

Misal kita tentukan crossover probability adalah sebesar 25%, maka

diharapkan dalam satu generasi ada 50% Chromosome (3 chromosome) dari

satu generasi mengalami proses crossover. Prosesnya adalah sebagai berikut:

Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi

R[1] = 0.191

R[2] = 0.259

R[3] = 0.760

R[4] = 0.006

R[5] = 0.159

R[6] = 0.340

Maka Chromosome ke k akan dipilih sebagai induk jika R[k] < ρc, dari

bilangan acak R diatas maka yang dijadikan induk adalah chromosome[1],

chromosome[4] dan chromosome[5].

Setelah melakukan pemilihan induk proses selanjutnya adalah menentukan

posisi crossover. Ini dilakukan dengan cara membangkitkan bilangan acak

dengan batasan 1 sampai (panjang chromosome-1), dalam kasus ini bilangan

acak yang dibangkitkan adalah 1 – 3. Misalkan didapatkan posisi crossover

adalah 1 maka chromosome induk akan dipotong mulai gen ke 1 kemudian

potongan gen tersebut saling ditukarkan antar induk.

chromosome[1] >< chromosome[4]

chromosome[4] >< chromosome[5]

chromosome[5] >< chromosome[1]

Posisi cut-point crossover dipilih menggunakan bilangan acak 1-3 sebanyak

jumlah crossover yang terjadi, misal

C[1] = 1

17

Page 18: algoritma semut

C[2] = 1

C[3] = 2

offspring[1] = chromosome[1] >< chromosome[4]

= [02;01;08;03] ><  [01;04;03;09] = [02;04;03;09]

offspring[4] = Chromosome[4] >< Chromosome[5]

= [01;04;03;09] >< [02;01;08;03] = [01;01;08;03]

offspring[5] = Chromosome[5] >< Chromosome[1]

= [02;01;08;03] >< [02;01;08;03] = [02;01;08;03]

Dengan demikian populasi Chromosome setelah mengalami proses crossover

menjadi:

chromosome[1] = [02;04;03;09]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;08]

chromosome[4] = [01;01;08;03]

chromosome[5] = [02;01;08;03]

chromosome[6] = [10;04;03;04]

6. Mutasi

Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan

oleh parameter mutation_rate. Proses mutasi dilakukan dengan cara mengganti

satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara

acak. Prosesnya adalah sebagai berikut. Pertama kita hitung dahulu panjang

total gen yang ada dalam satu populasi. Dalam kasus ini panjang total gen

adalah total_gen     = (jumlah gen dalam chromosome) * jumlah populasi

= 4 * 6 = 24

Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara

membangkitkan bilangan integer acak antara 1 sampai total_gen, yaitu 1

sampai 24. Jika bilangan acak yang kita bangkitkan lebih kecil daripada

variabel mutation_rate (ρm) maka pilih posisi tersebut sebagai sub-

chromosome yang mengalami mutasi. Misal ρm kita tentukan 10% maka

diharapkan ada 10% dari total_gen yang mengalami populasi:

jumlah mutasi      = 0.1 * 24 = 2.4 = 2

Misalkan setelah kita bangkitkan bilangan acak terpilih posisi gen 12 dan 18

yang mengalami mutasi. Dengan demikian yang akan mengalami mutasi

18

Page 19: algoritma semut

adalah chromosome ke-3 gen nomor 4 dan Chromosome ke-5 gen nomor 2.

Maka nilai gen pada posisi tersebut kita ganti dengan bilangan acak 0-30.

Misalkan bilangan acak yang terbangkitkan adalah 2 dan 5. Maka populasi

chromosome setelah mengalami proses mutasi adalah:

chromosome[1] = [02;04;03;09]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;02]

chromosome[4] = [01;01;08;03]

chromosome[5] = [02;05;08;03]

chromosome[6] = [10;04;03;04]

Setelah proses mutasi maka kita telah menyelesaikan satu iterasi dalam

algoritma genetika atau disebut dengan satu generasi. Maka fungsi_objective

setelah satu generasi adalah:

chromosome[1]     = [02;04;03;09]

fungsi_objektif[1]     = Abs(( 2 + 2*4 + 3*3 + 4*9 ) – 30) = 25

chromosome[2]     = [02;01;08;03]

fungsi_objektif[2]    = Abs(( 2 + 2*1 + 3*8 + 4*3 ) – 30) = 10

chromosome[3]     = [12;05;03;02]

fungsi_objektif[3]    = Abs(( 12 + 2*5 + 3*3 + 4*2 ) – 30) = 9

chromosome[4]     = [01;01;08;03]

fungsi_objektif[4]    = Abs(( 1 + 2*1 + 3*8 + 4*3 ) – 30) = 9

chromosome[5]     = [02;05;08;03]

fungsi_objektif[5]    = Abs(( 2 + 2*5 + 3*8 + 4*3 ) – 30) = 18

chromosome[6]     = [10;04;03;04]

fungsi_objektif[6]    = Abs(( 10 + 2*4 + 3*3 + 4*4 ) – 30) = 13

Rata-rata fungsi objektif setelah satu generasi adalah:

rata-rata = ( 25 + 10 + 9 + 9 + 18 + 13) / 6 = 14.0

Dapat dilihat dari hasil perhitungan fungsi objektif diatas bahwa setelah satu

generasi, nilai hasil rata-rata fungsi_objektif lebih menurun dibandingkan hasil

fungsi_objektif pada saat sebelum mengalami seleksi, crossover dan mutasi.

Hal ini menunjukkan bahwa chromosome atau solusi yang dihasilkan setelah

satu generasi lebih baik dibandingkan generasi sebelumnya. Maka pada

generasi selanjutnya chromosome-chromosome yang baru adalah:

19

Page 20: algoritma semut

chromosome[1] = [02;04;03;09]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;02]

chromosome[4] = [01;01;08;03]

chromosome[5] = [02;05;08;03]

chromosome[6] = [10;04;03;04]

Chromosome-chromosome ini akan mengalami proses yang sama seperti

generasi sebelumnya yaitu proses evaluasi, seleksi, crossover dan mutasi yang

kemudian akan menghasilkan chromosome-chromosome baru untuk generasi

yang selanjutnya. Proses ini akan berulang sampai sejumlah generasi yang

telah ditetapkan sebelumnya.

Setelah 50 generasi didapatkan chromosome yang terbaik adalah:

Chromosome = [07;05;03;01]

Jika didekode maka:

a=7 ; b=5 ; c=3 ; d=1

Jika dihitung terhadap persamaan f = a+2b+3c+4d:

7 + (2*5) + (3*3) + (4*1) = 30

20

Page 21: algoritma semut

C. Algoritma Particle Swarm

1. Dasar Particle Swarm

Algoritma Particle Swarm Optimization (PSO) diperkenalkan oleh Kennedy dan

Eberhart pada tahun 1995, proses algoritmanya diinspirasi oleh perilaku sosial

dari binatang, seperti sekumpulan burung dalam suatu swarm. Particle Swarm

Optimization (PSO) adalah salah satu dari teknik komputasi evolusioner, yang

mana populasi pada PSO didasarkan pada penelusuran algoritma dan diawali

dengan suatu populasi yang random yang disebut dengan particle. Berbeda

dengan teknik komputasi evolusioner lainnya, setiap particle di dalam PSO juga

berhubungan dengan suatu velocity. Particle-particle tersebut bergerak melalui

penelusuran ruang dengan velocity yang dinamis yang disesuaikan menurut

perilaku historisnya. Oleh karena itu, particleparticle mempunyai kecenderungan

untuk bergerak ke area penelusuran yang lebih baik setelah melewati proses

penelusuran. Particle Swarm Optimization (PSO) mempunyai kesamaan dengan

genetic algorithm yang mana dimulai dengan suatu populasi yang random dalam

bentuk matriks. Namun PSO tidak memiliki operator evolusi yaitu crossover dan

mutasi seperti yang ada pada genetic algorithm. Baris pada matriks disebut

particle atau dalam genetic algorithm sebagai kromosom yang terdiri dari nilai

suatu variable. Setiap particle berpindah dari posisinya semula ke posisi yang

lebih baik dengan suatu velocity . Pada algoritma PSO vektor velocity diupdate

untuk masing-masing particle kemudian menjumlahkan vektor velocity tersebut

ke posisi particle. Update velocity dipengaruhi oleh kedua solusi yaitu global best

yang berhubungan dengan biaya yang paling rendah yang pernah diperoleh dari

suatu particle dan solusi local best yang berhubungan dengan biaya yang paling

rendah pada populasi awal. Jika solusi local best mempunyai suatu biaya yang

kurang dari biaya solusi global yang ada, maka solusi local best menggantikan

solusi global best . Kesederhanaan algoritma dan performansinya yang baik,

menjadikan PSO telah menarik banyak perhatian di kalangan para peneliti dan

telah diaplikasikan dalam berbagai persoalan optimisasi sistem tenaga seperti

economic dispatch, design kontrol PID pada sistem AVR, kontrol tegangan dan

daya reaktif, unit commitment dan lain sebagainya. PSO telah populer menjadi

optimisasi global dengan sebagian besar permasalahan dapat diselesaikan dengan

baik di mana variabelvariabelnya adalah bilangan riil.

21

Page 22: algoritma semut

Beberapa istilah umum yang biasa digunakan dalam Optimisasi Particle Swarm

dapat didefinisikan sebagai berikut :

1. Swarm : populasi dari suatu algoritma.

2. Particle: anggota (individu) pada suatu swarm.

Setiap particle merepresentasikan suatu solusi yang potensial pada

permasalahan yang diselesaikan. Posisi dari suatu particle adalah ditentukan

oleh representasi solusi saat itu.

3. Pbest (Personal best): posisi Pbest suatu particle yang menunjukkan posisi

particle yang dipersiapkan untuk mendapatkan suatu solusi yang terbaik.

4. Gbest (Global best) : posisi terbaik particle pada swarm.

5. Velocity (vektor): vektor yang menggerakkan proses optimisasi yang

menentukan arah di mana suatu particle diperlukan untuk berpindah (move)

untuk memperbaiki posisinya semula.

6. Inertia weight : inertia weight di simbolkan w, parameter ini digunakan untuk

mengontrol dampak dari adanya velocity yang diberikan oleh suatu particle.

2. Prosedur Penerapan Particle Swarm

Prosedur standar untuk menerapkan algoritma PSO adalah sebagai berikut :

1. Inisialisasi populasi dari particle-particle dengan posisi dan velocity secara

random dalam suatu ruang dimensi penelusuran.

2. Evaluasi fungsi fitness optimisasi yang diinginkan di dalam variabel d pada

setiap particle.

3. Membandingkan evaluasi fitness particle dengan Pbestnya. Jika nilai yang ada

lebih baik dibandingkan dengan nilai Pbestnya, maka Pbest diset sama dengan

nilai tersebut dan Pi sama dengan lokasi particle yang ada Xi dalam ruang

dimensional d.

4. Identifikasi particle dalam lingkungan dengan hasil terbaik sejauh ini.

5. Update velocity dan posisi particle.

6. Kembali ke step 2 sampai kriteria terpenuhi, biasanya berhenti pada nilai

fitness yang cukup baik atau sampai pada jumlah maksimum iterasi.

Seperti halnya dengan algoritma evolusioner yang lain, algoritma PSO adalah

sebuah populasi yang didasarkan penelusuran inisialisasi particle secara random

dan adanya interaksi diantara particle dalam populasi. Di dalam PSO setiap

22

Page 23: algoritma semut

particle bergerak melalui ruang solusi dan mempunyai kemampuan untuk

mengingat posisi terbaik sebelumnya dan dapat bertahan dari generasi ke generasi.

3. Contoh Kasus

Pada makalah ini algoritma optimasi particle swarm digunakan untuk

menyelesaikan sistem persamaan nonlinear. Data masukan utama yang

dibutuhkan untuk proses uji coba adalah sistem persamaan nonlinear dan beberapa

fungsi umum

a. Data Uji coba

23

Page 24: algoritma semut

b. Hasil dan Analisa Uji Coba

Perbandingan Hasil Uji coba Pertama

24

Page 25: algoritma semut

Perbandingan Hasil Uji coba Kedua

25

Page 26: algoritma semut

c. Grafik Perbandingan Antara Jumlah Partikel dengan Hasil

Akhir yang didapat

Pada uji coba pertama

Pada uji coba kedua

26

Page 27: algoritma semut

Masing-masing skenario pada uji coba pertama dan kedua menggunakan

jumlah partikel yang berbeda-beda. Hal ini dilakukan untuk mengetahui

hubungan antara jumlah partikel yang digunakan dengan hasil akhir yang

didapat. Grafik hubungan antara jumlah partikel dengan nilai akhir fungsi f(x)

pada uji coba pertama ditampilkan pada Gambar 2, sedangkan grafik

hubungan untuk uji coba kedua ditampilkan pada Gambar 3. Berdasarkan

gambar tersebut, hasil akhir yang didapat dengan menggunakan jumlah

partikel yang berbeda tidak jauh berbeda. Oleh karena itu disimpulkan bahwa

jumlah partikel yang digunakan tidak mempengaruhi hasil akhir.

D. Kesimpulan

1. Pemanfaatan teknologi informasi pada pencarian jalur terpendek menghasilkan

suatu hasil atau keluaran yang akurat dan tepat, untuk pilihan perjalanan seseorang

dengan mempertimbangkan beberapa parameter yang lain.

2. Secara konsep algoritma, metode konvesional lebih mudah untuk dipahami.

Namun, hasil yang diperoleh dari metode heuristik lebih variatif.

3. Algoritma genetika adalah sistem kecerdasan buatan yag meniru sel pada tubuh

manusia.

4. Algoritma genetika dapat digunakan untuk proses pencarian dan proses optimasi.

5. Algoritma Particle Swarm yang diusulkan oleh Jaberipour dapat digunakan untuk

menyelesaikan sistem persamaan nonlinear.

6. Algoritma Particle Swarm yang diusulkan oleh Jaberipour memiliki kinerja yang

baik dalam mencari solusi yang optimal. Hal ini dibuktikan dengan hasil uji coba

pertama, solusi yang didapat mendekati solusi eksak masing-masing fungsinya.

27

Page 28: algoritma semut

Daftar Pustaka

Sina, Ibnu Wardy. Penggunaan Graf dalam Algoritma Semut untuk Melakukan Optimisasi.

Institut Teknologi Bandung.

Mutakhiroh, I’ing, dkk. Pencarian Jalur Terpendek Menggunakan Algoritma Semut. SNATI.

2007.

Rosita, Ardiana. Implementasi Algoritma Particle Swarm untuk Menyelesaikan Sistem

Persamaan Nonlinear. JURNAL TEKNIK ITS Vol. 1. 2012.

28


Top Related