Inisialisasi Populasi pada Algoritma Genetika untuk Travelling Salesman Problem (TSP) Menggunakan Algoritma Steepest Ascent Hill Climbing

Abstract

In classical genetic algorithm, the determination of the initial population generated by random methods. In the study using a large population, these methods often cause undesirable effects such as premature convergence in finding the optimal solution. In this study, algorithm Steepest Ascent Hill Climbing (SAHC) as the algorithm locally optimal analyzed its application to improve the performance of the genetic algorithm in order to avoid the genetic algorithm to the problem of convergence premature so expect to achieve optimal solutions in solving the Traveling Salesman Problem (TSP), In this research, three types of experiments by applying different parameters of Genetic Algorithm. Each of these parameters consist of 10, 20 and 50 of the population, number of iterations 100, crossover probability 0.1 and mutation probability of 0.75. In the first experiment, initial values obtained for the solution is 3596.6, SAHC amounted to 31618.0 best solution and the best solution Genetic Algorithm 2725.5. In the second experimental values obtained initial solution to SAHC at 3494.1, 2722.1 and the best SAHC for the best solution Genetic Algorithm 2722.1. In the third experiment obtained the initial value of 3330.9 solutions for SAHC, SAHC best solution and the best solution for 3202.3 Genetic Algorithm 2695.7. In this study population the greater the number of genetic algorithm applied to the obtained value the better solution.In this study, the authors compare the results obtained with similar studies that use methods of EA, GA and ACO-GA. The results obtained by the method of EA is equal to 2678, the GA of 3218 and with the ACO-GA by 3092 while with the research results obtained by the author in 2667.

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 Steepest Ascent Hill Climbing (SAHC) sebagai algoritma yang bersifat lokal optimal dianalisis penerapannya untuk memperbaiki kinerja dari algoritma genetika dalam rangka menghindari algoritma genetika pada masalah konvergensi premature 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, Probabilitas crossover 0,1 dan Probabilitas Mutasi 0,75. Pada percobaan pertama diperoleh nilai inisial solusi untuk SAHC sebesar 3596.6, solusi terbaik untuk SHC sebesar 31618.0 dan solusi terbaik untuk Algoritma Genetika 2725.5. Pada percobaan kedua diperoleh nilai inisial solusi untuk SAHC 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 sebesar 3330.9,solusi terbaik untuk SAHC sebesar 3202.3 dan solusi terbaik untuk 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.