智能优化算法综述

Nanjing University of Science and Technology

智能优化算法的统一框架

110040692

5班

2011年6月20日

目录

1 概述.............................................................. 3

2群体智能优化算法 ................................. 错误！未定义书签。

2.1人工鱼群算法 ................................................ 4

2.2蚁群算法 .................................................... 5

2.3混合蛙跳算法 ................................................ 9

3神经网络算法 ..................................................... 10

3.1神经网络知识点概述 ......................................... 10

3.2神经网络在计算机中的应用 ................................... 11

4模拟退火算法 ..................................................... 15 5遗传算法 ......................................... 错

5.1遗传算法知识简介 17

5.2遗传算法现状 18

5.3遗传算法定义 19

5.4遗传算法特点和应用 20

5.5遗传算法的一般算法 21

5.6遗传算法的基本框架 26

6总结 28

7感谢 29

1概述

近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，搜索空间则会产生搜索的组合爆炸。因此，有关搜索空间的知识，并能自适应地控制搜索过程，通用搜索算法一直是令人瞩目的课题。实践证明特别有效的算法。

2群体智能优化算法

,大都表现出惊人的完成复杂行为的能力。人们从中得到启发, ,提出了模拟生物系统,通过相互作用形 20世纪 90年代模拟蚂蚁行为的蚁群算法(ACO) ( PSO)、 模拟鱼类生 模拟青蛙觅食的混合蛙跳算法 ( SFLA)等。这些群体,使原来一些复杂的、难于用常规的优化算法进行处理的问,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点: ①群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性; ②每个个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、 方便; ③系统用于通信的开销较少,易于扩充; ④自

组织性,即群体表现出来的复杂行为是通过简单个体的交互表现出高度的智能。 本文部分内容，在群体智能优化算法范围内分别详细讨论了人工鱼群算法、蚁群算法、混合蛙跳算法等三种智能优化方法。

2.1人工鱼群算法

