Optimisasi dengan metaheuristik

Swarm Based Optimization Algorithm

Ayomi Sasmito, [Link]., [Link].

[Link]@[Link]

Ayomi Sasmito (PRASMUL) Optimization Theory 1 / 15

Outline Perkuliahan

1 Introduction

Ayomi Sasmito (PRASMUL) Optimization Theory 2 / 15

Introduction

Swarm intelligence is a concept that emerged from the interactions of many non-intelligent
units, combining the power of neural networks and deep learning to create intelligent sys-
tems. Swarm intelligence algorithms share the key aspect of being composed of a large
set of processing units with limited computational power, forming powerful information
processing systems. Intelligence is often associated with search and optimization, and
swarm-based optimization algorithms are part of the family of algorithms inspired by na-
ture.

Ayomi Sasmito (PRASMUL) Optimization Theory 3 / 15

Swarm intelligence (SI) is a unique category of algorithms that promotes cooperation
and collaboration rather than competition among the members of the swarm. SI ac-
counts for a variety of computational models with significant applications, including
traveling salesman problems, vehicle routing, flow shop scheduling, and robotics. This
article presents the principles of swarm-based optimization and representative algo-
rithms for continuous and discrete optimization problems.

Ayomi Sasmito (PRASMUL) Optimization Theory 4 / 15

Principles of Swarm Intelligence

1 Awareness: Each member must be aware of their surroundings and abilities

2 Autonomy: To self-coordinate, each member must operate as an autonomous
master (not as a slave).
3 Solidarity: When a task is completed, members should autonomously look for a
new task.
4 Expandability: The system must permit dynamic expansion where members are
seamlessly aggregated.
5 Resiliency: When members are removed, the system must be self-healing.

Ayomi Sasmito (PRASMUL) Optimization Theory 5 / 15

Real World Examples

We have various intelligence examples in nature such as Ant colonies, Bee beehives,
Fish schooling, Bird flocking, Bacterial growth, and microbial intelligence.
Also, there are biological advantages of swarm intelligence. For example, birds steal in-
formation using up to a fifth less energy than those that fly solo. In addition, Swarm in-
telligence is modeled for the purpose of understanding microscopic (global) transforma-
tions. Furthermore, it allows getting ideas for artificial systems the similar proprieties.

Ayomi Sasmito (PRASMUL) Optimization Theory 6 / 15

Besides, there are two main development areas of swarm intelligence:
Particle Swarm Optimization: One of the most well-known swarm intelligence-based
optimization techniques. Particle swarm optimization was modeled by the social be-
havior of animals and insects. In this context, every individual swarm member is
handled as a particle. Cooperation and learning enable the collective intelligence of
these dispersed particles.
Ant Colony Optimization: Based on the social instincts of actual ants for their com-
munity, the ant colony optimization approach is an essential component of swarm
intelligence. This algorithm enables them to cooperate to accomplish a common ob-
jective. Since they are all gathered in one place, the ants must locate the food and
carry it back to the colony.

Ayomi Sasmito (PRASMUL) Optimization Theory 7 / 15

Particle Swarm Optimization (PSO)

Inspirasi
Algoritma Partical Swarm Optimization (PSO) diperkenalkan oleh kennedy dan Elberhart
pada tahun 1995, proses algoritmanya diinspirasi oleh perilaku sosial dari binatang,
seperti sekumpulan burung dalam suatu swarm.

PSO
Partical Swarm Optimization (PSO) adalah salah satu dari teknik komputasi evolusioner,
yang mana populasi pada PSO didasarkan pada penelusuran algoritma dan diawali
dengan suatu populasi yang random yang disebut particle.

Ayomi Sasmito (PRASMUL) Optimization Theory 8 / 15

Particle Swarm Optimization (PSO)

Particle Swarm Optimization (PSO) adalah algoritma komputasi evolusioner di mana

setiap partikel bergerak melalui penelusuran ruang dengan kecepatan dinamis yang
disesuaikan dengan perilaku historisnya.
PSO mirip dengan algoritma genetika karena dimulai dengan populasi acak dalam
bentuk matriks, tetapi PSO tidak memiliki operator evolusi seperti crossover dan
mutasi. Setiap partikel bergerak ke area penelusuran yang lebih baik setelah proses
penelusuran, dan vektor kecepatan diperbarui untuk setiap partikel.
PSO telah menarik perhatian para peneliti karena kesederhanaan algoritmanya dan
performanya yang baik. Algoritma ini telah diterapkan dalam berbagai persoalan
optimisasi seperti masalah rute kendaraan, masalah salesman keliling, masalah rute
inventaris, dan lainnya.
PSO telah populer menjadi optimisasi global dengan sebagian besar permasalahan
dapat diselesaikan dengan baik di mana variabelvariabelnya adalah bilangan riil.

Ayomi Sasmito (PRASMUL) Optimization Theory 9 / 15

Istilah-istilah umum dalam PSO

1 Swarm : Populasi dari suatu algoritma.

2 Particle : Anggota (individu) pada suatu swarm. Setiap particle merepresentasikan
suatu solusi yang potensial pada permasalahan yang diselesaikan. Posisi dari suatu
particle ditentukan oleh representasi dari solusi saat itu.
3 Pbest (Personal Best) : Posisi Pbest suatu particle yang menunjukkan posisi particle
yang dipersiapkan untuk mendapatkan suatu solusi yang terbaik.
4 Gbest (Global Best) : posisi terbaik particle pada swarm.
Velocity (vektor) : vektor yang menggerakkan proses optimisasi yang menentukan
arah dimana suatu particle diperlukan untuk berpindah (move) untuk memperbaiki
posisinya semula.

