PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN QUADRATIC ASSIGNMENT PROBLEM (QAP)

ADLN Perpustakaan Universitas Airlangga

PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN QUADRATIC ASSIGNMENT PROBLEM (QAP)

SKRIPSI

NAILIL HIDAYAH

PROGRAM STUDI S-1 MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS AIRLANGGA 2015 i Skripsi


NAILIL HIDAYAH


PENERAPAN ALGORITMA CAT SWARM OPTIMIZANON (CSO} UNTUK MENYELESAIKAN SUADRATTC ASSIGNMENT PROBLEM

(QAP)

,

SKRIPSI

Sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Sains Bidang Matematika Pada Fakultas Sains dan Teknologi

Utivoriiitf,s Aiflangga

Disetujui oleh

:

PembimbingII,

@ .--<-

Dr. Herrv Sunraiitno. M.Si NIP.19680404 199403

Skripsi


I

020

NAILIL HIDAYAH


LEMBAR PT,NGESAHAN NASKAH SKRIPSI

Judul

Penerapan Algoritma Cal Swarm Optimizmion (CSO)

untuk Menyelesaikan Quadratic Assignment Problem (QAP) Penyusun

Nailil Hidayah

NIM

08tl12048

Pembimbing Pembimbing

I II

Dr. Miswanto, M.Si Dr. Herry Supqiitno, M.Si

Tanggal Seminar

Disetujui oleh

:

Pembimhing

NrP. 19680204 199303

I

002

II,

NrP.19680404 199403

I

020

. Mengetahui, Ketua Departemen Matematika Fakultas Sains dan Teknologi

Dr. Miswanto. M.Si NIP. 19680204 199303 1 002

iii Skripsi


NAILIL HIDAYAH


PEDOMAN PENGGUNAAN SKRIPSI

Skripsi ini tidak dipublikasikan, namun tersedia di perpustakaan dalam lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seizin penulis dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah. Dokumen skripsi ini merupakan hak milik Universitas Airlangga.

i Skripsi


NAILIL HIDAYAH


KATA PENGANTAR

Dengan menyebut asma Allah SWT yang Maha Pengasih lagi Maha Penyayang. Segala puji dan syukur alhamdulillah penulis ucapkan kepada-Nya yang telah melimpahkan rahmat dan karunia-Nya, sehingga penulis dapat menyelesaikan skripsi yang berjudul ”Penerapan Cat Swarm Optimization (CSO) Untuk Menyelesaikan Quadratic Assignment Problem

(QAP)” ini

dengan baik. Serta Shalawat dan Salam semoga tetap terlimpahkan kepada Rasulullah Muhammad SAW yang mengantarkan pada sebuah kehidupan yang penuh keselamatan di dunia dan di akhirat. Pada kesempatan ini, penulis ingin menyampaikan terima kasih yang sebesar-besarnya kepada: 1. Universitas Airlangga yang telah memberikan kesempatan bagi penulis untuk melanjutkan pendidikan tinggi khususnya dalam program studi Matematika di Fakultas Sains dan Teknologi. 2. Bapak Dr. Miswanto, M.Si selaku Ketua Departemen Matematika Fakultas Sains dan Teknologi Universitas Airlangga sekaligus dosen pembimbing I yang senantiasa meluangkan waktu, dan dengan sabar memberikan saran, dorongan, serta bimbingan kepada penulis sehingga dapat menyelesaikan skripsi ini dengan baik. 3. Bapak Dr. Herry Suprajitno, M.Si selaku dosen wali selama menjadi mahasiswa di Program Studi Matematika Fakultas Sains dan Teknologi ii Skripsi


NAILIL HIDAYAH


Universitas Airlangga yang telah banyak memberikan arahan dan nasihat demi kesuksesan menjadi mahasiswa, dan selaku dosen Pembimbing II yang senantiasa mencurahkan segenap ilmu, waktu, tenaga, saran, dan motivasi kepada penulis selama bimbingan hingga menyelesaikan skripsi ini. 4. Ibu Auli Damayanti, S.Si, M.Si selaku dosen penguji I yang telah banyak memberikan pengetahuan, saran, dan masukan pada proses penyelesaian naskah skripsi. 5. Segenap Bapak dan Ibu dosen yang telah mengajarkan penulis berbagai hal mulai dari ilmu hingga pengalaman-pengalaman. 6. Kedua orang tua tersayang, Bapak Moh. Humaidi dan Ibu Aminatus Sholihah, kakak Humaidah dan Nihayatus Sa’adah, adik Himayatus Shofwatir Rohmah, beserta segenap keluarga besar penulis yang telah memberikan doa, dukungan, cinta kasih, dan kepercayaan yang begitu besar. 7. Mas Shendy Akbar Andhyka yang telah menjadi motivator dan psikolog terbaik yang selalu mendoakan dan mendukung penulis selama penyusunan skripsi. 8. Seluruh teman-teman S-1 Matematika 2011 Universitas Airlangga khususnya Fafa, Linda, Rizka, Naila serta sahabat-sahabat penulis, Faizah, mbak Efi, Anis, mbak Atik, Iis, dan Bariroh yang selalu memberi motivasi, inspirasi, dan semangat kepada penulis. 9. Serta semua pihak yang tidak dapat disebutkan satu per satu, yang telah membantu penulis hingga terselesaikannya skripsi ini.

