source: branches/OptimizationNetworks/HeuristicLab.Networks.IntegratedOptimization.TravelingThief/3.3/Problems/TravelingThiefProblem.cs @ 14671

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2017 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;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.BinaryVectorEncoding;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.Knapsack;
using HeuristicLab.Problems.TravelingSalesman;

namespace HeuristicLab.Networks.IntegratedOptimization.TravelingThief {
  [Item("Traveling Thief Problem (TTP)", "")]
  [Creatable(CreatableAttribute.Categories.Problems, Priority = 999)]
  [StorableClass]
  public sealed class TravelingThiefProblem : SingleObjectiveBasicProblem<MultiEncoding> {
    private const string InstanceParameterName = "Instance";

    [Storable]
    private Dictionary<int, int[]> availability;
    [Storable]
    private double minSpeed, maxSpeed, rentingRatio;
    [Storable]
    private TravelingSalesmanProblem tsp;
    [Storable]
    private BinaryKnapsackProblem ksp;

    public override bool Maximization {
      get { return true; }
    }

    public IFixedValueParameter<TextFileValue> InstanceParameter {
      get { return (IFixedValueParameter<TextFileValue>)Parameters[InstanceParameterName]; }
    }

    [StorableConstructor]
    private TravelingThiefProblem(bool deserializing) : base(deserializing) { }
    private TravelingThiefProblem(TravelingThiefProblem original, Cloner cloner) : base(original, cloner) {
      if (original.availability != null) availability = original.availability.ToDictionary(k => k.Key, v => (int[])v.Value.Clone());
      minSpeed = original.minSpeed;
      maxSpeed = original.maxSpeed;
      rentingRatio = original.rentingRatio;
      tsp = cloner.Clone(original.tsp);
      ksp = cloner.Clone(original.ksp);

      InstanceParameter.Value.ToStringChanged += InstanceParameter_Value_ToStringChanged;
    }
    public TravelingThiefProblem() {
      Parameters.Add(new FixedValueParameter<TextFileValue>(InstanceParameterName));

      InstanceParameter.Value.ToStringChanged += InstanceParameter_Value_ToStringChanged;

      Encoding.Add(new BinaryVectorEncoding("loot"))
              .Add(new PermutationEncoding("tour"));
    }


    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      InstanceParameter.Value.ToStringChanged += InstanceParameter_Value_ToStringChanged;
    }

    private void InstanceParameter_Value_ToStringChanged(object sender, EventArgs e) {
      string filePath = InstanceParameter.Value.Value;

      TtpUtils.DistanceType distanceType;
      double[,] tspCoordinates;
      int kspCapacity;
      int[] kspItemValues, kspItemWeights;
      int[] ttpAvailability;

      TtpUtils.Import(filePath, out tspCoordinates, out distanceType,
                                out kspCapacity, out kspItemValues, out kspItemWeights,
                                out ttpAvailability, out minSpeed, out maxSpeed, out rentingRatio);

      this.availability = TtpUtils.GetAvailability(ttpAvailability);

      tsp = new TravelingSalesmanProblem();
      tsp.Coordinates = new DoubleMatrix(tspCoordinates);
      tsp.DistanceMatrix = new DistanceMatrix(TtpUtils.GetDistances(tsp.Coordinates, distanceType));

      ksp = new BinaryKnapsackProblem();
      ksp.KnapsackCapacity.Value = kspCapacity;
      ksp.Encoding.Length = kspItemValues.Length;
      ksp.Values = new IntArray(kspItemValues);
      ksp.Weights = new IntArray(kspItemWeights);

      Encoding.Encodings.OfType<BinaryVectorEncoding>().Single().Length = ksp.Encoding.Length;
      Encoding.Encodings.OfType<PermutationEncoding>().Single().Length = tsp.Coordinates.Rows;
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new TravelingThiefProblem(this, cloner);
    }

    public override double Evaluate(Individual individual, IRandom random) {
      var binaryVector = individual.BinaryVector();
      var permutation = individual.Permutation();
      return TtpUtils.Evaluate(tsp, permutation.ToArray(), ksp, binaryVector.ToArray(), availability, rentingRatio, minSpeed, maxSpeed);
    }

    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
      base.Analyze(individuals, qualities, results, random);
      var orderedIndividuals = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q }).OrderBy(z => z.Quality);
      var best = Maximization ? orderedIndividuals.Last() : orderedIndividuals.First();
      var bestIndividual = best.Individual;
      var bestQuality = best.Quality;

      if (!results.ContainsKey("Best TTP Quality")) {
        results.Add(new Result("Best TTP Quality", typeof(DoubleValue)));
        results.Add(new Result("Best Tour", typeof(PathTSPTour)));
        results.Add(new Result("Best Loot", typeof(KnapsackSolution)));
      }
      results["Best TTP Quality"].Value = new DoubleValue(bestQuality);
      results["Best Tour"].Value = new PathTSPTour(
        (DoubleMatrix)tsp.Coordinates.Clone(),
        (Permutation)bestIndividual.Permutation().Clone(),
        new DoubleValue(double.NaN)
      );
      results["Best Loot"].Value = new KnapsackSolution(
        (BinaryVector)bestIndividual.BinaryVector().Clone(),
        new DoubleValue(double.NaN),
        (IntValue)ksp.KnapsackCapacity.Clone(),
        (IntArray)ksp.Weights.Clone(),
        (IntArray)ksp.Values.Clone()
      );
    }
  }
}