Operation Research and Analysis

Mengenal Istilah Feasible Region Dalam Optimasi Matematis

Dipublikasikan oleh Dias Perdana Putra pada 20 Februari 2024


Feasible Region

Dalam optimasi matematis, wilayah, himpunan, ruang pencarian, atau ruang solusi yang layak adalah himpunan semua titik yang mungkin (kumpulan nilai dari variabel yang dipilih) dari suatu masalah optimasi yang memenuhi batasan masalah tersebut. , yang mungkin mengandung kesenjangan, persamaan dan ketidaksetaraan. pembatasan bilangan bulat. Ini adalah rangkaian solusi pertama yang mungkin untuk mengatasi masalah tersebut sebelum mempersempit kelompok kandidat.

Misalnya, pertimbangkan masalah meminimalkan fungsi {\displaystyle x^{2}+y^{4}} sehubungan dengan variabel x dan y,, tunduk pada{\displaystyle 1\leq x\leq 10} dan {\displaystyle 5\leq y\leq 12.\,}Di sini himpunan layak adalah himpunan pasangan (x,y) yang nilai x paling sedikit 1 dan paling banyak 10 dan nilai y paling sedikit 5 dan paling banyak 12. Himpunan masalah yang layak terpisah dari fungsi tujuan, yang menyatakan kriteria yang akan dioptimalkan dan yang dalam contoh di atas adalah {\displaystyle x^{2}+y^{4}.}

Dalam banyak permasalahan, himpunan layak mencerminkan batasan bahwa satu atau lebih variabel tidak boleh negatif. Untuk permasalahan pemrograman yang hanya menggunakan bilangan bulat, himpunan bilangan bulat (atau bagiannya) adalah himpunan yang diperbolehkan. Dalam permasalahan program linier, himpunan layak adalah politop cembung: wilayah ruang multidimensi yang batasnya dibentuk oleh bidang hiper dan simpulnya adalah simpul.

Kepuasan kendala adalah proses menemukan titik di wilayah yang layak.

Daerah fisibel tertutup dari masalah program linier dengan tiga variabel adalah polihedron cembung.

Himpunan layak cembung

Dalam masalah pemrograman linier, serangkaian kendala linier menghasilkan wilayah layak cembung dari nilai-nilai yang mungkin untuk variabel-variabel tersebut. Dalam kasus dua variabel daerah ini berbentuk poligon sederhana cembung.

Himpunan layak cembung adalah himpunan yang ruas garis yang menghubungkan dua titik layak hanya melalui titik layak lainnya dan tidak melalui suatu titik di luar himpunan layak tersebut. Himpunan layak cembung muncul dalam banyak jenis masalah, termasuk masalah program linier, dan sangat menarik karena masalah dengan fungsi tujuan konveks yang dimaksimalkan umumnya lebih mudah diselesaikan jika ada solusi cembung. set yang diizinkan, dan setiap maksimum lokal juga merupakan maksimum global.

Tidak ada set yang layak

Jika kendala dari masalah optimasi saling bertentangan, tidak ada titik yang memenuhi semua kendala dan dengan demikian wilayah yang layak adalah himpunan nol. Dalam hal ini masalah tidak memiliki solusi dan dikatakan tidak layak.

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan layak terbatas dan tidak terbatas

Himpunan layak terbatas (atas) dan himpunan layak tak terbatas (bawah). Set di bagian bawah berlanjut selamanya ke arah kanan.

Himpunan yang dapat diwujudkan bisa terbatas atau tidak terbatas. Misalnya, himpunan nilai realisasi yang ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0} tidak terhingga karena tidak ada batasan jarak yang dapat ditempuh dalam arah tertentu selama berada dalam rentang nilai realisasi tetap. Sebaliknya, himpunan kemungkinan yang dibentuk oleh himpunan batasan {x ≥ 0, y ≥ 0, x + 2y ≤ 4} adalah terbatas karena amplitudo pergerakan ke segala arah dibatasi oleh batasan tersebut.

Untuk masalah program linier dengan n variabel, kondisi yang diperlukan tetapi tidak cukup untuk membatasi himpunan kemungkinan adalah jumlah batasan paling sedikit n + 1 (seperti yang ditunjukkan pada contoh di atas).

Ketika himpunan kemungkinan tidak terbatas, optimalitas mungkin terjadi atau tidak tergantung pada spesifikasi fungsi tujuan.Misalnya, jika wilayah layak ditentukan oleh himpunan batasan {x ≥ 0, y ≥ 0}, maka permasalahan pemaksimalan x + y adalah suboptimal karena setiap solusi yang mungkin dapat diperbaiki dengan meningkatkan x atau y; Namun jika permasalahannya meminimalkan x + y, maka terdapat permasalahan optimal (terutama pada (x, y) = (0, 0)).

Solusi kandidat

Dalam optimasi dan cabang matematika lainnya, serta dalam algoritma pencarian (cabang ilmu komputer), solusi kandidat adalah anggota dari himpunan solusi yang mungkin dalam domain yang mungkin dari suatu masalah tertentu. Solusi kandidat tidak harus berupa solusi yang mungkin atau masuk akal terhadap suatu masalah, namun hanya solusi yang memenuhi semua batasan; yaitu, dalam serangkaian solusi yang mungkin. Algoritma untuk menyelesaikan berbagai jenis masalah optimasi sering kali mereduksi himpunankemungkinan solusi menjadi subkumpulan solusi layak yang poin-poinnya tetap menjadi solusi layak, sementara solusi lain yang mungkin kemudian dikeluarkan sebagai kandidat.

Ruang semua kandidat solusi sebelum mengecualikan titik layak disebut wilayah layak, himpunan layak, ruang pencarian, atau ruang solusi. Ini adalah himpunan semua solusi yang mungkin yang memenuhi kondisi batas masalah. Kepuasan Kendala adalah proses menemukan titik-titik dalam suatu himpunan yang mungkin.

Algoritma genetika

Dalam kasus algoritma genetik thm, solusi kandidat adalah individu dalam populasi yang dikembangkan oleh algoritma.

Kalkulus

Dalam kalkulus, pencarian solusi optimal dilakukan dengan menggunakan uji turunan pertama: turunan pertama dari fungsi yang dioptimalkan ditetapkan sama dengan nol, dan nilai apa pun dari variabel terpilih yang memenuhi persamaan ini diperlakukan sebagai kandidat solusi (sementara mereka yang tidak dikecualikan dari daftar peringkat). Solusi potensial mungkin bukan solusi aktual dalam beberapa hal. Pertama, ini mungkin merupakan titik terendah ketika bertujuan untuk mencapai titik tertinggi (atau sebaliknya), dan kedua, mungkin tidak memberikan titik terendah atau tertinggi pada, melainkan sebuah pelana atau titik balik ketika ada jeda sementara dalam pertumbuhan lokal. . Jika tidak, fungsinya akan hilang. Solusi kandidat tersebut dapat dikecualikan dengan uji turunan kedua, yang pemenuhannya cukup untuk membuat solusi kandidat setidaknya optimal secara lokal.Ketiga, solusi potensial mungkin optimal secara lokal namun tidak optimal secara global.

