c'mon...express your action

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). Detail dari proses crossover ini akan dibahas kemudian.
• 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.
ya...kira-kira seperti itulah genetic algorithm

sumber : http://bambangeko.wordpress.com/2007/08/29/a-gentle-introduction-to-genetic-algorithm-bagian-pertama/