source: branches/3055_SMSEMOA/HeuristicLab.Algorithms.SMSEMOA/3.4/SMSEMOAAlgorithm.cs @ 17717

#region License Information
/* HeuristicLab
 * Author: Kaifeng Yang
 * 
 * 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/>.
 */

// SMS-EMOA
/*
Implemenetation of a real-coded SMS_EMOA algorithm.
This implementation follows the description of: 'M. Emmerich, N. Beume, and B. Naujoks. 
An EMO Algorithm Using the Hypervolume Measure as Selection Criterion.EMO 2005.'
*/
#endregion

using HEAL.Attic;                       
using HeuristicLab.Common;             
using HeuristicLab.Core;               
using HeuristicLab.Data;               
using HeuristicLab.Random;             
using System.Linq;                     
using System;
using CancellationToken = System.Threading.CancellationToken;


/*  This algorithm is SMS-EMOA implementation on HL. The main structure and interfaces with HL are copied from MOEA/D on HL, which was written by Dr. Bogdan Burlacu. The S-metric selection operator was adapted from Kaifeng's MATLAB toolbox in SMS-EMOA. The computational complexity of HVC is AT LEAST $O (n^2 \log n)$ in 2-D and 3-D cases. HVC should definitely be reduced to $\Theta (n \times \log n)$. 
 *  
 *  This algorithm assumes: 
 *    1. minimization problems. For maximization problems, it is better to add "-" symbol.
 *  
 *  This algorithm works on:
 *    1. continuous, discrete, mixed-integer MOO problems. For different types of problems, the operators should be adjusted accordingly. 
 *    2. both multi-objective and many-objective problems. For many-objective problems, the bottleneck is the computational complexity of HV. 
 * 
 * This algorithm is the basic implementation of SMS-EMOA, proposed by Michael Emmerich et. al. Some potential improvements can be: 
 *    1. Dynamic reference point strategy
 *    2. Normalized fitness value strategy ---- desirability function. See, Yali, Longmei, Kaifeng, Michael Emmerich CEC paper. 
 *    3. HVC calculation should definitely be improved, at least in the 2D and 3D cases.
 *    4. multiple point strategy when $\lambda>1$ 
 *    5. multiple reference points strategy, in ICNC 2016, Zhiwei Yang et. al. 
 *    6. HVC approximation by R2 for MANY OBJECTIVE cases, by Ishibushi 2019, IEEE TEC  
 *    7. Maybe: See maps 
 * 
 * Global parameters:
 *    1. population  
 *    
 * Many thanks for Bogdan Burlacu and Johannes Karder, especially Bogdan for his explanation, help, and supports. 
 */

namespace HeuristicLab.Algorithms.SMSEMOA {
  // Format: 
  // The indexed name of the algorithm/item, Description of the algorithm/item in HL  
  [Item("SMS-EMOA", "SMS-EMOA implementation adapted from MATLAB.")]

