I'm finding difficulty in computing the extreme points in NSGA-III. Can anyone help?
Basically you are computing extreme points in an N-dimensional space.
N can be very large. It's going to be a polyhedral convexity method you want to consider: you form a polygon/polyhedron with points M(i1) M(i2)... M(in). A point M will be either on the interior of the convex shape built so far, or outside. Then M is either in the interior and not extreme, or if it is on the exterior and is added to the convex hull.
You see the sort of algorithm?
Now, get more familiar with this N dimensional strategy by looking at N=1:
You have points x(i) on a line. You look for the extremes.
One possible way is to start from one point say x(0) and grow an interval I(j) containing it: if x(j+1) is in the interior of I(j), keep I(j) as your I(j+1). Otherwise x(j+1) becomes a new extreme point (either lower or upper) with the other extremity of I(j) becoming the other extremity of intervalI(j+1).
Easy? Yes, but you can generalise.
In your kitchen or bathroom or elsewhere where you live, you may have a tiling.
Now go for dimension N=2, take a tile, as your I(0) and aggregate border tiles of a growing connected shape around I(0), with an algorithm as the one above. Then you get to a maximum shape, which is a convex polygon formed of the extreme points of your tiling.
It is an easy matter to generalise the algorithm for any dimension N.
Careful on how it terminates: you could end up in a local extremum instead of a global extremum shape.
Imagine you blow air in a spherical balloon inside a cube... You want the cube as the border, but the spherical shape limits your growth.... You only will get the largest sphere included.
Of course, there are techniques to get off from a local optimum. In simulation, simulated annealing was a good way. Look it up if needed.
I hope that this practical hands-on geometric approach helps you develop algorithms for your particular problem
@ Renaud Di Francesco Thank you very much Sir for describing the algorithm in an easy manner.
@Renaud Di Francesco Would u please explain what are the values of weights w_g in the denominator of equation (5) in the uploaded file.
Explanation of formula (6)? f' is not a real derivative, but a difference in values of f, to get to a derivative estimate, you need to divide the function difference by the argument difference
- Badges
- Science topic
- Similar topics
- Computer Science
- Computing