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}