Application of the Outbreeding Elitist Adaptive Genetic Algorithm in High Meteorological Detection＊

SUN Baojing

（Department of Electronic Reconnaissance and Command，Shenyang Artillery Academy，Shenyang 110867，China）

Application of the Outbreeding Elitist Adaptive Genetic Algorithm in High Meteorological Detection＊

SUN Bao－jing

（Department of Electronic Reconnaissance and Command，Shenyang Artillery Academy，Shenyang 110867，China）

On the basis of analyzing the feature of the outbreeding elitist and adding the evolution of slave population，the outbreeding elitist adaptive genetic algorithm（OEAGA）is presented，and in according with the characteristics of the huge amounts，complicated and unpredicted change of the high meteorological detecting data，the OEAGA is utilized to compute the B－spline knots so that the optimal B－spline curve which is fitting the high meteorological detecting data curve under the accuracy requirement，can possess less control vertexes.Compared with the result of the B－spline curve with the standard genetic algorithm to compute knots，the B－spline curve with the OEAGA is better，and experiments indicate that the OEAGA has stronger searching performance and higher converging efficiency.

outbreeding elitist；B－spline curve fitting；meteorological detecting

1 Introduction

At present，the primary method of processing the high meteorological detecting data is to divide the whole detecting height interval into several parts，and then calculate the required meteorological data at the prescriptive heights；finally the required meteorological data at other heights can be calculated through interpolating the results calculated from the prescriptive heights.This method makes big truncation error and rounding error and makes many detecting data useless because the required meteorological data at most heights are obtained from the results of the prescriptive heights［1］.

As the continuous improvement in robotization of the meteorological detecting and operating equipments，it is more imperative to increase the accuracy and efficiency of processing meteorological detecting data.Because of the influence of some uncertain natural conditions，the high meteorological detecting data have the feature of huge amounts，complicated and unpredicted trend of changes［2］，especially complicated the temperature－h(huán)eight curve which is composed of over 2 000 sets of temperature and height data.It is hard to fit the temperature－h(huán)eight curve with traditional fitting measure.

Non－uniform B－spline curve fitting has three important factors：parameterization of raw data，node vectors and control vertexes.How to optimize the relation of these three factors will determine whether it can be achieved to calculate the optimal non－uniform B－spline curve with less control vertexes to fit theplane orderly data under the given precision.

So far，there are some references to apply genetic algorithm to optimize such relation.Thereinto，references［3－4］put forward the special coding way to increase the fitting accuracy，but when the number of raw data is so large，it makes each chromosome have large numbers of genes，so that the calculation speed and convergence speed are reduced greatly.Reference［5］puts forward the coding way to improve the calculation efficiency，but ignores the relation between node vectors and parameterization of raw data.Reference［6］puts forward a new method of optimizing production of the initial population，but such the fitting algorithm is based on simple genetic algorithm that has poor ability of global convergence and easily converges into the local optima.

In this paper，we define the outbreeding elitist，present the outbreeding elitist policy，produce the slave population，and improve the accuracy of fitting the high meteorological detecting data curve by the optimal non－uniform B－spline curve with less control vertexes.

2 B－Spline Least Square Fitting

Supposing the number of plane orderly data is m＋1，they are q0，q1，q2，…，qm（m＞n），and the degree of fitting curve is k（k≥1），we try to calculate such a B－spline curve with k－th degree

satisfying q0＝p（0），qm＝p（1），and other data qi（i＝1，2，…，m－1）are approximated by least squares method［7］，and the following function

has a minimum value about n－1 control vertexes，which are dj（j＝1，2，…，n－1），where Nj，kis k－th degree basic spline function，U is node vectors ofis parametric value of plane orderly data.And U has its interval｛u0＝u1＝…＝uk≤uk＋1≤…≤un≤un＋1＝…which is calculated by the method of accumulating chords，has its interval

Equation（1）can be represented by matrixes

where N is the matrix of basic spline function，P is the matrix of plane orderly data，and D is the matrix of control points.When the condition is k＜n＜m，the approximate solution of equation（2）can be calculated by least squares method［7－9］，then the matrix of control points D is

From equation（3）we can see，the matrix D is related to the parametric value of raw data and node vectors.How to optimize the relation of such three important factors for the non－uniform B－spline curve to satisfy fitting precision demand，is a complicated nonlinear optimization problem.

3 Outbreeding Elitist Adaptive Genetic Algorithm

3.1 Adaptive Genetic Operator

