收稿日期:2001-12-28
  基金项目：江苏省教育厅自然科学研究基金资助项目(00KJB4600031)  作者简介：鲁刚(1977-)，男，辽宁营口人，江苏大学机械工程学院测控系硕士研究生，研究方向：智能检测诊断技术。
文章编号:1006-2475(2002)07-0001-03
基于VB 的遗传算法软件实现及其应用
鲁　刚，李伯全
(江苏大学机械工程学院测控系，江苏镇江　212013)
摘要：遗传算法是一种模拟达尔文理论的自然进化机制的搜索和优化方法。它在搜索优化问题的全局或全局附近的最优解上具有良好的优势条件，因此它在很多诸如组合优化、图像处理和故障诊断等的领域都得到了应用。本文对遗传算法基本的数学基础理论、主要特点、算法实现的VB 编程和实际应用进行了描述。关键词：遗传算法;VB ；优化方法；应用中图分类号:TP301.6  　文献标识码:A
Genetic Algorithm 's Programming Realization Based on VB and Its Application
LU Gang ,LI B o -quan
(Department of Testing and Controlling ,School of Mechanical Engineering ,Jiangsu University ,Zhenjiang  212013,China )Abstract :Genetic Algorith m is s uch a searching and optimal method based on Darwins theories ,which has been developed to stimulate and inherit the mechanism of natural evolution .It has good advantages in finding the global or near global ans wers of optimization prob -lems ,s o that it has a lot of applications in different fields ,s uch as combined optimizations ,image proceeding and fault diagnosis and so on .This paper describes genetic algorith m 's fundamental theory based on mathematic fundament ,its traits ,its program ming realization based on VB and its application .
Keywords :genetic algorithm ;VB ;optimization method ;application
0　引　言
遗传算法(Genetic Algorithm ,GA )是一种模拟达尔文自然选择和遗传机制，在计算机上进行自适应概率性全局寻优搜索算法，它是由美国Michigan 大学的J .Holland 教授于1975年首先提出的，是近些年来发展起来的一种新型的优化算法。遗传算法是从初始
种出发，不断重复执行选择、交叉和变异的操作过程，使种一代一代地沿着既定目标方向发展。GA 在寻优过程中，是在高维可行解空间随机产生多个起始点并同时开始搜索，由适应度函数来指导搜索方
向，因而搜索区域广，搜索效率高。
1　遗传算法的操作机制
遗传算法主要包括选择、交叉和变异:(1)选择(又称繁殖)：选择操作是根据其编码串
的目标函数的适应度值大小来进行的，是一种从旧种中选择生命力强的个体产生新种的过程。一般说来，一个码串的适应值越高，则它在种中生存繁殖的几率也越大，即适合于生存环境的优良个体具有更多繁殖后代的机会，从而使优良特性得以代代遗传。常见的选择方法有适应值比例法、两两竞争法、排位次法等几种。一般而言，选择要通过选择算子来操作。选择算子是在一个种中选择一个个体，它是
一种随机映射:T S :S N
※S ，即按照概率规则
P {T a s
(X ※
)=Xi }=f a
(X i )
∑N k =1
f a
(X k )(1)
来选择个体。
(2)交叉：交叉是两个码串重组的操作，是遗传算
法区别于其它传统优化方法的重要标志。交叉分两步进行，首先随机地从操作种中取出要匹配的两个
　2002年第7期
计　算　机　与　现　代　化
JISUANJI YU XIANDAIHUA
　总第83期
码串；然后以一定的交叉方式互换这两个码串中的信息，从而产生一对新的码串。常见的交叉方式有①单点交叉：等概率地随机确定一个基因位置作为交叉点，再把一对母体两个个体从杂交点分成前后两个部分得到两个新个体，取第一个个体为杂交结果。②单点随机杂交：等概率地随机确定一个基因位置作为交叉点，再把一对母体两个个体从交叉点分为前后两个部分，以概率p c交换两个个体的后半部分，得到两个新个体，取第一个个体为交叉结果。称p c为交叉概率。③均匀随机交叉：独立地以概率p c把母体的第一个个体的相应的分量交换为第二母体的相应分量，从而得到交叉结果。杂交中要通过杂交算子来完成杂交的操作。杂交算子是母体空间到个体空间的映射，记作T c:S2※S
(3)变异：变异是以一定变异概率从种中随机选取若干个体。对于选中的个体，在需变异的基因位上随机产生0～9之间的数来取代原来的数。若为二进制编码，则变异操作实现0-1的转换。变异是通过变异算子来操作变异的。变异算子是个体空间到个体空间的随机映射，即T m:S※S，其作用方式为独立地以概率p m改变个体分量位码取值。p m称做变异概率。
2　遗传算法的主要特点
(1)GA与传统的优化方法的主要区别是:GA同时搜索解空间的许多类，而不是从一个单点上进行寻优，因而可以有效地防止搜索过程收敛于局部最优解，而能求得全局最优解。
(2)GA在解空间内进行充分的搜索，但这并不是漫无目的的，而是一种启发式搜索，其搜索效率往往是
其它优化方法所不能及的。
(3)GA的应用范围广泛：它仅需要一适应值函数，即问题本身所具有的目标函数的限制极少；既可连续又可离散，也不要求可微，且不要求其他先决条件和辅助信息；既可以是数学表达式等显函数，又可以是映射矩阵，甚至神经网络等隐函数。
(4)GA使用概率规则而不是确定性规则指导搜索。因而能搜索离散的有噪声的高峰值复杂空间，即其适用于大规模，甚至是超大规模复杂优化问题。并且其结果是确定的。
(5)GA隐含并行性。易于采用并行机制制作并行高速计算，具有很大的计算潜力。3　遗传算法的常见编码方法
(1)二进制编码：它是将十进制数或实际应用中所遇到的问题的解转换成二进制的表现形式，即由0或1组成的字符串。其长度要由具体问题的要求来定，例如解的精度要求等。但这样就会有一定的量化误差产生，则只适用于一般的遗传算法。
(2)灰编码：也是一种用0或1来表示解的编码方法，但灰编码可以克服二进制编码映射不连续问题(欧氏空间邻近点的二进制编码在Hamming距离下并不邻近)。
(3)实数编码：顾名思义，是用实数来作为等位基因。实数编码适合于高维或复杂优化问题的求解。
4　基本遗传算法的软件实现
4.1　基于VB的遗传算法软件实现
在程序中,FitnessValue(i)为适应度值数组、avFit-nessValue(100)为归一化适应度值数组、Population-Chrom(i,j)为遗传个体的等位基因值、Popsize为种中的个体数,C HROMLENGTH为一母体对的等位基因总数。
(1)选择操作实现:
Public Function SelectOperation()
Dim i,j,sortnu mber As Integer
Dim p,sum,avFitness Value(100)As Double
sum=0
Randomize(137)
For i=0To Popsize-1
　sum=su m+FitnessValue(i)'求种个体总适应度值Next i
For i=0To Popsize-1
　If(sum<>0)Then
  avFitness Value(i)=FitnessValue(i)sum
