基于遗传算法和蚁群算法的多重序列比对

基于遗传-蚁群混合算法的排课系统孙弋;胡粔珲【摘要】在高校的教务管理中,排课问题是复杂又关键的环节,科目数量众多,教学资源有限等等因素都制约着排课的复杂程度和结果.排课本质就是将课程、班级在合适的时间段安排到合适的教学位置,是一个NP问题的求解.随着规模的不断扩大,问题求解难度呈指数形式增加,当规模达到一定程度的时候就很难在短的时间内求出最优解.鉴于此,本文提出了遗传-蚁群混合算法,将两种算法混合使用,依靠遗传算法生成信息素分布,利用蚁群算法求最优解.实验结果表明,混合算法提高了排课的效率和课表的合理度.【期刊名称】《计算机系统应用》【年(卷),期】2019(028)002【总页数】6页(P81-86)【关键词】排课;NP问题;遗传算法;蚁群算法;混合算法【作者】孙弋;胡粔珲【作者单位】西安科技大学通信与信息工程学院,西安 710054;西安科技大学通信与信息工程学院,西安 710054【正文语种】中文引言教务管理是教育活动的重要支撑,随着高校教育改革的发展,高校人数的增加,但教学资源却相对有限的情况下,排课工作的难度和复杂程度都有所提高.因此,如何设计一个能满足多约束条件并且高效的排课系统成为了目前待解决的问题[1].排课系统的核心是排课,排课算法一个NP完全问题,即算法的计算时间呈指数增长[2].常用的排课算法有: 蚁群算法、遗传算法、贪心算法、图论算法等.遗传算法模拟生物进化过程,具有自适应全局寻优和智能搜索等优点,但是容易收敛得到局部近似最优解,进行大量的无用迭代,难以收敛于最优解[3,4].蚁群算法启发于蚂蚁寻找最优路径的行为,具有较强的鲁棒性,是一种正反馈算法.但当群体规模较大时,搜索初期信息素匮乏,容易产生停滞现象.单算法在解决问题时都会有局限性,花费的时间成本更多,求解的结果不理想[5,6].为了提高排课的效率和成功率,本文提出一种将遗传算法与蚁群算法结合使用的方法,首先使用遗传算法对初始种群进行优化选择,生成蚁群算法所需的信息素,再通过蚁群算法求得全局精确解.优劣互补,充分发挥两者的优势[7].1 排课问题的分析排课问题主要涉及教师、教室、课程、班级、上课时间等因素,排课的实质就是要求课程表在安排的时候不能在上述五个因素中发生冲突.可使用五个集合来表示这些因素.班级集合: C={C1,C2,C3,···,Cn}课程集合: S={S1,S2,S3,···,Sm}教师集合: T={T1,T2,T3,···,Tx}教室集合: R ={R1,R2,R3,···,Rt},教室有多种类型,例如实验室、多媒体教室、机房等,每个教室容纳的人数也不相同.时间段集合: P ={P1,P2,P3,···,Pi},Pi表示时间段,例如P 1为周一的1-2节课,P 2为3-4节课.时间和教室的笛卡儿积为: N = R * P ={(r1,p1),(r2,p2),…,(rn,pn)},N 中的元素是教室-时间对.排课问题由此转化为一门课寻找一个合适的教室时间对.1.1 硬约束条件硬约束是在排课过程中必须要遵守的约束条件,如果排课过程中无法遵守硬约束条件,则会导致日常的教学计划无法顺利的进行.例如:(1)同一个教师在同一时间段内只能够上一门课,并且教室的性质要和课程要求相吻合;(2)同一个班级在同一时间段内只能够接受一门课;(3)一门课程安排的教室座位数量要大于或等于本门课程上课的人数.1.2 软约束条件软约束条件需要将人体生物规律与排课进行结合.满足软约束条件越多,课表越能让教师与学生满意.例如:(1)尽量将专业课或者难度较大的课程安排在学生思维活跃的时间段;(2)体育课应安排在下午或者上午的第二大节,因为体育课后人体疲惫不适宜安排专业性过强的课程.2 算法概述2.1 遗传算法遗传算法是通过模拟生物界遗传选择和自然淘汰的生物进化过程的计算模型,借鉴了生物界适者生存、优胜劣汰的进化规律,从而演化的随机化搜索方法.遗传算法从一个种群开始,在这个种群中可能存在问题的潜在解,每个种群是由经过编码的N个个体组成,每个个体就是带有一定特征的染色体实体.在每一代中,选择适应度较大的个体进行培育,然后借助遗传学中的遗传算子进行多次组合交叉、变异等操作,产生出代表新的解集的种群.这样经过了多次演化之后得到的种群就可以看作问题的近似最优解.遗传算法的流程如下:(1)随机产生一定数量的初始种群,数量由业务需求定义.(2)对全部个体进行适应度的评估,如果某个个体的适应度已经满足最优化的要求,则输出此个体,并结束计算.否则转向第(3)步.(3)从所有个体中取出适应度较强的个体成为再生个体.(4)依据交叉概率,变异概率生成新的个体.(5)由上述两步交叉和变异产生新一代种群,然后返回第(2)步.2.2 蚁群算法蚁群算法是一个寻找最优路径的方法.蚂蚁在寻找食物的过程中,通过释放信息素留下信息,后面的蚂蚁就会根据路上的信息素来选择路径,信息素的浓度与行走的路程成反比,走的路途越长,信息素浓度越低,则越不容易找到,路途越短,信息素浓度含量越高.随着时间的推移最优路上的信息素浓度越大,最终蚁群会找到一个最优路径.2.3 遗传-蚁群混合算法遗传,蚁群算法是两大仿生算法,都有各自的优势和不足.遗传算法的优势在于在大范围内具有快速全局搜索的能力,但在处理反馈信息时利用率过低,容易过早的收敛,或求解到一定范围时会做大量的无用迭代,从而会降低求解过程中的效率.蚁群算法采用正反馈机制,具有较强的鲁棒性,使搜索过程不断收敛,有更好的全局优化能力.但是在搜索初期信息素分布较少时,求解速率较慢.而排课问题的实质就是一个NP完全问题,影响排课因素的细微变动,尤其是信息量一点点的增加,都会给排课带来“组合爆炸”灾难,当排课规模较大时,单算法在排课问题中就表现出局限性,会出现排课时间较长、排出的课表无法令教师学生满意等现象.因此,本文将两算法结合应用于排课问题中,首先利用遗传算法在大范围内快速的生成信息素分布,再利用蚁群算法求出全局最优解,优势互补,可以减少求解的时间,提高精确率.3 遗传-蚁群混合算法解决排课问题3.1 遗传算法在排课问题中的应用3.1.1 构造基因编码和染色体实施遗传算法的第一步就是对需要解决问题的参数进行基因编码,从而进行相关的遗传操作.本文采用二进制对编码数据进行设计.如表1所示.表1 编码方式教师ID 班级ID 课程ID 教室上课时间3.1.2 适应度函数在遗传算法的进化过程中,其根据适应度函数来确定进化方向.适应度是对课表优劣的一种体现.适应度越大则证明课表的效果越优秀.因此适应度函数直接决定着排课方案的寻优速率和能否找到最优解.所以这就需要制定一个合适的适应度函数(期望).在本文中,课表的期望值可以分为以下三种: 课程离散程度期望,节次优化度期望和特殊课程期望.(1)课程离散程度期望同一门课程安排的时间应该分布均匀,每周安排的时间不能分散也不能太集中.本文将每天的教学时间段分为4个,每周一共20个时间段.用编号相同课程的时差来表示离散程度的大小如表2所示.表2 课程离散程度期望时差 1,2,3,18,19 4,5,15,16,17 6,7,12,13,14 8,9,10,11期望 0.2 0.4 0.6 0.8每一个课程时差对应一个期望,期望函数公式为:(2)节次优化度期望值人体生物钟规律应与教学内容相匹配,逻辑思维活跃的时间段一般在早晨,而下午更容易疲倦所以学习效率较低.根据人体生物钟规律节次的不同的课程期望值也不同,如表3所示.表3 节次优化度期望值节次1,5,9,13,17 2,6,10,14,18 3,7,11,15,19 4,8,12,16,20期望 0.8 0.7 0.5 0.1对于难度比较大的课程就可以安排在期望值高的节次上,对于节次期望值函数的公式为:(3)特殊课程的期望值特殊课程包含体育课与自习课,此类课程最好安排在下午的第二节.当体育课结束后,人体处于疲倦状态,不适于将专业性过强的课程安排在体育课后.如表4对特殊课程给出了不同的期望.表4 特殊课程的期望值节次1,5,9,13,17 2,6,10,14,18 3,7,11,15,19 4,8,12,16,20期望 0 0 2 4对体育课排课就依据上表的期望值为:应将课表中没有课程的时间段安排给自习课.则计算特殊课程期望值的公式为:根据以上分析可得出适应度函数F,如下公式为:式中,K1,K 2,K 3为调控期望值对总期望影响程度的参数.3.1.3 种群操作当形成初始种群,并设计好适应度函数后,下一步就是要进行遗传操作.遗传算法包括三个基本操作: 选择、交叉和变异.(1)选择操作选择操作就是依照适应度的值保留优良的个体,适应度越高证明越近似于最优解.本文中保留优良个体的依据是期望值方法,选择期望值高的个体进行交叉变异操作.(2)交叉操作交叉操作就是把两个个体的部分结构进行替换重组从而产生新的个体.根据选择操作的结果,选择两条染色体作为父代,进行交叉操作.为了防止染色体的结构发生更改,本文的交叉操作只针对教室和上课时间,这样教师和班级都没有发生改变,维持了染色体原本的结构.同时设定交叉概率为 PJ ,若 P J大于随机值r(0＜r＜1),就进行交叉操作.(3)变异操作变异操作能够随机的对个体的局部进行搜索,提高种群的多样化.本文中的变异操作就是对染色体编码中教室和时间段的局部编码进行修改,可以提高染色体的适应度.同时设定变异概率为 P G ,若P G大于随机值r(0＜r＜1),就进行变异操作.3.2 蚁群算法在排课问题中的应用蚁群算法最初用于解决TSP(Traveling Salesman Problem),TSP具有广泛的代表意义,许多问题都可类似的抽象为TSP问题的求解.因此以TSP来描述蚁群算法的模型: 一只蚂蚁要去n个有食物的地区,它先随机选择一个地方作为起点,然后在逐个到达所有地区,留下信息素,最后再返回起点,每个地区只能到达一次,蚂蚁要怎么样选择顺序才能使行程最短.下面建立蚁群算法的数学模型:m为蚁群中的蚂蚁数量;n为问题的规模大小(有食物地方的个数);bi(t)为t时刻位于i地区的蚂蚁数量,故蚂蚁数量为:其中,τ ij(t)为 t时刻路径(i, j)上的信息素;µ ij(t)为蚂蚁从i到j地区的期望程度;pkij(t)为t时刻蚂蚁k从i转移到j的概率.蚂蚁k是根据τ ij(t)的结果来决定该往哪个方向前进,一般会选择τ ij(t)值高的路径,则蚂蚁k在t时刻由i地转移到j的概率为:其中,α为信息启发因子,表示在蚂蚁选择行走路径时信息量的影响;μ为期望启发式因子,表示启发信息对蚂蚁选择路径时产生的影响程度.在每只蚂蚁访问完所有的地区以后,每条路上的信息素浓度会发生变化,因此需要对信息素进行更新.其中,ρ是信息素挥发系数(0＜ρ＜1),1-ρ表示路径残留的信息素量;Δ τij(t)为从i到j地区路上增加的信息素量;Δ τkij(t)为蚂蚁k在i到j地区路上留下的信息素量;Q为表示信息素浓度;Lk为蚂蚁k需要行走的路径长度.3.2.1 蚁群算法的二分图模型当遇到需要用图结构解决的问题时可以使用蚁群算法.在本文中,用蚁群算法解决排课问题,首先需将排课问题用图结构G来描述:上式中, N是图的顶点;S是边的集合; C是边集有关的权值集合.排课问题涉及五个要素,在蚁群算法中这五个要素的关系可转化为“课程,教师,班级”关系与“时间,教师”关系,排课问题就是解决这两个关系所构成的二分图的最大匹配问题.(1)二分图的顶点集定义在本文将“课程,教师,班级”的关系定义为 R LSC,R LSC=L×S×C,R LSC 的元素组成的集合为G LSC,称其为二分图左侧的顶点集.“时间,教室”的的关系为RTR,RTR=T×R,R TR 的元素组成的集合为G TR,为二分图右侧的顶点集.(2)二分图的边集定义在排课中对教室的安排要满足两个要求: 一是安排人数不能大于教室座位数量,二是教室类型满足课程要求.因此,G LSC 与G TR之间只有满足上述两个基本要求的节点才能进行连接.二分图的边集就是G LSC中的节点与G TR中相匹配节点的连线.(3)二分图中边的权值每条边上的权值根据具体课程时间的期望度来构造.例如,较难的专业课嵌入式教师对课程的期望度是上午的第二节课,那么 GLSC中所有嵌入式课程与GTR中时间段为满足上午第二节的所有节点连接的边权值要尽可能的小.通过设置权值,才能更加合理的排出质量高的课表.3.2.2 二分图模型根据上节构造好的二分图模型,蚂蚁都是从左侧GLSC的顶点集出发,根据转移概率的值和边集在右侧GTR 寻找匹配的节点.然后再返回至G LSC进行下一次的搜索工作,如此反复直到蚂蚁为G LSC的顶点集全部安排好上课地点和时间后,一次循环结束.图1 二分图模型图1展示了蚂蚁一次循环的过程,蚂蚁从A1出发,则蚂蚁此次行走的路径为:其中,B1是第一次匹配的终点,A2是第二次匹配的起点,B1和A2可以看成是一个逻辑节点.同理,B4和A3在此次周游中也可以看成是相同的逻辑节点.3.3 遗传-蚁群混合算法在排课问题中的应用本文将遗传与蚁群算法进行混合,首先利用遗传算法生成信息素分布,在利用蚁群算法求出问题的精确解.在遗传算法生成信息素时,为了防止其在收敛后进行无用的迭代,要设置相应的终止条件.在运算工程中,当连续两次运算结果出现的差值小于0.01,或迭代100次,满足其中一个条件时可停止运算并将取得的最优解作为蚁群算法的初始解.蚁群算法在进行100次迭代之后,选择路径最短的解即可作为最优解.遗传-蚁群混合算法对排课问题解决步骤如图2所示.3.4 实验结果及分析为了验证遗传-蚁群混合算法在排课系统中的应用,选取一个学院对排课系统进行测试,该学院的专业数量为6,班级数量为21,约有800名学生,55名教师,22间教室,其中有16名教师对排课有特殊要求,排课单元为202.图2 遗传-蚁群混合算法流程图为了验证遗传-排课算法在排课系如中的实际使用效果,在排课单元为100,400,800的情况下,对遗传-蚁群混合算法、遗传算法、蚁群算法三种算法的排课效果、运算时间及适应度进行了比较.三种算法各测试10组数据后取得平均值.(1)实验参数设置遗传算法的参数设置如下: M=40,PJ=0.4,PG=0.02;蚁群算法设置的参数如下: m =6,α =1,β =4,ρ=0.25 ,Q =8 ,τ max=800 ,τ min=0.01 ,µ ij=1/cij,gen=100. (2)排课效果的比较通过以下四个指标来衡量排课课表的质量,如表5所示.1为违反硬约束的次数;2为一周有两次课程且间隔少于一天的次数;3为难度较大的课程安排在时间段不好的次数;4为教师的特殊要求未满足的次数.表5 排课效果比较排课方案遗传算法蚁群算法遗传-蚁群1 0 0 0 27.6 16.8 10.4 3 24.0 11.3 7.2 4 7.2 4.3 2.1 2如表5可以看出,遗传算法在软约束的冲突方面表现的最不理想,基于遗传-蚁群混合算法排出的课程表,在软约束方面的冲突次数最令人满意,课程表的可行性及质量都要优于单算法排出的课程表.(3)实验结果分析三种算法的平均运算时间如表5所示,平均适应度结果如表6所示.表6 运算时间比较排课单元遗传算法蚁群算法遗传-蚁群100 37 51 44 400 133 185 146 800 529 562 538表7 适应度比较排课单元遗传算法蚁群算法遗传-蚁群100 182 204 238 400 276 290 320 800 301 365 413由表6可得,每种算法随着排课单元的增加,所需要的排课时间随之增加.在排课单元相同的情况下,遗传算法需要的时间最短,而蚁群算法需要的时间最长.由表7可得,三种算法的适应度与排课的单元成正比.当排课单元相同时,遗传-蚁群混合算法的适应度最高.也就证明混合算法排出的课表最优.由此可见,在相同的条件下,遗传-蚁群混合算法排课消耗的时间比遗传算法高一些,但适应度却远远高于另外两个算法.说明混合算法解决排课问题具有良好的时间性能和优化性能.在选择最优课表时,可以将适应度最大的三个课表取出,根据定义排课质量的四个指标,满足软约束条件越多的课表则可作为最终使用的课表4 结论目前解决排课问题可使用的单算法很多,但混合算法却相对较少.本文提出了一种遗传-蚁群混合的排课算法,将两种算法的优势进行了结合.在经过测试后混合算法在运算时间上介于遗传与蚁群算法中间,但适应度高于单算法.混合算法不仅解决了单算法的局限性问题,还在排课效率上有所提高.参考文献【相关文献】1 薛冬梅.充分利用资源科学合理排课.中原工学院学报,2002,13(S1): 97-98.2 杜立智,陈和平,符海东.NP完全问题研究及前景剖析.武汉工程大学学报,2015,37(10): 73-78.3 朱剑冰,李战怀,赵娜.基于混合遗传算法的自动组卷问题的研究.计算机仿真,2009,26(5): 328-331,352.[doi: 10.3969/j.issn.1006-9348.2009.05.084]4 许秀林,胡克瑾.基于约束满足和遗传算法的排课算法.计算机工程,2010,36(14): 281-284.[doi: 10.3969/j.issn.1000-3428.2010.14.102]5 李俊,周虎,李波.基于虚拟蚂蚁的局部优化蚁群算法.控制与决策,1-10.[doi:10.13195/j.kzyjc.2018.0298]6 史文.基于遗传算法的自动排课系统设计与实现[硕士学位论文].成都: 电子科技大学,2013.7 宗薇.高校智能排课系统算法的研究与实现.计算机仿真,2011,28(12): 389-392.[doi: 10.3969/j.issn.1006-9348.2011.12.095]。

