Algoritma EO (Evolutionary Optimization)


Algoritma EO (Evolutionary Optimization) adalah salah satu algoritma optimasi yang dapat digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi minimal.
Evolutionary Optimization adalah algoritma yang menggunakan mekanisme seleksi biologi, seperti seleksi, reproduksi, rekombinasi dan mutasi. Calon solusi permasalahan diibaratkan sebagai individu dalam sebuah populasi, dan nilai fitness akan menentukan seberapa baik individu tersebut dapat bertahan.
Algoritma ini merupakan salah satu variasi dari Algoritma GA (Genetic Algorithm) / Genetika Algoritma, oleh karena itu memiliki struktur yang sama seperti perhitungan fitness, crossover dan mutasi. Implementasi algoritma ini dapat pula diterapkan untuk pencarian matriks bobot dalam algoritma berbasis jaringan.



Diasumsikan ada sebaran titik 3 dimensi, yaitu dimensi x, y, z
Masing-masing dimensi memiliki sebuah konstanta dan batas rentang titik yang dapat digunakan
Contoh data pada masing-masing dimensi adalah sebagai berikut

Dimensi konstanta batas minimal batas maksimal
x 3.2 10 50
y 3 30 80
z 2.5 50 150

Contoh data awal adalah sebagai berikut:



Nilai fungsi yang diketahui adalah dengan rumus f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)
Tentukan posisi dimana fungsi tersebut mengembalikan nilai minimal
Dengan batasan nilai bahwa x + y + z harus bernilai 210



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan dimensi permasalahan (jumlah gen) dalam sebuah solusi (kromosom)
Diasumsikan dalam kasus ini, dimensi bernilai 3 karena ada 3 dimensi yang akan dicari solusinya

* Tentukan popsize / ukuran populasi
nilai yang direkomendasikan adalah 10 sampai dengan 1000
Diasumsikan dalam kasus ini, ukuran popsize adalah 20

* Tentukan probabilitas mutasi, yaitu besar kemungkinan sebuah gen akan bermutasi
nilai yang direkomendasikan adalah 0.1 sampai dengan 0.5
Diasumsikan dalam kasus ini, probabilitas mutasi adalah 0.2

* Tentukan konstanta pergerakan gen pada saat bermutasi
semakin besar nilai ini, maka semakin luas area perpindahan gen pada saat bermutasi
nilai yang direkomendasikan adalah 0.001 sampai dengan 0.1
Diasumsikan dalam kasus ini, konstanta pergerakan gen adalah 0.01

* Tentukan tau, yaitu persentase jumlah kromosom induk yang terpilih untuk kemudian dicari induk terbaiknya
nilai yang direkomendasikan adalah 0.3 sampai dengan 0.7
Diasumsikan dalam kasus ini, tau bernilai 0.4

* Tentukan jumlah maksimal iterasi / generasi yang dilakukan
Diasumsikan dalam kasus ini, jumlah maksimal iterasi adalah 1000

* Tentukan batas nilai fungsi yang paling rendah
Jika nilai fungsi yang ditemukan sudah kurang dari nilai ini, maka perhitungan sudah selesai
Diasumsikan dalam kasus ini, batas nilai fungsi yang paling rendah adalah 0.00001

* Tentukan total posisi yang harus dicapai
Semua solusi yang ditemukan oleh masing-masing individu harus berjumlah sebanyak variabel ini
Diasumsikan dalam kasus ini, total nilai yang harus dicapai adalah 210


Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini (poin 1 – 3)

Memasuki fungsi prosesPerhitungan untuk melakukan pencarian posisi terbaik

1. Inisialisasi individu sebanyak parameter popsize, dan inisialisasi posisi nya sebanyak parameter dimensi
Untuk setiap individu, Beri nilai kromosom acak pada setiap dimensi
Kemudian hitung nilai fungsi untuk individu pada posisi tersebut

2. Untuk masing-masing individu awal, lakukan pengecekan apakah individu ini berada pada posisi terbaik

3. Lakukan proses pencarian posisi terbaik sebanyak jumlah perulangan (poin 3a – 3e)

3a. Tentukan 2 data induk pada populasi, yang kira-kira memiliki nilai fungsi yang cukup rendah

3a1. Lakukan pengacakan urutan indeks populasi, sehingga populasi yang dipilih tidak akan berurutan

3a2. Tentukan banyak calon induk yang akan dipilih
Kemudian ambil induk acak sebanyak jumlah calon induk
Urutkan calon induk acak, kemudian ambil 2 data teratas untuk menjadi jawaban 2 data induk yang dicari

3b. Buat 2 data anak dari 2 data induk yang sudah dipilih sebelumnya

3b1. Lakukan proses crossover
Buat 2 individu anak yang baru
Masukan sebagian kromosom induk 1 dan sebagian kromosom induk 2 kepada anak 1
Masukan sebagian kromosom induk 2 dan sebagian kromosom induk 1 kepada anak 2

3b2. Lakukan proses mutasi
Pada masing-masing kromosom anak1
Apabila termasuk dalam probabilitas mutasi, maka lakukan proses mutasi pada kromosom tersebut
Yaitu dengan menambahkan nilai acak pada kromosom tersebut

3b3. Perlu diingat bahwa apabila nilai posisi baru melebihi batas nilai minimal dan maksimal pada masing-masing dimensi,
maka kembalikan nilai posisi nya agar kembali dalam rentang nilai pada dimensi tersebut

3b4. Sama seperti perhitungan sebelumnya, jumlah posisi diatas belum tentu sesuai dengan parameter totalPosisi
Oleh karena itu, lakukan penyesuaian posisi agar jumlah posisi selalu bernilai sama dengan parameter totalPosisi

3b5. Lakukan proses mutasi yang sama (poin 3b2 – 3b4) untuk individu anak 2

3b6. Setelah proses crossover dan mutasi, hitung nilai fungsi pada masing-masing anak
Kemudian masukkan 2 individu anak ini sebagai jawaban individu anak

* Gunakan fungsi ini untuk menghitung nilai fungsi individu tersebut
Rumus yang digunakan adalah sesuai dengan rumus yang sudah ditentukan, yaitu
f(x, y, z) = (kx * x^2) + (ky * y^2) + (kz * z^2)

3c. Urutkan populasi induk, kemudian masukkan 2 data anak untuk menggantikan 2 data induk yang paling buruk (nilai fungsi tertinggi)

3d. Buat 1 individu acak untuk menggantikan individu induk dengan posisi ketiga terburuk

3e. Hitung nilai fungsi pada 3 data yang baru, yaitu 2 data anak dan 1 data individu acak
Jika nilai fungsinya lebih rendah dari nilai fungsi terbaik, ambil individu tersebut sebagai solusi terbaik
Jika nilai fungsinya lebih rendah dari batas minimal nilai fungsi, maka hentikan perhitungan

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Individu untuk menampung semua data kromosom, nilai fungsi, jumlah gen, probabilitas mutasi, dan konstanta pergerakan gen. Deklarasi Class Individu adalah sebagai berikut:


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd47


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *