Genetic Algorithm

Posted by Nanda Bima - - 0 comments

Converted document

GENETIC ALGORITHM

“JGAP (Java Genetic Algorithms Package)”

Dosen : Dr. rer. nat. I Made Wiryana, SKom, SSi, MAppSc

SOFTSKILL

Kelompok 4 :

» Agus Mulyadi

» Deka Sasmita P

» Erlandika A

» Nanda Bima

» Nurjanah

Kata Pengantar

Puji Syukur pada Allah SWT atas nikmat sehat iman dan islam serta semua pertolongannya yang selalu menjaga hati dan pikiran penyusun sehingga dapat menyelesaikan penulisan ini dengan baik.

Penulisan ini disusun guna memenuhi tugas mata kuliah “Pengantar Komputasi Modern”. Penyusun mengucapkan terima kasih kepada Bapak I Made Wiryana selaku dosen pengampu, teman-teman satu tim dan semua pihak yang membantu dalam penyelesaian penulisan buku ini.

Penyusun berharap penulisan ini dapat menambah pengetahuan pembaca dan memberikan gambaran mengenai materi terkait yaitu Algoritma Genetika. Sehingga pembaca dapat menggunakan makalah ini sebagai literatur pendukung dalam pengembangan bidang ilmu selanjutnya yang terkait dengan penggunaan algoritma genetika.

Penyusun menyadari bahwa penulisan ini masih jauh dari kesempurnaan, karena itu penyusun mengharapkan saran dan kritik yang membangun guna memperbaiki penulisan ini. Besar harapan penyusun agar penulisna ini dapat berguna bagi siapapun yang menjadikan penulisan ini sebagai bahan literatur mengenai materi terkait.

Tim Penyusun

BAB 1

PENDAHULUAN

Sekilas Tentang Buku

Optimisasi merupakan suatu upaya sistematis untuk memilih elemen terbaik dari suatu kumpulan elemen yang ada. Didalam kontek matematika, optimisasi ini bisa diyatakan sebagai suatu usaha sistematis untuk mencari nilai minimum atau maksimum dari suatu fungsi. Dengan kata lain, optimisasi merupakan proses mencari nilai terbaik berdasarkan fungsi tujuan dengan daerah asal yang telah didefinisikan.

Dalam perkembangan selanjutnya, optimisasi sangat berkaitan dengan perkembangan komputer karena proses optimisasi ini umumnya dijalankan di komputer. Metode optimisasi sendiri bisa dibagi menjadi metode eksak (exact method atau analitical method) dan metode pendekatan (approximate method). Ciri yang paling khas dari exact method adalah bahwa metode ini akan menghasilkan penyelesaian optimal. Bagaimana bisa tahu bahwa hasil yang diperoleh adalah hasil optimal ? Pembuktiannya dilakukan secara analitis menggunakan metode matematis. Sedangkan metode pendekatan tidak menjamin bahwa hasil penyelesaiannya adalah yang optimal (karena itu disebut metode pendekatan). Tetapi, meskipun metode ini tidak menjamin hasil optimal, tetapi umumnya hasil penyelesaiannya cukup baik. Walaupun definisi baik ini juga sulit, karena bersifat kualitatif. Sehingga seringkali untuk mengukur kualitas baik ini, maka diadakan perbandingan hasil dengan menggunakan metode lain. Suatu metode dikatakan lebih baik jika dia menghasilkan penyelesaian yang lebih bagus daripada metode lainnya.

Metode pendekatan ada bermacam-macam, salah duanya metode heuristik dan metaheuristik. Heuristic sendiri merupakan suatu teknik untuk penyelesaian permasalahan yang tidak menekankan pada pembuktian apakah solusi yang didapatkan adalah benar (pembuktian apakah suatu solusi adalah benar merupakan fokus dari metode penyelesaian analitik), tetapi lebih menekankan pada performa komputasi dan kesederhanaan. Metode heuristik merupakan suatu metode penyelesaian yang menggunakan konsep pendekatan. Sedangkan Metaheuristic dapat didefinisikan sebagai metode lanjut (advanced) berbasis heuristic untuk menyelesaikan persoalan optimisasi secara efficient. Di dalam wikipedia, metaheuristik didefinisikan sebagai metode optimisasi yang dilakukan dengan memperbaiki kandidat penyelesaian secara iteratif sesuai dengan fungsi objektifnya. Metode ini mampu menghasilkan penyelesaian yang baik dalam waktu yang cepat (acceptable), tetapi tidak menjamin bahwa penyelesaian yang dihasilkan merupakan penyelesaian terbaik (optimal). Metode metaheuristik banyak dipakai dalam optimisasi stokastik (optimisasi stokastim merupakan optimisasi yang memiliki derajat ketidakpastian atau random).

Metaheuristic memiliki banyak metode seperti Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization dan Simulated Annealing. Dari sekian banyak metode yang dimiliki, yang paling populer dari Metaheuristic adalah metode Genetic Algorithm. Hal ini disebabkan karena algoritma genetik memiliki performa yang baik untuk berbagai macam jenis permasalahan optimisasi. Algoritma genetik di perkenalkan oleh (Holland, 1975) dalam bukunya “Adaptation in Natural and Artificial Systems”. Adaptasi menjadi prinsip yang penting didalam algoritma genetik. Adaptasi adalah kemampuan untuk menyesuaikan diri dengan lingkungannya, dan didalam algoritma genetik, adaptasi dinyatakan dengan proses memodifikasi struktur individu yang akan meningkatkan kinerja algoritma genetik. Mekanisme kerja algoritma enetic mengikuti fenomena evolusi genetika yang terjadi dalam makhluk hidup.

Buku ini dibuat guna membahas metode yang paling populer tersebut. Dalam buku ini akan dijelaskan apa itu metode algoritma genetik dan bagaimana cara kerja algoritma tersebut.

BAB 2

LANDASAN TEORI

2.1 TENTANG ALGORITMA GENETIK

Pada tahun 1859 Charles Darwin (1809 – 1882), seorang peneliti alam dari Inggris, mengumumkan teorinya yang berjudul “Theory of Natural Selection”. Teori tersebut menyatakan bahwa individu-individu yang mempunyai karakteristik yang bagus (menurut kriteria-kriteria tertentu) akan mempunyai kemungkinan untuk bertahan hidup lebih besar dan bereproduksi dan menurunkan karakteristiknya kepada keturunan-keturunannya. Berlaku sebaliknya, individu-individu dengan karakteristik yang kurang bagus secara perlahan akan tersingkir dari populasi.

Pada alam ini, informasi genetik dari sebuah individu disimpan dalam chromosome, yang terdiri dari sekumpulan gen. Karakteristik dari setiap individu dikendalikan oleh gen-gen tersebut, yang kemudian akan diwariskan kepada keturunan-keturunannya ketika individu tersebut berkembang biak. Selain faktor perkembangbiakan, suatu ketika juga terjadi peristiwa yang disebut mutasi, yang menyebabkan terjadinya perubahan informasi pada chromosome. Berdasarkan teori Darwin tersebut, nilai rata-rata karakteristik dari populasi akan meningkat setiap generasi, seiring dengan bertambahnya individu-individu yang mempunyai kriteria yang bagus dan punahnya individu-individu yang mempunyai kriteria yang buruk.

Terinspirasi dari teori darwin tersebut, pada tahun 1975 John Holland dan timnya menciptakan teori Genetic Algorithm. Ide utama dibalik Genetic Algorithm ini adalah memodelkan proses evolusi alami menggunakan warisan genetika seperti yang diumumkan oleh Darwin. Meskipun diperkenalkan oleh John Holland, penggunaan Genetic Algorithm untuk memecahkan persoalan yang complex didemonstrasikan kemudian (pada tahun yang sama) oleh De Jong, dan kemudian oleh Goldberg pada tahun 1989. Menyesuaikan dengan teori Darwin, dalam Genetic Algorithm digunakan istilah-istilah yang mewakili elemen-elemen dalam teori Darwin tersebut, yaitu:

Population: Merupakan sekumpulan solusi dari permasalahan yang akan diselesaikan menggunakan Genetic Algorithm. Population terdiri dari sekumpulan Chromosome.
Chromosome: Mewakili sebuah solusi yang mungkin (feasible solution) untuk permasalahan yang ingin diselesaikan. Sebuah Chromosome terdiri dari sekumpulan Gen.
Gen: Mewakili elemen-elemen yang ada dalam sebuah solusi.
Parent: Merupakan chromosome yang akan dikenai operasi genetik (crossover).
Offspring: Adalah chromosome yang merupakan hasil dari operasi genetik (crossover).
Crossover: Merupakan operasi genetik yang mewakili proses perkembangbiakan antar individu. Proses crossover ini memerlukan dua buah parent dan menghasilkan satu atau lebih offspring (keturunan).
Mutation: Merupakan operasi genetik yang mewakili proses mutasi dalam perjalanan hidup individu. Mutasi berperan menghasilkan perubahan acak dalam populasi, yang berguna untuk menambah variasi dari chromosome-chromosome dalam sebuah populasi. Detail dari proses mutasi ini juga akan dibahas kemudian.
Selection Procedure: Merupakan proses yang mewakili proses seleksi alam (natural selection) dari teori Darwin. Proses ini dilakukan untuk menentukan parent dari operasi genetik (crossover) yang akan dilakukan untuk menghasilkan keturunan (offspring).
Fitness Value: Merupakan penilaian yang menentukan bagus tidaknya sebuah chromosome. Chromosome yang mempunyai Fitness Value yang rendah pada akhirnya akan tersingkir oleh chromosome-chromosome yang mempunyai Fitness Value yang lebih baik.
Evaluation Function: Merupakan fungsi yang digunakan untuk menentukan nilai dari Fitness Value. Evaluation Function ini merupakan sekumpulan kriteria-kriteria tertentu dari permasalahan yang ingin diselesaikan.
Generation: Merupakan satuan dari populasi setelah mengalami operasi-operasi genetika, berkembang biak, dan menghasilkan keturunan. Pada akhir dari setiap generation, untuk menjaga agar jumlah chromosome dalam populasi tetap konstan, chromosome-chromosome yang mempunya Fitness Value yang rendah dan memiliki peringkat dibawah nilai minimal akan dihapus dari populasi.

Genetic Algorithm merupakan metode pembelajaran heuristic yang adaptif, karena itu bisa jadi terdapat beberapa versi dari Genetic Algorithm, yang menyesuaikan dengan permasalahan yang dihadapi. Genetic Algorithm juga merupakan algoritma yang efektif dan sederhana dan relatif mudah untuk diimplementasikan. Genetic Algorithm memiliki keunggulan-keunggulan dibandingkan dengan metode-metode heuristic yang lain, yaitu:

Genetic Algorithm menyelesaikan masalah dengan mengkodekan permasalah menjadi chromosome, bukan dengan menyelesaikan permasalahan itu sendiri. Karena itu diperlukan pemodelan chromosome yang baik dan efektif yang dapat mewakili solusi dari permasalahan yang dihadapi.
Genetic Algorithm memulai prosesnya dengan sekumpulan initial solutions, berbeda dengan metaheuristic lain seperti Simulated Annealing dan Tabu Search yang memulai proses dengan sebuah solusi tunggal, dan berlanjut ke solusi lainnya melalui suatu transisi. Karena itu GA melakukan pencarian multi-directional dalam solution space, yang memperkecil kemungkinan berhentinya pencarian pada kondisi local optimum.
Hanya diperlukan sebuah fungsi evaluasi tunggal yang berbeda untuk tiap permasalahan.
Genetic Algorithm merupakan algoritma yang ‘buta’, karena GA tidak mengetahui kapan dirinya telah mencapai solusi optimal.

Seperti yang telah disebutkan sebelumnya, Genetic Algorithm dapat dengan mudah beradaptasi dengan berbagai macam permasalahan, sehingga ada banyak versi dari Genetic Algorithm, tergantung dari permasalahan yang ingin dipecahkan. Tapi secara umum Genetic Algorithm harus memenuhi kriteria-kriteria dibawah ini untuk menghasilkan solusi yang optimal:

Sebuah representasi yang tepat dari sebuah solusi permasalahan, dalam bentuk chromosome.
Pembangkit populasi awal. Umumnya populasi awal dibangkitkan secara acak, namun untuk beberapa kasus juga bisa dibangkitkan melalui metode-metode tertentu. Penggabungan keduanya (pembangkitan populasi awal secara acak dan menggunakan metode-metode tertentu) disebut dengan seeding. Populasi awal yang dihasilkan sebaiknya bersifat heterogen, karena jika populasi yang terbentuk terlalu homogen, Genetic Algorithm kehilangan kemampuannya untuk mencari dalam solution space, sampai populasi mempunyai variasi chromosome yang beragam melalui operasi genetik lain (mutation).
Sebuah evaluation function untuk menentukan fitness value dari tiap solusi.
Genetic Operator, mensimulasikan proses reproduksi (perkembangbiakan) dan mutasi.
Parameter-parameter lain, seperti kapasitas populasi, probabilitas dari operasi-operasi genetik, dan semacamnya.

Kapasitas populasi sangat mempengaruhi kemampuan Genetic Algorithm dalam mencari solusi. Kapasitas populasi yang terlalu kecil menyebabkan kurangnya variasi chromosome yang muncul, sehingga dapat menyebabkan hasil akhir yang buruk. Kapasitas populasi yang besar biasanya memberikan hasil yang lebih baik, dan mencegah terjadinya konvergensi yang prematur.

2.2 PROSEDUR ALGORITMA GENETIK

Suatu Genetic Algorithm standar membutuhkan dua hal untuk didefinisikan, yaitu :

Sebuah genetic representation dari sebuah solution domain (domain solusi),
Sebuah fitness function untuk mengevaluasi sebuah domain solusi.

Representasi standar dari solusinya adalah sebuah array of bits (Larik bit). Larik dari tipe laen atau struktur lain juga bisa digunakan. Properti utama yang membuat representasi genetic ini baik adalah bagian-bagiannya yang bisa diakses dengan mudah karena ukuran yang pasti (fixed), yang memudahkan suatu operasi persilangan yang sederhana. Representasi panjang variabel juga digunakan disini, tetapi implementasi persilangan jauh lebih sulit pada kasus ini.

Fungsi penghitung nilai kecocokan (fitness) didefinisikan pada representasi genetic dan digunakan untuk mengukur kualitas (quality) pada solusi yang direpresentasikan. Fungsi penghitung ini selalu tergantung pada masalah yang ada (problem dependent). Sebagai contoh, pada knapsack problem, kita ingin memaksimalkan nilai total objek yang bisa dimasukkan ke knapsack (karung) yang memiliki kapasitas tertentu. Representasi solusinya mungkin bisa sebuah larik bit, dimana setiap bitnya merepresentasikan obyek yang berbeda, dan nilai dari bitnya (0 atau 1) merepresentasikan apakah obyek itu ada di knapsack atau tidak. Tidak setiap representasi solusi valid, karena bisa saja jumlah total obyek-obyeknya melebihi kapasitas dari knapsack itu sendiri.

Setelah kita memiliki representasi genetik dan sebuat fungsi untuk mencari nilai kecocokan (fitness) terdefinisi, maka Genetic Algorithm akan melanjutkan untuk membentuk suatu populasi acak, kemudian meningkatkannya melalui aplikasi yang berulang-ulanng dari mutasi, persilangan, dan operator seleksi.

Tahapan-tahapan dalam GA diantaranya yaitu :

Initialization

Pada awalnya solusi individual akan secara acak dibuat dalam bentuk sebuah inisial populasi. Besar populasinya sangat tergantung pada keadaan masalah itu sendiri, tapi biasanya populasi mengandung sekitar beberapa ratus atau bahkan ribuan solusi yang mungkin. Secara sederhana, populasinya dibuat secara acak, dengan mengcover seluruh kemungkinkan solusi (search space). Cara lainnya, solusinya mungkin bisa di “seeded” pada area dimana kemungkinan besar ditemukan solusi optimalnya.

Selection

Seiring dengan berjalannya algoritma, suatu bagian pada populasi akan dipilih (selected) untuk membuat suatu generasi baru. Solusi individual tersebut dipilih melalui suatu fitnessbased process, dimana solusi pencocok (fitter, yang diukur oleh suatu fitness function) akan menyatakan kemungkinan terpilih. Beberapa metode seleksi menggunakan nilai kecocokan tersebut dan kemudian memilih solusi terbaik dari situ. Metode lain hanya menggunakan solusi acak dari populasi, sehingga proses ini mungkin akan memakan waktu lama. Metode seleksi yang populer dan telah teruji antara lain roulette wheel selection dan tournament selection.

Reproduction

Langkah selanjutnya adalah dengan membuat generasi kedua dari populasi yang ada melalui genetic-operator: crossover (persilangan), dan atau mutation (mutasi). Untuk setiap solusi baru yang dibentuk, sebuah pasangan “parent” atau orang tua solusi dipilih dari kumpulan populasi sebelumnya. Dengan membuat sebuah “child” atau anak solusi menggunakan metoda diatas, yaitu persilangan dan mutasi, sebuah solusi baru telah dibuat, dimana pada umumnya akan memwarisi bagianbagian dari orang tuanya. Orang tua baru dipilih lagi dan membuat suatu anak solusi lagi, dan berlanjut sampai suatu populasi solusi baru dengan ukuran yang cukup terbentuk. Secara umum rata-rata nilai kecocokannya (fitness) akan meningkat melalui prosedur ini, karena hanya organisme terbaik yang dipilih dalam pembentukan populasi selanjutnya.

Termination

Proses diatas akan terus dilakukan sampai suatu kondisi terminasi/berhenti ditemukan. Kondisi terminasi/berhenti yang umum dipergunakan yaitu : Suatu solusi ditemukan yang memenuhi kriteria minimum; Generasi telah mencapai suatu tingkat tertentu; Budget yang dialokasikan (misalnya waktu komputasi) telah dicapai; Solusi dengan nilai kecocokan tertinggi akan mencapai atau telah mencapai suatu batas dimana proses selanjutnya yang akan dilakukan tidak akan menghasilkan hasil yang lebih baik; Inspeksi secara manual dan berkala; Kombinasi dari berbagai macam cara terminasi di atas.

Algoritma pseudo-code

Memilih atau membuat suatu populasi inisial.
Menghitung nilai kecocokan (fitness) untuk setiap individu pada populasi tersebut.
Proses pengulangan

Memilih beberapa individu yang memiliki nilai kecocokan tertinggi untuk melakukan proses reproduksi.
Membuat suatu generasi baru melalui proses persilangan dan mutasi (operasi genetika) sehingga akan memberikan kelahiran pada beberapa bibit unggul.
Menghitung nilai kecocokan individual pada bibit unggul tersebut.
Mengganti individu dengan rangking terburuk pada populasi sebelumnya dengan bibit unggul hasil operasi genetika tadi.

4. Sampai mencapai suatu kondisi terminasi yang sesuai.

Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah allele yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukan crossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahan knapsack atau pengepakan, dimana ada beberapa barang dengan jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung olehk napsack tanpa harus menambah kapasitasnya.

Istilah-istilah yang digunakan dalam Algoritma genetika ini hampir sama dengan istilah-istilah yang dipakai dalam bidang biologi genetika, antara lain Gen, Kromosom, Populasi, Fungsi Fitness, dan operator genetika yang meliputi mutasi dan crossover.

Gen

Gen adalah suatu sel dari suatu kromosom atau nilai yang terdapat dalam Algoritma genetika ini dapat dibentuk oleh sebuah byte bahkan tidak menutup kemungkinan suatu string. Gen ini mewakili sebagian kecil dari solusi permasalahan.

Kromosom

Individu dalam populasi disebut string, genotype atau kromosom-kromosom terdiri dari unit-unit yang dinamakan Gen, Karakter, Decoder. Kromosom ini dapat mewakili suatu solusi, dimana dapat diilustrasikan dalam gambar dibawah ini:

Untuk mempresentasikan kromosom dilakukan dengan proses encoding, dibawah ini akan dijelaskan beberapa proses encoding yang biasa digunakan dalam beberapa kasus tertentu.

Permutation_Encoding

Untuk jenis Permutation Encoding ini digunakan untuk permasalahan proses pengurutan, misalnya terdapat kasus optimasi jadwal atau pada kasus traveling salesman. Pada Permutation Encoding, setiap Gen pada kromosom berupa angka dimana dapat ditampilkan seperti gambar di bawah ini:

Permutation Encoding hanya berlaku untuk permasalahan pengurutan, untuk itu dalam kasus-kasus yang ada pada Permutation Encoding terdapat beberapa jenis crossover dan mutasi yang harus dibuat untuk mempertahankan kromosom agar tetap konsisten. Contoh penggunaan Permutation Encoding ini adalah pada kasus trvelling salesman, dimana terdapat beberapa kota dengan jarak masing-masing. Pada kasus traveling salesman ini seorang salesman harus mengunjungi semua kota yang ada, tetapi tidak harus berjalan jauh untuk mencapai seluruh kota. Permasalahanya adalah menentukan urutan kota yang akan dikunjungi untuk meminimalisasi jarak yang harus ditempuh.

Binary_encoding

Binary encoding adalah jenis encoding yang paling sering digunakan karena kasus pertama yang ada pada Algiritma Genetik menggunakan algoritma jenis ini. Setiap kromosom pada Binary encoding merupakan bit 0 dan 1 dimana dapat ditampilkan pada gambar bawah:

Binary encoding dapat memberikan banyak kemungkinan pada kromosom meskipun pada jumlah Gen yang sedikit. Dilain pihak jenis encoding ini tidak cukup natural untuk beberapa kasus tertentu dan kadang-kadang harus dilakukan koreksi setelah melakukan crossover atau mutasi, contoh penggunaan Binary encoding adalah pada permasalahan knapsack atau pengepakan, dimana ada beberapa barang dengna jumlah dan ukuran masing-masing dan knapsack harus memberikan kapasitasnya untuk barang-barang tersebut, permasalahanya adalah bagaimana memilih barang untuk memaksimalkan jumlah barang sehingga dapat ditampung oleh knapsack tanpa harus menambah kapasitasnya.

Crossover

Crossover adalah operator algoritma genetika yang membutuhkan parameter dua kromosom. Dua buah kromosom tersebut disebut kromosom induk. Operator ini akan menghasilkan dua buah kromosom baru. Ada beberapa jenis crossover yang sering digunakan dalam algoritma genetika antara lain:

Ordered Based Crossover

Ordered based Crossover diawali dengan menentukan posisi-posisi gen secara random pada induk pertama misalnya didapatkan posisi 3,4,6 dan 9 pada induk.

P1= ( 1 2 3 4 5 6 7 8 9 )

P1= ( 4 5 2 1 8 7 6 9 3 )

Kemudian Gen-gen pada induk yang berada tepat dibawah posisi-posisi tersebut dicatat yaitu 2,1,7 dan 3 untuk Q1 disalin dari P1 dengan menghilangkan angka-angka 2,1,7 dan3 tersebut sehingga menjadi

Q1= ( x x x 4 5 6 x 8 9 )

Subset 2,1,7, dan 3 ini di masukan dalam Q1 dimulai dari kiri dengan mempertahankan urutan sehingga menjadi

Q1 = (2 1 7 4 5 6 3 8 9)

Untuk Q2 diperlukan sama hanya perlu meukar induk pertama menjadi induk kedua dan induk kedua menjadi induk pertama yang menjadi:

Q2 = (3 5 2 1 8 7 4 6 9)

One-Point Crossover

Contoh kerja operator ini adalah dengan menentukan crossover point (gen tertentu). Kromosom baru pertama berisi gen pertama sampai gen crossover point dari kromosom induk pertama ditambah dengan gen dari crossover point sampai gen terakhir dari kromosom induk kedua. Kromosom baru kedua berisi gen pertama sampai gen crossover point dari induk kedua ditambahkan dengan gen dari crossover point sampai gen dari kromosom induk pertama. Adapun metode crossover ini dapat diilustrasikan pada gambar berikut:

Dari ilustrasi di atas maka contoh penerapan metode One-Point Crossover adalah sebagai berikut:

Parent 1: 1 2 3 4 5 | 6 7 8 9

Parent 2: 4 5 3 6 8 | 9 7 2 1

Setelah proses crossover turunan yang dapat dihasilkan adalah dari kedua parent diatas adalah:

Parent 1: 1 2 3 4 5 | 9 7 2 1

Parent 2: 4 5 3 6 8 | 6 7 8 9

Two-Point Crossover

Proses Two-Point Crossover hampir sama dengan prosedur One-Point Crossover, kecuali pada Two-Point Crossover harus dipilih dua crossover point dan hanya gen yang ada di antara kedua crossover point itu yang akan ditukarkan.

Metode ini dapat menjadi bagian awal dan akhir dari kromosom dan hanya menukar bagian tengahnya saja.

N-Point Crossover

Prosedur N-Point Crossover hampir sama baik dengan prosedur one-point crossover maupun two-point crossover, hanya saja dalam n-point crossover ini harus dipilih n crossover point dan hanya gen di antara crossover point ganjil dan genap yang dapat ditukarkan sedangkan gen diantara genap dan ganjil operator crossover tidak berubah. Atau dengan kata lain harus dipilih posisi n dan hanya bit antara ganjil dan genap posisi crossover yang akan dihilangkan.

Contoh: P1= 9 7 6 3 2 8

P2= 2 1 9 7 4 5

Jika didapatkan angka random untuk n=3 dan diacak 1,2 dan 4 sebagai posisi dari gen yang akan di crossover, didapatkan kromosom turunan:

T1= 9 1 6 3 4 5

T2= 2 7 9 7 2 8

2.3 Mutasi

Mutasi adalah operator yang membutuhkan satu perameter. Kromosom operator ini merupakan nilai suatu gen dari sebuah kromosom sehingga kromosom yang baru ini berbeda dengan kromosom yang lama. Sekumpulan kejadian dengan suatu nilai pelanggaran maksimal dapat dengan mudah dihilangkan selama evaluasi fitness “tujuan dari proses mutasi ini, untuk mempertahankan kehilangan permanent dari suatu bit atau gen” (Whitley,1993:16). Seluruh proses mutasi ini menjanjikan keuntungan melalui pengarahan mutasi kemana mutasi ini tersebut sangat dibutuhkan. Oprator mutasi digunakan untuk melakukan modifikasi satu atau lebih dari nilai gen dalam individu yang sama. Mutasi memastikan bahwa probabilitas untuk pencarian pada daerah tertentu dalam persoalan tidak akan pernah nol dan mencegah kehilangan total materi genetika setelah pemilihan dan penghapusan. Mutasi ini bukanlah operator genetika yang utama, yang dilakukan secara acak pada gen dengan kemungkinan yang lebih kecil. Metode ini disebut metasi gen (gene mutation) terdapat metode lain yaitu: “order mutation” dimana dimungkinkan untuk menghilangkan seluruh gen dari dua gen yang dipilih secara acak. Terdapat empat operator yang biasa digunakan untuk permasalahan penjadwalan antara lain:

2.3.1 Violation Directed Mutation (VDM)

Memilih sutatu kejadian dengan suatu nilai pelanggaran maksimal, dan secara acak mengubah waktu penugasan.

2.3.2 Event Freeing Mutation (EFM)

Memilih suatu kejadian dengan sauatu pelanggaran maksimal, kemudian memberi waktu baru yang mana akan mengurangi secara maksimal angka ini.

Secara stokastik memilih suatu kejadian ,bias melalui kejadian itu dengan nilai pelanggaran yang tinggi, kemudian secara stokastik memilh waktu baru untuk kejadian ini, bisa melalui waktu yang mana akan mengurangi secara maksimal angka pelanggaran kejadian.

2.3.3 Fungsi Objektif

Fungsi objektif adalah tujuan dari optimasi permasalahan. Biasanya fungsi objektif ini hanya dua macam yaitu memaksimalkan dan meminimalkan.

2.3.4 Model Pengembangan Algoritma Genetika

Algoritma genetika menyelesaikan permasalahan dengan cara menghasilkan, mengubah dan mengevaluasi kandidat solusi dari permasalahan tersebut. Awalnya sebuah populasi acak yang terdiri dari kromosom-kromosom di hasilkan kemudian kromosom-kromosom itu diubah oleh operator genetika yaitu crossover dan mutasi, kemudian kromosom-kromosom tersebut dievaluasi oleh fungsi fitness.

Terdapat beberapa cara dalam menentukan inisialisasi diantaranya biner dan non biner. Untuk inisialisasi masalah penjadwalan yang paling sederhana dapat dilihat sebagai masalah penetapan V even atau kejadian dalam S selang waktu dengan kata lain definisi dari masalah penjadwalan adalah:

E adalah definisi dari sejumlah V even (e1.e2,….en)

T adalah definisi dari sejumlah S selang waktu (t1,t2,…tn)

2.4 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. Diagram alir dari algoritma genetika untuk menyelesaikan permasalahan diatas dapat dilihat pada Gambar 1.

Penjelasan mengenai langkah-langkah penyelesaian permasalahan diatas menggunakan algoritma genetika adalah sebagai berikut:

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.
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]
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)

= Abs((12 + 10 + 9 + 32 ) - 30)

= Abs(63 - 30) = 33

fungsi_objektif(chromosome[2])

= Abs(( 2 + 2*1 + 3*8 + 4*3 ) - 30)

= Abs(( 2 + 2 + 24 + 12 ) - 30)

= Abs(40 - 30) = 10

fungsi_objektif(chromosome[3])

= Abs(( 10 + 2*4 + 3*3 + 4*4 ) - 30)

= Abs(( 10 + 8 + 9 + 16 ) - 30)

= Abs(43 - 30) = 13