遗传算法与蚁群算法的效果比较随着计算机技术的发展，人工智能逐渐成为了一个热门话题。

其中，算法是实现人工智能的基础，而遗传算法和蚁群算法则是两种较为流行的算法。

那么，这两种算法的效果如何呢？今天，我们就来比较一下遗传算法与蚁群算法的效果。

一、遗传算法遗传算法，是一种基于自然选择和遗传进化的优化算法。

遗传算法是通过模仿自然界中的进化过程，不断地变异和选择，来获取优良解的算法。

遗传算法最开始是用来解决复杂的优化问题，如函数优化、组合优化等。

遗传算法实现的过程可以简单地分为三个部分：选择、交叉和变异。

选择是在种群中选择合适的个体，使其能够进入下一代；交叉是通过染色体的重组，产生新的个体；变异是在单个个体的染色体中引入一些随机变异。

遗传算法因其在搜索解空间上的出色表现而得到了广泛的应用。

但是，它也存在着一些问题。

如容易陷入局部最优解、算法计算时间长等。

二、蚁群算法蚁群算法是另一种流行的优化算法，它是一种模拟蚂蚁觅食的行为来处理最优解问题的方法。

蚁群算法的灵感来源于蚂蚁在寻找食物时的行为。

蚂蚁会留下信息素，使得其他蚂蚁找到食物的概率也会增大，从而实现了蚂蚁群体的集体智慧。

蚁群算法的优点在于它能够通过局部搜索来帮助找到全局最优解。

它的本质是通过不断调整问题的搜索关键字而找到最优解。

与遗传算法不同，蚁群算法能够通过一步步的迭代来逼近最优解，因此蚁群算法更适用于某些复杂问题的求解。

但是，蚁群算法存在的问题是需要调整参数才能达到最优解。

同时，蚁群算法对问题的输入比较敏感，也容易陷入局部最优。

三、效果比较上述两种算法都能用来解决优化问题，但具体哪一种优化效果更好呢？不同的优化问题需要不同的算法才能得到更加合适的解决方案。

下面，我们以某个实际问题作为例子，来比较一下这两种算法的效果。

假设有一个工厂需要完成一人任务，可以用五台机器加工。

不同的机器之间的加工时间不同，但是任务需要按照固定的顺序加工才能完成。

我们需要确定哪个工序分配给哪个机器，才能使得任务的加工时间最短。

数学与统计学院智能计算及应用课程设计设计题目：智能计算解决旅行商问题摘要本文以遗传算法、模拟退火、蚁群算法三个算法解决旅行商问题，将三个算法进行比较分析。

目前这三个算法广泛应用于各个领域中，本文以31个城市为例，运用遗传算法、模拟退火、蚁群算法分别进行了计算，将他们的计算结果进行了比较分析。

