AI-ParticleSwarmOptimization

 view release on metacpan or  search on metacpan

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

        posMax
        posMin
        randSeed
        randStartVelocity
        stallSpeed
        themWeight
        verbose
        /;

    die "-dimensions must be greater than 0\n"
        if exists $params{-dimensions} && $params{-dimensions} <= 0;

    if (defined $self->{verbose} and 'ARRAY' eq ref $self->{verbose}) {
        my @log = map {lc} @{$self->{verbose}};
        my %logTypes = (
            better => kLogBetter,
            stall  => kLogStall,
            iter   => kLogIter,
            detail => kLogDetail,
        );

        $self->{verbose} = 0;
        exists $logTypes{$_} and $self->{verbose} |= $logTypes{$_} for @log;
    }

    $self->{numParticles} ||= $self->{dimensions} * 10
        if defined $self->{dimensions};
    $self->{numNeighbors} ||= int sqrt $self->{numParticles}
        if defined $self->{numParticles};
    $self->{iterations}        ||= 1000;
    $self->{exitPlateauDP}     ||= 10;
    $self->{exitPlateauWindow} ||= $self->{iterations} * 0.1;
    $self->{exitPlateauBurnin} ||= $self->{iterations} * 0.5;
    $self->{posMax} = 100 unless defined $self->{posMax};
    $self->{posMin} = -$self->{posMax} unless defined $self->{posMin};
    $self->{meWeight}   ||= 0.5;
    $self->{themWeight} ||= 0.5;
    $self->{inertia}    ||= 0.9;
    $self->{verbose}    ||= 0;

    return 1;
}


sub init {
    my ($self) = @_;

    die "-fitFunc must be set before init or optimize is called"
        unless $self->{fitFunc} and 'CODE' eq ref $self->{fitFunc};
    die
        "-dimensions must be set to 1 or greater before init or optimize is called"
        unless $self->{dimensions} and $self->{dimensions} >= 1;

    my $seed =
        int (exists $self->{randSeed} ? $self->{randSeed} : rand (0xffffffff));

    $self->{rndGen} = Math::Random::MT->new ($seed);
    $self->{usedRandSeed} = $seed;

    $self->{prtcls}         = [];
    $self->{bestBest}       = undef;
    $self->{bestBestByIter} = undef;
    $self->{bestsMean}      = 0;
    $self->_initParticles ();
    $self->{iterCount} = 0;

    # Normalise weights.
    my $totalWeight =
        $self->{inertia} + $self->{themWeight} + $self->{meWeight};

    $self->{inertia}    /= $totalWeight;
    $self->{meWeight}   /= $totalWeight;
    $self->{themWeight} /= $totalWeight;

    die "-posMax must be greater than -posMin"
        unless $self->{posMax} > $self->{posMin};
    $self->{$_} > 0 or die "-$_ must be greater then 0" for qw/numParticles/;

    $self->{deltaMax} = ($self->{posMax} - $self->{posMin}) / 100.0;

    return 1;
}


sub optimize {
    my ($self, $iterations) = @_;

    $iterations ||= $self->{iterations};
    $self->init () unless $self->{prtcls};
    return $self->_swarm ($iterations);
}


sub getBestParticles {
    my ($self, $num) = @_;
    my @bests  = 0 .. $self->{numParticles} - 1;
    my $prtcls = $self->{prtcls};

    @bests = sort {$prtcls->[$a]{bestFit} <=> $prtcls->[$b]{bestFit}} @bests;
    $num ||= 1;
    return @bests[0 .. $num - 1];
}


sub getParticleBestPos {
    my ($self, $prtcl) = @_;

    return undef if $prtcl >= $self->{numParticles};
    $prtcl = $self->{prtcls}[$prtcl];

    return ($prtcl->{bestFit}, @{$prtcl->{bestPos}});
}


sub getIterationCount {
    my ($self) = @_;

    return $self->{iterCount};
}


sub getSeed {
    my ($self) = @_;

    return $self->{usedRandSeed};
}


sub _initParticles {
    my ($self) = @_;

    for my $id (0 .. $self->{numParticles} - 1) {
        $self->{prtcls}[$id]{id} = $id;
        $self->_initParticle ($self->{prtcls}[$id]);
    }
}


