PENERAPAN ALGORITMA GENETIK UNTUK OPTIMASI DENGAN MENGUNAKAN PENYELEKStAN RODA ROULETTE Samuel Lukas, M.Tech." Abstract The purpose of this paper is to introducing genetic algorithm. This algorithm is one method of the non-deterministic algorithms to solve optimizing problem. The principle of how the genetic algorithm work is explained through the paper. One optimizing problem is also introducing to demonstrate how the genetic algorithm works. That is to maximizing f(x) = sin (nxl 256).
1. PENDAHULUAN Masalah optimasi merupakan topik yang menarik karena ia mempunyai banyak terapan dalam kehidupan. Perjalanan seorang salesmen dari kantornya untuk mengunjungi sejumlah pelanggan dan terakhir kembali ke kantor adalah salah satu aplikasi yang menarik dalam optimasi. Persoalan optimasi yang mungkin diambil dari masalah diatas adalah bagaimana memilih urutan pelanggan yang harus dikunjungi sehingga meminimalisasi jarak tempuh, atau meminimalisasi waktu perjalanan, atau meminimalisasi biaya perjalaan, atau bahkan memaksimalkan keuntungan yang mungkin didapat. Sudah dikembangkan banyak algoritma untuk mencari jawab atas suatu masalah optimasi. Umumnya algortima yang dipakai adalah algoritma yang deterministik. Algortima genetik adalah salah satu algoritma yang bersifat nondeterministik. la dapat dipakai untuk mencari jawab masalah optimasi. Pada makalah ini akan dibahas bagaimana mekanisme pengunaan algoritma genetik secara umum dengan mengambil satu kasus yaitu mencari optimasi untuk menyelesaian berapa nilai x sehingga persamaan f(x) = sin (70U256) mencapai titik maksimum. 2. ALGORITMA GENETIK DAN TERMINOLOGINYA Algoritma generik pertama kali dikembangkan oleh John Holland Universitas Michigan tahun 1975. \a mengatakan bahwa algoritma genetik dapat mensimulasikan proses evolusi Darwin dan operasi genetika atas kromosom. la mengembangkan beberapa terminologi yang berkaitan dengan algorotma genetik. Seluruh terminologi yang ada berkaitan dengan terminologi biologi. Terminologi itu adalah Populasi, Kromosom, Offspring, Generasi. Populasi adalah himpunan dari jawaban yang akan dicari dari suatu permasalahan yang ada. Kromosom adalah salah satu jawab yang masih dalam bentuk suatu simbol. Offspring adalah anak dari hasil penggabungan 2 buah kromosom sebagai induk dengan mengunakan operator crossover atau penyilangan. Salah satu operator lainnya adalah mutasi. Generasi adalah suatu populasi yang dihasilkan dari hasil perubahan seluruh kromosom dari populasi sebelumnya, setelah melalui suatu proses penseleksian yang dinamakan Fitness.
' Dosen Tetap Fakultas llmu Komputer UPH Penerapan Algoritma Genetika Untuk Optimasi.. (Samuel Lukas)
53
Populasi awal dibangkitkan secara acak. Populasi awal ini sering kali disebut sebagai generasi pertama. Populasi berikutnya yang adalah generasi berikutnya adalah hasil evaluasi seluruh kromosom dalam populasi. Proses pengevaluasian ini melibatkan suatu fungsi yang disebut fungsi fitness. Beberapa Kromosom dalam populasi melalui proses offspring, fitness dan penolakan kromosom. Hasil dari seluruh proses ini menghasilkan kromosom baru dan meniadakah kromosom lainnya sehingga ukuran populasi tetap dan konvergen pada kromosom terbaik.
3. KOMPONEN UTAMA ALGORITMA GENETIK Ada beberapa komponen utama dalam algoritma genetik yaitu Penyandian, Fungsi Evaluasi, Seleksi, Operator Genetika dan Parameter Kontrolnya. Penyandian adalah bagian yang penting pada proses genetika. Seperti yang dikatakan di atas kromosom adalah salah satu dari kemungkinan jawab atas permasalah yang ada. la masih dalam bentuk simbol-simbol. Simbol-simbol ini adalah hasil dari suatu penyandian. Kromosom terdiri dari sejumlah gen tertentu. Setiap simbol pada gen mempunyai arti tersendiri sesuai dengan teknik penyandian yang digunakan. Fungsi Evaluasi dipakai untuk menghitung nilai fitness dari suatu kromosom yang dihasilkan. Kromosom yang mempunyai nilai fitness terbesar adalah merupakan kromosom terbaik yang juga berarti suatu jawab simbolik yang terbaik atas suatu peroalannya. Fungsi evaluasi ini diturunkan dari fungsi objektif permasalah yang ada. Seleksi merupakan suatu proses penseleksian kromosom sedemikian rupa sehingga kromosom mana yang akan tetap tinggal untuk menjadi kromosom pada generai berikutnya dan kromosom mana yang harus berubah untuk bisa menjadi kromosom baru sehingga jumlah kromosom dalam satu populasi tetap. Ada banyak teknik penseleksian yang dapat dipakai seperti Rank based fitness assigment, Roulette wheel selection, Stochastic universal sampling, Local selestion, Truncation selection dan Tournament selection Operator Genetika adalah suatu operator yang digunakan untuk membentuk generasi baru. Ada dua operator yaitu untuk melakukan rekombinasi dan operator untuk mutasi. Opererator rekombinasi dapat berupa rekombinasi real, rekombinasi bernilai biner (crossover) atau crossover dengan permutasi. Sedangkan Mutasi dapat berupa mutasi bernilai real dan mutasi bernilai biner. Parameter Kontrol adalah suatu parameter yang menentukan berapa banyak kromosom yang akan mengalami perubahan dari satu generasi ke generasi berikutnya. Parameter kontrolnya adalah ukuran populasi, peluang crossover dan peluang mutasi.
54 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 53-61
4. PERANCANGAN SISTEM (^ START ) Lakukan Penjandian
3Z. Populasi awal
Prinsip dasar algoritma genetik dimulai dengan melakukan teknik penyandian yang kemudian dibangkitkan sejumlah kromosom, sebanyak paramater ukuran populasi. Populasi ini sebagai generasi pertama. Generasi kedua dan seterusnya didapat setelah melakukan proses pengulangan atas pengevaluasian fungsi fitness, seleksi populasi, rekombiinasi dan mutasi. Proses pengulangan berhenti sesuai dengan apa yang diharapkan. Jawaban atas persoalan diambil dari kromosom terbaik pada generasi terakhir yang kemudian dilakukan dekodifikasi untuk mengambil makna dari jawaban yang ada.
Gambar 1: Diagram Alir Perancangan sistem
5. SELEKSI POPULASI DENGAN RODA ROULETTE. Proses penseleksian dengaq metoda roda roulette ini dilakukan dengan mengambil prinsip penyeleksian alami. Prosesnya dilakukan dengan membangkitkan bilangan random. Hal ini yang mengambarkan penyeleksian dilakukan secara acak. Langkahnya diawali dengan menentukan fitness relative setiap kromosom dan tentukan fitness kumulatifnya. Kemudian menentukan sejumlah bilangan acak diantara 0 sampai dengan 1 sebanyak jumlah populasi. Bilangan acak ini berfungsi sebagai acuan untuk menentukan kromosom mana yang akan bertahan pada generasi berikutnya. Kromosom yang bertahan adalah kromosom yang mempunyai nilai fitness terdekat dengan bilangan random yang terbangkitkan. Karena banyaknya bilangan random terbangkitkan sama dengan banyaknya populasi maka dipastikan jumlah kromosom pada generasi berikutnya sama dengan jumlah kromosom pada populasi awal. Bagaimana mekanisme hal ini dapat terjadi, sangat ditentukan dengan teknik penyeleksian yang dipakai. Pada makalah ini akan digunakan teknik penyelesian dengan mengunakan Roda Roulette. Penerapan Algoritma Genetika Untuk Optimasi... (Samuel Lukas)
55
6. REKOMBINASI DENGAN SATU TITIK Sama halnya dengan metoda penyeleksian, ada banyak metoda yang dapat dipakai untuk melakukan rekombinasi. Pada makalah ini akan dilakukan rekombinasi dengan satu titik. Mekanisme rekombinasi dimulai dengan menentukan parameter rekombinasi. Paramater ini untuk menentukan berapa banyak kromosom yang akan dilakukan rekombinasi. Katakanlah ada n kromosom yang akan direkombinasi. Persoalannya adalah kromosom mana yang akan dilakukan rekombinasi. Hal ini ditentukan dengan metoda random. Pertama dibangkitkan bilangan random sebanyak jumlah kromosom dalam populasi. Kedua, ditentukan suatu bilangan pengukur, x, yang biasanya besarnya adalah persentasi jumlah kromosom yang akan dilakukan rekombinasi. Ke tiga, menentukan kromosom yang terpilih untuk dilakukan rekombinasi yaitu kromosom yang bersesuai dengan bilangan random yang kurang dari nilai x tadi. Jika jumlah kromosom terpilih lebih dari seharusnya maka tentukan sebanyak n, n harus genap. Jika tidak maka itulah kromosom terpilih untuk melakukan rekombinasi. Ke empat, dibangkitkan'satu bilangan random dalam range 1 sampai dengan jumlah gen dalam satu kromosom minus 1. Bilangan random ini dipakai untuk menentukan posisi gen mana dalam satu kromosom yang akan direkombinasi dengan kromosom pasangannya. Pelaksanaan rekombinasi satu titik dimulai dari gen pada posisi itu + 1 hingga pada gen terakhir. 7. MUTASI Mutasi adalah suatu proses perubahan salah satu atau sejumlah gen pada suatu populasi atau generasi. Proses mutasi ini memungkinkan terbentuknya suatu kromosom baru yang keberadaannya tak terperhitungkan. Proses mutasi ini dimulai dengan menentukan berapa banyak jumlah gen yang akan mengalami mutasi dalam satu populasi lalu dibangkitkan sejumlah bilangangan random dari 0 sampai dengan 1. Gen mana yang mengalami mutasi ditentukan dari bilangan random yang dihasilkan. Gen yang mengalami mutasi diganti secara acak dari kemungkinan gen yang mungkin dibentuk. 8. HASIL PERCOBAAN Percobaan dilakukan untuk menentukan berapa nilai f(x)=s'm(m/256) sehingga berharga maksimum. Penyandian satu kromosom terdiri dari 18 bits. Arti dari satu kromosom bersimbol 100000110011100000 merepresentasikan nilai x sebesar 130,7067 didapat dari interpolasi sederhana X = 255/(218-1) * 134468 Fungsi evaluasi yang adalah fungsi fitness adalah fungsi itu sendiri
fungsi yang yang yaitu
f(x)=sm(nx/256) Populasi awal dibentuk sebanyak 20 kromosom dan setelah dihitung nilai x dan nilai filnessnya maka didapat tabel 1. Penyeleksian dilakukan dengan metoda roda roulette dihasilkan Tabel 2. Dari tabel itu maka terlihat bahwa kromosom ke 1, 2, 3, dst pada generasi kedua adalah kromosom ke-17, ke-1, ke-7 dst. Terlihat bahwa beberapa kromosom telah hilang pada generasi baru ini misalnya kromosom ke-3, ke-5, ke-6 dsb. Sebaliknya ada beberapa kromosom yang identikal dalam satu populasi.
56 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 53-61
Tabel 1: Populas: awal Bentuk Biner
Kromosom 1
1
0
1
0
0
1
1
0
1
1
0
0
0
0
0
1
X
fitness
1
1
166.106
0.892
2
1
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
1
0
200.167
0 632
3
0
0
0
0
0
1 0
1
0
0
1
0
1
1
0
1
1
0
5.158
0.063
4
0
0
1
0
0
0
1
0
0
1
1
0
1
1
0
0
0
0
34.288
0.409
5
0
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
0
1
88.953
0.888
6
0
0
1
1
0
0
0
1
0
1
0
1
0
1
0
0
1
0
49.138
0.567
7
1
0
0
1
0
0
0
0
I
0
1
1
0
1
0
0
0
0
144.138
0.980
8
1
1
0
I
0
0
0
1 0
0
0
0
0
1
0
0
1
0
208.202
0.553
9
1
0
1
0
0
1
1
0
1
0
0
1
0
1
1
1
0
1
165.941
0.893
10
0
1
0
0
0
1
1
0
0
1
1
0
1
0
0
0
0
0
70.131
0.758
11
1
1
0
1
0
1
1
0
0
1
0
0
1
1
0
0
1
1
213.464
0498
12
1
1
1
0
1
0
0
1
0
1
0
1
1
1
0
0
0
1
232.450
0.284
13
0
1
0
0
1
1
1
0
1
0
0
1
0
0
0
1
1
1
78.263
0.820
14
1
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
1
239.173
0.204
15
0
0
0
1
1
1
1
0
0
1
1
I
0
1
1
0
0
1
30.343
0.364
16
I
t
0
0
1
0
1
1
1
0
0
0
1
1
0
1
1
0
202.758
0.607
17
0
0
0
0
1
1
0
1
0
1
0
1
0
I
1
1
1
0
13.290
0 162
18
1
1
0
1
0
1
1
1
0
1
0
1
0
1
0
0
1
0
214.490
0.487
19
1
0
1
1
1
0
1
0
0
1
1
0
0
1
I)
0
0
0
185.663
0.759
20
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
1
I
0
225.186
0.368
Total Fitness
11.189
Tabel 2: Penseleksian Kromosom Kromosom
fitrel
fitkum
Bilangan acak
Kromosom baru
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0.080 0056 0.006 0.037 0.079 0.051 0088 0.049 0.080 0.068 0.044 0.025 0.073 0.018 0.033 0.054 0.015 0.044 0.068 0.033
0.080 0.136 0.142 0.178 0.258 0.308 0.396 0.445 0.525 0.593 0.638 0.663 0.736 0.754 0.787 0.841 0.856 0.899 0.967 1.000
0852 0.040 0.352 0.606 0.583 0.888 0.586 0.377 0.088 0.037 0.111 0.730 0298 0.559 0.163 0.799 0.895 0.608 0.078 0.318
17 1 7 11 10 18 10 7 2 1 2 13 6 10 4 16 18 11 1 7
Penerapan Algohtma Genetika Untuk Optimasi... (Samuel Lukas)
57
Pembentukan generasi baru belum selesai karena perlu dilakukan rekombinasi dan mutasi terlebih dahulu. Rekombinasi dtetapkan sebanyak 25%. Ini berarti dalam satu generasi ada 25%*20 atau 5 kromosom yang akan mengalami rekombinasi. Karena jumlah kromosom yang mengalami rekombinasi harus genap maka diambil 6 kromosom atau 4 kromosom yang akan mengami rekombinasi. Kemudian dibangkitkan 20 bilangan acak seperti tabel 3. satu bilangan acak berkoresponden satu-satu dengan nomor kromosom. Kromosom yang mengalami rekombinasi ditentukan dengan mengambil bilangan acak yang kurang dari 0.25, maka didapat tujuh kromosom yaitu kromosom ke 5,6,10,11,17,18 dan 19. Maka ditetapkan 6 kromosom pertama dengan pasangan (5,6), (10,11) dan (17,18) yang akan mengalami rekombinasi. Bangkitkan satu bilangan acak dari 1 sampai 17 jika didapat angka 4 maka proses rekombinasi untuk kromosom ke-5 dan 6 diperlihatkan pada gambar 2. Akhir dari proses rekombinasi didapat Tabel 4. Tabel 3: Bilangan Acak untuk Rekombinasi Krom
Bil Acak
1
0.383
0.475
0.849
0.851
0.125
6
0.209
0.968
0.462
0.481
0.112
11
0.241
0.597
0.908
0.807
0.961
16
0.497
0.062
0.106
0.051
0.857
No kromosom
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5
(i
1
0
0
0
1
1
1)
0
1
1
0
1
0
0
0
0
0
70.131
0758
6
1
1
0
1
0 1 1 0 0 0 1 0 1 Kromosom ke 5 dan ke 6 sebeltim iekoinbin;ir,i
1
0
0
1
0
214490
0.487
No kromosom
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Nilai x
fitness
5
0
1
0
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
71 052
0.766
6
1
1
0
1
0 1 1 0 0 1 1 0 1 Kromosom ke-5 dan ke-6 setelah rekombinasi
0
0
0
0
0
213.570
0.497
Nilai x
Gambar 2: Proses Rekombinasi Kromosom Ke-5 dengan Ke-6 dengan Satu Titik
Proses mutasi dimulai dengan menetapkan probabilitas mutasi adalah 0.01. Ini berarti ada 0.01*20*18 gen yang akan mengalami mutasi. Jadi ada 4 gen yang akan mengalami mutasi. Bangkitkan 360 bilangan acak, menggambarkan 360 buah bits yang mungkin mengalami mutasi. Bit mana yang dimutasi dipilih dari bilangan acak yang kurang dari 0.01. Jika bilangan acak yang ke 20 adalah 0.006 maka bit yang ke 20 mengalami mutasi dan itu berarti pada kromosom ke 2 dan pada bit yang ke 2. Jika yang terpilih dinyatakan dengan (Kromosom,bit) adalah (2,2), (7,6), (11,9), (12,17), (13,1) maka dihasilkan generasi akhir 1 pada Tabel 5.
58 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 53-61
fitness
Tabel 4: Hasil Akhir Proses Rekombinasi Pada Generasi Pertama Bentuk Biner
Kromosom 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1
0 0 0
1 1 1 0 1 h 1 1 0 1 1 0 1 1 1 0 1 1 0 1 h 6 0 -OJ 1 0 0 1 1 1 1 1 1 1 0 1 0
0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0
0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0
1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0
0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 0 Total
0 1 0 1 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 1 Fitness
0 0 0 1 0 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0
1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0
1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0
1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0
0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0
X
fitness
13 290 166.106 144.138 213.464 71 052 213.570 70.131 144.138 200.167 106.300 199.973 78.263 49.138 70.131 34.288 202.758 213.464 214.490 166.106 144.138
0 162 0.892 0.980 0498 0.766 0497 0758 0980 0.632 0 891 0.634 0.820 0.567 0 758 0.409 0.607 0.498 0487 0.892 0.980 13.709
X
fitness
13.290 229.856 144.138 213.464 71.052 213.570 66.147 144.138 200.167 166.300 199.475 78.271 176.638 70.131 34.288 202.758 213.464 214.490 166.106 144.138
0.162 0.314 0.980 0.498 0.766 0.497 0.726 0.980 0.632 0.891 0639 0.820 0.827 0.758 0.409 0.607 0.498 0.487 0.892 0.980
Tabel 5: Hasil Akhir Pada Generasi Pertama Bentuk Biner
Kromosom 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1 1 h 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1
0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0
0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0
0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 1
1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 '0 0 1 0 1 0 I 0 0
0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0
1 0 0
0 1 1 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 I 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0
0 0 1 0 0 1 1 1 1
1 0 0 0 1 1 0 0 u 0 1
1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1
0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0
1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1
1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0
1 1 0 1 1 0 0 0 1 1 1 1
1 0 0 1 1 1 1 0
0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 I 0 1 0
Generasi pertama telah dihasilkan dari generasi awal hal ini dilakukan berulang hingga sampai mencapai keadaan optimal atau sejumlah generasi telah dilakukan. Akhirnya generasi ke 100 didapat tabel 6.
Penerapan Algoritma Genetika Untuk Optimasi ... (Samuel Lukas)
59
Generasi pertama telah dihasilkan dari generasi awal hal ini dilakukan berulang hingga sampai mencapai keadaan optimal atau sejumlah generasi telah dilakukan. Akhirnya generasi ke 100 didapat tabel 6. Tabel6: Generasi Ke-100 Kromosom 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Bentuk Biner 1 I 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 I 0 I 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 I) 0 0 0
1 1 1 0 1 1 1 1 1 I 1 1
! 1 1 1
1 1 1 I
1 0 0 0 1 I) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 I 1 0
a
0 0 0 0 0 0 1 0 1 0 1
0 0 0 1 0 0 (]
0 1
0 0 I 0 0 1 0 0 0 0 0 0 I)
0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 I)
0 0
1 1 1 1 1 1 1 0 I 1 1 1 1 1 1 1 1 1 0 1
0 0 0 0 0 0 0 1 0 0 0 0 D 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 •1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1
0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1
X
fitness
151.689 143.721 152.701 135.765 151.704 152.701 153.698 151.580 153.682 151.703 153.702 151.704 183.580 151.705 153.682 151.673 151.704 151.704 151.455 153.682
0.958 0.981 0.954 0.995 0.958 0.954 0.950 0.958 0.951 0.958 0.950 0.958 0.776 0.958 0951 0958 0.958 0.958 0.959 0.951
Total Fitness
18.992
Terlihat bahwa kromosom ke 4 dengan x = 135.765 adalah terbaik dengan nilai fitness = 0.995. 9. ANALISIS HASH PERCOBAAN Secara analisis untuk f(x)=s'm(/tK/256) mempunyai nilai maksimum adalah 1. Dengan pendekatan algoritma genetik maka didapat nilai maksimumnya adalah 0.995. Hal ini terlihat bahwa pendekatan algoritma ini dapat dipakai untuk melakukan optimasi meskipun memerlukan iterasi sebanyak 100 kali. Pengurangan atau penambahan jumlah iterasi sudah tentu dipengaruhi oleh parameter kontrol. Algoritma genetik ini baik dipakai apabila kombinasi kemungkinan jawab berjumlah banyak. Sehingga penentuan jawab secara deterministik menjadi sangat tidak mungkin. Salah satu penerapannya adalah dalam penyelesaian masalah penjadwalan untuk mengoptimasikan misalnya jumlah ruang yang dipakai.
10. KESIMPULAN Dari bahasan diatas maka beberapa eksimpulan dapat diambil sebagai berikut • Prinsip kerja Algoritma Genetik mendekati pola terbentuknya generasi ke generasi berikutnya dari makluk biologis. • Algoritma genetik ini baik dipakai apabila kombinasi kemungkinan jawab berjumlah banyak, dan nondeterministik. • Lamanya proses pengoptimalisasian sangat tergantung pada penentuan parameter kontrol. 60 Jurnal llmiah llmu Komputer, Vol. 2 No. 3 September 2004: 53-61
I
DAFTAR PUSTAKA [1] [2]
Sri Kusumadewi, Artificial Intelligence.Graha llmu, Jogjakarta, 2003. J.S.R.Jang., C.T. Sun, E. Mizutani., Neuro-Fuzzy and Soft Computing, Prentice-Hall International, Inc, 1997.
Penerapan Algoritma Genetika Untuk Optimasi ... (Samuel Lukas)
61
