中科大瀚海星云BBS论坛
中国科大,中科大bbs,瀚海星云,瀚海星云bbs,中科大瀚海星云
[回到开始]
[上一篇][下一篇]
发信人: China_Heart (崛龙祝你新年好)，原信区: ustcbbs
标 题: 一种最优化算法．（二）
发信站: 中国科大BBS站 (Mon, 30 Dec 1996 14:56:08)，站内信件
二.模拟进化的最优化算法
§1.模拟进化算法概述
虽然决定进化过程的信息物理过程很明晰，而由实验－出错得到的系统结构异常复杂。
于是在模拟进化方法发展历史中，为解决复杂性有两类作法：
⑴从整体中分出各成分，然后分别优化。
⑵从进化结构的整体进行优化，评价。
而工程学上看，只要能从繁殖后代中作出明确的选择，又有较高效率，就可以认为是好算
法。
达尔文进化是一个严格的物理过程，其特例之一就是精确的Boltzman热动力学。于是
进化最优化表面上是一个很简单的热动力学过程，通过选择将各实验变异的行为不合适度
最小化。
这种本质的简单使得可以为工程目的设计一种模拟进化最优化算法(Simulated
evolutionary optimization alogrithm)。其表述如下：
Step1:选取初始实验群体，其个体数Ｎ常远远大于１。
Step2:群体进行有错的自繁殖，每对双亲常可产生Ｃ个(C在1-1000之间)后代。
Step3:对繁殖后群体的每个个体(包括父辈和子女)的行为错误进行选择。选择的方式
通常有：①选最好的Ｎ个留下来繁衍下一代。
②或Ｎ个最好的最有可能留下来繁殖。
Step4:重复执行Step2和Step3，直到达到预期效果或计算时间已到为止。
虽然具体问题将有具体的技巧，但都是以此为各模拟自然进化算法的基础。
§2.模拟进化最优化方法的特点－隧道效应
一个繁殖后群体的整体适应性常用其全部“特性”的行为错误之和表示，称为群体的
适应性。任何一个进化过程的目的都是使之最小化，然而和普遍的数值函数一样，也常有
局部极小值问题。
几乎所有的基于梯度的常规最优化算法都处理不好局部极值问题，而这在模拟自然进
化方法中却得到了较好的解决。
我们知道，进化是由基因的变化造成的，然后表现在“表型”的变化之上。选择是通
过对“表型”进行评价而进行的，这就使得表型的出现不受群体适应性的约束，也就是说
基因改变可能造成任何程度的变异，虽然其概率是受适应性影响的。
（图略）
如上图，若群体进化到Ｖeocal这一变异体阶段，是否意味着进化会停止呢？不会，
虽然其下一代中大部分具有同样变异体，但还是可能出现虚线以右部分的变异。一旦出现
这些适应性更好的变异体，这个群体的分布格局将立即被打破，从而转到更优的区域。也
就是说，群体通过变异具有了一种无形的通过壁垒的能力，这与量子力学中的隧道效应也
具有类似之处，故称为隧道效应。
由以上发析可知，影响进化的关键不是壁垒的高度而是它的宽度，同时群体变异的步
长也极为重要。
--
┏━━━━━━━━━━━━━━━┓
┃ 长城永不倒,我辈当自强! ┃
┗━━━━━━━━━━━━━━━┛
※ 来源: 中国科大BBS站 [bbs.ustc.edu.cn]
[回到开始]
[上一篇][下一篇]