DNA折纸术在0-1整数规划问题中的应用

DNA折纸术是自组装在纳米技术方面的应用,具有构造几乎任何复杂二维纳米级图形的能力。文中将DNA折纸术应用于求解0-1整数规划问题,构造约束条件中变量的特殊DNA链,使其与初始数据池中的DNA链发生杂交反应形成二级结构。根据反应后DNA链长度不同的特点,用凝胶电泳操作分离出不满足条件的DNA链,从而得到问题的解。与以往的DNA计算模型相比,该模型的并行性得到了大幅度的提高,通过逐步缩小解空间,减少了实验操作的复杂度,可以解决变量更多、更为复杂的0-1规划问题。     

基于DNA链置换的可满足性问题的计算模型

可满足性问题是经典的NP完全问题之一。本文建立了一个基于DNA链置换的可满足性问题的计算模型,可满足性问题的约束条件被映射成计算模型上的荧光个数,将可满足性问题中变量的两种取值(0和1)分别设计成不同的DNA链,通过DNA链置换反应,最后观察反应后的计算模型上荧光个数找出可满足性问题的可行解。该模型具有操作简单,结果便于观察和检测的优点。     

利用DNA链的相对浓度求解背包问题

对于含有n个变量的0-1背包问题,提出了利用DNA链的浓度来判断某种0-1组合是否为可行解的计算模型。该计算模型编码了3n-3种寡聚核苷酸片断,并利用这些编码合成对应于约束条件的、不同浓度的2n-3种DNA链,作为数据池。随后,表示该0-1组合的DNA链被加入到数据池诱发链置换,根据可行解不会产生荧光来并行地搜索所有可行解。最后将可行解对应的目标函数加以比较,最终得到背包问题的最优解。结果表明,该模型的空间复杂度为O(n),时间复杂度为O(1)。模型的优点是计算过程可自动进行,中间结果无需分离,无需人工干预,可靠性高。因此DNA计算求解问题的规模得以大大增加。     

0-1整数规划问题的巨磁电阻型DNA计算模型

给出了基于GMR(巨磁电阻)型DNA芯片技术的0-1整数规划问题的DNA计算模型。将问题的变量编码成DNA链,在GMR型芯片表面固定DNA探针,然后将被生物素标记的待分析目标DNA链与探针进行充分杂交,通过芯片上的GMR传感器对芯片上纳米磁珠的检测,以电信号方式输出,得到问题的解,避免了荧光分析中的信号转换而引起的失真。该模型具有较高灵敏度,信号检测和分析较为简单,对信号检测设备要求较低。     

0-1整数规划问题的DNA四面体步行者计算模型

DNA折纸术是一种新型的自组装方法,广泛应用于DNA计算中。基于DNA折纸术设计了一个DNA四面体步行者,并将DNA四面体步行者应用于求解0-1整数规划问题。通过DNA四面体步行者的行走,来找出所有可能解。最后,通过DNA四面体步行者所携带的纳米金颗粒的个数来判断是否是0-1整数规划问题的可行解。该模型求解错误率低,具有很强的可控性和实用性。     

一类特殊整数规划问题的DNA计算

通过22种荧光标记DNA链的办法,在基于表面方式的实验环境中,将变量用变异的二进制变量组来表示,提出一种基于DNA计算的特殊整数规划问题的求解算法.算法通过将上述问题转化为特殊的-1-0-1规划问题,解决了运筹学中特殊的整数规划问题,并为最终解决一般的整数规划问题奠定了基础.     

一种改进的遗传退火算法以及收敛性分析

针对一种约束条件既有0-1变量又有整数变量的非线性混合整数规划模型,给出一种改进的遗传退火算法求解,并建立对应的Markov链且理论证明其收敛性.     

基于杂交链式反应工序问题的DNA计算模型

杂交链式反应是一种无酶参与的自主组装反应.文章利用杂交链式反应和折纸术给出工序问题的求解过程.首先,将工序问题映射为一个有向图,将调整时间之和t+(Ji)最小的点作为根节点,将问题映射为一个有向树.然后,将有向树锚定在矩形的折纸基底上,利用杂交链式反应来求解问题的最优解.此模型在试管中进行,只有加入了启动链以后,反应才可进行.当发夹结构打开后,反应是不可逆的,最终生成的都是以根节点为起点,以叶子为终点的有向路径.最后,利用荧光光谱仪检测每条有向路上的荧光个数,从而确定问题的最优解.通过仿真可得该模型的复杂度为Θ(depth(T))+Θ(n).     

对求解整数规划方法的新探索

借鉴分枝定界法求解整数规划的基本原理和目标排序法求解0-1规划的思路,在完成一系列理论分析和证明之后,提出求解整数规划的简捷有效的新方法-松驰最优解邻域整点搜索法。     

0-1型整数规划解法刍议

用穷举法和隐枚举法解0-1型整数规划问题时,常常遇到组合爆炸问题。本文从约束条件入手直接给出某些变量的值,从而将减少了运算次数有效的改善了这一问题。     

枚举可行解寻优法——在黄浦江污染治理规划系统分析中的应用

一、引言在黄浦江上游工业区水污染治理规划的系统分析中,我们开发了一种“枚举可行解寻优”的算法来求解系统分析中的0-1型整数规划模型。求解0-1型整数规划问题,常用“隐枚举法”虽然隐“枚举法”被认为是一种标准的算法,但它也有不足之处。在求解变量和约束条件较多的中、大型规模的问题时,花费的计算机时间较多。整数规划理论在应用于实际工作时所建立的模型,常常由于一些物理或技术上的约束因子,使得模型都有自己的特性。在求解问题时,利用这些特性往往能收到事半功倍     

求解线性0-1规划的一种连续化方法

线性0-1规划作为一种特殊形式的整数规划,在科学和工程问题中有许多应用.基于拉格朗日松弛方法,提出求解线性0-1规划的一种连续化方法.该方法不仅给出了原问题显式形式的对偶函数,而且对偶变量的数目仅等于原问题部分约束的个数,原来的线性0-1规划问题被转化为只有简单约束的普通优化问题,极大地方便了工程应用.以背包问题为例进行的数值实验表明,该方法是求解线性0-1规划的行之有效的实用方法.     

求解混合整数线性规划的降维搜索法

很多实际问题归结为解如下线性规划max C~TX AX=b (1) {X≥0 其中X=(x_1,…x_L,x_(L 1),…x_n)~T的x_1…x_L 为整数。降维搜索法求解这个问题,首先是从(1)的约束中除掉x_1…x_L为整数的要求,求出线性规划的最优解。此解若不为整数解,则从解的分量x_1开始取整,即令x_1=[x_1~(0)] 代入约束,在n-1维空间上求最优解。如果仍不是整数解,则继续在n-1维最优解中令分量x_2取整,求n-2维空间的最优解。若降维至n-r得一整数解,则依定理1,停止继续降维。此时的整数解为(1)的可行解。然后在此可行解的基础上在x的两边进行左右搜索,用新的更优的可行整数解代替原有的可行整数解。用定理(2)和(3)判别是否停止搜索,搜索完毕便得n-r 1维(1≤r≤L)的一个最优整数解。然后求出所有n-r 1维的最优整数解,比较所有n-r 1维的最优解,得n-r 2维的一个最优整数解,如此类推,一定可求得原问题(1)的最优整数解。降维搜索法可以完全平行地推广到求非线性规划的整数解。     

自动优化露天矿短期进度计划的渐进细化法

分析了露天矿生产计划技术现状,提出计算机辅助设计法与数学规划法有机结合是制定露天生产进度计划的最佳手段.针对整数规划和具有前后时段顺序的0-1整数规划在露天矿生产进度计划应用中存在的问题,提出了渐进细化的生产进度计划优化方法,论述了渐进细化过程,建立了相应的0-1整数规划模型.在VC++环境下通过调用LindoAPI实现模型求解,该细化0-1整数规划方法,较前后时段0-1整数规划方法提高了计算速度,满足设计细化需要.     

汽车涂装中虚拟重排序问题建模与求解

针对汽车涂装中的虚拟重排序问题,建立了关于颜色转换次数最少的0-1二次整数规划模型.根据0-1变量的特点,把该0-1二次整数规划转化为以相邻颜色个数最大为目标的0-1线性整数规划,从而使得所建立的虚拟重排序模型可直接用现有优化软件求解,无须设计专门解法.所建模型在任何虚拟重排序场合均可采用或借鉴.     

双编码方式求解整数规划问题的DNA算法

DNA计算是以DNA分子作为数据的一种新型计算模式,在DNA计算中首要面对的问题是编码问题。文中提出了一种双编码方法,利用这种编码方法使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作。基于该编码方法所建立的DNA计算模型可用于求解整数规划问题,只需有限的几次PCK反应即可读取问题的可行解。与其他DNA算法相比,该算法具有操作简单、易于实现的优点。     

0-1整数规划问题的稀疏解求解模型研究

本文研究了0-1整数规划问题的稀疏解的求解模型,运用线性互补约束得到了该问题的连续优化模型,并运用最优性条件考虑了两个模型解之间的关系,为模型的进一步求解和算法设计提供了理论的基础和保证.     

基于0-1整数规划模型的水坝选址问题

针对赞比西河卡里巴大坝存在的问题,提出了一种应用于大坝选址的新方法,用于求解出大坝的具体位置和数量.该新方法运用了0-1整数规划,以低成本、高安全系数为目标,建立多目标0-1整数规划模型,并运用lingo软件求解出在赞比西河流域建立水坝的具体位置与数量.所建立的新多坝系统不仅可以满足赞比西河流域基本的水利用情况,而且还可应对一些突发的自然灾害.此法不仅克服了其他选址方法中数量单一、位置不明确等缺点,且具有原理简单、计算量小等优点.另外,还可将此模型用于其他选址问题上.     

凸整数规划问题的混合蚁群算法

混合蚁群算法是基于群体的一类仿生算法, 适合于解困难的组合最优化问题. 本文对其做适当改进, 用于解凸整数规划问题. 结果表明: 用该算法求目标函数为正定二次型的整数规划问题的最小值, 找到的解比多起始点局部搜索方法好得多, 比原来的混合蚁群算法找到更好的解     

自适应粒子群优化的AdHoc网络多播路由算法

针对AdHoc网络中带QoS约束的多播路由问题,提出了一种自适应粒子群优化的AdHoc网络多播路由算法（APs0）,将微粒在解空间中的飞行搜索过程映射为多播树的树形变换过程．构建了AdHoc网络中QoS多播网络模型,采用罚函数处理约束条件来设计适应度函数．描述了APSO算法求解AdHoe网络多播路由问题的实现过程,将QoS多播路由优化问题转化为整数计算问题．仿真结果表明：该算法能快速地找到针对AdHoc网络中满足qos要求的最优多播树,尤其在大规模网络下更能显示该算法的有效性和可靠性．