In this paper，we apply binary coding，use the method of normalized accumulating chords to calculate the parametric value of plane orderly data U－，take node vector as gene code，and apply the method of equally－distributed node vector proportionately to generate genes of chromosomes in initial population［6］.

In order to minimize the fitting error and the amount of the control vertexes of the B－spline curve，the fitness function is defined as

where err is least squares error，Num＿pt is the number of control vertexes，andλis parameter of adjusting control vertexes number.

Crossover rate and mutation rate are significant to the genetic performance.If crossover rate is too much larger，the excellent genetic model and the chromosomes with superior fitness are easily destroyed.If crossover rate is too much smaller，the global searching performance is very poor.If mutation rate is too much larger，the randomicity of the genetic algorithm search becomes so strong to reduce the global converging efficiency，and then it is hard to produce new better chromosomes while the mutation rate is too much smaller.

In the middle and later periods of evolution，chromosomes gradually converge to the local optima，especially the chromosomes with fitness all above the average fitness of the whole population have an increasing percentage in the population.In the later periods of evolution，these better chromosomes lead the direction of evolution.In order to highlight the distance in the population space between these better chromosomes and the local optima，we use the average fitness of all the chromosomes with fitness above the average fitness of the whole population to distinguish between superior and inferior chromosomes，then the crossover rate rcand the mutation rate rmare defined as

where f is the fitness of a chromosome，favg＿eliteis the average fitness of all the chromosomes whose fitness is above the average fitness of the whole population，and pc1，pc2，pm1and pm2are the genetic parameters predetermined.

3.2 Outbreeding Elitist Policy

Rich population diversity is the basic requirement for genetic algorithm to search the global optima.In the early periods of evolution，population diversity is at high lever，and the chromosomes similarities are very low，so genetic algorithm has high converging efficiency.In the middle and later evolution periods，the superior chromosomes converge to the local optima，meanwhile，the chromosomes with fitness below the average fitness of the whole population are distributed more discretely，and their survival probability becomes smaller，so the population diversity is lower and lower.

When the population diversity is at lower lever for several generations，genetic algorithm maybe has searched the global optima or the deceptive problems may happen and genetic algorithm is converged to the local optima［10－12］.To some extent，the genetic algorithm convergence is the process of searching the global optima as soon as possible under the condition of keeping the population diversity as high as possible［13］.

Based on analyzing the population diversity deeply，we find that it is relevant to the similarities of two individual chromosomes，especially the similarities of the local optima and other chromosomes.In the process of evolution，the inferior chromosomes are more likely to be eliminated，and some of them are long－distance from the local optima and with inferior fitness but maybe in the area containing the superior optima.Especially those chromosomes with fitness above the average fitness of population are longdistance from the local optima but maybe in the area containing the superior optima.To make these spe－cial kinds of chromosomes be exerted adequately during the process of evolution is very helpful for searching the area containing the global optima，keeping the population diversity rich and improving the performance of the genetic algorithm global search.

So in this paper，the outbreeding elitist policy is presented.It means that in every evolutional generation these special kinds of chromosomes and local optima are copied to the slave population，and when the number of chromosomes in the slave population reaches the threshold，the slave population starts its evolution with its own evolution operator.If the local optima keeps the same in the master population after certain evolution times，the inferior chromosomes in the master population are replaced by the superior chromosomes in the master population.

According to the outbreeding elitist policy，the following definitions are offered.

Definition 1 The average fitness of the population.

Suppose the population size is n in the t－th generation，the population is，the fitness of each individual chromosome is respectively f，then the average fitness of the population in the t－th generation is

Definition 2 The distance of two individual chromosomes.

In the binary coding population Pt＝｛a1t，a2t，a3t，…，ant｝（ait＝｛ai1t，ai2t，ai3t，…，aiLt｝），the number of genes in every chromosome is L，then the distance from the chromosome aitto the chromosome ajtin population space is

Definition 3 The outbreeding elitist.

Suppose the population in the t－th generation is Pt，in which the local optima i（m∈［1，n］），whose fitness is fThe fitness of chromosome ai≠m）iis equal to or larger than favg＿tand the distance disi，mbetween chromosomthe maximum among the distances between the optimaand all the chromosomes whose fitness is larger than favg＿t，then the chromosome amtis called as the outbreeding elitist and written as

Definition 4 The slave population.

