遗传算法的0-1背包问题c语言

1、基于遗传算法得01背包问题得求解摘要: 一、前言组合优化问题得求解方法研究已经成为了当前众多科学关注得焦点，这不仅 在于其内在得复杂性有着重要得理论价值，同时也在于它们能在现实生活中广泛得应用。比如资源分配、投资决策、装载设汁、公交车调度等一系列得问题都可以归结到组合优化问题中来、但就是，往往山于问题得计算量远远超出了汁算机 在有效时间内得计算能力，使问题得求解变为异常得困难。尤其 对于NP完全问题,如何求解其最优解或就是近似最优解便成为科学得焦点之一、遗传算法已经成为组合优化问题得近似最优解得一把钥匙。它就是一种模拟生物进化过程得计算模型，作为一种新得全局优化搜索算法，它以其简单、鲁棒性 强

2、、适应并行处理以及应用 范用广等特点，奠定了作为 2 1世纪关键智能计算得 地位。背包问题就是一个典型得组合优化问题，在计算理论中属于NP-完全问题，其计算复杂度为，传统上采用动态规划来求解。设 w 订就是经营活动i所需要 得资源消耗,M就是所能提供得 资源总量，p 门就是人们经营活动i得到得利润或收益,则背包问题就就是在资源有限得条件下， 追求总得最大收益得资源有效分 配问题。二、问题描述背包问题(K n a p sack Problem)得一般提法就是：已知n个物品得重量(wei g ht)及其价值(或收 益profi t )分别为与，背包得容量(cont a in)假设设为，如何选 择哪

3、些物品装入背包可以使得在背 包得容量约束限制之内所装物品得价值最大？该问题得模型可以表示为下述 0/1整数规划模型： 目标函数：(*)式中为0 I决策变量，时表示将物品装入背包中，时则表示不将其装入背包中。三、求解背包问题得一般方法解决背包问题一般就是采取动态规划、递归回溯法与贪心方法、动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易得单阶段问题、对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策得搜索范用越小，求解也越容易。它得主要缺点就是用数值方法求解时会随着状态变量得个数呈指数级 得增长，往往对于求解背包问题得实际问题就是不现实得。遍历搜索空间,使用递归回溯法解决背包

4、问题得优点在于它算法思想简单，而且它能完全遍历搜索空间,肯定能找到问题得最优解；但就是山于此问题解得总组合数有个，因此，随着物件数n得增大，其解得空间将以级增长，当n大到一定程度上，用 此算法解决背包问题将就是不现实得。使用贪心方法求解时计算得复杂度降低了很多，但就是往往难以得到最优解,有时所得解与最优解相差其远。因此，我们可以探索使用遗传算法解决物件数较大得背包问题、四、遗传算法简介遗传算Genetic Algorithms, G A ）就是在19 75年首次山美国密西根大 学得D。J、Ho 11a nd 教授与她得同事们借鉴生物界达尔文得自然选择法则与孟德尔得遗传进化机制基础之上提出得、经

5、过近30年得研究、应用，遗传算法 已被广泛地应用于函数优化、机器人系统、神经网络学习 过程、模式识别、图象 处理、工业优化控制等领域。遗传算法就是将问题得每一个可能性解瞧作就是群体中得一个个体（染色体），并将每一个染色体编码成串得形式，再根据预定得LI标函数对每个个体进行 评价，给出一个适应值、算法 将根据适应度值进行它得寻优过程，遗传算法得寻优过程就是通过选择、朵交与变异三个遗传算子来具体实现得。它得搜索能力山选 择算子与杂交算子决定，变异算子则保证了算法能够搜索到问 题空间得尽可能多得点，从而使其具有搜索全局最优得能力。遗传算法得高效性与强壮性可FllHo 1 land提出得模式定理（Sc

