金甜甜_基于遗传算法求解背包问题

金甜甜_基于遗传算法求解背包问题内容摘要：

(l)编码，把问题的解转化成位串表示形式。 (2)定义适应性函数。 (3)确定遗传算法的各算子及参数，包括选择、交叉、变异方法，交叉率、变异率、群体容量、最大遗传代数等。 (4)随机初始化群体。 正文： 基于遗传算法的背包问题求解 5 (5)计算群体中每一个染色体的适应值。 (6)按照遗传操作形成下一代群体。 ①从当前群体中由事先设定好的选择方法选出两个染色体。 ②根据给定的交叉率，对选出的两个染色体进行交叉操作。 ③根据给定的变异率，对每个染 色体进行变异操作。 ④重复①、②、③步，直到新的一代群体被创建出来。 (7)判断新产生的群体是否能满足结束指标，如果满足，则算法结束，如果不满足，则返回步骤 (6)。 编码 按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立关系，即确定编码和解码运算。 编码就是将问题的解用一种码来表示，从而将问题的状态空间与 GA 的编码空间相对应，编码的选择是影响算法性能与效率的重要因素。 常用的编码方法有如下几种： ①二进制编码：二进制编码将问题空间的参数表示 为基于字符集 {0,1}构成的染色体位串，是最常用的一种编码方式。 ②大字符集编码 :除基于字符集 {0,1}的二进制编码之外，可以结合实际问题的特征采用 D 进制数或字符集来表示长度为 L 的位串。 ③序列编码：用排列法进行编码显得更为自然、合理。 ④实数编码：实数编码具精度高、大空间搜索的优点。 ⑤树编码：树编码是一种非固定常用编码模式，其表示空间是开放的。 在搜索过程中树可以自由生长，但是不便于形成更具有结构化和层次性的问题解，实际应用中往往可以加以限制。 ⑥自适应编码：实现选择合适的固定编码方式对潜在的遗传算法用户 来说是一个难题。 事实上，提出合适的编码同解决问题本身一样困难。 因此，许多用户认为既然要用遗传算法解决问题，为什么不让它同时调整编码呢 ?一些专家就采用了自适应编码 [11]。 适应度函数 适应度评价是通过适应度函数对个体质量的一种测量，是进化过程中自然的唯一依据。 因此适应度函数的选择至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。 一般而言，适应度函数是由目标函数变换而成的。 对目标函数值域的某种映射变换称为适应度的尺度变换。 适应度函数的设计主要满足以下条件： ①单值、连续、非负、最大化 :这 个条件是容易理解和实现的。 ②合理、一致性：要求适应度值反映对应解的优劣程度，这个条件的达成比较难以衡量。 正文： 基于遗传算法的背包问题求解 6 ③计算量小：适应度函数设计应尽可能简单，这样可以减小计算时间和空间上的复杂性，降低成本。 ④通用性强：适应度函数对具体问题应尽可能具有通用性，最好无需使用者改变适应度函数中的参数。 适应度函数的尺度变换有线性变换法、幕函数变换法、指数变换法 [10]。 遗传算子 标准的遗传算子 一般都包括选择、交叉和变异三种。 它们构成了遗传算法的核心，使得算法具有强大的搜索能力。 选择算 子 选择操作就是用来确定如何从父代种群中按照某种方法选取哪些个体遗传到下一代种群的遗传运算。 它是根据个体适应度函数值的大小正比于其被放入候选的概率的过程。 在备选集中按照一定的选择概率进行操作，这个概率取决于种群中个体的适应度及其分布。 其主要作用是避免了基因缺失，提高全局收敛性和计算效率。 选择算子可看作是种群空间到父体空间的随机映射，它按照某种准则或概率分布从当前种群中以高的概率选取那些好的个体组成不同的父体以供生成新的个体。 目前常用的选择策略有赌盘赌选择算子、排序选择算子、最优保存选择算子和锦标赛选择算子 等 [8]。 在遗传算法中，目前常用的选择机制有以下几种： ①适应度比例方法 适应度比例方法是目前遗传算法中最基本也是最常用的选择方法。 它也叫赌轮或蒙特卡罗选择。 在该方法中，各个个体的选择概率和其适应度值成比例。 设群体大小为 n，其中个体 i 的适应度值为 fi，则 i 被选择的概率 psi为： /si i ip f f  （ 41） 显然，概率 psi反映了个体 i 的适应度在整个群体的个体适应度总和中所占的比例。 个体适应度越大，其被选择的概率就越高，反之则被选 择的概率越低。 ②最佳个体保存方法 最佳个体保留进化策略的基本思想是当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。 具体操作过程是： 1)找出当前群体中适应度最高的个体和适应度最低的个体。 2)若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。 3)用迄今为止的最好个体替换掉当前群体中的最差个体。 ③期望值方法 在赌轮选择机制中，当个体数不太多时，依据产生的 随机数有可能会出现不正正文： 基于遗传算法的背包问题求解 7 确地反映个体适应度的选择，即存在统计误差。 也就是说，适应度高的个体也有可能被淘汰 (当然，适应度低的个体也有可能被选择 )，为克服这种误差，期望值方法用了如下思想。 1)计算群体中每个个体在下一代生存的期望数目： _/ / /i i iM f f f f n  （ 42） 2)若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望值数目减去 ；若不参与配对和交叉，则该个体的生存期望数目减去 1。 3)在 2)的两种情况下，若一个个体的期望值小于 0 时，则该个体不参与选择。 ④排序选择机制 排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。 排序选择机制的主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个体被选中的概率。 其具体操作过程是： 1)对群体中的所有个体按其适应度大小进行降序排序。 2)根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。 3)以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用比例选择的方法来产生下一 代群体。 是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。 交叉算子 交叉操作是遗传算法中最主要的遗传操作。 它是模仿自然界有性繁殖的基因重组过程，对两个父代个体进行基因操作，其作用在于把原有优良基因遗传到下一代种群中，并生成包含更复杂基因结构的新个体。 交叉算子可看作是父体空间到个体空间的随机映射， 它通常的作用方式是：随机地确定一个或多个分量位置为交叉点，由此将一对父体的两个个体分为有限个片断再以概率 cp （称为交叉概率）交换相应片断得到新的个体。 变异算子 在生物种群中总是存在着变异，变异指的是子代和父代之间具有某些不相似的现象，即因为存在着变异现象，所以子代和父代之间中总是不完全相同的。 变异是生物进化过程中不可缺少的，它为生物的进化和发展创造了条件。 在遗传算法中，变异是指父代染色体中的某些基因片，以相对较小的概率发生随机改变的操作过程。 所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。 在 遗传算法中使用变异算子主要有以下两个目的： ①改善遗传算法的局部搜索能力。 遗传算法使用交叉算子已经从全局的角度出正文： 基于遗传算法的背包问题求解 8 发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。 但仅使用交叉算子无法对搜索空间的细节进行局部搜索。 这时若再使用变异算子来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能力。 ②维持群体的多样性，防止出现早熟现象。 变异算子用新的基因值替换原有基因值，从而可以改变个体编码串的结构，维持群体的多样性，这样就有利于防止出现早熟现象。 参数控制 在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数。 这组参数在初始阶段或种群进化过程中需要合理地选择和控制。 主要包括种群规模 n、交叉概率 pc以及变异概率 pm。 群体规模 大种群含有较多模式，为遗传算法提供了足够的模式采样容量，可以改进 GA搜索的质量，防止早熟前收敛。 但大种群增加了个体适应性评价的计算量，从而使收敛速度降低。 交叉概率 交叉概率 pc控制着交叉算子的应用频率，在每一代新的种群中，需要对个体的染色体结构进行交叉操作。 交叉概率越高， 种群中新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高。 而交叉概率太低则可能导致搜索阻滞。 一般pc=—。 变异概率 变异操作是保持种群多样性的有效手段，交叉结束后，交配池中的全部个体位串上的每位等位基因按概率随机改变，因此每代中大约发生 n 次变异。 变异概率太小，可能使某些基因位过早丢失的信息无法恢复；而变异概率过高，则搜索将变成随机搜索。 一般取 pm=—。 算法结束条件控制 终止代数是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前种群中的最优个体作为所求问题的最优解输出。 由于遗传算法不同于传统的优化算法，它没有利用目标函数的梯度等信息，所以在遗传进化过程中，很难有明确的搜索终止准则。 常用的办法是预先给定算法的终止进化代数。 一般来说，预先给定算法的终止进化代数只能找到问题在给定时限内所能寻求的相对满意解，但不一定是问题的最优解或较高精度的近似解。 为了获得较高精度的近似解，通常可依据种群适应度的正文： 基于遗传算法的背包问题求解 9 稳定来适时调整终止进化代数的设置，或者在连续进化数代以后，如果解的适应度没有明显的改进，则终止进化过程。 终 止进化代数一般的取值范围是 1001000。 5 实现求解背包问题的遗传算法 0_1 背包问题中染色体的表示 用向量 X来表示染色体， X = ｛ x1， x2，„„， xn｝。 ， xi∈｛ 0,1｝， xi=1 表示物品 i 装入了背包， xi =0 表示物品 i 未装入背包。 每个染色体对应其当前装入背包的物品的总价值和总重量。 背包中物品的中价值代表了该物品的适应度。 程序中定义了这样的一个结构来表示染色体： typedef struct{ int Weight。 //染色体代表的物品的总重量 int Fitness。 //染色体代表的物品的价值（适应。