量子智能算法及在OFDM系统资源分配中的应用 第10页
量子免疫算法
遗传算法，量子遗传算法是一类自适应的迭代搜索算法，尽管算法具有全局收敛的特性，但算法的交叉，变异，选择等操作是在概率意义下随机进行的，一方面可以保持种群的进化性，但令一方面，有时也有退化的情况出项。另外，单纯使用量子遗传算法，保持了算法的通用性，但在解决具体问题时，往往会忽略问题特征的辅助作用。同时，仅仅依单一的进化算法在模拟人类智能化处理问题方面严重不足，还需要挖掘利用人类的多种智能。因此，将免疫算法的疫苗接种和免疫选择思想引入到量子遗传算法中，提出量子免疫算法，结合免疫算法与量子遗传算法的优点来提高算法的整体性能，并有目的的利用待求解问题的特征信息来抑制优化问题中退化现象的出现的。以下分别介绍量子免疫算法的每个步骤。
4.2.1 疫苗获取方法及改进
疫苗是指依据人们对于待求问题的先验知识而从中取出的一种基本特征信息，抗体是指根据这种特征信息而得出的一类解。前者可以看做对待求的最佳个体所能匹配模式的一种估计，后者则是对这种模式进行匹配而形成的样本。疫苗的正确选择对算法的运行效率具有十分重要的意义，是免疫操作得以有效发挥作用的基础与保障【32】。
考虑到量子免疫算法的应用对象主要是NP类问题[24]，而这类问题在规模较小时一般易于求解，容易发现局部条件下的求解规律。因此，在获取疫苗时，既可以根据问题的特征来构造疫苗，也可以在分析需求解问题的基础上降低原问题的规模，增设局部条件来简化问题，用简化后的问题来作为选取疫苗的一种途径。同时，由于每个疫苗都是通过某一局部信息来探求全局最优解，所以没有必要对每个疫苗都做到精确无误。因此可以根据问题的特征，对原问题选用一些迭代优化算法来提取疫苗。
由于量子遗传算法中，每次迭代都会产生局部最优解，为了充分利用当前最优解的信息，本文提出一种新的疫苗产生方式，即将当前最优解的特征与问题的先验知识结合，形成混合疫苗，由于最优解的个体携带了更适合问题的基因，因此，这种方式制备的疫
苗可能会更加适合算法的全局寻优。
4.2.2 免疫选择和疫苗接种
免疫选择，既是对接种疫苗的范围和浓度进行选择。
由于疫苗可能从问题的先验知识中取得，或从局部最优解中取得，因此要选择疫苗接种的范围和浓度。免疫选择可以用以下公式表示：
（4.1）
公式表示在某代的所有 个个体中，按照比例 随机抽取个个体进行注射， 即为抗体浓度。
疫苗接种，即将选定的疫苗注射到个体的基因中。假设选定的疫苗为 ，量子种群为 ，则疫苗接种可以表示如下：
（4.2）
其中 表示疫苗对种群的影响因子。
4.2.3 算法运行框架
将免疫算法的思想放在量子遗传算法中，得到算法的框架如下图所示：
图4.1 量子免疫算法运行框图
算法的基本流程如下
（1）生成并初始化第一代量子种群
（2）对第一代种群进行测量得到第一代个体
（3）对各个个体进行适应度评估
（4）找出出最优个体，并以此作为种群演化的目标
（5）按照一定得策略利用量子门对种群进行更新操作，得到下一代种群
（6）分析问题的先验知识，结合上一代种群的最佳个体，获取当前的疫苗，按照抗体浓度进行当前种群的疫苗接种。
（7）按照一定的概率对种群进行量子变异操作。
（8）按照一定的概率对种群进行全交叉操作。
（9）对种群进行一次测量获得个体 。
（10）对生成的个体进行适应度函数的评估。
（11）找出最佳个体，如果符合程序结束条件，则结束程序，否则，转入第（5）步继续计算。
4.3 使用量子免疫算法求解0-1背包问题
4.3.1 0-1背包问题介绍
背包问题(Knapsack problem)是一种组合优化的经典问题[27][28]。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题有着广泛的应用背景，如预算控制，项目选择，材料切割，货物装载等。同时也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？
图4.2 背包问题图示
背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？
4.3.1.1 0-1背包问题数学定义
我们有 种物品，物品 的重量为 ，价格为 。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为 。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>