Subscribe Now Subscribe Today
Research Article
 

The Solution to Linear Variation Inequality by Evolution Strategies



Zhang Ming, Zhou Yong-quan and Ahmed N. Abdalla
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

This study presents a solution to linear variation inequality by evolution strategies based on the question that iterative algorithm of traditional numerical computer can not satisfy parallel in solving variation inequality. The numerical solution that evolution strategies are used to solve linear variation inequality, which sufficiently exerted the advantage of evolution strategies such as group search and global convergence and it satisfies the question of parallel solute the linear variation inequality in engineering technique. The numerical computation results indicate that the algorithm offers an effective way to solve linear variation inequality, high convergence rate, high accuracy and robustness.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Zhang Ming, Zhou Yong-quan and Ahmed N. Abdalla , 2007. The Solution to Linear Variation Inequality by Evolution Strategies. Journal of Applied Sciences, 7: 1181-1185.

DOI: 10.3923/jas.2007.1181.1185

URL: https://scialert.net/abstract/?doi=jas.2007.1181.1185

INTRODUCTION

Linear variation inequality problem is a fundamental field of research in operation research and plays a significant role in differential equation, mechanics, cybernetics, game theory, economy and finance, transport and many other fields. Linear variation inequality problem can be described: Suppose K is a nonempty closed convex subset of Rn, we want to find a vector x*εK such that the inequality

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
(1)

Holds for all yεK, where M = (Mij)n*n is a n*n real matrix, p = (p1, p2,…, pn)TεRn. So far, there are several methods developed for solving the problem, such as iterative methods, projection methods, Newton methods and so on (Dafermos, 1983; Taji et al., 1993; Marcotte and Wu, 1995; Jian Jinbao and Yanlian, 1997). It usually claims parallel solving linear variation inequality problem in engineering and technology, but the iterative algorithm that based on traditional digital computer is hard to satisfy the demands of parallel solving. Furthermore, the convergence of iterative methods has much to do with the selection of initial values. So it has important actual meaningful to parallel solving the problem (1) by studying and using evolution strategies.

The evolution strategies algorithm (Schwefel and Back, 1995a,b; Zhi and Tao, 2000; Qingxia, 1997) with global convergence is another research hotspot in design optimization in recent years. Evolution strategies is an intelligence optimization algorithm that imitative natural selection and heredity mechanism, which was put forward by (Schwefel, 1965) in order to research the fluid mechanics of wind tunnel. Evolution strategies is a self adaptation and stochastic algorithm, which originates from the Evolution Theory Darwinian. The algorithm comes from the simple natural evolution model. A population is made up of a test point set of objective function search space. Every individual's fitness can be decided by the objective function value of the corresponding test points. Every individual's reproduction rate depends on the relative fitness of the individual in current population. They select parents (test points) in the population according to the reproduction rate and selection operator. The selected parents can generate the offspring by recombination and mutation. The recombination stochastic combine the genetic information of parents while the mutation stochastic change the genetic information of parents. The two obvious features are hidden parallelism and population global search. Furthermore, evolution strategies are extremely robust, which has unique predominant performance for solving some complex nonlinear systems. The algorithm has been commonly used in disposing varied optimizations at present, such as the training and design of neural network, system identification, robotic control, machine learning and many other fields.

This study presents a solution to solve linear variation inequality by evolution strategies based on the global convergence and parallel search of evolution strategies algorithm. The algorithm can actualize parallel search in the feasible region and convergent to the global optimal solution, which efficiently overcome the defect that the traditional methods can't parallel solute the linear variation inequality in engineering technique. The numerical computation results indicate that the algorithm has high convergence rate and high accuracy. It is a very effective way to solve linear variation inequality, which is comfortable for facilitating practical application.

THE THEORY OF LINEAR VARIATION INEQUALITIES

In this study, we select the 2-norm as the vector norm. For explicitness, we define:

K = {xεRn | ¨Ox = (x1,x2,L,xn)T, xiε [ai,bi], I =1,2,…,n}

Where ai≤=biq = (q1,q2,…,qn)Tε. We define the function:

Fk (q) = (Fk(1) (q1), Fk (2) (q2), L, Fk (I) (qi), L, Fk.(n) (qn))T

Where

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
(1)

Obviously, FK(I) (qi) is a monotone continuous function whose global Lipschitz constant is 1.

Lemma 1: (Eaves, 1971; Mosco, 1985) The necessary and sufficient condition for x* is a solution to the problem (1) is if and only if

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
(2)

Lemma 2: (Zhanquan et al., 1999). The Eq. (2) has the solution in K.

Proof: Let H(x) = FK(x-Mx-p), then H is a continuous operator from Rn into itself, so it is a compact operator. H is a mapping from K to K too, so H (x) has a fixed point in K at least, namely the equation (2) has the solution in K.

STANDARD EVOLUTION STRATEGIES

