Algoritma Levenberg–Marquardt / Levenberg-Marquardt-Fletcher

Entri ini telah di terbitkan di Algoritma Peramalan / Prediksi dan telah ditandai algoritma levenberg-marquardt levenberg-marquardt-fletcher lmf matlab on sebesar

Algoritma Levenberg–Marquardt adalah salah satu algoritma yang digunakan untuk memperkirakan hasil berikutnya berdasarkan data-data yang sudah ada sebelumnya. Contoh yang dibahas kali ini adalah mengenai memperkirakan penjualan pada periode berikutnya berdasarkan data penjualan pada periode sebelumnya.
Algoritma ini biasa digunakan dalam menyelesaikan permasalahan nonlinier yang menggunakan prinisip pencarian nilai minimum berdasarkan jumlah kuadrat terendah. Proses ini biasanya ditemukan dalam kasus penyesuaian data ke dalam sebuah kurva.
Dalam kasus penerapannya ke dalam pemrograman, algoritma Levenberg–Marquardt kemudian dimodifikasi untuk diterjemahkan ke dalam bahasa pemrograman FORTRAN oleh Fletcher, sehingga algoritma ini terkadang disebut juga sebagai algoritma Levenberg–Marquardt-Fletcher



Diasumsikan ada 4 data barang yang sudah diketahui hasil penjualannya
Masing-masing barang memiliki data penjualan pada 5 periode sebelumnya
Maka tentukan prediksi penjualan untuk 3 periode berikutnya
Diasumsikan data penjualan adalah sebagai berikut:

Nama BarangPeriode1Periode2Periode3Periode4Periode5
Pensil101281120
Penghapus1512131414
Pena97151510
Penggaris1241213

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:

data=[10 12 8 11 20; ...
      15 12 13 14 14; ...
      9 7 15 15 10; ...
      1 2 4 12 13];



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan persamaan Non-linier yang digunakan

fx = @(x) sqrt(-1*x(1)*x(1) + -0.5*x(2)*x(2) + 0.5*x(3)*x(3) + 0.75*x(4)*x(4) + x(5)*x(5));

* Tentukan batas toleransi selisih data dan batas toleransi nilai fungsi yang diperbolehkan
Diasumsikan dalam kasus ini, batas toleransi selisih data adalah 0.0000001,
dan batas toleransi selisih nilai fungsi adalah 0.0000001

epsX  = 1e-7;
epsFX = 1e-7;

* Tentukan nama fungsi yang digunakan untuk menghitung matriks Jacobian
Metode yang digunakan adalah penaksiran Jacobian dengan selisih terbatas

jacobian = 'finiteJacobian';

* Tentukan jumlah iterasi yang digunakan dalam perhitungan
Diasumsikan dalam kasus ini, jumlah iterasi adalah 500 kali

maksIterasi = 500;

* Tentukan bobot selisih minimal dan maksimal untuk nantinya dibandingkan dengan selisih output
Diasumsikan dalam kasus ini, bobot selisih minimal adalah 0.25 dan bobot selisih maksimal adalah 0.75

minBobotSelisih  = 0.25;
maksBobotSelisih = 0.75;

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan perhitungan pada masing-masing data (poin 1 – 2)

for i=1:size(data,1)
. . .

1. Lakukan proses perhitungan dengan menggunakan metode Levenberg-Marquardt
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1a – 1c)

output = LMF(fx,data(i,:)', epsX, ...
			 epsFX, jacobian, maksIterasi, minBobotSelisih, maksBobotSelisih);

Memasuki perhitungan pada fungsi LMF

1a. Lakukan inisialisasi variabel yang digunakan dalam perhitungan (poin 1a1 – 1a7)

1a1. Tentukan jumlah data yang dihitung, yaitu sama dengan banyak data pada parameter data
Kemudian lakukan inisialisasi parameter epsX sebanyak jumlah data

jumlahData = length(data);
epsX       = epsX * ones(jumlahData,1);

