基于貪心遺傳算法的專業期刊選訂模型研究

〔摘 要〕高校圖書館如何科學地選訂期刊是一個復雜的非線性多目標優化問題，在分析期刊選訂影響因子的基礎上，建立期刊選訂模型，探討利用遺傳算法與貪心算法相結合的方法對該問題求解。

〔關鍵詞〕遺傳算法;貪心算法;高校圖書館;期刊選訂

〔中圖分類號〕TP301.6 〔文獻標識碼〕A 〔文章編號〕1008-0821(2009)07-0185-04

Study on the Model for Selected Subscribing to Professional

Periodicals Based on Greedy and Genetic AlgorithmChen Maoguo

(Taizhou Teachers College，Taizhou 225300，China)

〔Abstract〕Scientific selected subscribing to the professional periodicals for university library is a complex problem which is non-liner and multi-objective optimized.This paper set up the periodicals subscription model by analyzing the influence factors of subscription，and using the combination of genetic algorithm and greedy algorithm to realize a scientific periodicals subscription.

〔Key words〕genetic algorithm;greedy algorithm;university library;selected subscribing

在高校圖書館的信息資源中，期刊信息是最主要的信息源之一，期刊信息含量大、傳遞快、內容新，能迅速反映當前信息和動態。隨著科學技術的迅猛發展，各類知識的更新速度加快，期刊品種和數量也急劇增加，我國通過郵局公開出版發行的各類期刊總數已有11 000多種，自辦發行的也有7 700種之多。而各類高校圖書館都面臨著資金緊缺的困惑，每年的訂閱經費總量和增量都非常有限，如何合理地利用有限的訂閱經費，科學地選訂專業期刊，滿足學校教學科研對期刊文獻信息的需求，這是一個值得深入研究的課題。

1 高校圖書館期刊采購影響因子分析

高校圖書館訂閱的期刊主要服務于學校的教學、科研等方面，因此選擇期刊必須根據學校的辦學規模和層次、專業設置、學科建設和科研項目來選定，同時也要考慮本館的期刊經費預算、館藏期刊建設情況，并參考讀者的意見等實際情況科學地選擇期刊。期刊選訂工作要從其實用性、計劃性、完整性、節約性幾個方面著手，具體而言:高校期刊采購的主要影響因子有:學科建設的需求、科研及課題開發的需要、核心期刊的排名影響、期刊雜志社的影響力、學科發展的前瞻性、課外實踐的需求、館藏特色的需要、館藏的連續性和完整性以及訂閱經費限制、經費投入效益等。根據對期刊采訪影響因子的分析，進行期刊選訂時需注重適用性原則，以讀者滿足率為基本選訂條件，以期刊采訪的經費預算為限定條件，保證重點刊的訂閱，兼顧一般刊的訂閱，擴大一般刊的訂閱。

2 相關理論基礎

2.1 貪心算法

貪心算法是一種不追求最優解，只希望得到較為滿意解的方法。貪心算法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪心算法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪心算法不要回溯。貪心算法的基本思路是:首先建立數學模型來描述問題，其次把求解的問題分成若干個子問題，然后對每一子問題求解，得到子問題的局部最優解，最終把子問題的解局部最優解合成原來解問題的一個解。

2.2 遺傳算法

遺傳算法是計算數學中用于解決最優化的搜索算法，是一種借鑒生物自然選擇和進化機制發展起來的高度并行、隨機、自適應搜索算法。最初是借鑒了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。遺傳算法具有很強的魯棒性，非常適合處理多目標的優化問題。

遺傳算法通常表現為一種計算機模擬。對于一個最優化問題，一定數量的候選解(稱為個體)的抽象表示(稱為染色體)的種群向更好的解進化。傳統上，解用二進制表示，但也可以用其他表示方法。進化從完全隨機個體的種群開始，之后一代一代發生。在每一代中，整個種群的適應度被評價，從當前種群中隨機地選擇多個個體(基于它們的適應度)，通過自然選擇和突變產生新的生命種群，該種群在算法的下一次迭代中成為當前種群。遺傳算法在適應度函數選擇不當的情況下有可能收斂于局部最優，而不能達到全局最優。

3 期刊選訂的數學模型

3.1 期刊選訂決策策略

3.1.1 確定專業刊比例

根據學校具體情況確定專業學術期刊與普通期刊(休閑大眾化)的比例。我校定為8∶2。

3.1.2 專業期刊數據篩選

