1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 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 System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Encodings.RealVectorEncoding;


28  using HeuristicLab.Optimization;


29  using HEAL.Attic;


30 


31  namespace HeuristicLab.Algorithms.MOCMAEvolutionStrategy {


32  [Item("MinimalDistanceIndicator", "Selection of Offspring based on distance to nearest neighbour")]


33  [StorableType("FBBD4517164C4DEEB87D49B99172EDF4")]


34  internal class MinimalDistanceIndicator : Item, IIndicator {


35 


36  #region Constructor and Cloning


37  [StorableConstructor]


38  protected MinimalDistanceIndicator(StorableConstructorFlag _) : base(_) { }


39  protected MinimalDistanceIndicator(MinimalDistanceIndicator original, Cloner cloner) : base(original, cloner) { }


40  public override IDeepCloneable Clone(Cloner cloner) { return new MinimalDistanceIndicator(this, cloner); }


41  public MinimalDistanceIndicator() { }


42  #endregion


43 


44  public int LeastContributer(IReadOnlyList<Individual> front, MultiObjectiveBasicProblem<RealVectorEncoding> problem) {


45  var extracted = front.Select(x => x.PenalizedFitness).ToArray();


46  if (extracted.Length <= 2) return 0;


47  var distances = CalcDistances(extracted);


48  var mindexI = 0;


49  var mindexJ = 0;


50  var min = double.MaxValue;


51  for (var i = 0; i < extracted.Length; i++) {


52  var d = double.MaxValue;


53  var minj = 0;


54  for (var j = 0; j < extracted.Length; j++) {


55  if (i == j) continue;


56  var d1 = distances[i, j];


57  if (!(d1 < d)) continue;


58  minj = j;


59  d = d1;


60  }


61  if (!(d < min)) continue;


62  min = d;


63  mindexI = i;


64  mindexJ = minj;


65  }


66 


67  //break tie with distance to second nearest


68  var minI = double.MaxValue;


69  var minJ = double.MaxValue;


70 


71  for (var i = 0; i < extracted.Length; i++) {


72  double d;


73  if (mindexI != i) {


74  d = distances[mindexI, i];


75  if (!d.IsAlmost(min)) minI = Math.Min(minI, d);


76  }


77  if (mindexJ == i) continue;


78  d = distances[mindexJ, i];


79  if (!d.IsAlmost(min)) minJ = Math.Min(minJ, d);


80  }


81 


82  //find min


83  return minI < minJ ? mindexI : mindexJ;


84  }


85 


86  #region Helpers


87  private static double[,] CalcDistances(IReadOnlyList<double[]> extracted) {


88  var res = new double[extracted.Count, extracted.Count];


89  for (var i = 0; i < extracted.Count; i++)


90  for (var j = 0; j < i; j++)


91  res[i, j] = res[j, i] = Dist(extracted[i], extracted[j]);


92  return res;


93  }


94 


95  private static double Dist(IEnumerable<double> a, IEnumerable<double> b) {


96  return Math.Sqrt(a.Zip(b, (x, y) => (x  y) * (x  y)).Sum());


97  }


98  #endregion


99  }


100  }

