Memetic算法及其在分类中的应用研究

群体智能优化算法Memetic算法(Memetic Algorithm,MA)采用进化算法的操作流程,引入局部搜索算子,使其在问题的求解中保证较高收敛性能的同时又能获得较高质量的解,克服了遗传算法等传统全局优化算法易"早熟"的问题,同时避免陷入局部解。在MA框架基础上,提出了全局动态适应MA算法,采用遗传算法为全局搜索算子,k-means算法为局部搜索算子。使用Java语言实现算法并对UCI中分类实验数据集进行测试,结果表明,将遗传算法和k-means结合的全局动态适应MA在分类问题中具有较高准确率。     

SIGA:一种新的自适应免疫遗传算法

为了克服传统遗传算法收敛速度慢和容易陷入局部最优的不足,提出了一种新的自适应免疫遗传算法SIGA（Self-adaptive Immune Genetic Algorithm）。新算法对遗传算子进行改进,提出了自适应交叉和变异算子,保证了种群多样性和防止早熟现象发生;为了使免疫算子兼顾个体多样性和提高种群个体适应度的水平,提出了基于相似性矢量距离的免疫选择算法。实验表明,与传统的遗传算法和免疫算法相比,该算法收敛速度提高了3～90倍,求解精度达到10^-3,并有效地抑制了早熟现象。     

利用基因重组策略改进遗传算法

为了克服标准遗传算法的早熟现象，提高遗传算法的全局收敛性，提出了一种基于基因重组策略的遗传算法。该算法定义了一种新的交叉算子，即移位逻辑交叉算子(包括蝶形移位交叉算子和洗牌移位交叉算子)，用它们对染色体的部分基因实现有规律的交叉重组。实验结果表明，该算法比经典的遗传算法具有更好的收敛性和稳定性。     

一种考虑环境作用的协同免疫遗传算法

在综合考虑了环境对生物进化的影响、免疫算法的结构以及遗传算法部分算子的基础上,提出一种考虑环境作用的协同免疫遗传算法(ESIGA),以实现提高算法搜索速度和全局搜索能力的目标.在该算法中,设计了克隆环境演化算子和自适应探索算子,并构造了3个子种群协同进化以发挥克隆环境演化算子的影响,从而提高算法的全局搜索能力.引入的自适应探索算子和克隆环境演化算子,使算法具备了一定的学习能力,可加速搜索和防止早熟.构建的主种群和协同种群相互影响,使得算法对环境具有改良能力,加强了克隆环境演化算子的性能,而精英种群则加强了算法在优质个体邻域的搜索能力.采用13个常用无约束优化问题测试函数对算法做了检验,测试数据表明:ESIGA算法与正交遗传算法相比,其搜索速度要快于正交遗传算法1～2倍,并能够处理1 000维的高维优化问题.     

基于改进遗传算法的模糊聚类研究及应用

模糊C-均值聚类算法是一种局部搜索算法,采用迭代的爬山技术,对初值敏感易陷入局部最小值。遗传算法是一种全局优化算法,能够克服模糊C-均值聚类算法陷入局部最小值的问题,但遗传算法收敛速度慢,易早熟。应用小生境思想对遗传算法进行了改进,以保护种群中基因的多样性,设计了基于最短距离的算术交叉算子、边界变异算子及双精英种子参与进化的策略。仿真实验结果表明,改进后的算法能够提高模糊聚类的收敛速度和聚类质量。     

一种改进的遗传算法求解TSP问题

提出一种基于顶点的候选表进行交配的遗传算法(Candidate Crossover Genetic Algorithm,CCGA)求解旅行商问题(TSP).遗传算法(GAs)是一种广泛使用的全局优化算法,并且已经成功地用于求解TSP.但是传统的遗传算法的交配算子缺乏指导性和启发性,交配算子随机的选择父体基因进行交配,导致GAs求解速度慢、解的精度不高等不足.通过分析TSP问题本身的特征,给出了一个使用已有的邻接边的信息和路径信息生成顶点的候选表,然后基于顶点的候选表进行交配的交配算子,使用该交配算子的遗传算法在求解TSP问题时性能上得到了很大的提高,通过TSP Lib上的测试样例将该CCGA和传统的遗传算法进行比较.比较结果表明CCGA具有更大的优势,它能使算法求解到近似最优解和最优解只存在很小的偏差.     

用遗传算法求最小生成树

以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了＂无性生殖＂的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树.     

加强的混合遗传算法求解能力约束弧路径问题

为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA). 该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力. 同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较. 结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.     

基于免疫遗传算法的物流运输求解

针对传统遗传算法的缺陷，提出了结合免疫系统原理和遗传算子自适应调整的方法，即免疫遗传算法．该算法可防止算法未成熟收敛、保证种群的多样性，在使用此算法搜索最优解时，可防止陷入局部寻优情况的出现．通过对一个运输实例的求解，证实算法可达到预期的效果．     

一种新的自适应免疫遗传算法

 为了克服传统遗传算法收敛速度慢和容易陷入局部最优的不足,提出了一种新的自适应免疫遗传算法SIGA(Self-adaptive Immune Genetic Algorithm)。新算法对遗传算子进行改进,提出了自适应交叉和变异算子,保证了种群多样性和防止早熟现象发生;为了使免疫算子兼顾个体多样性和提高种群个体适应度的水平,提出了基于相似性矢量距离的免疫选择算法。实验表明,与传统的遗传算法和免疫算法相比,该算法收敛速度提高了3~90倍,求解精度达到10^-3,并有效地抑制了早熟现象。     

