source: branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/Algorithms/DirectedWalk.cs @ 17915

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2018 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;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;

namespace HeuristicLab.Analysis.FitnessLandscape {
  /// <summary>
  /// A generic implementation of a directed walk that can still be used in an efficient manner.
  /// </summary>
  /// <remarks>
  /// The algorithm is only implemented for use in the API
  /// </remarks>
  /// <typeparam name="T">The type of the solution encoding.</typeparam>
  public static class DirectedWalk<T> where T : IDeepCloneable {
    /// <summary>
    /// Provides regular directed walks between two solutions.
    /// </summary>
    /// <param name="maximization">Whether the problem is a maximization or minimization problem.</param>
    /// <param name="distFunc">The distance function that compares two solutions.</param>
    /// <param name="neighborFunc">The neighborhood functions that returns _all_ neighbors of a solution.</param>
    /// <param name="start">The starting solution (to which distance should be increased in every step).</param>
    /// <param name="startFitness">Fitness value of the starting solution.</param>
    /// <param name="target">The destination solution (to which distance should be decreased in every step).</param>
    /// <param name="firstImprovement">Whether the walk should choose the first improving neighbor instead of scanning the whole neighborhood.</param>
    /// <returns>The trail of the directed walk including start and target solution.</returns>
    public static IEnumerable<Tuple<T, double>> Walk(bool maximization, Func<T, T, double> distFunc, Func<Tuple<T, double>, IEnumerable<Tuple<T, double>>> neighborFunc, T start, double startFitness, T target, bool firstImprovement = false) {
      Func<T, T, bool> restriction = (current, neighbor) => distFunc(neighbor, target) < distFunc(current, target);
      if (firstImprovement)
        return DoFirstImprovementWalk(maximization, neighborFunc, start, startFitness, restriction);
      return DoBestImprovementWalk(maximization, neighborFunc, start, startFitness, restriction);
    }

    /// <summary>
    /// Provides regular directed walks between two solutions when already a restricted neighborhood is given.
    /// </summary>
    /// <param name="maximization">Whether the problem is a maximization or minimization problem.</param>
    /// <param name="restrictedNeighborFunc">The neighborhood functions that returns only those neighbors that move closer to some target solution.</param>
    /// <param name="start">The starting solution.</param>
    /// <param name="startFitness">Fitness value of the starting solution.</param>
    /// <param name="firstImprovement">Whether the walk should choose the first improving neighbor instead of scanning the whole neighborhood.</param>
    /// <returns>The trail of the directed walk including start solution (and potentially target solution if it was part of the final restricted neighborhood).</returns>
    public static IEnumerable<Tuple<T, double>> WalkRestricted(bool maximization, Func<Tuple<T, double>, IEnumerable<Tuple<T, double>>> restrictedNeighborFunc, T start, double startFitness, bool firstImprovement = false) {
      if (firstImprovement)
        return DoFirstImprovementWalk(maximization, restrictedNeighborFunc, start, startFitness, (_, __) => true);
      return DoBestImprovementWalk(maximization, restrictedNeighborFunc, start, startFitness, (_, __) => true);
    }

    /// <summary>
    /// Provides inverse directed walks away from a starting solution.
    /// </summary>
    /// <param name="maximization">Whether the problem is a maximization or minimization problem.</param>
    /// <param name="distFunc">The distance function that compares two solutions.</param>
    /// <param name="neighborFunc">The neighborhood functions that returns _all_ neighbors of a solution.</param>
    /// <param name="start">The starting solution (to which distance should be increased in every step).</param>
    /// <param name="startFitness">Fitness value of the starting solution.</param>
    /// <param name="firstImprovement">Whether the walk should choose the first improving neighbor instead of scanning the whole neighborhood.</param>
    /// <returns>The trail of the directed walk including start solution.</returns>
    public static IEnumerable<Tuple<T, double>> InverseWalk(bool maximization, Func<T, T, double> distFunc, Func<Tuple<T, double>, IEnumerable<Tuple<T, double>>> neighborFunc, T start, double startFitness, bool firstImprovement = false) {
      Func<T, T, bool> inverseRestriction = (current, neighbor) => distFunc(neighbor, start) > distFunc(current, start);
      if (firstImprovement)
        return DoFirstImprovementWalk(maximization, neighborFunc, start, startFitness, inverseRestriction);
      return DoBestImprovementWalk(maximization, neighborFunc, start, startFitness, inverseRestriction);
    }

    /// <summary>
    /// Provides inverse directed walks away from a starting solution when already a restricted neighborhood is given.
    /// </summary>
    /// <param name="maximization">Whether the problem is a maximization or minimization problem.</param>
    /// <param name="restrictedNeighborFunc">The neighborhood functions that returns only those neighbors that move away from the start solution.</param>
    /// <param name="start">The starting solution.</param>
    /// <param name="startFitness">Fitness value of the starting solution.</param>
    /// <param name="firstImprovement">Whether the walk should choose the first improving neighbor instead of scanning the whole neighborhood.</param>
    /// <returns>The trail of the directed walk including start solution.</returns>
    public static IEnumerable<Tuple<T, double>> InverseWalkRestricted(bool maximization, Func<Tuple<T, double>, IEnumerable<Tuple<T, double>>> restrictedNeighborFunc, T start, double startFitness, bool firstImprovement = false) {
      if (firstImprovement)
        return DoFirstImprovementWalk(maximization, restrictedNeighborFunc, start, startFitness, (_, __) => true);
      return DoBestImprovementWalk(maximization, restrictedNeighborFunc, start, startFitness, (_, __) => true);
    }

    private static IEnumerable<Tuple<T, double>> DoBestImprovementWalk(bool maximization, Func<Tuple<T, double>, IEnumerable<Tuple<T, double>>> neighborFunc, T start, double startFitness, Func<T, T, bool> restriction) {
      var current = Tuple.Create(start, startFitness);

      while (true) {
        yield return current;

        var iterator = neighborFunc(current).Where(n => restriction(current.Item1, n.Item1)).GetEnumerator();
        if (!iterator.MoveNext()) yield break;

        current = Tuple.Create((T)iterator.Current.Item1.Clone(), iterator.Current.Item2);

        while (iterator.MoveNext()) {
          var other = iterator.Current;
          if (maximization && other.Item2 > current.Item2 || !maximization && other.Item2 < current.Item2) {
            current = Tuple.Create((T)other.Item1.Clone(), other.Item2);
          }
        }
      }
    }

    private static IEnumerable<Tuple<T, double>> DoFirstImprovementWalk(bool maximization, Func<Tuple<T, double>, IEnumerable<Tuple<T, double>>> neighborFunc, T start, double startFitness, Func<T, T, bool> restriction) {
      var current = Tuple.Create(start, startFitness);

      while (true) {
        yield return current;

        var iterator = neighborFunc(current).Where(n => restriction(current.Item1, n.Item1)).GetEnumerator();
        if (!iterator.MoveNext()) yield break;

        var prevFitness = current.Item2;

        current = Tuple.Create((T)iterator.Current.Item1.Clone(), iterator.Current.Item2);

        if (maximization && current.Item2 > prevFitness || !maximization && current.Item2 < prevFitness)
          continue;

        while (iterator.MoveNext()) {
          var other = iterator.Current;
          if (maximization && other.Item2 > current.Item2 || !maximization && other.Item2 < current.Item2) {
            current = Tuple.Create((T)other.Item1.Clone(), other.Item2);

            if (maximization && current.Item2 > prevFitness || !maximization && current.Item2 < prevFitness)
              break;
          }
        }
      }
    }
  }
}