Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ichiriac/HeuristicLab.Algorithms.GDE3/GDE3.cs @ 14736

Last change on this file since 14736 was 14705, checked in by gkronber, 8 years ago

#2646: changes to GDE3 and svn:ignore props

File size: 26.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * Implementation based on the GDE3 implementation in jMetal Framework https://github.com/jMetal/jMetal
8 *
9 * HeuristicLab is free software: you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, either version 3 of the License, or
12 * (at your option) any later version.
13 *
14 * HeuristicLab is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
21 */
22#endregion
23using System;
24using System.Linq;
25using System.Collections.Generic;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.RealVectorEncoding;
31using HeuristicLab.Operators;
32using HeuristicLab.Optimization;
33using HeuristicLab.Optimization.Operators;
34using HeuristicLab.Parameters;
35using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
36using HeuristicLab.PluginInfrastructure;
37using HeuristicLab.Problems.MultiObjectiveTestFunctions;
38using HeuristicLab.Random;
39using System.Threading;
40using HeuristicLab.Algorithms.GDE3;
41
42namespace HeuristicLab.Algoritms.GDE3 {
43
44  [Item("Generalized Differential Evolution (GDE3)", "A generalized differential evolution algorithm.")]
45  [StorableClass]
46  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
47  public class GDE3 : BasicAlgorithm {
48    public override Type ProblemType {
49      get { return typeof(MultiObjectiveBasicProblem<RealVectorEncoding>); }
50    }
51    public new MultiObjectiveTestFunctionProblem Problem {
52      get { return (MultiObjectiveTestFunctionProblem)base.Problem; }
53      set { base.Problem = value; }
54    }
55
56    public ILookupParameter<DoubleMatrix> BestKnownFrontParameter {
57      get {
58        return (ILookupParameter<DoubleMatrix>)Parameters["BestKnownFront"];
59      }
60    }
61
62    private readonly IRandom _random = new MersenneTwister();
63    private int evals;
64    private double IGDSumm;
65
66    #region ParameterNames
67    private const string MaximumGenerationsParameterName = "Maximum Generations";
68    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
69    private const string CrossoverProbabilityParameterName = "CrossoverProbability";
70    private const string PopulationSizeParameterName = "PopulationSize";
71    private const string ScalingFactorParameterName = "ScalingFactor";
72
73    #endregion
74
75    #region ParameterProperties
76    public IFixedValueParameter<IntValue> MaximumGenerationsParameter {
77      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
78    }
79    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
80      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
81    }
82    private ValueParameter<IntValue> PopulationSizeParameter {
83      get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
84    }
85    public ValueParameter<DoubleValue> CrossoverProbabilityParameter {
86      get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }
87    }
88    public ValueParameter<DoubleValue> ScalingFactorParameter {
89      get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
90    }
91    #endregion
92
93    #region Properties
94    public int MaximumGenerations {
95      get { return MaximumGenerationsParameter.Value.Value; }
96      set { MaximumGenerationsParameter.Value.Value = value; }
97    }
98
99    public int MaximumEvaluations {
100      get { return MaximumEvaluationsParameter.Value.Value; }
101      set { MaximumEvaluationsParameter.Value.Value = value; }
102    }
103
104    public Double CrossoverProbability {
105      get { return CrossoverProbabilityParameter.Value.Value; }
106      set { CrossoverProbabilityParameter.Value.Value = value; }
107    }
108    public Double ScalingFactor {
109      get { return ScalingFactorParameter.Value.Value; }
110      set { ScalingFactorParameter.Value.Value = value; }
111    }
112    public IntValue PopulationSize {
113      get { return PopulationSizeParameter.Value; }
114      set { PopulationSizeParameter.Value = value; }
115    }
116    #endregion
117
118    #region ResultsProperties
119    private double ResultsBestQuality {
120      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
121      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
122    }
123
124    private double ResultsIGDMean {
125      get { return ((DoubleValue)Results["IGDMeanValue"].Value).Value; }
126      set { ((DoubleValue)Results["IGDMeanValue"].Value).Value = value; }
127    }
128
129    private double ResultsIGDBest {
130      get { return ((DoubleValue)Results["IGDBestValue"].Value).Value; }
131      set { ((DoubleValue)Results["IGDBestValue"].Value).Value = value; }
132    }
133
134    private double ResultsIGDWorst {
135      get { return ((DoubleValue)Results["IGDWorstValue"].Value).Value; }
136      set { ((DoubleValue)Results["IGDWorstValue"].Value).Value = value; }
137    }
138
139    private double ResultsInvertedGenerationalDistance {
140      get { return ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value; }
141      set { ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value = value; }
142    }
143
144    private double ResultsHypervolume {
145      get { return ((DoubleValue)Results["HyperVolumeValue"].Value).Value; }
146      set { ((DoubleValue)Results["HyperVolumeValue"].Value).Value = value; }
147    }
148
149    private DoubleMatrix ResultsBestFront {
150      get { return (DoubleMatrix)Results["Best Front"].Value; }
151      set { Results["Best Front"].Value = value; }
152    }
153
154    private int ResultsEvaluations {
155      get { return ((IntValue)Results["Evaluations"].Value).Value; }
156      set { ((IntValue)Results["Evaluations"].Value).Value = value; }
157    }
158    private int ResultsGenerations {
159      get { return ((IntValue)Results["Generations"].Value).Value; }
160      set { ((IntValue)Results["Generations"].Value).Value = value; }
161    }
162    private double ResultsGenerationalDistance {
163      get { return ((DoubleValue)Results["GenerationalDistance"].Value).Value; }
164      set { ((DoubleValue)Results["GenerationalDistance"].Value).Value = value; }
165    }
166
167    private double ResultsSpacing {
168      get { return ((DoubleValue)Results["Spacing"].Value).Value; }
169      set { ((DoubleValue)Results["Spacing"].Value).Value = value; }
170    }
171
172    private double ResultsCrowding {
173      get { return ((DoubleValue)Results["Crowding"].Value).Value; }
174      set { ((DoubleValue)Results["Crowding"].Value).Value = value; }
175    }
176
177    #endregion
178
179    [StorableConstructor]
180    protected GDE3(bool deserializing) : base(deserializing) { }
181
182    protected GDE3(GDE3 original, Cloner cloner)
183      : base(original, cloner) {
184    }
185
186    public override IDeepCloneable Clone(Cloner cloner) {
187      return new GDE3(this, cloner);
188    }
189
190    public GDE3() {
191      Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsParameterName, "", new IntValue(1000)));
192      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
193      Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
194      Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.5)));
195      Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.5)));
196      Parameters.Add(new LookupParameter<DoubleMatrix>("BestKnownFront", "The currently best known Pareto front"));
197    }
198
199    protected override void Run(CancellationToken cancellationToken) {
200      // Set up the results display
201      Results.Add(new Result("Generations", new IntValue(0)));
202      Results.Add(new Result("Evaluations", new IntValue(0)));
203      Results.Add(new Result("Best Front", new DoubleMatrix()));
204      Results.Add(new Result("Crowding", new DoubleValue(0)));
205      Results.Add(new Result("InvertedGenerationalDistance", new DoubleValue(0)));
206      Results.Add(new Result("GenerationalDistance", new DoubleValue(0)));
207      Results.Add(new Result("HyperVolumeValue", new DoubleValue(0)));
208      Results.Add(new Result("IGDMeanValue", new DoubleValue(0)));
209      Results.Add(new Result("IGDBestValue", new DoubleValue(Int32.MaxValue)));
210      Results.Add(new Result("IGDWorstValue", new DoubleValue(0)));
211
212      Results.Add(new Result("Spacing", new DoubleValue(0)));
213      Results.Add(new Result("Scatterplot", typeof(IMOFrontModel)));
214      var table = new DataTable("Qualities");
215      table.Rows.Add(new DataRow("Best Quality"));
216      Results.Add(new Result("Qualities", table));
217
218      //setup the variables
219      List<SolutionSet> population;
220      List<SolutionSet> offspringPopulation;
221      SolutionSet[] parent;
222      double IGDSumm = 0;
223
224      //initialize population
225      population = new List<SolutionSet>(PopulationSizeParameter.Value.Value);
226
227      for(int i = 0; i < PopulationSizeParameter.Value.Value; ++i) {
228        var m = createIndividual();
229        m.Quality = Problem.Evaluate(m.Population, _random);
230        //the test function is constrained
231        if(m.Quality.Length > Problem.Objectives) {
232          m.OverallConstrainViolation = m.Quality[Problem.Objectives];
233        } else {
234          m.OverallConstrainViolation = 0;
235        }
236        population.Add(m);
237      }
238
239      this.initProgress();
240      int generations = 1;
241
242      while(ResultsEvaluations < MaximumEvaluationsParameter.Value.Value
243         && !cancellationToken.IsCancellationRequested) {
244        var populationSize = PopulationSizeParameter.Value.Value;
245
246        // Create the offSpring solutionSet
247        offspringPopulation = new List<SolutionSet>(PopulationSizeParameter.Value.Value * 2);
248
249        for(int i = 0; i < populationSize; i++) {
250          // Obtain parents. Two parameters are required: the population and the
251          //                 index of the current individual
252          parent = selection(population, i);
253
254          SolutionSet child;
255          // Crossover. The parameters are the current individual and the index of the array of parents
256          child = reproduction(population[i], parent);
257
258          child.Quality = Problem.Evaluate(child.Population, _random);
259
260          this.updateProgres();
261
262          //the test function is constrained
263          if(child.Quality.Length > Problem.Objectives) {
264            child.OverallConstrainViolation = child.Quality[Problem.Objectives];
265          } else {
266            child.OverallConstrainViolation = 0;
267          }
268
269          // Dominance test
270          int result;
271          result = compareDomination(population[i], child);
272
273          if(result == -1) { // Solution i dominates child
274            offspringPopulation.Add(population[i]);
275          } else if(result == 1) { // child dominates
276            offspringPopulation.Add(child);
277          } else { // the two solutions are non-dominated
278            offspringPopulation.Add(child);
279            offspringPopulation.Add(population[i]);
280          }
281        }
282
283        // Ranking the offspring population
284        List<SolutionSet>[] ranking = computeRanking(offspringPopulation);
285        population = crowdingDistanceSelection(ranking);
286        generations++;
287        ResultsGenerations = generations;
288        displayResults(population);
289      }
290    }
291
292    public override bool SupportsPause { get { return false; } } // XXX does it actually support pause?
293
294    private void displayResults(List<SolutionSet> population) {
295      List<SolutionSet>[] rankingFinal = computeRanking(population);
296
297      int objectives = Problem.Objectives;
298      var optimalfront = Problem.TestFunction.OptimalParetoFront(objectives);
299
300      double[][] opf = new double[0][];
301      if(optimalfront != null) {
302        opf = optimalfront.Select(s => s.ToArray()).ToArray();
303      }
304
305      //compute the final qualities and population
306      double[][] qualitiesFinal = new double[rankingFinal[0].Count][];
307      double[][] populationFinal = new double[rankingFinal[0].Count][];
308
309      for(int i = 0; i < rankingFinal[0].Count; ++i) {
310        qualitiesFinal[i] = new double[Problem.Objectives];
311        populationFinal[i] = new double[Problem.Objectives];
312        for(int j = 0; j < Problem.Objectives; ++j) {
313          populationFinal[i][j] = rankingFinal[0][i].Population[j];
314          qualitiesFinal[i][j] = rankingFinal[0][i].Quality[j];
315        }
316      }
317      IEnumerable<double[]> en = qualitiesFinal;
318      IEnumerable<double[]> frontVectors = NonDominatedSelect.selectNonDominatedVectors(qualitiesFinal, Problem.TestFunction.Maximization(objectives), true);
319      //update the results
320
321      ResultsEvaluations = this.evals;
322      ResultsBestFront = new DoubleMatrix(MultiObjectiveTestFunctionProblem.To2D(qualitiesFinal));
323      ResultsCrowding = Crowding.Calculate(qualitiesFinal, Problem.TestFunction.Bounds(objectives));
324      GenerationalDistanceCalculator distance = new GenerationalDistanceCalculator();
325      ResultsInvertedGenerationalDistance = distance.CalculateGenerationalDistance(qualitiesFinal, opf, Problem.Objectives);
326      ResultsHypervolume = Hypervolume.Calculate(frontVectors, Problem.TestFunction.ReferencePoint(objectives), Problem.TestFunction.Maximization(objectives));
327      ResultsGenerationalDistance = GenerationalDistance.Calculate(qualitiesFinal, optimalfront, 1);
328      Results["Scatterplot"].Value = new MOSolution(qualitiesFinal, populationFinal, opf, objectives);
329      ResultsSpacing = Spacing.Calculate(qualitiesFinal);
330
331      if(ResultsIGDBest > ResultsInvertedGenerationalDistance) {
332        ResultsIGDBest = ResultsInvertedGenerationalDistance;
333      }
334      if(ResultsIGDWorst < ResultsInvertedGenerationalDistance) {
335        ResultsIGDWorst = ResultsInvertedGenerationalDistance;
336      }
337      this.IGDSumm += ResultsInvertedGenerationalDistance;
338      ResultsIGDMean = this.IGDSumm / ResultsGenerations;
339    }
340
341    private int getWorstIndex(List<SolutionSet> SolutionsList) {
342      int result = 0;
343
344      if((SolutionsList == null) || SolutionsList.Count == 0) {
345        result = 0;
346      } else {
347        SolutionSet worstKnown = SolutionsList[0],
348                    candidateSolution;
349        int flag;
350        for(int i = 1; i < SolutionsList.Count; i++) {
351          candidateSolution = SolutionsList[i];
352          flag = compareDomination(worstKnown, candidateSolution);
353          if(flag == -1) {
354            result = i;
355            worstKnown = candidateSolution;
356          }
357        }
358      }
359      return result;
360    }
361
362    private SolutionSet createIndividual() {
363      var dim = Problem.ProblemSize;
364      var lb = Problem.Bounds[0, 0];
365      var ub = Problem.Bounds[0, 1];
366      var range = ub - lb;
367      var v = new double[Problem.ProblemSize];
368      SolutionSet solutionObject = new SolutionSet(PopulationSizeParameter.Value.Value);
369
370      for(int i = 0; i < Problem.ProblemSize; ++i) {
371        v[i] = _random.NextDouble() * range + lb;
372
373      }
374      solutionObject.createSolution(v);
375      return solutionObject;
376    }
377
378    private SolutionSet createEmptyIndividual() {
379      SolutionSet solutionObject = new SolutionSet(PopulationSizeParameter.Value.Value);
380      var n = new RealVector(Problem.ProblemSize);
381      solutionObject.Population = n;
382      return solutionObject;
383    }
384
385    private void initProgress() {
386      this.evals = PopulationSizeParameter.Value.Value;
387    }
388
389    private void updateProgres() {
390      this.evals++;
391    }
392
393    private SolutionSet[] selection(List<SolutionSet> population, int i) {
394      SolutionSet[] parents = new SolutionSet[3];
395      int r0, r1, r2;
396      //assure the selected vectors r0, r1 and r2 are different
397      do {
398        r0 = _random.Next(0, PopulationSizeParameter.Value.Value);
399      } while(r0 == i);
400      do {
401        r1 = _random.Next(0, PopulationSizeParameter.Value.Value);
402      } while(r1 == i || r1 == r0);
403      do {
404        r2 = _random.Next(0, PopulationSizeParameter.Value.Value);
405      } while(r2 == i || r2 == r0 || r2 == r1);
406
407      parents[0] = population[r0];
408      parents[1] = population[r1];
409      parents[2] = population[r2];
410
411      return parents;
412    }
413
414    private SolutionSet reproduction(SolutionSet parent, SolutionSet[] parentsSolutions) {
415      var individual = createEmptyIndividual();
416      double rnbr = _random.Next(0, Problem.ProblemSize);
417      for(int m = 0; m < Problem.ProblemSize; m++) {
418        if(_random.NextDouble() < CrossoverProbabilityParameter.Value.Value || m == rnbr) {
419          double value;
420          value = parentsSolutions[2].Population[m] +
421              ScalingFactorParameter.Value.Value * (parentsSolutions[0].Population[m] - parentsSolutions[1].Population[m]);
422          //check the problem upper and lower bounds
423          if(value > Problem.Bounds[0, 1]) value = Problem.Bounds[0, 1];
424          if(value < Problem.Bounds[0, 0]) value = Problem.Bounds[0, 0];
425          individual.Population[m] = value;
426        } else {
427          double value;
428          value = parent.Population[m];
429          individual.Population[m] = value;
430        }
431      }
432      return individual;
433    }
434
435    private List<SolutionSet> crowdingDistanceSelection(List<SolutionSet>[] ranking) {
436      List<SolutionSet> population = new List<SolutionSet>();
437      int rankingIndex = 0;
438      while(populationIsNotFull(population)) {
439        if(subFrontFillsIntoThePopulation(ranking, rankingIndex, population)) {
440          addRankedSolutionToPopulation(ranking, rankingIndex, population);
441          rankingIndex++;
442        } else {
443          crowdingDistanceAssignment(ranking[rankingIndex]);
444          addLastRankedSolutionToPopulation(ranking, rankingIndex, population);
445        }
446      }
447      return population;
448    }
449
450    private void addLastRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population) {
451      List<SolutionSet> currentRankedFront = ranking[rankingIndex];
452      //descending sort and add the front with highest crowding distance to the population
453      currentRankedFront.Sort((x, y) => -x.CrowdingDistance.CompareTo(y.CrowdingDistance));
454      int i = 0;
455      while(population.Count < PopulationSizeParameter.Value.Value) {
456        population.Add(currentRankedFront[i]);
457        i++;
458      }
459    }
460
461    private void crowdingDistanceAssignment(List<SolutionSet> rankingSubfront) {
462      int size = rankingSubfront.Count;
463
464      if(size == 0)
465        return;
466
467      if(size == 1) {
468        rankingSubfront[0].CrowdingDistance = double.PositiveInfinity;
469        return;
470      }
471
472      if(size == 2) {
473        rankingSubfront[0].CrowdingDistance = double.PositiveInfinity;
474        rankingSubfront[1].CrowdingDistance = double.PositiveInfinity;
475        return;
476      }
477
478      //Use a new SolutionSet to evite alter original solutionSet
479      List<SolutionSet> front = new List<SolutionSet>(size);
480      for(int i = 0; i < size; i++) {
481        front.Add(rankingSubfront[i]);
482      }
483
484      for(int i = 0; i < size; i++)
485        front[i].CrowdingDistance = 0.0;
486
487      double objetiveMaxn;
488      double objetiveMinn;
489      double distance;
490
491      for(int i = 0; i < Problem.Objectives; i++) {
492        // Sort the front population by the objective i         
493        front.Sort((x, y) => x.Quality[i].CompareTo(y.Quality[i]));
494        objetiveMinn = front[0].Quality[i];
495        objetiveMaxn = front[front.Count - 1].Quality[i];
496
497        //Set crowding distance for the current front           
498        front[0].CrowdingDistance = double.PositiveInfinity;
499        front[size - 1].CrowdingDistance = double.PositiveInfinity;
500
501        for(int j = 1; j < size - 1; j++) {
502          distance = front[j + 1].Quality[i] - front[j - 1].Quality[i];
503          distance = distance / (objetiveMaxn - objetiveMinn);
504          distance += front[j].CrowdingDistance;
505          front[j].CrowdingDistance = distance;
506        }
507      }
508    }
509
510    private void addRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population) {
511      foreach(SolutionSet solution in ranking[rankingIndex]) {
512        population.Add(solution);
513      }
514    }
515
516    private bool subFrontFillsIntoThePopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population) {
517      return ranking[rankingIndex].Count < (PopulationSizeParameter.Value.Value - population.Count);
518    }
519
520    private bool populationIsNotFull(List<SolutionSet> population) {
521      return population.Count < PopulationSizeParameter.Value.Value;
522    }
523
524    private List<SolutionSet>[] computeRanking(List<SolutionSet> tmpList) {
525      // dominateMe[i] contains the number of solutions dominating i       
526      int[] dominateMe = new int[tmpList.Count];
527
528      // iDominate[k] contains the list of solutions dominated by k
529      List<int>[] iDominate = new List<int>[tmpList.Count];
530
531      // front[i] contains the list of individuals belonging to the front i
532      List<int>[] front = new List<int>[tmpList.Count + 1];
533
534      // flagDominate is an auxiliar encodings.variable
535      int flagDominate;
536
537      // Initialize the fronts
538      for(int i = 0; i < front.Length; i++) {
539        front[i] = new List<int>();
540      }
541
542      //-> Fast non dominated sorting algorithm
543      // Contribution of Guillaume Jacquenot
544      for(int p = 0; p < tmpList.Count; p++) {
545        // Initialize the list of individuals that i dominate and the number
546        // of individuals that dominate me
547        iDominate[p] = new List<int>();
548        dominateMe[p] = 0;
549      }
550      for(int p = 0; p < (tmpList.Count - 1); p++) {
551        // For all q individuals , calculate if p dominates q or vice versa
552        for(int q = p + 1; q < tmpList.Count; q++) {
553          flagDominate = compareConstraintsViolation(tmpList[p], tmpList[q]);
554          if(flagDominate == 0) {
555            flagDominate = compareDomination(tmpList[p], tmpList[q]);
556          }
557          if(flagDominate == -1) {
558            iDominate[p].Add(q);
559            dominateMe[q]++;
560          } else if(flagDominate == 1) {
561            iDominate[q].Add(p);
562            dominateMe[p]++;
563          }
564        }
565        // If nobody dominates p, p belongs to the first front
566      }
567      for(int i = 0; i < tmpList.Count; i++) {
568        if(dominateMe[i] == 0) {
569          front[0].Add(i);
570          tmpList[i].Rank = 0;
571        }
572      }
573
574      //Obtain the rest of fronts
575      int k = 0;
576
577      while(front[k].Count != 0) {
578        k++;
579        foreach(var it1 in front[k - 1]) {
580          foreach(var it2 in iDominate[it1]) {
581            int index = it2;
582            dominateMe[index]--;
583            if(dominateMe[index] == 0) {
584              front[k].Add(index);
585              tmpList[index].Rank = k;
586            }
587          }
588        }
589      }
590      //<-
591
592      var rankedSubpopulation = new List<SolutionSet>[k];
593      //0,1,2,....,i-1 are front, then i fronts
594      for(int j = 0; j < k; j++) {
595        rankedSubpopulation[j] = new List<SolutionSet>(front[j].Count);
596        foreach(var it1 in front[j]) {
597          rankedSubpopulation[j].Add(tmpList[it1]);
598        }
599      }
600      return rankedSubpopulation;
601    }
602
603    private int compareDomination(SolutionSet solution1, SolutionSet solution2) {
604      int dominate1; // dominate1 indicates if some objective of solution1
605                     // dominates the same objective in solution2. dominate2
606      int dominate2; // is the complementary of dominate1.
607
608      dominate1 = 0;
609      dominate2 = 0;
610
611      int flag; //stores the result of the comparison
612
613      // Test to determine whether at least a solution violates some constraint
614      if(needToCompareViolations(solution1, solution2)) {
615        return compareConstraintsViolation(solution1, solution2);
616      }
617
618      // Equal number of violated constraints. Applying a dominance Test then
619      double value1, value2;
620      for(int i = 0; i < Problem.Objectives; i++) {
621        value1 = solution1.Quality[i];
622        value2 = solution2.Quality[i];
623        if(value1 < value2) {
624          flag = -1;
625        } else if(value2 < value1) {
626          flag = 1;
627        } else {
628          flag = 0;
629        }
630
631        if(flag == -1) {
632          dominate1 = 1;
633        }
634
635        if(flag == 1) {
636          dominate2 = 1;
637        }
638      }
639
640      if(dominate1 == dominate2) {
641        return 0; //No one dominate the other
642      }
643      if(dominate1 == 1) {
644        return -1; // solution1 dominate
645      }
646      return 1;    // solution2 dominate   
647    }
648
649    private bool needToCompareViolations(SolutionSet solution1, SolutionSet solution2) {
650      bool needToCompare;
651      needToCompare = (solution1.OverallConstrainViolation < 0) || (solution2.OverallConstrainViolation < 0);
652
653      return needToCompare;
654    }
655
656    private int compareConstraintsViolation(SolutionSet solution1, SolutionSet solution2) {
657      int result;
658      double overall1, overall2;
659      overall1 = solution1.OverallConstrainViolation;
660      overall2 = solution2.OverallConstrainViolation;
661
662      if((overall1 < 0) && (overall2 < 0)) {
663        if(overall1 > overall2) {
664          result = -1;
665        } else if(overall2 > overall1) {
666          result = 1;
667        } else {
668          result = 0;
669        }
670      } else if((overall1 == 0) && (overall2 < 0)) {
671        result = -1;
672      } else if((overall1 < 0) && (overall2 == 0)) {
673        result = 1;
674      } else {
675        result = 0;
676      }
677      return result;
678    }
679  }
680}
681
682
683
Note: See TracBrowser for help on using the repository browser.