《引力搜索算法及其应用》刘勇，马良著|(epub+azw3+mobi+pdf)电子书下载

图书名称：《引力搜索算法及其应用》

【作　者】刘勇，马良著

【页 数】 126

【出版社】 上海：上海人民出版社 , 2014.10

【ISBN号】978-7-208-12544-5

【价 格】38.00

【分 类】最优化算法-研究

【参考文献】 刘勇，马良著. 引力搜索算法及其应用. 上海：上海人民出版社, 2014.10.

图书封面：

图书目录：

《引力搜索算法及其应用》内容提要：

本书是在分析国内外引力搜索算法研究现状的基础上，着重介绍作者在引力搜索算法及其应用方面的研究成果。书中系统介绍了引力搜索算法的原理，分析了算法的数学模型和相关参数，进行了算法的理论研究，并探讨了算法在实际问题中的应用。

《引力搜索算法及其应用》内容试读

第一章智能优化算法

最优化理论和算法是一个重要的研究内容，其追求的目标是如何在众多的方案中找出最优方案。最优化问题普遍存在于我们的工作和生活中。例如，安排生产计划时，选择怎样的实施方案才能提高产值与利润；在城市建设规划时，如何安排住户、学校、医院、超市和工厂等单位的布局，才能有利于各行各业的发展，也能方便生活；工程设计时，如何确定设计参数，使得设计方案既能够满足设计指标又能够降低成本；资源分配时，如何分配有限的资源，使得分配方案既能满足各个方面的要求，又能获得好的效益。目前，优化作为一种希望实现的目标已经深入到各个领域，诸如此类，不胜枚举。最优化就是为这些问题的求解，提供理论基础和解决方法，是一门实用性强和应用广泛的学科1.)。

长期以来，人们一直对优化问题进行探讨和研究。早在17世纪，Newton发明微积分的时代，就已经提出极值问题，随后又出现了Lagrange乘数法。1847年，

Cauchy提出了最速下降法。1947年，Dantzig提出了单纯形法。随着研究的深入，人们提出了很多经典的优化算法。按照优化策略的不同，传统的优化算法可以大致分为以下几类：(1)枚举法，枚举法是将整个可行解空间所有点的性能进行比较并找出其中的最优，点。枚举法有完全枚举法和隐式枚举法等。算法的搜索策略最简单，但计算量也最大。枚举法适用于可行解空间是有限集合的情况。(2)解析法，解析法在优化过程中使用目标函数的解析性质，如一阶导数、二阶导数等。解析法是从一个初始点出发，并根据目标函数的梯度方向来确定下一步的搜索方向。常见的解析法有Newton法、共轭梯度法和变尺度法等.)。当目标函数有多个极值点时，算法难以找到全局最优点。

传统优化算法为优化问题的求解提供了巨大帮助，但在计算过程中传统优化算法也暴露出一些缺点。这些缺点主要表现在以下几点：(1)传统优化算法通常都是从一个初始点出发，每次迭代过程中也仅仅对一个点进行计算，这种算法架构很

001

难发挥现代计算机高速计算的性能，尤其是高性能的多处理器的计算机和现代并行计算的模式往往很难应用到传统优化算法中，这样就限制了算法求解大规模问题的能力和计算速度。(2)传统优化算法一般都要求目标函数是连续可微的，甚至有时要求是高阶可微的，但是在实际问题中这样的条件往往很难得到满足，这样就限制了传统优化算法的应用范围。(3)传统优化算法在每一次迭代时都要求迭代向改进方向移动，即每一次都要求目标函数值有所降低（以最小值优化问题为例），这样算法就不会具有“爬山”能力。若算法陷入某个局部的低谷，则无法继续搜索该区域之外的任何其他区域。因此，算法就失去了全局搜索能力。(4)每种传统优化算法只能求解一部分问题，即算法只能求解符合其适用条件的问题。要应用某种传统优化算法往往就会简化甚至改变原有的问题，使之能满足该方法的使用条件。但是如果问题不满足任何已知的传统优化算法的适用条件，那么用传统优化算法就无法有效求解6.刀。

考虑到传统优化算法的不足，人们希望能够设计出新的有效的优化方法。特别是进入20世纪90年代以来，所研究的实际问题的结构越来越复杂，规模越来越大，不可微、非线性、不确定性、多目标已经成为这些问题的基本特征，而建立在解析基础上的传统优化算法往往对这些问题的求解显得无能为力。因此，人们逐渐意识到，必须探索新的优化方法来解决这些问题。同时随着计算机科学与技术的飞速发展，从根本上改变了人们的工作和生活，并已经渗透到各个领域，如何充分发挥计算机技术的优势推动优化方法的发展，也是人们越来越关注的问题

大自然永远是人类创造力的丰富源泉，生命在长期的进化过程中，积累了许多特有的功能。各种生物为了延续自身和种群的生命所展现出的智能，令人叹为观止8，]。例如，一只蚂蚁或蜜蜂的行为能力非常有限，它几乎不可能独立存在于自然世界中，但由多个蚂蚁或蜜蜂形成的群体则具有非常强的生存能力，而这种生存能力不是通过多个个体之间能力的简单叠加所能获得的。自然界的很多现象不断给人们以启示，生物和自然生态系统可以通过自身的演化使得很多在人类看来高度复杂的问题能够得到完美的解决一)。受大自然的启发，人们从大自然的运行机制中找到了许多求解优化问题的新方法。从人工智能的角度，人们常常称这些算法为智能优化算法；从群体进化的特征来看，这些算法又可以称为进化计算算法；近几年人们从算法模仿自然规律的特点出发，也将这些算法称为自然计算。从应用这些方法的层面来看，方法采用什么名称并不重要，重要的是理解和掌握这

002

些算法所蕴含的搜索机制)。

智能优化算法的发展得益于运筹学、生物学、物理学、计算数学、计算机科学、人工智能和控制论等许多学科，充分吸收了这些学科的思想、概念和方法。智能优化算法，大都具备自组织性、正反馈性、鲁棒性、并行性和实现简单等特征，为在没有集中控制且不提供全局信息的条件下寻找复杂问题的求解方案提供了思路，为优化问题的求解开辟了新的手段6一-1]。

应用智能优化算法求解优化问题时，其搜索过程通常具有以下一些特征：

(1)个体都具有能执行简单的空间或时间上的评估和计算能力：(2)当环境（包括其他个体)发生变化时，个体能够对变化做出响应，特别是出现值得付出代价的改变机会时，个体必须能够改变其行为模式：(3)不同的个体对环境中的某一变化所表现出的响应行为应该具备多样性9]

和传统优化算法相比，智能优化算法具有其特有的优化方式。(1)非单点操作，采用群体搜索策略。智能优化算法大都采用由多个个体组成的群体对可行解空间进行搜索，在搜索过程中能够实现对各个体所提供信息的共享。信息的传播可以避免对一些不必要区域的搜索，既能提高算法的搜索效率，又能在一定程度上避免陷入局部极值。(2)智能优化算法在求解优化问题时，目标函数和约束函数可以不必是解析的，更不必是连续和可微的。智能优化算法可有效求解那些目标函数没有明确表达式，或有表达式但不可精确估值的优化问题。此外，智能优化算法对计算中数据的不确定性有较强的适应能力。(3)智能优化算法是对自然现象和自然规律的模拟，这些现象和规律所蕴含的深刻的优化思想为算法的设计提供了坚实的科学基础。在算法中，个体行为虽然简单但通过个体之间的相互作用，整个群体涌现出智能行为，而这种行为可用于求解优化问题。(4)智能优化算法不依赖于优化问题本身的数学性质和所求问题本身的结构特征以及其他辅助信息，算法可以用于求解不同类型的优化问题，具有广泛的适用性6刀。

对智能优化算法的研究可以追溯到上世纪50年代。当时，研究人员就已经意识到可以采用Darwin的生物进化论来求解复杂问题。l975年，Holland正式提出了遗传算法，这种新发展起来的完全异于传统优化算法的方法为优化问题的求解提供了崭新的途径。由于其在求解优化问题方面的巨大潜力，许多研究人员开始对智能优化算法展开研究，并获得了显著的进展。

随着人们对大自然的进一步观察和研究，又提出了很多有代表性的智能优化

003

算法。例如，模拟退火算法2)、人工神经网络、蚁群优化算法、微粒群优化算法[]、人工免疫系统31,2、蜂群算法[.]和生物地理学优化算法，等。除此以外，还包括这些算法与其他方法相结合而形成的混合型算法。这些算法构成了当前优化范畴内来自跨学科的别具特色的优化策略，丰富了优化手段，为那些传统优化算法难以处理的问题提供了切实可行的解决途径)。但是随着研究的深入，这些算法暴露出自身存在的一些不足，如容易早熟收敛、优化精度不高和优化速度慢等问题。此外，智能优化算法的数学基础相对薄弱，没有形成系统的理论体系。这些缺点都制约了智能优化算法的进一步发展。从本质上讲，之所以会有这么多的优化算法，主要是因为到目前为止还没有找到一种方法，能够应用到所有的优化问题中。为了解决我们所面临的问题，就必须研究新的优化算法。

经过多年的发展，已经出现了很多有代表性的智能优化算法，例如人工神经网络、模拟退火算法、遗传算法、蚁群优化算法和微粒群优化算法等等。虽然这些算法的优化原理各不相同，但也具有一些共同的特征，对不同智能优化算法的理解对另一种算法的研究有着重要的启发作用。因此，这里对现有的一些智能优化算法做一些简单介绍。

1.1人工神经网络

