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

Last change on this file since 14087 was 14087, checked in by ichiriac, 5 years ago

Final revision of the code

File size: 31.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * Implementation based on the GDE3 implementation in jMetal Framework https://github.com/jMetal/jMetal
8 *
9 * HeuristicLab is free software: you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, either version 3 of the License, or
12 * (at your option) any later version.
13 *
14 * HeuristicLab is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
21 */
22#endregion
23using System;
24using System.Linq;
25using System.Collections.Generic;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.RealVectorEncoding;
31using HeuristicLab.Operators;
32using HeuristicLab.Optimization;
33using HeuristicLab.Optimization.Operators;
34using HeuristicLab.Parameters;
35using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
36using HeuristicLab.PluginInfrastructure;
37using HeuristicLab.Problems.MultiObjectiveTestFunctions;
38using HeuristicLab.Random;
39using System.Threading;
40using HeuristicLab.Algorithms.GDE3;
41
42namespace HeuristicLab.Algoritms.GDE3
43{
44
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"];
65            }
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    }
803}
804
805
806
Note: See TracBrowser for help on using the repository browser.