PRESENTASI_particle swarm optimization_CTSS.pdf

Presentasi particle swarm optimization

1. Presented by: Medria Hardhienata
PengenalanAlgoritmeParticle Swarm Optimization (PSO) sertaImplementasinyadalamSistemMulti-Agent
11thGraduate Student Sustainability Seminar
CTSS IPB
13 Januari2022

2. Quick Poll

3. PART I : INTRODUCTION

4. What is
Particle Swarm
Optimization?

5. Particle swarm optimization is a stochastic populationbasedoptimization approach, first published by Kennedy and Eberhart in 1995 *
*) J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Joint Conference on Neural Networks, IEEE Press, 1995, pp. 1942–1948.
R.C. Eberhart, J. Kennedy, A new optimizer using particle swarm theory, in: Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan, 1995, pp. 39–43.

6. Remember about Optimization?
Optimization problem: Maximizing or minimizing some function relative to some set, often representing a range of choices available in a certain situation.
Contoh:

7. Remember about Optimization?
Common applications of optimization: Minimal cost, maximal profit, minimal error, optimal design, optimal managementetc.

8. Introduction on PSO
§Inspired by social behavior of birds and fishes
§Combines self-experience with social experience
§Population-based optimization

9. Origins and
Inspiration
from Natural Systems

10. “When designing artificially intelligent systems, researchers have historically turned to Mother Nature for guidance. “
--Louis Rosenberg (“Artificial Swarm Intelligence, a Human-in-the-Loop Approach to A.I.", 2016)

11. Social behaviour of fishes

12. Social behaviour of birds

13. Introductionto thePSO: Origins
In 1986, Craig Reynolds described this processin 3 simple
behaviors:
Separation
avoid crowding local
flockmates
Alignment
move towards the average
heading of local
flockmates
Cohesion
move toward the average
position of local
flockmates
Andry Pinto et al. TheParticleSwarmOptimizationAlgorithmSlides. DecisionSupport2010-2011

14. Can we adopt the idea for solving
optimization problem?

15. Origins and Inspiration from Natural
Systems
Developed by Jim Kennedy, Bureau of Labor Statistics, U.S. Department of Labor and Russ Eberhart, Purdue University at1995.

16. The “inventors” (1)
Russell
Eberhart
[email protected]

17. Prof.Eberhartin SCCI Conference
2014, Florida

18. The “inventors” (2)
James Kennedy
[email protected]

19. Other scientist working on PSO:
Prof.AndriesEngelbrecht
https://www.researchgate.n
et/profile/Andries-
Engelbrecht-2/4

20. Sowith the inspiration from nature,
how do you think the idea can be
adopted for solving optimization
problem?

21. As stated before, PSO simulates the behaviorsof bird flocking.
Suppose the following scenario: a group of birds are randomly searching food in an area. There is only one piece of food in the area being searched. All the birds do not know where the food is. But they know how far the food is in each iteration. Sowhat's the best strategy to find the food? *
*) http://www.swarmintelligence.org/tutorials.php
Scenario

24. The effective one is to follow the bird which is nearest to the food.

25. PSO general Ideas
§PSO learned from the above scenario and used it to solve the optimization problems.
§In PSO, each single solution is a "bird" in the search space. We
call it "particle".

26. PSO general Ideas
§All of particles have fitness values which are evaluated by the fitness function to be optimized, andhave velocities which direct the flying of the particles.
§The particles fly through the problem space by following the current optimum particles.

27. Concept
Uses a number ofparticles that constitute a swarm moving around in the search space looking for the best solution.
Each particle in the search space adjusts its “flying” according to its own flying experience as well as theflying experience of other particles.
Andry Pinto et al. TheParticleSwarmOptimizationAlgorithmSlides. DecisionSupport2010-2011

