Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2987_MOEAD_Algorithm/HeuristicLab.Algorithms.MOEAD/3.4/MOEADUtil.cs

Last change on this file was 16649, checked in by bburlacu, 5 years ago

#2987: Prevent updating the Ideal and Nadir points with NaN or Infinity values. Simplify algorithm code (use arrays instead of lists). Add missing StorableType attributes. Add hypervolume analysis for the pareto fronts.

File size: 7.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using System;
25using System.Collections.Generic;
26using System.Linq;
27
28namespace HeuristicLab.Algorithms.MOEAD {
29  public static class MOEADUtil {
30    public static void QuickSort(double[] array, int[] idx, int from, int to) {
31      if (from < to) {
32        double temp = array[to];
33        int tempIdx = idx[to];
34        int i = from - 1;
35        for (int j = from; j < to; j++) {
36          if (array[j] <= temp) {
37            i++;
38            double tempValue = array[j];
39            array[j] = array[i];
40            array[i] = tempValue;
41            int tempIndex = idx[j];
42            idx[j] = idx[i];
43            idx[i] = tempIndex;
44          }
45        }
46        array[to] = array[i + 1];
47        array[i + 1] = temp;
48        idx[to] = idx[i + 1];
49        idx[i + 1] = tempIdx;
50        QuickSort(array, idx, from, i);
51        QuickSort(array, idx, i + 1, to);
52      }
53    }
54
55    public static void MinFastSort(double[] x, int[] idx, int n, int m) {
56      for (int i = 0; i < m; i++) {
57        for (int j = i + 1; j < n; j++) {
58          if (x[i] > x[j]) {
59            double temp = x[i];
60            x[i] = x[j];
61            x[j] = temp;
62            int id = idx[i];
63            idx[i] = idx[j];
64            idx[j] = id;
65          }
66        }
67      }
68    }
69
70    public static IList<IMOEADSolution> GetSubsetOfEvenlyDistributedSolutions(IRandom random, IList<IMOEADSolution> solutionList, int newSolutionListSize) {
71      if (solutionList == null || solutionList.Count == 0) {
72        throw new ArgumentException("Solution list is null or empty.");
73      }
74
75      return solutionList[0].Dimensions == 2
76        ? TwoObjectivesCase(solutionList, newSolutionListSize)
77        : MoreThanTwoObjectivesCase(random, solutionList, newSolutionListSize);
78    }
79
80    private static IList<IMOEADSolution> TwoObjectivesCase(IList<IMOEADSolution> solutionList, int newSolutionListSize) {
81      var resultSolutionList = new IMOEADSolution[newSolutionListSize];
82
83      // compute weight vectors
84      double[][] lambda = new double[newSolutionListSize][];
85      var values = SequenceGenerator.GenerateSteps(0m, 1m, 1m / newSolutionListSize).ToArray();
86      for (int i = 0; i < newSolutionListSize; ++i) {
87        var weights = new double[newSolutionListSize];
88        weights[0] = (double)values[i];
89        weights[1] = 1 - weights[0];
90
91        lambda[i] = weights;
92      }
93
94      var idealPoint = new double[2];
95      foreach (var solution in solutionList) {
96        // update ideal point
97        idealPoint.UpdateIdeal(solution.Qualities);
98      }
99
100      // Select the best solution for each weight vector
101      for (int i = 0; i < newSolutionListSize; i++) {
102        var currentBest = solutionList[0];
103        double value = ScalarizingFitnessFunction(currentBest, lambda[i], idealPoint);
104        for (int j = 1; j < solutionList.Count; j++) {
105          double aux = ScalarizingFitnessFunction(solutionList[j], lambda[i], idealPoint); // we are looking for the best for the weight i
106          if (aux < value) { // solution in position j is better!
107            value = aux;
108            currentBest = solutionList[j];
109          }
110        }
111        resultSolutionList[i] = (MOEADSolution)currentBest.Clone();
112      }
113
114      return resultSolutionList;
115    }
116
117    private static IList<IMOEADSolution> MoreThanTwoObjectivesCase(IRandom random, IList<IMOEADSolution> solutionList, int newSolutionListSize) {
118      var resultSolutionList = new List<IMOEADSolution>();
119
120      int randomIndex = random.Next(0, solutionList.Count);
121
122      var candidate = new List<IMOEADSolution>();
123      resultSolutionList.Add(solutionList[randomIndex]);
124
125      for (int i = 0; i < solutionList.Count; ++i) {
126        if (i != randomIndex) {
127          candidate.Add(solutionList[i]);
128        }
129      }
130
131      while (resultSolutionList.Count < newSolutionListSize) {
132        int index = 0;
133        var selected = candidate[0]; // it should be a next! (n <= population size!)
134        double aux = CalculateBestDistance(selected, solutionList);
135        int i = 1;
136        while (i < candidate.Count) {
137          var nextCandidate = candidate[i];
138          double distanceValue = CalculateBestDistance(nextCandidate, solutionList);
139          if (aux < distanceValue) {
140            index = i;
141            aux = distanceValue;
142          }
143          i++;
144        }
145
146        // add the selected to res and remove from candidate list
147        var removedSolution = candidate[index];
148        candidate.RemoveAt(index);
149        resultSolutionList.Add((MOEADSolution)removedSolution.Clone());
150      }
151
152      return resultSolutionList;
153    }
154
155    private static double ScalarizingFitnessFunction(IMOEADSolution currentBest, double[] lambda, double[] idealPoint) {
156      double maxFun = -1.0e+30;
157
158      for (int n = 0; n < idealPoint.Length; n++) {
159        double diff = Math.Abs(currentBest.Qualities[n] - idealPoint[n]);
160
161        double functionValue;
162        if (lambda[n] == 0) {
163          functionValue = 0.0001 * diff;
164        } else {
165          functionValue = diff * lambda[n];
166        }
167        if (functionValue > maxFun) {
168          maxFun = functionValue;
169        }
170      }
171
172      return maxFun;
173    }
174
175    public static void UpdateIdeal(this double[] idealPoint, double[] point) {
176      for (int i = 0; i < point.Length; ++i) {
177        if (double.IsInfinity(point[i]) || double.IsNaN(point[i])) {
178          continue;
179        }
180
181        if (idealPoint[i] > point[i]) {
182          idealPoint[i] = point[i];
183        }
184      }
185    }
186
187    public static void UpdateNadir(this double[] nadirPoint, double[] point) {
188      for (int i = 0; i < point.Length; ++i) {
189        if (double.IsInfinity(point[i]) || double.IsNaN(point[i])) {
190          continue;
191        }
192
193        if (nadirPoint[i] < point[i]) {
194          nadirPoint[i] = point[i];
195        }
196      }
197    }
198
199    public static void UpdateIdeal(this double[] idealPoint, IList<IMOEADSolution> solutions) {
200      foreach (var s in solutions) {
201        idealPoint.UpdateIdeal(s.Qualities);
202      }
203    }
204
205    public static void UpdateNadir(this double[] nadirPoint, IList<IMOEADSolution> solutions) {
206      foreach (var s in solutions) {
207        nadirPoint.UpdateNadir(s.Qualities);
208      }
209    }
210
211    private static double CalculateBestDistance(IMOEADSolution solution, IList<IMOEADSolution> solutionList) {
212      var best = solutionList.Min(x => EuclideanDistance(solution.Qualities, x.Qualities));
213      if (double.IsNaN(best) || double.IsInfinity(best)) {
214        best = double.MaxValue;
215      }
216      return best;
217    }
218
219    public static double EuclideanDistance(double[] a, double[] b) {
220      if (a.Length != b.Length) {
221        throw new ArgumentException("Euclidean distance: the arrays have different lengths.");
222      }
223
224      var distance = 0d;
225      for (int i = 0; i < a.Length; ++i) {
226        var d = a[i] - b[i];
227        distance += d * d;
228      }
229      return Math.Sqrt(distance);
230    }
231  }
232}
Note: See TracBrowser for help on using the repository browser.