source: branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/Comparators/Crowding.cs @ 13620

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Data;
using HeuristicLab.Encodings.RealVectorEncoding;
using HeuristicLab.Problems.MultiObjectiveTestFunctions.Comparators;

namespace HeuristicLab.Problems.MultiObjectiveTestFunctions {

  /// <summary>
  /// Crowding distance d(x,A) is usually defined between a point x and a set of points A
  /// d(x,A) is then a weighted sum over all dimensions where for each dimension the next larger and the next smaller Point to x are subtracted
  /// I extended the concept and defined the Crowding distance of a front A as the mean of the crowding distances of every point x in A 
  /// C(A) = mean(d(x,A)) where x in A  and d(x,A) is not infinite 
  /// </summary>
  public class Crowding : IMultiObjectiveDistance {
    private double[,] bounds;

    public Crowding(double[,] bounds) {
      this.bounds = bounds;

    }

    public static double GetDistance(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront, double[,] bounds) {
      return new Crowding(bounds).Compare(front, optimalFront);
    }

    public static double GetCrowding(IEnumerable<double[]> front, double[,] bounds) {
      return new Crowding(bounds).Get(front);
    }

    public double Get(IEnumerable<double[]> front) {
      double sum = 0;
      int c = 0;
      foreach (double[] point in front) {
        double d = CalcCrowding(point, front);
        if (!Double.IsInfinity(d)) {
          sum += d;
          c++;
        }
      }
      return c==0?Double.PositiveInfinity:sum / c;
    }

    public double Compare(IEnumerable<double[]> front, IEnumerable<double[]> optimalFront) {
      return Get(optimalFront) - Get(front);
    }

    private double CalcCrowding(double[] point, IEnumerable<double[]> list) {
      double sum = 0;
      for (int i = 0; i < point.Length; i++) {
        sum += CalcCrowding(point, list, i);
      }
      return sum;
    }

    private double CalcCrowding(double[] point, IEnumerable<double[]> list, int dim) {
      double fmax = bounds[dim % bounds.GetLength(0), 1];
      double fmin = bounds[dim % bounds.GetLength(0), 0];
      double[][] arr = list.ToArray();  //TODO Shady
      Array.Sort<double[]>(arr, Utilities.getDimensionComparer(dim, false));
      if (arr[0][dim] == point[0] || arr[arr.Length - 1][dim] == point[0]) return Double.PositiveInfinity;
      int pos = Utilities.binarySearch(point[dim], arr, dim);
      if (pos == 0 || pos == list.Count()-1) return Double.PositiveInfinity;
      return (arr[pos + 1][dim] - arr[pos - 1][dim]) / (fmax - fmin);
    }

  }
}