BAB 2

LANDASAN TEORI

2.1 Optimalisasi

Optimalisasi adalah sarana untuk mengekspresikan, dalam model matematika,

hasil dari penyelesaian suatu masalah dengan cara terbaik (Sergio et. al., 2008, p403).

Hal ini dapat diartikan sebagai menjalankan bisnis untuk memaksimalkan keuntungan

dan efisiensi serta meminimalkan kerugian, biaya atau resiko. Keinginan untuk

memecahkan masalah dalam model optimalisasi secara umum dapat digunakan pada

hampir semua bidang aplikasi.

Model optimalisasi telah digunakan selama berabad-abad. Pada masa sekarang

ini menjadi sangat mencolok jika ingin mengembangkan bisnis menjadi sangat besar dan

rumit. Para insinyur pun menjadi makin ambisius. Dalam banyak keadaan, tidak lagi

mungkin untuk membuat keputusan tanpa bantuan model optimalisasi. Sebagai contoh,

dalam sebuah kerjasama multinasional yang besar, presentase kecil suatu perkembangan

dalam proses operasi mungkin meningkatkan penambahan keuntungan hingga jutaan

dollar.

Untuk model yang besar, dengan segala kerumitan yang ada, akan sedikit

bermasalah jika tidak dapat diselesaikan. Beberapa dekade terakhir telah menjadi saksi

pengembangan yang sangat mengejutkan dalam hardware dan software komputer, dan

kemajuan ini telah membuat model optimalisasi menjadi alat yang umum dipakai dalam

bisnis, ilmu pengetahuan, dan perusahaan.

8

Menurut Crama (2001, p4), persoalan optimalisasi adalah suatu persoalan untuk

membuat suatu nilai fungsi beberapa variabel menjadi maksimum atau minimum dengan

memperhatikan pembatasan-pembatasan yang ada. Biasanya pembatasan-pembatasan

tersebut meliputi tenaga kerja (men), uang (money) dan material yang merupakan input

serta waktu dan ruang.

Sedangkan menurut National Institude of Standard and Technology (NIST),

masalah optimalisasi adalah masalah komputasi dimana tujuannya adalah menemukan

yang terbaik dari semua solusi yang mungkin.

Saat ini, ada banyak masalah optimalisasi dimana tidak terdapat metode yang

pasti atau metode komputasi deterministik terlalu rumit untuk diterapkan. Simulated

Annealing dapat menjadi jawaban untuk kasus-kasus ini. Hal ini tidak rumit dalam arti

bahwa ia tidak dibodohi dengan minima yang salah, dan sangat mudah dilaksanakan.

Lebih jauh lagi, karena tidak membutuhkan model matematis, ini dapat digunakan untuk

memecahkan berbagai masalah.

Sayangnya, pemetaan masalah real pada domain Simulated Annealing sangatlah

sulit dan membutuhkan algoritma yang kompleks. Selain itu, ada beberapa faktor lain

yang menentukan kegagalan (the success of failure) algoritma ini.

Beberapa pertimbangan yang praktis untuk mengimplementasikan secara tepat

Simulated Annealing akan ditinjau dan dianalisis. Disini juga terdapat cara untuk

menetapkan solusi, bagaimana untuk menentukan jadwal pendinginan yang tepat, dan

cara yang paling penting, bagaimana menerapkan algortima dengan baik. Beberapa

9

jadwal pendinginan akan dicakup, termasuk eksponensial, linear dan perputaran

temperatur.

Selain itu, dampak dari pembangkit nomor acak akan diperiksa, bagaimana

mereka mempengaruhi kecepatan dan kualitas dari algoritma. Pada dasarnya, ilmu ini

difokuskan untuk mereka yang ingin memecahkan masalah real dengan menggunakan

Simulated Annealing, seperti kecerdasan buatan (artificial intelligence), teknik

(engineering), atau penelitian (research).

Sebuah contoh ilustratif diselesaikan menggunakan Simulated Annealing dan

diimplementasikan ke dalam bahasa pemrograman yang populer menggunakan