fungsi_objektif(chromosome[4])

= Abs(( 20 + 2*1 + 3*10 + 4*6 ) - 30)

= Abs(( 20 + 2 + 30 + 24 ) - 30)

= Abs(76 - 30) = 46

fungsi_objektif(chromosome[5])

= Abs(( 1 + 2*4 + 3*3 + 4*9 ) - 30)

= Abs(( 1 + 8 + 9 + 36 ) - 30)

= Abs(54 - 30) = 24

fungsi_objektif(chromosome[6])

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

= Abs(( 20 + 10 + 21 + 4) - 30)

= Abs(55 - 30) ) = 25

Rata-rata dari fungsi objektif adalah:

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

= 151 / 6

= 25.167
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 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)

= 1 / 34

= 0.0294

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

= 1 / 11

= 0.0909

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

= 1 / 14

= 0.0714

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

= 1 / 47

= 0.0212 fitness[5]

= 1 / (fungsi_objektif[5]+1)

= 1 / 25

= 0.0400

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

= 1 / 26

= 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. 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]

2.5 Aplikasi Algoritma Genetika

Algoritma genetika banyak diaplikasikan untuk berbagai macam permasalahan, yaitu :

Optimasi Beberapa penggunaan algoritma genetika untuk optimasi antara lain untuk optimasi numerik dan optimasi kombinatorial seperti Traveling Salesmen Problem (TSP), 6 Perancangan Integrated Circuit atau IC, Job Scheduling, dan Optimasi video dan suara.
Pemrograman Otomatis. Algoritma genetika untuk pemrograman otomatis antara lain untuk melakukan proses evolusi terhadap program komputer dalam merancang struktur komputasional, seperti cellular automata dan sorting networks.
Machine Learning. Algoritma genetika juga telah berhasil diaplikasikan untuk memprediksi struktur protein. Algoritma genetika juga berhasil diaplikasikan dalam perancangan neural networks (jaringan syaraf tiruan) untuk melakukan proses evolusi terhadap aturanaturan pada learning classifier system atau symbolic production system dan dapat digunakan untuk mengontrol robot.
Model Ekonomi. Dalam bidang ekonomi, algoritma genetika digunakan untuk memodelkan prosesproses inovasi dan pembangunan bidding strategies.
Model Sistem Imunisasi. Contoh penggunaan algoritma genetika dalam bidang ini untuk memodelkan berbagai aspek pada sistem imunisasi alamiah, termasuk somatic mutation selama kehidupan individu dan menemukan keluarga dengan gen ganda (multi gen families) sepanjang waktu evolusi.
Model Ekologis Algoritma genetika juga dapat digunakan untuk memodelkan fenomena ekologis seperti host-parasite co evolutions, simbiosis dan aliran sumber di dalam ekologi.
2.6 Keuntungan Menggunakan Algoritma Genetika

Keuntungan penggunaan algoritma genetika terlihat dari kemudahan implementasi dan kemampuannya untuk menemukan solusi yang optimal dan bisa diterima secara cepat untuk masalah-masalah berdimensi tinggi. Algoritma Genetika sangat berguna dan efisien untuk masalah dengan karakteristik sebagai berikut :

Ruang masalah sangat besar, kompleks, dan sulit dipahami,
Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit,
Tidak tersedianya analisis matematika yang memadai,
Ketika metode-metode konvensional sudah tidak mampu menyelesaikan masalah yang dihadapi,
Solusi yang diharapkan tidak harus paling optimal, tetapi cukup “bagus” atau bisa diterima,
Terdapat batasan waktu, misalnya dalam real time system atau sistem waktu nyata.
2.7 Struktur Algoritma Genetika

Procedure Genetic_Algorithm

Begin

Pt = 0

Generate initial population Pt

Evaluate population Pt

While stopping criteria not

satisfied Repeat

Begin

Pt = Pt+l

Select elements from Pt-1 to

copy into Pt

Crossover elements of Pt

Mutation elements of Pt

Evaluate new population Pt

End;

Penjelasan procedure Genetic Algorithm :

1. Begin

2. Pt = 0 Set generasi awal =0.

3. Generate initial population Pt Pembentukan populasi awal dari n individu ( kromosom ) secara random atau dipilih menurut metode tertentu. Setiap individu merepresentasikan suatu kandidat solusi bagi suatu masalah.

4. Evaluate population Pt Mengevaluasi individu-individu yang terbentuk pada populasi awal berdasarkan nilai fitness.

5. While stopping criteria not satisfied Repeat Jika belum memenuhi kondisi pemberhentian, maka algoritma genetika masuk ke dalam suatu loop proses genetika.

6. Begin

7. Pt = Pt+l

8. Select elements from Pt-1 to copy into Pt Memilih kromosom dari populasi menurut nilai fitness, semakin besar fitness semakin besar kemungkinan diseleksi. Populasi akan dibentuk melalui suatu pemilihan dari alternative solusi pada P(t) secara random.

9. Crossover elements of Pt Proses crossover dua kromosom bergabung menghasilkan dua keturunan, dengan menentukan titik crossover secara random.

10. Mutation elements of Pt Mutasi merupakan proses pengubahan satu atau lebih gen.

11. Evaluate new population Pt Memeriksa kromosom-kromosom yang terbaik.

12. End

13. End

Algoritma Genetika memiliki karakteristik yang khas yaitu :

1. Mengkodekan satu set parameter, bukan per parameter.

2. Melakukan pencarian dari sekumpulan titik bukan titik tungggal. Pencarian dilakukan dari generasi ke generasi sampai diperoleh solusi potensial.

3. Menggunakan fungsi fitness, bukan ilmu genetika turunan. Nilai fungsi fitness kembali pada pencarian secara langsung.

2.8 Parameter-parameter Algoritma Genetika

Parameter-parameter tersebut adalah :

1. Ukuran Populasi (pop_size) Populasi adalah kumpulan beberapa individu yang sejenis yang hidup dan saling berinteraksi bersama pada suatu tempat. Jumlah individu dinyatakan sebagai ukuran dari populasi tersebut.

2. Laju crossover Pada saat proses genetika berlangsung, nilai dari laju crossover digunakan untuk menentukan individu-individu yang akan mengalami crossover.

3. Laju mutasi Nilai dari laju mutasi digunakan untuk menentukan individu yang akan mengalami mutasi, terjadi setelah proses crossover dilakukan.

4. Banyaknya gen dalam kromosom

5. Satu individu direpresentasikan sebagai sebuah kromosom yang terdiri dari sejumlah gen yang membentuk satu kesatuan.

2.9 Nilai Fitnes

Nilai fitness adalah nilai yang menyatakan baik tidaknya suatu individu. Semakin besar nilai fitness yang dimiliki suatu individu, maka semakin besar pula kesempatan individu tersebut untuk tetap bertahan atau berkembangbiak. Algoritma genetika bertujuan mencari individu dengan nilai fitness yang paling tinggi.

2.10 Pembentukan Populasi Awal

Membangkitkan populasi awal adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Syarat-syarat yang harus dipenuhi untuk menunjukkan suatu solusi harus benar-benar diperhatikan dalam pembangkitan setiap individunya.

2.11 Reproduksi dan Seleksi

Reproduksi adalah tahap pengkopian stringstring kromosom berdasarkan suatu kriteria [1]. Seleksi merupakan proses memilih kromosom induk dari populasi.

Dalam tahap reproduksi dan seleksi menggunakan nilai fitness untuk memilih kromosom yang akan dijadikan kromosom induk. Semakin besar nilai fitness kromosom maka akan semakin besar pula kemungkinan diseleksi. Macam-macam seleksi :

1. Mesin roulette.

2. Turnamen.

Seleksi mesin roullete untuk memilih induk dilakukan dengan menggunakan prosentasi fitness setiap individu, di mana setiap individu mendapatkan luas bagian sesuai dengan prosentase nilai fitnessnya. Sedangkan seleksi turnamen untuk memilih individu dilakukan dengan kompetisi dari tiap individu, individu yang terpilih merupakan individu pemenang. Seleksi mesin roullete lebih memberikan variansinya dibandingkan seleksi turnamen.

2.12 Perkawinan Silang (Crossover)

Perkawinan Silang atau Crossover merupakan proses mengkombinasikan dua individu untuk memperoleh individu-individu baru yang diharapkan mempunyai fitness lebih baik. Crossover menukar bagian dari 2 kromosom induk yang berbeda, bekerja menggabungkan 2 kromosom induk dengan cara penyilangan untuk menghasilkan 2 individu baru. Tidak semua pasangan induk mengalami proses crossover, banyaknya pasangan induk yang mengalami crossover ditentukan dengan nilai laju crossover dan dilakukan secara acak. Sehingga pemilihan laju crossover yang tepat akan semakin mempercepat pencarian suatu hasil yang diinginkan begitu juga sebaliknya.

2.13 Mutasi

Mutasi adalah penggantian satu atau lebih gen dalam suatu kromosom yang terjadi tanpa melibatkan kromosom yang lain. Pada kromosom biner, mutasi dilakukan dengan mengubah gen biner 0 menjadi 1 dan 1 menjadi 0.

Probabilitas mutasi yang baik berada pada kisaran 0 sampai dengan 0.3. Probabilitas mutasi yang terlalu kecil menyebabkan terjebak dalam optimum lokal, dan probabilitas mutasi yang terlalu besar menyebabkan konvergensi sulit didapatkan.

2.14 Evaluasi

Penyeleksian kromosom-kromosom yang terpilih dilakukan dalam tahap ini. Setiap kromosom hasil crossover dan mutasi akan dilihat apakah lebih baik dari kromosom sebelumnya ataukah sebaliknya.

2.15 Terminasi (batasan iterasi generasi)

Dalam proses algoritma genetika, untuk menghentikan proses regenerasi yang berlangsung diadakan Stopping criteria yang mempunyai definisi sesuai dengan kebutuhan . Misal proses regenerasi akan berhenti jika generasi berikutnya menghasilkan individu yang sama dari individu sebelumnya.

BAB 3

JGAP (Java Genetic Algorithms Package)

3.1 Sekilas Tentang JGAP

JGAP (Hava Genethic Algorithm Pakcage) adalah suatu framework yang ditulis dengan bahasa java. JGAP berbeda dengan aplikasi lainnya. JGAP tidak bisa diinstall seperti file executable lainnya. Tetapi terdapat contoh yang diberikan oleh JGAP yang dapat dijalankan dengan menggunakan baris perintah (atau file batch).

JGAP (nama lain: JAY-GAP) adalah Algoritma Genetik dan Komponen Pemrograman Genetik seperti framework java. Disediakan mekanisme genetik dasar yang dapat digunakan dengan mudah untuk menerapkan prinsip evolusioner untuk menyelesaikan masalah.

JGAP telah di desain agar mudah untuk digunakan, juga di desain dengan sangat modular sehingga pengguna dapat dengan mudah mengkostumisasi operasi genetik dan sub-komponen lainnya.

Dokumentasi, kualitas dan stabilitas kode adalah hal yang utama dalam mengembangkan JGAP. Tersedia banyak paket Unit Tes dengan JGAP (>1400), extensive javadocs dan tentunya dengan contoh yang banyak. JGAP dapat digabungkan dengan proyek lainnya.

3.2 Instalasi JGAP

Untuk menginstall JGAP tidak seperti menginstall file exectutable lainnya. Namun penginstallan JGAP sangat mudah untuk dilakukan. Berikut langkahnya:

- Pastikan anda memiliki file (jgap_xxx_full.zip). Bila tidak ada anda dapat mengunduh JGAP Pakcage dari jgap.sourceforge.net.

- Extract file ke direktori yang anda inginkan, beri nama direktori jgap-current.

- Buka direktori pada file manager, Seperti windows explorer untuk Windows atau yang lainnya untuk sistem UNIX.

- Pada direktori tempat mengekstrak JGAP, terdapat beberapa file yang memiliki ekstensi .jar. File-file inilah yang akan digunakan untuk mengkompilasi JGAP dan cukup itu saja yang dibutuhkan.

3.3 Cara menjalankan Example

- Untuk Windows : Mulai example dengan mengeksekusi file start_example.bat

Untuk Linux dan sistem operasi lainnya : Buka command line dan masuk kedalam direktori tempat mengekstrakk JGAP (jgap-current). Sekarang ketikkan: “java -classpath ".;jgap-examples.jar;jgap.jar" examples.MinimizingMakeChange 89” tanpa tanda kutip.

- Bila anda menggunakan dari external libraries, anda perlu mengambahkan file .jar ini ke dalam class path seperti langkah 5. Sebagai contoh, bila anda menjalankan class utilitas “WeightedRouletteSelector” class pada pakcage org.jgap.impl anda perlu menambahkan file lib/trove-2.0.2.jar ke dalam classpath.

- Bila berhasil menjalankan example maka akan muncul file seperti ini pada layar konsol:

3.4 Investigasi Sourcedan Tes Kasus

JGAP dapat dan di kompilasi dengan java versi 5 ke atas. Bila anda menggunakan java versi 1.4 maka tidak akan dapat melakukan banyak modifikasi. Jika anda ingin memulai pengkodingan algoritma genetik dengan JGAP, menggunakan example yang disediakan JGAP adalah awal yang baik.

Untuk lebih mengetahui cara kerja di balik layar, investigasi ke dalam tes kasus. Anda akan menemukannya di bawah sub direktori tes. Ini sangat membantu dalam belajar bagaimana mengerti cara kerja JGAP.

3.5 Memulai JGAP

Harap dicatat bahwa dokumentasi ini dapat berkorelasi dengan versi terdahulu JGAP. Oleh karena itu kami sarankan memiliki melihat contoh yang diberikan dengan JGAP dan kemudian membaca dokumen ini untuk mendapatkan ide.

Untuk menggunakan JGAP dalam sebuah aplikasi, ada lima hal dasar yang harus Anda lakukan:

1. Rencanakan kromosomAnda.

2. Terapkan sebuah “Fungsi Kebugaran”.

3. Atur konfigurasi objek

4. Buat sebuah populasi berdasarkan solusi potensial.

5. Kembangkan populasi!

Melalui rangkaian tutorial ini, kita akan membangun sebuah contoh program sederhana yang menggunakan JGAP. Tujuan dari program kami adalah untuk menghasilkan jumlah yang ditentukan pengguna dari perubahan dalam koin Amerika paling sedikit mungkin (perempat, dime, sen, dan uang).

3.5.1 Plan your Chromosome

Jantung dari algoritma genetika adalah kromosom tersebut. Kromosom ini merupakan solusi potensial dan dibagi menjadi beberapa gen. Gen di JGAP mewakili aspek yang berbeda dari solusi secara keseluruhan, seperti gen manusia merupakan aspek yang berbeda dari orang-orang individu, seperti jenis kelamin atau warna mata. Selama proses evolusi JGAP, kromosom yang terkena beberapa operator genetik yang mewakili kawin, mutasi, dll dan kemudian dipilih untuk generasi berikutnya selama fase seleksi alam berdasarkan "kebugaran," mereka yang merupakan ukuran seberapa optimal bahwa solusi adalah relatif terhadap solusi potensial lainnya. Seluruh Tujuan dari algoritma genetika adalah untuk meniru proses alami evolusi untuk menghasilkan solusi superior.

