Menjelajahi Kekuatan dan Batasan Algoritma Genetika

Pada titik ini dalam serangkaian pemrograman genetik (GP), kita telah mempelajari apa itu pemrograman genetik dan bagaimana ia mewakili informasi, bagaimana operator genetik bekerja dalam algoritma evolutif, dan bekerja melalui pengembangan program pengurutan melalui regresi simbolik.

Di sini, kita akan melihat tingkat tinggi apa yang dapat dicapai teknologi ini seiring berkembangnya.

Pertimbangan Praktis Pemrograman Genetik

Untuk memahami bab akhir dari seri ini, mari kita ingat contoh XOR yang kita bahas di bagian pertama seri ini:

Solusi sempurna untuk masalah XOR yang ditemukan oleh GP:
(defun program ()
  (AND (OR X1 X2)
 (NOT (AND X1 X2) )
 )
)

Listing 1. Hasil XOR.

Mari kita juga lihat kembali contoh regresi simbolik dari artikel sebelumnya:

Aproksimasi polinomial untuk sin(x) dalam interval (0 <= x <= pi/2)

(defun program ()
 (+ (* (* (* X X) X)
 (* 0.2283 -0.6535))
 X)
)

Menyederhanakan program di atas menghasilkan persamaan setara berikut:

polysin(x) = -.1492 x3 + x

Hasil:

Listing 4. Regresi simbolik.

Perhatikan bahwa baik contoh XOR maupun regresi simbolik yang disajikan di sini mengembalikan satu nilai saat dievaluasi.

Karakteristik ini tidak perlu menjadi batasan karena tentu mungkin untuk suatu fungsi atau terminal untuk memiliki efek samping saat dieksekusi. Ini sering terjadi untuk program pengurutan, yang berisi fungsi dengan potensi efek samping menukar pasangan elemen dalam vektor. Dalam praktiknya, umum bagi efek samping untuk hadir. Beberapa contoh tambahan efek samping yang berguna adalah menetapkan satu variabel ke variabel lain atau mengubah arah robot menghadap.

Kumpulan fungsi kami dapat mencakup fungsi bersyarat yang memberikan program yang berevolusi kemampuan untuk membuat keputusan. Fungsi bersyarat secara selektif mengevaluasi argumen mereka. Sebagai contoh, pertimbangkan fungsi, dengan arity tiga, seperti (if arg1 arg2 arg3). Fungsi dievaluasi dengan mengevaluasi argumen pertama dan jika hasilnya benar, argumen kedua dievaluasi; jika tidak, argumen ketiga dievaluasi. Konstruksi iteratif juga mungkin, karena suatu fungsi dapat mengevaluasi salah satu argumen mereka beberapa kali. Kompleksitas tambahan diperkenalkan, namun, oleh kebutihan untuk membatasi jumlah iterasi dan tingkat bersarang sehingga menghindari situasi di mana evaluasi individu dapat memakan waktu yang berlebihan. Beberapa pekerjaan telah dilakukan untuk memungkinkan formulasi rekursif, meskipun keberhasilan di area ini terbilang terbatas.

Meskipun hasil sistem GP cenderung menjadi program seperti LISP, sistem GP tidak perlu diimplementasikan dalam LISP. Banyak sistem diimplementasikan dalam C atau C++. Representasi linearisasi dari pohon program dapat digunakan dan biaya overhead memori dinamis bersama dengan pengumpulan sampah yang mahal dapat dihindari. Efisiensi fungsi kebugaran layak mendapat perhatian khusus karena sering menjadi hambatan karena jumlah besar kali ia dipanggil selama setiap generasi. Sebuah makalah yang bagus yang membahas berbagai teknik implementasi dapat ditemukan di Advances in Genetic Programming (dikutip di bagian Bacaan Disarankan di bawah ini).

Seperti dalam paradigma pembelajaran mesin lain, seperti jaringan saraf, potensi untuk overfit pada data pelatihan (kasus uji GP) ada. Overfitting dapat terjadi ketika solusi secara efektif “menghafal” data, sehingga memberikan lebih sedikit dari tabel pencarian yang rumit. Cara sederhana untuk membantu menahan efek ini adalah melalui penggunaan faktor kesederhanaan. Faktor kesederhanaan biasanya merupakan pecahan kecil yang dikalikan dengan jumlah simpul dalam pohon program, hasilnya diintegrasikan ke dalam fungsi kebugaran. Ideanya adalah memberikan hadiah pada solusi yang lebih kecil, yang presumed lebih umum. Selain itu, Anda didorong untuk menggunakan teknik desain eksperimen yang tepat. Misalnya, jika Anda mencoba mengembangkan model untuk prediksi, ide bagus untuk membatasi evaluasi kebugaran pada subset data yang tersedia. Dengan cara ini, data yang tersisa dapat mengukur kinerja prediktif model yang dihasilkan.

Seperti yang terjadi dengan algoritma evolutif, GP tidak memberikan jaminan untuk menemukan solusi yang tepat atau bahkan solusi yang dapat diterima. Hasil dapat bervariasi sangat dari satu run ke run lain. Seringkali, proses secara premature konvergen pada minimum lokal. Kinerja sangat tergantung pada kompleksitas masalah, representasinya yang ditentukan oleh pilihan fungsi dan terminal, dan properti fungsi kebugaran.

Aplikasi untuk Pemrograman Genetik

Pemrograman genetik telah berhasil diterapkan untuk masalah yang muncul di area seperti:

• Desain rangkaian
• Optimasi kombinatorial
• Sistem kontrol
• Pemasangan kurva/analisis regresi
• Kompresi data
• Peringkatan keuangan/pelagangan keuangan
• Pengakuan strategi permainan
• Induksi urutan matematika
• Desain jaringan saraf
• Pengenalan pola dan klasifikasi
• Pembangkitan angka acak
• Navigasi robot
• Integrasi dan diferensiasi simbolik
• Desain tiga dimensi

Arah Masa Depan untuk Pemrograman Genetik

Bergantung pada kompleksitas masalah, beberapa run GP mungkin diperlukan untuk menemukan solusi yang dapat diterima, jika ada yang dapat ditemukan. Secara ideal, kita ingin GP “skala up” seiring bertambahnya kompleksitas masalah. Menemukan cara yang baik untuk mencapai tujuan ini adalah area penelitian yang aktif. Seperti dalam pemrograman konvensional, gagasan membangun representasi tingkat yang lebih tinggi melalui subrutin adalah satu cara untuk mendekati masalah ini. Di Genetic Programming II, Koza membahas metode yang dapat menemukan subrutin yang dapat digunakan kembali dan menyajikan hasil yang mendukung kemampuan program hierarkis, modular untuk menyelesaikan masalah yang lebih kompleks.

Seperti yang kita lihat, GP menggabungkan karakteristik swa-organisasi algoritma genetika dengan kekuatan representasi dan generalisasi S-expression. Keanggunan pendekatan ini menyederhanakan spesifikasi masalah menjadi menyediakan fungsi kebugaran spesifik domain dan kumpulan fungsi serta terminal yang tepat. Berlaku untuk berbagai masalah yang beragam, GP terus menjadi tanah subur untuk penelitian.

Masih dalam tahap awal, breakthrough di masa depan mungkin membawa kita satu langkah lebih dekat ke Graal Suci dari sistem yang mampu menulis program mereka sendiri.

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.