几种智能优化方法

1.遗传算法遗传算法(GeneticAlgorithms,GA)是由美国密歇根大学的 JohnH.Holland教授及其学生于20世纪60年代末到70年代初提出的。在1975年出版的《自然与人工系统的自适应性》一书中，Holland系统地阐述了遗传算法的基本原理和方法，提出了对遗传算法的理论发展极为重要的模板理论。遗传算法基本思想：遗传算法是根据问题的目标函数构造一个适值函数，对于有多个解构成的种群进行评估、遗传运算、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。具体描述如下。产生初始种群遗传算法是一种基于群体寻优的方法，算法运行时是以一个种群在搜索空间进行搜索。一般是采用随机方法产生一个初始种群。也可以采用其他方法构造一个初始种群。根据问题的目标函数构造适值函数在遗传算法中使用适值函数来表征种群中每个个体对其生存环境的适应能力， 每个个体具有一定的适应值。适应值是种群中个体生存机会的唯一确定值。适值函数直接决定着群体的进化行为。适值函数基本上依据优化的目标函数来确定。为了能够直接将适值函数与群体中的个体优劣相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好。根据适应值的好坏不断选择和繁殖在遗传算法中自然选择规律的体现就是以适应值的大小决定的概率分布来进行计算选择。 个体的适应值越大，该个体被遗传到下一代的概率越大；反之，个体适应值越小，该个体被遗传到下一代的概率越小。被选择的个体两两进行繁殖，繁殖产生的个体组成新的种群。这样的选择和繁殖的过程不断重复。若干代后得到适应值最好的个体即为最优解在若干代后，得到适应值最好的个体所对应的解即被认为是问题的最优解。遗传算法构成要素：种群和种群大小种群是有染色体构成的。每个个体就是一个染色体，每个染色体对应着问题的一个解。种群中个体的数量称为种群大小或种群规模。种群规模通常采用一个不变的常数。一般来说种群规模越大越好，但是种群规模增大也将导致运算时间的增大。在一些特殊情况下，群体规模也可能采用与遗传代数相关的变量，以获取更好的优化效果。编码方法(EncodingScheme)编码方法也称为基因的表达方法。在遗传算法中，种群中每个个体，即染色体是由基因构成的。所以染色体与要优化的问题的解如何进行对应，就需要通过基因来进行表示，即染色体进行正确的编码(一般用二进制编码)。正确地对染色体进行编码来表示问题的解是遗传算法的基础工作，也是最重要的工作。遗传算子(GeneticOperator)遗传算子包括交叉(Crossover)和(Mutation)。遗传算子模拟了每一代中创造后代的繁殖过程，是遗传算法的精髓。交叉是最重要的遗传算子，它同时对两个染色体进行操作，组合二者的特性产生新的后代。交叉最简单的方式是在双亲的染色体上随机地选择一个断点，将断点的右段相互交换，从而形成两个新的后代。这种方式对于二进制编码最适合。遗传算法的性能很大程度上取决于采用的交叉运算的方式。交叉率定义为各代中交叉产生后代数与种群中个体数的比。 显然，较高的交叉率将达到更大的解空间，从而减小停止在非最优解上的机会；但交叉率过高，会因过多搜索不必要的解空间而浪费大量的计算时间。变异率定义为种群中变异基因数在总基因数中的百分比。变异率控制着新基因导入种群的比例。若变异率太低，一些有用的基因就难以进入选择；若太高，即随机的变化太多，那么后代就可能失去从双亲继承下来的好特性，这样算法就会失去从过去搜索中学习的能力。选择策略和停止准则选择策略是从当前种群中选择适应值高的个体以生成交配池的过程。使用最多的是正比例选择策略。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想，并保证优良基因遗传给下一代。一般使用最大迭代次数作为停止准则。蚁群算法20世纪90年代初，意大利学者DorigoM等人提出一种模拟昆虫王国中蚂蚁群体觅食行为方式的仿生优化算法一一蚁群算法( AntColonyAlgorithm,ACA)。该算法引入正反馈并行机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点。据生物学家的观察和研究，发现自然界中的蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物一一信息素，使得一定范围内的其他蚂蚁能察觉到并由此影响它们以后的行为当一些路径上通过的蚂蚁越来越大时，其留下的信息素浓度也越来越大，好来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择被称为蚂蚁的自催化行为。 因此，也可以将蚂蚁王国理解成所谓的增强型学习系统。自从蚁群算法在著名的旅行商问题( TSP和二次分配问题(QAP)上取得成效以来，已陆续渗透到其他问题领域中，如工件排序、图着色问题、车辆调度问题、大规模集成电路设计、通讯网络中的负载平衡问题等。蚁群算法这种来自生物界的随机搜索寻优方法目前已在许多方面表现出相当好的性能，它的正反馈性和协同性是指可用于分布式系统，其隐藏的并行性更是具有极强的发展潜力。其求解的问题领域也在进一步扩大，如一些约束型问题和多目标问题，从1998年10月与比利时布鲁塞尔召开的第一届蚁群优化国际研讨会的内容中可以看出这种带有构造性特征的搜索方法所产生的深远影响和广泛应用。模拟退火算法模拟退火算法(SimulatedAnnealing,SA)是属于一种通用的随机搜索算法，是局部搜索算法的扩展，它的早期思想是在1953年由Metropolis提出来的，到1983年由Kirkpatrick等人成功的应用在组合优化问题中.模拟退火法来源于固体退火原理，将固体加热到一定温度后，它的所有分子在状态空间自由运动.随着温度的逐渐下降，分子停留在不同的状态，分子运动逐渐趋于有序，最后以一定的结构排列.这种由高温向低温逐渐降温的过程称为退火 .退火过程中系统地熵值不断减小系统能量随温度的降低趋于最小值.固体退火过程与优化问题之间存在着类似性.Kirkpatrick等人把Metropolis等人对用固体在恒定问题下达到热平衡过程的模拟引入到优化过程中 .即如果E2-E1<0则接受新状态，否则按概率P接受新状态.T为一随即时间t增加而下降的参变量，相当于退火过程中的温度.这种利用优化问题求解物理系统退火过程的相似性 ，使用Metropolis算法，适当控制温度的下降过程，实现模拟退火，从而达到求解全局优化问题的随机性方法称之为“模拟退火算法”。模拟退火算法在搜索策略上引入了适当的随机因素和物理系统退火过程的自然机理，使得在迭代过程中出现可以接受使目标函数值变“好”的试探点，也可以以一定的概率接受使目标函数值变“差”的试探点、接受概率随温度的下降逐渐减小。这样避免了搜索过程陷入局部最优解，有利于提高求的全局最优解的可靠性。 因此，模拟退火算法具有实用广泛性，求的全局最优解的可靠性高，算法简单，便于实现等优点。基本模拟退火算法的步骤：步骤1:选择初始状态H(初始解)、初始温度、降温次数等；步骤2:生产H',并计算两种状态下的目标函数变化 f(H)-f(H')；步骤3:按接收概率置换H为H';步骤4:重复步骤2和步骤3直至满足结束条件。禁忌搜索算法禁忌搜索算法(TabooSearch,TS是继遗传算法之后又一种元启发式优化算法，最早于1977年由Glover提出。它采用了类似爬山法的移动原理，将最近若干步内所得到的解存储在一种称为Tabu的列表中，从而强制搜索避免再次重复表中的解。如果说遗传算法开辟了在解空间中从多出发点搜索问题最优解的先河， 则禁忌搜索法是首次在搜索过程中使用记忆功能的先驱，他们在求解各种实际问题中都取得了相对的成功。算法基本步骤大致如下：步骤1:选择初始解XO,X*<—XO,Z*<-f(X*);禁忌列表Tabu为空；步骤2：对当前解邻域中的X，若f(X)<Z*,并且X不再Tabu中或者X在Tabu中，但不符合期望准则，则X*<—X，Z*<—f(X);X*进Tabu;步骤3:重复步骤2直至满足结束条件。禁忌搜索算法自提出以来，已陆续应用到 TSPQAP、工件排序、车辆路径问题、电路设计问题。图着色问题、背包问题等领域。在 TS法提出初期，就已与神经网络进行了有机的结合，20世纪90年代还增有求解过有几十万个顶点的大型 TSP问题。该方法与模拟退火算法、遗传算法。蚁群算法等相结合，形成了更为有力的混合型启发式算法。人工神经网络神经网络的基本原理是构造人工神经网络模型的一个基本依据。 1943年McCulloch和Pitts建立了第一个人工神经网络模型， 后被扩展为“认知”模型。认知模型的一个功效可以用来解决简单的分类问题。1982年，美国生物物理学家Hopfield提出人工神经网络(ArtificialNeuralNetworks,ANNs)模型，才被认为是一个重大突破。而 Hopfield和Tank用ANN方法求解TSP获得成功以来，更是引起了极大的关注。该方法的思想是通过对神经网络引入适当的能量函数，使之与TSP的目标函数一致来确定神经元之间的连接权， 随着网络状态的变化，其能力不断减少，最后达到平衡时， 及收敛到局部最优解。但是，这种算法在求解中很有可能陷入在解空间中作无目标的周游或者落到许多局部最小点中的某一点上， 尽管可以适当修正Liapunov函数，但一些根本性的困难仍很难消除。随着人们对感知机兴趣的衰退，神经网络的研究沉寂了相当长的时间。 80年代初期，模拟与数字混合的超大规模集成电路制作技术提高到新的水平， 完全付诸实用化，此外，数字计算机的发展在若干应用领域遇到困难。 这一背景预示，向人工神经网络寻求出路的时机已经成熟。美国的物理学家Hopfield于1982年和1984年在美国科学院院刊上发表了两篇关于人工神经网络研究的论文，引起了巨大的反响。人们重新认识到神经网络的威力以及付诸应用的现实性。随即，一大批学者和研究人员围绕着 Hopfield提出的方法展开了进一步的工作，形成了80年代中期以来人工神经网络的研究热潮。粒子群算法粒子群算法(ParticleSwarmOptimization,PSO)是由美国社会心理学家JamesKennedy和电气工程师RussellEberhart在1995年共同提出的，是继遗传算法、蚁群算法之后的又一种新的群体智能算法，目前以成为进化算法的一个重要分支。PSO基本思想是受Eberhart和Kennedy对许多鸟类群体行为进行建模与仿真研究结果的启发，而其模型及仿真算法主要利用了生物学家FrankHepper的模型：当一只鸟飞离鸟群而飞向栖息地时，将导致它周围的其他鸟也飞向栖息地，直到整个鸟群都落到栖息地。鸟群寻找栖息地与对一个特定问题寻找解很类似。正是由于这一发现，Eberhart和Kennedy对FrankHepper的模型进行修正，以使微粒能够飞向解空间并在最好解处降落。其关键在于探索和开发之间寻找一个恰到的平衡。另一方面，需要在个性与社会性之间寻求平衡，即希望个体既具有个性化，又希望其知道其他个体已经找到优解并向他们学习，即社会性。基本粒子群算法的核心步骤如下：步骤1：依照初始化过程，对微粒群的随机位置和速度进行初始设定；步骤2：计算每个微粒的适应值；步骤3：对每个微粒，将其适应值与所经历过的最好位置进行比较，若较好，则将其作为当前最好位置；步骤4：对每个微粒，将其适应值与全局所经历过的最好位置的适应值进行比较，若较好，则将其作为当前全局最好位置；步骤5:对微粒的速度和位置进行进化；步骤6:若未达到结束条件，则返回步骤 2.捕食搜索算法捕食搜索算法(PredatorySearch,PS是由巴西学者AlexandreLinhares在1998年提出来的一种用于解决组合优化问题的模拟动物捕食行为的空间搜索策略。AlexandreLinhares把捕食搜索策略分别应用于解决TSP问题和超大规模集成电路设计问题，都取得了较好的效果。捕食动物的搜索过程分为