Читать книгу Power Magnetic Devices - Scott D. Sudhoff - Страница 20
1.5 The Canonical Genetic Algorithm
ОглавлениеA century after the work of Mendel and Darwin, but a mere decade after the work of Watson and Crick, John Holland, a professor at the University of Michigan, proposed using the principles of biological genetics as a computation algorithm for optimization, a concept instantiated by a GA [3]. In this section, we will begin our consideration of GAs with a canonical GA similar to Holland’s original vision.
GAs are quite different from traditional optimization algorithms. First of all, GAs operate not on the argument of the function being optimized, but rather on an encoding of the argument. Second, rather than iterating to improve an estimate for an optimizer, GAs iterate to improve a large number of different estimates of the optimizer. This collection of estimates will be referred to as a population. The use of a population of estimated solutions improves the chances of finding a global optimum. Third, GA operations are based only on the values of the objective function—gradients and Hessians are not used, nor even estimated. This property is useful in function with discontinuities or with a discrete or mixed search space. Finally, GA operations are based on probabilistic rather than deterministic computations.
The first concept that must be set forth in a GA is that it, like evolution, operates on a population, not on an individual. We will denote the population within the GA as P[k], where k is the generation number. The kth generation consists of a number of individuals, that is,
(1.5-1)
where θi is the genetic code for the ith individual in the kth generation of the population and where Np denotes the number of individuals in the population, which should be an even number. The genetic code for the ith individual may be organized as
where Nc is the number of chromosomes, Ng is the number of genes, and is the jth gene of the ith individual (and it is understood that we are referring to the kth generation). Each gene is a string sequence. Recall that DNA consists of alphabet AT, TA, CG, and GC. In the case of the canonical GA, the string is most typically a binary sequence. Thus, θi takes the form of a binary number. The significance of the chromosome organization will come into play when we consider reproduction.
The fact that the genes are encoded results in a limitation of the domain of the parameter vector. In other words, the domain of possible values of each element of the parameter vector is inherently limited. In some cases, this property is very convenient, but in other cases this limitation on the domain of the parameter vectors is disadvantageous.
Associated with the genetic code for each population member, we will have a decoding function that translates the genetic code into a parameter vector. In particular,
where xi is the parameter vector of the ith member of the population and is structured as
(1.5-4)
As can be seen, xi has one element (denoted with a subscript) for each gene. However, it is not partitioned into chromosomes.
Based on the parameter vector of ith population member, the objective function can be evaluated. In particular,
In the case of a GA, the objective function is referred to as a fitness function. It will be used in a “survival of the fittest” sense to determine which members of the population will mate to form the next generation. In the context of a GA, fitness is viewed in a positive sense, thus it is assumed that we wish to maximize the fitness function. Fortunately, it is a straightforward matter to convert between maximization of a function and the minimization of a function. At this point, we have enough background to discuss the computational aspects of a GA. However, before doing this, it is appropriate to briefly pause in our development and consider an example.