Changeset 6086

Timestamp:

04/30/11 15:40:40 (13 years ago)

Author:

abeham

Message:

#1497

• Added problem-specific local improvement operator (best improvement local search using swap2 moves)
  • Adapted ExhaustiveSwap2MoveGenerator to yield moves
• Added a parameter BestKnownSolutions to collect possible optimal invariants
  • Adapted BestQAPSolutionAnalyzer to collect optimal invariants
• Added a function to the QAP Evaluator that calculates the impact of a certain allele

Location:

branches/histogram

Files:

• HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/Swap2/ExhaustiveSwap2MoveGenerator.cs (modified) (2 diffs)
• HeuristicLab.Problems.QuadraticAssignment.Views/3.3/HeuristicLab.Problems.QuadraticAssignment.Views-3.3.csproj (modified) (3 diffs)
• HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QuadraticAssignmentProblemView.Designer.cs (modified) (4 diffs)
• HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QuadraticAssignmentProblemView.cs (modified) (2 diffs)
• HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QuadraticAssignmentProblemView.resx (modified) (1 diff)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/BestQAPSolutionAnalyzer.cs (modified) (3 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement (added)
• HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs (added)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs (modified) (10 diffs)

branches/histogram/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/Swap2/ExhaustiveSwap2MoveGenerator.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -39 +40 @@
     }
 
+    public static IEnumerable<Swap2Move> Generate(Permutation permutation) {
+      int length = permutation.Length;
+      if (length == 1) throw new ArgumentException("ExhaustiveSwap2MoveGenerator: There cannot be an Swap move given a permutation of length 1.", "permutation");
+
+      for (int i = 0; i < length - 1; i++)
+        for (int j = i + 1; j < length; j++) {
+          yield return new Swap2Move(i, j);
+        }
+    }
+
     public static Swap2Move[] Apply(Permutation permutation) {
       int length = permutation.Length;
-      if (length == 1) throw new ArgumentException("ExhaustiveSwap2MoveGenerator: There cannot be an Swap move given a permutation of length 1.", "permutation");
       int totalMoves = (length) * (length - 1) / 2;
       Swap2Move[] moves = new Swap2Move[totalMoves];
       int count = 0;
-
-      for (int i = 0; i < length - 1; i++)
-        for (int j = i + 1; j < length; j++) {
-          moves[count++] = new Swap2Move(i, j);
-        }
+      foreach (Swap2Move move in Generate(permutation)) {
+        moves[count++] = move;
+      }
       return moves;
     }

branches/histogram/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/HeuristicLab.Problems.QuadraticAssignment.Views-3.3.csproj

@@ -102 +102 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=x86" />
+    <Reference Include="HeuristicLab.Data.Views-3.3">
+      <HintPath>..\..\HeuristicLab.Data.Views\3.3\bin\x86\Debug\HeuristicLab.Data.Views-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Visualization.ChartControlsExtensions-3.3">
+      <HintPath>..\..\HeuristicLab.Visualization.ChartControlsExtensions\3.3\bin\x86\Debug\HeuristicLab.Visualization.ChartControlsExtensions-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -107 +114 @@
     <Reference Include="System.Drawing" />
     <Reference Include="System.Windows.Forms" />
+    <Reference Include="System.Windows.Forms.DataVisualization" />
     <Reference Include="System.Xml" />
   </ItemGroup>
@@ -184 +192 @@
       <Name>HeuristicLab.MainForm-3.3</Name>
     </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Optimization.Views\3.3\HeuristicLab.Optimization.Views-3.3.csproj">
+      <Project>{662B4B15-8F4D-4AE5-B3EB-D91C215F5AF2}</Project>
+      <Name>HeuristicLab.Optimization.Views-3.3</Name>
+    </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Optimization\3.3\HeuristicLab.Optimization-3.3.csproj">
       <Project>{14AB8D24-25BC-400C-A846-4627AA945192}</Project>

branches/histogram/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QuadraticAssignmentProblemView.Designer.cs

