Analisis Hibridisasi Pencarian Lokal Dengan Populasi Dalam Travelling Salesman Problem TSP

of 7

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
PDF
7 pages
0 downs
14 views
Share
Description
Analisis Hibridisasi Pencarian Lokal Dengan Populasi Dalam Travelling Salesman Problem TSP
Tags
Transcript
  Serambi Engineering, Volume II, No.4, Agustus 2017  ISSN : 2528-3561Edisi Khusus 1. Pendahuluan Traveling Salesman Problem   (TSP) merupakan sebuah permasalah optimasi yang dapat diterapkan pada berbagai kegiatan seperti pendistribusian barang, pengambilan tagihan listirk dan pedagang keliling. Masalah optimasi pada TSP sangat terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Pokok dari permasalahan  TSP adalah bagaimana seorang salesman harus dapat mengunjungi sejumlah kota yang telah diketahui jarak kota satu dengan yang lainnya. Dari semua kota yang ada harus dikunjungi oleh salesman dan kota tersebut hanya boleh dikunjungi tepat satu kali saja dan kembali lagi kekota asal keberangkatannya. Yang menjadi permasalahannya adalah bagaimana salesman tersebut dapat mengatur rute perjalanannya sehingga jarak yang ditempuh merupakan jarak yang paling minimum (G. Ramani, N. Bouvanasilan, and V. Seenuvasan, 2009). Telah banyak metode algoritma yang dapat digunakan untuk dapat menyelesaikan TSP diantaranya Hill Climbing Method  ,  Ant Colony System  . Metode lain yang dapat digunakan untuk menyelesaikan TSP seperti algoritma berevolusi.  Algoritma berevolusi merupakan sebuah algoritma yang meniru cara kerja proses alam pada makhluk hidup, dimana terdapat proses seleksi, rekombinasi dan mutasi untuk mendapatkan kromosom yang  Analisis Hibridisasi Pencarian Lokal Dengan Populasi Dalam Travelling Salesman Problem (TSP) Erdiwansyah*, Yeni Yanti, Munawir, Raihan Islamadina  Teknik Informatika, Fakultas Teknik, Universitas Serambi Mekkah Jl. Tgk. Imum Lueng Bata Desa Bathoh, Kota Banda Aceh, Propinsi Aceh, Indonesia *Koresponden Email : erdiwansyah@serambimekkah.ac.id  Abstrak.   Traveling Salesman Problem   (TSP) merupakan sebuah permasalah optimasi yang dapat diterapkan pada berbagai kegiatan seperti pendistribusian barang, pengambilan tagihan listirk dan pedagang keliling. Masalah optimasi pada TSP sangat terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Pokok dari permasalahan TSP adalah bagaimana seorang salesman harus dapat mengunjungi sejumlah kota yang telah diketahui jarak kota satu dengan yang lainnya. Algoritma Local search merupakan metode pencarian solusi berdasarkan neighborhood dari solusi awal. Metode ini dikenal dengan nama iterative improvement  . Algoritma ini mencari solusi disekitar solusi awal untuk memperbaiki solusi. Algoritma hybrid menggunakan fungsi random sehingga menyebabkan algoritma hybrid menjadi suatu algoritma berbasis komputer yang menghasilkan solusi yang lebih optimal. Hasil penelitian menunjukan hibridisasi lebih baik dari pencarian lokal maupun populasi murni. Kata Kunci:    Analisis Hibridisasi, Pencarian Lokal, Populasi, Hibridisasi ABPLPB .  Abstract.  Traveling Salesman Problem (TSP) is an optimization problems that can be applied to a variety of activities such as distribution of goods, making burning electricity bills and pitchman. TSP optimization problem in a very famous and has become the standard to try algorithm komputational. Highlights of the  TSP problem is how a salesman should be able to visit a number of cities within the city that have known each other. Local search algorithm is a method of nding a solution based on the neighborhood of the initial solution. This method is known as iterative improvement. These algorithms look for solutions around the initial solution to xing solutions. Hybrid algorithm uses a random function resulting hybrid algorithm into a computer-based algorithm that generates more optimal solution. The results showed better hybridization of local search as well as pure populations. Keywords:  Evolutionary Algorithms  , Local Search, Population Hybrid LS end Population  . 165  Serambi Engineering, Volume II, No.4, Agustus 2017  ISSN : 2528-3561Edisi Khusus terbaik pada suatu generasi (Sri, Y.; Nurmaulidar; dan Tauq, A.G, 2011). Dengan meniru teori evolusi, algoritma berevolusi dapat digunakan untuk mencari solusi permasalahan dalam dunia nyata. Sebelum algoritma dapat dijalankan, maka sebuah kode yang sesuai pada persoalan harus dirancang, Untuk ini maka solusi ruang permasalahan di kodekan dalam bentuk kromosom yang terdiri atas komponen genetika terkecil yaitu gen. Dengan teori evolusi dan teori genetika, di dalam penerapan nya algoritma berevolusi akan melibatkan beberapa operator, diantaranya reproduksi, crossover, dan mutasi. Algoritma Pencarian lokal (  local search   )   merupakan metode pencarian solusi berdasarkan neighborhood dari solusi awal (W. Maharani, 2009). Metode ini dikenal dengan nama iterative improvement  .  Algoritma ini mencari solusi disekitar solusi awal untuk memperbaiki solusi. Jika ditemukan solusi yang lebih baik maka solusi itu akan menggantikan solusi awal dan local search   akan diteruskan, langkah ini akan terus dilakukan sampai tidak ada kemungkinan untuk memperbaiki solusi lagi. Pada saat itu algoritma akan berhenti dan kondisi saat itu akan mencapai lokal optimum. Untuk memenuhi spesikasi algoritma Local Search   diperlukan pemeriksaan skema “ neighborhood  ”. Bagaimana skema pencarian “ neighborhood  ” dan “ neighbor  ” yang mana yang akan menggantikan solusi awal, aturan ini disebut  pivoting rule  . Macam-macam  pivoting rule   antara lain : 1. the best-improvement rule 2. the rst-improvement rule.  Jika k-opt “ neighborhood  ” maka solusi tetangga yang berbeda paling banyak k busur. Algoritma hybrid merupakan gabungan metode-metode heuristik lain ke dalam algoritma berevolusi dengan harapan mampu meningkatkan kinerja algoritma local search   (Zne-Jung Lee, 2004). Pada prinsipnya hibridisasi ini diharapkan mampu memberikan solusi lain yang lebih baik disekitar lokal optimum yang diberikan oleh algoritma evolusi atau dikenal dengan istilah local search  . Algoritma hybrid menggunakan fungsi random sehingga menyebabkan algoritma hybrid menjadi suatu algoritma berbasis komputer. Best Improvement Local Search   adalah memperhatikan semua solusi tepat diantara semua lingkungan solusi. Dan mengambil solusi yang terbaik diantara semua solusi. 2. Studi Literatur Pada bab ini akan dibahas mengenai penggunaan algoritma Local   dan algoritma Population Based dala algoritma berevolusi untuk penyelesaian masalah jalur terpendek. Beberapa proses yang penting harus dilakukan dalam mengimplementasikan algoritma local   dan algoritma  populastion based dalam berevolusi untuk mencari jalur terpendek yaitu sebagai berikut : 1. Representasi kromosom. 2. Inisialisasi Populasi. 3. Fungsi evaluasi/tness. 4. Seleksi. 5. Operator algoritma berevolusi, yaitu operator rekombinasi (  crossover   ) dan mutasi. 6. Penentuan parameter, yaitu parameter control algoritma local  , yaitu : ukuran populasi (   popsize   ), peluang crossover   (pc) dan peluang mutasi (pm) Dalam penentuan parameter ini dilakukan dengan proses sistem  population   untuk mendapatkan nilai yang akan digunakan sebagai parameter. Dalam hal ini kedua algoritma mempunyai proses berkesinambungan yang dimana pada algoritma  population based   hanya berbeda pada penentuan parameternya, oleh karena itu proses yang dilakukan sama dengan algoritma local (Erdiwansyah, 2016). 3. Metode Penelitian Pada penelitian ini, algoritma Local Search akan dibandingkan dengan Algoritma Population Based dalam algoritma berevolusi. Sedangkan parameter yang akan digunakan sebagai berikut : 1.  Jumlah Populace = 100 individu 2. Proses Seleksi = Roulette Wheel  3. Proses Mutasi = Insertion   dan Inversion  4. Probalitas Crossover = 0,5 5. Probalitas Mutasi = 0,8Sedangkan data yang digunakan pada penelitian ini adalah dataset TSPLib95 yang di download secara gratis dengan format type EUC_2D dengan 166  Serambi Engineering, Volume II, No.4, Agustus 2017  ISSN : 2528-3561Edisi Khusus julah data paling kecil 51 sampai dengan 127 node  . Dikarenakan dataset tersebut adala TSP simetris yang hanya mendukung tipe EDGE_WEIGHT_  TYPE : EUC_2D, yaitu koordinat posisi dengan 2 dimensi sebagai alat perbandingan antara kedua metode yang akan dibandingkan. 4. Perancangan Algoritma  Algoritma hybrid merupakan gabungan dari algoritma local search   (pencarian lokal) dengan  population Based   (sekumpulan individu) yaitu best improvement search untuk menghasilkan solusi yang lebih optimal. Penyelesaian permasalahan dengan menggunakan Algoritma hybrid antara pencarian lokal dengan populasi ini melalui beberapa tahapan. Berikut tahapan-tahapan algoritma hybrid dalam algoritma berevolusi. 1. Inisialisasi populasi awal dengan merepresentasikan tiap rute atau kota dalam node. Salah satu cara dalam menghasilkan populasi awal secara acak adalah dengan menggunakan permutasi. Misalkan ada 7 kota, permutasi dapat dilakukan dengan menentukan node awal dan selang. Misalkan node awal adalah 3 dan selang adalah 2. Maka lintasan berangkat dari kota 3 selang 2 dari kota 3 adalah kota 5 (dengan asumsi bahwa kota 1 sampai kota 7 membentuk list). Kemudian kota 5 akan dihapus dari daftar, selang 2 kota 5 adalah kota 7. Proses ini diulang hingga terdapat satu jalur dalam daftar yang memuat semua node. Hasil dari mutasi ini adalah 3 5 7 2 4 6 1. 2.  Validasi setiap rute untuk memperoleh lintasan yang akan dilalui dalam tiap rute.Evaluasi fungsi  tness   dari tiap populasi. Untuk evaluasi kromosom-kromosom digunakan fungsi  tness   yang merupakan fungsi obyektif dari jumlah jarak terpendek dari jumlah yang ada (Fv). Fv  i    = , dimana R adalah rute yang terbentuk  f  x    = (I. H. Saputra, T. Octavia, and A. S. Chandra, 2009).Pilih sesuai dengan n individu terbaik dan masing-masing rute (individu) akan di local search   (  Best Improvement Local Search   ) dan pada akhir proses akan dibentuk kumpulan rute (populasi) baru. Best Gambar 1.   Flowchart   Algoritma Pencarian LokalGambar 2 Flowchart   Algoritma Populasi 167  Serambi Engineering, Volume II, No.4, Agustus 2017  ISSN : 2528-3561Edisi Khusus Improvement Local Search   adalah memperhatikan semua solusi yang tepat diantara dari semua lingkungan solusi. Dan mengambil solusi yang terbaik diantara semua rute. Validasi kendala waktu untuk memperoleh waktu yang dibutuhkan setiap rute yang akan dilalui. Seleksi dilakukan dengan seleksi roullete wheel  . Seleksi yang digunakan untuk memilih individu-individu mana saja yang akan terpilih untuk proses kawin silang dan mutasi. Seleksi digunakan untuk mendapatkan induk yang baik. “induk yang baik akan menghasilkan keturunan yang baik pula”. Semakin tinggi nilai  tness   suatu individu maka semakin besar kemungkinannya untuk terpilih.Selanjutnya akan dilakukan crossover   dan mutasi pada setiap individu tersebut sehingga diperoleh rute yang baru serta akan divalidasi rute baru tersebut, dan dilakukan dengan local search  , serta hitung nilai  tness  -nya. Crossover   bekerja pada pasangan solusi dan disusun ulang (  recombines   ) yang menghasilkan satu kromosom. Fungsi dari crossover   tergantung pada data yang disajikan. Pada dasarnya crossover   dapat bekerja dengan menukar sebagian gen pada kromosom satu ke kromosom lainnya yang akan menghasilkan kromosom yang berbeda (I. H. Saputra, T. Octavia, and A. S. Chandra, 2009).1. Beberapa operator berikut diantaranya crossover   untuk representasi permutasi adalah metode simple    random crossover  , pindah silang satu titik, unifom crossover  , order xrossover (E. Samana, B. Prihandono, and E. Noviani, 2015). Adapun mengenai probabilitas crossover   yang baik, dari hasil penelitian yang dilakukan oleh Zbiniew Michalewics (1996) menyatakan bahwa probabilitas crossover   yang baik berada dalam range 0.65 sampai dengan 1. Operator ini digunakan untuk memodikasi suatu kromosom agar menghasilkan perubahan kromosom secara random. Cara yang paling sederhana dalam melakukan mutasi dengan mengubah satu atau lebih gen dalam kromosom. Fungsi mutasi untuk mengganti gen yang hilang pada saat proses seleksi dan menyediakan gen yang tidak terdapat pada populasi awal.  Tingkat mutasi awal P m  akan didenisikan sebagai presentase dari jumlah gen pada populasi. Tingkat mutasi dapat mengontrol tingkat gen yang akan dimodikasi. Jika tingkat mutasi rendah, banyak gen yang tidak dicoba.2. Berikut beberapa operator mutasi untuk representasi permutasi adalah metode inversion mutation, insertion mutation, Displacement   Mutation dan rechiprocal exchange mutation  . Adapun mengenai probabilitas mutasi yang baik, dari hasil penelitian yang dilakukan oleh (S. Kumar, J. Kurmi, and S.P.  Tiwari, 2015) menyatakan bahwa probabilitas mutasi yang baik yang berada pada range 0.01 sampai dengan 0.3. 3. Keturunan atau anak hasil dari crossover   yang berupa rute baru dan rute lama tersebut Gambar 3 Flowchart   Algoritma Hibridisasi PL-PB 168  Serambi Engineering, Volume II, No.4, Agustus 2017  ISSN : 2528-3561Edisi Khusus diurutkan berdasarkan fungsi  tness  -nya. 4. Selanjutnya rute dengan fungsi  tness   yang terbaik tersebut kemudian dievaluasi jaraknya.  Jika sudah memenuhi semua kendala dalam hybrid LPBSAB dipilih n rute terbaik. Adapaun tahapan-tahapan algoritma hybrid ini, bisa dilihat dari  owchart   diagram alir dari algoritma hybrid Local dan Populatiaon Based Search dalam  Algoritma   Berevolusi. Berikut penjelasan dan tahapan-tahapan dalam menyelesaikan hibridisasi pencarian lokal dengan populasi dalam algoritma berevolusi :a. Inisialisasi parameter dengan LS: • Intensitas  pheromone   (τij).•  Tetapan siklus rute (q0). •  Tetapan pengendali intensitas visibilitas (β), nilai β ≥ 0.•  Tetapan pengendali  pheromone   (α), nilai α ≥ 0.•  Jumlah ants (m). •  Tetapan penguapan  pheromone   (ρ), nilai ρ harus > 0 dan < 1. •  Jumlah siklus maksimum (NCmax).b. Memberikan nilai bobot (w) untuk jarak.c. Menghitung visibilitas antar individu dengan Populasi.d. Mentukan individu selanjutnya, ulangi proses sampai individu tercapai. Dengan menggunakan persamaan (4) atau persamaan (4) dapat ditentukan individu mana yang akan dituju yaitu dengan : • Jika q ≤ q0 maka pemilihan individu (aturan transisi) yang akan dituju menggunakan persamaan (3.). •  Jika q > q0 maka pemilihan individu yang akan dituju (aturan transisi) menggunakan persamaan (4) 169
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks