Optimasi

Tugas 7

Kontak : \(\downarrow\)
Email
Instagram https://www.instagram.com/sherlytaurin/
RPubs https://rpubs.com/sherlytaurin/

1 Pengenalan

1.1 Tentang

Optimasi sangat penting di berbagai macam bidang, termasuk data science. Dalam manufaktur, setiap keputusan sangat penting untuk proses dan keuntungan organisasi, optimasi sering digunakan, dari jumlah setiap produk yang dihasilkan, bagaimana unit dijadwalkan untuk produksi, mendapatkan proses parameter yang terbaik atau optimal, dan juga penentuan rute seperti masalah pengiriman ekspedisi. Dalam data science, kita tidak asing dengan model tuning, yaitu ketika kita menyesuaikan model kita untuk meningkatkan kinerja model. Algoritma optimasi dapat membantu kita untuk mendapatkan kinerja model terbaik. Algoritma Genetik merupakan salah satu yang sering digunakan dalam optimasi.

Artikel ini menjelaskan mekanisme dari salah satu algoritma yang paling efektif untuk masalah optimasi, yaitu Algoritma Genetik (GA). Ada banyak algoritma lainnya untuk masalah optimasi seperti Particle Swarm Optimization (PSO), Simulated Annealing (SA), dan Tabu Search. Akan tetapi, di berbagai area, GA dapat mencapai tujuan terbaik dibanding metode lainnya. Ada beberapa turunan dan variasi dari implementasi GA, salah satunya yang paling terkenal adalah masalah optimasi multi objektif yaitu ketika ingin mengoptimalkan dua tujuan secara bersamaan yang disebut dengan Multi-Objective Evolutionary Algorithm (MOEA). Selanjutnya kita akan mencari tahu bagaimana GA bekerja dan penerapannya, baik di masalah bisnis ataupun data science.

1.2 Tujuan

Tujuan Pembelajaran:

  • Mempelajari pentingnya optimasi dalam bisnis
  • Mempelajari fungsi biaya atau fungsi tujuan dan variabel-variabel keputusan
  • Mempelajari hubungan antara machine learning dan optimasi
  • Mempelajari prinsip dan konsep Algoritma Genetik (GA)
  • Mempelajari implementasi GA dalam masalah bisnis dan data science

1.3 Library and Pengaturan

Untuk menggunakan GA, dapat dilakukan penginstalan package GA menggunakan fungsi install.packages(). Berikut ini merupakan beberapa packages yang akan digunakan.

library(tidyverse)
library(GA)
## Warning: package 'GA' was built under R version 4.1.2
## Warning: package 'foreach' was built under R version 4.1.2
## Warning: package 'iterators' was built under R version 4.1.2
library(ranger)
## Warning: package 'ranger' was built under R version 4.1.2
library(tidymodels)
## Warning: package 'tidymodels' was built under R version 4.1.2
## Warning: package 'dials' was built under R version 4.1.2
## Warning: package 'infer' was built under R version 4.1.2
## Warning: package 'modeldata' was built under R version 4.1.2
## Warning: package 'parsnip' was built under R version 4.1.2
## Warning: package 'recipes' was built under R version 4.1.2
## Warning: package 'rsample' was built under R version 4.1.2
## Warning: package 'tune' was built under R version 4.1.2
## Warning: package 'workflows' was built under R version 4.1.2
## Warning: package 'workflowsets' was built under R version 4.1.2
## Warning: package 'yardstick' was built under R version 4.1.2
library(caret)
## Warning: package 'caret' was built under R version 4.1.2
library(tictoc)
library(themis)
## Warning: package 'themis' was built under R version 4.1.2
library(randomForest)
## Warning: package 'randomForest' was built under R version 4.1.2

2 Masalah Optimasi

2.1 Mengapa Optimasi itu Penting

Misalkan kita memiliki 2 garis produk. Produk A dengan profit 50 USD dan produk B dengan profit 30 USD. Kita ingin memaksimumkan profit. Akan tetapi, bahan yang tersedia terbatas. Kita hanya memiliki waktu 80 jam seminggu, lama produksi produk A mencapai 10 jam, sedangkan produk B mencapai 4 jam. Kedua produk memiliki bahan yang sama dan kita hanya mempunyai 100 meter kain. Produk A membutuhkan 2 meter kain, sedangkan produk B membutuhkan 4 meter kain. Bagaimana kita memutuskan berapa jumlah produk A dan B terbaik yang akan diproduksi? Hal tersebut merupakan masalah optimasi (dalam kasus ini, optimalkan profit).

