Changeset 8292


Ignore:
Timestamp:
07/16/12 09:06:27 (10 years ago)
Author:
gkronber
Message:

#1847: worked on move operators. version of the final EMSS submission

Location:
branches/GP-MoveOperators
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • branches/GP-MoveOperators/HeuristicLab.Algorithms.TabuSearch/3.3/TabuSelector.cs

    r7259 r8292  
    7575      get { return (ILookupParameter<BoolValue>)Parameters["EmptyNeighborhood"]; }
    7676    }
     77    public ILookupParameter<IRandom> RandomParameter {
     78      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     79    }
    7780
    7881    public BoolValue CopySelected {
     
    103106      Parameters.Add(new ValueLookupParameter<BoolValue>("CopySelected", "True if the selected move should be copied.", new BoolValue(false)));
    104107      Parameters.Add(new LookupParameter<BoolValue>("EmptyNeighborhood", "Will be set to true if the neighborhood didn't contain any non-tabu moves, otherwise it is set to false."));
     108      Parameters.Add(new LookupParameter<IRandom>("Random"));
    105109      CopySelectedParameter.Hidden = true;
     110    }
     111
     112    [StorableHook(HookType.AfterDeserialization)]
     113    private void AfterDeserialization() {
     114      if (!Parameters.ContainsKey("Random"))
     115        Parameters.Add(new LookupParameter<IRandom>("Random"));
    106116    }
    107117
     
    134144      }
    135145
    136       if (selected[0] == null) {
    137         EmptyNeighborhoodParameter.ActualValue = new BoolValue(true);
    138         selected[0] = new Scope("All moves are tabu.");
    139       } else EmptyNeighborhoodParameter.ActualValue = new BoolValue(false);
    140 
    141146      // remove from last to first so that the stored indices remain the same
    142147      if (!copy) {
     
    146151        }
    147152      }
     153      if (selected[0] == null) {
     154        //EmptyNeighborhoodParameter.ActualValue = new BoolValue(true);
     155        //selected[0] = new Scope("All moves are tabu.");
     156        // select a random move
     157        selected[0] = scopes[RandomParameter.ActualValue.Next(scopes.Count)];
     158      } else EmptyNeighborhoodParameter.ActualValue = new BoolValue(false);
     159
    148160
    149161      return selected;
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMove.cs

    r8206 r8292  
    2929  [StorableClass]
    3030  public class ReplaceBranchMove : Item {
    31 
     31    [Storable]
     32    public int FragmentIndex { get; set; }
    3233    [Storable]
    3334    public ISymbolicExpressionTree Tree { get; set; }
     
    5960    protected ReplaceBranchMove(ReplaceBranchMove original, Cloner cloner)
    6061      : base(original, cloner) {
     62      this.FragmentIndex = original.FragmentIndex;
    6163      this.Tree = cloner.Clone(original.Tree);
    6264      this.SubtreeIndex = original.SubtreeIndex;
     
    6870      this.Beta = original.Beta;
    6971    }
    70     public ReplaceBranchMove(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode parent, int subtreeIndex, ISymbolicExpressionTreeNode newChild, double[] originalOutput, double[] newOutput)
     72    public ReplaceBranchMove(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode parent, int subtreeIndex, ISymbolicExpressionTreeNode newChild, double[] originalOutput, double[] newOutput, int fragmentIndex)
    7173      : base() {
    7274      this.Tree = tree;
     
    7678      this.OriginalOutput = originalOutput;
    7779      this.NewOutput = newOutput;
     80      this.FragmentIndex = fragmentIndex;
    7881    }
    7982
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs

    r8286 r8292  
    8787
    8888      // prevent scaling to a constant value
    89       if (beta.IsAlmost(0.0)) beta = 10E-5;
     89      if (beta.IsAlmost(0.0)) beta = 1.0;
    9090
    9191      move.Alpha = alpha;
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveMaker.cs

    r8214 r8292  
    4848      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
    4949    }
     50    public ILookupParameter<ItemList<ISymbolicExpressionTree>> FragmentsParameter {
     51      get { return (ILookupParameter<ItemList<ISymbolicExpressionTree>>)Parameters["Fragments"]; }
     52    }
     53    public ILookupParameter<ItemList<DoubleArray>> FragmentOutputsParameter {
     54      get { return (ILookupParameter<ItemList<DoubleArray>>)Parameters["FragmentOutputs"]; }
     55    }
    5056
    5157    [StorableConstructor]
     
    5864      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The relative quality of the move."));
    5965      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree on which the move should be applied."));
     66      Parameters.Add(new LookupParameter<ItemList<ISymbolicExpressionTree>>("Fragments"));
     67      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("FragmentOutputs"));
    6068    }
    6169
     
    6573
    6674    public override IOperation Apply() {
     75      var fragments = FragmentsParameter.ActualValue;
     76      var fragmentOutputs = FragmentOutputsParameter.ActualValue;
     77
    6778      var move = ReplaceBranchMoveParameter.ActualValue;
    6879      DoubleValue moveQuality = MoveQualityParameter.ActualValue;
     
    7081
    7182      var newNode = (ISymbolicExpressionTreeNode)move.NewBranch.Clone();
     83      var oldBranch = move.Parent.GetSubtree(move.SubtreeIndex);
     84
    7285      move.Parent.RemoveSubtree(move.SubtreeIndex);
    7386      move.Parent.InsertSubtree(move.SubtreeIndex, Scale(newNode, move.Alpha, move.Beta));
    7487
     88      // move oldBranch into pool
     89      var fragmentStart = fragments[move.FragmentIndex].Root.GetSubtree(0);
     90      fragmentStart.RemoveSubtree(0);
     91      fragmentStart.AddSubtree(oldBranch);
     92      fragmentOutputs[move.FragmentIndex] = new DoubleArray(move.NewOutput);
    7593      quality.Value = moveQuality.Value;
    7694      // update solution
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs

    r8286 r8292  
    101101      ItemList<IItem> tabuList = TabuListParameter.ActualValue;
    102102      var move = ReplaceBranchMoveParameter.ActualValue;
    103       var tree = SymbolicExpressionTreeParameter.ActualValue;
    104103      bool isTabu = true;
    105104      bool useQualityAspiration = UseQualityAspirationCriterion.Value;
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs

    r8286 r8292  
    9494      get { return (IValueLookupParameter<BoolValue>)Parameters["Semantic"]; }
    9595    }
    96 
    97     private IList<ISymbolicExpressionTree> fragments;
    98     private IList<double[]> fragmentOutput;
     96    public ILookupParameter<ItemList<ISymbolicExpressionTree>> FragmentsParameter {
     97      get { return (ILookupParameter<ItemList<ISymbolicExpressionTree>>)Parameters["Fragments"]; }
     98    }
     99    public ILookupParameter<ItemList<DoubleArray>> FragmentOutputsParameter {
     100      get { return (ILookupParameter<ItemList<DoubleArray>>)Parameters["FragmentOutputs"]; }
     101    }
    99102
    100103    [StorableConstructor]
     
    119122      Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
    120123      Parameters.Add(new ValueLookupParameter<BoolValue>("Semantic", new BoolValue()));
     124      Parameters.Add(new LookupParameter<ItemList<ISymbolicExpressionTree>>("Fragments"));
     125      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("FragmentOutputs"));
    121126    }
    122127
     
    139144    }
    140145
    141     public override void ClearState() {
    142       fragments = null;
    143       fragmentOutput = null;
    144       base.ClearState();
    145     }
    146     public override void InitializeState() {
    147       fragments = null;
    148       fragmentOutput = null;
    149       base.InitializeState();
    150     }
    151 
    152146    public override IOperation Apply() {
    153147      var random = RandomParameter.ActualValue;
    154       if (fragments == null || fragmentOutput == null) {
     148      if (FragmentsParameter.ActualValue == null || FragmentOutputsParameter.ActualValue == null) {
    155149        InitializeOperator();
    156150      }
     
    176170      int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
    177171      int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
    178       var possibleInternalChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
     172      var possibleInternalChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
    179173                                      from i in Enumerable.Range(0, parent.SubtreeCount)
    180174                                      let currentChild = parent.GetSubtree(i)
    181175                                      where currentChild.SubtreeCount > 0
    182                                       where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
     176                                      where tree.Root.GetBranchLevel(currentChild) < maxDepth + 2
    183177                                      where tree.Length - currentChild.GetLength() < maxLength
    184178                                      select new CutPoint(parent, i)).ToArray();
    185179
    186       var possibleLeaveChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
     180      var possibleLeaveChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
    187181                                   from i in Enumerable.Range(0, parent.SubtreeCount)
    188182                                   let currentChild = parent.GetSubtree(i)
    189183                                   where currentChild.SubtreeCount == 0
    190                                    where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
     184                                   where tree.Root.GetBranchLevel(currentChild) < maxDepth + 2
    191185                                   where tree.Length - 1 < maxLength
    192186                                   select new CutPoint(parent, i)).ToArray();
    193 
     187      if (possibleInternalChildren.Length == 0) possibleInternalChildren = possibleLeaveChildren;
     188      if (possibleLeaveChildren.Length == 0) possibleLeaveChildren = possibleInternalChildren;
    194189
    195190      var root = (new ProgramRootSymbol()).CreateTreeNode();
     
    202197
    203198      bool semantic = SemanticParameter.ActualValue.Value;
    204 
    205       // select a random replacement point
    206       CutPoint[] possibleChildren;
    207       if (random.NextDouble() < 0.9)
    208         possibleChildren = possibleInternalChildren;
    209       else possibleChildren = possibleLeaveChildren;
    210       var selected = possibleChildren[random.Next(possibleChildren.Length)];
    211       // evaluate
    212       start.AddSubtree(selected.Parent.GetSubtree(selected.ChildIndex));
    213       var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
    214       start.RemoveSubtree(0);
    215 
    216       if (semantic) {
    217         return FindMostSimilarFragments(tree, maxLength, maxDepth, selected, random, n, output);
    218       } else {
    219         return FindRandomFragments(tree, maxLength, maxDepth, selected, random, n, output);
     199      int maxNeighbours = NeighbourhoodSizeParameter.ActualValue.Value;
     200      var count = 0;
     201      while (count < n) {
     202        // select a random replacement point
     203        CutPoint[] possibleChildren;
     204        if (random.NextDouble() < 0.9)
     205          possibleChildren = possibleInternalChildren;
     206        else possibleChildren = possibleLeaveChildren;
     207        var selected = possibleChildren[random.Next(possibleChildren.Length)];
     208        // evaluate
     209        start.AddSubtree(selected.Parent.GetSubtree(selected.ChildIndex));
     210        var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
     211        start.RemoveSubtree(0);
     212
     213        if (semantic) {
     214          foreach (var m in FindMostSimilarFragments(tree, maxLength, maxDepth, selected, random, maxNeighbours, output)) {
     215            yield return m;
     216            count++;
     217          }
     218        } else {
     219          foreach (var m in FindRandomFragments(tree, maxLength, maxDepth, selected, random, maxNeighbours, output)) {
     220            yield return m;
     221            count++;
     222          }
     223        }
    220224      }
    221225    }
     
    223227    private IEnumerable<ReplaceBranchMove> FindRandomFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
    224228  IRandom random, int maxNeighbours, double[] output) {
    225       var selectedFragments = new List<Tuple<ISymbolicExpressionTree, double[]>>(maxNeighbours);
     229      var selectedFragments = new List<int>(maxNeighbours);
    226230      int treeLength = tree.Length;
    227231      int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
     
    229233      int iterations = 0;
    230234      int maxIterations = maxNeighbours + 100;
     235      var fragments = FragmentsParameter.ActualValue;
     236      var fragmentOutput = FragmentOutputsParameter.ActualValue;
    231237      // select random fragments
    232238      while (selectedFragments.Count < maxNeighbours && iterations++ < maxIterations) {
     
    238244          parentBranchLevel + selectedFragment.Depth - 2 <= maxDepth + 2 &&
    239245          tree.Root.Grammar.IsAllowedChildSymbol(selected.Parent.Symbol, selectedFragment.Root.GetSubtree(0).GetSubtree(0).Symbol, selected.ChildIndex)) {
    240           selectedFragments.Add(Tuple.Create(selectedFragment, selectedFragmentOutput));
     246          selectedFragments.Add(r);
    241247        }
    242248      }
    243249      // yield moves (we need to add linear scaling parameters for the inserted tree)
    244250      return selectedFragments
    245         .Select(pair => new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0), output, pair.Item2));
     251        .Select(i => new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, fragments[i].Root.GetSubtree(0).GetSubtree(0), output, fragmentOutput[i].ToArray(), i));
    246252    }
    247253
    248254    private IEnumerable<ReplaceBranchMove> FindMostSimilarFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
    249255      IRandom random, int maxNeighbours, double[] output) {
    250       var bestTrees = new SortedList<double, List<Tuple<ISymbolicExpressionTree, double[]>>>(fragments.Count);
     256      var fragments = FragmentsParameter.ActualValue;
     257      var fragmentOutput = FragmentOutputsParameter.ActualValue;
     258      var bestTrees = new SortedList<double, List<int>>(fragments.Count);
    251259      int treeLength = tree.Length;
    252260      int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
     
    266274          if (similarity < 1 && ((bestTrees.Count < maxNeighbours) || similarity > bestTrees.ElementAt(0).Key)) {
    267275            if (!bestTrees.ContainsKey(similarity)) {
    268               var l = new List<Tuple<ISymbolicExpressionTree, double[]>>();
     276              var l = new List<int>();
    269277              bestTrees.Add(similarity, l);
    270278            }
    271             bestTrees[similarity].Add(Tuple.Create(fragments[i], fragmentOutput[i]));
     279            bestTrees[similarity].Add(i);
    272280            if (bestTrees.Count > maxNeighbours) bestTrees.RemoveAt(0);
    273281          }
     
    278286      while (c < maxNeighbours) {
    279287        var l = bestTrees.ElementAt(c % bestTrees.Count).Value;
    280         var pair = l[random.Next(l.Count)];
     288        var index = l[random.Next(l.Count)];
    281289        yield return
    282           new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0),
    283                                 output, pair.Item2);
     290          new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, fragments[index].Root.GetSubtree(0).GetSubtree(0),
     291                                output, fragmentOutput[index].ToArray(), index);
    284292        c++;
    285293      }
     
    313321      // enable constants again
    314322      constSym.InitialFrequency = oldConstFreq;
    315       this.fragments = trees;
    316       this.fragmentOutput = treeOutput;
     323      // set parameters
     324      FragmentsParameter.ActualValue = new ItemList<ISymbolicExpressionTree>(trees);
     325      FragmentOutputsParameter.ActualValue = new ItemList<DoubleArray>(treeOutput.Select(a => new DoubleArray(a)));
    317326    }
    318327  }
Note: See TracChangeset for help on using the changeset viewer.