中科大瀚海星云BBS论坛
中国科大,中科大bbs,瀚海星云,瀚海星云bbs,中科大瀚海星云
[回到开始]
[上一篇][下一篇]
发信人: China_Heart (崛龙)，原信区: ustcbbs
标 题: 一种最优化算法．（三）
发信站: 中国科大BBS站 (Sat, 04 Jan 1997 16:33:38)，站内信件
三.三种模拟自然进化的最优化算法
由前文对达尔文进化论的讨论可知，自然进化可分为三个层次：
⑴基于基因重组的种系进化。
⑵基于群体交流的群体进化。
⑶基于神经和激素刺激的个体进化。
于是模拟自然进化算法也有相应的三种：
⑴基因算法（Genetic Algorithm）。
⑵进化策略（Evolution Strategies）。
⑶进化程序算法（Evolutionary Programming）。
§1.基因算法ＧＡ
Fraser,Bremermann,Reed,Holland等提出了模拟基因系统的相似算法。算法的过程如
下： ⑴确定衡量群体适应性的目标函数。
⑵在确定的空间中给出一群初始解。每一个实验解用一个向量X来表示，它和三条
染色体对应，元素是基因。
⑶对每一个基因Xi，i=1,...,p，给出其适应性度量u(Xi)。
⑷每个染色体被配以繁殖概率Pi，i=1,...,p，以使其被选中参与繁殖的可能性正
比于它的相对适应性。
⑸根据Pi，从p个Xi中选出双亲繁殖，获得新一代染色体组。有两种方式繁殖。一
种是两个染色体交换一部分；另一种是一个染色体自身基因换位。
⑹重复⑶⑷⑸直到找到满意解或计算时间到为止。
Holland提出并证明，任何一个问题，总可将每个染色体的元素表示成０或１。
基因算法是在寻找好积木，以便由之构成更大的积木，这是Holland等的积木假设。
基因算法容易发生预收敛，即获得最优前，群体中不再有变异。
§2.进化策略ＥＳ
另一种进化方法由Schwefel，Rechenberg and L.Fogel 等独立提出，即进化策略算
法。它强调父辈与儿女间的行为联系，很适合于实函数最优化。
进化策略的算法过程为：
⑴问题：找F(x):Rn->R的极值点，不失一般性，认为是最小化过程。
⑵随机给出一群相量Xi，i=1,...,p，其分布函数是正态的。
⑶在每一个母相量上加上一个平均值为0，预先给定标准差的高斯随机变量，得到子
向量XXi，i=1,...,p。
⑷比较每种“行为错误”即适应性F(Xi)和F(XXi)，i=1,...,p，选取错误最小的p个
“行为向量”组成下一代。
⑸重复执行，直到得到满意解“行为”或计算次数用尽。
这一例中每个向量Xi称为一个行为特性，它们(i=1,...,p)的决定基因是相同的。
为了使问题达到最小点附近很快收敛，变异随机变量的方差常随过程的进行而减小。
§3.进化程序算法ＥＰ
人们最先想到模拟进化方法是在解决人工智能问题时，这就是现在所说的“进化程序
算法”。Fogel提出智能行为应有能力预测环境的变化，并使自己有目的的作出响应以适
应未来的环境。为了通用，人们将环境用一串从一字母表中取出的符号来描述。于是，问
题就成了选择一种优良算法，使之作用于已有的“环境”符号上，并输出能适应环境的“
响应”。有限状态机（FSM'S）能很好的描述这一进化优化过程。
这种方法的“适应性”是时变的，对一系列静态进行最优法。最近，这种方法也被用
于连续实值函数的优化，其效果与进化策略法相似。
由此可知，以上三种方法的应用领域可以极广。除了传统的实值函数优化问题，对神
经网络的优化，模式识别优化以及并行算法的优化都有很好的效果。
不过，由于发展时间短，模拟进化法的理论基础还不够扎实，但由于其效率和高度的
实际收敛性，可以预见模拟进化算法必有美好的发展前景。
[参考文献]
1.《进化论教程》 李难 高等教育出版社
2.《并行图论算法》 唐策善 梁维发 中国科技大学出版社
3.《神经网络与神经计算机原理．应用》 范俊波 谭永东 西南交通大学出版社
4. D.B.Fogel:An Introduction to Simulated Evolutionary Optimization in
IEEE TRANSACTIONS ON NEURAL NETWORKS V.S NO.1 Jan 1994
5. Wirt Atmar:Notes on the Simulation of Evolution in IEEE TRANSACTIONS
ON NEURAL NETWORKS V.S NO.1 Jan 1994
§3.进化程序算法ＥＰ
人们最先想到模拟进化方法是在解决人工智能问题时，这就是现在所说的“进化程序
算法”。Fogel提出智能行为应有能力预测环境的变化，并使自己有目的的作出响应以适
应未来的环境。为了通用，人们将环境用一串从一字母表中取出的符号来描述。于是，问
题就成了选择一种优良算法，使之作用于已有的“环境”符号上，并输出能适应环境的“
响应”。有限状态机（FSM'S）能很好的描述这一进化优化过程。
这种方法的“适应性”是时变的，对一系列静态进行最优法。最近，这种方法也被用
于连续实值函数的优化，其效果与进化策略法相似。
由此可知，以上三种方法的应用领域可以极广。除了传统的实值函数优化问题，对神
经网络的优化，模式识别优化以及并行算法的优化都有很好的效果。
不过，由于发展时间短，模拟进化法的理论基础还不够扎实，但由于其效率和高度的
实际收敛性，可以预见模拟进化算法必有美好的发展前景。
[参考文献]
1.《进化论教程》 李难 高等教育出版社
2.《并行图论算法》 唐策善 梁维发 中国科技大学出版社
3.《神经网络与神经计算机原理．应用》 范俊波 谭永东 西南交通大学出版社
4. D.B.Fogel:An Introduction to Simulated Evolutionary Optimization in
IEEE TRANSACTIONS ON NEURAL NETWORKS V.S NO.1 Jan 1994
5. Wirt Atmar:Notes on the Simulation of Evolution in IEEE TRANSACTIONS
ON NEURAL NETWORKS V.S NO.1 Jan 1994
6.《遗传学词典》 科学出版社
在原文中，还有一例题。因为输入不变，所以略去了。愿与大家共同探讨。
--
. + * . . . . . +
☆ . * . * ☆ .
* . . 让真心的话,和开心的泪 + * . *
+ . * 在你我的心里流动! . ★ . +
★ + . . + * *
. . . . ☆ * . + . ☆ .
※ 来源: 中国科大BBS站 [bbs.ustc.edu.cn]
[回到开始]
[上一篇][下一篇]