PENYELESAIAN TSP DENGAN ALGORITMA GENETIK

Algoritma Genetik – by Ignas Lamabelawa

PENGERTIAN TSP sebuah persoalan optimasi untuk

mencari ruteterpendek bagi seorang pedagang

keliling (salesman)

Persoalan optimasi yang ingin dicapai ialah rute

yang dilalui dan biaya yang digunakan paling

minimum

PERMASALAHANBila dipandang dari sudut komputasinya,

algoritma ini dapat diselesaikan dengan cepat walaupun dengan menggunakan algoritma brute force sekalipun, jika kota-kota yang akan dikunjunginya sedikit. Namun, jika kota-kota yang akan dikunjungi banyak, maka algoritma seperti Brute Force tidaklah menjadi pilihan lagi. Sebab, Algoritma Brute Force sendiri memiliki kompleksitas O(n!)

METODE PENYELESAIN TSP KONVENSIONAL

Salah satu cara untuk menyelesaikan TSP yaitu

dengan menggunakan Algoritma Brute Force. Hal

yang dilakukan ialah dengan cara mengenumerasi seluruh kemungkinan

rute yang akan ditempuh

METODE PENYELESAIAN - ALGORTIMA GENETIK

Beberapa metode telah dikembangkan untuk memecahkan persoalan ini namun belum ditemukan algoritma penyelesaian yang optimal. Salah satu algoritma yang muncul untuk menyelesaikan persoalan ini ialah Algoritma Genetika

CONTOH MASALAH TSP

PENYELESAIAN 1Jumlah node (n) ada 5 buah, Jumlah kemungkinan jalur = (n-1)! / 2Jumlah jalur 4! /2 = 12 buahDimisalkan titik asal A dan titik akhir

adalah AMaka jumlah jalur dan panjang

lintasannya adalah :

PENYELESAIAN 21. Lintasan 1 = (a b c d e a) atau (a e d c b a) memiliki panjang lintasan = 7 + 7 + 4 + 6 + 9 = 33 2. Lintasan 2 = (a b c e d a) atau (a d e c b a) memiliki panjang lintasan = 7 + 7 + 3 + 6 + 9 = 32 3. Lintasan 3 = (a b d c e a) atau (a e c d b a) memiliki panjang lintasan = 7 + 2 + 4 + 3 + 9 = 25 4. Lintasan 4 = (a b d e c a) atau (a c e d b a) memiliki panjang lintasan = 7 + 2 + 6 + 3 + 5 = 235. Lintasan 5 = (a b e c d a) atau (a d c e b a) memiliki panjang lintasan = 7 + 8 + 3 + 4 + 9 = 31 6. Lintasan 6 = (a b e d c a) atau (a c d e b a) memiliki panjang lintasan = 7 + 8 + 6 + 4 + 5 = 307. Lintasan 7 = (a c b d e a) atau (a e d b c a) memiliki panjang lintasan = 5 + 7 + 2 + 6 + 9 = 29 8. Lintasan 8 = (a c b e d a) atau (a d e b c a) memiliki panjang lintasan = 5 + 7 + 8 + 6 + 9 = 359. Lintasan 9 = (a c d b e a) atau (a e b d c a) memiliki panjang lintasan = 5 + 4 + 2 + 8 + 9 = 28 10. Lintasan 10 = (a d b c e a) atau (a e c b d a) memiliki panjang lintasan = 9 + 2 + 7 + 3 + 9 = 30 11. Lintasan 11 = (a d b e c a) atau (a c e b d a) memiliki panjang lintasan = 9 + 2 + 8 + 3 + 5 = 2712. Lintasan 12 = (a d c b e a) atau (a e b c d a) memiliki panjang lintasan = 9 + 4 + 7 + 8 + 9 = 37

Lintasan yang jaraknya paling pendek adalah : 4 yaitu 23

HASILDari hasil ke-12 enumerasi di atas didapatkan

panjang jalur lintasan paling minimum yaitu 23.

Jumlah enumerasi dari algoritma ini ialah (n - 1)! yang akan memerlukan waktu yang sangat lama untuk mendapatkan panjang lintasan paling minimum jika nilai n bernilai sangat besar.

PENYELESAIAN DENGAN AGDengan contoh yang sama diatas,

tahap2 penyelesaian TSP dengan AG adalah :

1. Inisialisasi2. Evaluasi kromosom3. Seleksi Kromosom4. Pindah Silang (crossover)5. Mutasi