人工神经网络是对人类大脑系统一些特征的一种描述。简单地讲，它是一个数学模型，可以通过计算机程序进行模拟，也可以采用电子线路进行实现，是人工智能的一种研究方法[)。1943年，Mcculloch和Pitts第一次对神经系统中的神经元进行数学建模，并提出了MP模型。1957年，Rosenblatt提出了著名的感知器模型，该模型是一个能够连续调节权值矢量的MP模型。l959年，Widrow和Hoff设计出了自适应线性单元的网络模型，第一次把神经网络研究从纯理论研究转向工程应用研究3。自此，很多学者陆续对人工神经网络展开了研究，并取得许多可喜的成果。

人工神经网络是由大量功能简单但具有自适应能力的信息处理单元—神经元按照大规模并行的方式，采用一定的拓扑结构连接而成。神经元是对人脑神经细胞功能的简化、抽象和模拟。一个人工神经网络的神经元的模型与结构描述了一个网络的输入变量转换成输出变量的过程。从数学角度看这个转换过程就是

一个计算过程0.们

004

人工神经网络发展至今，已经出现了很多版本。这里，以Hopfield网络为例，分析其优化策略。Hopfield网络是一种非线性的动力学模型，采用类似Lyapunov函数的能量函数的概念，将神经网络的拓扑结构（采用连接权矩阵描述）和所求解问题（采用目标函数表示）对应起来，并转换为神经网络动力学系统的演化问题。所以在应用Hopfield网络解决优化问题之前，要将该问题映射为对应的神经网络。例如对旅行商问题的求解，首先将问题的可行解映射成一个置换矩阵，并能给出对应的能量函数，再将满足置换矩阵要求的能量函数的最小值和问题的最优解对应起来[。

对一般性的问题，往往需要处理以下一些工作：

(1)选择恰当的问题表示方式，使得神经网络的输出和问题的解相对应。

(2)设计合适的能量函数，使得其最小值和问题的最优解相对应。

(3)根据能量函数与稳定条件设置网络参数，如连接权值与偏置参数等。

(4)建立对应的神经网络与动态方程。

(5)采用软件或硬件进行模拟。

目前，人工神经网络的应用已经取得了令人瞩目的进展，其应用涉及科学研究和工程应用等领域中的许多问题。例如，函数优化、组合优化、模式识别、时间序列预测、非线性系统辨识与控制、特征选择、故障诊断和信号检测等。有关人工神经网络计算机硬件的开发也已经取得显著的成果。

1.2模拟退火算法

模拟退火算法是源于对热力学中退火过程的模拟，是一种通用的随机搜索方法，是对局部搜索方法的扩展，理论上是一种全局优化算法。1953年，Metropolis提出了模拟退火算法的思想。1983年，Kirkpatrick将模拟退火算法成功用于求解组合优化问题，才真正提出了模拟退火算法。从此，该算法受到越来越多的人的重视8.们

模拟退火算法的原理来自物理学，是将优化问题和统计力学的热平衡进行类比，问题的解视作状态，最优解视作退火过程中能量最低的状态，优化的目标函数视作能量函数，模拟物理学中固体物质的退火处理的过程。首先对物体进行加温使之具有足够高的能量，然后再逐步降温，其内部能量也逐渐下降。在热平衡的条件下，物体内部处于不同状态的概率服从Boltzmann分布，如果退火的步骤恰当，

005

那么最后会形成能量最低的状态。该算法在求解优化问题时，不仅接受对目标函数有改进的状态，而且能够以一定的概率接受目标函数恶化的状态，从而可以使得算法避免过早收敛到某个局部最优值，也正因为这种概率性的扰动，使得算法能够跳出局部极值，获得较好的优化结果5.6，门

以最小值优化问题(minf(x),x∈S)为例，给出基本模拟退火算法的求解流程6

步骤1随机生成初始解x:,设定初始温度T。和终止温度T,,令迭代次数k=0,Tb=T。。

步骤2从x:的邻域N(x,)生成一个解x,并计算两个解对应的目标函数值的增量△f=f(x,)一f(x:)。

步骤3若△f<0,则令x,=x,；否则生成0到1之间的随机数r,若exp(-△f/T)>r,则令x:=x,。

步骤4若达到热平衡条件（内循环次数大于n(T。)),则转步骤5；否则转步骤2。

步骤5降低T,令k=k十1，若T

1.3遗传算法

遗传算法是一种基于生物进化论中“自然选择、适者生存”规律的优化方法，算法的基本原理源于自然选择理论和遗传机制，通过模拟生命进化的方法来搜索问题的最优解.o。l967年，Holland的学生Bagley在其博士论文中首次提出“遗传算法”一词。1975年，Holland发表了在遗传算法领域具有重要意义的专著《Adaptation in natural and artificial systems》(《自然系统和人工系统的自适应》)，这是第一本比较系统论述遗传算法的著作。因此，有人把1975年作为遗传算法的诞生年。自提出以来，遗传算法获得了广泛的应用，为许多复杂困难的问题提供了有效的解决办法。

遗传算法在求解优化问题时，采用群体搜索策略而不是在单点上进行寻优，采用随机转换规则而不是确定性原则进行工作。算法将问题的解通过编码的方法

006

···试读结束···