[16560] | 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 | }
|
---|