Pemrograman genetika [ditutup]

Saya baru-baru ini menjelajah Reddit dan menemukan sebuah tulisan yang menghubungkan dengan contoh "algoritma genetik JavaScript". Saya benar-benar terpesona dengan konsep-konsep algoritma genetika dan pemrograman, namun bahkan setelah beberapa Googling saya masih dibiarkan sedikit bingung. Bagaimana cara kerjanya?

Saya kira istilah kosa kata membingungkan saya lebih dari apa pun. Saya akan menghargai contoh-contoh singkat dan mungkin penjelasan. Hanya konsep pemrograman genetika dan bagaimana saya bisa mengimplementasikannya dalam proyek saya dan mengapa?

Kedengarannya Anda berbicara tentang Algoritma Genetika lebih daripada Pemrograman Genetik, tapi inilah kontribusi saya untuk pemahaman Anda.

Mungkin berguna untuk memikirkan GAS dalam hal bagian-bagian yang terdiri dari mereka.

Jadi katakanlah Anda memiliki masalah. Hal pertama yang Anda butuhkan adalah cara mengekspresikan seperti apa solusi itu nantinya. Jika Anda memiliki masalah wiraniaga keliling dengan kota A, B, C, D, E maka Anda sudah tahu seperti apa solusi itu, sebuah deretan nama-nama kota [B, C, A, D, E].

Ini adalah Gene .

Atau dikenal sebagai solusi potensial untuk masalah tersebut. Seperti Steven A. Lowe menyebutkan, string bit adalah cara umum untuk menyandikan gen, tetapi itu tidak perlu; itu hanya membuat hal-hal tertentu lebih mudah. Bagian yang penting adalah bahwa Anda memiliki cara untuk mewakili solusi dengan cara seperti ini.

Sekarang. Bagaimana Anda tahu jika solusinya bagus? Anda memerlukan fungsi yang dapat memberi tahu Anda, dan menilai solusinya. Jadi, sekali lagi untuk di TSP Anda mungkin memiliki fungsi yang mengukur jarak yang ditempuh menggunakan jalur [B, C, A, D, E]. 'Nilai' yang Anda tetapkan bisa saja jarak yang ditempuh tetapi dalam masalah yang lebih rumit Anda bisa memasukkan hal-hal seperti biaya perjalanan dan hal-hal lain.

Ini adalah Fungsi Kebugaran .

Jadi sekarang Anda dapat mengambil solusi potensial dan mencari tahu apakah itu ada gunanya. Apa berikutnya?

Selanjutnya kita perlu memulai generasi pertama kita. Jadi kami menghasilkan banyak solusi acak. Tidak masalah apakah itu bagus atau tidak. Ini adalah populasi awal Anda, atau benih. Anda dapat menyebut ini kumpulan gen Anda.

Jadi, Anda mengambil kumpulan gen awal Anda dan menerapkan fungsi kebugaran Anda untuk mereka semua dan memberi mereka semua nilai. Sekarang Anda perlu mengambil dua dari mereka dan membuat populasi baru dari mereka - untuk generasi berikutnya. Siapa yang kamu pilih? Yah Anda tidak ingin hanya memilih yang paling cocok, yang dapat menyebabkan beberapa masalah. Alih-alih, Anda membutuhkan fungsi pemilihan .

Salah satu cara untuk memilih yang mudah divisualisasikan adalah menggunakan semacam roda: setiap gen adalah irisan pada roda, dan skor kebugaran mereka menunjukkan seberapa besar irisan mereka (semakin baik kebugaran, semakin besar irisan). Letakkan pin yang menunjuk ke roda dan putar (mis. Menghasilkan angka acak). Pin menunjuk ke induk pertama. Lakukan lagi untuk orang tua kedua.

Sekarang, Anda perlu membuat anak-anak baru. Anda ingin menggabungkan orang tua untuk menghasilkan populasi baru. Ada berbagai cara untuk melakukan ini, tetapi semuanya disebut fungsi crossover . Anda dapat membaginya menjadi dua dan menukar bagian di antara orang tua, atau melakukan semacam interleaving. Ini sangat analog dengan orang tua mamalia yang menghasilkan anak-anak baru -> mereka berdua menyumbangkan gen mereka kepada anak baru.