关键词:遗传算法模拟退火蚁群算法旅行商问题背景：遗传算法：20世纪60年代初，美国Michigan大学的John Holland教授开始研究自然和人工系统的自适应行为，在从事如何建立能学习的机器的研究过程中，受达尔文进化论的启发，逐渐意识到为获得一个好的算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候选策略的群体的繁殖，从而提出了遗传算法的基本思想。

20世纪60年代中期，基于语言智能和逻辑数学智能的传统人工智能十分兴盛，而基于自然进化思想的模拟进化算法则遭到怀疑与反对，但Holland及其指导的博士仍坚持这一领域的研究。

Bagley发表了第一篇有关遗传算法应用的论文，并首先提出“遗传算法”这一术语，在其博士论文中采用双倍体编码，发展了复制、交叉、变异、显性、倒位等基因操作算子，并敏锐地察觉到防止早熟的机理，发展了自组织遗传算法的概念。

与此同时，Rosenberg在其博士论文中进行了单细胞生物群体的计算机仿真研究，对以后函数优化颇有启发，并发展了自适应交换策略，在遗传操作方面提出了许多独特的设想。

Hollistien在其1971年发表的《计算机控制系统的人工遗传自适应方法》论文中首次将遗传算法应用于函数优化，并对优势基因控制、交叉、变异以及编码技术进行了深入的研究。

