Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/23/11 00:29:24 (13 years ago)
Author:
abeham
Message:

#1425

  • Changed LocalImprovementOperators
    • Changed interface (made Problem a property, added a property that denotes the type of the problem that it can be applied on, added some general parameters)
    • Added some parameters and wiring
    • Changed move discovery and parameterization and added a helper class to ease finding compatible move operators
    • Discovering only IMultiMoveOperators and IExhaustiveMoveOperators and putting the multi move ones first
    • Fixed bug in Apply method that could create an endless string of nested execution contexts
    • Removed all problem specific analyzers in the two local improvement operators and only left the BestAverageWorstQualityAnalyzer since it doesn't make any sense to perform diversity or allele analysis during local improvement in the most common case and those analyzers take a lot of time (one can always add them manually should he/she be interested). The analyzers in the VNS's Analyzer parameter are left untouched.
  • Removed shaking operator and interface from VNS plugin and added that to Optimization and Optimization.Operators
  • Changed some ValueParameters to ConstrainedValueParameters and added type discovery to fill them (using the ProblemType property to get compatible local improvement operators)
  • Added missing GPL license headers
  • Changed some ValueParameters to the new FixedValueParameters
  • Added an additional encoding specific ShakingOperator to each encoding and added that to each problem
    • reason is that only the problem/encoding can really decide if a shaking operator is meaningful or not
  • Fixed an unrelated bug in the BestAverageWorstQualityAnalyzer that I encountered (and made the fix backwards compatible)
    • Also added a snippet for creating the backwards compatible comment marker and region
  • Fixed the operator graph of the VNS main loop
    • The condition to continue only when the local search was not successful is not necessary and is not part of the VNS definition as far as I know it (only condition to break the inner loop is when k reaches k_max)
  • Changed the ShakingOperator to input current index and output the maximum number of neighborhoods instead of a boolean that indicates that the last index has been reached since the maximum number is a little more generally useful and equally powerful in modeling
    • Remodeled the VNS main loop to check for k < k_max in order to continue the inner loop
  • other changes that I forgot...

