Pencarian solusi family traveling salesman problem dengan algoritma genetik

Abstract

Algoritma genetik adalah algoritma berbasis populasi dengan melakukan pendekatan secara biologis. Strategi evolusi dan pemrograman ini menggunakan operasi mutasi sebagai cara untuk mencari solusi. Solusi potensial (atau bisa disebut dengan kromosom) dapat direpresentasikan sebagai rangkaian bit. Selain mutasi, algoritma ini juga menggunakan operasi crossover (persilangan) untuk mencari solusi baru (kromosom baru). Family Traveling Salesman Problem (FTSP) dimotivasi dari aplikasi pengambilan pesanan di gudang. Meski pekerjaan dilakukan dengan desain dan kontrol gudang, pemesanan biasanya dimodelkan menggunakan Travelling Salesman Problem, di mana produk serupa dapat disimpan bersama. Karenanya, produk serupa dapat disimpan secara terpisah. Pada skripsi ini, sebuah perangkat lunak dibangun untuk mengimplementasikan secara bruteforce dan algoritma genetik. Input yang dipakai pada perangkat lunak ini adalah plaintext dan input yang diberikan oleh pengguna dengan keyboard. Setelah perangkat lunak dibangun, pengujian dilakukan terhadap implementasi secara bruteforce dan algoritma genetik. Perangkat lunak diuji dengan 2 metode pengujian, yaitu pengujian fungsional dan eksperimental. Berdasarkan pengujian fungsional, dapat disimpulkan bahwa perangkat lunak yang dibangun mampu mengimplementasikan proses bruteforce dan algoritma genetik dengan baik dan juga mampu menghasilkan kromosom yang sesuai dengan ketentuan pengambilan berapa banyak kota dalam setiap family. Berdasarkan pengujian eksperimental, dapat disimpulkan bahwa parameter input yang diberikan oleh pengguna perangkat lunak yaitu banyaknya kromosom yang dibentuk dalam 1 populasi, mutation rate, iterasi, dan treshold dapat menentukan dan mempengaruhi hasil pencarian kromosom dengan jarak tempuh minimum.