1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  *


8  * HeuristicLab is free software: you can redistribute it and/or modify


9  * it under the terms of the GNU General Public License as published by


10  * the Free Software Foundation, either version 3 of the License, or


11  * (at your option) any later version.


12  *


13  * HeuristicLab is distributed in the hope that it will be useful,


14  * but WITHOUT ANY WARRANTY; without even the implied warranty of


15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


16  * GNU General Public License for more details.


17  *


18  * You should have received a copy of the GNU General Public License


19  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


20  */


21  #endregion


22  using System;


23  using System.Linq;


24  using System.Collections.Generic;


25  using HeuristicLab.Analysis;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.RealVectorEncoding;


30  using HeuristicLab.Operators;


31  using HeuristicLab.Optimization;


32  using HeuristicLab.Optimization.Operators;


33  using HeuristicLab.Parameters;


34  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


35  using HeuristicLab.PluginInfrastructure;


36  using HeuristicLab.Problems.MultiObjectiveTestFunctions;


37  using HeuristicLab.Random;


38  using System.Threading;


39  using HeuristicLab.Algorithms.GDE3;


40 


41  namespace HeuristicLab.Algoritms.GDE3


42  {


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  {


49  public override Type ProblemType


50  {


51  get { return typeof(MultiObjectiveTestFunctionProblem); }


52  }


53  public new MultiObjectiveTestFunctionProblem Problem


54  {


55  get { return (MultiObjectiveTestFunctionProblem)base.Problem; }


56  set { base.Problem = value; }


57  }


58 


59  public ILookupParameter<DoubleMatrix> BestKnownFrontParameter


60  {


61  get


62  {


63  return (ILookupParameter<DoubleMatrix>)Parameters["BestKnownFront"];


64  }


65  }


66 


67  private readonly IRandom _random = new MersenneTwister();


68  private int evals;


69  private double IGDSumm;


70 


71  #region ParameterNames


72  private const string MaximumGenerationsParameterName = "Maximum Generations";


73  private const string CrossoverProbabilityParameterName = "CrossoverProbability";


74  private const string PopulationSizeParameterName = "PopulationSize";


75  private const string ScalingFactorParameterName = "ScalingFactor";


76 


77  #endregion


78 


79  #region ParameterProperties


80  public IFixedValueParameter<IntValue> MaximumGenerationsParameter


81  {


82  get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsParameterName]; }


83  }


84  private ValueParameter<IntValue> PopulationSizeParameter


85  {


86  get { return (ValueParameter<IntValue>)Parameters[PopulationSizeParameterName]; }


87  }


88  public ValueParameter<DoubleValue> CrossoverProbabilityParameter


89  {


90  get { return (ValueParameter<DoubleValue>)Parameters[CrossoverProbabilityParameterName]; }


91  }


92  public ValueParameter<DoubleValue> ScalingFactorParameter


93  {


94  get { return (ValueParameter<DoubleValue>)Parameters[ScalingFactorParameterName]; }


95  }


96  #endregion


97 


98  #region Properties


99  public int MaximumEvaluations


100  {


101  get { return MaximumGenerationsParameter.Value.Value; }


102  set { MaximumGenerationsParameter.Value.Value = value; }


103  }


104 


105  public Double CrossoverProbability


106  {


107  get { return CrossoverProbabilityParameter.Value.Value; }


108  set { CrossoverProbabilityParameter.Value.Value = value; }


109  }


110  public Double ScalingFactor


111  {


112  get { return ScalingFactorParameter.Value.Value; }


113  set { ScalingFactorParameter.Value.Value = value; }


114  }


115  public IntValue PopulationSize


116  {


117  get { return PopulationSizeParameter.Value; }


118  set { PopulationSizeParameter.Value = value; }


119  }


120  #endregion


121 


122  #region ResultsProperties


123  private double ResultsBestQuality


124  {


125  get { return ((DoubleValue)Results["Best Quality"].Value).Value; }


126  set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }


