Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17707 was 17707, checked in by dleko, 4 years ago

#2825 Minor refactoring.

File size: 8.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using HeuristicLab.Common;
5using HeuristicLab.Core;
6
7namespace HeuristicLab.Algorithms.NSGA3
8{
9    public class ReferencePoint : IDeepCloneable
10    {
11        #region Properties
12
13        // The potentially associated solutions to this reference point and the distance to that solution
14        private readonly Dictionary<Solution, double> potentialAssociatedSolutions = new Dictionary<Solution, double>();
15
16        private readonly IRandom random;
17
18        public double[] Values { get; }
19        public int Objectives => Values.Length;
20        public int NumberOfAssociatedSolutions { get; set; } = 0;
21
22        #endregion Properties
23
24        #region Constructors
25
26        public ReferencePoint(IRandom random, int obj)
27        {
28            this.random = random;
29            Values = new double[obj];
30        }
31
32        public ReferencePoint(ReferencePoint other, Cloner cloner)
33        {
34            random = cloner.Clone(other.random);
35            Values = new double[other.Objectives];
36            other.Values.CopyTo(Values, 0);
37        }
38
39        public IDeepCloneable Clone(Cloner cloner)
40        {
41            return new ReferencePoint(this, cloner);
42        }
43
44        public object Clone()
45        {
46            return new Cloner().Clone(this);
47        }
48
49        #endregion Constructors
50
51        #region Static methods
52
53        public static Tuple<int, int> GetDivisions(int obj)
54        {
55            switch (obj)
56            {
57                case 3:
58                    return Tuple.Create(12, 0);
59
60                case 5:
61                    return Tuple.Create(6, 0);
62
63                case 8:
64                    return Tuple.Create(3, 2);
65
66                case 10:
67                    return Tuple.Create(3, 2);
68
69                case 15:
70                    return Tuple.Create(2, 1);
71
72                default:
73                    return null;
74            }
75        }
76
77        /// <summary>
78        /// Returns the number of reference points that would be created when using <see
79        /// cref="GenerateReferencePoints(IRandom, int)" />.
80        /// </summary>
81        /// <param name="obj"></param>
82        /// <returns></returns>
83        public static int GetNumberOfGeneratedReferencePoints(int obj)
84        {
85            Tuple<int, int> division = GetDivisions(obj);
86            if (division == null) return -1;
87
88            return GetNumberOfGeneratedReferencePoints(obj, division.Item1, division.Item2);
89        }
90
91        public static int GetNumberOfGeneratedReferencePoints(int obj, int outerDiv, int innerDiv = 0)
92        {
93            int outerPoints = Utility.NCR(obj + outerDiv - 1, outerDiv);
94            int innerPoints = innerDiv == 0 ? 0 : Utility.NCR(obj + innerDiv - 1, innerDiv);
95            return outerPoints + innerPoints;
96        }
97
98        public static int GetPopulationSizeForReferencePoints(int referencePoints)
99        {
100            return (referencePoints + 3) / 4 * 4;
101        }
102
103        /// <summary>
104        /// Generate reference points that are evenly distributed over a hyperplane with dimensions
105        /// <paramref name="obj" /> - 1 with the sum of the values in all dimensions being equal to
106        /// 1 for each reference point. <paramref name="obj" /> may only be one of {3, 5, 8, 10, 15}
107        /// -&gt; The number of inner divisions and outer divisions are determined based on the
108        /// values provided in the NSGA-III paper, chapter V: Results. If different dimensions are
109        /// given, a NotSupportedException is thrown.
110        /// </summary>
111        /// <param name="random">
112        /// The <see cref="IRandom" /> to give as a parameter to the ReferencePoint constructors.
113        /// </param>
114        /// <param name="obj">The dimensionality of the Reference Points</param>
115        /// <returns></returns>
116        public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int obj)
117        {
118            Tuple<int, int> divisions = GetDivisions(obj);
119
120            if (divisions == null) return null;
121            return GenerateReferencePoints(random, obj, divisions.Item1, divisions.Item2);
122        }
123
124        /*
125         * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
126         * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
127         */
128
129        /// <summary>
130        /// Generate reference points that are evenly distributed over a hyperplane with dimensions
131        /// <paramref name="obj" /> - 1 with the sum of the values in all dimensions being equal to
132        /// 1 for each reference point.
133        /// </summary>
134        /// <param name="obj">The number of dimensions for the reference points.</param>
135        /// <param name="outerDiv">The number of divisions for the outer reference points</param>
136        /// <returns>The generated reference points (Check Fig. 4 in NSGA-III paper).</returns>
137        /// <param name="innerDiv">The number of divisions for the inner reference points</param>
138        /// <returns>
139        /// The generated reference points (Check Fig. 4 in NSGA-III paper). Set to 0, in order to
140        /// not have inner reference points
141        /// </returns>
142        public static List<ReferencePoint> GenerateReferencePoints(IRandom random, int obj, int outerDiv, int innerDiv = 0)
143        {
144            if (obj <= 0) throw new ArgumentException("obj must be greater than 0");
145            if (outerDiv <= 1) throw new ArgumentException("outerDiv must be greater than 1");
146
147            List<ReferencePoint> referencePoints = new List<ReferencePoint>();
148            ReferencePoint refPoint = new ReferencePoint(random, obj);
149            GenerateRecursive(referencePoints, refPoint, obj, outerDiv, outerDiv, 0);
150
151            if (innerDiv > 0)
152            {
153                List<ReferencePoint> insideReferencePoints = new List<ReferencePoint>();
154                GenerateRecursive(insideReferencePoints, refPoint, obj, innerDiv, innerDiv, 0);
155
156                double center = 1.0 / obj;
157
158                for (int i = 0; i < insideReferencePoints.Count; i++)
159                {
160                    for (int j = 0; j < insideReferencePoints[i].Values.Length; j++)
161                    {
162                        insideReferencePoints[i].Values[j] = (center + insideReferencePoints[i].Values[j]) / 2;
163                    }
164                    referencePoints.Add(insideReferencePoints[i]);
165                }
166            }
167
168            return referencePoints;
169        }
170
171        /*
172         * This method is based on Tsung-Che Chiang's NSGA-III implementation (version 1.20)
173         * http://web.ntnu.edu.tw/~tcchiang/publications/nsga3cpp/nsga3cpp.htm
174         */
175
176        private static void GenerateRecursive(List<ReferencePoint> referencePoints, ReferencePoint refPoint, int numberOfObjectives, int left, int total, int element)
177        {
178            if (element == numberOfObjectives - 1)
179            {
180                refPoint.Values[element] = ((double)left) / total;
181                var newRefPoint = (ReferencePoint)refPoint.Clone();
182                referencePoints.Add(newRefPoint);
183            }
184            else
185            {
186                for (int i = 0; i <= left; i++)
187                {
188                    refPoint.Values[element] = (double)i / total;
189                    GenerateRecursive(referencePoints, refPoint, numberOfObjectives, left - i, total, element + 1);
190                }
191            }
192        }
193
194        #endregion Static methods
195
196        public void AddPotentialAssociatedSolution(Solution s, double distance)
197        {
198            if (potentialAssociatedSolutions.ContainsKey(s))
199                throw new InvalidOperationException("Given solution was already added as a potential solution");
200
201            potentialAssociatedSolutions.Add(s, distance);
202        }
203
204        public void RemovePotentialAssociatedSolution(Solution s)
205        {
206            potentialAssociatedSolutions.Remove(s);
207        }
208
209        public bool HasPotentialMember()
210        {
211            return potentialAssociatedSolutions.Any();
212        }
213
214        internal Solution FindClosestMember()
215        {
216            if (!potentialAssociatedSolutions.Any())
217                throw new InvalidOperationException("No potential members exist");
218
219            return Utility.ArgMin(pair => pair.Value, potentialAssociatedSolutions).Key;
220        }
221
222        internal Solution RandomMember()
223        {
224            if (!potentialAssociatedSolutions.Any())
225                throw new InvalidOperationException("No potential members exist");
226
227            return potentialAssociatedSolutions.Keys.ElementAt(random.Next(potentialAssociatedSolutions.Count));
228        }
229    }
230}
Note: See TracBrowser for help on using the repository browser.