Genetic Algorithm Optimization in C/C++
9.1 Pendahuluan
C adalah bahasa pemrograman terstruktur untuk tujuan umum yang kuat, efisien, dan kompak. C menggabungkan fitur bahasa tingkat tinggi dengan elemen-elemennya assembler dan karenanya, dekat dengan manusia dan mesin. C juga banyak dipakai oleh berbagai jenis platform sistem operasi dan arsitektur komputer, bahkan terdapat beberepa compiler yang sangat populer telah tersedia. C secara luar biasa memengaruhi bahasa populer lainnya, terutama C++ yang merupakan extensi dari C.
9.2 Problema Salesman Keliling (Travelling Salesman Problem/ TSP)
Dalam masalah salesman keliling, salesman bepergian ke kota-kota dan kembali ke permulaan kota dengan biaya minimal, ia tidak diperbolehkan melintasi kota lebih dari sekali. Di masalah ini kita mengambil asumsi bahwa semua n kota saling terhubung. Biaya menunjukkan jarak antara dua kota. Untuk mengatasi masalah ini kami buat penggunaan algoritma genetika karena kota-kota secara acak.
Populasi awal untuk ini masalah adalah kota yang dipilih secara acak. Fungsi kebugaran tidak lain adalah minimum biaya. Awalnya fungsi kebugaran diatur ke nilai maksimum dan untuk setiap perjalanan,biaya dihitung dan dibandingkan dengan fungsi kebugaran. Nilai kebugaran baru ditugaskan untuk biaya minimum. Populasi awal dipilih secara acak dan diambil sebagai orang tua. Untuk generasi berikutnya, crossover siklik diterapkan di atas induk. Crossover Siklik.
P1 dan P2 adalah induk
lalu ambil keturunanlangsung dari induk 1 (01)
Untuk menemukan kota berikutnya, cari anak-anak O1 kota saat ini, yang dipilih dari P1 dalam P2. Temukan lokasi kota di P2 dan pilih kota yang sama dengan lokasi di P1.
Gunakan prosedur yang sama, kita akan mendapatkan bahwa O1 sebagai
Prosedur selanjutnya, kita akan mendapatkan kota 2 yang sudah ada di O1 lalu hentikan prosedur. Salin kota dari induk P2 di lokasi yang sesuai.
O1: 2 8 0 1 6 4 5 7 9 3
Untuk generasi O2, seleksi awal adalah dari induk P2,dan ulangi prosedur dengan P1.
O2: 1 5 4 3 8 9 7 2 6
9.3 Problema Mencocokkan Data
Masalah pencocokan kata mencoba untuk mengembangkan ekspresi "menjadi atau tidak menjadi" dari daftar surat yang dihasilkan secara acak dengan algoritma genetika. Dikarenakan ada 26 kemungkinan kata-kata dari 13 lokasi di dalam daftar nama, maka kemungkinan probabilitas yang kita dapatkan melalui cara acak adalah s (1/26)*13 = 4.03038∗10−19, atau dua daari se-milyar kali kemungkinan. Kita mengunakan integer ASCII untuk mengkode barisan huruf.
[116,111,98,101,111,114,110,111,116,116,111,98,101]
Populasi awal dihasilkan secara acak. Kebugaran dihitung sebagai jumlah huruf yang cocok. Operator genetik digunakan untuk mendapatkan output. Masalahnya adalah diimplementasikan dalam C dan output diperoleh.
9.4 Dilema Tahanan
Kooperator "curang" yang kerjasamanya tidak dikembalikan. Seluruh situasi permainan dan hasil yang berbeda dapat diringkas oleh tabel di bawah ini, di mana hipotetis "Poin" diberikan sebagai contoh bagaimana perbedaan dalam hasil dapat dikuantifikasi.
Jenis crossover yang dilakukan adalah "crossover titik tunggal" di mana titik tersebut crossover dipilih secara acak. Mutasi ini diharapkan terjadi setiap dua seribu generasi. Sangat mudah untuk mengubah mutasi karena diimplementasikan sebagai fungsi terpisah.
9.5 Maximize f(x) = x2
Program C ++ untuk memaksimalkan f (x) = x2 menggunakan algoritma genetik, di mana x adalah
berkisar dari 0 hingga 31.
Generate Initial four populations of binary string with 5 bits length.
Calculate corresponding x and fitness value f(x) = x2.
Use the tournament selection method to generate new four populations.
Apply cross-over operator to the new four populations and generate new populations.
Apply mutation operator for each population.
Repeat the step 2 to 5 for some 20 iterations.
. Finally print the result.
9.6 Me-minimisasi fungsi sin dengan batasan.
Batasan biasanya diklasifikasikan sebagai hubungan kesetaraan atau ketidaksetaraan. Karena kendala kesetaraan dapat dimasukkan ke dalam model sistem, kami hanya peduli kendala ketimpangan. Algoritme genetik menghasilkan urutan parameter diuji menggunakan model sistem, fungsi tujuan dan kendala.
Jika tidak, set parameter diberikan nilai kebugaran yang sesuai dengan evaluasi fungsi tujuan. Jika kendala dilanggar, solusinya tidak layak dan dengan demikian tidak memiliki kesesuaian. Kami biasanya ingin mendapatkan beberapa informasi solusi tidak layak, dengan menurunkan peringkat kebugaran mereka sehubungan dengan derajat pelanggaran kendala. Metode ini disebut sebagai metode penalti.
Dalam metode ini, masalah kendala dalam pengoptimalan ditransformasikan ke masalah tidak dibatasi dengan mengaitkan biaya atau penalti dengan semua pelanggaran kendala. Biaya tersebut termasuk dalam evaluasi fungsi tujuan
9.6 Me-Maksimalkan fungsi f(x) = x∗sin(10∗Π∗x) + 10
Step by step
Langkah 1: Hasilkan nomor acak sebagai n
Langkah 2: Inisialisasi masing-masing i, j ke n dan m
Langkah 3: Max ← 1, x [i] ← 0, jumlah ← 0, m_max ← 1
Langkah 4: Hitung x [i] ← x [i] + (pp [i] [j] / pow (10, j-1)) dan
fx [i] = x [i] * sin (10 * * x [i]) + 10
jumlah = jumlah + fx [i];
langkah 5: if (max> = fx [i])
Langkah 6: maks ← fx [i];
Langkah 7: hingga m_max> maks
Langkah8: Hitung nilai maksimum
Tidak ada komentar:
Posting Komentar