论文部分内容阅读
NP难度问题在现实生产和生活中广泛存在,其高效求解有着极其重要的经济价值、科研价值、军事价值,但是,由于NP是否等于P一直是一个理论上悬而未决的难题,因而有效的求解其全局最优解的算法随着问题的规模变大而变得令人望而却步,即使对于较小的N,非常简单的问题,例如N=20的等圆装填问题,其全局最优解至今尚未被寻获或证实。因此,设计高效能的启发式算法,使得能在可获得的计算资源、可接受的计算时间内找到优度尽量高的局部最优解解成为当前唯一有效的解决办法。而在现实中,很多优秀的启发式算法也确实表现不俗,取得的结果比常规的经验性结果大为改进,产生巨大的效益。论文的研究针对NP难问题中的两个具有重要实用背景的形式简单的实例:不等球和不等圆装填问题,研究、设计求解它们的高性能算法并对结果进行了分析和讨论。本论文主要综合应用禁忌搜索、迭代局部搜索、拟牛顿法、变邻域搜索、拟牛顿法的连续优化策略来解决这两个问题,同时,在迭代局部搜索中,根据关键元素导向的扰动策略(CEGP),采用了大圆或大球优先的扰动策略。本文的主要创新点在于:1、首次应用迭代禁忌搜索来解决不等圆和不等球装填问题;2、在邻域的构造过程的连续优化阶段,使用拟牛顿法,大大提高了计算速度;3、首次提出将某一较小的圆盘放置到某一较大的空穴然后进行连续优化以形成邻域的方法;4、首次使用“打格子"的方法来寻找格局中的空穴;5、不等圆装填问题中将构造邻域的两种方法在禁忌搜索中交替使用,应用变邻域搜索技术;6、在迭代禁忌搜索的扰动过程中基于关键元素驱动的策略思想使用大圆盘优先的扰动策略;7、在拟牛顿法的迭代过程中,使用Greedy-Redo的贪心策略,大大节省了连续优化的计算时间:8、在拟牛顿法的过程的运行过程中设定时间检查点,通过与其它邻域的拟牛顿过程的对应时间点时的优度进行比较,进行贪心剪枝,以节省计算时间;9、在不等球的装填问题中,设计了一种外半径容器可以根据计算情况自适应变化的方法,从而不需要在一开始就设定一个较合理的容器半径以启动计算;通过本文设计的算法进行实验计算,将结果与当今世界的最好记录比较,对于其中的一个经典系列,ri=1/i-1/2,改进了其中N=17-19和N=21-30的13项世界纪录,N小于等于30的其它世界纪录也都可以平。对于ri=i的另一个经典算例系列,可以平其中的N=1-30的世界纪录。以上结果显示出本论文提出的算法具有相当的优势。本论文进而分析了两个系列算例的当前世界最优格局的特征,包括半径和装填密度的变化曲线规律,以及最优格局中的小圆盘的布局特征的规律,以为进一步的算法设计提供启发和依据。同时,本文分析了以势能做为启发函数的优劣,指出势能较低的格局并不一定会在合法化后得到更小的容器半径,并指出这种误差是可以接受的,并提出了减小这种误差的策略。