第２５卷第ｌｌ期 ２０１５年１１月 计算机技术与发展 Ｃ０ＭＰＵＴＥＲ ＴＥＣＨＮＯＬＯＧＹ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ ＶｏｌＪ ２５ Ｎｏ．１１ ＮＯＶ． ２０１５ 新型紧致遗传算法及其性能分析 彭 军，刘 振，徐学文 （海军航空工程学院接改装训练大队，山东烟台２６４００１） 摘要：针对传统紧致遗传算法收敛速度过慢及容易陷入局部极值的情况，对分布估计算法中的紧致遗传算法进行了研 究，提出了一种新型的混合紧致遗传算法，系统地阐述了该算法的流程和进化机制。首先设置主种群和辅种群，通过多种 群并行进化设置来加速收敛速度，并通过多个概率向量来控制算法的进化过程，当满足一定进化条件后，在主种群内进行 免疫接种，以增加优良个体存活的概率。设置主种群和辅种群的自适应模式交流策略，增加种群多样性，避免过早收敛。 对提出的算法在收敛性以及收敛速度上进行了理论分析，证明了算法满足收敛条件，能够确保收敛，并给出了算法的收敛 时间的估计。最后利用基准函数进行了函数仿真分析，结果充分验证了所提算法的正确性。 关键词：紧致遗传算法；概率向量；收敛性；函数仿真 中图分类号：ＴＰ１８ 文献标识码：Ａ 文章编号：１６７３－６２９Ｘ（２０１５）１１－０１２０－０５ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３－６２９Ｘ．２０１５．１１．０２４ Ｎｏｖｅｌ Ｃｏｍｐａｃｔ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｉｔｓ Ｐｅｒｆｏｒｍａｎｃｅ Ａｎａｌｙｓｉｓ ＰＥＮＧ Ｊｕｎ，ＬＩＵ Ｚｈｅｎ，ＸＵ Ｘｕｅ－ｗｅｎ （Ｔｒａｉｎｉｎｇ Ｂｒｉｇａｄｅ ｏｆ Ｅｑｕｉｐｍｅｎｔ Ａｃｃｅｐｔａｎｃｅ ａｎｄ Ｍｏｄｉｉｆｃａｔｉｏｎ，Ｎａｖａｌ Ａｅｒｏｎａｕｔｉｃａｌ ｎｄ ａＡｓ仃ｏｎａｕｔｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｔａｉ ２６４００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｓｌｏｗ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ ａｎｄ ｗｅａｋ ｃｏｎｖｅｒｇｅｎｃｅ ｐｅｒｆｏｒｍａｎｃｅ ｆｏｒ ｔｈｅ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｈｍ，ｔａ ｎｏｖｅｌ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｈｍ ｉｔｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ ｈｒｏｕｇｈ ｒｔｅｓｅａｒｃｈ ｏｆ ｈｅ ｃｏｍｐａｃｔｔ ｇｅｎｅｔｉｃ ｌｇｏｒａｉｔｈｍ ｉｎ ｄｉｓｔｒｉｂｕｔｄ ｅｖａｅｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｐｒｏｃｅ— ｄｕｒｅ ａｎｄ ｅｖ￣ｕｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｉｓ ａｌｓｏ ｇｉｖｅｎ．Ｆｉｒｓｔｌｙ，ｓｅｔｉｎｇ ｕｐ ｐｒｔｉｍａｒｙ ｐｏｐｕｌａｔｉｏｎ ａｎｄ ｓｅｃｏｎｄａｒｙ ｐｏｐｕｌａｔｉｏｎ，ｔｈｅ ａｌｇｏｒｉｔｈｍ Ｃａｎ ａｃｃｅｌｅｒａｔｅ ｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｓｔｅｅｄ ｔｐｈｒｏｕｇｈ ｐａｒａｌｌｅｌ ｅｖｏｌｕｔｉｏｎ ｉｎ ｍｕｌｔｉｐｅ ｐｏｐｕｌａｔｉｏｎ ａｎｄ ｃｏｎｔｒｏｌ ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｐｒｏｃｅｓｓ ｂｙ ｖａｒｉｏｕｓ ｐｒｏｂａｂｉｌｉｔｙ ｖｅｃｔｏｒ．Ｉｎ ｈｅ ｆｔｉｒｓｔ ｐｒｉｍａｒｙ ｐｏｐｕｌａｔｉｏｎ，ｉｍｍｕｎｅ ｖａｃｃｉｎａｔｉｏｎ ｉｓ ｕｓｅｄ ｔｏ ｉｎｃｒｅａｓｅ ｔｈｅ ｐｒｏｂａｂｉｌｉｔｙ ｏｆ ｂｅｔｔｅｒ ｉｎｄｉｖｉｄｕａｌ，ｔｈｅ ｆｉｓｔｒ ｐｒｉｍａｒｙ ａｎｄ ｔｈｅ ｓｅｃｏｎｄ ｐｏｐｕｌａｔｉｏｎ Ｃａｎ ｅｘｃｈａｎｇｅ ｗｉｔｈ ｅａｃｈ ｏｔｈｅｒ ａｄａｐｔｉｖｅｌｙ ｉｎ ｏｒｄｅｒ ｔｏ ｐｒｅｖｅｎｔ ｐｒｅｍａｔｕｒｅ ａｎｄ ｅｎｈａｎｃｅ ｔｈｅ ｄｉｖｅｒｓｉｔｙ．Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ａｎｄ ｃｏｎｖｅｒ－ ｇｅｎｃｅ ｓｐｅｅｄ ｏｆ ｈｅ ａｔｌｇｏｒｉｔｈｍ ｉｓ ａｎａｌｙｚｅｄ ｉｎ ｔｈｅｏｒｙ，ｗｈｉｃｈ ｐｒｏｖｅｓ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ Ｃａｎ ｃｏｎｖｅｒｇｅ，ａｎｄ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｔｉｍｅ ｉｓ ａｌｓｏ ｅｓｔｉ— ｍａｔｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ｃｌａｓｓｉｃ ｆｕｎｃｔｉｏｎ ｐｒｏｖｅ ｔｈｅ ｃｏｒｒｅｃｔｎｅｓｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｐｒｏｂａｂｉｌｉｔｙ ｖｅｃｔｏｒ；ｃｏｎｖｅｒｇｅｎｃｅ；ｆｕｎｃｔｉｏｎ ｓｉｍｕｌａｔｉｏｎ Ｏ 引 言 基本遗传算法本身存在的诸多局限，过早收敛一 直就是困扰遗传算法的一个问题。进化算法成功的关 键是良好的积木块能够不断成长和混合，但当待优化 要，分布估计算法的提出改变了传统进化算法的进化 机制。由于其局部寻优能力的增强，有效地解决了传 统进化算法陷入局部极值的弊端。紧致遗传算法 （Ｃｏｍｐａｃｔ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＣＧＡ）是Ｈａｒｉｋ在伊利诺 问题的良性积木块几乎散布在所有的染色体中时，此 时遗传算法将很难寻找到最优解。因此现在主要集中 于研究基于概率模型的进化算法，试图从优良解的概 遗传算法实验室所做的研究报告中提出的一种分布估 计算法…。在国外已经进行了较为广泛的研究 ｊ， 国内也有一部分人在研究这方面 ，但主要偏重于 应用，对其理论分析及在军事问题中的应用还相对 较少。 率分布中指导下一代个体的产生，紧致遗传算法便是 一种概率模型进化算法。 传统进化算法最大的问题在于收敛速度及寻优能 进化算法需要在进化过程的每一代中存储种群的 力存在一定的瓶颈，不能满足诸多工程应用问题的需 收稿日期：２０１５—０２—０７ 修回日期：２０１５—０５—０７ 信息，用以指导下一步的进化方向。紧致遗传算法则 网络出版时间：２０１５一ｌｌ—ｏ４ 基金项目：国家自然科学基金资助项目（６１１７４０３１，６０６７４０９０） 作者简介：彭军（１９６８一），男，硕士，副教授，研究方向为装备综合保障与仿真技术。 网络出版地址：ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／６１．１４５０．ＴＰ．２０１５１１０４．０９４９．０２２．ｈｔｍｌ 第ｌ１期 彭军等：新型紧致遗传算法及其性能分析 ・１２１・ 利用概率模型有效地减少了系统内存的开销，在每一 代进化过程中产生少量对种群整体信息具有代表性的 个体，来更新概率向量，指导进化的方向，因此对于求 解ＮＰ难问题，具有较高的效率。但紧致遗传算法是 一种低阶概率模型进化算法，在具有存储容量较小及 速度较快等优势的条件下，也势必存在一定的局限性， 因此在国内外也逐步提出了一些紧致遗传算法的改进 版本。 文中在广泛研究国内外文献的基础上，提出一种 新型的自适应交流的紧致遗传算法，并进行了收敛性 分析及函数的仿真分析。 １ ＣＧＡ及其存在的问题 紧致遗传算法将种群的染色体看作概率向量，概 率向量的分量就是基因的取值，在向量中引入竞争机 制，同一位置的基因进行竞争。 初始时设定进化向量为Ｐ＝｛０．５，０．５，…，０．５｝， 然后进行两个个体之间的竞争，获胜的就前进一小步， 否则相应减小。直到Ｐ为全０或１，这时就形成了最 优解。 Ｐ（ｋ＋１）＝Ｐ（ｋ）＋Ｏ／（ （ｋ）一Ｚ（ｋ）） （１） 为了阻止Ｐ 收敛速度过快，一般设０［为１／Ｎ。其 中，Ⅳ为染色体的长度，Ｏｌ为控制步长，决定着概率向 量的更新速度。 文献［７］对线性伪布尔ｎ变量函数进行了严格的 数学分析，给出了所有线性函数的低界和高界；文献 ［８］提出的分级竞争的ＣＧＡ，过大地增加了选择压力， 并且一次产生过多的个体，明显违背了ＣＧＡ的优良本 质；ＣＧＡ作为一种优良分布估计算法的优势就在于其 每次产生的个体较少，因而占据的存储空间较少，其次 执行和计算效率较高；文献［８］提出一种利用紧致进 化机制与量子进化算法相结合的新型进化算法；杨有 龙 在国内较早地对典型紧致遗传算法的进化机制进 行了分析；文献［１０］提出一种基于移动平均的方法进 行概率向量的更新，这就意味着在单位时窗内所产生 的优良个体必须保留起来，因为增加了系统的存储开 销；文献［１１］提出基于精英保留的ＣＧＡ，分别为ＰＥ— ＣＧＡ以及ＮＥ—ＣＧＡ，并得出了一些有益的理论结果， 但也存在一定的问题。提出的ＰＥ—ＣＧＡ虽然加快了 收敛速度，但会在一定程度上导致选择压的增加，从而 使得收敛到局部极值；提出的ＮＥ－ＣＧＡ并没有说明参 数的详细设置，带有一定的主观性。 ２新型紧致遗传算法 针对传统ＣＧＡ存在的问题，文中提出一种伪并行 模式交流ＣＧＡ。设置两个种群同时进化，并在两个种 群之间进行模式的交流，同时自适应地改变控制参数， 从而实现进化的自适应，不至于收敛到局部极值。称 这种ＣＧＡ为新型ＣＧＡ（Ｎｏｖｅｌ ＣＧＡ，ＮＣＧＡ），算法流程 可表示为： （１）初始化。产生两个种群Ｐｏｐ 及Ｐｏｐ ，分别为 主种群和辅种群，三个概率向量为Ｐ 、Ｐ：及Ｐ，； （２）初始时刻，在主种群中产生初始个体，暂定其 为精英个体，然后依据概率向量产生第二个体，让其与 之竞争并更新优良个体，同时更新概率向量，在主种群 中维持一个概率变量Ｐ，，使其存储优良个体中位置为 １的概率。在辅种群的开始阶段，按照传统ＰＥ—ＣＧＡ 的进化策略进行进化； （３）当进化代数达到Ｔ＝０．２ 后，使主种群 中的优良个体ｎ 与依据Ｐ 产生的个体进行接种疫苗， 以一定的概率更改主种群中的优良个体，以增加种群 的多样性。 接种方法为，随机选择根据Ｐ 向量产生的个体中 的某一位或几位，更改主种群的个体，并比较更改前后 的适应度，如果较之前优，则保留，否则遗弃； （４）设置参数 ，ｌ，，其中，／．ｔ＜ ，Ｉ，为保留最优解 的代数。设定参数Ａ用来表示当前最优解保持的代 数，如果连续 代的最优个体都未更新，则在辅种群中 增加控制参数的值，加快概率向量的收敛。与辅种群 进行模式的交流，模式交流比例为： ＝０．１・（１一ｅ－ｔ／ｔｍａｘ） 前期两个种群模式交流比例较低，为了进行全局 搜索，防止陷入局部值，在后期逐步发现极值点以后， 进行较多的优良模式的交流可以有效地发现极值点， 并跳出局部值； （５）判断Ｐ 是否收敛，是则结束，输出结果，否则 继续运行。 设置两个种群，不但能够尽量地增大模式的多样 性，扩大搜索空间，同时也可以有效地跳出局部极值。 可以看到，辅种群中的选择压力较大，因而有利于全局 的大范围搜索，而主种群中，则采用了精确搜索的方 法，利用接种疫苗的方法，精确探索种群内部的良好结 构，并采取优良个体非永久保留的策略，从而更有利于 局部的寻优。 由于采用了具有指导性的疫苗接种策略，从而使 得种群可以具备有效的指导性，依据各个优良的模式 确定新的个体，在保证收敛精度的前提下，加快了收敛 速度。 通过ＮＣＧＡ的进化流程，可以得到其概率向量的 更新过程为： ｐ ＝ ・１２２・ 计算机技术与发展 第２５卷 ｄ ｄ ｄ ｄ ＋ 一 ＜Ａ＜ 且当前位置为１的个体获胜 ＋ 一 旦２ 芒叫２ ％ ＜Ａ＜ 且当前位置为０的个体获胜 ０＜Ａ＜ 且当前位置为１的个体获胜 ０＜Ａ＜ 且当前位置为０的个体获胜 其他 ３ ＮＣＧＡ的收敛性分析 采用多个体的方法，可以有效降低选择的随机性， 在一定的选择压下，保持多样性的同时，有效抑制了漂 移现象。现在分析ＣＧＡ多是基于其概率向量来分析 其收敛性。文中从ＣＧＡ本身的性质出发，ＣＧＡ总是依 据优良个体更新概率向量，再利用更新后的概率向量 产生个体，其种群转移概率依然是一个马尔可夫过程， 此时可以利用标准遗传算法的分析工具，用于分析 ＮＣＧＡ的收敛性 。 定理１：ＮＣＧＡ的概率向量Ｐ （ｋ）构成一个Ｍａｒｋｏｖ 过程。 证明：在［０，１］区间，取１／Ｎ为步长，则Ｐ （ｋ）的状 态有限，又Ｐ （ｋ）的状态仅与其前一时刻的状态有关， 因为Ｐｄ（ｋ＋１）仅依赖于Ｐｄ（ｋ），Ｘ（ｋ＋１）由Ｐｄ（ｋ＋１） 决定，而Ｘ（ｋ）由Ｐ （ｋ）决定，因此Ｘ（ｋ＋１）仅由 Ｘ（ｋ）决定，因此ＮＣＧＡ为Ｍａｒｋｏｖ过程。 ＮＣＧＡ进化示意图见图１。 图１ ＮＣＧＡ进化示意图 对于算法的收敛有很多定义方法 “ ，可以用达 到最优值所需的最小迭代次数作为度量指标，称之为 收敛时间。Ｔ＝ｍｉｎ（ｔ；ｐ（ ｌ ）＝１），这里 ’为全 局最优值， ’为第计 种群，ｐ（ Ｉ ）为在第ｔ代产 生最优值 ’的概率。除了利用收敛时间以外，首达时 间也是一个经常用到的度量方法。首达时间的定义如 下： ＝ｍｉｎ｛ｔ；ｘ ∈ 川｝。其中， ＋。为ｔ＋１代时的 种群。 引理１［１引：首达时间的概率分布满足： ｔ一１ Ｖｔ≥０，Ｐ（ ＝ｔ）＝（１一Ｐ：）Ⅱ（１一Ｐ ） 其中，Ｐ；为第ｔ代发现最优解的概率。 （ ）表示首达时间的期望值，则：Ｐ（Ｔ＞ｃＴｏ）≤ Ｅ（ ）／ｃ ，当Ｅ（Ｔ）≤Ｔｏ时，Ｐ（Ｔ＞ｃＴｏ）≤Ｔｏ／ｃＴｏ＝ １／ｃ，即独立地运行算法ｋ次，至少有一次在ｃＴｏ步之 前找到最优解的概率小于１—１／ｃ。 设定Ｓ （ｉ≤ｎ）为种群的状态，由于ＣＧＡ的基本 性质，当ｉ＜＿『时，．ｓ 中的种群不可能到达Ｓ 中。整个 状态空间为：｛ｓ ，ｓ：，…，ｓ ｝，构成新的马尔可夫链，记： Ｐｆｆ＝ｍｉｎ｛Ｐ（Ｘ，Ｙ）； ∈Ｓｆ，Ｙ∈Ｊｓ，｝ Ｐ（Ｘ，Ｙ）为齐次马尔可夫链｛Ｘ（ｎ）｝的转移概率， 令 ＝１一∑Ｐ ，（ｐ ）构成种群的马尔可夫链，令： ｑ ｐ ＋∑Ｐ ｑＪ＝ｉ＋２ ｌｌ十１＝ｐｆ．ｉ＋１ ｑ ＋ ＝０（２≤ｋ≤ｎ—ｉ），ｑ ＝０（ ＜ｉ） 得到了修正的马尔可夫链的齐次转移矩阵，令 表示从Ｓ 到 ，的首达时间，则可得到ＮＣＧＡ的首达时 间为： Ｅ（ ）≤∑ Ｔｉ ） 由于Ｐ（Ｔｉ＝ ． ）＝ｑｆ．１＋。（１一ｑ ＋ ） ，因此 层（ ）＝∑ｑ ＋ （１一ｑ ＋ ） ・ｒ＝ （一ｑｆ，ｌ＋－）［∑（１一ｑ ＋ ） 】＝ －ｑｉ，ｉ＋１）（ ） １ １ （ ）≤∑ （２ 以上对ＮＣＧＡ进行了初步分析，以下将对其到达 吸收态的速度进行估计。由于Ｐ （ ）为带有两个吸收 壁的马尔可夫过程，故此时可以用ＮＣＧＡ到达吸收态 的收敛概率对其收敛速度进行估计。 定理２：在ＮＣＧＡ中，｛０，１｝是吸收态，Ｓ＝｛０，１｝， 构成一个闭集。 证明：当概率向量Ｐ （ｋ）到达０或１时，对于状态 ０和１来说，Ｐ。。＝Ｐ。 ＝１，故为吸收态，在整个｛０，１｝构 成的状态空间Ｓ中，Ｐ ＝０，Ｊ隹Ｓ不可能超过这个区 间，故构成一个闭集。 定义１：设随机游动｛ ，Ｉｔ≥０）的状态空间为 ｛０，１，…，ｎ｝，且一步转移概率为： ｆ１，ｉ＝ ＝０或ｉ： ＝ １ ． Ｐ，Ｊ＝ 一１ Ｐ＝｛ｐ ）＝｛ｌ ： ＋１ （３） ｒ， ＝ Ｌｏ√＜ ｉ一１或 ＞ｉ 第１１期 彭军等：新型紧致遗传算法及其性能分析 ０；０ ０ ０ ・１２３・ 其中，Ｐ≥０，ｑ≥０，Ｐ＋ｑ＋ｒ＝１。 １ 游动。 ０ 吼 设定种群规模Ｐｏｐ。和Ｐｏｐ：分别为１００，迭代次数 称｛Ｘ ，ｎ≥０｝为带有两个吸收壁０和ｎ的随机 ０ ．．０ 由于引入了自适应机制，从而扩大了搜索的空间， ．＝１００。分别用基本的紧致遗传算法（ＣＧＡ）、文献 ． ～ 一 ～ ［１１］提出的ＮＥ—ＣＧＡ及文中提出的ＮＣＧＡ进行仿真 ．．分析。选取某一次的典型的仿真对比结果如图２ 在未引入自适应机制之前的种群空间为｛０，ａ，２０，…， ０ 所示。 ～ ０ ．．． １｝，ＮＣＧＡ的种群空间为｛０，孚，ａ， ，…，１｝，ＮＣＧＡ 二 二 ～ ０．．． 的随机游走矩阵可以表示为： ‰０ ～． ．． ． ． ｇ ｒ ０ ０ ０ ｏ ０ Ｐ＝ （４） 令Ｑ＝｛ｑ ｝表示矩阵Ｐ不包含第一行及最后一 行，同时也不包含第一列及最后一列的矩阵；／ｄ， 和 。 分别表示从任意状态ｉ∈Ｓ到吸收态０和１的吸收概 率，因此可以得到： ｕ ＝∑ｑｑｕｊｏ， １一ｕ （５） 解方程组可得： ｏ０＝ Ｉ１＝１， １０： ０ｌ＝０，Ｍｎ＝１一 ｉ０ （“古０，“如，…，“ ）＝（Ｊ—Ｑ） （ｐｌｌＩｐ２ 一， ｐ ）１） 其中，Ｊ为单位矩阵。 令Ｃ＝（Ｉ—Ｑ）～，则从某个状态到达吸收态的速 度为： Ｔ＝（ｔ。，ｔ２，…，ｔ２ ） ＝（Ｉ—Ｑ） （１，１，…，１） （６） ４函数仿真分析 为了验证所提出的算法，利用Ｓｃｈａｆｆｅｒ函数及 Ｃａｍｅｌ函数对所提出的新型紧致遗传算法进行仿真 分析。 （１）Ｓｃｈａｆｆｅｒ函数。 厂 —一 （ ）： ： ： 圣 ， ：２，最大值为 １．０＋１０ ・（∑ ） ０．９９４。 （２）Ｃａｍｅｌ函数。 （ ，ｙ）＝（４—２．１ｘ ＋等） ＋ｘｙ＋（一４＋ ４ｙ ）ｙ２，一１００＜ ，Ｙ＜１００，该函数有６个局部极小 点，其中最小值为一１．０３１ ６２８。 １ 迭代次数 （ａ）Ｓｃｈａｆｆｅｒ函数仿真结果图 趔 辐 圈 Ⅱ ｊ卷代次数 （ｂ）Ｃａｍｅｌ函数仿真结果 图２仿真结果 从图２可以看出，利用文中提出的ＮＣＧＡ能有效 提出函数的寻优性能，需要较少的迭代循环次数就能 寻找到最优解附近，同时所寻找的结果也更稳定。同 时也注意到，由于基本ＣＧＡ是一种低阶概率优化算 法，在缺乏有效指导的情形下，寻优结果较差，甚至在 某些情况下无法寻找到最优解。 为了更加充分地进行对比分析，利用三种算法，分 别独立运行二十次，将运行结果的均值和标准差进行 对比分析，其统计结果如表１所示。 表１仿真结果对比表 从统计结果可以看出，文中提出的ＮＣＧＡ在绝大 ・１２４・ 计算机技术与发展 第２５卷 部分性能指标上都占有优势，显示出良好的优越性。 利用ＮＣＧＡ进行函数优化所得到的函数均值，也非常 接近函数的最优值，显示出良好的稳定性。 ［５］ 叶苗，程小辉．改进的紧致遗传算法求解族状旅行商问 题［Ｊ］．微电子学与计算机，２０１３，３０（８）：７—１２． ［６］ 宋波．基于紧致遗传算法的Ｎ次检测测试集压缩［Ｊ］． 牡丹江师范学院学报：自然科学版，２０１２，２０（３）：６－７． ５ 结束语 由于紧致遗传算法进化机制的优越性，已经得到 越来越多的关注，文中在研究国内外紧致遗传算法的 基础上，提出了一种新型的紧致遗传算法，以及该算法 的详细步骤。针对紧致遗传算法收敛性及收敛速度等 方面研究内容较少，文中提出了一些对其收敛性方面 分析的方法。最后利用所提出的新型紧致遗传算法进 ［７］Ｄｒｏｓｔｅ Ｓ．Ａ ｉｒｇｏｏｕｓｒ ａｎａｌｙｓｉｓ ｏｆ ｈｔｅ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏｉｒｔｈｍ ｆｏｒ ｌｉｎｅａｒ ｆｕｎｃｔｉｏｎｓ［Ｊ］．Ｎａｔｕｒａｌ Ｃｏｍｐｕｔｉｎｇ，２００６，５（３）：２５７— ２８３． ［８］刘振，史建国，高晓光．紧致遗传算法及其在武器目标分 配中的应用［Ｊ］．计算机工程与应用，２００８，４４（３Ｏ）：２２９— ２３１． ［９］杨有龙，高晓光．紧致遗传算法的进化机制分析［Ｊ］．控制 理论与应用，２００３，２０（３）：４１５—４１８． ［１０］Ｓｅｏｋ Ｊ Ｈ，Ｌｅｅ Ｊ Ｊ．Ａ ｎｏｖｅｌ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｏｆｆｓｐｒｉｎｇ ｓｕｒｖｉｖａｌ ｅｖｏｌｕｔｉｏｎａｒｙ ｓｔｒａｔｅｇｙ［Ｊ］．Ａｒｔｉｆｉｃｉｌａ Ｌｉｆｅ ａｎｄ Ｒｏｂｏｔｉｃｓ，２００９，１４（４）：４８９－４９３． 行了函数的仿真分析，证明了算法的正确性。 紧致遗传算法作为一种新兴进化算法，还属于单 变量低阶的概率模型进化算法，因此下一步的工作可 考虑与高阶概率模型进化算法进行良好的交互和融 合，提高其全局寻优性。 参考文献： ［１ Ｈａｒｉｋ Ｇ Ｒ，ｅｂｏ ＬＦ Ｇ，Ｇｏｌｄｂｅｒｇ Ｄ Ｅ．Ｔｈｅ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌ— ［１１］Ａｈｎ Ｃ，Ｒａｍａｋｒｉｓｈｎａ Ｒ．Ｅｌｉｔｉｓｍ－ｂａｓｅｄ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏ－ ｉｒｈｔｍｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ， ２００３，７（４）：３６７—３８５． ［１２］张文修，梁怡．遗传算法的数学基础［Ｍ］．西安：西安交 通大学出版社，２００３． ［１３］Ｒａｓｔｅｇａｒ Ｒ，Ｈａｒｉｉｒ Ａ．Ａ ｓｔｅｐ ｏｆｒｗａｒｄ ｉｎ ｓｔｕｄｙｉｎｇ ｈｅｔ ｃｏｍｐａｃｔ ｇｏｒｉｔｈｍ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ， １９９９，３（４）：２８７－２９７． ｇｅｎｅｔｉｃ ａｌｇｏｉｒｔｈｍ［Ｊ］．Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００６，１４ （３）：２７７—２８９． ［２］Ａｍｒ Ｂ，Ｉｂｔｅｈａｌ Ｍ，Ｂａｓｍａ Ｍ，ｅｔ ａ１．Ｓｏｌｖｉｎｇ ｐｒｏｔｅｉｎ ｆｏｌｄｉｎｇ ｐｒｏｂｌｅｍ ｕｓｉｎｇ ｅｌｉｔｉｓｍ－ｂａｓｅｄ ｃｏｍｐａｃｔ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００８，４（７）：５２５－５２９． ［１４］“ｕ Ｚ，Ｈｕ Ｙ Ａ．Ｅｓｔｉｍａｔｉｏｎ ｏｆ ｄｉｓｔｒｉｂｕｔｉｏｎ ｉｍｍｕｎｅ ｇｅｎｅｔｉｃ ａｌｇｏ— ｒｉｔｈｍ ａｎｄ ｉｔｓ ｃｏｎｖｅｒｇｅｎｃｅ ａｎａｌｙｓｉｓ［Ｊ］．ＴＥＬＫＯＭＮＩＫＡ：Ｊｏｕｒ— ｎａｌ ｏｆＥｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｉｒｎｇ，２０１３，１１（１）：１２３－１２９． ［３］ Ｓｏｈｅｉｌ Ｒ，Ｈａｄｉ Ａ，Ｇｕｙ Ｖ．Ａ ｓｉｍｐｌｅ ｒｅａｌ—ｃｏｄｅｄ ｃｏｍｐａｃｔ ｇｅｎｅｔ— ｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ａｎｔｅｎｎａ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ａｓｉａ—Ｐａｃｉｉｆｃ ｍｉｃｒｏｗａｖｅ ｃｏｎｆｅｒｅｎｃｅ．［Ｓ．１．］： ［１５］Ｃｈｅｎ Ｔ ｓ，Ｈｅ Ｊ，Ｓｕｎ Ｇ，ｅｔ ａ１．Ａ ｎｅｗ ａｐｐｒｏａｃｈ ｏｆｒ ａｎａｌｙｚｉｎｇ ａｖ— ｅｒａｇｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｐｏｐｕｌａｔｉｏｎ—－ｂａｓｅｄ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏ— ｒｉｔｈｍｓ ｏｎ ｕｎｉｍｏｄａｌ ｐｒｏｂｌｅｍｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓ— ｔｅｍｓ，Ｍａｎ，Ｃｙｂｅｒｎｅｔｉｃｓ，Ｐａｒｔ Ｂ：Ｃｙｂｅｒｎｅｔｉｃｓ，２００９，３９（５）： ［Ｓ．ｎ．］，２００７． ［４］ 刘振，胡云安，彭军．协同进化扩展紧致量子进化算法 １０９２－ｌ１ｏ６． ［Ｊ］．控制与决策，２０１４，２９（２）：３２０—３２６． （上接第１１９页） ｏｒｒｅｎｔ－ｂａｓｅｄ ｖｉｄｅｏ ｉｆｌｅ ｓｗａｒｍｉｎｇ［Ｊ］．Ｐｅｅｒ—ｔｏ—Ｐｅｅｒ Ｎｅｔｗｏｒ－ ｋｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０，３（３）：２３７－２５３． ［５］ 郑纬民，胡进锋，代亚非，等．对等计算研究概论［Ｊ］．中国 计算机学会通讯，２００５，７（２）：３８—５１． ［６］ 张景伟，田馨铭．利用ＢＴ技术设计视频点播系统［Ｊ］．电 脑知识与技术，２００９，５（１２）：３２６２—３２６４． ［１１］Ｑｉｕ Ｄ，Ｓｒｉｋａｎｔ Ｒ．Ｍｏｄｅｌｉｎｇ ａｎｄ ｐｅｒｆｏｍａｒｎｃｅ ａｎａｌｙｓｉｓ ｏｆ ＢｉｔＴ－ ｏｒｒｅｎｔ－ｌｉｋｅ ｐｅｅｒ—ｔｏ—ｐｅｅｒ ｎｅｔｗｏｒｋｓ［Ｊ］．ＡＣＭ ＳＩＧＣＯＭＭ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ，２００４，３４（４）：３６７—３７８． ［１２］Ｘｕ Ｄ，Ｈｅｆｅｅｄａ Ｍ，Ｈａｍｂｒｕｓｃｈ Ｓ，ｅｔ ａ１．Ｏｎ ｐｅｅｒ—ｔｏ—ｐｅｅｒ ｍｅｄｉａ ［７］ 王裕邦，卢显良，段翰聪，等．ＢＴ流量控制系统的设计与实 现［Ｊ］．计算机应用研究，２００７，２４（９）：２１４—２１６． ［８］ 夏辉宇，孟令奎，娄书荣．ＢｉｔＴｏｒｒｅｎｔ的影像流式传输模型 研究［Ｊ］．测绘学报，２０１３，４２（２）：２２５—２３２． ｓｔｒｅａｍｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２２ｎｄ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｆｅｎｒｅｎｃｅ ｏｎ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｍｐｕｔｉｎｇ ｓｙｓｔｅｍｓ．［Ｓ．１．］：ＩＥＥＥ，２００２：３６３— ３７１． ［９］ Ｃｏｈｅｎ Ｂ．Ｉｎｃｅｎｔｉｖｅｓ ｂｕｉｌｄ ｒｏｂｕｓｔｎｅｓｓ ｉｎ ＢｉｔＴｏｒｒｅｎｔ『ｃ］／／Ｐｒｏｃ ｏｆ ｗｏｒｋｓｈｏｐ ｏｎ ｅｃｏｎｏｍｉｃｓ ｏｆ ｐｅｅｒ－ｔｏ—ｐｅｅｒ ｓｙｓｔｅｍｓ．［Ｓ．１．］： ［Ｓ．ｎ．］，２００３：６８—７２． ［１０］Ｗａｎｇ Ｈ，Ｌｉｕ Ｊ，Ｘｕ Ｋ．Ｍｅａｓｕｒｅｍｅｎｔ ａｎｄ ｅｎｈａｎｃｅｍｅｎｔ ｏｆ ＢｉｔＴ－ ［１３］苗文健，杨雅辉．面向视频播放的ＢＴ协议下载算法的改进 ［Ｊ］．计算机工程与应用，２０１０，４６（１８）：６８—７０． ［１４］刘宏亮．ＢｉｔＴｏｒｒｅｎｔ核心算法研究与改进［Ｄ］．北京：北京交 通大学，２００８．