1a2. Beri nilai awal lambda dengan angka 0 dan lambdaC dengan angka 1

lambda     = 0;
lambdaC    = 1;

1a3. Hitung nilai output menggunakan fungsi yang sudah ditentukan sebelumnya

outputData = feval(fungsi,data);

1a4. Hitung jumlah kuadrat dari output data, yaitu kuadrat dari masing-masing elemen dalam output data

jumlahKuadratOutputData = outputData'*outputData;

1a5. Lakukan perhitungan untuk menghitung nilai JTJ dan JTOutput
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini

[JTJ,JTOutput] = HitungJTJJTOutput(fungsi,jacobian,data,outputData,epsX);

* Gunakan fungsi ini untuk menghitung nilai JTJ dan JTOutput
matriks Jacobian (J) dihitung menggunakan fungsi Jacobian

function [JTJ,JTOutput] = HitungJTJJTOutput(fungsi,jacobian,data,outputData,epsX)
if isa(jacobian,'function_handle')
    J = jacobian(data);
else
    J = feval(jacobian,fungsi,outputData,data,epsX);
end
JTJ = J'*J;
JTOutput = J'*outputData;

* Gunakan fungsi ini untuk melakukan linierisasi pada fungsi non-linier,
Teknik yang digunakan adalah diferensiasi kompleks dengan metode Jacobian

function J = finiteJacobian(fungsi,outputData,data,epsX)
jumlahData = length(data);
J  = zeros(length(outputData),jumlahData);

for k = 1:jumlahData
    deltaX = .25 * epsX(k);
    if deltaX==0, deltaX=eps; end
    xData = data;
    xData(k) = xData(k) + deltaX;
    outputTerhitung = feval(fungsi,xData);
    
    J(:,k)=((outputTerhitung(:)-outputData(:))/deltaX);
end

1a6. Hitung nilai skala kontrol D, yaitu nilai diagonal dari JTJ
Kemudian hitung akar dari skala tersebut

skalaD = diag(JTJ);
skalaD(skalaD<=0)=1;
akarSkalaD = sqrt(skalaD);

1a7. Beri nilai awal untuk jumlah iterasi dan jumlah iterasi delta yang akan dilakukan

iterasi = 0;
iterasiDeltaJumlahKuadrat = 1;

* Lakukan proses perhitungan untuk menghitung nilai output (poin 1b)

1b. Lakukan perhitungan sampai salah satu kondisi terpenuhi (poin 1b1 – 1b5)

while 1
. . .

1b1. Simpan nilai diagonal dari matriks JTJ untuk digunakan dalam perhitungan selanjutnya

diagJTJ = diag(JTJ);

1b2. Lakukan perhitungan sampai selisih nilai output data dan output terhitung sudah kurang dari batas toleransi selisih data (poin 1b2a – 1b2l)

while 1
. . .

1b2a. Lakukan faktorisasi matriks JTJ menggunakan teknik Cholesky sampai variabel p bernilai 0
Jika variabel p belum bernilai 0, maka nilai lambda pada perulangan berikutnya akan dikalikan 2

while 1
	UA = triu(JTJ,1);
	JTJ = UA' + UA + diag(diagJTJ+lambda*skalaD);
	[U,p] = chol(JTJ);            
	if p==0, break, end
	
	lambda = 2*lambda;
	if lambda==0, lambda=1; end
end

1b2b. Hitung nilai deltaX, kemudian hitung bobot dari matriks JTOutput
Jika bobot matriks JTOutput bernilai kurang dari 0, maka hentikan perhitungan