  // Call "HeuristicLab.Core"
  // Define the category of this class. 
  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 125)]

  // Call "HEAL.Attic"
  // Define GUID for this Class
  [StorableType("05B0D578-B285-4049-B01F-9A4D348A8C73")]

  public class SMSEMOAAlgorithm : SMSEMOAAlgorithmBase {
    public SMSEMOAAlgorithm() { }

    protected SMSEMOAAlgorithm(SMSEMOAAlgorithm original, Cloner cloner) : base(original, cloner) { }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new SMSEMOAAlgorithm(this, cloner);
    }

    [StorableConstructor]
    protected SMSEMOAAlgorithm(StorableConstructorFlag deserializing) : base(deserializing) { }

    protected override void Run(CancellationToken cancellationToken) {
      if (previousExecutionState != ExecutionState.Paused) { // Call "base" class, SMSEMOAAlgorithmBase
        InitializeAlgorithm(cancellationToken);
      }

      var populationSize = PopulationSize.Value;
      bool[] maximization = ((BoolArray)Problem.MaximizationParameter.ActualValue).CloneAsArray();
      var maximumEvaluatedSolutions = MaximumEvaluatedSolutions.Value;
      var crossover = Crossover;
      var crossoverProbability = CrossoverProbability.Value;
      var mutator = Mutator;
      var mutationProbability = MutationProbability.Value;
      var evaluator = Problem.Evaluator;
      var analyzer = Analyzer;
      var rand = RandomParameter.Value;
      //int lambda = 1;            // the size of offspring 
      var lambda = Lambda.Value;
      //int indexOffspring = 0;    // the index of offspring to be generated

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


      // initilize the offspring population. 
      offspringPopulation = new ISMSEMOASolution[lambda];
      jointPopulation = new ISMSEMOASolution[lambda + populationSize];

      // Mainloop 
      while (evaluatedSolutions < maximumEvaluatedSolutions && !cancellationToken.IsCancellationRequested) {

        int indexOffspring = 0;

        // Generate one offspring: 
        var mates = MatingSelection(rand, 2); // select parents


        // Get the selected individuals 
        // int variable mate[i] --> index population --> extract "Individual" --> Clone it. 
        var s1 = (IScope)population[mates[0]].Individual.Clone();
        var s2 = (IScope)population[mates[1]].Individual.Clone();

        // URGENT: What is global scope? 
        s1.Parent = s2.Parent = globalScope;

        IScope childScope = null;

        // crossover
        if (rand.NextDouble() < crossoverProbability) {
          childScope = new Scope($"{mates[0]}+{mates[1]}") { Parent = executionContext.Scope };
          childScope.SubScopes.Add(s1);
          childScope.SubScopes.Add(s2);
          // The crossover is executed by using SubScope information. 
          var opCrossover = executionContext.CreateChildOperation(crossover, childScope);
          ExecuteOperation(executionContext, innerToken, opCrossover);
          // Clear the SubScopes for the next useage in the next iteration. 
          childScope.SubScopes.Clear(); // <<-- VERY IMPORTANT!
        }
        else {
          // mutation
          childScope = childScope ?? s1;
          var opMutation = executionContext.CreateChildOperation(mutator, childScope);
          ExecuteOperation(executionContext, innerToken, opMutation);
        }

        // evaluation
        if (childScope != null) { // Evaluate the childScope
          var opEvaluation = executionContext.CreateChildOperation(evaluator, childScope);
          ExecuteOperation(executionContext, innerToken, opEvaluation);

          // childScope 
          var qualities = (DoubleArray)childScope.Variables["Qualities"].Value;
          var childSolution = new SMSEMOASolution(childScope, maximization.Length, 0);
          // set child qualities
          for (int j = 0; j < maximization.Length; ++j) {
            childSolution.Qualities[j] = maximization[j] ? 1 - qualities[j] : qualities[j];
          }
          IdealPoint.UpdateIdeal(childSolution.Qualities);
          NadirPoint.UpdateNadir(childSolution.Qualities);

          // TODO, KF -- For later usage when $lambda > 1$
          childSolution.HypervolumeContribution = null;
          childSolution.NondominanceRanking = null;

          offspringPopulation[indexOffspring] = childSolution;

          ++evaluatedSolutions;
        }
        else {
          // no crossover or mutation were applied, a child was not produced, do nothing
        }

        if (evaluatedSolutions >= maximumEvaluatedSolutions) {
          break;
        }

        // Update jointPopulation 
        population.CopyTo(jointPopulation, 0);
        offspringPopulation.CopyTo(jointPopulation, populationSize);

        // Update the population according to the S-metric selection. 
        // TODO:
        //    See the details of TODO list at the beginning for this file .... 
        SmetricSelection(lambda);

        // run analyzer
        var analyze = executionContext.CreateChildOperation(analyzer, globalScope);
        ExecuteOperation(executionContext, innerToken, analyze);
        // update Pareto-front approximation sets
        UpdateParetoFronts();
        // Show some results in the GUI.
        Results.AddOrUpdateResult("IdealPoint", new DoubleArray(IdealPoint));
        Results.AddOrUpdateResult("NadirPoint", new DoubleArray(NadirPoint));
        Results.AddOrUpdateResult("Evaluated Solutions", new IntValue(evaluatedSolutions));

        // Update globalScope
        globalScope.SubScopes.Replace(population.Select(x => (IScope)x.Individual));
      }
    }
  }
}