用遗传算法求解多维背包问题

数学建模遗传算法例题数学建模中，遗传算法是一种基于进化思想的优化算法，可以应用于复杂的优化问题中。

本文将介绍一些遗传算法的例题，帮助读者更好地理解遗传算法的应用。

例题一：背包问题有一个体积为V的背包和n个物品，第i个物品的体积为vi，价值为wi。

求这个背包最多能装多少价值的物品。

遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群。

2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。

3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。

4. 交叉：对被选中的个体进行交叉操作，生成新的个体。

5. 变异：对新的个体进行变异操作，引入新的基因。

6. 重复以上步骤，直到符合终止条件。

在背包问题中，适应度函数可以定义为：背包中物品的总价值。

交叉操作可以选择单点交叉或多点交叉，变异操作可以选择随机变异或非随机变异。

例题二：旅行商问题有n个城市，旅行商需要依次经过这些城市，每个城市之间的距离已知。

求旅行商经过所有城市的最短路径。

遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群，每个个体代表一种旅行路线。

2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。

3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。

4. 交叉：对被选中的个体进行交叉操作，生成新的个体。

5. 变异：对新的个体进行变异操作，引入新的基因。

6. 重复以上步骤，直到符合终止条件。

在旅行商问题中，适应度函数可以定义为：旅行商经过所有城市的总距离。

交叉操作可以选择顺序交叉或部分映射交叉，变异操作可以选择交换或反转基因序列。

总结：遗传算法是一种强大的优化算法，可以应用于多种复杂的优化问题中。

在数学建模中，遗传算法的应用也越来越广泛。

本文介绍了背包问题和旅行商问题的遗传算法解决步骤，希望对读者有所帮助。

遗传算法解决01背包问题2015 ～2016 学年第二学期学生姓名专业学号2016年 6 月目录一：问题描述 (3)二：遗传算法原理及特点 (3)三：背包问题的遗传算法求解 (3)1.文字描述 (3)2.遗传算法中的抽象概念在背包问题的具体化 (3)3.算法求解的基本步骤 (4)四：算法实现 (4)1.数据结构 (4)2.部分代码 (5)五：结论 (8)六：参考文献 (8)一、问题描述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。

01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。

问应如何选择合适的物品装入背包，使得背包中装入的物品的总价值最大。

注意的一点是，背包内的物品的重量之和不能大于背包的容量C。

在选择装入背包的物品时，对每种物品i只有两种选择：即装入背包或者不装入背包，不能讲物品i装入背包多次，也不能只装入部分的物品，称此类问题为0/1背包问题。

二、遗传算法原理及特点遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法有着鲜明的优点：(1)遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条,因而具有良好的并行性.(2)遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因而适用于任何规模,高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性.(3)遗传算法择优机制是一种“软”选择,加上良好的并行性,使它具有良好的全局优化性和稳健性.(4)遗传算法操作的可行解集是经过编码化的(通常采用二进制编码),目标函数解释为编码化个体(可行解)的适应值,因而具有良好的可操作性与简单性.三、背包问题的遗传算法求解1、文字描述0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。

遗传算法求解背包问题程序实现一、背包问题描述背包问题是著名的NP 完备类困难问题,对这个问题的求解前人已经研究出了不少的经典的方法,对该问题确实能得到很好的结果。

近年来蓬勃发展起来的遗传算法已被广泛地应用于优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制. 本程序将遗传算法应用于背包问题。

二、实验程序1、编程语言：C++2、开发环境：Microsoft Visual Studio 20053、程序整体流程：步1初始化过程1. 1确定种群规模scale、杂交概率pc、变异概率pm、染色体长度chN及最大进化代数maxgen。

1. 2取x1′(0) = u (0 ,1) , x2′(0) = u (0 ,1) , …, xchN′(0) = u (0 ,1) ,其中函数u (0 ,1) 表示随机地产生数0 或1 ,则x (0) = ( x1 (0) , x2 (0) ,⋯, xN (0) ) .若不满足约束条件,则拒绝接受. 由(1. 2) 重新产生一个新的染色体; 如果产生的染色体可行,则接受它作为种群的一名成员,经过有限次抽样后, 得到scale个可行的染色体xj (0) , j =1 ,2 , ⋯, M ,设xj (0) 的染色体编码为vj (0) ,并记为v (0) = ( v1 (0) , ⋯, vchN (0) ) .1. 3计算各个染色体的适值1. 4 置k = 0步2选择操作2. 1采用转轮法选择下一代。

