一种基于DNA计算的改进遗传算法
- 格式：pdf
- 大小：251.08 KB
- 文档页数：5
下载文档原格式
合集下载
遗传算法的改进与应用
遗传算法的改进与应用遗传算法是一种模拟自然进化过程并求解最优解的计算方法。
它主要受到遗传学中的基因进化和自然选择的启发，模拟生物群体中个体之间的竞争、选择和繁殖过程，从而使种群逐步趋向最优解。
遗传算法的基本工作原理是以一定的适应度函数作为评价标准，在一个种群中不断地评估每个个体的适应度并进行复制、交叉、变异等操作，产生下一代群体。
通过不断地迭代求解，最终找到适应度函数达到最大值或最小值的优化解。
这种算法被广泛应用于函数优化、组合优化、动态优化、多目标优化等众多领域。
然而，遗传算法有其局限性和不足之处。
其中，算法本身的收敛速度较慢是被广泛诟病的问题之一。
在实际应用中，为了提升算法的收敛速度和精度，人们对遗传算法进行了各种修改和改进。
例如，基于分布式的遗传算法（DGA）将一个单点交叉操作改进为多点交叉，有效地提升了算法的搜索能力。
与此类似地，基于强化学习的遗传算法（RLGA）使用强化学习提高了算法的局部搜索能力，以更快地找到全局最优解。
此外，遗传算法还可以与其他算法结合使用，形成混合优化算法。
例如，粒子群算法（PSO）和遗传算法的结合使用，既保留了遗传算法的全局搜索特性，又充分发挥了PSO算法的速度快、精度高的特点。
除此之外，遗传算法可以应用于很多领域。
在工程领域，遗传算法常被应用于优化设计问题、机器人路径规划和信号处理等问题。
在经济领域，遗传算法可用于个人理财规划、股票投资策略的优化等问题。
在人工智能领域，遗传算法被用于构建深度学习模型、自然语言处理、图像识别等等。
总的来说，虽然遗传算法存在局限性，但它已经被证明是一种非常优秀、有效的优化算法。
随着新的技术和方法的不断出现，遗传算法的效率和精度将继续提高。
未来，这种算法将被广泛应用于更多的领域，并发挥出更强大的威力。
一种改进的遗传算法及其应用
一种改进的遗传算法及其应用杨晓燕;李水仙;周武夷【摘要】为解决遗传算法的早熟和局部收敛现象,提出的一种改进的遗传算法,该算法引入海明距离构造初始种群,在选择、交叉、变异过程中采用最优保存策略.实验表明改进的遗传算法增强了种群的多样性,并在一定程度上避免早熟现象发生,同时又能较快找到全局最优解.【期刊名称】《丽水学院学报》【年(卷),期】2010(032)005【总页数】4页(P38-41)【关键词】遗传算法;多样性;最优保存策略;背包问题【作者】杨晓燕;李水仙;周武夷【作者单位】闽江学院计算机系,福建,福州,350108;闽江学院计算机系,福建,福州,350108;闽江学院计算机系,福建,福州,350108【正文语种】中文【中图分类】TP301.6遗传算法[1]是当今影响最广泛，同时也是发展最迅速的进化计算方法之一。
作为一种模拟生物进化过程的新颖方法，遗传算法对非线性和复杂问题具有很强的鲁棒性和全局搜索能力，因此，被广泛应用于机器学习、模式识别、数学规划等领域。
但传统的遗传算法往往存在易早熟、易陷入局部最优解、后期收敛速度较慢等不足。
针对以上问题，文献［2］提出一种基于物种方程和Kriging算子的多种群遗传算法；文献［3］提出通过引入具有优良性能的修正种群替换进化种群较差个体的策略，以提高种群的多样性；文献［4］提出一种自适应调节交叉概率和变异概率的策略以避免早熟，提高算法的收敛速度。
本文提出引入海明距离构造初始种群，以提高种群的多样性，在选择、交叉、变异操作中采用最优保存的策略，以提高算法的收敛速度。
实验结果表明，改进的遗传算法不仅能加快遗传进化速度，而且还能增强算法的全局收敛性能，从而得到满意的全局最优值。
1.1 初始种群的构造遗传算法对初始种群很敏感，采用随机生成初始种群的方法会导致算法收敛速度较慢。
为了加快求解速度，本文引入海明距离的定义[5]来构造初始种群，使得初始种群在解空间中尽量分布均匀。
一种改进的遗传算法
一种改进的遗传算法
刘伟军;康磐石
【期刊名称】《沈阳工业大学学报》
【年(卷),期】2000(022)005
【摘要】针对传统遗传算法在编码方案及交叉操作中存在的局限性，提出了一种新的遗传算法的改进方法．该方法(1)以实数编码代替二进制编码，有效地解决了传统遗传算法中二进制编码串的长度与计算精度、运算量之间的矛盾，(2)根据适应度值对父染色体进行重组操作，克服了传统遗传算法中交叉操作所存在的盲目性．最后，以求解自然对数和神经网络的训练为例验证了所提出方法的有效性．【总页数】4页(P441-444)
【作者】刘伟军;康磐石
【作者单位】中国科学院沈阳自动化研究所机器人学开放实验室，辽宁沈阳110015;辽宁省机械研究院，辽宁沈阳 110032
【正文语种】中文
【中图分类】O235
【相关文献】
1.一种改进了的基于遗传算法的维特征加权改进FCM算法 [J], 韦相;汤兴华
2.一种新的改进遗传算法--混合式遗传算法 [J], 令狐选霞;徐德民;张宇文
3.一种基于改进遗传算法的组合加工约束混流车间调度方法 [J], 朱海华;张毅;孙宏伟;廖良闯;唐敦兵
4.一种改进的双种群遗传算法在服务机器人仿真中的应用 [J], 刘璇;陈万米;钟灿灿
5.一种改进的自适应遗传算法 [J], 刘萍;俞焕
因版权原因，仅展示原文概要，查看原文内容请购买。
遗传算法改进及算法应用PPT课件
修正过的交叉临界值的公式为:
r就表示交叉临界值，g表示该种群此时的进化代数，G表示该种群规定 的总的进化代数。
第25页/共37页
r是一个(1/3,2/3]之间的数，并不是固定不变的，是随着当前的进化代数 的增长而不断增大的。
如果需要进行交叉的两个父代个体的相似度S大于或等于当前的交叉临 界值r时，则不准这两个父代个体进行交叉互换操作，以避免破坏它们的优良 基因模式。
第3页/共37页
GA流程
第4页/共37页
遗传算法基本原理
1、基本思想
模拟自然界优胜劣汰的进化现象，把搜索空间映射为 遗传空间，把可能的解编码成一个向量——染色体，向量的 每个元素称为基因。 通过不断计算各染色体的适应值，选 择最好的染色体，获得最优解。
2、遗传算法的基本运算
⑴ 选择运算 ⑵ 交换操作 ⑶ 变异
④交换率: Pc 一般为60~100%. ⑤变异率: Pm 一般为0.1~10%
第12页/共37页
实例
1、产生初始种群
0001100000 0101111001 0000000101 1001110100 1010101010
（8）
（5）
（2）
（10）
（7）
1110010110 1001011011 1100000001 1001110100 000101001
第17页/共37页
5、变异
000101010010100 11111101001101101101 111100000000010001 11000011111100110000 1100110011001100110 11111010011000101000 11000010001110011110 11100001010100000011 11100001010100010010 00000011001100010011
r就表示交叉临界值，g表示该种群此时的进化代数，G表示该种群规定 的总的进化代数。
第25页/共37页
r是一个(1/3,2/3]之间的数，并不是固定不变的，是随着当前的进化代数 的增长而不断增大的。
如果需要进行交叉的两个父代个体的相似度S大于或等于当前的交叉临 界值r时，则不准这两个父代个体进行交叉互换操作，以避免破坏它们的优良 基因模式。
第3页/共37页
GA流程
第4页/共37页
遗传算法基本原理
1、基本思想
模拟自然界优胜劣汰的进化现象，把搜索空间映射为 遗传空间，把可能的解编码成一个向量——染色体，向量的 每个元素称为基因。 通过不断计算各染色体的适应值，选 择最好的染色体，获得最优解。
2、遗传算法的基本运算
⑴ 选择运算 ⑵ 交换操作 ⑶ 变异
④交换率: Pc 一般为60~100%. ⑤变异率: Pm 一般为0.1~10%
第12页/共37页
实例
1、产生初始种群
0001100000 0101111001 0000000101 1001110100 1010101010
（8）
（5）
（2）
（10）
（7）
1110010110 1001011011 1100000001 1001110100 000101001
第17页/共37页
5、变异
000101010010100 11111101001101101101 111100000000010001 11000011111100110000 1100110011001100110 11111010011000101000 11000010001110011110 11100001010100000011 11100001010100010010 00000011001100010011
DNA遗传算法的集成研究与应用
DNA遗传算法的集成研究与应用作为进化计算最重要的一个分支, 遗传算法在许多领域已经获得大量的研究但发展到现在仍然存在很多缺陷。
遗传算法进化到后期, 种群中的个体相似度较高,无法对解空间做进一步的搜寻, 导致算法早熟收敛。
遗传算法的局部搜索能力较弱, 在最优解附近需要花费较长时间才能得到问题的全局最优解。
而且, 传统遗传算法一般采用二进制编码方式, 这种编码方法不能表达丰富的生物遗传信息, 在计算模型中无法反映遗传信息对生物体生长、发育的调制作用,尤其是起关键控制作用的DNA编码机制。
自从Adleman提出DNA计算理论开始,基于DNA计算的智能系统开始引起研究人员的注意, 它能够更好的反映生物体的遗传信息, 从而建立功能更强、效率更高的智能计算模型。
受此启发, 研究者们开始尝试进一步分析和模仿生物遗传信息的调控功能, 建立分子水平上的遗传信息模型。
基于这种思想,学者们提出了DNA®传算法。
这种算法将遗传算法与DNA计算相结合,在DNA S码方式的基础上对种群中的个体进行遗传操作，从而更好地模拟生物的遗传机理和遗传信息表达机制。
DNA S传算法的结构与一般遗传算法基本上类似,主要区别在于DNA S传算法采用DNA S码方式，并基于这种编码方式发展众多的生物遗传操作模拟进化过程,得到问题的解。
由于DNA®传算法是建立在遗传算法的框架上，因而继承了传统遗传算法的诸多优点, 具有优良的全局搜索性能及隐性并行性等。
但与传统遗传算法相比，DNA遗传算法在编码方式上有较大的改进，更适合于表达复杂知识, 方法灵活, 编码精度高。
丰富的编码及译码特性, 使得种群可以在变异概率低的情况, 仍保持一定水平的多样性。
同时由于引入复杂的基因级的操作, 可以发展更多更有效的遗传操作算子如倒位、分离、异位等, 进一步丰富遗传操作。
本文在前期大量工作的基础上, 对DNA遗传算法及应用开展了更进一步的研究,主要研究工作如下：(1)提出了一种新颖的三联核苷酸编码的DNA遗传算法-GA-TNE+DRO依据生物进化机制,通过模拟DNA在氨基酸水平上的繁殖过程来模拟DNA分子的遗传操作，在解空间中创建新的个体。
一种改进的遗传算法
一种改进的遗传算法
石玉;于盛林
【期刊名称】《合肥工业大学学报（自然科学版）》
【年(卷),期】2002(025)003
【摘要】采用实数编码的遗传算法,在基于适应值比例和最优保留策略结合的选择、数值交叉及一致变异的基础上对算法作了两方面的改进,即对交叉操作采用剔除无
效个体和保留父代进入选择,在算法出现未成熟收敛的趋势时插入混沌序列,增加群
体多样性,以判断算法搜索特性.对函数优化仿真结果显示,新方法提高了搜索精度,较好地克服了未成熟收敛现象,取得了较满意的优化效果.
【总页数】4页(P403-406)
【作者】石玉;于盛林
【作者单位】南京航空航天大学,自动化学院,江苏,南京,210016;南京航空航天大学,自动化学院,江苏,南京,210016
【正文语种】中文
【中图分类】TP183
【相关文献】
1.一种改进了的基于遗传算法的维特征加权改进FCM算法 [J], 韦相;汤兴华
2.一种新的改进遗传算法--混合式遗传算法 [J], 令狐选霞;徐德民;张宇文
3.一种基于改进遗传算法的组合加工约束混流车间调度方法 [J], 朱海华;张毅;孙宏伟;廖良闯;唐敦兵
4.一种改进的双种群遗传算法在服务机器人仿真中的应用 [J], 刘璇;陈万米;钟灿灿
5.一种改进的自适应遗传算法 [J], 刘萍;俞焕
因版权原因，仅展示原文概要，查看原文内容请购买。
DNA遗传算法研究
２００７年第１２期福建电脑ＤＮＡ遗传算法研究王丽丽１，杨光军２（１．德州学院计算机系山东德州２５３０１５２．德州学院机电工程系山东德州２５３０１５）【摘要】：ＤＮＡ计算与遗传算法的集成起了科学界的广泛关注。
交叉操作是ＤＮＡ遗传算法（ＤＮＡ－ＧＡ）的核心，其效率和精度直接影响到计算结果。
论文主要介绍了ＤＮＡ－ＧＡ计算过程中的交叉、变异问题及已有的几种主要的交叉变异方法，最后指出了ＤＮＡ－ＧＡ存在的问题及研究方向。
【关键词】：ＤＮＡ遗传算法；ＤＮＡ编码；倒位；基因转移１．引言ＤＮＡ计算是一种新的计算模式，首先是由Ａｄｌｅｍａｎ博士于１９９４年提出来的［１］。
其最大优点是充分利用了ＤＮＡ分子具有海量存储遗传密码以及生化反应的海量并行性。
近年来，一大批科学家投身于ＤＮＡ计算这一新的研究领域，提出了许多组合优化问题的ＤＮＡ计算模型［２］。
遗传算法（ＧＡ）是一种基于自然选择和生物遗传机制的优化技术［３］，其位串编码由于简单性和易处理性，是最常用的经典方法。
然而，这种简单的编码方法不能表达丰富的遗传信息，许多基于基因级的操作也难以在常规ＧＡ中得到模拟和实现。
并且，在解决复杂问题时，染色体长度有时很长，进化计算代价很大，增加了问题的复杂性。
为了进一步模拟生物的遗传机理和基因调控机理，一些学者提出了基于ＤＮＡ编码的遗传算法（ＤＮＡ－ＧＡ）［４］。
本文主要介绍ＤＮＡ－ＧＡ的实现过程，重点介绍用基因转移代替传统的交叉操作和几种变异操作的新方法。
２．ＤＮＡ－ＧＡ基本框架２．１ＤＮＡ计算中的基本术语［１］ＤＮＡ是在ＤＮＡ计算中起中心作用的分子，是重要的基因物质，携带着生物的遗传信息。
ＤＮＡ的基本元素是核苷酸，由于化学结构的不同，核苷酸划分为腺嘌呤（Ａ），鸟嘌呤（Ｇ），胞嘧啶（Ｃ）和胸嘧啶（Ｔ）四类碱基。
碱基之间的配对关系是：Ａ与Ｔ配对，Ｃ与Ｇ配对。
２．２ＤＮＡ遗传算法的结构ＤＮＡ－ＧＡ的结构与常规遗传算法类似，如图１所示。
基于改进遗传算法的配送路径优化方案
圃臣 旦
文０ 徐 鹏 沈金星 （ 河海大学交通学院 海洋 学院 南京）
节 点的 最 短 回路 ，不 需 要对 整 个 网络 进 行 问题 求 解 ，可 以只 提 取 出 与节 点 紧密 相 关 的节 点 与 弧 段构 成 子 网络 ，在 子 网络 中进 以 及车 辆 的行 使路 线 的新 的 测序 方式 ，很 行 问题 求 解 ， 降低 问 题规 模 ，提 高算 法 效 好地 解 决 遗 传算 法 的早 熟、 局 部 寻优 能力 率 。 即基 于 方 向策 略 的 限制 搜 索 区域 方 法 差 的 问题 。 通过 测 试 ， 发现 交替 使 用遗 传 【 ７】，比 如搜 索从 北京 到沈 阳的 最短 路径 ， 算 法和 ＤＮＡ 算 法进 行 全局寻优 和 局部寻优 完全 可 以 把 南京 、重 庆 等节 点 排 除在 搜 索 可 以相 对 较 准确 、 快速 的实 现 车辆 线路 的 空 间以 外 。 该 方法 是 一种 有 损 局部 寻 优 算 寻优 。 法 ， 即排 除 了概 率 极 小 的子 网 络外 最 优 路 关键词 ： 传算法 ；Ｄ Ａ算法 ；Ｖ 遗 Ｎ ＲＰ 径的可能。 引 言 在 单 条路 径 寻 优 中 ， 以该 点集 作 最 小 物 流被 誉 为 经济 活 动 中 的 “ 开 发 的 凸包 ，并 以该 凸包 区 域 作适 当 扩 充的 缓 冲 未 黑大 陆 ” 、企 业 的 “ 三利 润 源 泉 ” 第 。物 流 区 ，落 在 缓 冲 区内 的 节 点 与弧 段构 成 子 网 的 目标 在 于 以最 小 的费 用 满 足消 费 者 的最 络进 行搜 索 计算 。Ｄ Ｎ Ａ 计 算 模型 即构 建 大需 求 ，而 运 输 的 费用 占整 个企 业 物 流的 在该 子 网 络 上进 行 ，在 保证 有 效搜 索 的 基 ４０％ 左右 。在运输 过 程 中 ，配 送是其 中一 础上 多余 的边 （ 助边 ） 量 少 。 辅 尽 个 重要 的直 接 与 消 费者 相 连 接的 环 节 ，物 我们这里的 Ｖ ＲＰ可描 述为 ：已知 ｎ 个 流 配送 车辆 的线 路优 化 问 题 ，更是 物 流 配 代售 点之 间的 相 互 费用 大 小 （在 编 码 时 用 送优 化 中 的关 键 环 节 ，正 确 合理 的安 排车 Ｄ Ｎ Ａ 片 段的长 度来表 示 ） ，现有 一辆 配送 辆 的配 送线 路 ，可 以有 效 的 减少 车 辆 的空 车必须 访遍 ｎ个代 售点 ， 最后 又必须返 回 驶率 ，实现 合 理 线路 运 输 ，从而 降 低 运输 起始 送 货 点 。如 何 安 排车 对 这 些代 售 点 的 成本 ，节约 运 输 时 间 ，提 高 经济 效 益 ，达 有 向行 使 路线 ，可 使 其行 驶 路 线 的总 费 用 到物 流 科 学 化 管 理 。 最 少？ 以 图论 术语 来 说 ，假设 有 一 个 图 Ｇ 二 、遗传 算法与 Ｄ ＮＡ 算法 （Ｖ， Ｗ ） Ｅ， ，其中 ，Ｖ 是顶点集 ，Ｅ是边 遗 传算 法 是一 种 基 于 自然 选 择和 自然 集，ｗ 是顶点和边的权值集 ，设 Ｄ＝（ｉ） 是 ｄｊ 遗传 机 制 的 自适 应 的随 机 搜索 算 法 ，它是 由顶点 ｉ和 顶点 ｊ之 间的 距离所组 成的 距离 种 有 效 的 解 决 最优 化 问题 的 方 法 。 矩 阵 ，Ｖ 就是 求出一 条通过所 有顶点 完 ＲＰ 遗 传算 法 求解 工 程 实 际最 优 化 问题 的 成 配送 任 务 并 且 总 费 用 最 少 的有 向路 径 。 基本 步 骤是 ：首 先对 可 行 域 中的 个 体进 行 （ ） 算 法 思 想 一 编 码 ；然后 在 可 行域 中 随机 挑 选 指 定群 体 依据上述思 想 ，为 了便于利用 ＤＮＡ 计 大 小 的 一些 个 体组 成 作 为进 化 起 点 的第 一 算 ，我们设 计如下 的求解该 ＶＲＰ 的基 本算 代 群 体 ，并 计 算 每 个 个 体 的 目标 函数 值 ， 法 ： 即该 个 体的 适 应 度 。利 用选 择 机 制 从群 体 步骤 １ ：搜索 出所有 闭合 路径 。 中随 机挑 选 个 体作 为 繁 殖过 程 前 的 个体 样 步骤 ２ ：找 出那些开始 于 ０、结束 也 本 。选择 机 制 保证 适 应 度较 高 的 个体 能 够 是 ０ 的 固定 顶 点的 闭路 经 ，也 就 是说 ，保 保 留较 多的 样 本 ；而 适 应 度较 低 的 个体 则 留那 些经 过 Ｏ 的 固定顶 点 的 闭路 经 。 保 留较 少的 样 本 ，甚 至 被 淘汰 。在 繁殖 过 步骤 ３ ：找 出那 些 经过 所 有节 点 至 少 程 中 ，遗 传 算 法提 供 了交 叉和 变 异两 种 算 次 的 闭合 路径 ，也就 是 说 ，保 留 ０ 的 所 法 对 挑 选 后 的 样 本 进 行 交 换 和 基 因突 变 。 有 广 义 Ｅｕ ｅ ｌ ｒ闭 迹 。 交叉算 法 交 换随 机 挑 选 的两 个 个 体 的某 些 步骤 ４：找出最短的 广义 Ｅｕｌ ｅ ｒ闭迹 ， 位 ，变异 算 子 则直 接 对 一个 个 体 中 的随 机 这 就 是 我 们 所 需 的 解 。 挑 选 的某 一 位 进行 突 变 。这 样 通 过 选择 和 步骤 ５：确 定 出配送 车路 线 。 繁 殖就 产 生 了下一 代 群体 。 重复 上述 选 择 （ ）Ｖ Ｒ Ｐ 的 Ｄ Ｎ Ａ 计 算 编码 以及 二 和 繁 殖 过 程 ， 直 到 结 束 条 件 得 到 满 足 为 实 施 止 。进 化 过 程 最后 一 代 中的 最 优 解就 是 用 ｌ 、构建 ＶＲ 的 ＤＮＡ 计算 编码 Ｐ 遗 传算 法 解 最 优 化 问题 所 得 到 的 最 终 结 先 选 取 节 点和 弧 段 的基 本 寡聚 核 苷 酸 果。 片 断 ，通 常 是 根 据相 应 权 值的 大 小 先 同等 遗 传 算 法 是 一 种 自适 应 随 机 搜 索 方 放 大 为 正 整 数 ， 再 分 别 求 出 节 点 和 弧 段 的 法 ，具 有 极 强的 并 行机 制 ，在 解 决 整体 的 最 小 公倍 数 作 为 基本 寡 聚 核苷 酸 长 度的 制 搜索 问题 时 ，具 有 很 强 的鲁 棒 性 和全 局 寻 定 标 准 。 优 能 力 。但 遗 传算 法忽 视 了个 体潜 力的 开 由于 Ｄ Ｎ Ａ 编 码片 断的 数 目随着 路径 发 而只 重 视 群体 整 体性 能 的 提 高 。也 就 是 条 数 的增 加 呈 指 数增 长 ，如此 复 杂 的编 码 说 ，遗 传 算 法能 够 以较 大 的 概率 找 到 最 优 也将 成 为 Ｄ Ｎ Ａ 计 算的 技术瓶 颈 。本 文采 区 域而 不 是 最优 点 。 因此 遗 传 算 法在 应 用 用 基本 寡聚 核 苷酸 （ 个 ）连 接组 合 （ Ｋ 单 中 也有 一 些 不尽 人 意 的地 方 ，主 要表 现 在 独长为 ４的一条就能形成 Ｋ４／２种组合 ，因 算 法收 敛 慢 、效 率 低 、容 易 早 熟 、局 部 寻 此 所需 的 寡 聚 核苷 酸 的 种 类大 大减 少 ）从 优能力差等。 很 大 程 度 上 简 化 这 个 过 程 ， 尽 量 减 少 三 、基于 Ｄ Ａ算法对 Ｖ多地 通过 合理 的编 码 为追 求 Ｄ Ｎ Ａ 计算 局部寻 优解 的质量 ， 进 行 处 理 ， 从 而 大 大 减 少 了 误 差 的 来 源 ， 我们 在 算 法 中加 入 基于 启 发 式知 识 的 方 向 这也 是 Ｄ Ｎ Ａ 计 算研 究 的难 以解决 的 问题 搜 索 策 略 。在 网络 拓扑 图中 ，求解 某 几 个 之 一 。
文０ 徐 鹏 沈金星 （ 河海大学交通学院 海洋 学院 南京）
节 点的 最 短 回路 ，不 需 要对 整 个 网络 进 行 问题 求 解 ，可 以只 提 取 出 与节 点 紧密 相 关 的节 点 与 弧 段构 成 子 网络 ，在 子 网络 中进 以 及车 辆 的行 使路 线 的新 的 测序 方式 ，很 行 问题 求 解 ， 降低 问 题规 模 ，提 高算 法 效 好地 解 决 遗 传算 法 的早 熟、 局 部 寻优 能力 率 。 即基 于 方 向策 略 的 限制 搜 索 区域 方 法 差 的 问题 。 通过 测 试 ， 发现 交替 使 用遗 传 【 ７】，比 如搜 索从 北京 到沈 阳的 最短 路径 ， 算 法和 ＤＮＡ 算 法进 行 全局寻优 和 局部寻优 完全 可 以 把 南京 、重 庆 等节 点 排 除在 搜 索 可 以相 对 较 准确 、 快速 的实 现 车辆 线路 的 空 间以 外 。 该 方法 是 一种 有 损 局部 寻 优 算 寻优 。 法 ， 即排 除 了概 率 极 小 的子 网 络外 最 优 路 关键词 ： 传算法 ；Ｄ Ａ算法 ；Ｖ 遗 Ｎ ＲＰ 径的可能。 引 言 在 单 条路 径 寻 优 中 ， 以该 点集 作 最 小 物 流被 誉 为 经济 活 动 中 的 “ 开 发 的 凸包 ，并 以该 凸包 区 域 作适 当 扩 充的 缓 冲 未 黑大 陆 ” 、企 业 的 “ 三利 润 源 泉 ” 第 。物 流 区 ，落 在 缓 冲 区内 的 节 点 与弧 段构 成 子 网 的 目标 在 于 以最 小 的费 用 满 足消 费 者 的最 络进 行搜 索 计算 。Ｄ Ｎ Ａ 计 算 模型 即构 建 大需 求 ，而 运 输 的 费用 占整 个企 业 物 流的 在该 子 网 络 上进 行 ，在 保证 有 效搜 索 的 基 ４０％ 左右 。在运输 过 程 中 ，配 送是其 中一 础上 多余 的边 （ 助边 ） 量 少 。 辅 尽 个 重要 的直 接 与 消 费者 相 连 接的 环 节 ，物 我们这里的 Ｖ ＲＰ可描 述为 ：已知 ｎ 个 流 配送 车辆 的线 路优 化 问 题 ，更是 物 流 配 代售 点之 间的 相 互 费用 大 小 （在 编 码 时 用 送优 化 中 的关 键 环 节 ，正 确 合理 的安 排车 Ｄ Ｎ Ａ 片 段的长 度来表 示 ） ，现有 一辆 配送 辆 的配 送线 路 ，可 以有 效 的 减少 车 辆 的空 车必须 访遍 ｎ个代 售点 ， 最后 又必须返 回 驶率 ，实现 合 理 线路 运 输 ，从而 降 低 运输 起始 送 货 点 。如 何 安 排车 对 这 些代 售 点 的 成本 ，节约 运 输 时 间 ，提 高 经济 效 益 ，达 有 向行 使 路线 ，可 使 其行 驶 路 线 的总 费 用 到物 流 科 学 化 管 理 。 最 少？ 以 图论 术语 来 说 ，假设 有 一 个 图 Ｇ 二 、遗传 算法与 Ｄ ＮＡ 算法 （Ｖ， Ｗ ） Ｅ， ，其中 ，Ｖ 是顶点集 ，Ｅ是边 遗 传算 法 是一 种 基 于 自然 选 择和 自然 集，ｗ 是顶点和边的权值集 ，设 Ｄ＝（ｉ） 是 ｄｊ 遗传 机 制 的 自适 应 的随 机 搜索 算 法 ，它是 由顶点 ｉ和 顶点 ｊ之 间的 距离所组 成的 距离 种 有 效 的 解 决 最优 化 问题 的 方 法 。 矩 阵 ，Ｖ 就是 求出一 条通过所 有顶点 完 ＲＰ 遗 传算 法 求解 工 程 实 际最 优 化 问题 的 成 配送 任 务 并 且 总 费 用 最 少 的有 向路 径 。 基本 步 骤是 ：首 先对 可 行 域 中的 个 体进 行 （ ） 算 法 思 想 一 编 码 ；然后 在 可 行域 中 随机 挑 选 指 定群 体 依据上述思 想 ，为 了便于利用 ＤＮＡ 计 大 小 的 一些 个 体组 成 作 为进 化 起 点 的第 一 算 ，我们设 计如下 的求解该 ＶＲＰ 的基 本算 代 群 体 ，并 计 算 每 个 个 体 的 目标 函数 值 ， 法 ： 即该 个 体的 适 应 度 。利 用选 择 机 制 从群 体 步骤 １ ：搜索 出所有 闭合 路径 。 中随 机挑 选 个 体作 为 繁 殖过 程 前 的 个体 样 步骤 ２ ：找 出那些开始 于 ０、结束 也 本 。选择 机 制 保证 适 应 度较 高 的 个体 能 够 是 ０ 的 固定 顶 点的 闭路 经 ，也 就 是说 ，保 保 留较 多的 样 本 ；而 适 应 度较 低 的 个体 则 留那 些经 过 Ｏ 的 固定顶 点 的 闭路 经 。 保 留较 少的 样 本 ，甚 至 被 淘汰 。在 繁殖 过 步骤 ３ ：找 出那 些 经过 所 有节 点 至 少 程 中 ，遗 传 算 法提 供 了交 叉和 变 异两 种 算 次 的 闭合 路径 ，也就 是 说 ，保 留 ０ 的 所 法 对 挑 选 后 的 样 本 进 行 交 换 和 基 因突 变 。 有 广 义 Ｅｕ ｅ ｌ ｒ闭 迹 。 交叉算 法 交 换随 机 挑 选 的两 个 个 体 的某 些 步骤 ４：找出最短的 广义 Ｅｕｌ ｅ ｒ闭迹 ， 位 ，变异 算 子 则直 接 对 一个 个 体 中 的随 机 这 就 是 我 们 所 需 的 解 。 挑 选 的某 一 位 进行 突 变 。这 样 通 过 选择 和 步骤 ５：确 定 出配送 车路 线 。 繁 殖就 产 生 了下一 代 群体 。 重复 上述 选 择 （ ）Ｖ Ｒ Ｐ 的 Ｄ Ｎ Ａ 计 算 编码 以及 二 和 繁 殖 过 程 ， 直 到 结 束 条 件 得 到 满 足 为 实 施 止 。进 化 过 程 最后 一 代 中的 最 优 解就 是 用 ｌ 、构建 ＶＲ 的 ＤＮＡ 计算 编码 Ｐ 遗 传算 法 解 最 优 化 问题 所 得 到 的 最 终 结 先 选 取 节 点和 弧 段 的基 本 寡聚 核 苷 酸 果。 片 断 ，通 常 是 根 据相 应 权 值的 大 小 先 同等 遗 传 算 法 是 一 种 自适 应 随 机 搜 索 方 放 大 为 正 整 数 ， 再 分 别 求 出 节 点 和 弧 段 的 法 ，具 有 极 强的 并 行机 制 ，在 解 决 整体 的 最 小 公倍 数 作 为 基本 寡 聚 核苷 酸 长 度的 制 搜索 问题 时 ，具 有 很 强 的鲁 棒 性 和全 局 寻 定 标 准 。 优 能 力 。但 遗 传算 法忽 视 了个 体潜 力的 开 由于 Ｄ Ｎ Ａ 编 码片 断的 数 目随着 路径 发 而只 重 视 群体 整 体性 能 的 提 高 。也 就 是 条 数 的增 加 呈 指 数增 长 ，如此 复 杂 的编 码 说 ，遗 传 算 法能 够 以较 大 的 概率 找 到 最 优 也将 成 为 Ｄ Ｎ Ａ 计 算的 技术瓶 颈 。本 文采 区 域而 不 是 最优 点 。 因此 遗 传 算 法在 应 用 用 基本 寡聚 核 苷酸 （ 个 ）连 接组 合 （ Ｋ 单 中 也有 一 些 不尽 人 意 的地 方 ，主 要表 现 在 独长为 ４的一条就能形成 Ｋ４／２种组合 ，因 算 法收 敛 慢 、效 率 低 、容 易 早 熟 、局 部 寻 此 所需 的 寡 聚 核苷 酸 的 种 类大 大减 少 ）从 优能力差等。 很 大 程 度 上 简 化 这 个 过 程 ， 尽 量 减 少 三 、基于 Ｄ Ａ算法对 Ｖ多地 通过 合理 的编 码 为追 求 Ｄ Ｎ Ａ 计算 局部寻 优解 的质量 ， 进 行 处 理 ， 从 而 大 大 减 少 了 误 差 的 来 源 ， 我们 在 算 法 中加 入 基于 启 发 式知 识 的 方 向 这也 是 Ｄ Ｎ Ａ 计 算研 究 的难 以解决 的 问题 搜 索 策 略 。在 网络 拓扑 图中 ，求解 某 几 个 之 一 。
一种改进的遗传优化算法
４ 重 复步 骤２ 和 ３ ，直 到所 有邻 域操 作 均不能 ） ） ） 改进解 的质量为止 。
３ 在Ａ。 自交换 区域后 依次删 除 与交换区域相 ） 中 同的城 市码 ，则两个子 串变为
Ａ ” ５ ３ ２ ８ ＝６ ４ １ ７ Ｂ” ５ ８ １ ＝３ ４ ６ ７ ２
次 提 出遗 传算 法（ ｎ ｔｃ Ｇｅ ｅｉ Ａｌｏ ｉｈ ｇ ｒｔ ｍ， ＧＡ） ，。遗 ２ １ 传算法 是模 拟达 尔文 的遗 传选择 和 自然 淘汰的 生物 进
化 过程 的计 算模 型 ，可在 复杂 、庞大 的搜 索空 间 中寻
上进 行遗 传操作 。它 对适 应度 函数没 有特 别的要 求 ， 只要 针 对 于 输 入 可 计算 出能 加 以 比 较 的非 负结 果 即 可 ，这一 特性 使得遗 传算法 应用范 围很广 。
１ 遗传算法求解Ｔ Ｐ Ｓ
ＴＳ 是 一个 易于描 述却难 以处理 的ＮＰ Ｐ 难题 ，ＴＳ Ｐ 因其 典 型性 已成为 比较各 种 启发式 搜索 、优化 算法性
传 统搜 索方 法大 都是 单 点搜索 算法 ，即通过 一定
的规 则 ，使 问题 的 解从 搜索 空间的 一点 移到 另一 点 。 对于 多峰 分布 的搜索 空 间 ，这 种点 对点 的搜 索方 法常
一
种改进 的遗传优化算法
＿
ｌБайду номын сангаас孙小勇
ｌ唐山市城市建筑工程总公司 唐山 ０３０ ６００
摘 要 讨论 了遗传算法 的基本原理 ，提 出一种 引人 局部搜索机制的遗传算法 ，并用于求解ＴＳＰ。实验 表明 ，本算 法在 城市规模较小 时 ，能１ ０ Ｏ ％求 得最优解 ，而且寻 优速度很－ 陕；当城市规模较大 时 ，能在很 短的时间内求得次优解 。
基于改进的选择算子和交叉算子的遗传算法
基于改进的选择算子和交叉算子的遗传算法
哎呀，各位朋友，今儿咱来摆摆龙门阵，说说这改进的选择算子和交叉算子的遗传算法。
这算法啊，就像咱们四川的火锅，得选好料，还得有技巧，才能整出那麻辣鲜香的味儿。
咱们先从选择算子说起。
这就好比咱们陕西人挑面，得选那筋道有嚼劲的面条子。
选择算子也得挑那些优质的基因，才能培育出更好的后代。
有时候，咱也得学学北京人那种精细劲儿，得看清楚、想明白，再下手。
这样选出来的基因，才能确保遗传算法的效率和准确性。
再来说说交叉算子。
这就好比咱们四川人做串串香，得把各种食材串在一起，才能烧出那独特的味道。
交叉算子也是这么回事，得把不同的基因片段交叉组合，才能产生新的可能性。
咱得借鉴陕西人的大胆创新，也得学学北京人的稳重务实，在交叉的过程中既要敢于尝试，又得确保稳定可靠。
总的来说啊，这改进的选择算子和交叉算子的遗传算法，就得咱们三地人结合起来，才能把事儿办得漂漂亮亮的。
四川人的灵活变通，陕西人的大胆创新，还有北京人的精细稳重，都得用上。
这样整出来的算法，才能像咱们三地的美食一样，让人回味无穷啊！。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
个方 面有 所 不 同． 文 中的 实验 数 据 由 Ｍ ｔ ｂ编程 本 ａｌ ａ
随机搜 索 与优化 算 法 ， 具有 不依 赖 于 问题 模 型 、 它 易 于并行 处 理 、 较强 的全 局搜 索功 能 、 有 鲁棒 性强 等特
点， 适用于处理传统搜索方法难 以解决的复杂 和非 线 性 问题 … ． 而 ， 传 算 法 也 存 在 早 期 收 敛 和 然 遗 微调能力差 等不 足． Ｎ Ｄ Ａ计算 是南加 州 大学 的 Ａ ｌｍ ｎ博士 １９ ｄｅ ａ ９ ４年 首 次 提 出 的 Ｊ从 Ｄ Ａ 计 算 ． Ｎ 的角度看 ， 目前 所有 基 于进化 机理 的方法 中 ， 在 遗传
ｉｉｓ ｏｅ ｏｅａ ｏ ｏ ｅａ ｒ ｓ ｎｒｄ ｃｄ ｕ ｌ ｒｈ ａ ｅｅｓｙｉ ｐｅ ｎｅ ｉ ｔ ｂｓｆ ａｅ ｓｃ．Ａ ｎ ｖｌ ｐ ｒｔ ｎ（ ｐ ｒｔ ）ｉ ｉｔ ｕ ｅ ．Ｏ ｒ ｇｉ ｍ ｃｎｂ ａｉ ｌ ｔ ｉ ｏ ｏ ａ ｏｔ ｌ ｍ ｍｅｔｄｖ Ｍａ ａ ｏ ｗ ｒ． ａ ｌ ｔ Ｎ ｍ ｒ ａ ｓ ｌ ｉｎｉｕｔ ｔｓ ｈ ｆ ｃｉ ｎｓ ｎ ｕ ｅ ｏ ｔ ｏ ｅＤ Ａ ｂｓｄＧ ｎ ｔ ｌｏ ｔｍ （ Ｎ Ｇ ． ｕ ｅｉ ｌ ｉ ａ ｏ ｌｓ ａ ｅｅｆ ｔ ｅ ｅｓａ ｄｓｐ ｒ ｒｙ ｆｈ Ｎ —ａｅ ｅ ｅｉ Ａ ｇｒｈ Ｄ Ａ— Ａ） ｃ ｍｕ ｔ ｌ ｒ ｅ ｔ ｅ ｖ ｉｉ ｔ ｃ ｉ
Ａｎ Ｉ ｒ ｖ ｄ Ｇｅ ｅ ｉ Ａｌｏ ｉ ｍ ａ ｅ ｎ ＤＮ Ｃｏ ｍｐ ｏ ｅ ｎ ｔ ｇ ｒ ｈ Ｂ ｓ ｄ ｏ Ａ ｍｐ ｔ ｇ ｃ ｔ ｕｉ ｎ
ＡＸ Ｎ Ｕ Ｌ Ｉ Ｉ Ｊ Ｅ ＵＯ ・ ｈ ａ Ｃ ｕ ｎ， ＭＩ Ｌ —ｕ ｒ Ｎ ｅｑ ａ ｔ
（ ｃｏｌ ｆ ｐ ｌ ｄＳｉｎｅ ｎｖｒｉ ｆ ｃｅｃ ｎ ｅｈ ｏｏｙＢ ｉｎ ，Ｂ ｉｎ ００ ３， ｈｎ ） Ｓｈｏ ｐｉ ｃ ｃ ，Ｕ ｉｅｓｙｏ ｉ ｅａｄＴ ｃｎ ｌ ｅｊ ｇ ｅｊ ｇ１０ ８ Ｃ ｉａ ｏＡ ｅ ｅ ｔ Ｓ ｎ ｇ ｉ ｉ
２ 基于 Ｄ Ａ计算 的改进遗传 算法 Ｎ
本文在基于 Ｄ Ａ编码的染 色体表达机制的基 Ｎ 础 上 引入 了新 的基 因级 操作 （ 子 ） 提 出 了一 种新 算 ，
的 Ｄ Ａ遗传 算法 （ Ｎ Ｎ Ｄ Ａ—Ｇ ． Ｎ Ａ）Ｄ Ａ—Ｇ Ａ与基 本 遗 传 算法 相 比 ， 要在 编码 方 式 和 遗传 操 作 （ 子 ） 主 算 两
算 法尤其 适合 于采 用 Ｄ Ａ编码 来实 现 ． Ｎ 这就 为解 决 遗 传算 法 的不足 提 供 了新 途 径 ． 文 提 出 了一 种 基 本
计算 得 到．
对 Ｄ Ａ—Ｇ Ｎ Ａ模 型作 如 下假设 ：
１ Ｎ 链 是 由 Ａ、 Ｇ 和 Ｃ组 成 的一 个 固定 ）Ｄ Ａ Ｔ、
Ａ ｓ ａｔＴ ｒｖｎ ｔ ｒｍａ ｒ ｃｎ ｅｇｎ ｅａ ｄｂ ｄｌｃｌ ｄｕｔ ｎ ｏ ｉ ｘｒｍ ａ ｅｏ ｍ ｌ ｂ ｔ ｃ ：ｏｐｅｅ ｔｈ ｐｅ ｔ ｅ ｏ ｖｒｅ ｃ ｎ ａ ａ ａｊｓ ｒ ｅ ｕ ｏ ｍｅｔ ｎｓｌ ｎ ｅｔ ｅｖ ｌ ｆ ｏ ｐｉ ｉ ｖｇ ｅ ｕ ｃ —
爱 新 觉 罗 ・ ， 闵乐 泉 川
（ 北京科技大学 应用科学学 院 ， 北京 １０ ８ ） ０ ０ ３
摘
要 ：针 对遗传 算 法 求解复 杂 函数 极 值 问题 中出现 的 早 期 收 敛和 微 调 能 力 差 的 问题 ， 出 提
了一 个具 有 Ｄ Ａ编 码特 征 的改进 遗传 算 法 ， 引入 了新 的操作 （ Ｎ 并 算子 ） 编 制 了一 系列 可在 Ｍａａ ． ｔｂ ｌ
ｃ ｔｄ ｆ ｎ ｔ ｎ ｙ ｇ ｎ ｔ ｌ ｏ ｔｍ ，ｔ ｉ ｐ ｐ ｒｐ ｅ ｅ ｔ ａ ｍｐ ｏ ｅ ｅ ｅ ｉ ｌｏ ｔ ｍ ｉ Ａ ｏ ｉ ｇ ｃ ａ ａ ｔ ｒ ａ ｅ ｕ ｃｉ ｓｂ ｅ ｅ ｉ ａｇ ｒ ｈ ｏ ｃ ｉ ｈ ｓ ａ ｅ ｒ ｓ ｎ ｓ ｎ ｉ ｒ ｖ ｄ ｇ ｎ ｔ ａ ｇ ｒ ｈ ｗ ｔ ＤＮ ｃ ｄ ｎ ｈ ｒ ｃｅ － ｃ ｉ ｈ
Ｋｅ ｒ ｓ ＤＮＡ ｃ ｍｐ ｔ ｇ；ｇ ｎ ｔ ｇ ｒｔ ｍ ；ｎ ｍｅ ｃ ｌｓｍｕ ａｉ ｎ ｙ ｗｏ ｄ ： ｏ ｕｉ ｎ ｅ ｅｉ ａ ｏ ｈ ｃｌ ｉ ｕ ｒ ａ ｉ ｌｔ ｓ ｉ ｏ
１ 引 言
遗传 算法是 近 年来迅 速 发展起 来 的一 种全 新 的
平 台上 实现 的 算 法程 序 ， 并通 过数 值模 拟验 证 了算 法 的有 效性 ． 关 键词 ： Ｎ Ｄ Ａ计 算 ； 传 算 法 ； 值模 拟 遗 数
中图分 类号 ｉ Ｐ ８ １ Ｔ
文献标 识码 ： Ａ
文章 编号 ：１０ — ６３ ２０ ）３ ０ ７ ０ ０７ ２ ８ （０８ ０ —０５ — ５
维普资讯
第 ｌ ３卷
第 ３期 ห้องสมุดไป่ตู้
哈 尔 滨 理 工 大 学 学 报
Ｊ ＯＵＲＮＡＬ ＨＡＲＢ Ｎ ＵＮＩ Ｉ Ｖ．Ｓ ．＆ Ｔ ＣＨ． ＣＩ Ｅ
Ｖｏ ． ３ Ｎｏ ３ １１ ．
２０ ０ ８年 ６月
Ｊ ｎ ，２ ０ ｕ ． ０８
一
种 基 于 Ｄ Ａ 计 算 的 改 进 遗 传 算 法 Ｎ
（ 可变 ） 度 的字符 串 ， 中每 一位 都 具 有 有 限数 或 长 其
目的等 位基 因 ；
于 Ｄ Ａ计算的改进遗传算法， Ｎ 与基本遗传算法相 比 具有 全局 寻优 能力 强 、 确 度 高的特 点 ． 精
收 稿 日期 ： ０ ７— ４—２ ２０ ０ ８ 作 者 简 介 ： 新 觉 罗 ． （９ ５～） 男 ， 京 科 技 大 学 本 科 生 爱 川 １８ ， 北
随机搜 索 与优化 算 法 ， 具有 不依 赖 于 问题 模 型 、 它 易 于并行 处 理 、 较强 的全 局搜 索功 能 、 有 鲁棒 性强 等特
点， 适用于处理传统搜索方法难 以解决的复杂 和非 线 性 问题 … ． 而 ， 传 算 法 也 存 在 早 期 收 敛 和 然 遗 微调能力差 等不 足． Ｎ Ｄ Ａ计算 是南加 州 大学 的 Ａ ｌｍ ｎ博士 １９ ｄｅ ａ ９ ４年 首 次 提 出 的 Ｊ从 Ｄ Ａ 计 算 ． Ｎ 的角度看 ， 目前 所有 基 于进化 机理 的方法 中 ， 在 遗传
ｉｉｓ ｏｅ ｏｅａ ｏ ｏ ｅａ ｒ ｓ ｎｒｄ ｃｄ ｕ ｌ ｒｈ ａ ｅｅｓｙｉ ｐｅ ｎｅ ｉ ｔ ｂｓｆ ａｅ ｓｃ．Ａ ｎ ｖｌ ｐ ｒｔ ｎ（ ｐ ｒｔ ）ｉ ｉｔ ｕ ｅ ．Ｏ ｒ ｇｉ ｍ ｃｎｂ ａｉ ｌ ｔ ｉ ｏ ｏ ａ ｏｔ ｌ ｍ ｍｅｔｄｖ Ｍａ ａ ｏ ｗ ｒ． ａ ｌ ｔ Ｎ ｍ ｒ ａ ｓ ｌ ｉｎｉｕｔ ｔｓ ｈ ｆ ｃｉ ｎｓ ｎ ｕ ｅ ｏ ｔ ｏ ｅＤ Ａ ｂｓｄＧ ｎ ｔ ｌｏ ｔｍ （ Ｎ Ｇ ． ｕ ｅｉ ｌ ｉ ａ ｏ ｌｓ ａ ｅｅｆ ｔ ｅ ｅｓａ ｄｓｐ ｒ ｒｙ ｆｈ Ｎ —ａｅ ｅ ｅｉ Ａ ｇｒｈ Ｄ Ａ— Ａ） ｃ ｍｕ ｔ ｌ ｒ ｅ ｔ ｅ ｖ ｉｉ ｔ ｃ ｉ
Ａｎ Ｉ ｒ ｖ ｄ Ｇｅ ｅ ｉ Ａｌｏ ｉ ｍ ａ ｅ ｎ ＤＮ Ｃｏ ｍｐ ｏ ｅ ｎ ｔ ｇ ｒ ｈ Ｂ ｓ ｄ ｏ Ａ ｍｐ ｔ ｇ ｃ ｔ ｕｉ ｎ
ＡＸ Ｎ Ｕ Ｌ Ｉ Ｉ Ｊ Ｅ ＵＯ ・ ｈ ａ Ｃ ｕ ｎ， ＭＩ Ｌ —ｕ ｒ Ｎ ｅｑ ａ ｔ
（ ｃｏｌ ｆ ｐ ｌ ｄＳｉｎｅ ｎｖｒｉ ｆ ｃｅｃ ｎ ｅｈ ｏｏｙＢ ｉｎ ，Ｂ ｉｎ ００ ３， ｈｎ ） Ｓｈｏ ｐｉ ｃ ｃ ，Ｕ ｉｅｓｙｏ ｉ ｅａｄＴ ｃｎ ｌ ｅｊ ｇ ｅｊ ｇ１０ ８ Ｃ ｉａ ｏＡ ｅ ｅ ｔ Ｓ ｎ ｇ ｉ ｉ
２ 基于 Ｄ Ａ计算 的改进遗传 算法 Ｎ
本文在基于 Ｄ Ａ编码的染 色体表达机制的基 Ｎ 础 上 引入 了新 的基 因级 操作 （ 子 ） 提 出 了一 种新 算 ，
的 Ｄ Ａ遗传 算法 （ Ｎ Ｎ Ｄ Ａ—Ｇ ． Ｎ Ａ）Ｄ Ａ—Ｇ Ａ与基 本 遗 传 算法 相 比 ， 要在 编码 方 式 和 遗传 操 作 （ 子 ） 主 算 两
算 法尤其 适合 于采 用 Ｄ Ａ编码 来实 现 ． Ｎ 这就 为解 决 遗 传算 法 的不足 提 供 了新 途 径 ． 文 提 出 了一 种 基 本
计算 得 到．
对 Ｄ Ａ—Ｇ Ｎ Ａ模 型作 如 下假设 ：
１ Ｎ 链 是 由 Ａ、 Ｇ 和 Ｃ组 成 的一 个 固定 ）Ｄ Ａ Ｔ、
Ａ ｓ ａｔＴ ｒｖｎ ｔ ｒｍａ ｒ ｃｎ ｅｇｎ ｅａ ｄｂ ｄｌｃｌ ｄｕｔ ｎ ｏ ｉ ｘｒｍ ａ ｅｏ ｍ ｌ ｂ ｔ ｃ ：ｏｐｅｅ ｔｈ ｐｅ ｔ ｅ ｏ ｖｒｅ ｃ ｎ ａ ａ ａｊｓ ｒ ｅ ｕ ｏ ｍｅｔ ｎｓｌ ｎ ｅｔ ｅｖ ｌ ｆ ｏ ｐｉ ｉ ｖｇ ｅ ｕ ｃ —
爱 新 觉 罗 ・ ， 闵乐 泉 川
（ 北京科技大学 应用科学学 院 ， 北京 １０ ８ ） ０ ０ ３
摘
要 ：针 对遗传 算 法 求解复 杂 函数 极 值 问题 中出现 的 早 期 收 敛和 微 调 能 力 差 的 问题 ， 出 提
了一 个具 有 Ｄ Ａ编 码特 征 的改进 遗传 算 法 ， 引入 了新 的操作 （ Ｎ 并 算子 ） 编 制 了一 系列 可在 Ｍａａ ． ｔｂ ｌ
ｃ ｔｄ ｆ ｎ ｔ ｎ ｙ ｇ ｎ ｔ ｌ ｏ ｔｍ ，ｔ ｉ ｐ ｐ ｒｐ ｅ ｅ ｔ ａ ｍｐ ｏ ｅ ｅ ｅ ｉ ｌｏ ｔ ｍ ｉ Ａ ｏ ｉ ｇ ｃ ａ ａ ｔ ｒ ａ ｅ ｕ ｃｉ ｓｂ ｅ ｅ ｉ ａｇ ｒ ｈ ｏ ｃ ｉ ｈ ｓ ａ ｅ ｒ ｓ ｎ ｓ ｎ ｉ ｒ ｖ ｄ ｇ ｎ ｔ ａ ｇ ｒ ｈ ｗ ｔ ＤＮ ｃ ｄ ｎ ｈ ｒ ｃｅ － ｃ ｉ ｈ
Ｋｅ ｒ ｓ ＤＮＡ ｃ ｍｐ ｔ ｇ；ｇ ｎ ｔ ｇ ｒｔ ｍ ；ｎ ｍｅ ｃ ｌｓｍｕ ａｉ ｎ ｙ ｗｏ ｄ ： ｏ ｕｉ ｎ ｅ ｅｉ ａ ｏ ｈ ｃｌ ｉ ｕ ｒ ａ ｉ ｌｔ ｓ ｉ ｏ
１ 引 言
遗传 算法是 近 年来迅 速 发展起 来 的一 种全 新 的
平 台上 实现 的 算 法程 序 ， 并通 过数 值模 拟验 证 了算 法 的有 效性 ． 关 键词 ： Ｎ Ｄ Ａ计 算 ； 传 算 法 ； 值模 拟 遗 数
中图分 类号 ｉ Ｐ ８ １ Ｔ
文献标 识码 ： Ａ
文章 编号 ：１０ — ６３ ２０ ）３ ０ ７ ０ ０７ ２ ８ （０８ ０ —０５ — ５
维普资讯
第 ｌ ３卷
第 ３期 ห้องสมุดไป่ตู้
哈 尔 滨 理 工 大 学 学 报
Ｊ ＯＵＲＮＡＬ ＨＡＲＢ Ｎ ＵＮＩ Ｉ Ｖ．Ｓ ．＆ Ｔ ＣＨ． ＣＩ Ｅ
Ｖｏ ． ３ Ｎｏ ３ １１ ．
２０ ０ ８年 ６月
Ｊ ｎ ，２ ０ ｕ ． ０８
一
种 基 于 Ｄ Ａ 计 算 的 改 进 遗 传 算 法 Ｎ
（ 可变 ） 度 的字符 串 ， 中每 一位 都 具 有 有 限数 或 长 其
目的等 位基 因 ；
于 Ｄ Ａ计算的改进遗传算法， Ｎ 与基本遗传算法相 比 具有 全局 寻优 能力 强 、 确 度 高的特 点 ． 精
收 稿 日期 ： ０ ７— ４—２ ２０ ０ ８ 作 者 简 介 ： 新 觉 罗 ． （９ ５～） 男 ， 京 科 技 大 学 本 科 生 爱 川 １８ ， 北