Ayomi Sasmito (PRASMUL) Optimization Theory 10 / 15

1 Ukuran Swarm
Ukuran swarm atau populasi yang dipilih bergantung pada persoalan yang dihadapi.
Umumnya berkisar antara 20 sampai 50. PSO hanya perlu ukuran swarm atau
populasi yang lebih kecil dibanding algoritma-algoritma evolusioner lainnya untuk
mendapatkan solusi-solusi terbaik.
2 Koefisien akselerasi
Nilai-nilai untuk koefisien akselerasi c1 dan c2 adalah 2. Namun, biasanya nilai c1
dan c2 adalah sama dan pada rentang 0 dan 4.
3 Updating Kecepatan
Perubahan velocity pada algoritma PSO terdiri dari tiga bagian yaitu social part,
cognitive part, dan momentum part. Bagian tersebut menentukan keseimbangan
antara kemampuan penelusuran global dan lokal, oleh karena itu dapat
memberikan performansi yang baik pada PSO.

Ayomi Sasmito (PRASMUL) Optimization Theory 11 / 15

Secara matematis, diberikan A ⊆ R n sebagai ruang pencarian dan f : A− > Y ⊆ R
adalah fungsi tujuan. Seperti dijelaskan sebelumnya, PSO merupakan algoritma berbasis
populasi yaitu dengan mengeksploitasi populasi solusi untuk menyelidiki ruang pencar-
ian secara bersamaan. Dalam PSO, disebut dengan swarm dan individu disebut dengan
partikel.
Swarm didefinisikan sebagai himpunan :

S = {x1 , x2 , . . . , xN } (1)

dan N partikel (calon solusi) didefinisikan sebagai berikut :

xi = (xi1 , xi2 , . . . , xin )T ∈ A, i = 1, 2, . . . , N. (2)

Partikel-partikel tersebut bergerak dalam ruang pencariannya, pergerakan ini dilakukan

dengan menyesuaikan posisi mereka dengan menggunakan kecepatan (velocity) yang
didefinisikan sebagai berikut :

vi = (vi1 , vi2 , . . . , vin )T ∈ A, i = 1, 2, . . . , N. (3)

Ayomi Sasmito (PRASMUL) Optimization Theory 12 / 15

Kecepatan tersebut disesuaikan secara bertahap sehingga diharapkan partikel mampu
mengunjungi setiap wilayah A. Jika t dinotasikan sebagai jumlah iterasi, maka posisi saat
ini dari partikel ke-i dan kecepatannya masing-masing dinotasikan sebagai xi (t) dan vi (t).
Kecepatan diperbarui berdasarkan informasi yang diperoleh dari langkah sebelumnya.
Hal ini diimplementasikan dalam sebuah memori, dimana setiap partikel dapat menyimpan
posisi terbaik yang pernah dikunjungi selama pencarian, sehingga S berisi posisi partikel
saat ini. Memori yang dipertahankan oleh PSO adalah :

P = {p1best , p2best , . . . , pNbest } (4)

Yang mengandung best positions

pibest = (pi1 , pi2 , . . . , pin ) ∈ A, i = 1, 2, . . . , N (5)

dan pernah dikunjungi masing-masing partikel. Sehingga posisi ini didefinisikan sebagai
berikut :
pibest = arg min fi (t) (6)
dengan arg min fi (t) adalah partikel fi (t) minimal.
Masing-masing partikel memperbarui kecepatan dan posisinya dengan persamaan

vij (t + 1) = vij (t) + c1 r1 (pibest − xij (t)) + c2 r2 (gbest − xij (t)) (7)
xij (t + 1) = xij (t) + vij (t + 1) (8)

Ayomi Sasmito (PRASMUL) Optimization Theory 13 / 15

Prosedur algoritma dasar PSO

1 Inisialisasi posisi awal partikel (xi ) dan kecepatan awal (vi ), dengan i = 1, 2, . . . , N
dan N adalah ukuran swarm.
2 Evaluasi nilai fungsi tujuan untuk setiap partikel, f (xi ).
3 Tentukan pibest awal dan gbest awal.
4 Update Kecepatan dengan Persamaan (7)
5 Update Posisi partikel baru dengan Persamaan (8).
6 Evaluasi kembali nilai f (xi ), jika f (xi ) ≤ f (pibest ) maka pibest = xi , setelah
mendapatkan pibest baru, maka didapatkan gbest baru.
(
pibest iff (pibest ) < f (gbest )
gbest =
gbest iff (pibest ) ≥ f (gbest )

7 Jika iterasi sudah maksimum dan konvergen, maka algoritma berhenti, jika tidak
maka kembali ke Langkah 4.

Ayomi Sasmito (PRASMUL) Optimization Theory 14 / 15

Latihan

* Dikumpulkan maksimal hari ini pukul 11.30 di LMS dalam bentuk pdf.
Misalkan kita mempunyai persoalan optimasi dengan satu variabel sebagai berikut :

max f (x, y ) = (100 − x)2 − 25y 3 + 5

dengan 60 ≤ x, y ≤ 120. Dengan menggunakan particle swarm optimization, carilah

solusinya dengan jumlah partikel = 5, c1 = 0.4, c2 = 0.6 dan maksimum iterasi sama
dengan 2.

Ayomi Sasmito (PRASMUL) Optimization Theory 15 / 15