AI-PSO
view release on metacpan or search on metacpan
0.85 Wed Nov 15 22:30:47 2006
- corrected the fitness function in the test
- added perceptron c++ code that I wrote a long time ago ;)
- added an example (pso_ann.pl) for training a simple feed-forward neural network
- updated POD
0.82 Sat Nov 11 22:20:31 2006
- fixed POD to correctly 'use AI::PSO'
- fixed fitness function in PSO.t
- added research paper to package
- moved into a subversion repository
- removed requirement for perl 5.8.8
- removed printing of solution array in test
0.80 Sat Nov 11 14:22:27 2006
- changed namespace to AI::PSO
- added a pso_get_solution_array function
0.70 Fri Nov 10 23:50:32 2006
- added user callback fitness function
# http://module-build.sourceforge.net/META-spec.html
name: AI-PSO
version: 0.86
version_from: lib/AI/PSO.pm
installdirs: site
requires:
Callback: 0
Math::Random: 0
distribution_type: module
generated_by: ExtUtils::MakeMaker version 6.30
MPL-1.1.txt view on Meta::CPAN
1.10.1. "Patent Claims" means any patent claim(s), now owned or
hereafter acquired, including without limitation, method, process,
and apparatus claims, in any patent Licensable by grantor.
1.11. "Source Code" means the preferred form of the Covered Code for
making modifications to it, including all modules it contains, plus
any associated interface definition files, scripts used to control
compilation and installation of an Executable, or source code
differential comparisons against either the Original Code or another
well known, available Covered Code of the Contributor's choice. The
Source Code can be in a compressed or archival form, provided the
appropriate decompression or de-archiving software is widely available
for no charge.
1.12. "You" (or "Your") means an individual or a legal entity
exercising rights under, and complying with all of the terms of, this
License or a future version of this License issued under Section 6.1.
For legal entities, "You" includes any entity which controls, is
controlled by, or is under common control with You. For purposes of
this definition, "control" means (a) the power, direct or indirect,
to cause the direction or management of such entity, whether by
contract or otherwise, or (b) ownership of more than fifty percent
(50%) of the outstanding shares or beneficial ownership of such
entity.
2. Source Code License.
2.1. The Initial Developer Grant.
The Initial Developer hereby grants You a world-wide, royalty-free,
non-exclusive license, subject to third party intellectual property
claims:
(a) under intellectual property rights (other than patent or
trademark) Licensable by Initial Developer to use, reproduce,
MPL-1.1.txt view on Meta::CPAN
3. Distribution Obligations.
3.1. Application of License.
The Modifications which You create or to which You contribute are
governed by the terms of this License, including without limitation
Section 2.2. The Source Code version of Covered Code may be
distributed only under the terms of this License or a future version
of this License released under Section 6.1, and You must include a
copy of this License with every copy of the Source Code You
distribute. You may not offer or impose any terms on any Source Code
version that alters or restricts the applicable version of this
License or the recipients' rights hereunder. However, You may include
an additional document offering the additional rights described in
Section 3.5.
3.2. Availability of Source Code.
Any Modification which You create or to which You contribute must be
made available in Source Code form under the terms of this License
either on the same media as an Executable version or via an accepted
Electronic Distribution Mechanism to anyone to whom you made an
Executable version available; and if made available via Electronic
Distribution Mechanism, must remain available for at least twelve (12)
months after the date it initially became available, or at least six
(6) months after a subsequent version of that particular Modification
has been made available to such recipients. You are responsible for
ensuring that the Source Code version remains available even if the
Electronic Distribution Mechanism is maintained by a third party.
3.3. Description of Modifications.
You must cause all Covered Code to which You contribute to contain a
file documenting the changes You made to create that Covered Code and
the date of any change. You must include a prominent statement that
the Modification is derived, directly or indirectly, from Original
Code provided by the Initial Developer and including the name of the
Initial Developer in (a) the Source Code, and (b) in any notice in an
MPL-1.1.txt view on Meta::CPAN
(such as notifying appropriate mailing lists or newsgroups)
reasonably calculated to inform those who received the Covered
Code that new knowledge has been obtained.
(b) Contributor APIs.
If Contributor's Modifications include an application programming
interface and Contributor has knowledge of patent licenses which
are reasonably necessary to implement that API, Contributor must
also include this information in the LEGAL file.
(c) Representations.
Contributor represents that, except as disclosed pursuant to
Section 3.4(a) above, Contributor believes that Contributor's
Modifications are Contributor's original creation(s) and/or
Contributor has sufficient rights to grant the rights conveyed by
this License.
3.5. Required Notices.
You must duplicate the notice in Exhibit A in each file of the Source
Code. If it is not possible to put such notice in a particular Source
Code file due to its structure, then You must include such notice in a
location (such as a relevant directory) where a user would be likely
MPL-1.1.txt view on Meta::CPAN
Exhibit A. You must also duplicate this License in any documentation
for the Source Code where You describe recipients' rights or ownership
rights relating to Covered Code. You may choose to offer, and to
charge a fee for, warranty, support, indemnity or liability
obligations to one or more recipients of Covered Code. However, You
may do so only on Your own behalf, and not on behalf of the Initial
Developer or any Contributor. You must make it absolutely clear than
any such warranty, support, indemnity or liability obligation is
offered by You alone, and You hereby agree to indemnify the Initial
Developer and every Contributor for any liability incurred by the
Initial Developer or such Contributor as a result of warranty,
support, indemnity or liability terms You offer.
3.6. Distribution of Executable Versions.
You may distribute Covered Code in Executable form only if the
requirements of Section 3.1-3.5 have been met for that Covered Code,
and if You include a notice stating that the Source Code version of
the Covered Code is available under the terms of this License,
including a description of how and where You have fulfilled the
obligations of Section 3.2. The notice must be conspicuously included
in any notice in an Executable version, related documentation or
MPL-1.1.txt view on Meta::CPAN
Code or ownership rights under a license of Your choice, which may
contain terms different from this License, provided that You are in
compliance with the terms of this License and that the license for the
Executable version does not attempt to limit or alter the recipient's
rights in the Source Code version from the rights set forth in this
License. If You distribute the Executable version under a different
license You must make it absolutely clear that any terms which differ
from this License are offered by You alone, not by the Initial
Developer or any Contributor. You hereby agree to indemnify the
Initial Developer and every Contributor for any liability incurred by
the Initial Developer or such Contributor as a result of any such
terms You offer.
3.7. Larger Works.
You may create a Larger Work by combining Covered Code with other code
not governed by the terms of this License and distribute the Larger
Work as a single product. In such a case, You must make sure the
requirements of this License are fulfilled for the Covered Code.
4. Inability to Comply Due to Statute or Regulation.
If it is impossible for You to comply with any of the terms of this
License with respect to some or all of the Covered Code due to
statute, judicial order, or regulation then You must: (a) comply with
the terms of this License to the maximum extent possible; and (b)
describe the limitations and the code they affect. Such description
must be included in the LEGAL file described in Section 3.4 and must
be included with all distributions of the Source Code. Except to the
extent prohibited by statute or regulation, such description must be
sufficiently detailed for a recipient of ordinary skill to be able to
understand it.
5. Application of this License.
MPL-1.1.txt view on Meta::CPAN
or a Contributor (the Initial Developer or Contributor against whom
You file such action is referred to as "Participant") alleging that:
(a) such Participant's Contributor Version directly or indirectly
infringes any patent, then any and all rights granted by such
Participant to You under Sections 2.1 and/or 2.2 of this License
shall, upon 60 days notice from Participant terminate prospectively,
unless if within 60 days after receipt of notice You either: (i)
agree in writing to pay Participant a mutually agreeable reasonable
royalty for Your past and future use of Modifications made by such
Participant, or (ii) withdraw Your litigation claim with respect to
the Contributor Version against such Participant. If within 60 days
of notice, a reasonable royalty and payment arrangement are not
mutually agreed upon in writing by the parties or the litigation claim
is not withdrawn, the rights granted by Participant to You under
Sections 2.1 and/or 2.2 automatically terminate at the expiration of
the 60 day notice period specified above.
(b) any software, hardware, or device, other than such Participant's
Contributor Version, directly or indirectly infringes any patent, then
any rights granted to You by such Participant under Sections 2.1(b)
and 2.2(b) are revoked effective as of the date You first made, used,
sold, distributed, or had made, Modifications made by that
Participant.
8.3. If You assert a patent infringement claim against Participant
alleging that such Participant's Contributor Version directly or
indirectly infringes any patent where such claim is resolved (such as
by license or settlement) prior to the initiation of patent
infringement litigation, then the reasonable value of the licenses
granted by such Participant under Sections 2.1 or 2.2 shall be taken
into account in determining the amount or value of any payment or
license.
8.4. In the event of termination under Sections 8.1 or 8.2 above,
all end user license agreements (excluding distributors and resellers)
which have been validly granted by You or any distributor hereunder
prior to termination shall survive termination.
9. LIMITATION OF LIABILITY.
UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, WHETHER TORT
(INCLUDING NEGLIGENCE), CONTRACT, OR OTHERWISE, SHALL YOU, THE INITIAL
DEVELOPER, ANY OTHER CONTRIBUTOR, OR ANY DISTRIBUTOR OF COVERED CODE,
OR ANY SUPPLIER OF ANY OF SUCH PARTIES, BE LIABLE TO ANY PERSON FOR
ANY INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES OF ANY
MPL-1.1.txt view on Meta::CPAN
The Covered Code is a "commercial item," as that term is defined in
48 C.F.R. 2.101 (Oct. 1995), consisting of "commercial computer
software" and "commercial computer software documentation," as such
terms are used in 48 C.F.R. 12.212 (Sept. 1995). Consistent with 48
C.F.R. 12.212 and 48 C.F.R. 227.7202-1 through 227.7202-4 (June 1995),
all U.S. Government End Users acquire Covered Code with only those
rights set forth herein.
11. MISCELLANEOUS.
This License represents the complete agreement concerning subject
matter hereof. If any provision of this License is held to be
unenforceable, such provision shall be reformed only to the extent
necessary to make it enforceable. This License shall be governed by
California law provisions (except to the extent applicable law, if
any, provides otherwise), excluding its conflict-of-law provisions.
With respect to disputes in which at least one party is a citizen of,
or an entity chartered or registered to do business in the United
States of America, any litigation relating to this License shall be
subject to the jurisdiction of the Federal Courts of the Northern
District of California, with venue lying in Santa Clara County,
California, with the losing party responsible for costs, including
without limitation, court costs and reasonable attorneys' fees and
expenses. The application of the United Nations Convention on
Contracts for the International Sale of Goods is expressly excluded.
Any law or regulation which provides that the language of a contract
shall be construed against the drafter shall not apply to this
License.
12. RESPONSIBILITY FOR CLAIMS.
As between Initial Developer and the Contributors, each party is
responsible for claims and damages arising, directly or indirectly,
out of its utilization of rights under this License and You agree to
work with Initial Developer and Contributors to distribute such
responsibility on an equitable basis. Nothing herein is intended or
shall be deemed to constitute any admission of liability.
13. MULTIPLE-LICENSED CODE.
Initial Developer may designate portions of the Covered Code as
"Multiple-Licensed". "Multiple-Licensed" means that the Initial
Developer permits you to utilize portions of the Covered Code under
Your choice of the NPL or the alternative licenses, if any, specified
by the Initial Developer in the file described in Exhibit A.
EXHIBIT A -Mozilla Public License.
``The contents of this file are subject to the Mozilla Public License
Version 1.1 (the "License"); you may not use this file except in
compliance with the License. You may obtain a copy of the License at
http://www.mozilla.org/MPL/
Software distributed under the License is distributed on an "AS IS"
basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
License for the specific language governing rights and limitations
under the License.
The Original Code is ______________________________________.
The Initial Developer of the Original Code is ________________________.
Portions created by ______________________ are Copyright (C) ______
_______________________. All Rights Reserved.
Contributor(s): ______________________________________.
To install this module type the following:
perl Makefile.PL
make
make test
make install
DEPENDENCIES
This module requires these other modules and libraries:
Math::Random
Callback
COPYRIGHT AND LICENCE
Copyright (C) 2006 by W. Kyle Schlansker
This Code is released under the Mozilla Public License Version 1.1.
examples/NeuralNet/NeuralNet.h view on Meta::CPAN
/// \fn ~TransferFunction()
/// \brief destructor
///
virtual ~TransferFunction()
{
}
///
/// \fn virtual double compute()
/// \brief computes the transfer function and returns result
/// \param val a double
/// \return double
///
virtual double compute(double val) = 0;
protected:
double m_value; /// value on which to compute the transfer function
};
examples/NeuralNet/NeuralNet.h view on Meta::CPAN
delete [] m_weights;
m_neurons = newNeuronArr;
m_weights = newWeightArr;
}
}
///
/// \fn double transferFunction(double val)
/// \brief applies a transfer function to val and returns the result
/// \param val a double
/// \return double
///
double transferFunc(double val)
{
return val;
}
int m_numConnections; /// number of connections to other Neurons
lib/AI/PSO.pm view on Meta::CPAN
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 #-#-#
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 -----------
#
# 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 ...
lib/AI/PSO.pm view on Meta::CPAN
# 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;
}
lib/AI/PSO.pm view on Meta::CPAN
$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)
#
sub clamp_velocity($) {
my ($dx) = @_;
if($dx < $deltaMin) {
$dx = $deltaMin;
} elsif($dx > $deltaMax) {
$dx = $deltaMax;
}
return $dx;
}
lib/AI/PSO.pm view on Meta::CPAN
=head1 NAME
AI::PSO - Module for running the Particle Swarm Optimization algorithm
=head1 SYNOPSIS
use AI::PSO;
my %params = (
numParticles => 4, # total number of particles involved in search
numNeighbors => 3, # number of particles with which each particle will share its progress
maxIterations => 1000, # maximum number of iterations before exiting with no solution found
dimensions => 4, # number of parameters you want to optimize
deltaMin => -4.0, # minimum change in velocity during PSO update
deltaMax => 4.0, # maximum change in velocity during PSO update
meWeight => 2.0, # 'individuality' weighting constant (higher means more individuality)
meMin => 0.0, # 'individuality' minimum random weight
meMax => 1.0, # 'individuality' maximum random weight
themWeight => 2.0, # 'social' weighting constant (higher means trust group more)
themMin => 0.0, # 'social' minimum random weight
themMax => 1.0, # 'social' maximum random weight
exitFitness => 0.9, # minimum fitness to achieve before exiting
verbose => 0, # 0 prints solution
# 1 prints (Y|N):particle:fitness at each iteration
# 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
}
lib/AI/PSO.pm view on Meta::CPAN
Particle Swarm Optimization is an optimization algorithm designed by
Russell Eberhart and James Kennedy from Purdue University. The
algorithm itself is based off of the emergent behavior among societal
groups ranging from marching of ants, to flocking of birds, to
swarming of bees.
PSO is a cooperative approach to optimization rather than an
evolutionary approach which kills off unsuccessful members of the
search team. In the swarm framework each particle, is a relatively
unintelligent search agent. It is in the collective sharing of
knowledge that solutions are found. Each particle simply shares its
information with its neighboring particles. So, if one particle is
not doing to well (has a low fitness), then it looks to its neighbors
for help and tries to be more like them while still maintaining a
sense of individuality.
A particle is defined by its position and velocity. The parameters a
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
lib/AI/PSO.pm view on Meta::CPAN
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.
lib/AI/PSO.pm view on Meta::CPAN
=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()
# simple test function to sum the position values up to 3.5
my $testValue = 3.5;
sub test_fitness_function(@) {
my (@arr) = (@_);
my $sum = 0;
my $ret = 0;
foreach my $val (@arr) {
$sum += $val;
}
# sigmoid-like ==> squash the result to [0,1] and get as close to 3.5 as we can
return 2 / (1 + exp(abs($testValue - $sum)));
return $ret;
}
ok( pso_set_params(\%test_params) == 0 );
ok( pso_register_fitness_function('test_fitness_function') == 0 );
ok( pso_optimize() == 0 );
my @solution = pso_get_solution_array();
( run in 1.339 second using v1.01-cache-2.11-cpan-49f99fa48dc )