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
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