Particle Swarm Optimization (PSO) – dengan Octave

Tulisan ini merupakan lanjutan dari tulisan sebelumnya yang menggunakan Matlab sebagai medianya. Ketika membuka Octave pertama kali, ada dua pilihan yaitu mode Command Line Interface (CLI) atau Graphical User Interface (GUI). Kita pilih yang mudah saja yaitu GUI. Tampak tampilan yang mirip dengan matlab. Untuk yang ingin menginstallnya, baca postingan saya yang lalu.

Seperti pada Matlab, Octave juga membutuhkan direktori kerja dimana M-file yang telah kita buat berada. Di sini saya harus menempatkan dua file yaitu file algoritma PSO, simplepso.m dan fungsi2.m yang merupakan fungsi tujuan (objective function) yang akan dioptimalkan.

Tampak hasil optimasi untuk 4 iterasi dengan fungsi pause yang saya sisipkan untuk melihat perjalanan program tiap operasi. Di sini sedikit berbeda, ketika Octave menjumpai fungsi pause ternyata ada pesan agar kita menekan huruf f yang artinya forward (maju).

Grafik di atas merupakan hasil plot yang kecanggihannya ga jauh beda dengan Matlab. Harga Octave pun tidak terlalu mahal, hanya Rp. 0,- alias gratis, dibanding harga lisensi Matlab versi stand alonenya (individual price) sekitar Rp. 34 juta dengan harga 1 dollar yang saat ini melambung Rp. 13.000,-.

Particle Swarm Optimization (PSO)

PSO jika diterjemahkan berarti optimasi segerombolan partikel. Partikel di sini adalah makhluk hidup seperti burung, ikan, atau lebah yang sedang mencari makanan. Mengapa mengikuti prinsip pergerakan segerombolah makhluk-makhluk tersebut? Jawabannya sederhana, karena makhluk-makhluk tersebut berhasil menemukan makanannya. PSO pertama kali dicetuskan oleh kennedy dan Eberhart pada tahun 1995 yang membahas mengenai perilaku kerumunan makhluk hidup.

Menurut beberapa paper, misalnya Sathya, yang melakukan optimasi terhadap segmentasi gambar, PSO memiliki beberapa kelebihan di antaranya:

  • Mudah diimplementasikan dan hanya sedikit parameter yang dibutuhkan.
  • Tidak ada evolusi pada operatornya, misalnya mutasi dan crossover pada Genetic Algorithms (GAs).
  • Di GAs kromosom membagi informasi sehingga pergerakan mengikuti group-nya sendiri, berbeda dengan PSO yang berkelompak, dan menurut Sathya PSO lebih robust. Sepertinya saya kurang setuju dengan pendapat yang ini, apa boleh buat kita rujuk saja.
  • PSO lebih efisien karena membutuhkan sedikit komputasi.
  • Dibanding GAs dan metode heuristik lainnya, PSO lebih fleksibel dalam menjaga keseimbangan antara pencarian global dan lokal terhadap search space-nya.

Salah satu point menarik yang dibahas oleh kennedi et al. adalah masalah collision karena jika setiap partikel menganggap ada partikel lain yang lebih “optimum” tentu saja dia akan mengarah ke sana dan terjadi tuburukan/collision. Tetapi kenyataannya tidak ada tabrakan saat burung terbang, ikan berenang, lebah menari-nari dan sebagainya.

Untuk menerapkan algoritma PSO, di sini kita coba dengan menggunakan matlab atau octave. Kita coba terlebih dahulu dengan matlab. Sebagai referensi, Anda dapat mendownload materi budi santoso dari ITS di link berikut, kemudian coba jalankan kode yang ada di dalamnya. Di sana dijelaskan dua jenis PSO dengan dan tanpa inersia. Agar lebih mudah memahami alur instruksi programnya, di bawah instruksi yang akan saya selidiki biasanya saya sisipkan instruksi pause dan titik kemo di belakang kode yang dibuat saya hilangkan titik koma-nya agar muncul di layar command window. Saya coba jalankan dengan jumlah partikel 3 dan iterasi maksimum 4.

Variabel v,x,f yang menyatakan nilai awal kecepatan, swarm, dan nilai fitness-nya dimunculkan dalam variabel yang saya lingkari di atas. Untuk menampilkan nilai minimum minftot saya hapus titik komanya agar muncul di command window ketika berhenti sejenak di tiap iterasi karena instruksi pause yang saya sisipkan. Hasilnya tampak di bawah ini dimana fitness yang terbaik adalah pada swarm ketiga (34.8627) dengan swarm 105.9045. Ini tentu saja masih belum optimal karena masih iterasi pertama.

Setelah iterasi keempat dijalankan dengan menekan sembarang tombol untuk melanjutkan akibat instruksi pause tersebut diperoleh grafik dan hasil akhir. Kita coba dengan octave, di tulisan selanjutnya