bab 2 landasan teori - thesis.binus.ac.idthesis.binus.ac.id/doc/bab2/2007-3-00459-ti bab 2.pdf ·...

26

BAB 2

LANDASAN TEORI

2.1 Penjadwalan

2.1.1 Pengertian Penjadwalan

Penjadwalan ialah proses pembuat keputusan yang digunakan sehari-hari

dalam industri manufaktur dan jasa. Alokasi sumber daya harus dilakukan dengan

cara tertentu supaya perusahaan mengoptimasikan objektifnya dan mencapai target.

Sumber daya dapat berupa mesin dalam bengkel, dan aktivitas dapat berupa

pengerjaan pada lantai produksi. Setiap kegiatan mungkin memiliki tingkat prioritas,

waktu mulai tercepat, dan waktu penyelesaian yang berbeda [22].

Dua permasalahan kunci dalam penjadwalan produksi, menurut Wight, ialah

prioritas dan kapasitas. Dengan kata lain, “Apa yang harus dikerjakan terlebih

dahulu?” dan “Siapa yang harus mengerjakannya?”. Menurut Cox et al., penjadwalan

secara detil ialah menugaskan pekerjaan atau sekelompok pekerjaan berdasarkan

waktu mulai dan/atau penyelesaian, untuk menunjukkan kapan hal tersebut harus

selesai bila pesanan manufaktur ingin diselelsaikan tepat waktu. Penjadwalan ialah

alat yang penting bagi manufaktur dan engineering, dimana hal tersebut dapat

memberikan pengaruh yang besar bagi produktivitas sebuah proses. “Dalam industri

manufaktur, tujuan penjadwalan ialah untuk meminimasikan waktu dan biaya

27

produksi, dengan cara mengatur apa yang harus dibuat, kapan, dengan pekerja yang

mana, dan menggunakan alat apa. Penjadwalan produksi memiliki objektif untuk

memaksimalkan efisiensi operasional dan mengurangi biaya” [12].

Perusahaan menggunakan penjadwalan kedepan (forward) dan kebelakang

(backward) untuk mengalokasikan sumber daya pabrik dan mesin, merencanakan

sumber daya manusia, merencanakan proses produksi dan pembelian bahan.

Penjadwalan kedepan ialah merencanakan tugas dari tanggal sumber daya tersedia

untuk menetapkan tanggal pengiriman atau penyelesaian. Penjadwalan kebelakang

ialah merencanakan tugas dari tanggal produk dibutuhkan untuk menetapkan tanggal

dimulainya produksi atau perubahan lain dalam kapasitas yang dibutuhkan [12].

Karena perkiraaan waktu sering tidak akurat dan kejadian serta proyek baru

seringkali muncul, mengikuti sebuah jadwal secara persis menjadi lebih sulit seiring

dengan berjalannya waktu. Dalam beberapa situasi, sistem mungkin mengikuti urutan

yang ditargetkan oleh jadwal walaupun waktu mulai dan selesai yang direncanakan

tidak lagi fisibel. Semakin lama, sebuah jadwal baru akan dibutuhkan.

Oleh karena itu, penjadwalan ulang ialah konsep kunci untuk mengerti sistem

penjadwalan. “Penjadwalan ulang ialah proses memperbarui jadwal produksi yang

sudah ada untuk merespon gangguan serta perubahan lain yang terjadi.” [19]. Ada

banyak macam gangguan yang dapat merusak jadwal produksi, termasuk kegagalan

mesin, penundaan waktu proses, pesanan cepat, masalah kualitas dan bahan yang

tidak tersedia. Dalam dunia nyata, penjadwalan ulang dilakukan secara periodik

28

untuk merencanakan aktivitas untuk periode berikutnya, berdasarkan kondisi sistem.

Hal ini juga dilakukan bila terdapat gangguan yang signifikan.

2.1.2 Klasifikasi Penjadwalan

Karena sifat penjadwalan produksi yang rumit, ada beberapa cara untuk

melihatnya [20]:

Problem-solving Perspective melihat penjadwalan sebagai masalah optimasi.

Hal ini terdiri dari formulasi penjadwalan sebagai masalah optimasi yang

dikombinasikan, dan terisolasi dari perencanaan manufaktur dan sistem

kendali.

Decision-making Perspective ialah sudut pandang bahwa penjadwalan

merupakan keputusan yang harus dilakukan oleh manusia. Para pembuat

jadwal menjalankan berbagai tugas dan menggunakan informasi baik formal

maupun tidak formal untuk menyelesaikannya. Mereka harus menetapkan

ketidakpastian, mengelola bottlenecks dan mengantisipasi masalah yang

diakibatkan oleh manusia.

Organisational Perspective merupakan sudut pandang tingkat sistem yang

melihat bahwa penjadwalan ialah sebagian dari aliran informasi yang rumit

dan pembuatan keputusan yang membentuk sistem perencanaan dan kendali

manufaktur. Sitem-sistem seperti itu biasanya dibagi ke dalam beberapa

29

modul yang mengerjakan fungsi yang berbeda, seperti perencanaan agregat

dan kebutuhan bahan.

Penjadwalan produksi dapat diklasifikasikan berdasarkan kriteria berikut [20]:

Flow patterns

Flow shop: seluruh proyek memiliki alur proses yang identik dan

membutuhkan urutan kerja yang sama.

Job shop: proyek memiliki alur proses yang berbeda, dan mungkin

membutuhkan urutan kerja yang berbeda secara signifikan.

Metode pemrosesan

Unit processing: proyek diproses satu per satu.

Batch processing: beberapa proyek diproses bersamaan sebagai batch.

Job release pattern (waktu pelepasan proyek ialah waktu tercepat dimana

proses dapat dimulai)

Statis: proyek dilepas (atau diasumsikan) ke lantai produksi pada waktu nol.

Dinamis: proyek dilepas (atau diasumsikan) ke lantai produksi setelah waktu

nol.

Konfigurasi pusat kerja

Mesin tunggal: terdapat hanya satu mesin untuk menyelesaikan seluruh

proyek.

Mesin identik paralel: proyek dapat dikerjakan pada semua mesin, dimana

setiap mesin memiliki spesifikasi yang sama.

30

Mesin paralel seragam: proyek dapat dikerjakan pada semua mesin, namun

hasil mungkin akan berbeda dari segi waktu, biaya dan kualitas.

Mesin paralel tidak berhubungan: setiap mesin berbeda dan proyek tidak

dapat berpindah mesin dengan bebas. Biasanya digunakan bila ada urutan

kerja yang membutuhkan tipe mesin lebih dari satu.

2.1.3 Keuntungan Penjadwalan Produksi

Keuntungan melakukan penjadwalan produksi mencakup [12]:

Mengurangi perubahan proses

Mengurangi atau menstabilkan persediaan

Mengurangi usaha penjadwalan

Meningkatkan efisiensi produksi

Meratakan beban kerja

Waktu pengiriman yang akurat

Informasi yang nyata

Menurut [20], tujuan dan keuntungan penjadwalan produksi termasuk:

Dapat memastikan apakah perjanjian pengiriman dapat terpenuhi atau tidak

dan mengindentifikasi periode waktu yang tersedia untuk pemeliharaan

preventif.

31

Memberikan operator lantai produksi sebuah pernyataan eksplisit mengenai

apa yang harus dilakukan sehingga para supervisor dan manajer dapat

mengukur kinerja mereka.

Meminimasi persediaan work in progress.

Meminimasi rata-rata waktu alur melalui sistem.

Memaksimasi penggunaan mesin dan/atau pekerja.

Meminimasi waktu setup.

Dapat mengidentifikasi konflik sumber daya, mengendalikan pelepasan

proyek ke lantai produksi, dan memastikan bahan baku yang dibutuhkan telah

dipesan tepat waktu.

Menciptakan koordinasi yang lebih baik untuk meningkatkan produktivitas

dan menimimasi biaya operasional.

2.1.4 Kekurangan Penjadwalan, Jeda antara Teori dan Praktek

Dunia nyata berbeda dengan model komputer yang ideal, sehingga ada

beberapa batasan fuzzy, tidak adanya informasi, dan perubahan yang tiba-tiba.

Berlung berpendapat, “Hasil dari proses yang dijadwalkan dipengaruhi oleh pembuat

jadwal ditambah kemampuan manusia yang tidak bisa diotomasikan, menyelesaikan

masalah saat sistem gagal, dan bernegosiasi antar kelompok pekerja untuk

mengelola sasaran yang tidak compatible. Pengaruh teknologi dan alat-alat

penjadwalan terbatas dalam sistem penjadwalan produksi. Akhirnya, organisasi

32

mempengaruhi hasil penjadwalan melalui tingkat kedekatan antar pekerja, struktur

rapat, posisi pembuat jadwal dalam hirarki dan peran kerja mereka yang

menghubungkan kegiatan dari bagian-bagian organisasi yang berbeda” [20].

Disamping itu, ada pendapat bahwa kemampuan penerapan riset operasi dan teknik-

teknik artificial intelligence memiliki beberapa kekurangan dalam prakteknya:

1. Kehandalan (robustness), mengacu kepada sejauh mana jadwal akan tetap bila

informasi dasar pembuatan jadwal berubah. Kehandalan menghindari

nervousness dalam penjadwalan dalam situasi tidak pasti. Kebanyakan penulis

berpendapat nervousness harus dihindari sejauh mungkin.

2. Kerumitan (complexity), mengacu kepada jumlah elemen-elemen dunia nyata

yang relevan untuk masalah penjadwalan, serta hubungan antara elemen-

elemen ini. Beberapa masalah mengenai kerumitan ialah penyederhanaan

yang berlebih, dan pengetahuan mengenai pusat masalah.

3. Pengurkuran kinerja (performance measurement), kriteria optimasi dari

banyak teknik penjadwalan tidak dipenuhi oleh kriteria yang digunakan dalam

praktek. Pada prakteknya, kinerja seringkali dinilai dari manusia yang

membuat jadwal, dan dapat dinegosiasikan.

4. Masukan tetap vs. tidak tetap (fixed vs. changeable input), banyak teknik

penjadwalan yang berasumsi bahwa informasi yang dimasukkan tidak dapat

diubah. Akan tetapi, pada prakteknya, masukan seperti kapasitas yang tersedia

dapat berubah bila diperlukan.

33

5. Pengaruh organisasi (organisational embedding), hubungan antara pembuatan

keputusan penjadwalan dengan bagian lain dari organisasi umumnya tidak

dipertimbangkan dalam teknik penjadwalan.

6. Tersedianya dan ketepatan data (availability and accuracy of data), proses

penjadwalan pada awalnya sebagian besar bergantung pada tersedianya data

yang akurat. Jika kondisi ini tidak terpenuhi, jadwal akan salah dan tidak

dapat dilaksanakan dengan benar.

7. Interaksi dengan pembuat jadwal, banyak yang berpendapat bahwa manusia

akan tetap menjadi faktor yang tidak indispensable dalam proses penjadwalan.

Akan tetapi, banyak teknik yang tidak memperhitungkan interaksi dengan

manusia.

2.2 Algoritma Genetika

2.2.1 Pengertian Algoritma Genetika

Banyak cara supaya sebuah komputer dapat menyerupai proses evolusi,

namun algoritma genetika (genetic algorithm) merupakan metode yang memiliki

garis konsep sangat bersih, diciptakan oleh John Holland pada tahun 1970.

“Algoritma genetika (AG) ialah sebuah teknik yang bersifat stokastik dan berbasis

pada ide-ide evolusi dari seleksi alam dan genetika” [1]. “Sesuatu yang stokastik

berbasis pada kejadian yang acak. Munculnya kejadian yang individu tidak bisa

34

diramalkan, akan tetapi mengukur distribusi dari seluruh observasi biasanya

mengikuti sebuah pattern” [13].

Algoritma genetika sangat tepat digunakan untuk penyelesaian masalah

optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode yang

konvensional. Metode ini dapat dikategorikan sebagai pencari global heuristik. AG

masuk ke dalam kelas algoritma evolusioner (atau komputasi evolusioner) yang

menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti keturunan,

mutasi, seleksi dan persilangan (atau rekombinasi). Teknik dasar AG dirancang untuk