Still necessary

  • test, test, test
  • check for backwards compatible breakers
  • add a maximum evaluated solutions stop criterion
  • optionally: implement fast problem specific local search improvement operators that do not build on the whole generic overhead (e.g. a 2-opt TSP specific local search operator). The idea of VNS is really to converge to a local optimum which is difficult to achieve using the current rather limited termination options
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Algorithms.VariableNeighborhoodSearch/3.3/VariableNeighborhoodSearch.cs

    r5809 r6042  
    1 using System;
    2 using System.Collections.Generic;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    323using System.Linq;
    4 using HeuristicLab.Algorithms.LocalSearch;
    524using HeuristicLab.Analysis;
    625using HeuristicLab.Common;
     
    1231using HeuristicLab.Parameters;
    1332using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     33using HeuristicLab.PluginInfrastructure;
    1434using HeuristicLab.Random;
    1535
     
    3252
    3353    #region Parameter Properties
    34     private ValueParameter<IntValue> SeedParameter {
    35       get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
    36     }
    37     private ValueParameter<BoolValue> SetSeedRandomlyParameter {
    38       get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
    39     }
    40     private ValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
    41       get { return (ValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
    42     }
    43     private ValueParameter<IShakingOperator> ShakingParameter {
    44       get { return (ValueParameter<IShakingOperator>)Parameters["Shaking"]; }
    45     }
    46     private ValueParameter<IntValue> MaximumIterationsParameter {
    47       get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
     54    private FixedValueParameter<IntValue> SeedParameter {
     55      get { return (FixedValueParameter<IntValue>)Parameters["Seed"]; }
     56    }
     57    private FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
     58      get { return (FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
     59    }
     60    private ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
     61      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
     62    }
     63    private ConstrainedValueParameter<IMultiNeighborhoodShakingOperator> ShakingOperatorParameter {
     64      get { return (ConstrainedValueParameter<IMultiNeighborhoodShakingOperator>)Parameters["ShakingOperator"]; }
     65    }
     66    private FixedValueParameter<IntValue> MaximumIterationsParameter {
     67      get { return (FixedValueParameter<IntValue>)Parameters["MaximumIterations"]; }
    4868    }
    4969    private ValueParameter<MultiAnalyzer> AnalyzerParameter {
    5070      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
    5171    }
    52     private VariableNeighborhoodSearchMainLoop VNSMainLoop {
    53       get { return FindMainLoop(SolutionsCreator.Successor); }
     72    public FixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
     73      get { return (FixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
    5474    }
    5575    #endregion
     
    6686      get { return (SolutionsCreator)RandomCreator.Successor; }
    6787    }
     88    private VariableNeighborhoodSearchMainLoop MainLoop {
     89      get { return FindMainLoop(SolutionsCreator.Successor); }
     90    }
    6891    #endregion
    6992
     
    7396    [StorableConstructor]
    7497    private VariableNeighborhoodSearch(bool deserializing) : base(deserializing) { }
    75     [StorableHook(HookType.AfterDeserialization)]
    76     private void AfterDeserialization() {
    77 
    78     }
    7998    private VariableNeighborhoodSearch(VariableNeighborhoodSearch original, Cloner cloner)
    8099      : base(original, cloner) {
    81100      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
    82       Initialize();
    83     }
    84     public override IDeepCloneable Clone(Cloner cloner) {
    85       return new VariableNeighborhoodSearch(this, cloner);
     101      RegisterEventHandlers();
    86102    }
    87103    public VariableNeighborhoodSearch()
    88104      : base() {
    89       Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
    90       Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
    91       Parameters.Add(new ValueParameter<ILocalImprovementOperator>("LocalImprovement", "The local improvement operation", new LocalSearchImprovementOperator()));
    92       Parameters.Add(new ValueParameter<IShakingOperator>("Shaking", "The shaking operation"));
    93       Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
     105      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
     106      Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
     107      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "The local improvement operation"));
     108      Parameters.Add(new ConstrainedValueParameter<IMultiNeighborhoodShakingOperator>("ShakingOperator", "The operator that performs the shaking of solutions."));
     109      Parameters.Add(new FixedValueParameter<IntValue>("MaximumIterations", "The maximum number of iterations which should be processed.", new IntValue(50)));
     110      Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations which should be performed in the local improvement phase.", new IntValue(50)));
    94111      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
    95112
     
    112129
    113130      variableCreator.Name = "Initialize Evaluated Solutions";
    114       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue()));
     131
     132      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
     133      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     134      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("CurrentNeighborhoodIndex", new IntValue(0)));
     135      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("NeighborhoodCount", new IntValue(0)));
    115136      variableCreator.Successor = resultsCollector;
    116137
    117138      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
     139      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
    118140      resultsCollector.ResultsParameter.ActualName = "Results";
    119141      resultsCollector.Successor = mainLoop;
    120142
     143      mainLoop.IterationsParameter.ActualName = "Iterations";
     144      mainLoop.CurrentNeighborhoodIndexParameter.ActualName = "CurrentNeighborhoodIndex";
     145      mainLoop.NeighborhoodCountParameter.ActualName = "NeighborhoodCount";
    121146      mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
    122       mainLoop.ShakingParameter.ActualName = ShakingParameter.Name;
     147      mainLoop.ShakingOperatorParameter.ActualName = ShakingOperatorParameter.Name;
    123148      mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
    124149      mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
     
    127152      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
    128153
     154      InitializeLocalImprovementOperators();
    129155      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
    130156      ParameterizeAnalyzers();
    131157      UpdateAnalyzers();
    132158
    133       Initialize();
     159      RegisterEventHandlers();
     160    }
     161
     162    public override IDeepCloneable Clone(Cloner cloner) {
     163      return new VariableNeighborhoodSearch(this, cloner);
     164    }
     165
     166    [StorableHook(HookType.AfterDeserialization)]
     167    private void AfterDeserialization() {
     168      RegisterEventHandlers();
    134169    }
    135170
     
    138173    }
    139174
    140     private void Initialize() {
     175    private void RegisterEventHandlers() {
     176      LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
    141177      if (Problem != null) {
    142178        Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    143179      }
    144       LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
    145180    }
    146181
    147182    #region Events
    148183    protected override void OnProblemChanged() {
     184      InitializeLocalImprovementOperators();
     185      UpdateShakingOperators();
     186      UpdateAnalyzers();
     187
    149188      ParameterizeStochasticOperator(Problem.SolutionCreator);
    150189      ParameterizeStochasticOperator(Problem.Evaluator);
    151190      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
    152191      ParameterizeSolutionsCreator();
    153       ParameterizeVNSMainLoop();
     192      ParameterizeMainLoop();
    154193      ParameterizeAnalyzers();
    155194      ParameterizeIterationBasedOperators();
    156       UpdateShakingOperator();
    157       UpdateLocalImprovementOperator();
    158       UpdateAnalyzers();
     195      ParameterizeLocalImprovementOperators();
    159196      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    160197      base.OnProblemChanged();
    161198    }
    162 
    163199    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
    164200      ParameterizeStochasticOperator(Problem.SolutionCreator);
     
    169205      ParameterizeStochasticOperator(Problem.Evaluator);
    170206      ParameterizeSolutionsCreator();
    171       ParameterizeVNSMainLoop();
     207      ParameterizeMainLoop();
    172208      ParameterizeAnalyzers();
    173209      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
     
    175211    }
    176212    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
     213      UpdateShakingOperators();
     214      UpdateAnalyzers();
    177215      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
    178216      ParameterizeIterationBasedOperators();
    179       UpdateShakingOperator();
    180       UpdateLocalImprovementOperator();
    181       UpdateAnalyzers();
    182217      base.Problem_OperatorsChanged(sender, e);
    183218    }
    184 
    185219    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
    186       ParameterizeVNSMainLoop();
     220      ParameterizeMainLoop();
    187221      ParameterizeAnalyzers();
    188222    }
    189 
    190     void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
    191       if (LocalImprovementParameter.Value != null)
    192         LocalImprovementParameter.Value.OnProblemChanged(Problem);
     223    private void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
     224      ParameterizeLocalImprovementOperators();
    193225    }
    194226    #endregion
     
    203235        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
    204236    }
    205     private void ParameterizeVNSMainLoop() {
    206       VNSMainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
    207       VNSMainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
    208       VNSMainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
     237    private void ParameterizeMainLoop() {
     238      MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
     239      MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
     240      MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
    209241    }
    210242    private void ParameterizeAnalyzers() {
     
    221253        foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
    222254          op.IterationsParameter.ActualName = "Iterations";
    223           op.MaximumIterationsParameter.ActualName = "MaximumIterations";
     255          op.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
    224256        }
    225257      }
    226258    }
    227     private void UpdateShakingOperator() {
    228       Type manipulatorType = typeof(IManipulator);
    229       List<Type> manipulatorInterfaces = new List<Type>();
    230 
    231       foreach (IManipulator mutator in Problem.Operators.OfType<IManipulator>().OrderBy(x => x.Name)) {
    232         Type t = mutator.GetType();
    233         Type[] interfaces = t.GetInterfaces();
    234 
    235         for (int i = 0; i < interfaces.Length; i++) {
    236           if (manipulatorType.IsAssignableFrom(interfaces[i])) {
    237             bool assignable = false;
    238             for (int j = 0; j < interfaces.Length; j++) {
    239               if (i != j && interfaces[i].IsAssignableFrom(interfaces[j])) {
    240                 assignable = true;
    241                 break;
    242               }
    243             }
    244 
    245             if (!assignable)
    246               manipulatorInterfaces.Add(interfaces[i]);
    247           }
     259    private void ParameterizeLocalImprovementOperators() {
     260      foreach (ILocalImprovementOperator op in LocalImprovementParameter.ValidValues) {
     261        if (op != LocalImprovementParameter.Value) op.Problem = null;
     262        op.MaximumIterationsParameter.Value = null;
     263        op.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
     264      }
     265      if (LocalImprovementParameter.Value != null)
     266        LocalImprovementParameter.Value.Problem = Problem;
     267    }
     268    private void InitializeLocalImprovementOperators() {
     269      if (Problem == null) {
     270        LocalImprovementParameter.ValidValues.Clear();
     271      } else {
     272        LocalImprovementParameter.ValidValues.RemoveWhere(x => !x.ProblemType.IsAssignableFrom(Problem.GetType()));
     273        foreach (ILocalImprovementOperator op in ApplicationManager.Manager.GetInstances<ILocalImprovementOperator>().Where(x => x.ProblemType.IsAssignableFrom(Problem.GetType()))) {
     274          if (!LocalImprovementParameter.ValidValues.Any(x => x.GetType() == op.GetType()))
     275            LocalImprovementParameter.ValidValues.Add(op);
    248276        }
    249277      }
    250 
    251       foreach (Type manipulatorInterface in manipulatorInterfaces) {
    252         //manipulatorInterface is more specific
    253         if (manipulatorType.IsAssignableFrom(manipulatorInterface)) {
    254           //and compatible to all other found manipulator types
    255           bool compatible = true;
    256           foreach (Type manipulatorInterface2 in manipulatorInterfaces) {
    257             if (!manipulatorInterface.IsAssignableFrom(manipulatorInterface2)) {
    258               compatible = false;
    259               break;
    260             }
    261           }
    262 
    263           if (compatible)
    264             manipulatorType = manipulatorInterface;
    265         }
    266       }
    267 
    268       Type genericType = typeof(ShakingOperator<>).MakeGenericType(manipulatorType);
    269       ShakingParameter.Value = (IShakingOperator)Activator.CreateInstance(genericType, new object[] { });
    270 
    271       ShakingParameter.Value.OnProblemChanged(Problem);
    272     }
    273     private void UpdateLocalImprovementOperator() {
    274       LocalImprovementParameter.Value.OnProblemChanged(Problem);
     278    }
     279    private void UpdateShakingOperators() {
     280      ShakingOperatorParameter.ValidValues.Clear();
     281      foreach (IMultiNeighborhoodShakingOperator op in Problem.Operators.OfType<IMultiNeighborhoodShakingOperator>()) {
     282        ShakingOperatorParameter.ValidValues.Add(op);
     283        op.CurrentNeighborhoodIndexParameter.ActualName = "CurrentNeighborhoodIndex";
     284        op.NeighborhoodCountParameter.ActualName = "NeighborhoodCount";
     285      }
    275286    }
    276287    private void UpdateAnalyzers() {
Note: See TracChangeset for help on using the changeset viewer.