Particle Swarm optimization. More...

#include <pso.h>

Inheritance diagram for pagmo::algorithm::pso:

Public Member Functions
	pso (int gen=1, double omega=0.7298, double eta1=2.05, double eta2=2.05, double vcoeff=0.5, int variant=5, int neighb_type=2, int neighb_param=4)
	Constructor. More...

base_ptr	clone () const
	Clone method.

void	evolve (population &) const
	Evolve implementation. More...

decision_vector	particle__get_best_neighbor (population::size_type pidx, std::vector< std::vector< int > > &neighb, const std::vector< decision_vector > &lbX, const std::vector< fitness_vector > &lbfit, const problem::base &prob) const
	Get information on the best position already visited by any of a particle's neighbours. More...

void	initialize_topology__gbest (const population &pop, decision_vector &gbX, fitness_vector &gbfit, std::vector< std::vector< int > > &neighb) const
	Defines the Swarm topology as a fully connected graph, where particles are influenced by all other particles in the swarm. More...

void	initialize_topology__lbest (std::vector< std::vector< int > > &neighb) const
	Defines the Swarm topology as a ring, where particles are influenced by their immediate neighbors to either side. More...

void	initialize_topology__von (std::vector< std::vector< int > > &neighb) const
	Arranges particles in a lattice, where each interacts with its immediate 4 neighbors to the N, S, E and W. More...

void	initialize_topology__adaptive_random (std::vector< std::vector< int > > &neighb) const
	Arranges particles in a random graph having a parameterized maximum outdegree; the graph changes adaptively over time. More...

std::string	get_name () const
	Algorithm name.

Public Member Functions inherited from pagmo::algorithm::base
	base ()
	Default constructor. More...

virtual	~base ()
	Trivial destructor. More...

std::string	human_readable () const
	Return human readable representation of the algorithm. More...

void	set_screen_output (const bool p)
	Setter-Getter for protected m_screen_output data. More...

bool	get_screen_output () const
	Gets screen output. More...

void	reset_rngs (const unsigned int) const
	Resets the seed of the internal rngs using a user-provided seed. More...

Protected Member Functions
std::string	human_readable_extra () const
	Extra human readable algorithm info. More...

Friends
class	boost::serialization::access

Additional Inherited Members
Protected Attributes inherited from pagmo::algorithm::base
bool	m_screen_output
	Indicates to the derived class whether to print stuff on screen.

rng_double	m_drng
	Random number generator for double-precision floating point values.

rng_uint32	m_urng
	Random number generator for unsigned integer values.

unsigned int	m_fevals
	A counter for the number of function evaluations.

Detailed Description

Particle Swarm optimization.

Particle swarm optimization (PSO) is a population based algorithm that has been proposed in the mid nineties and that is inspired by the foraging behaviour of swarms. In PSO each point has memory of the position where it achieved the best performance $\mathbf x^l_i$ and of the swarm 'champion' position $\mathbf x^g$ and uses this information to update its position using the equation:

$\mathbf v_{i+1} = \omega \mathbf v_i + \eta_1 \mathbf r_1 \cdot \left( \mathbf x_i - \mathbf x^l_i \right) + \eta_2 \mathbf r_2 \cdot \left( \mathbf x_i - \mathbf x^g \right)$

$\mathbf x_{i+1} = \mathbf x_i + \mathbf v_i$

The user can specify the values for $\omega, \eta_1, \eta_2$ and the magnitude of the maximum velocity allowed. this last value is evaluated for each search direction as the product of $ vcoeff$ and the search space width along that direction. The user can also specify one of four variants:

the velocity update rule differing on the definition of the random vectors $r_1$ and $r_2$

Variant 1: $\mathbf r_1 = [r_{11}, r_{12}, ..., r_{1n}]$ , $\mathbf r_2 = [r_{21}, r_{21}, ..., r_{2n}]$
Variant 2: $\mathbf r_1 = [r_{11}, r_{12}, ..., r_{1n}]$ , $\mathbf r_2 = [r_{11}, r_{11}, ..., r_{1n}]$
Variant 3: $\mathbf r_1 = [r_1, r_1, ..., r_1]$ , $\mathbf r_2 = [r_2, r_2, ..., r_2]$
Variant 4: $\mathbf r_1 = [r_1, r_1, ..., r_1]$ , $\mathbf r_2 = [r_1, r_1, ..., r_1]$

