现在位置: >

*computation techniques have mostly been used to solve various optimization and learning problems. This paper describes a novel application of evolutionary computation techniques to equation solving. Several combinations of evolutionary computation techniqu*

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION,VOL.4,NO.3,SEPTEMBER2000295

Solving Equations by Hybrid Evolutionary Computation Techniques

Jun He,Jiyou Xu,and Xin Yao

Abstract—Evolutionary computation techniques have mostly been used to solve various optimization and learning problems. This paper describes a novel application of evolutionary com-putation techniques to equation solving.Several combinations of evolutionary computation techniques and classical numerical methods are proposed to solve linear and partial differential equations.The hybrid algorithms have been compared with the well-known classical numerical methods.The experimental results show that the proposed hybrid algorithms outperform the classical numerical methods significantly in terms of effectiveness and efficiency.

Index Terms—Adaptation,hybrid algorithms,linear equations, partial differential equations.

I.I NTRODUCTION

T HERE has been a huge increase in the number of papers and successful applications of evolutionary computation techniques in a wide range of areas in recent years.Almost all of these applications can be classified as evolutionary optimization (either numerical or combinatorial)or evolutionary learning(su-pervised,reinforcement,or unsupervised).This paper presents a very different and novel application of evolutionary computa-tion techniques in equation solving,i.e.,solving linear and par-tial differential equations by simulated evolution.

One of the best-known numerical methods for solving linear equations is the successive overrelaxation(SOR)method[1]. However,it is often very difficult to estimate the optimal re-laxation factor,which is a key parameter of the SOR method. This paper proposes a hybrid algorithm combining the SOR method with evolutionary computation techniques.The hybrid algorithm does not require a user to guess or estimate the op-timal relaxation factor.The algorithm“evolves”it.

Unlike most other hybrid algorithms where an evolutionary algorithm is used as a wrapper around another algorithm(often a classical algorithm),the hybrid algorithm proposed in this paper integrates the SOR method with evolutionary computation tech-niques,such as recombination and mutation.It makes better use of a population by employing different equation-solving strategies for different individuals in the population.Then these individuals can exchange information through recombination. Experimental results show that the hybrid algorithm can solve equations within a small fraction of time needed by the classical SOR method for a number of problems we have tested.

Manuscript received September28,1999;revised February3,2000.This work was supported in part by the State Key Laboratory of Software Engi-neering,Wuhan University,Wuhan,China.

J.He and J.Xu are with the Department of Computer Science,Northern Jiao-tong University,Beijing100044,China(e-mail:jhe1998@http://doc.guandang.net).

X.Yao is with the School of Computer Science,University of Birmingham, Edgbaston,Birmingham B152TT,U.K.(e-mail:x.yao@cs.bham.ac.uk). Publisher Item Identifier S1089-778X(00)04472-6.

Built on the work of solving linear equations,this paper also proposes two hybrid algorithms for solving partial differential equations,i.e.,the Dirichlet problem[2].Both hybrid algo-rithms use the difference method[2]to discretize the partial differential equations into a linear system first and then solve it. Fogel and Atmar[3]used linear equation solving as test problems for comparing recombination and inversion operators and Gaussian mutation in an evolutionary algorithm.A linear system of the

form

was used in their study.The worth of an individual that

encoded

(1)

where

diag

相关文档

相关主题

热门文档