deltaX = U\(U'\JTOutput);
bobotJTOutput = deltaX'*JTOutput;
if bobotJTOutput<=0, break, end

1b2c. Lakukan perhitungan pada masing-masing data
Hitung nilai z, kemudian hitung nilai deltaS dengan rumus:
ds = 2 * JTOutput – z

for i=1:jumlahData
	z = diagJTJ(i)*deltaX(i);
	if i>1, z=JTJ(i,1:i-1)*deltaX(1:i-1)+z; end
	if i<jumlahdata, z="JTJ(i+1:jumlahData,i)'*deltaX(i+1:jumlahData)+z;" end="" deltas(i)="2*JTOutput(i)-z;" <="" pre="">

1b2d. Hitung nilai deltaQ dengan cara mengalikan setiap elemen deltaS dengan deltaX

deltaQ = deltaS'*deltaX;

1b2e. Hitung nilai deltaS yang baru, yaitu selisih antara dawa awal dengan deltaX
Kemudian hitung nilai output dari deltaS menggunakan fungsi Jacobian

deltaS = data-deltaX;
outputTerhitung = feval(fungsi,deltaS);

1b2f. Hitung jumlah kuadrat dari masing-masing elemen dalam output terhitung
Kemudian hitung selisih dari jumlah kuadrat output data dengan jumlah kuadrat output terhitung

jumlahKuadratOutputTerhitung = outputTerhitung'*outputTerhitung;
deltaOutput  = jumlahKuadratOutputData-jumlahKuadratOutputTerhitung;

1b2g. Hentikan perhitungan apabila semua nilai elemen deltaX lebih rendah dari batas toleransi selisih data
atau jumlah iterasi yang dilakukan sudah melebihi batas maksimal perulangan
atau nilai selisih output jumlah kuadrat kurang dari batas toleransi selisih nilai fungsi

isSelesai = 1;
if all((abs(deltaX)-epsX)<=0) || iterasiDeltaJumlahKuadrat>=maksIterasi || abs(deltaOutput)<=epsFX
	break
end        
isSelesai = 0;

1b2h. Jika kondisi sebelumnya tidak terpenuhi, lanjutkan ke pengecekan kedua
Hentikan perhitungan apabila selisih output lebih dari bobot minimal selisih dikali dengan deltaQ

if deltaOutput>=minBobotSelisih*deltaQ, break, end

1b2i. Hitung nilai JTJ yang baru, variabel y dan variabel z
Nantinya variabel y akan digunakan untuk mengupdate nilai lambda yang baru

JTJ = U;
y = .5;
z = 2*bobotJTOutput-deltaOutput;
if z>0, y=bobotJTOutput/z; end
if y>.5, y=.5; end
if y<.1, y=.1; end

1b2j. Jika faktorisasi dengan teknik Cholesky pada perhitungan sebelumnya langsung menghasilkan p = 0,
maka lakukan perhitungan dibawah ini untuk mendapatkan nilai lambda (poin 1b2j1 – 1b2j4)

if lambda==0
. . .

1b2j1. Hitung nilai y yang baru, yaitu 2 kali dari y sekarang

y = 2*y;

1b2j2. Lakukan perhitungan untuk mendapatkan nilai JTJ yang baru

for i = 1:jumlahData
	JTJ(i,i) = 1/JTJ(i,i);
end

for i = 2:jumlahData
	ii = i-1;
	for j= 1:ii
		JTJ(j,i) = -JTJ(j,j:ii)*JTJ(j:ii,i).*JTJ(i,i);
	end
end

for i = 1:jumlahData
	for j= i:jumlahData
		JTJ(i,j) = abs(JTJ(i,j:jumlahData)*JTJ(j,j:jumlahData)');
	end
end

1b2j3. Lakukan perhitungan pada masing-masing data
Hitung nilai z, kemudian cari nilai z tertinggi untuk dijadikan sebagai nilai lambda

lambda = 0;
for i = 1:jumlahData
	z = JTJ(1:i,i)'*akarSkalaD(1:i)+z;
	if ilambda, lambda=z; end
end

1b2j4. Hitung nilai jumlah perkalian antara setiap elemen pada diagonal JTJ yang baru dengan skala kontrol D
Jika nilai ini kurang dari nilai lambda yang telah ditemukan, maka ambil nilai ini sebagai nilai lambda yang baru
Kemudian hitung nilai lambda dan lambdaC yang baru dengan cara angka 1 dibagi dengan lambda sekarang

tr = diag(JTJ)'*skalaD;
if tr<lambda, lambda="tr;" end="" lambdac="lambda;" <="" pre="">

1b2k. Hitung nilai lambda yang baru dengan membagi nilai lambda sebelumnya dengan variabel y

lambda = lambda/y;

1b2l. Hentikan perhitungan apabila nilsi selisih output sudah lebih dari 0

if deltaOutput>0, deltaOutput=-1e300; break, end

1b3. Hentikan perhitungan apabila memenuhi salah satu syarat sebelumnya,
yaitu apabila semua nilai elemen deltaX lebih rendah dari batas toleransi selisih data
atau jumlah iterasi yang dilakukan sudah melebihi batas maksimal perulangan
atau nilai selisih output jumlah kuadrat kurang dari batas toleransi selisih nilai fungsi

if isSelesai, break, end

1b4. Jika nilai selisih output lebih dari bobot selisih maksimal dikali dengan deltaQ,
maka nilai lambda akan dibagi dengan 2,
dan apabila nilainya kurang dari nilai lambdaC, maka nilai lambda akan dikembalikan menjadi 0

if deltaOutput > maksBobotSelisih*deltaQ
	lambda = lambda/2;
	if lambda < lambdaC, lambda=0; end
end

1b5. Sebelum menuju ke perulangan berikutnya,
Gunakan nilai deltaS untuk menggantikan nilai data,
nilai output terhitung menggantikan nilai output data
nilai jumlah kuadrat dari output terhitung untuk menggantikan nilai jumlah kuadrat output data
kemudian hitung nilai JTJ dan JTOutput menggunakan nilai data dan output data yang baru

data=deltaS;
outputData=outputTerhitung;
jumlahKuadratOutputData=jumlahKuadratOutputTerhitung;
[JTJ,JTOutput] = HitungJTJJTOutput(fungsi,jacobian,data,outputData,epsX);

1c. Nilai output adalah nilai data yang sudah dihitung sebelumnya

output = data;

2. Nilai prediksi akhir diambil dari nilai terakhir output yang sudah dihitung sebelumnya

lmf(i) = round(output(end),0);

Hasil akhir adalah:

Algoritma Levenberg-Marquardt / Levenberg-Marquardt-Fletcher
Contoh: Memperkirakan penjualan pada periode berikutnya berdasarkan data penjualan pada periode sebelumnya
Diasumsikan ada 4 data barang yang sudah diketahui hasil penjualannya
Masing-masing barang memiliki data penjualan pada 5 periode sebelumnya
Maka tentukan prediksi penjualan untuk 3 periode berikutnya
Diasumsikan data penjualan adalah sebagai berikut: 
Nama Barang, Periode1, Periode2, Periode3, Periode4, Periode5
Pensil     , 10      , 12      , 8       , 11      , 20
Penghapus  , 15      , 12      , 13      , 14      , 14
Pena       , 9       , 7       , 15      , 15      , 10
Penggaris  , 1       , 2       , 4       , 12      , 13


Hasil Perhitungan dengan metode Levenberg-Marquardt / Levenberg-Marquardt-Fletcher
Nama Barang, Periode1, Periode2, Periode3, Periode4, Periode5, Prediksi Periode berikutnya
Pensil     , 10      , 12      , 8       , 11      , 20      , 17
Penghapus  , 15      , 12      , 13      , 14      , 14      , 13
Pena       , 9       , 7       , 15      , 15      , 10      , 6
Penggaris  , 1       , 2       , 4       , 12      , 13      , 12

Contoh modul / source code menggunakan Matlab dapat didownload disini:

Download Now!



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.

</lambda,>
</jumlahdata,>

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *