Changeset 17616


Ignore:
Timestamp:
06/21/20 16:34:08 (3 weeks ago)
Author:
dleko
Message:

#2825 Implement the first part of NSGA3.
Solutions are saved in a List.
Minor changes in Utility.cs.

Location:
branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/NSGA3.cs

    r17615 r17616  
    2525    public class NSGA3 : BasicAlgorithm
    2626    {
    27         public override bool SupportsPause => false; // todo: make true
     27        private const double EPSILON = 10e-6; // a tiny number that is greater than 0
     28
     29        public override bool SupportsPause => false;
    2830
    2931        #region ProblemProperties
     
    4850
    4951        [Storable]
    50         private Solution[] solutions;
     52        private List<Solution> solutions;
     53
     54        [Storable]
     55        private List<List<Solution>> fronts;
    5156
    5257        [Storable]
     
    170175            // todo: don't forget to clone storable fields
    171176            random = cloner.Clone(original.random);
    172             solutions = original.solutions?.Select(cloner.Clone).ToArray();
     177            solutions = new List<Solution>(original.solutions?.Select(cloner.Clone));
    173178        }
    174179
     
    192197        protected override void Run(CancellationToken cancellationToken)
    193198        {
    194             throw new NotImplementedException();
     199            referencePoints = new List<ReferencePoint>(); // todo: use existing list of reference points
     200            for (int iteration = 0; iteration < MaximumGenerations.Value; iteration++)
     201                ToNextGeneration();
    195202        }
    196203
     
    207214        private void InitSolutions()
    208215        {
    209             int minBound = 0; // todo: find min inside Problem.Encoding
    210             int maxBound = 1; // todo: find max inside Problem.Encoding
     216            int minBound = 0;
     217            int maxBound = 1;
    211218
    212219            // Initialise solutions
    213             solutions = new Solution[PopulationSize.Value];
     220            solutions = new List<Solution>(PopulationSize.Value);
    214221            for (int i = 0; i < PopulationSize.Value; i++)
    215222            {
    216223                RealVector randomRealVector = new RealVector(Problem.Encoding.Length, random, minBound, maxBound);
    217224
    218                 solutions[i] = new Solution(StorableConstructorFlag.Default)
     225                solutions.Add(new Solution(StorableConstructorFlag.Default)
    219226                {
    220227                    Chromosome = randomRealVector
    221                 };
     228                });
    222229                solutions[i].Fitness = Evaluate(solutions[i].Chromosome);
    223230            }
     
    260267        }
    261268
     269        private List<Solution> ToNextGeneration()
     270        {
     271            List<Solution> st = new List<Solution>();
     272            List<Solution> qt = Mutate(Recombine(solutions));
     273            List<Solution> rt = Utility.Concat(solutions, qt);
     274            List<Solution> nextGeneration;
     275
     276            // Do non-dominated sort
     277            var qualities = Utility.ToFitnessMatrix(solutions);
     278            // compute the pareto fronts using the DominationCalculator and discard the qualities
     279            // part in the inner tuples
     280            fronts = DominationCalculator<Solution>.CalculateAllParetoFronts(rt.ToArray(), qualities, Problem.Maximization, out int[] rank, true)
     281                .Select(list => new List<Solution>(list.Select(pair => pair.Item1))).ToList();
     282
     283            int i = 0;
     284            List<Solution> lf = null; // last front to be included
     285            while (i < fronts.Count && st.Count < PopulationSize.Value)
     286            {
     287                lf = fronts[i];
     288                st = Utility.Concat(st, lf);
     289                i++;
     290            }
     291
     292            if (st.Count == PopulationSize.Value) // no selection needs to be done
     293                nextGeneration = st;
     294            else
     295            {
     296                int l = i - 1;
     297                nextGeneration = new List<Solution>();
     298                for (int f = 0; f < l; f++)
     299                    nextGeneration = Utility.Concat(nextGeneration, fronts[f]);
     300                Normalize(st);
     301                Associate();
     302                throw new NotImplementedException();
     303            }
     304
     305            throw new NotImplementedException();
     306        }
     307
     308        private void Normalize(List<Solution> population)
     309        {
     310            // Find the ideal point
     311            double[] idealPoint = new double[Problem.Encoding.Length];
     312            for (int j = 0; j < Problem.Encoding.Length; j++)
     313            {
     314                // Compute ideal point
     315                idealPoint[j] = Utility.Min(s => s.Fitness[j], solutions);
     316
     317                // Translate objectives
     318                foreach (var solution in solutions)
     319                    solution.Fitness[j] -= idealPoint[j];
     320            }
     321
     322            // Find the extreme points
     323            Solution[] extremePoints = new Solution[Problem.Encoding.Length];
     324            for (int j = 0; j < Problem.Encoding.Length; j++)
     325            {
     326                // Compute extreme points
     327                double[] weights = new double[Problem.Encoding.Length];
     328                for (int i = 0; i < Problem.Encoding.Length; i++) weights[i] = EPSILON;
     329                weights[j] = 1;
     330                Func<Solution, double> func = s => ASF(s.Fitness, weights);
     331                extremePoints[j] = Utility.ArgMin(func, solutions);
     332            }
     333
     334            // Compute intercepts
     335            List<double> intercepts = GetIntercepts(extremePoints.ToList());
     336
     337            // Normalize objectives
     338            NormalizeObjectives(intercepts, idealPoint);
     339
     340            // Associate reference points to solutions
     341            Associate();
     342        }
     343
     344        private void NormalizeObjectives(List<double> intercepts, double[] idealPoint)
     345        {
     346            for (int f = 0; f < fronts.Count; f++)
     347            {
     348                foreach (var solution in fronts[f])
     349                {
     350                    for (int i = 0; i < Problem.Encoding.Length; i++)
     351                    {
     352                        if (Math.Abs(intercepts[i] - idealPoint[i]) > EPSILON)
     353                        {
     354                            solution.Fitness[i] = solution.Fitness[i] / (intercepts[i] - idealPoint[i]);
     355                        }
     356                        else
     357                        {
     358                            solution.Fitness[i] = solution.Fitness[i] / EPSILON;
     359                        }
     360                    }
     361                }
     362            }
     363        }
     364
     365        private void Associate()
     366        {
     367            for (int f = 0; f < fronts.Count; f++)
     368            {
     369                foreach (var solution in fronts[f])
     370                {
     371                    // find reference point for which the perpendicular distance to the current
     372                    // solution is the lowest
     373                    var rpAndDist = Utility.MinArgMin(rp => GetPerpendicularDistance(rp.Values, solution.Fitness), referencePoints);
     374
     375                    //// todo: use ArgMin here
     376                    //int min_rp = -1;
     377                    //double min_dist = double.MaxValue;
     378                    //for (int r = 0; r < referencePoints.Count; r++)
     379                    //{
     380                    //    double d = GetPerpendicularDistance(referencePoints[r].Values, solution.Fitness);
     381                    //    if (d < min_dist)
     382                    //    {
     383                    //        min_dist = d;
     384                    //        min_rp = r;
     385                    //    }
     386                    //}
     387                    if (f + 1 != fronts.Count)
     388                    {
     389                        // Todo: Add member for reference point on index min_rp
     390                        throw new NotImplementedException();
     391                    }
     392                    else
     393                    {
     394                        // Todo: Add potential member for reference point on index min_rp
     395                        throw new NotImplementedException();
     396                    }
     397                }
     398            }
     399        }
     400
     401        private double GetPerpendicularDistance(double[] values, double[] fitness)
     402        {
     403            double numerator = 0;
     404            double denominator = 0;
     405            for (int i = 0; i < values.Length; i++)
     406            {
     407                numerator += values[i] * fitness[i];
     408                denominator += Math.Pow(values[i], 2);
     409            }
     410            double k = numerator / denominator;
     411
     412            double d = 0;
     413            for (int i = 0; i < values.Length; i++)
     414            {
     415                d += Math.Pow(k * values[i] - fitness[i], 2);
     416            }
     417            return Math.Sqrt(d);
     418        }
     419
     420        private double ASF(double[] x, double[] weight)
     421        {
     422            List<int> dimensions = new List<int>();
     423            for (int i = 0; i < Problem.Encoding.Length; i++) dimensions.Add(i);
     424            Func<int, double> f = dim => x[dim] / weight[dim];
     425            return Utility.Max(f, dimensions);
     426        }
     427
     428        private List<double> GetIntercepts(List<Solution> extremePoints)
     429        {
     430            // Check whether there are duplicate extreme points. This might happen but the original
     431            // paper does not mention how to deal with it.
     432            bool duplicate = false;
     433            for (int i = 0; !duplicate && i < extremePoints.Count; i++)
     434            {
     435                for (int j = i + 1; !duplicate && j < extremePoints.Count; j++)
     436                {
     437                    // maybe todo: override Equals method of solution?
     438                    duplicate = extremePoints[i].Equals(extremePoints[j]);
     439                }
     440            }
     441
     442            List<double> intercepts = new List<double>();
     443
     444            if (duplicate)
     445            { // cannot construct the unique hyperplane (this is a casual method to deal with the condition)
     446                for (int f = 0; f < Problem.Encoding.Length; f++)
     447                {
     448                    // extreme_points[f] stands for the individual with the largest value of
     449                    // objective f
     450                    intercepts.Add(extremePoints[f].Fitness[f]);
     451                }
     452            }
     453            else
     454            {
     455                // Find the equation of the hyperplane
     456                List<double> b = new List<double>(); //(pop[0].objs().size(), 1.0);
     457                for (int i = 0; i < Problem.Encoding.Length; i++)
     458                {
     459                    b.Add(1.0);
     460                }
     461
     462                List<List<double>> a = new List<List<double>>();
     463                foreach (Solution s in extremePoints)
     464                {
     465                    List<double> aux = new List<double>();
     466                    for (int i = 0; i < Problem.Encoding.Length; i++)
     467                        aux.Add(s.Fitness[i]);
     468                    a.Add(aux);
     469                }
     470                List<double> x = GaussianElimination(a, b);
     471
     472                // Find intercepts
     473                for (int f = 0; f < Problem.Encoding.Length; f++)
     474                {
     475                    intercepts.Add(1.0 / x[f]);
     476                }
     477            }
     478
     479            return intercepts;
     480        }
     481
     482        private List<double> GaussianElimination(List<List<double>> a, List<double> b)
     483        {
     484            List<double> x = new List<double>();
     485
     486            int n = a.Count;
     487            for (int i = 0; i < n; i++)
     488                a[i].Add(b[i]);
     489
     490            for (int @base = 0; @base < n - 1; @base++)
     491                for (int target = @base + 1; target < n; target++)
     492                {
     493                    double ratio = a[target][@base] / a[@base][@base];
     494                    for (int term = 0; term < a[@base].Count; term++)
     495                        a[target][term] = a[target][term] - a[@base][term] * ratio;
     496                }
     497
     498            for (int i = 0; i < n; i++)
     499                x.Add(0.0);
     500
     501            for (int i = n - 1; i >= 0; i--)
     502            {
     503                for (int known = i + 1; known < n; known++)
     504                    a[i][n] = a[i][n] - a[i][known] * x[known];
     505                x[i] = a[i][n] / a[i][i];
     506            }
     507
     508            return x;
     509        }
     510
     511        private List<Solution> Recombine(List<Solution> solutions)
     512        {
     513            throw new NotImplementedException();
     514        }
     515
     516        private List<Solution> Mutate(List<Solution> solutions)
     517        {
     518            throw new NotImplementedException();
     519        }
     520
    262521        #endregion Private Methods
    263522    }
  • branches/2825-NSGA3/HeuristicLab.Algorithms.NSGA3/3.3/Utility.cs

    r17559 r17616  
    88    internal static class Utility
    99    {
     10        internal static List<T> Concat<T>(List<T> list1, List<T> list2)
     11        {
     12            List<T> resultList = new List<T>(list1.Count + list2.Count);
     13
     14            resultList.AddRange(list1);
     15            resultList.AddRange(list2);
     16
     17            return resultList;
     18        }
     19
    1020        /// <summary>
    1121        /// Returns the number of possible combinations of size <paramref name="r" /> from a set of
     
    4252        }
    4353
    44         internal static double[,] ToArray(List<ReferencePoint> referencePoints)
     54        internal static double[][] ToFitnessMatrix(this List<Solution> solutions)
     55        {
     56            double[][] data = new double[solutions.Count][];
     57            for (int i = 0; i < solutions.Count; i++)
     58            {
     59                Solution solution = solutions[i];
     60                data[i] = new double[solution.Fitness.Length];
     61                for (int j = 0; j < solution.Fitness.Length; j++)
     62                {
     63                    data[i][j] = solution.Fitness[j];
     64                }
     65            }
     66
     67            return data;
     68        }
     69
     70        internal static DoubleMatrix ToMatrix(this IEnumerable<IReadOnlyList<double>> data)
     71        {
     72            var d2 = data.ToArray();
     73            var mat = new DoubleMatrix(d2.Length, d2[0].Count);
     74            for (var i = 0; i < mat.Rows; i++)
     75                for (var j = 0; j < mat.Columns; j++)
     76                    mat[i, j] = d2[i][j];
     77            return mat;
     78        }
     79
     80        private static double[,] ToArray(List<ReferencePoint> referencePoints)
    4581        {
    4682            if (referencePoints == null || !referencePoints.Any()) throw new ArgumentException($"{nameof(referencePoints)} is null or empty");
     
    5692        }
    5793
    58         internal static DoubleMatrix ToMatrix(this IEnumerable<IReadOnlyList<double>> data)
     94        internal static TOut Min<TIn, TOut>(Func<TIn, TOut> func, IEnumerable<TIn> inputs) where TOut : IComparable
    5995        {
    60             var d2 = data.ToArray();
    61             var mat = new DoubleMatrix(d2.Length, d2[0].Count);
    62             for (var i = 0; i < mat.Rows; i++)
    63                 for (var j = 0; j < mat.Columns; j++)
    64                     mat[i, j] = d2[i][j];
    65             return mat;
     96            //var it = inputs.GetEnumerator();
     97            //it.MoveNext();
     98            //var minValue = func(it.Current);
     99            //while (it.MoveNext())
     100            //{
     101            //    var currentValue = func(it.Current);
     102            //    if (minValue.CompareTo(currentValue) > 0) minValue = currentValue;
     103            //}
     104
     105            //return minValue;
     106            return MinArgMin(func, inputs).Item2;
     107        }
     108
     109        internal static TIn ArgMin<TIn, TOut>(Func<TIn, TOut> func, IEnumerable<TIn> inputs) where TOut : IComparable
     110        {
     111            return MinArgMin(func, inputs).Item1;
     112        }
     113
     114        internal static Tuple<TIn, TOut> MinArgMin<TIn, TOut>(Func<TIn, TOut> func, IEnumerable<TIn> inputs) where TOut : IComparable
     115        {
     116            var it = inputs.GetEnumerator();
     117            it.MoveNext();
     118            var minArg = it.Current;
     119            var minValue = func(it.Current);
     120            while (it.MoveNext())
     121            {
     122                var currentArg = it.Current;
     123                var currentValue = func(it.Current);
     124                if (minValue.CompareTo(currentValue) > 0)
     125                {
     126                    minArg = currentArg;
     127                    minValue = currentValue;
     128                }
     129            }
     130
     131            return Tuple.Create(minArg, minValue);
     132        }
     133
     134        internal static TOut Max<TIn, TOut>(Func<TIn, TOut> func, IEnumerable<TIn> inputs) where TOut : IComparable
     135        {
     136            //var it = inputs.GetEnumerator();
     137            //it.MoveNext();
     138            //var maxValue = func(it.Current);
     139            //while (it.MoveNext())
     140            //{
     141            //    var currentValue = func(it.Current);
     142            //    if (maxValue.CompareTo(currentValue) < 0) maxValue = currentValue;
     143            //}
     144
     145            //return maxValue;
     146            return MaxArgMax(func, inputs).Item2;
     147        }
     148
     149        internal static TIn ArgMax<TIn, TOut>(Func<TIn, TOut> func, IEnumerable<TIn> inputs) where TOut : IComparable
     150        {
     151            return MaxArgMax(func, inputs).Item1;
     152        }
     153
     154        internal static Tuple<TIn, TOut> MaxArgMax<TIn, TOut>(Func<TIn, TOut> func, IEnumerable<TIn> inputs) where TOut : IComparable
     155        {
     156            var it = inputs.GetEnumerator();
     157            it.MoveNext();
     158            var maxArg = it.Current;
     159            var maxValue = func(it.Current);
     160            while (it.MoveNext())
     161            {
     162                var currentArg = it.Current;
     163                var currentValue = func(it.Current);
     164                if (maxValue.CompareTo(currentValue) < 0)
     165                {
     166                    maxArg = currentArg;
     167                    maxValue = currentValue;
     168                }
     169            }
     170
     171            return Tuple.Create(maxArg, maxValue);
    66172        }
    67173    }
Note: See TracChangeset for help on using the changeset viewer.