BAB 2 LANDASAN TEORI

36

BAB 2 LANDASAN TEORI

2.1

Pengurutan Pekerjaan (Job Sequencing)

2.1.1

Deskripsi Umum Dalam

industri

manufaktur,

tujuan

penjadwalan

ialah

untuk

meminimasikan waktu dan biaya 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. Salah satu permasalahan yang menarik dalam penjadwalan ialah Job Sequencing. Job Sequencing adalah suatu pengurutan pekerjaan, dimana kombinasi urutan-urutan tersebut diukur berdasarkan performanya. Job Sequencing ini merupakan salah satu dari sekian banyak permasalahan pada analisis produksi.

Permasalahan ini sangatlah rumit dan biasanya jauh dari

penyelesaian yang optimal, terutama untuk kasus dimana pekerjaan sangatlah banyak. Menurut Cox et al., Job Sequencing dapat dianalogikan seperti ini: Diberikan sejumlah n Job untuk diproses, dan tiap-tiap Job memiliki waktu mulai, waktu proses, dan waktu dimana tanggal pekerjaan tersebut harus selesai, dan setiap pekerjaan diproses oleh mesin, dan permasalahannya adalah bagaimana mengurutkan mesin-mesin tersebut agar optimal dalam

37

suatu kondisi kriteria tertentu. Hal ini menunjukkan kapan pekerjaan harus selesai bila pesanan manufaktur ingin diselesaikan tepat waktu, dimana hal ini dapat memberikan pengaruh yang besar bagi produktivitas sebuah proses. Dua hal yang menjadi kunci dalam Job Sequencing, menurut Wight, adalah prioritas dan kapasitas. Prioritas berarti “Apa yang harus dikerjakan lebih dahulu?” dan kapasitas berarti “Siapa yang harus mengerjakannya?”. Beberapa daftar dari kriteria performa untuk dioptimalkan dalam Job Sequencing adalah sebagai berikut: •

Rata-rata waktu produksi.

•

Waktu menganggur dari mesin.

•

Rata-rata perbedaan antara waktu selesai dengan waktu pengiriman.

•

Rata-rata pekerjaan yang selesai sebelum waktunya.

•

Rata-rata pekerjaan yang selesai melewati waktunya.

•

Rata-rata waktu menunggu.

•

Rata-rata pekerjaan di dalam system.

•

Persentase dari jumlah pekerjaan yang memiliki perbedaan antara waktu selesai dengan waktu pengiriman. Beberapa faktor yang dideskripsikan dan diklarifikasikan sebagai

permasalahan dalam penjadwalan: •

Jumlah pekerjaan yang harus dijadwalkan.

•

Jumlah mesin.

38

•

Tipe manufaktur (Flow Shop atau Job Shop).

•

Aturan datangnya pekerjaan (Statis atau Dinamis).

•

Kriteria dimana alternatif jadwal lain akan dievaluasi. Faktor pertama menjelaskan jumlah pekerjaan yang akan diproses,

waktu untuk memproses, dan tipe mesin yang diperlukan. Sementara faktor kedua menjelaskan mengenai jumlah mesin yang diperlukan. Faktor ketiga menjelaskan mengenai jenis dari aliran material, jika aliran dari material kontinyu dan pekerjaan tersebut membutuhkan urutan mesin yang sama, maka disebut Flow Shop Pattern. Jika dimana aliran material berbeda-beda tiap pekerjaan, urutan mesin pun berbeda, maka disebut Job Shop Pattern. Dudek et al. melaporkan bahwa sebanyak 57% permasalahan pada industri adalah permasalahan Job Shop, sementara 20% adalah permasalahan Flow Shop. Laporan tersebut menyatakan bahwa kebanyakan dari penelitian mengenai Job Sequencing berkutat seputar permasalahan Flow Shop dengan kriteria tujuan meminimalkan total keseluruhan waktu proses.

Sementara pada

penelitian mengenai Job Shop dihadapkan dengan permasalahan dimana kriteria tidak hanya satu saja, melainkan lebih dari satu.

39

Pola kedatangan pekerjaan dideskripsikan sebagai statis atau dinamis. Pada pola statis, ada sejumlah n pekerjaan, setiap pekerjaan harus diproses oleh beberapa mesin, semua pekerjaan dapat diproses pada inisialisasi awal periode penjadwalan, dan selama pemrosesan, tidak ada pekerjaan baru yang datang. Pada pola dinamis, pekerjaan datang bergantung dari proses stokastik.

2.1.2

Job Shop Sequencing Telah dijelaskan sebelumnya bahwa pengurutan pekerjaan pada produksi sangatlah rumit berdasarkan kombinasi-kombinasi yang sulit dipecahkan. Walaupun beberapa proses telah dicoba untuk diterapkan pada permasalahan Flow Shop, pada permasalahan Job Shop, sangat sedikit perkembangan yang terjadi. Hal ini bergantung dari kompleksnya faktorfaktor yang ada pada permasalahan Job Shop, seperti permasalahan dimana setiap Job memiliki spesifikasi dan urutan proses yang berbeda-beda. Oleh karena itu, maka simulasi menjadi satu-satunya jalan yang digunakan sebagai alat dalam penelitian mengenai Job Shop.

Pada landasan teori ini, akan

dipaparkan beberapa aturan-aturan mengenai pengurutan pekerjaan, dengan permasalahan sebagai berikut:

40

Tabel 2.1 Contoh Soal Job Sequencing Pekerjaan 1 2 3 4 5 6 7 8 •

Waktu Proses 5 8 6 3 10 14 7 3

Pengiriman 15 10 15 25 20 40 45 50

FCFS: Memilih pekerjaan berdasarkan yang datang dahulu, itu yang diproses. Tabel 2.2 Contoh Penyelesaian FCFS

Pekerjaan 1 2 3 4 5 6 7 8

Mulai Proses Selesai 0 5 5 5 8 13 13 6 19 19 3 22 22 10 32 32 14 46 46 7 53 53 3 56 Total Keterlambatan Rata-rata Keterlambatan Keterlambatan Maksimum Jumlah Pekerjaan Terlambat

Pengiriman Keterlambatan 15 -10 10 3 15 4 25 -3 20 12 40 6 45 8 50 6 39 6.5 12 6

41

•

DDATE: Memilih pekerjaan berdasarkan tanggal pengiriman yang terdekat. Tabel 2.3 Contoh Penyelesaian DDATE

Pekerjaan 2 1 3 5 4 6 7 8

•


Pengiriman Keterlambatan 10 -2 15 -2 15 4 20 9 25 7 40 6 45 8 50 6 40 6.67 9 6

SLACK: Memilih pekerjaan berdasarkan selisih waktu terkecil antara tanggal pengiriman dan waktu proses. Tabel 2.4 SLACK Tiap Pekerjaan Pekerjaan 1 2 3 4 5 6 7 8

Waktu Proses 5 8 6 3 10 14 7 3

Pengiriman 15 10 15 25 20 40 45 50

Slack 10 2 9 22 10 26 38 47

42

Tabel 2.5 Contoh Penyelesaian SLACK Pekerjaan 2 9 1 5 4 6 7 8

•


Pengiriman 10 15 15 20 25 40 45 50

Keterlambatan -2 -1 4 9 7 6 8 6 40 6.67 9 6

SPT: Memilih pekerjaan berdasarkan waktu proses yang paling cepat. Tabel 2.6 Contoh Penyelesaian SPT

Pekerjaan 4 8 1 3 7 2 5 6


Pengiriman Keterlambatan 25 -22 50 -44 15 -4 15 2 45 -21 10 22 20 22 40 16 62 15.5 22 4

43

•

Critical Ratio: Memilih pekerjaan berdasarkan faktor kritis terkecil, yaitu perbandingan antara tanggal pengiriman dan waktu proses. Tabel 2.7 Critical Ratio Pekerjaan 1 2 3 4 5 6 7 8

Waktu Proses 5 8 6 3 10 14 7 3

Pengiriman 15 10 15 25 20 40 45 50

CR 3.00 1.25 2.50 8.33 2.00 2.86 6.43 16.67

Tabel 2.8 Contoh Penyelesaian Critical Ratio Pekerjaan 2 5 3 6 1 7 4 8


Pengiriman Keterlambatan 10 -2 20 -2 15 9 40 -2 15 28 45 5 25 28 50 6 76 15.2 28 5

44

Selain aturan-aturan yang tertera diatas, terdapat juga beberapa algoritma yang dapat digunakan untuk permasalahan pengurutan pekerjaan. Salah satunya adalah algoritma Hodgson, yang memiliki tahapan sebagai berikut: 1. Urutkan semua pekerjaan dengan aturan DDATE, jika terdapat suatu pekerjaan dengan nilai keterlambatan nol atau nilai keterlambatan positif, hentikan. Jika selain itu, lanjutkan ke langkah 2 2. Dimulai dari mula aturan DDATE, temukan task yang terlambat pertama kali. Jika tidak ada task yang terlambat, lanjutkan ke langkah 4, jika ada, lanjutkan ke langkah 3 3. Anggaplah suatu pekerjaan yang telat ada pada urutan ke i pada urutan. Maka periksa semua pekerjaan sampai pada urutan ke i dan identifikasi yang memiliki waktu proses terlama. Ambil pekerjaan itu dan singkirkan. Revisi semua perhitungan keterlambatan, dan kembali ke langkah 2. 4. Semua pekerjaan yang telah disingkirkan dapat ditaruh ke urutan terakhir dalam pekerjaan.

45

Berikut adalah contoh penyelesaian Algoritma Hodgson: Tabel 2.9 Contoh Penyelesaian Algoritma Hodgson Iterasi 1 2 1 3 5 4 6 7 8 5 6 10 3 14 7 8 13 19 29 32 46 53 10 15 15 20 25 40 45 -2 -2 4 9 7 6 8 Urutan Baru : …………………2

i ti ci di Li

8 3 56 50 6

Tabel 2.10 Contoh Penyelesaian Algoritma Hodgson Iterasi 2 i ti ci di Li

1 3 5 4 6 7 5 6 10 3 14 7 5 11 21 24 38 45 15 15 20 25 40 45 -10 -4 1 -1 -2 0 Urutan Baru: ……………..2 - 5

8 3 48 50 -2

Tabel 2.11 Contoh Penyelesaian Algoritma Hodgson Iterasi 3 1 3 4 6 7 8 i 5 6 3 14 7 3 ti 5 11 14 28 35 38 ci 40 45 50 di 15 15 25 -12 Li -10 -4 -11 -12 -10 Urutan Baru: 1 – 3 – 4 – 6 – 7 – 8 – 2 – 5 Pada iterasi pertama, dicari pekerjaan yang memiliki Li positif pertama kali, didapat terjadi pada pekerjaan no. 3. Setelah itu, dari pekerjaan pada urutan paling awal sampai pada urutan pekerjaan yang memiliki Li positif pertama kali, dicari ti paling besar, dan didapat pada pekerjaan no. 2,

46

sehingga no. 2 dihapus dari daftar, dan ditaruh paling belakang. Pada iterasi selanjutnya, pekerjaan no. 2 sudah tidak ada pada daftar, dan lakukan hal yang sama, hingga terdapat pekerjaan no. 5 yang harus dihapus dari daftar dan ditaruh di paling belakang. Sehingga sampai pada iterasi ke-3 dimana tidak ada lagi pekerjaan yang memiliki Li positif, sehingga urutannya adalah urutan pekerjaan pada iterasi ke-3 ditambah dengan urutan pekerjaan yang sudah dihapus pada iterasi-iterasi sebelumnya. Selain algoritma Hodgson, terdapat juga algoritma Wilkerson-Irwin, yang memiliki tahapan sebagai berikut: 1. Urutkan pekerjaan dengan aturan DDATE. Bandingkan dua pekerjaan pertama pada urutan, anggap pekerjaan ini adalah a dan b. Jika max (ta,tb) ≤ dari max (da, db), masukkan task a ke kolom α dan yang lainnya ke kolom β. Jika tidak, maka masukkan pekerjaan dengan waktu pemrosesan terpendek ke kolom α dan yang lainnya ke kolom β .Pekerjaan ketiga di dalam urutan dimasukkan ke kolom γ. 2. Bandingkan β dan γ untuk melihat jika β akan dijadwalkan bersama dengan α pada urutan. Jika tβ ≤ tγ atau jika Fα + max (tβ, tγ) ≤ max (dβ, dγ), pindahkan pekerjaan di kolom β ke α dan pekerjaan di kolom γ ke β. Pekerjaan selanjutnya dalam urutan DDATE akan dimasukkan ke dalam kolom γ. Fα adalah nilai kumulatif dari waktu proses pekerjaan yang ada pada kolom α Jika tidak ada lagi pekerjaan dari urutan DDATE, masukkan

47

pekerjaan α dan β ke dalam urutan lalu hentikan.

Selain itu, ulangi

langkah 2. Jika dua kondisi diatas tidak terpenuhi, pergi ke langkah 3. 3. Taruh β ke dalam urutan teratas pada DDATE tersisa dan pindahkan pekerjaan di γ ke kolom β. Bandingkan α dan β untuk melihat apakah β akan dijadwalkan bersama dengan α pada urutan. Jika tα ≤ tβ atau jika Fα – tα + max (tα, tβ) ≤ max (dα, dβ), pindahkan pekerjaan pada kolom β ke kolom α dan pilih dua pekerjaan berikutnya pada daftar DDATE untuk menjadi β dan γ yang baru. Kembali ke langkah 2. Jika kondisi tidak terpenuhi, pergi ke langkah 4. 4. Masukkan pekerjaan pada kolom α kembali ke daftar teratas DDATE dan masukkan pekerjaan terakhir ke kolom α. Kembali ke langkah 3. Jika tidak ada pekerjaan di dalam urutan, masukkan β ke urutan dan pindahkan dua pekerjaan pertama pada daftar DDATE menjadi β dan γ. Kembali ke langkah 2 Berikut adalah contoh penyelesaian Algoritma Wilkerson-Irwin: Tabel 2.12 Contoh Penyelesaian Algoritma Wilkerson-Irwin Step

2 2 2 3 2 2

α

2 1 3 3 4 5

β

1 3 5 4 5 6

γ

3 5 4

Step 2: Calculation Fα + max (tβ, tγ) ≤ max (dβ, dγ) 8+6≤15 Yes 13+10≤20 No 19+10≤25 No

TB tβ ≤ tγ

Step 3: Calc Fα – tα + max (tα, tβ) ≤ max (dα, dβ)

22+14≤40 Yes 32+14≤45 No

tα ≤ tβ

5≤6 Yes 6≤10 Yes 10≤3 No 19-6+6≤25 Yes

6 7

TA

10≤14 Yes 14≤7 No

6≤3 No

48

