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

using System;
using System.Collections.Generic;
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.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; // todo: make true

        #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; }
        }

        #endregion ProblemProperties

        #region Storable fields

        [Storable]
        private IRandom random;

        [Storable]
        private Solution[] solutions;

        [Storable]
        private List<ReferencePoint> referencePoints;

        #endregion Storable fields

        #region ParameterAndResultsNames

        // Parameter Names

        private const string SeedName = "Seed";
        private const string SetSeedRandomlyName = "SetSeedRandomly";
        private const string PopulationSizeName = "PopulationSize";
        private const string CrossoverProbabilityName = "CrossOverProbability";
        private const string MutationProbabilityName = "MutationProbability";
        private const string MaximumGenerationsName = "MaximumGenerations";
        private const string DominateOnEqualQualitiesName = "DominateOnEqualQualities";

        // Results Names

        private const string GeneratedReferencePointsResultName = "Generated Reference Points";
        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<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 PercentValue MutationProbability => MutationProbabilityParameter.Value;

        public IntValue MaximumGenerations => MaximumGenerationsParameter.Value;

        public BoolValue DominateOnEqualQualities => DominateOnEqualQualitiesParameter.Value;

        #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; }
        }

        #endregion ResultsProperties

        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(100)));
            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<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 = original.solutions?.Select(cloner.Clone).ToArray();
        }

        #region Overriden Methods

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

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

            InitFields();
            InitReferencePoints();
            InitResults();
            Analyze();
        }

        protected override void Run(CancellationToken cancellationToken)
        {
            throw new NotImplementedException();
        }

        #endregion Overriden Methods

        #region Private Methods

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

        private void InitSolutions()
        {
            int minBound = 0; // todo: find min inside Problem.Encoding
            int maxBound = 1; // todo: find max inside Problem.Encoding

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

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

        private void InitReferencePoints()
        {
            // Generate reference points and add them to results
            int nDiv = 5; // todo: figure out the correct number of divisions
            referencePoints = ReferencePoint.GenerateReferencePoints(Problem.Encoding.Length, nDiv);
            ResultsGeneratedReferencePoints = Utility.ConvertToDoubleMatrix(referencePoints);
        }

        private void InitResults()
        {
            Results.Add(new Result(GeneratedReferencePointsResultName, "The initially generated reference points", Utility.ConvertToDoubleMatrix(referencePoints)));
            Results.Add(new Result(CurrentFrontResultName, "The Pareto Front", new DoubleMatrix()));
        }

        private void Analyze()
        {
            ResultsSolutions = solutions.Select(s => s.Chromosome.ToArray()).ToMatrix();
            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);
        }

        #endregion Private Methods
    }
}