127  }


128 


129  private double ResultsIGDMean


130  {


131  get { return ((DoubleValue)Results["IGDMeanValue"].Value).Value; }


132  set { ((DoubleValue)Results["IGDMeanValue"].Value).Value = value; }


133  }


134 


135  private double ResultsIGDBest


136  {


137  get { return ((DoubleValue)Results["IGDBestValue"].Value).Value; }


138  set { ((DoubleValue)Results["IGDBestValue"].Value).Value = value; }


139  }


140 


141  private double ResultsIGDWorst


142  {


143  get { return ((DoubleValue)Results["IGDWorstValue"].Value).Value; }


144  set { ((DoubleValue)Results["IGDWorstValue"].Value).Value = value; }


145  }


146 


147  private double ResultsInvertedGenerationalDistance


148  {


149  get { return ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value; }


150  set { ((DoubleValue)Results["InvertedGenerationalDistance"].Value).Value = value; }


151  }


152 


153  private double ResultsHypervolume


154  {


155  get { return ((DoubleValue)Results["HyperVolumeValue"].Value).Value; }


156  set { ((DoubleValue)Results["HyperVolumeValue"].Value).Value = value; }


157  }


158 


159  private DoubleMatrix ResultsBestFront


160  {


161  get { return (DoubleMatrix)Results["Best Front"].Value; }


162  set { Results["Best Front"].Value = value; }


163  }


164 


165  private int ResultsEvaluations


166  {


167  get { return ((IntValue)Results["Evaluations"].Value).Value; }


168  set { ((IntValue)Results["Evaluations"].Value).Value = value; }


169  }


170  private int ResultsGenerations


171  {


172  get { return ((IntValue)Results["Generations"].Value).Value; }


173  set { ((IntValue)Results["Generations"].Value).Value = value; }


174  }


175  private double ResultsGenerationalDistance


176  {


177  get { return ((DoubleValue)Results["GenerationalDistance"].Value).Value; }


178  set { ((DoubleValue)Results["GenerationalDistance"].Value).Value = value; }


179  }


180 


181  private double ResultsSpacing


182  {


183  get { return ((DoubleValue)Results["Spacing"].Value).Value; }


184  set { ((DoubleValue)Results["Spacing"].Value).Value = value; }


185  }


186 


187  private double ResultsCrowding


188  {


189  get { return ((DoubleValue)Results["Crowding"].Value).Value; }


190  set { ((DoubleValue)Results["Crowding"].Value).Value = value; }


191  }


192 


193  #endregion


194 


195  [StorableConstructor]


196  protected GDE3(bool deserializing) : base(deserializing) { }


197 


198  protected GDE3(GDE3 original, Cloner cloner)


199  : base(original, cloner)


200  {


201  }


202 


203  public override IDeepCloneable Clone(Cloner cloner)


204  {


205  return new GDE3(this, cloner);


206  }


207 


208  public GDE3()


209  {


210  Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsParameterName, "", new IntValue(1000)));


211  Parameters.Add(new ValueParameter<IntValue>(PopulationSizeParameterName, "The size of the population of solutions.", new IntValue(100)));


212  Parameters.Add(new ValueParameter<DoubleValue>(CrossoverProbabilityParameterName, "The value for crossover rate", new DoubleValue(0.5)));


213  Parameters.Add(new ValueParameter<DoubleValue>(ScalingFactorParameterName, "The value for scaling factor", new DoubleValue(0.5)));


214  Parameters.Add(new LookupParameter<DoubleMatrix>("BestKnownFront", "The currently best known Pareto front"));


215  }


216 


217  protected override void Run(CancellationToken cancellationToken)


