Power Magnetic Devices. Scott D. Sudhoff

Скачать книгу

they are a part of the genetic code that is unused. When mutation has a noticeable effect, it is generally for the worse. However, occasionally beneficial mutations occur which improve the ability of an individual (and eventually a species) to survive.

      A final concept from biology that will serve our needs for an optimization engine is the idea of natural selection and the survival of the fittest, an idea stemming from Charles Darwin’s voyages of the H.M.S Beagle, during a period of time roughly contemporary with the work of Mendel and the American Civil War. The idea that the most fit individuals of a population survive to reproduce is directly used in GAs. These algorithms are based on an explicit fitness function, which will be used to determine which individuals “survive” and will be placed into a mating pool.

      Clearly, the discussion in this section is at a high level and has been greatly simplified. The interested reader is referred to Crow [2] for a more thorough introduction to the topic.

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 θⁱ is the genetic code for the ith individual in the kth generation of the population and where N_p 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

(1.5-2)

where N_c is the number of chromosomes, N_g 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, θⁱ 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,

(1.5-3)

      where xⁱ is the parameter vector of the ith member of the population and is structured as

      (1.5-4)

      As can be seen, xⁱ 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,

(1.5-5)

      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.

Example 1.5A

      Suppose the 13th member of the population has the genetic code

(1.5A-1)

      The decoding algorithm is on a gene‐by‐gene basis and is of the form

(1.5A-2)

where l_i is the number of bits of the ith gene, m is an index ranging from least significant (rightmost) bit to most significant (leftmost) bit for a given gene, b_m is the value of that bit (0 or 1), and x_mn,i and x_mx,i are the minimum and maximum values of the ith element of the parameter vector. For the problem at hand, we assume x_mn,1 = 5, x_mx,1 = 10, x_mn,2 = − 2, x_mx,2 = 0, x_mn,3 = 0, and x_mx,3 = 1. In Section 1.9, we will formally consider the construction of fitness functions, and in Section 1.10, we will consider an engineering example. However, for the moment we will assume a purely mathematical fitness function given by

(1.5A-3)

      Our goal is to compute

Скачать книгу