Changeset 3101 for trunk

Timestamp:

03/18/10 20:56:34 (14 years ago)

Author:

abeham

Message:

Updated simulated annealing:

• Added inner loop to noticeably speed up algorithm
• Removed exception in StochasticTwoOptMultiMoveGenerator when more moves would be generated than from the exhaustive move generator. The StochasticTwoOptMultiMoveGenerator simply draws from all moves with replacement.

#923

Location:

trunk/sources

Files:

• HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealing.cs (modified) (12 diffs)
• HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealingMainLoop.cs (modified) (7 diffs)
• HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticTwoOptMultiMoveGenerator.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealing.cs

@@ -53 +53 @@
       get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
     }
-    private ConstrainedValueParameter<ISingleMoveGenerator> MoveGeneratorParameter {
-      get { return (ConstrainedValueParameter<ISingleMoveGenerator>)Parameters["MoveGenerator"]; }
+    private ConstrainedValueParameter<IMultiMoveGenerator> MoveGeneratorParameter {
+      get { return (ConstrainedValueParameter<IMultiMoveGenerator>)Parameters["MoveGenerator"]; }
     }
     private ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
@@ -67 +67 @@
     private ValueParameter<IntValue> MaximumIterationsParameter {
       get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
+    }
+    private ValueParameter<IntValue> InnerIterationsParameter {
+      get { return (ValueParameter<IntValue>)Parameters["InnerIterations"]; }
     }
     private ValueParameter<DoubleValue> StartTemperatureParameter {
@@ -85 +88 @@
       set { SetSeedRandomlyParameter.Value = value; }
     }
-    public ISingleMoveGenerator MoveGenerator {
+    public IMultiMoveGenerator MoveGenerator {
       get { return MoveGeneratorParameter.Value; }
       set { MoveGeneratorParameter.Value = value; }
@@ -100 +103 @@
       get { return MaximumIterationsParameter.Value; }
       set { MaximumIterationsParameter.Value = value; }
+    }
+    public IntValue InnerIterations {
+      get { return InnerIterationsParameter.Value; }
+      set { InnerIterationsParameter.Value = value; }
+    }
+    public DoubleValue StartTemperature {
+      get { return StartTemperatureParameter.Value; }
+      set { StartTemperatureParameter.Value = value; }
+    }
+    public DoubleValue EndTemperature {
+      get { return EndTemperatureParameter.Value; }
+      set { EndTemperatureParameter.Value = value; }
     }
     private RandomCreator RandomCreator {
@@ -121 +136 @@
       Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
       Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
-      Parameters.Add(new ConstrainedValueParameter<ISingleMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
+      Parameters.Add(new ConstrainedValueParameter<IMultiMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
       Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
       Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
       Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>("AnnealingOperator", "The operator used to modify the temperature."));
-      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
+      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(100)));
+      Parameters.Add(new ValueParameter<IntValue>("InnerIterations", "The amount of inner iterations (number of moves before temperature is adjusted again).", new IntValue(10)));
       Parameters.Add(new ValueParameter<DoubleValue>("StartTemperature", "The initial temperature.", new DoubleValue(100)));
       Parameters.Add(new ValueParameter<DoubleValue>("EndTemperature", "The final temperature which should be reached when iterations reaches maximum iterations.", new DoubleValue(1e-6)));
@@ -176 +192 @@
       ParameterizeSolutionsCreator();
       ParameterizeMainLoop();
-      ParameterizeMoveEvaluator();
-      ParameterizeMoveMaker();
+      ParameterizeMoveEvaluators();
+      ParameterizeMoveMakers();
+      ParameterizeMoveGenerators();
       UpdateMoveGenerator();
       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
@@ -191 +208 @@
       ParameterizeSolutionsCreator();
       ParameterizeMainLoop();
-      ParameterizeMoveEvaluator();
-      ParameterizeMoveMaker();
+      ParameterizeMoveEvaluators();
+      ParameterizeMoveMakers();
       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       base.Problem_EvaluatorChanged(sender, e);
@@ -204 +221 @@
         op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
       }
-      ISingleMoveGenerator oldMoveGenerator = MoveGenerator;
+      IMultiMoveGenerator oldMoveGenerator = MoveGenerator;
       UpdateMoveGenerator();
       if (oldMoveGenerator == MoveGenerator) // in this case MoveGeneratorParameter_ValueChanged did not fire
         UpdateMoveParameters();
       ParameterizeMainLoop();
-      ParameterizeMoveEvaluator();
-      ParameterizeMoveMaker();
+      ParameterizeMoveEvaluators();
+      ParameterizeMoveMakers();
+      ParameterizeMoveGenerators();
       base.Problem_OperatorsChanged(sender, e);
     }
     private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
       ParameterizeMainLoop();
-      ParameterizeMoveEvaluator();
-      ParameterizeMoveMaker();
+      ParameterizeMoveEvaluators();
+      ParameterizeMoveMakers();
     }
     private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
@@ -223 +241 @@
     private void MoveEvaluatorParameter_ValueChanged(object sender, EventArgs e) {
       ParameterizeMainLoop();
-      ParameterizeMoveEvaluator();
-      ParameterizeMoveMaker();
+      ParameterizeMoveEvaluators();
+      ParameterizeMoveMakers();
     }
     private void MoveEvaluator_MoveQualityParameter_ActualNameChanged(object sender, EventArgs e) {
       ParameterizeMainLoop();
-      ParameterizeMoveEvaluator();
-      ParameterizeMoveMaker();
+      ParameterizeMoveEvaluators();
+      ParameterizeMoveMakers();
     }
     #endregion
