AI-PSO
view release on metacpan or search on metacpan
lib/AI/PSO.pm view on Meta::CPAN
#
# 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 --------
lib/AI/PSO.pm view on Meta::CPAN
# pso_optimize
# - runs the particle swarm optimization algorithm
#
sub pso_optimize() {
&init();
return &swarm();
}
#
# 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 -----------
lib/AI/PSO.pm view on Meta::CPAN
#
# 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.
lib/AI/PSO.pm view on Meta::CPAN
$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";
}
lib/AI/PSO.pm view on Meta::CPAN
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}});
&dump_particle($p);
return 0;
} else {
if($verbose == 1) {
print "N:$iter:$p:$fitness\n"
}
if($verbose == 2) {
&dump_particle($p);
}
}
}
## at this point we've updated our position, but haven't reached the end of the search
## so we turn to our neighbors for help.
## (we see if they are doing any better than we are,
## and if so, we try to fly over closer to their position)
for(my $p = 0; $p < $numParticles; $p++) {
my $n = &get_index_of_best_fit_neighbor($p);
my @meDelta = (); # array of self position updates
my @themDelta = (); # array of neighbor position updates
for(my $d = 0; $d < $dimensions; $d++) {
if($useModifiedAlgorithm) { # this if shold be moved out much further, but i'm working on code refactoring first
my $meFactor = $meWeight * &random($meMin, $meMax);
my $themFactor = $themWeight * &random($themMin, $themMax);
$meDelta[$d] = $particles[$p]{bestPos}[$d] - $particles[$p]{currPos}[$d];
$themDelta[$d] = $particles[$n]{bestPos}[$d] - $particles[$p]{currPos}[$d];
my $delta = ($meFactor * $meDelta[$d]) + ($themFactor * $themDelta[$d]);
$delta += $particles[$p]{velocity}[$d];
# do the PSO position and velocity updates
$particles[$p]{velocity}[$d] = &clamp_velocity($delta);
$particles[$p]{nextPos}[$d] = $particles[$p]{currPos}[$d] + $particles[$p]{velocity}[$d];
} else {
my $rho1 = &random(0, $psoRandomRange);
my $rho2 = $psoRandomRange - $rho1;
$meDelta[$d] = $particles[$p]{bestPos}[$d] - $particles[$p]{currPos}[$d];
$themDelta[$d] = $particles[$n]{bestPos}[$d] - $particles[$p]{currPos}[$d];
my $delta = ($rho1 * $meDelta[$d]) + ($rho2 * $themDelta[$d]);
$delta += $particles[$p]{velocity}[$d];
# do the PSO position and velocity updates
$particles[$p]{velocity}[$d] = &clamp_velocity($delta);
$particles[$p]{nextPos}[$d] = $particles[$p]{currPos}[$d] + $particles[$p]{velocity}[$d];
}
}
}
}
#
# at this point we have exceeded the maximum number of iterations, so let's at least print out the best result so far
#
print STDERR "MAX ITERATIONS REACHED WITHOUT MEETING EXIT CRITERION...printing best solution\n";
my $bestFit = -1;
my $bestPartIndex = -1;
for(my $p = 0; $p < $numParticles; $p++) {
my $endFit = &compute_fitness(@{$particles[$p]{bestPos}});
if($endFit >= $bestFit) {
$bestFit = $endFit;
$bestPartIndex = $p;
}
}
&save_solution(@{$particles[$bestPartIndex]{bestPos}});
&dump_particle($bestPartIndex);
return 1;
}
#
# save solution
# - simply copies the given array into the global solution array
#
sub save_solution(@) {
@solution = @_;
}
lib/AI/PSO.pm view on Meta::CPAN
# ...
#
sub get_index_of_neighbor($$) {
my ($particleIndex, $neighborNum) = @_;
# TODO: insert error checking code / defensive programming
return ($particleIndex + $neighborNum) % $numParticles;
}
#
# get_index_of_best_fit_neighbor
# - returns the index of the neighbor with the best fitness (when given a particle index)...
#
sub get_index_of_best_fit_neighbor($) {
my ($particleIndex) = @_;
my $bestNeighborFitness = 0;
my $bestNeighborIndex = 0;
my $particleNeighborIndex = 0;
for(my $neighbor = 0; $neighbor < $numNeighbors; $neighbor++) {
$particleNeighborIndex = &get_index_of_neighbor($particleIndex, $neighbor);
if(&compute_fitness(@{$particles[$particleNeighborIndex]{bestPos}}) > $bestNeighborFitness) {
$bestNeighborFitness = &compute_fitness(@{$particles[$particleNeighborIndex]{bestPos}});
$bestNeighborIndex = $particleNeighborIndex;
}
}
# TODO: insert error checking code / defensive programming
return $particleNeighborIndex;
}
#
# clamp_velocity
# - restricts the change in velocity to be within a certain range (prevents large jumps in problem hyperspace)
#
lib/AI/PSO.pm view on Meta::CPAN
# 2 dumps each particle (+1)
psoRandomRange => 4.0, # setting this enables the original PSO algorithm and
# also subsequently ignores the me*/them* parameters
);
sub custom_fitness_function(@input) {
# this is a callback function.
# @input will be passed to this, you do not need to worry about setting it...
# ... do something with @input which is an array of floats
# return a value in [0,1] with 0 being the worst and 1 being the best
}
pso_set_params(\%params);
pso_register_fitness_function('custom_fitness_function');
pso_optimize();
my @solutionArray = pso_get_solution_array();
E<32>
=head2 General Guidelines
lib/AI/PSO.pm view on Meta::CPAN
user wants to optimize define the dimensionality of the problem
hyperspace. So, if you want to optimize three variables, a particle
will be three dimensional and will have 3 values that devine its
position 3 values that define its velocity. The position of a
particle determines how good it is by a user-defined fitness function.
The velocity of a particle determines how quickly it changes location.
Larger velocities provide more coverage of hyperspace at the cost of
solution precision. With large velocities, a particle may come close
to a maxima but over-shoot it because it is moving too quickly. With
smaller velocities, particles can really hone in on a local solution
and find the best position but they may be missing another, possibly
even more optimal, solution because a full search of the hyperspace
was not conducted. Techniques such as simulated annealing can be
applied in certain areas so that the closer a partcle gets to a
solution, the smaller its velocity will be so that in bad areas of
the hyperspace, the particles move quickly, but in good areas, they
spend some extra time looking around.
In general, particles fly around the problem hyperspace looking for
local/global maxima. At each position, a particle computes its
fitness. If it does not meet the exit criteria then it gets
lib/AI/PSO.pm view on Meta::CPAN
=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
( run in 0.641 second using v1.01-cache-2.11-cpan-4e96b696675 )