Oleh karena itu, adalah untuk memutuskan susunan kromosom Anda, yang mencakup berapa banyak gen yang Anda inginkan dan apa yang gen-gen akan mewakili. Dalam contoh program kami, kami ingin membuat tumpukan perubahan yang berisi mungkin koin Amerika paling sedikit yang total sampai dengan jumlah yang ditentukan oleh pengguna. Karena kromosom merupakan solusi potensial, dalam sampel kami akan mewakili tumpukan perubahan. Kami akan mengatur gen kita untuk mewakili denominasi koin sehingga kita akan memiliki total empat gen per kromosom (masing-masing untuk kuartal, dime, sen, dan uang).

(Diagram darikromosomdenganempat gen: quarters, dimes, nickels, and pennies)

Kami benar-benar akan menulis kode untuk setup objek Kromosom kami pada langkah 3.

3.5.2 Terapkan Sebuah Fungsi Kebugaran

JGAP dirancang untuk melakukan hampir semua pekerjaan evolusi untuk Anda dengan cara yang relatif generik. Namun, ia tidak memiliki pengetahuan tentang masalah khusus Anda benar-benar mencoba untuk memecahkan, dan karenanya tidak memiliki cara intrinsik memutuskan apakah salah satu solusi potensial adalah lebih baik daripada solusi lain yang potensial untuk masalah khusus Anda. Di situlah fungsi fitness datang: itu adalah metode tunggal yang harus Anda menerapkan yang menerima solusi masalah potensial dan mengembalikan nilai integer yang menunjukkan seberapa baik (atau "cocok") solusi yang relatif terhadap solusi lain yang mungkin. Semakin tinggi angkanya, semakin baik solusinya. Semakin rendah nomor (1 menjadi nilai fitness hukum terendah), yang miskin solusi. JGAP akan menggunakan pengukuran kebugaran ini berkembang populasi solusi terhadap satu set yang lebih optimal dari solusi.

Mari kita mulai dengan contoh sepenuhnya kerja fungsi fitness, rincian yang akan dijelaskan di bawah ini. Karena tujuan dari program kecil kami adalah untuk menghasilkan sejumlah perubahan dalam koin Amerika sama dengan jumlah target dalam jumlah paling sedikit mungkin koin, tampaknya masuk akal bahwa ukuran kebugaran untuk solusi tertentu akan menjadi kombinasi dari kedekatan relatif dari jumlah perubahan itu mewakili dengan jumlah sasaran perubahan, dan jumlah koin yang diwakili oleh solusi (sedikit menjadi lebih baik).

Mari kita mengatasi contoh fungsi fitness sedikit demi sedikit. Untuk memulai, kita mendefinisikan kelas kami sendiri dan memperpanjang kelas org.jgap.FitnessFunction. Semua fungsi fitness harus memperpanjang kelas FitnessFunction. Kami kemudian mendefinisikan konstruktor dan mengevaluasi () method. Mengevaluasi () Metode ini adalah metode standar yang semua fungsi fitness harus menerapkan. Itu adalah metode yang akan dipanggil oleh mesin genetik saat dibutuhkan untuk mengetahui nilai fitness dari suatu kromosom.

Konstruktor kami tidak sangat menarik: itu hanya menerima sejumlah perubahan target itu keinginan pengguna, memverifikasi bahwa jumlah memenuhi kendala kami berada antara 1 dan 99 sen, dan kemudian menyimpan jumlah dalam sebuah variabel instan untuk digunakan nanti.

Bagian yang menarik dari seluruh kelas adalah metode mengevaluasi (), yang mana pekerjaan dilakukan. The mengevaluasi metode selalu dikirimkan dalam Kromosom, yang merupakan solusi potensial. Sebuah kromosom terdiri dari gen, yang masing-masing merupakan bagian masing-masing dari solusi. Dalam contoh kita, Kromosom ini merupakan jumlah perubahan, sedangkan gen mewakili jenis spesifik koin: perempat untuk gen pertama, dime untuk gen kedua, receh untuk gen ketiga, dan uang untuk gen keempat. Nilai gen disebut alel. Dalam contoh kita, alel akan jumlah jenis tertentu dari koin (misalnya, 2 sen).

Hal pertama yang mengevaluasi () metode yang dilakukan adalah memanggil beberapa metode penolong yang mudah mengembalikan jumlah perubahan yang diwakili oleh solusi potensial dan jumlah koin yang diwakili oleh solusi. Kita akan melihat lebih dekat bagaimana pekerjaan ini nanti. Kemudian mengurangi jumlah perubahan diwakili oleh solusi dari jumlah sasaran, dan mengambil nilai absolut dari selisih untuk mengukur seberapa dekat jumlah solusinya adalah dengan jumlah target. Kami kemudian mulai menghitung nilai fitness kami.

Sebagai komentar menunjukkan, kita akan menghitung kebugaran dalam dua tahap. Tahap pertama menghitung nilai fitness awal berdasarkan seberapa jauh jumlah solusinya adalah dari jumlah sasaran. Lalu, jika jumlah solusi kebetulan sama dengan jumlah sasaran, kita lanjut ke tahap dua, yang menyesuaikan nilai fitness berdasarkan jumlah koin yang diwakili oleh solusi. Pada akhirnya, kita ingin mengembalikan nilai fitness tinggi untuk solusi yang sesuai dengan jumlah target dengan koin sangat sedikit, dan mengembalikan nilai fitness yang lebih rendah untuk solusi yang jauh dari jumlah target atau mewakili sejumlah besar koin.

Bergerak di luar metode evaluasi (), kita menemukan metode-metode pembantu yang telah disebutkan sebelumnya. The amountOfChange () metode menghitung jumlah total perubahan (dalam cent) diwakili oleh kromosom yang dikirimkan ke sana. Secara internal, itu menangguhkan metode getNumberOfCoinsAtGene () untuk benar-benar mengekstrak jumlah setiap jenis koin. Kemudian menghitung jumlah total perubahan dan mengembalikannya.

Metode kenyamanan berikutnya, getNumberOfCoinsAtGene (), bertanggung jawab untuk menentukan jumlah koin diwakili oleh gen tertentu dalam kromosom tertentu. Seperti disebutkan sebelumnya, nilai dari setiap gen dalam kromosom disebut alel. Metode ini mendapat alel untuk gen pada posisi yang diberikan dalam Kromosom dan kemudian mengembalikannya sebagai int primitif.

Akhirnya, ada metode getTotalNumberOfCoins () yang menentukan jumlah koin diwakili oleh kromosom tertentu. Ini hanya tallies up jumlah koin yang diwakili oleh masing-masing gen - menggunakan getNumberOfCoinsAtGene () method - dan kemudian kembali penghitungan.

Dan itulah akhir dari fungsi fitness. Jika Anda merasa sedikit kewalahan, jangan khawatir tentang hal itu dan mengambil beberapa kenyamanan dalam kenyataan bahwa itu semua turun bukit dari sini! Fungsi fitness adalah bagian tersulit dari menggunakan JGAP dan, setelah menulis beberapa, Anda akan mendapatkan menguasainya.

3.5.3 Atur Konfigurasi Objek

JGAP dirancang untuk menjadi sangat fleksibel dan pluggable. Jika Anda ingin, Anda dapat membuat operator sendiri genetik, nomor acak generator, penyeleksi alam, dan sebagainya. Untuk mendukung semua ini, JGAP menggunakan objek Konfigurasi yang harus mengatur semua pengaturan yang Anda inginkan sebelum menggunakan mesin genetik. Untungnya, kami menyadari bahwa kebanyakan orang akan ingin menggunakan komponen saham, sehingga kita termasuk kelas DefaultConfiguration yang datang sudah setup dengan pengaturan yang paling umum. Anda hanya perlu menyediakan tiga potong tambahan informasi: apa fungsi fitness yang ingin Anda gunakan, bagaimana Anda ingin Kromosom Anda harus setup, dan berapa banyak Kromosom yang Anda inginkan dalam populasi Anda.

Mari kita lihat beberapa contoh kode yang mungkin ingin Anda sertakan dalam kelas yang sama seperti potongan di atas.

Mudah-mudahan sebagian besar dari kode di atas adalah cukup jelas, dengan mungkin pengecualian menyiapkan sampel kromosom. Mari kita lihat sedikit bahwa dalam sedikit lebih detail.

Seperti disebutkan sebelumnya, Kromosom yang terdiri dari gen. JGAP memungkinkan Anda memilih apa Gene kelas digunakan untuk mewakili masing-masing gen dalam kromosom (untuk informasi lebih lanjut tentang cara membuat kelas Gene kustom, silakan lihat Membuat Kustom Gen document). Yang menyediakan fleksibilitas yang paling dan kenyamanan. Jika kita mau, kita bisa benar-benar menulis kelas Gene terpisah untuk setiap jenis koin dalam contoh kita, seperti QuarterGene, DimeGene, NickelGene, dan PennyGene. Bahkan, kita melihat apa QuarterGene mungkin terlihat seperti di Gen Membuat Kustom mendokumentasikan bahwa kita hanya disebutkan.

Seperti yang terjadi, kami memutuskan bahwa IntegerGene (yang datang dengan JGAP) akan cukup. Anda akan melihat, bagaimanapun, bahwa kami tidak mengambil keuntungan dari kemampuan untuk menentukan implementasi Gene berbeda untuk setiap gen dalam kromosom dengan menciptakan IntegerGenes terpisah dengan batas bawah dan atas yang berbeda untuk setiap jenis koin. Kami menetapkan batas atas untuk jumlah terbesar koin dari jenis masing-masing yang akan muncul dalam solusi optimal. Membatasi ruang solusi cara ini membantu JGAP mendapatkan solusi yang lebih baik dengan lebih sedikit evolusi.

Jadi untuk kembali ke kode, pertama-tama kita membuat sebuah array dari Gen dengan panjang 4, karena kami ingin mewakili 4 gen (satu untuk setiap jenis koin). Kami kemudian mengatur setiap Gene dalam array ke IntegerGene yang dibangun dengan batas bawah dan atas yang sesuai untuk jenis koin. Akhirnya, kita membangun Kromosom baru dan menyebarkannya array Gen, dan kemudian menetapkan bahwa sampel Kromosom pada objek Konfigurasi.

Bagian akhir dari langkah ini adalah pengaturan ukuran populasi, yang merupakan jumlah Kromosom yang kita inginkan dalam populasi. Sebuah ukuran populasi yang lebih besar berarti solusi yang lebih potensial untuk memilih dari dan lebih keragaman genetik, tetapi juga berarti lebih banyak pekerjaan untuk berkembang populasi itu. Pada akhirnya, Anda harus menetap di nilai yang menyeimbangkan kebutuhan Anda untuk pilihan baik solusi potensial terhadap berapa banyak waktu yang Anda bersedia untuk menghabiskan menunggu populasi Anda berkembang. Ukuran populasi yang dipilih lebih tinggi dari jumlah kemungkinan solusi di sini (sebagai 4 * 3 * 2 * 5 = 120). Tapi seperti Algoritma Genetika adalah sistem stokastik, semakin mencoba GA diperbolehkan untuk membuat, semakin tinggi kemungkinan menemukan solusi yang baik. Selain itu, ukuran populasi tidak boleh berkorelasi terlalu khusus untuk ruang pencarian menyempit, tetapi dapat digunakan dalam cara yang lebih umum. Artinya: jika 120 kemungkinan kombinasi yang disebutkan di atas dibesarkan, maka penduduk tidak akan perlu diadaptasi. Dan jika 120 disimpan, ukuran populasi dari 500 tidak akan memiliki dampak negatif, karena evolusi sedikit diperlukan menemukan solusi yang baik dibanding dengan ukuran populasi yang lebih kecil.

3.5.4 Buat Sebuah Populasi

Ingat bahwa setiap solusi potensial diwakili oleh Kromosom sebuah. Sebuah populasi Kromosom disebut Genotipe, dan itu adalah kelas kita perlu membangun untuk menciptakan populasi kita. Jika Anda ingin, Anda dapat membuat setiap Kromosom individual dan kemudian lulus mereka semua ke dalam Genotipe baru (seperti kami membangun setiap Gene dan melewati mereka ke dalam sampel Kromosom pada langkah 3), tapi JGAP menyediakan cara yang lebih cepat dan lebih mudah untuk menciptakan populasi acak. Bahkan, hanya membutuhkan satu baris kode (menambahkan semua baris kode berikut ke kode di atas dalam metode utama):

Genotype population = Genotype.randomInitialGenotype(conf );

The randomInitialGenotype () metode dalam mengambil sebuah objek Konfigurasi (yang kita setup pada langkah 3) dan kembali Genotipe dengan jumlah yang benar Kromosom, masing-masing memiliki gen yang diatur ke nilai acak. Dengan kata lain, itu menghasilkan populasi acak. Untuk sebagian besar aplikasi, ini adalah semua yang diperlukan untuk menciptakan populasi awal Anda solusi potensial.

3.5.5 Kembangkan Populasi

Sekarang kita sudah setup segalanya dan siap untuk pergi, saatnya untuk mulai berkembang penduduk sampai berisi beberapa solusi potensial yang kami puas dengan. Berkembang populasi satu siklus adalah satu-kapal lain:

population.evolve();

Biasanya, setelah setiap siklus evolusi, Anda akan ingin memeriksa apakah populasi mengandung salah solusi yang memuaskan. Cara termudah untuk melakukannya adalah dengan memanggil getFittest Kromosom () metode pada populasi:

IChromosomebestSolutionSoFar = population.getFittestChromosome();

Jika solusi terbaik sejauh ini cukup baik untuk Anda, maka Anda sudah selesai. Jika tidak, maka Anda dapat berkembang penduduk lagi. Atau, Anda hanya dapat memilih untuk berkembang populasi sejumlah set kali dan kemudian melihat apa solusi yang terbaik adalah yang dihasilkan pada akhir (atau kombinasi keduanya). Untuk masalah contoh kita, kita akan mengambil pendekatan yang kedua ini.

Sekarang kita punya aplikasi genetik penuh diri kita sendiri! Untuk melihat semua kode untuk contoh ini, lihat Meminimalkan Membuat Change.java dan Meminimalkan MakeChangeFitnessFunction.java file dalam direktori examples / src distribusi JGAP.

3.6 Menyelesaikan Masalah menggunakan Pemrograman Genetik dengan JGAP

- Identifikasi Kandidat masalah

