source: branches/HeuristicLab.Problems.MultiObjectiveTestFunctions/HeuristicLab.Problems.MultiObjectiveTestFunctions/3.3/NonDominatedSelect.cs @ 13562

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System.Collections.Generic;
using HeuristicLab.Core;
using HeuristicLab.Encodings.RealVectorEncoding;

namespace HeuristicLab.Problems.MultiObjectiveTestFunction {

  public class NonDominatedSelect {
    private enum DominationResult { Dominates, IsDominated, IsNonDominated };


    public static RealVector[] selectNonDominatedVectors(RealVector[] qualities, bool[] maximization, bool dominateOnEqualQualities) {
      int populationSize = qualities.Length;

      List<RealVector> front = new List<RealVector>();
      foreach (RealVector row in qualities) {
        bool insert = true;
        for (int i = 0; i < front.Count; i++) {
          DominationResult res = Dominates(front[i], row, maximization, dominateOnEqualQualities);
          if (res == DominationResult.Dominates) { insert = false; break; }           //Vector domiates Row
          else if (res == DominationResult.IsDominated) {   //Row dominates Vector
            front.RemoveRange(i, 1);
          }
        }
        if (insert) {
          front.Add(new RealVector(row));
        }
      }

      return front.ToArray();
    }

    public static RealVector[] selectNonDominatedRows(double[][] qualities, bool[] maximization, bool dominateOnEqualQualities) {
      int populationSize = qualities.Length;

      List<RealVector> front = new List<RealVector>();
      foreach (double[] row in qualities) {
        bool insert = true;
        for (int i = 0; i < front.Count; i++) {
          DominationResult res = Dominates(front[i], row, maximization, dominateOnEqualQualities);
          if (res == DominationResult.Dominates) { insert = false; break; }           //Vector domiates Row
          else if (res == DominationResult.IsDominated) {   //Row dominates Vector
            front.RemoveRange(i, 1);
          } 
        }
        if (insert) {
          front.Add(new RealVector(row));
        }
      }

      return front.ToArray();
    }

    private static DominationResult Dominates(RealVector left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
      if (dominateOnEqualQualities) {
        var equal = true;
        for (int i = 0; i < left.Length; i++) {
          if (left[i] != right[i]) {
            equal = false;
            break;
          }
        }
        if (equal) return DominationResult.Dominates;
      }

      bool leftIsBetter = false, rightIsBetter = false;
      for (int i = 0; i < left.Length; i++) {
        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
        if (leftIsBetter && rightIsBetter) break;
      }

      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
      return DominationResult.IsNonDominated;
    }

    private static DominationResult Dominates(RealVector left, RealVector right, bool[] maximizations, bool dominateOnEqualQualities) {
      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
      if (dominateOnEqualQualities) {
        var equal = true;
        for (int i = 0; i < left.Length; i++) {
          if (left[i] != right[i]) {
            equal = false;
            break;
          }
        }
        if (equal) return DominationResult.Dominates;
      }

      bool leftIsBetter = false, rightIsBetter = false;
      for (int i = 0; i < left.Length; i++) {
        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
        if (leftIsBetter && rightIsBetter) break;
      }

      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
      return DominationResult.IsNonDominated;
    }

    private static bool IsDominated(double left, double right, bool maximization) {
      return maximization && left < right
        || !maximization && left > right;
    }

    private static void AddToFront(IScope p, List<ScopeList> fronts, int i) {
      if (i == fronts.Count) fronts.Add(new ScopeList());
      fronts[i].Add(p);
    }

  }
}