AI-PSO
view release on metacpan or search on metacpan
lib/AI/PSO.pm view on Meta::CPAN
package AI::PSO;
use strict;
use warnings;
use Math::Random;
use Callback;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT = qw(
pso_set_params
pso_register_fitness_function
pso_optimize
pso_get_solution_array
);
our $VERSION = '0.86';
######################## BEGIN MODULE CODE #################################
#---------- BEGIN GLOBAL PARAMETERS ------------
#-#-# search parameters #-#-#
my $numParticles = 'null'; # This is the number of particles that actually search the problem hyperspace
my $numNeighbors = 'null'; # This is the number of neighboring particles that each particle shares information with
# which must obviously be less than the number of particles and greater than 0.
# TODO: write code to preconstruct different topologies. Such as fully connected, ring, star etc.
# Currently, neighbors are chosen by a simple hash function.
# It would be fun (no theoretical benefit that I know of) to play with different topologies.
my $maxIterations = 'null'; # This is the maximum number of optimization iterations before exiting if the fitness goal is never reached.
my $exitFitness = 'null'; # this is the exit criteria. It must be a value between 0 and 1.
my $dimensions = 'null'; # this is the number of variables the user is optimizing
#-#-# pso position parameters #-#-#
my $deltaMin = 'null'; # This is the minimum scalar position change value when searching
my $deltaMax = 'null'; # This is the maximum scalar position change value when searching
#-#-# my 'how much do I trust myself verses my neighbors' parameters #-#-#
my $meWeight = 'null'; # 'individuality' weighting constant (higher weight (than group) means trust individual more, neighbors less)
my $meMin = 'null'; # 'individuality' minimum random weight (this should really be between 0, 1)
my $meMax = 'null'; # 'individuality' maximum random weight (this should really be between 0, 1)
my $themWeight = 'null'; # 'social' weighting constant (higher weight (than individual) means trust group more, self less)
my $themMin = 'null'; # 'social' minimum random weight (this should really be between 0, 1)
my $themMax = 'null'; # 'social' maximum random weight (this should really be between 0, 1)
my $psoRandomRange = 'null'; # PSO::.86 new variable to support original unmodified algorithm
my $useModifiedAlgorithm = 'null';
#-#-# user/debug parameters #-#-#
my $verbose = 0; # This one defaults for obvious reasons...
#NOTE: $meWeight and $themWeight should really add up to a constant value.
# Swarm Intelligence defines a 'pso random range' constant and then computes two random numbers
# within this range by first getting a random number and then subtracting it from the range.
# e.g.
# $randomRange = 4.0
# $meWeight = random(0, $randomRange);
# $themWeight = $randomRange - $meWeight.
#
#
#---------- END GLOBAL PARAMETERS ------------
#---------- BEGIN GLOBAL DATA STRUCTURES --------
#
# a particle is a hash of arrays of positions and velocities:
#
# The position of a particle in the problem hyperspace is defined by the values in the position array...
# You can think of each array value as being a dimension,
# so in N-dimensional hyperspace, the size of the position vector is N
#
# A particle updates its position according the Euler integration equation for physical motion:
# Xi(t) = Xi(t-1) + Vi(t)
# The velocity portion of this contains the stochastic elements of PSO and is defined as:
# Vi(t) = Vi(t-1) + P1*[pi - Xi(t-1)] + P2*[pg - Xi(t-1)]
# where P1 and P2 add are two random values who's sum adds up to the PSO random range (4.0)
# and pi is the individual's best location
# and pg is the global (or neighborhoods) best position
#
# The velocity vector is obviously updated before the position vector...
#
#
my @particles = ();
my $user_fitness_function;
my @solution = ();
#---------- END GLOBAL DATA STRUCTURES --------
#---------- BEGIN EXPORTED SUBROUTINES ----------
#
# pso_set_params
# - sets the global module parameters from the hash passed in
#
sub pso_set_params(%) {
my (%params) = %{$_[0]};
my $retval = 0;
#no strict 'refs';
#foreach my $key (keys(%params)) {
# $$key = $params{$key};
#}
#use strict 'refs';
$numParticles = defined($params{numParticles}) ? $params{numParticles} : 'null';
$numNeighbors = defined($params{numNeighbors}) ? $params{numNeighbors} : 'null';
$maxIterations = defined($params{maxIterations}) ? $params{maxIterations} : 'null';
$dimensions = defined($params{dimensions}) ? $params{dimensions} : 'null';
$exitFitness = defined($params{exitFitness}) ? $params{exitFitness} : 'null';
$deltaMin = defined($params{deltaMin}) ? $params{deltaMin} : 'null';
lib/AI/PSO.pm view on Meta::CPAN
}
#
# pso_get_solution_array
# - returns the array of parameters corresponding to the best solution so far
sub pso_get_solution_array() {
return @solution;
}
#---------- END EXPORTED SUBROUTINES ----------
#--------- BEGIN INTERNAL SUBROUTINES -----------
#
# init
# - initializes global variables
# - initializes particle data structures
#
sub init() {
if($psoRandomRange =~ m/null/) {
$useModifiedAlgorithm = 1;
} else {
$useModifiedAlgorithm = 0;
}
&initialize_particles();
}
#
# initialize_particles
# - sets up internal data structures
# - initializes particle positions and velocities with an element of randomness
#
sub initialize_particles() {
for(my $p = 0; $p < $numParticles; $p++) {
$particles[$p] = {}; # each particle is a hash of arrays with the array sizes being the dimensionality of the problem space
$particles[$p]{nextPos} = []; # nextPos is the array of positions to move to on the next positional update
$particles[$p]{bestPos} = []; # bestPos is the position of that has yielded the best fitness for this particle (it gets updated when a better fitness is found)
$particles[$p]{currPos} = []; # currPos is the current position of this particle in the problem space
$particles[$p]{velocity} = []; # velocity ... come on ...
for(my $d = 0; $d < $dimensions; $d++) {
$particles[$p]{nextPos}[$d] = &random($deltaMin, $deltaMax);
$particles[$p]{currPos}[$d] = &random($deltaMin, $deltaMax);
$particles[$p]{bestPos}[$d] = &random($deltaMin, $deltaMax);
$particles[$p]{velocity}[$d] = &random($deltaMin, $deltaMax);
}
}
}
#
# initialize_neighbors
# NOTE: I made this a separate subroutine so that different topologies of neighbors can be created and used instead of this.
# NOTE: This subroutine is currently not used because we access neighbors by index to the particle array rather than storing their references
#
# - adds a neighbor array to the particle hash data structure
# - sets the neighbor based on the default neighbor hash function
#
sub initialize_neighbors() {
for(my $p = 0; $p < $numParticles; $p++) {
for(my $n = 0; $n < $numNeighbors; $n++) {
$particles[$p]{neighbor}[$n] = $particles[&get_index_of_neighbor($p, $n)];
}
}
}
sub dump_particle($) {
$| = 1;
my ($index) = @_;
print STDERR "[particle $index]\n";
print STDERR "\t[bestPos] ==> " . &compute_fitness(@{$particles[$index]{bestPos}}) . "\n";
foreach my $pos (@{$particles[$index]{bestPos}}) {
print STDERR "\t\t$pos\n";
}
print STDERR "\t[currPos] ==> " . &compute_fitness(@{$particles[$index]{currPos}}) . "\n";
foreach my $pos (@{$particles[$index]{currPos}}) {
print STDERR "\t\t$pos\n";
}
print STDERR "\t[nextPos] ==> " . &compute_fitness(@{$particles[$index]{nextPos}}) . "\n";
foreach my $pos (@{$particles[$index]{nextPos}}) {
print STDERR "\t\t$pos\n";
}
print STDERR "\t[velocity]\n";
foreach my $pos (@{$particles[$index]{velocity}}) {
print STDERR "\t\t$pos\n";
}
}
#
# swarm
# - runs the particle swarm algorithm
#
sub swarm() {
for(my $iter = 0; $iter < $maxIterations; $iter++) {
for(my $p = 0; $p < $numParticles; $p++) {
## update position
for(my $d = 0; $d < $dimensions; $d++) {
$particles[$p]{currPos}[$d] = $particles[$p]{nextPos}[$d];
}
## test _current_ fitness of position
my $fitness = &compute_fitness(@{$particles[$p]{currPos}});
# if this position in hyperspace is the best so far...
if($fitness > &compute_fitness(@{$particles[$p]{bestPos}})) {
# for each dimension, set the best position as the current position
for(my $d2 = 0; $d2 < $dimensions; $d2++) {
$particles[$p]{bestPos}[$d2] = $particles[$p]{currPos}[$d2];
}
}
## check for exit criteria
if($fitness >= $exitFitness) {
#...write solution
print "Y:$iter:$p:$fitness\n";
&save_solution(@{$particles[$p]{bestPos}});
lib/AI/PSO.pm view on Meta::CPAN
mentioned, the velocity controls how quickly a particle changes
location in the problem hyperspace. There are also some stochastic
weights involved in the positional updates so that each particle is
truly independent and can take its own search path while still
incorporating good information from other particles. In this
particluar perl module, the user is able to choose from two
implementations of the algorithm. One is the original implementation
from I<Swarm Intelligence> which requires the definition of a
'random range' to which the two stochastic weights are required to
sum. The other implementation allows the user to define the weighting
of how much a particle follows its own path versus following its
peers. In both cases there is an element of randomness.
Solution convergence is quite fast once one particle becomes close to
a local maxima. Having more particles active means there is more of
a chance that you will not be stuck in a local maxima. Often times
different neighborhoods (when not configured in a global neighborhood
fashion) will converge to different maxima. It is quite interesting
to watch graphically. If the fitness function is expensive to
compute, then it is often useful to start out with a small number of
particles first and get a feel for how the algorithm converges.
The algorithm implemented in this module is taken from the book
I<Swarm Intelligence> by Russell Eberhart and James Kennedy.
I highly suggest you read the book if you are interested in this
sort of thing.
=head1 EXPORTED FUNCTIONS
=over 4
=item pso_set_params()
Sets the particle swarm configuration parameters to use for the search.
=item pso_register_fitness_function()
Sets the user defined fitness function to call. The fitness function
should return a value between 0 and 1. Users may want to look into
the sigmoid function [1 / (1+e^(-x))] and it's variants to implement
this. Also, you may want to take a look at either t/PSO.t for the
simple test or examples/NeuralNetwork/pso_ann.pl for an example on
how to train a simple 3-layer feed forward neural network. (Note
that a real training application would have a real dataset with many
input-output pairs...pso_ann.pl is a _very_ simple example. Also note
that the neural network exmaple requires g++. Type 'make run' in the
examples/NeuralNetwork directory to run the example. Lastly, the
neural network c++ code is in a very different coding style. I did
indeed write this, but it was many years ago when I was striving to
make my code nicely formatted and good looking :)).
=item pso_optimize()
Runs the particle swarm optimization algorithm. This consists of
running iterations of search and many calls to the fitness function
you registered with pso_register_fitness_function()
=item pso_get_solution_array()
By default, pso_optimize() will print out to STDERR the first
solution, or the best solution so far if the max iterations were
reached. This function will simply return an array of the winning
(or best so far) position of the entire swarm system. It is an
array of floats to be used how you wish (like weights in a
neural network!).
=back
=head1 EXAMPLES
=over 4
=item examples/NeuralNet/pso_ann.pl
=item t/PSO.t
=back
=head1 SEE ALSO
1. I<Swarm intelligence> by James Kennedy and Russell C. Eberhart.
ISBN 1-55860-595-9
2. A Hybrid Particle Swarm and Neural Network Approach for Reactive Power Control
AI-PSO-0.86/extradocs/ReactivePower-PSO-wks.pdf
L<http://webapps.calvin.edu/~pribeiro/courses/engr302/Samples/ReactivePower-PSO-wks.pdf>
=head1 AUTHOR
W. Kyle Schlansker
kylesch@gmail.com
=head1 COPYRIGHT AND LICENSE
Copyright (C) 2006 by W. Kyle Schlansker
This code is released under the Mozilla Public License Version 1.1.
A copy of this license may be found along with this module or at:
L<http://www.mozilla.org/MPL/MPL-1.1.txt>
=cut
( run in 0.350 second using v1.01-cache-2.11-cpan-39bf76dae61 )