Download - PERBANDINGAN ALGORITMA GENETIKA DAN OPTIMASI … · KATA PENGANTAR Puji dan syukur ... Graph tak-berhingga (unlimited graf)..... 12 2.2.2.1.5. Graph berarah (directed graf atau

PERBANDINGAN ALGORITMA GENETIKA DAN OPTIMASI

KOLONI SEMUT DALAM MENYELESAIKAN TRAVELLING

SALESMAN PROBLEM

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer

Program Studi Teknik Informatika

Disusun oleh:

Alexander

135314114

PROGRAM STUDI TEKNIK INFORMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2018

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

THE COMPARISON OF GENETIC ALGORITHM AND ANT

COLONY OPTIMIZATION FOR SOLVING THE TRAVELLING

SALESMAN PROBLEM

Presented as Partial Fullfillment of the Requirements

To Obtain the Sarjana Komputer Degree

In Study Program of Informatics Engineering

Present by:

Alexander

135314114

INFORMATICS ENGINEERING STUDY PROGRAM

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2018


iii

SKRIPSI

PERBANDINGAN ALGORITMA GENETIKA DENGAN OPTIMASI


SALESMAN PROBLEM

Disusun oleh:

Alexander

135314114

Telah disetujui oleh:

Pembimbing,

Drs. Haris Sriwindono, M.Kom.

Tanggal: ………………….


iv

SKRIPSI



SALESMAN PROBLEM

Dipersiapkan dan ditulis oleh:

Alexander

NIM: 135314114

Telah dipertahankan didepan Dewan Penguji

Pada Tanggal: 27 Juli 2018

Dan dinyatakan memenuhi syarat

Susunan Dewan Penguji

Ketua : Paulina Heruningsih Prima Rosa, M.Sc. .……………..

Sekretaris : Agnes Maria Polina, S.Kom., M.Sc. ………………

Anggota : Drs. Haris Sriwindono, M.Kom. ………………

Yogyakarta, …… Agustus 2018

Fakultas Sains dan Teknologi

Universitas Sanata Dharma

Dekan,

Sudi Mungkasi, Ph.D.


v

MOTTO

“Segala sesuatu menjemukan, sehingga tak terkatakan oleh manusia; mata tidak

kenyang melihat, telinga tidak puas mendengar. Apa yang pernah ada akan ada

lagi, dan apa yang pernah dibuat akan dibuat lagi; tak ada sesuatu yang baru di

bawah matahari”

~Pengkotbah 1: 8-9


vi

HALAMAN PERSEMBAHAN

Segala hasil ini saya persembahkan kepada Allah, atas segala rahmat

dan berkat yang diberikan, sehingga semua dapat terselesaikan.

Kepada kedua Orang Tua saya, yang telah memberikan doa dan

dukungan semangat selama proses perkuliahan.

Kepada Doses-dosen Teknik Informatika Sanata Dharma, atas

bimbingan dari awal proses sampai akhir perkuliahan.

Kepada teman-teman Teknik Informatika Sanata Dharma angkatan

2013, terima kasih telah saling memberi semangat dan berjuang

bersama.


vii

PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa tugas akhir yang saya tulis

tidak mengandung atau memuat hasil karya orang lain, kecuali yang telah

disebutkan dalam daftar pustaka dan kutipan selayaknya karya ilmiah.

Yogyakarta, ………………...

Penulis,

Alexander


viii

LEMBAR PERNYATAAN PERSETUJUAN

PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN

AKADEMIS

Yang bertanda tangan dibawah ini, saya mahasiswa Universitas Sanata Dharma:

Nama : Alexander

Nomor Mahasiswa : 135314114

Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan

Universitas Sanata Dharma karya ilmiah saya yang berjudul:



SALESMAN PROBLEM

Dengan demikian saya memberikan kepada Perpustakaan Universitas Sanata

Dharma hak untuk menyimpan, mengalihkan dalam bentuk media lain,

mengolahnya dalam bentuk pangkalan data, mendistribusikan secara terbatas, dan

mempublikasikannya di Internet atau media lain untuk kepentingan akademis tanpa

perlu meminta ijin dari saya maupun memberikan royalti kepada saya selama tetap

mencantumkan nama saya sebagai penulis.

Demikian pernyataan ini saya buat dengan sebenarnya.

Yogyakarta, …………………

Yang menyatakan,

Alexander


ix

INTISARI

Travelling Salesman Problem selanjutnya disingkat TSP, adalah persoalan

NP-hard yang seringkali diterapkan dalam berbagai aplikasi. TSP adalah sebuah

permasalahan polynomial, sehingga pemecahan solusi terbentuk secara

eksponensial. Salah satu cara efektif untuk memecahkan masalah NP-hard adalah

dengan merancang algoritma metaheuristic yang efisien seperti algoritma genetika,

optimasi koloni semut, dan lain-lain.

Perbandingan antara GA dan ACS menggunakan data TSP asimetrik yang

disimpan dalam berkas bereksistensi .txt dengan variasi 10, 20, 30, 40, 50, 60, 70,

80, 90, dan 100 kota. Masing-masing data diuji sebanyak 10 kali terhadap masing-

masing algoritma dan diperoleh jarak rata-rata, jarak terdekat, waktu rata-rata,

waktu tercepat, memori rata-rata, dan memori tersedikit. Hasil pengujian

menunjukkan algoritma ACS lebih konsisten dibandingkan algoritma genetika

yang nilainya bervariasi, ACS mampu menemukan solusi berupa jarak yang lebih

pendek dibandingkan algoritma genetika, dan untuk data di atas 20 buah kota

algoritma genetika secara rata-rata memproses data lebih cepat dan menggunakan

memori yang lebih sedikit dibandingkan rata-rata hasil algoritma ACS.

Kata Kunci: Travelling Salesman Problem, Algorima Genetika, GA, Ant

Colony Optimization, ACO, Ant Colony System, ACS.

Algoritma Genetika (GA) telah menjadi popular sebagai sarana pemecahan

masalah optimasi kombinatorial yang kompleks. Dengan susunan kromosom dalam

populasi dan rangkaian gen dalam satu kromosom, di mana satu kromosom

mewakili satu solusi yang berarti dalam satu populasi terdapat berbagai solusi yang

menjadikan GA lebih efisien jika dibandingkan algoritma polynomial atau secara

brute-force. Optimasi koloni semut (ACO) adalah metaheuristic yang digunakan

untuk menyelesaikan masalah optimasi kombinatorial yang kompleks. Ant System

(AS) adalah algoritma ACO yang dirancang khusus untuk menyelesaikan

permasalahan TSP. Lebih jauh, AS dikembangkan lagi menjadi beberapa algoritma

baru dan salah satunya adalah Ant Colony System (ACS).


x

ABSTRACT

Traveling Salesman Problem hereinafter abbreviated as TSP, is a NP-hard

problem that is often applied in various applications. TSP is a polynomial problem,

so solution solving is formed exponentially. One way to solve an NP-hard problem

is designing an efficient metaheuristic algorithm such as genetic algorithms, ant

colony optimization, etc.

The Genetic Algorithm (GA) has become popular as a means of solving hard

combinatorial optimization problems (NP-hard). With the arrangement of

chromosomes in a population and gene sequences on a single chromosome, which

one chromosome represents one meaningful solution that make GA more efficient

than polynomial or brute-force algorithms. Ant Colony Optimization (ACO) is a

metaheuristic for solving hard combinatorial optimization problems (NP-hard).

Ant System (AS) is the first ACO algorithm, specially designed to solve TSP

problems and in times developed again into several new algorithms, and one of

them is Ant Colony System (ACS).

The comparison between GA and ACS uses asymmetric TSP data, has stored

in .txt existential files with a kind of variations of 10, 20, 30, 40, 50, 60, 70, 80, 90,

and 100 cities. Each data was tested 10 times for each algorithm and obtained

average distance, shortest distance, average time, fastest time, average memory,

and least memory. The test results showed that ACS is more consistent than the GA

whose value varies, ACS was able to find a solution of shorter distance than the

genetic algorithm, and for the data over than 20 cities the genetic algorithm in

average processing is faster and uses less memory than the ACS algorithm.

Keywords: Travelling Salesman Problem, Genetic Algorithms, GA, Ant

Colony Optimization, ACO, Ant Colony System, ACS.


xi

KATA PENGANTAR

Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa karena

atas rahmat dan karunia-Nya, penulis dapat menyelesaikan Tugas Akhir yang

berjudul “PERBANDINGAN ALGORITMA GENETIKA DENGAN OPTIMASI

KOLONI SEMUT DALAM MENYELESAIKAN TRAVELLING SALESMAN

PROBLEM” ini dengan baik.

Dalam proses penulisan tugas akhir ini penulis menyadari bahwa ada begitu

banyak pihak yang turut memberikan motivasi semangat dan juga bantuan dalam

menyelesaikan tugas akhir ini, oleh karena itu saya ingin mengucapkan terima kasih

antara lain kepada:

1. Bapak Sudi Mungkasi, Ph.D. selaku Dekan Fakultas Sains dan Teknologi.

2. Ibu Dr. Anastasia Rita Widiarti, selaku Kepla Prodi Teknik Informatika.

3. Ibu P.H Prima Rosa, M.Sc. sebagai dosen pembimbing akademik, yang

telah memberikan bimbingan dan saran selama penulis menempuh studi.

4. Drs. Haris Sriwindono, M.Kom. selaku dosem pembimbing skripsi yang

telah memberikan kesabaran, waktu dan saran sehingga dapat

diselesaikannya tugas akhir ini.

5. Seluruh dosen yang telah mendidik dan memberikan pengetahuan dan

pengalaman berharga selama penulis belajar di Universitas Sanata Dharma

Yogyakarta.

6. Orang tua, kakak dan kerabat yang telah memberikan kasih sayang,

perhatian, doa dan dukungan sehingga penulis dapat menyelesaikan tugas

akhir.

7. Teman-teman kos pentagon, Vrengki, Adrian, dan Arga selaku teman

seperjuangan.

8. Pipin, Novan, Rudi, Aldi, Bang Hendri, dan Bang Leo, sebagai teman curhat

dan teman diskusi sekaligus teman terbaik selama penulis menempuh

pendidikan di Yogyakarta.

9. Seluruh teman-teman angkatan 2013 untuk kebersamaan kita menjalani

masa-masa perkuliahan.


xii

10. Teman-teman forum FOKUS MAPAWI.

11. Adriana Fitri yang selalu setia mendukung dan memberi semangat dan

motivasi dalam pengerjaan skripsi ini.

Penulis menyadari bahwa penulisan tugas akhir ini masih perlu dikembangkan lebih

lanjut. Untuk itu penulis sangat membutuhkan kritik dan saran yang bersifat

membangun untuk perbaikan dimasa mendatang. Semoga penulisan tugas akhir ini

dapat bermanfaat dan berguna bagi semua pihak.

Yogyakarta, …………..

Penulis


xiii

DAFTAR ISI

JUDUL…………………………………………………………………………….i

TITLE……………………………………………………………………………..ii

MOTTO .................................................................................................................. v

HALAMAN PERSEMBAHAN ............................................................................ vi

PERNYATAAN KEASLIAN KARYA ............................................................... vii

LEMBAR PERNYATAAN PERSETUJUAN .................................................... viii

PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS ........ viii

INTISARI ............................................................................................................... ix

ABSTRACT .............................................................................................................. x

KATA PENGANTAR ........................................................................................... xi

DAFTAR ISI ........................................................................................................ xiii

DAFTAR GAMBAR ........................................................................................... xxi

DAFTAR TABEL .............................................................................................. xxiv

DAFTAR LAMPIRAN ...................................................................................... xxvi

BAB I PENDAHULUAN .................................................................................. 1

1.1. Latar Belakang Masalah .......................................................................... 1

1.2. Rumusan Masalah ................................................................................... 2

1.3. Tujuan Penelitian .................................................................................... 2

1.4. Batasan Masalah...................................................................................... 2

1.5. Manfaat Penelitian .................................................................................. 3

1.6. Desain Penelitian ..................................................................................... 3

1.7. Metode Penelitian.................................................................................... 4

1.8. Prosedur Penelitian.................................................................................. 4

1.9. Sistematika Penulisan ............................................................................. 5


xiv

BAB II LANDASAN TEORI .............................................................................. 7

2.1. Penelitian Terdahulu yang Relevan ........................................................ 7

2.2. Kajian Teori ............................................................................................ 8

2.2.1. Analisis Algoritma Secara Umum .................................................... 8

2.2.2. Teori Graph ....................................................................................... 9

2.2.2.1. Jenis-jenis graph ...................................................................... 10

2.2.2.1.1. Graph sederhana (Simple graf) ........................................... 10

2.2.2.1.2. Graph tak-sederhana (unsimple-graf/multigraf) ................. 11

2.2.2.1.3. Graph berhingga (limited graf) ........................................... 12

2.2.2.1.4. Graph tak-berhingga (unlimited graf) ................................ 12

2.2.2.1.5. Graph berarah (directed graf atau digraf) .......................... 12

2.2.2.1.6. Graph tak-berarah (undirected graf) .................................. 12

2.2.2.2. Graph berbobot ........................................................................ 12

2.2.2.3. Graph lengkap .......................................................................... 13

2.2.2.4. Keterhubungan antar titik ........................................................ 13

2.2.3. Traveling Salesman Problem .......................................................... 14

2.2.4. Algoritma Genetika ......................................................................... 15

2.2.4.1. Konsep yang mendasari ........................................................... 15

2.2.4.2. Alur Algoritma Genetika ......................................................... 16

2.2.4.3. Populasi .................................................................................... 17

2.2.4.4. Evaluasi nilai fitness ................................................................ 18

2.2.4.5. Crossover (Kawin-Silang) ....................................................... 18

2.2.4.6. Mutasi ...................................................................................... 19

2.2.4.7. Seleksi Individu ....................................................................... 19

2.2.4.7.1. Roda Roulette ..................................................................... 20


xv

2.2.4.7.2. Rangking ............................................................................ 20

2.2.4.7.3. Turnamen ............................................................................ 21

2.2.5. Algoritma Koloni Semut ................................................................. 21

2.2.5.1. Konsep yang mendasari ........................................................... 21

2.2.5.2. Model dan Teori Algoritma ACO ............................................ 23

2.2.5.3. Ant System (AS) dan Turunan Langsungnya .......................... 25

2.2.5.3.1. Ant System (AS) ................................................................ 25

2.2.5.3.2. Elitist Ant System (EAS) ................................................... 28

2.2.5.3.3. Rank-Based Ant System (ASRank) ...................................... 29

2.2.5.3.4. MAX-MIN Ant System (MMAS) ...................................... 29

2.2.5.4. Ant Colony System (ACS) Sebagai Ekstensi Dari Algoritma

Ant System (AS) ....................................................................................... 31

2.2.5.4.1. Aturan transisi status .......................................................... 32

2.2.5.4.2. Update Global Pheromone ................................................. 32

2.2.5.4.3. Pheromone Lokal ............................................................... 33

2.2.5.5. Alur algoritma ACS ................................................................. 34

BAB III ANALISIS DAN PERANCANGAN ................................................... 36

3.1. Analisis Sistem ...................................................................................... 36

3.1.1. Gambaran Umum ............................................................................ 36

3.1.2. Kebutuhan Pembangunan Sistem .................................................... 36

3.1.2.1. Perangkat keras ........................................................................ 36

3.1.2.2. Perangkat lunak........................................................................ 37

3.2. Analisis Permasalahan .......................................................................... 37

3.3. Algoritma Genetika untuk Travelling Salesman Problem .................... 37

3.3.1. Pembentukan Populasi Awal........................................................... 37


xvi

3.3.2. Fitness ............................................................................................. 38

3.3.3. Seleksi ............................................................................................. 40

3.3.4. Crossover ........................................................................................ 42

3.3.5. Mutasi .............................................................................................. 43

3.4. Ant Colony System (ACS) untuk Travelling Salesman Problem .......... 44

3.4.1. Parameter Pendukung...................................................................... 44

3.4.1.1. Matriks Nearest-Neighbor ....................................................... 44

3.4.1.2. Rute Inisial ............................................................................... 44

3.4.1.3. Matriks Pheromone .................................................................. 45

3.4.2. Konstruksi Solusi ............................................................................ 46

3.4.3. Perbaharuan ..................................................................................... 47

3.4.4. Kondisi diakhiri ..................................................................................... 47

3.5. Rancangan Pengujian Sistem ................................................................ 47

BAB IV IMPLEMENTASI DAN PENGUJIAN ................................................ 49

4.1. Java Virtual Machine (JVM) Runtime .................................................. 49

4.2. Waktu Olah Sistem ............................................................................... 49

4.3. Implementasi Genetika.......................................................................... 50

4.3.1. Class Kromosom ............................................................................. 50

4.3.1.1. Ringkasan Metode ................................................................... 50

4.3.1.2. Detail Metode .......................................................................... 51

4.3.1.2.1. bersikanKromosom() .......................................................... 51

4.3.1.2.2. bangkitkanKromosom(int sizeKromosom) ........................ 51

4.3.1.2.3. fittnessKromosom(double graph[][]) ................................. 51

4.3.1.2.4. jarakTotalKromosom(double graph[][]) ............................. 51

4.3.2. Class Populasi ................................................................................. 51


xvii


4.3.2.2. Detail Metode .......................................................................... 53

4.3.2.2.1. fitnessPopulasi(double graph[][]) ....................................... 53

4.3.2.2.2. fittestPopulasi(double graph[][]) ........................................ 53

4.3.2.2.3. flacidPopulasi(Populasi pop, double graph[][]) ................. 53

4.3.2.2.4. probKromosom(Kromosom kromosom, double totFittness,

double graph[][]) ................................................................................... 53

4.3.2.2.5. ProbKomulatif(int index,double graph[][]) ........................ 54

4.3.2.2.6. rodaRoulete(double graph[][]) ........................................... 54

4.3.2.2.7. xo_DO(Kromosom p1, Kromosom p2) .............................. 54

4.3.2.2.8. mutasi(Kromosom parent) .................................................. 54

4.3.3. Class Genetika ................................................................................. 55


4.3.3.2. Detail Metode .......................................................................... 55

4.3.3.2.1. run_genetika(double graph[][]) .......................................... 55

4.3.3.2.2. bangkitkanPopulasi(int ukuranKromosome, int

ukuranPopulasi) .................................................................................... 55

4.4. Implementasi ACS ................................................................................ 56

4.4.1. Class Ant ......................................................................................... 56


4.4.1.2. Detail Metode .......................................................................... 56

4.4.1.2.1. clear() .................................................................................. 56

4.4.1.2.2. getTourLength(double Graph[][]) ...................................... 57

4.4.2. Class ACS ....................................................................................... 57



xviii

4.4.2.2. Detail Metode .......................................................................... 59

4.4.2.2.1. run_colony(double Graph[][]) ............................................ 59

4.4.2.2.2. prepare_allVariablesAndParams(double Graph[][]) .......... 59

4.4.2.2.3. prepareNearestNeighbour(double[][] Graph) ..................... 59

4.4.2.2.4. compute_initial_trail() ........................................................ 60

4.4.2.2.5. preparePheromoneTrail() ................................................... 60

4.4.2.2.6. heuristic_information(double[][] Graph) ........................... 60

4.4.2.2.7. choice_info(double[][] Graph) ........................................... 60

4.4.2.2.8. init_ants() ............................................................................ 60

4.4.2.2.9. constructSolution() ............................................................. 61

4.4.2.2.10. choose_and_move_to_next(Ant ant, int step) .................. 61

4.4.2.2.11. choose_best_next(Ant ant, int step) ................................. 61

4.4.2.2.12. pseudo_rand_proportional_rule(Ant ant, int step) ........... 61

4.4.2.2.13. nn_choose_and_move_to_the_next(Ant ant, int step) ..... 62

4.4.2.2.14. local_pheromone_update(Ant ant, int step) ..................... 62

4.4.2.2.15. update_initial_trail() ......................................................... 62

4.4.2.2.16. pheromone_evaporation()................................................. 62

4.4.2.2.17. global_pheromone_update() ............................................. 63

4.5. Genetika Untuk TSP ............................................................................. 63

4.5.1. Kromosom ....................................................................................... 63

4.5.2. Populasi ........................................................................................... 65

4.5.3. Fitness ............................................................................................. 66

4.5.4. Probabilitas kromosom ................................................................... 71

4.5.5. Probabilitas komulatif ..................................................................... 72

4.5.6. Seleksi Roullete ............................................................................... 74


xix

4.5.7. Crossover XO .................................................................................. 76

4.5.8. Mutasi .............................................................................................. 78

4.6. ACS Untuk TSP .................................................................................... 79

4.6.1. Matriks Nearest-Neighbor ............................................................... 79

4.6.2. Rute inisial ...................................................................................... 80

4.6.3. Pheromone ...................................................................................... 81

4.6.4. Informasi heuristic .......................................................................... 82

4.6.5. Phermone lokal................................................................................ 83

4.6.6. Konstruksi Solusi ............................................................................ 84

4.6.7. Penguapan pheromone .................................................................... 87

4.6.8. Pheromone global............................................................................ 87

4.7. Pengujian Algoritma Genetika .............................................................. 88

4.7.1. 10 Kota ............................................................................................ 89

4.7.2. 20 Kota ............................................................................................ 89

4.7.3. 30 Kota ............................................................................................ 90

4.7.4. 40 Kota ............................................................................................ 91

4.7.5. 50 Kota ............................................................................................ 92

4.7.6. 60 Kota ............................................................................................ 93

4.7.7. 70 Kota ............................................................................................ 94

4.7.8. 80 Kota ............................................................................................ 95

4.7.9. 90 Kota ............................................................................................ 96

4.7.10. 100 Kota ...................................................................................... 97

4.8. Pengujian ACS ...................................................................................... 98

4.8.1. 10 Kota ............................................................................................ 98

4.8.2. 20 Kota ............................................................................................ 99


xx

4.8.3. 30 Kota .......................................................................................... 100

4.8.4. 40 Kota .......................................................................................... 101

4.8.5. 50 Kota .......................................................................................... 102

4.8.6. 60 Kota .......................................................................................... 103

4.8.7. 70 Kota .......................................................................................... 104

4.8.8. 80 Kota .......................................................................................... 105

4.8.9. 90 Kota .......................................................................................... 106

4.8.10. 100 Kota .................................................................................... 107

4.9. Pembandingan Algoritma.................................................................... 108

4.9.1. Jarak .............................................................................................. 108

4.9.2. Waktu ............................................................................................ 111

4.9.3. Memori .......................................................................................... 113

BAB V PENUTUP ........................................................................................... 115

5.1. Kesimpulan ......................................................................................... 115

5.2. Saran .................................................................................................... 115

DAFTAR PUSTAKA ......................................................................................... 116

LAMPIRAN ........................................................................................................ 118


xxi

DAFTAR GAMBAR

Gambar 1.1 Desain Penelitian ......................................................................... 4

Gambar 2.1 Contoh Graph.............................................................................. 10

Gambar 2.2 Contoh Graph Sederhana ............................................................ 11

Gambar 2.3 Contoh Graph Tidak Sederhana.................................................. 11

Gambar 2.4 Contoh Graph Berarah ................................................................ 12

Gambar 2.5 Contoh Graph Berbobot .............................................................. 13

Gambar 2.6 Contoh graph lengkap 𝐾𝑛 dengan 1 ≤ n ≤ 6 ............................... 13

Gambar 2.7 Prosedur Algoritma Genetika ..................................................... 17

Gambar 2.8. Populasi dalam Algoritma Genetika .......................................... 17

Gambar 2.9 Fitness Populasi .......................................................................... 18

Gambar 2.10 Kromosom Crossover ............................................................... 18

Gambar 2.11 Mutasi Kromosom .................................................................... 19

Gambar 2.12 Contoh Seleksi Roda Roulette .................................................. 20

Gambar 2.13 Contoh Jalur Perjalanan Semut ................................................. 23

Gambar 2.14 Prosedur ACO ........................................................................... 24

Gambar 2.15 Prosedur ACS ........................................................................... 35

Gambar 3.1 Roda Roullete ............................................................................. 41

Gambar 4.1 Kode Kromosom ......................................................................... 63

Gambar 4.2 Uji Metode Pembentukan Kromosom ........................................ 64

Gambar 4.3 Kode Populasi Awal ................................................................... 65

Gambar 4.4 Populasi Awal Hasil Uji Sistem ................................................. 66

Gambar 4.5 Kode Fitness Kromosom ............................................................ 66


xxii

Gambar 4.6 Hasil Uji Fitness Kromosom ...................................................... 67

Gambar 4.7 Kode Fittest Populasi .................................................................. 68

Gambar 4.8 Hasil Uji Fittest Populasi ............................................................ 69

Gambar 4.9 Kode Flaccid Populasi ................................................................ 70

Gambar 4.10 Hasil Uji Flaccid Populasi ........................................................ 71

Gambar 4.11 Kode Probabilitas Kromosom ................................................... 72

Gambar 4.12 Hasil Uji Probabilitas Kromosom ............................................. 72

Gambar 4.13 Kode Probabilitas Komulatif .................................................... 73

Gambar 4.14 Kode Roda Roullete .................................................................. 74

Gambar 4.15 Hasil Uji Roda roullete ............................................................. 76

Gambar 4.16 Hasil Pengujian Crossover ........................................................ 76

Gambar 4.17 Kode Crossover ........................................................................ 77

Gambar 4.18 Kode Mutasi.............................................................................. 78

Gambar 4.19 Hasil Uji Mutasi ........................................................................ 78

Gambar 4.20 Kode Matriks Nearest-Neighbor ............................................... 79

Gambar 4.21 Hasil Uji Matiks Nearest-Neigbor ............................................ 79

Gambar 4.22 Kode Rute Inisial ...................................................................... 80

Gambar 4.23 Hasil Uji Rute Inisial ................................................................ 81

Gambar 4.24 Kode Pheromone Inisial ........................................................... 82

Gambar 4.25 Hasil Uji Pheromone Awal ....................................................... 82

Gambar 4.26 Kode Matriks Heuristic............................................................. 83

Gambar 4.27 Kode Perbaharuan Phermone Lokal ......................................... 84

Gambar 4.28 Kode Konstruksi Solusi ............................................................ 85


xxiii

Gambar 4.29 Kode Metode choose_and_move_to_next(Ant, int) ................. 85

Gambar 4.30 Kode Metode choose_best_next(Ant, int) ................................ 86

Gambar 4.31 Kode Random Proportional Rule.............................................. 86

Gambar 4.32 Kode Pencarian Tetangga Terdekat .......................................... 87

Gambar 4.33 Kode Penguapan Pheromone .................................................... 87

Gambar 4.34 Kode Pembaharuan Rute Inisial ............................................... 88

Gambar 4.35 Kode Pembaharuan Pheromone Global .................................... 88

Gambar 4.36 Grafik hasil rata-rata jarak ...................................................... 109

Gambar 4.37 Grafik hasil jarak minimal ...................................................... 109

Gambar 4.38 Grafik hasil perbandingan jarak 40 buah kota ........................ 110

Gambar 4.39 Grafik hasil waktu rata-rata .................................................... 111

Gambar 4.40 Grafik hasil waktu minimal .................................................... 111

Gambar 4.41 Grafik hasil perbandingan waktu proses 40 buah kota ........... 112

Gambar 4.42 Grafik hasil memori rata-rata .................................................. 113

Gambar 4.43 Grafik hasil memori minimal .................................................. 113

Gambar 4.44 Grafik hasil perbandingan konsumsi memori 40 buah kota ... 114


xxiv

DAFTAR TABEL

Tabel 3.1 Fitness Tanpa Pembagian .............................................................. 39

Tabel 3.2 Fitness Dengan Pembagian ............................................................. 39

Tabel 3.3 Probabilitas Komulatif Seleksi Roullete ........................................ 41

Tabel 3.4 Rancangan pengujian sistem .......................................................... 48

Tabel 4.1 Metode Class Runtime ................................................................... 49

Tabel 4.2 Ringkasan Metode Dalam Class Kromosom .................................. 50

Tabel 4.3 Ringkasan Metode Dalam Class Populasi ...................................... 52

Tabel 4.4 Ringkasan Metode Dalam Class Genetika ..................................... 55

Tabel 4.5 Ringkasan Metode Dalam Class Ant .............................................. 56

Tabel 4.6 Ringkasan Metode Dalam Class ACS ............................................ 57

Tabel 4.7 Data Masukan 5 Kota ..................................................................... 68

Tabel 4.8 Pengurutan Kromosom Hasil Uji Fittest Populasi.......................... 70

Tabel 4.9 Hasil Uji Probabilitas Komulatif .................................................... 73

Tabel 4.10 Bilah Roda Roullete ..................................................................... 75

Tabel 4.11 Ketetanggaan Lima Kota .............................................................. 80

Tabel 4.12 Pengujian Algoritma Genetika TSP 10 Kota ................................ 89








xxv



Tabel 4.21 Pengujian Algoritma Genetika TSP 100 Kota .............................. 98

Tabel 4.22 Pengujian Algoritma Genetika ACS 10 Kota ............................... 99

Tabel 4.23 Pengujian Algoritma Genetika ACS 20 Kota ............................. 100








Tabel 4.31 Pengujian Algoritma Genetika ACS 100 Kota ........................... 108

Tabel 4.32 Perbandingan Jarak Untuk Data 40 Kota ................................... 110

Tabel 4.33 Perbandingan Waktu Untuk Data 40 Kota ................................. 112

Tabel 4.34 Perbandingan Konsumsi Memori Untuk Data 40 Kota .............. 114


xxvi

DAFTAR LAMPIRAN

Lampiran 1: Kode Program Algoritma Genetika Class Kromosom .............118

Lampiran 2: Kode Program Algoritma Genetika Class Populasi .................120

Lampiran 3: Kode Program Algoritma Genetika Class Genetika .................126

Lampiran 4: Kode Program Algoritma ACS Class Ant ................................131

Lampiran 5: Kode Program Algoritma ACS Class ACS ..............................133

Lampiran 6: Kode Program Class Param ......................................................143

Lampiran 7: Kode Program Class Main........................................................145


1

BAB I

PENDAHULUAN

1.1. Latar Belakang Masalah

Traveling Salesman Problem (TSP) merupakan sebuah permasalahan

optimasi yang terkenal dan menjadi standar untuk mencoba algoritma yang

komputasional. TSP sendiri cukup banyak diaplikasikan di dunia nyata. Pokok

permasalahan dari TSP adalah seorang salesman harus mengunjungi sejumlah kota,

dengan jarak antar kota sudah diketahui sebelumnya. Semua kota yang ada harus

dikunjungi dan harus mengoptimalkan biaya perjalanan. Masing-masing kota hanya

boleh dikunjungi satu kali dan harus kembali ke kota asal keberangkatan. Biaya

perjalanan yang menjadi pertimbangan salesman tersebut dapat berupa jarak,

waktu, bahan bakar, kenyamanan, dan sebagainya.

Berbagai metode diterapkan untuk menangani permasalahan TSP. Metode

tersebut terbagi menjadi dua, yaitu metode konvensional dan metode heuristic.

Metode konvesional adalah metode dengan perhitungan matematis biasa,

sedangkan metode heuristic adalah metode yang diterapkan dengan perhitungan

kecerdasan buatan. Algoritma Genetika (GA), Optimasi Koloni Semut (ACO),

Particle Swarn Optimation (PSO), dan Soccer Games Optimation (SGO), adalah

beberapa contoh algoritma metode heuristic untuk optimasi.

Algoritma genetika adalah algoritma yang banyak digunakan untuk

mengatasi permasalahan-permasalahan optimasi yang kompleks. Algoritma ini

mengadopsi konsep evolusi makhluk hidup dan seleksi alam dalam ilmu Biologi, di

mana individu yang tidak mampu beradaptasi akan tersingkirkan secara alami.

Secara dangkalnya, algoritma genetika digunakan untuk membangun solusi terbaik

dari sekian banyak solusi yang sudah ada sebelumnya.

Algoritma optimasi koloni semut adalah algoritma yang mengadopsi perilaku

semut. Secara alamiah, semut mampu menemukan rute perjalanan dari sumber

makanan menuju sarang atau sebaliknya. Semut-semut dalam koloni, mampu

menemukan rute perjalanan berdasarkan jejak kaki sebagai tanda khusus pada jalur


2

yang telah dilewati sebelumnya. Semakin banyak anggota koloni yang melewati

jalur, maka semakin jelas bagi anggota koloni untuk mengenali jalur sebelumnya.

Sebagai algoritma optimasi, algoritma koloni semut adalah algoritma yang

dirancang khusus untuk menyelesaikan persoalan pencarian jalur.

Dari penjelasan singkat di atas, untuk mengetahui metode yang paling

optimal dan efisien dalam menyelesaikan permasalahan TSP, peneliti memandang

perlu adanya suatu pembandingan. Perbandingan tersebut untuk mengetahui hasil

optimasi algoritma pemrograman dengan metode heuristic. Untuk itu, peneliti

merumuskan penelitian berjudul “Perbandingan algoritma genetika dan optimasi

koloni semut dalam menyelesaikan permasalahan travelling salesman problem”.

1.2. Rumusan Masalah

Berdasarkan uraian latar belakang di atas, peneliti merumuskan permasalahan

sebagai berikut:

“Di antara algoritma genetika dan algoritma optimasi koloni semut, algoritma

manakah yang lebih baik dalam hal pencarian jarak traveling, lebih minimal dalam

hal penggunaan memori dan lebih cepat dalam hal durasi proses, jika dihadapkan

dengan persoalan Travelling Salesman Problem?”

1.3. Tujuan Penelitian

Berdasarkan rumusan masalah di atas, maka dibuatlah penelitian ini dengan

tujuan:

1. Mendapatkan perbandingan harga optimum berupa jarak traveling dari

kedua algoritma.

2. Mendapatkan perbandingan waktu (durasi) olah sistem dari kedua

algoritma.

3. Mendapatkan perbandingan konsumsi memori pada kedua algoritma.

1.4. Batasan Masalah

Peneliti memfokuskan pada beberapa hal, yaitu:

1. Data yang digunakan dalam penelitian adalah matriks jarak untuk

Assymetric Travelling Salesman Problem berupa berkas bereksistensi


3

teks.

2. Dalam algoritma genetika, metode crossover yang digunakan adalah

order crossover (OX) dan metode mutasi yang diterapkan adalah

reciprocal exchange.

3. Dalam optimasi koloni semut, algoritma yang digunakan adalah Ant

Colony System (ACS).

4. Pengujian menggunakan variasi data dengan 10, 20, 30, 40, 50, 60, 70,

80, 90, dan 100 buah kota atau titik.

5. Dalam pengujian, faktor pembanding yang digunakan selalu sama untuk

setiap data yang diuji.

6. Ukuran yang digunakan sebagai pembanding kedua algoritma adalah

jarak traveling, waktu/durasi olah sistem, dan besar konsumsi memori.

1.5. Manfaat Penelitian

Penelitian ini diharapkan dapat memberikan manfaat bagi mahasiswa dan

peneliti lain.

1. Bagi Mahasiswa

Membantu menambah wawasan dan memperluas pengetahuan tentang

algoritma, khususnya kedua algoritma yang digunakan dalam penelitian

ini.

2. Bagi Peneliti Lain

Sebagai bentuk sumbangan terhadap penelitian lainnya agar dapat

mengembangkan penelitian lebih lanjut, berkaitan dengan masalah

perbandingan algoritma.

1.6. Desain Penelitian

Desan penelitian merupakan langkah awal yang akan dilakukan dalam

penelitian ini. Gambar 1.1 di bawah menunjukan alur penelitian yang dilakukan.


4

Gambar 1.1. Desain Penelitian

1.7. Metode Penelitian

Metode penelitian yang diterapkan sebagai berikut:

1. Pengumpulan data

Penelitian ini menerapkan metode studi kepustakaan sebagai metode

dalam pengumpulan data dan informasi. Peneliti mempelajari dokumen,

gambar, buku, dan lain-lain, yang berkaitan dengan teori dan penerapan

TSP, algoritma genetika, dan algoritma ACO.

2. Metodologi pembangunan sistem

Untuk metodologi pembangunan sistem, peneliti menggunakan

paradigma pengembangan metode waterfall karena metode ini

mempunyai tahapan pengembangan yang terstruktur. Tahap

pengembangan yang bertahap dimulai dari analisa sistem, dilanjutkan

dengan perancangan proses dan perancangan prosedur kerja,

implementasi hasil perancangan, pengujian dan pemeliharaan. Waterfall

juga memungkinkan untuk dilakukannya ulas ulang terhadap tahapan

yang telah dilakukan.

1.8. Prosedur Penelitian

Prosedur penelitian yang dilakukan mengikuti metodologi pengembangan

sistem, yakni meliputi lima tahapan yang akan diuraikan sebagai berikut:

1. Tahap analisis

Tahap analisis terbagai atas tiga bagian. Pertama, analisis terhadap


5

penelitian secara keseluruhan. Bentuk analisis yang dilakukan adalah

studi kepustakaan. Bagian kedua adalah analisis tujuan penelitian dan

pengembangan sistem, dan yang terakhir adalah analisis terhadap

kebutuhan perangkat yang digunakan dalam penelitian ini.

2. Tahap desain

Tahap desain merupakan tahap perancangan alur proses dan perancangan

pengujian.

3. Tahap pengembangan

Tahap pengembangan ini bertujuan untuk menghasilkan sebuah sistem

dengan penerapan algoritma.

4. Tahap evaluasi

Tahap evaluasi merupakan tahap pengujian sistem kedalam berbagai

kondisi. Pengujian dilakukan untuk memastikan keluaran sistem sesuai

dengan kebutuhan.

1.9. Sistematika Penulisan

Adapun sistematika penulisan tugas akhir ini terdiri dari 5 bab dengan

susunan sebagai berikut:

BAB I PENDAHULUAN

Bab ini berisi tentang latar belakang masalah, rumusan masalah, tujuan

penelitian, manfaat penelitian, batasan masalah, metodologi penelitian,

dan sistematika penulisan.

BAB II LANDASAN TEORI

Bab ini berisi tentang penelitian terdahulu yang relevan dan kajian teori-

teori yang dipakai untuk menunjang penelitian.

BAB III ANALISIS DAN PERANCANGAN

Bab ini berisi analisis sistem, analisis permasalahan, perancangan sistem,

dan perancangan pengujian.


6

BAB IV IMPLEMENTASI DAN PENGUJIAN

Bab ini berisi implementasi algoritma, pengujian proses, serta pengujian

dan perbandingan hasil algoritma.

BAB V PENUTUP

Bab ini berisi kesimpulan penelitian dan saran untuk pengembangan

penelitian lebih lanjut.


7

BAB II

LANDASAN TEORI

2.1. Penelitian Terdahulu yang Relevan

Penelitian tentang perbandingan algoritma memang kerap kali dilakukan.

Kajian terhadap penelitian-penelitian tersebut sangat beragam sesuai dengan

permasalahan yang diamati. Keragaman yang ada dijadikan sebagai sumber data

yang dianalisis.

Penelitian mengenai perbandingan algoritma pernah dilakukan oleh Iing

Mutakhiroh, Fajar Saptono, Nur Hasanah dan Romi Wiryadinata. Penelitian

tersebut berjudul “Pemanfaatan Metode Heuristik Dalam Pencarian Jalur

Terpendek Dengan Algoritma Semut Dan Algoritma Genetik”. Adapun hasil

penelitian menunjukan waktu perhitungan yang diperlukan lebih cepat 30%

dibandingkan dengan menggunakan metode konvensional.

Karisma dan Ridwan, pernah melakukan penelitian tentang “Perbandingan

Algoritma Dijkstra Dan Algoritma Ant Colony Optimization Dalam Travelling

Salesman Problem (TSP) Pada Kota Semarang”. Berikut ini adalah hasil penelitian

tersebut:

1. Pencarian jalur terpendek dengan metode Ant Colony tergantung dari

parameter-parameter yang dimasukan. Parameter tersebut antara lain:

banyaknya titik, banyak semut, Alfa (tetapan pengendali intensitas

feromon), Beta (tetapan pengendali visibilitas), Rho (tetapan penguapan

feromon).

2. Algoritma Ant Colony membutuhkan waktu rata-rata 19 detik dengan

iterasi sebanyak 100, sedangkan untuk mendapatkan jarak terpendek dari

pada waktu rata-rata pada algoritma Dijkstra yaitu 263,87 detik.

3. Jarak optimal untuk menempuh semua titik kecamatan di kota semarang

pada algoritma Ant Colony sebesar 113 km, sedangkan Dijkstra

mempunyai jarak sebesar 110 km. Algoritma Dijkstra mempunyai jarak

optimal dibandingkan algoritma Ant Colony.


8

Meskipun penelitian perbandingan algoritma pernah dilakukan, penelitian

tersebut masih layak dilakukan. Masih banyak algoritma yang perlu dibandingkan

untuk mengetahui kelebihan dan kelemahan setiap algoritma, terutama apabila

dihadapkan pada persoalan-persoalan khusus. Oleh karena itu, peneliti akan

mencoba ulang membandingkan algoritma Ant Colony Optimization dengan

algoritma genetika.

2.2. Kajian Teori

2.2.1. Analisis Algoritma Secara Umum

Ada dua hal yang perlu diperhatikan dalam menganalisis kinerja suatu

algoritma. Hal tersebut adalah waktu tempuh dan jumlah memori yang

digunakan. Waktu tempuh dapat didefinisikan sebagai waktu yang diperlukan

oleh suatu algoritma, dalam mencari solusi atas permasalahan yang diberikan.

Menurut Suryadi MT (1996), seperti yang dikutip oleh Darmadipta (2013)

dalam tugas akhirnya yang berjudul “Perbandingan Penggunaan

Algoritma Dijkstra dan Algoritma Floy-Warshall Untuk Pencarian

Jalur Terpendek Pada Bus Trans Jogja”, waktu tempuh yang diperlukan

oleh suatu algoritma dipengaruhi oleh beberapa hal, yaitu:

1. Banyak langkah

Banyaknya langkah yang digunakan dalam suatu algoritma akan

menentukan cepat lambatnya proses yang dilakukan oleh suatu

algoritma. Semakin banyak langkah yang digunakan, akan

memperlambat proses. Begitu pula sebaliknya, semakin sedikit

langkah yang digunakan maka semakin cepat pula prosesnya.

2. Besar dan jenis input data

Besar dan jenis input data mempengaruhi proses perhitungan pada

suatu algoritma. Jenis data dengan tingkat ketelitian tunggal (single

precision) waktu tempuhnya lebih kecil dari pada data dengan

tingkat ketelitian ganda (dopuble precision) maupun dengan

tingkat ketelitian lainnya yang lebih besar (triple precision dan

quadruple precision).


9

3. Jenis operasi

Jenis operasi juga akan mempengaruhi waktu tempuh dari sutau

algoritma dalam mencari solusi dari permasalahan yang diberikan.

Jenis operasi yang dimaksud dapat berupa operasi aritmatika,

logika, dan lain-lain.

4. Komputer dan kompilator

Hal ini merupakan faktor luar yang mempengaruhi waktu tempuh

suatu algoritma. Suatu algoritma walaupun sudah mencapai waktu

yang cukup efisien, namun jika menggunakan komputer

kemampuannya lambat dan kompilator yang tidak sesuai, maka

waktu tempuh yang digunakan algoritma tersebut pun akan

membesar (lambat).

Jumlah memori juga perlu diperhatikan dalam menganalisis suatu

algoritma. Hal yang mempengaruhi dalam pemakaian memori adalah jenis

variable dan data yang digunakan pada suatu algoritma. Oleh karena itu,

pengalokasian memori perlu diperhitungkan supaya dapat mempercepat

waktu tempuh dan kekurangan memori dapat dihindari.

Dalam persoalan komputasi suatu algoritma, kompleksitas waktu

asimptotik juga harus dipertimbangkan. Kompleksitas waktu asimptotik

adalah perkiraan kebutuhan waktu algoritma sejalan dengan meningkatnya

nilai n. Kebanyakan algoritma memakan waktu yang semakin lama apabila

ukuran masukan n semakin besar/kompleks, bahkan seperti deret

eksponensial. Kompleksitas waktu asimptotik dinotasikan dengan notasi “O”

(Big Oh).

2.2.2. Teori Graph

Penelitian tentang Travelling Salesman Problem apabila dilihat lebih

jauh sangat berkaitan dengan teori graph. Setiap kota yang dikunjungi oleh

Salesman merupakan representasi dari node, sedangkan setiap jalur yang

menghubungkan antar dua kota juga direpresentasikan dari path pada sebuah


10

graph.

Graph secara umum adalah suatu diagram yang menggambarkan obyek

seperti peta, jalur distribusi air, dan lain-lain. Setiap obyek dihubungkan oleh

sebuah jalur. Di dalam graph, obyek dilambangkan dengan titik. Sedangkan

garis yang menghubungkan antar titik merupakan gambaran dari jalur yang

menghubungkan obyek-obyek.

Graph atau lebih lengkapnya dapat dituliskan dengan notasi G(V, E)

adalah sekumpulan set titik (nodes/vertices) V(G) dan sekumpulan set garis

(edges) E(G). Berikut beberapa contoh graph:

Gambar 2.1. Contoh Graph.

Graph pada gambar (2.1) contoh a terdiri dari tiga titik yaitu v1, v2, dan

v3, serta mempunyai tiga garis penghubung antar titik yaitu e1 (v1,v2), e2

(v1,v3), dan e3 (v2,v3). Sedangkan pada contoh b terdiri dari tujuh titik yaitu

v4, v5, v6, v7, v8, v9, dan v10, serta mempunyai enam garis penghubung

antar titik yaitu e4 (v4,v5), e5 (v4,v6), e6 (v5,v7), e7 (v5,v8), e8 (v6,v9), dan

e9 (v6,v10).

2.2.2.1. Jenis-jenis graph

2.2.2.1.1. Graph sederhana (Simple graf)

Graph sederhana adalah graph yang tidak menggandung

gelang maupun sisi-ganda. Contoh graph sederhana dapat dilihat

pada gambar (2.2) dibawah.


11

Gambar 2.2. Contoh Graph Sederhana

2.2.2.1.2. Graph tak-sederhana (unsimple-graf/multigraf)

Graph tak-sederhana adalah graph yang menggandung

garis/ruas ganda atau gelang. Pada gambar (2.3) dibawah, graph

pertama memiliki garis ganda e3 dan e4 yang menghubungkan

titik 1 dengan titik 3, serta garis ganda e6 dan e7 yang

menghubungkan titik 4 dengan titik 3.

Pada graph kedua dalam gambar (2.3), graph tersebut

mempunyai garis ganda dan gelang. Garis ganda e3 dan e4

menghubungkan titik 1 dengan titik 3. Garis ganda e6 dan e7

menghubungkan titik 4 dengan titik 3. Selain itu garis e8 yang

menyerupai gelang, menghubungkan titik 3 dengan dirinya

sendiri.

Gambar 2.3. Contoh Graph Tidak Sederhana


12

2.2.2.1.3. Graph berhingga (limited graf)

Graph berhingga adalah graph dengan jumlah simpul/titik

sebanyak n (berhingga).

2.2.2.1.4. Graph tak-berhingga (unlimited graf)

Graph tak-berhingga adalah graph yang mempunyai jumlah

simpul/titik dengan banyak yang tak-berhingga.

2.2.2.1.5. Graph berarah (directed graf atau digraf)

Graph berarah adalah graph yang setiap garisnya

mempunyai orientasi arah. Pada gambar (2.4) dibawah, terlihat

bahwa garis-garis yang menjadi penghubung antar titik, setiap

garisnya mempunyai orientasi arah.

Gambar 2.4. Contoh Graph Berarah

2.2.2.1.6. Graph tak-berarah (undirected graf)

Graph tak-berarah adalah graph dengan seluruh garisnya

tidak mempunyai orientasi arah.

2.2.2.2. Graph berbobot

Graph berbobot atau graph berlabel adalah graph yang setiap

garisnya mempunyai nilai berupa bilangan non-negatif. Dalam gambar

(2.5) dapat dilihat setiap garis yang menghubungkan antar titik

mempunyai nilai atau bobot. Titik A dihubungkan dengan titik B dan

bobot hubungan antar titik adalah 3, titik B dihubungkan dengan titik D


13

dengan bobot 3, begitu seterusnya.

Gambar 2.5. Contoh Graph Berbobot

2.2.2.3. Graph lengkap

Graph lengkap adalah graph sederhana yang setiap titiknya

mempunyai garis ke semua simpul lainnya. Graph lengkap dengan n

buah titik dilambangkan dengan Kn. Jumlah garis pada graph lengkap

yang terdiri dari n buah titik, adalah n(n-1)/2. Gambar (2.6) menunjukan

contoh 6 buah graph lengkap, dengan setiap garisnya adalah n(n-1)/2.

Gambar 2.6. Contoh Graph Lengkap Kn Dengan 1 ≤ n ≤ 6

2.2.2.4. Keterhubungan antar titik

1. Perjalanan (walk)

Perjalanan atau walk pada suatu graph adalah barisan titik

dan garis berganti-ganti (v1,e1,v2,e2,v3,e3, . . . .,en-1,vn) dengan

setiap garis en menghubungkan titik vn dengan titik vn+1.

Dalam hal ini, v1 disebut titik awal dan vn+1 disebut titik akhir.

2. Lintasan (trail)

Lintasan adalah istilah dalam perjalanan yang mengunjungi

titik dan melewati garis.


14

3. Jalur lintasan (path)

Jalur lintasan atau path adalah panjang lintasan dari titik awal

hingga titik akhir.

4. Sirkuit (cycle)

Sirkuit lintasan atau cycle adalah lintasan yang berawal dan

berakhir pada titik yang sama.

2.2.3. Travelling Salesman Problem

Masalah Travelling Salesman problem (TSP) adalah salah satu contoh

yang paling banyak dipelajari dalam combinatorial optimization. Masalah ini

mudah untuk dinyatakan tetapi sangat sulit untuk diselesaikan. TSP termasuk

kelas NP-Hard problem dan tidak dapat diselesaikan secara optimal dalam

Polynomial computation time dengan algoritma eksak. Bila diselesaikan

secara eksak waktu komputasi yang diperlukan akan meningkat secara

eksponensial seiring bertambah besarnya masalah.

TSP dapat dinyatakan sebagai permasalahan dalam mencari jarak

minimal sebuah tour terhadap sejumlah n kota, dimana kota-kota yang ada

hanya dikunjungi sekali dan berakhir dengan mengunjungi kembali kota

keberangkatan. Secara lebih teoritis, TSP merupakan representasi dari Graph

lengkap dan berbobot G = (V, E) dengan V himpunan vertek yang

merepresentasikan himpunan titik - titik, dan E adalah himpunan dari edge.

Setiap edge (r,s) ∈ E adalah nilai (jarak) drs yang merupakan jarak dari kota r

ke kota s, dengan (r,s) ∈ V.

Beberapa karakteristik TSP, adalah sebagai berikut:

1. Terdapat n buah titik (kota)

2. Dari titik i ke titik j terhubung oleh edge E(i,j) berbobot D(i,j)

3. Perjalanan dimulai dari dan berakhir pada titik yang sama

4. Kecuali titik keberangkatan, titik-titik yang lainnya harus

dikunjungi satu kali

5. Dari n! (n faktorial) kombinasi perjalanan, solusi optimum

adalah perjalanan dengan jarak tempuh terpendek


15

2.2.4. Algoritma Genetika

Algoritma genetika adalah algoritma yang berdasarkan pada

mekanisme seleksi alam dan konsep genetika. Konsep genetika digunakan

untuk merepresentasikan setiap kemungkinan solusi dari masalah optimasi

yang ada. Sedangkan seleksi alam merepresentasikan proses seleksi terhadap

calon-calon solusi dari sebuah populasi. Dalam implementasinya, algoritma

genetika meniru beberapa proses yang terdapat pada evolusi alami makhluk

hidup antara lain seleksi alam dan reproduksi.

2.2.4.1. Konsep yang mendasari

Algoritma genetika adalah algoritma pencarian yang

dikembangkan dari konsep genetika dan teori evolusi alam. Teori

genetika dan teori evolusi dikemukakan oleh Charles Darwin, seorang

ahli Biologi. Dalam konsep genetika, disebutkan bahwa setiap

organisme merupakan suatu sistem yang terdiri dari organ-organ, dan

setiap organ terdiri dari sekumpulan sel. Setiap sel dibagi lagi menjadi

sejumlah kromosom, dengan masing-masing kromosom terdiri dari

gen-gen yang merupakan blok DNA. Blok DNA menghasilkan suatu

karakteristik/sifat tertentu dari makhluk hidup. Karakteristik/sifat

masing-masing makhluk hidup berbeda antar satu dengan yang lainnya.

Setiap gen terdiri dari sekumpulan allele yang masing-masing

membawa berbagai variasi dari karakteristik tertentu.

Sedangkan teori evolusi alam adalah proses seleksi terhadap

anggota dari berbagai populasi. Seleksi terjadi secara alami atau karena

adanya faktor-faktor alam yang berpengaruh terhadap tingkat

ketahanan hidup suatu organisme. Daya tahan hidup ini disebabkan

kemampuan penyesuaian yang tinggi dari organisme terhadap

perubahan lingkungan. Proses-proses yang terjadi dalam evolusi alam

yang menjadi konsep dasar algoritma genetika adalah:

1. Seleksi alam

Seleksi alam adalah suatu proses pencarian terhadap anggota


16

populasi yang dapat bertahan hidup yang sifatnya diturunkan

dari genotif (kumpulan gen-gen tertentu dalam kromosom)

untuk mendapatkan struktur yang lebih efisien. Genotif

dengan struktur yang efisien, berguna untuk melaksanakan

kegiatan yang diperlukan untuk dapat bertahan hidup.

2. Reproduksi

Reproduksi adalah suatu proses biologi untuk

mempertahankan kelestarian populasi suatu spesies. Proses

biologi ini dilakukan untuk mendapatkan keturunan yang

sifatnya diturunkan dari sang induk. Proses ini dapat

dilakukan oleh dua induk individu atau satu induk individu.

2.2.4.2. Alur Algoritma Genetika

Alur algoritma genetika mengikuti langkah-langkah di bawah:

1. Bentuk populasi awal dengan menginisialkan gen-gen

dalam kromosom.

2. Selama kondisi terminasi belum terpenuhi maka lakukan:

a. Jika syarat crossover terpenuhi maka:

1) Pilih kromosom parent

