implementasi algoritma evolusi diferensial untuk...
TRANSCRIPT
IMPLEMENTASI ALGORITMA EVOLUSI DIFERENSIAL UNTUK
PENEMPATAN IKLAN BARIS PADA SURAT KABAR
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1
Teknik Informatika Universitas Muhammadiyah Malang
Oleh:
CATUR PUTRI PERTIWI
NIM: 08560326
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS MUHAMMADIYAH MALANG
2013
i
ABSTRAK
Penempatan Iklan baris merupakan suatu pemasalahan tentang tata letak iklan baris pada pada surat kabar dimana iklan baris akan di letakan pada suatu halaman dengan ukuran tertentu sehingga harus ada iklan yang dipilih. Setiap iklan yang dipilih akan diletakan pada halaman yang telah tersedia tanpa melebihi luas halaman yang telah ditentukan agar dapat memaximalkan luas halaman dan juga meningkatkan profit atau keuntungan. Dalam implementasinya digunakan algoritma evolusi diferiansial dimana algoritma ini merupakan algoritma pengembangan dari algoritma genetika yang prinsip dan filosofinyasama seperi genetika yang meniru prilaku alam. Evolusi diferensial memiliki solusi optimal global yang multidimensional dengan probabilistik yang lebih baik, lebih efektif, handal dan performansinya kuat. Implementasi algoritma evolusi diferensial ini dikembangakan dengan bahasa PHP. Dari hasil pengujian yang telah dilakukan hasil implementasi dapat memberikan hasil yang cukup baik, dimana algoritma evolusi diferensial mampu memberikan solusi optimal sesuai dengan yang diharapkan. Kata kunci: Algoritma Evolusi diferensial
ii
ABSTRACT
The line advertisement’s placement is became a problem in a newspaper with certain size so it is needed to choose what’s exactly the adverstiment to be put in a page. Every choosen adverstiment will be put in page without over wide the page to maximizethe page capacity and also to increase the profit. In the implementation is using the differential evolution algorythm which this algorithm is the development from genetic algorythm which has the same princip with natural genetic and filosophy. Differential evolution algorythm also has better probability, more effective, and strong perform. The differential evolution algorythm is from PHP language’s development. From the test has been done, the implementation gives good result. That’s it mean that differential evolution algorithm can give optimal solution as we hope. Key words : Differential Evolution Algorythm
iii
LEMBAR PERSEMBAHAN Penyusunan dan pembuatan Tugas Akhir ini tidak lepas dari bantuan berbagai
pihak , oleh karena itu dengan segala kerendahan hati, penulis menyampaikan
terimakasih kepada:
1. Allah Subhanahu Wa Ta’ala yang selalu memberikan rahmat dan hidayah-
Nya serta segala bentuk anugrah yang telah dilimpahkan.
2. Rasulullah Muhammad SAW, suri tauladan dan panutan terbaik bagi
umatnya.
3. Mamak dan Bapak tercinta yang selalu memberikan yang terbaik untuk
saya,doa yang tulus, ,semangat, motivasi, pelajaran hidup serta kebahagian
tanpa batas. Meski tidak selalu sempurna bagi saya mamak dan bapak adalah
malaikat yang menjelma.
4. Ibu Ir. Nur Alif Mardiyah, MT selaku dosen pembimbing I serta Ibu Gita
Indah Marthasari, S.T selaku dosen pembimbing II yang telah memberikan
banyak pengarahan dan bimbingannya dalam penyelesaian Tugas Akhir ini .
5. Seluruh dosen pengajar di Jurusan Teknik Informatika yang telah
membimbing saya dalam menuntut ilmu sehingga saya bisa menjadi
seseorang yang lebih baik.
6. Kakak-kakak saya (Mba Echo, Mas Rendra, Mas Yoga) yang selalu
memberikan doa, dorongan dan semangat untuk terus move on dan gak
gampang nyerah, gambaran kesuksesan nyata dalam pencapaian mimpi dan
harapan.
7. Rizky Indra, atas doa, semangat dan dukungannya selama ini akhirnya
langkah awal sudah terlewati. :D
8. Teman-teman terindah (Nova, Intan, Poppy, Mba Icha, Mba Pit, Mba Yul,
Luluk, Anita, Bibil, Nizar, Wahyu, Rifan, Arif, Faris, Hamzah, *cempe dan
cempewati lainnya*) dan teman seperjuangan di kampus putih yang sudah
memberikan tinta warnanya dan manjadikan kanvas hidup ini lebih indah dan
ceria. Tetap bersinar Kawan.
iv
9. Teman gila (Rando, Kolim, Pakde ), gerombolan gak tau malu yang selalu
menghadirkan tawa, penghilang stress yang bikin laris warung kopi. Serta
sahabat lama saya (Lindi, Windi, Totoy) yang sudah lama gak ketemu tapi
tetap ingat untuk ngasih semangat.
10. Melodi pembakar semangat, jurus ampuh melawan rasa putus asa yang bikin
mata terus melek dan tangan gak mau berhenti ngetik.
Malang, 20Januari 2013
Penulis
Catur Putri Pertiwi
v
MOTTO
“Kamu adalah apa yang kamu pikirkan, ketika kamu berpikir gagal maka
kamu akan gagal tetapi ketika kamu berpikir bisa maka kamu akan bisa melakukan
apapun diluar batas kemampuanmu selama ini”
“percuma mengeluh dan menyesali keadaan, buka mata lihat sekitar maka
akan banyak kebahagian yang akan dirasakan”
“You’re the universe, you’re the driver not passenger in life. And when you’re
ready, you won’t have to try because you’re the universe and there ain’t nothing you
can’t do. If you conceive it, you can achive it (The Brand New Heavy) ”
vi
KATA PENGANTAR
Assalamu'alaikum Wr. Wb.
Dengan memanjatkan puji syukur kehadirat Allah SWT atas limpahan rahmat yang
telah diberikan sehingga Penulis dapat menyelesaikan Tugas Akhir yang berjudul
“Implementasi Algoritma Evolusi Diferensial Untuk Penempatan Iklan Baris
Pada Surat Kabar”.
Penulis menyadari sepenuhnya bahwa penulis Tugas Akhir ini masih banyak
kekurangan, oleh karena itu penulis mengharapkan saran dan kritik yang membangun
agar tulisan ini bermanfaat bagi perkembangan ilmu kedepannya.
Akhir kata penulis mengucapkan terima kasih kepada semua pihak yang telah
membantu sehingga tugas akhir ini terselesaikan.
Wassalamu’alaikum Wr. Wb
Malang, 20Januari 2013
Penulis
Catur Putri Pertiwi
vii
DAFTAR ISI
Halaman Judul Lembar persetujuan Lembar Pengesahan Lembar Pernyataan Keaslian Abstrak ........................................................................................................ i Abstract ....................................................................................................... ii Lembar Persembahan ................................................................................... iii Motto ........................................................................................................... v Kata Pengantar ............................................................................................. vi Daftar Isi ...................................................................................................... vii Daftar Gambar ............................................................................................. ix Daftar Tabel ................................................................................................. xi BAB I PENDAHULUAN
1.1 Latar Belakang .................................................................... 1 1.2 Rumusan Masalah ............................................................... 2 1.3 Batasan Masalah .................................................................. 2 1.4 Tujuan ............................................................................... 3 1.5 Metodologi Penelitian ......................................................... 3
1.5.1 Studi Pustaka dan Pengumpulan Data ...................... 3 1.5.2 Membuat Desain dan Rancang Sistem ...................... 4 1.5.3 Implementasi Perangkat Lunak ................................ 5 1.5.4 Deployment dan Pengujian ....................................... 5
1.6 Sistematika Penulisan ............................................................ 5 BAB II LANDASAN TEORI
2.1 Iklan Baris ........................................................................... 7 2.1.1 Jenis Iklan Bars ........................................................ 7
2.2 Algoritma Optimasi ............................................................. 7 2.3 Algoritma Evolusi Diferensial .............................................. 12
2.3.1 Evolusi Diferensial untuk Optimasi .......................... 13 2.3.2 Tahapan dari Evolusi Diferensial .............................. 14
2.4 PHP ................................................................................. 16
BAB III ANALISA DAN PERANCANGAN SISTEM 3.1 Analisa Masalah .................................................................. 18 3.1.1 Analisis Sistem ......................................................... 19 3.1.2 Analisis Alur Proses ................................................. 20 3.1.2.1 Desain Flowchart Perangkat Lunak ............ 20 3.1.2.2 Desain Flowchart Algoritma DE ................. 21 3.1.2.3 Usecase Diagram ....................................... 23 3.1.2.4 Activity Diagram ........................................ 24
viii
3.1.2.5 Sequence Diagram ..................................... 25 3.1.2.6 Class Diagram ............................................ 27 3.2 Perancangan Sistem ............................................................ 27 3.2.1 Perancangan Database .............................................. 27 3.2.1.1 Perancangan CDM ..................................... 27 3.2.1.2 Perancangan PDM ..................................... 28 3.2.2 Perancangan Anatar Muka ........................................ 31 3.2.2.1 Desain Login ............................................... 31 3.2.2.2 Desain Home ............................................. 32 3.2.2.3 Desain Manajemen Iklan............................. 32 3.2.2.4 Desain Manajemen Harga ........................... 33 3.2.2.5 Desain Proses DE ........................................ 34 3.2.2.6 Desain Menu Tambahan ............................ 34
BAB IV IMPLEMENTASI DAN PENGUJIAN 4.1 Spesifikasi Kebutuhan Hardware dan Software .................... 35 4.2 Implementasi Sistem ........................................................... 35
4.2.1 Pembuatan Basis Data .............................................. 35 4.2.2 Pembuatan Fungsi Koneksi Basis Data .................... 40 4.2.3 Pembuatan Fungsi yang Dibutuhkan ......................... 40 4.2.4 Hasil Penerapan Algoritma Evolusi Diferensial ........ 41
4.2.4.1 Inisialisasi ................................................... 41 4.2.4.2 Mutasi......................................................... 42 4.2.4.3 Crossover .................................................... 43 4.2.4.4 Seleksi ........................................................ 44 4.3 Pengujian ............................................................................ 45
4.3.1 Pengujian Sistem ...................................................... 45 4.3.2 Pengujian Perhitungan Algoritma DE ....................... 49
4.3.2.1 Inisialisasi ................................................... 49 4.3.2.2 Mutasi......................................................... 50 4.3.2.3 Crossover .................................................... 51 4.3.2.4 Seleksi ........................................................ 52
4.3.3 Pengujian Hasil ........................................................ 53 4.3.3.1 Pengujian Unit ............................................ 53 4.2.4.2 Pengujian Populasi dan Generasi................. 54
BAB V KESIMPULAN DAN SARAN 5.1 Kesimpulan ......................................................................... 60 5.2 Saran ................................................................................... 61
DAFTAR PUSTAKA
ix
DAFTAR GAMBAR
Halaman Gambar 3.1 Flowchart Perangkat Lunak ................................................... 20 Gambar 3.2 Flowchart Algoritma DE ....................................................... 21 Gambar 3.3 Usecase Diagram ................................................................... 23 Gambar 3.4 Activity Diagram Pengelolaan Iklan Baris .............................. 24 Gambar 3.5 Activity Diagram Optimasi Iklan Baris ................................... 25 Gambar 3.6 Sequence Diagram Pengelolaan Iklan Baris ........................... 26 Gambar 3.7 Sequence Diagram Optimasi Iklan Baris ................................ 26 Gambar 3.8 Class Diagram ....................................................................... 27 Gambar 3.9 CDM Perangkat Lunak ........................................................... 28 Gambar 3.10 PDM Perangkat Lunak ........................................................... 28 Gambar 3.11 Desain Login .......................................................................... 31 Gambar 3.12 Desain Main Menu ................................................................ 32 Gambar 3.13 Desain Manajemen Iklan ........................................................ 33 Gambar 3.14 Desain Manajemen Harga ...................................................... 33 Gambar 3.15 Desain Proses DE ................................................................... 34 Gambar 3.16 Desain Menu Tambahan ......................................................... 34 Gambar 4.1 MySQL Admin ...................................................................... 36 Gambar 4.2 MySQL Generasi ................................................................... 36 Gambar 4.3 MySQL Harga........................................................................ 36 Gambar 4.4 MySQL Iklan ......................................................................... 37 Gambar 4.5 MySQL Jenis ......................................................................... 37 Gambar 4.6 MySQL Klasifikasi ................................................................ 37 Gambar 4.7 MySQL Populasi .................................................................... 38 Gambar 4.8 Script Koneksi Basis Data ...................................................... 40 Gambar 4.9 Fungsi yang Dibutuhkan......................................................... 40 Gambar 4.10 Inisialisasi Target .................................................................. 41 Gambar 4.11 Pembentukan Populasi ........................................................... 42 Gambar 4.12 Proses Mutasi ......................................................................... 43 Gambar 4.13 Proses Crossover .................................................................... 43 Gambar 4.14 Proses Seleksi ........................................................................ 44 Gambar 4.15 Proses Hasil ........................................................................... 44 Gambar 4.16 Menu Utama .......................................................................... 45 Gambar 4.17 Menu Order Iklan ................................................................... 45 Gambar 4.18 Menu Manajemen Iklan ......................................................... 46 Gambar 4.19 Menu Harga ........................................................................... 46 Gambar 4.20 Menu Perhitungan DE ............................................................ 47 Gambar 4.21 Pengujian Data pada Menu Perhitungan DE ........................... 47 Gambar 4.22 Hasil Perhitumgan DE ............................................................ 48 Gambar 4.23 Hasil Perhitungan DE ............................................................. 48 Gambar 4.24 Iklan ....................................................................................... 50 Gambar 4.25 Populasi Generasi yang Terpilih ............................................. 52
x
Gambar 4.26 Hasil Aplikasi ........................................................................ 53 Gambar 4.27 Data Iklan yang diuji .............................................................. 54 Gambar 4.28 Nilai Uji Paremeter Pertama ................................................... 55 Gambar 4.29 Hasil Uji Parameter Pertama .................................................. 55 Gambar 4.30 Nilai Uji Paremeter Kedua ..................................................... 55 Gambar 4.31 Hasil Uji Parameter Kedua ..................................................... 56 Gambar 4.32 Nilai Uji Paremeter Ketiga ..................................................... 56 Gambar 4.33 Hasil Uji Parameter Ketiga ..................................................... 57 Gambar 4.34 Nilai Uji Paremeter Keempat .................................................. 57 Gambar 4.35 Hasil Uji Parameter Keempat ................................................. 58 Gambar 4.36 Nilai Uji Paremeter Kelima .................................................... 58 Gambar 4.37 Hasil Uji Parameter Kelima .................................................... 59
xi
DAFTAR TABEL
Halaman Tabel 3.1 Keterangan Tabel Iklan ............................................................... 27 Tabel 3.2 Keterangan Tabel Harga ............................................................. 28 Tabel 3.3 Keterangan Tabel Klasifikasi ...................................................... 28 Tabel 3.4 Keterangan Tabel Generasi ......................................................... 28 Tabel 3.5 Keterangan Tabel Jenis ............................................................... 29 Tabel 3.6 Keterangan Tabel Admin ............................................................ 29 Tabel 3.7 Keterangan Tabel Populasi ......................................................... 29 Tabel 4.1 Data Kasus Uji Coba................................................................... 36 Tabel 4.2 Inisialisasi Klasifikasi ................................................................. 47 Tabel 4.3 Inisialisasi Jenis Iklan ................................................................ 48 Tabel 4.4 Nilai Target Biaya Operasi.......................................................... 49 Tabel 4.5 Pengujian Unit ............................................................................ 52 Tabel 4.6 Pengujian Generasi dan Populasi ................................................ 57
DAFTAR PUSTAKA
Erik Magnus. 2010. Good Parameters For Differential Evolution. Hvass Laboratories
Fleetwood Kelly. An Introduction to Differential Evolution . K. V.Price, R. M. Storn and J. A. Lampinen, Differential evolution: a partical
approach to global optimization, Spinger, 2005. Karabo Dervis, Okdem Selcuk. 2004. A Simple and Global Optimization
Algorithm forEngineering Problems: Differential Evolution. Erciyes University of Turki.
Komarudin.Manual Penggunaan Algoritma Evolusi Diferensial Unuk
Mengoptimasikan Tata Letak Fasilitas.Universitas Indonesia. Salman Ayed, Hamdan Suha. 2009. Solving Department’s Course-scheduling
Problem using Differential Evolution. College of Engineering Kuwait University.
Saputra Nico, Beatrix. 2006. Penempatan Iklan Baris Dengan AlgoritmaGenitika.
Makalah disajikan dalam seminar Nasional Aplikasi Teknologi Informasi, Universitas Katolik Parahyangan.
Setiawan Teguh, Suwignjo Patdono, dan Santosa Budi. Penggunaan Metode
Differential Evolution untuk Menghitung Costumer Utility yang Optimum di Supermarket X. Institut Sepuluh November Surabaya.
Storn Rainer, Price Kenneth. 1997. Differential Evolution: A Simple and
Effiecient Heuristic for Global Optimizatiton over Continous Spaces. Kluwer Academic Netherlands.
Sunarto Andiek, Santosa Budi, dan Rahman Arief. Pengembangan Model Airline
Rostering System Menggunakan Metode Differential Evolution. Institut Sepuluh November Surabaya.
Suyanto. 2006. Evolutionary Computation-Komputasi Berbasis Evolusi dan
Genetika. Yogyakarta : Graha Ilmu.
Wikipedia. Diferensial Evolution. (Februari, 2012)