Menyelesaikan Sistem Persamaan Linear dengan Metode Eksak dan Meta Heuristic

Tahun lalu, saya sempat menulis tentang bagaimana menyelesaikan suatu sistem persamaan linear (SPL) dengan mudah dengan R.

Saya baru menyadari bahwa saya belum pernah sama sekali membahas terkait SPL pada blog saya ini. Oleh karena itu, saya akan coba ulas secara simpel bagaimana kita mencari solusi dari SPL dengan berbagai macam cara.

Misalkan saya memiliki suatu SPL sebagai berikut:

Kita akan mencari solusi yang memenuhi SPL di atas.

Setidaknya ada dua metode atau pendekatan yang bisa dilakukan untuk mencari solusi dari SPL, yakni:

1. Metode eksak, dan
2. Metode meta heuristic.

Metode eksak adalah metode yang berdasarkan pendekatan matematis sedangkan metode meta heuristic berdasarkan pendekatan yang terinspirasi dari natural events seperti yang saya bahas pada tulisan sebelumnya (black hole dan spiral dynamic).

Metode Eksak

Untuk menyelesaikan SPL dengan metode eksak, ada banyak sekali caranya. Kali ini saya akan membahas dua cara, yakni:

1. Invers matriks, dan
2. Iterasi Jacobi.

Invers Matriks

Cara ini adalah cara yang paling populer diketahui oleh banyak orang. Suatu SPL bisa dibuat dalam bentuk perkalian matriks dengan vektor sebagai berikut:

Dikatakan memiliki solusi jika memiliki invers.

Maka untuk mencari kita cukup mencari invers dari matriks , sehingga:

Maka untuk contoh soal di atas, kita bisa melakukan hal berikut di R:

A = matrix(c(4,-1,1,4,-8,1,-2,1,5),byrow = T,nrow = 3)
b = c(7,-21,15)

A_inv = solve(A)

# solusi
A_inv %*% b

##      [,1]
## [1,]    2
## [2,]    4
## [3,]    3

Iterasi Jacobi

Cara berikutnya adalah dengan membuat iterasi Jacobi berdasarkan formula per variabel . Salah satu syarat agar bisa melakukan iterasi ini adalah dengan membuat bentuk dominan diagonal. Yakni, masing-masing variabel harus memiliki konstanta terbesar. Bentuk formulanya adalah sebagai berikut:

Lantas bentuk iterasinya adalah sebagai berikut:

Dengan mengambil sebarang nilai , diharapkan iterasi Jacobi akan mengantarkan kita ke nilai solusinya.

Misalkan kita gunakan nilai awal .

# set initial values
x = c(10)
y = c(20)
z = c(30)

# menentukan berapa iterasi maksimal
max_iter = 20

# melakukan iterasi
for(i in 2:max_iter){
  x[i] = (7 + y[i-1] - z[i-1])/(4)
  y[i] = (21 + 4 * x[i-1] + z[i-1])/(8)
  z[i] = (15 + 2 * x[i-1] - y[i-1])/(5)
}

data.frame(x,y,z)

##            x         y         z
## 1  10.000000 20.000000 30.000000
## 2  -0.750000 11.375000  3.000000
## 3   3.843750  2.625000  0.425000
## 4   2.300000  4.600000  4.012500
## 5   1.896875  4.276562  3.000000
## 6   2.069141  3.948437  2.903437
## 7   2.011250  4.022500  3.037969
## 8   1.996133  4.010371  3.000000
## 9   2.002593  3.998066  2.996379
## 10  2.000422  4.000844  3.001424
## 11  1.999855  4.000389  3.000000
## 12  2.000097  3.999927  2.999864
## 13  2.000016  4.000032  3.000053
## 14  1.999995  4.000015  3.000000
## 15  2.000004  3.999997  2.999995
## 16  2.000001  4.000001  3.000002
## 17  2.000000  4.000001  3.000000
## 18  2.000000  4.000000  3.000000
## 19  2.000000  4.000000  3.000000
## 20  2.000000  4.000000  3.000000

Terlihat bahwa semakin banyak iterasi dilakukan, nilai yang awalnya sembarang menjadi semakin konvergen menuju solusi.

Metode Meta Heuristic

Pada metode meta heuristic ini, saya akan gunakan big bang - black hole optimization algorithm yang saya pernah tuliskan sebelumnya. Tentunya dengan memodifikasi bentuk SPL menjadi:

= 4x - y + z - 7

= 4x - 8y + z + 21

= -2x + y + 5z - 15

menjadi masalah memaksimalkan fungsi berikut:

Berikut adalah algoritmanya:

# fungsi objective
F = function(vec){
  h1 = 4 * vec[1] - vec[2] + vec[3] - 7
  h2 = 4 * vec[1] - 8 * vec[2] + vec[3] + 21
  h3 = -2 * vec[1] + vec[2] + 5 * vec[3] - 15
  alpha = 1
  F_total = 1 + alpha * h1^2 + alpha * h2^2 + alpha * h3^2
  return(1 / F_total)
}

# definisi big bang function
big_bang = function() runif(3,0,10)

# definisi
# berapa banyak bintang
N = 900
stars = vector("list",N)
# rumah untuk F
fxi = rep(0,N)
# berapa banyak iterasi
max_iter = 300

# tahap I
# membuat bintang
for(i in 1:N){
  stars[[i]] = big_bang()
  fxi[i] = F(stars[[i]])
}

# tahap II
# menentukan black hole
n_bh = which.max(fxi)
bh = stars[[n_bh]]
f_bh = fxi[n_bh]

# tahap III
# iterasi Big Bang - BHO
for(ikanx in 1: max_iter){
  # menghitung radius event horizon
  r = f_bh / sum(fxi)

  # memakan bintang berjarak kurang dari r
  jarak = abs(fxi - f_bh)
  n_luar = which(jarak >= r)

  # stars yang masih ada
  stars = stars[n_luar]

  # jika jumlah stars < N, kita lakukan big bang lagi
  n_stars = length(stars)
  if(n_stars < N){
    for(i in (n_stars + 1):N){
    stars[[i]] = big_bang()
    fxi[i] = F(stars[[i]])
    }
    }

  # gravity rate
  g = runif(2,0,1.5)

  # proses penarikan bintang
  for(j in 1:N){
    xt = stars[[j]]
    xt_new = bh + g * (xt - bh)
    fxi[j] = F(xt_new)
    stars[[j]] = xt_new
  }

  # mencari black hole lagi
  n_bh = which.max(fxi)
  bh = stars[[n_bh]]
  f_bh = fxi[n_bh]
}

# menuliskan solusi
n_sol = which.max(fxi)
stars[[n_sol]]

## [1] 2.037021 4.018342 2.987137

fxi[n_sol]

## [1] 0.9725758

---

Summary

Banyak cara bisa dilakukan untuk menyelesaikan SPL. Saya sendiri lebih suka menggunakan metode invers matriks karena lebih simpel. Tapi untuk kasus SPL dengan bentuk matriks yang lebih kompleks dan tidak bisa dibentuk menjadi dominan diagonal, penyelesaian dengan metode meta heuristic akan sangat membantu sekali.