218  {


219  // Set up the results display


220  Results.Add(new Result("Generations", new IntValue(0)));


221  Results.Add(new Result("Evaluations", new IntValue(0)));


222  Results.Add(new Result("Best Front", new DoubleMatrix()));


223  Results.Add(new Result("Crowding", new DoubleValue(0)));


224  Results.Add(new Result("InvertedGenerationalDistance", new DoubleValue(0)));


225  Results.Add(new Result("GenerationalDistance", new DoubleValue(0)));


226  Results.Add(new Result("HyperVolumeValue", new DoubleValue(0)));


227  Results.Add(new Result("IGDMeanValue", new DoubleValue(0)));


228  Results.Add(new Result("IGDBestValue", new DoubleValue(Int32.MaxValue)));


229  Results.Add(new Result("IGDWorstValue", new DoubleValue(0)));


230 


231  Results.Add(new Result("Spacing", new DoubleValue(0)));


232  Results.Add(new Result("Scatterplot", typeof(IMOFrontModel)));


233  var table = new DataTable("Qualities");


234  table.Rows.Add(new DataRow("Best Quality"));


235  Results.Add(new Result("Qualities", table));


236 


237  //setup the variables


238  List<SolutionSet> population;


239  List<SolutionSet> offspringPopulation;


240  SolutionSet[] parent;


241  double IGDSumm = 0;


242 


243  //initialize population


244  population = new List<SolutionSet>(PopulationSizeParameter.Value.Value);


245 


246  for (int i = 0; i < PopulationSizeParameter.Value.Value; ++i)


247  {


248  var m = createIndividual();


249  m.Quality = Problem.Evaluate(m.Population, _random);


250  //the test function is constrained


251  if (m.Quality.Length > Problem.Objectives)


252  {


253  m.OverallConstrainViolation = m.Quality[Problem.Objectives];


254  } else {


255  m.OverallConstrainViolation = 0;


256  }


257  population.Add(m);


258  }


259 


260  this.initProgress();


261  int generations = 1;


262 


263  while (ResultsGenerations < MaximumGenerationsParameter.Value.Value


264  && !cancellationToken.IsCancellationRequested)


265  {


266  var populationSize = PopulationSizeParameter.Value.Value;


267 


268  // Create the offSpring solutionSet


269  offspringPopulation = new List<SolutionSet>(PopulationSizeParameter.Value.Value * 2);


270 


271  for (int i = 0; i < populationSize; i++)


272  {


273  // Obtain parents. Two parameters are required: the population and the


274  // index of the current individual


275  parent = selection(population, i);


276 


277  SolutionSet child;


278  // Crossover. The parameters are the current individual and the index of the array of parents


279  child = reproduction(population[i], parent);


280 


281  child.Quality = Problem.Evaluate(child.Population, _random);


282 


283  this.updateProgres();


284 


285  //the test function is constrained


286  if (child.Quality.Length > Problem.Objectives)


287  {


288  child.OverallConstrainViolation = child.Quality[Problem.Objectives];


289  } else {


290  child.OverallConstrainViolation = 0;


291  }


292 


293  // Dominance test


294  int result;


295  result = compareDomination(population[i], child);


296 


297  if (result == 1)


298  { // Solution i dominates child


299  offspringPopulation.Add(population[i]);


300  }


301  else if (result == 1)


302  { // child dominates


303  offspringPopulation.Add(child);


304  }


305  else


306  { // the two solutions are nondominated


307  offspringPopulation.Add(child);


308  offspringPopulation.Add(population[i]);


309  }


310  }


311 


312  // Ranking the offspring population


313  List<SolutionSet>[] ranking = computeRanking(offspringPopulation);


314  population = crowdingDistanceSelection(ranking);


315  generations++;


316  ResultsGenerations = generations;


317  displayResults(population);


318  }


319  }


320 


321  private void displayResults(List<SolutionSet> population)