Bagaimana jika kita memutuskan secara acak memilih jumlah setiap produk yang akan diproduksi. Kita mungkin tidak punya cukup waktu untuk menyelesaikannya dan tidak memiliki cukup bahan, atau sebaliknya kita memiliki bahan yang tersisa.

Kasus lainnya, misalkan kita ingin mengirim produk kita ke beberapa gudang. Bagaimana kita memutuskan gudang mana yang harus dikunjungi pertama kali atau bagaimana kita memutuskan rute mana yang harus dipilih supaya meminimumkan waktu pengiriman?

Optimasi sangatlah penting apalagi dalam situasi bahan yang terbatas. Hal penting lainnya, optimasi memerhatikan profit dan loss, memilih rute pengiriman yang salah akan mengakibatkan keterlambatan pengiriman dan dapat menimbulkan biaya penalti atau merusak produk selama perjalanan. Maka dari itu, optimasi sangat penting dalam bisnis.

2.2 Fungsi Tujuan dan Variabel Keputusan

Setiap masalah optimasi selalu memiliki 2 elemen: fungsi tujuan dan variabel keputusan. Fungsi tujuan berarti bagaimana kita merumuskan tujuan kita, seperti bagaimana kita mengukur keuntungan untuk memaksimalkannya atau bagaimana kita mengukur waktu pengiriman untuk meminimalkannya. Di dalam fungsi tujuan terdapat variabel keputusan, apa yang harus menjadi keputusan kita untuk dapat menghasilkan keuntungan maksimal? Kita ingin memaksimalkan tujuan dengan memilih variabel keputusan yang tepat. Pada contoh sebelumnya, tujuan untuk memaksimalkan keuntungan termasuk dalam fungsi tujuan, sedangkan jumlah produk A dan produk B yang akan diproduksi termasuk dalam variabel keputusan.

Beberapa tujuan mungkin memiliki kendala, seperti jumlah jam kerja seminggu hanya 80 jam atau jumlah bahan yang tersedia hanya 100 meter. Batasan ini penting karena solusi apa pun yang tidak memenuhi batasan adalah solusi yang tidak layak.

2.3 Machine Learning and Optimasi

Machine learning dan optimasi tidak dapat dipisahkan, keduanya saling berkaitan, meskipun tujuannya berbeda. Machine learning berkaitan dengan prediksi atau klasifikasi berdasarkan beberapa prediktor, sedangkan optimasi berkaitan dengan menemukan nilai objektif terbaik berdasarkan pilihan variabel keputusan. Namun, mekanisme di balik sebagian besar model machine learning adalah optimasi. Sebagai contoh, metode gradient descent dari model training Neural Network adalah metode optimasi, dengan tujuan untuk menemukan titik terendah dan konvergen. Contoh lain adalah pemasangan regresi linier, yang meminimalkan jumlah kesalahan kuadrat, sehingga disebut metode Kuadrat Terkecil.

3 Algoritma Genetik: Konsep

3.1 Gambaran Umum

“Algoritma Genetik (GA) merupakan algoritma pencarian stokastik terinspirasi oleh prinsip-prinsip dasar evolusi biologis dan seleksi alam. GA mensimulasikan evolusi organisme hidup, di mana individu yang paling kuat mendominasi yang lebih lemah dengan meniru mekanisme evolusi biologis seperti seleksi, crossover, dan mutasi.”
Luca Scrucca

Algoritma Genetika adalah algoritma optimasi yang menggunakan konsep evolusi melalui seleksi alam. Evolusi melalui seleksi alam, sebagaimana dikemukakan oleh Darwin, adalah mekanisme berapa banyak jenis makhluk hidup yang beradaptasi dengan lingkungannya untuk bertahan hidup, melalui 2 prinsip utama: seleksi alam dan mutasi acak. Algoritma genetika (GA) meminjam konsep dan menggunakannya untuk mendapatkan solusi optimal dengan memilih solusi terbaik atau paling cocok di samping kejadian mutasi yang langka dan acak. Flowchart Algoritma Genetik ditunjukkan di bawah ini:

Algoritma Genetik

  1. Akan ada populasi dari kromosom atau solusi yang dipilih secara acak.
  2. Nilai fitness atau nilai fungsi tujuan dari masing-masing solusi dihitung.
  3. Dari populasi tersebut akan dipilih dua solusi sebagai parent solutions, baik dengan tournament selection atau metode pemilihan lainnya.
  4. Solusi yang dipilih akan disilangkan untuk membuat solusi baru, yang disebut child solutions.
  5. Child solutions dapat berubah karena mutasi acak (kemungkinannya sangat kecil untuk terjadi).
  6. Pada akhir iterasi, populasi baru akan dipilih dari parent solutions atau populasi awal dan child solutions berdasarkan nilai fitness.
  7. Selama kriteria berhenti tidak terpenuhi, biasanya dalam hal jumlah iterasi, algoritma akan terus melakukan iterasi.
  8. Solusi terbaik atau optimal adalah solusi dengan nilai fitness yang optimal.

3.2 Elemen

Terdapat 3 elemen utama GA: Populasi, Kromosom, dan Gen.

Populasi adalah sekelompok individu atau solusi yang disebut kromosom. Kromosom terdiri dari urutan gen, dengan masing-masing atau beberapa gen (tergantung pada pengkodean) mewakili variabel keputusan tunggal yang akan dipasang pada fungsi tujuan.

Populasi, Kromosom, dan Gen

Gen dapat ditampilkan atau pengkodean dengan berbagai macam cara, termasuk:

  • Binary Encoding

Binary encoding artinya gen dikodekan menjadi angka binari, ini merupakan yang pertama dan yang paling sering digunakan dalam GA encoding.

  • Real-Valued Encoding

Real-valued encoding artinya gen dikodekan dalam floating point atau angka desimal. Encoding bernilai nyata dapat digunakan untuk mengoptimalkan parameter proses, karena terdiri dari bilangan floating point dan tidak cocok untuk optimasi berbasis integer.

  • Permutation Encoding

Permutation encoding artinya gen dikodekan ke dalam urutan nomor, setiap nomor secara unik ditugaskan untuk gen sehingga tidak ada 2 gen yang akan memiliki jumlah atau nilai yang sama. Pengkodean ini sering digunakan dalam masalah penjadwalan atau perutean, di mana setiap permutasi mewakili satu lokasi atau titik unik.

3.3 Parents Selection

Parents selections dilakukan untuk memilih dua solusi yang akan digunakan dalam crossover dan menghasilkan solusi baru disebut child solutions. Ada beberapa metode untuk melakukan parents selections:

  • Pairing From Top to Bottom

Metode ini memasangkan kromosom individu teratas dalam populasi dengan individu setelahnya sampai sejumlah individu terpenuhi untuk digunakan dalam proses persilangan. Dengan kata lain, metode ini mengawinkan solusi pada baris ganjil dengan solusi pada baris genap. Metodenya sangat sederhana meskipun tidak memodelkan seleksi alam secara akurat.

  • Random Pairing

Parents dipilih secara acak dengan peluang yang sama untuk dipilih.

  • Weighted Random Pairing (Roulette Selection)

Parents akan dipilih secara acak berdasarkan nilai fitness. Nilai fitness yang lebih tinggi berarti peluang yang lebih tinggi untuk dipilih.

  • Tournament Selection

Tournament selection dilakukan dengan memilih sekumpulan kromosom dari populasi dan membuat kriteria seleksi tertentu. Pemilihan turnamen efektif untuk GA yang memiliki populasi besar karena tidak perlu mengurutkan individu di dalam populasi.

3.4 Crossover and Mutasi

3.4.1 Crossover

Crossover adalah proses perkawinan antara dua individu yang dipilih, proses tersebut mewakili bagaimana gen ditransfer ke keturunannya. Ada beberapa metode crossover:

  • One-point crossover

One-point crossover gunakan hanya satu titik acak sebagai penanda di mana crossover harus terjadi.

  • Two-point crossover

Two-point crossover menggunakan dua titik sebagai penanda dimana setiap kromosom harus berpisah dan bergabung dengan kromosom lainnya.

  • Three-point crossover

Three-point crossover menggunakan tiga titik sebagai penanda di mana setiap kromosom harus berpisah dan bergabung dengan kromosom lainnya.

3.4.2 Mutasi

Mutasi berarti perubahan pada satu atau beberapa gen di dalam kromosom. Seperti halnya di alam, mutasi jarang terjadi, sehingga kemungkinannya kecil untuk terjadi, biasanya ditetapkan pada 0,01. Ada beberapa contoh mutasi:

  • Mutasi Pertukaran Berdekatan