Before the master population begins to evolve，the slave population is empty.When the local optimaof the t－th（t≥1）generation is larger than the local optima amt－1of the t－1－th in the master population，andare copied to the slave population.When the number of chromosomes in the slave population reaches the threshold NumS，the slave population begins to evolve.

Because the chromosomes in the slave population are excellent and discrete，only crossover and mutation operators are performed.In the process of the crossover operation in the slave population，all the chromosomes participate the crossover operation randomly by twos，and only when the offspring chromosome is superior to both the parent chromosomes，the offspring can survive.In process of mutation operation in the slave population，only when the offspring chromosome is superior to its parent chromosome，the offspring can survive.

When the number of chromosomes in the slave population reaches n，the superior offspring chromosomes replace the worst parent chromosomes to sustain the slave population size as n.When the offspring chromosomes whose amount is u in the slave population，are superior toin the master popula－tion，these offspring chromosomes replace u worst chromosomes of the master population in the t－th generation.

The time threshold TimePis set up as the maximum residence time of the master population evolution.When the local optima in the master population keeps the same for TimePgenerations，the algorithm is judged to converge to the local optima，then a quarter of chromosomes in slave population are selected randomly to replace one quarter of chromosomes in master population.

4 Application

The detecting data from the GZZ8 type electrical air－sounding equipment with NO.087233 is taken as fitting example which is also the example of the reference［6］.The detecting data have 2 039 sets of temperature and height data，and 1 177 sets of feature points.

Considering the computation efficiency and the variation trend of the detecting data curve，the whole detecting data curve is divided into 7 parts which are fitted respectively.In every fitting part，we set up the following parameters：λ＝0.005，pc1＝0.8，pc2＝0.5，pm1＝0.1，pm2＝0.001，the mutation rate of the slave population r＝1／L.The data of standard GA in the following tables are from refersm－ence［6］.

（1）In part 1，there are 167 couples of data.The following parameter values are configured：n＝40，L＝60；the fitting results comparison between the standard GA and the OEAGA is shown in table 1.

Table 1 First Part of GA and OEAGA Fitting Results

（2）In part 2，there are 243 couples of data.The following parameter values are configured：n＝40，L＝60；the fitting results comparison between the standard GA and the OEAGA is shown in table 2.

Table 2 Second Part of GA and OEAGA Fitting Results

（3）In part 3，there are 142 couples of data.The following parameter values are configured：n＝40，L＝80；the fitting results comparison between the standard GA and the OEAGA is shown in table 3.

Table 3 Third Part of GA and OEAGA Fitting Results

（4）In part 4，there are 217 couples of data.The following parameter values are configured：n＝60，L＝120；the fitting results comparison between the standard GA and the OEAGA is shown in table 4.

Table 4 Fourth Part of GA and OEAGA Fitting Results

（5）In part 5，there are 156 couples of data.The following parameter values are configured：n＝60，L＝80；the fitting results comparison between the standard GA and the OEAGA is shown in table 5.

Table 5 Fifth Part of GA and OEAGA Fitting Results

（6）In part 6，there are 114 couples of data.The following parameter values are configured：n＝60，L＝120；the fitting results comparison between the standard GA and the OEAGA is shown in table 6.

Table 6 Sixth Part of GA and OEAGA Fitting Results

（7）In part 7，there are 138 couples of data.The following parameter values are configured：n＝60，L＝80；the fitting results comparison between the standard GA and the OEAGA is shown in table 7.

Table 7 Seventh Part of GA and OEAGA Fitting Results

The fitting results comparison between the standard GA and the OEAGA indicates that in the middle and later periods of evolution the searching performance and the fitting precision of the OEAGA is greatly improved and the amount of control vertexes decreases，which demonstrates that the outbreeding elitist plays an important role in evolution.

5 Conclusion

Based on analyzing the characteristics of the outbreeding elitist and adding the evolution of slave population，this paper presents the outbreeding elitist adaptive genetic algorithm（OEAGA）and applies the OEAGA to calculate the optimal non－uniform B－spline curve with less control vertexes to fit the high meteorological detecting data curve.Compared with the result of the B－spline curve with the standard GA，the B－spline curve fitting with the OEAGA improves the fitting precision and converging speed greatly.

In the interval of nodes，cubic non－uniform B－spline curve is infinitely differentiable，which makes itpossible to calculate meteorological trajectory elements with continuous functions.

Reference：

［1］ SUN Bao－jing.Research About Artillery Air Defence Force’Meteorological Information System［D］.Shenyang：Northeastern University，2004.

