背包遗传算法
‘壹’ 我想知道运筹学中旅行背包问题。谢谢！
背包问题是一个非常有名的问题。可以这样叙述如下。假设有 n 件物品，记为 d1,d2,d3,…… dn。对于每一种物品di (1=<i=<n), 它的重量是wi ,而它的价值为 vi。现在要求用这 n 种物品的子集填满背包，使其总重量不超过给定的重量限制 TOT，并使得背包的价值尽可能高。
1.实数背包
物品可以一部分放在背包中，那么直接贪心就行了，把物品按性价比(v[i]/w[i])升序放入即为最优解。
复杂度O(n+nlogn)
2.整数背包
物品只能整个放入背包，不允许拆开放，用动态规划求解。
dp[i,j]表示前i个物品放入容量为j的背包中可以得到的最优解。
状态转移方程：dp[i,j]=max{dp[i-1,j],dp[i-1,j-w[i]]+v[i]}
复杂度O(nm)
3.多重背包
与1、2不同，这里有k个背包，每个背包有不同的容量，其它一样。
没什么好办法，只能搜索。
对于每个物品i，枚举它能被放在背包j，也可以不放物品i。
复杂度O(kn)
可以针对不同的题目采取不同的剪枝。
背包问题数学模型为(由于输入问题,下标很难输入规范,如c1中1是下标,请注意)
maxZ=c1x1+c2x2+...+cnxn
w1x1+w2x2+...+wnxn<=W
xi>=0,且为整数,i=1,2,...,n
式中：
ck为第k种物品的单位价值，wk是第k种物品的单位重量或体积，W是背包的重量或体积限制。
动态规划的有关要素如下:
阶段k：第k次装载第k种物品（k=1,2,…,n）
状态变量sk：第k次装载时背包还可以装载的重量(或体积)
决策变量xk：第k次装载第k种物品的件数
决策允许集合：Dk(sk)={dk|0 xksk/wk，xk为整数}
状态转移方程：sk+1=sk－wkxk
阶段指标：vk=ckxk
一般来说，用来解决背包问题的方法有递归法和贪心法等，但用这两中方法来解决背包问题都有其不可避免的缺点，递归法虽能遍历搜索空间，找到最优解，但由于此问题的解的空间是以2的N级增长的，所以它只适用于解决小规模的背包问题，而贪心法又很难真正找到最优解，此方法找到的最优解往往与真正的最优解相差很远。而遗传算法作为一种随机的优化与搜索方法，具有良好的并行性，而且遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因此适用于任何规模。遗传算法的高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性。
（如果你是需要计算机编程序的话，答案内容就更多些，现在不晓得你应用背包问题做什么呢）
‘贰’ 如何用遗传算法求解多重背包问题
遗传算法将目标函数转换为适应度函数，评估，复制，交叉，变异种群中的个体，并从中选出适应性最强的个体，算法的最优解就是这个个体。具体流程是：1.初始种群的产生。2.适应度函数的构造。3.选择和繁殖。4.终止条件。
‘叁’ 遗传算法--GA
遗传算法（GA）属于 人工智能启发式算法 ，启发式算法的目标就是 寻找原始问题的最优解 ，该算法的定义为
人类通过直观常识和生活经验，设计出一种以搜索最优解为目的，通过仿真大自然规律的算法，该算法在可以在接受的花销（计算时间和存储空间）范围内找到问题实例的一个可行解，且该可行解和真实最优解的误差一般不可以被估计
当下主要有的启发式算法包括 遗传算法、退火法，蚁群算法、人工神经网络等 ，这篇文章主要介绍遗传算法
遗传算法的基本原理是模拟达尔文进化论 "物竞天择，适者生存" 的自然法则，其核心思想为
（1）将原始问题的参数，抽象为基因编码
（2）将原始问题的可行解，抽象为基因排列的染色体组合
（3）将原始问题的解集规模，抽象为一定数量染色体组成的种群
（4）寻找可行解的过程，抽象为种群的进化过程（染色体选择、交叉、变异等）
（5）比较可行解的优劣，抽象为量化比较不同种群对当前环境的适应程度
（6）逼近最优解的过程，抽象为淘汰适应度差的种群，保留适应度高的种群进行下一次进化
（7）问题的最优解，抽象为经过多次进化后，最终生存下来的精英种群
理论上，通过有限次种群进化，生存下来的种群都是 精英染色体 ，是最适合当前环境条件的种群，也就可以无限逼近原始问题的最优解
相关生物学术语：
为了大家更好了解遗传算法，在此之前先简单介绍一下相关生物学术语，大家了解一下即可。
基因型(genotype)：性状染色体的内部表现；
表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；
进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
适应度(fitness)：度量某个物种对于生存环境的适应程度。
选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
复制(reproction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
解码(decoding)：基因型到表现型的映射。
个体（indivial）：指染色体带有特征的实体；
种群（population）：个体的集合，该集合内个体数称为种群
大体实现过程
遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。 遗传算法的实现过程实际上就像自然界的进化过程那样。
基本遗传算法概述
1.[开始]生成n个染色体的随机群体（适合该问题的解决方案）
2.[适应度]评估群体中每个染色体x的适应度f（x）
3.[新种群]通过重复以下来创建新种群直到新种群完成的步骤
3.1 [选择]根据种群的适合度选择两个亲本染色体（更好的适应性，更大的选择机会）
3.2 [交叉]以交叉概率跨越父母形成新的后代（儿童） ）。如果没有进行交叉，后代就是父母的确切副本。
3.3 [突变]突变概率突变每个基因座（染色体中的位置）的新后代。
4.[接受]在新种群中放置新后代[替换]使用新生成的种群进一步运行算法
5.[测试]如果满足结束条件，则停止并返回当前种群中的最佳解
6。[循环]转到步骤2
影响GA的因素
从遗传算法概述可以看出，交叉和变异是遗传算法中最重要的部分。性能主要受这两个因素的影响。在我们解释有关交叉和变异的更多信息之前，我们将给出一些有关染色体的信息。
染色体编码
染色体应该以某种方式包含它所代表的解决方案的信息。最常用的编码方式是二进制字符串。然后染色体看起来像这样：
每个染色体由二进制字符串表示。字符串中的每个位都可以表示解决方案的一些特征。另一种可能性是整个字符串可以表示一个数字 - 这已在基本的GA小程序中使用。当然，还有许多其他的编码方式。编码主要取决于解决的问题。例如，可以直接编码整数或实数，有时对某些排列等进行编码很有用。
染色体交叉
在我们确定了将使用的编码之后，我们可以继续进行交叉操作。 Crossover对来自亲本染色体的选定基因进行操作并产生新的后代。最简单的方法是随机选择一些交叉点，并在此点之前从第一个父项复制所有内容，然后在交叉点之后复制另一个父交叉点之后的所有内容。交叉可以说明如下:( |是交叉点）：
还有其他方法可以进行交叉，例如我们可以选择更多的交叉点。交叉可能非常复杂，主要取决于染色体的编码。针对特定问题进行的特定交叉可以改善遗传算法的性能。
4.染色体突变
在执行交叉之后，发生突变。突变旨在防止群体中的所有解决方案落入解决问题的局部最优中。突变操作随机改变由交叉引起的后代。在二进制编码的情况下，我们可以将一些随机选择的位从1切换到0或从0切换到1.突变可以如下所示：
突变（以及交叉）技术主要取决于染色体的编码。例如，当我们编码排列时，可以将突变作为两个基因的交换来进行。
GA的参数
1.交叉和突变概率
GA有两个基本参数 - 交叉概率和变异概率。
交叉概率 ：交叉的频率。如果没有交叉，后代就是父母的精确副本。如果存在交叉，则后代由父母染色体的部分组成。如果交叉概率为100％，那么所有后代都是由交叉产生的。如果它是0％，那么全新一代都是从旧种群的染色体的精确拷贝制成的（但这并不意味着新一代是相同的！）。交叉是希望新染色体将包含旧染色体的良好部分，因此新染色体将更好。但是，将旧人口的一部分留给下一代是好的。
突变概率 ：染色体部分突变的频率。如果没有突变，则在交叉（或直接复制）后立即生成后代而不进行任何更改。如果进行突变，则改变染色体的一个或多个部分。如果突变概率为100％，则整个染色体发生变化，如果是0％，则没有变化。突变通常会阻止GA陷入局部极端。突变不应该经常发生，因为GA实际上会改变为随机搜索。
2.其他参数
种群规模 ：种群中有多少染色体（一代）。如果染色体太少，GA几乎没有可能进行交叉，只探索了一小部分搜索空间。另一方面，如果染色体太多，GA会减慢。研究表明，经过一定的限制（主要取决于编码和问题），使用非常大的种群是没有用的，因为它不能比中等规模的种群更快地解决问题。
3 选择
正如您从GA概述中已经知道的那样，从群体中选择染色体作为交叉的父母。问题是如何选择这些染色体。根据达尔文的进化论，最好的进化能够创造出新的后代。选择最佳染色体的方法有很多种。例如轮盘赌选择，Boltzman选择，锦标赛选择，等级选择，稳态选择和其他一些选择。
1.轮盘赌选择
父母根据他们的健康状况选择。染色体越好，它们被选择的机会就越多。想象一下轮盘赌轮，人口中的所有染色体都放在那里。轮盘中截面的大小与每条染色体的适应度函数的值成比例 - 值越大，截面越大。有关示例，请参见下图。
轮盘赌中放入一块大理石，并选择停止的染色体。显然，具有较大适应值的染色体将被选择更多次。
该过程可以通过以下算法来描述。
[Sum]计算总体中所有染色体拟合度的总和 - 总和S.
[Select]从区间（0，S）-r生成随机数。
[循环]遍历总体并从0 - 总和中求和。当总和s大于r时，停止并返回您所在的染色体。当然，对于每个群体，步骤1仅执行一次。
2.排名选择
当健身值之间存在很大差异时，先前的选择类型会出现问题。例如，如果最佳染色体适应度是所有拟合度总和的90％，那么其他染色体将很少被选择的机会。等级选择首先对群体进行排序，然后每个染色体接收由该等级确定的适合度值。最差的将是健身1，第二个最差的2等等，最好的将具有适应度N（人口中的染色体数量）。您可以在下面的图片中看到，在更改适应性与排名确定的数字后情况如何变化。
排名前的情况（适合度图）
排名后的情况（订单号图）
现在所有染色体都有机会被选中。然而，这种方法会导致收敛速度变慢，因为最好的染色体与其他染色体的差别不大。
3.稳态选择
这不是选择父母的特定方法。这种选择新种群的主要思想是染色体的很大一部分可以存活到下一代。稳态选择GA以下列方式工作。在每一代中，选择一些好的（具有更高适应性）染色体来创建新的后代。然后去除一些不好的（具有较低适合度）染色体并将新的后代放置在它们的位置。其余人口幸存下来。
4.精英
精英主义的想法已经被引入。当通过交叉和变异创建新的种群时，我们有很大的机会，我们将失去最好的染色体。精英主义是首先将最佳染色体（或少数最佳染色体）复制到新种群的方法的名称。其余人口以上述方式构建。精英主义可以迅速提高GA的性能，因为它可以防止丢失最佳找到的解决方案。
交叉(Crossover)和突变 (Mutation)
交叉和变异是GA的两个基本运算符。 GA的表现非常依赖于它们。运算符的类型和实现取决于编码以及问题。有多种方法可以执行交叉和变异。在本章中，我们将简要介绍一些如何执行多个编码的示例和建议。
1.二进制编码
交叉
单点交叉 - 选择一个交叉点，从第一个父项复制从染色体开始到交叉点的二进制字符串，其余从另一个父项复制
选择两点交叉 - 两个交叉点，从第一个父节点复制从染色体开始到第一个交叉点的二进制字符串，从第一个父节点复制从第一个交叉点到第二个交叉点的部分，其余的是再次从第一个父级复制
均匀交叉 - 从第一个父项或第二个父项中随机复制位
算术交叉 - 执行一些算术运算以产生新的后代
突变
位反转 - 选择的位被反转
2.置换编码
交叉
单点交叉 - 选择一个交叉点，将排列从第一个父项复制到交叉点，然后扫描另一个父项，如果该数字还没有在后代中，则添加它注意：还有更多方法如何在交叉点之后产生休息
(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)
变异
顺序更改 - 选择并交换两个数字
(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)
3.值编码
交叉
可以使用来自二进制编码的所有交叉
变异
添加一个小数字（用于实数值编码） - 将一个小数字添加到（或减去）所选值
（1.29 5.68 2.86 4.11 5.55）=>（1.29 5.68 2.73 4.22 5.55）
4.树编码
交叉
树交叉 - 在父母双方中选择一个交叉点，父母在该点被分割，交换点下面的部分被交换以产生新的后代
变异
更改运算符，数字 - 选定节点已更改
补充:
疑惑点：
初始种群是啥：
利用二进制（一般）表示最终解
例如：需要求解z=x^2+y^2的最大值，x={1，5，3，8}，y={5，4，0，6}
用六位二进制数表示由x，y组成的解，例如：001100 表示x=1，y=4
001100 称为一条基因序列，表示的是该问题的一种解决 方案
种群是包含多个基因序列（解决方案/个体）的集合
适应度函数是啥，有什么作用：
适应度函数可以理解成“ 游戏 规则”，如果问题较为复杂，需要自定义适应度函数，说明如何区分优秀与不优秀的个体; 如果问题比较简单，例如上述求最大值的问题，则直接用此函数式作为适应度函数即可。作用：评定个体的优劣程度，从而决定其遗传机会的大小。
怎么选择：
定义“适者生存不适者淘汰”的规则，例如：定义适应度高的被选择的概率更大
怎么交叉：
利用循环，遍历种群中的每个个体，挑选另一个体进行交叉。例如，通过遍历为基因序列A挑选出B配对，则取A的前半部分，B的后半部分，组合成新的个体（基因序列）C
如何变异：
随机挑选基因序列上的某一位置，进行0-1互换
建议 GA的参数
如果您决定实施遗传算法，本章应该为您提供一些基本建议。这些建议非常笼统。您可能希望尝试使用自己的GA来解决特定问题，因为没有一般理论可以帮助您针对任何问题调整GA参数。
建议通常是对GA的经验研究的结果，这些研究通常仅在二进制编码上进行。
交叉率
交叉率一般应高，约为80％-95％。 （但是有些结果表明，对于某些问题，交叉率约为60％是最好的。）
突变率
另一方面，突变率应该非常低。最佳利率似乎约为0.5％-1％。
人口规模
可能令人惊讶的是，非常大的人口规模通常不会改善GA的性能（从找到解决方案的速度的意义上说）。良好的人口规模约为20-30，但有时大小为50-100是最好的。一些研究还表明，最佳种群规模取决于编码字符串（染色体）的大小。这意味着如果你有32位染色体，那么人口应该高于16位染色体。
选择
可以使用基本的轮盘赌选择，但有时排名选择可以更好。查看有关选择优缺点的章节。还有一些更复杂的方法可以在GA运行期间更改选择参数。基本上，这些表现类似于模拟退火。如果您不使用其他方法来保存最佳找到的解决方案，则应确保使用精英主义。您也可以尝试稳态选择。
编码
编码取决于问题以及问题实例的大小。查看有关编码的章节以获取一些建议或查看其他资源。
交叉和变异
运算符取决于所选的编码和问题。查看有关操作员的章节以获取一些建议。您还可以查看其他网站。
搜索空间
如果我们正在解决问题，我们通常会寻找一些最好的解决方案。所有可行解决方案的空间（所需解决方案所在的解决方案集）称为搜索空间（也称为状态空间）。搜索空间中的每个点代表一种可能的解决方案。每个可能的解决方案可以通过其对问题的值（或适应度）进行“标记”。通过GA，我们在众多可能的解决方案中寻找最佳解决方案 - 以搜索空间中的一个点为代表。然后寻找解决方案等于在搜索空间中寻找一些极值（最小值或最大值）。有时可以很好地定义搜索空间，但通常我们只知道搜索空间中的几个点。在使用遗传算法的过程中，随着进化的进行，寻找解决方案的过程会产生其他点（可能的解决方案）。
问题是搜索可能非常复杂。人们可能不知道在哪里寻找解决方案或从哪里开始。有许多方法可用于寻找合适的解决方案，但这些方法不一定能提供最佳解决方案。这些方法中的一些是爬山，禁忌搜索，模拟退火和遗传算法。通过这些方法找到的解决方案通常被认为是很好的解决方案，因为通常不可能证明最佳方案。
NP-hard Problems
NP问题是一类无法用“传统”方式解决的问题。我们可以快速应用许多任务（多项式）算法。还存在一些无法通过算法解决的问题。有很多重要问题很难找到解决方案，但是一旦有了解决方案，就很容易检查解决方案。这一事实导致了NP完全问题。 NP代表非确定性多项式，它意味着可以“猜测”解决方案（通过一些非确定性算法），然后检查它。如果我们有一台猜测机器，我们或许可以在合理的时间内找到解决方案。为简单起见，研究NP完全问题仅限于答案可以是或否的问题。由于存在输出复杂的任务，因此引入了一类称为NP难问题的问题。这个类并不像NP完全问题那样受限。 NP问题的一个特征是，可以使用一个简单的算法，可能是第一眼看到的，可用于找到可用的解决方案。但是这种方法通常提供了许多可能的解决方案 - 只是尝试所有可能的解决方案是非常缓慢的过程（例如O（2 ^ n））。对于这些类型问题的更大的实例，这种方法根本不可用。今天没有人知道是否存在一些更快的算法来提供NP问题的确切答案。对于研究人员来说，发现这样的算法仍然是一项重大任务（也许你！:-)）。今天许多人认为这种算法不存在，因此他们正在寻找替代方法。替代方法的一个例子是遗传算法。 NP问题的例子是可满足性问题，旅行商问题或背包问题。可以获得NP问题汇编。
参考：
https://www.jianshu.com/p/ae5157c26af9
https://www.jianshu.com/p/b36b520bd187
‘肆’ 遗传算法求解背包问题的程序
1楼的不是遗传算法吧！
刚好做过这个遗传算法解背包问题的论文，给你回答啦~~独家哦，分数要给偶~~
1、程序开发环境
开发环境：Visual C++6.0 (把Fortran程序改为VC)
操作系统：Windows 2003 Professional
2、程序性能对比
运行时间与加速比（如表1所示）
进程数p（个） 1 2 4
运行时间t（秒） 129s 78s 38s
加速比s 1.65 3.38
表1、运行时间与加速比
3、程序运行结果：
实例数据：
假设物体的重量Weight、物体的收益Profit和背包的容量Contain 分别为：
Weight={ 80，82，85，70，72， 70，66，50，55，25 ，
50，55，40，48，50， 32，22，60，30，32 ，
40，38，35，32，25， 28，30，22，50，30 ，
45，30，60，50，20 ， 65，20，25，30，10 ，
20，25，15，10，10 ， 10，4， 4， 2， 1 }
Profit={ 220，208，198，192，180， 180，165，162，160，158，
155，130，125，122，120 ， 118，115，110，105，101，
100，100，98， 96， 95， 90， 88， 82， 80， 77 ，
75， 73， 72， 70， 69， 66， 65， 63， 60， 58，
56， 50， 30， 20， 15， 10， 8， 5， 3， 1}
Contain=1000，
如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大?
传统的算法（动态规划、递归回溯法和贪心算法所得结果：
总价值为3077 , 总重量为999。
2001年张铃，张钹教授在计算机学报上发表的《佳点集遗传算法》所得结果
总价值为3103, 总重量为1000。
我们算法所得结果： 总价值为3103, 总重量为1000。
我们所求得最优解的个体分配情况为：
11010 10111 10110 11011 01111 11101 00001 01001 10000
01000
算法 最大迭代次数 总价值为 总重量为
传统的算法 400 3077 999
佳点集算法 70 3103 1000
遗传算法 75 3103 1000
// knapsack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>
// 重要常量参数
#define popsize 200 //种群的规模
#define pc 0.618 //杂交概率
#define pm 0.03 //变异概率
#define lchrom 50 //染色体长度
#define maxgen 1000 //最大进化代数
struct population
{
unsigned int chrom[lchrom]; //染色体
double weight; //背包重量
double fitness; //适应度
unsigned int parent1,parent2,cross; //双亲、交叉点
};
//新生代种群、父代种群
struct population oldpop[popsize],newpop[popsize];
//背包问题中物体重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain;
//种群的总适应度、最小、最大、平均适应度
double sumfitness,minfitness,maxfitness,avgfitness;
//计算适应度时使用的 惩罚函数系数
double alpha;
//一个种群中最大和最小适应度的个体
int minpop,maxpop;
/* 读入背包信息,并且计算惩罚函数系数 */
void read_infor()
{
FILE *fp;
int j;
//获取背包问题信息文件
if ((fp=fopen("knapsack.txt","r"))==NULL)
{
//读取文件失败
AfxMessageBox("The file is not found",MB_OK,NULL);
return;
}
//读入物体收益信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&profit[j]);
}
//读入物体重量信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&weight[j]);
}
//读入背包容量
fscanf(fp,"%d",&contain);
fclose(fp);
}
//根据计算的个体重量,判断此个体是否该留在群体中
double cal_weight(unsigned int *chr)
{
int j;
double pop_weight;//背包重量
pop_weight=0;
for (j=0;j<lchrom;j++)
{
pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}
return pop_weight;
}
/* 种群中个体适应度计算*/
double cal_fit(unsigned int *chr)
{
int j;
double pop_profit;//适应度
pop_profit=0;
// pop_weight=0;
for (j=0;j<lchrom;j++)
{
pop_profit=pop_profit+(*chr)*profit[j];
// pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}
return pop_profit;
}
/* 群体适应度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
int i;
double tmp_fit;
sumfitness=pop[0].fitness;
minfitness=pop[0].fitness;
minpop=0;
maxfitness=pop[0].fitness;
maxpop=0;
for (i=1;i<popsize;i++)
{
//计算种群的总适应度
sumfitness=sumfitness+pop[i].fitness;
tmp_fit=pop[i].fitness;
//选择种群中最大适应度的个体
if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
{
maxfitness=pop[i].fitness;
maxpop=i;
}
//选择种群中最小适应度的个体
if (tmp_fit<minfitness)
{
minfitness=pop[i].fitness;
minpop=i;
}
//计算平均适应度
avgfitness=sumfitness/(float)popsize;
}
// printf("\nthe max pop = %d;",maxpop);
// printf("\nthe min pop = %d;",minpop);
// printf("\nthe sumfitness = %f\n",sumfitness);
}
//报告种群信息
void report(struct population *pop,int gen)
{
int j;
int pop_weight=0;
printf("the generation is %d.\n",gen); //输出种群的代数
//输出种群中最大适应度个体的染色体信息
printf("The population's chrom is: \n");
for (j=0;j<lchrom;j++)
{
if (j%5==0)
{ printf(" ");}
printf("%1d",pop[maxpop].chrom[j]);
}
//输出群体中最大适应度
printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness);
printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight);
}
/* 生成初始种群 */
void initpop()
{
int i,j,ispop;
double tmpWeight;
//变量用于判断是否为满足条件的个体
ispop=false;
//生成popsize个种群个体
for(i=0;i<popsize;i++)
{
while (!ispop)
{
for(j=0;j<lchrom;j++)
{
oldpop[i].chrom[j]=rand()%2; //随机生成个体的染色体
oldpop[i].parent1=0; //双亲
oldpop[i].parent2=0;
oldpop[i].cross=0; //交叉点
}
//选择重量小于背包容量的个体,即满足条件
tmpWeight=cal_weight(oldpop[i].chrom);
if (tmpWeight<=contain)
{
oldpop[i].fitness=cal_fit(oldpop[i].chrom);
oldpop[i].weight=tmpWeight;
oldpop[i].parent1=0;
oldpop[i].parent2=0;
oldpop[i].cross=0;
ispop=true;
}
}
//此个体可以加入到种群中
ispop=false;
}
}
/* 遗传操作 */
//概率选择试验
int execise(double probability)
{
double pp;
//如果生成随机数大于相应的概率则返回真，否则试验不成功
pp=(double)(rand()%20001/20000.0);
if (pp<=probability) return 1;
return 0;
}
// 选择进行交叉操作的个体
int selection(int pop)
{
double wheel_pos,rand_Number,partsum;
int parent;
//赌轮法选择
rand_Number=(rand()%2001)/2000.0;
wheel_pos=rand_Number*sumfitness; //赌轮大小
partsum=0;
parent=0;
do{
partsum=partsum+oldpop[parent].fitness;
parent=parent+1;
} while (partsum<wheel_pos && parent<popsize);
return parent-1;
}
/* 交叉操作 */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
int j,cross_pos;
if (execise(pc))
{
//生成交叉位置0,1,...(lchrom-2)
cross_pos=rand()%(lchrom-1);
}
else cross_pos=lchrom-1;
for (j=0;j<=cross_pos;j++)
{ //保留复制；
//包括在概率选择不成功时，父体完全保留
newpop[i].chrom[j]=parent1[j];
}
for(j=cross_pos+1;j<=(lchrom-1);j++)
{
//从交叉点开始交叉
newpop[i].chrom[j]=parent2[j];
}
//记录交叉位置
newpop[i].cross=cross_pos;
return 1;
}
/* 变异操作 */
int mutation(unsigned int alleles)
{
if (execise(pm))
{
if (alleles)
alleles=0;
else alleles=1;
}
//返回变异值，或者返回原值
return alleles;
}
/* 群体更新 */
void generation()
{
unsigned int i,j,mate1,mate2;
double tmpWeight;
int ispop;//记录是否是符合条件的个体
i=0;
while (i<popsize)
{
ispop=false;
while (!ispop)
{
//选择
mate1=selection(i);
mate2=selection(i+1);
//交叉
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);
//变异
for (j=0;j<lchrom;j++)
{
newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);
}
//选择重量小于背包容量的个体,即满足条件
tmpWeight=cal_weight(newpop[i].chrom);
if (tmpWeight<=contain)
{
newpop[i].fitness=cal_fit(newpop[i].chrom);
newpop[i].weight=tmpWeight;
newpop[i].parent1=mate1;
newpop[i].parent2=mate2;
ispop=true;
}
}
//此个体可以加入到种群中
i=i+1;
}
}
void main(int argc, char* argv[])
{
int gen,oldmaxpop,k;
double oldmax;
read_infor();//读入背包信息
gen=0;
srand( (unsigned)time( NULL ) );//置随机种子
initpop();
memcpy(&newpop,&oldpop,popsize*sizeof(struct population));
statistics(newpop);//统计新生种群的信息
report(newpop,gen);
while(gen<maxgen)
{
gen=gen+1;
if (gen%100==0)
{
srand( (unsigned)time( NULL ) );//置随机种子
}
oldmax=maxfitness;
oldmaxpop=maxpop;
generation();
statistics(newpop); //统计新生代种群信息
//如果新生代种群中个体的最大适应度小于老一代种群
//个体的最大适应度，则保存老一代种群个体的最大适应度
//否则报告新生代的最大适应度
if (maxfitness<oldmax)
{
for(k=0;k<lchrom;k++)
newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];
newpop[minpop].fitness=oldpop[oldmaxpop].fitness;
newpop[minpop].parent1=oldpop[oldmaxpop].parent1;
newpop[minpop].parent2=oldpop[oldmaxpop].parent2;
newpop[minpop].cross=oldpop[oldmaxpop].cross;
statistics(newpop);
}
else if (maxfitness>oldmax)
{
report(newpop,gen);
}
//保存新生代种群的信息到老一代种群信息空间
memcpy(&oldpop,&newpop,popsize*sizeof(struct population));
}
printf("It is over.");
getch();
}
‘伍’ c语言中遗传算法的种群的适应度是什么
种群适应度就是演化的目标啊，比如说01背包问题，一个背包中所放物品的价值就是适应度，通过不断的变异交叉，适应度会发生改变，每次只选出适应度更高的个体就好了
‘陆’ 如何通俗易懂地解释遗传算法
遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。
我们都知道一个种群，通过长时间的繁衍，种群的基因会向着更适应环境的趋势进化，牛B个体的基因被保留，后代越来越多，适应能力低个体的基因被淘汰，后代越来越少。经过几代的繁衍进化，留下来的少数个体，就是相对能力最强的个体了。
那么在解决一些问题的时候，我们能不能学习这样的思想，比如先随机创造很多很多的解，然后找一个靠谱的评价体系，去筛选比较好的解，再用这些好的解像生小宝宝一样生一堆可能更好的解，然后再筛再生，反复弄个几代，得到的说不定就是近似最优解哟
说干就干，有一个经典组合问题叫“背包问题”，我们拿这种思路来试试
“背包问题（Knapsack Problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。”
这个问题的衍生简化问题“0-1背包问题” 增加了限制条件：每件物品只有一件，可以选择放或者不放，更适合我们来举例
这样的问题如果数量少，当然最好选择穷举法
比如一共3件商品，用0表示不取，1表示取，那么就一共有
000 001 010
011 100 101
110 111
这样方案，然后让计算机去累加和，与重量上限比较，留下来的解里取最大即可。
‘柒’ 遗传算法-总结
最近在做遗传算法的项目，简单记录一下。
遗传算法是模拟自然界生物进化机制的一种算法，在寻优过程中有用的保留无用的去除。包括3个基本的遗传算子：选择（selection）、交叉（crossover）和变异（mutation）。遗传操作的效果与上述3个遗传算子所取的操作概率、编码方法、群体大小、初始群体，以及适应度函数的设定密切相关。
1、种群初始化
popsize 种群大小，一般为20-100，太小会降低群体的多样性，导致早熟；较大会影响运行效率；迭代次数一般100-500；交叉概率：0.4-0.99，太小会破坏群体的优良模式；变异概率：0.001-0.1，太大搜索趋于随机。编码包括实数编码和二进制编码，可以参考遗传算法的几个经典问题，TSP、背包问题、车间调度问题。
2、选择
目的是把优化个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代，我大部分采用了轮盘赌的方法。具体可参考 http://my.oschina.net/u/1412321/blog/192454 轮盘赌方法各个个体的选择概率和其适应值成比例，个体适应值越大，被选择的概率也越高，反之亦然。在实际问题中，经常需要最小值作为最优解，有以下几种方法进行转换
a、0-1之间的数据，可以用1-该数值，则最小值与最大值互换；
b、 求倒数；
c、求相反数；
以上几种方法均可以将最大值变为最小值，最小值变为最大值，便于利用轮盘赌选择最优个体，根据实际情况来确定。
3、交叉
交叉即将两个父代个体的部分结构加以替换重组而生成新个体的操作，通过交叉，遗传算法的搜索能力得以飞跃提高。根据编码方法的不同，可以有以下的算法：
a、实值重组
离散重组、中间重组、线性重组、扩展线性重组
b、二进制交叉
单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉
4、变异
基本步骤：对群中所有个体以事先设定的变异概率判断是否进行变异；对进行变异的个体随机选择变异位进行变异。根据编码表示方法的不同，有实值变异和二进制变异
变异的目的：
a、使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部搜索能力可以加速向最优解收敛。显然该情况下变异概率应取较小值，否则接近最优解的积木块会因为变异遭到破坏。
b、使遗传算法可维持多样性，以防止未成熟收敛现象。此时收敛概率应取较大值。
变异概率一般取0.001-0.1。
5、终止条件
当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设代数一般为100-500。
6、其它
多变量：将多个变量依次连接
多目标：一种方法是转化为单目标，例如按大小进行排序，根据排序和进行选择，可以参考 https://blog.csdn.net/paulfeng20171114/article/details/82454310