Artificial Intelligence Indra EHM

Sejarah

Simulasi komputer dari evolusi dimulai sejak awal 1954 dengan pekerjaan dari Nils Aall Barricelli, yang menggunakan komputer di Institute of Advanced Study, Princetown, New Jersey. Tetapi, publikasinya pada tahun 1954 tidak diketahui secara luas. Mulai tahun 1957, ahli genetika asal Australia Alex Fraser mempublikasikan beberapa tulisan mengenai simulasi proses seleksi dari organisme dengan beberapa loci yang mengendalikan ancaman/ gangguan yang dapat diukur. Dari awal ini, simulasi komputer dari evolusi biologi menjadi lebih dikenal pada awal 1960, dan metode – metodenya dituliskan dalam beberapa buku oleh Fraser, Burnell(1970), dan Crosy(1973). Simulasi yang dilakukan oleh Fraser mengandung seluruh elemen penting dari algoritma genetika modern. Sebagai tambahan, Hans Bremermann mempublikasikan beberapa tulisan pada tahun 1960 yang juga mengadopsi sebuah populasi dari solusi untuk mengoptimisasi masalah, rekombinasi yang terjadi, mutasi dan seleksi. Penelitian Bremermann juga memasukkan elemen dari modern algoritma genetika. Pelopor awal lainnya yang layak diketahui antara lain Richard Friedberg, George Friedman, dan Michael Conrad yang tulisannya dicetak ulang oleh Fogel pada tahun 1998.

Walaupun Barricelli, dalam pekerjaan yang dilaporkannya pada tahun 1963, telah mensimulasikan kemampuan evolusi untuk memainkan permainan sederhana, evolusi buatan menjadi metode optimisasi yang diakui secara luas sebagai suatu hasil pekerjaan dari Ingo Rechenberg dan Hans-Paul Schwefel pada tahun 1960 dan awal 1970 – kelompoknya dapat menyelesaikan masalah teknik yang rumit melalui strategi evolusi. Pendekatan lainnya adalah teknik pemrograman evolusioner dari Lawrence J. Fogel, yang dimaksudkan untuk menentukan kecerdasan buatan. Pemrograman evolusioner awalnya menggunakan mesin finite state untuk memperkirakan lingkungan, dan menggunakan variasi dan seleksi untuk mengoptimisasi predictive logics. Genetic Algorithm menjadi terkenal melalui karya John Holland pada awal 1970, dan bukunya Adaptation in Natural and Artificial System (1975). Karyanya awalnya ditujukan untuk pembelajaran cellular automata, yang dilakukan oleh Holland dan murid – muridnya pada University of Michigan. Holland memperkenalkan framework yang diformalisasikan untuk memperkirakan kualitas dari generasi selanjutnya, yang dikenal sebagai Holland’s Schema Theorem. Penelitian mengenai Genetic Algorithm sebagian besar hanya bersifat teori hingga pertengahan 1980, ketika Konferensi Internasional Pertama mengenai Algoritma Genetika diadakan di Pittsburgh, Pennsylvania.

Dengan meningkatnya ketertarikan akademis, perkembangan secara besar dalam kemampuan komputasi desktop memungkinkan untuk percobaan aplikasi dari teknik baru ini. Pada akhir 1980, General Electric mulai menjual produk pertama Genetic Algorithm di dunia, peralatan berbasis mainframe yang ditujukan untuk proses industri. Pada 1989, Axcels,Inc. meluncurkan Evolver, produk Genetic Algorithm kedua di dunia dan pertama untuk komputer desktop yang dituliskan oleh John Markoff , penulis mengenai teknologi untuk New York Times.

Definisi

Genetic Algortihm (GA) adalah sebuah teknik pencarian yang digunakan dalam komputasi untuk mencari solusi yang tepat atau hampir tepat untuk optimisasi dan masalah pencarian. Genetic algorithm dikategorikan sebagai pencarian global secara heuristic. Teknik ini merupakan kelas lain dari evolutionary algorithm (juga dikenal sebagai evolutionary computation) yang menggunakan teknik – teknik yang diinspirasikan oleh evolusi dalam biologi seperti penurunan sifat, mutasi, seleksi, cross over (disebut juga rekombinasi). Hal ini dilakukan dengan menciptakan sebuah populasi yang terdiri dari individu-individu yang setiap individunya merepresentasikan kromosom seperti yang terdapat pada DNA kita. Individu-individu pada populasi tersebut kemudian mengalami sebuah proses evolusi.

