Changeset 17985


Ignore:
Timestamp:
06/01/21 17:49:41 (13 days ago)
Author:
gkronber
Message:

#3106 call localsearch after mutation and recombination as well as in the main loop for the whole population

Location:
branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression/Agent.cs

    r17984 r17985  
    1 using System.Collections.Generic;
     1using System;
     2using System.Collections.Generic;
     3using System.Diagnostics;
    24
    35namespace HeuristicLab.Algorithms.DataAnalysis.ContinuedFractionRegression {
     
    79    public ContinuedFraction current;
    810    public double currentObjValue;
     11    public IList<Agent> children = new List<Agent>();
    912
    10     public IList<Agent> children = new List<Agent>();
     13    public void MaintainPocketCurrentInvariant() {
     14      if (currentObjValue < pocketObjValue) {
     15        Swap(ref pocket, ref current);
     16        Swap(ref pocketObjValue, ref currentObjValue);
     17      }
     18    }
     19
     20    public void MaintainInvariant() {
     21      foreach (var child in children) {
     22        MaintainParentChildInvariant(parent: this, child);
     23      }
     24      MaintainPocketCurrentInvariant();
     25    }
     26
     27
     28    private static void MaintainParentChildInvariant(Agent parent, Agent child) {
     29      if (child.pocketObjValue < parent.pocketObjValue) {
     30        Swap(ref child.pocket, ref parent.pocket);
     31        Swap(ref child.pocketObjValue, ref parent.pocketObjValue);
     32      }
     33    }
    1134
    1235    public IEnumerable<Agent> IterateLevels() {
     
    3154      return agents;
    3255    }
    33     internal void MaintainInvariant() {
    34       foreach (var child in children) {
    35         MaintainInvariant(parent: this, child);
    36       }
    37       if (currentObjValue < pocketObjValue) {
    38         Swap(ref pocket, ref current);
    39         Swap(ref pocketObjValue, ref currentObjValue);
    40       }
    41     }
    42 
    43 
    44     private static void MaintainInvariant(Agent parent, Agent child) {
    45       if (child.pocketObjValue < parent.pocketObjValue) {
    46         Swap(ref child.pocket, ref parent.pocket);
    47         Swap(ref child.pocketObjValue, ref parent.pocketObjValue);
    48       }
    49     }
    5056
    5157    private void IteratePostOrderRec(Agent agent, List<Agent> agents) {
     
    6975      b = temp;
    7076    }
     77
     78    internal void AssertInvariant() {
     79      Debug.Assert(pocketObjValue <= currentObjValue);
     80      foreach (var ch in children) {
     81        Debug.Assert(pocketObjValue <= ch.pocketObjValue);
     82      }
     83    }
    7184  }
    7285}
  • branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression/Algorithm.cs

    r17984 r17985  
    11using System;
    22using System.Collections.Generic;
     3using System.Diagnostics;
    34using System.Linq;
    45using System.Threading;
     
    162163      for (int gen = 1; gen <= numGen && !cancellationToken.IsCancellationRequested; gen++) {
    163164        /* mutate each current solution in the population */
    164         var pop_mu = Mutate(pop, mutationRate, rand);
     165        var pop_mu = Mutate(pop, mutationRate, rand, trainingData);
    165166        /* generate new population by recombination mechanism */
    166         var pop_r = RecombinePopulation(pop_mu, rand, nVars);
    167 
     167        var pop_r = RecombinePopulation(pop_mu, rand, nVars, trainingData);
     168
     169        // Paper:
     170        // A period of individual search operation is performed every generation on all current solutions.
     171
     172        // Statement by authors:
    168173        // "We ran the Local Search after Mutation and recombination operations. We executed the local-search only on the Current solutions."
    169174        // "We executed the MaintainInvariant() in the following steps:
     
    175180        /* local search optimization of current solutions */
    176181        foreach (var agent in pop_r.IterateLevels()) {
    177           LocalSearchSimplex(localSearchIterations, localSearchRestarts, localSearchTolerance, evalDelta, agent.current, ref agent.currentObjValue, trainingData, rand);
     182          LocalSearchSimplex(localSearchIterations, localSearchRestarts, localSearchTolerance, evalDelta, agent, trainingData, rand);
     183          Debug.Assert(agent.pocketObjValue < agent.currentObjValue);
    178184        }
    179185        foreach (var agent in pop_r.IteratePostOrder()) agent.MaintainInvariant(); // post-order to make sure that the root contains the best model
    180 
     186        foreach (var agent in pop_r.IteratePostOrder()) agent.AssertInvariant();
    181187
    182188        // for detecting stagnation we track the best objective value since the last reset
     
    252258        agent.MaintainInvariant();
    253259      }
     260
     261      foreach (var agent in pop.IteratePostOrder()) agent.AssertInvariant();
     262
    254263      return pop;
    255264    }
     
    266275      root.pocketObjValue = Evaluate(root.pocket, trainingData, Delta);
    267276
    268       foreach (var agent in root.IteratePreOrder()) { agent.MaintainInvariant(); } // Here we push the newly created model down the hierarchy.
    269     }
    270 
    271 
    272 
    273     private Agent RecombinePopulation(Agent pop, IRandom rand, int nVars) {
     277      foreach (var agent in root.IteratePreOrder()) { agent.MaintainInvariant(); } // Here we use pre-order traversal push the newly created model down the hierarchy.
     278
     279      foreach (var agent in root.IteratePostOrder()) agent.AssertInvariant();
     280
     281    }
     282
     283
     284
     285    private Agent RecombinePopulation(Agent pop, IRandom rand, int nVars, double[,] trainingData) {
    274286      var l = pop;
    275287
     
    284296        // Step 4. These steps are executed sequentially from 1 to 4. Similarly, in the
    285297        // recombination of lower-level subpopulations, we will have the new current
    286         // (the supporters generated at the previous level) as the leader of the subpopulation.
    287         l.current = Recombine(l.pocket, s1.current, SelectRandomOp(rand), rand, nVars);
    288         s3.current = Recombine(s3.pocket, l.current, SelectRandomOp(rand), rand, nVars);
    289         s1.current = Recombine(s1.pocket, s2.current, SelectRandomOp(rand), rand, nVars);
    290         s2.current = Recombine(s2.pocket, s3.current, SelectRandomOp(rand), rand, nVars);
     298        // (the supporters generated at the previous level) as the leader of the subpopulation."
     299        Recombine(l, s1, SelectRandomOp(rand), rand, nVars, trainingData);
     300        Recombine(s3, l, SelectRandomOp(rand), rand, nVars, trainingData);
     301        Recombine(s1, s2, SelectRandomOp(rand), rand, nVars, trainingData);
     302        Recombine(s2, s3, SelectRandomOp(rand), rand, nVars, trainingData);
    291303
    292304        // recombination works from top to bottom
    293305        foreach (var child in pop.children) {
    294           RecombinePopulation(child, rand, nVars);
     306          RecombinePopulation(child, rand, nVars, trainingData);
    295307        }
    296308
     
    299311    }
    300312
    301     private static ContinuedFraction Recombine(ContinuedFraction p1, ContinuedFraction p2, Func<bool[], bool[], bool[]> op, IRandom rand, int nVars) {
     313    private ContinuedFraction Recombine(Agent a, Agent b, Func<bool[], bool[], bool[]> op, IRandom rand, int nVars, double[,] trainingData) {
     314      ContinuedFraction p1 = a.pocket;
     315      ContinuedFraction p2 = b.pocket;
    302316      ContinuedFraction ch = new ContinuedFraction() { h = new Term[p1.h.Length] };
    303317      /* apply a recombination operator chosen uniformly at random on variables of two parents into offspring */
     
    332346        ch.h[i].beta = p1.h[i].beta + (rand.NextDouble() * 5 - 1) * (p2.h[i].beta - p1.h[i].beta) / 3.0;
    333347      }
    334       // return LocalSearchSimplex(ch, trainingData); // The paper has a local search step here.
    335       // The authors have stated that local search is executed after mutation and recombination
    336       // for the current solutions.
    337       // Local search and MaintainInvariant is called in the main loop (Alg 1)
     348
     349      a.current = ch;
     350      LocalSearchSimplex(LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, Delta, a, trainingData, rand);
    338351      return ch;
    339352    }
    340353
    341     private Agent Mutate(Agent pop, double mutationRate, IRandom rand) {
     354    private Agent Mutate(Agent pop, double mutationRate, IRandom rand, double[,] trainingData) {
    342355      foreach (var agent in pop.IterateLevels()) {
    343356        if (rand.NextDouble() < mutationRate) {
     
    347360          else
    348361            ModifyVariable(agent.current, rand); // soft mutation
     362
     363          // Finally, the local search operation is executed on the mutated solution in order to optimize
     364          // non-zero coefficients. We do not apply mutation on pocket solutions because we consider them as a "collective memory"
     365          // of good models visited in the past. They influence the search process via recombination only.
     366          LocalSearchSimplex(LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, Delta, agent, trainingData, rand);
    349367        }
    350368      }
     
    365383        /* Case 1: cfrac variable is turned ON: Turn OFF the variable, and either 'Remove' or
    366384         * 'Remember' the coefficient value at random */
    367         if (cfrac.vars[vIdx]) {  // CHECK: paper uses varAt()
    368           h.vars[vIdx] = false;  // CHECK: paper uses varAt()
     385        if (cfrac.vars[vIdx]) {
     386          h.vars[vIdx] = false;
    369387          h.coef[vIdx] = coinToss(0, h.coef[vIdx]);
    370388        } else {
     
    372390           * or 'Replace' the coefficient with a random value between -3 and 3 at random */
    373391          if (!h.vars[vIdx]) {
    374             h.vars[vIdx] = true;  // CHECK: paper uses varAt()
     392            h.vars[vIdx] = true;
    375393            h.coef[vIdx] = coinToss(0, rand.NextDouble() * 6 - 3);
    376394          }
     
    378396      }
    379397      /* toggle the randomly selected variable */
    380       cfrac.vars[vIdx] = !cfrac.vars[vIdx];  // CHECK: paper uses varAt()
     398      cfrac.vars[vIdx] = !cfrac.vars[vIdx];
    381399    }
    382400
     
    384402      /* randomly select a variable which is turned ON */
    385403      var candVars = new List<int>();
    386       for (int i = 0; i < cfrac.vars.Length; i++) if (cfrac.vars[i]) candVars.Add(i);  // CHECK: paper uses varAt()
     404      for (int i = 0; i < cfrac.vars.Length; i++) if (cfrac.vars[i]) candVars.Add(i);
    387405      if (candVars.Count == 0) return; // no variable active
    388406      var vIdx = candVars[rand.Next(candVars.Count)];
     
    392410
    393411      /* modify the coefficient value */
    394       if (h.vars[vIdx]) {  // CHECK: paper uses varAt()
     412      if (h.vars[vIdx]) {
    395413        h.coef[vIdx] = 0.0;
    396414      } else {
     
    398416      }
    399417      /* Toggle the randomly selected variable */
    400       h.vars[vIdx] = !h.vars[vIdx]; // CHECK: paper uses varAt()
     418      h.vars[vIdx] = !h.vars[vIdx];
    401419    }
    402420
     
    465483
    466484
    467     private static void LocalSearchSimplex(int iterations, int restarts, double tolerance, double delta, ContinuedFraction ch, ref double quality, double[,] trainingData, IRandom rand) {
     485    private static void LocalSearchSimplex(int iterations, int restarts, double tolerance, double delta, Agent a, double[,] trainingData, IRandom rand) {
    468486      double uniformPeturbation = 1.0;
    469487      int maxEvals = iterations;
     
    472490      int numSelectedRows = numRows / 5; // 20% of the training samples
    473491
    474       quality = Evaluate(ch, trainingData, delta); // get quality with origial coefficients
     492      var ch = a.current;
     493      var quality = Evaluate(ch, trainingData, delta); // get quality with original coefficients
    475494
    476495      double[] origCoeff = ExtractCoeff(ch);
     
    507526      } // reps
    508527
    509       SetCoeff(ch, bestCoeff);
    510       quality = bestQuality;
     528      SetCoeff(a.current, bestCoeff);
     529      a.currentObjValue = bestQuality;
     530
     531      // Unclear what the following means exactly.
     532      //
     533      // "We remind again that
     534      // each solution corresponds to a single model, this means that if a current model becomes better than its corresponding
     535      // pocket model (in terms of the guiding function of the solution), then an individual search optimization step is also
     536      // performed on the pocket solution/ model before we swap it with the current solution/ model. Individual search can then
     537      // make a current model better than the pocket model (again, according to the guiding function), and in that case they
     538      // switch positions within the agent that contains both of them."
     539
     540      a.MaintainPocketCurrentInvariant();
    511541    }
    512542
     
    531561        coeff.Add(hi.beta);
    532562        for (int vIdx = 0; vIdx < hi.vars.Length; vIdx++) {
    533           if (hi.vars[vIdx]) coeff.Add(hi.coef[vIdx]);
     563          if (hi.vars[vIdx] && hi.coef[vIdx] != 0) coeff.Add(hi.coef[vIdx]); // paper states twice (for mutation and recombination) that non-zero coefficients are optimized
    534564        }
    535565      }
     
    542572        hi.beta = curCoeff[k++];
    543573        for (int vIdx = 0; vIdx < hi.vars.Length; vIdx++) {
    544           if (hi.vars[vIdx]) hi.coef[vIdx] = curCoeff[k++];
     574          if (hi.vars[vIdx] && hi.coef[vIdx] != 0) hi.coef[vIdx] = curCoeff[k++]; // paper states twice (for mutation and recombination) that non-zero coefficients are optimized
    545575        }
    546576      }
Note: See TracChangeset for help on using the changeset viewer.