DYNAMIC TRAVELLING SALESMAN PROBLEM (DTSP)MENGGUNAKAN HYBRID ALGORITMA PARTICLE SWARM OPTIMIZATION (PSO) DAN GENETIC ALGORITHM (GA)
| Main Author: | REVIKA FARA MAYLINDA, 081411233016 |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | ind |
| Terbitan: |
, 2018
|
| Subjects: | |
| Online Access: |
http://repository.unair.ac.id/78166/1/ABSTRAK%20MPM%20114%2018%20May%20d.pdf http://repository.unair.ac.id/78166/2/FULLTEXT%20MPM%20114%2018%20May%20d.pdf http://repository.unair.ac.id/78166/ http://lib.unair.ac.id |
Daftar Isi:
- Dynamic Travelling Salesman Problem (DTSP) akan diselesakan dengan hybrid Particle Swarm Optimization (PSO) dan Genetic Algorithm (GA). DTSP merupakan permasalahan dimana seorang sales harus melalui semua kota yang sudah ditetapkan dan setiap kota hanya boleh dilewati satu kali. Tujuannya adalah mencari rute terpendek untuk melewati sejumlah kota tersebut, dan perjalanan diakhiri dengan kembali ke kota semula dimana terdapat pengurangan atau penambahan kota tujuan sebelum perjalanan berakhir. Hybrid Particle Swarm Optimization dan Genetic Algorithm adalah menggabungkan proses algoritma Genetika dengan PSO, proses algoritma genetika dilakukan pertama kali, output dari algoritma ini diproses dengan algoritma PSO. Secara umum proses Algoritma Genetika adalah inisialisasi parameter, pembangkitan populasi awal, evalusi fungsi tujuan, seleksi, crossover, dan mutasi. Dalam tugas akhir ini, proses seleksi yang digunakan adalah Roulette Wheel, proses crossover yang digunakan adalah Two Cut Point Crossover, dan proses mutasi yang digunakan adalah Reciprocal Exchange. Kemudian dilanjutkan proses PSO adalah pemilihan partikel awal, pembangkitan kecepatan awal, pemilihan pbest dang best, update kecepatan dan partikel, evaluasi fungsi tujuan, dan proses berlanjut sampai maksimal iterasi. Ada 3 jenis data yang digunakan dan diselesaikan dengan progam C ++ yang dibuat oleh perangkat lunak Borland C ++. Hasil perhitungan jarak tempuh total minimal 10 kota setelah terdapat penambahan 5 kota tujuan adalah 316, untuk perhitungan 25 kota setelah terdapat penambahkan 5 kota tujuan adalah 10422, sedangkan untuk perhitungan 100 kota setelah penambahan terdapat 5 kota tujuan adalah 60172. Perubahan nilai parameter dapat mempengaruhi hasil. Semakin besar jumlah kromosom dan Pc serta banyak iterasi cenderung memberikan hasil yang lebih baik.