@@ -257 +275 @@
     }
     private void UpdateMoveGenerator() {
-      ISingleMoveGenerator oldMoveGenerator = MoveGenerator;
+      IMultiMoveGenerator oldMoveGenerator = MoveGenerator;
       MoveGeneratorParameter.ValidValues.Clear();
       if (Problem != null) {
-        foreach (ISingleMoveGenerator generator in Problem.Operators.OfType<ISingleMoveGenerator>().Where(x => !(x is IMultiMoveGenerator)).OrderBy(x => x.Name))
+        foreach (IMultiMoveGenerator generator in Problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
           MoveGeneratorParameter.ValidValues.Add(generator);
       }
       if (oldMoveGenerator != null) {
-        ISingleMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
+        IMultiMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
         if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
       }
@@ -314 +332 @@
         ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
     }
-    private void ParameterizeMoveEvaluator() {
+    private void ParameterizeMoveEvaluators() {
       foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
         op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
       }
     }
-    private void ParameterizeMoveMaker() {
+    private void ParameterizeMoveMakers() {
       foreach (IMoveMaker op in Problem.Operators.OfType<IMoveMaker>()) {
         op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
@@ -337 +355 @@
       }
     }
+    private void ParameterizeMoveGenerators() {
+      foreach (IMultiMoveGenerator op in Problem.Operators.OfType<IMultiMoveGenerator>()) {
+        op.SampleSizeParameter.ActualName = InnerIterationsParameter.Name;
+      }
+    }
     #endregion
   }

trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealingMainLoop.cs

@@ -55 +55 @@
       get { return (ValueLookupParameter<DoubleValue>)Parameters["EndTemperature"]; }
     }
+    public ValueLookupParameter<IntValue> InnerIterationsParameter {
+      get { return (ValueLookupParameter<IntValue>)Parameters["InnerIterations"]; }
+    }
     public ValueLookupParameter<IntValue> MaximumIterationsParameter {
       get { return (ValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
@@ -97 +100 @@
       Parameters.Add(new ValueLookupParameter<DoubleValue>("StartTemperature", "The initial temperature."));
       Parameters.Add(new ValueLookupParameter<DoubleValue>("EndTemperature", "The end temperature."));
+      Parameters.Add(new ValueLookupParameter<IntValue>("InnerIterations", "The amount of inner iterations (number of moves before temperature is adjusted again)."));
       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of iterations which should be processed."));
       Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
@@ -116 +120 @@
       Placeholder annealingOperator = new Placeholder();
       UniformSequentialSubScopesProcessor mainProcessor = new UniformSequentialSubScopesProcessor();
+      DataTableValuesCollector valuesCollector = new DataTableValuesCollector();
       Placeholder moveGenerator = new Placeholder();
-      SequentialSubScopesProcessor moveEvaluationProcessor = new SequentialSubScopesProcessor();
+      UniformSequentialSubScopesProcessor moveEvaluationProcessor = new UniformSequentialSubScopesProcessor();
       Placeholder moveEvaluator = new Placeholder();
       ProbabilisticQualityComparator qualityComparator = new ProbabilisticQualityComparator();
@@ -123 +128 @@
       Placeholder moveMaker = new Placeholder();
       SubScopesRemover subScopesRemover = new SubScopesRemover();
-      DataTableValuesCollector valuesCollector = new DataTableValuesCollector();
       IntCounter iterationsCounter = new IntCounter();
       Comparator iterationsComparator = new Comparator();
@@ -142 +146 @@
       annealingOperator.OperatorParameter.ActualName = "AnnealingOperator";
 
+      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Quality"));
+      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("BestQuality"));
+      valuesCollector.DataTableParameter.ActualName = "Qualities";
+
       moveGenerator.Name = "Move generator (placeholder)";
       moveGenerator.OperatorParameter.ActualName = "MoveGenerator";
@@ -159 +167 @@
 
       subScopesRemover.RemoveAllSubScopes = true;
-
-      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Quality"));
-      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("BestQuality"));
-      valuesCollector.DataTableParameter.ActualName = "Qualities";
 
       iterationsCounter.Name = "Increment Iterations";
@@ -188 +192 @@
       bestQualityMemorizer.Successor = annealingOperator;
       annealingOperator.Successor = mainProcessor;
-      mainProcessor.Operator = moveGenerator;
-      mainProcessor.Successor = valuesCollector;
+      mainProcessor.Operator = valuesCollector;
+      mainProcessor.Successor = iterationsCounter;
+      valuesCollector.Successor = moveGenerator;
       moveGenerator.Successor = moveEvaluationProcessor;
-      moveEvaluationProcessor.Operators.Add(moveEvaluator);
+      moveEvaluationProcessor.Operator = moveEvaluator;
       moveEvaluationProcessor.Successor = subScopesRemover;
       moveEvaluator.Successor = qualityComparator;
       qualityComparator.Successor = improvesQualityBranch;
       improvesQualityBranch.TrueBranch = moveMaker;
-      valuesCollector.Successor = iterationsCounter;
       iterationsCounter.Successor = iterationsComparator;
       iterationsComparator.Successor = iterationsTermination;

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticTwoOptMultiMoveGenerator.cs

@@ -47 +47 @@
     public static TwoOptMove[] Apply(Permutation permutation, IRandom random, int sampleSize) {
       int length = permutation.Length;
-      int totalMoves = (length) * (length - 1) / 2 - 3;
-      // FIXME: Should this be an exception or a warning for the logger?
-      if (sampleSize >= totalMoves) throw new InvalidOperationException("StochasticTwoOptMoveGenerator: Sample size (" + sampleSize + ") is larger than the set of all possible moves (" + totalMoves + "), use the ExhaustiveTwoOptMoveGenerator instead.");
       TwoOptMove[] moves = new TwoOptMove[sampleSize];
       for (int i = 0; i < sampleSize; i++) {