Evaluation

Each individual in the population specifies a particular parameter set for the system, and is evaluated by running a simulation with the specified parameters in a given environment. Consider that the agent navigates from an initial position $p_{0}$ to the target cluster C containing the $n$ target positions ($t_{1}$, $t_{2}$, ..., $t_{n}$) and that it takes $d_{i}$ steps to reach the target $t_{i}$ from $p_{0}$ with a success value $s_{i}$. A threshold is defined for the number of steps that are taken to reach the target, above which the agent is said to have failed in its attempt to navigate to the target (i.e. its success value is 0, otherwise it is 1).

This formalization gives the clues to define the fitness function that permits the selection of the best parameter sets. It is clear that the average cost of reaching a target from the initial position $p_{0}$ is defined as the summation of the steps required to reach each target divided by the number of targets. That is,

$$\overline{c} = \displaystyle \frac{\sum_{i=1}^{n} d_{i}}{n}$$

Similarly, we can naturally define the average success value as:

$$\overline{s} = \displaystyle \frac{\sum_{i=1}^{n} s_{i}}{n}$$

The best behavior for a navigation system is the one that has a high success rate with a low average cost and with a low standard deviation for this average cost, $\sigma_{c}$. Thus, we define the fitness function as follows:

$$f = \frac{\overline{s}}{\overline{c} + \sigma_{c}}$$