2) Jalankan crossover

b. Jika syarat mutasi terpenuhi maka:

1) Pilih kromosom parent

2) Jalankan mutasi

c. Lakukan evaluasi terhadap nilai fitness offspring

3. Return kromosom fittest sebagai hasil algoritma

Apabila langkah-langkah di atas dipetakan kedalam prosedur,

maka terlihat seperti pada gambar (2.7) di bawah:


17

Gambar 2.7 Prosedur Algoritma Genetika

2.2.4.3. Populasi

Algoritma Genetika dalam menyelesaikan masalah, dimulai

dengan menginisialisasikan himpunan solusi yang dibangkitkan secara

acak. Himpunan solusi ini dinamakan populasi. Dalam setiap populasi

terdapat individu yang disebut kromosom. Kromosom merupakan

representasi dari solusi. Dapat dilihat dalam gambar (2.8), menunjukan

populasi dengan 4 buah kromosom di dalamnya. Masing-masing

kromosom adalah biner 4 bits dengan biner 0 dan 1 sebagai allele.

Gambar 2.8. Populasi dalam Algoritma Genetika


18

Dalam penerapannya, allele biner biasanya lebih cenderung

diterapkan dalam optimasi fungsi atau pencarian titik optimal di titik

(x,y). Sedangkan untuk permasalahan yang lebih kompleks seperti

