Population Update Model

There are different techniques for updating the population, among the most important are the generational model and the steady-state model. In the generational model in each generation a complete set of $N$ new offspring individuals is created from $N$ parents selected from the population. In most such generational models, the tournament selection is used to choose two parent individuals, and a crossover with $p_c$ probability and a mutation operator con $p_m$ probability are applied to the parents.

This contrasts with the steady-state model, where one member of the population is replaced at a time. The steady-state model selects an individual to be mutated and the mutated individual replaces another individual of the population. For the crossover two individuals are selected and one of the offspring replaces one individual of the population. There are a number of different replacement strategies: replace-worst, replace a randomly chosen member, select replacement using negative fitness.

The model that extrapolates between generational and steady-state is said to have a generation gap $G$ [De 75,JS93]. Thus for a generational model, $G=1$; while for a steady-state model, $G=1/N$. One of the most widely used variants of the steady-stated genetic algorithm is the Minimal Generation Gap (MGG) model [SYK96]. This model takes two parents randomly from the population and generates $\lambda$ children. Two individuals are selected from the parents and the offspring: the best individual, and another individual chosen by roulette selection. These two individuals substitute the parents in the population.

The generational model is the most frequently used in the comparative studies that use BLX, SBX, logical crossover and fuzzy recombination. This is the reason why it will be the model used in this paper. However, for UNDX crossover we have used the MGG model, because UNDX and MGG are commonly used together and the generational model can have a negative influence on the performance of UNDX.

For the parameters of the two models we have used the most commonly used in the literature. For the generational model, we use a probability of crossover of $p_c=0.6$ [De 75,HLV98]. For the MGG model we have used $\lambda=200$, as this is a value commonly used in papers about UNDX [OK97,OKK99,OKY00]. For the mutation probability, values in the interval $p_m \in[0.001, 0.1]$ are usual [De 75,HLV98,Mic92,Bäc96]. We have chosen a value of $p_m=0.05$ for both models.