Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14705 for branches


Ignore:
Timestamp:
02/27/17 10:09:36 (7 years ago)
Author:
gkronber
Message:

#2646: changes to GDE3 and svn:ignore props

Location:
branches/ichiriac/HeuristicLab.Algorithms.GDE3
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/ichiriac/HeuristicLab.Algorithms.GDE3

    • Property svn:ignore set to
      obj
  • branches/ichiriac/HeuristicLab.Algorithms.GDE3/GDE3.cs

    r14087 r14705  
    4040using HeuristicLab.Algorithms.GDE3;
    4141
    42 namespace HeuristicLab.Algoritms.GDE3
    43 {
    44 
    45     [Item("Generalized Differential Evolution (GDE3)", "A generalized differential evolution algorithm.")]
    46     [StorableClass]
    47     [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
    48     public class GDE3 : BasicAlgorithm
    49     {
    50         public override Type ProblemType
    51         {
    52             get { return typeof(MultiObjectiveTestFunctionProblem); }
    53         }
    54         public new MultiObjectiveTestFunctionProblem Problem
    55         {
    56             get { return (MultiObjectiveTestFunctionProblem)base.Problem; }
    57             set { base.Problem = value; }
    58         }
    59 
    60         public ILookupParameter<DoubleMatrix> BestKnownFrontParameter
    61         {
    62             get
    63             {
    64                 return (ILookupParameter<DoubleMatrix>)Parameters["BestKnownFront"];
     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;
    65586            }
    66         }
    67 
    68         private readonly IRandom _random = new MersenneTwister();
    69         private int evals;
    70         private double IGDSumm;
    71 
    72         #region ParameterNames
    73         private const string MaximumGenerationsParameterName = "Maximum Generations";
    74         private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
    75         private const string CrossoverProbabilityParameterName = "CrossoverProbability";
    76         private const string PopulationSizeParameterName = "PopulationSize";
    77         private const string ScalingFactorParameterName = "ScalingFactor";
    78 
    79         #endregion
    80 
    81         #region ParameterProperties
    82         public IFixedValueParameter<IntValue> MaximumGenerationsParameter
    83         {
    84             get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }
    85         }
    86         public IFixedValueParameter<IntValue> MaximumEvaluationsParameter
    87         {
    88             get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
    89         }
    90         private ValueParameter<IntValue> PopulationSizeParameter
    91         {
    92             get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
    93         }
    94         public ValueParameter<DoubleValue> CrossoverProbabilityParameter
    95         {
    96             get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }
    97         }
    98         public ValueParameter<DoubleValue> ScalingFactorParameter
    99         {
    100             get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }
    101         }
    102         #endregion
    103 
    104         #region Properties
    105         public int MaximumGenerations
    106         {
    107             get { return MaximumGenerationsParameter.Value.Value; }
    108             set { MaximumGenerationsParameter.Value.Value = value; }
    109         }
    110 
    111         public int MaximumEvaluations
    112         {
    113             get { return MaximumEvaluationsParameter.Value.Value; }
    114             set { MaximumEvaluationsParameter.Value.Value = value; }
    115         }
    116 
    117         public Double CrossoverProbability
    118         {
    119             get { return CrossoverProbabilityParameter.Value.Value; }
    120             set { CrossoverProbabilityParameter.Value.Value = value; }
    121         }
    122         public Double ScalingFactor
    123         {
    124             get { return ScalingFactorParameter.Value.Value; }
    125             set { ScalingFactorParameter.Value.Value = value; }
    126         }
    127         public IntValue PopulationSize
    128         {
    129             get { return PopulationSizeParameter.Value; }
    130             set { PopulationSizeParameter.Value = value; }
    131         }
    132         #endregion
    133 
    134         #region ResultsProperties
    135         private double ResultsBestQuality
    136         {
    137             get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
    138             set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
    139         }
    140 
    141         private double ResultsIGDMean
    142         {
    143             get { return ((DoubleValue)Results["IGDMeanValue"].Value).Value; }
    144             set { ((DoubleValue)Results["IGDMeanValue"].Value).Value = value; }
    145         }
    146 
    147         private double ResultsIGDBest
    148         {
    149             get { return ((DoubleValue)Results["IGDBestValue"].Value).Value; }
    150             set { ((DoubleValue)Results["IGDBestValue"].Value).Value = value; }
    151         }
    152 
    153         private double ResultsIGDWorst
    154         {
    155             get { return ((DoubleValue)Results["IGDWorstValue"].Value).Value; }
    156             set { ((DoubleValue)Results["IGDWorstValue"].Value).Value = value; }
    157         }
    158 
    159         private double ResultsInvertedGenerationalDistance
    160         {
    161             get { return ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value; }
    162             set { ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value = value; }
    163         }
    164 
    165         private double ResultsHypervolume
    166         {
    167             get { return ((DoubleValue)Results["HyperVolumeValue"].Value).Value; }
    168             set { ((DoubleValue)Results["HyperVolumeValue"].Value).Value = value; }
    169         }
    170 
    171         private DoubleMatrix ResultsBestFront
    172         {
    173             get { return (DoubleMatrix)Results["Best Front"].Value; }
    174             set { Results["Best Front"].Value = value; }
    175         }
    176 
    177         private int ResultsEvaluations
    178         {
    179             get { return ((IntValue)Results["Evaluations"].Value).Value; }
    180             set { ((IntValue)Results["Evaluations"].Value).Value = value; }
    181         }
    182         private int ResultsGenerations
    183         {
    184             get { return ((IntValue)Results["Generations"].Value).Value; }
    185             set { ((IntValue)Results["Generations"].Value).Value = value; }
    186         }
    187         private double ResultsGenerationalDistance
    188         {
    189             get { return ((DoubleValue)Results["GenerationalDistance"].Value).Value; }
    190             set { ((DoubleValue)Results["GenerationalDistance"].Value).Value = value; }
    191         }
    192 
    193         private double ResultsSpacing
    194         {
    195             get { return ((DoubleValue)Results["Spacing"].Value).Value; }
    196             set { ((DoubleValue)Results["Spacing"].Value).Value = value; }
    197         }
    198 
    199         private double ResultsCrowding
    200         {
    201             get { return ((DoubleValue)Results["Crowding"].Value).Value; }
    202             set { ((DoubleValue)Results["Crowding"].Value).Value = value; }
    203         }
    204 
    205         #endregion
    206 
    207         [StorableConstructor]
    208         protected GDE3(bool deserializing) : base(deserializing) { }
    209 
    210         protected GDE3(GDE3 original, Cloner cloner)
    211           : base(original, cloner)
    212         {
    213         }
    214 
    215         public override IDeepCloneable Clone(Cloner cloner)
    216         {
    217             return new GDE3(this, cloner);
    218         }
    219 
    220         public GDE3()
    221         {
    222             Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsParameterName, "", new IntValue(1000)));
    223             Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
    224             Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));
    225             Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.5)));
    226             Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.5)));
    227             Parameters.Add(new LookupParameter<DoubleMatrix>("BestKnownFront", "The currently best known Pareto front"));
    228         }
    229 
    230         protected override void Run(CancellationToken cancellationToken)
    231         {
    232             // Set up the results display
    233             Results.Add(new Result("Generations", new IntValue(0)));
    234             Results.Add(new Result("Evaluations", new IntValue(0)));
    235             Results.Add(new Result("Best Front", new DoubleMatrix()));
    236             Results.Add(new Result("Crowding", new DoubleValue(0)));
    237             Results.Add(new Result("InvertedGenerationalDistance", new DoubleValue(0)));
    238             Results.Add(new Result("GenerationalDistance", new DoubleValue(0)));
    239             Results.Add(new Result("HyperVolumeValue", new DoubleValue(0)));
    240             Results.Add(new Result("IGDMeanValue", new DoubleValue(0)));
    241             Results.Add(new Result("IGDBestValue", new DoubleValue(Int32.MaxValue)));
    242             Results.Add(new Result("IGDWorstValue", new DoubleValue(0)));
    243 
    244             Results.Add(new Result("Spacing", new DoubleValue(0)));
    245             Results.Add(new Result("Scatterplot", typeof(IMOFrontModel)));
    246             var table = new DataTable("Qualities");
    247             table.Rows.Add(new DataRow("Best Quality"));
    248             Results.Add(new Result("Qualities", table));
    249 
    250             //setup the variables
    251             List<SolutionSet> population;
    252             List<SolutionSet> offspringPopulation;
    253             SolutionSet[] parent;
    254             double IGDSumm = 0;
    255            
    256             //initialize population
    257             population = new List<SolutionSet>(PopulationSizeParameter.Value.Value);
    258 
    259             for (int i = 0; i < PopulationSizeParameter.Value.Value; ++i)
    260             {
    261                 var m = createIndividual();
    262                 m.Quality = Problem.Evaluate(m.Population, _random);
    263                 //the test function is constrained
    264                 if (m.Quality.Length > Problem.Objectives)
    265                 {
    266                     m.OverallConstrainViolation = m.Quality[Problem.Objectives];
    267                 } else {
    268                     m.OverallConstrainViolation = 0;
    269                 }
    270                 population.Add(m);
    271             }
    272 
    273             this.initProgress();
    274             int generations = 1;
    275 
    276             while (ResultsEvaluations < MaximumEvaluationsParameter.Value.Value
    277                && !cancellationToken.IsCancellationRequested)
    278             {
    279                 var populationSize = PopulationSizeParameter.Value.Value;
    280 
    281                 // Create the offSpring solutionSet
    282                 offspringPopulation = new List<SolutionSet>(PopulationSizeParameter.Value.Value * 2);
    283 
    284                 for (int i = 0; i < populationSize; i++)
    285                 {
    286                     // Obtain parents. Two parameters are required: the population and the
    287                     //                 index of the current individual
    288                     parent = selection(population, i);
    289 
    290                     SolutionSet child;
    291                     // Crossover. The parameters are the current individual and the index of the array of parents
    292                     child = reproduction(population[i], parent);
    293 
    294                     child.Quality = Problem.Evaluate(child.Population, _random);
    295 
    296                     this.updateProgres();
    297 
    298                     //the test function is constrained
    299                     if (child.Quality.Length > Problem.Objectives)
    300                     {
    301                         child.OverallConstrainViolation = child.Quality[Problem.Objectives];
    302                     } else {
    303                         child.OverallConstrainViolation = 0;
    304                     }
    305 
    306                     // Dominance test
    307                     int result;
    308                     result = compareDomination(population[i], child);
    309 
    310                     if (result == -1)
    311                     { // Solution i dominates child
    312                         offspringPopulation.Add(population[i]);
    313                     }
    314                     else if (result == 1)
    315                     { // child dominates
    316                         offspringPopulation.Add(child);
    317                     }
    318                     else
    319                     { // the two solutions are non-dominated
    320                         offspringPopulation.Add(child);
    321                         offspringPopulation.Add(population[i]);
    322                     }
    323                 }
    324 
    325                 // Ranking the offspring population
    326                 List<SolutionSet>[] ranking = computeRanking(offspringPopulation);
    327                 population = crowdingDistanceSelection(ranking);
    328                 generations++;
    329                 ResultsGenerations = generations;
    330                 displayResults(population);
    331             }
    332         }
    333 
    334         private void displayResults(List<SolutionSet> population)
    335         {
    336             List<SolutionSet>[] rankingFinal = computeRanking(population);
    337 
    338             int objectives = Problem.Objectives;
    339             var optimalfront = Problem.TestFunction.OptimalParetoFront(objectives);
    340 
    341             double[][] opf = new double[0][];
    342             if (optimalfront != null)
    343             {
    344                 opf = optimalfront.Select(s => s.ToArray()).ToArray();
    345             }
    346 
    347             //compute the final qualities and population
    348             double[][] qualitiesFinal = new double[rankingFinal[0].Count][];
    349             double[][] populationFinal = new double[rankingFinal[0].Count][];
    350 
    351             for (int i = 0; i < rankingFinal[0].Count; ++i)
    352             {
    353                 qualitiesFinal[i] = new double[Problem.Objectives];
    354                 populationFinal[i] = new double[Problem.Objectives];
    355                 for (int j = 0; j < Problem.Objectives; ++j)
    356                 {
    357                     populationFinal[i][j] = rankingFinal[0][i].Population[j];
    358                     qualitiesFinal[i][j] = rankingFinal[0][i].Quality[j];
    359                 }
    360             }
    361             IEnumerable<double[]> en = qualitiesFinal;
    362             IEnumerable<double[]> frontVectors = NonDominatedSelect.selectNonDominatedVectors(qualitiesFinal, Problem.TestFunction.Maximization(objectives), true);
    363             //update the results
    364 
    365             ResultsEvaluations = this.evals;
    366             ResultsBestFront = new DoubleMatrix(MultiObjectiveTestFunctionProblem.To2D(qualitiesFinal));
    367             ResultsCrowding = Crowding.Calculate(qualitiesFinal, Problem.TestFunction.Bounds(objectives));
    368             GenerationalDistanceCalculator distance = new GenerationalDistanceCalculator();
    369             ResultsInvertedGenerationalDistance = distance.CalculateGenerationalDistance(qualitiesFinal, opf, Problem.Objectives);
    370             ResultsHypervolume = Hypervolume.Calculate(frontVectors, Problem.TestFunction.ReferencePoint(objectives), Problem.TestFunction.Maximization(objectives));
    371             ResultsGenerationalDistance = GenerationalDistance.Calculate(qualitiesFinal, optimalfront, 1);
    372             Results["Scatterplot"].Value = new MOSolution(qualitiesFinal, populationFinal, opf, objectives);
    373             ResultsSpacing = Spacing.Calculate(qualitiesFinal);
    374 
    375             if (ResultsIGDBest > ResultsInvertedGenerationalDistance) {
    376                 ResultsIGDBest = ResultsInvertedGenerationalDistance;
    377             }
    378             if (ResultsIGDWorst < ResultsInvertedGenerationalDistance)
    379             {
    380                 ResultsIGDWorst = ResultsInvertedGenerationalDistance;
    381             }
    382             this.IGDSumm += ResultsInvertedGenerationalDistance;
    383             ResultsIGDMean = this.IGDSumm / ResultsGenerations;
    384         }
    385 
    386         private int getWorstIndex(List<SolutionSet> SolutionsList)
    387         {
    388             int result = 0;
    389 
    390             if ((SolutionsList == null) || SolutionsList.Count == 0)
    391             {
    392                 result = 0;
    393             }
    394             else
    395             {
    396                 SolutionSet worstKnown = SolutionsList[0],
    397                             candidateSolution;
    398                 int flag;
    399                 for (int i = 1; i < SolutionsList.Count; i++)
    400                 {
    401                     candidateSolution = SolutionsList[i];
    402                     flag = compareDomination(worstKnown, candidateSolution);
    403                     if (flag == -1)
    404                     {
    405                         result = i;
    406                         worstKnown = candidateSolution;
    407                     }
    408                 }
    409             }
    410             return result;
    411         }
    412 
    413         private SolutionSet createIndividual()
    414         {
    415             var dim = Problem.ProblemSize;
    416             var lb = Problem.Bounds[0, 0];
    417             var ub = Problem.Bounds[0, 1];
    418             var range = ub - lb;
    419             var v = new double[Problem.ProblemSize];
    420             SolutionSet solutionObject = new SolutionSet(PopulationSizeParameter.Value.Value);
    421 
    422             for (int i = 0; i < Problem.ProblemSize; ++i)
    423             {
    424                 v[i] = _random.NextDouble() * range + lb;
    425 
    426             }
    427             solutionObject.createSolution(v);
    428             return solutionObject;
    429         }
    430 
    431         private SolutionSet createEmptyIndividual()
    432         {
    433             SolutionSet solutionObject = new SolutionSet(PopulationSizeParameter.Value.Value);
    434             var n = new RealVector(Problem.ProblemSize);
    435             solutionObject.Population = n;
    436             return solutionObject;
    437         }
    438 
    439         private void initProgress()
    440         {
    441             this.evals = PopulationSizeParameter.Value.Value;
    442         }
    443 
    444         private void updateProgres()
    445         {
    446             this.evals++;
    447         }
    448 
    449         private SolutionSet[] selection(List<SolutionSet> population, int i)
    450         {
    451             SolutionSet[] parents = new SolutionSet[3];
    452             int r0, r1, r2;
    453             //assure the selected vectors r0, r1 and r2 are different
    454             do
    455             {
    456                 r0 = _random.Next(0, PopulationSizeParameter.Value.Value);
    457             } while (r0 == i);
    458             do
    459             {
    460                 r1 = _random.Next(0, PopulationSizeParameter.Value.Value);
    461             } while (r1 == i || r1 == r0);
    462             do
    463             {
    464                 r2 = _random.Next(0, PopulationSizeParameter.Value.Value);
    465             } while (r2 == i || r2 == r0 || r2 == r1);
    466 
    467             parents[0] = population[r0];
    468             parents[1] = population[r1];
    469             parents[2] = population[r2];
    470 
    471             return parents;
    472         }
    473 
    474         private SolutionSet reproduction(SolutionSet parent, SolutionSet[] parentsSolutions)
    475         {
    476             var individual = createEmptyIndividual();
    477             double rnbr = _random.Next(0, Problem.ProblemSize);
    478             for (int m = 0; m < Problem.ProblemSize; m++)
    479             {
    480                 if (_random.NextDouble() < CrossoverProbabilityParameter.Value.Value || m == rnbr)
    481                 {
    482                     double value;
    483                     value = parentsSolutions[2].Population[m] +
    484                         ScalingFactorParameter.Value.Value * (parentsSolutions[0].Population[m] - parentsSolutions[1].Population[m]);
    485                     //check the problem upper and lower bounds
    486                     if (value > Problem.Bounds[0, 1]) value = Problem.Bounds[0, 1];
    487                     if (value < Problem.Bounds[0, 0]) value = Problem.Bounds[0, 0];
    488                     individual.Population[m] = value;
    489                 }
    490                 else
    491                 {
    492                     double value;
    493                     value = parent.Population[m];
    494                     individual.Population[m] = value;
    495                 }
    496             }
    497             return individual;
    498         }
    499 
    500         private List<SolutionSet> crowdingDistanceSelection(List<SolutionSet>[] ranking)
    501         {
    502             List<SolutionSet> population = new List<SolutionSet>();
    503             int rankingIndex = 0;
    504             while (populationIsNotFull(population))
    505             {
    506                 if (subFrontFillsIntoThePopulation(ranking, rankingIndex, population))
    507                 {
    508                     addRankedSolutionToPopulation(ranking, rankingIndex, population);
    509                     rankingIndex++;
    510                 }
    511                 else {
    512                     crowdingDistanceAssignment(ranking[rankingIndex]);
    513                     addLastRankedSolutionToPopulation(ranking, rankingIndex, population);
    514                 }
    515             }
    516             return population;
    517         }
    518 
    519         private void addLastRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)
    520         {
    521             List<SolutionSet> currentRankedFront = ranking[rankingIndex];
    522             //descending sort and add the front with highest crowding distance to the population
    523             currentRankedFront.Sort((x, y) => -x.CrowdingDistance.CompareTo(y.CrowdingDistance));
    524             int i = 0;
    525             while (population.Count < PopulationSizeParameter.Value.Value)
    526             {
    527                 population.Add(currentRankedFront[i]);
    528                 i++;
    529             }
    530         }
    531 
    532         private void crowdingDistanceAssignment(List<SolutionSet> rankingSubfront)
    533         {
    534             int size = rankingSubfront.Count;
    535 
    536             if (size == 0)
    537                 return;
    538 
    539             if (size == 1)
    540             {
    541                 rankingSubfront[0].CrowdingDistance = double.PositiveInfinity;
    542                 return;
    543             }
    544 
    545             if (size == 2)
    546             {
    547                 rankingSubfront[0].CrowdingDistance = double.PositiveInfinity;
    548                 rankingSubfront[1].CrowdingDistance = double.PositiveInfinity;
    549                 return;
    550             }
    551 
    552             //Use a new SolutionSet to evite alter original solutionSet
    553             List<SolutionSet> front = new List<SolutionSet>(size);
    554             for (int i = 0; i < size; i++)
    555             {
    556                 front.Add(rankingSubfront[i]);
    557             }
    558 
    559             for (int i = 0; i < size; i++)
    560                 front[i].CrowdingDistance = 0.0;
    561 
    562             double objetiveMaxn;
    563             double objetiveMinn;
    564             double distance;
    565 
    566             for (int i = 0; i < Problem.Objectives; i++)
    567             {
    568                 // Sort the front population by the objective i         
    569                 front.Sort((x, y) => x.Quality[i].CompareTo(y.Quality[i]));
    570                 objetiveMinn = front[0].Quality[i];
    571                 objetiveMaxn = front[front.Count - 1].Quality[i];
    572 
    573                 //Set crowding distance for the current front           
    574                 front[0].CrowdingDistance = double.PositiveInfinity;
    575                 front[size - 1].CrowdingDistance = double.PositiveInfinity;
    576 
    577                 for (int j = 1; j < size - 1; j++)
    578                 {
    579                     distance = front[j + 1].Quality[i] - front[j - 1].Quality[i];
    580                     distance = distance / (objetiveMaxn - objetiveMinn);
    581                     distance += front[j].CrowdingDistance;
    582                     front[j].CrowdingDistance = distance;
    583                 }
    584             }
    585         }
    586 
    587         private void addRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)
    588         {
    589             foreach (SolutionSet solution in ranking[rankingIndex])
    590             {
    591                 population.Add(solution);
    592             }
    593         }
    594 
    595         private bool subFrontFillsIntoThePopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)
    596         {
    597             return ranking[rankingIndex].Count < (PopulationSizeParameter.Value.Value - population.Count);
    598         }
    599 
    600         private bool populationIsNotFull(List<SolutionSet> population)
    601         {
    602             return population.Count < PopulationSizeParameter.Value.Value;
    603         }
    604 
    605         private List<SolutionSet>[] computeRanking(List<SolutionSet> tmpList)
    606         {
    607             // dominateMe[i] contains the number of solutions dominating i       
    608             int[] dominateMe = new int[tmpList.Count];
    609 
    610             // iDominate[k] contains the list of solutions dominated by k
    611             List<int>[] iDominate = new List<int>[tmpList.Count];
    612 
    613             // front[i] contains the list of individuals belonging to the front i
    614             List<int>[] front = new List<int>[tmpList.Count + 1];
    615 
    616             // flagDominate is an auxiliar encodings.variable
    617             int flagDominate;
    618 
    619             // Initialize the fronts
    620             for (int i = 0; i < front.Length; i++)
    621             {
    622                 front[i] = new List<int>();
    623             }
    624 
    625             //-> Fast non dominated sorting algorithm
    626             // Contribution of Guillaume Jacquenot
    627             for (int p = 0; p < tmpList.Count; p++)
    628             {
    629                 // Initialize the list of individuals that i dominate and the number
    630                 // of individuals that dominate me
    631                 iDominate[p] = new List<int>();
    632                 dominateMe[p] = 0;
    633             }
    634             for (int p = 0; p < (tmpList.Count - 1); p++)
    635             {
    636                 // For all q individuals , calculate if p dominates q or vice versa
    637                 for (int q = p + 1; q < tmpList.Count; q++)
    638                 {
    639                     flagDominate = compareConstraintsViolation(tmpList[p], tmpList[q]);
    640                     if (flagDominate == 0) {
    641                         flagDominate = compareDomination(tmpList[p], tmpList[q]);
    642                     }
    643                     if (flagDominate == -1)
    644                     {
    645                         iDominate[p].Add(q);
    646                         dominateMe[q]++;
    647                     }
    648                     else if (flagDominate == 1)
    649                     {
    650                         iDominate[q].Add(p);
    651                         dominateMe[p]++;
    652                     }
    653                 }
    654                 // If nobody dominates p, p belongs to the first front
    655             }
    656             for (int i = 0; i < tmpList.Count; i++)
    657             {
    658                 if (dominateMe[i] == 0)
    659                 {
    660                     front[0].Add(i);
    661                     tmpList[i].Rank = 0;
    662                 }
    663             }
    664 
    665             //Obtain the rest of fronts
    666             int k = 0;
    667 
    668             while (front[k].Count != 0)
    669             {
    670                 k++;
    671                 foreach (var it1 in front[k - 1])
    672                 {
    673                     foreach (var it2 in iDominate[it1])
    674                     {
    675                         int index = it2;
    676                         dominateMe[index]--;
    677                         if (dominateMe[index] == 0)
    678                         {
    679                             front[k].Add(index);
    680                             tmpList[index].Rank = k;
    681                         }
    682                     }
    683                 }
    684             }
    685             //<-
    686 
    687             var rankedSubpopulation = new List<SolutionSet>[k];
    688             //0,1,2,....,i-1 are front, then i fronts
    689             for (int j = 0; j < k; j++)
    690             {
    691                 rankedSubpopulation[j] = new List<SolutionSet>(front[j].Count);
    692                 foreach (var it1 in front[j])
    693                 {
    694                     rankedSubpopulation[j].Add(tmpList[it1]);
    695                 }
    696             }
    697             return rankedSubpopulation;
    698         }
    699 
    700         private int compareDomination(SolutionSet solution1, SolutionSet solution2)
    701         {
    702             int dominate1; // dominate1 indicates if some objective of solution1
    703                            // dominates the same objective in solution2. dominate2
    704             int dominate2; // is the complementary of dominate1.
    705 
    706             dominate1 = 0;
    707             dominate2 = 0;
    708 
    709             int flag; //stores the result of the comparison
    710 
    711             // Test to determine whether at least a solution violates some constraint
    712             if (needToCompareViolations(solution1, solution2))
    713             {
    714                 return compareConstraintsViolation(solution1, solution2);
    715             }
    716 
    717             // Equal number of violated constraints. Applying a dominance Test then
    718             double value1, value2;
    719             for (int i = 0; i < Problem.Objectives; i++)
    720             {
    721                 value1 = solution1.Quality[i];
    722                 value2 = solution2.Quality[i];
    723                 if (value1 < value2)
    724                 {
    725                     flag = -1;
    726                 }
    727                 else if (value2 < value1)
    728                 {
    729                     flag = 1;
    730                 }
    731                 else
    732                 {
    733                     flag = 0;
    734                 }
    735 
    736                 if (flag == -1)
    737                 {
    738                     dominate1 = 1;
    739                 }
    740 
    741                 if (flag == 1)
    742                 {
    743                     dominate2 = 1;
    744                 }
    745             }
    746 
    747             if (dominate1 == dominate2)
    748             {
    749                 return 0; //No one dominate the other
    750             }
    751             if (dominate1 == 1)
    752             {
    753                 return -1; // solution1 dominate
    754             }
    755             return 1;    // solution2 dominate   
    756         }
    757 
    758         private bool needToCompareViolations(SolutionSet solution1, SolutionSet solution2)
    759         {
    760             bool needToCompare;
    761             needToCompare = (solution1.OverallConstrainViolation < 0) || (solution2.OverallConstrainViolation < 0);
    762 
    763             return needToCompare;
    764         }
    765 
    766         private int compareConstraintsViolation(SolutionSet solution1, SolutionSet solution2)
    767         {
    768             int result;
    769             double overall1, overall2;
    770             overall1 = solution1.OverallConstrainViolation;
    771             overall2 = solution2.OverallConstrainViolation;
    772 
    773             if ((overall1 < 0) && (overall2 < 0))
    774             {
    775                 if (overall1 > overall2)
    776                 {
    777                     result = -1;
    778                 }
    779                 else if (overall2 > overall1)
    780                 {
    781                     result = 1;
    782                 }
    783                 else
    784                 {
    785                     result = 0;
    786                 }
    787             }
    788             else if ((overall1 == 0) && (overall2 < 0))
    789             {
    790                 result = -1;
    791             }
    792             else if ((overall1 < 0) && (overall2 == 0))
    793             {
    794                 result = 1;
    795             }
    796             else
    797             {
    798                 result = 0;
    799             }
    800             return result;
    801         }
    802     }
     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  }
    803680}
    804681
  • branches/ichiriac/HeuristicLab.Algorithms.GDE3/HeuristicLab.Algorithms.GDE3.csproj

    r13756 r14705  
    9191      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
    9292    </Reference>
    93     <Reference Include="HeuristicLab.Problems.MultiObjectiveTestFunctions-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    94       <SpecificVersion>False</SpecificVersion>
    95       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.MultiObjectiveTestFunctions-3.3.dll</HintPath>
    96     </Reference>
    9793    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    9894      <SpecificVersion>False</SpecificVersion>
Note: See TracChangeset for help on using the changeset viewer.