Penerapan metode pindah silang cycle crossover untuk Travelling Salesman Problem (TSP) / Rina Uktafiya
| Main Author: | Uktafiya, Rina |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2012
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17155/ |
Daftar Isi:
- KataKunciGraphTravellingSalesmanProblem(TSP)MetodePindahSilangCycleCrossoverMetodePindahSilangPartialMappedCrossoverDalamilmumatematikakhususnyaTeoriGraphpermasalahanoptimasirutekendaraandikenaldenganTravellingSalesmanProblem(TSP).TSPadalahsuatuperjalanansalesmandarisuatudepotken-outlettepatsatukalidankembalidepottersebutdenganjarakyangminimum.TSPdapatditerapkanpadagraphkomplitberbobotyangmemilikitotalbobotsisiminimum.RutepadaTSPinimemuatsemuaoutletpadagraphtersebut.BanyakalgoritmayangdigunakanuntukmenyelesaikanTSPsalahsatunyayaituAlgoritmaGenetika.TerdapatbeberapatahapuntukmenyelesaikanAlgoritmaGenetikayaitutahapinisialisasi(pencarianrute)tahapevaluasi(pembobotan)tahapseleksi(pemilihan)tahapcrossover(pindahsilang)dantahapmutasi(menukaroutletantarrute).DalamAlgoritmaGenetikapadatahapcrossoverterdapatbeberapametodelagidiantaranyayaituMetodeCycleCrossover(CX)danPartialMappedCrossover(PMX).MetodeCXinimerupakanmetodecrossoverdimanacarakerjanyadenganmengkopioutlet-outletdarisaturutedanmemilihoutlet-outletyanglaindarirutelainnyadenganmengingatpolacycle(rute).SedangkanmetodePMXmerupakanmetodepersilanganduaoutletditambahdenganprosedureperbaikanyaituadanyahubunganpemetaanantarakeduarute.DariduahasilujicobauntukbeberapatitikdapatdiketahuibahwarutedanjarakyangdihasilkanolehkeduametodeyaituMetodeCXdanMetodePMXadalahberbeda.Perbedaaninidikarenakanadanyaprosespadapemilihanoutletyangdicrossovertidaksamadandilakukansecaraacak.AgarlebihmudahuntukmenyelesaikanpermasalahanTSPpenerapanMetodeCXdanPMXpadacrossoveriniakandiaplikasikandalamprogramkomputermenggunakanBorlandDelphi7.0.