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

Last change on this file since 16630 was 16630, checked in by bburlacu, 2 years ago

#2987: Migrate to new persistence. Add support for objective scaling.

File size: 7.6 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 (idealPoint[i] > point[i]) {
178          idealPoint[i] = point[i];
179        }
180      }
181    }
182
183    public static void UpdateNadir(this double[] nadirPoint, double[] point) {
184      for (int i = 0; i < point.Length; ++i) {
185        if (nadirPoint[i] < point[i]) {
186          nadirPoint[i] = point[i];
187        }
188      }
189    }
190
191    public static void UpdateIdeal(this double[] idealPoint, IList<IMOEADSolution> solutions) {
192      foreach (var s in solutions) {
193        idealPoint.UpdateIdeal(s.Qualities);
194      }
195    }
196
197    public static void UpdateNadir(this double[] nadirPoint, IList<IMOEADSolution> solutions) {
198      foreach (var s in solutions) {
199        nadirPoint.UpdateNadir(s.Qualities);
200      }
201    }
202
203    private static double CalculateBestDistance(IMOEADSolution solution, IList<IMOEADSolution> solutionList) {
204      var best = solutionList.Min(x => EuclideanDistance(solution.Qualities, x.Qualities));
205      if (double.IsNaN(best) || double.IsInfinity(best)) {
206        best = double.MaxValue;
207      }
208      return best;
209    }
210
211    public static double EuclideanDistance(double[] a, double[] b) {
212      if (a.Length != b.Length) {
213        throw new ArgumentException("Euclidean distance: the arrays have different lengths.");
214      }
215
216      var distance = 0d;
217      for (int i = 0; i < a.Length; ++i) {
218        var d = a[i] - b[i];
219        distance += d * d;
220      }
221      return Math.Sqrt(distance);
222    }
223  }
224}
Note: See TracBrowser for help on using the repository browser.