共查询到20条相似文献,搜索用时 140 毫秒
1.
在货物装载、木材下料、超大规模集成电路(VLSI)设计等工作中提出了矩形块装填与切割问题,对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验,提出了一种求解矩形块装填问题的拟人算法。谊算法使用了两个主要的思想策略,即矩形块选择策略和矩形块放置策略。用本文提出的算法,对21个测试算例进行了实算测试,测试结果表明:算法所得装填结果的优度高,计算时间短。对这21个测试算例。用本文算法计算,得到了其中16个算例的最优解,而计算时间都在2秒以内。进一步的测试表明,本文提出的算法对求解矩形块装填问题十分有效。 相似文献
2.
等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法. 相似文献
3.
求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性. 相似文献
4.
在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。 相似文献
5.
研究一种自适应遗传模拟退火算法,应用于矩形件优化排样问题。以整数编码矩形件的排样序列,采用经验选择与随机生成相结合的策略构造初始种群。运用自适应交叉和变异概率动态地控制遗传算法的收敛速度,通过模拟退火算法引导全局最优搜索,采用启发式最低水平线择优算法对排样序列进行解码,形成排样方式。多组对比实验结果表明,自适应遗传模拟退火算法求解速度较快,可以有效提高板材的利用率。 相似文献
6.
以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法. 相似文献
7.
王石 《计算机技术与发展》2011,21(3)
针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于"阶梯式堆码"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的. 相似文献
8.
命题逻辑公式的CNF范式的可满足性问题(sAT)是计算机科学的非常重要的核心问题,能否快速求解SAT问题是目前的研究热点之一。介绍Johnson算法、遗传算法和模拟退火算法,比较三种算法的特性,提出综合GA、SA算法优点的一种混舍遗传和模拟退火算法的思想。数值计算结果表明,相对于Johnson算法,采用启发式(SA、GA)算法可以显著地提高3-SAT问题解的质量和求解速度。 相似文献
9.
基于遗传算法和模拟退火算法的布局问题研究 总被引:8,自引:0,他引:8
文章在介绍遗传算法和模拟退火算法的基本理论及主要特点的基础上,提出了一个基于遗传算法和模拟退火算法的求解布局问题(矩形件排样优化)算法,并通过算例验证了该算法的有效性。 相似文献
10.
许继影 《计算机工程与应用》2012,48(13):234-239
提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。 相似文献
11.
提出了一个基于确定性模拟退火技术的时延驱动标准单元布局算法,实现在满足时延约束和宽高比约束的前提下优化版图面积,与基于一般的随机模拟退火技术的标准单元布局算法相比,该算法的运行速度快、布局效果较好。 相似文献
12.
针对嵌入式系统软硬件划分问题,在比较了遗传算法(GA)和模拟退火(SA)各自优缺点的基础上,提出了采用遗传/模拟退火混合算法(GASA)的策略。该算法的核心思想是将模拟退火算法嵌入到遗传算法中,利用遗传优化算法的结果来制约模拟退火的随机状态产生,然后根据模拟退火算法的接受准则和随机状态产生函数来更新遗传算法的种群,从而最终得到最优解。与单纯的遗传算法和模拟退火算法进行对比实验,实验结果表明,GASA更有优势,得到的划分结果也更优秀。 相似文献
13.
Mahdi Hamzeei Reza Zanjirani Farahani Hannaneh Rashidi-Bejgan 《Journal of Manufacturing Systems》2013
In this paper, we present two algorithms to design flow path and the location of its pickup and delivery (P/D) stations simultaneously in a block layout for Automated Guided Vehicles (AGVs). We develop two algorithms to solve this problem. The first one is a cutting-plane algorithm to solve the mixed integer linear program that models the problem. The second one is a Simulated Annealing (SA) approach which solves the problem heuristically to a near best solution. Computational results show the performance of both algorithms. 相似文献
14.
提出一种用于处理板材下料问题的粒子群与模拟退火混合算法。同时,在把下料模式转化为实际设计时,提出了一种类似于Bottom Left(BL)算法的转换方法。模拟实验结果表明这种混合方法的性能明显优于粒子群算法。 相似文献
15.
16.
Gülfem Tuzkaya Bahadır Gülsün Umut R. Tuzkaya Semih Onut Ender Bildik 《Journal of Intelligent Manufacturing》2013,24(2):357-372
In this study, a facility layout problem having NP-hard problem characteristic is attempted to be solved by using two different meta-heuristic approaches—Genetic Algorithm (GA) and Simulated Annealing (SA)—and a hybrid approach—Genetic Algorithm/Simulated Annealing (HGASA). The case study is completed for a company which can be seen as a small or a medium size enterprise. First, parameter values of GA and SA are determined by testing for various combinations of them. Then, the algorithms are run for one hundred times. The results of the algorithms are compared based on their fitness values and calculation time requirements using the paired-t test, mean and standard values. The results show that SA performs better than the others in terms of the fitness values and the time requirements. In this study, we also test the performance of our GA, SA and HGASA methodologies using some of the well-known test problems from the literature. We obtain very close results to those in literature. 相似文献
17.
18.
A stochastic version of Expectation Maximization algorithm for better estimation of Hidden Markov Model 总被引:1,自引:0,他引:1
This paper attempts to overcome the local convergence problem of the Expectation Maximization (EM) based training of the Hidden Markov Model (HMM) in speech recognition. We propose a hybrid algorithm, Simulated Annealing Stochastic version of EM (SASEM), combining Simulated Annealing with EM that reformulates the HMM estimation process using a stochastic step between the EM steps and the SA. The stochastic processes of SASEM inside EM can prevent EM from converging to a local maximum and find improved estimation for HMM using the global convergence properties of SA. Experiments on the TIMIT speech corpus show that SASEM obtains higher recognition accuracies than the EM. 相似文献
19.