mensimulasikan proses-proses dalam sistem alam untuk evolusi, khususnya yang

mengikuti prinsip-prinsip yang dicetuskan oleh Charles Darwin, yaitu “survival of the

fittest”. Karena dalam alam, kompetisi antar individu untuk sumber daya yang

terbatas mengantar mereka yang lebih kuat untuk mendominasi mereka yang lemah.

Algoritma genetika diimplementasikan sebagai simulasi komputer dalam

sebuah populasi dari perwakilan abstrak (disebut dengan kromosom, genotype atau

genome) dari kandidat solusi (disebut dengan individu, mahluk, atau phenotype)

kepada permasalahan optimasi seputar penyelesaian yang lebih baik. Secara

tradisional, solusi dihasilkan dalam binary code sebagai string yang terdiri dari 0 dan

1, namun pemberian kode yang lain juga dimungkinkan. Evolusi biasanya dimulai

dari populasi yang dihasilkan secara acak dan terjadi dalam generasi ke generasi.

“Walaupun menggunakan angka acak, AG tidak sama sekali menghasilkan

nilai yang acak, sebaliknya mereka menggunakan informasi historis untuk

35

mengarahkan pencarian ke daerah dengan performa yang lebih baik” [3]. Perincian

proses encoding dan decoding sebuah kromosom tidak dipahami sepenuhnya, namun

terdapat beberapa teori yang sudah diterima secara luas. Teori inilah yang memiliki

persamaan dengan metodologi yang dicetuskan oleh John Holland:

Evolusi merupakan sebuah proses yang beroperasi pada kromosom, bukan

pada makhluk hidup yang dikodekan.

Seleksi alami ialah hubungan antara kromosom dan performa dari struktur

yang dikodekan. Proses seleksi alami menyebabkan kromosom yang

mengkode struktur yang berhasil untuk mereproduksi lebih sering daripada

mereka yang tidak.

Proses reproduksi ialah titik dimana evolusi berjalan. Mutasi dapat

menyebabkan kromosom dari turunan-turunan biologis menjadi berbeda dari

induknya, dan proses persilangan (atau rekombinasi) dapat menghasilkan

kromosom yang cukup berbeda pada turunannya dengan cara menggabungkan

kode dari kromosom kedua induknya.

Evolusi biologis tidak memiliki ingatan. Apapun yang diketahuinya mengenai

menghasilkan individu yang akan berfungsi dengan baik dalam lingkungan,

terdapat dalam gen – kromosom yang dibawa oleh individu – dan dalam

struktur dekoder kromosom.

36

2.2.2 Terminologi Biologis dan Algoritma Genetika

Kebanyakan dari terminologi yang digunakan oleh komunitas AG

berdasarkan, lewat analogi, ialah yang digunakan oleh para ahli biologi. Binary codes

(atau kode-kode lain) dapat dianggap sebagai sebuah kromosom, dan karena individu

yang diperhitungkan hanya memiliki satu rangkaian (string), kromosom ini juga

dianggap sebagai genotype. Organismenya, atau phenotype, ialah hasil yang

diproduksi oleh genotype dalam lingkungan. Dalam AG ini akan menjadi sebuah

rangkaian parameter yang tidak diketahui, atau vektor solusi individu. Metafora pada

algoritma genetika dapat dilihat pada Tabel 2.1 dan analogi AG pada Tabel 2.2.

Tabel 2.1 Metafora Algoritma Genetika

Sumber: [8]

Algoritma Genetika Alam

Masalah optimasi Lingkungan

Solusi fisibel Individu yang hidup pada lingkungan tersebut

Kualitas solusi (fungsi kesesuaian) Tingkat adaptasi individu pada lingkungannya

Serangkaian solusi fisibel Sebuah populasi organisme (spesies)

Operator stokastik Seleksi, perkawinan dan mutasi dalam proses evolusi alam

Menerapkan iterasi-iterasi operator stokastik pada rangkaian solusi fisibel

Evolusi populasi dalam menyesuaikan terhadap lingkungannya

37

Tabel 2.2 Analogi Algoritma Genetika

Sumber: [15]

2.2.3 Prosedur Algoritma Genetika

2.2.3.1 Langkah Dasar Algoritma Genetika

