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

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

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

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

基于欧氏距离的矩形Packing问题的确定性启发式求解算法

使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.     

求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计,裁缝裁剪布料,玻璃切割等工作中提出了矩形和圆形装填问题,即把不同大小的矩形块和圆饼装入一个矩形容器中,以最大化容器的面积利用率为优化目标。对这一问题,可采用模拟退火,遗传算法等国际流行算法进行求解,但这些方法计算时间较长,计算结果的优度也不甚理想。利用人类的智慧和经验,提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％,平均计算时阊为8．38s。测试结果表明,算法对求解矩形和圆形装填问题是行之有效的。     

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

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

求解不等圆布局问题的一类遗传算法物方法

在已有求解不等圆布局问题算法的基础上 ,根据问题特点提出了一类遗传算法 ,通过将拟物方法与标准遗传算法结合使用 ,较好地解决了对布局优化函数进行全局最优求解的问题 最后通过实例计算验证了本算法的有效性 .     

求解矩形packing问题的贪心算法

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。     

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

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

一种求解集合覆盖问题的启发式算法

集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.     

求解VLSI布局问题的启发式算法

在人们现实布局实践经验的启发下。对 VLSI 布局问题提出了一个启发式算法。该算法由定序规则和定位规则组成,定序规则用来确定布局物体放入布局空间的先后顺序,定位规则规定每一布局物体都被当前最优的占角动作放入布局空间。对5个 MCNC 算例的测试结果表明,本文算法与基于 O-tree 表示的算法相比,速度提高15～56倍;对于其中4个算例,面积利用率提高0.95%～5.31%。     

一种有效的面向软模块的VLSI布图规划算法

随着VLSI设计规模和复杂度的提高,以可复用IP为代表的软模块得到了广泛的应用,针对软模块的布图规划问题随之变得日益重要。基于正则波兰表达式（NPE）表示,提出了一种形状曲线相加算法来处理软模块之间的组合运算,可获得每个布图解下最优的布图实现。通过回溯算法来确定每个模块的位置及形状,并将它们集成到模拟退火算法的流程之内。应用MCNC和GSRC电路对算法进行了测试,结果表明该算法解决软模块的布图规划问题是可行和有效的。     

Fixed-outline floorplanning using robust evolutionary search

Typical floorplanning concerns a series of objectives, such as area, wirelength, and routability, etc., with various aspect ratios of modules in a free-outline regime. However, in a hierarchical design flow for very large ASICs and SoCs, a floorplan can be completely useless for a situation where its outline is dissatisfied. In this paper, we study the fixed-outline floorplanning problem that is more applicable to the hierarchical design style. We develop an efficient algorithm based on robust evolutionary search and achieve substantially improved success rate. We also propose a new approach to handle soft modules to further adjust the generated floorplan to fit into the prescribed chip outline. The effectiveness of our methods is demonstrated on several large cases of MCNC and GSRC benchmarks.     

A PSO-based intelligent decision algorithm for VLSI floorplanning

Floorplanning is an important issue in the very large-scale integrated (VLSI) circuit design automation as it determines the performance, size, yield and reliability of VLSI chips. This paper proposes a novel intelligent decision algorithm based on the particle swarm optimization (PSO) technique to obtain a feasible floorplanning in VLSI circuit physical placement. The PSO was applied with integer coding based on module number and a new recommended value of acceleration coefficients for optimal placement solution. Inspired by the physics of genetic algorithm (GA), the principles of mutation and crossover operator in GA are incorporated into the proposed PSO algorithm to make this algorithm to break away from local optima and achieve a better diversity. Experiments employing MCNC and GSRC benchmarks show that the proposed algorithm is effective. The proposed algorithm can avoid local minimum and performs well in convergence. The experimental results of the proposed method in this paper can also greatly help floorplanning decision making in VLSI circuit design automation.     

基于切分结构的快速布图规划算法

分析了切分(Slicing)结构的布图产生空白面积的原因,提出了一种直观、快速的确定模块方向的方法,改进了正则波兰表达式的一个邻域构造算子,并采用模拟退火算法实现了Slicing结构布图规划。对MCNC和GSRC的标准电路进行了测试,结果表明所提出的算法在解决Slicing结构的布图规划方面是有效的。     

基于拟人策略的带有预放置模块的布局算法

在超大规模集成电路设计中，一些特别重要的模块，像RAM、ROM和CPU等经常被优先放置，而其它模块则被两两互不重叠地放置在芯片的剩余区域。此类问题能被形式化为带有预放置模块的布局问题，关于此问题的求解方法多为随机优化方法。该文基于拟人的思想，提出了占角和最大穴度优先的放置策略，为该问题的快速求解提供了一种高效的启发式确定性算法。算法的高效性通过应用于标准电路MCNC得到了验证。     

利用公共子序列求解固定边框布图问题

提出一种新的固定边框的布图算法．该算法采用SP表示方法,以公共子序列为基础,在随机搜索过程中限定布图宽度的变化,从而使减小芯片面积的目标与固定边框的目标在一定程度上取得一致．与现有的固定边框布图算法相比,文中算法在边框更紧凑、宽长比更大的条件下具有更高的成功率和更短的运行时间．此外,文中算法在布图初始阶段就可以对固定边框的合理性进行评估,避免了因给定的边框不合理而带来的时间上的浪费．     

逻辑函数适于双逻辑实现的探测算法

提出一种判定逻辑函数是否适于双逻辑实现的探测算法,直接从XOR逻辑的特点出发,即2个汉明距离为2 的最小项可以由 XOR 逻辑表示.通过计算函数最小项之间的汉明距离分析其所具有的逻辑模式,给出探测适用于双逻辑实现的判断条件.该算法已用 C 语言实现,并应用于 MCNC benchmark 电路的判定测试,实验结果验证了其有效性.