遗传算法及其在函数优化问题中的应用.doc

课程：算法设计与分析题 目：遗传算法及其在函数优化问题中的应用姓 名： 陈珍姗学 院： 信息科学与技术学院 系： 自动化专 业： 控制工程 年级：2009级学 号： 23220091152865老 师：罗德林2010 年 1 月 4 日遗传算法及其在函数优化问题中的应用摘要 遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，主要应用在对没有做任何有关问题域假设的优化求解的算法设计中。本文主要通过介绍一个简单函数的优化问题中遗传算法的设计过程，体现遗传算法在优化性问题求解过程中的优越性，并最终实现对函数最大值的解的准确性、小数点精确度的设计要求。一、 遗传算法介绍1.1. 遗传算法思想遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。1.2. 遗传算法的主要特征遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：1. 首先组成一组候选解；2. 依据某些适应性条件测算这些候选解的适应度；3. 根据适应度保留某些候选解，放弃其他候选解；4. 对保留的候选解进行某些操作，生成新的候选解。1.3. 遗传算法的应用由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：1、 函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2、 组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。二、 遗传算法的设计思路2.1. 遗传算法的运行步骤本节讨论用遗传算法求解简单参数优化问题的一般思路。为了不失一般性，这里的问题都是求最大值问题。如果优化问题是求函数f的最小值，它等同于求函数g的最大，其中g=-f，即Minf(x)=max g(x)=max-f(x)假定目标函数f在其域内只取正值；若为负，可通过加入某个正常数C使之为正，即：Maxg(x)maxg(x)+C现在，假设欲求一个有k个变量的函数的的最大值。进一步假设每个变量为域内的一个值，且对所有，。假定以某个要求的精度优化函数：这里取自变量小数点后第6位。很明显，要达到这样的精度，每个域应该被分割成个等尺寸的区间。这里用表示使成立的最小整数。这样，对每个变量，由串长为的二进制编码表达显然能满足精度要求。下面的公式对应于每个串的自变量值：其中表示二进制的十进制值。现在，代表一个潜在解的染色体被长度为的二进制串表达：前位对应区间里的一个值，随后的位对应区间里的一个值，等等；最后的位对应区间里的一个值。为初始化一个群体，可以简单地以位的方式随机地设定pop_size个染色体。算法的其他部分是直接的：使用解码后自变量序列的函数值评价每代中的每个染色体，按照适应值的概率分布选择新群体，通过变异和杂交算子改变新群体中的染色体。经过若干代后，如果观察不到更进一步的改进，最好染色体就表示一个可能是全局的最优解。我们通常根据速度和资源判据在一固定数目的循环后停止算法。对基于适应值的概率分布选择新群体，通过变异和杂交算子改变新群体中的染色体。经过若干代后，如果观察不到更进一步的改进，最好染色体就表示一个可能是全局的最优解。我们通常根据速度和资源判据在一固定数目的循环后停止算法。 对基于适应值的概率分布选择新群体的选择过程，通常使用一个根据适应值调节刻度宽距的轮盘。并按照如下方法构造这样一个轮盘：1、 计算每个染色体的适应值；2、 计算群体的总适应值：；3、 计算每个染色体的选择概率：；4、 计算每个染色体的累积概率：； 对轮盘转动次；每次按照下面的方法为新群体选择一个单个的染色体：1、 产生一个在区间里的随机浮点数r；2、 如果，选择第一个染色体；否则选择使成立的第i个染色体。很明显，这样的染色体将被选择一次以上。这是符合模式定理的：最好染色体得到多个拷贝，中等染色体保持平稳，最差染色体死亡。 现在，我们准备在新群体中的个体应用重组算子杂交。如前所述，遗传系统的一个参数是杂交概率。此概率给出预计要进行杂交的染色体个数。我们进行下面的处理：对新群体中的每个染色体1、 产生一个在区间里的随机浮点数r；2、 如果，选择给定的染色体进行杂交。随机地对被选择染色体配对：对染色体对中的每一个，产生一个在区间（m为总长染色体的位数）里的随机整数pos。数pos表示杂交点的位置。两个染色体和被它们的子代：和所替换。下一个算子变异，是在一位一位（bit-by-bit）基础上执行的。另一个遗传系统参数，变异率，给出我们预计的变异位数。整个群体中所有染色体中的每一位都有均等的机会经历变异，即从0到1或者相反，所以进行如下的步骤。 对杂交后的当前群体中的每个染色体和染色体中的每个位：1、 产生在区间里的随机浮点数r；2、 如果变异此位。随着选择、杂交和变异的进行，新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽距的轮盘，演化的其余部分只是上述步骤的循环重复。2.2. 遗传算法设计的流程图搭建群体结构产生第一代群体，找出第一代最好个体，存入最末端寻找当前代的最好个体cur_best通过轮盘选择进化到下一代杂交变异比较cur_best和最末端最好个体的评价值将cur_best存入最末端输出最优值YN图2.1 遗传算法的流程图三、 遗传算法在简单函数优化问题中的应用3.1. 函数定义已知，其图如图3.1所示，找到区间内的x使函数值最大，即找出，使对所有。精度要求达到小数点后6位。图3.1 函数图3.2. 函数初步分析很容易进行函数的分析，可以确定该函数的一阶导数为零： ，该式等同于：，很明显，上述方程有无穷多解，其中i=1，2，.,其中i=-1，-2，.这里表示接近于零的实数递减序列（i=1，2，及i=-1，-2，）。注意对，如果i是一个奇数，函数达到其局部最大。如果i是一个偶数，则达到其最小，见图3.1。因为问题的定义域是，当时，函数达到其最大。此时比稍大。假定希望构造一个遗传算法来解决上述问题，即求函数的最大值。下面部分将依次介绍遗传算法各个组成部分的设计思路。3.3. 求解步骤3.3.1. 表达这里使用一个二进制向量作为一个染色体来表示变量x的真值。向量的长度依赖于要求的精度，本例为小数点后六位数。变量x的区间长度为3，精度要求意味着区间应该至少被划分成个等长区间。这就意味着二进制向量（染色体）要求有22位：在区间内，从二进制串到实数x之间的映射是直接的，在程序中我们主要通过两步完成：1、通过随机函数产生一个0到1之间的随机数r，便可在区间内找出相应的实数x：，其中-1.0是区间左边界，3是区间长度；2、通过r计算出相应22位二进制串的十进制形式：，再转换成二进制串形式存入数组，程序如下：int numeric = (Int32)(r * (Math.Pow(2, weishu) - 1); for (int i = weishu-1; i =0; i-) if (numeric != 0) bnumerici = numeric % 2; numeric = numeric / 2; 3.3.2. 初始群体初始化群体的过程主要就是产生一个染色体群体population，其中每个染色体都是22位的向量。每个染色体的所有22位都是随机初始化的。每个群体里的每个染色体都包含有如下信息：染色体值x（gene）、染色体二进制向量（bgene）、适应度（fitness）、适应度评价值（cfitness）和适应度评价累积值。后面三个值初始化为零，将在后面的步骤中进行计算。3.3.3. 评价函数对染色体的评价函数等同于函数：，这里染色体表示实数值。正如前面已经注意到，评价函数起着环境的作用，它们的适应值被用来评价潜在解。评价值越高的染色体越优。3.3.4. 寻找最好个体将群体中的染色体按照适应值的大小选出当前群体中的最优和最差个体，然后将最好个体存入群体中的最末，每当一代新群体产生，都与上一代群体得到的最好个体进行比较，找出更优个体。通过此法，算法将报告整个过程中的最好值，而不只是最终群体的最好值。3.3.5. 建立轮盘并转动产生新群体遗传算法的目的在于让好的“染色体”在繁衍下一代时占的优势多一些，差一些的“染色体”处于劣势。选择概率为此目的而设。现在，系统为选择过程建立一个轮盘。群体的总适应值为：，对每个染色体，选择概率为：，显然，。对每个染色体的累积概率为：。准备转动轮盘次；每次为新群体选择一单个的染色体。即产生个在0到1间的随机数，若大于小于，意味着染色体被选择。显然，（，）区间越长，被选上的机会越大。由此新一代群体中的较好个体必然比上一代群体中的要多。3.3.6. 遗传算子在遗传算法的变换阶段，我们将使用两个经典的遗传算子：变异和杂交。1、 杂交算子：确定一杂交的概率，程序中默认杂交概率，所以预计染色体中平均有25%将经历杂交。杂交按照下面的方法进行：对新群体中的每个染色体，产生一个0到1的随机数r，如果，则选择一给定的染色体进行杂交。由于杂交需满足具有偶数个个体，故本程序中进行累加判别，当满足偶数个染色体被选择时，进行杂交操作：随机产生一个0到1的数r， 即随机产生的杂交点，例如染色体和，杂交点为8，则：和产生的两个子代为：和2、 变异算子：变异是遗传算法模拟染色体的基因突变的一种操作，即以等于变异率的概率改变染色体上的一位或多位上的基因。程序中默认变异概率为，所以预计将有15%的染色体通过变异而改变。变异按照下面的方法进行：对杂交后的每个染色体，产生一个0到1的随机数r，如果，则选择一给定的染色体进行变异，即重新产生一个新的染色体3.4. 实算结果1、 程序界面如图3.2所示：图3.2 程序界面示意图2、 实算结果如图3.3所示：图3.3 实算结果四、 小结通过程序的实算结果可以看出，精确到小数点6位的函数最大值，此时。几次运算的结果基本都能满足程序设计的要求，但仍有个别次运算会出现较不理想的结果。主要原因在于系统随机数的产生无法预计所导致。欲解决此问题，可在程序运算过程中加入收敛性判别的步骤，在目标函数的精度要求下，如若前后两代的目标函数的平均值误差小于，便认为进化过程基本稳定，进化收敛，否则仍需继续群体的繁殖过程。本次算法设计是基于Visual Studio 2008的平台，运用C#语言进行程序的设计。在程序的设计和调试过程中学到了许多，如程序调试的方法、结构数组的建立方法等等。进一步增加了本人对程序编写的兴趣和探索热情。五、 参考文献1 卢开澄.计算机算法导引设计与分析.清华大学出版社 2006.2 Z.米凯利维茨美.演化程序遗传算法和数据编码的结合.科学出版社,2000.3 James Foxall美著，张秸 译.Visual C# 2008入门经典.人民邮电出版社,2009.4 王小平、曹立明著.遗传算法理论、应用与软件实现. 清华大学出版社 2006附录：遗传算法程序示例1. 主程序namespace GAnew public partial class Form1 : Form private int ub, lb, pop, maxg,generation; private double px, pm; ClassGenotype gene1 = new ClassGenotype(); public Form1() InitializeComponent(); private void Form1_Load(object sender, EventArgs e) void Initialize()/界面初始化 ub = int.Parse(UboundNum.Value.ToString(); lb = int.Parse(LboundNum.Value.ToString(); pop = int.Parse(PopsizeNum.Value.ToString(); maxg = int.Parse(MaxGensNum.Value.ToString(); px = double.Parse(PxoverNum.Value.ToString(); pm = double.Parse(PmutationNum.Value.ToString(); ialize(lb, ub, pop, maxg, px, pm); private void CountST_Click(object sender, EventArgs e) calculate1(); void calculate1()/计算过程 generation = 0; Initialize(); gene1.evaluate();/计算第一代的适应值 gene1.keep_the_best();/保存第一代最好个体 while (generation =0; i-)/将个体转换为二进制数组以便繁殖 if (numeric != 0) bnumerici = numeric % 2; numeric = numeric / 2; return val; /*评价函数f(x)=x*sin(10*pi*x)+2.0*/ public void evaluate() int mem; double x; for (mem = 0; mem pop; mem+) x = populationmem.gene; populationmem.fitness = x * Math.Sin(x * 10 * (Math.PI) + 2; /*存储最优个体函数*/ public void keep_the_best() int mem; for (mem = 0; mem population pop.fitness ) cur_best = mem; populationpop.fitness = populationmem.fitness; populationpop.gene = populationmem.gene; populationpop.bgene = populationmem.bgene; /*筛选函数：将前一代群体中的最优个体存入数组末端，如果此最优个体比当代群体的最优个体还差，则将后者取代前者*/ public void elitist() int i; double best, worst; int best_mem=0; int worst_mem = 0; best = population0.fitness; worst = population0.fitness; for (i = 0; i populationi + 1.fitness) if (populationi.fitness = best) best = populationi.fitness; best_mem = i; if (populationi + 1.fitness = worst) worst = populationi + 1.fitness; worst_mem = i + 1; else if (populationi.fitness = best) best = populationi + 1.fitness; best_mem = i + 1; if (best = populationpop.fitness) populationpop.gene = populationbest_mem.gene; populationpop.bgene = populationbest_mem.bgene; populationpop.fitness = populationbest_mem.fitness; else populationworst_mem.gene = populationpop.gene; populationworst_mem.bgene = populationpop.bgene; populationworst_mem.fitness = populationpop.fitness; /*新一代个体选择函数*/ public void select() int mem, i,j; double sum = 0; /double cavg = 0; double p; for (mem = 0; mem pop; mem+)/计算总适应值 sum += populationmem.fitness; /cavg = sum / pop; for (mem = 0; mem pop; mem+)/计算选择概率pi populationmem.rfitness = populationmem.fitness / sum; population0.cfitness = population0.rfitness; for (mem = 1; mem pop; mem+)/计算累积概率qi populationmem.cfitness = populationmem - 1.cfitness + populationmem.rfitness; for (i = 0; i pop; i+)/转动轮盘 p = r.NextDouble(); if (p population0.cfitness) newpopulationi = population0; else for (j = 0; j = populationj.cfitness & p populationj + 1.cfitness) newpopulationi = populationj + 1; for (i = 0; i pop; i+) populationi = newpopulationi;/新一代较优群体产生 void getnewgene(int one)/新个体的gene值计算函数 int i; double data = 0; for (i = 0; iweishu ; i+) if (populationone.bgenei != 0) data += Math.Pow(2, weishu-1 - i); populationone.gene = range * (data / (Math.Pow(2, weishu) - 1) + lowr; void Xover(int one, int two) int i; int point; point = (Int32)(r.NextDouble() * weishu); for (i = 0; i point; i+) swap(populationone.bgenei, populationtwo.bgenei); getnewgene(one); getnewgene(two); /*杂交函数*/ public void crossover() int mem, one=0; int first = 0; double x; for (mem = 0; mem pop; mem+) x = r.NextDouble(); if (x pxover) +first; if (first % 2 = 0) Xover(one, mem); else one = mem; void swap(int x, int y) int temp; temp = x; x = y; y = temp; /*变异函数*/ public void mutate() int i; double lbound, hbound; double