量子免疫算法的改进及在组合优化问题中的应用 第2页
考虑到量子免疫算法的应用对象主要是NP类问题，而这类问题在规模较小时一般易于求解，容易发现局部条件下的求解规律。因此，在获取疫苗时，既可以根据问题的特征来构造疫苗，也可以在分析需求解问题的基础上降低原问题的规模，增设局部条件来简化问题，用简化后的问题来作为选取疫苗的一种途径。同时，由于每个疫苗都是通过某一局部信息来探求全局最优解，所以没有必要对每个疫苗都做到精确无误。因此可以根据问题的特征，对原问题选用一些迭代优化算法来提取疫苗[6][7]。
由于量子遗传算法中，每次迭代都会产生局部最优解，为了充分利用当前最优解的信息，本文提出一种新的疫苗产生方式，即将当前最优解的特征与问题的先验知识结合，形成混合疫苗，由于最优解的个体携带了更适合问题的基因，因此，这种方式制备的疫苗可能会更加适合算法的全局寻优。
（2）免疫选择
免疫选择，既是对接种疫苗的范围和浓度进行选择。
由于疫苗可能从问题的先验知识中取得，或从局部最优解中取得，因此要选择疫苗接种的范围和浓度。
免疫选择可以用以下公式表示： （2.1）
公式表示在某代的所有 个个体中，按照比例 随机抽取个个体进行注射， 即为抗体浓度。
（3）疫苗接种
疫苗接种，即将选定的疫苗注射到个体的基因中。假设选定的疫苗为 ，量子种群为 ，则疫苗接种可以表示如下：
（2.2）
其中 表示疫苗对种群的影响因子。
3. 组合优化问题
0-1背包问题是经典的组合优化问题，描述如下：我们有 种物品，物品 的重量为 ，价格为 。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为 。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：
maximize （3.1）
subject to （3.2）
对此问题经常采用贪婪算法，贪婪算法使用一系列的选择得到问题的解，在每一次的选择中总是做出当前状态来看最优的选择。即通过局部最优来达到全局最优。这种启发式策略不一定总是获得全局最优解，但多数情况下都可以获得问题的较优解。
在0-1背包问题中一般选择如下贪婪算法[8]：价值密度最大比贪婪算法。选择准则为：从剩余物品中选择 值最大的物品装入背包，这也是直觉上最好的选择。但对于0-1背包问题，不一定能够获得全局最优解，并且有时与最优解相去甚远。
4 量子免疫算法应用于组合优化问题中
4.1 量子比特编码方案
求解0-1背包问题时，将染色体长度设为 ，其中 为可以放入背包中的物品总数，也即每条量子染色体拥有 个量子基因。量子坍塌后的每条染色体即为代表一种背包问题的装入方案，某位取1表示将此物品放入背包中，取0则相反，如下图所示：
图2 0-1背包问题编码方案
4.2 适应度函数评价
针对每条染色体确定的物品装入方案，计算背包的总价值作为此染色体的适应度函数的评价标准，总价值越高，则适应度函数越大。如果背包总重量超过所能承受最大重量，则把适应度函数设为最小。
4.3 疫苗获取
对0-1背包问题进行分析，在最优分配方案中，一定具备以下特征：价值较大，重量较小的物品，即价值密度比较大的物品，会出现在背包中。重量大于背包承受重量的物品，一定不会出现在背包中。可以根据以上两个先验知识来制备疫苗。对于具备第一个特征的物品，接种疫苗基因位置1。具备第二个特征的物品，接种疫苗基因位置0。
而对于迭代过程中产生的局部最优解，直接使用其基因作为疫苗。
4.5 免疫选择和疫苗接种
免疫选择和疫苗接种均使用上节介绍的方法，而疫苗接种时影响因子 使用如下公式产生：
（4.1）
为量子免疫算法当前迭代次数， 表示量子免疫算法迭代总次数，使用以上公式，则在算法迭代初期，可以增加疫苗的作用范围，加快算法的收敛速度，而在迭代中期， 影响因子变小，可以降低疫苗选群对种群的影响，增加搜索的范围。
4.6 终止条件
当算法迭代值规定的迭代代数时算法终止，输出结果
5 算法仿真及讨论
5.1 仿真使用参数
使用以下数据对算法进行仿真：
第一组物品数量 n=30, 最大重量Y=150。
第二组物品数量 n=40, 最大重量Y=200。
对于以上数据，分别使用贪婪算法，量子遗传算法，量子免疫算法进行最优值求解仿真。
量子遗传算法：初始种群规模大小为40，进化代数500次，采用量子全干扰交叉，量子变异概率为0.15。
量子免疫算法：初始规模大小为40，进化代数500次，也采用量子全干扰
上一页 [1] [2] [3] 下一页
量子免疫算法的改进及在组合优化问题中的应用 第2页下载如图片无法显示或论文不完整，请联系qq752018766
