Genetic Algirithm

RESUME VIDEO PEMBELAJARAN 3
KECERDASAN BUATAN

SITI FITRIANAH (18.01.013.120)

GENETIC ALGORITHM

Outline :

1. What is Solution?

2. Metahuristic Search

- Evolutionary Algorithms

Genetic Algorithm

a. Chromosome

b. Fitness

c. Parent Selection

d. Crossover and Mutation

e. Survivor Selection

Genetic Algorithm adalah sebuah teknik searching untuk mencari solusi dari suatu permasalahan optimasi. Teknik ini diinspirasi dari biologi evolutionary termasuk masalah inheritance, mutation, selection, and crossover. Metode ini melakukan proses searching dengan langkah-langkah sebagai berikut:

1. Populasi diciptakan secara random

2. Setiap individu dari populasi dievaluasi

3. Beberapa individu dipilih untuk berdasarkan nilai fitnessny

4. Individu yang terpilih tersebut kemudian dimodifikasi (di-crossover atau dimutasi

5. Semua individu yang dimodifikasi disatukan menjadi satu populasi baru. Apabila individu yang baru yang terbentuk mempunyai nilai fitness yang lebih rendah dari orang tuanya, individu yang baru tidak dimasukkan di dalam populasi baru, dan dapat tetap menggunakan individu yang lama.

6. Apabila banyaknya jumlah pembentukan populasi telah mencapai angka tertentu, atau level fitness yang memuaskan sudah dicapai, maka proses dihentikan. Apabila belum, populasi baru kemudian digunakan untuk melakukan proses yang sama mulai dari tahap nomor 2.

Menyimpulkan pada langkah-langkah yang tersebut di atas, maka metode ini memerlukan pendefinisian representasi genetic dari domain solusi, dan fungsi fitness untuk mengevaluasi domain solusi. Khusus untuk modifikasi crossover dan mutasi, crossover melakukan kombinasi ulang dari dua atau lebih parents dan mutasi melakukan perubahan terhadap 1 atau lebih dari bagian-bagian yang terdapat pada individu yang dimodifikasi. Bagian-bagian dari individu yang akan dimodifikasi dalam proses ini dapat ditentukan secara random. Kedua jenis fungsi modifikasi ini sangat berguna karena dapat menghindarkan proses searching dari permasalahan local minima.

Genetic Algorithm (GA) adalah bagian dari Evolutionary Algorithm yaitu suatu algoritma yang mencontoh proses evolusi alami dimana konsep utamanya adalah individu-individu yang paling unggul akan bertahan hidup, sedangkan individu-individu yang lemah akan punah[1]. Keunggulan individu-individu ini diuji melalui suatu fungsi yang dikenal sebagai fitness function. Fitness dalam GA didefinisikan sebagai gambaran kelayakan suatu solusi terhadap suatu permasalahan. Fitness Function akan menghasilkan suatu nilai fitness value yang akan menjadi referensi untuk proses GA selanjutnya.

Proses GA dimulai dengan menentukan populasi awal initial population yang terdiri dari beberapa kromosom yang disusun oleh beberpa gen yang merupakan representasi dari kandidat-kandidat solusi dari suatu masalah. Kandidat-kandidat terbaik akan dipilih melalui proses selection, berdasarkan fitness value yang telah dihitung untuk setiap kromosom dalam populasi. Kandidat – kandidat terpilih dari proses ini adalah individu-individu yang akan mengisi mating pool yaiu suatu set dimana dua parents akan dibentuk dari sini. Dalam Evolutionary Algorithm prinsip bertahan muncul karena adanya proses reproduksi. Turunan offspring yang dihasilkan akan membawa sifat gen orangtuanya (parents) , oleh sebab itu parents dipilih dari mating pool yang merupakan kumpulan kandidat-kandidat terbaik dari suatu populasi. Dengan demikian turunan yang dihasilkan adalah turunan yang memiliki sifat unggul dari kedua orang tuanya.

GA adalah salah satu algoritma yang digunakan untuk proses optimisasi. Dalam optimisasi, kondisi optimal solusi-solusi yang diperoleh adalah target utama yang akan dicapai. Namun dalam algoritma optimisasi, kondisi optimum lokal local optimum sering terjadi. Optimum lokal adalah suatu kondisi dimana algoritma mencapai nilai tertinggi atau terendah pada beberapa nilai kandidat solusi. Hal ini berlawanan dengan kondisi optimum global (global optimum) yaitu algoritma mencapai niai teringgi atau terendah untuk seluruh kandidat solusi dalam suatu masalah tertentu. Optimum lokal dapat terjadi salah satunya diakibatkan oleh populasi mencapai format konvergensi terlalu dini premature convergence. Menurut Rajeev dan Krisnamoorthy [2] kriteria tercapainya konvergensi adalah apabila sekitar 80% atau 85 % dari jumlah kromosom memiliki nilai gen yang sama. Salah satu cara untuk mencegah masalah prematur dini ini adalah dengan mempertahankan keragaman kromosom dari suatu populasi. Dalam GA, keragaman kromosom dari suatu populasi dapat dipertahankan dengan mengimplementasikan operator crossover dan mutasi (mutation).

Crossover adalah suatu operator rekombinasi yang bertujun untuk memperloleh individu yang lebih baik. Operator crossover melakukan rekombinasi dari set parents yang akan dipilih secara acak dari mating pool yang telah terbentuk dari proses seleksi. Crossover akan menghasilkan satu set turunan offspring yang keragamannya akan tetap dipertahankan dengan proses selanjutnya yaitu mutasi. Pada operator mutasi, keragaman akan dipertahankan dengan menukar salah satu atau lebih gen dalam kromosom dengan nilai kebalikannya. Sebagai contoh, jika kromosom kita memiliki nilai biner 0 dan 1 maka jika secara acak titik mutasi yang terpilih memiliki nilai 1, nilai ini akan ditukar menjadi nilai 0 atau sebaliknya. Hasil dari operator mutasi ini adalah turunan baru yang selanjutnya akan kembali diuji pada funsi fitness untuk melihat kelayakan populasi baru dari hasil proses GA ini sebagai kandidat solusi dari masalah yang diberikan. Proses pengujian fitness, seleksi,crossover dan mutasi akan dilakukan secara berulang sedemikian hingga telah dipenuhi salah satu kontrol perulangan proses GA berikut yaitu iterasi, konvergensi atau nilai fitness.