Tabel 2.13 Contoh Penyelesaian Algoritma Wilkerson-Irwin (lanjutan) Step 3 2 3 2

α 5 7 7 8

β 7 6 8 6

γ

Step 2: Calculation

TB

8

39+14≤50 No

14≤3 No

Step 3: Calc 32-10+10≤45 Yes

TA 10≤7 No

39-7+7≤56 Yes

7≤3 No

Urutan Baru: 2 – 1 – 3 – 4 – 5 – 7 – 8 – 6 Pada awalnya, urutan adalah 2 1 dan 3, dimasukkan ke kolom α, β dan γ. Pada iterasi selanjutnya, pekerjaan di kolom α dimasukkan ke dalam urutan pekerjaan yang baru, hingga didapati untuk selanjutnya urutan kolom kolom α, β dan γ berdasarkan pekerjaan yang tersisa pada DDATE. Pada saat kedua syarat No, yaitu tidak terpenuhi, maka pekerjaan pada kolom β, yaitu pekerjaan no. 5, disimpan sementara ke dalam urutan DDATE, sehingga pada saat kembali ke step 2, urutan DDATE berikutnya lah yang memasuki kolom α, β dan γ, dimana ada pekerjaan no. 5 disitu, begitu seterusnya sampai tidak ada lagi pekerjaan yang tersisa pada DDATE. Pada umumnya, beberapa aturan yang ada terbukti lebih baik daripada aturan yang lain. Akan tetapi, hal ini juga dipengaruhi oleh banyak faktor, seperti kriteria performa, pola kedatangan pekerjaan, dan lainnya. Ada aspek dinamis dari sebuah permasalahan Job Shop Sequencing. Sebuah jadwal dari beberapa pekerjaan telah dibuat, dan sementara jadwal tersebut dilaksanakan, pekerjaan baru akan datang.

Muhlemann et al.,

mengatakan bahwa ada dua kondisi ekstrim untuk menjadwalkan sebuah Job

49

Shop: yang pertama yaitu membuat ulang jadwal setiap kali ada pekerjaan baru, atau langsung menyelesaikan jadwal yang ada sebelum menyelesaikan pekerjaan yang baru datang. Pada kasus kedua, ini mengubah permasalahan Job Shop dari dinamis menjadi statis. Sementara itu, hal yang baik adalah menggunakan sebuah komputer yang senantiasa online dan cepat tanggap terhadap setiap perubahan yang terjadi. Sebuah program komputer yang baik akan menganalisa status aktual saat sebuah jadwal berlangsung, dan mengaplikasikan berbagai macam kriteria, hingga menyusun ulang jadwal yang sedang berlangsung. Akan tetapi, membutuhkan suatu biaya yang mahal untuk menyusun sebuah program komputer yang efektif, dan ini menjadi suatu hambatan bagi banyak perusahaan maupun peneliti pada masa ini

2.2

Algoritma Genetika

2.2.1

Deskripsi Umum Algoritma Genetika Algoritma Genetika adalah suatu algoritma yang didasarkan pada konsep evolusi dan perubahan gen pada makhluk hidup. Algoritma Genetika (AG) diciptakan oleh John Holland dari Universitas Michigan pada tahun 1975. Algoritma Genetika adalah sebuah teknik yang bersifat stokastik dan berbasis pada ide-ide evolusi dari seleksi alam dan genetika.

50

Pada dasarnya ada 4 kondisi yang sangat mempengaruhi proses evaluasi, yaitu: •

Kemampuan organisme untuk melakukan reproduksi

•

Keberadaaan populasi organisme yang bisa melakukan reproduksi

•

Keberagaman organisme dalam suatu populasi

•

Perbedaan kemampuan untuk survive Sesuatu yang stokastik adalah sebuah kejadian yang bersifat acak,

dimana munculnya suatu kejadian tidak dapat diramalkan, akan tetapi, jika diukur dari seluruh distribusi observasi, biasanya akan mengikuti sebuah pola. Algoritma Genetika sangat tepat digunakan untuk berbagai macam permasalahan yang kompleks dan sulit diselesaikan dengan metode konvensional. Metode ini dikategorikan sebagai pencari solusi global secara heuristik. AG merupakan metode yang terinspirasi oleh biologi evolusioner seperti kawin silang atau rekombinasi, mutasi, dan seleksi, khususnya pada seleksi, sesuai dengan prinsip-prinsip yang dicetuskan oleh Charles Darwin, yaitu “Survival of the fittest”.

Dikarenakan di alam ini, kompetisi antar

individu untuk sumber daya yang terbatas mengakibatkan individu yang kuatlah yang akan bertahan dan mendominasi yang lemah. Individu yang lebih kuat (fit) akan memiliki tingkat survival dan reproduksi yang lebih tinggi daripada individu yang kurang fit. Pada kurun waktu tertentu, populasi secara keseluruhan akan lebih banyak memuat organisme yang fit.

51

AG diimplementasikan dengan bantuan simulasi komputer dalam sebuah populasi, dimana sebuah solusi, yakni sebuah individu, diwakili secara abstrak oleh apa yang disebut kromosom.