penjadwalan atau titik kota pada TSP, allele dimodifikasi sedemikian

rupa dengan penginisialan secara permutasi.

2.2.4.4. Evaluasi nilai fitness

Dari setiap generasi, nilai kromosom dievaluasi untuk

memperoleh gen yang lebih baik dari gen pada kromosom milik

generasi sebelumnya. Kromosom dengan nilai fitness yang baik,

dijadikan anggota generasi selanjutnya.

Gambar 2.9 Fitness Populasi

Dalam gambar (2.9) ditunjukkan anggota populasi yang

mempunyai nilai fitness yang baik adalah 1 dan 3. Anggota lain dengan

nilai fitness yang tidak lebih baik, maka dihapus. Selanjutnya anggota

1 dan 3 akan dijadikan kromosom bagi generasi berikutnya.

2.2.4.5. Crossover (Kawin-Silang)

Perkawinan silang adalah proses pertukaran gen dari dua

individu. Kedua individu tersebut dengan karakteristik yang berbeda,

menghasilkan keturunan-keturunan dengan karakteristik yang berbeda

dari induknya.

Gambar 2.10 Kromosom Crossover


19

Misalnya, dalam gambar (2.10) terpilih 2 kromosom sebagai

induk yang akan disilangkan. Dari hasil perkawinan silang kedua biner

8 bit tersebut, diperoleh keturunan 110/11001 dengan nilai yang lebih

tinggi dibanding kedua orang tua. Terlihat hasil persilangan

menghasilkan induvidu/kromosom baru yang berbeda dari kedua induk.

2.2.4.6. Mutasi

Mutasi adalah proses perubahan materi genetik dari suatu spesies

atau individu dalam usaha penyesuaian (adaptasi) terhadap perubahan

lingkungan. Penyesuaian ini terjadi semata-mata supaya individu atau

spesies dapat bertahan hidup. Perubahan pada mutasi terjadi dalam nilai

yang kecil. Hal ini dikarenakan perubahan lingkungan juga dalam nilai

yang kecil. Dalam algoritma genetika, mutasi terjadi dengan mengganti

allele 1 dengan allele 0.

Gambar 2.11 Mutasi Kromosom

Sebagaimana ditunjukkan dalam gamabr (2.11), perubahan nilai

yang terjadi sangat kecil. Hal ini untuk untuk menghindari terjadinya

noisy atau perubahan yang sangat signifikan karena menyesuaikan pada

keadaan yang sebenarnya, sebagaimana dalam ilmu Biologi. Apabila

perubahan nilai terlalu besar, maka gen yang dihasilkan melenceng jauh

dari region yang diinginkan. Oleh karena itu, beberapa sistem tidak

menggunakan mutasi sebagai operatornya.

2.2.4.7. Seleksi Individu

Seleksi merupakan proses pemilihan kromosom untuk dijadikan

orang tua yang nantinya akan melakukan proses reproduksi.

Berdasarkan teori Darwin, kromosom yang terbaik harusnya dapat

bertahan hidup dan membentuk keturunan baru.


20

2.2.4.7.1. Roda Roulette

Pada metode ini, pemilihan orang tua berdasar pada nilai

fitness-nya. Semakin baik nilai fitness individu, maka semakin

besar peluang untuk dipilih. Diandaikan semua individu diletakan

pada sebuah roda roullete, besarnya kemungkinan bagi setiap

individu adalah tergantung pada probabilitas komulatif

kromosom dan nilai fitness-nya.

Gambar 2.12 Contoh Seleksi Roda Roulette

Pada Gambar (2.12) di atas, individu b (fitness = 30%) dan

c (fitness = 28%) berpeluang besar untuk terpilih sebagai individu

pembentuk keturunan baru. Skema pemilihan Roda Roulette

berdasarkan skala fitness, karena terpilihnya suatu kromosom

dalam populasi adalah sebanding dengan fitness-nya. Jika semua

kromosom dalam populasi mempunyai fitness yang sama atau

hampir sama, maka seleksi ini menjadi seleksi yang bersifat

acak/random.

2.2.4.7.2. Rangking

Seleksi rangking dilakukan dengan mengurutkan

kromosom dalam populasi dengan membandingkan nilai fitness

setiap kromosom. Kromosom dengan nilai fitness terburuk akan

diganti nilai fitness-nya dengan nilai 1. Kromosom dengan nilai

fitness terburuk kedua, nilai fitness-nya diganti dengan 2, begitu

20%

30%28%

22% a

b

c

d


21

seterusnya untuk seluruh kromosom. Kromosom yang

mempunyai nilai fitness paling baik, nilai fitness-nya diganti

dengan n, dimana n adalah jumlah kromosom dalam populasi.

2.2.4.7.3. Turnamen

Seleksi turnamen merupakan variasi dari seleksi roda

roullete dengan seleksi rangking. Sejumlah k kromosom tertentu

dari populasi beranggota n kromosom, dipilih secara acak dengan

prioritas yang sama. Dari k kromosom yang terpilih, dipilih satu

kromosom dengan fitness terbaik yang diperoleh dari hasil

pengurutan rangking nilai fitness.

2.2.5. Algoritma Koloni Semut

Algoritma koloni semut diadopsi dari perilaku semut dalam

menemukan jalur, sebagai sebuah simulasi multi agen yang menggunakan

metafora alami semut untuk menyelesaikan problem ruang fisik. Algoritma

ini diperkenalkan oleh Moyson dan Manderick pada tahun 1996, dan secara

meluas dikembangkan oleh Marco Dorigo dan Thomas Stutzle.

Algoritma koloni semut mempunyai karakteristik:

1. Serbaguna, algoritma ini dapat diterapkan dalam persoalan-

persoalan yang memiliki kesamaan seperti pada travelling

salesman problem, asymetric travelling problem, sequential

ordering problem dan vehicle routing problem.

2. Pendekatan yang mendasar, karena menggunakan metode seperti

cara pencarian.

2.2.5.1. Konsep yang mendasari

Semut dapat membangun sebuah jalur dari sarang menuju sumber

makanan dan kemudian kembali lagi ke sarang melalui jalur tercepat.

Jalur yang dibangun tersebut dinamakan pheromone trails / jejak bau.

Semut-semut dalam perjalanan selalu meninggalkan pheromone pada

jalur yang dilewatinya. Setiap jalur mempunyai kuantitas pheromone


22

yang berbeda. Perbedaaan kadar pheromone menunjukan seberapa

sering jalur tersebut dilewati. Semakin banyak kadar pheromone yang

tertinggal di sebuah jalur, maka semakin sering jalur tersebut

digunakan, dan dapat dipastikan sebagai jalur yang tercepat.

Pheromone adalah zat kimia yang berasal dari kelenjar endokrin

dan digunakan oleh makhluk hidup untuk mengenali sesama jenis,

individu lain, kelompok, dan untuk membantu proses reproduksi.

Berbeda dengan hormon, pheromone menyebar ke luar tubuh dan hanya

dapat mempengaruhi dan dikenali oleh individu lain yang sejenis (satu

spesies). Proses peninggalan pheromone dikenal sebagai stigmery,

yaitu sebuah proses memodifikasi lingkungan yang tidak hanya

bertujuan untuk mengingat jalan pulang ke sarang, tetapi juga

memungkinkan para semut berkomunikasi dengan koloninya.

Seiring waktu, bagaimanapun juga jejak pheromone akan

menguap dan akan mengurangi kekuatan daya tariknya. Lebih cepat

setiap semut pulang pergi melalui rute tersebut, maka pheromone yang

menguap lebih sedikit. Begitu pula sebaliknya jika semut lebih lama

pulang pergi melalui rute tersebut, maka pheromone yang menguap

lebih banyak. Pada tahun 1989 Deneubourg dan teman-temannya

melakukan eksperimen menggunakan semut Argentina Iridomyrmex

humilis. Eksperiment itu kemudian dikenal dengan sebutan Double

Brige Experiment, seperti yang digambarkan pada gambar (2.13).

Pada gambar ke-a (2.13), adalah gambaran pertama-tama semut

berjalan dari sarang menuju sumber makanan. Dalam perjalanan

tersebut, semut menempuh dua jalur. Semut berpencar dan menandai

jalur dengan meninggalkan pheromone. Pheromone yang ditinggalkan

sebagai tanda untuk mengenali jalan kembali ke sarang, dapat menguap

seiring waktu. Oleh karena itu, pehormone yang ditinggalkan pada jalur

yang lebih dekat dibanding yang lainnnya, mengandung kadar

pheromone yang lebih tinggi. Hal ini disebabkan karena intensitas

penguapan pheromone adalah statis atau stabil. Gambar (2.13) ke-b,


23

menunjukan bahwa semut-semut dalam koloni memilih melewati jalan

yang kadar pheromone-nya tinggi.

Gambar 2.13 Contoh Jalur Perjalanan Semut

2.2.5.2. Model dan Teori Algoritma ACO

Konsep ACO sebenarnya cukup sederhana, yaitu dengan

menghitung banyaknya semut dalam sebuah koloni yang melalui jalur

pheromone. Semakin banyak jumlah semut yang melewati jalur

pheromone maka dapat diputuskan jalur tersebut adalah jalur terdekat.

Jalur pheromone dalam ACO dapat dikatakan sebagai sebuah jalur

distribusi informasi numerik, yang digunakan oleh semut (artificial)

dalam membangun sebuah solusi probabilistik dalam menyelesaikan

masalah. Dengan pencarian berbasis probabilitas, semut-semut yang

pada mulanya bergerak secara random diarahkan menuju jalur solusi

(Stutzle, T., Dorigo, M., 2004).

Dalam mengkonstruksi jalur solusi, secara sederhananya

mengikuti langkah-langkah berikut:

1. Memilih secara random, sebuah kota awal dimana semut

diposisikan.

2. Secara probabilistik dengan mempertimbangkan informasi


24

pheromone, mengunjungi kota-kota yang belum pernah

dikunjungi sampai semuanya dikunjungi.

3. Setelah semua semut menyelesaikan tur (membangun jalur

solusi), semut kembali lagi ke kota awal dan menempatkan

pheromone pada tur yang mereka bangun.

Jika dipetakan ke dalam sebuah prosedur, maka akan terlihat

seperti pada gambar (2.14) di bawah:

Gambar 2.14 Prosedur ACO

Pada awalnya ACO dengan algoritmanya Ant System (AS)

dirancang untuk menyelesaikan permasalahan TSP. AS merupakan

algoritma ACO pertama, yang diusulkan oleh Marco Dorigo dalam tesis

PhD-nya pada tahun 1992. AS mencapai hasil awal yang

menggembirakan, namun ditemukan lebih rendah daripada algoritma

mutakhir untuk TSP. Pentingnya AS karena itu terutama terletak pada

inspirasi yang diberikannya untuk sejumlah ekstensi yang

meningkatkan kinerja secara signifikan dan saat ini berada di antara

algoritma ACO yang paling sukses. Sebenarnya, sebagian besar


25

ekstensi ini merupakan perluasan langsung AS dalam artian bahwa

mereka menjaga prosedur penyelesaian solusi yang sama dan prosedur

penguapan phremone yang sama. Turunan (ekstensi) ini termasuk

elitis-AS, basis berbasis AS, dan MAX-MIN AS. Perbedaan utama

antara AS dan turunannya adalah cara dilakukannya pembaruan

pheromone, dan juga beberapa detail tambahan dalam argumen jalur

feromon.

2.2.5.3. Ant System (AS) dan Turunan Langsungnya

2.2.5.3.1. Ant System (AS)

Algoritma Ant System (AS) adalah algoritma ACO pertama

yang dirumuskan dan diuji untuk menyelesaikan kasus TSP.

Algoritma ini tersusun atas sejumlah m semut yang bekerjasama

dan berkomunikasi secara tidak langsung melalui komunikasi

Pheromone.

Secara informal, AS bekerja sebagai berikut : Setiap semut

memulai tournya melalui sebuah titik yang dipilih secara acak.

Secara berulang kali, satu-persatu titik yang ada dikunjungi oleh

semut dengan tujuan untuk menghasilkan sebuah tour. Pemilihan

titik-titik yang akan dilaluinya didasarkan pada suatu fungsi

probabilitas, dinamai aturan transisi status (state transition rule),

dengan mempertimbangkan visibility titik tersebut dan jumlah

pheromone yang terdapat pada ruas yang menghubungkan titik

tersebut.

Dengan adanya kadar (intensitas) pheromone, semut lebih

suka untuk bergerak menuju ke titik-titik yang dihubungkan

dengan ruas yang pendek dan memiliki tingkat pheromone yang

tinggi. Setiap semut memiliki sebuah memori, dinamai tabulist,

yang berisi semua titik yang telah dikunjunginya pada setiap tour.

Tabulist ini mencegah semut untuk mengunjungi titik-titik yang

sebelumnya telah dikunjungi selama tour tersebut berlangsung,


26

yang membuat solusinya mendekati optimal.

Setelah semua semut menyelesaikan tour mereka dan

tabulist mereka menjadi penuh, sebuah aturan pembaruan

pheromone global (global pheromone updating rule) diterapkan

pada setiap semut. Penguapan pheromone pada semua ruas

dilakukan, kemudian setiap semut menghitung panjang tour yang

telah mereka lakukan lalu meninggalkan sejumlah pheromone

pada edge-edge yang merupakan bagian dari tour mereka yang

sebanding dengan kualitas dari solusi yang mereka hasilkan.

Semakin pendek sebuah tour yang dihasilkan oleh setiap

semut, jumlah pheromone yang ditinggalkan pada edge-edge

yang dilaluinya pun semakin besar. Dengan kata lain, edge-edge

yang merupakan bagian dari tour-tour terpendek adalah edge-

edge yang menerima jumlah pheromone yang lebih besar. Hal ini

menyebabkan edge-edge yang diberi pheromone lebih banyak

akan lebih diminati pada tour-tour selanjutnya, dan sebaliknya

edge-edge yang tidak diberi pheromone menjadi kurang diminati.

Dan juga, rute terpendek yang ditemukan oleh semut disimpan

dan semua tabulist yang ada dikosongkan kembali.

Peranan utama dari penguapan pheromone adalah untuk

mencegah stagnasi, yaitu situasi dimana semua semut berakhir

dengan melakukan tour yang sama. Proses di atas kemudian

diulangi sampai tour-tour yang dilakukan mencapai jumlah

maksimum atau sistem ini menghasilkan perilaku stagnasi

dimana sistem ini berhenti untuk mencari solusi alternatif.

Aturan transisi status yang digunakan oleh AS dinamai

random proportional rule, yang ditunjukkan oleh persamaan

(2.1). 𝑃𝑟𝑠𝑘 merupakan probabilitas dari semut k pada titik r yang

memilih untuk menuju ke titik s.


27

𝑃𝑟𝑠𝑘 = {

[𝜏𝑟𝑠]𝛼.[𝜂𝑟𝑠]𝛽

∑ [𝜏𝑟𝑢]𝛼.[𝜂𝑟𝑢]𝛽𝑢 ∈ 𝐽𝑟

𝑘 𝑢𝑛𝑡𝑢𝑘 𝑠 ∈ 𝐽𝑟

𝑘

0 𝑢𝑛𝑡𝑢𝑘 𝑠 𝑙𝑎𝑖𝑛𝑛𝑦𝑎

……………(2.1)

Dimana 𝜏𝑠𝑟 adalah jumlah pheromone yang terdapat pada

edge antara titik r dan titik s, (𝜂𝑟𝑠) = 1

𝑑𝑟𝑠 adalah visibility (invers

dari jarak 𝑑𝑟𝑠) dengan 𝑑𝑟𝑠 = √(𝑥𝑟 − 𝑥𝑠)2 + (𝑦𝑟 − 𝑦𝑠)2 (jika

hanya diketahui koordinat titiknya saja). 𝛼 adalah sebuah

parameter yang mengontrol bobot (weight) relative dari

pheromone dan 𝛽 adalah parameter pengendali jarak, dengan 𝛼 >

0 𝑑𝑎𝑛 𝛽 > 0.

𝐽𝑟𝑘 adalah himpunan titik yang akan dikunjungi oleh semut

k yang sedang berada pada titik r (untutk membuat solusinya

mendekati optimal), dan pada persamaan (2.1) kita mengalikan

pheromone pada edge (r,s) dengan nilai visibility yang sesuai

(𝜂𝑟𝑠). Dengan cara ini kita memilih edge yang lebih pendek dan

memiliki jumlah pheromone yang lebih besar.

Setelah semua semut menyelesaikan tour-nya masing-

masing, maka pheromone diperbaharui. Dalam Ant System,

aturan pembaharuan pheromone global diimplementasikan

menurut persamaan (2.2) sebagai berikut:

𝜏𝑟𝑠 ← (1 − 𝜌). 𝜏𝑟𝑠 + ∑ ∆𝜏𝑟𝑠𝑘𝑚

𝑘=1 …………....(2.2)

Dimana rho atau parameter evaporasi berada di rentang 0 <

𝜌 ≤ 1 dan m adalah jumlah semut dalam koloni. Sedangkan ∆𝜏𝑟𝑠𝑘

dapat dicari dengan persamaan (2.3) dengan 𝑐𝑘 panjang tour yang

dilalui semut k.

∆𝜏𝑟𝑠𝑘 = {

1

𝐶𝑘 , (𝑟, 𝑠) ∈ 𝑡𝑜𝑢𝑟 𝑦𝑎𝑛𝑔 𝑑𝑖𝑙𝑎𝑘𝑢𝑘𝑎𝑛 𝑠𝑒𝑚𝑢𝑡 𝑘

0, 𝑢𝑛𝑡𝑢𝑘 𝑠𝑒𝑏𝑎𝑙𝑖𝑘𝑛𝑦𝑎… …(2.3)

Untuk memastikan bahwa semut mengunjungi n titik yang


28

berbeda, diberikan tabulist pada masing-masing semut, yaitu

sebuah struktur data yang menyimpan titik-titik yang telah

dikunjungi semut dan melarang semut mengunjungi kembali

titik-titik tersebut sebelum mereka menyelesaikan sebuah tour.

Ketika sebuah tour selesai, tabulist digunakan untuk menghitung

solusi yang ditemukan semut pada tour tersebut. Tabulist

kemudian dikosongkan dan semut kembali bebas memilih titik

tujuannya pada tour berikutnya. 𝑇𝑎𝑏𝑢𝑘 adalah tabulist untuk

semut k. 𝑇𝑎𝑏𝑢𝑘 (𝑟) adalah elemen ke-r dari 𝑇𝑎𝑏𝑢𝑘, yaitu titik ke-

r yang dikunjungi semut k pada suatu tour.

2.2.5.3.2. Elitist Ant System (EAS)

Pengembangan Pengembangan pertama dari AS adalah

elitist strategy for Ant System (EAS), seperti yang dikemukakan

Dorigo, M., dkk. (1991a), (1991b), dan (1996). Ide ini berawal

ketika adanya penguatan pheromone pada edge-edge yang

merupakan tour terbaik yang ditemukan sejak awal algoritma.

Tour terbaik ini dinotasikan sebagai Tbs (best-so-far tour).

Penambahan intensitas Pheromone dari tour Tbs adalah

dengan memberi penambahan quantity 𝑒

𝐶𝑏𝑠 untuk setiap edge,

dimana e parameter yang diberikan untuk mendefinisikan nilai

tour terbaik (Tbs) dan Cbs adalah panjang tour terbaik. Perubahan

Pheromone didefinisikan dalam persamaan (2.4) sebagai berikut:

𝜏𝑟𝑠 ← (1 − 𝜌). 𝜏𝑟𝑠 + ∑ ∆𝜏𝑟𝑠𝑘 + ∆𝑒𝑟𝑠

𝑘𝑚𝑘=1 ……………(2.4)

Sedangkan untuk mencari ∆𝑒𝑟𝑠𝑘 dapat digunakan persamaan (2.5)

berikut :


1

𝐶𝑏𝑠, 𝑗𝑖𝑘𝑎 𝑒𝑑𝑔𝑒 (𝑟, 𝑠)𝑡𝑒𝑟𝑑𝑎𝑝𝑎𝑡 𝑝𝑎𝑑𝑎 𝑇𝑏𝑠

0, 𝑢𝑛𝑡𝑢𝑘 𝑠𝑒𝑏𝑎𝑙𝑖𝑘𝑛𝑦𝑎 …..(2.5)


29

Sebagai catatan, untuk algoritma EAS bagian lain dari

algoritma sama seperti pada AS yang telah dibahas pada bagian

sebelumnya.

2.2.5.3.3. Rank-Based Ant Sistem (ASRank)

Rank-based version of Ant Sistem (ASRank) merupakan

pengembangan dari AS dengan menerapkan elitist strategy. Pada

setiap iterasi, metode ini lebih dulu mengurutkan semut

berdasarkan tingkat fluktuasi solusi (panjang/pendek tour) yang

telah mereka temukan sebelumnya.

Saat melakukan pembaharuan pheromone hanya (w-1)

semut terbaik dan semut yang memiliki solusi best-so-far yang

diperbolehkan meninggalkan pheromone. Semut yang ke-z

terbaik memberikan kontribusi pheromone sebesar max{0, w-z},

sementara jalur best-so-far tour memberikan kontribusi

pheromone paling besar yaitu sebanyak w. Parameter w

menyatakan adanya tour terbaik dan z adalah peringkat semut.

Dalam ASRank aturan pembaharuan pheromone mengikuti

persamaan (2.6) berikut:

𝜏𝑟𝑠 ← (1 − 𝜌). 𝜏𝑟𝑠 + ∑ (𝑤 − 𝑧)∆𝜏𝑟𝑠𝑧 + 𝑤∆𝜏𝑟𝑠

𝑏𝑠,𝑤−1𝑧=1 ………(2.6)

Dengan ∆𝜏𝑟𝑠 = 1

𝐶𝑧 dan ∆𝜏𝑟𝑠𝑏𝑠 =

1

𝐶𝑏𝑠 untuk Cz adalah panjang

tour yang dilewati semut ke-z, Cbs adalah panjang tour terbaik.

Seperti dikutip dari Dorigo & Stutzle (2004), disebutkan bahwa

Bullnheimer, dkk (1999) telah melakukan eksperimen evaluasi

terhadap ASRank. Hasil eskperimen menunjukan ASRank

mempunyai hasil yang lebih baik daripada EAS namun lebih

signifikan daripada AS.

2.2.5.3.4. MAX-MIN Ant System (MMAS)

MAX-MIN Ant System (MMAS) merupakan


30

pengembangan dari algoritma AS selanjutnya, dengan beberapa

perubahan utama. Mengutip dari bukunya Marco Dorigo dan

Thomas Stutzle (2004), Stutzle & Hoos pada 1997 meyebutkan

empat perubahan utama di dalam MMAS terhadap AS.

Perubahan tersebut diantaranya:

1. Perubahan pertama yaitu, penambahan pheromone bisa

dilakukan pada edge-edge yang merupakan bagian dari

tour terbaik yang ditemukan sejak awal algoritma

(best-so-far tour), atau pada tour terbaik yang

ditemukan pada iterasi tersebut (iteration best-tour).

Bisa juga dimodifikasi dengan menambahkan

pheromone pada keduanya, best-so-far tour dan

iteration best-tour sekaligus. Akan tetapi, dengan

strategi ini muncul kemungkinan terjadinya stagnansi

yang menyebabkan semua semut melalui lajur yang

sama, karena pemberian pheromone yang berlebihan

pada edge.

2. Kedua, untuk mengatasi masalah stagnansi maka pada

MMAS diberikan batasan dalam pemberian nilai

pheromone dengan interval [𝜏𝑚𝑖𝑛, 𝜏𝑚𝑎𝑥].

3. Ketiga, menginisialisasi pheromone dengan batas atas

nilai pheromone, yang mana bersamaan dengan tingkat

pheromone evaporation yang kecil, akan

meningkatkan eksplorasi tour sejak dimulainya

pencarian.

4. Keempat, pheromone diinisialisasi kembali pada saat

terjadinya stagnasi atau ketika tidak ditemukan tour

yang sesuai dengan iterasi yang diinginkan.

Perbaharuan pheromone dilakukan saat semua semut sudah

membangun tournya. Pheromone diperbaharui menurut

persamaan (2.7) berikut:


31

𝜏𝑟𝑠 ← (1 − 𝜌). 𝜏𝑟𝑠 + ∆𝜏𝑟𝑠𝑏𝑒𝑠𝑡 ……………(2.7)

Di mana,


1𝐶𝑏𝑒𝑠𝑡⁄ , 𝑠𝑒𝑚𝑢𝑡 𝑚𝑒𝑛𝑒𝑚𝑢𝑘𝑎𝑛 𝑏𝑒𝑠𝑡 𝑠𝑜 𝑓𝑎𝑟 𝑡𝑜𝑢𝑟

1𝐶𝑖𝑏⁄ , 𝑠𝑒𝑚𝑢𝑡 𝑚𝑒𝑛𝑒𝑚𝑢𝑘𝑎𝑛 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛 𝑏𝑒𝑠𝑡 𝑡𝑜𝑢𝑟

…(2.8)

dengan Cbest merupakan panjang tour terbaik, dan Cib adalah

panjuang iterasi terbaik sebuah tour. Pada umumnya MMAS

mengimplementasikan keduanya, baik iterasi terbaik maupun

panjang tour tebaiknya.

2.2.5.4. Ant Colony System (ACS) Sebagai Ekstensi Dari

Algoritma Ant System (AS)

Algoritma Ant Colony System (ACS) merupakan pengembangan

dari algoritma AS selanjutnya setelah beberapa algoritma di atas.

Algoritma ini tersusun atas sejumlah m semut yang bekerjasama dan

berkomunikasi secara tidak langsung melalui komunikasi pheromone.

Secara informal, ACS bekerja pertama-tama sejumlah m semut

ditempatkan pada sejumlah n titik berdasarkan beberapa aturan

inisialisasi (misalnya, secara acak). Setiap semut membuat sebuah tour

(yaitu, sebuah solusi TSP yang mungkin) dengan menerapkan sebuah

aturan transisi status secara berulang kali. Selagi membangun tour,

setiap semut memodifikasi jumlah pheromone pada edge-edge yang

dikunjunginya, dengan menerapkan aturan pembaruan pheromone

lokal yang telah disebutkan tadi. Setelah semua semut mengakhiri tour

mereka, jumlah pheromone yang ada pada edge-edge dimodifikasi

kembali (dengan menerapkan aturan pembaruan pheromone global).

Seperti yang terjadi pada Ant system, dalam membuat tour semut-

semut “dipandu” oleh informasi heuristic (mereka lebih memilih edge-

edge yang pendek) dan oleh informasi pheromone. Sebuah edge dengan

jumlah pheromone yang tinggi merupakan pilihan yang sangat


32

diinginkan. Kedua aturan pembaruan pheromone itu dirancang agar

semut cenderung untuk memberi lebih banyak pheromone pada edge-

edge yang harus mereka lewati.

Berikutnya akan dibahas mengenai tiga karakteristik utama dari

ACS, yaitu aturan transisi status, aturan pembaharuan pheromone

global, dan aturan pembaharuan pheromone lokal.

2.2.5.4.1. Aturan transisi status

Aturan transisi yang berlaku pada ACS ditunjukkan pada

persamaan (2.9). Semut k yang berada di titik r, akan memilih

titik berikutnya s, menurut persamaan berikut :

𝑠 = {𝑎𝑟𝑔𝑚𝑎𝑥𝑙 ∈ 𝐽𝑟

𝑘{[𝜏𝑟𝑢]𝛼[𝜂𝑟𝑢]𝛽}, 𝑗𝑖𝑘𝑎 𝑞 ≤ 𝑞0

𝐽, 𝑏𝑖𝑙𝑎 𝑡𝑖𝑑𝑎𝑘 (𝑒𝑘𝑠𝑝𝑙𝑜𝑟𝑎𝑠𝑖) ……..(2.9)

Dimana q adalah bilangan random dalam [0,1], 𝑞0(0 ≤

𝑞0 ≤ 1) adalah sebuah parameter pembanding bilangan random,

dan 𝐽 = 𝑃𝑟𝑠𝑘 probabilitas dari semut k pada titik r yang memilih

untuk menuju ke titik s (persamaan 2.1).

Dengan kata lain, jika 𝑞 ≤ 𝑞0 maka semut tersebut akan

memanfaatkan informasi heuristic tentang jarak antara titik

tersebut dengan titik-titik lainnya, dan juga memanfaatkan

informasi yang tersimpan dalam bentuk pheromone. Hal ini

mengakibatkan edge terbaik (berdasarkan persamaan 2.9) dipilih.

Jika yang terjadi sebaliknya, maka sebuah edge dipilih

berdasarkan persamaan (2.1).

2.2.5.4.2. Update Global Pheromone

Setelah semua semut menyelesaikan sebuah tour,

pembaharuan pheromone dengan menerapkan global updating

rule menurut persamaan berikut ini :

𝜏𝑟𝑠 ← (1 − 𝜌). 𝜏𝑟𝑠 + 𝜌. ∆𝜏𝑟𝑠𝑘 ……………………...(2.10)


33

untuk ∆𝜏𝑟𝑠𝑘 = {

1𝐶𝑏𝑠⁄ , 𝑗𝑖𝑘𝑎 (𝑟, 𝑠) ∈ 𝑙𝑖𝑛𝑡𝑎𝑠𝑎𝑛 𝑏𝑎𝑖𝑘 𝑘𝑒𝑠𝑒𝑙𝑢𝑟𝑢ℎ𝑎𝑛

0, 𝑗𝑖𝑘𝑎 (𝑟, 𝑠)𝑏𝑢𝑘𝑎𝑛 𝑙𝑖𝑛𝑡𝑎𝑠𝑎𝑛 𝑏𝑎𝑖𝑘 𝑘𝑒𝑠𝑒𝑙𝑢𝑟𝑢ℎ𝑎𝑛… (2.11)

di mana 𝜌 adalah parameter global evaporation, yang mempunyai

nilai dengan bilangan real di antara 0 dengan 1. Serta ∆𝜏𝑟𝑠𝑘 adalah

1

𝑝𝑎𝑛𝑗𝑎𝑛𝑔 𝑙𝑖𝑛𝑡𝑎𝑠𝑎𝑛 𝑡𝑒𝑟𝑏𝑎𝑖𝑘 𝑘𝑒𝑠𝑒𝑙𝑢𝑟𝑢ℎ𝑎𝑛 jika (i,j) merupakan bagian

panjang lintasan terbaik keseluruhan dan 0 jika tidak.

Persamaan perbaharui jejak pheromone secara offline ini,

dilakukan pada akhir iterasi algoritma, saat semua-semut telah

menyelesaikan tour. Persamaan diterapkan pada edge dan

digunakan oleh semut untuk menemukan lintasan keseluruhan

yang terbaik sejak awal percobaan. Tujuan penambahan nilai ini

untuk memberi sejumlah jejak pheromone pada lintasan

terpendek, dimana tour terbaik (lintasan dengan panjang

terpendek) mendapat penguatan.

2.2.5.4.3. Pheromone Lokal

Ketika membangun tour TSP, semut menerapkan lokal

updating rule mengikuti persamaan (2.12) berikut ini:

𝜏𝑟𝑠 ← (1 − 𝛿)𝜏𝑟𝑠 + 𝛿. 𝜏0 …………………………(2.12)

Dengan 𝛿 adalah parameter evaporasi lokal dengan nilai

bilangan real di antara 0 dengan 1. 𝜏0 adalah nilai awal jejak

pheromone, dimana 𝜏0 = 1𝑛𝐶𝑛𝑛⁄ dengan n adalah jumlah titik

dan Cnn adalah panjang sebuah tour terbaik yang diperoleh dari

metode nearest neighbourhood heuristic.

Persamaan (2.12) ini diaplikasikan saat semut membangun

tour TSP, yaitu ketika melewati edge dan mengubah tingkat

pheromone pada edge (r,s). Tujuannya untuk membantu melewati

sebuah edge, edge ini menjadi kurang diinginkan (karena

berkurangnya jejak pheromone pada edge yang bersesuaian).


34

2.2.5.5. Alur algoritma ACS

Alur algoritma ACS mengikuti langkah-langkah berikut:

1. Lakukan set parameter alpha (α), bheta (β), dan rho (ρ).

2. Lakukan inisialisi kebutuhan data seperti:

a. Adjacency matrix

b. Daftar titik terdekat dari masing-masing titik

c. Rute pheromone inisial

d. Data informasi heuristic pada tiap-tiap jalur yang

menghubungkan antar titik

e. Jika diperlukan, set paramater untuk kondisi terminasi

dapat diatur. Misalnya batasan iterasi, batas konsumsi

memori, dan atau durasi proses.

3. Selama kondisi terminasi tidak terpenuhi maka jalankan:

a. Konstruksi solusi dengan menjalankan;

1) Masing-masing semut memulai perjalanan dari titik

acak.

2) Semut mengujungi kota berikutnya dengan

menerapkan kondisi:

a) Jika probabilitas q terpenuhi, maka jalankan

pencarian dengan menerapkan persamaan (2.9).

b) Jika probabilitas q tidak terpenuhi, maka

