Feasibility and Genetic Algorithms: The Behaviour of Crossover and Mutation

摘要

New genetic operators are described that assure preservation of the feasibility of candidate solutions to any discrete and linearly constrained optimisation problem. The design of these operators is the result of extensive theoretical investigations, with particular assiduity devoted to considering the most challenging examples of this type. Attention is largely centred on problems that have defied satisfactory solution by traditional means, because of poorly behaved or imprecise objective functions, high dimensionality, or intractable algorithmic complexity. Evolutionary Algorithms, inspired by adaptation in biological systems, are ideally suited to such arduous conditions, as testified by their increasing popularity and successful exploitation in resolving numerous difficult problems. Their obvious attraction notwithstanding, the applicability of evolutionary algorithms has suffered by the deficiency of general techniques to manage constraints, a feature common to many problems, and the asperity is compounded when some proportion of the decision variables are discrete. The enhanced operators presented here guarantee the feasibility of proffered aspirant solutions with respect to a system of linear constraints. Exploration of highly constrained systems indicates the possibility of performance degradation, with the diminishing probability of discovering a feasible and meaningful exchange of information between candidate solutions. Relaxation of the crossover operator is proposed to alleviate this, and the effective utilisation of this in the context of the overall algorithm suggests a modification in which the population is permitted to transiently increase in size.