Beberapa cara untuk

menginterpretasikan solusi ke dalam sebuah kromosom, salah satunya adalah secara binary code, yaitu sebuah kromosom yang terdiri dari angka 0 dan 1. Akan tetapi, pemberian kode yang lain juga memungkinkan. Walaupun menggunakan angka acak, AG sama sekali tidak menghasilkan nilai yang acak, sebaliknya mereka menggunakan informasi historis untuk mengarahkan pencarian ke daerah dengan performa yang lebih baik. Perincian proses encoding dan decoding (yaitu proses dimana sebuah solusi dikodekan menjadi sebuah kromosom, dan sebaliknya) tidak dipahami sepenuhnya, namun beberapa teori yang dicetuskan oleh John Holland adalah sebagai berikut: •

Evolusi merupakan sebuah proses yang beroperasi pada kromosom.

•

Seleksi alamiah adalah hubungan antara kromosom dengan performa dari struktur yang dikodekan. Proses seleksi alami menyebabkan kromosom yang lebih baik untuk memiliki kemampuan reproduksi yang lebih baik daripada mereka yang kurang baik.

•

Proses

reproduksi

ialah

titik

dimana

evolusi

berjalan.

Mutasi

menyebabkan kromosom-kromosom menjadi berbeda dari induknya,

52

sedangkan proses kawin silang atau biasa disebut rekombinasi menghasilkan kromosom yang berbeda namun masih membawa sifat dari induknya. •

Evolusi biologis tidak memiliki ingatan, apapun yang diketahui oleh suatu individu terdapat dalam gen dan kromosom yang dibawa oleh individu tersebut.

2.2.2

Terminologi Algoritma Genetika Didalam AG, terdapat banyak sekali istilah yang perlu diketahui. Istilah-istilah ini diambil dari istilah biologis, mengingat kesamaan proses dari AG ini terhadap proses yang terjadi pada makhluk hidup. Adapun beberapa persamaan istilahnya adalah sebagai berikut: Tabel 2.14 Terminologi Algoritma Genetika

Terminologi AG Gen/Locust Chromosome/Phenotype Genotype Parent Offspring Crossover Mutation Fitness

Arti Bit yang ada di dalam sebuah string Susunan dari banyak bit yang membentuk suatu string Parameter atau vektor solusi dari Phenotype Kromosom orang tua Kromosom anak yang dihasilkan oleh proses operasi AG Kawin silang antara kedua kromosom orang tua Mutasi dari sebuah kromosom hingga menghasilkan kromosom yang berbeda Nilai kesesuaian dari sebuah kromosom

53

2.2.3

Struktur Umum Algoritma Genetika Pada algoritma ini, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang mungkin yang dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi dikenal dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan istilah generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak atau biasa disebut offspring, terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk atau biasa disebut parent dengan menggunakan teknik penyilangan atau disebut juga crossover. Selain operator penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru digenbuk dengan cara menyeleksi nilai fitness dari kromosom induk dan nilai fitness dari kromosom anak, serta menolak kromosom-kromosom yang lainnya hingga ukuran populasi akan konstan. Setelah melalui beberapa generasi, maka algoritma ini akan konvergen ke kromosom terbaik.

54

Adapun langkah-langkah dasar Algoritma Genetika adalah: 1. Membangkitkan inisialisasi awal dari populasi secara acak. 2. Mencari kesesuaian fitness dari populasi. 3. Pilih induk dari populasi. 4. Lakukan kawin silang antara induk yang menghasilkan populasi. 5. Lakukan mutasi pada individu dalam populasi. 6. Mencari kesesuaian fitness dari populasi. 7. Buang individu-individu yang kurang baik. 8. Kembali ke no. 3.

2.2.4 2.2.4.1

Komponen-Komponen Utama Algoritma Genetika Teknik Penyandian Teknik penyandian disini meliputi penyandian gen dari kromosom. Gen merupakan bagian dari kromosom. Satu gen biasanya akan 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.

55

Gambar 2.1 Contoh Struktur Data Algoritma Genetika

Demikian juga, kromosom dapat direpresentasikan dengan menggunakan: •

String Bit

: 10011, 01101, 1101, dst

•

Bilangan real

: 65.65, -67.98, 562.88, dst

•

Elemen permutasi

: E2, E10, E5, dst

•

Daftar aturan

: R2, R3, R1, dst

•

Elemen program

: Pemrograman genetika

•

Struktur lainnya

56

2.2.4.2

Inisialisasi Ukuran populasi tergantung pada masalah apa yang akan dipecahkan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut.

Inisialisasi

kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada. Penyelesaian menggunakan Algoritma Genetika membutuhkan dua hal yang harus di definisikan: 1. Sebuah representasi genetika dari solusi dari individu atau kromosom 2. Sebuah fungsi kesesuaian (fitness function) untuk mengevaluasi individu 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 obyek yang dapat

57

