Galapagos "multiple fitnesses" best workaround

Replies to This Discussion

Permalink Reply by David Rutten on February 25, 2011 at 6:16am

Hi Niels,

 

it's not easy is it, trying to match multiple targets? There's no clear-cut solution as the approach depends heavily on the behaviour of the system you're solving. But let's take a very simple problem.

 

Imagine you're dividing a space (100m²) into two rooms, one of which (room A) should be 60m², the other (room B) 40m². Now it follows that the sum of both rooms must always add up to 100m². And if you make one room smaller by 5m², the other one gets bigger by 5m².

 

The simplest expression that would convert room areas into a fitness value is, I think:

 

Abs(A - 40) + Abs(B - 60)

 

or, in English, the sum total of the discrepancies between the actual areas and the desired areas.

 

If the rooms are both 50m² we get a fitness of:

Abs(50-40) + Abs(50-60) = 20

 

If room A equals 10m² and room B equals 90m², we get:

Abs(10-40) + Abs(90-60) = 60

 

If both rooms are exactly right, we get:

Abs(40-40) + Abs(60-60) = 0

 

So the point here is to minimize fitness, and once the fitness has reached zero we know we're home free.

 

 

But this is a very straightforward case. What if we're trying to optimize a problem, while knowing there's no way on Earth we'll be able to solve all constraints? This is after all what Evolutionary solvers are good at. So what if the problem is not as clear cut? 

 

This time try to imagine we want every room to be 50m², but all the rooms are too small. Let's write down three cases like before:

 

(Room A = 30m², Room B = 40m²)

Abs(30 - 50) + Abs(40 - 50) = 30

 

(Room A = 35m², Room B = 35m²)

Abs(35 - 50) + Abs(35 - 50) = 30

 

(Room A = 25m², Room B = 45m²)

Abs(25 - 50) + Abs(45 - 50) = 30

 

Holy Crap! They're all the same! Well this is no good, it's like three bald men fighting over a comb. Even though all solutions fail to meet constraints, they certainly shouldn't all be equally fit. Let's assume for the time being we'd rather have both rooms fail to meet demands in equal amounts instead of one room being ok-ish and the other being way off. How can we add this assumption to the fitness function?

 

Basically we need to exaggerate large departures from the ideal and trivialize small departures. Our naive fitness function was linear, our new and improved fitness function must be non-linear. The simplest non-linear function is the parabola (x²). So let's see where that gets us.

 

Abs(30 - 50)² + Abs(40 - 50)² = 500

Abs(35 - 50)² + Abs(35 - 50)² = 450

Abs(25 - 50)² + Abs(45 - 50)² = 650

 

Phew... The case where both room fail to meet demands equally has the lowest value (and thus the highest fitness) whereas the most extreme discrepancy has the highest value (and thus the lowest fitness).

 

This approach is called Least Squares fitting and it's one of the most common fitting algorithms in statistics.

 

Whether you decide to weigh your competing factors equally or differently, and whether you decide to treat deviations linearly or non-linearly is entirely up to you. It requires you have a decent understanding of the problem at hand and also a decent understanding of the mathematical behaviour of the fitness function.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Mårten Nettelbladt on February 25, 2011 at 6:48am

Thanks David, I have been wondering about this too. /Mårten

Permalink Reply by Chris Tietjen on February 25, 2011 at 7:15am

Very nice.  Thankyou.

Chris

Permalink Reply by taz on February 25, 2011 at 10:25am

Interesante

Permalink Reply by William Lopez Campo on July 26, 2011 at 7:50am

David,

Despite a clear approach to multiple criteria optimization with a weighted average (linear, square, or any other), you could argue that in nature (where GA is taking inspitarion from) different species adapt to the same environment with different srategies, and so diversity is kept.

Example: One animal survives running faster, another hides better, another is poisonous. All three survive being better in their own right, and all three are "optimal" solutions.

The Pareto Efficiency is a way to establish a comparison (therefore a ranking) of solutions, based on how each solution is compared to their competitors in multiple criteria. For Design this is fundamental, as it opens up a possibility of "out of the box thinking" solutions that solve the problem in an original combination without the "weighted" solution that in theory could be reverse-calculated considering the set of definitions that lead to the fitness build-up formula, which could lead to a single or multiple solutions, and the relationship of the input parameters - like in the queries where Galapagos is used to calculate radius and height to match a given volume of a cylinder...

 

Not easy as you said, and with the current set-up I find it very difficult to face multi-criteria optimization without merging the variables... any thought??

 

Thanks and kudos for your amazing work!!!