Dalam mengambil antiturunan dari monomial bentuk x^{n}, solusi kandidat menggunakan rumus kuadratur Cavalieri adalah {\displaystyle {\tfrac {1}{n+1}}x^{n+1}+C.} Kandidat solusi ini sebenarnya benar kecuali jika {\displaystyle n=-1.}

Pemrograman linier

Serangkaian kendala pemrograman linier pada dua variabel menghasilkan wilayah nilai yang mungkin untuk variabel tersebut. Masalah dua variabel yang dapat diselesaikan akan memiliki wilayah layak dalam bentuk poligon sederhana cembung jika dibatasi. Dalam algoritma yang menguji titik-titik yang layak secara berurutan, setiap titik yang diuji pada gilirannya merupakan solusi kandidat.

Dalam metode simpleks penyelesaian masalah program linier, sebuah simpul dari politop yang layak dipilih sebagai kandidat solusi awal dan diuji optimalitasnya; Jika ditolak sebagai titik optimal, simpul-simpul tetangga dianggap sebagai kandidat solusi berikutnya. Proses ini berlanjut hingga solusi yang diusulkan dianggap optimal.

Disadur dari : https://en.wikipedia.org/wiki/Feasible_region#Candidate_solution

Selengkapnya
Mengenal Istilah Feasible Region  Dalam Optimasi Matematis

Operation Research and Analysis

Mengenal Lebih Jauh Optimasi kawanan partikel

Dipublikasikan oleh Dias Perdana Putra pada 20 Februari 2024


Optimasi kawanan partikel

Dalam ilmu komputer, optimasi gerombolan partikel (PSO) adalah metode komputasi yang bertujuan untuk meningkatkan kandidat solusi secara berulang dengan mempertimbangkan ukuran kualitas tertentu. Metode ini memecahkan masalah dengan memanipulasi populasi kandidat solusi, yang disebut partikel, dan memindahkan partikel-partikel tersebut dalam ruang pencarian berdasarkan rumus matematika sederhana yang menggambarkan posisi dan kecepatan partikel. Pergerakan setiap partikel dipengaruhi oleh posisi lokalyang paling terkenal, namun juga diarahkan ke posisi paling terkenal di ruang pencarian, yang diperbarui saat partikel lain menemukan posisi yang lebih baik. Tujuannya adalah untuk memimpin kelompok menuju solusi terbaik.

PSO awalnya dikaitkan dengan Kennedy, Eberhart dan Shi dan pada awalnya dimaksudkan untuk mensimulasikan perilaku sosial, mewakili pergerakan organisme dalam kawanan burung atau gerombolan ikan.Algoritma tersebut kemudian disederhanakan dan diamati untuk melakukan optimasi. Buku Kennedy dan Eberhart menjelaskan banyak aspek filosofis PSO dan badan intelijen mafia. Poli melakukan survei komprehensif terhadap permintaan PSO. Baru-baru ini, Bonyadi dan Michalewicz menerbitkan tinjauan komprehensif karya teoretis dan eksperimental tentang PSO.

PSO bersifat metaheuristik karena membuat sedikit atau tidak ada asumsi mengenai masalah yang sedang dioptimalkan dan dapat mencari solusi yang mungkin dalam ruang yang sangat luas. Selain itu, PSO tidak menggunakan gradien dari masalah yang sedang dioptimalkan, sehingga masalah optimasi tidak perlu dapat dibedakan, seperti yang disyaratkan oleh metode optimasi klasik seperti metode penurunan gradien dan metode quasi-Newton. Namun perlu diperhatikan bahwa metaheuristik seperti PSO tidak menjamin akan ditemukannya solusi optimal.

Pemlihan Parameter

Pemilihan parameter PSO mempunyai pengaruh yang signifikan terhadap kinerja optimasi. Oleh karena itu, penelitian tentang pemilihan parameter PSO yang mencapai kinerja optimal menjadi fokus utama. Untuk menghindari divergensi (“ledakan”), bobot inersia harus kurang dari 1. Dua parameter lainnya dapat diturunkan dengan menggunakan pendekatan restriktif atau dipilih secara bebas, namun analisis menyarankan wilayah konvergensi untuk membatasinya pada nilai-nilai tipikal. berada dalam kisaran [1,3].Parameter PSO juga dapat dioptimalkan menggunakan pengoptimal overlay lainnya, sebuah konsep yang dikenal sebagai meta-optimasi, atau bahkan disempurnakan selama optimasi, misalnya dengan menggunakan logika fuzzy.Pemilihan parameter PSO juga dapat disesuaikan untuk skenario optimasi yang berbeda.

Lingkungan dan Topologi

Topologi gerombolan mendefinisikan subset partikel yang dapat bertukar informasi dengan setiap partikel. Versi dasar dari algoritma ini menggunakan topologi global sebagai struktur komunikasi cluster. Topologi ini memungkinkan semua partikel untuk berkomunikasi dengan partikel lainnya, sehingga seluruh gerombolan berbagi posisi terbaik yang sama (g) dari satu partikel. Namun, pendekatan ini dapat mengakibatkan kawanan ternak terjebak dalam kondisi minimum lokal. Oleh karena itu,topologi berbeda digunakan untuk mengontrol aliran informasi antar partikel.

Misalnya, dalam topologi lokal, sebuah partikel hanya berbagi informasi dengan subset partikel, di mana subset tersebut adalah subset geometris, seperti "m partikel terdekat", atau subset sosial, yaitu sekelompok partikel yang tidak bergantung pada semua jarak.Dalam kasus seperti ini, varian PSO dianggap yang terbaik secara lokal (dibandingkan dengan varian global dari PSO dasar).Topologi cluster yang umum digunakan adalah ring dimana setiap partikel hanya memiliki dua tetangga, namun terdapat banyak partikel lain di dalam cluster. Topologi belum tentu statis dan upaya telah dilakukan untuk menciptakan topologi adaptif seperti SPSO, APSO, Stochastic Star, TRIBES, Cyber ​​​​​​Swarm dan C-PSO.Dengan menggunakan topologi ring, PSO dapat mencapai paralelisme pada tingkat generasi, sehingga secara signifikan meningkatkan kecepatan evolusi.

Cara Kerja Bagian Dalam

Cara kerja algoritma PSO memiliki pemikiran yang berbeda tentang mengapa dan bagaimana hal itu dapat dioptimalkan.Pandangan umum di kalangan peneliti adalah bahwa perilaku gerombolan bervariasi antara eksplorasi, yang melibatkan pencarian di wilayah ruang pencarian yang lebih luas, dan eksploitasi, yang merupakan pencarian berorientasi lokal untuk mendapatkan titik optimal terdekat (mungkin lokal).

