source: branches/ProblemRefactoring/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageCrossover.cs @ 13361

Last change on this file since 13361 was 13361, checked in by mkommend, 4 years ago

#2521: Adapted real vector encoding, test function problems, P3, CMA-ES and optimization.

File size: 3.3 KB
RevLine 
[11663]1#region License Information
2/* HeuristicLab
[12012]3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[11838]4 * and the BEACON Center for the Study of Evolution in Action.
[11663]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;
[11987]25using HeuristicLab.Encodings.BinaryVectorEncoding;
[13339]26using HeuristicLab.Optimization;
[11663]27using HeuristicLab.Random;
28
29namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
[11838]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
[11663]33  public static class LinkageCrossover {
[11672]34    // In the GECCO paper, Figure 3
[13361]35    public static double ImproveUsingTree(LinkageTree tree, IList<BinaryVector> donors, BinaryVector solution, double fitness, ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector> problem, IRandom rand) {
[11663]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;
[11666]41        foreach (var donorIndex in options.ShuffleList(rand)) {
[11663]42          // Attempt the donation
[11987]43          fitness = Donate(solution, fitness, donors[donorIndex], cluster, problem, rand, out donorFound);
[11663]44          if (donorFound) break;
45        }
46      }
47      return fitness;
48    }
49
[13361]50    private static double Donate(BinaryVector solution, double fitness, BinaryVector source, IEnumerable<int> cluster, ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector> problem, IRandom rand, out bool changed) {
[11663]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) {
[11987]61        double newFitness = problem.Evaluate(solution, rand);
[11667]62        // if the original is strictly better, revert the change
63        if (problem.IsBetter(fitness, newFitness)) {
[11663]64          foreach (var index in flipped) {
65            solution[index] = !solution[index];
66          }
[11667]67        } else {
68          // new solution is no worse than original, keep change to solution
69          fitness = newFitness;
[11663]70        }
71      }
72      return fitness;
73    }
74  }
75}
Note: See TracBrowser for help on using the repository browser.