Pemrograman Genetika

6. Pemrograman Genetika




6.1 Pengenalan Pemrograman Genetika
Salah satu tantangan utama ilmu komputer adalah untuk menjadikan komputer mampu melakukan apa
yang ingin kita lakukan, tanpa memberitahu itu bagaimana melakukannya. Pemrograman genetik (GP)
membahas tantangan ini dengan menyediakan sebuah metode yang secara otomatis mampu menciptakan
sebuah program komputer yang bekerja dari pernyataan masalah yang kita berikan. Pemrograman
genetik mencapai tujuan ini dengan pemrograman otomatis ( disebut juga sintesis program atau
induksi program) oleh genetik pemrograman dengan memanfaatkan populasi program komputer 
menggunakan prinsip-prinsip seleksi alam Darwin dan operasi terinspirasi secara biologis. 
Operasi yang termasuk didalamnya adalah reproduksi, crossover (rekombinasi seksual), mutasi,
dan operasi arsitektur-mengubah berpola setelah duplikasi gen dan penghapusan gen di alam.
Misalnya, unsur populasi mungkin sesuai dengan penempatan delapan ratu pada papan catur, dan
fungsi fitness fi mungkin menghitung jumlah ratu yang tidak diserang oleh ratu lainnya.
Mengingat perhitungan yang sesuai dari operator genetik dimana populasi awal penempatan ratu
dapat menelurkan koleksi baru dari penempatan ratu ini, sebuah sistem yang dirancang sesuai bisa
memecahkan  masalah delapan ratu. Keunikan GP berasal dari fakta bahwa sistem ini memanipulasi
populasi program-in terstruktur berbeda dengan banyak sistem dalam perhitungan evolusi lainnya
di mana unsur-unsur populasi yang diwakili menggunakan fl di string lebih dari beberapa abjad.
Dalam bab ini, konsep-konsep dasar, kerja, representasi dan aplikasi dari program GP genetik
akan dibahas secara rinci. 


6.2 Perbandingan GP dengan Pendekatan lain
               Pemrograman genetik (GP) adalah pemrograman yang bersifat  independen, pendekatan pada
pemecahan masalah domain di lakukan pada program komputer yang berkembang untuk solusi
mendapati masalah. Teknik solusi didasarkan pada prinsip Darwin dari "survival of the fi ttest" dan
hal ini sangat berkaitan erat dengan algoritma genetika (GA).
Terdapat tiga perbedaan penting antara GA dan GP :
·         Struktur: GP biasanya menggunakan struktur pohon sementara GA ini berevolusi biner atau 
real string number.
·         Aktif Vs Pasif: Karena GP biasanya berkembang dengan  program komputer, solusi yang 
dapat dijalankan tanpa pengolahan pasca yaitu struktur aktif, sementara GA ini biasanya beroperasi
 pada string kode biner yaitu struktur pasif, yang membutuhkan pengolahan pasca. 
·         Variable Vs fi panjang yang tetap: Dalam GA versi lama, panjang string biner adalah  tetap 
sebelum prosedur solusi dimulai. Namun pohon parsing GP dapat bervariasi dalam panjang seluruh 
jalankan. Meskipun diakui bahwa pemrograman GA lebih baik dari pada GP karena menggunakan
variabel string panjang.
 
               Kemampuan untuk mencari ruang solusi dan menemukan daerah yang berpotensi 
mengandung solusi optimal untuk masalah yang diberikan adalah salah satu komponen fundamental
dari yang paling arti fi cial intelligence (AI) sistem. Ada tiga jenis utama dari pencarian; buta pencarian,
mendaki bukit dan pencarian balok. GP adalah diklasifikasikan sebagai pencari balok karena
mempertahankan populasi solusi yang lebih kecil dari semua solusi yang tersedia. GP juga biasanya
diimplementasikan sebagai algoritma pencarian yang lemah karena tidak mengandung masalah spesifik
pengetahuan, meskipun beberapa penelitian telah diarahkan "stronglytypedgeneticprogramming"
ndregions fi .HoweverwhileGPcan mengandung solusi optimal, algoritma pencarian lokal tambahan
biasanya diperlukan untuk mencari optima tersebut. algoritma memetika dapat memenuhi tanggung
peran ini, dengan menggabungkan algoritma evolusioner dengan masalah spesifik algoritma c pencari
untuk menemukan solusi optimal. pemrograman genetik juga berbeda dari semua pendekatan lain
untuk Arti fi cial kecerdasan, pembelajaran mesin, jaringan saraf, sistem adaptif, pembelajaran
penguatan, atau logika otomatis di semua (atau sebagian besar) dari tujuh cara berikut: 
(1) Representasi: pemrograman genetik terang-terangan melakukan pencari untuk solusi untuk
masalah yang diberikan dalam program ruang.
(2) Peran point-to-point transformasi dalam pencarian: pemrograman genetik tidak melakukan
pencarian dengan mengubah satu titik dalam ruang pencarian ke titik lain, melainkan mengubah satu
set poin ke satu set poin. 
(3) Peran mendaki bukit dalam pencarian: pemrograman genetik tidak bergantung secara eksklusif
pada mendaki bukit serakah untuk melakukan pencarian, melainkan mengalokasikan sejumlah
percobaan, dengan cara berprinsip, untuk pilihan yang dikenal rendah.
(4) Peran determinisme dalam pencarian: pemrograman genetik melakukan pencarian probabilistik. 
(5) Peran basis pengetahuan eksplisit: Tidak ada
(6) Peran logika formal dalam pencarian: Tidak ada.
(7) dasar-dasar teknik: biologis terinspirasi.

