source: branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs @ 17686

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.RealVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Problems.TestFunctions.MultiObjective;
using HeuristicLab.Random;

namespace HeuristicLab.Algorithms.NSGA3
{
    /// <summary>
    /// The Reference Point Based Non-dominated Sorting Genetic Algorithm III was introduced in Deb
    /// et al. 2013. An Evolutionary Many-Objective Optimization Algorithm Using Reference Point
    /// Based Non-dominated Sorting Approach. IEEE Transactions on Evolutionary Computation, 18(4),
    /// pp. 577-601.
    /// </summary>
    [Item("NSGA-III", "The Reference Point Based Non-dominated Sorting Genetic Algorithm III was introduced in Deb et al. 2013. An Evolutionary Many-Objective Optimization Algorithm Using Reference Point Based Non-dominated Sorting Approach. IEEE Transactions on Evolutionary Computation, 18(4), pp. 577-601.")]
    [Creatable(Category = CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 136)]
    [StorableType("07C745F7-A8A3-4F99-8B2C-F97E639F9AC3")]
    public class NSGA3 : BasicAlgorithm
    {
        public override bool SupportsPause => false;

        #region ProblemProperties

        public override Type ProblemType
        {
            get { return typeof(MultiObjectiveBasicProblem<RealVectorEncoding>); }
        }

        public new MultiObjectiveBasicProblem<RealVectorEncoding> Problem
        {
            get { return (MultiObjectiveBasicProblem<RealVectorEncoding>)base.Problem; }
            set { base.Problem = value; }
        }

        public int NumberOfObjectives
        {
            get
            {
                if (!(Problem is MultiObjectiveTestFunctionProblem testFunctionProblem)) throw new NotSupportedException("Only test multi objective test function problems are supported");
                return testFunctionProblem.Objectives;
            }
        }

        #endregion ProblemProperties

        #region Storable fields

        [Storable]
        private IRandom random;

        [Storable]
        private List<Solution> solutions; // maybe todo: rename to nextGeneration (see Run method)

        #endregion Storable fields

        #region ParameterAndResultsNames

        // Parameter Names

        private const string SeedName = "Seed";
        private const string SetSeedRandomlyName = "Set Seed Randomly";
        private const string PopulationSizeName = "Population Size";
        private const string CrossoverProbabilityName = "Crossover Probability";
        private const string CrossoverContiguityName = "Crossover Contiguity";
        private const string MutationProbabilityName = "Mutation Probability";
        private const string MaximumGenerationsName = "Maximum Generations";
        private const string DominateOnEqualQualitiesName = "Dominate On Equal Qualities";

        // Results Names

        private const string GeneratedReferencePointsResultName = "Generated Reference Points";
        private const string CurrentGenerationResultName = "Generations";
        private const string GenerationalDistanceResultName = "Generational Distance";
        private const string InvertedGenerationalDistanceResultName = "Inverted Generational Distance";
        private const string ScatterPlotResultName = "Scatter Plot";
        private const string CurrentFrontResultName = "Pareto Front"; // Do not touch this

        #endregion ParameterAndResultsNames

        #region ParameterProperties

        private IFixedValueParameter<IntValue> SeedParameter
        {
            get { return (IFixedValueParameter<IntValue>)Parameters[SeedName]; }
        }

        private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter
        {
            get { return (IFixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyName]; }
        }

        private IFixedValueParameter<IntValue> PopulationSizeParameter
        {
            get { return (IFixedValueParameter<IntValue>)Parameters[PopulationSizeName]; }
        }

        private IFixedValueParameter<PercentValue> CrossoverProbabilityParameter
        {
            get { return (IFixedValueParameter<PercentValue>)Parameters[CrossoverProbabilityName]; }
        }

        private IFixedValueParameter<DoubleValue> CrossoverContiguityParameter
        {
            get { return (IFixedValueParameter<DoubleValue>)Parameters[CrossoverContiguityName]; }
        }

