Algoritma Genetik
MAKALAH
ALGORITMA GENETIK
Makalah ini Disusun Untuk Memenuhi Tugas Mata
Kuliah Peng. Tek. Sistem Cerdas yang Diberikan oleh Ibu Eel Susilowati, SKom,
MM
Nama Anggota
Kelompok :
Reza Fajriansyah (19114165)
Rico Prayoga (19114275)
Rifqi Sulthan Ikbari (19114381)
Riska Maghfira (19114493)
Riswan Fauzi (19114531)
Safira Amalia M (19114919)
Satya Dharmadi (1A114085)
Tb. Anugrah Prasetya (1A114902)
Yosua Kelvin (1C114484)
Kelas 3KA05
FAKULTAS
ILMU KOMPUTER & TEKNOLOGI INFORMASI
JURUSAN SISTEM INFORMASI
JURUSAN SISTEM INFORMASI
UNIVERSITAS
GUNADARMA
PENDAHULUAN
1.
Latar Belakang
Algoritma genetika adalah salah satu
metode metaheuristik yang digunakan untuk menyelesaikan permasalahan optimasi.
Algoritma genetika diciptakan pada tahun 1975oleh John Holland yang
mengemukakan komputasi berbasis evolusi dalam bukunya yang berjudul “Adaption in Natural and Artificial
Intelligence”. Tujuannya adalah untuk membuat mesin dapat melakukan apa
yang alam lakukan. Holland mengemukakan sebuah algoritma yang memfokuskan diri
pada manipulasi stringdalam bentuk binary bit yang diambil dari konsep abstrak
dari evolusi alam. Tahapan algoritma genetika yang dikemukakan dapat
direpresentasikan sebagai tahapan berurutan sebagai bentuk populasi dari
kromosom buatan menjadi sebuah populasi baru (Negnevitsky, 2005). Algoritma
genetika merupakan suatu mekanisme yang dapat melakukan pencarian dengan meniru
sistem seleksi alam dan genetika alamiah. Pengaplikasian algoritma genetika
biasanya menggambarkan proses evolusi, dengan menghasilkan kromosom-kromosom
dari tiap populasi secara acak dan memungkinkan kromosom tersebut berkembang
biak sesuai dengan hukum evolusi yang diharapkan akan dapat menghasilkan suatu
individu yang lebih baik lagi. Setelah didapat suatu individu yang baru
diharapkan individu tersebut dapat menjadi solusi yang baik dari permasalahan
yang dibahas. Sebutan untuk algoritma genetika yang umum digunakan adalah
algoritma genetika umum atau algoritma genetika klasik.
2.
Rumusan Masalah
1. Apa
pengertian algoritma genetik?
2. Bagaimana
sejarah algoritma genetik?
3. Bagaimana
tahapan proses algoritma genetik?
4. Apa
kelebihan algoritma genetik?
5. Apa
struktur umum algoritma genetik?
3.
Tujuan Penulisan
Tujuan penulisan makalah ini adalah
untuk menjelaskan tentang algoritma genetik dari pengertian, sejarah, tahapan
proses, kelebihan serta struktur umum.
ISI
1.
Pengertian Algoritma Genetik
Algoritma Genetika adalah suatu
algoritma pencarian yang bertujuan untuk mencari solusi dari suatu masalah,
baik dengan satu variable maupun multivariable. Metode ini meniru mekanisme
dari genetika alam yaitu untuk menemukan susunan-susunan gen yang terbaik dalam
tubuh makhluk hidup.
Dasar Algoritma Genetika adalah
teori evolusi Darwin, yang menjelaskan prinsip dasar terciptanya banyak spesies
makhluk hidup yang ada di dunia sekarang ini. Makhluk hidup yang dapat
beradaptasi dengan lebih baik terhadap lingkungannya akan mempunyai kesempatan
yang lebih besar untuk bertahan hidup dan bereproduksi sehingga mempengaruhi
jumlah populasi spesies yang bersangkutan di waktu-waktu selanjutnya.
Dalam perkembangannya, metode
Algoritma Genetika banyak dipakai dalam berbagai disiplin ilmu. Algoritma ini
digunakan untuk menyekesaikan kasus-kasus yang mempunyai banyak solusi, dimana
tidak ada kepastian solusi yang terbaik. Sehingga dalam penyelesaian
masalah tersebut akan membutuhkan waktu yang sangat lama. Setiap solusi
Algoritma Genetika diwakili oleh suatu individu atau satu kromosom. Keuntungan
Algoritma Genetika adalah sifat metode pencariannya yang lebih optimal, tanpa
terlalu memperbesar ruang pencarian, dan tanpa kehilangan kelengkapannya.
Melalui persilangan dan mutasi,
akan ada individu-individu yang baru pada populasi sebagai populasi generasi.
Persilangan atau mutasi akan dilakukan lagi sehingga populasi yang baru dapat
menemukan nilai pembandingnya. Proses ini akan diulangi selama beberapa
generasi hingga dihasilkan suatu hasil yang optimal.
2.
Sejarah Algoritma Genetik
Algoritma Genetika pertama kali
ditemukan oleh John Holland pada tahun 1960-an dan kemudian dikembangkan
bersama murid-murid dan rekan kerjanya di Universitas Michigan pada tahun
1970-an. Tujuan Holland mengembangkan Algoritma Genetika saat itu bukan untuk
mendesain suatu algoritma yang dapat memecahkan suatu masalah, namun lebih
mengarah ke study mengenai fenomena adaptasi yang terjadi di alam dan mencoba
menerapkan mekanisme adaptasi alam tersebut kedalam system computer.
Algoritma Genetika yang dibuat
Holland merupakan sebuah metode untuk memindahkan suatu populasi kromosom
(terdiri dari bit-bit 1 dan 0 ) ke populasi baru dengan menggunakan “ seleksi
alam “ dan operator genetic seperti :
1. Crossover
menukar bagian kecil dari dua
kromosom
2. Mutasi
mengganti secara acak nilai gen
beberapa lokasi pada kromosom,
3. Inversion
membalikkan urutan beberapa gen
yang berurutan dalam kromosom.
Dasar teori inilah yang menjadi
dasar kebanyakan program yang menggunakan Algoritma Genetika.
3.
Tahapan Proses Algoritma Genetik
Pada dasarnya, algoritma genetika dapat dilakukan
melalui lima tahap yaitu sebagai berikut :
- Membentuk Populasi Awal
Langkah pertama dalam algoritma
genetika adalah membentuk sebuah populasi untuk sejumlah gen. populasi itu
sendiri merupakan sekumpulan solusi yang akan digunakan dalam proses regenerasi
selanjutnya untuk mencari solusi terbaik. Solusi-solusi yang ada selanjutnya
disebut sebagai individu.
- Mencari Fitness Cost
Pada tahap ini setiap individu
yang terbentuk dicari fitness cost-nya sebagai nilai pembanding antara individu
satu dengan yang lainnya.
- Pengurutan (Sorting)
Pada tahap ini, individu yang
terdapat pada populasi diurutkan berdasarkan fitness costnya. Tujuan utamanya
adalah untuk mencari individu terbaik pada populasi yang ada, yang dapat
dikatakan sebagai solusi sementara.
- Proses Regenerasi
Proses ini terdapat dua metode
yaitu :
· Elitism
Method
Metode
dimana individu-individu yang akan mengalmi proses regenerasi, yaitu proses
mutasi dan crossover adalah individu-individu dengan nilai fitness yang rendah,
sedangkan individu dengan nilai fitness tertinggi atau gen terbaik akan
dipertahankan untuk dibandingkan lagi dengan individu hasil proses regenerasi.
· Non
Elitms
Suatu
metode regenerasi yang melibatkan semua individu baik individu / gen terbaik
maupun gen yang kurang baik (individu dengan nilai fitness rendah).
- Tahapan Pengulangan
Setelah proses regenerasi
selesai, maka dilakukan pengulangan proses ini sampai sejumlah generasi yang
dikehendaki.
4.
Kelebihan Algoritma Genetik
Beberapa
hal yang termasuk kelebihan dari Algoritma Genetika adalah sebagai berikut
(Haupt dan Haupt, 2004):
- Mengoptimalkan dengan variabel kontinu atau diskrit,
- Tidak memerlukan informasi derivatif,
- Bersamaan pencarian dari sebuah sampling yang luas pada permukaan biaya,
- Berkaitan dengan sejumlah besar variabel,
- Baik untuk komputer paralel,
- Mengoptimalkan permukaan variabel dengan biaya yang sangat kompleks (GA bisa melompat dari minimum lokal),
- Memberikan daftar variabel yang optimal, bukan hanya solusi tunggal,
- Dapat menyandikan variabel sehingga optimasi dilakukan dengan mengkodekan variabel, dan
- Bekerja dengan data numerik yang dihasilkan, data eksperimen, atau analitis fungsi.
5.
Struktur Umum Algoritma Genetik
Struktur
umum algoritma genetik dapat diilustrasikan dalam diagram
alir berikut ini:
Inisialisasi populasi awal
dilakukan untuk menghasilkan solusi awal dari suatu permasalahan algoritma
genetika. Inisialisasi ini dilakukan secara acak sebanyak jumlah
kromosom/populasi yang diinginkan. Selanjutnya dihitung nilai fitness dan
seterusnya dilakukan seleksi dengan menggunakan metode roda roullete,
tournament atau ranking. Kemudian dilakukan perkawinan silang (crossover)
dan mutasi. Setelah melalui beberapa generasi maka algoritma ini akan berhenti
sebanyak generasi yang diinginkan.
6. Karakteristik Algoritma Genetik
Goldberg (1989) mengemukakan bahwa algoritma
genetika mempunyai karakteristik-karakteristik yang perlu diketahui sehingga
dapat terbedakan dari prosedur pencarian atau optimasi yang lain yaitu:
- AG bekerja dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri. Sebagai contoh untuk mendapatkan minimum dari fungsi f(x)=y=x4+2x3+5, AG tidak secara langsung mencari nilai x atau y, tetapi terlebih dahulu merepresentasikan x dalam bentuk string biner.
- AG melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.
- AG merupakan informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi.
- AG menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik
KESIMPULAN
Algoritma
genetik adalah
teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian
perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah
kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang
terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan
rekombinasi (atau crossover). Algoritma Genetik pertama kali
dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat.
Sebelum algoritma genetika
dilakukan, ada dua hal penting yang harus dilakukan yaitu pendefinisian
kromosom yang merupakan suatu solusi yang masih berbentuk simbol dan fungsi fitness
atau fungsi obyektif. Dua hal ini berperan penting dalam algoritma genetika
untuk menyelesaikan suatu masalah.
Referensi
http://singgihawi.blogspot.co.id/2011/04/algoritma-genetika.html
http://informatika.web.id/algoritma-genetika.html
http://repository.usu.ac.id/bitstream/123456789/55989/5/Chapter%20I.pdf
