#region License Information
/* HeuristicLab
* Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using HeuristicLab.Analysis;
using HeuristicLab.Analysis.SelfOrganizingMaps;
using HeuristicLab.Collections;
using HeuristicLab.Common;
using HeuristicLab.Common.Resources;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.MainForm;
using HeuristicLab.Optimization;
using HeuristicLab.Persistence.Default.Xml;
using HeuristicLab.Random;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using RunCreationClient = HeuristicLab.Clients.OKB.RunCreation.RunCreationClient;
using SingleObjectiveOKBProblem = HeuristicLab.Clients.OKB.RunCreation.SingleObjectiveOKBProblem;
using SingleObjectiveOKBSolution = HeuristicLab.Clients.OKB.RunCreation.SingleObjectiveOKBSolution;
namespace HeuristicLab.OptimizationExpertSystem.Common {
[Item("Knowledge Center", "Currently in experimental phase, an expert system that makes algorithm suggestions based on fitness landscape analysis features and an optimization knowledge base.")]
[Creatable(CreatableAttribute.Categories.TestingAndAnalysis, Priority = 119)]
public sealed class KnowledgeCenter : IContent {
private bool SuppressEvents { get; set; }
public string Filename { get; set; }
public static new Image StaticItemImage {
get { return VSImageLibrary.Library; }
}
private readonly IntValue maximumEvaluations;
public IntValue MaximumEvaluations {
get { return maximumEvaluations; }
}
private readonly DoubleValue minimumTarget;
public DoubleValue MinimumTarget {
get { return minimumTarget; }
}
private readonly RunCollection instanceRuns;
public RunCollection InstanceRuns {
get { return instanceRuns; }
}
private readonly RunCollection seededRuns;
public RunCollection SeededRuns {
get { return seededRuns; }
}
private readonly RunCollection knowledgeBase;
public RunCollection KnowledgeBase {
get { return knowledgeBase; }
}
private readonly SingleObjectiveOKBProblem problem;
public SingleObjectiveOKBProblem Problem {
get { return problem; }
}
private readonly ItemList suggestedInstances;
private readonly ReadOnlyItemList readOnlySuggestedInstances;
public ReadOnlyItemList SuggestedInstances {
get { return readOnlySuggestedInstances; }
}
private readonly RunCollection problemInstances;
public RunCollection ProblemInstances {
get { return problemInstances; }
}
private readonly CheckedItemList problemCharacteristics;
private readonly ReadOnlyCheckedItemList readonlyProblemCharacteristics;
public ReadOnlyCheckedItemList ProblemCharacteristics {
get { return readonlyProblemCharacteristics; }
}
private readonly EnumValue problemInstanceProximity;
public EnumValue ProblemInstanceProximity {
get { return problemInstanceProximity; }
}
private readonly DoubleValue problemInstanceNeighborhoodFactor;
public DoubleValue ProblemInstanceNeighborhoodFactor {
get { return problemInstanceNeighborhoodFactor; }
}
private readonly CheckedItemList solutionSeedingPool;
public CheckedItemList SolutionSeedingPool {
get { return solutionSeedingPool; }
}
private readonly EnumValue seedingStrategy;
public EnumValue SeedingStrategy {
get { return seedingStrategy; }
}
private BidirectionalLookup algorithmId2RunMapping;
private BidirectionalDictionary algorithmId2AlgorithmInstanceMapping;
private BidirectionalDictionary problemId2ProblemInstanceMapping;
private bool Maximization {
get { return Problem != null && Problem.ProblemId >= 0 && ((IValueParameter)Problem.MaximizationParameter).Value.Value; }
}
public KnowledgeCenter() {
maximumEvaluations = new IntValue(10000);
minimumTarget = new DoubleValue(0.05);
instanceRuns = new RunCollection();
seededRuns = new RunCollection();
knowledgeBase = new RunCollection();
suggestedInstances = new ItemList();
readOnlySuggestedInstances = suggestedInstances.AsReadOnly();
problemInstances = new RunCollection();
problemCharacteristics = new CheckedItemList();
problemInstanceProximity = new EnumValue(ProblemInstanceProximityType.FeatureSpace);
problemInstanceNeighborhoodFactor = new DoubleValue(5);
readonlyProblemCharacteristics = problemCharacteristics.AsReadOnly();
problem = new SingleObjectiveOKBProblem();
algorithmId2RunMapping = new BidirectionalLookup();
algorithmId2AlgorithmInstanceMapping = new BidirectionalDictionary();
problemId2ProblemInstanceMapping = new BidirectionalDictionary();
solutionSeedingPool = new CheckedItemList();
seedingStrategy = new EnumValue(SeedingStrategyTypes.NoSeeding);
RegisterEventHandlers();
}
private void ProblemOnProblemChanged(object sender, EventArgs eventArgs) {
// TODO: Potentially, knowledge base has to be re-downloaded
}
private void RegisterEventHandlers() {
maximumEvaluations.ValueChanged += MaximumEvaluationsOnValueChanged;
minimumTarget.ValueChanged += MinimumTargetOnValueChanged;
problem.ProblemChanged += ProblemOnProblemChanged;
problem.Solutions.ItemsAdded += ProblemSolutionsChanged;
problem.Solutions.ItemsReplaced += ProblemSolutionsChanged;
problem.Solutions.ItemsRemoved += ProblemSolutionsChanged;
problem.Solutions.CollectionReset += ProblemSolutionsChanged;
instanceRuns.CollectionReset += InformationChanged;
instanceRuns.ItemsAdded += InformationChanged;
instanceRuns.ItemsRemoved += InformationChanged;
instanceRuns.Reset += InformationChanged;
instanceRuns.UpdateOfRunsInProgressChanged += InformationChanged;
knowledgeBase.CollectionReset += InformationChanged;
knowledgeBase.ItemsAdded += InformationChanged;
knowledgeBase.ItemsRemoved += InformationChanged;
problemCharacteristics.ItemsAdded += CharacteristicChanged;
problemCharacteristics.ItemsReplaced += CharacteristicChanged;
problemCharacteristics.ItemsRemoved += CharacteristicChanged;
problemCharacteristics.CollectionReset += CharacteristicChanged;
problemCharacteristics.CheckedItemsChanged += CharacteristicChanged;
problemInstanceProximity.ValueChanged += ProblemInstanceProximityChanged;
problemInstanceNeighborhoodFactor.ValueChanged += ProblemInstanceProximityChanged;
}
private void MaximumEvaluationsOnValueChanged(object sender, EventArgs eventArgs) {
UpdateSuggestions();
}
private void MinimumTargetOnValueChanged(object sender, EventArgs e) {
UpdateSuggestions();
}
private void ProblemSolutionsChanged(object sender, EventArgs e) {
foreach (var sol in Problem.Solutions.Select(x => x.Solution).OfType()) {
if (!SolutionSeedingPool.Contains(sol))
SolutionSeedingPool.Add(sol, false);
}
}
private void InformationChanged(object sender, EventArgs e) {
var runCollection = sender as RunCollection;
if (runCollection != null && runCollection.UpdateOfRunsInProgress) return;
UpdateSuggestions();
}
private void CharacteristicChanged(object sender, EventArgs e) {
if (SuppressEvents) return;
UpdateInstanceProjection();
}
private void ProblemInstanceProximityChanged(object sender, EventArgs e) {
UpdateSuggestions();
}
public bool IsCurrentInstance(IRun run) {
if (!problemId2ProblemInstanceMapping.ContainsSecond(run)) return false;
return problemId2ProblemInstanceMapping.GetBySecond(run) == Problem.ProblemId;
}
public void UpdateInstanceProjection() {
if (ProblemCharacteristics.Count == 0) return;
var instances = GetProblemCharacteristics();
var key2Idx = new BidirectionalDictionary();
foreach (var kvp in instances.Select((k, i) => new { Index = i, Key = k.Key }))
key2Idx.Add(kvp.Key, kvp.Index);
#region MDS
Func euclid = (a, b) => Math.Sqrt(a.Zip(b, (x, y) => (x - y)).Sum(x => x * x));
var num = instances.Count;
var matrix = new DoubleMatrix(num, num);
for (var i = 0; i < num - 1; i++) {
for (var j = i + 1; j < num; j++) {
matrix[i, j] = matrix[j, i] = euclid(instances[key2Idx.GetBySecond(i)], instances[key2Idx.GetBySecond(j)]);
}
}
var coords = MultidimensionalScaling.KruskalShepard(matrix);
#endregion
#region PCA
var ds = new double[instances.Count, ProblemCharacteristics.CheckedItems.Count()];
foreach (var instance in instances) {
var arr = instance.Value;
for (var feature = 0; feature < arr.Length; feature++)
ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
}
int info;
double[] s2;
double[,] v;
alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
#endregion
#region SOM
var features = new DoubleMatrix(ProblemCharacteristics.CheckedItems.Count(), instances.Count);
foreach (var instance in instances) {
var arr = instance.Value;
for (var feature = 0; feature < arr.Length; feature++)
features[feature, key2Idx.GetByFirst(instance.Key)] = arr[feature];
}
var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 20, learningRadius: 20, iterations: 200, jittering: true);
#endregion
ProblemInstances.UpdateOfRunsInProgress = true;
try {
foreach (var instance in ProblemInstances) {
double x = 0, y = 0;
for (var feature = 0; feature < ds.GetLength(1); feature++) {
x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
}
IItem item;
if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
((DoubleValue)item).Value = x;
} else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
((DoubleValue)item).Value = y;
} else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 0];
} else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance), 0]));
if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 1];
} else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance), 1]));
if (instance.Results.TryGetValue("Projection.SOM.X", out item)) {
((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 0];
} else instance.Results.Add("Projection.SOM.X", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 0]));
if (instance.Results.TryGetValue("Projection.SOM.Y", out item)) {
((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 1];
} else instance.Results.Add("Projection.SOM.Y", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 1]));
}
} finally { ProblemInstances.UpdateOfRunsInProgress = false; }
}
private Dictionary GetProblemCharacteristics() {
var instances = new Dictionary();
var values = new List[ProblemCharacteristics.CheckedItems.Count()];
foreach (var run in ProblemInstances) {
var f = 0;
instances[run] = new double[ProblemCharacteristics.CheckedItems.Count()];
foreach (var c in ProblemCharacteristics.CheckedItems.Select(x => x.Value.Value)) {
if (values[f] == null) values[f] = new List(ProblemInstances.Count);
IItem item;
if (run.Results.TryGetValue(c, out item)) {
var val = (double)((dynamic)item).Value;
if (!double.IsNaN(val)) values[f].Add(val);
instances[run][f] = val;
} else instances[run][f] = double.NaN;
f++;
}
}
var median = values.Select(x => x.Count == 0 ? 0.0 : x.Median()).ToList();
var allValues = instances.Values.Select(x => x.Select((f, i) => new {Idx = i, Val = double.IsNaN(f) ? median[i] : f}).ToList())
.SelectMany(x => x)
.GroupBy(x => x.Idx, x => x.Val)
.OrderBy(x => x.Key).ToList();
var avg = allValues.Select(x => x.Average()).ToList();
var stdev = allValues.Select(x => x.StandardDeviation()).ToList();
// normalize characteristic values by transforming them to their z-score
foreach (var key in instances.Keys.ToList()) {
var arr = instances[key];
for (var i = 0; i < arr.Length; i++) {
if (double.IsNaN(arr[i])) arr[i] = median[i];
if (stdev[i] > 0) arr[i] = (arr[i] - avg[i]) / stdev[i];
}
}
return instances;
}
private static readonly HashSet InterestingValueNames = new HashSet() {
"QualityPerEvaluations", "Problem Name", "Problem Type", "Algorithm Name", "Algorithm Type", "Maximization", "BestKnownQuality"
};
public Task StartAlgorithmAsync(int index) {
return StartAlgorithmAsync(index, CancellationToken.None);
}
public Task StartAlgorithmAsync(int index, CancellationToken cancellation) {
var selectedInstance = suggestedInstances[index];
var algorithmClone = (IAlgorithm)selectedInstance.Clone();
var problemClone = Problem.CloneProblem() as ISingleObjectiveHeuristicOptimizationProblem;
if (problemClone == null) throw new InvalidOperationException("Problem is not of type " + typeof(ISingleObjectiveHeuristicOptimizationProblem).FullName);
// TODO: It is assumed the problem instance by default is configured using no preexisting solution creator
var seedingStrategyLocal = SeedingStrategy.Value;
if (seedingStrategyLocal != SeedingStrategyTypes.NoSeeding) {
if (!SolutionSeedingPool.CheckedItems.Any()) throw new InvalidOperationException("There are no solutions selected for seeding.");
// TODO: It would be necessary to specify the solution creator somewhere (property and GUI)
var seedingCreator = problemClone.Operators.OfType().FirstOrDefault();
if (seedingCreator == null) throw new InvalidOperationException("The problem does not contain a solution creator that allows seeding.");
seedingCreator.PreexistingSolutionsParameter.Value.Replace(SolutionSeedingPool.CheckedItems.Select(x => x.Value));
seedingCreator.SampleFromPreexistingParameter.Value.Value = seedingStrategyLocal == SeedingStrategyTypes.SeedBySampling;
// TODO: WHY!? WHY??!?
((dynamic)problemClone.SolutionCreatorParameter).Value = (dynamic)seedingCreator;
}
algorithmClone.Problem = problemClone;
algorithmClone.Prepare(true);
IParameter stopParam;
var monitorStop = true;
if (algorithmClone.Parameters.TryGetValue("MaximumEvaluations", out stopParam)) {
var maxEvalParam = stopParam as IValueParameter;
if (maxEvalParam != null) {
maxEvalParam.Value.Value = MaximumEvaluations.Value;
monitorStop = false;
}
}
// TODO: The following can be simplified when we have async implementation patterns for our algorithms:
// TODO: The closures can be removed and replaced with private member methods
var waitHandle = new AutoResetEvent(false);
#region EventHandler closures
EventHandler exeStateChanged = (sender, e) => {
if (algorithmClone.ExecutionState == ExecutionState.Stopped) {
lock (Problem.Solutions) {
foreach (var solution in algorithmClone.Results.Where(x => x.Name.ToLower().Contains("solution")).Select(x => x.Value).OfType()) {
Problem.Solutions.Add(new SingleObjectiveOKBSolution(Problem.ProblemId) {
Quality = solution.Variables.ContainsKey(Problem.Problem.Evaluator.QualityParameter.ActualName) ? ((DoubleValue)solution.Variables[Problem.Problem.Evaluator.QualityParameter.ActualName].Value).Value : double.NaN,
Solution = (IItem)solution.Clone()
});
}
}
if (seedingStrategyLocal == SeedingStrategyTypes.NoSeeding) {
lock (InstanceRuns) {
InstanceRuns.Add(algorithmClone.Runs.Last());
}
} else {
lock (SeededRuns) {
SeededRuns.Add(algorithmClone.Runs.Last());
}
}
waitHandle.Set();
}
};
EventHandler> exceptionOccurred = (sender, e) => {
waitHandle.Set();
};
EventHandler timeChanged = (sender, e) => {
IResult evalSolResult;
if (!algorithmClone.Results.TryGetValue("EvaluatedSolutions", out evalSolResult) || !(evalSolResult.Value is Data.IntValue)) return;
var evalSols = ((Data.IntValue)evalSolResult.Value).Value;
if (evalSols >= MaximumEvaluations.Value && algorithmClone.ExecutionState == ExecutionState.Started)
algorithmClone.Stop();
};
#endregion
algorithmClone.ExecutionStateChanged += exeStateChanged;
algorithmClone.ExceptionOccurred += exceptionOccurred;
if (monitorStop) algorithmClone.ExecutionTimeChanged += timeChanged;
return Task.Factory.StartNew(() => {
algorithmClone.Start();
OnAlgorithmInstanceStarted(algorithmClone);
var cancelRequested = false;
while (!waitHandle.WaitOne(200)) {
if (cancellation.IsCancellationRequested) {
cancelRequested = true;
break;
}
}
if (cancelRequested) {
try { algorithmClone.Stop(); } catch { } // ignore race condition if it is stopped in the meantime
waitHandle.WaitOne();
}
waitHandle.Dispose();
return algorithmClone.Results;
}, TaskCreationOptions.LongRunning);
}
public ResultCollection StartAlgorithm(int index, CancellationToken cancellation) {
var task = StartAlgorithmAsync(index, cancellation);
task.Wait(cancellation);
return task.Result;
}
public Task UpdateKnowledgeBaseAsync(IProgress progress = null) {
if (progress == null) progress = new Progress(string.Empty);
progress.Start("Updating Knowledge Base from OKB");
OnDownloadStarted(progress);
return Task.Factory.StartNew(() => { DoUpdateKnowledgeBase(progress); }, TaskCreationOptions.LongRunning);
}
public void UpdateKnowledgeBase(IProgress progress = null) {
UpdateKnowledgeBaseAsync(progress).Wait();
}
private void DoUpdateKnowledgeBase(IProgress progress) {
var queryClient = Clients.OKB.Query.QueryClient.Instance;
var adminClient = Clients.OKB.Administration.AdministrationClient.Instance;
try {
progress.Status = "Connecting to OKB...";
progress.ProgressValue = 0;
// FIXME: How to tell if refresh is necessary?
var refreshTasks = new[] {
Task.Factory.StartNew(() => queryClient.Refresh()),
Task.Factory.StartNew(() => adminClient.Refresh())
};
Task.WaitAll(refreshTasks);
var probInstance = adminClient.Problems.SingleOrDefault(x => x.Id == Problem.ProblemId);
if (probInstance == null) throw new InvalidOperationException("The chosen problem instance cannot be found in the OKB.");
var probClassId = probInstance.ProblemClassId;
var problemClassFilter = (Clients.OKB.Query.StringComparisonAvailableValuesFilter)queryClient.Filters.Single(x => x.Label == "Problem Class Name");
problemClassFilter.Value = adminClient.ProblemClasses.Single(x => x.Id == probClassId).Name;
problemId2ProblemInstanceMapping.Clear();
progress.Status = "Downloading problem instances...";
progress.ProgressValue = 0;
int[] p = { 0 };
ProblemInstances.UpdateOfRunsInProgress = true;
ProblemInstances.Clear();
var characteristics = new HashSet();
var totalProblems = adminClient.Problems.Count(x => x.ProblemClassId == probClassId);
Parallel.ForEach(adminClient.Problems.Where(x => x.ProblemClassId == probClassId), new ParallelOptions { MaxDegreeOfParallelism = 3 }, (pInst) => {
var charas = new List();
IRun probRun = null;
var data = Clients.OKB.Administration.AdministrationClient.GetProblemData(pInst.Id);
if (data != null) {
using (var stream = new MemoryStream(data)) {
try {
var prob = (IProblem)XmlParser.Deserialize(stream);
probRun = new Run() { Name = prob.Name };
prob.CollectParameterValues(probRun.Parameters);
probRun.Parameters["Problem Name"] = new StringValue(prob.Name);
probRun.Parameters["Problem Type"] = new StringValue(prob.GetType().Name);
foreach (var v in RunCreationClient.Instance.GetCharacteristicValues(pInst.Id)) {
probRun.Results.Add("Characteristic." + v.Name, RunCreationClient.Instance.ConvertToItem(v));
charas.Add("Characteristic." + v.Name);
}
} catch { }
stream.Close();
}
if (probRun != null) {
lock (characteristics) {
problemId2ProblemInstanceMapping.Add(pInst.Id, probRun);
ProblemInstances.Add(probRun);
progress.Status = string.Format("Downloaded problem {0} (okb-id: {1})....", pInst.Name, pInst.Id);
p[0]++;
progress.ProgressValue = p[0] / (double)totalProblems;
foreach (var c in charas) characteristics.Add(c);
}
}
}
});
algorithmId2AlgorithmInstanceMapping.Clear();
progress.Status = "Downloading algorithm instances...";
progress.ProgressValue = 0;
p[0] = 0;
Parallel.ForEach(adminClient.Algorithms, new ParallelOptions { MaxDegreeOfParallelism = 3 }, (algInst) => {
IAlgorithm alg = null;
var data = Clients.OKB.Administration.AdministrationClient.GetAlgorithmData(algInst.Id);
if (data != null) {
using (var stream = new MemoryStream(data)) {
try {
alg = (IAlgorithm)XmlParser.Deserialize(stream);
} catch { }
stream.Close();
}
if (alg != null) {
lock (algorithmId2AlgorithmInstanceMapping) {
algorithmId2AlgorithmInstanceMapping.Add(algInst.Id, alg);
progress.Status = string.Format("Downloaded algorithm {0} (okb-id: {1})...", algInst.Name, algInst.Id);
p[0]++;
progress.ProgressValue = p[0] / (double)adminClient.Algorithms.Count;
}
}
}
});
var interestingValues = queryClient.ValueNames.Where(x => InterestingValueNames.Contains(x.Name)).ToList();
progress.Status = "Downloading runs...";
progress.ProgressValue = 0;
p[0] = 0;
var count = queryClient.GetNumberOfRuns(problemClassFilter);
if (count == 0) return;
var runList = new List();
var runIds = queryClient.GetRunIds(problemClassFilter).ToList();
var batches = runIds.Select((v, i) => new { Idx = i, Val = v }).GroupBy(x => x.Idx / 500, x => x.Val);
Parallel.ForEach(batches.Select(x => x.ToList()), new ParallelOptions { MaxDegreeOfParallelism = 3 }, (batch) => {
var okbRuns = queryClient.GetRunsWithValues(batch, true, interestingValues);
var hlRuns = okbRuns.AsParallel().Select(x => new { AlgorithmId = x.Algorithm.Id, Run = queryClient.ConvertToOptimizationRun(x) }).ToList();
lock (runList) {
foreach (var r in hlRuns) {
algorithmId2RunMapping.Add(r.AlgorithmId, r.Run);
runList.Add(r.Run);
}
progress.Status = string.Format("Downloaded runs {0} to {1} of {2}...", p[0], p[0] + batch.Count, count);
p[0] += batch.Count;
progress.ProgressValue = p[0] / (double)count;
}
});
progress.Status = "Finishing...";
var algInstRunDict = runList.Where(x => x.Parameters.ContainsKey("Problem Name") && x.Parameters["Problem Name"] is StringValue)
.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)
.ToDictionary(x => x.Key, x => x.GroupBy(y => ((StringValue)y.Parameters["Algorithm Name"]).Value)
.ToDictionary(y => y.Key, y => y.ToList()));
foreach (var instance in ProblemInstances) {
IItem probNameParam;
if (!instance.Parameters.TryGetValue("Problem Name", out probNameParam)) continue;
var probInstanceName = ((StringValue)probNameParam).Value;
var maximization = ((BoolValue)instance.Parameters["Maximization"]).Value;
IItem bkParam;
if (!instance.Parameters.TryGetValue("BestKnownQuality", out bkParam) || !(bkParam is DoubleValue)) {
Dictionary> algRuns;
if (!algInstRunDict.TryGetValue(probInstanceName, out algRuns)) continue;
var list = algRuns.SelectMany(x => x.Value)
.Where(x => x.Results.ContainsKey("QualityPerEvaluations"))
.Select(x => ((IndexedDataTable)x.Results["QualityPerEvaluations"]).Rows.First().Values.Last().Item2);
bkParam = new DoubleValue(maximization ? list.Max() : list.Min());
instance.Parameters["BestKnownQuality"] = bkParam;
} else bkParam = instance.Parameters["BestKnownQuality"];
var bkQuality = ((DoubleValue)bkParam).Value;
if (!algInstRunDict.ContainsKey(probInstanceName)) continue;
// TODO: Things needs to be configurable here (table name, targets)
foreach (var target in new[] { 1, 1.01, 1.05, 1.1, 1.2, 1.5 }) {
var indexMap = new BidirectionalDictionary();
var dict = new Dictionary();
var idx = 0;
foreach (var kvp in algInstRunDict[probInstanceName]) {
var result = ExpectedRuntimeHelper.CalculateErt(kvp.Value, "QualityPerEvaluations", bkQuality * target, maximization);
indexMap.Add(kvp.Key, idx);
dict[kvp.Key] = !double.IsNaN(result.ExpectedRuntime) ? result.ExpectedRuntime : int.MaxValue;
idx++;
}
var points = dict.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value > 0 ? Math.Log10(x.Value) : 0).ToArray();
int[] clusters;
Ckmeans1dClusters(points, 5, out clusters);
var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = dict[indexMap.GetBySecond(i)] })
.GroupBy(x => x.Cluster, x => x.Perf)
.Select(x => new { Cluster = x.Key, AvgPerf = x.Average() })
.OrderBy(x => x.AvgPerf)
.Select((c, i) => new { Cluster = c.Cluster, Rank = i })
.ToDictionary(x => x.Cluster, x => x.Rank);
for (var i = 0; i < clusters.Length; i++) {
var resultName = "Rank." + indexMap.GetBySecond(i) + "@" + ((target - 1) * 100) + "%";
instance.Results[resultName] = new IntValue(dict[indexMap.GetBySecond(i)] < int.MaxValue ? ranks[clusters[i]] : 6);
}
}
}
try {
SuppressEvents = true;
problemCharacteristics.Replace(characteristics.Select(x => new StringValue(x)));
foreach (var pc in problemCharacteristics.Where(x => !x.Value.StartsWith("Characteristic.")))
problemCharacteristics.SetItemCheckedState(pc, false);
} finally { SuppressEvents = false; }
try {
KnowledgeBase.UpdateOfRunsInProgress = true;
KnowledgeBase.Clear();
KnowledgeBase.AddRange(runList);
} finally { KnowledgeBase.UpdateOfRunsInProgress = false; }
} finally { progress.Finish(); ProblemInstances.UpdateOfRunsInProgress = false; }
UpdateInstanceProjection();
UpdateSuggestions();
}
private void UpdateSuggestions() {
if (Problem == null) return;
var piDistances = GetProblemDistances();
var maxDist = piDistances.Max(x => x.Value);
var instances = new SortedList();
foreach (var relevantRuns in knowledgeBase.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
var algorithm = algorithmId2AlgorithmInstanceMapping.GetByFirst(relevantRuns.Key);
Func distFunc = (d) => Math.Exp(ProblemInstanceNeighborhoodFactor.Value * (-d / maxDist));
var pis = relevantRuns.Select(x => ((StringValue)x.Parameters["Problem Name"]).Value).Distinct()
.Select(x => Tuple.Create(x, ProblemInstances.SingleOrDefault(y => ((StringValue)y.Parameters["Problem Name"]).Value == x)))
.Where(x => x.Item2 != null)
.Select(x => Tuple.Create(x.Item1, distFunc(piDistances[x.Item2]), ((DoubleValue)x.Item2.Parameters["BestKnownQuality"]).Value))
.ToDictionary(x => x.Item1, x => Tuple.Create(x.Item2, x.Item3));
var sumPis = pis.Sum(x => x.Value.Item1);
var avgERT = 0.0;
foreach (var problemRuns in relevantRuns.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)) {
Tuple info;
if (!pis.TryGetValue(problemRuns.Key, out info)) continue;
var convGraph = new List>>();
foreach (var run in problemRuns) {
var current = new List>();
var performanceGraph = ((IndexedDataTable)run.Results["QualityPerEvaluations"]);
current.AddRange(performanceGraph.Rows.First().Values.TakeWhile(v => v.Item1 < MaximumEvaluations.Value));
if (current.Count > 0) {
current.Add(Tuple.Create((double)MaximumEvaluations.Value, current.Last().Item2));
convGraph.Add(current);
}
}
var ert = ExpectedRuntimeHelper.CalculateErt(convGraph, (Maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value)) * info.Item2, Maximization).ExpectedRuntime;
if (double.IsNaN(ert)) {
ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", (Maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value)) * info.Item2, Maximization).ExpectedRuntime;
if (double.IsNaN(ert)) ert = int.MaxValue;
}
avgERT += info.Item1 * ert;
}
avgERT /= sumPis;
if (instances.ContainsKey(avgERT)) {
avgERT += new System.Random().NextDouble();
}
instances.Add(avgERT, algorithm);
}
var instanceLadder = instances.Select(x => (IAlgorithm)x.Value.Clone()).ToList();
suggestedInstances.Replace(instanceLadder);
}
private Dictionary GetProblemDistances() {
var result = new Dictionary();
var currentInstance = problemId2ProblemInstanceMapping.GetByFirst(Problem.ProblemId);
switch (ProblemInstanceProximity.Value) {
case ProblemInstanceProximityType.MDS:
case ProblemInstanceProximityType.PCA:
case ProblemInstanceProximityType.SOM:
double xa, ya;
GetProjectionCoordinates(currentInstance, out xa, out ya);
foreach (var b in ProblemInstances) {
double xb, yb;
GetProjectionCoordinates(b, out xb, out yb);
var d = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
result[b] = d;
}
break;
case ProblemInstanceProximityType.FeatureSpace:
var features = GetProblemCharacteristics();
var cF = features[currentInstance];
foreach (var b in ProblemInstances) {
var sum = features[b].Select((t, f) => (cF[f] - t) * (cF[f] - t)).Sum();
result[b] = Math.Sqrt(sum);
}
break;
default: throw new InvalidOperationException(string.Format("Unkonwn proximity type {0}", ProblemInstanceProximity.Value));
}
return result;
}
private void GetProjectionCoordinates(IRun problemInstance, out double x, out double y) {
x = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".X"]).Value;
y = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".Y"]).Value;
if (ProblemInstanceProximity.Value == ProblemInstanceProximityType.SOM) {
x = Math.Floor(x);
y = Math.Floor(y);
}
}
public event EventHandler> DownloadStarted;
private void OnDownloadStarted(IProgress progress) {
var handler = DownloadStarted;
if (handler != null) handler(this, new EventArgs(progress));
}
public event EventHandler> AlgorithmInstanceStarted;
private void OnAlgorithmInstanceStarted(IAlgorithm instance) {
var handler = AlgorithmInstanceStarted;
if (handler != null) handler(this, new EventArgs(instance));
}
// implement further classes and methods
private static SortedList Ckmeans1dClusters(double[] estimations, int k, out int[] clusterValues) {
int nPoints = estimations.Length;
var distinct = estimations.Distinct().OrderBy(x => x).ToArray();
var max = distinct.Max();
if (distinct.Length <= k) {
var dict = distinct.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Value, y => y.Index);
for (int i = distinct.Length; i < k; i++)
dict.Add(max + i - distinct.Length + 1, i);
clusterValues = new int[nPoints];
for (int i = 0; i < nPoints; i++)
if (!dict.ContainsKey(estimations[i])) clusterValues[i] = 0;
else clusterValues[i] = dict[estimations[i]];
return new SortedList(dict);
}
var n = distinct.Length;
var D = new double[n, k];
var B = new int[n, k];
for (int m = 0; m < k; m++) {
for (int j = m; j <= n - k + m; j++) {
if (m == 0)
D[j, m] = SumOfSquaredDistances(distinct, 0, j + 1);
else {
var minD = double.MaxValue;
var minI = 0;
for (int i = 1; i <= j; i++) {
var d = D[i - 1, m - 1] + SumOfSquaredDistances(distinct, i, j + 1);
if (d < minD) {
minD = d;
minI = i;
}
}
D[j, m] = minD;
B[j, m] = minI;
}
}
}
var centers = new SortedList();
var upper = B[n - 1, k - 1];
var c = Mean(distinct, upper, n);
centers.Add(c, k - 1);
for (int i = k - 2; i >= 0; i--) {
var lower = B[upper - 1, i];
var c2 = Mean(distinct, lower, upper);
centers.Add(c2, i);
upper = lower;
}
clusterValues = new int[nPoints];
for (int i = 0; i < estimations.Length; i++) {
clusterValues[i] = centers.MinItems(x => Math.Abs(estimations[i] - x.Key)).First().Value;
}
return centers;
}
private static double SumOfSquaredDistances(double[] x, int start, int end) {
if (start == end) throw new InvalidOperationException();
if (start + 1 == end) return 0.0;
double mean = 0.0;
for (int i = start; i < end; i++) {
mean += x[i];
}
mean /= (end - start);
var sum = 0.0;
for (int i = start; i < end; i++) {
sum += (x[i] - mean) * (x[i] - mean);
}
return sum;
}
private static double Mean(double[] x, int start, int end) {
if (start == end) throw new InvalidOperationException();
double mean = 0.0;
for (int i = start; i < end; i++) {
mean += x[i];
}
mean /= (end - start);
return mean;
}
}
}