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

25 respons untuk ‘Particle Swarm Optimization (PSO)

  1. Pak, apakah bapak punya referensi perhitungan manual PSO untuk feature selection? Karena saya masih bingung PSO untuk feature selection. Terima kasih.

    • kasusnya harus yg bervariabel banyak, trus dipilih variabel-variabel yg paling mencirikan suatu fitur. Maksudnya supaya variabel sesedikit mungkin tapi tidak membuat fitur melenceng jauh dari yang sesungguhnya. Dengan variabel yg sedikit diharapkan proses learning lebih cepat. Nah peran PSO untuk mencari variabel2 itu sambil dihitung performanya (kecocokan dengan yang asli /semirip mungkin)

      • Pak, saya masih bingung menentukan fungsi fitness nya bagaimana ya? Kalo pada case seleksi fitur untuk klasifikasi citra fungsi fitness nya kira-kira apa ya pak ?

      • inti dari optimasi ya meramu fitnes. minimumkan variabel fitur, dan maksimumkan similarity dengan citra real-nya (bisa dengan euclidean)

  2. Pak Rahmadya yth…

    Gimana cara mengatur step nilai variabel yang akan dicari jika bersifat diskrit? Contohnya kapasitor bank. Misalnya memiliki rating 0.0 – 0.3 pu. Nilai variable pencarian memiliki step 0,005. Misalnya 0.005, 0,010, 0,015. Terima kasih

  3. Pak Rahmadya

    Bagaimana cara jika variable yang akan dicari memiliki nilai diskrit? Misalnya kapasitor bank. Rating 0.0-0.3 pu. Step variable = 0.005. Pencarian nilai variable jika npop = 5 misalnya 0.010, 0.005, 0.015, 0.025, 0.010

    Terima kasih

  4. Maksud saya begini pak..

    Jika ada kasus dimana nilai variabel yang akan dicari mixed continue dan diskrit
    Misalnya:
    Variabel memiliki ambang batas di bawah ini:
    Variabel A = 0,9-1,1 (variabel kontinu)
    Variabel B = 0,0-0,3 step 0,05 (variabel diskrit)

    Jika misalnya memiliki fungsi objective F yang didalamnya ada variabel A dan B yang akan dicari

    Bagaimana caranya supaya nilai posisi (X) pada PSO (misalnya jumlah populasi 3) untuk variabel B berada dalam rentang 0,0-03 dengan step 0,05 dan variabel A tanpa step

    Mohon pencerahannya

    Salam

    • ada fungsi “rand” untuk membangkitkan bilangan random pecahan dari 0.00 sd 1.00. jika ingin 1 -10 kalikan saja dengan 10, e.g. rand*10

      • Maaf pak sebelumnya

        Maksunya bukan nilai random yang lebih dari 10

        Tapi bagaimana meng-generate nilai variabel yang memiliki mixed kontinu dan diskrit?

        Contoh:
        Variabel VG (kontinu), LB = 0,9; UB = 1,1 —-> tanpa step
        Variabel T (diskrit) , LB = 0,0 UB = 0,3 —-> step 0,05

        Kalo variabel kontinu saya menggunakan:

        LB = [0,9 0,0];
        UB = [1,1 0,3]

        nPop = 3;
        nVar = 2; % ada 2 variabel keputusan

        VarSize = [1 nVar);

        pop(i).Position=unifrnd(LB,UB,VarSize);

        Nah, bagaimana solusinya jika kasus mixed kontinu dan diskrit?

        Untuk variabel T yang diskrit diharapkan nilai randomnya memiliki step 0,05
        misalnya posisi (X) PSO = [ 0,93 0,15]
        [1,02 0,25]
        [1,09 0,05]

        Terima kasih
        Sabhan

      • mau tidak mau harus ditambahkan satu if-than agar diperoleh angka diskrit (bulat ke atas/ke bawah) tiap step 0.05

      • sebagai ilustrasi jika diketahui sebuah angka tertentu dengan step 0.5.
        coba di comnand window:
        angka=2.3;
        steps=0.5;
        baseangka=floor(angka);
        pecahan=angka-floor(angka);
        upper=abs(steps-pecahan);
        buttom=abs(0-pecahan);
        if upper<buttom
        newangka=baseangka+steps
        else
        newangka=baseangka
        end

    • PSO, GA, dll hanya memilih yg optimal dari beberapa kandidat. bisa diterapkan di FMS asalkan constraint direset ulang karena perubahan akibat fleksibel.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google

You are commenting using your Google account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.