Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageCrossover.cs @ 11672

Last change on this file since 11672 was 11672, checked in by bgoldman, 9 years ago

#2282 Commenting, added some basic unit tests for P3.

File size: 2.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21using System;
22using System.Collections.Generic;
23using System.Linq;
24using System.Text;
25using System.Threading.Tasks;
26using HeuristicLab.Core;
27using HeuristicLab.Random;
28
29namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
30  public static class LinkageCrossover {
31    // In the GECCO paper, Figure 3
32    public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, IBinaryVectorProblem problem, IRandom rand) {
33      var options = Enumerable.Range(0, donors.Count).ToArray();
34      foreach (var cluster in tree.Clusters) {
35        // Find a donor which has at least one gene value different
36        // from the current solution for this cluster of genes
37        bool donorFound = false;
38        foreach (var donorIndex in options.ShuffleList(rand)) {
39          // Attempt the donation
40          fitness = Donate(solution, fitness, donors[donorIndex], cluster, problem, out donorFound);
41          if (donorFound) break;
42        }
43      }
44      return fitness;
45    }
46
47    private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, IBinaryVectorProblem problem, out bool changed) {
48      // keep track of which bits flipped to make the donation
49      List<int> flipped = new List<int>();
50      foreach (var index in cluster) {
51        if (solution[index] != source[index]) {
52          flipped.Add(index);
53          solution[index] = !solution[index];
54        }
55      }
56      changed = flipped.Count > 0;
57      if (changed) {
58        double newFitness = problem.Evaluate(solution);
59        // if the original is strictly better, revert the change
60        if (problem.IsBetter(fitness, newFitness)) {
61          foreach (var index in flipped) {
62            solution[index] = !solution[index];
63          }
64        } else {
65          // new solution is no worse than original, keep change to solution
66          fitness = newFitness;
67        }
68      }
69      return fitness;
70    }
71  }
72}
Note: See TracBrowser for help on using the repository browser.