Aliran pemikiran ini telah menjadi konsep umum sejak awal PSO. Aliran pemikiran ini berpendapat bahwa algoritma PSO dan parameternya harus dipilih sedemikian rupa sehingga dapat menyeimbangkan eksplorasi dan eksploitasi untuk menghindari konvergensi dini ke optimal lokal sekaligus memastikan tingkat konvergensi yang baik. Keyakinan ini menjadi dasar dari banyak varian PSO.Sebaliknya, aliran pemikiran lain berfokus pada pemahaman perilaku gerombolan PSO dan bagaimana pengaruhnya terhadap kinerja pengoptimalan aktual, khususnya untuk ruang pencarian berdimensi lebih tinggi dan masalah pengoptimalan yang dapat terputus-putus, berisik, dan bervariasi terhadap waktu. Aliran pemikiran ini mencari algoritma dan parameter PSO yang berkinerja baik dalam konteks eksplorasi dan eksploitasi, terlepas dari interpretasi perilaku kawanan. Studi-studi ini telah mengarah pada penyederhanaan algoritma PSO.

Konvergensi

Dalam konteks OSP, konvergensi memiliki dua arti utama. Pertama, konvergensi himpunan solusi terjadi ketika semua partikel berkumpul pada suatu titik di ruang pencarian, yang mungkin optimal atau tidak. Analisis konvergensi urutan solusi telah memberikan pedoman untuk memilih parameter PSO untuk menghindari divergensi kawanan partikel. Meskipun ada kritik terhadap penyederhanaan analisis yang berlebihan, penelitian menunjukkan bahwa penyederhanaan tersebut tidak berdampak pada batas konvergensi.Kedua, konvergensi menuju optimal lokal terjadi ketika posisi terbaik atau paling terkenal dari kawanan mendekati permasalahan optimal lokal tanpa mempertimbangkan perilaku kawanan secara keseluruhan.

Analisis konvergensi terhadap optimum lokal menunjukkan bahwa PSO memerlukan modifikasi tertentu untuk memastikan ditemukannya optimum lokal. Meskipun penentuan kemampuan konvergensi masih bergantung pada hasil empiris, upaya sedang dilakukan untuk mengembangkan strategi “pembelajaran ortogonal” untuk meningkatkan kinerja PSO secara keseluruhan. Tujuan dari strategi ini adalah untuk mendorong konvergensi global yang lebih cepat, solusi berkualitas lebih tinggi, dan ketahanan yang lebih besar. Namun,penelitian ini tidak memberikan bukti teoretis apa pun yang mendukung klaim tersebut.

Mekanisme Adaptif

Tanpa memerlukan keseimbangan antara konvergensi (“eksploitasi”) dan divergensi (“eksplorasi”), mekanisme adaptif dapat diterapkan. Optimasi kawanan partikel adaptif (APSO) memberikan efisiensi pencarian yang lebih baik daripada PSO standar. APSO dapat melakukan pencarian global di seluruh ruang pencarian dengan kecepatan konvergensi yang lebih cepat, memungkinkan kontrol otomatis terhadap bobot inersia, koefisien percepatan, dan parameter algoritmik lainnya pada waktu proses.ini sekaligus meningkatkan efektivitas dan efisiensi pencarian. Selain itu, APSO juga dapat bertindak berdasarkan partikel terbaik global untuk meninggalkan optimal lokal.Meskipun APSO memperkenalkan parameter algoritme baru, tidak diperlukan kompleksitas desain atau implementasi tambahan.Selain itu, PSO dapat secara efisien mengatasi masalah optimasi komputasi intensif dengan memanfaatkan mekanisme evaluasi kesesuaian skala-adaptif.

Varian

Banyak varian bahkan dari algoritma PSO dasar yang dimungkinkan. Misalnya, ada beberapa metode untuk menginisialisasi partikel dan kecepatan, seperti memulai dari kecepatan nol, serta berbagai pendekatan untuk buffering kecepatan, memperbarui pi dan g hanya setelah seluruh gerombolan diperbarui, dan seterusnya. Beberapa pilihan ini dan dampaknya terhadap kinerja telah dibahas dalam literatur.

Peneliti terkemuka telah mengembangkan serangkaian implementasi standar sebagai dasar untuk menguji kinerja teknik peningkatan sekaligus memperkenalkan PSO ke komunitas pengoptimalan yang lebih luas. Keberadaan standar algoritme yang terkenal dan didefinisikan secara ketat memberikan titik perbandingan berharga yang dapat digunakan di seluruh penelitian untuk menguji kemajuan baru dengan lebih baik.Salah satu standar terbaru adalah Standar PSO 2011 (SPSO-2011).

Hibridisasi

Untuk meningkatkan kinerja pengoptimalan, varian PSO baru dan lebih canggih terus diperkenalkan. Terdapat tren tertentu dalam penelitian ini, termasuk pengembangan metode optimasi hybrid yang menggabungkan PSO dengan pengoptimal lainnya. Contoh pendekatan ini antara lain menggabungkan PSO dengan optimasi berbasis biogeografi dan mengintegrasikan metode pembelajaran yang efektif. Tujuan pengembangan varian ini adalah untuk mencapai peningkatan kinerja lebih lanjut dalam proses optimasi dengan menggabungkan keunggulan PSO dengan sifat positif metode optimasi lainnya. Pendekatan ini membuka peluang eksplorasi dan penggunaan yang lebih efisien dalam bidang pencarian solusi.

Mengurangi Kovergensi Dini

Tren penelitian lainnya adalah upaya untuk mengurangi konvergensi dini, yang mengindikasikan stagnasi optimasi. Beberapa pendekatan yang digunakan antara lain membalikkan atau menghentikan pergerakan partikel PSO. Selain itu, strategi lain untuk mengatasi konvergensi prematur adalah dengan menggunakan multiple-swarm (multi-swarm optimizer). Pendekatan multi-swarm juga dapat digunakan untuk mengimplementasikan optimasi multi-tujuan. Selain itu, terdapat kemajuan dalam penyesuaian parameter perilakuPSO selama proses optimasi.Semua ini merupakan upaya untuk meningkatkan ketahanan algoritme terhadap konvergensi dini dan meningkatkan kinerja pengoptimalan pada masalah yang kompleks dan dinamis.

Penyederhanaan

Aliran pemikiran lainnya adalah bahwa PSO harus disederhanakan sebanyak mungkin tanpa mengorbankan kinerjanya, sebuah konsep yang sering disebut sebagai “Occam's Razor.” Kennedy awalnya mengusulkan penyederhanaan PSO, dan penelitian selanjutnya menunjukkan bahwa menyederhanakan PSO meningkatkan kinerja pengoptimalan, mempermudah penyesuaian parameter, dan menjaga konsistensi kinerja di berbagai masalah pengoptimalan.

Argumen untuk menyederhanakan PSO mencakup keyakinan bahwa efektivitas metaheuristik hanya dapat ditunjukkan secara empiris melalui eksperimen komputasi pada sejumlah masalah optimasi yang terbatas. Sulit untuk membuktikan bahwa metaheuristik seperti PSO benar, sehingga meningkatkan risiko kesalahan dalam deskripsi dan implementasinya. Misalnya, varian algoritma genetika menunjukkan potensi besar tetapi kemudian ditemukan cacat karena optimasi pencariannya bias terhadapnilai serupa untuk berbagai dimensi dalam ruang pencarian.Penyederhanaan PSO juga berlaku untuk inisialisasi cepat. Variasi PSO Bare Bones yang diusulkan oleh James Kennedy pada tahun 2003 tidak memerlukan penggunaan kecepatan sama sekali. Varian lain yang lebih sederhana adalah Accelerated Particle Swarm Optimization (APSO), yang juga tidak memerlukan kecepatan dan dapat mempercepat konvergensi di banyak aplikasi. Kode demo APSO sederhana tersedia.

Pengoptimalan Multi-Tujuan

PSO juga telah berhasil diterapkan pada masalah multiobjektif dimana perbandingan fungsi objektif memperhitungkan dominasi Pareto dalam gerak partikel PSO. Dalam konteks ini, solusi yang tidak didominasi disimpan sedemikian rupa sehingga mendekati front Pareto dan memberikan alternatif optimal yang mencakup solusi yang tidak dapat dilampaui satu sama lain dalam konteks fungsi tujuan yang berbeda. 

Disadur dari : https://en.wikipedia.org/wiki/Particle_swarm_optimization

Selengkapnya
Mengenal Lebih Jauh Optimasi kawanan partikel

Operation Research and Analysis

Lebih Jauh Mengenal Algoritma Genetika Part 2

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Hipotesis Dasar

Algoritma genetika mudah diimplementasikan, namun perilakunya sulit dipahami. Secara khusus, sulit untuk memahami mengapa algoritme ini, ketika diterapkan pada masalah praktis, sering kali berhasil menghasilkan solusi dengan kesesuaian tinggi. Hipotesis dasar (BBH) terdiri dari deskripsi heuristik yang melakukan adaptasi dengan mengidentifikasi dan menggabungkan kembali “building block”. Komponen dasarnya adalah skema tingkat rendah dan jangka pendek dengan kebugaran di atas rata-rata.

Hipotesis ini menyatakan bahwa algoritma genetika beradaptasi dengan mengimplementasikan heuristik ini secara implisit dan efisien.Goldberg menggambarkan heuristik ini sebagai skema pendek, tingkat rendah, dan sangat kongruen yang diambil sampelnya, digabungkan kembali, dan diambil sampelnya kembali untuk membentuk rangkaian dengan potensi konkordansi yang lebih tinggi. Dengan menggunakan skema ini, algoritme genetika bertujuan untuk mencapai kinerja yang mendekati optimal dengan membandingkan skema atau blok penyusun yang pendek, tingkat rendah, dan kinerja tinggi.

Meskipun tidak ada konsensus mengenai validitas hipotesis dasar, hipotesis tersebut terus dievaluasi dan digunakan sebagai referensi selama bertahun-tahun. Beberapa penelitian telah mencoba untuk memahami keterbatasannya dari perspektif estimasi algoritma distribusi, namun masih ada skeptisisme mengenai keumuman dan/atau kepraktisan hipotesis blok penyusun sebagai penjelasan efisiensi GA. Namun, beberapa penelitian melaporkan hasil yang baik untuk beberapa kelas masalah, dan algoritma estimasi distribusi telah diusulkan untuk memberikan pengaturan yang mendukung hipotesis.

Keterbatasan Algoritma Genetik

Penggunaan algoritma genetika memiliki beberapa keterbatasan dibandingkan dengan alternatif optimasi lainnya. Pertama, evaluasi fungsi kebugaran, yang harus dilakukan secara berulang untuk masalah yang kompleks, dapat menjadi segmen algoritma evolusi buatan yang paling mahal dan membatasi. Untuk permasalahan dunia nyata seperti optimasi struktural, evaluasi satu fungsi dapat memakan waktu berjam-jam hingga berhari-hari. Hal ini mengharuskan dilakukannya evaluasi yang tidak akurat atau menggunakanestimasi kebugaran yang efisien secara komputasi.

Selain itu, sulit bagi algoritma genetika untuk mengukur kompleksitas dengan baik, terutama ketika jumlah elemen yang dipengaruhi oleh mutasi berjumlah besar, karena hal ini dapat menyebabkan peningkatan ruang pencarian secara eksponensial.Selain itu, terdapat kebingungan dalam menentukan solusi yang “lebih baik” dibandingkan solusi lainnya, sehingga kriteria penghentiannya tidak jelas. Algoritma genetika juga cenderung berkumpul pada titik optimal lokal atau bahkan titik sembarang dibandingkan titik optimal global suatu permasalahan. Hal ini bergantung pada bentuk lanskap kebugaran. Untuk mengatasi masalah ini, digunakan fungsi kebugaran yang berbeda, peningkatan laju mutasi, atau teknik seleksi yang mempertahankan populasi solusi yang beragam.

Berurusan dengan kumpulan data dinamis juga sulit karena genom mulai menyatu sejak awal dan dapat menghasilkan solusi yang tidak lagi valid untuk data selanjutnya. Meskipun berbagai metode telah diusulkan untuk mengatasi masalah ini seperti: B. memicu hipermutasi atau imigrasi acak, strategi evolusi dan program evolusi bisa lebih efektif dalam masalah yang dinamis.Yang terakhir, algoritma genetika bisa menjadi tidak efisien untuk masalah-masalah yang membutuhkan solusi biner lolos/gagal karena tidak ada cara untuk menyatukan solusi-solusi tersebut. Ketika ukuran keberhasilan dan kegagalan diberikan dalam bentuk hasil biner, pencarian acak dapat menghasilkan solusi secepat algoritma genetika. Untuk masalah optimasi dan contoh masalah tertentu, algoritma optimasi yang berbeda mungkin lebih efisien dalam hal kecepatan konvergensi, tergantung pada seberapa banyak pengetahuan yang dimiliki seseorang tentang masalah tersebut.

Varian

Representasi Kromosom

Algoritma genetika dapat direpresentasikan dengan cara yang berbeda-beda tergantung pada jenis masalah yang ditangani. Pendekatan paling sederhana adalah dengan merepresentasikan setiap kromosom sebagai string bit, dimana parameter numerik dapat direpresentasikan sebagai bilangan bulat atau angka floating point. Namun, perlu dicatat bahwa gagasan algoritma genetika bernilai nyata sebenarnya adalah sebuah kekeliruan dan tidak sepenuhnya mencerminkan teori blok bangunan yang diajukan oleh John Henry Holland pada tahun 1970-an.

Pada tingkat dasar, algoritma melakukan operasi crossover dan mutasi tingkat bit. Saat merepresentasikan bilangan bulat dalam bentuk bitstring, pengkodean Gray sering digunakan untuk mencegah konvergensi dini dalam situasi di mana perubahan kecil pada bilangan bulat dapat dengan mudah dipengaruhi oleh mutasi atau persilangan.Alternatif lain termasuk merepresentasikan kromosom sebagai daftar angka yang diindeks dalam tabel instruksi, sebagai node dalam daftar tertaut, sebagai hash, sebagai objek, atau sebagai struktur data lain yang sesuai dengan batas elemen data. Kromosom juga dapat direpresentasikan sebagai kumpulan bilangan real, yang dapat memberikan hasil yang baik, meskipun pada awalnya hal ini mengejutkan para peneliti.

