Algoritma Conjugate Gradient

Algoritma Conjugate Gradient adalah salah satu algoritma yang digunakan untuk pengambilan keputusan. Contoh yang dibahas kali ini adalah menentukan hasil jual tipe sepeda motor baru berdasarkan kelompok data yang sudah ada.
Conjugate Gradient dapat digunakan untuk menyelesaikan permasalahan sistem linier dan non-linier
Dalam kasus ini, sistem yang dibahas adalah menggunakan sistem linier
Bentuk persamaan linier yang paling sederhana adalah Ax = b
nilai yang akan dihitung adalah x, sehingga harus diketahui dahulu nilai A dan b
Metode ini mampu melakukan perhitungan yang lebih cepat daripada metode regresi linier,
karena metode ini tidak melakukan perhitungan invers matriks A,
dengan catatan bahwa matriks A harus simetris
dan matriks b harus memliki jumlah baris yang sama dengan matriks A

Diasumsikan ada 4 tipe motor yang sudah diketahui datanya, yaitu Motor A,B,C,D
Masing-masing tipe motor memiliki kriteria, yaitu harga, jarak tempuh per liter, cc, dan memiliki hasil jual dalam unit
Diasumsikan data dari 4 tipe motor tersebut adalah sebagai berikut:

Contoh data awal adalah sebagai berikut:

contohData = [10000000 35 110; ...
              12000000 45 125; ...
              11000000 40 150; ...
              14000000 37.5 125];
          
hasilContohData = [20; ...
                   9; ...
                   17; ...
                   12];

Selanjutnya ada 4 buah motor lagi, yaitu E,F,G,H, yang baru akan diluncurkan, sehingga tidak diketahui hasil jualnya
Maka tentukan data-data ini nantinya diperkirakan memiliki hasil jual berapa unit
Diasumsikan data awalnya adalah sebagai berikut:

Contoh data yang baru adalah sebagai berikut:

dataBaru = [13000000 45 125; ...
            12000000 47 110; ...
            10500000 43 110; ...
            13500000 35 125];

Langkah-langkah penggunaan algoritma ini adalah

1. Hitung matriks input A dengan cara perkalian matriks antara transpos matriks contoh data dan matriks contoh data

A = contohData' * contohData;

2. Hitung matriks input b dengan cara perkalian matriks antara transpos matriks contoh data dan matriks hasil contoh data

b = contohData' * hasilContohData;

3. Lakukan proses pembelajaran data menggunakan metode Conjugate Gradient
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3a – 3e)

x = ConjugateGradient(A, b);

Memasuki perhitungan pada fungsi ConjugateGradient

3a. Beri nilai awal x adalah sama dengan b

x = b;

3b. Hitung nilai r0 dengan rumus:
r0 = b – (A * x0)
Jika nilai norma vektor r0 kurang dari nilai tolerasi, maka hentikan perhitungan

r0 = b - A*x;
if norm(r0) < toleransi
	return
end

3c. Hitung nilai alpha0 dengan rumus:
alpha0 = (r0T * r0) / (p0T * A * p0)

p0 = -r0;
Ap0 = A*p0;
p0TAp0 = p0'*Ap0;
alpha0 = (r0'*p0)/p0TAp0;

3d. Hilai x yang baru dihitung dengan rumus:
x1 = x0 + alpha0 * p0

x = x + alpha0*p0;

* Selanjutnya adalah menghitung nilai residual pada masing-masing elemen b (poin 3e)

3e. Lakukan perhitungan pada masing-masing elemen b (poin 3e1 – 3e4)

for k = 1:numel(b);
. . .

3e1. Hitung nilai r0 dengan rumus:
r1 = r0 – (alpha0 * A * p0)
Jika nilai norma vektor r1 kurang dari nilai tolerasi, maka hentikan perhitungan

r0 = r0 - alpha0*Ap0;
if(norm(r0) < toleransi)
	return;
end

3e2. Hitung nilai beta0 dengan rumus:
beta0 = (r1T * r1) / (r0T * r0)

beta0 = (r0'*Ap0)/p0TAp0;

3e3. Hitung nilai p1 dengan rumus:
p1 = r1 + (beta0 * p0)

p0 = -r0 + beta0*p0;

3e4. Selanjutnya adalah menghitung nilai alpha0 dan x1 yang baru untuk digunakan pada elemen selanjutnya
Rumus untuk menghitung nilai alpha0 dan x1 sudah dijelaskan pada perhitungan sebelumnya

Ap0 = A*p0;
p0TAp0 = p0'*Ap0;
alpha0 = (r0'*p0)/p0TAp0;
x = x + alpha0*p0;

4. Lakukan perhitungan hasil contoh data menggunakan hasil pembelajaran yang sudah ada

hasilPerhitunganContohData = contohData * x;

5. Hitung rata-rata selisih dari hasil contoh data yang asli dengan hasil contoh data menggunakan perhitungan tersebut

rata2delta = sum((hasilContohData - hasilPerhitunganContohData)) / size(hasilContohData,1);

6. Lakukan perhitungan prediksi pada data yang baru
Kemudian tambahkan nilai delta untuk mendapatkan jawaban akhir

hasilPerhitunganDataBaru = dataBaru * x + rata2delta;

Hasil akhir adalah:

Algoritma Conjugate Gradient
Contoh: memperkirakan hasil jual tipe sepeda motor baru berdasarkan kelompok data yang sudah ada
Diasumsikan ada 4 tipe motor yang sudah diketahui datanya, yaitu Motor A,B,C,D
Masing-masing tipe motor memiliki kriteria, yaitu harga, jarak tempuh per liter, cc, dan memiliki hasil jual dalam unit
Diasumsikan data dari 4 tipe motor tersebut adalah sebagai berikut:
Motor  , Harga     , Jarak tempuh per liter, cc , hasil jual
Motor A, 10.000.000, 35                    , 110, 20
Motor B, 12.000.000, 45                    , 125, 9
Motor C, 11.000.000, 40                    , 150, 17
Motor D, 14.000.000, 37.5                  , 125, 12


Selanjutnya ada 4 buah motor lagi, yaitu E,F,G,H, yang baru akan diluncurkan, sehingga tidak diketahui hasil jualnya
Maka tentukan data-data ini nantinya diperkirakan memiliki hasil jual berapa unit
Diasumsikan data awalnya adalah sebagai berikut:
Motor  , Harga     , Jarak tempuh per liter, cc
Motor E, 13.000.000, 45                    , 125
Motor G, 12.000.000, 47                    , 110
Motor F, 10.500.000, 43                    , 110
Motor H, 13.500.000, 35                    , 125


Hasil Perhitungan dengan metode Conjugate Gradient
Motor  , Harga     , Jarak tempuh per liter, cc , prediksi hasil jual
Motor E, 13000000  , 45                    , 125, 30
Motor F, 12000000  , 47                    , 110, 47
Motor G, 10500000  , 43                    , 110, 39
Motor H, 13500000  , 35                    , 125, -2

Contoh modul / source code menggunakan Matlab dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.