Optimisasi Statistika - Genetic Algorithm

Video Pembelajaran - P10

Video Pembelajaran dapat diakses melalui link berikut : https://ipb.link/materiopstat

Algoritma Genetik

Pengantar

Algoritma Genetik (AG) adalah teknik pemrograman yang mengikuti prinsip evolusi biologis dan seleksi alam. Teknik ini sering digunakan dalam pencarian solusi optimal untuk masalah yang kompleks di mana metode tradisional tidak efisien. Dalam konteks statistika dan pemrograman linear, Algoritma Genetik dapat digunakan untuk optimasi model prediktif berdasarkan set data yang diberikan. AG beroperasi dengan menggunakan populasi dari solusi potensial yang disebut individu atau kromosom. Proses evolusi ini meliputi seleksi, rekombinasi (crossover), dan mutasi.

Langkah-langkah dasar dalam Algoritma Genetik adalah:

  • Inisialisasi Populasi: Membuat populasi awal yang terdiri dari individu-individu secara acak.
  • Evaluasi: Menghitung kecocokan setiap individu dalam populasi.
  • Seleksi: Memilih individu-individu terbaik sebagai orang tua yang akan menghasilkan keturunan.
  • Crossover (Rekombinasi): Menggabungkan informasi genetik dari orang tua untuk menghasilkan keturunan baru.
  • Mutasi: Memodifikasi keturunan secara acak untuk menjaga keragaman genetik.
  • Penggantian: Mengganti individu lama dengan yang baru untuk generasi berikutnya.
  • Iterasi: Mengulangi proses dari evaluasi hingga penggantian sampai kriteria berhenti terpenuhi.

Modul R Kuliah

Berikut adalah contoh implementasi Algoritma Genetik menggunakan bahasa pemrograman R:

# Create a vector for each column

x1 <- c(15, 11, 18, 10, 18, 13, 18, 12, 19, 10, 18, 17, 15, 15, 13, 19, 11)

x2 <- c(13, 15, 15, 16, 16, 16, 10, 16, 11, 16, 20, 13, 12, 11, 17, 12, 12)

x3 <- c(20, 19, 17, 13, 20, 18, 17, 12, 10, 19, 17, 19, 14, 11, 18, 13, 20)

x4 <- c(16, 20, 10, 20, 20, 10, 19, 17, 19, 17, 11, 15, 10, 12, 11, 11, 10)

x5 <- c(13, 14, 18, 11, 11, 10, 10, 10, 11, 19, 17, 20, 20, 19, 20, 16, 17)

x6 <- c(11, 19, 15, 12, 10, 17, 15, 17, 12, 16, 20, 20, 19, 16, 17, 16, 15)

x7 <- c(16, 10, 13, 20, 20, 20, 13, 19, 20, 15, 14, 18, 14, 14, 14, 18, 20)

x8 <- c(19, 14, 17, 20, 18, 11, 14, 11, 19, 10, 19, 17, 17, 17, 10, 17, 15)

x9 <- c(16, 15, 19, 12, 10, 16, 10, 19, 13, 10, 20, 16, 13, 14, 11, 20, 10)

x10 <- c(12, 17, 20, 10, 10, 17, 15, 12, 12, 20, 10, 17, 18, 12, 18, 19, 19)

x11 <- c(10, 14, 13, 20, 15, 12, 12, 18, 10, 12, 20, 17, 20, 12, 20, 17, 14)

y <- c(96, 88, 118, 91, 122, 102, 102, 101, 114, 89, 127, 111, 93, 90, 108, 117, 81)



# Combine the vectors into a dataframe

x <- data.frame(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11)

dd <- x

dd$y <- y

Data dd akan digunakan pada analisis selanjutnya.

Contoh dasar genetic algorithm

a <- c(1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0)

xterpilih <- x[, which(a == 1)] 

ddterpilih <- cbind(xterpilih, y)

regresi <- lm(y~., data=ddterpilih)

summary(regresi)$adj.r.squared
## [1] 0.5193257
a <- c(1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1)

xterpilih <- x[, which(a == 1)] 

ddterpilih <- cbind(xterpilih, y)

regresi <- lm(y~., ddterpilih)

summary(regresi)$adj.r.squared
## [1] 0.645484

Tahapan genetic algorithm

Inisialisasi populasi

npop = 5

populasi <- matrix(rbinom(55, 1, 0.2), nrow=npop, ncol=11) 