·         Pertama, mempertimbangkan masalah representation. Sebagian besar teknik kecerdasan buatan, pembelajaran mesin, jaringan saraf, sistem adaptif, pembelajaran penguatan, atau logika otomatis mempekerjakan secara khusus struktur sebagai pengganti program komputer biasa. Struktur pengganti termasuk jika-maka aturan produksi, Horn klausa, pohon keputusan, jaringan Bayesian, logika proporsional, tata bahasa formal, diagram keputusan biner, frame, cluster konseptual, konsep set, vektor berat numerik (untuk jaring saraf), vektor koefisien numerik koefisien fi untuk polinomial atau fi xed ekspresi lain (untuk sistem adaptif), aturan sistem fi er genetik klasifikasi, fi xed tabel nilai (seperti dalam pembelajaran penguatan), atau string kromosom linear (seperti dalam algoritma genetika konvensional). Terkecuali situasi yang tidak biasa, beberapa programmer juta komputer tidak menggunakan salah satu struktur pengganti untuk menulis program komputer. Sebaliknya, selama lima dekade, programmer manusia telah bertahan dalam menulis program komputer yang mencampurkan banyaknya jenis perhitungan (misalnya, aritmatika dan logis) yang beroperasi pada bermacam jenis variabel (misalnya, integer, terapung-point, dan Boolean). Programmer telah bertahan dalam menggunakan memori internal untuk menyimpan hasil perhitungan antara untuk menghindari mengulangi perhitungan pada setiap kesempatan ketika hasilnya diperlukan. Terlebih lagi, mereka telah bertahan dalam melewati parameter untuk subrutin sehingga mereka dapat menggunakan kembali subrutin mereka dengan instantiations berbeda nilai. Dan mereka telah bertahan dalam mengatur subrutin mereka ke hirarki. Semua alat di atas pemrograman komputer biasa telah digunakan sejak awal era komputer elektronik di l940s. Secara signifikan, tidak ada telah jatuh ke dalam tidak digunakan oleh programmer manusia.
Namun, terlepas dari utilitas nyata dari alat-alat setiap hari dari pemrograman komputer, alat-alat ini sebagian besar absen dari teknik yang ada otomatis mesin belajar, jaringan saraf, arti fi cial intelligence, sistem adaptif, pembelajaran penguatan, dan logika otomatis. Kami percaya bahwa pencarian solusi untuk tantangan untuk mendapatkan computersto memecahkan masalah tanpa secara eksplisit programmingthem harus dilakukan di ruang program komputer. Tentu saja, setelah Anda menyadari bahwa pencarian harus dilakukan program ruang, Anda langsung dihadapkan dengan tugas dari fi nding program yang diinginkan dalam ruang yang sangat besar dari program mungkin. Seperti yang akan terlihat, pemrograman genetik melakukan tugas ini penemuan Program. Ini menyediakan cara masalah-independen untuk produktif mencari ruang mungkin program komputer untuk fi nd program yang memuaskan memecahkan masalah yang diberikan.
·         Kedua, perbedaan lain antara pemrograman genetik dan teknik hampir setiap otomatis menyangkut sifat dari pencarian yang dilakukan di ruang pencarian yang dipilih teknik ini. Hampir semua metode non-genetik ini menggunakan strategi point-to point yang mengubah satu titik dalam ruang pencarian ke lain programmings point.Genetic tunggal berbeda karena beroperasi dengan secara eksplisit budidaya populasi yang beragam dari sering-tidak konsisten dan sering bertentangan pendekatan untuk memecahkan masalah. pemrograman genetik melakukan pencarian berkas di ruang program dengan iterasi mengubah satu populasi program komputer calon ke populasi baru program.
·         Ketiga, mempertimbangkan peran mendaki bukit. Ketika lintasan melalui ruang pencarian adalah dari satu titik tunggal untuk titik lain, ada godaan hampir tak tertahankan untuk memperpanjang pencarian hanya dengan memindahkan ke titik yang dikenal superior ke titik saat ini. Akibatnya, teknik hampir semua otomatis bergantung secara eksklusif pada mendaki bukit serakah untuk membuat transformasi dari titik saat ini di ruang pencarian ke titik berikutnya. Godaan untuk mengandalkan mendaki bukit diperkuat karena banyak masalah mainan dalam literatur dari ladang pembelajaran mesin dan arti fi intelijen resmi sangat sederhana yang mendaki bukit sebenarnya bisa, memecahkan mereka. Namun, popularitas tidak bisa menyembuhkan kecenderungan bawaan mendaki bukit untuk menjadi terjebak pada optimum lokal yang tidak optimal global. masalah yang menarik dan trivial umumnya memiliki poin tinggi hasil yang tidak dapat diakses untuk mendaki bukit serakah. Bahkan, keberadaan titik-titik dalam ruang pencarian yang tidak dapat diakses untuk mendaki bukit adalah kerja yang baik definisi dari non-kesia. Fakta bahwa pemrograman genetik tidak bergantung pada strategi pencarian point-to-point membantu liberateit dari miopia mendaki bukit. pemrograman genetik bebas untuk mengalokasikan sejumlah terukur tertentu percobaan untuk poin yang dikenal rendah. Alokasi ini cobaan untuk individu dikenal-rendah tidak termotivasi oleh badan amal, tetapi dengan harapan bahwa itu akan sering menggali lintasan unobvious melalui ruang pencarian yang mengarah ke poin dengan hasil akhirnya lebih tinggi. Fakta bahwa pemrograman genetik beroperasi dari populasi memungkinkan untuk membuat sejumlah kecil bergerak petualang sekaligus mengejar jalan lebih segera memuaskan dari muka melalui ruang pencarian.
·         Keempat, perbedaan lain antara pemrograman genetik dan hampir setiap teknik lain dari arti kecerdasan fi resmi dan pembelajaran mesin adalah bahwa pemrograman genetik melakukan pencarian probabilistik. Sekali lagi, pemrograman genetik tidak unik dalam hal ini. Misalnya, simulasi annealing dan algoritma genetika juga probabilistik. Namun, sebagian besar teknik otomatis yang ada adalah deterministik.
·         Kelima, mempertimbangkan peran basis pengetahuan dalam mengejar tujuan secara otomatis membuat program komputer. Banyak ilmuwan komputer tanpa bertanya menganggap bahwa logika formal harus memainkan peran terkemuka dalam sistem untuk secara otomatis membuat program komputer. Demikian pula, sebagian besar peneliti kontemporer dalam arti kecerdasan fi cial percaya bahwa sistem untuk secara otomatis menciptakan program komputer harus menggunakan basis pengetahuan eksplisit. Memang, selama empat dekade terakhir, lapangan dari arti fi intelijen resmi telah didominasi oleh keyakinan kuat menegaskan bahwa tujuan mendapatkan komputer untuk memecahkan masalah secara otomatis dapat dicapai hanya melalui metode logika inferensi formal dan pengetahuan. Pendekatan ini biasanya memerlukan pemilihan representasi pengetahuan, akuisisi pengetahuan, yang codi fi kasi pengetahuan ke dalam basis pengetahuan, penitipan basis pengetahuan ke dalam komputer, dan manipulasi pengetahuan di komputer menggunakan metode inferensi logika formal. Mencolok, pemrograman genetik tidak bergantung pada basis pengetahuan eksplisit untuk mencapai tujuan secara otomatis membuat program komputer. Meskipun ada banyak cara opsional untuk menggabungkan pengetahuan domain menjadi lari dari pemrograman genetik, pemrograman genetik tidak memerlukan (atau biasanya menggunakan) basis pengetahuan eksplisit untuk memandu pencarian.
·         Keenam, mempertimbangkan peran metode inferensi logika formal. Banyak ilmuwan komputer tanpa bertanya menganggap bahwa setiap teknik pemecahan masalah harus logis suara, deterministik, logis konsisten, dan pelit. Dengan demikian, metode yang paling konvensional arti fi intelijen resmi dan mesin pembelajaran memiliki karakteristik ini. Namun, logika tidak mengatur dua jenis yang paling penting dari proses pemecahan masalah yang kompleks, yaitu, proses penemuan yang dilakukan oleh manusia kreatif dan evolusi proses occurringin alam. Sebuah ide baru yang dapat secara logis disimpulkan dari fakta-fakta yang diketahui dalam lapangan, menggunakan transformasi yang mengetahui lapangan, tidak dianggap sebagai penemuan. Harus ada apa hukum paten mengacu sebagai "langkah logis" (yaitu, sebuah fi unjusti ed langkah) untuk membedakan penemuan diduga dari apa yang mudah deducible dari yang sudah dikenal.

