Algoritma Evolusi Teknik Optimasi

Algoritma Evolusi

Teknik Optimasi Imam Cholissodin | [email protected]

Pokok Bahasan 1. 2. 3. 4.

Pengantar Klasifikasi Teknik Optimasi Prinsip Kerja Algoritma Evolusi Tugas

Pengantar (1 of 3)  Dalam kehidupan sehari-hari seringkali kita berhadapan dengan pencarian solusi suatu masalah seperti contoh berikut: o Pembuatan jadwal kuliah yang mencakup ketersediaan dosen dan ruangan. Jadwal harus dibuat tujuan untuk menghindari seorang dosen/mahasiswa terjadwal di lebih dari satu kelas pada waktu yang sama. o Persoalan transportasi yang mencakup pendistribusian suatu komoditas atau produk dari sejumlah sumber kepada sejumlah tujuan dengan tujuan meminimumkan ongkos pengangkutan yang terjadi. o Pemilihan rute terpendek (biaya terkecil) untuk mengunjungi sejumlah kota. o Penentuan komposisi makanan ternak dengan biaya minimum yang harus memenuhi batasan minimal untuk setiap komponen nutrisi.

Pengantar (2 of 3)  Penyelesaian masalah di atas akan mudah dilakukan jika ukuran data relatif kecil.  Masalah akan menjadi kompleks jika data berukuran besar atau melibatkan sejumlah entitas besar.  Pada masalah kompleks dibutuhkan juga formulasi matematika yang kompleks yang bisa jadi sangat sulit dibangun atau membutuhkan waktu yang lama.  Berdasarkan model matematis yang dibangun bisa dilakukan analisis untuk mencari solusi yang terbaik (optimum). Solusi optimum mungkin dapat diperoleh tetapi memerlukan proses perhitungan yang panjang.

Pengantar (3 of 3)  Untuk penyelesaikan kasus khusus seperti di atas dapat digunakan metode heuristik, yaitu suatu metode pencarian yang didasarkan atas intuisi atau aturanaturan empiris untuk memperoleh solusi yang lebih baik daripada solusi yang telah dicapai sebelumnya.  Metode ini tidak selalu menghasilkan solusi optimum tetapi jika dirancang dengan baik akan menghasilkan solusi yang mendekati optimum dalam waktu yang relatif cepat.  Metode heuristis yang bisa diterapkan pada masalah optimasi misalnya algoritma koloni semut, algoritma hillclimbing, tabu search, algoritma simulated annealing dan algoritma evolusi.

Klasifikasi Teknik Optimasi (1 of 4)  Secara umum, posisi dari EAs di antara teknik optimasi lainnya ditunjukkan pada Gambar berikut :

Klasifikasi Teknik Optimasi (2 of 4)  Algoritma evolusi (evolutionary algorithms, EAs) merupakan subset dari komputasi evolusi (evolutionary computation, EC) yang merupakan bentuk generik dari algoritma optimasi meta-heuristic berbasis populasi.  Pada Gambar tersebut, optimization didefinisikan sebagai proses pemilihan sebuah solusi dari sejumlah alternatif solusi dengan memenuhi sejumlah batasan (contstraints).  Misalkan pada pencarian rute untuk mengunjungi sejumlah kota. Pada kasus ini tentu saja terdapat banyak alternatif pilihan rute (solusi).  Solusi yang dipilih disesuaikan dengan tujuan (objective) dari permasalahan ini, misalkan memilih rute terpendek atau rute dengan waktu tempuh tercepat. Batasan yang ada misalkan setiap kota harus dikunjungi tepat satu kali.

Klasifikasi Teknik Optimasi (3 of 4)  Stochastic optimization menggunakan bilangan acak (random) dalam pencarian solusi. Sebagai konsekuensinya, sebuah algoritma dalam kelas ini setiap dijalankan akan menghasilkan solusi akhir yang berbeda, meskipun diterapkan dalam permasalahan yang sama.  Sebuah algoritma meta-heuristic bertindak sebagai ‘manajer’ dari beberapa algoritma heuristic yang secara terorganisir mencari solusi dari sebuah permasalahan.  Misalkan metode Variable Neighborhood Search (VNS) yang memanage sebuah teknik local search (LS). VNS secara sistematis meng-iterasi LS untuk mencari solusi dari titik awal yang berbeda serta mencakup area pencarian yang lebih luas. Contoh lainnya adalah algoritma genetika yang me-manage beberapa genetic operator seperti crossover, mutation, dan selection. (Materi ini akan dijelaskan secara mendetail pada pert. ke-3).

