Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageCrossover.cs @ 17277

Last change on this file since 17277 was 17180, checked in by swagner, 5 years ago

#2875: Removed years in copyrights

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