Ide Dibalik Particle Swarm Optimization
Assalamualaikum warahmatullahi wabarakatuh
Semoga Allah Subhana Wata’ala senantiasa mencurah-curahkan RahmatNya kepada kita semua dan semoga sholawat serta salam senantiasa tercurahkan kepada Rosulullah Shalallahu Alaihi Wassalam
Terkhusus untuk para sahabat penuntut ilmu di bidang data, semoga Allah mempermudah proses belajar temen-temen, dan semoga ilmu yang temen-temen pelajari menjadi ilmu yang bermanfaat.
Particle Swarm Optimization(PSO)
Particle Swam Optimization merupakan salah satu metode optimisasi yang populer dan sering digunakan, metode ini memiliki kelebihan di antaranya:
- Mudah diimplementasikan dan hanya butuh sedikit parameter
- Komputasi yang efisien
- Fleksibilitas dalam keseimbangan pencarian optimum lokal dan global
- Tidak terdapat evolusi pada operatornya seperti pada Genetic Algorithm
Inspirasi Particle Swarm Optimization(PSO)
Dirujuk dari paper pertamanya, terinspirasi dari gerakan sekelompok burung di udara. Setiap burung terbang dengan arah dan kecepatannya masing-masing, meskipun demikian, setiap mereka tetap berada dalam sebuah kawanan(swarm) yang solid. Kawanan burung tersebut akan selalu mencari jalur terbaik untuk menuju targetnya. Jalur tersebut bisa saja dilihat oleh seekor burung atau sekelompok kecil burung dalam kawanan yang kemudian diikuti oleh semua anggota dalam kawanan tersebut. Sehingga setiap burung juga menyimpan memori tentang jalur yang dipilih oleh kawanan tersebut.
Fenomena Murmurasi Dibahas dalam Al-Qur’an
Saya sangat senang ketika melihat banyak berbagai teori terinspirasi dari alam, terlebih lagi, sebagai seorang muslim saya akan bisa terkagum-kagum dengan fenomena-fenomena alam yang begitu indah dibahas dalam Al-Qur’an dan dijadikan inspirasi untuk algoritma tertentu. Tentu setiap fenomena alam yang dibahas dalam Al-Qur’an adalah petunjuk bagi kita untuk mendapatkan ilham padanya. Berkaitan dengan pergerakan burung di udara, itu merupakan tanda kebesaran Allah subhana wata’ala seperti tertuang dalam ayat berikut:
أَلَمْ يَرَوْا۟ إِلَى ٱلطَّيْرِ مُسَخَّرَٰتٍۢ فِى جَوِّ ٱلسَّمَآءِ مَا يُمْسِكُهُنَّ إِلَّا ٱللَّهُ ۗ إِنَّ فِى ذَٰلِكَ لَـَٔايَـٰتٍۢ لِّقَوْمٍۢ يُؤْمِنُونَ
Tidakkah mereka memperhatikan burung-burung yang dimudahkan terbang melayang-layang di angkasa? Tiada yang menahan mereka (dari jatuh) melainkan Allah; sesungguhnya pada yang demikian itu, ada tanda-tanda (yang membuktikan kekuasaan Allah) bagi kaum yang beriman.
[Q.S. An-Nahl : 79]
Kemudian pembahasan fenomena pergerakan burung dalam kelompok tertuang di dalam ayat berikut:
إِنَّا سَخَّرْنَا ٱلْجِبَالَ مَعَهُۥ يُسَبِّحْنَ بِٱلْعَشِىِّ وَٱلْإِشْرَاقِ ١٨ وَٱلطَّيْرَ مَحْشُورَةًۭ ۖ كُلٌّۭ لَّهُۥٓ أَوَّابٌۭ ١٩
Sesungguhnya Kami menundukkan gunung-gunung untuk bertasbih bersama dia(Daud) di waktu petang dan pagi(18). Dan (Kami tundukkan pula) burung-burung dalam keadaan terkumpul. Masing-masingnya amat taat kepada Allah(19).
[Q.S. Shaad : 18–19]
Setiap burung terbang dengan sayapnya, arah dan kecepatannya masing-masing di bahas dalam ayat berikut:
أَلَمْ تَرَ أَنَّ ٱللَّهَ يُسَبِّحُ لَهُۥ مَن فِى ٱلسَّمَـٰوَٰتِ وَٱلْأَرْضِ وَٱلطَّيْرُ صَـٰٓفَّـٰتٍۢ ۖ كُلٌّۭ قَدْ عَلِمَ صَلَاتَهُۥ وَتَسْبِيحَهُۥ ۗ وَٱللَّهُ عَلِيمٌۢ بِمَا يَفْعَلُونَ ٤١
Tidaklah kamu tahu bahwasanya Allah; kepada-Nya bertasbih apa yang di langit dan di bumi dan (juga) burung dengan mengembangkan sayapnya. Maing-masing telah mengetahui (cara) sembahyang dan tasbihnya, dan Allah Maha Mengetahui apa yang mereka kerjakan.
[Q.S. Nuur : 41]
Pemodelan & Algoritma Particle Swarm Optimization
Selain burung, fenomena pergerakan kelompok ini juga ditemukan di hewan lain yakni ikan. Oleh karenanya, sebagai perumuman teori ini disebut Particle Swarm atau kerumunan partikel. Ide dasar dari pemodelan ini adalah mencari nilai optimum dengan membangkitkan sejumlah populasi partikel yang bergerak ke arah nilai optimum sevara berkerumun. PSO memiliki dua varian berdasarkan skema pertukaran informasi antar partikel.
- Varian Global: Posisi terbaik yang dicapai oleh semua individu pada swarm dikomunikasikan pada semua partikel pada tiap iterasi.
- Varian Lokal: Setiap partikel ditempatkan pada persekitaran (neighborhood) yang terdisir atas partikel-partikel yang ditentukan di awal (prespecified particles) . Pada kasus ini, posisi terbaik yang pernah dicapai partikel dalam persekitaran hanya dikomunkasikan antar anggota persekitaran.
PSO dimulai dari inisialisasi populasi hingga penghentian komputasi, seperti algoritma berikut:
- Inisialisasi populasi(posisi dan kecepatan acak) dalam hyperspace.
- Evaluasi fitness partikel individu.
- Pembaharuan kecepatan berdasarkan kondisi terbaik sebelumnya(previous best; pbest) dan terbaik global atau lokal (global or neighborhood best; gbest or lbest).
- Hentikan berdasarkan beberapa kondisis.
- Kembali ke langkah 2.
Setiap partikel menyesuaikan koordinatnya dengan mengasosiasikannya terhadap solusi terbaik (pbest) yang diperoleh. Persamaan — persamaan di bawah ini digunakan untuk melakukan penyesuaian partikel dengan asumsi untuk penyelesaian permasalahan minimasi dengan fungsi suai (fitness function).
Persamaan (1) menjelaskan adaptasi kecepatan suatu partikel i pada dimensi j saat t+1.
Persamaan (2) menjelaskan adaptasi posisi suatu partikel i pada dimensi j saat t+1.
Posisi terbaik suatu personal partikel saat t+1 diberikan oleh persamaan (3)
Posisi terbaik global pada saat t diberikan oleh persamaan (4)
yang mana
Contoh Kasus dan Implementasi pada Python
Misal kita hendak menemukan nilai minimum dari fungsi berikut:
Kita mulai dari import library yang dibutuhkan
import numpy as np # Numerical Python
import matplotlib.pyplot as plt # Static Ploting
import plotly.graph_objects as go # Dynamic/Interactive Ploting
import random # Modul untuk generasi Bilangan Random
random.seed(29) # Parameter bilangan randomMendefinisikan fungsi objektif
def f(x,y):
"Fungsi Objektif"
return x**2 + y**2 Visualisasi 3D fungsi objektif
# Menentukan Space Ploting
x, y = np.array(np.meshgrid(np.linspace(-5,5,100), np.linspace(-5,5,100)))
# Hasil Fungsi Objektif
z = f(x, y)
# Ploting 3D
fig = go.Figure(data=[go.Surface(z=z, x=x, y=y, colorscale ='viridis')])
fig.update_layout(title='Fungsi Objektif', autosize=False,
width=500, height=500,
margin=dict(l=65, r=50, b=65, t=90))
fig.show()Berikut outputnya:
Kita akan meminimumkan fungsi objektif tersebut. Untuk simulasi akan digunakan contour plot untuk melihat pergerakan partikel menuju titik minimum.
# Menentukan Space Ploting
x, y = np.array(np.meshgrid(np.linspace(-5,5,100), np.linspace(-5,5,100)))
# Hasil Fungsi Objektif
z = f(x, y)
x_min = x.ravel()[z.argmin()]
y_min = y.ravel()[z.argmin()]
plt.figure(figsize=(8,6))
plt.imshow(z, extent=[-5, 5, -5, 5], origin='lower', cmap='viridis', alpha=0.5)
plt.colorbar()
# Contour plot: Nilai minimum global ditunjukkan dengan tanda "X"
plt.plot([x_min], [y_min], marker='x', markersize=5, color="red")
contours = plt.contour(x, y, z, 10, colors='black', alpha=0.4)
plt.clabel(contours, inline=True, fontsize=8, fmt="%.0f")
plt.show()Berikut outputnya:
Inisialisasi populasi(posisi dan kecepatan acak) dalam hyperspace.
n_particles = 20 # Jumlah partikel
np.random.seed(29)
X = np.random.rand(2, n_particles) * 5 # Posisi partikel awal random
V = np.random.randn(2, n_particles) * 0.1 # Kecepatan partikel awal randomEvaluasi fitness partikel individu.
pbest = X # P best awal
pbest_obj = f(X[0], X[1])
gbest = pbest[:, pbest_obj.argmin()] # G best awal
gbest_obj = pbest_obj.min()Visualisasi partikel pada space fungsi objektif.
fig, ax = plt.subplots(figsize=(8,6))
fig.set_tight_layout(True)
img = ax.imshow(z, extent=[-5, 5, -5, 5], origin='lower', cmap='viridis', alpha=0.6)
fig.colorbar(img, ax=ax)
ax.plot([x_min], [y_min], marker='x', markersize=5, color="orange")
contours = ax.contour(x, y, z, 10, colors='black', alpha=0.4)
ax.clabel(contours, inline=True, fontsize=8, fmt="%.0f")
pbest_plot = ax.scatter(pbest[0], pbest[1], marker='o', color='red')
p_plot = ax.scatter(X[0], X[1], marker='o', color='green')
p_arrow = ax.quiver(X[0], X[1], V[0], V[1], color='yellow', width=0.005, angles='xy', scale_units='xy', scale=1)
gbest_plot = plt.scatter([gbest[0]], [gbest[1]], marker='*', s=100, color='cyan')
ax.set_xlim([-5,5])
ax.set_ylim([-5,5])Berikut outputnya:
Partikel divisualkan sebagai titik bulat berwarna hijau dengan tanda panah berwarna kuning sebagai vektor kecepatan partikel tersebut. Titik bintang berwarna biru adalah g best dan titik bulat berwarna merah adalah p best. Partikel akan bergerak menuju nilai minimum fungsi objektif yang ditandai dengan titik berbentuk silang “x” berwarna orange. Terlihat pada iterasi awal partikel masih jauh dari target. Kita akan melakukan iterasi untuk mendekati nilai minimum.
c1 = c2 = 0.1
w = 0.8
# Pembaruan nilai X dan V [Iterasi 2]
r = np.random.rand(2)
V1 = w * V + c1*r[0]*(pbest - X) + c2*r[1]*(gbest.reshape(-1,1)-X)
X1 = X + V
obj = f(X1[0], X1[1])
pbest[:, (pbest_obj >= obj)] = X1[:, (pbest_obj >= obj)]
pbest_obj = np.array([pbest_obj, obj]).max(axis=0)
gbest = pbest[:, pbest_obj.argmin()]
gbest_obj = pbest_obj.min()Visualisasi contour plot iterasi 2
Terlihat ada pergerakan yang cukup signifikan. Pada iterasi yang cukup besar terlihat pergerakan yang sangat jelas sebagai berikut:
Semakin tinggi iterasi, kerumunan semakin padat pada titik minimum. Berikut fungsi python untuk update posisi dan kecepatan partikel
def update():
"Fungsi untuk iterasi PSO"
global V, X, pbest, pbest_obj, gbest, gbest_obj
# Update parameter
r1, r2 = np.random.rand(2)
V = w * V + c1*r1*(pbest - X) + c2*r2*(gbest.reshape(-1,1)-X)
X = X + V
obj = f(X[0], X[1])
pbest[:, (pbest_obj >= obj)] = X[:, (pbest_obj >= obj)]
pbest_obj = np.array([pbest_obj, obj]).min(axis=0)
gbest = pbest[:, pbest_obj.argmin()]
gbest_obj = pbest_obj.min()
return X, V, pbest, gbestSimulasi dimulai
# Inisialisasi
n_particles = 20
np.random.seed(29)
X = np.random.rand(2, n_particles, ) * 5
V = np.random.randn(2, n_particles) * 0.1
# Evaluasi Fitness Posisi dan Kecepatan Partikel
pbest = X
pbest_obj = f(X[0], X[1])
gbest = pbest[:, pbest_obj.argmin()]
gbest_obj = pbest_obj.min()
# Jumlah Iterasi
n=30
# Iterasi Pembaruan Posisi dan Kecepatan Partikel
for i in range(n):
fig, ax = plt.subplots(figsize=(8,6))
fig.set_tight_layout(True)
img = ax.imshow(z, extent=[-5, 5, -5, 5], origin='lower', cmap='viridis', alpha=0.6)
fig.colorbar(img, ax=ax)
ax.plot([x_min], [y_min], marker='x', markersize=5, color="white")
contours = ax.contour(x, y, z, 10, colors='black', alpha=0.4)
ax.clabel(contours, inline=True, fontsize=8, fmt="%.0f")
pbest_plot = ax.scatter(pbest[0], pbest[1], marker='o', color='red')
p_plot = ax.scatter(X[0], X[1], marker='o', color='green')
p_arrow = ax.quiver(X[0], X[1], V[0], V[1], color='yellow', width=0.005, angles='xy', scale_units='xy', scale=1)
gbest_plot = plt.scatter([gbest[0]], [gbest[1]], marker='*', s=100, color='cyan')
ax.set_xlim([-5,5])
ax.set_ylim([-5,5])
title = '"PSO Step By Step: Pembaruan posisi dan kecepatan partikel" \n Iterasi ke: {:02d}'.format(i)
ax.set_title(title)
X, V, pbest, gbest = update()Pada looping di atas akan dihasilkan 30 gambar masing-masing untuk setiap n iterasi yang telah saya buat animasi sebagai berikut:
Penutup
Demikian tulisan saya bertajuk Ide Dibalik Particle Swarm Optimization, tulisan ini akan saya lanjutkan dengan implementasi PSO pada NN di Python. Doakan ya temen-temen agar dipermudah oleh Allah subhana wata’ala. Source code python pada artikel ini dapat diunduh pada link berikut:
Nun walqolami wama yasturun, Wassalamualaikum warahmatullahi wabarakatuh
Referensi
- Kennedy, J., & Eberhart, R. (1995, November). Particle swarm optimization. In Proceedings of ICNN’95-international conference on neural networks (Vol. 4, pp. 1942–1948). IEEE.
- Taufiq, Aji (2008, April). Gagasan Particle Swarm Optimization Dalam Al-Qur’an. Kaunia Jurnal Sains dan Teknologi (Vol. 4, No. 1)
- https://machinelearningmastery.com/a-gentle-introduction-to-particle-swarm-optimization/
- https://quran.com/ms