在一片水域中生活的鱼类一般都能找到食物丰富的地方并聚集成群。在这种群体活动中,没有统一的协调者,的。模拟鱼类生活觅食的特性,李晓磊等人于2002 (AFSA)。在此算法中,人工鱼的活动被描述为三种典型行为:行为,当发现附近有食物时,会向该方向游动; ②追尾行为:物丰富时,其它鱼会快速尾随而至: ③聚群行为: 人工鱼所处的状态可以用矢量描述: X = ( x1 ,( i = 1, 2, „, n) 是所要优化问题的变量。,表示所要优化的目标函数。di , j= ‖,人工鱼的感知距离定义为 V isua l境的拥挤程度,,当环境过分拥挤时, :

Step1:Step2::

Yi

‖Xj- Xi‖, Xi| nex t= Xi+Random ( S tep) ;

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

对于人工鱼的追尾行为:由状态 Xi转移到状态Xj能获得更好的适应值 Yj,人工鱼就向状态 Xj移动一步。否则,就转入觅食行为。人工鱼的聚群行为,当人工鱼探测到所感知的范围内具有较多食物又不拥挤时,人工鱼就向伙伴的中心移动,否则,转向觅食行为。在人工鱼群算法中设置一个公告板,用于记录最优人工鱼个体的状态,当人工鱼自身状态优于最优状态就替代之。算法具有良好的求取

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

人工鱼群算法的改进研究,如在算法中增加鱼群的协调行为,将人工鱼群算法与模拟退火算法相融和的混合智能算法等。人工鱼群算法目前已用于组合优化、 参数估计、PI D控制器的参数整定、神经网络优化等。

2.2蚁群算法

蚁群算法(ant colony optimization, ACO)在图中寻找优化路径的机率型算法。它由Marco 文中提出，种模拟进化算法,.PID控制器参数优化设计问题,,数值仿真结果表明,只蚂蚁单独行动, ,一旦某一条轨迹发现了食物,这条道路上,蚂蚁发现不同路径的距离有远、 近的区别,,并把这一情况通过路径上信息,Colorni、 Dorigo等于 ,并用这一算法解决了一系列组合优化问题。

:

Step1:初始化信息素轨迹;

Step2:生成个可行解 (蚂蚁) ;

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

Step4:确定每一只蚂蚁的最优位置 (最优解) ;

Step5:确定全局的最优位置 (最优解) ;

Step6:更新信息素轨迹;

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

在蚁群算法中,蚂蚁通过行走在不同的地点 (状态)之间转移, t时刻蚂蚁 k

在点 i向点 j的转移概率Pkij( t) 为:

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

由式 (1)可知,转移概率 Pij( t) 与τij· ηij数,相对重要性。经过 n时刻,蚂蚁完成一次循环,

:

式中:Δ τ k ( t, t +1)留在路径 ( i ,j) ,就越多;Δ ( i, j ) 的信息素的增量;ρ— — ,通常设置ρ

1、多样性、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就

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

就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。栩如生的世界，了，被环境淘汰了！ 其中，‘F’点表示食物，‘H+C++程序用地点之间的距离用矩阵来输入。

#include

最大长度

{

};

class Graph

{

private:

int arcs[MAX][MAX];

char node[MAX];

int count;

public:

void init_graph();

void dijkstra();

};

void Graph::init_graph()

{

int i;

cout

cin>>count;

cout

for( i=0;i

cin>>node[i];

cout

{

起始结点序号

int des; //终点序号

cout

cin>>sor>>des

蚁群算法中参加觅食的每一只蚂蚁都是一个单独计算的单元,由于大量的蚂蚁参与了运算,算法具有很强的并行性。蚂蚁之间通过信息素进行合作,而不是直接通信,因此随着个体的增加系统的通信开销增加的也较小。因此,蚁群算法是一

种结合了分布式计算、 正反馈机制和贪婪式搜索的算法,具有很强的搜索较优解的能力。但是蚁群算法也有搜索速度慢、陷入局部最优及搜索停滞等缺点。针对这些问题,人们对蚁群算法的机理进行了深入研究并提出许多改进措施。

2.3混合蛙跳算法

在一片湿地中生活着一群青蛙,湿地内离散地分布着许多石头,青蛙通过寻找不同的石头进行跳跃去找到食物较多的地方。高自己寻找食物的能力,群体青蛙的觅食特性,文献于2003有自己的文化,为了达到自己的目标努力,青蛙群体被分为不同的子群体,每个子群体有着自己文化在子群体中的每个个体有着自己的文化,,现子群体间的混合运算,

对于 D,只青蛙可表示为U ( i) = (U1i, U2i, „, UD i) ,根据每只青蛙适应值)这样,整个青蛙群体被 分为 m个子群体,,即池塘中的青蛙数目为 F = m·n。,第二只青蛙进入第二个子群体,一直分配下去, m m个子群体。然后,第 m + 1只青,第 m + 2只青蛙进入到第二个子群体等,这样循环分配下去,在每一个子群体中,适应值最好的个体和最差的个体记为,整个青蛙群体的最优值记为 Ug 。在每次循环中,只提高最

混合蛙跳中最差适应值 (位置 )青蛙的计算过程为:

蛙跳步长更新:

位置更新为：

Smax ≥Si≥- Smax ,其中 rand ( ) ∈ [ 0, 1 ] ( k =1, 2, „, n) , Smax是最大步长。如果计算后新的解较优,则用其替代最差个体。并且通过式 ( 6)、( 7)求全局最优解 Ug 。如果得到的解没有改进,那么随机生成新解取代所求个体的解,算法继续迭代直至迭代次数完毕。

混合蛙跳算法的算法流程如下:

Step1:针对 F只青蛙 (解) ,随机产生种群;

Step2:对每只青蛙个体,计算其适应值;

Step3:将 F只青蛙按适应值降序排列分为 m个子群体;

Step4:,在指定迭代次数内提高最差个体的适应值;

Step5:针对各个子群体,按适应值降序排列个体,; Step6:终止条件是否满足? 如果满足,,。

,和离散问题,并且具有较强的鲁棒性,非线性函数优

3神经网络算法

3.1

很多人听过这个词，但很少人真一“神经网络”这个词实际是来自于生物学，ANNs）”。在本文，我会同时使用这两个互换的术语。一个真正的神经网络是由数个至数十亿个被称为神经元的细胞（组成我们大脑的微小细胞）所组成，它们以不同方式连接而型成网络。

人工神经网络就是尝试模拟这种生物学上的体系结构及其操作。在这里有一个难题：我们对生物学上的神经网络知道的不多！因此，不同类型之间的神经网络体系结构有很大的不同，我们所知道的只是神经元基本的结构。虽然已经确认

在我们的大脑中有大约50至500种不同的神经元，但它们大部份都是基于基本神经元的特别细胞。基本神经元包含有synapses、soma、axon及dendrites。Synapses负责神经元之间的连接，它们不是直接物理上连接的，而是它们之间有一个很小的空隙允许电子讯号从一个神经元跳到另一个神经元。然后这些电子讯号会交给soma处理及以其内部电子讯号将处理结果传递给axon。而axon会将这些讯号分发给dendrites。最后，dendrites带着这些讯号再交给其它的synapses，再继续下一个循环。如同生物学上的基本神经元，（weight）出权重合计值（net value）计。每个神经元都有它们各自的临界值（threshold），值时，神经元会输出1。相反，则输出0接的其它神经元继续剩余的计算。

多不同的训练方式，就类型一样多。但有些比较出名的包括 - 监管的及非监管的。，而整个过监管方式的训练模式包括有。非监管方式的规则无需教师，因为他们所产在神经网络中，遵守明确的规则一词是最“模糊不清”Perceptrons），至复杂的自我调整网络（Kohonen），至热动态性网络模型（Boltzmann machines）！而这些，都遵守一个网络体系结构的标准。一个网络包括有多个神经元“层”，输入层、隐蔽层及输出层。输入层负责接收输入及分发到隐蔽层（因为用户看不见这些层，所以见做隐蔽层）。这些隐蔽层负责所需的计算及输出结果给输出层，而用户则可以看到最终结果。现在，为免混淆，不会在这里更深入的探讨体系结构这一话题。对于不同神经网络的更多详细资料可以看Generation5 essays尽管

我们讨论过神经元、训练及体系结构，但我们还不清楚神经网络实际做些什么。神经网络被设计为与图案一起工作 - 它们可以被分为分类式或联想式。分类式网络可以接受一组数，然后将其分类。例如ONR程序接受一个数字的影象而输出这个数字。或者PPDA32程序接受一个坐标而将它分类成A类或B类（类别是由所提供的训练决定的）。更多实际用途可以看Applications in the Military中的军事雷达，该雷达可以分别出车辆或树。联想模式接受一组数而输出另一组。例如HIR程序接受一个‘脏’联

3.2神经网络在计算机中的应用

作。神经网络也得助于神经系统科学的发展，...方。理资讯，因此，要一个串行的机器模拟并行处理是非常 - 神经网络算法是指模拟生物的网格计算是网格并行计算其目标是将广域网上一些计算资源、数据源和其他合作的高性能计算网，用户可以像登陆

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

clear

Popsize=40;

P_mutation=0.1;

P_cross=0.6;

real chrom;

real currentbest_value;

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

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

temchrom=zeros(size(chrom));

p=[0 0 0 0 1 1 1 1;0 0 1 1 0 0 1 1;1 0 1 0 1 0 1 0]; %输入值

aim=[0 1 1 0 1 0 0 1]'; % 输出值

ecope=100;

currentbest=zeros(ecope,21);

%计的染色体均方误差 fitness=8/sum(error.^2)

%

% 选择过程

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;

%变异

chrom=temchrom;

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

N=Popsize;

基因选择

chrom=chrom(s,:);

fitness_gene=fitness_gene(s);

end

% if currentbest_value(k)==1

% break

% end

end

%图表显示

i=1:k;

y=1./currentbest_value(1:k,:);

plot(i,y,'r:');

title(' sum root mean square error');

% toc

y(k)

类/。

4模拟退火算法

，SA)最早由Kirkpatrick等应用于组迭代求解策略的一种随机寻优算法，其出发模拟退,结合概率突跳特性在解即在局部最优解能概率性地跳出并最终理论上算法具有概率的全局优化性能诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis

准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。下面介绍一简单的模拟退火算法原理。优化问题：

minf(x)

s.t.g(x)0

xD

其中f(x)为目标函数，g(x)D Step1 xoixo；k:0;totmax(初始尺度)

Step2 Step3；否则，从邻域N(xi)中随机选一xjfij)(xi)；若fij0，则xi:xj，否则若exp(fij)/tkra1)xixj；重复Step2；

tk1tkk:k1；若满足停止条件，终止计算；否则，返回Step2。

包含一个内循环和一个外循环。内循环是Step2，tk时，在一些状态随机搜索。外循环包括Step3的温度下降变化tk1:d(tk)，迭代步数的增加k:k1和停止条件。模拟退火的直观理解是：在一个给定温度，搜索从一个状态随机地变化到另一个状态。每一个状态到达的次数服从一个概率分布。当温度很低时，以概率1停留在最优解。

5遗传算法（Genetic Algorithm）

5.1遗传算法知识简介

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《》，GA这个名称才逐渐为人所知，J.Holland教授所提出的（SGA）。其主要特点是直接对结构对象进行操作，定；具有内在的隐并行性和更好的全局寻优能力；能自动获取和指导优化的搜索空间，遗

a)初始化:，T，随机生成M个个体作为初始群体P(0)。

b)

c)选择操作是建立在群体

d)所谓交叉是指把两个父代个体的部分子。

e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。

群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。

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

5.2遗传算法的现状

随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21展，和另一个称为人工生命的崭新研究领域正不断渗透。模拟自然界丰富多彩的生命现象，生命的重要研究对象，五是遗传算法和进化规划（Evolution

Strategy,ESEP和ES几乎是和遗传算法同时独立发展起来的，

