11

BAB 2. LANDASAN TEORI

2.1 Proses Bisnis

Proses bisnis merupakan kombinasi dari aktivitas yang saling berhubungan

didalam sebuah perusahaan untuk menghasilkan pelayanan tertentu kepada klien.

(Leyman et al 1994). Sementara itu, Davenport (1993) mendefinisikan sebuah proses

bisnis adalah aktivitas yang terstruktur untuk menghasilkan keluaran spesifik untuk

pelanggan atau market. Masukkan dapat berupa material, peralatan, objek terukur

lainnya, ataupun berbagai macam informasi yang kemudian diubah menjadi sejumlah

keluaran yang diperlukan oleh penerima. Penerima terbagi menjadi konsumen internal

(internal consumer) dan konsumen luar (eksternal consumer). Konsumen internal dapat

berupa departemen, kelompok, atau sejumlah peralatan dan mesin. Sedangkan

konsumen luar adalah orang atau organisasi yang membayar untuk mendapatkan produk

atau pelayanan yang diperlukan. Selain itu penerima juga dapat berupa lokasi tempat

keluaran disimpan untuk kebutuhan yang akan datang.

Suatu proses bisnis merupakan serangkaian aktivitas yang bertujuan untuk

mencapai tujuan organisasi. Suatu proses bisnis dapat terdiri dari beberapa aktivitas.

Kejadian (event) merupakan suatu aktivitas tunggal yang terdapat pada sebuah proses

bisnis. Setiap proses bisnis dapat dibagi ke dalam tiga jenis kejadian yang berbeda

( 212HLukman,2008), yaitu:

• Kejadian-kejadian Operasional (Operating Events)

• Kejadian-kejadian Informasi (Information Events)

• Kejadian-kejadian Keputusan/Pengelolaan (Decision/Management Events)

12

Kejadian-kejadian Operasional adalah aktivitas-aktivitas operasional yang

dilakukan dalam suatu proses bisnis saat menyediakan barang/jasa bagi pelanggan.

Contoh memasarkan barang, menerima pesanan dari pelanggan, mengirimkan barang

pesanan, dan menerima pembayaran. Pada kejadian-kejadian informasi terdiri dari tiga

aktivitas, yaitu: mencatat data tentang kejadian-kejadian operasional, memelihara data

yang penting bagi organisasi, melaporkan informasi yang berguna bagi para pengambil

keputusan. Kejadian-kejadian Keputusan/Pengelolaan adalah aktivitas-aktivitas di mana

para pimpinan membuat keputusan tentang perencanaan, pelaksanaan, pengawasan, dan

penilaian proses-proses bisnis. Contoh : pimpinan memutuskan untuk membuat produk

baru atau pimpinan memutuskan untuk membuka sebuah cabang baru.

Keterkaitan antar Kejadian Proses Bisnis adalah sebagai berikut :

• Kejadian-kejadian keputusan/pengelolaan akan menentukan dan memicu

kejadian-kejadian operasional.

• Menjalankan kejadian-kejadian operasional akan memicu kejadian-kejadian

informasi untuk mencatat dan memelihara data bisnis.

• Kejadian-kejadian keputusan/pengelolaan juga memicu kejadian-kejadian

informasi, yaitu saat para pimpinan meminta informasi sebelum mengambil

keputusan.

Gambar 2.1 Keterkaitan antar kejadian Proses Bisnis

(Sumber : Lukman, 2008)

13

Contoh kejadian-kejadian operasional umum pada proses bisnis

penjualan/pengumpulan:

• Menerima pesanan barang/jasa dari pelanggan.

• Memilih dan memeriksa barang/jasa yang akan dikirim.

• Mempersiapkan barang/jasa yang akan dikirim.

• Mengirimkan barang/jasa kepada pelanggan.

• Menerima pembayaran untuk barang/jasa yang dijual.

• Menerima pengembalian (retur) barang dari pelanggan.

Suatu proses bisnis yang baik harus memiliki tujuan-tujuan seperti

mengefektifkan, mengefisienkan dan membuat mudah untuk beradaptasi pada proses-

proses didalamnya. Artinya proses bisnis tersebut harus merupakan proses bisnis yang

berorientasikan pada jumlah dan kualitas produk output, minimal dalam menggunakan

sumber daya dan dapat beradaptasi sesuai dengan kebutuhan bisnis dan pasar.

Pengelolaan bisnis proses yang baik akan memberikan keuntungan-keuntungan

pada organisasi perusahaan yang banyak, yaitu :

• Organisasi dapat lebih memfokuskan diri pada kebutuhan customer.

• Organisasi mampu mengendalikan dan memprediksi setiap perubahan yang

terjadi di lingkungan dalam ataupun luar.

• Organisasi mampu memperbaiki tingkat penggunaan sumber dayanya sehingga

dapat menekan biaya pemakaian serendah mungkin.

• Organisasi dapat mengelola dengan baik inter relasi proses-proses antar bagian

yang ada.

2.2 Business Process Improvement

Perbaikan proses bisnis atau Business Process Improvement (BPI) merupakan

sebuah metode yang sistematik yang dikembangkan untuk membantu sebuah

perusahaan memperoleh keuntungan yang signifikan dalam caranya menjalankan proses

bisnisnya (Harrington, 1991).

14

BPI dikembangkan oleh H.James Harrington (1991), seorang International

Quality Advisor pada tahun 1980-an dari Ernst and Young, yaitu sebuah perusahaan jasa

konsultasi profesional yang sangat terkenal dengan 80.000 orang karyawan di seluruh

dunia. Perusahaan seperti IBM, Corning Glass, dan Boeing telah menjalankan

pendekatan ini dan mendapatkan hasil perbaikannya. Tiga tujuan utama dari BPI adalah

(Harrington, 1991) :

o Membuat proses berjalan secara efektif, yaitu memproduksi hasil seperti yang

diinginkan.

o Membuat proses berjalan dengan efisien, yaitu meminimalkan sumber daya yang

digunakan.

o Membuat proses menjadi adaptable, yaitu mampu beradaptasi dengan

perubahan kebutuhan konsumen dan bisnis.

2.3 Reengineering Proses Bisnis

Reengineering proses bisnis adalah pemikiran ulang yang fundamental dan

perancangan ulang yang radikal terhadap proses-proses bisnis organisasi, yang

membawa organisasi mencapai peningkatan yang dramatis dalam kinerja bisnisnya

(Hammer dan Champy, 1993). Reengineering bisa juga diartikan sebagai inovasi proses,

atau perencanaan visi strategik dan strategi kompetitif bau serta pengembangan proses

bisnis baru yang mendukung visi tersebut. Menurut Herbkersman (1994) reengineering

adalah perubahan secara drastis bagaimana cara anggota organisasi menyelesaikan cara

kerja mereka.

Hal mendasar yang perlu dilakukan adalah 'reengineering business process'

termasuk memotong alur proses yang menimbulkan ketidakefisienan atau pengulangan

kerja. Melakukan 'reengineering' berarti meninggalkan cara kerja yang lama dan

memulai lagi dari awal; menciptakan cara kerja baru yang lebih baik Beberapa

perusahaan telah menerapkan paradigma inovasi baru ini untuk mencapai berbagai

perbaikan dalam biaya, kualitas, dan efisiensi. Bahkan makin banyak perusahaan yang

mencari peluang untuk menerapkan proyek reengineering dan metodologi-metodologi

yang membantu mereka dalam mencapai usaha-usaha perbaikan tersebut. Dalam

15

tulisannya, Hammer juga memperkenalkan esensi dan prinsip-prinsip rengineering,

antara lain adalah :

1 Memfokuskan pada faktor-faktor sekitar hasil (outcome) bukan pada tugas, artinya

bahwa suatu perusahaan hendaknya memiliki seorang yang melaksanakan semua

tahapan dalam suatu proses.

2 Suatu perusahaan hendaknya membentuk departemen-departemen terspesialisasi

untuk menangani proses yang terspesialisasi pula.

3 Mengelompokkan pemrosesan informasi ke dalam fungsi yang menghasilkan

informasi.

4 Memperlakukan sumber-sumber yang terpisah seolah-olah tersentralisasi.

5 Mengkaitkan aktivitas-aktivitas paralel serta mengintegrasikan hasil-hasilnya. Hal

ini ditujukan untuk meningkatkan keterkaitan antar fungsi paralel sehingga unit-unit

terpisah bisa melakukan satu fungsi.

6 Menghubungkan aspek-aspek keputusan untuk menyelesaikan tugas dan

membangun sistem pengendalian dalam suatu proses.

7 Memperoleh informasi sekaligus pada sumbernya.

Sementara itu, Davenport dan Short (1990) sebagi pelopor pengembangan

metodologi BPR menentukan framework untuk BPR yang terdiri dari lima tahap sbb:

1. Pengembangan visi bisnis dan tujuan proses

2. Identifikasi proses yang perlu redesign

3. Mengerti dan mengukur proses yang ada

4. Identifikasi kapabilitas IT

5. Design dan buat prototipe proses baru

2.4 Pemodelan Proses Bisnis

Suatu proses dalam perusahaan adalah kombinasi sekumpulan aktivitas yang

digambarkan dengan struktur tertentu untuk menjelaskan logical order dan dependence

sesuai tujuan yang diinginkan (Aguilar-Saven 2004). Model adalah sebuah abstraksi

atau penyederhanaan realita yang mempunyai input dan ouput. Sedangkan permodelan

proses merupakan suatu cara atau jalan untuk memahami dan menganalisa dari suatu

16

proses dalam bentuk model proses. Model proses yang terbentuk memberikan

pemahaman yang menyeluruh dari suatu proses atau sistem. Aguilar menambahkan

bahwa pemodelan proses sangat penting bagi perusahaan karena dengan cara tersebut,

perusahaan dapat mengintegrasikan, menganalisa, dan meningkatkan performance dari

pengelolaan proses bisnisnya.

Pada Gambar 2.2, Phalp, et. al, (1999) membedakan antara penggunaan model

proses bisnis, yaitu: pertama untuk traditional software development dan kedua untuk

restructure proses bisnis, yaitu: pendekatan pragmatik yang khusus untuk menangkap

dan memahami proses, dan pendekatan rigorous (teliti) yang khusus untuk analisis

proses.

Gambar 2.2 Use of Process Models

Aguilar-Saven (2004) mengklasifikasikan kegunaan model proses ke dalam empat

kategori, yaitu:

1. Model deskripsi untuk pembelajaran;

17

2. Model deskripsi dan analitik untuk pendukung keputusan pada pengembangan

dan perancangan proses;

3. Model analitik untuk pendukung keputusan selama proses eksekusi dan kontrol;

dan

4. Model pendukung untuk teknologi informasi.

Aguilar juga mengklasifikasikan model proses ke dalam kategori pasif dan aktif. Model

proses yang tergolong dalam pasif adalah model proses yang tidak memiliki

kemampuan untuk mendukung interaksi dengan user, tidak seperti model yang bersifat

