# Evolutionary algorithm - how to select the parents

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

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).
• @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). – Juho Jun 13 '13 at 14:57