1. Membangkirkan inisialisasi awal dari populasi secara acak

2. Mencari kesesuaian (fitness) dari populasi

3. Ulangi

a. Pilih induk dari populasi

b. Lakukan persilangan pada induk yang menghasilkan populasi

c. Lakukan mutasi pada populasi

d. Tetapkan kesesuaian dari populasi

4. Hingga individu yang terbaik sudah cukup baik

Diagram 3.2 menggambarkan siklus evolusi dari algoritma genetika.

Biologis Algoritma Genetika

Kromosom atau genotypeStruktur, atau rangkaian gen (seringkali biner)

Locus Sebagian khusus (bit ) yang diposisikan pada string

Phenotype Parameter atau vektor solusi (nilai asli)

38

2.2.3.2 Inisialisasi

Penyelesaian menggunakan algoritma genetika membutuhkan dua hal yang

harus didefinisiskan [11]:

1. Sebuah representasi genetika dari solusi atau individu atau kromosom,

2. Sebuah fungsi kesesuaian (fitness function) untuk mengevaluasi solusi.

Representasi standar dari solusi ialah sebuah array of bits, atau serangkaian

angka atau simbol yang mewakili sesuatu dalam permasalahannya. Sifat utama yang

membuat representasi genetika ini mudah ialah karena bagian-bagian mereka mudah

disusun karena ukurannya yang tetap, yang memungkinkan operasi persilangan

sederhana. Representasi dengan ukuran yang variatif juga dapat digunakan, akan

tetapi implementasi persilangan akan lebih sulit.

Fungsi kesesuaian didefinisikan untuk representasi genetika dan mengukur

kualitas dari solusi yang diwakilkan. Fungsi kesesuaian selalu bergantung pada

permasalahan. Contohnya, pada permasalahan sebuah tas, kami ingin

memaksimalkan nilai total dari objek yang dapat dimasukkan ke dalam tas dengan

kapasitas yang tetap. Representasi solusi mungkin dapat berupa bits, dimana setiap

bit mewakilkan sebuah objek, dan nilai dari setiap bit (0 atau 1) mengartikan apakah

objek tersebut dimasukkan atau tidak ke dalam tas. Tidak setiap representasi seperti

itu dapat digunakan, dimana ukuran dari objek dapat melebihi ukuran tas. Kesesuaian

dari solusi ialah jumlah nilai seluruh objek di dalam tas bila representasi fisibel, bila

tidak maka 0. Dalam beberapa permasalahan, bahkan sulit untuk mendefinisikan

40

2. Persilangan (crossover), yang mewakilkan perkawinan antara dua individu;

3. Mutasi (mutation), yang memperkenalkan modifikasi acak.

2.2.3.4 Operator Seleksi

Operator penghasil generasi ini memiliki beberapa sifat dasar, yaitu: [3]

1. Ide kunci: memberikan preference kepada solusi yang lebih baik, sehingga

memungkinkan mereka untuk menurunkan gen-gen mereka kepada generasi

yang berikutnya.

2. Tingkat kebaikan setiap individu bergantung pada kesesuiannya.

3. Kesesuaian dapat ditetapkan oleh sebuah fungsi obyektif atau sebuah

penilaian subyektif.

Pada setiap generasi, sebuah proporsi dari populasi yang ada dipilih untuk

menurukan generasi yang baru. Solusi individu dipilih melalui proses yang berbasis

keseuaian (fitness-based), dimana solusi yang lebih sesuai atau kuat (diukur dengan

fungsi kesesuaian atau fitness function) cenderung lebih mudah untuk terpilih.

Beberapa metode seleksi mengukur tingginya kesesuaian dari setiap solusi dan lebih

memilih yang terbaik. Beberapa metode lain hanya mengukur sampel acak dari

populasi, karena proses ini dapat memakan waktu banyak.

Kebanyakan fungsi yang digunakan bersifat stokastik dan dirancang sehingga

proporsi kecil dari mereka yang kurang sesuai tetap terpilih. Hal ini dilakukan untuk

41

menjaga supaya ukuran perbedaan populasi tetap besar, yang menghindari