322  {


323  List<SolutionSet>[] rankingFinal = computeRanking(population);


324 


325  int objectives = Problem.Objectives;


326  var optimalfront = Problem.TestFunction.OptimalParetoFront(objectives);


327 


328  double[][] opf = new double[0][];


329  if (optimalfront != null)


330  {


331  opf = optimalfront.Select(s => s.ToArray()).ToArray();


332  }


333 


334  //compute the final qualities and population


335  double[][] qualitiesFinal = new double[rankingFinal[0].Count][];


336  double[][] populationFinal = new double[rankingFinal[0].Count][];


337 


338  for (int i = 0; i < rankingFinal[0].Count; ++i)


339  {


340  qualitiesFinal[i] = new double[Problem.Objectives];


341  populationFinal[i] = new double[Problem.Objectives];


342  for (int j = 0; j < Problem.Objectives; ++j)


343  {


344  populationFinal[i][j] = rankingFinal[0][i].Population[j];


345  qualitiesFinal[i][j] = rankingFinal[0][i].Quality[j];


346  }


347  }


348  IEnumerable<double[]> en = qualitiesFinal;


349  IEnumerable<double[]> frontVectors = NonDominatedSelect.selectNonDominatedVectors(qualitiesFinal, Problem.TestFunction.Maximization(objectives), true);


350  //update the results


351 


352  ResultsEvaluations = this.evals;


353  ResultsBestFront = new DoubleMatrix(MultiObjectiveTestFunctionProblem.To2D(qualitiesFinal));


354  ResultsCrowding = Crowding.Calculate(qualitiesFinal, Problem.TestFunction.Bounds(objectives));


355  ResultsInvertedGenerationalDistance = InvertedGenerationalDistance.Calculate(en, optimalfront, 1);


356  ResultsHypervolume = Hypervolume.Calculate(frontVectors, Problem.TestFunction.ReferencePoint(objectives), Problem.TestFunction.Maximization(objectives));


357  ResultsGenerationalDistance = GenerationalDistance.Calculate(qualitiesFinal, optimalfront, 1);


358  Results["Scatterplot"].Value = new MOSolution(qualitiesFinal, populationFinal, opf, objectives);


359  ResultsSpacing = Spacing.Calculate(qualitiesFinal);


360 


361  if (ResultsIGDBest > ResultsInvertedGenerationalDistance) {


362  ResultsIGDBest = ResultsInvertedGenerationalDistance;


363  }


364  if (ResultsIGDWorst < ResultsInvertedGenerationalDistance)


365  {


366  ResultsIGDWorst = ResultsInvertedGenerationalDistance;


367  }


368  this.IGDSumm += ResultsInvertedGenerationalDistance;


369  ResultsIGDMean = this.IGDSumm / ResultsGenerations;


370  }


371 


372  private int getWorstIndex(List<SolutionSet> SolutionsList)


373  {


374  int result = 0;


375 


376  if ((SolutionsList == null)  SolutionsList.Count == 0)


377  {


378  result = 0;


379  }


380  else


381  {


382  SolutionSet worstKnown = SolutionsList[0],


383  candidateSolution;


384  int flag;


385  for (int i = 1; i < SolutionsList.Count; i++)


386  {


387  candidateSolution = SolutionsList[i];


388  flag = compareDomination(worstKnown, candidateSolution);


389  if (flag == 1)


390  {


391  result = i;


392  worstKnown = candidateSolution;


393  }


394  }


395  }


396  return result;


397  }


398 


399  protected SolutionSet createIndividual()


400  {


401  var dim = Problem.ProblemSize;


402  var lb = Problem.Bounds[0, 0];


403  var ub = Problem.Bounds[0, 1];


404  var range = ub  lb;


405  var v = new double[Problem.ProblemSize];


406  SolutionSet solutionObject = new SolutionSet(PopulationSizeParameter.Value.Value);


407 


408  for (int i = 0; i < Problem.ProblemSize; ++i)


409  {


410  v[i] = _random.NextDouble() * range + lb;


411 


412  }


413  solutionObject.createSolution(v);


414  return solutionObject;


415  }


416 