        private IFixedValueParameter<PercentValue> MutationProbabilityParameter
        {
            get { return (IFixedValueParameter<PercentValue>)Parameters[MutationProbabilityName]; }
        }

        private IFixedValueParameter<IntValue> MaximumGenerationsParameter
        {
            get { return (IFixedValueParameter<IntValue>)Parameters[MaximumGenerationsName]; }
        }

        private IFixedValueParameter<BoolValue> DominateOnEqualQualitiesParameter
        {
            get { return (IFixedValueParameter<BoolValue>)Parameters[DominateOnEqualQualitiesName]; }
        }

        #endregion ParameterProperties

        #region Properties

        public IntValue Seed => SeedParameter.Value;

        public BoolValue SetSeedRandomly => SetSeedRandomlyParameter.Value;

        public IntValue PopulationSize => PopulationSizeParameter.Value;

        public PercentValue CrossoverProbability => CrossoverProbabilityParameter.Value;

        public DoubleValue CrossoverContiguity => CrossoverContiguityParameter.Value;

        public PercentValue MutationProbability => MutationProbabilityParameter.Value;

        public IntValue MaximumGenerations => MaximumGenerationsParameter.Value;

        public BoolValue DominateOnEqualQualities => DominateOnEqualQualitiesParameter.Value;

        public List<List<Solution>> Fronts { get; private set; }

        public List<ReferencePoint> ReferencePoints { get; private set; }

        // todo: create one property for the Generated Reference Points and one for the current
        // generations reference points

        #endregion Properties

        #region ResultsProperties

        public DoubleMatrix ResultsGeneratedReferencePoints
        {
            get { return (DoubleMatrix)Results[GeneratedReferencePointsResultName].Value; }
            set { Results[GeneratedReferencePointsResultName].Value = value; }
        }

        public DoubleMatrix ResultsSolutions
        {
            get { return (DoubleMatrix)Results[CurrentFrontResultName].Value; }
            set { Results[CurrentFrontResultName].Value = value; }
        }

        public IntValue ResultsCurrentGeneration
        {
            get { return (IntValue)Results[CurrentGenerationResultName].Value; }
            set { Results[CurrentGenerationResultName].Value = value; }
        }

        public DoubleValue ResultsGenerationalDistance
        {
            get { return (DoubleValue)Results[GenerationalDistanceResultName].Value;}
            set { Results[GenerationalDistanceResultName].Value = value; }
        }

        public DoubleValue ResultsInvertedGenerationalDistance
        {
            get { return (DoubleValue)Results[InvertedGenerationalDistanceResultName].Value; }
            set { Results[InvertedGenerationalDistanceResultName].Value = value; }
        }

        public ParetoFrontScatterPlot ResultsScatterPlot
        {
            get { return (ParetoFrontScatterPlot)Results[ScatterPlotResultName].Value; }
            set { Results[ScatterPlotResultName].Value = value; }
        }

        #endregion ResultsProperties

        #region Constructors