1991年（Adjacency based crossoverTSP

等提出了随机迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。 H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个

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

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

2004不高的现象，提出了一种用基因块编码的并行遗传算法（Coded Parallel GA，BCPGA产生长度较短的染色体，的初始群体。

2005年，TSP问题,持群体的多样性,,

5.3遗传算法的定义

population）开始的，（(individual)组成。每带有特征的实体。染色体作为遗传物质的主如黑头发的特征是由染色体中控制这一特征的某种基我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

5.4遗传算法的特点和应用

遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：

① 首先组成一组候选解；

② 依据某些适应性条件测算这些候选解的适应度；

③ 根据适应度保留某些候选解，放弃其他候选解；

④ 对保留的候选解进行某些操作，生成新的候选解。

基于染色体群的并行搜索，

遗传算法还具有以下几方面的特点：

(1)

(2)减少了陷入

(3)适应度函数不仅不受连续可微的约

(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：

函数优化：

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。

组合优化：

随着问题规模的增大，有时在目前的计算上用枚举法很难求出最优解。精力放在寻求满意解上，实践证明，遗传算法对于组合优化中的NP行商问题、

此外，GA

5.5下面是遗传算法的一般算法：

1

将这些解比喻为染色体或基因，该种群在那里问题的初始状态已经给定了。2

对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。

3）繁殖、下一代

繁殖(包括子代突变)

带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。

下一代

如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。

4）并行计算

点当成一个并行的种群看待。另一个节点。另一种方法是“农场主/

5）终止条件

或者最优个体的适应度和群体适应度不再上升时，算法终止。预设的代数一般设置为100-500代。

4.6 在遗传算法中，通过编码组成初始群(适应度评估)从优化搜索的角度而言，遗传

(genetic operator):选择

(selection)；交叉。这三个遗传算子有如下特点: 因此，群体中个体向最这种随机化操作和传统的随机搜索方法是有区别的。行的无向搜索。

编码方法，群体大小，

1）选择

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种:适应度比例方法、随机遍历抽样法、局部选择法。

其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率,为遗传算法

显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例.[0，1]之间均匀随机数，可随机地组成交配对，以供后面的交叉操作。

2）交叉

(加上变异)。同样，遗传算法的搜索能力得以飞跃提高。

能够产生新的基因组合，根据编码表示方法的不同，可以有以下的算法：

a)）

1)离散重组（）；

）；

3)linear recombination）；

4)extended linear recombination）。

b)二进制交叉（binary valued crossover）

1)单点交叉（single-point crossover）；

2)多点交叉（multiple-point crossover）；

3)均匀交叉（uniform crossover）；

4)洗牌交叉（shuffle crossover）；

5)缩小代理交叉（crossover with reduced surrogate）。

最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：

个体A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体

个体B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体

3）变异

依据个体编码表示方法的不同，可以有以下的算法：

a)实值变异；

b)二进制变异。

一般来说，变异算子操作的基本步骤如下:

a)

b)

遗传算法引入变异的目的有两个:力。利用变异算子的这种局部随二是使遗传算法可维持群体多样

变异算子因其局.是指当群体通过变异操作可有所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。

基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下:

基因位下方标有*号的基因发生变异。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。

5.6基本框架 GA

流程图：

GA的流程图

必须把它们转换成遗传空间的由基(问题的)表示(representation)。

评估编码策略常采用以下3个规范:

a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。

b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。

c)非冗余性(nonredundancy):染色体和候选解一一对应。

目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。

而二进值编码是目前遗传算法中最常用的编码方法。即是由二进值字符集{0, 1}产生通常的0, 1字符串来表示问题空间的候选解。它具有以下特点:

a)简单易行；

b)符合最小字符集编码原则；

c)2）适应度函数

进化论中的适应度，后代的能力。遗传算法的适应度函数也叫评价函数，

个体或解的优劣，适应度函数要所以适应度函数的值要取正值.由此可见，在不少场合，的。

a

b)

d

适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。

3）初始群体的选取

遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:

a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模

6总结

络算法，模拟退火算法和遗传算法。互相渗透、互相影响的时代，个典型例子，甚至同一学科的不同方法，相互协调， 优化算法的性能,使算法在处理不,这些优点正是群体智能优化算法研

7感谢

首先，他知识渊博的风度，态度严谨的风格，给我留下了很深的印象，的算法理论课时，到真本事。其次，本次报告完成也不例外。在此，对王伟，

年6月20日

Nanjing University of Science and Technology

智能优化算法的统一框架

110040692

5班

2011年6月20日

目录

1 概述.............................................................. 3

2群体智能优化算法 ................................. 错误！未定义书签。

2.1人工鱼群算法 ................................................ 4

2.2蚁群算法 .................................................... 5

2.3混合蛙跳算法 ................................................ 9

3神经网络算法 ..................................................... 10

3.1神经网络知识点概述 ......................................... 10

3.2神经网络在计算机中的应用 ................................... 11

4模拟退火算法 ..................................................... 15 5遗传算法 ......................................... 错

5.1遗传算法知识简介 17

5.2遗传算法现状 18

5.3遗传算法定义 19

5.4遗传算法特点和应用 20

5.5遗传算法的一般算法 21

5.6遗传算法的基本框架 26

6总结 28

7感谢 29

1概述

近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，搜索空间则会产生搜索的组合爆炸。因此，有关搜索空间的知识，并能自适应地控制搜索过程，通用搜索算法一直是令人瞩目的课题。实践证明特别有效的算法。

2群体智能优化算法

,大都表现出惊人的完成复杂行为的能力。人们从中得到启发, ,提出了模拟生物系统,通过相互作用形 20世纪 90年代模拟蚂蚁行为的蚁群算法(ACO) ( PSO)、 模拟鱼类生 模拟青蛙觅食的混合蛙跳算法 ( SFLA)等。这些群体,使原来一些复杂的、难于用常规的优化算法进行处理的问,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点: ①群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性; ②每个个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、 方便; ③系统用于通信的开销较少,易于扩充; ④自

组织性,即群体表现出来的复杂行为是通过简单个体的交互表现出高度的智能。 本文部分内容，在群体智能优化算法范围内分别详细讨论了人工鱼群算法、蚁群算法、混合蛙跳算法等三种智能优化方法。

2.1人工鱼群算法

在一片水域中生活的鱼类一般都能找到食物丰富的地方并聚集成群。在这种群体活动中,没有统一的协调者,的。模拟鱼类生活觅食的特性,李晓磊等人于2002 (AFSA)。在此算法中,人工鱼的活动被描述为三种典型行为:行为,当发现附近有食物时,会向该方向游动; ②追尾行为:物丰富时,其它鱼会快速尾随而至: ③聚群行为: 人工鱼所处的状态可以用矢量描述: X = ( x1 ,( i = 1, 2, „, n) 是所要优化问题的变量。,表示所要优化的目标函数。di , j= ‖,人工鱼的感知距离定义为 V isua l境的拥挤程度,,当环境过分拥挤时, :

Step1:Step2::

Yi

‖Xj- Xi‖, Xi| nex t= Xi+Random ( S tep) ;

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

对于人工鱼的追尾行为:由状态 Xi转移到状态Xj能获得更好的适应值 Yj,人工鱼就向状态 Xj移动一步。否则,就转入觅食行为。人工鱼的聚群行为,当人工鱼探测到所感知的范围内具有较多食物又不拥挤时,人工鱼就向伙伴的中心移动,否则,转向觅食行为。在人工鱼群算法中设置一个公告板,用于记录最优人工鱼个体的状态,当人工鱼自身状态优于最优状态就替代之。算法具有良好的求取

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

人工鱼群算法的改进研究,如在算法中增加鱼群的协调行为,将人工鱼群算法与模拟退火算法相融和的混合智能算法等。人工鱼群算法目前已用于组合优化、 参数估计、PI D控制器的参数整定、神经网络优化等。

2.2蚁群算法

蚁群算法(ant colony optimization, ACO)在图中寻找优化路径的机率型算法。它由Marco 文中提出，种模拟进化算法,.PID控制器参数优化设计问题,,数值仿真结果表明,只蚂蚁单独行动, ,一旦某一条轨迹发现了食物,这条道路上,蚂蚁发现不同路径的距离有远、 近的区别,,并把这一情况通过路径上信息,Colorni、 Dorigo等于 ,并用这一算法解决了一系列组合优化问题。

:

Step1:初始化信息素轨迹;

Step2:生成个可行解 (蚂蚁) ;

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

Step4:确定每一只蚂蚁的最优位置 (最优解) ;

Step5:确定全局的最优位置 (最优解) ;

Step6:更新信息素轨迹;

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

在蚁群算法中,蚂蚁通过行走在不同的地点 (状态)之间转移, t时刻蚂蚁 k

在点 i向点 j的转移概率Pkij( t) 为:

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

由式 (1)可知,转移概率 Pij( t) 与τij· ηij数,相对重要性。经过 n时刻,蚂蚁完成一次循环,

:

式中:Δ τ k ( t, t +1)留在路径 ( i ,j) ,就越多;Δ ( i, j ) 的信息素的增量;ρ— — ,通常设置ρ

1、多样性、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就

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

就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。栩如生的世界，了，被环境淘汰了！ 其中，‘F’点表示食物，‘H+C++程序用地点之间的距离用矩阵来输入。

#include

最大长度

{

};

class Graph

{

private:

int arcs[MAX][MAX];

char node[MAX];

int count;

public:

void init_graph();

void dijkstra();

};

void Graph::init_graph()

{

int i;

cout

cin>>count;

cout

for( i=0;i

cin>>node[i];

cout

{

起始结点序号

int des; //终点序号

cout

cin>>sor>>des

蚁群算法中参加觅食的每一只蚂蚁都是一个单独计算的单元,由于大量的蚂蚁参与了运算,算法具有很强的并行性。蚂蚁之间通过信息素进行合作,而不是直接通信,因此随着个体的增加系统的通信开销增加的也较小。因此,蚁群算法是一

种结合了分布式计算、 正反馈机制和贪婪式搜索的算法,具有很强的搜索较优解的能力。但是蚁群算法也有搜索速度慢、陷入局部最优及搜索停滞等缺点。针对这些问题,人们对蚁群算法的机理进行了深入研究并提出许多改进措施。

2.3混合蛙跳算法

在一片湿地中生活着一群青蛙,湿地内离散地分布着许多石头,青蛙通过寻找不同的石头进行跳跃去找到食物较多的地方。高自己寻找食物的能力,群体青蛙的觅食特性,文献于2003有自己的文化,为了达到自己的目标努力,青蛙群体被分为不同的子群体,每个子群体有着自己文化在子群体中的每个个体有着自己的文化,,现子群体间的混合运算,

对于 D,只青蛙可表示为U ( i) = (U1i, U2i, „, UD i) ,根据每只青蛙适应值)这样,整个青蛙群体被 分为 m个子群体,,即池塘中的青蛙数目为 F = m·n。,第二只青蛙进入第二个子群体,一直分配下去, m m个子群体。然后,第 m + 1只青,第 m + 2只青蛙进入到第二个子群体等,这样循环分配下去,在每一个子群体中,适应值最好的个体和最差的个体记为,整个青蛙群体的最优值记为 Ug 。在每次循环中,只提高最

混合蛙跳中最差适应值 (位置 )青蛙的计算过程为:

蛙跳步长更新:

位置更新为：

Smax ≥Si≥- Smax ,其中 rand ( ) ∈ [ 0, 1 ] ( k =1, 2, „, n) , Smax是最大步长。如果计算后新的解较优,则用其替代最差个体。并且通过式 ( 6)、( 7)求全局最优解 Ug 。如果得到的解没有改进,那么随机生成新解取代所求个体的解,算法继续迭代直至迭代次数完毕。

混合蛙跳算法的算法流程如下:

Step1:针对 F只青蛙 (解) ,随机产生种群;

Step2:对每只青蛙个体,计算其适应值;

Step3:将 F只青蛙按适应值降序排列分为 m个子群体;

Step4:,在指定迭代次数内提高最差个体的适应值;

Step5:针对各个子群体,按适应值降序排列个体,; Step6:终止条件是否满足? 如果满足,,。

,和离散问题,并且具有较强的鲁棒性,非线性函数优

3神经网络算法

3.1

很多人听过这个词，但很少人真一“神经网络”这个词实际是来自于生物学，ANNs）”。在本文，我会同时使用这两个互换的术语。一个真正的神经网络是由数个至数十亿个被称为神经元的细胞（组成我们大脑的微小细胞）所组成，它们以不同方式连接而型成网络。

人工神经网络就是尝试模拟这种生物学上的体系结构及其操作。在这里有一个难题：我们对生物学上的神经网络知道的不多！因此，不同类型之间的神经网络体系结构有很大的不同，我们所知道的只是神经元基本的结构。虽然已经确认

在我们的大脑中有大约50至500种不同的神经元，但它们大部份都是基于基本神经元的特别细胞。基本神经元包含有synapses、soma、axon及dendrites。Synapses负责神经元之间的连接，它们不是直接物理上连接的，而是它们之间有一个很小的空隙允许电子讯号从一个神经元跳到另一个神经元。然后这些电子讯号会交给soma处理及以其内部电子讯号将处理结果传递给axon。而axon会将这些讯号分发给dendrites。最后，dendrites带着这些讯号再交给其它的synapses，再继续下一个循环。如同生物学上的基本神经元，（weight）出权重合计值（net value）计。每个神经元都有它们各自的临界值（threshold），值时，神经元会输出1。相反，则输出0接的其它神经元继续剩余的计算。

多不同的训练方式，就类型一样多。但有些比较出名的包括 - 监管的及非监管的。，而整个过监管方式的训练模式包括有。非监管方式的规则无需教师，因为他们所产在神经网络中，遵守明确的规则一词是最“模糊不清”Perceptrons），至复杂的自我调整网络（Kohonen），至热动态性网络模型（Boltzmann machines）！而这些，都遵守一个网络体系结构的标准。一个网络包括有多个神经元“层”，输入层、隐蔽层及输出层。输入层负责接收输入及分发到隐蔽层（因为用户看不见这些层，所以见做隐蔽层）。这些隐蔽层负责所需的计算及输出结果给输出层，而用户则可以看到最终结果。现在，为免混淆，不会在这里更深入的探讨体系结构这一话题。对于不同神经网络的更多详细资料可以看Generation5 essays尽管

我们讨论过神经元、训练及体系结构，但我们还不清楚神经网络实际做些什么。神经网络被设计为与图案一起工作 - 它们可以被分为分类式或联想式。分类式网络可以接受一组数，然后将其分类。例如ONR程序接受一个数字的影象而输出这个数字。或者PPDA32程序接受一个坐标而将它分类成A类或B类（类别是由所提供的训练决定的）。更多实际用途可以看Applications in the Military中的军事雷达，该雷达可以分别出车辆或树。联想模式接受一组数而输出另一组。例如HIR程序接受一个‘脏’联

3.2神经网络在计算机中的应用

作。神经网络也得助于神经系统科学的发展，...方。理资讯，因此，要一个串行的机器模拟并行处理是非常 - 神经网络算法是指模拟生物的网格计算是网格并行计算其目标是将广域网上一些计算资源、数据源和其他合作的高性能计算网，用户可以像登陆

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

clear

Popsize=40;

P_mutation=0.1;

P_cross=0.6;

real chrom;

real currentbest_value;

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

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

temchrom=zeros(size(chrom));

p=[0 0 0 0 1 1 1 1;0 0 1 1 0 0 1 1;1 0 1 0 1 0 1 0]; %输入值

aim=[0 1 1 0 1 0 0 1]'; % 输出值

ecope=100;

currentbest=zeros(ecope,21);

%计的染色体均方误差 fitness=8/sum(error.^2)

%

% 选择过程

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;

%变异

chrom=temchrom;

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

N=Popsize;

基因选择

chrom=chrom(s,:);

fitness_gene=fitness_gene(s);

end

% if currentbest_value(k)==1

% break

% end

end

%图表显示

i=1:k;

y=1./currentbest_value(1:k,:);

plot(i,y,'r:');

title(' sum root mean square error');

% toc

y(k)

类/。

4模拟退火算法

，SA)最早由Kirkpatrick等应用于组迭代求解策略的一种随机寻优算法，其出发模拟退,结合概率突跳特性在解即在局部最优解能概率性地跳出并最终理论上算法具有概率的全局优化性能诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis

准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。下面介绍一简单的模拟退火算法原理。优化问题：

minf(x)

s.t.g(x)0

xD

其中f(x)为目标函数，g(x)D Step1 xoixo；k:0;totmax(初始尺度)

Step2 Step3；否则，从邻域N(xi)中随机选一xjfij)(xi)；若fij0，则xi:xj，否则若exp(fij)/tkra1)xixj；重复Step2；

