Opened 4 years ago

Closed 3 years ago

#2174 closed feature request (done)

Add programmable optimization problem

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.11
Component: Optimization Version: branch
Keywords: Cc:

Description (last modified by abeham)

A programmable optimization problem should be created that allows to define parameter vector and evaluation function in an easy way. This will build upon the scripting feature.

Change History (102)

comment:1 Changed 4 years ago by abeham

  • Status changed from new to accepted
  • Version changed from 3.3.9 to branch

comment:2 Changed 4 years ago by abeham

r10726: Created branch

comment:3 Changed 4 years ago by abeham

  • Description modified (diff)
  • Summary changed from Add SimSharp based simulation optimization problem to Add programmable optimization problem

r10753: The problem is now not Sim# specific anymore, but the parameters of Sim# models could be optimized using this problem. It's all about being able to program the evaluation function and parameter vector.

comment:4 Changed 4 years ago by abeham

r10754: minor refactorings

comment:5 Changed 3 years ago by abeham

r10850: Major refactoring:

  • ParameterVector is only a temporary datastructure that is constructed for evaluation purposes only
  • Multiple permutations are allowed
  • Special support for single-vector encodings (to apply specialized algorithms such as PSO or CMA-ES)
  • General support for multi-vector encoding

comment:6 Changed 3 years ago by abeham

r10855: Added crossover and manipulator for multi-vector encoding

comment:7 Changed 3 years ago by abeham

r10856: Worked on programmable problem

  • Changed ProblemBase to IProblemDefinition and SingleObjectiveProblemBase to ISingleObjectiveProblemDefinition
  • Derived ParameterVectorCreater, -Crossover, and -Manipulator from MultiOperator<> instead of InstrumentedOperator
  • Split the megamoth ScriptOnInstanceChanged to multiple methods dealing with single-vector and multi-vector encodings separately, it's still a lot of tedious code
  • Removed maximization from Configuration again (would not be consistent with multi-objective problems)

comment:9 Changed 3 years ago by abeham

r11363:

  • Removed SimSharp reference (not the purpose of this branch anymore)
  • Fixed bugs regarding parameter names when no parameter have been defined
  • Added a method to the problem definition to retrieve a neighborhood solution
    • Programmable problem now works with LocalSearch and SimulatedAnnealing

Algorithms yet to support:

  • Scatter search
  • Variable neighborhood search

comment:10 Changed 3 years ago by abeham

r11369: renamed programmable problem branch

comment:11 Changed 3 years ago by abeham

  • Description modified (diff)

After talking with the RG bioinformatics about these developments it was identified that the work of this ticket could support application of HL optimizers in their problems. Their issue is that they do have their own GUIs that allow e.g. a user to select a particular region of an image and create an optimization problem out of the data in that region. The difficult part has been that the problem needs to be described by writing a new problem class that includes all the necessary details of operator discovery, parameters, wiring, cloning, etc. The ProgrammableProblem now is a nice way of not having to do this, but relies heavily on the HeuristicLab UI. Additionally, to the UI it would be nice if this ProgrammableProblem could be instantiated in code and its definition could be given in the same code in a very intuitive and friendly manner. Because the programmable problem configures everything in the background the user doesn't need to take more care, but to assign that problem to an algorithm and start it. The following pseudo code shows such a use case and how the programmable problem could support that:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Algorithms.CMAEvolutionStrategy;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Optimization;
using HeuristicLab.Problems.Programmable;

public class MyScript : HeuristicLab.Scripting.CSharpScriptBase {
  private ManualResetEvent waitHandle = new ManualResetEvent(false);
  
  public override void Main() {
    var definition = new SingleObjectiveProblemDefinition() {
      Configuration = () => {
        return new Configuration().AddRealVector("r", 5, -1, 1);
      },
      Evaluate = (random, vector) => {
        return vector.RealVector("r").Sum(x => x * x);
      }
    };
    
    var prob = new SingleObjectiveProgrammableProblem() {
      ProblemDefinition = definition
    };
    var cmaes = new CMAEvolutionStrategy();
    cmaes.Problem = prob;
    vars.alg = cmaes;
    cmaes.ExecutionStateChanged += executionStateChanged;
    cmaes.Start();
    waitHandle.WaitOne();
  }
  
