Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8022 for trunk/sources


Ignore:
Timestamp:
06/18/12 02:53:03 (12 years ago)
Author:
abeham
Message:

#1855:

  • Transformed LAP into a SingleObjectiveHeuristicOptimizationProblem
  • Added HungarianAlgorithm as separate algorithm for solving the problem
Location:
trunk/sources
Files:
9 added
2 deleted
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Optimizer/3.3/HeuristicLab.Optimizer-3.3.csproj

    r7985 r8022  
    248248      <Project>{72104A0B-90E7-42F3-9ABE-9BBBADD4B943}</Project>
    249249      <Name>HeuristicLab.Data.Views-3.3</Name>
     250      <Private>False</Private>
    250251    </ProjectReference>
    251252    <ProjectReference Include="..\..\HeuristicLab.Data\3.3\HeuristicLab.Data-3.3.csproj">
    252253      <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
    253254      <Name>HeuristicLab.Data-3.3</Name>
     255      <Private>False</Private>
    254256    </ProjectReference>
    255257    <ProjectReference Include="..\..\HeuristicLab.MainForm.WindowsForms\3.3\HeuristicLab.MainForm.WindowsForms-3.3.csproj">
    … …  
    271273      <Project>{56F9106A-079F-4C61-92F6-86A84C2D84B7}</Project>
    272274      <Name>HeuristicLab.Parameters-3.3</Name>
     275      <Private>False</Private>
    273276    </ProjectReference>
    274277    <ProjectReference Include="..\..\HeuristicLab.Persistence\3.3\HeuristicLab.Persistence-3.3.csproj">
    … …  
    285288      <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
    286289      <Name>HeuristicLab.Problems.Instances-3.3</Name>
     290      <Private>False</Private>
    287291    </ProjectReference>
    288292  </ItemGroup>

  • trunk/sources/HeuristicLab.Problems.LinearAssignment.Views/3.3/HeuristicLab.Problems.LinearAssignment.Views-3.3.csproj

    r7874 r8022  
    102102  </PropertyGroup>
    103103  <ItemGroup>
     104    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     105      <Private>False</Private>
     106    </Reference>
    104107    <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
    105108      <HintPath>..\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
    … …  
    114117  <ItemGroup>
    115118    <None Include="Plugin.cs.frame" />
    116     <Compile Include="LinearAssignmentProblemView.cs">
     119    <Compile Include="LAPAssignmentView.cs">
    117120      <SubType>UserControl</SubType>
    118121    </Compile>
    119     <Compile Include="LinearAssignmentProblemView.Designer.cs">
    120       <DependentUpon>LinearAssignmentProblemView.cs</DependentUpon>
     122    <Compile Include="LAPAssignmentView.Designer.cs">
     123      <DependentUpon>LAPAssignmentView.cs</DependentUpon>
    121124    </Compile>
    122125    <Compile Include="Plugin.cs" />
    … …  
    148151      <Private>False</Private>
    149152    </ProjectReference>
     153    <ProjectReference Include="..\..\HeuristicLab.Data.Views\3.3\HeuristicLab.Data.Views-3.3.csproj">
     154      <Project>{72104A0B-90E7-42F3-9ABE-9BBBADD4B943}</Project>
     155      <Name>HeuristicLab.Data.Views-3.3</Name>
     156      <Private>False</Private>
     157    </ProjectReference>
    150158    <ProjectReference Include="..\..\HeuristicLab.Data\3.3\HeuristicLab.Data-3.3.csproj">
    151159      <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
    … …  
    153161      <Private>False</Private>
    154162    </ProjectReference>
     163    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
     164      <Project>{DBECB8B0-B166-4133-BAF1-ED67C3FD7FCA}</Project>
     165      <Name>HeuristicLab.Encodings.PermutationEncoding-3.3</Name>
     166      <Private>False</Private>
     167    </ProjectReference>
    155168    <ProjectReference Include="..\..\HeuristicLab.MainForm.WindowsForms\3.3\HeuristicLab.MainForm.WindowsForms-3.3.csproj">
    156169      <Project>{AB687BBE-1BFE-476B-906D-44237135431D}</Project>
    … …  
    163176      <Private>False</Private>
    164177    </ProjectReference>
    165     <ProjectReference Include="..\..\HeuristicLab.Optimization.Views\3.3\HeuristicLab.Optimization.Views-3.3.csproj">
    166       <Project>{662B4B15-8F4D-4AE5-B3EB-D91C215F5AF2}</Project>
    167       <Name>HeuristicLab.Optimization.Views-3.3</Name>
    168       <Private>False</Private>
    169     </ProjectReference>
    170     <ProjectReference Include="..\..\HeuristicLab.Optimization\3.3\HeuristicLab.Optimization-3.3.csproj">
    171       <Project>{14AB8D24-25BC-400C-A846-4627AA945192}</Project>
    172       <Name>HeuristicLab.Optimization-3.3</Name>
     178    <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">
     179      <Project>{23DA7FF4-D5B8-41B6-AA96-F0561D24F3EE}</Project>
     180      <Name>HeuristicLab.Operators-3.3</Name>
    173181      <Private>False</Private>
    174182    </ProjectReference>

  • trunk/sources/HeuristicLab.Problems.LinearAssignment.Views/3.3/Plugin.cs.frame

    r7937 r8022  
    2525  [Plugin("HeuristicLab.Problems.LinearAssignment.Views", "3.3.6.$WCREV$")]
    2626  [PluginFile("HeuristicLab.Problems.LinearAssignment.Views-3.3.dll", PluginFileType.Assembly)]
     27  [PluginDependency("HeuristicLab.Core", "3.3")]
    2728  [PluginDependency("HeuristicLab.Core.Views", "3.3")]
    2829  [PluginDependency("HeuristicLab.Data", "3.3")]
     30  [PluginDependency("HeuristicLab.Data.Views", "3.3")]
     31  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
    2932  [PluginDependency("HeuristicLab.MainForm", "3.3")]
    3033  [PluginDependency("HeuristicLab.MainForm.WindowsForms", "3.3")]
    31   [PluginDependency("HeuristicLab.Optimization", "3.3")]
    32   [PluginDependency("HeuristicLab.Optimization.Views", "3.3")]
    3334  [PluginDependency("HeuristicLab.Problems.LinearAssignment", "3.3")]
    3435  public class HeuristicLabProblemsLinearAssignmentViewsPlugin : PluginBase {

  • trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/HeuristicLab.Problems.LinearAssignment-3.3.csproj

    r7874 r8022  
    112112  </ItemGroup>
    113113  <ItemGroup>
     114    <Compile Include="HungarianAlgorithm.cs" />
     115    <Compile Include="LAPAssignment.cs" />
    114116    <None Include="Plugin.cs.frame" />
     117    <Compile Include="Analyzers\BestLAPSolutionAnalyzer.cs" />
     118    <Compile Include="Interfaces\ILAPEvaluator.cs" />
     119    <Compile Include="LAPEvaluator.cs" />
    115120    <Compile Include="LinearAssignmentProblem.cs" />
    116121    <Compile Include="LinearAssignmentProblemSolver.cs" />
    … …  
    123128  </ItemGroup>
    124129  <ItemGroup>
     130    <ProjectReference Include="..\..\HeuristicLab.Analysis\3.3\HeuristicLab.Analysis-3.3.csproj">
     131      <Project>{887425B4-4348-49ED-A457-B7D2C26DDBF9}</Project>
     132      <Name>HeuristicLab.Analysis-3.3</Name>
     133      <Private>False</Private>
     134    </ProjectReference>
    125135    <ProjectReference Include="..\..\HeuristicLab.Collections\3.3\HeuristicLab.Collections-3.3.csproj">
    126136      <Project>{958B43BC-CC5C-4FA2-8628-2B3B01D890B6}</Project>
    … …  
    146156      <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
    147157      <Name>HeuristicLab.Data-3.3</Name>
     158      <Private>False</Private>
     159    </ProjectReference>
     160    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
     161      <Project>{DBECB8B0-B166-4133-BAF1-ED67C3FD7FCA}</Project>
     162      <Name>HeuristicLab.Encodings.PermutationEncoding-3.3</Name>
    148163      <Private>False</Private>
    149164    </ProjectReference>

  • trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblem.cs

    r7934 r8022  
    2222using System;
    2323using System.Drawing;
     24using System.Linq;
    2425using HeuristicLab.Common;
    2526using HeuristicLab.Core;
    2627using HeuristicLab.Data;
     28using HeuristicLab.Encodings.PermutationEncoding;
    2729using HeuristicLab.Optimization;
    2830using HeuristicLab.Parameters;
    2931using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     32using HeuristicLab.PluginInfrastructure;
    3033
    3134namespace HeuristicLab.Problems.LinearAssignment {
    … …  
    3336  [Creatable("Problems")]
    3437  [StorableClass]
    35   public sealed class LinearAssignmentProblem : Problem {
     38  public sealed class LinearAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<ILAPEvaluator, IPermutationCreator> {
     39    public static readonly string CostsDescription = "The cost matrix that describes the assignment of rows to columns.";
     40
    3641    public override Image ItemImage {
    3742      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
    … …  
    4247      get { return (IValueParameter<DoubleMatrix>)Parameters["Costs"]; }
    4348    }
    44     public IValueParameter<IntArray> SolutionParameter {
    45       get { return (IValueParameter<IntArray>)Parameters["Solution"]; }
     49    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
     50      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
    4651    }
    47     public IValueParameter<DoubleValue> QualityParameter {
    48       get { return (IValueParameter<DoubleValue>)Parameters["Quality"]; }
     52    public IValueParameter<Permutation> BestKnownSolutionParameter {
     53      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
    4954    }
    5055    #endregion
    … …  
    5560      set { CostsParameter.Value = value; }
    5661    }
    57     public IntArray Solution {
    58       get { return SolutionParameter.Value; }
    59       set { SolutionParameter.Value = value; }
     62    public ItemSet<Permutation> BestKnownSolutions {
     63      get { return BestKnownSolutionsParameter.Value; }
     64      set { BestKnownSolutionsParameter.Value = value; }
    6065    }
    61     public DoubleValue Quality {
    62       get { return QualityParameter.Value; }
    63       set { QualityParameter.Value = value; }
     66    public Permutation BestKnownSolution {
     67      get { return BestKnownSolutionParameter.Value; }
     68      set { BestKnownSolutionParameter.Value = value; }
    6469    }
     70    #endregion
    6571
    66     #endregion
     72    [Storable]
     73    private BestLAPSolutionAnalyzer bestLAPSolutionAnalyzer;
    6774
    6875    [StorableConstructor]
    … …  
    7077    private LinearAssignmentProblem(LinearAssignmentProblem original, Cloner cloner)
    7178      : base(original, cloner) {
     79      this.bestLAPSolutionAnalyzer = cloner.Clone(original.bestLAPSolutionAnalyzer);
    7280      AttachEventHandlers();
    7381    }
    7482    public LinearAssignmentProblem()
    75       : base() {
    76       Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", "The cost matrix that describes the assignment of rows to columns.", new DoubleMatrix(3, 3)));
    77       Parameters.Add(new OptionalValueParameter<IntArray>("Solution", "An optimal solution.", null));
    78       Parameters.Add(new OptionalValueParameter<DoubleValue>("Quality", "The solution quality.", null));
    79 
     83      : base(new LAPEvaluator(), new RandomPermutationCreator()) {
     84      Parameters.Add(new ValueParameter<DoubleMatrix>("Costs", CostsDescription, new DoubleMatrix(3, 3)));
     85      Parameters.Add(new OptionalValueParameter<ItemSet<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));
     86      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));
     87     
    8088      ((ValueParameter<DoubleMatrix>)CostsParameter).ReactOnValueToStringChangedAndValueItemImageChanged = false;
    8189
     90      bestLAPSolutionAnalyzer = new BestLAPSolutionAnalyzer();
     91      SolutionCreator.PermutationParameter.ActualName = "Assignment";
     92      InitializeOperators();
     93      Parameterize();
    8294      AttachEventHandlers();
    8395    }
    … …  
    88100
    89101    #region Events
     102    protected override void OnEvaluatorChanged() {
     103      base.OnEvaluatorChanged();
     104      Parameterize();
     105    }
     106    protected override void OnOperatorsChanged() {
     107      base.OnOperatorsChanged();
     108      Parameterize();
     109    }
     110    protected override void OnSolutionCreatorChanged() {
     111      base.OnSolutionCreatorChanged();
     112      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
     113      Parameterize();
     114    }
    90115    private void Costs_RowsChanged(object sender, EventArgs e) {
    91       if (Costs.Rows != Costs.Columns)
     116      if (Costs.Rows != Costs.Columns) {
    92117        ((IStringConvertibleMatrix)Costs).Columns = Costs.Rows;
     118        Parameterize();
     119      }
    93120    }
    94121    private void Costs_ColumnsChanged(object sender, EventArgs e) {
    95       if (Costs.Rows != Costs.Columns)
     122      if (Costs.Rows != Costs.Columns) {
    96123        ((IStringConvertibleMatrix)Costs).Rows = Costs.Columns;
     124        Parameterize();
     125      }
     126    }
     127    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
     128      Parameterize();
    97129    }
    98130    #endregion
    … …  
    107139      Costs.RowsChanged += new EventHandler(Costs_RowsChanged);
    108140      Costs.ColumnsChanged += new EventHandler(Costs_ColumnsChanged);
     141      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
     142    }
     143
     144    private void InitializeOperators() {
     145      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
     146      Operators.RemoveAll(x => x is IMoveOperator);
     147      Operators.Add(bestLAPSolutionAnalyzer);
     148    }
     149
     150    private void Parameterize() {
     151      SolutionCreator.LengthParameter.Value = new IntValue(Costs.Rows);
     152      SolutionCreator.LengthParameter.Hidden = false;
     153      Evaluator.CostsParameter.ActualName = CostsParameter.Name;
     154      Evaluator.CostsParameter.Hidden = true;
     155      Evaluator.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     156      Evaluator.AssignmentParameter.Hidden = true;
     157
     158      foreach (var op in Operators.OfType<IPermutationCrossover>()) {
     159        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     160        op.ParentsParameter.Hidden = true;
     161        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     162        op.ChildParameter.Hidden = true;
     163      }
     164
     165      foreach (var op in Operators.OfType<IPermutationManipulator>()) {
     166        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     167        op.PermutationParameter.Hidden = true;
     168      }
     169
     170      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
     171        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     172        op.PermutationParameter.Hidden = true;
     173      }
     174
     175      bestLAPSolutionAnalyzer.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
     176      bestLAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
     177      bestLAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
     178      bestLAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
     179      bestLAPSolutionAnalyzer.CostsParameter.ActualName = CostsParameter.Name;
     180      bestLAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
     181      bestLAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
    109182    }
    110183    #endregion

  • trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/LinearAssignmentProblemSolver.cs

    r7873 r8022  
    2121
    2222using HeuristicLab.Common;
     23using HeuristicLab.Core;
    2324using HeuristicLab.Data;
     25using HeuristicLab.Encodings.PermutationEncoding;
     26using HeuristicLab.Operators;
     27using HeuristicLab.Parameters;
     28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2429
    2530namespace HeuristicLab.Problems.LinearAssignment {
    26   public static class LinearAssignmentProblemSolver {
     31  [Item("LinearAssignmentProblemSolver", "Uses the hungarian algorithm to solve linear assignment problems.")]
     32  [StorableClass]
     33  public sealed class LinearAssignmentProblemSolver : SingleSuccessorOperator {
    2734    private const int UNASSIGNED = -1;
     35
     36    public ILookupParameter<DoubleMatrix> CostsParameter {
     37      get { return (ILookupParameter<DoubleMatrix>)Parameters["Costs"]; }
     38    }
     39    public ILookupParameter<Permutation> AssignmentParameter {
     40      get { return (ILookupParameter<Permutation>)Parameters["Assignment"]; }
     41    }
     42    public ILookupParameter<DoubleValue> QualityParameter {
     43      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     44    }
     45
     46    [StorableConstructor]
     47    private LinearAssignmentProblemSolver(bool deserializing) : base(deserializing) { }
     48    private LinearAssignmentProblemSolver(LinearAssignmentProblemSolver original, Cloner cloner) : base(original, cloner) { }
     49    public LinearAssignmentProblemSolver()
     50      : base() {
     51      Parameters.Add(new LookupParameter<DoubleMatrix>("Costs", LinearAssignmentProblem.CostsDescription));
     52      Parameters.Add(new LookupParameter<Permutation>("Assignment", "The assignment solution to create."));
     53      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));
     54    }
     55
     56    public override IDeepCloneable Clone(Cloner cloner) {
     57      return new LinearAssignmentProblemSolver(this, cloner);
     58    }
     59
     60    public override IOperation Apply() {
     61      var costs = CostsParameter.ActualValue;
     62      double quality;
     63      var solution = Solve(costs, out quality);
     64
     65      AssignmentParameter.ActualValue = new Permutation(PermutationTypes.Absolute, solution);
     66      QualityParameter.ActualValue = new DoubleValue(quality);
     67
     68      return base.Apply();
     69    }
    2870
    2971    /// <summary>

  • trunk/sources/HeuristicLab.Problems.LinearAssignment/3.3/Plugin.cs.frame

    r7873 r8022  
    2525  [Plugin("HeuristicLab.Problems.LinearAssignment", "3.3.6.$WCREV$")]
    2626  [PluginFile("HeuristicLab.Problems.LinearAssignment-3.3.dll", PluginFileType.Assembly)]
     27  [PluginDependency("HeuristicLab.Analysis", "3.3")]
    2728  [PluginDependency("HeuristicLab.Collections", "3.3")]
    2829  [PluginDependency("HeuristicLab.Common", "3.3")]
    … …  
    3031  [PluginDependency("HeuristicLab.Core", "3.3")]
    3132  [PluginDependency("HeuristicLab.Data", "3.3")]
     33  [PluginDependency("HeuristicLab.Encodings.PermutationEncoding", "3.3")]
     34  [PluginDependency("HeuristicLab.Operators", "3.3")]
    3235  [PluginDependency("HeuristicLab.Optimization", "3.3")]
    3336  [PluginDependency("HeuristicLab.Parameters", "3.3")]
Note: See TracChangeset for help on using the changeset viewer.