view release on metacpan or  search on metacpan

lib/AI/PSO.pm  view on Meta::CPAN

            $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}});
                &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];
				}
            }

lib/AI/PSO.pm  view on Meta::CPAN

  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 
  information from neighboring particles about how well they are doing.  
  If a neighboring particle is doing better, then the current particle 
  tries to move closer to its neighbor by adjusting its position.  As 
  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