tk1tkk:k1；若满足停止条件，终止计算；否则，返回Step2。

包含一个内循环和一个外循环。内循环是Step2，tk时，在一些状态随机搜索。外循环包括Step3的温度下降变化tk1:d(tk)，迭代步数的增加k:k1和停止条件。模拟退火的直观理解是：在一个给定温度，搜索从一个状态随机地变化到另一个状态。每一个状态到达的次数服从一个概率分布。当温度很低时，以概率1停留在最优解。

5遗传算法（Genetic Algorithm）

5.1遗传算法知识简介

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《》，GA这个名称才逐渐为人所知，J.Holland教授所提出的（SGA）。其主要特点是直接对结构对象进行操作，定；具有内在的隐并行性和更好的全局寻优能力；能自动获取和指导优化的搜索空间，遗

a)初始化:，T，随机生成M个个体作为初始群体P(0)。

b)

c)选择操作是建立在群体

d)所谓交叉是指把两个父代个体的部分子。

e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。

群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。

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

5.2遗传算法的现状

随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21展，和另一个称为人工生命的崭新研究领域正不断渗透。模拟自然界丰富多彩的生命现象，生命的重要研究对象，五是遗传算法和进化规划（Evolution

Strategy,ESEP和ES几乎是和遗传算法同时独立发展起来的，

