0

ALGORITMA GENETIKA

Algoritma genetika merupakan sebuah algoritma komputasi yang diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”. Salah satu aplikasi algoritma genetika adalah pada permasalahan optimasi kombinasi, yaitu mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi. Dalam tulisan ini, akan dibahas teori dasar algoritma genetika beserta contoh aplikasinya dalam menyelesaikan suatu permasalahan optimasi kombinasi sederhana.

Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul “Adaption in Natural and Artificial Systems” pada tahun 1975.

Struktur Umum Algoritma Genetika

Struktur umum algoritma genetik dapat diilustrasikan dalam diagram alir berikut ini:

untitled.png

 

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.

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string ‘0’ dan ‘1’, walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.

Karakteristik Algoritma Genetika

Goldberg (1989) mengemukakan bahwa algoritma genetika mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain yaitu:

  1. 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.
  2. AG melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.
  3. AG merupakan informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi.
  4. AG menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik.

Parameter yang digunakan pada algoritma genetika adalah:

  1. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai.
  2. Populasi jumlah individu yang dilibatkan pada setiap generasi
  3. Probabilitas terjadinya persilangan (crossover) pada suatu generasi
  4. Probabilitas terjadinya mutasi pada setiap individu.
  5. Jumlah generasi yang akan dibentuk yang menentukan lama dari penerapan AG

Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu : operator reproduksi, operator crossover (persilangan) dan operator mutasi.

Langkah-langkah Algoritma Genetika

Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:

  1. Pengkodean Pengkodean disini meliputi pengkodean gen dan kromosom.
  2. Inisialisasi populasi awal Membangkitkan sejumlah kromosom (sesuai dengan ukuran populasi) untuk dijadikan anggota populasi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan.
  3. Evaluasi nilai fitnes Setiap kromosom pada populasi dihitung nilai fitnessnya berdasarkan fungsi fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti.
  4. Pembentukan kromosom baru
  5. Seleksi Memilih sejumlah kromosom yang akan menjadi kromosom calon parent
  6. Crossover Mengkombinasikan dua kromosom parent (induk) berdasar nilai probabilitas crossovernya untuk menghasilkan offspring
  7. Mutasi Mengubah sejumlah gen berdasar nilai probabilitas mutasinya untuk menghasilkan kromosom baru.
  8. Update Generasi Membaharui kromosom yang terdapat dalam populasi.
  9. Pengecekan faktor pemberhenti

Jika memenuhi dari salah satu dari kondisi untuk berhenti, maka siklus algoritma genetika berhenti. Proses evolusi bisa dihentikan berdasarkan beberapa kondisi, misalnya ketika:

  1. evolusi telah mencapai jumlah generasi maksimum yang diizinkan,
  2. terdapat suatu individu yang telah memiliki fitness tertentu yang diharapkan,
  3. keberagaman populasi telah mencapai tingkat minimum yang diizinkan,
  4. dalam beberapa generasi tertentu, tidak ada peningkatan nilai fitness yang diharapkan.

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.

Sumber:

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

http://informatika.web.id/struktur-umum-algoritma-genetika.htm

Advertisements
0

SISTEM CERDAS YANG ADA DI SEKITAR KITA

Berikut adalah contoh sistem cerdas yang ada di lingkungan sekitar kita.

  1. Vending Machine

bevmaxcoke

Vending Machine adalah mesin yang digunakan untuk mengeluarkan/menjual produk secara otomatis tanpa ada operator. Operator tidak perlu menunggu mesin, tetapi hanya bertugas untuk mengisi, memeriksa ketersediaan barang yang dijual dan memeriksa mesin. Saat ini vending machine mudah kita jumpai di negara-negara maju yang digunakan sebagai alat untuk menjual berbagai macam produk.

Vending Machine menurut sejarahnya ditemukan pada abad pertama oleh seorang pahlawan dari Alexandria. Vending Machine modern pertama kali diperkenalkan di London pada tahun 1880, vending machine ini menjual kartu pos. Sedangkan di US pada tahun 1888 dibuat vending machine untuk menjual permen karet, mesin dibuat oleh Thomas Adams Gum Company yaitu perusahaan pembuat permen karet. Perkembangan vending machine justru berkembang pesat di Jepang. Dimana hampir segala kebutuhan sehari-hari jika bisa di buat vending machine-nya.

Cara kerja vending machine adalah dengan melakukan pembayaran (baik menggunakan uang ataupun sistem lainnya) kepada mesin kemudian memilih produk, setelah itu produk yang dipilih akan segera keluar.

     2. ATM (Anjungan Tunai Mandiri)

6172535_g

ATM (Anjungan Tunai Mandiri) adalah sebuah alat elektronik yang melayani nasabah bank untuk mengambil uang dan mengecek rekening tabungan mereka tanpa perlu dilayani oleh seorang “teller” manusia. Banyak ATM juga melayani penyimpanan uang atau cek, transfer uang atau bahkan membeli perangko.

ATM modern pertama yang berfungsi ditemukan oleh Sir John Shepherd-Barron tanggal 27 Juni 1967 di Inggris. Mesin tersebut dipasang di Bank Barclays cabang Enfield di Inggris. Oleh karena jasanya, Ratu Inggris pada tahun 2004 memberikan gelar “Most Excellent Order of the Britis Empire” kepadanya.

Mesin ATM mulai ramai digunakan di Indonesia pada tahun 1980an, pengguna ATM pertama di Indonesia adalah bank HSBC dan bank Niaga. Dengan persaingan pasar yang besar, maka bank – bank lain juga ikut memasang ATM untuk memudahkan nasabah mereka dalam menarik uang.

ATM sering ditempatkan di lokasi-lokasi strategis, seperti restoran, pusat perbelanjaan, bandar udara, stasiun kereta api, terminal bus, pasar tradisional, dan kantor-kantor bank itu sendiri.

Cara kerja mesin ATM mudah dan sederhana. Yang pertama kamu lakukan ialah memasukkan kartu ATM ke dalam mesin. Setelah kartu dimasukkan, maka kartu akan dibaca oleh magnetic card reader yang berfungsi sebagai pembaca dan penerima data. Setelah dibaca, data dikirim ke sistem komputerisasi bank.

    3. Automatic Sliding Door (Pintu Geser Otomatis)

es_200_1200x1200_au_image_slider_product_image_slider_zoom

Automatic Sliding Door atau Pintu Geser Otomatis adalah suatu perangkat yang dapat mendeteksi kehadiran manusia atau objek hidup lainnya. Automatic sliding door biasanya sering kita temui di mall, perkantoran, apartemen dan pabrik. Penggunaan automatic sliding door juga sangat praktis, kita tidak perlu memegang gagang pintu untuk membukanya, kita hanya perlu berjalan menghampirinya maka pintu akan otomatis terbuka dan akan otomatis tertutup kembali.