konvergensi prematur pada solusi yang buruk. Beberapa metode seleksi dapat ialah:

1. Roulette-Wheel Selection [21]: induk dipilih menurut kesesuaiannya. Semakin

baik kromosom, semakin tinggi kesempatannya untuk terpilih. Bila semua

kromosom dari populasi diletakkan pada sebuah roda rolet, setiap kromosom

memiliki luas bagian yang berdasarkan fungsi kesesuaiannya, seperti pada

Diagram 2.3. Angka acak dibangkitkan dan kromosom dipilih. Kromosom

dengan kesesuaian yang lebih besar memiliki probabilitas terpilih yang lebih

besar. Kekurangan metode ini ialah bila kromosom terbaik memiliki

kesesuaian 90% dari seluruh roda, maka kromosom lainnya akan memiliki

kesempatan yang sangat kecil untuk terpilih.

Kromosom 1

Kromosom 2

Kromosom 3

Kromosom 4

Diagram 2.3 Roda Rolet

Sumber: [21]

2. Rank Selection [21]: pertama populasi diurutkan lalu setiap kromosom

mendapatkan kesesuaian dari rangking ini. Yang terburuk akan memiliki

kesesuaian 1, kedua terburuk 2 dsb, dan yang terbaik akan memiliki

kesesuaian N (jumlah kromosom dalam populasi). Pada Diagram 2.4 dan

42

Diagram 2.5 dapat terlihat bagaimana situasi berubah setelah mengganti

kesesuaian dengan nomor urut. Setelah proses ini, semua kromosom memiliki

kesempatan untuk terpilih. Namun metode ini akan menuntun ke konvergensi

yang lebih lambat, karena kromosom yang terbaik tidak jauh berbeda dengan

yang lain.

Kromosom 1

Kromosom 2

Kromosom 3

Kromosom 4

Diagram 2.4 Situasi sebelum rangking (menurut kesesuaian)

Sumber: [21]

Kromosom 1

Kromosom 2

Kromosom 3

Kromosom 4

Diagram 2.5 Situasi setelah rangking (menurut nomor urut)

Sumber: [21]

3. Steady-State Selection [21]: bukan merupakan metode seleksi, namun tujuan

utama dari metode ini ialah sebagian besar dari kromosom harus bertahan ke

generasi berikutnya. Dalam setiap generasi, beberapa kromosom dengan

43

kesesuaian yang tinggi dipilih untuk menghasilkan turunan baru. Lalu

beberapa kromosom dengan kesesuaian yang rendah dikeluarkan dan turunan-

turunan baru menggantikannya. Sisa dari populasi bertahan ke generasi

berikutnya.

4. Elitism [21]: bila membuat populasi baru dengan persilangan dan mutasi, kita

memiliki kesempatan yang besar untuk kehilangan kromosom yang terbaik.

Metode ini menyalin kromosom terbaik (atau beberapa yang terbaik) ke

populasi baru, sisanya dilakukan dengan cara biasa. Elitism dapat

meningkatkan kinerja AG karena menghindari hilangnya solusi terbaik.

5. Tournament Selection [6]: metode ini menjalankan sebuah “persaingan” di

antara beberapa individu yang dipilih secara acak dari populasi dan memilih

pemenangnya (dengan kesesuaian yang lebih tinggi) untuk disilangkan.

Tekanan persaingan dapat diubah hanya dengan mengubah ukuran

persaingan. Jika lebih besar, maka individu yang lebih lemah memiliki

kesempatan yang lebih kecil untuk terpilih. Metode ini memiliki beberapa

kelebihan, yaitu bekerja pada arsitektur yang berbeda-beda dan mengizinkan

tekanan persaingan untuk mudah diubah.

2.2.3.5 Reproduksi

Langkah berikutnya ialah untuk mebangkitkan populasi solusi generasi kedua

dari mereka yang terpilih menggunakan operator genetika, yaitu persilangan dan

44

mutasi. Untuk setiap solusi yang dihasilkan, sepasang solusi “induk” dipilih untuk

memberi keturunan dari kumpulan yang dipilih sebelumnya. Dengan menghasilkan

sebuah solusi “turunan” menggunakan persilangan dan mutasi, sebuah solusi baru