We describe the process of standard evolution strategies simply (Qingxia, 1997):

Step 1: Determine the expressive form of the problem. Every individual of the expression is made up of goal variation X and standard deviation σ, each part also has n components. Namely,

(X, σ) = ((x 1, x 2, ..., xi, ...., xn), (σ1, σ2, ...., σi, .... σn))

The relations between X and σ are

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
(3)

where (xi, σi) denotes the ith component of the above generation's individual, denotes the ith component of the offspring's individual, N(0,1) denotes the stochastic numbers that obeys standard normal distribution, Ni(0,1) denotes recreating the stochastic numbers that obeys standard normal distribution according to the ith components, ri denotes global coefficient which always choose 1 and r denotes local coefficient which always choose 1. The above formula indicates that the new individuals are generated from the old individuals.

Step 2: Initialize population with random and compute these fitness. The initial population of the evolution strategies is made up of μ individuals. Every individual (X, σ) includes n xi and σi components. The method of generating initial population generates randomly. In order to compare with the traditional methods, we can start from some starting point (X (0), σ (0)), which generates μ initial individuals by multiple mutation. The initial point can randomly select from the feasible region and the standard deviation of the initial individual is σ (0) = 3.0.

Step 3: Compute the fitness of the initial individuals. If it satisfies the conditions, then terminate. If not, carry on.

Step 4: Generate the new population with the following operations in accordance with the evolution strategies.

Recombination. Generate the new individuals by exchanging the goal variations and the standard deviations of the two parent individuals. The goal variation adopts discrete recombination in general and the standard deviation always adopts mean recombination.
Mutation. We adds stochastic variations to the recombinant individuals and generates the new individuals in term of the formula (3).
Compute the new individuals' fitness.
Selection. We select the good individuals, to make up of the next generation population in term of the strategy of selection (μ, λ).

Step 5: Repeat execute the step 4 until it satisfies the termination conditions and then select the best individual as the result of the evolution strategies.

IMPROVED EVOLUTION STRATEGIES

We know the one dimension Cauchy density function concentrates on the origin's neighborhood, which can be defined (Gehlhaar and Fogel, 1997):

Image for - The Solution to Linear Variation Inequality by Evolution Strategies

where t denotes a proportional parameter. The corresponding distribution function can be defined:

Image for - The Solution to Linear Variation Inequality by Evolution Strategies

The density function ft(x) is similar to the Gaussian density function. The differences between the Cauchy density function and the Gaussian density function are as following: The Cauchy distribution is a little smaller than the Gaussian distribution in vertical direction, but the Cauchy distribution is next to horizontal axis in horizontal direction and it is slower for the Cauchy distribution. So, the Cauchy distribution can be seen infinite. The relations between the Cauchy density function and the Gaussian density function can be seen in Fig. 1.

The Cauchy distribution easily generates a random number which is far away the origin, according that the Cauchy distribution has the high two wings probability characteristics. The random numbers generated by the Cauchy distribution have more breadth distribution than the Gaussian distribution.

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
Fig. 1: Compared the Cauchy distribution (t =1) with the Gaussian distribution (π (0,1))

It means that the evolution maybe jump out the local minimal area with the Cauchy distribution quickly using Cauchy mutation generate the offspring. However, the Cauchy distribution's small middle part is its weakness which cuts down the performance in accurate local search. But the Gaussian mutation operator can make the population meticulous search in local space. In order to exert their advantage, it presents an eclectic scheme in the thirteenth documentary, which combines the Cauchy mutation operator with the Gaussian mutation operator and defines a new mutation operator which is called mean mutation operator. So, the new mutation form is

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
(4)

where ½(ηi + Ni(0,1)) is mean mutation operator and the parameter çi is a proportional parameter which obeys the Cauchy distribution when t equals 1. It is used to renew each component. The other parameters equal the parameters of the formula (3).

THE ALGORITHM PROCESS OF SOLVING LINEAR VARIATION INEQUALITY BY EVOLUTION STRATEGIES

Solving the linear variation inequality can be converted function optimization in the field K. Obviously, the solution x* to the variation inequality is the best solution to the function optimization.

Step 1: Determine the expression form of the problem. Every individual of the expression is made up of goal variation X and standard deviation σ, which each part also has n components. Namely,

Image for - The Solution to Linear Variation Inequality by Evolution Strategies

where x1, x2, …, xn are the components of the vector x*, n denotes the dimension of the vector x*.

Step 2: Initialize population with random. The initial population of the evolution strategies is made up of μ individuals. Every individual includes xi and σi components. The method of generating initial population is random. In order to compare with the traditional methods, we can start from some starting point (X(0),σ (0)) which generates μ initial individuals by multiple mutation. The initial point can randomly select from the feasible region and the standard deviation of the initial individual is σ (0) = 30.

