|
99—4—10 A study on the problems of solving multiple scheme design by the use of genetic algorithm Ouyang Miaoan(South China University of Science and Technology, Postdoctoral Workstation of Foshan Enterprises) Abstract: This paper put forward a genetic algorithm for solving the problems of multiple scheme design in the design of intelligence. It discussed the key technique, including a kind of an improved genetic algorithm, for solving the problems of multi-scheme in genetic algorcthm and thus avoided a too early convergence at a partial optimum solution happened in the standard genetic algorithm and also accelerated the convergent speed in an overall optimization. An example of making solutions for multiple schemes in the modular synthesis of machine tools is presented. The genetic algorithm can settle problems effectively on the selection of modules and the "combined explosion" in issues of combination.
Key words: Intelligent design, Genetic algorithm, Multiple schemede design, Modular synthesis of machine tool.
Fig 2 Tab 0 Ref 3 “Jixie Sheji”8172 1 引言
智能设计是知识密集型工业阶段，设计自动化领域中，以追求最高效率求得工程系统最优方案或技术问题最优解为目的的计算机应用技术。工程问题的智能设计不可避免要面对多方案问题，多方案求解是工程问题普遍存在的问题，也是智能设计的关键问题之一，没有多方案也就没有方案的最优，没有最优方案也就体现不出智能设计的真正意义。然而，至今大多数智能设计主题集中在知识获取、知识表示、知识处理、人机界面等方面。同时以往的智能系统，在解决多方案设计时，基本上采用一种原理综合方法，如形态学矩阵方法，键合图方法，这些方法一般从功能分析角度列举并组合出可选方案，但这些组合方法的方案数太多，且难以进行评价与优化，鉴于以上原因，有必要探索一种新的处理机制来解决智能设计中的多方案设计问题。
遗传算法（Genetic Algorithm, GA）是计算智能（CI）的一个分支，与人工神经网络一样，遗传算法师法大自然，从大自然的杰作——“生物进化”中得到灵感与启迪。自然界的进化过程总是客观地遵循着“物竞天演，适者生存”的法则。1961年，Bledsoe就已提出将生物学中的一些概念用于系统的分析研究，60年代末美国密歇根大学John Holland提出了遗传算法的概念，从此，“自然选择”的法则开始在工程应用中得到发展。1975年John Holland所著的《自然和人工系统中的适应性》（Adaptation in Natural and Artificial System）为生物学、控制论和人工智能综合应用的引导与分析奠定了整个算法的理论基础。遗传算法的研究特别对人工智能中计算智能的发展有着重要的意义，为计算智能这一新的学科打下了基础。
遗传算法的应用前景极为广泛，已应用于神经网络结构优化设计、神经网络权重训练，替代传统的优化设计、模糊逻辑控制器的矩阵的参数优化设计、决策支持系统、推销员路径的优化、VLSI数字电路设计。在制造领域，应用于广泛的制造智能系统中，如机构零部件和切削刀具的优化设计、生产调度、非线性系统的辨识、控制和测量系统等等。本文试图在智能设计中采用遗传算法，解决多方案求解问题。 2 多方案求解的算法描述
2．1 遗传算法的数学描述
假设有一个待优化的问题：
F=f(x,y,z), F∈R, (x,y,z)∈C (1) 式中：x,y,z——自变量，它可以是数值量，也可以是逻辑量，甚至可以是符号量。每一组xi,yi,zi∈C构成问题的一个解；
C——既可以看成自变量x,y,z的定义域，也可以看成问题的约束条件，或所有满足约束条件的解构成的解空间；
F——属于实数域R的一个实数，也可看成对一组解(xi,yi,zi)∈C的质量优劣的度量；
f——表示由解空间C到实数域R的一个映射，对它的唯一要求是它必须有定义，即对于一个确定的解(xi,yi,zi)∈C，都可算出一个确定的Fi与之对应。
优化目标是：找到(x0,y0,z0)∈C，使得F=f(x0,y0,z0)→max，在求解多方案问题时，应该找到一系列的解，得到最优解，次优解等等。
2．2 遗传算法求解多方案问题的求解策略
遗传算法采用群体全局搜索技术，初始群体的产生意味着多个初始方案的产生，这些初始方案其性态一般都不好，其好坏通过适合度计算来衡量，根据适合度的大小进行方案的排序，遗传算法的求解通过三种主要算子，即选种、杂交和突变来实现。算子的目的是产生新一代群体，即产生更好的方案，这种算子一直进行到得到用户满意的一个或多个方案。遗传算法求解策略如图1所示。
图1 遗传算法求解策略 通过选种、杂交、突变得到的新一代群体代替上一代群体，对新群体的个体进行评价，判定结果是否满意并判定迭代过程是否收敛，不满意或不收敛重复基因算子过程，直到达到结果满意或迭代收敛。通过以上的遗传算法得到一组个体，再根据各个体的合适度大小进行排序，构成一系列的可供选择使用的多个模块设计方案。由系统确定或用户交互式确定最优方案，或供方案设计的再设计使用。 3 遗传算法求解模块综合多方案的关键问题
模块综合是指在对一定范围内的不同规格的产品，在进行功能分析，划分并设计出一系列功能模块的基础上，通过模块的选择和组合可以构成不同的产品以满足市场的不同需求。以下通过结合机床模块综合的实际，探讨遗传算法的关键技术。
3．1 初始群体的生成
初始群体的生成以基因编码为基础，基因（gene）是描述生物特性的染色体（chromosome)的最基本单位，一个染色体由若干个基因组成，染色体也称为个体(individual)。基因是以一定的代码表示，这个代码可以是数字串，也可以是字符串。
机床模块化设计中，经过模块划分后，每一个模块都赋于一个模块代号，例如：对于四种立柱（立柱模块)，其模块代号分别为：“C51AA11”，“C51BA11”，“C51CA11”及“C51DA11”。把模块代号翻译成一个一定范围内的整数，比如：以上四种模块用1，2，3，4来表示，该整数就代表一个基因，一连串的整数构成一个个体，对应于一连串的模块组合成一种机床，个体代表机床，同时代表问题的一个解（方案)。
数控立车模块方案采用形态学矩阵方法表示，形态学矩阵中横行与纵列分别表示模块方案的横系列（各组成模块）与纵系列（加工的最大直径），横竖交叉处为模块代号，通过编码生成相应的模块基因代码。代码含义：如“-2-2-2-2-”代表机床是由如下模块组成：C51BA17，C51BA11，C51BA13，C51AA20等等。
对于特定类型的机床，如：CK，组成机床模块的类型已经确定，为了使码链有意义，引进力流的概念，也就是说，码链上，特定位置的基因其含义是确定的，比如说，码链的第一位应对应工作台模块，在这个位置上的基因变化，意味着选用的工作台模块规格在变化。为了方便计算机处理，每个基因用一定比特数的二进制码表示，如：基因“2”在计算机中表示为“10”。
初始群体的产生是由计算机按随机的方法产生一系列的二进制码链，每个码链代表某一群体中的一位祖先，一定数量的祖先就构成最原始的群体。这一群体代表优化问题的一些可能的解。当然，一般来说，它们的素质都很差。GA的任务是要从这些祖先出发，模拟进化过程，择优汰劣，最后得出非常优秀的群体与个体，满足优化的要求。在模块综合问题中，假设一种机床由11（CHROM-LENGTH=11)个模块组成，每个模块由2（GENE-LENGTH=2)位二进制串表示，两位二进制串可以表示4种模块（如立柱模块有4种候选模块），初始群体产生一个随机个体(0111110001100001110000)，并可以转换成相应的十进制串和模块代号（省略C51）。
3．2 适合度的计算
适合度（Fitness)是评价个体优劣的度量。设l是个体（方案）的数目，m是组成个体基因（模块）的数目，n为性能评价指标数目。Pjk与 为评价指标和相对应的权重，则每个个体的适合度（Fi）为组成个体的基因的适合度（Gj）之和，由公式（2）表示。
 (2) 其中：i——个体数（方案数），1≤i≤l；
j——基因数（模块数），1≤j≤m；
k——评价指标数，1≤k≤n；
Wj——基因权重，表示各模块的重要性程度。
公式(3）用来计算基因（模块）的适合度。
 (3) 其中： 
P′j1，P′j2，P′jn是评价指标必须满足值。评价指标可以是数值量，也可以是逻辑量，还可以是符号量。在数控立车方案设计中的评价指标如：最大加工直径、工作台最大承重量、模块的重量、成本、工艺指标、模块的相似度、共有度、模块与模块之间的接口检验或是用户的特殊要求等等。
3．3 选种算子
选种就是从群体中选取适合度高的个体，作为繁殖（reproduction)后代(offsprings)的双亲（parents)。选种的规则是：适合度Fi越大的个体，有更大的选中概率Pi，一般Pi∝Fi。因此，适合度为群体的进化提供了选择压力（Selection pressure)，即适合度愈大的个体有更多的机会繁殖后代，使其优良特性得以遗传和保留。这样所有的个体被分成两组：Ph和Pl，Ph为适合度高的个体集合，Pl为适合度低的个体集合。Ph集合被选中，用来繁殖后代，使其优良特性得以遗传和保留，Pl集合被淘汰。
3．4 杂交算子
根据生物学上杂交优势的原理，杂交是GA成功的一个关键。杂交保证优良的品质可以从父辈遗传到子辈，一般而言，新群体的平均素质和最优个体的素质可望比上一代的素质要好。将随机选中的双亲进行杂交，通过交换一对父个体的部分基因产生一对新的子个体，杂交算子分两步进行：首先随机地选两个个体（父个体）；其次随机产生一个整数k，k要大于等于1而小于基因码链的长度，从k位置起，将一定长度（图中k=k+1)父个体进行交换。机床模块综合问题的杂交是建立在方案求解的形态学矩阵的基础之上，属于平面式杂交。假设有两个个体，个体1为“…-3-2-3-2-”个体2为“…-2-3-2-3-”如图2a和图2b，杂交过程如图2c，杂交算子产生两个新子个体分别为：“…-3-3-2-2-”与“…-2-2-3-3-”如图2d和图2e。
图2 杂交算子示意图 3.5 突变算子
突变用以模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，描述了生物的变异特性。突变增加了群体基因材料的多样性，增加了自然选择的余地，有利的变异使自然选择的作用得以遗传和保留；而有害的变异则将在逐代遗传中被淘汰。突变在GA中起辅助作用，因为选择和杂交虽然可以有效地重组新的个体，但有时变得太过份而失去潜在的某些优良品质，突变可以保护那些无法挽回的损失。突变算子是，先随机产生一个整数，确定突变的基因的位置，再产生一随机数代表突变的值。
3.6 标准遗传算法SGA的改进
标准的遗传算法（称SGA)中，由于后代替换双亲，存在以下问题，优良基因结构被基因算子破坏的可能性较大，因此群体需要保护；如果群体的适合度变化不大或过大，会引起选择压力不足或波动，导致迭代过程过早收敛或发生振荡，因此群体需要做比较大的变动，这是一对矛盾。经验的方法是采用适中大小的杂交率Pc和突变率Pm，固定大小的Pc和Pm，并不能有效地解决这对矛盾，本文采用变概率（称AGA)的方法处理以上问题。适合度既是评价方案优劣的指标，也是控制算法收敛的一个指标，综合考虑各种适合度大小（假设f）为个体适合度， 为群体的平均适合度，fmax为群体的最大适合度，f′为待杂交的个体中，适合度较大的个体的适合度）的变化来确定Pc，Pm值。
采用动态可调杂交率和突变率的方法，可以折中地处理遗传算法的矛盾，AGA的采用既可以减小遗传的代数，以提高求解效率，也可以更好地避免象SGA陷入局部最优。 4 工程应用实例
机床模块综合问题中的遗传算法，通过给定用户的约束要求，作为计算适合度的评价指标，通过遗传算法，求出组合成机床的模块方案，通过多方案和方案排序得到最佳方案。
设总体方案数为l=30，组成机床的模块数为m=11，每种模块有4个可选模块，评价指标简化为满足最大加工直径要求和模块与模块之间接口要求，即k=2。取杂交率为0.9，突变率为0.05，最大进化代数为100，当群体平均适合度不再增加时算法结束，随机产生群体后进入进化过程。通过控制变量实施两种策略，可以看到采用SGA遗传代数为9代，而采用AGA只需7代（运行实例略）。 作者单位： 参考文献
1 查建中．智能工程．北京：机械工业出版社，1992，3
2 檀润华，陈 鹰，路甬祥．产生多个设计方案的键合图方法．机械设计，1998，1
3 Ermer G.etc. Steps towards integrating function-based models and bond graphs for conceptual design in engineering.DSC-Vol.47,Automated modelling for design，ASME,1993,47～62 | 