akan muncul yang memiliki banyak sifat dari induknya. Induk-induk baru dipilih

untuk setiap turunan, dan proses ini berlanjut hingga sebuah solusi populasi dengan

ukuran yang sesuai telah didapatkan.

Proses ini akhirnya akan menghasilkan populasi kromosom generasi

berikutnya yang berbeda dengan generasi awal. Secara umum, rata-rata kesesuaian

populasi akan meningkat dengan prosedur ini, karena hanya individu terbaik dari

generasi pertama telah dipilih untuk memberi keturunan, bersama dengan mereka

yang kurang baik, untuk alasan yang telah dijelaskan diatas. Ciri-ciri kedua operator,

persilangan dan mutasi, dapat dijelaskan dibawah ini:

1. Operator Persilangan

Untuk operasi persilangan, kromosom dipilih berpasangan (sv, sw). Terdapat beberapa

tipe persilangan, yaitu:

Persilangan aritmetika sederhana (simple arithmetic crossover), dimana svt

dan swt disilangkan pada posisi ke-k. Turunan yang dihasilkan ialah sv

t+l =

(v1,...,vk,wk+1,...,wN) dan swt+l = (w1,...,wk,vk+1,...,vN), dimana k dipilih secara

acak dari {2,..., N-1} [14].

47

Menggunakan operator seleksi dan persilangan akan cenderung

mengakibatkan algoritma untuk berkonvergensi pada solusi yang baik namun

sub-optimal.

Menggunakan mutasi saja akan memberikan sifat acak dalam search space.

Menggunakan seleksi dan mutasi menghasilkan sebuah algoritma yang

paralel, noise-tolerant dan hill climbing.

2.2.3.6 Terminasi

Proses generasional ini diulangi sampai sebuah kondisi terminasi sudah

tercapai. Kondisi pemberhentian yang umum ialah:

Solusi yang memuaskan kriteria sudah ditemukan.

Jumlah generasi tetap sudah tercapai.

Anggaran yang dialokasikan (waktu/uang komputasi) sudah tercapai.

Kesesuaian solusi yang terbaik sedang mencapai atau telah mencapai sebuah

plateau, atau dataran tinggi yang rata, sehingga iterasi-iterasi berikutnya tidak

lagi menghasilkan nilai yang lebih baik.

Inspeksi manual.

Kombinasi dari yang di atas.

48

2.2.2 Kelebihan dan Kekurangan Algoritma Genetika

Ada beberapa kekurangan dan kelebihan metode optimasi ini [17] &[1]:

Kelebihan:

Proposal atau solusi yang buruk tidak mempengaruhi solusi akhir karena

langsung dibuang.

Sifak induktif dari AG berarti metode ini tidak perlu mengetahui peraturan

apapun dari permasalahan – ia bekerja berdasarkan peraturan internalnya

sendiri.

Dapat memberikan informasi mengenai stabilitas dari solusi.

Dapat digunakan untuk memberikan solusi optimasi yang multidimensional.

Kekurangan:

Tidak selalu menemukan optimum global yang pasti.

Karena proses evolusi induktif, pada alam hidup tidak berputar menuju solusi

yang baik, tapi berputar menjauhi yang buruk. Ini dapat mengakibatkan

sebuah spesies untuk berputar menuju kebuntuan evolusioner.

Membutuhkan jumlah evaluasi yang besar dari fungsi kesesuaian.

2.2.3 Contoh Penerapan Algoritma Genetika

Untuk mengilustrasikan manipulasi kromosom menggunakan operator

reproduksi genetika, persilangan dan mutasi, dapat dilihat hasil sampel dari sebuah

masalah yang sangat sederhana.

49

Maksimalkan jumlah satuan dalam sebuah kromosom dengan panjang 10.

Populasi terdiri dari empat kromosom.

Persilangan one-point diaplikasikan dengan probabilitas 0.7. Operator

genetika ini menukar gen antar dua kromosom.

Setiap gen bermutasi dengan peluang 0.1.

Populasi dicetak pada setiap generasi.

Algortima genetika berjalan untuk tiga generasi.

Pertama dilihat populasi awal yang dibangkitkan secara acak, dimana

