Metode-Metode Optimisasi
Adam Syarifani Muhammad
2023-11-12
library(mosaicCalc)## Loading required package: mosaic## Registered S3 method overwritten by 'mosaic':
## method from
## fortify.SpatialPolygonsDataFrame ggplot2##
## The 'mosaic' package masks several functions from core packages in order to add
## additional features. The original behavior of these functions should not be affected by this.##
## Attaching package: 'mosaic'## The following objects are masked from 'package:dplyr':
##
## count, do, tally## The following object is masked from 'package:Matrix':
##
## mean## The following object is masked from 'package:ggplot2':
##
## stat## The following objects are masked from 'package:stats':
##
## binom.test, cor, cor.test, cov, fivenum, IQR, median, prop.test,
## quantile, sd, t.test, var## The following objects are masked from 'package:base':
##
## max, mean, min, prod, range, sample, sum## Loading required package: mosaicCore##
## Attaching package: 'mosaicCore'## The following objects are masked from 'package:dplyr':
##
## count, tally##
## Attaching package: 'mosaicCalc'## The following object is masked from 'package:stats':
##
## DBerikut adalah beberapa metode optimisasi dan contoh kode dalam bahasa R:
Metode Gradien Turun (Gradient Descent)
Gradient Descent adalah proses yang terjadi pada fase backpropagation di mana tujuannya adalah untuk secara terus-menerus mengubah gradien parameter model dalam arah yang berlawanan berdasarkan bobot w, memperbarui secara konsisten hingga kami mencapai fungsi global minimum J (w).
Berikut contoh penerapan Gradient Descent:
gradientDesc <- function(x, y, learn_rate, conv_threshold, n, max_iter) {
plot(x, y, col = "red", pch = 20)
m <- runif(1, 0, 1)
c <- runif(1, 0, 1)
yhat <- m * x + c
MSE <- sum((y - yhat) ^ 2) / n
converged = F
iterations = 0
while(converged == F) {
m_new <- m - learn_rate * ((1 / n) * (sum((yhat - y) * x)))
c_new <- c - learn_rate * ((1 / n) * (sum(yhat - y)))
m <- m_new
c <- c_new
yhat <- m * x + c
MSE_new <- sum((y - yhat) ^ 2) / n
if(MSE - MSE_new <= conv_threshold) {
abline(c, m)
converged = T
return(paste("Optimal intercept:", c, "Optimal slope:", m))
}
iterations = iterations + 1
if(iterations > max_iter) {
abline(c, m)
converged = T
return(paste("Optimal intercept:", c, "Optimal slope:", m))
}
}
}
# Memanggil fungsi
disp <- c(1, 2, 3, 4, 5)
mpg <- c(15, 20, 25, 30, 35)
gradientDesc(disp, mpg, 0.0000293, 0.001, 32, 2500000)
## [1] "Optimal intercept: 8.90887065599583 Optimal slope: 5.30222533197385"Metode Nelder-Mead
Metode Nelder–Mead (metode simpleks downhill, metode amuba , atau metode polytope) adalah metode numerik yang umum diterapkan yang digunakan untuk menemukan minimum atau maksimum fungsi tujuan dalam ruang multidimensi. Ini adalah metode pencarian langsung (berdasarkan perbandingan fungsi) dan sering diterapkan pada masalah optimasi nonlinier yang turunannya mungkin tidak diketahui. Namun, teknik Nelder–Mead merupakan metode pencarian heuristik yang dapat konvergen ke titik-titik non-stasioner pada masalah yang dapat diselesaikan dengan metode alternatif.
Berikut contoh penerapan Metode Nelder-Mead:
library(stats)
f <- function(x) {
return((x[1] - 1)^2 + (x[2] - 2)^2)
}
result <- optim(par = c(0, 0), fn = f, method = "Nelder-Mead")
# Memanggil fungsi
cat("Optimal Parameters:", result$par, "\n")## Optimal Parameters: 1.000106 1.999859cat("Optimal Value:", result$value, "\n")## Optimal Value: 3.095176e-08Metode Quasi-Newton
Metode Quasi-Newton adalah kelas algoritma optimasi numerik yang digunakan untuk mencari fungsi minimum atau maksimum. Ini adalah generalisasi dari metode Newton, yang menggunakan matriks turunan kedua Hessian untuk memperkirakan kelengkungan lokal suatu fungsi. Metode Quasi-Newton menggunakan versi perkiraan matriks Hessian yang diperbarui seiring berjalannya algoritma. Hal ini memungkinkan algoritme untuk lebih cepat konvergen ke titik optimal tanpa perlu menghitung matriks Hessian secara lengkap. Metode kuasi-Newton yang paling umum digunakan adalah Broyden – Fletcher – Goldfarb – Shanno (BFGS) dan BFGS memori terbatas (L-BFGS).
Berikut contoh penerapan Metode Quasi-Newton:
library(stats)
# Fungsi objektif yang ingin dioptimalkan
f <- function(x) {
return((x[1] - 1)^2 + (x[2] - 2)^2)
}
result <- optim(par = c(0, 0), fn = f, method = "BFGS", hessian = TRUE)
# Menampilkan hasil optimisasi
cat("Optimal Parameters:", result$par, "\n")## Optimal Parameters: 1 2cat("Optimal Value:", result$value, "\n")## Optimal Value: 6.357135e-26Algoritma Genetika
Metode Algoritma Genetika merupakan metode yang dapat menyelesaikan persoalan dalam penyusunan penjadwalan perkuliahan. Algoritma Genetika diperoleh berdasarkan fenomena biologis evolusi genetika. Tujuan dari algoritma ini adalah untuk membuat populasi konvergen ke populasi akhir di mana individu berkinerja terbaik akan sedekat mungkin dengan solusi optimal dari masalah.
Berikut contoh penerapan Algoritma Genetika:
# Install dan load library 'GA' untuk Algoritma Genetika
if (!requireNamespace("GA", quietly = TRUE)) {
install.packages("GA")
}
library(GA)## Loading required package: foreach## Loading required package: iterators## Package 'GA' version 3.2.3
## Type 'citation("GA")' for citing this R package in publications.##
## Attaching package: 'GA'## The following object is masked from 'package:utils':
##
## de# Definisi fungsi yang ingin dioptimalkan
fitness <- function(x) {
return(sum(x^2))
}
# Menjalankan optimasi dengan Algoritma Genetika
result <- ga(type = "real-valued", fitness = fitness, lower = -5.12, upper = 5.12, popSize = 50, maxiter = 100)
# Menampilkan hasil optimal
cat("Optimal Parameters:", result@solution, "\n")## Optimal Parameters: 5.11038cat("Optimal Value:", result@fitnessValue, "\n")## Optimal Value: 26.11599Metode Simulated Annealing
Simulated annealing adalah algoritma pencarian lokal (meta-heuristic) yang mampu mendapatkan hasil secara optimal dari suatu area. Kemudahan implementasi, sifat konvergensi dan penggunaannya menjadikan metode ini telah menjadi teknik yang populer dalam dua dekade terakhir. Simulated annealing merupakan metode searching yang memanfaatkan teori probabilitas untuk mencari global minimum dari suatu permasalahan optimasi.
Berikut contoh penerapan Metode Simulated Annealing:
# Fungsi yang ingin dioptimalkan
fitness <- function(x) {
return(sum(x^2))
}
# Menentukan batas bawah dan atas
lower_bound <- rep(-5.12, 10)
upper_bound <- rep(5.12, 10)
# Memanggil fungsi optim
result <- optim(par = runif(10, min = lower_bound, max = upper_bound),
fn = fitness,
method = "L-BFGS-B",
lower = lower_bound,
upper = upper_bound)
# Menampilkan hasil optimal
cat("Optimal Parameters:", result$par, "\n")## Optimal Parameters: -8.468409e-22 4.108096e-20 2.117492e-21 3.812082e-21 -1.05877e-20 2.498735e-20 -1.058736e-20 6.776202e-21 4.658784e-21 -6.352615e-21cat("Optimal Value:", result$value, "\n")## Optimal Value: 2.663914e-39Metode Pencarian Hukum (Tabu Search)
Algoritma tabu search adalah sebuah metode optimasi yang berbasis pada local search. Algoritma tabu search digunakan untuk mencari solusi yang bergerak ke solusi berikutnya dengan cara memilih solusi yang terdekat dan tidak dilarang atau tabu. Algoritma tabu search juga banyak digunakan kasus penelitian seperti melakukan penjadwaan, pemilihan rute terbaik, tata letak tempat dan lain sebagainya.
Algoritma Levenberg-Marquardt
Algoritma Levenberg Marquardt digunakan untuk pelatihan feedforward neural network karena keefektifan dan kecepatan konvergensinya. Levenberg Marquardt merupakan metode optimasi nonlinier yang digunakan pada saat koreksi error backpropagation untuk menemukan bobot yang disesuaikan.
Metode Penurunan Koordinat (Coordinate Descent)
Metode Penurunan Koordinat (Coordinate Descent) adalah algoritma optimasi yang meminimalkan secara berturut-turut sepanjang arah koordinat untuk mencari nilai minimum suatu fungsi. Pada setiap iterasi, algoritme menentukan koordinat atau blok koordinat melalui aturan pemilihan koordinat, kemudian meminimalkan secara tepat atau tidak tepat pada hyperplane koordinat yang sesuai sambil memperbaiki semua koordinat atau blok koordinat lainnya.
Berikut contoh penerapan Metode Penurunan Koordinat (Coordinate Descent):
# Fungsi objektif
objective_function <- function(x, y) {
return(x^2 + y^2)
}
coordinate_descent <- function(starting_point, learn_rate, tol, max_iter) {
x <- starting_point[1]
y <- starting_point[2]
iter <- 0
while (iter < max_iter) {
x = x - learn_rate * 2 * x
y = y - learn_rate * 2 * y
obj_val = objective_function(x, y)
cat("Iteration:", iter, " x:", x, " y:", y, " Objective Value:", obj_val, "\n")
if (obj_val < tol) {
break
}
iter = iter + 1
}
return(c(x, y))
}
# Memanggil fungsi
starting_point <- c(3, 4)
learn_rate <- 0.1
tol <- 1e-6
max_iter <- 1000
result <- coordinate_descent(starting_point, learn_rate, tol, max_iter)## Iteration: 0 x: 2.4 y: 3.2 Objective Value: 16
## Iteration: 1 x: 1.92 y: 2.56 Objective Value: 10.24
## Iteration: 2 x: 1.536 y: 2.048 Objective Value: 6.5536
## Iteration: 3 x: 1.2288 y: 1.6384 Objective Value: 4.194304
## Iteration: 4 x: 0.98304 y: 1.31072 Objective Value: 2.684355
## Iteration: 5 x: 0.786432 y: 1.048576 Objective Value: 1.717987
## Iteration: 6 x: 0.6291456 y: 0.8388608 Objective Value: 1.099512
## Iteration: 7 x: 0.5033165 y: 0.6710886 Objective Value: 0.7036874
## Iteration: 8 x: 0.4026532 y: 0.5368709 Objective Value: 0.45036
## Iteration: 9 x: 0.3221225 y: 0.4294967 Objective Value: 0.2882304
## Iteration: 10 x: 0.257698 y: 0.3435974 Objective Value: 0.1844674
## Iteration: 11 x: 0.2061584 y: 0.2748779 Objective Value: 0.1180592
## Iteration: 12 x: 0.1649267 y: 0.2199023 Objective Value: 0.07555786
## Iteration: 13 x: 0.1319414 y: 0.1759219 Objective Value: 0.04835703
## Iteration: 14 x: 0.1055531 y: 0.1407375 Objective Value: 0.0309485
## Iteration: 15 x: 0.08444249 y: 0.11259 Objective Value: 0.01980704
## Iteration: 16 x: 0.06755399 y: 0.09007199 Objective Value: 0.01267651
## Iteration: 17 x: 0.0540432 y: 0.07205759 Objective Value: 0.008112964
## Iteration: 18 x: 0.04323456 y: 0.05764608 Objective Value: 0.005192297
## Iteration: 19 x: 0.03458765 y: 0.04611686 Objective Value: 0.00332307
## Iteration: 20 x: 0.02767012 y: 0.03689349 Objective Value: 0.002126765
## Iteration: 21 x: 0.02213609 y: 0.02951479 Objective Value: 0.001361129
## Iteration: 22 x: 0.01770887 y: 0.02361183 Objective Value: 0.0008711229
## Iteration: 23 x: 0.0141671 y: 0.01888947 Objective Value: 0.0005575186
## Iteration: 24 x: 0.01133368 y: 0.01511157 Objective Value: 0.0003568119
## Iteration: 25 x: 0.009066944 y: 0.01208926 Objective Value: 0.0002283596
## Iteration: 26 x: 0.007253555 y: 0.009671407 Objective Value: 0.0001461502
## Iteration: 27 x: 0.005802844 y: 0.007737125 Objective Value: 9.35361e-05
## Iteration: 28 x: 0.004642275 y: 0.0061897 Objective Value: 5.986311e-05
## Iteration: 29 x: 0.00371382 y: 0.00495176 Objective Value: 3.831239e-05
## Iteration: 30 x: 0.002971056 y: 0.003961408 Objective Value: 2.451993e-05
## Iteration: 31 x: 0.002376845 y: 0.003169127 Objective Value: 1.569275e-05
## Iteration: 32 x: 0.001901476 y: 0.002535301 Objective Value: 1.004336e-05
## Iteration: 33 x: 0.001521181 y: 0.002028241 Objective Value: 6.427752e-06
## Iteration: 34 x: 0.001216945 y: 0.001622593 Objective Value: 4.113761e-06
## Iteration: 35 x: 0.0009735557 y: 0.001298074 Objective Value: 2.632807e-06
## Iteration: 36 x: 0.0007788445 y: 0.001038459 Objective Value: 1.684997e-06
## Iteration: 37 x: 0.0006230756 y: 0.0008307675 Objective Value: 1.078398e-06
## Iteration: 38 x: 0.0004984605 y: 0.000664614 Objective Value: 6.901746e-07cat("Optimal Point:", result, "\n")## Optimal Point: 0.0004984605 0.000664614