水果梦是我的梦
X10+ex=100*/
#include #include #include #define T1 10 #define T2 7 #define P1 0.75//交配率 #define P2 0.03//变异率 #define D_num 10//迭代次数 struct Grad_fx//记录测试的成绩就是适应度的 { }; Grad_fx Gfx[T1];//记录一组数据的适应度的 int J_line[T1];//记录随机交配序列 int Random(int n ) //产生随机数，在小于等于0并小于n { } void Statr(int (*F )[T2])//初始化父类的值， { } void Output(int (*F )[T2])//输出整个种群 { } //int x=0;// for (int i=0;i float ERtoTen(int *a ) //二进制变为10进制 { } float F_x(int *a ) //求目标取函数值 { } void fintness(int (*F )[T2])//建立适应度并且排序 { int i,j; Grad_fx tempG; for (i=0;i } /*for(i=0;i bool J_lineexist(int n , int num ) //为了生成一个随机无重复的交配序列判断交配序列里是否已经有已存在的树，就是为了不产生重复的随机数 { } void J_linerand()//产生一个交配序列 { } void Mat_make(int *F , int *M ) //两个个体交配 { } int n=Random(T2),i=0,temp; for (i=n;i void Mating(int (*F )[T2])//种群交配 { } void Change(int (*F )[T2])//变异 { } int main() { int Father[T1][T2];//定义一个父代的种群 int i=D_num; float x; Statr(Father); printf(" 原始数据：;\n"); Output(Father); fintness(Father);//适应度计算 while (i--&&Gfx[0].grade!=0.0) { int n=T1*T2*P2,r1,r2; //n为变异个体 for (int i=0;i } } printf(" 这是第%d次交配\n", D_num-i); Mating(Father);//进行交配 Change(Father);//变异 Output(Father); fintness(Father);//适应度计算 x=ERtoTen(Father[Gfx[0].num]); x=x*0.01+1; printf(" 这是最后结果：X 的值%.2f,适应度为%.2f\n",x,Gfx[0].grade); return 0; 实验六 遗传算法求解 TSP 问题 一、实验目的 熟悉和掌握遗传算法的原理、 流程和编码策略, 并利用遗传求解函数优化 问题,理解求解 TSP 问题的流程并测试主要参数对结果的影响。 二、实验内容 1、参考实验系统给出的遗传算法核心代码,用遗传算法求解 TSP 的优化问 题,分析遗传算法求解不同规模 TSP 问题的算法性能。 2、对于同一个 TSP 问题,分析种群规模、交叉概率和变异概率对算法结果 的影响。 3、增加 1种变异策略和 1种个体选择概率分配策略,比较求解同一 TSP 问 题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。 三、遗传算法求解 TSP 问题的流程图 四、遗传算法求解不同规模的 TSP 问题的算法性能 (1) 遗传算法执行方式说明: 适应度值计算方法:当前路线的路径长度 ●个体选择概率分配方法:适应度比例方法 ●选择个体方法:轮盘赌选择 ●交叉类型:PMX 交叉 ●变异类型 : 两点互换变异 (2)实验模拟结果: 图 1-1 (3)分析 由图 1-1可知,遗传算法执行时间随着 TSP 问题规模的增大而增大,并且大 致为线性增长。 五、不同参数下的计算结果对比 (1)种群规模对算法结果的影响 实验次数:10 最大迭代步数 :100 交叉概率:0.85 变异概率:0.15 如表 1-1或 3-1-0-9-2-4-8-5-7-6,注意到这是一圈,顺时针或者逆时针都可以。当种群规模为 10, 20时,并没有找到最优解。 (2)交叉概率对算法结果的影响 实验次数:15 种群规模:25 最大迭代步数 :100 变异概率:0.15 实验结果: 在该情况下,交叉概率过低将使搜索陷入迟钝状态,得不到最优解。 (3)变异概率对算法结果的影响 实验次数:10 种群规模:25 最大迭代步数 :100 交叉概率:0.85 实验结果: 又表 1-3可知,当变异概率过大或过低都将导致无法得到最优解。 注:(2) (3)的实验数据与(1)的实验数据不同,详见附录。 六、不同变异策略和个体选择概率分配策略对算法结果的影响 (1) 两点互换变异与插入变异的比较: ●试验次数(CASNUM ) :10 ●城市数 (POINTCNT):10 ●种群规模 (POPSIZE):100 ●最大迭代步数 (GENERATIONS):100 ●交叉概率 (PC):0.85 ●变异概率 (PM):0.15 ●选择个体方法:轮盘赌选择 ●交叉类型:PMX 交叉 ●个体选择概率分配方法:适应度比例方法 a. 变异类型 : 两点互换变异 b. 变异类型 : 插入变异 分析: 两点互换变异 20次模拟中, 4次得到非最优解; 而插入变异只有 2次; 插入 变异的最好适应度平均值比两点互换变异小 0.14755,最差适应度平均值和总的 适应度平均值都比两点互换下,并且在 Release 下,运行时间前者比后者快 218.3ms 。可见在该条件下(交叉概率,变异概率,种群规模等) ,插入变异比两 点互换变异的算法效果要好。 (2)个体选择分配策略 ●试验次数(CASNUM ) :10 ●城市数 (POINTCNT):10 ●种群规模 (POPSIZE):100 ●最大迭代步数 (GENERATIONS):100 ●交叉概率 (PC):0.85 ●变异概率 (PM):0.15 ●选择个体方法:轮盘赌选择 ●交叉类型:PMX 交叉 ●变异类型 : 两点互换变异 a. 个体选择概率分配方法:适应度比例方法 同表 1-4 b. 个体选择概率分配方法:非线性排序方式 分析: 个体选择概率分配方式采用非线性排序方式时,程序运行结果非常糟糕。 20次模拟中竟然有 11次无法找到最优解。运行时间也很慢。可见在该条件下(交 叉概率,变异概率,种群规模等) ,个体选择概率分配方式不宜采用非线性排序 方式,简单的适应度比例方法的效果明显更好。 七、实验心得与体会 通过本实验,更加深入体会了参数设置对算法结果的影响。同一个算法,参 数值不同,获得的结果可能会完全不同。 遗传算法是一种智能优化算法,它能较好的近似求解 TSP 问题,在问题规模 比较大的时候, 遗传算法的优势就明显体现出来, 当然不能完全保证能得到最优 解。 遗传算法的实现有些关键点,一是串的编码方式,本质就是问题编码,串长 度及编码形式对算法收敛影响极大; 二是适应函数的确定, 这是选择的基础, 应 具体问题具体分析, 没有大一统的方法; 三是自身参数的设定, 其中重要的是种 群规模, 最大迭代次数, 交叉概率和变异概率, 通过实验我们可以看到种群规模、 最大迭代次数对问题求解的精度有很大影响, 交叉概率和变异概率的设定对问题 的收敛速度和求解精度也都有极大的影响, 但在不同条件下, 这种影响表现的程 度有很大的不同。具体参数的设定应根据具体的领域问题。 八:附录: 变异概率与交叉概率对算法的影响: 智能优化计算及应用课考核论文 第 1 页 遗传算法的TSP (旅行商问题)的求解 学生姓名：XXX 指导老师：XXX 摘 要 TSP 问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文 针对解决TSP 问题,在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交 叉和变异算子进行了算法设计，最后在MATLAB软件上进行编程实现。最后探讨了遗传算 法解决旅行商问题自身具备的特点[1]。 关键词：遗传算法；TSP问题；MATLAB软件 智能优化计算及应用课考核论文 第 2 页 Author : Zong Man-yi Tutor : Qiao Li-hong Abstract TSP( Traveling Salesman Problem) is a typical NP complete problem ,genetic algorithm is the perfect method for solving NP complete problem. This paper use genetic algorithm in the MATLAB software to solve the a typical TSP problem . It probes into the realization of genetic operator program through TSP solving by genetic algorithm , design the each function of each genetic operator(select, intercross, mutate). Finally ,We programm in Matlab language and discuss the characteristic of genetic algorithm in solving TSP : genetic algorithm; TSP Matlab ; 智能优化计算及应用课考核论文 第 3 页 引言 .................................................................... 4 1 GA概述 .......................................................... 4 2 旅行商问题(TSP) .................................................. 4 3 用遗传算法解决旅行商问题 ......................................... 5 4 论文的主要构成 .................................................... 5 遗传算法的设计 .......................................................... 6 1问题分析 ........................................................... 6 2 总体设计 .......................................................... 7 3 详细设计 .......................................................... 8 3.1 编码与随机和初始群体生成 .............................................................................................................................. 8 3.2 城市位置及距离矩阵和适应度函数 .................................................................................................................. 8 3.4 选择 ................................................................................................................................................................... 9 3.4 交叉 ................................................................................................................................................................... 9 3.5 变异 ................................................................................................................................................................. 10 3.6 群体的跟新和终止条件 ................................................................................................................................... 10 MATLAB编程验证 ........................................................ 11 1MATLAB计算 ........................................................ 11 2算法分析优化 ...................................................... 13 结论 ................................................................... 15 参考文献 ............................................................... 16 智能优化计算及应用课考核论文 第 4 页 引言 1 概述 遗传算法(Genetic Algorithm , GA ) 是由美国J. Holland 教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论, 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略 和群体中个体之间的信息交换, 搜索不以梯度信息为基础。它尤其适用于处理传统搜索 方法难于解决的复杂和非线性问题, 可广泛应用于组合优化、机器学习、自适应控制、 规划设计和人工生命等领域。作为一种全局优化搜索算法, 遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点, 使其成为21 世纪智能计算核心技术之一。进入80 年代, 遗传算法迎来了兴盛发展时期, 无论是理论研究还是应用研究都成 了十分热门的话题[2]。 2 旅行商问题(TSP) 一个有名的组合优化问题就是旅行商问题(Travelling Salesman Problem , TSP)。TSP问题是典型的、易于描述却难以处理的组合优化问题。由于遗传算法方法的本质是 处理复杂问题的一种鲁棒性强的启发性随机搜索算法, 故而利用遗传算法求解这类问 题是有效的。 假设平面上有n个点代表n个城市的位置, 寻找一条最短的闭合路径, 使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形, 或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达 (n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之 间都以欧氏距离直接相连。也就是说, 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。是一个典型的优化组合问题 [3]。 智能优化计算及应用课考核论文 第 5 页 3 用遗传算法解决旅行商问题 目前针对TSP问题有许多种解法，较为常用的算法有神经网络法、列表寻优法、二 叉树描述法、模拟退火法和遗传算法等等。遗传算法是近几年发展起来的一种崭新的全 局优化算法，它借用了生物遗传学的观点，通过选择、遗传、变异和免疫等作用机制， 使每个个体的适应性提高。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。提出的TSP问题包括31个城市的编号和各自的位置。本文针对这 个TSP问题进行了遗传算法的编程和求解。 4 论文的主要构成 本论文在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和 变异、免疫等算子进行了算法设计，最后在MATLAB软件上进行编程实现。 智能优化计算及应用课考核论文 第 6 页 1问题分析 TSP 问题的描述十分简单, 简言之, 就是寻找一条最短的遍历n 个城市的最短路径, 或者说搜索自然数子集X = { 1 ,2 , ?, n} ( X 的元素表示对n 个城市的编号) 的一个排列 π( X) = { V1 , V2 , ?, Vn} , 使len = ? d ( Vi , Vi+1) + d ( V1 , Vn)取最小值, 式中的d ( Vi , Vi+1) 表示城市Vi 到城市Vi + 1的距离. （图 1）[3] 本实例中设定了我国31个省会城市，当一个旅行商彼遍历了所有城市后回到出发城 市，求其最短路径的走法。一个最容易想到的方法是利用排列组合的方法把所有的路径 都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的 个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的， 甚至是不可能完成的，31个城市所有路径个数是30！个。由于其全局搜索的特性，遗传 算法在解决TSP问题中有着其他算法所没有的优势。本文针对这个TSP问题进行了遗传算法的编程和求解。 智能优化计算及应用课考核论文 第 7 页 2 总体设计 随机产生初始群，计 算各个个体的适配值标准的遗传算法包括群体的初始化，选 择，交叉，变异操作。其主要步骤可描述如Y算法是否达到收敛输出 N下[1]： （1）随机产生一组初始个体构成的初始种依适配值大小选择 群，并评价每一个个体的适配值。 Pc>=rand?（2）判断算法的收敛准则是否满足。若满 Y足输出搜索结果；否则执行以下步骤。 （3）根据适配值大小以一定方式执行选择交叉N操作。 （4）按交叉概率Pc执行交叉操作. Pm>=rand? N（5）按变异概率Pm执行变异操作。 Y （6）返回步骤（2）。 变异 （图 2）标准遗传算法的流程图 本TSP问题的遗传算法总体设计 跟新群体N 最优解加入下次迭代1 N2N2选择交叉变异 产生随机路径产生初始群体N随机路径使群体数目不变N-N2-1 智能优化计算及应用课考核论文 第 8 页 （图3）总体设计 说明：（1）本算法的判断结束准则是固定指定了迭代的次数当算法达到迭代次数时， 算法结束，输出当前的最优解 （2）在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入 跟新的群体，保证新的迭代循环中TSP解越来越好（不会变差）。 （3）在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变， 再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。 3 3.1 编码与随机和初始群体生成 给所有城市编码，以城市的遍历次序作为遗传算法的编码。在MATLAB中使用 randperm(N)产生一个1×N 的矩阵（N为所有城市的个数，本例中为31）为一个随机路径。利用n×N矩阵存储n个随机群体产生初始群体。 3.2 城市位置及距离矩阵和适应度函数 城市的位置为编译前指定，也可以使用随机生成的坐标参数。距离矩阵使用一个N×N矩阵D存储，D（i，j）代表城市 i和城市j之间的距离。 D（i，j）=sqrt(（Xi-Xj）.^2+(Yi-Yj).^2) 在该问题的求解中，用距离的总和来衡量适应度，距离的总和越大，适应度越小，进 而探讨求解结果是否最优。 每个个体（每条路径距离）总合计算公式为： len=D(1,N); for i=1:(N-1) len=len+D(i,,i+)); end len纪录总路径格式n×1 len(i)代表第i个个体（路径）距离总合。 智能优化计算及应用课考核论文 第 9 页 3.4 选择 选择操作是为了避免有效基因的损失，使高性能的个体得以更大的几率生存，从而得 到全局收敛性和计算效率。 本例中使用的适配值函数为 fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.0001))).^m; % maxlen ，minlen为最大和最短路径 利用fitness〉rand选择个体，将个体，将较小路径(适应度较大)个体选择下来。但这种算法的群体的个体数目变小并且较优的个体个数较少， 可能收敛的数目变慢，在算法调试的过程中证明了这一点[4]。 3.4 交叉 交叉操作用于组合出新的个体，再借空间中进行有效的搜索，同时降低有效模式的破 坏概率[1]。 本实例中交叉采用部分匹配交叉策略,其基本实现A: 9 8 ‖4 5 6 7 1 ‖3 2 0的步骤是： B: 8 7 ‖1 4 0 3 2 ‖9 6 5步骤1： 随机选取两个交叉点 将匹配段互换 步骤2： 将两交叉点中间的基因段互换 A: 8 7‖4 5 6 7 1 ‖9 6 5步骤3： 将互换的基因段以外的部分中与互换后基 B: 9 8‖1 4 0 3 2 ‖3 2 0对A进行路径冲突互换因段中元素冲突的用另一父代的相应位置代替，直 A: 8 3‖4 5 6 7 1 ‖9 0 4 到没有冲突。 B: 9 8‖1 4 0 3 2 ‖3 2 0 A: 8 3‖4 5 6 7 1 ‖9 0 1 本例中路径实例如图交叉点为2，7，交换匹配段后B: 9 8‖1 4 0 3 2 ‖3 2 0 A中冲突的有7 、6、5，在B的匹配段中找出与A匹配A: 8 3‖4 5 6 7 1 ‖9 0 2段中对应位置的值7-3，6-0，5-4，继续检测冲突直B: 9 8‖1 4 0 3 2 ‖3 2 0到没有冲突。对B 做同样操作，得到最后结果。 同理对B进行冲突呼唤 （图 4） A: 8 3‖4 5 6 7 1 ‖9 0 2 B: 9 8‖1 4 0 3 2 ‖7 5 6 智能优化计算及应用课考核论文 第 10 页 3.5 变异 变异操作通过随机改变个体中某些个体的某些基因而产生新个体，有助于增加种群的 多样性，避免早熟收敛（非全局最优）。 本例中变异操作使用互换操作算子（SWAP），即随机交换染色体中两个不同基因编码 的位置，SWAP相对于INV（逆序操作）和INS（插入操作）更有利于算法的大范围搜索。 对于一个31路径的染色体的变异操作，依变异概率确定是否变异，随机选择路径上 的两个城市进行交换。例如 变异交换位置为2和8 8 3 4 5 6 7 1 9 0 28 9 4 5 6 7 1 3 0 2 3.6 群体的跟新和终止条件 为保证计算随迭代次数的增加，最优解越来越好，本例种每次变异后将每次的上次迭 代最优解加入群体，防止因交叉或变异而是最优解失去，出现退化现象。 为保持群体数目不变，变异后产生随机解加入群体（本算法群体数目仔选择中可能发 生减少）。 终止条件最常用的有事先给定一个最大进化步数，或者是判断最优化值是否连续若干 步没有明显变化两种。本实例中只选择了第一种方法[6]。 智能优化计算及应用课考核论文 第 11 页 1MATLAB计算 1初始值（图 5） 种群个数n=100;迭代次数C=1000; 交叉概率Pc=0.9;变异概率Pm=0.2; 初始种群中的一个随机值: R =[ 29 13 15 16 4 17 22 12 2 18 31 5 25 26 11 6 28 3 14 30 20 1 9 21 10 24 8 7 23 19 27] Rlength = 4.4308e+004 迭代1000次后路径如图Rlength = 3.0902e+004发现算法收敛很慢 2初始值（图 6） 种群个数n=100;迭代次数C=2000; 交叉概率Pc=0.9;变异概率Pm=0.2; 初始种群中的一个随机值: Rlength = 4.3506e+004 迭代2500次后路径如图 Rlength =1.9497e+004趋向于收敛 3初始值（图 7） 种群个数n=100;迭代次数C=2500; 交叉概率Pc=0.9;变异概率Pm=0.2; 初始种群中的一个随机值: Rlength = 4.3506e+004 迭代2500次后路径如图Rlength = Rlength = 1.8754e+004 趋向于收敛 智能优化计算及应用课考核论文 第 12 页 （图 8） 4初始值： 种群个数n=100;迭代次数C=3000; 交叉概率Pc=0.9;变异概率Pm=0.2; Rlength = 4.4721e+004 迭代3000次路径如图Rlength = 1.6957e+004 次序为R =29 13 7 10 9 8 3 18 22 21 26 28 27 31 1 15 14 12 11 23 6 5 2 4 16 17 19 24 20 25 30 路径较小可能已经为最优解 5初始值：（图9） 种群个数n=100;迭代次数C=3500; 交叉概率Pc=0.9;变异概率Pm=0.2; Rlength = 4.4721e+004 迭代3500次路径如图Rlength = 1.7093e+004 次序为R =25 20 21 22 18 3 17 16 5 6 7 2 4 8 9 10 13 12 11 23 19 24 29 14 15 1 31 30 27 28 26 路径较小可能已经为最优解 城市 坐标矩阵为a=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; 3238 1229;4196 1044;4312 790;4386 570;3007 970;2562 1756; 2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376; 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826; 2370 2975]; 可以认为该算法在迭代3000左右时，已经发生了收敛，对于本例给出一个解为R =29 13 7 10 9 8 3 18 22 21 26 28 27 31 1 15 14 12 11 23 6 5 2 4 16 17 19 24 20 25 30 智能优化计算及应用课考核论文 第 13 页 2算法分析优化 1. 选择操作。本例中算法收敛较慢，改进选择操作如下，选定K个最大适应 度的个体，用来代替适应度最小的K个个体，保持群体的数目不变。此方法可以使 群体的平均适应度大幅提高，可能使其收敛速度加快。 试验中使用该种选择操作，发现速度有加快迹象 6初始值：（图 10） 种群个数n=100;迭代次数 C=1000; 2. 交叉概率Pc=0.9;变异概率 Pm=0.2; Rlength= 1.9575e+004 与图6相比收敛速度又加快迹 象 （本次迭代次数为1000次） 7初始值：（图 11） 种群个数n=100;迭代次数 C=4000; 交叉概率Pc=0.9;变异概率 Pm=0.2; Rlength= 1.8588e+004 与图8，9相比收敛结果基本正 确。证明优化方式正确。 3. 每次交叉或变异操作以后，检验子代的适应度。如果子代发生退化，取消操 作，用父代代替子代。这种方法可能带来的问题有?虽然收敛迭代次数可能减少， 但每次运算的计算量增加，增加了运算的时间?不利于种群的多样化，可能收敛解 非最优解。解决方法根据某一较小概率0.1-0.2有选择的进行检验和替换。 本例中算法已经进行了设计 4. 免疫遗传算法。免疫遗传算法在变异以后加入免疫算子，可以大幅减少迭代 次数。针对TSP问题，免疫遗传算子设计为先用一个n×2的矩阵存储每一个顶点（城市）与其相应的最近城市的编号。如阿a[i,1]的最近城市a[i,2]。根据TSP问题而言， 智能优化计算及应用课考核论文 第 14 页 在最终的解决方案中，即在最佳路径中必然包括（或载很大程度上包括）了相邻城 市间距离的最短路径。将城市a[i,2]移到a[i,1]之后，进行免疫检测，如果个体发生退化，取消免疫。免疫遗传算法可以大幅加快迭代的收敛速度减少迭代次数。本实例 中没有进行免疫设计[4]。 5. 终止条件。终止条件最常用的有事先给定一个最大进化步数，或者是判断最 优化值是否连续若干步没有明显变化两种。本实例中只选择了第一种方法。可以设 定一百次记录一次最优解，当连续三次的解不变（或相差不大）输出迭代结果。本 实例中没有设计。 智能优化计算及应用课考核论文 第 15 页 结论 论文用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程，证明了遗传算 法在求解TSP问题时，具有可行性，MATLAB在进行算法优化编程时具有一定的优势。遗传算法在设计过程中要照顾好两个原则?子代要具有父代优良的基因信息即继承性 ?子代要保持群体的多样性，即变异。虽然这两个原则在设计过程中经常会出现冲突， 我们必须统筹的把握。既要实现算法的快速运算，又要实现解的最优。本论文认为对标 准遗传算法有进行改经的必要，以提高其求解能力。 智能优化计算及应用课考核论文 第 16 页 参考文献 [1] 王凌著，智能优化算法及其应用，清华大学出版社，2001 [2]陈国良，王煦法，庄镇圈等.遗传算法及其应用，北京：人民邮电出版社，1996 [3] 谢胜利等,基于遗传算法的旅游商问题求解,温州师范学院学报;2002.1.23 [4]阮怀忠,张建中,基于改进遗传算法的TSP 问题求解, 安徽建筑工业学院学报 2003.11 [5]刘克胜, 邵华, 曹先彬等. 基于免疫算法的TSP 问题求解[A] . 1999 中国智能自动化学术会议论文 [6] 高经纬，张煦等，求解TSP 问题的遗传算法实现，计算机时代， 2004年第2 期 改进遗传算法求解背包问题 肖丹凤 *1, 2 杨华 2 1 广西师范大学 计算机科学与信息工程学院 , 广西 桂林 5410042 桂林航天工业学院 信息工程系 , 广西 桂林 ( ) 541004摘 要 改进后的遗传算法采用自然数直接编码 , 在个体选择上结合使用常用的最优个体保留策略和轮盘赌法 。 文章 基于经典 0-1背包问题的数学模型基础 , 构造改进后的遗传算法和适应度评估 , 减少二进制编码或浮点型编 码的复杂性 , 同时精 简 适 应 度 评 估 的 计 算 。 文 章 通 过 进 行 多 次 实 验 和 计 算 , 证 明 改 进 后 的 遗 传 算 法 , 在 优 化 0-1背包问题方面比传统的遗传算法 , 收敛性更好 、 更优越 , 进而更高效地获得问题的最优解或近似最优 。 关键词 改进遗传算法 ; 背包问题 ; 优化 中图分类号 :O 241. 6 文献标志码 :A 文章编号 :1009-1033(2012) 02-0151- 03 背包 问 题 (K n a p s a c k p r o b l e m ) 是 在 运 筹 学 中 的 典 型 N P 完全问题 [1] 。 对该问题 求 解 方 法 在 理 论 研 究 和 实 践 都 有很强的意义 , 如工厂 里 的 作 业 调 度 问 题 、 装 载 问 题 、 管 理 中的资源分配等都可建模为背包问题 。 目前解决背包问题 的算法有贪婪 算 法 [2]、 混 合 蛙 跳 算 法 [3]、 蚁 群 算 法 [4] 以 及 回溯法 [ 5] 等 。 通过比较 分 析 , 发 现 混 合 蛙 跳 算 法 需 将 全 局 信息交换和局部深度搜索相结合 , 构造比较麻烦 , 而蚁群算 法不能保证问题的最优解 , 只能求解问题的近似解 , 回溯法 求问题的所有解时 , 需要回溯到根 , 而且要搜索根节点的所 有叶子节点 , 较适合 求 解 组 数 大 的 问 题 . 而 遗 传 算 法 (G e -n e t i c A l g o r i t h m , G A ) [6-8]。 在 求 解 一 些 复 杂 优 化 问 题 中 , 显示了良好的 求 解 特 性 。 G A 采 用 了 生 物 进 化 论 的 思 想 , 通过自然选择和全局 搜 索 性 能 , 该 方 法 应 用 于 实 践 容 易 产 生早熟收敛 , 并且进 化 后 期 搜 索 效 率 较 低 。 文 章 针 对 背 包 问题的特点 , 对基本遗 传 算 法 进 行 改 进 , 经 过 反 复 实 验 , 改 进的遗传算法获得了比传统遗传算法更好的效果 。 1 背包问题的数学模型 背包问题的数学模型实际上是一个 0-1规划问题 。 假 设有 n 个物件 , 其重量用 a i 表示 , 价值用 c i ( i =1, …, n ) , 背包 的最大容量重量为 b 。 如果物件 i 被选入背包时 , 定义变量 x i =0, 否则 x i =1。 考虑 n 个物件的选择与否 , 背包内物件 的总重量为 ∑ n i =1c i x i , 如何决定变量 x i ( i =1, …, n ) 的值 , 即确 定一个物件的组合序列 , 使得背包内物件总价值为最大 。 该 问题的解的总组合数有 2n 个 , 其数学模型表示如下 : M a x i m i z e ∑ n i =1c i x i s u b j e c t t o ∑ i =n i =1 a i x i ≤ b x i = 0或 1, i =1, …, n (1 ) 表达式 (1) 中 , c i , x i , b 均为正值 。 2 基本遗传算法 (S i m p l e G e n e t i c A l g o r i t h m S G A ) 遗传算法采纳了自然进化模型 , 如选择 、 交叉 、 变异 、 迁 移 、 局域与邻域等 [1] , 图 1显示了基本遗传算法的过程 。 当 遗传算法开始运行时 , 首先对随机产生的种群进行初始化 , 计算种群中单 个 个 体 的 适 应 度 , 并 与 优 化 准 则 进 行 比 较 。 如果满足优化准则 , 则 表 示 已 经 找 出 最 佳 个 体 同 时 输 出 其 值 ; 否则产生新一代 个 体 并 重 新 进 行 比 较 。 在 产 生 新 一 代 个体时 , 父代需要按照 一 定 的 交 叉 概 率 和 变 异 概 率 来 产 生 新一代个体 , 此时新一代个体的适应度将重新进行计算 , 同 时新一代个体按照适 应 度 高 低 插 入 到 上 一 代 种 群 中 , 使 得 种群产生变化而生 成 新 的 种 群 。 循 环 执 行 这 一 过 程 , 直 到 符合优化准则为止 。 图 1 基本遗传算法流程 S G A 算法具有过 程 简 单 、 易 于 理 解 等 特 点 , 但 是 局 部 搜索能力差 , 容易产生早熟 。 1 512012年第 2期 (总第 66期 ) 桂林航天工业高等专科学校学报 J O U R N A L O F G U I L I N C O L L E G E O F A E R O S P A C E T E C HN O L O G Y 信息与电子工程 * 作者简介 :肖丹凤 (1978-) , 女 , 湖南邵阳人 。 讲师 , 硕士研究生 。 研究方向 :计算机网络 。 3 改 进 遗 传 算 法 (I m p r o v e d g e n e t i c a l g o -r i t h m MG A ) 的构造 3. 1 编码方法 编码是运行遗传算 法 的 首 要 要 素 , 也 是 决 定 遗 传 算 法 能够成功的关键要素 。 编码既决定了种群中个体的染色体 排列 , 又决定了优化时搜索范围的大小 , 此外还影响到了交 叉算子 、 变异算子的表现形式 。 根据背包问题中的特点 , 变 量为物件是否被选中 , 属于单一参数问题 , 因此直接编码为 二进制串 。 这种编码方式中 , 如果第 i 个物件被 选 中 , 则 第 i 为基因码为 1, 否 则 第 i 位 基 因 码 编 码 为 0。 设 一 个 一 维 10物 件 的 背 包 问 题 中 , 如 果 产 生 一 个 基 因 编 码 为 0100100010时 , 则说明该基因所选择的物件为 2, 5, 9。 3. 2 初始化种群 在选择初始种群时 , 首先确定 M 个 (1~n ) 不重复的自 然数作为种群规模 。 该过程等于在整个解空间中随机选出 M 个解作为优化的开始 。 3. 3 适应度函数 对于背包问题 , 可以直接使用公式 (1) 作为其适应度函 数 : f ( x 1, x 2, . . . , x n ) =∑ n i =1c i x i , x i =0或 1, i =1, . . . , n (2 ) 3. 4 选择操作的改进设计 选择操作是为把更优的个体通过直接遗传的方式传递 给下一代或者通过配 对 交 叉 后 产 生 的 新 个 体 传 递 给 后 代 。 选择操作首先要对种 群 中 的 个 体 进 行 适 应 度 的 评 估 , 只 有 适应度更高的个体才能被通过遗传而保留 。 改进后的选择 操作将种群中 适 应 度 高 的 个 体 直 接 保 留 而 不 进 行 交 叉 配 对 , 同时直接传递到新种群中 。 定义 设时刻 t (第 T 代 ) 时 , 群体中 x (t ) 为最佳个体 。 设 X (t +1) 为新一代群体 , 若 X (t +1) 中不存在 x (t ) , 则把 x (t ) 作为 X (t +1) 中的第 M +1个个体 (其中 , M 为群体大 小 ) 。 改进后的选择操作可以使进化过程中某一代的最优解 不被变异或交叉操作所淘汰 。 3. 5 交叉操作的改进设计 交叉操作是将种群中的两个父代个体的部分基因码进 行交换重组后形成新个体的一种操作 。 此处的交叉操作基 于文献 [4, 8] 中所 使 用 的 交 叉 操 作 算 法 基 础 上 , 基 于 种 群 直 径和半径等概念 , 进而计算交叉概率 p 。 p 使 用 公 式 (3) 进 行计算 : p = 5 M d -3 M r 3 M d (3 ) 其中 , M 为当前种群 ; M d 为 当 前 种 群 直 径 。 M r 为 当 前 种群的半径 。 此处的交叉概率 P 并 不 固 定 , 而 是 随 着 遗 传 算法进行时种群所反映出来的相关信息变化 。 在遗传算法 刚开始进行时 , 种群的 规 模 不 大 , 因 为 交 叉 概 率 也 较 小 , 此 时正好充分利用交叉操作对种群进行改造 。 而当算法进行 到一定规模时 , 因为选择操作所作出的改变 , 种群规模此时 较大 , 此时无需对种群进行大规模改造 , 因而此时交叉概率 将接近于 1。 此 种 改 进 能 够 更 多 地 保 留 种 群 中 的 优 秀 基 因 , 使遗传算法能够加快收敛 , 及时找到问题的最优解 。 3. 6 变异操作 变异操作能够使种 群 中 的 染 色 体 多 样 化 , 不 至 于 在 算 法进行过程中陷入局部最优的情况 。 此处根据预先设定好 的一个变异概率 p ' 对 交 叉 后 形 成 的 新 一 代 种 群 进 行 变 异 , 使种群中的染色体能够保持多样性 。 至于什么时候终止 算 法 , 最 简 单 的 方 式 为 算 法 达 到 指 定的遗传代数后直接 终 止 , 也 可 以 根 据 相 关 改 进 及 时 作 出 判断来提高算法的效率 。 此处改进主要在选择操作和交叉 操作 , 如果种群中某染 色 体 能 够 在 连 续 一 定 的 代 数 中 一 直 保持 , 则说明算 法 已 经 产 生 了 最 优 解 , 此 时 可 以 及 时 终 止 算法 。 4 实验与比较 根据改 进 遗 传 算 法 , 编 写 了 M a t l a b 程 序 , 用 实 验 验 证 改进遗传算法后的效果 。 实例中问题规模为 50个变量 , 并 随机地产生系数值 , 按以下三个步骤生成一个背包问题 , 共 生成 10个 。 ① 50个系数 c i , a i 在区间 (0, 999]内随机产生 。 ② b 的值按 p ∑ 50 i =1 a i 计算 , 其中 p 为区间 [0. 25, 0. 75]内 一随机数 。 ③ 若 所 有 a i ≤ b (i =1, . . . , 50) 则 结 束 操 作 ; 若 存 在 a i > b , 则返回到步骤 ① , ② 。 表 1 50个体背包问题数据表 c i 882 16 216 660 354 233 124 832 12 92061 273 763 406 985 562 123 972 879 6038 82 192 137 609 260 292 732 723 383 561620 760 848 707 117 453 640 703 599 163822 540 898 311 421 497 86 326 447 784a i 600 428 590 34 241 922 794 828 853 612747 779 384 985 715 298 423 256 762 9 34 02 842 872 446 760 122 895 163 98 855792 354 92 628 327 930 9 734 305 739774 907 508 488 839 865 486 769 368 937b 1 883372 512012年第 2期 (总第 66期 ) 桂林航天工业高等专科学校学报 J O U R N A L O F G U I L I N C O L L E G E O F A E R O S P A C E T E C HN O L O G Y 肖丹凤 杨华 /文 表 1列出了按照 以 上 步 骤 产 生 的 一 个 5 0变 量 的 背 包 问题数据 。 设定遗传算法运行时个体数为 50, 交 叉 率 使 用 公式 (3) 进 行 动 态 计 算 , 变 异 率 为 0. 001, 终 止 代 数 为 500代 。 将遗传算法模拟计算末世代目标函数值与分枝定界法 获得的精确值比较 得 到 相 对 误 差 。 对 10个 不 同 的 问 题 分 别计算 , 得到图 2、 图 3所示的基本遗传算法和改 进 遗 传 算 法最差值误差和最优值误差值比较 。 显然 , 对于同一问题 , 改进后的遗传算法较基本遗传算法要优越得多 。 图 2 最差值的误差比较 图 3 最优值的误差比较 5 结束语 针对背包问题 , 直接使用二进制编码 , 能够简化对种群 个体适应度的计算 ; 同时改进选择操作 , 以保留适应度高的 个体不至于被交叉操作等淘汰 ; 改进交叉概率的计算 , 能够 让算法有更好的收敛性 , 加速最优个体的产生 。 实验表明 , 改进后的遗传算法比基本遗传算法在求解背包问题中有更 好的表现 。 需要注意的是 , 50变量的背包问 题 是 较 简 单 的 单目标背包问题 , 若考虑多目标的情况 , 将是需要进一步研 究的问题 。 参考文献 [1] 王小平 , 曹立明 . 遗传算法 — — — 理论 、 应用与算法实现 [M ]. 西安 :西安交通大学出版社 , 2002:136- 140. [2] K i m H S , C h o S B . A p p l i c a t i o n o f I n t e r a c t i v e G e n e t i c A l g o r i t h m t o F a s h i o n D e s i g n [J ]. E n g i n e e r i n g A p p l i c a t i o n o f A r t i f i c i a l I n t e l l i g e n c e , 2000, 13(6) :635-644. [3] 陈亮 . 改进的混合蛙跳算法求解背包问题 [J ]. 长春工业大学学报 :自然科学版 , 2011, 32(1) :61-63[4] 秦玲 , 白云 , 章春芳等 . 解 0-1背包问题的蚁群算法 [J ]. 计算机工程 , 2006, 32(6) :212- 214. [5] 马慧民 , 叶春明 , 张爽 . 二进制改进粒子群算法在背包问题中的应用 [J ]. 上海理工大学学报 , 2006, 26(1) :31-34. [6] A r n o l d D V , H a n s -G e o r g B . A G e n e r a l N o i s e M o d e l a n d I t s E f f e c t s o n E v o l u t i o n S t r a t e g y P e r f o r m a n c e [J ]. I E E E T r a n s a c t i o n o n E v o l u t i o n a r y C o m p u t a t i o n , 2006, 10(4) :380-391. [7] 郝国生 , 张勇 , 石明辉 , 等 . 基于灭绝机制的交互式遗传算法 [J ]. 控制理论与应用 , 2006, 23(5) :665-670. [8] 孙晓云 , 蔡远利 . 利用改进遗传算法的参数估计 [J ]. 自动化技术与应用 , 2004, 23(1) :23- 26. [9] I . J . G r a h a m. G e n e t i c a l g o r i t h m s i n c o m p u t e r -a i d e d d e s i g n . J o u r n a l o f M a t e r i a l s P r o c e s s i n g T e c h n o l o g y . V o l u m e 117, I s s u e s 1-2, 2001, 11(1) :216- 221. [10] 史亮 , 邹谊 , 庄镇泉 . 基于主动进化遗传算法的模糊聚类技术 [J ]. 小型微型计算机系统 , 2005, 26(2) :204-208. [11] 潘伟 , 刁华宗 , 井元伟 . 一种改进的实数自适应遗传算法 [J ]. 控制与决策 , 2006, 21(7) :792- 795, 800. (责任编辑 李卫华 ) 3 512012年第 2期 (总第 66期 ) 桂林航天工业高等专科学校学报 J O U R N A L O F G U I L I N C O L L E G E O F A E R O S P A C E T E C HN O L O G Y 肖丹凤 杨华 /文 课程设计 题目6-基于遗传算法求解0-1背包问题 一、 题目分析 （1） 遗传算法：遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自 然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan 大学J.Holland 教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA 这个名称才逐渐为人所知，J.Holland 教授所提出的GA 通常为简单遗传算法（SGA ）。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法是从代表问题可能潜在的解集的一个种群（population ）开始的，而一个种群则由经过基因（gene ）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation ）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness ）大小选择（selection ）个体，并借助于自然遗传学的遗传算子（genetic operators ）进行组合交叉（crossover ）和变异（mutation ），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding ），可以作为问题近似最优解。 （2） 遗传算法的基本运算过程如下：a) 初始化:设置进化代数计数器t=0，设置 最大进化代数T ，随机生成M 个个体作为初始群体P(0)。b) 个体评价:计算群体P(t)中各个个体的适应度。c) 选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d) 交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e) 变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f) 终止条件判断:若tT, 则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 （遗传算法流程图） （3） 0-1背包：给定n 中物品和一个背包。物品i 的重量是Wi ，其价值为Vi ， 背包的容量为C 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？在选择装入的背包的物品时，对每种物品i 只有两种选择，即装入背包或不装入背包。不能将物品i 装入背包多次，也不能只装入部分物品i 。因此，该问题成为0-1背包问题。 二、 总体设计 本学期中，我们学习了多种算法求解背包问题，本次课程设计中，我们通过自学探究方法用遗传算法求解背包问题。首先，运用遗传算法步骤，产生初始群体、评价个体、复制交叉变异等中心步骤求解，为背包问题的进一步学习拓宽了思路。 三、 详细设计 根据设计要求，该算法的基本运行流程为: 第1 步: 随机产生一组初始个体构成的初始群体; 第2 步: 对串群体迭代的执行下面的步骤(3) , (4) , 直到满足停止准则后转(5) ; 第3 步: 计算群体中每一个个体的适配值(fitness value) ; 第4 步: 应用复制、交叉、变异算子产生下一代群体; 第5 步: 把在任何一代中出现的最好的个体串指定为遗传算法的执行结果, 这个结果可以表示问题的一个解(或近似解) 。由此可设计所需结构和函数如下: 1. 定义数据类型 个体评价的结构类型 typedef struct tagIndivdualMsg { int index; int value; } IndivdualMsg; IndivdualMsg indivdualMsg[max]; 2. 实现算法的各函数说明： （1） （2） 对个体进行评价: 初始化群体：void colonyInit() int cmp(const void *a, const void *b), void indivdualEstimate() （3） bool stopFlag() （4） 赌轮选择, 计算适应度 终止循环的条件，给定一个最大进化步数 int gambleChoose() （5） 交叉，进行交叉运算, 随即选择一对个体产生一对有效交叉位置 进行交叉运算, 并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量, 则对新产生的个体进行修正, 放弃在一个个体中的一个物品, 增加另一个个体的一个物品使其重量小于背包重量。 void across(int male, int female, int index) （6） 变异进行变异操作, 如果一个个体的一个基因为1, 则变为0; 如果 是0则变为1, 重新计算该个体的适应度值和约束条件值 void aberrance(int index) （7） void dealDeath() （8） void saveBest() 处理死亡个体 最优个体保护 （9） 输出函数void setProblem() void printProblem(); void printColonyState(int k) ; void printIndividualMsg(); （10） 主函数: void main() { 调用函数； 解出问题的解； } 3. 函数调用关系如图： 四、 调试分析 错误1 --------------------Configuration: bag - Win32 Debug-------------------- Compiling... bag.cpp c:\documents and settings\administrator\桌面\算法\bag\bag.cpp(41) : error C2018: unknown character '0xa3' c:\documents and settings\administrator\桌面\算法\bag\bag.cpp(41) : error C2018: unknown character '0xac' c:\documents and settings\administrator\桌面\算法\bag\bag.cpp(41) : error C2146: syntax error : missing ';' before identifier 'j' c:\documents and settings\administrator\桌面\算法\bag\bag.cpp(41) : error C2065: 'j' : undeclared identifier Error executing cl.exe. bag.exe - 4 error(s), 0 warning(s) 分析：在代码编写过程中，由于中英文输入法之间的转换，错将英文输入法下的“, ”输入为中文输入法下的“，”以至于出现错误。这类错误是在程序设计中经常出现的错误，是由于长时间的程序编写造成的粗心大意造成的。 解决：将中文输入法下的“，”改为英文输入法下的“, ”即可 。 错误2 --------------------Configuration: bag - Win32 Debug-------------------- Compiling... bag.cpp C:\Documents and Settings\Administrator\桌面\算法\bag\bag.cpp(285) : error C2065: 'saveBest' : undeclared identifier Error executing cl.exe. bag.exe - 1 error(s), 0 warning(s) 分析：函数调用过程输错。 解决：重新书写出错的函数名即可。 五、 测试结果 测试数据如下： 物品个数：5 物品价值：6、3、5、4、6 物品重量：2、2、6、5、4 背包容量：10 程序运行结果如下: 六、 程序代码 //遗传算法求解0-1背包问题 #include #include #include #include #include using namespace std; //定义问题的最大规模 #define max 100 //为题规模，即共有多少个包 int packageNum; //每个包的重量 int packageWeight[max]; //每个包的价值 int packageValue[max]; //约束，背包的最大容量 int limitWeight; //群体的规模 int colonySize; /*colonyState[i][k] 表示一个染色体*/ /*colonyState[1...conlonySize][0|1] 表示一个群体*/ int colonyState[max][2][max]; /* currAge 表示当前代的编号*/ /* (currAge+1)%2 表示下一代的编号*/ int currAge = 0; /* 个体评价*/ typedef struct tagIndivdualMsg { int index; int value; }IndivdualMsg; IndivdualMsg indivdualMsg[max]; /*函数声明*/ void printColonyState(int nextAge); /*初始化群体，初始种群产生, 并计算每个适应度值和其对应的约束条件值(即为在染色体中选取的物品的重量) , 比较初始种群中各个个体的适应度。选择最大者所对应的个体作为第一代最优个体, 并记录该个体以及它的适应度和约束条件值。*/ void colonyInit() { int i, j; int w; for(i=0; i } } //保证找到一个符合约束的染色体 w = limitWeight +1; while(w > limitWeight) { } w = 0; for(j=0; j<><=limitweight; j++)="" {="" }="" colonystate[i][currage][j]="rand()%2;" w="" +="packageWeight[j]" *=""> /*对个体进行评价*/ int cmp(const void *a, const void *b) { } void indivdualEstimate() { IndivdualMsg *x = (IndivdualMsg *)a; IndivdualMsg *y = (IndivdualMsg *)b; return y->value - x->value; int i, j; for(i=0; i } indivdualMsg[i].value += packageValue[j]*colonyState[i][currAge][j]; qsort(indivdualMsg, colonySize, sizeof(IndivdualMsg), cmp); } /*终止循环的条件，给定一个最大进化步数*/ bool stopFlag() { //进行n 代进行后停止 static int n = 50; if(n-- <=> return false; else return true; } /*赌轮选择*/ int gambleChoose() { int wheel[max] = {0}; int i = colonySize-1; int choose; wheel[i] = indivdualMsg[i].value; for(i--; i>=0; i--) wheel[i] = (indivdualMsg[i].value colonySize*(colonySize-i); int seed = abs(wheel[0]-(rand()%(2*wheel[0]+1))); choose = colonySize-1; while(seed > wheel[choose]) choose--; return choose; + wheel[i+1]) + /*交叉，进行交叉运算, 随即选择一对个体产生一对有效交叉位置进行交叉运算, 并计算新产生的个体的适应度值和约束条 件值。如果新产生的个体重量大于背包容量, 则对新产生的个体进行修正, 放弃在一个个体中的一个物品, 增加另一个个体的 一个物品使其重量小于背包重量。*/ void across(int male, int female, int index) { int nextAge = (currAge+1) %2; int i, j, t; int acrossBit = rand() % (packageNum-1) + 1; for(j=0; j colonyState[index+1][nextAge][j] = colonyState[indivdualMsg[female].index][currAge][j]; } /*变异:进行变异操作, 如果一个个体的一个基因为1, 则变为0; 如果是0则变为1, 重新计算该个体的适应度值和约束条件值*/ void aberrance(int index) { } for(i=0; i nextAge = (currAge+1) %2; //只有1/3的概率发生异变 seed = rand() %(packageNum*3); if(seed < packagenum)="" colonystate[index][nextage][seed]="(colonyState[index][nextAge][seed]"> 1) %2; } /*处理死亡个体*/ void dealDeath() { int i, j; int weight, w; int nextAge = (currAge+1) %2; for(i=0; i } } } } /*最优个体保护*/ void saveBest() { int i, j; int min, minp, value; int nextAge = (currAge+1) %2; min = indivdualMsg[0].value; minp = -1; for(i=0; i { value = 0; for(j=0; j value += packageValue[j] *colonyState[i][nextAge][j]; if(value <=> { min = value; minp = i; } } if(minp >= 0) { for(j=0; j { colonyState[minp][nextAge][j] colonyState[indivdualMsg[0].index][currAge][j]; = } } } /*输出函数*/ void setProblem() { for(i=0; i } cout<> void printProblem() { } void printColonyState(int k) { int i; cout<> } for(i=0; i for(j=0; j cout<><> cout<> void printIndividualMsg() { } void main() { int i; cout<> cout<><><><> srand((unsigned int)time(NULL)); setProblem(); printProblem(); //初始化群体 colonyInit(); printColonyState(currAge); while(! stopFlag()) { //评价当前群体 indivdualEstimate(); //生成下一代 for(int i=0; i } } //处理死亡个体 dealDeath(); //保护最优个体 saveBest(); //现在的下一代变成下一轮的当前代 currAge = (currAge+1) %2; int male = gambleChoose(); int female = gambleChoose(); across(male, female, i); aberrance(i); aberrance(i+1); //输出问题解 indivdualEstimate(); cout<> cout<><<"value:"; for(j="0;"> cout<><> cout<> cout<><<"weight:"; for(j="0;"> cout<> cout<><<"choose:> w += packageWeight[j] *colonyState[indivdualMsg[0].index][currAge][j]; cout<><> } cout<><> cout<> cout<<"limitweight:><> cout<<"总价值:><><> 七、 算法比较 从计算复杂性理论看, 背包问题是一个经典NP 难解问题。半个多世纪以来, 该问题一直是算法与复杂性研究的热点问题之一。通过对0-1背包问题的算法分析可以看出, 回溯法能够精确地得到问题的最优解, 可是计算时间太慢; 动态规划算法也可以得到最优解, 但当m > 时, 算法需要Ω ( n* ) 的计算时间, 这与回 溯法存在着一样的缺点——计算速度慢; 采用贪心算法和遗传算法, 虽然耗费上优于前者, 但不一定能得到最优解。目前, 以上四种方法都广泛地应用到不同的实际问题中, 并在应用中不断改进和完善。 八、 遗传算法解决0-1背包问题的进一步探究 8.1 改进遗传算法的基本思想 人类的繁殖方式与其他动物有着根本的区别。首先，为了提高人口素质，法律对婚配年龄作了明确的规定， 也就是说人类的繁殖要受到法定年龄的制约。当然，在达到一定的年龄之后，个体的生育能力也就自然消失了；其次，人类的繁殖方式是严格的远缘繁殖，而在动物界，“乱伦”现象经常发生。人类为了避免近亲繁殖，制定了相应的法律来进行约束，法律规定直系血亲和三代以内的旁系血亲禁止通婚，因为研究表明，双亲的亲缘关系越近，他们的基因特性雷同的机会就越大，并存于双亲的基因就越容易显现出消极的一面， 致使近亲繁殖产生的后代往往都体弱多病，甚至不能存活。 为了提高遗传算法的收敛性能，本文将人类繁殖方式引入到遗传算法中来，得到一种改进的遗传算法(IGA)。该算法的遗传个体具有雄性和雌性两种性别，同时融合了个体的年龄和个体间的亲缘关系两种特征，在允许的年龄范围内，异性个体进行严格的远缘繁殖，遗传算子包括选择算子、助长算子、交叉算子和变异算子。这种改进的遗传算法流程如图1 所示。 8.2 编码方法 采用二进制编码方法对个体进行编码，每一个个体编码是由两部分组成的，第一部分是个体表现型对应的二进制编码；第二部分是个体性别对应的二进制编码，如表1 所示。 其中，个体性别编码部分为0 或1，可用0 表示雌性个体，用1 表示雄性个体。个体表现型编码是将n 个xi 的值顺序排列， 就可构成背包问题的遗传编码。具体地说，个体表现型编码X=（x1，x2，?，xn ），xi=0或1，如果xi=1，则表示将第i 件物品放入背包中；如果xi=0， 则表示第i 件物品不放入背包中。例如“110001100000000??0000000011” 就代表一个解，它表示将第1，2，6，7，??n-1，n 号物品放入背包中，其他的物品则不放入。 8.3 适应度函数 由于适应度值是群体中个体生存机会选择的唯一确定性指标，所以适应度函数的形式直接决定着群体的行为进化。为了直接将适应度函数与群体中的个体优劣度量相联系， 在遗传算法中规定适应度为非负，并且在任何情况下总是越大越好。本文在进行个体适应度评价时， 直接使用目标函数作为适应度函数，即： 式中，vi 表示第i 个物品的价值。 8.4遗传算子 （1）选择算子 采用两代竞争排序的选择方法来对个体进行优选，即把父代与子代的所有雄性个体与雌性个体分别进行重新排序，再在允许的年龄范围内按群体规模N 分别从排序后的雄性个体集与雌性个体集中截取前N/2 个优秀的个体进入匹配池， 作为交叉操作的对象。这样不仅保证了交叉操作的个体能进行有效的配对，同时也可以使每一代的优秀个体得以保留，而淘汰那些不良的个体， 从而使好的基因和模式不会丢失，有利于尽快找到全局最优解。 （2）助长算子 为了加强算法跳出局部最优的能力，加速算法的收敛，IGA 使用一个助长算子来对种群中的个体进行一定概率下的助长。助长操作在选择操作之后及配对操作之前进行，其具体步骤如下： Step1：令i=1； Step2：随机产生一个实数r ，使0≤r ≤1，如果r ≤ph ，则执行Step3；否则，跳转到Step6； Step3：令j=1； Step4：如果=0，令 =1；但如果此时si 的适应度值降低，则维持 =0； Step5：j=j+1，如果j>n-1，则执行Step6；否则，跳转到Step4； Step6：i=i+1，如果i>N，则执行Step7；否则，跳转到Step2； Step7：结束。 其中，ph 表示助长概率，si 表示种群中第i 个个体，sij 表示第i 个个体编码的第j 位，n 表示编码长度，N 表示种群大小。 （3）交叉与变异算子 二进制编码方式下的交叉操作采用单点交叉方式非常有效，单点交叉操作的重要特点是：它可以产生与原配对个体完全不同的子代个体，如果邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度，那么单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。 经过杂交产生的所有新个体，要在一定概率下随机发生变异，形成新一代种群，这样增加了群体中个体的多样性，有助于跳出局部最优，达到全局最优。在二进制编码方式下，变异操作就是以很小的变异概率从群体中随机选取若干个体，对于选中的个体又随机选取表现型编码中的某一位或多位进行数码翻转，即将1 变为0 或0 变为1。 （4）个体年龄判断 个体的繁殖能力与年龄有着十分密切的关系，随着年龄的增长，个体的成活率和繁育率均成下降的趋势，个体的繁殖能力也会随之衰减。在基本遗传算法中， 对个体基因年龄的忽略是不符合自然规律的，这样有可能会导致搜索范围缩小及局部最优，从而出现早熟收敛。为此，本文改进算法在选择操作之后首先要对进入匹配池中的个体进行年龄判断，不符合年龄要求的个体予以剔除，重新选择相同性别的优秀个体来替换。 个体年龄判断方法：设个体配对的最大允许年龄为N ，初始种群P （0）中个体的年龄记为ni （0）=1，每进化一次，个体年龄加1，记录每次进化后新种群P （t ）个体的年龄ni （t ）。如果ni （t ） （5）配对于亲缘关系计算 在本文改进的遗传算法中，同性别个体之间是不能进行配对的， 雄性个体只能同雌性个体进行配对。配对是按个体优劣顺序进行的，即对按优劣顺序排队的雄性个体与按优劣顺序排队的雌性个体进行一一配对， 这有利于提高遗传算法寻找全局最优解的速度，增强遗传算法的全局收敛能力。 为了避免近亲繁殖，两个异性个体在配对之后还要进行个体间亲缘关系的检测。个体间亲缘关系直接用两个个体表现型编码对应的二进制数的差值来衡量， 如果两个个体表现型编码所对应的二进制数相等或者仅相差1，则视为近亲，不能进行杂交，需对它们进行修正。修正的方法是：把适应度小的个体表现型编码的高位修改为与适应度大的个体表现型编码的高位不同的值。这样，保证个体之间的繁殖属于远缘繁殖，从而提高遗传算法的效率。 九、 参考文献 [1].《算法设计与分析》，清华大学出版社，王晓东编著 [2].《0-1背包问题的遗传算法求解》，鄂州大学，曾国清 [3].《0-1背包问题及其算法分析》，金华职业技术学院，应莉 [4].《一种求解背包问题的改进遗传算法》，湖南理工学院，严太山、陈专红、陈群 [5].遗传算法，百度百科，baike.baidu.com遗传算法求解TSP问题
遗传算法求解tsp
改进遗传算法求解背包问题
6-遗传算法求解背包问题
