2012200979MTIFBab2001

BAB 2

LANDASAN TEORI

2.1 Teori Graf

Adiwijaya (P47)

menyatakan bahwa teori graf

ditulis pertama kali

dalam makalah oleh Leonard Euler

matematikawan asal Swiss pada tahun

1736, yang digunakan untuk menyelesaikan masalah jembatan Königsberg

yang tertera pada gambar 2.1. Masalah tersebut adalah apakah bisa

melewati setiap jembatan tepat satu kali dan kembali lagi ke tempat asal

mula?.

Gambar 2. 1 Masalah Jembatan Königsberg

Gambar 2.2 adalah sketsa yang merepresentasikan ilustrasi jembatan

Königsberg yang pada gambar 2.1

Gambar 2. 2 Representasi Graf dari Masalah Jembatan Königsberg

Jawaban atas masalah tersebut adalah tidak mungkin. Karena untuk

bisa melalui setiap jembatan tepat satu kali dan kembali lagi ke tempat asal

mula maka jumlah jembatan harus genap.

2.1.1

Definisi Graf

Adiwijaya (P48)

menjelaskan bahwa graf

merupakan struktur diskrit

yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul dan

himpunan sisi

yang menghubungkan simpul-simpul tersebut. Notasi

sebuah graf adalah G = (V, E), di mana :

V merupakan himpunan tak kosong dari simpul-simpul misalkan V

= { v1 , v2 , ... , vn }

E merupakan himpunan sisi – sisi yang menghubungkan sepasang

simpul, misalkan E = {e1 , e2 , ... , en }

Contoh :

Graf dari masalah jembatan Königsberg dapat disajikan pada gambar 2.3 :

Gambar 2. 3 Graf dari Masalah Jembatan Königsberg

2.1.2

Macam – macam Graf

Adiwijaya (P53) menjelaskan macam – macam graf yaitu :

Graf

tidak berarah : Graf dengan sisi –

sisi penghubung simpulnya

tidak memiliki arah. Contoh seperti pada gambar 2.4.

Gambar 2. 4 Graf Tidak Berarah

Graf berarah: Graf dengan sisi – sisi penghubung simpulnya memiliki

arah. Contoh seperti pada gambar 2.5.

Gambar 2. 5 Graf Berarah

Graf berbobot : Graf yang sisi –

sisi penghubung simpulnya

mempunyai bobot. . Contoh seperti pada gambar 2.6.

Gambar 2. 6 Graf Berbobot

Adiwijaya (P71) menjelaskan bahwa graf bisa diaplikasikan pada suatu

permasalahan, salah satunya adalah travelling salesman problem.

2.1.3

Lintasan dan Sirkuit Hamilton

Lintasan hamilton suatu graf merupakan lintasan yang melalui setiap

simpul dalam graf tersebut tepat satu kali.

Jika lintasan tersebut kembali

kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit) maka

lintasan ini dinamakan sirkuit hamilton.

Dengan demikian, sirkuit hamilton merupakan sirkuit yang melewati

masing-masing sisi tepat satu kali. Graf

yang memuat sirkuit hamilton

dinamakan graf

hamilton, sedangkan graf

yang memuat lintasan hamilton

dinamakan graf semi hamilton.

Contoh :

Perhatikan tiga graf pada gambar 2. 7 :

Gambar 2. 7 Graf

Graf G1 merupakan graf semi hamilton, lintasan hamilton-nya adalah

s – r – p – q – r.

Sedangkan graf G2 merupakan graf hamilton, sirkuit hamiltonya adalah

t – p – r – q – p – s – q – t .

Sementara itu pada graf

G3 tidak terdapat lintasan maupun sirkuit

hamilton.

2.2 Optimasi

2.2.1

Definisi Optimasi

Optimasi merupakan suatu tindakan pengambilan keputusan terbaik

pada suatu masalah, keputusan tersebut berupa memaksimalkan faktor

yang diinginkan atau meminimumkan faktor yang tidak diinginkan

menurut batasan yang diberikan. Optimasi juga dijadikan solusi untuk

menentukan keputusan menyelesaikan suatu masalah. (Bidisha G, 2011).

2.2.2

Permasalahan Optimasi

Beberapa permasalahan dalam optimisasi adalah sebagai berikut:

Shortest Path Problem

: Suatu permasalahan untuk mencari

rute

terpendek dari suatu tempat ke tempat yang lain.

Traveling Salesman Problem

: Suatu permasalahan untuk mencari

rute perjalanan agar semua tempat dapat dilewati dengan jarak yang

optimal.

Assignment Problems

: Suatu permasalahan untuk mencari solusi

biaya pengeluaran agar seminimum mungkin dan memberikan tugas

pekerjaan kepada mesin-mesin yang tersedia.

Scheduling Problems

: Suatu permasalahan untuk mencari