dimasukkan ke dalam tas dengan sebuah kapasitas yang tetap. Representasi solusi dapat berupa bits, dimana setiap bit mewakili sebuah objek, dan nilai dari setiap bit yaitu 0 atau 1 mengartikan apakah objek tersebut akan dimasukkan ke dalam tas atau tidak. Tidak setiap saat representasi seperti ini dapat digunakan, dimana ukuran dari objek dapat melebihi ukuran tas. Oleh karena itu diperlukan yang namanya kesesuaian dari solusi, yaitu ialah jumlah nilai dari seluruh objek di dalam tas fisibel, bila tidak maka tidak sesuai. Dalam beberapa permasalahan, bahkan sulit untuk mendefinisikan kesesuaian, dan dalam kasus-kasus seperti ini digunakan Algoritma Genetika interaktif. Setelah

mendefinisikan

representasi

genetika

dan

fungsi

kesesuaian, AG berlanjut untuk menginisialisasi sebuah populasi. Pada awalnya beberapa solusi dari permasalahan yang terkait dikumpulkan secara acak, kelompok solusi ini akan membentuk sebuah populasi. Pada kasus pengurutan pekerjaan pada Job Shop, solusi berupa beberapa urutan kombinasi pekerjaan.

Ukuran populasi bergantung pada sifat dari

permasalahan, tetapi biasanya mengandung banyak sekali solusi yang mungkin diangkat. Secara tradisional, solusi dibangkitkan secara acak, menutupi seluruh jangkauan kemungkinan lingkup penyelesaian (search space).

Namun terkadang, solusi permasalahan dapat dibibitkan pada

bagian-bagian tertentu dimana solusi optimal dapat ditemukan.

58

2.2.4.3

Pemilihan Operator Setelah sebuah populasi awal dibangkitkan, algoritma melewati beberapa operator, yakni:

2.2.4.4

•

Seleksi, yang memberikan hasil kromosom terkuat

•

Genetika, berupa kawin silang (crossover) dan mutasi (mutation)

Operator Seleksi Operator ini memiliki beberapa sifat dasar yaitu: 1. Ide kunci: memberikan preference kepada solusi yang lebih baik, hingga memungkinkan mereka untuk menurunkan gen-gen mereka kepada generasi yang berikutnya 2. Tingkat kebaikan setiap individu bergantung pada kesesuaiannya 3. Kesesuaian dapat ditetapkan oleh sebuah fungsi obyektif atau sebuah penilaian subyektif Pada setiap generasi, sebuah proporsi dari populasi yang ada dipilih untuk menurunkan generasi yang baru. Solusi individu dipilih melalui proses yang berbasis kesesuaian (fitness-based), dimana solusi yang lebih sesuai atau kuat diukur dengan fungsi kesesuaian cenderung lebih mudah untuk terpilih. Beberapa metode seleksi mengukur tingginya kesesuaian dari setiap solusi dan lebih memilih yang terbaik. Beberapa

59

metode lainnya 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 dapat kemungkinan untuk terpilih.

Hal ini dilakukan untuk menjaga

supaya perbedaan populasi tetap besar, yang menghindari konvergensi premature pada solusi yang buruk. Beberapa metode seleksi adalah: 1. Roulette-Wheel Selection 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

kesesuaiannya, seperti pada gambar dibawah.

fungsi

Angka acak

dibangkitkan untuk memilih kromosom. Kromosom yang memiliki kesesuaian lebih besar memiliki probabilitas terpilih yang lebih besar. Kekurangan metode ini ialah bila kromosom terbaik memiliki kesesuaian yang sangat besar dari seluruh roda, maka kromosom lainnya akan memiliki kesempatan yang sangat kecil untuk terpilih.

60

Gambar 2.2 Roulette Wheel Selection

2. Rank-based fitness assignment Pertama

populasi

diurutkan,

lalu

setiap

mendapatkan ranking dari urutan kesesuaiannya.

kromosom Makin besar

kesesuaiannya, maka rankingnya makin baik. Setelah itu dimasukkan ke dalam roda rolet. Bedanya dengan metode roda rolet diatas adalah jika metode roda rolet sebelumnya tidak diurutkan, maka metode rank ini mengurutkan, sehingga roda rolet yang terdapat akan teratur urutannya. Namun metode ini akan menuntun ke konvergensi yang lebih lambat, karena kromosom yang terbaik tidak jauh berbeda dengan yang lain.

Gambar 2.3 Rank-Based Fitness Assignment

61

3. Steady-state selection Bukan merupakan metode seleksi, tetapi tujuan utama dari metode ini ialah sebagian besar dari kromosom harus bertahan ke generasi berikutnya.

Dalam setiap generasi, beberapa kromosom

dengan 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. The Elitism Bila membuat populasi baru dengan persilangan dan mutasi, kita memiliki kesempatan yang besar untuk kehilangan kromosom yang terbaik. Metode ini menyalin beberapa kromosom terbaik ke populasi baru, sisanya dilakukan dengan cara biasa. The Elitism dapat meningkatkan kinerja AG karena menghindari hilangnya solusi terbaik. 5. Tournament Selection Metode ini menjalankan sebuah persaingan diantara beberapa individu yang dipilih secara acak dari populasi dan memilih pemenangnya untuk disilangkan.

