123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- package holeg.algorithm.binary;
- import holeg.api.AlgorithmFrameworkFlex;
- import holeg.utility.math.decimal.Format;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.ListIterator;
- import javax.swing.JFrame;
- 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 size", popsize, intValue -> popsize = intValue, () -> popsize, 1);
- addIntParameter("Generations", maxGenerations, intValue -> maxGenerations = intValue,
- () -> maxGenerations, 1);
- addDoubleParameter("Vaporization rate", p, doubleValue -> p = doubleValue, () -> p, 0.0, 1.0);
- addDoubleParameter("Convergence factor threshold", convergenceFactorReset,
- doubleValue -> convergenceFactorReset = doubleValue, () -> convergenceFactorReset, 0.0,
- 1.0);
- addBooleanParameter("Detailed information", 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: " + Format.doubleFixedPlaces(2, best.fitness));
- if (moreInformation) {
- console.println("");
- }
- if (best.position.isEmpty()) {
- return best;
- }
- int problemSize = best.position.size();
- 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" + Format.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:" + Format.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: " + Format.doubleAllPlaces(p)
- + " convergenceFactorReset: " + Format.doubleAllPlaces(convergenceFactorReset);
- }
- @Override
- protected String plottFileName() {
- return "plottAcoAlgo.txt";
- }
- }
|