28. Concept
Uses a number ofparticles that constitute a swarm moving around in the search space looking for the best solution.
Each particle in the search space adjusts its “flying” according to its own flying experience (personal best (pbest)) as well as theflying experience of other particles(global best (gbest)).
Andry Pinto et al. TheParticleSwarmOptimizationAlgorithmSlides. DecisionSupport2010-2011

29. Best values
Pbest: The first one is the best solution (fitness) it has achieved so far. (The fitness value is also stored.) This value is called Pbest.
Gbest: Another "best" value that is tracked by the particle swarm optimizer is the best value, obtained so far by any particle in the population. This best value is a global best and calledGbest.
Andry Pinto et al. TheParticleSwarmOptimizationAlgorithmSlides. DecisionSupport2010-2011

31. PART II : PSO ALGORITHM II

32. Particle Swarm Optimization
Swarm: a set of particles (S)
Particle: a potential solution
Position:
Velocity:
Each particle maintains
Individual best position (PBest)
Swarm maintains its global best (GBest)
n
niiii xxx ÂÎ= ),...,,(
,2,1,x
n
niiii vvv ÂÎ= ),...,,(
,2,1,v
SFitness
function
Fitness
value
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

33. PSO Algorithm
Basic algorithm of PSO
1.Initialize the swarm form the solution space
2.Evaluate the fitness of each particle
3.Update individual and global bests
4.Update velocity and position of each particle
5.Go to step2, and repeat until termination condition
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

34. PSO Algorithm
}Original velocity update equation
◦w,c1,c2: Constant
◦random1(), random2(): random variable
}Position update
))((()
))((())()1(
22
11
kGBestrandomc
kPBestrandomckk
i
iiii
x
xvv
-´´+
-´´+´=+w
)1()()1( ++=+ kkk
iii vxx
social cognitiveInertia)1( ++=+k
iv
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

35. PSO Algorithm
Particle’s velocity
social cognitiveInertia)1( ++=+k
iv
GBest
Inertia
cognitive
social
PBest
x(k)
x(k+1)
v(k+1)
v(k)
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

36. PART III:
PSO SOLUTION UPDATE IN 2D

37. PSO solution update in 2D
x(k) -Current solution (4, 2)
PBest -Particle’s best solution (9, 1)
GBest-Global best solution (5, 10)
GBest
PBest
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

38. PSO solution update in 2D
Current solution (4, 2)
Particle’s best solution (9, 1)
Global best solution (5, 10)
Inertia: v(k)=(-2, 2)
x(k) -Current solution (4, 2)
PBest -Particle’s best solution (9, 1)
GBest-Global best solution (5, 10)
GBest
PBest
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

39. PSO solution update in 2D
Current solution (4, 2)
Particle’s best solution (9, 1)
Global best solution (5, 10)
ØInertia: v(k)=(-2,2)
ØCognitive:
PBest-x(k)=(9,1)-(4,2)=(5,-1)
ØSocial:
GBest-x(k)=(5,10)-(4,2)=(1,8)
x(k) -Current solution (4, 2)
PBest -Particle’s best solution (9, 1)
GBest-Global best solution (5, 10)
GBest
PBest
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

40. PSO solution update in 2D
x(k) -Current solution (4, 2)
PBest -Particle’s best solution (9, 1)
GBest-Global best solution (5, 10)
ØInertia: v(k)=(-2,2)
ØCognitive:
PBest-x(k)=(9,1)-(4,2)=(5,-1)
ØSocial:
GBest-x(k)=(5,10)-(4,2)=(1,8)
v(k+1)=(-2,2)+0.8*(5,-1)
+0.2*(1,8) = (2.2,2.8)
GBest
PBest
v(k+1)
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

41. PSO solution update in 2D
GBest
PBest
x(k+1)
x(k) -Current solution (4, 2)
PBest -Particle’s best solution (9, 1)
GBest-Global best solution (5, 10)
ØInertia: v(k)=(-2,2)
ØCognitive:
PBest-x(k)=(9,1)-(4,2)=(5,-1)
ØSocial:
GBest-x(k)=(5,10)-(4,2)=(1,8)
Øv(k+1)=(2.2,2.8)
x(k+1)=x(k)+v(k+1)=
(4,2)+(2.2,2.8)=(6.2,4.8)
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

42. PART IV: EXAMPLE

43. Example
Find the minimum of this function
21
2
221
2
1 323)( xxxxxxf --+-=x
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

44. Example
ú
û
ù
ê
ë
é
=
1.5771 3.3118- 2.7043- 2.7580- 0.4894-
4.0058- 3.1717 4.0005 0.6238 2.2824
1x
ú
û
ù
ê
ë
é
=
0.3122 0.6079 0.2500- 0.5598- 0.2133
0.2207 0.0264 0.6942 0.1712 0.6321-
1v
ú
û
ù
ê
ë
é
=
0.5338- 0.3199 0.3385- 2.2903- 0.3187-
3.3541 2.2018 2.5656 1.4300 1.7767
2x
ú
û
ù
ê
ë
é
=
2.1109- 3.6317 2.3657 0.4677 0.1706
7.3599 0.9700- 1.4349- 0.8063 0.5057-
2v
ú
û
ù
ê
ë
é
=
2.0485- 2.7884 1.5627 0.1959 0.1822-
7.9656 1.1350 1.0728 2.4464 1.3721
3x
ú
û
ù
ê
ë
é
=
1.5146- 2.4685 1.9012 2.4862 0.1365
4.6114 1.0667- 1.4928- 1.0163 0.4046-
3v
…
ú
û
ù
ê
ë
é
=
0.21060.21560.23780.24360.2056
0.21670.22930.24000.21970.2230
tx 25.0
2057.0
2227.0
-=
ú
û
ù
ê
ë
é
= fitnessGBest
Particle Swarm Optimization Slideshare.Published by Gertrude Bellhttps://slideplayer.com/slide/13389026/

45. PART V: DEMO

47. PART VI: EXAMPLE OF PSO IMPLEMENTATION IN
MULTI-AGENT SYSTEM

48. In the last few years, PSO has been widely employed to solve a number ofoptimization problems, including the problem of task allocation in multi-agent system(Hardhienata M. et al, 2012)
M. K. D. Hardhienata, K. E. Merrick, V. Ugrinovskii,“Task allocation in multi-agent systems using models of motivation and leadership,” in 2012 IEEE
Congress on Evolutionary Computation, 2012, pp. 1–8, doi: 10.1109/CEC.2012.6256114

49. What is a task allocation problem?
Illustration of the task allocation problem
(source: Epuckrobots at CRRC, UW Newport)

50. Introduction
Definition
GivenMagentsandNtaskswithunknownlocations,ataskallocationproblemisdefinedasaproblemoflocating(discovering)tasksanddistributingagentstothetaskssothatacommongoalofthesystemcanbeachieved.
Research
QuestionObjectivesSignificanceInnovationLiterature ReviewConceptImplementation &
ExperimentationsMilestonesSummaryIntroduction
Robots to the rescue (TEEX, 2011)
Task Allocation Problems
Rollingoff a group of soldier
robot (www.jber.af.mi)(Kernbach,2009)
Even distribution of agents to tasks
(Mengand Gan, 2008).
A small number of agentsRandomly positioned
(Doctor,2004)

51. Amulti-agent systemis a computerized system composed of multiple interacting intelligent agents(Huetal., 2020), (Hu et al., 2021)
Multi-agent systems can solve problems that are difficult or impossible for an individual agent to solve(Hu et al, 2021)
Hu, J.; Bhowmick, P.; Jang, I.; Arvin, F.; Lanzon, A., "A Decentralized Cluster Formation Containment Framework for Multirobot Systems" IEEE Transactions on Robotics, 2021.
Hu, J.; Niu, H.; Carrasco, J.; Lennox, B.; Arvin, F., "Voronoi-Based Multi-Robot Autonomous Exploration in Unknown Environments via Deep Reinforcement Learning" IEEE Transactions on Vehicular
Technology, 2020.
Hu, J.; Turgut, A.; Lennox, B.; Arvin, F., "Robust Formation Coordination of Robot Swarms with Nonlinear Dynamics and Unknown Disturbances: Design and Experiments" IEEE Transactions on Circuits
and Systems II: Express Briefs, 2021.

52. What’s the idea?

53. Objective*
This study considers the task allocation problem in the case where there is a small
number of agents initialized at a single point.
The objective is to achieve an even distribution of agents to tasks.
To address this problem, this study proposes a new method that endows agents
with models of motivation and leadership to aid their coordination.
SignificanceInnovationLiterature ReviewConceptImplementation &
ExperimentationsMilestonesSummaryIntroductionObjectives
*) M. K. D. Hardhienata, K. E. Merrick, V. Ugrinovskii,“Task allocation in multi-agent systems using models of motivation and leadership,” in 2012 IEEE
Congress on Evolutionary Computation, 2012, pp. 1–8, doi: 10.1109/CEC.2012.6256114

54. Objective
The proposed approach uses the Particle Swarm Optimization (PSO) methodology
using a ring neighborhoodtopology (X. Li, 2010)*, (Eberhard and Kennedy, 1995)**
as a foundation and incorporates computational models of motivation to achieve
the goals of task allocation more effectively.
SignificanceInnovationLiterature ReviewConceptImplementation &
ExperimentationsMilestonesSummaryIntroductionObjectivesResearch
Question
*) XiaodongLi. Niching without niching parameters: Particle swarm optimization using a ring topology. IEEE Trans. Evol. Comput., 14(1):150–169, Feb. 2010.
**) J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Joint Conference on Neural Networks, IEEE Press, 1995, pp. 1942–
1948

