. q- v8 G y3 e* i+ v7 z: ~- k
/ u% ]% N g* L6 f4 e
遗传算法 % f4 P2 T* P# l- K9 J f遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想,它借用了仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。( D" ?$ N" v. |8 {
这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群染色体,也即是假设解。然后,把这些假设解置于问题的“环境”中,也即一个适应度函数中来评价。并按适者生存的原则,从中选择出较适应环境的染色体进行复制, 淘汰低适应度的个体,再通过交叉,变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化,至到最适合环境的值。 % i" D; I* f% C4 N7 c遗传算法已用于求解带有应用前景的一些问题,例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。 |, R3 K( J1 L9 `: I6 k术语说明. K: A* S8 s. D( C, _. E2 u+ J
由于遗传算法是由进化论和遗传学机理而产生的搜索算法,所以在这个算法中会用到很多生物遗传学知识,下面是我们将会用来的一些术语说明: - y' ?1 e' ]2 q5 q4 B5 Y; t一、染色体(Chronmosome) 2 o+ M k) p. X; l! k8 K染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。 ( E! K4 A. Q2 v9 N4 J! |/ `8 v. J二、基因(Gene) 0 j/ K( c* D8 D! w基因是串中的元素,基因用于表示个体的特征。例如有一个串S=1011,则其中的1,0,1,1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 : U" _4 A& e' z三、基因地点(Locus) ' m7 Q% w' T& Y3 X0 K基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position),有时也简称基因位。基因位置由串的左向右计算,例如在串 S=1101 中,0的基因位置是3。 : ?7 N6 |! a5 ^* m" ?, @& K2 q, {/ P四、基因特征值(Gene Feature)9 X0 Z, q( i1 ?% p
在用串表示整数时,基因的特征值与二进制数的权一致;例如在串 S=1011 中,基因位置3中的1,它的基因特征值为2;基因位置1中的1,它的基因特征值为8。1 }. k `9 V0 Q: t 五、适应度(Fitness)! \+ h8 k1 h6 G* L& D' ^: ]
各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力,引入了对问题中的每一个染色体都能进行度量的函数,叫适应度函数. 这个函数是计算个体在群体中被使用的概率。 Y& z) t4 u2 Z, P' V+ _& i4 ~$ r 操作算法 ) m+ j) \5 U. T1 ]霍兰德(Holland)教授最初提出的算法也叫简单遗传算法,简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)这也是遗传算法中最常用的三种算法: 9 C8 T7 K+ P) U8 \$ n1.选择(selection)+ `: v+ _2 I( ^7 [& C5 c5 t' p* G: N
选择操作也叫复制操作,从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说,选择将使适应度高的个体繁殖下一代的数目较多,而适应度较小的个体,繁殖下一代的数目较少,甚至被淘汰。最通常的实现方法是轮盘赌(roulette wheel)模型。令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它被选择的概率正好为其适应度值所占份额fi/Σfi。如下图表中的数据适应值总和Σfi=6650,适应度为2200变选择的可能为fi/Σfi=2200/6650=0.394. * N) i$ a2 V3 a9 y! z" T% z + Z+ j# @2 Q% C% d. h7 \6 `6 N9 a[url=]图1. 轮盘赌模型[/url] 0 ?( }+ ]" j" H" {; H% M) z+ Q+ u8 l* u
Fitness 值:
2200
1800
1200
950
400
100
选择概率:
3331
0.271
0.18
0.143
0.06
0.015
2.交叉(Crossover) 5 w' P' q! b2 W a交叉算子将被选中的两个个体的基因链按一定概率pc进行交叉,从而生成两个新的个体,交叉位置pc是随机的。其中Pc是一个系统参数。根据问题的不同,交叉又为了单点交叉算子(Single Point Crossover)、双点交叉算子(Two Point Crossover)、均匀交叉算子 (Uniform Crossover),在此我们只讨论单点交叉的情况。 6 g; Z5 I& x5 n5 m% O# h* ~单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体,将两者的部分基因码值进行交换。假设如下两个8位的个体: 8 \( H1 s: z: e1 a7 T# x, @
S1 1000 1111 S2 1110 1100
' V! { e4 U3 v. h( A0 g$ p产生一个在1到7之间的随机数c,假如现在产生的是2,将S1和S2的低二位交换:S1的高六位与S2的低六位组成数串10001100,这就是S1和S2 的一个后代P1个体;S2的高六位与S1的低二位组成数串11101111,这就是S1和S2的一个后代P2个体。其交换过程如下图所示:8 E ]* h% r/ M. E; K
Crossover
11110000
Crossover
11110000
S1
1000 1111
S2
1110 1100
P1
1000 1100
P2
1110 1111
3.变异(Mutation)* ?& a6 f6 ~6 c/ N
这是在选中的个体中,将新个体的基因链的各位按概率pm进行异向转化,最简单方式是改变串上某个位置数值。对二进制编码来说将0与1互换:0变异为1,1变异为0。' I5 D- F: ^$ O9 L3 L
如下8位二进制编码: 5 f& n f0 S7 X) H! H2 Z' I3 F1 }
1 1 1 0 1 1 0 0
7 t+ f8 l' i3 @7 Q. f6 A随机产生一个1至8之间的数i,假如现在k=6,对从右往左的第6位进行变异操作,将原来的1变为0,得到如下串: 8 i0 |6 h- y8 O/ c
choose an intial population2 s! p0 Z3 C9 W% |: W
For each h in population,compute Fitness(h). e2 y7 A L0 R M1 y
While(max Fitness(h) < Fitnessthreshold)3 L o0 ^- c. c( }" h
do selection y& _1 O J% M% Q do crossover 7 J$ O( y1 E; n+ ]3 odo mutation ( L* C6 P9 {4 c a5 Y update population0 V9 h6 k2 i; p' c' y
For each h in population,compute Fitness(h)& P5 ~5 z! F3 Q
Return best Fitness ! V6 u* w2 s& I* L
, O! u7 o* ?% U. y0 ]' |Robocode 说明2 j, G. g; V, V o
能有效实现遗传算法的应用例子有很多,像西洋双陆棋、国际名模等等都是遗传程序设计学习的工具,但是 Robocode 有着其他几个无可比拟的优势: $ @; t+ ` v# t4 k
ahead(200);4 {- o6 b" o0 a
setBack(200);! x4 A4 v9 J" a$ s- O
2 ^6 p3 e" J2 f
Circular:/ |# I: J' p6 O ] ^$ D/ |! j1 J0 B
setTurnRight(1000);$ x8 t6 p% G7 C. T1 e; X
setMaxVelocity(4); 7 v5 J0 e, {) ]2 {' E+ O Hahead(1000);0 H. K& B6 M1 Q8 x+ x
3 L8 D! `+ O& ?2 Banti gravity:- x6 M; `/ i1 Y [
double forceX = 0; ' v& R5 ^* t9 y4 Y/ ~8 n% H2 q" z double forceY = 0;* b! J: Q' P& X
for (int i=0; i
8 j r' j% _6 I+ e这里我们用遗传算法来控制机器人移动位置。这些策略是基于下面几点:机器人人自己的位置、速度和方位;对手的位置(x,y坐标)、速度、方位以及相对角;所有机器人和子弹位置,方位及速度;场地大小等参数。 3 u; k. Q' q2 ]: [$ d7 m当上面的信息在下一回移动中使用时,出输出一对坐标值,根据这对坐标在Robocode就能得到距离和角度。要想让移动实现遗传必须要让它实现在线学习:所以我们的代码必须做下面几件事:要有一个函数收集适应度值,在Robocode运行过程中要运用到遗传操作,遗传后代要在Robocode运行中产生,而不是事后由手写入代码。0 }% n3 O' A- Q5 {6 C5 K- ?& I& m 遗传操作* ~" E. J6 w6 x1 Q6 B: t8 o( f! A
本例中遗传算法为实现移动用到两个类GA和MovePattern。此处的GA比较简单主要完成数据和群体的定义,以及这些定义的读写文件操作。基中包括如下参数:群体大小、交叉概率、变异概率、精英概率(既告诉从当前群体到下一代中有多少移动不需要改变)、方程式中使用的加权系数大小,它通过一个主循环完成MovePattern的封装。MovePattern类中实现交叉、变异方法等方法,完成移动模式操作。而所有的输出保存在一个vector函数当中。Vector函数拥有一对实数数组,一个用于计算x坐标,另一个用于计算y坐标。通过对x,y坐标的计算,从而得到距离、角度等值,并产生相就在移动策略。如下,MovePattern包含三个参数,grad表示vector函数排列顺序,input即表示算法给出的输入编号,rang是加权的范围。# E, w$ i3 B. ~! b+ D0 m8 r' P
public class MovePatteren implements Comparable {; L. S( L, a5 i; E
private int grad, input; 0 T6 W2 j0 |' |7 G5 ^/ @0 G$ T$ F private double range; 4 d! Z. \# t1 {! S0 D6 p protected double fitness=0;& N0 k( c4 j; f' _9 r
protected double[] weightsX, weightsY; 1 M! f; S# J1 ]& f… }5 G) s i8 K4 m1 O, \2 }7 A- N' k
+ E- ^) J# F# t8 { h1 B4 J交叉操作:每一个交叉操作执行如下步骤,先在交叉操作中产生一个特征码。这个特征码是个0到1之间的变量数组。有关交叉的基本原理可参考上面部分。最后通过遍历vector函数,把相应的加权值进行交叉操作。1 k4 T2 U3 k' E9 A/ ?5 v) R
protected MovePatteren crossOver(MovePatteren mate, boolean[] maskx, boolean[] masky) { $ E% H$ y- z" f6 c& X double[] wx= new double[weightsX.length]; * r9 r. [6 h1 W( c double[] wy= new double[weightsX.length];5 _4 s+ O) ~% |
for(int mask=0; mask <="" pre="" mask++)="" for(int="" g="0;" g
protected void mutate() {3 G2 o* D: S( ?" ?! K2 R
weightsX[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;; ~; M& A, R& ^+ ]( H6 z& t* H
weightsY[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;0 J; q5 a" \+ H! |
} % n2 v v, z4 D' m: b! j
& j+ J, ]6 }' b" z ^6 G
从上面的例子我们知道了遗传算法的大概实现,但并没有告诉我们这些组件是如何一起工作的。当Robocode开始时,如果文件中没有数据,所以系统会依照输入的策略随机生成一个移动模式,如果文件中有数据,则加载这些数据。每一个移动模式在开始都会给出了一个适应度值。当所有的移动模式都接收到适应度值,并完成各自的编号后,下面的操作将开始执行:2 g7 P* n( F1 w$ K. q& {