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

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

Add license information

File size: 30.2 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 *
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
22using System;
23using System.Linq;
24using System.Collections.Generic;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.RealVectorEncoding;
30using HeuristicLab.Operators;
31using HeuristicLab.Optimization;
32using HeuristicLab.Optimization.Operators;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35using HeuristicLab.PluginInfrastructure;
36using HeuristicLab.Problems.MultiObjectiveTestFunctions;
37using HeuristicLab.Random;
38using System.Threading;
39using HeuristicLab.Algorithms.GDE3;
40
41namespace 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 non-dominated
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,....,i-1 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
Note: See TracBrowser for help on using the repository browser.