55. What are models of motivation?

56. AffiliationAchievementPower
May select goals with a
higher probability of
success
Tend to avoid both low-risk
and high-risk
May select goals with higher
incentive
Models of Motivation
Motivation
Three motive profiles in human (McClelland,1975)* , (Merrick and Shafi,
2011)**
*)D.C. McClelland. Power: The Inner Experience. Irvington, New York, 1975.
**)Merrick KE, ShafiK. Achievement, affiliation, and power: Motive profiles for artificial agents.Adaptive Behavior. 2011;19(1):40-62
.

57. Particle Swarm Optimization Algorithms
in Task Allocation problems
5858ObjectivesConceptImplementation &
ExperimentationsSummaryMilestonesIntroductionResearch
QuestionSignificanceLiterature ReviewInnovation
A generic scheme for application of the PSO
methodology to solving a task allocation
problem adopted in (Mengand Gan, 2007).
In this scheme, agents are regarded as
particles, which update their positions in
accordance to the PSO rules to approach the
location of a task in the search space.
the local best-position of a task which is selected
based on the highest visibilityvalue.
sk
Task 1
Task 2
Distance 1
Distance 2
Visibility 1 > Visibility 2

58. Particle Swarm Optimization Algorithms
in Task Allocation problems
5959ObjectivesConceptImplementation &
ExperimentationsSummaryMilestonesIntroductionResearch
QuestionSignificanceLiterature ReviewInnovation
A generic scheme for application of the PSO
methodology to solving a task allocation
problem adopted in (Meng and Gan,
2008)*.
In this scheme, agents are regarded as
particles, which update their positions in
accordance to the PSO rules to approach the
location of a task in the search space.
the task that has the highest task utility value
sk
Task 1
Utility 1 < Utility 2
s1
s4
s5
s3
Task 2 s2
Redundancy 1
Redundancy 2
*) Yan Meng and Jing Gan. Self-adaptive distributed multi-task allocation in a multi-robot system. In IEEE Congr. Evol. Comput., pages 398–404, Jun.
2008.

