ALGORITMA GENETIK HIBRID UNTUK TRAVELLING SALESMAN PROBLEM

ABDUL HARRIS SULAIMAN, 080312767 (2008) ALGORITMA GENETIK HIBRID UNTUK TRAVELLING SALESMAN PROBLEM. Skripsi thesis, UNIVERSITAS AIRLANGGA.

[img]
Preview
Text (ABSTRAK)
gdlhub-gdl-s1-2008-sulaimanab-9505-mpm260-k.pdf

Download (407kB) | Preview
[img] Text (FULL TEXT)
24398.pdf
Restricted to Registered users only

Download (1MB) | Request a copy
Official URL: http://lib.unair.ac.id

Abstract

Skripsi ini bertujuan untuk menyelesaikan masalah Travelling Salesman Problem (TSP) menggunakan algoritma genetik hibrid dan membuat program komputer untuk menyelesaikan permasalahan tersebut. Masalah Travelling Salesman Problem (TSP) digambarkan dengan perjalanan seorang salesman yang akan mengunjungi N kota, dengan rute perjalanannya dimulai dari tempat dia berada lalu mengunjungi kota lain masing-masing kota tepat satu kali dan diakhiri di kota asal tempat dia memulai perjalanan. Tujuan TSP adalah mencari urutan tour dengan jarak atau biaya perjalanan yang minimal. Algoritma genetik hibrid dalam skripsi ini merupakan gabungan antara algoritma genetik dan algoritma local search yaitu first improvement search. Langkah - langkah algoritma genetik hibrid untuk masalah Travelling Salesman Problem (TSP) dimulai dengan membangkitkan populasi awal secara acak dengan kode permutasi sebanyak ukuran populasi (pop size), lalu masing-masing individu dievaluasi, kemudian untuk mendapatkan individu yang lebih baik, dilakukan proses local search dan diseleksi dengan seleksi turnamen, selanjutnya akan dilakukan crossover dengan menggunakan partial mapped crossover dan dilakukan mutasi dengan menggunakan mutasi modifikasi bit inversion. Setelah crossover dan mutasi masing - masing individu akan di local search dan pada akhir proses akan dibentuk populasi baru. Proses diulangi sampai N generasi yang diinginkan. Skripsi ini menggunakan data 10 kota di Jawa Timur dan data 100 kota di Jawa. Data tersebut diambil dari Kees Roos, (2004). Data 10 kota Masing¬-masing diselesaikan secara manual dan menggunakan program C++. Parameter untuk 10 kota yang diselesaikan secara manual adalah pop size = 10, pc = 0,6, pm = 0,01, s = 0,6, p = 4 maksimum generasi = 1, diperoleh jarak minimal adalah 1160 km.Untuk data 10 kota yang menggunakan program C++ : pop_size = 10, pc = 0,6, pm = 0,01, e = 0,6, p = 4 maksimum generasi = 100, diperoleh jarak minimal adalah 969 km. Data 100 kota dengan pop size = 500, pc = 0,7 , pm = 0,01, s = 0,6, p = 4 maksimum generasi = 100, diperoleh jarak minimal adalah 14589 km. Dengan pop size = 1000, pc = 0,7 , pm = 0,01, e = 0,6, p = 4 maksimum generasi = 100, diperoleh jarak minimal adalah 14420 km.

Item Type: Thesis (Skripsi)
Additional Information: KKC KK MPM 26/08 Sul a
Uncontrolled Keywords: GENETIC ALGORITHMS
Subjects: B Philosophy. Psychology. Religion > BF Psychology > BF699-711 Genetic Psychology
Q Science > QA Mathematics
Q Science > QA Mathematics > QA76.73. Computer algorithms and Data structures
Divisions: 08. Fakultas Sains dan Teknologi
Creators:
CreatorsNIM/NIDN
ABDUL HARRIS SULAIMAN, 080312767UNSPECIFIED
Contributors:
ContributionNameNIDN/NIDK/NUP
ContributorHerry Suprajitno, , S.Si., M.SiUNSPECIFIED
ContributorEndah Purwanti, , S.SiUNSPECIFIED
Depositing User: Nn Shela Erlangga Putri
Date Deposited: 22 May 2009 12:00
Last Modified: 07 Jun 2017 20:27
URI: http://repository.unair.ac.id/id/eprint/24398
Sosial Share:

Actions (login required)

View Item View Item