populasi
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
## [1,]    0    0    1    1    0    0    0    0    0     0     0
## [2,]    1    0    0    0    0    0    0    1    0     0     0
## [3,]    0    0    0    0    0    0    0    0    0     0     0
## [4,]    0    1    1    1    0    0    0    0    0     0     0
## [5,]    0    0    0    0    0    0    0    1    0     0     1

Bagian ini menginisialisasi populasi awal. Populasi terdiri dari 5 individu (baris), dan setiap individu memiliki 11 gen (kolom). Fungsi rbinom digunakan untuk menghasilkan nilai biner acak (0 atau 1) untuk setiap gen.

Evaluasi fitness (R2-adj)

fitness = rep(0, npop)

for (i in 1:npop){

  a <- populasi[i,]

  xterpilih <- x[, which(a == 1)] 

  ddterpilih <- data.frame(cbind(xterpilih, y))

  regresi <- lm(y~., data=ddterpilih)

  fitness[i] = summary(regresi)$adj.r.squared

}

Bagian ini mengevaluasi fitness setiap individu dalam populasi. Fitness dihitung sebagai nilai R-squared dari model regresi linier yang dibangun menggunakan subset fitur yang dipilih oleh gen dalam individu.

Seleksi

nseleksi <- 2

terbaik <- order(fitness, decreasing=TRUE)[1:nseleksi]

ambilterbaik = populasi[terbaik, ]

Bagian ini melakukan seleksi individu terbaik dari populasi berdasarkan nilai fitness mereka. Dua individu dengan fitness tertinggi dipilih.

Crossover

anak1 <- c(ambilterbaik[1, 1:5], ambilterbaik[2, 6:11])

anak2 <- c(ambilterbaik[2, 1:5], ambilterbaik[1, 6:11])

populasi <- rbind(ambilterbaik, anak1, anak2)

Bagian ini melakukan operasi crossover untuk menghasilkan individu baru. Dua individu terbaik dipilih sebagai orang tua, dan gen mereka dikombinasikan untuk menghasilkan dua individu baru (anak).

Mutasi

mutasi = matrix(rbinom(nrow(populasi)*ncol(populasi), 1, 1/10), 

nrow=nrow(populasi), ncol=ncol(populasi))

populasi = abs(populasi - mutasi)

Bagian ini melakukan operasi mutasi pada populasi. Setiap gen dalam setiap individu memiliki peluang tertentu untuk berubah (dari 0 menjadi 1, atau sebaliknya).

Tahapan Ver 2

Fungsi-fungsi

# Fungsi untuk evaluasi fitness

eval_fitness <- function(populasi, x, y) {

  fitness = rep(0, nrow(populasi))

  for (i in 1:nrow(populasi)){

    a <- populasi[i,]

    xterpilih <- x[, which(a == 1)] 

    ddterpilih <- data.frame(cbind(xterpilih, y))

    regresi <- lm(y~., data=ddterpilih)

    fitness[i] = summary(regresi)$adj.r.squared

  }

  return(fitness)

}



# Fungsi untuk seleksi

seleksi <- function(populasi, fitness, nseleksi) {

  terbaik <- order(fitness, decreasing=TRUE)[1:nseleksi]

  return(populasi[terbaik, ])

}



# Fungsi untuk crossover

crossover <- function(ambilterbaik) {

  n_genes <- ncol(ambilterbaik)

  half_point <- floor(n_genes / 2)  # Adjust to always be an integer

  

  populasi <- ambilterbaik

  for (t1 in 1:(nrow(ambilterbaik)-1)){

    for (t2 in (t1+1):nrow(ambilterbaik)){

      anak1 <- c(ambilterbaik[t1, 1:half_point], ambilterbaik[t2, (half_point+1):n_genes])

      anak2 <- c(ambilterbaik[t2, 1:half_point], ambilterbaik[t1, (half_point+1):n_genes])

      populasi <- rbind(populasi, anak1, anak2)

    }

  }

  return(populasi)

}



# Fungsi untuk mutasi

mutasi <- function(populasi, j) {

  mutasi = matrix(rbinom(nrow(populasi)*ncol(populasi), 1, 1/(j*10)), 

                  nrow=nrow(populasi), ncol=ncol(populasi))

  return(abs(populasi - mutasi))

}

Iterasi Genetic Algorithm

# Inisialisasi populasi

npop = 5

populasi <- matrix(rbinom(55, 1, 0.2), nrow=npop, ncol=11)



# Algoritma Genetik

simpanfitness = NULL

