MATLAB-Based Swarm Intelligence and Agents: Understanding Collective Behaviors
The study of swarm intelligence in MATLAB involves analyzing the interaction among simple autonomous agents to achieve specific goals. Swarm behavior mimics natural phenomena like flocking birds, with agents governed by local rules but working collectively towards a common objective. This collective intelligence plays a crucial role in optimizing solutions across various fields such as telecommunication, robotics, and transportation systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
MATLAB-Based Swarm Intelligence
Introduction to Swarms O The phenomenon of animals forming large swarms has lead to the study of swarm behaviour O Biologist and and computer scientists study biological swarms to analyze the interaction among social animals to achieve goals and to evolve themselves
Introduction to Swarms O Swarm Intelligence has become increasingly important in the solving of optimization problems in several fields O These fields can include: O Telecommunication systems O Robotics O electrical power systems O consumer appliances O traffic patterns in transportation systems O military applications
Introduction to Swarms O Swarm intelligence is the collective intelligence of a group of simple autonomous agents O Swarm intelligence involves N agents that are working together to complete a specific goal O The agents themselves are governed by simple local rules that when observed by an entire swarm can complete a goal O The agent interacts with its surrounding environment which may include other agents, but still acts relatively independent from those agents
Swarm Example O The movement of a bird within a flock is analogous to an agent within a swarm O The bird has its individual movements within the flock to maintain its speed and to prevent collisions by adjusting its speed and position relative to its flock mates O There is no flock leader that is assigning movements O The flock works together for benefits that include protection from animals and the location of food
Biological Background O The boid model was created in 1987 by Craig Reynolds O The boid is a distributed behavioral model which is used to simulate the motion of a flock of birds O The boid is an individual actor that navigates its position based upon its own perception of the changing environment
Boid Rules O The avoidence rule states that the boid must move away from other boids that are to close O The copy rule states that a boid must follow the general direction of the flock based upon the flocks average velocities and directions O The center rule states that the boid should minimize the exposure to flocks exterior by moving towards the perceived center of the flock O The view rule states that the boid should move laterally away from any boid that blocks its view
Swarm Robots O Swarms can provide increased task performance high reliability, low unit complexity and decreased cost as compared to traditional robotic systems O Application of Swarm robots include: O Flexible manufacturing systems O Spacecraft O Inspection/Maintenance O Construction O Agriculture O Medicine http://www.youtube.com/watch?v=i3ernrkZ91E
Swarm Robots O Gerardo Beni introduced cellular robotic systems which are a group of non- synchronized, autonomous and non- intelligent robots that coordinated on a n- dimensional cellular space under distributed control O Gerard Beni and Susan Hackwood proposed a model in which the robots would operate on a signpost concept
Signpost concept O The signposts modify the internal state of the robots as they move around O These signposts cause the entire swarm of robots to act as a collective unit to complete complex tasks O This model requires that the swarm circulate in a loop during its sensing operation
Swarm Robots taxonomy O A taxonomy of the different ways swarm robots can be characterized was introduced by Gregory Dudek O These areas can include: O Swarm size O Communication range O Topology O Bandwith O Swarm reconfigurability O Unit processing ability O Composition
Swarm Robots taxonomy O Swarm size can include single agents, pair agents, finite sets and infinite numbers O Communication ranges include: O None O Close by neighbors O Complete communication O Swarm composition can either be homogeneous or heterogeneous
Stability of Swarms O There are several simple principles of Swarm intelligence that include: O Proximity O Quality O Response diversity O Adaptability O Stability O The stability of the swarm is based upon the relative velocities and distance of adjacent agents
Stability of Swarms O Jin proposed the stability analysis of synchronized distributed control of 1D and 2D swarm structures O He proved that synchronized swarm structures would remain stable as long as the vertical disturbances vary slower than the response time of the servo systems for the agents
Swarm Intelligence O Gerardo Beni and Jing Wang coined the term Swarm intelligence in a 1989 article O Swarm intelligence techniques are population based stochastic methods used in combinatorial optimization problems O Swarm intelligence represents a metaheuristic approach to solving a variety of problems
Swarm Intelligence O Local interactions among the agents often cause a global pattern to emerge O This can be seen in several examples in nature such as: O Ant colonies O Bird flocking O Animal herding O Honey bees O Bacteria
Swarm Intelligence O Swarm intelligence algorithms have been applied to real world optimization problems in various engineering applications O Some of the techniques that were used include Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO)
Particle Swarm Intelligence O PSO was proposed by James Kennedy and R.C. Eberhart in 1995 O PSO was inspired by the social behavior of bird flocking and fish schooling O PSO as an optimization tool which provides a population based search procedure in which agents called particles change their position over time.
Particle Swarm Optimization Fig 1. Flock of Birds Fig 2. School of Fish
Particle Swarm Intelligence O Particles move around in multi-dimensional search space O Each particle adjust its position based upon its own experience and its neighbor experience O PSO systems combine local search methods with global methods to balance exploration and exploitation
Ant Colony Optimization O The ant system was first proposed by Colorni, Dorigo and Maniezzo O ACO algorithms are inspired by the foraging behavior of ant colonies O A colony of ants move through states of a problem corresponding to partial solutions of the problem to solve Fig 3. Colony of Ants
Ant Colony Optimization O The ants move based upon stochastic local decision policy by using two parameters which are trails and attractiveness O Each ant slowly completes a solution to the problem O When the ant has finished, it evaluates the solution and modifies the trail value on all nodes that were used to construct the path O This will direct the search of future ants
Properties of Swarm Intelligence O Unity: A swarm is a combination of several individuals O Fault tolerance: Swarm intelligence does not rely on a central controller and therefore the loss of a few pathways will not result in a complete failure O Rule based behavior: A set of rules are followed by each agent that take advantage of the local information gained from its environment or other neighboring agents
Properties of Swarm Intelligence O Autonomy: The behavior of the entire swarm system is self organized. (No human involvement) O Scalability: The population of the agents can be easily adapted according to the network size O Adaptation: The individuals present in the ant change, die or reproduce according to the network changes
Properties of Swarm Intelligence O Speed: The individuals in the group change their behavior rapidly according to the neighbors O Modularity: The behavior of agents is independent of the others in the group O Parallelism: The operations of the agents are inherently parallel
Particle Swarm Optimization O inspired by social behavior of flocks of birds, school of fish, swarm of bees and sometimes the social behavior of human. O PSO is similar to Genetic Algorithms in the sense that there is a population initialization with random solutions and the global optima is searched for in successive generations O PSO is dissimilar to Genetic algorithms because there is no crossover or mutations
Particle Swarm Optimization O Particles move through the problem space following the current optimum particles O The concept is that for every instant in time the velocity of the particle (otherwise known as potential solution) changes between its pbest and lbest locations
Particle Swarm Optimization O The fitness value (best value) that is found by each individual particle is called the pbest O The best fitness value that is found by any of the particles neighbors is referred to as the lbest O If the particle is taking into account the entire population of the swarm as its neighbors the best is referred to as the gbest (Global best)
PSO Algorithm Flowchart Fig 4. PSO Algorithm Flowchart http://mnemstudio.org/part icle-swarm-introduction.htm
Mathematical Model of PSO O W= inertia weight O C1 is called the coefficient of the self recognition component and is usually a positive constant O C2 is called the coefficient of the social component and is usually a positive constant O C1 and C2 are known as learning factors
Mathematical Model of PSO Fig 5. Used to find the new velocity based upon the personal best of the particle and the global best for the swarm Fig 6. Used to discover the new position for the particle based upon the old position and the new velocity of the particle
Mathematical Model of PSO O The particles are held at maximum moving distance per iteration O This is done so that the particles can be guided effectively throughout the search space O The velocity is clamped between [- max velocity , max velocity] Fig 7. used to clamp the new velocity between [- max velocity , max velocity]
Pseudocode for PSO Algorithm Fig 8. Pseudocode for PSO Algorithm
Matlab PSO to Minimize Objective Function O Solves (x - 15) ^2 + (y - 20) ^ 2 Fig 9. PSO
Parameters and Tuning of PSO O There are not many parameters that are required to be initialized for the initialization process of PSO O They are as follows: O Number of particles O Inertia Weight O Learning Factors O Range and Dimension of particles O Stopping Condition
Number of Particles O The general range of particles that is chosen is between 20 and 40 particles O For difficult problems sometimes 100 to 200 particles can be used
Inertia Weight O Plays an important role in the convergence behavior of PSO algorithm O The inertia weight takes into account the previous history of velocities on the current one O W regulates the trade off between the global and the local exploration abilities O A balance between global and local exploration abilities is obtained by decreasing the inertia weight to 0 over the course of all of the iterations
Learning Factors O The fine tuning of the learning factors C1 and C2 aid in faster convergence and alleviation of local minima O Several papers report that C1=C2=1.49 may provide better results O Other papers report that C1+C2=4 may provide better results where a larger self recognition component (C1 ) is used
Range and Dimension of Particles O Various ranges can be used for different dimensions of particles O The range of the particles is usually set as the maximum velocity of the particles O For example if the particle belongs to the range of [-20, 20] then the maximum velocity would be 40
Stopping Condition O The Stopping Condition is generally set by one of the following criteria: O The stopping criteria can be set to a fix number of iterations O The stopping criteria can be set to when the error between the objective function value and the best fitness value is less than a pre set threshold
Neighborhood Topologies O The most common neighborhood topologies based upon the movement of swarms are as follows: O Star (Wheel) topology O Ring (Circle) topology O Von Neumann (Square) topology
Star topology O Star topology is a fully connected neighborhood relation O Star topology is also known as the gbest model O All the particles in the problem space connect to a specific particle which works as the central hub
Star Topology O This topology has the downside of a premature convergence problem (due to fast propagation) Fig 10. representation of the Star neighborhood topology
Ring Topology O The ring topology is also known as the lbest model O In this model each particle is connected to the closest neighbor O This cause the propagation of information to be quit slower than in ring topology O using the ring topology will slow down the convergence rate because the best solution found has to propagate through several neighborhoods before affecting all particles in the swarm
Ring Topology O This slower propagation will allow the particles to search more areas in the problem space and will lessen the chance of premature convergence Fig 11. representation of the Ring neighborhood topology
Von Neumann Topology O Kennedy and Mendes proposed Von Neumann Topology O The topology can be seen as a spatial neighborhood when it is determined that the Euclidean distance between two particles O Particles are connected using a grid network where each particle is connected to four neighboring particles
Von Neumann Topology O Von Neumann topology will slow down convergence rate which will allow the particles to search the problem space more effectively Fig 12. representation of the Von Neumann neighborhood topology
Extended Models of PSO O There are several extended models of Particle Swarm Optimization that include: O PSO-1 O PSO-2 O PSO-3 O PSO-4
PSO-1 O The next position of each particle is sampled from the global search range O Sampling will continue until the next position of each particle is in the local range Fig 13. the sampling range
PSO-2 O In PSO-2 a particle that is close to the current best particle is randomly generated with a threshold value p (between [0,1]) O R is the radius of the area around the global best position xgB O S is randomly taken from an uniform distribution between [-R, R] Fig 14. the position of the particle is calculated
