3.1 特点 5 Z3 ^& {4 P Y& H
9 ^7 \5 f6 l5 h$ `$ m+ c' O, l
遗传算法是解决搜索问题的一种通用算法,对于各种通用问题都可以使用。搜索算法的共同特征为: ① 首先组成一组候选解; ② 依据某些适应性条件测算这些候选解的适应度; ③ 根据适应度保留某些候选解,放弃其他候选解; ④ 对保留的候选解进行某些操作,生成新的候选解。在遗传算法中,上述几个特征以一种特殊的方式组合在一起:基于染色体群的并行搜索,带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。 ( b2 P x8 U% s+ ]; N* e
遗传算法还具有以下几方面的特点: . [9 C* X1 ~: J8 Z3 X- Q" j3 C ( Z* w: v* k# j(1)遗传算法从问题解的串集开始嫂索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的;容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。* s5 a' J1 M2 y6 E
+ @8 X, D) n5 O6 O' e$ G; e4 F( S
(2)许多传统搜索算法都是单点搜索算法,容易陷入局部的最优解。遗传算法同时处理群体中的多个个体,即对搜索空间中的多个解进行评估,减少了陷入局部最优解的风险,同时算法本身易于实现并行化。 ! l$ E& Q2 [+ i f- K
% H6 x. E$ {% F- v(3)遗传算法基本上不用搜索空间的知识或其它辅助信息,而仅用适应度函数值来评估个体,在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。 ; f5 F/ n* o+ S+ h0 b1 o: M+ s3 Q' i. U0 @! L& M
(4)遗传算法不是采用确定性规则,而是采用概率的变迁规则来指导他的搜索方向。 # ~5 u& |) w$ I' ]: D4 D* z! Z5 g& c8 F) G
(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时,硬度大的个体具有较高的生存概率,并获得更适应环境的基因结构。 # L: v/ }+ v x8 R3 C! S ) H9 b! y+ Q, K- n( T0 K) H3.2 运用领域 - O# v! L, d! T% M2 i. _ # m8 b& o1 d0 P" Z 前面描述是简单的遗传算法模型,可以在这一基本型上加以改进,使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域: ① 优化:遗传算法可用于各种优化问题。既包括数量优化问题,也包括组合优化问题。 ② 程序设计:遗传算法可以用于某些特殊任务的计算机程序设计。 ③ 机器学习:遗传算法可用于许多机器学习的应用,包括分类问题和预测问题等。 ④ 经济学:应用遗传算法对;济创新的过程建立模型,可以研究投标的策略,还可以建立市场竞争的模型。 ⑤ 免疫系统:应用遗传算法可以对自然界中免疫系统的多个方面建立模型,研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。 ⑥ 进化现象和学习现象:遗传算法可以用来研究个体是如何学习生存技巧的,一个物种的进化对其他物种会产生何种影响等等。 ⑦ 社会经济问题:遗传算法可以用来研究社会系统中的各种演化现象,例如在一个多主体系统中,协作与交流是如何演化出来的。 2 u9 p9 c7 G! @- W! r) \. u$ g$ P
4 z5 v% R S5 u5 C9 i* _ o4 模拟退火算法 2 Q% T2 w6 u# e$ d* S3 {+ a b
. A5 S; G: a) _; N
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f ,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 * d) E0 @) z# {/ O+ Z. X) V0 m) E
$ h$ d% o0 h- s7 p I, e" n
5 群体(群集)智能(Swarm Intelligence) 6 e2 `4 [3 p4 _1 C5 Y9 I
0 ` v. ~+ v. G3 L, G% R
受社会性昆虫行为的启发,计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法,这些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体,这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中控制并且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了基础。 9 Y2 `+ P( P) ~' ?群集智能的特点和优点:群体中相互合作的个体是分布式的(Distributed),这样更能够适应当前网络环境下的工作状态; 没有中心的控制与数据,这样的系统更具有鲁棒性(Robust),不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间直接通信而是通过非直接通信(Stimergy)进行合作,这样的系统具有更好的可扩充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个个体的能力十分简单,这样每个个体的执行时间比较短,并且实现也比较简单,具有简单性(Simplicity)。因为具有这些优点,虽说群集智能的研究还处于[初级阶段,并且存在许多困难,但是可以预言群集智能的研究代表了以后计算机研究发展的一个重要方向。 - @3 a; l% D4 _( j5 T! D8 R' f
0 @7 S$ b" d8 L
在计算智能(Computational Intelligence)领域有两种基于群智能的算法,蚁群算法(Ant Colony Optimization)和粒子群算法(Particle Swarm Optimization),前者是对蚂蚁群落食物采集过程的模拟,已经成功运用在很多离散优化问题上。 # t0 y1 M T4 f r4 C e* U& g# s ]) _
5.1 蚁群优化算法 0 A/ K1 `: o& M- j; [( U+ p% T 6 c: Y' o4 r6 o" O 受蚂蚁觅食时的通信机制的启发,90年代Dorigo提出了蚁群优化算法(Ant Colony Optimization,ACO)来解决计算机算法学中经典的“货郎担问题”。如果有n个城市,需要对所有n个城市进行访问且只访问一次的最短距离。 6 A. [. @' o1 s
在解决货郎担问题时,蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路线,并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发,每只蚂蚁每次随机选择要走的路径,它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近"的原则,即可选择出最佳路线。由于这个算法利用了正反馈机制,使得较短的路径能够有较大的机会得到选择,并且由于采用了概率算法,所以它能够不局限于局部最优解。 , b$ C* { I2 Z/ I }7 G
蚁群优化算法对于解决货郎担问题并不是目前最好的方法,但首先,它提出了一种解决货郎担问题的新思路;其次由于这种算法特有的解决方法,它已经被成功用于解决其他组合优化问题,例如图的着色(Graph Coloring)以及最短超串(Shortest Common Supersequence)等问题。 2 l6 ]3 k( ]' i! |# R% D# G
: F; I! z- s/ |) _5.2 粒子群优化算法 % v J2 F( u( i" T, v. N0 B/ L0 E% X" i+ B; F
粒子群优化算法(PSO)是一种进化计算技术(Evolutionary Computation),有Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为研究。 : {$ a+ ^8 ?# i# {+ MPSO同遗传算法类似,是一种基于叠代的优化工具。系统初始化为一组随机解,通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。 # w% i* r5 D' O同遗传算法比较,PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化,神经网络训练,模糊系统控制以及其他遗传算法的应用领域。 . K/ K, }/ V8 w, z9 J粒子群优化算法(PSO) 也是起源对简单社会系统的模拟,最初设想是模拟鸟群觅食的过程,但后来发现PSO是一种很好的优化工具。 + S/ D. `, v9 `' p. P- c 7 N- l# E' M5 s" L" h) x5.2.1 算法介绍 + J: e' d y% K4 Q0 J3 e; `0 l