Dua gen yang berdekatan ditukar secara acak.

  • Mutasi Pertukaran Acak

Dua gen secara acak bertukar posisi.

  • Shift Mutation

Shift mutation dilakukan dengan memposisikan ulang gen secara acak dan menggeser gen berikut setelah posisinya.

  • Inverse Mutation

Inverse mutation dilakukan dengan membalik barisan antara dua titik acak.

3.5 Aplikasi

Algoritma Genetika dapat diterapkan pada berbagai masalah bisnis. Karena algoritme adalah tentang pengoptimalan, selama ada fungsi tujuan/kebugaran untuk dioptimalkan, GA dapat diterapkan. Beberapa contoh termasuk penjadwalan produksi, masalah knapsack (berapa banyak/berapa banyak barang yang dapat kita muat di tas atau truk kita untuk memaksimalkan ruang atau beban berat), masalah travelling salesman, dll. GA juga dapat diterapkan di bidang data science, terutama ketika kami melakukan penyetelan hyperparameter untuk mengoptimalkan kinerja model.

4 Genetic Algorithm with R

Pada bagian ini akan diilustrasikan bagaimana GA akan bekerja menggunakan package GA pada permasalahan bisnis dan machine learning hyper-parameter tuning.

4.1 Business Application

4.1.1 Production Scheduling

Misalkan kita memiliki berbagai unit mobil yang akan diproduksi di pabrik kita. Ada 7 jenis warna produk yang berbeda. Jika unit berikut memiliki warna yang berbeda dari mobil sebelumnya, maka akan ada biaya changeover (biaya yang timbul karena perubahan jenis produk), seperti biaya material yang dibutuhkan untuk membersihkan peralatan dari warna cat sebelumnya. Ada banyak cara untuk mengoptimalkan urutan warna, tetapi kami akan menggunakan yang paling sederhana di sini. Kami ingin meminimalkan jumlah setup, membuat jumlah pergantian warna atau pergantian terjadi lebih sedikit, sehingga biaya pergantian juga dapat diminimalkan.

Pertama kita impor datanya. Telah disiapkan data dummy yang bisa Anda akses di sini.

df_car <- read.csv("data/car_data.csv")

df_car

Fungsi objektifnya adalah: \[ S = 1 + \Sigma_{k=2}^{DT} \ S_k\]

  • \(S\) = jumlah pengaturan
  • \(D_T\) = Jumlah mobil/unit yang akan diproduksi
  • \(k\) = Posisi mobil dalam barisan
  • \(S_k\) = Apakah diperlukan penyiapan? 1 jika mobil berikutnya (\(K+1\)) tidak memiliki warna yang sama dengan mobil \(k^{th}\) saat ini, 0 jika mobil berikutnya memiliki warna yang sama

Kita akan mengubah fungsi objektif tersebut ke bentuk R dengan nama min_setup. Algoritma pada package GA bekerja pada kasus maksimisasi, untuk itu dalam kasus minimisasi, kita akan membuat nilai fitnya negatif.

min_setup <- function(x) {
    df <- df_car[x, ]
    for (i in 1:(nrow(df_car) - 1)) {
        df$s[i] <- if_else(df$color[i] == df$color[i + 1], 0, 1)
    }
    S = -(1 + sum(df$s, na.rm = T))
    return(S)
}

Sekarang kita jalankan algoritmanya. Karena masalahnya adalah masalah penjadwalan, kami akan mengkodekan solusi kami dengan pengkodean permutasi. Kami akan menghentikan algoritma jika jumlah iterasi telah mencapai 1000 iterasi atau jika dalam 100 iterasi tidak ada peningkatan nilai fit yang optimal.

IMPORTANT Pemilihan ukuran populasi dan jumlah iterasi akan sangat mempengaruhi kinerja GA. Jika ukuran populasi terlalu kecil, akan ada gene pool yang terbatas dalam populasi sehingga solusi baru tidak akan terlalu berbeda jauh dari generasi sebelumnya. Jika jumlah iterasi terlalu sedikit, tidak akan ada cukup waktu bagi algoritma untuk menemukan solusi optimal baru. Paket GA dapat dijalankan dengan komputasi paralel.

Parameter pada Algoritma:

