optimasi fungsi sederhana dengan algoritma genetika

PENERAPAN ALGORITMA GENETIKA UNTUK OPTIMASI

FUNGSI LINIER

OLEH :

SUPRIYANTO

G651090191

Dosen :

Dr. Ir. Yandra Arkeman, M.Sc

MEI 2010

DEPARTEMEN ILMU KOMPUTER

SEKOLAH PASCASARJANA

INSTITUT PERTANIAN BOGOR

BOGOR

Kepunyaan Allah-lah apa yang di langit dan apa yang di bumi, dan adalah (pengetahuan)

Allah Maha meliputi segala sesuatu. (QS 4 : 126)

Dan sesungguhnya telah Kami pilih mereka dengan pengetahuan (Kami) atas bangsa-bangsa

(QS 44 : 32)

i

KATA PENGANTAR

Puji syukur kehadirat Allah SWT yang dengan Rahmat dan Karunianya, maka penulis dapat

menyelesaikan tugas Algoritma Genetika. Topik yang diangkat pada tulisan ini adalah

tentang optimasi fungsi linier dengan menggunakan Algoritma Genetika.

Patut disadari bahwa dalam penulisan makalah ini tidak lepas dari kesalahan dan kekurangan.

Penulis mengharapkan masukan dan kritikan demi perbaikan di kemudian hari.

Bogor, Mei 2010

Penulis

ii

DAFTAR ISI

Halaman

BAB I. PENDAHULUAN ...................................................................................................... 1

A. Latar Belakang ........................................................................................................ 1

B. Perumusan Masalah ................................................................................................ 2

C. Tujuan ..................................................................................................................... 2

BAB II. TINJUAN PUSTAKA ................................................................................................ 3

A. Terminologi Knowledge ......................................................................................... 3

B. Komponen-Komponen Utama Algoritme Genetika ............................................... 5

1. Teknik Pengkodean ............................................................................................ 5

2. Membangkitkan Populasi Awal ......................................................................... 5

3. Seleksi ................................................................................................................ 6

4. Crossover ............................................................................................................ 7

5. Mutasi ................................................................................................................. 8

2. Persamaan Linier................................................................................................... 10

BAB III. HASIL DAN PEMBAHASAN ................................................................................ 11

A. Perancangan Aplikasi ............................................................................................ 11

B. Perangkat Lunak ................................................................................................... 12

C. Mekanisme Algoritma Genetika Untuk Optimasi Fungsi Linier .......................... 12

1. Pembentukan Kromosom ................................................................................. 12

2. Inisiasi Masalah dan Pembantukan Kromosom ............................................... 13

3. Seleksi Kromosom ........................................................................................... 14

4. Proses Penyilangan ........................................................................................... 15

5. Proses Mutasi ................................................................................................... 16

6. Proses Seleksi ................................................................................................... 17

iii

D. Hasil Running Program ......................................................................................... 17

BAB IV. KESIMPULAN ........................................................................................................ 18

iv

DAFTAR TABEL

Tabel 3.1. Inisiasi Populasi Awal ............................................................................................ 13

Tabel 3.2. Kromosom Hasil Penyilangan Pada Generasi ke-200 ............................................ 16

Tabel 3.3. Kromosom Hasil Mutasi Pada Generasi ke-200 ..................................................... 16

v

DAFTAR GAMBAR

Gambar 2.1. Diagram alir proses crossover ................................................................................ 8

Gambar 2.2. Diagram alir proses mutasi .................................................................................... 9

Gambar 2.3. Proses dan hasil mutasi ........................................................................................ 10

Gambar 2.1. Diagram Alir Rancangan Aplikasi Algoritma Genetika Untuk Optimisasi

Persamaan Linier ................................................................................................. 11

1

BAB I. PENDAHULUAN

A. Latar Belakang

Algoritma Genetika adalah salah satu pendekatan untuk menentukan global

optimum yang didasari oleh Teori Darwin. Secara garis besar langkah dalam

prosedur ini dimulai dengan menetapkan suatu set solusi potensial dan

melakukan perubahan dengan beberapa iterasi dengan algoritma genetika

untuk mencapat solusi terbaik. Set solusi potensial ini ditetapkan diawal dan

disebut dengan kromosom. Kromosom ini dibentuk secara random berupa

susunan angka binary yang di-generate dan dipilih. Keseluruhan set dari

kromosom yang diobservasi mewakili suatu populasi.

Kemudian, kromosom-kromosom tersebut akan berevolusi dalam beberapa

