1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022016 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


21 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Algorithms.MemPR.Interfaces;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.PermutationEncoding;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31  using HeuristicLab.Random;


32 


33  namespace HeuristicLab.Algorithms.MemPR.Permutation.SolutionModel.Univariate {


34  [Item("Univariate solution model (Permutation.Relative)", "")]


35  [StorableClass]


36  public sealed class UnivariateRelativeModel : Item, ISolutionModel<Encodings.PermutationEncoding.Permutation> {


37  [Storable]


38  public DoubleMatrix Probabilities { get; set; }


39 


40  [Storable]


41  public IRandom Random { get; set; }


42 


43  [Storable]


44  public PermutationTypes PermutationType { get; set; }


45 


46  [StorableConstructor]


47  private UnivariateRelativeModel(bool deserializing) : base(deserializing) { }


48  private UnivariateRelativeModel(UnivariateRelativeModel original, Cloner cloner)


49  : base(original, cloner) {


50  Probabilities = cloner.Clone(original.Probabilities);


51  Random = cloner.Clone(original.Random);


52  PermutationType = original.PermutationType;


53  }


54  public UnivariateRelativeModel(IRandom random, double[,] probabilities, PermutationTypes permutationType) {


55  Probabilities = new DoubleMatrix(probabilities);


56  Random = random;


57  PermutationType = permutationType;


58  }


59  public UnivariateRelativeModel(IRandom random, DoubleMatrix probabilties, PermutationTypes permutationType) {


60  Probabilities = probabilties;


61  Random = random;


62  PermutationType = permutationType;


63  }


64 


65  public override IDeepCloneable Clone(Cloner cloner) {


66  return new UnivariateRelativeModel(this, cloner);


67  }


68 


69  public Encodings.PermutationEncoding.Permutation Sample() {


70  var N = Probabilities.Rows;


71  var next = Random.Next(N);


72  var child = new Encodings.PermutationEncoding.Permutation(PermutationType, N);


73  child[0] = next;


74  var open = Enumerable.Range(0, N).Where(x => x != next).Shuffle(Random).ToList();


75  for (var i = 1; i < N  1; i++) {


76  var total = 0.0;


77  for (var j = 0; j < open.Count; j++) {


78  total += Probabilities[next, open[j]] + 1.0 / N;


79  }


80  var ball = Random.NextDouble() * total;


81  for (var j = 0; j < open.Count; j++) {


82  ball = Probabilities[next, open[j]] + 1.0 / N;


83  if (ball <= 0.0) {


84  child[i] = open[j];


85  next = open[j];


86  open.RemoveAt(j);


87  break;


88  }


89  }


90  }


91  child[N  1] = open[0];


92  return child;


93  }


94 


95  public static UnivariateRelativeModel CreateDirected(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {


96  var model = new double[N, N];


97  for (var i = 0; i < pop.Count; i++) {


98  for (var j = 0; j < N  1; j++) {


99  for (var k = j + 1; k < N; k++) {


100  model[pop[i][j], pop[i][k]]++;


101  }


102  model[pop[i][N  1], pop[i][0]]++;


103  }


104  }


105  return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeDirected);


106  }


107 


108  public static UnivariateRelativeModel CreateDirectedWithRankBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {


109  var popSize = 0;


110  var model = new double[N, N];


111 


112  var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });


113  foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {


114  // from worst to best, worst solution has 1 vote, best solution N votes


115  popSize++;


116  for (var j = 0; j < N  1; j++) {


117  for (var k = j + 1; k < N; k++) {


118  model[ind.Solution[j], ind.Solution[k]] += popSize;


119  }


120  model[ind.Solution[N  1], ind.Solution[0]] += popSize;


121  }


122  }


123  if (popSize == 0) throw new ArgumentException("Cannot train model from empty population.");


124  return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeDirected);


125  }


126 


127  public static UnivariateRelativeModel CreateDirectedWithFitnessBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {


128  var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);


129  var factor = 1.0 / proportions.Sum();


130  var model = new double[N, N];


131 


132  foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {


133  for (var x = 0; x < model.Length; x++) {


134  for (var j = 0; j < N  1; j++) {


135  for (var k = j + 1; k < N; k++) {


136  model[ind.Solution[j], ind.Solution[k]] += ind.Proportion * factor;


137  }


138  model[ind.Solution[N  1], ind.Solution[0]] += ind.Proportion * factor;


139  }


140  }


141  }


142  return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeDirected);


143  }


144 


145  public static UnivariateRelativeModel CreateUndirected(IRandom random, IList<Encodings.PermutationEncoding.Permutation> pop, int N) {


146  var model = new double[N, N];


147  for (var i = 0; i < pop.Count; i++) {


148  for (var j = 0; j < N  1; j++) {


149  for (var k = j + 1; k < N; k++) {


150  model[pop[i][j], pop[i][k]]++;


151  model[pop[i][k], pop[i][j]]++;


152  }


153  model[pop[i][0], pop[i][N  1]]++;


154  model[pop[i][N  1], pop[i][0]]++;


155  }


156  }


157  return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeUndirected);


158  }


159 


160  public static UnivariateRelativeModel CreateUndirectedWithRankBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {


161  var popSize = 0;


162  var model = new double[N, N];


163 


164  var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });


165  foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {


166  // from worst to best, worst solution has 1 vote, best solution N votes


167  popSize++;


168  for (var j = 0; j < N  1; j++) {


169  for (var k = j + 1; k < N; k++) {


170  model[ind.Solution[j], ind.Solution[k]] += popSize;


171  model[ind.Solution[k], ind.Solution[j]] += popSize;


172  }


173  model[ind.Solution[0], ind.Solution[N  1]] += popSize;


174  model[ind.Solution[N  1], ind.Solution[0]] += popSize;


175  }


176  }


177  if (popSize == 0) throw new ArgumentException("Cannot train model from empty population.");


178  return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeUndirected);


179  }


180 


181  public static UnivariateRelativeModel CreateUndirectedWithFitnessBias(IRandom random, bool maximization, IList<Encodings.PermutationEncoding.Permutation> population, IEnumerable<double> qualities, int N) {


182  var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);


183  var factor = 1.0 / proportions.Sum();


184  var model = new double[N, N];


185 


186  foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {


187  for (var x = 0; x < model.Length; x++) {


188  for (var j = 0; j < N  1; j++) {


189  for (var k = j + 1; k < N; k++) {


190  model[ind.Solution[j], ind.Solution[k]] += ind.Proportion * factor;


191  model[ind.Solution[k], ind.Solution[j]] += ind.Proportion * factor;


192  }


193  model[ind.Solution[0], ind.Solution[N  1]] += ind.Proportion * factor;


194  model[ind.Solution[N  1], ind.Solution[0]] += ind.Proportion * factor;


195  }


196  }


197  }


198  return new UnivariateRelativeModel(random, model, PermutationTypes.RelativeUndirected);


199  }


200  }


201  }

