下载文档原格式
遗传算法详解（含MATLAB代码）Python遗传算法框架使用实例（一）使用Geatpy实现句子匹配在前面几篇文章中，我们已经介绍了高性能Python遗传和进化算法框架——Geatpy的使用。
本篇就一个案例进行展开讲述：pip install geatpy更新至Geatpy2的方法：pip install --upgrade --user geatpy查看版本号，在Python中执行：import geatpyprint(geatpy.__version__)我们都听过“无限猴子定理”，说的是有无限只猴子用无限的时间会产生特定的文章。
在无限猴子定理中，我们“假定”猴子们是没有像人类那样“智能”的，而且“假定”猴子不会自我学习。
因此，这些猴子需要“无限的时间"。
而在遗传算法中，由于采用的是启发式的进化搜索，因此不需要”无限的时间“就可以完成类似的工作。
当然，需要产生的文章篇幅越长，那么就需要越久的时间才能完成。
下面以产生"T om is a little boy, isn't he? Yes he is, he is a good and smart child and he is always ready to help others, all in all we all like him very much."的句子为例，讲述如何利用Geatpy实现句子的搜索。
之前的文章中我们已经讲述过如何使用Geatpy的进化算法框架实现遗传算法编程。
这里就直接用框架。
把自定义问题类和执行脚本编写在下面的"main.py”文件中：# -*- coding: utf-8 -*-import numpy as npimport geatpy as eaclass MyProblem(ea.Problem): # 继承Problem父类def __init__(self):name = 'MyProblem' # 初始化name（函数名称，可以随意设置） # 定义需要匹配的句子strs = 'Tom is a little boy, isn't he? Yes he is, he is a good and smart child and he is always ready to help others, all in all we all like him very much.'self.words = []for c in strs:self.words.append(ord(c)) # 把字符串转成ASCII码M = 1 # 初始化M（目标维数）maxormins = [1] # 初始化maxormins（目标最小最大化标记列表，1：最小化该目标；-1：最大化该目标）Dim = len(self.words) # 初始化Dim（决策变量维数）varTypes = [1] * Dim # 初始化varTypes（决策变量的类型，元素为0表示对应的变量是连续的；1表示是离散的）lb = [32] * Dim # 决策变量下界ub = [122] * Dim # 决策变量上界lbin = [1] * Dim # 决策变量下边界ubin = [1] * Dim # 决策变量上边界# 调用父类构造方法完成实例化ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin)def aimFunc(self, pop): # 目标函数Vars = pop.Phen # 得到决策变量矩阵diff = np.sum((Vars - self.words)**2, 1)pop.ObjV = np.array([diff]).T # 把求得的目标函数值赋值给种群pop的ObjV执行脚本if __name__ == "__main__":"""================================实例化问题对象============================="""problem = MyProblem() # 生成问题对象"""==================================种群设置================================"""Encoding = 'RI' # 编码方式NIND = 50 # 种群规模Field = ea.crtfld(Encoding, problem.varTypes, problem.ranges,problem.borders) # 创建区域描述器population = ea.Population(Encoding, Field, NIND) # 实例化种群对象（此时种群还没被初始化，仅仅是完成种群对象的实例化）"""================================算法参数设置=============================="""myAlgorithm = ea.soea_DE_rand_1_L_templet(problem, population) # 实例化一个算法模板对象myAlgorithm.MAXGEN = 2000 # 最大进化代数"""===========================调用算法模板进行种群进化========================="""[population, obj_trace, var_trace] = myAlgorithm.run() # 执行算法模板population.save() # 把最后一代种群的信息保存到文件中# 输出结果best_gen = np.argmin(obj_trace[:, 1]) # 记录最优种群是在哪一代best_ObjV = obj_trace[best_gen, 1]print('最优的目标函数值为：%s'%(best_ObjV))print('有效进化代数：%s'%(obj_trace.shape[0]))print('最优的一代是第 %s 代'%(best_gen + 1))print('评价次数：%s'%(myAlgorithm.evalsNum))print('时间已过 %s 秒'%(myAlgorithm.passTime))for num in var_trace[best_gen, :]:print(chr(int(num)), end = '')上述代码中首先定义了一个问题类MyProblem，然后调用Geatpy内置的soea_DE_rand_1_L_templet算法模板，它实现的是差分进化算法DE-rand-1-L，详见源码：运行结果如下：种群信息导出完毕。
遗传算法代码python一、简介遗传算法是一种通过模拟自然选择和遗传学原理来寻找最优解的优化算法。
它广泛应用于各种领域，包括优化问题、搜索和机器学习等。
二、代码概述以下是一个简单的遗传算法的Python代码示例，用于解决简单的优化问题。
该算法使用一个简单的二进制编码方式，并使用适应度函数来评估每个个体的适应度。
三、代码实现```pythonimportnumpyasnp#遗传算法参数POPULATION_SIZE=100#种群规模CROSSOVER_RATE=0.8#交叉概率MUTATION_RATE=0.1#变异概率MAX_GENERATIONS=100#最大迭代次数#适应度函数deffitness(individual):#在这里定义适应度函数，评估每个个体的适应度#这里简单地返回个体值的平方，可以根据实际问题进行调整returnnp.sum(individual**2)#初始种群生成pop=np.random.randint(2,size=(POPULATION_SIZE,))#迭代过程forgenerationinrange(MAX_GENERATIONS):#评估种群中每个个体的适应度fitness_values=np.apply_along_axis(fitness,1,pop)#选择种群selected_idx=np.random.choice(np.arange(POPULATION_SIZE), size=POPULATION_SIZE,replace=True,p=fitness_values/fitness_va lues.sum())selected_pop=pop[selected_idx]#交叉操作ifCROSSOVER_RATE>np.random.rand():cross_points=np.random.rand(POPULATION_SIZE,2)<0.5#随机选择交叉点cross_pop=np.array([np.hstack((individual[cross_points[i, 0]:cross_points[i,1]]+individual[cross_points[i,1]:],other))f ori,otherinenumerate(selected_pop)]).T#合并个体并随机交叉得到新的个体cross_pop=cross_pop[cross_points]#将交叉后的个体重新排列成原始种群大小selected_pop=np.vstack((selected_pop,cross_pop))#将新个体加入种群中#变异操作ifMUTATION_RATE>np.random.rand():mutated_pop=selected_pop+np.random.randn(POPULATION_SIZE, 1)*np.sqrt(np.log(POPULATION_SIZE))*(selected_pop!=pop).astyp e(np.float)#根据变异概率对个体进行变异操作，得到新的个体种群mutated_pop=mutated_pop[mutated_pop!=0]#将二进制种群中值为0的个体去掉，因为这些个体是随机的二进制串，不是解的一部分，不应该参与变异操作selected_pop=mutated_pop[:POPULATION_SIZE]#将新种群中除最后一个以外的部分加入原始种群中（即新的种群被排除了适应度最差的个体）#选择当前最好的个体（用于更新最优解）best_idx=np.argmax(fitness_values)best_solution=selected_pop[best_idx]print(f"Generation{generation}:Bestsolution:{best_solutio n}")```四、使用示例假设要解决一个简单的优化问题：求一个一维函数的最小值。
GATBX遗传算法工具箱函数及实例讲解基本原理：遗传算法是一种典型的启发式算法，属于非数值算法范畴。
它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。
它是采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。
遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群，每一个染色体都对应问题的一个解。
从初始种群出发，采用基于适应度函数的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。
如此模仿生命的进化进行不断演化，直到满足期望的终止条件。
运算流程：Step 1：对遗传算法的运行参数进行赋值。
参数包括种群规模、变量个数、交叉概率、变异概率以及遗传运算的终止进化代数。
Step 2：建立区域描述器。
根据轨道交通与常规公交运营协调模型的求解变量的约束条件，设置变量的取值范围。
Step 3：在Step 2的变量取值范围内，随机产生初始群体，代入适应度函数计算其适应度值。
Step 4：执行比例选择算子进行选择操作。
Step 5：按交叉概率对交叉算子执行交叉操作。
Step 6：按变异概率执行离散变异操作。
Step 7：计算Step 6得到局部最优解中每个个体的适应值，并执行最优个体保存策略。
Step 8：判断是否满足遗传运算的终止进化代数，不满足则返回Step 4，满足则输出运算结果。
运用遗传算法工具箱:运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库。
目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学开发的遗传算法工具箱GATBX、GAOT以及Math Works公司推出的GADS。
实际上，GADS就是大家所看到的Matlab中自带的工具箱。
我在网上看到有问为什么遗传算法函数不能调用的问题，其实，主要就是因为用的工具箱不同。
因为，有些人用的是GATBX带有的函数，但MATLAB自带的遗传算法工具箱是GADS，GADS当然没有GATBX里的函数，因此运行程序时会报错，当你用MATLAB来编写遗传算法代码时，要根据你所安装的工具箱来编写代码。
遗传算法代码遗传算法是一种基于自然选择和遗传学原理的优化算法，用于解决许多复杂的优化问题，如机器学习、图像处理、组合优化等。
以下是一个简单的遗传算法代码示例：1. 初始化种群首先，我们需要创建一组初始个体，称为种群。
每个个体都是由一组基因表示的，这些基因可能是一些数字、布尔值或其他类型的值。
我们可以使用随机数生成器生成这些基因，并将它们组合成一个个体。
2. 适应度函数为了衡量每个个体的表现，我们需要编写一个适应度函数。
该函数将计算每个个体的适应度得分，该得分反映了该个体在解决优化问题方面的能力。
适应度函数将对每个个体进行评分，并将其分配到一个适应度等级。
3. 选择操作选择操作是基于每个个体的适应度得分来选择哪些个体将被选择并用于生成下一代种群。
较高适应度的个体将有更高的概率被选择，而较低适应度的个体将有更低的概率被选择。
这通常是通过轮盘赌选择方法实现的。
4. 交叉操作交叉操作是将两个个体的基因组合并以生成新的个体。
我们可以将两个随机个体中的某些基因进行交换，从而创建新的个体。
这样的交叉操作将增加种群的多样性，使其更有可能找到最优解。
5. 变异操作变异操作是用于引入种群中的随机性的操作。
在变异操作中，我们将随机选择一个个体，并随机更改其中的一个或多个基因。
这将引入新的、未经探索的基因组合，从而增加种群的多样性。
6. 迭代随着种群不断进化，每个个体的适应度得分也将不断提高。
我们将重复执行选择、交叉和变异操作，以生成新的个体，并淘汰旧的个体。
这个不断迭代的过程将继续，直到达到预设的迭代次数或找到最优解为止。
这是一个简单的遗传算法代码示例，它演示了如何使用遗传算法来解决优化问题。
在实际应用中，我们可以进一步对算法进行优化，以获得更好的结果。
详解⽤python实现简单的遗传算法详解⽤python实现简单的遗传算法今天整理之前写的代码，发现在做数模期间写的⽤python实现的遗传算法，感觉还是挺有意思的，就拿出来分享⼀下。
⾸先遗传算法是⼀种优化算法，通过模拟基因的优胜劣汰，进⾏计算（具体的算法思路什么的就不赘述了）。
⼤致过程分为初始化编码、个体评价、选择，交叉，变异。
遗传算法介绍遗传算法是通过模拟⼤⾃然中⽣物进化的历程，来解决问题的。
⼤⾃然中⼀个种群经历过若⼲代的⾃然选择后，剩下的种群必定是适应环境的。
把⼀个问题所有的解看做⼀个种群，经历过若⼲次的⾃然选择以后，剩下的解中是有问题的最优解的。
当然，只能说有最优解的概率很⼤。
这⾥，我们⽤遗传算法求⼀个函数的最⼤值。
f(x) = 10 * sin( 5x ) 7 * cos( 4x ), 0 <= x <= 101、将⾃变量x进⾏编码取基因⽚段的长度为10, 则10位⼆进制位可以表⽰的范围是0到1023。
基因与⾃变量转变的公式是x = b2d(individual) * 10 / 1023。
构造初始的种群pop。
每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]2、计算⽬标函数值根据⾃变量与基因的转化关系式，求出每个个体的基因对应的⾃变量，然后将⾃变量代⼊函数f（x），求出每个个体的⽬标函数值。
3、适应度函数适应度函数是⽤来评估个体适应环境的能⼒，是进⾏⾃然选择的依据。
本题的适应度函数直接将⽬标函数值中的负值变成0. 因为我们求的是最⼤值，所以要使⽬标函数值是负数的个体不适应环境，使其繁殖后代的能⼒为0.适应度函数的作⽤将在⾃然选择中体现。
4、⾃然选择⾃然选择的思想不再赘述，操作使⽤轮盘赌算法。
其具体步骤：假设种群中共5个个体，适应度函数计算出来的个体适应性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ，如果将fitvalue画到圆盘上，值的⼤⼩表⽰在圆盘上的⾯积。
遗传算法matlab程序代码
遗传算法（GA）是一种用于求解优化问题的算法，其主要思想是模拟
生物进化过程中的“选择、交叉、变异”操作，通过模拟这些操作，来寻
找最优解。
Matlab自带了GA算法工具箱，可以直接调用来实现遗传算法。
以下是遗传算法Matlab程序代码示例：
1.初始化
首先定义GA需要优化的目标函数f，以及GA算法的相关参数，如种
群大小、迭代次数、交叉概率、变异概率等，如下所示：
options = gaoptimset('PopulationSize',10,...
'Generations',50,...
2.运行遗传算法
运行GA算法时，需要调用MATLAB自带的ga函数，将目标函数、问
题的维度、上下界、约束条件和算法相关参数作为输入参数。
其中，上下
界和约束条件用于限制空间，防止到无效解。
代码如下：
[某,fval,reason,output,population] = ga(f,2,[],[],[],[],[-10,-10],[10,10],[],options);
3.结果分析
最后，将结果可视化并输出，可以使用Matlab的plot函数绘制出目
标函数的值随迭代次数的变化，如下所示：
plot(output.generations,output.bestf)
某label('Generation')
ylabel('Best function value')
总之，Matlab提供了方便易用的GA算法工具箱，开发者只需要根据具体问题定义好目标函数和相关参数，就能够在短时间内快速实现遗传算法。
1、遗传算法介绍遗传算法，模拟达尔文进化论的自然选择和遗产学机理的生物进化构成的计算模型，一种不断选择优良个体的算法。
谈到遗传，想想自然界动物遗传是怎么来的，自然主要过程包括染色体的选择，交叉，变异（不明白这个的可以去看看生物学），这些操作后，保证了以后的个基本上是最优的，那么以后再继续这样下去，就可以一直最优了。
2、解决的问题先说说自己要解决的问题吧，遗传算法很有名，自然能解决的问题很多了，在原理上不变的情况下，只要改变模型的应用环境和形式，基本上都可以。
但是遗传算法主要还是解决优化类问题，尤其是那种不能直接解出来的很复杂的问题，而实际情况通常也是这样的。
本部分主要为了了解遗传算法的应用，选择一个复杂的二维函数来进行遗传算法优化，函数显示为y=10*sin(5*x)+7*abs(x-5)+10,这个函数图像为：怎么样，还是有一点复杂的吧，当然你还可以任意假设和编写，只要符合就可以。
那么现在问你要你一下求出最大值你能求出来吗？这类问题如果用遗传算法或者其他优化方法就很简单了，为什么呢？说白了，其实就是计算机太笨了，同时计算速度又超快，举个例子吧，我把x等分成100万份，再一下子都带值进去算，求出对应的100万个y的值，再比较他们的大小，找到最大值不就可以了吗，很笨吧，人算是不可能的，但是计算机可以。
而遗传算法也是很笨的一个个搜索，只不过加了一点什么了，就是人为的给它算的方向和策略，让它有目的的算，这也就是算法了。
3、如何开始？我们知道一个种群中可能只有一个个体吗？不可能吧，肯定很多才对，这样相互结合的机会才多，产生的后代才会多种多样，才会有更好的优良基因，有利于种群的发展。
那么算法也是如此，当然个体多少是个问题，一般来说20-100之间我觉得差不多了。
那么个体究竟是什么呢？在我们这个问题中自然就是x值了。
其他情况下，个体就是所求问题的变量，这里我们假设个体数选100个，也就是开始选100个不同的x值，不明白的话就假设是100个猴子吧。
遗传算法简述及代码详解声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。
遗传算法基本内容遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。
遗传学与遗传算法中的基础术语比较染色体：又可以叫做基因型个体(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位（串的长度根据解的精度设 定，串长度越长解得精度越高）。
人工智能遗传算法及python代码实现人工智能遗传算法是一种基于生物遗传进化理论的启发式算法，常用于求解复杂的优化问题。
它的基本思想是通过自然选择和基因交叉等机制，在种群中不断进化出适应性更强的个体，最终找到问题的最优解。
遗传算法通常由以下几个步骤组成：1. 初始化种群：从问题空间中随机生成一组解作为初始种群。
2. 评价适应度：利用一个适应度函数来评价每个解的适应性，通常是优化问题的目标函数，如最小化代价、最大化收益等。
3. 选择操作：从种群中选择一些具有较高适应度的个体用于产生新的种群。
选择操作通常采用轮盘赌选择方法或精英选择方法。
4. 交叉操作：将两个个体的染色体进行交叉、重组，生成新的子代个体。
5. 变异操作：对新产生的子代个体随机变异一些基因，以增加种群的多样性。
6. 生成新种群：用选择、交叉和变异操作产生新的种群，并进行适应度评价。
7. 终止条件：如果达到终止条件，算法停止，否则返回步骤3。
遗传算法的优点是可以适应各种优化问题，并且求解精度较高。
但由于其需要进行大量的随机操作，因此效率相对较低，也较容易陷入局部最优解。
在实际应用中，遗传算法常与其他算法结合使用，以求得更好的结果。
以下是使用Python实现基本遗传算法的示例代码：import randomimport math# 定义适应度函数，用于评价每个个体的适应程度def fitness_func(x):return math.cos(20 * x) + math.sin(3 * x)# 执行遗传算法def genetic_algorithm(pop_size, chrom_len, pcross, pmutate, generations):# 初始化种群population = [[random.randint(0, 1) for j in range(chrom_len)] for i in range(pop_size)]# 迭代指定代数for gen in range(generations):# 评价种群中每个个体的适应度fits = [fitness_func(sum(population[i]) / (chrom_len * 1.0)) for i in range(pop_size)]# 选择操作：轮盘赌选择roulette_wheel = []for i in range(pop_size):fitness = fits[i]roulette_wheel += [i] * int(fitness * 100)parents = []for i in range(pop_size):selected = random.choice(roulette_wheel)parents.append(population[selected])# 交叉操作：单点交叉for i in range(0, pop_size, 2):if random.uniform(0, 1) < pcross:pivot = random.randint(1, chrom_len - 1)parents[i][pivot:], parents[i+1][pivot:] = parents[i+1][pivot:], parents[i][pivot:]# 变异操作：随机翻转一个基因for i in range(pop_size):for j in range(chrom_len):if random.uniform(0, 1) < pmutate:parents[i][j] = 1 - parents[i][j]# 生成新种群population = parents# 返回种群中适应度最高的个体的解fits = [fitness_func(sum(population[i]) / (chrom_len * 1.0)) for i in range(pop_size)]best = fits.index(max(fits))return sum(population[best]) / (chrom_len * 1.0)# 测试遗传算法print("Result: ", genetic_algorithm(pop_size=100, chrom_len=10, pcross=0.9, pmutate=0.1, generations=100))上述代码实现了遗传算法，以优化余弦函数和正弦函数的和在某个区间内的最大值。
遗传算法( 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背包问题的一个“近似最优解”。
编码：需要将问题的解编码成字符串的形式才能使用遗传算法。
最简单的一种编码方式是二进制编码，即将问题的解编码成二进制位数组的形式。
例如，问题的解是整数，那么可以将其编码成二进制位数组的形式。
将0-1字符串作为0-1背包问题的解就属于二进制编码。
遗传算法有3个最基本的操作：选择，交叉，变异。
选择：选择一些染色体来产生下一代。
一种常用的选择策略是“比例选择”，也就是个体被选中的概率与其适应度函数值成正比。
假设群体的个体总数是M，那么那么一个体Xi被选中的概率为f(Xi)/( f(X1) + f(X2) + …….. + f(Xn) ) 。
比例选择实现算法就是所谓的“轮盘赌算法”( Roulette Wheel Selection ) ，轮盘赌算法的一个简单的实现如下：轮盘赌算法/** 按设定的概率，随机选中一个个体* P[i]表示第i个个体被选中的概率*/int RWS(){m =0;r =Random(0,1); //r为0至1的随机数for(i=1;i<=N; i++){/* 产生的随机数在m~m+P[i]间则认为选中了i* 因此i被选中的概率是P[i]*/m = m + P[i];if(r<=m) return i;}}交叉(Crossover)：2条染色体交换部分基因，来构造下一代的2条新的染色体。
例如：交叉前：00000|011100000000|1000011100|000001111110|00101交叉后：00000|000001111110|1000011100|011100000000|00101染色体交叉是以一定的概率发生的，这个概率记为Pc 。
变异(Mutation)：在繁殖过程，新产生的染色体中的基因会以一定的概率出错，称为变异。
变异发生的概率记为Pm 。
例如：变异前：000001110000000010000变异后：000001110000100010000适应度函数 ( Fitness Function )：用于评价某个染色体的适应度，用f(x)表示。
有时需要区分染色体的适应度函数与问题的目标函数。
例如：0-1背包问题的目标函数是所取得物品价值，但将物品价值作为染色体的适应度函数可能并不一定适合。
适应度函数与目标函数是正相关的，可对目标函数作一些变形来得到适应度函数。
三.基本遗传算法的伪代码基本遗传算法伪代码/** Pc：交叉发生的概率* Pm：变异发生的概率* M：种群规模* G：终止进化的代数* Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程*/初始化Pm，Pc，M，G，Tf等参数。
随机产生第一代种群Popdo{计算种群Pop中每一个体的适应度F(i)。
初始化空种群newPopdo{根据适应度以比例选择算法从种群Pop中选出2个个体if ( random ( 0 , 1 ) < Pc ){对2个个体按交叉概率Pc执行交叉操作}if ( random ( 0 , 1 ) < Pm ){对2个个体按变异概率Pm执行变异操作}将2个新个体加入种群newPop中} until ( M个子代被创建)用newPop取代Pop}until ( 任何染色体得分超过Tf，或繁殖代数超过G )四.基本遗传算法优化下面的方法可优化遗传算法的性能。
精英主义(Elitist Strategy)选择：是基本遗传算法的一种优化。
为了防止进化过程中产生的最优解被交叉和变异所破坏，可以将每一代中的最优解原封不动的复制到下一代中。
插入操作：可在3个基本操作的基础上增加一个插入操作。
插入操作将染色体中的某个随机的片段移位到另一个随机的位置。
五. 使用AForge.Genetic解决TSP问题是一个C#实现的面向人工智能、计算机视觉等领域的开源架构。
中包含有一个遗传算法的类库。
主页：/代码下载：/p/aforge/介绍一下AForge的遗传算法用法吧。
AForge.Genetic的类结构如下：图1. AForge.Genetic的类图下面用AForge.Genetic写个解决TSP问题的最简单实例。
测试数据集采用网上流传的中国31个省会城市的坐标:13042312363913154177224437121399348815353326155632381229419610044312790438657030071970256217562788149123811676133269537151678391821794061237037802212367625784029283842632931342919083507236733942643343932012935324031403550254523572778282623702975操作过程：(1) 下载类库，网址：/p/aforge/downloads/list(2) 创建C#空项目GenticTSP。
然后在AForge目录下找到AForge.dll和AForge.Genetic.dll，将其拷贝到TestTSP项目的bin/Debug目录下。
再通过“Add Reference...”将这两个DLL添加到工程。
(3) 将31个城市坐标数据保存为bin/Debug/Data.txt 。
(4) 添加TSPFitnessFunction.cs，加入如下代码：TSPFitnessFunction类using System;using AForge.Genetic;namespace GenticTSP{///<summary>/// Fitness function for TSP task (Travaling Salasman Problem)///</summary>publicclass TSPFitnessFunction : IFitnessFunction{// mapprivateint[,] map =null;// Constructorpublic TSPFitnessFunction(int[,] map){this.map = map;}///<summary>/// Evaluate chromosome - calculates its fitness value ///</summary>publicdouble Evaluate(IChromosome chromosome) {return1/ (PathLength(chromosome) +1);}///<summary>/// Translate genotype to phenotype///</summary>publicobject Translate(IChromosome chromosome) {return chromosome.ToString();}///<summary>/// Calculate path length represented by the specified chromosome ///</summary>publicdouble PathLength(IChromosome chromosome){// salesman pathushort[] path = ((PermutationChromosome)chromosome).Value;// check path sizeif (path.Length != map.GetLength(0)){thrownew ArgumentException("Invalid path specified - not all cities are visited");}// path lengthint prev = path[0];int curr = path[path.Length -1];// calculate distance between the last and the first citydouble dx = map[curr, 0] - map[prev, 0];double dy = map[curr, 1] - map[prev, 1];double pathLength = Math.Sqrt(dx * dx + dy * dy);// calculate the path length from the first city to the last for (int i =1, n = path.Length; i < n; i++){// get current citycurr = path[i];// calculate distancedx = map[curr, 0] - map[prev, 0];dy = map[curr, 1] - map[prev, 1];pathLength += Math.Sqrt(dx * dx + dy * dy);// put current city as previousprev = curr;}return pathLength;}}}(5) 添加GenticTSP.cs，加入如下代码：GenticTSP类using System;using System.Collections.Generic; using System.Linq;using System.Text;using System.IO;using AForge;using AForge.Genetic;namespace GenticTSP{class GenticTSP{staticvoid Main(){StreamReader reader =new StreamReader("Data.txt");int citiesCount =31; //城市数int[,] map =newint[citiesCount, 2];for (int i =0; i < citiesCount; i++){string value = reader.ReadLine();string[] temp = value.Split('');map[i, 0] =int.Parse(temp[0]); //读取城市坐标map[i, 1] =int.Parse(temp[1]);}// create fitness functionTSPFitnessFunction fitnessFunction =new TSPFitnessFunction(map); int populationSize = 1000; //种群最大规模/** 0：EliteSelection算法* 1：RankSelection算法* 其他：RouletteWheelSelection 算法* */int selectionMethod =0;// create populationPopulation population =new Population(populationSize,new PermutationChromosome(citiesCount), fitnessFunction,(selectionMethod ==0) ? (ISelectionMethod)new EliteSelection() : (selectionMethod ==1) ? (ISelectionMethod)new RankSelection() : (ISelectionMethod)new RouletteWheelSelection());// iterationsint iter =1;int iterations =5000; //迭代最大周期// loopwhile (iter < iterations){// run one epoch of genetic algorithmpopulation.RunEpoch();// increase current iterationiter++;}System.Console.WriteLine("遍历路径是：{0}", ((PermutationChromosome)population.BestChromosome).ToString()); System.Console.WriteLine("总路程是：{0}",fitnessFunction.PathLength(population.BestChromosome)); System.Console.Read();}}}。