jalankan pencarian dengan menerapkan

persamaan (2.1)

3) Setelah semut menemukan kota yang dikunjungi,

lakukan pembaharuan rute pheromone pada jalur

yang menghubungkan kota sebelumnya dengan kota

yang dikunjungi tersebut.

4) Lakukan langkah 3.a.2 dan 3.a.3 sampai seluruh

kota terkunjungi, kemudian atur kota pertama

sebagai kota terakhir.

b. Lakukan update global


35

4. Return semut terbaik sebagai hasil algoritma

Jika langkah-langkah tersebut dipetakan kedalam sebuah

prosedur maka terlihat seperti pada gambar (2.15) di bawah:

Gambar 2.15 Prosedur ACS

Begin-prosedurACS_ACO

Set parameter;

Adjacency matrix;

Daftar ketetanggaan terdekat;

Inisialisasi pheromone awal;

Matrix informasi heuristic;

While(Terminasi == false) do

For i = 0 < banyak semut

Ant[i].rute[0] = random kota

End-for


For j = 1 < banyak kota

If 0 < q < 1 then

Ant[i].rute[j] = 𝑎𝑟𝑔𝑚𝑎𝑥𝑙 ∈ 𝐽𝑟𝑘{[𝜏𝑟𝑢]𝛼[𝜂𝑟𝑢]𝛽}

Else then

Ant[i].rute[j] = [𝜏𝑟𝑠]𝛼.[𝜂𝑟𝑠]𝛽

∑ [𝜏𝑟𝑢]𝛼.[𝜂𝑟𝑢]𝛽𝑢 ∈ 𝐽𝑟

𝑘

End-for

Pembaharuan pheromone lokal

End-for


Ant[i].rute[banyak semut] = Ant[i].rute[0]

Pembaharuan pheromone lokal

End-for

Penguapan pheromone;

Cari semut terbaik;

Pembaharuan pheromone global;

End-while

Return semut terbaik

End-Prosedur


36

BAB III

ANALISIS DAN PERANCANGAN

3.1. Analisis Sistem

Analisis Sistem dilakukan untuk mempelajari dan menganalisa kebutuhan

sistem yang akan dibuat, sehingga dapat dilakukan perancangan dengan kriteria dan

perangkat-perangkat pendukung yang diperlukan. Analisis sistem bertujuan untuk

mengidentifikasi permasalahan yang ada pada sistem di mana aplikasi dibangun.

Analisis ini diperlukan sebagai dasar atau kebutuhan dalam tahap perancangan

sistem.

3.1.1. Gambaran Umum

Sistem dibangun untuk menyelesaikan persoalan Traveling Salesman

Problem (TSP) dengan menerapkan algoritma genetika dan optimasi koloni

semut. Hasil keluaran sistem berupa jarak rute, waktu yang digunakan selama

melakukan proses serta besar kapasitas memori yang digunakan. Sistem

dibuat dan dikembangkan dengan menerapkan prinsip optimalitas, di mana

dalam setiap iterasi olah algoritma hasil iterasi ke-i akan dibandingkan

dengan iterasi sesudahnya atau ke-(i+1).

Dalam algoritma genetika dengan k kromosom yang mewakili k solusi

rute, akan diolah sedemikian rupa dalam setiap iterasinya sehingga dapat

ditemukan rute optimal. Dalam algoritma koloni semut (ACO) dengan l

jumlah semut yang mewakili l jumlah solusi rute, akan diarahkan menuju satu

ragam solusi rute sebagai solusi optimal.

3.1.2. Kebutuhan Pembangunan Sistem

3.1.2.1. Perangkat keras

Perangkat keras adalah alat pendukung yang digunakan sebagai

penunjang pembangunan sistem. Dalam pengembangan sistem ini,

perangkat keras yang digunakan yaitu laptop dengan spesifikasi sebagai


37

berikut:

1. Processor : Intel® Pentium® Dual-Core B950

2. Memori : 2GB, DDR3 1333 MHz SDRAM

3. Hard Drive : 2.5" SATA 500GB 5400 rpm

3.1.2.2. Perangkat lunak

Perangkat lunak adalah program atau aplikasi pendukung, yang

digunakan sebagai penunjang kebutuhan dalam pengembangan sistem.

Perangkat lunak yang dibutuhkan adalah:

1. Sistem Operasi Microsoft Windows 10 Profesional 64bit

2. Netbeans IDE 8.2

3. Java versi “1.8.0_144”

4. Java™ SE Runtime Environment (build 1.8.0_144-b01)

3.2. Analisis Permasalahan

Traveling salesman problem (TSP) adalah permasalahan yang menuntut

penyelesaian secara komputasional. Dalam menyelesaikan TSP, algoritma yang

digunakan harus mematuhi 2 batasan. Batasan yang pertama, semua titik selain titik

keberangkatan hanya dikunjungi sekali. Batasan yang kedua, titik keberangkatan

harus menjadi titik pemberhentian. Dalam membangun solusi penyelesian TSP,

berarti kita menyelesaikan persoalan dengan kemungkinan solusi sebesar n! dengan

n jumlah titik. TSP merupakan persoalan terapan dari teori graph, dan dalam

penelitian ini digunakanlah data masukan berupa berkas yang menyimpan matriks

n x n di dalamnya. Data masukan mempunyai ciri yaitu harga M(i,j) tidak sama

dengan harga M(j,i).

3.3. Algoritma Genetika untuk Travelling Salesman Problem

3.3.1. Pembentukan Populasi Awal

Pembentukan populasi awal dimulai dengan membentuk kromosom-

kromosom sebanyak x buah kromosom. Masing-masing kromosom

mempunyai gen sebanyak (n+1) buah, di mana n adalah banyaknya kota


38

masukan. Pembentukan kromosom dilakukan secara permutasi dengan

menggunakan bilangan asli sebagai inisial kota, dengan kota pertama diberi

inisial 0, kota kedua berinisial 1, dan seterusnya hingga kota ke-n.

Dalam membangun kromosom, misalnya dalam rute yang ditempuh

ditentukan kota (titik) mulai adalah kota pertama (dengan inisial 0) yang

otomatis dijadikan sebagai kota pemberhentian, maka kota-kota selain kota

pertama akan diurutkan secara acak. Untuk lebih mudahnya, dapat dilihat

dalam langkah-langkah di bawah:

1. Terdapat 10 buah kota, maka dibuatlah inisial-inisial kota sebanyak

10 buah. Inisial-inisial tersebut dapat berupa [0-1-2-3-4-5-6-7-8-9].

2. Tentukan titik awal dan akhir, misalnya kota pertama yang

berinisial 0.

3. Selanjutnya lakukan pengacakan terhadap sisa kota yang ada.

Misal diperoleh hasil acak dengan hasil [4-7-2-1-9-6-8-5-3].

4. Setelah pengacakan selesai, tambahkan titik awal dan akhir ke

dalam hasil yang sudah diacak. Pada tahap ini, pembuatan

kromosom sudah slesai dan diperoleh kromosom dengan

kombinasi rute [0-4-7-2-1-9-6-8-5-3-0].

5. Tahap terakhir, dilakukan pengulangan dari langkah 2 sampai 4

sebanyak ukuran populasi.

3.3.2. Fitness

Penghitungan nilai fitness kromosom atau individu dengan

menggunakan persamaan (3.1).

𝑓 = (100𝑗𝑎𝑟𝑎𝑘 𝑟𝑢𝑡𝑒⁄ )…………………………………………(3.1)

Sebenarnya dapat saja jarak kromosom dijadikan sebagai nilai fitness

seperti ditunjukkan dalam tabel (3.1), namun apabila demikian maka kita

tidak memperoleh probabilitas komulatif dengan rentang 0 < 𝑃𝑘 < 1.

𝑃𝑘𝑖 = 𝑃𝑘

𝑖−1 + 𝑃 …………………………………………………(3.2)


39

Tabel 3.1 Fitness Tanpa Pembagian

Kromosom Jarak Total Probabilitas

Kromosom

Probabilitas

Komulatif

1 10000 0.082460625 0.082460625

2 12300 0.101426569 0.183887194

3 7809 0.064393502 0.248280696

4 12092 0.099711388 0.347992084

5 11667 0.096206811 0.444198895

6 10982 0.090558258 0.534757153

7 9002 0.074231055 0.608988208

8 8764 0.072268492 0.6812567

9 14782 0.121893296 0.803149996

10 13872 0.114389379 0.917539375

TOTAL 121270 0.917539375

Dalam menentukan besar bidang atau bilah papan roullete untuk

1 kromosom, kita menggunakan persamaan (3.2). Pada tabel (3.1),

adalah contoh jika kita tidak menggunakan persamaan (3.1) akan

mendapatkan noisy atau terjadinya selisih pada probabilitas komulatif

kromosom terakhir. Namun, tidak akan terjadi noisy jika kita

menerapkan persamaan (3.1) dalam menghitung nilai fitness

kromosom. Dalam tabel (3.2), kita dapat melihat tidak terjadi noisy

pada probabilitas komulatif.

Tabel 3.2 Fitness Dengan Pembagian

Kromosom Jarak

Total Fitness

Probabilitas

Kromosom

Probabilitas

Komulatif

1 10000 0.01 0.107094531 0.107094531

2 12300 0.008130081 0.087068724 0.194163255

3 7809 0.012805737 0.13714244 0.331305695

4 12092 0.008269931 0.088566433 0.419872128

5 11667 0.008571184 0.09179269 0.511664818

6 10982 0.00910581 0.09751824 0.609183058

7 9002 0.011108643 0.118967486 0.728150544

8 8764 0.011410315 0.122198233 0.850348776

9 14782 0.006764984 0.072449284 0.92279806

10 13872 0.007208766 0.07720194 1

TOTAL 121270 0.09337545 1


40

3.3.3. Seleksi

Seleksi individu menggunakan metode roda roullete. Pada metode ini,

pemilihan orang tua berdasar pada nilai fitness-nya. Semakin baik nilai fitness

individu, maka semakin besar peluang untuk dipilih. Diandaikan semua

individu diletakan pada sebuah roda roullete, besarnya kemungkinan bagi

setiap individu adalah tergantung pada probabilitas komulatif kromosom dan

nilai fitness-nya. Lebih jelasnya, dapat dilihat dalam simulasi di bawah:

1. Dibentuk 10 buah kromosom dalam 1 populasi dengan 10 buah

node.

K0 = [0-8-5-4-1-9-3-6-7-2-0] | f = 0,010738831615120275

K1 = [0-8-1-2-9-3-5-7-6-4-0] | f = 0,007612667478684531

K2 = [0-4-2-7-6-1-3-5-9-8-0] | f = 0,007233273056057866

K3 = [0-5-7-1-4-2-8-3-9-6-0] | f = 0,008237910865804433

K4 = [0-7-4-1-8-5-6-3-2-9-0] | f = 0,007829627309740057

K5 = [0-9-38-6-5-7-2-4-1-0] | f = 0,009650646593321753

K6 = [0-2-7-3-9-5-1-6-4-8-0] | f = 0,0070244450688395615

K7 = [0-2-5-3-4-7-1-9-8-6-0] | f = 0,007543753771876886

K8 = [04-5-9-8-3-7-6-1-2-0] | f = 0,005954153021732658

K9 = [0-3-9-7-8-1-4-5-2-6-0] | f = 0,007935248373274084

2. Representasi roda roullete

Sebelum melakukan seleksi dengan roda roullete, terlebih dahulu

kita membutuhkan probabilitas kromosom dalam populasi.

Probabilitas kromosom dapat kita hitung dengan mengunakan

persamaan (3.3).

𝑃 = 𝑓

𝐹…………………………………………………………(3.3)

Dengan f adalah nilai fitness kromosom dan F adalah total fitness

dalam populasi, kemudian diperoleh probabilitas kromosom.

Selanjutnya dapat kita hitung probabilitas komulatif kromosom

dengan menggunakan persamaan (3.2). Hasil kalkulasi dapat dilihat

pada tabel (3.3).


41

Tabel 3.3 Probabilitas Komulatif Seleksi Roullete

Kromosom Fitness Probabilitas

kromosom

Probabilitas

komulatif

0 0,010738831615120275 0,1346383726272761 0,1346383726272761

1 0,007612667478684531 0,09544401080277064 0,23008238343004672

2 0,007233273056057866 0,0906873436459454 0,3207697270759921

3 0,008237910865804433 0,1032830155618416 0,4240527426378337

4 0,007829627309740057 0,09816415016482893 0,5222168928026627

5 0,009650646593321753 0,12099522542995514 0,6432121182326178

6 0,0070244450688395615 0,08806915748139892 0,7312812757140167

7 0,007543753771876886 0,09458000346297488 0,8258612791769916

8 0,005954153021732658 0,07465034390623371 0,9005116230832253

9 0,007935248373274084 0,09948837691677473 1,0

Total 0,079760557 1,0

Berdasarkan hasil kalkulasi pada table di atas, maka diperoleh sebuah

roda roullete seperti gambar (3.1) di bawah.

Gambar 3.1 Roda Roullete


42

3. Hasil jika roda roullete dijalankan sebanyak 2 kali

a) Roullete pertama dijalankan dan diperoleh bilangan random

sebesar 0,124567. Dari tabel (3.3) kita dapat melihat bahwa

bilangan random tersebut terletak di antara 0 dengan probabilitas

komulatif kromosom pertama 0,1346383726272761. Maka

kromosom yang terpilih adalah kromosom K0.

b) Roullete kedua dijalankan dan diperoleh bilangan random

sebesar 0,954423. Dari tabel (3.3) kita dapat melihat bahwa

bilangan random tersebut terletak di antara probabilitas komulatif

kromosom K8 (0,9005116230832253) dengan probababilitas

kromosom K9 (1.0). Maka kromosom yang terpilih adalah

kromosom K9.

3.3.4. Crossover

Order Crossover (OX) diusulkan oleh Davis pada tahun 1985. OX

membangun offspring dengan memilih sub-sequence tour dari satu induk,

kemudian mengambil dari induk satunya lagi kota-kota yang tidak ada di

dalam sub-sequence. Kota-kota yang diambil, ditempatkan secara berurutan

dalam mengisi posisi kosong dalam kromosom. Lebih jelasnya, dapat dilihat

dalam simulasi di bawah:

1. Didapatkan 2 induk hasil roda roullete. Dengan ‘|’ sebagai cut-

point untuk menentukan susequence tour offspring.

P1 = [0 7 4 | 5 3 6 8 | 1 2 9 0]

P2 = [0 2 8 | 1 7 5 6 | 4 9 3 0]

2. Dibentuk 2 buah offspring dengan masing-masing subsequense.

Of1 = [null null null | 5 3 6 8 | null null null null]


3. Untuk mengisi null pada offspring 1, hilangkan kota-kota pada P2

yang sama dengan subsequence pada offspring 1. Kemudian


43

masukan kota yang tidak dihapus secara berurutan untuk mengisi

nilai null.

a) Hilangkan nilai sama


P2 = [0 2 null 1 7 null null 4 9 null 0]

b) Masukan secara berurutan

Of1 = [0 2 1 | 5 3 6 8 | 7 4 9 0]

4. Untuk mengisi null pada offspring 2, hilangkan kota-kota pada P1

yang sama dengan subsequence pada offspring 2. Kemudian

masukan kota yang tidak dihapus secara berurutan untuk mengisi

nilai null.

a) Hilangkan nilai sama

Of2 = [0 null null | 1 7 5 6 | null null null 0]

P1 = [0 null 4 null 3 null 8 null 2 9 0]

b) Masukan secara berurutan

Of2 = [0 4 3 | 1 7 5 6 | 8 2 9 0]

5. Diperoleh hasil crossover

Induk:

P1 = [0 7 4 | 5 3 6 8 | 1 2 9 0]

P2 = [0 2 8 | 1 7 5 6 | 4 9 3 0]

Anak:

Of1 = [0 2 1 | 5 3 6 8 | 7 4 9 0]

Of2 = [0 4 3 | 1 7 5 6 | 8 2 9 0]

3.3.5. Mutasi

Mutasi kromosom dilakukan dengan menukar gen ke-dua di awal

dengan gen ke-dua di akhir. Penukaran gen ini dirasa cukup efektif mengingat

mutasi tidak boleh mengubah struktur gen secara massif, hal ini dilakukan

untuk menghindari terjadi noisy. Hasil mutasi setidaknya memiliki 90%

struktur gen yang sama dengan induknya. Misalnya kita mempunyai induk

dengan kromosom [0 2 1 5 3 6 8 7 4 9 0]. Kemudian dilakukan penukaran gen


44

ke-3 pertama dengan gen ke-3 terakhir dan didapatkan kromosom hasil

mutasi dengan kromosom keturunan [0 2 |4| 5 3 6 8 7 |1| 9 0].

3.4. Ant Colony System (ACS) untuk Travelling Salesman Problem

3.4.1. Parameter Pendukung

Mengutip dari Stutzle & Dorigo (2004), beberapa hal yang perlu

dipersiapkan adalah matriks jarak yang sudah siap digunakan, daftar nearest-

neighbor untuk setiap titik, pheromone dan informasi heuristic awal perlu

diinisialisasikan, inisialisasi semut-semut, dan beberapa parameter-parameter

algoritma seperti alpha, beta, dan lain-lain, serta kondisi terminasi perlu

ditentukan.

Kondisi terminasi merupakan hal yang opsional, sebab ada berbagai

pilihan untuk itu seperti menentukan iterasi maksimal, maksimal waktu olah

CPU, dan variable elit atau best-so-far.

3.4.1.1. Matriks Nearest-Neighbor

Matriks nearest-neighbor diperlukan dalam mencari rute inisial

dan diperlukan dalam tahap konstruksi solusi. Untuk mencari matriks

tersebut dapat dilihat dalam langkah-langkah di bawah ini:

1. Pertama-tama, persiapkan sebuah variable array 2 dimensi

dengan ukuran n x n di mana n sama dengan banyak titik.

2. Dari kota pertama terhadap semua titik yang ada, lakukan

pengurutan jarak terdekat sampai terjauh. Kemudian

masukan ke dalam matriks nearest-neighbor.

3. Lanjutkan langkah 2 sampai seluruh kota yang tersisa.

3.4.1.2. Rute Inisial

Rute inisial atau best-so-far tour adalah variable yang digunakan

sebagai rute elit algoritma. Dalam setiap iterasi, isi variable ini akan

dibandingkan dengan tur terbaik. Isi variable ini akan diganti setiap kali

ditemukan rute baru yang lebih baik. Namun pada saat algoritma


45

menjalankan iterasi yang pertama, isi variable ini tetap dijadikan

sebagai pembanding. Selain itu, isi variable ini digunakan dalam proses

inisialisasi pheromone.

Untuk mencari rute inisial, dimanfaatkan matriks nearest-

neighbor. Lebih jelasnya dapat dilihat dalam langkah-langkah di bawah

ini:

1. Siapkan sebuah aray sepanjang n+1. Kemudian masukkan

kota sebagai titik keberangkatan, atau rute[0] = nn[0][0] lalu

atur rute[0] sebagai pernah dikunjungi atau dapat

menggunakan teknik boolean dengan rute[0].visited = true.

2. Untuk i = 1, masukan isi matriks nn[0][1] ke dalam array

rute[i] lalu atur rute[i] sebagai pernah dikunjungi atau

rute[i].visited = true.

3. Untuk j = 0, i = i + 1, dan k = rute[j+1], periksa apakah isi

matriks nn[k][j] pernah dikunjungi atau tidak. Jika belum

dikunjugi maka masukan isi matriks nn[k][j] ke dalam array

rute[i] lalu atur rute[i] sebagai pernah dikunjungi atau

rute[i].visited = true. Jika ternyata pernah dikunjungi, maka

ulangi langkah tiga serta mengisi variable j dengan j = j + 1.

Penambahan nilai variable j bertujuan untuk mencari kota

terdekat kedua dalam urutan matriks nearest-neighbor.

4. Ulangi langkah 3 selama i lebih kecil dari n.

5. Langkah terakhir memasukan isi rute[0] ke dalam rute[n+1].

Langkah ini dilakukan supaya terjadinya cycling rute yang

merupakan syarat terjadinya TSP.

3.4.1.3. Matriks Pheromone

Dalam menyiapkan pheromone, diperlukan rute inisial. Matriks

pheromone ini merupakan set pheromone inisial sebagai pheromone

global. Nantinya, setelah satu iterasi selesai dijalankan maka isi matriks

