Predicting production based on genetic algorithms

Predicting production based on genetic algorithms

KeywordsCybernetics, Genetic algorithms, Optimisation

Abstract Proposes a genetic algorithm approach to predict the production of an enterprise. It is shown that the genetic algorithm is an effective method to be applied in the economic field as the other methods, such as recursive and LMS methods, are mostly used. Based on natural selection and the natural genetic mechanism,genetic algorithms are global search algorithms such that the solution found is close to the global optimization. Considers how the genetic algorithms work to reach the solution and what are the principle and concrete procedures of predicting production of genetic algorithms.

Introduction

Many scientific models are always nonlinear, even non- deterministic, or even have several unknown parameters or coefficients. LMS is in principle a local method and depends on the linearity of the problem. Global methods such as the consistent Monte Carlo method do not depend on differential information and are not related to any error criterion. It avoids matrix inversion of a matrix and so it is robust. Global methods randomly check a wider solution space. This means checking useless parameter subspace, so it wastes a lot of time. Randomly searching a large parameter space is different from local methods because the latter uses only several models and differential message to check samples to obtain information to diminish estimation error. So there is a trade-off between robustly searching parameter space and effectively using sample checking information.

In recent years, genetic algorithms, that are different from other optimal algorithms in methodology,have got into use. They are based on natural selection and population genetic mechanism, simulating natural genetic procedure. It implements global, parallel and random search optimization in problem space and enables a population to converge optimization in a global manner. This method provides a new approach to solving these problems.

Basic principle of genetic algorithms

Genetic algorithms, based on natural selection and natural genetic mechanism, are recursive, adaptive, and probabilistic search algorithms. They are suggested by Holland (1975), and introduced in detail in his book. Later, genetic algorithms became an interesting topic in research fields, especially in the West and in Japan. The study and application of genetic algorithms became interesting. Several different researchers proceeded to improve simple genetic algorithms (Potts et al., 1994), applying it in the design and modification of a controller (Park et al., 1994), associating it with fuzzy control and fuzzy inference(Goldberg, 1993). In China, the study and application of genetic algorithms became more and more widespread (Chen et al., 1993; Chen Guoliang et al., 1997). Genetic algorithms employ evolution methodology, encode problem solving. Each possible solution is represented by a string of characters.

In the initial step, it randomly produces a population whose size is N, a constant. The population is estimated in performance by a reasonable fitness function and then it is processed by reproduction, crossover and mutational genetic operations. A fitness function is similar to some force in natural selection. These three genetic operators simulate widely existing biological evolution in nature. Reproduction is a procedure of selecting living and strong individuals to produce a new population from the last generation of the population. It simulates the biological evolution in which selecting is to find a function value of a single bit string and to transfer it to a fitness degree. It takes reproduction probability corresponding to individual fitness. The higher the fitness is, the more the individual produces the next generation of individuals. The individual with less fitness will be suppressed or discarded. Crossover includes two steps. First, it takes a pair of mating individuals from a mating pool chosen randomly, then it randomly produces a cross position that the two individuals exchange information, produces new individuals representing different points in the solution space, enables the genetic algorithm search region to be wider. But the reproduction and crossover cannot ensure no loss of some important genetic things. So mutation is introduced. Mutation refers to some bits of a character string changing suddenly, 0 to 1 or 1 to 0. Thus new information is produced in a bit unit. At the same time this can promote the efficiency of genetic algorithm search to some extent. But the quantity of patterns processed is:

O(N³).This is just what the parallel mechanism genetic algorithms are and why genetic algorithms work so efficiently. Under the action of genetic operators acting on the population, the estimation of performance can be done. The average performance of it increases step by step. The solution of the related problem converges to its optimization.

Genetic algorithms are obviously different from other search methods. They are parallel searches. They estimate and operate on a population, and search several points at the same time while the population evolves, and greatly decrease the possibility of trapping into local optimization. Meanwhile, the existence of mutation ensures theoretically that genetic algorithms can search any point of the space. This strengthens genetic algorithms. Next, genetic algorithms use code forms rather than operating on parameters. They enable us to regroup information in bit unit. They use only the target function problems needed to work. They do not need any other precondition or additional information. Meanwhile, genetic algorithms are probabilistic searches rather than determinative transformations.

This leads to non-determinativeness in natural selection.

Popular study topics

Since genetic algorithms have many special features, several popular study topics about them now are:

• How to encode to achieve effectiveness, reasonableness and generality. Generally coding methods should enable the code length to be short,the bit number defined small and should be problem related. Codes should be at minimum, such that the character list represents problems naturally. Binary codes are often chosen.

• How to define the population size N, occurring probabilities P_cand P_m of crossover and mutation respectively. Genetic algorithms are sensitive to the definition and the maintenance of population size. As to maintaining versatility of individuals in size so as not to trap into local solution, it seems better that the size is larger. But this will increase computation obviously as well as influencing individual competition. Crossover and mutation probabilities are defined according to the problem. Crossover probability is often taken over 0.5 so as to enable the interchange of information enough in a character string. Goldberg gives a group of reasonable parameters in his special book (Goldberg, 1993): population size is 20 to 30;crossover probability P_c is in [0.75, 0.95]; mutation probability P_mis in [0.005, 0.01].

• How to choose the fitness function to estimate the performance of population? This is another key problem in a genetic algorithm. Fitness function estimation is the unique criterion in a genetic algorithm to guide search direction. There is no other information to guide evolution. At first, the fitness value should be non-negative. Next, the optimal direction of target function should be in the direction of fitness increasing.

  For minimization problems,the fitness function is of the following general form:

  (1)

  where C_max is an input parameter or a theoretically maximum value or its computation changes according to an algebra. g(x) is often a function related to the differential of parameter set x. The more the parameters are close to the true value, the less the differential is. The less g(x) is, the bigger the fitness value is.

Using GA method to predict production

Models to predict production of an enterprise can be generally described as the following equation:

(2)

where f is a stable nonlinear function in the sense of the Lyapunov meaning.W = (w₁,..., w_r)^Tis a vector of r fixed parameters. Y = (y(k­l), ..., y(k­n))^Tis a vector of n self recursive items. U = (u(k­l), ..., u(k­m))^Tis a vector of m past input values.

Suppose the structure of f is given. Then equation (1) can be estimated by:

(3)

where W~ = w~₁, ..., w~_r)^Tis a vector of r estimated parameters. Y~ = (y~(k­1), ..., y~(k­n))^Tis a vector of n output values estimated. U is defined as the same as the above.

According to pre-experience, the region of fixed parameter vector W~ can be defined initially. Then according to the precision it is going to reach, each parameter w~_k (k=l, ..., r)should be defined. For example, if each parameter w~_k distribute in [­2^1­1,2^1­1] and the identification precision is less than 2^­m,then each parameter needs l+m bit binary codes to represent. So the string length of the solution is r*(l+m). The identification strategy is to use GA to search the optimal parameter vector W~ such that y~(k) is close to y(k).

The error of the jth (j=i, ..., N)string in the ith generation is defined as

(4)

where d represents data length. y~_ji() is the estimated output of jth string in the ith generation.

Fitness function (the jth string in the ith generation) is chosen as

(5)

where C_max is related to a concrete problem.

After the fitness value of each individual in the population is calculated, it is required to be normalized.

At first, the average fitness value is found as :

(6)

Then the normalized fitness is calculated by

(7)

In the preceeding genetic operations, the simplest reproduction method is to put normalized values in round numbers according to the round principle. That is the function of individuals which evolve into the next generation.

For parametric estimation, genetic algorithms follow the following steps:

• 1.

  Initialize population randomly, i.e produce N strings;

• 2.

  Decode strings to find w~_k, and find y~(k) according to equation(3);

• 3.

  Simplify system's real output y(k),and then calculate e_jiaccording equation (4);

• 4.

  Estimate individual performance according to fitness function, and calculate the whole average performance.

• 5.

  Do parameters converge to the defined precision or simulation steps reach maximal? If the answer is yes, then the algorithm ends.

• 6.

  Evolve the next generation according to normal fitness value and proceed with crossover and mutation according to probabilities.

Go to step (2).

Experiments

Suppose that the predicting production model is as follows:

where the input signals are uniformly distributed in [­3.0, 3.0]. Measurement noise ×(k) is distributed uniformly in [­0.5, 0.5]. Numbers 0.4 and 5.2 are constants. Other coefficients are all parameters to be estimated. According to our experience and knowledge, these parameters all fall in [­4.0, 4.0]. Identification precision is 0.001. Each parameter can be represented in 10 binary bits. So the parameter set string length is 9*10=90 bits.

Take the population size N as 35. Crossover and mutation possibilities are 0.9 and 0.005 respectively. Fitness function C_max takes the values segmentally. At the initial step, the value of C_max can be big enough to allow versatility of individuals,for example, C_max = 1.9*d. Later, competition is emphasized, C_maxcan be changed to take a small value, for example C_max = 1.5*d, where 45<d<90 so as to balance computational speed and fitness function reliability.

Square sum of the errors of population's normalized fitness and average fitness are used to define convergence. If

where × is used to define a convergent region and it is supposed that × <0.0001, then population is considered to be convergent. At the time after 1,900 generations the individuals with high fitness in the population just converge to the optimization.

Conclusion

This communication suggests a genetic algorithm method for predicting production. A genetic algorithm has many significant advantages compared with other analytical methods. It does not need the calculation of the differential of a function nor the assumption of being linear. It is not related to the criterion of data error. On the other hand, it is global, less probable to be caught in local optimization. It also avoids the dependence on initial data.

Wu ChenDepartment of Electronics and Information, East China Shipbuilding Institute, Zhenjiang, P.R. China