全局最优化算法及其应用.pdfVIP

维普资讯 大 庆 石 油 学 院 学 报 第29卷 第 1期 2005年 2月 JOURNAIOFDAQING PETROIEUM INSTITUTE VoI．29 No．1 Feb． 2005 全局最优化算法及其应用 陈冬芳 ，薛继伟 ，张 漫 (1．大庆石油学院 计算机科学学院，黑龙江 大庆 163318； 2．中国科学 院 成都计算机应用研究所，四川 成都 6l0041) 摘 要：综述了近年来国内外学者对全局最优化问题的研 究成果，分析了不同全局最优算法的优缺点，指出了因存 在最优化问题的本质特征 (NP一难题)而在实践 中算法可解的问题并不一定可解 ，同时指 出了没有适合解决任何问题的 通用全局最优算法，最后给出了2个研究趋势． 关 键 词 ：全局优化 ；禁忌有哪些信誉好的足球投注网站；遗传算法；模拟退火算法；分枝与界定 ；区间方法 中圈分类号 ：TP301．6 文献标识码 ：A 文章编号：1000—1891(2005)01—0089—05 1 最优化 问题的一般形式 大部分工程优化设计问题可以表示为在一组约束条件下求一个 目标函数的极值问题，即 opt．f(xl，．272，…，．27)， fg (．27l，．272，… ，．27)≤ 0，i一 1，…，Z， 1h，(z1，．272，…，．27)一0， 一z+1，…，m． 式中：opt．为优化 (optima1)；s．t．为受约束于(subjectto)；(zl，z2，…，z)为决策变量 ；g。(zl，z2，…，z)≤ 0和h，(。， ，…， )一0为约束条件；f(x。，．27，…，．27)为 目标函数．满足约束条件的全体 71维 向量x一 (。，oT，…，oT)构成 71维空间 中的子集，即 一 {x∈R”lg。(x)≤0，h(x)一0，i一 1，…，z；—z+1，…，m) 称为可行域 ，可行域中的点称为问题的可行解． 若 x ∈ ，对一切x∈ ，都有 -厂(x)≥f(X )，则称x 为问题的全局最优解或整体最优解． 若x ∈ ，存在x 的某个邻域N (x )一{x… x—x ll￡，x∈R (其中e0，llll为向量模)，使 得一切x∈ —N (x )均有 -厂(x)≥f(x )，则称x 为问题的局部最优解． 显然，问题的全局最优解必是它的一个局部最优解．最优化问题就是在可行域中找使 目标函数达到 全局最优点的集合． 2 最优化算法的分类 对最优化问题求解的理论和算法的研究，是当今数学和计算机科学研究的重要课题之一．所谓优化 算法，是一种有哪些信誉好的足球投注网站过程或规则 ，它是基于某种思想和机制 ，通过一定的途径或规则得到满足用户要求的问 题解．总体上分为局部最优算法和全局最优算法． 局部优化的理论 比较成熟，具有判断局部极小点的最优性条件 (无约束问题的一阶必要条件、二阶充 分条件和二阶必要条件；约束问题的FritzJohn必要条件、Kuhn—Tucker必要条件和 Kuhn—Tucker充 分条件)．局部优化的算法较多，如，求解线性规划的单纯形方法 (Dantzig，1947)、求解非线性最优化问题 的最速下降法、牛顿法、拟牛顿法、共轭梯度法(FR算法和PRP算法等)、罚函数法、可行方向法和信赖域 收稿 日期 ：2004一O5一l4；审稿人 ：刘成仕；编辑：关开澄 基金项 目：国家973计划项 目(2004CB318003) 作者简介：陈冬芳(1972一)，男，硕士，讲师 ，主要从事智能优化算法方面的研究 维普资讯 大 庆 石 油 学 院 学 报 第 29卷 2005年 法(Powell，1975)等；但是，这些传统的数值最优化算法通常只能找到 目标函数的平稳点／驻点和局部