Klasifikasi Teknik Optimasi (4 of 4)  Evolutionary

computing merujuk kepada berbagai teknik penyelesaian masalah yang berbasis proses evolusi biologi seperti seleksi alam (natural selection) dan penurunan sifat genetis (genetic inheritance).  Berbagai teknik dalam kelas ini telah diaplikasikan pada berbagai permasalahan praktis. Salah satu sub-kelas dari evolutionary computing adalah algoritma evolusi yang sedang anda pelajari.

Prinsip Kerja ALEV (1 of 3)  Algoritma Evolusi (evolutionary algorithms, EAs) merupakan teknik optimasi yang meniru proses evolusi biologi.  Menurut teori evolusi terdapat sejumlah individu dalam populasi. Dari generasi ke generasi, individu-individu ini berperan sebagai induk (parent) yang melakukan reproduksi menghasilkan keturunan (offspring).  Individu-individu ini (beserta offspring) berevolusi dan individuindividu yang lebih baik (mampu beradaptasi dengan lingkungannya) mempunyai peluang lebih besar untuk melewati seleksi alam (natural selection) dan bertahan hidup.  Individu yang lebih baik juga cenderung (tidak selalu tapi mempunyai kemungkinan lebih besar) menghasilkan keturunan yang lebih baik, sehingga dari generasi ke generasi akan terbentuk populasi yang lebih baik.

Prinsip Kerja ALEV (2 of 3)  Keseluruhan proses dalam EAs ditunjukkan pada Gambar berikut : Individu dalam populasi

Pemilihan parent

Hasil reproduksi (offspring)

Seleksi alam

Himpunan individu baru

 Individu-individu dalam populasi di EAs merepresentasikan solusi dari masalah yang akan diselesaikan.  Sebuah fungsi fitness digunakan untuk mengukur seberapa baik suatu individu. Individu terbaik di akhir generasi bisa didekodekan sebagai solusi terbaik yang bisa diperoleh.  Dari penjelasan di atas, EAs bisa dikelompokkan dalam algoritma ‘generate and test’ yang berbasis populasi (population based). EAs juga bersifat stochastic, setiap kali dijalankan untuk masalah yang sama ada kemungkinan menghasilkan solusi yang berbeda.

Prinsip Kerja ALEV (3 of 3)  Berbagai tipe EAs telah dikembangkan sebagai berikut: o Algoritma genetika (Genetic Algorithms, GAs), merupakan tipe EAs yang paling popular dan banyak diterapkan pada masalah-masalah kompleks. Pada awalnya banyak menggunakan representasi string biner tapi kemudian berkembang dengan menggunakan vektor bilangan integer dan pecahan (real). Pembangkitkan solusi baru banyak mengandalkan proses tukar silang (crossover). Mutasi biasanya dipakai sebagai operator tambahan untuk menjaga keragaman populasi. o Evolution Strategies (ES), representasi solusi biasanya menggunakan vektor bilangan pecahan. Mutasi merupakan operator reproduksi utama. Mekanisme self-adaptation digunakan untuk mengontrol perubahan nilai parameter pencarian. o Genetic Programming (GP), digunakan untuk mengoptimasi rangkaian program komputer yang direpresentasikan dalam bentuk struktur data pohon (tree). o Evolutionary Programming (EP), mempunyai tujuan seperti GP tapi prinsip kerjanya seperti ES. Finite State Machines (FSM) digunakan untuk merepresentasikan program komputer.

Tugas Kelompok 1. Pada jenis permasalahan apa algoritma heuristik seharusnya diterapkan? 2. Jelaskan apa yang dimaksud dengan gen, individu, populasi, generasi dalam algoritma evolusi! 3. Apa yang dimaksud dengan fungsi fitness? 4. Apa yang dimaksud dengan pernyataan bahwa algoritma evolusi bersifat stochastic? 5. Jelaskan perbedaan antara Soft Contstraints dan Hard Contstraints, dan berikan contohnya! Note : Untuk memperjelas pemahaman anda, kerjakanlah latihan berikut sebisa mungkin tanpa melihat materi pada buku atau slide!

Terimakasih Imam Cholissodin | [email protected]