遗传算法论文范文第1篇

关键词全局最优；混合算法；遗传算法；Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。

近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

2混合遗传算法

编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1)，式中为变量个数，、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中，得到求解问题(1)如下混合遗传算法：

min(1)

step1给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。

Step2随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。

fi’=a×fi’+b（fi³0）(2)

step3执行比例选择算子进行选择操作。

step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和，算术交叉产生的两个子代为和，是[0，1]上的随机数，1,。

step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异，，则变异结果为，其中，

(3)

(4)

返回区间[,]里的一个值，使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间，而在后面阶段非常局部化。是[,]之间的随机数，为最大代数，为决定非均匀度的系统参数。

step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作，则以作为初始点执行Powell方法得，若则把所得计算结果作为子代，否则，若取=；若取=，1。

step7计算个体适应值，并执行最优个体保存策略。

step8判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。

作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：

(1)变量赋初值，n个线性无关的n个方向,,…,，和允许误差ε>0，令k=1。

(2)令，从出发，依次沿方向,,…,作一维搜索，得到点,,…,求指标m，使得-=max{-}，令。若ε，则Powell方法计算结束，否则，执行(3)。

(3)求使得=min，令==，若，则Powell方法计算结束，得点；否则，执行(4)。

(4)若，令，否则令()，然后置，转(2)。

3算例

T[-500,500]

图1函数f(x)特性示意图

函数f(x)有相当多的极小点,全局极小点是=-420.97，=1,2,…,，最优值为-837.97；次最优点为={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranPowerStation4.0，随机数由内部随机函数产生，在奔腾133微机上运行。

采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。

Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.95、变异概率pm=0.05，最大进化代数T=1000，每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。当取最大进化代数为T=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取T=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。

采用本文混合法计算，取m=30，pc=0.85、pm=0.2，T=100，进行Powell搜索的概率pPowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明pPowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.85、pm=0.2，T=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中PPowell=0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。

表1pPowell取不同值时混合法的计算结果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最优解的次数

82

85

89

94

98

100

求得最优解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均计算时间/秒

0.14

0.20

0.31

0.47

0.68

0.87

4结束语

针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。

参考文献

[1]周明，孙树林．遗传算法原理及应用[M]．北京：国防工业出版社，1999．

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．

[3]孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35(5)：44－48．

[4]戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[J]．控制与决策，2000，15(3)：263－268．

[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．

[6]赵明旺．连续可微函数全局优化的混合遗传算法[J]．控制与决策，1997，12(5)：589－592．

[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．

[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．

[9]陈宝林．最优化理论与算法[M]．北京：清华大学出版社，1989．

[10]俞红梅．全过程系统能量综合方法的研究[D]．大连理工大学博士学位论文，1998．

Hybridapproachforglobaloptimaofindifferentiablenonlinearfunction

AbstractAhybridcomputationalintellectivealgorithmforlocatingtheglobaloptimaofindifferentiablenonlinearfunctionwasputforwardbysettingthePowellalgorithminreal-codegeneticalgorithm.Thehybridapproachimprovedthelocalsearchingabilityofthegeneticalgorithmandpromotedtheprobabilityfortheglobaloptimagreatly.Becauseonlytheobjectivevaluesareused,thehybridapproachisageneralizedgeneticalgorithmforglobaloptimaofdifferentiableandindifferentiablenonlinearfunctions.

遗传算法论文范文第2篇

关键字：频率分配遗传算法GECP组合优化

1.通信网频率分配问题的背景

无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率（信道）构成无线通信链路。由于电磁波的自然特性，无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配（FAP）的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道)，使所有设备都以尽量小的概率被干扰，从而使整个网络的可用性得到优化。FAP可以描述为：对N个给定的待分配工作频率的链路，设G={S1,S2,…Sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，寻找最优解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一种组合优化问题。

具体设备频率分配方法虽然会随着设备的工作方式（单工、双工）、工作频段、天线类型、信号的调制解调方式的不同而有所区别，但是大部分频率分配算法都可以转换为等价的图的边着色问题。从图论算法理论上讲，图的广义边着色问题是NPC问题[7]，也就是说无法在多项式时间内求得问题的最优解。例如对于存在n条边的无向图，使用c种颜色对其着色，在没有其它约束条件下，其解空间是cn。即使在不考虑颜色重复使用（c>n）的情况下，其解空间也达到n!。这两者都是超越数，在c和n的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。

在工程实践中许多NPC问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（DP）或者分支界限算法（BC）；概率算法；求近似解；启发式算法（HeufisticAlgorithms）等。这些方法的和核心是分割问题的解空间，按照特定规则搜索典型解作为次最优解。

对于FAP问题国内外许多学者进行了深入的研究，提出许多解决问题的方法。文献[4]在对FAP进行理论分析的基础上给出了几种常用算法的框架，这些算法包括：最小-最后次序查找算法，贪心T着色算法、模拟退火算法（SA）、列表寻优算法（TS）、遗传算法（GA）、神经网络（NN）多面体算法等，并指出各种算法有各自的适用范围；文献[2]提出了利用启发式的蚂蚁算法，并对解决CELAR、GRAPH、PHILADELPHIA上的几类问题同TS和SA算法进行了比较；文献[1]比较了SA、TS、GA、VDS（variable–depthsearch）、BC等算法的性能。文献[7]利用GECP理论对存在禁用频率的异频双工设备的频率分配给出工程上的实用算法；文献[9]则采用了BC方法频率分配的全排列算法进行了优化。本文将探讨如何遗传算法解决FAP问题。

2.遗传算法在频率分配问题中的适用性

2．1遗传算法的原理

遗传算法(GeneticAlgorithmsGA)是根据生物学上的染色体基因因子构成机制而产生的。1975年Holland教授首次提出了GA的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面。遗传算法是一种全局优化算法，其仅以目标函数值为搜索依据，通过群体优化搜索和随机执行基本遗传运算，实现遗传群体的不断进化，适合解决组合优化问题和复杂非线性问题[6]。

利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。

实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了模式定理。所谓模式，就是某些码位取相同值的编码的集合。模式定理说明在进化过程的各代码中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长[6]。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解[5]。

2．2遗传算法的基本结构

在遗传算法中，将问题的求解的过程，看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索，一般采用遗传算子(或称遗传操作)诸如交配(Crossover)和变异(Mutation)等，以及模拟自然过程的选择机制，采用计算适应值的方法来评估一个候选解的优劣。

遗传算法求解问题的基本步骤可以描述如下：

1.首先生成一组初始的候选解群体(假设为N个候选解个体)，称为第0代；

2.计算群体中各个候选解的适应值；

3.如果有候选解满足算法终止条件，算法终止，否则继续4；

4.根据交配概率，将候选解群体中的个体随机两两配对，进行交配操作以生成新的候选解；

5.根据变异概率，对4中生成的候选解群中的每个个体进行变异操作；

6.使用选择机制形成新一代候选解；转2。

GA算法具有下述特点：GA是对问题参数的编码组进行，而不是直接对参数本身；GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始；GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息；GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。

遗传算法通过编码和遗传操作，达到了处理的并行性，可以同时处理群体中的多个个体，即同时对搜索空间内的多个解进行评估，具有较好的全局搜索性能，减少了限于局部最优解的风险。

3.遗传算法用于频率分配

3．1算法的基本流程

采用遗传算法的FAP基本流程

3．2遗传算子的选择

3．2．1选择算子

选择算子在父代群体中选出父体和母体。生物界中，父母亲素质比较高的其后代素质高的概率也大。模拟这种现象，在FAP中选择算子采用轮赌算法实现。

轮赌算法流程如下：

sum=0;i=0;

wheelpos=rand()*sumfitness;

for(sum<wheelpos&&i<pop-size)

｛

i++;

if(i≥pop-size)

｛

sum=0;i=0

wheelpos=rand()*sumfitness;

｝

j=rand()*pop-size;

sum+=fitness［j］;

｝

returnj;

3．2．2交叉算子

交叉算子让父体和母体互相交换某部分基因而产生下一代个体的雏形，起全局搜索的作用。交叉算子通常有单点交叉、双点交叉、多点交叉等等。在频率自动分配的算法中，为了不破坏基因段内部频点间的关系，采用单点交叉和双点交叉比较合适。此外，在生物界中并不是两个个体相遇了就一定会结合，模拟此现象，引入交叉因子pc。

其基本流程如下：

//flip函数中，产生一个0到1的随机数，若小于pc，则返回1，否则返回0

if(flip(pc))

crossover1(mother,father);

elseif(flip(pc))

crossover2(mother,father);

else

copy(mother);

copy(father);

3．2．3变异算子

变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界中，父母的染色体交叉后产生后代个体的染色体雏形，这个雏形在成长过程中会发生基因的变异，正是这种变异使得下一代的群体中会出现各种特征的个体.另外，生物界中并非每个基因都会变异，模拟此现象，引入变异因子pm，使用方法与交叉因子类似。

其基本流程如下：

while(allfrequentpoint)

{

if(flip(pm))mutate(frequentpoint)；}

4.工程上需要注意的问题

4．1初始候选种群

由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。实践中采用文献[7]的GECP得到以各个顶点为主顶点的可行解作为初始候选种群。

4．2编码方案

编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。频率分配问题适合采用十进制编码方案，每个码表示一条通信链路，码值表示分配的信道编号。

4．3适配值函数

适配值函数对个体（频率分配方案）进行评价，也是优化过程发展的依据。可以采用如下方式来计算适应度：

fitness=1000/Σ(pri×seperate(Freq))。

其中：

pri是节点的加权值；

函数seperate(Freq)是节点中各条链路发频率同其它链路的收频率间隔的和；

参考文献：

[1]RobertA.Murphey,PanosM.Pardalosetc,FrequencyAssignmentProblems,Handbookofcombinatorialoptimization,KluwerAcademicPublishers,1999

[2]VittorioM.,AntonellaC.,AnANTSHeuristicfortheFrequencyAssignmentProblem,www.csr.unibo.it

[3]JoeBater,PeterJeavons,DavidCohen,ArethereoptimalreusedistanceconstraintsforFAPswithrandomTxplacement?,CSD-TR-98-01,CSRoyalHollowayUni.OfLondon,1998

[4]K.IAardal,C.A.J.Hurkens,J.K.etc.AlgorithmsforFreequencyAssignmentProblems,CWIQuarterly,Vol9(1&2),1996

[5]王凌：《智能优化算法及其应用》清华大学出版社2001

[6]陈国良等：《遗传算法及其应用》人民邮电出版社1996

[7]孙俊柏：禁用频点、频段下野战通信网的频率分配中国科学技术大学硕士学位论文1998

遗传算法论文范文第3篇

关键词全局最优；混合算法；遗传算法；Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。

近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

2混合遗传算法

编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1)，式中为变量个数，、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中，得到求解问题(1)如下混合遗传算法：

min(1)

step1给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。

Step2随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。

fi’=a×fi’+b（fi³0）(2)

step3执行比例选择算子进行选择操作。

step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和，算术交叉产生的两个子代为和，是[0，1]上的随机数，1,。

step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异，，则变异结果为，其中，

(3)

(4)

返回区间[,]里的一个值，使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间，而在后面阶段非常局部化。是[,]之间的随机数，为最大代数，为决定非均匀度的系统参数。

step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作，则以作为初始点执行Powell方法得，若则把所得计算结果作为子代，否则，若取=；若取=，1。

step7计算个体适应值，并执行最优个体保存策略。

step8判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。

作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：

(1)变量赋初值，n个线性无关的n个方向,,…,，和允许误差ε>0，令k=1。

(2)令，从出发，依次沿方向,,…,作一维搜索，得到点,,…,求指标m，使得-=max{-}，令。若ε，则Powell方法计算结束，否则，执行(3)。

(3)求使得=min，令==，若，则Powell方法计算结束，得点；否则，执行(4)。

(4)若，令，否则令()，然后置，转(2)。

3算例

T[-500,500]

函数f(x)有相当多的极小点,全局极小点是=-420.97，=1,2,…,，最优值为-837.97；次最优点为={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranPowerStation4.0，随机数由内部随机函数产生，在奔腾133微机上运行。

采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。

Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.95、变异概率pm=0.05，最大进化代数T=1000，每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。当取最大进化代数为T=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取T=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。

采用本文混合法计算，取m=30，pc=0.85、pm=0.2，T=100，进行Powell搜索的概率pPowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明pPowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.85、pm=0.2，T=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中PPowell=0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。

表1pPowell取不同值时混合法的计算结果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最优解的次数

82

85

89

94

98

100

求得最优解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均计算时间/秒

0.14

0.20

0.31

0.47

0.68

0.87

4结束语

针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。

参考文献

[1]周明，孙树林．遗传算法原理及应用[M]．北京：国防工业出版社，1999．

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．

[3]孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35(5)：44－48．

[4]戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[J]．控制与决策，2000，15(3)：263－268．

[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．

[6]赵明旺．连续可微函数全局优化的混合遗传算法[J]．控制与决策，1997，12(5)：589－592．

[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．

[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．

遗传算法论文范文第4篇

关键词：计算机应用;装配规划;综述;虚拟现实;软计算;协同装配

装配是产品生命周期的重要环节，是实现产品功能的主要过程。写作毕业论文装配成本占产品制造成本40%～50%，装配自动化一直是制造自动化中的瓶颈问题。装配规划是在给定产品与相关制造资源的完整描述前提下，得到产品详细的装配方案的过程，对指导产品可装配性设计、提高产品装配质量和降低装配成本具有重要意义。产品的装配规划通常需要得到零部件的装配序列、装配路径、使用的工装夹具和装配时间等内容[1]~[3]。

较早的传统装配规划采用人工方式，工艺人员根据设计图纸和技术文档，通过分析产品装配图中零件的几何形状和位置关系，必要时再和设计人员进行讨论，进一步明确设计者的真正意图，利用自己的经验和知识规划出产品的装配方案。这种方法工作量大、效率低，且难于保证装配方案的经济性。

随着计算机集成制造CIMS和并行工程CE技术的发展和应用，一方面对装配相关的设计技术提出了计算机化的要求，以提高和产品开发过程中其他环节的集成化程度。另一方面要求装配方案的优化以降低成本和缩短规划时间以加快产品开发进程。受“需求牵引”和“技术推动”两方面的影响，80年代初，出现了对计算机辅助装配规划(ComputerAidedAssemblyPlanning，CAAP)技术的研究。到目前为止，CAAP经历了几个不同的发展阶段，出现了4种代表性的方法，按照出现的时间顺序及方法的特点，笔者将其归结为经典装配规划方法、虚拟装配规划方法、装配规划软计算方法和协同装配规划方法。

1经典装配规划方法

早期CAAP的研究侧重于装配序列的规划，以产品CAD装配模型为基础，写作硕士论文一般采用几何推理的方法，通过产品装配建模、装配序列推理和表达以及装配序列评价和选择为产品面向装配的设计和装配工艺规划提供指导和支持，其过程通常如图1所示。

1.1产品装配建模

产品装配模型是装配规划的基础，为装配规划提供装配体和零部件的相关信息。常用的装配信息表达模型可分为图模型和矩阵模型。法国学者Bourjauct提出了联系图模型[4]，将零件之间的物理接触关系定义为联系即装配关系，图中的节点对应零件，边表示所连接的零件间至少有一种装配关系。关系模型[5]进一步区分了零件之间的接触关系和联接关系，图中包含3种实体类型：零件、接触和联接，边表达了实体间的关系。产品等级装配模型[6]将装配体看成具有层次结构性，即装配体可以分解为子装配体，子装配体又可分解为下级子装配体和零件的集合，以此表达产品的装配组成。

矩阵比图易于计算机表达和实现。Dini和Santochi[7]利用干涉矩阵、接触矩阵和连接矩阵表达产品，干涉矩阵描述了零部件间沿坐标轴方向装配时相互间的干涉情况，接触矩阵描述了零部件间的物理接触状态，连接矩阵描述了零部件间的连接类型。为减少矩阵的数量，Huang[8]等把6个干涉矩阵合并为一个拆卸矩阵，集成的表达零部件间沿坐标轴方向的干涉情况。

1.2装配序列推理和表达

基于联系图模型，Bourjauct采用人机交互“问答式”方法获取装配优先约束关系[4]，写作医学论文随后DeFazio和Whitney[9]，Baldwin[10]等人的工作进一步较少了需要由用户回答问题的数量，然后通过对装配优约束关系进行推理得到联络建立优先关系的层次模型表达产品的装配序列。

“割集”法是基于拆卸策略的装配规划中通常采用的图论算法。HomemdeMell和Sanderson[5]通过对产品联接图进行缩并，利用“割集”算法对联接图进行循环分解，生成所有可能的子装配体，直到不可再分。并提出了装配序列的AND/OR图表达方法，图中的节点对应装配过程中的子装配体或零件，超弧表达将子装配体或零件联接在一起形成更大子装配体的装配操作。因为“割集”算法的计算复杂性为O(3N)(N为零件个数)，因此，对于复杂产品的装配顺序规划存在指数爆炸问题，这是难以让人接受的。

1.3装配序列评价和选择

装配序列的选择对装配线设计、装配成本、装配设备选择有很大影响，写作职称论文而评价是选择的基础。装配序列的评价可分为定性和定量两方面因素[11]~[13]，定性因素主要考虑的有装配方向换向的频度、子装配体的稳定性和安全性、装配操作任务间的并行性、子装配体的结合性和模块性、紧固件的装配、零件的聚合等。定量因素主要考虑的有整个装配时间(包括子装配体的操作时间、运输时间等)、整个装配成本(包括劳动成本、夹紧和加工成本)、产品在装配中再定位的次数、夹具的数目、操作者的数目、机器人手爪的数目、工作台的数目等。

更多的经典装配规划方法研究文献可以参见TexasA&M大学Wolter教授的“AssemblyPlanningBibliography”[14]，其中收集了自1980年起近15年经典装配规划方法的相关研究。经典方法一般表达出全部的序列解空间，这使它可能从中找出最优的装配序列，但随着产品中零件数量的增加，解空间的组合爆炸给序列的存储、选优带来极大困难；且序列的几何推理方法不易融入人类的装配知识，难免产生众多几何可行但工艺不可行的序列结果。

2虚拟装配规划方法

虚拟现实技术为装配规划的“人－机”协同工作提供了契机。虚拟装配是指由操作者通过数据手套和三维立体显示设备直接三维操作虚拟零部件来模拟装配/拆卸过程，无需产品或支撑过程的物理实现，通过分析、先验模型、可视化和数据表达等手段，利用计算机工具来安排或辅助与装配有关的工程决策[15]。虚拟装配过程中，人机可以充分发挥各自的优势，即人通过直觉/装配经验和知识决定产品的装配过程，但不能精确地判断当前所有可能装配的零件，也不太可能准确判定装配某一零件后装配体的稳定性等因素，而通过一定算法和规则实现的机器智能刚好弥补人的不足。虚拟装配方法得到的不仅仅是零件的顺序，还可以包括零件路径、装配工具、夹具和工作台等信息。图2为虚拟装配规划的工作步骤。

国外虚拟装配规划的研究以沉浸式虚拟装配环境VADE[16],[17](VirtualAssemblyDesignEnvironment)为代表，写作英语论文通过建立一个装配规划和评价的虚拟环境来探索运用虚拟现实技术进行设计、制造的潜在技术可能性，为机械系统装配体的规划、评价和验证提供支持。在虚拟环境中，利用提取并导入的CAD系统产生的装配约束信息引导装配过程；通过引入了质量、惯性和加速度等物理属性，基于物理特性进行装配建模，逼真地模拟真实装配环境；支持双手的灵活装配和操作；记录虚拟装配过程中产生的扫体积和路径信息并可进行编辑；建立了工具/零件/人相互作用模型，支持装配工具在虚拟装配环境中的运用。

国内管强等[18]将虚拟现实技术与面向装配设计的理论相结合，建立了一个虚拟环境下的面

向装配设计系统（VirDFA）。万华根等[19]建立了一个具有多通道界面的虚拟设计与虚拟装配系统（VDVAS），通过直接三维操作和语音命令方便地对零件进行交互拆装以建立零件的装配顺序和装配路径等装配信息。在面向过程与历史的虚拟设计与装配环境（VIRDAS）中，张树有等[20]通过识别装配关系进行装配运动的导航，实现虚拟拆卸/装配顺序规划、虚拟装配分析。从集成的观点出发，姚珺等[21]提出面向产品设计全过程的虚拟装配体系结构，从方案设计、结构设计和装配工艺设计3个层次上分阶段地对产品可装配性进行分析与评价。田丰等[22]提出一个面向虚拟装配的三维交互平台（VAT），简化了虚拟装配应用系统的构造，便于应用的快速生成。

应用虚拟现实环境开展装配规划，提供了一种新的思路和工具。但是，虚拟环境的构建需要较大资金的软硬件投入，另外，虚拟现实技术本身（如图形的高速刷新）及其相关硬件技术（如力触觉设备）的不成熟使得虚拟装配的研究仍处于探索阶段。

3装配规划软计算方法

1994年，Zadeh教授将模糊逻辑与智能技术结合起来，提出了软计算方法（softcomputing）[23]。软计算以模糊逻辑、神经网络和概率推理为基础，不追求问题的精确解，以近似性和不确定性为主要特征，所得到的是精确或不精确问题的近似解。为避免组合爆炸同时又能得到较优的装配规划方案，近来，基于建模、表达和寻优一体化的装配规划软计算方法得到广泛关注。

3.1装配规划神经网络方法

神经网络是模拟人类形象思维的一种人工智能方法，它是由大量神经元广泛互连而成的复杂网络系统，写作留学生论文单一神经元可以有许多输入、输出，神经元之间的相互作用通过连接的权值体现，神经元的输出是其输入的函数。若将优化计算问题的目标函数与网络某种状态函数(通常称网络能量函数)对应起来，网络动态向能量函数极小值方向移动的过程就可视作优化问题的求解过程，稳态点则是优化问题的局部或全局最优解。

Hong和Cho[24]用于机器人装配顺序优化的Hopfiled神经网络中，考虑装配约束、子装配体稳定性和装配方向改变等因素建立网络的能量方程，基于优先约束推理和专家系统提供的装配成本驱动网络的进化方程得到优化的序列。但由于神经网络缺乏全局搜索能力，计算结果显示，该方法容易产生不优化的装配顺序，且常常只能得到一个局部最优的装配序列。另外，参数选择和初始条件对网络的灵敏度影响大；神经网络在应用前须进行训练，而训练时要由专家提供较多可行的顺序作为样本。而样本可能是针对某种类型的产品，对其它类型的产品则不一定适用，该方法的应用范围窄。

3.2装配规划模拟退火算法

模拟退火算法源于固体退火思想，将一个优化问题比拟成一个热力学系统，将目标函数比拟为系统的能量，将优化求解过程比拟成系统逐步降温以达到最低能量状态的退火过程，通过模拟固体的退火过程获得优化问题的全局最优解。

Saeid等[25]利用模拟退火算法进行装配序列规划时，根据产品装配模型获得装配优先关系，将装配过程总装配时间和重定向次数运用多属性应用理论组合成单一目标函数，作为装配序列优化的评价函数。Hong和Cho[26]将装配约束和装配过程的成本映射为装配序列能量函数，利用模拟退火算法使装配序列能量函数扰动地逐步减小，经过多次迭代，直到能量函数不再变化为止，最后得到具有最小装配成本的装配序列。作者将该方法应用到一个电子继电器装配体上，并将其性能与利用神经网络[24]的装配规划方法进行了比较，结果显示基于模拟退火的装配序列优化方法可以产生较好的装配序列并且在运算时间上优于人工神经网络方法。

模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优，但模拟退火算法对整个搜索空间的状况了解不多，不能使搜索过程进入最有希望的搜索区域，从而使得算法的运算效率不高。

3.3装配规划遗传算法

在众多软计算方法中，遗传算法得到了众多研究者的重视。写作工作总结遗传算法是模仿生物自然选择和遗传机制的随机搜索算法，它将问题的可能解组成种群，将每一个可能的解看作种群的个体，从一组随机给定的初始种群开始，持续在整个种群空间内随机搜索，按照一定的评估策略即适应度函数对每一个体进行评价，不断通过复制、交叉、变异等遗传算子的作用，使种群在适应度函数的约束下不断进化，算法终止时得到最优/次最优的问题解。图3为装配规划遗传算法的一般流程。

装配规划遗传算法的研究重点集中于设计装配序列的基因编码方式以包含更多的装配过程信息、设计基因操作的形式和改进遗传算法的局部搜索能力上。Lazzerini等[27]的分段编码遗传算法中，将染色体分为3段编码，第1段表示参与装配的零件编号，第2段表示零件的可行装配方向，第3段表示装配工具，从而使染色体包含了部分工艺信息。为了提高算法的性能，文中将装配体分解为子装配体进行装配，减少了参加装配序列规划的零件数目；Guan等[28]采用基因团编码方式，一个基因团表达一个零件的装配操作，由被装配零件号装配元、装配工具装配元、装配方向装配元和装配类型装配元组成。在扩大采样空间选择下一代种群的基础上，通过交叉和多层次变异实现装配序列并行优化。廖小云和陈湘凤[29]在装配序列规划遗传算法中设计了复制、交叉、变异、剪贴和断连5种遗传算子寻找装配序列优化解。在Smith等[30]的增强型遗传算法中，选择下一代个体并不完全依靠适应度，而是先把一定数量较优的个体复制到下一代，将适应度低但几何可行的序列用于继续产生序列，直到满足下一代种群中序列个数的需求，从而使算法能跳出局部最优点，在全局范围内搜索最优解。

理论上，找到全局最优装配序列要求参加演化计算的种群规模要足够大，迭代次数要无限

多，但在计算资源和时间限制下是达不到要求的。因此，遗传算法求解装配规划问题的效率和结果依赖于初始种群规模及其质量、遗传算子及其操作概率等因素。

4协同装配规划方法

装配体作为实现产品功能的载体，零部件可能由不同的企业设计，零部件和产品可能在不同的装配工厂完成装配过程，因此需要设计团队的协同工作和决策以保证装配质量和降低装配成本。计算机和网络技术的快速发展缩短了异地人员在时间和空间上的距离，为实时的“人－机－人”协同装配工作提供了可能。

Wisconsin-Madison大学[31]提出网络环境下的电子化装配（e-Assembly），探讨在Internet/Intranet上利用3D模型进行协同虚拟装配和拆卸的方法论和工具，拟实现的关键技术包括3D交互可视化、协同装配/拆卸/维护/回收等。目前已开发了Motive3D系统，利用Synthesizer模块可以交互/自动进行产品的装配建模和规划，Visualizer模块为用户在Web平台上提供装配序列规划结果的可视化仿真，但缺少交互修改、调整功能。在ATS项目[32]实施中，为了向异地的开发人员展示装配设计和装配规划结果，尝试利用VRML作为可视化工具，一方面供设计团队浏览零部件设计，另外将装配模型用文本编辑软件进行编辑，生成装配序列的VRML仿真文件，供异地的设计团队实时进行评价和提出修改意见。但手工编辑文件不但花费的时间长达一周，而且每次设计修改后都必须重新编辑；同时，仿真文件仅具有浏览功能，不能进行交互修改。

Web环境下的协同装配规划方法[33]采用协同工作环境下的装配建模、装配规划任务分配和装配序列合成等技术，通过对复杂产品装配规划问题的分解，即降低了单机规划工作模式的复杂度，又便于集中不同地域多专家的装配知识和经验进行装配规划方案的协同决策。面向协同广义装配[34]通过确定装配子任务编码方法、装配人员评价指数和制定协同装配协议，以VRML为产品模型载体实现协同装配系统。在装配知识和规则的支撑下，支持局域网内多用户实施产品预装配、验证零部件可装配性，相关的装配人员能够协同讨论装配方案。Web环境下3D交互装配可视化仿真结构是一个符合开放技术标准的可视化装配系统[35]，它基于VRML-Java实现装配场景的动态生成、装配控制、碰撞检测以及装配过程的动画回放等功能，目前完成了基于“堆叠”思路的装配验证方式。但该系统属于单用户系统，不能支持多用户的实时协同装配工作。

5结论与展望

CAAP的研究在理论上取得了一定的成果，在工业界也得到了一定的应用，但相对而言还很少，这说明该技术距离工业实用还存在较大差距。装配规划是一个经验和知识密集型的工作，同时又与具体行业和产品有紧密的关系。经典装配规划方法的精确推理在保证序列的几何可行性方面具有优势，而软计算技术能够将人的模糊知识融入规划过程中，使得结果具有更好的工艺可行性，两者的适当结合将有利于模仿人类装配专家的实际装配规划过程，从而得到合理的装配方案。

跨地域、跨国家的网络化、协同化产品设计和制造新模式的形成使产品装配成为一个需要协同工作和决策的问题。随着虚拟现实技术和网络技术的进一步发展，建立基于网络的协同装配决策平台和虚拟环境，支持异地多人员协同装配方案决策将是新形势下装配规划研究的新趋势。

参考文献

[1]苏强,林志航.计算机辅助装配顺序规划研究综述[J].机械科学与技术,1999,18(6):1006~1012.

[2]石淼,唐朔飞,李明树.装配序列规划研究综述[J].计算机研究与发展,1994,31(6):30~34.

[3]牛新文,丁汉,熊有伦.计算机辅助装配顺序规划研究综述[J].中国机械工程,2001,12(12):1440~1443.

遗传算法论文范文第5篇

关键词：计算机应用;装配规划;综述;虚拟现实;软计算;协同装配

装配是产品生命周期的重要环节，是实现产品功能的主要过程。写作毕业论文装配成本占产品制造成本40%～50%，装配自动化一直是制造自动化中的瓶颈问题。装配规划是在给定产品与相关制造资源的完整描述前提下，得到产品详细的装配方案的过程，对指导产品可装配性设计、提高产品装配质量和降低装配成本具有重要意义。产品的装配规划通常需要得到零部件的装配序列、装配路径、使用的工装夹具和装配时间等内容[1]~[3]。

较早的传统装配规划采用人工方式，工艺人员根据设计图纸和技术文档，通过分析产品装配图中零件的几何形状和位置关系，必要时再和设计人员进行讨论，进一步明确设计者的真正意图，利用自己的经验和知识规划出产品的装配方案。这种方法工作量大、效率低，且难于保证装配方案的经济性。

随着计算机集成制造CIMS和并行工程CE技术的发展和应用，一方面对装配相关的设计技术提出了计算机化的要求，以提高和产品开发过程中其他环节的集成化程度。另一方面要求装配方案的优化以降低成本和缩短规划时间以加快产品开发进程。受“需求牵引”和“技术推动”两方面的影响，80年代初，出现了对计算机辅助装配规划(ComputerAidedAssemblyPlanning，CAAP)技术的研究。到目前为止，CAAP经历了几个不同的发展阶段，出现了4种代表性的方法，按照出现的时间顺序及方法的特点，笔者将其归结为经典装配规划方法、虚拟装配规划方法、装配规划软计算方法和协同装配规划方法。

1经典装配规划方法

早期CAAP的研究侧重于装配序列的规划，以产品CAD装配模型为基础，写作硕士论文一般采用几何推理的方法，通过产品装配建模、装配序列推理和表达以及装配序列评价和选择为产品面向装配的设计和装配工艺规划提供指导和支持，其过程通常如图1所示。

1.1产品装配建模

产品装配模型是装配规划的基础，为装配规划提供装配体和零部件的相关信息。常用的装配信息表达模型可分为图模型和矩阵模型。法国学者Bourjauct提出了联系图模型[4]，将零件之间的物理接触关系定义为联系即装配关系，图中的节点对应零件，边表示所连接的零件间至少有一种装配关系。关系模型[5]进一步区分了零件之间的接触关系和联接关系，图中包含3种实体类型：零件、接触和联接，边表达了实体间的关系。产品等级装配模型[6]将装配体看成具有层次结构性，即装配体可以分解为子装配体，子装配体又可分解为下级子装配体和零件的集合，以此表达产品的装配组成。

矩阵比图易于计算机表达和实现。Dini和Santochi[7]利用干涉矩阵、接触矩阵和连接矩阵表达产品，干涉矩阵描述了零部件间沿坐标轴方向装配时相互间的干涉情况，接触矩阵描述了零部件间的物理接触状态，连接矩阵描述了零部件间的连接类型。为减少矩阵的数量，Huang[8]等把6个干涉矩阵合并为一个拆卸矩阵，集成的表达零部件间沿坐标轴方向的干涉情况。

1.2装配序列推理和表达

基于联系图模型，Bourjauct采用人机交互“问答式”方法获取装配优先约束关系[4]，写作医学论文随后DeFazio和Whitney[9]，Baldwin[10]等人的工作进一步较少了需要由用户回答问题的数量，然后通过对装配优约束关系进行推理得到联络建立优先关系的层次模型表达产品的装配序列。

“割集”法是基于拆卸策略的装配规划中通常采用的图论算法。HomemdeMell和Sanderson[5]通过对产品联接图进行缩并，利用“割集”算法对联接图进行循环分解，生成所有可能的子装配体，直到不可再分。并提出了装配序列的AND/OR图表达方法，图中的节点对应装配过程中的子装配体或零件，超弧表达将子装配体或零件联接在一起形成更大子装配体的装配操作。因为“割集”算法的计算复杂性为O(3N)(N为零件个数)，因此，对于复杂产品的装配顺序规划存在指数爆炸问题，这是难以让人接受的。

1.3装配序列评价和选择

装配序列的选择对装配线设计、装配成本、装配设备选择有很大影响，写作职称论文而评价是选择的基础。装配序列的评价可分为定性和定量两方面因素[11]~[13]，定性因素主要考虑的有装配方向换向的频度、子装配体的稳定性和安全性、装配操作任务间的并行性、子装配体的结合性和模块性、紧固件的装配、零件的聚合等。定量因素主要考虑的有整个装配时间(包括子装配体的操作时间、运输时间等)、整个装配成本(包括劳动成本、夹紧和加工成本)、产品在装配中再定位的次数、夹具的数目、操作者的数目、机器人手爪的数目、工作台的数目等。

更多的经典装配规划方法研究文献可以参见TexasA&M大学Wolter教授的“AssemblyPlanningBibliography”[14]，其中收集了自1980年起近15年经典装配规划方法的相关研究。经典方法一般表达出全部的序列解空间，这使它可能从中找出最优的装配序列，但随着产品中零件数量的增加，解空间的组合爆炸给序列的存储、选优带来极大困难；且序列的几何推理方法不易融入人类的装配知识，难免产生众多几何可行但工艺不可行的序列结果。

2虚拟装配规划方法

虚拟现实技术为装配规划的“人－机”协同工作提供了契机。虚拟装配是指由操作者通过数据手套和三维立体显示设备直接三维操作虚拟零部件来模拟装配/拆卸过程，无需产品或支撑过程的物理实现，通过分析、先验模型、可视化和数据表达等手段，利用计算机工具来安排或辅助与装配有关的工程决策[15]。虚拟装配过程中，人机可以充分发挥各自的优势，即人通过直觉/装配经验和知识决定产品的装配过程，但不能精确地判断当前所有可能装配的零件，也不太可能准确判定装配某一零件后装配体的稳定性等因素，而通过一定算法和规则实现的机器智能刚好弥补人的不足。虚拟装配方法得到的不仅仅是零件的顺序，还可以包括零件路径、装配工具、夹具和工作台等信息。图2为虚拟装配规划的工作步骤。

国外虚拟装配规划的研究以沉浸式虚拟装配环境VADE[16],[17](VirtualAssemblyDesignEnvironment)为代表，写作英语论文通过建立一个装配规划和评价的虚拟环境来探索运用虚拟现实技术进行设计、制造的潜在技术可能性，为机械系统装配体的规划、评价和验证提供支持。在虚拟环境中，利用提取并导入的CAD系统产生的装配约束信息引导装配过程；通过引入了质量、惯性和加速度等物理属性，基于物理特性进行装配建模，逼真地模拟真实装配环境；支持双手的灵活装配和操作；记录虚拟装配过程中产生的扫体积和路径信息并可进行编辑；建立了工具/零件/人相互作用模型，支持装配工具在虚拟装配环境中的运用。

国内管强等[18]将虚拟现实技术与面向装配设计的理论相结合，建立了一个虚拟环境下的面

向装配设计系统（VirDFA）。万华根等[19]建立了一个具有多通道界面的虚拟设计与虚拟装配系统（VDVAS），通过直接三维操作和语音命令方便地对零件进行交互拆装以建立零件的装配顺序和装配路径等装配信息。在面向过程与历史的虚拟设计与装配环境（VIRDAS）中，张树有等[20]通过识别装配关系进行装配运动的导航，实现虚拟拆卸/装配顺序规划、虚拟装配分析。从集成的观点出发，姚珺等[21]提出面向产品设计全过程的虚拟装配体系结构，从方案设计、结构设计和装配工艺设计3个层次上分阶段地对产品可装配性进行分析与评价。田丰等[22]提出一个面向虚拟装配的三维交互平台（VAT），简化了虚拟装配应用系统的构造，便于应用的快速生成。

应用虚拟现实环境开展装配规划，提供了一种新的思路和工具。但是，虚拟环境的构建需要较大资金的软硬件投入，另外，虚拟现实技术本身（如图形的高速刷新）及其相关硬件技术（如力触觉设备）的不成熟使得虚拟装配的研究仍处于探索阶段。

3装配规划软计算方法

1994年，Zadeh教授将模糊逻辑与智能技术结合起来，提出了软计算方法（softcomputing）[23]。软计算以模糊逻辑、神经网络和概率推理为基础，不追求问题的精确解，以近似性和不确定性为主要特征，所得到的是精确或不精确问题的近似解。为避免组合爆炸同时又能得到较优的装配规划方案，近来，基于建模、表达和寻优一体化的装配规划软计算方法得到广泛关注。

3.1装配规划神经网络方法

神经网络是模拟人类形象思维的一种人工智能方法，它是由大量神经元广泛互连而成的复杂网络系统，写作留学生论文单一神经元可以有许多输入、输出，神经元之间的相互作用通过连接的权值体现，神经元的输出是其输入的函数。若将优化计算问题的目标函数与网络某种状态函数(通常称网络能量函数)对应起来，网络动态向能量函数极小值方向移动的过程就可视作优化问题的求解过程，稳态点则是优化问题的局部或全局最优解。

Hong和Cho[24]用于机器人装配顺序优化的Hopfiled神经网络中，考虑装配约束、子装配体稳定性和装配方向改变等因素建立网络的能量方程，基于优先约束推理和专家系统提供的装配成本驱动网络的进化方程得到优化的序列。但由于神经网络缺乏全局搜索能力，计算结果显示，该方法容易产生不优化的装配顺序，且常常只能得到一个局部最优的装配序列。另外，参数选择和初始条件对网络的灵敏度影响大；神经网络在应用前须进行训练，而训练时要由专家提供较多可行的顺序作为样本。而样本可能是针对某种类型的产品，对其它类型的产品则不一定适用，该方法的应用范围窄。

3.2装配规划模拟退火算法

模拟退火算法源于固体退火思想，将一个优化问题比拟成一个热力学系统，将目标函数比拟为系统的能量，将优化求解过程比拟成系统逐步降温以达到最低能量状态的退火过程，通过模拟固体的退火过程获得优化问题的全局最优解。

Saeid等[25]利用模拟退火算法进行装配序列规划时，根据产品装配模型获得装配优先关系，将装配过程总装配时间和重定向次数运用多属性应用理论组合成单一目标函数，作为装配序列优化的评价函数。Hong和Cho[26]将装配约束和装配过程的成本映射为装配序列能量函数，利用模拟退火算法使装配序列能量函数扰动地逐步减小，经过多次迭代，直到能量函数不再变化为止，最后得到具有最小装配成本的装配序列。作者将该方法应用到一个电子继电器装配体上，并将其性能与利用神经网络[24]的装配规划方法进行了比较，结果显示基于模拟退火的装配序列优化方法可以产生较好的装配序列并且在运算时间上优于人工神经网络方法。

模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优，但模拟退火算法对整个搜索空间的状况了解不多，不能使搜索过程进入最有希望的搜索区域，从而使得算法的运算效率不高。

3.3装配规划遗传算法

在众多软计算方法中，遗传算法得到了众多研究者的重视。写作工作总结遗传算法是模仿生物自然选择和遗传机制的随机搜索算法，它将问题的可能解组成种群，将每一个可能的解看作种群的个体，从一组随机给定的初始种群开始，持续在整个种群空间内随机搜索，按照一定的评估策略即适应度函数对每一个体进行评价，不断通过复制、交叉、变异等遗传算子的作用，使种群在适应度函数的约束下不断进化，算法终止时得到最优/次最优的问题解。图3为装配规划遗传算法的一般流程。

装配规划遗传算法的研究重点集中于设计装配序列的基因编码方式以包含更多的装配过程信息、设计基因操作的形式和改进遗传算法的局部搜索能力上。Lazzerini等[27]的分段编码遗传算法中，将染色体分为3段编码，第1段表示参与装配的零件编号，第2段表示零件的可行装配方向，第3段表示装配工具，从而使染色体包含了部分工艺信息。为了提高算法的性能，文中将装配体分解为子装配体进行装配，减少了参加装配序列规划的零件数目；Guan等[28]采用基因团编码方式，一个基因团表达一个零件的装配操作，由被装配零件号装配元、装配工具装配元、装配方向装配元和装配类型装配元组成。在扩大采样空间选择下一代种群的基础上，通过交叉和多层次变异实现装配序列并行优化。廖小云和陈湘凤[29]在装配序列规划遗传算法中设计了复制、交叉、变异、剪贴和断连5种遗传算子寻找装配序列优化解。在Smith等[30]的增强型遗传算法中，选择下一代个体并不完全依靠适应度，而是先把一定数量较优的个体复制到下一代，将适应度低但几何可行的序列用于继续产生序列，直到满足下一代种群中序列个数的需求，从而使算法能跳出局部最优点，在全局范围内搜索最优解。

理论上，找到全局最优装配序列要求参加演化计算的种群规模要足够大，迭代次数要无限

多，但在计算资源和时间限制下是达不到要求的。因此，遗传算法求解装配规划问题的效率和结果依赖于初始种群规模及其质量、遗传算子及其操作概率等因素。

4协同装配规划方法

装配体作为实现产品功能的载体，零部件可能由不同的企业设计，零部件和产品可能在不同的装配工厂完成装配过程，因此需要设计团队的协同工作和决策以保证装配质量和降低装配成本。计算机和网络技术的快速发展缩短了异地人员在时间和空间上的距离，为实时的“人－机－人”协同装配工作提供了可能。

Wisconsin-Madison大学[31]提出网络环境下的电子化装配（e-Assembly），探讨在Internet/Intranet上利用3D模型进行协同虚拟装配和拆卸的方法论和工具，拟实现的关键技术包括3D交互可视化、协同装配/拆卸/维护/回收等。目前已开发了Motive3D系统，利用Synthesizer模块可以交互/自动进行产品的装配建模和规划，Visualizer模块为用户在Web平台上提供装配序列规划结果的可视化仿真，但缺少交互修改、调整功能。在ATS项目[32]实施中，为了向异地的开发人员展示装配设计和装配规划结果，尝试利用VRML作为可视化工具，一方面供设计团队浏览零部件设计，另外将装配模型用文本编辑软件进行编辑，生成装配序列的VRML仿真文件，供异地的设计团队实时进行评价和提出修改意见。但手工编辑文件不但花费的时间长达一周，而且每次设计修改后都必须重新编辑；同时，仿真文件仅具有浏览功能，不能进行交互修改。

Web环境下的协同装配规划方法[33]采用协同工作环境下的装配建模、装配规划任务分配和装配序列合成等技术，通过对复杂产品装配规划问题的分解，即降低了单机规划工作模式的复杂度，又便于集中不同地域多专家的装配知识和经验进行装配规划方案的协同决策。面向协同广义装配[34]通过确定装配子任务编码方法、装配人员评价指数和制定协同装配协议，以VRML为产品模型载体实现协同装配系统。在装配知识和规则的支撑下，支持局域网内多用户实施产品预装配、验证零部件可装配性，相关的装配人员能够协同讨论装配方案。Web环境下3D交互装配可视化仿真结构是一个符合开放技术标准的可视化装配系统[35]，它基于VRML-Java实现装配场景的动态生成、装配控制、碰撞检测以及装配过程的动画回放等功能，目前完成了基于“堆叠”思路的装配验证方式。但该系统属于单用户系统，不能支持多用户的实时协同装配工作。

5结论与展望

CAAP的研究在理论上取得了一定的成果，在工业界也得到了一定的应用，但相对而言还很少，这说明该技术距离工业实用还存在较大差距。装配规划是一个经验和知识密集型的工作，同时又与具体行业和产品有紧密的关系。经典装配规划方法的精确推理在保证序列的几何可行性方面具有优势，而软计算技术能够将人的模糊知识融入规划过程中，使得结果具有更好的工艺可行性，两者的适当结合将有利于模仿人类装配专家的实际装配规划过程，从而得到合理的装配方案。

跨地域、跨国家的网络化、协同化产品设计和制造新模式的形成使产品装配成为一个需要协同工作和决策的问题。随着虚拟现实技术和网络技术的进一步发展，建立基于网络的协同装配决策平台和虚拟环境，支持异地多人员协同装配方案决策将是新形势下装配规划研究的新趋势。

参考文献

[1]苏强,林志航.计算机辅助装配顺序规划研究综述[J].机械科学与技术,1999,18(6):1006~1012.

[2]石淼,唐朔飞,李明树.装配序列规划研究综述[J].计算机研究与发展,1994,31(6):30~34.

[3]牛新文,丁汉,熊有伦.计算机辅助装配顺序规划研究综述[J].中国机械工程,2001,12(12):1440~1443.