#region License Information /* HeuristicLab * Copyright (C) 2002-2016 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 . */ #endregion using System; using System.Collections.Generic; using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.GeneralizedQuadraticAssignment; using HeuristicLab.Random; namespace HeuristicLab.Analysis.FitnessLandscape { [Item("Directed Walk (GQAP-specific)", "")] [StorableClass] public class GQAPDirectedWalk : CharacteristicCalculator { public IFixedValueParameter PathsParameter { get { return (IFixedValueParameter)Parameters["Paths"]; } } public IFixedValueParameter BestImprovementParameter { get { return (IFixedValueParameter)Parameters["BestImprovement"]; } } public IValueParameter SeedParameter { get { return (IValueParameter)Parameters["Seed"]; } } public IFixedValueParameter LocalOptimaParameter { get { return (IFixedValueParameter)Parameters["LocalOptima"]; } } public int Paths { get { return PathsParameter.Value.Value; } set { PathsParameter.Value.Value = value; } } public bool BestImprovement { get { return BestImprovementParameter.Value.Value; } set { BestImprovementParameter.Value.Value = value; } } public int? Seed { get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; } set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; } } public bool LocalOptima { get { return LocalOptimaParameter.Value.Value; } set { LocalOptimaParameter.Value.Value = value; } } [StorableConstructor] private GQAPDirectedWalk(bool deserializing) : base(deserializing) { } private GQAPDirectedWalk(GQAPDirectedWalk original, Cloner cloner) : base(original, cloner) { } public GQAPDirectedWalk() { characteristics.AddRange(new[] { "1Shift.Sharpness", "1Shift.Bumpiness", "1Shift.Flatness" } .Select(x => new StringValue(x)).ToList()); Parameters.Add(new FixedValueParameter("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50))); Parameters.Add(new FixedValueParameter("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true))); Parameters.Add(new OptionalValueParameter("Seed", "The seed for the random number generator.")); Parameters.Add(new FixedValueParameter("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false))); } public override IDeepCloneable Clone(Cloner cloner) { return new GQAPDirectedWalk(this, cloner); } public override bool CanCalculate() { return Problem is GQAP; } public override IEnumerable Calculate() { IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister(); var gqap = (GQAP)Problem; List assignments = CalculateRelinkingPoints(random, gqap, Paths, LocalOptima); var trajectories = Run(random, (GQAP)Problem, assignments, BestImprovement).ToList(); var result = IntegerVectorPathAnalysis.GetCharacteristics(trajectories); foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) { if (chara == "1Shift.Sharpness") yield return new Result("1Shift.Sharpness", new DoubleValue(result.Sharpness)); if (chara == "1Shift.Bumpiness") yield return new Result("1Shift.Bumpiness", new DoubleValue(result.Bumpiness)); if (chara == "1Shift.Flatness") yield return new Result("1Shift.Flatness", new DoubleValue(result.Flatness)); } } public static List CalculateRelinkingPoints(IRandom random, GQAP gqap, int pathCount, bool localOptima) { var assign = new IntegerVector(gqap.ProblemInstance.Demands.Length, random, 0, gqap.ProblemInstance.Capacities.Length); if (localOptima) { var eval = gqap.ProblemInstance.Evaluate(assign); var fit = gqap.ProblemInstance.ToSingleObjective(eval); OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals); } var points = new List { assign }; while (points.Count < pathCount + 1) { assign = (IntegerVector)points.Last().Clone(); RelocateEquipmentManipluator.Apply(random, assign, gqap.ProblemInstance.Capacities.Length, 0); if (localOptima) { var eval = gqap.ProblemInstance.Evaluate(assign); var fit = gqap.ProblemInstance.ToSingleObjective(eval); OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals); } if (HammingSimilarityCalculator.CalculateSimilarity(points.Last(), assign) < 0.75) points.Add(assign); } return points; } public static IEnumerable>> Run(IRandom random, GQAP gqap, IEnumerable points, bool bestImprovement = true) { var iter = points.GetEnumerator(); if (!iter.MoveNext()) yield break; var start = iter.Current; while (iter.MoveNext()) { var end = iter.Current; var walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList(); yield return walk.ToList(); start = end; } // end paths } private static IEnumerable> BestDirectedWalk(GQAP gqap, IntegerVector start, IntegerVector end) { var N = gqap.ProblemInstance.Demands.Length; var sol = start; var evaluation = gqap.ProblemInstance.Evaluate(start); var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation); yield return Tuple.Create(sol, fitness); var reassignments = Enumerable.Range(0, N).Select(x => { if (start[x] == end[x]) return null; var r = new int[N]; r[x] = end[x] + 1; return r; }).ToArray(); var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List(1) { x }).ToArray(); for (var step = 0; step < N; step++) { var bestFitness = double.MaxValue; Evaluation bestEvaluation = null; var bestIndex = -1; sol = (IntegerVector)sol.Clone(); for (var index = 0; index < N; index++) { if (sol[index] == end[index]) continue; var oneMove = new NMove(reassignments[index], indices[index]); var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance); var fit = gqap.ProblemInstance.ToSingleObjective(eval); if (fit < bestFitness) { // QAP is minimization bestFitness = fit; bestEvaluation = eval; bestIndex = index; } } if (bestIndex >= 0) { sol[bestIndex] = end[bestIndex]; fitness = bestFitness; evaluation = bestEvaluation; yield return Tuple.Create(sol, fitness); } else break; } } private static IEnumerable> FirstDirectedWalk(IRandom random, GQAP gqap, IntegerVector start, IntegerVector end) { var N = gqap.ProblemInstance.Demands.Length; var sol = start; var evaluation = gqap.ProblemInstance.Evaluate(start); var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation); yield return Tuple.Create(sol, fitness); var reassignments = Enumerable.Range(0, N).Select(x => { if (start[x] == end[x]) return null; var r = new int[N]; r[x] = end[x] + 1; return r; }).ToArray(); var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List(1) { x }).ToArray(); // randomize the order in which improvements are tried var order = Enumerable.Range(0, N).Shuffle(random).ToArray(); for (var step = 0; step < N; step++) { var bestFitness = double.MaxValue; Evaluation bestEvaluation = null; var bestIndex = -1; sol = (IntegerVector)sol.Clone(); for (var i = 0; i < N; i++) { var index = order[i]; if (sol[index] == end[index]) continue; var oneMove = new NMove(reassignments[index], indices[index]); var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance); var fit = gqap.ProblemInstance.ToSingleObjective(eval); if (fit < bestFitness) { // GQAP is minimization bestFitness = fit; bestEvaluation = evaluation; bestIndex = index; if (fit < fitness) break; } } if (bestIndex >= 0) { sol[bestIndex] = end[bestIndex]; fitness = bestFitness; evaluation = bestEvaluation; yield return Tuple.Create(sol, fitness); } else break; } } } }