基于粒計(jì)算理論的背包問(wèn)題研究

肖鏃

摘要：本文闡述了遺傳算法是解決背包問(wèn)題的有效方法，指出將粒計(jì)算理論引入背包問(wèn)題求解的可行性，研究了基于粒矩陣知識(shí)約簡(jiǎn)遺傳算法求解背包問(wèn)題，為背包問(wèn)題的求解提供了新的思路，本文通過(guò)一個(gè)四背包問(wèn)題進(jìn)行舉例說(shuō)明。

關(guān)鍵詞：遺傳算法；粒計(jì)算理論；背包問(wèn)題

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）06-0062-02

遺傳算法是一種問(wèn)題求解方法，它模仿了生物進(jìn)化過(guò)程，可以使用多種編碼方法來(lái)表征復(fù)雜的結(jié)構(gòu)，可以用一組編碼表示進(jìn)行遺傳操作，經(jīng)過(guò)優(yōu)勝劣汰的自然選擇，決定搜索路徑，在解決背包問(wèn)題的眾多算法中，遺傳算法可以是一個(gè)比較好的方法遺傳算法將0-1背包問(wèn)題看成一個(gè)知識(shí)系統(tǒng)，包括了條件和決策屬性。背包問(wèn)題中的各個(gè)物件可以認(rèn)為是條件屬性，在滿足約束條件的情況下，決策屬性為背包中物件的總價(jià)值是否大于等于群體某一值，大于等于則為優(yōu)秀個(gè)體，記為1，小于則為劣質(zhì)個(gè)體記為0。即可將背包問(wèn)題用遺傳算法表示，進(jìn)行編碼和運(yùn)算等工作，用遺傳算法的規(guī)則求出0-1背包問(wèn)題的最優(yōu)解[1]。

1 粒矩陣知識(shí)約簡(jiǎn)方法的實(shí)現(xiàn)過(guò)程

1.1 決策信息系統(tǒng)的知識(shí)粒化

對(duì)決策表T=（U，A，C，D）進(jìn)行知識(shí)粒化，針對(duì)不同要求可采取不同的粒化方法（均勻粒化、模糊粒化、分層粒化等），這里采用等價(jià)類的二進(jìn)制粒化法，根據(jù)條件類與決策類，求取對(duì)應(yīng)的二進(jìn)制粒矩陣BGrM。

1.2 判斷初始決策信息系統(tǒng)是否相容

定義2 相容與不相容：在決策表中，對(duì)于U/C中同一等價(jià)類的記錄都是相同的決策值，就稱這個(gè)等價(jià)類的任一記錄為確定性記錄，若有不同的決策值，則為不確定性記錄。如果在決策表中的所有記錄都是確定性的，就稱這個(gè)決策表為相容表，否則稱為不相容表，根據(jù)公式：。

計(jì)算k，如果k=1，決策信息系統(tǒng)相容，轉(zhuǎn)下一步，否則根據(jù)Cm×n，通過(guò)矩陣的變換將其拆分成相容決策表，篇幅有限，這里只討論相容決策表。

1.3 合并相同規(guī)則，進(jìn)行屬性約簡(jiǎn)

2 將粒計(jì)算理論引入遺傳算法求解0-1背包問(wèn)題

在求解0-1背包問(wèn)題的過(guò)程中，遺傳算法產(chǎn)生新基因型個(gè)體的方法有兩種，一是基因交換，另一種是突變。而這兩種方式都是隨機(jī)產(chǎn)生的，并沒(méi)有讓個(gè)體向適應(yīng)度更好的方向發(fā)展，而只是經(jīng)過(guò)模擬自然選擇的過(guò)程，對(duì)劣質(zhì)個(gè)體進(jìn)行了淘汰。這樣在一定程度上讓運(yùn)算更加復(fù)雜。通過(guò)粒矩陣知識(shí)約簡(jiǎn)方法，在進(jìn)行遺傳算子操作之前，先對(duì)初始群體進(jìn)行屬性約簡(jiǎn)。然后在最簡(jiǎn)屬性的基礎(chǔ)上進(jìn)行選擇復(fù)制、交換和突變的操作。在能夠終止之前，每一代個(gè)體都存在著差別，可以進(jìn)行屬性約簡(jiǎn)，獲得每一代個(gè)體染色體上的主要基因，然后再進(jìn)行遺傳算子操作。基于粒矩陣的知識(shí)約簡(jiǎn)方法實(shí)際上是將決策信息表的屬性及屬性值約簡(jiǎn)等效為矩陣的數(shù)學(xué)計(jì)算。決策信息表中相同規(guī)則的合并，不相容決策信息表的分解都可以認(rèn)為是一種矩陣運(yùn)算，從而0-1背包問(wèn)題的信息可以用矩陣來(lái)表示，描述更加直觀[2]。

3 算法對(duì)比和結(jié)果分析

GA和GCGA都可以得到20個(gè)背包問(wèn)題的最優(yōu)解，此時(shí)最優(yōu)解的個(gè)體相同，背包重量也一樣，但GA在128代達(dá)到最優(yōu)解，GCGA在42代獲得最優(yōu)解，本文提出的GCGA算法在迭代次數(shù)上明顯優(yōu)于遺傳算法，GCGA算法比遺傳算法具有更快的收斂速度。

參考文獻(xiàn)

[1]朱閱岸.解0-1背包問(wèn)題的算法比較和改進(jìn)[D].暨南大學(xué)，2011.

[2]賀毅朝，王熙照，李文斌，等.基于遺傳算法求解折扣0-1背包問(wèn)題的研究[J].計(jì)算機(jī)學(xué)報(bào)，2015，（12）：2614-2630.

Abstract：This paper expounds that genetic algorithm is an effective method to solve the knapsack problem， points out the feasibility of introducing the grain computing theory into the knapsack problem solving， and studies the solution of knapsack problem based on the kernel matrix knowledge reduction genetic algorithm， and provides a new idea for the solution of the knapsack problem. This paper is carried out through a four knapsack problem. Examples are given.

Key words：genetic algorithm； grain computing theory； knapsack problem