2
$\begingroup$

I try to solve Physical Travelling Salesman Problem using evolutionary algorithm and I have diffucult to detemine how to choose the parent , on which we do the crossover.

Assume I have popultion of 100. The parent should be selected randomally? or according to their fitness? If I choose them randomally I don't think the result be enough good but in the other hand, if I will choose the 2 with the best fitness, I will always choose the same! (Maybe child of them , but most of my population will never be choosed!).

What I miss?

I also need some advise on how to calculate fitness. The parameters are the amount of waypoints each van collect and the total time.

My problem here is becuase there are unit that don't manage to collect any points and thus thier fitness is 0 and step by step my array full with 0....(I am working with the code here : http://www.ptsp-game.net/ ant there is problem of time exceed..)

$\endgroup$
5
$\begingroup$

As a simple method, you can use the roulette wheel selection. The idea is that every individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let $f_i$ be the fitness of the individual $i$. The probability $p_i$ of choosing $i$ as a parent for the next round is $p_i = f_i / \sum_{j=1}^{N}$, where N is the size of your population.

Here's an example in the context of TSP. For simplicity, let's say your population is only 4 individuals. Assume every individual is a tour of some length. The shorter the tour, the higher the fitness. Let the fitness values of the tours be $F = \{ 25,15,10,5 \}$. The sum of elements is 55. We divide every element $f_i$ with 55, and obtain $\{ 0.45, 0.27, 0.18, 0.09\}$. To implement the roulette wheel, you can use a weighted random generator if the language provides one (if not, just roll your own).

If you want to experiment with other genetic selection operators, look up other more complicated selection methods. To get you started on those, have a look at selection operators.

$\endgroup$
  • $\begingroup$ @user2459338 If you are having problems with formulating the fitness function, try this. Let $M$ be the length of the longest tour you currently have in your population. The fitness value for individual $i$ is then $M-l_i$, where $l_i$ is the length of the tour $i$ represents. That works for TSP (I don't know exactly what your problem is). $\endgroup$ – Juho Jun 13 '13 at 14:57
  • $\begingroup$ length in the meaning of amount of cities or time? I need to consider 2 paramaters in the fitness function : amount of cities he visited and total time its take him. $\endgroup$ – user2459338 Jun 13 '13 at 18:43
  • $\begingroup$ @user2459338 OK. I meant the length of the tour and assumed every edge has a weight. If you have 2 parameters, your problem is certainly different. Maybe it can still give you some inspiration as to what is a good fitness function (or you could google it, too). $\endgroup$ – Juho Jun 13 '13 at 20:15
0
$\begingroup$

There is also the tournament selection which can be used in conjunction with the simple microbial genetic algorithm as outlined in this paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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