Image for - The Solution to Linear Variation Inequality by Evolution Strategies
Fig. 2:
a)The numerical distribution map of the fitness of initial population's individual; b) the numerical distribution map of the fitness of the population's individuals when termination and c) the variety of the best fitness of each generation in evolution

Step 3: Compute the fitness x* is the solution to the formula (1) when x* = FK (x*-Mx*-p) according to the formula (2). Let

y' = x - FK ( x- Mx -p)

we know y' = y'1, y'2, …, y'n, y'εK, so we select the fitness function

Image for - The Solution to Linear Variation Inequality by Evolution Strategies

The solution x* to the formula (1) is the value which makes f (x*) = 0. Suppose e = f (x), then the accurate solution x* to the formula (1) is the value of x which makes e = 0. The smaller of the value of e is, the better of the similar to the solution to the formula (1) is. We select the fitness function e and select ε near to zero for the termination conditions. The evolution terminate when the value of the fitness is smaller than ε.

Step 4: If it satisfies the conditions, then terminate. If not, carry on.

Step 5: Generate the new population with the following operations in accordance with evolution strategies.

Recombination. Generate the new individuals by exchanging the goal variation and the standard deviation of the two parent individuals. The goal variation always adopts discrete recombination and the standard deviation always adopts mean recombination.
Mutation. Add stochastic variations to the recombinant individuals and generate the new individuals in term of the formula (4).
Compute the new individuals' fitness as the step 3.
Select. Select the good individuals and make them composite the next generation population in term of the strategy of selection (μ, λ) (Fig. 2).

Step 6: Repeat execute the step 5 until it satisfies the termination conditions and select the best individual as the result of the evolution strategies.

SIMULATION RESULT

In this study, we solve the linear variation inequalities by (Table 1) evolution strategies for Example.

Let n = 2, μ = 15, λ =100, ε = 10–10.

K = [0, 2]x[0, 2]x[0, 2]x[0, 2]x[0, 2]x[0, 2]x[0, 2]x[0, 2]

Table 1: The simulated results of the solution of the liner variation inequalities (5)
Image for - The Solution to Linear Variation Inequality by Evolution Strategies

Image for - The Solution to Linear Variation Inequality by Evolution Strategies

We want to find a vector x*εK such that the inequality holds for all yεK.

(y- x*)T (Mx* +p)≥0 (5)

CONCLUSIONS

This study presents a solution to linear variation inequality by evolution strategies based on the advantage of evolution strategies such as group search and global convergence. We select the mean mutation operator in order to get quick convergence. The Algorithm avoids the trivial deviate operation in solving linear variation inequalities with traditional methods, whose parallelism satisfies the question of parallel solving the linear variation inequality in engineering technique. Global convergence to the best solution, high accuracy, high convergence rate and parallelism make the algorithm easily use in engineering.

REFERENCES
1:  Dafermos, S., 1983. An iterative scheme for variation inequalities. Math. Programming, 6: 40-47.

2:  Eaves, B.C., 1971. On the basic theorem of complementarily's. Math. Program 5: 68-75.

3:  Gehlhaar, D.K. and D.B. Fogel, 1997. Two new mutation operators for enhanced search and optimization in evolutionary programming. Proc. SPIE, 31: 260-269.
Direct Link  |  

4:  Jinbao, J. and L. Yanlian, 1997. Some sorts of methods for solving variation inequalities. J. Applied Mathematics Chinese Univ., 14: 197-212.

5:  Marcotte, P. and J.H. Wu, 1995. On the convergence of projection methods: Application to the decomposition of affine variation inequalities. J. Optima. Theory Applic., 85: 347-362.
Direct Link  |  

6:  Mosco, U., 1985. Introduction to Approximate Solutions for Variation Inequalities (M). Science and Technology of Shanghai Press, Shanghai, China.

7:  Qingxia, Y., 1997. Evolutionary Algorithm [M]. Metallurgical Industry of Beijing Press, Beijing.

8:  Schwefel, H.P. and T. Back, 1995. Evolution Strategies I: Variants and Their Computational Implementation. Wiley, London, pp: 111-126.

9:  Schwefel, H.P. and T. Back, 1995. Evolution Strategies II. In: Theoretical Aspects, Winter G. (Ed). Wiley, London, pp: 127-140.

10:  Taji, K., M. Fukushima and T. Ibaraki, 1993. A globally convergent Newton method for solving strongly monotone variation inequalities. Math. Programming, 3: 369-383.
Direct Link  |  

11:  Zhanquan, W., Z. Chaoyi and Y. Qingxia, 1999. Study on improvement of mutation operator in evolutionary strategies. Comput. Simulation, 16: 8-11.

12:  Zhi, Z.W. and B. Tao, 2000. Evolutionary Computation (M). University of Science and Technology of Defense Press, UK.

©  2021 Science Alert. All Rights Reserved