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

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

#2987: Create separate plugin for MOEA/D

File size: 6.8 KB
Line 
1using HeuristicLab.Common;
2using HeuristicLab.Core;
3using System;
4using System.Collections.Generic;
5using System.Linq;
6
7namespace HeuristicLab.Algorithms.MOEAD {
8  public static class MOEADUtil {
9    public static void QuickSort(double[] array, int[] idx, int from, int to) {
10      if (from < to) {
11        double temp = array[to];
12        int tempIdx = idx[to];
13        int i = from - 1;
14        for (int j = from; j < to; j++) {
15          if (array[j] <= temp) {
16            i++;
17            double tempValue = array[j];
18            array[j] = array[i];
19            array[i] = tempValue;
20            int tempIndex = idx[j];
21            idx[j] = idx[i];
22            idx[i] = tempIndex;
23          }
24        }
25        array[to] = array[i + 1];
26        array[i + 1] = temp;
27        idx[to] = idx[i + 1];
28        idx[i + 1] = tempIdx;
29        QuickSort(array, idx, from, i);
30        QuickSort(array, idx, i + 1, to);
31      }
32    }
33
34    public static void MinFastSort(double[] x, int[] idx, int n, int m) {
35      for (int i = 0; i < m; i++) {
36        for (int j = i + 1; j < n; j++) {
37          if (x[i] > x[j]) {
38            double temp = x[i];
39            x[i] = x[j];
40            x[j] = temp;
41            int id = idx[i];
42            idx[i] = idx[j];
43            idx[j] = id;
44          }
45        }
46      }
47    }
48
49    public static IList<IMOEADSolution> GetSubsetOfEvenlyDistributedSolutions(IRandom random, IList<IMOEADSolution> solutionList, int newSolutionListSize) {
50      if (solutionList == null || solutionList.Count == 0) {
51        throw new ArgumentException("Solution list is null or empty.");
52      }
53
54      return solutionList[0].Dimensions == 2
55        ? TwoObjectivesCase(solutionList, newSolutionListSize)
56        : MoreThanTwoObjectivesCase(random, solutionList, newSolutionListSize);
57    }
58
59    private static IList<IMOEADSolution> TwoObjectivesCase(IList<IMOEADSolution> solutionList, int newSolutionListSize) {
60      var resultSolutionList = new IMOEADSolution[newSolutionListSize];
61
62      // compute weight vectors
63      double[][] lambda = new double[newSolutionListSize][];
64      var values = SequenceGenerator.GenerateSteps(0m, 1m, 1m / newSolutionListSize).ToArray();
65      for (int i = 0; i < newSolutionListSize; ++i) {
66        var weights = new double[newSolutionListSize];
67        weights[0] = (double)values[i];
68        weights[1] = 1 - weights[0];
69
70        lambda[i] = weights;
71      }
72
73      var idealPoint = new double[2];
74      foreach (var solution in solutionList) {
75        // update ideal point
76        idealPoint.UpdateIdeal(solution.Qualities);
77      }
78
79      // Select the best solution for each weight vector
80      for (int i = 0; i < newSolutionListSize; i++) {
81        var currentBest = solutionList[0];
82        double value = ScalarizingFitnessFunction(currentBest, lambda[i], idealPoint);
83        for (int j = 1; j < solutionList.Count; j++) {
84          double aux = ScalarizingFitnessFunction(solutionList[j], lambda[i], idealPoint); // we are looking for the best for the weight i
85          if (aux < value) { // solution in position j is better!
86            value = aux;
87            currentBest = solutionList[j];
88          }
89        }
90        resultSolutionList[i] = (MOEADSolution)currentBest.Clone();
91      }
92
93      return resultSolutionList;
94    }
95
96    private static IList<IMOEADSolution> MoreThanTwoObjectivesCase(IRandom random, IList<IMOEADSolution> solutionList, int newSolutionListSize) {
97      var resultSolutionList = new List<IMOEADSolution>();
98
99      int randomIndex = random.Next(0, solutionList.Count);
100
101      var candidate = new List<IMOEADSolution>();
102      resultSolutionList.Add(solutionList[randomIndex]);
103
104      for (int i = 0; i < solutionList.Count; ++i) {
105        if (i != randomIndex) {
106          candidate.Add(solutionList[i]);
107        }
108      }
109
110      while (resultSolutionList.Count < newSolutionListSize) {
111        int index = 0;
112        var selected = candidate[0]; // it should be a next! (n <= population size!)
113        double aux = CalculateBestDistance(selected, solutionList);
114        int i = 1;
115        while (i < candidate.Count) {
116          var nextCandidate = candidate[i];
117          double distanceValue = CalculateBestDistance(nextCandidate, solutionList);
118          if (aux < distanceValue) {
119            index = i;
120            aux = distanceValue;
121          }
122          i++;
123        }
124
125        // add the selected to res and remove from candidate list
126        var removedSolution = candidate[index];
127        candidate.RemoveAt(index);
128        resultSolutionList.Add((MOEADSolution)removedSolution.Clone());
129      }
130
131      return resultSolutionList;
132    }
133
134    private static double ScalarizingFitnessFunction(IMOEADSolution currentBest, double[] lambda, double[] idealPoint) {
135      double maxFun = -1.0e+30;
136
137      for (int n = 0; n < idealPoint.Length; n++) {
138        double diff = Math.Abs(currentBest.Qualities[n] - idealPoint[n]);
139
140        double functionValue;
141        if (lambda[n] == 0) {
142          functionValue = 0.0001 * diff;
143        } else {
144          functionValue = diff * lambda[n];
145        }
146        if (functionValue > maxFun) {
147          maxFun = functionValue;
148        }
149      }
150
151      return maxFun;
152    }
153
154    public static void UpdateIdeal(this double[] idealPoint, double[] point) {
155      for (int i = 0; i < point.Length; ++i) {
156        if (idealPoint[i] > point[i]) {
157          idealPoint[i] = point[i];
158        }
159      }
160    }
161
162    public static void UpdateNadir(this double[] nadirPoint, double[] point) {
163      for (int i = 0; i < point.Length; ++i) {
164        if (nadirPoint[i] < point[i]) {
165          nadirPoint[i] = point[i];
166        }
167      }
168    }
169
170    public static void UpdateIdeal(this double[] idealPoint, IList<IMOEADSolution> solutions) {
171      foreach (var s in solutions) {
172        idealPoint.UpdateIdeal(s.Qualities);
173      }
174    }
175
176    public static void UpdateNadir(this double[] nadirPoint, IList<IMOEADSolution> solutions) {
177      foreach (var s in solutions) {
178        nadirPoint.UpdateNadir(s.Qualities);
179      }
180    }
181
182    private static double CalculateBestDistance(IMOEADSolution solution, IList<IMOEADSolution> solutionList) {
183      var best = solutionList.Min(x => EuclideanDistance(solution.Qualities, x.Qualities));
184      if (double.IsNaN(best) || double.IsInfinity(best)) {
185        best = double.MaxValue;
186      }
187      return best;
188    }
189
190    public static double EuclideanDistance(double[] a, double[] b) {
191      if (a.Length != b.Length) {
192        throw new ArgumentException("Euclidean distance: the arrays have different lengths.");
193      }
194
195      var distance = 0d;
196      for (int i = 0; i < a.Length; ++i) {
197        var d = a[i] - b[i];
198        distance += d * d;
199      }
200      return Math.Sqrt(distance);
201    }
202  }
203}
Note: See TracBrowser for help on using the repository browser.