Evolutionary Algorithm

Evolutionary Algorithm (Algoritma Evolusioner)

Sejarah dan Ikhtisar

Dalam kecerdasan buatan, algoritma evolusioner (EA) adalah bagian dari komputasi evolusioner, algoritma optimasi metaheuristik berbasis populasi generik. EA menggunakan mekanisme terinspirasi oleh evolusi biologis, seperti reproduksi, mutasi, rekombinasi, dan seleksi. Solusi calon untuk masalah optimasi memainkan peran individu dalam suatu populasi, dan fungsi fitness menentukan lingkungan dimana solusi "hidup" (lihat juga fungsi biaya). Evolusi penduduk kemudian terjadi setelah aplikasi berulang dari operator di atas. Buatan evolusi (AE) menggambarkan proses yang melibatkan algoritma evolusioner individu, EA merupakan komponen individu yang berpartisipasi dalam AE.

Algoritma evolusioner sering melakukan solusi baik yang mendekati semua jenis masalah karena mereka idealnya tidak membuat asumsi tentang lanskap kebugaran mendasari; umum ini ditunjukkan oleh keberhasilan dalam bidang beragam seperti teknik, seni, biologi, ekonomi, pemasaran, genetika, operasi penelitian, robotika, ilmu sosial, fisika, politik dan kimia. Teknik dari algoritma evolusioner diterapkan pada model evolusi biologis umumnya terbatas pada eksplorasi proses evolusi mikro. Komputer simulasi Tierra dan Avida upaya untuk memodelkan dinamika macroevolutionary. Dalam aplikasi yang paling nyata dari EA, kompleksitas komputasi merupakan faktor melarang. Bahkan, kompleksitas komputasi ini adalah karena evaluasi fungsi fitness. Kebugaran pendekatan adalah salah satu solusi untuk mengatasi kesulitan ini. Namun, EA tampaknya sederhana dapat memecahkan masalah sering kompleks, sehingga mungkin tidak ada hubungan langsung antara kompleksitas algoritma dan kompleksitas masalah.

           
Sebuah kemungkinan pembatasan banyak algoritma evolusioner adalah kurangnya yang jelas perbedaan genotipe-fenotip. Di alam, yang dibuahi sel telur mengalami proses yang kompleks yang dikenal sebagai embriogenesis menjadi fenotipe matang. Ini encoding tidak langsung diyakini membuat pencarian genetik lebih kuat (yaitu mengurangi kemungkinan mutasi fatal), dan juga dapat meningkatkan evolvability organisme tidak langsung (alias generatif atau perkembangan) pengkodean tersebut. Juga memungkinkan evolusi untuk mengeksploitasi keteraturan dalam lingkungan. Penelitian terbaru di bidang embryogeny buatan, atau sistem perkembangan buatan, berusaha untuk mengatasi masalah ini. Dan gen pemrograman ekspresi berhasil mengeksplorasi sistem genotipe-fenotip, di mana genotipe terdiri dari kromosom multigenic linear panjang tetap dan fenotipe terdiri dari beberapa pohon ekspresi atau program komputer ukuran dan bentuk yang berbeda.

Pelaksanaan Proses Biologi

Dalam hal melakukan pelaksanaan proses biologinya, algoritma evolusioner dibagi - bagi menjadi beberapa tahapan, diantaranya adalah sebagai berikut :

1.      Menghasilkan populasi awal individu secara acak - Generasi pertama

2.      Mengevaluasi kebugaran masing-masing individu dalam populasi yang 
3.      Ulangi pada generasi ini sampai terminasi (batas waktu, cukup kebugaran dicapai, dll):

            1.Pilih individu terbaik cocok untuk reproduksi - orang tua

       2.Berkembang biak individu baru melalui crossover dan mutasi operasi untuk melahirkan  keturunan

            3.Mengevaluasi kebugaran individu individu baru

            4.Ganti populasi paling-fit dengan individu baru

