基于免疫的并行单亲遗传算法研究.doc

第8期行小帅等：基于免疫的并行单亲遗传算法研究105基于免疫的并行单亲遗传算法研究行小帅，霍冰鹏（山西师范大学 物理与信息工程学院，山西 临汾 041004）摘要：在分析了单亲遗传算法的优越性与存在不足的基础上，借鉴生物免疫概念与理论并结合并行计算的思想，提出了一种新的遗传算法基于免疫的并行单亲遗传算法。理论分析和仿真结果表明,该算法不仅能够有效地保持群体多样性，而且减轻了遗传算法后期的波动现象，同时收敛速度有明显的提高。关键词：并行；单亲遗传算法；免疫算法；非均匀变异算子；免疫算子中图分类号：TP18，PT13 文献标识码：B 文章编号：1000-436X(2007)08-0099-06Research on parallel partheno genetic algorithm based onthe immune programming XING Xiao-shuai, HUO Bing-peng(College of Physics and Information Engineering, Shanxi Teachers University, Linfen 041004,China)Abstract: A novel algorithm parallel partheno genetic algorithm based on the immune programming (IPPPGA) was proposed, the algorithm analogies to the concept and theory of immunity in biotic science and unifies the parallel computation thought, after analyzing the advantages and disadvantages of the partheno genetic algorithm. The theory analysis and experimental results show that the algorithm not only effectively keeps population diversity, but also alleviates the undulate phenomenon in evolutionary latter stages, meanwhile increases the convergent speed and computational efficiency greatly. Key words: parallel; partheno genetic algorithm; immune programming; nonuniform mutation operator; immune operator1 引言收稿日期：2006-12-12；修回日期：2007-05-20基金项目：山西省青年科技研究基金资助项目（20031008）Foundation Item: The Shanxi Young Science and Technology Research Fund Scheme of China (20031008)单亲遗传算法1,2(PGA, partheno genetic algorithm)是一种对样本空间的样本分别进行基因换位、基因移位、基因倒位、变位等单亲遗传操作，实现解空间全局搜索的算法。与传统的遗传算法相比，PGA可以更好地保持样本地稳定性，特别适合于求解组合优化以及多峰函数的优化问题3,4。从理论上分析，在PGA的循环迭代过程中保留了上一代最佳个体的前提下，PGA是全局收敛的5。通常PGA操作算子如换位、移位等为了保证遗传算子的全局搜索能力，都是基于一定的概率操作。但是在定向搜索时，这样操作往往效率较低6。文献7提出的单亲遗传算法是基于实数编码，它使用选择算子和变异算子，从而保证了个体间隔离，彼此互不交换信息，能够有效地保持群体的多样性，在一定程度上减少了早熟现象，收敛速度也较快，但是在进化过程中利用系统信息不够，进化后期易出现波动现象，因此不能保证其以最大概率收敛到全局最优解。免疫进化算法（IEA, immune evolutionary algorithm）8是一种有效的全局寻优算法，它借鉴生命科学中的免疫概念和理论，在保留原算法优良特性的前提下，力图有目地、有选择地利用待求问题中一些特征或知识来抑制其优化过程中出现的退化现象。免疫进化算法的核心是在合理抽取疫苗的基础上，通过接种疫苗和免疫选择2个步骤完成的。前者是为了提高个体的适应度，后者是为了防止群体的退化。因此免疫算法能够提高个体的适应度和防止群体的退化现象，从而提高了收敛速度并且减轻了原有进化算法后期的波动现象。本文将免疫算法和单亲遗传算法的优点相结合，并集成了并行计算9,10中的分而治之策略的思想，提出了一种新的遗传算法基于免疫的并行单亲遗传算法(IPPPGA, parallel partheno genetic algorithm based on the immune programming)。在单亲遗传算法的基础上，利用实数编码，非均匀变异算子，接种疫苗和免疫选择。在算法的前期能均匀地搜索解空间，后期能对局部进行越来越细微的搜索，使得个体可以进入最优点的吸引域，并且后期在一定选择条件下逐渐使群体集中到最优点的吸引域内，从而防止了算法的过早收敛。利用并行的处理方式，把多峰的函数转换为单峰的函数，利用接种疫苗和免疫选择，得以把最优的个体的信息保留到下一代，防止盲目的搜索，从而提高搜索速度。防止局部收敛和提高收敛速度本来就是一对矛盾，本文在权衡两者的前提条件下，合理的构造算子和参数，平衡两者的关系，可以很好的防止过早的收敛，并提高了收敛的速度。2算子描述及其分析 2.1非均匀变异算子(nonuniform mutation)非均匀变异算子8可描述如下：在对一个个体向的非均匀变异操作时，若变异处的基因值取值范围为，新的基因值由式(1)确定(1)其中，（y代表和表示0, y范围内符合非均匀分布的一个随机数，要求随着进化代数t的增加，接近于0的概率也逐渐增加。例如，可按式(2)定义(2)其中，r为0, 1范围内符合均匀概率分布的一个随机数，T是最大进化代数，b是一个系统参数，它决定了随机扰动对进化代数t的依赖程度2.2免疫算子分析免疫算子8这一概念是借鉴生命科学的启发而提出的。它是由疫苗抽取、接种疫苗和免疫选择3个步骤完成的。疫苗提取是为了有效地保持疫苗提取最优，以便遗传算子在接种疫苗时能够充分地发挥作用并保证全局最优；接种疫苗是为了提高个体的适应度；免疫选择则是为了防止群体的退化。具体描述如下。2.2.1疫苗抽取免疫疫苗的抽取通常有2种,一种视具体分析待求问题，搜集特征信息，进而制作免疫疫苗；另一种是自适应方法，即在群体进化过程中从其每代最佳的基因中抽取有效信息，从而制作疫苗。前者由于以下2个原因而受到限制，一是对待求问题有时难以形成较为成熟的先验知识，无法从分析问题的过程中抽取出合适的特征信息，因此得不到有效的免疫疫苗。二是提取疫苗的工作代价太大，超出了其在寻找全局最优解过程中的比例，所以在本文算法中采用自适应抽取疫苗方法。其过程是设个体为,通过对前K1代保留下来的最优个体群和当前代的最优个体群进行分析，抽取该最优个体的x1和x2基因位的共同特点和有效信息作为疫苗。机体免疫细胞对感染的不同微生物种类的反应是不同的。通常病毒感染时，白细胞计数显示淋巴细胞的比例较高，而细菌感染则中性粒细胞比较高，这意味者免疫系统产生的抗体具有很强的针对性，这给我们的提示是适应度较高的抗体含有解决问题的特征信息。因为IPPPGA每代都保留最佳个体，所以在抽取每一代最优个体基因疫苗时，采用疫苗更新，因为抽取疫苗的优劣，生成抗体的好坏，会严重影响到免疫算子中接种疫苗作用的发挥，但与算法的收敛性无关。从概率上来讲，一方面，最优个体和全局最优解之间的结合概率要大于群体中其他个体和全局最优解之间的结合概率，另一方面，最优个体有较大结合概率的个体也应有较高适应度。而IPPPGA算法保留了历史最佳个体在每一代淘汰最差个体，用保留的历史最佳个体替换掉当前代最差个体，这能够有效地保持疫苗的抽取最优，以便使遗传算子在接种疫苗时能够充分地发挥作用并保证全局收敛。2.2.2接种疫苗 假设个体为，给其接种疫苗是指按照先验知识强制性修改的某些基因位上的基因，使所得个体有一较大概率具有更高的适应度值。该操作应满足下述条件：如果个体已是最优个体，即以概率1转移为；如果是最差个体，即的每一个基因位都与最优个体不相同，则个体以概率0转移为。设第代的群体为，对群体进行接种疫苗，是按照一定比例随机抽取个个体而进行的一种操作。2.2.3免疫选择 即对接种了疫苗的个体进行检测。如果其适应度不如父代，说明在遗传过程中出现了严重的退化现象，这时该个体将被父代中所对应的个体所替代。如果子代适应度优于父代，则其子代将代替父代进入下一代种群。免疫选择对算法收敛性有积极作用，消除其负面影响，具有较强的顽健性。3算法的描述和收敛性分析3.1算法的执行步骤Step1(实数编码，产生初始化种群)把解空间分解为K=mm块，各子种群随机产生，一般种群个体取20100，本文中=20，把初始化变量基于实数编码11映射到0,1，记为population(k),实数编码可以大大简化计算，同时使gen=1(初始代数)。Step2(解码)对于K个子空间，进行独立的解码运算，用式（2）进行解码，其中a(j)为子解空间的最小值，b (j)为子解空间的最大值，u(j)为子解空间的个体,解码后得到新的种群，记为population_ decoded (k)。(3)Step3(求解目标函数值)对于K个子空间，进行独立的求解目标函数值运算，把解码后的值population_decoded (k)代入待求目标函数(式(4)。(4)Step4(寻找最优个体)对于K个子空间，寻找各子种群的最优个体,得到各子种群的最优个体best_individual (k)。Step5(提取疫苗)对于K个子空间，在各子空间基于最优个体best_individual (k)抽取疫苗vaccine(k)。Step6(非均匀变异)对于K个子空间，对population(k)进行非均匀变异按式(1)进行，得到种群population_ mutation(k)。Step7(接种疫苗)对于K个子空间，用vaccine(k)分别对population_mutation(k)进行接种疫苗，生成下一代population(k)。Step8(更新种群)对于K个子空间，分别对population(k)进行操作，用最优个体替代最差个体，得到新的种群population(k)。Step9(流向判断)如果符合判断条件，则结束程序，否则跳转到Step2，继续执行直到符合程序的结束条件。3.2算法的伪代码描述Procedure PGAbegainInitialize population(k) ；/ 种群初始化，划分为k = mm 块gen = 0；/ 代数初值while(genmax_gen) do/ max_gen 为最大进化代数for i = 1 to k do/ k = mm, k为种群分组大小population_decoded (i) = decode（population(i)）；/ 解码; end forfor i = 1 to k doobject_function(i) = evalution_function (population_decoded(i) ；/ 求解目标函数值end for for i = 1 to k dobest_individual (i)= get_best_individual (population(i), object_function(i)；/ 取得各种群的最优个体end for for i = 1 to k doVaccine(i) = get_vaccine(best_individual (i)；/ 取得疫苗end forfor i = 1 to k dopopulation_mutation (i) = multiNonUnifMutation(population(i)；/ 非均匀变异end forfor i = 1 to k dopopulation(i) = inject_vaccine(population_ mutation (i), Vaccine(i)；/ 注入疫苗，更新下一代end forfor i = 1 to k dopopulation(i) = Substitute（population(i)）；/ 最优个体替换最差个体end forgen = gen +1；/代数加1end while max_num = max_function(population)； / 得到全局最优end 3.3算法的收敛性分析免疫算法的状态转移情况可用如下马尔可夫链来表述设为搜索空间，即所有个体的空间，并定义若,则。将规模为N 的群体认为是状态空间中的一个点,其每个坐标分别是中的个体。用表示中状态的数量,用表示是中的某一状态,用表示和分别作为的子集时的包含关系。用表示随机变量V在第K代时处于状态Si。设是上的适应度函数,令(5)则定义算法的收敛性如下：定义1如果对于任意的初始分布均有(6)则称免疫规划算法收敛.该定义表明：算法收敛是指当算法迭代到足够多的次数以后,群体中包含全局最佳个体的概率接近于1。这种定义即为通常所说的概率1收敛。免疫规划算法是以概率1收敛的，在文献12,13中已经证明它是以概率1收敛的。4算法的实例分析对于本算法，本文取Schaffer测试函数max(F1) = 1(7)取种群个体为20，迭代次数为200，非均匀变异算子中的参数b为2，求解精度为1012时，运行算法结果如以图1所示。图1是Schaffer函数的三维立体图，它再现了多峰函数的特性，能够从图中看出全局极大峰值和无穷多次全局最优点。图2为25个子种群收敛后在Schaffer函数的立体图中的位置。图1Schaffer函数的三维立体图图2种群收敛后在立体图中的位置图3是根据并行计算中的分而治之的思想，将种群分割成为55块后，每块初始化随机产生的20个种群个体。图4为55个独立的种群经（每个群体大小为20）过200代的独立进化后，分别收敛于各个区域的极大值点，图5为图4的中心区域的放大图，即Schaffer函数最优解。图3种群初始化图4种群收敛图5全局最优的收敛区域为图4的中心区图6为55个独立的种群（每个群体大小为20）经过50代的并行收敛结果，图7为55个独立的种群（每个群体大小为20）经过50代的并行收敛结果，图中横轴为进化代数，纵轴表示适应度（即目标函数值），由于图6和图7的纵坐标采取不同的精度，在此出现了看似图7有较大的振荡，在本算法中应为采用了非均匀变异算子（伴随代数而变化），此算子伴随代数的增大而搜索空间变小，在前期可以搜索较大的空间，表现出大的振荡，在后期搜索空间逐渐变小，可以在最优解的周围搜索，进而在最后达到收敛。图6和图7可以看出本算法可以很快的收敛并找到最优解。表1运行代数以及最优解最优解第1次第2次第3次第4次第5次50代100代200代0.999 999 998 669 770.999 999 999 989 400.999 999 999 999 820.999 999 948 280 440.999 999 999 626 200.999 999 999 999 720.999 999 998 543 850.999 999 999 922 060.999 999 999 999 980.999 999 547 340 130.999 999 999 994 730.999 999 999 999 950.999 999 911 611 520.999 999 999 932 510.999 999 999 999 85图8为25个独立的种群收敛过程（共25条曲线），各条曲线都收敛于各自空间的最优点。图7为图8的每代的最优点的集合（即最高点的集合）。图6多种群全局最优收敛过程(50代)图7多种群全局最优并行收敛过程(200代)图825个独立种群并行收敛过程(200代)由表1可以看出本算法随进化代数的增加，求解的精度在不断的提高，在运行50代时可以精确到105,在运行到100代时，可以精确到109,在运行到200代时可以精确到1012,如果运行更多代数，将可以达到理想的精度要求。由表2可以看出基于免疫的并行单亲遗传算法相对于PGA算法有更高的精度和更快的收敛速度。各种遗传算法对于参数是很敏感的，合理的选择参数提高收敛速度和防止局部收敛是很重要的，对于本算法，每个分割的种群大小2040，种群过大收敛速度会大大降低，单亲遗传算法的进化主要靠非均匀变异，变异概率选0.5比较合适，过大会局部收敛，过小收敛速度过慢，疫苗的注入选择0.2，过大使得种群内部个体之间有太多的相似性，破坏种群的多样性，不利于进化，过小免疫所取得的进化会在变异中稀释掉。表2IPPPGA与PGA算法性能比较数值种群大小代数精度F(x1,x2)IPPPGAPGA2020200600101210100.999 999 999 9990.999 999 999 95结束语基于免疫的并行单亲遗传算法是在单亲遗传算法中有机的集成了免疫进化的机理和并行计算的思想。理论分析和试验表明，本文提出的新算法能有效地防止早熟现象，提高了算法的性能。由于种群之间被隔离保护，形成了并行种群独立的演化过程，并且在各种群的演化过程种，使用了非均匀变异算子，可以充分的分散探测，发现全局最优所在区域，保持了种群的多样性，而且运用了免疫算子，通过对疫苗的提取和免疫，大大加快了收敛速度，提高了计算效率同时在防止遗传算法后期的退化和波动现象有了提高。算例结果表明，该算法是可行的和有效的，其性能要优于并行遗传算法和单亲遗传算法。赖于问题的具体研究领域，可望推广于求解其他复杂优化问题。参考文献：1AMARI S I, CARDOSO J F. Blind source separation-semiparametric statical approachJ.IEEE Trans on Signal Processing, 1997,45(11): 2692-2700.2李茂军,罗日成,童调生.单亲遗传算法的遗传算子分析J.系统工程与电子技术, 2001,23(8):84-87.LI M J, LUO R C, TONG T S. Analysis on the genetic operators of partheno-genetic algorithmJ. Systems Engineering and Electronics, 2001, 23(8):84-87.3AHN C W, RAMAKRISHN R S. A genetic algorithm for shortest path routing problem and the sizing of populations J.IEEE Trans on Evolutionary Computation, 2002,6(6): 566 -579.4李茂军, 童调生.用单亲遗传算法求解有序组合优化问题J.系统工程与电子技术, 1998,10:58-61.LI M J, TONG T S. A partheno genetic algorithm solving serial combinatorial optimizationJ. systems Engineering and Electronics, 1998, 10:58-61.5李茂军, 童调生.单亲遗传算法及其全局收敛性分析J.自动化学报, 1999,25(1):68-72.LI M J , TONG T S. A partheno genetic algorithm and analysis on its global convergenceJ. Acta Automatica Sinica, 1999,25(1):68-72.6李勇,曹广益,朱新坚.一种基于单亲遗传算法的Petri网发射路径求解算法J.系统仿真学报,2005,17(1):203-206.LI Y, CAO G Y, ZHU X J. An algorithm for finding firing sequences of petri nets based on partheno-genetic algorithmJ. Acta Simulata Systematica Sinica, 2005,17(1):203-206.7王斌, 李元香, 王治. 一种求解函数优化问题的单亲遗传算法J.计算机科学, 2003,30(4):162-164.WANG B, L I, Y X, WANG Z. A partheno genetic algorithm for traveling salesman problemJ. Computer Science, 2003,30(4):162-164.8JIAO L C, WANG L. A novel genetic algorithm based on immunity J. IEEE Trans on System, Man, and Cybernetics-Part A: Systems and Humans, 2000, 30(5):552-561.9李广强,赵洪伦,靳慧.并行混合免疫遗传算法及其应用J.计算机工程与应用,2005,3:331-333.LI G Q, ZHAO H L, JIN H. A parallel hybrid immu