perbandingan performansi algoritma genetika dan algoritma...

TUGAS AKHIR

PERBANDINGAN PERFORMANSI ALGORITMA

GENETIKA DAN ALGORITMA KOLONI SEMUT

PADA JADWAL PERJALANAN KERETA API

JALUR CIREBON - JAKARTA

WASKITO ADHI OKTAFIANTO

15102117

PROGRAM STUDI S1 INFORMATIKA

FAKULTAS TEKNOLOGI INDUSTRI DAN INFORMATIKA

INSTITUT TEKNOLOGI TELKOM PURWOKERTO

PURWOKERTO

2019

i

TUGAS AKHIR




JALUR CIREBON – JAKARTA

PERFORMANCE COMPARING OF GENETIC

ALGORITHM AND ANT COLONY ALGORITHM ON

TRAVEL SCHEDULE OF RAILWAYS

CIREBON - JAKARTA

Disusun Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Komputer


15102117

PROGRAM STUDI S1 INFORMATIKA

FAKULTAS TEKNOLOGI INDUSTRI DAN INFORMATIKA

INSTITUT TEKNOLOGI TELKOM PURWOKERTO

PURWOKERTO

2019

ii

HALAMAN PERSETUJUAN PEMBIMBING








CIREBON - JAKARTA

Dipersiapkan dan Disusun Oleh


15102117

Usulan Penelitian Tugas Akhir telah disetujui pada tanggal

21 Oktober 2019

Pembimbing I,

Rima Dias Ramadhani, S.Kom, M.Kom.

NIDN. 0602039301

Pembimbing II,

Yogo Dwi Prasetyo, M.Si.

NIDN. 0101088702

iii

LEMBAR PENGESAHAN PEMBIMBING



DALAM OPTIMASI JADWAL PERJALANAN

KERETA API JALUR CIREBON – JAKARTA




CIREBON - JAKARTA



15102117

Telah Diujikan dan Dipertahankan dalam Sidang Ujian Tugas Akhir

Pembimbing I, Pembimbing II, Rima Dias Ramadhani, S.Kom.,M.Kom.

NIDN. 0602039301

Yogo Dwi Prasetyo., M.Si.

NIDN. 0101088702

Tugas Akhir ini diterima sebagai salah satu persyaratan untuk

Memperoleh gelar Sarjana Komputer

Tanggal 28 Oktober 2019

Dekan

Didi Supriyadi, S.T., M.Kom.

NIK. 13840016

iv

HALAMAN PENETAPAN PENGUJIAN








CIREBON - JAKARTA



15102117

Tugas Akhir Telah diuji dan Dinilai Panitia Penguji Program Studi S1

Informatika Fakultas Teknologi Industri dan Informatika

Institut Teknologi Telkom Purwokerto

Pada Tanggal : 28 Oktober 2019

Ketua

Penguji,

(Tri Ginanjar Laksana, S.Kom., M.Cs., M.Kom.)

NIDN. 0407088502

Anggota

Penguji I,

(Siti Khomsah, S.Kom., M.Cs.)

NIDN. 0517108101

v

HALAMAN PERNYATAAN KEASLIAN TUGAS AKHIR

Yang bertanda tangan dibawah ini:

Nama Mahasiswa : Waskito Adhi Oktafianto

NIM : 15102117

Program Studi : Informatika

Menyatakan bahwa Tugas Akhir dengan judul berikut:

PERBANDINGAN PERFORMANSI ALGORITMA GENETIKA DAN

ALGORITMA KOLONI SEMUT PADA JADWAL PERJALANAN

KERETA API JALUR CIREBON – JAKARTA

Dosen Pembimbing Utama : Rima Dias Ramadhani, S.Kom., M.Kom.

Dosen Pembimbing Pendamping : Yogo Dwi Prasetyo, M.Si.

1. Karya tulis ini adalah benar-benar ASLI dan BELUM PERNAH diajukan untuk mendapatkan gelar akademik, baik di Institut Teknologi Telkom

Purwokerto maupun di Perguruan Tinggi lainnya.

2. Karya tulis ini merupakan gagasan, rumusan, dan penelitian Saya Sendiri, tanpa bantuan pihak lain kecuali arahan dari Tim Dosen Pembimbing.

3. Dalam Karya tulis ini tidak terdapat karya atau pendapat orang lain, kecuali secara tertulis dengan jelas dicantumkan sebagai acuan dalam naskah dengan

