Implementasi algoritma genetika hibrid (First improvement search) pada travelling salesman problem / Devi Yuliagandi
| Main Author: | Yuliagandi, Devi |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16994/ |
Daftar Isi:
- KatakuncigraphTravellingSalesmanProblem(TSP)AlgoritmaGenetikaHibrid.TravellingSalesmanProblem(TSP)merupakansuatupermasalahandalammemilihrutedarisalesmanyangakanmendistribusikanbarangkeberbagaikotadankembalikekotaawaldimanasetiapkotaharusdilewatihanyasatukalidengantotalbobotseminimummungkin.Dalamhalinibobotbisadalamukuranjarakwaktuataupunbiaya.AlgoritmayangdapatmenyelesaikanTravellingSalesmanProblemdiantaranyafarthestinsertionheuristicdannearestneighbor.TerdapatalgoritmalainyangdapatmenyelesaikanTravellingSalesmanProblemdanmenghasilkansolusitidaktunggalyaitualgoritmagenetika.Algoritmagenetikamerupakanteknikoptimasiyangdidasarkanpadaprosesevolusimakhlukhidupdimanadalamevolusitersebutmakhlukhidupmengalamimekanismeseleksialam(diantaranyapindahsilangdanmutasi)untukbertahanhidup.Algoritmagenetikamerupakansuatualgoritmayangdapatdiaplikasikandalamberbagaijenispermasalahanoptimasi.Algoritmafirstimprovementsearchadalahsalahsatukeluargalocalsearchyangmemperhitungkanperubahandilingkunganpersekitarannyadarikeadaanyangdiberikanuntukmenghasilkannilaioptimal.Selainituterdapatalgoritmalainyangdapatmenghasilkansolusitidaktunggalyangmerupakanpengembangandarialgoritmagenetika.Algoritmatersebutadalahalgoritmagenetikahybrid.Algoritmagenetikahybridmerupakangabungandarialgoritmagenetikadanlocalsearch(firstimprovementsearch).Dariujicobayangdilakukansolusiyangdihasilkanalgoritmagenetikahybridsamaataulebihbaikdaripadaalgoritmagenetikadanmetode-metodeheuristic.Halinidipengaruhiolehadanyalocalsearch.Solusidarilocalsearchakanlebihbaikjikapadalangkahawaltelahditemukannilaifitnessyanglebihbaiksebelumatausampaibatasp(p61646N18804p880415).Namunterdapatbeberapaparameteryangharusdiperhatikandiantaranyabanyaknyapopulasiyangdigunakandanmaksimumgenerasi.Parametertersebutakanmempengaruhiunjukkerjadarialgoritmagenetikahybrid.Olehkarenaitudalammelakukanprosesalgoritmagenetikahybridperluadanyakesesuaianantarajumlahpopulasidanmaksimumgenerasiterhadapjumlahkota.Maksimumgenerasiyangbaikadalah30%dariukuranpopulasidanukuranpopulasiyangdigunakansebaiknyatidakkurangdari30.Untukmempermudahdalamperhitunganmakadibuatsoftwarealgoritmagenetikahybriddalamsuatubahasapemrogramandelphi.