量子智能算法及在OFDM系统资源分配中的应用 第11页
maximize                          （4.3）
subject to                      （4.4）
如果限定物品 最多只能选择 个，则问题称为有界背包问题。可以用公式表示为：
maximize                             （4.5）
subject to                   （4.6）
如果不限定每种物品的数量，则问题称为无界背包问题【29】。
本节主要研究0-1背包问题。
4.3.1.2 0-1背包问题计算复杂度
使用动态规划算法可以解决0-1背包问题[30]，首先可以假定 都是正数，假定在总重量不超过 的情况下，前 种物品总价格所能达到的最高值定义为 。
则 的递推关系为：
 ；                          （4.7）
 ；                          （4.8）
如果 ， ；                   （4.9）
如果 ，         （4.10）
通过计算 即可获得最终结果。因此算法的时间和空间复杂度均为 。
4.3.1.3 0-1背包问题的贪婪算法
贪婪算法使用一系列的选择得到问题的解[31]，在每一次的选择中总是做出当前状态来看最优的选择。即通过局部最优来达到全局最优。这种启发式策略不一定总是获得全局最优解，但多数情况下都可以获得问题的较优解。
在0-1背包问题中一般选择如下贪婪算法[32]：价值密度最大比贪婪算法。选择准则为：从剩余物品中选择 值最大的物品装入背包，这也是直觉上最好的选择。、、
具体过程如下：
（1）对给定的物品，分别求出价值密度： 。
（2）按照价值密度比，对物品进行降序排列。
（3）按照以下步骤依次装入物品，直到停止。对于当前物品，如果重量低于剩余的重量，则装入，并将其标志为一，否则停止。
    此算法时间复杂度体现为计算价值密度比和进行排序，复杂度为 ，时间空间复杂度较低，可以找到背包问题的最优解，但对于0-1背包问题，不一定能够获得全局最优解。
4.3.2 量子免疫算法求解0-1背包问题
由于量子免疫算法就是结合免疫算法与遗传算法的优点来提高算法的整体性能，并有目的的利用待求解问题的特征信息来抑制优化问题中退化现象。因此，可以使用量子免疫算法来求解0-1背包问题。
1 量子比特编码方案
求解0-1背包问题时，将染色体长度设为 ，其中 为可以放入背包中的物品总数，也即每条量子染色体拥有 个量子基因。量子坍塌后的每条染色体即为代表一种背包问题的装入方案，某位取1表示将此物品放入背包中，取0则相反，如下图所示：
                           图4.3 0-1背包问题编码方案2 适应度函数评价
针对每条染色体确定的物品装入方案，计算背包的总价值作为此染色体的适应度函数的评价标准，总价值越高，则适应度函数越大。如果背包总重量超过所能承受最大重量，则把适应度函数设为最小。
3 疫苗获取
对0-1背包问题进行分析，在最优分配方案中，一定具备以下特征：价值较大，重量较小的物品，即价值密度比较大的物品，会出现在背包中。重量大于背包承受重量的物品，一定不会出现在背包中。可以根据以上两个先验知识来制备疫苗。对于具备第一个特征的物品，接种疫苗增加基因位置1的概率。具备第二个特征的物品，接种疫苗基因位置0。而对于迭代过程中产生的局部最优解，直接使用其基因作为疫苗。
4 免疫选择和疫苗接种
免疫选择和疫苗接种均使用上节介绍的方法，而疫苗接种时影响因子 使用如下公式产生：
                                                          （4.11）
 为量子免疫算法当前迭代次数， 表示量子免疫算法迭代总次数，使用以上公式，则在算法迭代初期，可以增加疫苗的作用范围，加快算法的收敛速度，而在迭代中期，影响因子 变小，可以降低疫苗选群对种群的影响，增加搜索的范围。
5  量子变异与交叉操作
    采用第三章讨论的量子变异操作与全交叉操作对个体进行更新。6  终止条件
当算法迭代值达到规定的迭代代数时算法终止，输出结果
4.3.3 算法仿真及实验结果分析
使用以下三组数据对0-1背包问题进行求解。
第一组：n=20，最大重量Y=85。
物品重量W={7    44    10    96     0    77    81    86     8    39 
  25    80    43    91   18    26    14    13    86    57}
物品价值P= {54    14    85    62    35    51    40    7    23    12
   18    23    41     4    90    94    49    48    33   90}
第二组：n=30，最大重量 Y=150
物品重量W={42    50     8    26    80     2    92    73    48    57   
23    45    96    54   52     23    48    62    67    39  
36    98     3    88    91    79    9    33    67    13   }
物品价值Y={ 50    47     5    68   4     7    52    9    81    81   
72    14     65   51   97    64    80    45   43    82   
 8    13     17   39   83    80     6    39   52    41   }
第三组：n=40, 最大重量Y=200
物品重量W={36    11    78    38    24    40     9    13    94    95
   57     5    23    35    82     1     4    16    64    73  
 64    45    54    29    74    18    68    18    36    62 
 78     8    92    77    48    43    44    30    50    51}
物品价值P={81    79    64    37    81    53    35    93    87    55   
62    58    20    30    47    23    84    19    22    17  
22    43    31    92    43    18    90    97    43    11   
25    40    59    26    60    71    22    11    29    31}
4.3.3.1 算法参数设定
对于以上三组数据，分别使用贪婪算法，量子免疫算法，改进的量子免疫算法进行最优值求解仿真。
量子免疫算法：初始种群规模大小为40，进化代数500次，采用量子全干扰交叉，量子变异概率为0.15。疫苗浓度 设为0.4，影响因子 采用上一节介绍的公式进行计算。使用0-1背包问题的先验知识来获取疫苗。
改进的量子免疫算法：使用0-1背包问题的先验知识和每次迭代产生的局部最优解来产生疫苗，其他与量子免疫算法设置相同。
4.3.3.2实验结果及分析
对每组数据，使用贪婪算法，量子免疫算法，改进的量子免疫算法各独立运行50次，统计运行结果如表4.1所示：

 << 上一页  [11] [12] [13] [14] [15] 下一页