package algorithm.binary;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
import java.util.stream.Collectors;
import javax.swing.JFrame;
import api.AlgorithmFrameworkFlex;
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 mutationInterval = 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 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);
}
public PsoAlgorithm() {
super();
addIntParameter("swarmSize", swarmSize, intValue -> swarmSize = intValue, () -> swarmSize, 1);
addIntParameter("maxIterations", maxIterations, intValue -> maxIterations = intValue, () -> maxIterations, 1);
addDoubleParameter("dependency", dependency, doubleValue -> dependency = doubleValue, () -> dependency, 2.001, 2.4);
addIntParameter("mutationInterval", mutationInterval, intValue -> mutationInterval = intValue, () -> mutationInterval, 0);
addBooleanParameter("useIntervalMutation", useIntervalMutation, booleanValue -> useIntervalMutation = booleanValue);
addDoubleParameter("mutateProbabilityInterval", mutateProbabilityInterval, doubleValue -> mutateProbabilityInterval = doubleValue, () -> mutateProbabilityInterval, 0.0, 1.0);
addDoubleParameter("mutationRate", mutationRate, doubleValue -> mutationRate = doubleValue, () -> mutationRate, 0.0, 1.0);
addDoubleParameter("maxMutationPercent", maxMutationPercent, doubleValue -> maxMutationPercent = doubleValue, () -> maxMutationPercent, 0.0, 1.0);
addDoubleParameter("maxVelocity", maxVelocity, doubleValue -> maxVelocity = doubleValue, () -> maxVelocity, 0.0);
addBooleanParameter("moreInformation", moreInformation , booleanValue -> moreInformation = booleanValue);
}
@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 #limit})
*
*
*/
@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 % mutationInterval;
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() < mutationRate) {
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:" + mutationInterval
+ " maxVelocity: " + maxVelocity
+ (useIntervalMutation?
(" mutateProbabilityInterval:" + mutateProbabilityInterval
+ " maxMutationPercent:" + maxMutationPercent) : " mutationRate:" + mutationRate);
}
/**
* 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(", "));
}
}
@Override
protected String plottFileName() {
return "plottPsoAlgo.txt";
}
}