INISIALISASIDipilih secara random ada 6 buah populasi dalam satu generasi, yaitu : Kromosom[1] = [B D E C] Kromosom[2] = [D B E C] Kromosom[3] = [C B D E] Kromosom[4] = [E B C D] Kromosom[5] = [E C B D] Kromosom[6] = [C D E B]

EVALUASI KROMOSOMMenghitung nilai fitness dari tiap kromosom yang telah dibangkitkan pada langkah 1 di atas, dengan menghitung bobot dari setiap lintasan : Fitness[1] = AB+BD+DE+EC+CA = 7 + 2 + 6 + 3 + 5 = 23 Fitness[2] = AD+DB+BE+EC+CA = 9 + 2 + 8 + 3 + 5 = 27 Fitness[3] = AC+CB+BD+DE+EA = 5 + 7 + 2 + 6 + 9 = 29 Fitness[4] = AE+EB+BC+CD+DA = 9 + 8 + 7 + 4 + 9 = 37 Fitness[5] = AE+EC+CB+BD+DA = 9 + 3 + 7 + 2 + 9 = 30 Fitness[6] = AC+CD+DE+EB+BA = 5 + 4 + 6 + 8 + 7 = 30

SELEKSIQ[i] = 1 / Fitness[i]

Q[1] = 1 / 23 = 0,043 Q[2] = 1 / 27 = 0,037 Q[3] = 1 / 29 = 0,034 Q[4] = 1 / 37 = 0,027 Q[5 = 1 / 30 = 0,033 Q[6] = 1 / 30 = 0,033

Total = 0,043 + 0,037 + 0,034 + 0,027 + 0,033 + 0,033 = 0,207  

PROBABILITAS Untuk mencari probabilitas kita menggunakan rumus berikut : P[i] = Q[i] / Total (2) P[1] = 0,043 / 0,207 = 0,208 P[2] = 0,037 / 0,207 = 0,179 P[3] = 0,034 / 0,207 = 0,164 P[4] = 0,027 / 0,207 = 0,130 P[5] = 0,033 / 0,207 = 0,159 P[6] = 0,033 / 0,207 = 0,159

PROBABILITAS KUMULATIFDengan C[1] = 0,028 C[2] = 0,028+0,179 = 0,387 C[3] = 0,387+0,164 = 0,551 C[4] = 0,551+0,130 = 0,681 C[5] = 0,681+0,159 = 0,840 C[6] = 0,840+0,159 = 1

METODE ROULETTE WHEEL

0 - 0,208

0,208- 0,387

0.387 - 0.551

0.551 - 0.681

0,681- 0,84

0,84-1

Bila bilangan random R[i] yang dihasilkan sbb :R[1] = 0,314 R[2] = 0,111, R[3] = 0,342, R[4] = 0,743R[5] = 0,521, R[6] = 0,411Induk yang dipilih denganC[k-1]<R[k]<C[k] menghasilkan :C[2],C[[1],C[3],C[5],C[[4],C[]

POPULASI BARU YANG TERBENTUK Kromosom[1] = [D B E C] Kromosom[2] = [B D E C] Kromosom[3]= [C B D E] Kromosom[4] = [E C B D] Kromosom[5] = [E B C D] Kromosom[6] = [C D E B]

PINDAH SILANG(CROSSOVER)Misal parameter crossover probability (ρc) = 25%. Berarti jika bilangan random dihasilkan <

0.25 maka akan dipilih menjadi induk baru. Hasil 6

bilangan random yang dihasilkan adalah : R[1] = 0,451 , R[2] = 0,211 , R[3] = 0,202 , R[4] = 0,877 , R[5] = 0,771 ,R[6] =

0,131 ,

Kromosom ke-k yang dipilih sebagai induk jika R[k] < ρc. Maka yang akan dijadikan induk adalah kromosom[2], kromosom[3], dan kromosom[6].

PROSES CROSSOVER :Proses crossover : Kromosom[2] = Kromosom[2] >< Kromosom[3] = [B D E C] >< [C B D E] = [B D C E] Kromosom[3] = Kromosom[3] >< Kromosom[6] = [C B D E] >< [C D E B] = [C D E B] Kromosom[6] = Kromosom[6] >< Kromosom[2] = [C D E B] >< [B D E C] = [C D B E]

HASIL CROSSOVERKromosom[1] = [D B E C] diambil dari kromosom induk 1Kromosom[2] = [B D C E] diambil dari hasil crossover

kromosom 2 dan 3Kromosom[3] = [C D E B] diambil dari hasil crossover

kromosom 3 dan 6Kromosom[4] = [E C B D] diambil dari kromosom induk 4Kromosom[5] = [E B C D] diambil dari kromosom induk 5Kromosom[6] = [C D B E] diambil dari hasil crossover

kromosom 6 dan 2

MUTASIPanjang total gen = jumlah gen dalam 1 kromosom *

jumlah Kromosom (3) = 4 * 6 = 24 Misal probabilitas mutasi (ρm) = 20 %, maka jumlah gen yang akan dimutasi adalah = 0,2*24 = 4,8 = 5 .Posisi tersebut didapat dari pembangkitan 5 bilangan acak, mis bilangan acak yang dihasilkan adalah 0,1 maka posisi gen yang akan dimutasi adalah posisi no 3, dimana 0.1 < 3/24 Mis 5 buah posisi gen yang akan dimutasi adalah 3, 7,

10, 20, 24.

PROSES MUTASI

Kromosom[1] = [D B C E] Kromosom[2] = [B D E C] Kromosom[3] = [C E D B] Kromosom[4] = [E C B D] Kromosom[5] = [D B C E] Kromosom[6] = [E D B C]

KESIMPULANKelebihan algoritma genetika dibandingkan metode

pencarian konvensiona pada TSP yaitu 1. Solusi dapat diperoleh kapanpun karena solusi

dihasilkan pada generasi ke berapapun2. Algoritma genetika tidak harus membutuhkan

waktu yang lama karena tidak semua kemungkinan dicoba, tergantung pada kriteria berakhirnya.

3. Algoritma pencarian konvensional dilakukan apabila jumlah n kecil, tapi jika n nya banyak maka akan memakan banyak waktu untuk penyelesaian dibandingkan algoritma genetik

CONTOH PROGRAM TSP DENGAN MATLABAda 10 kota yang dipetakan dalam titik

koordinat sebagai berikut :Kota(x,y) = [1 3;1 7; 3 9; 5 3; 7 1; 9 5; 9 9; 11 1;15

7; 19 3];

GAMBAR

1. INISIALISASIfunction Populasi =

TSPInisialisasiPopulasi(UkPop,JumGen)for i=1:UkPop, [Xval,Ind] = sort(rand(1,JumGen)); Populasi(i,:) = Ind;end

IMPLEMENTASIMisalkan diambil ukuran populasi atau jumlah kromosom dalam populasi = 20 Jumlah gen dalam kromosom/ jumlah kota = 10

>> TSPinisialisasiPopulasi(20,10)

Y = 8 7 3 2 4 5 1 9 6 10 10 3 5 2 6 8 9 4 1 7 1 9 8 10 7 3 6 5 2 4 10 8 1 7 6 5 3 4 2 9 2 8 1 7 6 9 4 3 10 5 2 8 1 3 9 10 4 5 7 6 1 5 8 10 6 3 4 9 2 7 7 3 4 8 10 9 1 5 2 6 5 10 4 2 6 9 1 3 8 7 10 1 4 3 5 2 7 6 9 8 5 3 1 2 6 4 7 10 9 8 4 8 1 10 7 2 3 9 6 5 10 4 6 8 2 5 9 1 7 3 6 1 3 2 4 5 8 9 10 7 6 7 2 8 3 9 10 5 4 1 10 6 3 4 9 2 5 7 1 8 4 7 6 5 10 2 3 1 8 9 2 9 10 5 6 8 4 3 7 1 6 9 1 7 3 4 2 8 5 10 1 9 7 8 10 4 3 5 2 6

2. HITUNG NILAI FITNESSfunction fitness =

TSPEvaluasiIndividu(Kromosom,JumGen,XYkota)

TB = 0;For i=1:JumGen-1, TB = TB + norm(XYkota(Kromosom(ii),:) -

XYkota(Kromosom(i+1),:));end% Jalur harus kembali ke kota asalTB = TB + norm(XYkota(Kromosom(JumGen),:) -

XYkota(Kromosom(1),:));fitness = 1 / TB;

>> TSPEvaluasiIndividu(Y,10,XYkota)

TB =

105.3432

ans =

0.0095

LINEARFITNESSRANKINGfunction LFR =

LinearFitnessRanking(UkPop,Fitness,MaxF,MinF)

[SF,IndF] = sort(Fitness);

% LinearFitness = nilai fitness baru hasil pen-skala-anfor rr=1:UkPop, LFR(IndF(UkPop-rr+1)) =

MaxF-(MaxF-MinF)*((rr-1)/(UkPop-1));end

ROULETTE WHEELfunction Pindex = RouletteWheel(UkPop,LinearFitness);

JumFitness = sum(LinearFitness);KumulatifFitness = 0;RN = rand;ii = 1;while ii <= UkPop, KumulatifFitness = KumulatifFitness + LinearFitness(ii); if (KumulatifFitness/JumFitness) > RN, Pindex = ii; break; end ii = ii + 1;end

PINDAH SILANGfunction Anak = TSPPindahSilang(Bapak,Ibu,JumGen)cp1 = 1 + fix(rand*(JumGen-1))cp2 = 1 + fix(rand*(JumGen-1))while cp2==cp1, cp2 = 1 + fix(rand*(JumGen-1))endif cp1 < cp2, cps = cp1; cpd = cp2;else cps = cp2; cpd = cp1;endAnak(1,cps+1:cpd) = Ibu(cps+1:cpd);Anak(2,cps+1:cpd) = Bapak(cps+1:cpd);C=Anak(1,cps+1:cpd)D=Anak(2,cps+1:cpd)SisaGenbapak = [];SisaGenIbu = [];for ii=1:JumGen, if ~ismember(Bapak(ii),Anak(1,:)), SisaGenbapak = [SisaGenbapak Bapak(ii)]; end if ~ismember(Ibu(ii),Anak(2,:)), SisaGenIbu = [SisaGenIbu Ibu(ii)]; endendSGB=SisaGenbapakSGI=SisaGenIbuAnak(1,cpd+1:JumGen) = SisaGenbapak(1:JumGen-cpd);Anak(1,1:cps) = SisaGenbapak(1+JumGen-cpd:length(SisaGenbapak));Anak(2,cpd+1:JumGen) = SisaGenIbu(1:JumGen-cpd);Anak(2,1:cps) = SisaGenIbu(1+JumGen-cpd:length(SisaGenIbu));

 >> B=TSPInisialisasiPopulasi(1,10) B =2 8 1 3 9 10 4 5 7 6 >> I=TSPInisialisasiPopulasi(1,10) I = 1 5 8 10 6 3 4 9 2 7 cp1 = 8;cps=4cp2 = 4;cpd=8 anak1( 5:8 ) = baris ke 5-8 dari ibu 6 3 4 9sisanya diambil dari Sisa Gen Bapak yang tidak sama dengan anak1 yang terbentuk diatas:2 8 1 10 5 7 Dengan perincian Anak1(9:10)=sisa gen bapak(1:10-8) = 2 8Anak1(1:4)=sisag gen bapak(3:6) = 1 10 5 7 Anak2 = 9 10 4 5Anak2(5:8) = 9 10 4 5Sisa gen ibu = 1 8 6 3 2 7Anak2(9:10)= 1 8Anak2(1:4)= 6 3 2 7 Anak 1 : 1 10 5 7 6 3 4 9 2 8Anak 2 : 6 3 2 7 9 10 4 5 1 8

MUTASIfunction MutKrom = TSPMutasi(Kromosom,JumGen,Pmutasi)

MutKrom = Kromosom;

For i=1:JumGen, if rand < Pmutasi, TM2 = 1 + fix(rand*JumGen); while TM2==i, TM2 = 1 + fix(rand*JumGen); end temp = MutKrom(i); MutKrom(i) = MutKrom(TM2); MutKrom(TM2) = temp; endend

HASIL MUTASI>> TSPMutasi(Y,10,0.005)

ans =

8 7 3 2 4 5 1 9 6 10 10 3 5 2 6 8 9 4 1 7 1 9 8 10 7 3 6 5 2 4 10 8 1 7 6 5 3 4 2 9 2 8 1 7 6 9 4 3 10 5 2 8 1 3 9 10 4 5 7 6 1 5 8 10 6 3 4 9 2 7 7 3 4 8 10 9 1 5 2 6 5 10 4 2 6 9 1 3 8 7 10 1 4 3 5 2 7 6 9 8 5 3 1 2 6 4 7 10 9 8 4 8 1 10 7 2 3 9 6 5 10 4 6 8 2 5 9 1 7 3 6 1 3 2 4 5 8 9 10 7 6 7 2 8 3 9 10 5 4 1 10 6 3 4 9 2 5 7 1 8 4 7 6 5 10 2 3 1 8 9 2 9 10 5 6 8 4 3 7 1 6 9 1 7 3 4 2 8 5 10 1 9 7 8 10 4 3 5 2 6

HASIL OUTPUT

JalurTerbaik =

4 5 8 10 9 6 7 3 2 1

Terima kasih