INISIALISASI POPULASI PADA ALGORITMAGENETIKA MENGGUNAKAN SIMPLE HILL CLIMBING (SHC)UNTUK TRAVELING SALESMAN PROBLEM (TSP)

Abstract

Pada algoritma genetika klasik, penentuan populasi awal dibangkitkan dengan metode acak (random). Pada penelitian dengan menggunakan jumlah populasi yang besar, metode ini sering menimbulkan efek yang tidak baik berupa konvergensi prematur dalam menemukan solusi optimal. Pada penelitian ini,Algoritma Simple Hill Climbing (SHC) sebagai algoritma yang bersifat lokal optimal dianalisis penerapannya untuk memperbaiki kinerja dari algoritma genetika dalam rangka menghindari algoritma genetika pada masalah konvergensi prematur sehingga diharapkan dicapai solusi yang optimal dalam penyelesaian masalah Traveling Salesman Problem(TSP). Pada penelitian ini dilakukan tiga jenis percobaan dengan menerapkan parameter Algoritma Genetika yang berbeda. Masing-masing parameter terdiri dari 10, 20 dan 50 populasi, jumlah iterasi 100, Probabilitascrossover0,1 dan Probabilitas Mutasi 0,75. Pada percobaan pertama diperoleh nilai inisial solusi untuk SHC sebesar 3596.6, solusi terbaik untuk SHC sebesar 31618.0 dan solusi terbaik untuk AlgoritmaGenetika 2725.5. Pada percobaan kedua diperoleh nilai inisial solusi untuk SHC sebesar 3494.1,solusi terbaik untuk SHC sebesar 3060.9dansolusi terbaik untuk Algoritma Genetika 2722.1. Pada percobaan ketiga diperoleh nilai inisial solusi untuk SHC sebesar3330.9,solusi terbaik untuk SHC sebesar 3202.3dan solusi terbaikuntuk Algoritma Genetika 2695.7.Pada penelitian ini semakin besar jumlah populasi yang diterapkan pada algoritma genetika maka diperoleh nilai solusi yang semakin baik pula. Pada penelitian ini penulis membandingkan hasil yang diperoleh dengan penelitian sejenis yang menggunakan metode EA, GA, dan ACO-GA. Hasil yang diperoleh dengan metode EA adalah sebesar 2678, dengan GA sebesar 3218 dan dengan ACO-GA sebesar 3092 sedangkan dengan penelitian penulis diperoleh dengan hasil 2667