［2］ QU Yan－lu.Survey of Exterior Ballistic Meteorology［M］.Beijing：Meteorological Press，1987：59－176.

［3］ FUJICHI YOSHIMOTO，TOSHINOBU HARADA，YOSHIHIDE YOSHIMNTO.Data Fitting with a Spline Using a Real－Coded Genetic Algorithm［J］.Computer－Aided Design，2003，35：751－760.

［4］ SUN Yue－h(huán)ong，WEI Jian－xiang，XIA De－shen.Parameter Optimization for B－Spline Curve Fitting Based on Adaptive Genetic Algorithm［J］.Journal of Computer Applications，2010，30（7）：1 878－1 882.

［5］ MU Guo－wang，ZANG Ting，ZHAO Gang.Using the Modified Genetic Algorithm to Determine the Knots of B－Spline Curves［J］.Computer Engineering and Applications，2006，42（11）：88－90.

［6］ LI Jian－bao，ZHANG Tie，SUN Bao－jing，et al.Application of Non－Uniform B－Spline Curve Fitting Based on Genetic Algorithm in High Meteorological Detection［C］.The 2011 Chinese Control and Decision Conference，2011.

［7］ ROGERS D F，F(xiàn)OG N G.Constrained B－Spline Curve and Surface Fitting［J］.Computer－Aided Design，1989，21（10）：641－648.

［8］ JOE B.Quartic Beta－Splines［J］.ACM Transactions on Graphics，1990，9（3）：301－337.

［9］ BARSHY A.Determinging a Set of B－Spline Control Vertices to Generate an Interpolating Surface［J］.Graphics and Image Processing，1980，42（7）：191－195.

［10］ LI Mao－jun，F(xiàn)AN Shao－sheng，TONG Tiao－sheng.The Application of Partheno－Genetic Algorithm in Pattern Clustering Problem［J］.Engineering Applications of Artificial Intelligence，1999，12（2）：175－184.

［11］ CORREA R C，F(xiàn)ERREIRA A，REBREYEND P.Scheduling Multiprocessor Tasks with Genetic Algorithms［J］.IEEE Trans.on Parallel and Distributed Systems，1999，10（8）：825－837.

［12］ FUMIAKI T，TOSHINIRO N，SIGERUO.Banknote Recognition by Means of Optimized Masks，Neural Network and Genetic Algorithms［J］.Engineering Applications of Artificial Intelligence，1999，12（2）：175－184.

［13］ HE Da－kuo，WANG Fu－li.Improving the Global Convergence of the Genetic Algorithm［J］.Journal of Northeastern University：Natural Science，2003，24（6）：511－514.

遠(yuǎn)緣選優(yōu)策略遺傳算法在高空氣象探測(cè)中的應(yīng)用

孫寶京

（沈陽(yáng)炮兵學(xué)院電子偵察指揮系，遼寧沈陽(yáng) 110867）

在分析遠(yuǎn)緣優(yōu)質(zhì)個(gè)體的特點(diǎn)和對(duì)從屬種群優(yōu)化的基礎(chǔ)上，提出了遠(yuǎn)緣選優(yōu)策略遺傳算法（OEAGA），并且針對(duì)高空氣象探測(cè)數(shù)據(jù)數(shù)量大、變化復(fù)雜和可預(yù)測(cè)性差等特點(diǎn)，使用OEAGA來(lái)計(jì)算B樣條節(jié)點(diǎn)，在滿足準(zhǔn)確度要求的前提下，使用更少的控制頂點(diǎn)擬合高空氣象探測(cè)數(shù)據(jù)的最佳B樣條曲線.將B樣條曲線的結(jié)果與標(biāo)準(zhǔn)演變算法計(jì)算節(jié)點(diǎn)的結(jié)果作比較，發(fā)現(xiàn)經(jīng)由OEAGA得出的B樣條曲線更優(yōu)，實(shí)際探測(cè)和仿真試驗(yàn)均表明OEAGA擁有更強(qiáng)大的搜索性能和更高的收斂效果.

遠(yuǎn)緣選優(yōu)；B樣條曲線擬合；氣象探測(cè)

P412.2

A

book=53,ebook=143

P412.2 Document code：A

10.3969／j.issn.1007－2985.2012.04.012

（責(zé)任編輯 向陽(yáng)潔）

1007－2985（2012）04－0053－07

date：2012－03－20

Biography：SUN Bao－jing（1968－），was born in Wulian，Shandong Province，professor；research area is ballistic density.