serambi engineering, volume ii, no.4, agustus 2017 edisi...

Serambi Engineering, Volume II, No.4, Agustus 2017 ISSN : 2528-3561Edisi Khusus

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. Kesimpulan1. 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 PustakaAnonim, (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

164 165


1. PendahuluanTraveling 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 IslamadinaTeknik Informatika, Fakultas Teknik, Universitas Serambi Mekkah

Jl. Tgk. Imum Lueng Bata Desa Bathoh, Kota Banda Aceh, Propinsi Aceh, Indonesia*Koresponden Email: [email protected]

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.

164 165


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 rule2. 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 LiteraturPada 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 PenelitianPada 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 individu2. Proses Seleksi = Roulette Wheel3. Proses Mutasi = Insertion dan Inversion4. Probalitas Crossover = 0,55. 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

166 167


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 rule2. 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 LiteraturPada 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 PenelitianPada 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 individu2. Proses Seleksi = Roulette Wheel3. Proses Mutasi = Insertion dan Inversion4. Probalitas Crossover = 0,55. 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

166 167


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 AlgoritmaAlgoritma 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). Fvi =

, dimana R adalah rute yang terbentuk fx = (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

166 167


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 Pm 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

168 169


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 Pm 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

168 169


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)

169


• 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 PenelitianPada 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

170 171


• 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 PenelitianPada 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

170 171


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.

170 171

serambi engineering, volume ii, no.4, agustus 2017 edisi...

Documents