人们经过长期的研究，在20世纪}o年代初形成了遗传算法的基本框架。

1975年Holland 出版了经典著作“Adaptation in Nature and Artificial System",该书详细阐述了遗传算法的基本理论和方法，提出了著名的模式理论，为遗传算法奠定了数学基础。

蚁群算法与遗传算法的混合算法蚁群算法（Ant Colony Optimization，ACO）和遗传算法（Genetic Algorithm，GA）都属于启发式算法的范畴，它们分别从不同的角度对问题进行建模和求解。

蚁群算法以模拟蚁群觅食行为为基础，通过信息素和启发式规则指导蚂蚁解空间；而遗传算法通过模拟进化过程，利用交叉和变异运算生成新的个体，并适应性地选择个体进行下一代的繁衍。

两者在解决问题时有各自的局限性，因此将两种算法相结合，形成混合算法，可以克服各自的缺点，实现更有效的求解。

蚁群算法具有较强的全局能力，但其速度较慢，且可能会陷入局部最优解。

而遗传算法能够在过程中较快地收敛到局部最优解，但有可能会陷入局部最优解无法跳出。

因此，将两者结合起来，可以同时利用蚁群算法的全局和遗传算法的局部特性。

混合算法的基本思想是，将蚁群算法作为全局策略，用于生成一组较优的解，然后利用遗传算法在这组解中进行局部优化，以寻找最优解。

