package holeg.algorithm.binary;
import holeg.api.AlgorithmFrameworkFlex;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
import java.util.stream.Collectors;
import javax.swing.JFrame;
public class PsoAlgorithm extends AlgorithmFrameworkFlex {
//Parameter for Algo with default Values:
private int swarmSize = 20;
private int maxIterations = 100;
private double dependency = 2.07;
private int mutationIteration = 1;
private boolean useIntervalMutation = true;
private double mutationRate = 0.01;
private double mutateProbabilityInterval = 0.01;
private double maxMutationPercent = 0.01;
private double c1, c2, w;
private double maxVelocity = 4.0;
private boolean moreInformation = false;
public PsoAlgorithm() {
super();
addIntParameter("Particles", swarmSize, intValue -> swarmSize = intValue, () -> swarmSize, 1);
addIntParameter("Iterations", maxIterations, intValue -> maxIterations = intValue,
() -> maxIterations, 1);
addDoubleParameter("Dependency", dependency, doubleValue -> dependency = doubleValue,
() -> dependency, 2.001, 2.4);
addIntParameter("Mutation iteration", mutationIteration,
intValue -> mutationIteration = intValue, () -> mutationIteration, 0);
addBooleanParameter("Interval-based mutation", useIntervalMutation,
booleanValue -> useIntervalMutation = booleanValue);
addDoubleParameter("Mutation probability (%)", mutateProbabilityInterval,
doubleValue -> mutateProbabilityInterval = doubleValue, () -> mutateProbabilityInterval,
0.0, 1.0);
// addDoubleParameter("mutationRate", mutationRate, doubleValue -> mutationRate = doubleValue, () -> mutationRate, 0.0, 1.0);
addDoubleParameter("Mutation severity (% of problem size)", maxMutationPercent,
doubleValue -> maxMutationPercent = doubleValue, () -> maxMutationPercent, 0.0, 1.0);
addDoubleParameter("Velocity", maxVelocity, doubleValue -> maxVelocity = doubleValue,
() -> maxVelocity, 0.0);
addBooleanParameter("Detailed information", moreInformation,
booleanValue -> moreInformation = booleanValue);
}
public static void main(String[] args) {
JFrame newFrame = new JFrame("exampleWindow");
PsoAlgorithm instance = new PsoAlgorithm();
newFrame.setContentPane(instance.getPanel());
newFrame.pack();
newFrame.setVisible(true);
newFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
@Override
protected int getProgressBarMaxCount() {
return swarmSize * (maxIterations + 1) * rounds + rounds;
}
/**
*
Algo from Paper:
*
* Begin
* t = 0; {t: generation index}
* initialize particles xp,i,j(t);
* evaluation xp,i,j(t);
* while (termination condition ≠ true) do
* vi,j(t) = update vi,j(t); {by Eq. (6)}
* xg,i,j(t) = update xg,i,j(t); {by Eq. (7)}
* xg,i,j(t) = mutation xg,i,j(t); {by Eq. (11)}
* xp,i,j(t) = decode xg,i,j(t); {by Eqs. (8) and (9)}
* evaluate xp,i,j(t);
* t = t + 1;
* end while
* End
* with:
*
* xg,i,j: genotype ->genetic information -> in continuous space
xp,i,j:
* phenotype -> observable characteristics-> in binary space
Xg,max: is the Maximum
* here set to 4.
Eq. (6):vi,j(t + 1) = wvi,j+c1R1(Pbest,i,j-xp,i,j(t))+c2R2(gbest,i,j-xp,i,j(t))
* Eq. (7):xg,i,j(t + 1) = xg,i,j(t) + vi,j(t + 1)
Eq.
* (11):if(rand()<rmu)then xg,i,j(t + 1) =
* -xg,i,j(t + 1)
Eq. (8):xp,i,j(t + 1) = (rand() <
* S(xg,i,j(t + 1))) ? 1 : 0
Eq. (9) Sigmoid:S(xg,i,j(t +
* 1)) := 1/(1 + e-xg,i,j(t + 1))
* Parameter:
* w inertia, calculated from phi(Variable:{@link #dependency})
c1: influence, calculated from
* phi(Variable:{@link #dependency})
c2: influence, calculated from phi(Variable:{@link
* #dependency})
rmu: probability that the proposed operation is conducted defined
* by limit(Variable:{@link #})
*/
@Override
protected Individual executeAlgo() {
initDependentParameter();
Individual globalBest = new Individual();
globalBest.position = extractPositionAndAccess();
globalBest.fitness = evaluatePosition(globalBest.position);
console.println("Start Value:" + globalBest.fitness);
int dimensions = globalBest.position.size();
List swarm = initializeParticles(dimensions);
List runList = new ArrayList();
runList.add(globalBest.fitness);
evaluation(globalBest, swarm);
runList.add(globalBest.fitness);
for (int iteration = 0; iteration < maxIterations; iteration++) {
int mutationAllowed = iteration % mutationIteration;
double bitsFlipped = 0;
for (int particleNumber = 0; particleNumber < swarmSize; particleNumber++) {
Particle particle = swarm.get(particleNumber);
if (this.useIntervalMutation) {
boolean allowMutation = (Random.nextDouble() < this.mutateProbabilityInterval);
TreeSet mutationLocationSet = null;
if (allowMutation) {
mutationLocationSet = locationsToMutate(dimensions);
}
for (int index = 0; index < dimensions; index++) {
updateVelocity(particle, index, globalBest);
updateGenotype(particle, index);
if (allowMutation && mutationAllowed == 0 && iteration != 0
&& mutationLocationSet.contains(index)) {
mutation(particle, index);
}
decode(particle, index);
}
} else {
int count = 0;
for (int index = 0; index < dimensions; index++) {
updateVelocity(particle, index, globalBest);
updateGenotype(particle, index);
if (mutationAllowed == 0 && iteration != 0
&& Random.nextDouble() < mutateProbabilityInterval) {
count++;
mutation(particle, index);
}
decode(particle, index);
}
bitsFlipped += count;
}
}
if (moreInformation) {
console.println("\t\t\t\t\t\tAvgBitsMutate: " + (bitsFlipped / (double) swarmSize));
}
if (cancel) {
return null;
}
evaluation(globalBest, swarm);
runList.add(globalBest.fitness);
if (moreInformation) {
console.println("------------------------");
}
}
console.println(" End Value:" + globalBest.fitness);
this.runList = runList;
return globalBest;
}
/**
* @param j maximum index of position in the particle
* @return
*/
private List initializeParticles(int j) {
List swarm = new ArrayList();
//Create The Particle
for (int particleNumber = 0; particleNumber < swarmSize; particleNumber++) {
//Create a Random position
List aRandomPosition = new ArrayList();
for (int index = 0; index < j; index++) {
aRandomPosition.add(Random.nextBoolean());
}
swarm.add(new Particle(aRandomPosition));
}
return swarm;
}
/**
* Calculate w, c1, c2
*/
private void initDependentParameter() {
w = 1.0 / (dependency - 1 + Math.sqrt(dependency * dependency - 2 * dependency));
c1 = c2 = dependency * w;
}
/**
* Evaluate each particle and update the global Best position;
*
* @param globalBest
* @param swarm
*/
private void evaluation(Individual globalBest, List swarm) {
for (Particle p : swarm) {
double localEvaluationValue = evaluatePosition(p.xPhenotype);
if (moreInformation) {
console.println("Fitness " + localEvaluationValue);
}
p.checkNewEvaluationValue(localEvaluationValue);
if (localEvaluationValue < globalBest.fitness) {
globalBest.fitness = localEvaluationValue;
globalBest.position = p.localBest.position;
}
}
}
/**
* Eq. (6):vi,j(t + 1) = wvi,j+c1R1(Pbest,i,j-xp,i,j(t))+c2R2(gbest,i,j-xp,i,j(t))
*
* @param particle
* @param index
* @param globalBest
*/
private void updateVelocity(Particle particle, int index, Individual globalBest) {
double r1 = Random.nextDouble();
double r2 = Random.nextDouble();
double posValue = particle.xPhenotype.get(index) ? 1.0 : 0.0;
particle.velocity.set(index, clamp(w * particle.velocity.get(index) + c1 * r1 * (
(particle.localBest.position.get(index) ? 1.0 : 0.0) - posValue) + c2 * r2 * (
(globalBest.position.get(index) ? 1.0 : 0.0) - posValue)));
}
/**
* Eq. (7):xg,i,j(t + 1) = xg,i,j(t) + vi,j(t + 1)
*
* @param particle
* @param index
*/
private void updateGenotype(Particle particle, int index) {
particle.xGenotype.set(index,
clamp(particle.xGenotype.get(index) + particle.velocity.get(index)));
}
/**
* Eq. (11):if(rand()<rmu)then xg,i,j(t + 1) =
* -xg,i,j(t + 1)
*
* @param particle
* @param index
*/
private void mutation(Particle particle, int index) {
//if(Random.nextDouble() < limit)
particle.xGenotype.set(index, -particle.xGenotype.get(index));
}
/**
* Eq. (8):xp,i,j(t + 1) = (rand() < S(xg,i,j(t + 1))) ? 1
* : 0
*
* @param particle
* @param index
*/
private void decode(Particle particle, int index) {
particle.xPhenotype.set(index, Random.nextDouble() < Sigmoid(particle.xGenotype.get(index)));
}
/**
* Eq. (9) Sigmoid:S(xg,i,j(t + 1)) := 1/(1 + e-xg,i,j(t +
* 1))
*
* @param value
* @return
*/
private double Sigmoid(double value) {
return 1.0 / (1.0 + Math.exp(-value));
}
/**
* To clamp Xg,j,i and vi,j in Range [-Xg,max|+Xg,max]
* with {Xg,max= 4}
*
* @param value
* @return
*/
private double clamp(double value) {
return Math.max(-maxVelocity, Math.min(maxVelocity, value));
}
private TreeSet locationsToMutate(int dimensions) {
TreeSet mutationLocation = new TreeSet(); //sortedSet
int maximumAmountOfMutatedBits = Math.max(1,
(int) Math.round(((double) dimensions) * this.maxMutationPercent));
int randomUniformAmountOfMutatedValues = Random.nextIntegerInRange(1,
maximumAmountOfMutatedBits + 1);
for (int i = 0; i < randomUniformAmountOfMutatedValues; i++) {
boolean success = mutationLocation.add(Random.nextIntegerInRange(0, dimensions));
if (!success) {
i--; //can be add up to some series long loops if maximumAmountOfMutatedBits get closed to problemsize.
}
}
return mutationLocation;
}
@Override
protected String algoInformationToPrint() {
// private int swarmSize = 20;
// private int maxIterations = 100;
// private double limit = 0.01;
// private double dependency = 2.07;
// private int mutationInterval = 1;
// private boolean useIntervalMutation = true;
// private double mutateProbabilityInterval = 0.01;
// private double maxMutationPercent = 0.01;
return "PsoAlgo" + " Rounds:" + rounds
+ " maxIterations:" + maxIterations
+ " swarmSize:" + swarmSize
+ " dependency:" + dependency
+ " mutationInterval:" + mutationIteration
+ " maxVelocity: " + maxVelocity
+ (useIntervalMutation ?
(" mutateProbabilityInterval:" + mutateProbabilityInterval
+ " maxMutationPercent:" + maxMutationPercent) : " mutationRate:" + mutationRate);
}
@Override
protected String plottFileName() {
return "plottPsoAlgo.txt";
}
/**
* Class to represent a Particle.
*/
private class Particle {
/**
* The velocity of a particle.
*/
public List velocity;
/**
* The positions genotype.
*/
public List xGenotype;
/**
* The positions phenotype. Alias the current position.
*/
public List xPhenotype;
public Individual localBest;
Particle(List position) {
this.xPhenotype = position;
//Init velocity, xGenotype with 0.0 values.
this.velocity = position.stream().map(bool -> 0.0).collect(Collectors.toList());
this.xGenotype = position.stream().map(bool -> 0.0).collect(Collectors.toList());
localBest = new Individual();
localBest.fitness = Double.MAX_VALUE;
}
public void checkNewEvaluationValue(double newEvaluationValue) {
if (newEvaluationValue < localBest.fitness) {
localBest.fitness = newEvaluationValue;
localBest.position = xPhenotype.stream().map(bool -> bool).collect(Collectors.toList());
}
}
public String toString() {
return "Particle with xPhenotype(Position), xGenotype, velocity:["
+ listToString(xPhenotype) + "],[" + listToString(xGenotype) + "],["
+ listToString(velocity) + "]";
}
private String listToString(List list) {
return list.stream().map(Object::toString).collect(Collectors.joining(", "));
}
}
}