001/******************************************************************************* 002 * Copyright (c) 2016 Pablo Pavon Mariņo. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the GNU Lesser Public License v2.1 005 * which accompanies this distribution, and is available at 006 * http://www.gnu.org/licenses/lgpl.html 007 ******************************************************************************/ 008package com.net2plan.examples.ocnbook.offline; 009 010 011 012import java.io.File; 013import java.util.ArrayList; 014import java.util.Arrays; 015import java.util.Collections; 016import java.util.LinkedList; 017import java.util.List; 018import java.util.Map; 019import java.util.Random; 020 021import cern.colt.matrix.tdouble.DoubleFactory1D; 022import cern.colt.matrix.tdouble.DoubleMatrix1D; 023 024import com.net2plan.interfaces.networkDesign.IAlgorithm; 025import com.net2plan.interfaces.networkDesign.Link; 026import com.net2plan.interfaces.networkDesign.Net2PlanException; 027import com.net2plan.interfaces.networkDesign.NetPlan; 028import com.net2plan.libraries.IPUtils; 029import com.net2plan.utils.Constants.OrderingType; 030import com.net2plan.utils.Constants.RoutingType; 031import com.net2plan.utils.Constants.SearchType; 032import com.net2plan.utils.DoubleUtils; 033import com.net2plan.utils.InputParameter; 034import com.net2plan.utils.Pair; 035import com.net2plan.utils.TimeTrace; 036import com.net2plan.utils.Triple; 037 038/** 039 * Searches for the OSPF link weights that minimize a measure of congestion, using an evolutionary algorithm (genetic algorithm) heuristic 040 * 041 * The time evolution of different metrics can be stored in output files, for later processing. 042 * As an example, see the <a href="../../../../../../graphGeneratorFiles/fig_sec12_9_ospfWeightEA.m">{@code fig_sec12_9_ospfWeightEA.m}</a> MATLAB file used for generating the graph/s of the case study in the 043 * <a href="http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html">book</a> using this algorithm. 044 * @net2plan.description 045 * @net2plan.keywords IP/OSPF, Flow assignment (FA), Evolutionary algorithm (EA) 046 * @net2plan.ocnbooksections Section 12.9 047 * @net2plan.inputParameters 048 * @author Pablo Pavon-Marino 049 */ 050public class Offline_fa_ospfWeightOptimization_EA implements IAlgorithm 051{ 052 private OSPFHeuristicUtils ospfEngine; 053 private NetPlan netPlan; 054 private List<DoubleMatrix1D> population; 055 private double[] costs; 056 057 private TimeTrace stat_objFunction; 058 private TimeTrace stat_avEntropy; 059 private int E; 060 061 private InputParameter ospf_maxLinkWeight = new InputParameter ("ospf_maxLinkWeight", (int) 16 , "OSPF link weights are constrained to be integers between 1 and this parameter" , 1 , Integer.MAX_VALUE); 062 private InputParameter algorithm_randomSeed = new InputParameter ("algorithm_randomSeed", (long) 1 , "Seed of the random number generator"); 063 private InputParameter algorithm_outputFileNameRoot = new InputParameter ("algorithm_outputFileNameRoot", "ospfWeghtOptimization_ea" , "Root of the file name to be used in the output files. If blank, no output"); 064 private InputParameter ospf_weightOfMaxUtilizationInObjectiveFunction = new InputParameter ("ospf_weightOfMaxUtilizationInObjectiveFunction", (double) 0.9 , "Objective function is this factor multiplied by maximum link utilization, plus 1 minus this factor by average link utilization" , 0 , true , 1 , true); 065 private InputParameter algorithm_maxExecutionTimeInSeconds = new InputParameter ("algorithm_maxExecutionTimeInSeconds", (double) 300 , "Algorithm maximum running time in seconds" , 0 , false , Double.MAX_VALUE , true); 066 private InputParameter ea_maxNumIterations = new InputParameter ("ea_maxNumIterations", (int) 100 , "Maximum number of iterations" , 1 , Integer.MAX_VALUE); 067 private InputParameter ea_populationSize = new InputParameter ("ea_populationSize", (int) 1000 , "Number of elements in the population" , 1 , Integer.MAX_VALUE); 068 private InputParameter ea_offSpringSize = new InputParameter ("ea_offSpringSize", (int) 200 , "Number of childs in the offspring every generation" , 1 , Integer.MAX_VALUE); 069 private InputParameter ea_fractionParentsChosenRandomly = new InputParameter ("ea_fractionParentsChosenRandomly", (double) 0.1 , "Fraction of the parents that are selected randomly for creating the offspring" , 0 , true , 1 , true); 070 071 @Override 072 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 073 { 074 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 075 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 076 077 /* Basic checks */ 078 final int N = netPlan.getNumberOfNodes(); 079 this.E = netPlan.getNumberOfLinks(); 080 if (N == 0) throw new Net2PlanException("The input design must have nodes"); 081 netPlan.removeAllUnicastRoutingInformation(); 082 netPlan.setRoutingType (RoutingType.HOP_BY_HOP_ROUTING); 083 084 /* Initialize some variables */ 085 if (ea_offSpringSize.getInt () > ea_populationSize.getInt () / 2.0) throw new Net2PlanException("The offspring size cannot exceed the population size divided by two"); 086 087 088 Random rng = new Random (algorithm_randomSeed.getLong()); 089 this.netPlan = netPlan; 090 this.E = netPlan.getNumberOfLinks(); 091 this.ospfEngine = new OSPFHeuristicUtils(netPlan, ospf_maxLinkWeight.getInt (), ospf_weightOfMaxUtilizationInObjectiveFunction.getDouble(), rng); 092 final long algorithmInitialtime = System.nanoTime(); 093 final long algorithmEndtime = algorithmInitialtime + (long) (algorithm_maxExecutionTimeInSeconds.getDouble() * 1E9); 094 095 this.stat_objFunction = new TimeTrace (); 096 this.stat_avEntropy = new TimeTrace(); 097 098 DoubleMatrix1D bestSol = null; 099 double bestObjFunction = Double.MAX_VALUE; 100 101 /* Generate the initial population */ 102 generateInitialSolutions(ea_populationSize.getInt ()); 103 104 /* Update the best solution found so far */ 105 final int bestSolutionId = DoubleUtils.maxIndexes(costs, SearchType.FIRST)[0]; 106 bestObjFunction = costs[bestSolutionId]; 107 bestSol = population.get(bestSolutionId).copy (); 108 System.out.println("Initial population. Best solution cost: " + bestObjFunction); 109 110 /* Evolve: one iteration per generation */ 111 int iterationCounter = 0; 112 while ((System.nanoTime() < algorithmEndtime) && (iterationCounter < ea_maxNumIterations.getInt ())) 113 { 114 LinkedList<Integer> parents = operator_parentSelection(ea_offSpringSize.getInt () , ea_fractionParentsChosenRandomly.getDouble () , rng); 115 List<DoubleMatrix1D> offspring = operator_crossover(parents , rng); 116 this.operator_mutate(offspring , rng , ospf_maxLinkWeight.getInt ()); 117 int indexBestSolution = this.operator_select(offspring); 118 if (costs[indexBestSolution] < bestObjFunction) 119 { 120 bestObjFunction = costs[indexBestSolution]; 121 bestSol = this.population.get(indexBestSolution).copy (); 122 } 123 124 //System.out.println("Iteration: " + iterationCounter + ". Best solution cost: " + bestObjFunction); 125 126 final double runningTimeSecs = (System.nanoTime() - algorithmInitialtime) * 1E-9; 127 stat_objFunction.add (runningTimeSecs , costs); 128 stat_avEntropy.add (runningTimeSecs , computeAverageEntropy ()); 129 iterationCounter++; 130 } 131 132 /* Save the best solution found into the netPlan object */ 133 IPUtils.setECMPForwardingRulesFromLinkWeights(netPlan, bestSol); 134 135 stat_objFunction.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_cong.txt")); 136 stat_avEntropy.printToFile(new File (algorithm_outputFileNameRoot.getString () + "_entropy.txt")); 137 138 System.out.println("Ok! Best solution OF: " + bestObjFunction + ", number generations: " + iterationCounter); 139 return "Ok! Best solution OF: " + bestObjFunction + ", number generations: " + iterationCounter; 140 } 141 142 @Override 143 public String getDescription() 144 { 145 return "Given a set of nodes, links and offered traffic, this algorithm assumes that the nodes are IP routers running the OSPF protocol (applying ECMP rules) for routing it. The algorithm searches for the set of link weights that optimize the routing. In particular, the target is minimizing a congestion metric computed as a function of both the worst-case link utilization and the average link utilization. The algorithm is based on applying an evolutionary algorithm (EA) or genetic algorithm heuristic approach."; 146 } 147 148 @Override 149 public List<Triple<String, String, String>> getParameters() 150 { 151 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 152 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 153 } 154 155 private void generateInitialSolutions(int ea_populationSize) 156 { 157 population = new ArrayList<DoubleMatrix1D>(ea_populationSize); 158 costs = new double[ea_populationSize]; 159 160 for (int cont = 0; cont < ea_populationSize; cont++) 161 { 162 Pair<DoubleMatrix1D,Double> p = ospfEngine.getInitialSolution ("random"); 163 population.add(p.getFirst()); 164 costs[cont] = p.getSecond(); 165 } 166 } 167 168 private LinkedList<Integer> operator_parentSelection(int ea_offspringSize , double ea_fractionChosenRandomly , Random rng) 169 { 170 final int numParentsToChoose = 2 * ea_offspringSize; 171 final int numParentsChosenRandomly = (int) Math.floor(numParentsToChoose * ea_fractionChosenRandomly); 172 final int numParentsChosenFromCost = numParentsToChoose - numParentsChosenRandomly; 173 174 /* Initialize the list to be returned */ 175 LinkedList<Integer> chosenParents = new LinkedList<Integer>(); 176 177 int [] sortedPopulationIds = DoubleUtils.sortIndexes(costs, OrderingType.ASCENDING); 178 179 /* Choose the best solutions as parents: as many as numParentsChosenFromCost */ 180 for (int cont = 0; cont < numParentsChosenFromCost; cont++) 181 chosenParents.add(sortedPopulationIds [cont]); 182 183 /* The rest of the parents (numParentsChosenRandomly) are chosen randomly among all. Parents can be repeated */ 184 for (int cont = 0; cont < numParentsChosenRandomly; cont++) 185 chosenParents.add(rng.nextInt(this.population.size())); 186 187 return chosenParents; 188 } 189 190 private List<DoubleMatrix1D> operator_crossover(LinkedList<Integer> parents , Random rng) 191 { 192 /* The offspring to be returned */ 193 List<DoubleMatrix1D> offspring = new ArrayList<DoubleMatrix1D>(parents.size() / 2); 194 195 /* Shuffle randomly the parent selection. Then, couples are formed randomly */ 196 Collections.shuffle(parents); 197 198 /* Two consecutive parents are a couple */ 199 while (parents.size() >= 2) 200 { 201 final int firstParentId = parents.poll(); 202 final int secondParentId = parents.poll(); 203 204 final DoubleMatrix1D firstParent = population.get(firstParentId); 205 final DoubleMatrix1D secondParent = population.get(secondParentId); 206 207 /* The descendant chooses randomly for each link, the link weight from any of the two parents */ 208 final DoubleMatrix1D descendant = DoubleFactory1D.dense.make (E); 209 for (Link link : netPlan.getLinks ()) descendant.set(link.getIndex (), rng.nextBoolean() ? firstParent.get(link.getIndex ()) : secondParent.get(link.getIndex ())); 210 offspring.add(descendant); 211 } 212 213 return offspring; 214 } 215 216 private void operator_mutate(List<DoubleMatrix1D> offspring , Random rng , int maxLinkWeight) 217 { 218 for (DoubleMatrix1D solution : offspring) 219 { 220 final int e = rng.nextInt(netPlan.getNumberOfLinks()); 221 solution.set(e, 1.0 + rng.nextInt(maxLinkWeight)); 222 } 223 } 224 225 private int operator_select(List<DoubleMatrix1D> offspring) 226 { 227 /* Compute the costs of the offspring */ 228 final int ea_populationSize = costs.length; 229 double [] combinedCosts = Arrays.copyOf(costs, ea_populationSize + offspring.size()); 230 population.addAll(offspring); 231 int counter = ea_populationSize; 232 for (DoubleMatrix1D descendant : offspring) 233 combinedCosts[counter ++] = ospfEngine.computeObjectiveFunction(descendant).getFirst(); 234 235 int [] sortedPopulationIds = DoubleUtils.sortIndexes(combinedCosts, OrderingType.ASCENDING); 236 237 this.costs = new double [ea_populationSize]; 238 ArrayList<DoubleMatrix1D> newPopulation = new ArrayList<DoubleMatrix1D>(ea_populationSize); 239 for (int cont = 0 ; cont < ea_populationSize ; cont ++) 240 { 241 final int indexInCombinedOffspringAndPopulation = sortedPopulationIds[cont]; 242 costs [cont] = combinedCosts [indexInCombinedOffspringAndPopulation]; 243 newPopulation.add(population.get(indexInCombinedOffspringAndPopulation)); 244 } 245 this.population = newPopulation; 246 return 0; // return the best solution 247 } 248 249 250 private double computeAverageEntropy () 251 { 252 double freq_ew [][] = new double [E][ospf_maxLinkWeight.getInt ()]; // number of occurrencies 253 double sum_e [] = new double [E]; // sum of occurrencies per link 254 //private List<Map<Long, Double>> population; 255 for (DoubleMatrix1D sol : population) 256 { 257 for (Link e : netPlan.getLinks ()) 258 { 259 final int eIndex = e.getIndex (); 260 final int w = (int) sol.get(eIndex) - 1; 261 freq_ew [eIndex][w] ++; 262 sum_e [eIndex] ++; 263 } 264 } 265 final double convLogFactor = 1 / Math.log(2); 266 double avEntropy = 0; 267 for (int eIndex = 0 ; eIndex < E ; eIndex ++) 268 { 269 double entropy_e = 0; 270 for (int w = 0 ; w < ospf_maxLinkWeight.getInt () ; w ++) 271 { 272 if (sum_e [eIndex] > 0) { final double val = freq_ew [eIndex][w] / sum_e [eIndex]; entropy_e -= (val == 0)? 0 : val * Math.log(val) * convLogFactor; } 273 } 274 avEntropy += entropy_e; 275 } 276 return avEntropy / E; 277 } 278}