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

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;

namespace HeuristicLab.Algorithms.NSGA3
{
    public class ReferencePoint : IDeepCloneable
    {
        #region Properties

        // The potentially associated solutions to this reference point and the distance to that solution
        private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();

        private readonly IRandom random;

        public double[] Values { get; }
        public int NumberOfDimensions => Values.Length;
        public int NumberOfAssociatedSolutions { get; set; } = 0;

        #endregion Properties

        #region Constructors

        public ReferencePoint(IRandom random, int numberOfDimensions)
        {
            this.random = random;
            Values = new double[numberOfDimensions];
        }

        public ReferencePoint(ReferencePoint other, Cloner cloner)
        {
            random = cloner.Clone(other.random);
            Values = new double[other.NumberOfDimensions];
            other.Values.CopyTo(Values, 0);
        }

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

        public object Clone()
        {
            return new Cloner().Clone(this);
        }

        #endregion Constructors

        #region Static methods

        /// <summary>
        /// Returns the number of reference points that would be created when using <see
        /// cref="GenerateReferencePoints(IRandom, int)" />.
        /// </summary>
        /// <param name="nDim"></param>
        /// <returns></returns>
        public static int GetNumberOfGeneratedReferencePoints(int nDim)
        {
            int outerDiv;
            int innerDiv;
            switch (nDim)
            {
                case 3:
                    outerDiv = 12;
                    innerDiv = 0;
                    break;

                case 5:
                    outerDiv = 6;
                    innerDiv = 0;
                    break;

                case 8:
                    outerDiv = 3;
                    innerDiv = 2;
                    break;

                case 10:
                    outerDiv = 3;
                    innerDiv = 2;
                    break;

                case 15:
                    outerDiv = 2;
                    innerDiv = 1;
                    break;

                default:
                    return -1;
            }

            return GetNumberOfGeneratedReferencePoints(nDim, outerDiv, innerDiv);
        }

        public static int GetNumberOfGeneratedReferencePoints(int nDim, int outerDiv, int innerDiv = 0)
        {
            int outerPoints = Utility.NCR(nDim + outerDiv - 1, outerDiv);
            int innerPoints = innerDiv == 0 ? 0 : Utility.NCR(nDim + innerDiv - 1, innerDiv);
            return outerPoints + innerPoints;
        }

        public static int GetPopulationSizeForReferencePoints(int referencePoints)
        {
            return (referencePoints + 3) / 4 * 4;
        }

        /// <summary>
        /// Generate reference points that are evenly distributed over a hyperplane with dimensions
        /// <paramref name="nDim" /> - 1 with the sum of the values in all dimensions being equal to
        /// 1 for each reference point. <paramref name="nDim" /> may only be one of {3, 5, 8, 10, 15}
        /// -&gt; The number of inner divisions and outer divisions are determined based on the
        /// values provided in the NSGA-III paper, chapter V: Results. If different dimensions are
        /// given, a NotSupportedException is thrown.
        /// </summary>
        /// <param name="random">
        /// The <see cref="IRandom" /> to give as a parameter to the ReferencePoint constructors.
        /// </param>
        /// <param name="nDim">The dimensionality of the Reference Points</param>
        /// <returns></returns>
        public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim)
        {
            List<ReferencePoint> referencePoints;
            switch (nDim)
            {
                case 3:
                    referencePoints = GenerateReferencePoints(random, nDim, 12, 0);
                    break;

                case 5:
                    referencePoints = GenerateReferencePoints(random, nDim, 6, 0);
                    break;

                case 8:
                    referencePoints = GenerateReferencePoints(random, nDim, 3, 2);
                    break;

                case 10:
                    referencePoints = GenerateReferencePoints(random, nDim, 3, 2);
                    break;

                case 15:
                    referencePoints = GenerateReferencePoints(random, nDim, 2, 1);
                    break;

                default:
                    throw new NotSupportedException("Only the reference points for 3, 5, 8, 10 or 15 dimensions can be created.");
            }

            return referencePoints;
        }

        /*
         * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
         * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
         */

        /// <summary>
        /// Generate reference points that are evenly distributed over a hyperplane with dimensions
        /// <paramref name="nDim" /> - 1 with the sum of the values in all dimensions being equal to
        /// 1 for each reference point.
        /// </summary>
        /// <param name="nDim">The number of dimensions for the reference points.</param>
        /// <param name="outerDiv">The number of divisions for the outer reference points</param>
        /// <returns>The generated reference points (Check Fig. 4 in NSGA-III paper).</returns>
        /// <param name="innerDiv">The number of divisions for the inner reference points</param>
        /// <returns>
        /// The generated reference points (Check Fig. 4 in NSGA-III paper). Set to 0, in order to
        /// not have inner reference points
        /// </returns>
        public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int nDim, int outerDiv, int innerDiv = 0)
        {
            if (nDim <= 0) throw new ArgumentException("nDim must be greater than 0");
            if (outerDiv <= 1) throw new ArgumentException("outerDiv must be greater than 1");

            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
            ReferencePoint refPoint = new ReferencePoint(random, nDim);
            GenerateRecursive(referencePoints, refPoint, nDim, outerDiv, outerDiv, 0);

            if (innerDiv > 0)
            {
                List<ReferencePoint> insideReferencePoints = new List<ReferencePoint>();
                GenerateRecursive(insideReferencePoints, refPoint, nDim, innerDiv, innerDiv, 0);

                double center = 1.0 / nDim;

                for (int i = 0; i < insideReferencePoints.Count; i++)
                {
                    for (int j = 0; j < insideReferencePoints[i].Values.Length; j++)
                    {
                        insideReferencePoints[i].Values[j] = (center + insideReferencePoints[i].Values[j]) / 2;
                    }
                    referencePoints.Add(insideReferencePoints[i]);
                }
            }

            return referencePoints;
        }

        /*
         * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
         * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
         */

        private static void GenerateRecursive(List<ReferencePoint> referencePoints, ReferencePoint refPoint, int numberOfObjectives, int left, int total, int element)
        {
            if (element == numberOfObjectives - 1)
            {
                refPoint.Values[element] = ((double)left) / total;
                var newRefPoint = (ReferencePoint)refPoint.Clone();
                referencePoints.Add(newRefPoint);
            }
            else
            {
                for (int i = 0; i <= left; i++)
                {
                    refPoint.Values[element] = (double)i / total;
                    GenerateRecursive(referencePoints, refPoint, numberOfObjectives, left - i, total, element + 1);
                }
            }
        }

        #endregion Static methods

        public void AddPotentialAssociatedSolution(Solution s, double distance)
        {
            if (potentialAssociatedSolutions.ContainsKey(s))
                throw new InvalidOperationException("Given solution was already added as a potential solution");

            potentialAssociatedSolutions.Add(s, distance);
        }

        public void RemovePotentialAssociatedSolution(Solution s)
        {
            potentialAssociatedSolutions.Remove(s);
        }

        public bool HasPotentialMember()
        {
            return potentialAssociatedSolutions.Any();
        }

        internal Solution FindClosestMember()
        {
            if (!potentialAssociatedSolutions.Any())
                throw new InvalidOperationException("No potential members exist");

            return Utility.ArgMin(pair => pair.Value, potentialAssociatedSolutions).Key;
        }

        internal Solution RandomMember()
        {
            if (!potentialAssociatedSolutions.Any())
                throw new InvalidOperationException("No potential members exist");

            return potentialAssociatedSolutions.Keys.ElementAt(random.Next(potentialAssociatedSolutions.Count));
        }
    }
}