Pengembangan Algoritma Hill Climbing untuk Persoalan Lintasan Terpendek Multi Objektif

Abstract

Hill climbing algorithm is one of the heuristic technique than can be used to solve the shortst path problem. Hill climbing algorithm is a local search at random and usually the result obtained cannot be optimal because the exchange performed only as many as combination of obtained from the nodes.In this thesis had been asked the development of hill climbing algorithm. The steps in the development of begins with the determination of initial position. Hill climbing process will be conducted development of modification at the exchange session. The exchange process does with hill climbing and will get the new individuals. The result of exchange as individuals next used as a new individual in development process by using genetic algorithm. The individuals would be early population to complete the fitness function crossover, and mutation. The result is better than with the result hill climbing algorithm.

Algoritma hill climbing merupakan salah satu teknik heuristik yang dapat digunakan untuk menyelesaikan persoalan lintasan terpendek. Algoritma hill climbing melakukan pencarian lokal secara acak dan biasanya hasil yang diperoleh tidak optimal karena pertukaran yang dilakukan hanya sebanyak kombinasi yang diperoleh dari jumlah node yang ada. Dalam tesis ini diajukan pengembangan algoritma hill climbing. Langkah-langkah dalam pengembangan diawali dengan penentuan posisi awal. Proses hill climbing akan dilakukan pengembangan berupa modifikasi pada tahap pertukaran. Proses pertukaran dilakukan dengan hill climbing dan diperoleh individu-individu baru. Individu-individu yang merupakan hasil dari pertukaran selanjutnya dijadikan sebagai individu baru dalam proses pengembangan dengan menggunakan algoritma genetik. Individu-individu tersebut akan menjadi populasi awal untuk menyelesaikan fungsi fitness, crossover, dan mutasi. Hasil yang diperoleh lebih baik dibandingkan dengan hasil yang menggunakan algoritma hill climbing.