#ifndef _PSO_H_
#define _PSO_H_
/*******************************************************************************
* The following code is an implementation of PSO as described in Essentials of
* Metaheuristics, Sean Luke, 2009, http://cs.gmu.edu/~sean/book/metaheuristics/
* Please reference the book for a more in depth discussion of the algorithm
******************************************************************************/
/*******************************************************************************
* If you want to use a different random number generator, you can substitute it
* here for drand48. Code expects this to be a function that takes no parameters
* and returns a number in [0,1] inclusive.
******************************************************************************/
#ifndef RNDM
#define RNDM drand48
#endif
/*******************************************************************************
* The swarm struct
* This needs to get passed into every function. Typical usage is to make a
* local statically allocated swarm struct, pass it into init_swarm(...) with
* appropriate parameters (explained in a minute), then pass the struct into
* randomize (or do your own particle initialization), then pass it to run(...),
* or run_one_step(...) (managing the loop yourself). Then, once done with the
* struct, pass it to free_swarm(...) to clean up all the dynamic memory. Of
* course, all the steps of a single iteration are further broken out into
* functions if you want to alter some of the internals.
*
* Data members
* num_particles - the number of particles in the population
* dimensions - the dimensionality of the problem (size of a particle)
* neighborhood - Number of ``informers'' used to determin neighborhood best
* particles - big 2D double array of particles. First index goes from 0 to
* num_particles. Second index is from 0 to dimensions.
* velocities - big 2D double array of velocities for the particles. Indecies
* are the same as for particles
* personal_bests - big 2D double array of the personal best for the particles.
* indecies are the same as for particles
* global_best - The best particle we've seen so far. Index from 0 to
* dimensions
*
* Swarm parameters
* alpha, beta, gamma, delta and epsilon are the swarm parameters, dictating how
* members of the swarm update their velocities. They are:
* alpha - Prior Speed (Momentum): Proportion of the prior velocity
* beta - Personal Best (Memory): Proportion of the personal best
* gamma - Neighborhood Best (Social): Proportion of the neighborhood
* best
* delta - Global Best (Cognitive): Proportion of the global best.
* epsilon - Scaling Factor: How much to scale the velocity vector by
* when updating the particles position
* How the first 4 parameters are used and combined is explained in the comments
* for the update_velocities(...) function further down.
*
* evaluate(...)
* The evaluate function pointer is used whenever the fitness of a particle
* needs to be determined. This happens in update_bests(...),
* neighborhood_best(...) (which is called in update_velocities(...)), and
* run(...). Note that the swarm does not keep around fitnesses (so you could
* potentially have a dynamic fitness function), which also means you need to
* make your evaluation function as optimized as possible.
******************************************************************************/
struct swarm{
unsigned int num_particles;
unsigned int dimensions;
unsigned int neighborhood;
double **particles;
double **velocities;
double **personal_bests;
double *global_best;
double alpha, beta, gamma, delta, epsilon;
double (*evaluate)(const double *particle, const unsigned int dim);
};
/*******************************************************************************
* This function sets all of the parameters in the swarm struct, allocates
* memory for the particles, velocities, personal bests, and the global best.
* THIS FUNCTION DOES NOT ALLOCATE A NEW SWARM STRUCT
* You must handle the creation/allocation/deallocation of the struct yourself.
* This function also does not check to see if any part of the arrays have
* been allocated already, it just re-assigns the pointers, so DON'T call this
* function unless you've called free_swarm(...), or unless this is a new struct
* that has never been passed to init_swarm(...) before.
******************************************************************************/
void init_swarm(const unsigned int particles,
const unsigned int dimension,
const unsigned int neighborhood,
const double alpha,
const double beta,
const double gamma,
const double delta,
const double epsilon,
double (*evaluate)(const double *particle, const unsigned int dim),
struct swarm *s);
/*******************************************************************************
* This function deallocates all memory allocated by init_swarm(...) and sets
* the structs pointers to NULL. This does NOT deallocate the swarm struct. You
* must handle the creation/allocation/deallocation of the struct yourself. This
* function also does not check to see if the arrays are still allocated, so
* ONLY call this on a struct that has been passed to init_swarm(...).
******************************************************************************/
void free_swarm(struct swarm *s);
/*******************************************************************************
* This function randomizes the components of all particles and their velocities
* The components are set between the min and max range given.
******************************************************************************/
void randomize(const double min, const double max, struct swarm *s);
/*******************************************************************************
* This function iterates over all of the particles, evaluates them, and updates
* the personal bests, and global best. If the parameter first is zero, it is
* assumed that the global best has not been evaluated yet
******************************************************************************/
void update_bests(const char first, struct swarm *s);
/*******************************************************************************
* This function picks ``neighborhood'' particles from the swarm randomly and
* returns a pointer to the one with the best fitness. This pointer is a direct
* pointer inside the double array, do not modify it.
******************************************************************************/
const double* neighborhood_best(const unsigned int particle, struct swarm *s);
/*******************************************************************************
* This function iterates over all the velocities, and updates them using a
* linear combination of the current velocity, personal best, neighborhood best,
* and global best. The weights are alpha, beta, gamma and delta. See
* ``Essentials of Metaheuristics'' for more details
******************************************************************************/
void update_velocities(struct swarm *s);
/*******************************************************************************
* This function iterates over all the particles, adding in the velocity scaled
* by epsilon
******************************************************************************/
void update_particles(struct swarm *s);
/*******************************************************************************
* This function runs through one step of the PSO algorithm. Specifically, it
* calls update_bests(...), update_velocities(...), update_particles(...) in
* that order, passing in ``first'' to update_bests(...). Use this function if
* you want greater control over statistics, stopping criteria, or if you want
* to do something in between iterations.
******************************************************************************/
void run_one_step(const char first, struct swarm *s);
/*******************************************************************************
* This function handles the main loop of the PSO algorithm. You can specify
* three different stopping criteria, a maximum number of iterations, an ideal
* fitness value (stops after global_bests fitness meets/exceeds this value), or
* convergence (stops once the average distance of the particles to the global
* best is less than the provided value). If use_* is non-zero, that condition
* will be checked. If all use_* parameters are 0, this will loop forever.
* Prints out which check stoped the loop, and the best particle of each
* iteration.
******************************************************************************/
void run(const char use_iterations, const unsigned int num_iterations,
const char use_ideal, const double ideal_fitness,
const char use_convergence, const double distance_epsilon,
struct swarm *s);
#endif