'归一化适应度值
vba 字符串转数组　End If
Next i
For i=1To Popsize-1'法选择下代种个体
avFitness Value(i)=avFitness Value(i-1)+avFitness Value(i)
Next i
For i=0To Popsize-1
　p=(1000＊Rnd+1)1000#
　sortnumber=0
　Do Until p>avFitness Value(s ortnumber)
  sortnumber=sortnu mber+1
　Loop
　For j=0To CHROM LENGTH-1
2计　算　机　与　现　代　化2002年第7期
newPop ulationChrom (i ,j )=PopulationChrom (sortnumber ,j )　Next j Next i
For i =0To Popsize -1'产生新一代的种　For j =0To CHROMLENGTH -1
  PopulationChrom (i ,j )=newPopulationChrom (i ,j )　Next j Next i End Function
(2)交叉操作实现:
Public Function CrossoverOperation ()Dim i ,j As Integer Dim index (150)As Integer Dim point ,median As Integer Dim p As Single Dim ch As Integer Randomize (137)For i =0To Popsize -1　index (i )=i Next i
For i =0To Popsize -1'随机重新排列种中的个体序列　point =Round ((Popsize -1-i )＊Rnd )　median =index (i )
　index (i )=index (point +i )　index (point +i )=median Next i
For i =0To Popsize -1Step 2
'按一定的随机概率单点交叉相邻两个体　p =(1000#＊Rnd +1) 1000#　If (p <Pc )Then
  point =CHROMLE NGTH ＊Rnd  　For j =point To CHROMLE NGTH -1  　ch =PopulationChrom (index (i ),j )
  　Population Chrom (i ,j )=PopulationChrom (in dex (i +1),j )  　PopulationChrom (index (i +1),j )=ch  　Next j  　End If Next i End Function
(3)变异操作实现:
Public Function MutionOperation ()Dim i ,j As Integer Dim p As Single For i =0To Popsize -1
'按一定随机概率取反变异点的位码值　For j =0To CHROMLENGTH -1  p =1000#＊Rnd  1000#
  If (p <Pm )Then
  　If PopulationChrom (i ,j )=0Then    　PopulationChrom (i ,j )=1  　Else :PopulationChrom (i ,j )=0  　End If  　End If  Next j Next i End Function