aktif. Contoh dari model-model proses dalam kategori aktif adalah model-model

simulasi.

Kedua klasifikasi di atas, digambarkan dengan sumbu horizontal dan vertikal seperti

terlihat pada Gambar 2.3 di bawah ini.

Gambar 2.3 Klasifikasi teknik pemodelan proses

18

Wilhelm, F., (2000) membagi model-model proses ke dalam lima kategori, yaitu:

1. Model-model temporal: sebagai tambahan untuk mengidentifikasikan dari

subproses, yang hanya memasukkan informasi tentang waktu mulai dan

berakhir, dan durasi komponen-komponen proses.

2. Model-model struktur: hanya merepresentasikan informasi tentang struktur dari

proses.

3. Model-model logika: mendukung dependencies antar elemen-elemen proses.

4. Model-model fungsional: merepresentasikan fungsi-fungsi potensial dari

elemen-elemen dalam sebuah proses.

5. Model-model behavioral: merepresentasikan deskripsi kuantitatif dari proses

yang dibangun dari parameter-parameter, variabel, dll.

Pemodelan proses dapat dipakai sebagai alat bantu dalam perencanaan sistem, analisis

sistem yang biasanya untuk menggambarkan sistem “as is”, dan desain sistem yang

biasanya untuk menggambarkan system “to be”. Adapun teknik pemodelan proses yang

akan digunakan dalam penelitian ini adalah sebagai berikut :

2.4.1 Flowchart

Flowchart adalah penyajian yang sistematis tentang proses dan logika dari

kegiatan penanganan informasi. Flowchart didefinisikan sebagai representasi keadaan

sebenarnya secara formal dari proses manufaktur, rencana organisasi atau struktur

formal (Lakin et al., 1996). Flowchart merupakan representasi grafis dengan

menggunakan simbol seperti operasi, data, arah flow, dan perlengkapan. Pemodelan

flowchart juga merepresentasikan proses yang menggambarkan urutan aktivitas dan

tidak didukung dengan dekomposisi detil aktivitas tersebut.

Adapun alasan pentingnya penggunaan flowchart adalah:

1. Relationship

Flowchart dapat memberikan gambaran yang efektif, jelas, dan ringkas tentang

prosedur logic. Teknik penyajian yang bersifat grafis jelas akan lebih baik daripada

19

uraian-uraian yang bersifat teks khususnya dalam menyajikan logika-logika yang

bersifat kompleks.

2. Analisis

Dengan adanya pengungkapan yang jelas dalam model atau chart, maka para

pembaca dapat dengan mudah melihat permasalahan atau memfokuskan perhatian

pada area-area tertentu sistem informasi.

3. Komunikasi

Karena simbol-simbol yang digunakan mengikuti suatu standar tertentu yang sudah

diakui secara umum, maka flowchart dapat merupakan alat bantu yang sangat efektif

dalam mengkomunikasikan logika suatu masalah atau dalam mendokumentasikan

logika tersebut.

Adapun simbol-simbol yang biasanya digunakan dalam flowchart ditunjukkan pada

tabel 2.1 di bawah ini.

Tabel 2.1 Simbol-Simbol Flowchart

SIMBOL NAMA FUNGSI

Terminator Permulaan/akhir program

Garis alir/flow line Arah aliran

Preparation Proses inisialisasi/Pemberian

harga awal

Proses Proses

perhitungan/Pengolahan data

Input/Ouput data Proses input/ouput data,

parameter,informasi

20

Tabel 2.1 Lanjutan Simbol-Simbol Flowchart

SIMBOL NAMA FUNGSI

Input /Output di cetak ke

kertas

Input berasal dari dokumen

dalam bentuk kertas atau

output di cetak ke kertas

Predefined Proses (Sub

program)

Permulaan sub program/

Proses menjalankan sub

program

Decison Perbandingan

pernyataan/Penyeleksian data

yang memberikan pilihan bagi

langkah selanjutnya

On page connector Penghubung bagian-bagian

flowchart yang berada pada

satu halaman

Off page connector Penghubung bagian-bagian

flowchart yang berada

halaman berbeda

Gambar 2.4 berikut ini menggambarkan proses yang sederhana dengan

menggunakan flowchart. Proses dimulai ketika customer memesan barang ke

perusahaan dan Depatemen Pemasaran dari perusahaan akan menerima order dan

memasukkan informasi tersebut ke dalam sistem informasi ke perusahaan yang akan

mengirim pesanan itu ke bagian Distribution Centre. Bagian Distribution Centre

kemudian akan mengecek ketersediaan dari permintaan produk dan apabila pesanan

tersebut tersedia maka pesanan akan dikirim ke customer bersamaan dengan tagihan,

sebaliknya apabila produk yang dipesan tidak tersedia, maka mereka akan

memberitahukan ke bagian Pemasaran dan bagian Pemasaran akan memberitahukan

kepada customer.

21

Gambar 2.4 Contoh Flowchart

2.4.2 Gantt Chart

Gantt Chart adalah sebuah gambar dimana sumbu y menjelaskan aktivitas-

aktivitas yang dilakukan dalam proses dan sumbu x menggambarkan angka dari setiap

aktivitas (Aguilar-Saven, 2001). Setiap baris berisi single Aktivitas, yang dimana

biasanya terdiri sejumlah angka dan sejumlah nama. Sumbu horizontal

mengindentifikasikan estimasi dari durasi aktivitas, tingkatan ketrampilan yang

dibutuhkan untuk melakukan aktivitas, dan nama seseorang yang ditugaskan pada

aktivitas, yang dimana pada penggambarannya satu kolom untuk satu periode dalam

durasi proyek. Setiap periode bisa menyatakan waktu dalam jam, hari, minggu, bulan

ataupun dalam unit waktu tertentu. Gantt Chart menghubungkan aktivitas-aktivitas ke

dlaam skala waktu, yang dapat digunakan untuk merepresentasikan proses secara grafis

dan kemampuan control pada kondisi situasi tersebut, meskipun sangat terbatas untuk

dianalisis lebih lanjut.

2.4.3 Metode IDEF3

2.4.3.1 Gambaran Singkat IDEF 3

IDEF3 (Integrated Definition Methodology) adalah suatu metode pendiskripsian

proses dimana dalam metode ini disediakan suatu metode terstruktur yang dapat

digunakan oleh para domain expert untuk menjelaskan sebuah sistem atau situasi

sebagai suatu urutan aktivitas. Metode ini juga dapat digunakan untuk menjelaskan

obyek-obyek yang berpartisipasi dalam sistem atau proses.

22

IDEF3 Process Description dikembangkan menggunakan dua strategi, process-

centered dan object-centered. Process-centered mengorganisasikan process knowledge

dengan berfokus kepada proses dan hubungan-hubungan di dalam sebuah skenario,

sedangkan object-centered mengorganisasikan process knowledge dengan berfokus

kepada objek-objek dan perubahan bentuk objek tersebut yang terjadi dalam sebuah

skenario ataupun multiple skenario.

Ada dua tipe skema IDEF3 yang sesuai untuk kedua strategi di atas, yaitu skema

proses dan skema objek. Skema proses menampilkan process-centered dari skenario

yang dibuat dan skema objek dari object-centered mendukung tampilan grafis untuk

informasi.

Di bawah ini akan dijelaskan secara singkat tentang skema proses dan skema objek.

1. Process-Centered Views : Skema Proses

Skema proses IDEF3 memiliki tujuan utama adalah untuk menangkap, mengelola,

dan menampilkan process-centered knowledge. Process-centered dibangun secara

sistematik dengan menggunakan building block IDEF3. Building block tersebut

masing-masing memiliki arti dan kegunaan sendiri.

2. Object-Centered Views : Skema Objek

Skema objek IDEF3 menangkap, mengelola, dan menampilkan deskripsi yang

berfokus pada objek dalam suatu proses, yaitu informasi-informasi tentang

bagaimana objek ditranformasikan ke objek yang berbeda melalui sebuah proses,

dan bagaimana hubungan antar objek-objek tersebut.

2.4.3.2 IDEF3 Process Description Language

Elemen-elemen dasar IDEF3

Tahap awal dalam membuat suatu model IDEF harus ditetapkan terlebih dahulu

skenarionya. Skenario-skenario tersebut merupakan dasar dari pengelolaan struktur

sebuah model IDEF3, dimana di dalam skenario tersebut berisikan aktivitas-aktivitas

23

atau proses yang sifatnya sequencing (berurutan). Sebuah skenario menjelaskan tujuan

dan ruang lingkup dari sebuah model yang dibuat. Model yang dibuat harus jelas untuk

apa tujuan model tersebut, sedangkan ruang lingkup menjelaskan hal-hal apa saja yang

terlibat ataupun tidak terlibat dalam model dan untuk siapa model dibuat.

Elemen-elemen dasar dari IDEF3 ditunjukkan pada gambar di bawah ini:

Gambar 2.5 IDEF3 Process Description Schematics

24

Skema Proses

A. Unit of Behavior/Aktivitas

Aktivitas di dalam teknik pemodelan IDEF3 disebut juga Unit of Behavior (UOB)

merupakan komponen utama dalam pemodelan IDEF3. Dalam diagram IDEF3 aktivitas

tersebut digambarkan dengan persegi panjang. Aktivitas diidentifikasikan dengan

sebuah kata kerja (kata kerja+objek), dan diiringi dengan sebuah nomor unik. Objek

pada penamaan UOB biasanya menjelaskan input utama untuk aktivitaas, output dari

aktivitas, atau nama dari sistem. Ketika sebuah aktivitas dibentuk, diberikan juga nomor

unik. Apabila sebuah aktivitas yang berurutan dihapus, maka nomor pada aktivitas

tersebut tidak dapat digunakan lagi.

Gambar 2.6 Aktivitas IDEF3 dan penomoran.

B. Links

Links berfungsi menghubungkan antar aktivitas (source Aktivitas and destination

Aktivitas). Dalam diagram IDEF3 pada umumnya link berasal dari sebelah kiri dan

berakhir di sebelah kanan kotak aktivitas (UOB).

C. Junctions

Penyelesaian satu aktivitas mungkin menyebabkan beberapa aktivitas untuk memulai,

atau sebuah aktivitas mungkin harus menunggu beberapa aktivitas lain selesai sebelum

aktivitas tersebut mulai. Junctions dapat berfungsi menyebarkan atau menggabungkan

aliran proses dan dapat menjelaskan pencabangan proses.

Di bawah ini menjelaskan 2 fungsi pencabangan :

25

Fan-out junctions mendistribusikan aliran proses. Penyelesaian satu aktivitas

menyebabkan mulainya beberapa aktivitas lain.

Fan-in junctions menggabungkan aliran proses. Penyelesaian satu atau lebih

aktivitas menyebabkan mulainya satu aktivitas.

Tabel di bawah ini menguraikan 3 tipe junctions dengan masing-masing fungsi dan

rules-nya:

Tabel 2.2 Tipe Junctions

Grafik Nama Fungsi Activation Rules

& AND

Junction

Fan-Out Setiap aktivitas tujuan (destination Aktivitas) yang

dihubungkan dengan AND adalah selalu dikerjakan

Fan-In Setiap aktivitas awal (source Aktivitas) yang

dihubungkan dengan AND harus selesai dikerjakan

X

Exclusive-

OR

Junction

Fan-Out

Satu dan hanya satu aktivitas tujuan (destination

Aktivitas) yang dihubungkan dengan Exclusive-OR

dikerjakan

Fan-In

Satu dan hanya satu aktivitas awal (source Aktivitas)

yang dihubungkan dengan Exclusive-OR harus

selesai dikerjakan.

O OR

Junction

Fan-Out

Satu atau lebih aktivitas-aktivitas tujuan (destination

activities) yang dihubungkan dengan OR selalu

dikerjakan.

Fan-In

Satu atau lebih aktivitas-aktivitas awal (source

activities) yang dihubungkan dengan OR harus

selesai dikerjakan.

Synchronous dan Asynchronous Junctions

Pada AND dan OR junction, kita tidak dapat mendiskusikan hubungan antara waktu

mulai dan berakhir suatu aktivitas dari fan-out junctions. Aktivitas-aktivitas dinyatakan

asinkron jika aktivitas-aktivitas tersebut mulai dan berakhir pada saat yang tidak

bersamaan. Tapi, bagaimanapun ada juga mulai dan/atau berakhirnya aktivitas-aktivitas

26

terjadi secara sinkron. Junction sinkron akan digunakan untuk perilaku aktivitas-

aktivitas tersebut. Junction sinkron ditandai dengan dua buah garis vertikal di dalam

sebuah junction, yang berseberangan terhadap garis vertikal pada junction asinkron.

Tabel di bawah ini menunjukkan interpretasi dari sinkron junction.

Tabel 2.3 Junctions sinkronisasi

Grafik Nama Fungsi Activation Rules

AND

Fan-Out Semua aktivitas pada fan-out junction akan mulai

bersamaan.

Fan-In Semua aktivitas pada fan-in junction akan berakhir

bersamaan.

OR

Fan-Out Satu atau lebih aktivitas pada fan-out junction akan

mulai bersamaan.

Fan-In Satu atau lebih aktivitas pada fan-in junction akan

mulai bersamaan.

Exclusive-

OR

Fan-Out

Ketika satu atau hanya satu aktivitas yang

terhubungan pada Exclusive-OR fan-out junction

mulai, sinkronisasi dengan aktivitas-aktivitas lain

adalah tidak mungkin.

Fan-In

Ketika satu atau hanya satu aktivitas yang

terhubungan pada Exclusive-OR fan-in junction

selesai, sinkronisasi dengan aktivitas-aktivitas lain

adalah tidak mungkin.

Junction Pairs

Pada suatu diagram IDEF3, junction sebaiknya dipasangkan, yaitu setiap fan-out

junction memiliki pasangan fan-in junction. Pasangan fan-out junction dan fan-in

junction tidaklah harus merupakan tipe junction yang sama.

27

Junction Combinations

Pada gambar berikut ini Junction dapat digabungkan dari beberapa tipe junction.

Kombinasi junction harus dibuat dan digunakan secara seksama dan benar dengan

diiringi pengertian yang jelas. Kombinasi junction yang ada tidak semuanya benar,

misalnya kombinasi antara XOR junction dengan AND junction.

D. UOB Decomposition

Aktivitas dalam IDEF3 dapat didekomposisikan untuk menjelaskan aktivitas tersebut

lebih detil. Metode IDEF3 memperbolehkan sebuah aktivitas didekomposisikan

beberapa kali, atau yang disebut sebagai multiple children. Metode dekomposisi ini juga

dapat digunakan untuk menjelaskan alternatif-alternatif aliran proses atau aktivitas.

Pada diagram IDEF3 yang terdiri dari multiple dekomposisi, skema penomoran harus

jelas dengan melibatkan nomor dekomposisi seperti Aktivitas ID dan parent Aktivitas

ID. Untuk lebih jelasnya dapat dilihat pada gambar di bawah ini.

1.1.10

Decomposition NumberParent Activity ID

Activity ID

Gambar 2.7 Aktivitas yang memasukkan nomor dekomposisi.

Sebuah nomor UOB dipakai untuk setiap UOB box di dalam sebuah IDEF3 Process

Description. Pada umumnya, sebuah deskripsi IDEF3 dapat menjadi sangatlah

kompleks, yang terdiri dari beberapa UOB, dan memiliki multiple dekomposisi. Pada

level bawah sebuah dekomposisi, nomor referensi dari suatu UOB terdiri dari tiga angka

(misalnya : 1.1.10). Angka pertama merupakan angka terakhir pada parent Aktivitas-

nya. Angka kedua merupakan nomor dekomposisi untuk UOB-nya. Angka ketiga

28

adalah UOB box untuk aktivitas yang bersangkutan. Pemakaian nomor referensi dapat

dilihat pada gambar berikut ini.

Gambar 2.8 Skema penomoran UOB

E. Referent

Referent adalah simbol khusus yang mengacu kepada sisi lain dari deskripsi proses.

Referent ditambahkan pada sebuah diagram agar pembaca secara langsung memahami

informasi apa yang harus diketahui.

F. Elaborasi untuk UOB, junctions, dan link yang dibutuhkan

Elaborasi merupakan penjelasan yang lebih detil dari elemen-elemen IDEF3 dalam

suatu skema baik itu skema proses maupun skema objek. Elaborasi yang dibuat untuk

UOB, junction dan links disesuaikan dengan informasi yang diperoleh dari domain

expert.

2.5 Analisis Struktur Model

Setelah pemodelan proses dipilih untuk menggambarkan sistem “as is”, maka

selanjutnya dilakukan analisis model yang telah digambarkan. Kusiak (1999)

menjelaskan bahwa ada dua tipe analisis yang dapat dilakukan untuk perbaikan proses,

yaitu: analisis observasi (manual) dan analisis computational. Pada analisis observasi,

terdapat 5 cara yang dilakukan (Kusiak, 1999), yaitu:

29

1. Menurunkan durasi proses

Model IDEF3 (dengan resources) dapat digunakan untuk mengidentifikasikan

aktivitas yang perlu dieliminasi. Ketika aktivitas-aktivitas tersebut di

dekomposisi, control dan mekanisme merupakan constraints untuk setiap

aktivitas. Seperti contohnya, sumber daya mungkin dapat diganti dengan

perlengkapan yang otomatis atau penghilangan control ataupun penyederhanaan

control untuk aktivitas tersebut. Control merupakan sejumlah informasi yang

diperlukan untuk melaksanakan suatu aktivitas sehingga pengurangan beberapa

informasi diperlukan akan dapat mengurangi lamanya durasi dan

penyederhanaan proses seperti penyederhanaan prosedur dan mengeliminasi

beberapa aktivitas yang tidak diperlukan.

2. Eliminasi aktivitias redundant

Gambar berikut menunjukkan prinsip eliminasi aktivitas redundant dalam

konteks model IDEF3 dengan input I1 dan I2=O1, output O1 dan O2,

mekanisme M1 dan M2, dan kontrol C1 dan C2.

Gambar 2.9 Eliminasi aktivitas redundant

3. Membagi aktivitas (partitioning)

Gambar berikut menunjukkan konsep partisi dalam model IDEF3 yang

memecah atau membagi aktivitas 2 menjadi aktivitas 2’ dan aktivitas 2’’.

30

Gambar 2.10 Partitioning aktivitas

4. Menggabungkan aktivitas serial (Merging)

Gambar berikut ini merupakan prinsip penggabungan dua aktivitas dengan cara

mengganti atau mengeleminasi kebutuhan mekanisme dan kontrolnya.

Gambar 2.11 Merging dua aktivitas

5. Eliminasi siklus

Gambar berikut ini merupakan prinsip eleminasi siklus dalam model IDEF3.

Aktivitas 3 pada gambar telah dieliminasi dari model sehingga tidak terjadi

siklus.

Gambar 2.12 Eliminasi siklus

31

Analisis computational dilakukan untuk merekayasa model proses. Analisis

struktur model dilakukan pada model IDEF3 yang telah ditransfer ke dalam bentuk

matrik. Analisis computational merupakan analisis yang memanipulasi elemen-elemen

dalam matrik sesuai dengan tujuan yang diinginkan.

2.6 Metoda Qualitative dan Metoda Quantitative

Kusiak, 1999 menjelaskan bahwa terdapat dua tipe analisis yang dapat dilakukan

untuk perbaikan proses yaitu analisis observasi (manual) dan analisis computational.

Analisis observasi dapat dilakukan dengan cara menurunkan durasi proses, eliminasi

aktivitas redundant, membagi aktivitas (partitioning), menggabungkan aktivitas serial

(merging), dan eliminasi siklus.

Analisis qualitative (kualitatif) dapat dilakukan berdasarkan model dari proses

bisnis sehingga analisis ini membutuhkan gambaran detil dari sasaran proses. Analisa

qualitative (kualitatif) merupakan analisis structural yang mengevaluasi proses pada

setiap aktivitasnya berdasarkan kualitasnya seperti dari aktivitas pertama dipilih mana

alternatif yang lebih berkualitas, setelah itu dilanjutkan pada pilihan alternatif pada

aktivitas 2 dan seterusnya Hasil dari analisis qualitative (kualitatif) dapat digunakan

untuk mendeteksi aktivitas-aktivitas mana yang mungkin dapat tereliminasi, yang dapat

diparalel, dapat digabungkan, dapat disederhanakan, di tambah nilai prosesnya ataupun

diotomasikan proses aktivitasnya.

Sedangkan analisis quantitative (kuantitatif) merupakan analisis performance

yang mengevaluasi proses berdasarkan nilai numerik dari parameter, seperti tingkatan

suksesnya, lamanya durasi dan besarnya biaya, serta jumlah aktivitas yang terjadi.

Analisis quantitative (kuantitatif) memerlukan informasi yang dapat diandalkan secara

statistik, maka untuk mendapatkan informasi seperti itu diperlukan analisis

computational untuk identifikasi proses seperti adanya pengembangan algoritma dalam

optimisasi proses bisnis.

Karena sifat model proses yang kualitatif, analisis sering didasarkan pada

metoda observasi (Kusiak et al., 1999). Seperti yang dijelaskan di atas bahwa terdapat

berbagai cara untuk melakukan analisis observasi yang memungkinkan analisis untuk

32

identifikasi model yang kurang sempurna. Model IDEF3 (dengan resources) dapat

digunakan untuk mengidentifikasikan aktivitas yang perlu dieliminasi. Ketika aktivitas-

aktivitas tersebut di dekomposisi, control dan mekanisme merupakan constraints untuk

setiap aktivitas. Seperti contohnya, sumber daya mungkin dapat diganti dengan