整个混合算法的流程如下：1.初始化蚁群相关参数和遗传算法的相关参数，包括蚁群大小、信息素更新速率、遗传算法的种群大小、交叉和变异的概率等；2.使用蚁群算法生成一组初始解，并计算每个解的适应度；3.利用遗传算法从初始解中选择适应度较高的一部分个体，作为种群；4.对种群进行交叉和变异操作，生成下一代个体；5.计算下一代个体的适应度；6.如果满足停止条件（如达到指定迭代次数或找到满意解），则输出结果；否则，返回第3步，继续优化。

在混合算法中，蚁群算法和遗传算法的相互作用可以通过以下几种方式实现：1. 优选策略（Elitism）：将蚁群算法生成的一组解合并到遗传算法的种群中，在遗传算法的选择过程中保留一些蚁群算法生成的优秀个体，以避免遗传算法陷入局部最优解。

2.信息素启发式规则：将蚁群算法的信息素启发式规则应用于遗传算法的交叉和变异操作中，以指导交叉和变异过程中的方向，增加遗传算法的全局能力。

基于蚁群算法的双序列比对及其实现作者：李宏周来源：《电子技术与软件工程》2018年第01期序列比对是生物信息学的基础，本文首先分析了基于动态规划的经典双序列比对方法，然后根据蚁群算法求解旅行商问题的思路，将旅行商问题与双序列比对问题简单比较了它们的异同点，并详述了基于蚁群算法的双序列比对步骤，根据双序列比对过程的具体特点，对基本蚁群算法各个参量以及更新公式进行了相应的修改，成功实现了基于蚁群算法的双序列比对过程。

