论文部分内容阅读
至今无严格有效的方法能保证在合理的计算时间内找出NP难问题的最优解。受自然界和人类社会中智慧的启发,我们提出了有效地近似求解具有NP难度的圆形packing问题的启发式方法。 本文所做的工作主要有: 第一,得出了一个高效地近似求解圆形packing问题的快速拟物拟人算法。此算法比之于前人所得的最好算法,其效能有了显著的提高。对于困难的问题实例,在保持优度相等的前提下,其速度大致提高了10~100倍。 第二,受物理世界中弹性物体运动规律的启发,得到了一个预测搜索前景的策略,它通过及早地终止将会陷入局部极小值陷阱的搜索,提高了搜索的效率;受自然界中优胜劣汰规律的启发得出另一个策略,它通过很好地利用人类在社会活动中积累的智慧,使搜索逃离局部极小值的陷阱,并走向更有前途的方向。结合这两个启发式策略以及拟物拟人法得到了快速拟物拟人算法。 第三,在模拟物理世界中弹性物体运动的基础上,借鉴模拟退火法的思想,得出了二个启发式方法。这两个方法通过在搜索过程中以不同的规则接受不优于当前解的新解,使搜索有可能逃离局部极小值陷阱,从而有效地求解了等圆packing问题。 第四,在用各启发式方法有效地求解大量实例的基础上,研究了启发式方法的工作原理,提出了设计启发式方法的可行的方案。