#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 System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
namespace HeuristicLab.Optimization.Algorithms.SingleObjective {
public abstract class HeuristicAlgorithm : Algorithm
where TContext : HeuristicAlgorithmContext,
IStochasticContext, IEvaluatedSolutionsContext, IBestQualityContext,
IBestSolutionContext, new()
where TProblem : class, ISingleObjectiveProblem, ISingleObjectiveProblemDefinition
where TEncoding : class, IEncoding
where TSolution : class, ISolution {
private Type problemType;
public override Type ProblemType {
get { return typeof(SingleObjectiveProblem); }
}
public new TProblem Problem {
get { return (TProblem)base.Problem; }
set { base.Problem = value; }
}
private CancellationTokenSource cancellationTokenSource;
protected CancellationTokenSource CancellationTokenSource {
get { return cancellationTokenSource; }
private set { cancellationTokenSource = value; }
}
public int? MaximumEvaluations {
get {
var val = ((OptionalValueParameter)Parameters["MaximumEvaluations"]).Value;
return val != null ? val.Value : (int?)null;
}
set {
var param = (OptionalValueParameter)Parameters["MaximumEvaluations"];
param.Value = value.HasValue ? new IntValue(value.Value) : null;
}
}
public TimeSpan? MaximumExecutionTime {
get {
var val = ((OptionalValueParameter)Parameters["MaximumExecutionTime"]).Value;
return val != null ? val.Value : (TimeSpan?)null;
}
set {
var param = (OptionalValueParameter)Parameters["MaximumExecutionTime"];
param.Value = value.HasValue ? new TimeSpanValue(value.Value) : null;
}
}
public double? TargetQuality {
get {
var val = ((OptionalValueParameter)Parameters["TargetQuality"]).Value;
return val != null ? val.Value : (double?)null;
}
set {
var param = (OptionalValueParameter)Parameters["TargetQuality"];
param.Value = value.HasValue ? new DoubleValue(value.Value) : null;
}
}
public bool SetSeedRandomly {
get { return ((FixedValueParameter)Parameters["SetSeedRandomly"]).Value.Value; }
set { ((FixedValueParameter)Parameters["SetSeedRandomly"]).Value.Value = value; }
}
public int Seed {
get { return ((FixedValueParameter)Parameters["Seed"]).Value.Value; }
set { ((FixedValueParameter)Parameters["Seed"]).Value.Value = value; }
}
public IMultiAnalyzer AlgorithmAnalyzer {
get { return ((ValueParameter)Parameters["Analyzer.Algorithm"]).Value; }
set { ((ValueParameter)Parameters["Analyzer.Algorithm"]).Value = value; }
}
public IMultiAnalyzer ProblemAnalyzer {
get { return ((ValueParameter)Parameters["Analyzer.Problem"]).Value; }
set { ((ValueParameter)Parameters["Analyzer.Problem"]).Value = value; }
}
[Storable]
private ResultCollection results;
public override ResultCollection Results {
get { return results; }
}
[Storable]
private TContext context;
public TContext Context {
get { return context; }
protected set {
if (context == value) return;
context = value;
}
}
[StorableConstructor]
protected HeuristicAlgorithm(bool deserializing) : base(deserializing) { }
protected HeuristicAlgorithm(HeuristicAlgorithm original, Cloner cloner)
: base(original, cloner) { }
protected HeuristicAlgorithm() {
results = new ResultCollection();
Parameters.Add(new ValueParameter("Analyzer.Algorithm", "The algorithm's analyzers to apply to the solution(s) (independent of the problem)."));
Parameters.Add(new ValueParameter("Analyzer.Problem", "The problem's analyzer to apply to the solution(s)."));
Parameters.Add(new OptionalValueParameter("MaximumEvaluations", "The maximum number of solution evaluations."));
Parameters.Add(new OptionalValueParameter("MaximumExecutionTime", "The maximum runtime.", new TimeSpanValue(TimeSpan.FromMinutes(1))));
Parameters.Add(new OptionalValueParameter("TargetQuality", "The target quality at which the algorithm terminates."));
Parameters.Add(new FixedValueParameter("SetSeedRandomly", "Whether each run of the algorithm should be conducted with a new random seed.", new BoolValue(true)));
Parameters.Add(new FixedValueParameter("Seed", "The random number seed that is used in case SetSeedRandomly is false.", new IntValue(0)));
}
protected override void OnProblemChanged() {
base.OnProblemChanged();
if (ProblemAnalyzer != null) {
ProblemAnalyzer.Operators.Clear();
if (Problem != null) {
foreach (var analyzer in Problem.Operators.OfType()) {
foreach (var param in analyzer.Parameters.OfType())
param.Depth = 1;
ProblemAnalyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
}
}
}
}
public override void Prepare() {
if (Problem == null) return;
base.Prepare();
results.Clear();
Context = null;
stopRequested = false;
OnPrepared();
}
private bool stopRequested = false;
public override void Start() {
base.Start();
CancellationTokenSource = new CancellationTokenSource();
OnStarted();
var task = Task.Run((Action)Run, cancellationTokenSource.Token);
var continuation = new Task[3];
continuation[0] = task.ContinueWith(t => {
if (t.Exception != null) {
OnExceptionOccurred(t.Exception.InnerExceptions.Count == 1 ? t.Exception.InnerExceptions[0] : t.Exception);
}
OnPaused();
}, TaskContinuationOptions.OnlyOnFaulted);
continuation[1] = task.ContinueWith(t => {
OnStopped();
}, TaskContinuationOptions.OnlyOnRanToCompletion);
continuation[2] = task.ContinueWith(t => {
if (stopRequested) OnStopped();
else OnPaused();
}, TaskContinuationOptions.OnlyOnCanceled);
Task.WhenAny(continuation).ContinueWith(_ => {
CancellationTokenSource.Dispose();
CancellationTokenSource = null;
});
}
public override void Pause() {
base.Pause();
CancellationTokenSource.Cancel();
}
public override void Stop() {
// CancellationToken.ThrowIfCancellationRequested() must be called from within the Run method, otherwise stop does nothing
// alternatively check the IsCancellationRequested property of the cancellation token
base.Stop();
stopRequested = true;
if (CancellationTokenSource != null) {
try {
CancellationTokenSource.Cancel();
} catch {
OnStopped();
}
} else OnStopped();
}
private DateTime lastUpdateTime;
private void Run() {
var token = CancellationTokenSource.Token;
lastUpdateTime = DateTime.UtcNow;
System.Timers.Timer timer = new System.Timers.Timer(250);
timer.AutoReset = true;
timer.Elapsed += timer_Elapsed;
timer.Start();
try {
if (context == null) {
context = CreateContext();
IExecutionContext ctxt = null;
foreach (var item in Problem.ExecutionContextItems)
ctxt = new Core.ExecutionContext(ctxt, item, Context.Scope);
ctxt = new Core.ExecutionContext(ctxt, this, Context.Scope);
context.Parent = ctxt;
if (SetSeedRandomly) Seed = new System.Random().Next();
Context.Random.Reset(Seed);
Context.Scope.Variables.Add(new Variable("Results", Results));
} else context.CancellationToken = token;
if (!Context.Initialized) {
try {
PerformInitialize(token);
} catch {
context = null;
return;
}
Context.Initialized = true;
}
while (!CheckTerminate(token)) {
PerformIterate(token);
PerformAnalyze(token);
token.ThrowIfCancellationRequested();
}
} finally {
timer.Elapsed -= timer_Elapsed;
timer.Stop();
ExecutionTime += DateTime.UtcNow - lastUpdateTime;
}
}
protected virtual TContext CreateContext() {
return new TContext() { Problem = Problem, CancellationToken = CancellationTokenSource.Token };
}
protected virtual ISingleObjectiveSolutionScope CreateEmptySolutionScope() {
return new SingleObjectiveSolutionScope(null, Problem.Encoding.Name, double.NaN, Problem.Evaluator.QualityParameter.ActualName);
}
protected static bool IsBetter(bool maximization, double a, double b) {
return !double.IsNaN(a) && double.IsNaN(b) || maximization && a > b || !maximization && a < b;
}
protected virtual void Evaluate(ISingleObjectiveSolutionScope scope, CancellationToken token) {
scope.Fitness = Problem.Evaluate(scope.Solution, Context.Random);
}
protected abstract void PerformInitialize(CancellationToken token);
protected abstract void PerformIterate(CancellationToken token);
protected virtual void PerformAnalyze(CancellationToken token) {
IResult res;
if (!Results.TryGetValue("EvaluatedSolutions", out res)) {
res = new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions));
Results.Add(res);
} else ((IntValue)res.Value).Value = Context.EvaluatedSolutions;
if (!Results.TryGetValue("BestQuality", out res)) {
res = new Result("BestQuality", new DoubleValue(Context.BestQuality));
Results.Add(res);
} else ((DoubleValue)res.Value).Value = Context.BestQuality;
RunOperator(ProblemAnalyzer, Context.Scope, token);
RunOperator(AlgorithmAnalyzer, Context.Scope, token);
}
protected virtual bool CheckTerminate(CancellationToken token) {
return MaximumEvaluations.HasValue && Context.EvaluatedSolutions >= MaximumEvaluations.Value
|| MaximumExecutionTime.HasValue && ExecutionTime >= MaximumExecutionTime.Value
|| TargetQuality.HasValue && (Problem.Maximization && Context.BestQuality >= TargetQuality.Value
|| !Problem.Maximization && Context.BestQuality <= TargetQuality.Value);
}
#region Engine Helper
protected void RunOperator(IOperator op, IScope scope, CancellationToken cancellationToken) {
var stack = new Stack();
stack.Push(Context.CreateChildOperation(op, scope));
while (stack.Count > 0) {
cancellationToken.ThrowIfCancellationRequested();
var next = stack.Pop();
if (next is OperationCollection) {
var coll = (OperationCollection)next;
for (int i = coll.Count - 1; i >= 0; i--)
if (coll[i] != null) stack.Push(coll[i]);
} else if (next is IAtomicOperation) {
var operation = (IAtomicOperation)next;
try {
next = operation.Operator.Execute((IExecutionContext)operation, cancellationToken);
} catch (Exception ex) {
stack.Push(operation);
if (ex is OperationCanceledException) throw ex;
else throw new OperatorExecutionException(operation.Operator, ex);
}
if (next != null) stack.Push(next);
}
}
}
#endregion
#region Events
private void timer_Elapsed(object sender, System.Timers.ElapsedEventArgs e) {
System.Timers.Timer timer = (System.Timers.Timer)sender;
timer.Enabled = false;
DateTime now = DateTime.UtcNow;
ExecutionTime += now - lastUpdateTime;
lastUpdateTime = now;
timer.Enabled = true;
}
#endregion
}
}