Algoritma Genetik

Algoritma Genetik
Algoritma genetic adalah suatu metoda pencarian (search) acak yang didasarkan atas prinsip evolusi yang terjadi di alam. Dalam proses evolusi, individu secara terusmenerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. Hanya individu yang kuat yang mampu bertahan, sehingga dalam proses evolusi dapat diharapkan diperoleh individu yang terbaik. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melalui proses perkembangbiakan untuk mendapatkan keturunan yang lebih baik.

Genetik
Cabang biologi yang mempelajari tentang keturunan dan variasi mahluk hidup
Informasi genetik manusia tesimpan dalam sel tepatnya di kromosom.
Dalam sel manusia kromosom bentuknya berpasangan dan terdapat 23 pasang Kromosom ini terbentuk dari bagian-bagian yang disebut gen Gen inilah yang mengatur properti dan karateristik suatu individu eg: Warna mata, jenis rambut

Gen akan menentukan sifat individu dan keturunan berikutnya Kumpulan dari gen yang terdapat dalam sebuah populasi akan menentukan jumlah variasi keturunan yang dimungkinkan

Sejarah
Landasan teoritis untuk Algoritma genetik ini diajukan oleh John Holland dalam bukunya yang berjudul “Adaption in Natural and Artificial Systems” pada tahun 1975, yang kemudian dikembangkan lebih lanjut oleh
muridnya David Goldberg. Proses genetika dari organisme-organisme biologi yang berdasar pada teori evolusi Charles Drawin

Dasar Algoritma Genetik
-Populasi-
Populasi adalah kumpulan kromosom (chromosome). Kromosom ini dibentuk dari komponen-komponen penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik, biner, simbol ataupun karakter tergantung dari permasalahan yang ingin diselesaikan.

Individu merupakan kumpulan gen dalam sistem algoritma genetik bisa dikatakan sama dengan kromosom. Gen ini bisa biner, float, dan kombinatorial. Individu dalam algoritma genetik dapat juga menyatakan salah satu kemungkinan solusi yang dicari. Misalkan dalam travel salesman problem individu dapat menyatakan suatu jalur terpendek yang akan ditempuh.

Dasar Algoritma Genetik
-Nilai Fitness-
Sebelum algoritma ini dijalankan, masalah apa yang ingin dioptimalkan
itu harus dinyatakan dalam fungsi tujuan, yang dikenal dengan fungsi fitness.
Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik
Kromosom dengan nilai fitness yang tinggi ini akan memberikan probabilitas yang tinggi untuk bereproduksi pada generasi selanjutnya. Sehingga untuk setiap generasi pada proses evolusi, fungsi fitness yang mensimulasikan seleksi alam, akan menekan populasi kearah fitness yang meningkat.

Prinsip Kerja
Membangkitkan populasi awal, Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan. Membentuk generasi baru, Dalam membentuk digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/ seleksi, perkawinan silang dan mutasi. Proses ini dilakukan berulangulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru.

Evaluasi solusi, Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2.
Beberapa kriteria berhenti yang sering digunakan antara lain:
Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah. Berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi.

Beberapa Definisi Penting
Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter. Allele, nilai dari gen.
Kromosom, gabungan gen-gen yang membentuk nilai tertentu. Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat

Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. Generasi, menyatakan satu-satuan siklus proses
evolusi. Nilai Fitness, menyatakan seberapa baik nilai dari suatu
individu atau solusi yang didapatkan.

Algoritma Genetik Untuk Mencari Kata Secara Acak Sebuah kata ditentukan sebagai target, misalnya:
‘BASUKI’. Bila setiap huruf diberi nilai dengan nilai urut alfabet, maka targetnya bisa dinyatakan sebagai besaran numerik :
Target=[2 1 19 21 11 9]
Komputer akan membangkitkan kata dengan jumlah huruf yang sama dengan target secara acak, terus-menerus hingga diperoleh kata yang sama dengan kata target.

Individu adalah satu kata yang muncul dari proses acak tersebut, misalnya : AGHSQE atau [1 7 8 19 17 5] Satu individu mempunyai n gen integer yang setiap gennya menyatakan no urut alfabet. Nilai fitness adalah inversi dari perbedaan antara nilai kata yang muncul (individu) dan target yang ditentukan. Misalnya kata yang muncul : AGHSQE dan targetnya BASUKI maka, nilai perbedaannya:
E = |1-2| + |7-1| + |8-18| + |19-21| + |17-11| + |5-9|
= 1+6+10+2+6+4 = 29
Fitness = (26)(6) – 29 = 156-29 = 127

10 thoughts on “Algoritma Genetik”

  1. febby anggraini says:

    trmksi telah berbagi ilmu 🙂

    1. FeGa WiHe says:

      ma sama

  2. DWI AYU LESTARI says:

    isinya sangat bagus dan mudah dipahami
    dwi ayu lestari

    1. FeGa WiHe says:

      terima kasih banyk

  3. dwiayulestari97 says:

    artikelnya bagus
    My blog

    1. FeGa WiHe says:

      terima kasih

  4. anggrainifeby says:

    trimaksih banyak
    My blog

  5. wahyu ningsih says:

    mau nanya dong.
    gimana cara menentukan jumlah kromosom untuk penjadwalan mobil jika gennya itu terdiri dari mobil=13, hari=7, waktu=4 dan rute=6 ?

    1. Ferry says:

      bisa di spesifikasi kan mbak ? mobil sebanyak 13 buah , hari = 7 hari, waktu 4 jam, rute = 6 rute ? kira-kira begitu kah ?

  6. hitado says:

    Ijin share ke blog saya

Leave a Reply

Your email address will not be published. Required fields are marked *