.步3杂交变异操作3. 1 事先定义杂交操作的概率pc ,为确定杂交操作的父代,从j = 1 到M 重复以下过程:从[0 ,1 ] 中产生随机数r ,若r < pc ,则选择cj′( k)作为一个父代.3. 2 产生两个[1 , N ] 上的随机整数i 、j ,变异的结果为染色体vj′( k)的第i 位基因的值变为其第j 位基因的值,同样将染色体的vj′( k)第j 位基因的值变为其第i 位基因的值.3. 3 检验该染色体的可行性,若可行则作为变异的结果;如不可行,重复3. 2 直至该染色体可行.3. 4 事先定义变异概率pm ,对经过杂交操作的中间个体进行变异操作: ,如果r < pm ,则选择vi″( k) 作为变异的父代.3. 5 产生一个[1 , N ] 上的随机整数i ,及随机地产生数0 或1 , 记为b , 变异的结果为染色体vi″( k) 的第i 位基因的值变为b.3. 6 检验该染色体的可行性,若可行则作为变异的结果:如不可行,重复3. 5 直至该染色体可行.3. 7 计算新个体的适应值,并把它们同时放回,和步2 选择操作中剩余的个体一起构成新一代种群v ( k + 1) = { v1 ( k + 1) , v2 ( k + 1) , ⋯, vM ( k + 1) } .步4 终止检验如果达到最大进化代数maxgen 则终止演化,否则置k : = k + 1 ,转步2.4、程序流程图程序流程图5、程序代码1）主程序代码：KnapsacksProblem.cpp文件#include "GAonKP.h"#include <iostream>using namespace std;void main(){FILE* fp;CGAonKP gakp;int scale; //种群规模double MaxWeight; //背包允许最大财宝质量double pc; //杂交概率double pm; //变异概率int maxgen; //最大进化代数char filename[256];cout<<"遗传算法解决背包问题程序使用说明："<<endl;cout<<"1、该背包问题采用遗传算法"<<endl;cout<<"2、-1编码的方法，其中代表选中所对应的物品，代表不选中该物品"<<endl;cout<<"3、背包允许最带重量，种群规模（解空间大小），";cout<<"杂交概率，变异概率，最大进化代数需自己给";cout<<"定，程序会提示输入"<<endl;cout<<"4、程序提供一个输入示例"<<endl;cout<<"5、输入文件可加单行或多行注释"<<endl;cout<<"例如：#添加单行注释内容#"<<endl;cout<<"例如：#添加多行注释内容"<<endl;cout<<" 添加多行注释内容#"<<endl;cout<<"6、输入文件头位置需指定物品个数为int型数据。

遗传算法求解0-1背包问题一、问题描述给定n种物品和容量为C的背包。

物品i的重量是wi，其价值为vi。

问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示1、状态表示（1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。

（2）基因：染色体的每一个比特。

（3）种群：解的集合。

（4）适应度：衡量个体优劣的函数值。

2、控制参数（1）种群规模：解的个数。

（2）最大遗传的代数（3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.4～0.99。

（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001～0.1。

3、算法描述（1）在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；（2）随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代数计数器t=1；（3）计算S中每个个体的适应度f() ；（4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。

（5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；（6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；（7）按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；（8）将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。

三、算法实现1、主要的数据结构染色体：用一维数组表示，数组中下标为i的元素表示第（i+1）个物品的选中状态，元素值为1，表示物品被选中，元素值为0表示物品不被选中。

种群：用二维数组表示，每一行表示一个染色体。

遗传算法的过程：初始化：将计划装入背包的每个物品看成一个二进制串的一位，为1表示放入该物品，为0表示不放入该物品。

初始种群的产生：初始化前对放入背包物品数的一个预测（背包容积/物品最大体积），接下来只要在种群每条染色体中保证有（背包容积/物品最大体积）个为1的位初始化就完成了。

选择：选择进行杂交的父代染色体，被选中的父代染色体总是若干个染色体中最优（适应度最高）的，来保证向优化的方向发展。

详细的选择方法：随机产生2个数：Chrom_Cross_From, Chrom_Cross_To,当然得采用一定的手段来保证前者比后者小。

从Chrom_Cross_From到Chrom_Cross_To这Chrom_Cross_To-Chrom_Cross_From+1条染色体中选择最优（适应度最大）的染色体作为父代之一。

