检索结果-内蒙古大学图书馆

计算机研究与发展 2012年第9期49卷 1899-1909页

作者：黎自强田茁君王奕首岳本贤教育部智能计算与信息处理重点实验室(湘潭大学) 湖南湘潭411105 工业装备结构分析国家重点实验室(大连理工大学) 辽宁大连116024 大连理工大学计算机科学与技术学院辽宁大连116024

带平衡约束圆形packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆... 详细信息

带平衡约束圆形packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.

关键词：平衡约束圆形packing问题蚁群算法物理模型启发式方法并行算法

来源：评论

学校读者我要写书评

暂无评论

矩形区域不等圆形随机堆放的数值模拟

引用

计算力学学报 2017年第1期34卷 62-67页

作者：宋来忠廖大乾三峡大学理学院宜昌443002

将若干待堆放的圆形堆放到一个给定矩形区域,是一类特殊的packing问题。针对这一具有NP难度的困难问题,提出一种快速的数值模拟方法以及模拟力学检验的方法。该方法将圆形堆放的力学平衡规律化为几何形体相互接触的几何条件,把大量的圆... 详细信息

将若干待堆放的圆形堆放到一个给定矩形区域,是一类特殊的packing问题。针对这一具有NP难度的困难问题,提出一种快速的数值模拟方法以及模拟力学检验的方法。该方法将圆形堆放的力学平衡规律化为几何形体相互接触的几何条件,把大量的圆形按级配及分布律等约束条件,随机堆放形成空间区域。按此方法得到的圆形堆体,在不加外力的情形下即可保持自身的稳定。使用该方法,在边长为15cm的正方形区域内,取圆形的直径范围为0.5cm^4cm,模拟了孔隙率小于25%(面积比)的圆形堆体。最后,将所模拟的圆形堆体试件进行了有限元网格划分及力学加载试算,结果表明该堆体是稳定的。为进一步在细观层次研究圆形堆体提供了一个快速的数值模拟方法。

关键词： NP难问题圆形packing问题随机堆放数值模拟有限元

来源：评论

学校读者我要写书评

暂无评论

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

引用

计算机工程 2011年第19期37卷 141-144页

作者：刘朝霞刘景发南京信息工程大学网络信息中心南京210044 衡阳师范学院数学系湖南衡阳421008

为求解矩形区域内的圆形packing问题,提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局,使这些圆两两互不嵌入地放置。算法从任一初始构形出发,采用模拟退火(SA)算法进行全局寻优,在SA执行过程中,应用基于自适应步长... 详细信息

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

关键词：圆形packing问题模拟退火算法启发式策略梯度法布局矩形区域

来源：评论

学校读者我要写书评

暂无评论

求解圆形packing问题及模型蛋白结构预测问题的启发式算法

求解圆形Packing问题及模型蛋白结构预测问题的启发式算法

引用

作者：周国城南京信息工程大学

学位级别：硕士

求解NP难度问题是计算机科学技术的一个瓶颈任务。近年来研究表明,对于NP难度问题可能根本不存在既完整严格又不太慢的求解算法。研究者们试图从生物进化过程、物理运动过程以及人类社会中等得到启发,以期得到关于该类问题的非绝对完整... 详细信息

求解NP难度问题是计算机科学技术的一个瓶颈任务。近年来研究表明,对于NP难度问题可能根本不存在既完整严格又不太慢的求解算法。研究者们试图从生物进化过程、物理运动过程以及人类社会中等得到启发,以期得到关于该类问题的非绝对完整的,但是高效的近似的启发式求解算法。于是,一些具有高效优化性能,无需问题特殊信息等优点的现代启发式算法相继出现,如进化算法、模拟退火算法、禁忌搜索算法、蚁群算法等。这些计算方法大大丰富了现代优化技术,也为传统最优化技术难以处理的NP难度问题提供了切实可行的解决方案。本文对其中的贪心算法,局部搜索算法,模拟退火算法,禁忌搜索算法,遗传算法,蒙特卡洛算法等进行了简单的介绍,并重点研究了圆(球)形packing问题以及模型蛋白结构预测问题的现代启发式求解算法。首先,基于拟人化思想,为势能曲面变平法提出了一种高效的构形更新策略。通过将改进的势能曲面变平法(ELP+)与基于自适应步长的梯度法相结合,得到一种求解圆形packing问题的混合算法。其次,通过对禁忌搜索算法的邻域解,禁忌对象和当前解的接受原则进行改进,得到改进的禁忌搜索算法,并将改进的禁忌搜索算法和基于自适应步长的梯度算法相结合,提出了一种求解球形packing问题的基于禁忌搜索的启发式算法。另外,考虑到改进的ELP (ELP+)方法的高效优化性能,本文将ELP+方法应用到HP格点模型中去进行蛋白质结构预测,提出了一种高效的启发式算法。算法首先利用贪心策略产生初始构形,然后利用牵引移动更新构形,一旦计算陷入极小值的陷阱,则采用90°旋转,平移等启发式的跳坑策略跳出局部极小点。总之,受物理运动过程、人类社会以及具体问题的启发,本文为圆(球)形packing问题和模型蛋白结构预测问题提出了若干有效的启发式求解算法。这些方法对于研究其它NP难度问题的现实求解也具有普遍的实际意义。

