"Overview of Genetic Algorithms 002.ps.gz" - читать интересную книгу автораAn Overview of Genetic Algorithms: Part 2, Research Topics David Beasley\Lambda Department of Computing Mathematics, University of Wales College of Cardiff, Cardiff, CF2 4YN, UK David R. Bully Department of Electrical and Electronic Engineering, University of Bristol, Bristol, BS8 1TR, UK Ralph R. Martinz Department of Computing Mathematics, University of Wales College of Cardiff, Cardiff, CF2 4YN, UK University Computing, 1993, 15(4) 170-181. cfl UCISA. All rights reserved. No part of this article may be reproduced for commercial purposes. In the first part of this article [BBM93a] we described the fundamental aspects of genetic algorithms (GAs). We explained their basic principles, such as task representation, fitness functions and reproduction operators. We explained how they work, and compared them with other search techniques. We described several practical aspects of GAs, and mentioned a number of applications. In this part of the article we shall explore various more advanced aspects of GAs, many of which are the subject of current research. 2 Crossover techniques The "traditional" GA, as described in Part 1 of this article, uses 1-point crossover, where the two mating chromosomes are each cut once at corresponding points, and the sections after the cuts exchanged. However, many different crossover algorithms have been devised, often involving more than one cut point. DeJong [DeJ75] investigated the effectiveness of multiple-point crossover, and concluded (as reported in [Gol89a, p119]) that 2-point crossover gives an improvement, but that adding further crossover points reduces the performance of the GA. The problem with adding additional crossover points is that building blocks are more likely to be disrupted. However, an advantage of having more crossover points is that the problem space may be searched more thoroughly. 2.1 2-point crossover In 2-point crossover, (and multi-point crossover in general), rather than linear strings, chromosomes are regarded as loops formed by joining the ends together. To exchange a segment from one loop with that from another \Lambda email: [email protected] yemail: [email protected] zemail: [email protected] 1 loop requires the selection of two cut points, as shown in Figure 1. In this view, 1-point crossover can be seen StartFinish |
|
|