source: branches/2457_ExpertSystem/WalkExporter/AdaptiveWalks.cs @ 16955

#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.Collections.Generic;
using HeuristicLab.Core;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Problems.Instances;

namespace WalkExporter {
  static class AdaptiveWalks {
    
    public static IEnumerable<double> AdaptiveWalk(IRandom random, QAPData qap, int sampleSize) {
      var sol = new Permutation(PermutationTypes.Absolute, qap.Dimension, random);
      var fit = Util.Evaluate(sol, qap);
      yield return fit;
      while (true) {
        var bestZ1 = -1;
        var bestZ2 = -1;
        var bestMove = double.MaxValue;
        for (var s = 0; s < sampleSize; s++) {
          var z1 = random.Next(qap.Dimension);
          var z2 = (z1 + random.Next(1, qap.Dimension)) % qap.Dimension;
          var move = Util.EvaluateSwap2Diff(sol, z1, z2, qap);
          if (move < bestMove) {
            bestZ1 = z1;
            bestZ2 = z2;
            bestMove = move;
          }
        }
        fit += bestMove;
        yield return fit;
        sol.Swap(bestZ1, bestZ2);
      }
    }

    public static IEnumerable<double> UpDownWalk(IRandom random, QAPData qap, int sampleSize) {
      var sol = new Permutation(PermutationTypes.Absolute, qap.Dimension, random);
      var fit = Util.Evaluate(sol, qap);
      yield return fit;
      var down = true;
      while (true) {
        int z1 = -1, z2 = -1, bestDownZ1 = -1, bestDownZ2 = -1, bestUpZ1 = -1, bestUpZ2 = -1;
        double move = 0, bestDownMove = 0, bestUpMove = 0;
        for (var s = 0; s < sampleSize; s++) {
          z1 = random.Next(qap.Dimension);
          z2 = (z1 + random.Next(1, qap.Dimension)) % qap.Dimension;
          move = Util.EvaluateSwap2Diff(sol, z1, z2, qap);
          if (move < bestDownMove) {
            bestDownZ1 = z1;
            bestDownZ2 = z2;
            bestDownMove = move;
          } else if (move > bestUpMove) {
            bestUpZ1 = z1;
            bestUpZ2 = z2;
            bestUpMove = move;
          }
        }
        // revert direction
        if (down && bestDownZ1 < 0 || !down && bestUpZ1 < 0) down = !down;

        if (down && bestDownZ1 >= 0) {
          fit += bestDownMove;
          yield return fit;
          sol.Swap(bestDownZ1, bestDownZ2);
        } else if (!down && bestUpZ1 >= 0) {
          fit += bestUpMove;
          yield return fit;
          sol.Swap(bestUpZ1, bestUpZ2);
        } else {
          // all moves neutral, make a random move , i.e. last sampled one
          fit += move;
          yield return fit;
          sol.Swap(z1, z2);
        }
      }
    }
  }
}