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个算例上找到了比此前最优记录更优的构型。