@@ -101 +101 @@
       this.QAPLIBInstancesLabel.AutoSize = true;
       this.QAPLIBInstancesLabel.Cursor = System.Windows.Forms.Cursors.Hand;
+      this.QAPLIBInstancesLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 8.25F, System.Drawing.FontStyle.Underline, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
+      this.QAPLIBInstancesLabel.ForeColor = System.Drawing.Color.Blue;
       this.QAPLIBInstancesLabel.Location = new System.Drawing.Point(3, 5);
       this.QAPLIBInstancesLabel.Name = "QAPLIBInstancesLabel";
@@ -109 +111 @@
               "qaplib/");
       this.QAPLIBInstancesLabel.Click += new System.EventHandler(this.QAPLIBInstancesLabel_Click);
+      this.QAPLIBInstancesLabel.MouseEnter += new System.EventHandler(this.QAPLIBInstancesLabel_MouseEnter);
+      this.QAPLIBInstancesLabel.MouseLeave += new System.EventHandler(this.QAPLIBInstancesLabel_MouseLeave);
       // 
       // instancesComboBox
@@ -191 +195 @@
       this.Name = "QuadraticAssignmentProblemView";
       this.Size = new System.Drawing.Size(647, 492);
-      this.Controls.SetChildIndex(this.infoLabel, 0);
-      this.Controls.SetChildIndex(this.parameterCollectionView, 0);
-      this.Controls.SetChildIndex(this.nameLabel, 0);
-      this.Controls.SetChildIndex(this.nameTextBox, 0);
       this.Controls.SetChildIndex(this.QAPLIBInstancesLabel, 0);
       this.Controls.SetChildIndex(this.loadInstanceButton, 0);
@@ -200 +200 @@
       this.Controls.SetChildIndex(this.tabControl, 0);
       this.Controls.SetChildIndex(this.instancesComboBox, 0);
+      this.Controls.SetChildIndex(this.infoLabel, 0);
+      this.Controls.SetChildIndex(this.parameterCollectionView, 0);
+      this.Controls.SetChildIndex(this.nameLabel, 0);
+      this.Controls.SetChildIndex(this.nameTextBox, 0);
       ((System.ComponentModel.ISupportInitialize)(this.errorProvider)).EndInit();
       this.tabControl.ResumeLayout(false);

branches/histogram/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QuadraticAssignmentProblemView.cs

@@ -21 +21 @@
 
 using System;
+using System.Drawing;
 using System.Windows.Forms;
 using HeuristicLab.Common.Resources;
@@ -120 +121 @@
       System.Diagnostics.Process.Start("http://www.seas.upenn.edu/qaplib/");
     }
+
+    private void QAPLIBInstancesLabel_MouseEnter(object sender, EventArgs e) {
+      Cursor = Cursors.Hand;
+      QAPLIBInstancesLabel.ForeColor = Color.Red;
+      toolTip.SetToolTip(QAPLIBInstancesLabel, "Browse to http://www.seas.upenn.edu/qaplib/");
+    }
+
+    private void QAPLIBInstancesLabel_MouseLeave(object sender, EventArgs e) {
+      Cursor = Cursors.Default;
+      QAPLIBInstancesLabel.ForeColor = Color.Blue;
+      toolTip.SetToolTip(QAPLIBInstancesLabel, String.Empty);
+    }
   }
 }

branches/histogram/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QuadraticAssignmentProblemView.resx

@@ -121 +121 @@
     <value>107, 17</value>
   </metadata>
+  <metadata name="errorProvider.TrayLocation" type="System.Drawing.Point, System.Drawing, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a">
+    <value>107, 17</value>
+  </metadata>
   <metadata name="toolTip.TrayLocation" type="System.Drawing.Point, System.Drawing, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a">
     <value>17, 17</value>

branches/histogram/HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/BestQAPSolutionAnalyzer.cs