6、hema Therein ）与隐式并行性得以解释、在遗传算法中，定义长度较短、低阶且适应值超过平均适应值得模式在群体中数LI得期望值按指数递增，这个结论称为遗传算法得基本定理、遗传算法就是通过定义长度短、确定位数少、适应度值高得模式得反复抽样、组合来寻找最佳点，称这些使 遗传算法有效工作得模式为积木块，就是遗传算法构造答案得基本 材料。但归根到底，要使遗传算法有效工作必须按照遗传算法得模式定理（或积木块假设）根 据 具体问题设讣合理得编码方案。在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群得大小、染色体长、交义率、变异率、最大进化代数等，这些参数对GA得性能都有很重 要得影响。在

7、试验中参数一般选取如下：种群大小N= 20-100 ,交叉概率二0。4? 0。9，变异概率二0. 0 010 o 1，最大进化代数 max gen =100 ? 50 0、遗传算法就是具有“生成+检测”得迭代过程得搜索算法。它得基本处理流程如图1所示。图1、遗传算法得基本流程遗传算法得基本流程描述如下：编码:将解空间得解数据进行二进制编码，表达为遗传空间得基因型串(即染 色体)结构数据，如将数据9编码为“ 1001 ” ；(2 )初始化种群：定义整数po p_size作为染色体得个数，弁且随机产生pop_ size个染色体作为初 始种群；(3 )评估种群中个体适应度：评价函数对种群中得每个染色

8、体 (ch r omos o me) 求得其个体适应度;(4 )选择:选择把当前群体中适应度较高得个体按某种规则或者模型遗传到下一代种群中，这里所用得规则就是：染色体在种群中被选择得可能性与其个体得适应度得大小成正比；交义:定义参数作为交义操作得概率，由选择得到得两个个体以概率交换各自得部分染色体,得到新得两个个体；(6 )变异:定义参数作为变异操作得概率，山 得到每个个体中得每个基因值都以概率进行变异;演化：经过选择、交义与变异操作，得到一个新得种群，对上述步骤经过给定得循环次数(maxgen)得种群演化，遗传算法终止。五、背包问题得遗传算法求解描述基于背包问题得模型(次)，我们设计了针对于

9、背包问题得染色体编码方法 ：将待求解得各量表示成长为得二进制字符串,j=i,2,n、表示物体j不放入 背包内，表示物体j放入背包内。例如：11 1 0011 0 0-0001 1 1代表一个解，它表 示将第 1、2、3、6、7?n-2,n-1, n 号物体放入背包中，其它得物体则不放入。根据遗传算法得基本流程，我们确定了求解背包问题得遗传算法：步骤1、初始化过程1确定种群规模popsize、杂交概率、变异概率、染色体长度1 c h r o m 及最大进化代数m ax g e n ;读入背包问题得相关信息，如每个物体得重量 weight j、每个物体得收益p r of i t j 与背包得容量c

10、o n tain,其中；取，其中表示0 1整数得均匀分布函数，即随机地主成数 0或1,生成得串 即可瞧为一 个染色体个体。若不满足模型(*)得约束条件，则拒绝接受，由1.2重新生成一个新得染色体个体chrom;如果产生得染色体可行，则接受它作为种群得一名成员，经过有限次得1、2抽样后，得到popsi z e个可行得染色体c h rom,形成新得种群。lo 4置种群得代数gen=0;步骤2、计算种群中个体适应度以及统计种群适应度情况2、1按照下列公式计算种群中个体适应度：khrom-lprofit! j * chronf jifw eight 工 profitj *chronf j - alph