Variant 5: $\mathbf r_1 = [r_1, r_1, ..., r_1]$ , $\mathbf r_2 = [r_1, r_1, ..., r_1]$

At each call of the evolve method a number of function evaluations equal to m_gen * pop.size() is performed.

The algorithm is suitable for box-constrained single-objective continuous optimization.

See also: http://www.particleswarm.info/ for a repository of information related to PSO; http://dx.doi.org/10.1007/s11721-007-0002-0 for a recent survey; http://www.engr.iupui.edu/~shi/Coference/psopap4.html for the first paper on this algorithm

Author: Dario Izzo (dario.nosp@m..izz.nosp@m.o@goo.nosp@m.glem.nosp@m.ail.c.nosp@m.om); Luis Simoes (luis..nosp@m.f.m..nosp@m.simoe.nosp@m.s@gm.nosp@m.ail.c.nosp@m.om)

Definition at line 75 of file pso.h.

Constructor & Destructor Documentation

pagmo::algorithm::pso::pso	(	int	gen = `1`,
		double	omega = `0.7298`,
		double	eta1 = `2.05`,
		double	eta2 = `2.05`,
		double	vcoeff = `0.5`,
		int	variant = `5`,
		int	neighb_type = `2`,
		int	neighb_param = `4`
	)

Constructor.

Allows to specify in detail all the parameters of the algorithm.

Parameters

[in]	gen	number of generations
[in]	omega	particles' inertia weight, or alternatively, the constriction coefficient (usage depends on the variant used)
[in]	eta1	magnitude of the force, applied to the particle's velocity, in the direction of its previous best position
[in]	eta2	magnitude of the force, applied to the particle's velocity, in the direction of the best position in its neighborhood
[in]	vcoeff	velocity coefficient (determining the maximum allowed particle velocity)
[in]	variant	algorithm variant to use
[in]	neighb_type	swarm topology to use
[in]	neighb_param	if the lbest topology is selected (neighb_type=2), it represents each particle's indegree (also outdegree) in the swarm topology. Particles have neighbours up to a radius of k = neighb_param / 2 in the ring. If the Randomly-varying neighbourhood topology is selected (neighb_type=4), neighb_param represents each particle's maximum outdegree in the swarm topology. The minimum outdegree is 1 (the particle always connects back to itself).

Exceptions

value_error if m_omega is not in the [0,1] interval, eta1, eta2 are not in the [0,1] interval, vcoeff is not in ]0,1], variant is not one of 1 .. 6, neighb_type is not one of 1 .. 4

Definition at line 54 of file pso.cpp.

Member Function Documentation

void pagmo::algorithm::pso::evolve ( population & pop ) const

virtual

Evolve implementation.

Run the PSO algorithm for the number of generations specified in the constructors.

Parameters

[in,out] pop input/output pagmo::population to be evolved.

Implements pagmo::algorithm::base.

Definition at line 100 of file pso.cpp.

std::string pagmo::algorithm::pso::human_readable_extra ( ) const

protectedvirtual

Extra human readable algorithm info.

Will return a formatted string displaying the parameters of the algorithm.

Reimplemented from pagmo::algorithm::base.

Definition at line 580 of file pso.cpp.

void pagmo::algorithm::pso::initialize_topology__adaptive_random ( std::vector< std::vector< int > > & neighb ) const

Arranges particles in a random graph having a parameterized maximum outdegree; the graph changes adaptively over time.

''At the very beginning, and after each unsuccessful iteration (no improvement of the best known fitness value), the graph of the information links is modified: each particle informs at random K particles (the same particle may be chosen several times), and informs itself. The parameter K is usually set to 3. It means that each particle informs at less one particle (itself), and at most K+1 particles (including itself). It also means that each particle can be informed by any number of particles between 1 and S. However, the distribution of the possible number of "informants" is not uniform. On average, a particle is often informed by about K others, but it may be informed by a much larger number of particles with a small probability''
[Maurice Clerc, 2011] Standard Particle Swarm Optimisation, From 2006 to 2011
http://clerc.maurice.free.fr/pso/SPSO_descriptions.pdf

