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 (Lukman,2008), yaitu: 21H
•
Kejadian-kejadian Operasional (Operating Events)
•
Kejadian-kejadian Informasi (Information Events)
•
Kejadian-kejadian Keputusan/Pengelolaan (Decision/Management Events)
11
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)
12
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 prosesproses 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).
13
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
14
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 15
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; 16
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
17
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
18
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
19
Tabel 2.1 Lanjutan Simbol-Simbol Flowchart
SIMBOL
NAMA
FUNGSI
Input /Output di cetak ke
Input berasal dari dokumen
kertas
dalam bentuk kertas atau output di cetak ke kertas
Predefined Proses (Sub
Permulaan sub program/
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.
20
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.
21
IDEF3 Process Description dikembangkan menggunakan dua strategi, processcentered 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
22
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
23
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 :
24
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 AND Junction
Fungsi Fan-Out Fan-In
Activation Rules Setiap aktivitas tujuan (destination Aktivitas) yang dihubungkan dengan AND adalah selalu dikerjakan Setiap aktivitas awal (source Aktivitas) yang dihubungkan dengan AND harus selesai dikerjakan Satu dan hanya satu aktivitas tujuan (destination
ExclusiveX
Fan-Out
dikerjakan
OR Junction
Aktivitas) yang dihubungkan dengan Exclusive-OR Satu dan hanya satu aktivitas awal (source Aktivitas)
Fan-In
yang dihubungkan dengan Exclusive-OR harus selesai dikerjakan. Satu atau lebih aktivitas-aktivitas tujuan (destination
Fan-Out O
activities) yang dihubungkan dengan OR selalu dikerjakan.
OR Junction
Satu atau lebih aktivitas-aktivitas awal (source Fan-In
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 25
terjadi secara sinkron. Junction sinkron akan digunakan untuk perilaku aktivitasaktivitas 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 Fan-Out
AND Fan-In Fan-Out OR Fan-In
Activation Rules Semua aktivitas pada fan-out junction akan mulai bersamaan. Semua aktivitas pada fan-in junction akan berakhir bersamaan. Satu atau lebih aktivitas pada fan-out junction akan mulai bersamaan. Satu atau lebih aktivitas pada fan-in junction akan mulai bersamaan. Ketika satu atau hanya satu aktivitas yang
Fan-Out
terhubungan pada Exclusive-OR fan-out junction mulai, sinkronisasi dengan aktivitas-aktivitas lain adalah tidak mungkin.
ExclusiveOR
Ketika satu atau hanya satu aktivitas yang Fan-In
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.
26
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
Activity ID Decomposition Number Parent 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 Aktivitasnya. Angka kedua merupakan nomor dekomposisi untuk UOB-nya. Angka ketiga 27
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: 28
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’’.
29
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
30
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 31
identifikasi model yang kurang sempurna. Model IDEF3 (dengan resources) dapat digunakan untuk mengidentifikasikan aktivitas yang perlu dieliminasi. Ketika aktivitasaktivitas 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, persamaanpersamaan matematis yang menggambarkan hukum fisika mengenai gerak atau reaksi32
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)
33
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 Subject to
34
(2.1)
gi(xj,........,xn) [ ≤ or = or ≥ ] bi Æ fungsi kendala
(2.2)
xj ∈ R, j=1,........,n
(2.3)
Æ batas dan variabel keputusan
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. Sistem Yang Menggunakan AI Masalah
Solusi Interference Engine
Basis Pengetahuan
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
35
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.
36
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 kandidatkandidat 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
Keterangan
Genetika Kromosom
String
Gen
Karakter
String yang dibentuk dari beberapa 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 akan bergabung membentuk struktur.
Fenotip
Parameter
bila struktur tersebut dikodekan akan diperoleh satu titik yang merupakan salah satu alternatif solusi
37
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.
38
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.
39
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
40
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
41
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):
42
• 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.
43
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 44
- 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
2.9.6
•
Mutasi bernilai real
•
Mutasi bernilai biner
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
45
0
0
0
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
g1
g2
g3
9 g4
9
9
g5
g6
0 g7
1 g8
3 g9
• Binary encoding.
Setiap gen hanya bisa bernilai 0 atau1. x1 67 8 0 ,2 3 9 0 g1
x2 67 8 1 ,0 0 0 0 g2
x3 67 8 0 ,0 1 3 1 g3
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
46
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
Nilai Fitness
K1
1
K2
2
K3
0,5
K4
0,5
Jumlah
4
K4
K3
25%
Kromosom
12,5% 12,5%
dengan yang nilai fitnessnya lebih rendah.
K1
50%
K2
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
47
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.
48
ρ
F = U j =1 F j
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.
49
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:
50
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. 51
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
52
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 : Loop
1
2 (1,2,....k)
2a
3
4
2 (1,2,....k)
2a
5
Sequential Decomposition
General MOEA Tasks 1. Initialize Population 2. Fitness Evaluation 2a. Vektor/Fitness Transformation 3. Recombination 4. Mutation 5. Selection
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
53
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)
x Lj ≤ xi ≤ x Uj 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 9 solusi x1 adalah lebih baik dibanding x2 dalam semua hasil fungsi tujuan 9 solusi x1 lebih baik daripada x2 sedikitnya dalam satu fungsi tujuan o
x1 mendominasi x2
↔
jika x2 dikuasai oleh x1
54
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.
55
Feasible Objective Space
F2(x)
1
2 Pareto-Optimal Front
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
56
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.
57
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.
58
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 : 9 Inisialisasi Sp=Ø, yang nantinya akan berisikan semua individu-individu yang didominasi oleh p. 9 Inisialisasi ηp = 0, yang merupakan jumlah individu-individu yang mendominasi p. 9 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
9 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.
59
Inisialisasi front = 1 Æ i =1 Dilakukan pada front ke-i ketika Fi ≠ Ø 9 Q = Ø merupakan penyimpanan kumpulan individu-individu untuk front ke (i+1). 9 Untuk setiap individu p di dalam Front Fi
Setiap individu q yang berada dalam Sp (Sp berisikan semua individuindividu 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. 9 Tambahkan counter front dengan 1 9 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 9 Inisialisasi jarak (distance) untuk semua individu-individu dengan nilai 0 yaitu Fi (dj) = 0, dimana j adalah individu ke-j di dalam front Fi. 9 Pada setiap fungsi tujuan m 60
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) I (d k ) = I ( d k ) +
I ( k + 1) • m − I ( k − 1) • m f mmax − f mmin
(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 ( p n ). 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.
61
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.
c1,k =
1 [(1 − β k ) p1,k + (1 + β ) p2,k ] 2
(2.9)
c 2, k =
1 [(1 + β k ) p1,k + (1 − β ) p2,k ] 2
(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.
p (β ) =
1 (η c +1)β ηc , if 0 ≤ β ≤ 1 2
62
(2.11)
p (β ) =
1 (η c +1) η1c + 2 , if β > 1 2 β
(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.
β (u ) = (2u ) β (u ) =
1
(η + 1 )
(2.13)
1 [2(1 − u )]1 (η + 1)
(2.14)
2.11.2.5.2 Polynomial Mutation
(
)
c k = p k + p ku − p kl δ k
(2.15)
dimana ck adalah anak (child) dan pk adalah induk (parent) dengan p ku yang menjadi batas atas pada semua bagian induk, p kl merupakan batas bawah dan δ k adalah small variation yang digunakan dalam perhitungan polynomial distribution dengan menggunakan :
δ k = (2rk )
1
η m +1
− 1, if rk < 0.5
δ k = 1 − [2(1 − rk )]
1
η m +1
, if rk ≥ 0.5
(2.16) (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 63
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.
64
