【讨论】遗传算法

遗传算法的起源和特点
遗传算法是模拟达尔文的遗传选择和自然淘汰、适者
生存的生物进化过程的计算模型，是由美国Michigan
大学的J.Holland教授于1975年首先提出的，是搜索
最优解的一种随机化的方法。其主要特点是群体搜索
策略和群体中个体之间的信息交换，是近十多年来备
受关注的一种算法。
遗传算法与传统搜索方法的比较
单纯形法主要解决线性规划问题，而实际中遇到的大部分是非线性规划问题。
解决非线性规划问题常用的是以梯度为基础的优化算法，比如梯度法Hessian法等。遗传算法与它们相比，搜索不依赖于梯度信息，计算过程对函数性态的依赖性较小，甚至都不一定要显式地写出目标函数。
传统的搜索方法是单点搜索方法，初始点仅有一个，由决策者给出；遗传算法初始点多个，随机产生。
遗传算法的流程
遗传算法的描述
Step1  给出一个有N个染色体的初始群体pop(1),t=1；
Step2  若停止规则满足，则算法停止；否则，对群体pop(t)中每一个染色
            体pop

1. 
   

复制代码

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
遗传算法实现的技术问题
解的编码
初始群体的设定
适应值函数的设计
选择规则

编码的主要方法
常规码（二进制编码）
每个实数都可以用二进制数表示
例（连续变量的编码）：对于给定的区间[a,b],设采用二进制编码长为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 7  8 9  10           子A  1 2 3 | 4  7  8  5  9  6  10
父B   4 7 8  |  3 2 5 9  1 6  10            子B  4 7 8 | 1  2  3  5  6  9  10
  

交叉规则 (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 编辑 ]