1991年（Adjacency based crossoverTSP

等提出了随机迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。 H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个

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

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

2004不高的现象，提出了一种用基因块编码的并行遗传算法（Coded Parallel GA，BCPGA产生长度较短的染色体，的初始群体。

2005年，TSP问题,持群体的多样性,,

5.3遗传算法的定义

population）开始的，（(individual)组成。每带有特征的实体。染色体作为遗传物质的主如黑头发的特征是由染色体中控制这一特征的某种基我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

5.4遗传算法的特点和应用

遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：

① 首先组成一组候选解；

② 依据某些适应性条件测算这些候选解的适应度；

③ 根据适应度保留某些候选解，放弃其他候选解；

④ 对保留的候选解进行某些操作，生成新的候选解。

基于染色体群的并行搜索，

遗传算法还具有以下几方面的特点：

(1)

(2)减少了陷入

(3)适应度函数不仅不受连续可微的约

(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：

函数优化：

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。

组合优化：

随着问题规模的增大，有时在目前的计算上用枚举法很难求出最优解。精力放在寻求满意解上，实践证明，遗传算法对于组合优化中的NP行商问题、

此外，GA

5.5下面是遗传算法的一般算法：

1

将这些解比喻为染色体或基因，该种群在那里问题的初始状态已经给定了。2

对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。

3）繁殖、下一代

繁殖(包括子代突变)

带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。

下一代

如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。

4）并行计算

点当成一个并行的种群看待。另一个节点。另一种方法是“农场主/

5）终止条件

或者最优个体的适应度和群体适应度不再上升时，算法终止。预设的代数一般设置为100-500代。

4.6 在遗传算法中，通过编码组成初始群(适应度评估)从优化搜索的角度而言，遗传

(genetic operator):选择

(selection)；交叉。这三个遗传算子有如下特点: 因此，群体中个体向最这种随机化操作和传统的随机搜索方法是有区别的。行的无向搜索。

编码方法，群体大小，

1）选择

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproduction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种:适应度比例方法、随机遍历抽样法、局部选择法。

其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率,为遗传算法

显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例.[0，1]之间均匀随机数，可随机地组成交配对，以供后面的交叉操作。

2）交叉

(加上变异)。同样，遗传算法的搜索能力得以飞跃提高。

能够产生新的基因组合，根据编码表示方法的不同，可以有以下的算法：

a)）

1)离散重组（）；

）；

3)linear recombination）；

4)extended linear recombination）。

b)二进制交叉（binary valued crossover）

1)单点交叉（single-point crossover）；

2)多点交叉（multiple-point crossover）；

3)均匀交叉（uniform crossover）；

4)洗牌交叉（shuffle crossover）；

5)缩小代理交叉（crossover with reduced surrogate）。

最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：

个体A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体

个体B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体

3）变异

依据个体编码表示方法的不同，可以有以下的算法：

a)实值变异；

b)二进制变异。

一般来说，变异算子操作的基本步骤如下:

a)

b)

遗传算法引入变异的目的有两个:力。利用变异算子的这种局部随二是使遗传算法可维持群体多样

变异算子因其局.是指当群体通过变异操作可有所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。

基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下:

基因位下方标有*号的基因发生变异。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。

5.6基本框架 GA

流程图：

GA的流程图

必须把它们转换成遗传空间的由基(问题的)表示(representation)。

评估编码策略常采用以下3个规范:

a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。

b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。

c)非冗余性(nonredundancy):染色体和候选解一一对应。

目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。

而二进值编码是目前遗传算法中最常用的编码方法。即是由二进值字符集{0, 1}产生通常的0, 1字符串来表示问题空间的候选解。它具有以下特点:

a)简单易行；

b)符合最小字符集编码原则；

c)2）适应度函数

进化论中的适应度，后代的能力。遗传算法的适应度函数也叫评价函数，

个体或解的优劣，适应度函数要所以适应度函数的值要取正值.由此可见，在不少场合，的。

a

b)

d

适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。

3）初始群体的选取

遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:

a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模

6总结

络算法，模拟退火算法和遗传算法。互相渗透、互相影响的时代，个典型例子，甚至同一学科的不同方法，相互协调， 优化算法的性能,使算法在处理不,这些优点正是群体智能优化算法研

7感谢

首先，他知识渊博的风度，态度严谨的风格，给我留下了很深的印象，的算法理论课时，到真本事。其次，本次报告完成也不例外。在此，对王伟，

年6月20日