perlengkapan yang otomatis atau penghilangan control ataupun penyederhanaan control

untuk aktivitas tersebut. Control merupakan sejumlah informasi yang diperlukan untuk

melaksanakan suatu aktivitas sehingga pengurangan beberapa informasi diperlukan

akan dapat mengurangi lamanya durasi dan penyederhanaan proses seperti

penyederhanaan prosedur dan mengeliminasi beberapa aktivitas. Hasil yang diperoleh

dari analisis qualitative dan analisis quantitative dapat digunakan untuk perbaikan

proses bisnis. Teknik pemodelan proses bisnis seperti flowchart dan IDEF yang

menggunakan pendekatan diagram tidak mampu menganalisis secara kuantitatif dan

tidak mampu mengoptimisasi struktur proses bisnis karena hanya dilakukan secara

manual, hanya dapat dilakukan pada kasus yang sederhana saja tanpa adanya

kemampuan untuk generalisasinya dan hanya menggunakan simbol standar. (Vergidis et

al.,2007).

2.7 Pendekatan Matematis

Di dalam Penelitian Operasional, setelah merumuskan masalah, langkah

berikutnya adalah untuk merumuskan kembali masalah tersebut ke dalam suatu bentuk

yang memudahkan analisa. Pendekatan riset operasi yang konvensional adalah membuat

model matematis yang menggambarkan inti permasalahan. (Lieberman G.J et al.,1990)

Sebelum membahas bagaimana merumuskan model matematis, maka terlebih dahulu

akan membahas sifat-sifat model secara umum dan sifat model-model matematis secara

khusus.

Model atau suatu gambaran yang ideal, merupakan bagian yang integral dalam

hidup sehari-hari. Contoh-contoh model adalah model pesawat terbang, potret dll.

Demikian pula, model mempunyai peranan penting dalam sains dan bisnis, seperti

misalnya model mengenai atom, model mengenai struktur genetik, persamaan-

persamaan matematis yang menggambarkan hukum fisika mengenai gerak atau reaksi-

33

reaksi kimiawi,grafik dan lain-lain. Model-model demikian sangat berguna untuk

mengabstraksikan inti dari apa yang diteliti, memperlihatkan saling keterkaitan

hubungan, dan memudahkan analisa.

Model matematis juga merupakan gambaran yang ideal, tetapi dinyatakan dalam

simbol-simbol dan ungkapan matematika. Model matematis mempunyai banyak

keuntungan dibandingkan deskripsi verbal mengenai masalah. Satu kelebihan yang

nyata adalah bahwa suatu model matematis keseluruhan masalah lebih mudah

dimengerti, dan membantu untuk mengungkapkan hubungan-hubungan sebab akibat

yang penting. Dengan cara demikian, juga jelas ditunjukkan data tambahan apa yang

relevan pada saat analisa. Model matematis juga memudahkan menghadapi masalah

secara keseluruhan dan mempertimbangkan semua hubungan yang saling terkait secara

simultan. Sehingga dapat dikatakan model matematis merupakan jembatan bagi

pemakaian teknik-teknik matematika dan komputer yang canggih untuk menganalisa

masalah. (Lieberman G.J et al.,1990)

Pengembangan model matematis dapat dimulai dengan menjawab ketiga

pertanyaan berikut yaitu :

1. Apa yang diusahakan untuk ditentukan oleh model tersebut ? Dengan kata lain, apa

variabel dari masalah tersebut?

2. Apa batasan yang harus dikenakan atas variabel untuk memenuhi batasan sistem

yang dimodel tersebut?

3. Apa tujuan (sasaran) yang harus dicapai untuk menentukan pemecahan optimum

dari semua nilai yang layak dari variabel tersebut?

Sistem merupakan kumpulan dari elemen yang bekerja secara bersama dalam

rangka mencapai tujuan. Sistem merupakan objek penelitian dan model merupakan

representasi sederhana sari sistem. Terdapat tiga model yaitu ikonik, analog, dan

simbolik. Model ikonik adalah model skala. Model analog menggunakan sistem/model

yang berbeda tetapi mirip dengan sistem model yang menjadi objek penelitian. Model

simbolik berbasis pada hubungan logika yang mengatur sistem. Model simbolik sering

dihubungkan dengan model matematis. (Graham et al., 2000)

34

Seperti yang dijelaskan di atas bahwa model matematis menggambarkan

perilaku sistem menggunakan persamaan dan hubungan logika. Tipe model matematis

mencakup pemograman matematis dan simulasi. Model matematis mencakup

komponen-komponen seperti keputusan, parameter, kendala, dan fungsi tujuan.

Variabel keputusan adalah variabel yang dikendalikan oleh pembuat keputusan.

Parameter adalah nilai yang tidak dapat dikendalikan oleh pembuat keputusan. Kendala

adalah pembatas yang ada di variabel keputusan. Fungsi tujuan mengidentifikasikan

ukuran kinerja dan optimisasi dari ukuran kinerja yang ingin dicapai. Pada model

matematis, semua variabel keputusan, parameter, kendala, dan fungsi tujuan tercakup

secara bersamaan di dalam persamaan atau hubungan berdasarkan logika.

Pemograman matematis merupakan teknik penelitian operasional yang berkaitan

dengan pemecahan masalah untuk menentukan solusi optimal dengan memperhatikan

beberapa pembatas. Model pemograman matematik memilih nilai dari variabel

keputusan untuk mengoptimisasikan fungsi tujuan berdasarkan kendala-kendala yang

ada. Pada formulasi model pemograman matematis, langkah krusialnya adalah

bagaimana menentukan nilai yang tepat untuk parameter-parameternya dan bagaimana

fungsi tujuannya.

Setelah model matematis diformulasikan untuk permasalahan yang sedang

dibahas, sebuah prosedur untuk menghasilkan solusi bagi model harus dikembangkan.

Isu utama dalam model pemograman matematis adalah mencari solusi optimal dan

solusi terbaik. Karena model merupakan representasi suatu permasalahan yang riil

maka tidak dapat dijamin bahwa solusi yang dapat diimplementasikan langsung

terhadap permasalahan nyata. Terdapat banyak faktor-faktor yang tidak dapat

diperhitungkan dan ketidakpastian yang berhubungan denagn permasalahan nyata.

Suatu model yang diformulasikan dan diuji dengan baik, maka solusi yang dihasilkan

akan menjadi suatu pendekatan yang baik bagi pengambil keputusan untuk

permasalahan nyata. Adapun Model umum dari pemograman matematis adalah

Maksimasi atau Minimasi f (xj,........,xn) fungsi tujuan (2.1)

Subject to

35

gi(xj,........,xn) [ ≥=≤ oror ] bi fungsi kendala (2.2)

xj∈ R, j=1,........,n batas dan variabel keputusan (2.3)

Tipe dari pemograman matematis dapat ditentukan oleh beberapa faktor, yaitu :

• Jumlah variabel keputusan

• Tipe dari variabel keputusan

• Bentuk dari fungsi tujuan dan kendala

• Jumlah dari fungsi tujuan

• Formulasi permasalahan

• Kondisi input data atau parameter

2.8 Artificial Intelligence (AI)

Pada sistem dengan kecerdasan buatan, input yang diberikan berupa masalah

dan output yang dihasilkan oleh sistem tersebut berupa solusi. Sedangkan untuk sistem

itu sendiri harus dilengkapi dengan sekumpulan pengetahuan yang ada pada basis

pengetahuan dan harus memiliki interference engine untuk pengambilan kesimpulan

berdasarkan fakta atau pengetahuan tersebut.

Basis Pengetahuan

Interference Engine

Sistem Yang Menggunakan AI

SolusiMasalah

Gambar 2.13 Sistem Yang Menggunakan Kecerdasan Buatan

(Sumber: Kusumadewi, Sri dan Purnomo, Hari, 2005).

Dalam menghimpun pengetahuan diperlukan adanya ruang keadaan (state

space), yaitu ruang yang berisi semua keadaan yang mungkin. Di dalam ruang keadaan

itulah proses pencarian dan pencocokan dilakukan untuk memperoleh kesimpulan yang

36

mengarah pada solusi. Ada 2 teknik pencarian dan pelacakan yang lazim digunakan,

yaitu teknik pencarian buta (blind search) dan teknik pencarian heuristik (heuristic

search). Teknik pencarian buta (blind search) ada 2 macam, yaitu breadth first search

dan depth first search. Teknik pencarian heuristik (heuristic search) terdapat beberapa

metode yang sudah/mulai dikembangkan seperti generate and test, hill climbing, tabu

search, simulated annealing, algoritma genetika, dan algoritma semut.

2.9 Algoritma Genetika

Algoritma genetika (AG) merupakan jenis Evolutionary Algorithm yang paling

populer. Algoritma genetika ini dipengaruhi oleh ilmu biologi dimana baik istilah

maupun konsep yang digunakan berasal dari istilah dan konsep dalam biologi itu

sendiri, terutama mengenai genetika.

2.9.1 Pengertian Algoritma Genetika

Algoritma genetik merupakan algoritma pencarian yang bekerja berdasarkan

mekanisme seleksi alam dan genetika alam untuk menentukan struktur-struktur atau

individu-individu berkualitas tinggi yang terdapat dalam sebuah domain yang disebut

populasi. Algoritma genetika dikembangkan oleh John Holland untuk pertama kalinya.

Ia menyatakan bahwa setiap masalah yang berbentuk adaptasi (alami ataupun buatan)

dapat diformulasikan dalam bentuk terminologi genetika. Keberagaman pada evolusi

biologis adalah variasi dari kromosom antar individu organisme. Variasi kromosom ini

akan mempengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap

hidup. Individu yang lebih fit akan memiliki tingkat survival dan tingkat reproduksi

yang lebih tinggi jika dibandingkan dengan individu kurang fit. Pada saat generasi,

populasi secara keseluruhan akan lebih banyak memuat organisme yang fit. Proses

evolusi biologis itu sendiri dipengaruhi oleh empat kondisi, yaitu :

1. Kemampuan suatu organisme untuk berkembang biak (melakukan reproduksi).

2. Keberadaan populasi dari organisme yang dapat melakukan reproduksi.

3. Variasi/keberagaman organisme dalam suatu populasi.

37

4. Perbedaan kemampuan organisme untuk bertahan hidup (survive)

Algoritma genetika digunakan untuk menyelesaikan masalah permasalahan

searching dan optimisasi yang mempunyai kompleksitas tinggi yang banyak terjadi

dalam dynamic programming. Algoritma genetika dapat menghindari keadaan lokal

optimum yang baik.

Proses pencarian pada algoritma genetik dilakukan dengan melaksanakan suatu

prosedur iteratif untuk mengatur sebuah populasi individu yang merupakan kandidat-

kandidat solusi. Dalam satu siklus iterasi (yang disebut generasi) terdapat dua tahap,

yaitu tahap seleksi dan rekombinasi. Tahap seleksi dilakukan dengan mengevaluasi

