Serambi Engineering, Volume II, No.4, Agustus 2017
dari masing-masing packing tersebut, untuk kemudian dijual ke pembeli selanjutnya dengan menggunakan armada transportasi yaitu truk barang. Pemuatan kemasan plastik cacahan tersebut, harus dapat memenuhi permintaan/pemesanan pembeli selanjutnya, oleh karena itu biasanya tonase harus mencapai jumlah tertentu misalnya mencapai sepuluh ton, sehingga dapat memenuhi permintaan dan memudahkan dalam proses pengiriman ke pembeli berikutnya. Biasanya, penjualan produk plastik cacahan biasanya diluar Aceh yaitu di industri pengolahan plastik yang berada di Kota Medan Provinsi Sumatera Utara.
5. Kesimpulan 1.  Pertambahan jumlah penduduk khususnya di Aceh mengakibatkan konsumsi limbah (khususnya limbah plastik) menjadi meningkat.
Hal ini akan berdampak buruk apabila limbah plastik tidak diperlakukan sebagaimana layaknya misalnya tidak diolah kembali ( reuse , reduce maupun recycle / reprocessing ). Jika tidak di kendalikan atau dikelola dengan benar, maka ancaman akan munculnya baik itu pencemaran lingkungan misalnya menyumbat saluran buang di lingkungan tempat tinggal (pemukiman), dan seterusnya. Apabila dibakar di alam terbuka juga menyebabkan resiko bencana (menggangu kesehatan, polusi udara, dan lainnya). Agar limbah plastik dapat bersahabat dengan alam, maka diperlukan pengelolaan sehingga dapat memberikan nilai ekonomi bagi pengelolanya.
2.  Pengumpulan dan Pembelian bahan baku limbah plastik yang paling banyak diproduksi dan sangat diminati oleh pasar adalah seperti PP, PET dan HDPE, sedangkan untuk jenis lain seperti LDPE, PVC dan PS diproduksi umumnya jika ada pesanan tertentu dari pasar industri ( buyer ) yang umumnya berlokasi di Binjai, Medan dan sekitarnya.
3.  Dengan bertambahnya jumlah penduduk khususnya di Aceh, serta kecenderungan konsumtif  yang meningkat baik rumah
tangga, kantor-kantor, pasar dan pabrikasi sehingga kecenderungan peningkatan jumlah limbah plastik secara masif  sangat dimungkinkan, sehingga potensi untuk mengembangkan usaha ini masih sangat dirasakan perlu keberadaannya.

