1 | using HeuristicLab.Common;
|
---|
2 | using HeuristicLab.Core;
|
---|
3 | using System;
|
---|
4 | using System.Collections.Generic;
|
---|
5 | using System.Linq;
|
---|
6 |
|
---|
7 | namespace 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 | }
|
---|