417  private SolutionSet createEmptyIndividual()


418  {


419  SolutionSet solutionObject = new SolutionSet(PopulationSizeParameter.Value.Value);


420  var n = new RealVector(Problem.ProblemSize);


421  solutionObject.Population = n;


422  return solutionObject;


423  }


424 


425  protected void initProgress()


426  {


427  this.evals = PopulationSizeParameter.Value.Value;


428  }


429 


430  protected void updateProgres()


431  {


432  this.evals++;


433  }


434 


435  protected SolutionSet[] selection(List<SolutionSet> population, int i)


436  {


437  SolutionSet[] parents = new SolutionSet[3];


438  int r0, r1, r2;


439  //assure the selected vectors r0, r1 and r2 are different


440  do


441  {


442  r0 = _random.Next(0, PopulationSizeParameter.Value.Value);


443  } while (r0 == i);


444  do


445  {


446  r1 = _random.Next(0, PopulationSizeParameter.Value.Value);


447  } while (r1 == i  r1 == r0);


448  do


449  {


450  r2 = _random.Next(0, PopulationSizeParameter.Value.Value);


451  } while (r2 == i  r2 == r0  r2 == r1);


452 


453  parents[0] = population[r0];


454  parents[1] = population[r1];


455  parents[2] = population[r2];


456 


457  return parents;


458  }


459 


460  protected SolutionSet reproduction(SolutionSet parent, SolutionSet[] parentsSolutions)


461  {


462  var individual = createEmptyIndividual();


463  double rnbr = _random.Next(0, Problem.ProblemSize);


464  for (int m = 0; m < Problem.ProblemSize; m++)


465  {


466  if (_random.NextDouble() < CrossoverProbabilityParameter.Value.Value  m == rnbr)


467  {


468  double value;


469  value = parentsSolutions[2].Population[m] +


470  ScalingFactorParameter.Value.Value * (parentsSolutions[0].Population[m]  parentsSolutions[1].Population[m]);


471  //check the problem upper and lower bounds


472  if (value > Problem.Bounds[0, 1]) value = Problem.Bounds[0, 1];


473  if (value < Problem.Bounds[0, 0]) value = Problem.Bounds[0, 0];


474  individual.Population[m] = value;


475  }


476  else


477  {


478  double value;


479  value = parent.Population[m];


480  individual.Population[m] = value;


481  }


482  }


483  return individual;


484  }


485 


486  private List<SolutionSet> crowdingDistanceSelection(List<SolutionSet>[] ranking)


487  {


488  List<SolutionSet> population = new List<SolutionSet>();


489  int rankingIndex = 0;


490  while (populationIsNotFull(population))


491  {


492  if (subFrontFillsIntoThePopulation(ranking, rankingIndex, population))


493  {


494  addRankedSolutionToPopulation(ranking, rankingIndex, population);


495  rankingIndex++;


496  }


497  else {


498  crowdingDistanceAssignment(ranking[rankingIndex]);


499  addLastRankedSolutionToPopulation(ranking, rankingIndex, population);


500  }


501  }


502  return population;


503  }


504 


505  private void addLastRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)


506  {


507  List<SolutionSet> currentRankedFront = ranking[rankingIndex];


508  //descending sort and add the front with highest crowding distance to the population


509  currentRankedFront.Sort((x, y) => x.CrowdingDistance.CompareTo(y.CrowdingDistance));


510  int i = 0;


511  while (population.Count < PopulationSizeParameter.Value.Value)


512  {


513  population.Add(currentRankedFront[i]);


514  i++;


515  }


516  }


517 


518  public void crowdingDistanceAssignment(List<SolutionSet> rankingSubfront)