关键词：启发式算法 NP难度问题圆形packing问题 HP格点模型蛋白质结构预测

来源：评论

学校读者我要写书评

暂无评论

求解圆形packing问题的改进的模拟退火算法

求解圆形Packing问题的改进的模拟退火算法

引用

2011 International conference on Intelligent Computation and Industrial Application(ICIA2011)

作者：刘景发张国建耿焕同刘朝霞南京信息工程大学计算机与软件学院

圆形packing问题是一个有着很高理论研究与实用价值的NP难度问题,求解这一问题的关键障碍是缺乏一种高效的全局优化方法。模拟退火(SA)法是一种基于Metropolis抽样的启发式全局寻优方法,已成功应用于许多优化问题。通过将SA法与梯度下... 详细信息

圆形packing问题是一个有着很高理论研究与实用价值的NP难度问题,求解这一问题的关键障碍是缺乏一种高效的全局优化方法。模拟退火(SA)法是一种基于Metropolis抽样的启发式全局寻优方法,已成功应用于许多优化问题。通过将SA法与梯度下降法相结合,并引入启发式构形更新策略,提出了一种改进的模拟退火(ISA)算法。对文献中的一组算例进行了测试,计算结果表明ISA算法是一种求解圆形packing问题的有效算法。

关键词：圆形packing问题模拟退火算法梯度下降法

来源：评论

学校读者我要写书评

暂无评论

求解圆形packing问题的改进的模拟退火算法

求解圆形Packing问题的改进的模拟退火算法

引用

2010 The 3rd International Conference on Computational Intelligence and Industrial Application (PACIIA2010)

作者：刘景发张国建耿焕同刘朝霞南京信息工程大学计算机与软件学院

关键词：圆形packing问题模拟退火算法梯度下降法

来源：评论

学校读者我要写书评

暂无评论

在圆形packing及团簇结构优化问题上的启发式优化算法研究

在圆形Packing及团簇结构优化问题上的启发式优化算法研究

引用

作者：叶涛华中科技大学

学位级别：博士

NP难度的优化问题广泛的出现在科学研究和生产实践的各个领域,是各自领域里的核心问题和瓶颈性问题。但是,关于计算复杂性理论的研究经验表明,对于NP难度问题,可能根本不存在那种精确完备而又快速高效的求解算法。迄今为止,人们所能找... 详细信息