Pemrograman genetik telah diterapkan pada berbagai macam masalah. Secara khusus, Koza telah menunjukkan bahwa banyak masalah dapat dirumuskan sehingga mereka berbagi arsitektur perangkat lunak yang sama dan sehingga mereka dapat diselesaikan dengan teknik Pemrograman Genetik. Arsitektur ini terdiri dari penyajian komponen pemrograman genetik dengan input yang sesuai, menjalankan input melalui serangkaian program yang dihasilkan secara genetis, dan kemudian mengukur keberhasilan setiap program terhadap jawaban yang diharapkan untuk input yang sesuai. Proses ini diulang lagi dan lagi sampai ukuran keberhasilan memenuhi kriteria akhir yang Anda berikan.

- Tantangan pertama adalah mengidentifikasi masalah yang menarik dan menentukan bahwa masalah yang dipilih memiliki kesempatan yang masuk akal untuk dibedah. Ada masalah yang dapat dikembangkan dengan pemrograman tradisional yang dapat juga diselesaikan dengan pemrograman genetik. Namun, Anda mungkin menemukan dalam beberapa kasus bahwa upaya untuk menciptakan genetik pemrograman arsitektur perangkat lunak di atas sama dengan atau lebih besar dari upaya untuk menciptakan solusi dengan pemrograman tradisional.

3.6.1 Contoh Kasus (Masalah semut)

Masalahnya terdiri dari 10 semut dalam kotak 10x10 toroidal dengan 10 butir pasir hitam, 10 butir pasir abu-abu, dan 10 butiran pasir bergaris. Tujuannya adalah untuk menemukan satu program yang ketika dijalankan pada setiap semut, memindahkan butiran pasir ke dalam tiga kolom pertama.

- Seleksi Set Fungsi

Untuk masalah dengan solusi yang tidak diketahui, kita perlu mengidentifikasi satu set fungsi yang cukup untuk memecahkan masalah. Untuk masalah kita, kita menggunakan fungsi set diidentifikasi oleh Koza. Terminals = {X, Y, Carrying, SandColor, GO_N, GO_E, GO_S, GO_W, MoveRandom, Pickup}

Functions = {IfLessThanOrEqual, IfLessThanZero, IfDrop}

Untuk solusi pertama, kita akan meniru bahasa pemrograman Lisp dengan memiliki fungsi masing-masing mengembalikan nilai integer sesuai dengan aturan pada paper.

- Membuat kelas Domain

Kami memilih untuk menerapkan logika bisnis dalam dua kelas. The AntMap berisi pengetahuan tentang lokasi dan set semut. Hal ini bertanggung jawab untuk memuat masalah dari file location yang berisi pasir dan lokasi semut. Hal ini juga bertanggung jawab untuk menyajikan keadaan saat ini peta pada System.out. Kelas semut bertanggung jawab atas segala perilaku tertentu semut. Pendekatan menggunakan kelas domain diperbolehkan unit pengujian perilaku luar dari kerangka JGAP dan kemudian menciptakan JGAP berbasis unit test untuk membandingkan terhadap perilaku domain.

Kelas domain dapat dengan mudah dimodifikasi untuk pendekatan yang lebih modern dengan mengubah kembali nilai-nilai dari int untuk membatalkan itu. Prosedur ini kemudian dapat dipetakan ke kelas yang sesuai genetik.

- Membuat Fungsi Set

Sekarang kita tahu fungsi yang ingin kita mencoba untuk program kami, kita perlu mengubah fungsi ke JGAP kelas kompatibel tepat. Untuk setiap terminal dan fungsi masing-masing yang tercantum di atas ada kelas Java yang sesuai. Anda dapat menelusuri kelas dalam paket paintedDesert. Untuk tutorial ini, kita akan fokus pada konsep-konsep kunci untuk mengintegrasikan dengan kerangka JGAP.

- Konsep JGAP Key

Konstruktor kelas - Setiap kelas fungsi membutuhkan konstruktor yang membentang dari CommandGene. Sama seperti JGAP contoh anttrail, kami telah membuat sebuah kelas AntCommand untuk menyediakan perilaku umum yang terkait dengan mengambil dengan AntMap. Terkadang dalam pembangunan objek, misalnya harus mengidentifikasi jumlah argumen dan jenis kembali. Jumlah argumen adalah argumen kedua di konstruktor CommandGene dan disahkan sebagai a_arity argumen. Argumen ketiga dalam constructor adalah jenis kembali. Anda harus menggunakan definisi statis CommandGene jenis; BooleanClass, IntegerClass, LongClass, FloatClass, dan VoidClass. Parameter tambahan int a_subReturnType dan akhir int [] a_childSubTypes memiliki arti sebagai berikut:

Pertimbangkan fungsi yang mengembalikan jumlah integer, sehingga jenis itu kembali dinyatakan sebagai IntegerClass (atau: Integer.class). Pertimbangkan lebih jauh, bahwa Anda memiliki fungsi yang mengharapkan sebagai parameter Integer mengetik masukan. Jika untuk alasan apapun Anda ingin menghindari bahwa fungsi yang disebutkan pertama kembali IntegerClass berpotensi untuk digunakan sebagai masukan untuk fungsi yang disebutkan terakhir, Anda dapat menggunakan sub jenis. Itu berarti: Fungsi kembali IntegerClass bisa memiliki subReturnType, katakanlah, 1, sedangkan fungsi menerima input type IntegerClass bisa memiliki childSubType yang berbeda dari subReturnType 1 Untuk childSubtype Anda bisa menggunakan 2, misalnya.

Dalam kasus-kasus tidak masuk akal untuk menghindari fungsi dengan pas tipe kembali menjadi input dari fungsi mengharapkan jenis ini kembali sebagai input type? Misalnya, jika salah satu fungsi mengembalikan angka integer yang merupakan multiplier yang bisa berada di kisaran 2 .. 5, dan fungsi lainnya mengharapkan angka integer yang mewakili indeks dari array, berada di kisaran 0 .. 99.

- Operasi fungsi

Argumen Set diijinkan jenis argumen didefinisikan dalam getChildType operasi (IGPProgram a_ind, int a_chromNum). The a_chrom_Num adalah argumen kunci. Ini mengidentifikasi indeks berbasis 0 argumen. Jika Anda ingin mendukung kombinasi dari jenis argumen, maka Anda akan perlu untuk mengembalikan jenis yang sesuai. Sebagai contoh, jika argumen pertama adalah VoidClass dan argumen kedua perlu menjadi IntegerClass, Anda ingin metode seperti:

if (a_chromNum == 0) {

kembali CommandGene.VoidClass;

} Else if (a_chromNum == 1) { kembali CommandGene.IntegerClass;

}

- Representasi String untuk Kelas Fungsi Ada dua mekanisme di mana sistem ini akan membuat representasi string kelas. Yang pertama adalah getName () fungsi yang mengembalikan nama fungsi. Versi ini digunakan dalam berbagai Pengecualian dilemparkan oleh kelas CommandGene. Mekanisme kedua memberikan umpan balik pada fungsi diturunkan secara genetik. The IGPProgram contoh fungsi toStringNorm (int a_startNode) digunakan untuk mengembalikan sebuah string yang mewakili program sistem JGAP. Ini hierarkis memanggil toString () operasi untuk mengembalikan representasi Program.

- Menggabungkan semua Bersama Kami telah menganalisis masalah kita dan menciptakan fungsi kami yang mudah-mudahan cukup untuk memecahkan masalah, sekarang kita perlu menambahkan logika yang saya disebut "Process Control" dalam diagram pertama. Kami akan diperluas dari kelas GPProblem untuk menciptakan kelas PaintedDesertProblem kami. Salah satu metode utama adalah GPGenotype menciptakan () method. Berbagai opsi untuk mengendalikan proses pembelajaran akan didokumentasikan sesegera mungkin.

- Membuat Unit Pengujian Seperti semua latihan pemrograman, penting untuk menciptakan tes unit. Anda berharap untuk menemukan alasan mengapa JGAP tidak memecahkan masalah seperti yang Anda harapkan. Anda bisa membuat kesalahan dalam tes kecukupan. Dapatkah fungsi yang tersedia dikombinasikan untuk memecahkan masalah? Apakah fungsi kebugaran Anda mengembalikan hasil yang tepat? Apa yang sebenarnya terjadi dalam kotak hitam ajaib JGAP? Apakah JGAP menempatkan program bersama-sama dengan cara yang Anda harapkan? Apakah Anda menemukan bug di JGAP?

Atau Anda bisa membuat kesalahan tradisional pemrograman? Dalam masalah Painted Desert, pendekatan objek domain memungkinkan untuk pengujian JUnit tradisional di Ant dan AntMap kelas. Tentu saja, aku punya kesalahan di kelas domain. Keuntungan dari pendekatan solusi yang ada adalah bahwa selain tes unit, kami bisa menulis sebuah program yang menunjukkan bahwa solusi bekerja.

Kami ingin menambahkan catatan tentang jenis-jenis kesalahan yang Anda dapat membuat. Saya telah mengidentifikasi bahwa kesalahan dibuat di kelas domain. Saya mengumpulkan beberapa contoh unit test elemental untuk bekerja melalui masalah. Tentu saja, cakupan tes unit tidak lengkap, tetapi memberikan ide yang dapat membantu Anda dengan tantangan Anda. Anda mungkin melihat bahwa satu kasus tes, OneElementGenElementsTest, membandingkan hasil dari kode solusi tangan terhadap solusi menggunakan kelas fungsi JGAP. Salah satu pengakuan lain yang perlu diperhatikan, sesederhana masalah ini adalah, saya melakukan kesalahan penting dalam pemrograman kelas IfDrop. Ini tidak menjatuhkan pasir. Oleh karena itu, program genetika tidak bisa memecahkan masalah. Itu adalah pengawasan sederhana yang harganya terlalu banyak jam frustrasi dan eksplorasi, tetapi membantu saya memahami lebih lanjut tentang JGAP.

- Menulis Tes Pengujian pada JGAP

Jika kelas fungsi memerlukan satu atau lebih argumen, maka kelas yang ditambahkan dalam elemen array berikut dan digunakan oleh kelas fungsi bersarang sebelum melanjutkan untuk menambahkan argumen ke kelas fungsi induk.

- Ringkasan

Pemrograman genetik dengan JGAP dapat bekerja jika Anda telah mengatur masalah Anda dengan benar. Debugging program bahwa sistem otomatis dibuat menawarkan tantangan yang signifikan. Untuk memerangi delegasi kontrol ke JGAP, pertimbangkan untuk menulis unit test yang memeriksa logika domain Anda dan serius mempertimbangkan memeriksa fungsi genetik dengan JGAP unit test.

3.6.2 Contoh Program

Saat anda mengekstrak file yang di unduh tadi, terdapat beberapa contoh program yang telah dibuat. Mari kita coba 1 contoh yang di sediakan oleh JGAP. Contoh yang saya gunakan disini yaitu Start_monalisa_gp (Genetic Leonardo). Genetic Leonardo adalah program komputer yang menggunakan teori evolusi untuk menyusun gambar seperti aslinya. Program akan memulai meulkis monalisa menggunakan kumpulan polygon yang berbeda warna kemudian menyusunnya menjadi sebuah gambar.

Untuk memulai klik 2 kali pada file start monalisa_gp dalam folder jgap-current.

Bila program tadi dijalankan, maka akan muncul layar konsol seperti diatas. Layar ini menandakan bahwa program sedang dalam proses berjalan. Tunggu beberapa saat hingga konsol berhasil mengkompilasi programnya.

Lalu bagaimana program ini bekerja? Untuk memulainya klik pada tombol “Start Evolution”. Maka akan muncul window baru seperti berikut:

Pada window baru yang muncul terdapat beberapa polygon yang mulai tersusun. Proses ini akan memakan sedikit waktu. Tunggu hingga kumpulan polygon tersebut terkumpul menjadi sebuah lukisan monalisa seperti berikut:

3.7 STATISTIKA

JCSC (Java Coding Standard Checker) digunakan untuk mengumpulkan data berikut tentang baris kode, paket dan kelas.

- Baris kode, kelas dan paket

JGAP memiliki sekitar 57.200 baris kode (LOC). Mereka didistribusikan melalui sekitar 339 kelas Java dan 26 paket. Contoh-contoh yang disediakan mengambil 182 kelas lain dalam 32 paket dengan kira-kira 20000 baris kode.

Tentu saja angka-angka ini meningkat dari waktu ke waktu sebagai JGAP secara permanen mengalami proses evolusi.

- Tes uji kasus / Unit

Saat ini, lebih dari 1400 kasus uji ditampilkan oleh JGAP. Mereka menempati 122 kelas di 21 paket dengan sekitar 32.600 baris kode.

- Dokumentasi

JGAP memiliki banyak dokumentasi. Yang paling penting untuk hands-on pengembang mungkin Javadoc yang tersedia di hampir semua kelas JGAP. Sebagai sebuah perintah, Javadoc hampir selalu ditambahkan ke kelas dan metode yang lebih penting, sebagian besar juga untuk metode sederhana seperti getter dan setter. Selain itu, ada banyak dokumentasi yang diberikan oleh halaman depan/utama ini (di sini kita bisa mendapat bantuan karena sulit menjaganya agar tetap up-to-date).

Ketika memeriksa sumber dan file lainnya ke CVS (sistem versi konkuren), hampir setiap saat komentar deskriptif melekat dengan tindakan, muncul di CVS.

BAB 4

STUDI KASUS

4.1 Penjelasan

Pada penjelasan kali ini akan ada beberapa studi kasus yang menggunakan JGAP pada algoritma genetik, dan studi kasus seperti berikut:

4.2 Perancangan Sistem

Penjelasan kali ini adalah bagaimana penulis merancang sebuah sistem yang menggunakan materi yang dijelaskan pada teori tersebut.

4.2.1 Spesisifikasi Perangkat Lunak dan Perangkat Keras

Spesifikasi perangkat lunak sistem, adalah sebagai berikut : Java SE 6 Update 18; Netbeans IDE 7.0.1 Sebagai software pembantu untuk membuat program dan desain antar muka; Pustaka JFugue 4.0.2 sebagai pustaka untuk membunyikan musik String dan melakukan export ke dalam bentuk format file MIDI; Pustaka JGAP 3.6 sebagai pustaka framework untuk pemrogram genetika dan algoritma genetika java.

Spesifikasi perangkat keras sistem adalah sebagai berkut : Intel Core 2 Duo 2.2 GHz; RAM 1.00 GB; HardDisk 160 GB

4.2.2 Use Case Diagram

Rancangan use case diagram pada sistem, ditunjukkan pada Gambar 13.

Use case diagram sistem pada Gambar 13, menggambarkan interaksi antar user dengan sistem. Pada sistem ini, user dapat membuat pola suara baru, kemudian dari suara baru yang telah dibuat, user dapat memainkan, menghentikan dan export ke format file MIDI.

4.2.3 Pembahasan Kode Program

Aplikasi dibuat menggunakan java dengan software NetBeans IDE 7.0.1 dengan JDK 1.6u18.