Untuk memperluas cakupan masalah, kromosom dapat dikodekan dengan menggabungkan beberapa jenis gen yang terwakili secara heterogen pada suatu kromosom. Pendekatan ini memungkinkan pemodelan dan simulasi sistem adaptif yang kompleks dengan rentang definisi yang sangat berbeda untuk parameter masalah tertentu. Untuk menggabungkan kembali bagian kromosom, pendekatan ini memerlukan penerapan persilangan khusus.

Elitisme

Strategi seleksi elit merupakan varian praktis dari proses penciptaan populasi baru dalam algoritma genetika. Dengan strategi ini, organisme terbaik dari generasi sekarang dapat diwariskan tanpa perubahan ke generasi berikutnya. Pendekatan seleksi elit ini menjamin kualitas solusi yang diperoleh algoritma genetika tidak menurun dari generasi ke generasi.

Implementasi Paralel

Implementasi paralel dari algoritma genetika hadir dalam dua bentuk. Algoritme genetika paralel berbutir kasar mengasumsikan populasi di setiap node komputer dan migrasi individu di antara node-node tersebut. Algoritma genetika paralel yang terperinci mengasumsikan bahwa individu-individu di setiap node prosesor bekerja sama dengan individu-individu tetangga dalam seleksi dan reproduksi. Varian lain, seperti algoritme genetika untuk masalah pengoptimalan online, memperkenalkan ketergantungan temporal atau gangguan ke dalam fungsi kebugaran.

GA adaptif

Algoritma genetika parameter adaptif (AGA) adalah varian penting dari algoritma genetika yang menawarkan potensi peningkatan dalam akurasi solusi dan kecepatan konvergensi. Dalam AGA, probabilitas crossover (pc) dan mutasi (pm), yang secara signifikan mempengaruhi kinerja algoritma genetika, tidak tetap tetapi disesuaikan secara adaptif berdasarkan informasi populasi di setiap generasi. Penyesuaian ini dilakukan untuk menjaga keberagaman populasi dan kemampuan konvergensi. Ada beberapa pendekatan pada AGA, salah satunya adalah metode ekstensi berturut-turut, yang meningkatkan konvergensi.

CAGA (algoritme genetika adaptif berbasis cluster) adalah contoh lain dari AGA yang menggunakan analisis cluster untuk mengevaluasi keadaan optimalitas populasi, dengan PC dan PM disesuaikan bergantung pada keadaan optimalitas ini.Pendekatan saat ini termasuk menggunakan variabel yang lebih abstrak untuk menentukan pc dan pm, seperti prinsip dominasi dan kodominan dan LIGA (Level Interpolative Genetic Algorithm), yang mengintegrasikan GA dengan pencarian A* yang dimodifikasi untuk mengurangi anisotropi dari ruang pencarian yang diambil. memperhitungkan.

Kombinasi GA dengan metode optimasi lainnya juga terbukti berhasil. GA umumnya cenderung menemukan solusi global yang baik, namun mungkin kurang efisien dalam menemukan mutasi akhir untuk mencapai solusi optimal absolut. Oleh karena itu, mengganti GA dengan teknik lain, seperti pendakian gunung sederhana, dapat meningkatkan efisiensi GA dan mengatasi ketidakmampuan mendaki bukit. Variasi genetik dapat memiliki arti berbeda dalam konteks ini; Misalnya, persilangan diartikan sebagai penjumlahan langkah DNA ibu dan ayah.Operator inversi juga dapat digunakan untuk menyusun langkah-langkah secara berurutan atau sesuai untuk efisiensi atau kelayakan.

Rekombinasi kumpulan gen adalah variasi yang melibatkan evolusi seluruh populasi, bukan individu. Beberapa varian lain, seperti mGA, GEMGA dan LLGA, telah dikembangkan untuk meningkatkan kinerja GA pada masalah kebugaran epistasis tinggi dimana kebugaran solusi melibatkan interaksi fenotipik antar variabel. Pendekatan ini bertujuan untuk memahami dan mengeksploitasi interaksi fenotipik sebelum mengeksploitasinya, sehingga mengurangi rekombinasi yang dapat menyebabkan gangguan adaptif.

 

Disadur dari : https://en.wikipedia.org/wiki/Genetic_algorithm

Selengkapnya
Lebih Jauh Mengenal Algoritma Genetika Part 2

Operation Research and Analysis

Lebih Jauh Mengenal Algoritma Genetika Part 1

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Algoritma Genetika

Dalam ilmu komputer dan riset operasi, algoritma genetika (GA) adalah metaheuristik yang terinspirasi oleh proses seleksi alam dan termasuk dalam kelas algoritma evolusioner (EA) yang lebih luas. Algoritme genetika banyak digunakan untuk menciptakan solusi berkualitas tinggi untuk masalah pencarian dan optimasi berdasarkan operator yang terinspirasi secara biologis seperti mutasi, persilangan, dan seleksi. Aplikasi GA antara lain mengoptimalkan pohon keputusan untuk meningkatkan kinerja, memecahkanteka-teki Sudoku, optimasi hyperparameter, inferensi kausal, dan berbagai masalah lainnya.

Metodologi

Masalah Optimasi

Dalam algoritma genetika, populasi kandidat solusi (disebut individu, makhluk, organisme, atau fenotipe) terhadap masalah optimasi berevolusi menuju solusi yang lebih baik. Setiap kandidat solusi memiliki serangkaian karakteristik (kromosom atau genotipenya) yang dapat dimutasi dan diubah; Secara tradisional, solusi direpresentasikan dalam biner sebagai string 0 dan 1, namun pengkodean lain juga dimungkinkan.

Evolusi umumnya dimulai dengan populasi individu yang dihasilkan secara acak dan merupakan proses berulang dimana populasi pada setiap iterasi disebut generasi. Pada setiap generasi, kebugaran setiap individu dalam populasi dinilai; Fitness biasanya merupakan nilai fungsi tujuan dalam masalah optimasi yang ingin diselesaikan. Individu yang paling sehat dipilih secara stokastik dari populasi saat ini dan genom masing-masing individu diubah (dikombinasikan ulang dan mungkin bermutasi secara acak) untuk membentuk generasi baru.Kandidat solusi generasi baru kemudian digunakan pada iterasi algoritma berikutnya. Secara umum, algoritma berakhir ketika jumlah generasi maksimum telah dihasilkan atau tingkat kesesuaian populasi yang memuaskan telah tercapai.

Algoritme genetika tipikal memerlukan representasi genetik dari domain solusi dan fungsi kebugaran untuk mengevaluasi domain solusi. Representasi standar dari setiap kandidat solusi adalah sebagai array bit (juga disebut kumpulan bit atau urutan bit). Array tipe dan struktur lain pada dasarnya dapat digunakan dengan cara yang sama.Fitur utama yang membuat representasi genetik ini mudah digunakan adalah bagian-bagiannya mudah disejajarkan karena ukurannya yang tetap, sehingga memudahkan operasi persilangan sederhana. Representasi panjang variabel juga dapat digunakan, meskipun dalam kasus ini penerapan traversal lebih kompleks. Representasi pohon dipelajari dalam pemrograman genetik dan representasi grafis dalam pemrograman evolusioner; campuran kromosom linier dan pohon yang dipelajari dalam pemrograman ekspresi gen tahun.

