algoritma genetika untuk distribusi barang

PENENTUAN JARAK TERPENDEK PADA JALUR DISTRIBUSI BARANG

DENGAN MENGGUNAKAN ALGORITMA GENETIKA

MAKALAH ALGORITMA GENETIKA

Disusun Untuk Memenuhi Tugas KD IV Algoritma

Oleh :

1. HARI KUSUMA D. (K1310035)

2. SIGIT RIMBATMOJO (K1310075)

3. HENDRO NUR B. (K1311040)

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS SEBELAS MARET

SURAKARTA

2015

BAB I

PENDAHULUAN

A. Latar Belakang

Permasalahan distribusi barang merupakan permasalahan optimasi

kombinatorial. Jika diberikan sejumlah kota (atau tempat) dan biaya perjalanan dari

satu kota ke kota lain. Deskripsi permasalahannya adalah bagaimana menemukan rute

perjalanan paling murah dari suatu kota dan mengunjungi semua kota lainnya.

Masing-masing kota hanya dikunjungi satu kali dan harus kembali ke kota asal

keberangkatan. Biaya perjalanan bisa berupa jarak, waktu, bahan bakar, dan

sebagainya.

Salah satu metode yang dapat dipakai untuk menyelesaikan permasalahan

distribusi barang ini dengan algoritma yang dapat menyelesaikan persoalan tersebut

dengan relatif cepat sehingga diperoleh solusi yang mendekati solusi optimal yaitu

salah satunya menggunakan algoritma genetika.

Algoritma genetika merupakan algoritma adaptive yang biasa digunakan

untuk memecahkan suatu pencarian nilai dalam sebuah masalah optimasi. Algoritma

ini didasarkan pada proses genetika yang ada dalam makhluk hidup yaitu

perkembangan generasi dalam sebuah populasi yang alami, secara lambat laun

mengikuti seleksi alam dengan prinsip “siapa yang kuat, dia yang bertahan

(survive)”.Sebelum algoritma genetika dapat dijalankan, maka sebuah kode yang

sesuai (representatif) untuk permasalahan harus dirancang. Titik solusi dalam ruang

permasalahan dikodekan (encoding) dalam bentuk kromosom yang terdiri atas

komponen genetika terkecil yaitu gen. Dengan teori evolusi dan teori genetika, di

dalam penerapan algoritma genetika akan melibatkan proses seleksi (selection),

operator pindah silang (crossover) dan mutasi (mutation). Untuk memeriksa hasil

optimasi, dibutuhkan fungsi fitness yang menggambarkan hasil (solusi) yang sudah

dikodekan. Selama algoritma berjalan, induk harus digunakan untuk reproduksi,

pindah silang, dan mutasi untuk menciptakan keturunan. Proses terakhir adalah

mengambil makna dari hasil kromosom terbaik (decoding) untuk menjawab

permasalahan. Jika algoritma genetika didesain secara baik, populasi akan mengalami

konvergensi dan akan didapatkan sebuah solusi yang mendekati optimum.

Makalah ini membahas bagaimana algoritma genetika menentukan jarak

terpendek pada jalur distribusi barang dengan menggunakan metode Order Based

Crossover sebagai teknik rekombinasi dan metode swapping mutation sebagai teknik

mutasi.Untuk mengetahui bagaimana penerapan algoritma genetika dalam

menyelesaikan persoalan distribusi barang ini, dibuatkan sebuah visualisasi sederhana

dengan menggunakan Java Script.

B. Pembatasan Masalah

Pembatasan pada masalah ini dibatasi pada rute perjalanan pada persoalan

distribusi barang dari lima kota dari graf yang tak berarah, berbobot positif, dan

disajikan dalam matriks terhubung langsung. Serta penyelesaian persoalan TSP

menggunakan metode seleksi dengan mesin roulette, metode Order Based Crossover

sebagai teknik pindah silang, dan metode swapping mutation sebagai teknik mutasi.

C. Rumusan Masalah

Berdasarkan uraian di atas maka rumusan masalah dalam makalah ini

adalah:

1. Bagaimana langkah-langkah dalam algoritma genetika?

2. Bagaimana penerapan algoritma genetika untukmenentukan jarak terpendek pada

jalur distribusi barang?

D. Tujuan Masalah

Berdasarkan rumusan masalah di atas, maka tujuan penulisan makalah ini

antara lain:

1. Menjelaskan langkah-langkah dalam algoritma genetika.