Genetic Algorithm diimplementasikan sebagai sebuah simulasi komputer dimana sebuah populasi dari representasi abstrak (disebut kromosom atau genotype atau genome) dari calon kandidat solusi ( disebut individu atau phenotypes) untuk sebuah optimisasi masalah yang berubah menjadi solusi yang lebih baik. Secara tradisional, solusi direpresentasikan dalam bentuk biner sebagai 0 atau 1, tetapi representasi lain juga dapat dilakukan. Evolusi biasanya dimulai dari populasi dari individu yang ditentukan secara acak dan terjadi di setiap generasi. Pada setiap generasi, kecocokan individu dalam populasi dievaluasi kembali, beberapa individu dipilih dari populasi mereka berdasarkan dari kecocokan mereka dengan fungsi fitness, dan diubah (direkombinasikan dan mungkin bermutasi secara acak) untuk membentuk suatu populasi baru. Populasi baru tersebut kemudian digunakan untuk iterasi selanjutnya dari algoritma. Biasanya, algoritma akan berhenti ketika jumlah maksimum dari generasi telah dihasilkan atau tingkat kecocokan yang telah ditentukan telah terpenuhi untuk populasi tersebut. Jika algoritma tersebut telah berhenti akibat jumlah maksimal dari generasi, sebuah solusi yang memuaskan mungkin belum tercapai.

Genetic algorithm dapat digunakan dalam bidang ilmu komputer, ekonomi, kimia, matematika fisika dan bidang – bidang lainnya.

Genetic algorithm membutuhkan dua hal untuk ditentukan yaitu sebuah representasi genetika dari wilayah solusi dan fitness function untuk mengevaluasi wilayah solusi.

Representasi standar dari solusi adalah sebuah kumpulan bilangan biner. Kumpulan dari tipe lain dan susunan lainnya dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini dapat digunakan adalah bagian dimana bagian – bagiannya dapat dengan mudah diatur akibat ukurannya yang tetap, yang memungkinkan operasi persilangan yang sederhana. Representasi dari panjang variabel mungkin juga dapat digunakan, tetapi penggunaan persilangan lebih rumit dalam hal ini. Representasi yang seperti pohon ditemukan dalam pemrograman genetik dan representasi seperti grafik ditemukan dalam pemrograman evolusioner.

Fitness function ditentukan berdasarkan representasi genetik dan menentukan kualitas dari solusi yang direpresentasikan. Fitness function adalah sebuah masalah yang tergantung pada hal lain. Sebagai contoh, dalam masalah knapsack dalam memaksimalkan nilai total dari obyek – obyek yang diletakkan dalam sebuah knapsack dengan kapasitas yang ditentukan. Representasi dari sebuah solusi mungkin berupa array of bits dimana setiap bit merepresentasikan objek yang berbeda dan nilai dari bit (0 atau 1) merepresentasikan apakah suatu obyek berada dalam knapsack atau tidak. Tidak setiap representasi berlaku karena ukuran dari obyek – obyek mungkin melebihi kapasitas dari knapsack. Kecocokan dari solusi merupakan jumlah nilai dari seluruh obyek dalam knapsack bila representasinya berlaku, atau jika 0 hal yang sebaliknya yang terjadi. Dalam beberapa masalah, terdapat kesulitan atau bahkan tidak mungkin untuk menentukan kecocokan; dalam hal ini genetic algorithm yang interaktif digunakan.

Ketika kita memiliki representasi genetik dari fitness function telah ditentukan, GA akan melanjutkan operasi selanjutnya yaitu menginisialisasi sebuah populasi dari solusi secara acak, kemudian mengembangkannya melalui aplikasi yang berulang – ulang dari operator mutasi, persilangan, pembalikan dan seleksi.

Pada tahap inisialisasi, awalnya beberapa individu solusi ditentukan secara acak untuk membentuk populasi awal. Ukuran populasi bergantung pada sifat dari masalah, tetapi biasanya berisi beberapa ratus atau beberapa ribu solusi yang memungkinkan. Secara tradisional, populasi ditentukan secara acak, dan mengandung seluruh daerah dari solusi yang memungkinkan (daerah pencarian). Biasanya, solusi – solusi mungkin tersebar di daerah dimana solusi yang optimal mungkin ditemukan.
Pada tahap seleksi, pada setiap generasi turunan, sebagian dari populasi yang ada dipilih untuk membuat generasi yang baru. Individu solusi dipilih melalui proses berdasarkan sebuah fitness, dimana solusi yang lebih cocok (seperti yang diukur oleh sebuah fitness function) lebih mungkin untuk dipilih. Metode pemilihan yang pasti memperkirakan kecocokan dari setiap solusi dan menentukan ke arah mana solusi yang paling baik berada. Metode lain hanya memperkirakan sebuah contoh acak dari populasi dan tentu saja proses ini mungkin memakan lebih banyak waktu. Sebagian besar fungsi dirancang dan dibuat sedemikian rpa sehingga sebagian kecil dari solusi yang kurang cocok terpilih. Ini membantuk untuk menyimpan penyimpangan dari populasi yang besar, menghindari konvergensi awal dari solusi yang kurang baik.

