智能优化算法综述.docx

智能优化算法综述.docx

《智能优化算法综述.docx》由会员分享，可在线阅读，更多相关《智能优化算法综述.docx（23页珍藏版）》请在冰点文库上搜索。

智能优化算法综述

智能优化算法的统一框架

指导老师：

叶晓东教授

姓名：

***

学号：

2

班级：

电磁场与微波技术5班

2011年6月20日

4模拟退火算法15

1概述

近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。

众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。

像货朗担问题和规划问题等组合优化问题就是典型的例子。

在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。

因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。

智能优化算法就是在这种背景下产生并经实践证明特别有效的算法。

2群体智能优化算法

自然界中群体生活的昆虫、动物,大都表现出惊人的完成复杂行为的能力。

人们从中得到启发,参考群体生活的昆虫、动物的社会行为,提出了模拟生物系统中群体生活习性的群体智能优化算法。

在群体智能优化算法中每一个个体都是具有经验和智慧的智能体（Agent）,个体之间存在互相作用机制,通过相互作用形成强大的群体智慧来解决复杂的问题。

自20世纪90年代模拟蚂蚁行为的蚁群算法（ACO）提出以来,又产生了模拟鸟类行为的微粒群算法（PSO）、模拟鱼类生存习性的人工鱼群算法、模拟青蛙觅食的混合蛙跳算法（SFLA）等。

这些群体智能优化算法的出现,使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。

群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点:

①群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性;②每个个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、方便;③系统用于通信的开销较少,易于扩充;④自组织性,即群体表现出来的复杂行为是通过简单个体的交互表现出高度的智能。

本文部分内容，在群体智能优化算法范围内分别详细讨论了人工鱼群算法、蚁群算法、混合蛙跳算法等三种智能优化方法。

人工鱼群算法

在一片水域中生活的鱼类一般都能找到食物丰富的地方并聚集成群。

在这种群体活动中,没有统一的协调者,而是通过鱼类每个个体的自适应行为而达到目的。

模拟鱼类生活觅食的特性,李晓磊等人于2002年提出人工鱼群算法（AFSA）。

在此算法中,人工鱼的活动被描述为三种典型行为:

①觅食行为:

这是鱼的基本行为,当发现附近有食物时,会向该方向游动;②追尾行为:

当某条鱼发现该处食物丰富时,其它鱼会快速尾随而至:

③聚群行为:

它们往往能形成非常庞大的群。

人工鱼所处的状态可以用矢量描述:

X=（x1,x2,…,xn）,xi（i=1,2,…,n）是所要优化问题的变量。

Y=f（X）为人工鱼的食物密度,表示所要优化的目标函数。

di,j=‖Xi-Xj‖为两条人工鱼之间的距离,人工鱼的感知距离定义为Visual距离。

在人工鱼群算法中定义拥挤因子表示人工鱼所处环境的拥挤程度,人工鱼在食物较多而又不拥挤的环境下捕食,当环境过分拥挤时它就会离开这个环境,游往别处。

人工鱼群算法觅食行为如下:

Step1:

设置最大尝试次数;

Step2:

人工鱼从一个状态转移到另一个状态:

Xj=Xi+Random（Visual）;

Step3:

如果适应值Yi

‖Xj-Xi‖;否则,Xi|next=Xi+Random（Step）;

Step4:

检查终止条件,如果条件满足结束迭带,否则转Step2。

对于人工鱼的追尾行为:

由状态Xi转移到状态Xj能获得更好的适应值Yj,人工鱼就向状态Xj移动一步。

否则,就转入觅食行为。

人工鱼的聚群行为,当人工鱼探测到所感知的范围内具有较多食物又不拥挤时,人工鱼就向伙伴的中心移动,否则,转向觅食行为。

在人工鱼群算法中设置一个公告板,用于记录最优人工鱼个体的状态,当人工鱼自身状态优于最优状态就替代之。

算法具有良好的求取全局极值能力,并具有对初值、参数选择不敏感、鲁棒性强、简单易实现等诸多优点,但是当问题规模过大时求解困难并且求解初期收敛较快,后期较慢。

人工鱼群算法的改进研究,如在算法中增加鱼群的协调行为,将人工鱼群算法与模拟退火算法相融和的混合智能算法等。

人工鱼群算法目前已用于组合优化、参数估计、PID控制器的参数整定、神经网络优化等。

蚁群算法

蚁群算法（antcolonyoptimization,ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。

它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

蚂蚁是一类社会性很强的生物,它们群体生活、共同觅食。

在觅食过程中每只蚂蚁单独行动,蚂蚁之间通过信息素的释放来对觅食的轨迹进行“记忆”,一旦某一条轨迹发现了食物,那么其它蚂蚁就会向这条道路进行聚集,这条道路上的信息素的量就会增多。

如果在觅食的过程中,蚂蚁发现不同路径的距离有远、近的区别,则蚂蚁就会选择最近的路径进行觅食,并把这一情况通过路径上信息素量的大小通知给其它蚂蚁。

受到蚂蚁觅食现象的启发,Colorni、Dorigo等于1991年首次提出了蚁群算法,并用这一算法解决了一系列组合优化问题。

基本蚁群算法的求解过程:

Step1:

设置参数,初始化信息素轨迹;

Step2:

生成m个可行解（蚂蚁）;

Step3:

对每一个蚂蚁个体,计算其适应度;

Step4:

确定每一只蚂蚁的最优位置（最优解）;

Step5:

确定全局的最优位置（最优解）;

Step6:

更新信息素轨迹;

Step7:

判断终止条件是否满足,若满足则终止迭代,否则返回Step3。

在蚁群算法中,蚂蚁通过行走在不同的地点（状态）之间转移,t时刻蚂蚁k在点i向点j的转移概率Pkij（t）为:

式中:

ηij—边（i,j）的能见度,反映由点i转移到点j的启发程度,这个量在蚂蚁系统的运行中不改变;τij—边（i,j）上的信息素轨迹强度;Pkij—蚂蚁k的转移概率,j是尚未访问的点;allowedk—蚂蚁k下一步允许选择的点,allowed={0,1,…,n-1};r—蚂蚁可以到达的位置。

由式

（1）可知,转移概率Pij（t）与τij·ηij成正比。

α和β为两个参数,分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。

经过n时刻,蚂蚁完成一次循环,各路径上信息素量根据下式调整:

式中:

Δτij（t,t+1）———第k只蚂蚁在时刻（t,t+1）留在路径（i,j）上的信息素量,其值大小视蚂蚁表现的优劣而定。

路径越短信息素释放就越多;Δτij（t,t+1）———本次循环中路径（i,j）的信息素的增量;ρ———信息素挥发系数,通常设置ρ<1来避免路径上轨迹量的无限累加。

通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：

1、多样性2、正反馈多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。

我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。

正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。

引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。

如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。

这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。

既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的多样性和正反馈又是哪里来的我本人的意见：

规则来源于大自然的进化。

而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。

而这样的巧妙结合又是为什么呢为什么在你眼前呈现的世界是如此栩栩如生呢答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！

蚁群算法的实现下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。

其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’就是蚂蚁了。

下面给出了一段求最优路径的蚁群算法的C++程序用vc++来运行，地点之间的距离用矩阵来输入。

#include

usingnamespacestd;

constintMAX=100;

.是的，神经网络也有些不好的地方。

这通常都是因为缺乏足够强大的硬件。

神经网络的力量源自于以并行方式处理资讯，即是同时处理多项数据。

因此，要一个串行的机器模拟并行处理是非常耗时的。

神经网络的另一个问题是对某一个问题构建网络所定义的条件不足-有太多因素需要考虑：

训练的算法、体系结构、每层的神经元个数、有多少层、数据的表现等，还有其它更多因素。

因此，随着时间越来越重要，大部份公司不可能负担重复的开发神经网络去有效地解决问题。

神经网络算法是指模拟生物的神经结构以及其处理信息的方式来进行计算一种算法。

网格计算是网格并行计算的一种，另一种是机群计算，其目标是将广域网上一些计算资源、数据源和其他设备等互联，形成一个大的可相互利用、合作的高性能计算网，用户可以像登陆一台超级巨型机一样使用它。

下面是一个基因算法在人工神经元网络中的应用的matlab程序：

clear

Popsize=40;

P_mutation=;

P_cross=;

realchrom;

realcurrentbest_value;

m=25;%权值和阈值的初始化范围

chrom=2*m.*rand（Popsize,21）-m;%产生初始种群

temchrom=zeros（size（chrom））;

p=[00001111;00110011;10101010];%输入值

aim=[01101001]';%输出值

ecope=100;

currentbest=zeros（ecope,21）;

currentbest_value=zeros（ecope,1）;

fitness_gene=fitness（chrom,p,aim）;%计算的染色体均方误差fitness=8/sum（error.^2）

[c_valuec_order]=max（fitness_gene）;

fork=1:

ecope

%保留当前最好染色体

[c_valuec_order]=max（fitness_gene）;

currentbest（k,:

）=chrom（c_order,:

）;

currentbest_value（k）=c_value;

%选择过程

fit=cumsum（fitness_gene）/sum（fitness_gene）;

N=Popsize;

s=select（fit,N）;

temchrom=chrom（s,:

）;

%交叉

P=rand（1,N）;

prob=find（P

crosschrom=temchrom（prob,:

）;

crosschrom=cross_over（crosschrom）;

temchrom（prob,:

）=crosschrom;

%变异

temchrom=mutation（temchrom,P_mutation,Popsize,ecope）;

chrom=temchrom;

%计算交叉变异之后的染色体的适应度

fitness_gene=fitness（chrom,p,aim）;

fit=cumsum（fitness_gene）/sum（fitness_gene）;

N=Popsize;

s=select（fit,N-1）;

[s_values_order]=max（fitness_gene）;

ifs_value

chrom=[chrom（s,:

）;currentbest（k,:

）];

fitness_gene=[fitness_gene（s）;currentbest_value（k）];

else

s=[ss_order

（1）];

chrom=chrom（s,:

）;

fitness_gene=fitness_gene（s）;

end

%ifcurrentbest_value（k）==1

%break

%end

end

%图表显示

i=1:

k;

y=1./currentbest_value（1:

k,:

）;

plot（i,y,'r:

'）;

title（'sumrootmeansquareerror'）;

%toc

y（k）

总之，神经网络在这个领域中有很多优点，使得它越来越流行。

它在类型分类/识别方面非常出色。

神经网络可以处理例外及不正常的输入数据，这对于很多系统都很重要（例如雷达及声波定位系统）。

4模拟退火算法

模拟退火算法（SimulatedAnnealing，SA）最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。

用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：

由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

退火过程由冷却进度表（CoolingSchedule）控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

下面介绍一简单的模拟退火算法原理。

我们假设算法用以解决如下的组合最优化问题：

min

.

其中

为目标函数，

为约束方程，D为定义域。

简单的模拟退火算法为：

Step1任选一个初始解

；

；

;

（初始尺度）

Step2若在该温度达到内循环停止条件，则到Step3；否则，从邻域

中随机选一

，计算

；若

，则

，否则若

时，则

；重复Step2；

Step3

；若满足停止条件，终止计算；否则，返回Step2。

在上述的模拟退火算法中，包含一个内循环和一个外循环。

内循环是Step2，他表示在同一个温度

时，在一些状态随机搜索。

外循环包括Step3的温度下降变化

，迭代步数的增加

和停止条件。

模拟退火的直观理解是：

在一个给定温度，搜索从一个状态随机地变化到另一个状态。

每一个状态到达的次数服从一个概率分布。

当温度很低时，以概率1停留在最优解。

5遗传算法（GeneticAlgorithm）

遗传算法知识简介

遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，教授所提出的GA通常为简单遗传算法（SGA）。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。

遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

它是现代有关智能计算中的关键技术。

遗传算法的基本运算过程如下:

　　a）初始化:

设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P（0）。

　　b）个体评价:

计算群体P（t）中各个个体的适应度。

　　c）选择运算:

将选择算子作用于群体。

选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

选择操作是建立在群体中个体的适应度评估基础上的。

　　d）交叉运算；将交叉算子作用于群体。

所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。

遗传算法中起核心作用的就是交叉算子。

　　e）变异运算:

将变异算子作用于群体。

即是对群体中的个体串的某些基因座上的基因值作变动。

　　群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t1）。

　　f）终止条件判断:

若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

遗传算法的现状

随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：

一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。

这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。

二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。

三是并行处理的遗传算法的研究十分活跃。

这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。

四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。

所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（EvolutionProgramming,EP）以及进化策略（EvolutionStrategy,ES）等进化计算理论日益结合。

EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。

目前，这三者之间的比较研究和彼此结合的探讨正形成热点。

　　1991年在他的论文中提出了基于领域交叉的交叉算子（Adjacencybasedcrossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。

　　等提出了随机迭代遗传爬山法（StochasticIteratedGeneticHill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。

实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。

　　和将遗传算法与单一方法（simplexmethod）结合起来，形成了一种叫单一操作的多亲交叉算子（simplexcrossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。

同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。

　　国内也有不少的专家和学者对遗传算法的交叉算子进行改进。

2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题

　　2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-blockCodedParallelGA，BCPGA）。

该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。

2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。

遗传算法的定义

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。

每个个体实际上是染色体（chromosome）带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

因此，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算