另外，从减少漏磁的角度考虑，衔铁的吸合面积还要根据阀芯端面面积的大小来选择，二者的面积不能有太大的差异。
（5）线圈电阻
电磁线圈的电阻与线圈导线长度、线径、线圈材料以及线圈工作温度等因素有关。通常线圈采用铜丝绕制而成，则线圈电阻R 的计算公式如式（3-11）所示
))20(1(20?+=t t αρρ （3-10） )/(2r l R t πρ= （3-11） 其中α为铜的温度系数，等于0.0041/℃，r 为铜丝导线线径，20ρ为铜在温度为20℃时的电阻率，等于，m ??×?61001754.0t ρ铜在温度为t 时的电阻率，为导线总长度，等于线圈匝数和单圈线
圈导线长度的乘积。由导线电阻计算公式，线圈电阻与线径的平方成反比，与导线长度成正比。当
驱动电压相同时，电阻越大，电流上升越慢，导致开启响应时间增加，同时电路的铜损增加，使线圈和阀芯温升增加。因此，应该尽量减小线圈电阻。在线圈匝数确定且阀芯结构允许的情况下，可以适当加大线径，以减小线圈电阻。
l R I P cu 2=?3.2.2 控制参数影响分析
（1）驱动电压
在电磁阀开启的初始阶段，驱动电压越大，线圈电流上升就越快，电磁吸力的上升速度也越快，这将缩短衔铁的吸合触动响应时间，同时在整个吸合动作过程中衔铁的运动加速度也越大，在间隙宽度不变的情况下，运动时间将缩短。因此，提高线圈激励电压是提高电磁阀开启响应速度的有效方法，但是驱动电压的提高受成本、阀芯的饱和磁感应强度以及电路器件的性能等因素的影响。由于阀芯的饱和磁感应强度基本不变，在驱动电压达到一定大小时，再增加驱动电压，效果已经不是很明显，而且多余的能量输入会造成电路发热量的增加，使阀芯和线圈的温升增加，反而会降低阀芯的饱和磁感应强度。此外，电流峰值过高会对线圈及电路中使用的其它器件造成破坏。因此，在电磁阀开启阶段，对线圈输入的高压幅值要根据线圈匝数、线路电阻以及线圈电感等参数来选择。在电磁阀保持阶段，电磁阀驱动电路应该为线圈提供能够使衔铁克服弹簧力并稳定地保持吸合状态的最小电压，使线圈电流维持在一个较低的水平，以减少能量损耗。在衔铁复位过程中，较低的保持电流还有利于缩短线圈电流的衰减时间，提高衔铁复位响应速度。
（2）主脉冲宽度
在激励电压幅值确定的情况下，主脉冲宽度决定了在衔铁吸合过程中，对电磁线圈的能量输入强度。因此，它只对电磁阀的开启响应特性有影响。当主脉冲宽度加大，线圈激励时间加长，输入能量增大，线圈电流幅值就越大，最大电磁吸力就越大，衔铁运动所需时间也会缩短。但是当主脉冲宽度达到一定值时，衔铁已经运动到吸合位置时，再增加脉冲宽度不但没有必要，反而会引起能量不必要的损耗，使阀芯温度上升。因此，对于一定幅值的驱动电压，存在一个最佳的主脉冲宽度，即衔铁到达吸合位置时的脉冲宽度。所以，主脉冲宽度要根据驱动电压幅值和电磁阀结构参数和工作行程等因素进行匹配。
3.3基于遗传算法的电磁阀多参数优化设计
影响高速电磁阀性能的参数很多，且各个参数之间相互作用、相互耦合，共同决定了高速电磁阀的特性，在设计电磁阀时，须综合考虑这些参数。采用传统的方法设计电磁阀，不但浪费人力物力，而且开发周期长。随着计算机处理能力的不断提高，越来越多的工程设计问题借助计算机进行优化设计，取得了良好的效果。采用优化设计方法对实际工程问题进行优化设计具有以下优点[145]： (1) 将一个大型的、复杂的、重复的问题简单化。
(2) 用最短的时间找到最优化的解决方法。
(3) 用动态的、科学的、计算机化的方法来解决问题。
(4) 适应了现代产品的快、优、省，一次成功的可靠性大。
遗传算法作为一种现代最优化方法，具有强大的随机搜索能力。它克服了传统优化方法容易陷入局部极值的缺点，是一种全局优化算法，常应用于大规模、多峰多态函数、含离散变量等情况下的全局最优化问题，具有求解速度快和质量好等优点。因此，本文选择遗传算法对高速电磁阀进行优化设计。
3.3.1遗传算法的特点及基本原理[145-149]
遗传算法又称GA（Genetic Algorithms）最早由美国Michigan大学的John Holland教授提出。他不仅设计了遗传算法的模拟与操作原理，并运用统计决策理论对遗传算法的搜索机理进行了理论分析，为遗传算法的发展奠定了基础。此后，De Jong将遗传算法应用于函数优化，并设计了一系列遗传算法的执行策略和性能评价指标。从20世纪80年代末开始，遗传算法无论是在理论方面还是实际应用上都得到迅速发展，成为诸多学科共同关注的研究热点。遗传算法通过模拟生物进化过程中的“优胜劣汰，适者生存”选择机制，来搜索优化问题的最优解。由于遗传算法简单通用，鲁棒性强，适于并行处理，目前已在工程优化、组合优化、模式识别、自适应控制、机器学习和人工生命等领域获得了广泛的应用。
遗传算法与传统的优化搜索算法不同，是一类可用于复杂系统优化计算的鲁棒搜索算法，主要具有如下特点：
（1）遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理方式，使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，同时可以方便地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了独特的优越性。
（2）遗传算法直接以目标函数值作为搜索信息，对搜索空间没有任何要求（如连通性、凸性等）。传统的优化算法不仅需要利用目标函数值，且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其它辅助信息。这个特性对很多无法或很难求导数的目标函数，或导数不存在的目标函数的优化问题，以及组合优化问题等，应用遗传算法时就显得比较方便，因为它避开了函数求导这个障碍。再者，利用目标函数值或个体适应度，可以把搜索范围集中到适应度较高的部分搜索范围中，从而提高了搜索效率。
（3）遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时甚至使搜索过程陷于局部最优解而停滞不前。遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程，属于一种并行操作过程，而不是从一个单一的个体开始搜索。对这个群体所进行的复制、交叉、变异等运算，产生出的就是新一代的群体，在这之中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法中所特有的一种隐含并行性。
（4）遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而遗传算法属于一种自适应概率搜索技术，其复制、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体，实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问
题的最优解。同时，遗传算法利用输出结果的性能来指导算法朝着最优的方向前进，不需要其它先决条件和特殊知识，这样保证了系统的鲁棒性，具有广泛的适应性。
遗传算法的核心是遗传操作，包括三个基本遗传算子：选择（selection）、交叉（crossover）、变异（mutation）。
（1）选择：它是指从一个旧群体中选择复制优胜个体、淘汰劣质个体而产生新种群的过程。选择操作目的是根据对各个个体在群体中的适应度评估，按照一定的规则或方法，把优秀的个体直接复制遗传到下一代或通过配对杂交产生新的个体遗传到下一代。遗传算法使用选择算子（reproduction operator）来实现选择操作。目前常用的选择算子有适应度比例法（fitness proportional model）、最佳个体保存法(elitist model)、随机竞争法 (stochastic tournament model)和排序选择法（rank-based model）等方法。其中，适应度比例法是遗传算法中最基本、最常用的选择方法。
（2）交叉：交叉是指把两个父代个体的部分基因按一定的方式相互交换，产生两个新的子代个体的过程。交叉运算是遗传算法的核心，是遗传算法区别于其它优化方法的重要特征。交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力。交叉操作过程包括两个基本内容：①从选择操作形成的配对库（mating pool）中，对个体进行两两配对，按预先设定的交叉概率来决定每对是否进行交叉操作；②确定进行交叉的方式，并根据设定的方法对配对的个体相互交换部分基因。个体配对的方式可以分为随机方式配对和确定方式配对，其中确定方式配对常用的方法有全局顺序配对、分组顺序配对以及优劣搭配配对。而常用的交叉方式有一点交叉、两点交叉及多点交叉、一致交叉、顺序交叉等方法，其中一点交叉方法是最基本的方法。
（3）变异：变异是以一个很小变异概率（mutation rate）随机地改变个体中某一个或某一些基因座上的基因值。变异操作的目的有两个：①挖掘群体中个体的多样性，防止遗传算法出现过早收敛现象。②使遗传算法具有局部的随机搜索能力。相对于选择算子和交叉算子来说，变异算子是遗传算法中的辅助算子，但却是不可或缺的。它与交叉算子妥善配合使用，使遗传算法能够兼备全局和局部的均衡搜索能力。若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，容易使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。常用的变异算子有基本变异算子、均匀变异算子、自适应变异算子等。
3.3.2遗传算法的应用步骤[145][146][148][149]
对于一个实际的待优化问题，遗传算法提供了一种解决问题的通用框架，一般包括以下几个步骤：
（1）根据待优化的问题确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间。
（2）建立优化模型，即确定目标函数的类型及数学描述形式或量化方法。
（3）确定表示可行解的染色体编码方法，即确定个体的基因型x及遗传算法的搜索空间。
遗传算法不直接处理问题空间的参数，必须将这些参数转换为遗传空间中由基因按一定结构组成的染色体，这一过程称为编码（representation）。编码必须满足完备性、健全性和非冗余性。常用的编码方法有二进制编码方法和实数编码方法。
（4）确定解码方法，即确定个体基因型到个体表现型的对应关系或转换方法。
（5）确定个体适应度的量化评价方法
遗传算法在搜索进化过程中通过评估函数值来评估个体或解的优劣，并作为进一步遗传操作的依据。评估函数值又称为适应度（fitness）。适应度值越大的个体就越好，得到的遗传机会就越大。在具体应用中，适应度函数的设计要结合待优化问题本身的要求而定，适应度函数设计将直接影响遗传算法的性能。确定个体的适应度值度量包括两个方面的内容：①将目标函数映射成适应度函数；
②对适应度进行定标，目的是在遗传算法的执行过程中，调节竞争水平，提高算法的性能。常用的适应度定标方法有指数定标法、线性定标法和乘幂定标法，应根据实际问题进行选择。
（6）设计算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。
（7）确定遗传算法的参数和变量。
遗传算法的主要参数有群体规模、最大代数目N M 、选择复制概率、交叉概率、变异概率等参数。这些参数的不同
会直接影响遗传算法的性能，
因此必须选择最优的参数，才
能得到最快的收敛速度和最好
的优化结果。
s P c P m P
图3-8 GA 的基本构造过程示意图
（8）确定指定结果的方法
和停止运行的准则。
当适应度函数的最大值已
知或最优解适应度的下限可以
确定时，一般以发现满足最大
值作为遗传算法迭代停止条
件。但这个条件在许多实际待
优化问题中并不适用。在实际
优化过程中，如果发现群体的
进化已趋于稳定状态，即群体
中的个体都是同一个体，则可
以终止迭代。或者当迭代已经
执行了预置的最大迭代数M ，
也可以终止迭代。
图3-8所示为遗传算法的
基本构造图。
3.3.3 基于GA 方法的电磁阀多参数优化设计[145-156]
根据遗传算法的优化步骤，对高速电磁阀进行优化设计。本文所研究的电磁阀结构简图及相关结构参数如图3-9 所示。 图3-9 电磁阀结构简图
（1）确定决策变量及约束条件
图3-9中，电磁阀的外径由喷油器的容许安装尺寸决定，即max 1D D ==25mm ，同时假定衔铁端面直径也等于；而电磁阀的气隙宽度5D 1D δ根据喷油系统的流量特性要求等因素确定。根据论文第二章建立的电磁阀静态吸力特性和动态响应特性数学模型，结合论文本章前部分对高速电磁阀结构和控制参数对电磁阀特性的影响分析结论，在利用遗传算法进行优化时结构参数选取，，，，，N ，d ，1d 2D 2d 1h 3h K ，这几个参数变量，控制参数选择最大激磁电压，主脉冲宽度作为待优化参数。根据以上分析可得遗传算法的决策变量：
0F H U H t },,,,,,,,,,{031221H L t U F K d N h h d D d X = （3-12） 其中
1d ，，， ，——电磁阀结构尺寸参数，如图3-9所示；
2D 2d 1h 3h N ——线圈匝数；
d ——线圈线径；
K ——弹簧刚度；
0F ——弹簧预紧力。
为减少计算量并考虑电磁阀的实际情况，可得决策参数取值范围：㎜， ㎜，㎜，23161≤≤d 18102≤≤D 1552≤≤d 931≤≤h ㎜，2053≤≤h ㎜； 7815≤≤N ， 2.15.0≤≤d ㎜，N/m ，400009000≤≤K 70100≤≤F N ；最大激磁电压， H U 12024≤≤H U V ；主脉冲宽度，ms 。
H t 5.01.0≤≤H t 显然决策参数还必须满足约束条件：>>，1d 2D 2d 4
)(2
321d N h D d π?>??。 （2）建立优化模型
高压共轨燃油喷射系统要求高速电磁阀工作时在开启阶段能够快速、平稳地吸合以打开电磁阀，开通油路；在关闭阶段衔铁能迅速复位以关闭电磁阀，阻断油路。因此，优化时主要考虑电磁阀的动态响应时间。在综合考虑高速电磁阀的性能要求的基础上，本文选取高速电磁阀开启响应时间和关闭响应时间之和作为高速电磁阀的优化设计目标，则优化目标函数可以表示为：
)(X T oc （3-13）
)()(X T X T oc =（3）确定编码方法
本文采用二进制编码方法对决策变量进行编码。其中变量、、、和都采用5位二进制编码，分别将各自的取值范围离散化为31个均等区域，对应从～共32个不同离散点。采用6位二进制编码，从～共64个不同离散点，即将匝数15～78的区域分为64等份，每点对应从15到78之间的一种线圈匝数。线径采用3位二进制编码，即将取值范围0.5～1.2㎜对应～共8个离散点。弹簧刚度1d 2D 2d 1h 3h )0(00000)32(11111N )0(000000)64(111111d )0(000)8(111K 采用5位二进制编码，从～共32个不同离散点对应9000～40000N/m ，相邻两个离散点相差1000N/m 。弹簧预紧力采用5位二进制编码，从～共32个不同离散点对应10～70N 。最大激磁电压采用6位二进制编码，从～共64个不同离散点，即将24～120V 的区域分为64等份。主脉冲宽度采用6位二进制编码，从～共64个不同离散点，即将0.1～0.5 ms 的区域分为64等份。因此，将各变量的二进制编码串按上面的顺序从左到右连接在一起，组成了一个56位的二进制编码串，就构成了本优化问题的染色体编码方法。
)0(00000)32(111110F )0(00000)32(11111H U )0(000000)64(111111H t )0(000000)64(111111（4）确定解码方法
解码时根据各变量的编码位数和在染色体编码串中的位置，将变量编码从编码串中提取出来，再由变量的取值范围即可计算出此时变量的实际值。以变量为例，处于染色体编码串的最左端，1d 1d
它由5位二进制编码组成，因此，只需提出染色体编码串的最左端5位二进制编码，并将其转化为十进制数，设值为，则根据的取值范围可得的实际值为
i y 1d 1d 1632
)1623()(1+×?=i y i d （3-14） （5）确定个体适应度的量化评价方法
由于优化目标函数的值总是非负的，并且优化目标是求的最小值，因此直接将个体的适应度取为对应的目标函数值，即取适应度函数为。
)(X T )(X T )(X T （6）设计遗传算子
这里选择算子使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用高斯变异算子。
（7）确定遗传算法的参数和变量
根据有关原则，这里选择群体大小M ＝50，终止代数G =500，交叉概率=0.8，变异概率P c p m 随进化代数自适应调整，即P m =0.1-[1:1:M ]×0.01/M 。
（8）确定指定结果的方法和停止运行的准则
当同一代个体之间的适应度值最大差别小于5%时，或达到最大代数时终止操作。
根据以上遗传算法优化设计步骤，对高速电磁阀进行优化设计，优化过程如图3-10所示。由图可见，计算到130代左右算法收敛，此时优化目标函数的值0.505ms 。各参数优化结果如表3-3所示。
)(X T
图3-10 目标函数的优化过程
)(X T 表3-3 参数优化结果 优化参数 优化结果
优化参数 优化结果 d 119.871
D 213.677 d 2 5.484
h 1 3.29 h 312.581
N 50 d 0.8
K 22000 m 9.7
U H 100.855 F 025.16 t H 0.255 3.3.4优化结果仿真 根据优化设计结果，利用高速电磁阀特性仿真系统对优化设计得出的电磁阀的特性进行了仿真。高速电磁阀的其它参数根据高速电磁阀的工作特性及结构要求等因素决定，如气隙宽度、衔铁阀杆直径及长度、线圈顶面到阀芯上端面的长度等，衔铁质量也根据估算得出。其中图3-11和图3-122h
为静态吸力特性仿真结果，图3-13为动态响应特性仿真结果。从仿真结果来看，优化后的电磁阀开启时间达到0.255ms ，关闭响应时间达到0.25ms ，总的响应时间为0.505ms 。
电流（A ）电磁吸力（N ）
μm μm μ
m μm μm μm μm μm μm μm μm μm
3-11 高速电磁阀静态吸力特性电磁力与电流关系仿真曲线
气隙宽度( )电磁吸力（N ）
μm
3-12 高速电磁阀静态吸力特性电磁力与气隙宽度关系仿真曲线
（a）电压输入方案
（b）驱动电流
（c）电磁吸力
（d）衔铁运动阻力
（e）衔铁位移响应
图3-13 参数优化后的高速电磁阀动态特性仿真结果
如果不考虑液体阻力的影响，而其它控制参数件相同，则通过仿真可以得到衔铁的位移响应如图3-14所示。此时电磁阀开启时间为0.17ms，关闭时间为0.22ms，分别比有液体阻力时减少了
0.085ms和0.03ms。因此，电磁阀开启时衔铁受到的液体阻力对开启时间有较大影响。
图3-14 不考虑液体阻力时衔铁位移响应
本章小结
设计了高速电磁阀性能仿真系统，介绍了仿真系统的开发情况。利用仿真系统对给定结构参数和控制参数的高速电磁阀的静态吸力特性和动态响应特性进行了仿真，并给出了仿真结果。分析了高速电磁阀主要结构参数和控制参数对其性能的影响。在此基础上，提出了利用遗传算法对电磁阀主要结构参数和控制参数进行优化设计，得到了优化结果，并对根据优化结果得到的电磁阀的性能进行了仿真。
实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)
遗传算法在多目标优化的应用：公式，讨论，概述/总括 概述 本文主要以适合度函数为基础的分配方法来阐述多目标遗传算法。传统的群落形成方法（niche formation method）在此也有适当的延伸,并提供了群落大小界定的理论根据。适合度分配方法可将外部决策者直接纳入问题研究范围，最终通过多目标遗传算法进行进一步总结：遗传算法在多目标优化圈中为是最优的解决方法，而且它还将决策者纳入在问题讨论范围内。适合度分配方法通过遗传算法和外部决策者的相互作用以找到问题最优的解决方案，并且详细解释遗传算法和外部决策者如何通过相互作用以得出最终结果。 1.简介 求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息，先将多目标问题标量化处理为单目标问题后再以遗传算法求解，仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标非劣解的解集的研究尚不多见。 本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点，设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法，并通过在个体适应度定标中引入该方法，控制优解替换和保持种群多样性，采用自适应变化的方式确定交叉和变异概率，设计了多目标遗传算法(Multi Objective Genetic Algorithm, MOGA)。该算法通过一次计算就可以得到问题的非劣解集， 简化了多目标问题的优化求解步骤。 多目标问题中在没有给出决策偏好信息的前提下，难以直接衡量解的优劣，这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点，我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最 后对非劣解集的逼近。 考虑一个n维的多目标规划问题，且均为目标函数最大化， 其劣解可以定义为： f i (x * )≤f i (x t ) i=1，2，??，n (1) 且式(1)至少对一个i取“＜”。即至少劣于一个可行解的x必为劣解。 对于遗传算法中产生大量的可行解，我们考虑对同一代中的个体基于目标函数相互比较，淘汰掉确定的劣解，并以生成的新解予以替换。经过数量足够大的种群一定次数的进化计算，可以得到一个接近非劣解集前沿面的解集，在一定精度要求下，可以近似的将其作为非劣解集。 个体的适应度计算方法确定后，为保证能得到非劣解集，算法设计中必须处理好以下问题：(1)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解，所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变
. % function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance
TSP问题的遗传算法求解 摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。 关键词：遗传算法、旅行包问题 一、旅行包问题描述： 旅行商问题，即TSP问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。 用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（d ij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1，v2，v3，...，vn}的一个访问顺序为T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且记tn+1= t1，则旅行商问题的数学模型为：min L=Σd(t(i),t(i+1)) （i=1，…，n） 旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。 在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。
第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，…，S n 的物体和容量为C 的背包，此处S 1，S 2，…，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题：输入由C 和两个向量C ＝(S 1，S 2，…，S n )和P ＝(P 1，P 2，…，P n )组成。设X 为一整数集合，即X ＝1，2，3，…，n ，T 为X 的子集，则问题就是找出满足约束条件∑∈≤T i i C X ，而使∑∈T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。
4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模)，T i (1≤i ≤n )＝1表示该物件装入背包，T i ＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将P i ，S i 按P i /S i 值的大小依次排列，即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数：∑==n i i i P T T J 1 )( 约束条件：C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f (T )如下式： f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数，惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值，β为合适的惩罚系数。 4.2 货郎担问题（Traveling Salesman Problem ——TSP ） 在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全（NP-complete ）问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法 就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。
煤矿机械Coal Mine Machinery Vol.30No.12 Dec.2009 第30卷第12期2009年12月 0引言 工程机械中所用电动机的转速较高，为了满足工作机低转速的需要，一般在电动机和工作机之间安装减速器，用来降低电机的转速或增大转矩，减速器是一种机械传动装置，广泛地应用于运输机械、矿山机械和建筑机械等重型机械中。因此，减速器的设计非常重要。 遗传算法（GA）是模拟生物在自然界中优胜劣汰的自然进化过程而形成的一种具有全局范围内优化的启发式搜索算法。这种方法已在很多学科得到广泛的应用，为减速器的优化设计提供有力的保证。因此，本文采用遗传算法对两级齿轮减速器进行优化设计，并通过与惩罚函数法和模拟退火算法等优化方法计算结果进行比较，来探讨适合于减速器的优化设计方法。 1建立数学模型 两级齿轮传动减速器结构如图1所示。该减速器的总中心距 a∑＝［m n1z1（1＋i1）+m n2z3（1＋i2）］/2cosβ（1）式中m n1、m n2—— —高速级与低速级的齿轮法面模 数； i1、i2—— —高速级与低速级传动比； z1、z3—— —高速级与低速级的小齿轮齿数： β—— —2组齿轮组的螺旋角。 1.1设计变量的确定 在进行两级齿轮传动减速器设计时，一般选择齿轮传动独立的基本参数或性能参数，如齿轮的齿数、模数、传动比、螺旋角等为设计变量。两级齿轮传动由4个齿轮组成，分别用z1、z2、z3、z4表示，高速级的传动比由i1表示，低速级传动比由i2表示，两组齿轮组的法面模数分别由m n1和m n2表示，2组齿轮的螺旋角用β表示，由于两级齿轮传动减速器的总传动比i0，在设计时会给出具体数据，并且满足i0＝i1i2，可以得出i2＝i0/i1，可以确定独立的参数有z1、z3、m n1、m n2、i1和β。因此，可以确定该设计变量X＝［z1，z3，m n1，m n2，i1，β］T=［x1，x2，x3，x4，x5，x6］T。 图1减速器结构简图 1.2目标函数的建立 在对减速器进行优化设计时，首先要确定目标函数。确定目标函数的原则是在满足各种性能要求的前提下，使减速器的体积最小，这样设计的减速器既经济又实用，从而达到了优化的目的。要使减速器的体积最小，必须使减速器的总中心距最小。因此，以减速器的中心距最小建立目标函数为 a∑＝［x3x1（1＋x5）+x4x2(1+i0/x5)］ 6 （2）1.3约束条件的确定 为使两级齿轮传动减速器满足强度、设计变量 基于遗传算法的齿轮减速器优化设计* 吴婷，张礼兵，黄磊 （安徽建筑工业学院机电学院，合肥230601） 摘要：对两级齿轮减速器优化设计进行了分析，建立了其优化设计的数学模型，确定了优化设计的约束条件，采用遗传算法对两级齿轮减速器进行优化设计，并通过实例说明，采用遗传算法对减速器进行优化，可以得到更加优化的设计结果。 关键词：减速器；遗传算法；优化设计 中图分类号：TH132文献标志码：A文章编号：1003－0794（2009）12－0009－03 Gear Reducer Optimal Design Based on Genetic Algorithm WU Ting，ZHANG Li-bing，HUANG Lei （School of Mechanical and Electrical Engineering,Anhui University of Architecture,Hefei230601,China）Abstract:T he optimal design of a gear reducer was analyzed,the mathematic model was established, and the restriction condition was confirmed.Design of the gear reducer was optimized with genetic algorithm and the examples showed that design of the gear reducer based on genetic algorithm can gain more optimized result. Key words:reducer；genetic algorithm；optimal design *安徽省教育厅自然基金项目（2006KJ015C） 轴1轴2轴3 z1z2 z3z4 9
多目标遗传算法优化 铣削正交试验结果 说明： 1.建立切削力和表面粗糙度模型 如： 3.190.08360.8250.5640.45410c e p z F v f a a -=（1） a R =此模型你们来拟合（上面有实验数据，剩下的两个方程已经是我帮你们拟合好的了）（2） R a =10?0.92146v c 0.14365f z 0.16065a e 0.047691a p 0.38457 10002/c z p e Q v f a a D π=-????（3） 变量约束范围：401000.020.080.25 1.0210c z e p v f a a ≤≤??≤≤??≤≤? ?≤≤? 公式（1）和（2）值越小越好，公式（3）值越大越好。π=3.14 D=8 2.请将多目标优化操作过程录像（同时考虑三个方程，优化出最优的自变量数值），方便我后续进行修改；将能保存的所有图片及源文件发给我；将最优解多组发给我，类似于下图（黄色部分为达到的要求）
遗传算法的结果:
程序如下: clear; clc; % 遗传算法直接求解多目标优化 D=8; % Function handle to the fitness function F=@(X)[10^(3.19)*(X(1).^(-0.0836)).*(X(2).^0.825).*(X(3).^0.564).*(X(4).^0. 454)]; Ra=@(X)[10^(-0.92146)*(X(1).^0.14365).*(X(2).^0.16065).*(X(3).^0.047691).*( X(4).^0.38457)]; Q=@(X)[-1000*2*X(1).*X(2).*X(3).*X(4)/(pi*D)];
收稿日期:20001225 综 述 遗传算法电机优化设计简介 李鲲鹏,胡虔生 (东南大学,南京210096) B rief I ntroduction of Motor Optimizing Design B ased on G enetic Algorithms L I Kun -peng ,HU Qian -sheng (S outheast University ,Nanjing 210096,China ) 摘 要:介绍了遗传算法的基本思想及其特点,实现了基于遗传算法的电机优化设计,讨论了保证其全局收敛性的方法,最后给出了基于遗传算法的电机优化设计实例。 关键词:电机优化设计;遗传算法;全局收敛性中图分类号:T M302 文献标识码:A 文章编号:1004-7018(2001)04-0032-02 Abstract :In this paper ,the essence and a pplications of genetic alg orithms are friendly introduced.Based on com paris ons between ge 2netic alg orithms and conventional methods ,the a pplication of genetic alg orithm to motor design is im plemented.In this process ,the meth 2ods to improve the global convergence of genetic alg orithm are dis 2cussed.Finally ,the results of the optimization of three -phase electri 2cal machine design based on genetic alg orithms are presented. K eyw ords :motor optimal design ;genetic alg orithms (G A );glob 2al convergence 1遗传算法的基本思想及其特点 遗传算法是模拟生物进化机制的一种现代优化计算方法。其基本思想是:首先通过编码操作将问题空间映射到编码空间(如[0,1]L ),然后在编码空间内进行选择、交叉、变异三种遗传操作及其循环迭代操作,模拟生物遗传进化机制,搜索编码空间的最优解,最后逆映射到原问题空间,从而得到原问题的最优解。选择操作模拟了个体之间和个体与环境之间的生存竞争,优良个体有更多的生存繁殖机会。在这种选择压力作用下,个体之间通过交叉、变异遗传操作进行基因重组,期望得到更优秀的后代个体,在这场竞争中胜出。选择、交叉、变异遗传操作都是以概率值进行的。这些概率值与当时生存环境和个体适应能力密切相关。从这里可以看出遗传算法是一种随机性搜索算法,但是它不同于传统的随机搜索算法。遗传算法通过交叉算子(Cross over operator )和变异算子(Mutation Operator )的协同作用确保状态空间([0,1]L )各点的概 率可达性,在选择算子(Selection Operator )的作用下保证迭代进程的方向性。 2电机优化设计的数学模型和一般优化方法 电机优化设计的一般数学模型: min/max :f (x ) g i (X )≤0,i =1,2,3,…,m X j ∈[a j ,b j ],j =1,2,3,…,n (1) 其中:X =[x 1,x 2,x 3,…,x n ]为设计参量即电磁系统的参数,如冲片尺寸、绕组参量等。g i (X )(i =1,2,3,…,m )为约束条件,如性能约束和一般约束。由于目标函数f (X )和约束条件g i (X )都是X 的高度非线性函数,因此电机优化设计问题是求解约束非线性最优化问题。 由于电机设计的目标函数f (X )不是一个单纯的数学表达式,而是一段电机设计分析计算程序,在计算目标函数值的同时还计算各个性能指标值,即约束条件函数值,因此利用目标函数的梯度确定搜索方向的优化方法在电机优化设计中是相当繁琐,直接利用目标函数值的优化方法在电机优化设计中具有优势,遗传算法通过选择、交叉、变异算子的协同作用,既保证了搜索的方向性,又满足了状态空间各点的概率可达性,具有概率意义下的全局收敛性。遗传算法继承了传统确定性算法和一般随机算法的优点,是一种新的启发式随机搜索算法。 遗传算法对约束的处理有两种思路:增加修正算子将约束条件反映在遗传算子的设计中;利用惩罚函数法将有约束优化问题转化为无约束优化问题。在电机优化设计中常采取后者。基于遗传算法的惩罚函数主要分为静态惩罚函数、动态惩罚函数和自适应惩罚函数三种[4]。自适应惩罚函数法效果较好,但较复杂; 静态、动态惩罚函数相对较简单,经常使用。约束条件 23 微特电机 2001年第4期
·制造业信息化· 图1吊车结构系统有限元模型 Fig.1The finite element model of a fixed crane Based on Genetic Algorithms and Artificial Neural Network Algorithms to Optimize the Structure Design and Implementation of Crane XUE Jia-Hai ，YU Xiao-Mo ，QING Ai-Ling ，ZHOU Wen-Jing ，YE Jun-Ke （College of Mechanical Engineering,Guangxi University,Nanning Guangxi 530004,China ） Abstract:This paper by using the finite element method,orthogonal test method,BP neural network and genetic algorithm to optimization of crane structure system.At last ，the neural network model will be optimized through the generic algorithm and the optimal parameters of the structure dynamic behavior will be obtained ． Key words ：finite element ；orthogonal experimental method ；BP-neural network ；genetic algorithm 0引言 随着吊车向大型化方向发展，结构在动载荷作用下的振动问题变得日益突出。因此，进行基于动态特性的优化设计，使产品在设计阶段就可以预测其动态特性，可有效减小系统的振动，提高整机工作性能。结构动力学建模方法主要有有限元法、试验模态法、混合建模法及基于人工神经网络的建模方法。基于人工神经网络的动态优化设计建模方法，是利用多层人工神经网络极强的非线性映射功能，来描述和处理动态系统中设计变量及其动态参数之间的关系。人工神经网络模型一旦建立，可取代有限元模型进行结构动态特性重分析，其分 析过程简单而直接，且远比有限元模型计算速度快，尤其适用于工程技术人员使用。由于吊车结构系统的动态特性很难用设计变量显式表达，因此用遗传算法对建立的神经网络模型寻优，计算出可行区域内动态特性最优时的设计变量及目标值。 1吊车结构系统动态特性分析 图1所示为某厂生产的固定式吊车的有限元模型。主要参数为：塔身高48．5m ，起重臂长70m ，最大起重力矩4400kN ·m 。吊车结构的弦杆、腹杆、钢丝绳及集中质量分别以空间梁单元、杆单元、弹簧单元及质量单元模拟。表1所示 为按最大起重力矩工况计算的系统前8阶固有频率。修稿日期：2012－12－21 作者简介：薛加海（1986-），男，云南彝族人，在读硕士研究生。主要研究方向：制造业管理信息化研究；于晓默（1982-），男，蒙古族人，在读博士研究生。主要研究方向：制造业管理信息化研究。 摘要：论文综合利用BP 神经网络、遗传算法有限元法以及正交试验法对吊车结构系统进行优化研究。利 用遗传算法和BP 神经网络建立复杂结构系统动态优化的计算模型，该模型可代替系统原来的有限元模型。首先对吊车起重机结构系统进行模态分析及谐响应动力学分析，找出对结构动态特性影响最大的模态频率，再利用灵敏度分析，确定对动态特性较敏感的设计变量作为神经网络的输入变量，并利用正交试验法确定神经网络训练样本，用有限元模型计算出样本点数据，建立反映结构振动特性的人工神经网络模型，最后利用遗传算法对所建立的神经网络模型寻优，得到使结构动态性能最优的设计参数。 关键词：有限元法；正交试验法；BP 神经网络；遗传算法中图分类号：TP18 文献标识码：A doi:10.3969/j.issn.1002-6673.2013.01.037 文章编号：1002－6673（2013）01－093－03 基于遗传算法和神经网络算法的吊车结构优化设计与实现 薛加海，于晓默，秦爱玲，周文景，叶俊科 （广西大学机械工程学院，广西南宁530004） 机电产品开发与创新 Development ＆Innovation of M achinery ＆E lectrical P roducts Vol．26,No．1Jan ．,2013第26卷第1期2013年1月 93
收稿日期:2002-11-13;修订日期:2003-02-12 作者简介:郭海丁(1958-) 男 山东潍坊人 南京航空航天大学能源与动力学院副教授 博士 主要从事工程结构强度~断裂~疲 劳损伤及结构优化设计方法等研究. 第18卷第2期2003年4月 航空动力学报 Journal of Aerospace Power Vol.18No.2 E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E E Apr.2003 文章编号:1000-8055(2003)02-0216-05 基于BP 神经网络和遗传算法 的结构优化设计 郭海丁1 路志峰2 (1.南京航空航天大学能源与动力学院 江苏南京210016; 2.北京运载火箭技术研究院 北京100076) 摘要:现代航空发动机不断追求提高推重比 优化其零部件的结构设计日益重要 传统结构优化方法耗时多且不易掌握 针对这一问题 本文提出了将BP 神经网络和遗传算法相结合用于结构优化设计的方法 并编制了相应的计算程序 实现了一个含9个设计变量的发动机盘模型的结构优化计算 计算证明 与传统结构优化方法相比 此方法计算速度快~精度良好 关 键 词:航空~航天推进系统;结构优化;神经网络;遗传算法;航空发动机 中图分类号:V 231 文献标识码:A Structure Design Optimization Based on BP -Neural Networks and Genetic Algorithms GUO -ai -ding 1 LU Zhi -feng 2 (1.Nanjing University of Aeronautics and Astronautics Nanjing 210016 China ; 2.Beijing institute of Astronautics Beijing 100076 China ) Abstract :Owing to the increasing demand for raising the thrust -weight ratio of modern aero -engine it is very important to optimize the structures of the components .Traditional optimization methods of structure design are time -consuming and hard to be put into practice .So in this paper a new method of structure design optimization is induced to which both BP neural networks and genetic algorithms (in short :BPN -GA )are applied .A program which contains 9variables is designed for the structure optimization of a disk model with the BPN -GA method which proves that it has better calculating rate and precision than those with traditional optimization methods . Key words :aerospace propulsion ;structure optimization ;neural network ; genetic algorithms ;aero -engine 1 引言 在航空~航天等领域 结构优化设计技术正在得到越来越广泛的应用 结构优化设计逐步进入工程实用阶段!1"3# 但从工程应用角度来看 结构优化设计方法的推广仍存不少障碍 主要表现为: (1)优化中靠经验调整的参数较多 掌握困难;(2)优化计算效率较低 应用现有的结构优化算法进
一种在复杂网络中发现社区的多目标遗传算法 Clara Pizzuti 摘要——本文提出了一种揭示复杂网络社区结构的多目标遗传算法。该算法优化了两个目标函数，这些函数能够识别出组内节点密集连接，而组间连接稀疏。该方法能产生一系列不同等级的网络社区，其中解的等级越高，由更多的社区组成，被包含在社区较少的解中。社区的数量是通过目标函数更佳的折衷值自动确定的。对合成和真实网络的实验，结果表明算法成功地检测到了网络结构，并且能与最先进的方法相比较。 关键词：复杂网络，多目标聚类，多目标进化算法 1、简介 复杂网络构成了表示组成许多真实世界系统的对象之间关系的有效形式。协作网络、因特网、万维网、生物网络、通信传输网络，社交网络只是一些例子。将网络建模为图，节点代表个体，边代表这些个体之间的联系。 复杂网络研究中的一个重要问题是社区结构[25]的检测，也被称作为聚类[21]，即将一个网络划分为节点组，称作社区或簇或模块，组内连接紧密，组间连接稀疏。这个问题，如[21]指出，只有在建模网络的图是稀疏的时候才有意义，即边的数量远低于可能的边数，否则就类似于数据簇[31]。图的聚类不同于数据聚类，因为图中的簇是基于边的密度，而在数据聚类中，它们是与距离或相似度量紧密相关的组点。然而，网络中社区的概念并未严格定义，因为它的定义受应用领域的影响。因此，直观的理解是同一社区内部边的数量应该远多于连接图中剩余节点的边的数量，这构成了社区定义的一般建议。这个直观定义追求两个不同的目标：最大化内部连接和最小化外部连接。 多目标优化是一种解决问题的技术，当多个相互冲突的目标被优化时，成功地找到一组解。通过利用帕累托最优理论[15]获得这些解，构成了尽可能满足所有目标的全局最优解。解决多目标优化问题的进化算法取得成功，是因为它们基于种群的特性，同时产生多个最优解和一个帕累托前沿[5]的优良近似。 因此，社区检测能够被表述为多目标优化问题，并且帕累托最优性的框架可以提供一组解对应于目标之间的最佳妥协以达到最优化。事实上，在上述两个目标之间有一个折衷，因为当整个网络社区结构的外部连接数量为空时，那它就是最小的，然而簇密度不够高。 在过去的几年里，已经提出了许多方法采用多目标技术进行数据聚类。这些方法大部分在度量空间[14], [17],[18], [28], [38], [39], [49], [51]聚集目标，虽然[8]中给出了分割图的一个方法，并且在[12]中描述了网络用户会议的一个图聚类算法。 本文中，一个多目标方法，名为用于网络的多目标遗传算法(MOGA-Net)，通过利用提出的遗传算法发现网络中的社区。该方法优化了[32]和[44]中介绍的两个目标函数，它们已被证实在检测复杂网络中模块的有效性。第一个目标函数利用了community score的概念来衡量对一个网络进行社区划分的质量。community score值越高，聚类密度越高。第二个目标函数定义了模块中节点fitness的概念，并且反复迭代找到节点fitness总和最大的模块，以下将这个目标函数称为community fitness。当总和达到最大时，外部连接是最小。两个目标函数都有一个正实数参数控制社区的规模。参数值越大，找到的社区规模越小。MOGA-Net利用这两个函数的优点，通过有选择地探索搜寻空间获得网络中存在的社区，而不需要提前知道确切的社区数目。这个数目是通过两个目标之间的最佳折衷自动确定的。 多目标方法的一个有趣结果是它提供的不是一个单独的网络划分，而是一组解。这些解中的每一个都对应两个目标之间不同的折衷，并对应多种网络划分方式，即由许多不同簇组成。对合成网络和真实网络的实验表明，这一系列帕累托最优解揭示了网络的分层结构，其中簇的数目较多的解包含在社区数目较少的解中。多目标方法的这个特性提供了一个很好的机会分析不同层级
% function nsga_2(pro) %% Main Function % Main program to run the NSGA-II MOEA. % Read the corresponding documentation to learn more about multiobjective % optimization using evolutionary algorithms. % initialize_variables has two arguments; First being the population size % and the second the problem number. '1' corresponds to MOP1 and '2' % corresponds to MOP2. %inp_para_definition=input_parameters_definition; %% Initialize the variables % Declare the variables and initialize their values % pop - population % gen - generations % pro - problem number %clear;clc;tic; pop = 100; % 每一代的种群数 gen = 100; % 总共的代数 pro = 2; % 问题选择1或者2，见switch switch pro case 1 % M is the number of objectives. M = 2; % V is the number of decision variables. In this case it is % difficult to visualize the decision variables space while the % objective space is just two dimensional. V = 6; case 2 M = 3; V = 12; case 3 % case 1和case 2 用来对整个算法进行常规验证，作为调试之用；case 3 为本工程所需； M = 2; %(output parameters 个数) V = 8; %(input parameters 个数) K = 10; end % Initialize the population chromosome = initialize_variables(pop,pro); %% Sort the initialized population % Sort the population using non-domination-sort. This returns two columns % for each individual which are the rank and the crowding distance % corresponding to their position in the front they belong. 真是牛X了。 chromosome = non_domination_sort_mod(chromosome,pro); %% Start the evolution process