Optimasi
~ Assignment Week 14 ~
Introduction
About
Optimasi penting dalam banyak bidang, termasuk dalam ilmu data. Dalam manufaktur, di mana setiap keputusan sangat penting untuk proses dan keuntungan organisasi, optimasi sering digunakan, mulai dari jumlah setiap produk yang dihasilkan, bagaimana unit dijadwalkan untuk produksi, mendapatkan parameter proses terbaik atau optimal, dan juga perutean. penentuan seperti masalah salesman keliling. Dalam ilmu data, kami akrab dengan penyetelan model, di mana kami menyetel model kami untuk meningkatkan kinerja model. Algoritma optimasi dapat membantu kita untuk mendapatkan performa model yang lebih baik. Algoritma Genetika (GA) merupakan salah satu algoritma optimasi yang banyak digunakan.
Artikel ini mencoba menjelaskan mekanisme di balik salah satu algoritma yang paling efektif untuk masalah optimasi: Algoritma Genetika (GA). Ada banyak algoritma yang khusus dibuat untuk optimasi, seperti Particle Swarm Optimization (PSO), Simulated Annealing (SA), dan Tabu Search. Namun, di banyak bidang, GA dapat mencapai tujuan lebih baik daripada metode tersebut. Ada berbagai turunan dan variasi implementasi GA, mungkin yang paling terkenal adalah implementasi GA dalam masalah optimasi multiobjective, di mana kita ingin mengoptimalkan dua tujuan secara bersamaan, yang disebut Multi Objective Evolutionary Algorithm (MOEA). Kita akan melihat bagaimana GA umum bekerja dan di mana itu dapat diterapkan, baik pada masalah bisnis maupun di bidang ilmu data.
Objectives
Tujuan Pembelajaran:
- Pelajari pentingnya optimasi dalam bisnis
- Pelajari tentang fungsi biaya/fungsi tujuan dan variabel keputusan
- Pelajari hubungan antara pembelajaran mesin dan pengoptimalan
- Pelajari prinsip dan konsep Algoritma Genetika
- Pelajari implementasi GA dalam kasus bisnis dan bidang ilmu data
Library and Setup
Untuk menggunakan GA, Anda dapat menginstal paket GA menggunakan fungsi install.packages().
Berikut ini adalah paket-paket yang akan digunakan di seluruh artikel.
library(tidyverse)
library(GA)
library(ranger)
library(tidymodels)
library(caret)
library(tictoc)
library(tufte)
library(randomForest)Optimization Problem
Why Optimization is Important
Katakanlah, kami memiliki 2 lini produk, dengan produk A memiliki keuntungan sebesar USD 50 sedangkan produk B memiliki keuntungan sebesar USD 30. Kami ingin memaksimalkan keuntungan kami, tetapi kami memiliki sumber daya yang terbatas. Kami hanya memiliki 80 jam kerja selama seminggu, dengan produk A memakan waktu sekitar 10 jam dalam pembuatan sedangkan produk B adalah 4 jam dalam pembuatan. Kedua produk berbagi bahan yang sama dan kami hanya memiliki 100 meter kain dengan masing-masing 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? Begitulah masalah optimasi (dalam hal ini, optimasi profit).
Bagaimana jika kita memutuskan untuk memilih secara acak jumlah setiap produk yang akan diproduksi. Kita mungkin tidak punya cukup waktu untuk menyelesaikannya. Kami mungkin tidak memiliki cukup bahan, atau sebaliknya bisa terjadi: kami mungkin memiliki bahan cadangan.
Kasus lain, katakanlah kami ingin mengirimkan produk kami ke beberapa gudang. Bagaimana kami memutuskan gudang mana yang harus kami kunjungi terlebih dahulu atau bagaimana kami memutuskan rute apa yang harus kami ambil untuk meminimalkan waktu pengiriman?
Optimalisasi penting terutama jika kita memiliki sumber daya yang terbatas. Lebih penting lagi, optimasi memperhatikan keuntungan dan kerugian: memilih rute pengiriman yang salah akan mengakibatkan keterlambatan pengiriman, yang dapat menimbulkan biaya penalti atau merusak produk kami di sepanjang jalan. Itulah mengapa optimasi sangat penting untuk bisnis.
Objective Function and Decision Variables
Setiap masalah optimasi selalu memiliki 2 elemen: fungsi tujuan dan variabel keputusan. Fungsi objektif 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 yang dapat menghasilkan keuntungan maksimal? Kami ingin memaksimalkan tujuan kami dengan memilih variabel keputusan yang tepat. Pada contoh sebelumnya, tujuan untuk memaksimalkan laba termasuk ke 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. Kendala itu penting, karena solusi apa pun yang tidak memenuhi kendala adalah solusi yang tidak layak.
Machine Learning and Optimization
Machine learning dan optimasi tidak dapat dipisahkan, keduanya saling berkaitan, meskipun tujuannya berbeda. Pembelajaran mesin 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 pembelajaran mesin adalah pengoptimalan. Sebagai contoh, metode gradient descent dari model pelatihan Neural Network adalah metode optimasi, yang tujuannya adalah untuk menemukan titik terendah dan konvergen. Contoh lain adalah pemasangan regresi linier, yang meminimalkan jumlah kesalahan kuadrat (dengan demikian, nama metode Kuadrat Terkecil).
Pembelajaran mesin dapat ditingkatkan dengan menyetel hyper-parameter dengan pengoptimalan, sementara pada saat yang sama metode pengoptimalan juga dapat ditingkatkan dengan model pembelajaran mesin. Misalnya, kita dapat secara signifikan mengurangi MSE model Regresi K-NN Standar dan Tertimbang dengan menggunakan Algoritma Genetika1. Dengan optimasi multi-tujuan, kita dapat memperoleh model ensemble yang memiliki keseimbangan keseimbangan antara runtime dan kinerja model2.
Genetic Algorithm: Concepts
Overview
Pertama-tama mari kita baca paragraf indah ini dari The Blind Watchmaker oleh Richard Dawkins
“Semua penampilan sebaliknya, satu-satunya pembuat jam di alam adalah kekuatan buta fisika, meskipun dikerahkan dengan cara yang sangat khusus. Seorang pembuat jam sejati memiliki pandangan jauh ke depan: ia merancang pegas roda giginya, dan merencanakan interkoneksinya, dengan tujuan masa depan di benaknya. Seleksi alam, proses buta, tidak sadar, otomatis yang ditemukan Darwin, dan yang sekarang kita ketahui adalah penjelasan atas keberadaan dan bentuk yang tampaknya memiliki tujuan dari semua kehidupan, tidak memiliki tujuan dalam pikiran. Ia tidak memiliki pikiran dan tidak memiliki mata pikiran. Itu tidak merencanakan masa depan. Ia tidak memiliki visi, tidak ada pandangan ke depan, tidak ada penglihatan sama sekali. Jika dapat dikatakan memainkan peran pembuat jam di alam, itu adalah pembuat jam buta.”
Evolusi melalui seleksi alam pertama kali dikemukakan oleh Charles Darwin melalui bukunya On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. Terlepas dari pernyataan berani Dawkins bahwa seleksi alam tidak memiliki tujuan, mekanismenya dapat disesuaikan untuk memecahkan masalah optimasi. Jika dalam dunia biologis nyata, seleksi alam bekerja secara tidak sengaja dengan memilih individu yang paling cocok yang dapat bertahan hidup dan bereproduksi, sehingga menyebarkan gennya, solusi optimal atau terbaik dalam masalah optimasi dapat diperoleh dengan memilih yang memiliki nilai tercocok, yaitu nilai fungsi tujuan. Ini mungkin perbedaan utama antara seleksi alam yang sebenarnya dan yang diadopsi untuk Algoritma Genetika.
“Algoritma genetika (GA) adalah algoritma pencarian stokastik yang 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, persilangan dan mutasi..”
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 mutasi yang jarang dan acak.
Misalkan kita memiliki fungsi non-cembung. Jika kita menggunakan metode berbasis turunan seperti penurunan gradien, itu berpotensi jatuh ke optima lokal di \(x_1\). Algoritma Genetika dapat mengatasi local optima sehingga dapat memberikan solusi yang lebih baik. Dikombinasikan dengan pembelajaran mesin seperti jaringan saraf, GA dapat membuat sistem kecerdasan buatan yang dapat bermain game, like Flappy Bird
The general flow of the algorithm is shown below:
- Akan ada populasi dari kromosom atau solusi yang dipilih secara acak.
- Nilai fitness atau nilai fungsi tujuan dari masing-masing solusi dihitung.
- Dari populasi tersebut akan dipilih dua solusi sebagai solusi induk, baik dengan pemilihan turnamen atau metode pemilihan lainnya.
- Solusi yang dipilih akan disilangkan untuk membuat solusi baru, yang disebut solusi anak.
- Solusi anak dapat berubah karena mutasi acak (yang kemungkinannya sangat kecil untuk terjadi).
- Di akhir iterasi, populasi baru akan dipilih dari solusi induk atau populasi awal dan solusi anak berdasarkan nilai fitness.
- Selama kriteria berhenti tidak terpenuhi, biasanya dalam hal jumlah iterasi, algoritma akan terus melakukan iterasi.
- Solusi terbaik atau optimal adalah solusi dengan nilai fitness yang optimal.
Ada beberapa keuntungan dari Algoritma Genetika:
- Algoritma Genetika dapat menghindari optimal lokal
- Dapat menangani masalah yang kompleks dengan banyak variabel keputusan dan ruang solusi yang besar
- Ini mempertimbangkan banyak titik di ruang pencarian secara bersamaan, bukan satu titik, untuk berurusan dengan besar ruang parameter.
- Dapat diparalelkan karena GA terdiri dari beberapa kromosom/solusi
- Mendukung pengoptimalan multi-tujuan
Elements
Ada 3 elemen utama GA: Populasi, Kromosom, dan Gen.
Populasi adalah sekelompok individu atau solusi, terutama disebut kromosom. Sebuah kromosom terdiri dari urutan gen, dengan masing-masing atau beberapa gen (tergantung pada pengkodeannya) mewakili variabel keputusan tunggal yang akan dipasang pada fungsi tujuan.
Gen dapat direpresentasikan atau dikodekan dengan berbagai cara, termasuk:
- Binary Encoding
Pengkodean biner berarti bahwa gen kita dikodekan ke dalam bilangan biner, ini adalah bentuk pengkodean GA yang paling awal dan paling umum.
- Real-Valued Encoding
Pengkodean bernilai nyata berarti bahwa gen kita 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
Pengkodean permutasi berarti bahwa gen kita dikodekan ke dalam urutan nomor, setiap nomor secara unik ditugaskan untuk gen sehingga tidak ada 2 gen yang akan memiliki nomor atau nilai yang sama. Pengkodean ini sering digunakan dalam masalah penjadwalan atau perutean, di mana setiap permutasi mewakili satu lokasi atau titik unik.
Selection
Pemilihan parent dilakukan untuk memilih dua solusi yang akan digunakan untuk crossover untuk membuat solusi baru yang disebut solusi anak. Ada beberapa metode untuk memilih orang tua:
- Pemilihan Roda Roulette
Orang tua akan dipilih secara acak berdasarkan nilai fitness. Nilai fitness yang lebih tinggi berarti kesempatan yang lebih tinggi untuk dipilih. 
- Pemilihan Peringkat Linier
Individu diberi kebugaran subjektif berdasarkan peringkat dalam populasi. Individu dalam populasi diurutkan dari yang terbaik hingga yang terburuk berdasarkan nilai fitnessnya. Setiap individu dalam populasi diberi peringkat numerik berdasarkan kebugaran, dan seleksi didasarkan pada peringkat ini daripada perbedaan dalam kebugaran.
- Pemilihan Turnamen
Seleksi turnamen dilakukan dengan menyeleksi 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.
Crossover and Mutation
Crossover
Crossover adalah proses perkawinan antara dua individu yang dipilih, proses tersebut mewakili bagaimana gen ditransfer ke keturunannya. Ada beberapa metode crossover: #### Binary
- Crossover titik tunggal
Pisahkan induk berdasarkan satu titik yang dihasilkan secara acak. Anak pertama akan memiliki gen dari orang tua pertama untuk posisi 1 sampai dengan titik, sedangkan sisanya diisi dengan gen dari orang tua kedua. Anak kedua kebalikannya, posisi 1 sampai titik diisi dengan gen dari induk kedua.
- Seragam Crossover
Setiap gen dipertukarkan antara sepasang kromosom yang dipilih secara acak dengan probabilitas tertentu, yang disebut sebagai probabilitas swapping. Biasanya, nilai probabilitas swapping diambil menjadi 0,5.
Real-Valued
- Crossover Aritmatika Utuh
Mengambil jumlah tertimbang dari dua gen induk untuk setiap posisi. Bobot diterapkan untuk semua posisi. Misal x = nilai parent pertama dan y = nilai parent kedua untuk posisi/gen 1:
\[Child \ 1 = weight \ * x + (1-weight) \ * y\]
\[Child \ 2 = weight \ * y + (2-weight) \ * x\]
Jika berat = 0,5 dua keturunan identik
- Crossover Aritmatika Lokal
Crossover lokal mirip dengan crossover aritmatika keseluruhan, tetapi menggunakan alpha acak untuk setiap posisi.
Permutation
- One-point crossover
Crossover satu titik hanya menggunakan satu titik acak sebagai penanda dimana seharusnya crossover terjadi.
Nearchou, 2014
- Position-Based crossover
Sejumlah posisi dari induk pertama dipilih secara acak dan mengisi posisi yang tersisa dari induk kedua.
Nearchou, 2014
Mutation
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:
Binary
- Random Mutation
Gen dibalik secara acak dari 1 ke 0 atau sebaliknya dengan probabilitas seragam untuk setiap gen, artinya setiap gen memiliki peluang yang sama untuk bermutasi dengan tingkat mutasi atau probabilitas mutasi yang ditetapkan oleh pengguna. 
Real Valued
- Mutasi Acak Seragam
Gen bermutasi secara acak pada posisi dengan nilai dari kisaran tertentu dengan distribusi seragam.
- Mutasi Acak Tidak Seragam
Pilih gen/posisi acak dari sebuah kromosom dan berikan nilai acak yang tidak seragam padanya.
Permutation
- Mutasi Pertukaran Berdekatan
Dua gen yang berdekatan ditukar secara acak. 
- Mutasi Terbalik
Mutasi terbalik dilakukan dengan cara membalik barisan antara dua titik acak. 
Application
Algoritma Genetika dapat diterapkan dalam berbagai permasalahan 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 kami muat di tas atau truk kami untuk memaksimalkan ruang atau beban berat), masalah traveling salesman, dll. GA juga dapat diterapkan di bidang ilmu data, khususnya ketika kami melakukan penyetelan hyper-parameter untuk mengoptimalkan kinerja model. Masalah tertentu mungkin memiliki pengaturan parameter uniknya sendiri yang dapat memiliki nilai kebugaran yang lebih baik. Misalnya, masalah penjadwalan flowshop telah diteliti oleh Nearchou3. Gambaran detail dan penerapan GA dapat dilihat di karya Kramer4
Illustration
Mari kita ilustrasikan langkah demi langkah bagaimana Algoritma Genetika bekerja. Katakanlah saya memiliki satu set item dengan poin dan berat masing-masing (kg). Saya ingin memaksimalkan poin, tetapi aturan mengatakan bahwa saya tidak dapat membawa barang dengan berat total lebih dari 15 kg. Item mana yang harus saya pilih untuk memaksimalkan poin saya?
Define Encoding and Fitness Function
Karena masalahnya adalah apakah membawa item tertentu atau tidak, maka solusinya harus terdiri dari nilai logis dari setiap item. Jika nilainya 1 atau TRUE, maka saya harus membawa item tersebut, dan jika nilainya 0 atau FALSE, maka saya tidak boleh membawa item tersebut. Dengan logika ini, pengkodean untuk algoritma genetika kita harus pengkodean biner karena hanya terdiri dari 2 nilai (1 atau 0).
Fungsi kebugaran kemudian, harus memaksimalkan titik total.
\[Maximize \ Total\ Point = \Sigma_{i=1}^{k} \ P_k \ * \ chosen_k \]
- \(Total\ Poin\): Total poin yang dihasilkan
- \(k\): Jumlah barang
- \(P_k\): Titik item k
- \(chosen_k\): nilai logika setiap item (1 atau 0)
Batasan:
\[Total\ Weight <= 15\]
Karena kita memiliki kendala, kita perlu memasukkan kendala ke dalam fungsi fitness. Hal ini dilakukan untuk mencegah solusi yang tidak layak (yang melanggar batasan) untuk dipilih atau dipilih sebagai nilai optimal.
\[Maximize\ Total\ Point = \Sigma_{i=1}^{k} \ P_k \ chosen_k - 2 \ (total\ weight - 15)^2\]
Initial Population
Pertama, GA akan membangkitkan populasi solusi secara acak. Di sini, kami memiliki populasi 4 solusi/individu. Nilai biner pada setiap individu dibangkitkan secara acak.
Fitness Assignment
Now we calculate the fitness value (total point) of each individuals based on the fitness function above. We can see that solution that violate the constraint (have total weight > 15) will have worse fitness function.
Selection
Sekarang kita akan memilih individu mana yang akan disilangkan untuk mendapatkan solusi baru. Kami akan menggunakan pemilihan peringkat linier untuk memilih solusi induk. Kami akan memilih 2 solusi karena crossover membutuhkan 2 solusi parent.
Pemilihan peringkat linier bekerja sebagai berikut:
- Berikan peringkat untuk setiap individu. Peringkat yang lebih besar diberikan untuk fungsi kebugaran yang lebih besar. Individu 2 dengan fungsi fitness 19 adalah yang tertinggi, sehingga akan diberikan rangking 4.
- Hitung probabilitas setiap individu berdasarkan peringkat mereka. Jumlah peringkatnya adalah 10, jadi probabilitas setiap solusi adalah \(Rank_i/10\).
- Pilih solusi secara acak berdasarkan probabilitas. Solusi dengan fungsi fitness yang lebih tinggi secara alami akan memiliki peluang lebih tinggi untuk dipilih.
Katakanlah misalnya, solusi pertama dan kedua dipilih sebagai parent 
Crossover
Crossover berarti pertukaran gen antara dua orang tua dua membuat solusi baru yang disebut solusi anak. Kami akan menggunakan crossover titik tunggal di sini. Satu titik dipilih secara acak.
Katakanlah titik yang dipilih berada di antara posisi 2 dan 3. Untuk anak pertama akan memiliki gen pertama dan kedua dari induk pertama, sedangkan sisanya akan diisi dari induk kedua. Untuk anak kedua, sebaliknya, ia akan memiliki gen pertama dan kedua dari orang tua kedua, sedangkan sisanya akan diisi dari orang tua pertama. 
Mutation
Mutasi adalah perubahan nilai pada gen. Di sini kita menggunakan mutasi acak. Ini akan secara acak menukar nilai gen. Jika gen di posisi 3 bernilai 1, maka akan diubah menjadi 0 dan sebaliknya. Mutasi jarang terjadi, probabilitasnya dapat diatur secara manual, tetapi umumnya orang menggunakan probabilitas mutasi 0,1.
Proses seleksi, crossover, dan mutasi akan diulangi dengan memilih induk yang berbeda sampai jumlah anak sama dengan ukuran populasi induk. Jika orang tua memiliki ukuran populasi 4, maka kita akan memiliki populasi anak-anak 4. ### Check Stopping Criteria
Setelah mutasi selesai, kami akan memeriksa apakah sudah waktunya untuk menghentikan algoritma. Sudahkah kita mencapai iterasi 100? Apakah dalam 10 iterasi terakhir nilai fitness optimal tidak berubah? Jika tidak, maka iterasi akan dilanjutkan. Setelah crossover dan mutasi, sekarang kami memiliki populasi induk 4 dan populasi anak-anak 4, jadi total kami sekarang memiliki 8 solusi. Untuk iterasi selanjutnya, kita hanya akan memilih 4 individu (sesuai dengan ukuran populasi awal) dari induk dan anak. Umumnya individu dengan nilai fitness tinggi akan dipilih, sehingga populasi berikutnya akan lebih baik dari yang terakhir.
Genetic Algorithm with R
Di sini kita akan mengilustrasikan bagaimana GA dapat bekerja menggunakan paket GA56 baik pada masalah bisnis maupun pada penyetelan hyper-parameter machine learning.
Business Application
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_itemSetiap 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("item","weight")]
head(df_item_long)Mari kita atur fungsi tujuan.
\[Total\ Weight = \Sigma_{i=1}^{k} \ W_k \ * \ n_k \]
- \(Total\ Berat\): Berat total (kg)
- \(k\): Jumlah item unik
- \(W_k\): Berat barang k
- \(n_k\): Jumlah item k yang dipilih
Batasan:
\[Total\ Weight <= 10000\]
We will translate the objective function into R function.
weightlimit <- 10000
evalFunc <- function(x) {
# Subset only selected item based on the solution
df <- df_item_long[x == 1, ]
# calculate the total weight
total_weight <- sum(df$weight)
# Penalty if the total weight surpass the limit
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 logis (BENAR atau SALAH), dengan setiap bit mewakili nilai logis tunggal apakah item tersebut dipilih.
Parameter algoritma:
type: Jenis pengkodean gen, di sini kami menggunakan “biner”fitness: Fungsi kebugaran yang akan dioptimalkannBits: Jumlah bit yang dihasilkan untuk variabel keputusanpmutation: probabilitas mutasi, default 0.1pcrossover: probabilitas crossover, default 0,8seed: Nilai seed acak untuk mendapatkan hasil yang dapat direproduksielitisme: Jumlah solusi terbaik yang akan bertahan di setiap iterasi, defaultnya adalah 5% teratas dari populasi.maxiter: Jumlah iterasi maksimal untuk menjalankan algoritmepopSize: Jumlah solusi dalam suatu populasirun: Jumlah iterasi sebelum algoritma berhenti jika tidak ada perbaikan pada nilai fitness optimalparalel: Apakah kita akan menggunakan komputasi paralel? Dapat berupa nilai logika atau jumlah inti yang digunakanlower: Nilai terendah dari pengkodean permutasiupper: Nilai tertinggi dari pengkodean permutasikeepBest: Logis apakah kami menyimpan solusi terbaik di setiap generasi di slot terpisah
Ada beberapa opsi yang dapat dipilih untuk setiap proses GA. Misalnya, pemilihan induk default GA untuk biner adalah pemilihan peringkat linier. Metode default terperinci yang digunakan pada setiap penyandian dapat ditemukan di sini7.
Fungsi tic() dan toc() digunakan untuk mengukur waktu komputasi.
Di sini kita akan menjalankan algoritme genetika dengan pengkodean biner, fungsi fitnessnya adalah evalFunc() yang kita buat sebelumnya. Ukuran populasi (popSize) adalah 100 dengan iterasi maksimum (maxiter) juga 100. Maksimum run (run) tanpa perbaikan adalah 20, setelah itu algoritma akan dihentikan. Seed untuk reproduktifitas diatur pada 123. Karena kami menggunakan pengkodean biner, parameter nBits mengontrol jumlah bit yang dihasilkan. Karena setiap bit akan mewakili keputusan untuk setiap item, jumlah bit sama dengan jumlah baris dari df_item_long.
tic()
library(GA)
ga_knapsack <- ga(type = "binary", fitness = evalFunc, popSize = 100,
maxiter = 100,
run = 20, nBits = nrow(df_item_long), seed = 123)
toc()## 0.39 sec elapsedIterasi berhenti pada iterasi 22 karena setelah 20 iterasi tidak ada perbaikan pada total weight. Solusi optimal dapat dilihat pada Nilai fungsi kebugaran yaitu 10.000 (10.000 kg).
Keluaran 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.
summary(ga_knapsack)## -- 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 0Solusi terburuk dalam populasi memiliki nilai fitness 0 (mereka yang terkena penalti karena melewati batasan batas bobot), sedangkan solusi optimal memiliki nilai fitness 10000. Dari semua 100 kromosom atau solusi dihasilkan, median nilai fitness adalah 9572 sedangkan meannya adalah 6733.
Untuk memeriksa ringkasan, kami menggunakan fungsi summary() pada objek GA
summary(ga_knapsack)## -- 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 0Seperti yang kita lihat, ada beberapa solusi untuk masalah tersebut, semuanya memiliki nilai fitness yang sama: 10000. Oleh karena itu, kami memiliki fleksibilitas untuk memilih solusi mana yang akan kami pilih. Semua solusi optimal tidak memiliki nilai lebih besar dari kendalanya, yang juga 10.000.
Mari kita periksa plot progresi nilai fitness menggunakan plot().
plot(ga_knapsack)
Kita dapat melihat bahwa solusi optimal (Best) sudah tercapai pada iterasi 3.
Mari kita pilih salah satu solusi sebagai keputusan kita.
df_sol <- df_item_long[ga_knapsack@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_solMari kita periksa berat totalnya
sum(df_sol$total_weigth)## [1] 10000ga_knapsack@solution## x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21
## [1,] 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1
## [2,] 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1
## [3,] 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1
## [4,] 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1
## [5,] 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1
## x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37 x38 x39
## [1,] 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0
## [2,] 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0
## [3,] 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1
## [4,] 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0
## [5,] 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0
## x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x55 x56 x57
## [1,] 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0
## [2,] 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0
## [3,] 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0
## [4,] 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0
## [5,] 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0
## x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72 x73 x74 x75
## [1,] 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1
## [2,] 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1
## [3,] 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1
## [4,] 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1
## [5,] 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1
## x76 x77 x78 x79 x80 x81 x82 x83 x84 x85 x86 x87 x88 x89 x90 x91 x92 x93
## [1,] 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0
## [2,] 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0
## [3,] 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0
## [4,] 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0
## [5,] 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0
## x94 x95 x96 x97 x98 x99 x100 x101 x102 x103 x104 x105 x106 x107 x108 x109
## [1,] 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0
## [2,] 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0
## [3,] 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1
## [4,] 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0
## [5,] 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0
## x110 x111 x112 x113 x114 x115 x116 x117 x118 x119 x120 x121 x122 x123 x124
## [1,] 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0
## [2,] 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0
## [3,] 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0
## [4,] 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0
## [5,] 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0
## x125 x126 x127 x128 x129 x130 x131 x132 x133 x134 x135 x136 x137 x138 x139
## [1,] 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
## [2,] 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
## [3,] 1 1 1 0 0 0 1 1 1 1 0 1 1 0 1
## [4,] 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
## [5,] 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
## x140 x141 x142 x143 x144 x145 x146 x147 x148 x149 x150 x151 x152 x153 x154
## [1,] 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0
## [2,] 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0
## [3,] 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0
## [4,] 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0
## [5,] 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0
## x155 x156 x157 x158 x159 x160 x161 x162 x163 x164 x165 x166 x167 x168 x169
## [1,] 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0
## [2,] 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0
## [3,] 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1
## [4,] 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0
## [5,] 1 1 1 0 1 0 0 1 0 0 1 1 0 1 0
## x170 x171 x172 x173 x174 x175 x176 x177 x178 x179 x180 x181 x182 x183 x184
## [1,] 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0
## [2,] 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0
## [3,] 1 1 1 0 1 0 0 1 1 1 0 1 0 0 1
## [4,] 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0
## [5,] 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0
## x185 x186 x187 x188 x189 x190 x191 x192 x193 x194 x195 x196 x197 x198 x199
## [1,] 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1
## [2,] 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1
## [3,] 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1
## [4,] 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1
## [5,] 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1
## x200 x201 x202 x203 x204 x205 x206 x207 x208 x209 x210 x211 x212 x213 x214
## [1,] 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
## [2,] 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
## [3,] 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1
## [4,] 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
## [5,] 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
## x215 x216 x217 x218 x219 x220 x221 x222 x223 x224 x225 x226 x227 x228 x229
## [1,] 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1
## [2,] 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1
## [3,] 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0
## [4,] 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1
## [5,] 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1
## x230 x231 x232 x233 x234 x235 x236 x237 x238 x239 x240 x241 x242 x243 x244
## [1,] 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1
## [2,] 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1
## [3,] 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1
## [4,] 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1
## [5,] 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1
## x245 x246 x247 x248 x249 x250 x251 x252 x253 x254 x255 x256 x257 x258 x259
## [1,] 0 0 0 0 1 1 1 1 0 1 0 0 1 0 1
## [2,] 0 0 0 0 1 1 1 1 0 1 0 0 1 0 1
## [3,] 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1
## [4,] 0 0 0 0 1 1 1 1 0 1 0 0 1 0 1
## [5,] 0 0 0 0 1 1 1 1 0 1 0 0 1 0 1
## x260 x261 x262 x263 x264 x265 x266 x267 x268 x269 x270 x271 x272 x273 x274
## [1,] 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0
## [2,] 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1
## [3,] 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0
## [4,] 1 0 1 0 0 1 0 1 1 0 0 0 1 1 1
## [5,] 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0
## x275 x276 x277 x278 x279 x280 x281 x282 x283 x284 x285 x286 x287 x288 x289
## [1,] 1 0 1 1 1 0 1 1 0 1 0 0 0 0 1
## [2,] 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0
## [3,] 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1
## [4,] 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0
## [5,] 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1
## x290 x291 x292 x293 x294 x295 x296 x297 x298 x299 x300 x301 x302 x303 x304
## [1,] 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0
## [2,] 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0
## [3,] 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0
## [4,] 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0
## [5,] 0 0 0 1 0 1 1 0 0 0 1 1 0 0 0
## x305 x306 x307 x308 x309 x310 x311 x312 x313 x314 x315 x316 x317 x318 x319
## [1,] 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0
## [2,] 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1
## [3,] 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0
## [4,] 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1
## [5,] 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1
## x320
## [1,] 1
## [2,] 1
## [3,] 0
## [4,] 1
## [5,] 0Nilai fitness yang optimal sama dengan constraintnya, sehingga kita dapat memuat kendaraan secara penuh sesuai dengan kapasitas maksimumnya.
Mari kita periksa solusi ketiga
df_sol <- df_item_long[ga_knapsack@solution[3, ] == 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_solsum(df_sol$total_weigth)## [1] 10000Meskipun solusi pertama dan solusi kedua memiliki keputusan yang berbeda, fungsi fitness atau bobot totalnya sama, oleh karena itu keduanya merupakan solusi optimal dan keputusan untuk memilih mana yang harus digunakan sebenarnya diserahkan kepada pengambil keputusan.
Traveling Salesman Problem
Travelling Salesperson Problem (TSP) adalah salah satu masalah yang paling banyak dibahas dalam optimasi kombinatorial. Dalam bentuknya yang paling sederhana, pertimbangkan satu set n kota dengan jarak intra simetris yang diketahui, TSP melibatkan pencarian rute optimal untuk mengunjungi semua kota dan kembali ke titik awal sedemikian rupa sehingga jarak yang ditempuh diminimalkan. Himpunan solusi layak diberikan oleh jumlah total rute yang mungkin, yang sama dengan (n 1)!/2.
Pertimbangkan kumpulan data eurodist ini. Terdiri dari 21 x 21 matriks jarak antar kota. Jumlah total rute yang mungkin adalah (21 - 1)!/2 = 1216451004088320000. Mencoba setiap rute akan memakan banyak waktu. Pencarian acak sederhana mungkin gagal menemukan global optima.
cities <- as.matrix(eurodist)
head(cities)## Athens Barcelona Brussels Calais Cherbourg Cologne Copenhagen Geneva
## Athens 0 3313 2963 3175 3339 2762 3276 2610
## Barcelona 3313 0 1318 1326 1294 1498 2218 803
## Brussels 2963 1318 0 204 583 206 966 677
## Calais 3175 1326 204 0 460 409 1136 747
## Cherbourg 3339 1294 583 460 0 785 1545 853
## Cologne 2762 1498 206 409 785 0 760 1662
## Gibraltar Hamburg Hook of Holland Lisbon Lyons Madrid Marseilles
## Athens 4485 2977 3030 4532 2753 3949 2865
## Barcelona 1172 2018 1490 1305 645 636 521
## Brussels 2256 597 172 2084 690 1558 1011
## Calais 2224 714 330 2052 739 1550 1059
## Cherbourg 2047 1115 731 1827 789 1347 1101
## Cologne 2436 460 269 2290 714 1764 1035
## Milan Munich Paris Rome Stockholm Vienna
## Athens 2282 2179 3000 817 3927 1991
## Barcelona 1014 1365 1033 1460 2868 1802
## Brussels 925 747 285 1511 1616 1175
## Calais 1077 977 280 1662 1786 1381
## Cherbourg 1209 1160 340 1794 2196 1588
## Cologne 911 583 465 1497 1403 937karena tujuannya adalah untuk meminimalkan jarak, nilai fitness akan bernilai negatif.
tsp_fitness <- function(x) {
x <- c(x, x[1])
# create from-to matrix
route <- embed(x, 2)[, 2:1]
# Calculate distance
distance <- -sum(cities[route])
return(distance)
}Let’s run the algorithm.
tic()
ga_cities <- ga(type = "permutation", fitness = tsp_fitness, monitor = F,
lower = 1, upper = nrow(cities), popSize = 100, maxiter = 5000,
run = 500, seed = 123)
summary(ga_cities)## -- Genetic Algorithm -------------------
##
## GA settings:
## Type = permutation
## Population size = 100
## Number of generations = 5000
## Elitism = 5
## Crossover probability = 0.8
## Mutation probability = 0.1
##
## GA results:
## Iterations = 1739
## Fitness function value = -12919
## Solutions =
## x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 ... x20 x21
## [1,] 15 2 9 12 14 5 18 4 3 11 8 13
## [2,] 5 18 4 3 11 7 20 10 6 17 12 14
## [3,] 1 21 17 6 10 20 7 11 3 4 16 19
## [4,] 6 10 20 7 11 3 4 18 5 14 21 17
## [5,] 1 19 16 8 13 15 2 9 12 14 17 21toc()## 10.5 sec elapsedKami memiliki 5 solusi/rute yang memiliki jarak minimal. Ubah informasi menjadi rute yang dapat dibaca
route_optimal <- ga_cities@solution
cities_name <- names(cities[1 , ])
cities_name <- apply(route_optimal, 1, function(x) {cities_name[x]})
apply(cities_name, 2, paste, collapse = " > ")## [1] "Marseilles > Barcelona > Gibraltar > Lisbon > Madrid > Cherbourg > Paris > Calais > Brussels > Hook of Holland > Copenhagen > Stockholm > Hamburg > Cologne > Munich > Vienna > Athens > Rome > Milan > Geneva > Lyons"
## [2] "Cherbourg > Paris > Calais > Brussels > Hook of Holland > Copenhagen > Stockholm > Hamburg > Cologne > Munich > Vienna > Athens > Rome > Milan > Geneva > Lyons > Marseilles > Barcelona > Gibraltar > Lisbon > Madrid"
## [3] "Athens > Vienna > Munich > Cologne > Hamburg > Stockholm > Copenhagen > Hook of Holland > Brussels > Calais > Paris > Cherbourg > Madrid > Lisbon > Gibraltar > Barcelona > Marseilles > Lyons > Geneva > Milan > Rome"
## [4] "Cologne > Hamburg > Stockholm > Copenhagen > Hook of Holland > Brussels > Calais > Paris > Cherbourg > Madrid > Lisbon > Gibraltar > Barcelona > Marseilles > Lyons > Geneva > Milan > Rome > Athens > Vienna > Munich"
## [5] "Athens > Rome > Milan > Geneva > Lyons > Marseilles > Barcelona > Gibraltar > Lisbon > Madrid > Cherbourg > Paris > Calais > Brussels > Hook of Holland > Copenhagen > Stockholm > Hamburg > Cologne > Munich > Vienna"Better representation for the route can be visualized through network or graph.
Business Application
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. Saya sudah menyiapkan data dummy yang bisa Anda akses di sini.
df_car <- read.csv("data_input/car_data.csv")
df_carThe 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.
PENTING Pemilihan ukuran populasi dan jumlah iterasi akan sangat mempengaruhi kinerja GA. Jika ukuran populasi terlalu kecil, akan ada kumpulan gen yang terbatas dalam populasi kita 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 algoritma:
type: Jenis pengkodean gen, di sini kita menggunakan “permutasi”kebugaran: Fungsi kebugaran yang akan dioptimalkanlebih rendah: Nilai terendah dari pengkodean permutasi, kami akan mengkodekan permutasi dari 1 ke jumlah mobil yang tersediaatas: Nilai tertinggi dari pengkodean permutasiseed: Nilai seed acak untuk mendapatkan hasil yang dapat direproduksielitism: Jumlah solusi terbaik yang akan bertahan di setiap iterasi, default adalah 5% teratas dari populasi, di sini kami menetapkannya menjadi 50 solusi yang akan bertahanmaxiter: Jumlah iterasi maksimal untuk menjalankan algoritmapopSize: Jumlah solusi dalam suatu populasirun: Jumlah iterasi sebelum algoritma berhenti jika tidak ada perbaikan pada nilai fitness optimalparalel: 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 22toc()## 57.84 sec elapsedKita 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] -6Jika 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.00Solusi 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_itemSetiap 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_longThe 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 0toc()## 0.49 sec elapsedplot(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)## `summarise()` has grouped output by 'item'. You can override using the `.groups` argument.df_solTotal berat:
sum(df_sol$total_weigth)## [1] 10000Nilai 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.
Hyper-Parameter Tuning on Machine Learning Model
Sekarang kami akan mencoba menerapkan algoritme untuk mengoptimalkan model pembelajaran mesin kami. Kami akan menggunakan dataset attrition.
Import Data
attrition <- read.csv("data_input/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))
attritionCross-Validation
Kami membagi data menjadi training set dan testing dataset, dengan 80% data akan digunakan sebagai training set.
set.seed(123)
intrain <- initial_split(attrition, prop = 0.8, strata = "attrition")
intrain## <Analysis/Assess/Total>
## <1175/295/1470>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_18karena hanya memiliki 1 level 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()## Registered S3 methods overwritten by 'themis':
## method from
## bake.step_downsample recipes
## bake.step_upsample recipes
## prep.step_downsample recipes
## prep.step_upsample recipes
## tidy.step_downsample recipes
## tidy.step_upsample recipes
## tunable.step_downsample recipes
## tunable.step_upsample recipesdata_train <- juice(rec)
data_test <- bake(rec, testing(intrain))
data_trainCreate 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] 128Jadi, 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.
Kami akan mencoba menggunakan pemilihan turnamen alih-alih pemilihan peringkat linier default.
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 1toc()## 235.86 sec elapsedMari kita plot perkembangan GA
plot(ga_rf)
Mari kita periksa setiap variabel keputusan dan akurasi yang digunakan sebagai nilai fitness.
# Transform decision variables into data frame
ga_rf_pop <- as.data.frame(ga_rf@population)
# Convert decision variables into mtry and min_n
ga_mtry <- apply(ga_rf_pop[ , 1:5], 1, binary2decimal)
ga_min_n <- apply(ga_rf_pop[ , 6:12], 1, binary2decimal)
# Show the list of solutions in the final population
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))Compare with K-fold Cross Validation
Anda mungkin ingin membandingkan waktu komputasi GA dengan waktu yang diperlukan untuk validasi silang K-fold berulang menggunakan paket caret konvensional. Kami akan menggunakan k = 5 dan 10 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()## 416.06 sec elapsedattrition_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 periksa keakuratan model hutan acak dengan caret
pred_rf <- predict(attrition_forest, newdata = data_test)
accuracy_vec(truth = data_test$attrition, estimate = pred_rf)## [1] 0.820339Performa 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.
Conclusion
Masalah optimasi adalah salah satu dari banyak perhatian dalam bisnis, yang mungkin berusaha untuk memaksimalkan keuntungan dan meminimalkan kerugian. Pembelajaran mesin menerapkan pengoptimalan pada metode model pelatihan mereka untuk mendapatkan hasil terbaik. GA merupakan algoritma optimasi yang dapat diterapkan di berbagai bidang, termasuk data science. Jika seorang ilmuwan data dapat memanfaatkan manfaat GA, ia bisa mendapatkan model yang lebih optimal dengan kinerja yang lebih baik. Kelemahan GA adalah membutuhkan waktu untuk menghitung karena termasuk dalam kelompok algoritma pencarian, di mana ia mengeksplorasi solusi yang mungkin secara efisien dibandingkan dengan pencarian acak.
What’s Next
Penelitian dalam algoritma evolusioner masih berkembang dalam beberapa tahun terakhir, beberapa membahas skema crossover dan mutasi terbaik, sementara yang lain meningkatkan metode. GA juga dapat diterapkan untuk optimasi multi-tujuan, di mana dua atau lebih tujuan yang saling bertentangan perlu dioptimalkan. Beberapa metode seperti NSGA-II atau SPEA2 merupakan metode GA populer yang dapat digunakan untuk melakukan optimasi multi-objektif. Banyak algoritma evolusioner multi-tujuan atau bahkan banyak-tujuan baru (yang memiliki lebih dari 3 tujuan) diturunkan dari dua metode ini8. Salah satu aplikasi yang paling menarik adalah di sektor manufaktur, terutama untuk masalah penjadwalan, di mana masalah optimasi kombinatorial yang kompleks perlu dipecahkan karena memiliki dampak yang besar terhadap produktivitas dan biaya9.
Reference
Treiber, N. A., and O. Kramer. 2015. Evolutionary feature weighting for wind power prediction with nearest neighbor regression. IEEE Congress on Evolutionary Computation (CEC), 332-337.↩︎
Oehmcke, S., Heinermann, J., and Kramer, O. 2015. Analysis of diversity methods for evolutionary multi-objective ensemble classifiers. Applications of Evolutionary Computation (EvoStar), 567–578.↩︎
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.↩︎
Kramer, Oliver. 2017. Genetic Algorithm Essentials. Gewerbestrasse: Springer.↩︎
Scrucca, Luca. 2013. GA: A Package for Genetic Algorithms in R. Journal of Statistical Software, 3(4).↩︎
GA Package: A Function For Setting Or Retrieving Defaults Genetic Operators↩︎
Chand, Shelvin and Markus Wagner. 2015. Evolutionary many-objective optimization: A quick-start guide. Surveys in Operations Research and Management Science, 20(2), 35-42.↩︎
Gen, M., & Lin, L. 2013. Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey. Journal of Intelligent Manufacturing, 25(5), 849–866.↩︎