type: Jenis pengkodean gen, di sini kita menggunakan “permutasi” fitness: Fungsi kebugaran yang akan dioptimalkan lower: Nilai terendah dari pengkodean permutasi, kami akan mengkodekan permutasi dari 1 ke jumlah mobil yang tersedia upper: Nilai tertinggi dari pengkodean permutasi seed: Nilai seed acak untuk mendapatkan hasil yang dapat direproduksi elitisme: Jumlah solusi terbaik yang akan bertahan di setiap iterasi, defaultnya adalah 5% teratas dari populasi, di sini kami menetapkannya menjadi 50 solusi yang akan bertahan maxiter: Jumlah iterasi maksimal untuk menjalankan algoritme popSize: Jumlah solusi dalam suatu populasi run: Jumlah iterasi sebelum algoritma berhenti jika tidak ada perbaikan pada nilai fitness yang optimal paralel: Apakah kita akan menggunakan komputasi paralel? Dapat berupa nilai logika atau jumlah inti yang digunakan

Parameter lainnya, seperti probabilitas crossover dan mutasi diserahkan ke pengaturan default.

tic()
gann <- ga(type = "permutation", fitness =      min_setup, lower = 1, upper = nrow(df_car), 
    seed = 123, elitism = 50, maxiter = 300, popSize = 300, run = 30, parallel = parallel::detectCores())

summary(gann)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  permutation 
## Population size       =  300 
## Number of generations =  300 
## Elitism               =  50 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## 
## GA results: 
## Iterations             = 101 
## Fitness function value = -7 
## Solutions = 
##       x1 x2 x3 x4 x5 x6 x7 x8 x9 x10  ...  x27 x28
## [1,]   4 24 11 18 22 14 19  9  6  12        10  17
## [2,]   6 12 21 15 19  7 17 10 28   5        14   9
## [3,]  22 14  4 24 11 18 19  9  6  12         3  17
## [4,]  22 14  4 24 11 18 19  9  6  12         3  17
## [5,]  21 12  4 24 11 18 19  9  7  26        15   6
## [6,]   4 24 11 18 22 14 19  9  6  12         3  17
## [7,]   1  3 19  9  6 15 21 12 18  11         8  20
## [8,]  10  7 17  4 24 11 18  6 12  21        22  14
## [9,]   4 11 18 24 19  9  6 12 21  15        22  14
## [10,] 22 14 24 18 11  4 13 28  7  25        10  26
##  ...                                              
## [27,] 27 23 20  3  2  8  1 16 18  22        24   4
## [28,]  4 24 11 18 22 14 19  9  6  12         2  17
toc()
## 57.38 sec elapsed

Kita dapat memplot perkembangan algoritma dengan menggunakan fungsi plot() pada objek GA.

plot(gann)

Solusi terbaik atau optimal diperoleh setidaknya pada iterasi ke-72 dan tidak mengalami perbaikan sejak saat itu, sehingga algoritma berhenti setelah 30 iterasi pada iterasi ke-101.

Hasil dari Solution adalah solusi yang menghasilkan nilai fit yang optimal. Kita dapat memilih salah satunya karena akan menghasilkan nilai fitness yang sama. Mari kita periksa salah satunya.

min_setup(gann@solution[1, ])
## [1] -7

Jika ingin melihat semua nilai fit dari populasi terakhir, gunakan bisa menggunakan atribut fitness dari objek GA. Kami akan meringkas nilai fit untuk mendapatkan distribusinya.

summary(gann@fitness)
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##  -24.00  -17.00  -13.00  -13.37  -10.00   -7.00

Solusi terburuk dalam populasi memiliki nilai fit 24, sedangkan solusi optimal memiliki nilai fitness 7. Dari seluruh 300 kromosom atau solusi yang dihasilkan, median nilai fitness adalah 13 sedangkan meannya adalah 13.37.

Mari kita menempatkan urutan optimal untuk data kita. Data frame yang dihasilkan akan menjadi jadwal produksi kita. Karena ada banyak solusi, mari kita lihat dua solusi optimal pertama.

Solusi pertama:

df_car[gann@solution[1, ], ]

Solusi kedua:

df_car[gann@solution[2, ], ]

Meskipun solusi pertama dan solusi kedua memiliki urutan yang berbeda, fungsi fitness atau jumlah setup adalah sama, oleh karena itu keduanya merupakan solusi optimal dan keputusan untuk memilih mana yang harus digunakan sebenarnya diserahkan kepada pengambil keputusan. , dalam hal ini, staf kontrol produksi.

4.1.2 Knapsack Problem

