Crossover

• Crossover satu titik Crossover satu titik hanya menggunakan satu titik acak sebagai penanda di mana crossover harus terjadi.

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/cross1.png")

• Crossover dua titik Crossover dua titik menggunakan dua titik sebagai penanda di mana setiap kromosom harus membelah dan bergabung dengan kromosom lainnya.

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/cross2.png")

• Crossover tiga poin Crossover dua titik menggunakan tiga titik sebagai penanda di mana setiap kromosom harus membelah dan bergabung dengan kromosom lainnya.

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/cross3.png")

Mutation

• Mutasi Pertukaran yang Berdekatan
  Dua gen yang berdekatan ditukar secara acak.

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/mutasi1.png")

• Mutasi Pertukaran Acak
  Dua gen secara acak bertukar posisi

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/mutasi2.png")

• Mutasi Shift
  Mutasi shift dilakukan dengan reposisi gen secara acak dan menggeser gen berikut setelah posisi tersebut.

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/mutasi3.png")

• Mutasi Terbalik
  Mutasi invers dilakukan dengan mengedver urutan antara dua titik acak.

knitr::include_graphics("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/mutasi4.png")

Production Scheduling

Pertama kita impor datanya. Saya sudah menyiapkan data dummy yang bisa Anda akses di sini.

df_car <- read.csv("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/car_data.csv")

df_car

