source: branches/VRP/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Potvin/Manipulators/PotvinManipulator.cs @ 6753

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2010 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 HeuristicLab.Core;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Problems.VehicleRouting.Encodings.General;
using HeuristicLab.Problems.VehicleRouting.Interfaces;
using HeuristicLab.Common;

namespace HeuristicLab.Problems.VehicleRouting.Encodings.Potvin {
  [Item("PotvinManipulator", "A VRP manipulation operation.")]
  [StorableClass]
  public abstract class PotvinManipulator : VRPManipulator, IStochasticOperator, IPotvinOperator {
    public ILookupParameter<IRandom> RandomParameter {
      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    }

    public IValueParameter<BoolValue> AllowInfeasibleSolutions {
      get { return (IValueParameter<BoolValue>)Parameters["AllowInfeasibleSolutions"]; }
    }

    [StorableConstructor]
    protected PotvinManipulator(bool deserializing) : base(deserializing) { }

    public PotvinManipulator() {
      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
      Parameters.Add(new ValueParameter<BoolValue>("AllowInfeasibleSolutions", "Indicates if infeasible solutions should be allowed.", new BoolValue(false)));
    }

    protected PotvinManipulator(PotvinManipulator original, Cloner cloner)
      : base(original, cloner) {
    }

    protected abstract void Manipulate(IRandom random, PotvinEncoding individual);

    protected int SelectRandomTourBiasedByLength(IRandom random, PotvinEncoding individual) {
      int tourIndex = -1;

      double sum = 0.0;
      double[] probabilities = new double[individual.Tours.Count];
      for (int i = 0; i < individual.Tours.Count; i++) {
        probabilities[i] = 1.0 / ((double)individual.Tours[i].Stops.Count / (double)ProblemInstance.Cities.Value);
        sum += probabilities[i];
      }

      for (int i = 0; i < probabilities.Length; i++)
        probabilities[i] = probabilities[i] / sum;

      double rand = random.NextDouble();
      double cumulatedProbabilities = 0.0;
      int index = 0;
      while (tourIndex == -1 && index < probabilities.Length) {
        if (cumulatedProbabilities <= rand && rand <= cumulatedProbabilities + probabilities[index])
          tourIndex = index;

        cumulatedProbabilities += probabilities[index];
        index++;
      }

      return tourIndex;
    }

    protected bool FindInsertionPlace(PotvinEncoding individual, int city, int routeToAvoid, bool allowInfeasible, out int route, out int place) {
      return individual.FindInsertionPlace(
        city, routeToAvoid, allowInfeasible, out route, out place);
    }
    
    public override IOperation Apply() {
      IVRPEncoding solution = VRPToursParameter.ActualValue;
      if (!(solution is PotvinEncoding)) {
        VRPToursParameter.ActualValue = PotvinEncoding.ConvertFrom(solution, ProblemInstance);
      }
      
      Manipulate(RandomParameter.ActualValue, VRPToursParameter.ActualValue as PotvinEncoding);

      return base.Apply();
    }
  }
}