iii Skripsi


NAILIL HIDAYAH


Penulis berharap semoga skripsi ini dapat bermanfaat bagi semua pihak sebagai bahan pustaka, penambah pengetahuan maupun sebagai acuan dalam mengembangkan penelitian selanjutnya.

Surabaya, November 2015 Penulis,

Nailil Hidayah

iv Skripsi


NAILIL HIDAYAH


Nailil Hidayah, 2015, Penerapan Algoritma Cat Swarm Optimization (CSO) untuk Menyelesaikan Quadratic Assignment Problem (QAP). Skripsi ini dibawah bimbingan Dr. Miswanto, M.Si dan Dr. Herry Suprajitno, M.Si. Departemen Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga, Surabaya

ABSTRAK

Quadratic Assignment Problem (QAP) merupakan masalah penugasan yang membahas penempatan fasilitas pada lokasi dan bertujuan meminimalkan total biaya/jarak tempuh perpindahan barang antar fasilitas pada suatu lokasi. Tujuan dari skripsi ini adalah untuk menyelesaikan quadratic assignment problem dengan menggunakan algoritma Cat Swarm Optimization (CSO). CSO merupakan algoritma yang diadaptasi dari perilaku sekelompok kucing dalam mencari dan melacak mangsa. Algoritma ini dikembangkan oleh Tsu Chuan Chu dan Pe We Tsai tahun 2007 di Taiwan. Proses dari algoritma ini dimulai dengan inisialisasi parameter, membentuk populasi awal kucing, menghitung nilai objektif, menentukan self position considering (SPC), menentukan bendera setiap kucing, memproses setiap kucing sesuai dengan benderanya, dan menentukan global best, iterasi ini berlanjut sampai iterasi maksimum dipenuhi. Program dibuat dengan bahasa pemrograman C++ yang diimplementasikan pada 4 data yaitu, 5 fasilitas dan 5 lokasi, 12 fasilitas dan 12 lokasi, 20 fasilitas dan 20 lokasi, serta 33 fasilitas dan 33 lokasi. Diperoleh total biaya/jarak tempuh terbaik masing-masing adalah 50, 1652, 7040, dan 381768. Berdasarkan hasil implementasi yang diperoleh, dapat disimpulkan bahwa semakin besar maksimum iterasi, jumlah kucing, dan seeking memory pool (SMP), maka solusi dari penyelesaian QAP cenderung semakin baik yakni dengan fungsi objektif yang minimum.

Kata Kunci : Cat Swarm Optimization (CSO), Quadratic Assignment Problem (QAP), Algoritma

v Skripsi


NAILIL HIDAYAH


Nailil Hidayah, 2015, Application of Cat Swarm Optimization (CSO) Algorithm to Solve Quadratic Assignment Problem (QAP). This final project was supervised by Dr. Miswanto, M.Si and Dr. Herry Suprajitno, M.Si. Mathematics Department, Faculty of Science and Technology, Airlangga University, Surabaya

ABSTRACT

Quadratic Assignment Problem (QAP) is a assignment problem which addresses the placement of facilities to locations and aims to minimize the total cost or distance of materials movement among facilities on locations. The purpose of writing this undergraduate thesis is to solve the quadratic assignment problem using a Cat Swarm Optimization algorithm (CSO Algorithm). CSO is an algorithm adapted from the behavior of cats in seeking and tracing prey. This algorithm was firstly developed by Tsu Chu Chuan and Pe We Tsai in 2007 at Taiwan. Process of the algorithm begins with the initialization parameters, generation of the initial population of cat, calculate the objective function, determining self position considering (SPC), determining flag of each cat, process each cat according its flag, and determining global best, this process continues until maximum iteration filled. The program was built using C++ programming language and implemented on the four sample data, 5 facillities and 5 locations, 12 facilities and 12 locations, 20 facilities and 20 locations, and 33 facilities and 33 locations. The computation processes obtain the best total cost or distance ranges for each data are 50, 1652, and 381768. Based on the implementation results, it was obtained the higher maksimum iteration, size of cats, and seeking memory pool (SMP), result the better QAP solution as indicated by minimum objective function.

