下载文档原格式
使用遗传算法进行优化问题求解遗传算法（Genetic Algorithm, GA）是一种基于自然界生物进化思想的优化算法，广泛应用于求解复杂的优化问题。
本文将介绍遗传算法的基本原理、流程以及在实际问题中的应用，并深入探讨其优势和局限性。
一、遗传算法基本原理遗传算法模拟了生物演化的过程，核心思想是通过模拟生物的遗传、变异和选择过程来搜索问题的最优解。
遗传算法的基本原理如下：1.个体编码：将问题的解表示为某种形式的编码，常用的编码方式包括二进制编码、实数编码和排列编码等。
2.初始种群的生成：随机生成一组个体作为初始种群。
3.适应度评估：根据问题的要求，设计适应度函数来评估每个个体的优劣。
4.选择操作：根据适应度函数的结果，选择适应度较高的个体作为下一代的父代。
5.交叉操作：通过交叉操作产生新个体，实现信息的交流和融合。
6.变异操作：对新个体进行随机的变异操作，增加搜索空间的多样性。
7.新种群的生成：依据选择、交叉和变异操作，生成新的种群作为下一代。
8.终止条件的判断：判断是否满足终止条件，如果满足则算法终止，否则返回第4步。
二、遗传算法的流程遗传算法的流程如下：1.初始化：确定种群大小、编码方式、变异概率、交叉概率等参数。
2.生成初始种群：随机生成一组个体作为初始种群。
3.适应度评估：计算每个个体的适应度。
4.选择操作：根据适应度函数的结果，选择适应度较高的个体作为下一代的父代。
5.交叉操作：从父代中选择两个个体进行交叉以产生新个体。
6.变异操作：对新个体进行变异操作，增加种群中的多样性。
7.生成新种群：依据选择、交叉和变异操作，生成新的种群作为下一代。
8.终止条件的判断：判断是否满足终止条件，如果满足则算法终止，否则返回第4步。
三、遗传算法的应用遗传算法在许多领域中得到了广泛的应用，包括组合优化问题、机器学习、数据挖掘、图像处理等。
以下是几个具体的应用案例：1.旅行商问题（Traveling Salesman Problem, TSP）：TSP是一个经典的组合优化问题，在遗传算法中，可以将城市序列作为个体的编码，通过交叉和变异操作不断优化路径，求解最短路径问题。
智能优化算法 python 解方程智能优化算法在解方程方面的应用是一项非常有意义的研究领域。
通过利用智能算法，我们可以自动地找到方程的解，大大提高了解方程的效率和准确性。
本文将介绍一些常见的智能优化算法在解方程问题中的应用，并通过Python代码示例来说明其实现方法。
我们来介绍一种常用的智能优化算法——遗传算法。
遗传算法是模拟生物进化过程的一种优化算法。
其基本思想是通过模拟生物的遗传、变异和选择等过程，逐步演化出最优解。
在解方程问题中，遗传算法可以用来寻找方程的根。
下面我们以一个简单的一元二次方程为例，来说明遗传算法在解方程中的应用。
假设我们要解方程：x^2 - 3x + 2 = 0。
首先，我们需要定义一个适应度函数，用来评估每个个体的适应度。
在这个例子中，我们可以使用方程的根与0的距离作为适应度函数的值。
接下来，我们需要定义遗传算法的参数，如种群大小、交叉概率、变异概率等。
然后，我们随机生成初始种群，并通过遗传算法的操作（选择、交叉和变异）对种群进行迭代优化，直到找到满足适应度函数要求的最优解。
下面是使用Python实现遗传算法解方程的示例代码：```pythonimport random# 定义适应度函数def fitness_function(x):return abs(x**2 - 3*x + 2)# 定义遗传算法参数population_size = 100crossover_rate = 0.8mutation_rate = 0.01max_generations = 100# 随机生成初始种群population = [random.uniform(-10, 10) for _ in range(population_size)]# 迭代优化for generation in range(max_generations):# 计算适应度值fitness_values = [fitness_function(x) for x in population]# 选择操作selected_population = random.choices(population, weights=[1/fitness for fitness in fitness_values], k=population_size)# 交叉操作offspring_population = []for i in range(0, population_size, 2):parent1 = selected_population[i]parent2 = selected_population[i+1]if random.random() < crossover_rate:offspring1 = (parent1 + parent2) / 2offspring2 = (parent1 - parent2) / 2else:offspring1 = parent1offspring2 = parent2offspring_population.extend([offspring1,offspring2])# 变异操作for i in range(population_size):if random.random() < mutation_rate:offspring_population[i] += random.uniform(-0.1, 0.1)# 更新种群population = offspring_population# 输出最优解best_solution = min(population, key=fitness_function)print("最优解为：", best_solution)```上述代码通过遗传算法迭代优化的方法，最终得到了方程的最优解。
使用Matlab进行遗传算法优化问题求解的方法引言在现代科技发展的背景下，优化算法成为解决各种问题的重要工具之一。
遗传算法作为一种生物启发式算法，具有全局寻优能力和适应性强的特点，在许多领域中被广泛应用。
本文将介绍如何使用Matlab进行遗传算法优化问题求解，包括问题建模、遗传算子设计、遗传算法编码、适应度评价和求解过程控制等方面。
一、问题建模在使用遗传算法求解优化问题之前，我们首先需要将问题定义为数学模型。
这包括确定问题的目标函数和约束条件。
例如，假设我们要最小化一个多变量函数f(x)，其中x=(x1,x2,...,xn)，同时还有一些约束条件g(x)<=0和h(x)=0。
在Matlab中，我们可通过定义一个函数来表示目标函数和约束条件。
具体实现时，我们需要在目标函数和约束函数中设置输入参数，通过调整这些参数进行优化。
二、遗传算子设计遗传算法的核心是遗传算子的设计，包括选择（Selection）、交叉（Crossover）、变异（Mutation）和替代（Replacement）等。
选择操作通过一定的策略从种群中选择出适应度较高的个体，作为进行交叉和变异的父代个体。
交叉操作通过将两个父代个体的基因片段进行交换，产生新的子代个体。
变异操作通过改变个体某些基因的值，引入新的基因信息。
替代操作通过选择适应度较低的个体将其替换为新产生的子代个体。
三、遗传算法编码在遗传算法中，个体的编码方式决定了问题的解空间。
常见的编码方式有二进制编码和实数编码等。
当问题的变量是二进制形式时，采用二进制编码。
当问题的变量是实数形式时，采用实数编码。
在Matlab中，我们可以使用矩阵或向量来表示个体的基因型，通过制定编码方式来实现遗传算法的编码过程。
四、适应度评价适应度评价是遗传算法中判断个体优劣的指标。
在适应度评价过程中，我们将问题的目标函数和约束条件应用于个体的解，计算得到一个适应度值。
适应度值越大表示个体越优。
MATLAB实验遗传算法与优化设计遗传算法与优化设计一实验目的1 了解遗传算法的基本原理和基本操作选择交叉变异2 学习使用Matlab中的遗传算法工具箱 gatool 来解决优化设计问题二实验原理及遗传算法工具箱介绍1 一个优化设计例子图1所示是用于传输微波信号的微带线电极的横截面结构示意图上下两根黑条分别代表上电极和下电极一般下电极接地上电极接输入信号电极之间是介质如空气陶瓷等微带电极的结构参数如图所示Wt分别是上电极的宽度和厚度D是上下电极间距当微波信号在微带线中传输时由于趋肤效应微带线中的电流集中在电极的表面会产生较大的欧姆损耗根据微带传输线理论高频工作状态下假定信号频率1GHz电极的欧姆损耗可以写成简单起见不考虑电极厚度造成电极宽度的增加图1 微带线横截面结构以及场分布示意图1其中为金属的表面电阻率为电阻率可见电极的结构参数影响着电极损耗通过合理设计这些参数可以使电极的欧姆损耗做到最小这就是所谓的最优化问题或者称为规划设计问题此处设计变量有3个WDt它们组成决策向量[W D t] T待优化函数称为目标函数上述优化设计问题可以抽象为数学描述2其中是决策向量x1xn为n个设计变量这是一个单目标的数学规划问题在一组针对决策变量的约束条件下使目标函数最小化有时也可能是最大化此时在目标函数前添个负号即可满足约束条件的解X 称为可行解所有满足条件的X组成问题的可行解空间2 遗传算法基本原理和基本操作遗传算法 Genetic Algorithm GA 是一种非常实用高效鲁棒性强的优化技术广泛应用于工程技术的各个领域如函数优化机器学习图像处理生产调度等遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法按照达尔文的进化论生物在进化过程中物竞天择对自然环境适应度高的物种被保留下来适应度差的物种而被淘汰物种通过遗传将这些好的性状复制给下一代同时也通过种间的交配交叉和变异不断产生新的物种以适应环境的变化从总体水平上看生物在进化过程中子代总要比其父代优良因此生物的进化过程其实就是一个不断产生优良物种的过程这和优化设计问题具有惊人的相似性从而使得生物的遗传和进化能够被用于实际的优化设计问题按照生物学知识遗传信息基因Gene 的载体是染色体Chromosome 染色体中一定数量的基因按照一定的规律排列即编码遗传基因在染色体中的排列位置称为基因座Locus在同一个基因座上所有可能的基因就称为等位基因Allele生物所持有的基因以及基因的构成形式称为生物的基因型Genotype而该生物在环境中所呈现的相应性状称为该生物的表现型Phenotype在遗传过程中染色体上的基因能够直接复制给子代从而使得子代具有亲代的特征此外两条染色体之间也通过交叉 Crossover 而重组即两个染色体在某个相同的位置处被截断其前后两串基因交叉组合而形成两个新的染色体在基因复制时也会产生微小的变异Mutation从而也产生了新的染色体因此交叉和变异是产生新物种的主要途径由于自然选择在子代群体新产生的物种或染色体当中只有那些对环境适应度高的才能生存下来即适应度越高的被选择的概率也越大然后又是通过遗传和变异再自然选择一代一代不断进化因此生物遗传和进化的基本过程就是选择即复制交叉和变异遗传算法就是通过模拟生物进化的这几个基本过程而实现的①编码编码是设计遗传算法首要解决的问题在生物进化中选择交叉变异这些基本过程都是基于遗传信息的编码方式进行的即基于染色体的基因型而非表现型因此要模拟生物进化过程遗传算法必须首先对问题的可行解X决策向量进行某种编码以便借鉴生物学中染色体和基因等概念在遗传算法中将每一个决策向量X用一个染色体V来表示3其中每一个vi代表一个基因染色体的长度m不一定等于设计变量的数目n取决于染色体上基因的编码方式一般有两种编码方式二进制编码和浮点数编码如果是二进制编码每一个设计变量xi的真实值用一串二进制符号0和1按照一定的编码规则来表示每个二进制符号就代表一个基因因此染色体长度要远大于设计变量的数目这种由二进制编码构成的排列形式V就是染色体也称个体的基因型而基因型经过解码后所对应的决策向量X即可行解就是个体的表现型如果是浮点数编码每个设计变量用其取值范围内的一个浮点数表示构成染色体的一个基因vi因此个体的编码长度m也就等于决策变量的个数n由于这种编码方式使用的是决策变量的真实值所以也称真值编码方法无论哪种编码方式所有可能的染色体个体V构成问题的搜索空间种群遗传算法对最优解的搜索就是在搜索空间中搜索适应度最高的染色体后面叙述适应度的计算因此通过编码将一个问题的可行解从其解空间转换到了遗传算法能够处理的搜索空间经过个体的编码后就可以进行遗传算法的基本操作选择交叉和变异②选择复制操作选择也就是复制是在群体中选择适应度高的个体产生新群体的过程生物的进化是以集团为主体的与此相应遗传算法的运算对象是有M个个体或染色体组成的集合称为种群M也称为种群规模遗传算法在模拟自然选择时以个体的适应度Fitness高低为选择依据即适应度高的个体被遗传到下一代种群的概率较高而适应度低的个体遗传到下一代的概率则相对较低个体适应度由适应度函数计算适应度函数总是和个体表现型 ie X 的目标函数值f X 关联一般是由目标函数经过一定的变换得到一种最简单的方法就是直接使用目标函数f X 作为适应度函数4选定了适应度函数之后个体适应度也随之确定则在选择操作时个体被选中的概率5其中Fi为个体的适应度这种选择方式称为比例选择也称轮盘赌选择除此之外还有多种选择方法如随机竞争选择均匀选择无回放随机选择等不一一介绍③交叉操作所谓交叉就是以一定的概率交叉概率从群体中选择两个个体染色体按照某种方式交换其部分基因从而形成两个新的个体在遗传算法中它是产生新个体同时也是获得新的优良个体的主要方法它决定了遗传算法的全局搜索能力对于不同的编码方式交叉操作的具体方法也不相同对于浮点数编码一般使用算术交叉对于二进制编码有单点交叉和多点交叉等方式不论何种方式在交叉操作时首先应定义交叉概率Pc这个概率表明种群中参与交叉的个体数目的期望值是M 是种群规模通常交叉概率应取较大的值以便产生较多的新个体增加全局搜索力度但是Pc过大时优良个体被破坏的可能性也越大如果Pc 太小则搜索进程变慢影响算法的运行效率一般建议的取值范围是04–099④变异操作遗传算法中的变异操作就是将染色体上某些基因座上的基因以一定的变异概率Pm用其他的等位基因替代从而形成新的个体对于浮点数编码变异操作就是将变异点处的基因用该基因取值范围内的一个随机数替换对于二进制编码则是将变异点处的基因由1变成00变成1变异操作也有多种方法如均匀变异非均匀变异高斯变异等变异操作的概率Pm要比交叉操作的概率Pc小得多变异只是产生新个体的辅助手段但它是遗传算法必不可少的一个环节因为变异操作决定了算法的局部搜索能力它弥补了交叉操作无法对搜索空间的细节进行局部搜索的不足因此交叉和变异操作相互配合共同完成对搜索空间的全局和局部搜索以上简要介绍了遗传算法的基本原理和操作归纳起来基本遗传算法一般可以表示为一个8元组6式中C 个体的编码方法E 个体适应度评价函数P0 初始种群M 种群规模选择操作交叉操作变异操作是进化终止代数进化终止条件其中有4个运行参数需要预先设定M T PcPm 种群规模M一般取为20100 终止代数T一般取100500交叉概率Pc一般取04099 变异概率Pm一般取0000101最后给出遗传算法的基本步骤①选择二进制编码或浮点数编码把问题的解表示成染色体②随机产生一群染色体个体也就是初始种群③计算每一个个体的适应度值按适者生存的原则从中选择出适应度较大的染色体进行复制再通过交叉变异过程产生更适应环境的新一代染色体群即子代④重复第3步经过这样的一代一代地进化最后就会收敛到最适应环境适应度最大的一个染色体即个体上它就是问题的最优解图2给出了基本遗传算法设计流程图其中t代表当前代数T是进化终止代数图2 基本遗传算法设计流程图3 Matlab遗传算法工具箱 gatoolMatlab的遗传算法工具箱有一个精心设计的图形用户界面可以帮助用户直观方便快速地利用遗传算法求解最优化问题在Matlab命令窗口输入命令gatool可以打开遗传算法工具箱的图形用户界面如图3所示GA工具箱的参数设置步骤如下图3 遗传算法工具1 首先使用遗传算法工具箱必须输入下列信息Fitness function 适应度函数这里指的是待优化的函数也即目标函数该工具箱总是试图寻找目标函数的最小值输入适应度函数的格式为fitnessfun其中符号产生函数fitnessfun的句柄fitnessfun代表用户编写的计算适应度函数目标函数的M文件名该M文件的编写方法如下假定我们要计算Rastrigin函数的最小值7M函数文件确定这个函数必须接受一个长度为2的行向量X也即决策向量向量的长度等于变量数目行向量X的每个元素分别和变量x1和x2对应另外M文件要返回一个标量Z其值等于该函数的值下面是计算Rastrigin函数的M文件代码function Z Ras_fun XZ 20X 1 2X 2 2-10 cos 2piX 1 cos 2piX 2M文件编写保存后再在gatool工具箱界面Fitness function栏输入 Ras_funNumber of variable 变量个数目标函数中的变量数目也即适应度函数输入向量的长度在上例中它的值是22 其次设置遗传算法参数即Options设置以下只介绍部分运行参数的设置其他未提及的参数采用默认设置即可①种群参数 PopulationPopulation size 种群规模每一代中的个体数目一般是20-100之间种群规模大算法搜索更彻底可以增加算法搜索全局最优而非局部最优的概率但是耗时也更长Initial range 初始范围其值是两行的矩阵代表初始种群中个体的搜索范围实际上是决策向量X中每个变量xi的初始搜索范围矩阵的列数等于变量个数Number of variable第一行是每个变量的下限第二行是每个变量的上限如果只输入2 1的矩阵则每个变量的初始搜索范围都一样注意初始范围仅限定初始种群中个体或决策向量的范围后续各代中的个体可以不在初始范围之内初始范围不能设置太小否则造成个体之间的差异过小即种群的多样性降低不利于算法搜索到最优解②复制参数 ReproductionCrossover fraction 交叉概率一般取04099默认08③算法终止准则 Stopping Criteria提供了5种算法终止条件Generations最大的进化代数一般取100500默认是100当遗传算法运行到该参数指定的世代计算终止Time limit指明算法终止执行前的最大时间单位是秒缺省是Inf 无穷大Fitness limit 适应度限当最优适应度值小于或等于此参数值时计算终止缺省是-InfStall generation 停滞代数如果每一代的最佳适应度值在该参数指定的代数没有改善则终止计算缺省是50代Stall time 停滞时间如果每一代的最佳适应度值在该参数指定的时间间隔内没有改善则终止计算缺省是20秒3 设置绘图参数即Plots设置绘图参数Plots工作时可以从遗传算法得到图形数据当选择各种绘图参数并执行遗传算法时一个图形窗口在分离轴上显示这些图形下面介绍其中2个参数Best fitness 选择该绘图参数时将绘制每一代的最佳适应度值和进化世代数之间的关系图如图4的上图所示图中蓝色点代表每一代适应度函数的平均值黑色点代表每一代的最佳值Distance 选择此参数时绘制每一代中个体间的平均距离它反映个体之间的差异程度所以可用来衡量种群的多样性图4的下图显示的即是每一代个体间的平均距离图44 执行算法参数设置好了之后点击工具箱界面上的按钮Star 执行求解器在算法运行的同时Current generation当前代数文本框中显示当前的进化代数通过单击Pause按钮可以使计算暂停之后再点击Resume可以恢复计算当计算完成时Status and results窗格中出现如图5所示的情形图5其中包含下列信息算法终止时适应度函数的最终值即目标函数的最优值Fitness function value 0003909079476983379算法终止原因Optimization terminated imum number of generations exceeded 超出最大进化世代数最终点即目标函数的最优解[x1 x2] [-0004 -000193]两个变量的例子三实验内容1 Rastrigin函数的最小值问题函数表达式如 7 式函数图像如下图6所示它有多个局部极小值但是只有一个全局最小值Rastrigin函数的全局最小值的精确解是0出现在[x1 x2] [0 0]处图6 Rastrigin函数图像使用遗传算法工具箱近似求解Rastrigin函数的最小值首先编写计算适应度函数的M文件然后设置运行参数绘图参数Plots勾选Best fitness和Distance两项其它参数可以使用默认值执行求解器Run solver计算Rastrigin函数的最优值观察种群多样性对优化结果的影响决定遗传算法的一个重要性能是种群的多样性个体之间的距离越大则多样性越高反之则多样性越低多样性过高或过低遗传算法都可能运行不好通过实验调整Population 种群的Initial range 初始范围参数可得到种群适当的多样性取Initial range参数值[1 11]观察Rastrigin函数最小值的计算结果取Initial range参数值[1 100]观察Rastrigin函数最小值的计算结果取Initial range参数值[1 2]观察Rastrigin函数最小值的计算结果2 微带电极欧姆损耗的优化微带电极的欧姆损耗公式可由 1 式表示令设计变量[WDt] [x1 x2 x3] X变量的约束条件如下8根据 1 式和 8 式使用遗产算法工具箱优化设计电极的结构参数W 宽度 D 间距 t 厚度使得电极的欧姆损耗最小 1 式中用到的常数提示对约束条件 8 式的处理可以在编写计算适应度函数的M文件中实现方法是在M文件中引入对每个输入变量值范围的判断语句如果任一变量范围超出 8 式的限制则给该个体的适应度施加一个惩罚使得该个体被遗传到下一代的概率减小甚至为0一般可用下式对个体适应度进行调整9其中F x 是原适应度F x 是调整后的适应度P x 是罚函数为简单计本问题中我们可以给个体的适应度 com件的返回值Z 加上一个很大的数即可如正无穷Inf四思考题1 在遗传算法当中个体的变异对结果有何影响如果没有变异结果又将如何试以Rastrigin函数最小值的计算为例说明取变异概率为0即交叉概率Crossover fraction 102 遗传算法工具箱针对的是最小化函数值问题如果要利用该工具箱计算函数的最大值该如何实现。
遗传算法简述及代码详解声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。
遗传算法基本内容遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。
遗传学与遗传算法中的基础术语比较染色体：又可以叫做基因型个体(individuals)群体/种群(population)：一定数量的个体组成，及一定数量的染色体组成，群体中个体的数量叫做群体大小。
初始群体：若干染色体的集合，即解的规模，如30，50等，认为是随机选取的数据集合。
适应度(fitness)：各个个体对环境的适应程度优化时先要将实际问题转换到遗传空间，就是把实际问题的解用染色体表示，称为编码，反过程为解码/译码，因为优化后要进行评价（此时得到的解是否较之前解优越），所以要返回问题空间，故要进行解码。
SGA采用二进制编码，染色体就是二进制位串，每一位可称为一个基因；如果直接生成二进制初始种群，则不必有编码过程，但要求解码时将染色体解码到问题可行域内。
遗传算法的准备工作:1) 数据转换操作，包括表现型到基因型的转换和基因型到表现型的转换。
前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding)，后者是它的逆操作(decoding)2) 确定适应度计算函数，可以将个体值经过该函数转换为该个体的适应度，该适应度的高低要能充分反映该个体对于解得优秀程度。
非常重要的过程。
遗传算法基本过程为:1) 编码，创建初始群体2) 群体中个体适应度计算3) 评估适应度4) 根据适应度选择个体5) 被选择个体进行交叉繁殖6) 在繁殖的过程中引入变异机制7) 繁殖出新的群体，回到第二步实例一：（建议先看实例二）求 []30,0∈x 范围内的()210-=x y 的最小值1) 编码算法选择为"将x 转化为2进制的串"，串的长度为5位（串的长度根据解的精度设 定，串长度越长解得精度越高）。
遗传算法( GA , Genetic Algorithm ) ，也称进化算法。
遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。
因此在介绍遗传算法前有必要简单的介绍生物进化知识。
一.进化论知识作为遗传算法生物背景的介绍，下面内容了解即可：种群(Population)：生物的进化以群体的形式进行，这样的一个群体称为种群。
个体：组成种群的单个生物。
基因 ( Gene ) ：一个遗传因子。
染色体 ( Chromosome )：包含一组的基因。
生存竞争，适者生存：对环境适应度高的、牛B的个体参与繁殖的机会比较多，后代就会越来越多。
适应度低的个体参与繁殖的机会比较少，后代就会越来越少。
遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。
简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。
那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。
二.遗传算法思想借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。
这样进化N代后就很有可能会进化出适应度函数值很高的个体。
举个例子，使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。
这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。
编码：需要将问题的解编码成字符串的形式才能使用遗传算法。
遗传算法多目标优化matlab源代码遗传算法(Genetic Algorithm，GA)是一种基于自然选择和遗传学原理的优化算法。
它通过模拟生物进化过程，利用交叉、变异等操作来搜索问题的最优解。
在多目标优化问题中，GA也可以被应用。
本文将介绍如何使用Matlab实现遗传算法多目标优化，并提供源代码。
一、多目标优化1.1 多目标优化概述在实际问题中，往往存在多个冲突的目标函数需要同时优化。
这就是多目标优化(Multi-Objective Optimization, MOO)问题。
MOO不同于单一目标优化(Single Objective Optimization, SOO)，因为在MOO中不存在一个全局最优解，而是存在一系列的Pareto最优解。
Pareto最优解指的是，在不降低任何一个目标函数的情况下，无法找到更好的解决方案。
因此，在MOO中我们需要寻找Pareto前沿(Pareto Front)，即所有Pareto最优解组成的集合。
1.2 MOO方法常见的MOO方法有以下几种：（1）加权和法：将每个目标函数乘以一个权重系数，并将其加和作为综合评价指标。
（2）约束法：通过添加约束条件来限制可行域，并在可行域内寻找最优解。
（3）多目标遗传算法：通过模拟生物进化过程，利用交叉、变异等操作来搜索问题的最优解。
1.3 MOO评价指标在MOO中，我们需要使用一些指标来评价算法的性能。
以下是常见的MOO评价指标：（1）Pareto前沿覆盖率：Pareto前沿中被算法找到的解占总解数的比例。
（2）Pareto前沿距离：所有被算法找到的解与真实Pareto前沿之间的平均距离。
（3）收敛性：算法是否能够快速收敛到Pareto前沿。
二、遗传算法2.1 遗传算法概述遗传算法(Genetic Algorithm, GA)是一种基于自然选择和遗传学原理的优化算法。
它通过模拟生物进化过程，利用交叉、变异等操作来搜索问题的最优解。
遗传算法及其MATLAB程序代码遗传算法及其MATLAB实现主要参考书：MATLAB 6.5 辅助优化计算与设计飞思科技产品研发中⼼编著电⼦⼯业出版社2003.1遗传算法及其应⽤陈国良等编著⼈民邮电出版社1996.6主要内容：遗传算法简介遗传算法的MATLAB实现应⽤举例在⼯业⼯程中,许多最优化问题性质⼗分复杂,很难⽤传统的优化⽅法来求解.⾃1960年以来,⼈们对求解这类难解问题⽇益增加.⼀种模仿⽣物⾃然进化过程的、被称为“进化算法（evolutionary algorithm）”的随机优化技术在解这类优化难题中显⽰了优于传统优化算法的性能。
⽬前，进化算法主要包括三个研究领域：遗传算法、进化规划和进化策略。
其中遗传算法是迄今为⽌进化算法中应⽤最多、⽐较成熟、⼴为⼈知的算法。
⼀、遗传算法简介遗传算法（Genetic Algorithm, GA）最先是由美国Mic-hgan⼤学的John Holland于1975年提出的。
遗传算法是模拟达尔⽂的遗传选择和⾃然淘汰的⽣物进化过程的计算模型。
它的思想源于⽣物遗传学和适者⽣存的⾃然规律，是具有“⽣存+检测”的迭代过程的搜索算法。
遗传算法以⼀种群体中的所有个体为对象，并利⽤随机化技术指导对⼀个被编码的参数空间进⾏⾼效搜索。
其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核⼼内容。
遗传算法的基本步骤：遗传算法是⼀种基于⽣物⾃然选择与遗传机理的随机搜索算法，与传统搜索算法不同，遗传算法从⼀组随机产⽣的称为“种群(Population)”的初始解开始搜索过程。
种群中的每个个体是问题的⼀个解，称为“染⾊体(chromos ome)”。
染⾊体是⼀串符号，⽐如⼀个⼆进制字符串。
这些染⾊体在后续迭代中不断进化，称为遗传。
在每⼀代中⽤“适值(fitness)”来测量染⾊体的好坏，⽣成的下⼀代染⾊体称为后代（offspring）。
遗传算法入门（上）代码中的进化学说与遗传学说写在之前算法所属领域遗传算法的思想解析为什么要用遗传算法？科研现状应用现状遗传算法入门系列文章：（中篇）遗传算法入门（中）实例，求解一元函数最值（MATLAB版）（下篇）遗传算法入门（下）实例，求解TSP问题（C++版）写在之前说明：本想着用大量篇幅写一篇“关于遗传算法的基本原理”作为本系列入门的第一篇，但是在找寻资料的过程中，看到网络上有大量的关于遗传算法的介绍，觉得写的都挺好，所以本文我就简单写点自己的理解。
推荐几篇关于遗传算法的介绍性文章：遗传算法详解（GA）（个人觉得很形象，很适合初学者）算法所属领域相信每个人学习一门知识之前，都会想知道这门知识属于哪一门学科范畴，属于哪一类技术领域？首先对于这种问题，GA是没有绝对的归属的。
算法的定义是解决问题的一种思想和指导理论。
而遗传算法也是解决某一问题的一种思想，用某一编程语言实现这种思想的程序具有很多特点，其中一个便是智能性和进化性，即，不需要大量的人为干涉，程序本身能够根据一定的条件自我筛选，最终得出令人满意的结果。
所以按照这种特性，把它列为人工智能领域下的学习门类毫无疑问是可以的。
遗传算法的思想是借鉴了达尔文的进化学说和孟德尔的遗传学说，把遗传算法说成是一门十足的仿生学一点都不过分。
然而从应用的角度出发，遗传算法是求最优解问题的好方法，如信号处理中的优化、数学求解问题、工业控制参数最优解、神经网络中的激活函数、图像处理等等，所以把遗传算法说成优化范畴貌似也说的过去。
为了方便理解，我们可以暂时将其定位为人工智能–智能优化，这也是很多书中描述遗传算法的惯用词汇。
遗传算法的思想解析遗传算法（gentic algorithms简称GA）是模拟生物遗传和进化的全局优化搜索算法我们知道，在人类的演化中，达尔文的进化学说与孟德尔的遗传学说起着至关重要的理论指导。
每个人作为一个个体组成一个人类种群，正是经历着物竞天择，才会让整个群体慢慢变的更好，即更加适应周围的环境。
实验一 遗传算法解决函数优化问题一、实验目的1.掌握遗传算法的基本原理和步骤。
2. 复习VB 、VC 的基本概念、基本语法和编程方法，并熟练使用VB 或VC 编写遗传算法程序。
二、实验内容1. 上机编写程序，解决以下函数优化问题：()1021min 100i i i f x x =⎛⎫=≤ ⎪⎝⎭∑X2. 调试程序。
3. 根据实验结果，撰写实验报告。
三、实验原理遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。
标准遗传算法流程图如下图所示，主要步骤可描述如下： ① 随机产生一组初始个体构成初始种群。
② 计算每一个体的适配值（fitness value ，也称为适应度）。
适应度值是对染色体(个体)进行评价的一种指标，是GA 进行优化所用的主要信息，它与个体的目标值存在一种对应关系。
③ 判断算法收敛准则是否满足，若满足，则输出搜索结果；否则执行以下步骤。
④ 根据适应度值大小以一定方式执行复制操作（也称为选择操作）。
⑤ 按交叉概率p c 执行交叉操作。
⑥ 按变异概率p m 执行变异操作。
⑦ 返回步骤②。
图1.1 标准遗传算法流程图四、程序代码#include <stdio.h>#include <math.h>#include <stdlib.h>#include<time.h>#define byte unsigned char#define step 200 //步长#define MAX 50#define N 10 //随机数个数#define Pc 0.74 //被选择到下一代的概率,个数=Pc*N，小于N 下一代数=上一代，不用处理#define Pt 0.25 //交叉的概率,个数=Pt*N 舍，小于N 0~(n2+1)随机数，之后部分开始交叉#define Pm 0.01 //变异的概率,个数=Pm*N*n2 入，小于N 0~(N*(n2+1))随机数/(n2+1)=个体,0~(N*(n2+1))随机数%(n2+1)=该个体基因位置#define n2 15//2的15次方,共16位#define next_t (int)(Pt*N)//交叉个数#define next_m (int)(Pm*N+1)//变异个数向后约等于#define e 0.001//次数限制阈值/*int N=10; //随机数个数float Pc=0.74; //被选择到下一代的概率,个数=Pc*N，小于N 下一代数=上一代，不用处理float Pt=0.25; //交叉的概率,个数=Pt*N 舍，小于N 0~(n2+1)随机数，之后部分开始交叉float Pm=0.01; //变异的概率,个数=Pm*N*n2 入，小于N 0~(N*(n2+1))随机数/(n2+1)=个体,0~(N*(n2+1))随机数%(n2+1)=该个体基因位置*/bytebitary[N][n2+1],bitary0[N][n2+1];//二进制int src1[N];float ShowType(int a);//表现型void BinNum(int a);//二进制位数n2 float fit_func(float a);//适应度void DecToBin (int src,int num);//十进制转二进制void BinToDec (void);//十进制转二进制int selectT(float a,float b[10]);//选择交叉个体int selectM(float a,float b[10]);//选择变异个体void main(void){//范围是[-100,100]*************************** intsrc[N],i=0,j=0,k=0,count=0;//十进制float show[N];//表现型float fit[N],sumfit=0;//适应度float pcopy[N];//优胜劣汰，遗传到下一代的概率fit[i]/总和(fit[i]) float pacc[N];//pcopy[i]累加概率值float prand[N];//随机产生N个0~1的下一代概率int iselect;//根据概率选择到的个体序号int new_select[N];//根据概率选择到的个体int new_T[next_t],new_M[next_m];float min,min1;printf("随机数(原始母体),表现型, 适配值\n");srand( (unsigned)time(NULL) );for(i=0;i<N;i++){src[i]=rand()%32768;//rand()%201-100===>-100~100的十进制随机数随时间递增show[i]=ShowType(src[i]);//转化成表现型fit[i]=fit_func(show[i]);//计算各个适配值(适应度)sumfit=sumfit+fit[i]; //种群的适应度总和printf("%5d, %f, %f\n",src[i],s how[i],fit[i]);}printf("\n第%d代适配总值\n%f\n",count,sumfit);//第0代count++;min=sumfit;printf("\n遗传到下一代的概率\n");for(i=0;i<N;i++){pcopy[i]=fit[i]/sumfit;printf("%f, ",pcopy[i]);}// 求选择(被复制)的累加概率,用于轮盘赌产生随机数区域，选择下一代个体printf("\n遗传到下一代的累加概率\n");pacc[0]=pcopy[0];for(i=1;i<N;i++){pacc[i]=pacc[i-1]+pcopy[i];printf("%f, ",pacc[i]);}//每个src[N]都随机取其中一个pcopy，取得的值pcopy[i]跟pcopy概率大小有关//模拟轮盘赌方式选择新一代printf("\n\n新产生的第%d代,表现型, 适配值\n",count);srand( (unsigned)time(NULL) );for(i=0;i<N;i++){prand[i]=(float)( (rand()%101)*0.01 );//0~1的十进制小数，精确到0.01iselect=selectT(prand[i],pacc);new_select[i]=src[iselect];//产生的新一代,十进制show[i]=ShowType(new_select[i]);/ /转化成表现型fit[i]=fit_func(show[i]);DecToBin (new_select[i],i);sumfit=sumfit+fit[i]; //种群的适应度总和printf(" %d %f %f\n",new_selec t[i],show[i],fit[i]);}printf("\n第%d代适配总值\n%f\n",count,sumfit);//第1代min1=sumfit;if (min>sumfit){min1=min;min=sumfit;}while(fabs(min-min1)>e&&count<MAX ){//从新一代选择个体交叉printf("\n随机产生交叉个体号");srand( (unsigned)time(NULL) );for(i=0;i<2;i++) //简单起见交叉数设为2{new_T[i]=rand()%N;//0~10的十进制数产生的交叉个体if (i>0)//两个不同个体交叉while(new_T[i]==new_T[i-1])new_T[i]=rand()%N;printf("%d, ",new_T[i]);}srand( (unsigned)time(NULL) );//随机产生交叉位置k=rand()%n2;//0~14的十进制数printf("\n随机产生交叉位置 %d\n",k);printf("\n原编码\n");for(j=n2;j>=0;j--)printf("%c",bitary[new_T[0]][j]);printf("\n");for(j=n2;j>=0;j--)printf("%c",bitary[new_T[1]][j]);printf("\n位置%d后交叉编码\n",k);char temp;for(i=k+1;i<n2+1;i++)//交叉{temp=bitary[new_T[0]][i];bitary[new_T[0]][i]=bitary[new_T[ 1]][i];bitary[new_T[1]][i]=temp;}for(j=n2;j>=0;j--)printf("%c",bitary[new_T[0]][j]);printf("\n");for(j=n2;j>=0;j--)printf("%c",bitary[new_T[1]][j]);//从新一代选择个体变异printf("\n随机产生变异个体号");srand( (unsigned)time(NULL) );for(i=0;i<1;i++) //简单起见变异数设为1个{new_M[i]=rand()%N;//0~9的十进制数产生的变异个体k=rand()%(n2+1);//0~15的十进制数printf("%d\n编码位置 %d\n原编码\n",new_M[i],k);for(j=n2;j>=0;j--)printf("%c",bitary[new_M[i]][j]);if(bitary[new_M[i]][k]=='0')//变异取反bitary[new_M[i]][k]='1';elsebitary[new_M[i]][k]='0';printf("\n位置%d变异后编码\n",k);for(j=n2;j>=0;j--)printf("%c",bitary[new_M[i]][j]);}printf("\n");count++;//新的bitary即产生第二代printf("\n新产生的第%d代\n",count);for(i=0;i<N;i++){for(j=n2;j>=0;j--)printf("%c",bitary[i][j]);printf("\n");}BinToDec ();//二进制转十进制 for(i=0;i<N;i++){new_select[i]=src1[i];show[i]=ShowType(src[i]);//转化成表现型fit[i]=fit_func(show[i]);//计算各个适配值(适应度)sumfit=sumfit+fit[i]; //种群的适应度总和printf("%5d, %f, %f\n",src1[i], show[i],fit[i]);}printf("\n第%d代适配总值\n%f\n",count,sumfit);if (sumfit<min){min1=min;min=sumfit;}}printf("\n\n\n*****************\n over\n*****************\n",sumfit);}//////////////////////////子函数////////////////float ShowType(int a){float temp;temp=(float)(a*200.0/32767-100);/ /(2的15次方减1)=32767return temp;}float fit_func(float a){float temp;temp=a*a;return temp;}void DecToBin (int src,int num){int i;//注意负数的补码if (src<0){src=(int)pow(2,16)-abs(src);}for (i=0;i<=n2;i++){bitary[num][i]='0';bitary0[num][i]='0';if(src){bitary[num][i]=(src%2)+48;bitary0[num][i]=(src%2)+48;src=(int)(src/2);}}}void BinToDec (void){int i,j;for(i=0;i<N;i++){src1[i]=0;for(j=0;j<n2+1;j++){src1[i]=src1[i]+(bitary[i][j]-48) *(int)pow(2,j);}}}int selectT(float a,float b[10]) {int i;for(i=0;i<N;i++){if (a<b[i])return i;}return -1;} 五、实验结果分析：随机性大，精度不高六、实验心得理论指导实践，在实践中得以提高。
实验十遗传算法与优化问题一、问题背景与实验目的遗传算法（Genetic Algorithm —GA）,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975 年首先提出的•遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位.本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算.1. 遗传算法的基本原理遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程. 它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代. 后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程. 群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解.值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）.（1）遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念.首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系.这些概念如下：（2）遗传算法的步骤遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossove）、变异（Mutation）.遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解.然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群.经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解.下面给出遗传算法的具体步骤，流程图参见图1:第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；第四步：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步.图1 一个遗传算法的具体步骤遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要 步骤，此算法会一直运行直到找到满足条件的最优解为止.2. 遗传算法的实际应用例 1:设 f (x) x 2x 0.5，求 max f(x), x ［ 1,2］.注：这是一个非常简单的二次函数求极值的问题，相信大家都会做•在此我 们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题.在此将细化地给出遗传算法的整个过程.(1)编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把1到2这个区间内的数用计 算机语言表示出来.编码就是表现型到基因型的映射，编码时要注意以下三个原则： 完备性：问题空间中所有点(潜在解)都能成为 GA 编码空间中的点(染色 体位串)的表现型；健全性：GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应.这里我们通过采用二进制的形式来解决编码问题， 将某个变量值代表的个体 表示为一个｛0，1｝二进制串.当然，串长取决于求解的精度.如果要设定求解精 度到六位小数，由于区间长度为2 ( 1) 3，则必须将闭区间［1,2］分为3 106 等分•因为2097152 2213 106 2224194304所以编码的二进制串至少需要22位.将一个二进制串(b 21b 20b 19…b 1b 0)转化为区间［1,2］内对应的实数值很简单， 只需采取以下两步(Matlab 程序参见附录4):1)将一个二进制串(b 21b 20b 19・・・b 1b 。
)代表的二进制数化为10进制数：21(b 21b 20b ］9( b i 2 )10 x'i 02) x'对应的区间［1,2］内的实数:例如，一个二进制串 a=<1000101110110101000111 表示实数 0.637197.x' =(1000101110110101000111)=2288967二进制串 <0000000000000000000000> <1111111111111111111111>则分别 表示区间的两个端点值-1和2.利用这种方法我们就完成了遗传算法的第一步 编码， 这种二进制编码的方法完全符合上述的编码的三个原则.x' 2 ( 1)22222889673 22210.637197首先我们来随机的产生一个个体数为 4个的初始群体如下: pop(1)={ 1.523032, 0.574022 , -0.697235 , 0.247238 } 接下来我们就要解决每个染色体个体的适应值问题了.(2) 定义适应函数和适应值由于给定的目标函数f(x)x 2 2x 0.5在[1,2]内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系， 标函数的优化方向应对应于适应值增大的方向, 打下基础.f (x) F min ,若 f (x) F min 00, 其他式中F min 既可以是特定的输入值，也可以是当前所有代或最近 K 代中f(x)的最 小值，这里为了便于计算，将采用了一个特定的输入值.若取F min 1,则当f(x) 1时适应函数g(x) 2 ；当f(X ) 1.1时适应函数 g(x) 0 . 由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下 (Matlab 程序参见附录3):f [pop(1)]={ 1.226437,1.318543 , -1.380607,0.933350 }然后通过适应函数计算出适应值分别如下 (Matlab 程序参见附录5、附录6):取 F min1，g[pop(1)]= { 2.226437,2.318543 , 0,1.933350 }(3) 确定选择标准这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值 比例叫作入选概率.其计算公式如下：对于给定的规模为n 的群体pop={a 1,a 2,a 3,L ,a n }，个体a i 的适应值为g(aj ， 则其入选概率为P s (a)ng(ai), i 1,2,3, ,ng(a i )i 1由上述给出的群体，我们可以计算出各个个体的入选概率.4首先可得 g(a i ) 6.478330，i 1 4然后分别用四个个体的适应值去除以g(a )，得：i 1P(a1)=2.226437 / 6.478330 = 0.343675 %% a1 P(a2)=2.318543 / 6.478330 = 0.357892 %% a2 P(a3)= 0 / 6.478330 = 0 %% a3pop(1)={<1101011101001100011110> <1000011001010001000010> <0001100111010110000000> <0110101001101110010101〉}%% a1 %% a2 %% a3%% a4 (Matlab 程序参见附录2)保证映射后的适应值非负，而且目 也为以后计算各个体的入选概率 对于本题中的最大化问题，定义适应函数g(x)，采用下述方法: g(x)P(a4)=1.933350 / 6.478330 = 0.298433 %% a4 (Matlab 程序参见附录7)(4)产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群(Matlab程序参见附录&附录11).要说明的是：附录11的算法与这里不完全相同•为保证收敛性，附录 11的 算法作了修正，采用了最佳个体保存方法(elitist model ),具体内容将在后面给 出介绍.由初始群体的入选概率我们淘汰掉 a3,再加入a2补足成与群体同样大小的 种群得到newpop(1)如下：n ewpop(1)={<1101011101001100011110> %%a1 <1000011001010001000010〉， %%a2<1000011001010001000010> %%a2 <0110101001101110010101〉}%%a4(5) 交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体， 然后得到新 的染色体组，组成新的群体(Matlab 程序参见附录9).我们把之前得到的n ewpop(1)的四个个体两两组成一对，重复的不配对，进 行交叉.(可以在任一位进行交叉)<1101011叭 /1001100011110> <1101011101010001000010>交叉得：<100001100 1010001000010〉 <1000011001001100011110> <1000011001010010010101>交叉得：通过交叉得到了四个新个体，得到新的群体jchpop (1)如下：jchpop(1)={<1101011101010001000010> <1000011001001100011110> <1000011001010010010101> <0110101001101101000010>}这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐， 这里就不着重介绍了. (6) 变异变异也就是通过一个小概率改变染色体位串上的某个基因 (Matlab 程序参见附录10).现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到 了新的群体pop(2)如下：pop(2)= {<1101011101010001000010> <1000011001001100011110> <1000011011010010010101>， <0110101001101101000010> }然后重复上述的选择、交叉、变异直到满足终止条件为止. (7) 终止条件10010101>，<0110101001101101000010> <10000110010100 <0110101001101101000010>，遗传算法的终止条件有两类常见条件：（1采用设定最大（遗传）代数的方法，一般可设定为50代，此时就可能得出最优解•此种方法简单易行，但可能不是很精确（Matlab 程序参见附录1）; （2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制.3. 遗传算法的收敛性前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍•作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下图2所示.图2均衡搜索的具体实现图示应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决.目前普遍认为，标准遗传算法并不保证全局最优收敛•但是，在一定的约束条件下，遗传算法可以实现这一点.下面我们不加证明地罗列几个定理或定义，供读者参考（在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）.定理1如果变异概率为P m （0,1），交叉概率为P c [0,1]，同时采用比例选择法（按个体适应度占群体适应度的比例进行复制），则标准遗传算法的变换矩阵P是基本的.定理2标准遗传算法（参数如定理1）不能收敛至全局最优解.由定理2可以知道，具有变异概率P m（0,1），交叉概率为P c [0,1]以及按比例选择的标准遗传算法是不能收敛至全局最最优解.我们在前面求解例1时所用的方法就是满足定理1的条件的方法.这无疑是一个令人沮丧的结论.然而，庆幸的是，只要对标准遗传算法作一些改进，就能够保证其收敛性.具体如下：我们对标准遗传算法作一定改进，即不按比例进行选择，而是保留当前所得的最优解（称作超个体）.该超个体不参与遗传.最佳个体保存方法（elitist model）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中.此种选择操作又称复制（copy）. De Jong 对此方法作了如下定义：定义设到时刻t (第t代)时，群体中a (t)为最佳个体•又设A (t + 1) 为新一代群体，若A (t + 1)中不存在a* (t),则把a*(t)作为A (t + 1)中的第n+1个个体(其中，n为群体大小)(Matlab程序参见附录11).采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏•但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解•也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索•所以此方法一般都与其他选择方法结合使用.定理3具有定理1所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解.当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丢失.但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解.有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况.定理4具有定理1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解.2 .例2:设f(x) 3 x x，求maxf(x), x [0,2]，编码长度为5，采用上述定理4所述的“在选择前保留当前最优解的遗传算法”进行.此略，留作练习.二、相关函数(命令)及简介本实验的程序中用到如下一些基本的Matlab函数：ones, zeros, sum, size, length, subs, double等，以及for, while等基本程序结构语句，读者可参考前面专门关于Matlab的介绍，也可参考其他数学实验章节中的“相关函数(命令) 及简介”内容，此略.三、实验内容上述例1的求解过程为：群体中包含六个染色体，每个染色体用22位0—1码，变异概率为0.01，变量区间为[1,2]，取Fmin= 2，遗传代数为50代，则运用第一种终止条件(指定遗传代数)的Matlab程序为：[Cou nt,Result,BestMember]=Ge netic1(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,50)执行结果为：Count =50Result =1.0316 1.0316 1.0316 1.0316 1.0316 1.03161.4990 1.4990 1.4990 1.4990 1.4990 1.4990BestMember =1.03161.49901,4 阳1 ------ 1-------------- 1 --------■------- 1 ------------- 1-------------- r ------------- 1 ------------- 1 ------------- 1 -------1.4D9 - z --------------------------------------------------------------------------------------14a«y - I -1.4SSS - ―I -1 JQR7____ i _____ I _____| ____ |____ | ____ |_____ | ____ 1 ____ |____ I! 0 £讪祐M 药丑I % 如站和图2例1的计算结果(注：上图为遗传进化过程中每一代的个体最大适应度；而下图为目前为止的个体最大适应度--- 单调递增)我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当x取1.0316时，Max f(x) 1.4990 .当然这个解和实际情况还有一点出入(应该是x取1时，Max f (x) 1.5000 ), 但对于一个计算机算法来说已经很不错了.我们也可以编制Matlab程序求在第二种终止条件下的最优解.此略，留作练习.实践表明，此时的遗传算法只要经过10代左右就可完成收敛，得到另一个“最优解”，与前面的最优解相差无几.四、自己动手1 .用Matlab编制另一个主程序Genetic2.m，求例1的在第二种终止条件下的最优解. 提示：一个可能的函数调用形式以及相应的结果为：[Cou nt,Result,BestMember]=Ge netic2(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,0.00001) Count =13Result =1.0392 1.0392 1.0392 1.0392 1.0392 1.03921.4985 1.4985 1.4985 1.4985 1.4985 1.4985BestMember =1.03921.4985可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小.可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只要经过10代左右就可以完成收敛，达到一个最优解.2•按照例2的具体要求，用遗传算法求上述例2的最优解.3•附录9子程序Crossing.m中的第3行到第7行为注解语句•若去掉前面的% 号，则程序的算法思想有什么变化？4. 附录9子程序Cross in g.m中的第8行至第13行的程序表明，当Dim(1)>=3 时，将交换数组Population的最后两行，即交换最后面的两个个体.其目的是什么？5. 仿照附录10子程序Mutatio n.m，修改附录9子程序Cross in g.m,使得交叉过程也有一个概率值(一般取0.65~0.90);同时适当修改主程序Genetic1.m或主程序Genetic2.m，以便代入交叉概率.6. 设f(x) x2 4x 1,求maxf(x), x [ 2,2]，要设定求解精度到15位小数.五、附录附录1:主程序Genetic1.mfun ctio n[Cou nt,Result,BestMember]=Ge netic1(MumberLe ngth,MemberNumber,Fu nctio nFitn ess,MinX,MaxX,Fmi n, Mutatio nProbability,Ge n)Populatio n=Populatio nln itialize(MumberLe ngth,MemberNumber);global Count;global Curren tBest;Cou nt=1;Populatio nCode=Populati on;Populatio nFit ness=Fit ness(Populatio nCode,F un ctio nFitness,MinX,MaxX,Mumbe rLen gth);Populatio nFit nessF=Fit nessF(Populatio nFit ness,Fmi n);Populatio nProbability=Probability(Populatio nFit nessF);[Populatio n,Curre ntBest,EachGe nMaxFit ness]=Elitist(PopulationCode,Populatio nF it ness,MumberLe ngth);EachMaxFit ness(Co un t)=EachGe nM axFit ness;MaxFit ness(Cou nt)=Curre ntBest(le ngth(Curre ntBest));while Cou nt<GenNewPopulatio n=Select(Populatio n,Populatio nProbability,MemberNumber);Populatio n=NewPopulatio n;NewPopulatio n=Crossi ng(Populatio n,Fun ctio nFit ness,MinX,MaxX,MumberLe ngth);Populatio n=NewPopulatio n;NewPopulatio n=Mutatio n(Populatio n,Mutatio nProbability);Populatio n=NewPopulatio n;Populatio nFit ness=Fit ness(Populatio n,Fun ctio nFit ness,MinX,MaxX,MumberLe ngth);Populatio nFit nessF=Fit nessF(Populatio nFit ness,Fmi n);Populatio nProbability=Probability(Populatio nFit nessF); Cou nt=Cou nt+1;[NewPopulatio n,Curre ntBest,EachGe nM axFit ness]=Elitist(Populatio n,Populatio nF it n ess,MumberLe ngth);EachMaxFit ness(Co un t)=EachGe nM axFit ness;;MaxFit ness(Cou nt)=Curre ntBest(le ngth(Curre ntBest));Populatio n=NewPopulatio n;endDim=size(Populatio n);Result=o nes(2,Dim(1));for i=1:Dim(1)Result(1,i)=Tra nslate(Populatio n(i,:),MinX,MaxX,MumberLe ngth);endResult(2,:)=Populati onF it ness;BestMember(1,1)=Tra nslate(Curre ntBest(1:MumberLe ngth),MinX,MaxX,Mumb erLe ngth);BestMember(2,1)=Curre ntBest(MumberLe ngth+1);close allsubplot(211)plot(EachMaxFit ness)subplot(212)plot(MaxFit ness)【程序说明】主程序Genetic1.m包含了8个输入参数：(1) MumberLength: 表示一个染色体位串的二进制长度. (例1中取22)(2) MemberNumber：表示群体中染色体的个数.(例1中取6个)(3) Fun ctio nFit ness：表示目标函数，是个字符串，因此用表达式时，用单引号括出.(例1中是f(x) x2 2x 0.5)⑷MinX : 变量区间的下限.(例1中是［1,2］中的)(5) MaxX : 变量区间的上限.(例1中是［1,2］中的2)⑹Fmin: 定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出.(例1中取Fmin= 2)(7) MutationProbability : 表示变异的概率，一般都很小.(例1中取0.01)(8) Gen：表示遗传的代数，也就是终止程序时的代数. (例1中取50)另外，主程序Genetid.m包含了3个输出值：Count表示遗传的代数；Result 表示计算的结果，也就是最优解；BestMember表示最优个体及其适应值.附录2：子程序Populationlnitialize.mfun ctio n Populatio n=Populatio nln itialize(MumberLe ngth,MemberNumber) Temporary=ra nd(MemberNumber,MumberLe ngth);Populatio n=(Temporary>=0.5* on es(size(Temporary)));【程序说明】子程序PopulationInitialize.m用于产生一个初始群体.这个初始群体含有MemberNumber个染色体，每个染色体有MumberLength个基因(二进制码).附录3:子程序Fitness.mfunction Populati onF it ness=Fit ness(Populatio nCode,Fu nctio nFit ness,MinX,MaxX,MumberLe ngth) Dim=size(Populati on Code);Populatio nFit ness=zeros(1,Dim(1));for i=1:Dim(1)Populatio nF it ness(i)=Tran sfer(Populatio nCode(i,:),Fu nctio nFit ness,MinX,MaxX,MumberLe ngth);end【程序说明】子程序Fitness.m用于计算群体中每一个染色体的目标函数值.子程序中含有5个输入参数：PopulationCode表示用0—1代码表示的群体，Fun ctio nFit ness表示目标函数，它是一个字符串，因此写入调用程序时，应该用单引号括出，MumberLength表示染色体位串的二进制长度. MinX和MaxX分别指变量区间的上下限.附录4：子程序Translate.mfun cti on Populatio nData=Tra nslate(Populatio nCode,MinX,MaxX,MumberLe ngth) Populati on Data=0;Dim=size(Populati on Code);for i=1:Dim(2)Populatio nData=Populatio nData+Populatio nCode(i)*(2A(MumberLe ngth-i));endPopulatio nData=MinX+Populatio nData*(MaxX-MinX)/(2ADim(2)-1);【程序说明】子程序Translate.m把编成码的群体翻译成变量的数值•含有4个输入参数，PopulationCode, MinX, MaxX, MumberLength .附录5:子程序Transfer.mfunction Populati onF it ness=Tran sfer(Populatio nCode,F un ctio nFit ness,MinX,MaxX,MumberLe ngth) Populati onF it ness=0;Populatio nData=Tra nslate(Populatio nCode,MinX,MaxX,MumberLe ngth);Populatio nF it ness=double(subs(F un cti onF it ness,'x',sym(Populatio nData)));【程序说明】子程序Transfer把群体中的染色体的目标函数值用数值表示出来，它是Fitness的重要子程序.其有5个输入参数分别为PopulationCode, FunctionFitness, MinX, MaxX , MumberLength.附录6:子程序FitnessF.mfunction Populati onF it nessF=Fit nessF(Populati onF it ness,F min)Dim=size(Populatio nFit ness);Populatio nFit nessF=zeros(1,Dim(2));for i=1:Dim(2)if Populati onF it ness(i)>F minPopulati onF it nessF(i)=Populatio nF it ness(i)-F min;endif Populati onF it ness(i)<=FminPopulati onF it nessF(i)=0;endend【程序说明】子程序FitnessF.m是用于计算每个染色体的适应函数值的.其输入参数如下：PopulationFitness为群体中染色体的目标函数值，Fmin为定义适应函数过程中给出的一个目标函数的可能的最小值.附录7：子程序Probability.mfun ctio n Populatio nProbability=Probability(Populatio nFit ness)SumPopulati onF it ness=sum(Populati onF it ness);Populatio nProbability=Populatio nFit ness/SumPopulatio nFit ness;【程序说明】子程序Probability.m用于计算群体中每个染色体的入选概率，输入参数为群体中染色体的适应函数值Populatio nFit ness附录8子程序Select.mfun ctio n NewPopulati on=Select(Populatio n,Populatio nProbability,MemberNumber)CProbability(1)=Populatio nProbability(l);for i=2:MemberNumberCProbability(i)=CProbability(i-1)+Populatio nProbability(i);endfor i=1:MemberNumberr=ra nd(1);In dex=1;while r>CProbability(I ndex)In dex=In dex+1;endNewPopulati on (i,:)=Populati on (I ndex,:);end【程序说明】子程序Select.m根据入选概率(计算累计概率)在群体中按比例选择部分染色体组成种群，该子程序的3个输入参数分别为：群体Population,入选概率PopulationProbability，群体中染色体的个数MemberNumber.附录9:子程序Crossing.mfun ctio n NewPopulati on=Cross in g(Populatio n,Fun cti onF it ness, MinX, MaxX,MumberLe ngth) %%Populati onF it ness=%% Fit ness(Populatio n,Fu nctio nFit ness,MinX,MaxX,MumberLe ngth);%%Populatio nProbability=Probability(Populatio nFitness); %%[SortResult,SortSite]=sort(Populatio nProbability);%%Populatio n=Populatio n(SortSite,:);Dim=size(Populatio n);if Dim⑴>=3Temp=Populatio n( Dim(1),:);Populatio n(Dim(1),:)=Populatio n(Dim(1)-1,:);Populatio n(Dim(1)-1,:)=Temp;endfor i=1:2:Dim(1)-1SiteArray=ran dperm(Dim(2));Site=SiteArray(1);Temp=Populati on (i,1:Site);Populatio n(i,1:Site)=Populatio n(i+1,1:Site);Populatio n(i+1,1:Site)=Temp;endNewPopulatio n=Populatio n;【程序说明】子程序Cross in g.m用于群体中的交叉并产生新群体.其输入参数为：Population, FunctionFitness MinX , MaxX , MumberLength.附录10:子程序Mutation.mfunction NewPopulation=Mutation(Population,MutationProbability)Dim=size(Populatio n);for i=1:Dim(1)Probability=ra nd(1);Site=ra ndperm(Dim(2));if ProbabilityvMutatio nProbabilityif Populatio n(i,Site(1))==1Populatio n(i,Site(1))=0;endif Populatio n(i,Site(1))==0Populatio n(i,Site(1))=1;endendendNewPopulatio n=Populatio n;【程序说明】子程序Mutation.m用于群体中少量个体变量并产生新的群体.输入参数为：群体Population和变异概率MutationProbability .附录11:子程序Elitist.mfunction [NewPopulationlncludeMax,CurrentBest,EachGenMaxFitness]=Elitist(Populatio n,Populatio nFit ness,MumberLe ngth)global Count Curren tBest;[Mi nFit ness,Mi nSite]=mi n( Populatio nFit ness);[MaxFit ness,MaxSite]=max(Populati onF it ness);EachGe nMaxFit ness=MaxFit ness;if Cou nt==1Curre ntBest(1:MumberLe ngth)=Populatio n(MaxSite,:);Curre ntBest(MumberLe ngth+1)=Populatio nFit ness(MaxSite);elseif Curre ntBest(MumberLe ngth+1)<Populatio nFit ness(MaxSite);Curre ntBest(1:MumberLe ngth)=Populatio n(MaxSite,:);Curre ntBest(MumberLe ngth+1)=Populatio nFit ness(MaxSite);endPopulatio n(Mi nSite,:)=Curre ntBest(1:MumberLe ngth); endNewPopulatio nln cludeMax=Populatio n;【程序说明】子程序Elitist.m用到最佳个体保存方法(“优胜劣汰”思想).输入参数为：群体Population,目标函数值PopulationFitness和染色体个数MumberLe ngth.。