kualitas setiap individu dalam populasi untuk mendapatkan peringkat kandidat solusi.

Berdasarkan hasil evaluasi, selanjutnya dipilih secara acak individu-individu yang akan

mengalami rekombinasi. Individu-individu yang mempunyai kualitas yang lebih baik,

mempunyai kemungkinan yang lebih besar untuk dipilih sebagai calon-calon individu

bagi generasi berikutnya. Tahap rekombinasi meliputi proses genetika untuk

mendapatkan populasi baru dari calon-calon individu yang diperoleh pada tahap seleksi.

Alnalogi algoritma genetika dengan sistem biologi menurut Goldberg (1989)

ditunjukkan pada tabel berikut ini.

Natural  Algoritma 

Genetika 

Keterangan 

Kromosom  String  String yangdibentuk dari beberapa karakter 

Gen  Karakter  Informasi tunggal dalam satu kromosom, sekumpulan gen membentuk 

kromosom 

Alele  Nilai karakter  Informasi yang terkandung dalam gen

Lokus  Posisi String  Setiap karakter mempunyai posisi

Genotip  Struktur  Satu atau beberapa string akanbergabung membentuk struktur. 

Fenotip  Parameter  bila struktur tersebut dikodekanakan diperoleh satu titik yang merupakan salah satu alternatif solusi 

38

Goldberg (1989) menyebutkan bahwa terdapat tiga tipe untuk pencarian titik optimal,

yaitu :

1. Calculus Based

Metoda ini berorientasi pada penyelesaian persamaan matematis untuk mencari

titik ekstrim lokal. Ada dua jenis, yaitu metoda langsung dan metoda tidak

langsung. Metoda langsung berharap pada fungsi pertidaksamaan dan

mengerakkannya ke solusi sekitar yang memungkinkan untuk mencapai optimal

lokal. Metoda tidak langsung mencari ekstrim lokal dengan menyelesaikan

beberapa pertidaksamaan matematis, sampai terjadi tingkat kemiringan nol untuk

semua arah. Kedua metoda ini memiliki kelemahan, yaitu kedua metoda ini hanya

mencapai optimal lokal. Di samping itu, jika suatu nilai optimal lokal telah

tercapai, untuk mencari solusi yang lebih baik dibutuhkan metoda modifikasi

solusi ekstrim baik berupa mengadaptasi aspek kerandoman, maupun dengan

aturan-aturan tertentu. Permasalahan lainnya adalah metoda ini sangat bergantung

pada fungsi turunan dari fungsi utama.

2. Enumerative

Metoda ini mencari nilai fungsi obyektif pada setiap poin dalam ruang solusi satu

persatu. Algoritma ini cukup sederhana, tetapi kurang efisien terlebih untuk

permasalahan riil dengan ruang solusi yang sangat besar.

3. Random Search

Metoda ini banyak menjadi perhatian akhir-akhir ini sejalan dengan

berkembangnya penelitian di bidang algoritma, kecerdasan buatan, dan komputasi

evolusioner. Menyadari kelemahan pada dua metoda sebelumnya, berbagai variasi

metoda random search, baik berupa guided search hingga multiple points solution

telah dikemukakan dalam berbagai penelitian yang pada akhirnya berkembang

yaitu metoda simulated annealing, algoritma genetika, dan algoritma evolusioner

lainnya.

Isu utama yang mengiringi algoritma genetika adalah robustness, yaitu keseimbangan

antara efisiensi dan efektivitas yang diperlukan untuk mencari solusi pada berbagai

lingkungan permasalahan yang berbeda. Jika level adaptasi dapat dicapai semakin

tinggi, sistem yang sudah ada dapat melaksanakan fungsinya lebih lama dan lebih baik.

39

Karakteristik robust inilah yang mampu diakomodasi oleh efisiensi dan fleksibilitas dari

sistem biologi. Karakter-karakter seperti perbaikan sendiri (self repair), pemanduan

sendiri (self guidance) dan reproduksi adalah aturan-aturan evolusi yang ada dalam

sistem biologi yang mampu meningkatkan performansi artifisial.

Dengan menggunakan prinsip-prinsip evolusi, algoritma genetika memiliki perbedaan

mendasar dibandingkan dengan metoda pencarian solusi lainnya. Goldberg (1989)

menyebutkan perbedaan mendasar ini, yaitu :

• Algoritma genetika tidak bekerja secara langsung, tetapi bekerja dengan hasil

kodifikasi (parameter) solusi. Solusi beranalogi dengan sifat fisik makhluk

hidup, sedangkan kodifikasi solusi beranalogi dengan pengkodean sifat fisik ke

kromosom. Evolusi yang merupakan inti dari algoritma genetika bekerja dengan

memanipulasi isi kromosom. Hal ini menyebabkan algoritma genetika tidak

dipengaruhi oleh persoalan yang dihadapi secara langsung.

• Algoritma genetika menggunakan kumpulan solusi dalam melakukan pencarian

solusi. Hal ini berbeda dengan solusi lainnya yang hanya menggunakan satu

solusi untuk dievaluasi. Algoritma genetika mengikuti proses evolusi yang

bekerja pada suatu populasi, dimana informasi yang terkandung dalam populasi

akan menentukan individu-individu baru dalam generasi selanjutnya.

• Algoritma genetika bekerja dengan menggunakan informasi yang diperoleh dari

fungsi tujuan saja. Berbeda sekali dengan banyak metoda konvensional yang

biasanya menggunakan informasi lainnya berupa turunan atau pengetahuan

tambahan.

• Algoritma genetika menggunakan aturan transisi probabilistik, bukan

deterministik. Algoritma genetika menggunakan mekanisme acak sebagai alat

bantu untuk mengeksplorasi solusi.

40

2.9.2 Struktur Umum Algoritma Genetika

Struktur umum algoritma genetika menggunakan istilah-istilah yang terdapat

pada ilmu biologi dimana konsepnya pun berasal dari ilmu biologi. Istilah-istilah

tersebut antara lain:

1. Populasi

Populasi merupakan teknik pencarian yang dilakukan sekaligus atas sejumlah

solusi yang mungkin.

2. Kromosom

Kromosom merupakan suatu solusi yang masih berbentuk simbol.

3. Generasi

Generasi merupakan populasi berikutnya setelah populasi awal yang merupakan

hasil evolusi kromosom-kromosom melalui iterasi. Populasi awal itu sendiri

dibangun secara acak.

4. Fungsi Fitness

Fungsi fitness merupakan alat ukur yang digunakan dalam proses evaluasi

kromosom pada setiap generasi.

5. Anak (Offspring)

Anak (offspring) merupakan generasi berikutnya yang terbentuk dari gabungan

dua kromosom sekarang yang bertindak sebagai induk/orang tua (parent)

dengan menggunakan operator penyilangan (crossover) maupun proses mutasi.

Dalam genetika alam, kromosom terdiri dari susunan gen. Tiap gen mengandung

nilai atau sifat tertentu yang disebut allele, sedangkan posisi gen dalam kromosom

disebut lokus. Selanjutnya satu atau beberapa kromosom bergabung membentuk paket

41

genetik yang disebut sebagai genotif. Interaksi genotif ini dengan lingkungannya

disebut fenotif.

Dalam genetika buatan, kromosom bersesuaian dengan string yang dibentuk dari

beberapa karakter. Setiap karakter ini mempunyai posisi (lokus) dan mengandung nilai

tertentu (allele). Satu atau beberapa string akan bergabung membentuk struktur

(genotif), bila struktur tersebut dikodekan akan diperoleh satu titik yang merupakan

salah satu alternatif solusi (fenotif).

2.9.3 Aplikasi Algoritma Genetika

Algoritma genetika pertama kali dirintis pada tahun 1960-an oleh John Holland.

Algoritma genetika diaplikasikan dalam pencarian parameter-parameter optimal.

Namun aplikasinya tidak terbatas pada masalah optimisasi saja, melainkan dapat

digunakan untuk masalah di luar optimisasi. Aplikasi algoritma genetika tersebut, antara

lain:

• Optimisasi

Aplikasi dalam masalah optimisasi, yaitu untuk optimisasi numerik dan optimisasi

kombinatorial seperti Traveling Salesman Problem (TSP), perancangan Integrated

Circuit atau IC, Job Shop Scheduling, optimisasi video, dan suara.

• Pemrograman Otomatis

Aplikasi dalam pemrograman otomatis, yaitu pemanfaatan algoritma genetika

dalam proses evolusi program komputer untuk merancang struktur komputasional,

seperti cellular automata dan sorting networks.

• Machine Learning

Aplikasi dalam machine learning, yaitu untuk merancang neural networks

(jaringan syaraf tiruan) dalam melakukan proses evolusi terhadap aturan-aturan

42

pada learning classifier systems atau symbolic production systems serta untuk

mengontrol robot.

• Model Ekonomi

Aplikasi dalam model ekonomi, yaitu untuk memodelkan proses-proses inovasi

dan pembangunan bidding strategies.

• Model Sistem Imunisasi

Aplikasi dalam model sistem imunisasi, yaitu untuk memodelkan berbagai aspek

dalam sistem imunisasi alamiah, seperti somatic mutation selama kehidupan

individu dan menemukan keluarga dengan gen ganda (multi-gene families)

sepanjang waktu evolusi.

• Model Ekologis

Aplikasi dalam model ekologis, yaitu untuk memodelkan fenomena ekologis

seperti host-parasite co-evolutions, simbiosis dan aliran sumber daya dalam

ekologi.

• Interaksi Antara Evolusi Dan Belajar

Aplikasi dalam interaksi antara evolusi dan belajar, yaitu untuk mempelajari

bagaimana proses belajar suatu individu bisa mempengaruhi proses evolusi suatu

spesies dan sebaliknya.

2.9.4 Karakteristik Masalah yang Dapat Dipecahkan Dengan Menggunakan

Algoritma Genetika

Algoritma genetika dapat memberikan solusi yang ‘bagus’ dan efisien untuk

masalah-masalah berdimensi tinggi, terutama untuk masalah dengan karakteristik

sebagai berikut (Kusumadewi, 2003):

43

• Ruang masalah sangat besar, kompleks, dan sulit dipahami,

• Kurang atau bahkan tidak ada pengetahuan yang memadai untuk

merepresentasikan masalah ke dalam ruang pencarian yang lebih sempit,

• Tidak tersedianya analisis matematika yang memadai,

• Ketika metode-metode konvensional sudah tidak mampu menyelesaikan masalah

yang dihadapi,

• Solusi yang diharapkan tidak harus paling optimal, tetapi cukup ‘bagus’ atau bisa

diterima,

• Terdapat batasan waktu, misalnya dalam real time systems atau sistem waktu

nyata.

• Mempunyai multi-objective dan multi-criteria sehingga diperlukan solusi yang

dapat secara bijak diterima oleh semua pihak.

2.9.5 Komponen Utama Algoritma Genetika