【关键词】蚁群算法双序列比对更新公式序列比对是生物信息学的基础，通过在基因比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。

生物序列比对主要应用在生物信息学上，例如DNA双序列比对其相似性能够反映出两条DNA亲缘关系，实现生物基因识别技术；通过研究病变的生物蛋白序列和正常的序列，能够有效地研究病变机理甚至采取一定的预防措施。

在计算机领域，一般首先是将序列元素用不同的字符表示，一整条序列就可以用字符串来表示，因此，双序列比对问题就是比较两条字符串的相似性。

目前对于双序列比对方法主要是基于动态规划算法有经典的Needleman-Wunsch算法和Smith-Waterman算法，利用一定的打分规则和填充分值矩阵等步骤，可以进行序列的精确比对，主要包括比对和回溯两个过程，需要耗费大量的时间，对于较长序列，需要耗费大量存储空间来存储分值矩阵，因此，经典序列比对算法对机器性能有一定的要求。

对于此种方法的不足，主要有两方面的改进与优化，一是算法上的优化，二是硬件上的优化。

万文利用CUDA 开发平台实现了基于CPU与GPU异构系统来加速Smith-Waterman算法，并且对算法进行了深入分析，设计CPU+GPU的协同并行方案，对应用程序性能与系统性能有显著的提升效果。

夏飞利用FPGA器件结合通用处理器实现了算法加速器，并且设计了细粒度并行算法，成功解决了FPGA逻辑单元和存储资源在进行长序列比对时资源受限问题。

《基于遗传—蚁群融合算法的聚类算法研究》篇一基于遗传-蚁群融合算法的聚类算法研究一、引言随着大数据时代的到来，聚类算法在数据分析和处理中扮演着越来越重要的角色。

遗传算法和蚁群算法作为两种经典的优化算法，各自在聚类问题中表现出良好的性能。

然而，传统的聚类算法往往在处理复杂数据时存在局限性。

因此，本文提出了一种基于遗传-蚁群融合算法的聚类算法，旨在提高聚类的准确性和效率。

二、相关研究概述遗传算法是一种模拟自然进化过程的优化算法，具有较强的全局搜索能力。

蚁群算法则是一种模拟蚂蚁觅食行为的优化算法，具有较强的局部搜索能力和自适应性。

这两种算法在聚类问题中均有所应用，但各自存在局限性。

遗传-蚁群融合算法则是将这两种算法的优势结合起来，以提高聚类的效果。

三、遗传-蚁群融合算法的聚类算法设计1. 算法框架本文提出的基于遗传-蚁群融合算法的聚类算法主要包括三个步骤：初始化、遗传操作和蚁群操作。

在初始化阶段，算法随机生成初始聚类中心；在遗传操作阶段，通过遗传算法优化聚类中心；在蚁群操作阶段，利用蚁群算法优化聚类结果。

2. 遗传操作遗传操作包括选择、交叉和变异三个步骤。

在选择阶段，根据适应度函数选择优秀的个体；在交叉阶段，对选中的个体进行交叉操作，生成新的个体；在变异阶段，对个体进行随机变异，增加种群的多样性。

通过遗传操作，算法可以全局地搜索最优的聚类中心。

3. 蚁群操作蚁群操作主要利用蚁群算法的局部搜索能力和自适应性。

在蚁群操作阶段，每个蚂蚁根据当前的信息素和启发式信息选择下一个聚类中心，并通过信息素的更新机制逐步优化聚类结果。

蚁群操作可以在局部范围内搜索更优的聚类结果。

四、实验与分析为了验证本文提出的基于遗传-蚁群融合算法的聚类算法的有效性，我们进行了多组实验。

实验结果表明，该算法在处理复杂数据时具有较高的准确性和效率。

与传统的聚类算法相比，该算法在聚类效果和稳定性方面均有所提高。

此外，我们还对算法的参数进行了敏感性分析，以确定最佳参数组合。