[5603] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
| 3 | using System.Linq;
|
---|
| 4 | using System.Text;
|
---|
| 5 | using HeuristicLab.Core;
|
---|
| 6 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 7 | using HeuristicLab.Common;
|
---|
| 8 | using HeuristicLab.Optimization;
|
---|
| 9 | using HeuristicLab.Parameters;
|
---|
| 10 | using HeuristicLab.Data;
|
---|
| 11 | using HeuristicLab.Analysis;
|
---|
| 12 | using HeuristicLab.Random;
|
---|
| 13 | using HeuristicLab.Optimization.Operators;
|
---|
| 14 | using HeuristicLab.Operators;
|
---|
[5622] | 15 | using HeuristicLab.Algorithms.LocalSearch;
|
---|
[5603] | 16 |
|
---|
| 17 | namespace HeuristicLab.Algorithms.VariableNeighborhoodSearch {
|
---|
| 18 | [Item("Variable Neighborhood Search", "A variable neighborhood search algorithm.")]
|
---|
| 19 | [Creatable("Algorithms")]
|
---|
| 20 | [StorableClass]
|
---|
| 21 | public sealed class VariableNeighborhoodSearch : EngineAlgorithm, IStorableContent {
|
---|
| 22 | public string Filename { get; set; }
|
---|
| 23 |
|
---|
| 24 | #region Problem Properties
|
---|
| 25 | public override Type ProblemType {
|
---|
| 26 | get { return typeof(ISingleObjectiveProblem); }
|
---|
| 27 | }
|
---|
| 28 | public new ISingleObjectiveProblem Problem {
|
---|
| 29 | get { return (ISingleObjectiveProblem)base.Problem; }
|
---|
| 30 | set { base.Problem = value; }
|
---|
| 31 | }
|
---|
| 32 | #endregion
|
---|
| 33 |
|
---|
| 34 | #region Parameter Properties
|
---|
| 35 | private ValueParameter<IntValue> SeedParameter {
|
---|
| 36 | get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
|
---|
| 37 | }
|
---|
| 38 | private ValueParameter<BoolValue> SetSeedRandomlyParameter {
|
---|
| 39 | get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
|
---|
| 40 | }
|
---|
[5735] | 41 | private ValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
|
---|
| 42 | get { return (ValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
|
---|
[5603] | 43 | }
|
---|
[5642] | 44 | private ValueParameter<IShakingOperator> ShakingParameter {
|
---|
| 45 | get { return (ValueParameter<IShakingOperator>)Parameters["Shaking"]; }
|
---|
[5603] | 46 | }
|
---|
| 47 | private ValueParameter<IntValue> MaximumIterationsParameter {
|
---|
| 48 | get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
|
---|
| 49 | }
|
---|
| 50 | private ValueParameter<MultiAnalyzer> AnalyzerParameter {
|
---|
| 51 | get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
|
---|
| 52 | }
|
---|
[5642] | 53 | private VariableNeighborhoodSearchMainLoop VNSMainLoop {
|
---|
| 54 | get { return FindMainLoop(SolutionsCreator.Successor); }
|
---|
| 55 | }
|
---|
[5603] | 56 | #endregion
|
---|
| 57 |
|
---|
| 58 | #region Properties
|
---|
| 59 | private RandomCreator RandomCreator {
|
---|
| 60 | get { return (RandomCreator)OperatorGraph.InitialOperator; }
|
---|
| 61 | }
|
---|
[5642] | 62 | public MultiAnalyzer Analyzer {
|
---|
| 63 | get { return AnalyzerParameter.Value; }
|
---|
| 64 | set { AnalyzerParameter.Value = value; }
|
---|
| 65 | }
|
---|
| 66 | private SolutionsCreator SolutionsCreator {
|
---|
| 67 | get { return (SolutionsCreator)RandomCreator.Successor; }
|
---|
| 68 | }
|
---|
[5603] | 69 | #endregion
|
---|
| 70 |
|
---|
[5642] | 71 | [Storable]
|
---|
| 72 | private BestAverageWorstQualityAnalyzer qualityAnalyzer;
|
---|
| 73 |
|
---|
[5603] | 74 | [StorableConstructor]
|
---|
| 75 | private VariableNeighborhoodSearch(bool deserializing) : base(deserializing) { }
|
---|
| 76 | [StorableHook(HookType.AfterDeserialization)]
|
---|
| 77 | private void AfterDeserialization() {
|
---|
| 78 |
|
---|
| 79 | }
|
---|
| 80 | private VariableNeighborhoodSearch(VariableNeighborhoodSearch original, Cloner cloner)
|
---|
| 81 | : base(original, cloner) {
|
---|
[5642] | 82 | qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
|
---|
| 83 | Initialize();
|
---|
[5603] | 84 | }
|
---|
| 85 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 86 | return new VariableNeighborhoodSearch(this, cloner);
|
---|
| 87 | }
|
---|
| 88 | public VariableNeighborhoodSearch()
|
---|
| 89 | : base() {
|
---|
| 90 | Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
|
---|
| 91 | Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
|
---|
[5735] | 92 | Parameters.Add(new ValueParameter<ILocalImprovementOperator>("LocalImprovement", "The local improvement operation", new LocalSearchImprovementOperator()));
|
---|
[5642] | 93 | Parameters.Add(new ValueParameter<IShakingOperator>("Shaking", "The shaking operation"));
|
---|
[5603] | 94 | Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
|
---|
| 95 | Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
|
---|
| 96 |
|
---|
| 97 | RandomCreator randomCreator = new RandomCreator();
|
---|
| 98 | SolutionsCreator solutionsCreator = new SolutionsCreator();
|
---|
| 99 | VariableCreator variableCreator = new VariableCreator();
|
---|
| 100 | ResultsCollector resultsCollector = new ResultsCollector();
|
---|
| 101 | VariableNeighborhoodSearchMainLoop mainLoop = new VariableNeighborhoodSearchMainLoop();
|
---|
| 102 | OperatorGraph.InitialOperator = randomCreator;
|
---|
| 103 |
|
---|
| 104 | randomCreator.RandomParameter.ActualName = "Random";
|
---|
| 105 | randomCreator.SeedParameter.ActualName = SeedParameter.Name;
|
---|
| 106 | randomCreator.SeedParameter.Value = null;
|
---|
| 107 | randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
|
---|
| 108 | randomCreator.SetSeedRandomlyParameter.Value = null;
|
---|
| 109 | randomCreator.Successor = solutionsCreator;
|
---|
| 110 |
|
---|
| 111 | solutionsCreator.NumberOfSolutions = new IntValue(1);
|
---|
| 112 | solutionsCreator.Successor = variableCreator;
|
---|
| 113 |
|
---|
| 114 | variableCreator.Name = "Initialize Evaluated Solutions";
|
---|
| 115 | variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue()));
|
---|
| 116 | variableCreator.Successor = resultsCollector;
|
---|
| 117 |
|
---|
| 118 | resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
|
---|
| 119 | resultsCollector.ResultsParameter.ActualName = "Results";
|
---|
| 120 | resultsCollector.Successor = mainLoop;
|
---|
| 121 |
|
---|
| 122 | mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
|
---|
| 123 | mainLoop.ShakingParameter.ActualName = ShakingParameter.Name;
|
---|
| 124 | mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
|
---|
| 125 | mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
|
---|
| 126 | mainLoop.ResultsParameter.ActualName = "Results";
|
---|
| 127 | mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
|
---|
| 128 | mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
|
---|
| 129 |
|
---|
[5642] | 130 | qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
|
---|
| 131 | ParameterizeAnalyzers();
|
---|
| 132 | UpdateAnalyzers();
|
---|
| 133 |
|
---|
| 134 | Initialize();
|
---|
[5603] | 135 | }
|
---|
[5642] | 136 |
|
---|
| 137 | public override void Prepare() {
|
---|
| 138 | if (Problem != null) base.Prepare();
|
---|
| 139 | }
|
---|
| 140 |
|
---|
| 141 | private void Initialize() {
|
---|
| 142 | if (Problem != null) {
|
---|
| 143 | Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
|
---|
| 144 | }
|
---|
| 145 | }
|
---|
| 146 |
|
---|
| 147 | #region Events
|
---|
| 148 | protected override void OnProblemChanged() {
|
---|
| 149 | ParameterizeStochasticOperator(Problem.SolutionCreator);
|
---|
| 150 | ParameterizeStochasticOperator(Problem.Evaluator);
|
---|
| 151 | foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
|
---|
| 152 | ParameterizeSolutionsCreator();
|
---|
| 153 | ParameterizeVNSMainLoop();
|
---|
| 154 | ParameterizeAnalyzers();
|
---|
| 155 | ParameterizeIterationBasedOperators();
|
---|
| 156 | UpdateShakingOperator();
|
---|
| 157 | UpdateLocalImprovementOperator();
|
---|
| 158 | UpdateAnalyzers();
|
---|
| 159 | Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
|
---|
| 160 | base.OnProblemChanged();
|
---|
| 161 | }
|
---|
| 162 |
|
---|
| 163 | protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
|
---|
| 164 | ParameterizeStochasticOperator(Problem.SolutionCreator);
|
---|
| 165 | ParameterizeSolutionsCreator();
|
---|
| 166 | base.Problem_SolutionCreatorChanged(sender, e);
|
---|
| 167 | }
|
---|
| 168 | protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
|
---|
| 169 | ParameterizeStochasticOperator(Problem.Evaluator);
|
---|
| 170 | ParameterizeSolutionsCreator();
|
---|
| 171 | ParameterizeVNSMainLoop();
|
---|
| 172 | ParameterizeAnalyzers();
|
---|
| 173 | Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
|
---|
| 174 | base.Problem_EvaluatorChanged(sender, e);
|
---|
| 175 | }
|
---|
| 176 | protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
|
---|
| 177 | foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
|
---|
| 178 | ParameterizeIterationBasedOperators();
|
---|
| 179 | UpdateShakingOperator();
|
---|
| 180 | UpdateLocalImprovementOperator();
|
---|
| 181 | UpdateAnalyzers();
|
---|
| 182 | base.Problem_OperatorsChanged(sender, e);
|
---|
| 183 | }
|
---|
| 184 |
|
---|
| 185 | private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
|
---|
| 186 | ParameterizeVNSMainLoop();
|
---|
| 187 | ParameterizeAnalyzers();
|
---|
| 188 | }
|
---|
| 189 | #endregion
|
---|
| 190 |
|
---|
| 191 | #region Helpers
|
---|
| 192 | private void ParameterizeSolutionsCreator() {
|
---|
| 193 | SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
|
---|
| 194 | SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
|
---|
| 195 | }
|
---|
| 196 | private void ParameterizeStochasticOperator(IOperator op) {
|
---|
| 197 | if (op is IStochasticOperator)
|
---|
| 198 | ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
|
---|
| 199 | }
|
---|
| 200 | private void ParameterizeVNSMainLoop() {
|
---|
| 201 | VNSMainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
|
---|
| 202 | VNSMainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
|
---|
| 203 | VNSMainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
|
---|
| 204 | }
|
---|
| 205 | private void ParameterizeAnalyzers() {
|
---|
| 206 | qualityAnalyzer.ResultsParameter.ActualName = "Results";
|
---|
| 207 | if (Problem != null) {
|
---|
| 208 | qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
|
---|
| 209 | qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
|
---|
| 210 | qualityAnalyzer.QualityParameter.Depth = 1;
|
---|
| 211 | qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
|
---|
| 212 | }
|
---|
| 213 | }
|
---|
| 214 | private void ParameterizeIterationBasedOperators() {
|
---|
| 215 | if (Problem != null) {
|
---|
| 216 | foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
|
---|
[5735] | 217 | op.IterationsParameter.ActualName = "Iterations";
|
---|
[5642] | 218 | op.MaximumIterationsParameter.ActualName = "MaximumIterations";
|
---|
| 219 | }
|
---|
| 220 | }
|
---|
| 221 | }
|
---|
| 222 | private void UpdateShakingOperator() {
|
---|
| 223 | Type manipulatorType = typeof(IManipulator);
|
---|
| 224 | List<Type> manipulatorInterfaces = new List<Type>();
|
---|
| 225 |
|
---|
| 226 | foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name)) {
|
---|
| 227 | Type t = mutator.GetType();
|
---|
| 228 | Type[] interfaces = t.GetInterfaces();
|
---|
| 229 |
|
---|
| 230 | for(int i = 0; i < interfaces.Length; i++) {
|
---|
| 231 | if (manipulatorType.IsAssignableFrom(interfaces[i])) {
|
---|
| 232 | bool assignable = false;
|
---|
| 233 | for (int j = 0; j < interfaces.Length; j++) {
|
---|
| 234 | if (i != j && interfaces[i].IsAssignableFrom(interfaces[j])) {
|
---|
| 235 | assignable = true;
|
---|
| 236 | break;
|
---|
| 237 | }
|
---|
| 238 | }
|
---|
| 239 |
|
---|
| 240 | if(!assignable)
|
---|
| 241 | manipulatorInterfaces.Add(interfaces[i]);
|
---|
| 242 | }
|
---|
| 243 | }
|
---|
| 244 | }
|
---|
| 245 |
|
---|
| 246 | foreach (Type manipulatorInterface in manipulatorInterfaces) {
|
---|
| 247 | //manipulatorInterface is more specific
|
---|
| 248 | if (manipulatorType.IsAssignableFrom(manipulatorInterface)) {
|
---|
| 249 | //and compatible to all other found manipulator types
|
---|
| 250 | bool compatible = true;
|
---|
| 251 | foreach (Type manipulatorInterface2 in manipulatorInterfaces) {
|
---|
| 252 | if (!manipulatorInterface.IsAssignableFrom(manipulatorInterface2)) {
|
---|
| 253 | compatible = false;
|
---|
| 254 | break;
|
---|
| 255 | }
|
---|
| 256 | }
|
---|
| 257 |
|
---|
| 258 | if (compatible)
|
---|
| 259 | manipulatorType = manipulatorInterface;
|
---|
| 260 | }
|
---|
| 261 | }
|
---|
| 262 |
|
---|
| 263 | Type genericType = typeof(ShakingOperator<>).MakeGenericType(manipulatorType);
|
---|
| 264 | ShakingParameter.Value = (IShakingOperator)Activator.CreateInstance(genericType, new object[]{});
|
---|
| 265 |
|
---|
| 266 | ShakingParameter.Value.Parameterize(Problem);
|
---|
| 267 | }
|
---|
| 268 | private void UpdateLocalImprovementOperator() {
|
---|
[5735] | 269 | LocalImprovementParameter.Value.OnProblemChanged(Problem);
|
---|
[5642] | 270 | }
|
---|
| 271 | private void UpdateAnalyzers() {
|
---|
| 272 | Analyzer.Operators.Clear();
|
---|
| 273 | if (Problem != null) {
|
---|
| 274 | foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
|
---|
| 275 | foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
|
---|
| 276 | param.Depth = 1;
|
---|
| 277 | Analyzer.Operators.Add(analyzer);
|
---|
| 278 | }
|
---|
| 279 | }
|
---|
| 280 | Analyzer.Operators.Add(qualityAnalyzer);
|
---|
| 281 | }
|
---|
| 282 | private VariableNeighborhoodSearchMainLoop FindMainLoop(IOperator start) {
|
---|
| 283 | IOperator mainLoop = start;
|
---|
| 284 | while (mainLoop != null && !(mainLoop is VariableNeighborhoodSearchMainLoop))
|
---|
| 285 | mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
|
---|
| 286 | if (mainLoop == null) return null;
|
---|
| 287 | else return (VariableNeighborhoodSearchMainLoop)mainLoop;
|
---|
| 288 | }
|
---|
| 289 | #endregion
|
---|
[5603] | 290 | }
|
---|
| 291 | }
|
---|