Thank you very much Duane! It will help me a lot.
Right now, I found something that was really slowing down my algorithm.
The original function checkDominance has the following signature:
function checkDominance(mgeoData::MGEOStructure,
candidatePoint::ParetoPoint, paretoFrontier::Array{ParetoPoint,1})
in which
type MGEOStructure
# Number of objective functions.
nf::Integer
# Parameter to set the search determinism.
tau::Float64
# Maximum number of generations.
ngenMax::Float64
# Maximum number of independent runs (reinitializations).
runMax::Float64
# Structure that store the configuration for each design variable.
designVars::Array{DesignVariable,1}
# Epsilon to compare objective functions.
mgeoEps::Float64
end
type DesignVariable
# Number of bits.
bits::Uint32
# Minimum allowed value for the design variable.
min::Float64
# Maximum allowed value for the design variable.
max::Float64
# Full scale of the design variable.
fullScale::Uint64
# Index in the string.
index::Uint64
# Name of the variable.
name::String
end
type ParetoPoint
# Design variables.
vars::Array{Float64,1}
# Objective functions.
f::Array{Float64, 1}
end
In this case, it took almost 62s to find the Pareto Frontier for the
problem mentioned before in which this function is called almost 128,000
times.
After some tests, I decided to change the function signature to:
function checkDominance(nf::Int, eps::Float64, candidatePoint::ParetoPoint,
paretoFrontier::Array{ParetoPoint,1})
Now the code takes now only 2s to optimize the same problem (it is 30x
faster). Just for comparison, optimized (-O3) C++ version takes 0.6s.
Question: Is it expected such slow down when a structure is passed to a
function? I can easily provide a working example if it helps julia devs.
Thanks very much,
Ronan
P.S.: I will upload the entire algorithm this week, I promise :)
Em segunda-feira, 27 de abril de 2015 22:19:21 UTC-3, Duane Wilson escreveu:
>
> 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
>>>
>>>