pheromone inilah yang akan diperbaharui dengan persamaan (. Matriks


46

pheromone mempunyai ukuran yang sama dengan matriks jarak yaitu

n x n. Langkah-langkah yang dilakukan dalam mempersiapkan

pheromone adalah:

1. Persiapkan sebuah matriks dengan ukuran n x n.

2. Untuk i = 1 dan j = 1, isi matriks P[i][j] dengan

100𝑗𝑎𝑟𝑎𝑘 𝑖𝑛𝑖𝑠𝑖𝑎𝑙 𝑡𝑟𝑎𝑖𝑙⁄

3. Dengan i = 1 dan j = j + 1, lakukan langkah 2 sampai j = n.

4. Dengan i = i + 1, lakukan langkah 3 sampai i = n.

3.4.2. Konstruksi Solusi

Konstruksi solusi, dapat mengikuti langkah-langkah berikut:

1. Kosongkan tabulist masing-masing semut. Seluruh kota ditandai

dengan belum dikunjungi.

2. Masing-masing semut memulai dari kota awal. Kota-kota diambil

secara acak.

3. Masing-masing semut menyelesaikan tur dengan menerapkan

aturan transisi satus persamaan (2.9).

4. Setelah semua semut mengunjungi seluruh kota, maka tur

dikatakan selesai.

Dalam aturan transisi status pada langkah ke-3, probabilitas dalam

dipilih atau tidaknya sebuah kota untuk dikunjungi tergantung pada roda

roullete. Dikatakan roda roullete karena variable random q seperti yang

ditunjukan dalam persamaan (2.9), jika q lebih kecil atau sama dengan q0

maka jalur yang dipilih adalah jalur yang mempunyai info heuristik tertinggi

selama kota tujuan belum dikunjungi. Selain itu, jika q lebih besar dari q0

maka jalur yang dipilih selanjutnya mengikuti persamaan (2.1). Setelah semut

menentukan kota berikutnya yang akan dikunjungi, maka kadar pheromone

di jalur yang sudah dilewati diperbaharui sesuai persamaan (2.12).

Dalam random proportional rule yang ditunjukkan oleh persamaan

(2.1), dengan 0 apabila s lainnya, dapat dimodifikasi dengan memanfaatkan

matriks nearest-neighbor. Hal ini dilakukan untuk memaksa pencarian titik


47

tetap berlanjut. Lagipula, dalam prosesnya pemilihan melalui matriks

nearest-neighbor jarang terjadi, sebab status (kondisi) terkunjungi atau

belumnya sebuah kota/titik dapat saja selalu terpenuhi saat persamaan (2.9)

dan persamaan (2.1) dijalankan.

3.4.3. Perbaharuan

Pheromone lokal selalu diperbaharui setiap kali semut berhasil

menemukan satu titik yang akan dikunjungi. Pembaharuan pheromone lokal

berdasarkan persamaan (2.12), sedangkan pheromone global diperbaharui

setelah semua semut selesai melakukan perjalanan. Pembaharuan pheromone

global berdasarkan pada persamaan (2.9). Namun sebelum pheromone global

diperbaharui, jalur pheromone mengalami penguapan dengan melibatkan

parameter rho.

3.4.4. Kondisi diakhiri

Program akan berakhir ketika mencapai batasan yang ditentukan

dengan memanfaatkan rute inisial sebagai pembanding dalam setiap

iterasinya. Misalkan kita mempunyai rute inisial [7-0-5-6-1-3-9-8-2-4-7]

dengan dan jarak rute sejauh 8509.0, maka kemudian dalam setiap iterasinya

rute inisial akan dibandingkan dengan rute terbaik yang ditemukan dalam

iterasi itu. Jika rute terbaik lebih buruk dibandingkan rute inisial, maka rute

inisial tidak akan berubah. Namun, jika ternyata rute terbaik yang ditemukan

lebih dekat jaraknya dibandingkan rute inisial, maka rute terbaik tersebut

akan dijadikan sebagai rute inisial. Selain itu digunakan variable bertipe

integer sebagai pembatas. Selama batas belum terpenuhi maka pembandingan

rute inisial dengan rute terbaik iterasi akan terus dilakukan.

3.5. Rancangan Pengujian Sistem

Kedua algoritma yang dibangun, akan diuji pada 10 buah data masing-masing

dilakukan sebanyak 10 kali pengujian. Jika masing-masing algoritma mempunyai

attribut yang akan dibandingkan, attribut tersebut adalah jarak dengan satuan

kilometer atau Km, konsumsi memori dengan satuan Byte, dan waktu dengan


48

satuan milidetik (millisecond) atau ms.

Dari 10 kali pengujian, kemudian diperoleh rata-rata dari masing-masing

attribut yaitu rata-rata jarak, rata-rata memori, dan rata-rata waktu. Selain mencari

rata-rata, nilai terbaik yaitu nilai minimal value selama 10 kali percobaan juga akan

digunakan sebagai pembanding. Untuk masing-masing data pengujian, digunakan

tabel seperti pada tabel (3.4) di bawah.

Tabel 3.4 Rancangan pengujian sistem

Pengujian Jarak (Km) Memori (Byte) Waktu (ms)

Ke-1

Ke-2

Ke-3

Ke-4

Ke-5

Ke-6

Ke-7

Ke-8

Ke-9

Ke-10


49

BAB IV

IMPLEMENTASI DAN PENGUJIAN

4.1. Java Virtual Machine (JVM) Runtime

JVM runtime di-import dari class java.lang.Runtime() dengan 2 metode yang

diterapkan dalam penelitian ini untuk memperoleh konsumsi memori yang

digunakan masing-masing algoritma. Detail metode yang digunakan dapat dilihat

dalam table (4.1) di bawah. Penghitungan jumlah memori yang dipakai selama

algoritma dijalankan digunakan metode freeMemory(), namun terlebih dahulu

dilakukan teknik pengumpulan sampah atau garbage collection dengan metode

gc(). Pengumpulan sampah merupakan teknik manajemen memori yang membuat

programmer tidak perlu secara manual membebaskan memori dari objek yang tidak

terpakai.

Tabel 4.1 Metode Class Runtime

Tipe Metode dan Deskripsi

long public long totalMemory()

Mengembalikan jumlah total memori yang dialokasikan oleh mesin

virtual Java. Nilai yang dikembalikan dengan metode ini dapat bervariasi

dari waktu ke waktu, tergantung pada lingkungan host. Jumlah memori

yang dialokasikan diukur dalam satuan byte.

long public long freeMemory()

Mengembalikan jumlah memori tersisa di Java Virtual Machine.

Perkiraan ke jumlah memori yang tersisa/tersedia untuk objek yang

dialokasikan di masa mendatang, diukur dalam satuan byte.

4.2. Waktu Olah Sistem

Dalam menghitung lama proses dijalankan, penelitian ini menerapkan metode

currentTimeMillis() yang diimport dari class java.lang.System(). Dengan metode

bertipe long, metode ini memberi kembalian berupa waktu saat ini dalam milidetik.


50

Perhatikan bahwa unit waktu pengembalian nilai adalah milidetik, dan waktu yang

dicari adalah waktu saat ini, maka untuk mencari lamanya sistem beroperasi

diperlukan 2 variable yaitu waktu sebelum proses dimulai (start time) dan waktu

setelah proses selesai (end time) dan lamanya sistem beroperasi adalah

𝑐𝑢𝑟𝑟𝑒𝑛𝑡 𝑡𝑖𝑚𝑒 = (𝑒𝑛𝑑 𝑡𝑖𝑚𝑒 − 𝑠𝑡𝑎𝑟𝑡 𝑡𝑖𝑚𝑒).

4.3. Implementasi Genetika

4.3.1. Class Kromosom

Class Kromosom diterapkan untuk mengendalikan 1 kromosom atau

kromosom tunggal. Dalam satu populasi terdapat g gen. Gen-gen ini disimpan

dalam satu variable bertipe ArrayList<Integer>.

4.3.1.1. Ringkasan Metode

Ringkasan metode yang ada dalam class kromosom dapat dilihat

dalam tabel (4.2) di bawah ini.

Tabel 4.2 Ringkasan Metode Dalam Class Kromosom


void bersihkanKromosom()

Membersihkan isi variable kromosom tunggal

void bangkitkanKromosom(int sizeKromosom)

Membentuk sebuah kromosom tunggal

double fittnessKromosom(double graph[][])

Memberikan kembalian berupa nilai fitness kromosom

double jarakTotalKromosom(double graph[][])

Memberikan kembalian berupa jarak cycling rute pada

kromosom


51

4.3.1.2. Detail Metode

4.3.1.2.1. bersikanKromosom()

public void bersihkanKromosom()

Variable kromosom tunggal dengan tipe arrayList<Integer>

digunakan berulang-ulang dalam proses pembentukan kromosom

populasi, oleh karena itu perlu pembersihan variable supaya tidak

terjadinya duplikasi dari proses sebelumnya.

4.3.1.2.2. bangkitkanKromosom(int sizeKromosom)

public void bangkitkanKromosom(int sizeKromosom)

Kromosom dalam populasi yang dibentuk memiliki

kombinasi dengan gen-gen berupa inisial dari titik-titik kota yang

merupakan representasi dari rute travelling.

4.3.1.2.3. fittnessKromosom(double graph[][])

public double fittnessKromosom(double graph[][])

Metode ini untuk mengembalikan nilai fitness sebuah

kromosom. Perlu dicatat, fitness sebuah kromosom, semakin

besar nilainya maka semakin bagus.

4.3.1.2.4. jarakTotalKromosom(double graph[][])

public double jarakTotalKromosom(double graph[][])

Metode ini memberikan keluaran berupa nilai dari jarak

tempuh rute kromosom. Untuk i = 1 sampai i = n, jarak kromosom

dihitung dengan total = total + graph[kromosom.get(i-

1)][kromosom.get(i)].

4.3.2. Class Populasi

Class Populasi diterapkan untuk mengendalikan satu populasi. Dalam

satu populasi terdapat m kromosom. Kromosom-kromosom ini disimpan

dalam satu variable bertipe ArrayList<Kromosom>.


52


Ringkasan metode yang ada dalam class Populasi dapat dilihat

dalam tabel (4.3) di bawah ini.

Tabel 4.3 Ringkasan Metode Dalam Class Populasi


double fitnessPopulasi(double graph[][])

Memberikan kembalian berupa total fitness populasi

Kromosom fittestPopulasi(double graph[][])

Memberikan kembalian berupa kromosom terbaik

dalam populasi

int flacidPopulasi(Populasi pop, double graph[][])

Memberikan kembalian berupa nomor lokasi

kromosom terjelek dalam populasi

double probKromosom(Kromosom kromosom, double

totFittness, double graph[][])

Memberikan kembalian berupa nilai probabilitas

sebuah kromosom dalam populasi

double ProbKomulatif(int index,double graph[][])

Memberikan kembalian berupa nilai probabilitas

komulatif satu kromosom dalam populasi

int rodaRoulete(double graph[][])

Memberikan kembalian berupa posisi kromosom

yang terpilih melalui roda roullete

Kromosom[] xo_DO(Kromosom p1, Kromosom p2)

Memberikan kembalian berupa 2 buah kromosom

hasil crossover

Kromosom mutasi(Kromosom parent)

Memberikan kembalian berupa kromosom hasil

mutasi


53


4.3.2.2.1. fitnessPopulasi(double graph[][])

public double fitnessPopulasi(double graph[][])

Metode ini memberikan keluaran berupa jumlah total

fitness dari populasi. Jika dalam satu populasi terdapat k buah

kromosom/individu, maka total fitness populasi adalah

penjumlahan dari fitness-fitness kromosom dalam populasi

tersebut.

4.3.2.2.2. fittestPopulasi(double graph[][])

public Kromosom fittestPopulasi(double graph[][])

Metode ini memberikan kembalian nilai berupa sebuah

kromosom terbaik dalam satu populasi. Kromosom terbaik dipilih

berdasarkan nilai fitness tertinggi.

4.3.2.2.3. flacidPopulasi(Populasi pop, double graph[][])

public int flacidPopulasi(Populasi pop, double graph[][])

Metode ini memberikan kembalian berupa posisi

kromosom terjelek dari seluruh kromosom dalam populasi.

Kromosom terjelek ditandai dengan nilai fitness yang paling

rendah.

4.3.2.2.4. probKromosom(Kromosom kromosom, double

totFittness, double graph[][])

public double probKromosom(Kromosom kromosom,

double totFittness, double graph[][])

Metode ini melakukan kalkulasi terhadap satu buah

kromosom dalam populasi dan hasil keluarannya berupa data

bertipe double. Probabilitas kromosom dihitung dengan membagi

nilai fitness kromosom dengan total fitness dalam populasi.


54

4.3.2.2.5. ProbKomulatif(int index,double graph[][])

public double ProbKomulatif(int index,double graph[][])

Metode ini melakukan kalkulasi terhadap sebuah satu buah

kromosom dalam populasi dan hasil keluarannya berupa sebuah

data bertipe double. Keluaran metode dari ini merupakan nilai

probabilitas komulatif kromosom tersebut.

4.3.2.2.6. rodaRoulete(double graph[][])

public int rodaRoulete(double graph[][])

Metode ini melakukan sebuah proses yang dinamakan

roullete whell atau roda roullete. Keluaran dari metode ini berupa

posisi atau alamat kromosom dalam populasi. Nilai keluaran

bertipe integer karena dalam satu populasi terdiri dari banyak

kromosom, dan masing-masing kromosom memiliki alamat.

Alamat yang dimaksud adalah posisi kromosom dalam arrayList

populasi.

4.3.2.2.7. xo_DO(Kromosom p1, Kromosom p2)

public Kromosom[] xo_DO(Kromosom p1, Kromosom p2)

Metode ini melakukan sebuah proses persilangan antara

kromosom p1 dengan kromosom p2, yang kemudian membentuk

2 buah kromosom baru sekaligus keluaran dari metode ini. Dua

kromosom baru hasil persilangan secara umum disebut child.

4.3.2.2.8. mutasi(Kromosom parent)

public Kromosom mutasi(Kromosom parent)

Dalam metode ini, proses penukaran gen dalam satu

kromosom (parent) dilakukan. Kromosom yang merupakan hasil

kembalian dari metode ini, adalah kromosom yang sama sekali

berbeda dari induknya. Sesuai konsep dalam ilmu Biologi, mutasi

adalah perubahan gen dalam kromosom.


55

4.3.3. Class Genetika

Class genetika merupakan class utama atau class induk dalam

algoritma ini. Dalam class genetika, proses-proses inti dijalankan seperti

membentuk, mengontrol, dan mengubah isi dalam populasi.


Ringkasan metode-metode yang ada dalam class Genetika dapat

dilihat dalam tabel (4.4) di bawah ini.

Tabel 4.4 Ringkasan Metode Dalam Class Genetika


Kromosom run_genetika(double graph[][])

Memberikan kembalian berupa sebuah kromosom

yang merupakan representasi rute travelling dari hasil

olah algoritma genetika.

Populasi bangkitkanPopulasi(int ukuranKromosome, int

ukuranPopulasi)

Memberikan kembalian berupa populasi yang terdiri

dari kromosom-kromosom


4.3.3.2.1. run_genetika(double graph[][])

public Kromosom run_genetika(double graph[][])

Metode ini digunakan untuk melakukan proses utama pada

algoritma genetika dan kemudian memberikan kembalian berupa

sebuah kromosom yang merupakan representasi rute travelling.

4.3.3.2.2. bangkitkanPopulasi(int ukuranKromosome, int

ukuranPopulasi)

public Populasi bangkitkanPopulasi(int

ukuranKromosome, int ukuranPopulasi)


56

Dalam metode ini, kromosom populasi dibangkitkan.

Metode ini digunakan untuk mencari populasi awal dalam

algoritma genetika, dan kembalian dari metode ini berupa satu

buah populasi.

4.4. Implementasi ACS

4.4.1. Class Ant

Class ini mewakili 1 semut dengan 2 variable lokal yaitu rute[] dan

visited[]. Variable rute[] merupakan variable yang menyimpan rute yang

ditempuh semut, sedangkan visited[] merupakan taboo list semut.


Ringkasan metode-metode yang ada dalam class Ant dapat dilihat

dalam tabel (4.5) di bawah.

Tabel 4.5 Ringkasan Metode Dalam Class Ant


void clear()

Membersihkan taboo list titik-titik yang akan

dikunjungi.

double getTourLength(double Graph[][])

Memberikan kembalian berupa jarak tempuh semut

terhadap rute yang dipilihnya.


4.4.1.2.1. clear()

protected void clear()

Metode ini digunakan untuk membersihkan daftar-daftar

kota yang tersimpan dalam taboo list semut. Pembersihan yang

dimaksud adalah mengkondisikan kota-kota menjadi belum

terkunjungi.


57

4.4.1.2.2. getTourLength(double Graph[][])

public double getTourLength(double Graph[][])

Metode ini digunakan untuk menghitung jarak temput

semut setelah melewati rute yang dipilihnya. Keluaran metode ini

berupa data bertipe double.

4.4.2. Class ACS

Class ACS merupakan kelas utama yang mengatur, mengontro, dan

mengendalikan semut-semut dalam koloni.


Ringkasan metode-metode yang ada dalam class Genetika dapat

dilihat dalam tabel (4.6) di bawah.

Tabel 4.6 Ringkasan Metode Dalam Class ACS


Ant run_colony(double Graph[][])

Memberikan kembalian berupa semut dengan rute

terbaik selama algoritma ACS dijalankan.

void prepare_allVariablesAndParams(double Graph[][])

Metode ini melakukan proses inisialisasi seluruh

parameter yang diperlukan dalam algoritma ACS.

int[][] prepareNearestNeighbour(double[][] Graph)

Metode ini memberikan kembalian berupa matriks

nearest-neighbor.

Ant compute_initial_trail()

Metode ini memberikan kembalian berupa rute inisial

awal.

void preparePheromoneTrail()

Metode ini melakukan kalkulasi dan memasukan data

ke dalam matriks pheromone.

double[][] heuristic_information(double[][] Graph)


58


informasi heuristic.

double[][] choice_info(double[][] Graph)


informasi pemilihan.

void init_ants()

Metode ini digunakan untuk menginisialisasi jumlah

semut yang akan digunakan dalam algoritma ACS.

void constructSolution()

Metode ini digunakan untuk mengkonstruksi rute

yang ditempuh oleh semut-semut dalam koloni.

void choose_and_move_to_next(Ant ant, int step)

Metode ini merupakan penerapan dari persamaan

(2.9).

int choose_best_next(Ant ant, int step)

Metode memberikan kembalian berupa kota

selanjutnya yang akan dipilih oleh semut.

int pseudo_rand_proportional_rule(Ant ant, int step)

Metode ini memberikan kembalian berupa kota yang

akan dikunjungi selanjutnya, berdasarkan pada aturan

transisi status AS.

int nn_choose_and_move_to_the_next(Ant ant, int step)

Metode ini memberikan kembalian berupa kota yang

akan dikunjungi selanjutnya, berdasarkan matriks

nearest-neighbor.

void local_pheromone_update(Ant ant, int step)

Metode ini melakukan pembaharuan terhadap matriks

pheromone dan matrik informasi pilihan.

void update_initial_trail()

Metode ini melakukan pembaharuan terhadap rute


59

inisial algoritma ACS.

void pheromone_evaporation()

Metode ini melakukan pembaharuan berupa

penguapan terhadap intensitas pheromone dalam

matriks pheromone.

void global_pheromone_update()

Melakukan pembaharuan terhadap intensitas

pheromone dalam matriks pheromone secara global


4.4.2.2.1. run_colony(double Graph[][])

public Ant run_colony(double Graph[][])

Dalam metode run_colony(), algoritma ACS dijalankan.

Keluaran dari metode ini adalah satu semut yang mempunyai rute

terbaik sepanjang iterasi. Satu semut terbaik ini dinamai semut

elit.

4.4.2.2.2. prepare_allVariablesAndParams(double Graph[][])

public void prepare_allVariablesAndParams(double

Graph[][])

Metode ini digunakan untuk menyiapkan seluruh variable

dan parameter yang diperlukan dalam algoritma ACS. Beberapa

hal yang perlu disiapkan diantaranya matriks jarak, jumlah semut,

matriks pheromone, matriks informasi heuristic, matriks

informasi pilihan, matriks nearet-neighbor, dan rute inisial.

4.4.2.2.3. prepareNearestNeighbour(double[][] Graph)

protected int[][] prepareNearestNeighbour(double[][]

Graph)

Metode ini melakukan kalkulasi berupa pencarian nearest-

neighbor dari seluruh titik yang ada. Hasil kembalian metode ini

adalah matriks nearest-neighbor.


60

4.4.2.2.4. compute_initial_trail()

public Ant compute_initial_trail()

Metode ini melakukan kalkulasi dalam mencari rute inisial

berdasarkan matriks nearest-neighbor. Kembalian metode ini

berupa seekor semut dengan rute travelling. Rute inisial yang

merupakan hasil dari metode ini selanjutnya akan dibandingkan

dengan rute terbaik dalam setiap iterasi.

4.4.2.2.5. preparePheromoneTrail()

protected void preparePheromoneTrail()

Metode ini melakukan kalkulasi dan mengisi data

pheromone ke dalam matriks pheromone. Matriks pheromone

hasil olahan metode ini, merupakan pheromone inisial yang akan

terus diperbaharui pada proses-proses berikutnya.

4.4.2.2.6. heuristic_information(double[][] Graph)

protected double[][] heuristic_information(double[][]

Graph)

Metode ini melakukan kalkulasi dan menghasilkan sebuah

matriks informasi heuristic. Matriks informasi heuristic ini

diperlukan oleh semut dalam menentukan titik yang akan

dikunjungi selama pembangunan rute travelling.

4.4.2.2.7. choice_info(double[][] Graph)

protected double[][] choice_info(double[][] Graph)

Metode ini melakukan kalkulasi dan menghasilkan sebuah

matriks informasi pilihan. Matriks ini sebagai pertimbangan bagi

semut dalam menentukan titik yang akan dikunjungi selama

pembangunan rute travelling.

4.4.2.2.8. init_ants()

private void init_ants()

Metode ini menyiapkan semut untuk melakukan proses


61

dalam algoritma ACS. Semut sebanyak m ekor, ditambahkan ke

dalam koloni. Satu koloni semut direpresentasikan oleh satu

variable bertipe arrayList<Ant>.

4.4.2.2.9. constructSolution()

public void constructSolution()

Dalam metode ini, seluruh semut dalam koloni akan

membentuk sebuah rute travelling. Sebelum metode ini

dijalankan, terlebih dahulu diperlukan m ekor semut dengan

taboo list yang sudah dibersihkan.

4.4.2.2.10. choose_and_move_to_next(Ant ant, int step)

private void choose_and_move_to_next(Ant ant, int step)

Dalam metode ini, kalkulasi menurut persamaan (2.9)

dijalankan dengan probabilitas q ditentukan secara random pada

rentang 0 < q < 1. Jika batasan q terpenuhi maka kota yang akan

dikunjungi selanjutnya ditentukan berdasarkan hasil metode

choose_best_next(ant, step). Apabila batasan q tidak terpenuhi,

maka kota yang dikunjungi selanjutnya ditentukan berdasarkan

hasil metode pseudo_rand_proportional_rule(ant, step). Namun

jika kota hasil kedua metode tersebut ternyata sudah dikunjungi

sebelumnya, maka kota yang akan dikunjungi selanjutnya dipilih

berdasarkan matriks nearest-neighbor.

4.4.2.2.11. choose_best_next(Ant ant, int step)

private int choose_best_next(Ant ant, int step)

Dalam metode ini, kota yang akan dikunjungi selanjutnya

ditentukan berdasarkan matriks choice info dengan value terbaik.

Keluaran metode ini berupa nilai integer yang merupakan inisial

titik kota yang akan dikunjungi selanjutnya.

4.4.2.2.12. pseudo_rand_proportional_rule(Ant ant, int step)

private int pseudo_rand_proportional_rule(Ant ant, int


62

step)

Metode ini memberikan keluaran berupa titik yang akan

dikunjungi selanjutnya. Titik ditentukan berdasarkan persamaan

(2.1) atau teknik random proportional rule pada algoritma Ant

System (AS).

4.4.2.2.13. nn_choose_and_move_to_the_next(Ant ant, int step)

private int nn_choose_and_move_to_the_next(Ant ant,

int step)

Metode ini memberikan kembalian berupa kota yang akan

dikunjungi selanjutnya berdasarkan pencarian dari matriks

nearest-neighbor. Metode ini mencari titik yang belum

dikunjungi dengan mengakses taboo list semut.

4.4.2.2.14. local_pheromone_update(Ant ant, int step)

public void local_pheromone_update(Ant ant, int step)

Metode ini melakukan kalkulasi dan memperbaharui

matriks pheromone dan matriks choice info. Kalkulasi dan

perbaharuan dilakukan setiap kali setelah semut melewati satu

titik.

4.4.2.2.15. update_initial_trail()

private void update_initial_trail()

Metode ini memperbaharui rute inisial algoritma ACS

setiap kali 1 iterasi selesai dijalankan. Pembaharuan dilakukan

dengan membandingkan harga rute insial dengan harga rute

tempuh semut terbaik dalam iterasi saat itu.

4.4.2.2.16. pheromone_evaporation()

private void pheromone_evaporation()

Dalam metode ini, tahap penguapan pheromone dalam jalur

terjadi. Seluruh pheromone mengalami perubahan intensitas

berdasarkan parameter rho. Penguapan terjadi setelah 1 iterasi


63

selesai dijalankan atau setelah seluruh semut menyelesaikan tur

mereka.

4.4.2.2.17. global_pheromone_update()

private void global_pheromone_update()

Dalam metode ini, matriks pheromone mengalami

pembaharuan. Berdasarkan teori, jalur pheromone setelah

menguap memiliki kadar berbeda-beda. Semakin jalur yang

ditempuh adalah jalur terdekat, maka kadar pheromone pada jalur

semakin kuat.

4.5. Genetika Untuk TSP

4.5.1. Kromosom

Kromosom dikodekan ke dalam bahasa pemrograman java, dengan

kode seperti pada gambar (4.1) di bawah ini:

Gambar 4.1 Kode Kromosom

Satu kromosom disimpan dalam 1 arraylist dengan panjang n+1 untuk

n adalah banyak titik yang akan ditempuh. Dalam kode pada gambar (4.1)

untuk baris 3 sampai dengan 5 dilakukan penginisialan terhadap titik-titik

kota sebanyak n jumlah titik, penginisialisasian titik menggunakan inisial

angka dengan inisial dari 0, 1, 2, 3…., n. Pada baris ke-6 dilakukan

pengacakan. Pengacakan ini sekaligus penginisialisasian terhadap seluruh

titik yang ada.

Pada baris 7, titik pertama dalam kromosom tunggal digandakan ke


64

dalam titik terakhir. Penggandaan ini bertujuan membentuk cycling rute

kromosom. Hasil dari kode ini, diharapkan membentuk sebuah kromosom

dengan kombinasi titik-titik acak yang mewakili rute travelling.

Gambar 4.2 Uji Metode Pembentukan Kromosom

Dalam gambar (4.2) ditunjukkan bagaimana sistem membangun

serangkaian gen dan menjadikannya sebuah kromosom. Kromosom yang

terbentuk mewakili sebuah cycling rute travelling. Sebagai pembanding

apakah sistem sudah berjalan dengan benar, dilakukanlah uji secara manual

dengan masukan 10 buah titik, maka proses-proses yang terjadi adalah

sebagai berikut:

1. Dengan n adalah jumlah titik, maka n = 10

2. Sebuah variable kromosom sementara, dengan tipe arraylist.

List<Integer> kromosom = new ArrayList<Integer>();

3. Untuk m = 0 sampai m = 10-1; masukan i ke dalam variable

kromosom.

G0 G1 G2 G3 G4 G5 G6 G7 G8 G9

0 1 2 3 4 5 6 7 8 9

4. Dilakukan pengacakan terhadap gen-gen kromosom.

G0 G1 G2 G3 G4 G5 G6 G7 G8 G9

7 4 8 3 1 9 6 0 2 5


65

5. Gen pertama dalam kromosom digandakan ke dalam gen terkahir.

G0 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10

7 4 8 3 1 9 6 0 2 5 7

6. Maka diperoleh sebuah kromosom tunggal dengan kombinasi

kromosom [7-4-8-3-1-9-6-0-2-5-7]

Dari hasil uji (percobaan) manual di atas diperoleh kromosom tunggal

dengan kombinasi [7-4-8-3-1-9-6-0-2-5-7]. Kromosom tunggal yang

dihasilkan berupa kombinasi acak dari 10 titik masukan, selain itu cycling

rute juga terbentuk. Dengan demikian dapat dikatakan bahwa sistem sudah

berjalan dengan benar.

4.5.2. Populasi

Pembentukan populasi terutama populasi awal, dikodekan ke dalam

bahasa pemrograman java dengan kode seperti pada gambar (4.3) di bawah.

Gambar 4.3 Kode Populasi Awal

Satu populasi disimpan dalam 1 arraylist dengan kapasitas sebanyak 10

buah kromosom. Dalam kode pada gambar (4.3) untuk baris 3 dibentuk

sebuah variable lokal bertipe populasi, dan pada baris 4 dibentuk sebuah

variable untuk menyimpan sebuah kromosom secara sementara. Pada baris 5

sampai dengan 9, dilakukan penyimpanan kromosom-kromsom sebanyak 10


66

buah ke dalam variable populasi lokal. Pada baris ke-10 sampai 11, isi

variable (lokal) populasi dijadikan sebagai populasi awal dan dikembalikan

sebagai hasil keluaran metode.

Sebagai pengujian sistem, digunakan data dengan 10 buah titik kota.

Populasi awal yang terbentuk dapat dilihat dalam gambar (4.4) di bawah.

Dalam gambar (4.4), terlihat satu populasi terdiri atas 10 buah kromosom

dengan masing-masing kromosom terdiri atas serangkaian gen sepanjang n+1

untuk n adalah jumlah kota. Setiap 1 kromosom terbentuk dengan gen yang

terkombinasi secara acak. Pembentukan populasi awal oleh sistem, dapat

dikatakan berhasil dan sesuai dengan hasil yang diharapkan.

Gambar 4.4 Populasi Awal Hasil Uji Sistem

4.5.3. Fitness

4.5.3.1. Fitness Kromosom

Penghitungan nilai fitness kromosom, dikodekan ke dalam

bahasa pemrograman java dengan kode seperti pada gambar (4.5) di

bawah.

Gambar 4.5 Kode Fitness Kromosom


67

Metode yang digunakan dalam mencari nilai fitness kromosom

hanya diterapkan untuk mengatasi 1 kromosom. Nilai fitness

kromosom dihitung pada baris ke 2 dalam kode pada gambar (4.5).

Untuk mengetahui apakah sistem menghitung dengan benar maka perlu

adanya pembandingan hasil sistem dengan hasil perhitungan secara

manual.

Gambar 4.6 Hasil Uji Fitness Kromosom

Pada gambar (4.6) di atas, dengan menggunakan data seperti pada

tabel (4.7) ada 5 buah kota yang diolah, diperoleh sebuah kromosom

dengan kombinasi [3-1-4-2-0-3]. Kromosom yang dihasilkan, menurut

perhitungan sistem mempunyai jarak tempuh sebesar 4.881 Km dan

nilai fitness sebesar 0,020785699438786116. Apabila merujuk pada

tabel (4.7) sebagai data, maka secara manual diperoleh:

1. Jarak tempuh = (3-1) + (1-4) + (4-2) + (2-0) + (0-3)

= 656 + 680 + 809 + 569 + 2.097 = 4.811

2. Fitness = 100

𝐽𝑎𝑟𝑎𝑘 𝑇𝑒𝑚𝑝𝑢ℎ =

100

4.811 = 0,0207856994

Terlihat bahwa nilai fitness yang dihasilkan oleh sistem, sama

dengan nilai fitness hasil perhitungan manual. Dengan demikian, sistem

sudah berjalan dengan benar.


68

Tabel 4.7 Data Masukan 5 Kota

Ke

Dari

0 1 2 3 4

0 9999999 1619 528 2097 1310

1 1593 9999999 1297 723 680

2 569 1191 9999999 1781 780

3 2056 656 1682 9999999 1023

4 1327 595 809 996 9999999

4.5.3.2. Kromosom Fittest Populasi

Dari sekian banyak kromosom dalam populasi, tentu ada satu

kromosom yang mempunyai nilai fitness paling tinggi atau fittest

populasi. Dalam mencari kromosom terbaik, digunakan teknik

pencarian berdasarkan pembandingan terhadap seluruh kromosom

dalam populasi.

Kromosom fittest populasi artinya satu kromosom yang memiliki

nilai fitness paling baik dalam populasi. Nilai fitness terbaik ditentukan

berdasarkan harga fitness paling besar. Pencarian fittest populasi

dikodekan ke dalam bahasa pemrograman java dengan kode seperti

pada gambar (4.7) di bawah.

Gambar 4.7 Kode Fittest Populasi

Dalam baris 3 pada gambar (4.7), variable kromosom sementara


69

diisi dengan kromosom pertama dalam populasi. Selanjutnya,

dilakukan perbandingan terhadap seluruh anggota populasi. Jika

kromosom selanjutnya memiliki nilai fitness yang lebih tinggi, maka

variable kromosom sementara akan diisi dengan kromosom tersebut.

Pembandingan nilai fitness kromosom terdapat pada baris 8 sampai 10

dalam gambar.

Untuk mengetahui apakah metode ini berjalan sesuai yang

diharapkan, maka dengan data masukan berupa 10 buah kota dilakukan

pengujian terhadap metode ini. Hasil pengujian dapat dilihat dalam

gambar (4.8) di bawah.

Gambar 4.8 Hasil Uji Fittest Populasi

Dari hasil uji sistem pada gambar (4.8), apabila kita susun

kromosom berdasarkan nilai fittnes secara menurun seperti pada tabel

(4.8), maka hasilnya adalah kromosom ke-7 merupakan kromosom

dengan nilai fittnes terbesar.


70

Tabel 4.8 Pengurutan Kromosom Hasil Uji Fittest Populasi

Urutan Kromosom Jarak Fittnes

1 7) [5-0-8-7-4-1-2-3-9-6-5] 9.940 0,01006036217303823