@@ -61 +61 @@
       get { return (LookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
     }
+    public LookupParameter<ItemList<Permutation>> BestKnownSolutionsParameter {
+      get { return (LookupParameter<ItemList<Permutation>>)Parameters["BestKnownSolutions"]; }
+    }
     public LookupParameter<Permutation> BestKnownSolutionParameter {
       get { return (LookupParameter<Permutation>)Parameters["BestKnownSolution"]; }
@@ -81 +84 @@
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best QAP solution should be stored."));
       Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this QAP instance."));
+      Parameters.Add(new LookupParameter<ItemList<Permutation>>("BestKnownSolutions", "The best known solutions of this QAP instance."));
       Parameters.Add(new LookupParameter<Permutation>("BestKnownSolution", "The best known solution of this QAP instance."));
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      /*if (Parameters.ContainsKey("BestKnownSolution")) {
+        Parameters.Remove("BestKnownSolution");
+        Parameters.Add(new LookupParameter<ItemList<Permutation>>("BestKnownSolutions", "The best known solutions of this QAP instance."));
+      }*/
+      if (!Parameters.ContainsKey("BestKnownSolutions")) {
+        Parameters.Add(new LookupParameter<ItemList<Permutation>>("BestKnownSolutions", "The best known solutions of this QAP instance."));
+      }
+      #endregion
     }
 
@@ -93 +111 @@
       DoubleValue bestKnownQuality = BestKnownQualityParameter.ActualValue;
 
-      int i = -1;
-      if (!max)
-        i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
-      else i = qualities.Select((x, index) => new { index, x.Value }).OrderByDescending(x => x.Value).First().index;
+      var sorted = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).ToArray();
+      if (max) sorted = sorted.Reverse().ToArray();
+      int i = sorted.First().index;
 
-      if (bestKnownQuality == null ||
-          max && qualities[i].Value > bestKnownQuality.Value ||
-          !max && qualities[i].Value < bestKnownQuality.Value) {
+      if (bestKnownQuality == null
+          || max && qualities[i].Value > bestKnownQuality.Value
+          || !max && qualities[i].Value < bestKnownQuality.Value
+          || bestKnownQuality.Value == qualities[i].Value
+            && (BestKnownSolutionsParameter.ActualValue == null || BestKnownSolutionsParameter.ActualValue.Count == 0)) {
         BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[i].Value);
         BestKnownSolutionParameter.ActualValue = (Permutation)permutations[i].Clone();
+        BestKnownSolutionsParameter.ActualValue = new ItemList<Permutation>();
+        BestKnownSolutionsParameter.ActualValue.Add((Permutation)permutations[i].Clone());
+      } else if (bestKnownQuality != null && qualities[i].Value == bestKnownQuality.Value) {
+        PermutationEqualityComparer comparer = new PermutationEqualityComparer();
+        foreach (var k in sorted) {
+          if (!max && k.Value > qualities[i].Value
+            || max && k.Value < qualities[i].Value) break;
+          Permutation p = permutations[k.index];
+          bool alreadyPresent = false;
+          foreach (Permutation p2 in BestKnownSolutionsParameter.ActualValue) {
+            if (comparer.Equals(p, p2)) {
+              alreadyPresent = true;
+              break;
+            }
+          }
+          if (!alreadyPresent)
+            BestKnownSolutionsParameter.ActualValue.Add((Permutation)permutations[k.index].Clone());
+        }
       }
 

branches/histogram/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPEvaluator.cs

@@ -69 +69 @@
     }
 