Setelah representasi genetik dan fungsi kebugaran ditentukan, GA menginisialisasi populasi solusi dan kemudian menyempurnakannya melalui penerapan berulang dari operator mutasi, persilangan, inversi, dan seleksi. Namun, perlu dicatat bahwa penerapan traversal lebih kompleks dalam kasus representasi panjang variabel.

Inisiasi

Ukuran populasi dalam algoritma genetika bergantung pada sifat masalah yang dihadapi, namun biasanya berisi beberapa ratus atau ribuan kemungkinan solusi. Seringkali populasi awal dihasilkan secara acak sehingga seluruh kemungkinan solusi dalam ruang pencarian dapat dieksplorasi. Kadang-kadang suatu solusi dapat “lebih disukai” di area dimana solusi optimal lebih mungkin ditemukan, atau distribusi probabilitas sampling disesuaikan untuk fokus pada area yang lebih diminati.

Seleksi

Pada setiap generasi berikutnya, sebagian dari populasi yang ada dipilih untuk bereproduksi pada generasi baru. Solusi individual dipilih melalui proses berbasis kebugaran, dimana solusi yang lebih tepat umumnya lebih mungkin untuk dipilih (yang diukur dengan fungsi kebugaran). Metode seleksi tertentu mengevaluasi kesesuaian setiap solusi dan memilih solusi terbaik. Metode lain hanya mengevaluasi sampel populasi secara acak, karena proses yang dijelaskan di atas dapat memakan waktu.fungsi kebugaran didefinisikan dalam representasi genetik dan mengukur kualitas solusi yang diwakili.

Fungsi kebugaran selalu bergantung pada masalah yang dimaksud. Misalnya pada soal tas punggung, tujuannya adalah memaksimalkan nilai total benda yang dapat dimasukkan ke dalam tas ransel berkapasitas tetap. Representasi solusinya dapat berupa array bit, dimana setiap bit mewakili objek yang berbeda dan nilai bit (0 atau 1) menunjukkan apakah objek tersebut ada di dalam ransel atau tidak. Tidak semua gambaran ini valid karena ukuran benda mungkin melebihi kapasitas ransel.

Kesesuaian suatu solusi diukur sebagai jumlah nilai semua benda di dalam ransel jika representasinya valid, jika tidak maka 0.Untuk beberapa permasalahan, sulit atau bahkan tidak mungkin untuk mendefinisikan istilah kebugaran; Dalam kasus ini, simulasi dapat digunakan untuk menentukan nilai fungsi kebugaran suatu fenotipe (misalnya, dinamika fluida komputasi digunakan untuk menentukan hambatan kendaraan yang bentuknya dikodekan sebagai fenotipe), atau bahkan algoritma genetika interaktif dapat digunakan. digunakan menjadi. diperlukan.

Operator Genetik

Langkah selanjutnya dalam algoritma genetika adalah membuat solusi populasi generasi kedua dari solusi terpilih dengan menggunakan kombinasi operator genetik yaitu crossover (rekombinasi) dan mutasi.Untuk setiap solusi baru yang akan dibuat, sepasang solusi “utama” dipilih dari kumpulan solusi yang dipilih sebelumnya.

Metode crossover dan mutasi digunakan untuk menciptakan solusi baru yang biasanya memiliki banyak karakteristik yang sama dengan “induknya”. Proses ini berlanjut hingga dihasilkan populasi solusi baru dengan ukuran yang sesuai. Meskipun metode reproduksi yang menggunakan dua orang tua cenderung lebih “terinspirasi secara biologis”, beberapa penelitian menunjukkan bahwa lebih dari dua “orang tua” dapat menghasilkan kromosom dengan kualitas lebih tinggi.

Pada akhirnya, proses tersebut menciptakan populasi kromosom pada generasi berikutnya yang berbeda dengan generasi aslinya. Secara umum, metode ini meningkatkan rata-rata kebugaran suatu populasi karena hanya organisme generasi pertama terbaik yang dipilih untuk reproduksi, selain sebagian kecil dari solusi yang kurang sesuai. Solusi yang tidak tepat ini menjamin keragaman genetik pada kumpulan gen orang tua dan oleh karena itu keragaman genetik pada anak-anak generasi berikutnya.

Pendapat berbeda-beda mengenai arti persilangan versus mutasi, dengan beberapa referensi yang mendukung pentingnya penelusuran berbasis mutasi. Meskipun persilangan dan mutasi dikenal sebagai operator genetika utama, namun dimungkinkan juga untuk menggunakan operator lain seperti pengelompokan ulang, pemusnahan kolonisasi, atau migrasi dalam algoritma genetika.Yang terbaik adalah menyesuaikan parameter seperti probabilitas mutasi, probabilitas persilangan, dan ukuran populasi untuk menemukan konfigurasi yang masuk akal untuk kelas masalah tertentu. Tingkat mutasi yang sangat kecil dapat menyebabkan variasi genetik yang tidak bersifat ergodik. Tingkat rekombinasi yang terlalu tinggi dapat menyebabkan konvergensi dini pada algoritma genetika. Tingkat mutasi yang terlalu tinggi dapat mengakibatkan hilangnya solusi yang baik kecuali dilakukan seleksi elit. Ukuran populasi yang memadai memastikan keragaman genetik yang memadai untuk memecahkan masalah yang ada, namun dapat mengakibatkan sumber daya komputasi terbuang jika diatur ke nilai yang lebih besar dari yang dibutuhkan.

Heuristik

Selain operator utama di atas, beberapa heuristik tambahan dapat digunakan untuk meningkatkan kecepatan atau kekuatan penghitungan. Salah satunya adalah heuristik spesiasi yang memberikan hukuman kepada persilangan antara kandidat solusi yang terlalu mirip. Heuristik ini bertujuan untuk mendorong keberagaman populasi dan membantu mencegah konvergensi dini menuju solusi yang kurang optimal.

Disadur dari : https://en.wikipedia.org/wiki/Genetic_algorithm

Selengkapnya
Lebih Jauh Mengenal Algoritma Genetika Part 1

Operation Research and Analysis

Mengenal Pengertian, Sejarah, Teknik dan Algoritma Pada Komputasi Evolusioner Part 1

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Komputasi Evolusioner

Dalam ilmu komputer, komputasi evolusioner adalah seperangkat algoritme pengoptimalan global yang terinspirasi oleh evolusi biologis dan subbidang kecerdasan buatan serta komputasi lunak yang mempelajari algoritme ini. Secara teknis, ini adalah rangkaian pemecah masalah coba-coba berbasis populasi dengan fungsi optimasi metaheuristik atau stokastik.

