首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 105 毫秒
1.
分子生物学中基因无方向的反转基因组重排问题在数学上已被证明是一个NP-难问题.目前,较好的算法是Christie(2001)的3/2-近似算法.本文给出一种适合于计算基因无方向的反转基因组重排问题的模拟退火算法,定义了解的邻域结构.数据实验的结果表明该算法性能优于3/2-近似算法.  相似文献   

2.
在推断两个基因组的进化关系上反转排序是一个重要问题。无向排列排序问题已被证明是一个NP-困难问题,目前,最好的算法是3/2-近似算法。基于一个无向排列π的反转距离等于由π所生成的包含2n个有向排列集Sign(π)中最优排列的反转距离,给出应用遗传模拟退火算法计算基因组重排的反转距离的方法。实验结果显示,这个方法优于3/2-近似算法。  相似文献   

3.
在推断两个基因组的进化关系上反转排序是一个重要问题.无向排列排序问题已被证明是一个NP-困难问题,目前,最好的算法是3/2-近似算法.基于一个无向排列π的反转距离等于由π所生成的包含2n个有向排列集Sign(π)中最优排列的反转距离,给出应用遗传模拟退火算法计算基因组重排的反转距离的方法.实验结果显示,这个方法优于3/2-近似算法.  相似文献   

4.
提出一种基于免疫算法的无向排列的反转排序的方法,将一种免疫算子加入到遗传算法的框架中,通过对个体接种疫苗来进一步提升个体的存活能力。数据实验的结果表明,该算法性能优于Christe提出的3/2-近似算法。  相似文献   

5.
货郎问题求解算法分析   总被引:4,自引:0,他引:4  
介绍了求解货郎问题的4个算法:贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解,并对各个算法的性能进行了分析比较。贪心算法的运行速度较快,但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题,其近似性能比(即精确度)分别为:RMST(I)<2,RMM(I)<3/2。回溯搜索算法可以求出货郎问题的最优解,随着城市数目的增加,其搜索效率会下降。  相似文献   

6.
提出一种基于免疫算法的无向排列的反转排序的方法,将一种免疫算子加入到遗传算法的框架中,通过对个体接种疫苗来进一步提升个体的存活能力.数据实验的结果表明,该算法性能优于Christe提出的3/2-近似算法.  相似文献   

7.
讨论多重基因组在移位变换下的一类进化树的重构问题:给定一个由若干基因组组成的集族∏与另一个基因组A,其中所有基因组由同样的一些有向的基因组成,且每个基因组由相同数目的染色体组成,每一个基因在每个基因组中恰好出现一次,所有基因组有相同的尾基因集合,要求构造一个由A到∏的进化树,使得沿此树所发生的移位变换数目最少.给出由一个基因组生成一些给定基因组的近似算法;在一个特殊情况下给出其多项式时间算法.  相似文献   

8.
改进了Garg N和Koenemarm给出的求解具有预算限制的最大并行流问题的近似算法,使得算法求出的目标函数值的近似性由原来的λ≥(1-ε)^3OPT改进为λ≥1/(1+3ε)OPT,更接近最优值,而算法复杂性不变,给出数值例子,验证了算法改进的有效性。  相似文献   

9.
Zheng等给出了一个只含有反转操作的部分排序基因组重组的算法.本文推广了这一结果,给出了允许有删除或插入操作的两个含有不同基因集合的部分排序基因组重组的算法.  相似文献   

10.
满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.  相似文献   

11.
In view of the fact that the problem of sorting unsigned permutation by reversal is NP-hard, while the problem of sorting signed permutation by reversal can be solved easily, in this paper, we first transform an unsigned permutation of length n,π (π1 ,… ,πn), into a set S(π) containing 2^n signed permutations, so that the reversal distance of π is equal to the reversal distance of the optimal signed permutation in S(π). Then analyze the structural features of S(π) by creating a directed graph and induce a new computing model of this question. Finally, an improved genetic algorithm for solving the new model is proposed. Experimental results show that the proposed model and algorithm is very efficient in practice.  相似文献   

12.
考虑的基因组的进化基于两种形式:基因组中染色体之间的移位(translocation)和染色体内部的翻转(reversal).研究了标号基因组间的重组问题:求一个标号基因组进化成另一个标号基因组所需最少数目的移位和翻转,这个数目叫做重组距离.给出了求“共尾”标号基因组间重组距离的一个线性时间算法,从而改进了Hannenhalli和Pevzner的O(n^2)算法,其中n是基因组中基因的个数.  相似文献   

13.
离散加工时间可控的排序问题,得到界为3/2的多项式时间近似算法。  相似文献   

14.
凸二次规划松驰方法研究离散加工时间可控排序问题   总被引:1,自引:1,他引:1  
用凸二次规划松弛方法研究离散加工时间可控的排序问题,得到界为3/2的多项式时间近似算法。  相似文献   

15.
Scheduling unrelated parallel machines with controllable processing times subject to release times is investigated. Based on the convex quadratic programming relaxation and the randomized rounding strategy, a 2-approximation algorithm is obtained for a special case with the all-or-none property and then a 3-approximation algorithm is presented for general problem.  相似文献   

16.
考虑多纤波分复用链网与环网中的利润极大化问题, 分别给出了多项式时间精确算法和2 近似算法. 对于环上各边光纤数目相同的均匀模式, 给出了1.582 近似算法. 这些结果也适用于有向链网与环网.  相似文献   

17.
讨论了互联网信息组织和规划的一个新问题:带拒绝装箱问题,利用原始对偶互补松弛条件给出此问题的一个最优值的下界,利用下界值对应解的性质得到带拒绝装箱问题的一个近似算法.  相似文献   

18.
研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.  相似文献   

19.
多目标激光反导决策优化是激光反导系统的关键技术,其本质上是一个动态最短路问题,但是目前对于寻求该问题的全局最优解存在很多困难,特别是当目标个数大于6时,很难获得全局最优解。针对多目标激光反导决策优化问题引入了一种动态置换算法,包括邻近置换和对称置换,其中邻近置换是在原有解的基础上进行微调,容易进入局部最优解,而对称置换则可以进行大范围的搜索,有利于跳出局部最优解,从而增加了获得全局最优解的概率。以8个目标为例进行了仿真,结果表明所提出的算法比遗传算法收敛速度快。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号