共查询到19条相似文献,搜索用时 62 毫秒
1.
沿着拟人的途径,本文为一类具有NP难度的等国Packing问题得到了若干求解策略,以此为基础发展出两种高效率的快速近似求解算法。 相似文献
2.
等圆Packing问题是一个著名的几何难题,也是全局优化领域的一个天然明白客观公正的算法试金石.文中为等圆Packing问题提出了一个拟物型的全局优化算法.在算法中,N个圆饼在弹性挤压力的作用下平缓地运动,到达某个局部最优格局;适当的时期,又在高强度的引力和斥力的作用下剧烈地运动,跳出局部最优格局的陷阱,到达前景可能更... 相似文献
3.
等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法. 相似文献
4.
5.
6.
提出一种处理高维背包问题(KP)的贪婪封装二进制差分进化算法(GPBDE),并设计了一种贪婪封装的修补策略处理不可行解.为了提高种群的多样性及算法的全局搜索能力,对适应度较低的个体执行对偶变换.数值实验选取4种KP对GPBDE的优化能力进行测试,并将所提出的算法与4种同类算法进行比较,结果表明,GPBDE具有较强的寻优和约束处理能力,且收敛速度较快. 相似文献
7.
王永皎 《计算机工程与应用》2012,48(31):53-55,114
针对0-1任务规划模型存在维数灾维的问题,提出了一种基于改进差分进化算法的整数任务分配算法。将任务分配的0-1规划模型转化整数规划模型,不仅大幅降低了优化变量的维数,还减小了整式约束条件;将差分进化算法常用的变异算子DE/rand/1/bin和DE/best/2/bin结合起来组成新的变异算子,使得DE既保持了种群的多样性,又有较快的收敛速度和搜索精度,并用改进的差分进化算法求解整数规划;通过典型的任务分配实例验证了该算法在优化大规模任务分配的有效性和快速性。 相似文献
8.
具有单连续变量的背包问题(knapsack problem with a single continuous variable,KPC)是标准0-1背包问题的自然推广,在KPC中背包容量不是固定的,因此其求解难度变大.针对现有差分进化(differential evolution,DE)算法在高维KPC实例上求解精度不... 相似文献
9.
提出一种改进差分进化算法(IDE),以解决系统可靠性冗余分配问题.在罚函数法的基础上,对约束处理方法进行改进. 新约束处理方法在搜索过程中不需要在每一步都计算惩罚函数值,加快了寻优速度.具有良好的通用性,可以引入到其他智能优化算法中.将改进的算法用于求解4类典型的系统可靠性冗余分配问题,实验结果表明了所提出的改进算法具有很好的寻优精度和收敛速度. 相似文献
10.
针对当前算法在求解非线性方程组时面临解的个数不完整、精确度不高、收敛速度慢等问题进行了研究,提出一种多模态多目标差分进化算法。首先将非线性方程组转换为多模态多目标优化问题,初始化一个随机种群并对种群中全部个体进行评价;然后通过非支配解排序和决策空间拥挤距离选择机制,挑选种群中的一半优质个体进行变异;接着在变异过程中采用一种新的变异策略和边界处理方法以增加解的多样性;最后通过交叉和选择机制使优质个体进行进化,直到搜索到全部最优解。在所选测试函数集和工程实例上的实验结果表明,该算法能有效地搜索到非线性方程组的解,并通过与当前四个算法进行比较,该算法在解的数量和成功率上具有优越性。 相似文献
11.
利用改进的微分进化算法求解带平衡约束的圆形packing问题 总被引:8,自引:0,他引:8
提出了一种改进的微分进化算法(DE)求解二维带平衡约束的圆形packing问题.首先,构造出等价的物理模型,定义系统的能量函数,再对能量函数进行全局优化,从而间接得到问题的近似解.其中引入的参数动态调整策略在计算初期维持个体的多样性,后期加快算法的收敛速度,提高了DE算法的性能.最后,对两个算例进行了数值计算,实验结果证明了算法的有效性.此算法思路可推广应用于求解其它类型布局问题. 相似文献
12.
13.
求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性. 相似文献
14.
为了提高包装箱的空间利用率,提出一种基于离散差分进化算法的方法,以求解二维板材组包排样问题.采用带符号的序列代表一个排样方案,提出了基于最低水平线的空隙可再利用启发式算法,对单个包的子序列进行解码,获得对单包的排样子问题的自动排样方案,使板材充分填充产生的空隙;为了改进排样结果,提出邻近策略以进一步提高空间利用率.实验结果表明,对仿真实验数据,该算法获得了比遗传算法更好的结果;对实际生产数据,该算法所得结果比原有排样方案的空间利用率更高. 相似文献
15.
16.
对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题,提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域去是设计跳坑策略的一个关键难点.借鉴求解矩形Packing问题中动作空间的概念,通过化“圆”为“方”,将不规则的空闲空间近似为一系列规则的矩形空间,从而有效地解决了此难点.另外,将拟物法与提前中止、粗精调和自适应步长这3个拟人辅助策略相结合,以提高势能下降的效率.对3组共13个代表性算例的计算结果及与国内外代表性算法的比较表明,所提格局的外包络圆半径多为最小或次小,且在部分算例上找到了有更小外包络圆半径的格局,总体计算结果较好,且静不平衡量的精度较高. 相似文献
17.
压缩感知是基于信号稀疏性提出的采样理论,它在压缩成像、医学图像、雷达成像、天文学、通信等领域都有广泛的应用.压缩感知问题的求解本质上是一个优化问题,本文在微分进化算法的基础上对其改进,提出了一种改进微分进化算法,将其应用于压缩感知问题的求解中,取得了良好的效果. 相似文献
18.
对典型的NP难度问题--著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语"金角银边草肚皮"的启发,并将它发展提高到"价值最高钻石穴",提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录. 相似文献
19.
针对多模态优化问题(MultiModal Optimization Problems,MMOPs)的求解,提出了一种基于邻域低密度个体的差分进化算法.该算法在每一代,首先使用密度峰值聚类的方法求得每一个个体的密度,然后,将当前个体邻域范围内密度更低的个体作为变异算子的基向量,随着种群的进化,算法将会自动从探索阶段转化为... 相似文献