kesesuaian terbaik ialah 10.

Parameter AG ialah:

Ukuran populasi = 4 Generasi max = 3

Peluang persilangan = 0.7 Peluang mutasi = 0.1

Panjang kromosom = 10 Kesesuaian solusi = 10

p0: 0000110100 kromosom memiliki 3 bits, kesesuaian= 3.0




Terbaik (generasi=0):

1100010110 kromosom memiliki 5 bits, kesesuaian= 5.0

Populasi awal:

generasi=0; nilai terbaik=5.0; rata2=4.5 stddev=1.0

Seleksi menggunakan metode roulette wheel.

Nilai kesesuaian kumulatif dari kromosom dimasukkan.

50

Empat angka acak antara 0 dan 1 ditampilkan untuk memilih anggota populasi

baru.

Nilai kesesuaian kumulatif yang mencakup setiap nilai acak menetapkan

kromosom mana yang terpilih.

Adalah mungkin untuk sebuah kromosom dipilih lebih dari sekali.

mem=0, kesesuaian=0.16666666666666666

mem=1, kesesuaian=0.4444444444444444

mem=2, kesesuaian=0.7222222222222222

mem=3, kesesuaian=1.0

p=0.07431843256287485, dipilih 0

p=0.25792751503513034, dipilih 1

p=0.6502614780006086, dipilih 2

p=0.3749322338318496, dipilih 1





Sekarang sudah terdapat populasi baru, maka persilangan dan mutasi dapat

diterapkan.

Untuk setiap kromosom, sebuah angka acak antara 0 dan 1 ditampilkan.

Jika angka acak lebih kecil daripada peluang persilangan, kromosom dipilih

untuk disilangkan.

Setiap kali dua kromosom terpilih, persilangan one-point diterapkan dan dua

kromosom yang baru menggantikan yang lama dalam populasi.

51

Hanya satu persilangan terjadi pada generasi pertama: kromosom 2 dan 1

menukar gen mereka pada sisi kiri kromosom 1.

111 | 1001000 110 | 1001000

110 | 0010110digantikan oleh

111 | 0010110

Setelah persilangan, populasi baru didaftarkan.

persilangan 2 dan 1

OnePointCrossover: persilangan pada 3





Masing-masing kromosom diberikan kesempatan untuk bermutasi dengan

menampilkan angka acak antara 0 dan 1 untuk masing-masing gennya. Jika angka

acak lebih kecil daripada probabilitas mutasi, nilai gen diubah dari 0 menjadi 1 atau

dari 1 menjadi 0.

mutasi, i=0, gen=3: 0001110100

kromosom memiliki 4 bits, kesesuaian= 4.0

mutasi, i=0, gen=6: 0001111100


mutasi, i=1, gen=9: 1100010111


mutasi, i=2, gen=5: 1101011000


52

mutasi, i=2, gen=7: 1101011100


mutasi, i=3, gen=3: 1111010110


mutasi, i=3, gen=6: 1111011110


Setelah tujuh mutasi gen, populasi baru didaftarkan:

Lapor:generasi=1; nilai terbaik=8.0; rata2=6.25 stddev=1.258

Paling sesuai (generasi sebelumnya=1):


jumlah persilangan dan mutasi: 1 dan 7





Ini menyelesaikan generasi yang pertama. Perhatikan bahwa rata-rata

kesesuaian dan kesesuaian terbaik dari populasi telah meningkat. Setelah dua

generasi berikutnya, populasi didaftarkan sekali lagi.

Rata-rata kesesuaian meningkat, akan tetapi kromosom yang paling sesuai

dalam generasi-generasi sebelumnya telah hilang dari populasi.

Pilihan elitism dapat digunakan untuk menjaga kromosom terbaik yang telah

dihasilkan dari generasi ke generasi.

Lapor: generasi=3, nilai terbaik=7.0; rata2=6.75 stddev=0.5

Paling sesuai (generasi sebelumnya=1):

53


jumlah persilangan dan mutasi: 3 dan 12





bab 2 landasan teori - thesis.binus.ac.idthesis.binus.ac.id/doc/bab2/2007-3-00459-ti bab 2.pdf ·...

Documents