Komponen-komponen utama dalam algoritma genetika ada 6, yaitu:

1. Teknik Penyandian

Teknik penyandian ini merupakan penyandian gen dari kromosom dimana gen

merupakan bagian dari kromosom yang mewakili suatu variabel. Biasanya satu

gen mewakili satu variabel.

Gen dapat direpresentasikan dalam bentuk: string bit, pohon, array, bilangan

real, daftar aturan, elemen permutasi, elemen program, atau representasi lainnya

yang dapat diimplementasikan untuk operator genetika (Kusumadewi, 2003).

Kromosom dapat direpresentasikan dalam bentuk: string bit, bilangan real,

elemen permutasi, daftar aturan, elemen program (pemrograman genetika), dan

struktur lainnya.

44

2. Prosedur Inisialisasi

Inisialisasi kromosom yang terdapat dalam suatu populasi dilakukan setelah

ukuran populasi tersebut ditentukan dimana ukuran populasi tergantung pada

masalah yang akan dipecahkan dan operator genetika yang akan

diimplementasikan. Inisialisasi ini dilakukan secara acak dengan memperhatikan

domain solusi dan kendala permasalahan yang ada.

3. Fungsi Evaluasi

Dalam evaluasi kromosom ada dua hal yang harus dilakukan, yaitu evaluasi

fungsi obyektif (fungsi tujuan) dan konversi fungsi obyektif ke dalam fungsi

fitness. Pada umumnya, fungsi fitness diturunkan dari fungsi obyektif dengan

nilai yang tidak negatif. Jika nilai pada fungsi obyektif adalah negatif maka

perlu ditambahkan suatu konstanta C agar nilai fitness yang terbentuk tidak

negatif.

4. Seleksi

Tujuan dari proses seleksi ini adalah untuk memberikan kesempatan reproduksi

yang lebih besar bagi anggota populasi yang paling fit. Metode-metode yang

digunakan dalam seleksi induk, antara lain:

• Rank-based fitness assignment.

• Roulette-wheel selection.

• Stochastic universal sampling.

• Local selection.

• Trancation selection.

• Tournament selection.

5. Operator Genetika

Operator genetika ada dua, yaitu:

1. Operator untuk melakukan rekombinasi, terdiri dari:

• Rekombinasi bernilai real

45

- Rekombinasi diskret

- Rekombinasi intermediate (menengah)

- Rekombinasi garis

- Rekombinasi garis yang diperluas

• Rekombinasi bernilai biner (crossover)

- Crossover satu titik

- Crossover banyak titik

- Crossover seragam

• Crossover dengan permutasi

2. Mutasi

• Mutasi bernilai real

• Mutasi bernilai biner

2.9.6 Komponen Algoritma Genetika Dalam Matlab

Algoritma genetika dalam matlab memiliki tujuh komponen dimana dalam tiap-tiap

komponen terdapat variasi metode yang diusulkan yang masing-masing memiliki

kelebihan dan kekurangan. Komponen-komponen algoritma genetika tersebut, antara

lain:

1. Skema Pengkodean

Skema yang paling umum digunakan untuk pengkodean ada tiga, yaitu:

• Real-number encoding.

Nilai gen berada dalam interval [0,R], dimana R adalah bilangan real positif dan

biasanya R=1.

0 1 0 1 1 1 0 0 0

46

g1 g2 g3 g4 g5 g6 g7 g8 g9

• Discrete decimal encoding.

Setiap gen bisa bernilai salah satu bilangan bulat dalam interval [0,9].

2 3 9 9 9 9 0 1 3

g1 g2 g3 g4 g5 g6 g7 g8 g9

• Binary encoding.

Setiap gen hanya bisa bernilai 0 atau1.

876876876 321 xxx

0 ,0 1 3 1 1 ,0 0 0 0 0 ,2 3 9 01g 2g 3g

2. Nilai Fitness

Fitness merupakan istilah yang digunakan dalam ilmu Biologi sebagai ukuran

kinerja suatu individu untuk tetap bertahan hidup dalam lingkungannya. Dalam

algoritma genetik, fungsi fitness adalah fungsi objektif dari masalah yang akan

dioptimisasi. Fungsi objektif ini dapat dibayangkan sebagai pengukuran

keuntungan (profit) yang ingin dimaksimumkan atau pengukuran biaya (cost)

yang ingin diminimumkan. Setiap masalah yang akan dioptimisasi memerlukan

pendefinisian fungsi fitness, string dengan kinerja yang lebih baik akan

memiliki fitness yang lebih baik. Setiap string dalam populasi memiliki fitness

tertentu sebagai hasil dari interaksi dengan lingkungannya. Fitness dalam

algoritma genetik diperoleh dari fungsi fitness permasalahan yang dihadapi.

Fungsi fitness ini harus sesuai dengan permasalahan yang akan dioptimisasi.

Fungsi fitness yang ditentukan dengan baik akan menjamin keberhasilan

pencarian pada algoritma genetik.

3. Seleksi Orang Tua

47

Seleksi orang tua merupakan pemilihan dua buah kromosom sebagai orang tua

yang akan dipindah-silangkan, biasanya dilakukan secara proporsional sesuai

dengan nilai fitnessnya. Metode yang umum digunakan dalam seleksi ini adalah

metode roulette-wheel, yaitu metode seleksi dengan penempatan masing-masing

kromosom pada potongan lingkaran pada roda roulette-wheel secara

proporsional sesuai dengan nilai fitnessnya. Kromosom dengan nilai fitness

lebih besar menempati potongan lingkaran yang lebih besar dibandingkan

dengan yang nilai fitnessnya lebih rendah.

Kromosom Nilai Fitness

K1 1

K2 2

K3 0,5

K4 0,5

Jumlah 4

25%

50%

12,5

%12

,5%

K4K3

K2

K1

Gambar 2.14 Contoh penggunaan metode roulette-wheel selection (Sumber: Suyanto, 2005)

Berdasarkan contoh pada gambar 2.14 maka K2 memiliki nilai fitness yang

paling besar dan memiliki peluang sebesar 0,5 (2 dibagi 4) untuk terpilih sebagai

orang tua.

4. Pindah Silang

Pindah silang (crossover) merupakan proses memindah-silangkan dua buah

kromosom guna memperoleh kromosom yang mengarah pada solusi yang bagus.

Namun, pindah silang dapat berakibat buruk bila ukuran populasinya sangat

kecil dimana suatu kromosom dengan gen-gen yang mengarah ke solusi akan

sangat cepat menyebar ke kromosom lainnya. Ada beberapa cara pindah silang,

di antaranya adalah pindah silang satu titik potong (one-point crossover), pindah

silang lebih dari satu titik potong (n-point crossover), dan uniform crossover.

One-point crossover merupakan penyilangan dengan satu titik potong yang

dipilih secara random dimana bagian pertama dari orang tua 1 digabungkan

dengan bagian kedua dari orang tua 2. Sedangkan untuk n-point crossover

48

penyilangan dilakukan dengan lebih dari satu titik potong yang dipilih secara

random. Uniform crossover merupakan kasus khusus dari n-point crossover

dimana n sama dengan jumlah gen dikurangi satu.

5. Mutasi

Operator crossover dan reproduksi dapat menyebabkan terhapusnya materi

penting dalam suatu struktur tertentu. Operator mutasi berguna untuk

mengembalikan materi yang hilang tersebut. Dengan mutasi dapat diciptakan

suatu string baru yang didapat dari memodifikasi satu atau lebih nilai gen pada

string yang sama. Operator mutasi memungkinkan melakukan pencarian dalam

sembarang daerah dalam ruang persoalan.

Pada proses mutasi, jika bilangan random yang dibangkitkan kurang dari

probabilitas mutasi Pmut yag ditentukan maka gen tersebut diubah menjadi nilai

kebalikannya (dalam binary encoding, 0 diubah 1, dan 1 diubah 0). Hal ini

berlaku untuk semua gen yang ada dan biasanya Pmut diset sebagai 1/n dimana n

adalah jumlah gen dalam kromosom.

6. Elitisme

Ketika menciptakan populasi baru dengan crossover atau mutasi, ada

kemungkinan bahwa string dengan fitness terbaik akan hilang. Metode Elitism

ini bertujuan mencegah hilangnya string terbaik pada generasi berikutnya

dengan cara menduplikasi n string terbaik dari populasi as is ke generasi

berikutnya. Metode Elitism ini menunjukkan kinerja yang sangat baik pada

algoritma genetik dalam mencari solusi terbaik (Suyanto,2005).

Elitisme merupakan proses peng-copy-an terhadap individu bernilai

fitness tinggi untuk menjaga agar individu tersebut tidak hilang selama evaluasi.

Hal ini karena bilamana individu bernilai fitness tinggi lolos seleksi, ada

kemungkian individu tersebut akan rusak/menurun nilai fitnessnya karena proses

pindah silang.

49

Uρ

1==

j jFF

Gambar 2.15 Elitist Non-Dominated Sorting GA (Sumber: Deb, 2001)

7. Penggantian Populasi

Penggantian populasi (Generation Replacement) merupakan penggantian semua

individu (misal N individu dalam satu populasi) dari generasi oleh N individu

baru hasil pindah silang dan mutasi. Skema penggantian populasi secara umum

dapat dirumuskan berdasarkan satu ukuran yang disebut generational gap 6 yang

menunjukkan presentase populasi yang digantikan dalam setiap generasi (G =

1).

Steady-state reproduction merupakan skema penggantian yang paling ekstrim

dimana hanya mengganti satu individu dalam setiap generasi, yaitu G = 1/N (N

adalah jumlah individu dalam populasi). Pada steady-state reproduction,

biasanya G sama dengan 1/N atau 2/N. Dalam setiap generasi, ukuran populasi

perlu dijaga tetap N dengan cara menghapus sejumlah NG individu. Prosedur

penghapusan bisa berlaku pada individu bernilai fitness paling rendah atau

individu yang paling tua, atau bisa juga pada semua individu dalam populasi.

50

2.9.7 Algoritma Genetika Sederhana

Langkah-langkah yang dilakukan untuk kasus algoritma genetika secara

sederhana dapat dilihat pada contoh berikut:

Misalkan P(generasi) adalah populasi dari suatu generasi, maka secara sederhana

algoritma genetika terdiri dari langkah-langkah (Kusumadewi, 2003):

1. Generasi = 0 (generasi awal).

2. Inisialisasi populasi awal, P(generasi), secara acak.

3. Evaluasi nilai fitness pada setiap individu dalam P(generasi).

4. Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum

generasi:

a. generasi = generasi +1 (tambah generasi).

b. Seleksi populasi tersebut untuk mendapatkan kandidat induk,

P’(generasi).

c. Lakukan crossover pada P’(generasi).

d. Lakukan mutasi pada P’(generasi).

e. Lakukan evaluasi fitness setiap individu pada P’(generasi).

f. Bentuk populasi baru: P(generasi) = {P(generasi-1) yang survive,

P’(generasi)}

