Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2825 Be able to copy and store NSGA3 executions.

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