基本遗传算法及其在函数优化中的应用-021050谭同学

1、基本遗传算法及其在函数优化中的应用摘要遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。遗传算法是一种是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，不需要有先验条件。其搜索过程是从问题解的一个随机产生的集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，也就大大减少可陷入局部极小值的可能。因而，遗传算法在求解函数优化问题中有着良好的应用，同时，遗传算法在解决可能在求解过程中产生组合爆炸的问题时会产生很好的效果。 关键字：遗传算法 函数优

2、化 人工智能前言这是一个关于遗传算法的问题，而本文的主要目的就是利用C语言编写程序实现利用遗传算法中的编码，变异，交叉，复制来求解函数最大值的问题。一、 遗传算法概述遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取

3、和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术二、 遗传算法基本机理遗传算法是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种重要形式。遗传算法与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。同时，遗传算法借鉴了生物科学中的某些知识，从而体现了人工智能的这一交叉学科的特点。遗传算法基本机理主要分为以下三方面：1、 编码与解码将问题结构变换为位串形式编码

4、表示的过程叫做编码；相反的，将位串形式编码表示变换为原问题结构的过程叫做解码或者译码。把位串形式编码表示叫做染色体，有时也叫做个体。2、 适应度函数为了体现染色体的适应能力，引入了对问题中的每一个染色体都进行度量的函数，叫做适应度函数（fitness function）。通过适应度函数来决定染色体的优劣程度，它体现了自然界进化中的优胜劣汰原则。对于优化问题，适应度函数就是目标函数。3、 遗传操作简单的遗传算法操作主要有三种：选择（selection）、交叉（crossover）、变异（mutation）。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫做复制操作（reprodu

5、ction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。变异操作的简单方式是改变数码串的某个位置上的数码。4、 遗传算法基本步骤1、初始化种群；2、计算种群上每个个体的适应度值；3、按由个体适应度值所决定的某个规则选择将进入下一代的个体4、按概率PC进行交叉操作5、按概率PC进行变异操作6、若没有满足某种停止条件，则转步骤2），否则进入下一步；7、输入种群中适应度值最优的染色体作为问题的满足解或最优解5、 基本遗传算法框图基本遗传算法框图开始GEN：=0产生初始种群计算每

6、个个体的适应值i:=0依概率选择遗传操作选择两个个体i:=i+1执行杂交将两个后代插入新种群是否满足停止准则i:=M?选择一个个体执行复制复制到新种群选择一个个体tiytiyu 体执行变异插入到新种群GEN:=GEN+1执行结果结束I=i+1复制交叉变异是是否I=i+1是否是 否复制变异 交叉6、 遗传算法求解举例利用遗传算法求解函数：f(x)=x*sin(10*x)+1.0的最大值，其中，x-1,2|。7、 编程实现const int MAX = ;const int MIN = 0;#include #include /产生随机数要用到time(int)，以使每次产生的数不同。#inclu

7、de /sin(float)在这儿。using namespace std; const double pi = 3.; class Individuality private: int chromosome; /染色体public: void set(int chromosome) this-chromosome = chromosome; Individuality operator =(Individuality c) this-chromosome = c.chromosome; return *this; bool operator =(Individuality c) return

8、 this-chromosome = c.chromosome; float resolve() /通过染色体取得x的值. return -1.0 + (float)chromosome * 3.0 / (MAX - 1); float evaluate() /求f() return resolve() * (float)sin(10*pi*resolve() + 1.0; void print() cout = 0; j-) /以下循环是在以二进制串的形式打印染色体 if(1j) & chromosome) cout 1; else cout 0; cout ttx = resolve()

9、tf(x) = evaluate() chromosome = 1i; return *this; /以下是两个个体进行交叉，并且返回两个新个体的操作 void crisscross(Individuality prnt1, Individuality prnt2, Individuality &child1, Individuality &child2) int i = rand() % 21 + 1; int temp1 = prnt1.chromosome; int temp2 = prnt2.chromosome; int temp = 0; for(; i 22; i+) temp

10、+= 1i; temp1 &= temp; temp2 &= temp; prnt1.chromosome &= temp; prnt2.chromosome &= temp; prnt1.chromosome |= temp2; prnt2.chromosome |= temp1; child1 = prnt1; child2 = prnt2; ;const int POP_SIZE = 200; /建立一个种群的类，并且有固定的大小/每次遗传，选出f(x)的排名在前50%的个体进行遗传（排名通过希尔排序实现），都会有约1%的个体变异，10%的个体发生交叉遗传，其余的直接遗传。每次遗传都记录

11、下本次f(x)为最大的个体Max。遗传150次，如果过程中发现已有30代的Max一直不变了，说明已达到最优，基本不需要再遗传了，所以提前跳出循环。class Population private: Individuality indPOP_SIZE;public: Population() for(int i = 0; i 0; gap /= 2) for(i = gap; i =0 & indj.evaluate() indj+gap.evaluate(); j -= gap) temp = indj; indj = indj+gap; indj+gap = temp; void inher

12、it() Population:shellSort(); const int NT = POP_SIZE / 2; int nc = (rand() % (POP_SIZE/10) + (POP_SIZE/4) / 2; int nv = rand() % (POP_SIZE/100+1) + (POP_SIZE/100); int i, n1, n2; Individuality tempNT; for( i=0; i NT; i+) tempi = indi; for(i = 0; i nv; i+) n1 = rand() % NT; indi = tempn1.variate(); f

13、or(i = nv; i crisscross(tempn1, tempn2, temp1, temp2); indi = temp1; indi+1 = temp2; for(i = nv+nc*2; i POP_SIZE; i+) n1 = rand() % NT; indi = tempn1; Individuality getMax() Individuality max = ind0; for(int i = 0; i indi.evaluate() ) max = indi+1; return max; void traverse( ) for(int i = 0; i POP_S

14、IZE; i+) indi.print(); cout endl; ; int main() srand( (unsigned)time( NULL ) ); Population a; a.traverse(); int count = 0; int gen = 0; for(int i = 0; i 30) break; a.traverse(); gen+; cout The max is:n; a.getMax().print(); cout After gen generations.n; return 0;三、 实验结果结论这是迭代60次之后的结果，求得的最大值是2.85027，此时的x为1.85054这是迭代54次之后的结果，求得的最大值是2.85027，此时的x为1.85059结论：传统的搜索方法由于其应用的局限性,在某些情况下可能搜索到局部最优点，而不能达到全局最优点。利用遗传算法搜索函数最优点的方法极大地提高了搜索全局最优点的准确性，有效地避免了组合爆炸地产生。因此，遗传算法在求解复杂的优化问题中具有广泛的应用前景。四、 参考文献主要参考文献：1蔡自兴 徐光祐.人工智能及其应用.北京：清华大学出版社, 2009。2王小平，曹立明.遗传算法-理论、应用与软件实现.西安：西安交通大学出版社,2002。3Schmitt, Lothar