for (j in 1:50){

  fitness = eval_fitness(populasi, x, y)

  simpanfitness <- c(simpanfitness, mean(fitness))

  ambilterbaik = seleksi(populasi, fitness, 4)

  populasi = crossover(ambilterbaik)

  if (j < 50){

    populasi = mutasi(populasi, j)

  }

}



# Plot fitness

plot(simpanfitness, type="b")

Algoritma Genetika dengan Paket genalg

Algoritma genetika adalah salah satu metode optimasi berbasis heuristic yang terinspirasi oleh proses seleksi alam. Konsep ini mensimulasikan evolusi biologis dengan komponen utama berupa populasi, kromosom, seleksi, crossover (rekombinasi), dan mutasi. Algoritma genetika cocok untuk memecahkan masalah optimasi non-linear dengan ruang solusi yang sangat besar.

Paket genalg di R memfasilitasi implementasi algoritma genetika, mendukung kromosom berbentuk biner (binary chromosome) dan titik-mengambang (floating-point chromosome).

library(genalg)
library(MASS)

Komponen Utama Algoritma Genetika

  1. Representasi Kromosom
    Dalam konteks ini, kromosom direpresentasikan sebagai vektor biner:
    \[ \mathbf{C} = \{c_1, c_2, \dots, c_n\}, \quad c_i \in \{0, 1\}, \quad \forall i = 1, 2, \dots, n \] Setiap gen (\(c_i\)) merepresentasikan pemilihan atau pengecualian fitur tertentu.

  2. Fungsi Fitness
    Fungsi fitness mengevaluasi kualitas setiap kromosom berdasarkan tujuan optimasi. Misalnya, untuk seleksi fitur, fitness dapat berupa \(-R^2_{adj}\) (adjusted R-squared) dari model regresi:
    \[ \text{fitness}(\mathbf{C}) = \begin{cases} -R^2_{adj}(\mathbf{C}) & \text{jika } |\mathbf{C}| > 0 \\ 0 & \text{jika } |\mathbf{C}| = 0 \end{cases} \] Di mana \(R^2_{adj}\) adalah koefisien determinasi yang disesuaikan.

  3. Seleksi
    Seleksi bertujuan memilih kromosom terbaik berdasarkan fitness. Strategi umum adalah roulette wheel selection, di mana peluang seleksi proporsional terhadap fitness.

  4. Crossover
    Crossover menggabungkan dua kromosom (induk) untuk menghasilkan kromosom baru (keturunan). Misalnya, dengan metode satu titik:
    \[ \mathbf{C}_{\text{offspring}} = \mathbf{C}_{\text{parent1}}[1:k] \cup \mathbf{C}_{\text{parent2}}[k+1:n] \]

  5. Mutasi
    Mutasi memperkenalkan variasi acak ke dalam populasi dengan mengubah nilai gen dengan probabilitas tertentu (\(\text{mutationChance}\)):
    \[ c_i' = \begin{cases} 1 - c_i & \text{dengan probabilitas } p_{\text{mutasi}} \\ c_i & \text{dengan probabilitas } 1 - p_{\text{mutasi}} \end{cases} \]

Contoh Implementasi: Seleksi Fitur

Langkah 1: Menyiapkan Dataset Dataset sintetik dengan 10 fitur (\(X_1, X_2, \dots, X_{10}\)) dan satu variabel respons (\(y\)) dapat dibuat sebagai berikut:

set.seed(123)
n <- 100
p <- 10
X <- matrix(rnorm(n * p), ncol = p)
beta <- runif(p, -1, 1)
y <- X %*% beta + rnorm(n)
data <- data.frame(X, y = y)

Langkah 2: Mendefinisikan Fungsi Fitness Fungsi fitness menggunakan regresi linier untuk mengevaluasi subset fitur berdasarkan \(-R^2_{adj}\):

fitness <- function(chromosome) {
  selected <- which(chromosome == 1)
  if (length(selected) == 0) return(0)
  fit <- lm(y ~ ., data = data[, c(selected, ncol(data))])
  return(-summary(fit)$adj.r.squared)
}

Langkah 3: Menjalankan Algoritma Genetika Algoritma dijalankan dengan parameter tertentu, seperti ukuran populasi dan peluang mutasi:

GA_results <- rbga.bin(size = p, popSize = 50, iters = 100, mutationChance = 0.01, evalFunc = fitness)

Hasil dan Visualisasi

Output Algoritma Hasil akhir mencakup informasi tentang solusi terbaik (\(\mathbf{C}^*\)) dan nilai fitness-nya:

GA_results
## $type
## [1] "binary chromosome"
## 
## $size
## [1] 10
## 
## $popSize
## [1] 50
## 
## $iters
## [1] 100
## 
## $suggestions
## NULL
## 
## $population
##       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
##  [1,]    1    1    1    0    1    1    1    1    1     1
##  [2,]    1    1    1    0    1    1    1    1    1     1
##  [3,]    1    1    1    0    1    1    1    1    1     1
##  [4,]    1    1    1    0    1    1    1    1    1     1
##  [5,]    1    1    1    0    1    1    1    1    1     1
##  [6,]    1    1    1    0    1    1    1    1    1     1
##  [7,]    1    1    1    0    1    1    1    1    1     1
##  [8,]    1    1    1    0    1    1    1    1    1     1
##  [9,]    1    1    1    0    1    1    1    1    1     1
## [10,]    1    1    1    0    1    1    1    1    1     1
## [11,]    1    1    1    0    1    1    1    1    1     1
## [12,]    1    1    1    0    1    1    1    1    1     1
## [13,]    1    1    1    0    1    1    1    1    1     1
## [14,]    1    1    1    0    1    1    1    1    1     1
## [15,]    1    1    1    0    1    1    1    1    1     1
## [16,]    1    1    1    0    1    1    1    1    1     1
## [17,]    1    1    1    0    1    1    1    1    1     1
## [18,]    1    1    1    0    1    1    1    1    1     1
## [19,]    1    1    1    0    1    1    1    1    1     1
## [20,]    1    1    1    0    1    1    1    1    1     1
## [21,]    1    1    1    0    1    0    1    1    1     1
## [22,]    1    1    1    0    1    1    1    1    1     1
## [23,]    1    1    1    0    1    1    1    1    1     1
## [24,]    1    1    1    0    1    1    1    1    1     1
## [25,]    1    1    1    0    1    1    1    1    1     1
## [26,]    1    1    1    0    1    1    1    1    1     1
## [27,]    1    1    1    0    1    1    1    1    1     1
## [28,]    1    1    1    0    1    1    1    1    1     1
## [29,]    0    1    1    0    1    1    1    1    1     1
## [30,]    1    1    1    0    1    1    0    1    1     1
## [31,]    1    1    1    0    1    1    1    1    1     1
## [32,]    1    1    1    0    1    1    1    1    1     1
## [33,]    1    1    1    0    1    1    1    1    1     1
## [34,]    1    1    1    0    1    1    1    1    0     1
## [35,]    1    1    1    0    1    1    1    1    1     1
## [36,]    1    1    1    0    1    1    1    1    0     1
## [37,]    1    1    1    0    1    1    1    1    1     1
## [38,]    1    1    1    0    1    1    1    1    1     1
## [39,]    1    1    1    0    1    1    1    1    1     1
## [40,]    1    1    1    0    1    1    1    0    1     1
## [41,]    1    1    1    0    1    1    1    1    1     1
## [42,]    1    1    1    0    1    1    1    1    1     1
## [43,]    1    1    1    0    1    1    1    1    1     1
## [44,]    1    1    1    0    1    1    1    1    1     1
## [45,]    1    1    1    0    1    1    1    1    1     1
## [46,]    1    1    1    0    1    1    1    1    1     1
## [47,]    1    1    1    0    1    1    1    1    1     1
## [48,]    1    1    1    0    1    1    1    1    1     1
## [49,]    1    1    1    0    1    1    1    1    1     1
## [50,]    1    1    1    0    1    1    1    1    1     1
## 
## $elitism
## [1] 10
## 
## $mutationChance
## [1] 0.01
## 
## $evaluations
##  [1] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [7] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
## [13] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
## [19] -0.7715529 -0.7715529 -0.7577728 -0.7715529 -0.7715529 -0.7715529
## [25] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7203688 -0.7689687
## [31] -0.7715529 -0.7715529 -0.7715529 -0.5028571 -0.7715529 -0.7715529
## [37] -0.7715529 -0.7715529 -0.7715529 -0.5339069 -0.7715529 -0.7715529
## [43] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
## [49] -0.7715529 -0.7715529
## 
## $best
##   [1] -0.3001773 -0.3960330 -0.5113361 -0.5113361 -0.6247445 -0.6351578
##   [7] -0.7539872 -0.7646669 -0.7646669 -0.7689687 -0.7689687 -0.7689687
##  [13] -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687
##  [19] -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687
##  [25] -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687
##  [31] -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687 -0.7689687
##  [37] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [43] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [49] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [55] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [61] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [67] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [73] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [79] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [85] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [91] -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529 -0.7715529
##  [97] -0.7715529 -0.7715529 -0.7715529 -0.7715529
## 
## $mean
##   [1] -0.08772023 -0.19255148 -0.27473859 -0.35402961 -0.42193414 -0.47579882
##   [7] -0.56565508 -0.61060513 -0.64408684 -0.69833158 -0.73887399 -0.76018961
##  [13] -0.76832583 -0.76800358 -0.76325351 -0.75257954 -0.75827003 -0.76866997
##  [19] -0.75902680 -0.74692904 -0.75790596 -0.76888267 -0.76385763 -0.76067412
##  [25] -0.75997213 -0.76896871 -0.76375311 -0.76315564 -0.76018483 -0.75762346
##  [31] -0.76237944 -0.76424240 -0.76325351 -0.76540043 -0.76518773 -0.76030805
##  [37] -0.76553815 -0.76622600 -0.76688955 -0.76019322 -0.76439720 -0.74849150
##  [43] -0.76686632 -0.77152003 -0.76694197 -0.76521641 -0.75200723 -0.76418725
##  [49] -0.76854913 -0.76722760 -0.75549226 -0.77155286 -0.77127726 -0.76066205
##  [55] -0.76877188 -0.76671425 -0.77143586 -0.77127726 -0.77155286 -0.76679994
##  [61] -0.76046109 -0.76587663 -0.76672452 -0.75510383 -0.76278253 -0.74658412
##  [67] -0.76602490 -0.76805997 -0.76699525 -0.76534699 -0.77150118 -0.76471395
##  [73] -0.76616305 -0.75650407 -0.76612726 -0.76075335 -0.76708914 -0.76703629
##  [79] -0.77155286 -0.77127726 -0.76885756 -0.76174806 -0.76945381 -0.77039181
##  [85] -0.76545036 -0.75673425 -0.76007644 -0.76830636 -0.77155286 -0.75636556
##  [91] -0.76671425 -0.77127726 -0.76606043 -0.76230960 -0.76075335 -0.76652434
##  [97] -0.76992290 -0.76671425 -0.75873073 -0.76007506
## 
## attr(,"class")
## [1] "rbga"

Visualisasi Proses Optimasi Progres optimasi dapat divisualisasikan dengan:

plot(GA_results)

Grafik ini menunjukkan bagaimana fitness terbaik dan rata-rata dalam populasi meningkat selama iterasi, mencerminkan konvergensi solusi.

Studi Kasus: Dataset Iris

Dataset Iris digunakan untuk mendemonstrasikan kemampuan algoritma genetika dalam seleksi fitur. Dataset ditambahkan variabel acak (noise) untuk mensimulasikan tantangan.

Langkah 1: Persiapan Data

data(iris)
set.seed(123)
X <- cbind(scale(iris[, 1:4]), matrix(rnorm(36 * 150), 150, 36))
Y <- iris[, 5]

Langkah 2: Fitness Function untuk LDA Fungsi fitness menggunakan Linear Discriminant Analysis (LDA) untuk meminimalkan tingkat salah klasifikasi: \[ \text{fitness}(\mathbf{C}) = \begin{cases} 1 - \frac{\text{Jumlah Salah Klasifikasi}}{\text{Total Data}} & \text{jika } |\mathbf{C}| > 2 \\ 1 & \text{lainnya} \end{cases} \] Kode R:

iris.evaluate <- function(indices) {
  result = 1
  if (sum(indices) > 2) {
    huhn <- lda(X[, indices == 1], Y, CV = TRUE)$posterior
    result = sum(Y != colnames(huhn)[apply(huhn, 1, which.max)]) / length(Y)
  }
  result
}

Langkah 3: Menjalankan Algoritma

GA_iris <- rbga.bin(size = 40, popSize = 50, iters = 100, mutationChance = 0.05, evalFunc = iris.evaluate)
plot(GA_iris)

Kesimpulan

  1. Keunggulan Algoritma Genetika
    Algoritma genetika fleksibel dalam menangani masalah optimasi kompleks seperti seleksi fitur dan pengurangan dimensi, terutama dengan data yang memiliki ruang solusi luas.

  2. Hasil Visualisasi
    Plot menunjukkan bahwa algoritma mampu mengkonvergensi menuju solusi optimal dalam jumlah iterasi tertentu.

  3. Aplikasi Lanjut
    Metode ini dapat diperluas untuk berbagai model statistik (misalnya regresi, LDA, atau metode non-linear).