123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210 |
- package algorithm.binary;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.ListIterator;
- import javax.swing.JFrame;
- import api.AlgorithmFrameworkFlex;
- import utility.StringFormat;
- public class AcoAlgorithm extends AlgorithmFrameworkFlex{
-
- //Parameter for Algo with default Values:
- /**
- * Should be even.
- */
- private int popsize = 20;
- private int maxGenerations = 200;
- /**
- * The vaporization factor;
- */
- private double p = 0.3;
- private double convergenceFactorReset = 0.99;
- private boolean moreInformation = false;
-
-
-
- public AcoAlgorithm() {
- super();
- addIntParameter("Population", popsize, intValue -> popsize = intValue, () -> popsize, 1);
- addIntParameter("maxGenerations", maxGenerations, intValue -> maxGenerations = intValue, () -> maxGenerations, 1);
- addDoubleParameter("Vaporization", p, doubleValue -> p = doubleValue, () -> p, 0.0, 1.0);
- addDoubleParameter("FactorReset", convergenceFactorReset, doubleValue -> convergenceFactorReset = doubleValue, () -> convergenceFactorReset, 0.0, 1.0);
- addBooleanParameter("moreInformation", moreInformation, booleanValue -> moreInformation = booleanValue);
- }
-
-
-
- public static void main(String[] args)
- {
- JFrame newFrame = new JFrame("exampleWindow");
- AcoAlgorithm instance = new AcoAlgorithm();
- newFrame.setContentPane(instance.getPanel());
- newFrame.pack();
- newFrame.setVisible(true);
- newFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
- }
-
- @Override
- protected int getProgressBarMaxCount() {
- return rounds * popsize * maxGenerations;
- }
-
-
- /**
- * Algorithm 20 !! Fitness is better when smaller.:
- * PseudoCode:
- * Best <- actual;
- * pheromones = initPheromons();
- * for(maxGeneration times){
- * population = createSolutionsBiasedBy(pheromones);
- * for(each Individual i from population){
- * fitness <- evaluatePosition(i);
- * if(fitness < best.fitnessValue) Best <- i;
- * }
- * vaporizeIntensifiePheromons(pheromones);
- * }
- * @return
- */
- @Override
- protected Individual executeAlgo() {
- Individual best = new Individual();
- best.position = extractPositionAndAccess();
- if(moreInformation )console.println("Bit-Array_length: " + best.position.size());
- best.fitness = evaluatePosition(best.position);
- List<Double> runList = new ArrayList<Double>();
- runList.add(best.fitness);
- console.print("Start with: " + StringFormat.doubleFixedPlaces(2, best.fitness));
- if(moreInformation)console.println("");
- int problemSize = best.position.size();
- if(problemSize == 0) return best;
- List<Double> pheromones = initPheromones(problemSize);
- List<Individual> population = new ArrayList<Individual>();
- if(moreInformation)console.println("Size To Test:" + population.size());
- for(int generation = 0; generation< maxGenerations; generation++) {
- population.clear();
- population = constructSolutionsBiasedBy(pheromones);
- if(moreInformation)console.println("Generation" + generation + " start with Fitness: " + best.fitness);
- for(Individual i : population) {
- i.fitness = evaluatePosition(i.position);
- if(moreInformation)console.println("Fitness" + StringFormat.doubleFixedPlaces(2, i.fitness));
- if(i.fitness < best.fitness) best = i;
- }
- runList.add(best.fitness);
- if(moreInformation)console.println("________________");
- vaporizeIntensifiePheromons(pheromones, best.position, problemSize);
- double cf = calculateConvergenceFactor(pheromones, problemSize);
- if(moreInformation)console.println("ConvergenceFactor = " + cf);
- if(cf > this.convergenceFactorReset) {
- pheromones = initPheromones(problemSize);
- }
- if(cancel)return null;
- }
-
-
- console.println(" End With:" + StringFormat.doubleFixedPlaces(2, best.fitness));
- this.runList = runList;
- return best;
-
- }
-
-
- /**
- * tj1 is the pheromon level in the j position
- * cf is the convergence factor cf e [0;1]
- * difference = | tj1 - tj0 | = | tj1 - (1 - tj1) |
- *
- *
- *
- * @param pheromones
- * @return cf
- */
- private double calculateConvergenceFactor(List<Double> pheromones,int problemSize) {
- double sumOfDifference = pheromones.stream().map(tj1 -> Math.abs(tj1 - (1.0 - tj1))).reduce(0.0, Double::sum);
- double cf = sumOfDifference / (double)problemSize;
- return cf;
- }
- /**
- * pheromone <- (1-p) * pheromone;
- * if(best is true at this position) pheromone <- pheromone + p;
- * @param pheromones
- * @param position
- */
- private void vaporizeIntensifiePheromons(List<Double> pheromones, List<Boolean> position, int problemSize) {
- ListIterator<Double> iterPheromone = pheromones.listIterator();
- ListIterator<Boolean> iterBest = position.listIterator();
- for(int i = 0; i < problemSize; i++) {
- double pheromone = iterPheromone.next();
- boolean bestDecision = iterBest.next();
- iterPheromone.set((1.0 - p) * pheromone + (bestDecision?p:0.0));
- }
- }
- /**
- *
- * @param pheromones
- * @return
- */
- private List<Individual> constructSolutionsBiasedBy(List<Double> pheromones) {
- List<Individual> population = new ArrayList<Individual>();
- for(int i = 0; i < popsize; i++) {
- population.add(constructASolutionBiasedBy(pheromones));
- }
- return population;
- }
-
-
- /**
- * Walks the path with a ant and decide by pheromones if should take true or false;
- * A pheromone have a level of 0 < pheromone < 1.
- * A Pheromone is equal to the probability.
- * @param pheromones
- * @return
- */
- private Individual constructASolutionBiasedBy(List<Double> pheromones) {
- Individual result = new Individual();
- result.position = new ArrayList<Boolean>();
- for(double pheromone : pheromones) {
- result.position.add((Random.nextDouble() < pheromone));
- }
- return result;
- }
- /**
- * Initialize Pheromons with 0.5
- */
- private List<Double> initPheromones(int problemSize) {
- List<Double> result = new ArrayList<Double>();
- for(int i = 0; i < problemSize;i++) {
- result.add(0.5);
- }
- return result;
- }
- @Override
- protected String algoInformationToPrint() {
- // private int popsize = 20;
- // private int maxGenerations = 200;
- // private double p = 0.3;
- // private double convergenceFactorReset = 0.99;
- return "AcoAlgo"
- + " Rounds: " + rounds
- + " Iterations: " + maxGenerations
- + " Individuals: " + popsize
- + " vaporization: " + StringFormat.doubleAllPlaces(p)
- + " convergenceFactorReset: " + StringFormat.doubleAllPlaces(convergenceFactorReset);
- }
- @Override
- protected String plottFileName() {
- return "plottAcoAlgo.txt";
- }
-
- }
|