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

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

namespace HeuristicLab.Algorithms.NSGA3
{
    [StorableType("5026513A-F3C7-4A85-95D6-82B5B376E900")]
    public class ReferencePoint : IDeepCloneable
    {
        #region Properties

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

        [Storable]
        private IRandom random;

        [Storable]
        public double[] Values { get; set; }

        [Storable]
        public int NumberOfAssociatedSolutions { get; set; } = 0;

        #endregion Properties

        #region Constructors

        [StorableConstructor]
        public ReferencePoint(StorableConstructorFlag _) { }

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

        public ReferencePoint(ReferencePoint other, Cloner cloner)
        {
            random = cloner.Clone(other.random);
            Values = new double[other.Values.Length];
            Array.Copy(other.Values, Values, Values.Length);
        }

        public ReferencePoint(ReferencePoint other)
        {
            random = other.random;
            Values = new double[other.Values.Length];
            Array.Copy(other.Values, Values, Values.Length);
        }

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

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

        #endregion Constructors

        #region Static methods

        public static Tuple<int, int> GetDivisions(int obj)
        {
            switch (obj)
            {
                case 3:
                    return Tuple.Create(12, 0);

                case 5:
                    return Tuple.Create(6, 0);

                case 8:
                    return Tuple.Create(3, 2);

                case 10:
                    return Tuple.Create(3, 2);

                case 15:
                    return Tuple.Create(2, 1);

                default:
                    return null;
            }
        }

        /// <summary>
        /// Returns the number of reference points that would be created when using <see
        /// cref="GenerateReferencePoints(IRandom, int)" />.
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public static int GetNumberOfGeneratedReferencePoints(int obj)
        {
            Tuple<int, int> division = GetDivisions(obj);
            if (division == null) return -1;

            return GetNumberOfGeneratedReferencePoints(obj, division.Item1, division.Item2);
        }

        public static int GetNumberOfGeneratedReferencePoints(int obj, int outerDiv, int innerDiv = 0)
        {
            int outerPoints = Utility.NCR(obj + outerDiv - 1, outerDiv);
            int innerPoints = innerDiv == 0 ? 0 : Utility.NCR(obj + 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="obj" /> - 1 with the sum of the values in all dimensions being equal to
        /// 1 for each reference point. <paramref name="obj" /> 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="obj">The dimensionality of the Reference Points</param>
        /// <returns></returns>
        public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int obj)
        {
            Tuple<int, int> divisions = GetDivisions(obj);

            if (divisions == null) return null;
            return GenerateReferencePoints(random, obj, divisions.Item1, divisions.Item2);
        }

        /*
         * 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="obj" /> - 1 with the sum of the values in all dimensions being equal to
        /// 1 for each reference point.
        /// </summary>
        /// <param name="obj">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 obj, int outerDiv, int innerDiv = 0)
        {
            if (obj <= 0) throw new ArgumentException("obj 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, obj);
            GenerateRecursive(referencePoints, refPoint, obj, outerDiv, outerDiv, 0);

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

                double center = 1.0 / obj;

                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();
        }

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

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

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

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