|
引 言 学位论文题目为《基于聚类分析的启发式优化算法》，论文内容涉及了优化算法（主要是经典优化算法，启发式优化算法），算复杂性理论和聚类分析等相关领域。根据这些领域与论文的相关程度，比较详细的归纳总结启发式优化算法，对计算复杂性理论和聚类分析只做了一般性的总结。最后对这些相关领域未来的发展和研究提出自己的观点。 最优化问题 在现实生活中许多重要的问题，都涉及到选区一个最好的目标，或者为达到这个目标而选择某些参数、确定某些值，这些问题都可以归结为最优化问题。 对于一个最小值问题，其形式的描述为 （1） 这里的S为解的可行域，也称为解空间或搜索空间，条件 概括了对向量 的约束。这些约束可以包括线性或非线性函数，以及离散变量，都可以根据实际要求设置。 最优化问题的目标是找到（1）的最优解（全局最优解或局部最优解）。显然，只要改变目标函数的符号，最大值问题就可以转变成最小值问题，因此，本文在说明都是以最小值问题问标准。解决最优化问题的算法称为最优化算法，可以分为经典优化算法和启发式优化算法。 经典优化算法 而经典优化算法又分为线形与非线性最优化算法，下面分别对两类算法的发展及常用的软件包做了介绍。 1. 线性最优化[1][10]： 线性最优化, 又称线性规划, 是运筹学中应用最广泛的一个分支.这是因为自然科学和社会科学中许多问题都可以近似地化成线性规划问题. 线性规划理论和算法的研究及发展共经历了三个高潮, 每个高潮都引起了社会的极大关注. 线性规划研究的第一高潮是著名的单纯形法的研究. 这一方法是Dantzig在1947年提出的,它以成熟的算法理论和完善的算法及软件统治线性规划达三十多年. 随着60年代发展起来的计算复杂性理论的研究, 单纯形法在七十年代末受到了挑战. 1979年前苏联数学家Khachiyan提出了第一个理论上优于单纯形法的所谓多项式时间算法--椭球法, 曾成为轰动一时的新闻, 并掀起了研究线性规划的第二个高潮. 但遗憾的是广泛的数值试验表明, 椭球算法的计算比单纯形方法差. 1984年Karmarkar提出了求解线性规划的另一个多项式时间算法. 这个算法从理论和数值上都优于椭球法, 因而引起学术界的极大关注, 并由此掀起了研究线性规划的第三个高潮. 从那以后, 许多学者致力于改进和完善这一算法,得到了许多改进算法.这些算法运用不同的思想方法均获得通过可行区域内部的迭代点列, 因此统称为解线性规划问题的内点算法. 目前内点算法正以不可抗拒的趋势将超越和替代单纯形法. 在互联网上能访问到的解线性和整数规划问题的软件还有:EQPS（线性，整数和非线性规划）,FMP（线性和混合整数规划），HS/LPLO（线性规划），KORBX（线性规划），LAMPS（线性和整数规划），LPBLP（线性规划），MILP（混合整数规划），MINTO（混合整数规划）， MPSIII（线性和混合整数规划），OML（线性和混合整数规划）， OSL（线性，二次和混合整数规划），PROCLP（线性和整数规划），WB（线性和混合整数规划），WHIZARD（线性和混合整数规划），XPRESSMP（线性和混合整数规划）等[41]。 2．非线性最优化[1][2][3][10]： 非线性规划的一个重要理论是1951年Kuhn-Tucker最优条件(简称KT条件)的建立[2].此后的50年代主要是对梯度法和牛顿法的研究.以Davidon(1959), Fletcher和Powell(1963)提出的DFP方法为起点, 60年代是研究拟牛顿方法活跃时期, 同时对共轭梯度法也有较好的研究. 在1970年由Broyden,Fletcher,Goldfarb 和Shanno从不同的角度共同提出的BFGS方法是目前为止最有效的拟牛顿方法. 由于Broyden, Dennis 和More的工作使得拟牛顿方法的理论变得很完善. 70年代是非线性规划飞速发展时期, 约束变尺度(SQP)方法(Han和Powell为代表)和Lagrange乘子法(代表人物是Powell 和Hestenes)是这一时期主要研究成果.计算机的飞速发展使非线性规划的研究如虎添翼.80年代开始研究信赖域法、稀疏拟牛顿法、大规模问题的方法和并行计算, 90年代研究解非线性规划问题的内点法和有限储存法. 可以毫不夸张的说, 这半个世纪是最优化发展的黄金时期. 与线性规划相比，非线性规划软件还不够完善. 但是已有大量解非线性规划问题的软件, 其中有相当一部分可从互联网上免费下载.LANCELOT是由Conn,Gould和Toint研制的解大规模最优化问题的软件包,适合解无约束最优化、非线性最小二乘、边界约束最优化和一般约束最优化问题.这个软件的基本思想是利用增广Lagrange函数来处理约束条件, 在每步迭代中解一个边界约束优化子问题, 其所用的方法结合信赖域和投影梯度等技术.MINPACK是美国Argonne国家实验室研制的软件包，适合求解非线性方程组和非线性最小二乘问题, 所用的基本方法是阻尼最小二乘法, 此软件可以从网上图书馆获得. PROC NLP是SAS软件公司研制的SAS商业软件中OR模块的一个程序，这个程序适合解无约束最优化、非线性最小二乘、线性约束最优化、二次规划和一般约束最优化问题.TENMIN是Schnabel等研制的解中小规模问题的张量方法软件。在互联网上能访问到的解非线性最优化问题的软件还有:CONOPT（非线性规划），DOT（优化设计工具箱），Excel and Quattro Pro Solvers（线性，整数和非线性规划），FSQP（非线性规划和极小极大问题），GRG2（非线性规划)， LBFGS（有限储存法），LINDO（线性、二次和混合整数规划），LSSOL（最小二乘和二次规划），MINOS（线性和非线性规划），NLPJOB（非线性多目标规划）， OPTPACK（约束和无约束最优化）,PETS（解非线性方程组和无约束问题的并行算法），QPOPT（线性和二次规划）,SQOPT（大规模线性和凸二次规划），SNOPT（大规模线性、二次和非线性规划），SPRNLP（稀疏最小二乘,稀疏和稠密非线性规划），SYSFIT（非线性方程组的参数估计），TENSOLVE（非线性方程组和最小二乘）， VE10(非线性最小二乘)等[38][39][40][41]. 启发式算法 大自然是神奇的，它造就了很多巧妙的手段和运行机制。受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。 启发式算法有不同的定义：一种定义为，一个基于直观或经验的构造的算法，对优化问题的实例能给出可接受的计算成本（计算时间、占用空间等）内，给出一个近似最优解，该近似解于真实最优解的偏离程度不一定可以事先预计；另一种是，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度[11]。我比较赞同第二种定义，因为启发式算法现在还没有完备的理论体系，只能视作一种技术。 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就[11][23]。 40年代：由于实际需要，人们已经提出了一些解决实际问题快速有效的启发式算法。 50年代：启发式算法的研究逐步繁荣起来。随后，人们将启发式算法的思想和人工智能领域中的各种有关问题的求解的收缩方法相结合，提出了许多启发式的搜索算法。其中贪婪算法和局部搜索等到人们的关注。 60年代: 随着人们对数学模型和优化算法的研究越来越重视，发现以前提出的启发式算法速度很快，但是解得质量不能保证。虽然对优化算法的研究取得了很大的进展，但是较大规模的问题仍然无能为力（计算量还是太大）。 70年代：计算复杂性理论的提出。NP完全理论告诉我们，许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，得到的解不能保证全局最优性。由此必须引入新的搜索机制和策略，才能有效地解决这些困难问题，这就导致了超启发式算法（meta-heuristic algorithms）的产生。 Holland模拟地球上生物进化规律提出了遗传算法（Genetic Algorithm），它的与众不同的搜索机制引起了人们再次引发了人们研究启发式算法的兴趣，从而掀起了研究启发式算法的热潮。 80年代以后： 模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。最近，演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等油相继兴起，掀起了研究启发式算法的高潮。由于这些算法简单和有效，而且具有某种智能，因而成为科学计算和人类之间的桥梁。
优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异（多样化）是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不同的超启发式算法。超启发式算法的主要思想来自于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得到的。 遗传算法：是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异得到的算法。在进化过程中，较好的个体有较大的生存几率[5]。 模拟退火：是模拟统计物理中固体物质的结晶过程。在退火的过程中，如果搜索到好的解接受；否则，以一定的概率接受不好的解（即实现多样化或变异的思想），达到跳出局部最优解得目的[10]。 神经网络：模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选择和变异的过程[22]。 禁忌搜索：模拟人的经验，通过禁忌表记忆最近搜索过程中的历史信息，禁忌某些解，以避免走回头路，达到跳出局部最优解的目的[32]。 蚂蚁算法：模拟蚂蚁的行为，拟人拟物，向蚂蚁的协作方式学习。 这几种超启发式算法都有一个共同的特点：从随机的可行初始解出发，才用迭代改进的策略，去逼近问题的最优解[23]。 他们的基本要素：（1）随机初始可行解； （２）给定一个评价函数（常常与目标函数值有关）； （３）邻域，产生新的可行解； （４）选择和接受解得准则； （５）终止准则。 其中（４）集中反映了超启发式算法的克服局部最优的能力。 虽然人们研究对启发式算法的研究将近５０年，但它还有很多不足[5][23]： 1.启发式算法目前缺乏统一、完整的理论体系。 2.由于NP理论，各种启发式算法都不可避免的遭遇到局部最优的问题，如何判断 3.各种启发式算法都有个自优点如何，完美结合。 4.启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。 5.启发算法缺乏有效的迭代停止条件。 6.启发式算法收敛速度的研究等。 计算复杂性 由于各种算法对同一个问题都有可能给出最优解，为了判定各种算法的效率，人们给出了算法复杂性的度量。计算复杂性理论是研究算法有效性和问题难度的一种工具。它是最优化问题的基础，涉及如何判断一个问题的难易程度。只有了解了所研究问题的复杂性，才能更有针对性地设计有关算法，提高算法效率。 所谓P问题，就是可以被关于问题本身的参数，如维数，约束个数等的多项式时间内求解的问题。 几个多项式和指数的时间复杂性函数的对比[9]
图（1）（S:秒 M:分 D:天 Y:年 C:世纪） NP问题就是对于一个给定的点，能多项式时间内判定它是否给定问题的解的问题[9][14]。NP包含P是以显然的事实。但是P是否也包含NP，就是一个非常困难的问题。目前这个问题被列为全世界7大数学难题之首。有一类NP问题，它们之间相互等价，求解其中一个问题就求解了全部问题。大部分组合组优化问题属于此类。这类问题称为NP完全问题类。单个问题就称为NP完全问题。一般相信，这类问题不存在多项式时间算法。 全局最优问题 全局最优化的问题很早就有很提出来个,Markowzi&Manne(1957)和Dantzig(1958)讨论了线性混合整数规划问题的全局最优解.(线性优化问题没有全局最优和局部最优的区别,因为线性规划是凸规划,它的可行域上的局部最优就是全局最优).之后又有LAND&DOIG等研究了全局最优化.全局最优化成为数学规划的一个分支的时间是<<Towards Global Optimization>>(dixon&Szego 1975).为了解决这个问题,大量的学者开始研究它,并提出了很多理论和算法,但是人们发现似乎是没有好的算法能有效的解决全局最优化问题. 起初人们用经典算法(如最速下降法,牛顿法,SQP等)进行多初试点的计算不能有效地解决,在那时(1970年代)计算复杂理论创立了. 自从Cook1972年提出NP理论，衡量计算复杂性就有了标准。已经证明了全局最优化问题是NP问题[11]．经典算法对它效果不是很好，随后有的人开始根据全局优化问题的特点对经典算法进行改进，有的则引入了启发式算法（如遗传算法，神经网络，模拟退活）[35][36]。大都采用随机搜索的策略[25][26]。似乎完美的东西是不存在的，如果得到精确的解，计算时间总是难以承受的．计算时间和结果的质量是不能同时提高的，如果想提高计算结果的质量就要多花时间，如果想要快速计算计算的结果就无法保证。
聚 类 分析 聚类分析是一种重要的人类行为。早在文明历史前，一个人就能通过不断地改进下意识中的聚类模式来学会如何区分动植物。聚类分析已经广泛地用在许多应用中，包括模式识别，数据分析，图像处理，以及市场研究。通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣相互关系。 聚类（clustering）就是将数据对象分组成为多个类或簇（cluster），在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大[17]。相异度是根据描述对象的属性值来计算的。距离是经常采用的度量方式。 常用的距离和相似度有明考斯基距离（Minkowski distance）、欧氏距离（Euclidean distance）、绝对值距离（City-block distance）、切比雪夫距离（Sup distance）、马氏距离（Mahalanobis distance）、帕松相关系数（Pearson correlation）、夹角余旋（Cosine similarity）等[15][18][20]。距离和相关系数的选取对整个聚类过程起着至关重要的作用，当然也可以根据具体问题，定义具体的距离和相关系数的计算方法。 聚类分析的方法可分为：划分的方法（partitioning method）、层次方法（hierarchical method）、基于密度的方法（density-based method）、基于网格的方法（grid-based method）、和基于模型的方法（model-based method） [17][19][37]。 １．划分的方法（partitioning method） 给定一个对n个对象或元素的数据，一个划分方法构建数据的k个划分，每个划分表示一个聚簇，并且n>k。它将数据划分为k个组，同时满足a.每组至少包含一个对象；b.每个对象必须属于且只属于一个组（模糊聚类除外）。 思想：给定要构建的划分数目k，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。 具体方法：k-means, k-median, EM(Expectation Maximization), CLARA(Clustering LAge Applications)等[17][20]。 ２．层次方法（hierarchical method） 层次的方法对给定数据对象集合进行层次的分解，根据层次的方法可以分为凝聚的和分裂的。凝聚的方法，一开始将每个对象作为单独得一组，然后相继地和合并相近的对象或组，直到所有的组合并称为一类。 具体方法：系统聚类法[15]，CURE(Clustering Using Representatives)，变色龙(Ch |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