sub _initParticle {
    my ($self, $prtcl) = @_;

    # each particle is a hash of arrays with the array sizes being the
    # dimensionality of the problem space
    for my $d (0 .. $self->{dimensions} - 1) {
        $prtcl->{currPos}[$d] =
            $self->_randInRange ($self->{posMin}, $self->{posMax});

        $prtcl->{velocity}[$d] =
              $self->{randStartVelocity}
            ? $self->_randInRange (-$self->{deltaMax}, $self->{deltaMax})
            : 0;
    }

    $prtcl->{currFit} = $self->_calcPosFit ($prtcl->{currPos});
    $self->_calcNextPos ($prtcl);

    unless (defined $prtcl->{bestFit}) {
        $prtcl->{bestPos}[$_] =
            $self->_randInRange ($self->{posMin}, $self->{posMax})
            for 0 .. $self->{dimensions} - 1;
        $prtcl->{bestFit} = $self->_calcPosFit ($prtcl->{bestPos});
    }
}


sub _calcPosFit {
    my ($self, $pos) = @_;

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

    for my $iter (1 .. $iterations) {
        ++$self->{iterCount};
        last if defined $self->_moveParticles ($iter);

        $self->_updateVelocities ($iter);
        next if !$self->{exitPlateau} || !defined $self->{bestBest};

        if ($iter >= $self->{exitPlateauBurnin} - $self->{exitPlateauWindow}) {
            my $i = $iter % $self->{exitPlateauWindow};

            $self->{bestsMean} -= $self->{bestBestByIter}[$i]
                if defined $self->{bestBestByIter}[$i];
            $self->{bestsMean} += $self->{bestBestByIter}[$i] =
                $self->{bestBest} / $self->{exitPlateauWindow};
        }

        next if $iter <= $self->{exitPlateauBurnin};

        #Round to the specified number of d.p.
        my $format  = "%.$self->{exitPlateauDP}f";
        my $mean    = sprintf $format, $self->{bestsMean};
        my $current = sprintf $format, $self->{bestBest};

        #Check if there is a sufficient plateau - stopping iterations if so
        last if $mean == $current;
    }

    return $self->{bestBest};
}


sub _moveParticles {
    my ($self, $iter) = @_;

    print "Iter $iter\n" if $self->{verbose} & kLogIter;

    for my $prtcl (@{$self->{prtcls}}) {
        @{$prtcl->{currPos}} = @{$prtcl->{nextPos}};
        $prtcl->{currFit} = $prtcl->{nextFit};

        my $fit = $prtcl->{currFit};

        if ($self->_betterFit ($fit, $prtcl->{bestFit})) {
            # Save position - best fit for this particle so far
            $self->_saveBest ($prtcl, $fit, $iter);
        }

        return $fit if defined $self->{exitFit} and $fit < $self->{exitFit};
        next if !($self->{verbose} & kLogIterDetail);

        printf "Part %3d fit %8.2f", $prtcl->{id}, $fit
            if $self->{verbose} >= 2;
        printf " (%s @ %s)",
            join (', ', map {sprintf '%5.3f', $_} @{$prtcl->{velocity}}),
            join (', ', map {sprintf '%5.2f', $_} @{$prtcl->{currPos}})
            if $self->{verbose} & kLogDetail;
        print "\n";
    }

    return undef;
}


sub _saveBest {
    my ($self, $prtcl, $fit, $iter) = @_;

    # for each dimension, set the best position as the current position
    @{$prtcl->{bestPos}} = @{$prtcl->{currPos}};

    $prtcl->{bestFit} = $fit;
    return if !$self->_betterFit ($fit, $self->{bestBest});

    if ($self->{verbose} & kLogBetter) {
        my $velSq;

        $velSq += $_**2 for @{$prtcl->{velocity}};
        printf "#%05d: Particle $prtcl->{id} best: %.4f (vel: %.3f)\n",
            $iter, $fit, sqrt ($velSq);
    }

    $self->{bestBest} = $fit;
}


sub _betterFit {
    my ($self, $new, $old) = @_;

    return !defined ($old) || ($new < $old);
}