2.9.8 Parameter Genetika

Penentuan parameter ini merupakan merupakan penentuan parameter kontrol

algoritma genetika, yaitu ukuran populasi (popsize), peluang crossover (pc), dan peluang

mutasi (pm). Penentuan nilai parameter ini didasarkan pada permasalahan yang akan

dipecahkan. Parameter-parameter yang sering digunakan dalam algoritma genetika

adalah sebagai berikut:

51

a. Ukuran populasi

Tidak ada aturan yang baku dalam menentukan ukuran populasi (di satu generasi).

Biasanya ukuran populasi diperoleh dengan metode trial and error Bila terdapat

sedikit string, algoritma genetik hanya mempunyai beberapa pilihan untuk

melakukan crossover, yang berarti hanya sebagian kecil dari search space (domain

dari suatu solusi yang mungkin) yang dieksplorasi. Sebaliknya, bila terlalu banyak

string, proses algoritma genetik menjadi lambat. Penelitian menunjukkan bahwa

setelah batas tertentu (sangat bergantung dari encoding dan masalahnya) ternyata

memakai ukuran populasi sangat besar tidak terlalu berguna karena tidak

menyelesaikan masalah dengan lebih cepat (Saputro dan Nico, 1994).

b. Probabilitas crossover (Pc)

Probabilitas crossover mengendalikan operator crossover. Penentuan besarnya Pc

tidak mempunyai aturan khusus namun karena crossover merupakan operator

genetik utama yang memungkinkan timbulnya titik-titik pencarian baru, pada

umumnya Pc besar. Semakin besar Pc, semakin cepat string baru diperkenalkan ke

dalam populasi. Akan tetapi jika nilai Pc yang diberikan terlalu besar, string yang

merupakan kandidat solusi terbaik mungkin dapat hilang lebih cepat dari seleksi.

Jika string-string yang dipilih mempunyai probabilitas (yang ditentukan secara acak)

lebih kecil daripada Pc maka crossover akan bekerja pada string – string tersebut.

Dalam setiap generasi, sebanyak Pc x n individu dalam populasi mengalami

crossover, dimana n adalah jumlah individu dalam sebuah populasi (Saputro dan

Nico, 1994).

c. Probabilitas mutasi (Pm)

Probabilitas mutasi mengendalikan operator mutasi. Penentuan besarnya Pm tidak

mempunyai aturan khusus namun pada umumnya probabilitas mutasi yang

dipergunakan biasanya lebih kecil daripada probabilitas crossover. Hal ini sesuai

prinsip seleksi alam murni, mutasi jarang sekali muncul. Sama seperti Pc, jika

string-string yang dipilih mempunyai probabilitas (yang ditentukan secara acak)

lebih kecil daripada Pm maka mutasi akan bekerja pada string – string tersebut.

52

Dalam satu 2-20 generasi diperkirakan terjadi mutasi sebanyak Pm x n x l, di mana n

adalah jumlah individu dalam sebuah populasi dan l adalah jumlah gen dalam

sebuah kromosom (Saputro dan Nico, 1994).

Walaupun tidak ada aturan baku dalam menentukan parameter- parameter

genetika, namun Marek Obitko di website-nya memberikan rekomendasi sebagai

berikut:

1. Probabilitas crossover (Pc)

Probabilitas crossover secara umum sebaiknya sekitar 80%-95% (walaupun

beberapa hasil percobaan menunjukkan bahwa untuk beberapa permasalahan, Pc

yang terbaik adalah 60%).

2. Probabilitas mutasi (Pm)

Probabilitas mutasi sebaiknya sangat rendah. Pm yang terbaik sekitar 0.5%-1%.

3. Ukuran populasi

Ukuran populasi yang sangat besar biasanya tidak meningkatkan kinerja algoritma

genetik dalam menemukan solusi. Populasi yang baik adalah sekitar 20-30,

walaupun kadang-kadang 50-100 merupakan yang terbaik.

4. Tipe crossover dan mutasi

Tipe crossover dan mutasi yang digunakan tergantung pada encoding yang dipilih

dan masalah yang dihadapi.

2.10 Multi-objective Optimization (MOOP)

Terdapat banyak problem di dunia nyata ini yang memiliki beberapa tujuan yang

hendak dicapai, dengan penentuan nilai variabel yang terlibat di dalamnya.

Permasalahan ini biasanya disebut multi-objective or multi-criterion problem. Akan

53

tetapi, kebanyakan tujuan dari permasalahan tersebut biasanya mengalami konflik, yang

dimana apabila kita mengoptimisasi satu fungsi tujuan yang pertama, maka kita

mungkin tidak akan dapat mengoptimalkan semua fungsi tujuan itu secara bersamaan.

Menurut A.Osyczka, (1985) definisi dari Multi-objective Optimization adalah :

“ sebuah vektor dari variabel keputusan yang merupakan pembatas dan mengoptimalkan

vektor fungsi yang memiliki nilai fungsi tujuan. Fungsi ini terbentuk dari penjelasan

kriteria pencapaian secara matematika yang dimana biasanya menunjukkan konflik di

antara fungsi tujuannya. Oleh sebab itu, optimisasi digunakan untuk menemukan sebuah

solusi yang akan memberikan nilai yang dapat mengoptimalkan semua fungsi tujuan yang

dapat diterima sepenuhnya oleh pembuat keputusan”

Gambar di bawah ini menunjukkan general MOEA Tasks :

1 2(1,2,....k)

2a 3 4 2(1,2,....k)

2a 5

Loop

General MOEA Tasks1. Initialize Population2. Fitness Evaluation2a. Vektor/Fitness Transformation3. Recombination4. Mutation5. Selection

Sequential Decomposition

Gambar 2.16 MOEA Task Decomposition

(Sumber: Coello et al., 2007)

Jadi multi-objective optimization problem adalah permasalahan yang melibatkan

lebih dari satu fungsi tujuan yang akan diminimasi atau dimaksimasi. Jawaban yang

akan diperoleh dari permasalahan ini adalah kumpulan solusi yang menggambarkan

54

tradeoff terbaik di antara fungsi tujuan yang bersaing (Deb, 2001). Adapun bentuk

umum dari model matematis dari fungsi ini adalah :

Min/max fm (x) m = 1,2,……..m (2.4)

Subject to

g i (x) ≥ 0 j = 1,2,.......,j (2.5)

h i (x) = 0 k = 1,2,.......,k (2.6)

Uji

Lj xxx ≤≤ i = 1,2,.......,n ; L =lower bound; U=upper bound (2.7)

Di dalam masalah optimisasi pada single-objective, solusi terbaik mudah

ditentukan/diputuskan dengan membandingkan nilai fungsi objektifnya. Sedangkan

dalam masalah optimisasi pada multi-objective, solusi terbaik ditentukan/diputuskan

dengan dominance. Dominance Test maksudnya adalah sebagai berikut dan contohnya

ditunjukkan pada gambar di bawah ini :

o x1 mendominasi x2, jika

solusi x1 adalah lebih baik dibanding x2 dalam semua hasil fungsi tujuan

solusi x1 lebih baik daripada x2 sedikitnya dalam satu fungsi tujuan

o x1 mendominasi x2 ↔ jika x2 dikuasai oleh x1

55

Gambar 2.17 Contoh Dominance Test

(Sumber: Deb,2001)

Pada gambar 2.17 di atas dapat dilihat bahwa

• 1 Vs 2: 1 mendominasi 2

• 1 Vs 5: 5 mendominasi 1

• 1 Vs 4: tak ada solusi yang mendominasi

Menurut Deb.K (2001), non-dominated solution set adalah merupakan suatu set

solusi, yang merupakan solusi yang tidak didominasi oleh solusi manapun dari

kumpulan anggota solusi yang ada. Pareto-Optimal set adalah kumpulan solusi yang

tidak dikuasai (Non-dominated solution set) di antara domain solusi keputusan yang

mungkin secara keseluruhan. Sedangkan batas yang digambarkan dengan kumpulan

semua titik-titik yang dipetakan dari Pareto-Optimal set disebut Pareto-Optimal Front.

Sasaran dari multi-objective optimization (MOOP) adalah menemukan suatu set solusi

yang sedekat mungkin dengan Pareto Optimal Front dan menemukan set solusi yang

berbeda sebisa mungkin.

56

1

2

Feasible Objective

Space

Pareto-Optimal Front

F2(x)

F1(x) Gambar 2.18 Pencarian set solusi dari MOOP

(Sumber: Deb,2001)

Misalkan vektor x adalah sebuah solusi yang potensial untuk masalah optimisasi. Untuk

vektor x tersebut, kriteria fitness fi adalah fi(x) i = 1,2 ,……,K, dimana K adalah jumlah

kriteria optimisasi. Vektor x disebut sebagai pareto-optimal jika tidak ada individu y

sedemikian hingga fi(y) ≤ fi(x) untuk semua i, dan fj(y) < fj(x) untuk paling sedikit satu

j, dimana j = 1,2,…….K. Himpunan solusi-solusi ini akan membentuk pareto-optimal

set, dan vektor yang termasuk dalam himpunan ini disebut sebagai non-dominated.

Secara umum pareto-optimal set berisi lebih dari satu elemen. Gambar 2.19 di bawah

ini mengilustrasikan pareto optimally dimana titik-titik yang digambarkan dengan

lingkaran membentuk pareto-optimal set di antara titik yang ada.

Gambar 2.19 Contoh Dominated ,Non Dominated Solution dan Pareto Optimally

57

Tantangan dari multi-objective optimization adalah untuk meminimasi jarak (distance)

dari solusi yang dibangkitkan ke pareto set dan memaksimasi keanekaragaman dari

pareto set. Pareto set yang baik diperoleh dari pemandu yang cocok dari proses

penyelusuran melalui desain dari operator reproduksi dan strategi penetapan fitness.

Untuk mendapatkan diversifikasi, maka yang harus diperhatikan adalah proses seleksi,

dan mempertahankan solusi yang mendominasi untuk tidak hilang dalam populasi.

2.11 Algoritma NSGA-II

Kalyanmoy Deb mengembangkan variasi lain dari algoritma yang

dikembangkan oleh Goldberg yang disebut “Non-Dominated Sorting in Genetic

Algorithms” (NSGA). NSGA (Non-Dominated Sorting in Genetic Algorithms)

dikembangkan di Srinivas oleh Kalyanmoy Deb yang merupakan salah satu dari

evolutionary algoritms. Algoritma NSGA ini didasarkan pada beberapa lapisan

penggolongan individu (several layers). Sebelum seleksi dilakukan, populasi diatur

pada basis nondomination yaitu semua individu nondominated digolongkan ke dalam

satu kategori (dengan sebuah nilai dummy fitness yang sebanding dengan ukuran

populasi, untuk menetapkan suatu potensi reproduktif yang sama untuk individu ini).

NSGA adalah algoritma genetika yang sangat popular untuk digunakan pada