2. Menerapkan algoritma genetika untuk menentukan jarak terpendek pada jalur

distribusi barang.

BAB II

PEMBAHASAN MASALAH

A. Algoritma Genetika

Algoritma genetika adalah algoritma pencarian heuristik yang didasarkan atas

mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari

kromosom antar individu organisme. Algoritma ini didasari oleh konsep evolusi

biologi, dan dapat memberikan solusi alternatif atas suatu masalah yang hendak

diselesaikan. Algoritma genetika menawarkan suatu solusi pemecahan masalah yang

terbaik, dengan memanfaatkan metode seleksi, crossover, dan mutasi. Algoritma

genetika adalah suatu bentuk teknik pencarian secara stochastic, berdasarkan

mekanisme yang ada pada seleksi alam dan genetik secara natural. Algoritma

genetika telah banyak diaplikasikan untuk penyelesaian masalah dan pemodelan

dalam bidang teknologi seperti optimasi, pemrograman otomatis dan machine

learning. Pada implementasi program algoritma genetika dapat digunakan untuk

mencari jalan terpendek bebas hambatan. Berbeda dengan teknik pencarian

konvensional, tahap awal pencarian dalam algoritma genetika dimulai dari himpunan

penyelesaian acak (random) yang disebut populasi. Populasi ini terdiri dari

kromosom-kromosom. Setiap kromosom merupakan gambaran solusi atas pemecahan

masalah. Populasi yang telah dipilih tersebut akan menghasilkan keturunan baru yang

sifatnya diharapkan lebih baik dari populasi sebelumnya. Populasi yang baik sifatnya

akan memiliki peluang untuk terus dikembangkan agar menghasilkan keturunan

populasi yang lebih baik selanjutnya. Dengan demikian, solusi terbaik yang

diinginkan dapat dicapai dengan terus mengulang proses pencarian keturunan.

Dalam proses tersebut, sebelum algoritma genetika dijalankan didefinisikan

suatu fungsi fitness yang menyatakan tingkat keberhasilan sebuah populasi. Dengan

melakukan perhitungan berdasarkan fungsi fitness, akan dapat ditentukan populasi

yang akan dipertahankan untuk menghasilkan generasi selanjutnya. Proses ini biasa

disebut sebagai proses seleksi. Proses ini merupakan salah satu tahap yang dirangkai

dalam proses yang iteratif.

Proses lain yang termasuk pada rangkaian iterasi ini yaitu crossover. Pada

proses ini, dilakukan persilangan atau perkawinan antar kromosom yang berada

dalam satu generasi. Dengan demikian, kromosom yang terdapat pada populasi

selanjutnya mewarisi sifat kedua induknya. Kromosom ini diharapkan bersifat lebih

baik dibanding dengan generasi sebelumnya. Sedangkan proses mutasi merupakan

proses diubahnya satu atau lebih nilai gen kromosom dalam satu populasi. Nilai gen

tersebut akan digantikan dengan suatu nilai yang dipilih secara acak. Pada tahap ini,

terdapat kemungkinan perubahan sifat di luar sifat induk pada keturunan yang

dihasilkan.

Siklus dari Algoritma Genetika pertama kali dikenalkan oleh David Goldberg,

dimana gambaran siklus tersebut dapat dilihat pada gambar 1.

Populasi Evaluasi Seleksi

Awal Fitness Individu

Populasi Reproduksi:

Baru Cross-Over

Dan Mutasi

Gambar 1 Siklus Algoritma Genetika

a. Pengertian Individu

Individu menyatakan salah satu solusi yang mungkin. Individu bisa

dikatakan sama dengan kromosom, yang merupakan kumpulan gen. Gen ini bisa

biner, float, dan kombinatorial.

Beberapa definisi penting yang perlu diperhatikan dalam mendefinisikan

individu untuk membangun penyelesaian masalah dengan algoritma genetika

adalah sebagai berikut:

1) Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang

membentuk suatu arti tertentu dalam satu kesatuan gen yang

dinamakan kromosom. Dalam algoritma genetika, gen ini bisa

berupa nilai biner, float, integer, karakter, maupun kombinatorial.

2) Allele, nilai dari gen.

3) Kromosom, gabungan gen-gen yang membentuk nilai tertentu.

4) Individu, menyatakan satu nilai atau keadaan yang menyatakan

salah satu solusi yang mungkin dari permasalahan yang diangkat.