disebutkan nama pengarang dan disebutkan dalam Daftar Pustaka pada karya

tulis ini.

4. Perangkat lunak yang digunakan dalam penelitian ini sepenuhnya menjadi tanggungjawab Saya, bukan tanggungjawab Institut Teknologi Telkom

Purwokerto.

5. Pernyataan ini Saya buat dengan sesungguhnya, apabila dikemudian hari terdapat penyimpangan dan ketidakbenaran dalam pernyataan ini, maka Saya

bersedia menerima Sanksi Akademik dengan pencabutan gelar yang sudah

diperoleh serta sanksi lainnya sesuai dengan norma yang berlaku di

Perguruan Tinggi.

Purwokerto, 21 Oktober 2019

Yang Menyatakan,

(Waskito Adhi Oktafianto)

viii

KATA PENGANTAR

Puji syukur penulis panjatkan kehadiran Allah SWT yang telah

memberikan rahmat dan hidayah-Nya dalam penyusunan skripsi, sehingga penulis

dapat menyelesaikan skripsi dengan judul “Perbandingan Performansi

Algoritma Genetika dan Algoritma Koloni Semut Pada Jadwa Perjalanan

Kereta Api Jalur Cirebon – Jakarta”.

Skripsi ini dapat diselesaikan karena dengan adanya kerjasama, bantuan

dan motivasi dari berbagai pihak. Ucapan terimakasih ini penulis tunjukan kepada

yang terhormat:

1. Yth. Bapak Didi Supriyadi, S.T.,M.Kom, selaku Dekan FTII. 2. Yth. Bapak Fahrudin Mukti Wibowo, S.Kom.M.Eng., selaku Ketua

Program Studi Teknik Informatika.

3. Yth. Ibu Rima Dias Ramadhani, S.Kom.,M.Kom., selaku dosen pembimbing I yang telah membantu membimbing, dan mengarahkan

untuk memberikan bimbingan pada penulis dalam menyelesaikan

skripsi.

4. Yth. Bapak Yogo Dwi Prasetyo, M.Si, selaku dosen pembimbing II yang telah meluangkan waktu, membimbing, dan mengarahkan untuk

memberikan bimbingan pada penulis dalam menyelesaikan skripsi.

5. Ayahanda dan Ibunda tercinta serta kakakku tersayang, yang telah memberikan do’a dan dorongan baik secara moril, materi, spiritual

dalam menyelesaikan skripsi.

6. Tri Cahyo Nugroho yang telah memberikan motivasi dalam menyelesaikan skripsi.

7. Sahabat dan rekan-rekan teknik informatika 2015 yang bersama-sama berjuang dalam menyelesaikan skripsi.

Semoga bantuan yang telah diberikan kepada penulis mendapatkan

imbalan dari Allah Yang Maha Pengasih.

Purwokerto, 21 Oktober 2019

Waskito Adhi Oktafianto

ix

DAFTAR ISI

Halaman

HALAMAN JUDUL..... ................................................................................................ i

PENGESAHAN. ......................................................................................................... iii

ABSTRAK. ................................................................................................................. vi

ABSTRACT ................................................................................................................. vii

KATA PENGANTAR. ............................................................................................. viii

DAFTAR ISI ............................................................................................................... ix

DAFTAR TABEL. ...................................................................................................... xi

DAFTAR GAMBAR. ............................................................................................... xiii

BAB I PENDAHULUAN

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

1.2 Rumusan Masalah. ............................................................................... 3

1.3 Tujuan Penelitian. ................................................................................. 3

1.4 Batasan Masalah. .................................................................................. 4

1.5 Manfaat Penelitian. ............................................................................... 4

BAB II DASAR TEORI

2.1 Tinjauan Pustaka .................................................................................. 5

2.2 Landasan Teori ................................................................................... 11

2.2.1 Grafik Perjalanan Kereta Api (GAPEKA). ........................................ 11

2.2.2 Optimasi ............................................................................................. 11

2.2.3 Algoritma Optimasi Koloni Semut. ................................................... 12

2.2.4 Algoritma Genetika ............................................................................ 16

BAB III METODE PENELITIAN

3.1 Objek Penelitian ..................................................................................... 24

3.2 Metode Penelitian ................................................................................. 24

3.3 Teknik Pengumpulan Data .................................................................... 25

3.4 Analisa Data ........................................................................................... 27

x

3.4.1 Analisa Dataset ................................................................................... 27

