123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412 |
- 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;
- }
- /**
- * <p>Algo from Paper:</p><font size="3"><pre>
- *
- * Begin
- * t = 0; {t: generation index}
- * initialize particles x<sub>p,i,j</sub>(t);
- * evaluation x<sub>p,i,j</sub>(t);
- * while (termination condition ≠ true) do
- * v<sub>i,j</sub>(t) = update v<sub>i,j</sub>(t); {by Eq. (6)}
- * x<sub>g,i,j</sub>(t) = update x<sub>g,i,j</sub>(t); {by Eq. (7)}
- * x<sub>g,i,j</sub>(t) = mutation x<sub>g,i,j</sub>(t); {by Eq. (11)}
- * x<sub>p,i,j</sub>(t) = decode x<sub>g,i,j</sub>(t); {by Eqs. (8) and (9)}
- * evaluate x<sub>p,i,j</sub>(t);
- * t = t + 1;
- * end while
- * End</pre></font>
- * <p>with:</p><font size="3">
- *
- * x<sub>g,i,j</sub>: genotype ->genetic information -> in continuous space<br>
- * x<sub>p,i,j</sub>: phenotype -> observable characteristics-> in binary space<br>
- * X<sub>g,max</sub>: is the Maximum here set to 4.<br>
- * Eq. (6):v<sub>i,j</sub>(t + 1) = wv<sub>i,j</sub>+c<sub>1</sub>R<sub>1</sub>(P<sub>best,i,j</sub>-x<sub>p,i,j</sub>(t))+c<sub>2</sub>R<sub>2</sub>(g<sub>best,i,j</sub>-x<sub>p,i,j</sub>(t))<br>
- * Eq. (7):x<sub>g,i,j</sub>(t + 1) = x<sub>g,i,j</sub>(t) + v<sub>i,j</sub>(t + 1)<br>
- * Eq. (11):<b>if(</b>rand()<r<sub>mu</sub><b>)then</b> x<sub>g,i,j</sub>(t + 1) = -x<sub>g,i,j</sub>(t + 1)<br>
- * Eq. (8):x<sub>p,i,j</sub>(t + 1) = <b>(</b>rand() < S(x<sub>g,i,j</sub>(t + 1))<b>) ?</b> 1 <b>:</b> 0<br>
- * Eq. (9) Sigmoid:S(x<sub>g,i,j</sub>(t + 1)) := 1/(1 + e<sup>-x<sub>g,i,j</sub>(t + 1)</sup>)<br></font>
- * <p>Parameter:</p>
- * w inertia, calculated from phi(Variable:{@link #dependency})<br>
- * c1: influence, calculated from phi(Variable:{@link #dependency}) <br>
- * c2: influence, calculated from phi(Variable:{@link #dependency})<br>
- * r<sub>mu</sub>: probability that the proposed operation is conducted defined by limit(Variable:{@link #limit})<br>
- *
- *
- */
- @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<Particle> swarm= initializeParticles(dimensions);
- List<Double> runList = new ArrayList<Double>();
- 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<Integer> 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<Particle> initializeParticles(int j) {
- List<Particle> swarm = new ArrayList<Particle>();
- //Create The Particle
- for (int particleNumber = 0; particleNumber < swarmSize; particleNumber++){
- //Create a Random position
- List<Boolean> aRandomPosition = new ArrayList<Boolean>();
- 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<Particle> 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):v<sub>i,j</sub>(t + 1) = wv<sub>i,j</sub>+c<sub>1</sub>R<sub>1</sub>(P<sub>best,i,j</sub>-x<sub>p,i,j</sub>(t))+c<sub>2</sub>R<sub>2</sub>(g<sub>best,i,j</sub>-x<sub>p,i,j</sub>(t))<br>
- * @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):x<sub>g,i,j</sub>(t + 1) = x<sub>g,i,j</sub>(t) + v<sub>i,j</sub>(t + 1)<br>
- * @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):<b>if(</b>rand()<r<sub>mu</sub><b>)then</b> x<sub>g,i,j</sub>(t + 1) = -x<sub>g,i,j</sub>(t + 1)<br>
- * @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):x<sub>p,i,j</sub>(t + 1) = <b>(</b>rand() < S(x<sub>g,i,j</sub>(t + 1))<b>) ?</b> 1 <b>:</b> 0<br>
- * @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(x<sub>g,i,j</sub>(t + 1)) := 1/(1 + e<sup>-x<sub>g,i,j</sub>(t + 1)</sup>)<br></font>
- * @param value
- * @return
- */
- private double Sigmoid(double value) {
- return 1.0 / (1.0 + Math.exp(-value));
- }
- /**
- * To clamp X<sub>g,j,i</sub> and v<sub>i,j</sub> in Range [-X<sub>g,max</sub>|+X<sub>g,max</sub>] with {X<sub>g,max</sub>= 4}
- * @param value
- * @return
- */
- private double clamp(double value) {
- return Math.max(-maxVelocity, Math.min(maxVelocity, value));
- }
- private TreeSet<Integer> locationsToMutate(int dimensions) {
- TreeSet<Integer> mutationLocation = new TreeSet<Integer>(); //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<Double> velocity;
- /**
- * The positions genotype.
- */
- public List<Double> xGenotype;
- /**
- * The positions phenotype. Alias the current position.
- */
- public List<Boolean> xPhenotype;
-
- public Individual localBest;
-
- Particle(List<Boolean> 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 <Type> String listToString(List<Type> list) {
- return list.stream().map(Object::toString).collect(Collectors.joining(", "));
- }
-
- }
- @Override
- protected String plottFileName() {
- return "plottPsoAlgo.txt";
- }
-
-
-
-
-
- }
|