Algoritma Genetika untuk Optimasi

Hello Gan, lama ane ga update ini Blog. Ternyata setelah lama ane ga buka sudah banyak sarang laba-labanya disana sini haha, tpi gpp sekarang sudah dibersihin dan semoga tetep ilmu yang ada dpet bermanfaat.

Ni Gan untuk kali ini ane coba share ilmu tentang Algoritma Genetika. (#makanan apaan tuh haha), biar ga penasaran langsung cek dan telusuri aja gan, semoga bermanfaat :).

PENGERTIAN

Algoritma Genetika atau nantinya sering disebut dengan ”AG” merupakan suatu metode optimasi berbasis pengetahuan biosains, yang mana mengadopsi sifat seleksi alam seperti sifat pindah silang, mutasi, pewarisan generasi atau keturunan, dan lain-lainnya. (#wkwkwk kata-kata pertama aj langsung ga jelas dan bikin pusing haha).

Nah optimasi tu pentingnya buat apa aja sih?? Ini banyak Sob, kebetulan ane orang Ketenagaan Listrik ya, jadi mungkin kalo di bidang ane AG bisa digunakan untuk mengoptimalkan suatu keadaan contoh :

a.    Pengoptimalan Daya Masing-masing pembangkit pada suatu sistem agar tercapai nilai biaya ekonomis (Economic Dispatch).

b.        Pengoptimalan Unit Commitment suatu sistem pembangkit.

c.         Pengoptimalan transfer daya listrik melalui FACTS.

d.       Posisi penempatan windturbine terbaik berdasarkan kondisi arah angin dan kecepatan angin.

e.         dan masih banyak lagi gan. :)

Tapi sebenarnya masih banyak lagi gan ga sebatas bisa digunakan di bidang listrik saja, bisa juga bidang Industri seperti Optimasi Jadwal Machine Operasi, bisa juga masalah rute TSP (Traveling Salesman Program), dan masalah di bidang-bidang lainnya pokoknya ada keterkaitan tentang optimasi maupun minimasi hehe.

Trus misal timbul pertanyaan Kenapa Harus Menggunakan Algoritma Genetika??

Kalo boleh adopsi kata iklan, Emm yang lebih sulit banyak haha. Loh, kenapa?? AG dikenal sebagai suatu metode optimasi yang terkenal kefleksibelannya karena hanya membutuhan input berupa fungsi tujuan dan mampu beradaptasi terhadap berbagai kekangan yang digunakan. Algoritma genetika mampu mencari solusi relatif lebih baik dibandingkan metode konvensional karena AG mencari berdasarkan sifat stochastic search serta AG mampu menghasilkan lebih dari satu solusi.

 Gambar 1. Ilustrasi AG vs Metode Konvensional

Nah mulai agak sedikit paham kan AG tu makanan apa haha, Emm untuk lebih tertariknya, Yuk mari kita telusuri lebih jauh proses-proses dalam AG itu seperti apa?

Dalam proses seleksi menggunakan AG dikenal berbagai macam istilah seperti populasi, kromosom, dan banyak variabel lainnya. Untuk lebih jelasnya proses atau tahapan mengenai algoritma genetika dapat dijelaskan sebagai berikut.

Inisialisasi Populasi

Inisialisasi populasi merupakan langkah awal dalam penyelesaian AG.  Dalam prosesnya populasi dilambangkan sebagai sebuah deretan bilangan biner 0 dan 1, yang tersusun atas kolom dan baris sehingga membentuk suatu matriks berisi bilangan biner. Pada satu  deret baris matriks tersusun atas beberapa kolom.  Satu deret baris matriks ini pada AG dikenal dengan istilah kromosom sedangkan jumlah kolom tersebut dikenal dengan istilah jumlah gen. Nilai jumlah gen tersebut  merupakan perkalian nilai Nvar(jumlah variabel) dan nilai Nbit (jumlah bit). Nvar merupakan jumlah variabel yang mewakili dari sebuah kromosom, dan Nbit yaitu jumlah bit biner yang mewakili sebuah variabel. Sedangkan jumlah baris pada sebuah matriks tersebut dikenal dengan istilah UkPop (Ukuran Populasi). Untuk lebih jelasnya dapat dilihat pada Gambar 2.

Gambar 2. Skema Populasi dalam AG

Dari Gambar 2 dapat diketahui informasi sebagai berikut.

Matriks Populasi Satu merupakan sebuah contoh inisialisasi populasi pada program AG, terdiri atas :        

            Kromosom ke-1          : [ 1 1 0 1 0 0 1 1 0]

            Kromosom ke-2          : [ 0 1 1 0 0 1 1 0 1]

            Kromosom ke-3          : [ 0 0 1 1 0 0 1 1 1]

            Nvar                            = 3 Variabel

            Nbit                             = 3 Bit

            Jumlah Gen                 = Nvar x Nbit

            Jumlah Gen                 = 9 buah

            Ukuran Populasi          = 3 buah

Setiap kromosom yang dihasilkan dari inisialisasi populasi merepresentasikan sebuah satu solusi, kemudian kromosom ini nantinya akan diproses pada proses AG selanjutnya.

Dekode Kromosom

Dekode Kromosom merupakan suatu cara pengkodean isi kromosom menjadi suatu nilai tertentu yang mana hasil dekodenya mewakili tiap variabel dan terdiri dari beberapa jumlah bit yang ada. Hal ini dilakukan guna untuk merepresentasikan sifat genotip dan fenotip yang ada dari suatu populasi. Sifat genotip dari populasi ini dilambangkan sebagai suatu deret biner yang ada pada kromosom, sedangkan sifat fenotipnya merupakan nilai hasil dekode dari kromosom yang ada. Sifat genotip ini dipakai saat pada proses pindah silang, mutasi, maupun tindakan genetis lainnya. Sedangkan sifat fenotip digunakan untuk mengetahui nilai mutu atau kualitas dari kromosom yang ada.

Pada umumnya dikenal dengan beberapa contoh skema pendekodean kromosom, yaitu antara lain :

1. Real number encoding. Pada skema ini nilai gen berada pada {x I 0<x<1, xER(+)}, yang mana berarti nilainya gen x terletak dimana x terletak diantara 0 sampai dengan 1, dimana x berupa elemen bilangan real positif, dan biasanya R=1.
2. Discrete decimal encoding. Pada skema pengkodean ini setiap gen bernilai salah satu bilangan bulat dalam interval 0 sampai dengan 9, {x I 0<x<9, xEB}.
3. Binary encoding. Pada skema pengkodean ini setiap gen bernilai 0 dan 1.

Untuk ilustrasi lebih jelasnya dapat dilihat pada Gambar 3.

Gambar 3. Skema Pengkodean Kromosom

Untuk prosedur pendekodean sendiri dapat dilihat sebagai berikut:

1. Real number encoding

x = r_b +(r_a- r_b)g                                                 (1)

sebagai contoh misal rb= -1 dan ra= 2 maka kromosom dapat didekodekan menjadi :

x₁= -1 + (2 – (-1))x0,239   = - 0,2830

x₂= -1 + (2 – (-1))x1,000   =  2,000

x₃= -1 + (2 – (-1))x0.0131 = -0.9607

2. Discrete decimal encoding

x = r_b + (r_a-r_b)(g₁x 10^-1 + g₂x10^-2 + . . . +g_Nx10^-N)                    (2)

sebagai contoh misal rb= -1 dan ra= 2 maka kromosom dapat didekodekan menjadi :

x₁ = -1 + (2 – (-1))( 2x 10^-1 + 3x10^-2 + 9x10^-3) = -0,2830

x₂=  -1 + (2 – (-1))( 9x 10^-1 + 9x10^-2 + 9x10^-3) = 1,9970

x₃=  -1 + (2 – (-1))( 0x 10^-1 + 1x10^-2 + 3x10^-3) = -0.9610

3. Binary encoding

x= r_b + (r_a – r_b)(g₁x2^-1 + g₂x2^-2 + . . . +g_Nx2^-N)                         (3)

sebagai contoh misal rb= -1 dan ra= 2 maka kromosom dapat didekodekan menjadi :

x₁ = -1 + (2 – (-1))( 0x 2^-1 + 1x2^-2 + 0x2^-3) = -0,25

x₂ = -1 + (2 – (-1))( 0x 2^-1 + 1x2^-2 + 0x2^-3) = 1,625

x₃ = -1 + (2 – (-1))( 0x 0^-1 + 0x2^-2 + 0x2^-3) = -1

 

Dari hasil pendekodean di atas terlihat bahwa untuk tipe pendekodean discrete encoding dan binary encoding tidak bisa merepresentasikan nilai sebenarnya sebab terbatas pada jumlah bit yang mewakilinya oleh karena perlu dilakukan pendekatan agar nilai hasil dekode mendekati nilai asli batasnya, yaitu dengan cara membagi nilai representasinya.Untuk lebih jelasnya maka diambil sampel hasil pendekodean pada kondisi x₂ dimana nilai Ra = 2 dan Rb =-1.

Dari hasil nilai pendekodean kromosom yang ada, maka didapat nilai hasil dekode seperti penjelasan di atas, dan nantinya nilai tersebut akan digunakan sebagai sifat fenotip dan digunakan untuk analisis nilai mutu dan kualitas hasil seleksi algoritma genetika. Untuk lebih jelasnya dapat dilihat pada Gambar 4.

  Gambar 4. Sifat dari kromosom GA

Persamaan Optimasi Fungsi Tujuan

Seperti pada proses pencarian solusi biasanya, nilai hasil pendekodean kromosom tadi akan dimasukkan ke dalam persamaan yang nantinya digunakan untuk menentukan titik global optimal dari grafik persamaan yang ada. Sebagai contoh untuk permasalahan fungsi kuadrat dengan persamaan y=x₁² + x₂² + x₃² +4, dengan batas bawah= -1 dan batas atas =2. Maka nilai fungsi tujuan kromosom tersebut adalah sebagai berikut.

Kromosom : [ 0 1 0 1 1 1 0 0 0] dengan Nvar=3 dan Nbit=3, maka hasil pendekodean secara biner dengan cara yang sama sesuai dengan persamaan binary encoding, maka didapat :

x₁ = - 0,1428   x₂= 2,000  x₃ = -1,000

sehingga apabila dimasukkan ke fungsi tujuan  y=x₁² + x₂² + x₃² +4 maka didapat:

y= x₁² + x₂² + x₃² +4

y= (-0.1428)² + 2,000² + -1,000² + 4

y= 7,0204

Kemudian nilai y=7,0204 ini yang nantinya akan dimasukkan ke dalam fungsi fitness dan akan dilakukan evaluasi individu pada setiap kromosom dari setiap populasi.

Persamaan Fungsi Fitness

Pada umumnya fungsi fitness ini terbagi atas dua tujuan yaitu fungsi untuk mencari maksimasi (nilai maksimum) dan untuk mencari nilai minimasi (nilai minimum). Dan rumusan secara umumnya sebagai berikut (Suyanto, 2010).

Masalah Maksimasi maka fungsi fitness = fungsi tujuan                        (4)

Masalah Minimasi maka fungsi fitness   = 1/(fungsi tujuan + Bilangan Kecil) (5)

Pada fungsi minimasi perlu ditambahkan dengan bilangan kecil guna untuk mencegah terjadinya nilai tak hingga, saat nilai fungsi tujuan bernilai 0.

Evaluasi Individu

Pada evaluasi individu dilakukan proses seleksi atas hasil nilai fungsi fitness dari setiap kromosom, dari proses seleksi inilah dijaring individu terbaik dari sekumpulan populasi yang ada, yang nantinya individu terbaik dari kromosom terbaiklah yang mampu bertahan, dan akan menjadi solusi atas permasalahan optimasi maupun minimasi dari suatu fungsi atau permasalahan yang ada.

Elitisme

Elitisme merupakan suatu prosedur untuk melakukan kopi dari kromosom terbaik, ke sebuah temporary populasi yang hal ini dimaksudkan agar individu terbaik tetap ada dan tidak hilang maupun rusak saat terjadi proses genetis berupa pindah silang dan mutasi, yang nantinya dari temporary populasi tersebut akan kembali dipindahkan ke populasi yang baru.

Linear Fitness Ranking

Linear Fitness Ranking (LFR)  merupakan metode penskalaan yang digunakan untuk menentukan batasan-batasan wilayah dari masing-masing fungsi fitness hasil solusi dari setiap kromosom. Batasan ini nantinya digunakan sebagai dasar penentuan pada proses pemilihan orang tua.

Tabel 1. Tabel LFR (Linear Fitness Ranking)

Sebagai contoh ilustrasi, dapat dilihat pada tabel yang menyimbolkan hasil evaluasi, seperti ditunjukkan oleh Tabel 1.

Roulette Wheel

Pada AG dikenal berbagai macam metode tentang bagaimana cara mencari kromosom yang akan dijadikan sebagai parental (orang tua) yaitu salah satu dari metode tersebut yaitu roulette wheel selection. Untuk lebih jelasnya dapat dilihat pada Gambar 5.

Gambar 5. Ilustrasi Roulette Wheel

Prinsipnya mirip kita memutar sebuah roda dengan adanya sebuah jarum penghenti, roda yang berputar tersebut berisikan nilai-nilai yang mewakili dari indeks orang tua yang ada. Dan indeks orang tua dari kromosom dipilih dari rentan nilai dimana jarum penunjuk roda itu berhenti. Begitulah analogi yang digunakan dalam menyusun pemilihan orang tua pada AG. Untuk proses detailnya, yaitu kita membangkitkan suatu nilai random antara 0 dan 1. Kemudian nilai hasil random tersebut digunakan untuk mengetahui indeks orang tua yang akan dipakai pada proses pindah silang, yang mana didapat berdasarkan nilai rentan yang sesuai pada LFR masing-masing kromosom. Sebagai contoh pada kondisi LFR di atas saat nilai random berhenti pada angka 0,67 maka indeks K2 lah yang terpilih sebagai orang tua.

Pindah Silang

Proses pindah silang inilah merupakan salah satu komponen paling penting dalam AG. Hal ini disebabkan dengan adanya pindah silang,  solusi yang dihasilkan akan menuju konvergen pada suatu titik tertentu secara acak, berbeda dengan metode iterasi konvensional yang sifatnya berupa hill climbing. Untuk lebih detailnya dapat dilihat pada Gambar 6.

Gambar 6. Ilustrasi Pindah Silang pada Kromosom

Terlihat dari hasil ilustrasi di atas bahwa proses pindah silang pada AG mirip dengan proses pindah silang pada proses genetis pada umumnya, dimana hasil pindah silang dalam hal ini disebut Anak 1 dan Anak 2 merupakan hasil percampuran gen genetis dari kedua orang tuanya. Sedangkan untuk proses konvergen solusi yang dihasilkan, dapat dilihat pada Gambar 7.

 Gambar 7. Komparasi Metode Iterasi Konvensional dengan metode iterasi AG

Dari Gambar 7., terlihat bahwa untuk proses konvensional proses iterasinya berjalan berurutan dan karena keteraturannya tersebut memungkinkan dapat terjebak pada lokal minimal. Oleh karena itu sekarang banyak dikembangkan metode pencarian berbasis pengetahuan biosains salah satunya adalah AG, karena dianggap mampu melakukan pencarian lebih baik dalam mendekati global optimal apabila dibandingkan dengan metode pencarian biasa.

Mutasi

Proses mutasi pada AG disini juga mirip dengan proses genetis pada umumnya. Pada AG proses mutasi dinyatakan dengan cara proses mengganti nilai gen yang terkena mutasi dengan nilai sebaliknya, seperti yang ditunjukkan pada Gambar 8.

Gambar 8. Ilustrasi Mutasi Kromosom

Sesuai dengan Gambar 8., pada kromosom X pada gen ke 10 dan pada gen ke 15 terjadi mutasi, sehingga mulanya indeks biner dari kromosom X pada gen-10 yang bernilai 0 berubah menjadi 1, dan begitu pula pada gen ke 15 indeks biner yang semula bernilai 1 berubah menjadi 0.

Penggantian Generasi

Pada proses akhir dari satu kali generasi AG ialah penggantian generasi. Generasi yang digantikan ialah generasi yang digunakan  sebagai populasi pertama pada proses AG, kemudian digantikan dengan populasi baru yang merupakan hasil seleksi dari proses Elitisme, Roullette Wheel, Pindah Silang, dan Mutasi. Dan Generasi baru inilah yang nantinya kan dipakai untuk proses AG berikutnya sebagai populasi yang baru. Proses ini berlanjut hingga beberapa generasi sampai didapat  fitness yang dianggap terbaik dari hasil proses AG tersebut atau saat generasi yang dihasilkan telah mencapai batas maksimal generasi.

Nah gimana gan, lumayan mudeng dan sedikit mumet ya, hhe. :p. Untuk sementara dipegang dulu gan konsep AG nya. InsyaAllah materinya dilanjut lagi tentang procedural AG nya, dan cara pengkodean programnya hhe. Semoga ilmu ini dapat bermanfaat gan hehe dan Salam Cerah..