一种求解矩形块布局问题的拟物拟人算法

在VLSI工作中提出了矩形块布局问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法等求解算法。本文以人类上万年以来形成的经验为基础,利用“占角”和“聚类”两个拟物拟人的思想策略,提出了基于最大穴度优先的拟物拟人布局算法。用本文提出的算法,对MCNC、GSRC两个典型测试算例的所有实例进行了实算测试,测试结果表明:计算所得布局结果的优度高,计算时间短。对MCNC和GSRC测试算例,除apte实例外,其它所有实例均得到了最优解,而计算时间都在10秒以内。与CBL算法、遗传算法和号称当今最好的CompaSS算法相比,本文算法所得结果的优度更高,计算时间更短。进一步的测试表明,本文提出的拟物拟人布局算法为当今的一种高效算法。

一种求解多维0-1背包问题的拟人算法

在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法,蚁群算法及其它一些启发式算法等求解算法。该文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法,对55个测试算例进行了实算测试,得到了其中54个算例的最优解。测试结果表明,用该文提出的拟人算法求解多维0-1背包问题,计算结果的优度高,计算时间短,是求解此问题的有效算法。

求解正交数组问题的拟物拟人算法

此工作是方开泰工作的继续 .正交数组在制造业和高技术产业的试验中有着广泛的应用 .目前正交数组构造的研究相当活跃 .现有的许多构造方法很复杂且所能构造的类型有限 .提出了一个构造正交数组简单而有效的方法——拟物拟人算法 .应用该算法已经独立地得到了一些历史上尚未发现的 L2 7(31 3)的不同构数组 .

求解TSP问题的拟人算法

基于贪心算法提出了一种改进的求解旅行商问题(TSP)的拟人算法。该算法采用邻域定义,主要思想是:给定一个所有城市的全排列,依此全排列的指挥用贪心算法生成一个回路。通过城市交换和城市序列平移,在当前的邻域中搜索比它更好的解,如能找到如此的解,则使之成为新的当前解,然后重复上述过程。在搜索的过程中,采取跳坑策略以跳出局部最优解,始终向目标最接近的方向搜索。算法结果与Rego提出的完全子路径搜索算法(F-SEC)做比较。

一种求解矩形块装填问题的拟人算法

在货物装载、木材下料、超大规模集成电路(VLSI)设计等工作中提出了矩形块装填与切割问题,对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验,提出了一种求解矩形块装填问题的拟人算法。该算法使用了两个主要的思想策略,即矩形块选择策略和矩形块放置策略。用本文提出的算法,对21个测试算例进行了实算测试,测试结果表明:算法所得装填结果的优度高,计算时间短。对这21个测试算例,用本文算法计算,得到了其中16个算例的最优解,而计算时间都在2秒以内。进一步的测试表明,本文提出的算法对求解矩形决装填问题十分有效。

求解蛋白质结构预测问题的三维连续模型及其相应的拟物拟人算法

提出了蛋白质结构预测问题的三维欧氏空间连续模型,为由此形成的数学问题找到了相应的物理模型,进而找到了相应的拟物拟人算法。

解不等圆 packing 问题拟物拟人算法初态选取

提出形式化了的人工经验方法，由此得出的算法可以极快速地为不等圆填装（ｐａｃｋｉｎｇ）问题求出初始近似解．将此初始近似解作为求解不等圆ｐａｃｋｉｎｇ问题的拟物拟人算法中的初态，可以提高这种拟物拟人算法的计算速度约１０倍．此种方法还有可能发展为关于求解ＮＰ难问题的不仅具有高速度而且具有高精确度高完整度的具有实用价值的纯粹拟人方法．

蛋白质结构预测的拟物拟人算法研究

根据国际上最新提出的蛋白质结构预测问题的三维欧氏空间连续模型,找到了相应的物理模型,并且设计了适当的拟人策略,形成了相应的拟物拟人算法。

求解非格点模型的蛋白质结构预测问题的拟物拟人算法

本文研究了一个具有两种氨基酸(疏水氨基酸和亲水氨基酸)的三维非格点的蛋白质模型.受物理世界的物体间相互作用的规律和人类社会生活经验的启发,给出了该模型蛋白质结构预测问题的拟物拟人算法.计算结果表明被提出的方法在非格点的蛋白质模型上是有效的.与文献中给出的所有算例的结果相比,无论是在最低能量值还是在计算时间上,本文算法都要好.对于这些算例中规模最大的3个,还找到了与文献中结构完全不同的最低能量构形.

无线网络中寻找非干扰不相交路径的拟人算法

针对无线网络中寻找从源点s到汇点t的两条非干扰不相交路径这一NP难问题,提出了一种拟人算法。该算法首先基于网络流方法得到两条点不相交的s-t路径,然后通过一种拟人化的策略逐步调整这两条路径,力图使得它们变为两条非干扰不相交的s-t路径。模拟实验表明,与现有的算法相比,拟人算法可以快速地以更高的概率找到两条长度较短的非干扰不相交路径。

预测蛋白质结构的拟物拟人算法