11、a * (weight - contain) ifw eight containj-0公式(2)得下半部分即为适应度得惩罚函数，其中参数。2、2按公式(3)计算种群得总体适应度，并且按照排序得方法统计出种群中得最大、最小适应度得染色体个体，分别标i己为maxpo p、minp op;步骤3、选择操作生成一个随机数r a nd_Num b e r, 要求；按照赌轮法选择个体，赌轮法得算法描述如下：i nt select i o n()(i=0;/个体得编号sum =0;/ /部分个体适应度得累加与/根据随机数与群体得总适应度确定赌轮得位置wh e e l-pos=rand_Number*suf

12、i tness;whi 1 e sum w h e e 1 -p o s & i M a x gen侧结束种群得演化,否则转到步骤2。六、遗传算法求解得实现都邮憎pma辘都邮憎pma辘8000 alp h a;#d efine p mdefi no/ /最吹沸鹦觑模杂交进化代体长度概率讣算适应度时使用得惩罚函数系数1、遗传算法得主要参数背包信息：背包问题中物体重量、收益、背包容量int wei g ht 1c h r om, p r o fi t lehr o m,co n tain;(2)种群个体结构体染色体染色体u nsi g ned int c h rom 1 chrom ;doub 1

13、 e fit n es s ;适应度u nsig n ed int parent 1 , p a re n t2, c ros s ; 适应度；父代种群与新生代种群父代种群、新生代种群st r uc t pop u lat i o n oldp o ppops i z e ,newpoppopsize; / p op_size为 种群大小适应度信息种群得总适应度、最小、最大适应度d ou b 1 e sumf i t n essjninfi t ness,ma x f i t n ess; 一个种群中最大与最小适应度得个体编号i n t minp o p,m a xpop;3、主要函数说明、i

14、nt r ead i n for()功能:从文件k napsa c k.t x t中读出背包信息(物体重量、收益、背包容量)；参数:无；返回值:返回读取文件信息就是否正确；流程图现图2、图 2、re a d_inf o r() 流程图doubl e cal f it(unsig n e d i n t * chr)功能:种群中个体适应度计算；参数:un s i gned int *chr就是染色体个体得指针，根据指针所指向得染色体计算个体得适应度；返回值:染色体个体适应度得大小； 流程图现图3o适应度与总重量置0累加计算个体适应度与背包得总重量使用惩罚函数对个体 适应度进行处理返回个体适应度图

15、3、函数ca 1 _fi t得流程图 void s t a tistic s (struct po p u 1 a t ion * pop)功能:群体适应度得最大最小值以及其她信息；参数：s truct popula t io n * p o p 就是种群指针，根据指针所指向得种群信息统计群体适应度得信息；返回值:无；流程图:见图4、 v oid re p ort( s true t pop u 1 a t i on * p op,i nt g e n)功能:报告种群得适应度信息，尤其就是最大个体适应度、最大适应度个体得染色体信息；参数:st r uctpopulation *pop 就是种群

16、指针，根据指针所指向得种群报告群体适应度得信息，gen就是表示此种群所在得演化代数返回值:无； 流程图:见图5o计数器i=l图 4、函数 statis t ics得流程图返回i = i+1置最小适应度得编 计数器i=l图 4、函数 statis t ics得流程图返回i = i+1置最小适应度得编 号为i总适应度=总适应度+ 个体i得适应度最气 1n tj八输种群得代数gen输出最大适应度个体得柒色体信息chroni输出最大个体适应度max fitness图5、函数repo r t得流程图(5卜v oid in i t pop() 功能:生成初始种群;参数:无；返回值:无；流程图:见图6o(6

17、 卜 i nt ex e cise( d o u ble prob a bi 1 ity)功能:概率选择试验，以概率pro b ability做随机试验，判断就是否进行交义或变异操作；参数:doubl e probability为交义概率或变异概率返回值 试验就是否成功，0代表不试验成功，将不做交义或者变异操作，1代表试 验成功，即进行交叉或者变异操作；流程图:见图7图7、函数e xeci s e得流程图(7)、in t selec t io n (int p op)功能:在父代种群中选择个体，规则为适应度越大得个体被选择得概率越大参数：i nt p o p为父代种群；返回值:父体中被选择得个

18、体i；流程图:见图8、t2,i n t i)个体编号i=o,部分适应度之与partsum=O图8t2,i n t i)个体编号i=o,部分适应度之与partsum=O图8、函数selection得流程图c ross o ver( u n si g n ed int * p a r entn signe d in t *p a功能:两个父代个体在染色体得第i个位置进行交义，生成两个新个体;参数:u n s i gne d i n t * p a r entl,u n signed int * p a ren t 2分别为两个父代染色体指针，指针指向父代个体得染色体，i为新种群得个体编号； 返回值

19、:交义就是否成功;流程图：见图9o概率选择试验 成功随机生成交义位置cross_pos两个父代个体按照交 义位置进行交义，生 成新得两个个体保留两个父体成为新 种群中得个体图9、函数c r oss o ver得流程图(9)、int muta t ion(unsigne d i nt a lleles)功能根据变异概率进行变异操作；参数：u n s igned in t al 1 eles就是染色体上得基因型，在这里就就是0或1得 取值;返回值:变异后得基因型；流程图：见图10o1111进行变芹返回变异或者原值图 10、函数 mu t ation 得流程图(10)、v o id g e n er

20、 a t ion()功能:综合选择、交义、变异等操作，生成新得种群 ；参数:无;返回值:无;流程图：见图11、置个体编号i=0调用selection调用selection生成两个父体生成新得种群完毕调 11 crossover,交叉生成两个新个体对每个个体得居因调用mutation调 11 crossover,交叉生成两个新个体对每个个体得居因调用mutation进行变异置个体编号i=i+2图 11、函数 genera t i o n得流程图(11)、vo i d ma i n()功能:遗传算法得主函数;参数:无;返回值:无；流程图：见图11调用 statistics ()统计种群得适应度调用

21、 generation()生成新种群调用 调用 statistics ()统计种群得适应度调用 generation()生成新种群调用 report(),输出结果信息调用 statistics ()统复制旧种群得最大适应 度个体到新种群中最小 个体置演化代数2en=?en+I图1 2、主函数main得流程图七、成果说明1、程序开发环境开发环境：Vi sual C+6、0 （把 Fo r tr a n 程序改为 VC） 操作系统：Wi n dows 2003 Pr o f e ssi o nal2、程序性能对比运行时间与加速比（如表1所示）进程数P （个）124运行时间t （秒）129s78 s

22、38 s加速比slo 653.38表1、运行时间与加速比3.程序运行结果实例数据:假设物体得重量 Weigh t、物体得收益Profit与背包彳#容量Cont a in分别为:Wei g ht= 80,82, 8 5,7 0,72,7 0 ,66,50,55,25 ,5 0 ,5 5 ,4 0 ,4 8,5 0,3 2,22,6 0,30,3 2 ,40,3 8,3 5,32,25,2&3 0 ,2 2 ,5 0 ,30 ,4 5,3 0,60,50.20 ,65,20,25,30,10,1 80,165 ,162,160, 1 5&20,25,15,10,10 ,104 4, 2, 11 8

23、0,165 ,162,160, 1 5&Prof i t = 220,20 8 ,198,192, 1 8 0,155, 1 3 0,1 25J22, 1 20,11& 115J 10,1 05J01,1 0 0 , 1 0 0 ,9 8,96,9 5,90, 8 8,82, 80, 77 ,7 5, 73, 7 2, 70, 69,66, 65, 63, 6 0,5&56, 50, 30, 20, 15,10,8, 5,3,1Contain = 1000,如何选择哪些物品装入该背包可使得在背包得容量约束限制之内所装物品得总价值最大?传统得算法（动态规划、递归回溯法与贪心算法所得结果:总价值为

24、3 0 77 ,总重量为99 9 o200 1年张铃，张钱教授在计算机学报上发表得佳点集遗传算法所得结果我们算法所得结果:总价值为310 3、总重量为1 0 00、我们算法所得结果:总价值为3 103，总重量为1000c我们所求得最优解得个体分配情况为：1 10 1 0 1 0 111 1 0 110 1101 1 011 1 1 11101 00 0 0 10 1001 10000算法最大迭代次数总价值为总传统得算法40030779佳点集算法703 103遗传算法75310310 1000八、收获、体会与课题展望在本课题中，我们研究了如何用遗传算法求解组合优化问题中得背包问题、我们可以瞧出在

25、求解背包问题上显示了超出想象、良好得搜索能力，它具有收敛 快、搜索速度快得特点，在试验 中取得了比动态规划、递归回溯法与贪心法等更好得求解效果。然而在一般情况下，使用基本遗传算法解决背包问题时，得到问题得近似解也 不能满足逼近最优解得要求。如何改进基本遗传算法使它所求得得解逼近最优解 ,成为我们当前亟待解决得问题, 也就是我们将来得课题中所要研究得重要问题、 kn a psa c k 、cpp : Defin e s the e n try p oin t fo r the c o nsole appli c at i on/#mclude stdafic h ”Win elude AfxWi

26、n 。 h)#includc i nc 1 udc i n cl u de inclu d e (con io 、hinclud e 种群得规模/杂交概率最大进化代数种群得规模/杂交概率最大进化代数de f ine po p si z e 20 0define pcOo 618defin e pm 0 o 03define lchrom 50d e f inc maxg e ns t ni c tp op u 1 a t i o n背包重量unsigned int c hromfl c h r om;染色体 dou b le w e i g h t ;dou b le fit n ess; 适

27、应度u nsi g n e d i nt parcn tLp a re nt 2, cross; / 双亲、交叉点/新生代种群.父代种群s t r uct pop u lation oldp o p po p s ize?newpopp ops ize;背包问题中物体重量、收益、背包容量i n t we i ght lch r o mJ,prof i t lch r o m ,con tain;种群得总适应度、最小、最大、平均适应度do uble sum f i t nessjni n fit n ess,maxfi t nes s , a vgf i t n ess;/计算适应度时使用得惩罚

28、函数系数d o ubl e alph a ;/ 一个种群中最大与最小适应度得个体int minpo p jnaxpop;/*读入背包信息，并且计算惩罚函数系数* /voi d read_inf o r()oFI LE *fp:。i ntj;/获取背包问题信息文件4 f (fp=fopen( u knaps ack .txt H/r M )=NULL)(o /读取文件失败AAfxMe s sagcBox( u The no t found : MB_OKNULL); re t urn:町/读入物体收益信息for (j=O;j Ichr o m;j+)(f sea n f( fp d ： &pro

29、fitj);)O 读入物体重量信息f o r (j=0; j lch r om;j+)( fs c an f (f p& weigh t j);)O /读入背包容量f s c a nf (年 , %d l&contain);fcl o se( f p );根据计算得个体重量，判断此个体就是否该留在群体中do u ble c a 1 weig h t( u n s i gned in t *c h r )int j ;d o u ble p op_weig h t ; 背包重量pop_w e i g h t= 0 ;for (j =0;jl c h r om;j+)po p _weight=po

30、p_weight+(*chr) * weight|j;)return p o p_w e ig h t;)/*种群中个体适应度计算*/d ou b le c a Lfi t (u n si g ned i n t * c hr)int j ;doubl e p op_profit; 适应度po p _prof i t =0;/ pop_wc i ght=O;for (j= 0 ;j 1 chrom; j +)p o p _pr o f i t=pop_p r ofit+(* c hr)*p r of i t j;/Apop_w e i g ht=po p _weigh t +(* ch r )

31、 * w e ig h t j;c h r+;)ret u r n p op_prof i t;)/*群体适应度得最大最小值以及其她信息*/v o id sta t istics( s t ruct p opu 1 a tion *pop)4nt i;o d o u bl e tmp_ f it;nsum f itness=po p 0 卜 f i t n ess;切 i nf i t n e s s = p op 0 .f i t nes s ;minpop= 0 ; m a xfitness=pop 0 、 fi t ne s s;切 a x p o p =0;of o r ( i = 1

32、 ; i ma x fi t n e ss)& & (int)(tmp_ f it* 10)% 10=0) g zmaxfi t ness=po p i 。 f it n es s ;Amaxpo p =i;/选择种群中最小适应度得个体血 f (tmpAfit (minfitness) oo am i nfit n e ss= p op C 订。fit ness;g minpop=i;J/计算平均适应度Aavgf i t ne s s=sum f itness/(f 1 oat)po p si z e; / printf( H nthe max po p = %d; Mjnaxpop);/ q

33、 pri n tf( H nthe min pop = % d ; Mjnin p o p);/ p r i ntfAAnthe s u m fitness = %fn n ,sumfi t ncss);)/报告种群信息voi d report(struct po p ulat i o n * ge n )nt j ;int pop_wc i gh t =0;p r in t f C t h c gene ratio n i s %d ng e n); 输出种群得代数O /输出种群中最大适应度个体得染色体信息o pri n t f ( MThe p o pu 1 a lions

34、c hrom i s: n M);a for (j=O;j lchrom;j+)o if (j % 5=0)。 pri ntf (printf( % 1 cT, pop maxpop.chr o m j);)O 输出群体中最大适应度print f ( M nT h e popu 1 a t i o n t m ax fi t n e ss is %d M ,(i n t)pop maxpop f i tn e ss);p rintf(AnThe knapsack we i gh t is %d o n n M ,(in t )p o p maxpop.weigh t);/*生成初始种群*/v