519  {


520  int size = rankingSubfront.Count;


521 


522  if (size == 0)


523  return;


524 


525  if (size == 1)


526  {


527  rankingSubfront[0].CrowdingDistance = double.PositiveInfinity;


528  return;


529  }


530 


531  if (size == 2)


532  {


533  rankingSubfront[0].CrowdingDistance = double.PositiveInfinity;


534  rankingSubfront[1].CrowdingDistance = double.PositiveInfinity;


535  return;


536  }


537 


538  //Use a new SolutionSet to evite alter original solutionSet


539  List<SolutionSet> front = new List<SolutionSet>(size);


540  for (int i = 0; i < size; i++)


541  {


542  front.Add(rankingSubfront[i]);


543  }


544 


545  for (int i = 0; i < size; i++)


546  front[i].CrowdingDistance = 0.0;


547 


548  double objetiveMaxn;


549  double objetiveMinn;


550  double distance;


551 


552  for (int i = 0; i < Problem.Objectives; i++)


553  {


554  // Sort the front population by the objective i


555  front.Sort((x, y) => x.Quality[i].CompareTo(y.Quality[i]));


556  objetiveMinn = front[0].Quality[i];


557  objetiveMaxn = front[front.Count  1].Quality[i];


558 


559  //Set crowding distance for the current front


560  front[0].CrowdingDistance = double.PositiveInfinity;


561  front[size  1].CrowdingDistance = double.PositiveInfinity;


562 


563  for (int j = 1; j < size  1; j++)


564  {


565  distance = front[j + 1].Quality[i]  front[j  1].Quality[i];


566  distance = distance / (objetiveMaxn  objetiveMinn);


567  distance += front[j].CrowdingDistance;


568  front[j].CrowdingDistance = distance;


569  }


570  }


571  }


572 


573  private void addRankedSolutionToPopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)


574  {


575  foreach (SolutionSet solution in ranking[rankingIndex])


576  {


577  population.Add(solution);


578  }


579  }


580 


581  private bool subFrontFillsIntoThePopulation(List<SolutionSet>[] ranking, int rankingIndex, List<SolutionSet> population)


582  {


583  return ranking[rankingIndex].Count < (PopulationSizeParameter.Value.Value  population.Count);


584  }


585 


586  private bool populationIsNotFull(List<SolutionSet> population)


587  {


588  return population.Count < PopulationSizeParameter.Value.Value;


589  }


590 


591  private List<SolutionSet>[] computeRanking(List<SolutionSet> tmpList)


592  {


593  // dominateMe[i] contains the number of solutions dominating i


594  int[] dominateMe = new int[tmpList.Count];


595 


596  // iDominate[k] contains the list of solutions dominated by k


597  List<int>[] iDominate = new List<int>[tmpList.Count];


598 


599  // front[i] contains the list of individuals belonging to the front i


600  List<int>[] front = new List<int>[tmpList.Count + 1];


601 


602  // flagDominate is an auxiliar encodings.variable


603  int flagDominate;


604 


605  // Initialize the fronts


606  for (int i = 0; i < front.Length; i++)


607  {


608  front[i] = new List<int>();


609  }


610 


611  //> Fast non dominated sorting algorithm


612  // Contribution of Guillaume Jacquenot


613  for (int p = 0; p < tmpList.Count; p++)


614  {


615  // Initialize the list of individuals that i dominate and the number


616  // of individuals that dominate me


617  iDominate[p] = new List<int>();


618  dominateMe[p] = 0;


619  }


620  for (int p = 0; p < (tmpList.Count  1); p++)


621  {


622  // For all q individuals , calculate if p dominates q or vice versa


623  for (int q = p + 1; q < tmpList.Count; q++)


624  {


625  flagDominate = compareConstraintsViolation(tmpList[p], tmpList[q]);


626  if (flagDominate == 0) {


627  flagDominate = compareDomination(tmpList[p], tmpList[q]);


628  }


629  if (flagDominate == 1)


630  {


631  iDominate[p].Add(q);


632  dominateMe[q]++;


633  }


634  else if (flagDominate == 1)


635  {


636  iDominate[q].Add(p);


637  dominateMe[p]++;


638  }


639  }


640  // If nobody dominates p, p belongs to the first front


641  }


642  for (int i = 0; i < tmpList.Count; i++)


643  {


644  if (dominateMe[i] == 0)


645  {


646  front[0].Add(i);


647  tmpList[i].Rank = 0;


648  }


649  }


650 


651  //Obtain the rest of fronts


652  int k = 0;


653 


654  while (front[k].Count != 0)


655  {


656  k++;


657  foreach (var it1 in front[k  1])


658  {


659  foreach (var it2 in iDominate[it1])


660  {


661  int index = it2;


662  dominateMe[index];


663  if (dominateMe[index] == 0)


664  {


665  front[k].Add(index);


666  tmpList[index].Rank = k;


667  }


668  }


669  }


670  }


671  //<


672 


673  var rankedSubpopulation = new List<SolutionSet>[k];


674  //0,1,2,....,i1 are front, then i fronts


675  for (int j = 0; j < k; j++)


676  {


677  rankedSubpopulation[j] = new List<SolutionSet>(front[j].Count);


678  foreach (var it1 in front[j])


679  {


680  rankedSubpopulation[j].Add(tmpList[it1]);


681  }


682  }


683  return rankedSubpopulation;


684  }