首先篩選掉和本校辦學層次不相適應的期刊，如某高校是本科層次，則高職高專、嬰幼兒、中小學類的期刊則需刪除掉;其次刪除掉與學校專業設置不相關的期刊，如某高校無醫學、農學等專業，則此類期刊需要篩選掉。根據以上兩點原則及我校圖書館實際情況篩選后適用于我校的待選專業期刊約有2 000種左右。

3.1.3 確定讀者需求評價權值

將待選目錄按專業或主題分類后，在圖書館網站上(或打印分發)由對應專業的師生讀者針對該專業教學、科研及提高綜合素質幾方面的需要，對待選期刊目錄進行圈選薦訂。表1 讀者需求評價模型表

級別教 師學 生10薦訂人數≥N1薦訂人數≥N28N1>薦訂人數>M1N2>薦訂人數>M25薦訂人數≤M1一訂人數≤M20薦訂人數為0薦訂人數為0

W11=10 (C1N1)

8 ?(N1C1M1)

5 ?(C1M1)

0 ?(C1=0)(1)W12=10 (C2N2)

8 ?(N2C2M2)

5 ?(C2M2)

0 ?(C2=0)(2)

W1=(W11+W12)/20(3)

C的值為薦訂人數，N和M的值根據各專業教師和學生人數及讀者參與薦訂期刊工作的熱情程序而定。如某專業學生人數為500人，約有10%的學生參與期刊的圈選薦訂工作，則N2取30，M2取5。從事該專業教學教師人數為10人，N1取值6，M1取值2。某專業刊教師有3人選，學生有28人選。則該刊的讀者需求評價權值為:W1=(8+10)/20=0.9

3.1.4 確定適用度評價權值

將待選期刊目錄按專業主題分類后，提供給學科專家小組，由他們根據期刊選購影響因子從學科建設等方面，對期刊本身的價值按4個等級進行評價。表2 期刊適用度評價模型表

級別學科建設科研課題期刊影響力學科發展課外實踐優10權威刊非常適用很大迫切需要指導性很強良8核心刊較適用較大較需要較強中5一般刊一般一般一般一般差0無關刊不適用低不需要無指導性

W2=∑ni=1W2nN(4)

N為參加評價的專家人數。如:第i位專家評價某刊是一般刊、非常適用、影響力較大、學科發展迫切需要、課外實踐指導性很強，則該刊的適用度評價權值為:W2i=(5+10+8+10+10)/50=0.86

3.1.5 確定經濟性評價權值

根據師生館藏特色的需要、期刊館藏的連續性和完整性、訂閱經費限制等影響期刊選訂的影響因子，由圖書館員對待選期刊目錄的期刊按4個等級進行評價。表3 期刊經濟性評價模型表

級別館藏特色連續性和完整性優10非常符合非常好良8較符合好中5一般一般差0不符合無關

如:某刊非常符合館藏特色，且館藏連續性和完整性好，則經濟性評價權值為:W3=(10+8)/20=0.9

3.1.6 綜合評價期刊的價值

根據讀者薦選結果分析統計讀者需求度、根據學科專家評價結果分析該期刊的適用度、根據圖書館員的評價結果分析該期刊的經濟性，并綜合評價該期刊的價值V。

V=∑3i=1Ki×Wi3(5)

Ki是常數值，根據各館實際需求可通過設定K1、K2、K3值的，以確定各適應度W1、W2、W3在整個適應度函數V中的比重大小，在本文中K的值都設為1。

3.2 數學模型的構建

根據期刊選訂決策策略，構建其數學模型，可將期刊選訂概括為NP完全問題。已知n個期刊的訂價(Price)及其價值(Value)分別為Pi>0和Vi>0，本校的期刊經費預算(Budget)Bi>0，選擇訂閱哪些期刊可以使得在經費預算限制之內所訂期刊的價值最大?該問題的模型可以表示為下述0/1整數規劃模型:

目標函數:

Maxf(X1，X2，L，Xn)=∑ni=1ViXi

s.t∑ni=1PiXiBi

xi∈{0，1} (i=1，2，…，n)(6)

Xi為0-1決策變量，Xi=1時表示該期刊訂閱，Xi=0時則表示該刊不訂閱。

4 貪心遺傳算法設計

借助貪心算法思想將啟發式規則引入遺傳算法的搜索過程，以解決遺傳算法收斂過慢和封閉競爭問題，運用遺傳算法在多峰搜索空間尋找相對最優解，不增加進化代數前提下，用貪心算法作為確定性選擇原則指導遺傳操作得到盡量優的解。

4.1 貪心算法設計