The objective function will be: \[ 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 pengaturan diperlukan? 1 jika mobil berikutnya (K+1) tidak memiliki warna yang sama dengan mobil ke-k saat ini, 0 jika mobil berikutnya berwarna
  Kami akan menerjemahkan fungsi tujuan menjadi fungsi R dari min_setup. Algoritma dalam paket GA dijalankan dalam konteks maksimisasi, jadi untuk menyelesaikan masalah minimasi, kita akan membuat nilai fitness kita menjadi negatif.

min_setup <- function(x){
  df <- df_car[x, ]
  print(df)
  S <- df %>% 
  mutate(color_next = lead(color),
         setup = if_else(color == color_next, 0, 1)) %>% 
  head(nrow(df)-1) %>% 
  pull("setup") %>% 
  sum() + 1
  S <- -S
  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 fitness yang optimal.

Parameter algoritma:

• type: Jenis pengkodean gen, di sini kita menggunakan “permutasi”
• kebugaran: Fungsi kebugaran yang akan dioptimalkan
• lebih rendah: Nilai terendah dari pengkodean permutasi, kami akan mengkodekan permutasi dari 1 ke jumlah mobil yang tersedia
• atas: Nilai tertinggi dari pengkodean permutasi
• seed: Nilai seed acak untuk mendapatkan hasil yang dapat direproduksi
• elitism : Jumlah solusi terbaik yang akan bertahan di setiap iterasi, default adalah 5% teratas dari populasi, di sini kami menetapkannya menjadi 50 solusi yang akan bertahan
• maxiter: Jumlah iterasi maksimal untuk menjalankan algoritma
• popSize: Jumlah solusi dalam suatu populasi
• run: Jumlah iterasi sebelum algoritma berhenti jika tidak ada perbaikan pada nilai fitness 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             = 91 
## Fitness function value = -6 
## Solutions = 
##       x1 x2 x3 x4 x5 x6 x7 x8 x9 x10  ...  x27 x28
## [1,]  24  4 11 18 16 20  1  8  3  23        14  22
## [2,]   4 24 11 18  3 16 20  1  8  23        14  22
## [3,]   4 11 24 18 16 20  1  8  3  23        14  22
## [4,]   4 11 24 18 20  1  8  3 23  16        14  22
## [5,]   3 16 20  1  2 23  8 27  9  19        11  18
## [6,]   4 24 11 18  3 16 20  1  8  23        22  14
## [7,]   3 16 20  1  2 23  8 27  9  19        11  18
## [8,]  14 22  4 11 24 18  3 16 20   1        15  21
## [9,]   4 11 24 18  3 16 20  1  8  23        14  22
## [10,]  3 16 20  1  2 23  8 27  9  19        11  18
##  ...                                              
## [18,] 11 24  4 18  3 16 20  1  8  23        14  22
## [19,]  4 11 24 18 16 20  1  8 27   3        14  22

toc()

## 96.79 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-67 dan tidak mengalami perbaikan sejak saat itu, sehingga algoritma berhenti setelah 30 iterasi pada iterasi ke-96.

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

min_setup(gann@solution[1, ])

##     X       color
## 24 24        Gray
## 4   4        Gray
## 11 11        Gray
## 18 18        Gray
## 16 16       White
## 20 20       White
## 1   1       White
## 8   8       White
## 3   3       White
## 23 23       White
## 27 27       White
## 2   2       White
## 7   7      Silver
## 28 28      Silver
## 5   5      Silver
## 17 17      Silver
## 26 26      Silver
## 25 25      Silver
## 13 13      Silver
## 10 10      Silver
## 12 12       Black
## 6   6       Black
## 21 21       Black
## 15 15       Black
## 9   9      Orange
## 19 19      Orange
## 14 14 Solid White
## 22 22 Solid White

## [1] -6

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

summary(gann@fitness)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##  -22.00  -16.00  -13.00  -12.43   -8.00   -6.00

Solusi terburuk dalam populasi memiliki nilai fitness 25, sedangkan solusi optimal memiliki nilai fitness 7. Dari seluruh 300 kromosom atau solusi yang dihasilkan, median nilai fitness adalah 15 sedangkan meannya adalah 14,29.

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.

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 Algoritma Genetika. 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 item memiliki jumlah dan berat masing-masing.s

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

The objective function will be: \[ Total Weight= \Sigma_{i=1}^{k} \ W_k*n_k\]

• \(Total Weight\) = Total berat
• \(k\) = Jumlah data unik
• \(W_k\) = berat data k
• \(n_k\)= nomor item k yang dipilih

Batasan:

\[ 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.79 sec elapsed

plot(gann2)

Mari pilih salah satu solusi sebagai pilihan 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)

df_sol

Total berat:

sum(df_sol$total_weigth)

## [1] 10000

Nilai fitness 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.

Import Data

attrition <- read.csv("F:/KEFAS/MATANA UNIVERSITY/SEMESTER 5/OPTIMASI/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

Cross-Validation

Kami membagi data menjadi training set dan testing dataset, dengan 80% data akan digunakan sebagai training set.

Data Preprocessing

Kami akan melakukan preprocess data dengan langkah berikut:

• Upsample untuk meningkatkan jumlah kelas minoritas dan mencegah ketidakseimbangan kelas
• Menskalakan semua variabel numerik
• Hapus variabel numerik dengan varian hampir nol
• Gunakan PCA untuk mengurangi dimensi dengan ambang 90% informasi disimpan
• Hapus variabel over_18 karena hanya memiliki 1 level faktor

Create Fitness Function

Kami akan melatih model menggunakan hutan acak. Kami akan mengoptimalkan nilai mtry (jumlah node di setiap pohon) dan nilai min_n (jumlah minimum anggota di setiap pohon untuk dipecah) dengan memaksimalkan akurasi model pada kumpulan data pengujian. Karena jumlah mtry dan min_n adalah bilangan bulat, lebih baik kita menggunakan encoding biner daripada encoding real-valued.

Kami akan mengatur rentang mtry dari 1 hingga 32. Kami akan membatasi rentang min_n dari 1 hingga 128. Mari kita periksa berapa bit yang kita perlukan untuk menutupi angka-angka itu.

# max value of mtry = 32
2^5

## [1] 32

# max value of min_n = 128
2^7

## [1] 128

Jadi, kita membutuhkan setidaknya 12 bit biner. Jika nilai konversi bit untuk mtry atau min_n adalah 0, kami mengubahnya menjadi 1.

Kami akan menulis model sebagai fungsi kebugaran. Kami akan memaksimalkan akurasi model kami pada dataset pengujian.

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,
  min_n = b,
  trees = 500)

#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)
}

Run the Algorithm

IMPORTANT Karena beberapa model memerlukan banyak waktu untuk dilatih, Anda mungkin perlu ekstra hati-hati dalam memilih ukuran populasi dan jumlah iterasi. Jika Anda tidak memiliki masalah untuk menjalankan GA dalam jangka waktu yang lama, Anda dapat memilih ukuran populasi dan jumlah iterasi yang lebih besar. Di sini saya akan mengatur ukuran populasi menjadi hanya 100 dan jumlah maksimum iterasi adalah 100. Anda dapat menggunakan parallel = TRUE jika Anda ingin komputasi yang lebih cepat dengan komputasi paralel.

Mari kita periksa setiap variabel keputusan dan akurasi yang digunakan sebagai nilai fitness.

Compare with K-fold Cross Validation

Performa model oleh GA lebih baik daripada yang dioptimalkan dengan validasi silang K-fold sederhana, meskipun GA memerlukan lebih banyak waktu untuk menghitung. Pertukaran waktu komputasi vs kinerja ini harus dipertimbangkan.