62

Tekanan persaingan dapat dirubah dengan mengubah ukuran persaingan.

Jika lebih besar, maka individu yang lebih lemah

memiliki kesempatan yang lebih kecil untuk terpilih.

Kelebihan

metode ini adalah bekekerja pada arsitektur yang berbeda-beda dan mengizinkan tekanan persaingan untuk mudah diubah.

2.2.4.5

Operator Genetika Langkah berikutnya ialah membangkitkan populasi solusi generasi kedua dari mereka yang terpilih dengan menggunakan operator genetika, yaitu persilangan dan mutasi.

Untuk setiap solusi yang dihasilkan,

sepasang solusi induk dipilih untuk member keturunan dari kumpulan yang dipilih sebelumnya. Dengan menghasilkan sebuah solusi turunan menggunakan persilangan dan mutasi, sebuah solusi baru akan muncul yang memiliki sifat-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 member keturunan, bersama dengan mereka yang kurang baik. berdasarkan para ahli:

Beberapa parameter Algoritma Genetika

63

•

Menurut De Jong, untuk permasalahan dengan solusi besar, digunakan Pop; Pc; Pm : 50; 0.6; 0.001

•

Menurut Grefenstette, untuk jika fitness dari individu yang terbaik yang diambil, digunakan Pop; Pc; Pm : 80; 0.45; 0.01

•

Jika rata-rata fitness tiap generasi digunakan sebagai indikator, digunakan Pop; Pc; Pm : 30; 0.95; 0.01 Beberapa dari sekian banyak operator genetika akan dijelaskan di

bawah ini: 1. Crossover a. One Point Crossover (Rekombinasi satu titik) Penyilangan satu titik adalah penyilangan yang terjadi pada gen antara dua invididu kromosom induk setelah satu titik dari kromosom mereka.

Gambar 2.4 One Point Crossover

64

Pada gambar diatas, terlihat bahwa kawin silang terjadi setelah bit ke-5 pada kromosom.

Dimana bit ke 6, 7, 8 dari

kromosom induk saling ditukar, sehingga menghasilkan kromosom anak. b. Two Point Crossover (Rekombinasi dua titik) Rekombinasi dua titik terjadi pada dua titik pada kromosom. Sehingga yang ditukar hanyalah gen-gen yang ada diantara titik-titik tersebut.

Gambar 2.5 Two Point Crossover Pada gambar diatas dapat dilihat bahwa rekombinasi terjadi setelah bit ke – 3 dan sebelum bit ke -7, sehingga yang ditukar hanyalah gen ke 4, 5, dan 6.

65

c. Partially Matched Crossover Pada beberapa kasus, jenis-jenis rekombinasi diatas tidak dapat diaplikasikan, karena kromosom akan menjadi suatu individu yang tidak fisibel.

Sebagai contoh pada kasus TSP

(Travelling Salesman Problem) dan pada kasus Job Sequencing. Jika menggunakan metode diatas, maka akan terjadi pengulangan pada kota-kota atau Job yang diurutkan, sehingga banyak terjadi kromosom yang tidak fisibel. Oleh karena itu, ada suatu metode yang namanya PMX (Partially Matched Crossover).

66

Gambar 2.6 Partially Matched Crossover Pada PMX, pertama-tama dilakukan Two Point Crossover. Setelah itu, setiap gen yang ada diluar zona Two Point Crossover yang memiliki kembaran di dalam area Two Point Crossover, saling ditukarkan antara kromosom orang tua masing masing.

67

Ciri-ciri operator persilangan adalah: •

Faktor cirri utama dari AG dibandingkan dengan teknik optimasi lainnya.

•

Untuk menentukan seberapa banyak dari populasi yang akan disilangkan, ditetapkan sebuah peluang persilangan (crossover probability).

•

Dua individu diambil dari populasi menggunakan operator seleksi untuk menjadi induk dan dikawinkan.

•

Sebuah atau beberapa titik pada kromosom dipilih secara acak, atau menurut aturan.

•

Dua turunan yang dihasilkan dari perkawinan ini dimasukkan ke dalam populasi dari generasi berikutnya.

•

Dengan menggabungkan beberapa bagian dari individu yang baik, proses ini cenderung akan membuat individu yang lebih baik lagi.

2. Mutation Untuk operasi mutasi, hanya satu kromosom yang diseleksi. Penelitian ini menggunakan operator mutasi bernama Order-Based Mutation. Dimana gen-gen didalam kromosom hanya akan ditukar posisinya.

68

Tujuan dari mutasi adalah untuk menjaga keanekaragaman dalam populasi, dan menghindari terjadinya konvergensi premature, atau dikenal juga dengan local optimum.

Gambar 2.7 Order-Based Mutation Menggunakan operator-operator genetika akan memiliki beberapa efek, yakni: •

Menggunakan seleksi saja akan cenderung mengisi populasi dengan salinan dari individu yang terbaik dalam populasi.