Keywords : Cat Swarm Optimization (CSO), Quadratic Assignment Problem (QAP), Algorithm

vi Skripsi


NAILIL HIDAYAH


DAFTAR ISI

Halaman HALAMAN JUDUL .....................................................................................

i

LEMBAR PERNYATAAN ...........................................................................

ii

LEMBAR PENGESAHAN NASKAH SKRIPSI .........................................

iii

LEMBAR PEDOMAN PENGGUNAAN SKRIPSI .....................................

iv

KATA PENGANTAR ..................................................................................

v

ABSTRAK .................................................................................................... viii ABSTRACT ..................................................................................................

ix

DAFTAR ISI .................................................................................................

x

DAFTAR GAMBAR ..................................................................................... xiv DAFTAR TABEL ......................................................................................... xvi DAFTAR LAMPIRAN .................................................................................. xviii BAB I

BAB II

PENDAHULUAN .........................................................................

1

1.1

Latar Belakang .....................................................................

1

1.2

Rumusan Masalah ................................................................

3

1.3

Tujuan ..................................................................................

3

1.4

Manfaat ................................................................................

4

TINJAUAN PUSTAKA ................................................................

5

2.1

Graf (Graph) ........................................................................

5

2.2

Permasalahan Penugasan (Assignment Problem).................

6

2.3

Quadratic Assignment Problem (QAP) ..............................

7

2.4

Cat Swarm Optimization (CSO)...........................................

8

vii Skripsi


NAILIL HIDAYAH


2.4.1 Seeking Mode ........................................................... 10 2.4.2 Tracing Mode .......................................................... 12 2.4.3 Algoritma CSO ........................................................ 13 2.5

Pengkodean ......................................................................... 14

2.6

Pemrograman C++ .............................................................. 15

BAB III METODE PENELITIAN............................................................... 17 BAB IV PEMBAHASAN ............................................................................ 25 4.1

Quadratic Assignment Problem ........................................... 25

4.2

Cat Swarm Optimization ...................................................... 25 4.2.1 Input Data ................................................................. 27 4.2.2 Inisialisasi Parameter................................................ 27 4.2.3 Pembangkitan Posisi Awal Kucing .......................... 28 4.2.4 Pembangkitan Kecepatan Awal Kucing ................... 29 4.2.5 Menentukan Bendera Kucing ................................... 29 4.2.6 Transformasi Posisi Kucing ..................................... 30 4.2.7 Menghitung Fungsi Tujuan ...................................... 31 4.2.8 Menentukan Solusi Terbaik ..................................... 33 4.2.9 Menentukan Self Position Considering (SPC) ......... 34 4.2.10 Melakukan Proses Seeking Mode ............................. 34 4.2.11 Melakukan Proses Tracing Mode ............................. 39 4.2.12 Menentukan Solusi Terbaik Global (Global Best) ... 40

4.3

Data ...................................................................................... 41

4.4

Penyelesaian Secara Manual Contoh Kasus ........................ 42

viii Skripsi


NAILIL HIDAYAH


4.4.1 Input Data dan Inisialisasi Parameter ....................... 42 4.4.2 Membangkitkan Posisi Awal ................................... 42 4.4.3 Membangkitkan Kecepatan Awal ............................ 43 4.4.4 Menentukan Bedera (flag) ........................................ 44 4.4.5 Transformasi Posisi Kucing ke Dalam Kode Permutasi .................................................................. 45 4.4.6 Menghitung Fungsi Tujuan dari Posisi Awal ........... 45 4.4.7 Menentukan Solusi Terbaik Sementara.................... 47 4.4.8 Menentukan Self Position Considering (SPC) ......... 47 4.4.9 Melakukan Proses Seeking Mode ............................. 48 4.4.10 Melakukan Proses Tracing Mode ............................. 57 4.4.11 Menentukan Solusi Terbaik Global (Global Best) ... 60 4.5

Implementasi Program pada Contoh Kasus QAP ........... 61 4.5.1

Implementasi Program pada Data 1 (5 Fasilitas dan 5 Lokasi) ................................................................... 61

4.5.2

Implementasi Program pada Data 2 (12 Fasilitas dan 12 Lokasi) ................................................................. 62