  private void executionStateChanged(object sender, EventArgs e) {
    waitHandle.Set();
  }
}

These lines of code are very simple to understand and demonstrate.

Last edited 3 years ago by abeham (previous) (diff)

comment:12 Changed 3 years ago by abeham

r11393: enabled possibility to set different problem definitions than just scripted ones (see example in the comment above)

comment:13 Changed 3 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.11

r11395: fixed parameterization of strategy vector operators

comment:14 Changed 3 years ago by abeham

  • Description modified (diff)

r11396:

  • Added analyzer operator that will call into the analyze function
  • Added helper class for creating a parameter vector
  • Added parameters to the interfaces and improved wiring

comment:15 Changed 3 years ago by abeham

r11397:

  • Renamed methods from e.g. Configuration.AddReal to Configuration.AddRealVector
  • Introduced the variable store into the single-objective problem definition script
  • Created a base class for problem definitions that are derived from in code
  • Created a view for problem definition scripts that also includes the variable store
    • It looks like a C# script view, but unfortunately, the content types are not compatible

comment:16 Changed 3 years ago by abeham

  • Description modified (diff)

comment:17 Changed 3 years ago by abeham

r11398:

  • Structured code into regions
  • Added shaking operators for the different encodings
  • Added particle and swarm operators for realvectors
  • Fixed bug in view

comment:18 Changed 3 years ago by abeham

r11399: fixed bug in particle creator/updater wiring

comment:19 Changed 3 years ago by abeham

  • Description modified (diff)

comment:20 Changed 3 years ago by abeham

  • Description modified (diff)

r11400: Added multi-objective programmable problem

comment:21 Changed 3 years ago by abeham

r11402: cleaned up API a little

comment:22 Changed 3 years ago by abeham

  • Description modified (diff)

r11405: Made single-objective programmable problem compatible with scatter search

comment:23 Changed 3 years ago by abeham

  • Owner changed from abeham to architects
  • Status changed from accepted to assigned

comment:24 Changed 3 years ago by abeham

  • Owner changed from architects to mkommend
  • Status changed from assigned to reviewing

As discussed today:

  • Please review how the name clashing between host and definition could be resolved, respectively how the host would be transparent to the user of the API.
  • Think about how the expression tree encoding could be added so that we can formulate "sentence finding problems" as well and in a similarly easy or intuitive way

comment:25 Changed 3 years ago by abeham

r11424: fixed a casting bug and bugs regarding the parameterization of move operators

comment:26 Changed 3 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to assigned

comment:27 Changed 3 years ago by abeham

I will perform the discussed refactoring

comment:28 Changed 3 years ago by abeham

  • Status changed from assigned to accepted

comment:29 Changed 3 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from accepted to reviewing

r11484: Major refactoring

  • Removed ProblemDefinitionHosts
  • Renamed ParameterVector to Individual
  • Renamed Configuration to Encoding
  • Changed handling of existing operators that they will not be removed and recreated, but only rewired

comment:30 Changed 3 years ago by abeham

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to assigned

comment:31 Changed 3 years ago by abeham

  • Status changed from assigned to accepted

comment:32 Changed 3 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from accepted to reviewing

r11485:

  • fixed some bugs
  • changed IsMaximizationProblem/Maximization to be an abstract property
  • changed Analyze to include an empty virtual definition

comment:33 Changed 3 years ago by mkommend

  • Status changed from reviewing to assigned

comment:34 Changed 3 years ago by mkommend

  • Status changed from assigned to accepted

comment:35 Changed 3 years ago by mkommend

r11543: Refactoring of encodings to allow wiring of operators within the encoding instead of the problem (work in progress).

comment:36 Changed 3 years ago by mkommend

r11546: Extracted wiring of real vector operators from the single objective programmable problem to the real encoding.

comment:37 Changed 3 years ago by mkommend

r11550: Updated IEncoding interface, adapted problems and refactored operator discovery in real encoding.

