Particle Swarm Optimization - Université Libre de Bruxelles

Particle Swarm Optimization Introduction Marco A. Montes de Oca IRIDIA-CoDE, Universit´e Libre de Bruxelles (U.L.B.) May 7, 2007 Marco A. Montes de Oca Particle Swarm Optimization Presentation overview Origins The idea Continuous optimization The basic algorithm Main variants Parameter selection Research issues Our work at IRIDIA-CoDE Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: Origins How can birds or fish ex- hibit such a coordinated collective behavior? Marco A. Montes de Oca Particle Swarm Optimization Particle swarm

optimization: Origins Reynolds [12] proposed a behavioral model in which each agent follows three rules: Separation. Each agent tries to move away from its neighbors if they are too close. Alignment. Each agent steers towards the average heading of its neighbors. Cohesion. Each agent tries to go towards the average position of its neighbors. Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: Origins Kennedy and Eberhart [6] included a ‘roost’ in a simplified Reynolds-like simulation so that: Each agent was attracted towards the location of the roost. Each agent ‘remembered’ where it was closer to the roost. Each agent shared information with its neighbors (originally, all other agents) about its closest location to the roost. Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The idea Eventually, all agents ‘landed’ on the roost. What if the notion of distance to the roost is changed by an unknown function? Will the agents ‘land’ in the minimum? J. Kennedy R. Eberhart Marco A. Montes de Oca Particle Swarm Optimization Continuous Optimization The continuous optimization problem can be stated as follows: -4 -2 0 2 4 -4 -2 0 2 4 -60-40-20 0 20 40 60 80 100 Find X∗ ⊆ X ⊆ Rn such that X∗ = argminx ∈X f (x) = {x∗ ∈ X : f (x∗) ≤ f (x) ∀x ∈ X} Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The basic algorithm 1. Create a ‘population’ of agents (called particles) uniformly distributed over X. Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The basic algorithm 2. Evaluate each particle’s position according to the objective function. Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The basic algorithm 3. If a particle’s current position is better than its previous best position, update it. Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The basic algorithm 4. Determine the best particle (according to the particle’s previous best positions). Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The basic algorithm 5. Update particles’ velocities according to vt+1i = vti + ϕ1Ut1(pbti −xti ) + ϕ2Ut2(gbt −xti ). Marco A. Montes de Oca Particle Swarm Optimization Particle swarm optimization: The basic algorithm 6. Move particles to their new positions according to xt+1i = xti + vt+1i . Marco A. Montes de Oca Particle Swarm Optimization...

Website: iridia.ulb.ac.be | Filesize: -
No of Page(s): 58
Download Particle Swarm Optimization - Université Libre de Bruxelles.pdf