        public NSGA3() : base()
        {
            Parameters.Add(new FixedValueParameter<IntValue>(SeedName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
            Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
            Parameters.Add(new FixedValueParameter<IntValue>(PopulationSizeName, "The size of the population of Individuals.", new IntValue(200)));
            Parameters.Add(new FixedValueParameter<PercentValue>(CrossoverProbabilityName, "The probability that the crossover operator is applied on two parents.", new PercentValue(0.9)));
            Parameters.Add(new FixedValueParameter<DoubleValue>(CrossoverContiguityName, "The contiguity value for the Simulated Binary Crossover that specifies how close a child should be to its parents (larger value means closer). The value must be greater than or equal than 0. Typical values are in the range [2;5]."));
            Parameters.Add(new FixedValueParameter<PercentValue>(MutationProbabilityName, "The probability that the mutation operator is applied on a Individual.", new PercentValue(0.05)));
            Parameters.Add(new FixedValueParameter<IntValue>(MaximumGenerationsName, "The maximum number of generations which should be processed.", new IntValue(1000)));
            Parameters.Add(new FixedValueParameter<BoolValue>(DominateOnEqualQualitiesName, "Flag which determines wether Individuals with equal quality values should be treated as dominated.", new BoolValue(false)));
        }

        // Persistence uses this ctor to improve deserialization efficiency. If we would use the
        // default ctor instead this would completely initialize the object (e.g. creating
        // parameters) even though the data is later overwritten by the stored data.
        [StorableConstructor]
        public NSGA3(StorableConstructorFlag _) : base(_) { }

        // Each clonable item must have a cloning ctor (deep cloning, the cloner is used to handle
        // cyclic object references). Don't forget to call the cloning ctor of the base class
        public NSGA3(NSGA3 original, Cloner cloner) : base(original, cloner)
        {
            // todo: don't forget to clone storable fields
            random = cloner.Clone(original.random);
            solutions = new List<Solution>(original.solutions?.Select(cloner.Clone));
        }

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

        #endregion Constructors

        #region Initialization

        protected override void Initialize(CancellationToken cancellationToken)
        {
            base.Initialize(cancellationToken);

            int numberOfGeneratedReferencePoints = ReferencePoint.GetNumberOfGeneratedReferencePoints(NumberOfObjectives);
            int pop = ((numberOfGeneratedReferencePoints + 3) / 4) * 4;
            PopulationSize.Value = pop;
            InitResults();
            InitFields();
            InitReferencePoints();
            Analyze();
        }

        private void InitReferencePoints()
        {
            // Generate reference points and add them to results
            ReferencePoints = ReferencePoint.GenerateReferencePoints(random, NumberOfObjectives);
            ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(ReferencePoints);
        }

        private void InitFields()
        {
            random = new MersenneTwister();
            InitSolutions();
        }

        private void InitSolutions()
        {
            int minBound = 0;
            int maxBound = 1;

            // Initialise solutions
            solutions = new List<Solution>(PopulationSize.Value);
            for (int i = 0; i < PopulationSize.Value; i++)
            {
                RealVector randomRealVector = new RealVector(Problem.Encoding.Length, random, minBound, maxBound);

                solutions.Add(new Solution(randomRealVector));
                solutions[i].Fitness = Evaluate(solutions[i].Chromosome);
            }
        }

        private void InitResults()
        {
            Results.Add(new Result(GeneratedReferencePointsResultName, "The initially generated reference points", new DoubleMatrix()));
            Results.Add(new Result(CurrentFrontResultName, "The Pareto Front", new DoubleMatrix()));
            Results.Add(new Result(CurrentGenerationResultName, "The current generation", new IntValue(1)));
            Results.Add(new Result(GenerationalDistanceResultName, "The generational distance to an optimal pareto front defined in the Problem", new DoubleValue(double.NaN)));
            Results.Add(new Result(InvertedGenerationalDistanceResultName, "The inverted generational distance to an optimal pareto front defined in the Problem", new DoubleValue(double.NaN)));
            Results.Add(new Result(ScatterPlotResultName, "A scatterplot displaying the evaluated solutions and (if available) the analytically optimal front", new ParetoFrontScatterPlot()));

            var problem = Problem as MultiObjectiveTestFunctionProblem;
            if (problem == null) return;
            // todo: add BestKnownFront parameter
            ResultsScatterPlot = new ParetoFrontScatterPlot(new double[0][], new double[0][], problem.BestKnownFront.ToJaggedArray(), problem.Objectives, problem.ProblemSize);
        }

        #endregion Initialization

        #region Overriden Methods

        protected override void Run(CancellationToken cancellationToken)
        {
            while (ResultsCurrentGeneration.Value < MaximumGenerations.Value)
            {
                // create copies of generated reference points (to preserve the original ones for
                // the next generation) maybe todo: use cloner?

                try
                {
                    List<Solution> qt = Mutate(Recombine(solutions));
                    List<Solution> rt = Utility.Concat(solutions, qt);

                    solutions = NSGA3Selection.SelectSolutionsForNextGeneration(rt, GetCopyOfReferencePoints(), Problem.Maximization, random);

                    ResultsCurrentGeneration.Value++;
                    Analyze();
                }
                catch (Exception ex)
                {
                    throw new Exception($"Failed in generation {ResultsCurrentGeneration}", ex);
                }
            }
        }

        #endregion Overriden Methods

        #region Private Methods

        private List<ReferencePoint> GetCopyOfReferencePoints()
        {
            if (ReferencePoints == null) return null;

            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
            foreach (var referencePoint in ReferencePoints)
                referencePoints.Add(new ReferencePoint(referencePoint));

            return referencePoints;
        }

        private void Analyze()
        {
            ResultsScatterPlot = new ParetoFrontScatterPlot(solutions.Select(x => x.Fitness).ToArray(), solutions.Select(x => x.Chromosome.ToArray()).ToArray(), ResultsScatterPlot.ParetoFront, ResultsScatterPlot.Objectives, ResultsScatterPlot.ProblemSize);
            ResultsSolutions = solutions.Select(s => s.Chromosome.ToArray()).ToMatrix();

            var problem = Problem as MultiObjectiveTestFunctionProblem;
            if (problem == null) return;

            ResultsGenerationalDistance = new DoubleValue(problem.BestKnownFront != null ? GenerationalDistance.Calculate(solutions.Select(s => s.Fitness), problem.BestKnownFront.ToJaggedArray(), 1) : double.NaN);
            ResultsInvertedGenerationalDistance = new DoubleValue(problem.BestKnownFront != null ? InvertedGenerationalDistance.Calculate(solutions.Select(s => s.Fitness), problem.BestKnownFront.ToJaggedArray(), 1) : double.NaN);

            Problem.Analyze(
                solutions.Select(s => (Individual)new SingleEncodingIndividual(Problem.Encoding, new Scope { Variables = { new Variable(Problem.Encoding.Name, s.Chromosome) } })).ToArray(),
                solutions.Select(s => s.Fitness).ToArray(),
                Results,
                random
                );
        }

        /// <summary>
        /// Returns the fitness of the given <paramref name="chromosome" /> by applying the Evaluate
        /// method of the Problem.
        /// </summary>
        /// <param name="chromosome"></param>
        /// <returns></returns>
        private double[] Evaluate(RealVector chromosome)
        {
            return Problem.Evaluate(new SingleEncodingIndividual(Problem.Encoding, new Scope { Variables = { new Variable(Problem.Encoding.Name, chromosome) } }), random);
        }

        private List<Solution> Recombine(List<Solution> solutions)
        {
            List<Solution> childSolutions = new List<Solution>();

            for (int i = 0; i < solutions.Count; i += 2)
            {
                int parentIndex1 = random.Next(solutions.Count);
                int parentIndex2 = random.Next(solutions.Count);
                // ensure that the parents are not the same object
                if (parentIndex1 == parentIndex2) parentIndex2 = (parentIndex2 + 1) % solutions.Count;
                var parent1 = solutions[parentIndex1];
                var parent2 = solutions[parentIndex2];

                // Do crossover with crossoverProbabilty == 1 in order to guarantee that a crossover happens
                var children = SimulatedBinaryCrossover.Apply(random, Problem.Encoding.Bounds, parent1.Chromosome, parent2.Chromosome, 1);
                Debug.Assert(children != null);

                var child1 = new Solution(children.Item1);
                var child2 = new Solution(children.Item2);
                child1.Fitness = Evaluate(child1.Chromosome);
                child2.Fitness = Evaluate(child1.Chromosome);

                childSolutions.Add(child1);
                childSolutions.Add(child2);
            }

            return childSolutions;
        }

        private List<Solution> Mutate(List<Solution> solutions)
        {
            foreach (var solution in solutions)
            {
                UniformOnePositionManipulator.Apply(random, solution.Chromosome, Problem.Encoding.Bounds);
            }
            return solutions;
        }

        #endregion Private Methods
    }
}