OPTIMISASI MULTIKRITERIA
Optimisasi Satu Kriteria
Model matematis umum untuk masalah optimisasi satu kriteria sering juga
disebut sebagai program nonlinear, yaitu:
Diberikan fungsi-fungsi linear dan/atau nonlinear
f : Rn R, g : Rn Rm, h : Rn Rl
Tetapkanlah x*
agar f(x*) memiliki nilai optimum
seraya tunduk pada m+l kekangan
g(x*) = 0
h(x*) ≥ 0.
Di sini x=(x1, x2, …, xn )T akan disebut sebagai variabel keputusan (decision
variables), f(x) disebut fungsi sasaran (objective function), g(x*)=0 disebut kekangan
kesamaan (equality constraints), dan h(x*)≥0 disebut kekangan ketaksamaan
(inequality constraints).
Di sini akan diambil kesepakatan bahwa yang dimaksud dengan nilai optimum
adalah nilai minimum dari fungsi yang bersangkutan. Masalah mencari x* agar f(x*)
maksimum dapat diungkapkan sebagai masalah mencari x* agar -f(x*) minimum,
sebab max f(x) = -min -f(x).
Optimisasi Multikriteria
Jika pada masalah optimisasi satu kriteria hanya ada satu fungsi sasaran yang
terlibat, maka masalah optimisasi multikriteria meliputi lebih dari satu fungsi sasaran.
Jadi perlu diadakan sedikit perubahan pada model matematis di atas:
Diberikan fungsi-fungsi linear dan/atau nonlinear
f : Rn Rk, g : Rn Rm, h : Rn Rl
Tetapkanlah x*
agar setiap komponen f(x*)memiliki nilai optimum
seraya tunduk pada m + l kekangan
g(x*)=0
h(x*)≥0.
Di sini akan muncul konflik kepentingan antar fungsi sasaran; karena jika
f1(x* ) memiliki nilai minimum, belum tentu f2(x*(1)), f3(x*(1)), … fk(x*(1)) juga
(1)
memiliki nilai minimum. Konflik kepentingan di atas harus dikompromikan: nilai
optimum suatu fungsi sasaran haruslah berupa nilai yang dapat diterima oleh
keseluruhan fungsi sasaran.
METODE
Pada bagian ini dibicarakan metode-metode yang digunakan dalam proyek ini
untuk menyelesaikan masalah optimisasi multikriteria yang telah didefinisikan di atas.
Pilihan atas metode-metode ini didasarkan pada kemudahan implementasi.
Optimisasi Satu Kriteria Tanpa Kekangan: Metode Pencarian Langsung dan
Acak
Salah satu metode numeris untuk mencari lokasi minimum dari fungsi real
f(x), x ∈ Rn , adalah metode pencarian langsung (direct search) yang diajukan oleh
Hooke dan Jeeves. Metode ini memanfaatkan dua langkah, yaitu langkah penjelajahan
(exploratory moves) untuk menentukan arah pencarian yang tepat, dan langkah pola
(pattern moves) untuk mempercepat pencarian. Parameter-parameter yang digunakan
dalam metode ini adalah:
maxm ≡ jumlah maksimum langkah pola yang diijinkan.
≡ panjang langkah awal, dinyatakan sebagai fraksi dari jangkauan xk –
fpk
xp, di mana xk ∈ Rn adalah perkiraan batas atas dan xp ∈ Rn adalah
perkiraan batas bawah.
≡ fraksi dari panjang langkah awal sebagai kriteria konvergensi.
wk
Keterangan lebih lanjut mengenai metode Hooke dan Jeeves diberikan antara
lain oleh Avriel (1976) dan Bronson (1982).
Pencarian langsung belum tentu menemukan minimum yang merupakan
global minimum. Untuk memperbesar peluang itu, digunakan kombinasi berupa
pencarian langsung dan acak (direct and random search), yang memanfaatkan
parameter-parameter berikut:
ntest ≡ jumlah lokasi acak dalam pencarian shotgun.
nh ≡ jumlah maksimum pencarian shotgun yang diijinkan.
ntmc ≡ jumlah lokasi acak untuk memperoleh lokasi awal pencarian yang
baru.
nraz ≡ jumlah pencarian yang dilakukan menggunakan lokasi awal pencarian
yang baru.
Metode pencarian langsung dan acak dapat dijelaskan melalui pseudocode
berikut, diawali dengan mengambil suatu nilai xac ∈ Rn sebagai lokasi awal
pencarian:
kl=1;
do {
kount=0;
do{
Lakukan pencarian langsung Hooke dan Jeeves;
Hasilnya x;
Lakukan pencarian shotgun: Dari sebanyak ntest
lokasi acak di sekitar x cari yang paling optimal;
Hasilnya xs;
if (f(xs)>= f(x)|| kount>=nh) break;
Gunakan xs sebagai lokasi awal pencarian;
kount++;
} while(1);
if (kl==1 || f(x)<fex){
fex = f(x);
xex=x;
}
if (kl>nraz) break;
Dari sebanyak ntmc lokasi acak di ruang
K ≡ {x : x ∈ Rn, xp < x < xk}, cari yang paling optimal.
Gunakan sebagai lokasi awal pencarian;
kl++;
} while(1);
Lokasi optimal akan diberikan oleh xex.
Optimisasi Satu Kriteria Dengan Kekangan: Penggunaan Fungsi Hukuman
Meninjau masalah optimisasi satu kriteria dengan kekangan:
Tetapkanlah x*
agar f(x*) memiliki nilai optimum
seraya tunduk pada kekangan
g(x*) = 0
h(x*) ≥ 0
Dengan mendefinisikan suatu daerah layak (feasible region)
X = {x : x ∈ Rn, g(x) = 0, h(x) ≥ 0}
dan mendefinisikan suatu fungsi hukuman (penalty function)
⎧ 0, x ∈ X
P( x) = ⎨
⎩ +∞, x ∉ X ,
maka masalah optimisasi dengan kekangan di atas dapat ditransformasikan menjadi
masalah optimisasi tanpa kekangan sebagai berikut:
Tetapkanlah x*
agar F(x*)= f(x*) + P(x*) memiliki nilai optimum
Optimisasi Multikriteria: Metode Pembobotan Ternormalisasi
Masalah optimisasi multikriteria bisa dibawa ke bentuk masalah optimisasi
satu kriteria dengan cara skalarisasi: fungsi vektor f(x) yang mencakup fungsi-fungsi
sasaran f1(x), f2(x), … fk(x) ditransformasikan ke fungsi skalar f(x). Osyczka (1984)
menunjuk bahwa salah satu metode transformasi yang sangat sederhana adalah
metode pembobotan ternormalisasi (normalized weighting method).
Prinsip metode ini adalah menjumlahkan kesemua fungsi sasaran dengan
memberikan koefisien pembobot untuk tiap fungsi sasaran. Koefisien pembobot ini
menunjukkan kadar pentingnya suatu fungsi sasaran relatif terhadap fungsi-fungsi
yang lain. Hasil transformasi adalah
k
f (x) = ∑ wi f i (x)ci
i =1
k
∑w
dengan wi ≥ 0 adalah koefisien pembobot di mana = 1 . Di sini ci ≡ 1/ f i ( x*( i ) )
i
i =1
*( i )
adalah faktor normalisasi dengan f i (x ) adalah harga minimum dari fi (x) .
PENGEMBANGAN
Sistem perangkat lunak yang dibangun terdiri dari tiga subsistem pokok:
1. Program Utama. Metode numeris untuk menyelesaikan masalah optimisasi
diimplementasikan di sini.
2. Parser. Penggunaan parser memungkinkan dimasukkannya fungsi-fungsi
matematis ke dalam sistem pada saat run-time. Ini memberikan fleksibilitas
walaupun mengurangi efisiensi.
3. Antarmuka (user interface).
Subsistem 1 dan 2 dikembangkan menggunakan bahasa pemrograman C++.
Secara tradisional perangkat lunak optimisasi biasa dikembangkan dengan
menggunakan FORTRAN (bandingkan Kuester dan Mize, 1982; Osyczka, 1984),
namun di sini digunakan C++ karena popularitasnya di platform PC-Windows.
Digunakan ketelitian ganda (double precision) agar diperoleh akurasi yang memadai.
Subsistem 3 dikembangkan menggunakan bahasa pemrograman Pascal. Pascal dipilih
karena relatif mudah digunakan.
Secara garis besar langkah-langkah yang terdapat dalam Program Utama
adalah:
1. Mentransformasikan masalah optimisasi multikriteria ke masalah optimisasi satu
kriteria dengan kekangan menggunakan metode pembobotan ternormalisasi.
2. Mentransformasikan masalah optimisasi satu kriteria dengan kekangan ke
masalah optimisasi satu kriteria tanpa kekangan dengan memanfaatkan fungsi
hukuman.
3. Menyelesaikan masalah optimisasi satu kriteria tanpa kekangan dengan metode
pencarian langsung dan acak.
STUDI KASUS
Sistem yang telah dibangun tersebut diuji dengan satu studi kasus yang akan
dibicarakan di sini. Diajukan suatu permasalahan yang tergolong sebagai masalah
optimisasi multikriteria berikut model matematisnya, di mana penyelesaian untuk
masalah ini telah diketahui dan digunakan sebagai referens. Selanjutnya model
matematis di atas dimasukkan ke sistem, lalu keluaran sistem dibandingkan dengan
referens tersebut.
Kasus diambil dari buku teks karangan Osyczka (1984) berupa masalah
perancangan balok (beam), yaitu penentuan ukuran-ukuran dari balok yang
diperlihatkan pada Gambar 1. Ukuran-ukuran tersebut dipilih sebagai variabel
keputusan:
x1 = panjang bagian I dari balok
x2 = diameter interior balok.
Dianggap bahwa balok mampu menanggung gaya (force) maksimum Fmax =
12000 N dan besarnya tegangan lentur (bending stress) yang dibolehkan untuk bahan
balok adalah σ g =180 N/mm. Maka berlaku kekangan kekuatan lentur (bending
strength)
Fmax x1 Fmax l
≤σg; ≤σg
(D ) (D )
( 32 D2 ) ( 32 D1 )
− x2 − x2
4 4 4 4
2 1
yang melalui substitusi menghasilkan
9.78 ⋅106 x1
≤ 180; x2 ≤ 75.2 .
4.096 ⋅107 − x2
4
Juga dianggap bahwa besar diameter interior balok sekurang-kurangnya 40
mm dan bahwa panjang bagian I dapat dipilih secara bebas. Maka berlaku kekangan
geometrik berikut:
x2 ≥ 40; x1 ≥ 0.
Hingga di sini telah diperoleh empat kekangan ketaksamaan.
9.78 ⋅106 x1
h1 (x) ≡ 180 − ≥0
4.096 ⋅107 − x2
4
h2 (x) ≡ 75.2 − x2 ≥ 0
h3 (x) ≡ x2 − 40 ≥ 0
h4 (x) ≡ x1 ≥ 0
Perancang balok ingin agar balok yang dirancangnya memenuhi dua sasaran:
1. Minimisasi isi balok.
2. Minimisasi kepatuhan statik (static compliance) balok.
Isi balok dinyatakan oleh
π
f1 (x) = ⎡ x1 ( D2 − x2 ) + (1 − x1 )( D1 − x2 ) ⎤ mm3
2 2 2 2
⎣ ⎦
4
dan kepatuhan statik balok dinyatakan oleh
64 ⎡⎛ ⎤
⎞ 3 l3
1 1
f 2 ( x) = − 4 x1 + 4
⎢⎜ 4 4 ⎥
4 ⎟
mm/N
3π E ⎢⎝ D2 − x2 D1 − x2 ⎠ D1 − x2 ⎥
4
⎣ ⎦
di mana E = 2.06 ⋅ 105 N/mm2 adalah modulus Young. Dengan memberikan l = 1000
mm, D1 = 100 mm, D2 = 80 mm, diperoleh dua fungsi sasaran berikut:
( ) ( )
f1 (x) = 0.785 ⎡ x1 6400 − x2 + (1000 − x1 ) 10000 − x2 ⎤
2 2
⎣ ⎦
⎡⎛ 109 ⎤
⎞ 3
1 1
f 2 (x) = 3.298 ⋅10−5 ⎢⎜ − 8 x1 + 8 4⎥
4 ⎟
⎢⎝ 4.096 ⋅10 − x2 10 − x2 ⎠ 10 − x2 ⎥
4
7
⎣ ⎦
Untuk optimisasi kedua fungsi sasaran secara serentak (multikriteria),
perancang balok menggunakan metode pembobotan ternormalisasi dengan koefisien
pembobot untuk fungsi sasaran pertama dan kedua dipilih masing-masing sebesar w1
= 0.2 dan w2 = 0.8. Ini ekuivalen dengan optimisasi fungsi skalar f(x) berikut:
f1 ( x) f ( x)
f ( x) = 0.2 + 0.8 2 .
2.961 ⋅10 3.38 ⋅10 4
6
Optimisasi multikriteria ini memberikan hasil:
x* = ( 207.0, 52.5 )
T
f ( x* ) = ( 5.101⋅106 , 3.62 ⋅10−4 ) .
T
Model matematis di atas dimasukkan ke sistem perangkat lunak yang telah
dibangun. Parameter-parameter yang digunakan oleh sistem diberi nilai sebagai
berikut:
koefisien pembobot w1 = 0.2 dan w2 = 0.8;
xp = (0, 40) ; xk = (1000, 76)Τ; xac = (250, 60)Τ;
maxm = 300; fpk = 0.01; wk = 0.0001;
ntest = 300; nh = 3; ntmc = 500; nraz = 3
Sistem dioperasikan pada PC dengan prosesor Pentium III 450 MHz yang
bekerja pada sistem operasi Microsoft Windows 98. Ternyata penyelesaian yang
diberikan oleh sistem cocok dengan hasil yang ada pada referens.
Proses masukan dan keluaran yang terjadi selama pengujian juga menunjukkan
bahwa pengguna sistem ini dapat memasukkan dan menyunting model masalah
beserta parameter-parameter yang dikehendakinya secara mudah dan setiap saat bisa
meminta jawaban dari sistem.
I have 3 Environment in My activity
- Server, I’m Using Centos Because it’s stable, free and this is free version from Redhat Enterprise Linux
- Desktop/Laptop, I’m Using Ubuntu Karmic Koala, because with Ubuntu I can get all of I need with easy.
- My Lab, I’m using Backtrack, because I have interest in Network Auditing and I want to create application for that.
1. Buka Konsole
2. Login sebagai root
3. Kemudian ketikkan perintah sync; echo 3 > /proc/sys/vm/drop_caches
Potongan kode programnya sebagai berikut:
public void paint(Graphics g) {
Graphics2D g2 = (Graphics2D) g;
int[] xs={100,250,100};
int[] ys={500,50,50};
Polygon triangle = new Polygon(xs,ys,xs.length);
g2.setPaint(Color.YELLOW);
g2.fillPolygon(triangle);
}
Bagi para pembaca yang ingin mengenerate barcode menggunakan Java bisa menggunakan framework yang bernama barbecue.