5) Populasi, merupakan sekumpulan individu yang akan diproses

bersama dalam satu siklus proses evolusi.

6) Generasi, menyatakan satu siklus proses evolusi atau satu iterasi di

dalam algoritma genetika.

b. Teknik Pengkodean

Teknik pengkodean adalah bagaimana mengkodekan gen dari

kromosom, dimana gen merupakan bagian dari kromosom. Satu gen biasanya

akan mewakili satu variabel.

Proses pengkodean untuk setiap permasalahan berbeda-beda karena

tidak semua teknik pengkodean cocok untuk setiap permasalahan. Proses

pengkodean menghasilkan string yang kemudian disebut kromosom. String

terdiri dari sekumpulan bit. Bit ini dikenal sebagai gen. Jadi satu kromosom

terdiri dari sejumlah gen. Beberapa teknik pengkodean antara lain adalah binary

encoding, permutation encoding, value encoding, serta tree encoding. Teknik

pengkodean yang digunakan pada permasalahan distribusi barang adalah

permutation encoding. Pada permutation encoding, kromosom-kromosom adalah

kumpulan angka yang mewakili posisi dalam sebuah rangkaian. Pada pencarian

jalur distribusi, kromosom mewakili urutan kota sebagai jalur distribusi. Jadi

apabila satu kromosom berbentuk sebagai berikut P1 = (X1, X2, X3, …, Xn)

berarti distribusi barang bergerak dari kota bernomor X1 ke X2, dan seterusnya

hingga ke kota Xn.

c. Membangkitkan Populasi Awal Dengan Teknik Random Permutasi

Inti dari cara ini adalah melibatkan pembangkitan gen secara random

dengan aturan tambahan dimana urutan gen diperhatikan dan tidak ada gen yang

diulang sesuai dengan representasi kromosom yang digunakan yakni representasi

permutasi.

Source Code :

boolean[] sudahAda = new boolean[x + 1];

Random rnd = new Random();

for (int j = 0; j <= x; j++) {

sudahAda[j] = false;

}

for (int i = 0; i < x; i++) {

int tmp;

do {

tmp = rnd.nextInt(x) + 1; //1 s/d x

} while (sudahAda[tmp]);

kromosom[i] = tmp;

sudahAda[tmp] = true;

}

d. Nilai Fitness

Nilai fitness adalah nilai yang menyatakan baik tidaknya suatu solusi

(individu). Nilai fitness ini yang dijadikan acuan dalam mencapai nilai optimal

dalam algoritma genetika. Algoritma genetika bertujuan mencari individu dengan

nilai fitness yang paling tinggi.

Dalam menentukan jalur terpendek, maka nilai fitnessnya adalah inversi

dari total jarak dari jalur yang didapatkan. Cara melakukan inversi

bisamenggunakan rumus 1/x atau 100000 – x, dimana x adalah total jarak dari

jalur yang didapatkan.

Source code mengurutkan nilai fitness :

Individu tmpIdv = new Individu(nGen);

for (int i=0; i<((nIdv+nCr+nMt)-1); i++)

for (int j=i+1; j<(nIdv+nCr+nMt); j++) 30

{

if (pop[i].fitness<pop[j].fitness)

{

tmpIdv = pop[i];

pop[i] = pop[j];

pop[j] = tmpIdv;

}

}

e. Seleksi Dengan Mesin Roulette

Seleksi digunakan untuk memilih individu-individu mana saja yang

akan dipilih untuk proses kawin silang dan mutasi. Seleksi digunakan untuk

mendapatkan calon induk yang baik. “Induk yang baik akan menghasilkan

keturunan yang baik”. Semakin tinggi nilai fitness suatu individu semakin besar

kemungkinannya untuk terpilih.

Metode seleksi dengan mesin roulette ini merupakan metode yang

paling sederhana dan sering dikenal dengan nama stochastic sampling with

replacement. Cara kerja metode ini adalah sebagai berikut:

1) Menghitung nilai fitness dari masing-masing individu (fi,, dimana i

adalah individu ke-1 s/d ke-n).

2) Menghitung total fitness semua individu.

3) Menghitung probabilitas masing-masing individu.

4) Dari probabilitas tersebut, menghitung nilai kumulatif.

5) Membangkitkan bilangan random antara 0 sampai 1.

6) Dari bilangan random yang dihasilkan, ditentukan individu mana

yang terpilih dalam proses seleksi.

f. Pindah Silang (Crossover) Untuk Representasi Kromosom Permutasi

Dengan Metode Order Based Crossover

Pindah silang atau proses rekombinasi atau yang lebih dikenal dengan

nama proses crossover adalah menyilangkan dua kromosom sehingga

membentuk kromosom baru yang harapannya lebih baik daripada induknya.

Tidak semua kromosom pada suatu populasi akan mengalami proses

rekombinasi. Kemungkinan suatu kromosom mengalami proses rekombinasi

didasarkan pada probabilitas crossover (Pc) yang telah ditentukan terlebih

dahulu. Probabilitas crossover menyatakan peluang suatu kromosom akan

mengalami crossover.

Source code proses cross over:

for (int itr=1; itr<=nItr; itr++)

{

//CROSSOVER

for (int idCr=1; idCr<=nCr; idCr++)

{ 25

int idChd = (nIdv+idCr)-1; //index kromosom pada

populasi yang akan dijadikan child

//select parent

int p1,p2;

p1 = rnd.nextInt(nIdv); // 1 s/d nIdv

do {

p2 = rnd.nextInt(nIdv); // 1 s/d nIdv

} while (p2==p1);

str += " Cross"+idCr+": "+(p1+1)+" dengan "+(p2+1);

//sudahAda: variabel untuk mencegah redundancy pemilihan

gen

boolean[] sudahAda = new boolean[nGen+1];

for (int i=0; i<=nGen; i++)

{ sudahAda[i] = false; }

int cP = nGen / 2; //cP: cut Point

int idx = 0;

//copy dari P1 (sebelum cut Point)

for (int i=0; i<cP; i++)

{

int val = pop[p1].kromosom[i];

pop[idChd].kromosom[idx] = val;

idx++; sudahAda[val]=true;

}

//copy dari P2 (sebelum cut Point)

for (int i=0; i<cP; i++)

{


if (sudahAda[val]==false)

{



} 26

}

if (idx<nGen)

{

//copy dari P1 (setelah cut Point)

for (int i=cP; i<nGen; i++)

{



{



}

}

}

if (idx<nGen)

{

//copy dari P2 (setelah cut Point)

for (int i=cP; i<nGen; i++)

{



{



}

}

}

}

Pada gambar 2 diilustrasikan diagram alir penggunaan probabilitas crossover

pada proses crossover.

Induk 1Induk 2

p = random[0,1]

p < probCO

ya tidak

Cross Over

Gambar 2 Diagram Alir Proses Crossover

Operator crossover ini bergantung pada representasi kromosom.

Pada representasi kromosom permutasi dapat digunakan metode Order

Crossover, dimana satu bagian kromosom dipertukarkan dengan tetap menjaga

urutan kota yang bukan bagian dari kromosom tersebut. Kromosom yang

dijadikan induk dipilih secara acak dan jumlah kromosom yang dicrossover

dipengaruhi oleh probabilitas crossover (Pc).

g. Mutasi Dengan Teknik Swapping Mutation

Mutasi berperan untuk menggantikan gen yang hilang dari populasi

akibat proses seleksi yang memungkinkan munculnya kembali gen yang tidak

muncul pada inisialisasi populasi. Probabilitas mutasi (Pm) didefinisikan sebagai

presentasi dari jumlah total gen pada populasi yang mengalami mutasi.

Probabilitas mutasi mengendalikan banyaknya gen baru yang akan dimunculkan

untuk dievaluasi. Jika peluang mutasi terlalu kecil, banyak gen yang mungkin

berguna tidak pernah dievaluasi. Tetapi bila peluang mutasi ini terlalu besar,

maka akan terlalu banyak gangguan acak, sehingga anak akan kehilangan

kemiripan dari induknya, dan juga algoritma kehilangan kemampuan untuk

belajar dari histori pencarian.

Proses mutasi menggunakan metode swapping mutation dilakukan

dengan cara menukar gen yang dipilih secara acak dengan gen sesudahnya. Jika

gen tersebut berada di akhir kromosom, maka ditukar dengan gen yang pertama.

Sourch Code mutasi exchange point:

str = "";

int mP1,mP2,idxM; //mP1,m2: mutation Point 1 & 2, idxM:

27

kromosom yang akan dimutasi

mP1 = rnd.nextInt(nGen); // 0 s/d nGen-1

do {

mP2 = rnd.nextInt(nGen); // 0 s/d nGen-1

} while (mP2==mP1);

//sudahPilih: variabel untuk mencegah redundancy pemilihan

kromosom yang akan dimutasi

boolean[] sudahPilih = new boolean[nIdv+1];

for (int i=0; i<=nIdv; i++)

{ sudahPilih[i] = false; }

for (int idMt=1; idMt<=nMt; idMt++)

{

//pilih kromosom yang akan dimutasi

do {

idxM = rnd.nextInt(nIdv); // 0 s/d nIdv-1

} while (sudahPilih[idxM]);

sudahPilih[idxM] = true;

int idChd = (nIdv+nCr+idMt)-1; //index kromosom pada

populasi yang akan dijadikan child (hasil mutasi)

pop[idChd].kromosom[mP1] =

pop[idxM].kromosom[mP2];

pop[idChd].kromosom[mP2] =

pop[idxM].kromosom[mP1];

str += " Mutation"+idMt+": "+(idxM+1)+" pada posisi

"+(mP1+1)+" & "+(mP2+1);

B. Pembahasan Masalah

1. Langkah-Langkah Algoritma Genetika

Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan

langkah-langkah sebagai berikut:

a. Membangkitkan populasi awal secara random.

b. Membentuk generasi baru dengan menggunakan tiga operasi yaitu:

operasi reproduksi, operasi crossover (persilangan), dan operasi mutasi

secara berulang-ulang sehingga diperoleh kromosom yang cukup untuk

membentuk generasi baru sebagai representasi dari solusi baru.

c. Evolusi solusi yang akan mengevaluasi setiap populasi dengan

menghitung nilai fitness setiap kromosom hingga kriteria berhenti

terpenuhi. Bila kriteria berhenti belum terpenuhi maka akan dibentuk

lagi generasi baru dengan mengulang langkah 2. Beberapa kriteria

berhenti yang sering digunakan antara lain:

Berhenti pada generasi tertentu

Berhenti setelah dalam beberapa generasi berturut-turut didapatkan

nilai fitness tertinggi/terendah (tergantung persoalan) yang tidak

berubah.

Berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness

yang lebih tinggi/rendah.

2. Contoh Penerapan Algoritma Genetika Pada Persoalan Menentukan Jarak

Terpendek Dari Jalur Distribusi Barang

Penerapan algoritma genetika pada persoalan menentukan jarak terpendek

dari jalur distribusi barang akan lebih jelas jika diterapkan dalam contoh kasus

berikut.

Dimisalkan jalur distribusi yang akan ditempuh adalah Kediri – Malang – Semarang

–Rembang – Solo. Kemudian dilakukan teknik encoding dengan menginisialisasi

kota-kota tersebut yaitu Kediri(X0) – Malang(X1) – Semarang(X2) – Rembang(X3) –

Solo(X4). Didapatkan gennya adalah Malang(X1) – Semarang(X2) – Rembang(X3) –

Solo(X4), Kediri(X0) tidak dimasukkan kedalam gen karena asumsinya adalah bahwa

kota asal adalah juga merupakan kota akhir tujuan distribusi barang. Jarak antar kota

diperlihatkan pada tabel di bawah ini:

X0 X1 X2 X3 X4

X0 0 7 5 9 9

X1 7 0 7 2 8

X2 5 7 0 4 3

X3 9 2 4 0 6

X4 9 8 3 6 0

Persoalan tersebut akan diselesaikan dengan menggunakan algoritma genetika.

Kriteria berhenti ditentukan terlebih dahulu yaitu apabila setelah dalam generasi

berturut-turut diperoleh nilai fitness yang tertinggi tidak berubah. Pemilihan nilai

fitness yang tertinggi sebagai syarat karena nilai tersebut yang mempresentasikan

jarak terpendek yang dicari pada persoalan ini.

Ada 4 kota yang akan menjadi gen dalam kromosom yaitu kota-kota selain kota asal.

a. Inisialisasi

Misalkan kita menggunakan 6 buah populasi dalam satu generasi yang dibangkitkan

menggunakan random permutasi, yaitu

Kromosom[1] = [X1 X3 X4X2]

Kromosom[2] = [X3X1X4X2]

Kromosom[3] = [X2 X1X3X4]

Kromosom[4] = [X4 X1X2X3]



b. Evaluasi kromosom

Kita akan menghitung jarak total (X)dari tiapkromosom yang telah dibangkitkan:

X[1] = X0X1+X1X3 +X3X4 +X4X2+X2X0 = 7 + 2 + 6 + 3 + 5 = 23

X[2] = X0X3 +X3X1+X1X4 +X4X2+X2X0 = 9 + 2 + 8 + 3 + 5 = 27

X[3] = X0X2+X2X1+X1X3 +X3X4 +X4X0 = 5 + 7 + 2 + 6 + 9 = 29

X[4] = X0X4 + X4X1+X1X2+X2X3 +X3X0 = 9 + 8 + 7 + 4 + 9 = 37

X[5] = X0X4 +X4X2+X2X1+X1X3 +X3X0 = 9 + 3 + 7 + 2 + 9 = 30

X[6] = X0X2+X2X3 +X3X4 + X4X1+X1X0 = 5 + 4 + 6 + 8 + 7 = 30

c. Seleksi kromosom

Oleh karena persoalan pada penentuan jarak terpendek yang diinginkan yaitu

kromosom dengan jarak total yang lebih kecil akan mempunyai probabilitas untuk

terpilih kembali lebih besarmaka digunakan nilai fitness berupa inversi dari total jarak

dari jalur yang didapatkan.

Fitness[i] = 1

X [ i ]

Fitness[1] = 1

23 = 0,043

Fitness[2] = 1

27 = 0,037

Fitness[3] = 1

29 = 0,034

Fitness[4] = 1

37 = 0,027

Fitness[5] = 1

30 = 0,033

Fitness[6] = 1

30 = 0,033

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

Source Code menghitung fitness :

for (int idK=0; idK<(nIdv+nCr+nMt); idK++)

{

int idA, idB, minAdd, minTotal;

Date wkt = new

SimpleDateFormat("HH:mm").parse("07:00");

minTotal = 0; minAdd = 0; idA = 0;

String wktAkhir = "";

for (int i=0; i<nGen; i++)

{

if (i==0)

{

idA = pop[idK].kromosom[i]-1;

minAdd = costMatrix.awal[idA] +

spot.waktu[idA];

}

else if (i>0)

{

idB = pop[idK].kromosom[i]-1;

minAdd = costMatrix.mtr[idA][idB] +

spot.waktu[idB];

idA = idB;

}

minTotal += minAdd;

wkt.setTime(wkt.getTime()+ minAdd *60000);

wktAkhir = spot.tutup[idA];

}

Date jamAkhir = new

SimpleDateFormat("HH:mm").parse(wktAkhir);

long selisih = ((wkt.getTime()/60000) -

(jamAkhir.getTime()/60000));

int penalti = 0;

if (selisih>0) { penalti = (int) selisih;

minTotal += penalti; }

pop[idK].fitness = 1/(double) minTotal;

Untuk mencari probabilitas kita menggunakan rumus berikut:

P[i] = Fitness [ i ]

Total

P[1] = 0,0430,207

= 0,208

P[2] = 0,0370,207

= 0,179

P[3] = 0,0340,207

= 0,164

P[4] = 0,0270,207

= 0,130

P[5] = 0,0330,207

= 0,159

P[6] = 0,0330,207

= 0,159

Dari probabilitas di atas dapat terlihat bahwa kromosom ke-1 mempunyai fitness

paling besar maka probabilitas untuk terpilih pada generasi selanjutnya lebih besar

dari kromosom lainnya.

Untuk proses seleksi kita menggunakan mesin roulette, untuk itu terlebih dahulu

mencari nilai kumulatif dari probabilitasnya.

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

Proses mesin rouletteadalah membangkitkan nilai acak R antara 0-1. Jika R[k]<C[k]

maka kromosom ke-k yang dipilih sebagai induk, selain itu pilih kromosom ke-k

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

roulettesebanyak jumlah kromosom yaitu 6 kali (membangkitkan bilangan acak R).

R[1] = 0,314

R[2] = 0,111

R[3] = 0,342

R[4] = 0,743

R[5] = 0,521

R[6] = 0,411

Setelah itu, populasi baru akan terbentuk yaitu:

Kromosom[1] = [2] = [X3X1X4 X2]

Kromosom[2] = [1] = [X1X3 X4 X2]

Kromosom[3] = [3] = [X2X1X3X4]



Kromosom[6] = [6] = [X2X3 X4X1]

Source Code untuk menampilkan hasil populasi:

model3.setColumnCount(nGen+2); //set col count

model3.setNumRows(nIdv+nCr+nMt+1); //set row count

DefaultTableCellRenderer centerRenderer = new

DefaultTableCellRenderer();

centerRenderer.setHorizontalAlignment(SwingConstants.CENTER)

;

for (int i=0; i<=nGen; i++)

{

tbPop1.getColumnModel().getColumn(i).setPreferredWidth(30);

tbPop1.getColumnModel().getColumn(i).setCellRenderer(centerR

enderer);

}

tbPop1.getColumnModel().getColumn(nGen+1).setPreferredWidth(

80);

tbPop1.getColumnModel().getColumn(nGen+1).setCellRenderer(ce

nterRenderer);

for (int i=0; i<nGen; i++)

{ model3.setValueAt(i+1, 0, i+1); }

model3.setValueAt("Fitness", 0, nGen+1);

for (int i=0; i<nIdv; i++)

{ model3.setValueAt("P"+(i+1), i+1, 0); }

for (int i=0; i<(nCr+nMt); i++)

{ model3.setValueAt("C"+(i+1), (nIdv+i+1), 0); }

for (int i=1; i<=nIdv+nCr+nMt; i++)

{

for (int j=1; j<=nGen; j++)

{ model3.setValueAt(pop[i-1].kromosom[j-1], i, j);

}

model3.setValueAt(String.format("%.5f", pop[i-

1].fitness), i, nGen+1);

}

d. Crossover (kawin silang)

Kawin silang pada persoalan penentuan jarak terpendek pada jalur distribusi barang

ini diimplementasikan dengan metode order crossover.

Misal kita tentukan Pc = 50%, maka diharapkan dalam 1 generasi ada 50% (3

kromosom) dari populasi yang mengalami crossover.

Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi yaitu 6 kali.

R[1] = 0,451

R[2] = 0,211

R[3] = 0,302

R[4] = 0,877

R[5] = 0,771

R[6] = 0,131

Kromosom ke-k yang dipilih sebagai induk jika R[k] <Pc, maka yang akan dijadikan

induk adalah kromosom[2], kromosom[3], kromosom[6].

Setelah melakukan pemilihan induk, proses selanjutnya adalah menentukan posisi

crossover. Hal tersebut dilakukan dengan membangkitkan bilangan acak antara 1

sampai dengan panjang kromosom-1. Dalam kasus TSP ini bilangan acaknya adalah

antara 1-3. Misal diperoleh bilangan acaknya 1, maka gen ke-1 pada kromosom induk

pertama akan diambil kemudian ditukar dengan gen pada kromosom induk kedua

yang belum ada pada induk pertama dengan tetap memperhatikan urutannya.

Bilangan acak untuk 3 kromosom induk yang akan di-crossover:

C[2] = 2

C[3] = 1

C[6] = 2

Proses crossover :

Kromosom[2] = Kromosom[2] ><Kromosom[3]

= [X1X3X4 X2] >< [X2X1X3X4]

= [X1X3 X2X4]


= [X2X1X3X4] >< [X2X3X4X1]

= [X2X3X4X1]


= [X2X3X4X1] >< [X1X3X4 X2]

= [X2X3X1X4]

Populasi setelah di-crossover :

Kromosom[1] = [X3X1X4 X2]

Kromosom[2] = [X1X3 X2X4]


Kromosom[4] = [X4 X2X1 X3]

Kromosom[5] = [X4X1 X2X3]


e. Mutasi

Pada kasus penentuan jarak terpendek pada jalur distribusi barang ini skema mutasi

yang digunakan adalah swapping mutation. Jumlah kromosom yang mengalami

mutasi dalam satu populasi ditentukan oleh parameter mutation rate(Pm).

Pertama kita hitung dulu panjang total gen yang ada pada satu populasi:

Panjang total gen = jumlah gen dalam 1 kromosom * jumlah kromosom

= 4 * 6

= 24

Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan membangkitkan

bilangan acak antara 1 – panjang total gen yaitu 1- 24. Misal kita tentukan Pm = 20 %.

Maka jumlah gen yang akan dimutasi adalah = 0,2*24

= 4,8

= 5

5 buah posisi gen yang akan dimutasi, setelah diacak adalah posisi 3, 7, 10, 20, 24.

Proses mutasi :







Proses algoritma genetik untuk 1 generasi telah selesai. Maka nilai fitness setelah 1

generasi adalah:

Fitness[1] = 1/(X0X3 +X3X1+X1X2+X2X4 +X4X0) = 1/(9 + 2 + 7 + 3 + 9) = 1/30 =

0,033

Fitness[2] = 1/(X0X1+X1X3 +X3X4 +X4X2+X2X0) = 1/(7 + 2 + 6 + 3 + 5) = 1/23 =

0,043

Fitness[3] = 1/(X0X2+X2X4 +X4X3 +X3X1+X1X0) = 1/(5 + 3 + 6 + 2 + 7) = 1/23 =

0,043


0,033


0,033

Fitness[6] = 1/(X0X4+ X4X3 +X3X1+X1X2+X2X0) = 1/(9 + 6 + 2 + 7 + 5) = 1/29 =

0,034

Sebelumnya telah ditentukan kriteria berhenti yaitu bila setelah dalam beberapa

generasi berturut-turut diperoleh nilai fitness yang tertinggi tidah berubah. Pada 1

generasi telah terlihat bahwa terdapat nilai fitness tertinggi yang tidak berubah.

Apabila perhitungan dilanjutkan hingga ke generasi ke-N maka disimpulkan bahwa

nilai fitness yang terendah tetap tidak akan berubah. Walaupun perhitungan cukup

dijabarkan hingga generasi ke-1 saja namun solusi yang mendekati optimal telah

didapatkan. Oleh karena itu, terbukti bahwa algoritma genetika dapat menyelesaikan

persoalan menentukan jarak terpendek pada jalur distribusi barang.

BAB III

Kesimpulan

Berdasarkan perancangan dan implementasi Aplikasi Optimasi Rute

Pengiriman Barang Menggunakan Algoritma Genetika, maka didapatkan kesimpulan

sebagai berikut:

1. Penentuan jumlah individu dan banyaknya iterasi berpengaruh kepada hasil

fitness.

2. Aplikasi Optimasi Rute Pengiriman Barang Menggunakan Algoritma

Genetika telah dibuat sesuai dengan perancangan dan dapat digunakan dalam

merekomendasikan rute terdekat dalam pengiriman barang

Daftar Pustaka

Lukas, S., Anwar, T., Yuliani, W., 2005, Penerapan Algoritma Genetika untuk

Traveling Salesmen Problem dengan Menggunakan Metode Order

Crossover dan Insertion Mutation, Seminar Nasional Aplikasi

Teknologi Informasi.

http://repository.usu.ac.id/bitstream/123456789/21086/2/Reference.p

df di akses pada 20 Mei 2015 pukul 19.30

Lumbantobing, H., Hidayatno, A., Darjat, 2011, Penerapan Algoritma Genetika pada

Perencanaan Lintas Kendaraan, Undergraduate Thesis, Universitas

Diponegoro.

http://eprints.undip.ac.id/view/divisions/sch=5fecs/2011.html di

akses pada 20 Mei 2015 pukul 20.30

Fitrah, A., Zaky, A., Fitrasani, 2006, Penerapan Algoritma Genetika pada Persoalan

Pedagang Keliling (TSP), Sekolah Tinggi Elektro Dan Informatika

ITB.

http://www.researchgate.net/profile/Dewa_Adi/publication/23595719

4_PENENTUAN_JARAK_TERPENDEK_PADA_JALUR_DISTRI

BUSI_BARANG_DI_PULAU_JAWA_DENGAN_MENGGUNAK

AN_ALGORITMA_GENETIKA/links/

00b7d514c220dc207b000000.pdf di akses pada 20 Mei 2015 pukul

21.00

http://www.academia.edu/9543928/Algoritma_Genetika di akses pada 20 Mei 2015

http://www.academia.edu/9543928/Algoritma_Genetika

http://www.researchgate.net/profile/Dewa_Adi/publication/235957194_PENENTUAN_JARAK_TERPENDEK_PADA_JALUR_DISTRIBUSI_BARANG_DI_PULAU_JAWA_DENGAN_MENGGUNAKAN_ALGORITMA_GENETIKA/links/00b7d514c220dc207b000000.pdf



http://eprints.undip.ac.id/view/divisions/sch=5fecs/2011.html

http://repository.usu.ac.id/bitstream/123456789/21086/2/Reference.pdf

http://repository.usu.ac.id/bitstream/123456789/21086/2/Reference.pdf

http://www.researchgate.net/profile/Dewa_Adi/publications di akses pada 20 Mei

2015 pukul 20.00

http://www.researchgate.net/profile/Dewa_Adi/publications

algoritma genetika untuk distribusi barang

Documents