BAB 3 FUZZY
Fuzzy merupakan salah satu pendekatan dari K ecerdasan Komputasional untuk mengolah uncertainty information dan pengambilan kesimpulan dengan menggunakan bahasa natural. Bahasa Natural ini digunakan untuk merepresentasikan domain permasalah, aturan, ataupun domain solusi, sebagai pengganti angaka. Misalkan suhu sangat panas, kecepatan mobil kurang cepat, nilai mahasiswa yang rendah, dan lain-lain. Sehingga dengan representasi ini, maka fuzy dapat menghasilkan human reasoning. Fuzzy untuk reasorning atau pengambilan keputusan akan dijelaskan pada subbab berikut, yang didahului dengan pembahasan Himpunan Fuzzy, Logika Fuzzy, dan proses reasorning atau inferencing itu sendiri. 3.1 Himpunan Fuzzy Crisp Set merupakan suatu himpunan di mana elemenya hanya memiliki dua kemungkinan saja yaitu apakah elemen tersebut merupkan anggota dari suatu himpunan atau tidak, atau sering juga dikenal dengan logika Boolean yaitu yang memiliki kemungkinan nilai 0 dan 1 saja, atau true dan false. ...
KOMPUTASI EVOLUSI
Setiap organisme mahluk hidup pasti akan berevolusi agar dapat beradaptasi dengan lingkungannya yang selalu berubah dan tetap bertahan dalam lingkungan tersebut. Hasil adaptasi iniakan terus diwariskan ke generasi-generasi berikutnya. Generasi berikutnya juga tetap akan berevolusi agar mereka dapat bertahan di lingkungan yang selalu dinamis. Hanya saja terkadang di dalam proses untuk menghasilkan generasi baru, terdapat suatu kejadian tertentu yang tidak dapat dihindari, sehingga dapat menyebabkan perubahan sitat dari generasi tersebut, jika sifat tersebut mampu membantu para generasi baru untuk bertahan, maka sifat tersebut akan dipertahankan dan diwariskan untuk generasi berikutnya.
Algoritma Genetika
Genetic Algorithm atau Algoritma Genetika merupakan salah satu algoritma dari Komputasi Evolusi yang mensimulasikan evolusi gen individu yang terbaik, dan mengoperasikan operator Algoritma untuk memecahkan suatu permasalahan, dengan cara memilih Genetika terhadap gen-gen tersebut. Seperti halnya Komputasi Evolusi yang lain, Algoritma Genetika ini juga berdasarkan pada prinsip Darwin yaitu, prinsip reproduksi dan survival of the fittest, yaitu generasi baru dihasilkan dari proses seleksi dan reproduksi. Individu yang memiliki kualitas yang diinginkanlah yang akan bertahan dan menjadi individu terpilih sebagai solusi permasalahan.
Algoritmna Genetika ini digunakan untuk memecahkan Permasalahan Optimasi, yaitu permasalahan yang memiliki banyak kemungkinan solusi, dan algoritma ini akan mencari solusi yang terbaik dari kemungkinan-kemungkinan solusi yang ada di dalam ruang pencarian. Penjadwalan merupakan salah satu Permasalahan Optimasi yang sering ditemui dalam kehidupan sehari-hari.
Untuk memecahkan Permasalahan Optimasi tersebut, Algoritma Genetika merepresentasikan kandidiat-kandidat solusi tersebut dengan individu atau Kromosom yang terdiri dari beberapa gen, dan operasi-operasi Algoritma Genetika ini dilakukan terhadap gen-gen tersebut. Sebelum pembahasan mengenai Algoritma Genetika, berikut beberapa istilah dan proses penting yang terdapat pada Algoritma Genetika ini, antara lain:
· Populasi, Individu, Kromosom, dan Gen
· Fitness Function
· Seleksi, offspring
· Crossover
· Mutasi
· Elitist Strategy
Atribut Algoritma Genetika
Atribut yang harus disiapkan agar Algoritma Genetika dapat melakukan operasi genetika untuk menyelesaikan Permasalahan Optimasi adalah penentuan representasi individu atau yang dikenal dengan encoding schema dan penentuan Fungsi Fitness.
1. Representasi Individu
Tahap pertama yang harus dilakukan untuk penyelesaian masalah optimasi dengan menggunakan Algoritma Genetika ini adalah ini adalah penentuan bentuk individu atau encoding. Individu inilah yang akan merepresentasikan kandidat solusi dari Permasalahan Optimasi. Seperti
yang dijelaskan sebelumnya, Algoritma Genetika mensimuiasikan evolusi gen, oleh karena itu individu-individu atau juga disebut dengan Kromosom, disusun atas beberapa gen, dan operasi Algoritma Genetika dilakukan pada gen-gen tersebut.
Individu atau Kromosom ini dapat direpresentasikan dalam berbagai bentuk, misalkan biner, string, nilai integer, dan lain-lain, tergantung permasalahan yang akan diselesaikan. Syarat yang harus dimiliki untuk representasi individu ini adalah:
· Pengkodean kromosom atau individu yang dibuat mampu mewakili kemungkinan-kemungkinan solusi.
· Pengkodean kromosom atau individu dibuat sedemikan rupa sehingga mudah untuk dilakukan operasi seleksi, operasi crossover maupun mutasi.
Masing-masing bit pada Kromosom atau individu tersebut biasa dikenal dengan nama gen. Dan pada tahap inisialisasi dari Algoritma Genetika, sejumlah individu atau kromosom ini akan dibangkitkan secara acak. Kumpulan individu atau kromosom tersebut dikenal dengan nama dengan Populasi.
2. Fungsi Fitness
Tujuan dari Algoritma Genetika adalah mencari solusi yang optimal diantara kemungkinan solusi pada Permasalahan Optimasi. Solusi yang optimal ini diperoleh berdasarkan Fungsi Fitness, di mana Fungsi Fitness mengukur seberapa tepatkah suatu Kromosom atau indlvidu menjadi solusi permasalahan. Semakin besar nilai fitness ini, maka semakin tepat kromosom tersebut menjadi solusi optimal dari Permasalahan Optimasi.
Berikut akan dijelaskan masing-masing tahapan pada Algoritma Genetika.
2.1 Seleksi
Seleksi merupakan suatu operasi pada Algoritma Genetika yang memilih Kromosom-kromosom atau individu yang berkualitas untuk proser reproduksi selanjutnya. Kromosom-kromosom yang terpilih terpilih nantinya akan disebut sebagai parents. Pemilihan kromosom ini dilakukan dengan harapan, bahwa keturunan (offspring ) yang dihasilkan pada proses reproduksi, adalah keturunan yang berkualitas karena berasal dari parents yang berkualitas.
Pada proses seleksi ini, pemilihan kelayakan setiap kromosom dihitung berdasarkan Fungsi Fitness yang telah ditentukan sebelumnya. Semakin besar nilai fitness yang dimiliki oleh suatu Kromosom, maka semakin besar pula kemungkinan kromosom tersebut terpilih menjadi parents. Oleh karena itu tidak menutup kemungkinan bahwa suatu kromosom dengan nilai fitness yang besar, akan terpilih lebih dari satu kali pada proses seleksi ini. Sebaliknya, jika suatu kromosom memiliki nilai fitness kecil, maka tidak menutup kemungkinan bahwa kromosom tersebut tidak terpilih untuk dijadikan parents pada proses reproduksi selanjutnya.
Terdapat dua metode dasar dari proses seleksi ini, yaitu:
· Roulette Wheel Selection . Pada metode ini setiap kromosom dipilih berdasarkan probabilitas nilai fitness dari masing-masing kromosom tersebut.
· Rank Based Selection. Pada metode roulette wheel, jika kromosom memiliki nilai fitness yang besar, kemungkinan besar pula kromosom tersebut dipilih beberapa kali pada proses seleksi, sehingga tidak ada variasi kromosom untuk dijadikan parents pada proses selanjutnya. Oleh karena itu, pada metode ini, probabilitas seleksi sudah ditentukan sebelumnya berdasarkan rangking. Oleh karena itu metode rank based selection ini menggunakan nilai probabilitas seleksi yang tetap (berdasarkan peringkat nilai fitness), dengan harapan Kromosom tidak dipilih sampai beberapa kali sehingga tidak ada variasi parents.
2.2 Crossover
Setelah beberapa Kromosom telah dipilih pada proses seleksi, kromosom-kromosom ini akan dijadikan parents pada proses crossover. Pada proses ini, pasangan parents akan dicrossover, yaitu dilakukan penukaran gen-gen kromosom dari sepasang parents, sehingga dihasilkan individu atau kromosom baru. Individu atau kromosom ini disebut dengan offspring.
2.3 Mutasi
Kromosom offspring yang diperoleh dari proses reproduksi sebelumnya, digunakan untuk proses mutasi. Pada proses mutasi ini, gen yang terpilih dari suatu kromosom akan berubah. Misalkan representasi kromosom yang digunakan adalah string biner, maka gen 0 bermutasi menjadi 1 atau sebaliknya. Perubahan gen ini dimaksudkan agar individu yang dihasilkan berbeda dengan parents.
2.4 Replacement proses akhir
Secara umum, semua kromosom yang dihasilkan pada proses akhir Algoritma Genetika, yaitu mutasi, digunakan sebagai populasi untuk iterasi atau generasi berikutnya. Populasi baru ini akan diproses kembali mulai dari seleksi, crossover, dan mutasi, sehingga didapatkan populasi dengan komposisi yang baru kembali.
Pengaruh Elitist Strategy pada Algoritma Genetika untuk Pencarian Rute Terpendek dari Permasalahan TSP
Berbagai variabel yang dapat diteliti pada Algoritma Genetika untuk meningkatkan kinerja mulai dari solusi yang ditawarkan sampai dengan waktu komputasi yang dibutuhkan. Beberapa penelitian, telah dipublikasi untuk meneliti berbagai variabel ini khususnya untuk permasalahan
Travelling Salesman Problem (TSP), seperti optimasi pencarian parents yang akan digunakan untuk proses crossover, modifikasi tahapan mutasi, generation with replacement untuk memiliih individu-individu yang akan diproses di generasi berikutnya, dll [6], [91, [10].
Ringkasan
· Algoritma genetika merupakan salah satu metode yang terdapat pada paradigma komputasi evolusi dalam memecahkan permasalahan optimasi (yaitu permasalahan yang memiliki beberapa kandidat solusi).
· Algoritmna genetika dibangun berdasarkan teori Darwin tentang reproduksi dan survival of the fittest, yaitu algoritma ini akan melahirkan generasi-generasi baru melalui proses seleksi dan reproduksi.
· Terdapat lima tahapan utama yang dibutuhkan dalam algoritma genetika ini untuk menyelesaikan permasalahan optimasi, yaitu encoding, penentuan fungsi fitness, seleksi, crossover, dan mutasi.
· Encodingg merupakan penentuan representasi dari kandidat solusi. Representasi ini disebut juga dengan individu atau kromosom, dimana setiap kromosom terdiri dari beberapa gen.
· Fungsi fitness adalah fungsi yang menentukan apakah suatu individu atau kromosom yang dihasilkan atau dibentuk merupakan solusi yang optimal pada permasalahan optimasi. Semakin besar nilai fitness maka semakin optimal solusi yang dibentuk oleh kandidat solusi tersebut.
· Seleksi merupakan proses pemilihan individu atau kromosom yang tepat untuk proses berikutnya berdasarkan nilai fitness dari masing- masing individu tersebut. Metode yang sering digunakan untuk proses seleksi ini adalah Roulette wheel dan Rank based selection. Individu-individu hasil seleksi disebut dengan offspring.
· Crossover merupakan proses reproduksi pada algoritma genetika. Crossover dilakukan pada offspring-offspring yang dihasilkan dari proses seleksi. Dari proses crossOver ini akan dihasilkan individu-individu baru
· Mutasi adalah proses perubahan gen-gen yang terdapat pada pada kromosom hasil dari proses crossover. Dengan proses mutasi ini maka akan dihasilkan individu-individu baru.
· Proses seleksi, crossover, dan mutasi akan dilakukan terus menerus sampai jumlah generasi yang telah ditentukan sebelumnya. Individu terbaik, yaitu individu yang memiliki nilai fitness terbesar adalah solusi terbaik untuk permasalahan optimasi.
Comments