## 6. Daftar Pustaka
Anonim, (1991). Tata cara pengolahan teknik sampah perkotaan (SNI  T-13-1990-F) . Departemen Pekerjaan Umum, Yayasan LPMB. Bandung.
Anonim, (1991). Tata Cara Pengelolaan Teknik Sampah Perkotaan , (SNI 19-2454-1991) . Departemen Pekerjaan Umum. Jakarta.
Chandra, Budiman. (2007). Pengantar Kesehatan Lingkungan. Jakarta: Penerbit  Buku Kedokteran. Hal. 124, dan 144-147.
HEKS, (2010). Media Partisipatif Untuk (Mengurangi) Resiko Perubahan Iklim dan Untuk (Menanggulangi) Bencanana: Kertas kerja edisi 5.
Kusnoputranto, H, (2000). Kesehatan Lingkungan. Edisi Revisi Fakultas Kesehatan  Masyarakat Universitas Indonesia, Jakarta.
Palapa Plastic Recycle Foundation (Edisi ke-2, 2008), Materi Pelatihan dan Petunjuk Praktis Untuk Pemulung, Kota Lhokseumawe.
Sharp Environmental Report (2004), Plastic Find New Life Using an Industry-First Technology. Collected Plastic and Pellete Recycled based on Sharp’s Closed-Loop Material Recycling Technology.
Slamet, Juli Soemirat (2009). Kesehatan Lingkungan. Cetakan Kedelapan. Gadjah  Mada University Press, Yogyakarta.
USAID Enviromental Services Program (2006).
Action Plan For Integrated Solid Waste Management In Nanggroe Aceh Darussalam,
Indonesia, hal (10-11). Vedder, T. 2008. Edible Film . http://japemethe. port5.com (diakses 26 Agustus 2009).
http://alamendah.wordpress.com/2009/07/17/ mengenal-bahaya-kemasan-plastik-dan- kresek/ diakses tanggal 29 September  20114 http://alamendah.wordpress.com/2009/07/23/ dampak-plastik-terhadap-lingkungan/ diakses tanggal 29 September 2014
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  finding 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 fixing 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 .
terbaik pada suatu generasi (Sri, Y.; Nurmaulidar; dan  Taufiq,  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  spesifikasi  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 first-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/fitness.
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,8
Sedangkan data yang digunakan pada penelitian ini adalah dataset TSPLib95 yang di download secara gratis dengan format type EUC_2D dengan
terbaik pada suatu generasi (Sri, Y.; Nurmaulidar; dan  Taufiq,  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  spesifikasi  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 first-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/fitness.
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,8 Sedangkan data yang digunakan pada penelitian ini adalah dataset TSPLib95 yang di download secara gratis dengan format type EUC_2D dengan
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 fitness dari tiap populasi. Untuk evaluasi kromosom-kromosom digunakan fungsi fitness 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 Lokal
Gambar 2 Flowchart Algoritma Populasi
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 fitness 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 fitness -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  memodifikasi  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  didefinisikan sebagai presentase dari jumlah gen pada populasi. Tingkat mutasi dapat mengontrol tingkat  gen  yang  akan  dimodifikasi.  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
Serambi Engineering, Volume II, No.4, Agustus 2017
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 fitness 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 fitness -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  memodifikasi  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  didefinisikan sebagai presentase dari jumlah gen pada populasi. Tingkat mutasi dapat mengontrol tingkat  gen  yang  akan  dimodifikasi.  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
diurutkan berdasarkan fungsi fitness -nya.
4. Selanjutnya rute dengan fungsi fitness 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 flowchart 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)
• Apabila telah memilih individu yang terbaik, individu tersebut disimpan ke dalam daftar list untuk menyatakan bahwa individu berikutnya. Setelah itu intensitas pheromone di sisi tersebut diubah dengan  menggunakan persamaan (5). Perubahan pheromone tersebut dinamakan perubahan pheromone local .  Aturan transissi kembali dilakukan sampai individu terbaik.
• Apabila individu terbaik telah dicapai, panjang rute dari masing-masing akan dilakukan perangkingan dengan metode Populasi untuk mencari individu yang terbaik.
• Pembaruan pheromone pada individu yang termuat  dalam daftar terbaik  tersebut menggunakan persamaan (6). Perubahan pheromone ini dinamakan perubahan pheromone secara global.
• Pengosongan daftar list, daftar list perlu dikosongkan untuk diisi lagi dengan urutan individu yang baru. Algoritma diulang lagi dari langkah 2 dengan parameter intensitas pheromone yang sudah di perbarui.
• Setelah semua proses telah dilalui (jumlah iterasi maksimum sudah terpenuhi) maka akan di dapatkan solusi terbaik.
5. Hasil Penelitian
Pada bab ini, akan dilakukan analisis pengujian terhadap implementasi sebelum dan sesudah digabungkan antara pencarian lokal dengan populasi dalam pencarian jarak terpendek dengan algoritma berevolusi dalam TSP. parameter yang digunakan dalam penelitian ini adalah jumlah populasi, jumlah offspring , dan jumlah generasi. Pengujian dilakukan 10 kali untuk setiap dataset yang digunkan serta masing-masing metode.  Dataset yang digunakan dalam analisis data adalah dataset TSPLib95 (Data TSPLib, 2016).
Pengujian pertama dilakukan pada metode pencarian lokal dengan jumlah 13 dataset setiap dataset akan diuji sebanyak 10 kali untuk mendatkan nilai yang paling minimum. Hasil dari 10 kali iterasi dari masing-masing dataset denganmetode pencarian lokal seperti yang ditampilkan pada Tabel 1.
Berdasarkan Tabel 1, dapat dijelaskan bahwa
nilai tersebut diambil dari nilai minimum, nilai maximum, nilai rata-rata, dan nilai diversity dari hasil 10 kali pengujian.
Tabel 2. adalah hasil dari 10 kali iterasi dari masing-masing dataset, maka dapat diperoleh hasil seperti dalam tabel 2 tersebut. Hasil yang diperoleh tersebut diambil dari nilai yang paling minimum, sehingga dengan data tersebut dapat memudahkan untuk menganalisis data.
Tabel 3 tersebut adalah hasil dari penggabungan antara pencarian lokal dengan populasi dengan masing-masing 10 kali iterasi pengujian. Hasil tersebut diambil dari nilai yang paling minimum. Dengan hasil tersebut, maka dapat dirumuskan bahwa metode hibridisasi pencarian lokal dengan popuasi lebih baik dapa pada pencarian lokal murni maupun populasi sendiri.
Berdasarkan tabel 4 di atas dapat adalah perbandingan dari nilai minimum dari masing- masing metode yang telah dijelaskan sebelumnya. Hasil tersebut dapat dijelaskan bahwa metode hibridisasi atau penggabungan antara pencarian lokal dengan populasi lebih baik dalam pencarian jarak terpendek, dari 13 dataset yang digunakan dalam penelitian ini umumnya lebih baik, hanya satu dataset saja yang tidak baik sehingga dapat diambil kesimpulan bahwa metode yang diusulkan lebih baik dalam pencarian jarak terpendek dari pada metode pencarian lokal maupun populasi.

## 6. Kesimpulan
Berdasarkan hasil pengujian dan pembahasan diatas dapat diambil kesimpulan sebagai berikut.
1. Algoritma pencarian lokal lebih baik dengan nilai yang paling minimum, namu tidak baik dalam diversisynya.
2. Algoritma populasi memiliki nilai diversity yang lebih baik tetapi kurang optimal.
3. Hasil implementasi algoritma hybrid pencarian lokal dengan populasi yang diusulkan pada penelitan ini lebih baik dalam hal optimalisasi maupun diversitynya.

## 7. Daftar Pustaka
Data TSPLib [Online] : http//www.iwr.uni. heidelberg.de/groups/comopt/software/TSP
Serambi Engineering, Volume II, No.4, Agustus 2017
• Apabila telah memilih individu yang terbaik, individu tersebut disimpan ke dalam daftar list untuk menyatakan bahwa individu berikutnya. Setelah itu intensitas pheromone di sisi tersebut diubah dengan  menggunakan persamaan (5). Perubahan pheromone tersebut dinamakan perubahan pheromone local .  Aturan transissi kembali dilakukan sampai individu terbaik.
• Apabila individu terbaik telah dicapai, panjang rute dari masing-masing akan dilakukan perangkingan dengan metode Populasi untuk mencari individu yang terbaik.
• Pembaruan pheromone pada individu yang termuat  dalam daftar terbaik  tersebut menggunakan persamaan (6). Perubahan pheromone ini dinamakan perubahan pheromone secara global.
• Pengosongan daftar list, daftar list perlu dikosongkan untuk diisi lagi dengan urutan individu yang baru. Algoritma diulang lagi dari langkah 2 dengan parameter intensitas pheromone yang sudah di perbarui.
• Setelah semua proses telah dilalui (jumlah iterasi maksimum sudah terpenuhi) maka akan di dapatkan solusi terbaik.

## 5. Hasil Penelitian
Pada bab ini, akan dilakukan analisis pengujian terhadap implementasi sebelum dan sesudah digabungkan antara pencarian lokal dengan populasi dalam pencarian jarak terpendek dengan algoritma berevolusi dalam TSP. parameter yang digunakan dalam penelitian ini adalah jumlah populasi, jumlah offspring , dan jumlah generasi. Pengujian dilakukan 10 kali untuk setiap dataset yang digunkan serta masing-masing metode.  Dataset yang digunakan dalam analisis data adalah dataset TSPLib95 (Data TSPLib, 2016).
Pengujian pertama dilakukan pada metode pencarian lokal dengan jumlah 13 dataset setiap dataset akan diuji sebanyak 10 kali untuk mendatkan nilai yang paling minimum. Hasil dari 10 kali iterasi dari masing-masing dataset denganmetode pencarian lokal seperti yang ditampilkan pada Tabel 1.
Berdasarkan Tabel 1, dapat dijelaskan bahwa
nilai tersebut diambil dari nilai minimum, nilai maximum, nilai rata-rata, dan nilai diversity dari hasil 10 kali pengujian.
Tabel 2. adalah hasil dari 10 kali iterasi dari masing-masing dataset, maka dapat diperoleh hasil seperti dalam tabel 2 tersebut. Hasil yang diperoleh tersebut diambil dari nilai yang paling minimum, sehingga dengan data tersebut dapat memudahkan untuk menganalisis data.
Tabel 3 tersebut adalah hasil dari penggabungan antara pencarian lokal dengan populasi dengan masing-masing 10 kali iterasi pengujian. Hasil tersebut diambil dari nilai yang paling minimum. Dengan hasil tersebut, maka dapat dirumuskan bahwa metode hibridisasi pencarian lokal dengan popuasi lebih baik dapa pada pencarian lokal murni maupun populasi sendiri.
Berdasarkan tabel 4 di atas dapat adalah perbandingan dari nilai minimum dari masing- masing metode yang telah dijelaskan sebelumnya. Hasil tersebut dapat dijelaskan bahwa metode hibridisasi atau penggabungan antara pencarian lokal dengan populasi lebih baik dalam pencarian jarak terpendek, dari 13 dataset yang digunakan dalam penelitian ini umumnya lebih baik, hanya satu dataset saja yang tidak baik sehingga dapat diambil kesimpulan bahwa metode yang diusulkan lebih baik dalam pencarian jarak terpendek dari pada metode pencarian lokal maupun populasi.

## 6. Kesimpulan
Berdasarkan hasil pengujian dan pembahasan diatas dapat diambil kesimpulan sebagai berikut.
1. Algoritma pencarian lokal lebih baik dengan nilai yang paling minimum, namu tidak baik dalam diversisynya.
2. Algoritma populasi memiliki nilai diversity yang lebih baik tetapi kurang optimal.
3. Hasil implementasi algoritma hybrid pencarian lokal dengan populasi yang diusulkan pada penelitan ini lebih baik dalam hal optimalisasi maupun diversitynya.

## 7. Daftar Pustaka
Data TSPLib [Online] : http//www.iwr.uni. heidelberg.de/groups/comopt/software/TSP
Lib95, di akses 20 Februari 2016. E. Samana, B. Prihandono, and E. Noviani. “Aplikasi Simulated Annealing Untuk Menyelesaikan Travelling Salesman Problem”. Buletin Ilmiah Mat. Stat. dan Terapannya (Bimaster) Volume 03, No.1 2015.
Erdiwansyah dan Taufik. A.G. Analisis Perbandingan Metode Local Search dan Population Based Dalam Algoritma Berevolusi untuk Penyelesaian Travelling Salesman Problem (TSP). Jurnal Serambi Engineering, Vol. 1, No.1, Agustus 2016. G. Ramani, N. Bouvanasilan, and V. Seenuvasan, “A Perspective View on Travelling Salesman Problem Using Genetic Algorithm,” Nature & Biologically  Inspired  Computing  in  Congress  IEEE International  Conference  on , vol., no., pp.356,361, 9-11 Dec. 2009.
I. H. Saputra, T. Octavia, and A. S. Chandra, “Tabu Searchsebagai Local Searchpada Algoritma Ant Colony”. JTI, Vol.11, No.2, pp. 188-194 Desember 2009.
S. Kumar, J. Kurmi, and S.P. Tiwari., “Hibrida Ant Colony Optimization and Cuckoo Search Algorithm for Travelling Salesman Problem”. International  Journal  of   Scientific  and  Research Publications , Volume 5, Issue 6, June 2015.
Sri, Y.; Nurmaulidar; dan Taufiq, A.G., “Pengaruh elitism dalam penyelesaian permasalahan Penjadwalan mesin dengan menggunakan algoritma Berevolusi,” Konferensi Nasional Sistem dan Informatika 2011; Bali, November 12, 2011.
T. Mustafa, and R. Abiyev, “Hibrida Local Search Based Genetic Algorithm and Its Practical Application”. International  Journal  of   Soft Computing and Engineering (IJSCE) ISSN: 2231- 2307, Volume-5, Issue-2, May 2015.
W. Maharani, “Analisis Algoritma Hybrid Ant Colony Optimization (Aco) Dan Local Search Untuk Optimasipemotongan Bahan Baku”. Seminar Nasional Aplikasi Teknologi Informasi 2009.
Zne-Jung Lee, “ A hibrida algorithm applied to travelling salesman problem ” Networking, Sensing and Control , 2004 IEEE International Conference, vol. 1, no.pp.237, 242 Vol. 1, 21-23 March 2004.