注册| 登录

量子免疫克隆算法

2018-03-04

由于量子计算具有的并行处理能力、指数级存储容量及对经典算法的加速作用,极大的拓宽了学者们的视野,拥有及其宽广的应用前景。作为量子计算的重要组成部分——与经典领域中的人工智能算法结合而产生的量子智能算法,由于融合了量子计算和传统智能计算各自的优势,具有很高的理论价值和应用前景。量子免疫算法作为其中重要的一个分支,对其的研究也起步不久,但由于其具有种群规模小、收敛速度快、全局搜索能力强、鲁棒性强等优点及在组合优化问题中的良好表现,已成为该领域研究的热点之一。针对该算法的优化方案被不断的提出,该算法与其他优秀算法如粒子群、退火、神经网络 BP 等算法的特质也在不断的融合。

量子免疫克隆算法(Quantum-ispired immune clonal algotithm, QICA)是将量子搜索机制与生物免疫系统原理相结合而演化出的一种搜索和优化的计算方法。与量子遗传 算 法 ( Quantum  genetic  algorithm, QGA )、 量 子 进 化 算法( Quantum  evolution algorithm, QEA)等典型算法具有基本一致的核心进化思想,只是在具体的实施手段上有着略微的差异,可以认为 QICA 是 QGA、QEA 等算法的继承与发展。

 QICA 仿效了生物学原理中的进化和遗传的过程,利用量子编码的叠加性构造抗体,应用克隆操作实现种群的扩展,相比遗传算法更好的维护了种群的多样性,再通过选择、变异、交叉等进化操作,逐步逼近待优化问题的最优解。与 QGA、QEA 一样,本质上来讲,QICA 仍是概率意义上以随机方式寻求组合优化问题最优解的算法。

 

尽管量子免疫算法有很多实施方法,但总体来说,算法大体上是基本相同的,其采取的步骤如下:

Setp 1  初始化种群 Qt

Setp 2  观测操作,由 Qt生成二进制代码串 Pt

Setp 3  评价种群中 Pt适应度,保存最优解;

Setp 4  克隆操作,生成新的种群Pt’;

Setp 5  基因变异操作;

Setp 6  停机条件判断: 满足停机条件,输出当前最优个体,算法结束,否则跳转回 Setp 2。

其基本的算法流程图如图1 所示:

 QQ图片20180119162317_副本.jpg

图 1 量子免疫算法流程 


QICA 的基本思想是模拟生物免疫系统应答机制的过程,进行反复迭代,从而得到理想的结果。算法操作的对象是由若干染色体个体所组成的群体;应用某种机制构建对具体问题的评价函数;再通过克隆、选择等操作将优秀个体遗传到下一代,保持种群的多样性;通过变异操作促使优良个体的生成。

由于自然进化和生命现象的不可预知性,导致了此类算法无法保证期全局收敛性。其表现的主要特征一是收敛速度慢,二是容易早熟收敛。虽有很多学者给出了改进方案,但难以从根本上解决该问题。

 

参考文献:

1. 李士勇, 李盼池. 量子搜索及量子智能优化研究进展[J]. 计算机测量与控制,2009,17(7):1239-1241 

2. Jiao Licheng,  Li Yangyang. Quantum-inspired Immune Clonal Optimization[C]. Neural Networks and Brain, 2005. ICNN&B ’05. International Conference on. 2005:461~466. 

3. Li  Yangyang,  Jiao  Licheng.  Quantum-inspired  immune  clonal  algorithm  and  its application[C].Proceedings  of  2007  International  Symposium  on  Intelligent  Signal Processing and communication Systems. 2007:670~673. 

4. 马颖,“基于量子计算理论的优化算法研究”,西北工业大学博士学位论文(2014).

收藏 评论:0
没有ID?去注册 忘记密码? 已有账号,马上登陆

添加表情