Hi Ronan, Please ignore my last post. I misunderstood (got a little mixed up when you were talking about bits) what the issue was, but after reading a little more carefully I see where your challenge is. Some of the points in the algorithm I showed you before will still be valid but in general here are a few points.
>From an algorithmic standpoint, you don't actually have to check all points against the all points on the frontier to determine if it is on the frontier or not. The key to doing this is to make sure your current frontier is sorted lexicographically (from best to worst) on each objective. After that only you will need to take your current point and find where it falls within the sorted frontier. Only points that are "above" it can actually dominate the point you're looking to add. So you only need to check the points above it in the current Pareto frontier. You should check the points above it in reverse order as those are the points that most likely to dominate your current point first. Of course if any one of those points points dominates your current point you can stop, as that point is not on the Pareto frontier. If you find that no point above the point you're looking at dominates it, then you know that point is a part of the Pareto frontier. What you need to do now is start to look at the points "below" the point you're adding to see if they are dominated by your current point. You can early exit from this as soon as you find a point that is not dominated by your new point, because all points following it will also not be dominated by it. Then you can remove all points your new point dominates from the Pareto frontier. The result is a new Pareto frontier with only non-dominated points on it. That is a lot to say, but the pseudo steps look a little bit like this: 1) Find position for the new point where it would be placed if sorted into the current front. (I'd use a binary search for this at first thought) 2) For each point "above" it in the frontier, from last to first, check to see if it is dominated. If a point dominates the new point exit. 3) If the new point is not dominated, check to see which points below it that are dominated by the new point. Remove them from the pareto frontier. If you find a point that is not dominated by the new point exit. As an example, I updated the gist with code that does exactly the above and added in your example: f = [ x^2; (x-2)^2 ] given that -10 < x < 10 6000 points on the current frontier and determining if 16,000 new points should be added to it or not. That part of the code is done in cell 3. http://nbviewer.ipython.org/gist/dwil/5cc31d1fea141740cf96 Hope this helps you out a bit more. On Friday, April 24, 2015 at 6:01:31 PM UTC-3, Duane Wilson wrote: > > Ah I see. Yeah this probably depends a lot on the way you are representing > the bits and how you split the objectives. If each objective is an > ASCIIString of bits and they're held separately (i.e. objectives is a > Vector{ASCIIString}) what I have provided should work because the isless > function works on strings. It probably isn't the most efficient way to > compare them however. > > On Friday, April 24, 2015 at 1:34:25 PM UTC-3, Ronan Chagas wrote: >> >> Hi Duane Wilson, >> >> Em sexta-feira, 24 de abril de 2015 11:52:08 UTC-3, Duane Wilson escreveu: >>> >>> Actually I was able to get the go ahead from my boss to create a gist of >>> the code I've produced. I've modified it a little bit, as some of the >>> things in there are really relevant. >>> >>> http://nbviewer.ipython.org/gist/dwil/5cc31d1fea141740cf96 >>> >>> Any comments for optimizing this a little be more would be appreciated :) >>> >>> >> Thanks very much, it will help me and, if I can contribute, I will tell >> you :) >> >> The problem is that for each generation of this evolutionary algorithm I >> will need to check if n candidate points belong to the Pareto frontier, >> where n is the number of bits in the string. >> Thus, I need a really fast algorithm for this kind of operation. As I am >> doing now (I will post the code in github), it works fine until the >> frontier has a large number of elements. >> Just one example, suppose that I'm using n = 16 and I have 6,000 elements >> in the frontier. If I generate 1000 generations, then I will need to check >> if 16,000 points are in the frontier. >> It will lead to 96,000,000 comparisons considering that no point will be >> added to the frontier. >> >> Thanks, >> Ronan >> >>
