PENGARUH STRATEGI INISIALISASI PADA ALGORITMA EVOLUSI DALAM OPTIMASI TRAVELLING SALESMAN PROBLEM (TSP)

ABSTRAK Travelling Salesman Problem (TSP) yaitu pencarian rute terpendek atau jarak minimum olehseorang salesman dari suatu kota ke n-kota tepat satu kali dan kembali ke kota awalkeberangkatan. TSP dapat diterapkan pada graph komplit berbobot yang memiliki total bobotsisi minimum, dimana bobot pada sisi adalah jarak. Untuk menyelesaikan permasalahan inibisa dengan menggunakan metode Algoritma Evolusi (AE) yang merupakan metode yangmenggunakan seleksi alam sebagai gagasan utamanya dalam menyelesaikan suatupermasalahan tertentu. Dalam AE memiliki beberapa metode yaitu Random Search (RS) danRandom Generator (RG). Random search adalah metode pencarian langsung yang tidakmemerlukan derivatif untuk mencari domain continue. Inisialisasi random generator ialahcara untuk membangkitan angka acak pada tiap gen yang dibentuk dalam merepresentasikromosom awal. Penelitian ini merumuskan strategi inisialisasi pada algoritma berevolusiuntuk pemecahan TSP. Tujuan dari penelitian ini adalah modifikasi antara kedua metodestrategi inisialisasi random search dengan random generator untuk mendapatkan metodeinisialisasi yang terbaru sehingga dapat diterapkan dalam algoritma berevolusi. Setelahmelakukan penelitian, maka mendapatkan kesimpulan bahwa strategi inisialisasi RS dan RGtelah menyeimbangkan nilai diversity dengan mendapatkan hasil nilai rata-rata lebih optimaldibandingkan dengan penelitian sebelumnya. Selisih nilai jarak minimum antara RS dan RGmencapai rata-rata 16% dan hasil implementasi strategi inisialisasi RG telah menunjukkanhasil yang lebih optimal dibandingkan RS yaitu dapat dilihat berdasarkan nilai jarak minimumyang didapat setelah melakukan penelitian. Hal tersebut disebabkan oleh pada RG melakukanpencarian gen secara keseluruhan sebelum inisialisasi dibentuk, sedangkan pada RS mencarititik potong untuk menempatkan gen untuk pembentukan inisialisasi.Kata kunci : Strategi Inisialisasi, Algoritma Evolusi, Random Search, Random Generator, Travelling Salesman Problem