# Changeset 12721 for branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3

Ignore:
Timestamp:
07/10/15 16:38:17 (5 years ago)
Message:
• Renamed analyzer (us spelling)
• Removed script
• Implemented samples unit test
• Changed solution view to use horizontal splitting, removed viewhosts
• Updated instance provider to use .NET45 zip compression
• Restructuring and reformatting
Location:
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3
Files:
1 deleted
13 edited
2 moved

Unmodified
Removed
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3

• Property svn:ignore
•  old obj Plugin.cs *.DotSettings
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Analyzers/BestOrienteeringSolutionAnalyzer.cs

 r12693 #region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. namespace HeuristicLab.Problems.Orienteering { public sealed class BestOrienteeringSolutionAnalyser : SingleSuccessorOperator, IAnalyzer { public sealed class BestOrienteeringSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer { public bool EnabledByDefault { get { return true; } [StorableConstructor] private BestOrienteeringSolutionAnalyser(bool deserializing) : base(deserializing) { } private BestOrienteeringSolutionAnalyser(BestOrienteeringSolutionAnalyser original, Cloner cloner) : base(original, cloner) { } private BestOrienteeringSolutionAnalyzer(bool deserializing) : base(deserializing) { } private BestOrienteeringSolutionAnalyzer(BestOrienteeringSolutionAnalyzer original, Cloner cloner) : base(original, cloner) { } public override IDeepCloneable Clone(Cloner cloner) { return new BestOrienteeringSolutionAnalyser(this, cloner); return new BestOrienteeringSolutionAnalyzer(this, cloner); } public BestOrienteeringSolutionAnalyser() public BestOrienteeringSolutionAnalyzer() : base() { Parameters.Add(new ScopeTreeLookupParameter("IntegerVector", "The Orienteering solutions which should be analysed."));
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs

 r11321 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. namespace HeuristicLab.Problems.Orienteering { [Item("GreedyOrienteeringTourCreator", @"The initial solution for P-VNS is generated by means of a greedy algorithm that takes into account all vertices vi that are located within the cost limit Tmax. These points are sorted in descending order regarding the sum of their objective values. Afterwards, the algorithm starts with a tour only including the starting and ending point and successively inserts the points from this list at the first position in which they can feasibly be inserted. (Schilde et. al. 2009)")] /// /// The initial solution for P-VNS is generated by means of a greedy algorithm that takes into /// account all vertices vi that are located within the cost limit Tmax. These points are sorted /// in descending order regarding the sum of their objective values. Afterwards, the algorithm /// starts with a tour only including the starting and ending point and successively inserts the /// points from this list at the first position in which they can feasibly be inserted. /// (Schilde et. al. 2009) /// [Item("GreedyOrienteeringTourCreator", @"Implements the solution creation procedure described in Schilde M., Doerner K.F., Hartl R.F., Kiechle G. 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, Volume 3, Issue 3, pp 179-201.")] [StorableClass] public sealed class GreedyOrienteeringTourCreator : IntegerVectorCreator, IOrienteeringSolutionCreator { } protected override IntegerVector Create(IRandom _, IntValue __, IntMatrix ___) { protected override IntegerVector Create(IRandom random, IntValue length, IntMatrix bounds) { int startPoint = StartingPointParameter.ActualValue.Value; int endPoint = TerminalPointParameter.ActualValue.Value; endPoint }; double length = distances[startPoint, endPoint]; double tourLength = distances[startPoint, endPoint]; // Add points in a greedy way // If the insertion would be feasible, perform it if (length + detour <= maxDistance) { if (tourLength + detour <= maxDistance) { tour.Insert(insertPosition, feasiblePoints[i]); length += detour; tourLength += detour; feasiblePoints.RemoveAt(i); insertionPerformed = true;
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/DistanceMatrix.cs

 r11320 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab.
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Evaluators/OrienteeringEvaluator.cs

 r11327 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. namespace HeuristicLab.Problems.Orienteering { [Item("OrienteeringEvaluator", "Operator to evaluate a solution to the orienteering problem.")] [StorableClass] public class OrienteeringEvaluator : InstrumentedOperator, IOrienteeringEvaluator { } public static OrienteeringEvaluation Apply(IntegerVector solution, DoubleArray scores, public static OrienteeringEvaluationResult Apply(IntegerVector solution, DoubleArray scores, DistanceMatrix distances, double maximumDistance, double pointVisitingCosts, double distancePenaltyFactor) { double quality = score - penalty; return new OrienteeringEvaluation { return new OrienteeringEvaluationResult { Quality = new DoubleValue(quality), Penalty = new DoubleValue(penalty), } public OrienteeringEvaluation Evaluate(IntegerVector solution, DoubleArray scores, public OrienteeringEvaluationResult Evaluate(IntegerVector solution, DoubleArray scores, DistanceMatrix distances, double maximumDistance, double pointVisitingCosts) { return Apply(solution, scores, distances, maximumDistance, pointVisitingCosts,
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/HeuristicLab.Problems.Orienteering-3.3.csproj

 r11327 HeuristicLab.Problems.OrienteeringHeuristicLab.Problems.Orienteering-3.3v4.0v4.5512 prompt 4 false prompt 4 false true bin\x64\Debug\ ..\..\bin\ DEBUG;TRACE full prompt MinimumRecommendedRules.ruleset false bin\x64\Release\ ..\..\bin\ TRACE true prompt MinimumRecommendedRules.ruleset false true bin\x86\Debug\ ..\..\bin\ DEBUG;TRACE full prompt MinimumRecommendedRules.ruleset false bin\x86\Release\ ..\..\bin\ TRACE true prompt MinimumRecommendedRules.ruleset false
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

 r11323 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. #endregion using System; using System.Collections.Generic; using System.Linq; namespace HeuristicLab.Problems.Orienteering { [Item("OrienteeringLocalImprovementOperator", @"Iterative improvement consists of three basic operators: shortening, vertex insert and vertex exchange. The shortening operator tries to rearrange the vertices within a tour in order to minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009)")] /// /// Iterative improvement consists of three basic operators: shortening, vertex insert and vertex /// exchange. The shortening operator tries to rearrange the vertices within a tour in order to /// minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009) /// [Item("OrienteeringLocalImprovementOperator", @"Implements the iterative improvement procedure described in Schilde M., Doerner K.F., Hartl R.F., Kiechle G. 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, Volume 3, Issue 3, pp 179-201.")] [StorableClass] public sealed class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator { bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value; bool optimizationDone = true; bool solutionChanged = true; var tour = IntegerVectorParameter.ActualValue.ToList(); // Check if the tour can be improved by adding or replacing points while (optimizationDone && localIterations.Value < maxIterations) { optimizationDone = false; while (solutionChanged && localIterations.Value < maxIterations) { solutionChanged = false; if (localIterations.Value == 0) IncludeNewPoints(tour, visitablePoints, distances, pointVisitingCosts, maxLength, scores, ref tourLength, ref tourScore, ref evaluations, ref optimizationDone); ref tourLength, ref tourScore, ref evaluations, ref solutionChanged); // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores ReplacePoints(tour, visitablePoints, distances, maxLength, scores, ref tourLength, ref tourScore, ref evaluations, ref optimizationDone); ref tourLength, ref tourScore, ref evaluations, ref solutionChanged); localIterations.Value++; private void ShortenPath(List tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) { bool optimizationDone = true; bool solutionChanged; int pathSize = tour.Count; maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2); // Perform a 2-opt while (optimizationDone) { optimizationDone = false; do { solutionChanged = false; for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; if (solutionChanged) break; for (int position = 1; position < (pathSize - blockLength); position++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; if (solutionChanged) break; evaluations++; newLength += distances[tour[position], tour[position + blockLength]]; if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse(); // Re-run the optimization optimizationDone = true; solutionChanged = true; } } } } } } while (solutionChanged); } private void IncludeNewPoints(List tour, List visitablePoints, DistanceMatrix distances, double pointVisitingCosts, double maxLength, DoubleArray scores, ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) { ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) { for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; if (solutionChanged) break; for (int i = 0; i < visitablePoints.Count; i++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; if (solutionChanged) break; evaluations++; // Re-run this optimization optimizationDone = true; solutionChanged = true; } } } } private void ReplacePoints(List tour, List visitablePoints, DistanceMatrix distances, double maxLength, DoubleArray scores, ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) { ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) { for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; if (solutionChanged) break; for (int i = 0; i < visitablePoints.Count; i++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; if (solutionChanged) break; evaluations++; // Re-run this optimization optimizationDone = true; solutionChanged = true; } }
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Interfaces/IOrienteeringEvaluator.cs

 r11327 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. ILookupParameter PenaltyParameter { get; } OrienteeringEvaluation Evaluate(IntegerVector solution, DoubleArray scores, OrienteeringEvaluationResult Evaluate(IntegerVector solution, DoubleArray scores, DistanceMatrix distances, double maximumDistance, double pointVisitingCosts); }
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Interfaces/IOrienteeringSolutionCreator.cs

 r11321 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab.
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringEvaluationResult.cs

 r12693 #region License Information /* HeuristicLab * Copyright (C) 2002-2015 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 HeuristicLab.Data; namespace HeuristicLab.Problems.Orienteering { public class OrienteeringEvaluation { public class OrienteeringEvaluationResult { public DoubleValue Quality; public DoubleValue Penalty;
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs

 r11328 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. namespace HeuristicLab.Problems.Orienteering { [Item("Orienteering Problem", "Represents a single objective Orienteering Problem.")] [Creatable("Problems")] [Item("Orienteering Problem", "Represents a single-objective Orienteering Problem.")] [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 115)] [StorableClass] public sealed class OrienteeringProblem set { BestKnownSolutionParameter.Value = value; } } private BestOrienteeringSolutionAnalyser BestOrienteeringSolutionAnalyser { get { return Operators.OfType().SingleOrDefault(); } private BestOrienteeringSolutionAnalyzer BestOrienteeringSolutionAnalyser { get { return Operators.OfType().SingleOrDefault(); } } #endregion } private void InitializeOperators() { Operators.Add(new BestOrienteeringSolutionAnalyser()); Operators.Add(new BestOrienteeringSolutionAnalyzer()); ParameterizeAnalyzer();
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringSolution.cs

 r11327 #region License Information /* HeuristicLab * Copyright (C) 2002-2015 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.Drawing;
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Plugin.cs.frame

 r11307 #region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. /// Plugin class for HeuristicLab.Problems.Orienteering. /// [Plugin("HeuristicLab.Problems.Orienteering", "3.3.10.$WCREV$")] [Plugin("HeuristicLab.Problems.Orienteering", "3.3.11.$WCREV$")] [PluginFile("HeuristicLab.Problems.Orienteering-3.3.dll", PluginFileType.Assembly)] [PluginDependency("HeuristicLab.Analysis", "3.3")]
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Properties/AssemblyInfo.cs.frame

 r11185 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. [assembly: AssemblyCompany("")] [assembly: AssemblyProduct("HeuristicLab")] [assembly: AssemblyCopyright("(c) 2002-2014 HEAL")] [assembly: AssemblyCopyright("(c) 2002-2015 HEAL")] [assembly: AssemblyTrademark("")] [assembly: AssemblyCulture("")] // by using the '*' as shown below: [assembly: AssemblyVersion("3.3.0.0")] [assembly: AssemblyFileVersion("3.3.10.$WCREV$")] [assembly: AssemblyFileVersion("3.3.11.$WCREV$")]
• ## branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs

 r11320 ﻿#region License Information /* HeuristicLab * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. namespace HeuristicLab.Problems.Orienteering { [Item("OrienteeringShakingOperator", @"The used neighborhood operator is based on a two point exchange move. A move in the k-th neighborhood consists of removing k consecutive vertices from the tour, starting at a randomly selected position. Afterwards, a sorted list of all vertices not yet included in the current tour is built. The vertices are sorted in descending order with respect to the objective value increase using the current weights. Out of the first three entries with the highest ranking in this list, one randomly selected vertex is reinserted into the current tour at the same position as the removed vertices. This way, l new vertices are inserted into the tour. The largest neighborhood is a complete exchange of all vertices on the tour. The shaking procedure does not guarantee that the new tour does not exceed the cost limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The vertices are sorted in descending order with respect to costs saved when removing the vertex from the tour. Vertices are removed as long as the cost limit is violated. (Schilde et. al. 2009)")] /// /// The used neighborhood operator is based on a two point exchange move. A move in /// the k-th neighborhood consists of removing k consecutive vertices from the tour, starting /// at a randomly selected position. Afterwards, a sorted list of all vertices not yet included /// in the current tour is built. The vertices are sorted in descending order with respect to the /// objective value increase using the current weights. Out of the first three entries with the /// highest ranking in this list, one randomly selected vertex is reinserted into the current tour /// at the same position as the removed vertices. This way, l new vertices are inserted into the /// tour. The largest neighborhood is a complete exchange of all vertices on the tour. /// The shaking procedure does not guarantee that the new tour does not exceed the cost /// limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The /// vertices are sorted in descending order with respect to costs saved when removing the vertex /// from the tour. Vertices are removed as long as the cost limit is violated. /// (Schilde et. al. 2009) /// [Item("OrienteeringShakingOperator", @"Implements the shaking procedure described in Schilde M., Doerner K.F., Hartl R.F., Kiechle G. 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, Volume 3, Issue 3, pp 179-201.")] [StorableClass] public sealed class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator { int maximumNeighborhood = initialTour.Length - 2; // neighborhood limit within [0, changable tour length - 1) maximumNeighborhood = (maximumNeighborhood > currentNeighborhood) ? currentNeighborhood : maximumNeighborhood; int neighborhood = maximumNeighborhood;//random.Next(maximumNeighborhood) + 1; int neighborhood = maximumNeighborhood; // Find all points that are not yet included in the tour and are return base.Apply(); } private void InsertPoints(List actualTour, IntegerVector initialTour, int neighborhood, List visitablePoints, IRandom random) { } } private void CleanupTour(List actualTour, DistanceMatrix distances, double maxDistance, double pointVisitingCosts) { // Sort the points on the tour according to their costs savings when removed } } // private class SavingInfo { public int Index;
Note: See TracChangeset for help on using the changeset viewer.