# Multi-objectives fitness function with hard and soft constraints

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)?

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!

-
 Are you interested in any pareto-optimal point or do you need the Pareto frontier? – Deathbreath Jan 29 at 19:55 Those are new concepts for me. But given the description I just read, and if I understand well, I guess that it should be a great improvement for my problem, if I can manage to make the fitness of my final solution (the best individual at the end of the GA) be on the Pareto frontier. I guess the Pareto frontier can be represented as an equation? In multiple dimension? – Pierre-David Belanger Jan 29 at 21:57 The pareto-frontier may not have an analytical solution and you might actually have to compute it explicitly. I'm not an expert myself, but I assume you could use a partial order on your fitness array (versus a scalar in single objective optimization) to decide which members to keep. – Deathbreath Jan 30 at 15:14

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).