Kode Program 1 menunjukkan kode program method evaluate untuk perhitungan nilai fitness. Penentuan nilai fitness dengan pustaka JGAP membutuhkan sebuah class yang merupakan extends dari class FitnessFunction pada pustaka JGAP, dan class tersebut akan mengimplementasikan method evaluate yang digunakan untuk menghitung nilai fitness. Baris ke – 2 s/d 7 digunakan untuk menyimpan kromosom dari populasi ke dalam array String polaBaru. Baris ke – 8 merupakan perhitungan nilai fitness kromosom yang ditampung di variabel double fitnessValue dengan memanggil fungsi fitnessCountSymbol dan comparingSymbol untuk menghitung nilai fitness kromosom. Baris ke – 9 akan mengembalikan nilai fitness kromosom tersebut.

Kode Progam 2 merupakan method untuk membuat pola suara baru. Baris ke – 2 dan 3 adalah pembentukan populasi awal sesuai dengan ukuran populasi yang telah ditentukan. Baris ke – 4 merupakan proses pembentukan populasi dengan memanggil method evaluate() yang memiliki parameter maxEvolve sebagai batas maksimum evolusi. Kemudian, kromosom terbaik akan ditampung ke dalam String _str yang didapatkan dengan memanggil method outputSolution.

Kode Program 3 menunjukkan konfigurasi parameter Algoritma Genetika pada JGAP. Secara umum, JGAP menyediakan konfigurasi default dengan membuat instance dari class DefaultConfiguration(). Namun, JGAP juga menyediakan kemampuan untuk membuat konfigurasi manual agar parameter Algoritma Genetika bersifat dinamis dengan membuat instance dari class Configuration. Baris ke – 7 s/d 9 merupakan konfigurasi untuk proses selection pada kromosom. Objek dari class BestChromosomesSelector akan mengatur persentase banyaknya kromosom yang akan diambil dari populasi. Baris ke – 8 adalah pengaturan untuk kromosom yang digunakan, jika bernilai true, maka kromosom yang sama diperbolehkan untuk ditambahkan ke dalam populasi. Baris ke – 9 menambahkan natural selection pada konfigurasi JGAP.

Kode Program 4 merupakan cara untuk meng-export pola suara menjadi file MIDI. Jfugue menyediakan fungsi untuk melakukan proses tersebut dengan memanggil method saveMidi dari class Player. Method ini membutuhkan parameter berupa pattern dari pola suara dan file tujuannya.

4.2.4 Pengujian Sistem Berdasarkan Parameter Algoritma Genetika untuk Pembuatan Pola Baru

Pengujian sistem dilakukan terhadap beberapa parameter algoritma genetika untuk melihat pengaruhnya terhadap pola suara drum hasil generate.

4.2.5 Uji Coba Parameter Population Size.

Pengujian dilakukan sebanyak 30 kali ke setiap populasi yang diuji dengan menghitung rata–rata nilai fitness yang dihasilkan. Adapun pengujian dilakukan dengan nilai parameter population size berbeda–beda, sedangkan parameter lainnya tetap, agar dapat dilihat perbedaan yang terjadi. Parameter lainnya berisikan data sebagai berikut : (1) Genre Slow Rock; (2) Maksimum evolusi sebesar 10; (3) Natural selection rate sebesar 90%; (4) Crossover rate sebesar 35%; (5)Mutation rate sebesar 1/12.

Pengujian dilakukan sebanyak 3 kali dengan population size masing–masing 1, 10 dan 100. Hasil uji coba parameter disajikan pada Tabel 4.

Berdasarkan hasil pengujian pada Tabel 4, didapatkan hasil rata–rata fitness dengan population size 1 sebesar 80.59522, population size 10 sebesar 97.8125, population size 100 sebesar 100, dan dapat disimpulkan bahwa semakin besar nilai population size, semakin besar kemungkinan nilai fitness optimum.

4.2.6 Uji Coba Parameter Maksimum Evolusi

Pengujian Parameter Maksimum Evolusi dilakukan sebanyak 30 kali ke setiap populasi yang diuji, dengan menghitung rata–rata nilai fitness yang dihasilkan. Adapun pengujian dilakukan dengan nilai parameter maksimum evolusi yang berbeda-beda, sedangkan parameter lainnya tetap agar dapat dilihat perbedaan yang terjadi. Parameter lainnya berisi data sebagai berikut : (1) Genre Slow Rock; (2)Population size sebesar 10; (3)Natural selection rate sebesar 90%; (4)Crossover rate sebesar 35%; (5)Mutation rate sebesar 1/12.

Pengujian dilakukan sebanyak 3 kali dengan maksimum evolusi masing– masing 1, 10 dan 100. Hasil uji coba parameter Maksimum Evolusi disajikan pada Tabel 5.

Berdasarkan hasil pengujian pada Tabel 5 didapatkan hasil rata–rata fitness dengan maksimum evolusi 1 sebesar 92.0674, maksimum evolusi 10 sebesar 97.7083, maksimum evolusi 100 sebesar 100, dan dapat disimpulkan bahwa semakin besar nilai maksimum populasi, semakin besar kemungkinan nilai fitness optimum.

4.2.7 Uji Coba Parameter Crossover Rate

Pengujian Parameter Crossover Rate dilakukan sebanyak 30 kali ke setiap populasi yang diuji dengan menghitung rata–rata nilai fitness yang dihasilkan. Adapun pengujian dilakukan dengan nilai parameter crossover rate yang berbeda- beda, sedangkan parameter lainnya tetap agar dapat dilihat perbedaan yang terjadi. Parameter lainnya berisikan data sebagai berikut : (1) Genre Slow Rock; (2) Population size sebesar 10; (3) Maksimum evolusi sebesar 10%; (4) Natural selection rate sebesar 90%; (5) Mutation rate sebesar 1/12.

Pengujian dilakukan sebanyak 3 kali dengan crossover rate masing–masing 0.1, 0.5 dan 1. Hasil uji coba parameter disajikan pada Tabel 7.

Berdasarkan hasil pengujian pada Tabel 7 didapatkan hasil rata–rata fitness dengan crossover rate 0.1 sebesar 96.8229, crossover rate 0.5 sebesar 97.96875, crossover rate 1 sebesar 97.29167, dan dapat disimpulkan bahwa nilai fitness tidak bergantung pada nilai crossover rate.

4.2.8 Pengujian File Output Generator

Pengujian dilakukan pada hasil export MIDI dengan cara membandingkan pola hasil generate sistem dengan drum setelah dibuka di dalam editor musik drum lainnya. Gambar 22 menunjukkan hasil generate pola drum oleh sistem.

Gambar 22 Contoh Hasil Generate Pola Drum Oleh Sistem dan Log

Kemudian dibuka file hasil export MIDI di dalam aplikasi lain yaitu dibuka file hasil export MIDI di dalam software lain yaitu Fruty Loops 9 yang hasilnya dapat dilihat pada Gambar 23.

Gambar 23 menunjukkan bahwa file drum MIDI hasil export sistem dapat dibuka dengan baik oleh aplikasi Fruty Loop 9.

4.3 Penerapan Algoritma Genetika pada Perencanaan Lintasan Kendaraan

Algoritma genetika adalah suatu bentuk teknik pencarian secara stochastic, berdasarkan mekanisme yang ada pada seleksi alam dan genetik secara natural. Setiap makhluk hidup memiliki gen-gen, yaitu bagian dari kromosom yang menentukan atau mempengaruhi karakteristik setiap individu. Mekanisme genetik mencerminkan kemampuan individu untuk melakukan perkawinan dan menghasilkan keturunan yang memiliki karakteristik yang hampir sama dengan orang tuanya. Sedangkan prinsip seleksi alam menyatakan bahwa setiap makhluk hidup dapat mempertahankan dirinya jika mampu beradaptasi dengan lingkungannya. Dengan demikian, diharapkan keturunan yang dihasilkan memiliki kombinasi karakteristik yang terbaik dari orang tuanya, dan dapat menopang generasigenerasi selanjutnya.

Berbeda dengan teknik pencarian konvensional, tahap awal pencarian dalam algoritma genetika dimulai dari himpunan penyelesaian acak (random) yang disebut populasi. Setiap individu dalam populasi diwakili oleh sebuah kromosom yang merupakan satu solusi dari masalah yang akan dihadapi.

4.3.1 PERANCANGAN PROGRAM

Aplikasi perangkat lunak penerapan algoritma genetika pada perencanaan lintasan ini terdiri dari 4 komponen utama, yaitu proses inisialisasi awal, fungsi evaluasi, seleksi, dan operator genetika. Keluaran dari aplikasi ini adalah gambar 2 dimensi yang menunjukkkan lintasan terpendek.

Ada beberapa parameter yang harus dibangkitkan maupun ditentukan terlebih dahulu. Parameter ini dibuat sebagai batasan pada algoritma yang akan dilakukan. Inisialisasi awal dilakukan untuk memenuhi parameter yang dibutuhkan. Inisialisasi awal ini meliputi penentuan ukuran populasi, penentuan ukuran kromoson, penentuan jumlah penghalang dan posisi masing – masing serta radius dari penghalang itu sendiri, penentuan nilai mutation rate (Pm) dan crossover rate (Pc), penentuan ukuran peta lingkungan, penentuan titik awal dan titik tujuan.

Evaluasi kromoson dilakukan untuk memastikan tidak ada titik acuan yang berada pada titik awal (Sp) maupun titik tujuan (Ep) dan menentukan titik yang berada pada penghalang. Selanjutnya dilakukan pengecekan terhadap titik acuan, dimana titik acuan tidak boleh berada pada tit awal dan titik akhir serta tidak boleh berada pada penghalang.

Seleksi dilakukan dengan terlebih dahulu mencari nilai kebugaran (fitness) dari masingmasing individu. Nilai fitness itu sendiri merupakan panjang lintasan. Jadi nilai fitness yang terbaik adalah kromoson yang memiliki jarak terpendek. Sebelum menentukan nilai fitness generasi awal harus dibangkitkan terlebih dahulu. Generasi ini disebut sebagai induk (parent). Fungsi fitness yang digunakan dalam tugas akhir ini adalah ( ) d(k ) ft k 1 = , dimana d(k ) merupakan panjang lintasan untuk kth kromoson. Metoda seleksi yang digunakan ialah metode seleksi roda roulette (roulette wheel selection). Sesuai dengan namanya, metode ini menirukan permainan roulette-wheel dimana masing-masing kromoson menempati potongan lingkaran pada roda roulette secara proporsional sesuai dengan nilai fitnessnya. Kromoson yang memiliki nilai fitness lebih besar menempati potongan lingkaran yang lebih besar. Metode roulette-wheel dapat diimplementasikan dalam pemrograman dengan beberapa langkah. Pertama, dibuat interval nilai kumulatif (dalam iterval [0,1]) dari nilai fitness masing-masing kromosom dibagi total fitness dari semua kromosom. Sebuah kromosom akan terpilih jika bilangan random yang dibangkitkan berada dalam interval akumulatifnya.

Operator genetika bertujuan untuk merekombinasi kromoson. Dalam tugas akhir ini digunakan dua operator genetika yang direpresentasikan sebagai fungsi, yaitu fungsi crossover dan fungsi mutation.

Pindah silang (crossover) akan dilakukan pada beberapa kromoson pada setiap generasi. Akan tetapi, setiap crossover dikontrol oleh nilai Pc (crossover rate). Dengan kata lain, algoritma akan membangkitkan nilai random antara [0 1] untuk setiap kromoson. Jika nilai yang dibangkitkan lebih kecil dari nilai Pc, maka crossover dapat dilakukan pada kromoson tersebut. Untuk mencapai tujuan yang lebih akurat maka crossover point dipilih secara acak untuk setiap generasi.

Tidak seperti crossover,mutasi bekerja pada bit demi bit. Oleh karena itu, jika diberikan peluang mutasi (mutation rate) Pm = 0,01, populasi diperkirakan akan melakukan mutasi 1% bit. Misalnya, jika ada 20 kromosom dengan 5 bit di masing-masing, maka paling sedikit 20 x 5 x 0,01 = 1mutasi diharapkan terjadi.

Kromoson baru akan muncul pada setiap generasi. Walaupun kromoson – kromoson baru tersebut memenuhi kriteria jarak terpendek, namun bukan berarti itu menjadi sebuah solusi jika lintasan yang dilalui melewati penghalang. Begitu juga dengan titik acuan tidak boleh berada pada penghalang. Untuk itu perlu dilakukan pengecekan, contoh: sebuah kromoson dengan 1 titk acuan: [(0.0) (10.10) (20.20)]. Dan juga sebuah penghalang diletakkkan di (12.12) dengan radius 2. Kemudian mulai dari garis pertama yang dibentuk oleh 2 titik acuan [(0.0) (10.10)], algoritma akan melakukan pengecekan apakah garis tersebut melalui pengahalang. Penghalang dapat di ekspresikan sebagai berikut ( 12) ( 12) 4 2 2 x - - y - = (3.2.1) Dan persamaan untuk garis ialah y = x dimana 0 < x < 10 (3.2.2) Gabungkan kedua persamaan (3.2.1) dan (3.2.2) akan menghasilkan dua hasil yang memungkinkan. Jika koordinat X dari penghalang berada diantara 2 titik acuan yang diberikan dan kedua sulusi memiliki nilai real. Maka algoritma akan menyatakan bahwa garis tersebut akan melalui penghalang dan akan mengeliminasi kromoson tersebut.

4.3.2 ANALISA DAN PEMBAHASAN

Piranti lunak penerapan algoritma genetika pada perencanaan lintasan kendaraan dibuat menggunakan Matlab7.1 dengan sistem operasi Microsoft Windows XP.

Hasil dari kedua gambar di atas ada perbedaan pada jumlah generasi dan hasil yang ditemukan. Pada gambar 7. dilakukan iterasi sampai pada generasi ke-10 dan pada gambar 8. dilakukan iterasi sampai pada generasi ke-100. Dimana jarak yang ditempuh pada gambar 8. lebih kecil dibandingkan dengan gambar 7. Hal ini menunjukkan bahwa hasil yang ditemukan pada iterasi ke-100 lebih baik daripada hasil pada iterasi ke-10.

Hasil dari kedua gambar di atas ada perbedaan pada jumlah generasi dan hasil yang ditemukan. Pada gambar 9. dilakukan iterasi sampai pada generasi ke-10 dan pada gambar 10. dilakukan iterasi sampai pada generasi ke-100. Dimana jarak yang ditempuh pada gambar 10. lebih kecil dibandingkan dengan gambar 9. Hal ini menunjukkan bahwa hasil yang ditemukan pada iterasi ke-100 lebih baik daripada hasil pada iterasi ke-10.

Hasil dari kedua gambar di atas ada perbedaan pada jumlah generasi dan hasil yang ditemukan. Pada gambar 11. dilakukan iterasi sampai pada generasi ke-10 dan pada gambar 12. dilakukan iterasi sampai pada generasi ke-100. Dimana jarak yang ditempuh pada gambar 12. lebih kecil dibandingkan dengan gambar 11. Hal ini menunjukkan bahwa hasil yang ditemukan pada iterasi ke-100 lebih baik daripada hasil pada iterasi ke-10.