+    public static double Impact(int facility, Permutation assignment, DoubleMatrix weights, DoubleMatrix distances) {
+      double impact = 0;
+      for (int i = 0; i < assignment.Length; i++) {
+        impact += weights[facility, i] * distances[assignment[facility], assignment[i]];
+        impact += weights[i, facility] * distances[assignment[i], assignment[facility]];
+      }
+      return impact;
+    }
+
     public override IOperation Apply() {
       Permutation assignment = PermutationParameter.ActualValue;

branches/histogram/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

@@ -120 +120 @@
     <Compile Include="Interfaces\IQAPEvaluator.cs" />
     <Compile Include="Interfaces\IQAPMoveEvaluator.cs" />
+    <Compile Include="LocalImprovement\QAPExhaustiveSwap2LocalImprovement.cs" />
     <Compile Include="Parsers\QAPLIBSolutionParser.cs" />
     <Compile Include="Parsers\QAPLIBParser.cs" />

branches/histogram/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -49 +49 @@
 
     #region Parameter Properties
+    public IValueParameter<ItemList<Permutation>> BestKnownSolutionsParameter {
+      get { return (IValueParameter<ItemList<Permutation>>)Parameters["BestKnownSolutions"]; }
+    }
     public IValueParameter<Permutation> BestKnownSolutionParameter {
       get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
@@ -61 +64 @@
 
     #region Properties
+    public ItemList<Permutation> BestKnownSolutions {
+      get { return BestKnownSolutionsParameter.Value; }
+      set { BestKnownSolutionsParameter.Value = value; }
+    }
     public Permutation BestKnownSolution {
       get { return BestKnownSolutionParameter.Value; }
@@ -106 +113 @@
     public QuadraticAssignmentProblem()
       : base(new QAPEvaluator(), new RandomPermutationCreator()) {
+      Parameters.Add(new OptionalValueParameter<ItemList<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
       Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
       Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
@@ -138 +146 @@
     public override IDeepCloneable Clone(Cloner cloner) {
       return new QuadraticAssignmentProblem(this, cloner);
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      /*if (Parameters.ContainsKey("BestKnownSolution")) {
+        Permutation solution = ((IValueParameter<Permutation>)Parameters["BestKnownSolution"]).Value;
+        Parameters.Remove("BestKnownSolution");
+        Parameters.Add(new OptionalValueParameter<ItemList<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
+        if (solution != null) {
+          BestKnownSolutions = new ItemList<Permutation>();
+          BestKnownSolutions.Add(solution);
+        }
+      }*/
+      if (!Parameters.ContainsKey("BestKnownSolutions")) {
+        Parameters.Add(new OptionalValueParameter<ItemList<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
+      }
+      #endregion
     }
 
@@ -246 +273 @@
       Operators.Add(new QAPAlleleFrequencyAnalyzer());
       Operators.Add(new QAPPopulationDiversityAnalyzer());
+      Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
       ParameterizeAnalyzers();
       ParameterizeOperators();
@@ -270 +298 @@
         BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
         BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
-        BestQAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
+        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
         BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
       }
@@ -314 +342 @@
       foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>())
         op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
+
+      QAPExhaustiveSwap2LocalImprovement localOpt = Operators.OfType<QAPExhaustiveSwap2LocalImprovement>().SingleOrDefault();
+      if (localOpt != null) {
+        localOpt.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
+        localOpt.DistancesParameter.ActualName = DistancesParameter.Name;
+        localOpt.MaximizationParameter.ActualName = MaximizationParameter.Name;
+        localOpt.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
+        localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
+      }
     }
 
@@ -338 +375 @@
       Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
       BestKnownQuality = null;
-      BestKnownSolution = null;
+      BestKnownSolutions = null;
       OnReset();
     }
@@ -371 +408 @@
             if (solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, Distances))) {
               BestKnownQuality = new DoubleValue(solParser.Quality);
+              BestKnownSolutions = new ItemList<Permutation>(new Permutation[] { new Permutation(PermutationTypes.Absolute, solParser.Assignment) });
               BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
             } else {
               BestKnownQuality = new DoubleValue(solParser.Quality);
+              BestKnownSolutions = null;
               BestKnownSolution = null;
             }
           } else {
             BestKnownQuality = new DoubleValue(solParser.Quality);
+            BestKnownSolutions = new ItemList<Permutation>(new Permutation[] { new Permutation(PermutationTypes.Absolute, solParser.Assignment) });
             BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
           }
@@ -383 +423 @@
       } else {
         BestKnownQuality = null;
+        BestKnownSolutions = null;
         BestKnownSolution = null;
       }