Changeset 17985
 Timestamp:
 06/01/21 17:49:41 (3 years ago)
 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; 1 using System; 2 using System.Collections.Generic; 3 using System.Diagnostics; 2 4 3 5 namespace HeuristicLab.Algorithms.DataAnalysis.ContinuedFractionRegression { … … 7 9 public ContinuedFraction current; 8 10 public double currentObjValue; 11 public IList<Agent> children = new List<Agent>(); 9 12 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 } 11 34 12 35 public IEnumerable<Agent> IterateLevels() { … … 31 54 return agents; 32 55 } 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 }50 56 51 57 private void IteratePostOrderRec(Agent agent, List<Agent> agents) { … … 69 75 b = temp; 70 76 } 77 78 internal void AssertInvariant() { 79 Debug.Assert(pocketObjValue <= currentObjValue); 80 foreach (var ch in children) { 81 Debug.Assert(pocketObjValue <= ch.pocketObjValue); 82 } 83 } 71 84 } 72 85 } 
branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression/Algorithm.cs
r17984 r17985 1 1 using System; 2 2 using System.Collections.Generic; 3 using System.Diagnostics; 3 4 using System.Linq; 4 5 using System.Threading; … … 162 163 for (int gen = 1; gen <= numGen && !cancellationToken.IsCancellationRequested; gen++) { 163 164 /* mutate each current solution in the population */ 164 var pop_mu = Mutate(pop, mutationRate, rand );165 var pop_mu = Mutate(pop, mutationRate, rand, trainingData); 165 166 /* 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: 168 173 // "We ran the Local Search after Mutation and recombination operations. We executed the localsearch only on the Current solutions." 169 174 // "We executed the MaintainInvariant() in the following steps: … … 175 180 /* local search optimization of current solutions */ 176 181 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); 178 184 } 179 185 foreach (var agent in pop_r.IteratePostOrder()) agent.MaintainInvariant(); // postorder to make sure that the root contains the best model 180 186 foreach (var agent in pop_r.IteratePostOrder()) agent.AssertInvariant(); 181 187 182 188 // for detecting stagnation we track the best objective value since the last reset … … 252 258 agent.MaintainInvariant(); 253 259 } 260 261 foreach (var agent in pop.IteratePostOrder()) agent.AssertInvariant(); 262 254 263 return pop; 255 264 } … … 266 275 root.pocketObjValue = Evaluate(root.pocket, trainingData, Delta); 267 276 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 preorder 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) { 274 286 var l = pop; 275 287 … … 284 296 // Step 4. These steps are executed sequentially from 1 to 4. Similarly, in the 285 297 // recombination of lowerlevel 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); 291 303 292 304 // recombination works from top to bottom 293 305 foreach (var child in pop.children) { 294 RecombinePopulation(child, rand, nVars );306 RecombinePopulation(child, rand, nVars, trainingData); 295 307 } 296 308 … … 299 311 } 300 312 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; 302 316 ContinuedFraction ch = new ContinuedFraction() { h = new Term[p1.h.Length] }; 303 317 /* apply a recombination operator chosen uniformly at random on variables of two parents into offspring */ … … 332 346 ch.h[i].beta = p1.h[i].beta + (rand.NextDouble() * 5  1) * (p2.h[i].beta  p1.h[i].beta) / 3.0; 333 347 } 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); 338 351 return ch; 339 352 } 340 353 341 private Agent Mutate(Agent pop, double mutationRate, IRandom rand ) {354 private Agent Mutate(Agent pop, double mutationRate, IRandom rand, double[,] trainingData) { 342 355 foreach (var agent in pop.IterateLevels()) { 343 356 if (rand.NextDouble() < mutationRate) { … … 347 360 else 348 361 ModifyVariable(agent.current, rand); // soft mutation 362 363 // Finally, the local search operation is executed on the mutated solution in order to optimize 364 // nonzero 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); 349 367 } 350 368 } … … 365 383 /* Case 1: cfrac variable is turned ON: Turn OFF the variable, and either 'Remove' or 366 384 * '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; 369 387 h.coef[vIdx] = coinToss(0, h.coef[vIdx]); 370 388 } else { … … 372 390 * or 'Replace' the coefficient with a random value between 3 and 3 at random */ 373 391 if (!h.vars[vIdx]) { 374 h.vars[vIdx] = true; // CHECK: paper uses varAt()392 h.vars[vIdx] = true; 375 393 h.coef[vIdx] = coinToss(0, rand.NextDouble() * 6  3); 376 394 } … … 378 396 } 379 397 /* toggle the randomly selected variable */ 380 cfrac.vars[vIdx] = !cfrac.vars[vIdx]; // CHECK: paper uses varAt()398 cfrac.vars[vIdx] = !cfrac.vars[vIdx]; 381 399 } 382 400 … … 384 402 /* randomly select a variable which is turned ON */ 385 403 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); 387 405 if (candVars.Count == 0) return; // no variable active 388 406 var vIdx = candVars[rand.Next(candVars.Count)]; … … 392 410 393 411 /* modify the coefficient value */ 394 if (h.vars[vIdx]) { // CHECK: paper uses varAt()412 if (h.vars[vIdx]) { 395 413 h.coef[vIdx] = 0.0; 396 414 } else { … … 398 416 } 399 417 /* Toggle the randomly selected variable */ 400 h.vars[vIdx] = !h.vars[vIdx]; // CHECK: paper uses varAt()418 h.vars[vIdx] = !h.vars[vIdx]; 401 419 } 402 420 … … 465 483 466 484 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) { 468 486 double uniformPeturbation = 1.0; 469 487 int maxEvals = iterations; … … 472 490 int numSelectedRows = numRows / 5; // 20% of the training samples 473 491 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 475 494 476 495 double[] origCoeff = ExtractCoeff(ch); … … 507 526 } // reps 508 527 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(); 511 541 } 512 542 … … 531 561 coeff.Add(hi.beta); 532 562 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 nonzero coefficients are optimized 534 564 } 535 565 } … … 542 572 hi.beta = curCoeff[k++]; 543 573 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 nonzero coefficients are optimized 545 575 } 546 576 }
Note: See TracChangeset
for help on using the changeset viewer.