Dalam ilmu komputer Algoritme genetik merupakan suatu metode heuristic untuk mencari solusi optimum dari suatu permasalahan dengan menggunakan mekanisme pencarian yang meniru proses evolusi biologis. Mekanisme yang digunakan merupakan kombinasi dari pencarian acak dan terstruktur. Algoritma ini sudah berhasil diterapkan dalam berbagai permasalahan kombinatorial, mulai dari Traveling Salesman Problem (TSP ),VRP , dan penjadwalan produksi.
Salah satu aplikasi algoritma genetika adalah pada permasalahan vehicle routing problem yaitu untuk membuat suatu rute yang optimal, untuk suatu kelompok kendaraan, agar dapat melayani sejumlah konsumen dan mengurangi biaya transportasi.
Parameter Algoritma Genetik :
- Jumlah Generasi, merupakan jumlah perulangan (iterasi) dilakukannya rekombinasi dan seleksi.
- Ukuran populasi mempengaruhi kinerjadan efektifitas dari algoritma genetik.
- Probabilitas crossover (Pc) ini digunakan untuk mengendalikan frekuensi operator crossover.
- Probabilitas Mutasi (Pm), mutasi digunakan untuk meningkatkanvariasi populasi
Mekanisme Dasar Algoritma Genetik :
Adapun mekanisme Algoritma genetik adalah sangat sederhana, yaitu hanya melibatkan penyalinan string dan pertukaran bagian string. Siklus pengembangbiakan algoritma genetik diawali dengan pembuatan himpunan solusi yang dinamakan kromosom.
Langkah – Langkah Dasar Algoritma Genetik :
- [Start ] Parents awal yang digunakan digenerate secara random atau bisa juga dengan metode heuristik tertentu.
- [Fitness] Mengevaluasi fitness f(x) dari tiap kromosom x dalam populasi.
- [ New population] Menciptakan populasi baru dengan mengulang langkah – langkah di bawah ini sampai terbentuk populasi baru :[Selection] Pilih dua parents kromosomdari populasi termasuk fitness mereka. [Crossover ] Dengan sebuah probabilitas crossover , penyilangan parents dilakukan untuk membentuk offspring (keturunan) yang baru. Jika tidak ada crossover yang terbentuk, offspring yang terbentuk adalah murnisalinan dari orang tuanya. [Mutation] Dengan sebuah probabilitas mutasi, offspring yang baru terbentuk dimutasi pada setiap locus (posisidalam kromosom). [Accepting] Tempatkan offspring yang baru pada populasi baru.
- [Replace] Gunakan generasi populasi yang baru untuk replikasi algoritma berikutnya.
- [Test ] Jika kondisi akhir sudah memenuhi syarat,Stop, kembali ke solusi terbaik dalam populasi tersebut.
- [Loop] Kembali ke Langkah b.
Verifikasi Hasil
Setelah diperoleh hasil, maka dilakukan verifikasi, yaitu dengan cara memeriksa hasil tersebut dengan syarat – syarat pengiriman,antara lain :
- Tidak melanggar pembatas kapasitas kendaraan
- Semua node telah terlewati
Sumber: https://www.academia.edu/3589465/PENERAPAN_ALGORITMA_GENETIK_UNTUK_PENYELESAIAN_MASALAH_VEHICLE_ROUTING_DI_PT.MIF?auto=download
