Genetic Algorithm Network Optimization

Genetic Algorithm is the default optimization method for network optimization in PTV Vistro. Genetic Algorithms (GA) are widely used in several areas where automatic optimization is needed. There exists a huge number of books describing GA in detail, such as Holland 19751 Holland, John H (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor and Goldberg 19892 Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.. GA are inspired by the process of evolution. The principle workflow is shown in the figure below:

Figure 36: Genetic Algorithm Fundamental Workflow

There is a population of individuals (here: signal plans) and each of the individuals has a certain fitness (here: objective function, weighted sum of delay and number of stops, to be minimized). Every individual has a probability to be selected for reproduction for the next generation, where the probability is higher with a higher fitness (analogy to the evolution). Several so-called genetic operations can be performed in the reproduction process.

• Crossover
• Mutation

To never get worse with the next iteration, the best individual of every generation is taken over directly to the next generation.

As shown below, the Genetic algorithm allows you to adjust the Objective Function factors and define the optimization settings, providing you control over the level of robustness and speed of the optimization of your network.

Figure 37: Genetic Network Optimization Settings

Objective Function

The optimization algorithm aims to minimize the objective function. The objective function is the weighted sum of (a) total vehicle delay (hours) and (b) the number intersections where a vehicle has to stop over all vehicles. The user can define the weights for the two factors.

Maximum Number of Iterations

Maximum Number of Iterations specifies how many iterations (or: generations) there can be if no other termination criterion is met. In general, the higher Maximum Number of Iterations is, the longer the optimization may take. However, this value should not be too low, as Maximum Number of Iterations should not be the termination criterion (because there is still improvement, otherwise the termination criterion Number of Generations without Improvement would be met. In other words: There is still potential for improvement).

Population Size

Population Size specifies the number of individuals (network wide signal plans) there is per generation. Generally, the higher this number is, the better the chances to find the optimum. The computation time can be up to proportional to the population size (if Maximum Number of Iterations is the relevant termination criterion).

Number of Generations without Improvement

Number of Generations without Improvement specifies after how many generations with no improvement (or: less than Minimum Improvement, see next sections) the optimization terminates.

Minimum Improvement

Minimum Improvement specifies how much better the solution has to be to be considered better. Example: if this is 1 %, then an improvement of 0.5 % will not be considered as an improvement.