Multi-objectives fitness function with hard and soft constraints

Question

Background

I am using genetic algorithm to solve the multiple-traveling-salesman problem. It work fine when I have only one constraint (distance) for my fitness function: ie: the lower the total distance, the better are the chances of the individual to survive.

But now I want to add other contraints like:

• time-windows: for example: salesman1 (S1) work between 9h and 17h, city1 (C1) is open between 9h and 12h and C2 is open between 11h and 13h.

• capacity: S1 have a vehicle with a capacity of 10 boxes (whatever the unit), C1 wants 2 boxes and C2 will give 3 boxes.

• competence: S1 have a refrigerated vehicle, S1 needs perishable goods, and so on.

Also, I consider a constraint to be soft when an individual can survive a generation (have more chances) even if it the constraint is not fully satisfied (ie: distance, time-window). Where a hard constraint must be satisfied in order for the individual to survive (ie: capacity, competence).

I am already ok with the genetic representation and the technology I should use to solve this.

My attempt

So far, this is what I came up with to implement my fitness function:

For each individual:

(1) I will calculate/assign a score for each constraints separately:

• distance: 1 / km where km is the total distance traveled by each salesman
• time-window: 1 / second where second is the difference in second between the actual time (when the salesman vist the city) and the city time-window, for each city
• capacity: 1 / box where box is the number of over/under load of the salesman vehicles
• competence: +1 for each city if the assigned salesman satisfy the required competence

(2) I will multiply each constraint score by a factor (a kind of priority, this is what makes each constraint hard or soft?)

• distance score * 20
• time-windows score * 20
• capacity score * 30
• competence score * 30

(3) Then sum all those results. This sum will be the fitness cost, the higher the beter.

Questions

1. fist, am I in the right direction?
2. is there recommended/general ways to implements a multi-objectives fitness functions?
3. how can I make those constraints hard or soft?
4. how can I prevent premature optimization or local optima (ie: all constraints are satisfied except the distance, but individuals with beter distance optimization keep dying because they perform bad in the fitness function)?

Other advices are very welcome!

Thank you!

PS: sorry about my choice for the tags, I do not have the reputation to create new tags, I would have tag it at least with genetic-algorithm!

Answer 1

Using a weighted sum of your different fitness functions is a fairly standard way to handle multiple objectives. Of course your final answer can depend greatly on the priorities you set.

As far as making constraints hard and soft, it looks as though your current set up has them all soft. If a certain individual does well enough on one of the objectives, it can fail to meet other requirements, which I don't think is what you want.

I would remove the hard constraints from the fitness function, and simply check each individual to make sure they meet all the requirements. If they don't meet them, don't even evaluate the fitness function, just throw them out.

For your soft constraints, one option is to change your multi-objective coefficients as you get into later generations. For example, let $D$ be the objective value of the distance, with higher $D$ being better. Let $T$ be the objective value for time, which you mentioned was one of your soft constraints. You can then formulate your objective function as: $D+f(n) T$ where $n$ is the generation you are in. If $f(n)$ is an increasing function, you will allow misses on the time in early generations if the individuals perform well enough for your distance metric, however as $n$ increases, $T$ becomes more and more important, until all your individuals meet your time requirements (where $T$ would attain some high, but constant value).

This sort of setup would help avoid the local minima you mention in your 4th point. Of course I will defer to other answerers here since my own experience in optimization of this type is small and there may be more "text-book" ways of handling soft constraints.