35、oid i n it p op()(i n t ijjspop:d ou b I e t mpWe i ght;/变量用于判断就是否为满足条件得个体is p o p =f a Is e ;生成P opsiz e个种群个体f o r( i =0; i pare n t 2 =0;a ol d popi 、cross=0; / / 交叉点/ /选择重量小于背包容量得个体，即满足条件tmpWeight= c al_we i g h t(oldp o p 订、chrom);if (tmpWeigh t =c o n tain) (ao 1 dp o p i 、 fi t ne s s=ca 1 _fi

36、t( o ldpo p i、 c hr o m);aol d p op i .weight=tm p W e ig h t;a o 1 dpo p i 、 parent 1 =0;o I d pop 订。parent 2=0:a o 1 dpop i ? cro s s =0;g ispop=tr u e ;。/此个体可以加入到种群中isp o p=false;/*遗传操作*/概率选择试验int ex e ci se( double p rob abilit y )(d o uble p p ;/如果生成随机数大于相应得概率则返回真，否则试验不成功p p =(double)(ra n d()%

37、 2 0001/2000 0。0);if ( p p= p robab i lity) return 1 ;o r eturn 0;/选择进行交叉操作得个体int sele c tion( i n t pop)d o u b le w h e e l_pos,r and _Number.pa r tsum;int parent;赌轮法选择rand _Number=( r an d ()%20 0 1 )/2 0 0 0. 0 ;whe e I _p o s = r a nd_Numbe r *sumf i t n ess; / / 赌轮大小 par tsum=0; par e nt= 0 ;d

38、o a p a rtsu m=pa r tsu m+o 1 d p op parent、 fitness;a p a rent=p a rent+1; whi 1 e(part s urn (wheel.p os & parentpop s ize);return pa r ent 1;/* 交叉操作*/i n t crossove r (unsig n ed i n t * pare n t 1,unsig n ed i n t次 pare nt2jn t4n t j,c r o s s_ p o s;(e x e cis e ( p c )0 g 生成交叉位置 0,1八八(lchrom 2

39、)a cr o ss_ p os=r a nd()%( 1 chrom-1);吃 1 sc c r o ss_pos= 1 ch r om 1;dor(j=O;j=cross, p os;j+)保留复制；包括在概率选择不成功时，父体完全保留m ew p o p i o chrom j=par entl j ;4 o r(j=cross_pos+ 1 ; j =(lc h rom 1 ); j +)O 从交叉点开始交叉a n e wpo p io chrom j =pare n t2 j;/记录交叉位置new pop i 、cros s =cross_pos;return 1 ;)/*变异操作*

40、/int mutatio n (u n s igned int a 1 1 e les)(i f (exec i s e(pm)(o i f (alleles)o a 1 1 eles=0;e 1 se allel e s =1;)/返回变异值，或者返回原值r e tu r n all e les;)/*群体更新*/v oid g enera t i o n ()un s ign e d int ijmat e 1 ,ma te2;double t mpWeig h t ;in t i s pop;/记录就是否就是符合条件得个体i =0;whi I e (i pop s ize)(ispop=

41、f a Ise:whil e (! is p o p )0 (O /选择om a t e 1= s el e ction(i);omat e 2= s election(i+l);交叉c r ossove r (o I dpop mateljo chronioldp o p matc2o chr o mJ);o 变异fo r (j=O;jlch r om;j+ + )(n e wpopi .chromlj =niutation(newpop订.ch r om j);J选择重量小于背包容疑得个体，即满足条件tinpWe i gh t = c al_we ight( newp op ik c hrom);a if (t mpW