遗传算法求解背包问题

《遗传算法求解背包问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法求解背包问题程序实现一、背包问题描述背包问题是著名的NP完备类困难问题,对这个问题的求解前人已经研究出了不少的经典的方法,对该问题确实能得到很好的结果。近年来蓬勃发展起来的遗传算法已被广泛地应用于优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制.本程序将遗传算法应用于背包问题。二、实验程序1、编程语言：C++2、开发环境：MicrosoftVisualStudi

2、o20053、程序整体流程：步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个可行的染色

3、体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

4、的vj′(k)第j位基因的值变为其第i位基因的值.3.3　检验该染色体的可行性,若可行则作为变异的结果;如不可行,重复3.2直至该染色体可行.123.4　事先定义变异概率pm,对经过杂交操作的中间个体进行变异操作:,如果r

5、并把它们同时放回,和步2选择操作中剩余的个体一起构成新一代种群v(k+1)={v1(k+1),v2(k+1),⋯,vM(k+1)}.步4终止检验如果达到最大进化代数maxgen则终止演化,否则置k:=k+1,转步2.4、程序流程图12程序流程图5、程序代码1）主程序代码：KnapsacksProblem.cpp文件#include"GAonKP.h"#includeusingnamespacestd;voidmain(){FILE*fp;CGAonKPgakp;intscale;//种

6、群规模doubleMaxWeight;//背包允许最大财宝质量doublepc;//杂交概率doublepm;//变异概率12intmaxgen;//最大进化代数charfilename[256];cout<<"遗传算法解决背包问题程序使用说明："<

7、大进化代数需自己给";cout<<"定，程序会提示输入"<

8、xt文件中"<>filename;if(filename[0]=='Y'){if(!(fp=fopen("example.txt","r"))){cout<<"请确认example.txt是否背删除了！"<