Setelah Anda memiliki generasi baru ini, Anda membuang mutasi acak, namun jarang , ke setiap anak. Saya sering melihat tingkat mutasi terjadi kurang dari 1%. Fungsi mutasi secara acak akan mengubah sesuatu dalam gen Anda yang dikodekan. Jika gen Anda adalah string sedikit, itu bisa bertukar sedikit, jika itu adalah array kota, itu bisa menukar 2 kota dalam daftar. Bagian yang penting adalah bahwa itu adalah kejadian yang relatif jarang dan mencampuradukkan semuanya.

Ulangi proses ini sampai sejumlah generasi yang diinginkan, atau hingga fungsi kebugaran Anda menghasilkan orang tua dengan skor kebugaran tinggi secara konsisten dan Anda memiliki solusi yang (semoga, jika Anda telah melakukan segalanya dengan benar) optimal.

Itu agak bertele-tele, jadi izinkan saya meringkas dengan metafora:

1. Gen adalah manusia: orang memecahkan masalah
2. Fungsi Kebugaran adalah nilai: Orang mendapat nilai berdasarkan seberapa baik mereka memecahkan masalah
3. Anda memilih 2 orang untuk membiakkan populasi baru: Anda memberi orang dengan nilai lebih baik peluang lebih besar untuk berkembang biak
4. Ketika orang tua berkembang biak, mereka bergabung untuk menghasilkan anak.
5. Anda jarang dan secara acak bermutasi anak-anak mereka
6. Anda menilai anak-anak dari populasi baru
7. Bilas dan ulangi

Semoga ini membantu.

menyandikan solusi untuk masalah sebagai bit-string

tulis fungsi (disebut fungsi "kebugaran") yang mengevaluasi seberapa 'baik' solusi yang dikodekan diberikan bit-string - hasilnya biasanya angka antara 0 dan 1

secara acak menghasilkan sekelompok bit-string ini dan mengevaluasi kebugarannya

pilih beberapa kelompok - biasanya yang lebih pas - dan potong menjadi dua dan tukar bagian menjadi beberapa bit-string baru (crossover)

lalu terkadang, balik beberapa bit secara acak ke dalam beberapa bit-string baru (mutasi)

ulangi sampai solusi yang baik berkembang

mengapa melakukan ini: beberapa masalah memiliki ruang solusi yang sangat besar, sangat besar sehingga mengevaluasi semua kemungkinan tidak praktis (cf Traveling Salesman Problem)

Saya sangat merekomendasikan buku Algoritma Genetika dalam Pencarian, Optimasi, dan Pembelajaran Mesin

Pemrograman genetika adalah cara agar komputer menulis program untuk Anda!

Jangan berpikir "program" seperti MS Word, pikirkan "program" sebagai berikut:

function(x){ return x*2; }

Fungsi (atau program) ini, dengan sendirinya, tidak memiliki alasan untuk ada. Kami mencari solusi untuk masalah. Jika Anda perlu mencari jumlah dua angka, Anda cukup membuka kalkulator dan melakukan perhitungan. Bagaimana jika seseorang memberi Anda tabel berikut dan meminta Anda untuk mencari tahu hubungan antara resultdan xdan y:

x   y   result
99  1   (3.02)
79  88   2.01 
21  62   5.01 
84  52  (6.58)
12  70   5.54 
67  18   0.73 

Data ini adalah data "pelatihan" Anda. Komputer Anda akan menggunakan data ini untuk menghasilkan beberapa hipotesis, maka Anda akan mengujinya terhadap data aktual.

Katakanlah Anda tidak tahu statistik dan memutuskan masalah ini terlalu sulit untuk dipecahkan sendiri, sehingga Anda akan mendapatkan komputer untuk mengetahuinya untuk Anda.

Apakah komputer secara acak menghasilkan tebakan liar

Anda memiliki komputer yang menghasilkan jutaan jawaban, dan lihat apakah ada di antara mereka (coba tebak ... satu juta kali!). Berikut ini adalah contoh dari beberapa tebakan:

function(x,y){ return x+y; } // wrong
function(x,y){ return x/1*1*1*1*1*1+y; } //wrong, silly

