Pemrograman Genetika Dijelaskan: Bagaimana Mesin Belajar Menulis Kode Sendiri
Mungkin “Graal Suci” dari ilmu komputer akan ditemukan hari mesin kita dapat menulis program mereka sendiri. Pemrograman genetika (GP) adalah paradigma pembelajaran mesin yang relatif baru yang mewakili langkah ke arah tersebut.
GP menjanjikan banyak hal dalam bidang rekayasa kontrol. Dalam artikel ini, kita akan membahas apa itu pemrograman genetika, bagaimana ia dapat direpresentasikan, dan melihat contoh program.
Artikel ini adalah bagian pertama dalam sebuah seri. Untuk melompat ke entri berikutnya, pilih salah satu di bawah ini:
- Operator Genetik dalam Algoritma Evolutif
- Contoh Algoritma Genetika: Mengembangkan Program Pengurutan dan Regresi Simbolik
- Aplikasi dan Keterbatasan Pemrograman Genetik
Pemrograman Genetik dan Algoritma Genetika
GP pada dasarnya adalah variasi dari algoritma genetika (GA) yang awalnya dikonsep oleh John Holland. Seperti GA, GP adalah algoritma evolutif yang mengandalkan operator genetik seperti reproduksi proporsi kebugaran, crossover, dan mutasi untuk mendorong populasi program terenkode, atau “individu,” melalui generasi berturut-turut menuju solusi.
Namun, tidak seperti GA, yang biasanya menggunakan encoding bit string dengan panjang tetap, GP menggunakan representasi pohon berukuran variabel dari program aktual. Oleh karena itu, hasil dari run GP yang berhasil menghasilkan program komputer yang, saat diberikan input yang tepat dan dieksekusi, menghasilkan hasil yang diinginkan.
Nichael Cramer dan John Koza dihargai karena mendasari fondasi GP. John Koza (yang juga memiliki paten pada GP) telah melakukan banyak penelitian pada GP dan bukunya yang terkenal, “Genetic Programming,” dianggap sebagai karya seminal pada subjek ini. Penelitian saat ini telah menunjukkan beberapa keberhasilan yang mengajakan dari GP dalam berbagai aplikasi, termasuk navigasi robot, pengakuan strategi permainan, analisis regresi simbolik, dan sistem kontrol.
Representasi Pemrograman Genetik
Representasi pohon yang disebutkan sebelumnya adalah inti dari tema GP karena virtualnya setiap program komputer dapat direpresentasikan dengan cara ini. Dalam praktiknya, bahasa fungsional seperti LISP cocok untuk bentuk ini dan mudah untuk melihat bagaimana S-expression LISP dapat divisualisasikan sebagai pohon (Gambar 1).
Di bawah, Anda akan menemukan tiga representasi terpisah dari informasi yang sama:
Suatu potongan program sederhana:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END
LISP equivalent:
(progn (if (a < b)
(setq a (+ a 1))
(setq b (* b b))
)
(setq c (* (* a b) 2))
)
Gambar 1. Representasi pohon dari program. Perhatikan bahwa (progn arg1 arg2 arg3 ... argn) mengevaluasi setiap argumen secara berurutan.
Node interior pohon terdiri dari fungsi sementara node daun terdiri dari terminal. Fungsi harus memiliki jumlah argumen (sering disebut arity) paling sedikit satu, yang memungkinkan mereka terhubung ke fungsi atau terminal lainnya, sehingga menyediakan “penghangat” untuk cabang dalam pohon.
Terminal biasanya mencakup hal-hal seperti konstanta dan variabel. Karena terminal membentuk daun pohon, mereka selalu memiliki arity nol. Anda diwajibkan untuk memilih himpunan fungsi dan terminal untuk masalah yang Anda coba selesaikan. 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 memfungsikan fungsi boolean XOR. Fungsi kebugaran juga diperlukan karena Anda harus menyediakan cara untuk satu program diukur terhadap yang lain dalam arti bahwa satu lebih baik dalam menyelesaikan masalah tertentu.
Misalnya, dalam kasus XOR, kita dapat menguji kebugaran program dengan menjalankan program sekali untuk setiap kasus kebugaran yang sesuai dengan empat input boolean yang mungkin untuk X1 dan X2 (0 0, 0 1, 1 0, 1 1) dan menambahkan jumlah respons yang benar (0, 1, 1, 0) masing-masing, untuk setiap kasus uji.
Tentu, program yang menghasilkan skor sempurna empat dianggap sebagai solusi untuk masalah XOR, seperti ditunjukkan dalam Listing 1.
Suatu solusi sempurna untuk masalah XOR yang ditemukan oleh GP:
(defun program ()
(AND (OR X1 X2)
(NOT (AND X1 X2) )
)
)
Listing 1. Hasil XOR
Selanjutnya: Operator Genetik
Dalam artikel berikutnya, kita akan melihat operator genetik yang membuat algoritma evolutif mungkin. Kita juga akan menggunakannya dalam contoh algoritma yang lebih kompleks.
Bacaan Disarankan
- Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
- Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
- Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
- Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
- Montana, D. J. “Strongly Typed Genetic Programming.” BBN Technical Report #7866, May 1993.
- Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.
