implementasi algoritma evolusi diferensial untuk...

16
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

Upload: vankiet

Post on 05-Mar-2019

215 views

Category:

Documents


0 download

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)