Misalkan kita memiliki beberapa item untuk dikirim ke pusat distribusi. Namun, truk kami hanya dapat memuat hingga total 10 ton atau 10.000 kg, jadi kami harus memilih barang mana yang akan dikirim dan memaksimalkan berat yang dimuat. Anda dapat langsung menyelesaikan masalah ini menggunakan Metode Knapsack, tetapi Anda juga dapat menggunakan Genetic Algorithm. Di sini kita akan melihat bagaimana GA menangani masalah yang dibatasi (berat tidak boleh melebihi 10 ton atau 10.000 kg).

df_item <- data.frame(item = c("Tires", "Bumper", "Engine", "Chasis", "Seat"), freq = c(80, 
    50, 70, 50, 70), weight = c(7, 17, 158, 100, 30))

df_item

Setiap barang memiliki jumlah dan beratnya masing-masing.

Mari kita buat dataset baru dengan satu observasi yang sesuai dengan hanya 1 item.

df_item_long <- df_item[rep(rownames(df_item), df_item$freq), c(1, 3)]

df_item_long

Mari mengatur fungsi objektifnya

\[Total\ Weight = \Sigma_{i=1}^{k} \ W_k \ * \ n_k \]

  • \(Total\ Weight\): Berat total (kg)
  • \(k\): Jumlah item unik
  • \(W_k\): Berat barang k
  • \(n_k\): Jumlah item k yang dipilih

Dibatasi untuk:

\[Total\ Weight <= 10000\]

weightlimit <- 10000

evalFunc <- function(x) {
    df <- df_item_long[x == 1, ]
    total_weight <- sum(df$weight)
    total_weight <- if_else(total_weight > weightlimit, 0, total_weight)
    return(total_weight)
}

Mari kita jalankan algoritmanya. Kami akan menggunakan pengkodean biner karena variabel keputusan bernilai integer. Setiap bit mewakili nilai logis tunggal apakah item tersebut dipilih.

tic()
gann2 <- ga(type = "binary", fitness = evalFunc, popSize = 100, maxiter = 100, run = 20, 
    nBits = nrow(df_item_long), seed = 123)

summary(gann2)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  binary 
## Population size       =  100 
## Number of generations =  100 
## Elitism               =  5 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## 
## GA results: 
## Iterations             = 22 
## Fitness function value = 10000 
## Solutions = 
##      x1 x2 x3 x4 x5 x6 x7 x8 x9 x10  ...  x319 x320
## [1,]  1  1  0  1  1  1  1  0  1   1          0    1
## [2,]  1  1  0  1  1  1  1  0  1   1          1    1
## [3,]  0  1  1  1  1  0  0  1  1   0          0    0
## [4,]  1  1  0  1  1  1  1  0  1   1          1    1
## [5,]  1  1  0  1  1  1  1  0  1   1          1    0
toc()
## 0.59 sec elapsed

Mari mengecek plotnya

plot(gann2)

Mari memilih satu solusi sebagai solusi yang optimal.

df_sol <- df_item_long[gann2@solution[1, ] == 1, ]

df_sol <- df_sol %>% group_by(item, weight) %>% summarise(freq = n()) %>% mutate(total_weigth = freq * 
    weight)
## `summarise()` has grouped output by 'item'. You can override using the `.groups` argument.
df_sol

Mari mengecek berat totalnya

sum(df_sol$total_weigth)
## [1] 10000

Nilai fit yang optimal sama dengan constrainnya, sehingga kita dapat memuat kendaraan secara penuh sesuai dengan kapasitas maksimumnya.

Penerapan GA di berbagai bidang masih banyak, terutama dalam proses manufaktur dan engineering. Selama ada fungsi fitness dan variabel keputusan, GA dapat diterapkan terhadap masalah tersebut.

4.2 Hyper-Parameter Tuning on Machine Learning Model

Sekarang, kita akan mencoba untuk menerapkan untuk mengoptimasi model machine learning kita. Kita akan menggunakan dataset attrition.

4.2.1 Import Data

attrition <- read.csv("data/attrition.csv")

attrition <- attrition %>% mutate(job_involvement = as.factor(job_involvement), education = as.factor(education), 
    environment_satisfaction = as.factor(environment_satisfaction), performance_rating = as.factor(performance_rating), 
    relationship_satisfaction = as.factor(relationship_satisfaction), work_life_balance = as.factor(work_life_balance))

attrition

4.2.2 Cross-Validation