Lintasan terpendek yang didapatkan adalah 28,7062 satuan yang didapat pada generasi ke-100 dengan 2 titik acuan.

4.4 Job Shop Scheduling Problem (JSP)

Job Shop secara umum adalah terdapat m buah mesin dan n buah jobs atau pekerjaan yang harus diproses. Tiap pekerjaan terdiri dari l operasi dan tiap operasi harus diproses tanpa ada interupsi dalam jangka waktu dan mesin tertentu. Operasi-operasi di dalam pekerjaan merupakan jenis kegiatan yang harus diselesaikan di dalam suatu mesin, tiap operasi memiliki karakteristik pada kebutuhan mesin dan lamanya waktu terproses. Pemrosesan operasi merupakan kegiatan penyediaan mesin untuk sebuah operasi dalam rangka penyelesaian atau pengeksekusian operasi tersebut dalam waktu tertentu dengan rute atau jadwal tertentu.

Jadwal merupakan suatu urutan antrian tertentu operasi-operasi untuk dieksekusi, sebuah penjadwalan adalah sebuah pengalokasian operasi dalam mendapatkan mesin dengan urutan tertentu[2]. Mesin bertugas untuk menyelesaikan operasi-operasi di dalam pekerjaan sebagai alat, tiap mesin dapat memproses hanya satu operasi dalam satu waktu. Permasalahan utama dalam JSP adalah untuk menentukan jadwal untuk tiap pekerjaan pada tiap mesin, jadwal tersebut mengatur pekerjaanpekerjaan yang harus diselesaikan oleh satu mesin atau lebih. Banyaknya jadwal yang mungkin digambarkan oleh (n!)m untuk n pekerjaan dan m mesin[5]. Total waktu proses dipengaruhi oleh waktu setup atau waktu dimulainya pemrosesan tiap pekerjaan. Tiap jadwal dapat dievaluasi dengan berbagai macam pengukuran, tingkat keberhasilan pengukuran berhubungan dengan waktu yang dihabiskan satu pekerjaan dalam jadwal atau pengoptimalan waktu mesin atau ke duanya. Beberapa tingkat keberhasilan pengukurannya yaitu:

1. Flowtimes adalah jumlah waktu yang dihabiskan tiap pekerjaan dalam jadwal, ini hampir mirip dengan pekerjaan dalam proses inventori.

2. Makespan adalah total waktu untuk seluruh pekerjaan dalam prosesnya.

3. Lateness and earliness adalah pengukuran nilai deviasi dari pertama dan ke dua.

4. Machine and labor utilization adalah pengoptimalan penggunaan mesin dan pekerja.

Pemilihan jadwal berdasarkan pada sasaran untuk meminimalisasi makespan atau meminimalisasi rata-rata flowtime, atau lainnya.

Beberapa priority rule atau aturan prioritas sederhana dapat digunakan terutama untuk kasus-kasus sejumlah kecil dari mesin atau sumber. Ini dikembangkan untuk menghasilkan jadwal yang baik untuk beberapa objek yang berbeda dan pada kondisi yang berbeda.

Terdapat beberapa batasan pada pekerjaan dan mesin, yaitu:

1. Sebuah pekerjaan tepat mengunjungi satu mesin sekali.

2. Tiap mesin hanya dapat memproses sebuah operasi pada satu waktu dan selalu siap setiap waktu tanpa adanya gangguan kerusakan atau dalam perbaikan.

3. Operasi tidak dapat diinterupsi, dengan kata lain setelah operasi berlangsung, operasi itu harus diselesaikan sebelum operasi yang lain diproses pada mesin yang sama.

4. Terdapat batasan untuk lebih mendahulukan suatu operasi sebelum operasi berikutnya berlangsung atau berurutan pada pekerjaan yang sama, tetapi tidak berlaku pada pekerjaan yang berbeda

5. Tiap tipe mesin jumlahnya hanya satu.

6. Setelah sebuah operasi selesai diproses pada suatu mesin, akan langsung ditransfer ke mesin berikutnya secepatnya dan waktu transfer diabaikan.

Setiap operasi mempunyai jenis kegiatan tertentu, dikerjakan mesin tertentu dan waktu proses yang tertentu pula.

4.5 Pencarian Nilai Fungsi Maksimum

Metoda pencarian nilai optimum klasik pada umumnya memanfaatkan kemiringan kurva asimptotis yang konvergen pada solusi yang diinginkan. Proses konvergensi dilakukan dengan mengevaluasi satu titik pada kurva asimptotis di setiap proses iterasinya. Pada proses iterasi selanjutnya, titik evaluasi tersebut digeser ke arah lembah/bukit yang diperkirakan akan menuju ke titik konvergen yang ada. Analisis titik per titik seperti ini dapat menghasilkan nilai yang benar hanya jika permasalahan yang sedang dianalisis memiliki titik ekstrim yang menjamin bahwa nilai optimum lokal juga merupakan nilai optimum global.

Di lain pihak, algoritma genetika melakukan proses pencarian nilai optimum pada beberapa titik secara bersamaan (satu generasi). Proses iterasi kemudian dilakukan dengan pendekatan generasi ke generasi yang mengalami proses evolusi, tetapi jumlah anggota (chromosome) pada setiap generasi, yang merupakan kumpulan solusi, umumnya dipertahankan tetap. Chromosome yang dianalisis dapat merupakan kode binary, integer atau desimal. Dalam proses evolusi, sejumlah gen yang membentuk chromosome melewati proses crossover (kawin silang) dan/atau mutation (perubahan gen secara alami). Chromosome yang baik akan terus hidup, sedangkan chromosome yang buruk akan mati dengan sendirinya. Algoritma genetika menggunakan hukum transisi probabilistik untuk memilih solusi (chromosome) yang terus dipertahankan hidup sesuai dengan ketentuan yang diinginkan (fitness function), sehingga proses pencarian solusi optimum dapat diarahkan ke arah yang diperkirakan akan lebih baik.

Secara umum, tahapan proses dari algoritma genetika diperlihatkan pada Gambar 1. Seperti terlihat pada gambar, chromosome merupakan representasi dari solusi; operator genetika yang terdiri dari crossover dan mutation dapat dilakukan kedua-duanya atau hanya salah satu saja; selanjutnya, operator evolusi dilakukan melalui proses seleksi chromosome dari parent (generasi induk) dan dari offspring (generasi turunan) untuk membentuk generasi baru (new population) yang diharapkan akan lebih baik dalam memperkirakan solusi optimum; proses iterasi kemudian berlanjut sesuai dengan jumlah generasi yang ditetapkan. Penjelasan secara rinci mengenai setiap tahapan proses dari algoritma genetika dengan menggunakan contoh pencarian nilai maksimum untuk suatu fungsi sinus tertentu.

4.5.1 Karakteristik Fungsi Sinus Yang Dianalisis

Bentuk fungsi sinus yang dianalisis dalam makalah ini cukup kompleks karena, selain hanya ada satu nilai fungsi maksimum global, juga terdapat banyak nilai fungsi maksimum lokal, seperti diperlihatkan pada Gambar 2. Adapun fungsi sinus yang dimaksud adalah:

Nilai fungsi maksimum global yang dicari dibatasi hanya pada rentang nilai x1 dan x2 yang ditetapkan. Kenyataan bahwa ada nilai fungsi yang lebih besar dari pada nilai fungsi maksimum global di luar rentang nilai x1 dan x2 yang telah ditetapkan bukan merupakan masalah dalam bahasan ini.

Proses perhitungan nilai fungsi maksimum global dari persamaan (1) dengan menggunakan teknik konvergensi konvensional pada dasarnya sulit dilakukan. Misalnya, nilai fungsi maksimum yang diperoleh dengan menggunakan fasilitas “solver” pada program aplikasi Ms-Excel akan terus berubah dan sangat tidak mudah untuk mendapatkan nilai fungsi maksimum global. Penentuan nilai fungsi maksimum global secara grafis seperti diilustrasikan pada Gambar 2 juga sulit dilakukan. Sedangkan, dengan menggunakan algoritma genetika, solusi optimum yang diinginkan umumnya dapat diperoleh.

Pernyataan terakhir mungkin masih terdengar kurang pasti tetapi memang demikian halnya. Ketidakpastian tersebut sebenarnya merupakan sifat unik dari algoritma genetika yang memanfaatkan bilangan random dan probabilitas dalam proses pencarian solusi optimum yang diinginkan. Solusi yang diperoleh tidak selalu tepat dan dapat berubah-ubah. Meskipun demikian, dengan mengatur proses seleksi generasi baru secara cermat, generasi baru terbaik yang merupakan solusi yang tepat sangat mungkin dapat diperoleh.

Oleh karena itu, untuk persoalan yang sederhana, algoritma genetika secara teoritis tidak lebih baik dibandingkan dengan teknik konvergensi konvensional. Akan tetapi, algoritma genetika akan sangat bermanfaat khususnya untuk penyelesaian masalah yang sulit dipecahkan, seperti halnya fungsi sinus pada persamaan (1).

4.5.2 Contoh Tahapan Proses Dari Algoritma Genetika

Berikut diuraikan secara rinci contoh lima tahapan proses utama dari algoritma genetika, sesuai dengan yang telah diilustrasikan pada Gambar 1.

4.5.2.1 Kodifikasi Solusi dan Pembentukan Generasi Awal

Proses kodifikasi dari solusi yang dicari ke dalam chromosome merupakan isu kunci dalam algoritma genetika. Untuk fungsi sinus yang dianalisis, solusi yang dicari adalah nilai x1 dan x2. Jika ketelitian nilai x1 dan x2 adalah empat desimal, maka kode binary yang digunakan harus dapat mewakili rentang nilai -30,000 ÷ 120,000 (18 bits = 262,143) untuk nilai x1, dan rentang nilai 41,000 ÷ 58,000 (15 bits = 32767) untuk nilai x2.

Setiap bit merupakan gen yang membentuk chromosome. Dengan demikian, masingmasing chromosome memiliki 33 gen yang merupakan gabungan dari nilai x1 dan x2 sebagai solusi.

Generasi awal kemudian dibentuk dengan jumlah chromosome yang biasanya ditetapkan antara 10 ÷ 100, dengan jumlah gen per chromosome terdiri dari bilangan random sebesar 33 bits. Makin besar jumlah populasi yang dibentuk, maka akan makin besar pula kemungkinan solusi optimum yang dapat dihasilkan dari algoritma genetika. Tetapi, sebagai konsekwensi, waktu pemrosesan komputer akan menjadi lebih lama.

Sebagai contoh, dalam proses pencarian nilai fungsi sinus maksimum, 10 chromosome yang mungkin terbentuk secara random untuk menjadi generasi awal adalah sbb.:

C1 = 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 = { 22854 ; 19061 } = 19.483

C 2 = 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 = { 171564 ; 25374 } = 19.300

C 3 = 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 = { 102085 ; 31443 } = 23.913

C 4 = 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 = { 253253 ; 17323 } = 31.458

C 5 = 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 = { 246007 ; 1765 } = 28.774

C 6 = 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 = { 217348 ; 505 } = 27.949

C 7 = 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 = { 5718 ; 734 } = 26.561

C 8 = 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 = { 207907 ; 23806 } = 23.120

C 9 = 0 1 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 = { 109029 ; 24315 } = 16.736

C 10 = 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 0 0 = { 34513 ; 16208 } = 24.327

Nilai x1 dan x2 sebagai solusi dan nilai fungsi sinus untuk masing-masing chromosome juga telah dihitung; dimana, chromosome 4 merupakan solusi yang terkuat {f (x1 , x2) = 31.458} dan chromosome 9 merupakan solusi yang terlemah {f (x1 , x2) = 16.736}.

4.5.2.2 Proses Crossover

Crossover dan juga mutation merupakan dua operator genetika utama. Secara umum, operator genetika dapat diklasifikasikan ke dalam 3 kelas, yaitu:

Operator konvensional
Operator aritmatika
Operator direksional
Untuk chromosome dengan kode binary, proses crossover dilakukan dengan menggunakan operator konvensional, seperti yang akan diuraikan berikut ini. Dua operator crossover lainnya dijelaskan oleh Gen, et.al. (2005). Proses crossover bekerja pada dua chromosome melalui pertukaran gen (kawin silang) untuk menghasilkan dua chromosome baru sebagai turunannya. Cara yang mudah untuk dapat melakukan pertukaran gen adalah dengan menentukan titik potong secara random. Potongan gen sebelah kiri titik potong dari satu chromosome induk kemudian digabungkan dengan potongan gen sebelah kanan titik potong dari chromosome induk lainnya (lihat Gambar 1).

Jumlah chromosome yang mengalami proses crossover pada satu generasi ditentukan secara random berdasarkan tingkat probabilitas crossover yang diijinkan. Pada tingkat probabilitas crossover yang cukup tinggi, proses pencarian solusi optimum dapat menjelajah ke ruang explorasi yang lebih luas sehingga kemungkinan terperangkap pada nilai optimum lokal yang salah dapat dihindari. Akan tetapi, jika tingkat probabilitas crossover yang diijinkan terlalu tinggi, maka waktu pemrosesan komputer dapat menjadi lebih lama, dan proses pencarian solusi optimum menjadi redundant.

Kesepuluh chromosome setelah mengalami proses crossover diperlihatkan pada daftar berikut. Untuk tingkat probabilitas crossover sebesar 25%, dua chromosome 5 dan 9 ditetapkan secara random untuk mengalami proses crossover pada generasi ini. Proses crossover dilakukan pada gen ketujuh yang juga ditetapkan secara random. Terlihat bahwa chromosome 5 melemah dengan nilai fungsi turun dari 28.774 menjadi 11.060. Sedangkan, chromosome 9 menguat dengan nilai fungsi naik dari 16.736 menjadi 22.393.

C1’ = 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 = { 22854 ; 19061 } = 19.483

C 2’ = 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 = {171564 ; 25374 } = 19.300

C 3’ = 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 = {102085 ; 31443 } = 23.913

C 4’ = 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 = {253253 ; 17323 } = 31.458

C 5’ = 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 = { 248293 ; 24315 } = 11.060

C 6’ = 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 = {217348 ; 505 } = 27.949

C 7’ = 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 = { 5718 ; 734 } = 26.561

C 8’ = 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 = {207907 ; 23806 } = 23.120

C 9’ = 0 1 1 0 1 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 = { 106743 ; 1765 } = 22.393

C10’ = 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 0 0 = { 34513 ; 16208 } = 24.327

4.5.2.3 Proses Mutation