4.2　流程图
图1　基本遗传算法流程图
5　遗传算法的应用
根据遗传算法的特点及其机理，我们可以知道其适用于传统搜索方法所不能解决的复杂问题和非线性问题，因而在很多领域都可以将遗传算法渗入其
中:
(1)组合函数的优化问题：遗传算法可对一些不可微、不可导、非线性、离散的函数进行优化，并且能够克服目标函数容易发生的局部最优解的现象。如经典的背包问题和旅行商问题。(2)故障诊断应用问题：有些故障诊断问题可以归结为因果网络关系问题，即具有一定的征兆集和故障集，而且两者之间并不是单一的一一对应的关系，可能具有一对多或多对一的复杂且多层树状关系，则必然给传统的故障分析诊
断带来一定的挑战，即要求极大范围量的搜索计算，所以遗传算法在故障诊断应用上得到了极好的发展空间，同时也大大地促进了故障诊断学的发展。
(3)图像处理应用：传统的图像处理是从原始传感器数据开始，到高层任务如目标识别和理解为止。
(下转第11页)
3
2002年第7期  鲁刚等：基于VB 的遗传算法软件实现及其应用
不论是单机、C S结构、B S结构还是分布式结构的程序设计，多进程、多线程的应用都很广泛，单线程应用程序重新编写成多线程应用程序的策略和结果不是一成不变[7]。在使用多线程时要谨慎，因为操作系统要跟踪和确定线程的进度，因此线程的系统开销会比较大，由于必须为每个线程分配内存，太多的线程将会令整个系统的性能受到影响，这样也不是在应用的任何地方都创建新的线程。
参考文献:
[1]　William Stallings.Operating Systems Internals and Principles
[M].Third Edition.Englewood Cliffs,NJ:Prentice Hall,
1998.
[2]　尹俊文，等.分布式操作系统[M].长沙：国防科技大学出
版社,2000.[3]　John Shapley Gray.Interprocess Communications in Unix[M].
Second Edition.Englewood Cliffs,NJ:Prentice Hall,1998. [4]　Daniel Robbins.Common theads:POSIX threads explained,
Part2The little thin gs called mutexes[DB OL].http:www-
106.ibm developerworks library posix2index.html,
2000-08-02.
[5]　Microsoft Corporation.Microsoft Visual C#.NET:Features
Overview[DB OL].http:msdn.microsoft vcsharp pro-
ductinfo features.asp,2002-01-12.
[6]　查礼，等.一种多线程计算程序的机移植方法[J].计
算机学报,2002,25(3):306～312.
[7]　Microsoft Corporation.Multithreadin g with C and Win32[DB
OL].http:msdn.microsoft library en-us vccore98HT-
ML core multithreading with c and win32.asp,2002-01-
12.
(上接第3页)
但当传感器噪声很大时，则会降低所要计算的如分割标志和边界特征等的品质。但是，应用遗传算法可以消除上述不利因素，达到良好的图像处理效果。
6　结束语
尽管遗传算法并未发展成为一种完全成熟的算法，如对于交叉和变异概率的选择仍没有一个确定性的规定，种的个体数目也需要试算来决定，但它已经在很多的领域中得到了应用，尤其是在一些传统的算法不能得到很好的应用的问题上更加具有优越性。笔者正拟将遗传算法应用于机动车的变速齿轮箱的故障诊断中，以此来解决变速箱故障集与征兆集之间的复杂因果关系。
参考文献:
[1]　张文修，梁怡.遗传算法的数学基础[M].成都：西南交通
大学出版社,2000,5.
[2]　陈国良，王煦法，庄镇泉，王东生.遗传算法及应用[M].
北京：人民邮电出版社,2001,2.
[3]　徐章遂，房立清，王希武，左宪章.故障信息诊断原理及
应用[M].北京：国防工业出版社,2001,7.
(上接第6页)
  本文提出了用梯形来剖分多边形的通用算法，多边形可以是非单调的，可以包含孔，孔也可以梯形化。算法分3个步骤：初始化、梯形化及优化(后处理)。在最坏的情况下，算法的时间复杂度为O(n2log2n)。每个多边形的局部分类规则和包含性检查确保算法对累积误差不敏感，运算稳定。
参考文献:
[1]　王玉兰，沈越江.多边形的三角剖分及应用[J].成都理
工学院学报,1997(1):108～111.
[2]　徐春蕾，李思昆.一种适用任意平面多边形的三角剖分
算法[J].国防科技大学学报,2000(2):82～85.
[3]　巩丹超，戴晨光，张永生.三维模型重建中的凹多边形三
角剖分[J].解放军测绘学院学报,1999(3):194～196.[4]　Seidel R.A simple and fast incremental randomized algorithm
for computing trapezoidal decompositions and for triangulating
polygons[J].Computational Geometry:Theory and Applica-
tions,1991(1):151～154.
[5]　Narkhede A,M anocha D.Fast polygon triangulation based on
Seidel's algorith m[M].Boston:Academic Press,1995. [6]　Preparata FP,Shamos Mi.Computational Geometry:An Intro-
duction[M].Berlin:Springer,1985.
[7]　Manber U.Introduction to algorithms:a creative approach
[M].MA:Addison-Wesley,1989.
[8]　Mortenson ME.Geometric modeling[M].New York:Wiley,
1985.
[9]　O'Rourke J.Computational Geometry in C[M].Cambridge:
Cambridge University Press,1993.
11
2002年第7期  周炎涛等：现代操作系统中的多线程技术及其应用

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。