Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14466


Ignore:
Timestamp:
12/07/16 23:46:29 (8 years ago)
Author:
abeham
Message:

#2701:

  • Added MemPR for linear linkage (tabu walk still missing)
  • Added graph coloring problem
Location:
branches/MemPRAlgorithm
Files:
15 added
1 deleted
5 edited
7 copied

Legend:

Unmodified
Added
Removed

  • branches/MemPRAlgorithm/HeuristicLab 3.3.sln

    r14420 r14466  
    452452EndProject
    453453Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.MemPR-3.3", "HeuristicLab.Algorithms.MemPR\3.3\HeuristicLab.Algorithms.MemPR-3.3.csproj", "{9D274421-6332-4FBC-AAE4-467ACE27C368}"
     454EndProject
     455Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GraphColoring-3.3", "HeuristicLab.Problems.GraphColoring\3.3\HeuristicLab.Problems.GraphColoring-3.3.csproj", "{4B76E2CB-A990-4959-B080-1D81D418D325}"
    454456EndProject
    455457Global
    … …  
    22032205    {9D274421-6332-4FBC-AAE4-467ACE27C368}.Release|x86.ActiveCfg = Release|x86
    22042206    {9D274421-6332-4FBC-AAE4-467ACE27C368}.Release|x86.Build.0 = Release|x86
     2207    {4B76E2CB-A990-4959-B080-1D81D418D325}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     2208    {4B76E2CB-A990-4959-B080-1D81D418D325}.Debug|Any CPU.Build.0 = Debug|Any CPU
     2209    {4B76E2CB-A990-4959-B080-1D81D418D325}.Debug|x64.ActiveCfg = Debug|Any CPU
     2210    {4B76E2CB-A990-4959-B080-1D81D418D325}.Debug|x64.Build.0 = Debug|Any CPU
     2211    {4B76E2CB-A990-4959-B080-1D81D418D325}.Debug|x86.ActiveCfg = Debug|Any CPU
     2212    {4B76E2CB-A990-4959-B080-1D81D418D325}.Debug|x86.Build.0 = Debug|Any CPU
     2213    {4B76E2CB-A990-4959-B080-1D81D418D325}.Release|Any CPU.ActiveCfg = Release|Any CPU
     2214    {4B76E2CB-A990-4959-B080-1D81D418D325}.Release|Any CPU.Build.0 = Release|Any CPU
     2215    {4B76E2CB-A990-4959-B080-1D81D418D325}.Release|x64.ActiveCfg = Release|Any CPU
     2216    {4B76E2CB-A990-4959-B080-1D81D418D325}.Release|x64.Build.0 = Release|Any CPU
     2217    {4B76E2CB-A990-4959-B080-1D81D418D325}.Release|x86.ActiveCfg = Release|Any CPU
     2218    {4B76E2CB-A990-4959-B080-1D81D418D325}.Release|x86.Build.0 = Release|Any CPU
    22052219  EndGlobalSection
    22062220  GlobalSection(SolutionProperties) = preSolution

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/LocalSearch/ExhaustiveBitflipSubspace.cs

    r14450 r14466  
    2222using System.Threading;
    2323using HeuristicLab.Algorithms.MemPR.Interfaces;
     24using HeuristicLab.Algorithms.MemPR.Util;
    2425using HeuristicLab.Common;
    2526using HeuristicLab.Core;
    … …  
    4849
    4950    public void Optimize(TContext context) {
    50       var evalWrapper = new EvaluationWrapper(context);
     51      var evalWrapper = new EvaluationWrapper<BinaryVector>(context.Problem, context.Solution);
    5152      var quality = context.Solution.Fitness;
    5253      try {
    … …  
    5960      }
    6061    }
    61 
    62     public sealed class EvaluationWrapper {
    63       private readonly TContext context;
    64       private readonly ISingleObjectiveSolutionScope<BinaryVector> scope;
    65       private readonly SingleEncodingIndividual individual;
    66 
    67       public EvaluationWrapper(TContext context) {
    68         this.context = context;
    69         // don't clone the solution, which is thrown away again
    70         var cloner = new Cloner();
    71         cloner.RegisterClonedObject(context.Solution.Solution, null);
    72         this.scope = (ISingleObjectiveSolutionScope<BinaryVector>)context.Solution.Clone(cloner);
    73         this.individual = new SingleEncodingIndividual(context.Problem.Encoding, this.scope);
    74       }
    75 
    76       public double Evaluate(BinaryVector b) {
    77         scope.Solution = b;
    78         return context.Problem.Evaluate(individual, null);
    79       }
    80     }
    8162  }
    8263}

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj

    r14450 r14466  
    9696    <Compile Include="Binary\SolutionModel\Univariate\UnbiasedModelTrainer.cs" />
    9797    <Compile Include="Interfaces\Interfaces.cs" />
     98    <Compile Include="LinearLinkage\LinearLinkageMemPR.cs" />
     99    <Compile Include="LinearLinkage\LinearLinkageSolutionSubspace.cs" />
     100    <Compile Include="LinearLinkage\LinearLinkageMemPRContext.cs" />
     101    <Compile Include="LinearLinkage\LocalSearch\ExhaustiveSubspace.cs" />
     102    <Compile Include="LinearLinkage\LocalSearch\StaticAPI\ExhaustiveLocalSearch.cs" />
     103    <Compile Include="LinearLinkage\SolutionModel\Univariate\StaticAPI\Trainer.cs" />
     104    <Compile Include="LinearLinkage\SolutionModel\Univariate\UnbiasedModelTrainer.cs" />
     105    <Compile Include="LinearLinkage\SolutionModel\Univariate\UnivariateSolutionModel.cs" />
    98106    <Compile Include="MemPRAlgorithm.cs" />
    99107    <Compile Include="Permutation\PermutationMemPR.cs" />
    … …  
    106114    <Compile Include="Permutation\LocalSearch\StaticAPI\Exhaustive2Opt.cs" />
    107115    <Compile Include="Permutation\LocalSearch\StaticAPI\ExhaustiveSwap2.cs" />
    108     <Compile Include="Permutation\SimilarityCalculator.cs" />
    109116    <Compile Include="Permutation\SolutionModel\Univariate\StaticAPI\Trainer.cs" />
    110117    <Compile Include="Permutation\SolutionModel\Univariate\UnbiasedModelTrainer.cs" />
    … …  
    155162      <Private>False</Private>
    156163    </ProjectReference>
     164    <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj">
     165      <Project>{BE698769-975A-429E-828C-72BB2B6182C8}</Project>
     166      <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name>
     167      <Private>False</Private>
     168    </ProjectReference>
    157169    <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
    158170      <Project>{dbecb8b0-b166-4133-baf1-ed67c3fd7fca}</Project>
    … …  
    163175      <Project>{23da7ff4-d5b8-41b6-aa96-f0561d24f3ee}</Project>
    164176      <Name>HeuristicLab.Operators-3.3</Name>
     177      <Private>False</Private>
     178    </ProjectReference>
     179    <ProjectReference Include="..\..\HeuristicLab.Optimization.Operators\3.3\HeuristicLab.Optimization.Operators-3.3.csproj">
     180      <Project>{25087811-F74C-4128-BC86-8324271DA13E}</Project>
     181      <Name>HeuristicLab.Optimization.Operators-3.3</Name>
    165182      <Private>False</Private>
    166183    </ProjectReference>

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Interfaces/Interfaces.cs

    r14450 r14466  
    2222using System.Collections.Generic;
    2323using HeuristicLab.Algorithms.MemPR.Binary;
     24using HeuristicLab.Algorithms.MemPR.LinearLinkage;
    2425using HeuristicLab.Algorithms.MemPR.Permutation;
    2526using HeuristicLab.Core;
    … …  
    9596    new PermutationSolutionSubspace Subspace { get; }
    9697  }
     98  public interface ILinearLinkageSubspaceContext : ISolutionSubspaceContext<Encodings.LinearLinkageEncoding.LinearLinkage> {
     99    new LinearLinkageSolutionSubspace Subspace { get; }
     100  }
    97101
    98102

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

    r14456 r14466  
    2525using System.Threading;
    2626using HeuristicLab.Algorithms.MemPR.Interfaces;
     27using HeuristicLab.Algorithms.MemPR.Util;
    2728using HeuristicLab.Common;
    2829using HeuristicLab.Core;
    29 using HeuristicLab.Encodings.BinaryVectorEncoding;
     30using HeuristicLab.Encodings.LinearLinkageEncoding;
    3031using HeuristicLab.Optimization;
    3132using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    3334using HeuristicLab.Random;
    3435
    35 namespace HeuristicLab.Algorithms.MemPR.Binary {
    36   [Item("MemPR (binary)", "MemPR implementation for binary vectors.")]
     36namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     37  [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")]
    3738  [StorableClass]
    3839  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
    39   public class BinaryMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {
     40  public class LinearLinkageMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
    4041    private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
    4142   
    4243    [StorableConstructor]
    43     protected BinaryMemPR(bool deserializing) : base(deserializing) { }
    44     protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }
    45     public BinaryMemPR() {
    46       foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<BinaryMemPRPopulationContext>>())
     44    protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { }
     45    protected LinearLinkageMemPR(LinearLinkageMemPR original, Cloner cloner) : base(original, cloner) { }
     46    public LinearLinkageMemPR() {
     47      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<LinearLinkageMemPRPopulationContext>>())
    4748        SolutionModelTrainerParameter.ValidValues.Add(trainer);
    4849     
    49       foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<BinaryMemPRSolutionContext>>()) {
     50      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<LinearLinkageMemPRSolutionContext>>()) {
    5051        LocalSearchParameter.ValidValues.Add(localSearch);
    5152      }
    … …  
    5354
    5455    public override IDeepCloneable Clone(Cloner cloner) {
    55       return new BinaryMemPR(this, cloner);
    56     }
    57 
    58     protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    59       var len = a.Solution.Length;
    60       var acode = a.Solution;
    61       var bcode = b.Solution;
    62       for (var i = 0; i < len; i++)
    63         if (acode[i] != bcode[i]) return false;
    64       return true;
    65     }
    66 
    67     protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
    68       var len = a.Solution.Length;
    69       var acode = a.Solution;
    70       var bcode = b.Solution;
    71       var hamming = 0;
    72       for (var i = 0; i < len; i++)
    73         if (acode[i] != bcode[i]) hamming++;
    74       return hamming / (double)len;
    75     }
    76 
    77     protected override ISingleObjectiveSolutionScope<BinaryVector> ToScope(BinaryVector code, double fitness = double.NaN) {
    78       var creator = Problem.SolutionCreator as IBinaryVectorCreator;
    79       if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
    80       return new SingleObjectiveSolutionScope<BinaryVector>(code, creator.BinaryVectorParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
     56      return new LinearLinkageMemPR(this, cloner);
     57    }
     58
     59    protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {
     60      return a.Solution.SequenceEqual(b.Solution);
     61    }
     62
     63    protected override double Dist(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b) {
     64      if (a.Solution.Length != b.Solution.Length) throw new ArgumentException("Comparing encodings of unequal length");
     65      var dist = 0;
     66      for (var i = 0; i < a.Solution.Length; i++) {
     67        if (a.Solution[i] != b.Solution[i]) dist++;
     68      }
     69      return dist / (double)a.Solution.Length;
     70    }
     71
     72    protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> ToScope(Encodings.LinearLinkageEncoding.LinearLinkage code, double fitness = double.NaN) {
     73      var creator = Problem.SolutionCreator as ILinearLinkageCreator;
     74      if (creator == null) throw new InvalidOperationException("Can only solve linear linkage encoded problems with MemPR (linear linkage)");
     75      return new SingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
    8176        Parent = Context.Scope
    8277      };
    8378    }
    8479
    85     protected override ISolutionSubspace<BinaryVector> CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {
     80    protected override ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> CalculateSubspace(IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> solutions, bool inverse = false) {
    8681      var pop = solutions.ToList();
    8782      var N = pop[0].Length;
    … …  
    9489        }
    9590      }
    96       return new BinarySolutionSubspace(subspace);
    97     }
    98 
    99     protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    100       var evaluations = 0;
    101       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    102       if (double.IsNaN(scope.Fitness)) {
    103         Evaluate(scope, token);
    104         evaluations++;
    105       }
    106       SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
    107       var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
    108       var current = currentScope.Solution;
    109       var N = current.Length;
    110       var tabu = new Tuple<double, double>[N];
    111       for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
    112       var subN = subset != null ? subset.Count(x => x) : N;
    113       if (subN == 0) return 0;
    114       var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
    115 
    116       var steps = 0;
    117       var stepsUntilBestOfWalk = 0;
    118       for (var iter = 0; iter < int.MaxValue; iter++) {
    119         var allTabu = true;
    120         var bestOfTheRestF = double.NaN;
    121         int bestOfTheRest = -1;
    122         var improved = false;
    123 
    124         for (var i = 0; i < subN; i++) {
    125           var idx = order[i];
    126           var before = currentScope.Fitness;
    127           current[idx] = !current[idx];
    128           Evaluate(currentScope, token);
    129           evaluations++;
    130           var after = currentScope.Fitness;
    131 
    132           if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
    133             bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
    134             stepsUntilBestOfWalk = steps;
    135           }
    136 
    137           var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1;
    138           var isTabu = !IsBetter(after, qualityToBeat);
    139           if (!isTabu) allTabu = false;
    140 
    141           if (IsBetter(after, before) && !isTabu) {
    142             improved = true;
    143             steps++;
    144             tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
    145           } else { // undo the move
    146             if (!isTabu && IsBetter(after, bestOfTheRestF)) {
    147               bestOfTheRest = idx;
    148               bestOfTheRestF = after;
    149             }
    150             current[idx] = !current[idx];
    151             currentScope.Fitness = before;
    152           }
    153           if (evaluations >= maxEvals) break;
    154         }
    155         if (!allTabu && !improved) {
    156           var better = currentScope.Fitness;
    157           current[bestOfTheRest] = !current[bestOfTheRest];
    158           tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
    159           currentScope.Fitness = bestOfTheRestF;
    160           steps++;
    161         } else if (allTabu) break;
    162         if (evaluations >= maxEvals) break;
    163       }
    164 
    165       Context.IncrementEvaluatedSolutions(evaluations);
    166       scope.Adopt(bestOfTheWalk ?? currentScope);
    167       return stepsUntilBestOfWalk;
    168     }
    169 
    170     protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
    171       var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone();
    172       offspring.Fitness = double.NaN;
    173       var code = offspring.Solution;
    174       var p2Code = p2.Solution;
    175       var bp = 0;
    176       var lastbp = 0;
    177       for (var i = 0; i < code.Length; i++) {
    178         if (bp % 2 == 1) {
    179           code[i] = p2Code[i];
    180         }
    181         if (Context.Random.Next(code.Length) < i - lastbp + 1) {
    182           bp = (bp + 1) % 2;
    183           lastbp = i;
    184         }
    185       }
    186       return offspring;
    187     }
    188 
    189     protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
    190       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
    191       offspring.Fitness = double.NaN;
    192       var code = offspring.Solution;
    193       for (var i = 0; i < code.Length; i++) {
    194         if (subset != null && subset[i]) continue;
     91      return new LinearLinkageSolutionSubspace(subspace);
     92    }
     93
     94    protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) {
     95      return 0;
     96    }
     97
     98    protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Cross(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> p2Scope, CancellationToken token) {
     99      var p1 = p1Scope.Solution;
     100      var p2 = p2Scope.Solution;
     101      var transfered = new bool[p1.Length];
     102      var subspace = new bool[p1.Length];
     103      var lleeChild = new int[p1.Length];
     104      var lleep1 = p1.ToLLEe();
     105      var lleep2 = p2.ToLLEe();
     106      for (var i = p1.Length - 1; i >= 0; i--) {
     107        // Step 1
     108        subspace[i] = p1[i] != p2[i];
     109        var p1IsEnd = p1[i] == i;
     110        var p2IsEnd = p2[i] == i;
     111        if (p1IsEnd & p2IsEnd) {
     112          transfered[i] = true;
     113        } else if (p1IsEnd | p2IsEnd) {
     114          transfered[i] = Context.Random.NextDouble() < 0.5;
     115        }
     116        lleeChild[i] = i;
     117
     118        // Step 2
     119        if (transfered[i]) continue;
     120        var end1 = lleep1[i];
     121        var end2 = lleep2[i];
     122        var containsEnd1 = transfered[end1];
     123        var containsEnd2 = transfered[end2];
     124        if (containsEnd1 & containsEnd2) {
     125          if (Context.Random.NextDouble() < 0.5) {
     126            lleeChild[i] = end1;
     127          } else {
     128            lleeChild[i] = end2;
     129          }
     130        } else if (containsEnd1) {
     131          lleeChild[i] = end1;
     132        } else if (containsEnd2) {
     133          lleeChild[i] = end2;
     134        } else {
     135          if (Context.Random.NextDouble() < 0.5) {
     136            lleeChild[i] = lleeChild[p1[i]];
     137          } else {
     138            lleeChild[i] = lleeChild[p2[i]];
     139          }
     140        }
     141      }
     142      var child = new Encodings.LinearLinkageEncoding.LinearLinkage(lleeChild.Length);
     143      child.FromLLEe(lleeChild);
     144     
     145      return ToScope(child);
     146    }
     147
     148    protected override void Mutate(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> offspring, CancellationToken token, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> subspace = null) {
     149      var lle = offspring.Solution;
     150      var subset = subspace is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)subspace).Subspace : null;
     151      for (var i = 0; i < lle.Length - 1; i++) {
     152        if (subset == null || subset[i]) continue; // mutation works against crossover so aims to mutate noTouch points
    195153        if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {
    196           code[i] = !code[i];
    197           if (subset != null) subset[i] = true;
    198         }
    199       }
    200     }
    201 
    202     protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
     154          subset[i] = true;
     155          var index = Context.Random.Next(i, lle.Length);
     156          for (var j = index - 1; j >= i; j--) {
     157            if (lle[j] == index) index = j;
     158          }
     159          lle[i] = index;
     160          index = i;
     161          var idx2 = i;
     162          for (var j = i - 1; j >= 0; j--) {
     163            if (lle[j] == lle[index]) {
     164              lle[j] = idx2;
     165              index = idx2 = j;
     166            } else if (lle[j] == idx2) idx2 = j;
     167          }
     168        }
     169      }
     170    }
     171
     172    protected override ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> Relink(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> a, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> b, CancellationToken token) {
     173      var maximization = Context.Problem.Maximization;
    203174      if (double.IsNaN(a.Fitness)) {
    204175        Evaluate(a, token);
    … …  
    209180        Context.IncrementEvaluatedSolutions(1);
    210181      }
    211       if (Context.Random.NextDouble() < 0.5)
    212         return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
    213       else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);
    214     }
    215 
    216     protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
    217       var evaluations = 0;
    218       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
    219       var child = childScope.Solution;
    220       var better = betterScope.Solution;
    221       var worse = worseScope.Solution;
    222       ISingleObjectiveSolutionScope<BinaryVector> best = null;
    223       var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness;
    224       var bF = double.NaN;
    225       var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray();
    226       while (true) {
    227         var bestS = double.NaN;
    228         var bestIdx = -1;
    229         for (var i = 0; i < child.Length; i++) {
    230           var idx = order[i];
    231           // either move from worse to better or move from better away from worse
    232           if (fromWorseToBetter && child[idx] == better[idx] ||
    233             !fromWorseToBetter && child[idx] != worse[idx]) continue;
    234           child[idx] = !child[idx]; // move
    235           Evaluate(childScope, token);
    236           evaluations++;
    237           var s = childScope.Fitness;
    238           childScope.Fitness = cF;
    239           child[idx] = !child[idx]; // undo move
    240           if (IsBetter(s, cF)) {
    241             bestS = s;
    242             bestIdx = idx;
    243             break; // first-improvement
    244           }
    245           if (double.IsNaN(bestS) || IsBetter(s, bestS)) {
    246             // least-degrading
    247             bestS = s;
    248             bestIdx = idx;
    249           }
    250         }
    251         if (bestIdx < 0) break;
    252         child[bestIdx] = !child[bestIdx];
    253         cF = bestS;
    254         childScope.Fitness = cF;
    255         if (IsBetter(cF, bF)) {
    256           bF = cF;
    257           best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
    258         }
    259       }
    260       Context.IncrementEvaluatedSolutions(evaluations);
    261       return best ?? childScope;
     182      var child = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)a.Clone();
     183      var cgroups = child.Solution.GetGroups().Select(x => new HashSet<int>(x)).ToList();
     184      var g2 = b.Solution.GetGroups().ToList();
     185      var order = Enumerable.Range(0, g2.Count).Shuffle(Context.Random).ToList();
     186      ISingleObjectiveSolutionScope <Encodings.LinearLinkageEncoding.LinearLinkage> bestChild = null;
     187      for (var j = 0; j < g2.Count; j++) {
     188        var g = g2[order[j]];
     189        var changed = false;
     190        for (var k = j; k < cgroups.Count; k++) {
     191          foreach (var f in g) if (cgroups[k].Remove(f)) changed = true;
     192          if (cgroups[k].Count == 0) {
     193            cgroups.RemoveAt(k);
     194            k--;
     195          }
     196        }
     197        cgroups.Insert(0, new HashSet<int>(g));
     198        child.Solution.SetGroups(cgroups);
     199        if (changed) {
     200          Evaluate(child, token);
     201          if (bestChild == null || FitnessComparer.IsBetter(maximization, child.Fitness, bestChild.Fitness)) {
     202            bestChild = (ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage>)child.Clone();
     203          }
     204        }
     205      };
     206      return bestChild;
    262207    }
    263208  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPRContext.cs

    r14450 r14466  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
    25 using HeuristicLab.Encodings.PermutationEncoding;
     25using HeuristicLab.Encodings.LinearLinkageEncoding;
    2626using HeuristicLab.Optimization;
    2727using HeuristicLab.Parameters;
    2828using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2929
    30 namespace HeuristicLab.Algorithms.MemPR.Permutation {
    31   [Item("MemPR Population Context (permutation)", "MemPR population context for permutation encoded problems.")]
     30namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     31  [Item("MemPR Population Context (linear linkage)", "MemPR population context for linear linkage encoded problems.")]
    3232  [StorableClass]
    33   public sealed class PermutationMemPRPopulationContext : MemPRPopulationContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
     33  public sealed class LinearLinkageMemPRPopulationContext : MemPRPopulationContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
    3434
    3535    [StorableConstructor]
    36     private PermutationMemPRPopulationContext(bool deserializing) : base(deserializing) { }
    37     private PermutationMemPRPopulationContext(PermutationMemPRPopulationContext original, Cloner cloner)
     36    private LinearLinkageMemPRPopulationContext(bool deserializing) : base(deserializing) { }
     37    private LinearLinkageMemPRPopulationContext(LinearLinkageMemPRPopulationContext original, Cloner cloner)
    3838      : base(original, cloner) { }
    39     public PermutationMemPRPopulationContext() : base("PermutationMemPRPopulationContext") { }
    40     public PermutationMemPRPopulationContext(string name) : base(name) { }
     39    public LinearLinkageMemPRPopulationContext() : base("LinearLinkageMemPRPopulationContext") { }
     40    public LinearLinkageMemPRPopulationContext(string name) : base(name) { }
    4141
    4242    public override IDeepCloneable Clone(Cloner cloner) {
    43       return new PermutationMemPRPopulationContext(this, cloner);
     43      return new LinearLinkageMemPRPopulationContext(this, cloner);
    4444    }
    4545
    46     public override PermutationMemPRSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> solution) {
    47       return new PermutationMemPRSolutionContext(this, solution);
     46    public override LinearLinkageMemPRSolutionContext CreateSingleSolutionContext(ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> solution) {
     47      return new LinearLinkageMemPRSolutionContext(this, solution);
    4848    }
    4949  }
    5050
    51   [Item("MemPR Solution Context (permutation)", "MemPR solution context for permutation encoded problems.")]
     51  [Item("MemPR Solution Context (linear linkage)", "MemPR solution context for linear linkage encoded problems.")]
    5252  [StorableClass]
    53   public sealed class PermutationMemPRSolutionContext : MemPRSolutionContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext>, IPermutationSubspaceContext {
     53  public sealed class LinearLinkageMemPRSolutionContext : MemPRSolutionContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext>, ILinearLinkageSubspaceContext {
    5454
    5555    [Storable]
    56     private IValueParameter<PermutationSolutionSubspace> subspace;
    57     public PermutationSolutionSubspace Subspace {
     56    private IValueParameter<LinearLinkageSolutionSubspace> subspace;
     57    public LinearLinkageSolutionSubspace Subspace {
    5858      get { return subspace.Value; }
    5959    }
    60     ISolutionSubspace<Encodings.PermutationEncoding.Permutation> ISolutionSubspaceContext<Encodings.PermutationEncoding.Permutation>.Subspace {
     60    ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> ISolutionSubspaceContext<Encodings.LinearLinkageEncoding.LinearLinkage>.Subspace {
    6161      get { return Subspace; }
    6262    }
    6363
    6464    [StorableConstructor]
    65     private PermutationMemPRSolutionContext(bool deserializing) : base(deserializing) { }
    66     private PermutationMemPRSolutionContext(PermutationMemPRSolutionContext original, Cloner cloner)
     65    private LinearLinkageMemPRSolutionContext(bool deserializing) : base(deserializing) { }
     66    private LinearLinkageMemPRSolutionContext(LinearLinkageMemPRSolutionContext original, Cloner cloner)
    6767      : base(original, cloner) {
    6868
    6969    }
    70     public PermutationMemPRSolutionContext(PermutationMemPRPopulationContext baseContext, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> solution)
     70    public LinearLinkageMemPRSolutionContext(LinearLinkageMemPRPopulationContext baseContext, ISingleObjectiveSolutionScope<Encodings.LinearLinkageEncoding.LinearLinkage> solution)
    7171      : base(baseContext, solution) {
    7272
    73       Parameters.Add(subspace = new ValueParameter<PermutationSolutionSubspace>("Subspace", new PermutationSolutionSubspace(null)));
     73      Parameters.Add(subspace = new ValueParameter<LinearLinkageSolutionSubspace>("Subspace", new LinearLinkageSolutionSubspace(null)));
    7474    }
    7575
    7676    public override IDeepCloneable Clone(Cloner cloner) {
    77       return new PermutationMemPRSolutionContext(this, cloner);
     77      return new LinearLinkageMemPRSolutionContext(this, cloner);
    7878    }
    7979  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageSolutionSubspace.cs

    r14450 r14466  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
    25 using HeuristicLab.Encodings.BinaryVectorEncoding;
    2625using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2726
    28 namespace HeuristicLab.Algorithms.MemPR.Binary {
    29   [Item("Solution subspace (binary)", "")]
     27namespace HeuristicLab.Algorithms.MemPR.LinearLinkage {
     28  [Item("Solution subspace (linear linkage)", "")]
    3029  [StorableClass]
    31   public sealed class BinarySolutionSubspace : Item, ISolutionSubspace<BinaryVector> {
     30  public sealed class LinearLinkageSolutionSubspace : Item, ISolutionSubspace<Encodings.LinearLinkageEncoding.LinearLinkage> {
    3231
    3332    [Storable]
    … …  
    3635
    3736    [StorableConstructor]
    38     private BinarySolutionSubspace(bool deserializing) : base(deserializing) { }
    39     private BinarySolutionSubspace(BinarySolutionSubspace original, Cloner cloner)
     37    private LinearLinkageSolutionSubspace(bool deserializing) : base(deserializing) { }
     38    private LinearLinkageSolutionSubspace(LinearLinkageSolutionSubspace original, Cloner cloner)
    4039      : base(original, cloner) {
    4140      subspace = (bool[])original.subspace.Clone();
    4241    }
    43     public BinarySolutionSubspace(bool[] subspace) {
     42    public LinearLinkageSolutionSubspace(bool[] subspace) {
    4443      this.subspace = subspace;
    4544    }
    4645
    4746    public override IDeepCloneable Clone(Cloner cloner) {
    48       return new BinarySolutionSubspace(this, cloner);
     47      return new LinearLinkageSolutionSubspace(this, cloner);
    4948    }
    5049  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LocalSearch/ExhaustiveSubspace.cs

    r14450 r14466  
    2222using System.Threading;
    2323using HeuristicLab.Algorithms.MemPR.Interfaces;
     24using HeuristicLab.Algorithms.MemPR.Util;
    2425using HeuristicLab.Common;
    2526using HeuristicLab.Core;
    26 using HeuristicLab.Encodings.Binary.LocalSearch;
    27 using HeuristicLab.Encodings.BinaryVectorEncoding;
     27using HeuristicLab.Encodings.LinearLinkageEncoding;
    2828using HeuristicLab.Optimization;
    2929using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3030
    31 namespace HeuristicLab.Algorithms.MemPR.Binary.LocalSearch {
    32   [Item("Exhaustive Bitflip Local (Subspace) Search (binary)", "", ExcludeGenericTypeInfo = true)]
     31namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.LocalSearch {
     32  [Item("Exhaustive Local (Subspace) Search (linear linkage)", "", ExcludeGenericTypeInfo = true)]
    3333  [StorableClass]
    34   public class ExhaustiveBitflipSubspace<TContext> : NamedItem, ILocalSearch<TContext>
    35       where TContext : ISingleSolutionHeuristicAlgorithmContext<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector>, IBinaryVectorSubspaceContext {
     34  public class ExhaustiveSubspace<TContext> : NamedItem, ILocalSearch<TContext>
     35      where TContext : ISingleSolutionHeuristicAlgorithmContext<SingleObjectiveBasicProblem<LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage>, ILinearLinkageSubspaceContext {
    3636
    3737    [StorableConstructor]
    38     protected ExhaustiveBitflipSubspace(bool deserializing) : base(deserializing) { }
    39     protected ExhaustiveBitflipSubspace(ExhaustiveBitflipSubspace<TContext> original, Cloner cloner) : base(original, cloner) { }
    40     public ExhaustiveBitflipSubspace() {
     38    protected ExhaustiveSubspace(bool deserializing) : base(deserializing) { }
     39    protected ExhaustiveSubspace(ExhaustiveSubspace<TContext> original, Cloner cloner) : base(original, cloner) { }
     40    public ExhaustiveSubspace() {
    4141      Name = ItemName;
    4242      Description = ItemDescription;
    … …  
    4444
    4545    public override IDeepCloneable Clone(Cloner cloner) {
    46       return new ExhaustiveBitflipSubspace<TContext>(this, cloner);
     46      return new ExhaustiveSubspace<TContext>(this, cloner);
    4747    }
    4848
    4949    public void Optimize(TContext context) {
    50       var evalWrapper = new EvaluationWrapper(context);
     50      var evalWrapper = new EvaluationWrapper<Encodings.LinearLinkageEncoding.LinearLinkage>(context.Problem, context.Solution);
    5151      var quality = context.Solution.Fitness;
    5252      try {
    53         var result = ExhaustiveBitflip.Optimize(context.Random, context.Solution.Solution, ref quality,
     53        var result = ExhaustiveLocalSearch.Optimize(context.Random, context.Solution.Solution, ref quality,
    5454          context.Problem.Maximization, evalWrapper.Evaluate, CancellationToken.None, context.Subspace.Subspace);
    5555        context.IncrementEvaluatedSolutions(result.Item1);
    … …  
    5959      }
    6060    }
    61 
    62     public sealed class EvaluationWrapper {
    63       private readonly TContext context;
    64       private readonly ISingleObjectiveSolutionScope<BinaryVector> scope;
    65       private readonly SingleEncodingIndividual individual;
    66 
    67       public EvaluationWrapper(TContext context) {
    68         this.context = context;
    69         // don't clone the solution, which is thrown away again
    70         var cloner = new Cloner();
    71         cloner.RegisterClonedObject(context.Solution.Solution, null);
    72         this.scope = (ISingleObjectiveSolutionScope<BinaryVector>)context.Solution.Clone(cloner);
    73         this.individual = new SingleEncodingIndividual(context.Problem.Encoding, this.scope);
    74       }
    75 
    76       public double Evaluate(BinaryVector b) {
    77         scope.Solution = b;
    78         return context.Problem.Evaluate(individual, null);
    79       }
    80     }
    8161  }
    8262}

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnbiasedModelTrainer.cs

    r14450 r14466  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
    26 using HeuristicLab.Encodings.BinaryVectorEncoding;
    2726using HeuristicLab.Optimization;
    2827using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2928
    30 namespace HeuristicLab.Algorithms.MemPR.Binary.SolutionModel.Univariate {
    31   [Item("Unbiased Univariate Model Trainer (binary)", "", ExcludeGenericTypeInfo = true)]
     29namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.SolutionModel.Univariate {
     30  [Item("Unbiased Univariate Model Trainer (linear linkage)", "", ExcludeGenericTypeInfo = true)]
    3231  [StorableClass]
    3332  public class UniasedModelTrainer<TContext> : NamedItem, ISolutionModelTrainer<TContext>
    34     where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector>, ISolutionModelContext<BinaryVector> {
     33    where TContext : IPopulationBasedHeuristicAlgorithmContext<SingleObjectiveBasicProblem<Encodings.LinearLinkageEncoding.LinearLinkageEncoding>, Encodings.LinearLinkageEncoding.LinearLinkage>, ISolutionModelContext<Encodings.LinearLinkageEncoding.LinearLinkage> {
    3534   
    3635    [StorableConstructor]
    … …  
    4746
    4847    public void TrainModel(TContext context) {
    49       context.Model = Trainer.TrainUnbiased(context.Random, context.Population.Select(x => x.Solution));
     48      context.Model = Trainer.Train(context.Random, context.Population.Select(x => x.Solution));
    5049    }
    5150  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs

    r14450 r14466  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Linq;
    2524using HeuristicLab.Algorithms.MemPR.Interfaces;
    2625using HeuristicLab.Common;
    2726using HeuristicLab.Core;
    2827using HeuristicLab.Data;
    29 using HeuristicLab.Encodings.BinaryVectorEncoding;
    3028using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    31 using HeuristicLab.Random;
    3229
    33 namespace HeuristicLab.Algorithms.MemPR.Binary.SolutionModel.Univariate {
    34   [Item("Univariate solution model (binary)", "")]
     30namespace HeuristicLab.Algorithms.MemPR.LinearLinkage.SolutionModel.Univariate {
     31  [Item("Univariate solution model (linear linkage)", "")]
    3532  [StorableClass]
    36   public sealed class UnivariateModel : Item, ISolutionModel<BinaryVector> {
     33  public sealed class UnivariateModel : Item, ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> {
    3734    [Storable]
    38     public DoubleArray Probabilities { get; set; }
     35    public IntMatrix Frequencies { get; set; }
    3936    [Storable]
    4037    public IRandom Random { get; set; }
     38    [Storable]
     39    public IntValue Maximum { get; set; }
    4140
    4241    [StorableConstructor]
    … …  
    4443    private UnivariateModel(UnivariateModel original, Cloner cloner)
    4544      : base(original, cloner) {
    46       Probabilities = cloner.Clone(original.Probabilities);
     45      Frequencies = cloner.Clone(original.Frequencies);
    4746      Random = cloner.Clone(original.Random);
    4847    }
    49     public UnivariateModel(IRandom random, int N) : this(random, Enumerable.Range(0, N).Select(x => 0.5).ToArray()) { }
    50     public UnivariateModel(IRandom random, double[] probabilities) {
    51       Probabilities = new DoubleArray(probabilities);
     48    public UnivariateModel(IRandom random, int[,] frequencies, int max) {
     49      Frequencies = new IntMatrix(frequencies);
    5250      Random = random;
     51      Maximum = new IntValue(max);
    5352    }
    54     public UnivariateModel(IRandom random, DoubleArray probabilties) {
    55       Probabilities = probabilties;
     53    public UnivariateModel(IRandom random, IntMatrix frequencies, int max) {
     54      Frequencies = frequencies;
    5655      Random = random;
     56      Maximum = new IntValue(max);
    5757    }
    5858
    … …  
    6161    }
    6262
    63     public BinaryVector Sample() {
    64       var vec = new BinaryVector(Probabilities.Length);
    65       for (var i = 0; i < Probabilities.Length; i++)
    66         vec[i] = Random.NextDouble() < Probabilities[i];
    67       return vec;
     63    public Encodings.LinearLinkageEncoding.LinearLinkage Sample() {
     64      var N = Frequencies.Rows;
     65      var centroid = new Encodings.LinearLinkageEncoding.LinearLinkage(N);
     66      var dict = new Dictionary<int, int>();
     67      for (var i = N - 1; i >= 0; i--) {
     68        centroid[i] = i; // default be a cluster of your own
     69        for (var j = i + 1; j < N; j++) {
     70          // try to find a suitable link
     71          if (Maximum.Value * Random.NextDouble() < Frequencies[i, j]) {
     72            int pred;
     73            if (dict.TryGetValue(j, out pred)) {
     74              int tmp, k = pred;
     75              while (dict.TryGetValue(k, out tmp)) {
     76                if (k == tmp) break;
     77                k = tmp;
     78              }
     79              centroid[i] = k;
     80            } else centroid[i] = j;
     81            dict[centroid[i]] = i;
     82            break;
     83          }
     84        }
     85      }
     86      return centroid;
    6887    }
    6988
    70     public static ISolutionModel<BinaryVector> CreateWithoutBias(IRandom random, IEnumerable<BinaryVector> population) {
    71       double[] model = null;
    72       var popSize = 0;
    73       foreach (var p in population) {
     89    public static ISolutionModel<Encodings.LinearLinkageEncoding.LinearLinkage> Create(IRandom random, IEnumerable<Encodings.LinearLinkageEncoding.LinearLinkage> population) {
     90      var iter = population.GetEnumerator();
     91      if (!iter.MoveNext()) throw new ArgumentException("Cannot create solution model from empty population.");
     92      var popSize = 1;
     93      var N = iter.Current.Length;
     94      var freq = new int[N, N];
     95      do {
     96        var current = iter.Current;
    7497        popSize++;
    75         if (model == null) model = new double[p.Length];
    76         for (var x = 0; x < model.Length; x++) {
    77           if (p[x]) model[x]++;
     98        foreach (var g in current.GetGroups()) {
     99          for (var i = 0; i < g.Count - 1; i++)
     100            for (var j = i + 1; j < g.Count; j++) {
     101              freq[g[i], g[j]]++;
     102              freq[g[j], g[i]]++;
     103            }
    78104        }
    79       }
    80       if (model == null) throw new ArgumentException("Cannot train model from empty population.");
    81       // normalize to [0;1]
    82       var factor = 1.0 / popSize;
    83       for (var x = 0; x < model.Length; x++) {
    84         model[x] *= factor;
    85       }
    86       return new UnivariateModel(random, model);
    87     }
    88 
    89     public static ISolutionModel<BinaryVector> CreateWithRankBias(IRandom random, bool maximization, IEnumerable<BinaryVector> population, IEnumerable<double> qualities) {
    90       var popSize = 0;
    91 
    92       double[] model = null;
    93       var pop = population.Zip(qualities, (b, q) => new { Solution = b, Fitness = q });
    94       foreach (var ind in maximization ? pop.OrderBy(x => x.Fitness) : pop.OrderByDescending(x => x.Fitness)) {
    95         // from worst to best, worst solution has 1 vote, best solution N votes
    96         popSize++;
    97         if (model == null) model = new double[ind.Solution.Length];
    98         for (var x = 0; x < model.Length; x++) {
    99           if (ind.Solution[x]) model[x] += popSize;
    100         }
    101       }
    102       if (model == null) throw new ArgumentException("Cannot train model from empty population.");
    103       // normalize to [0;1]
    104       var factor = 2.0 / (popSize + 1);
    105       for (var i = 0; i < model.Length; i++) {
    106         model[i] *= factor / popSize;
    107       }
    108       return new UnivariateModel(random, model);
    109     }
    110 
    111     public static ISolutionModel<BinaryVector> CreateWithFitnessBias(IRandom random, bool maximization, IEnumerable<BinaryVector> population, IEnumerable<double> qualities) {
    112       var proportions = RandomEnumerable.PrepareProportional(qualities, true, !maximization);
    113       var factor = 1.0 / proportions.Sum();
    114       double[] model = null;
    115       foreach (var ind in population.Zip(proportions, (p, q) => new { Solution = p, Proportion = q })) {
    116         if (model == null) model = new double[ind.Solution.Length];
    117         for (var x = 0; x < model.Length; x++) {
    118           if (ind.Solution[x]) model[x] += ind.Proportion * factor;
    119         }
    120       }
    121       if (model == null) throw new ArgumentException("Cannot train model from empty population.");
    122       return new UnivariateModel(random, model);
     105      } while (iter.MoveNext());
     106      return new UnivariateModel(random, freq, popSize);
    123107    }
    124108  }

  • branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs

    r14456 r14466  
    7272
    7373    private static double Dist(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
    74       return 1.0 - PermutationSimilarityCalculator.CalculateSimilarity(a, b);
     74      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
    7575    }
    7676

  • branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/Plugin.cs.frame

    r14429 r14466  
    2222using HeuristicLab.PluginInfrastructure;
    2323
    24 namespace HeuristicLab.Problems.Instances.CordeauGQAP {
    25   [Plugin("HeuristicLab.Problems.Instances.CordeauGQAP", "3.3.14.$WCREV$")]
    26   [PluginFile("HeuristicLab.Problems.Instances.CordeauGQAP-3.3.dll", PluginFileType.Assembly)]
    27   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
    28   public class HeuristicLabProblemsInstancesCordeauGQAPPlugin : PluginBase {
     24namespace HeuristicLab.Problems.GraphColoring {
     25  [Plugin("HeuristicLab.Problems.GraphColoring", "3.3.14.$WCREV$")]
     26  [PluginFile("HeuristicLab.Problems.GraphColoring-3.3.dll", PluginFileType.Assembly)]
     27  [PluginDependency("HeuristicLab.Collections", "3.3")]
     28  [PluginDependency("HeuristicLab.Common", "3.3")]
     29  [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
     30  [PluginDependency("HeuristicLab.Core", "3.3")]
     31  [PluginDependency("HeuristicLab.Data", "3.3")]
     32  [PluginDependency("HeuristicLab.Encodings.LinearLinkageEncoding", "3.3")]
     33  [PluginDependency("HeuristicLab.Operators", "3.3")]
     34  [PluginDependency("HeuristicLab.Optimization", "3.3")]
     35  [PluginDependency("HeuristicLab.Parameters", "3.3")]
     36  [PluginDependency("HeuristicLab.Persistence", "3.3")]
     37  public class HeuristicLabProblemsGraphColoringPlugin : PluginBase {
    2938  }
    3039}
Note: See TracChangeset for help on using the changeset viewer.