Mutation merupakan operator genetika kedua dan hanya bekerja pada beberapa gen yang melakukan penyesuaian diri terhadap kondisi lingkungan sekitar. Proses mutation terjadi agar makhluk hidup dapat terus bertahan hidup dengan kwalitas yang lebih baik. Pada algoritma genetika, proses mutation yang menghasilkan gen yang lebih baik dapat membuat chromosome tetap bertahan dalam proses seleksi dan diharapkan akan dapat makin mendekati solusi optimum. Sebaliknya, proses mutation yang menghasilkan gen yang lebih buruk dapat membuat chromosome tereliminasi dalam proses seleksi.

Untuk chromosome dengan kode binary, proses mutation juga dilakukan dengan menggunakan operator konvensional, yaitu mengubah nilai 0 menjadi 1, atau sebaliknya (lihat Gambar 1). Jumlah gen yang mengalami proses mutation pada satu generasi ditentukan secara random berdasarkan tingkat probabilitas mutation yang diijinkan.

Seperti halnya pada proses crossover, jika tingkat probabilitas mutation yang diijinkan terlalu rendah, maka ada gen yang mungkin seharusnya berguna tidak pernah ikut terseleksi. Sebaliknya, jika tingkat probabilitas mutation terlalu tinggi, maka chromosome 6 turunan mungkin akan mulai kehilangan kesamaan dengan chromosome induknya sehingga membuat algoritma genetika kehilangan kemampuan untuk belajar dari sejarah dalam proses pencarian solusi optimum.

Untuk contoh pencarian nilai fungsi sinus maksimum, populasi yang ada terdiri dari 10x33 gen. Jika tingkat probabilitas mutation yang diijinkan adalah 10%, maka jumlah gen yang akan mengalami proses mutation pada satu generasi adalah kurang lebih 33.

Pada daftar berikut ini diperlihatkan kesepuluh chromosome setelah mengalami proses mutation.

C1” = 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 1 1 = { 20806 ; 6775 } = 19.995

C2” = 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 = { 171560 ; 25374 } = 19.298

C3” = 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 = { 101829 ; 26835 } = 16.081

C4” = 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 = { 253381 ; 17067 } = 28.350

C5” = 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 = { 248293 ; 24287 } = 11.443

C6” = 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 1 = { 219142 ; 2425 } = 35.340

C7” = 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 0 = { 153174 ; 19422 } = 19.229

C8” = 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 = { 207907 ; 21726 } = 24.000

C9” = 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 0 0 = { 73971 ; 9700 } = 22.262

C10” = 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 = { 100080 ; 16336 } = 21.751

Gen yang mengalami proses mutation pada generasi ini adalah sebanyak 35. Terlihat bahwa semua chromosome pada tingkat probabilitas 10% harus melewati proses mutation. Chromosome 6 sekarang menjadi yang terkuat dan chromosome 5 tetap yang terlemah.

4.5.2.3 Proses Evaluasi

Secara umum, proses evaluasi dalam pencarian nilai fungsi sinus maksimum terdiri dari tiga tahapan, yaitu:

Konversi chromosome (kode binary) ke dalam solusi yang dinyatakan dengan bilangan desimal.

Perhitungan nilai fungsi sinus, ( , ) 1 2 y = f x x , dengan menggunakan persamaan (1) berdasarkan nilai x1 dan x2 yang diperoleh untuk masing-masing chromosome.
Perhitungan nilai kecocokan (fitness) yang dalam hal ini juga adalah ’ ( , ) 1 2 y = f x x . Untuk setiap generasi, nilai y’max selalu dapat diperoleh. Akan tetapi, apakah nilai y’max ini merupakan nilai fungsi maksimum global yang dicari tetap tidak dapat langsung diketahui dengan algoritma genetika. Untuk itu, proses iterasi harus terus dilakukan sampai semua generasi yang diinginkan (~ 1000 generasi) telah selesai dianalisis.
4.5.2.3 Proses Seleksi

Proses seleksi dilakukan untuk memilih chromosome induk dan chromosome turunan berdasarkan nilai kecocokan yang diperoleh di atas untuk membentuk generasi baru yang lebih baik ke arah solusi optimum yang dicari. Ada tiga ketentuan dasar yang harus dipertimbangkan dalam melakukan proses seleksi, yaitu:

a. Jumlah chromosome pada setiap generasi baru harus selalu dipertahankan tetap. (untuk contoh proses pencarian nilai fungsi sinus maksimum, jumlah chromosome = 10)

b. Fungsi seleksi yang cocok harus dipilih sesuai dengan jenis aplikasinya. Banyak fungsi seleksi yang telah diusulkan; Gen, et.al. (2005) mengelompokkan fungsi seleksi ke dalam tiga kategori, yaitu: Fungsi seleksi normal yang cenderung untuk mengeliminasi chromosome yang memiliki nilai kecocokan ekstrim. Fungsi seleksi direksional yang ditargetkan untuk menurunkan atau menaikkan nilai kecocokan rata-rata dari seluruh chromosome yang dianalisis (populasi). Fungsi seleksi acak yang cenderung untuk mengeliminasi chromosome yang memiliki nilai kecocokan tengah.

Fungsi seleksi direksional merupakan fungsi yang umum digunakan, termasuk untuk contoh proses pencarian nilai fungsi sinus maksimum. Empat alternatif fungsi seleksi direksional dapat dianalisis dengan menggunakan program GA, termasuk:

1. 10 chromosome yang membentuk generasi baru dipilih secara random berdasarkan kurva distribusi kumulatif nilai fungsi kecocokan, baik yang berasal dari chromosome induk, maupun dari chromosome turunan dengan prosedur, sbb.:

i) hitung probabilitas nilai fungsi kecocokan,

ii) ambil nilai random, Prandom (= 0 ÷ 1)

iii) pilih chromosome i yang memenuhi kondisi (Pi-1 < Prandom = Pi)

iv) ulangi langkah ii) dan iii) untuk 10 chromosome yg membentuk generasi baru

2. Sama seperti alternatif 1 di atas tetapi chromosome terbaik dari generasi induk atau generasi turunan harus selalu disertakan dalam generasi baru.

3. Semua chromosome turunan dipilih sebagai generasi baru, kecuali chromosome terburuk yang digantikan oleh chromosome terbaik dari generasi induk; dan untuk menghindari duplikasi, chromosome pengganti harus lebih baik dibandingkan dengan yang terbaik dari chromosome turunan.

4. 10 chromosome yang memiliki nilai fungsi kecocokan terbesar dipilih dari antara gabungan chromosome induk dan chromosome turunan sebagai generasi baru.

Pada contoh, generasi baru yang dihasilkan dari proses seleksi untuk fungsi seleksi direksional alternatif 3 adalah sama dengan generasi turunan (pada Bab III.3), karena chromosome terbaik dari generasi induk tidak lebih baik dibandingkan dengan chromosome terbaik dari generasi turunan. Jadi, nilai fungsi sinus terbaik yang dihasilkan 8 pada generasi kedua ini adalah tetap 35.340 pada chromosome 6. Sedangkan, nilai fungsi sinus maksimum yang diharapkan adalah 38.850, untuk nilai x1 = 11.6255 dan x2 = 5.7250. Untuk itu, proses regenerasi harus terus dilanjutkan, seperti yang akan diuraikan berikut ini.

4.5.3 Program GA

Tampilan program GA untuk pencarian nilai fungsi sinus maksimum diperlihatkan pada Gambar 3. Proses regenerasi selalu dilakukan untuk 1000 generasi. Generasi yang menghasilkan chromosome (solusi) terbaik dapat diketahui di akhir proses regenerasi. Ketiga data input utama lainnya, yaitu jumlah chromosome, probabilitas crossover dan probabilitas mutation juga diperlihatkan di sini.

Gambar 3: Contoh data input (default) pada program GA dengan hasil generasi awal

Gambar 4: Tahapan konvergensi dalam mencapai nilai fungsi sinus maksimum untuk 5x pengulangan proses

Gambar 4 memperlihatkan trayektori pencapaian generasi terbaik yang memberikan nilai fungsi sinus maksimum untuk 5 kali pengulangan proses. Sifat stochastic algoritma genetika mulai dari proses pembentukan generasi awal sampai pada proses pencapaian generasi terbaik yang selalu berubah terlihat pada Gambar 4. Bahkan, solusi optimum tidak selamanya akan dapat dihasilkan jika empat data input utama, yaitu jumlah chromosome, probabilitas crossover, probabilitas mutation dan fungsi seleksi tidak ditentukan secara tepat.

4.5.4 Analisis Faktor-Faktor Pengaruh Dominan Dalam Algoritma Genetika

Gambar 5 memperlihatkan pengaruh dari masing-masing data input utama terhadap nilai fungsi sinus maksimum yang dihasilkan. Untuk menggambarkan keempat faktor pengaruh tersebut digunakan nilai data input berikut sebagai acuan, yang dari analisis pendahuluan diketahui merupakan data input yang relatif terbaik.

Jumlah chromosome = 10

Probabilitas crossover = 0.25

Probabilitas mutation = 0.05

Fungsi seleksi : memilih chromosome turunan secara random sebagai generasi baru dan harus selalu menyertakan chromosome yang memberikan nilai fungsi sinus maksimum (alternatif 2)

Gambar 5a memperlihatkan bahwa rentang jumlah chromosome yang dianalisis bervariasi dari 10 ÷ 100. Secara umum, nilai fungsi sinus maksimum selalu dapat diperoleh dalam 5 kali pengulangan proses, kecuali pada jumlah chromosome sebesar 10 dan 60 dimana solusi yang diperoleh agak bervariasi. Sedikit perbedaan solusi juga terlihat pada jumlah chromosome sebesar 20, 50 dan 90. Perbedaan2 solusi tersebut pada prinsipnya selalu mungkin terjadi dalam proses pencarian nilai optimum dengan menggunakan algoritma genetika yang berdasarkan pendekatan stochastic. Meskipun demikian, jika siklus regenerasi diperpanjang, maka nilai fungsi sinus maksimum umumnya akan dapat diperoleh.

(a) pengaruh dari jumlah chromosome

Gambar 5: Pengaruh dari berbagai data input terhadap nilai fungsi sinus maksimum dalam 5x pengulangan proses

(b) pengaruh dari probabilitas crossover

(d) pengaruh dari fungsi seleksi

Gambar 5: Pengaruh dari berbagai data input terhadap nilai fungsi sinus maksimum dalam 5x pengulangan proses (...lanjutan)

Rentang probabilitas crossover yang dianalisis bervariasi dari 0 ÷ 100%. Gambar 5b menunjukkan, bahwa secara umum nilai fungsi sinus maksimum juga tidak begitu dipengaruhi oleh tingkat probabilitas crossover. Variasi nilai fungsi sinus maksimum yang terlihat pada Gambar 5b akan berkurang jika jumlah chromosome yang dianalisis diperbesar.

Yang cukup menarik dari analisis sensitivitas terhadap tingkat probabilitas crossover adalah bahwa proses pencarian nilai optimum seringkali terperangkap pada nilai fungsi sinus maksimum lokal sebesar 38.844. Dari analisis awal diketahui, bahwa masalah ini kelihatannya dapat diatasi dengan menggunakan fungsi seleksi gabungan. Studi yang lebih mendalam masih diperlukan untuk menjelaskan kasus ini.

Pengaruh tingkat probabilitas mutation terhadap nilai fungsi sinus maksimum ternyata sangat signifikan, seperti diperlihatkan pada Gambar 5c. Bahkan, jika proses mutation tidak dilakukan, maka proses pencarian nilai optimum dengan menggunakan algoritma genetika sulit untuk konvergen. Untuk contoh kasus yang sedang dianalisis, tingkat probabilitas mutation terbaik kurang lebih adalah 5%.

Akhirnya, Gambar 5d memperlihatkan pengaruh fungsi seleksi terhadap nilai fungsi sinus maksimum. Generasi baru yang ditentukan hanya secara random (alternatif 1) umumnya tidak dapat memberikan solusi optimum. Sebaliknya, solusi optimum hampir selalu dapat diperoleh dengan menggunakan pendekatan meta-heuristic yang terus mempertahankan chromosome terbaik pada setiap proses regenerasi (alternatif 2 ÷ 4); dan, alternatif 2 yang merupakan pendekatan stochastic secara marginal dapat dikatakan lebih menjanjikan untuk menghasilkan solusi optimum yang diinginkan dalam kasus ini\

BAB 5

PENUTUP

5.1 Kesimpulan

1. Algoritma genetika karena merupakan pendekatan stochastic tidak selalu dapat memberikan solusi yang tepat, khususnya jika empat data input utama, yaitu jumlah chromosome, probabilitas crossover, probabilitas mutation dan fungsi seleksi, tidak ditentukan secara cermat. Meskipun demikian, jika proses regenerasi terus berlanjut, maka solusi optimum pada akhirnya akan dapat diperoleh. Untuk aplikasi algoritma genetika waktu pemrosesan komputer umumnya dapat dilakukan relatif secara cepat.

2. Secara umum, untuk contoh proses pencarian nilai fungsi sinus maksimum, jumlah chromosome dan probabilitas crossover tidak begitu mempengaruhi solusi optimum; sedangkan, probabilitas mutation memiliki nilai optimum, yaitu di sekitar 5%. Probabilitas mutation yang terlalu kecil atau terlalu besar cenderung tidak dapat menghasilkan solusi optimum; dan akhirnya, 3 alternatif fungsi seleksi yang terus mempertahankan chromosome terbaik untuk tetap disertakan pada setiap proses regenerasi umumnya dapat memberikan solusi optimum yang diinginkan.

3. Dari studi yang lebih mendalam pada buku referensi dan program GA diketahui bahwa algoritma genetika akan bermanfaat khususnya untuk persoalan yang sulit terpecahkan dengan pendekatan deterministik.

Bibliography

[1] Gen M and Cheng R (1997), “Genetic Algorithms and Engineering Design”, John Wiley and Sons, Inc., USA.

[2] Kosasih D (2005), “Petunjuk Pengoperasian Program GA”, Departemen Teknik Sipil, ITB, Bandung.

[3] Pakereng, M. A. Ineke, 2007, Kriptosistem Menggunakan Algoritma Genetika Pada Data Citra, Yogyakarta: Thesis. Universitas Gadjah Mada

[4] Nugroho dkk, Andi, 2009. Generator Melodi Berdasarkan Skala dan Akord Menggunakan Algoritma Genetika, Jurnal Informatika, Vol 5, No 1, Juni 2009: 15 – 29.

[5] Koelle, David, 2010. Java API for Music Programming, http://www.jfugue.org/. Diakses tanggal 4 April 2012.

[6] Suyanto, 2005, Algoritma Genetika dalam Matlab, Yogyakarta: ANDI OFFSET.

[7] Smith, Instruments, Dave, 2009. About Dave Smith Instruments, http://www.davesmithinstruments.com/about/index.php. Diakses tanggal 4 April 2012.

[8] Pressman, Roger S., 2001. Software Engineering a Practitioner’s Approach, New York : McGraw-Hill Higher Education.

Nanda Blog

No change, No Success

GUNADARMA

Daftar isi :

Total Pageviews

Followers

About Me

Blog Archive