Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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!

share|improve this question
    
Are you interested in any pareto-optimal point or do you need the Pareto frontier? –  Deathbreath Jan 29 '13 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 '13 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 '13 at 15:14

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
Wow, a good and fast answer! I love your idea to avoid local optima, to let the different constraint factor/priority change in function of the current generation, it gives the algorithm the chance to explore more individuals even if they will not be part of the final solution. –  Pierre-David Belanger Jan 27 '13 at 20:57
    
And indeed, as you said, I will remove the hard constraint calculation from the fitness function. And anyways, I think I will keep the individuals that break those constraints and by using the varying priority factor, they will be eliminated in the lasts generation. –  Pierre-David Belanger Jan 27 '13 at 21:03
    
So, I accept your answer without waiting for other. You answered all my points with a good enough answer for me. Thank you very much. –  Pierre-David Belanger Jan 27 '13 at 21:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.