Kita membagi data kita menjadi data train dan data test dengan proporsi 80% data akan digunakan sebagai data train

set.seed(123)
intrain <- initial_split(attrition, prop = 0.8, strata = "attrition")

intrain
## <Analysis/Assess/Total>
## <1175/295/1470>

4.2.3 Data Preprocessing

Kita akan melakukan preprocessing data dengan langkah-langkah berikut: * Upsample untuk mengingkatkan jumlah dari kelas minoritas dan mencegah terjadinya ketidakseimbangan kelas * Mengukur semua vairabel numerik * Menghapus variabel numerik yang memiliki varians mendekati 0 * Menggunakan PCA untuk mengunrangi dimensi dengan batas 90% informasi data tetap. * Menghapus variabel over_18 karena hanya memiliki 1 tingkatan faktor

rec <- recipe(attrition ~ ., data = training(intrain)) %>% themis::step_upsample(attrition) %>% 
    step_scale(all_numeric()) %>% step_nzv(all_numeric()) %>% step_pca(all_numeric(), 
    threshold = 0.9) %>% step_rm(over_18) %>% prep()

data_train <- juice(rec)
data_test <- bake(rec, testing(intrain))

data_train

Kita akan meng-train model menggunakan random forest. Kita akan mengoptimasi nilai mtry(jumlah node untuk setiap tree) dan min_m (nilai minimum anggota pada masing-masing tree dalam urutan untuk dipisahkan) dengan memaksimalkan akurasi model pada data test. Karena nilai dari mtry dan min_n adalah integer, maka lebih baik kita gunakan binary dibanging nilai biasa.

Kita akan mengatur jarak dari mtry dari 1 sampai 32. Kita akan membatasi jarak dari min_n dari 1 sampai 128. Sekarang, mari kita check berapa banyak bit yang kita butuhkan untuk menutupi angka-angka tersebut.

# nilai maksimim dari mtry = 32
2^5
## [1] 32
# nilai maksimim dari min_n = 128
2^7
## [1] 128

Jadi, diperlukasn setidaknya 12 bit binary. Jika nilai bit yang sudah diconvert dari mtry atau min_n adalah 0, kita akan mengubahnya menjadi 1

Kita akan menulis model sebagai fungsi kecocokan. Kita akan memaksimalkan akurasi dari model dataset testing.

fit_function <- function(x) {
    a <- binary2decimal(x[1:5])
    b <- binary2decimal(x[6:12])
    
    if (a == 0) {
        a <- 1
    }
    if (b == 0) {
        b <- 1
    }
    if (a > 17) {
        a <- 17
    }
    
    # define model spec
    model_spec <- rand_forest(mode = "classification", mtry = a, trees = 500, min_n = b)
    
    # define model engine
    model_spec <- set_engine(model_spec, engine = "ranger", seed = 123, num.threads = parallel::detectCores(), 
        importance = "impurity")
    
    # model fitting
    set.seed(123)
    model <- fit_xy(object = model_spec, x = select(data_train, -attrition), y = select(data_train, 
        attrition))
    
    pred_test <- predict(model, new_data = data_test %>% select(-attrition))
    acc <- accuracy_vec(truth = data_test$attrition, estimate = pred_test$.pred_class)
    return(acc)
}

IMPORTANT Karena beberapa model membutuhkan waktu yang banyak untuk di-train, Anda mungkin harus cukup hati-hati dengan memilih ukuran populasi dan jumlah iterasi. Jika Anda tidak memiliki masalah untuk menjalankan Genetic Algorithm dalam waktu panjang, maka Anda mungkin memilih ukuran populasi dan jumlah iterasi yang lebih tinggi. Disini, saya memilih untuk mengatur ukuran populasi saya hanya menjadi 100 dan jumlah iterasi menjadi 100. Anda dapat menggunakan parallel = TRUE jika Anda menginginkan perhitungan yang lebih cepat dengan perhitungan parallel.

Ada beberapa pilihan yang dapat digunakan untuk masing-masing proses Genetic Algoritm. Sebagai contoh, Misalnya, pemilihan default Genetic Algorithm untuk biner adalah linear rank selection. Detail untuk metode default yang digunakan untuk masing-masing langkah dapat dilihat di :
https://www.rdocumentation.org/packages/GA/versions/3.2/topics/gaControl.
Disini, kita akan mencoba menggunakan metode tournament selection dibandingkan defaultnya, yaitu linear rank selection.

