【讨论】遗传算法
遗传算法的起源和特点遗传算法是模拟达尔文的遗传选择和自然淘汰、适者
生存的生物进化过程的计算模型，是由美国Michigan
大学的J.Holland教授于1975年首先提出的，是搜索
最优解的一种随机化的方法。其主要特点是群体搜索
策略和群体中个体之间的信息交换，是近十多年来备
受关注的一种算法。
遗传算法与传统搜索方法的比较
单纯形法主要解决线性规划问题，而实际中遇到的大部分是非线性规划问题。
解决非线性规划问题常用的是以梯度为基础的优化算法，比如梯度法Hessian法等。遗传算法与它们相比，搜索不依赖于梯度信息，计算过程对函数性态的依赖性较小，甚至都不一定要显式地写出目标函数。
传统的搜索方法是单点搜索方法，初始点仅有一个，由决策者给出；遗传算法初始点多个，随机产生。
遗传算法的流程
遗传算法的描述
Step1给出一个有N个染色体的初始群体pop(1),t=1；
Step2若停止规则满足，则算法停止；否则，对群体pop(t)中每一个染色
体pop
i(t)计算其适应值；
Step3从群体pop(t)中随机选一些染色体构成一个种群
newpop(t+1)={popj(t)|j=1,2,…,N};
Step4通过交叉，交叉概率为Pc,得到有N个染色体的crosspop(t+1)
Step5对每个新个体依变异概率Pm进行变异，形成mutpop(t+1);t=t+1,
新的群体pop(t)=mutpop(t);返回Step2
遗传算法实现的技术问题
解的编码
初始群体的设定
适应值函数的设计
选择规则
编码的主要方法
常规码（二进制编码）
每个实数都可以用二进制数表示
例（连续变量的编码）：对于给定的区间,设采用二进制编码长为n,则任一变量 x=a+a1(b-a)/2+ a2(b-a)/22+…＋ an(b-a)/2n
对应二进制编码a1 a2 … an，二进制码与实际变量的最大误差为(b-a)/2n
有些问题的解可以用0，1变量来表示
例（0－1背包问题）：设有一个容积为b的背包，n个体积分别为ai（i=1,2,…,n）的价值分别为ci （i=1,2,…,n）的物品，如何以最大的价值装包？
编码的主要方法
浮点码：每一个染色体由一个向量表示，如用向量 x=(x1,x2,…,xn)表示最优化问题的解，相应的染色体也是V= (x1,x2,…,xn)
非常规码：非常规的编码与问题联系紧密
例（TSP旅行商问题）：一个商人欲到n个城市推销商品，每两个城市i和j
之间的距离为dij,如何选择一条道路使得商人每个城市走一遍后回到起
点且所走路径最短。
初始群体的设定
适应值函数的设计
适应值函数的设计
适应值函数的设计
排序适应函数（计算同一代群体中N个染色体的目标函数值）
选择规则（select）
交叉规则 (cross)
交叉规则 (cross)
非常规码的常规交叉法
随机选一个交叉位，两个后代交叉位之前的基因分别继承双亲的交叉位之前的基因，交叉位之后的基因分别按异方基因顺序选取不重基因。如
父A 1 2 3|4 5 6 78 910 子A1 2 3 | 47859610
父B 4 7 8|3 2 5 91 610 子B4 7 8 | 12356910
交叉规则 (cross)
变异规则 (cross)
变异规则 (cross)
约束条件的处理
为了保证染色体是可行的，必须对遗传操作过程中得到的 每一个染色体进行检查．对每个最优化问题，最好设计一个程序，其输出值1表示染色体是可行的，0表示不可行．
例如，对约束条件gj (x) ≤0,j=1,2,…,p，可以作如下的一个子函数：
从j＝1开始循环
若gj (x) >0 ，返回0
直到j＝p结束
返回 1．
结束准则
最简单的结束准则是给定一个最大的遗传代数MAXGEN,算法迭代代数达到MAXGEN时停止
给定问题一个下界LB，当进化中达到要求的偏差度ε时，算法终止，即当|V*(t)-LB|< ε时停止
( V*(t)为第t代所得的最优目标值，即 )
自适应规则。
用V*(t)进行监控，如果监控到算法已经K代没有进化到一个更好的解，则算法停止。
[ 本帖最后由 dushudushu 于 2006-7-25 19:46 编辑 ]
页:
[1]