•

Menggunakan operator seleksi dan persilangan saja 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 seleksi dan mutasi akan menghasilkan sebuah algoritma yang bersifat parallel, dan hill climbing.

69

2.2.4.6

Terminasi Proses generasional ini diulangi sampai sebuah kondisi terminasi sudah tercapai. Kondisi terminasi yang umum adalah: •

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 ynag rata, sehingga iterasi-iterasi berikutnya tidak lagi menghasilkan nilai yang lebih baik.

2.2.5

•

Inspeksi manual.

•

Kombinasi dari yang diatas.

Kelebihan dan Kekurangan Algoritma Genetika Beberapa kelebihan dari metode ini adalah: •

Proposal atau solusi yang buruk tidak mempengaruhi solusi akhir karena langsung dibuang.

•

Sifat 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.

70

•

Dapat

digunakan

untuk

memberikan

solusi

optimasi

yang

multidimensional. Beberapa kekurangan dari metode ini adalah: •

Tidak selalu menemukan global optimum yang pasti.

•

Karena proses evolusi induktif, pada alam hidup tidak berputar menuju solusi yang baik, tetapi berputar menjauhi yang buruk.

Ini dapat

mengakibatkan sebuah spesies berputar menuju kebuntuan evolusioner.

2.2.6

•

Membutuhkan jumlah evaluasi yang besar dari fungsi kesesuaian.

•

Memerlukan komputer untuk penanganannya.

Simulasi Sederhana Permasalahan Algoritma Genetika Sebuah contoh permasalahan. Carilah sebuah nilai variabel x dan y dengan fungsi x + y = 15. Dengan beberapa parameter AG sebagai berikut: •

Ukuran populasi = 4

•

Crossover probability (Pc) = 0.7

•

Mutation probability (Pm) = 0.1

•

Max Generation = 3

•

Struktur data biner, dengan perincian sebagai berikut: o 0:

0000

o 1:

0001

o 2:

0010

71

•

o 3:

0011

o 4:

0100

o 5:

0101

o 6:

0110

o 7:

0111

o 8:

1000

o 9:

1001

Fungsi kesesuaian ݂ൌ

‫݈݅ݏܽܪ‬ ܶܽ‫ݎܾ݁݉ݑܰݐ݁݃ݎ‬

Selanjutnya, tahapan tahapan dibagi dalam beberapa iterasi / generasi: 1. Generasi 0 (Inisialisasi awal) o Bangkitkan populasi acak Tabel 2.15 Populasi Kromosom pada Generasi 0 Kromosom Genotip 10000101 45 00000001 01 00110101 35 10000000 80 o Seleksi dan kawin silang P1: 10000000 P2: 00110101

Nilai Fitness 9/15 1/15 8/15 8/15

72

One Point Crossover setelah bit ke 3 C1: 10010101 C2: 00100000 o Seleksi dan mutasi P: 00000001 Flip Mutation pada bit ke 4 C: 00010001 o Populasi baru bertambah Tabel 2.16 Total Populasi Kromosom pada Generasi 0 Kromosom Genotip 10000101 45 00000001 01 00110101 35 10000000 80 10010101 95 00100000 40 00010001 11

Nilai Fitness 9/15 1/15 8/15 8/15 14/15 4/15 2/15

o Kromosom-kromosom yang nilai fitnessnya rendah dibuang Tabel 2.17 Populasi Baru Kromosom pada Generasi 0 Kromosom Genotip 10000101 45 00110101 35 10000000 80 10010101 95

Nilai Fitness 9/15 8/15 8/15 14/15

73

2. Generasi 1 o Populasi berdasarkan generasi sebelumnya Tabel 2.18 Populasi Kromosom pada Generasi 1 Kromosom Genotip 10000101 45 00110101 35 10000000 80 10010101 95

Nilai Fitness 9/15 8/15 8/15 14/15

o Seleksi dan kawin silang P1: 00110101 P2: 10000000 One Point Crossover setelah bit ke 4 C1: 00110000 C2: 10000101 o Seleksi dan mutasi P: 10000101 Flip Mutation pada bit ke 7 C: 10000111

74

o Populasi baru bertambah Tabel 2.19 Total Populasi Kromosom pada Generasi 1 Kromosom Genotip 10000101 45 00110101 35 10000000 80 10010101 95 00110000 30 10000101 85 10000111 87

Nilai Fitness 9/15 8/15 8/15 14/15 3/15 13/15 15/15

o Kromosom-kromosom yang nilai fitnessnya rendah dibuang Tabel 2.20 Populasi Baru Kromosom pada Generasi 1 Kromosom Genotip 10000101 45 10010101 95 10000101 85 10000111 87

Nilai Fitness 9/15 14/15 13/15 15/15

o Didapatkan bahwa kromosom yang memiliki nilai kesesuaian paling tinggi adalah kromosom 1000 0111, dengan genotip 8 dan 7. Hal ini berarti nilai X = 8 dan Nilai Y = 7

BAB 2 LANDASAN TEORI

Recommend Documents