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=x⁴+2x³+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://informatika.web.id/struktur-umum-algoritma-genetika.html

https://id.wikipedia.org/wiki/Algoritma_genetik

http://repository.usu.ac.id/bitstream/123456789/55989/5/Chapter%20I.pdf