Anda mungkin atau mungkin tidak tahu ini, tetapi fungsi atau program juga dapat direpresentasikan sebagai pohon, misalnya, fungsi kedua adalah:

(+ (/ x (* 1 (* 1 (* 1 (* 1 (* 1 1)))) y)

Anda dapat membuatnya lebih seperti pohon dengan membuat indentasi seperti itu (btw, cari notasi semir terbalik dan sintaksis lisp ... tetapi Anda akan mengerti mengapa kami mewakili program seperti ini segera):

(+ 
    (/ x 
        (* 1 
            (* 1 
                (* 1 
                    (* 1 
                        (* 1 1)))) 
    y)

( +berada di atas dengan dua "daun" dari /dan y. /sendiri memiliki beberapa anak, dll.)

Inilah sebabnya mengapa Anda banyak membaca tentang "pohon" dalam pemrograman genetika. Dalam kasus apa pun, kami memasukkan nilai-nilai xdan yke dalam fungsi ini dan itu memberi kami jawaban yang SALAH. Tidak mengherankan karena kami membuat ini secara acak.

Anda sekarang memutuskan untuk menghasilkan sejuta solusi semacam itu. Semuanya salah. Namun, Anda memperhatikan bahwa beberapa jawaban lebih dekat dengan jawaban yang benar daripada yang lain. Dengan kata lain, beberapa solusi lebih "cocok" daripada yang lain. Perhatikan bahwa komputer tidak tahu apa yang "benar" dan "salah" sehingga Anda harus menyediakan "fungsi kebugaran" Anda sendiri. Fungsi ini diberikan solusi potensial, data pelatihan, dan bertanggung jawab untuk memberi tahu sistem GP seberapa "pas" solusi ini. Seperti yang dapat Anda bayangkan, fungsi ini dijalankan jutaan kali.

Apa yang membuat GP berbeda

Inilah yang membuat pemrograman genetika berbeda dari tebakan liar. Anda memutuskan untuk melakukan satu lagi putaran tebakan; Namun, Anda melakukannya dengan lebih cerdas. Anda mengambil 10% tebakan teratas (tebakan yang mendekati nilai sebenarnya) dan menjadikannya bagian dari generasi kedua. Anda juga mengambil banyak dari solusi ini (mungkin 10% sama ... saya tidak ingat) dan memutuskan untuk "mencampurnya."

Anda secara acak memilih dua solusi, secara acak memilih sub-pohon dan mulai menukarnya. Jadi bagian dari solusi A berakhir di bawah solusi B dan sebaliknya - Anda baru saja "melewati" mereka. Anda juga mengambil beberapa solusi dan hanya "memutasikan" mereka ... mengambil subtree dan 'mengacaukannya' sedikit (hei, jika solusinya mengerikan, 'mengacaukannya tanpa alasan' mungkin benar-benar memperbaikinya).

Cara berpikir yang baik untuk hal ini adalah sebagai berikut: ibu dan ayah Anda memiliki atribut tertentu - warna rambut, tinggi, kemungkinan penyakit, dll. Anda, sebagai seorang anak mewarisi atribut yang berbeda dari kedua orang tua Anda. Jika kedua orang tua Anda adalah atlet olimpiade, Anda juga akan menjadi atlet super, bukan? Nah, ahli biologi, sosiolog, dan bahkan sejarawan mungkin mempermasalahkan gagasan ini, tetapi ilmuwan komputer tidak peduli dengan moralitas eugenika di sini. Mereka hanya melihat "sistem" melakukan pekerjaan yang cukup baik memberikan solusi, jadi mereka memutuskan untuk memodelkannya dalam perangkat lunak.

Jika itu tidak benar-benar cocok dengan biologi, tetapi masih memberikan jawaban yang baik ... banyak ilmuwan komputer secara kolektif mengatakan "apa pun Bung, dan terima kasih untuk terminologinya." Juga perhatikan bahwa semua saudara dan saudari Anda dan TIDAK PERSIS sama ... bahkan melalui mereka memiliki orang tua yang sama. Setiap orang memiliki gen yang bermutasi karena alasan apa pun (tolong jangan perlihatkan ini kepada seorang ahli biologi, intinya adalah untuk memahami motivasi di balik banyak terminologi).

Jadi sekarang kita mendapatkan komputer untuk menghasilkan jutaan program dan mengukur kebugaran mereka. Solusi terbaik bertahan ke generasi berikutnya. Kami juga "bermutasi" dan melakukan cross-over pada "populasi" (perhatikan bagaimana bahasa genetika dan biologi digunakan). Setelah generasi kedua diciptakan, kebugaran diukur kembali. Karena generasi ini memiliki solusi terbaik dari generasi sebelumnya DAN kami menyeberang dan bermutasi solusi terbaik (bersama dengan populasi biasa-biasa saja - untuk menjaga keragaman), generasi ini harus setidaknya sedikit lebih baik daripada generasi sebelumnya.

Kami melanjutkan ini untuk sejumlah generasi yang sangat besar. Setiap generasi (semoga) memberikan solusi yang lebih baik dan lebih baik, sampai kami mendapatkan jawaban yang tepat. Sebagai contoh:

(+ (- 2.2 (/ x 11) (* 7 (cos y))))

Nah lihat ini, ini benar!
(Saya menyalin ini dari http://en.wikipedia.org/wiki/Genetic_programming , yang juga memiliki representasi grafis dari pohon ini)

Barang sisa

Ada beberapa masalah penting, seperti bagaimana Anda memutuskan "terminal" ( +, -, *, /, cos, sin, tan) yang tersedia untuk sistem GP Anda, bagaimana Anda menulis fungsi kebugaran dan bagaimana sistem menangani program-program yang tidak masuk akal seperti (1 + cos)atau (2 / "hello")(di antara banyak lainnya).

Sangat membosankan untuk mengembangkan persamaan. Semakin menarik jika set terminal Anda terlihat seperti berikut: (api, akal sehat, bergerak, ...) dan fungsi kebugaran Anda mengukur kesehatan Anda dan jumlah mayat monster bela diri.

Saya menulis sebagian besar ini dari memori tetapi ini adalah ide dasar. Saya melakukan beberapa GP di masa kuliah saya. Anda harus bermain-main dengannya. Jangan khawatir tentang memahami semua terminologi, cukup unduh beberapa sistem GP gratis, jalankan melalui beberapa contoh untuk merasakan dan membuat contoh menarik Anda sendiri (menemukan hubungan antara set data yang berbeda, mencoba menghubungkannya ke permainan API, dll.)

Survival of the Fittest: Seleksi Alam dengan Bentuk Windows adalah bagaimana saya diperkenalkan dengan Pemrograman Genetik. Ini mudah dibaca dengan kode yang tersedia untuk diunduh. Kelemahannya adalah bahwa GP membutuhkan sarana untuk mengeksekusi kode yang dibuat pada saat runtime, dan pada saat artikel itu ditulis, C # tidak cocok untuk tugas ini. Itulah sebabnya contoh ini menggunakan CodeDOM untuk menghasilkan, mengkompilasi dan menjalankan kode pada saat run-time, yang dengan sendirinya menambahkan lapisan kompleksitas lain ke dalamnya.

Hal-hal telah berubah sejak saat itu. NET sekarang memiliki ExpressionTree API-nya sendiri, yang mungkin akan memungkinkan implementasi GP yang lebih elegan di C # daripada yang dijelaskan dalam artikel. Tapi itu cukup baik untuk mendapatkan pemahaman tentang cara kerja dokter umum.

Di sini Anda dapat mengunduh ebook gratis di GP, yang juga menyertakan contoh kode java yang sangat singkat yang mungkin juga Anda temukan menarik.

Algoritma genetika dan pemrograman genetika saling terkait, tetapi berbeda konsep.

Algoritma genetika (GAs) adalah algoritma pencarian untuk masalah optimisasi yang kompleks. Dalam GA, Anda menyandikan parameter solusi untuk beberapa masalah dalam bitstring "DNA", lalu secara acak "membiakkan" bitstring ini: minta mereka mereproduksi dengan menggabungkan bagian-bagiannya dan menerapkan "survival of the fittest" dengan menghapus semua bitstring Anda punya kecuali yang terbaik dalam memecahkan masalah Anda.

Pemrograman genetika (GP) bahkan lebih rumit: di sini, Anda tidak mewakili program dengan DNA mereka (bitstring), tetapi oleh pohon parsing yang Anda biakkan dan pilih.