c语言等概率输出0和1,遗传算法0-1背包问题(c语言).doc

基于遗传算法的0-1背包问题的求解

摘要：

一、前言

组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。

遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。

背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， ，传统上采用动态规划来求解。设w[i]是经营活动 i 所需要的资源消耗，M是所能提供的资源总量，p[i]是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，

二、问题描述

背包问题( Knapsack Problem)的一般提法是：已知n个物品的重量(weight)及其价值(或收益profit)分别为和，背包的容量(contain)假设设为，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？

该问题的模型可以表示为下述0/1整数规划模型：

目标函数：

(*)

式中为0-1决策变量，时表示将物品装入背包中，时则表示不将其装入背包中。

三、求解背包问题的一般方法

解决背包问题一般是采取动态规划、递归回溯法和贪心方法。动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。它的主要缺点是用数值方法求解时会随着状态变量的个数呈指数级的增长，往往对于求解背包问题的实际问题是不现实的。

使用递归回溯法解决背包问题的优点在于它算法思想简单， 个，因此，随着物件数 n 的增大，其解的空间将以级增长，当 n 大到一定程度上，用此算法解决背包问题将是不现实的。

使用贪心方法求解时计算的复杂度降低了很多，但是往往难以得到最优解，有时所得解与最优解相差甚远。因此， ( Genetic Algorithms，GA) 是在1975 年首次由美国密西根大学的D。J。Holland 30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。

遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应度值进行它的寻优过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的尽可能多的点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理( Schema Therem) 和隐式并行性得以解释。，，。，，。，(或积木块假设) 根据具体问题设计合理的编码方案。

，，，GA 的性能都有很重要的影响。N= 20~100 ， = 0.4 ~0.9 ， = 0.001~0.1 ，axgen = 100~500。

遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图1所示。

图1、遗传算法的基本流程

遗传算法的基本流程描述如下：

(1)编码：将解空间的解数据进行二进制编码，表达为遗传空间的基因型串(即染色体)结构数据，如将数据9编码为“1001”；

(2)初始化种群：定义整数pop_size作为染色体的个数，并且随机产生pop_size个染色体作为初始种群；

(3)评估种群中个体适应度：评价函数对种群中的每个染色体(chromosome)求得其个体适应度；

(4)选择：选择把当前群体中适应度较高的个体按某种规则或者模型遗传到下一代种群中，这里所用的规则是：染色体在种群中被选择的可能性与其个体的适应度的大小成正比；

(5)交叉：定义参数作为交叉操作的概率，由(4)选择得到的两个个体以概率交换各自的部分染色体，得到新的两个个体；

(6)变异：定义参数作为变异操作的概率，由(5)得到每个个体中的每个基因值都以概率进行变异；

(7)演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经过给定的循环次数(maxgen)的种群演化，遗传算法终止。

五、背包问题的遗传算法求解描述

基于背包问题的模型(*)，我们设计了针对于背包问题的染色体编码方法