Teknik Algoritma Evolusioner

            Teknik yang mirip berbeda dalam rincian pelaksanaan dan sifat dari masalah diterapkan tertentu.

• Algoritma genetika - ini adalah jenis yang paling populer dari EA. Satu mencari solusi dari masalah dalam bentuk string nomor (tradisional biner, meskipun representasi terbaik biasanya yang mencerminkan sesuatu tentang masalah yang dipecahkan), dengan menerapkan operator seperti rekombinasi dan mutasi (kadang-kadang satu, kadang-kadang keduanya) . Jenis EA sering digunakan dalam masalah optimasi.

• Pemrograman genetik - Berikut solusi dalam bentuk program komputer, dan kebugaran mereka ditentukan oleh kemampuan mereka untuk memecahkan masalah komputasi.

• Evolusi pemrograman - Serupa dengan pemrograman genetik, tetapi struktur dari program ini adalah tetap dan parameter numerik yang diizinkan untuk berkembang.

• Gene pemrograman ekspresi - Seperti pemrograman genetik, PMP juga berkembang program komputer tetapi mengeksplorasi sistem genotipe-fenotip, di mana program komputer dengan ukuran yang berbeda dikodekan dalam kromosom linear panjang tetap.

• Strategi Evolusi - Bekerja dengan vektor bilangan real sebagai representasi dari solusi, dan biasanya menggunakan tingkat mutasi diri adaptif.

• Algoritma memetic - Ini adalah bentuk hibrida metode berbasis populasi. Terinspirasi oleh kedua prinsip-prinsip evolusi Darwin alam dan gagasan Dawkins meme yang dipandang sebagai bentuk algoritma berbasis populasi ditambah dengan prosedur pembelajaran individu mampu melakukan perbaikan lokal. Fokus dari penelitian demikian untuk menyeimbangkan telah eksplorasi dan eksploitasi dalam pencarian.

• Evolusi Diferensial - Berdasarkan perbedaan vektor dan karena itu terutama cocok untuk masalah optimasi numerik.

• Neuroevolution - Mirip dengan pemrograman genetik tetapi genom merupakan jaringan syaraf tiruan dengan menggambarkan struktur dan koneksi bobot. Pengkodean genom dapat langsung atau tidak langsung.

Teknik Terkait atau Teknik yang memiliki kemiripan dalam Implementasinya

• Algoritma Swarm, termasuk :

1.Ant koloni optimasi - Berdasarkan gagasan semut mencari makan dengan komunikasi feromon untuk membentuk jalur. Terutama cocok untuk optimasi kombinatorial dan masalah grafik.

2.Algoritma lebah didasarkan pada perilaku mencari makan lebah madu. Telah diterapkan di banyak aplikasi seperti routing dan penjadwalan.

3.Pencarian Cuckoo terinspirasi oleh parasitisme merenung dari spesies cuckoo. Ia juga menggunakan penerbangan Retribusi, sehingga cocok untuk masalah optimasi global.

4.Partikel swarm optimasi - Berdasarkan gagasan hewan berkelompok perilaku. Juga terutama cocok untuk masalah optimasi numerik.

• Metode metaheuristik berbasis populasi lainnya :

1.Algoritma Firefly terinspirasi oleh perilaku kunang-kunang, menarik satu sama lain dengan lampu berkedip. Hal ini sangat berguna untuk optimasi multimodal.

2.Harmony search - Berdasarkan gagasan perilaku musisi dalam mencari harmoni yang lebih baik. Algoritma ini cocok untuk optimasi kombinatorial serta optimasi parameter.

3.Gaussian adaptasi - Berdasarkan teori informasi. Digunakan untuk memaksimalkan hasil manufaktur, berarti kebugaran atau informasi rata-rata. Lihat misalnya Entropi dalam termodinamika dan teori informasi.

Sumber :

1. G.S. Hornby and J.B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8(3):223–246, 2002.
2. Ferreira, C., 2001. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems. Complex Systems, Vol. 13, issue 2: 87-129.