需要进行两次选择得到杂交的两条父代染色体。

这样做可以保证算法不会过早收敛。

函数实现：Individual Select(int ChromSize,Individual Pop[]){int Num_Selected,i,j,Chrom_Selected_From,Chrom_Selected_To,temp;Individual *Chrom_Selected;do{Chrom_Selected_From=rand()%PopSize;Chrom_Selected_To=rand()%PopSize;if(Chrom_Selected_From>Chrom_Selected_To){temp=Chrom_Selected_From;Chrom_Selected_From=Chrom_Selected_To;Chrom_Selected_To=temp;}Num_Selected=Chrom_Selected_To-Chrom_Selected_From+1;}while(Num_Selected<=0);Chrom_Selected=new Individual[Num_Selected];for(i=0;i<Num_Selected;i++)Chrom_Selected[i].chrom=new int[ChromSize];for(i=0,j=Chrom_Selected_From;i<Num_Selected,j<Chrom_Selected_To+1;i++,j++){Chrom_Selected[i]=Pop[j];}Order_Best_First(ChromSize,Num_Selected,Chrom_Selected);Chrom_Selected[0].fitness=Fitness(Chrom_Selected[0].chrom,ChromSize);return Chrom_Selected[0];}杂交：将两次选择得到的父代染色体进行杂交得到一条新的染色体，作为较新种群（并非新的种群）的一条染色体，杂交直到较新种群的染色体数等于原种群的染色体数。

遗传算法考试题目
题目1：使用遗传算法求解旅行商问题。

假设有一位旅行商需要拜访n个城市，每个城市只能访问一次，并且从一个城市回到起始城市。

每个城市之间都有距离，求解旅行商经过的最短路径。

题目2：使用遗传算法优化函数f(x)=x^2-4x+4，求解使得f(x)取得最小值的x。

题目3：使用遗传算法求解背包问题。

假设有一个背包的容量为C，同时有n个物品，每个物品有自己的重量和价值。

要求
选择一些物品放入背包中，使得背包内物品的总重量不超过C，并且物品的总价值最大。

题目4：使用遗传算法进行图像压缩。

假设有一张彩色图像，每个像素点都有RGB三个分量的值。

要求使用遗传算法对这
张图像进行压缩，使得图像的质量损失最小化的情况下，压缩比最大化。

题目5：使用遗传算法优化神经网络结构。

假设有一个神经网络，其层数和每层的节点数都是可调整的。

使用遗传算法搜索出最优的神经网络结构，使得在给定的数据集上，神经网络的预测性能最好。

一种有效求解多维背包问题的遗传算法摘要：就多维背包问题的求解，提出一个基于遗传算法的启发式算法（MKPGA）。

该算法中加入了一个利用问题特性知识的启发式修复算子以帮助求解。

测试实例使用270个不同特性的多维背包问题，实验结果表明，该算法对多维背包问题的求解十分有效，能获得不同特性问题的高质量解。

关键词：遗传算法;多维背包问题;贪婪算法遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，对它的研究起源于20世纪70年代初，由美国Michigan 大学的J.Holland教授于1975年正式提出。

GA的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。

它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。

2求解MKP的遗传算法设计MKPGA使用了一个基于简单贪婪算法的修复算子来修复交叉、变异操作后可能产生违反背包约束的不可行解。

虽然在标准遗传算法中并未提到修复算子的使用，但根据不同问题特性设计的修复算子被广泛应用在解决不同问题的遗传算法中。

MKPGA所采用的策略描述如下：①联赛选择方法；②一致交叉；③物品数小于500时变异概率取2／个体基因串长位，当物品数等于500时，变异概率取3/个体串长度；④不允许种群中有相同的个体；⑤每次迭代只产生一个不同于当前种群的新个体，如果新个体比当前种群中最差的个体好，则替换掉该最差个体。

3计算实验3.1实例本文使用的测试实例是由Beasley和Chu所提供的270个多维背包问题。

其中约束个数m包括5、10和30，物品数量n包括100、250和500，每一组m-n各有30个问题。

下面介绍这270个实例的生成方法。

物品j消耗资源i的量wij为一个均匀分布在区间（0，1 000）上的整数。

对于每一个m-n的组合，每个资源约束bi=α∑nj=1wij，α是问题的紧密比，前十个问题的α取0.25，接下来十个问题的α取0.50，最后十个问题的α取0.75。