jumlah

pekerja yang melakukan suatu proses kegiatan,

agar pengeluaran

biaya pekerja bisa diminimalkan dan hasil produksi tetap maksimal.

Routing Problems

: Mengatur routing

jaringan kabel agar biaya

pemasangan kabel tidak besar. (Vinnet C., Parveen K. Y., & Pawan

K. D., 2012:15)

2.3 Travelling Salesman Problem

Menurut Oloruntoyin S. T., Ojo J., Amao T., Salawudeen D., &

Oloruntoyin K. S. (2013: 1) menjelaskan bahwa travelling Salesman

Problem merupakan suatu masalah mencari rute terpendek dari satu tempat

melewati semua tempat dan kembali ke tempat asal. Penyelesaian masalah

ini menghasilkan

banyak rute

dengan jarak yang berbeda. Pencarian rute

terdekat dapat digunakan

dalam banyak hal, karena itu solusi untuk

masalah ini masih tetap dicari sampai sekarang. Banyak

metode yang ada

untuk menyelesaikan masalah ini.

2.4 Algoritma Semut

Algoritma semut diadaptasi dari tingkah laku semut mencari makanan

dari sarangnya. Dalam perjalanan mencari makanan, semut memberikan

feromon disetiap jejaknya. Tujuan pemberian feromon agar semut tersebut

dapat kembali saat menemukan dan membawa makanan ke sarangnya.

Feromon juga berfungsi sebagai komunikasi antar semut, sehingga semut

lain mengikuti jejaknya untuk membawa makanan. Dengan adanya

feromon, semut dapat menemukan rute perjalanan yang pendek dari sarang

ke sumber makanan (Thomas Stützle & Holger H. Hoos, 2000: 16).

2.5 Max – Min Ant System

Mann, A., Talwar, R., Bhushan, B., & Gupta, R. (2012:2)

memberikan penjelasan bahwa Max-Min

Ant System

yang dikembangkan

oleh Hoos pada tahun 1996 merupakan perluasan

dari algoritma Ant

System. Solusi dalam Max-Min

Ant System

dibangun dengan cara yang

persis sama seperti dalam Ant System.

Modifikasi utama dalam

Max-Min

Ant System

adalah untuk

mengeksploitasi solusi terbaik yang ditemukan, penambahkan feromon

diperbolehkan pada sisi –

sisi yang merupakan rute

terbaik. Lalu untuk

menghindari stagnasi semua semut melalui jalur yang sama, maka feromon

diberikan batasan dengan

interval [

]. Feromon diinisialisasi ke

batas atas nilai feromon, untuk eksplorasi lebih tinggi pada awal algoritma.

Feromon diinisialisasi ulang jika tidak menemukan rute terbaik.

Bambang Y., Agus S. A., & Siswanto B. W. (2009) yang menjelaskan

bahwa “dalam algoritma semut, diperlukan beberapa variabel dan langkah

langkah untuk menentukan rute terpendek”. Berikut adalah langkah -

langkah dalam Max - Min Ant System:

Langkah 1 : Inisialisasi harga parameter – parameter algoritma

Parameter – parameter yang diinisialisasi adalah :

Intensitas jejak semut antar titik dan perubahannya.

………………………………………………..…..….. (1)

Di mana

adalah panjang rute yang didapat dari metode nearest

neighbour heuristic

Banyaknya titik

dan juga koordinat

atau jarak antar titik

(

)

Titik berangkat (awal) dan titik tujuan

Tetapan pengendali intensitas jejak semut

Tetapan pengendali visibilitas

f) Visibilitas antar titik.

…………………….……. (2)

Banyaknya semut

Tetapan penguapan feromon (

dan

)

i) Jumlah iterasi maksimum (NCmax)

Langkah 2 : Penentuan kota tujuan

Semut diletakkan di masing masing kota sebagai tempat awal

sebelum memulai perjalanan. Semut akan memilih kota selanjutnya

berdasarkan persamaan probabilitas kota

yang bisa dilihat pada

persamaan (3) yaitu:

………………………. (3)

Di mana

yang didapat pada persamaan (2). Jika hanya diketahui

koordinatnya saja. Maka

bisa didapat dengan persamaan (4)

yaitu:

……………………………….. (4)

Dengan i sebagai indeks kota awal dan j sebagai indeks kota tujuan.

Langkah 3 : Menghitung panjang jalur setiap semut

Perhitungan panjang jalur tertutup setiap semut dilakukan

setiap pergantian siklus dengan persamaan (5) yaitu:

…………….. (5)

mana

adalah jarak

dari kota

s sampai

kota

s+1 dalam tabu list pada

semut k dan

adalah

jarak dari kota n dan kota pertama dalam tabu list.

Kemudian perhitungan dilanjutkan dengan mencari jalur

terpendek. Setelah

