Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/SolutionsCaching/PermutationSolutionDictionary.cs @ 9754

Last change on this file since 9754 was 9754, checked in by ascheibe, 11 years ago

#1886 added a caching analyzer for crossover

File size: 5.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Encodings.PermutationEncoding;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Analysis.AlgorithmBehavior.Analyzers {
31  [Item("PermutationSolutionDictionary", "Stores permutations generated by an algorithm.")]
32  [StorableClass]
33  public class PermutationSolutionDictionary : SolutionDictionary<PermutationWrapper, PermutationInformation> {
34    [Storable]
35    protected Dictionary<PermutationWrapper, List<PermutationInformation>> solutionDictionary;
36    public Dictionary<PermutationWrapper, List<PermutationInformation>> SolutionDictionary { get { return solutionDictionary; } }
37
38    public PermutationSolutionDictionary() {
39      solutionDictionary = new Dictionary<PermutationWrapper, List<PermutationInformation>>(new PermutationWrapperEqualityComparer());
40    }
41
42    [StorableConstructor]
43    protected PermutationSolutionDictionary(bool deserializing) : base(deserializing) { }
44    protected PermutationSolutionDictionary(PermutationSolutionDictionary original, Cloner cloner)
45      : base(original, cloner) {
46      this.solutionDictionary = new Dictionary<PermutationWrapper, List<PermutationInformation>>(original.solutionDictionary, new PermutationWrapperEqualityComparer());
47    }
48
49    public override int Size() {
50      return solutionDictionary.Count;
51    }
52
53    public override void Add(PermutationWrapper key, PermutationInformation value) {
54      if (solutionDictionary.Count == 0) {
55        var lst = new List<PermutationInformation>();
56        lst.Add(value);
57        solutionDictionary.Add(key, lst);
58        return;
59      }
60
61      if (ContainsKey(key)) {
62        if (!solutionDictionary[key].Contains(value))
63          solutionDictionary[key].Add(value);
64      } else {
65        InsertKeyValue(key, value);
66      }
67    }
68
69    protected override void InsertKeyValue(PermutationWrapper key, PermutationInformation value) {
70      int diffCnt;
71      Permutation p = key.GetPermutation();
72      Permutation ms = GetMostSimilarSolution(p, out diffCnt);
73
74      if (diffCnt < ms.Length / 2) {
75        key.StorePartialPermutation(ms, p);
76      }
77
78      var lst = new List<PermutationInformation>();
79      lst.Add(value);
80      solutionDictionary.Add(key, lst);
81    }
82
83    private Permutation GetMostSimilarSolution(Permutation permutation, out int diffCnt) {
84      Permutation result = null; int min = int.MaxValue;
85      foreach (PermutationWrapper p in solutionDictionary.Keys.Where(x => x.ElementType == ElementType.Complete)) {
86        Permutation pr = p.GetPermutation();
87        int diffs = CountDiffs(permutation, pr);
88        if (diffs < min) {
89          result = pr;
90          min = diffs;
91        }
92      }
93      diffCnt = min;
94      return result;
95    }
96
97    private int CountDiffs(Permutation x, Permutation y) {
98      int result = 0;
99      // yes we ignore path encoding at the moment
100      for (int i = 0; i < x.Length; i++) {
101        if (x[i] != y[i]) result++;
102      }
103      return result;
104    }
105
106    public PermutationWrapper GetPermutationWrapperOfPermutation(Permutation permutation) {
107      PermutationEqualityComparer peq = new PermutationEqualityComparer();
108      var res = solutionDictionary.Where(x => peq.GetHashCode(x.Key.GetPermutation()) == peq.GetHashCode(permutation));
109
110      //TODO: fix this
111      if (res.Count() > 1) {
112        throw new Exception("ERROR: Cannot conatin duplicates!");
113      }
114
115      return res.First().Key;
116    }
117
118    public override IDeepCloneable Clone(Cloner cloner) {
119      return new PermutationSolutionDictionary(this, cloner);
120    }
121
122    public int NumberOfPartialSolutions() {
123      return solutionDictionary.Where(x => x.Key.ElementType == ElementType.Diff).Count();
124    }
125
126    public int NumberOfCompleteSolutions() {
127      return solutionDictionary.Where(x => x.Key.ElementType == ElementType.Complete).Count();
128    }
129
130    public List<PermutationWrapper> GetSolutionsFromGeneration(int generation) {
131      return solutionDictionary.Where(x => x.Value.Where(y => y.Generation == generation).Count() != 0).Select(x => x.Key).ToList<PermutationWrapper>();
132    }
133
134    public override bool ContainsKey(PermutationWrapper key) {
135      return solutionDictionary.ContainsKey(key);
136    }
137  }
138}
Note: See TracBrowser for help on using the repository browser.