tic()
ga_rf <- ga(type = "binary", fitness = fit_function, nBits = 12, seed = 123, popSize = 100, 
    maxiter = 100, run = 10, parallel = T, selection = gabin_tourSelection)
summary(ga_rf)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  binary 
## Population size       =  100 
## Number of generations =  100 
## Elitism               =  5 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## 
## GA results: 
## Iterations             = 13 
## Fitness function value = 0.8576271 
## Solution = 
##      x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12
## [1,]  0  0  1  0  0  0  0  0  1   1   0   1
toc()
## 519.31 sec elapsed

Mari kita plot proses dari Genetic Algorithm

plot(ga_rf)

Mari kita cek keputusan untuk setiap variable dahn akurasi yang digunakan untuk nilai kecocokan.

ga_rf_pop <- as.data.frame(ga_rf@population)

# Mengubah bariabel keputusan menjadi mtry dan min_n
ga_mtry <- apply(ga_rf_pop[, 1:5], 1, binary2decimal)
ga_min_n <- apply(ga_rf_pop[, 6:12], 1, binary2decimal)

# Menunjukan list dari solusi untuk populasi akhir
data.frame(mtry = ga_mtry, min_n = ga_min_n, accuracy = ga_rf@fitness) %>% mutate(mtry = ifelse(mtry == 
    0, 1, mtry), min_n = ifelse(min_n == 0, 1, min_n), mtry = ifelse(mtry > 17, 17, 
    mtry)) %>% distinct() %>% arrange(desc(accuracy))

Anda mungkin ingin membandingkan waktu perhitungan dari Genetic Algorithim dengan K-Fold cross validation secara berulang menggunakan package caret. Kita akan menggunakan k=5 dan 10 kali pengulangan.

tic()
set.seed(123)
ctrl <- trainControl(method = "repeatedcv", number = 5, repeats = 10)
attrition_forest <- train(attrition ~ ., data = data_train, method = "rf", trControl = ctrl)
toc()
## 761.18 sec elapsed
attrition_forest
## Random Forest 
## 
## 1972 samples
##   17 predictor
##    2 classes: 'no', 'yes' 
## 
## No pre-processing
## Resampling: Cross-Validated (5 fold, repeated 10 times) 
## Summary of sample sizes: 1578, 1577, 1577, 1578, 1578, 1577, ... 
## Resampling results across tuning parameters:
## 
##   mtry  Accuracy   Kappa    
##    2    0.9513710  0.9027417
##   22    0.9646545  0.9293085
##   42    0.9578604  0.9157203
## 
## Accuracy was used to select the optimal model using the largest value.
## The final value used for the model was mtry = 22.

Mari kita cek akurasi dari random forest dengan caret

pred_rf <- predict(attrition_forest, newdata = data_test)
accuracy_vec(truth = data_test$attrition, estimate = pred_rf)
## [1] 0.820339

Performa model oleh Genetic Algorithm lebih baik daripada yang dioptimalkan dengan simple cross validation K-fold, meskipun Genetic Algorithm memerlukan lebih banyak waktu untuk menghitung. Pertukaran waktu komputasi vs kinerja ini harus dipertimbangkan.

5 Conclusion

Permasalahan optimasi adalah satu dari banyak hal dalam bisnis, dimana hal yang dapat memaksimalkan keuntungan dan meminimalkan kerugian. Machin learning menerapkan optimisasi dengan metode mereka dengan meng-train data untuk mendapatkan hasil terbaik. Genetic Algorithm adalah algoritma optimasi yang dapat digunakan di berbagai macam bidang, termasuk data science. Jika seorang data scientist dapat memanfaatkan keuntungan dari Genetic Algorithm, dia bisa mendapatkan model yang lebih optimal dengan performa yang lebih baik. Kelemahan dari Genetic Algorithm adalah algoritma ini memerlukat waktu yang lama untuk menghitung karena ini termasuk salah satu kelompok dari search algorithm

6 Reference

Luca Scrucca. A quick tour of GA. http://luca-scr.github.io/GA/articles/GA.html
Luca Scrucca. 2013. GA: A Package for Genetic Algorithms in R. Journal of Statistical Software, 3(4).
Rohit Ghandi. Genetic Algorithms. https://medium.com/datadriveninvestor/genetic-algorithms-9f920939f7cc
Nearchou, A. C. 2004. The Effect of Various Operators on The Genetic Search for Large Scheduling Problems. International Journal of productions Economics, 88, 191-203.