NP难度的优化问题广泛的出现在科学研究和生产实践的各个领域,是各自领域里的核心问题和瓶颈性问题。但是,关于计算复杂性理论的研究经验表明,对于NP难度问题,可能根本不存在那种精确完备而又快速高效的求解算法。迄今为止,人们所能找到的关于NP难度问题的精确型求解算法都是指数型的,只能适用于问题规模较小的情形,或者问题本身有特殊结构的情形。为了现实求解日常生活中出现的那些大规模的复杂的优化问题,人们把目光转向非完备的启发式优化算法。经过最近几十年的研究,人们发现,好的启发式优化算法往往能够在合理计算时间内找到高质量的解方案,能够又快又好的解决问题。启发式优化算法已成为计算机科学、人工智能和运筹学领域的研究热点。论文首先对启发式优化算法的理论背景、经典算法设计思路以及算法评价准则进行了系统的回顾。然后,以两个经典的有重要实际价值的问题—圆形packing问题和团簇结构优化问题—为研究介质,分别为其设计了高效的启发式优化算法,并通过计算实验对算法进行了分析和评价。论文的主要贡献包括： (1)为圆内等圆packing问题提出了一个高效的拟物型全局优化算法。算法包含三个主要部分：拟物下降过程、拟物跳坑过程以及容器调整过程。拟物下降过程通过模拟n个光滑弹性圆饼在一个刚性容器内的相互挤压运动来引导所有圆饼到达一个局部最优格局。拟物跳坑过程通过引入两种非接触的强烈的电磁排斥力和中心吸引力来刺激n个圆饼从局部最优的陷阱中跳出来,到达解空间中某个更有前景的位置。容器调整过程将容器的半径调整到一个合适的值,使得圆饼之间没有嵌入而且容器的半径尽量小。使用了圆内等圆packing问题n=1,2...,200的算例对算法进行了测试,拟物型全局优化算法在63个算例上找到比此前已知最优记录更优的布局。 (2)为方内等圆packing问题提出了一个高效的贪心空穴搜索算法。首先为问题提出了一个贴切的物理模型,并以此为基础为方内等圆packing问题提出了一个局部优化算法。然后,为方内等圆packing问题提出了一个贪心空穴搜索算法,它通过不断地将某个圆饼移动到格局中最空的区域来产生优度越来越好的解。使用了方内等圆packing问题n=1,2,...,200的算例对算法进行了测试,贪心空穴搜索算法在41个算例上找到比此前已知最优记录更优的布局。 (3)为双原子团簇结构优化问题提出了一个高效的启发式优化算法—30P算法。双原子团簇结构优化问题是计算化学中的著名的挑战性问题。问题的难度一方面是因为在解空间中存在着天文数字的局部最优构型；另一方面,我们需要同时为每个原子挑选坐标位置和原子类型,因此问题中同时包含有连续优化和离散优化。论文提出的30P算法系统地使用了三个有针对性的扰动算子来不断的改进团簇的构型。依靠这三个扰动算子,算法实际上在问题解空间的局部最小值集合上建立了一个复杂的邻域结构。以该邻域结构为基础,算法能够从一个初始的局部最优解出发,不断的找到优度越来越好的局部最优解。使用了双原子团簇结构优化问题上的标准算例对算法进行了测试,算法在绝大部分算例上都找到了当前的已知最好构型,并在12个算例上找到了比此前最优记录更优的构型。

关键词： NP难度全局优化启发式算法元启发式算法圆形packing问题团簇结构优化

来源：评论

学校读者我要写书评

暂无评论

基于禁忌搜索的启发式算法求解圆形packing问题

引用

计算机研究与发展 2004年第9期41卷 1554-1558页

作者：康雁黄文奇云南大学软件学院昆明65009 华中科技大学计算机科学与技术学院武汉430074

求解具有NP难度的圆形 packing问题具有很高的理论与实用价值现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程... 详细信息

求解具有NP难度的圆形 packing问题具有很高的理论与实用价值现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程中利用了禁忌搜索法的思想 ,通过禁止重复前面已做的工作 ,使搜索能有效地逃离局部极小值的陷阱 ,提高了搜索效率实验结果表明。

关键词：圆形packing问题禁忌搜索法启发式算法 NP难问题

来源：评论

学校读者我要写书评

暂无评论

求解不等圆packing问题的一个启发式算法

引用

计算机研究与发展 2007年第12期44卷 2092-2097页

作者：陈矛黄文奇华中师范大学教育信息技术工程研究中心武汉430079 华中科技大学计算机科学与技术学院武汉430074

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多... 详细信息

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性.

关键词： NP难问题圆形packing问题启发式算法占角动作有限枚举策略

来源：评论

学校读者我要写书评

暂无评论

求解圆形packing问题的一个快速拟物算法

引用

计算机工程与应用 2003年第35期39卷 30-32页

作者：康雁黄文奇云南大学软件学院昆明650091 华中科技大学计算机科学与技术学院武汉430074

求解NP难问题一直是计算机科学技术中的一个瓶颈任务。自20世纪70年代以来的研究表明,不存在求解此类问题的完整严格的有效算法。因此用启发式方法求解成为当今研究的一个热点。圆形packing问题是一个有着很高理论和实用价值的NP难问题... 详细信息

求解NP难问题一直是计算机科学技术中的一个瓶颈任务。自20世纪70年代以来的研究表明,不存在求解此类问题的完整严格的有效算法。因此用启发式方法求解成为当今研究的一个热点。圆形packing问题是一个有着很高理论和实用价值的NP难问题。该文提出了一些有效的搜索策略,得到了一个求解它的快速有效启发式算法。最后用计算实例验证了此算法的有效性,计算结果表明此算法明显优于已有快速算法。

关键词：圆形packing问题拟物方法 NP难度启发式方法

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：