根据国际上最新提出的蛋白质结构预测问题的三维欧氏空间的连续模型,找到相应的物理模型,并形成了相应的拟物拟人算法。

一种求解二维矩形Packing问题的拟人型全局优化算法

针对二维矩形Packing问题,提出了基于占角动作的基本算法。以基本算法为基础,提出了三阶段优化的拟人型全局优化算法。在第一阶段生成初始布局。在第二阶段交替调用邻域搜索子程序和跳坑策略子程序对矩形块的优先级排序进行优化。邻域搜索采用交换式和插入式两种邻域结构,避免单一邻域结构的局限性。当搜索遇到局部最优解时,采用跳坑策略子程序跳出局部最优解,将搜索引向有希望的区域。在第三阶段调用优美度枚举子程序对占角动作的选择作进一步优化。提出了两条优度定理。对于六组benchmark测试用例的实验结果表明,算法的整体表现优于当前文献中的先进算法。针对矩形块方向固定的情形,算法对zdf6和zdf7两个问题实例得到了比已有文献记录更优的布局。

求解SAT问题的拟人退火算法

该文利用一个简单的变换 ,将可满足性 (SAT)问题转换为一个求相应目标函数最小值的优化问题 ,提出了一种用于跳出局部陷阱的拟人策略 .基于模拟退火算法和拟人策略 ,为 SAT问题的高效近似求解得出了拟人退火算法 (PA) ,该方法不仅具有模拟退火算法的全局收敛性质 ,而且具有一定的并行性、继承性 .数值实验表明 ,对于本文随机产生的测试问题例 ,采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际上流行的 WAL KSAT算法 。

数字微流控生物芯片布局的拟人遗传组合算法

数字微流控生物芯片布局问题是芯片设计的关键问题,它是在二维微流控阵列上为每个操作布局一个合适的物理位置,以达到完成所有操作的微流控阵列总面积最小和总时间最短两个目标。构建了拟人遗传组合算法,应用拟人启发式算法来控制数字微流控模块的布局过程,用遗传算法对布局结果进行多目标优化,以多元体液检测为实例,模拟了数字微流控生物芯片的布局优化过程。实验结果表明该算法不仅达到了优化目标,且优于并行混合模拟退火算法。

求图符号控制数的拟人退火算法

为确定图符号控制数的问题提出了几个拟人的求解策略,并基于模拟退火算法和拟人策略,为该问题得出了一个拟人退火算法PA-SDN.实验结果表明,算法PA-SDN能快速收敛到问题的高质量解.

基于拟人策略的高校排课算法研究

排课问题早在70年代就被证明是一个NP完全问题,即算法的计算时间是呈指数增长的,这一论断确立了排课问题的理论深度。对于NP完全问题,目前在数学上还没有一个通用的算法能够很好地解决。拟人策略算法结合了多种高校排课算法实例和多年的实际排课经验,与其它算法相比,有效地避免了以往算法的高时间复杂度和高空间复杂度,简单易行,便于程序实现。

二维Packing问题拟人型算法中的动作空间更新过程求解

二维矩形Packing问题备受关注。对于这一问题,有学者提出了拟人型穴度算法。该类启发式算法极大提高了解决二维Packing问题的效率,其引用了动作空间的概念。此类算法中的基本算法B0旨在通过制定的指标选出每一次放置的矩形块及其矩形块放置的位置,待选出后完成矩形块放置动作,再进行动作空间的更新操作,以此类推,只至最终格局。基于此,详细解释了算法中动作空间的更新过程。

无线传感器网络区域覆盖的拟物拟人优化方法

建立了以节能为目标的无线传感器网络(WSN)区域覆盖优化模型,指出此模型是一个具有指数复杂度的NP问题,针对问题特点设计了三条拟物拟人策略,分别是"拟万有引力"模型、"拟库仑力"模型和"共同富裕"模型.以此为基础,设计了一个拟物拟人算法(QPQSA),此算法是一个基于节点局部信息的分布式迭代算法.仿真结果显示,对于边界复杂的目标区域,无线传感器网络可由随机初始覆盖出发,经过自组织移位调整和功率控制达到一个优化的覆盖方案,经过优化,网络寿命延长了45.03%,覆盖率从72.28%提高至98.79%.

混合粒子群算法求解多维背包问题

提出了一种求解多维0-1背包问题的混合粒子群算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪策略和基于二进制编码的粒子群算法.用提出的算法,对55个测试算例进行了测试,得到了全部算例的最优解.测试结果表明,提出的混合粒子群算法求解多维0-1背包问题,计算结果的优度高,时间短,是求解此问题的有效算法.

一种可满足模理论的拟物优化求解算法

为了研究改善可满足性模理论的求解效率,本文基于拟物方法结合萤火虫优化算法,设计出新的优化求解方案。实验结果表明,使用萤火虫优化算法求解可满足性问题在特定应用案例上效果显著,基于Benchmarks(可满足模理论求解器公开基准测试案例库)的基准测试案例中求解效率平均比纯拟物拟人算法上提高至少10%的性能。基于拟物方法结合最优化算法在特定领域的可满足性求解算法不仅容易实现,同时能有效提高求解效率。