4.5.3

Implementasi Program pada Data 3 (20 Fasilitas dan 20 Lokasi) ................................................................. 64

4.5.4

Implementasi Program pada Data 4 (33 Fasilitas dan 33 Lokasi .................................................................. 65

4.5.5

Perbandingan Solusi Optimal dengan Solusi Terbaik CSO .......................................................................... 66

ix Skripsi


NAILIL HIDAYAH


BAB V

KESIMPULAN DAN SARAN ..................................................... 67 5.1

Kesimpulan .......................................................................... 67

5.2

Saran..................................................................................... 68

DAFTAR PUSTAKA .................................................................................... 69 LAMPIRAN

x Skripsi


NAILIL HIDAYAH


DAFTAR GAMBAR

Gambar

Judul

Halaman

3.1

Flowchart Algoritma Cat Swarm Optimization

22

3.2

Flowchart Seeking Mode

23

3.3

Flowchart Tracing Mode

24

4.1

Prosedur CSO untuk Menyelesaikan QAP

26

4.2

Prosedur Input Data

27

4.3

Prosedur Inisialisasi Parameter

28

4.4

Prosedur Pembangkitan Posisi Awal Kucing

28

4.5

Prosedur Pembangkitan Kecepatan Awal Kucing

29

4.6

Prosedur Penentuan Bendera Kucing

30

4.7

Prosedur Transformasi Posisi Kucing ke Dalam Kode Permutasi

31

4.8

Prosedur Pembentukan Matriks Penempatan

32

4.9

Prosedur Menghitung Fungsi Tujuan

32

4.10

Prosedur Penentuan Solusi Terbaik

33

4.11

Prosedur Penentuan Nilai SPC

34

4.12

Prosedur Seeking Mode

35

4.13

Prosedur Modifikasi Tiruan Kucing

36

4.14

Prosedur Penentuan Individu Baru

37

4.15

Prosedur Perhitungan Nilai Fitness

38

4.16

Prosedur Perhitungan Probabilitas

39

xi Skripsi


NAILIL HIDAYAH


4.17

Prosedur Tracing Mode

40

4.18

Prosedur Penentuan Global Best

41

xii Skripsi


NAILIL HIDAYAH


DAFTAR TABEL

Tabel

Judul

Halaman

4.1

Posisi Awal Kucing

43

4.2

Kecepatan Awal Kucing

43

4.3

Hasil Penentuan Bendera Kucing

44

4.4

Hasil Transformasi Posisi Kucing ke Dalam Kode Permutasi

45

4.5

Hasil Nilai Fungsi Tujuan

47

4.6

Nilai

48

4.7

Hasil Copy Kucing-1

49

4.8

Hasil Modifikasi Tiruan Kucing-1

50

4.9

Hasil Transformasi Posisi Baru Tiruan Kucing-1 dan Nilai Fungsi Tujuannya

51

4.10

Hasil Perhitungan Nilai Fitness Tiruan Kucing-1

51

4.11

Hasil Roulette Wheel Kucing-1

53

4.12


54

4.13

Hasil Transformasi Posisi Baru Tiruan Kucing-2

54

4.14

Hasil Fungsi Tujuan, Nilai Fitness dan Probabilitas Tiruan Kucing-2

55

4.15


55

4.16


55

4.17

Hasil Transformasi Posisi Baru Tiruan Kucing-5

56

4.18

Hasil Fungsi Tujuan, Nilai Fitness dan Probabilitas Tiruan Kucing-5

56

Kucing

xiii Skripsi


NAILIL HIDAYAH


4.19


57

4.20

Hasil Solusi Terbaik Seeking Mode

57

4.21

Kecepatan dan Posisi Baru Kucing-4

59

4.22

Hasil Transformasi Posisi Baru Kucing pada Tracing Mode

59

4.23

Hasil Running Program pada Data 1

62

4.24


63

4.25


64

4.26


65

4.27

Hasil Perbandingan Solusi Optimal dengan Solusi Terbaik CSO

66

xiv Skripsi


NAILIL HIDAYAH


DAFTAR LAMPIRAN

Nomor

Judul Lampiran

1.

Data 5 Fasilitas dan 5 Lokasi

2.


3.


4.


5.

Source Code Program

6.

Output Program Solusi Terbaik pada Data 5 Fasilitas dan 5 Lokasi

7.


8.


9.


xv Skripsi


NAILIL HIDAYAH

PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN QUADRATIC ASSIGNMENT PROBLEM (QAP)

Recommend Documents