Penerapan algoritma genetika multi-tujuan (MOGA) untuk masalah penjadwalan produksi sepatu akan melibatkan pengoptimalan beberapa tujuan yang saling bertentangan, seperti:
Meminimalkan waktu produksi: Untuk memastikan sepatu diproduksi secepat mungkin.
Memaksimalkan kualitas produk : Untuk memastikan bahwa sepatu yang diproduksi memiliki kualitas terbaik.
Meminimalkan biaya produksi: Untuk memastikan bahwa biaya produksi setiap pasang sepatu serendah mungkin.
Memaksimalkan kepuasan pelanggan: Untuk memastikan bahwa sepatu memenuhi permintaan dan preferensi pelanggan.
MOGA akan bekerja sebagai berikut:
Langkah 1: Enkodekan Jadwal Produksi
Setiap solusi potensial (yaitu, jadwal produksi sepatu) dikodekan sebagai “kromosom” – serangkaian angka atau simbol lainnya. Dalam hal ini, sebuah kromosom mungkin menentukan urutan jenis sepatu berbeda yang akan diproduksi, mesin atau pekerja yang akan digunakan untuk setiap pekerjaan, dan seterusnya.
Langkah 2: Populasi Awal
Satu set solusi potensial, atau “populasi”, dihasilkan secara acak. Setiap anggota populasi ini mewakili jadwal produksi yang mungkin.
Langkah 3: Fungsi Kebugaran
Kesesuaian setiap solusi dihitung menggunakan fungsi yang menggabungkan semua tujuan. Karena tujuannya bertentangan, beberapa bentuk kompromi atau jumlah tertimbang perlu digunakan. Misalnya, Anda dapat memutuskan bahwa biaya produksi dua kali lebih penting daripada tujuan lainnya, sehingga mendapat bobot 0,5, sedangkan yang lain masing-masing mendapat bobot 0,25. Ini akan menghasilkan nilai kebugaran tunggal untuk setiap solusi.
Langkah 4: Seleksi
Solusi dipilih secara acak untuk menjadi orang tua dari generasi berikutnya. Solusi dengan fitness yang lebih tinggi memiliki kesempatan yang lebih tinggi untuk dipilih.
Langkah 5: Crossover dan Mutasi
Pasangan solusi induk digabungkan untuk menghasilkan solusi anak, dengan menukar bagian kromosomnya. Ini adalah operasi silang. Selain itu, beberapa bagian kromosom dapat diubah secara acak. Ini adalah operasi mutasi.
Langkah 6: Penggantian
Beberapa atau semua populasi lama digantikan oleh solusi anak yang baru. Hal ini dapat dilakukan hanya dengan mengganti populasi lama dengan yang baru, atau dengan memilih solusi terbaik dari kedua populasi.
Langkah 7: Ulangi Langkah 3-6
Langkah 3-6 diulang untuk beberapa generasi. Harapannya adalah setiap generasi akan lebih baik (yaitu, memiliki kebugaran yang lebih tinggi) daripada generasi sebelumnya.
Ini adalah ikhtisar yang disederhanakan, dan dalam praktiknya, lebih banyak detail perlu dipertimbangkan. Misalnya, bagaimana menangani kendala (misalnya, kapasitas atau ketersediaan mesin), bagaimana memilih bobot dalam fungsi kebugaran, bagaimana memilih ukuran populasi dan jumlah generasi, dan sebagainya. Tapi mudah-mudahan, ini memberi Anda gambaran tentang bagaimana algoritma genetika multi-objektif dapat diterapkan pada masalah penjadwalan produksi sepatu.
Sebagai contoh, kita bisa menganggap ada 3 jenis sepatu (A, B, C) yang harus diproduksi dalam sebuah pabrik. Setiap jenis sepatu memiliki waktu produksi, biaya produksi, dan tingkat kepuasan pelanggan yang berbeda-beda. Data tersebut dapat kita simbolkan dalam bentuk tabel berikut:
| Jenis Sepatu |
Waktu Produksi (jam) |
Biaya Produksi (dolar) |
Tingkat Kepuasan Pelanggan |
| A |
2 |
5 |
9 |
| B |
3 |
7 |
8 |
| C |
1 |
4 |
7 |
Tugas kita adalah mencari jadwal produksi yang optimal, di mana kita bisa memproduksi sepatu dengan waktu, biaya, dan tingkat kepuasan pelanggan yang seimbang.
Contoh sebuah solusi (jadwal produksi) mungkin adalah: [A, B, B, C, A, C, B, A], yang berarti kita memproduksi sepatu jenis A terlebih dahulu, diikuti oleh dua sepatu jenis B, dan seterusnya. Solusi ini bisa kita representasikan sebagai sebuah kromosom dalam algoritma genetik.
Jumlah solusi yang mungkin sangat banyak, tergantung pada jumlah sepatu yang perlu diproduksi dan jumlah mesin atau pekerja yang tersedia. Algoritma genetik akan mencoba berbagai solusi, dan berusaha mencari yang terbaik melalui proses seleksi, persilangan (crossover), dan mutasi.
Misalkan kita memiliki stok bahan baku untuk membuat 4 sepatu jenis A, 2 sepatu jenis B, dan 3 sepatu jenis C. Misalkan juga bahwa kita ingin memproduksi 5 sepatu secara total.
Pertama, kita perlu membuat populasi awal. Misalkan kita memilih ukuran populasi 4, maka kita mungkin mempunyai populasi awal seperti ini:
- [A, A, B, B, C]
- [B, B, A, C, C]
- [C, C, C, A, A]
- [B, C, A, A, B]
Kemudian, kita perlu menentukan fitness setiap individu dalam populasi. Misalkan kita menentukan fitness sebagai jumlah waktu produksi, biaya produksi, dan kepuasan pelanggan (semakin tinggi semakin baik).
- [A, A, B, B, C] -> (2+2+3+3+1, 5+5+7+7+4, 9+9+8+8+7) = (11 jam, 28 dolar, 41 skor)
- [B, B, A, C, C] -> (3+3+2+1+1, 7+7+5+4+4, 8+8+9+7+7) = (10 jam, 27 dolar, 39 skor)
- [C, C, C, A, A] -> (1+1+1+2+2, 4+4+4+5+5, 7+7+7+9+9) = (7 jam, 22 dolar, 39 skor)
- [B, C, A, A, B] -> (3+1+2+2+3, 7+4+5+5+7, 8+7+9+9+8) = (11 jam, 28 dolar, 41 skor)
Misalkan kita memilih dua individu dengan fitness terbaik (dalam hal ini, [A, A, B, B, C] dan [B, C, A, A, B]) untuk persilangan (crossover). Misalkan kita menggunakan crossover satu titik, di mana kita memilih titik acak di kromosom dan menukar semua elemen setelah titik tersebut. Misalkan kita memilih titik ke-3, maka kita mendapatkan dua anak baru:
- [A, A, B, A, B]
- [B, C, A, B, C]
Setelah itu, kita perlu melakukan mutasi. Misalkan kita memilih untuk mengubah jenis sepatu pertama dalam kromosom anak pertama dan jenis sepatu terakhir dalam kromosom anak kedua. Kita mendapatkan dua anak mutan:
- [B, A, B, A, B]
- [B, C, A, B, A]
Akhirnya, kita memilih individu terbaik dari populasi awal dan anak-anak untuk membentuk generasi baru. Misalkan kita memilih individu dengan fitness terbaik berdasarkan biaya produksi yang lebih rendah dan skor kepuasan pelanggan yang lebih tinggi:
- [A, A, B, B, C]
- [B, A, B, A, B]
- [B, C, A, B, A]
- [C, C, C, A, A]
Dan begitulah satu iterasi dari MOGA. Proses ini diulangi sebanyak yang diinginkan atau sampai kondisi berhenti terpenuhi (misalnya, jumlah generasi yang ditentukan atau ketika tidak ada peningkatan yang signifikan dalam fitness).
Perhatikan bahwa dalam contoh ini kita tidak memperhatikan batasan stok bahan baku. Untuk memasukkan batasan ini, kita bisa memodifikasi fungsi fitness kita untuk memberikan penalti kepada solusi yang melanggar batasan, atau kita bisa memastikan bahwa operasi crossover dan mutasi kita selalu menghasilkan solusi yang mematuhi batasan.
contoh Kode Program dalam Bahasa Python :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
import random
# Data produk
produk = {
'A': {'waktu': 2, 'biaya': 5, 'kepuasan': 9, 'stok': 100},
'B': {'waktu': 3, 'biaya': 7, 'kepuasan': 8, 'stok': 150},
'C': {'waktu': 1, 'biaya': 4, 'kepuasan': 7, 'stok': 200}
}
# Parameter algoritma
ukuran_populasi = 20
panjang_kromosom = 5
jumlah_generasi = 100
probabilitas_crossover = 0.8
probabilitas_mutasi = 0.1
# Fungsi fitness
def hitung_fitness(individu):
total_waktu = 0
total_biaya = 0
total_kepuasan = 0
for i in individu:
total_waktu += produk[i]['waktu']
total_biaya += produk[i]['biaya']
total_kepuasan += produk[i]['kepuasan']
return total_waktu, total_biaya, total_kepuasan
# Membuat populasi awal
populasi = [[random.choice(list(produk.keys())) for _ in range(panjang_kromosom)] for _ in range(ukuran_populasi)]
for _ in range(jumlah_generasi):
# Seleksi
fitness = [hitung_fitness(individu) for individu in populasi]
fitness = [sum(x) for x in fitness] # Menggabungkan tiga objektif menjadi satu
total_fitness = sum(fitness)
probabilitas_seleksi = [f/total_fitness for f in fitness]
individu_terpilih = random.choices(populasi, weights=probabilitas_seleksi, k=ukuran_populasi)
# Crossover
anak = []
for i in range(0, ukuran_populasi, 2):
individu1 = individu_terpilih[i]
individu2 = individu_terpilih[i+1]
if random.random() < probabilitas_crossover:
titik_crossover = random.randint(1, panjang_kromosom-1)
anak1 = individu1[:titik_crossover] + individu2[titik_crossover:]
anak2 = individu2[:titik_crossover] + individu1[titik_crossover:]
else:
anak1 = individu1
anak2 = individu2
anak.append(anak1)
anak.append(anak2)
# Mutasi
for individu in anak:
for i in range(panjang_kromosom):
if random.random() < probabilitas_mutasi:
individu[i] = random.choice(list(produk.keys()))
# Penggantian generasi
populasi = anak
# Cetak individu terbaik
fitness = [hitung_fitness(individu) for individu in populasi]
individu_terbaik = populasi[fitness.index(max(fitness))]
print('Individu terbaik:', individu_terbaik)
print('Fitness:', hitung_fitness(individu_terbaik))
|
Hasil Program :
1
2
|
Individu terbaik: ['A', 'B', 'B', 'B', 'B']
Fitness: (14, 33, 41)
|