dihitung, maka akan didapat jalur terpendek

dari setiap siklus yang dinyatakan dengan

Langkah 4 : Perhitungan intensitas jejak kaki semut

Untuk siklus selanjutnya, semut yang akan melewati lintasan

tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki

semut antar kota untuk siklus selanjutnya dapat dihitung dengan

persamaan (6) yaitu:

…………….………………………….. (6)

Di mana

……………………………………….….. (7)

Jika semut menemukan jalur terbaik di awal atau pada iterasi siklus.

Harga intensitas jejak kaki semut dibatasi dengan batas atas

nilai feromon

dan batas bawah feromon

yang dihitung

dari dengan persamaan (8) yaitu:

dan

………………………. (8)

Di mana

merupakan rata-rata dari jumlah dari pilihan

yang berbeda pada semut untuk menemukan jalur terbaiknya.

Jika

, maka

Jika

, maka

Untuk mendekati optimal dalam Max-Min Ant System

maka

jumlah semut sama dengan jumlah kota

2.6 Metode Nearest Neigbour Heuristic

Nearest Neighbour Heuristic

merupakan solusi jalur

perjalanan

optimal secara sistematis dengan mencari kota

terdekat yang

belum

dikunjungi dari sebuah kota. Menurut Oloruntoyin S. T., Ojo J., Amao T.,

Salawudeen D., & Oloruntoyin K. S. (2013:1) untuk mengatasi masalah

travelling salesman problem dengan menggunakan nearest neighbour

heuristic dapat menggunakan langkah – langkah berikut ini.

Langkah 1

: Pilih simpul awal.

Langkah 2

: Lihat semua sisi yang keluar dari simpul awal, pilih simpul

berikutnya dengan nilai sisi yang terkecil.

Langkah 3

: Ulangi proses ini sampai semua simpul dikunjungi.

Langkah 4

: Periksa apakah semua simpul telah dikunjungi, jika sudah

maka kembali lagi ke simpul awal.

Langkah 5

: Hitung jarak rute perjalanan yang didapat

2.7 Unified Modelling Language (UML)

UML menggambarkan kebutuhan dan alur proses sistem. UML terbagi

atas beberapa jenis diagram, yaitu use case, activity

diagram, sequence

diagram,dan class diagram.

2.7.1

Use Case

Menurut Martin Fowler (2003: P99) menyatakan bahwa use case

adalah teknik untuk merekam persyaratan fungsional sebuah sistem. Use

case merupakan sebuah narasi tentang bagaimana sistem tersebut

digunakan.

Menurut Albertus Bayu Aji Priyono untuk lebih memperjelas use case,

lihat gambaran suatu peristiwa untuk sebuah klinik kesehatan di bawah ini

Gambar 2. 8 Contoh use case

Pada gambar 2.8

menjelaskan bahwa “Pasien menghubungi klinik

untuk membuat janji (appointment) dalam pemeriksaan tahunan.

Receptionist

mendapatkan waktu yang luang pada buku jadwal dan

memasukkan janji tersebut ke dalam waktu luang itu.”

2.7.2

Activity Diagram

Menurut Martin Fowler (2003: P117) menyatakan bahwa activity

diagram

adalah teknik untuk menggambarkan logika prosedural, proses

bisnis, dan jalur kerja. Sebuah activity diagram

secara keseluruhan

menunjukkan aliran kontrol.

2.7.3

Sequence Diagram

Menurut Martin Fowler (2003: P53) menyatakan bahwa sequence

diagram menggambarkan interaksi diagram yang menunjukkan bagaimana

kelompok-kelompok objek saling berkolaborasi dalam beberapa aksi.

Menurut Albertus Bayu Aji Priyono

contoh dari sequence diagram

untuk pembuatan hotel reservation bisa dilihat di bawah ini. Objek yang

mengawali urutan pesan adalah ‘aReservation Window’.

Gambar 2. 9 Contoh Sequence Diagram

Pada gambar 2.9 menjelaskan bahwa ‘Reservation window’ mengirim

pesan makeReservation() ke ‘HotelChain’. Kemudian ‘HotelChain’

mengirim pesan yang sama ke ‘Hotel’. Bila ‘Hotel’ punya kamar kosong,

maka dibuat ‘Reservation’ dan ‘Confirmation’.

2.7.4

Class Diagram

Menurut Martin Fowler (2003: P35) class diagram

mendeskripsikan

berbagai jenis objek dalam sistem dan macam -

macam hubungan statis

yang terdapat diantara mereka.

Class diagram

juga menunjukkan

properties

dan operasi dari kelas dan kendala yang berlaku pada objek

yang terhubung.

2.8 Personal Home Page (PHP)

Menurut Loka Dwiartara (2010: P3) menyatakan bahwa

PHP

ditemukan pertama kali

