Documentation ¶
Overview ¶
Package setpso is a collection of Set based Particle Swarm Optimisers(SPSO) designed for cost functions that map binary patterns to *big.Int cost values. The binary patterns called Parameters is encoded also as a *big.Int. The SPSO is a swarm of entities called Particles that together iteratively hunt for better solutions. The update iteration of the swarm mimics the spirit of the continuous case and is based on set operations. It also includes experimental enhancements to improve the discrete case. For brief introduction, context of use and planned future development read the Readme file at https://github.com/mathrgo/setpso
Relation to Other Sub Packages ¶
Package setpso lives in a directory that is at the top of a a hierarchy of packages.
Package setpso contains two working SPSOs: GPso and CLPso that depend on Pso for all interfaces except Update() needed in package psokit.
Packages in setpso/fun is where cost-functions that interface with Pso are usually placed and includes any helper packages for such cost-functions.
Package psokit enables a high level multiple run interface where elements for the rum are referred by name to be used in setting up runs of various SPSOs and cost-function combinations and searching for good heuristics.
Particle's Personal-best ¶
While exploring Parameters for finding reduced cost as returned by the independent cost function the Particle keeps a record of the personal best Parameter achieved so far called Personal-best with a corresponding best cost. The Personal-best status is checked after each update.
Particle's Update Velocity ¶
It represents update Velocity as a vector of weights of the probability of flipping the corresponding bit at the update iteration. At the beginning of the update the velocity is calculated without flipping bits and then the bits are flipped with a probability given by the computed velocity component. During the update, once the bit has been flipped the corresponding probability is set to zero thus avoiding flipping back and keeping the velocity as a vector of flips that are requested with a given probability to move from a given position to a desired one that may improve performance.
during the calculation of the velocity of a particle probabilities are combined using an operation called pseudo adding where by default probabilities p,q are pseudo added to give p+q-pq. Alternatives may be considered in the future such as max(p,q) if only to show which is best.
Grouping of particles ¶
The particles are split up into groups with each group containing its own heuristic settings and a list of particles called Targets for it to tend to move towards. each Particle in the group also uses its Personal-best to move towards. Various strategies for targeting other Particle's personal-best Parameters or adapting heuristics can be explored: Pso is not used by its self, since it has no targets, but forms most common interfaces and has a function PUpdate() that does the common velocity update. To create a functioning SPSO extra code is added before PUpdate() to choose Targets and Heuristics which are added by the derived working SPSOs to generate the total update iteration function, Update(). GPso and CLPso are examples of such derived working SPSOs.
It is important to note that the collection of groups is stored as mapping from strings to pointers to groups so groups can be accessed by name if necessary although each particle knows which group it belongs to without using the name reference. Also groups can have no particles that belong to the group. At start up there is only one group called "root" which contains all the particles. Additional groups can be formed during initialisation or even during iteration and particles moved between groups as and when required.
setpso can be used in low level coding and the higher level run management is provided by the psokit toolkit package in
import "github.com/mathrgo/setpso/psokit"
you can quickly get to run an example by going to the setpso/example/runkit1 directory in a terminal then execute
go run runkit1.go -nrun 1
Index ¶
- Constants
- func CardinalSize(x *big.Int) (card int)
- func Pc0(i int, n float64) float64
- type CLPso
- type CLpart
- type Fun
- type GPso
- type Group
- type Particle
- type Pso
- func (pso *Pso) BestParticle() int
- func (pso *Pso) BlurTarget(x *big.Int, id int, l, l0 float64)
- func (pso *Pso) CreateGroup(name string, ntargets int) *Group
- func (pso *Pso) CreatePsoHeuristics() *PsoHeuristics
- func (pso *Pso) CurrentTry(i int) Try
- func (pso *Pso) Gr(name string) *Group
- func (pso *Pso) Group(id int) *Group
- func (pso *Pso) GroupBest(grp *Group) (best int)
- func (pso *Pso) Heuristics() *PsoHeuristics
- func (pso *Pso) LocalBestTry(i int) Try
- func (pso *Pso) MoveTo(g *Group, pat int)
- func (pso *Pso) NominalL() (l float64)
- func (pso *Pso) Nparticles() int
- func (pso *Pso) PUpdate()
- func (pso *Pso) Part(i int) *Particle
- func (pso *Pso) PrintDebug(w io.Writer, id string)
- func (pso *Pso) SetGroupHeuristics(g *Group, h *PsoHeuristics)
- func (pso *Pso) SetGroupTarget(grp *Group, targetList ...int)
- func (pso *Pso) SetParams(id int)
- func (pso *Pso) UpdateGlobal()
- func (pso *Pso) UpdateGroup(g *Group)
- type PsoHeuristics
- type PsoInterface
- type Try
Constants ¶
const ( //PhiHeuristic for target shooting probability range (1.0 ) PhiHeuristic = iota //OmegaHeuristic for probability velocity factoring after target blur (0.73) OmegaHeuristic = iota //LfactorHeuristic for target blur factor (0.15) LfactorHeuristic = iota //LoffsetHeuristic for target blur offset (2.0) LoffsetHeuristic = iota //ThresholdHeuristic for acting on a comparison(0.99) ThresholdHeuristic = iota )
const ( //NTriesHeuristic for maximum number of tries stored in a particle(250) NTriesHeuristic = iota //TryGapHeuristic for a minimum number of tries before doing something different(100) TryGapHeuristic = iota )
Variables ¶
This section is empty.
Functions ¶
func CardinalSize ¶
CardinalSize returns the number of 1's in a binary representation of Int (assuming it is positive) so is the cardinal size of the corresponding set.
func Pc0 ¶
Pc0 calculates the assigned probability of learning from other particles. i is the Particle id and n is the number of particles. The formula is an empirical one used in the continuous case. This is likely to be replaced by another empirical formula called Pc1 and Pc0 is just a stand in for Pc1.
Types ¶
type CLPso ¶
type CLPso struct { *Pso //target refreshing gap TryGap int // contains filtered or unexported fields }
CLPso is a comprehensive learning PSO that targets other personal best rather than just the global best. Each particle has its own group with group name set to the particles id and has one target. All particles share Heuristics.
func NewCLPso ¶
NewCLPso creates a CLPso and sets the heuristics if required. In this case TryGapHeuristic is the number of iterations with no improvement needed to trigger the probabilistic search for an alternative target. The ith particle is assigned the probability Pc0(i,n) to look for an alternative target when triggered, where n is the number of particles.
func (*CLPso) SetHeuristics ¶
func (p *CLPso) SetHeuristics(hu *PsoHeuristics)
SetHeuristics sets the heuristics for the particle swarm.
func (*CLPso) Update ¶
func (p *CLPso) Update()
Update does the iteration update. For each Particle a check is made to see if the updates have not given an improvement in cost of the Parameters compared to the last improvement for at least TryGap iterations. If so it looks for an alternative target with probability pc=Pc0(). If it looks for an alternative target it randomly selects two Particles and chooses the one that gives the least of the Local-best Cost. Note the choice is from all particles and can include itself. After this it does the usual PUpdate().
type CLpart ¶
type CLpart struct {
// contains filtered or unexported fields
}
CLpart includes the additional particle state used by CLPso to manage particle targets.
type Fun ¶
type Fun interface { //creates a new Try which is a pointer to a structure using a default parameter that should satisfy constraints and updates Try's cost and internal decode. NewTry() Try // setup t from x, where z is parameter assumed to satisfy constraints and it also computes dependants such as cost SetTry(t Try, z *big.Int) // sets the try by copying src to dest Copy(dest, src Try) // updates cost evaluation of a try where a lower cost is better // this is needed when the cost changes UpdateCost(x Try) // Cmp checks to see if y is better than x // for mode = futil.CostMode: // compare two tries with a spread of uncertainty from -1.0 to 1.0. -1.0 for // definitely cost(x) < cost(y) and 1.0 for definitely cost(x) > cost(y). // A deterministic cost should always return -1.0 or 1.0 with a value of // -1.0 if the costs are equal. // for mode = futil.TriesMode: (used only when cost is not deterministic) // compare how successful y has been in being better than an x //and updates y's success stats. // While being compared a value > 1.0 indicates y should replace x; a value // < -1.0 indicates y should be removed as a candidate. Cmp(x, y Try, mode futil.CmpMode) float64 // maximum number of bits in the parameter big integer which is the // maximum number of elements in the subset // at the moment this is fixed during a run but in the future could vary possibly to incorporate some form of subroutine use. MaxLen() (maxlen int) // string giving a description of the cost function About() (s string) // this attempts to give a constraint satisfying Try in pre that matches the hint by modifying hint // pre is the previous try to be replaced. on success it returns true otherwise it returns false and should leave pre un changed. ToConstraint(pre Try, hint *big.Int) bool // this hints to the function to replace the ith particle-item // if it returns True the function has replaced the item with a new meaning // thus modifying the decoder. Delete(i int) bool }
Fun is the interface to the function that evaluates the cost of tries. The try parameter is a binary pattern stored as a big integer. The integer can be regarded as a sub set of integers from 0 to MaxLen()-1 where i in this range is a member of the sub set if the ith bit is 1. MaxLen() returns the maximum number of bits in the pattern. ToConstraint() attempts to modify hint to be constraint satisfying. while possibly using pre to aid in this process. pre should not be changed during this process. It returns true if it succeeds. By convention pre always corresponds to a Parameter (apart from when it is the empty set at the beginning) that was a personal best and thus satisfies the constraints required by the function to give a meaningful solution. The function should be able to find a constraint satisfying version for hint that approximates to hint most of the time so that the SPSO can frequently change the Particle's Parameter during an update.
Providing a Meaningful Interpretation of Parameters ¶
Representing a particle's Parameters as a binary string or subset may not be easily interpreted as a meaningful representation of a solution to a combinatorial optimization so the cost function must provide an easily understood description of a Parameter as a string supplied by the Decode() function.
Catering for Changing a Set Item ¶
This is an advanced feature for cost functions. Certain set items will after a while not be used to give personal best at which point a cost function can be hinted to remove this item through Delete() which returns true if the cost function does so. if the cost function returns true it is then up to the cost function to either replace this by a new item with its own contribution to cost or set the corresponding item in a hint to zero during a successful ToConstraint() call. in this way the cost function can try out alternative items that may result in an improved cost. Typically this feature is not used and a call to Delete() returns false.
type GPso ¶
type GPso struct {
*Pso
}
GPso is a PSO that targets the global best element and has only one Group corresponding to all the particles
func (*GPso) SetHeuristics ¶
func (p *GPso) SetHeuristics(hu *PsoHeuristics)
SetHeuristics sets the heuristics for the particle swarm.
type Group ¶
type Group struct {
// contains filtered or unexported fields
}
Group is a collection of particles with same heuristic settings
func (*Group) Heuristics ¶
func (g *Group) Heuristics() (hu *PsoHeuristics)
Heuristics returns the pointer to the group's heuristics
type Particle ¶
type Particle struct {
// contains filtered or unexported fields
}
Particle is the state of a member of the PSO
type Pso ¶
type Pso struct { // collection of particles Pt []Particle // contains filtered or unexported fields }
Pso is the Particle swarm optimizer
func NewPso ¶
NewPso sets up a PSO with a swarm of n particles. fun is the costing function interface. Each Particle has a big integer Parameter. To initialize the parameter set values are uniformly randomly chosen with integer values up to Func.MaxLen()bits; ToConstraint() is used on these random choices with repeated use of random choice until each Particle has an initial Parameters that satisfies the cost function constraints on the Parameters. Default heuristics are applied to the "root" Group and all particles are added to this group. The PSO uses the random generator seed sd.
func (*Pso) BestParticle ¶
BestParticle returns the current global best particle.
func (*Pso) BlurTarget ¶
BlurTarget blurs the target set displacement based on its CardinalSize. Normally x is the exclusive or of a particle Parameters with a target Local-best Parameters. The blur is effected indirectly by pseudo adding a probability
pb =rand*(l*CardinalSize(x)+l0)/MaxLen()
to each component of the Velocity;l,l0 corresponds to the LfactorHeuristic, LoffsetHeuristic heuristics;MaxLen() is the maximum number of set items ;rand is a random number between 0 and 1.
func (*Pso) CreateGroup ¶
CreateGroup creates a group named 'name' with a slot for 'ntargets' targets. The heuristics for the group are shared from the 'root' group.
func (*Pso) CreatePsoHeuristics ¶
func (pso *Pso) CreatePsoHeuristics() *PsoHeuristics
CreatePsoHeuristics returns a pointer to a SPSO heuristics parameters with default values. pso is used to pass SPSO instance parameters such as number of particles and the initial number of elements in the parameter set to help provide tuned heuristics.
func (*Pso) CurrentTry ¶
CurrentTry returns the current try for the ith particle
func (*Pso) GroupBest ¶
GroupBest returns the best particle id in the group grp. It returns -1 if there is no member.
func (*Pso) Heuristics ¶
func (pso *Pso) Heuristics() *PsoHeuristics
Heuristics returns a copy of the master heuristics
func (*Pso) LocalBestTry ¶
LocalBestTry returns Local-best try of the ith Particle
func (*Pso) NominalL ¶
NominalL returns a nominal LfactorHeuristic value for the LfactorHeuristic based on * Number of particles and number of parameters. This was tuned for the * continuous case this needs tuning for the discrete set case and is not yet * used.
func (*Pso) Nparticles ¶
Nparticles returns the number of particles in use.
func (*Pso) PUpdate ¶
func (pso *Pso) PUpdate()
PUpdate does a single step update assuming that groups have been setup with the appropriate targets and heuristics.
for each Particle the Parameters difference between itself Personal-best and Targets is represented by taking the exclusive or of the corresponding Parameters as subset. This is then used to pseudo add up contributions to target blur prior to reducing the velocity by a factor equal to the OmegaHeuristic heuristic.
Then the PhiHeuristic is used to generate randomly chosen parameters r for each exclusive or between 0 and PhiHeuristic; each r is checked to be <= 1.0 and is forced to be so by replacing by 2-r if it isn't. These r are then pseudo added to the the velocity components that have an exclusive or bit of 1.
In this way the Velocity components are computed to encourage movement toward Personal-best and Targets after encouraging more mutation for distant Targets and Personal-best Parameters.
After this Setparams() and UpdateGlobal() are called to finish the update.
func (*Pso) PrintDebug ¶
PrintDebug outputs debugging diagnostics depending on the command id. It has the following values and output:
Command | Output =============================== group | group data for each Particle group0 | "root" group data's best member and cost Pt | particle local-best cost and parameter and | current parameter for each particle vel | velocity for each particle
func (*Pso) SetGroupHeuristics ¶
func (pso *Pso) SetGroupHeuristics(g *Group, h *PsoHeuristics)
SetGroupHeuristics sets the heuristics for the group g. As the Pso undergoes development additional heuristic parameters can be introduced with compatible defaults without destroying backwards compatibility with previous versions that do not have the extra heuristics. Not that only a link to the heuristics is passed so the heuristics can be changed outside the group with many groups referring to the same heuristics.
All group heuristics are derived, normally by just a pointer, from a master heuristics stored in pso, so often all heuristics can be changed via the master heuristic; how this is done should be through calling SetHeuristic() for the derived SPSO.
func (*Pso) SetGroupTarget ¶
SetGroupTarget sets the first few Targets of group 'grp' to the particle list targetList.
func (*Pso) SetParams ¶
SetParams sets the parameters of the id th particle updating the resulting cost and personal best case. It also revaluates the personal best cost in case the function has changed.
func (*Pso) UpdateGlobal ¶
func (pso *Pso) UpdateGlobal()
UpdateGlobal updates the global best by calling UpdateGroup() and then finding the best group with its best particle.
It searches for minimum best cost particle.
func (*Pso) UpdateGroup ¶
UpdateGroup does housekeeping for the group k it calculates the best try and the particle in group that gives this. Note that it looks for the best in the current iteration and disregards historic best costs even if they were better.
type PsoHeuristics ¶
type PsoHeuristics struct {
// contains filtered or unexported fields
}
PsoHeuristics is the collection of group heuristics, where some of the heuristics may not be used. The default values are in brackets.
Support for future heuristics ¶
Future heuristic parameters may be added to this list which can be ignored by earlier PSO variants by suitable choice of defaults. Note heuristics are often shared between groups so it is important to know where this is done when updating a group's heuristics.
func (*PsoHeuristics) Float ¶
func (hu *PsoHeuristics) Float(i int) float64
Float returns the ith floating point heuristic
func (*PsoHeuristics) Int ¶
func (hu *PsoHeuristics) Int(i int) int
Int returns the ith floating point heuristic
func (*PsoHeuristics) SetFloat ¶
func (hu *PsoHeuristics) SetFloat(i int, x float64)
SetFloat sets the ith floating point heuristic to x
func (*PsoHeuristics) SetInt ¶
func (hu *PsoHeuristics) SetInt(i, x int)
SetInt sets the ith integer heuristic to x
func (*PsoHeuristics) ToDefault ¶
func (hu *PsoHeuristics) ToDefault(pso *Pso)
ToDefault sets the heuristics to their default value. Note this may change in future when better defaults are found. pso is used to pass SPSO parameters.
type PsoInterface ¶
type PsoInterface interface { // single state update to all particles in the PSO Update() // best particle Id BestParticle() int // number of particles Nparticles() int // array of particles Part(i int) *Particle // current try of the ith Particle CurrentTry(i int) Try // Local-best try of the ith Particle LocalBestTry(i int) Try // interface for requesting debug output based on cmd PrintDebug(w io.Writer, cmd string) //Heuristics returns a copy of the master heuristics Heuristics() *PsoHeuristics //SetHeuristics sets the heuristics for the particle swarm. SetHeuristics(hu *PsoHeuristics) }
PsoInterface is the interface used with the PSO and its variants. Normally Pso supplies this apart from the Update() function. The interface is used by the monitoring and running program and psokit uses this interface to provide useful plotting functions.
Directories ¶
Path | Synopsis |
---|---|
example
|
|
multimodeS
main gives an example of a multimode function with added noise for testing the SPSO using the futil.SFloatCostvalue CostValue interface
|
main gives an example of a multimode function with added noise for testing the SPSO using the futil.SFloatCostvalue CostValue interface |
parityDAG
main gives an example of how to find DAG modeling of parity checking using random samples.
|
main gives an example of how to find DAG modeling of parity checking using random samples. |
quadDAG
main gives an example of how to find DAG modeling of quadratic equation solution.
|
main gives an example of how to find DAG modeling of quadratic equation solution. |
runkit2
main gives an example of how to use psokit to run an arbitrary prime factorization problem.
|
main gives an example of how to use psokit to run an arbitrary prime factorization problem. |
sc42
this runs the sum of 3 cubes for 42 finder
|
this runs the sum of 3 cubes for 42 finder |
fun
|
|
circles
Package circles provides method for playing with circles
|
Package circles provides method for playing with circles |
cubes3442
Package cubes3442 is a function for finding the sum of 3 cubes that equals 42.
|
Package cubes3442 is a function for finding the sum of 3 cubes that equals 42. |
dag
Package dag provides the base for Directed Asynchronous Graphs functions with two inputs per node.
|
Package dag provides the base for Directed Asynchronous Graphs functions with two inputs per node. |
futil
Package futil provides some usefull utilities for cost functions
|
Package futil provides some usefull utilities for cost functions |
lincircles
Package lincircles provides method for packing circles on a straight line using a packing cost
|
Package lincircles provides method for packing circles on a straight line using a packing cost |
multimode
Package multimode is a multimode function with noise
|
Package multimode is a multimode function with noise |
quadratic
Package quadratic includes a sampler for finding algebraic solutions to quadratic equation ax^2+bx+c =0.
|
Package quadratic includes a sampler for finding algebraic solutions to quadratic equation ax^2+bx+c =0. |
simplefactor
Package simplefactor is a cost function for finding prime factor pair: used to check that it is too difficult for the PSO to find the primes.
|
Package simplefactor is a cost function for finding prime factor pair: used to check that it is too difficult for the PSO to find the primes. |
subsetsum
Package subsetsum contains the object Fun and its generator for the the cost function of the combinatorial subset sum problem where a big integer is used to represent subsets as well as integer values thus potentially being able to represent combinatorial hard problems
|
Package subsetsum contains the object Fun and its generator for the the cost function of the combinatorial subset sum problem where a big integer is used to represent subsets as well as integer values thus potentially being able to represent combinatorial hard problems |
this is a utility for generating prime pairs
|
this is a utility for generating prime pairs |
Package psokit is a toolkit for running a collection of, at the moment, experimental Set-based Particle Swarm Optimisers (SPSOs) in the package setpso.
|
Package psokit is a toolkit for running a collection of, at the moment, experimental Set-based Particle Swarm Optimisers (SPSOs) in the package setpso. |