download html download
2.1 Pendahuluan
Charles Darwin menyatakan teori evolusi alam pada asal-usul spesies. Selama beberapa generasi, organisme biologis berevolusi berdasarkan prinsip alam sepembacaan "survival of the fittest" untuk mencapai tugas-tugas yang luar biasa tertentu. Dengan demikian, ia bekerja sangat baik di alam, sebagai hasilnya itu harus menarik untuk mensimulasikan evolusi alam dan untuk mengembangkan metode.Di alam, individu dalam populasi bersaing satu sama lain untuk sumber daya virtual seperti makanan, tempat tinggal dan sebagainya. Juga dalam spesies yang sama, individu bersaing untuk menarik pasangan untuk reproduksi. Karena seleksi ini, berkinerja buruk para individu memiliki lebih sedikit kesempatan untuk bertahan hidup, dan yang paling disesuaikan pada individu menghasilkan jumlah yang relatif besar dari keturunan ini.
2.2 Latar Belakang Biologi
Ilmu yang berhubungan dengan mekanisme yang bertanggung jawab untuk persamaan dan perbedaan-perbedaan dalam spesies ini disebut Genetics. Kata "genetika" berasal dari bahasa Yunani kata "genesis" yang berarti "tumbuh" atau "menjadi". Ilmu genetika membantu kita untuk membedakan antara keturunan dan variasi dan berusaha untuk menjelaskan kemiripan dan perbedaan karena konsep Algoritma Genetika dan langsung berasal dari keturunan alam, sumber dan perkembangan mereka.2.2.1 Cell
Setiap hewan / sel manusia adalah kompleks banyak organisme "kecil" yang bekerja sama. Pusat dari semua ini adalah inti sel. Informasi genetik yang terkandung dalam inti sel. Gambar 1 menunjukkan anatomi sel hewan dan inti sel.
2.2.2 Kromosom
Semua informasi genetik akan disimpan dalam kromosom. Setiap kromosom adalah membangun dari dioxy Ribo Nucleic Acid (DNA). Pada manusia, kromosom ada dalam bentuk pasangan (23 pasang ditemukan). Kromosom dibagi menjadi beberapa bagian yang disebut gen. Gen kode sifat-sifat spesies yaitu, karakteristik individu.
2.2.3 Genetika
Untuk individu tertentu, seluruh kombinasi gen yang disebut genotipe. fenotip menjelaskan aspek fisik decoding genotipe untuk menghasilkan fenotip. Salah satu hal yang menarik dari evolusi adalah bahwa seleksi selalu dilakukan pada fenotipe sedangkan reproduksi recombines genotipe. Jadi morfogenesis memainkan peran kunci antara seleksi dan reproduksi.
2.2.4 Reproduksi
Reproduksi spesies melalui informasi genetik dilakukan oleh,
- Mitosis
-Meiosis
Dalam Mitosis informasi genetik yang sama disalin ke keturunan baru. Tidak ada pertukaran informasi. Ini adalah cara yang normal tumbuh dari struktur multi-sel, seperti organ. Gambar 2.4 menunjukkan bentuk mitosis reproduksi.
bentuk meiosis dasar reproduksi seksual. Ketika pembelahan meiosis mengambil gamet Place2 muncul dalam proses. Ketika reproduksi terjadi, dua gamet ini konjugasi untuk zigot yang menjadi individu baru.
2.2.5 Seleksi Alam
Asal-usul spesies didasarkan pada "Pelestarian variasi yang menguntungkan dan variasi yang tidak menguntungkan". variasi mengacu pada perbedaan yang ditunjukkan oleh individu spesies dan juga pada keturunan untuk orang tua yang sama. Ada lebih individu yang lahir dari bisa bertahan, sehingga ada perjuangan terus menerus untuk hidup. Individu dengan keuntungan memiliki kesempatan lebih besar untuk bertahan hidup yaitu, kelangsungan hidup lebih besar.
Berikut Tabel 2.1 memberikan daftar ekspresi yang berbeda, yang berada di com- mon dengan evolusi alam dan algoritma genetika.
Reproduksi spesies melalui informasi genetik dilakukan oleh,
- Mitosis
-Meiosis
Dalam Mitosis informasi genetik yang sama disalin ke keturunan baru. Tidak ada pertukaran informasi. Ini adalah cara yang normal tumbuh dari struktur multi-sel, seperti organ. Gambar 2.4 menunjukkan bentuk mitosis reproduksi.
bentuk meiosis dasar reproduksi seksual. Ketika pembelahan meiosis mengambil gamet Place2 muncul dalam proses. Ketika reproduksi terjadi, dua gamet ini konjugasi untuk zigot yang menjadi individu baru.
2.2.5 Seleksi Alam
Asal-usul spesies didasarkan pada "Pelestarian variasi yang menguntungkan dan variasi yang tidak menguntungkan". variasi mengacu pada perbedaan yang ditunjukkan oleh individu spesies dan juga pada keturunan untuk orang tua yang sama. Ada lebih individu yang lahir dari bisa bertahan, sehingga ada perjuangan terus menerus untuk hidup. Individu dengan keuntungan memiliki kesempatan lebih besar untuk bertahan hidup yaitu, kelangsungan hidup lebih besar.
Berikut Tabel 2.1 memberikan daftar ekspresi yang berbeda, yang berada di com- mon dengan evolusi alam dan algoritma genetika.
2.3 Apa Algoritma Genetika?
komputasi evolusi diperkenalkan pada tahun 1960 oleh I. Rechenberg dalam karya "strategi Evolution". Ide ini kemudian dikembangkan oleh penelitian lainnya. Algoritma Genetika (GAs) diciptakan oleh John Holland dan mengembangkan ide ini dalam bukunya "Adaptasi dalam sistem resmi alami dan arti fi" pada tahun 1975. Belanda diusulkan GA sebagai metode heuristik berdasarkan "Survival of the fittest". GA ditemukan sebagai alat yang berguna untuk masalah pencarian dan optimasi.
2.3.1 Ruang Cari
Paling sering yang sedang mencari solusi terbaik dalam fitset tertentu dari solusi. Ruang semua solusi yang layak (himpunan solusi antara yang solusinya diinginkan berada) disebut ruang pencarian.
2.3.2 Algoritma Genetika Dunia
Algoritma genetik mempunyai beberapa fitur penting. Pertama adalah algoritma stokastik; keacakan sebagai peran penting dalam algoritma genetika. Kedua pilihan dan reproduksi perlu prosedur random. Sebuah hal yang sangat penting kedua adalah bahwa algoritma genetika selalu mempertimbangkan populasi solusi. Kekokohan algoritma juga harus disebutkan sebagai sesuatu yang penting untuk keberhasilan algoritma. Kekokohan mengacu pada kemampuan untuk melakukan secara konsisten baik pada berbagai jenis masalah.
Dengan keberhasilan Algoritma Genetika, algoritma lainnya membuat dalam penggunaan pada prinsip yang sama evolusi alami juga telah muncul. strategi evolusi, pemrograman genetik adalah beberapa dari mereka yang sama dari mereka algoritma yang sama.klasifikasi tidak selalu jelas antara algoritma yang berbeda, sehingga untuk menghindari kebingungan, mereka semua berkumpul dalam apa yang disebut evolusi Algoritma.
GAs adalah sesuatu yang layak mencoba ketika segala sesuatu yang lain sebagai gagal atau ketika kita tahu apa-apa dari ruang pencarian. Namun demikian, bahkan ketika teknik khusus seperti itu ada, sering menarik hibridasi mereka dengan GA untuk mungkin mendapatkan beberapa perbaikan. Hal ini penting untuk selalu menjaga sudut pandang obyektif; tidak menganggap GAs yang merupakan obat mujarab untuk menyelesaikan semua masalah optimasi.
2.3.3 Evolusi dan Optimasi
Mekanisme Darwin maka menghasilkan proses optimasi, optimasi hidrodinamik untuk Shesfi dan lain-lain hewan laut, aerodinamis untuk pterodactyls, burung atau kelelawar. pengamatan ini adalah dasar dari algoritma genetika.
2.3.4 Evolusi dan Algoritma Genetika
John Holland, dari University of Michigan mulai karyanya pada algoritma yang genetik pada awal tahun 60-an. Sebuah prestasi pertama adalah penerbitan Adaptasi di Sistem ficial Alam
Ide dasarnya adalah sebagai berikut: kolam genetik dari populasi tertentu yang berpotensi mengandung solusi, atau solusi yang lebih baik, untuk masalah adaptif diberikan. Solusi ini tidak "aktif" karena kombinasi genetik yang mengandalkan dibagi antara beberapa mata pelajaran.
Metode holland sangat efektif karena ia tidak hanya dianggap peran mutasi (mutasi meningkatkan sangat jarang algoritma), tetapi ia juga dimanfaatkan rekombinasi genetik, (crossover): rekombinasi ini, crossover solusi parsial sangat meningkatkan kemampuan algoritma untuk pendekatan, dan akhirnya fi nd, optimal.
Rekombinasi atau reproduksi seksual adalah operator utama untuk evolusi alami. Secara teknis, dibutuhkan dua genotipe dan menghasilkan genotipe baru dengan mencampur gen yang ditemukan di aslinya.
Mutasi adalah cara lain untuk mendapatkan genom baru. Mutasi terdiri dalam mengubah nilai gen. Dalam evolusi alami, mutasi sebagian besar menimbulkan genom non-layak. Sebenarnya mutasi tidak operator sangat sering dalam evolusi alam. Namun demikian, adalah optimasi, sebuah perubahan acak beberapa dapat menjadi cara yang baik untuk mengeksplorasi ruang pencarian cepat.
Menurut Darwinisme, variasi diwariskan ditandai dengan sifat sebagai berikut:
1. Variasi harus menyalin karena pilihan tidak menciptakan langsung apa-apa, tapi mengandaikan populasi besar untuk bekerja pada.
2. Variasi harus skala kecil dalam praktek. Spesies tidak muncul tiba-tiba.
3. Variasi adalah diarahkan. Hal ini juga dikenal sebagai paradigma pembuat jam buta.
2.4 konvensional Optimization dan Teknik Search
Prinsip dasar dari optimasi alokasi yang efisien sumber daya yang langka. Optimasi dapat diterapkan untuk setiap fisik ilmiah atau disiplin rekayasa. Tujuan dari optimasi adalah menemukan sebuah algoritma, yang memecahkan kelas tertentu dari masalah. Pertimbangkan fungsi,
Untuk fungsi di atas, f dapat dipertahankan dengan mengurangi € atau dengan membuat valensi antar dari [x1, xu] besar.
2.4.1 Gradient Berbasis Metode Optimasi Lokal
Untuk membahas berdasarkan gradien-optimasi lokal, mari kita asumsikan fungsi halus obyektif (yaitu, berkelanjutan pertama dan turunan kedua). Fungsi tujuan dinotasikan dengan,
Beberapa metode hanya perlu vektor gradien, namun dalam metode Newton kita membutuhkan Hessian matrix.The pseudo code umum digunakan dalam metode gradien adalah sebagai berikut:
metode gradien ini mencari minimum dan tidak maksimal. Beberapa metode yang berbeda diperoleh berdasarkan rincian algoritma.
The dibahas adalah satu-dimensi optimasi problem.The metode steepest descent memberikan kinerja yang buruk. Akibatnya, metode gradien konjugat dapat digunakan.
2.4.2 Random Search
Pencarian acak adalah metode yang sangat dasar. Ini hanya mengeksplorasi ruang pencarian dengan secara acak memilih solusi dan mengevaluasi fitness mereka. Hal ini cukup strategi cerdas, dan jarang digunakan dengan sendirinya. Namun demikian, metode ini kadang-kadang bernilai sedang diuji.
Pencarian acak memang memiliki kualitas yang menarik beberapa. Namun baik solusi yang diperoleh mungkin, jika tidak optimal satu, dapat selalu ditingkatkan dengan terus menjalankan algoritma pencarian acak untuk cukup lama.
2.4.3 Stochastic BukitClimbing
metode sienfief ada untuk masalah dengan berperilaku baik terus menerus fitness fungsi. Metode ini menggunakan jenis gradien untuk memandu arah pencarian. Stochastic Bukit Climbing adalah metode paling sederhana dari jenis ini. Setiap iterasi terdiri dalam memilih secara acak solusi di lingkungan solusi saat ini dan mempertahankan solusi baru ini hanya jika itu meningkatkan fungsi fi fitness. Stochastic Bukit Climbing menyatu dengan solusi optimal jika fungsi fi fitness dari masalah adalah continuous dan hanya memiliki satu puncak (fungsi unimodal).
2.4.4 Simulated Annealing
Dengan pendinginan, sistem fisik yang kompleks secara alami berkumpul menuju keadaan energi mal mini. Sistem ini bergerak secara acak, tetapi kemungkinan untuk tinggal di tertentu configurasi langsung tergantung pada energi dari sistem dan suhu. hukum Gibbs memberikan probabilitas ini secara resmi:
Dimana E adalah singkatan dari energi, k adalah konstanta Boltzmann dan T adalah temperatur. Pada pertengahan tahun 70-an, Kirlpatrick dengan analogi dari fenomena fisik ditata deskripsi pertama dari anil simulasi.
Seperti pada stochastic mendaki bukit, iterasi dari anil simulasi terdiri dari acak memilih solusi baru di lingkungan solusi yang sebenarnya. Jika fungsi fi fitness dari solusi baru lebih baik dari fungsi fi fitness dari saat ini, solusi baru diterima sebagai solusi saat baru. Jika fungsi fi fitness tidak membaik, solusi baru dipertahankan dengan probabilitas:
Anil simulasi berperilaku seperti metode mendaki bukit tetapi dengan kemungkinan akan menurun untuk menghindari terjebak dioptimal lokal.
2.4.5 simbolik Arti fi cial Intelligence (AI)
Kebanyakan sistem AI simbolis sangat statis. Kebanyakan dari mereka biasanya hanya bisa menyelesaikan satu diberikan spesifik masalah fisik, karena arsitektur mereka dirancang untuk apa pun yang spesifik masalah fi c adalah di tempat pertama.
2.5 Algoritma Genetika Sederhana
Algoritma adalah serangkaian langkah-langkah untuk memecahkan masalah. Sebuah algoritma genetika adalah metode pemecahan masalah yang menggunakan genetika sebagai modelnya pemecahan masalah. Ini adalah teknik pencarian untuk solusi dan perkiraan untuk optimasi dan pencari masalah.Kemudian, algoritma genetika loop melalui proses iterasi untuk membuat tion berevolusi populasi. Setiap iterasi terdiri dari langkah-langkah berikut:
• SELEKSI: Langkah pertama terdiri dalam memilih individu untuk reproduksi. Pemilihan ini dilakukan secara acak dengan probabilitas tergantung pada fi fitness relatif dari individu sehingga yang terbaik sering dipilih untuk reproduksi dari yang miskin.
• REPRODUKSI: Pada langkah kedua, anak yang dibesarkan oleh individu yang dipilih. Untuk menghasilkan kromosom baru, algoritma dapat menggunakan kedua bangsa rekombinan dan mutasi.
• EVALUASI: Lalu fi fitness dari kromosom baru dievaluasi.
• PENGGANTIAN: Selama langkah terakhir, individu dari populasi tua dibunuh dan digantikan oleh yang baru
.
Algoritma ini berhenti ketika populasi konvergen menuju solusi optimal. Algoritma genetika dasar adalah sebagai berikut:
• [mulai] populasi acak genetik n kromosom (solusi yang cocok untuk masalah)
• [Pusat] Evaluasi fi fitness f (x) dari setiap kromosom x dalam populasi
• Buat populasi baru dengan mengulangi langkah-langkah berikut sampai penduduk New selesai
- [Pilihan] pilih dua kromosom induk dari populasi sesuai dengan fi fitness mereka (fi fitness yang lebih baik, kesempatan lebih besar untuk mendapatkan dipilih).
- [Crossover] Dengan probabilitas crossover menyeberang orang tua untuk membentuk keturunan (anak) baru. Jika tidak ada Crossover dilakukan, keturunan adalah salinan dari orang tua.
- [Mutasi] Dengan probabilitas mutasi, mutasi keturunan baru pada setiap lokus (posisi di kromosom)
- [Menerima] Tempatkan anak baru dalam populasi baru.
• [Ganti] Gunakan populasi yang dihasilkan baru untuk jumlah lebih dari algoritma.
• [Test] Jika kondisi akhir adalah puas, berhenti, dan kembali solusi terbaik dalam populasi saat ini.
• [loop] Pergi ke step2 untuk evaluasi fi fitness.
Proses Algoritma genetika dibahas melalui siklus GA pada Gambar. 2.9
Reproduksi adalah proses dimana bahan genetik dalam dua atau lebih orang tua dikombinasikan untuk mendapatkan satu atau lebih keturunan. Sebelum menerapkan GAs penting untuk memahami beberapa pedoman untuk merancang sebuah algoritma pencarian umum yaitu algoritma optimasi global jenis metode optimasi:
1. determinisme: Sebuah pencarian murni deterministik mungkin memiliki varian yang sangat tinggi dalam kualitas solusi karena dapat segera terjebak dalam situasi kasus terburuk dari yang tidak mampu untuk melarikan diri karena determinisme nya. Hal ini dapat dihindari, tetapi merupakan fakta yang terkenal bahwa pengamatan situasi terburuk tidak dijamin menjadi mungkin pada umumnya.
2. nondeterminism: Sebuah metode pencarian stochastic biasanya tidak menderita potensi kasus terburuk "serigala perangkap" fenomena di atas. Oleh karena itu mungkin bahwa metode pencarian harus stokastik, tetapi mungkin juga mengandung sebagian besar determinisme, namun. Pada prinsipnya itu sudah cukup untuk memiliki sebanyak isme nondetermin- untuk dapat menghindari terburuk serigala perangkap.
3. determinisme lokal: Sebuah metode murni stochastic biasanya cukup lambat. Oleh karena itu adalah wajar untuk melakukan sebanyak mungkin yang efisien prediksi deterministik dari arah yang paling menjanjikan dari proses (lokal). Ini disebut mendaki bukit lokal atau pencarian serakah sesuai dengan strategi yang jelas.
Berdasarkan pembahasan sebelumnya, kriteria penting untuk pendekatan GA dapat dirumuskan sebagai diberikan di bawah ini:
- Kelengkapan: Setiap solusi harus memiliki pengkodean
- Non redundansi: Kode dan solusi harus sesuai 12:59
- Tingkat Kesehatan: Setiap kode (dihasilkan oleh operator genetik) harus memiliki solusi yang sesuai
- Karakteristik ketekunan: Offspring harus mewarisi karakteristik yang berguna dari orang tua.
Singkatnya, dasar empat langkah yang digunakan dalam algoritma genetika sederhana untuk memecahkan masalah,
1. Representasi masalah
2. Perhitungan fitness
3. Berbagai variabel dan parameter yang terlibat dalam mengendalikan algoritma
4. Representasi hasil dan cara mengakhiri algoritma
2.6 Perbandingan Algoritma Genetika dengan Teknik Optimasi Lain
Prinsip GAs sederhana: meniru genetika dan seleksi alam oleh program komputer: Parameter dari masalah dikodekan paling alami sebagai struktur DNA seperti linear data, vektor atau string. Kadang-kadang, ketika masalah ini secara alami dua atau tiga dimensi struktur array yang juga sesuai digunakan.Satu set, yang disebut populasi, dari tergantung masalah vektor nilai parameter tersebut diproses oleh GA. Dengan fungsi fitness kita dapat memilih kandidat solusi terbaik dari populasi dan menghapus spesimen yang tidak begitu baik.
Yang menyenangkan ketika membandingkan GAs dengan metode optimasi lain adalah bahwa fungsi fitness bisa apa saja yang dapat dievaluasi oleh komputer atau bahkan sesuatu yang tidak bisa! Dalam kasus terakhir itu mungkin penilaian manusia yang tidak dapat dinyatakan sebagai program renyah, seperti dalam kasus saksi mata, di mana manusia memilih di antara alternatif yang dihasilkan oleh GA.
Jadi, tidak ada de fi nite pembatasan matematika pada sifat dari fungsi fi fitness. Mungkin diskrit, multimodal dll.
Kriteria utama yang digunakan untuk mengklasifikasikan algoritma optimasi adalah sebagai berikut: continuous / diskrit , dibatasi / tak terbatas dan sekuensial / paralel. Ada perbedaan yang jelas antara masalah diskrit dan kontinyu.
2.7 Keuntungan dan Keterbatasan Algoritma Genetika
Keuntungan dari algoritma genetika meliputi,1. Paralelisme
2. Kewajiban
3. ruang Solusi lebih lebar
4. lanskap fi fitness adalah kompleks
5. Mudah untuk menemukan optimum global
6. Masalahnya memiliki multi fungsi tujuan
7. Hanya menggunakan evaluasi fungsi.
8. Mudah dimodifikasi untuk masalah yang berbeda.
9. Menangani fungsi bising dengan baik.
10. Menangani besar, ruang pencarian kurang dipahami dengan mudah
11. Baik untuk masalah multi-modal Mengembalikan suite solusi.
12. Sangat kuat untuk dif-kesulitan dalam evaluasi fungsi tujuan.
13. Mereka tidak memerlukan pengetahuan atau informasi gradien tentang permukaan respon
14. Cacat hadir pada permukaan respon memiliki sedikit efek pada kinerja optimasi keseluruhan
15. Mereka tahan terhadap terjebak dalam optimasi lokal
16. Mereka tampil sangat baik untuk masalah optimasi skala besar
17. Bisa digunakan untuk berbagai macam masalah optimasi
Keterbatasan algoritma genetika meliputi,
1. Masalah mengidentifikasi fi fitness functio
n2. Definisi representasi untuk masalah
3. konvergensi prematur terjadi
4. Masalah memilih berbagai parameter seperti ukuran populasi, tingkat mutasi, menyeberang tingkat, metode seleksi dan kekuatannya.
5. Tidak dapat menggunakan gradien.
6. Tidak bisa dengan mudah memasukkan masalah spesifik informasi c
7. Tidak baik untuk mengidentifikasi optima lokal
8. terminator Tidak efektif.
9. Tidak efektif untuk fungsi unimodal halus
10. Perlu ditambah dengan teknik pencarian lokal.
11. Memiliki kesulitan fi nding optimum global yang tepat
12. Membutuhkan sejumlah besar respon (fi fitness) evaluasi fungsi
13. Con fi gurasi tidak langsung
2,8 Aplikasi Algoritma Genetika
algoritma genetika telah digunakan untuk masalah sulit (seperti masalah-masalah NP-keras), untuk pembelajaran mesin dan juga untuk berkembang program sederhana. Mereka telah juga digunakan untuk beberapa seni, untuk berkembang gambar dan musik. Beberapa aplikasi dari GA adalah sebagai berikut:• dinamik nonlinier sistem-memprediksi, analisis data
• perencanaan Robot lintasan
• program Berkembang LISP (pemrograman genetik)
• Perencanaan Strategi • Menemukan bentuk molekul protein
• TSP dan penjadwalan urutan
• Fungsi untuk menciptakan gambar
• pipa Control-gas, tiang balancing, penggelapan rudal, mengejar
• tata letak Desain-semikonduktor, desain pesawat, keyboard con fi gurasi, jaringan komunikasi
• Penjadwalan-manufaktur, penjadwalan fasilitas, alokasi sumber daya
• Machine Learning-Merancang jaringan saraf, baik arsitektur dan bobot, meningkatkan algoritma kation fi klasi, sistem er dikelompokkan
• desain Signal pengolahan di fi lter
• Kombinatorial Optimization-set covering, bepergian salesman (TSP), penjadwalan urutan, routing, bin packing, pewarnaan graf dan partisi
2.9 Ringkasan
algoritma genetika adalah sistem asli berdasarkan seharusnya fungsi Hidup. Metode ini sangat berbeda dari algoritma optimasi klasik.
1. Penggunaan encoding parameter, bukan parameter themselves.
2. Bekerja pada populasi poin, bukan satu.
3. Gunakan hanya nilai fungsi unik untuk mengoptimalkan, bukan fungsi mereka berasal.
4. Gunakan fungsi transisi probabilistik bukan tambahan lainnya yang determinis.
Sangat penting untuk memahami bahwa fungsi algoritma tersebut tidak menjamin kesuksesan. Masalahnya adalah dalam sistem stochastic dan kolam genetik mungkin terlalu jauh dari solusi, atau misalnya, konvergensi terlalu cepat dapat menghentikan proses evolusi.algoritma ini tetap sangat efisien, dan digunakan dalam medan yang beragam seperti bursa,penjadwalan produksi atau pemrograman robot perakitan di industri otomotif.
0 komentar:
Posting Komentar