Changeset 15507


Ignore:
Timestamp:
12/11/17 15:42:12 (2 years ago)
Author:
abeham
Message:

#1614:

  • fixed some bugs introduced in last commit (project file, tests)
  • fixed ApproximateLocalSearch due to change in move evaluator that outputs an absolute quality of the move and not a delta
  • added evaluated solution counting to approximate local search
  • GRASP+PR: restructured main loop and combined iteration initialization with variable creator outside
Location:
branches/GeneralizedQAP
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • branches/GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinking.cs

    r15492 r15507  
    2626using HeuristicLab.Core;
    2727using HeuristicLab.Data;
     28using HeuristicLab.Operators;
    2829using HeuristicLab.Optimization;
    2930using HeuristicLab.Optimization.Operators;
     
    111112      get { return (RandomCreator)OperatorGraph.InitialOperator; }
    112113    }
     114    private VariableCreator VariableCreator {
     115      get { return (VariableCreator)RandomCreator.Successor; }
     116    }
    113117    private SolutionsCreator SolutionsCreator {
    114       get { return (SolutionsCreator)RandomCreator.Successor; }
     118      get { return (SolutionsCreator)VariableCreator.Successor; }
     119    }
     120    private SubScopesCounter SubScopesCounter {
     121      get { return (SubScopesCounter)SolutionsCreator.Successor; }
     122    }
     123    private ResultsCollector ResultsCollector {
     124      get { return (ResultsCollector)SubScopesCounter.Successor; }
    115125    }
    116126    private GRASPWithPathRelinkingMainLoop MainLoop {
    117       get { return SolutionsCreator.Successor as GRASPWithPathRelinkingMainLoop; }
     127      get { return (GRASPWithPathRelinkingMainLoop)ResultsCollector.Successor; }
    118128    }
    119129    #endregion
     
    153163      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
    154164      randomCreator.SetSeedRandomlyParameter.Value = null;
    155 
     165     
     166      var variableCreator = new VariableCreator();
     167      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
     168      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
     169      randomCreator.Successor = variableCreator;
     170     
    156171      var solutionsCreator = new SolutionsCreator();
    157172      solutionsCreator.NumberOfSolutionsParameter.ActualName = MinimumEliteSetSizeParameter.Name;
    158173      solutionsCreator.ParallelParameter.Value = new BoolValue(true);
    159       randomCreator.Successor = solutionsCreator;
     174      variableCreator.Successor = solutionsCreator;
     175
     176      var subscopesCounter = new SubScopesCounter();
     177      subscopesCounter.Name = "EvaluatedSolutions++";
     178      subscopesCounter.AccumulateParameter.Value.Value = true;
     179      subscopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
     180      solutionsCreator.Successor = subscopesCounter;
     181
     182      var resultsCollector = new ResultsCollector();
     183      resultsCollector.CopyValue.Value = false;
     184      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "Counter for the number of times the evaluation function is called."));
     185      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The algorithm's current iteration"));
     186      subscopesCounter.Successor = resultsCollector;
    160187
    161188      var mainLoop = new GRASPWithPathRelinkingMainLoop();
     
    168195      mainLoop.PathRelinkingParameter.ActualName = PathRelinkingParameter.Name;
    169196      mainLoop.ResultsParameter.ActualName = "Results";
    170       solutionsCreator.Successor = mainLoop;
     197      resultsCollector.Successor = mainLoop;
    171198
    172199      InitializeOperators();
  • branches/GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinkingMainLoop.cs

    r15492 r15507  
    3737  [StorableClass]
    3838  public class GRASPWithPathRelinkingMainLoop : AlgorithmOperator {
     39    public IValueLookupParameter<IntValue> IterationsParameter {
     40      get { return (IValueLookupParameter<IntValue>)Parameters["Iterations"]; }
     41    }
    3942    public IValueLookupParameter<IOperator> SolutionCreatorParameter {
    4043      get { return (IValueLookupParameter<IOperator>)Parameters["SolutionCreator"]; }
     
    7477    public GRASPWithPathRelinkingMainLoop()
    7578      : base() {
     79      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations", "The algorithm's current iteration."));
    7680      Parameters.Add(new ValueLookupParameter<IOperator>("SolutionCreator", "The solution creation procedure which ideally should be a greedy initialization heuristic."));
    7781      Parameters.Add(new ValueLookupParameter<IOperator>("Evaluator", "The evaluator which calculates the fitness of a solutions."));
     
    8589      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The analyzer that is to be applied."));
    8690
    87       var variableCreator1 = new VariableCreator();
    88       variableCreator1.Name = "Iterations = 0";
    89       variableCreator1.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
    90 
    91       var resultsCollector = new ResultsCollector();
    92       resultsCollector.CopyValue = new BoolValue(false);
    93       resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
     91      var analyzer1 = new Placeholder() { Name = "(Analyzer)" };
     92      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
    9493
    9594      var selector1 = new RandomSelector();
     
    111110      var eo2 = new EmptyOperator();
    112111
    113       var placeholder1 = new Placeholder();
    114       placeholder1.Name = "(LocalImprovement)";
     112      var placeholder1 = new Placeholder() { Name = "(LocalImprovement)" };
    115113      placeholder1.OperatorParameter.ActualName = LocalImprovementParameter.Name;
    116114
     
    120118      var ssp3 = new SubScopesProcessor();
    121119
    122       var placeholder2 = new Placeholder();
    123       placeholder2.Name = "(PathRelinking)";
     120      var placeholder2 = new Placeholder() { Name = "(PathRelinking)" };
    124121      placeholder2.OperatorParameter.ActualName = PathRelinkingParameter.Name;
    125122
    126       var placeholder3 = new Placeholder();
    127       placeholder3.Name = "(Evaluator)";
     123      var placeholder3 = new Placeholder() { Name = "(Evaluator)" };
    128124      placeholder3.OperatorParameter.ActualName = EvaluatorParameter.Name;
    129125
     
    137133      placeholder4.OperatorParameter.ActualName = LocalImprovementParameter.Name;
    138134
    139       var placeholder5 = new Placeholder();
    140       placeholder5.Name = "(EliteSetReplacer)";
     135      var placeholder5 = new Placeholder() { Name = "(EliteSetReplacer)" };
    141136      placeholder5.OperatorParameter.ActualName = EliteSetReducerParameter.Name;
    142137
    143       var counter = new IntCounter();
    144       counter.Name = "Iterations++";
    145       counter.ValueParameter.ActualName = "Iterations";
     138      var counter = new IntCounter() { Name = "Iterations++" };
     139      counter.ValueParameter.ActualName = IterationsParameter.Name;
    146140      counter.Increment = new IntValue(1);
    147141
    148       var analyzer1 = new Placeholder();
    149       analyzer1.Name = "(Analyzer)";
    150       analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
    151 
    152       var comparator3 = new Comparator();
    153       comparator3.Name = "Iterations >= MaximumIterations";
     142      var analyzer2 = new Placeholder() { Name = "(Analyzer)" };
     143      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
     144
     145      var comparator3 = new Comparator() { Name = "Iterations >= MaximumIterations" };
    154146      comparator3.Comparison.Value = ComparisonType.GreaterOrEqual;
    155       comparator3.LeftSideParameter.ActualName = "Iterations";
     147      comparator3.LeftSideParameter.ActualName = IterationsParameter.Name;
    156148      comparator3.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
    157149      comparator3.ResultParameter.ActualName = "TerminatedByIteration";
    158150
    159       var conditionalBranch3 = new ConditionalBranch();
    160       conditionalBranch3.Name = "Terminate by Iterations?";
     151      var conditionalBranch3 = new ConditionalBranch() { Name = "Terminate by Iterations?" };
    161152      conditionalBranch3.ConditionParameter.ActualName = "TerminatedByIteration";
    162153
    163       OperatorGraph.InitialOperator = variableCreator1;
    164       variableCreator1.Successor = resultsCollector;
    165       resultsCollector.Successor = selector1;
     154      OperatorGraph.InitialOperator = analyzer1;
     155      analyzer1.Successor = selector1;
    166156      selector1.Successor = ssp1;
    167157      ssp1.Operators.Add(eo1);
     
    183173      placeholder4.Successor = null;
    184174      placeholder5.Successor = counter;
    185       counter.Successor = analyzer1;
    186       analyzer1.Successor = comparator3;
     175      counter.Successor = analyzer2;
     176      analyzer2.Successor = comparator3;
    187177      comparator3.Successor = conditionalBranch3;
    188178      conditionalBranch3.TrueBranch = null;
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs

    r15506 r15507  
    130130
    131131      MoveEvaluationParameter.ActualValue = moveEvaluation;
     132      MoveQualityParameter.ActualValue = new DoubleValue(problemInstance.ToSingleObjective(moveEvaluation));
    132133      return base.Apply();
    133134    }
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

    r15504 r15507  
    102102    <Compile Include="GQAPAssignment.cs" />
    103103    <Compile Include="GQAPInstance.cs" />
     104    <Compile Include="Interfaces\Parameter\IAssignmentAwareGQAPOperator.cs" />
    104105    <Compile Include="Operators\Crossovers\CordeauCrossover.cs" />
    105106    <Compile Include="SolutionCreators\SlackMinimizationSolutionCreator.cs" />
  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

    r15506 r15507  
    106106    /// <param name="maximumIterations">The maximum number of iterations that should be performed each time the candidate list is generated.</param>
    107107    /// <param name="problemInstance">The problem instance that contains the data.</param>
     108    /// <param name="evaluatedSolutions">The number of evaluated solutions.</param>
    108109    /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
    109110    public static void Apply(IRandom random, IntegerVector assignment,
    110111      DoubleValue quality, ref Evaluation evaluation, IntValue maxCLS, IntValue maximumIterations,
    111       GQAPInstance problemInstance, PercentValue oneMoveProbability) {
     112      GQAPInstance problemInstance, IntValue evaluatedSolutions, PercentValue oneMoveProbability) {
    112113      var capacities = problemInstance.Capacities;
    113114      var demands = problemInstance.Demands;
    114       //var weights = problemInstance.Weights;
    115       //var distances = problemInstance.Distances;
    116       //var installationCosts = problemInstance.InstallationCosts;
     115      var evaluations = 0.0;
     116      var deltaEvaluationFactor = 1.0 / assignment.Length;
    117117      while (true) {
    118118        int count = 0;
     
    126126         
    127127          var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
     128          evaluations += move.NewAssignments.Count * deltaEvaluationFactor;
    128129          double moveQuality = problemInstance.ToSingleObjective(moveEval);
    129130
    130           if (moveEval.ExcessDemand <= 0.0 && moveQuality < 0.0) {
     131          if (moveEval.ExcessDemand <= 0.0 && moveQuality < quality.Value) {
    131132            CLS.Add(Tuple.Create(move, moveQuality, moveEval));
    132133            sum += 1.0 / moveQuality;
     
    135136        } while (CLS.Count < maxCLS.Value && count < maximumIterations.Value);
    136137
    137         if (CLS.Count == 0)
     138        if (CLS.Count == 0) {
     139          evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
    138140          return; // END
    139         else {
     141        } else {
    140142          var ball = random.NextDouble() * sum;
    141143          var selected = CLS.Last();
     
    148150          }
    149151          NMoveMaker.Apply(assignment, selected.Item1);
    150           quality.Value += selected.Item2;
     152          quality.Value = selected.Item2;
    151153          evaluation = selected.Item3;
    152154        }
     
    163165        MaximumIterationsParameter.ActualValue,
    164166        ProblemInstanceParameter.ActualValue,
     167        EvaluatedSolutionsParameter.ActualValue,
    165168        OneMoveProbabilityParameter.ActualValue);
    166169      EvaluationParameter.ActualValue = evaluation;
  • branches/GeneralizedQAP/UnitTests/CordeauCrossoverTest.cs

    r15504 r15507  
    4545
    4646        try {
    47           CordeauCrossover.Apply(random, gqap.Maximization,
     47          CordeauCrossover.Apply(random,
    4848            parent1,
    4949            new DoubleValue(gqap.Evaluate(parent1)),
Note: See TracChangeset for help on using the changeset viewer.