應(yīng)用知識(shí)進(jìn)化原理求解背包問題的算法研究

嚴(yán)太山, 郭觀七, 李文彬

?

應(yīng)用知識(shí)進(jìn)化原理求解背包問題的算法研究

嚴(yán)太山, 郭觀七, 李文彬

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

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

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

0 引言

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

1 應(yīng)用知識(shí)進(jìn)化原理求解背包問題的算法思想

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

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

圖1 KP-KEA算法流程

2 應(yīng)用知識(shí)進(jìn)化原理求解背包問題的算法實(shí)現(xiàn)

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

2.2 進(jìn)化算子

2.2.1傳承算子

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

2.2.2創(chuàng)新算子

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

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

2.2.3更新算子

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

3 應(yīng)用知識(shí)進(jìn)化原理求解背包問題的算法收斂性分析

3.1 基本概念與定理

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

3.2 應(yīng)用Banach壓縮映射原理分析KP-KEA的收斂性

4 應(yīng)用實(shí)例

為了測(cè)試算法的性能, 我們選取如下兩個(gè)背包問題實(shí)例進(jìn)行求解.

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

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

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

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

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

5 結(jié)論

以知識(shí)進(jìn)化原理為基礎(chǔ), 建立了一種背包問題求解算法(KP-KEA). 在理論上應(yīng)用Banach壓縮映射原理證明了該算法具有很好的全局收斂性; 算法在對(duì)背包問題實(shí)例進(jìn)行優(yōu)化求解時(shí), 表現(xiàn)出了良好的尋優(yōu)性能, 能以較少的迭代次數(shù)尋找到全局最優(yōu)解. 今后可以使知識(shí)進(jìn)化原理與各種傳統(tǒng)的生物進(jìn)化算法進(jìn)行融合應(yīng)用, 以拓寬其工程應(yī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)與動(dòng)態(tài)背包問題的研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(4): 1011~1015

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

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

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

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

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

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

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

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

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

[13] 舒煒光, 卓如飛. 客觀知識(shí)——一個(gè)進(jìn)化論的研究[M]. 上海: 上海譯文出版社, 2005

[14] 傅季重, 周昌忠, 蔣 戈. 猜測(cè)與反駁——科學(xué)知識(shí)的增長(zhǎng)[M]. 上海: 上海譯文出版社, 2005

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

[16] 李敏強(qiáng), 寇紀(jì)凇, 林 丹, 等. 遺傳算法的基本理論與應(yīng)用[M]. 北京: 科學(xué)出版社, 2002

[17] 許天周. 應(yīng)用泛涵分析[M]. 北京: 科學(xué)出版社, 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

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

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

TP301.6

A

1672-5298(2017)04-0008-06