Desain entitas kompleks oleh proses evolusi di alam adalah jenis penting dari pemecahan masalah yang tidak diatur oleh logika. Di alam, solusi untuk masalah desain yang ditemukan oleh proses probabilistik evolusi dan seleksi alam. Ini bukan proses logis. Memang, alternatif yang tidak konsisten dan kontradiktif berlimpah. Bahkan, keragaman genetik tersebut diperlukan untuk proses evolusi untuk berhasil. Secara signifikan, solusi yang dibuat oleh evolusi dan seleksi alam hampir selalu berbeda dari yang dibuat dengan metode konvensional arti fi kecerdasan dan mesin resmi pembelajaran dalam satu hal yang sangat penting. solusi Evolved tidak rapuh; mereka biasanya mampu bergulat dengan kebaruan abadi lingkungan nyata. Demikian pula, pemrograman genetik tidak dipandu oleh metode inferensi logika formal dalam pencarian untuk sebuah program komputer untuk memecahkan masalah yang diberikan. Ketika tujuannya adalah penciptaan otomatis dari program komputer, semua pengalaman kami telah membawa kita untuk menyimpulkan bahwa pendekatan non-logis yang digunakan dalam proses penemuan dan evolusi alam jauh lebih bermanfaat daripada prinsip-prinsip logika-driven dan pengetahuan berbasis konvensional arti fi intelijen resmi. Singkatnya, "logika dianggap berbahaya.

·         Ketujuh, metafora biologis yang mendasari pemrograman genetik sangat berbeda dari pinnings bawah dari semua teknik lain yang sebelumnya telah mencoba dalam mengejar tujuan secara otomatis membuat program komputer. Banyak ilmuwan komputer dan matematika yang baf fl ed oleh saran bahwa biologi mungkin relevan dengan medan mereka. Sebaliknya, kita tidak melihat biologi sebagai juga tidak mungkin dari yang menarik solusi untuk tantangan untuk mendapatkan komputer untuk memecahkan masalah tanpa secara eksplisit pemrograman itu. Genetik pemrograman pekerjaan con fi rms pandangan Turing bahwa memang ada "hubungan" antara mesin kecerdasan dan evolusi dengan menggambarkan implementasi kami dari jalan ketiga Turing untuk mencapai kecerdasan mesin.

6.3 Primitif Pemrograman Genetik
Setiap solusi berevolusi dengan GP dirakit dari dua set node primitif; terminal dan terminal functions.The set berisi node yang providean masukan untuk sistem GP sedangkan fungsi set berisi node yang memproses nilai-nilai yang sudah dalam sistem. Konstanta dapat digunakan di GP dengan memasukkan mereka di set terminal. Setelah proses evolusi dimulai, sistem GP secara acak memilih node dari salah mengatur atau sehingga tidak dapat memanfaatkan semua node yang tersedia. Namun peningkatan ukuran setiap set simpul memperbesar ruang pencarian. Oleh karena itu hanya satu set simpul relatif sederhana pada awalnya disediakan dan node biasanya ditambahkan hanya jika diperlukan.

6.3.1 Operator Genetik
Ada tiga operator evolusi besar dalam sistem GP:
·         Reproduksi: memilih individu dari dalam populasi saat ini akan disalin persis ke generation.There berikutnya beberapa cara memilih yang individu akan disalin termasuk "fi fitness proporsional" seleksi, "peringkat" seleksi dan "turnamen" pilihan.
·         Crossover: meniru rekombinasi seksual di alam, di mana dua solusi orangtua dipilih dan bagian dari subtree mereka bertukar dan karena masing-masing fungsi pameran properti "penutupan" (masing-masing anggota pohon mampu memproses semua nilai argumen mungkin), setiap Crossover operasi harus menghasilkan dalam pembentukan struktur hukum.
·         Mutasi: menyebabkan perubahan acak dalam individu sebelum diperkenalkan ke populasi berikutnya. Tidak seperti menyeberang, mutasi adalah aseksual dan dengan demikian hanya beroperasi pada satu individu. Selama mutasi baik semua fungsi atau terminal dikeluarkan di bawah node sewenang-wenang ditentukan dan cabang baru secara acak dibuat, atau node tunggal ditukarkan lain.

6.3.2 Pemrograman Genetik Generasi
GP telah mengembangkan dua approachesto utama berurusan dengan isu generasi tersebut; generasi dan steady state. Di GP generasi, terdapat juga-de fi generasi ned dan berbeda, dengan setiap generasi yang diwakili oleh populasi lengkap individu. Oleh karena itu setiap penduduk baru dibuat dari populasi yang lebih tua, yang kemudian menggantikan. Mapan GP tidak mempertahankan ini generasi diskrit tapi terus berkembang generasi sekarang menggunakan operator genetik yang tersedia.
Programming

6.3.3 Pohon Berbasis Genetik
Primitif dari GP, fungsi dan terminal node, harus dirakit menjadi struktur sebelum mereka dapat dieksekusi. Tiga jenis utama dari struktur yang ada: pohon, linear dan grafik. Dalam karya ini, input (struktur dioptimalkan atau dirancang) benar-benar membentuk jaringan grafik. Namun dengan duplikasi data sendi yaitu sama "simpul bersama" bisa ada di pohon yang sama pada lebih dari satu kesempatan, jaringan grafik ini diubah menjadi struktur pohon.

6.3.4 Representasi Pemrograman Genetik
Kebutuhan representasi yang baik dalam perhitungan evolusi, dan dalam arti fi intelijen resmi lebih umum, disebut masalah representasi. pemrograman genetik memiliki dua bentuk representasi; yang variational dan generatif. Representasi variational adalah deskripsi statis dari sebuah program dan tunduk pada variasi evolusi. Syarat utama untuk representasi variational adalah evolvability: evolusi program peningkatan fi fitness secara generasi ketika mengalami variasi genetik. Representasi generatif adalah produk dari representasi variasional, dan menggambarkan bentuk dinamis dari sebuah program. Persyaratan utamanya adalah bahwa hal itu dapat dijalankan. Namun, meskipun kebutuhan yang berbeda dari representasi variasional dan generatif, kebanyakan sistem GP tidak membedakan antara keduanya.

6.3.4.1 Representasi Biologi
Biologi tidak membedakan antara variational dan representasi generatif. Mereka disebut, masing-masing, genetik dan representasi genetik phenotypic.The, dari sudut pandang reduksionis, adalah linear, didistribusikan secara spasial, urutan atribut diwariskan. Setiap atribut diwariskan menggambarkan urutan asam amino dari protein. Pembangunan menafsirkan deskripsi ini dan menghasilkan protein; fundamental componentsof presentasi phenotypicre. Sekelompok protein kerja setelah tugas umum disebut jalur biokimia. Tugas-tugas yang dilakukan oleh jalur biokimia jatuh ke dalam tiga kelas yang luas: metabolik, sinyal dan ekspresi gen. Dari jumlah tersebut, jalur metabolisme yang dianggap paling mendasar bagi mereka menerapkan perilaku pengolahan sel, sementara sinyal dan jalur ekspresi gen mengambil peran gurational con fi. pengolahan biokimia sebesar manipulasi negara kimia sel melalui sistem reaksi kimia. jalur metabolisme terdiri dari enzim, suatu kelompok protein yang melaksanakan perilaku katalitik; memungkinkan reaksi yang akan bijak lain tidak mungkin dalam suhu selular relatif rendah. Enzim mencapai perilaku katalitik mereka dengan mengikat Speci fi c kimia, substrat enzim, dan membimbing reaksi mereka. Kerjasama dalam cara jalan metabolik muncul dari berbagi produk-substrat antara enzim, di mana produk dari satu enzim menjadi substrat lain.

6.3.4.2 Biomimetic Representasi
Representasi biologi memiliki sejumlah kualitas dibayangkan berguna, tapi biasanya tidak ditemukan, dalam representasi pemrograman genetik. Ini, meliputi: spesialisasi bentuk evolusi dan eksekusi; representasi evolvable, "dirancang" untuk evolusi; netralitas, meningkatkan keragaman genetik dan adaptasi; perilaku kurang dibatasi, sehingga lebih bebas untuk evolusi; dan posisi kemerdekaan, tidak membatasi fungsi gen ke posisi gen. Sebuah Banyaknya sistem GP meniru representasi genetik biologi. Banyak dari telah memperkenalkan tahap perkembangan, yang memungkinkan representasi genetik untuk menjadi independen dari representasi executable. Ini telah terbukti untuk meningkatkan keragaman genetik dan mendorong netralitas. Sejumlah pendekatan ini juga memungkinkan unit genic kedudukan independen dalam genom. Mimikri representasi fenotipik kurang umum. Namun, idiom komputasi telah digunakan untuk menggambarkan aksi enzim dan jalur biokimia. Analoginya aktivitas enzim telah digunakan untuk tujuan komputasi dalam domain arti fi cial. model evolusi pembangunan jalur juga telah dicoba.

6.3.4.3 Enzim Genetik Pemrograman Representasi
Enzim pemrograman genetik adalah sistem yang meniru biologi di kedua representasi genetik dan fenotipik. representasi fenotipik didasarkan pada sebuah abstraksi dari jalur metabolik. Tujuan dari sistem ini adalah untuk berevolusi analog dari jalur metabolisme dalam sirkuit logika kombinasional. Gambar 6.1 menunjukkan hubungan antara representasi dari GP enzim. Selama evolusi, sirkuit dikodekan sebagai urutan linear dari "gen"; dimana setiap gen menggambarkan preferensi masukan, kota-kota spesifisitas, dari gerbang logika tertentu atau terminal output.



Sebuah spesifisitas adalah nilai titik mengambang fl antara nol dan satu yang menunjukkan preferensi relatif untuk input (substrat). Setiap kegiatan masukan memakan memiliki spesifik kota fi didefinisikan untuk produk dari setiap kegiatan output. Representasi fenotip yang dihasilkan oleh genotipe divisualisasikan di pusat Gambar. 6.1. ketebalan garis menunjukkan relatif kota spesifik. Dalam prakteknya, jaringan harus terhubung sepenuhnya. Namun, untuk kejelasan hanya dominan dan beberapa kota spesifisitas resesif ditampilkan. Ketika sirkuit terealisasi, specicities dominan harus peta untuk koneksi sirkuit. Namun, sirkuit kombinasional harus non-berulang dan akibatnya tidak akan selalu mungkin untuk mengekspresikan koneksi paling disukai sirkuit elemen. Pendekatan ini diambil daripada membiarkan sirkuit valid atau menghambat representasi genetik.