4.1.1 將待選期刊Lc=2000種按密度值Vi/Pi從大到小排列{1，2，3，…，Lc}，K=1，K的初值設為1，從第1個期刊開始計算。

4.1.2 選中第K個期刊，Pi為第i個期刊的訂價，判斷所有期刊總金額是否超過經費預算，如不超，則選訂第K個期刊，Xk=1;如超過，則第K個期刊不選，Xk=0，K=K+1。選下一個期刊進行判斷。

Xk=1 ∑k-1i=1Pi×Xi+PkBi

0 ∑k-1i=1Pi×Xi+Pk>Bi

K=K+1(7)

4.1.3 若K=Lc+1時，停止計算，否則，重復4.1.2。

4.1.4 求得{X1，X2，X3，…，XLc}即為貪心解。

4.2 貪心遺傳算法設計

4.2.1 初始化

首先，確定染色體(Chromosome)的長度(Length)為我校圖書館篩選后的待訂期刊種數Lc=2000;其次，確定種群(Population)的大小(Size)Ps為全校參與薦選讀者人數的3~5倍，如8 000人規模的高校，參加推薦人數10%為800人，則Ps=3×800=2400。最終，根據貪心算法思想確定交叉概率Pc、變異概率Pm及最大進化代數Maxgen。

4.2.2 編碼

隨機產生Ps個0~(2Lc-1)之間的整數，將其轉變為二進制編碼表示，染色體中每一位(基因gene)對應惟一按密度大小排列后的一種報刊，第i位為1表示該報刊選訂，為0則不選訂。將以上染色體個體及貪心解作為第0代，置種群代數Gen=0。

4.2.3 計算個體適應度及對非正常編碼的貪心修正

按照下列公式計算種群中個體適應度:

Price=∑ni=1PiXi;

Fintess=∑Lc-1i=0Vi×Xi(8)

if Price≤Budget，else轉5.1.2~5.1.4通過貪心算法修正染色體中的非正常基因，求得貪心解，再計算該解的適應度。

4.2.4 測試是否滿足結束條件

按照個體適應度大小對種群排序。測試最高的個體適應度由是否滿足最高要求，或是否達到進化后代數上限值(Gen>Maxgen)，如果滿足則停止，譯碼后輸出結果;否則，繼續執行下一步。

4.2.5 選擇操作

按照個體的適應度大小得到它的選擇概率，保留適應度大于平均值的個體，按照輪盤賭法選擇其他個體，盡量保證種群的多樣性和健壯性，產生下一代的個體群。

4.2.6 貪心交叉操作

隨機每次選擇2個染色體進行交叉，根據事先定義好的交叉概率Pc，為了確定是否進行交叉操作，則生成[0，1]的隨機數Rand1，若Rand1

4.2.7 貪心變異操作

根據事先定義好的變異概率Pm，每次選擇一個當前種群適應度最差的個體進行變異操作。為了確定新種群上的每個個體上的每個基因是否進行變異操作，則生成[0，1]的隨機數Rand2，若Rand2Pm，基因不變異，保留個體。

4.2.8 貪心演化

按4.2.3的方法計算新種群的個體適應度，將新、舊種群按個體適應度大小排序，依次選擇最大適應度個體生成下一代待演化種群，Gen=Gen+1，轉4.2.4。

5 結 語

期刊選訂問題可看作是一個多重約束條件下的NP完全問題，本文根據專業期刊選訂的特點，引入基于貪心遺傳火算法的期刊選訂模型，遺傳算法被用于個體中的全局搜索，貪心算法則在染色體中施行局部探尋，解決遺傳算法中個體的可行性問題，并使個體趨向較好的解，從初始種群的建立、交叉操作、變異操作等過程，都引入貪心算法思想。該模型可為高校圖書館決策科學訂閱期刊提供參考，并可同樣作用于商品選訂、各類意見征求匯總時的輔助決策。

參考文獻

[1]董軍軍.動態規劃算法和貪心算法的比較與分析[J].軟件導刊，2008，(2):129-130.

[2]Min Kong，Peng Tian，and Yucheng Kao.A new ant colony optimization algorithm for the multidimensional Knapsack problem[J].Computers Operations Research，2008，35(8):2672-2683.

[3]白君禮.高校圖書館文獻采訪經費分配的博弈研究[J].情報雜志，2007，(2):114-120.

[4]姚瑞楓.多維0-1背包問題的混合遺傳算法[J].武漢科技大學學報，2003，(6):214-217.

[5]李劍.一種求解背包問題的混合遺傳微粒群算法[J].計算機與數字工程，2008，(11):4-6.