2 3) [2-3-8-7-6-5-9-1-4-0-2] 11.334 0,008823010411152285

3 1) [9-3-7-5-8-2-1-0-6-4-9] 11.455 0,008729812309035356

4 2) [5-1-0-7-6-8-9-3-4-2-5] 11.538 0,008667013347200554

5 8) [1-5-4-3-0-6-8-2-7-9-1] 12.754 0,007840677434530343

6 6) [7-4-5-1-0-9-3-6-2-8-7] 14.046 0,007119464616260857

7 9) [1-3-5-8-9-6-0-2-4-7-1] 14.116 0,007084159818645509

8 5) [8-0-5-2-9-7-4-1-6-3-8] 15.167 0,006593261686556339

9 4) [2-7-4-0-1-5-6-9-8-3-2] 15.608 0,006406970784213224

10 10) [1-7-9-2-4-6-8-3-0-5-1] 16.282 0,006141751627564181

4.5.3.3. Kromosom Flacid Populasi

Jika fittest adalah kromosom terbaik, maka kromosom terjelek

adalah flaccid. Kromosom flaccid adalah kromosom dengan nilai

fitness paling kecil. Flacid populasi dikodekan ke dalam bahasa

pemrograman java dengan kode seperti pada gambar (4.9) di bawah.

Gambar 4.9 Kode Flaccid Populasi

Kurang lebih dengan mencari kromosom fittest, dalam mencari

kromosom flaccid juga dilakukan pembandingan secara manual dengan


71

teknik rangking. Pertama-tama diperlukan sebuah variable untuk

menyimpan sementara kromosom, sebut saja variable kromosom

terendah. Kemudian, masukan kromosom pertama di populasi ke dalam

variable kromosom terendah lalu bandingkan dengan fitness kromosom

ke-2 dalam populasi dengan satu kondisi. Jika nilai fitness kromosom

ke-2 lebih rendah dibanding isi variable krom, maka kromosom ke-2

dimasukkan ke dalam variable krom.

Untuk mengetahui apakah metode ini berjalan sesuai yang


pengujian terhadap metode ini dan hasil pengujian dapat dilihat dalam

gambar (4.10). Dari hasil pengujian pada gambar (4.10), flaccid

populasi terletak pada indeks ke-5 dengan nilai fitness

0,006059504332545598 serta jarak tempuh 16.503 Km.

Gambar 4.10 Hasil Uji Flaccid Populasi

4.5.4. Probabilitas kromosom

Semakin besar probabilitas suatu kromosom, semakin besar pula

kemungkinannya terus bertahan hidup. Kromosom dengan nilai probabilitas

tinggi, selain mempunyai nilai fitness tinggi dan jarak tempuh terendah, juga

menempati bidang roda roullete dalam bilah yang besar. Probabilitas

kromosom, dihitung dan dikodekan ke dalam bahasa java seperti pada

gambar (4.11).


72

Gambar 4.11 Kode Probabilitas Kromosom

Probabilitas kromosom dicari dengan membagi fitness kromosom

dengan jumlah total fitness populasi, seperti ditunjukkan pada baris 4 dalam

gambar (4.11). Untuk mengetahui apakah metode ini berjalan sesuai yang


pengujian terhadap metode ini dan hasil pengujian dapat dilihat dalam gambar

(4.12). Dari hasil pengujian pada gambar (4.12), dengan menggunakan

kromosom flaccid populasi yang terletak pada indeks ke-2 dengan nilai fitness

0,006063913649869626 serta jarak tempuh 16.491 Km, dengan total nilai

fitness populasi sebesar 0,07264124917090525 maka diperoleh probabilitas

kromosom sebesar 0,08347755192924716.

Gambar 4.12 Hasil Uji Probabilitas Kromosom

4.5.5. Probabilitas komulatif

Probabilitas komulatif kromosom berada di antara 0 < 𝑃𝑘𝑓 ≤ 1.

Probabilitas komulatif diterapkan sebagai acuan bagi seleksi roda roullete dan

diimplementasikan ke dalam bahasa java seperti pada gambar (4.13).


73

Gambar 4.13 Kode Probabilitas Komulatif

Dalam gambar (4.13), baris 4 adalah penerapan dari persamaan (3.2).

Probabilitas komulatif kromosom di desain sedemikian rupa untuk

mendukung proses seleksi roda roullete. Untuk mengetahui apakah metode

ini berjalan sesuai yang diharapkan, maka dengan data masukan berupa 10

buah kota dilakukan pengujian terhadap metode ini dan hasil pengujian dapat

dilihat dalam tabel (4.9).

Tabel 4.9 Hasil Uji Probabilitas Komulatif

Kromosom Fittness Probbabilitas

Kromosom

Probabilitas

Komulatif

2-4-1-6-9-7-0-5-3-8-2 0.0069 0.0837 0.0837

7-0-2-8-9-3-1-4-6-5-7 0.0119 0.1448 0.2285

1-2-5-8-3-6-7-9-0-4-1 0.0066 0.0807 0.3093

3-2-7-9-5-6-8-4-0-1-3 0.0078 0.0949 0.4043

3-9-4-1-5-2-7-6-0-8-3 0.0094 0.1142 0.5185

8-7-4-5-6-1-3-9-2-0-8 0.0104 0.1272 0.6457

1-4-7-9-5-2-6-0-8-3-1 0.0077 0.0939 0.7396

0-7-4-1-9-8-2-5-3-6-0 0.0077 0.0934 0.8331

3-0-4-5-8-1-9-6-2-7-3 0.0066 0.0802 0.9133

0-4-2-5-9-7-6-1-3-8-0 0.0071 0.0866 1.0

TOTAL 0.0824 1.0

Dari hasil pengujian pada tabel (4.9) di atas, kita memperoleh

probabilitas komulatif kromosom dengan rentang 0 < 𝑃𝑘𝑓 ≤ 1, sehingga

apabila diterapkan dalam sebuah roda roullete kita memperoleh bilah dengan


74

batas atas nilai probabilitas komulatif kromosom dan batas bawah adalah

nilai probabilitas komulatif kromosom sebelumnya.

4.5.6. Seleksi Roullete

Semakin besar probabilitas suatu kromosom, semakin besar pula

kemungkinannya untuk terpilih melalui roda roullete. Kromosom dengan

nilai probabilitas tinggi, selain mempunyai nilai fitness tinggi dan jarak

traveling pendek, juga menempati bidang roda roullete dalam bilah yang

besar. Roda roullete diimplementasikan dengan bahasa pemrograman java,

dan kodenya dapat dilihat dalam gambar (4.14).

Gambar 4.14 Kode Roda Roullete

Probabilitas random dalam roda roullete ibarat sebuah pointer penunjuk

bilah. Saat bilah diputar dan berhenti pada bilah tertentu, maka bilah tersebut

yang dipilih. Seperti pointer, demikian pula cara kerja probabilitas random

dalam roda roullete. Jika nilai yang keluar saat probabilitas random di

eksekusi terletak pada bilah suatu kromosom, maka kromosom tersebut yang

terpilih. Bilah kromosom mempunyai nilai batas bawah dan nilai batas atas.

Nilai batas bawah sebuah kromosom adalah probabilitas komulatif

kromosom sebelumnya, sedangkan nilai batas atas bilah adalah probabilitas

komulatif kromosom tersebut. Lebih jelas mengenai batas bawah dan batas

atas bilah roda roullete, dapat dilihat pada tabel (4.10).

Dalam kode pada gambar (4.14), pointer roullete terletak pada baris 3.

Apabila probabilitas random tersebut dieksekusi, maka kita memperoleh

sebuah nilai yang letaknya dalam rentang 0 < 𝑅𝑎𝑛𝑑 < 1. Kemudian,


75

berapapun nilai random yang keluar, maka selanjutnya pada baris 5 sampai 8

akan mengeksekusi pencarian lokasi nilai random tersebut. Jika nilai random

terletak di antara probabilitas komulatif kromosom j dengan probabilitas

komulatif kromosom j+1, maka yang terpilih adalah kromosom j+1.

Tabel 4.10 Bilah Roda Roullete

Kromosom Probabilitas

Komulatif

Batas Bawah Batas Atas

5-4-9-0-8-2-6-7-3-1-5 0.1085 0.0 0.1085

0-4-7-3-2-1-5-9-6-8-0 0.1919 0.1085 0.1919

6-1-8-3-2-9-7-0-4-5-6 0.2799 0.1919 0.2799

9-6-5-2-1-8-4-0-7-3-9 0.3845 0.2799 0.3845

6-5-2-9-1-0-3-4-8-7-6 0.4984 0.3845 0.4984

1-6-3-2-5-0-8-9-4-7-1 0.5864 0.4984 0.5864

6-7-2-9-5-0-1-3-4-8-6 0.6981 0.5864 0.6981

4-1-8-9-3-7-6-0-5-2-4 0.8056 0.6981 0.8056

9-8-7-6-3-1-2-4-0-5-9 0.9034 0.8056 0.9034

5-6-3-7-2-8-4-0-1-9-5 1.0 0.9034 1.0

Dalam hasil pengujian roda roullete pada gambar (4.15), dengan

bilangan random sebesar 0.9179053732340812 kromosom yang terpilih

adalah kromosom indeks 10. Bilangan acak, sebagai pointer maka mengacu

pada tabel (4.10). Bilangan acak tersebut terletak di antara probabilitas

komulatif kromosom ke-9 dengan kromosom ke-10, atau batas bawah sebesar

0.9034751218638927 dan batas atas sebesar 1.


76

Gambar 4.15 Hasil Uji Roda roullete

4.5.7. Crossover XO

Crossover dikodekan ke dalam bahasa pemrograman java dengan kode

seperti pada gambar (4.17). Untuk mengetahui apakah metode sudah berjalan

sesuai dengan keingginan, maka dilakukan pengujian terhadap metode

crossover. Hasil pengujian dapat di lihat pada gambar (4.16).

Gambar 4.16 Hasil Pengujian Crossover

Dalam implementasinya, diperlukan check point (pembatas) gen yang

akan disilangkan. Jika m adalah panjang kromosom maka letak batas bawah

pada posisi 1

4∗ 𝑚 dan batas atas pada posisi

3

4∗ 𝑚. Selain penentuan check

point, offspring juga perlu disiapkan. Seperti ditunjukkan dalam kode pada


77

gambar (4.17), crossover terdiri atas 3 bagian. Pertama penentuan check point

pada baris 4 dan 5. Kedua, mengosongkan gen kromosom offspring di luar

check point (baris 14 sampai 38). Ketiga, menggabungkan offspring dan

parent (baris 39 sampai 52).

Gambar 4.17 Kode Crossover


78

4.5.8. Mutasi

Mutasi dikodekan ke dalam bahasa pemrograman java dengan kode

seperti pada gambar (4.18).

Gambar 4.18 Kode Mutasi

Proses mutasi dilakukan dengan menukar gen dalam populasi. Gen

yang ditukar adalah gen ke-3 dengan gen ke-2 terakhir dalam kromosom.

Penukaran gen diimplementasikan di baris 5 dan 6 dalam kode pada gambar

(4.18). Kromosom dalam populasi akan mengalami mutasi apabila operasi

crossover sudah dijalankan sebanyak 1000 kali, atau dengan perbandingan

1:1000.

Untuk menguji apakah metode sudah berjalan sesuai dengan teori,

maka hasilnya dapat dilihat dalam gambar (4.19). Dalam gambar (4.19)

dengan kromosom [5-1-4-7-2-9-6-8-3-0-5] sebagai induk, diperoleh

kromosom [5-1-0-7-2-9-6-8-3-4-5] sebagai hasil mutasi.

Gambar 4.19 Hasil Uji Mutasi


79

4.6. ACS Untuk TSP

4.6.1. Matriks Nearest-Neighbor

Dalam mencari matriks nearest-neighbor, diimplementasikan kode

dalam bahasa java seperti pada gambar (4.20) di bawah.

Gambar 4.20 Kode Matriks Nearest-Neighbor

Dalam kode pada gambar (4.20) pada baris 8, matriks nearest-neighbor

(nn) dicari dengan mengurutkan isi matriks jarak dan dilakukan secara

ascending. Kemudian, isi matriks jarak dibandingkan dengan hasil yang

sudah diurutkan. Apabila sesuai, maka indeks matriks jarak dimasukkan ke

dalam matriks nn. Dalam hal ini, indeks adalah inisial titik.

Apabila kita menguji kode di atas dan menggunakan tabel (4.7) sebagai

data masukkan, maka diperoleh hasil matriks nn seperti pada gambar (4.21).

Gambar 4.21 Hasil Uji Matiks Nearest-Neigbor


80

Dalam matriks nn hasil pengujian pada gambar (4.21), ditampilkan

urutan-urutan kota terdekat. Apabila diubah ke dalam sebuah tabel

ketetangaan, maka dapat kita lihat pada tabel (4.11) di bawah.

Tabel 4.11 Ketetanggaan Lima Kota

Titik Kota Ketetangaan

Ke-1 Ke-2 Ke-3 Ke-4 Ke-5

0 Titik 2 4 1 3 0

Jarak 528 1.310 1.619 2.097 999.999

1 Titik 4 3 2 0 1

Jarak 680 723 1.297 1.593 999.999

2 Titik 0 4 1 3 2

Jarak 569 780 1.192 1.781 999.999

3 Titik 1 4 2 0 3

Jarak 656 1.023 1.682 2.056 999.999

4 Titik 1 2 3 0 4

Jarak 595 809 996 1.327 999.999

4.6.2. Rute inisial

Gambar 4.22 Kode Rute Inisial

Dalam mencari rute inisial, digunakan data yang ada di dalam matriks

nn dengan isi nn[0][0] adalah kota pertama dari rute. Deklarasi kota pertama


81

ditunjukkan pada baris 3 dalam kode pada gambar (4.22). Setelah kota

pertama dideklarasikan, maka ubah status kota menjadi sudah dikunjungi

(baris 4 pada kode).

Setelah kota pertama diperoleh, selanjutnya dicari kota ke-2 dari

matriks nn. Dengan i = 0 dan kota pertama adalah rute[i] maka kota kedua

ditentukan dengan isi matriks nn[rute[i]][0], kemudia diperiksa apakan isi

matriks nn[rute[i]][0] sudah dikunjungi atau belum. Jika belum maka, isi

matriks nn[rute[i]][0] dijadikan sebagai kota ke-2 dan diatur statusnya

menjadi sudah dikunjungi. Jika isi matriks nn[rute[i]][0] sudah pernah

dikunjungi, maka dengan j = 0, isi matriks nn[rute[i]][j+1] dijadikan sebagai

kota ke-2 kemudian diatur statusnya menjadi sudah dikunjungi. Tahap ini

terus dilanjutkan selama isi variable i lebih kecil dari ukuran matriks nn

(nn.length).

Untuk menguji apakah kode sudah berjalan sesuai dengan yang

diharapkan, maka hasil pengujian metode dapat dilihat dalam gambar (4.23)

di bawah. Pengujian dilakukan dengan data masukan 5 kota pada tabel (4.7)

dan matriks nn pada gambar (4.21).

Gambar 4.23 Hasil Uji Rute Inisial

Dari hasil pengujian diperoleh rute [2-0-4-1-3-2] sebagai rute inisial.

Dengan merujuk pada tabel ketetanggaan (4.11), maka diperoleh jarak

tempuh adalah:

Jarak rute = 2-0 + 0-4 + 4-1 + 1-3 + 3-2

= 569 + 1.310 + 595 + 723 + 1.682 + 4.879 = 4.879

4.6.3. Pheromone

Matriks pheromone awal (inisial) diimplementasikan ke dalam sebuah


82

matriks berukuran n x n dengan kode dengan bahasa java seperti pada gambar

(4.24) di bawah.

Gambar 4.24 Kode Pheromone Inisial

Pheromone inisial, berarti pheromone awal mula yang tersebar di

seluruh rute dan dihitung berdasarkan jarak pada rute inisial. Sebagai

pheromone yang menjadi rujukkan dalam iterasi-terasi berikutnya,

pheromone awal diusahakan memiliki nilai dalam rentang 0 dan 1. Ketika

iterasi pertama dijalankan, pheromone inisial akan diperbaharui dengan

adanya penguapan dan penambahan pheromone dari pembaharuan

pheromone global. Mengenai penguapan dan pembaharuan pheromone

global, akan dibahas berikutnya. Dari jarak inisial sebesar 4.879 maka

diperoleh pheromone sebesar 𝑃 = 1004.879⁄ = 0.020496003279360523.

Berangkat dari kode pada gambar (4.24) di atas, apabila dilakukan

pengujian maka diperoleh hasil seperti pada gambar (4.25) di bawah.

Gambar 4.25 Hasil Uji Pheromone Awal

4.6.4. Informasi heuristic

Dalam implementasi penelitian ini, informasi dibagi ke dalam 2


83

metode. Pertama matriks heuristic untuk menyimpan hasil (𝜂𝑟𝑠) = 1

𝑑𝑟𝑠 yang

merujuk pada persamaan (2.1) dengan (𝜂𝑟𝑠) = 1

𝑑𝑟𝑠 dan 𝑑𝑟𝑠 =

√(𝑥𝑟 − 𝑥𝑠)2 + (𝑦𝑟 − 𝑦𝑠)2 (jika hanya diketahui koordinat titiknya saja).

Kedua, matriks heuristic untuk menyimpan hasil [𝜏𝑟𝑠]𝛼 . [𝜂𝑟𝑠]𝛽 yang merujuk

pada persamaan (2.1) di mana 𝜏𝑟𝑠 adalah kadar pheromone pada jalur kota r

dengan kota s.

Matriks heuristic dicari dengan kode pada gambar (4.26) di bawah. Isi

matriks heuristic [𝜏𝑟𝑠]𝛼 . [𝜂𝑟𝑠]𝛽 terus berubah seiring bertambahnya iterasi

karena dipengaruhi oleh perubahan isi matriks pheromone, sedangkan isi

matriks (𝜂𝑟𝑠) tidak akan berubah sebab jarak yang digunakan tetap merujuk

pada matriks jarak. Baris 5 dalam kode digunakan untuk menghitung (𝜂𝑟𝑠).

Baris 15 dalam kode, digunakan untuk menghitung [𝜏𝑟𝑠]𝛼 . [𝜂𝑟𝑠]𝛽 dengan nilai

𝛼 sebesar 1.0 dan nilai 𝛽 sebesar 5.0.

Gambar 4.26 Kode Matriks Heuristic

4.6.5. Phermone lokal

Matriks pheromone akan terus diperbaharui setiap kali semut telah

mengunjungi kota. Pembaharuan pheromone tersebut dinamakan local


84

pheromone update dan diimplementasikan ke dalam bahasa java dengan kode

seperti pada gambar (4.27) di bawah ini.

Gambar 4.27 Kode Perbaharuan Phermone Lokal

Baris 9 dalam kode pada gambar (4.27), matriks pheromone

diperbaharui sesuai dengan local updating rule pada persamaan (2.12). Baris

12 dalam kode digunakan untuk memperbaharui matriks heuristic choice info.

Matriks choice info harus selalu diperbaharui sebab dalam membangun

sebuah rute, semut memilih rute berdasarkan choice info.

4.6.6. Konstruksi Solusi

Dalam membangun solusi berupa rute semut, diimplementasikan ke

dalam bahasa java dengan kode seperti pada gambar (4.28). Membangun

solusi dimulai dengan membersihkan tabu list masing-masing semut, dapat

dilihat pada baris 2 sampai 4 pada kode. Pembersihan ini dilakukan dengan

mengatur status kota-kota menjadi belum dikunjungi. Setelah tabu list

dibersihkan, semut-semut diatur dengan menjadikan kota yang telah dipilih

secara acak sebagai kota keberangkatan. Pemilihan kota-kota secara acak ini,

dapat dilihat pada baris 5 sampai 9. Selanjutnya, semut mencari kota yang

akan dikunjungi. Pencarian ini dapat dilihat pada baris 15. Setelah masing-

masing semut mendapatkan kota yang dikunjungi, dilakukan pembaharuan

terhadap matriks pheromone. Pembaharuan pheromone dapat dilihat pada

baris 16. Setelah semua kota terkunjungi, maka diatur supaya kota

keberangkatan menjadi kota terakhir. Mengatur kota keberangkatan menjadi


85

kota terakhir, dapat dilihat pada baris 20 sampai 23.

Gambar 4.28 Kode Konstruksi Solusi

Saat semut-semut mencari kota yang akan dikunjungi (baris 15),

digunakan metode pencarian dengan kode seperti pada gambar (4.29).

Gambar 4.29 Kode Metode choose_and_move_to_next(Ant, int)

Pencarian kota yang akan dikunjungi, masing-masing semut

menerapkan persamaan (2.9). Dapat dilihat dalam baris 4 sampai 8 pada kode

dalam gambar (4.29). Jika nilai q berada di antara 0 dan 𝑞0 maka kota yang

dikunjungi dicari dengan menggunakan metode choose_best_next(Ant, int)


86

seperti pada gambar (4.30). Metode choose_best_next(Ant, int)

mengimplementasikan pencarian berdasarkan kota yang memiliki informasi

heuristic terbaik/terbesar. Nilai 𝑞0 yang digunakan sebesar 0.9.

Gambar 4.30 Kode Metode choose_best_next(Ant, int)

Sebaliknya, jika nilai q ternyata lebih kecil dari 0 atau lebih besar dari

𝑞0 maka kota berikutnya dicari dengan menerapkan pencarian Ant System

(AS) atau random proportional rule seperti pada gambar (4.31).

Gambar 4.31 Kode Random Proportional Rule

Setelah persamaan (2.9) selesai dijalankan, diperoleh kota yang akan

dikunjungi. Selanjutnya dalam gambar (4.29) kota yang akan dikunjungi

diperiksa statusnya. Apabila belum pernah dikunjungi maka kota tersebut

langsung dijadikan kota yang dikunjungi. Apabila kota hasil persamaan (2.9)


87

sudah pernah dikunjungi oleh semut, maka dicari kota berikutnya ber yang

belum dikunjungi dengan menerapkan pencarian berdasarkan tetangga

terdekat. Pencarian berdasarkan ketetanggan terdekat ini menggunakan isi

matriks nearest-neighbor dan dapat dilihat dalam gambar (4.32).

Gambar 4.32 Kode Pencarian Tetangga Terdekat

4.6.7. Penguapan pheromone

Penguapan pheromone merupakan pembaharuan kadar pheromone

pada jalur penghubung 2 kota yang tidak digunakan. Jalur yang tidak

digunakan, kadar pheromone akan berkurang. Begitu pula dengan kadar

pheromone pada jalur yang dilewati oleh hanya sedikit semut. Penguapan

pheromone diimplementasikan ke dalam bahasa java dengan kode seperti

pada gambar (4.33).

Gambar 4.33 Kode Penguapan Pheromone

4.6.8. Pheromone global

Pheromone global diperbaharui setelah seluruh semut menyelesaikan

rute. Sebelum pembaharuan pheromone global diterapkan, terlebih dahulu


88

rute inisial diperbaharui. Pembaharuan rute inisial dapat dilihat dalam gambar

(4.34) di bawah.

Gambar 4.34 Kode Pembaharuan Rute Inisial

Pembaharuan rute inisial, berarti mencari semut best_so_far atau semut

terbaik. Apabila dalam iterasi saat itu terdapat semut dengan jarak rute yang

lebih baik dibanding jarak rute inisial, maka rute semut terbaik saat itu

dijadikan sebagai rute inisial. Setelah diperoleh rute inisial, pembaharuan

pheromone global dapat dilakukan dengan menerapkan kode seperti pada

gambar (4.35). Pembaharuan pheromone global ini merujuk pada persamaan

(2.10) dengan nilai ∆𝜏𝑟𝑠𝑘 adalah 1 𝐷𝑖𝑠𝑡𝑟𝑢𝑡𝑒_𝑖𝑛𝑖𝑠𝑖𝑎𝑙

⁄ seperti pada baris 2 dalam

gambar (4.35).

Gambar 4.35 Kode Pembaharuan Pheromone Global

4.7. Pengujian Algoritma Genetika

Pengujian dilakukan pengujian sebanyak 10 kali dengan menggunakan data

yang bervariasi berupa jumlah kota. Variasi jumlah kota tersebut dimulai dari 10

buah kota, kemudian kelipatannya sampai 100 buah kota. Tujuan dari pengujian ini

untuk mendapatkan jarak rute yang dihasilkan, lama proses algoritma, dan besar

memori yang digunakan.


89

4.7.1. 10 Kota

Diperoleh hasil pengujian pada tabel (4.12), jika dihitung rata-rata

(mean) dari masing-masing attribut, maka diperoleh:

Rata-rata jarak = 𝑇𝑂𝑇𝐴𝐿 𝐽𝐴𝑅𝐴𝐾

10 =

134.772

10 = 13.477,2 Km

Rata-rata waktu = 𝑇𝑂𝑇𝐴𝐿 𝑊𝐴𝐾𝑇𝑈

10 =

834

10 = 83,4 ms

Rata-rata memori = 𝑇𝑂𝑇𝐴𝐿 𝑀𝐸𝑀𝑂𝑅𝐼

10 =

5.872.576

10 = 58.757,6 byte

Dengan ditentukan bahwa nilai minimum adalah hasil optimal, maka dari

masing-masing attribute diperoleh:

Optimal jarak = 11.924 Km

Optimal waktu = 34 ms

Optimal memori = 167.792 byte

Tabel 4.12 Pengujian Algoritma Genetika TSP 10 Kota

Pengujian Attribut

Jarak (Km) Waktu (ms) Memori (byte)

1 14.183 78 503.352

2 13.045 63 503.352

3 13.212 110 503.332

4 14.750 54 335.584

5 12.754 80 335.560

6 15.508 34 167.792

7 13.207 81 503.352

8 12.954 42 503.584

9 11.924 249 2.181.064

10 13.235 43 335.584

4.7.2. 20 Kota




90


10 =

293.925

10 = 29.392,5 Km


10 =

1408

10 = 140,8 ms


10 =

4.530.872

10 = 453.087,2 byte







Pengujian Attribut


1 29.315 31 167.840

2 33.002 15 167.840

3 30.384 32 167.840

4 29.128 101 335.608

5 26.966 36 335.608

6 29.334 922 2.181.424

7 27.184 91 335.608

8 25.839 114 335.656

9 32.990 12 167.840

10 29.783 54 335.608

4.7.3. 30 Kota




10 =

465.089

10 = 46.508,9 Km


10 =

1.106

10 = 110,6 ms


91


10 =

6.376.184

10 = 637.618,4 byte







Pengujian Attribut


1 43.860 234 335.608

2 48.544 141 1.342.216

3 48.725 16 167.840

4 42.634 403 2.348.840

5 48.381 64 503.376

6 48.219 50 167.840

7 45.127 27 167.840

8 47.475 14 167.840

9 42.195 65 671.408

10 49.929 92 503.376

4.7.4. 40 Kota




10 =

643.554

10 = 64.355,4 Km


10 =

2.136

10 = 213,6 ms


10 =

15.942.968

10 = 1.594.296,8 byte




92





Pengujian Attribut


1 66.269 109 1.343.016

2 65.423 328 3.188.464

3 61.160 406 3.019.896

4 61.190 41 503.328

5 66.798 60 167.792

6 66.612 50 167.792

7 60.809 729 3.861.560

8 59.185 356 3.019.848

9 69.832 31 335.712

10 66.276 26 335.560

4.7.5. 50 Kota




10 =

832.053

10 = 83.205,3 Km


10 =

1.945

10 = 194,5 ms


10 =

8.585.104

10 = 858.510,4 byte







93


Pengujian Attribut


1 85.277 16 503.432

2 78.495 16 335.560

3 85.996 500 671.224

4 88.104 293 2.351.096

5 87.935 32 503.328

6 83.662 80 503.720

7 84.878 18 494.000

8 75.368 901 2.048.240

9 82.368 14 335.640

10 79.970 75 838.864

4.7.6. 60 Kota




10 =

1.006.480

10 = 100.648 Km


10 =

1.630

10 = 163 ms


10 =

11.138.800

10 = 1.113.880 byte







94


Pengujian Attribut


1 99.679 20 335.824

2 101.041 16 335.560

3 102.880 16 503.744

4 101.428 49 503.432

5 100.982 23 335.560

6 97.833 57 1.007.528

7 100.308 28 494.192

8 103.032 275 2.182.200

9 92.856 375 4.535.064

10 106.441 771 905.696

4.7.7. 70 Kota




10 =

1.124.815

10 = 112.481,5 Km


10 =

1.030

10 = 103 ms


10 =

10.060.160

10 = 1.006.016 byte







95


Pengujian Attribut


1 118.868 15 503.744

2 115.774 94 839.440

3 110.105 16 335.688

4 107.008 255 1.848.096

5 118.813 69 671.096

6 107.851 34 671.408

7 113.117 20 494.280

8 112.470 248 3.190.488

9 111.879 27 330.808

10 108.930 252 1.175.112

4.7.8. 80 Kota




10 =

1.325.976

10 = 132.597,6 Km


10 =

2.020

10 = 202 ms


10 =

168.682.800

10 = 16.868.280 byte







96


Pengujian Attribut


1 134.831 47 1.007.824

2 132.100 93 1.343.832

3 139.178 31 839.952

4 133.837 12 503.456

5 128.779 70 1.176.096

6 127.344 129 2.184.552

7 134.149 12 497.264

8 131.419 248 2.986.224

9 131.131 850 2.460.280

10 133.208 528 3.863.320

4.7.9. 90 Kota




10 =

1.474.007

10 = 147.400,7 Km


10 =

1.998

10 = 199,8 ms


10 =

13.483.152

10 = 1.348.315,2 byte







97


Pengujian Attribut


1 150.269 47 1.007.824

2 140.777 93 1.343.832

3 155.808 31 839.952

4 136.108 12 503.456

5 151.507 70 1.176.096

6 141.003 129 2.184.552

7 144.621 12 497.264

8 145.280 248 2.986.224

9 153.503 850 2.460.280

10 155.131 16 328.848

4.7.10. 100 Kota




10 =

1.676.420

10 = 167.642 Km


10 =

2.179

10 = 217,9 ms


10 =

22.259.280

10 = 2.225.928 byte







98


Pengujian Attribut


1 167.255 15 335.872

2 166.360 125 1.793.992

3 173.281 31 504.048

4 168.117 455 3.697.328

5 167.174 288 3.123.608

6 169.772 647 7.064.400

7 167.948 39 646.616

8 171.445 73 484.824

9 165.187 32 495.240

10 159.881 474 4.113.352

4.8. Pengujian ACS

Pengujian dilakukan pengujian sebanyak 10 kali dengan menggunakan data

yang bervariasi berupa jumlah kota. Variasi jumlah kota tersebut dimulai dari 10

buah kota, kemudian kelipatannya sampai 100 buah kota. Tujuan dari pengujian ini

untuk mendapatkan jarak rute yang dihasilkan, lama proses algoritma, dan besar

memori yang digunakan. Dalam setiap pengujian, nilai parameter alpha = 1, beta =

5, dan rho = 0,9 yang digunakan selalu konsisten atau sama.

4.8.1. 10 Kota




10 =

109.819

10 = 10.981,9 Km


10 =

395

10 = 39,5 ms


10 =

3.020.256

10 = 302.025,6 byte


99






Tabel 4.22 Pengujian Algoritma ACS TSP 10 Kota

Pengujian Attribut


1 11.151 76 335.584

2 10.864 25 335.584

3 11.191 41 335.584

4 11.151 24 167.792

5 10.916 32 335.584

6 11.151 39 335.584

7 10.864 34 335.584

8 10.803 80 335.584

9 10.864 23 335.584

10 10.864 21 167.792

4.8.2. 20 Kota




10 =

149.329

10 = 14.932,9 𝐾𝑚


10 =

1.258

10 = 125,8 𝑚𝑠


10 =

3.357.840

10 = 335.784 𝑏𝑦𝑡𝑒


100



Optimal jarak = 14.564 𝐾𝑚

Optimal waktu = 44 𝑚𝑠

Optimal memori = 167840 𝑏𝑦𝑡𝑒


Pengujian Attribut


1 15.412 56 335.784

2 14.808 328 335.784

3 14.564 161 335.784

4 15.177 178 335.784

5 15.263 113 503.728

6 14.564 44 335.784

7 14.991 44 167.840

8 14.866 117 335.784

9 15.040 150 335.784

10 14.644 67 335.784

4.8.3. 30 Kota




10 =

200.251

10 = 20.025,1 𝐾𝑚


10 =

2.375

10 = 237, 5 𝑚𝑠


10 =

5.710.976

10 = 571.097,6 𝑏𝑦𝑡𝑒


101





Optimal memori = 503.888 𝑏𝑦𝑡𝑒


Pengujian Attribut


1 19.724 106 503.888

2 19.014 285 671.912

3 20.120 164 503.888

4 21.478 346 503.888

5 20.045 161 503.888

6 19.719 169 671.912

7 20.093 398 503.888

8 19.469 205 671.912

9 20.635 353 671.912

10 19.954 188 503.888

4.8.4. 40 Kota




10 =

253.480

10 = 25.348 𝐾𝑚


10 =

2.853

10 = 285,3 𝑚𝑠


10 =

8.906.872

10 = 890.687,2 𝑏𝑦𝑡𝑒


102







Pengujian Attribut


1 24.605 298 840.256

2 26.610 270 1.008.360

3 24.428 293 1.008.360

4 23.855 290 840.256

5 24.574 435 1.008.360

6 23.935 278 1.008.360

7 24.989 278 840.256

8 28.868 160 672.152

9 25.073 231 840.256

10 26.543 320 840.256

4.8.5. 50 Kota




10 =

134.772

10 = 19.014 𝐾𝑚


10 =

5.726

10 = 572,6 𝑚𝑠


10 =

14.796.384

10 = 1.479.638 𝑏𝑦𝑡𝑒


103





Optimal memori = 1.176.944 𝑏𝑦𝑡𝑒


Pengujian Attribut


1 29.457 362 1.176.944

2 31.583 403 1.176.944

3 29.599 405 1.345.128

4 28.388 434 1.345.128

5 28.388 718 1.513.312

6 29.779 423 1.344.760

7 27.608 689 2.017.864

8 31.352 372 1.176.944

9 26.895 633 1.849.680

10 26.950 1.287 1.849.680

4.8.6. 60 Kota




10 =

436.925

10 = 43.692,5 𝐾𝑚


10 =

8.807

10 = 880,7 𝑚𝑠


10 =

18.673.064

10 = 1.867.306 𝑏𝑦𝑡𝑒


104




Optimal waktu = 93 𝑏𝑦𝑡𝑒



Pengujian Attribut


1 31.468 851 2.187.008

2 31.700 794 2.018.744

3 30.259 863 2.187.008

4 48.973 93 504.368

5 30.845 990 2.187.008

6 34.526 671 1.850.480

7 32.319 800 2.018.744

8 32.465 945 2.355.272

9 43.664 715 1.682.216

10 33.406 2.085 1.682.216

4.8.7. 70 Kota




10 =

334.243

10 = 33.424,3 𝐾𝑚


10 =

18.928

10 = 1.892,8 𝑚𝑠


10 =

32.482.552

10 = 3.248.255 𝑏𝑦𝑡𝑒


105




Optimal waktu = 1.075 𝑚𝑠



Pengujian Attribut


1 31.444 2.937 3.366.096

2 34.908 1.456 3.029.408

3 32.987 2.227 3.534.440

4 32.228 1.494 3.366.096

5 33.427 1.383 3.197.752

6 32.608 1.594 3.534.440

7 32.232 1.460 3.366.096

8 34.529 3.254 2.356.032

9 37.263 1.075 2.524.376

10 32.617 2.048 4.207.816

4.8.8. 80 Kota




10 =

375.123

10 = 37.512,3 𝐾𝑚


10 =

33.703

10 = 3.370,3 𝑚𝑠


10 =

42.674.832

10 = 4.267.483 𝑏𝑦𝑡𝑒


106







Pengujian Attribut


1 34.678 2.543 4.631.824

2 40.086 3.380 3.638.776

3 42.755 2.858 3.808.856

4 37.803 4.316 4.306.088

5 34.152 4.315 4.632.040

6 35.022 3.897 4.308.288

7 33.774 2.502 5.127.928

8 39.680 1.594 3.366.944

9 40.825 3.712 4.040.640

10 36.348 4.586 4.813.448

4.8.9. 90 Kota




10 =

450.535

10 = 45.053,5 𝐾𝑚


10 =

39.426

10 = 3.942,6 𝑚𝑠


10 =

51.629.856

10 = 5.162.986 𝑏𝑦𝑡𝑒


107







Pengujian Attribut


1 41.065 3.196 5.065.128

2 84.684 1.073 2.279.256

3 37.815 4.867 5.545.720

4 36.595 6.256 7.188.880

5 39.026 3.019 5.392.552

6 41.827 3.324 5.882.368

7 39.970 4.707 4.745.088

8 36.977 6.448 6.686.848

9 37.429 4.495 5.239.176

10 55.147 2.041 3.604.840

4.8.10. 100 Kota




10 =

411.830

10 = 41.183 𝐾𝑚


10 =

80.984

10 = 8.098,4 𝑚𝑠


10 =

59.883.696

10 = 5.988.370 𝑏𝑦𝑡𝑒


108







Pengujian Attribut


1 43.959 4.494 5.551.736

2 40.615 7.119 8.252.696

3 44.417 5.548 6.201.320

4 41.574 9.941 1.886.016

5 41.339 6.624 7.678.656

6 43.897 6.608 7.037.728

7 38.655 7.332 8.329.808

8 38.545 11.216 2.587.712

9 40.622 7.979 8.008.984

10 38.207 14.123 4.349.040

4.9. Pembandingan Algoritma

4.9.1. Jarak

Pada gambar (4.36) adalah tampak perbandingan hasil jarak oleh kedua

algoritma. Grafik pada gambar (4.36) berdasarkan pada rata-rata jarak,

terlihat bahwa algoritma ACS menemukan solusi jarak yang lebih pendek

dibandingkan algoritma genetika. Jika kita melihat pada hasil

minimal/terendah yang didapatkan selama 10 kali percobaan tersebut, maka

diperoleh grafik seperti pada gambar (4.37).


109

Gambar 4.36 Grafik hasil jarak rata-rata

Grafik pada gambar (4.37) berdasarkan jarak minimal, memperlihatkan

bagaimana algoritma ACS mampu menemukan solusi jarak yang lebih

pendek dibandingkan algoritma genetika.

Gambar 4.37 Grafik hasil jarak minimal

Untuk memperjelas perbandingan jarak traveling dari hasil kedua

algoritma, missal digunakan data hasil pengujian terhadap data 40 buah kota,

maka akan tampak seperti pada tabel (4.32).

10Kota

20Kota

30Kota

40Kota

50Kota

60Kota

70Kota

80Kota

90Kota

100Kota

ACS 10982 14933 20025 25348 29131 34963 33424 37512 45054 41183

GA 13477 29393 46509 64355 83205 100648 112482 132598 147401 167642

020000400006000080000

100000120000140000160000180000

ACS GA

10Kota

20Kota

30Kota

40Kota

50Kota

60Kota

70Kota

80Kota

90Kota

100Kota

ACS 10803 14564 19014 23855 26895 30259 31444 33774 36595 38207

GA 11924 25839 42195 59185 75368 92856 107008 127344 136108 159881

020000400006000080000

100000120000140000160000180000

ACS GA


110

Table 4.32 Perbandingan Jarak Untuk Data 40 Kota

Pengujian

Ke

Algoritma Genetika

(Order Crossover, Reciprocal

exchange mutasi)

Algoritma ACS

(Alpa = 1, beta = 0.5, rho =

0.9)

1 66.269 24.605

2 65.423 26.610

3 61.160 24.428

4 61.190 23.855

5 66.798 24.574

6 66.612 23.935

7 60.809 24.989

8 59.185 28.868

9 69.832 25.073

10 66.276 26.543

Dari tabel (4.32) apabila dipetakan kedalam sebuah grafik, maka akan

terlihat seperti pada gambar (4.38) di bawah.

Gambar 4.38 Grafik hasil perbandingan jarak 40 buah kota

0.00

10,000.00

20,000.00

30,000.00

40,000.00

50,000.00

60,000.00

70,000.00

80,000.00

Uji 1 Uji 2 Uji 3 Uji 4 Uji 5 Uji 6 Uji 7 Uji 8 Uji 9 Uji 10

Genetika ACS


111

4.9.2. Waktu

Pada gambar (4.39) dan gambar (4.40) adalah tampak perbandingan

waktu pada kedua algoritma. Grafik pada gambar (4.39) berdasarkan pada

rata-rata waktu, memperlihatkan rata-rata algoritma genetika dapat

menemukan solusi lebih cepat dibandingkan ACS.

Gambar 4.39 Grafik hasil waktu rata-rata

Jika kita melihat pada hasil minimal/terendah yang didapatkan selama

10 kali percobaan, diperoleh grafik seperti pada gambar (4.40). Dalam grafik

pada gambar (4.40), tampak algoritma genetika adalah yang tercepat

dibandingkan dengan ACS.

Gambar 4.40 Grafik hasil waktu minimal

10 Kota 20 Kota 30 Kota 40 Kota 50 Kota 60 Kota 70 Kota 80 Kota 90 Kota100Kota

ACS 39.5 125.8 237.5 285.3 572.6 880.7 1892.8 3370.3 3942.6 8098.4

GA 83.4 140.8 110.6 213.6 194.5 163 103 202 199.8 217.9

0100020003000400050006000700080009000

ACS GA

10 Kota 20 Kota 30 Kota 40 Kota 50 Kota 60 Kota 70 Kota 80 Kota 90 Kota100Kota

ACS 21 44 106 160 362 93 1075 1594 1073 4494

GA 34 12 14 26 14 16 15 12 15 15

0

1000

2000

3000

4000

5000

ACS GA


112

Untuk memperjelas perbandingan waktu/durasi proses dari hasil kedua

algoritma, misal digunakan data 40 buah kota maka akan tampak seperti pada

tabel (4.33).

Table 4.33 Perbandingan Waktu Untuk Data 40 Kota

Pengujian

Ke

Algoritma Genetika


exchange mutasi)

Algoritma ACS

(Alpa = 1, beta = 0.5, rho =

0.9)

1 109 298

2 328 270

3 406 293

4 41 290

5 60 435

6 50 278

7 729 278

8 356 160

9 31 231

10 26 320



Gambar 4.41 Grafik hasil perbandingan waktu proses 40 buah kota

0

100

200

300

400

500

600

700

800


Genetika ACS


113

4.9.3. Memori

Pada gambar (4.42) dan gambar (4.43) adalah tampak perbandingan

konsumsi memori kedua algoritma. Grafik pada gambar (4.42) berdasarkan

pada rata-rata konsumsi memori, memperlihatkan rata-rata algoritma

genetika dapat menemukan solusi lebih cepat dibandingkan ACS.

Gambar 4.42 Grafik hasil memori rata-rata

Jika kita melihat pada hasil minimal/terendah yang didapatkan selama

10 kali percobaan, diperoleh grafik seperti pada gambar (4.43). Dalam grafik

pada gambar (4.43), tampak algoritma genetika menggunakan memori yang

lebih sedikit dibandingkan ACS.

Gambar 4.43 Grafik hasil memori minimal

10Kota

20Kota

30Kota

40Kota

50Kota

60Kota

70Kota

80Kota

90Kota

100Kota

ACS 302,02 335,78 571,09 890,68 1,479, 1,867, 3,248, 4,267, 5,162, 5,988,

GA 587,25 453,08 637,61 1,594, 858,51 1,113, 1,006, 1,686, 1,348, 2,225,

0

1,000,000

2,000,000

3,000,000

4,000,000

5,000,000

6,000,000

7,000,000

ACS GA

10Kota

20Kota

30Kota

40Kota

50Kota

60Kota

70Kota

80Kota

90Kota

100Kota

ACS 167,79 167,84 503,88 672,15 1,176, 504,36 2,356, 3,366, 2,279, 1,886,

GA 167,79 167,84 167,84 167,79 335,56 335,56 330,80 497,26 328,84 335,87

0500,000

1,000,0001,500,0002,000,0002,500,0003,000,0003,500,0004,000,000

ACS GA


114

Untuk memperjelas perbandingan konsumsi memori pada saat

memproses data, dan misalnya digunakan data 40 buah kota sebagai contoh

perbandingan maka akan tampak seperti pada tabel (4.34).

Table 4.34 Perbandingan Konsumsi Memori Untuk Data 40 Kota

Pengujian

Ke

Algoritma Genetika


exchange mutasi)

Algoritma ACS

(Alpa = 1, beta = 0.5, rho =

0.9)

1 1.343.016 840.256

2 3.188.464 1.008.360

3 3.019.896 1.008.360

4 503.328 840.256

5 167.792 1.008.360

6 167.792 1.008.360

7 3.861.560 840.256

8 3.019.848 672.152

9 335.712 840.256

10 335.560 840.256



Gambar 4.44 Grafik hasil perbandingan konsumsi memori 40 buah kota

0

1000

2000

3000

4000

5000


Genetika ACS


115

BAB V

PENUTUP

5.1. Kesimpulan

Berdasarkan hasil pengujian dan analisis yang telah dilakukan pada kedua

algoritma, maka dapat ditarik kesimpulan sebagai berikut:

1. Algoritma ACS lebih konsisten dibandingkan algoritma genetika yang

naik turun.

2. Algoritma ACS mampu menemukan solusi berupa jarak traveling yang

lebih pendek dibandingkan algoritma genetika.

3. Untuk data di atas 20 buah kota, algoritma genetika secara rata-rata

memproses data lebih cepat dibandingkan algoritma ACS.

4. Untuk data di atas 20 buah kota, algoritma genetika secara rata-rata

menggunakan memori yang lebih sedikit dibandingkan algoritma ACS.

5.2. Saran

1. Diharapkan dapat melakukan penelitian lebih lanjut terkait perbandingan

kedua algoritma dengan data pada rentang 20 buah kota sampai dengan

30 buah kota.

2. Diharapkan dapat melakukan penelitian lebih lanjut tentang

perbandingan algoritma genetika dengan algoritma ACS, terkait

implementasi Local Search setiap kali rute travelling ditemukan.

3. Perbandingan algoritma genetika dan ACS dapat dikembangkan dengan

mempertimbangkan perubahan parameter dan variable masing-masing

algoritma.


116

DAFTAR PUSTAKA

Basuki, Achmad. (2003), “Algoritma Genetika : Suatu Alternatif Penyelesaian

Permasalahan Searching, Optimasi dan Machine Learning”, Surabaya:

Politeknik Elektronika Negeri Surabaya PENS – ITS.

Budy., (2013), “Analisis Perbandingan Algoritma Kriptografi AES, DES dan IDEA

yang Tepat Untuk Perangkat Mobile”. Tesis S-2 pada Universitas Atma Jaya

Yogyakarta: tidak diterbitkan.

Darmadipta, Agustinus Wikrama., (2013), “Perbandingan Penggunaan Algoritma

Dijkstra dan Algoritma Floyd-warshall Untuk Pencarian Jalur Terpendek

Pada Bus Trans Jogja”, Skripsi S-1 pada Universitas Sanata Dharma

Yogyakarta: tidak diterbitkan.

Dorigo, M., & Stutzle, T., (2004), “Ant Colony Optimization”, MIT Press,

Cambrige, MA.

Gendreau, M., & Potvin, Jean-Yves. Editors. “Handbook of Metaheuristics”, 2nd

edn., (2010), New York, Springer.

Haupt, Randy L., & Haupt, Sue Ellen., “Practical Genetic Algorithm”, 2nd edn. ©

(2004) by John Wiley & Sons, Inc., Hoboken, New Jersey.

Michalewicz, Z., (1996), “Genetic Algorithm + Data Structures = Evolution

Programs”, 3rd edn. Berlin, Springer-Verlag.

Mutakhiroh, Iing., dkk., (2007), “Pemanfaatan Metode Heuristik dalam Pencarian

Jalur Terpendek dengan Algoritma Semut dan Algoritma Genetika”. Jurnal

penelitian pada Seminar Nasional Aplikasi Teknologi Informasi 2007.

Naftalin, M., & Wadler, P., “Java Generics”, 1st edn. (2006), O’Reilly Media.


117

Nugroho, Oktavianus Shunu., (2002), “Pencarian Jalur Terpendek Antar Kota Di

Pulau Jawa Dengan Algoritma Dijkstra”, Skripsi S-1 pada Universitas Sanata

Dharma Yogyakarta: tidak diterbitkan.

Prasetyo, Yohanes Beny., (2016), “Perbandingan Kompresi Teks Menggunakan

Algoritma Huffman Statis, Huffman Dinamis dan Modifikasi Algoritma

Huffman”, Skripsi S-1 pada Universitas Sanata Dharma Yogyakarta: tidak

diterbitkan.

Pratiwi, Sukeksi Esti., (2007), “Sistem Pendukung Keputusan Berbasis Web Untuk

Menentukan Alternatif Jalan Wisata Di DIY dan Sekitarnya Dengan

Menggunakan Algoritma Genetika”, Skripsi S-1 pada Universitas Sanata

Dharma Yogyakarta: tidak diterbitkan.

