Changeset 14487 for branches/MemPRAlgorithm
- Timestamp:
- 12/14/16 10:16:50 (8 years ago)
- Location:
- branches/MemPRAlgorithm
- Files:
-
- 21 edited
- 2 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/MemPRAlgorithm/HeuristicLab 3.3.sln
r14471 r14487 80 80 {3B90F866-70F8-43EF-A541-51819D255B7B} = {3B90F866-70F8-43EF-A541-51819D255B7B} 81 81 {07486E68-1517-4B9D-A58D-A38E99AE71AB} = {07486E68-1517-4B9D-A58D-A38E99AE71AB} 82 {BE698769-975A-429E-828C-72BB2B6182C8} = {BE698769-975A-429E-828C-72BB2B6182C8}83 82 {4AE3FC69-C575-42D2-BC46-0FAD5850EFC5} = {4AE3FC69-C575-42D2-BC46-0FAD5850EFC5} 84 83 {56F9106A-079F-4C61-92F6-86A84C2D84B7} = {56F9106A-079F-4C61-92F6-86A84C2D84B7} … … 423 422 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4", "HeuristicLab.Algorithms.CMAEvolutionStrategy\3.4\HeuristicLab.Algorithms.CMAEvolutionStrategy-3.4.csproj", "{291010E4-2F4E-4D29-A795-753CFF293FDB}" 424 423 EndProject 425 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.3", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj", "{BE698769-975A-429E-828C-72BB2B6182C8}"426 EndProject427 424 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Orienteering-3.3", "HeuristicLab.Problems.Orienteering\3.3\HeuristicLab.Problems.Orienteering-3.3.csproj", "{D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}" 428 425 EndProject … … 458 455 EndProject 459 456 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Instances.DIMACS-3.3", "HeuristicLab.Problems.Instances.DIMACS\3.3\HeuristicLab.Problems.Instances.DIMACS-3.3.csproj", "{9943FF23-8619-459C-B84A-E7FBDCBA04E6}" 457 EndProject 458 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Encodings.LinearLinkageEncoding-3.4", "HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj", "{166507C9-EF26-4370-BB80-699742A29D4F}" 460 459 EndProject 461 460 Global … … 2017 2016 {291010E4-2F4E-4D29-A795-753CFF293FDB}.Release|x86.ActiveCfg = Release|x86 2018 2017 {291010E4-2F4E-4D29-A795-753CFF293FDB}.Release|x86.Build.0 = Release|x86 2019 {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|Any CPU.ActiveCfg = Debug|Any CPU2020 {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|Any CPU.Build.0 = Debug|Any CPU2021 {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x64.ActiveCfg = Debug|x642022 {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x64.Build.0 = Debug|x642023 {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x86.ActiveCfg = Debug|x862024 {BE698769-975A-429E-828C-72BB2B6182C8}.Debug|x86.Build.0 = Debug|x862025 {BE698769-975A-429E-828C-72BB2B6182C8}.Release|Any CPU.ActiveCfg = Release|Any CPU2026 {BE698769-975A-429E-828C-72BB2B6182C8}.Release|Any CPU.Build.0 = Release|Any CPU2027 {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x64.ActiveCfg = Release|x642028 {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x64.Build.0 = Release|x642029 {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x86.ActiveCfg = Release|x862030 {BE698769-975A-429E-828C-72BB2B6182C8}.Release|x86.Build.0 = Release|x862031 2018 {D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}.Debug|Any CPU.ActiveCfg = Debug|Any CPU 2032 2019 {D1EFA4CC-909F-41D5-9C1F-C3AF1957A372}.Debug|Any CPU.Build.0 = Debug|Any CPU … … 2233 2220 {9943FF23-8619-459C-B84A-E7FBDCBA04E6}.Release|x86.ActiveCfg = Release|Any CPU 2234 2221 {9943FF23-8619-459C-B84A-E7FBDCBA04E6}.Release|x86.Build.0 = Release|Any CPU 2222 {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|Any CPU.ActiveCfg = Debug|Any CPU 2223 {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|Any CPU.Build.0 = Debug|Any CPU 2224 {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x64.ActiveCfg = Debug|x64 2225 {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x64.Build.0 = Debug|x64 2226 {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x86.ActiveCfg = Debug|x86 2227 {166507C9-EF26-4370-BB80-699742A29D4F}.Debug|x86.Build.0 = Debug|x86 2228 {166507C9-EF26-4370-BB80-699742A29D4F}.Release|Any CPU.ActiveCfg = Release|Any CPU 2229 {166507C9-EF26-4370-BB80-699742A29D4F}.Release|Any CPU.Build.0 = Release|Any CPU 2230 {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x64.ActiveCfg = Release|x64 2231 {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x64.Build.0 = Release|x64 2232 {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x86.ActiveCfg = Release|x86 2233 {166507C9-EF26-4370-BB80-699742A29D4F}.Release|x86.Build.0 = Release|x86 2235 2234 EndGlobalSection 2236 2235 GlobalSection(SolutionProperties) = preSolution -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/HeuristicLab.Algorithms.MemPR-3.3.csproj
r14466 r14487 162 162 <Private>False</Private> 163 163 </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> 164 <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj"> 165 <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project> 166 <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name> 168 167 </ProjectReference> 169 168 <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj"> -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs
r14484 r14487 250 250 var p1 = p1Scope.Solution; 251 251 var p2 = p2Scope.Solution; 252 var transfered = new bool[p1.Length]; 253 var subspace = new bool[p1.Length]; 254 var lleeChild = new int[p1.Length]; 255 var lleep1 = p1.ToLLEe(); 256 var lleep2 = p2.ToLLEe(); 257 for (var i = p1.Length - 1; i >= 0; i--) { 258 // Step 1 259 subspace[i] = p1[i] != p2[i]; 260 var p1IsEnd = p1[i] == i; 261 var p2IsEnd = p2[i] == i; 262 if (p1IsEnd & p2IsEnd) { 263 transfered[i] = true; 264 } else if (p1IsEnd | p2IsEnd) { 265 transfered[i] = Context.Random.NextDouble() < 0.5; 266 } 267 lleeChild[i] = i; 268 269 // Step 2 270 if (transfered[i]) continue; 271 var end1 = lleep1[i]; 272 var end2 = lleep2[i]; 273 var containsEnd1 = transfered[end1]; 274 var containsEnd2 = transfered[end2]; 275 if (containsEnd1 & containsEnd2) { 276 if (Context.Random.NextDouble() < 0.5) { 277 lleeChild[i] = end1; 278 } else { 279 lleeChild[i] = end2; 280 } 281 } else if (containsEnd1) { 282 lleeChild[i] = end1; 283 } else if (containsEnd2) { 284 lleeChild[i] = end2; 285 } else { 286 if (Context.Random.NextDouble() < 0.5) { 287 lleeChild[i] = lleeChild[p1[i]]; 288 } else { 289 lleeChild[i] = lleeChild[p2[i]]; 290 } 291 } 292 } 293 var child = new Encodings.LinearLinkageEncoding.LinearLinkage(lleeChild.Length); 294 child.FromLLEe(lleeChild); 295 296 return ToScope(child); 252 return ToScope(GroupCrossover.Apply(Context.Random, p1, p2)); 297 253 } 298 254 -
branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/SolutionModel/Univariate/UnivariateSolutionModel.cs
r14466 r14487 63 63 public Encodings.LinearLinkageEncoding.LinearLinkage Sample() { 64 64 var N = Frequencies.Rows; 65 var centroid = new Encodings.LinearLinkageEncoding.LinearLinkage(N);65 var centroid = Encodings.LinearLinkageEncoding.LinearLinkage.SingleElementGroups(N); 66 66 var dict = new Dictionary<int, int>(); 67 67 for (var i = N - 1; i >= 0; i--) { -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding
-
Property
svn:mergeinfo
set to
(toggle deleted branches)
/branches/crossvalidation-2434/HeuristicLab.Encodings.LinearLinkageEncoding merged eligible /stable/HeuristicLab.Encodings.LinearLinkageEncoding merged eligible /trunk/sources/HeuristicLab.Encodings.LinearLinkageEncoding merged eligible /branches/1721-RandomForestPersistence/HeuristicLab.Encodings.LinearLinkageEncoding 10321-10322 /branches/Algorithms.GradientDescent/HeuristicLab.Encodings.LinearLinkageEncoding 5516-5520 /branches/Benchmarking/sources/HeuristicLab.Encodings.LinearLinkageEncoding 6917-7005 /branches/CloningRefactoring/HeuristicLab.Encodings.LinearLinkageEncoding 4656-4721 /branches/CodeEditor/HeuristicLab.Encodings.LinearLinkageEncoding 11700-11806 /branches/DataAnalysis Refactoring/HeuristicLab.Encodings.LinearLinkageEncoding 5471-5808 /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Encodings.LinearLinkageEncoding 5815-6180 /branches/DataAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding 4458-4459,4462,4464 /branches/DataPreprocessing/HeuristicLab.Encodings.LinearLinkageEncoding 10085-11101 /branches/GP.Grammar.Editor/HeuristicLab.Encodings.LinearLinkageEncoding 6284-6795 /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.LinearLinkageEncoding 5060 /branches/HLScript/HeuristicLab.Encodings.LinearLinkageEncoding 10331-10358 /branches/HeuristicLab.DatasetRefactor/sources/HeuristicLab.Encodings.LinearLinkageEncoding 11570-12508 /branches/HeuristicLab.Problems.DataAnalysis.Trading/HeuristicLab.Encodings.LinearLinkageEncoding 6123-9799 /branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Encodings.LinearLinkageEncoding 11130-12721 /branches/HiveStatistics/sources/HeuristicLab.Encodings.LinearLinkageEncoding 12440-12877 /branches/LogResidualEvaluator/HeuristicLab.Encodings.LinearLinkageEncoding 10202-10483 /branches/NET40/sources/HeuristicLab.Encodings.LinearLinkageEncoding 5138-5162 /branches/NSGA-II Changes/HeuristicLab.Encodings.LinearLinkageEncoding 12033-12122 /branches/ParallelEngine/HeuristicLab.Encodings.LinearLinkageEncoding 5175-5192 /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Encodings.LinearLinkageEncoding 7568-7810 /branches/QAPAlgorithms/HeuristicLab.Encodings.LinearLinkageEncoding 6350-6627 /branches/Restructure trunk solution/HeuristicLab.Encodings.LinearLinkageEncoding 6828 /branches/RuntimeOptimizer/HeuristicLab.Encodings.LinearLinkageEncoding 8943-9078 /branches/ScatterSearch (trunk integration)/HeuristicLab.Encodings.LinearLinkageEncoding 7787-8333 /branches/SlaveShutdown/HeuristicLab.Encodings.LinearLinkageEncoding 8944-8956 /branches/SpectralKernelForGaussianProcesses/HeuristicLab.Encodings.LinearLinkageEncoding 10204-10479 /branches/SuccessProgressAnalysis/HeuristicLab.Encodings.LinearLinkageEncoding 5370-5682 /branches/Trunk/HeuristicLab.Encodings.LinearLinkageEncoding 6829-6865 /branches/UnloadJobs/HeuristicLab.Encodings.LinearLinkageEncoding 9168-9215 /branches/VNS/HeuristicLab.Encodings.LinearLinkageEncoding 5594-5752 /branches/histogram/HeuristicLab.Encodings.LinearLinkageEncoding 5959-6341
-
Property
svn:mergeinfo
set to
(toggle deleted branches)
-
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/ExactGroupsLinearLinkageCreator.cs
r14185 r14487 56 56 57 57 public static LinearLinkage Apply(IRandom random, int length, int groups) { 58 var solution = new LinearLinkage(length);59 58 var groupNumbers = Enumerable.Range(0, length).Select(x => x % groups).Shuffle(random); 60 59 var grouping = Enumerable.Range(0, groups).Select(x => new List<int>()).ToList(); … … 63 62 grouping[g].Add(idx++); 64 63 65 solution.SetGroups(grouping); 66 return solution; 64 return LinearLinkage.FromGroups(length, grouping); 67 65 } 68 66 -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/MaxGroupsLinearLinkageCreator.cs
r14185 r14487 55 55 56 56 public static LinearLinkage Apply(IRandom random, int length, int maxGroups) { 57 var solution = new LinearLinkage(length);58 57 var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(maxGroups))) 59 58 .GroupBy(x => x.Item2) 60 59 .Select(x => x.Select(y => y.Item1).ToList()); 61 solution.SetGroups(groups); 62 return solution; 60 return LinearLinkage.FromGroups(length, groups); 63 61 } 64 62 -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Creators/RandomLinearLinkageCreator.cs
r14185 r14487 41 41 42 42 public static LinearLinkage Apply(IRandom random, int length) { 43 var solution = new LinearLinkage(length);44 43 var groups = Enumerable.Range(0, length).Select(x => Tuple.Create(x, random.Next(length))) 45 44 .GroupBy(x => x.Item2) 46 45 .Select(x => x.Select(y => y.Item1).ToList()); 47 solution.SetGroups(groups); 48 return solution; 46 return LinearLinkage.FromGroups(length, groups); 49 47 } 50 48 -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GreedyPartitionCrossover.cs
r14185 r14487 44 44 public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) { 45 45 var len = parents[0].Length; 46 47 var child = new LinearLinkage(len);48 46 var childGroup = new List<HashSet<int>>(); 49 47 var currentParent = random.Next(parents.Length); … … 69 67 } while (remaining); 70 68 71 child.SetGroups(childGroup); 72 return child; 69 return LinearLinkage.FromGroups(len, childGroup); 73 70 } 74 71 -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/GroupCrossover.cs
r14185 r14487 39 39 return new GroupCrossover(this, cloner); 40 40 } 41 41 42 42 public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) { 43 43 var length = p1.Length; 44 var child = new LinearLinkage(length); 45 var endNodes = new HashSet<int>(); 46 for (var i = 0; i < length; i++) { 47 if ((p1[i] == i && p2[i] == i) 48 || ((p1[i] == i || p2[i] == i) && random.NextDouble() < 0.5)) { 49 child[i] = i; 50 endNodes.Add(i); 44 var lleeP1 = p1.ToEndLinks(); 45 var lleeP2 = p2.ToEndLinks(); 46 var lleeChild = new int[length]; 47 var isTransfered = new bool[length]; 48 49 for (var i = p1.Length - 1; i >= 0; i--) { 50 lleeChild[i] = i; 51 52 // Step 1 53 var isEndP1 = p1[i] == i; 54 var isEndP2 = p2[i] == i; 55 if (isEndP1 & isEndP2 || (isEndP1 | isEndP2 && random.NextDouble() < 0.5)) { 56 isTransfered[i] = true; 57 continue; 58 } 59 60 // Step 2 61 var end1 = lleeP1[i]; 62 var end2 = lleeP2[i]; 63 64 if (isTransfered[end1] & isTransfered[end2]) { 65 var end = random.NextDouble() < 0.5 ? end1 : end2; 66 lleeChild[i] = end; 67 } else if (isTransfered[end1]) { 68 lleeChild[i] = end1; 69 } else if (isTransfered[end2]) { 70 lleeChild[i] = end2; 71 } else { 72 var next = random.NextDouble() < 0.5 ? p1[i] : p2[i]; 73 var end = lleeChild[next]; 74 lleeChild[i] = end; 51 75 } 52 76 } 53 for (var i = 0; i < length; i++) { 54 if (endNodes.Contains(i)) continue; 55 var p1End = endNodes.Contains(p1[i]); 56 var p2End = endNodes.Contains(p2[i]); 57 if ((p1End && p2End) || (!p1End && !p2End)) { 58 child[i] = random.NextDouble() < 0.5 ? p1[i] : p2[i]; 59 } else if (p1End) { 60 child[i] = p1[i]; 61 } else { 62 child[i] = p2[i]; 63 } 64 } 65 child.LinearizeTreeStructures(); 66 return child; 77 return LinearLinkage.FromEndLinks(lleeChild); 67 78 } 68 79 -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexFirstCrossover.cs
r14185 r14487 43 43 var len = parents[0].Length; 44 44 var p = random.Next(parents.Length); 45 var child = new LinearLinkage(len);45 var child = LinearLinkage.SingleElementGroups(len); 46 46 var remaining = new SortedSet<int>(Enumerable.Range(0, len)); 47 47 do { -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/LowestIndexMaxCrossover.cs
r14185 r14487 44 44 public static LinearLinkage Apply(IRandom random, ItemArray<LinearLinkage> parents) { 45 45 var len = parents[0].Length; 46 var child = new LinearLinkage(len);46 var child = LinearLinkage.SingleElementGroups(len); 47 47 var remaining = new SortedSet<int>(Enumerable.Range(0, len)); 48 48 do { -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Crossovers/SinglePointCrossover.cs
r14185 r14487 41 41 public static LinearLinkage Apply(IRandom random, LinearLinkage p1, LinearLinkage p2) { 42 42 var length = p1.Length; 43 var child = new LinearLinkage(length);43 var child = LinearLinkage.SingleElementGroups(length); 44 44 var bp = random.Next(length - 1); 45 45 for (var i = 0; i <= bp; i++) child[i] = p1[i]; -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj
r14475 r14487 5 5 <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> 6 6 <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> 7 <ProjectGuid>{ BE698769-975A-429E-828C-72BB2B6182C8}</ProjectGuid>7 <ProjectGuid>{166507C9-EF26-4370-BB80-699742A29D4F}</ProjectGuid> 8 8 <OutputType>Library</OutputType> 9 9 <AppDesignerFolder>Properties</AppDesignerFolder> … … 183 183 <Compile Include="Moves\Swap\Swap2MoveMaker.cs" /> 184 184 <Compile Include="ShakingOperators\LLEShakingOperator.cs" /> 185 <Compile Include="SimilarityCalculators\HammingSimilarityCalculator.cs" /> 185 186 <None Include="HeuristicLab.snk" /> 186 187 <None Include="Plugin.cs.frame" /> -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs
r14185 r14487 37 37 private LinearLinkage(LinearLinkage original, Cloner cloner) : base(original, cloner) { } 38 38 public LinearLinkage() { } 39 public LinearLinkage(int length) : base(length) { } 40 public LinearLinkage(int[] elements) : base(elements) { } 39 40 private LinearLinkage(int length) : base(length) { } 41 private LinearLinkage(int[] elements) : base(elements) { } 42 43 /// <summary> 44 /// Create a new LinearLinkage object where every element is in a seperate group. 45 /// </summary> 46 public static LinearLinkage SingleElementGroups(int length) { 47 var elements = new int[length]; 48 for (var i = 0; i < length; i++) { 49 elements[i] = i; 50 } 51 return new LinearLinkage(elements); 52 } 53 54 /// <summary> 55 /// Create a new LinearLinkage object from an int[] in LLE 56 /// </summary> 57 /// <remarks> 58 /// This operation checks if the argument is a well formed LLE 59 /// and throws an ArgumentException otherwise. 60 /// </remarks> 61 /// <param name="lle">The LLE representation</param> 62 public static LinearLinkage FromForwardLinks(int[] lle) { 63 if (!Validate(lle)) { 64 throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.", "elements"); 65 } 66 return new LinearLinkage(lle); 67 } 68 69 /// <summary> 70 /// Create a new LinearLinkage object by parsing an LLE-e representation 71 /// and modifing the underlying array so that it is in LLE representation. 72 /// </summary> 73 /// <remarks> 74 /// This operation runs in O(n) time, but requires additional memory 75 /// in form of a int[]. 76 /// </remarks> 77 /// <param name="llee">The LLE-e representation</param> 78 /// <returns>LinearLinkage</returns> 79 public static LinearLinkage FromEndLinks(int[] llee) { 80 var result = new LinearLinkage(llee.Length); 81 result.SetEndLinks(llee); 82 return result; 83 } 84 85 /// <summary> 86 /// Create a new LinearLinkage object by translating 87 /// an enumeration of groups into the underlying array representation. 88 /// </summary> 89 /// <remarks> 90 /// Throws an ArgumentException when there is an element assigned to 91 /// multiple groups or elements that are not assigned to any group. 92 /// </remarks> 93 /// <param name="grouping">The grouping of the elements, each element must 94 /// be part of exactly one group.</param> 95 public static LinearLinkage FromGroups(int length, IEnumerable<IEnumerable<int>> grouping) { 96 var result = new LinearLinkage(length); 97 result.SetGroups(grouping); 98 return result; 99 } 41 100 42 101 public override IDeepCloneable Clone(Cloner cloner) { … … 55 114 public IEnumerable<List<int>> GetGroups() { 56 115 var len = array.Length; 57 var remaining = new HashSet<int>(Enumerable.Range(0, len)); 116 var used = new bool[len]; 117 for (var i = 0; i < len; i++) { 118 if (used[i]) continue; 119 var curr = i; 120 var next = array[curr]; 121 var group = new List<int> { curr }; 122 while (next > curr && next < len && !used[next]) { 123 used[curr] = true; 124 curr = next; 125 next = array[next]; 126 group.Add(curr); 127 } 128 if (curr != next) throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding."); 129 used[curr] = true; 130 yield return group; 131 } 132 /* 133 var len = array.Length; 134 var used = new bool[len]; 58 135 // iterate from lowest to highest index 59 136 for (var i = 0; i < len; i++) { 60 if ( !remaining.Contains(i)) continue;137 if (used[i]) continue; 61 138 var group = new List<int> { i }; 62 remaining.Remove(i);139 used[i] = true; 63 140 var next = array[i]; 64 if (next != i) { 65 int prev; 66 do { 67 group.Add(next); 68 if (!remaining.Remove(next)) 69 throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding."); 70 prev = next; 71 next = array[next]; 72 } while (next != prev); 141 if (next < i || next >= len) { 142 throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding."); 143 } 144 while (next != array[next]) { 145 if (next < 0 || next >= len || used[next]) { 146 throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding."); 147 } 148 group.Add(next); 149 used[next] = true; 150 next = array[next]; 73 151 } 74 152 yield return group; 75 } 153 }*/ 76 154 } 77 155 … … 151 229 public void SetGroups(IEnumerable<IEnumerable<int>> grouping) { 152 230 var len = array.Length; 153 var remaining = new HashSet<int>(Enumerable.Range(0, len));231 var used = new bool[len]; 154 232 foreach (var group in grouping) { 155 233 var prev = -1; 156 234 foreach (var g in group.OrderBy(x => x)) { 235 if (g < prev || g >= len) throw new ArgumentException(string.Format("Element {0} is bigger than {1} or smaller than 0.", g, len - 1), "grouping"); 157 236 if (prev >= 0) array[prev] = g; 158 237 prev = g; 159 if ( !remaining.Remove(prev))238 if (used[prev]) { 160 239 throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping"); 161 } 162 if (prev >= 0) array[prev] = prev; 163 } 164 if (remaining.Count > 0) 165 throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", remaining))); 240 } 241 used[prev] = true; 242 } 243 array[prev] = prev; 244 } 245 if (!used.All(x => x)) 246 throw new ArgumentException(string.Format("Elements are not assigned a group: {0}", string.Join(", ", used.Select((x, i) => new { x, i }).Where(x => !x.x).Select(x => x.i)))); 166 247 } 167 248 … … 175 256 /// <returns>True if the encoding is valid.</returns> 176 257 public bool Validate() { 258 return Validate(array); 259 } 260 261 private static bool Validate(int[] array) { 177 262 var len = array.Length; 178 var remaining = new HashSet<int>(Enumerable.Range(0, len));263 var used = new bool[len]; 179 264 for (var i = 0; i < len; i++) { 180 if (!remaining.Contains(i)) continue; 181 remaining.Remove(i); 182 var next = array[i]; 183 if (next == i) continue; 184 int prev; 185 do { 186 if (!remaining.Remove(next)) return false; 187 prev = next; 265 if (used[i]) continue; 266 var curr = i; 267 var next = array[curr]; 268 while (next > curr && next < len && !used[next]) { 269 used[curr] = true; 270 curr = next; 188 271 next = array[next]; 189 } while (next != prev); 190 } 191 return remaining.Count == 0; 272 } 273 if (curr!=next) return false; 274 used[curr] = true; 275 } 276 return true; 192 277 } 193 278 … … 216 301 public void LinearizeTreeStructures() { 217 302 // Step 1: Convert the array into LLE-e 218 To LLEeInplace(array);303 ToEndLinksInplace(array); 219 304 // Step 2: For all groups linearize the links 220 FromLLEe(array);305 SetEndLinks(array); 221 306 } 222 307 … … 233 318 /// </remarks> 234 319 /// <returns>An integer array in LLE-e representation</returns> 235 public int[] To LLEe() {320 public int[] ToEndLinks() { 236 321 var result = (int[])array.Clone(); 237 To LLEeInplace(result);322 ToEndLinksInplace(result); 238 323 return result; 239 324 } 240 325 241 private void ToLLEeInplace(int[] a) {242 var length = a .Length;326 private static void ToEndLinksInplace(int[] array) { 327 var length = array.Length; 243 328 for (var i = length - 1; i >= 0; i--) { 244 if (array[i] == i) a[i] = i; 245 else a[i] = a[a[i]]; 329 var next = array[i]; 330 if (next > i) { 331 array[i] = array[next]; 332 } else if (next < i) { 333 throw new ArgumentException("Array is malformed and does not represent a valid LLE encoding.", "array"); 334 } 246 335 } 247 336 } … … 253 342 /// <remarks> 254 343 /// This operation runs in O(n) time, but requires additional memory 255 /// in form of a dictionary.344 /// in form of a int[]. 256 345 /// </remarks> 257 346 /// <param name="llee">The LLE-e representation</param> 258 public void FromLLEe(int[] llee) {347 public void SetEndLinks(int[] llee) { 259 348 var length = array.Length; 260 var groups = new Dictionary<int, int>(); 349 if (length != llee.Length) { 350 throw new ArgumentException(string.Format("Expected length {0} but length was {1}", length, llee.Length), "llee"); 351 } 352 // If we are ok with mutating llee we can avoid this clone 353 var lookup = (int[])llee.Clone(); 261 354 for (var i = length - 1; i >= 0; i--) { 262 if (llee[i] == i) { 263 array[i] = i; 264 groups[i] = i; 355 var end = llee[i]; 356 if (end == i) { 357 array[i] = end; 358 } else if (end > i && end < length) { 359 array[i] = lookup[end]; 360 lookup[end] = i; 265 361 } else { 266 var g = llee[i]; 267 array[i] = groups[g]; 268 groups[g] = i; 362 throw new ArgumentException("Array is malformed and does not represent a valid LLE end encoding.", "llee"); 269 363 } 270 364 } -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Moves/StaticAPI/MoveGenerator.cs
r14477 r14487 45 45 yield return new MergeMove(i, l.Key); 46 46 } 47 } else { 48 // Fourth: extract i into group of its own (exclude first, because of Second) 49 yield return new ExtractMove(i, pred, next); 47 50 } 48 51 } 49 if (!isFirst) 50 // Fourth: extract i into group of its own (exclude first, because of Second) 51 yield return new ExtractMove(i, pred, next); 52 52 53 53 54 } -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Plugin.cs.frame
r14195 r14487 23 23 24 24 namespace HeuristicLab.Encodings.LinearLinkageEncoding { 25 [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3. 3.14.$WCREV$")]26 [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3. 3.dll", PluginFileType.Assembly)]25 [Plugin("HeuristicLab.Encodings.LinearLinkageEncoding", "Provides data structures and operators for the linear linkage encoding (LLE).", "3.4.14.$WCREV$")] 26 [PluginFile("HeuristicLab.Encodings.LinearLinkageEncoding-3.4.dll", PluginFileType.Assembly)] 27 27 [PluginDependency("HeuristicLab.Collections", "3.3")] 28 28 [PluginDependency("HeuristicLab.Common", "3.3")] -
branches/MemPRAlgorithm/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/Properties/AssemblyInfo.cs.frame
r14195 r14487 53 53 // by using the '*' as shown below: 54 54 // [assembly: AssemblyVersion("1.0.*")] 55 [assembly: AssemblyVersion("3. 3.0.0")]56 [assembly: AssemblyFileVersion("3. 3.14.$WCREV$")]55 [assembly: AssemblyVersion("3.4.0.0")] 56 [assembly: AssemblyFileVersion("3.4.14.$WCREV$")] -
branches/MemPRAlgorithm/HeuristicLab.PluginInfrastructure/3.3/Manager/PluginValidator.cs
r14185 r14487 260 260 } 261 261 // ignore exceptions. Just don't yield a plugin description when an exception is thrown 262 catch (FileNotFoundException ) {262 catch (FileNotFoundException e) { 263 263 } 264 264 catch (FileLoadException) { … … 468 468 // if the dependency is already disabled we can ignore the cycle detection because we will disable the plugin anyway 469 469 // if following one of the dependencies recursively leads to a cycle then we also return 470 if (dep == plugin || dep.PluginState == PluginState.Disabled || HasCycleInDependencies(plugin, dep.Dependencies)) return true; 470 if (dep == plugin || dep.PluginState == PluginState.Disabled || HasCycleInDependencies(plugin, dep.Dependencies)) 471 return true; 471 472 } 472 473 // no cycle found and none of the direct and indirect dependencies is disabled -
branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/GraphColoringProblem.cs
r14471 r14487 114 114 var fitFun = FitnessFunctionParameter.Value.Value; 115 115 var adjList = adjacencyListParameter.Value; 116 var lle = individual.LinearLinkage(Encoding.Name).To LLEe(); // LLE-e encoding uses the highest indexed member as group number116 var lle = individual.LinearLinkage(Encoding.Name).ToEndLinks(); // LLE-e encoding uses the highest indexed member as group number 117 117 118 118 switch (fitFun) { … … 158 158 159 159 var adjList = AdjacencyListParameter.Value; 160 var lle = best.To LLEe();160 var lle = best.ToEndLinks(); 161 161 var conflicts = 0; 162 162 var colors = lle.Distinct().Count(); -
branches/MemPRAlgorithm/HeuristicLab.Problems.GraphColoring/3.3/HeuristicLab.Problems.GraphColoring-3.3.csproj
r14471 r14487 88 88 <Private>False</Private> 89 89 </ProjectReference> 90 <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj"> 91 <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project> 92 <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name> 93 <Private>False</Private> 90 <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj"> 91 <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project> 92 <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name> 94 93 </ProjectReference> 95 94 <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj"> -
branches/MemPRAlgorithm/HeuristicLab.Problems.Programmable/3.3/HeuristicLab.Problems.Programmable-3.3.csproj
r12724 r14487 149 149 <Name>HeuristicLab.Encodings.IntegerVectorEncoding-3.3</Name> 150 150 </ProjectReference> 151 <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.3.csproj"> 152 <Project>{be698769-975a-429e-828c-72bb2b6182c8}</Project> 153 <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.3</Name> 154 <Private>False</Private> 151 <ProjectReference Include="..\..\HeuristicLab.Encodings.LinearLinkageEncoding\3.3\HeuristicLab.Encodings.LinearLinkageEncoding-3.4.csproj"> 152 <Project>{166507c9-ef26-4370-bb80-699742a29d4f}</Project> 153 <Name>HeuristicLab.Encodings.LinearLinkageEncoding-3.4</Name> 155 154 </ProjectReference> 156 155 <ProjectReference Include="..\..\HeuristicLab.Encodings.PermutationEncoding\3.3\HeuristicLab.Encodings.PermutationEncoding-3.3.csproj">
Note: See TracChangeset
for help on using the changeset viewer.