59. Motivated Particle Swarm Optimization (MPSO)*
6060ObjectivesConceptImplementation &
ExperimentationsSummaryMilestonesIntroductionResearch
QuestionSignificanceLiterature ReviewInnovation
Let and be the position and velocity of agent kat time t
To update their positions, the agents use a fitness function whose extremacorrespond to the tasks.
One possible scenario assumed in the paper is to equip the tasks with transmitters to radiate
signals, and equip each agent with a sensor to detect that signal.
Task
sk
Agent
In potential real world scenarios, the tasks can be
associated with radio base stations or humans, while
the signal can be a radio transmission or the sound of
survivors calling for help.
*) M. K. D. Hardhienata, K. E. Merrick, V. Ugrinovskii,“Task
allocation in multi-agent systems using models of
motivation and leadership,” in 2012 IEEE Congress on
Evolutionary Computation, 2012, pp. 1–8

60. TheGraph of the Incentive Function
6262ObjectivesConceptImplementation &
ExperimentationsSummaryMilestonesIntroductionResearch
QuestionSignificanceLiterature ReviewInnovation
The graph of the incentive function for all possible values of , in the
case M=15 ( in the figure is denoted as 'a')

61. Experimentations
Testing problem :Vincent function (Shirand Back, 2006)
In the range of 1.5<x<7 and 1.5<y <7, this function has 9 global maxima and no local
maxima. Its height in each position can be thought of as representing the strength of a signal
from a task.
lbestPSO with a ring
topology
MPSO
100 homogenous agents80 agents with affiliation
motive profiles and 20
agents with power motive
profiles
15 homogenous agents 9 affiliation and 6 power
agents

