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