ADLN - Perpustakaan Universitas Airlangga
Muhamad Jainal Abidin, 2012. Hybrid Algorithm Ant Colony Optimization dan Genetic Algorithm untuk Menyelesaikan Quadratic Assignment Problem. Skripsi ini di bawah bimbingan Herry Suprajitno, S.Si, M.Si, dan Dr. Miswanto, M.Si,. Departemen Matematika. Fakultas Sains dan Teknologi. Universitas Airlangga. ABSTRAK Penulisan skripsi ini bertujuan untuk menyelesaikan masalah penugasan kuadratik dengan menggunakan Hybrid Ant Colony Optimization dan Genetic Algorithm. Tujuan dari permasalahan penugasan kuadratik adalah menempatkan fasilitas pada lokasi, sehingga dapat meminimalkan total jarak tempuh perpindahan bahan antar fasilitas. Ant Colony Optimization adalah suatu algoritma yang mengambil inspirasi dari perilaku semut nyata. Sedangkan Genetic Algorithm adalah sebuah algoritma yang diinspirasikan oleh proses evolusi yang sangat dipengaruhi oleh proses mutasi dan crossover. Pada skripsi ini digunakan insertion mutation dan partial-mapped crossover. Program dibuat dalam bahasa pemrograman java untuk menerapkan Hybrid Ant Colony Optimization dan Genetic Algorithm dalam pencarian solusinya. Berdasarkan hasil yang diperoleh ditunjukkan bahwa semakin besar nilai alpha dan Pc, semakin kecil nilai betha, rho dan koefisien Q, maka solusi yang didapatkan semakin mendekati solusi optimal. Kata kunci : Hybrid, ant colony optimization, genetic algorithm, Masalah Penugasan Kuadratik.
vii Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Muhamad Jainal Abidin, 2012. Hybrid Algorithm Ant Colony Optimization dan Genetic Algorithm untuk Menyelesaikan Quadratic Assignment Problem. This Skripsi is supervised by Herry Suprajitno, S.Si, M.Si, and Dr. Miswanto, M.Si,. Mathematics Department, Faculty of Science and Technology, Airlangga University. ABSTRACT The purpose of this paper is to solve quadratic assignment problems using hybrid ant colony optimization and genetic algorithm. The purpose of the quadratic assignment problem is to place n facilities to n locations, in order to minimize the total distance of materials movement among facilities. Ant colony optimization is an algorithm inspired by the behavior of real ants. Whereas genetic algorithm is an algorithm inspired by evolutionary proces which is strongly influenced by the process of mutation and crossover. In this paper, we used insertion mutation and partial-mapped crossover methods. The program is made in java language program to implement the hybrid ant colony optimization and genetic algorithm in searching the solutions. Based on the results obtained, it showed that the larger value of alpha and Pc, and the smaller value of betha, rho and coefficient Q, then the solution approaches the optimal solution. Keywords: Hybrid, ant colony optimization, genetic algorithm, quadratic assignment problem.
viii Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
DAFTAR ISI HALAMAN JUDUL................................................................................... i LEMBAR PERNYATAAN ........................................................................ ii LEMBAR PENGESAHAN ........................................................................ iii LEMBAR PEDOMAN PENGGUNAAN SKRIPSI................................... iv KATA PENGANTAR ................................................................................ v ABSTRAK .................................................................................................. vii ABSTRACT ................................................................................................ viii DAFTAR ISI ............................................................................................... ix DAFTAR TABEL ....................................................................................... xi DAFTAR GAMBAR .................................................................................. xii DAFTAR LAMPIRAN ............................................................................... xiii BAB I PENDAHULUAN ........................................................................ 1 1.1 Latar Belakang ........................................................................ 1 1.2 Rumusan Masalah ................................................................... 3 1.3 Tujuan ..................................................................................... 4 1.4 Manfaat ................................................................................... 4 1.5 Batasan Masalah ..................................................................... 5 BAB II TINJAUAN PUSTAKA................................................................ 6 2.1 Graph ...................................................................................... 6 2.2 Permasalahan Penugasan ........................................................ 7 2.2.1 Penugasan Quadratik .................................................... 8 2.3 Ant Colony Optimization (ACO) ............................................ 10 2.4 Genetik Algoritma .................................................................. 15 2.5 Hybrid ACO dan GA .............................................................. 23 2.6 Pemrograman Java .................................................................. 23 BAB III METODE PENELITIAN.............................................................. 26 BAB IV PEMBAHASAN ........................................................................... 32 4.1 Masalah Penugasan Kuadratik ................................................ 32 4.2 Prosedur Hybrid Algorithm Ant Colony Optimization dan Genetic Algorithm ................................................................. 32 4.2.1 Pengisian Parameter ...................................................... 34 4.2.2 Inisialisasi ..................................................................... 35 4.2.3 Pengisian Tabu List ....................................................... 36 4.2.4 Menghitung Nilai Fungsi Tujuan .................................. 39 4.2.5 Menyimpan Solusi Terbaik ........................................... 41 4.2.6 Memperbarui Matriks Pheromone ................................ 42 4.2.7 Generate Pop_size ........................................................ 43 4.2.8 Menghitung Nilai Fungsi Tujuan .................................. 44 4.2.9 Seleksi ........................................................................... 44 4.2.10 Seleksi Crossover ....................................................... 46 4.2.10.1 Crossover ............................................................ 46 4.2.11 Seleksi Mutasi ............................................................. 48 4.2.11.1 Mutasi.................................................................. 49
ix Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
4.2.12 Evaluasi Anak ............................................................. 50 4.2.13 Populasi Baru .............................................................. 50 4.3 Data ......................................................................................... 51 4.4 Contoh Kasus Quadratic Assignment Problem dengan Menggunakan Data 4 Fasilitas dan 4 Lokasi yang Diselesaikan Secara Manual ............................................................................... 51 4.4.1 Pengisian Parameter yang Dibutuhkan ......................... 52 4.4.2 Pengisian Tabu List ....................................................... 53 4.4.3 Menghitung Nilai Fungsi Tujuan .................................. 58 4.4.4 Menyimpan Solusi Terbaik ........................................... 60 4.4.5 Memperbarui Matriks Pheromone ................................ 60 4.4.6 Cek Siklus ..................................................................... 62 4.4.7 Men-generate Populasi Awal ....................................... 62 4.4.8 Seleksi ........................................................................... 63 4.4.9 Crossover ...................................................................... 66 4.4.10 Mutasi ......................................................................... 67 4.4.11 Evaluasi Anak ............................................................. 68 4.4.12 Populasi Baru .............................................................. 68 4.4.13 Cek Siklus ................................................................... 70 4.5 Implementasi program Pada Contoh Kasus Quadratic Assignment Problem ..................................................................... 70 4.5.1 Menggunakan Data 4 fasilitas dan 4 Lokasi ................. 70 4.5.2 Menggunakan Data 12 fasilitas dan 12 Lokasi ............. 71 4.5.3 Menggunakan Data 20 fasilitas dan 20 Lokasi ............. 73 4.6 Perbandingan Hasil Perhitungan dengan Parameter yang Berbeda pada Hybrid ACO dan GA untuk QAP .......................... 75 4.7 Perbandingan Hasil Perhitungan QAP dengan Menggunakan Hybrid ACO dan GA dengan Penelitian Hadley, S. W., (1992) .. 78 BAB V KESIMPULAN DAN SARAN ...................................................... 79 5.1 Kesimpulan ............................................................................. 79 5.2 Saran ....................................................................................... 80 DAFTAR PUSTAKA ................................................................................. 81 LAMPIRAN
x Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
DAFTAR TABEL Tabel 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27
Judul Probabilitas pada j = 0 Probabilitas komulatif semut ke-0 pada j = 0 Bilangan acak pada j = 0 Tabu list pada j = 0 Probabilitas pada j = 1 Bilangan acak pada j = 1 Tabu list pada j = 1 Probabilitas pada j = 2 Bilangan acak pada j = 2 Tabu list pada j = 2 Tabu list pada j = 3 Nilai fungsi tujuan Individu populasi awal Nilai fungsi tujuan individu Probabilitas komulatif Random untuk calon induk crossover Random untuk calon induk mutasi Nilai fungsi tujuan anak Gabungan individu Urutan individu Populasi baru Nilai fungsi tujuan dengan pembanding alpha Nilai fungsi tujuan dengan pembanding betha Nilai fungsi tujuan dengan pembanding rho Nilai fungsi tujuan dengan pembanding koefisien Q Nilai fungsi tujuan dengan pembanding Perbandingan nilai optimal
Halaman 54 55 55 55 56 56 57 57 57 58 58 60 62 63 65 66 66 68 69 69 69 75 76 76 77 77 78
xi Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
DAFTAR GAMBAR Gambar 2.1 3.1 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22
Judul Percobaan yang dilakukan Gass, dkk., 1989 Skema flowchart hybrid ACO dan GA Prosedur Hybrid ACO dan GA Prosedur pengisian parameter Prosedur inisialisasi Prosedur pengisian tabu list Flowchart pengisian tabu list Prosedur menghitungan probabilitas Prosedur hitung penyebut Prosedur cek node Prosedur memilih fasilitas Prosedur fungsi tujuan Prosedur isi x Prosedur penyimpanan solusi Prosedur update pheremone Prosedur menghitung delta Prosedur generate pop_size Prosedur men-generate individu dengan menggunakan permutasi Prosedur seleksi Prosedur seleksi crossover Prosedur crossover PMX Prosedur seleksi mutasi Prosedur insertion mutation Prosedur populasi baru
Halaman 11 31 33 34 35 36 37 38 38 39 39 40 41 41 42 42 43 44 45 46 48 49 50 51
xii Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
DAFTAR LAMPIRAN No. 1. 2. 3. 4.
Judul Lampiran Data Quadratic Assignment Problem Source Code Program Hasil implementasi Program pada QAP Output
xiii Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
BAB I PENDAHULUAN
I.1 Latar Belakang Era globalisasi menuntut semua persaingan disegala aspek, salah satunya adalah persaingan di pasar global. Perusahan-perusahan bersaing untuk memperoleh hasil optimal dalam pencapaian kesuksesan perusahan. Banyak cara untuk menggapai hal tersebut salah satunya adalah pengoptimalan dalam sisi penugasan, dimana perusahan ingin memperoleh hasil yang optimal dari penugasan yang diberikan dengan pengeluaran biaya yang sangat minimal. Metode penugasan merupakan sebuah pelimpahan tugas atau pekerjaan pada sumber daya yang ada. Setiap sumber atau petugas (assignee) ditugasi secara khusus untuk suatu kegiatan atau tugas. Tujuan utamanya adalah meminimalisasi biaya total atau waktu yang diperlukan untuk melaksanakan tugas yang ada. Quadratic Assignment Problem (QAP) adalah masalah penugasan yang fungsi tujuannya berbentuk kuadrat dan merupakan salah satu pokok masalah optimalisasi combinatorial. Optimalisasi combinatorial adalah cabang dari ilmu optimalisasi dalam aplikasi matematika dan ilmu komputer yang umumnya berhubungan dengan operation research, teori algoritma dan teori kompleksitas komputasional yang berada pada dua persilangan dengan beberapa ruang ilmu lainnya, seperti intelegensia buatan, matematika dan software engineeering. Algoritma optimalisasi kombinatorial biasanya ditujukan untuk masalah yang
1 Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
2
dianggap NP-hard problems. Masalah tersebut dianggap tidak dapat dicari solusinya dengan efisien (Prana, 2007). QAP berukuran n terdiri dari pencarian alokasi terbaik dari n fasilitas ke n lokasi, dengan diketahui arus dari fasilitas dan jarak antar lokasi, supaya jumlahan antara arus dan jarak minimal. Pertama kali, masalah ini dirumuskan dalam (Koopmans dan Beckman, 1957), dan berkembang pada berbagai aplikasi, contohnya: perencanaan pembangunan di kampus, pengaturan departemen pada rumah sakit, perencanaan tata letak (layout), dan lain sebagainya. Pada umumnya permasalahan optimalisasi combinatorial merupakan masalah yang cukup sulit untuk diselesaikan. Beberapa algoritma yang telah dikembangkan untuk menyelesaikan masalah optimalisasi combinatorial antara lain: Genetic Algorithm, Simulated Anealing, Tabu Search dan Ant Colony Optimization. Pada skripsi (Kurniawan, 2008) telah dilakukan pengkajian ”Pendekatan Algoritma Semut untuk Persoalan Penugasan Kuadratik.” Ant Colony Optimization (ACO) dikemukakan pada tahun 1991 oleh Marco Dorigo, merupakan suatu algoritma yang mengambil inspirasi dari riset atas perilaku semut riil yang di dalamnya terdapat sekumpulan semut buatan (ants), yang bekerja sama untuk mencari solusi terhadap suatu masalah optimalisasi berdasarkan pheromone (suatu zat yang ditinggalkan oleh semut yang berisi sejumlah informasi). Dengan perantara pheromone inilah terjadi komunikasi tidak langsung dan juga pertukaran informasi antar semut ketika membangun suatu solusi. Bentuk komunikasi tidak langsung yang diperlihatkan oleh semut ini disebut stigmergy.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
3
Algoritma genetika (GA) merupakan algoritma yang diinspirasikan oleh proses evolusi. Algoritma genetika dapat disifatkan melalui populasi dan operator – operatornya, yaitu selection ( menentukan individu yang akan menjadi induk ), crossover ( perkawinan antar induk untuk memperoleh individu baru ), dan mutation ( perubahan sebagian sifat individu ). Algoritma genetik juga merupakan algoritma yang cukup open trial karena peneliti dapat mengeksplor algoritma genetik dasar untuk menambahkan beberapa kondisi. Hybrid menurut bahasa berarti campuran atau gabungan, jadi hybrid algorithm merupakan suatu algoritma yang digunakan untuk menyelesaikan suatu permasalahan yang menggunakan dua algoritma berbeda atau lebih (Dechter, 2011). Berdasarkan uraian diatas penulis tertarik untuk membahas bagaimana hybrid antara algoritma Ant Colony Optimization dan algoritma genetik (Genetic Algorithm) untuk menyelesaikan Quadratic Assignment Problem. Diharapkan dengan Hybrid antara ACO dan GA untuk menyelesaikan QAP dapat mendapatkan hasil yang lebih baik dan tidak terjadi kehomogenan lebih cepat. Untuk itu penulis ingin menerapkan Hybrid Algorithm Ant Colony Optimization dan Genetic Algorithm untuk menyelesaikan Quadratic Assignment Problem.
I.2 Rumusan Masalah Berdasarkan uraian latar belakang diatas, maka penulis merumuskan permasalahan dalam proposal skripsi adalah sebagai berikut :
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
4
1. Bagaimana menerapkan hybrid Ant Colony Optimization dan Genetic Algorithm untuk QAP? 2. Bagaimana
membuat
program
penggunaan
hybrid
Ant
Colony
Optimization dan Genetic Algorithm untuk QAP dengan menggunakan bahasa pemrograman java? 3. Bagaimana mengimplementasikan program pada contoh kasus QAP ?
I.3 Tujuan Dalam penulisan proposal skripsi ini, penulis mempunyai tujuan sebagai berikut : 1. Menerapkan hybrid Ant Colony Optimization dan Genetic Algorithm untuk QAP. 2. Membuat program penggunaan hybrid Ant Colony Optimization dan
Genetic Algorithm untuk QAP dengan menggunakan bahas apemrograman java. 3. Mengimplementasikan program pada contoh kasus QAP.
I.4 Manfaat Adapun manfaat yang nantinya akan didapatkan adalah sebagai berikut : 1. Dari hasil skripsi ini nantinya, diharapkan dapat menjadi referensi alternatif metode penyelesaian yang dapat digunakan untuk menyelesaikan QAP dalam perencanaan tata letak (layout).
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
5
2. Diharapkan pula dapat menjadi bahan pertimbangan dan perbandingan untuk penerapan algoritma lainnya pada QAP yang dapat mendukung perkembangan ilmu pengetahuan dan teknologi pada masa mendatang.
I.5 Batasan Masalah Mengacu pada rumusan masalah diatas, maka ruang lingkup penyelesaian QAP dengan hybrid Ant Colony Optimization dan Genetic Algorithm dalam penulisan proposal skripsi ini dibatasi pada penggunaan : 1. Jumlah fasilitas sama dengan jumlah lokasi pada QAP. 2. Pengkodean, solusi awal dari ACO direpresentasikan dengan pengkodean permutasi. 3. Proses Crossover mengunakan Partial-Mapped Crossover (PMX). 4. Proses mutasi menggunakan Mutasi Sisipan (Insertion Mutation).
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
BAB II TINJAUAN PUSTAKA
Dalam penulisan ini, dibutuhkan beberapa definisi atau informasiinformasi guna untuk memperdalam materi dan mempermudah dalam penulisan skripsi, diantaranya sebagai berikut : 2.1 Graph Definisi 2.1 Graph G didefinisikan sebagai himpunan berhingga V(G) yang tidak kosong yang anggotanya disebut titik (vertice) dan himpunan E(G) yang mungkin kosong, yang anggotanya terdiri dari pasangan tidak terurut dua elemen yang berbeda dari V(G) dan disebut garis (edge). Elemen dari V(G) dinotasikan dengan
vi dan elemen dari E(G) dinotasikan dengan vi v j dan kadang dinotasikan dengan ei . Jika terdapat garis e yang menghubungkan titik v i dan v j maka v i dikatakan terhubung (adjacent) dengan v j dalam hal ini titik v i dan v j dikatakan insiden dengan e . Definisi 2.2
Digraph D adalah himpunan tak kosong yang berhingga
V (D) dari titik dan himpunan E (D) (yang kemungkinan himpunan kosong) dari pasangan titik yang terurut. Arc (garis berarah) adalah elemen-elemen dari E (D) .
6 Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
7
Definisi 2.3
Perjalanan (walk) pada digraph D adalah urutan secara bergantian titik-titik elemen V (D) dan arc elemen E (D) yang terbentuk :
W v0 , e1 , v1 , e2 , v2 ,..., vn1 , en , vn
, untuk n 0
yang dimulai dan diakhiri dengan titik, sedemikian sehingga
ei (vi 1 , vi ) untuk i = 1, 2, ..., n. Definisi 2.4
cycle adalah walk v0, v1, v2, ..., vn-1, vn dengan n 3 , v0 vn dan titik-titik v0, v1, v2, ..., vn-1, vn yang berbeda satu dengan yang lain. Dengan kata lain cycle adalah walk yang tertutup.
Definisi 2.5
path adalah walk dimana titiknya tidak boleh berulang. (Chartrand dan Oellerman, 1993)
2.2 Permasalahan Penugasan Masalah penugasan yaitu mengalokasikan sumber-sumber kepada kegiatan-kegiatan atas dasar satu-satu (one to one basis). Jadi setiap sumber atau petugas (assignee) ditugasi secara khusus kepada suatu kegiatan atau tugas. Terdapat biaya yang berkaitan dengan sumber dan kegiatannya, sehingga tujuannya adalah bagaimana menentukan semua tugas yang dilakukan dengan biaya seminimal mingkin.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
8
Model masalah penugasan adalah sebagai berikut: Meminimalkan :
n
n
z cij xij i 1 j 1
dengan kendala :
n
x j 1
ij
1,
i = 1,2,…,n
ij
1,
j = 1,2,…,n
n
x i 1
xij {0,1}
i,j = 1,2,…,n
dengan : z
= biaya total yang diperlukan untuk menugaskan n tugas pada n petugas.
cij
= biaya yang diperlukan untuk menugaskan petugas i pada tugas j.
xij
= penugasan petugas i pada tugas j, dengan i,j = 0,1,…,n dan
1, xij 0, n
jika petugas i ditugaskan pada tugas j lainnya
= jumlah petugas. (Taha, 1996)
2.2.1 Penugasan Kuadratik Masalah penugasan kuadratik merupakan masalah penugasan yang fungsi tujuannya berbentuk kuadrat. Masalah penugasan kuadratik pada umumnya mempunyai konsep yang serupa dengan penugasan dari fasilitas pada suatu lokasi dengan tujuan untuk meminimalkan biaya pergerakan materi antar fasilitas. Fungsi tujuan dengan bentuk kuadratik melibatkan perkalian dua variable bebas.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
9
Bentuk kuadratik banyak digunakan pada fungsi obyektif untuk masalah layout fasilitas. (Gass dan Harris, 1996) Secara umum model penugasan quadratik adalah sebagai berikut: Minimumkan
n
n
n
n
z cijkl xij xkl i 1 j 1 k 1 l 1
atau Minimumkan
n
n
n
n
z f ik d jl xij xkl
(2.1)
i 1 j 1 k 1 l 1
dengan kendala:
n
x j 1
ij
1,
i = 1,2,…,n
ij
1,
j = 1,2,…,n
n
x i 1
xij {0,1},
i,j = 1,2,…,n
(2.2)
dengan: z
= biaya total yang diperlukan untuk menugaskan n fasilitas pada n lokasi.
cijkl
= biaya yang berhubungan dengan penugasan fasilitas i pada lokasi j dan fasilitas k pada lokasi l.
Skripsi
f ik
= frekuansi perpindahan bahan dari fasilitas i ke fasilitas k.
d jl
= jarak antara lokasi j ke lokasi l.
x ij
= penugasan fasilitas i pada lokasi j, dengan i,j = 0,1,…,n dan
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
10
1, jika fasilitas i ditugaskan pada lokasi j xij 0, lainnya
x kl
= penugasan fasilitas k pada lokasi l, dengan k,l = 0,1,…,n dan
1, jika fasilitas k ditugaskan pada lokasi l x kl 0, lainnya n
= jumlah fasilitas. (Gen dan Cheng, 1997)
2.3 Ant colony Optimization (ACO) Algoritma merupakan suatu himpunan langkah-langkah atau intruksi yang telah dirumuskan dengan baik (well defined) untuk memperoleh suatu keluaran khusus (specific output) dari suatu masukan khusus (specific input) dalam langkah-langkah yang jumlahnya berhingga. (Chartrand dan Oellermann, 1993)
Gass, dkk (1989) membuat percobaan dengan menggunakan spesies semut Iridomyrmex humilis (semut Argentina). Percobaan itu untuk menunjukkan kemampuan kerjasama semut untuk mendapatkan jalan terpendek menuju sumber makanan. Percobaan tersebut seperti terlihat pada Gambar 2.1. Pada percobaan tersebut, diantara sumber makanan dan sarang semut diletakkan 2 jembatan dengan panjang yang tidak sama. Semut harus memilih diantara 2 jembatan tersebut dan ternyata didapatkan 2 hal yang menarik yaitu: a. Setelah periode tertentu ternyata paling banyak semut memilih jembatan yang lebih pendek.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
11
b. Probabilitas untuk memilih jalan yang lebih pendek sebanding dengan jarak antara 2 cabang. Tingkah laku pemilihan jalan terpendek ini adalah hasil timbal balik positif (autokatalitis) dan perbedaan panjang jalan. Hal ini diperoleh melalui stimergy, bentuk komunikasi tidak langsung seperti digambarkan berikut ini: Stimergy didefinisikan sebagai perubahan lokal dari lingkungan. Perubahan ini disebabkan karena ketika semut pergi, semut-semut itu meninggalkan zat kimia yang disebut pheromone. Setiap pemilihan titik, semut membuat keputusan yang diwujutkan dalam bentuk banyak sedikitnya pheromone. Proses ini merupakan proses autokatalis karena dalam kenyataannya seekor semut yang memilih jalan dalam gilirannya akan menambah pheromone seperti yang dilakukan oleh semut lainnya pada saat kemudian.
Gambar 2.1 Percobaan yang dilakukan Gass, dkk., 1989
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
12
Pada gambar 2.1, semut 1 dan semut 2 meninggalkan sarang pada waktu yang sama. Semut-semut tersebut sampai pada titik pilihan 1 bersama-sama dan membuat keputusan 0,5:0,5 untuk memilih cabang. Semut 1 memilih cabang yang lebih pendek dan mencapai sumber makanan lebuh dulu (melalui titik A), mengambil makanan dan kembali lagi ke sarangnya. Ketika kembali pada titik pilihan 2, semut tersebut mendeteksi pheromone pada cabang yang lebih pendek (pheromone yang ditaruh oleh semut 1 itu sendiri pada saat perjalanan menuju sumber makanan) dan dengan probabilitas yang tinggi untuk memilih cabang itu kembali. Pada cabang yang lebih jauh tidak mengandung pheromone di dekat titik percabangan, karena semut yang memilihnya (termasuk semut 2) belum sampai pada titik pilihan 2. Pada akhirnya kedua semut pada saat menuju dan dari sumber makanan akan mengambil jalan yang lebih pendek dengan probabilitas yang tinggi dan pheromone yang ada pada cabang yang lebih panjang tidak diberi penguatan lagi karena tidak ada semut yang menaruh pheromone disitu akan menguap dan semut akan berjalan pada jalan yang paling pendek. Dari percobaan yang digambarkan pada Gambar 2.1 disusun sebuah algoritma untuk mencari solusi dari sebuah permasalahan optimalisasi combinatorial yang dinamakan Ant colony Optimization (ACO). Dalam buku karya Gaertner (2004) ACO secara umum adalah terdapat sejumlah populasi semut buatan (ant) yang melakukan sebuah perjalanan untuk membentuk solusi dari sebuah permasalahan optimaliasi kombinatorik. Algoritma ini menyatakan permasalahan kombinatorik kedalam sebuah graph, ant melakukan perjalanan
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
13
pada setiap cabang dari node satu ke node yang lain sehingga membentuk suatu path yang merupakan representasi dari solusi pada permasalahan tersebut. Hal yang membedakan antara semut sebenarnya dengan semut pada algoritma semut ini yang didefinisikan Dorigo, dkk. (1996) adalah sebagai berikut: a. Semut pada algoritma ini akan memiliki ingatan (memory) b. Semut pada algoritma ini tidak sepenuhnya buta c. Semut pada algoritma ini hidup pada lingkungan dengan waktu yang diskrit. Pada Dorigo, dkk. (1996) Langkah–langkah ACO adalah sebagai berikut : 1.
Inisialisasi parameter, yaitu : Alpha (α) = Tetapan pengendali intensitas Pheromone ( 0 ). Betha (β) = Tetapan pengendali visibilitas ( 0 ).
ij (t )
= Nilai Pheromone antara node i dan node j disaat t.
t
= Iterasi ke-w , dengan w = 1,2,3,...,max_iterasi.
= Koefisien penguapan intensitas pheromone
dij
= Jarak antara node i dan node j.
Q
= Konstanta yang mempengaruhi update pheromone.
Jumlah Semut, Jumlah Node dan Max_iterasi. 2.
Menempatkan sejumlah ant pada node awal
3.
Mengisi tabu list dengan cara menghitung nilai probabilitas dari node awal ke node yang akan dikunjungi. Tabu list adalah tempat yang disediakan untuk penyimpanan sementara dari solusi – solusi yang dihasilkan pada tiap iterasi. Persamaan untuk menentukan nilai probabilitas sebagai berikut :
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
14
( )
( ) ∑
(2.3)
( )
Tetapi untuk menentukan nilai probabilitas dari node awal ke node yang akan dikunjungi untuk Quadratic Assigment Problem menggunakan persamaan :
( )
( ) ∑
(2.4)
( )
keterangan :
( ) = probabilitas dari node i ke node j disaat t.
4.
Menghitung panjang perjalanan. Setelah semua semut menyelesaikan satu siklus selanjutnya dihitung panjang perjalanan. Indeks s menyatakan indeks urutan perjalanan, node asal dinyatakan tabuk (s) dan node – node lainnya dinyatakan sebagai {N-tabuk}. Menghitung panjang perjalanan dengan rumusan sebagai berikut : ( )
( )
∑
( )
(
)
(2.5)
Tetapi pada Quadratic Assigment Problem menghitung pangjang perjalanan menggunakan persamaan : (2.6) dengan k = semut ke-k yang bertugas untuk fasilitas ke i ke lokasi j dan k = 0,1,2,...,n-1.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
15
Keterangan : d = jarak antar lokasi. = biaya total fungsi tujuan semut ke-k. 5.
Perbaruhi matrik pheromone m
k ij t 1 . ij t ij
(2.7)
k 1
k
dengan ij adalah perubahan harga pheromone antar node setiap semut yang dihitung berdasarkan persamaan
Q k , ij Lk 0, 6.
untuk
node dalam tabuk (2.6) untuk (i,j) lainnya
Apabila siklus maksimum atau kondisi stagnan belum terpenuhi, maka kosongkan tabu list dan kembali ke langkah 2. Apabila siklus maksimum atau kondisi stagnan telah terpenuhi maka iterasi berakhir. Kondisi stagnan yaitu kondisi semua ant mendapatkan solusi yang sama.
2.4 Genetik Algoritma Berikut akan diberikan definisi algoritma genetik : Definisi 2.6
Algoritma genetika (GA) merupakan sebuah kelompok dari metode-metode
untuk
menyelesaikan
permasalahan-
permasalahan dengan menggunakan algoritma yang diinspirasi oleh proses evolusi. (Obitko, 1998)
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
16
Konsep GA secara sederhana dimulai dengan menentukan populasi awal. Beberapa definisi yang terkait akan disajikan sebagai berikut : Definisi 2.7
Masing-masing individu yang terdapat dalam populasi yang merupakan suatu solusi suatu permasalahan disebut individu. (Gen dan Cheng, 1997)
Definisi 2.8
Himpunan solusi (yang digambarkan dengan individu) disebut populasi. (Gen dan Cheng, 1997)
Definisi 2.9
Individu terdiri dari sejumlah struktur tersendiri yang disebut gen. (Obitko, 1998)
Definisi 2.10 Setiap gen mempunyai posisi pada individu yang disebut locus. (Obitko, 1998) Definsi 2.11 Individu akan berkembang melalui iterasi yang berturut-turut yang disebut sebagai generasi. (Gen dan Cheng, 1997) Definisi 2.12 Jumlah individu yang membentuk sebuah populasi pada satu generasi disebut sebagai ukuran populasi (pop_size). (Obitko, 1998) Definisi 2.13 Pengkodean (encoding) merupakan suatu cara menyajikan suatu solusi dalam ruang pencarian. (Obitko, 1998)
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
17
Ada beberapa cara untuk mengkode suatu individu diantaranya: 1. Pengkodean Biner Dalam pengkodean biner, individu dikodekan sebagai barisan bit 0 atau 1. 2. Pengkodean Nilai Dalam pengkodean nilai, setiap individu adalah barisan beberapa nilai. 3. Pengkodean Permutasi Dalam pengkodean permutasi, setiap individu adalah barisan angka yang memperhatikan urutan dan posisi sehingga tidak terjadi adanya pengulangan angka. 4. Pengkodean random Keys (Nomor Acak) Dalam random keys, setiap individu adalah barisan angka random yang berkisar antara 0 dan 1. (Obitko, 1998) Populasi yang telah dibangkitkan kemudian dievaluasi dengan menghitung nilai fitness masing – masing individu dalam populasi. Selanjutnya dilakukan proses seleksi yang merupakan operasi evolusi dalam algoritma genetik. Definisi 2.14 Fungsi fitness adalah fungsi yang menunjukkan keandalan suatu individu untuk bertahan dalam populasi. (Zomaya, 1996) Definisi 2.15 Seleksi (selection) merupakan proses pemilihan individu dari populasi untuk menjadi induk crossover atau induk mutasi.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
18
Menurut teori evolusi, individu yang terbaik seharusnya bertahan dan membentuk keturunan baru. (Obitko, 1998) Ada beberapa jenis seleksi, diantaranya adalah : a. Seleksi Elitism. Seleksi ini dilakukan dengan mengkopi beberapa individu terbaik untuk menjadi populasi yang baru (mempertahankan individu dengan fitness terbaik). Sisanya dilakukan dengan menggunakan cara klasik. b. Seleksi Roda Rolet. Sebuah roda rolet yang ditempati semua individu dalam populasi, dimana masing-masing individu menempati luasan menurut nilai fitnessnya. Selanjutnya roda rolet diputar untuk memilih individu yang akan dijadikan induk crossover atau induk mutasi. Individu dengan fitness yang lebih besar akan berpeluang untuk dipilih. (Obitko, 1998) Jika pada permasalahan fungsi tujuannya adalah untuk meminimalkan, maka seleksi roda rolet dapat diubah sebagai berikut : 1. Menghitung total fungsi tujuan f (v j ) setiap individu v j untuk populasi: pop _ host
f (v j 1
j
)
(2.8)
2. Menghitung nilai fitness untuk setiap individu v j :
pop_ size f (vk ) k 1
Skripsi
f( )
HYBRID ALGORITHM ANT COLONY...
(2.9)
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
19
3. Menghitung total nilai fitness untuk populasi :
F
pop _ host
fithost j 1
(2.10)
j
4. Menghitung probabilitas seleksi p j untuk setiap individu v j : pj
fithost j F
, j = 1, 2, ..., pop_host
(2.11)
5. Menghitung probabilitas kumulatif q j untuk setiap individu v j : j
q j pi , j = 1, 2, ..., pop_host
(2.12)
i 1
6. Melakukan generate bilangan acak dari interval [0,1] = s. 7. Jika s q1 , maka ditentukan menjadi individu pertama v1 ; sebaliknya, menentukan individu v j ke j 2 j pop _ host dengan q j 1 s q j . (Gen dan Cheng, 1997) Individu-individu yang telah terpilih dalam proses seleksi selanjutnya akan diproses crossover dan mutasi. Definisi 2.16 Crossover adalah proses penggabungan (persilangan) antara dua induk untuk mendapatkan individu baru yang mewarisi sifat dari kedua induknya. (Obitko, 1998) Crossover merupakan operator dasar pada algoritma genetik. Tipe dan bentuknya tergantung pada pengkodean dan jenis permasalahannya.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
20
Ada beberapa jenis crossover yang didefinisikan oleh Obitko (1998), diantaranya: a. Partial-Mapped Crossover (PMX). Memilih dua titik potong secara random. Substring antara kedua titik potong disebut mapping sections. Mapping sections diantara kedua induk ditukar kemudian ditentukan hubungan pemetaan antara kedua mapping sections untuk menghasilkan 2 anak. b. Order Crossover (OX). Memilih substring dari salah satu induk secara random kemudian membentuk calon anak dari substring dengan posisi yang sama. Gen yang telah ada pada induk kedua dihapus, sisanya adalah barisan gen yang belum ada pada calon anak. Kemudian barisan tersebut ditempatkan pada posisi calon anak yang masih kosong berurutan dari kiri ke kanan hingga terbentuk 1 anak. c. Position-Based Crossover. Memilih beberapa posisi dari salah satu induk secara random kemudian membentuk calon anak dari gen-gen pada posisi yang telah terpilih dengan posisi yang sama. Gen yang telah ada pada induk kedua dihapus, sisanya adalah barisan gen yang belum ada pada calon anak. Kemudian barisan tersebut ditempatkan pada posisi calon anak yang masih kosong berurutan dari kiri ke kanan hingga terbentuk 1 anak.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
21
Pada proses crossover terdapat rasio untuk mengontrol jumlah harapan dari individu yang mengalami crossover. Jumlah harapannya dihitung dengan cara p c x pop_size. Definisi 2.17 Laju crossover ( p c ) adalah rasio banyaknya keturunan yang dihasilkan dari crossover pada tiap-tiap generasi terhadap ukuran populasinya. (Gen dan Cheng, 1997) Definisi 2.18 Mutasi merupakan proses perubahan sebagian sifat individu secara random yang menghasilkan struktur genetik baru. (Obitko, 1998) Ada beberapa jenis mutasi yang didefinisikan Obitko (1998), diantaranya: a. Mutasi Inversi (inversion Mutation) Memilih dua posisi dalam individu secara acak dan kemudian membalik untaian diantara dua posisi itu. b. Mutasi Sisipan (Insertion Mutation) Memilih gen secara acak dan menyisipkannya di posisi acak. c. Mutasi perpindahan (Displacement Mutation) Memilih sebuah subtour secara acak dan memasukkannya pada posisi lain secara acak. d. Reciprocal Exchange Mutation Memilih dua posisi gen secara acak kemudian menukar gen pada kedua posisi tersebut.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
22
Pada proses mutasi terdapat rasio untuk mengontrol jumlah harapan dari individu yang mengalami mutasi. Jumlah harapannya dihitung dengan cara
p m x pop_size. Definisi 2.19 Laju mutasi ( p m ) adalah prosentase dari jumlah individu dalam populasi yang dimutasi. (Gen dan Cheng, 1997)
Secara umum langkah-langkah dalam algoritma genetika adalah sebagai berikut: 1. [Mulai] Membangkitkan populasi secara random sebanyak n individu (solusi fisibel dari permasalahan) 2. [Fitness] Menilai keandalan setiap individu dalam populasi. 3. [Populasi
baru]
Membentuk
populasi
baru
lewat
pengulangan
pengoperasian operator genetik berikut sampai populasi baru lengkap. a. [Seleksi]
Memilih
induk
dari
populasi
sesuai
dengan
nilai
keandalannya (keandalan yang lebih baik, lebih berpeluang untuk terpilih). b. [Crossover] Dengan suatu laju crossover, crossover induk untuk membentuk anak (individu baru). Jika tidak ada crossover yang dilaksanakan, anak merupakan copian yang sama dengan induknya. c. [Mutasi] Menggunakan suatu probabilitas, mutasi induk pada masingmasing sifat (lokus = posisi dalam individu).
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
23
4. [Mengganti]
Menggunakan
populasi
yang
baru
dibentuk
untuk
menjalankan algoritma lebih lanjut. 5. [Menguji] Jika sudah mencapai n iterasi atau optimal, berhenti dan diperoleh solusi terbaik dari populasi ini. Jika tidak maka kembali ke langkah 2 sampai diperoleh solusi terbaik dari populasi ini. (Obitko, 1998)
2.5 Hybrid ACO dan GA Hybrid menurut bahasa berarti campuran atau gabungan, jadi hybrid algorithm merupakan suatu algoritma yang digunakan untuk menyelesaikan suatu permasalahan yang menggunakan dua algoritma berbeda atau lebih. Hybrid ACO dan GA artinya menggabungkan antara algoritma ACO dan algoritma GA menjadi satu algoritma untuk menyelesaikan suatu permasalahan. (Dechter, 2011)
2.6. Pemrograman Java Java merupakan bahasa pemrograman yang didasari oleh OOP (Oriented Object Programing) yaitu merupakan teknik membuat suatu program berdasarkan objek. Java memiliki JVM (Java Virtual Machine) yaitu lingkungan tempat eksekusi program java berlangsung dimana setiap objek saling berinteraksi satu dengan yang lainnya. Virtual machine inilah yang menyebabkan java mempunyai kemampuan penanganan memori yang lebih baik, keamanan yang lebih tinggi serta portabilitas yang besar. Namun demikian java tidak terikat oleh lisensi
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
24
karena java bersifat open-source sehingga java merupaka bahasa pemrograman portable yang bisa digunakan secara muti-platform (Sistem Operasi) dan multiarsitektur dimana arsitektur java terbagi menjadi tiga bagian yaitu: 1. Java 2 Enterprise Edition ( J2EE ) untuk aplikasi berbasis web, aplikasi sistem tersebar dengan beraneka ragam klien dengan kompleksitas yang tinggi. 2. Java 2 Standard Edition ( J2SE ) untuk aplikasi standar berbasis dekstop. 3. Java 2 Mobile Edition (J2ME) untuk aplikasi mobile seperti handphone. ( Utama, 2002 ) Hal yang paling penting dalam pemrograman java adalah memahami karakter dari pola pemrograman berbasis objek yang mencakup konsep utama pada Object Oriented Programing ( OOP ) yaitu : 1. Class Dalam java, kelas didefinisikan menggunakan kata kunci class . 2. Method Terdapat dua buah method (metode) yaitu fungsi dan prosedur. Fungsi merupakan metode yang memiliki nilai balik yang menggunakan kata kunci tipe_data <spasi> nama_fungsi() . Sebaliknya prosedur merupakan metode yang tidak memiliki nilai balik yang menggunakan kata kunci void <spasi> nama_fungsi().
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
25
3. Inheritance ( pewarisan ) Pewarisan adalah membentuk subkelas baru ( kelas anak ) dari kelas utama atau kelas induk sebelumnya yang menggunakan kata kunci class <spasi> nama_kelas_anak <spasi> extends <spasi> nama_kelas_induk. 4. Polimorfisme Polimorfisme adalah pembentukan kelas baru yang bersifat abstrak karena adanya keragaman fungsi dari objek – objek yang identik. Oleh karena itu polimorfisme membentuk kelas abstrak yang menggunakan kata kunci abstract. 5. Interface Interface hampir menyerupai kelas abstrak, akan tetapi interface merupakan kelas abstrak sepenuhnya yang bertujuan untuk menerapkan pewarisan jamak. Interface menggunakan kata kunci interface. ( Huda, 2010 )
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
BAB III METODE PENELITIAN
Adapun langkah-langkah penyelesaian masalah untuk QAP dengan menggunakan hybrid ACO dan GA adalah sebagai berikut : 1. Studi pustaka Quadratic Assignment Problem, Ant Colony Optimization, Genetic Algorithm dan bahasa pemrograman java. 2. Mengkodekan QAP dengan pengkodean permutasi. 3. Prosedur hybrid ACO dan GA pada QAP : a. Pengisian parameter, diantaranya : Menentukan α , ρ , β, matrik Pheromone, jumlah semut, jumlah lokasi, jumlah fasilitas, konstanta Q, pop_size, nilai probabilitas crossover (Pc) , nilai probabilitas mutasi (Pm) dan max_iterasi. b. Inisialisasi Menentukan matrik biaya dengan cara mengalikan jumlah matrik arus dengan jumlah matrik jarak. c. Mengisi tabu list. Masing-masing semut memilih fasilitas untuk lokasi awal dan berikutnya secara acak dengan menggunakan persamaan (2.4) dan memasukkannya ke dalam tabu list, dengan syarat fasilitas dan lokasi tersebut belum masuk ke dalam tabu list. Jika fasilitas dan lokasi sudah masuk dalam tabu list maka fasilitas dan lokasi tersebut tidak boleh dipilih.
26 Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
27
d. Menghitung nilai fungsi tujuan. Setelah tabu list penuh atau dengan kata lain semua fasilitas dan lokasi sudah dikunjungi maka nilai fungsi tujuannya dihitung dengan menggunakan persamaan (2.1) untuk kemudian dibandingkan dan dicari nilai fungsi tujuan terkecil. Tabu list yang memiliki fungsi tujuan terkecil inilah sebagai solusi terbaik pada iterasi saat ini. e.
Menyimpan solusi terbaik Solusi-solusi terbaik dari perhitungan nilai fungsi tujuan setiap solusi pada langkah d akan disimpan dalam satu himpunan.
f. Memperbarui matrik pheromone. Matrik pheromone ini akan digunakan pada iterasi selanjutnya. Nilai yang lebih besar pada fasilitas i dan lokasi j pada matrik pheromone tersebut menandakan lebih banyak semut yang melalui garis tersebut. Matrik pheromone diperbarui dengan menggunakan persamaan (2.7). Nilai matrik pheromone yang baru akan digunakan pada iterasi selanjutnya. g. Mengulang proses. jika iterasi sama dengan Max_Iterasi maka iterasi berhenti dan mendapatkan solusi_awal QAP. Apabila belum tercapai, kosongkan tabu list selanjutnya kembali melakukan langkah c. h. Solusi awal Solusi awal merupakan himpunan dari solusi-solusi terbaik dari proses ACO, yang akan menjadi anggota populasi awal pada Algoritma Genetik.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
28
i. Populasi awal untuk proses GA. solusi_awal menjadi individu pada populasi awal. Membangkitkan individu untuk populasi awal sejumlah
pop_size dikurangi jumlah
solusi_awal. j. Menghitung nilai fungsi tujuan. Mengevaluasi populasi dengan cara menghitung nilai fungsi tujuan menggunakan persamaan (2.1) dari masing-masing individu. k. Menentukan seleksi induk. Seleksi yang akan digunakan adalah seleksi roda rollet. Tahapantahapan seleksi roda rollet adalah sebagai berikut : i.
Menghitung nilai fitness untuk setiap individu dengan menggunakan persamaan (2.9).
ii.
Menghitung total nilai fitness untuk populasi.
iii.
Menghitung probabilitas seleksi untuk setiap individu.
iv.
Menghitung probabilitas kumulatif untuk setiap individu.
v.
Melakukan generate bilangan acak dari interval [0,1].
vi.
Menentukan individu yang akan diproses untuk crossover dan mutasi.
l. Proses Crossover. Crossover yang digunakan dalam proposal skripsi ini adalah PartialMapped Crossover (PMX). Tahapan-tahapan dalam PMX adalah sebagai berikut :
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
29
i.
Tentukan dua posisi pada individu dengan aturan acak. Substring yang berada dalam dua posisi itu dinamakan daerah pemetaan.
ii.
Tukar dua substring antar induk untuk menghasilkan bakal anak.
iii.
Tentukan hubungan pemetaan diantara dua daerah pemetaan.
iv.
Tentukan individu
keturunan mengacu pada hubungan
pemetaan. m. Proses mutasi. Mutasi yang digunakan dalam proposal skripsi ini adalah Insertion Mutation. Tahapan-tahapan dalam Insertion Mutation adalah sebagai berikut : i.
Memilih dua posisi titik gen secara acak pada induk, namakan posisi_1 dan posisi_2.
ii.
Menentukan anak dengan cara menyisipkan gen pada posisi_2 ke posisi_1.
iii.
Sedangkan untuk gen yang lainnya akan bergeser berurutan sesuai posisinya dan hasilkanya akan menjadi anak.
n. Evaluasi anak. Mengevaluasi individu anak hasil dari proses crossover dan mutasi dengan menghitung nilai fungsi tujuannya menggunakan persamaan (2.1).
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
30
o. Populasi baru. Menyeleksi dalam pembentukan populasi baru dengan tahapantahapan sebagai berikut : i.
Mengumpulkan individu dari populasi awal, anak hasil crossover dan anak hasil mutasi.
ii.
Semua individu tersebut diurutkan berdasarkan nilai fungsi tujuannya.
iii.
Diambil individu-individu terbaik sebanyak pop_size.
p. Mengulang proses. jika iterasi sama dengan Max_Iterasi maka iterasi berhenti dan mendapatkan solusi_akhir QAP. Apabila belum tercapai, kembali melakukan langkah i. 4.
Membuat program dari algoritma hybrid ACO dan GA pada QAP dengan menggunakan bahasa pemrograman java.
5. Mengimplementasikan pada suatu contoh kasus QAP. Alur algoritma Hybrid ACO dan GA, disajikan dalam Gambar 3.1.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
31 mulai
Pengisian Parameter Inisialisasi Kosongkan Tabu List Pengisian Tabu List Menghitung Nilai Fungsi Tujuan
No
Menyimpan solusi terbaik Update Pheremone
max_iterasi? yes Solusi Awal Solusi awal dan Generate populasi Seleksi Mutasi
Crossover Anak
No Evaluasi Anak Populasi baru
Iterasi = max_iterasi yes Selesai Gambar 3.1 Skema flowchart hybrid ACO dan GA
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
BAB IV PEMBAHASAN Pada Bab ini diberikan beberapa penjelasan mengenai penerapan Hybrid Ant Colony Optimization dan Genetic Algorithm pada Quadratic Assignment Problem (QAP). 4.1 Masalah Penugasan Kuadratik Persoalan penugasan merupakan masalah penempatan fasilitas pada suatu lokasi tertentu sehingga : 1. Fasilitas-fasilitas dengan spesifikasi tertentu akan terkelompok dalam suatu stasiun kerja. 2. Penempatan fasilitas pada suatu lokasi tertentu dapat meminimalkan jarak tempuh
total
perpindahan
bahan
antar
fasilitas,
sehingga
akan
meminimalkan biaya operasional produksi. Berdasarkan pada (Gen dan Cheng, 1997) secara umum model penugasan kuadratik dapat dinyatakan pada persamaan (2.1) dengan kendala fungsional yang harus dipenuhi pada persamaan (2.2). 4.2 Prosedur Hybrid Algorithm Ant Colony Optimization dan Genetic Algorithm Penyelesaian QAP dengan menggunakan Hybrid (penggabungan) antara Algorithm Ant Colony Optimization dan Genetic Algorithm, akan diuraikan sebagai berikut ini. Proses di awali dengan menyelesaian QAP dengan Ant Colony
32 Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
33
Optimization. Hasil terbaik (solusi awal) akan menjadi individu awal bagi proses selanjutnya dengan Genetic Algorithm. Pada GA dibangkitkan individu untuk populasi awal sejumlah pop_size dikurangi dengan jumlah solusi awal. Prosedur Hybrid ACO dan GA dijelaskan dalam Gambar 4.1. Procedure for Hybrid ACO and GA begin parameter setting ( ); inisialisasi ( ); while (not max iteration) do begin pengisian tabu_list ( ); hitung fungsi tujuan ( ); solusi awal ( ); perbaruhi matriks pheromone ( ); end while (not max iteration) do begin generate pop_size ( ); seleksi pop_size ( ); genetic operation ( ); evaluasi anak ( ); pop_baru ( ); end end Gambar 4.1 Prosedur Hybrid ACO dan GA
Untuk mempermudah ilustrasi Hybrid Ant Colony Optization dan Genetic Algorithm maka prosedur diatas diuraikan pada Gambar 3.1. Proses Hybrid ACO dan GA ini, akan berhenti setelah mencapai n iterasi. Dalam proses GA diharapkan dapat membangkitkan individu-individu terbaik dari hasil crossover dan mutasi dengan induk dari solusi terbaik yang dihasil pada proses ACO. Setelah proses keseluruhan dari Hybrid ACO dan GA di ketahui, maka langkah selanjutnya adalah pengisian parameter.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
34
4.2.1 Pengisian Parameter Prosedur pengisian parameter disajikan dalam Gambar 4.2. Beberapa istilah yang dipakai, jml_ant adalah banyaknya semut, alpha adalah tetapan pengendali intensitas Pheromone, betha adalah tetapan pengendali visibilitas, phero_awal adalah nilai awal dari matriks pheromone,
rho adalah koefisien
penguapan intensitas pheromone, Q adalah konstanta ketetapan, jml_lok adalah jumlah lokasi, jml_fas adalah jumlah fasilitas, pop_size adalah ukuran populasi, Pc adalah nilai probabilitas crossover, Pm adalah nilai probabilitas mutasi, max_iterasi adalah iterasi maksimum yang akan digunakan untuk membatasi banyaknya siklus dalam pencarian solusi optimal. Procedure for parameter setting begin Banyak semut: jml_ant; Nilai alpha : alpha; Nilai Betha : betha; Nilai pheromone awal : phero_awal; Koefisien penguapan : rho; Konstanta Q : Q; Jumlah lokasi : jml_lok; Jumlah fasilitas : jml_fas; Ukuran Populasi : Pop_size;
probabilitas crossover : Pc; probabilitas mutasi : Pm ;
Banyak Iterasi : max_iterasi; end
Gambar 4.2 Prosedur pengisian parameter
Setelah proses pengisian parameter sudah dilakukan, maka proses selanjutnya untuk menyelesaikan QAP ini adalah inisialisasi.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
35
4.2.2 Inisialisasi Pada prosedur ini akan ditentukan nilai dari eij ditunjukkan pada Gambar 4.3.
adalah elemen baris ke-i dan kolom ke-j dari matriks biaya yang
dibutuhkan untuk menugaskan fasilitas i pada lokasi j. dan
diperoleh dari perkalian
, dengan
adalah jumlahan elemen
baris ke-i dari matriks fasilitas dan
adalah jumlahan elemen kolom
ke-j dari matriks lokasi. Sedangkan fasilitas i dan fasilitas k,
adalah matriks arus antara
adalah matriks jarak antara lokasi j dan lokasi l.
Procedure for initialization begin for i 0 to jml_fas - 1 begin 0; for k 0 to jml_fas - 1 begin = end end for j 0 to jml_lok - 1 begin 0; for l 0 to jml_lok - 1 begin = end end for i 0 to jml_fas - 1 begin for j 0 to jml_lok - 1 begin = end end end
+
+
*
;
;
;
Gambar 4.3 Prosedur inisialisasi
Setelah proses inisialisasi sudah dilakukan, maka proses selanjutnya untuk menyelesaikan QAP ini adalah pengisian tabu list.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
36
4.2.3 Pengisian tabu list Pada prosedur ini masing-masing semut memilih fasilitas untuk lokasi awal dan berikutnya secara acak dengan menggunakan persamaan (2.3) dan memasukkannya ke dalam tabu list. Prosedur untuk mengisi tabu list ditunjukkan pada Gambar 4.4. Procedure for pengisian tabu_list begin for k 0 to jml_semut - 1 begin calculate probabilitas ( ); calculate pilih_fasilitas ( ); end end Gambar 4.4 Prosedur pengisian tabu list
Untuk mempermudah ilustrasi pengisian tabu list maka prosedur diatas dapat dinyatakan dalam flowchart seperti pada Gambar 4.5 :
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
37
Mulai Cek Node
Hitung Probabilitas
Tidak
i iterasi ? Ya Generate Random Tidak
Isi tabu list untuk pilih fasilitas Tidak i iterasi ? Ya k iterasi ? Ya Selesai
Gambar 4.5 Flowchart pengisian tabu list
Pada Gambar 4.4. tercantum sebuah perintah untuk menghitung probabilitas. prob_ant adalah probabilitas semut untuk menugaskan fasilitas i pada lokasi j. Prosedur untuk menghitung probabilitas disajikan pada Gambar 4.6. Procedure for calculate probabilitas begin for k 0 to jml_ant – 1 for j 0 to jml_lok - 1 begin
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
38
penyebut hitung_penyebut(k, j); for i 0 to jml_fas-1 begin if (cek_node (k, i) == 0) begin ((( pow ( _( pow ((1/
, alpha) )*_ ), betha) )) / penyebut);
end else begin 0; end end end end Gambar 4.6 Prosedur menghitung probabilitas
Pada Gambar 4.6. tercantum sebuah fungsi hitung_penyebut. sum_allowed adalah
t
jallowed _ node
ij
1 yang disajikan pada Gambar 4.7. eij
Procedure for hitung_penyebut begin sum_allowed 0; for i 0 to jml_fas - 1 begin if (cek_node(k, i) == 0) begin for j 0 to jml_lok – 1 begin sum_allowed+=(pow( end end end return (sum_allowed); end
,alpha))*(pow((1/
),betha));
Gambar 4.7 Prosedur hitung penyebut
Prosedur untuk menghitung cek_node disajikan pada Gambar 4.8, dengan nilai 0 untuk fasilitas ke-i yang masih belum ditugaskan pada lokasi j dan nilai 1 untuk fasilitas ke-i yang sudah ditugaskan pada lokasi j.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
39
Procedure for cek_node begin ada 0; for j 0 to jml_lok - 1 begin if (i == begin ada 1; end end return (ada); end
)
Gambar 4.8 Prosedur cek node
Pada Gambar 4.4. tercantum sebuah perintah untuk memilih fasilitas. perm adalah nilai probabilitas semut ke-k pada fasilitas ke-i, dan randm adalah bilangan acak antara 0 dan 1. Prosedur untuk menghitung probabilitas disajikan pada Gambar 4.9. Procedure for pilih_fasilitas begin i 0; perm ; acak random(0,1); while ((acak > perm) && (i < jml_fas - 1)) begin i++; perm perm + ; end i; end Gambar 4.9 Prosedur memilih fasilitas
4.2.4 Menghitung Nilai Fungsi Tujuan Masing-masing semut dihitung nilai fungsi tujuannya dengan menghitung biaya yang berhubungan dengan penugasan fasilitas pada lokasi. Pasangan fasilitas dan lokasi pada tabu list yang didapatkan tidak dapat langsung dimasukkan ke dalam fungsi tujuan, tetapi pasangan fasilitas dan lokasi pada tabu
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
40
list tersebut akan diubah kedalam bentuk matriks penempatan (x). matriks penempatan (x) merupakan matrik yang berelemen biner (0 dan 1), dimana jika bernilai 1 maka fasilitas i ditempatkan pada lokasi j dan 0 jika tidak ditempatkan. Prosedur untuk menghitung fungsi tujuan tersaji pada Gambar 4.10, dengan digunakan untuk menampung nilai tmpf, tmpf diperoleh dari menghitung nilai fungsi tujuan dari masing-masing semut dengan rumus n
n
n
n
f i 1 j 1 k 1 l 1
ik
d jl xij xkl .
Procedure for fungsi tujuan begin for ant 0 to jml_ant - 1 begin calculate isi_x(ant); tmpf 0; 0; for i 0 to jml_fas - 1 begin for j 0 to jml_lok - 1 begin for k 0 to jml_fas - 1 begin for l 0 to jml_lok - 1 begin tmpf += end end end end tmpf; end end
*
*
*
;
Gambar 4.10 Prosedur fungsi tujuan
Pada Gambar 4.10. tercantum sebuah perintah untuk menghitung isi_x. Prosedur untuk menghitung isi_x disajikan pada Gambar 4.11, dengan elemen matriks penempatan (x), bernilai 1 jika
adalah
sama dengan
fasilitas ke-i.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
41
Procedure for calculate isi_x begin for j 0 to jml_lok - 1 begin for i 0 to jml_fas - 1 begin if ( == i) 1; else 0; end end end Gambar 4.11 Prosedur isi x
4.2.5 Menyimpan solusi terbaik
Hasil perhitungan nilai fungsi tujuan dan nilai
akan dibandingkan
terbaik artinya solusi_awal yang paling kecil akan
disimpan untuk dijadikan populasi awal pada proses genetic algorithm. Prosedur penyimpanan solusi terbaik disajikan pada Gambar 4.12. Procedure for save the solution Begin Min = for ant 0 to jml_ant – 1 if < Min Min = ; end for ant 0 to jml_ant – 1 if = Min update AR[ant] = ant ; end end Gambar 4.12 Prosedur penyimpanan solusi
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
42
4.2.6 Memperbarui Matriks Pheromone Setelah tabu_list penuh kemudian matriks pheromone diperbarui dengan m
ij (t 1) . ij (t ) ijk , dengan delta(i,j) adalah ijk . Prosedur memperbarui k 1
matriks pheromone disajikan pada Gambar 4.13.
Procedure for Update Pheromone begin for i 0 to jml_fas - 1 begin for j 0 to jml_lok - 1 begin =rho* end end end
+delta(i,j);
Gambar 4.13 Prosedur update pheromone
Pada Gambar 4.13. tercantum delta(i,j). Prosedur untuk menghitung delta(i,j) disajikan pada Gambar 4.14. Procedure for calculate delta begin tmpf 0; for k 0 to jml_ant-1 begin if ( == i) begin tmpf += Q/ ; end end return(tmpf); end Gambar 4.14 Prosedur menghitung delta
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
43
4.2.7 Generate pop_size Pada prosedur ini akan dibangkitkan sejumlah individu secara random didaerah solusi yang fisibel. Sejumlah individu yang dibangkitkan dari ruang penyelesaian akan membentuk sebuah populasi, dimana jumlah individu yang dibangkitkan dalam populasi awal adalah pop_size dikurangi dengan jumlah solusi_awal. Adapun prosedur untuk men-generate pop_size disajikan dalam Gambar 4.15. Procedure for Generate pop_size begin m = pop_size - solusi_awal; a 0; while (a < m) do begin generate individu dengan permutasi; a a + 1; end end Gambar 4.15 Prosedur generate pop_size
Pada Gambar 4.15 tercantum generate individu dengan menggunakan permutasi. Prosedur men-generate individu dengan menggunakan permutasi disajikan dalam Gambar 4.16. Misalkan pop_size adalah banyak individu dalam populasi dan tempi merupakan posisi gen dalam individu. Posisi adalah merandom dari 0, 1, ..., pop_size – 1. Procedure for Generate individu dengan menggunakan permutasi begin for b 0 to pop_size - 1 begin b; end for b 0 to pop_size - 1 begin posisi random(0, pop_size - 1);
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
44
; for c posisi to pop_size – 1 begin ; end end return individu; end Gambar 4.16 Prosedur men-generate individu dengan menggunakan permutasi
4.2.8 Menghitung Nilai Fungsi Tujuan Individu dalam populasi sudah terbentuk, dilakukan prosedur perhitungan nilai fungsi tujuan dari setiap individu, prosedurnya seperti pada bagian 4.2.4. 4.2.9 Seleksi Seleksi merupakan suatu proses untuk menentukan individu yang akan dijadikan induk crossover ataupun induk mutasi. Pada kasus QAP ini, seleksi yang digunakan adalah seleksi rollet whell (roda rollet). Pada seleksi ini diharapkan individu dengan nilai fitness terbaik dapat menjadi induk crossover dan mutasi. Seleksi ini didasarkan pada nilai fitness masing-masing individu. Parameter yang penting dalam seleksi ini adalah penentuan Pc dan Pm. Parameter Pc ini digunakan untuk menentukan probabilitas individu yang akan di crossover. Penentuan Pc untuk permasalahan QAP ini, direkomendasikan sebesar 0,6 (Obitko, 1998). Sedangkan Pm digunakan untuk menentukan probabilitas individu yang akan di mutasi. Penentuan Pm untuk permasalahan QAP ini, direkomendasikan sebesar 0,1 (Gen dan Cheng, 1997).
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
45
Prosedur untuk seleksi disajikan pada Gambar 4.17 dengan individu ke – k, sumfx adalah jumlahan dari fungsi tujuan, fitness individu seleksi dan
, F adalah jumlahan dari nilai fitness,
adalah
adalah nilai adalah probabilitas
adalah probabilitas komulatif.
Procedure for Selection begin sumfx 0; for k 1 to pop_size do sumfx sumfx f (v k ) ; end for k 1 to pop_ size do
fithost k sumfx f (v k ) ;
end
F 0;
for
k 1 to pop_ size do
F F fithost k ;
end for k
1 to pop_ size do pk
end for k
fithost k ; F
1 to pop_ size do k
qk p j ; j 1
end for k end for k
1 to pop_ size do
rk
random number [0,1];
1 to pop_ size do
if rk q1 then pilih
v1 ;
end if q k 1 rk q k then pilih end
vk ;
end end
Gambar 4.17 Prosedur seleksi
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
46
4.2.10 Seleksi Crossover Generate r p dengan r p merupakan bilangan acak dari interval [0,1] dan
p 1, 2, , pop _ size . Untuk memilih induk-induk yang akan dicrossover harus memenuhi ketentuan sebagai berikut : Jika rp pc , maka individu ke-p tersebut akan terpilih menjadi induk yang akan mengalami crossover. Prosedur untuk seleksi crossover disajikan dalam Gambar 4.18. Misal r p adalah nilai random ke-p, p c adalah probabilitas crossover, dan v p adalah individu ke-p. Procedure selection crossover begin for p 1 to pop_ size do
rp random number [0,1]; end for
p 1 to pop_ size do if rp pc then pilih v p sebagai induk crossover;
end end Gambar 4.18 Prosedur seleksi crossover
4.2.10.1 Crossover Pada proses seleksi crossover telah diperoleh sejumlah induk crossover. Jika dari seleksi crossover dihasilkan induk-induk crossover yang jumlahnya gasal, maka dibuang satu induk sehingga jumlahan induk crossover menjadi genap. Selanjutnya induk-induk tersebut akan mengalami crossover dengan cara mengambil dua induk yang akan dicrossover untuk menghasilkan dua anak.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
47
Proses ini dilakukan sampai semua induk crossover mengalami proses crossover. Anak-anak hasil crossover diharapkan lebih baik daripada induk-induknya. Crossover yang akan digunakan adalah PMX, dengan Langkah-langkahnya sebagai berikut : Langkah 1: Memilih dua individu hasil seleksi crossover untuk dijadikan induk crossover yang dinamakan induk_1 dan induk_2. Langkah 2: Memilih dua posisi secara acak, namakan pos_1 dan pos_2. Langkah 3: Menentukan subuntaian. Dari pos_1 sampai pos_2 dianggap sebagai subuntaian yang akan dijadikan bagian yang dipetakan. Subuntaian pada induk_1 dan induk_2, namakan sub_1 dan sub_2. Langkah 4: Mengkopi sub_1 ke anak awal_2 dan sub_2 ke anak awal_1 bersesuaian dengan posisinya. Sisanya pada induk_1 yang bukan sub_1 dikopi ke anak awal_1 dan sisanya pada induk_2 yang bukan sub_2 dikopi ke anak awal_2 bersesuaian dengan posisinya. Langkah 5: Menentukan pemetaan antara sub_2 dengan sub_1. Langkah 6: Menentukan anak dengan pemetaan dari langkah ke-5. Yaitu dengan cara, dicari gen yang bukan sub_2 pada anak awal_1 atau sub_1 pada anak awal_2, tapi gen tersebut mempunyai kesamaan dengan pemetaan, maka gen tersebut diganti dengan gen pemetaannya. Langkah ini dilakukan berulang-ulang sampai tidak ada gen yang
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
48
rangkap pada satu individu, dan terakhir akan diperoleh dua anak yaitu anak 1 dan anak 2. Langkah-langkah PMX ini dapat dibentuk dalam bentuk prosedur, adapun prosedur untuk PMX disajikan dalam Gambar 4.19. Procedure crossover PMX begin
i 1; ( jumlah induk crossover/2)) do
for ( i
Ambil dua individu sebagai induk crossover dari seleksi crossover; Pilih dua posisi sepanjang urutan secara acak; Tentukan sub-urutan dari dua posisi yang disebut pilihan pemetaan; Tukar dua sub-urutan antara induk untuk membentuk sub-anak; Tentukan hubungan pemetaan antara dua pilihan pemetaan; Nyatakan anak dengan hubungan pemetaan; i i 1;
end end Gambar 4.19 Prosedur crossover PMX
4.2.11 Seleksi Mutasi Generate rq yang merupakan bilangan acak dari interval [0,1] dan
q 1, 2, , pop _ size . Untuk memilih induk-induk yang akan dimutasi harus memenuhi ketentuan sebagai berikut : Jika rq p m , maka individu ke-q tersebut akan terpilih menjadi induk yang akan mengalami mutasi. Prosedur untuk seleksi mutasi disajikan dalam Gambar 4.20. Misal rq adalah random ke-q, p m adalah probabilitas mutasi, dan v q adalah individu ke-q.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
49
Procedure selection mutation begin for q 1 to pop_ size do
rq random number [0,1]; end for q 1 to pop_ size do if
r
q
pm if pilih v q
sebagai induk mutasi;
Selesai end Gambar 4.20 Prosedur seleksi mutasi
4.2.11.1 Mutasi Jika pada proses seleksi mutasi tidak diperoleh induk yang akan dimutasi, maka proses mutasi tidak dilakukan. Dan sebaliknya jika diperoleh induk mutasi, maka induk tersebut akan mengalami proses mutasi. Anak hasil mutasi tersebut akan dievaluasi, diharapkan anaknya lebih baik daripada induknya. Mutasi yang akan digunakan adalah Insertion Mutation, langkah-langkahnya adalah sebagai berikut : i.
Memilih dua posisi titik gen secara acak pada induk, namakan posisi_1 dan posisi_2.
ii.
Menentukan anak dengan cara menyisipkan gen pada posisi_2 ke posisi_1.
iii.
Sedangkan untuk gen yang lainnya akan bergeser berurutan sesuai posisinya.
Langkah-langkah Insertion Mutation ini dapat dibentuk dalam bentuk prosedur, adapun prosedur untuk Insertion Mutation disajikan dalam Gambar 4.21.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
50
Procedure insertion mutation Begin posisi_1 random; posisi_2 random; if (posisi_1 = posisi_2) then do posisi_2 random; ` while (posisi_1 = posisi_2) if (posisi_1 < posisi_2) then begin angka = posisi_1 – posisi_2; if i 0 to pop_size do begin if (i < posisi_1 or i > posisi_2) then else if (i = posisi_1) then else ; end end else begin angka posisi_1 – posisi_2; for i 0 to pop_size do begin if (i < posisi_2 or i > posisi_1) then else if (i = posisi_1) then else ; end end end
; ;
; ;
Gambar 4.21 Prosedur insertion mutation
4.2.12 Evaluasi Anak Anak crossover dan mutasi dihitung nilai fungsi tujuannya, prosedurnya seperti pada 4.2.4. 4.2.13 Populasi Baru Untuk membentuk populasi baru, langkah awalnya mengumpulkan populasi awal, anak hasil crossover dan anak hasil mutasi. Selanjutnya semua individu tersebut akan diurutkan sesuai dengan bobotnya. Individu dipilih yang
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
51
terbaik sebanyak pop_size untuk dibentuk menjadi populasi baru. Sedangkan individu yang tidak terpilih akan dikeluarkan dari populasi. Prosedur untuk populasi baru disajikan dalam Gambar 4.22. Procedure new population begin Ambil semua individu dari populasi awal, anak crossover dan anak mutasi; Urutkan indivu berdasarkan nilai fungsi tujuan; Ambil individu terbaik sebanyak pop_size; end Gambar 4.22 Prosedur populasi baru
4.3 Data Terdapat 2 data yang akan digunakan yaitu : 1.
Data aliran bahan antar fasilitas yang diambil dari Dorigo, dkk. (1996). Pada data ini terdapat 4 fasilitas dengan 4 lokasi, untuk selengkapnya dapat dilihat pada (Lampiran 1).
2.
Data aliran bahan antar fasilitas dengan 12, 14, 16, 18 dan 20 fasilitas dan lokasi, data ini diambil dari http://www.seas.upenn.edu/qaplib/inst.html , penelitihan dari Hadley, dkk (1992), untuk data selengkapnya dapat dilihat pada (Lampiran 1).
4.4 Contoh Kasus Quadratic Assignment Problem dengan Menggunakan Data 4 fasilitas dan 4 lokasi yang Diselesaikan Secara Manual Dari data aliran bahan antar fasilitas yang terdapat pada sub bab 4.4 maka dapat dibentuk matriks arus dan matriks jarak.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
52
Langkah – langkah penyelesainnya adalah sebagai berikut : 4.4.1 Pengisian Parameter yang Dibutuhkan Pada langkah inisialisasi parameter, dipilih jml_ant = 5, alpha = 1, betha = 1, phero_awal = 0,1, rho = 0,9, Q = 100, jml_lok = 4 , jml_fas = 4, pop_size = 5, Pc = 0,6, Pm = 0,1, max_iterasi = 1. Karena phero_awal = 0,1 sehingga terbentuk matriks pheromone berukuran i x j dengan i = j , yang menggambarkan banyaknya pheromone antar fasilitas i dan lokasi j.
Matriks pheromone = [
]
Dari matriks arus (flow) dan matriks jarak, maka dapat diperoleh matriks baru yaitu matriks biaya. Matriks biaya digunakan untuk menentukan seberapa besar biaya memilih fasilitas i ditempatkan pada lokasi j.
Matriks arus (F) = [
]
Jumlah dari matriks arus ke-i (fi) = [
Matriks jarak (D) = [
Skripsi
]
]
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
53
Jumlah dari matriks jarak ke-j (dj) = [
]
Dari pekalian antara fi dan dj, maka dapat diperoleh matrik biaya.
Matriks biaya (eij) =[
]x
=[
]
4.4.2 Pengisian tabu list Masing-masing semut memilih fasilitas untuk lokasi awal dan berikutnya secara acak dengan menggunakan persamaan (2.1) dan memasukkannya ke dalam tabu list.
Pada j = 0 Untuk semut ke-0. Probabilitas memilih fasilitas 0 ke lokasi 0 :
t
p
k ij
ij
t
1 eij
t
jallowed _ node
ij
1 eij
00
p
0 00
00
Skripsi
1 e00
1 1 1 1 10 20 30 e00 e10 e20 e30
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
54
1 720
0,11 0 p00
0 p00
1
1
1
1
1
1
1
1 1 1 1 1 1 1 0,1 0,1 0,1 1680 1440 1200 720
0,11
0,000139 0,396 0,0003512
Probabilitas memilih fasilitas 1 ke lokasi 0 :
1 1200
0,11 0 p10
0 p10
1
1
1
1 1 1 1 1 1 1 0,1 0,1 0,1 1680 1440 1200 720
0,11
0,0000833 0,237 0,0003512
Probabilitas memilih fasilitas 2 ke lokasi 0 : 0 p 20
0,0000694 0,198 0,0003512
Probabilitas memilih fasilitas 3 ke lokasi 0 : 0 p30
0,0000595 0,169 0,0003512
Karena pada j = 0 semua semut belum memilih fasilitas pada lokasi awal, sehingga nilai probabilitas semua semut untuk memilih fasilitas pada lokasi awal adalah sama. Hasil selengkapnya ditunjukkan pada Tabel 4.1. Tabel 4.1 Probabilitas pada j = 0
Ant 0 1 2 3
Probabilitas memilih fasilitas pada lokasi 0
0 0,396 0,396 0,396 0,396
1 0,237 0,237 0,237 0,237
2 0,198 0,198 0,198 0,198
3 0,169 0,169 0,169 0,169
Selanjutnya menghitung probabilitas komulatif dari probabilitas relatif pada semut ke-0, yang disajikan pada Tabel 4.2.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
55
Tabel 4.2 Probabilitas komulatif semut ke-0 pada j = 0
fasilitas Probabilitas relatif Probabilitas komulatif 0 0,396 0,396 1 0,237 0,633 2 0,198 0,831 3 0,169 1 Untuk menentukan fasilitas mana yang dipilih, maka diambil sebarang bilangan acak (0,1) yang akan dibandingkan dengan probabilitas kumulatif pada masing – masing semut. Bilangan ajak disajikan pada Tabel 4.3. Tabel 4.3 Bilangan acak pada j = 0
Ant 0 1 2 3 4
Bilangan acak (0,1) 0,357 0,127 0,698 0,988 0,531
Pada semut ke-0, bilangan acak yang terambil 0,357 sehingga semut ke-0 memilih fasilitas 0, karena nilai 0,357 mendekati nilai probabilitas komulatif pada fasiliats 0 sebesar 0,357. Dengan cara yang sama untuk semua semut akan diperoleh tabu list awal, seperti ditunjukkan pada Tabel 4.4. Tabel 4.4 Tabu list pada j = 0
Ant 0 1 2 3 4
Lokasi 0 Fasilitas 0 0 2 3 1
Pada j = 1 Karena semua semut sudah memilih fasilitas pada lokasi awal, maka nilai
probabilitas fasilitas pada lokasi yang sudah terpilih bernilai 0. Sehingga dengan
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
56
cara yang sama dapat diperoleh nilai probabilitas untuk semua semut. Hasil selengkapnya ditunjukkan pada Tabel 4.5. Tabel 4.5 Probabilitas pada j = 1
prob. Memilih fasilitas pada lokasi 1 0 1 2 3 0,000 0,393 0,327 0,280 0,000 0,393 0,327 0,280 0,493 0,296 0,000 0,211 0,476 0,286 0,238 0,000 0,519 0,000 0,259 0,222
Ant 0 1 2 3 4
Untuk menentukan fasilitas mana yang dipilih, maka diambil sebarang bilangan acak (0,1) yang akan dibandingkan dengan probabilitas kumulatif pada masing – masing semut. Tabel 4.6 Bilangan acak pada j = 1
Ant 0 1 2 3 4
Bilangan acak (0,1) 0,826 0,050 0,619 0,732 0,638
Pada semut ke-0, bilangan acak yang terambil 0,826 sehingga semut ke-0 memilih fasilitas 3 untuk ditempatkan pada lokasi 1, karena nilai 0,826 mendekati nilai probabilitas komulatif pada fasilitas 3 sebesar 1. Dengan cara yang sama untuk semua semut akan diperoleh tabu list berikutnya, seperti ditunjukkan pada Tabel 4.7.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
57
Tabel 4.7 Tabu list pada j = 1
Lokasi 0 Lokasi 1 Fasilitas Fasilitas 3 0 1 0 1 2 1 3 2 1
Ant 0 1 2 3 4
Pada j = 2 Dengan cara yang sama dapat diperoleh nilai probabilitas untuk semua
semut. Hasil selengkapnya ditunjukkan pada Tabel 4.8. Tabel 4.8 Probabilitas pada j = 2
Ant 0 1 2 3 4
Probabilitas memilih fasilitas pada lokasi 2 0 1 2 3 0,000 0,546 0,454 0,000 0,000 0,000 0,538 0,462 0,700 0,000 0,000 0,300 0,667 0,000 0,333 0,000 0,700 0,000 0,000 0,300
Selanjutnya mengambil bilangan acak (0,1) Tabel 4.9 Bilangan acak pada j = 2
Ant 0 1 2 3 4
Bilangan acak (0,1) 0,723 0,015 0,352 0,673 0,537
Dengan cara yang sama untuk semua semut akan diperoleh tabu list seperti ditunjukkan pada Tabel 4.10.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
58
Tabel 4.10 Tabu list pada j = 2
Ant 0 1 2 3 4
Lokasi 0 Lokasi 1 Lokasi 2 Fasilitas Fasilitas Fasilitas 0 3 2 0 1 2 2 1 0 3 1 2 1 2 0
Dengan cara yang sama pada j = 3, maka diperoleh tabu list seperti ditunjukkan pada Tabel 4.11. Tabel 4.11 Tabu list pada j = 3
Ant 0 1 2 3 4
Lokasi 0 Lokasi 1 Lokasi 2 Lokasi 3 Fasilitas Fasilitas Fasilitas Fasilitas 0 3 2 1 0 1 2 3 2 1 0 3 3 1 2 0 1 2 0 3
4.4.3 Menghitung Nilai Fungsi Tujuan Masing-masing semut dihitung nilai fungsi tujuannya dengan menghitung biaya yang berhubungan dengan penugasan fasilitas pada lokasi. Pasangan fasilitas dan lokasi pada tabu list yang didapatkan tidak dapat langsung dimasukkan kedalam fungsi tujuan, tetapi pasangan fasilitas dan lokasi pada tabu list tersebut akan dirubah kedalam bentuk matriks penempatan (x) dengan ketentuan sebagai berikut : 1) Jika fasilitas i ditempatkan pada lokasi j, maka
= 1.
2) Jika fasilitas i tidak ditempatkan pada lokasi j, maka
= 0.
dengan i = 0,1,...,jumlah fasilitas - 1 dan j = 0,1,...,jumlah lokasi - 1.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
59
Pembentukan matriks penempatan berdasarkan tabu list disajikan pada contoh dengan mengambil salah satu tabu list pada semut ditabel 4.11. Misal diambil tabu list pada ant 0. Ant 0
(0,0)
(Fasilitas,Lokasi) (3,1) (2,2)
Misalkan pada fasilitas 0 terletak pada lokasi 0 maka 4 tidak terletak pada lokasi 1 maka
(1,3)
= 1, sedangkan fasilitas
= 0 untuk yang lain analog, sehingga
matriks penempatan yang terbentuk adalah
Matrik penempatan ant 0 = [
]
Dari matriks penempatan yang didapat dan rumus nilai nilai fungsi tujuan, n
n
n
n
z f ik d jl xij xkl , dengan
i,k = 0,1,…,jumlah fasilitas-1
i 1 j 1 k 1 l 1
j,l = 0,1,…,jumlah lokasi-1 Maka proses perhitungan nilai fungsi tujuan adalah sebagai berikut : z
= f 03d 01x00 x31 f 02d 02 x00 x22 f 01d 03 x00 x13
f 30d10 x31x00 f 32d12 x31x22 f 31d13 x31x13 f 20d 20 x22 x00 f 23d 21x22 x31 f 21d 23 x22 x13 f10d 30 x13 x00 f13d 31x13 x31 f12d 32 x13 x22 = (10 x 1 x 1 x 1) + (50 x 2 x 1 x 1) + (60 x 3 x 1 x 1) + (10 x 1 x 1 x 1) + (50 x 4 x 1 x 1) + (20 x 5 x 1 x 1) + (50 x 2 x 1 x 1) + (50 x 4 x 1 x 1) + (30 x 6 x 1 x 1) + (60 x 3 x 1 x 1) + (20 x 5 x 1 x 1) + (30 x 6 x 1 x 1)
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
60
= 10 + 100 + 180 + 10 + 200 + 100 + 100 + 200 + 180 + 180 + 100 + 180 = 1540 Dengan cara yang sama akan didapat nilai fungsi tujuan dari setiap semut. Hasil selengkapnya dari perhitungan fungsi tujuan disajikan pada Tabel 4.12. Tabel 4.12 Nilai fungsi tujuan
Ant 0 1 2 3 4
z 1540 1420 1470 1820 1550
4.4.4 Memnyimpan solusi terbaik Pada proses 4.4.3 diperoleh nilai fungsi tujuan dari setiap semut yang disajikan pada Tabel 4.12, solusi terbaik merupakan solusi dengan nilai fungsi tujuan yang paling minimal. Solusi dari ant 1 disimpan dengan nilai fungsi tujuan 1420, yaitu :
Ant 1
(0,0)
(Fasilitas,Lokasi) (1,1) (2,2)
(3,3)
Dalam solusi tersebut dapat dituliskan menjadi pengkodean permutasi yaitu : 0 1 2 3. 4.4.5 Memperbarui Matriks Pheromone Dengan Persamaan (2.7) didapatkan matriks pheromone yang baru yang menggambarkan kecenderungan masing – masing semut melewati suatu garis tertentu. Apabila nilai pheromone pada suatu garis bertambah maka menunjukkan semakin banyak semut yang melewati garis tersebut, sebaliknya jika nilai pheromone pada suatu garis berkurang menunjukkan bahwa semakin jarang semut
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
61
yang melewati garis tersebut. Matriks Pheromone ini digunakan pada iterasi berikutnya. m
k ij t 1 . ij t ij k 1
ij
k
Q untuk node dalam tabuk , Lk 0, untuk (i,j) lainnya
100 100 0,135 1540 1420 01 0 00
100 100 0,133 1470 1550 100 03 0,055 1820 100 10 0,065 1550 100 100 100 11 0,193 1420 1470 1820 12 0 02
13
100 0,0649 1540
100 0,055 1820 100 31 0,0649 1540 32 0
30
33
00 0,9 . 0,1 0,135 0,225 01 0,9 . 0,1 0 0,09 02 0,9 . 0,1 0,133 0,233 03 0,9 . 0,1 0,055 0,145 10 0,9 . 0,1 0,065 0,155 11 0,9 . 0,1 0,193 0,283 12 0,9 . 0,1 0 0,09 13 0,9 . 0,1 0,0649 0,1549
Skripsi
100 0,068 1470 100 21 0,065 1550 100 100 100 22 0,190 1540 1420 1820 23 0 20
100 100 100 0,203 1420 1470 1550
20 0,9 . 0,1 0,068 0,158 21 0,9 . 0,1 0,065 0.155 22 0,9 . 0,1 0,190 0,280 23 0,9 . 0,1 0 0,09 30 0,9 . 0,1 0,055 0,145 31 0,9 . 0,1 0,0649 0,1549 32 0,9 . 0,1 0 0,09 33 0,9 . 0,1 0,203 0,293
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
62
Sehingga didapat matriks pheromone baru :
]
[
4.4.6 Cek Siklus Apabila jumlah iterasinya belum sama dengan siklus maksimum, maka kosongkan tabu list dan selanjutnya kembali melakukan langkah pengisian tabu list. Karena jumlah iterasinya adalah 1 maka iterasi berakhir, dilanjutkan untuk proses genetic algorithm. 4.4.7 Men-generate Populasi Awal Dibangkitkan
individu
pop_size
sejumlah
dikurangi
jumlah
solusi_awal. Dimana solusi_awal yang disimpan tadi akan menjadi individu pada populasi awal. Proses pembangkitan secara acak dan digunakan pengkodean permutasi dalam solusi QAP. Hasil solusi-solusi dari men-generate disajikan dalam Tabel 4.13. Tabel 4.13 Individu populasi awal
Individu
Skripsi
Solusi 0
1
2
3
3
2
1
0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
63
Individu
Solusi 1
3
0
2
0
2
1
3
3
0
1
2
4.4.8 Seleksi Mengevaluasi masing-masing individu dengan menghitung nilai fungsi tujuan masing-masing individu, seperti pada bagian 4.4.3. Hasil nilai fungsi tujuan setiap individu di sajikan dalam Tabel 4.14. Tabel 4.14 Nilai fungsi tujuan individu
Individu
f(
)
1420 1750 1710 1470 1820
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
64
Seleksi yang digunakan dalam QAP ini adalah roda rollet, beberapa tahapannya yaitu : a. Menghitung total nilai f ( pop _ size
f (v k 1
k
) dengan k = 1,2,...,pop_size.
) = 1420 + 1750 + 1710 + 1470 + 1820 = 8170.
b. Menghitung nilai fitness setiap individu dengan j dan k = 1,2,...,pop_size:
pop_ size f (vk ) k 1
f( )
= 8170 – 1420 = 6750
= 8170 – 1470 = 6700
= 8170 – 1750 = 6420
= 8170 – 1820 = 6350
= 8170 – 1710 = 6460 c. Menghitung total nilai fitness populasi :
F
pop _ size
fithost k 1
k
= 6750 + 6420 + 6460 +6700 + 6350 = 32680
d. Menghitung probabilitas seleksi p k untuk setiap individu v j :
pk
Skripsi
fithost k , k = 1, 2, ..., pop_size F
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
65
e. Menghitung probabilitas kumulatif q k untuk setiap individu v k k
q k pi , hasilnya disajikan dalam Tabel 4.15. i 1
Tabel 4.15 Probabilitas komulatif q k
Individu
pk
qk
0,207
0,207
0,197
0,404
0,198
0,602
0,205
0,807
0,193
1
f. Melakukan generate bilangan acak dari interval [0,1] = s. Jika s q1 , maka terpilih individu pertama v1 ; sebaliknya, menentukan individu v j ke j 2 j pop _ size dengan q j 1 s q j . Generate random [0,1] serta menentuan induk crossover dan mutasi akan disajikan dalam tabel 4.16 dan 4.17, dimana random [0,1] < dimana random [0,1] <
Skripsi
akan menjadi induk crossover dan
akan menjadi induk mutasi.
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
66
Tabel 4.16 Random untuk calon induk crossover
Random [0,1]
Calon induk
Status
Random [0,1] <
crossover 0,176
0,432
Induk
0,432
0,786
Bukan Induk
0,203
0,988
Bukan Induk
0,768
0,210
Induk
0,501
0,682
Bukan Induk
Tabel 4.17 Random untuk calon induk mutasi
Random [0,1]
Calon induk
Status
Random [0,1] <
mutasi 0,132
0,25
Bukan Induk
0,768
0,98
Bukan Induk
0,989
0,68
Bukan Induk
0,212
0,23
Bukan Induk
0,564
0,05
Induk
4.4.9 Crossover 1) Menentukan induk crossover yang akan diproses dalam operator crossover. Pada setiap proses crossover, individu harus sepasang. Induk crossover yang terpilih adalah
dan
.
2) Memilih dua posisi secara acak dari 0 sampai 3, misal diperoleh posisi 2 dan 3. Misal untuk proses pertama, individu
Skripsi
dengan individu
HYBRID ALGORITHM ANT COLONY...
.
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
67
0 1
Induk_1(𝑣 ) :
Induk_2(𝑣 ) :
2 3
0 2 1 3
3) Menentukan subuntaian pada induk 1 dan induk 2. 2 3
Sub_1 :
Sub_2 : 1 3 4) Mengkopy sub-1 ke anak awal-2 dan sub-2 ke anak awal-1 bersesuaian
dengan posisinya. Anak awal _1 :
0 1 1 3
Anak awal _2 :
0 2
2 3
5) Menentukan pemetaan antara sub-1 dan sub-2. Sub_1 :
2
3
1
2
Sub_2 :
1
3
3
3
6) Menentukan anak dengan hasil pemetaan dari langkah Anak _1 (𝑣 ) :
0 2 1 3
Anak _2 (𝑣 ) :
0 1
2 3
4.4.10 Mutasi 1) Menentukan induk mutasi yang akan diproses dalam operator mutasi, yaitu individu
Skripsi
.
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
68
2) Memilih dua posisi secara acak dari 0 sampai 3, misal diperoleh posisi 1 dan 2. Misal untuk individu
Induk :
. 1 3 0 2
3) Menyisipkan posisi gen terpilih dan menggeser posisi gen yang lainnya. Anak (𝑣 ) :
1 0 3 2
4.4.11 Evaluasi anak Mengevaluasi anak dengan menghitung nilai fungsi tujuan masingmasing anak, seperti pada bagian 4.4.3. Hasil nilai fungsi tujuan setiap individu di sajikan dalam Tabel 4.18. Tabel 4.18 Nilai fungsi tujuan anak Individu f( ) 1470 1420 1590
4.4.12 Populasi Baru 1) Menggabungkan semua individu dari populasi awal, individu anak hasil crossover dan individu anak hasil mutasi. Selengkapnya disajikan dalam Tabel 4.19.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
69
2) Mengurutkan individu berdasarkan bobotnya, dari bobot yang terkecil sampai yang terbesar. Selengkapnya disajikan dalam Tabel 4.20. 3) Memilih individu terbaik sebanyak pop_size untuk dibentuk menjadi populasi baru. Selengkapnya disajikan dalam Tabel 4.21. Tabel 4.19 Gabungan individu
Individu
f(
)
f(
Individu
)
1420
1420
1750
1420
1710
1470
1470
1470
1820
1590
1470
1710
1420
1750
1590
1820
Individu
Skripsi
Tabel 4.20 Urutan individu
Tabel 4.21 Populasi baru
Solusi
f(
)
0
1
2
3
1420
0
1
2
3
1420
0
2
1
3
1470
0
2
1
3
1470
1
0
3
2
1590
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
70
4.4.13 Cek Siklus Apabila jumlah iterasinya belum sama dengan siklus maksimum, maka kembali ke proses seleksi. Karena jumlah iterasinya adalah 1 maka iterasi berakhir, Nilai fungsi tujuan yang terbaik dari proses Hybrid Ant Colony Optimization
dan
Genetic
Algorithm
adalah
nilai
fungsi
tujuan
dari
. Dalam menyelesaikan quadratic assignment problem, akan dipilih
dan
penempatan fasilitas pada lokasi dengan pasangan sebagai berikut : (Fasilitas,Lokasi)
0,0
(1,1)
(2,2)
(3,3)
Dengan jarak tempuh total perpindahan bahan antar fasilitas sebesar 1420 satuan. Dengan kata lain fasilitas ke-0 diletakkan pada lokasi ke-0, fasilitas ke-1 diletakkan pada lokasi ke-1, fasilitas ke-2 diletakkan pada lokasi ke-2 dan fasilitas ke-3 diletakkan pada lokasi ke-3.
4.5 Implementasi Program pada Contoh Kasus Quadratic Assignment Problem Program penerapan Hybrid Ant Colony Optimization dan Genetic Algorithm pada Quadratic Assignment Problem yang telah dibuat dengan pemrograman JAVA dapat diterapkan dalam contoh kasus berikut : 4.5.1 Menggunakan Data 4 Fasilitas dan 4 Lokasi Contoh kasus data 4 fasilitas dan 4 lokasi pada Lampiran 1 dapat diselesaikan dengan menggunakan program. Parameter yang digunakan sebagai berikut :
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
71
jml_ant = 5
jml_lok = jml_fas = 4
alpha = 1
pop_size = 6
betha = 1
Pc = 0,6
phero_awal = 0,1
Pm = 0,1
rho = 0,9
max_iterasi = 50
Q = 10
Diperoleh solusi (2,0,1,3) , dimana penempatan fasilitas pada lokasi dengan pasangan sebagai berikut : (fasilitas,lokasi)
(2,0)
(0,1)
(1,2)
(3,3)
Dengan jarak tempuh total perpindahan bahan antar fasilitas sebesar 1340 satuan. Dengan kata lain fasilitas ke-2 diletakkan pada lokasi ke-0, fasilitas ke-0 diletakkan pada lokasi ke-1, fasilitas ke-1 diletakkan pada lokasi ke-2 dan fasilitas ke-3 diletakkan pada lokasi ke-3. Hasil solusi selengkapnya pada data 4 fasilitas dan 4 lokasi dapat dilihat pada Lampiran 3. 4.5.2 Menggunakan Data 12 Fasilitas dan 12 Lokasi Contoh kasus data 12 fasilitas dan 12 lokasi pada Lampiran 1 dapat diselesaikan dengan menggunakan program. Parameter yang digunakan sebagai berikut :
Skripsi
jml_ant = 10
phero_awal = 0,1
alpha = 1
rho = 0,9
betha = 1
Q = 100
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
72
jml_lok = jml_fas = 12
pop_size = 20
max_iterasi = 100
Pm = 0,1
Pc = 0,6 Diperoleh solusi (2, 9, 10, 1, 11, 4, 5, 6, 7, 0, 3, 8 ) , dimana penempatan fasilitas pada lokasi dengan pasangan sebagai berikut : (fasilitas,lokasi)
(2,0)
(9,1)
(10,2)
(1,3)
(fasilitas,lokasi)
(7,8)
(0,9)
(3,10)
(8,11)
(11,4)
(4,5)
(5,6)
(6,7)
Dengan jarak tempuh total perpindahan bahan antar fasilitas sebesar 1652 satuan. Dengan kata lain fasilitas ke-2 diletakkan pada lokasi ke-0, fasilitas ke-9 diletakkan pada lokasi ke-1, fasilitas ke-10 diletakkan pada lokasi ke-2, fasilitas ke-1 diletakkan pada lokasi ke-3, fasilitas ke-11 diletakkan pada lokasi ke-4, dan seterusnya sampai fasilitas ke-8 diletakkan pada lokasi ke-11. Hasil solusi selengkapnya pada data 12 fasilitas dan 12 lokasi dapat dilihat pada Lampiran 3.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
73
4.5.3 Menggunakan Data 20 Fasilitas dan 20 Lokasi Contoh kasus data 20 fasilitas dan 20 lokasi pada Lampiran 1 dapat diselesaikan dengan menggunakan program. Parameter yang digunakan sebagai berikut :
Skripsi
jml_ant = 15
alpha = 1
betha = 10
phero_awal = 0,1
rho = 0,9
Q = 10
jml_lok = jml_fas = 20
pop_size = 25
Pc = 0,65
Pm = 0,15
max_iterasi = 300
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
74
Diperoleh solusi (7, 14, 5, 0, 18, 13, 11, 17, 15, 10, 9, 16, 1, 19, 4, 2, 3, 8, 6, 12) atau (7, 14, 0, 5, 18, 13, 11, 17, 15, 10, 9, 16, 1, 19, 4, 2, 3, 8, 6, 12) , dimana penempatan fasilitas pada lokasi dengan pasangan sebagai berikut : (fasilitas,lokasi)
(7,0)
(14,1)
(5,2)
(0,3)
(18,4)
(13,5)
(11,6)
(17,7)
(fasilitas,lokasi)
(15,8)
(10,9)
(9,10)
(16,11)
(1,12)
(19,13)
(4,14)
(2,15)
(fasilitas,lokasi)
(3,16)
(8,17)
(6,18)
(12,19)
(fasilitas,lokasi)
(7,0)
(14,1)
(0,2)
(5,3)
(18,4)
(13,5)
(11,6)
(17,7)
(fasilitas,lokasi)
(15,8)
(10,9)
(9,10)
(16,11)
(1,12)
(19,13)
(4,14)
(2,15)
(fasilitas,lokasi)
(3,16)
(8,17)
(6,18)
(12,19)
Atau
Dengan jarak tempuh total perpindahan bahan antar fasilitas sebesar 6946 satuan. Dengan kata lain fasilitas ke-7 diletakkan pada lokasi ke-0, fasilitas ke-14 diletakkan pada lokasi ke-1, fasilitas ke-5 diletakkan pada lokasi ke-2, fasilitas ke0 diletakkan pada lokasi ke-3, fasilitas ke-18 diletakkan pada lokasi ke-4, dan seterusnya sampai fasilitas ke-12 diletakkan pada lokasi ke-19. Solusi lainnya fasilitas ke-7 diletakkan pada lokasi ke-0, fasilitas ke-14 diletakkan pada lokasi ke-1, fasilitas ke-0 diletakkan pada lokasi ke-2, fasilitas ke-5 diletakkan pada lokasi ke-3, fasilitas ke-18 diletakkan pada lokasi ke-4, dan seterusnya sampai fasilitas ke-12 diletakkan pada lokasi ke-19. Hasil solusi selengkapnya pada data 20 fasilitas dan 20 lokasi dapat dilihat pada Lampiran 3.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
75
4.6 Perbandingan Hasil Perhitungan dengan Parameter yang Berbeda pada Hybrid ACO dan GA untuk QAP Pada perbandingan ini, data yang digunakan adalah quadratic assignment problem 16 fasilitas dan 16 lokasi serta 20 fasilitas dan 20 lokasi, yang dapat dilihat pada Lampiran 1. Berikut hasil perhitungan fungsi tujuan yang didapatkan pada masing – masing permasalahan dengan parameter yang berbeda, yaitu berdasarkan alpha, betha, rho, konstanta Q dan
. Pada perbandingan ini
menggunakan jml_ant = 15, phero_awal = 0,1, pop_size = 25,
= 0,15 dan
max_iterasi = 300 . Tabel 4.22 Nilai fungsi tujuan dengan pembanding alpha
Data (fasilitas,lokasi) Alpha 16 x 16
20 x 20
1
3748
7146
5
3744
6986
10
3728
6968
Berdasarkan hasil perhitungan fungsi tujuan pada Tabel 2.22 diatas menunjukkan bahwa semakin besar nilai alpha maka nilai fungsi tujuan yang didapatkan semakin baik.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
76
Tabel 4.23 Nilai fungsi tujuan dengan pembanding betha
Data (fasilitas,lokasi) Betha 16 x 16
20 x 20
1
3728
6948
5
3766
7028
10
3778
7090
Berdasarkan hasil perhitungan fungsi tujuan pada Tabel 2.23 diatas menunjukkan bahwa semakin kecil nilai betha maka nilai fungsi tujuan yang didapatkan semakin baik. Tabel 4.24 Nilai fungsi tujuan dengan pembanding rho
Data (fasilitas,lokasi) Rho 16 x 16
20 x 20
0,9
3756
7022
1,5
3770
7036
2
3778
7092
Berdasarkan hasil perhitungan fungsi tujuan pada Tabel 2.24 diatas menunjukkan bahwa semakin kecil nilai rho maka nilai fungsi tujuan yang didapatkan semakin baik.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
77
Tabel 4.25 Nilai fungsi tujuan dengan pembanding koefisien Q
Data (fasilitas,lokasi) Koefisien Q 16 x 16
20 x 20
10
3730
6988
50
3734
7036
100
3792
7054
Berdasarkan hasil perhitungan fungsi tujuan pada Tabel 2.25 diatas menunjukkan bahwa semakin kecil nilai koefisien Q maka nilai fungsi tujuan yang didapatkan semakin baik. Tabel 4.26 Nilai fungsi tujuan dengan pembanding
Data (fasilitas,lokasi) 16 x 16
20 x 20
0,5
3768
7076
0,6
3734
7006
0,7
3726
6946
Berdasarkan hasil perhitungan fungsi tujuan pada Tabel 2.26 diatas menunjukkan bahwa semakin besar nilai
maka nilai fungsi tujuan yang
didapatkan semakin baik.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
78
4.7 Perbandingan Hasil Perhitungan QAP dengan Menggunakan Hybrid ACO dan GA dengan Penelitian Hadley, Dkk (1992). Hasil dari solusi yang didapatkan dengan menggunakan hybrid ant colony optimization dan genetic algorithm dalam penyelesaian quadratic assignment problem akan dibandingkan dengan penelitihan sebelumnya yang dilakukan oleh Hadley, dkk (1992). Pada Tabel 4.22 ditunjukkan hasil perhitungan fungsi tujuan solusi optimal dan nilai solusi optimal dari masing – masing permasalahan dari penelitihan Hadley, dkk (1992). Data serta solusi optimal tersebut diambil dari Hadley, dkk (1992). Tabel 4.27 Perbandingan nilai optimal
Data (fasilitas x lokasi)
Solusi Optimal
Hybrid ACO dan GA
12 x 12
1652
1652
14 x 14
2724
2744
16 x 16
3720
3728
18 x 18
5358
5378
20 x 20
6922
6946
Dari Tabel 2.22 didapatkan bahwa hasil solusi dari QAP menggunakan hybrid ant colony optimization dan genetic algorithm mendekati solusi optimal dari penelitihan Hadley, dkk (1992).
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
BAB V KESIMPULAN DAN SARAN 5.1 Kesimpulan 1. Hybrid Ant Colony Optimization dan Genetic Algorithm dapat diterapkan untuk menyelesaikan Quadratic Assignment Problem. Adapun proses Hybrid Ant Colony Optimization dan Genetic Algorithm untuk menyelesaikan quadratic assignment problem adalah sebagai berikut : pertama setting parameter dan inisialisasi, selanjutnya masing-masing semut mengisi tabu list sampai penuh, selanjutnya menghitung fungsi tujuan untuk masing-masing semut, menyimpan solusi terbaik, update pheromone, selajutnya cek siklus, jika masih belum terpenuhi, maka kosongkan tabu list dan kembali ke pengisian tabu list, jika terpenuhi dilanjutkan ke proses men-generate populasi awal, kemudian seleksi individu, lalu proses crossover, lalu proses mutasi, anak crossover dan mutasi, evaluasi anak, memperoleh populasi baru, selajutnya cek siklus, jika masih belum terpenuhi, maka kembali ke seleksi populasi baru, jika terpenuhi proses berakhir dan didapatkan solusi dari QAP. 2.
Program penerapan Hybrid Ant Colony Optimization dan Genetic Algorithm pada Quadratic Assignment Problem dapat dibuat dengan bahasa pemrograman Java dengan NetBeans IDE.
3. Implementasi program untuk contoh kasus menggunakan data 4 fasilitas dan 4 lokasi dengan parameter jml_ant = 7, alpha = 1, betha = 1,
79 Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
80
phero_awal = 0,1, rho = 0,9, Q = 10, jml_lok = 4 , jml_fas = 4, pop_size = 10, Pc = 0,6, Pm = 0,1, max_iterasi = 100 diperoleh solusi terbaik yaitu nilai fungsi tujuan sebesar 1340 satuan, sedangkan untuk data 12 fasilitas dan 12 lokasi dengan parameter jml_ant = 10, alpha = 1, betha = 1, phero_awal = 0,1, rho = 0,9, Q = 100, jml_lok = 12 , jml_fas = 12, pop_size = 20, Pc = 0,6, Pm = 0,1, max_iterasi = 100 diperoleh solusi terbaik yaitu nilai fungsi tujuan sebesar 1652 satuan dan untuk data 20 fasilitas dan 20 lokasi dengan parameter jml_ant = 25, alpha = 1, betha = 1, phero_awal = 0,15, rho = 0,9, Q = 10, jml_lok = 20 , jml_fas = 20, pop_size = 35, Pc = 0,7, Pm = 0,1, max_iterasi = 200 diperoleh solusi terbaik yaitu nilai fungsi tujuan sebesar 6946 satuan. 4. Berdasarkan hasil yang diperoleh dari perhitungan nilai fungsi tujuan menunjukkan bahwa semakin besar nilai alpha dan Pc, semakin kecil nilai betha, rho dan koefisien Q dengan menggunakan hybrid ant colony optimization dan genetic algorithm maka solusi yang didapatkan semakin baik dan hybrid ant colony optimization dan genetic algorithm untuk menyelesaikan quadratic assignment problem mendekati solusi optimal penelitian Hadley, dkk.
5.2 Saran Untuk penelitian selanjutnya, penulis berharap bahwa materi ini dapat dikembangkan untuk Ant System-Local Search dan Ant System-Simulated Annealing dalam menyelesaikan Quadratic Assignment Problem.
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
DAFTAR PUSTAKA
1. Chartrand, G. dan Oellermann, O.R., 1993, Applied and Algorithmic Graph Theory, McGraw-Hill, New York 2. Dechter,R.,www.wikipedia.org/wiki/hybrid_algorithm_(constraint_satisfa ction), 02 November 2011 3. Dorigo, M., Maniezzo, V. dan Colorni, A., 1996, The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on System, Man, and Cybernetics-Part B 26, 29-41 4. Gaertner, D., 2004, Natural Algorithm for Optimization Problem, Imperial College 5. Gass, SI. dan Harris, CM., 1989, Encylopedia of Operations Research and Management Science, Kluwer Academic Publishers, Boston 6. Gen, M. dan Cheng, R., 1997, Genetic Algorithms and Engineering Design, John Wiley & Sons, New York. 7. Hadley, S. W., Rendl, F., dan Wolkowicz, http://www.seas.upenn.edu/qaplib/inst.html, 16 Maret 2012.
H.,
1992,
8. Huda, M., 2010, Membuat Aplikasi Database dengan Java, MySQL, dan NetBeans, PT Elex Media Komputindo, Jakarta 9. Koopmans dan Beckman, 1957, Assignment problems and location of economic activities, Econometrica, vol 25, pp 53-76, Northwestren University, U.S.A. 10. Kurniawan, D., 2008, Penerapan Ant Colony Optimization pada Permasalahan Assigment Quadratic, Universitas Airlangga, Surabaya 11. Obitko, M., 1998, Introduction to Genetic Algorithms, Czech Technical University, Prague (www.obitko.com/tutorials/genetic-algorithms) 12. Prana, A.,R., 2007, Aplikasi kombinatorial Vehicle Routing Problem, Institut Teknologi Bandung, Bandung 13. Sari, K., 2005, Algoritma Genetik dengan Order Crossover pada Travelling Salesmen Problem, Universitas Airlangga Surabaya 14. Taha, HA., 1996, Riset Operasi Jilid I, Binarupa Aksara, Jakarta
81 Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
82
15. Utama, G., 2002, Berfikir Objek : Cara Efektif Menguasai Java, IlmuKomputer.com (www.ricisan.files.wordpress.com/2009/12/caramudah-menguasai-java.pdf) 16. Zomaya, A. Y., 1996, Parallel and Distributed Computing Handbook, MacGraw-Hill, New York
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 1 - 1
Lampiran 1 : Data Quadratic Assignment Problem 1. Data 4 fasilitas dan 4 lokasi (Sember : Dorigo, dkk. (1996)) Tabel frekuensi perpindahan antar fasilitas Fasilitas 0 1 2 3 0 60 50 10 0 60 0 30 20 1 50 30 0 50 2 10 20 50 0 3 Tabel jarak antar lokasi Lokasi 0 1 0 1 0 1 0 1 2 4 2 3 5 3
2 2 4 0 6
3 3 5 6 0
2. Data 12 fasilitas dan 12 lokasi (Sumber : Hadley, dkk (1992)) Tabel frekuensi perpindahan antar fasilitas Fasilitas 0 1 2 3 4 5 6 7 8 9 10 0 3 4 6 8 5 6 6 5 1 4 0 3 0 6 3 7 9 9 2 2 7 4 1 4 6 0 2 6 4 4 4 2 6 3 2 6 3 2 0 5 5 3 3 9 4 3 3 8 7 6 5 0 4 3 4 5 7 6 4 5 9 4 5 4 0 8 5 5 5 7 5 6 9 4 3 3 8 0 6 8 4 6 6 6 2 4 3 4 5 6 0 1 5 5 7 5 2 2 9 5 5 8 1 0 4 5 8 1 7 6 4 7 5 4 5 4 0 7 9 4 4 3 3 6 7 6 5 5 7 0 10 6 7 6 6 7 5 7 3 2 7 9 11
Skripsi
HYBRID ALGORITHM ANT COLONY...
11 6 7 6 6 7 5 7 3 2 7 9 0
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lokasi 0 1 2 3 4 5 6 7 8 9 10 11
0 0 1 2 2 3 4 4 5 3 5 6 7
Tabel jarak antar lokasi 1 2 3 4 5 1 2 2 3 4 0 1 1 2 3 1 0 2 1 2 1 2 0 1 2 2 1 1 0 1 3 2 2 1 0 3 2 2 1 2 4 3 3 2 3 2 1 3 2 3 4 3 3 2 1 5 4 4 3 2 6 5 5 4 3
6 4 3 2 2 1 2 0 1 3 1 2 3
7 5 4 3 3 2 3 1 0 4 2 1 2
Lampiran 1 - 2
8 3 2 1 3 2 3 3 4 0 4 5 6
9 5 4 3 3 2 1 1 2 4 0 1 2
10 6 5 4 4 3 2 2 1 5 1 0 1
11 7 6 5 5 4 3 3 2 6 2 1 0
3. Data 14 fasilitas dan 14 lokasi (Sumber : Hadley, dkk (1992)) Tabel frekuensi perpindahan antar fasilitas Fasilitas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 3 4 6 8 5 6 6 5 1 4 6 1 5 0 3 0 6 3 7 9 9 2 2 7 4 7 9 6 1 4 6 0 2 6 4 4 4 2 6 3 6 5 6 2 6 3 2 0 5 5 3 3 9 4 3 6 3 4 3 8 7 6 5 0 4 3 4 5 7 6 7 7 3 4 5 9 4 5 4 0 8 5 5 5 7 5 1 8 5 6 9 4 3 3 8 0 6 8 4 6 7 1 8 6 6 2 4 3 4 5 6 0 1 5 5 3 7 5 7 5 2 2 9 5 5 8 1 0 4 5 2 4 5 8 1 7 6 4 7 5 4 5 4 0 7 7 5 6 9 4 4 3 3 6 7 6 5 5 7 0 9 6 5 10 6 7 6 6 7 5 7 3 2 7 9 0 6 5 11 1 9 5 3 7 1 1 7 4 5 6 6 0 5 12 5 6 6 4 3 8 8 5 5 6 5 5 5 0 13
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lokasi 0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 0 1 2 2 3 4 4 5 3 5 6 7 8 9
Tabel jarak antar lokasi 1 2 3 4 5 6 7 1 2 2 3 4 4 5 0 1 1 2 3 3 4 1 0 2 1 2 2 3 1 2 0 1 2 2 3 2 1 1 0 1 1 2 3 2 2 1 0 2 3 3 2 2 1 2 0 1 4 3 3 2 3 1 0 2 1 3 2 3 3 4 4 3 3 2 1 1 2 5 4 4 3 2 2 1 6 5 5 4 3 3 2 7 6 6 5 4 4 3 8 7 7 6 5 5 4
8 3 2 1 3 2 3 3 4 0 4 5 6 7 8
9 5 4 3 3 2 1 1 2 4 0 1 2 3 4
Lampiran 1 - 3
10 11 12 13 6 7 8 9 5 6 7 8 4 5 6 7 4 5 6 7 3 4 5 6 2 3 4 5 2 3 4 5 1 2 3 4 5 6 7 8 1 2 3 4 0 1 2 3 1 0 1 2 2 1 0 1 3 2 1 0
4. Data 16 fasilitas dan 16 lokasi (Sumber : Hadley, dkk (1992)) Tabel frekuensi perpindahan antar fasilitas Fasilitas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 3 4 6 8 5 6 6 5 1 4 6 1 5 4 5 0 3 0 6 3 7 9 9 2 2 7 4 7 9 6 3 2 1 4 6 0 2 6 4 4 4 2 6 3 6 5 6 2 6 2 6 3 2 0 5 5 3 3 9 4 3 6 3 4 7 8 3 8 7 6 5 0 4 3 4 5 7 6 7 7 3 3 3 4 5 9 4 5 4 0 8 5 5 5 7 5 1 8 5 4 5 6 9 4 3 3 8 0 6 8 4 6 7 1 8 5 6 6 6 2 4 3 4 5 6 0 1 5 5 3 7 5 9 4 7 5 2 2 9 5 5 8 1 0 4 5 2 4 5 4 5 8 1 7 6 4 7 5 4 5 4 0 7 7 5 6 5 5 9 4 4 3 3 6 7 6 5 5 7 0 9 6 5 1 8 10 6 7 6 6 7 5 7 3 2 7 9 0 6 5 4 5 11 1 9 5 3 7 1 1 7 4 5 6 6 0 5 7 4 12 5 6 6 4 3 8 8 5 5 6 5 5 5 0 5 3 13 4 3 2 7 3 5 5 9 4 5 1 4 7 5 0 8 14 5 2 6 8 3 4 6 4 5 5 8 5 4 3 8 0 15
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lokasi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Skripsi
0 0 1 2 2 3 4 4 5 3 5 6 7 8 9 7 8
Tabel jarak antar lokasi 1 2 3 4 5 6 7 1 2 2 3 4 4 5 0 1 1 2 3 3 4 1 0 2 1 2 2 3 1 2 0 1 2 2 3 2 1 1 0 1 1 2 3 2 2 1 0 2 3 3 2 2 1 2 0 1 4 3 3 2 3 1 0 2 1 3 2 3 3 4 4 3 3 2 1 1 2 5 4 4 3 2 2 1 6 5 5 4 3 3 2 7 6 6 5 4 4 3 8 7 7 6 5 5 4 6 5 5 4 3 3 2 7 6 6 5 4 4 3
8 3 2 1 3 2 3 3 4 0 4 5 6 7 8 6 7
9 5 4 3 3 2 1 1 2 4 0 1 2 3 4 2 3
HYBRID ALGORITHM ANT COLONY...
Lampiran 1 - 4
10 11 12 13 14 15 6 7 8 9 7 8 5 6 7 8 6 7 4 5 6 7 5 6 4 5 6 7 5 6 3 4 5 6 4 5 2 3 4 5 3 4 2 3 4 5 3 4 1 2 3 4 2 3 5 6 7 8 6 7 1 2 3 4 2 3 0 1 2 3 1 2 1 0 1 2 2 3 2 1 0 1 1 2 3 2 1 0 2 1 1 2 1 2 0 1 2 3 2 1 1 0
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 1 - 5
5. Data 18 fasilitas dan 18 lokasi (Sumber : Hadley, dkk (1992)) Tabel frekuensi perpindahan antar fasilitas Fasilitas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 3 4 6 8 5 6 6 5 1 4 6 1 5 4 5 6 8 0 3 0 6 3 7 9 9 2 2 7 4 7 9 6 3 2 6 6 1 4 6 0 2 6 4 4 4 2 6 3 6 5 6 2 6 5 7 2 6 3 2 0 5 5 3 3 9 4 3 6 3 4 7 8 3 2 3 8 7 6 5 0 4 3 4 5 7 6 7 7 3 3 3 4 4 4 5 9 4 5 4 0 8 5 5 5 7 5 1 8 5 4 3 3 5 6 9 4 3 3 8 0 6 8 4 6 7 1 8 5 6 7 6 6 6 2 4 3 4 5 6 0 1 5 5 3 7 5 9 4 4 4 7 5 2 2 9 5 5 8 1 0 4 5 2 4 5 4 5 4 7 8 1 7 6 4 7 5 4 5 4 0 7 7 5 6 5 5 6 10 9 4 4 3 3 6 7 6 5 5 7 0 9 6 5 1 8 5 3 10 6 7 6 6 7 5 7 3 2 7 9 0 6 5 4 5 4 6 11 1 9 5 3 7 1 1 7 4 5 6 6 0 5 7 4 5 2 12 5 6 6 4 3 8 8 5 5 6 5 5 5 0 5 3 2 4 13 4 3 2 7 3 5 5 9 4 5 1 4 7 5 0 8 5 6 14 5 2 6 8 3 4 6 4 5 5 8 5 4 3 8 0 6 8 15 6 6 5 3 4 3 7 4 4 6 5 4 5 2 5 6 0 3 16 8 6 7 2 4 3 6 4 7 10 3 6 2 4 6 8 3 0 17
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lokasi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Skripsi
0 0 1 2 2 3 4 4 5 3 5 6 7 8 9 7 8 4 5
1 1 0 1 1 2 3 3 4 2 4 5 6 7 8 6 7 3 4
Lampiran 1 - 6
Tabel jarak antar lokasi (Sumber : Hadley, dkk (1992)) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 2 3 4 4 5 3 5 6 7 8 9 7 8 4 4 1 1 2 3 3 4 2 4 5 6 7 8 6 7 3 4 0 2 1 2 2 3 1 3 4 5 6 7 5 6 3 4 2 0 1 2 2 3 3 3 4 5 6 7 5 6 4 5 1 1 0 1 1 2 2 2 3 4 5 6 4 5 3 4 2 2 1 0 2 3 3 1 2 3 4 5 3 4 4 5 2 2 1 2 0 1 3 1 2 3 4 5 3 4 4 5 3 3 2 3 1 0 4 2 1 2 3 4 2 3 5 6 1 3 2 3 3 4 0 4 5 6 7 8 6 7 1 2 3 3 2 1 1 2 4 0 1 2 3 4 2 3 5 6 4 4 3 2 2 1 5 1 0 1 2 3 1 2 6 7 5 5 4 3 3 2 6 2 1 0 1 2 2 3 7 8 6 6 5 4 4 3 7 3 2 1 0 1 1 2 8 9 7 7 6 5 5 4 8 4 3 2 1 0 2 1 9 10 5 5 4 3 3 2 6 2 1 2 1 2 0 1 7 8 6 6 5 4 4 3 7 3 2 3 2 1 1 0 8 9 2 4 3 4 4 5 1 5 6 7 8 9 7 8 0 1 3 5 4 5 5 6 2 6 7 8 9 10 8 9 1 0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Fasilitas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Skripsi
Lampiran 1 - 7
6. Data 20 fasilitas dan 20 lokasi (Sumber :) Tabel frekuensi perpindahan antar fasilitas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 3 4 6 8 5 6 6 5 1 4 6 1 5 4 5 6 8 9 4 3 0 6 3 7 9 9 2 2 7 4 7 9 6 3 2 6 6 5 6 4 6 0 2 6 4 4 4 2 6 3 6 5 6 2 6 5 7 6 5 6 3 2 0 5 5 3 3 9 4 3 6 3 4 7 8 3 2 5 5 8 7 6 5 0 4 3 4 5 7 6 7 7 3 3 3 4 4 5 5 5 9 4 5 4 0 8 5 5 5 7 5 1 8 5 4 3 3 6 4 6 9 4 3 3 8 0 6 8 4 6 7 1 8 5 6 7 6 3 9 6 2 4 3 4 5 6 0 1 5 5 3 7 5 9 4 4 4 5 2 5 2 2 9 5 5 8 1 0 4 5 2 4 5 4 5 4 7 5 3 1 7 6 4 7 5 4 5 4 0 7 7 5 6 5 5 6 10 6 7 4 4 3 3 6 7 6 5 5 7 0 9 6 5 1 8 5 3 4 6 6 7 6 6 7 5 7 3 2 7 9 0 6 5 4 5 4 6 8 2 1 9 5 3 7 1 1 7 4 5 6 6 0 5 7 4 5 2 3 7 5 6 6 4 3 8 8 5 5 6 5 5 5 0 5 3 2 4 8 3 4 3 2 7 3 5 5 9 4 5 1 4 7 5 0 8 5 6 7 1 5 2 6 8 3 4 6 4 5 5 8 5 4 3 8 0 6 8 7 3 6 6 5 3 4 3 7 4 4 6 5 4 5 2 5 6 0 3 7 7 8 6 7 2 4 3 6 4 7 10 3 6 2 4 6 8 3 0 5 6 9 5 6 5 5 6 3 5 5 6 4 8 3 8 7 7 7 5 0 4 4 6 5 5 5 4 9 2 3 7 6 2 7 3 1 3 7 6 4 0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lokasi 0 0 0 1 1 2 2 2 3 3 4 4 5 4 6 5 7 3 8 5 9 6 10 7 11 8 12 9 13 7 14 8 15 4 16 5 17 3 18 10 19
Skripsi
1 1 0 1 1 2 3 3 4 2 4 5 6 7 8 6 7 3 4 2 9
Tabel jarak antar lokasi 2 3 4 5 6 7 8 2 2 3 4 4 5 3 1 1 2 3 3 4 2 0 2 1 2 2 3 1 2 0 1 2 2 3 3 1 1 0 1 1 2 2 2 2 1 0 2 3 3 2 2 1 2 0 1 3 3 3 2 3 1 0 4 1 3 2 3 3 4 0 3 3 2 1 1 2 4 4 4 3 2 2 1 5 5 5 4 3 3 2 6 6 6 5 4 4 3 7 7 7 6 5 5 4 8 5 5 4 3 3 2 6 6 6 5 4 4 3 7 2 4 3 4 4 5 1 3 5 4 5 5 6 2 1 3 2 3 1 2 2 8 8 7 6 6 5 9
9 5 4 3 3 2 1 1 2 4 0 1 2 3 4 2 3 5 6 2 5
Lampiran 1 - 8
10 11 12 13 14 15 16 17 18 19 6 7 8 9 7 8 4 5 3 10 5 6 7 8 6 7 3 4 2 9 4 5 6 7 5 6 2 3 1 8 4 5 6 7 5 6 4 5 3 8 3 4 5 6 4 5 3 4 2 7 2 3 4 5 3 4 4 5 3 6 2 3 4 5 3 4 4 5 1 6 1 2 3 4 2 3 5 6 2 5 5 6 7 8 6 7 1 2 2 9 1 2 3 4 2 3 5 6 2 5 0 1 2 3 1 2 6 7 3 4 1 0 1 2 2 3 7 8 4 3 2 1 0 1 1 2 8 9 5 2 3 2 1 0 2 1 9 10 6 1 1 2 1 2 0 1 7 8 4 3 2 3 2 1 1 0 8 9 5 2 6 7 8 9 7 8 0 1 3 10 7 8 9 10 8 9 1 0 4 11 3 4 5 6 4 5 3 4 0 7 4 3 2 1 3 2 10 11 7 0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 1
Lampiran 2 : Source Code Program package ant; import import import import import import import import import
java.io.File; java.io.IOException; java.util.Random; javax.swing.JFileChooser; javax.swing.JOptionPane; javax.swing.JTable; jxl.Sheet; jxl.Workbook; jxl.read.biff.BiffException;
/** * * @author user */ public class input extends javax.swing.JFrame { // input; private int nMesin; private int nLokasi; // nMesin = nLokasi private int ant, Q, popSize, maxIter; private double alpha, betha, rho, pheromoneAwal, Pm, Pc; private int[][] matrixAlur; private double[][] matrixJarak; // for ant requirement private double[][] matrixBiaya; private double[][] matrixPheromone; // yang selalu di update setiap iterasi //for all private double z; // fungsi tujuan private int[][] solusi; // solusi berupa kumpulan individu (vektor) yang memiliki fungsi tujuan terkecil yaitu z private boolean cekInput; /** Creates new form input */ public input() { initComponents(); jPanel1.setVisible(false); } /** This method is called from within the constructor to * initialize the form. * WARNING: Do NOT modify this code. The content of this method is * always regenerated by the Form Editor. */ @SuppressWarnings("unchecked") // <editor-fold defaultstate="collapsed" desc="Generated Code"> private void initComponents() { jLabel1 jLabel2 jLabel3 jLabel4 jLabel5 jLabel6
Skripsi
= = = = = =
new new new new new new
javax.swing.JLabel(); javax.swing.JLabel(); javax.swing.JLabel(); javax.swing.JLabel(); javax.swing.JLabel(); javax.swing.JLabel();
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 2
jLabel7 = new javax.swing.JLabel(); jLabel8 = new javax.swing.JLabel(); jLabel9 = new javax.swing.JLabel(); jLabel10 = new javax.swing.JLabel(); inputAnt = new javax.swing.JTextField(); inputQ = new javax.swing.JTextField(); inputAlpha = new javax.swing.JTextField(); inputBetha = new javax.swing.JTextField(); inputRho = new javax.swing.JTextField(); inputPheromon = new javax.swing.JTextField(); inputPopSize = new javax.swing.JTextField(); inputPm = new javax.swing.JTextField(); inputPc = new javax.swing.JTextField(); inputMaxIter = new javax.swing.JTextField(); jButton1 = new javax.swing.JButton(); jTabbedPane1 = new javax.swing.JTabbedPane(); jScrollPane1 = new javax.swing.JScrollPane(); jScrollPane2 = new javax.swing.JScrollPane(); jButton2 = new javax.swing.JButton(); jPanel1 = new javax.swing.JPanel(); jLabel12 = new javax.swing.JLabel(); jSeparator2 = new javax.swing.JSeparator(); jScrollPane3 = new javax.swing.JScrollPane(); jTextPane1 = new javax.swing.JTextPane(); jSeparator1 = new javax.swing.JSeparator(); jLabel11 = new javax.swing.JLabel(); jMenuBar1 = new javax.swing.JMenuBar(); jMenu1 = new javax.swing.JMenu(); jMenu2 = new javax.swing.JMenu(); jMenuItem1 = new javax.swing.JMenuItem(); setDefaultCloseOperation(javax.swing.WindowConstants.DO_NOTHING_ON_CLOSE) ; addWindowListener(new java.awt.event.WindowAdapter() { public void windowClosing(java.awt.event.WindowEvent evt) { formWindowClosing(evt); } }); getContentPane().setLayout(new org.netbeans.lib.awtextra.AbsoluteLayout()); jLabel1.setText("Jumlah Semut :"); getContentPane().add(jLabel1, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 83, -1, -1)); jLabel2.setText("Max_Iterasi :"); getContentPane().add(jLabel2, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 322, -1, -1)); jLabel3.setText("Q :"); getContentPane().add(jLabel3, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 110, -1, -1)); jLabel4.setText("Alpha :"); getContentPane().add(jLabel4, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 140, -1, -1)); jLabel5.setText("Betha :"); getContentPane().add(jLabel5, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 166, -1, -1)); jLabel6.setText("Rho :");
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 3
getContentPane().add(jLabel6, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 192, -1, -1)); jLabel7.setText("Pheromon awal :"); getContentPane().add(jLabel7, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 218, -1, -1)); jLabel8.setText("Pop_size :"); getContentPane().add(jLabel8, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 244, -1, -1)); jLabel9.setText("Pm :"); getContentPane().add(jLabel9, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 270, -1, -1)); jLabel10.setText("Pc :"); getContentPane().add(jLabel10, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 296, -1, -1)); inputAnt.setText("5"); inputAnt.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { inputAntActionPerformed(evt); } }); getContentPane().add(inputAnt, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 80, 63, -1)); inputQ.setText("10"); getContentPane().add(inputQ, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 111, 63, -1)); inputAlpha.setText("1"); inputAlpha.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { inputAlphaActionPerformed(evt); } }); getContentPane().add(inputAlpha, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 137, 63, -1)); inputBetha.setText("1"); inputBetha.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { inputBethaActionPerformed(evt); } }); getContentPane().add(inputBetha, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 163, 63, -1)); inputRho.setText("0.9"); getContentPane().add(inputRho, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 189, 63, -1)); inputPheromon.setText("0.1"); getContentPane().add(inputPheromon, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 215, 63, -1)); inputPopSize.setText("6"); getContentPane().add(inputPopSize, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 241, 63, -1));
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 4
inputPm.setText("0.1"); getContentPane().add(inputPm, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 267, 63, -1)); inputPc.setText("0.6"); getContentPane().add(inputPc, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 293, 63, -1)); inputMaxIter.setText("1"); getContentPane().add(inputMaxIter, new org.netbeans.lib.awtextra.AbsoluteConstraints(100, 319, 63, -1)); jButton1.setText("File"); jButton1.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { jButton1ActionPerformed(evt); } }); getContentPane().add(jButton1, new org.netbeans.lib.awtextra.AbsoluteConstraints(207, 88, -1, -1)); jTabbedPane1.addTab("Matrix Arus", jScrollPane1); jTabbedPane1.addTab("Matrix Jarak", jScrollPane2); getContentPane().add(jTabbedPane1, new org.netbeans.lib.awtextra.AbsoluteConstraints(207, 137, 294, 202)); jButton2.setText("Start"); jButton2.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { jButton2ActionPerformed(evt); } }); getContentPane().add(jButton2, new org.netbeans.lib.awtextra.AbsoluteConstraints(106, 365, -1, -1)); jPanel1.setBackground(new java.awt.Color(102, 102, 102)); jPanel1.setBorder(new javax.swing.border.SoftBevelBorder(javax.swing.border.BevelBorder.RAISED) ); jLabel12.setFont(new java.awt.Font("Traditional Arabic", 1, 14)); jLabel12.setForeground(new java.awt.Color(255, 255, 255)); jLabel12.setHorizontalAlignment(javax.swing.SwingConstants.CENTER); jLabel12.setText("Solusi"); jTextPane1.setEditable(false); jScrollPane3.setViewportView(jTextPane1); javax.swing.GroupLayout jPanel1Layout = new javax.swing.GroupLayout(jPanel1); jPanel1.setLayout(jPanel1Layout); jPanel1Layout.setHorizontalGroup( jPanel1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADI NG) .addGroup(javax.swing.GroupLayout.Alignment.TRAILING, jPanel1Layout.createSequentialGroup() .addContainerGap()
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 5
.addGroup(jPanel1Layout.createParallelGroup(javax.swing.GroupLayout.Align ment.TRAILING) .addComponent(jScrollPane3, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, 304, Short.MAX_VALUE) .addComponent(jLabel12, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, 304, Short.MAX_VALUE) .addComponent(jSeparator2, javax.swing.GroupLayout.Alignment.LEADING, javax.swing.GroupLayout.DEFAULT_SIZE, 304, Short.MAX_VALUE)) .addContainerGap()) ); jPanel1Layout.setVerticalGroup( jPanel1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADI NG) .addGroup(jPanel1Layout.createSequentialGroup() .addContainerGap() .addComponent(jLabel12) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addComponent(jSeparator2, javax.swing.GroupLayout.PREFERRED_SIZE, 10, javax.swing.GroupLayout.PREFERRED_SIZE) .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED) .addComponent(jScrollPane3, javax.swing.GroupLayout.DEFAULT_SIZE, 193, Short.MAX_VALUE) .addContainerGap()) ); getContentPane().add(jPanel1, new org.netbeans.lib.awtextra.AbsoluteConstraints(520, 88, -1, -1)); getContentPane().add(jSeparator1, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 55, 840, -1)); jLabel11.setFont(new java.awt.Font("Tahoma", 1, 18)); jLabel11.setForeground(new java.awt.Color(102, 102, 102)); jLabel11.setHorizontalAlignment(javax.swing.SwingConstants.CENTER); jLabel11.setText("Bidink Application"); getContentPane().add(jLabel11, new org.netbeans.lib.awtextra.AbsoluteConstraints(10, 15, 840, -1)); jMenu1.setText("File"); jMenuBar1.add(jMenu1); jMenu2.setText("Help"); jMenu2.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { jMenu2ActionPerformed(evt); } }); jMenuItem1.setText("Petunjuk"); jMenuItem1.addActionListener(new java.awt.event.ActionListener() { public void actionPerformed(java.awt.event.ActionEvent evt) { jMenuItem1ActionPerformed(evt); } });
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 6
jMenu2.add(jMenuItem1); jMenuBar1.add(jMenu2); setJMenuBar(jMenuBar1); pack(); }// private void inputAntActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: } private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: try{ JFileChooser fc=new JFileChooser(); int res=fc.showOpenDialog(this); if(res==JFileChooser.APPROVE_OPTION){ File file=fc.getSelectedFile(); String dir=file.getPath(); setTabelFromExcel(dir); } }catch(Exception e){ System.out.println(e); } } private void jButton2ActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: saveInput(); if( !(cekInput)){return;} prosesAll(); jPanel1.setVisible(true); } private void inputAlphaActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: } private void inputBethaActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: } private void formWindowClosing(java.awt.event.WindowEvent evt) { // TODO add your handling code here: int tutup; tutup=JOptionPane.showConfirmDialog(this,"Apakah anda yakin ingin keluar ?","Confirmations",JOptionPane.YES_NO_OPTION); if(tutup==0){ System.exit(0); }else{ input newInput = new input(); newInput.setVisible(true); this.dispose(); }
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 7
} private void jMenu2ActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: } private void jMenuItem1ActionPerformed(java.awt.event.ActionEvent evt) { // TODO add your handling code here: new help().setVisible(true); } /** * @param args the command line arguments */ public static void main(String args[]) { java.awt.EventQueue.invokeLater(new Runnable() { @Override public void run() { new input().setVisible(true); } }); } // Variables declaration - do not modify private javax.swing.JTextField inputAlpha; private javax.swing.JTextField inputAnt; private javax.swing.JTextField inputBetha; private javax.swing.JTextField inputMaxIter; private javax.swing.JTextField inputPc; private javax.swing.JTextField inputPheromon; private javax.swing.JTextField inputPm; private javax.swing.JTextField inputPopSize; private javax.swing.JTextField inputQ; private javax.swing.JTextField inputRho; private javax.swing.JButton jButton1; private javax.swing.JButton jButton2; private javax.swing.JLabel jLabel1; private javax.swing.JLabel jLabel10; private javax.swing.JLabel jLabel11; private javax.swing.JLabel jLabel12; private javax.swing.JLabel jLabel2; private javax.swing.JLabel jLabel3; private javax.swing.JLabel jLabel4; private javax.swing.JLabel jLabel5; private javax.swing.JLabel jLabel6; private javax.swing.JLabel jLabel7; private javax.swing.JLabel jLabel8; private javax.swing.JLabel jLabel9; private javax.swing.JMenu jMenu1; private javax.swing.JMenu jMenu2; private javax.swing.JMenuBar jMenuBar1; private javax.swing.JMenuItem jMenuItem1; private javax.swing.JPanel jPanel1; private javax.swing.JScrollPane jScrollPane1; private javax.swing.JScrollPane jScrollPane2; private javax.swing.JScrollPane jScrollPane3; private javax.swing.JSeparator jSeparator1; private javax.swing.JSeparator jSeparator2; private javax.swing.JTabbedPane jTabbedPane1; private javax.swing.JTextPane jTextPane1; // End of variables declaration
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 8
private void prosesAll(){ if( !(cekInput) ){return;} try{ jPanel1.setVisible(false); // ======= proses ACO System.out.println("||||||||||||||||||||||||||||||||||||||||||||||||||| Bidink Application |||||||||||||||||||||||||||||||||||||||||||||||||||"); System.out.println("!!!!!!!!!!! ACO !!!!!!!!!!"); for(int i=0;i<maxIter;i++){ System.out.println("====== iterasi - "+(i+1)+"========"); calcZandSolutionOnAnt(); System.out.println(); } // ======= proses GA System.out.println("!!!!!!!!!!! GA !!!!!!!!!!"); // proses get Populasi awal int[][] pop = new int[popSize][nMesin]; // proses mendapatkan populasi GA if(solusi.length >= popSize){ for(int i=0;i<popSize;i++){ // copy semua solusi dari ACO ke pop System.arraycopy(solusi[i], 0, pop[i], 0, nMesin); } }else{ // jika solusi.length < popSize for(int i=0;i<solusi.length;i++){ // copy semua solusi dari ACO ke pop System.arraycopy(solusi[i], 0, pop[i], 0, nMesin); } // random kromosom sisa ruang pop yang belum terisi for (int i=solusi.length;i<popSize;i++){ // set Element pop ke - i dengan null value (dalam hal ini -1 idiom dengan null) for (int j=0;j
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 9
for(int i=0;i<maxIter;i++){ if((i+1)%50 == 0){ if(Pm <= PmInf){ tambah = true; } else if(Pm >= PmSup){ tambah = false; } if(tambah){ Pm += 0.05; } else if(!(tambah)){ Pm -= 0.05; } } System.out.println("==== iterasi- "+(i+1)+"========"); pop = calcZandSolutionOnGA(pop); } System.out.println("========== Pemilihan Solusi ========="); // mencari z setiap individu dan tampil individu pada populasi beserta nilai Z double[] vectorZPop = new double[popSize]; for(int i=0;i<popSize;i++){ vectorZPop[i] = calcZ(pop[i]); for(int j=0;j
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 10
} } private void setTabelFromExcel(String Dir) throws IOException, BiffException{ Workbook wb = Workbook.getWorkbook(new File(Dir)); //file yang akan dibuka Sheet sit1 = wb.getSheet(0); //mendapatkan sheet tabel matrix Arus Sheet sit2 = wb.getSheet(1); //mendapatkan sheet tabel matrix jarak nMesin = sit1.getRows(); //baris terakhir yang terisi nLokasi = nMesin; matrixAlur = new int[nMesin][nLokasi]; matrixJarak = new double[nMesin][nLokasi]; Object[][] absMatrixAlur = new Object[nMesin][nLokasi]; Object[][] absMatrixJarak = new Object[nMesin][nLokasi]; for (int i = 0; i < nMesin; i++) { for (int j = 0; j < nLokasi; j++) { matrixAlur[i][j]=Integer.parseInt(sit1.getCell(j,i).getContents()); matrixJarak[i][j]=Double.parseDouble(sit2.getCell(j,i).getContents()); absMatrixAlur[i][j] = matrixAlur[i][j]; absMatrixJarak[i][j] = matrixJarak[i][j]; } } String nmKlm[] = new String[nMesin]; for (int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 11
rho = Double.parseDouble(inputRho.getText()); pheromoneAwal = Double.parseDouble(inputPheromon.getText()); popSize = Integer.parseInt(inputPopSize.getText()); Pm = Double.parseDouble(inputPm.getText()); Pc = Double.parseDouble(inputPc.getText()); maxIter = Integer.parseInt(inputMaxIter.getText()); }catch(Exception e){ JOptionPane.showMessageDialog(this, "Inputan ada yang error \n"+e, "Warning", JOptionPane.ERROR_MESSAGE); cekInput = false; return; } //cek kesimetrisan matrix alur dan jarak String[] cekSimetri = new String[2]; cekSimetri = isMatrixSimetris(matrixAlur); if( "false".equals(cekSimetri[0]) ){ cekInput = false; JOptionPane.showMessageDialog(this, cekSimetri[1], "Warnink", JOptionPane.WARNING_MESSAGE); return; } cekSimetri = isMatrixSimetris(matrixJarak); if( "false".equals(cekSimetri[0]) ){ cekInput = false; JOptionPane.showMessageDialog(this, cekSimetri[1], "Warnink", JOptionPane.WARNING_MESSAGE); return; } // set matrix pheromone awal matrixPheromone = new double[nMesin][nLokasi]; for (int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 12
// kosongkan tabu list, dalam hal ini -1 di idiomkan dengan kosong atau null for(int k=0;k
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 13
// proses mendapatkan solusi if(z == -1 || zBaru < z){ // jika z = -1 maka z belum mendapatkan nilai (awal) z = zBaru; solusi = new int[0][nMesin]; // membuat variable solusi tanpa baris (masih kosonk); for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 14
break; } } return facility; } private double calcZ(int[] kromosom){ double sum = 0; for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 15
randUniform = r.nextDouble(); // bil random Pc 0 - 1 untuk menentukan induk if (randUniform < Pc){ indexIndukCX = pushArray(indexIndukCX,indexCalonInduk); } } // mencari index induk mutasi int[] indexIndukMutasi = new int[0]; for(int i=0;i<popSize;i++){ randUniform = r.nextDouble(); // bil random 0 - 1 untuk pemilihan calon induk // cek random uniform masuk luas kumulatif yang mana... for(int j=0;j<popSize;j++){ if(randUniform <= areaCumulative[j]){ indexCalonInduk = j; break; } } randUniform = r.nextDouble(); // bil random Pm 0 - 1 untuk menentukan induk if (randUniform < Pm){ indexIndukMutasi = pushArray(indexIndukCX,indexCalonInduk); } } // ====== proses crossover untuk semua induk int nIndukCX = (indexIndukCX.length/2)*2; for (int i=0;i= letakAkhir); for(int i=letakAwal;i<=letakAkhir;i++){
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 16
// cari gen yang sama dengan subtring2 dari induk2 di anak1 yang diluar area substring kemudian replace dg pemetaannya for(int j=0;jletakAkhir) && induk2[i]==anak[0][j]){ // cari pemetaan dari induk2[i] pada substring1 int pemetaan = induk1[i]; boolean isAnyPemetaan = false; do{ // cek apakah pemetaan ada pada substring2 for(int iS=letakAwal;iS<=letakAkhir;iS++){ if(induk2[iS] == pemetaan){ pemetaan = induk1[iS]; isAnyPemetaan = true; break; }else{ isAnyPemetaan = false; } } }while(isAnyPemetaan); anak[0][j] = pemetaan; break; } } // cari gen yang sama dengan subtring1 dari induk1 di anak2 yang diluar area substring kemudian replace dg pemetaannya for(int j=0;jletakAkhir) && induk1[i]==anak[1][j]){ // cari pemetaan dari induk2[i] pada substring1 int pemetaan = induk2[i]; boolean isAnyPemetaan = false; do{ // cek apakah pemetaan ada pada substring1 for(int iS=letakAwal;iS<=letakAkhir;iS++){ if(induk1[iS] == pemetaan){ pemetaan = induk2[iS]; isAnyPemetaan = true; break; }else{ isAnyPemetaan = false; } } }while(isAnyPemetaan); anak[1][j] = pemetaan; break; } } anak[0][i] = induk2[i]; anak[1][i] = induk1[i]; } return anak; } private int[] mutasiInsertion(int[] induk){ int[] anak = new int[nMesin]; Random r = new Random(); int indexGenTerpilih = r.nextInt(nMesin); int indexPindah = r.nextInt(nMesin); while(indexPindah == indexGenTerpilih){ // loopink sampek indexPindah != indexGenTerpilih indexPindah = r.nextInt(nMesin); } anak[indexPindah] = induk[indexGenTerpilih]; int indexAnak = 0; for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 17
if(i != indexGenTerpilih){ if(indexAnak == indexPindah){ // jika anak[indexAnak] sudah terisi indexAnak++; } anak[indexAnak] = induk[i]; indexAnak++; } } return anak; } private int getGen(int[] array){ // mendapatkan gen random pada array antara 0 - (nMesin-1) int gen; Random r = new Random(); do{ gen = r.nextInt(nMesin); }while( ! allowed_node(array, gen) ); return gen; } private int[][] getPop(int[][] popBaru){ double[] vectorZBaru = new double[popBaru.length]; int nPopBaru = popBaru.length; for(int i=0;i=0) && (vectorZBaru[i] < min) ){ // vectorZBaru[i] < 0 artinya null min = vectorZBaru[i]; indexNull = i; } } System.arraycopy(popBaru[indexNull], 0, pop[indexPop], 0, nMesin); indexPop++; vectorZBaru[indexNull] = -1; // yang minimal nilainya akan diganti null (-1) } return pop; } private int[] pushArray(int[] array, int value){ int length = array.length; int[] copyArray = new int[length+1]; System.arraycopy(array, 0, copyArray, 0, length); copyArray[length] = value; return copyArray; } private int[][] pushArray(int[][] populasi, int[] kromosom){ int length = populasi.length; int[][] copyPopulasi = new int[length+1][nMesin]; for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 18
return copyPopulasi; } private int[][] pushArray(int[][] populasi, int[] kromosom1, int[] kromosom2){ int length = populasi.length; int[][] copyPopulasi = new int[length+2][nMesin]; for(int i=0;i max){ max = array[i]; } } return max; } private void pushSolusi(int[] indv){ // digunakan pada ACO int nSol = solusi.length; int lengthIndv = indv.length; int[][] temp = new int[nSol+1][lengthIndv]; for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 19
} System.arraycopy(indv, 0, temp[nSol], 0, lengthIndv); solusi = new int[nSol+1][lengthIndv]; solusi = temp; } private String[] isMatrixSimetris(int[][] matrix){ String[] hasil = new String[2]; try{ hasil[0] = "true"; // merupakan answer this methode hasil[1] = ""; // status this methode result int row = matrix.length, col = matrix[0].length; if( row != col){ hasil[0] = "false"; hasil[1] = "Oppss, sorry matrix anda BUKAN matrix persegi"; return hasil; } if( row == 0){ hasil[0] = "false"; hasil[1] = "Oppss, sorry matrix anda kosonk"; return hasil; } for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 2 - 20
return hasil; } private boolean isVectorNull(double[] vector){ // -1 or < 0 is idiom with null boolean hasil = true; int n = vector.length; for(int i=0;i= 0 ){ hasil = false; break; } } return hasil; } // === method tampil array private void tampilArray(int[][] m){ int row = m.length; int col = m[0].length; for(int i=0;i
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 1
Lampiran 3 : Hasil Implementasi Program pada QAP 1.) Data 4 fasilitas dan 4 lokasi Parameter inputan Output
jml_ant = 5 alpha = 1 betha = 1 phero_awal = 0,1 rho = 0,9 Q = 10
jml_lok = jml_fas = 4 pop_size = 6 Pc = 0,6 Pm = 0,1 max_iterasi=50
Nilai fungsi tujuan = 1340 satuan Kode solusi permasalahan adalah 2 0 1 3 Runing !!!!!!!!!!! ACO !!!!!!!!!! ====== iterasi - 1======== ***** Tabu List ****** 2 1 3 0 = 1440.0 3 2 0 1 = 1680.0 0 2 3 1 = 1440.0 2 3 1 0 = 1500.0 1 2 3 0 = 1520.0 nilai z terkecil tabu list sekarang = 1440.0 ***** Solusi sekarang ****** 2130 0231 dengan nilai Z = 1440.0 ====== iterasi - 2======== ***** Tabu List ****** 0 2 1 3 = 1380.0 3 1 0 2 = 1760.0 1 3 0 2 = 1640.0 0 2 3 1 = 1440.0 3 0 2 1 = 1700.0 nilai z terkecil tabu list sekarang = 1380.0 ***** Solusi sekarang ****** 0213 dengan nilai Z = 1380.0 ====== iterasi - 49======== ***** Tabu List ****** 3 0 2 1 = 1700.0 3 0 2 1 = 1700.0 3 2 0 1 = 1680.0 3 2 0 1 = 1680.0 0 1 2 3 = 1420.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 2
nilai z terkecil tabu list sekarang = 1420.0 ***** Solusi sekarang ****** 2013 dengan nilai Z = 1340.0 ====== iterasi - 50======== ***** Tabu List ****** 1 3 0 2 = 1640.0 0 3 1 2 = 1580.0 3 0 1 2 = 1740.0 2 0 1 3 = 1340.0 0 1 2 3 = 1420.0 nilai z terkecil tabu list sekarang = 1340.0 ***** Solusi sekarang ****** 2013 dengan nilai Z = 1340.0 !!!!!!!!!!! GA !!!!!!!!!! ==== iterasi- 1======== 2013 2103 0213 1203 1203 1023 ==== iterasi- 2======== 2013 2103 0213 1203 1203 1023 ==== iterasi- 3======== 2013 2013 2013 2013 2103 2103 ==== iterasi- 49======== 2013 2013 2013 2013 2013 2013 ==== iterasi- 50======== 2013 2013 2013
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 3
2013 2013 2013 ========== Pemilihan Solusi ========= 2 0 1 3 = 1340.0 2 0 1 3 = 1340.0 2 0 1 3 = 1340.0 2 0 1 3 = 1340.0 2 0 1 3 = 1340.0 2 0 1 3 = 1340.0 ==== Solusi ===== 2013 Nilai z = 1340.0 ||||||||||||||||||||||||||||||||||||||||||||||||||| END |||||||||||||||||||||||||||||||||||||||||||||||||||
2.) Data 12 fasilitas dan 12 lokasi Parameter inputan jml_ant = 10 jml_lok = jml_fas = 12 alpha = 1 pop_size = 20 betha = 1 Pc = 0,6 phero_awal = 0,1 Pm = 0,1 rho = 0,9 max_iterasi = Q = 100 Output Nilai fungsi tujuan = 1652 satuan Kode solusi permasalahan adalah 2 9 10 1 11 4 5 6 7 0 3 8
100
Runing !!!!!!!!!!! ACO !!!!!!!!!! ====== iterasi - 1======== ***** Tabu List ****** 4 2 5 11 7 6 3 10 0 1 8 9 = 1880.0 2 11 4 7 10 3 9 1 6 5 8 0 = 1878.0 4 8 1 3 6 7 2 9 0 11 5 10 = 1866.0 8 9 0 6 3 2 1 4 10 7 11 5 = 1958.0 5 3 11 7 8 0 9 10 6 2 4 1 = 1904.0 7 5 1 2 4 3 0 10 8 11 6 9 = 1890.0 7 1 3 9 0 2 8 10 11 5 6 4 = 1970.0 10 0 5 7 9 6 2 4 8 11 1 3 = 1846.0 5 10 1 9 6 4 11 8 0 3 2 7 = 1852.0 4 11 10 3 0 8 2 7 6 9 1 5 = 1920.0 nilai z terkecil tabu list sekarang = 1846.0 ***** Solusi sekarang ****** 10 0 5 7 9 6 2 4 8 11 1 3 dengan nilai Z = 1846.0 ====== iterasi - 2======== ***** Tabu List ****** 5 2 1 7 3 4 0 10 6 8 11 9 = 1896.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 4
8 0 2 9 11 3 7 1 6 5 4 10 = 1926.0 4 7 0 9 3 2 1 8 11 6 5 10 = 1886.0 4 3 8 9 1 10 6 11 2 5 7 0 = 1820.0 10 2 5 0 7 8 3 4 11 9 6 1 = 1960.0 7 9 3 6 0 1 8 4 10 5 2 11 = 1890.0 4 5 8 2 9 11 1 10 0 3 7 6 = 1942.0 1 3 7 2 6 4 11 10 8 0 5 9 = 1914.0 3 10 2 9 4 5 7 6 8 11 1 0 = 1860.0 10 9 8 3 7 2 11 4 5 1 6 0 = 1912.0 nilai z terkecil tabu list sekarang = 1820.0 ***** Solusi sekarang ****** 4 3 8 9 1 10 6 11 2 5 7 0 dengan nilai Z = 1820.0 ====== iterasi - 99======== ***** Tabu List ****** 7 3 0 9 10 8 5 2 11 1 4 6 = 1874.0 7 3 10 9 4 8 1 0 6 11 2 5 = 1896.0 8 1 11 0 4 6 5 10 2 7 3 9 = 1872.0 10 8 9 7 4 6 5 0 3 1 11 2 = 1802.0 7 2 1 0 10 8 5 9 3 4 6 11 = 1910.0 8 1 2 0 4 10 5 6 3 9 7 11 = 1868.0 7 3 9 0 4 6 5 10 2 8 11 1 = 1816.0 7 3 9 0 4 11 10 6 5 8 1 2 = 1816.0 7 8 9 4 11 1 10 0 2 5 3 6 = 1840.0 7 3 0 2 4 1 11 9 5 10 6 8 = 1798.0 nilai z terkecil tabu list sekarang = 1798.0 ***** Solusi sekarang ****** 2 1 9 10 11 6 5 0 4 8 3 7 dengan nilai Z = 1716.0 ====== iterasi - 100======== ***** Tabu List ****** 2 7 9 4 10 1 5 6 0 8 3 11 = 1844.0 7 3 5 11 4 6 1 10 2 0 9 8 = 1842.0 8 9 11 0 4 6 5 10 2 7 3 1 = 1896.0 7 3 0 9 10 8 1 2 6 4 5 11 = 1896.0 11 1 9 4 6 3 5 2 0 7 10 8 = 1888.0 8 7 11 0 3 2 5 9 6 1 10 4 = 1874.0 7 3 0 2 4 10 5 6 11 1 9 8 = 1802.0 2 3 0 6 4 8 5 7 11 1 9 10 = 1856.0 7 3 0 6 4 10 8 9 11 1 2 5 = 1852.0 7 3 5 0 4 1 10 9 2 8 6 11 = 1840.0 nilai z terkecil tabu list sekarang = 1802.0 ***** Solusi sekarang ****** 2 1 9 10 11 6 5 0 4 8 3 7 dengan nilai Z = 1716.0 !!!!!!!!!!! GA !!!!!!!!!! ==== iterasi- 1======== 2 1 9 10 11 6 5 0 4 8 3 7 3 0 2 4 6 10 11 9 8 5 7 1
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 5
3 0 11 2 8 5 9 4 10 6 1 7 7 5 2 6 10 1 0 3 8 11 4 9 1 8 6 11 3 4 5 10 0 7 9 2 3 0 11 2 5 9 8 4 10 6 1 7 7 8 6 10 1 0 2 5 3 11 4 9 8 1 0 6 11 3 4 5 10 7 9 2 3 6 4 9 0 1 5 7 8 11 2 10 2 7 10 6 5 4 3 9 8 0 11 1 1 8 0 6 11 4 3 5 10 7 9 2 3 6 4 9 0 5 1 7 8 11 2 10 1 8 0 6 11 3 4 5 10 7 9 2 3 0 11 4 5 9 10 2 6 8 1 7 2 9 8 3 1 6 5 0 7 10 4 11 2 4 3 11 8 5 1 7 9 10 0 6 4 3 10 1 0 8 11 6 5 9 2 7 4 3 10 1 8 11 0 6 5 9 2 7 11 8 10 1 0 3 4 5 6 9 2 7 10 4 9 3 11 2 7 0 1 5 8 6 ==== iterasi- 2======== 2 1 9 10 11 6 5 0 4 8 3 7 3 0 2 4 6 10 11 9 8 5 7 1 2 0 11 10 9 6 5 1 4 8 3 7 3 0 11 2 8 5 9 4 10 6 1 7 3 0 11 1 8 10 6 4 5 9 2 7 3 1 9 2 8 5 11 4 10 6 0 7 11 6 10 1 0 3 4 9 8 5 2 7 7 5 2 6 10 1 0 3 8 11 4 9 1 8 6 11 3 4 5 10 0 7 9 2 0 8 10 1 11 3 4 6 5 9 2 7 3 0 11 2 5 9 8 4 10 6 1 7 7 8 6 10 1 0 2 5 3 11 4 9 8 1 0 6 11 3 4 5 10 7 9 2 3 6 4 9 0 1 5 7 8 11 2 10 2 7 5 6 10 1 0 9 8 3 11 4 2 7 10 6 5 4 3 9 8 0 11 1 1 8 0 6 11 4 3 5 10 7 9 2 3 6 4 9 0 5 1 7 8 11 2 10 1 8 0 6 11 3 4 5 10 7 9 2 3 0 11 4 5 9 10 2 6 8 1 7 ==== iterasi- 99======== 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 6
2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 ==== iterasi- 100======== 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 2 9 10 1 11 4 5 6 7 0 3 8 ========== Pemilihan Solusi ========= 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 7
2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 2 9 10 1 11 4 5 6 7 0 3 8 = 1652.0 ==== Solusi ===== 2 9 10 1 11 4 5 6 7 0 3 8 Nilai z = 1652.0 ||||||||||||||||||||||||||||||||||||||||||||||||||| END |||||||||||||||||||||||||||||||||||||||||||||||||||
3.) Data 14 fasilitas dan 14 lokasi Parameter inputan jml_ant = 20 jml_lok = jml_fas = 14 alpha = 1 pop_size = 25 betha = 5 Pc = 0,6 phero_awal = 0,1 Pm = 0,15 rho = 0,9 max_iterasi = Q = 100 Output Nilai fungsi tujuan = 2744 satuan Kode solusi permasalahan adalah 3 8 6 5 13 1 11 10 0 4 9 2 12 7
400
Runing !!!!!!!!!!! ACO !!!!!!!!!! ====== iterasi - 1======== ***** Tabu List ****** 5 12 11 9 3 8 7 1 2 13 10 6 0 4 = 3212.0 12 7 1 8 4 10 2 3 0 6 9 13 11 5 = 3134.0 12 13 7 9 5 4 3 0 11 10 1 8 6 2 = 3150.0 7 11 9 3 8 4 0 10 6 2 5 12 1 13 = 3166.0 0 6 12 5 10 2 9 3 1 11 13 7 8 4 = 3214.0 7 11 3 12 13 2 9 10 5 8 1 4 0 6 = 3168.0 2 0 7 9 10 1 6 13 8 12 11 4 3 5 = 3158.0 3 2 9 10 0 1 6 11 8 13 4 12 5 7 = 3080.0 6 11 1 10 12 2 4 8 9 0 7 3 5 13 = 3112.0 4 3 12 13 9 2 0 11 8 7 5 6 10 1 = 3136.0 13 5 4 9 12 0 2 11 6 3 8 7 1 10 = 3392.0 5 9 12 0 13 1 10 8 7 11 2 3 6 4 = 3220.0 9 6 8 2 0 12 10 7 11 13 3 4 1 5 = 3290.0 11 8 2 12 3 1 7 4 5 10 0 6 13 9 = 3294.0 8 12 7 13 1 10 5 6 11 4 3 0 2 9 = 3150.0 12 0 6 10 7 13 11 5 4 2 9 8 3 1 = 3156.0 5 12 8 2 3 0 6 10 13 7 4 1 9 11 = 3222.0 0 11 7 1 10 2 12 5 13 8 9 4 3 6 = 3256.0 3 13 2 6 7 12 8 11 5 9 1 10 0 4 = 3140.0 7 11 5 2 12 13 10 6 1 3 8 0 9 4 = 3142.0 nilai z terkecil tabu list sekarang = 3080.0 ***** Solusi sekarang ****** 3 2 9 10 0 1 6 11 8 13 4 12 5 7 dengan nilai Z = 3080.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 8
====== iterasi - 2======== ***** Tabu List ****** 6 13 7 0 9 5 8 4 11 3 2 10 1 12 = 3146.0 3 8 0 2 12 9 4 6 1 7 11 5 10 13 = 3108.0 5 1 11 4 12 7 0 3 13 9 2 8 10 6 = 3226.0 2 6 8 7 10 3 13 1 12 4 11 5 0 9 = 3156.0 5 12 10 7 1 3 13 8 2 4 0 9 6 11 = 3242.0 12 0 7 8 11 4 1 3 13 5 9 6 10 2 = 3154.0 13 8 0 10 3 5 9 12 4 2 1 11 7 6 = 3136.0 6 2 8 9 0 3 10 13 5 12 7 1 4 11 = 3264.0 6 3 8 0 7 2 9 1 5 4 10 13 12 11 = 3104.0 9 7 0 4 2 5 8 3 12 1 11 6 10 13 = 3144.0 7 2 6 11 4 5 10 3 8 0 1 12 9 13 = 3156.0 10 7 13 5 3 2 0 12 1 11 8 6 4 9 = 3286.0 4 9 1 8 7 3 6 13 5 2 0 10 12 11 = 3208.0 12 11 1 8 5 0 6 3 7 13 4 9 2 10 = 3152.0 5 3 6 13 9 0 4 2 1 11 12 7 8 10 = 3112.0 8 12 11 2 7 10 3 1 6 9 4 0 13 5 = 3176.0 1 8 7 5 12 13 0 11 2 3 6 9 10 4 = 3250.0 9 10 3 6 2 8 1 11 12 5 4 0 7 13 = 3140.0 12 10 9 5 7 6 1 11 3 0 2 4 8 13 = 3162.0 11 1 7 13 4 5 0 12 6 9 3 10 8 2 = 3170.0 nilai z terkecil tabu list sekarang = 3104.0 ***** Solusi sekarang ****** 3 2 9 10 0 1 6 11 8 13 4 12 5 7 dengan nilai Z = 3080.0 ====== iterasi - 399======== ***** Tabu List ****** 10 12 2 3 4 1 6 0 13 11 5 9 8 7 = 3150.0 3 2 8 0 11 9 13 1 12 10 5 6 7 4 = 3078.0 8 6 13 7 11 9 0 2 1 12 4 10 5 3 = 3134.0 3 2 8 12 4 1 6 10 11 7 5 13 9 0 = 3106.0 12 8 0 5 10 9 6 2 13 7 11 1 4 3 = 3152.0 7 3 8 5 9 12 11 6 1 4 0 10 13 2 = 3110.0 10 6 1 0 11 3 8 7 5 13 2 12 4 9 = 3094.0 12 2 8 3 10 6 11 13 7 1 4 0 5 9 = 3126.0 7 8 1 2 9 0 12 5 13 10 6 11 3 4 = 3198.0 7 3 5 8 13 6 1 11 0 2 10 12 4 9 = 2942.0 5 0 13 1 4 3 9 11 6 2 10 7 8 12 = 3050.0 2 3 7 5 8 12 11 4 9 0 10 6 13 1 = 3208.0 3 8 13 7 1 9 11 5 6 2 4 0 12 10 = 3058.0 0 3 2 13 8 10 5 12 11 4 6 7 9 1 = 3138.0 7 0 9 3 10 5 13 12 2 8 4 6 11 1 = 3120.0 12 7 1 10 5 11 4 6 3 0 8 13 9 2 = 3018.0 7 1 5 9 8 10 11 13 6 2 0 12 3 4 = 3094.0 3 2 13 1 11 5 6 12 0 7 8 10 4 9 = 3080.0 8 13 5 2 3 7 1 6 9 4 10 11 0 12 = 3068.0 2 9 13 10 1 0 8 4 7 11 3 6 5 12 = 3214.0 nilai z terkecil tabu list sekarang = 2942.0 ***** Solusi sekarang ******
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 9
3 8 6 5 10 13 11 4 0 1 9 2 12 7 dengan nilai Z = 2746.0 ====== iterasi - 400======== ***** Tabu List ****** 7 8 10 1 4 11 6 9 12 2 5 3 0 13 = 3088.0 2 3 5 10 4 9 6 8 1 12 13 7 11 0 = 3150.0 7 3 10 1 8 9 2 0 11 4 6 13 12 5 = 3282.0 3 12 0 9 13 5 6 4 8 2 10 11 1 7 = 3104.0 7 6 8 1 9 10 5 13 12 11 3 0 4 2 = 3000.0 3 0 2 8 13 4 7 1 12 11 9 5 6 10 = 3036.0 2 12 8 3 4 5 10 11 0 1 6 7 13 9 = 3048.0 2 3 4 10 11 13 1 8 5 7 9 6 0 12 = 3198.0 8 2 10 1 3 6 11 13 9 4 5 12 0 7 = 3050.0 8 0 3 13 10 12 1 4 11 5 7 2 6 9 = 3122.0 12 3 9 2 13 1 7 10 4 8 6 0 5 11 = 3128.0 8 2 13 4 7 3 11 12 9 0 1 10 5 6 = 3142.0 3 8 7 1 13 5 4 6 0 2 10 9 12 11 = 3046.0 7 0 13 12 8 9 6 4 11 2 3 1 10 5 = 3200.0 3 9 7 8 11 13 0 12 5 4 2 6 1 10 = 3180.0 12 2 9 10 4 3 8 6 11 0 13 7 5 1 = 3074.0 7 9 8 0 11 12 5 13 10 2 1 6 3 4 = 3184.0 2 5 3 12 7 6 13 10 0 9 1 11 8 4 = 3186.0 3 12 8 4 10 9 11 0 2 6 13 1 5 7 = 2958.0 12 13 9 7 3 4 11 6 2 8 5 0 1 10 = 3118.0 nilai z terkecil tabu list sekarang = 2958.0 ***** Solusi sekarang ****** 3 8 6 5 10 13 11 4 0 1 9 2 12 7 dengan nilai Z = 2746.0 !!!!!!!!!!! GA !!!!!!!!!! ==== iterasi- 1======== 3 8 6 5 10 13 11 4 0 1 9 2 12 7 7 12 2 13 1 9 8 0 4 6 11 3 10 5 7 4 12 0 6 1 3 10 2 13 9 11 5 8 8 4 9 6 10 11 1 3 12 5 7 2 0 13 7 4 12 0 13 1 3 10 2 6 8 11 5 9 3 1 6 12 7 8 13 4 5 11 9 10 0 2 7 1 4 12 0 6 3 10 2 13 9 11 5 8 7 5 1 3 4 8 0 11 12 13 9 6 10 2 7 5 1 3 4 9 0 11 12 6 8 13 10 2 5 2 7 11 6 9 12 8 1 10 13 3 4 0 6 3 1 7 10 8 13 11 5 9 0 2 12 4 7 4 12 0 6 1 3 10 13 9 11 5 8 2 11 2 0 4 12 8 3 1 10 9 7 5 6 13 11 3 0 2 4 7 9 10 12 6 5 8 13 1 4 1 0 6 5 11 10 7 9 3 2 8 13 12 5 1 0 2 4 7 9 10 12 13 8 6 3 11 1 4 0 6 5 11 10 7 9 3 2 8 13 12 7 5 1 3 4 9 0 12 6 8 13 10 2 11
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 10
4 9 7 11 12 10 2 8 6 1 0 5 3 13 5 1 0 2 4 7 10 9 12 13 8 6 3 11 0 1 12 2 7 5 11 3 9 13 10 6 8 4 13 9 10 11 6 8 0 1 3 12 7 4 5 2 11 12 8 13 0 5 2 10 3 9 6 4 1 7 11 0 2 13 12 5 10 4 8 9 1 7 6 3 0 1 12 2 7 5 11 8 3 13 10 6 9 4 ==== iterasi- 2======== 3 8 6 5 10 13 11 4 0 1 9 2 12 7 7 4 9 0 5 1 11 10 12 13 8 6 3 2 7 12 2 13 1 9 8 0 4 10 11 6 3 5 7 12 2 13 9 1 8 0 4 6 11 3 10 5 7 4 12 0 13 5 10 9 2 1 8 6 3 11 7 0 2 13 12 6 10 4 8 9 1 11 5 3 7 12 2 13 1 9 8 0 4 6 11 3 10 5 7 12 2 13 1 9 0 4 6 11 3 8 10 5 7 1 4 12 0 6 3 10 2 11 13 9 5 8 6 1 0 2 4 7 12 10 13 9 11 5 8 3 7 4 12 0 6 1 3 10 2 13 9 11 5 8 11 1 4 12 0 5 3 10 2 13 9 7 6 8 7 4 12 0 13 6 1 3 10 9 11 5 8 2 8 4 9 6 10 11 1 3 12 5 7 2 0 13 7 4 12 0 13 1 3 10 2 6 8 11 5 9 7 4 12 0 13 1 11 3 10 2 6 8 5 9 3 1 6 12 7 8 13 4 5 11 9 10 0 2 7 1 4 12 0 6 3 10 2 13 9 11 5 8 7 5 1 3 4 8 0 11 12 13 9 6 10 2 7 5 1 3 4 9 0 11 12 6 8 13 10 2 5 2 7 11 6 9 12 8 1 10 13 3 4 0 6 3 1 7 10 8 13 11 5 9 0 2 12 4 7 4 12 0 6 1 3 10 13 9 11 5 8 2 11 3 0 13 12 5 10 4 8 9 1 7 6 2 5 1 0 2 11 4 7 9 10 12 13 8 6 3 ==== iterasi- 399======== 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 11
3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 ==== iterasi- 400======== 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 3 8 6 5 13 1 11 10 0 4 9 2 12 7 ========== Pemilihan Solusi ========= 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 12
3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 3 8 6 5 13 1 11 10 0 4 9 2 12 7 = 2744.0 ==== Solusi ===== 3 8 6 5 13 1 11 10 0 4 9 2 12 7 Nilai z = 2744.0 ||||||||||||||||||||||||||||||||||||||||||||||||||| END |||||||||||||||||||||||||||||||||||||||||||||||||||
4.) Data 16 fasilitas dan 16 lokasi Parameter inputan jml_ant = 15 jml_lok = jml_fas = 16 alpha = 1 pop_size = 25 betha = 10 Pc = 0,6 phero_awal = 0,1 Pm = 0,15 rho = 0,9 max_iterasi = 300 Q = 10 Output Nilai fungsi tujuan = 3728 satuan Kode solusi permasalahan adalah 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 atau 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 . Runing !!!!!!!!!!! ACO !!!!!!!!!! ====== iterasi - 1======== ***** Tabu List ****** 10 1 8 11 4 15 9 7 6 13 2 5 0 12 3 14 15 10 0 4 5 6 14 12 11 2 7 1 9 8 3 13 3 0 9 7 15 12 14 1 13 2 6 11 8 10 4 5 1 13 10 2 5 14 0 9 6 8 15 3 12 11 4 7 10 15 1 4 8 3 11 13 7 14 9 6 0 12 2 5 15 4 2 10 13 9 1 0 14 5 11 8 12 7 6 3 0 13 14 11 12 8 6 5 1 3 15 7 2 4 10 9 10 2 15 6 3 1 11 8 0 12 5 4 7 14 13 9 15 4 6 10 14 7 5 11 3 9 12 1 8 0 13 2 8 12 13 4 11 15 14 9 6 7 5 0 2 10 1 3 0 10 2 3 9 12 7 1 14 13 15 8 5 6 4 11 6 13 10 9 14 4 8 5 1 0 2 12 15 3 11 7 2 5 1 14 13 12 3 0 8 9 7 15 10 6 4 11 7 4 2 8 10 14 1 3 13 15 9 0 6 11 12 5 0 2 12 9 7 5 3 4 1 8 11 6 10 15 13 14
Skripsi
= 4222.0 = 4206.0 = 4210.0 = 4202.0 = 4438.0 = 4250.0 = 4204.0 = 4144.0 = 4202.0 = 4300.0 = 4374.0 = 4276.0 = 4188.0 = 4440.0 = 4198.0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 13
nilai z terkecil tabu list sekarang = 4144.0 ***** Solusi sekarang ****** 10 2 15 6 3 1 11 8 0 12 5 4 7 14 13 9 dengan nilai Z = 4144.0 ====== iterasi - 2======== ***** Tabu List ****** 3 13 12 7 11 6 0 5 4 9 14 1 10 8 2 15 = 4282.0 14 4 0 12 3 13 8 6 5 1 11 2 10 15 7 9 = 4170.0 3 8 9 0 4 6 7 14 12 13 15 10 11 5 1 2 = 4096.0 12 13 0 9 7 3 14 1 11 2 15 6 4 5 8 10 = 4288.0 0 4 2 13 12 11 5 7 15 1 8 9 6 3 14 10 = 4244.0 7 12 13 6 1 14 9 4 3 5 15 0 2 10 8 11 = 4166.0 0 14 9 6 13 4 11 8 10 7 12 2 5 3 15 1 = 4308.0 2 4 8 1 13 11 14 12 15 0 9 3 10 6 5 7 = 4268.0 15 2 9 4 3 0 7 5 6 12 13 11 8 10 1 14 = 4358.0 3 9 2 14 7 8 6 5 1 11 10 15 13 12 4 0 = 4248.0 10 8 12 0 13 5 1 9 7 14 4 15 2 11 3 6 = 4244.0 15 2 10 9 7 8 0 3 13 6 5 1 11 14 4 12 = 4196.0 4 8 2 10 6 7 3 5 0 14 12 9 11 1 13 15 = 4222.0 2 13 10 3 0 6 12 14 5 11 1 7 8 15 4 9 = 4272.0 7 2 5 1 3 12 6 14 11 4 9 8 10 0 15 13 = 4234.0 nilai z terkecil tabu list sekarang = 4096.0 ***** Solusi sekarang ****** 3 8 9 0 4 6 7 14 12 13 15 10 11 5 1 2 dengan nilai Z = 4096.0 ====== iterasi - 299======== ***** Tabu List ****** 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 nilai z terkecil tabu list sekarang = 4196.0 ***** Solusi sekarang ****** 12 1 9 4 11 10 13 5 2 6 0 7 14 3 15 8 12 1 4 9 11 10 13 5 2 6 0 7 14 3 15 8 dengan nilai Z = 3732.0 ====== iterasi - 300======== ***** Tabu List ******
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 14
15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 15 2 10 7 8 12 0 5 6 14 11 3 13 4 1 9 = 4196.0 nilai z terkecil tabu list sekarang = 4196.0 ***** Solusi sekarang ****** 12 1 9 4 11 10 13 5 2 6 0 7 14 3 15 8 12 1 4 9 11 10 13 5 2 6 0 7 14 3 15 8 dengan nilai Z = 3732.0 !!!!!!!!!!! GA !!!!!!!!!! ==== iterasi- 1======== 12 1 9 4 11 10 13 5 2 6 0 7 14 3 15 8 12 1 4 9 11 10 13 5 2 6 0 7 14 3 15 8 12 1 4 9 11 10 13 5 2 6 0 7 14 3 8 15 12 1 4 0 11 2 7 13 10 14 9 5 6 3 15 8 12 8 9 4 11 10 13 5 2 6 0 7 14 3 1 15 12 1 4 11 10 13 5 2 6 0 7 14 3 9 15 8 9 8 6 15 4 5 3 11 10 0 13 12 7 14 1 2 15 14 3 13 2 12 1 9 7 8 11 0 10 4 6 5 2 9 1 6 12 5 15 3 11 10 0 13 8 4 14 7 9 14 8 7 13 6 0 4 12 11 5 10 3 15 2 1 6 14 8 11 15 10 0 3 2 5 13 7 4 12 1 9 0 5 3 4 8 12 1 7 10 6 11 14 15 9 13 2 0 5 3 4 8 12 1 7 10 6 11 14 15 9 13 2 1 2 0 7 15 13 10 12 6 5 9 11 8 14 4 3 3 1 8 13 12 14 15 5 2 6 0 7 10 9 11 4 4 3 12 2 14 9 0 15 11 10 13 8 5 1 7 6 3 1 8 7 12 14 6 15 13 10 9 5 2 0 11 4 2 9 0 1 6 12 5 15 4 7 8 14 3 11 13 10 4 10 9 1 8 7 6 12 5 11 14 15 3 0 2 13 0 6 5 4 1 9 11 8 7 3 12 13 10 14 15 2 4 1 10 12 9 14 8 6 5 0 11 3 15 13 2 7 4 7 10 12 9 14 6 5 0 11 3 15 13 1 2 8 0 5 3 4 8 12 1 7 10 6 14 15 11 9 13 2 10 9 0 14 8 4 15 13 3 7 12 11 6 5 2 1 0 2 5 4 6 3 10 15 11 12 1 7 8 9 13 14 ==== iterasi- 2======== 12 1 9 4 11 10 13 5 2 6 0 7 14 3 15 8 12 1 4 9 11 10 13 5 2 6 0 7 14 3 15 8
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 15
12 1 4 9 11 10 13 5 2 6 0 7 14 3 8 15 1 12 9 11 4 10 13 5 2 6 0 7 14 3 15 8 12 1 4 9 11 10 13 5 2 6 0 15 8 14 7 3 12 1 9 4 11 10 13 5 6 0 2 7 14 3 15 8 12 1 4 6 9 11 10 13 5 2 0 7 14 3 8 15 12 1 4 0 11 2 7 13 10 14 9 5 6 3 15 8 12 8 9 4 11 10 13 5 2 6 0 7 14 3 1 15 9 1 4 11 10 13 5 2 6 0 7 14 3 15 8 12 12 1 4 11 10 13 5 2 6 0 7 14 3 9 15 8 12 1 4 11 10 5 2 6 0 7 14 3 9 13 15 8 9 8 6 15 4 5 3 11 10 0 13 12 7 14 1 2 1 4 0 11 2 7 12 13 10 14 9 5 6 3 15 8 12 1 4 6 10 13 5 3 11 0 7 14 2 9 15 8 7 0 5 3 4 8 12 1 10 6 11 14 15 9 13 2 15 14 3 13 2 12 1 9 7 8 11 0 10 4 6 5 2 1 0 15 7 13 10 12 6 5 9 11 8 14 4 3 2 9 1 6 12 5 15 3 11 10 0 13 8 4 14 7 12 10 4 0 1 9 11 8 7 3 2 5 6 14 15 13 9 14 8 7 13 6 0 4 12 11 5 10 3 15 2 1 6 14 8 11 15 10 0 3 2 5 13 7 4 12 1 9 0 5 3 4 8 12 1 7 10 6 11 14 15 9 13 2 0 5 3 4 8 12 1 7 10 6 11 14 15 9 13 2 1 2 0 7 15 13 10 12 6 5 9 11 8 14 4 3 ==== iterasi- 299======== 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 ==== iterasi- 300========
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 16
12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 ========== Pemilihan Solusi ========= 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 17
12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 = 3728.0 ==== Solusi ===== 12 1 4 9 11 10 13 6 2 5 0 7 14 3 15 8 12 1 9 4 11 10 13 6 2 5 0 7 14 3 15 8 Nilai z = 3728.0 ||||||||||||||||||||||||||||||||||||||||||||||||||| END |||||||||||||||||||||||||||||||||||||||||||||||||||
5.) Data 18 fasilitas dan 18 lokasi Parameter inputan jml_ant = 20 jml_lok = jml_fas = 18 alpha = 1 pop_size = 35 betha = 10 Pc = 0,6 phero_awal = 0,1 Pm = 0,15 rho = 0,9 max_iterasi = Q = 10 Output Nilai fungsi tujuan = 5378 satuan Kode solusi permasalahan adalah 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3
550
Runing !!!!!!!!!!! ACO !!!!!!!!!! ====== iterasi - 1======== ***** Tabu List ****** 6 9 5 11 16 2 17 1 14 13 15 0 8 4 10 3 7 12 5 12 17 6 10 11 15 0 9 16 1 14 13 8 3 4 7 2 10 12 17 4 8 14 13 7 2 1 15 3 6 16 5 11 9 0 5 13 0 10 7 1 15 8 17 11 6 12 3 9 14 16 2 4 17 11 0 7 4 3 5 8 9 12 15 10 6 16 2 13 14 1 11 16 4 3 0 13 14 15 7 10 1 2 17 12 5 8 9 6 11 12 3 2 1 13 15 10 0 9 16 5 6 17 14 8 7 4 1 14 6 16 13 12 8 3 7 0 15 9 10 11 4 2 5 17 11 2 5 16 8 6 3 14 0 12 15 13 17 1 7 9 10 4 1 15 2 12 14 3 17 9 4 0 10 6 13 11 8 16 7 5 1 14 12 8 7 11 6 2 9 17 3 0 5 16 15 13 10 4 8 6 12 14 1 17 7 15 0 3 10 9 11 13 4 16 5 2 7 14 13 16 3 10 4 12 15 0 11 8 17 5 9 2 1 6 2 1 3 14 15 10 7 5 6 11 12 8 4 17 13 16 0 9 8 3 14 9 10 13 12 0 16 1 5 17 7 6 2 4 15 11 6 12 1 8 16 17 3 10 4 9 11 2 5 0 15 7 14 13 13 3 15 4 5 2 7 0 9 11 8 12 17 10 14 6 1 16 6 2 13 17 4 10 0 16 15 9 1 7 14 11 5 12 3 8 10 4 7 1 6 15 0 9 5 12 11 16 13 14 8 2 3 17 13 2 12 16 4 5 6 3 17 15 9 7 14 10 8 1 0 11 nilai z terkecil tabu list sekarang = 5815.0 ***** Solusi sekarang ****** 6 2 13 17 4 10 0 16 15 9 1 7 14 11 5 12 3 8 dengan nilai Z = 5815.0
Skripsi
= 5819.0 = 5911.0 = 6054.0 = 5876.0 = 6053.0 = 6103.0 = 5851.0 = 5916.0 = 5992.0 = 5997.0 = 5990.0 = 6060.0 = 6012.0 = 6288.0 = 5982.0 = 5971.0 = 6134.0 = 5815.0 = 6112.0 = 6112.0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
====== iterasi - 2======== ***** Tabu List ****** 9 14 15 8 1 10 0 16 7 17 11 13 6 2 12 4 3 5 13 2 12 16 1 3 6 9 7 8 15 0 17 10 5 14 4 11 10 1 17 16 11 13 4 5 7 0 15 12 3 8 14 2 9 6 9 2 4 10 15 11 7 14 0 16 12 6 17 3 8 13 5 1 13 12 2 5 4 3 0 8 15 9 10 11 6 16 14 1 7 17 13 14 4 16 0 10 17 7 9 3 15 12 6 11 5 2 1 8 7 6 13 16 0 10 15 8 2 1 11 12 17 14 5 9 3 4 7 12 8 16 10 3 6 0 9 13 15 5 17 2 14 1 11 4 2 3 13 16 4 1 7 5 6 9 10 8 17 12 14 11 0 15 8 9 13 6 4 15 7 12 11 1 14 5 17 0 3 16 10 2 6 2 0 4 16 10 8 3 9 7 1 12 5 11 15 17 13 14 6 16 10 0 1 11 17 7 9 15 5 12 13 2 14 8 3 4 7 13 5 16 3 6 15 8 4 9 12 10 17 14 2 0 1 11 8 12 13 16 4 11 7 0 17 9 15 2 6 10 14 1 5 3 3 0 4 12 2 10 8 16 15 9 11 5 17 7 13 14 1 6 10 2 13 8 16 0 15 5 6 1 11 7 4 9 12 3 14 17 5 16 7 1 4 3 15 0 9 12 2 14 17 11 8 13 10 6 2 7 5 8 1 15 17 12 9 11 10 0 4 16 14 13 3 6 15 9 6 16 0 10 7 3 17 11 14 5 4 8 13 12 1 2 0 15 3 14 1 4 7 2 10 17 8 5 6 13 11 16 9 12 nilai z terkecil tabu list sekarang = 5841.0 ***** Solusi sekarang ****** 6 2 13 17 4 10 0 16 15 9 1 7 14 11 5 12 3 8 dengan nilai Z = 5815.0 ====== iterasi - 549======== ***** Tabu List ****** 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 nilai z terkecil tabu list sekarang = 5981.0
Skripsi
Lampiran 3 - 18
= 5949.0 = 5964.0 = 5920.0 = 5986.0 = 6043.0 = 6165.0 = 5969.0 = 5907.0 = 6004.0 = 5943.0 = 6230.0 = 5920.0 = 6113.0 = 6123.0 = 6039.0 = 6026.0 = 6097.0 = 6101.0 = 5841.0 = 6020.0
= 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 19
***** Solusi sekarang ****** 7 14 15 13 6 5 17 9 0 10 11 16 2 12 1 4 8 3 dengan nilai Z = 5380.0 ====== iterasi - 550======== ***** Tabu List ****** 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 8 2 13 16 1 10 7 0 9 11 15 5 17 14 3 4 6 12 nilai z terkecil tabu list sekarang = 5981.0 ***** Solusi sekarang ****** 7 14 15 13 6 5 17 9 0 10 11 16 2 12 1 4 8 3 dengan nilai Z = 5380.0
= 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0 = 5981.0
!!!!!!!!!!! GA !!!!!!!!!! ==== iterasi- 1======== 7 14 15 13 6 5 17 9 0 10 11 16 2 12 1 4 8 3 5 14 6 0 15 7 13 11 3 10 9 16 2 12 1 4 8 17 7 14 15 13 4 6 5 17 9 0 10 11 16 2 12 1 8 3 3 11 15 13 6 5 17 9 0 1 2 14 8 7 10 12 16 4 13 0 7 14 3 15 6 1 4 11 5 17 10 8 2 9 12 16 10 4 11 1 16 8 2 12 17 9 7 6 3 14 13 5 0 15 2 12 1 11 6 0 8 17 15 9 7 3 13 14 5 16 4 10 10 9 7 8 1 12 17 2 16 11 5 6 15 3 14 13 0 4 2 17 11 8 7 16 9 3 0 12 15 5 13 14 6 1 10 4 1 3 13 15 17 6 8 4 5 14 2 9 16 10 12 7 0 11 2 12 14 11 4 15 7 17 6 10 16 5 1 13 9 0 3 8 3 10 2 12 11 5 16 4 14 1 9 6 17 0 7 8 13 15 2 12 8 10 11 5 16 4 14 1 9 6 17 0 3 13 7 15 5 6 10 9 1 0 8 3 16 7 13 15 17 14 4 12 11 2 3 10 2 12 11 5 16 4 14 1 9 6 17 7 8 13 15 0 0 9 8 15 14 6 3 1 4 11 5 17 10 12 13 2 7 16 12 6 7 17 14 16 5 13 1 15 8 0 4 9 10 3 11 2
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 20
0 14 8 16 10 4 3 13 17 1 11 7 2 12 6 9 15 5 4 9 1 3 13 10 2 11 17 12 0 14 16 6 5 7 8 15 6 16 10 1 14 8 2 13 17 9 4 5 12 3 11 7 0 15 2 12 14 11 8 10 17 0 5 15 6 16 1 13 9 7 3 4 0 5 4 12 1 3 13 10 6 16 9 17 2 14 8 15 7 11 13 5 7 14 3 15 10 8 9 0 17 6 4 2 12 11 1 16 8 15 16 12 17 9 1 11 10 7 6 3 2 0 14 13 4 5 8 15 16 12 17 9 1 11 10 7 6 3 2 0 14 13 4 5 8 15 16 12 17 9 1 11 10 7 6 3 2 0 14 13 4 5 12 2 17 11 8 7 16 9 3 0 15 5 13 14 6 1 10 4 6 0 10 1 11 8 2 12 17 9 7 3 13 14 5 16 4 15 17 9 6 0 15 7 13 11 8 3 1 2 14 5 10 12 16 4 11 8 2 10 9 17 16 7 5 13 3 0 14 4 6 15 1 12 11 13 3 16 10 12 4 9 0 7 15 17 6 5 1 2 8 14 4 2 12 13 16 8 10 17 0 5 15 6 3 1 14 9 11 7 16 9 6 12 8 13 5 4 3 11 2 0 17 14 15 1 7 10 1 9 0 7 16 10 12 4 2 8 11 5 6 15 3 14 13 17 12 2 8 10 17 16 7 5 3 0 15 9 13 14 6 1 11 4 ==== iterasi- 2======== 7 14 15 13 6 5 17 9 0 10 11 16 2 12 1 4 8 3 7 14 15 13 0 6 5 17 9 10 11 16 2 12 1 4 8 3 5 14 6 0 15 7 13 11 3 10 9 16 2 12 1 4 8 17 7 14 15 13 4 9 6 5 17 0 10 11 16 2 12 1 8 3 7 14 15 13 4 6 5 17 9 0 10 11 16 2 12 1 8 3 2 12 9 1 11 6 0 8 17 15 7 3 13 14 5 16 4 10 13 12 1 11 6 0 5 3 16 9 4 17 2 14 8 15 7 10 12 7 17 14 6 16 5 13 1 15 8 0 4 9 10 3 11 2 3 11 15 13 6 5 17 9 0 1 2 14 8 7 10 12 16 4 13 0 7 14 3 15 6 1 4 11 5 17 10 8 2 9 12 16 2 12 1 11 0 8 17 6 15 9 7 3 13 14 5 16 4 10 7 12 15 2 6 1 17 9 0 10 11 3 13 14 5 4 8 16 10 4 11 1 16 8 2 12 17 9 7 6 3 14 13 5 0 15 10 16 9 6 12 8 13 5 4 3 11 2 0 17 14 15 1 7 2 12 1 11 6 0 8 17 15 9 7 3 13 14 5 16 4 10 10 9 7 8 1 12 17 2 16 11 5 6 15 3 14 13 0 4 2 12 1 11 6 0 8 17 15 9 7 3 13 14 5 16 4 10 2 12 1 11 6 0 8 17 15 9 7 3 13 14 5 16 4 10 3 10 2 12 11 5 16 17 4 14 1 9 6 7 8 13 15 0 2 12 1 6 0 8 17 15 9 11 7 3 13 14 5 16 4 10 2 17 11 8 7 16 9 3 0 12 15 5 13 14 6 1 10 4 3 11 2 16 10 4 12 5 14 1 9 6 17 7 8 13 15 0 1 3 13 15 17 6 8 4 5 14 2 9 16 10 12 7 0 11 17 3 6 12 8 13 5 4 9 0 10 11 16 2 15 1 7 14 3 11 13 16 10 12 4 9 0 7 15 17 6 5 1 2 8 14 2 12 14 11 4 15 7 17 6 10 16 5 1 13 9 0 3 8 3 10 2 12 11 16 4 14 5 1 9 6 17 7 8 13 15 0 3 10 2 12 11 5 16 4 14 1 9 6 17 0 7 8 13 15 2 12 8 10 11 5 16 4 14 1 9 6 17 0 3 13 7 15 0 14 8 16 10 4 3 13 17 1 11 2 12 7 6 9 15 5 5 6 10 9 1 0 8 3 16 7 13 15 17 14 4 12 11 2
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 21
3 10 2 12 11 5 16 4 14 1 9 6 17 7 8 13 15 0 3 10 2 1 12 11 5 16 4 14 9 6 17 7 8 13 15 0 6 0 10 5 11 8 13 14 17 9 7 16 2 12 1 3 4 15 0 9 8 15 14 6 3 1 4 11 5 17 10 12 13 2 7 16 ==== iterasi- 549======== 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 ==== iterasi- 550======== 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 22
7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 ========== Pemilihan Solusi ========= 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 23
7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 = 5378.0 ==== Solusi ===== 7 14 15 13 6 5 17 9 0 10 11 16 1 12 4 2 8 3 Nilai z = 5378.0 ||||||||||||||||||||||||||||||||||||||||||||||||||| END |||||||||||||||||||||||||||||||||||||||||||||||||||
6.) Data 20 fasilitas dan 20 lokasi Parameter inputan jml_ant = 15 jml_lok = jml_fas = 20 alpha = 1 pop_size = 25 betha = 10 Pc = 0,65 phero_awal = 0,1 Pm = 0,15 rho = 0,9 max_iterasi = Q = 10 Output Nilai fungsi tujuan = 6946 satuan Kode solusi permasalahan adalah 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12
300
Runing !!!!!!!!!!! ACO !!!!!!!!!! ====== iterasi - 1======== ***** Tabu List ****** 10 13 0 12 16 18 2 17 5 3 1 11 9 14 4 6 7 15 8 19 19 15 8 13 4 1 3 2 16 0 10 17 11 12 6 5 7 18 14 9 6 2 18 17 8 12 7 5 1 9 16 19 15 13 3 4 10 14 0 11 11 8 6 7 17 15 12 10 4 13 18 19 16 14 5 0 3 1 2 9 14 17 2 16 15 6 3 18 10 19 0 13 7 12 11 5 8 4 1 9 1 5 12 16 7 9 2 17 18 3 10 8 15 11 19 6 0 13 14 4 6 3 18 5 16 14 7 1 19 10 9 15 13 8 0 12 2 11 17 4 14 13 5 15 1 19 18 6 3 4 12 2 11 9 10 0 8 17 16 7 8 3 7 4 6 0 5 19 12 13 2 9 16 15 11 1 14 18 10 17 6 2 16 19 5 10 7 3 14 15 17 4 0 18 11 1 12 13 8 9 19 9 4 7 10 15 17 6 18 1 0 11 12 8 13 14 16 5 3 2 6 18 9 17 19 3 1 12 5 2 10 13 14 11 4 15 0 7 8 16 5 2 9 0 11 8 7 19 12 10 18 15 14 4 3 17 16 6 13 1 0 6 17 11 18 13 2 15 14 12 4 3 1 9 7 19 5 10 16 8
Skripsi
= 7770.0 = 7974.0 = 8130.0 = 7918.0 = 7798.0 = 7784.0 = 7864.0 = 7624.0 = 7642.0 = 7804.0 = 7738.0 = 7872.0 = 7994.0 = 7780.0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 24
7 14 5 10 16 18 4 6 15 19 9 8 0 17 3 2 11 12 1 13 = 7532.0 nilai z terkecil tabu list sekarang = 7532.0 ***** Solusi sekarang ****** 7 14 5 10 16 18 4 6 15 19 9 8 0 17 3 2 11 12 1 13 dengan nilai Z = 7532.0 ====== iterasi - 2======== ***** Tabu List ****** 2 9 15 4 19 16 3 14 5 18 17 0 7 1 13 8 6 11 12 10 5 17 3 13 19 6 7 1 15 18 8 2 10 4 0 12 9 14 16 11 19 11 6 2 3 1 8 17 15 5 12 9 16 7 13 0 10 14 18 4 6 11 14 2 16 5 9 3 15 7 12 19 0 17 8 1 13 4 18 10 5 19 2 12 18 15 11 7 0 10 17 4 1 6 9 8 14 3 16 13 12 6 11 1 2 7 18 14 13 19 17 4 0 5 10 8 16 9 3 15 0 7 12 5 2 13 9 19 17 3 18 11 8 6 1 14 4 16 10 15 5 15 0 6 12 14 13 2 3 4 8 16 10 7 9 18 19 17 1 11 12 3 7 15 1 4 17 14 8 9 11 16 19 10 2 13 0 5 6 18 13 8 17 16 4 19 2 12 11 14 0 10 1 9 5 7 3 6 15 18 0 17 14 6 15 4 8 19 11 1 7 2 9 3 18 10 12 13 16 5 8 6 4 15 14 16 11 2 18 9 12 7 5 1 0 3 17 19 13 10 13 12 11 8 15 19 16 5 2 6 10 18 1 3 0 14 17 4 7 9 0 8 1 2 7 12 10 16 11 15 3 19 13 17 6 14 4 5 9 18 15 6 14 8 7 13 11 19 12 0 16 3 1 18 4 17 2 5 9 10 nilai z terkecil tabu list sekarang = 7648.0 ***** Solusi sekarang ****** 7 14 5 10 16 18 4 6 15 19 9 8 0 17 3 2 11 12 1 13 dengan nilai Z = 7532.0 ====== iterasi - 299======== ***** Tabu List ****** 8 12 16 10 0 1 6 18 14 7 11 17 19 3 2 5 15 9 4 13 2 12 16 10 11 1 15 4 14 18 13 6 19 3 17 8 5 0 7 9 7 12 16 4 0 8 9 5 13 18 10 17 6 3 14 2 15 11 19 1 8 12 2 4 0 1 9 5 19 7 6 10 11 3 14 13 15 18 16 17 8 12 13 4 0 1 6 5 19 7 11 15 16 3 14 2 10 18 17 9 8 12 16 10 11 1 9 17 19 7 14 6 4 15 2 5 13 18 3 0 3 12 16 10 0 1 9 18 13 7 11 17 19 15 14 5 8 2 4 6 7 12 2 14 0 1 15 19 13 18 6 8 4 3 17 9 16 10 11 5 8 3 2 4 11 1 9 5 14 18 13 15 16 10 6 7 12 0 17 19 2 12 13 4 0 1 15 17 19 7 6 16 11 3 18 9 5 14 10 8 7 12 16 10 11 1 15 5 17 4 14 8 19 3 2 13 6 9 18 0 7 12 18 10 11 1 15 19 13 17 6 8 4 3 2 5 16 9 0 14 8 12 16 4 0 1 9 19 17 13 11 6 10 3 2 7 5 18 15 14 19 12 2 10 0 8 9 4 11 7 14 15 13 3 17 5 16 18 6 1 7 3 2 10 0 1 15 19 14 18 11 8 4 9 17 5 16 13 6 12 nilai z terkecil tabu list sekarang = 7468.0 ***** Solusi sekarang ****** 7 14 0 5 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 7 14 5 0 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 dengan nilai Z = 6964.0
Skripsi
= 7988.0 = 7674.0 = 7722.0 = 7974.0 = 7648.0 = 7784.0 = 7810.0 = 7832.0 = 7708.0 = 7968.0 = 7854.0 = 7778.0 = 7912.0 = 7878.0 = 7986.0
= 7758.0 = 7610.0 = 7994.0 = 7818.0 = 7788.0 = 7768.0 = 7728.0 = 7568.0 = 7468.0 = 7646.0 = 7716.0 = 7570.0 = 7782.0 = 7752.0 = 7750.0
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
====== iterasi - 300======== ***** Tabu List ****** 7 3 2 4 11 1 9 5 17 18 14 15 10 19 12 13 16 0 6 8 14 12 2 5 0 1 15 19 17 4 11 8 6 3 18 9 10 13 16 7 7 12 2 10 0 1 15 17 19 18 6 8 5 3 14 13 4 9 16 11 7 12 16 18 11 1 9 17 19 4 10 13 5 3 14 8 0 15 6 2 7 12 16 4 11 1 9 19 13 18 14 10 6 3 2 17 5 0 15 8 7 12 2 5 11 1 9 4 13 18 10 17 19 3 6 16 15 0 14 8 8 12 2 6 0 1 15 5 14 18 10 13 4 3 17 16 19 9 7 11 7 12 16 5 0 19 6 4 14 18 15 8 13 3 2 9 10 17 11 1 7 12 16 10 0 1 9 5 17 18 6 8 4 15 14 13 19 2 3 11 7 12 2 10 0 1 9 14 11 18 6 8 4 3 17 5 19 16 15 13 8 3 16 4 0 13 9 18 14 7 10 17 19 15 2 5 12 6 11 1 19 12 2 10 0 1 9 14 13 18 15 8 5 3 6 16 7 11 17 4 7 12 16 10 0 1 9 5 14 18 11 15 19 3 2 17 13 6 4 8 8 12 2 4 0 1 14 5 17 18 11 13 16 3 6 9 10 19 7 15 8 12 2 10 0 1 9 14 19 18 6 7 16 3 4 17 5 13 15 11 nilai z terkecil tabu list sekarang = 7460.0 ***** Solusi sekarang ****** 7 14 0 5 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 7 14 5 0 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 dengan nilai Z = 6964.0
Lampiran 3 - 25
= 7594.0 = 7868.0 = 7460.0 = 7604.0 = 7628.0 = 7474.0 = 7932.0 = 7768.0 = 7726.0 = 7518.0 = 7764.0 = 7612.0 = 7514.0 = 7684.0 = 7812.0
!!!!!!!!!!! GA !!!!!!!!!! ==== iterasi- 1======== 7 14 0 5 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 7 14 5 0 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 7 18 14 5 0 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 14 7 1 12 9 4 10 11 15 17 18 13 5 19 16 2 3 8 6 0 16 15 0 6 18 14 19 13 7 17 12 9 8 4 1 2 5 10 11 3 16 15 0 6 18 1 14 19 13 7 17 12 9 8 4 2 5 10 11 3 16 15 0 6 5 14 2 13 7 17 12 9 8 1 4 19 18 10 11 3 5 6 1 9 19 3 11 10 17 13 0 8 4 7 2 12 14 15 18 16 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 5 2 18 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 5 2 18 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 5 2 18 8 9 15 4 10 19 2 6 12 1 3 16 5 7 11 18 17 0 13 14 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 2 5 18 19 11 7 1 12 9 4 10 16 5 3 17 0 18 6 8 14 15 2 13 16 18 1 12 2 19 15 5 10 8 13 11 6 0 4 3 9 7 17 14 7 12 9 17 10 11 16 1 14 0 5 19 4 15 3 18 13 6 8 2 9 14 17 5 2 8 12 7 19 6 16 11 13 18 4 1 15 3 10 0 1 11 12 4 10 9 13 7 6 0 15 14 19 8 16 17 3 5 2 18 7 13 9 8 14 17 11 19 15 3 5 10 18 1 6 16 4 2 12 0 4 7 12 17 6 11 10 15 8 18 14 2 19 5 3 13 9 16 1 0 9 15 4 2 1 8 5 13 14 19 12 11 7 0 18 10 3 17 6 16 9 15 4 2 8 5 13 14 19 12 1 11 7 0 18 10 3 17 6 16 7 13 9 8 14 17 11 19 15 3 5 10 18 1 6 16 4 2 0 12 13 1 6 12 17 11 19 18 8 3 0 10 7 15 5 2 16 14 4 9 10 15 19 12 5 16 2 4 17 18 6 1 0 11 3 8 14 7 13 9
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 26
==== iterasi- 2======== 7 14 0 5 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 7 14 5 0 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 7 18 14 5 0 16 13 11 15 17 9 10 1 19 4 2 3 8 6 12 14 7 1 12 9 4 10 11 15 17 18 13 5 19 16 2 3 8 6 0 14 7 1 12 9 4 10 11 15 2 17 18 13 5 19 16 3 8 6 0 16 15 0 6 18 14 19 13 7 17 12 9 8 4 1 2 5 10 11 3 7 12 9 17 10 11 16 1 14 0 5 19 4 15 13 18 3 8 6 2 16 15 0 6 18 1 14 19 13 7 17 12 9 8 4 2 5 10 11 3 16 15 0 6 5 14 2 13 7 17 12 9 8 1 4 19 18 10 11 3 9 15 19 18 1 5 11 10 17 13 0 8 4 7 2 12 14 3 6 16 5 6 1 9 19 3 11 10 17 13 0 8 4 7 2 12 14 15 18 16 8 6 1 9 4 17 5 13 14 19 12 11 7 0 18 10 3 15 2 16 1 13 11 12 4 10 9 7 0 6 15 14 19 8 16 17 3 5 2 18 7 12 19 9 17 10 11 16 1 14 0 5 4 15 3 18 13 6 8 2 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 5 2 18 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 5 2 18 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 5 2 18 19 17 6 3 12 9 4 8 16 5 1 11 7 0 18 10 14 15 2 13 8 9 15 4 10 19 2 6 12 1 3 16 5 7 11 18 17 0 13 14 16 15 0 6 18 19 13 7 17 12 9 8 4 1 2 5 14 10 11 3 1 13 11 12 10 4 9 7 6 0 15 14 19 8 16 17 3 2 5 18 5 6 1 9 19 3 10 17 13 0 8 4 7 2 12 14 11 15 18 16 1 13 11 12 4 10 9 7 6 0 15 14 19 8 16 17 3 2 5 18 7 12 14 5 0 18 16 13 11 15 17 9 10 1 19 4 2 3 8 6 14 7 1 12 9 4 10 11 15 17 18 3 5 19 16 2 13 6 8 0 ==== iterasi- 299======== 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 27
7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 ==== iterasi- 300======== 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 ========== Pemilihan Solusi ========= 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 3 - 28
7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 = 6946.0 ==== Solusi ===== 7 14 5 0 18 13 11 17 15 10 9 16 1 19 4 2 3 8 6 12 Nilai z = 6946.0 ||||||||||||||||||||||||||||||||||||||||||||||||||| END |||||||||||||||||||||||||||||||||||||||||||||||||||
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 4 - 1
Lampiran 4 : Output Program 1.) Input Parameter
2.) Help a.) usage
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 4 - 2
b.) Input
c.) Data
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN
ADLN - Perpustakaan Universitas Airlangga
Lampiran 4 - 3
d.) Intepretasi solusi
3.) Solusi
Skripsi
HYBRID ALGORITHM ANT COLONY...
MUHAMAD JAINAL ABIDIN