3.5 Penetapan Metode Koloni Semut........................................................... 32

3.5.1 Implementasi Algoritma Semut Dalam Bentuk Kode Program ......... 32

3.5.1.1 Inisiasi Parameter ............................................................................. 32

3.5.1.2 Penyusunan Rute Kunjungan ........................................................... 32

3.5.1.3 Panjang Rute .................................................................................... 33

3.5.1.4 Jalur Tercepat ................................................................................... 33

3.5.2 Contoh Percobaan α, β, ρ .................................................................... 34

3.5.3 Pengaruh Nilai α, β, ρ Terhadap Algoritma Koloni Semut ................ 35

3.6 Penerapan Metode Genetika .................................................................. 37

3.6.1 Evaluasi Fungsi fitness ........................................................................ 38

3.6.2 Seleksi ................................................................................................. 39

3.6.3 Crossover ............................................................................................ 39

3.6.4 Mutasi ................................................................................................. 40

3.6.5 Kondisi Selesai.................................................................................... 42

3.6.6 Tabel Keberangkatan Kereta Api........................................................ 42

3.6.7 Implementasi Program Algoritma Genetika ....................................... 53

BAB IV HASIL DAN PEMBAHASAN

4.1 Simulasi Algoritma Koloni Semut ......................................................... 57

4.2 Simulasi Algoritma Genetika ................................................................. 66

4.3 Pembahasan dan Analisa........................................................................ 70

BAB V PENUTUP

5.1 Kesimpulan ............................................................................................ 71

5.2 Saran ...................................................................................................... 71

DAFTAR PUSTAKA ....................................................................................................

LAMPIRAN ...................................................................................................................

xi

DAFTAR TABEL

2.1 Penelitian Terkait ..................................................................................... 8

2.2 Pengkodean Biner .................................................................................. 19

2.3 Pengkodean Permutasi ........................................................................... 20

2.4 Pengkodean Nilai ................................................................................... 20

3.1 Perjalanan Kereta Api Keberangkatan Gambir Pasar Senen ................. 26

3.2 Rata-rata Perbandingan Kereta Api ...................................................... 27

3.3 Simbol Titik Stasiun .............................................................................. 27

3.4 Jarak Antar Titik ................................................................................... 28

3.5 Visibilitas Antar Titik ............................................................................ 29

3.6 Jadwal Perjalanan Kereta Api ................................................................ 43

3.7 Inisialisasi Populasi Awal ...................................................................... 44

3.8 Total Nilai Fitness .................................................................................. 47

3.9 Probabilitas Tiap Kromosom ................................................................. 48

3.10 Interval Tiap Kromosom ...................................................................... 48

3.11 Populasi Baru Hasil Seleksi ................................................................. 49

3.12 Crossover ............................................................................................. 50

4.1 Penetapan Parameter Algoritma Koloni Semut ..................................... 57

4.2 Hasil Percobaan Performansi Algoritma Koloni Semut ........................ 58









4.10 Hasil Percobaan Performansi Algoritma Koloni Semut ...................... 64

4.11 Hasil Percobaan Performansi Algoritma Koloni Semut ...................... 65

xii

4.12 Gabungan Hasil Percobaan Performansi Algoritma Koloni Semut ..... 65

4.8 Hasil Percobaan Performansi Algoritma Genetika ................................ 67

xiii

DAFTAR GAMBAR

2.1 Tingkah Laku Semut A .......................................................................... 12

2.2 Tingkah Laku Semut B .......................................................................... 13

2.3 Tingkah Laku Semut C .......................................................................... 13

2.4 Flowchart Proses Algoritma Koloni Semut ........................................... 15

2.5 Flowchart Proses Algoritma Genetika................................................... 18

3.1 Flowchart Penelitian .............................................................................. 24

3.2 Jarak Antar Stasiun ................................................................................ 26

3.3 Pengaruh Performa α, β, ρ ..................................................................... 34

3.4 Pengaruh Nilai α terhadap Koloni Semut .............................................. 35

3.5 Pengaruh Nilai β terhadap Koloni Semut .............................................. 35

3.6 Pengaruh Nilai ρ terhadap Koloni Semut .............................................. 36

3.7 Flowchart Populasi Awal ...................................................................... 38

3.8 Flowchart Crossover ............................................................................. 40

3.9 Flowchart Mutasi ................................................................................... 41

perbandingan performansi algoritma genetika dan algoritma...

Documents