comment:38 Changed 3 years ago by mkommend

r11553: Adapted binary encoding to new wiring method.

comment:39 Changed 3 years ago by mkommend

r11559: Adapted IEncoding and Encoding base class.

comment:40 Changed 3 years ago by mkommend

r11560: Added TestFunctionProblem for evaluating the design and correctness of the new encoding classes.

comment:41 Changed 3 years ago by mkommend

r11561: Adapted IntegerEncoding to include the wiring code of operators.

comment:42 Changed 3 years ago by mkommend

r11573: Branched HeuristicLab.Optimization for the programmable problem branch.

comment:43 Changed 3 years ago by mkommend

r11574: Adapted branched optimization plugin to branch structure and updated project references.

comment:44 Changed 3 years ago by mkommend

r11575: Adapted permutation encoding.

comment:45 Changed 3 years ago by mkommend

r11582: Configured solution creator in single encodings.

comment:46 Changed 3 years ago by mkommend

r11587: Implemented multi-encoding operators and adapated wiring of operators in the programmable problems.

comment:47 Changed 3 years ago by mkommend

r11588: Adapted encodings to store their specific parameters in the standard parameter collection.

Last edited 3 years ago by mkommend (previous) (diff)

comment:48 Changed 3 years ago by mkommend

r11593: Fixed addition of parameters in the encodings and set default values for encoding operators in MultiEncodingOperator.

comment:49 Changed 3 years ago by mkommend

r11595: Added possibility to look up parameters of the encoding and removed them from the programmable problem.

comment:50 Changed 3 years ago by mkommend

r11598: Added first version of refactored individuals.

comment:51 Changed 3 years ago by mkommend

r11619: Refactored individuals.

comment:52 Changed 3 years ago by mkommend

r11645: Merged trunk changes (update to .NET 4.5).

comment:53 Changed 3 years ago by mkommend

r11655: Updated programmable problem assemblies to .NET 4.5.

comment:55 Changed 3 years ago by mkommend

r11737: Minor code cleanup in encodings.

comment:56 Changed 3 years ago by mkommend

r11739: Worked on operators and programmable problem base classes and scripts.

comment:57 Changed 3 years ago by mkommend

r11740: Added multi-objective problems.

comment:58 Changed 3 years ago by mkommend

r11746: Fixed operator wiring bugs in Integer- and PermutationEncoding.

comment:59 Changed 3 years ago by mkommend

r11753: First working version of refactored programmable problem.

comment:60 Changed 3 years ago by mkommend

r11767: Several bug fixes in programmable problem that were discovered during testing.

comment:61 Changed 3 years ago by mkommend

r11768: Further bug fixing in programmable problem.

comment:62 Changed 3 years ago by mkommend

r11773: Adapated encodings to use new type discovery mechanism.

comment:63 Changed 3 years ago by mkommend

r11774: Branched HeuristicLab.Encodings.BinaryVectorEncoding. r11775: Branched HeuristicLab.Encodings.IntegerVectorEncoding. r11776: Branched HeuristicLab.Encodings.PermutationEncoding. r11777: Branched HeuristicLab.Encodings.RealVectorEncoding.

comment:64 Changed 3 years ago by mkommend

r11778: Added encoding projects to programmable problem solution and adapted them to the branch structure.

comment:65 Changed 3 years ago by mkommend

r11779: Added sealed modifier to the IntegerEncoding.

comment:66 Changed 3 years ago by mkommend

r11780: Corrected maximization in programmable problem base classes.

comment:67 Changed 3 years ago by mkommend

r11783: Adapted access modifiers of IntegerVectorEncoding.

comment:68 Changed 3 years ago by mkommend

r11786: Changed operator parametrization in programmable problem.

comment:69 Changed 3 years ago by mkommend

r11797: Fixed namespaces in programmable problem plugin.

comment:70 Changed 3 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from accepted to reviewing

comment:71 Changed 3 years ago by abeham

r11798: Added two TODO comments

comment:72 Changed 3 years ago by mkommend

  • Component changed from ### Undefined ### to Optimization
  • Owner changed from abeham to mkommend
  • Status changed from reviewing to assigned

