遗传算法详解及Java实现

1、遗传算法详解及Java实现1 .遗传算法的起源20世纪60年代中期，美国密西根大学的John Holland提出了位串编码技术， 这种编码 既适合于变异又适合杂交操作， 并且他强调将杂交作为主要的遗传操作。 遗传算法的通用编 码技术及简单有效的遗传操作为其广泛的应用和成功奠定了基础。2 .遗传算法的目的解决经典数学方法无法有效地求出最优解的复杂的、大规模的难题。3 .遗传算法的思想遗传算法通常使用二进制编码来仿照基因编码，初代种群产生之后，按照适者生存和 优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解，在每一代，根据问题 域中个体的适应度(fitness)大小选择个体，

2、并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation ),产生出代表新的解集的种群。4 .遗传算法的步骤?(1)用固定长度的染色体表示问题变量域，选择染色体种群数量为 N,交叉概率为C,突变概率为M?(2)定义适应性函数来衡量问题域上单个染色体的性能或适应性。适应性函数是在繁殖过 程中选择配对染色体的基础。?(3)随机产生一个大小为 N的染色体的种群。?(4)计算每个染色体的适应性。?(5)在当前种群中选择一对染色体。双亲染色体被选择的概率和其适应性有关。适应性高的染色体被选中的概率高于适应性低的染色体。?(6)通过执行遗

3、传操作交叉和突变产生一对后代染色体。?(7)将后代染色体放入新种群中。?(8)重复步骤5,直到新染色体种群的大小等于初始种群的大小N为止。?(9)用新(后代)染色体种群取代初始(双亲)染色体种群。?(10)回到步骤4,重复这个过程直到满足终止条件为止。c开始)股机打始化左擀PIOUQO计?工网0)中斑寺个体的武而仇杂交_Q 结束W “ NP中每个州的地FT屏优牛.成需种杂(.”)tt+1输xmcitR晶石卜5.算法思路：?(i)变量作为实数，可以视为演化算法的表现型形式。从表现型到基因型的映射称为 编码。我们这里采用二进制编码，将某个变量值代表的个体表示为一个8,1二进制串。串长取决于求解的精

4、度。?(2)用遗传算法解决函数优化问题，先随机产生0和1填充10个46位基因数字串来创建染色体的初始种群，再通过自然选择，交叉，变异等步骤得出下一代种群。?(3)迭代，再次执行步骤 2直到满足需求或达到迭代次数。(1)问题描述其他函数优化问题min 3 - sin: ( Jx) - sin )其中其中X1K2 06,2对于此例,我们所知对于尸2,3 ,4和5分别有16, 36, 64和100个全局最优解白要求：求该函数的最小值，产2,精确到小数点后6位最小值;L000000(2)编码与解码确定求解精度到6位小数，由于区间长度为 6,必须将区间0, 6分为6X 10A6等 份。因为由2A226X

5、 10A62人23得，使用23位的二进制数来表示变量，故单个染色体需 46 位基因(以表示 x和y两个变量)示例：二进制串转化为十进制：10= x x 例如 s=v01000110000片。y=560a-0.453 与 v11111111111 表示区间的两，?1234Java实现代码:/*将染色体转换成x,y变量的值*/private double口 calculate巾tnessvalue(String str) 56/二进制数前23位为x的二进制字符串，后23位为y的二进制字符串7int a = Integer.parseInt(str.substring(0, 23), 2);8int

6、 b = Integer.parseInt(str.substring(23, 46), 2);910 double x =a * (6.0 - 0) / (Math.pow(2, 23) - 1);/x 的11 基因12 double y =b * (6.0 - 0) / (Math.pow(2, 23) - 1);/y 的13 基因1415 /需优化的函数16 double fitness = 3 - Math.sin(2 * x) * Math.sin(2 * x)17 - Math.sin(2 * y) * Math.sin(2 * y);1819 double口 returns =

7、x, y, fitness ;20 return returns;(3)轮盘选择基本思想：个体被选中的概率与其适应度值成正比，即按由个体适应度值所决定的某 个规则选择将进入下一代的个体。(详细解析)Java实现代码：21 *轮盘选择22 *计算群体上每个个体的适应度值;23 *按由个体适应度值所决定的某个规则选择将进入下一代的个体24 */25 private void select() 26 double evals口 = new doubleChrNum; /所有染色体适应值27 doublep =newdoubleChrNum;/各染色体选择概率28 doubleq口 =newdoubl

8、eChrNum;/累计概率29 doubleF = 0; / 累计适应值总和30 for (inti = 0;i ChrNum; i+) 31 evalsi = calculate巾tnessvalue(ipopi)2;32 if (evalsi bestfitness)/ 记录下种群中的最小值,33 即最优解34 bestfitness = evalsi;35 bestgenerations = generation;36 beststr = ipopi;37 192021222324252627282930313233343536373839404142F = F + evalsi; 所有

9、染色体适应值总和for (int i = 0; i ChrNum; i+) pi = evalsi / F;if (i = 0)qi = pi;else qi = qi - 1 + pi;for (int i = 0; i ChrNum; i+) double r = Math.random();if (r = q0) ipopi = ipop0; else for (int j = 1; j ChrNum; j+) if (r qj) ipopi = ipopj;(4)组合交叉(杂交)单点杂交：设定杂交概率与杂交个体，按照断裂点进行染色体杂交示例：杂交前：a=, b=杂交后：a=, b=Ja

10、va实现代码:123456/*交叉操作交叉率为60%平土匀为60%勺染色体进行交叉*/private void cross() String temp1, temp2;for (int i = 0; i ChrNum; i+) 7if (Math.random() 0.60) 8 int pos = (int)(Math.random()*GENE)+1;/pos 位/9 进制用交叉10 temp1 = ipopi.substring(0, pos) + ipop(i + 1) %11 ChrNum.substring(pos);12 temp2 = ipop(i + 1) % ChrNum.

11、substring(0, pos) +13 ipopi.substring(pos);14 ipopi = temp1;15 ipop(i + 1) / ChrNum = temp2; (5)变异基本思想：根据变异概率选择变异位点，将二进制位改变Java实现代码：?1 /*2 *基因突变操作1%基因变异3 */4 private void mutation() 5 for (int i = 0; i = ChrNum)14 chromosomeNum = 9;15 String temp;16 String a;/记录变异位点变异后的编码17 if (ipopchromosomeNum.cha

12、rAt(mutationNum - 1) = 0) /18 异位点为0时19 a = 1;20 else 21a = 0;2223/当变异位点在首、中段和尾时的突变情况24if (mutationNum = 1)25temp = a + ipopchromosomeNum.substring(mutationNum);26 else 27if (mutationNum != GENE) 28temp = ipopchromosomeNum.substring(0, mutationN29+ a30+31 ipopchromosomeNum.substring(mutationNum);32 e

13、lse 33temp = ipopchromosomeNum.substring(0, mutation341) + a;3536/记录下变异后的染色体ipopchromosomeNum = temp;(6)运行结果public static void main(String args口)234567891011121314151617181920GA Tryer = new GA();产生初始种群Tryer.ipop = Tryer.initPop(); / String str =;/迭代次数for (int i = 0; i 100000; i+) Tryer.select();Tryer.cross();Tryer.mutation();Tryer.generation = i;double口 x = Tryer.calculatefitnessvalue(Tryer.beststr);str = 最小值+ Tryer.bestfitness +