Tanpa ragu, program dapat dianggap sebagai string. Namun demikian, dua keterbatasan penting yang membuat tidak mungkin untuk menggunakan representasi dan operasi dari GA sederhana kami:
1. Hal ini sebagian besar di tepat untuk mengasumsikan panjang yang tetap dari program.
2. Probabilitas untuk memperoleh program sintaksis benar ketika menerapkan inisialisasi sederhana kami, menyeberang, dan prosedur mutasi putus asa rendah.
Oleh karena itu, sangat diperlukan untuk memodifikasi representasi data dan operasi sehingga kebenaran sintaksis lebih mudah untuk menjamin. Pendekatan umum untuk mewakili program dalam pemrograman genetik adalah untuk mempertimbangkan program yang strees. Dengan demikian, inisialisasi dapat dilakukan secara rekursif, menyeberang dapat dilakukan dengan bertukar sub pohon, dan penggantian acak sub pohon dapat berfungsi sebagai operasi mutasi. Karena konstruksi adalah daftar bersarang, program dalam bahasa LISP-seperti sudah memiliki semacam struktur seperti pohon. Gambar 6.2 menunjukkan contoh bagaimana fungsi 3x + sin (x + 1) dapat dilaksanakan dalam LISP seperti bahasa dan bagaimana seperti fungsi LISPlike dapat dibagi menjadi pohon. Jelas, representasi pohon langsung sesuai dengan daftar bersarang program ini terdiri dari; ekspresi atom, seperti variabel dan konstanta, daun sedangkan fungsi sesuai dengan node non-cuti.
Ada satu dis penting keuntungan dari LISP pendekatan-itu sulit untuk memperkenalkan jenis kasus checking.In dari fungsi murni numerik seperti dalam contoh di atas, tidak ada masalah sama sekali. Namun, dapat diinginkan untuk memproses data numerik, string, dan ekspresi logis secara bersamaan. Ini adalah sulit untuk menangani jika kita menggunakan representasi pohon seperti pada Gambar. 6.2.

Dalam rangka untuk mendapatkan perasaan bagaimana bekerja dengan BNF keterangan tata bahasa, kita sekarang akan menunjukkan langkah demi langkah bagaimana ekspresi (TIDAK (x OR y)) dapat turunan dari bahasa di atas. Untuk mempermudah, kita menghilangkan tanda kutip untuk simbol terminal:
1. Kita harus mulai dengan simbol awal:  <exp>
2. Kami mengganti <exp> dengan derivasi kedua mungkin:
<exp> → (<neg><exp>)
3. Simbol <neg> hanya dapat diperluas dengan simbol terminal TIDAK:
(<Neg> <exp>) → (TIDAK <exp>)
4. Selanjutnya, kita ganti <exp> dengan derivasi ketiga mungkin:
(TIDAK <exp>) → (TIDAK (<exp> <bin> <exp>))
5. Kami memperluas derivasi kedua mungkin untuk <bin>:
(TIDAK (<exp> <bin> <exp>)) → (TIDAK (<exp> ATAU <exp>))


6. pertama terjadinya <exp> diperluas dengan derivasi pertama:
(NOT (<exp> ATAU <exp>)) → (TIDAK (<var> ATAU <exp>))
7. Terjadinya kedua hexpi diperluas dengan pertama derivasi, terlalu: (NOT (<var> ATAU
<exp>)) → (TIDAK (<var> ATAU <var>))
8. Sekarang kita ganti hvari pertama dengan alternatif pertama yang sesuai: (NOT (<var> ATAU <var>)) → (TIDAK (x OR <var>))
9. Akhirnya, simbol non-terminal lalu diperluas dengan alternatif kedua:
(NOT (x OR <var>)) → (TIDAK (x OR y))


6.4 Atribut di Pemrograman Genetik
Pemrograman genetik memiliki 16 atribut apa yang kadang-kadang disebut pemrograman otomatis atau sintesis program atau induksi program).
·         Atribut No 1 (Mulai dengan "Apa yang perlu dilakukan"): Dimulai dari pernyataan tingkat tinggi menentukan persyaratan dari masalah.
·         Atribut No 2 (Menceritakan kami "Bagaimana melakukannya"): Ini menghasilkan hasil dalam bentuk urutan langkah-langkah yang dapat dijalankan pada komputer.
·         Atribut No 3 (Menghasilkan program komputer): Ini menghasilkan anentity yang dapat dijalankan pada komputer.
Atribut No 4 (penentuan otomatis ukuran program): Memiliki kemampuan untuk secara otomatis menentukan jumlah yang tepat dari langkah-langkah yang harus dilakukan sehingga tidak memerlukan pengguna untuk prespecify ukuran dari solusi.
·         Atribut No 5 (Kode reuse): Memiliki kemampuan untuk secara otomatis mengatur kelompok yang berguna dari langkah-langkah sehingga mereka dapat digunakan kembali.
·         Atribut No 6 (penggunaan Parameterizedre): Memiliki kemampuan untuk menggunakan kembali kelompok langkah dengan instantiations yang berbeda nilai (parameter formal atau variabel dummy).
·         Atribut No 7 (storage internal): Memiliki kemampuan untuk menggunakan penyimpanan internal dalam bentuk variabel tunggal, vektor, matriks, array, tumpukan, antrian, daftar, memori relasional, dan struktur data lainnya.
·         Atribut No 8 (Iterasi, loop, dan recursions): Memiliki kemampuan untuk menerapkan iterasi, loop, dan recursions.
·         Atribut No 9 (Self-organisasi hierarki): Memiliki kemampuan untuk secara otomatis mengatur kelompok langkah menjadi sebuah hirarki.
·         Atribut No 10 (penentuan Automatic arsitektur program): Memiliki kemampuan untuk secara otomatis menentukan apakah akan menggunakan subrutin, iterasi, loop, recursions, dan penyimpanan internal, dan jumlah argumen yang dimiliki oleh masing-masing subroutine, iterasi, lingkaran, rekursi .
·         Atribut No 11 (Wide berbagai konstruksi pemrograman): Memiliki kemampuan untuk menerapkan analog dari pemrograman konstruksi yang pemrogram komputer manusia fi nd berguna, termasuk macro, perpustakaan, mengetik, pointer, operasi bersyarat, fungsi logis, fungsi integer, terapung fungsi-titik, fungsi bernilai kompleks, beberapa masukan, beberapa output, dan instruksi kode mesin.
·         Atribut No 12 (Well-de fi ned): Ini beroperasi dengan cara ned fi baik-de. Ini salah lagi membedakan antara apa yang pengguna harus menyediakan dan apa sistem memberikan.
·         Atribut No 13 (Soal-independent): Ini adalah masalah-independen dalam arti bahwa pengguna tidak harus memodifikasi langkah executable sistem untuk setiap masalah baru.
·         Atribut No 14 (Wide penerapan): Ini menghasilkan solusi yang memuaskan untuk berbagai macam masalah dari berbagai medan yang berbeda.
·         Atribut No 15 (Skalabilitas): Ini skala baik untuk versi yang lebih besar dari masalah yang sama.
·         Atribut No. 16 (Kompetitif dengan hasil yang dihasilkan manusia): Ini menghasilkan hasil yang kompetitif dengan yang dihasilkan oleh programmer manusia, insinyur, matematikawan, dan desainer.
6.5 Langkah Pemrograman Genetik

