Genetic Algorithm

The genetic algorithm [63,87—90] is used for minimization of functional of form (5.45). In this case, the distribution function f(r) can be taken in any form, in particular, in form (5.43). The search is performed over the space of parameters of the distribution function. The genetic algorithm of search for the minimum is based on simulation of the process of natural evolution and falls in the category of the so-called evolution search methods. That is why it is described by terms borrowed from biology. Operations used in the practical implementation of this method are based on analogs from the living world, such as mutation and crossing. Operations are carried out with a set of solutions (population), and their results are descendants (new solutions), which are also included in the population. Along with creation of descendants, in adaptive forms (worst solutions) are removed from the population. As a result of multiple repetition of these operations, the population consists of the best adapted forms, and thus the optimal solution can be achieved.

More rigorously, the genetic algorithm can be determined as the following object GA(P0, r,Fit,sl,cr,m,sc), where P0 is the initial population; r is the number of elements in the population; Fit is the fitness function (utility function); sl is selection of solutions for creation of a new solution; cr is the “crossover” operator determining the possibility of obtaining a new solution; m is the mutation operator; sc is the selection operator. The block diagram of our algorithm is shown in Figure 5.11.

The initial population P0 is a set of initial solutions belonging to the space of solutions X The population P0 is generated either in a random way or based on a priori data about the sought solution. The fitness function is determined by the minimizing functional. The selection of solutions is necessary for creation of a new solution. It is worth selecting the solutions corresponding to the optimal and most widely different solutions.

In other words, the algorithm strategy can consist in the equiprobable selection of the solutions, for which Fit(Xk) < Fitcp, where Fitcp is the average value of the fitness function. Upon selection of the generating solutions (ancestors), they are subjected to the crossing-over operation for creation of a new solution (descendant). The “crossover” operation can be performed with the aid of recombination of vector elements of ancestor solutions [63] or by the following equation: Block diagram of the genetic algorithm

Figure 5.11 Block diagram of the genetic algorithm.

where xi is the i-th element of the new solution vector, q is the uniformly distributed value from 0 to 1, xk1i, xk2ii are the generating solutions. Once the new solution is created, it is subjected to the mutation operation, which can be carried out in the following way:

where Np is the dimension of the solution vector, 6 is a small random value, i are selected from the given range, and the probability of change of a large number of elements is small. After this operation, the solution is added to the population. Then the good solutions are selected and worst solutions are rejected from the population. This process can proceed for one solution or several solutions simultaneously. For example, by the condition Fit(Xk) < Fitcp all solutions are rejected, and then the new set of solutions is created with the aid of overcrossing and mutations.

In the problem of lidar sensing of the microstructure of a cloud layer on the assumption that the droplet spectrum satisfies the generalized y-distribution of form (5.43), the fitness function can be represented in the form:

The number of functions is also an unknown parameter of the search, whose value at the mutation operation is selected every time by the exponential distribution law

The random number generator is described by the equation Ng = [— ln (1 — F/q) + 1], where the square brackets mean the rounding off to an integer number. The amplitude and center of every 7-function are also introduced as unknown parameters. The half-widths ц are variable parameters at ц ^ max (r), where r is the particle radius.

In general, the proposed algorithm can be described in the following way. For every sought parameter, the search range is specified based on our knowledge of the function f(r).

At the first stage, the initial array of solutions is determined. Random values from the corresponding range are assigned to the array parameters for every possible solution. For every solution (vector of sought parameters [ap a2, ... , an] for an arbitrary function or [a, a, b, 7] for the function of 7-distribution), fitness function (5.47) is calculated. The smaller the value of functional (5.47) (the smaller accuracy of parameter determination), the better the solution. Two or more solutions are selected in the array of solutions, and then the crossing-over operation is carried out. It is followed by the mutation operation, that is, change of one or more descendant parameter by a small value or complete change of several parameters. Once the descendant is created, it is determined whether this descendant is better than the most inadaptive member of the population. If it is so, the inadaptive member is removed and replaced with the descendant. The operation is repeated until the acceptable solution is obtained.

 
Source
< Prev   CONTENTS   Source   Next >