source: branches/2988_ModelsOfModels2/HeuristicLab.Algorithms.EMM/EMMAlgorithm.cs @ 16899

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2019 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 <http://www.gnu.org/licenses/>.
 */
#endregion

using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
using HeuristicLab.Random;
using HeuristicLab.Selection;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using CancellationToken = System.Threading.CancellationToken;
using Variable = HeuristicLab.Core.Variable;

namespace HeuristicLab.Algorithms.EvolvmentModelsOfModels {
  [Item("EvolvmentModelsOfModels Algorithm ", "EMM implementation")]
  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 125)]
  [StorableType("AD23B21F-089A-4C6C-AD2E-1B01E7939CF5")]
  public class EMMAlgorithm : EvolvmentModelsOfModelsAlgorithmBase {
    public EMMAlgorithm() : base() { }
    protected EMMAlgorithm(EMMAlgorithm original, Cloner cloner) : base(original, cloner) {
      //if (original.Map != null) {
      //  Map = cloner.Clone(original.Map);
      //}
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new EMMAlgorithm(this, cloner);
    }

    [StorableConstructor]
    protected EMMAlgorithm(StorableConstructorFlag _) : base(_) { }

    protected override void Run(CancellationToken cancellationToken) {
      InfixExpressionParser parser = new InfixExpressionParser();
      var trees = File.ReadAllLines(InputFileParameter.Value.Value).Select(parser.Parse);
      if (AlgorithmImplemetationType.Value == "Read") {
        Map.MapRead(RandomParameter.Value, trees, "Map.txt");
      } else {
        Map.MapCreationPrepare(RandomParameter.Value, trees, ClusterNumbersParameter.Value.Value);
        Map.CreateMap(RandomParameter.Value, ClusterNumbersParameter.Value.Value);
       // Map.WriteMapToTxtFile(RandomParameter.Value);
      }

      ClusterNumbersShowParameter.Value.Value = Map.K;

      if (AlgorithmImplemetationType.Value == "OnlyMap") {
        globalScope = new Scope("Global Scope");
        executionContext = new ExecutionContext(null, this, globalScope);
      } else {
        if (previousExecutionState != ExecutionState.Paused) {
          InitializeAlgorithm(cancellationToken);
        }
        if (!globalScope.Variables.ContainsKey("TreeModelMap"))
          globalScope.Variables.Add(new Variable("TreeModelMap", Map));
        EMMAlgorithmRun(cancellationToken);
      }
    }
    private void EMMAlgorithmRun(CancellationToken cancellationToken) {
      var bestSelector = new BestSelector();
      bestSelector.CopySelected = new BoolValue(false);
      bestSelector.MaximizationParameter.ActualName = "Maximization";
      bestSelector.NumberOfSelectedSubScopesParameter.ActualName = "Elites";
      bestSelector.QualityParameter.ActualName = "Quality";

      var populationSize = PopulationSize.Value;
      var maximumEvaluatedSolutions = MaximumEvaluatedSolutions.Value;
      var crossover = Crossover;
      var selector = Selector;
      var groupSize = GroupSize.Value;
      var crossoverProbability = CrossoverProbability.Value;
      var mutator = Mutator;
      var mutationProbability = MutationProbability.Value;
      var evaluator = Problem.Evaluator;
      var analyzer = Analyzer;
      var rand = RandomParameter.Value;
      var elites = Elites.Value;

      // cancellation token for the inner operations which should not be immediately cancelled
      var innerToken = new CancellationToken();

      while (EvaluatedSolutions < maximumEvaluatedSolutions && !cancellationToken.IsCancellationRequested) {

        var op4 = executionContext.CreateChildOperation(bestSelector, executionContext.Scope); // select elites
        ExecuteOperation(executionContext, innerToken, op4);

        var remaining = executionContext.Scope.SubScopes.Single(x => x.Name == "Remaining");
        executionContext.Scope.SubScopes.AddRange(remaining.SubScopes);
        var selected = executionContext.Scope.SubScopes.Single(x => x.Name == "Selected");
        executionContext.Scope.SubScopes.AddRange(selected.SubScopes);
        Population.Clear();
        Population.AddRange(selected.SubScopes.Select(x => new EMMSolution(x)));
        executionContext.Scope.SubScopes.Remove(remaining);
        executionContext.Scope.SubScopes.Remove(selected);

        var op = executionContext.CreateChildOperation(selector, executionContext.Scope);// select the rest of the Population
        ExecuteOperation(executionContext, innerToken, op);

        remaining = executionContext.Scope.SubScopes.Single(x => x.Name == "Remaining");
        selected = executionContext.Scope.SubScopes.Single(x => x.Name == "Selected");

        for (int i = 0; i < selector.NumberOfSelectedSubScopesParameter.Value.Value; i += 2) {
          // crossover
          IScope childScope = null;
          if (rand.NextDouble() < crossoverProbability) {
            childScope = new Scope($"{i}+{i + 1}") { Parent = executionContext.Scope };
            childScope.SubScopes.Add(selected.SubScopes[i]);
            childScope.SubScopes.Add(selected.SubScopes[i + 1]);
            var op1 = executionContext.CreateChildOperation(crossover, childScope);
            ExecuteOperation(executionContext, innerToken, op1);
            childScope.SubScopes.Clear();
          }

          childScope = childScope ?? selected.SubScopes[i];
          // mutation
          if (rand.NextDouble() < mutationProbability) {
            var op2 = executionContext.CreateChildOperation(mutator, childScope);
            ExecuteOperation(executionContext, innerToken, op2);
          }

          // evaluation
          if (childScope != null) {
            var op3 = executionContext.CreateChildOperation(evaluator, childScope);
            ExecuteOperation(executionContext, innerToken, op3);
            var qualities = (DoubleValue)childScope.Variables["Quality"].Value;
            var childSolution = new EMMSolution(childScope);
            // set child qualities
            childSolution.Qualities = qualities;
            ++EvaluatedSolutions;
            Population.Add(new EMMSolution(childScope));
          } else {// no crossover or mutation were applied, a child was not produced, do nothing
            Population.Add(new EMMSolution(selected.SubScopes[i]));
          }

          if (EvaluatedSolutions >= maximumEvaluatedSolutions) {
            break;
          }

        }
        globalScope.SubScopes.Replace(Population.Select(x => (IScope)x.Individual));
        // run analyzer
        var analyze = executionContext.CreateChildOperation(analyzer, globalScope);
        ExecuteOperation(executionContext, innerToken, analyze);
        Results.AddOrUpdateResult("Evaluated Solutions", new IntValue(EvaluatedSolutions));
      }
    }
    protected void InitializeAlgorithm(CancellationToken cancellationToken) {
      globalScope = new Scope("Global Scope");
      executionContext = new ExecutionContext(null, this, globalScope);

      // set the execution context for parameters to allow lookup
      foreach (var parameter in Problem.Parameters.OfType<IValueParameter>()) {  // 
                                                                                 // we need all of these in order for the wiring of the operators to work
        globalScope.Variables.Add(new Core.Variable(parameter.Name, parameter.Value));
      }
      globalScope.Variables.Add(new Core.Variable("Results", Results)); // make results available as a parameter for analyzers etc.

      var rand = RandomParameter.Value;
      if (SetSeedRandomly) Seed = RandomSeedGenerator.GetSeed();
      rand.Reset(Seed);

      var populationSize = PopulationSize.Value;

      InitializePopulation(executionContext, cancellationToken, rand);

      // initialize data structures for map clustering
      //var models = new ItemList<ISymbolicExpressionTree>(Map.ModelSet);
      //var map = new ItemList<ItemList<IntValue>>();
      //foreach (var list in Map.Map) {
      //  map.Add(new ItemList<IntValue>(list.Select(x => new IntValue(x))));
      //}
      //var clusterNumber = new ItemList<IntValue>(Map.ClusterNumber.Select(x => new IntValue(x)));
      //globalScope.Variables.Add(new Variable("Models", models));
      //globalScope.Variables.Add(new Variable("Map", map));
      //globalScope.Variables.Add(new Variable("ClusterNumber", clusterNumber));

      EvaluatedSolutions = populationSize;
      base.Initialize(cancellationToken);
    }
    private void InitializePopulation(ExecutionContext executionContext, CancellationToken cancellationToken, IRandom random) {
      var creator = Problem.SolutionCreator;
      var evaluator = Problem.Evaluator;
      var populationSize = PopulationSize.Value;
      Population = new List<IEMMSolution>(populationSize);

      var parentScope = executionContext.Scope; //main scope for the next step work
      // first, create all individuals
      for (int i = 0; i < populationSize; ++i) {
        var childScope = new Scope(i.ToString()) { Parent = parentScope };
        ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(creator, childScope));
        var name = ((ISymbolicExpressionTreeCreator)creator).SymbolicExpressionTreeParameter.ActualName;
        var tree = (ISymbolicExpressionTree)childScope.Variables[name].Value;
        foreach (var node in tree.IterateNodesPostfix().OfType<TreeModelTreeNode>()) {
          node.Tree = Map.NewModelForInizializtion(random, out int cluster, out int treeNumber);
          node.SetLocalParameters(random, 0.5);
          node.ClusterNumer = cluster;
          node.TreeNumber = treeNumber;
        }
        parentScope.SubScopes.Add(childScope);
      }

      // then, evaluate them and update qualities
      for (int i = 0; i < populationSize; ++i) {
        var childScope = parentScope.SubScopes[i];
        ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(evaluator, childScope));

        var qualities = (DoubleValue)childScope.Variables["Quality"].Value;
        var solution = new EMMSolution(childScope);  // Create solution and push individual inside

        solution.Qualities = qualities;
        Population.Add(solution);  // push solution to Population 
      }
    }
    private void LocalDecent(ISymbolicDataAnalysisSingleObjectiveProblem problem, CancellationToken cancellationToken, IScope childScope) {
      int maxStepNumber = 100;
      var creator = Problem.SolutionCreator;
      var name = ((ISymbolicExpressionTreeCreator)creator).SymbolicExpressionTreeParameter.ActualName;
      var tree = (ISymbolicExpressionTree)childScope.Variables[name].Value;
      var evaluator = problem.Evaluator;
      var oldTree = tree.Clone();
      ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(evaluator, childScope));
      var rand = RandomParameter.Value;
      if (SetSeedRandomly) Seed = RandomSeedGenerator.GetSeed();
      rand.Reset(Seed);
      while (maxStepNumber > 0) {
        maxStepNumber = TreeIterator(tree.Root, rand, cancellationToken, childScope, maxStepNumber);
      }
    }
    int TreeIterator(ISymbolicExpressionTreeNode a, IRandom rand, CancellationToken cancellationToken, IScope childScope, int maxStepNumber) {
      if (a is TreeModelTreeNode modelNode) {
        ModelChange(modelNode, rand, cancellationToken, childScope);
        maxStepNumber--;
      }
      if (a.Subtrees != null) {
        for (int i = 0; i < (a.Subtrees.Count()); i++) {
          TreeIterator(a.Subtrees.ToList()[i], rand, cancellationToken, childScope, maxStepNumber);
        }
      }
      return maxStepNumber;
    }
    void ModelChange(TreeModelTreeNode a, IRandom rand, CancellationToken cancellationToken, IScope childScope) {
      int treeNumber = a.TreeNumber;
      var oldSubTree = (ISymbolicExpressionTree)a.Tree.Clone();
      double oldQuality = ((DoubleValue)childScope.Variables["Quality"].Value).Value;
      int cluster = Map.ClusterNumber[treeNumber];
      int newTreeNumber = rand.Next(Map.Map[cluster].Count);
      a.Tree = (ISymbolicExpressionTree)Map.ModelSet[newTreeNumber].Clone();
      a.Tree.Root.ShakeLocalParameters(rand, 1);
      var evaluator = Problem.Evaluator;
      ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(evaluator, childScope));
      double currentQuality = ((DoubleValue)childScope.Variables["Quality"].Value).Value;
      if (oldQuality > currentQuality) {
        a.Tree = (ISymbolicExpressionTree)oldSubTree.Clone();
        ((DoubleValue)childScope.Variables["Quality"].Value).Value = oldQuality;
      }
    }
  }


}