带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

基于蚁群算法的带平衡约束矩形布局问题的启发式求解

以卫星舱布局问题作为研究背景,求解了带平衡约束的矩形布局问题。采用启发式策略设计了分区域分步布局法,该策略将圆形卫星舱承重板分成4个区域,分区域同步进行布局。当所布矩形和区域都确定时,采用最左最底填充策略进行布局。该方法通过不干涉约束,使布局紧凑,通过控制系统质心的位置,使系统保持平衡。在启发式策略的基础上,设计了蚁群算法搜索优化定位次序,从而得到优化的布局。数值仿真结果表明,该布局方法具有优良的计算性能。     

基于Wang-Landau抽样的带静不平衡约束的简化卫星舱布局方法

以简化卫星舱承载板上三维布局设计问题为背景,研究一类带静不平衡约束的圆柱体和长方体混合待布物布局问题。针对该三维布局问题,将已成功应用于统计物理学和蛋白质结构预测的Wang-Landau抽样算法引入布局问题中。Wang- Landau抽样算法通过在复杂布局空间中进行有效抽样来得到一个平坦的能量直方图,从而精确估计布局系统的状态密度。通过将Wang- Landau抽样算法与带加速策略的最速下降法、质心平移策略相结合,提出了改进的Wang-Landau抽样算法。对文献中两个算例进行了实算,计算结果表明,改进的Wang-Landau抽样算法的收敛速度和解的质量相比文献中其它算法均有较大的提高。     

求解带动不平衡约束的卫星舱布局问题的启发式算法

以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性.     

求解二维正交矩形布局问题的动态填空启发式算法

为更高效解决二维正交矩形布局问题,建立该问题的数学模型,改进BL算法规则;为寻找布局过程中的空余平面,建立了新颖的图形矩阵化理论。最后提出一种动态填空（DFB）启发式算法,制定了四条动态调整机制,结合遗传算法对该问题进行求解。大量算例测试显示：DFB算法可达到100%的平面利用率,极大提高了BL算法的效率,并且可以适用于大规模布局问题。     

求解矩形布局问题的自适应算法

矩形布局问题属于NP-Hard 问题,其求解算法多为启发式算法。该文侧重 于构造布局求解算法中定位函数（规则）的优化,将模拟退火算法的思想融入到遗传算法中, 提出了求解矩形布局问题的自适应算法,其利用自适应交叉、变异及接收劣质解的概率等方 法对定位函数中各参数进行优化。算法通过两种方式确定初始种群的数目,具有较强的适应 性。在算法搜索的后期,利用差异性较大的个体进行交叉操作,从而保持种群的多样性。最 后通过实例证明了该算法能够很好的应用于矩形布局问题的求解。     

基于模拟退火剩余矩形算法的矩形件排样

针对矩形件优化排样问题,讨论了用模拟退火算法结合剩余矩形法求解问题。首先阐述了矩形件排样问题的数学模型,然后给出了模拟退火剩余矩形算法求解问题的步骤和方法,最后用实例进行了算法验证。实例分析表明,采用模拟退火剩余矩形算法求解矩形件排样问题是适合的。     

用蚁群算法求解带平衡约束的圆形布局问题

采用启发式方法结合演化算法的思路求解带平衡约束的圆形布局问题.首先对传统优化模型进行调整,并探讨了调整的合理性;然后设计一种分步定位的布局方法,在此基础上利用蚁群算法寻优;最后利用局部搜索技术,在传统模型意义下对布局进行了改进.数值实验表明,算法的性能比目前已有的结果有较大的提高.     

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.     

解布局问题的四元组数据结构及其模拟退火算法

本文提出解布局问题的四元组数据结构，并根据该结构给出求解的模拟退火算法的基本程序。该结构和算法可直接用于求解复杂的布局问题，具有直接的实用价值和重要的理论意义。     

一种求解圆形Packing问题的模拟退火算法?

为求解矩形区域内的圆形Packing问题,提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局,使这些圆两两互不嵌入地放置。算法从任一初始构形出发,采用模拟退火(SA)算法进行全局寻优,在SA执行过程中,应用基于自适应步长的梯度法进行局部搜索,同时介绍一些启发式策略。对2组共20个算例进行实算测试,计算结果证明了该算法的有效性。     

求解多峰函数问题的模拟退火算法

论文提出了一种与演化算法群体搜索技术相结合的模拟退火算法(SimulatedAnnealingAlgorithmbasedonIn-dividuals,以下简记为ISA)。与传统的模拟退火算法(SimulatedAnnealing,以下简记为SA)不同的是它由多个个体在搜索空间里同时搜索,个体与个体之间没有信息交换,在遗传算子的作用下每个个体各自朝着适应值高的方向迅速演化,因而只要初始群体是均匀、随机地分布在搜索空间里并且个体数目适当多,算法最终都能找到多峰函数的所有峰值点。     

武器-目标分配问题的模拟退火算法

武器-目标分配(WeaponTargetAssignment)问题是一个典型的优化问题,模拟退火算法是求解此问题的一种有效方法。文章采用模拟退火算法对WTA问题进行求解,通过实验得到了理想的仿真结果。     

基于遗传算法和模拟退火算法的布局问题研究

文章在介绍遗传算法和模拟退火算法的基本理论及主要特点的基础上,提出了一个基于遗传算法和模拟退火算法的求解布局问题(矩形件排样优化)算法,并通过算例验证了该算法的有效性。     

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

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

改进的模拟退火算法在板式家具工业优化下料问题中的应用

讨论了如何利用改进的模拟退火算法即单调升温的模拟退火算法求解板式家具生产中的优化下料问题。在对问题进行数学描述的基础上，给出了算法求解的关键步骤和方法；讨论了单调升温模拟退火算法中如何跳出局部最优解，以及升温幅值的确定方法。实例表明该算法优化速度快，效率高，能有效解决大规模矩形件优化下料问题。     

基于模拟退火算法的旅行商问题的实现

旅行商问题TSP是一类典型的NP完全问题．围绕着这个问题有各种不同的求解方法,已有的算法例如动态规划法、分支限界法、回溯法等,这些精确式方法都是指数级的,根本无法解决目前的实际问题．贪心法是近似方法．无法达到比较满意的近似比。常用的遗传算法也是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列．所以遗传算法在求解该问题时的性能也并不理想。模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点．是解决旅行商问题的一种很好的算法。     

求解可满足性问题的改进的模拟退火算法

该文为可满足性问题的高效近似求解提出了改进的模拟退火算法。数值实验表明,对于该文随机产生的测试问题例,改进的模拟退火算法完全胜过局部搜索算法、模拟退火算法以及目前国际上流行的WSAT算法。     

一种基于模拟退火的自适应算法

针对常规BP算法收敛速度慢和易陷入局部极小的问题,文章提出了一种新的BP算法———SASSFBP算法。该算法根据训练中最近两个梯度的符号及其相对大小来动态地改变权步因子,提高了神经网络的收敛速度,并同时结合模拟退火算法来避免陷入局部极小。仿真实验结果表明:SASSFBP算法在收敛速度与运算精度,以及避免陷入局部极小的能力等方面均明显优于常规的BP算法。