62. Performance Results
* experiment repeated 50 times6464646464646464646464Objectives SummaryMilestonesIntroductionResearch
QuestionSignificanceInnovationConceptLiterature ReviewImplementation &
Experimentations
7,56
8,98,989
0
2
4
6
8
Ring (15)MPSO (9+6)Ring (100)MPSO (80+20)
Average number of discovered tasks
3,1
5,56
7,1
8,68
1
3
5
7
9
Ring (15)MPSO (9+6)Ring (100)MPSO (80+20)
Average number of tasks
to which the agents are allocated
Random initialization Single Point Initialization
1,24
8,96
1,9
9
0
2
4
6
8
Ring (15)MPSO (9+6)Ring (100)MPSO (80+20)
Average number of discovered tasks
1
5,4
1,3
8,32
0
2
4
6
8
10
Ring (15)MPSO (9+6)Ring (100)MPSO (80+20)
Average number of tasks
to which the agents are allocated
Single Point Initialization Random initialization

63. PART VII: CURRENT SWARM ROBOTICS RESEARCH IN
THE DEPARTMENT OF COMPUTER SCIENCE IPB

64. Task Allocation in Multi-agent Systems: E-Pucks Robots
Task Allocationusing EpuckRobots (Harmanda, T., PriandanaK., Hardhienata M,
2020)

65. PART VI: WHAT’S NEW?

66. ”Artificial Swarm Intelligence, a Human-in-the-Loop Approach to A.I.”*
*)Rosenberg, L. (2016). Artificial Swarm Intelligence, a Human-in-the-Loop Approach to A.I.Proceedings of the AAAI Conference on Artificial
Intelligence,30(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/9833

67. Personal doc. Florida 2014

68. References
J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proceedings of the IEEE International Joint Conference on Neural Networks, IEEE Press, 1995, pp. 1942–1948.
R.C. Eberhart, J. Kennedy, A new optimizer using particle swarm theory, in: Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan, 1995, pp. 39–43.
Andry Pinto et al. TheParticleSwarmOptimizationAlgorithmSlides. DecisionSupport2010-2011.
http://www.swarmintelligence.org/tutorials.php
Pictures are taken from https://www.pexels.com/
and various other sources

69. Thanks!