tahap iterasi yang disebut dengan generasi. Generasi baru (offsprings) di-

generate dengan teknik kawin silang (crossover) dan mutasi (mutation). Cross

over meliputi pemecahan (splitting) dua kromosom dan kemudian

mengkombinasikan setengah bagian dari masing-masing kromosom dengan

pasangan-pasangan lainnya. Sedangkan mutasi meliputi penggantian

(flipping) satu bit (bagian) dari kromosom dengan satu bagian lain dari

kromo-som lain yang menjadi pasangannya. Kromosom-kromosom ini

selanjutnya berevolusi dengan suatu kriteria kesesuaian (fitness) yang

ditetapkan dan hasil terbaik akan dipilih sementara yang lainnya diabaikan.

Selanjutnya, proses dilakukan berulang-ulang sampai dengan suatu

kromosom yang mempunyai kesesuaian terbaik (best fitness) akan diambil

sebagai solusi terbaik dari permasalahan. Keunggulan dari algoritma genetika

adalah berproses sangat baik untuk global optimization khususnya bilamana

fungsi objektif adalah diskontinu atau mempunyai beberapa local minima.

2

B. Perumusan Masalah

Optimasi fungsi linier umumnya diselesaikan dengan menggunakan

penyelesaian metode linier. Akan dicoba penyelesaian program linier dengan

menggunakan aplikasi algoritma genetika. Persamaan linier yang akan dicari

nilai optimumnya adalah sebagai berikut :

Fungsi f(x1,x2,x3) = x1-x2-x3 x2>5

x1-2x2-x3 x2<=5

C. Tujuan

Tujuan dari penulisan ini adalah Mengaplikasikan Algoritma genetika pada

permasalahan optimasi fungsi linier.

3

BAB II. TINJUAN PUSTAKA

A. Terminologi Knowledge

Sejak algortima genetika (AG) pertama kali dirintis oleh John Holland dari Universitas

Michigan pada tahun 1960-an, AG telah diaplikasikan secara luas pada berbagai bidang.

AG banyak digunakan untuk memecahkan masalah optimasi, walaupun pada

kenyataannya juga memiliki kemampuan yang baik untuk masalah- masalah selain

optimasi. John Holland menyatakan bahwa setiap masalah yang berbentuk adaptasi

(alami maupun buatan) dapat diformulasikan dalam terminologi genetika. Algoritma

genetika adalah simulasi dari proses evolusi Darwin dan operasi genetika atas

kromosom.

Pada algoritma genetika, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang

mungkin dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi

disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih

berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya

merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan

generasi.

Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat

ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan

menunjukkan kualitas dari kromosom dalam populasi tersebut. Generasi berikutnya

dikenal dengan istilah anak (offspring) terbentuk dari gabungan dua kromosom generasi

sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator

penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat juga

dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk

dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari

kromosom anak (offspring), serta menolak kromosom-kromosom yang lainnya sehingga

ukuran populasi (jumlah kromosom dalam suatu populasi) konstan. Setelah melalui

beberapa generasi, maka algoritma ini akan konvergen ke kromosom terbaik.

4

Ada tiga keunggulan dari aplikasi Algoritma Genetika dalam proses optimasi, yaitu: (a)

Algoritma Genetika tidak terlalu banyak memerlukan persyaratan matematika dalam

penyelesaian proses optimasi. Algoritma Genetika dapat diaplikasikan pada beberapa

jenis fungsi obyektif dengan beberapa fungsi pembatas baik berbentuk linier maupun

non-linier; (b) Operasi evolusi dari Algoritma Genetika sangat efektif untuk

mengobservasi posisi global secara acak; dan (c) Algoritma Genetika mempunyai

fleksibilitas untuk diimplementasikan secara efisien pada problematika tertentu.

Algoritma genetika sangat tepat jika digunakan untuk menyelesaikan masalah optimasi

yang kompleks dan sukar diselesaikan dengan menggunakan metode konvensional.

Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana

umumnya terdiri dari tiga operasi, yaitu: operasi reproduksi, operasi crossover

(persilangan), dan operasi mutasi. Struktur umum dari suatu algoritma genetika terdiri

dari langkah-langkah:

a. Membangkitkan populasi awal secara acak.

b. Membentuk generasi baru dengan menggunakan tiga operasi di atas 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 mengulangi langkah

d. Beberapa kriteria berhenti yang umum digunakan ialah:

Berhenti pada generasi tertentu.

Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness

tertinggi/terendah (tergantung persoalah) tidak berubah.

Berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness yang lebih

tinggi/rendah.

5

B. Komponen-Komponen Utama Algoritme Genetika

1. Teknik Pengkodean

Teknik pengkodean adalah bagaimana mengkodekan gen dari kromosom. Satu gen

biasanya merepresentasikan satu variabel. Gen dapat diwakili dalam bentuk : bilangan

real, bit, daftar aturan, elemen permutasi, elemen program, atau representasi lainya

yang dapat diimplementasikan untuk operator genetika. Teknik pengkodean ini

tergantung pada pemecahan masalah yang dihadapi. Misalnya, pengkodean secara

langsung bilangan real atau integer.

Oleh karena itu, kromosom dapat direpresentasikan sebagai :

String bit : 11001, 10111

Array bilangan real : 7.9, 9.7, -70

Elemen permutasi : E5, E8, E11

Daftar aturan : R1, R2, R3

Elemen program : pemrograman genetika

2. Membangkitkan Populasi Awal

Pembentukan inisialisasi populasi adalah proses pembentukkan sejumlah individu

secara acak atau melalui prosedur tertentu. Ukuran suatu populasi tergantung pada

masalah yang akan dan diselesaikan serta jenis operator genetika yang akan

diterapkan di dalam algoritme genetika. Jika ukuran populasi telah ditentukan, maka

dilakukan generate inisialisasi populasi. Persyaratan dalam pemenuhan solusi harus

diperhatikan dalam generate setiap individu.

Teknik untuk pembangkitan populasi awal ada beberapa metode, yaitu:

a. Random Generator

Random generator adalah suatu proses pembangkitan bilangan acak untuk nilai

setiap gen sesuai dengan representasi kromosom yang digunakan. Jika

menggunakan bilangan biner, maka salah satu contoh penggunaan random

generator adalah menggunakan rumus berikut ini untuk pembangkitan populasi

awal :

( )

6

dengan IPOP merupakan gen yang nantinya berisi pembulatan dari bilangan acak

yang dibangkitkan sebanyak (jumlah populasi) dan (jumlah gen

dalam tiap kromosom).

b. Pendekatan Tertentu

Teknik ini adalah memasukan nilai tertentu ke dalam gen dari populasi awal yang

dibentuk.

c. Permutasi Gen

Salah satu teknik permutasi gen dalam pembangkitan populasi awal adalah

penggunaan permutasi Josephus dalam permasalahan kombinatorial.

3. Seleksi

Seleksi digunakan untuk memilih individu-individu mana saja yang akan dipilih untuk

proses crossover dan mutasi. Selain itu, untuk mendapatkan calon induk yang baik.

“Induk yang baik akan menghasilkan keturunan yang baik”. Semakin tinggi nilai

fitness suatu individu semakin besar kemungkinannya untuk dipilih.

Langkah pertama yang dilakukan dalam seleksi ini adalah pencarian nilai fitness.

Nilai fitness ini nantinya akan digunakan pada tahap-tahap seleksi berikutnya.

Masing-masing individu dalam wadah seleksi akan menerima probabiltas reproduksi

yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua

individu dalam wadah seleksi tersebut.

Ada beberapa metode seleksi, yaitu :

a. Seleksi dengan mesin Roulette

Metode seleksi dengan mesin roulette adalah metode sederhana dan sering dikenal

dengan nama stochatic sampling with replacement. Cara kerja metode ini sebagai

berikut :

1) Hitung nilai fitness dari masing-masing individu

2) Hitung nilai total nilai fitness semua individu

3) Hitung probabilitas masing-masing individu

4) Dari probabilitas tersebut, hitung jatah masing-masing individu pada angka 1

sampai 200

5) Lakukan pembangkitan bilangan acak antara 1 sampai 200

7

6) Bila langkah 5 selesai, tentukan individu mana yang terpilih dalam proses

diseleksi

b. Seleksi dengan Turnamen

Pada metode seleksi dengan turnamen, ditentukan suatu nilai tour untuk individu-

individu yang dipilih secara acak dari suatu populasi. Individu yang terbaik dalam

kelompok ini akan diseleksi sebagai induk. Sedangkan parameter yang digunakan

pada metode ini adalah ukuran tour yang bernilai antara 2 sampai N (jumlah

individu dalam suatu populasi).

Berikut ini ilustrasi seleksi dengan mesin Roulete :

Individu 1 : fitness = 25%





Jatah untuk individu 1 : 1 - 40





Individu yang terpilih

Bilangan acak 170 Individu 5





Dibangkitkan bilangan acak antara 1

sampai 200 sebanyak 5 kali

4. Crossover

Kawin silang (Crossover) adalah operator dari algoritme genetika yang melibatkan

dua induk untuk membentuk kromosom baru. Crossover menghasilkan titik baru

dalam ruang pencarian yang siap diuji. Operasi ini tidak selalu dilakukan pada semua

individu yang ada. Individu dipilih secara acak untuk dilakukan penyilangan dengan

8

antara 0,6 sampai 0,95. Jika crossover tidak dilakukan, maka nilai dari induk akan

diturunkan kepada anak (keturunan).

Prinsip dari crossover adalah melakukan operasi genetika (pertukaran, aritmatika)

pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan individu baru.

Para crossover dilakukan pada setiap individu dengan probabilitas crossover yang

telah ditentukan. Pada Gambar 2.1, diilustrasikan diagram alir penggunaan

probabilitas crossover pada proses crossover.

P < probCO

Induk 1

Induk 2

P = random[0,1]

Crossover

ya

tidak

Gambar 2.1. Diagram alir proses crossover

5. Mutasi

Operator ini berperan untuk menggantikan gen yang hilang dari populasi akibat

proses seleksi yang memungkinkan munculnya kembali gen yang tidak muncul pada

inisialisasi populasi. Kromosom anak dimulai dengan menambahkan nilai random

yang sangat kecil dengan probabilitas yang rendah. Peluang mutasi ( didefinisikan

sebagai persentase dari jumlah total gen pada populasi yang mengalami mutasi.

Peluang mutasi mengendalikan banyaknya gen baru yang akan dimunculkan untuk

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

9

pernah dievaluasi. Tetapi jika peluang mutasi terlalu besar, maka akan terlalu banyak

gangguan acak, sehingga anak akan kehilangan kemiripan dari induknya dan

algoritme kehilangan kemampuan untuk belajar dan melakukan pencarian. Ada yang

berpendapat bahwa laju mutasi sebesar

akan memberikan hasil cukup baik. Ada

juga yang berpendapat bahwa laju mutasi tidak tergantung pada ukuran populasi.

Kromosom hasil mutasi harus diperiksa, apakah masih berada pada domain solusi,

dan bila perlu dapat dilakukan perbaikan.

Pada Gambar 2.2, diilustrasikan diagram alir penggunaan mutasi pada proses mutasi.

Proses yang diilustrasikan tersebut adalah cara mudah untuk melakukan mutasi.

Proses mutasi yang dilakukan tidak harus seperti pada tersebut, tapi bisa dengan

melakukan mutasi pada gen sebanyak (probabilitas mutasi * jumlah gen), dimana

posisi gen yang akan dilakukan mutasi dipilih secara acak.

P < probMut

Induk 1

Induk 2

P = random[0,1]

Gen (r)

dimutasi

yatidak

r = random

Gambar 1 Diagram alir proses mutasi

Mutasi biner merupakan salah satu cara sederhana untuk mengganti satu atau

beberapa nilai gen dari kromosom. Contoh mutasi biner pada Gambar 2.3.

10

1 0 10 1 r = 3 1 0 11 1

Gambar 2.3. Proses dan hasil mutasi

1. Hal-hal yang harus dilakukan dalam Algoritme Genetika

Beberapa hal yang harus dilakukan dalam Algoritme Genetika adalah :

a. Mendefinisikan individu, individu dinyatakan sebagai salah satu solusi atau

penyelesaian yang mungkin dari permasalahan yang diangkat.

b. Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu

atau solusi yang didapatkan.

c. Menentukan proses generate populasi awal. Proses ini umumnya dilakukan dengan

menggunakan pembangkitan acak.

d. Menentukan proses seleksi yang akan digunakan

e. Menentukan proses operasi genetika yaitu crossover dan mutation

2. Persamaan Linier

Persamaan linier digunakan untuk merepresentasikan suatu masalah yang akan dilakukan

optimisasi (minimisasi dan maksimisasi) dengan beberapa fungsi tujuan dan fungsi

kendala. Penyelesaian program linier digunakan untuk mencari nilai optimal dari

variabel-variabel pembentuk fungsi tersebut. Tujuan dari penyelesaian program linier

adalah untuk mencari solusi optimal yang memenuhi semua kendala. Akan didapatkan

berbagai macam solusi yang fisible yang memenuhi persamaan yang diberikan.

Program linier dapat digunakan dalam berbagai aplikasi, diantaranya adalah optimasi

sumberdaya yang ada di suatu organisasi. Misalnya dalam alokasi alat dan mesin, kita

memiliki alat dan mesin X1, X2 dan X3. Maka bagaimana kita bisa mengoptimalkan

pengguanaan mesin tersebut sementara terdapat batasan-batasan fungsi.

11

BAB III. HASIL DAN PEMBAHASAN

A. Perancangan Aplikasi

Pembanguanan aplikasi yang dilakukan menggunakan tahapan-tahapan sesuai dengan

metode pemecahan masalah optimasi dengan menggunakan algoritma genetika. Berikut

adalah urut-urutan (diagram alir) pemecahan masalah yang dilakukan.

Gambar 3.1. Diagram Alir Rancangan Aplikasi Algoritma Genetika Untuk Optimisasi

Persamaan Linier

12

B. Perangkat Lunak

Perangkat lunak yang digunakan dalam pembuatan aplikasi ini adalah dengan menggunakan

VBA macro Microsoft Excel.

C. Mekanisme Algoritma Genetika Untuk Optimasi Fungsi Linier

Untuk dapat mengaplikasikan algoritma genetika, ada beberapa langkah yang harus

dilakukuan antara lain mengenerate fungsi awal dalam bentuk representasi kromosom,

mengukur optimasi untuk semua calon solusi dari suatu masalah menggunakan fungsi fitness,

seleksi kromosom, penggunaan operator genetika seperti crossover dan mutasi agar

sekumpulan calon solusi (representasi kromosom) yang dibangkitkan pada populasi awal

dapat berkembang biak dengan sendirinya (melalui beberapa generasi) sehingga konvergen

memberikan nilai fitness yang terbaik (solusi tunggal dengan nilai paling optimum diantara

solusi) (Davids, 1991).

1. Pembentukan Kromosom

Untuk memecahkan masalah optimasi fungsi dengan persamaan :

Fungsi f(x1,x2,x3) = x1-x2-x3 x2>5

x1-2x2-x3 x2<=5

Maka fungsi tersebut direpresentasikan dalam bentuk kromosom-kromosom. Karena kita

akan mencari nilai optimal dari x1, x2 dan x3 maka x1, x2, dan x3 dijadikan sebagai gen

pembentuk kromosom. Berikut adalah batasan nilai-nilai x1, x2, dan x3 yang

diperbolehkan :

x1 = 0 s.d. 10

x2 = 0 s.d. 10

x3 = 0 s.d. 10

13

2. Inisiasi Masalah dan Pembantukan Kromosom

Proses inisiasi masalah dilakukan dengan membentuk generasi awal gen-gen dengan nilai

acak sesuai dengan batasan yang ditentukan. Dalam hal ini ditentukan jumalh populasi

yang digunakan adalah sebanyak 10 seperti tampak pada tabel di bawah ini :

Tabel 3.1. Inisiasi Populasi Awal

Kromosom Gen-1 Gen-2 Gen-3 f(X)

1 8,2980 8,2460 5,8916 5,8396

2 9,8609 9,1096 2,2687 1,5174

3 6,9512 9,8000 2,4393 5,2882

4 5,3387 1,0637 9,9941 6,7828

5 6,7618 0,1570 5,7518 0,6958

6 1,0005 1,0302 7,9888 9,0488

7 2,8448 0,4565 2,9577 1,0259

8 3,8201 3,0097 9,4857 11,6850

9 9,7983 4,0137 2,7828 1,0120

10 1,6044 1,6282 6,4659 8,1179

Setelah kromosom awal terbentuk maka dicari fungsi obyektif awal dari fungsi yang akan

dimaksimisasi. Tabel 3.1. diatas memperlihatkan representasi fungsi obyektif f(X) dari

kromosom awal yang dibentuk.

Berikut adalah kode program dengan VBA Excel untuk melakukan pembantukan

generasi pertama :

For i = 1 To 10 x(i, 1) = Cells(2, 5) + Rnd() * (Cells(2, 6) - Cells(2, 5)) x(i, 2) = Cells(3, 5) + Rnd() * (Cells(3, 6) - Cells(3, 5)) x(i, 3) = Cells(4, 5) + Rnd() * (Cells(4, 6) - Cells(4, 5)) Cells(i + 9, 3) = x(i, 1) Cells(i + 9, 4) = x(i, 2) Cells(i + 9, 5) = x(i, 3) If x(i, 2) > 5 Then f(i) = Abs(x(i, 1) - x(i, 2) - x(i, 3)) Else f(i) = Abs(x(i, 1) - 2 * x(i, 2) - x(i, 3)) End If Cells(i + 9, 6) = f(i)

14

Next i n = 0 br = 0 jum = Cells(1, 2) For k = 1 To jum

3. Seleksi Kromosom

Proses seleksi kromoson bertujuan untuk memilih kromosom yang akan menghasilkan

solusi dari persamaan linier yang optimal. Berikut adalah kode program yang digunakan

untuk proses seleksi :

tbs = f(i) For i = 1 To 10 If f(i) > tbs Then tbs = f(i) x1tbs = x(i, 1) x2tbs = x(i, 2) x3tbs = x(i, 3) End If Next i n = n + 1 DoEvents cacah.Text = "Generasi ke -" & Str(n) Cells(n + 55, 2) = n Cells(n + 55, 3) = x1tbs Cells(n + 55, 4) = x2tbs Cells(n + 55, 5) = x3tbs Cells(n + 55, 6) = tbs If Cells(n + 55, 6) > Cells(n + 55 - 1, 7) Then Cells(n + 55, 7) = Cells(n + 55, 6) Else Cells(n + 55, 7) = Cells(n + 55 - 1, 7) End If Cells(56, 7) = Cells(56, 6) DoEvents hasil.Text = "Nilai terbaik : " & Str(Cells(n + 55, 7))

15

4. Proses Penyilangan

Metode crossover yang digunakan pada eksperimen ini adalah one-cut-point yaitu

memilih secara acak satu posisi dalam kromosom induk kemudian saling menukar gen.

Kromosom dipilih secara acak sesuai dengan parameter cross over rate, yang dalam

eksperimen ini digunakan 0,3 yang artinya rata-rata 0,3 x 10 = 3,3 kromosom yang

mengalami cross over pada setiap populasi.

Berikut adalah kode program yang digunakan untuk melakukan cross over :

ulang: nc = 0 For i = 1 To 10 mc = Rnd() If mc <= Cells(4, 2) Then nc = nc + 1 co(nc) = i 'no kromosom yg cross over End If Next i If nc Mod 2 <> 0 Then GoTo ulang Cells(55 + n, 9) = nc For i = 1 To nc Step 2 If pot >= 0.5 Then buff = x(co(i), 2) x(co(i), 2) = x(co(i + 1), 2) x(co(i + 1), 2) = buf Else buff = x(co(i), 3) x(co(i), 3) = x(co(i + 1), 3) x(co(i + 1), 3) = buff End If Next i

16

Berikut adalah kromosom hasil penyilangan pada generasi ke 200 yang dirunning :

Tabel 3.2. Kromosom Hasil Penyilangan Pada Generasi ke-200


1 0,8868 5,2633 6,8569 11,2334

2 0,8868 5,2633 6,8569 11,2334

3 0,8868 5,2633 6,8569 11,2334

4 0,8868 5,2633 6,8569 11,2334

5 0,8868 5,2633 6,8569 11,2334

6 0,8868 5,2633 6,8569 11,2334

7 0,8868 5,2633 6,8569 11,2334

8 0,8868 5,2633 6,8569 11,2334

9 0,8868 5,2633 6,8569 11,2334

10 0,8868 5,2633 6,8569 11,2334

5. Proses Mutasi

Jumlah kromosom yang mengalami mutasi dalam satu populasi ditentukan oleh

parameter mutatation ration. Mutasi sendiri dilakukan untuk melakukan penggantian satu

gen yang terpilih secara acak dengan satu nilai baru yang didapat secara acak pula.

Prosesnya adalah dengan menghitung terlebih dahulu panjang gen yang ada dalam

populasi. Mutation ratio yang digunakan dalam percobaan ini adalah sebesar 0,1.

Berikut adalah kromosom hasil mutasi :

Tabel 3.3. Kromosom Hasil Mutasi Pada Generasi ke-200


1 0,8868 5,2633 8,3267 12,7032

2 0,8868 5,2633 6,8569 11,2334

3 7,8027 5,2633 6,8569 4,3175

4 0,8868 2,3631 6,8569 10,6963

5 0,8868 5,2633 6,8569 11,2334

6 0,8868 5,2633 6,8569 11,2334

7 0,8868 5,2633 6,8569 11,2334

8 0,8868 5,2633 6,8569 11,2334

9 0,8868 5,2633 6,8569 11,2334

10 0,8868 2,8907 6,8569 11,7515

17

6. Proses Seleksi

Proses seleksi adalah proses pengurutan solusi-solusi yang terbaik. Hal ini dilakukan

untuk mendapatkan nilai-nilai terbaik dari kromosom-kromosom yang telah dimutasi dan

cross over.

D. Hasil Running Program

Setelah dilakukan proses-proses diatas maka program di running dengan menggunakan

macro VBA Excel. Dari hasil running program yang didapatkan grafik fungsi fitnes. Program

sendiri di running dengan jumlah generasi sebanyak 200, dan jumlah populasi 10, mutation

ratio 0,1 dan cross over ratio 0,3. Gambar 2.2. memperlihatkan grafik fungsi fitness yang

dihasilkan dari running program dengan 200 generasi.

Gambar 2.2. Grafik Fungsi Fitness dengan 200 Generasi

Dari hasil running tersebut kita dapatkan nilai optimum global diperoleh pada iterasi

sebanyak 200 generasi adalah sebesar 17.8417807817459. Nilai tersebut merupakan nilai

optimal dari fungsi yang diselesaikan.

0.000

2.000

4.000

6.000

8.000

10.000

12.000

14.000

16.000

18.000

20.000

0 50 100 150 200

Nil

ai f(

)

Generasi

f(x)

f(x)*

18

BAB IV. KESIMPULAN

Penyelesaian program linier dapat diselesaikan diselesaikan dengan menggunakan algoritma

genetika. Prinsip utama algoritma genetika adalah melakukan operasi-operasi gentika pada

penyelesaian solusi. Dari hasil running program dengan 200 generasi didapatkan nilai terbaik

sebesar 17.8417807817459.

19

DAFTAR PUSTAKA

Davids, L. (Ed). 1991. Handbook of Genetic Algorithm. Van Nonstrand Reinhold, New York

Gen M and Cheng R. 1997. Genetic Algorithms and Engineering Design. John Willey and Sons,

Inc, USA.

Suyanto. 2005. Algoritma Genetika dalam MATLAB. ANDI : Yogyakarta.

20

Lampiran 1. Kode Program dengan VBA Excel

Dim i, j As Integer Dim x(20, 4), f(20), co(10) As Single Sub populasi() 'Hapus tampilan Call hapus ' Menggenerate generasi Pertama For i = 1 To 10 x(i, 1) = Cells(2, 5) + Rnd() * (Cells(2, 6) - Cells(2, 5)) x(i, 2) = Cells(3, 5) + Rnd() * (Cells(3, 6) - Cells(3, 5)) x(i, 3) = Cells(4, 5) + Rnd() * (Cells(4, 6) - Cells(4, 5)) Cells(i + 9, 3) = x(i, 1) Cells(i + 9, 4) = x(i, 2) Cells(i + 9, 5) = x(i, 3) If x(i, 2) > 5 Then f(i) = Abs(x(i, 1) - x(i, 2) - x(i, 3)) Else f(i) = Abs(x(i, 1) - 2 * x(i, 2) - x(i, 3)) End If Cells(i + 9, 6) = f(i) Next i n = 0 br = 0 jum = Cells(1, 2) For k = 1 To jum ' Nilai fungsi terbaik tbs = f(i) For i = 1 To 10 If f(i) > tbs Then tbs = f(i) x1tbs = x(i, 1) x2tbs = x(i, 2) x3tbs = x(i, 3) End If Next i n = n + 1 DoEvents cacah.Text = "Generasi ke -" & Str(n) Cells(n + 55, 2) = n Cells(n + 55, 3) = x1tbs Cells(n + 55, 4) = x2tbs

21

Cells(n + 55, 5) = x3tbs Cells(n + 55, 6) = tbs If Cells(n + 55, 6) > Cells(n + 55 - 1, 7) Then Cells(n + 55, 7) = Cells(n + 55, 6) Else Cells(n + 55, 7) = Cells(n + 55 - 1, 7) End If Cells(56, 7) = Cells(56, 6) DoEvents hasil.Text = "Nilai terbaik : " & Str(Cells(n + 55, 7)) 'Pengecekan cross over ulang: nc = 0 For i = 1 To 10 mc = Rnd() If mc <= Cells(4, 2) Then nc = nc + 1 co(nc) = i 'no kromosom yg cross over End If Next i If nc Mod 2 <> 0 Then GoTo ulang Cells(55 + n, 9) = nc For i = 1 To nc Step 2 If pot >= 0.5 Then buff = x(co(i), 2) x(co(i), 2) = x(co(i + 1), 2) x(co(i + 1), 2) = buf Else buff = x(co(i), 3) x(co(i), 3) = x(co(i + 1), 3) x(co(i + 1), 3) = buff End If Next i 'Generasi setelah cross over Cells(14, 10) = n Call cetak(15, 10) ' Pengecekan mut = 0 For i = 1 To 10

22

For j = 1 To 3 If Rnd() < Cells(3, 2) Then mut = mut + 1 If j = 1 Then x(i, 1) = Cells(2, 5) + Rnd() * (Cells(2, 6) - Cells(2, 5)) If j = 2 Then x(i, 2) = Cells(3, 5) + Rnd() * (Cells(3, 6) - Cells(3, 5)) If j = 3 Then x(i, 3) = Cells(4, 5) + Rnd() * (Cells(4, 6) - Cells(4, 5)) End If Next j Next i Cells(n + 55, 10) = mut ' Jumlah kejadian mutasi ' pencetakan mutasi Cells(28, 10) = n Call cetak(29, 10) Cells(41, 10) = n ' Proses pengurutan For i = 1 To 10 For j = 1 To 10 If f(i) > f(j) Then buf1 = x(i, 1) buf2 = x(i, 2) buf3 = x(i, 3) buf4 = f(i) x(i, 1) = x(j, 1) x(i, 2) = x(j, 2) x(i, 3) = x(j, 3) f(i) = f(j) x(j, 1) = buf1 x(j, 2) = buf2 x(j, 3) = buf3 f(j) = buf4 End If Next j Next i 'Pencetakan hasil pengurutan Call cetak(42, 10) Cells(23, 3) = n + 1 ' Seleksi b = 0 For i = 1 To 10 br = (Rnd() * 1000) / 1000 If br <= 0.182 Then x(i, 1) = x(1, 1): x(i, 2) = x(1, 2): x(i, 3) = x(1, 3): f(i) = f(1) If br <= 0.345 And br > 0.182 Then x(i, 1) = x(2, 1): x(i, 2) = x(2, 2): x(i, 3) = x(2, 3): f(i) = f(2) If br <= 0.491 And br > 0.345 Then x(i, 1) = x(3, 1): x(i, 2) = x(3, 2): x(i, 3) = x(3, 3): f(i) = f(3)

23

If br <= 0.618 And br > 0.491 Then x(i, 1) = x(4, 1): x(i, 2) = x(4, 2): x(i, 3) = x(4, 3): f(i) = f(4) If br <= 0.727 And br > 0.618 Then x(i, 1) = x(5, 1): x(i, 2) = x(5, 2): x(i, 3) = x(5, 3): f(i) = f(5) If br <= 0.818 And br > 0.727 Then x(i, 1) = x(6, 1): x(i, 2) = x(6, 2): x(i, 3) = x(6, 3): f(i) = f(6) If br <= 0.891 And br > 0.818 Then x(i, 1) = x(7, 1): x(i, 2) = x(7, 2): x(i, 3) = x(7, 3): f(i) = f(7) If br <= 0.945 And br > 0.891 Then x(i, 1) = x(8, 1): x(i, 2) = x(8, 2): x(i, 3) = x(8, 3): f(i) = f(8) If br <= 0.982 And br > 0.945 Then x(i, 1) = x(9, 1): x(i, 2) = x(9, 2): x(i, 3) = x(9, 3): f(i) = f(9) If br <= 1 And br > 0.982 Then x(i, 1) = x(10, 1): x(i, 2) = x(10, 2): x(i, 3) = x(10, 3): f(i) = f(10) Next i Call cetak(24, 3) Next k End Sub Sub cetak(bar, kol) For i = 1 To 10 Cells(bar + i, kol) = x(i, 1) Cells(bar + i, kol + 1) = x(i, 2) Cells(bar + i, kol + 2) = x(i, 3) If x(i, 2) > 5 Then f(i) = Abs(x(i, 1) - x(i, 2) - x(i, 3)) Else f(i) = Abs(x(i, 1) - 2 * x(i, 2) - x(i, 3)) End If Cells(bar + i, kol + 3) = f(i) Next i End Sub Sub hapus() For i = 1 To 300 Cells(i + 55, 2) = "" Cells(i + 55, 3) = "" Cells(i + 55, 4) = "" Cells(i + 55, 5) = "" Cells(i + 55, 6) = "" Cells(i + 55, 7) = "" Cells(i + 55, 9) = "" Cells(i + 55, 10) = "" Next i End Sub

24

Private Sub CommandButton1_Click() Call populasi End Sub

optimasi fungsi sederhana dengan algoritma genetika

Documents