permasalahan optimisasi yang multi-objective. NSGA merupakan algoritma yang sangat

efektif akan tetapi banyak yang mengkritik karena kompleksitasnya perhitungannya,

ketiadaan elitism dan membutuhkan parameter yang optimal σshare..

Deb.K. et al. (2000) dalam penelitiannya menjelaskan bahwa terdapat

kekurangan dari algoritma NSGA yaitu karena perhitungan yang kompleks, pendekatan

non-elitism, dan membutuhkan spesifikasi pembagian parameter. Untuk mengatasi

masalah itu maka diperkenalkan algoritma NSGA-II yang dapat menghasilkan solusi

yang lebih baik dengan perhitungan yang lebih sedikit, pendekatan elitist, dan

pembagian parameter yang lebih sedikit.

58

2.11.1 Multi-objective Optimization Using NSGA-II

NSGA-II merupakan versi yang dimodifikasi dan dikembangkan, yang dimana

lebih baik dalam sorting algorithm, disertai elistm dan tidak membutuhkan prioritas

pembagian parameter yang harus dipilih.

Populasi akan dibangkitkan pertama kali, setelah itu populasi akan diurutkan

berdasarkan non-domination pada setiap front. Front yang pertama terbentuk didasarkan

pada kumpulan non-dominant dalam populasi awal dan Front yang kedua akan di

dominasi oleh individu-individu yang berada dalam front yang pertama dan seterusnya.

Setiap individu dalam masing-masing front diberi nilai rank (fitness) atau berdasarkan

front dimana individu itu berada. Individu-individu yang berada dalam front yang

pertama diberikan nilai rank 1 dan individu-individu yang berada dalam front yang

kedua diberikan nilai rank 2 dan seterusnya.

Selain diberikan nilai fitness, parameter baru yang disebut crowding distance

juga dihitung untuk masing-masing individu. Crowding distance adalah pengukuran

mengenai kedekatan antara individu dengan individu di sampingnya. Nilai crowding

distance yang semakin besar akan dapat menghasilkan populasi yang lebih beragam.

Induk-induk (Parents) akan diseleksi dari suatu populasi dengan menggunakan

binary tournament selection berdasarkan nilai rank dan crowding distance. Suatu

individu yang akan dipilih apabila memiliki nilai rank yang lebih kecil dibandingkan

individu yang lainnya atau memiliki nilai crowding distance yang lebih besar dari

individu yang lainnya. Crowding distance dibandingkan apabila jika nilai rank dari

kedua individu tersebut sama. Populasi yang diseleksi akan membangkitkan keturunan

baru (offspring) melalui proses crossover dan mutasi.

Populasi awal yang berisikan induk (parents) dan populasi anak (offspring) di

urutkan kembali berdasarkan non-domination dan hanya N individu yang terbaik yang

akan terpilih, dimana N adalah ukuran populasi.

59

2.11.2 Deskripsi detil dari Algoritma NSGA-II

2.11.2.1 Inisialisasi Populasi

Populasi dibangkitkan berdasarkan pada range dan pembatas masalah jika ada.

2.11.2.2 Non-Dominated Sort

Populasi awal yang telah dibangkitkan akan diurutkan berdasarkan non domination.

Algoritma pengurutannya adalah sebagai berikut :

Untuk setiap individu p dalam populasi yang utama P, dilakukan :

Inisialisasi Sp=Ø, yang nantinya akan berisikan semua individu-individu yang

didominasi oleh p.

Inisialisasi ηp = 0, yang merupakan jumlah individu-individu yang mendominasi

p.

Untuk setiap individu q di dalam P

Jika p mendominasi q maka:

Tambahkan q pada kumpulan Sp yaitu Sp= Sp U {q}

Jika q mendominasi p maka:

Sehingga ηp= ηp + 1

Jika ηp = 0 yaitu tidak terdapat individu yang mendominasi p sehingga p

merupakan front yang pertama dan kemudian individu p diberi rank 1 seperti

prank = 1. Update front yang pertama dengan menambahkan p pada front yang

pertama yaitu F1 = F1 U {p}

Hal ini nantinya akan mengeluarkan semua individu-individu yang berada dalam

Populasi utama P.

60

Inisialisasi front = 1 i =1

Dilakukan pada front ke-i ketika Fi ≠ Ø

Q = Ø merupakan penyimpanan kumpulan individu-individu untuk front ke

(i+1).

Untuk setiap individu p di dalam Front Fi

Setiap individu q yang berada dalam Sp (Sp berisikan semua individu-

individu yang didominasi oleh p)

o ηq = ηq – 1, pengurangan individu q.

o Jika ηq = 0, tidak terdapat individu-individu pada front yang berikutnya

yang mendominasi q. Akibatnya ubah qrank = i+1 dan update Q dengan

menambahkan individu q yaitu Q = Q U q.

Tambahkan counter front dengan 1

Kemudian ubah Q menjadi front berikutnya sehingga Fi = Q

Algoritma ini lebih baik jika dibandingkan dengan Original NSGA sejak

menggunakan informasi mengenai kumpulan individu yang mendominasi (Sp) dan

jumlah individu-individu yang mendominasi suatu individu (ηp)

2.11.2.3 Crowding Distance

Setelah pengurutan yang non-dominated selesai dilakukan, maka dihitung nilai

crowding distance. Perhitungan nilai crowding distance ini hanya dilakukan pada

sepanjang nilai front yang sama, hal ini karena apabila perhitungan nilai front dilakukan

pada dua individu yang berada dalam front yang berbeda tidak akan berarti. Untuk

perhitungan crowding distance dilakukan sebagai berikut :

Pada setiap front Fi, η merupakan jumlah individu-individu

Inisialisasi jarak (distance) untuk semua individu-individu dengan nilai 0 yaitu Fi

(dj) = 0, dimana j adalah individu ke-j di dalam front Fi.

Pada setiap fungsi tujuan m

61

Urutan semua individu-individu di dalam front Fi berdasarkan fungsi tujuan

m yaitu I = sort (Fi,m)

o Untuk pertama kali, berikan nilai jarak (distance) untuk setiap

individu dalam front Fi sama dengan tak terhingga yaitu I(dI) = ∞ dan

I(dn) = ∞

o Untuk k =2 sampai (n-1)

( ) minmax

)1()1()(mm

kk ffmkImkIdIdI

−•−−•+

+= (2.8)

I(k). m adalah nilai fungsi tujuan ke- m dari individu ke-k

di I.

Ide dasar dari crowding distance ini adalah sebenarnya menemukan jarak euclidis di

antara masing-masing individu dari setiap front berdasarkan nilai m dimensi tujuannya.

Individu-individu pada batasan tersebut selalu dipilih ketika memiliki nilai jarak yang

tak terhingga (infinite).

2.11.2.4 Seleksi

Ketika pengurutan berdasarkan non-domination dan nilai crowding distance

selesai dilakukan, maka seleksi dilaksanakan dengan menggunakan crowded

comparison-operator ( np ). Perbandingan dilaksanakan sebagai berikut :

(1) Non domination rank prank yakni individu-individu di dalam front Fi akan

memiliki nilai rank seperti prank = i.

(2) Crowding distance Fi(dj)

- prank < qrank

- atau jika p dan q berada dalam front Fi yang sama dan Fi(dp) > Fi(dq) maka

crowding distance dilakukan.

Semua individu-individu diseleksi dengan menggunakan binary tournament selection

dengan menggunakan crowded comparison-operator.

62

2.11.2.5 Genetic Operators

Real-Coded dari Algoritma Genetika adalah menggunakan Simulated Binary

Crossover dan polynomial mutation.

2.11.2.5.1 Simulated Binary Crossover

Operasi crossover adalah suatu metoda untuk membagi informasi di antara

kromosom-kromosom. Operator rekombinasi dalam real-coded (real parameter) dalam

GA secara langsung menggerakkan dua atau lebih parents untuk menghasilkan dua

atau lebih offspring.

Pertama kali dibangkitkan bilangan random ui yang memiliki nilai di antara 0 dan 1.

Setelah itu hitung nilai β, dan pada akhirnya baru dibangkitkan nilai untuk offspring.

Pada saat bilangan random di antara nilai 0 dan 1 terbentuk. Sesudah itu melalui

probability distribution function, ordinat β ditemukan sehingga daerah di bawah kurva

probabilitas dari 0 sampai β menjadi sama dengan bilangan random ui. Distribusi

probabilitas digunakan untuk menghasilkan solusi child.

( ) ( )[ ]kkkk ppc ,2,1,1 1121 ββ ++−= (2.9)

( ) ( )[ ]kkkk ppc ,2,1,2 1121 ββ −++= (2.10)

dimana ci,k adalah anak (child) ke- dengan sejumlah komponen k, pi,k merupakan induk

(parent) yang dipilih dan βk (≥0) yang merupakan sampel dari bilangan random yang

di-generate yang memiliki kepadatan.

( ) ( ) 10,121

≤≤+= ββηβ η ifp cc (2.11)

63

( ) ( ) 1,1121

2 >+= + ββ

ηβ η ifpcc (2.12)

Distribusi tersebut dapat diperoleh melalui bilangan random ui secara uniform (0,1). ηc

adalah indeks distribusi untuk melakukan crossover, yang menentukan seberapa baik

penyebaran solusi anak dari induknya.

( ) ( ) ( )11

2 += ηβ uu (2.13)

( )( )[ ] ( )1112

1+−

= ηβu

u (2.14)

2.11.2.5.2 Polynomial Mutation

( ) klk

ukkk pppc δ−+= (2.15)

dimana ck adalah anak (child) dan pk adalah induk (parent) dengan ukp yang menjadi

batas atas pada semua bagian induk, lkp merupakan batas bawah dan kδ adalah small

variation yang digunakan dalam perhitungan polynomial distribution dengan

menggunakan :

( ) 5.0,12 11

<−= +kkk rifr mηδ (2.16)

( )[ ] 5.0,121 11

≥−−= +kkk rifr mηδ (2.17)

rk merupakan bilangan random yang uniform (0,1) dan ηm merupakan indeks distribusi

untuk melakukan mutasi.

2.11.2.6 Rekombinasi dan Seleksi

Populasi anak dikombinasikan dengan populasi awal yang dihasilkan pada

generasi tersebut dan seleksi akan dilakukan untuk membentuk individu-individu pada

generasi berikutnya, dan memastikan adanya elitism. Populasi kemudian akan diurutkan

berdasarkan non domination, generasi yang baru tersebut diisi oleh setiap front yang

64

berikutnya sampai ukuran populasi melebihi ukuran populasi yang awal. Jika

menambahkan semua individu-individu di dalam front Fj, maka populasi akan melebihi

populasi N, setelah itu individu-individu di dalam front Fj dipilih berdasarkan nilai

crowding distance dengan mengurangi nilainya sampai ukuran populasinya berukuran

N. Kemudian proses mengulang untuk memulai generasi pada berikutnya.