6.5.1 Persiapan Langkah Pemrograman Genetik
Figure6.4 showsthe lima langkah persiapan utama untuk versi dasar pemrograman genetik. Langkah-langkah persiapan (ditampilkan di atas angka) adalah input ke sistem pemrograman genetik. Sebuah program komputer (ditampilkan di bagian bawah) adalah output dari sistem pemrograman genetik. Program yang secara otomatis dibuat oleh pemrograman genetik dapat mengatasi, atau sekitar memecahkan, masalah theuser ini. pemrograman genetik membutuhkan satu set bahan primitif untuk memulai.



6.5.2 Pelaksanaan Langkah Pemrograman Genetik

6.5.2.1. Penciptaan Populasi inisial dari Program Komputer
pemrograman genetik dimulai dengan ribuan cairan primordial program komputer secara acak. Set fungsi yang mungkin muncul pada titik-titik internal pohon program dapat mencakup fungsi aritmatika biasa dan kondisional operator. Set terminal muncul pada titik-titik eksternal biasanya meliputi input eksternal program (seperti variabel independen X dan Y) dan acak konstanta (seperti 3,2 dan 0,4). Program-program secara acak dibuat biasanya memiliki berbagai ukuran dan bentuk.


6.6.2.2. Fungsi kecocokkan
Yang paling sulit dan konsep yang paling penting dari pemrograman genetik adalah fungsi kecocokkan. Fungsi kecocokkan menentukan seberapa baik program ini mampu memecahkan masalah. Hal ini sangat bervariasi dari satu jenis program ke jenis selanjutnya. Misalnya, jika satu adalah untuk membuat program genetik untuk mengatur waktu dari jam, fungsi kecocokkan akan hanya memperbaiki waktu pada jam yang salah. Sayangnya, beberapa masalah memiliki fungsi kecocokkan yang mudah; kebanyakan kasus memerlukan sedikit modifikasi dari masalah untuk menemukan kecocokkan.

6.5.2.3. Fungsi dan Terminal
Terminal dan fungsi set juga merupakan komponen penting dari pemrograman genetik. Pengaturan terminal dan fungsi adalah alfabet dari program yang akan dibuat. Set terminal terdiri dari variabel dan konstanta dari program. Dalam labirin misalnya, terminal set akan berisi tiga perintah: maju, kanan dan kiri. Fungsi set terdiri dari fungsi program. Dalam contoh labirin fungsi set akan berisi: Jika "dot" maka lakukan x yang lain lakukan y. Fungsi-fungsi tersebut adalah beberapa fungsi matematika, seperti penambahan, pengurangan, pembagian, perkalian dan fungsi yang lebih kompleks lainnya.

6.5.2.4. Operasi Crossover
Dua operasi utama ada untuk memodifikasi struktur dalam pemrograman genetik. Itu paling yang penting adalah operasi crossover. Dalam operasi crossover dua solusi digabungkan seksual untuk membentuk dua solusi baru atau keturunan. Orang tua dipilih dari populasi dengan fungsi dari ecocokkan dari solusi. tiga metode ada untuk memilih solusi untuk operasi crossover. Metode pertama menggunakan probabilitas didasarkan pada kecocokkan dari solusi. Jika f (s(T)) adalah kecocokkan dari solusi Si dan

adalah jumlah total dari semua anggota populasi, maka probabilitas solusi Si yang akan disalin ke generasi berikutnya adalah:


6.5.2.5. Mutasi
Mutasi merupakan fitur penting dari pemrograman genetik. Dua jenis mutasi yang mungkin. Jenis pertama adalah semacam fungsi yang hanya dapat menggantikan fungsi atau terminal hanya dapat menggantikan terminal. Pada jenis kedua seluruh cabang dapat menggantikan cabang lain.

6.6. Karakteristik Pemrograman Genetik
Pemrograman genetik sekarang memberikan Mesin cerdas pemasukan tinggi berkompetisi dengan umat manusia.
Berdasarkan kalimat ini, dapat dicatat bahwa empat karakteristik utama pemrograman genetik adalah:
• manusia-kompetitif
• keuntungan tinggi
• rutin
• mesin cerdas.

6.6.1. Apa yang dimaksud dengan "Manusia-Kompetitif"
Dalam upaya untuk mengevaluasi metode pemecahan masalah otomatis, muncul pertanyaan apakah ada zat nyata untuk masalah demonstratif yang diterbitkan sehubungan dengan metode ini. masalah demonstratif di lapangan dari kecerdasan buatan dan mesin pembelajaran sering dibuat masalah mainan yang beredar secara eksklusif di dalam kelompok akademis yang mempelajari metodologi tertentu. Masalah-masalah ini biasanya memiliki sedikit relevansi dengan masalah apapun yang dikejar oleh setiap ilmuwan atau insinyur luar lapangan dari kecerdasan buatan dan mesin belajar.

Gambar : operasi Crossover untuk pemrograman genetik. Yang ditebalkan pada kedua orang tua bertukar untuk menciptakan keturunan atau anak-anak. (Anak di sebelah kanan adalah representasi pohon parse untuk persamaan kuadrat.)


Gambar : Mengilustrasikan salah satu keuntungan utama dari pemrograman genetik lebih algoritma genetika. Dalam pemrograman genetik orang tua identik dapat menghasilkan keturunan yang berbeda, sedangkan dalam algoritma genetika orang tua identik akan menghasilkan keturunan yang identik. Yang ditebalkan menunjukkan percabangan untuk ditukarkan.