sub _updateVelocities {
    my ($self, $iter) = @_;

    for my $prtcl (@{$self->{prtcls}}) {
        my $bestN = $self->{prtcls}[$self->_getBestNeighbour ($prtcl)];
        my $velSq;

        for my $d (0 .. $self->{dimensions} - 1) {
            my $meFactor =
                $self->_randInRange (-$self->{meWeight}, $self->{meWeight});
            my $themFactor =
                $self->_randInRange (-$self->{themWeight}, $self->{themWeight});
            my $meDelta   = $prtcl->{bestPos}[$d] - $prtcl->{currPos}[$d];
            my $themDelta = $bestN->{bestPos}[$d] - $prtcl->{currPos}[$d];

            $prtcl->{velocity}[$d] =
                $prtcl->{velocity}[$d] * $self->{inertia} +
                $meFactor * $meDelta +
                $themFactor * $themDelta;
            $velSq += $prtcl->{velocity}[$d]**2;
        }

        my $vel = sqrt ($velSq);
        if (!$vel or $self->{stallSpeed} and $vel <= $self->{stallSpeed}) {
            $self->_initParticle ($prtcl);
            printf "#%05d: Particle $prtcl->{id} stalled (%6f)\n", $iter, $vel
                if $self->{verbose} & kLogStall;
        }

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

In addition to any user provided parameters the list of values representing the
current particle position in the hyperspace is passed in. There is one value per
hyperspace dimension.

=item I<-inertia>: positive or zero number, optional

Determines what proportion of the previous velocity is carried forward to the
next iteration. Defaults to 0.9

See also I<-meWeight> and I<-themWeight>.

=item I<-iterations>: number, optional

Number of optimization iterations to perform. Defaults to 1000.

=item I<-meWeight>: number, optional

Coefficient determining the influence of the current local best position on the
next iterations velocity. Defaults to 0.5.

See also I<-inertia> and I<-themWeight>.

=item I<-numNeighbors>: positive number, optional

Number of local particles considered to be part of the neighbourhood of the
current particle. Defaults to the square root of the total number of particles.

=item I<-numParticles>: positive number, optional

Number of particles in the swarm. Defaults to 10 times the number of dimensions.

=item I<-posMax>: number, optional

Maximum coordinate value for any dimension in the hyper space. Defaults to 100.

=item I<-posMin>: number, optional

Minimum coordinate value for any dimension in the hyper space. Defaults to
-I<-posMax> (if I<-posMax> is negative I<-posMin> should be set more negative).

=item I<-randSeed>: number, optional

Seed for the random number generator. Useful if you want to rerun an
optimization, perhaps for benchmarking or test purposes.

=item I<-randStartVelocity>: boolean, optional

Set true to initialize particles with a random velocity. Otherwise particle
velocity is set to 0 on initalization.

A range based on 1/100th of -I<-posMax> - I<-posMin> is used for the initial
speed in each dimension of the velocity vector if a random start velocity is
used.

=item I<-stallSpeed>: positive number, optional

Speed below which a particle is considered to be stalled and is repositioned to
a new random location with a new initial speed.

By default I<-stallSpeed> is undefined but particles with a speed of 0 will be
repositioned.

=item I<-themWeight>: number, optional

Coefficient determining the influence of the neighbourhod best position on the
next iterations velocity. Defaults to 0.5.

See also I<-inertia> and I<-meWeight>.

=item I<-exitPlateau>: boolean, optional

Set true to have the optimization check for plateaus (regions where the fit
hasn't improved much for a while) during the search. The optimization ends when
a suitable plateau is detected following the burn in period.

Defaults to undefined (option disabled).

=item I<-exitPlateauDP>: number, optional

Specify the number of decimal places to compare between the current fitness
function value and the mean of the previous I<-exitPlateauWindow> values.

Defaults to 10.

=item I<-exitPlateauWindow>: number, optional

Specify the size of the window used to calculate the mean for comparison to
the current output of the fitness function.  Correlates to the minimum size of a
plateau needed to end the optimization.

Defaults to 10% of the number of iterations (I<-iterations>).

=item I<-exitPlateauBurnin>: number, optional

Determines how many iterations to run before checking for plateaus.

Defaults to 50% of the number of iterations (I<-iterations>).

=item I<-verbose>: flags, optional

If set to a non-zero value I<-verbose> determines the level of diagnostic print
reporting that is generated during optimization.

The following constants may be bitwise ored together to set logging options:

=over 4

=item * kLogBetter

prints particle details when its fit becomes bebtter than its previous best.

=item * kLogStall

prints particle details when its velocity reaches 0 or falls below the stall
threshold.

=item * kLogIter

Shows the current iteration number.

=item * kLogDetail

Shows additional details for some of the other logging options.

=item * kLogIterDetail

Shorthand for C<kLogIter | kLogIterDetail>

=back

=back

=item B<setParams (%parameters)>

Set or change optimization parameters. See I<-new> above for a description of
the parameters that may be supplied.