[16630] | 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 |
|
---|
| 22 | using HeuristicLab.Common;
|
---|
[16560] | 23 | using HeuristicLab.Core;
|
---|
| 24 | using System;
|
---|
| 25 | using System.Collections.Generic;
|
---|
| 26 | using System.Linq;
|
---|
| 27 |
|
---|
| 28 | namespace 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 | }
|
---|