pendekatan berorientasi objek (Object Oriented Programming).

Secara garis besar, optimalisasi adalah Tindakan untuk memberikan hasil yang

paling baik, apakah itu hasil maksimal ataupun hasil minimum, untuk membuat sistem

yang seefektif mungkin untuk menemukan yang terbaik dari semua solusi yang

mungkin.

2.2 Metode Simulated Annealing

2.2.1 Proses Annealing dan Proses Simulated Annealing

Annealing adalah suatu pendinginan logam secara lambat setelah logam tersebut

dipanaskan pada temperatur yang sangat tinggi. Proses pendinginan logam yang

dipanaskan pada temperatur tinggi tersebut berlangsung secara perlahan-lahan. Ketika

penurunan temperatur berhenti, logam telah berada pada kondisi dengan energi yang

sangat rendah.

10

Dalam proses annealing ada beberapa tahap yang terjadi dalam pendinginan

logam.

Pada temperatur tinggi, atom-atom yang berada dalam logam yang dipanaskan

tersebut berorientasi acak dan mempunyai energi yang sangat tinggi.

Ketika temperatur diturunkan, atom-atom akan cenderung untuk mengikuti arah

atom tetangganya. Namun daerah yang berbeda akan memiliki arah yang berbeda

pula.

Jika temperatur sudah sangat rendah, maka terjadi proses pembekuan sehingga

atom-atom tersebut akan berikatan erat, memiliki energi yang sangat rendah dan

memiliki arah yang satu dengan yang lain.

Dengan Simulated Annealing ada beberapa proses yang sering terjadi dalam

pencapaian proses pembekuan sehingga atom-atom dapat memperoleh energi yang

rendah, yakni.

Melakukan gangguan secara acak terhadap orientasi atom-atom dan menghitung

perubahan energi yang dihasilkan.

Jika energi yang dihasilkan berkurang maka sistem akan bergerak menuju ke

status yang baru.

Jika energi yang dihasilkan bertambah maka status baru ini dapat diterima

dengan mengikuti peraturan hukum termodinamika. Pada temperatur T,

probabilitas dari selisih dari energi yang dihasilkan status baru dengan status

lama (Y) memenuhi U (bilangan acak) < e(-Y/T)

11

2.2.2 Simulated Annealing

Simulated Annealing adalah suatu metode optimasi yang berdasarkan pada

proses pendinginan yang digunakan dalam Metalurgi. Secara umum, pada saat suatu zat

melewati proses pendinginan, pertama-tama akan dipanaskan dulu sampai mencapai titik

lebur untuk pencairannya, kemudian didinginkan secara perlahan-lahan dengan cara

mengontrol proses pendinginannya hingga zat tersebut padat kembali. Sifat-sifat terakhir

dari zat ini sangat bergantung pada jadwal pendinginan yang diterapkan, jika suhu

pendinginan diturunkan secara cepat maka zat yang dihasilkan akan dengan mudah

rusak karena struktur yang tidak sempurna, sebaliknya jika suhu pendinginan diturunkan

secara perlahan maka struktur yang dihasilkan tersusun dengan baik dan kuat.

Ketika menyelesaikan masalah optimasi menggunakan Simulated Annealing,

struktur dari sebuah zat akan mewakili penyusunan solusi dari sebuah masalah, dan suhu

digunakan untuk menentukan bagaimana dan kapan solusi baru dapat diperbaharui dan

diterima. Algoritma ini pada dasarnya adalah proses tiga langkah, yakni.

1. Memperbaharui solusi.

2. Mengevaluasi kualitas dari solusi, dan

3. Menerima solusi jika solusi tersebut lebih baik daripada yang sebelumnya.

Untuk mengimplementasikan Simulated Annealing, biasanya diperlukan untuk

menghasilkan sejumlah angka acak. Sayangnya, pembangkit acak dalam bahasa

pemrograman berkualitas rendah dan tidak berguna untuk Simulated Annealing. Urutan

acak ini memiliki panjang yang terbatas dan mungkin memiliki korelasi.

12

