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

#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;
using HeuristicLab.Problems.DataAnalysis.Symbolic;
using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
using HeuristicLab.Random;
using HeuristicLab.Selection;
using System.Collections.Generic;
using System.Linq;
using CancellationToken = System.Threading.CancellationToken;
using Variable = HeuristicLab.Core.Variable;

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

    [StorableConstructor]
    protected EMMAlgorithm(StorableConstructorFlag _) : base(_) { }
    #endregion
    #region Algorithm run
    protected override void Run(CancellationToken cancellationToken) {

      Map.DistanceParametr = DistanceType.Value;

      if (AlgorithmImplemetationType.Value == "Read") {
        Map.MapRead(trees);
      } else {
        Map.MapCreationPrepare(trees);
        Map.CreateMap(RandomParameter.Value, Problem);
      }
      if (previousExecutionState != ExecutionState.Paused) {
        InitializeAlgorithm(cancellationToken);
      }
      if (!globalScope.Variables.ContainsKey("TreeModelMap"))
        globalScope.Variables.Add(new Variable("TreeModelMap", Map));
      if (!globalScope.Variables.ContainsKey("Map"))
        globalScope.Variables.Add(new Variable("Map", 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 maximumEvaluatedSolutions = MaximumEvaluatedSolutions.Value;
      var crossover = Crossover;
      var selector = Selector;
      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;
      var fmd = new InfixExpressionFormatter();
      // cancellation token for the inner operations which should not be immediately canceled
      var innerToken = new CancellationToken();
      // for future
      //var mutatorTypes = new SymbolicExpressionTreeManipulator[]
      //{
      //     new EMMMultyPointsMutator(),
      //     new EMMMultyPointsMutatorNodeTypeSaving (),
      //     new EMMMutators()
      //};
      //var tuu = MutatorParameter.ValidValues;
      //var select = SelectorParameter.ValidValues;

      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) {
          IScope childScope = null;
          // for future
          //var obbbb = CrossoverParameter.ValidValues.ToList();
          //int nn = 3;
          //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(obbbb[nn], childScope);
          //  ExecuteOperation(executionContext, innerToken, op1);
          //  childScope.SubScopes.Clear();
          //}

          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) {
            if (!childScope.Variables.ContainsKey("Quality"))
              childScope.Variables.Add(new Variable("Quality"));
            EvaluationComplex(executionContext, innerToken, 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;
          }
        }

        UpDateParameters();

        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 virtual void UpDateParameters() {
      if (Map is EMMSucsessMap) {
        var population = new Dictionary<ISymbolicExpressionTree, double>();
        foreach (var individ in Population) {
          var tree = (ISymbolicExpressionTree)(((IScope)individ.Individual).Variables["SymbolicExpressionTree"].Value);
          population.Add(tree, individ.Qualities.Value);
        }
        Map.MapUpDate(population);
        population.Clear();
      }
    }
    #endregion
    #region Initialization
    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>()) {
        globalScope.Variables.Add(new Variable(parameter.Name, parameter.Value));
      }
      globalScope.Variables.Add(new Variable("Results", Results)); // make results available as a parameter for analyzers etc.

      var rand = RandomParameter.Value;
      if (SetSeedRandomly) Seed = RandomSeedGenerator.GetSeed();
      rand.Reset(Seed);
      EvaluatedSolutions = 0;
      //  InitializeParametrs(); for future
      InitializePopulation(executionContext, cancellationToken, rand);


      base.Initialize(cancellationToken);
    }
    protected virtual void InitializeParametrs() { }

    private void InitializePopulation(ExecutionContext executionContext, CancellationToken cancellationToken, IRandom random) {
      Population = new List<IEMMSolution>();
      var fmd = new InfixExpressionFormatter();
      var evaluator = Problem.Evaluator;
      var creator = Problem.SolutionCreator;
      var parser = new InfixExpressionParser();

      var parentScope = executionContext.Scope; //main scope for the next step work
                                                // first, create all individuals
      for (int i = 0; i < PopulationSize.Value; ++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>()) {
          Map.NodeManipulationForInizializtion(random, node);
        }
        parentScope.SubScopes.Add(childScope);
      }
      // then, evaluate them and update qualities
      for (int i = 0; i < PopulationSize.Value; ++i) {
        var childScope = parentScope.SubScopes[i];
        if (!childScope.Variables.ContainsKey("Quality"))
          childScope.Variables.Add(new Variable("Quality", new DoubleValue(0)));
        EvaluationComplex(executionContext, cancellationToken, childScope);
      }
    }
    #endregion
    #region Evaluators
    private void EvaluationComplex(ExecutionContext executionContext, CancellationToken cancellationToken, IScope childScope) {
      var evaluator = Problem.Evaluator;
      if (evaluator is SymbolicRegressionConstantOptimizationEvaluator eval) {
        var creator = Problem.SolutionCreator;
        var name = ((ISymbolicExpressionTreeCreator)creator).SymbolicExpressionTreeParameter.ActualName;
        var tree = (ISymbolicExpressionTree)childScope.Variables[name].Value;
        var treeWithModelInside = ModelToTreePusher(tree);

        //ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(evaluator, treeScope));
        var pd = (IRegressionProblemData)Problem.ProblemData;
        var estimationLimits = ((SymbolicRegressionSingleObjectiveProblem)Problem).EstimationLimits;
        var interpreter = new SymbolicDataAnalysisExpressionTreeBatchInterpreter();
        var quality = SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(interpreter, treeWithModelInside, pd, pd.TrainingIndices, applyLinearScaling: true, maxIterations: 10, updateVariableWeights: true, lowerEstimationLimit: estimationLimits.Lower, upperEstimationLimit: estimationLimits.Upper, updateConstantsInTree: true);
        childScope.Variables["Quality"].Value = new DoubleValue(quality);

        int index = 0;
        ConstuntValuesInTreeUpdate(tree, ConstantValuesFromTreeToListExtruction(treeWithModelInside), ref index);
        childScope.Variables[name].Value = tree;
        EvaluatedSolutions += 10;
      } else {
        var op3 = executionContext.CreateChildOperation(evaluator, childScope);
        ExecuteOperation(executionContext, cancellationToken, op3);
        EvaluatedSolutions += 1;
      }
      Population.Add(new EMMSolution(childScope));
    }
    private ISymbolicExpressionTree ModelToTreePusher(ISymbolicExpressionTree tree) {
      //All model nodes in tree are exchange to trees that are stored in model nodes.
      // After this function we have deal with usual tree
      var clone = (ISymbolicExpressionTree)tree.Clone();
      foreach (var node in clone.IterateNodesPostfix().OfType<TreeModelTreeNode>()) {
        var newChild = node.Tree.Root.GetSubtree(0).GetSubtree(0);
        Swap(node, newChild);
      }
      return clone;
    }
    protected static void Swap(ISymbolicExpressionTreeNode oldChild, ISymbolicExpressionTreeNode newChild) {
      var parent = oldChild.Parent;
      if (parent == null)
        return;

      var index = parent.IndexOfSubtree(oldChild);
      parent.RemoveSubtree(index);
      parent.InsertSubtree(index, newChild);
    }
    private List<double> ConstantValuesFromTreeToListExtruction(ISymbolicExpressionTree tree) {
      //This function stored in a list all constants and coefficients from the tree
      var constants = new List<double>();
      foreach (var node in tree.IterateNodesPostfix()) {
        if (node is ConstantTreeNode cNode) {
          constants.Add(cNode.Value);
        }
        if (node is VariableTreeNode vNode) {
          constants.Add(vNode.Weight);
        }
      }
      return constants;
    }
    private void ConstuntValuesInTreeUpdate(ISymbolicExpressionTree tree, List<double> constants, ref int index) {
      foreach (var node in tree.IterateNodesPostfix()) {
        if (node is ConstantTreeNode cNode) {
          cNode.Value = constants[index];
          index++;
        } else if (node is VariableTreeNode vNode) {
          vNode.Weight = constants[index];
          index++;
        } else if (node is TreeModelTreeNode mNode) {
          ConstuntValuesInTreeUpdate(mNode.Tree, constants, ref index);
        }

      }
    }
    #endregion
    #region Local Search
    // next function was not tested in real work
    private void LocalDecent(ISymbolicDataAnalysisSingleObjectiveProblem problem, CancellationToken cancellationToken, IScope childScope) {
      int maxStepNumber = 100;
      var name = ((ISymbolicExpressionTreeCreator)Problem.SolutionCreator).SymbolicExpressionTreeParameter.ActualName;
      var tree = (ISymbolicExpressionTree)childScope.Variables[name].Value;
      var oldTree = tree.Clone();
      ExecuteOperation(executionContext, cancellationToken, executionContext.CreateChildOperation(problem.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 tree, IRandom rand, CancellationToken cancellationToken, IScope childScope) {
      int treeNumber = tree.TreeNumber;
      var oldSubTree = (ISymbolicExpressionTree)tree.Tree.Clone();
      double oldQuality = ((DoubleValue)childScope.Variables["Quality"].Value).Value;
      int cluster;
      if (Map is EMMIslandMap map)
        cluster = map.ClusterNumber[treeNumber];
      else cluster = treeNumber;
      int newTreeNumber = rand.Next(Map.Map[cluster].Count);
      tree.Tree = (ISymbolicExpressionTree)Map.ModelSet[newTreeNumber].Clone();
      tree.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) {
        tree.Tree = (ISymbolicExpressionTree)oldSubTree.Clone();
        ((DoubleValue)childScope.Variables["Quality"].Value).Value = oldQuality;
      }
    }
    #endregion
  }


}