Pengantar Pemrograman Genetik:Sistem yang Memprogram Itu Sendiri?
Mungkin "Cawan Suci" ilmu komputer akan ditemukan pada hari mesin kita dapat menulis programnya sendiri. Pemrograman genetik (GP) adalah paradigma pembelajaran mesin yang relatif baru yang mewakili langkah ke arah itu.
GP memegang banyak janji di bidang teknik kontrol. Dalam artikel ini, kita akan membahas apa itu pemrograman genetik, bagaimana hal itu dapat direpresentasikan, dan melihat contoh programnya.
Artikel ini adalah yang pertama dalam seri. Untuk melompat ke entri berikutnya, pilih salah satu di bawah ini:
- Operator Genetika dalam Algoritma Evolusi
- Contoh Algoritma Genetika:Mengembangkan Program Penyortiran dan Regresi Simbolik
- Aplikasi dan Keterbatasan Pemrograman Genetik
Pemrograman Genetika dan Algoritma Genetika
GP pada dasarnya adalah variasi dari algoritma genetika (GA) yang awalnya disusun oleh John Holland. Seperti GA, GP adalah algoritme evolusioner yang mengandalkan operator genetik seperti reproduksi proporsional kebugaran, persilangan, dan mutasi untuk mendorong populasi program yang disandikan, atau "individu", melalui generasi berturut-turut menuju solusi.
Namun, tidak seperti GA, yang biasanya menggunakan pengkodean string bit dengan panjang tetap, GP menggunakan representasi berbasis pohon ukuran variabel dari program aktual. Oleh karena itu, hasil dari GP run yang sukses menghasilkan program komputer yang, ketika diberikan input yang sesuai dan dijalankan, menghasilkan hasil yang diinginkan.
Nichael Cramer dan John Koza dikreditkan untuk meletakkan dasar-dasar GP. John Koza (yang juga memegang paten pada GP) telah melakukan banyak penelitian tentang GP dan bukunya yang terkenal, "Genetic Programming," dianggap sebagai karya mani tentang subjek tersebut. Penelitian saat ini telah menunjukkan beberapa keberhasilan yang menggembirakan dari GP dalam berbagai aplikasi, termasuk navigasi robot, akuisisi strategi permainan, analisis regresi simbolik, dan sistem kontrol.
Representasi Pemrograman Genetika
Representasi berbasis pohon yang disebutkan sebelumnya adalah inti dari tema GP karena hampir semua program komputer dapat direpresentasikan dengan cara ini. Dalam praktiknya, bahasa fungsional seperti LISP sangat cocok untuk bentuk ini dan mudah untuk melihat bagaimana ekspresi-S LISP dapat digambarkan sebagai pohon (Gambar 1).
Di bawah, Anda akan menemukan tiga representasi terpisah dari informasi yang sama:
Sebuah fragmen program sederhana: MULAI JIKA a Setara dengan LISP: (prog (jika (a
Gambar 1. Representasi pohon dari sebuah program. Perhatikan bahwa (progn arg1 arg2 arg3 ... argn) mengevaluasi setiap argumen secara berurutan.
Node interior pohon terdiri dari fungsi sedangkan node daun terdiri dari terminal. Fungsi harus memiliki jumlah argumen (biasanya disebut sebagai arity) setidaknya satu, yang memungkinkan mereka terhubung ke fungsi atau terminal lain, sehingga memberikan "lem" untuk cabang di dalam pohon.
Terminal biasanya mencakup hal-hal seperti konstanta dan variabel. Sejak terminal membentuk daun pohon, mereka selalu memiliki aritas nol. Anda diminta untuk memilih rangkaian fungsi dan terminal untuk masalah yang Anda coba pecahkan. Misalnya, fungsi logika AND, OR, dan NOT dan terminal X1 dan X2, yang mewakili dua variabel input boolean, sesuai jika Anda mencoba menemukan program yang mampu mensintesis fungsi boolean XOR. Fungsi kebugaran juga diperlukan karena Anda harus menyediakan cara untuk mengukur satu program terhadap program lain dalam arti bahwa program tersebut lebih baik dalam memecahkan masalah yang diberikan.
Sebagai contoh, dalam kasus XOR, kita dapat menguji kebugaran suatu program dengan mengeksekusi program sekali untuk setiap kasus kebugaran yang sesuai dengan empat kemungkinan input boolean untuk X1 dan X2 (0 0, 0 1, 1 0, 1 1) dan menjumlahkan jumlah tanggapan yang benar (0, 1, 1, 0) masing-masing, untuk setiap kasus uji.
Jelas, program yang menghasilkan skor sempurna empat dianggap sebagai solusi untuk masalah XOR, seperti yang ditunjukkan pada Daftar 1.
Solusi sempurna untuk masalah XOR yang ditemukan oleh GP: (program mati () (DAN (ATAU X1 X2) (TIDAK (DAN X1 X2) ) ) )
Daftar 1. Hasil XOR
Selanjutnya:Operator Genetika
Pada artikel berikutnya, kita akan melihat operator genetika yang memungkinkan algoritme evolusioner. Kami juga akan menggunakannya dalam contoh algoritme yang lebih kompleks.
Bacaan yang Disarankan
- Kinnear, Jr., K.E. (ed.). Kemajuan dalam Pemrograman Genetik . Cambridge, Mass.:The MIT Press, 1994.
- Knuth, D.E. Seni Pemrograman Komputer, Volume 3, Menyortir dan Mencari . Bacaan, Misa.:Addison-Wesley, 1973
- Koza, J.R. Pemrograman Genetika . Cambridge, Mass.:The MIT Press, 1992.
- Koza, J.R. Pemrograman Genetika II . Cambridge, Mass.:The MIT Press, 1994.
- Montana, D.J. “Pemrograman Genetik yang Sangat Diketik.” Laporan Teknis BBN #7866, Mei 1993.
- Mitchell, Melanie, Pengantar Algoritma Genetika , The MIT Press, 1998.