Memilih pembangkit acak yang sesuai memerlukan pengetahuan khusus dari

masalah, pada dasarnya adalah penting untuk menetapkan jumlah angka acak yang

diperlukan dan kecepatan dari pembangkit tersebut (beberapa masalah yang mungkin

memerlukan kecepatan dan kualitas. (Press et al., 2002) memberikan tinjauan komprehensif

tentang subjek dan termasuk kode aktual untuk menerapkan kualitas tinggi nomor acak

generator.

Simulated Annealing adalah proses dua langkah, yaitu mengubah kemudian

mengevaluasi kualitas solusi. Biasanya, algoritma ini menggunakan solusi yang kurang

optimal untuk membuat keputusan tentang penerimaan solusi baru. Selanjutnya,

beberapa notasi akan diberikan untuk membuat presentasi yang jelas. Misalkan Problem

Solution M variabel sebagai

X = {x1, x2, x3, , xM}

(1)

dimana {x1, x2, x3, , xM} dapat dicari dengan Simulated Annealing. Representasi ini

mungkin berguna untuk sebagian besar algoritma optimasi. Namun, Simulated

Annealing adalah algoritma yang tergantung pada temperatur dan proses temperatur

harus diberikan pada persamaan pertama. Misalkan T sebagai proses temperatur.

T = T1, T2, T3, , TN

(2)

13

dimana T1 adalah temperatur awal dan TN adalah temperatur akhir, N adalah jumlah

temperatur, nilai T akan diberikan pada saat jadwal pendinginan berdasarkan masalah

yang ada. Harap diperhatikan bahwa T adalah variabel diskrit karena biasanya

temperatur tidak meningkat terus-menerus.

Untuk meningkatkan kinerja Simulated Annealing, disetiap temperatur akan

diberikan sejumlah iterasi sebelum penurunan temperatur. Misalkan K adalah jumlah

iterasi yang dilakukan pada setiap temperatur, maka Persamaan (1) dapat ditulis sebagai

Xi = {x1,i, x2,i, x3,i, , xM,i}, i = 1, 2, 3,

(3)

dimana i adalah jumlah perubahan yang dilakukan terhadap sulosi, dan nilai x1,i adalah

nilai x setelah dilakukan perubahan sebagai i-kali. Dengan demikian, pada akhir

temperatur T1, jumlah perubahan yang dilakukan pada solusi adalah K, dan XK mewakili

solusi pada akhir temperatur ini. Biasanya, setiap solusi Xi harus memiliki error yang

berhubungan dengan K, misalkan

E1, E2, E3,

(4)

akan menjadi error pada X1, X2, X3, secara berturut-turut. Umumnya, suatu teknik

untuk memperkirakan kesalahan solusi harus ditetapkan, tapi biasanya teknik ini

bergantung pada masalah dan diperlukan pengetahuan yang penuh tentang masalah.

14

Tidak ada peraturan yang menentukan atau membatasi implementasi Simulated

Annealing. Namun ada beberapa kriteria spesifik tentang bagaimana menerima sebuah

solusi pada saat solusi ini telah diubah. Salah satu kriteria yang jelas adalah menerima

solusi setiap kali ia memiliki sedikit kesalahan daripada solusi sebelumnya. Algoritma

metropolis ditunjukkan pada Persamaan (5), mengikuti kriteria yang dibahas

sebelumnya dan biasanya digunakan dalam Simulated Annealing untuk melakukan

perhitungan probabilitas penerimaan untuk solusi yang telah diubah.

Pa = e

K ET

1

E E

(5)

dimana E adalah perbedaan antara error solusi setelah diubah dan error solusi sebelum

diubah. T adalah temperatur sekarang dan K adalah konstanta yang sesuai.

Berdasarkan Persamaan (5), dapat dilihat bahwa bila E bernilai negatif

solusinya selalu diterima. Namun, algoritma dapat menerima solusi baru bahkan jika

solusi tidak memiliki error yang lebih sedikit daripada solusi sebelumnya (E positif),

dan probabilitas untuk melakukan hal ini menurun ketika temperatur diturunkan atau

pada saat E meningkat. Akibatnya, pada temperatur tinggi mungkin algoritma akan

menerima solusi yang buruk. Ketika temperatur menurun, algoritma lebih selektif dan

menerima solusi hanya ketika E bernilai kecil. Ini adalah teori dibalik Simulated

Annealing dan harus dipahami secara jelas untuk mengimplementasikan algoritmanya.

15

Konstanta K merupakan peran penting pada Simulated Annealing untuk optimasi

global. Estimasi untuk nilai E dapat dihitung dari

E E

(6)

dimana dapat diestimasikan sebagai.

E 1

Q 1 EQ

1

Q Q 1 EQ

(7)

adalah variansi sampel E ketika solusi X0 telah diubah sebanyak Q-kali. Dalam praktek

nya, Persamaan (7) adalah perhitungan yang sangat baik dari nilai awal E selama Q

setidaknya 1000 atau lebih. Hal ini penting diperhatikan bahwa nilai yang tepat untuk

E tidak diperlukan karena ini hanya digunakan untuk mendapatkan perkiraan kasar K.

ini menyatakan bahwa nilai yang besar untuk Q tidak diperlukan.

Setelah perkiraan error untuk E dari solusi telah ditemukan, menemukan

perkiraan untuk K adalah dengan menggunakan langsung Persamaan (5). Namun nilai

awal untuk probabilitas penerimaan perlu didefinisikan. Jelas bahwa nilai awal untuk

penerimaan tidak boleh mendekati satu, dan tidak harus mendekati nol. Nilai antara 0,7

sampai 0,9 dianjurkan. Probabilitas penerimaan yang lebih besar dari 0,9 bukan tujuan

yang praktis karena algoritma akan menerima terlalu banyak solusi yang buruk. Disisi

lain, nilai yang kurang dari 0,7 akan membuat algoritma kehilangan salah satu

16

keuntungan dari Simulated Annealing. Secara umum, nilai awal untuk penerimaan

adalah 0,8. Dengan demikian perkiraan nilai K dapat diekspresikan sebagai

KT ln 0,8

E

(8)

dimana perkiraan untuk deviasi standar dari error solusi dapat dihitung dengan

menggunakan Persamaaan (7). Kinerja dari algoritma ini meningkat secara dramatis

ketika Persamaan (8) digunakan karena perubahan yang tidak diperlukan tidak akan

dihitung.

2.2.3 Istliah-istilah Dalam Simulated Annealing

Penerapan Simulated Annealing dalam permasalahan optimalisasi menggunakan

beberapa istilah sebagai berrikut.

Simulasi Termodinamika

Yaitu permasalahan optimisasi yang hendak dilakukan dengan menggunakan

algoritma Simulated Annealing.

Status Sistem

Yaitu solusi feasible yang terpilih karena adanya perubahan status

Energi

Yaitu biaya atau tujuan dari pencarian solusi permasalahan optimisasi misalnya

makespan, keterlambatan

17

Perubahan status

Yaitu pergerakan yang menggunakan solusi swap dan insertion.

Temperatur

Yaitu parameter yang digunakan sebagai kontrol dalam permasalahan

optimalisasi.

Status pembekuan

Yaitu solusi final dimana solusi sudah optimal atau mendekati optimal.

2.3 Dasar Perancangan Software

Menurut Pressman (2002, p10) perangkat lunak adalah

1. Perintah (program komputer) yang bila dieksekusi akan memberikan fungsi dan

unjuk kerja seperti yang diinginkan.

2. Struktur data yang memungkinkan program memanipulasi informasi secara

proporsional, dan

3. Dokumen yang menggambarkan operasi dan kegunaan program.

Model rekayasa piranti lunak yang digunakan adalah yang seringkali disebut

sebagai prototype model. Model ini memberikan pendekatan-pendekatan yang sistematis

dan berurutan (sequential) dalam pengembangan suatu software. Tahapan-tahapan yang

terdapat dalam prototype model adalah sebagai berikut.

18

Gambar 2.1 Prototype Model

Proses prototype model seperti yang telah digambarkan diatas akan dijelaskan berikut

ini.

Pengumpulan kebutuhan

Developer dan client bertemu dan menentukan tujuan umum, kebutuhan yang

diketahui dan gambaran bagian-bagian yang akan dibutuhkan berikutnya. Detail

kebutuhan mungkin tidak dibicarakan pada awal pengumpulan kebutuhan.

Perancangan

Perancangan dilakukan cepat dan rancangan memiliki semua aspek software

yang diketahui, dan rancangan ini menjadi dasar pembuatan prototype.

Evaluasi prototype

Client mengevaluasi prototype yang dibuat dan digunakan untuk memperjelas

kebutuhan software.

Listen to client

build/revise program

Listen to clientstart

19

2.4 State Transition Diagram

State Transition Diagram (STD) merupakan sebuah modelling tool yang

digunakan untuk menggambarkan suatu sistem yang memiliki ketergantungan terhadap

waktu. STD merupakan suatu kumpulan keadaan atau atribut yang mencirikan suatu

keadaan pada waktu tertentu.

Komponen-komponen utama STD adalah.

1. State, disimbolkan dengan

State merupakan suatu reaksi / respon yang dilakukan oleh sistem ketika

suatu tindakan dilakukan. Ada dua jenis state, yaitu state awal dan state

akhir. State akhir dapat berupa beberapa state, sedangkan state awal hanyalah

satu state.

2. Arrow, disimbolkan dengan

Arrow sering disebut juga dengan transisi state yang diberi label dengan

ekspresi aturan. Label tersebut menunjukkan kejadian yang menyebabkan

transisi tersebut terjadi.

3. Condition and Action, disimbolkan dengan simbol sebagai berikut.

contidtion action

20

Condition adalah suatu event pada lingkungan eksternal yang dapat dideteksi

oleh sistem, sedangkan action adalah tindakan yang dilakukan oleh sistem

bila terjadi perubahan state, atau merupakan reaksi terhadap kondisi yang

terpenuhi. Action akan menghasilkan suatu output.

2.5 Interaksi Manusia Komputer

Menurut Shneiderman (2005, p4), interaksi manusia dan komputer merupakan

disiplin ilmu yang berhubungan dengan perancangan, evaluasi, dan implementasi sistem

komputer interaktif untuk digunakan oleh manusia, serta studi fenomena-fenomena

besar yang berhubungan dengannya.

Pada interaksi manusia dan komputer ditekankan pada pembuatan antarmuka

pemakai (user interface), dimana user interface yang dibuat diusahakan sedemikian rupa

sehingga seorang user dapat dengan baik dan nyaman menggunakan aplikasi perangkat

lunak yang dibuat.

Antarmuka pemakai (user interface) adalah bagian sistem komputer yang

memungkinkan manusia berinteraksi dengan komputer. Tujuan user interface adalah

agar sistem komputer dapat digunakan oleh user. istilah tersebut digunakan untuk

menunjuk kepada kemampuan yang dimiliki oleh piranti lunak atau program aplikasi

yang mudah dioperasikan dan dapat membantu menyelesaikan suatu persoalan dengan

hasil yang sesuai dengan keinginan pengguna, sehingga pengguna merasa betah untuk

mengoperasikan program tersebut.

21

Pada tahap pembuatan program, ada beberapa aturan yang harus dipenuhi agar

user merasa betah untuk mengoperasikan program tersebut. Aturan-aturan tercantum

dalam sebuah hukum yang bernama Delapan Aturan Emas (Eight Golden Rules).

Penjelasan tentang aturan-aturan emas ini akan dibahas pada subbab berikutnya.

2.5.1 Program Interaktif

Interaktif maksudnya adalah memungkinkan user untuk mempengaruhi dan

bereaksi terhadapnya. Suatu program yang interaktif dan baik harus bersifat user

friendly. (Schneider, p15) menjelaskan lima kriteria yang harus dipenuhi oleh suatu

program user friendly, yakni.

1. Waktu belajar yang tidak lama;

2. Kecepatan penyajian informasi yang tepat;

3. Tingkat kesalahan pemakaian rendah;

4. Penghafalan sesudah melampaui jangka waktu;

5. Kepuasan pribadi.

Suatu program interaktif dapat dengan mudah dibuat dan dirancang dengan suatu

perangkat bantu pengembangan sistem antarmuka, seperti Visual Basic, Borland Delphi,

dan sebagainya. Keuntungan penggunaan perangkat bantu untuk mengembangkan

antarmuka menurut Santosa (1997, p7) yaitu.

22

1. Antarmuka yang dihasilkan menjadi lebih baik.

2. Program antarmukanya menjadi mudah ditulis dan lebih ekonomis untuk

dipelihara.

2.5.2 Pedoman Merancang User Interface

Beberapa pedoman yang dianjurkan dalam merancang suatu program, guna

mendapatkan suatu program yang user friendly yaitu.

1. Delapan aturan emas (Eight Golden Rules)

Untuk merancang sistem interaksi manusia dan komputer yang baik, harus

memperhatikan delapan aturan emas dalam perancangan antarmuka, yaitu.

a. Strive for consistency (konsisten dalam merancang tampilan),

b. Enable frequent user to use shortcuts (memungkinkan pengguna

menggunakan shortcuts secara berkala),

c. Offer informative feed back (memberikan umpan balik yang informatif),

d. Design dialogs to yield closure (merancang dialog untuk menghasilkan

keadaan akhir),

e. Offer simple error handling (memberikan penanganan kesalahan),

f. Permit easy reversal of actions (mengijinkan pembalikan aksi dengan

mudah),

g. Support internal locus of control (mendukung pengguna menguasai

sistem), dan

h. Reduce short-term memory load (mengurangi beban jangka pendek pada

pengguna).

23

2. Tampilan Data

Beberapa pedoman yang disarankan untuk digunakan dalam merancang

tampilan data yang baik menurut Smith dan Mosier yang dikutip oleh

Shneiderman (1998, p80) yaitu.

a. Konsistensi tampilan data, istilah, singkatan, format dan sebagainya

haruslah menurut standarisasi.

b. Beban ingatan yang sesedikit mungkin bagi pengguna. Pengguna tidak

perlu mengingat informasi dari layar yang satu ke layar yang lain.

c. Kompatibilitas tampilan data dengan pemasukan data. Format tampilan

informasi perlu berhubungan erat dengan tampilan pemasukan data.

d. Fleksibilitas kendali pengguna terhadap data. Pemakai harus dapat

memperoleh informasi dari tampilan data dalam bentuk yang paling

memudahkan.

3. Teori waktu respon

Waktu respon dalam sistem komputer menurut Shneiderman (1998, p352)

adalah jumlah detik dari saat pemakai memulai suatu aktifitas (misalnya

dengan menekan tombol pada keyboard atau tombol mouse), sampai pada

saat komputer menampilkan hasilnya di perangkat keluaran (monitor,

speaker, printer, dan sebagainya). Beberapa pedoman yang disarankan

mengenai kecepatan waktu respon pada suatu program menurut Shneiderman

(1998, p367) yaitu.

a. Pemakai lebih menyukai waktu respon yang lebih pendek.

24

b. Waktu respon yang panjang (lebih dari 15 detik) akan terasa

mengganggu.

c. Waktu respon yang lebih pendek menyebabkan waktu berpikir pengguna

juga lebih pendek.

d. Langkah yang lebih cepat dapat meningkatkan produktifitas, akan tetapi

juga dapat meningkatkan kesalahan.

e. Waktu respon harus sesuai dengan tugasnya.

1. Untuk mengetik, menggerakkan kursor, memilih dengan mouse: 50

150 milidetik.

2. Tugas sederhana yang sering: < 1 detik.

3. Tugas biasa: 2 4 detik.

4. Tugas kompleks: 8 12 detik.

5. Pemakai harus diberitahu mengenai penundaan yang panjang.