Dalam komputasi evolusioner, serangkaian solusi awal yang mungkin dihasilkan dan diperbarui secara berulang. Setiap generasi baru diciptakan dengan menghilangkan solusi yang kurang diinginkan secara stokastik, memperkenalkan perubahan kecil secara acak, dan, bergantung pada metodenya, mengacak informasi induknya. Dalam terminologi biologi, populasi solusi mengalami seleksi alam (atau seleksi buatan), mutasi, dan kemungkinan rekombinasi.Akibatnya, populasi secara bertahap akan berevolusi untuk meningkatkan kebugaran, dalam hal ini fungsi kebugaran yang dipilih dari algoritma.

Teknik komputasi evolusioner dapat memberikan solusi yang sangat optimal terhadap berbagai masalah, menjadikannya populer dalam ilmu komputer. Ada banyak varian dan ekstensi yang disesuaikan dengan masalah dan struktur data yang lebih spesifik. Evolusi komputasi juga terkadang digunakan dalam biologi evolusi sebagai metode eksperimental in silico untuk mempelajari aspek umum dari proses evolusi umum.

Sejarah

Konsep meniru proses evolusi untuk memecahkan masalah sudah ada sebelum munculnya komputer, misalnya ketika Alan Turing mengusulkan metode pencarian genetik pada tahun 1948. Mesin tipe B Turing menyerupai jaringan saraf primitif, dan hubungan antar neuron dipelajari melalui sejenis algoritma genetika. Mesin tipe P mereka menyerupai metode pembelajaran penguatan, di mana sinyal kesenangan dan rasa sakit menginstruksikan mesin untuk mempelajari perilaku tertentu. Meskipun makalah Turing baru diterbitkan pada tahun 1968 dan dia meninggal pada tahun 1954, karya-karya awal ini berdampak kecil pada perkembangan bidang komputasi evolusioner.

Komputasi evolusioner sebagai suatu bidang dimulai dengan sungguh-sungguh pada tahun 1950an dan 1960an.Pada tahun 1962, Lawrence J. Fogel mulai meneliti pemrograman evolusioner di Amerika Serikat, yang dianggap sebagai upaya kecerdasan buatan. Dalam sistem ini, mesin keadaan terbatas digunakan untuk menyelesaikan masalah prediksi: mesin ini akan bermutasi (menambah atau menghapus keadaan atau mengubah aturan transisi keadaan), dan mesin yang bermutasi lebih baik ini akan berkembang di generasi mendatang. Mesin keadaan terbatas terakhir dapat menghasilkanprediksi sesuai permintaan. Metode pemrograman evolusioner telah berhasil diterapkan pada masalah prediksi, identifikasi sistem, dan kontrol otomatis.Seiring waktu, ini telah diperluas untuk memproses data deret waktu dan pengembangan model strategi permainan.

Pada tahun 1964, Ingorechnerberg dan Hans-Paul Pelz memperkenalkan paradigma strategi evolusioner di Jerman. Karena teknik penurunan gradien tradisional menghasilkan hasil yang dapat terperangkap dalam nilai minimum lokal, Rechnerberg dan Pelz menyarankan bahwa mutasi acak (diterapkan pada semua parameter vektor solusi) dapat digunakan untuk menghindari nilai minimum ini. Solusi sekunder adalah hasil dari solusi primer, dan solusi yang paling berhasil dipertahankan untuk generasi mendatang.Teknik ini pertama kali digunakan oleh keduanya hingga berhasil memecahkan masalah optimasi dalam dinamika fluida. Awalnya, teknik optimasi ini dilakukan tanpa komputer, melainkan menggunakan dadu untuk menentukan mutasi acak.Jika metode sebelumnya hanya melacak satu organisme optimal dalam satu waktu (anak-anak bersaing dengan orang tuanya), algoritma genetika Holland melacak populasi besar (dengan banyak organisme bersaing di setiap generasi).

Pada tahun 1990-an, pendekatan baru terhadap komputasi evolusioner muncul, yang kemudian disebut pemrograman genetik, antara lain didukung oleh John Koza. Pada kelas algoritma ini, pokok bahasan evolusinya sendiri adalah program yang ditulis dalam bahasa pemrograman tingkat tinggi. Bagi Koza, programnya adalah ekspresi Lisp S, yang dapat dipandang sebagai pohon subekspresi. Representasi ini memungkinkan program untuk bertukar subpohon yang mewakili semacam campuran genetik.Program diberikan poin berdasarkan seberapa baik mereka melakukan tugas tertentu, dan poin ini digunakan untuk seleksi buatan. Induksi sekuens, pengenalan pola, dan perencanaan adalah penerapan paradigma pemrograman genetik yang berhasil.

Banyak tokoh lain yang berperan dalam sejarah komputasi evolusioner, meskipun karya mereka belum tentu cocok dengan salah satu cabang sejarah utama bidang ini. Simulasi komputer evolusi pertama yang menggunakan algoritma evolusi dan teknik kehidupan buatan dilakukan oleh Nils Aall Barricelli pada tahun 1953 dan hasil pertama dipublikasikan pada tahun 1954. Pelopor lain pada tahun 1950an adalah Alex Fraser, yang menerbitkan serangkaian artikel tentang simulasi kehidupan buatan. Pilihan.Seiring dengan meningkatnya minat akademis, peningkatan dramatis dalam kekuatan komputer memungkinkan penerapan praktis, termasuk pengembangan program komputer secara otomatis. Algoritme evolusioner sekarang digunakan untuk memecahkan masalah multidimensi dengan lebih efisien daripada perangkat lunak yang dibuat oleh perancang manusia dan juga untuk mengoptimalkan desain sistem.

Teknik

Teknik komputasi evolusioner mencakup berbagai algoritma optimasi metaheuristik yang digunakan untuk memecahkan masalah yang kompleks. Bidang ini mencakup pemodelan berbasis agen, optimasi koloni semut, sistem kekebalan buatan, kehidupan buatan (termasuk organisme digital), algoritma budaya, algoritma koevolusi, evolusi diferensial, evolusi multifase, algoritma estimasi distribusi, algoritma evolusi, pemrograman strategi evolusi dan evolusi, gen pemrograman ekspresi, algoritma genetika, pemrograman genetik, tata bahasa evolusioner, model evolusioner yang dapat dipelajari, sistem klasifikasi pembelajaran, algoritma memetika, neuroevolusi, optimalisasi kawanan partikel, pencarian antena kumbang, pengorganisasian mandiri sebagai peta yang diatur sendiri, pembelajaran kompetitif dan kecerdasan massa. Meskipun katalog ini berisi banyak algoritma yang diusulkan, penting untuk dicatat bahwa beberapa algoritma baru mungkin memiliki validasi eksperimental yang tidak memuaskan.Untuk informasi lebih lanjut tentang berbagai algoritma, lihat Bestiary of Evolutionary Computation.

Disadur dari : https://en.wikipedia.org/wiki/Evolutionary_computation

Selengkapnya
Mengenal  Pengertian, Sejarah, Teknik dan Algoritma Pada Komputasi  Evolusioner Part 1

Operation Research and Analysis

Mengenal Pengertian, Sejarah, Teknik dan Algoritma Pada Komputasi Evolusioner Part 2

