Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3057_DynamicALPS/backup/17032020/HeuristicLab.Algorithms.DynamicALPS/3.4/DynamicALPSUtil.cs @ 17479

Last change on this file since 17479 was 17479, checked in by kyang, 4 years ago

#3057

  1. upload the latest version of ALPS with SMS-EMOA
  2. upload the related dynamic test problems (dynamic, single-objective symbolic regression), written by David Daninel.
File size: 8.3 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.DynamicALPS
29{
30  public static class DynamicALPSUtil
31  {
32    public static void QuickSort(double[] array, int[] idx, int from, int to)
33    {
34      if (from < to)
35      {
36        double temp = array[to];
37        int tempIdx = idx[to];
38        int i = from - 1;
39        for (int j = from; j < to; j++)
40        {
41          if (array[j] <= temp)
42          {
43            i++;
44            double tempValue = array[j];
45            array[j] = array[i];
46            array[i] = tempValue;
47            int tempIndex = idx[j];
48            idx[j] = idx[i];
49            idx[i] = tempIndex;
50          }
51        }
52        array[to] = array[i + 1];
53        array[i + 1] = temp;
54        idx[to] = idx[i + 1];
55        idx[i + 1] = tempIdx;
56        QuickSort(array, idx, from, i);
57        QuickSort(array, idx, i + 1, to);
58      }
59    }
60
61    public static void MinFastSort(double[] x, int[] idx, int n, int m)
62    {
63      for (int i = 0; i < m; i++)
64      {
65        for (int j = i + 1; j < n; j++)
66        {
67          if (x[i] > x[j])
68          {
69            double temp = x[i];
70            x[i] = x[j];
71            x[j] = temp;
72            int id = idx[i];
73            idx[i] = idx[j];
74            idx[j] = id;
75          }
76        }
77      }
78    }
79
80    public static IList<IDynamicALPSSolution> GetSubsetOfEvenlyDistributedSolutions(IRandom random, IList<IDynamicALPSSolution> solutionList, int newSolutionListSize)
81    {
82      if (solutionList == null || solutionList.Count == 0)
83      {
84        throw new ArgumentException("Solution list is null or empty.");
85      }
86
87      return solutionList[0].Dimensions == 2
88        ? TwoObjectivesCase(solutionList, newSolutionListSize)
89        : MoreThanTwoObjectivesCase(random, solutionList, newSolutionListSize);
90    }
91
92    private static IList<IDynamicALPSSolution> TwoObjectivesCase(IList<IDynamicALPSSolution> solutionList, int newSolutionListSize)
93    {
94      var resultSolutionList = new IDynamicALPSSolution[newSolutionListSize];
95
96      // compute weight vectors
97      double[][] lambda_moead = new double[newSolutionListSize][];
98      var values = SequenceGenerator.GenerateSteps(0m, 1m, 1m / newSolutionListSize).ToArray();
99      for (int i = 0; i < newSolutionListSize; ++i)
100      {
101        var weights = new double[newSolutionListSize];
102        weights[0] = (double)values[i];
103        weights[1] = 1 - weights[0];
104
105        lambda_moead[i] = weights;
106      }
107
108      var idealPoint = new double[2];
109      foreach (var solution in solutionList)
110      {
111        // update ideal point
112        idealPoint.UpdateIdeal(solution.Qualities);
113      }
114
115      // Select the best solution for each weight vector
116      for (int i = 0; i < newSolutionListSize; i++)
117      {
118        var currentBest = solutionList[0];
119        double value = ScalarizingFitnessFunction(currentBest, lambda_moead[i], idealPoint);
120        for (int j = 1; j < solutionList.Count; j++)
121        {
122          double aux = ScalarizingFitnessFunction(solutionList[j], lambda_moead[i], idealPoint); // we are looking for the best for the weight i
123          if (aux < value)
124          { // solution in position j is better!
125            value = aux;
126            currentBest = solutionList[j];
127          }
128        }
129        resultSolutionList[i] = (DynamicALPSSolution)currentBest.Clone();
130      }
131
132      return resultSolutionList;
133    }
134
135    private static IList<IDynamicALPSSolution> MoreThanTwoObjectivesCase(IRandom random, IList<IDynamicALPSSolution> solutionList, int newSolutionListSize)
136    {
137      var resultSolutionList = new List<IDynamicALPSSolution>();
138
139      int randomIndex = random.Next(0, solutionList.Count);
140
141      var candidate = new List<IDynamicALPSSolution>();
142      resultSolutionList.Add(solutionList[randomIndex]);
143
144      for (int i = 0; i < solutionList.Count; ++i)
145      {
146        if (i != randomIndex)
147        {
148          candidate.Add(solutionList[i]);
149        }
150      }
151
152      while (resultSolutionList.Count < newSolutionListSize)
153      {
154        int index = 0;
155        var selected = candidate[0]; // it should be a next! (n <= population size!)
156        double aux = CalculateBestDistance(selected, solutionList);
157        int i = 1;
158        while (i < candidate.Count)
159        {
160          var nextCandidate = candidate[i];
161          double distanceValue = CalculateBestDistance(nextCandidate, solutionList);
162          if (aux < distanceValue)
163          {
164            index = i;
165            aux = distanceValue;
166          }
167          i++;
168        }
169
170        // add the selected to res and remove from candidate list
171        var removedSolution = candidate[index];
172        candidate.RemoveAt(index);
173        resultSolutionList.Add((DynamicALPSSolution)removedSolution.Clone());
174      }
175
176      return resultSolutionList;
177    }
178
179    private static double ScalarizingFitnessFunction(IDynamicALPSSolution currentBest, double[] lambda_moead, double[] idealPoint)
180    {
181      double maxFun = -1.0e+30;
182
183      for (int n = 0; n < idealPoint.Length; n++)
184      {
185        double diff = Math.Abs(currentBest.Qualities[n] - idealPoint[n]);
186
187        double functionValue;
188        if (lambda_moead[n] == 0)
189        {
190          functionValue = 0.0001 * diff;
191        }
192        else
193        {
194          functionValue = diff * lambda_moead[n];
195        }
196        if (functionValue > maxFun)
197        {
198          maxFun = functionValue;
199        }
200      }
201
202      return maxFun;
203    }
204
205    public static void UpdateIdeal(this double[] idealPoint, double[] point)
206    {
207      for (int i = 0; i < point.Length; ++i)
208      {
209        if (double.IsInfinity(point[i]) || double.IsNaN(point[i]))
210        {
211          continue;
212        }
213
214        if (idealPoint[i] > point[i])
215        {
216          idealPoint[i] = point[i];
217        }
218      }
219    }
220
221    public static void UpdateNadir(this double[] nadirPoint, double[] point)
222    {
223      for (int i = 0; i < point.Length; ++i)
224      {
225        if (double.IsInfinity(point[i]) || double.IsNaN(point[i]))
226        {
227          continue;
228        }
229
230        if (nadirPoint[i] < point[i])
231        {
232          nadirPoint[i] = point[i];
233        }
234      }
235    }
236
237    public static void UpdateIdeal(this double[] idealPoint, IList<IDynamicALPSSolution> solutions)
238    {
239      foreach (var s in solutions)
240      {
241        idealPoint.UpdateIdeal(s.Qualities);
242      }
243    }
244
245    public static void UpdateNadir(this double[] nadirPoint, IList<IDynamicALPSSolution> solutions)
246    {
247      foreach (var s in solutions)
248      {
249        nadirPoint.UpdateNadir(s.Qualities);
250      }
251    }
252
253    private static double CalculateBestDistance(IDynamicALPSSolution solution, IList<IDynamicALPSSolution> solutionList)
254    {
255      var best = solutionList.Min(x => EuclideanDistance(solution.Qualities, x.Qualities));
256      if (double.IsNaN(best) || double.IsInfinity(best))
257      {
258        best = double.MaxValue;
259      }
260      return best;
261    }
262
263    public static double EuclideanDistance(double[] a, double[] b)
264    {
265      if (a.Length != b.Length)
266      {
267        throw new ArgumentException("Euclidean distance: the arrays have different lengths.");
268      }
269
270      var distance = 0d;
271      for (int i = 0; i < a.Length; ++i)
272      {
273        var d = a[i] - b[i];
274        distance += d * d;
275      }
276      return Math.Sqrt(distance);
277    }
278  }
279}
Note: See TracBrowser for help on using the repository browser.