neighb_param represents each particle's maximum outdegree in the swarm topology. The minimum outdegree is 1 (the particle always connects back to itself).

Parameters

[out] neighb definition of the swarm's topology

Definition at line 542 of file pso.cpp.

void pagmo::algorithm::pso::initialize_topology__gbest	(	const population &	pop,
		decision_vector &	gbX,
		fitness_vector &	gbfit,
		std::vector< std::vector< int > > &	neighb
	)		const

Defines the Swarm topology as a fully connected graph, where particles are influenced by all other particles in the swarm.

''The earliest reported particle swarm version [3], [4] used a kind of topology that is known as gbest. The source of social influence on each particle was the best performing individual in the entire population. This is equivalent to a sociogram or social network where every individual is connected to every other one.''
''The gbest topology (i.e., the biggest neighborhood possible) has often been shown to converge on optima more quickly than lbest, but gbest is also more susceptible to the attraction of local optima since the population rushes unanimously toward the first good solution found.''
[Kennedy and Mendes, 2006] http://dx.doi.org/10.1109/TSMCC.2006.875410

Parameters

[in]	pop	pagmo::population being evolved
[out]	gbX	best search space position already visited by the swarm
[out]	gbfit	best fitness value in the swarm
[out]	neighb	definition of the swarm's topology

Definition at line 413 of file pso.cpp.

void pagmo::algorithm::pso::initialize_topology__lbest ( std::vector< std::vector< int > > & neighb ) const

Defines the Swarm topology as a ring, where particles are influenced by their immediate neighbors to either side.

''The L-best-k topology consists of n nodes arranged in a ring, in which node i is connected to each node in {(i+j) mod n : j = +-1,+-2, . . . ,+-k}.''
[Mohais et al., 2005] http://dx.doi.org/10.1007/11589990_80

neighb_param represents each particle's indegree (also outdegree) in the swarm topology. Particles have neighbours up to a radius of k = neighb_param / 2 in the ring.

Parameters

[out] neighb definition of the swarm's topology

Definition at line 446 of file pso.cpp.

void pagmo::algorithm::pso::initialize_topology__von ( std::vector< std::vector< int > > & neighb ) const

Arranges particles in a lattice, where each interacts with its immediate 4 neighbors to the N, S, E and W.

''The population is arranged in a rectangular matrix, for instance, 5 x 4 in a population of 20 individuals, and each individual is connected to the individuals above, below and on both of its sides, wrapping the edges''
[Kennedy and Mendes, 2006] http://dx.doi.org/10.1109/TSMCC.2006.875410

''Given a population of size n, the von Neumann neighborhood was configured into r rows and c columns, where r is the smallest integer less than or equal to sqrt(n) that evenly divides n and c = n / r''
[Mohais et al., 2005] http://dx.doi.org/10.1007/11589990_80
(there's an error in the description above: "smallest integer" should instead be "highest integer")

Parameters

[out] neighb definition of the swarm's topology

Definition at line 493 of file pso.cpp.

decision_vector pagmo::algorithm::pso::particle__get_best_neighbor	(	population::size_type	pidx,
		std::vector< std::vector< int > > &	neighb,
		const std::vector< decision_vector > &	lbX,
		const std::vector< fitness_vector > &	lbfit,
		const problem::base &	prob
	)		const

Get information on the best position already visited by any of a particle's neighbours.

Parameters

[in]	pidx	index to the particle under consideration
[in]	neighb	definition of the swarm's topology
[in]	lbX	particles' previous best positions
[in]	lbfit	particles' fitness values at their previous best positions
[in]	prob	problem undergoing optimization

Returns: best position already visited by any of the considered particle's neighbours

Definition at line 371 of file pso.cpp.

The documentation for this class was generated from the following files:

Public Member Functions

Protected Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation