Electronic Theses and Dissertation

Travelling Salesman Problem (TSP) termasuk kedalam persoalan optimasi kompleks yang sulit diselesaikan dan membutuhkan waktu yang sangat lama untuk jumlah kota yang besar. Algoritma berevolusi adalah algoritma yang sangat tepat digunakan untuk. menyelesaikan masalah optimasi kompleks, karena merupakan bagian dari metode heuristik. Namun demikian, algoritma berevolusi sebagaimana algoritma lainnya juga bisa mengalami fenomena kekonvergenan dini, dimana variasi dihilangkan dari suatu populasi sebelum solusi yang komplit didapatkan. Oleh karena itulah dibutuhkan suatu metode untuk memperlambat kekonvergenan tersebut. Salah satu dari metode terse but adalah fitness sharing dengan lebih spesifik yaitu phenotype fitness sharing. Dalam penelitian ini ingin dilihat apakahjitness sharing dalam algoritma berevolusi dapat mengoptimumkan TSP. Konsep algoritma berevolusi yang digunakan adalah dengan 1 elitism dan konsep solusi gabungan (n elitism). Kedua konsep tersebut diujikan terhadap metodefitness sharing dengan menggunakan treshold sebesar 0.25, 0.50 dan 0.75. Hasil yang didapatkan langsung dibandingkan dengan metode yang tidak menggunakan fitness sharing. Dari hasil pengujian diperoleh bahwa dengan meoggunakan satu elitism, fitness sharing dapat memberikan hasil yang lebih optimum untuk data berukuran 100-1000 kota, Sementara, untuk data yang berukuran diatas 1000 kota hasilnya lebih optimum dengan menggunakan n elitism. Fitness sharing juga mengakibatkan penyebaran solusi yang lebih baik dibandingkan dengan metode non fitness sharing.

Kata kunci : Travelling salesman problem (TSP), Algoritma berevolusi, fitness sharing.

Tidak Tersedia Deskripsi