685 


686  private int compareDomination(SolutionSet solution1, SolutionSet solution2)


687  {


688  int dominate1; // dominate1 indicates if some objective of solution1


689  // dominates the same objective in solution2. dominate2


690  int dominate2; // is the complementary of dominate1.


691 


692  dominate1 = 0;


693  dominate2 = 0;


694 


695  int flag; //stores the result of the comparison


696 


697  // Test to determine whether at least a solution violates some constraint


698  if (needToCompareViolations(solution1, solution2))


699  {


700  return compareConstraintsViolation(solution1, solution2);


701  }


702 


703  // Equal number of violated constraints. Applying a dominance Test then


704  double value1, value2;


705  for (int i = 0; i < Problem.Objectives; i++)


706  {


707  value1 = solution1.Quality[i];


708  value2 = solution2.Quality[i];


709  if (value1 < value2)


710  {


711  flag = 1;


712  }


713  else if (value2 < value1)


714  {


715  flag = 1;


716  }


717  else


718  {


719  flag = 0;


720  }


721 


722  if (flag == 1)


723  {


724  dominate1 = 1;


725  }


726 


727  if (flag == 1)


728  {


729  dominate2 = 1;


730  }


731  }


732 


733  if (dominate1 == dominate2)


734  {


735  return 0; //No one dominate the other


736  }


737  if (dominate1 == 1)


738  {


739  return 1; // solution1 dominate


740  }


741  return 1; // solution2 dominate


742  }


743 


744  private bool needToCompareViolations(SolutionSet solution1, SolutionSet solution2)


745  {


746  bool needToCompare;


747  needToCompare = (solution1.OverallConstrainViolation < 0)  (solution2.OverallConstrainViolation < 0);


748 


749  return needToCompare;


750  }


751 


752  private int compareConstraintsViolation(SolutionSet solution1, SolutionSet solution2)


753  {


754  int result;


755  double overall1, overall2;


756  overall1 = solution1.OverallConstrainViolation;


757  overall2 = solution2.OverallConstrainViolation;


758 


759  if ((overall1 < 0) && (overall2 < 0))


760  {


761  if (overall1 > overall2)


762  {


763  result = 1;


764  }


765  else if (overall2 > overall1)


766  {


767  result = 1;


768  }


769  else


770  {


771  result = 0;


772  }


773  }


774  else if ((overall1 == 0) && (overall2 < 0))


775  {


776  result = 1;


777  }


778  else if ((overall1 < 0) && (overall2 == 0))


779  {


780  result = 1;


781  }


782  else


783  {


784  result = 0;


785  }


786  return result;


787  }


788  }


789  }


790 


791 


792 

