What is the fitness landscape for minimal + viable solutions?

Let’s say I’m trying to find a number from 1 .. 100. All numbers in this range are “valid”, in that they could be interpreted as potential solutions.
Let’s say the ideal number is 50. And all numbers >= 50 are “feasible” in that they actually solve the problem. And all numbers < 50 are “not feasible” (but still valid).
How would you code a scenario like this with a fitness function (assuming that the landscape is similar to but more complex than this contrived example)? Do you give “bonuses” to valid solutions? Do you measure how far an unfeasible solution has left to go before becoming optimal? And do you penalize excessive solutions?

if (solution < 50) {
  maximalFitness = f(solution)
} else if (solution >= 50) {
  maximalFitness = 1_000 - f(solution)
}

The curve wouldn’t be continuous if all feasible solutions are strictly better than all unfeasible solutions, despite having a similar distance from optimal.

What you’re referring to is called “constrained optimization”. This is a really well-studied branch of evolutionary computation, and you can find dozens of resources describing common techniques for solving these problems. Carlos Coello-Coello does a tutorial on the subject each year at GECCO, the primary EC conference in the field. I found slides from one such session available here (ftp://ftp.cs.bham.ac.uk/.snapshot/nightly.1/pub/authors/W.B.Langdon/biblio/gecco2008/docs/p2445.pdf). You might find that a useful jumping-off point for further study.

In short, there are two high-level approaches that are by far the most common: penalization and repair. In penalization, you decrease the fitness of solutions by some function of how badly they violate the constraints. In repair, you actually modify infeasible solutions directly to attempt to move them into the feasible region.

Penalization works well if you can get the penalty scheme right, but that can be a tricky problem to solve, and it’s essentially always problem dependent. One option is to just mess around with your fitness function and figure out the right amount to penalize so that “good” infeasible solutions get just enough fitness to not die immediately but not so much that they become preferred over feasible solutions. Another method is to just replace the selection criteria to account for infeasible solutions directly. That is, instead of

if fitness(p1) > fitness(p2):
    # p1 is better
else:
    # p2 is better

you have something like

if (is_feasible(p1) and is_feasible(p2)) or (not is_feasible(p1) and not is_feasible(p2)):
    if fitness(p1) > fitness(p2):
        # p1 is better
    else:
        # p2 is better
else:
    if is_feasible(p1):
        # p1 is better
    else:
        # p2 is better

This explicitly handles all the ways of comparing feasible and infeasible solutions, and uses their fitness values only to break ties. Now it doesn’t matter so much if the raw fitness value of an infeasible solution is higher than a feasible solution due to weirdness in your penalization scheme.

Repair is often preferable if you can do it (it isn’t always possible to build an effective repair operator). By repair, we mean you take the infeasible solution and actually modify it so that it falls within your feasible region. This could be as simple as just thresholding the value within the allowed range, but more often will require some sort of domain specific or heuristic search. For example, if you have a knapsack problem and a solution has too much weight in the knapsack, a repair operator might randomly start throwing items out of the knapsack until the total weight was less than the capacity. A better operator might bias the removal of items toward those with the highest weight/value ratio. It’s usually beneficial for the repair to have some randomness involved — you may want to bias things slightly, but you don’t want to always do a greedy repair.

There are other approaches as well. One recent innovation has been to treat each constraint as a separate objective function and employ multi-objective optimization algorithms to find a range of trade-off solutions. For some problems, this has been shown to be effective, but I think the general rule of thumb should probably be to first see what can be done with the simpler methods like penalization and repair.

Filed under: softwareengineering - @ 21:23

Thẻ: genetic-algorithms

Thiết kế website giá rẻ

Danh mục

What is the fitness landscape for minimal + viable solutions?