嚴太山, 郭觀七, 李文彬

?

應用知識進化原理求解背包問題的算法研究

嚴太山, 郭觀七, 李文彬

(1. 湖南理工學院 信息與通信工程學院, 湖南 岳陽 414006; 2. 湖南理工學院 復雜工業(yè)物流系統(tǒng)智能控制與優(yōu)化湖南省重點實驗室, 湖南 岳陽 414006)

以知識進化論哲學思想為基礎(chǔ), 提出一種應用知識進化原理求解背包問題的算法(簡稱為KP-KEA), 利用Banach壓縮映射原理證明了算法的全局收斂性. 該算法使用傳承算子來傳承知識庫中的優(yōu)秀知識個體, 利用創(chuàng)新算子來產(chǎn)生新知識個體, 利用更新算子來更新知識庫, 在它們的共同作用下實現(xiàn)知識的進化, 最后從知識庫的最優(yōu)知識個體中獲取背包問題的最優(yōu)解. 實例表明, 該算法在求解背包問題時取得了良好的效果, 其收斂速度和最優(yōu)解的質(zhì)量均優(yōu)于常用的遺傳算法. 該算法同樣適用于其他約束優(yōu)化問題的求解.

背包問題求解; 知識進化原理; 全局收斂性分析; 約束優(yōu)化

0 引言

求解背包問題的算法通常有經(jīng)典算法以及各種生物進化算法[3~8], 目前人們的研究仍然集中在生物自然選擇層面上[9,10], 由于算法存在與生俱來的局限性, 在求解大規(guī)模背包問題時, 并不一定能得到問題的最優(yōu)解. 知識進化算法是模擬人類知識進化機理求解復雜問題的一種新方法, 本文將知識進化原理應用于背包問題求解, 建立應用知識進化原理求解背包問題的算法(簡稱為KP-KEA), 旨在提高背包問題的求解效率.

1 應用知識進化原理求解背包問題的算法思想

應用知識進化原理求解背包問題的算法(KP-KEA)是建立在卡爾·波普爾的知識進化論[9~15]基礎(chǔ)上的. 卡爾·波普爾的知識進化論告訴我們, 知識也是不斷進化的, 知識進化具有與生物進化相似的進化機理, 包含了新知識的產(chǎn)生機制和優(yōu)勝劣汰的自然選擇機制.

KP-KEA的基本思想是: 通過分析實際領(lǐng)域問題, 建立待求解問題的初始知識庫; 然后利用知識進化算子, 即傳承算子、創(chuàng)新算子和更新算子, 來執(zhí)行知識進化操作, 包括傳承優(yōu)秀知識個體、產(chǎn)生新的知識個體和更新知識庫; 算法滿足結(jié)束條件時, 知識庫中的最優(yōu)知識個體就是問題的最優(yōu)解. 其算法流程如圖1所示.

圖1 KP-KEA算法流程

2 應用知識進化原理求解背包問題的算法實現(xiàn)

2.1 知識庫的結(jié)構(gòu)及知識個體編碼方法

2.2 進化算子

2.2.1傳承算子

傳承算子的作用是從知識庫中選擇規(guī)模固定的優(yōu)秀知識個體進入進化池中. 本文采用罰函數(shù)法來處理背包問題的約束, 評價知識個體優(yōu)劣的適應值函數(shù)為

2.2.2創(chuàng)新算子

創(chuàng)新算子的作用是產(chǎn)生新的知識個體, 具體包括以下兩個方面:

②對問題可行解的創(chuàng)新, 即根據(jù)當前代的認知度對知識個體中的可行解部分進行調(diào)整. 創(chuàng)新規(guī)則為

2.2.3更新算子

知識庫更新規(guī)則為

3 應用知識進化原理求解背包問題的算法收斂性分析

3.1 基本概念與定理

本節(jié)相關(guān)概念與結(jié)果見文[16~18].

3.2 應用Banach壓縮映射原理分析KP-KEA的收斂性

4 應用實例

為了測試算法的性能, 我們選取如下兩個背包問題實例進行求解.

表1 GA和KP-KEA對實例1的求解結(jié)果

圖2 GA和KP-KEA求解實例1的收斂曲線

表2 GA和KP-KEA對實例2的求解結(jié)果

圖3 GA和KP-KEA求解實例2的收斂曲線

從表1、表2和圖2、圖3中的結(jié)果可以看出, 在求解背包問題時, 無論是在解的質(zhì)量方面, 還是在收斂速度方面, KP-KEA比遺傳算法都要優(yōu)越.

5 結(jié)論