Dipublikasikan oleh Dias Perdana Putra pada 19 Februari 2024


Komputasi Evolusioner 

Dalam ilmu komputer, komputasi evolusioner adalah sistem komputer untuk menemukan solusi masalah optimasi yang menggunakan model komputasi proses evolusi seperti seleksi alam, survival of the fittest, dan reproduksi. Komputasi evolusioner, bidang kecerdasan komputer, mencakup algoritma genetika, pemrograman genetik, dan pemrograman evolusioner. Penerapan komputasi evolusioner untuk masalah optimasi sangat luas dan mencakup teknik industri, transportasi, jaringan komunikasi, robotika, penambangan data, bioinformatika, sistem energi, permainan, teknik kontrol, dan pemrosesan sinyal/gambar. Penggunaan prinsip evolusi untuk pemecahan masalah otomatis sudah ada sejak tahun 1950an. Baru pada tahun 1960an tiga penafsiran berbeda terhadap gagasan ini mulai berkembang di tiga tempat berbeda.

Pemrograman evolusioner diperkenalkan oleh Lawrence J. Fogel di Amerika, sedangkan John Henry Holland menyebut metodenya sebagai algoritma genetika. Di Jerman, Ingorechnerberg dan Hans-Paul Pelz memperkenalkan strategi evolusi. Kawasan-kawasan ini dikembangkan secara terpisah selama kurang lebih 15 tahun. Sejak awal tahun 1990-an, mereka telah disatukan sebagai perwakilan (“dialek”) yang berbeda dari satu teknologi, yang disebut komputasi evolusioner.Juga pada awal tahun 1990-an, muncul tren keempat yang mengikuti ide dasar: pemrograman genetik. Sejak tahun 1990an, algoritma yang terinspirasi dari alam telah menjadi bagian yang semakin penting dalam komputasi evolusioner. Terminologi ini mengacu pada bidang komputasi evolusioner dan menganggap pemrograman evolusioner, strategi evolusi, algoritma genetika, dan pemrograman genetika sebagai subbidang.

Simulasi evolusi menggunakan algoritma evolusi dan kehidupan buatan dimulai dengan karya Nils Aall Barricelli pada tahun 1960an dan diperluas oleh Alex Fraser, yang menerbitkan sejumlah makalah tentang simulasi seleksi buatan. Evolusi buatan menjadi metode optimasi yang diterima secara luas melalui karya Ingorechnerberg pada tahun 1960an dan awal 1970an, yang menggunakan strategi evolusi untuk memecahkan masalah teknik yang kompleks. Algoritma genetika khususnya memperoleh popularitas luas pada tahunmelalui tulisan John Holland. Seiring dengan meningkatnya minat akademis, peningkatan dramatis dalam kekuatan komputer memungkinkan penerapan praktis, termasuk pengembangan program komputer secara otomatis. Algoritme evolusioner sekarang digunakan untuk memecahkan masalah multidimensi dengan lebih efisien daripada perangkat lunak yang dibuat oleh perancang manusia dan juga untuk mengoptimalkan desain sistem.

Algoritma Evolusioner

Algoritme evolusioner adalah bagian dari komputasi evolusioner yang umumnya hanya melibatkan penerapan mekanisme yang terinspirasi oleh evolusi biologis, seperti: B. Reproduksi, mutasi, rekombinasi, seleksi alam dan survival of the fittest. Kandidat solusi untuk masalah optimasi memainkan peran individu dalam suatu populasi, dan fungsi biaya menentukan lingkungan di mana solusi tersebut “hidup” (lihat juga fungsi kebugaran). Evolusi populasi kemudian terjadi setelah penerapan berulang kali dari operator sebelumnya.Dalam proses ini, ada dua kekuatan utama yang menjadi dasar sistem evolusi: rekombinasi (misalnya pindah silang) dan mutasi menciptakan keragaman yang diperlukan dan dengan demikian memfasilitasi hal-hal baru, sedangkan seleksi bertindak sebagai kekuatan yang meningkatkan kualitas.

Banyak aspek proses evolusi bersifat stokastik.Informasi yang berubah melalui rekombinasi dan mutasi dipilih secara acak. Di sisi lain, operator seleksi bisa bersifat deterministik atau stokastik. Dalam kasus terakhir, individu dengan kebugaran lebih tinggi memiliki peluang lebih besar untuk terpilih dibandingkan individu dengan kebugaran lebih rendah, namun umumnya individu yang lebih lemah juga memiliki peluang untuk menjadi orang tua atau bertahan hidup.

Algoritma evolusi dan biologi

Algoritma genetika menyediakan metode untuk memodelkan sistem biologis dan hubungannya dengan teori sistem dinamik karena keduanya digunakan untuk memprediksi keadaan suatu sistem di masa depan. Meskipun analogi ini mungkin berguna untuk memahami ciri-ciri perkembangan biologis yang teratur dan terstruktur, penggunaan algoritma dan ilmu komputer, khususnya teori komputasi, memiliki relevansi yang lebih luas untuk memahami evolusi itu sendiri.

Pandangan ini mempunyai keuntungan karena mengakui bahwa pembangunan tidak dikontrol secara terpusat; Organisme berkembang melalui interaksi lokal di dalam dan antar sel. Ide yang menjanjikan untuk paralelisme dalam pengembangan program adalah analogi yang erat antara proses dalam sel dan pengoperasian komputer tingkat rendah modern. Oleh karena itu, sistem biologis dapat dipandang sebagai mesin komputasi yang memproses informasi masukan untuk menghitung keadaan selanjutnya, menjadikan sistem biologis lebih dekat dengan komputasi daripada sistem dinamik klasik.

Dalam kerangka teori komputasi, mikroproses dalam organisme biologis dianggap tidak lengkap dan tidak dapat diputuskan, menunjukkan bahwa analogi antara sel dan komputer melibatkan lebih dari sekedar metafora. Analogi komputasi juga memperdalam pemahaman tentang hubungan antara sistem hereditas dan struktur biologis, yang sering kali dianggap sebagai salah satu tantangan terbesar dalam menjelaskan asal usul kehidupan.Automata evolusioner, sebuah generalisasi dari mesin Turing evolusioner, diperkenalkan untuk mempelajari sifat-sifat komputasi biologis dan evolusioner secara lebih rinci. Mereka memungkinkan untuk memperoleh hasil baru pada ekspresi komputasi evolusioner dan untuk mengkonfirmasi hasil awal mengenai ketidakpastian evolusi alam serta algoritma dan proses evolusi.

Automata evolusioner terbatas, sebagai subkelas sederhana dari automata evolusioner, dapat menerima bahasa apa pun dari alfabet tertentu, termasuk bahasa yang tidak dapat dihitung secara rekursif dan bahasa yang dapat dihitung secara rekursif tetapi tidak dapat dihitung secara rekursif.

Sumber Artikel: https://en.wikipedia.org/wiki/Evolutionary_computation

Selengkapnya
Mengenal Pengertian, Sejarah, Teknik dan Algoritma Pada Komputasi Evolusioner Part 2
page 1 of 10 Next Last »