Teknik Optimasi
umum digunakan untuk pengambilan keputusan, tetapi bisa juga digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian posisi dengan pengembalian nilai fungsi minimal. .
Umumnya Teknik optimasi dilakukan dengan cara menghitung secara terus menerus calon solusi dengan menggunakan suatu acuan kualitas. Tujuannya adalah untuk mengoptimasi permasalahan dengan cara menggerakan partikel / calon solusi di dalam ruang permasalahan menggunakan fungsi tertentu untuk posisi dan kecepatan dari partikel. Pergerakan partikel dipengaruhi oleh solusi terbaik partikel tersebut, dan solusi terbaik secara umum yang didapatkan dari partikel lain. Sekumpulan partikel ini dinamakan swarm, dan pada akhirnya swarm ini akan bergerak menuju kepada solusi terbaik.
Salah satu proses optiamasi adalah mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).
PSO untuk pengurutan adalah salah satu algoritma yang paling umum, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi.(menggunakan perbandingan dalam operasi antar elemennya.)
Contoh Penerapan:
Misalkan kita mempunyai sebuah array dengan. Elemen-elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma Optimasinya adalah sebagai berikut.
Pass pertama
(4 2 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9)
Pass kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Pass ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Dapat dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma PSO Optimasia dalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.
Atau jika di jabarkan:
Jika kita perhatikan proses diatas, para proses kedua data sudah terurut dengan benar. Tetapi algoritma Optimasi tetap berjalan hingga proses kedua berakhir. Proses ketiga masih terus berjalan karena pada algoritma ini maksud terurut itu adalah tidak ada satupun penukaran pada suatu proses. Proses ketiga ini dilakukan untuk verifikasi data.
Proses Optimasi ini mempunyai kelebihan dan kekurangan, untuk kelebihannya metode ini merupakan metode paling sederhana untuk mengurutkan data. Selain sederhana, algoritma Optimasi ini mudah dipahami. Sementara itu, kekurangannya terletak pada efisiensi..
B. Rule Algoritma Optimasi
1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
3. Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.
Contoh Kasus
Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan data ini (ascending) dengan menggunakan Teknik Optimasi. Berikut ini adalah proses yang terjadi:
Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)
Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)
Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)
Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai
C. Kompleksitas Algoritma Optimasi Jarak
Kompleksitas Algoritma ini dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.
Ø Kondisi Best-Case
Dalam kasus ini, data yang akan disorting telah terurut sebelumnya, sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali pass.
Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Contoh Best-Case dapatdilihat pada pengurutan data “1 2 3 4” di bawah ini.
Pass Pertama
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Dari proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi satu kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n). Dengan kata lain, pada kondisi Best-Case algoritma Optimasi termasuk pada algoritma lanjar.
Ø Kondisi Worst-Case
Dalam kasus ini, data terkecil berada pada ujung array. Contoh Worst-Case dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini.
Pass Pertama
(4 3 2 1) menjadi (3 4 2 1)
(3 4 2 1) menjadi (3 2 4 1)
(3 2 4 1) menjadi (3 2 1 4)
Pass Kedua
(3 2 1 4) menjadi (2 3 1 4)
(2 3 1 4) menjadi (2 1 3 4)
(2 1 3 4) menjadi (2 1 3 4)
Pass Ketiga
(2 1 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Pass Keempat
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Dari langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu pass, data terkecil akan bergeser ke arah awal sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali pass untuk memverifikasi. Sehingga jumlah proses pada kondisi best case dapat dirumuskan sebagai berikut. Jumlah proses = n2+n (3)
Dalam persamaan (3) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada kondisi worst-case, algoritma Optimasi termasuk dalam kategori algoritma kuadratik.
Ø Kondisi Average-Case
Pada kondisi average-case, jumlah pass ditentukan dari elemen mana yang mengalami penggeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseranpaling banyak adalah elemen 2, yaitu sebanyak dua kali.
Pass Pertama
(1 8 6 2) menjadi (1 8 6 2)
(1 8 6 2) menjadi (1 6 8 2)
(1 6 8 2) menjadi (1 6 2 8)
Pass Kedua
(1 6 2 8) menjadi (1 6 2 8)
(1 6 2 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Pass Ketiga
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Dari proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan diperlukan dua buah passing,ditambah satu buah passing untuk memverifikasi. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut. Jumlah proses = x2+x (4) Dalam persamaan (4) di atas, x adalah jumlahpenggeseran terbanyak. Dalam hal ini, x tidak pernah lebih besar dari n, sehingga x dapat dirumuskan sebagai
Dari persamaan (4) dan (5) di atas, dapat disimpulkan bahwa notasi
big-O nya adalah O(n2). Dengan kata lain, pada kondisi average case algoritma Optimasi termasuk dalam algoritma kuadratik.
D. Implementasi dalam Pseudo-Code
Setiap algoritma akan memiliki implementasi yang berbeda, tergantung dari bahasa program yang dipakai. Oleh karena itu berikut ini adalah pseudo-code dari algoritma Pengurutan Jarak untuk memudahkan implementasi Algortima pada bahasa apapun.
procedure Optimize( A : list of
bestOptimize items ) defined as:
do
swapped := false
for each i in 0 to length(A) - 2
inclusive do:
GBEST=A[i]
if GBEST> A[i+1] then
PBEST=A[i+1]
swap( A[i], PBEST )
swapped := true
end if
end for
while swapped
end procedure
E. List Code
Adapun implementasi dalam code java nya adalah sbb:
public static void Optimasi(){
int j;
boolean flag = true;
double temp=0.0;
String stemp="";
while ( flag ){
flag= false;
for( j=0; j < jd -1; j++ ){
GBEST=dJarak[ j ] ;
if ( GBEST > dJarak[j+1] ) {
PBEST= dJarak[ j ];
dJarak[ j ] = dJarak[ j+1 ];
dJarak[ j+1 ] = PBEST;
stemp=arId[j];
arId[ j ] = arId[ j+1 ];
arId[ j+1 ] = stemp;
stemp=arNama[j];
arNama[ j ] = arNama[ j+1 ];
arNama[ j+1 ] = stemp;
stemp=arUrl[j];
arUrl[ j ] = arUrl[ j+1 ];
arUrl[ j+1 ] = stemp;
stemp=arKet[j];
arKet[ j ] = arKet[ j+1 ];
arKet[ j+1 ] = stemp;
stemp=arUrlFoto[j];
arUrlFoto[ j ] = arUrlFoto[ j+1 ];
arUrlFoto[ j+1 ] = stemp;
stemp=arTelp[j];
arTelp[ j ] = arTelp[ j+1 ];
arTelp[ j+1 ] = stemp;
stemp=arLati[j];
arLati[ j ] = arLati[ j+1 ];
arLati[ j+1 ] = stemp;
stemp=arLongi[j];
arLongi[ j ] = arLongi[ j+1 ];
arLongi[ j+1 ] = stemp;
stemp=arAlamat[j];
arAlamat[ j ] = arAlamat[ j+1 ];
arAlamat[ j+1 ] = stemp;
stemp=arJarak[j];
arJarak[ j ] = arJarak[ j+1 ];
arJarak[ j+1 ] = stemp;
flag = true;
}
}
}
}