oleh seorang Software Developer bernama

Rasmus Lerdrof pada 1995. Awalnya Rasmus ingin mengetahui jumlah

pengunjung yang membaca resume

dalam website. Lalu dikembangkan

script

yang baru

dapat melakukan dua pekerjaan, yakni merekam

informasi pengunjung, dan menampilkan jumlah pengunjung dari suatu

website. Kemudian banyak orang di milis mendiskusikan script

buatan

Rasmus Lerdrof, hingga akhirnya rasmus mulai membuat

sebuah

tool/script, bernama Personal Home Page (PHP).

Keunggulan PHP :

Gratis

Cross platform

: Dapat di gunakan di berbagai sistem operasi,

mulai dari linux, windows, mac os dan sistem operasi yang lain.

Mendukung banyak database : PHP

telah mendukung banyak

database seperti MySQL, ODBC, Ovrimos, dan lain - lain.

On The Fly

: PHP

sudah mendukung on the fly, artinya dengan

PHP

anda dapat membuat dokumen seperti text, Word, Excel,

PDF, dan lain - lain.

2.9 Hyper Text Markup Language 5 (HTML5)

Menurut Yudha Yudhanto (2012) bahwa “HTML5 merupakan sebuah

bahasa markah untuk menstrukturkan dan menampilkan isi dari World

Wide Web, sebuah teknologi inti dari Internet. HTML5 adalah revisi kelima

dari HTML. Di

mana tujuan utama pengembangan HTML5 adalah untuk

memperbaiki teknologi HTML

agar mendukung teknologi multimedia

terbaru, mudah dibaca oleh manusia dan juga mudah dimengerti oleh

mesin”.

Berikut tujuan dibuatnya HTML5 :

Fitur baru harus didasarkan pada HTML, CSS, DOM, dan JavaScript.

Mengurangi ketergantugan untuk plugin eksternal (Seperti Flash).

Penanganan kesalahan yang lebih baik.

Lebih markup untuk menggantikan scripting.

HTML5 merupakan perangkat mandiri.

Proses pembangunan dapat terlihat untuk umum.

Fitur baru dalam HTML5 :

Unsur kanvas untuk menggambar.

Video dan elemen audio untuk media pemutaran.

Dukungan yang lebih baik untuk penyimpanan secara offline.

Elemen konten yang lebih spesifik, seperti artikel, footer, header, nav,

section.

Bentuk kontrol tampilan seperti kalender, tanggal, waktu, email, url,

search.

2.10

Model Waterfall

Pressman (2010: P39) menyatakan bahwa model waterfall, terkadang

disebut siklus model

klasik, dengan

pendekatan yang sistematis dan

sekuensial untuk pengembangan perangkat lunak.

Gambar 2.10 adalah fase model menurut Pressman (2010: P39)

Gambar 2. 10 Model waterfall

Communication

merupakan proses tahap awal untuk analisis

terhadap kebutuhan perangkat lunak, dan tahap untuk mengadakan

pertemuan dengan konsumen

untuk mencari kebutuhan dari

keseluruhan sistem, serta pengumpulan data tambahan dari jurnal,

artikel, dan internet.

Planning

Setelah proses communication selesai maka dilanjutkan dengan

proses planning

yang akan menghasilkan dokumen user requirement

atau bisa dikatakan sebagai data

yang berhubungan dengan keinginan

user dalam pembuatan perangkat lunak, termasuk rencana yang akan

dilakukan.

Modeling

Proses modeling ini akan menerjemahkan syarat kebutuhan ke

sebuah perancangan perangkat lunak

yang dapat diperkirakan sebelum

dibuat coding. Proses ini berfokus pada rancangan struktur data,

arsitektur perangkat lunak, representasi interface, dan detail

(algoritma) procedural. Tahapan ini akan menghasilkan dokumen yang

disebut software requirement.

Construction

Construction merupakan proses membuat kode. Pengkodean

merupakan penerjemahan desain dalam bahasa yang bisa dikenali oleh

komputer. Programmer

akan menerjemahkan transaksi yang diminta

oleh user. Tahapan inilah yang merupakan tahapan secara nyata dalam

mengerjakan suatu perangkat lunak, artinya penggunaan komputer

akan dimaksimalkan dalam tahapan ini. Setelah pengkodean selesai

maka akan dilakukan testing terhadap sistem yang telah dibuat dengan

tujuan menemukan kesalahan-kesalahan terhadap sistem tersebut untuk

kemudian bisa diperbaiki.

Deployment

Tahapan ini bisa dikatakan final dalam pembuatan sebuah

perangkat lunak

atau sistem.

Setelah melakukan analisis, desain dan

pengkodean maka sistem yang sudah jadi akan

digunakan user.

Kemudian perangkat lunak

yang telah dibuat harus dilakukan

pemeliharaan secara berkala