Langkah yang selanjutnya diambil adalah menentukan generasi kedua dari populasi solusi dari individu yang terpilih melalui operator genetik yaitu persilangan (yang juga disebut rekombinasi), dan / atau mutasi. Untuk setiap solusi yang baru yang dihasilkan, sepasang “induk” dari solusi dipilih untuk menghasilkan keturunan dari penampung yang telah dipilih sebelumnya. Dengan memproduksi keturunan solusi menggunakan metode – metode persilangan dan mutasi tersebut, solusi baru tercipta yang biasanya memiliki karakteristik dari induknya. Induk baru dipilih untuk setiap keturunan, dan proses tersebut berlanjut hingga sebuah populasi baru dari solusi dengan ukuran yang telah ditentukan tercipta. Proses ini menghasilkan kromosom dari generasi selanjutnya yang berbeda dengan generasi awal. Biasanya rata – rata fitness akan meningkat dengan prosedur ini untuk populasi, akibat hanya organime terbaik dari generasi pertama yang dipilih untuk peranakan, dan akibat digunakannya sebagian kecil dari solusi yang kurang cocok, untuk alasan - alasan yang telah disebutkan di atas.

Crossover

10001001110010010
01010001001000011

==>

10001001101000011
01010001010010010

Proses terjadinya crossover

Mutation

10001001110010010

==>

10001001110010011
Proses terjadinya mutasi (mutation)

Proses di atas diulangi secara terus menerus hingga kondisi untuk terminasi telah tercapai. Kondisi – kondisi yang berhenti biasanya antara lain sebuah solusi telah ditemukan yang memenuhi kriteria minimum yang telah ditentukan, jumlah generasi yang telah ditentukan telah tercapai, fitness untuk solusi dengan tingkatan tertinggi telah didapat atau telah didapat kondisi dimana iterasi selanjutnya tidak menghasilkan hasil yang lebih baik, pengamatan secara manual, atau kombinasi dari hal – hal yang telah disebutkan tersebut.

GA bekerja sesuai dengan langkah-langkah seperti di bawah ini:

1.    Tentukan jumlah individu (kromosom) dari sebuah populasi.
2.    Mengetes setiap kromosom tentang seberapa baik kromosom tersebut dalam menyelesaikan masalah yang sedang kita hadapi.
3.    Pilih dua kromosom dari populasi tersebut secara acak dengan Sesuai dengan crossover rate akan terdapat kemungkinan menggunakan metode roulette.
4.    terjadinya crossover pada sebuah titik yang acak.
5.    Sesuai dengan mutation rate akan terdapat kemungkinan terjadinya mutasi yang akan mengubah kode genetik dari sebuah kromosom.
6.    Ulangi tahap 2 sampai 5  hingga didapatkan kembali jumlah kromosom yang sesuai dengan populasi yang semula.
7.    Ulangi tahap 2 sampai 6 hingga tercapai solusi terbaik atau telah mencapai jumlah generasi yang telah ditentukan.

Evolutionary Programming dan Genetic Algorithm

Ada dua perbedaan utama antara EP dan GA:

Pertama  tidak ada batasan dalam representasi. Pendekatan umum GA terdiri dari mengubah solusi masalah menjadi sebuah rangkaian dari simbol representatif, Genome. Pada EP, representasinya mengikuti masalahnya. Sebuah jaringan saraf dapat direpresentasikan dengan cara yang sama dengan bagaimana jaringan tersebut bekerja, contohnya, karena operasi mutasi tidak membutuhkan perubahan (encoding) yang linear. (Dalam kasus ini, topologi yang tetap, weight yang bernilai riil dapat diubah langsung sebagai nilai riil-nya dan mutasi terjadi dengan mengubah vektor weight dengan menambahkan derau Gaussian dengan nilai rata-rata nol (zero mean Gaussian mutation). Untuk topologi yang berubah-ubah sering digunakan penembahan dan pengurangan terdistribusi Poisson).

Kedua, operasi mutasi mengubah aspek dari solusi sesuai dengan distribusi. Selanjutnya, skala mutasi sering kali berkurang seiring dengan tercapainya global optima.

ref : dari berbagai sumber

Popularity: 45% | December 21st, 2008 | Tags: Genetic Algorithm | Category: Algorithm | Subscribe to comments | Leave a comment | Trackback URL