123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181 |
- package algorithm.topologie;
- import java.util.ArrayList;
- import java.util.List;
- import java.util.ListIterator;
- import java.util.TreeSet;
- import java.util.stream.Collectors;
- import algorithm.objectiveFunction.ObjectiveFunctionByCarlos;
- import algorithm.objectiveFunction.TopologieObjectiveFunction;
- import api.TopologieAlgorithmFramework;
- import api.AlgorithmFrameworkFlex.Individual;
- import ui.model.DecoratedState;
- public class AcoAlgorithm extends TopologieAlgorithmFramework {
- private int popsize = 20;
- private int maxGenerations = 100;
- private boolean moreInformation = false;
- /**
- * The vaporization factor;
- */
- private double p = 0.05;
- private double convergenceFactorReset = 0.90;
-
- public AcoAlgorithm(){
- addIntParameter("popsize", 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);
- }
- @Override
- protected double evaluateState(DecoratedState actualstate) {
- return TopologieObjectiveFunction.getFitnessValueForState(actualstate);
- }
- @Override
- protected Individual executeAlgo() {
- resetWildcards();
- Individual best = new Individual();
- best.position = extractPositionAndAccess();
- int problemSize = best.position.size();
- best.fitness = evaluatePosition(best.position);
- List<Double> runList = new ArrayList<Double>();
- runList.add(best.fitness);
- console.println("Integer_Array_length: " + best.position.size());
- List<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" + 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(moreInformation)console.println("pheromones:" + pheromones);
- if(cf > this.convergenceFactorReset) {
- pheromones = initPheromones(problemSize);
- }
- if(cancel)return null;
- }
- console.println(" End with:" + best.fitness);
- this.runList = runList;
- return best;
- }
- @Override
- protected int getProgressBarMaxCount() {
- return rounds * maxGenerations * popsize + 1;
- }
- @Override
- protected String algoInformationToPrint() {
- return "GA for topologie generation";
- }
- @Override
- protected String plottFileName() {
- return "ga-topologie.txt";
- }
- /**
- * tj1 is the pheromon level in the j position
- * cf is the convergence factor cf e [0;1]
- *
- *
- *
- * @param pheromones
- * @return cf
- */
- private double calculateConvergenceFactor(List<List<Double>> pheromones,int problemSize) {
- double sumofmax = pheromones.stream().map(listPheromons -> listPheromons.stream().max((a,b) -> Double.compare(a,b)).get()).reduce(0.0, Double::sum);
- double cf = sumofmax / (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<List<Double>> pheromones, List<Integer> position, int problemSize) {
- ListIterator<List<Double>> iterPheromone = pheromones.listIterator();
- ListIterator<Integer> iterBest = position.listIterator();
- for(int i = 0; i < problemSize; i++) {
- List<Double> tauList = iterPheromone.next();
- int bestDecision = iterBest.next();
- ListIterator<Double> tauListiter = tauList.listIterator();
- for(int k = 0; tauListiter.hasNext(); k++) {
- double value = tauListiter.next();
- tauListiter.set((1.0 - p) * value + (k == bestDecision?p:0.0));
- }
- }
- }
- /**
- *
- * @param pheromones
- * @return
- */
- private List<Individual> constructSolutionsBiasedBy(List<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<List<Double>> pheromones) {
- Individual result = new Individual();
- result.position = new ArrayList<Integer>();
- for(List<Double> pheromoneList : pheromones) {
- ListIterator<Double> tauListiter = pheromoneList.listIterator();
- double radnomValue = Random.nextDouble();
- for(int i = 0;tauListiter.hasNext(); i++) {
- double actualtau = tauListiter.next();
- if(radnomValue > actualtau) {
- radnomValue -= actualtau;
- }else {
- result.position.add(i);
- break;
- }
- }
- }
- return result;
- }
- /**
- * Initialize Pheromons with 1.0 / maxIndex;
- */
- private List<List<Double>> initPheromones(int problemSize) {
- List<List<Double>> result = new ArrayList<List<Double>>();
- for(int i = 0; i < problemSize;i++) {
- //generate list equal tau values with max Int
- int maxIndex = this.getMaximumIndexObjects(i);
- double tauValue = 1.0 / (double) (maxIndex + 1);
- List<Double> tauList = new ArrayList<Double>();
- for(int tau= 0; tau < maxIndex + 1; tau++) {
- tauList.add(tauValue);
- }
- result.add(tauList);
- }
- return result;
- }
- }
-
|