Algoritma Genetika
A. Latar Belakang Biologis
Ilmu yang berurusan dengan mekanisme yang bertanggung jawab atas persamaan dan perbedaan dalam suatu spesies disebut Genetika. Kata "genetika" berasal dari Kata Yunani "genesis" yang berarti "tumbuh" atau "menjadi". Ilmu genetika membantu kami untuk membedakan antara faktor keturunan dan variasi serta berupaya menjelaskan kemiripan dan perbedaan karena konsep Algoritma Genetika dan langsung berasal dari keturunan alami, sumber dan perkembangan mereka.
Konsep Algoritma Genetika secara langsung berasal dari evolusi alami. Terminologi utama yang terlibat dalam latar belakang biologis spesies adalah sebagai berikut:
1. Sel
Setiap sel hewan / manusia adalah kompleks dari banyak pabrik “kecil” yang bekerja bersama.
Pusat semua ini adalah inti sel. Informasi genetik terkandung dalam inti sel. Gambar 2.1 menunjukkan anatomi sel hewan dan inti sel.
2. Chromosome
Semua informasi genetik disimpan dalam kromosom. Setiap kromosom adalah membangun Dioxy Ribo Nucleic Acid (DNA). Pada manusia, kromosom ada di bentuk pasangan (23 pasangan ditemukan). Kromosom dibagi menjadi beberapa bagian disebut gen. Gen mengkode sifat-sifat spesies yaitu, karakteristik suatu individu. Ukuran kumpulan gen membantu dalam menentukan keragaman dari individu dalam populasi. Himpunan semua gen dari spesies tertentu adalah
disebut genom. Masing-masing dan setiap gen memiliki posisi unik pada genom yang disebut
tempat. Faktanya, sebagian besar organisme hidup menyimpan genomnya pada beberapa kromosom,
tetapi dalam Genetic Algorithms (GAs), semua gen biasanya disimpan pada yang sama
kromosom. Jadi kromosom dan genom adalah sinonim dengan satu sama lain di
Gas. Gambar 2.2 menunjukkan model kromosom.
3. Genetika
Untuk individu tertentu, seluruh kombinasi gen disebut genotipe. Itu fenotip menggambarkan aspek fisik decoding genotipe untuk menghasilkan fenotip. Satu hal yang menarik dari evolusi adalah bahwa seleksi selalu dilakukan fenotip sedangkan reproduksi menggabungkan kembali genotipe. Demikian morfogenesis memainkan peran kunci antara seleksi dan reproduksi. Dalam bentuk kehidupan yang lebih tinggi, kromosom mengandung dua set gen. Ini dikenal sebagai diploid. Dalam kasus konflik antara dua nilai dari pasangan gen yang sama, yang dominan akan menentukan
fenotip sedangkan yang lain, yang disebut resesif, akan tetap ada dan bisa terjadi diteruskan ke keturunannya. Diploidy memungkinkan keragaman alel yang lebih luas. Ini menyediakan mekanisme memori yang berguna dalam lingkungan yang berubah atau bising. Namun, kebanyakan GA
berkonsentrasi pada kromosom haploid karena mereka jauh lebih mudah dibangun.
Dalam representasi haploid, hanya satu set masing-masing gen disimpan, sehingga proses
menentukan alel mana yang harus dominan dan mana yang harus resesif
dihindari. Gambar 2.3 menunjukkan pengembangan genotipe menjadi fenotipe.
Dalam Mitosis informasi genetik yang sama disalin ke keturunan baru. Tidak ada
Pertukaran informasi. Ini adalah cara normal pertumbuhan struktur multi sel,
seperti organ. Gambar 2.4 menunjukkan bentuk mitosis reproduksi.
5. Seleksi Alam
Asal usul spesies didasarkan pada "Pelestarian variasi yang menguntungkan dan penolakan terhadap variasi yang tidak menguntungkan". Variasi mengacu pada perbedaan yang ditunjukkan oleh
individu dari suatu spesies dan juga oleh keturunan dari orang tua yang sama. Ada
lebih banyak orang yang dilahirkan daripada yang bisa bertahan hidup, sehingga ada perjuangan terus menerus untuk hidup.
Individu dengan keunggulan memiliki peluang lebih besar untuk bertahan hidup yaitu kelangsungan hidup
dari yang terkuat. Misalnya, Jerapah dengan leher panjang bisa mendapatkan makanan dari pohon-pohon tinggi
nah dari pekarangan, kambing sebaliknya, rusa dengan leher kecil hanya mendapat makanan dari
alasan. Akibatnya, seleksi alam memainkan peran utama dalam proses bertahan hidup ini.
Demikianlah berbagai terminologi biologis yang akan digunakan dalam algoritma genetika
dibahas di bagian ini.
Tabel 2.1 berikut ini memberikan daftar ekspresi yang berbeda, yang sama dengan evolusi alami dan algoritma genetika.
B. Apa itu Algoritma Genetika?
Komputasi evolusioner diperkenalkan pada 1960-an oleh I. Rechenberg dalam karya ini
"Strategi evolusi". Gagasan ini kemudian dikembangkan oleh para peneliti lain. Genetik
Algoritma (GAS) ditemukan oleh John Holland dan mengembangkan ide ini dalam bukunya
"Adaptasi dalam sistem alami dan buatan" pada tahun 1975. Holland mengusulkan
GA sebagai metode heuristik berdasarkan “Survival of the fittest”. GA ditemukan sebagai
alat yang berguna untuk masalah pencarian dan optimisasi.
1. Ruang Pencarian
Paling sering seseorang mencari solusi terbaik dalam serangkaian solusi spesifik. Itu
ruang semua solusi yang layak (himpunan solusi di antaranya solusi yang diinginkan berada) disebut ruang pencarian (juga ruang negara). Setiap titik di ruang pencarian mewakili satu kemungkinan solusi. Oleh karena itu setiap solusi yang mungkin dapat dilakukan "ditandai" oleh nilai kebugarannya, tergantung pada definisi masalahnya. Dengan Genetika Algoritma satu mencari solusi terbaik di antara sejumlah solusi yang mungkin diwakili oleh satu titik di ruang pencarian yaitu; GAS digunakan untuk mencari pencarian ruang untuk solusi terbaik, mis. minimum. Kesulitan dalam kemudahan ini adalah lokal minima dan titik awal pencarian (lihat Gambar 2.6).
2. Dunia Algoritma Genetika
Algoritma Genetika memunculkan beberapa fitur penting. Pertama itu adalah stokastik
algoritma; keacakan sebagai peran penting dalam algoritma genetika. Pilihan keduanya
dan reproduksi memerlukan prosedur acak. Poin kedua yang sangat penting adalah itu
algoritma genetika selalu mempertimbangkan populasi solusi. Menyimpan dalam memori
lebih dari satu solusi di setiap iterasi menawarkan banyak keuntungan. Algoritma dapat menggabungkan kembali berbagai solusi untuk mendapatkan yang lebih baik sehingga dapat menggunakan manfaat bermacam-macam Algoritma basis populasi juga sangat setuju untuk paralelisasi. Kekokohan algoritma juga harus disebutkan sebagai sesuatu yang penting
untuk kesuksesan algoritma. Robustness mengacu pada kemampuan untuk melakukan secara konsisten dengan baik pada berbagai jenis masalah. Tidak ada persyaratan khusus pada
masalah sebelum menggunakan GAS, sehingga dapat diterapkan untuk menyelesaikan masalah apa pun. Semua itu fitur menjadikan GA alat pengoptimalan yang sangat kuat.
3. Evolusi dan Optimasi
Kita sekarang 45 juta tahun lalu memeriksa Basilosaurus: Basilosaurus adalah prototipe paus (Gbr. ). Itu sekitar 15 meter panjang untuk 5 ton. Itu masih memiliki kepala dan kaki posterior semi-independen. Dia pindah menggunakan gerakan undulatory dan memburu mangsa kecil. Anggota anteriornya direduksi menjadi sirip kecil dengan artikulasi siku. Pergerakan sedemikian
eleen kental (air) sangat keras dan membutuhkan upaya besar. Orang yang peduli
harus memiliki energi yang cukup untuk bergerak dan mengendalikan lintasannya. Anggota anterior
basilosaurus tidak benar-benar beradaptasi dengan berenang. Untuk mengadaptasinya, sebuah fenomena ganda harus terjadi: pemendekan "lengan" dengan penguncian siku
artikulasi dan ekstensi jari yang akan membentuk struktur dasar
sirip sirip (lihat Gambar ).
Gambar menunjukkan bahwa dua jari lumba-lumba biasa mengalami hipertrofi
merugikan anggota lainnya. Basilikaurus adalah pemburu, dia harus melakukannya
cepat dan tepat. Melalui waktu, subjek muncul dengan jari yang lebih panjang dan pendek
senjata. Mereka bisa bergerak lebih cepat dan lebih tepat daripada sebelumnya, dan karenanya, hidup
lebih lama dan memiliki banyak keturunan
Karenanya, mekanisme Darwin menghasilkan proses optimisasi, optimisasi hidrodinamik untuk ikan dan hewan laut lainnya, aerodinamik untuk pterodactyl, burung atau kelelawar. Pengamatan ini adalah dasar dari algoritma genetika.
4. Evolusi dan Algoritma Genetika
John Holland, dari University of Michigan memulai penelitiannya pada algoritma genetika pada awal tahun 60an. Prestasi pertama adalah publikasi Adaptasi dalam Sistem Alam dan Artifisial pada tahun 1975. Belanda memiliki tujuan ganda: untuk meningkatkan pemahaman proses adaptasi alami, dan untuk merancang sistem buatan yang memiliki sifat yang mirip dengan sistem alami.
Gagasan dasarnya adalah sebagai berikut: kumpulan genetis dari populasi tertentu berpotensi mengandung pemecahan, atau pemecahan huruf, untuk diadaptasi untuk mengatasi masalah. Pembubaran ini tidak "aktif" karena kombinasi genetik yang menjadi sandarannya dibagi antara beberapa subjek. Hanya asosiasi genome yang berbeda yang dapat mengarah ke solusi. Secara sederhana, kita dapat dengan contoh mempertimbangkan bahwa pemendekan cakar dan perluasan jari-jari basilosaurus kita dikendalikan oleh 2 "gen". Tidak ada subjek yang memiliki genom seperti itu, tetapi selama reproduksi dan crossover, kombinasi genetik baru dapat terjadi, pada akhirnya, sebagai subjek dari "goodgene" dari kedua orang tua: cakarnya sekarang menjadi lebih rata.
C. Optimasi Konvensional dan Teknik Pencarian
Untuk fungsi di atas, f dapat dipertahankan dengan menurunkan € atau dengan membuat interval [xl, x u] besar. Dengan demikian tugas yang sulit dapat dibuat lebih mudah. Oleh karena itu, seseorang dapat memecahkan masalah optimasi dengan menggabungkan daya kreativitas dan kekuatan pemrosesan komputer.
1. Metode Optimalisasi Lokal Berbasis Gradien
Ketika fungsi obyektif berjalan lancar dan seseorang membutuhkan optimalisasi lokal yang efisien, lebih baik menggunakan metode optimasi berbasis gradien atau Hessian. Kinerja dan keandalan berbagai metode gradien sangat bervariasi. Untuk membahas optimasi lokal berbasis gradien, mari kita asumsikan fungsi tujuan yang halus (yaitu, turunan pertama dan kedua yang berkelanjutan). Fungsi obyektif dilambangkan dengan,
Derivatif pertama terdapat pada vektor gradien∇ f (x)
Detektif-konduktif dari fungsi obyektif ini tertahan dalam matriks H (H).
Beberapa metode hanya membutuhkan vektor gradien, tetapi dalam metode Newton kita membutuhkan matriks Hessian.
2. Pencarian Acak
Pencarian acak adalah metode yang sangat mendasar. Itu hanya mengeksplorasi ruang pencarian dengan memilih secara acak solusi dan mengevaluasi kecocokan mereka. Analisis ini adalah strategi intelijen, dan jarang digunakan dengan sendirinya. Meskipun demikian, metode ini terkadang layak untuk diuji. Tidak perlu banyak upaya untuk mengimplementasikannya, dan sejumlah evaluasi penting dapat dilakukan dengan cukup cepat. Untuk masalah baru yang belum terselesaikan, akan bermanfaat untuk membandingkan hasil dari algoritma yang lebih maju dengan yang diperoleh hanya dengan pencarian acak untuk jumlah evaluasi yang sama. Kejutan-kejutan kejam mungkin muncul ketika membandingkan misalnya, genetik dengan riset. Bagus untuk diingat bahwa efisiensi GA sangat tergantung pada pengkodean yang konsisten dan operator reproduksi yang relevan. Membangun algoritma genetika, yang melakukan tidak lebih dari pencarian acak terjadi lebih sering daripada yang dapat kita harapkan. Jika operator reproduksi hanya menghasilkan solusi acak baru tanpa tautan konkret ke solusi yang dipilih dari generasi terakhir, algoritme genetik hanya melakukan hal-hal lain yang diperlukan sebagai pencarian acak.
3. Panjat Bukit Stochastic
Ada metode yang efisien untuk masalah dengan fungsi kelanjutan yang berperilaku baik. Metode ini menggunakan metode yang tidak sesuai untuk diarahkan pada penelitian. Stochastic Hill Climbing adalah metode paling sederhana dari jenis-jenis ini. Setiap iterasi terdiri dalam memilih secara acak solusinyauntukmenempatkankursusdisolusidanmenahan solusi baru ini hanya jika ia meningkatkan fungsi kebugaran. Stochastic Hill Climbing melakukan konversi dengan optimal jika penyelesaian fungsi dari masalah adalah terus menerus dan hanya memiliki satu puncak (tidak ada fungsi).
4. Simulasi Annealing
Simulasi Annealing pada awalnya diilhami oleh pembentukan kristal selama pendinginan, yaitu fenomena pendinginan fisik. Seperti yang sudah lama ditemukan oleh pandai besi zaman besi, semakin lambat pendinginannya, semakin sempurna kristalnya terbentuk. Dengan pendinginan, sistem fisik yang kompleks secara alami bertemu menuju keadaan energi minimal. Sistem bergerak secara acak, tetapi probabilitas untuk tetap dalam konfigurasi tertentu tergantung langsung pada energi sistem dan pada suhunya. Hukum Gibbs memberikan probabilitas ini secara formal:
Seperti dalam mendaki bukit stokastik, iterasi dari anil yang disimulasikan terdiri dari secara acak memilih solusi baru di sekitar solusi aktual. Jika fungsi kebugaran dari solusi baru lebih baik daripada fungsi kebugaran dari solusi saat ini, solusi baru diterima sebagai solusi baru saat ini. Jika fungsi kebugaran tidak ditingkatkan, solusi baru dipertahankan dengan probabilitas:
5. Kecerdasan Artifisial Simbolik (AI)
Sebagian besar sistem AI simbolik sangat statis. Kebanyakan dari mereka biasanya hanya dapat menyelesaikan satu masalah tertentu karena arsitektur mereka dirancang untuk apa pun masalah spesifik itu di tempat pertama. Jadi, jika masalah yang diberikan entah bagaimana harus diubah, sistem ini dapat mengalami kesulitan beradaptasi dengan mereka, karena algoritma yang awalnya akan tiba dalam solusi mungkin salah atau kurang efisien. Algoritma genetika (atau GA) diciptakan untuk mengatasi masalah ini. Mereka pada dasarnya adalah algoritma yang didasarkan pada evolusi biologis alami. Arsitektur sistem yang menerapkan algoritma genetika (atau GA) lebih mampu beradaptasi dengan berbagai masalah.
D. Algoritma Genetika Sederhana
Algoritma adalah serangkaian langkah untuk memecahkan masalah. Algoritma genetika adalah metode pemecahan masalah yang menggunakan genetika sebagai model penyelesaian masalahnya. Ini adalah teknik pencarian untuk menemukan solusi perkiraan untuk masalah optimasi dan pencarian.
Pada dasarnya, masalah optimasi terlihat sangat sederhana. Orang tahu bentuk dari semua solusi yang mungkin sesuai dengan pertanyaan spesifik. Himpunan semua solusi yang memenuhi formulir ini merupakan ruang pencarian. Masalahnya adalah menemukan solusi yang sesuai dengan yang terbaik, yaitu solusi dengan hasil terbanyak, dari semua solusi yang mungkin.
GA menangani populasi kemungkinan solusi. Setiap solusi diwakili melalui kromosom, yang hanya merupakan representasi abstrak. Pengodean semua solusi yang mungkin menjadi kromosom adalah bagian pertama, tetapi tentu saja bukan yang paling mudah dari Algoritma Genetika.
Kemudian, algoritma genetika mengulangi proses iterasi untuk membuat populasi berevolusi. Setiap iterasi terdiri dari langkah-langkah berikut:
• PILIHAN: Langkah pertama terdiri dalam memilih individu untuk reproduksi. Seleksi ini dilakukan secara acak dengan probabilitas tergantung pada kecukupan relatif individu sehingga yang terbaik sering dipilih untuk reproduksi daripada yang miskin.
• REPRODUKSI: Pada langkah kedua, keturunan dibesarkan oleh individu yang dipilih. Untuk menghasilkan kromosom baru, algoritma dapat menggunakan rekombinasi dan mutasi.
• EVALUASI: Lalu kesesuaian kromosom baru dievaluasi.
• PENGGANTIAN: Selama langkah terakhir, orang-orang dari populasi lama terbunuh dan digantikan oleh yang baru.
Algoritma dihentikan ketika populasi bertemu ke solusi optimal. Algoritma genetik dasar adalah sebagai berikut:
• [mulai] Populasi acak genetik kromosom n (solusi yang sesuai untuk masalah ini)
• [Kebugaran] Mengevaluasi kecukupan f (x) dari setiap kromosom dalam populasi
• Populasi baru] Buat populasi baru dengan mengulangi langkah-langkah berikut hingga populasi baru lengkap
- [seleksi] pilih dua kromosom induk dari suatu populasi sesuai dengan kecocokan mereka (semakin baik kecocokan, semakin besar peluang untuk dipilih).
- [crossover] Dengan probabilitas crossover, silangkan orang tua untuk membentuk keturunan baru (anak-anak). Jika tidak ada crossover yang dilakukan, keturunan adalah salinan tepat dari orang tua.
- [Mutasi] Dengan probabilitas mutasi, bermutasi keturunan baru di setiap lokus (posisi dalam kromosom)
- [Menerima] Tempatkan keturunan baru pada populasi baru.
• [Ganti] Gunakan populasi baru yang dihasilkan untuk penjumlahan lebih lanjut dari algoritma.
• [Tes] Jika kondisi akhir terpenuhi, hentikan, dan kembalikan solusi terbaik dalam populasi saat ini.
• [Loop] Lanjutkan ke langkah2 untuk evaluasi kebugaran.
E. Perbandingan Algoritma Genetika dengan Teknik Optimasi Lainnya
Prinsip prinsip sederhana: meniru genetika dan seleksi alam oleh program komputer: Parameter masalah dikodekan paling alami sebagai struktur data linear seperti DNA, vektor, atau string. Kadang-kadang, ketika masalahnya secara alami dua atau tiga dimensi juga struktur array yang sesuai digunakan.
Algoritma genetika berbeda dari teknik optimasi konvensional dengan cara berikut:
1. GA beroperasi dengan versi kode dari parameter masalah daripada parameter itu sendiri yaitu, GA bekerja dengan pengkodean set solusi dan bukan dengan solusi itu sendiri.
2. Hampir semua teknik optimisasi konvensional mencari dari satu titik tetapi GAS selalu beroperasi pada seluruh titik populasi (string) yaitu, GA menggunakan populasi solusi daripada solusi tunggal untuk pencarian. Ini memainkan peran utama pada kekokohan algoritma genetika. Ini meningkatkan peluang untuk mencapai global optimal dan juga membantu dalam menghindari titik stasioner lokal. 3. GA menggunakan fungsi kebugaran untuk evaluasi daripada turunan. Akibatnya, mereka dapat diterapkan untuk segala jenis masalah optimasi kontinu atau diskrit. Titik kunci yang harus dilakukan di sini adalah untuk mengidentifikasi dan menentukan fungsi pengkodean yang bermakna.
4. GAs dapat menggunakan transisi kestabilan yang berlaku sementara metode konvensional untuk optimasi berkelanjutan menerapkan transisi deterministik beroperasi yaitu, GAS tidak menggunakan aturan deterministik.
F. Keuntungan dan Keterbatasan Algoritma Genetika
1. Paralelisme
2. Pertanggungjawaban
3. Ruang solusi lebih luas
4. Lansekap kecekatan rumit
5. Mudah ditemukan secara global optimal
6. Masalahnya memiliki fungsi multi objektif
7. Hanya menggunakan evaluasi fungsi.
8. Mudah dimodifikasi untuk masalah yang berbeda.
9. Menangani fungsi bising dengan baik.
10. Menangani ruang penelitian yang besar dan kurang dipahami dengan baik
11. Baik untuk masalah multi-modal Mengembalikan serangkaian solusi.
12. Sangat kuat untuk kesulitan dalam evaluasi fungsi tujuan.
13. Mereka tidak memerlukan pengetahuan atau informasi gradien mengenai permukaan respons
14. Diskontinuitas yang ada pada permukaan respons memiliki sedikit efek pada kinerja pengoptimalan keseluruhan
15. Mereka tahan untuk terjebak di dalam optima lokal.
16. Mereka berkinerja sangat baik untuk masalah optimasi skala besar
17. Dapat digunakan untuk berbagai masalah optimasi
G. Aplikasi Algoritma Genetika
• Sistem nonlineardinamik – memprediksi, analisis data
• Perencanaan lintasan robot
• Program EvolvingLISP (pemrograman genetik)
• Perencanaan strategi
• Menemukan bentuk molekul protein
• Penjadwalan TSP dan urutan
• Fungsi untuk membuat gambar
• Kontrol-pipa gas, keseimbangan tiang, penghindaran rudal, pengejaran
• Desain-semikonduktor tata letak, desain pesawat terbang, konfigurasi keyboard, jaringan komunikasi
• Penjadwalan-manufaktur, penjadwalan fasilitas, alokasi sumber daya
• Pembelajaran Mesin-Merancang jaringan saraf, baik arsitektur dan bobot, meningkatkan algoritma klasifikasi, sistem klasifikasi Pengoptimalan - penutup yang diatur, salesman keliling (TSP), penjadwalan urutan, perutean, pengemasan bin, pewarnaan grafik dan partisi
Tidak ada komentar:
Posting Komentar