Purbasari, Intan Yuniar., (2007), “Desain & Analisis Algoritma”, Yogyakarta:

Graha Ilmu.

Purwanto, Eko Budi., (2008), “Perancangan dan Analisis Algoritma”, 1st edn.

Yogyakarta: Graha Ilmu.

Ridwan, Achmad., & Karisma, Aisyatul., “Perbandingan Algoritma Djikstra dan

Algoritma Ant Colony Optimation dalam Travelling Salesman Problem (TSP)

pada Kota Semarang”. Jurnal Penelitian Teknik Informatika Fakultas Ilmu

Komputer pada Universitas Dian Nuswantoro Semarang.

Zed, Mestika., (2004), “Metode Penelitian Kepustakaan”, Jakarta: Yayasan Obor

Indonesia.


118

LAMPIRAN

Lampiran 1: Kode Program Algoritma Genetika Class Kromosom

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

package Genetika;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.stream.IntStream;

/**

*

* @author Julak96

*/

public class Kromosom {

private List<Integer> kromosomTunggal = new ArrayList<Integer>();

public Kromosom() {

}

public List<Integer> getKromosomTunggal() {

return kromosomTunggal;

}


119

public void setKromosomTunggal(List<Integer> kromosomTunggal) {

this.kromosomTunggal = kromosomTunggal;

}

public void bersihkanKromosom() {

kromosomTunggal.clear();

}

public void bangkitkanKromosom(int sizeKromosom) {

bersihkanKromosom();

for (int i = 0; i < sizeKromosom; i++) {

kromosomTunggal.add(i);

}

Collections.shuffle(kromosomTunggal);

kromosomTunggal.add(kromosomTunggal.get(0));

}

public double fittnessKromosom(double graph[][]) {

return 100 / jarakTotalKromosom(graph);

}

public double jarakTotalKromosom(double graph[][]) {

double jarakTotal = 0.0;

for (int i = 1; i < getKromosomTunggal().size(); i++) {

int x = getKromosomTunggal().get(i - 1);

int y = getKromosomTunggal().get(i);

jarakTotal += graph[x][y];

}

return jarakTotal;

}


120

public void showKromosom() {

IntStream.range(0, getKromosomTunggal().size())

.forEach(i -> {

System.out.print("" + getKromosomTunggal().get(i) + "-");

});

}

}

Lampiran 2: Kode Program Algoritma Genetika Class Populasi

/*




*/

package Genetika;



import java.util.Objects;

/**

*

* @author Julak96

*/

public class Populasi {

private List<Kromosom> kromosomPopulasi = new ArrayList<>();

public Populasi() {

}


121

public List<Kromosom> getKromosomPopulasi() {

return kromosomPopulasi;

}

public void setKromosomPopulasi(List<Kromosom> kromosomPopulasi) {

this.kromosomPopulasi = kromosomPopulasi;

}

public double fitnessPopulasi(double graph[][]) {

double tot = 0.0;

for (int i = 0; i < getKromosomPopulasi().size(); i++) {

tot = tot + getKromosomPopulasi()

.get(i).fittnessKromosom(graph);

}

return tot;

}

public Kromosom fittestPopulasi(double graph[][]) {

Kromosom krom = new Kromosom();

krom = getKromosomPopulasi().get(0);


double fitt = krom.fittnessKromosom(graph);

double tempFitt = getKromosomPopulasi()


if (fitt < tempFitt) {

krom = getKromosomPopulasi().get(i);

}

}

return krom;

}


122

public int flacidPopulasi(Populasi pop, double graph[][]) {

int posisi = 0;

Kromosom krom;

krom = pop.getKromosomPopulasi().get(0);

for (int i = 1; i < pop.getKromosomPopulasi().size(); i++) {

double fitt = krom.fittnessKromosom(graph);

double tempFitt = pop.getKromosomPopulasi()


if (fitt > tempFitt) {

krom = pop.getKromosomPopulasi().get(i);

posisi = i;

}

}

return posisi;

}

public double probKromosom(Kromosom kromosom, double totFittness, double

graph[][]) {

double probabilitas;

probabilitas = kromosom.fittnessKromosom(graph) / totFittness;

return probabilitas;

}

public double ProbKomulatif(int index, double graph[][]) {

double probabilitas = 0, totFittness = fitnessPopulasi(graph);

for (int i = 0; i <= index; i++) {

probabilitas += probKromosom(getKromosomPopulasi().get(i),

totFittness, graph);

}

return probabilitas;


123

}

public int rodaRoulete(double graph[][]) {

int x = 0;

double r = (Math.random() % 2); //probabilitas random

// System.out.println("Probabilitas random roullete = "+r);

for (int j = 1; j < getKromosomPopulasi().size(); j++) {

if ((ProbKomulatif(j - 1, graph) < r) && (r <= ProbKomulatif(j, graph))) {

x = j;

break;

}

}

return x;

}

public Kromosom[] xo_DO(Kromosom p1, Kromosom p2) {

Kromosom[] child = new Kromosom[2];

int separuhKromosom = p1.getKromosomTunggal().size() / 2;

int point1 = (int) (separuhKromosom - (separuhKromosom / 2)), point2 = (int)

(separuhKromosom + (separuhKromosom / 2));

Integer[] offSpring1 = new Integer[p1.getKromosomTunggal().size()]; //temp

kromosom

Integer[] offSpring2 = new Integer[p2.getKromosomTunggal().size()]; //temp

kromosom

List<Integer> temp1 = new ArrayList<>(); //copy kromosom induk

List<Integer> temp2 = new ArrayList<>(); //copy kromosom induk

for (int i = 0; i < p2.getKromosomTunggal().size(); i++) {

temp1.add(p2.getKromosomTunggal().get(i));


124

temp2.add(p1.getKromosomTunggal().get(i));

}

for (int i = 0; i < temp1.size(); i++) {

if (i < point1 || i > point2) {

offSpring1[i] = -1;

offSpring2[i] = -1;

} else {

offSpring1[i] = p1.getKromosomTunggal().get(i);

offSpring2[i] = p2.getKromosomTunggal().get(i);

boolean stats_1 = true;

int counter = 0, copyOf_counter = 0;

while (stats_1) {

if (Objects.equals(temp1.get(counter),

p1.getKromosomTunggal().get(i))) {

temp1.remove(counter);

stats_1 = false;

} else {

counter += 1;

}

}

boolean stats_2 = true;

while (stats_2) {

if (Objects.equals(temp2.get(copyOf_counter),

p2.getKromosomTunggal().get(i))) {

temp2.remove(copyOf_counter);

stats_2 = false;

} else {

copyOf_counter += 1;

}

}


125

}

}

for (int i = 0; i < offSpring1.length; i++) {

if (offSpring1[i] == null || offSpring1[i] == -1) {

offSpring1[i] = temp1.get(0);

temp1.remove(0);

}

if (offSpring2[i] == null || offSpring2[i] == -1) {

offSpring2[i] = temp2.get(0);

temp2.remove(0);

}

}

temp1.clear();

temp2.clear();

for (int i = 0; i < offSpring2.length - 1; i++) {

temp1.add(offSpring1[i]);

temp2.add(offSpring2[i]);

}

temp1.add(temp1.get(0));

temp2.add(temp2.get(0));

Kromosom offspringKromosom1 = new Kromosom();

offspringKromosom1.setKromosomTunggal(temp1);

child[0] = offspringKromosom1;

Kromosom offspringKromosom2 = new Kromosom();

offspringKromosom2.setKromosomTunggal(temp2);

child[1] = offspringKromosom2;

return child;

}


126

public Kromosom mutasi(Kromosom parent) {

int swap =

parent.getKromosomTunggal().get((parent.getKromosomTunggal().size()) - 2);

int gen = parent.getKromosomTunggal().get(2);

parent.getKromosomTunggal().set(2, swap);

parent.getKromosomTunggal().set(((parent.getKromosomTunggal().size()) -

2), gen);

return parent;

}

public void showPopulationMembers(double graph[][]) {

double prevKomf = 0.0;


System.out.print((i + 1) + ") ");

getKromosomPopulasi().get(i).showKromosom();

System.out.println(" D = " +

getKromosomPopulasi().get(i).jarakTotalKromosom(graph) + " "

+ "f = " + getKromosomPopulasi().get(i).fittnessKromosom(graph) +

" "

+ " P^m = " + probKromosom(getKromosomPopulasi().get(i),

fitnessPopulasi(graph), graph) + " "

+ " P^kf = " + prevKomf + " -> " + ProbKomulatif(i, graph));

prevKomf = ProbKomulatif(i, graph);

}

}

}

Lampiran 3: Kode Program Algoritma Genetika Class Genetika

package Genetika;



127


/**

*

* @author Julak96

*/

public class Genetika {

Populasi pop;

public Genetika() {

}

public Populasi getPop() {

return pop;

}

public void setPop(Populasi pop) {

this.pop = pop;

}

/**

* ********* populasi awal **************

*/

public Populasi bangkitkanPopulasi(int ukuranKromosome, int ukuranPopulasi)

{


128

Populasi populasi = new Populasi();

List<Kromosom> populasi_temp = new ArrayList<Kromosom>();

for (int i = 0; i < ukuranPopulasi; i++) {

Kromosom kromosom = new Kromosom();

kromosom.bangkitkanKromosom(ukuranKromosome);

populasi_temp.add(kromosom);

}

populasi.setKromosomPopulasi(populasi_temp);

return populasi;

}

/**

* ********* run algo *************

*/

public Kromosom run_genetika(double graph[][]) {

Kromosom result = new Kromosom();

//1) initialize Data

System.out.println("Initialize Data");


populasi.getKromosomPopulasi().clear();

populasi = bangkitkanPopulasi(graph.length, 10);


129

int count_mutate = 0, breakTime=0;

boolean count_break = true;

while (count_break == true) {

//Evolusi

//2) fitness defined

double totFitness = populasi.fitnessPopulasi(graph);

//3) seleksi

Kromosom parent1 =

populasi.getKromosomPopulasi().get(populasi.rodaRoulete(graph));

Kromosom parent2 =

populasi.getKromosomPopulasi().get(populasi.rodaRoulete(graph));

//4) reproduksi

//4.a) mutasi jika sudah terjadi 1000 kali crossover

if (count_mutate == 1000) {

int indexFlacid = populasi.flacidPopulasi(populasi, graph);

Kromosom newKromosom =

populasi.mutasi(populasi.getKromosomPopulasi().get(indexFlacid));

populasi.getKromosomPopulasi().set(indexFlacid, newKromosom);

count_mutate = 0;

} else {//4.b) order crossover

Kromosom[] child = new Kromosom[2];


130

child = populasi.xo_DO(parent1, parent2);

count_mutate = count_mutate + 1;

for (int i = 0; i < child.length; i++) {

int indexFlacid = populasi.flacidPopulasi(populasi, graph);

Kromosom flacid =

populasi.getKromosomPopulasi().get(indexFlacid);

if (child[i].fittnessKromosom(graph) >

flacid.fittnessKromosom(graph)) {

populasi.getKromosomPopulasi().set(indexFlacid, child[i]);

}

}

}

//5) cek terminasi

int countIndex = 0;

for (int i = 1; i < graph.length; i++) {

Kromosom K1 = populasi.getKromosomPopulasi().get(i-1);

Kromosom K2 = populasi.getKromosomPopulasi().get(i);

if(K1.fittnessKromosom(graph) == K2.fittnessKromosom(graph)){

countIndex = countIndex + 1;

System.out.println("Count Index = "+countIndex);


131

}

}

//jika terdapat 7 kromosom sama dalam populasi maka selesai

if( countIndex >= 7){

count_break = false;

result = populasi.fittestPopulasi(graph);

}

}

return result;

}

}

Lampiran 4: Kode Program Algoritma ACS Class Ant

/*




*/

package Koloni_Semut;

/**

*

* @author Julak96

*/

public class Ant {


132

protected int[] rute;

protected boolean visited[];

public Ant(int tourSize) {

this.rute = new int[tourSize + 1];

this.visited = new boolean[tourSize];

}

protected boolean visited(int i) {

return visited[i];

}

protected void clear() {

for (int i = 0; i < visited.length; i++) {

visited[i] = false;

}

}

public double getTourLength(double Graph[][]) {

double tourLength = 0.0;

for (int i = 1; i < rute.length; i++) {

tourLength = tourLength + Graph[rute[i - 1]][rute[i]];

}

return tourLength;

}

public void showRute() {

for (int i = 0; i < rute.length; i++) {

System.out.print(rute[i] + "-");

}

}


133

}

Lampiran 5: Kode Program Algoritma ACS Class ACS

/*




*/



import java.util.Arrays;


import java.util.stream.IntStream;

/**

*

* @author Julak96

*/

public class ACS {

private int numberOfCities;

private Ant initial_trail;

private double alpha = 1.0, beta = 5.0, rho = 0.1, rand_q0=0.9;

private double[][] graph;

private double[][] pheromoneAwal_matrix;

private double[][] choiceInfo_matrix; //total

private double[][] heuristicInfo_matrix;

private int[][] neighbour_matrix;

private List<Ant> ants = new ArrayList<>();

private int ant_size;

// private Ant best_terminated[];


134

public ACS() {

}

public Ant run_colony(double Graph[][]) {

Ant result = new Ant(numberOfCities);

prepare_allVariablesAndParams(Graph);

Ant terminated_0 = new Ant(numberOfCities);

terminated_0 = initial_trail;

int counter = 0, ITERASI=0;

init_ants();

while (counter < 3) {

ITERASI += 1;

constructSolution();

all_update();

/**

* ********* terminated check ***********

*/

if (terminated_0.getTourLength(Graph) <

initial_trail.getTourLength(Graph) ||

terminated_0.getTourLength(Graph) ==

initial_trail.getTourLength(Graph)) {

counter += 1;

} else {

terminated_0 = initial_trail;

counter = 0;

}

}

result = terminated_0;

System.out.println("Iterasi = "+ITERASI);


135

return result;

}

/*

************ INITIAL VARIABLE **************

*/

public void prepare_allVariablesAndParams(double Graph[][]) {

//variables

graph = Graph;

numberOfCities = Graph.length;

ant_size = numberOfCities;

pheromoneAwal_matrix = new double[Graph.length][Graph.length];

heuristicInfo_matrix = new double[Graph.length][Graph.length];

choiceInfo_matrix = new double[Graph.length][Graph.length];

neighbour_matrix = new int[Graph.length][Graph.length];

neighbour_matrix = prepareNearestNeighbour(Graph);

initial_trail = new Ant(numberOfCities);

initial_trail = compute_initial_trail();

preparePheromoneTrail();

heuristicInfo_matrix = heuristic_information(Graph);

choiceInfo_matrix = choice_info(Graph);

}

protected int[][] prepareNearestNeighbour(double[][] Graph) {

int[][] list_nn = new int[Graph.length][Graph.length];

for (int i = 0; i < Graph.length; i++) {

double sort[] = new double[Graph.length];

for (int j = 0; j < Graph.length; j++) {

sort[j] = Graph[i][j];

}


136

Arrays.sort(sort);

for (int j = 0; j < sort.length; j++) {

for (int k = 0; k < sort.length; k++) {

if (sort[j] == Graph[i][k]) {

list_nn[i][j] = k;

}

}

}

}

return list_nn;

}

public Ant compute_initial_trail() {

Ant init_trail = new Ant(numberOfCities);

init_trail.rute[0] = neighbour_matrix[0][0];

init_trail.visited[neighbour_matrix[0][0]] = true;

int x = 0;

for (int i = 1; i < (init_trail.rute.length - 1); i++) {

int temp = init_trail.rute[i - 1];

if (init_trail.visited[neighbour_matrix[temp][x]] == true) {

while (init_trail.visited[neighbour_matrix[temp][x]] == true

&& x < numberOfCities) {

x += 1;

}

init_trail.rute[i] = neighbour_matrix[temp][x];

init_trail.visited[neighbour_matrix[temp][x]] = true;

x = 0;

} else {

init_trail.rute[i] = neighbour_matrix[temp][0];

init_trail.visited[neighbour_matrix[temp][x]] = true;

}


137

}

init_trail.rute[numberOfCities] = init_trail.rute[0];

return init_trail;

}

protected void preparePheromoneTrail() {

for (int i = 0; i < pheromoneAwal_matrix.length; i++) {

for (int j = 0; j < pheromoneAwal_matrix.length; j++) {

pheromoneAwal_matrix[i][j] = (1/initial_trail.getTourLength(graph));

}

}

}

protected double[][] heuristic_information(double[][] Graph) {

double heuristic_info[][] = new double[numberOfCities][numberOfCities];

for (int i = 0; i < numberOfCities; i++) {

for (int j = 0; j < numberOfCities; j++) {

heuristic_info[i][j] = (1 / Graph[i][j]);

}

}

return heuristic_info;

}

protected double[][] choice_info(double[][] Graph) {

double choise_info[][] = new double[numberOfCities][numberOfCities];



choise_info[i][j] = (Math.pow(pheromoneAwal_matrix[i][j], alpha)

* Math.pow(heuristicInfo_matrix[i][j], beta));


138

}

}

return choise_info;

}

/**************** CONSTRUCT SOLUTIONS ************

*/

private void init_ants() {

for (int i = 0; i < ant_size; i++) {

Ant new_ant = new Ant(numberOfCities);

ants.add(new_ant);

}

}

public void constructSolution() {


ants.get(i).clear();

}


int rand = Param.randInt(0, numberOfCities);

ants.get(i).rute[0] = rand;

ants.get(i).visited[rand] = true;

}


int step = 0;

Ant new_ant = ants.get(i);

while (step < numberOfCities) {

step = step + 1;


139

choose_and_move_to_next(new_ant, step);

local_pheromone_update(new_ant, step);

}

ants.set(i, new_ant);

}

for (int i = 0; i < ants.size(); i++) {

ants.get(i).rute[numberOfCities] = ants.get(i).rute[0];

local_pheromone_update(ants.get(i), ants.get(i).rute.length);

}

}

private void choose_and_move_to_next(Ant ant, int step) {

double q = Param.randDouble(0.0, 1.0);

int city;

if ((q > 0.0) && (q < rand_q0)) {

city = choose_best_next(ant, step);

} else {

city = pseudo_rand_proportional_rule(ant, step);

}

if (ant.visited[city] == true) {

city = nn_choose_and_move_to_the_next(ant, step);

/*check nn*/

}

ant.rute[step] = city;

ant.visited[city] = true;

}

private int choose_best_next(Ant ant, int step) {

int next_city = 0;

int curr_city = ant.rute[step - 1];


140

double value_best = (-1.0);

for (int i = 0; i < graph.length; i++) {

if (ant.visited[i] == false) {

if (choiceInfo_matrix[curr_city][i] > value_best) {

value_best = choiceInfo_matrix[curr_city][i];

next_city = i;

}

}

}

return next_city;

}

private int pseudo_rand_proportional_rule(Ant ant, int step) {

int city = 0, curr_city = ant.rute[step - 1], alpha = 1;

double q_0 = 0.9;

double low_calc = 0.0, tot_calc = 0.0, temp = 0.0;


low_calc += (Math.pow(pheromoneAwal_matrix[i - 1][i], alpha)) *

(Math.pow(heuristicInfo_matrix[i - 1][i], beta));

}

tot_calc = ((Math.pow(pheromoneAwal_matrix[curr_city][0], alpha)) *

(Math.pow(heuristicInfo_matrix[curr_city][0], beta))) / low_calc;


if (ant.visited[i] == false) {

temp = ((Math.pow(pheromoneAwal_matrix[curr_city][i], alpha)) *

(Math.pow(heuristicInfo_matrix[curr_city][i], beta))) / low_calc;

if (tot_calc < temp) {

city = i;

tot_calc = temp;

}

}


141

}

return city;

}

private int nn_choose_and_move_to_the_next(Ant ant, int step) {

int next_city = 0;

int curr_city = ant.rute[step - 1];

int x = 0;

while (ant.visited[neighbour_matrix[curr_city][x]] == true) {

x += 1;

if (x == numberOfCities - 1) {

break;

}

}

next_city = neighbour_matrix[curr_city][x];

return next_city;

}

public void local_pheromone_update(Ant ant, int step) {

int h, j;

if (step > numberOfCities) {

step = numberOfCities;

}

j = ant.rute[step];

h = ant.rute[step - 1];

pheromoneAwal_matrix[h][j] = ((1 - rho) * pheromoneAwal_matrix[h][j]) +

(rho * (1 / (numberOfCities * initial_trail.getTourLength(graph))));

choiceInfo_matrix[h][j] = Math.pow(pheromoneAwal_matrix[h][j], alpha) *

Math.pow(heuristicInfo_matrix[h][j], beta);

}


142

/*

**************** UPDATE ************************

*/

private void update_initial_trail() {

for (int i = 0; i < ants.size(); i++) {

if (initial_trail.getTourLength(graph)

> ants.get(i).getTourLength(graph)) {

initial_trail = ants.get(i);

}

}

}

public void all_update() {

update_initial_trail();

pheromone_evaporation();

global_pheromone_update();

choiceInfo_matrix = choice_info(graph);

}

private void pheromone_evaporation() {



pheromoneAwal_matrix[i][j] = (1 - rho) * pheromoneAwal_matrix[i][j];

}

}

}

private void global_pheromone_update() {

double dummy = rho * (1 / initial_trail.getTourLength(graph));

for (int i = 0; i < numberOfCities - 1; i++) {

int j = initial_trail.rute[i];


143

int h = initial_trail.rute[i + 1];

double count = (1 - rho) * pheromoneAwal_matrix[j][h];

pheromoneAwal_matrix[j][h] = count + dummy;

}

}

}

Lampiran 6: Kode Program Class Param

/*




*/


import java.io.BufferedReader;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;


import java.util.StringTokenizer;

/**

*

* @author Julak96

*/

public class Param {

public static int randInt(int min, int max) {

int randomNum = (int) (Math.random() * max) + min;

return randomNum;

}


144

public static double randDouble(double min, double max) {

double randomDouble = Math.random() * max + min;

return randomDouble;

}

public static double[][] Graph(String file) {

// System.out.println("Read Graph...........");

ArrayList<ArrayList<Double>> destinasi_GRAPH = new

ArrayList<ArrayList<Double>>();

BufferedReader buff = null;

FileReader firide = null;

String line, token = null;

StringTokenizer tokenizer;

try {

firide = new FileReader(file);

buff = new BufferedReader(firide);

while ((line = buff.readLine()) != null) {

tokenizer = new StringTokenizer(line);

ArrayList<Double> temp = new ArrayList<Double>();

temp.clear();

while (tokenizer.hasMoreTokens()) {

token = tokenizer.nextToken();

if (!token.isEmpty()) {

temp.add(Double.valueOf(token));

}

}

destinasi_GRAPH.add(temp);

}

} catch (FileNotFoundException ex) {

System.out.println("File tidak ketemu " + ex);//085701464140

} catch (IOException ex) {

System.out.println("gagal buka file " + ex);


145

} finally {

try {

buff.close();

firide.close();

} catch (IOException ex) {

System.out.println("gagal tutup file " + ex);

}

}

//create graph

double[][] graph;

graph = new double[destinasi_GRAPH.size()][destinasi_GRAPH.size()];

for (int i = 0; i < destinasi_GRAPH.size(); i++) {

for (int j = 0; j < destinasi_GRAPH.get(i).size(); j++) {

graph[i][j] = destinasi_GRAPH.get(i).get(j);

}

}

return graph;

}

}

Lampiran 7: Kode Program Class Main

package Main_Sistem;

import Genetika.Genetika;

import Genetika.Kromosom;

import Genetika.Populasi;

import Koloni_Semut.ACS;

import Koloni_Semut.Ant;

import Koloni_Semut.Param;


146

/**

*

* @author Julak96

*/

public class Run_All {

public static void main(String[] args) {

System.out.println("System Started");

System.out.println("\n************************** Data 10 Kota

**************************");

run_system("E:\\Skripsi\\Kode\\Kodingan_Skripsi_Fix\\src\\Data\\data_10Kota.tx

t");


**************************");


t");


**************************");


t");


**************************");


t");


**************************");


147


t");


**************************");


t");


**************************");


t");


**************************");


t");


**************************");


t");


**************************");

run_system("E:\\Skripsi\\Kode\\Kodingan_Skripsi_Fix\\src\\Data\\data_100Kota.t

xt");

}


148

public static void run_system(String file) {

// System.out.println("\n************************** Genetika

**************************");

// genetic_run(Param.Graph(file));

System.out.println("\n************************** Koloni Semut

**************************");

colony_run(Param.Graph(file));

}

public static void colony_run(double Graph[][]) {

Runtime.getRuntime().gc();

long startTime, endTime;

long maxMemmory = Runtime.getRuntime().maxMemory();

long totalMemory = Runtime.getRuntime().totalMemory();

long freeMemory = Runtime.getRuntime().freeMemory();

System.out.println("\nmax memory : " + maxMemmory + " "

+ "\ntotal memory : " + totalMemory + " "

+ "\nfree memory : " + freeMemory);

System.out.println("memory dump : " + (totalMemory - freeMemory));

startTime = System.currentTimeMillis();

ACS colony = new ACS();

Ant ant;

ant = colony.run_colony(Graph);

System.out.println("\nLength : " + ant.getTourLength(Graph));

endTime = System.currentTimeMillis();

long maxMemmory_2 = Runtime.getRuntime().maxMemory();

long totalMemory_2 = Runtime.getRuntime().totalMemory();


149

long freeMemory_2 = Runtime.getRuntime().freeMemory();

System.out.println("\nRun time " + (endTime - startTime) + " milliseconds");

System.out.println("max memory : " + maxMemmory_2 + " "

+ "\ntotal memory : " + totalMemory_2 + " "

+ "\nfree memory : " + freeMemory_2);

System.out.println("memory dump : " + (totalMemory_2 - freeMemory_2));

System.out.println("used : " + (freeMemory - freeMemory_2));

//

}

public static void genetic_run(double Graph[][]) {

Runtime.getRuntime().gc();

long startTime, endTime;

long maxMemmory = Runtime.getRuntime().maxMemory();

long totalMemory = Runtime.getRuntime().totalMemory();

long freeMemory = Runtime.getRuntime().freeMemory();

System.out.println("\nmax memory : " + maxMemmory + " "

+ "\ntotal memory : " + totalMemory + " "

+ "\nfree memory : " + freeMemory);

System.out.println("memory dump : " + (totalMemory - freeMemory));

startTime = System.currentTimeMillis();

Genetika genetika = new Genetika();


Kromosom kromosom;

kromosom = genetika.run_genetika(Graph);

System.out.println("Length = " + kromosom.jarakTotalKromosom(Graph));


150

//check memory again

// Runtime.getRuntime().gc();

endTime = System.currentTimeMillis();

long maxMemmory_2 = Runtime.getRuntime().maxMemory();

long totalMemory_2 = Runtime.getRuntime().totalMemory();

long freeMemory_2 = Runtime.getRuntime().freeMemory();

System.out.println("\nRun time " + (endTime - startTime) + " milliseconds");

System.out.println("max memory : " + maxMemmory_2 + " "

+ "\ntotal memory : " + totalMemory_2 + " "

+ "\nfree memory : " + freeMemory_2);

System.out.println("memory dump : " + (totalMemory_2 - freeMemory_2));

System.out.println("used : " + (freeMemory - freeMemory_2));

}

}


Download - PERBANDINGAN ALGORITMA GENETIKA DAN OPTIMASI … · KATA PENGANTAR Puji dan syukur ... Graph tak-berhingga (unlimited graf)..... 12 2.2.2.1.5. Graph berarah (directed graf atau

Top Related