comment:73 Changed 3 years ago by mkommend

r11812: Updated HL.Optimization with trunk changes.

comment:74 Changed 3 years ago by mkommend

r11813: Updated views and renamed programmable problem to basic problem and added individual extension methods.

comment:75 Changed 3 years ago by mkommend

r11814: Renamed scriptable to programmable problem.

comment:76 Changed 3 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from assigned to reviewing

comment:77 Changed 3 years ago by abeham

A couple issues that I want to discuss:

  • The cloning constructor of Encoding doesn't add the TypeEqualityComparer to the encodingOperators HashSet (I added the equality comparer)
  • There is a problem with ConfigureOperators accepting IEnumerable<IOperator>. This current code in BasicProblem will not work, because Union seems to be lazy. I also thought it would be a greedy operation executing immediately, but in the debugger I saw that every iteration in for each would trigger the cloning operation:
    var operators = oldOperators.Intersect(newOperators, comparer).Select(op => cloner.Clone(op));
    operators = operators.Union(newOperators, comparer);
    newEncoding.ConfigureOperators(operators);
    
    I would suggest changing the method to accept only ICollection<IOperator> in order to avoid such problems. This also requires some other changes (I only added a ToList).
  • I also noticed, that the problem definition script would compile successfully in the script window, when there was actually an error. The algorithm would then fail complaining that the script doesn't compile. We need to be sure to throw an exception whenever the problem definition cannot be created or set.
    • For instance, adding a multi-encoding fails when the script is compiled 3 times (I have no idea why it succeeds the first two times). The exception was swallowed in ProblemDefinitionScript's Compile() method so I guess nobody noticed so far. It isn't actually the compilation that fails, but the handling of the ProblemDefinitionChanged event (I added a throw statement in the catch clause)
  • The Analyze method was missing the random number generator (I added that)

r11880:

  • Added IImprovmentOperator interface to SingleObjectiveImprover
  • Added Random parameter to Analyze method and IStochasticOperator interface to the resp. analyzer
  • Updated code template text of the compiled single- and multi-objective problem definitions
  • Prevent ProblemDefinitionScript from silently ignoring exceptions
  • Added equality comparer in Encoding's cloning constructor
  • Small adaption of ProblemDefinitionScriptView to changes in new code editor

comment:78 Changed 3 years ago by abeham

r11885:

  • Some refactorings and bug fixes
  • Renamed (Binary|Integer|Real)Encoding to (Binary|Integer|Real)VectorEncoding
  • Improved error messages when compiling programmable problems

Remark: The bug with the error after compiling a multi-encoded programmable problem the third time was due to a cloning problem of multi-encoding operators. The old encoding was cloned and thus the references did not match anymore.

Last edited 3 years ago by abeham (previous) (diff)

comment:79 Changed 3 years ago by mkommend

r11886: Corrected build order in programmable problem solution.

comment:80 Changed 3 years ago by abeham