以知識進化原理為基礎(chǔ), 建立了一種背包問題求解算法(KP-KEA). 在理論上應用Banach壓縮映射原理證明了該算法具有很好的全局收斂性; 算法在對背包問題實例進行優(yōu)化求解時, 表現(xiàn)出了良好的尋優(yōu)性能, 能以較少的迭代次數(shù)尋找到全局最優(yōu)解. 今后可以使知識進化原理與各種傳統(tǒng)的生物進化算法進行融合應用, 以拓寬其工程應用領(lǐng)域.

[1] Sinnamon R M, Andrews J D.[J]. Reliability Engineering and System Safety, 1997, 58(2): 89~96

[2] Lee Hae Sang, Lie Chang Hoon.[J]. IEEE Trans. on Reliability,1997 , 46 (3): 360~363

[3] 賀毅朝, 宋建民, 張敬敏. 利用遺傳算法求解靜態(tài)與動態(tài)背包問題的研究[J]. 計算機應用研究, 2015, 32(4): 1011~1015

[4] 劉寒冰, 張亞娟. 求解0-1背包問題的改進混合遺傳算法[J]. 計算機系統(tǒng)應用, 2015,24(6): 197~201

[5] 余 娟, 馮曉華, 賀昱曜. 求解多維背包問題的改進分布估計算法[J]. 計算機仿真, 2014, 31(10): 286~290

[6] 張 晶, 吳虎勝. 求解背包問題的病毒進化蝙蝠算法[J]. 計算機仿真, 2015, 32(6): 256~261

[7] 楊 震, 馬天寶, 余 文. 廣義分子計算模型在0-1背包問題中的應用[J]. 計算機科學, 2014, 41(s2): 7~9

[8] 黃席樾, 張著洪. 現(xiàn)代智能算法理論及應用[M]. 北京: 科學出版社, 2005

[9] 劉純青, 楊莘元, 張 穎. 知識進化策略[J]. 系統(tǒng)工程與電子技術(shù), 2007,29(6): 1017~1020

[10] 黃海燕, 顧幸生, 劉曼丹. 求解約束問題的文化算法研究[J]. 自動化學報, 2007, 33(10): 1115~1120

[11] 朱祖平. 知識進化與知識創(chuàng)新機理研究[J]. 研究與發(fā)展管理, 2000, 12(6): 16~19

[12] 鐘義信. “信息-知識-智能”生態(tài)意義下的知識內(nèi)涵與度量[J]. 計算機科學與探索, 2007, 1(2): 129~137

[13] 舒煒光, 卓如飛. 客觀知識——一個進化論的研究[M]. 上海: 上海譯文出版社, 2005

[14] 傅季重, 周昌忠, 蔣 戈. 猜測與反駁——科學知識的增長[M]. 上海: 上海譯文出版社, 2005

[15] 馬慧民, 葉春明, 張 爽, 等. 基于知識進化算法的生產(chǎn)采購協(xié)同計劃問題研究[J]. 計算機應用研究, 2009, 26(12): 4621~4623

[16] 李敏強, 寇紀凇, 林 丹, 等. 遺傳算法的基本理論與應用[M]. 北京: 科學出版社, 2002

[17] 許天周. 應用泛涵分析[M]. 北京: 科學出版社, 2002

[18] Bryan P.Rynne Martin A. Youngson.[M]. Beijing: Tsinghua University Press, 2005

An Algorithm for Solving Knapsack Problem by Knowledge Evolution Principle

YAN Taishan, GUO Guanqi, LI Wenbin

(1.College of Information and Communication Engineering, Hunan Institute of Science and Technology, Yueyang 414006, China; 2. Key Laboratory of Hunan Province on Intelligent Control and Optimization of Complex Industrial Logistics System, Hunan Institute of Science and Technology, Yueyang 414006, China)

Based on the evolutionary epistemology idea, an algorithm (called KP-KEA) is proposed for solving knapsack problems by knowledge evolution principle. The global convergence of this algorithm is proved by using the Banach contraction mapping principle. In this algorithm, inheritance operator is used to inherit excellent knowledge individuals, innovation operator is used to produce novel knowledge individuals, and update operator is used to update knowledge-base. Knowledge evolution is realized by these three operators accordingly. Finally, the optimal solution of knapsack problems can be gained from the optimal knowledge individual. The successful experimental results show that this algorithm is effective to solve knapsack problems. Compared with genetic algorithm, the convergence speed and the optimal solution’s quality of this algorithm are all better. This algorithm is suited to solve other constraint optimization problems too.

knapsack problem solution, knowledge evolution principle, global convergence analysis, constraint optimization

2017-08-16

湖南省自然科學基金項目(2017JJ2107); 湖南省科技計劃項目(2016TP1021); 湖南理工學院研究生課程建設(shè)項目(201505)

嚴太山(1968? ), 男, 湖南祁東人, 博士, 湖南理工學院信息與通信工程學院副教授. 主要研究方向: 進化計算、智能信息處理

TP301.6

A

1672-5298(2017)04-0008-06