Gambar : Dua jenis mutasi. Pohon parse teratas adalah agen asli. Bagian bawah kiri cabang menggambarkan mutasi dari satu terminal (2) untuk terminal tunggal lain (a). Juga menggambarkan mutasi dari fungsi tunggal (-) untuk fungsi lain tunggal (+). Parse pohon di kanan bawah menggambarkan penggantian subtree dengan subtree lain.

Delapan kriteria untuk mengatakan bahwa hasil otomatis dibuat adalah human-competitive
A Hasil itu dipatenkan sebagai penemuan di masa lalu, merupakan perbaikan atas penemuan yang sudah dipetankan, atau akan memenuhi syarat hari ini sebagai penemuan baru yang dipatenkan
B Hasilnya adalah sama atau lebih baik dari hasil yang diterima sebagai ilmiah hasil baru di saat itu diterbitkan dalam ulasan tajam ilmiah jurnal.
C Hasilnya adalah sama atau lebih baik daripada hasil yang ditempatkan ke dalam database atau arsip hasil yang dikelola oleh sebuah panel yang diakui secara ahli peneliti ilmiah internasional.
D Hasilnya diterbitkan dalam dirinya sendiri sebagai ilmiah baru hasil-independen dari fakta c yang hasilnya diciptakan secara mekanik.
E Hasilnya adalah sama atau lebih baik daripada solusi manusia diciptakan terbaru ke lama masalah yang telah terjadi suksesi semakin baik solusi manusia-dibuat.
F Hasilnya adalah sama atau lebih baik dari hasil yang dianggap sebagai prestasi di lapangan yang pada saat itu pertama ditemukan.
G Hasilnya memecahkan masalah terbantahkan sulit di lapangan tersebut.
H Hasilnya memegang sendiri atau memenangkan kompetisi yang diatur melibatkan kontestan manusia (dibentuk baik pemain manusia hidup atau program komputer yang dituis manusia).

6.6.2. Apa yang dimaksud dengan "High-Return"
Apa yang sudah disampaikan oleh operasi otomatis sebenarnya metode resmi yang berarti dibandingkan untuk jumlah pengetahuan, informasi, analisis, dan kecerdasan yang akan diberikan oleh penggunaan metode manusia?
Kami mendefinisikan rasio AI ("artificial-to-intelligence" rasio) dari pemecahan masalah Metode sebagai rasio yang yang disampaikan oleh operasi otomatis dari artificial metode untuk jumlah kecerdasan yang disediakan oleh manusia menerapkan metode untuk masalah tertentu.
Rasio AI ini terutama berhubungan dengan metode untuk mendapatkan komputer untuk secara otomatis memecahkan masalah karena mengukur nilai tambah dengan metode pemecahan masalah artificial. Nyatanya, tujuan dari ladang dari arti fi intelijen resmi dan pembelajaran mesin adalah untuk menghasilkan manusia yang kompetitif dengan rasio AI tinggi.

6.2.3. Apa yang dimaksud dengan "Rutinitas"
Secara umum merupakan prasyarat untuk apa yang kita maksudkan ketika kita mengatakan bahwa metode pemecahan masalah otomatis adalah "rutinitas." Setelah keumuman dari metode didirikan, "kerutinan" berarti bahwa usaha manusia relatif sedikit yang diperlukan untuk mendapatkan metode untuk berhasil menangani masalah baru dalam domain tertentu dan untuk berhasil menangani masalah baru dari domain yang berbeda. Kemudahan membuat transisi ke masalah baru terletak di jantung apa yang kita maksud dengan "rutinitas."
Sebuah metode pemecahan masalah tidak dapat dianggap rutinitas jika langkah-langkah pelaksanaan harus ditambah, dihapus, disusun ulang, dikerjakan ulang, atau disesuaikan oleh pengguna manusia untuk setiap masalah baru.

6.2.4. Apa yang dimaksud dengan "Machine Intelligence"
Istilah "artificial intelligence" saat ini terutama terkait dengan upaya untuk mendapatkan komputer untuk memecahkan masalah dengan menggunakan metode yang mengandalkan pengetahuan, logika, dan berbagai metode analisis dan matematika. Istilah "machine learning" saat ini terutama terkait dengan upaya untuk mendapatkan komputer untuk memecahkan masalah yang menggunakan satu set kecil daN dipilih dari metodologi tertentu (banyak dari statistik alam).

6.7. Aplikasi dari Program Genetika

6.7.1. Aplikasi Pemrograman Genetik Teknik Sipil
Berbagai bidang aplikasi dari GP di teknik sipil adalah sebagai berikut:
• kekuatan prediksi pencukuran dari dalam RC balok
• Pemodelan pabrik pengolahan air limbah menggunakan pemrograman genetik untuk model kinerja dinamis dari instalasi pengolahan lumpur air limbah kota diaktifkan.
• Deteksi lalu lintas kecelakaan kecelakaan di jalan raya, kondisi kecepatan tinggi yaitu larut malam berdasarkan tiga tahun data lalu lintas sementara menghasilkan tingkat alarm palsu mendekati nol.
• Aliran melalui cekungan-Konstruksi perkotaan model jaringan limbah untuk menghitung risiko yang ditimbulkan oleh hujan untuk cekungan dan dengan demikian memberikan peringatan sebelum banjir.
• Prediksi pejalan kaki GP untuk meramalkan kali jalan tol perjalanan.
• Estimasi desain menggunakan GP untuk secara otomatis memperkirakan maksud desain berdasarkan informasi  operasional dan produk-spesifik dipantau selama proses desain.
• Pemodelan aset pasokan air untuk menentukan risiko ledakan pipa, GP  berevolusi untuk "tambang data" informasi database yang berisi tentang semburan pipa berkala.
• Identi fi kasi retak pro fi les retak dalam ratusan penukar panas tabung di pembangkit listrik tenaga nuklir pembangkit uap melalui analisis dari data yang diukur melalui pengujian non-destruktif kuantitatif.
• Pemodelan limpasan hujan-Discovery hubungan curah hujan-limpasan dalam dua tangkapan yang berbeda.
• Prediksi permintaan tenaga listrik jangka panjang
• Evolusi kontrol lampu lalu lintasnya hukum-Evolusi dari jenis baru kontrol adaptif sistem jaringan lalu lintasnya sinyal  tergantung pada variasi aliran lalu lintas.

6.8. Haploid Pemrograman Genetik dengan Dominasi
Dominasi crossover mirip dengan penggunaan dominasi di alam. Di alam, dominasi digunakan sebagai genotipe untuk fenotipik pemetaan ketika suatu organisme membawa pasangan (atau lebih dari satu) kromosom, tetapi di sini kita menggunakan dominasi pada struktur haploid. Bentuk haploid berisi semua informasi yang relevan dengan masalah, dan struktur yang banyak digunakan dalam algoritma evolusioner. Dominasi crossover digunakan sebagai cara untuk mempertahankan dan mempromosikan gen sukses (orang-orang yang meningkatkan individu kecocokkan di generasi sekarang) ke generasi berikutnya. operator crossover yang saat ini gagal untuk mengeksploitasi pengetahuan yang diperoleh di generasi sebelumnya dan sangat mengandalkan pada tekanan seleksi. Dominasi Crossover dalam teori memungkinkan eksploitasi ini terjadi selama Crossover tapi kami menyoroti masalah dengan penerapan dominasi Crossover dengan pemrograman genetik.


Gambar :
(C) dan (y) yang dipilih untuk Crossover
(Y) memiliki nilai dominasi besar dari (c)
(D) memiliki dominasi besar dari (w)
(E) memiliki dominasi besar dari (v)
(S), (r) yang dominan atas (f), (g)

Single-Node Dominasi Crossover
Dalam single-node dominasi Crossover dua orang tua membuat anak tunggal. Sebuah titik crossover dipilih secara acak seperti biasa. Dalam sub pohon yang dipilih untuk crossover nilai dominasi node atas dibandingkan. Node yang memiliki nilai dominasi tinggi menggantikan lainnya.


Gambar :
(C) dan (y) yang dipilih untuk Crossover
(Y) memiliki nilai dominasi besar dari (c)
Sub-Tree Dominasi Crossover
Sub-pohon dominasi crossover sangat banyak seperti SNDC. Perbedaan adalah bahwa dalam STDC node teratas dengan nilai dominasi tinggi menggantikan pohon lainnya.
Dominasi crossover bukanlah operator crossover yang tepat untuk digunakan dengan struktur GP saat ini. Karena fungsi mengambil nomor yang berbeda dari argumen mereka merusak bentuk pohon GP sehingga teknik luasnya pertama yang dipekerjakan oleh dominasi Crossover gagal ditemukan sesuai crossover yang berintegritas. Jalan alternatif promosi yang sudah digunakan dalam single-node dominasi crossover dan sub-pohon dominasi Crossover namun kedua operator gagal untuk meningkatkan kinerja GP. Yang pertama tidak memungkinkan pohon tumbuh sehingga mengurangi eksplorasi dan kedua pohon-pohon dieksploitasi daripada gen, sehingga menyebabkan pertumbuhan yang berlebihan.


(C) dan (y) yang dipilih untuk Crossover
(Y) memiliki nilai dominasi besar dari (c)

Ringkasan

Pemrograman genetik jauh lebih kuat daripada algoritma genetika. Output dari algoritma genetika adalah kuantitas, sementara output dari program genetik adalah program komputer lain. Pada dasarnya, ini adalah awal dari program komputer yang memprogram dirinya sendiri. pemrograman genetik yang terbaik bagi beberapa jenis masalah.  Jenis pertama adalah di mana tidak ada solusi yang ideal, (misalnya, sebuah program yang mendorong mobil). Tidak ada satu solusi untuk mengendarai mobil. Beberapa solusi berkendara aman dengan mengorbankan waktu, sementara yang lain melaju cepat pada risiko keamanan yang tinggi. Oleh karena itu, mengendarai mobil terdiri dari membuat fokus pada kecepatan dibandingkan keselamatan, serta banyak variabel lainnya. Dalam hal ini pemrograman genetik akan ditemukan sebagai solusi yang mencoba untuk berkompromi dan menjadi solusi yang efisien dari daftar besar variabel. Selanjutnya, pemrograman genetik berguna dalam mencari solusi di mana variabel yang terus berubah. Pada contoh mobil sebelumnya, program ini akan menemukan salah satu solusi untuk jalan raya beton halus, sementara itu akan menemukan solusi yang sama sekali berbeda untuk jalan beraspal kasar. Netralitas, hierarki dominasi dan keragaman semua aspek evolusi alam dan produk-produknya.
Pemrograman genetik telah digunakan untuk model dan mengontrol banyak proses dan untuk mengatur perilaku mereka sesuai dengan berbasis kecocokkan algoritma secara otomatis. Kebanyakan aplikasi ini ditandai dengan salah satu fitur berikut:
• solusi analitis tidak ada atau tidak dapat diturunkan
• variabel yang relevan yang kurang dipahami
• Kompleksitas solusi tidak diketahui
• Solusi Perkiraan semua yang dapat diharapkan
• Sejumlah besar data yang tersedia untuk pertambangan
• Besar marjinal manfaat yang ada untuk perbaikan kecil dalam kontrol atau pemodelan dan prediksi
Teori Pemrograman Genetik saat ini sangat terbelakang dan perlu untuk kemajuan cepat untuk mengejar ketinggalan dengan paradigma algoritma evolusioner lainnya. Sebagian besar hambatan berasal dari kenyataan kompleksitas variabel solusi berkembang di Pemrograman Genetik. Pelaksanaan Pemrograman Genetik akan diuntungkan dalam tahun-tahun mendatang dari pendekatan baru, yang meliputi penelitian dari biologi perkembangan. Selain itu, akan diperlukan untuk belajar menangani redundansi membentuk tekanan dalam evolusi kode. Aplikasi Programming genetik akan terus memperluas. Banyak aplikasi fokus pada pengendalian perilaku agen nyata atau maya. Dalam perannya ini, Programming genetik mungkin berkontribusi cukup untuk lapangan berkembang dari simulasi sosial dan perilaku.
Algoritma genetik telah ditemukan manfaat resmi dalam mengoptimalkan strategi agen sosial. Dengan kemampuannya untuk menyesuaikan kompleksitas strategi untuk lingkungan dan untuk memungkinkan persaingan antara agen Pemrograman Genetik posisi yang baik untuk memainkan peran penting dalam studi dan simulasi masyarakat dan evolusi mereka.

 Download HTML disini