The branch of HeuristicLab.Optimization differs from the trunk so that some problems (like JSSP) need to be adapted when merging this into the trunk (see #2302).

comment:81 Changed 3 years ago by abeham

r11892:

  • Branched ExternalEvaluation
    • Changed to use SingleObjectiveBasicProblem
    • Increased minor version number
  • Created view for MultiEncoding
  • Created dialog to construct encodings in the GUI

Setting up an external evaluation problem in HeuristicLab has finally become simple.

TODO: Add possibility to write neighborhood function in order to make use of all the algorithms. Maybe also include ability to analyze results.

Last edited 3 years ago by abeham (previous) (diff)

comment:82 Changed 3 years ago by abeham

r11893:

  • Added possibility to define neighborhood and analyze function for external evaluation problems

comment:83 Changed 3 years ago by abeham

  • Description modified (diff)

r11899:

  • Added regions to structure code
  • Added compile call to the default creator

r11900:

  • Removed compilation calls from the problem (AfterDeserialization and in cloning constructor) and instead compile instance lazily when accessed
  • Compile support code in ExternalEvaluationProblem lazy
  • Fixed encoding class names in template code files (forgot to add vector)

I think lazily compiling here is more user friendly. There could be more or less complex code running during initialize() when e.g. input data are processed into data that is required for evaluation. If that compilation step is done for every clone operation, I think it would be too much.

Last edited 3 years ago by abeham (previous) (diff)

comment:84 Changed 3 years ago by abeham

r11944:

  • Made it more visible that the problem definition needs to be recompiled.
  • Added protocol buffer tools (can be deleted before trunk integration)

comment:85 Changed 3 years ago by mkommend

r11946: Merged trunk changes into programmable problem branch.

comment:86 Changed 3 years ago by mkommend

r11949: Distributed files in programmable problem branch to the correct plugins.

comment:87 Changed 3 years ago by abeham

r11952:

  • Made encodingOperators hash set an ItemSet and private
  • Added a parameter that displays the operators of an encoding (fixedvalue showing a readonly version of the itemset)
  • Added protected methods to Encoding to add and remove operators
  • Adapted MultiEncodingView to derive from ParameterizedNamedItemView
  • Added name of MultiEncoding itself to list of forbidden names

comment:88 Changed 3 years ago by abeham

r11957: fixed alignment in tab control

comment:89 Changed 3 years ago by abeham

r11961: Integrated programmable problem into trunk

  • Fixed build configuration
  • Fixed some assembly references that had CopyLocal set to true
  • Added a missing license header
  • Cleaned some usings
  • Fixed the version number in ExternalEvaluation.GP
  • Added ProgrammableProblem and new ExternalEvaluationProblem as a reference to unit tests
  • Fixed plugin dependencies and assembly references
  • Changed icon of programmable problem to script icon
  • Fixed name clash in VRP that also had defined a "PermutationEncoding" class
  • (Hopefully) fixed all output paths

Open issues:

  • Move MultiEncoding view to Optimization.Views
  • Create interfaces I(Single|Multi)ObjectiveOperator with Quality and Maximization parameter properties and add that to the respective operators
    • Modify the *BasicProblems to weed out wrong operators
Last edited 3 years ago by abeham (previous) (diff)

comment:90 Changed 3 years ago by abeham

r11962: deleted branch

comment:91 Changed 3 years ago by abeham

r11963: Moved MultiEncodingView

comment:92 Changed 3 years ago by abeham

r11967: fixed plugin dependencies

comment:93 Changed 3 years ago by abeham

  • Owner changed from abeham to mkommend

r11970:

  • Added ISingleObjectiveOperator and IMultiObjectiveOperator interfaces
    • Added interface to all operators that would fall in either of these categories (excluding MainLoop operators)
  • Added some checks in BasicProblem on whether the MultiEncoding is being used
    • A new event handler is added that reacts on encodings being removed or added to the MultiEncoding
  • Added code to remove the non-fit operators in (Single|Multi)ObjectiveBasicProblem

Please look at the TODO in BasicProblem.cs

comment:94 Changed 3 years ago by abeham

r11971: Added interfaces

comment:95 Changed 3 years ago by mkommend

r11982: Reregistered solution creator changed event in basic problem.

comment:96 Changed 3 years ago by mkommend

r11984: Added best scope solution analyzer to single-objective programmable problem.

comment:97 Changed 3 years ago by mkommend

  • Owner changed from mkommend to abeham

comment:98 Changed 3 years ago by mkommend

r11998: Fixed Maximization handling and plugin dependencies.

comment:99 Changed 3 years ago by mkommend

r12001: Adapted script template for programmable problem (single-objective).

comment:100 Changed 3 years ago by abeham

r12002:

  • Reopened maximization parameter in ExternalEvaluationProblem
  • Added hidden flag to maximization parameter in multi-objective programmable problem

comment:101 Changed 3 years ago by ascheibe

r12003 moved old external evaluation projects to outdated plugin folder

comment:102 Changed 3 years ago by abeham

r12004: Added non-discoverable attribute to the outdated problems

comment:103 Changed 3 years ago by abeham

  • Status changed from reviewing to readytorelease

comment:104 Changed 3 years ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.