基于遗传算法的序列比对方法

为有效解决大尺度基因组序列的比对分析,提出了一种基于遗传算法的序列比对方法。该算法通过对序列比对问题进行编码,将其转换成了搜索空间中的一个优化问题。实验结果表明,这种新的比对算法是有效的,它在占用少量内存的情况下可以获得近似于Need lem an-W unsch算法结果的最优解。     

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

多重序列比对问题是复杂性较高的困难问题.基于蚁群算法的多重序列比对方法能够在合理的时间内找到得分接近参考比对的多序列比对解.但是,随着序列的加长,蚁群算法对于长序列的比对效果并不是很理想.本文提出一种基于遗传算法和蚁群算法的多重序列比对方法.该方法利用遗传算法对长序列分段,利用蚁群算法对分段后的序列进行求解,然后直接将各段的结果进行拼接即可.     

mRNA序列与蛋白序列对比

生物序列的对比是计算生物学中的一个基本问题．目前已有许多算法对DNA序列或蛋白序列之间进行对比,多是对同种生物序列进行对比．为得到mRNA序列和蛋白序列之间的对比,采用动态规划算法,提供了寻求mRNA序列和蛋白序列的局部对比和全局对比,解决了核酸与氨基酸之间的对比问题．算法的时间复杂度为O(nm)．     

基于A*算法的启发式算法求解多序列比对问题

通过分析动态规划算法及A^*算法的特点，针对多序列比对问题提出一种基于A^*算法的启发式算法。该算法采用了多个优化搜索机制。通过对此算法的理论分析，证明了它能够在有效地减小搜索的空间、节约搜索的时间的同时，保证得到比较好的比对结果。此算法不仅能够在多序列比对问题中得到应用，还能够用于其他有向无环图的最短路径问题的求解。     

一种新的视频质量评价中帧对齐算法

在全参考或者部分参考的视频质量评价算法中,由于视频序列在传输过程中总会存在丢帧、跳帧、停滞等现象,因此在视频质量评价之前进行的帧对齐处理是非常重要的步骤.提出了一种新的帧对齐算法,该方法在国际电信联盟(ITU)的ITU-T J.244和J.247的基础上,对源视频和劣化视频序列进行预处理和相关特征参数的提取,并采用类似滑动窗口的原理对二者进行相似度的运算,根据运算结果可判断是否达到帧对齐.结果表明,该方法可以明显甄别出视频序列相应帧的对齐情况,算法简单、实时性较好,具有一定的实用价值.     

针对基因选择性剪接的多序列比对算法研究

为对真核基因的选择性剪接形式进行准确、快速、有效的研究 ,提出了一种启发式多序列比对算法。该算法借助引导树启发序列之间的两两段对段比对 ,通过建立序列相似性估计模型 ,给出了一种由序列间相同词数估计序列相似程度的方法。利用这种方法构造引导树 ,大大缩短了其构造时间。通过采用序列间的段对段比对 ,克服了间隙罚分问题 ,更准确地反映了真核基因的选择性剪接形式。引导树构造方法的改进和快速局部比对算法的采用 ,使得算法运行速度大大高于一般算法。该算法为真核基因的选择性剪接研究提供了一种新的有效途径     

基于阶段变异的PSO组播路由算法

理论上已证明组播QoS(Quality of Service)路由问题是一NP完全问题。集群智能算法为此类问题的求解提出了新的思路。在进行基于粒子群优化(PSO)的QoS组播路由算法研究的基础上,分析了基本粒子群易陷入局部最优路由而导致停滞的现象,通过引入变异算子,阶段变异的机制,克服了标准PSO算法的缺点。仿真结果显示了算法的可行性和有效性。     

基于超平面及遗传算法优化的网格简化

基于对目前反求工程中已有方法的分析，引入超平面的概念；通过对三角网格曲率的离散化计算，经过种子点的生长以及区域合并形成超平面。在对超平面删除后留下的空洞进行重新三角化时，利用遗传算法生成具有空间形状优化的简化模型。在此过程中以一种新的编码方式使遗传算法能够适应网格优化的特殊性；通过对变异算子的修改，保证遗传进化的有效性；将交叉算子放弃，避免了新产生的三角网格和已经存在的网格重叠和相交。通过这种方法可以调节形状的优化程度和侧重度。     

Anchor-based English-Chinese Bilingual Chunk Alignment Model

Introduction Withtheincreasingdevelopmentofcorpuslinguistics,Example basedMachineTranslation(EBMT)hasbeena viabletrendinrecentyears[1,2].Thetranslationprocedure intheEBMTsystemconsistsgenerallyofthreesteps:First,asource languagesentenceisshallowlyparsedintoa sequenceofchunks;thenthebesttranslationsforthese chunksareselectedfromtheparallelchunk alignedcorpus accordingtotheircontexts;finallytheselectedtranslation chunksarecombinedintothetarget languagesentence.Thisapproachcircumventstoughpr…