一種基于交互式遺傳算法的圖書(shū)經(jīng)費(fèi)分配群決策模型_遺傳算法matlab程序
發(fā)布時(shí)間:2020-03-10 來(lái)源: 日記大全 點(diǎn)擊:
[摘要]提出一種基于交互式遺傳算法的大學(xué)圖書(shū)館藏書(shū)建設(shè)中圖書(shū)采購(gòu)經(jīng)費(fèi)分配群決策系統(tǒng)模型,通過(guò)人工智能技術(shù)把定性決策與定量決策結(jié)合起來(lái),解決文獻(xiàn)經(jīng)費(fèi)分配決策中優(yōu)化目標(biāo)非定量化、難以較高效率獲得專(zhuān)家群體意見(jiàn)共識(shí)的問(wèn)題。模擬實(shí)驗(yàn)反映出該模型能以較高效率達(dá)成專(zhuān)家群體意見(jiàn)共識(shí)。
[關(guān)鍵詞]交互式遺傳算法 圖書(shū)采購(gòu)經(jīng)費(fèi)分配 群決策模型
[分類(lèi)號(hào)]TP182
1 引言
建立科學(xué)的、適用于大學(xué)讀者的最佳藏書(shū)結(jié)構(gòu)是高校藏書(shū)建設(shè)的核心內(nèi)容和基本任務(wù)。高校圖書(shū)館的服務(wù)需求相對(duì)變化較小,藏書(shū)建設(shè)具有一定的穩(wěn)定性;但同時(shí),由于社會(huì)的發(fā)展、學(xué)科專(zhuān)業(yè)的調(diào)整,對(duì)藏書(shū)建設(shè)又提出前瞻性和突變性的要求,藏書(shū)結(jié)構(gòu)也要因之而變,通過(guò)調(diào)整各種新購(gòu)圖書(shū)的經(jīng)費(fèi)比例是實(shí)現(xiàn)藏書(shū)結(jié)構(gòu)改善的重要手段之一。因此,在經(jīng)費(fèi)有限的條件下,確定在一定周期內(nèi)(一般為一年)各種新購(gòu)圖書(shū)的最佳經(jīng)費(fèi)比例,是圖書(shū)采訪決策中十分關(guān)鍵的一環(huán)。各種新購(gòu)圖書(shū)經(jīng)費(fèi)的比例決策問(wèn)題是一種典型的隱性目標(biāo)非結(jié)構(gòu)化決策問(wèn)題,為了更好地反映本大學(xué)特色和學(xué)科發(fā)展的需要,一些大學(xué)圖書(shū)館采用由各學(xué)科教授等專(zhuān)家構(gòu)成藏書(shū)建設(shè)委員會(huì),通過(guò)群決策模式來(lái)完成各種新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策,但新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策具有優(yōu)化目標(biāo)非定量化、求解空間極大(組合爆炸)的特點(diǎn),決策過(guò)程中如何以較高的效率獲得群體意見(jiàn)共識(shí)就成為一個(gè)巨大的挑戰(zhàn)。傳統(tǒng)方法一般是通過(guò)利用判斷矩陣的一致性、群體一致性指標(biāo)、個(gè)體一致性指標(biāo)等方法來(lái)實(shí)現(xiàn)專(zhuān)家群體的共識(shí),這類(lèi)方法雖然簡(jiǎn)單,但在可操作性以及群體共識(shí)的最大化方面不理想。因此,結(jié)合人工智能技術(shù),探討高效的新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策問(wèn)題優(yōu)化模型,具有重要的理論和實(shí)踐價(jià)值。
2 交互式遺傳算法
2.1 遺傳算法
遺傳算法(Genetic Algorithm,GA)是由美國(guó)的J.Holland教授在1975年提出一類(lèi)模擬生命進(jìn)化機(jī)制(適者生存,優(yōu)勝劣汰遺傳機(jī)制)的搜索和優(yōu)化方法,它的全局最優(yōu)和隱含并行性特點(diǎn)適用于求解復(fù)雜的優(yōu)化問(wèn)題,已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。
基本遺傳算法的基本優(yōu)化流程如圖1所示,其核心思想是:首先隨機(jī)或按照一定的條件產(chǎn)生一個(gè)初始種群(若干問(wèn)題解方案),然后僅用適應(yīng)度(由實(shí)際問(wèn)題解的評(píng)價(jià)函數(shù)確定)來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣,并以此作為遺傳操作的依據(jù)進(jìn)行一代一代進(jìn)化(一般來(lái)說(shuō),適應(yīng)度越大,其被選擇進(jìn)行遺傳操作繁殖后代的概率就越大)
2.2 交互式遺傳算法
從2.1中的介紹可知,在遺傳算法中,適應(yīng)度是指引種群優(yōu)化的唯一方向標(biāo),因此,在利用遺傳算法解決實(shí)際問(wèn)題時(shí),確定個(gè)體解的適應(yīng)度的量化評(píng)價(jià)方法可以說(shuō)是整個(gè)優(yōu)化過(guò)程最重要的一步。隨著遺傳算法的廣泛應(yīng)用,學(xué)者們發(fā)現(xiàn)傳統(tǒng)的遺傳算法只能解決性能指標(biāo)用明確因數(shù)(顯式)表示的系統(tǒng)優(yōu)化問(wèn)題,因?yàn)閮?yōu)化問(wèn)題只有明確定義的性能指標(biāo)函數(shù)才能計(jì)算進(jìn)化個(gè)體的適應(yīng)值。但是,許多實(shí)際系統(tǒng)優(yōu)化問(wèn)題,如藝術(shù)設(shè)計(jì)、樂(lè)曲創(chuàng)作、知識(shí)學(xué)習(xí)和數(shù)據(jù)挖掘等的性能指標(biāo)往往難以用明確的函數(shù)表示,即它們屬于隱式性能指標(biāo)優(yōu)化問(wèn)題,而傳統(tǒng)的遺傳算法無(wú)法解決這類(lèi)問(wèn)題。在這樣的應(yīng)用背景下,日本學(xué)者高木英行等在前人研究成果的基礎(chǔ)上,系統(tǒng)地提出了交互式遺傳算法(interac―tive genetic algorithm,IGA)的理論與方法,并將其推廣應(yīng)用于藝術(shù)設(shè)計(jì)、語(yǔ)音識(shí)別、復(fù)雜產(chǎn)品設(shè)計(jì)等領(lǐng)域。交互式遺傳算法和傳統(tǒng)遺傳算法的最大區(qū)別在于通過(guò)交互式手段以用戶對(duì)個(gè)體評(píng)估來(lái)替代傳統(tǒng)的遺傳算法(GA)對(duì)適應(yīng)度值進(jìn)行自動(dòng)計(jì)算的過(guò)程。在IGA中,首先將種群的各個(gè)個(gè)體以某種可視化形式呈現(xiàn)給用戶,用戶對(duì)這些個(gè)體進(jìn)行評(píng)估(通常采用百分制、七分制、二分制等打分方式),并以此作為遺傳操作的依據(jù)。因此,它既具有傳統(tǒng)進(jìn)化算法的搜索能力強(qiáng)等優(yōu)點(diǎn),還具備與決策者交互的機(jī)制,特別適合應(yīng)用于那些適應(yīng)度函數(shù)難以表達(dá),但用戶對(duì)個(gè)體評(píng)估較容易的復(fù)雜隱性目標(biāo)優(yōu)化問(wèn)題。
3 基于交互式遺傳算法的新購(gòu)圖書(shū)比例輔助群決策模型
3.1 應(yīng)用IGA優(yōu)化新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策的主要步驟
遺傳算法有一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架,結(jié)合新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策問(wèn)題的實(shí)際,具體步驟如下:
3.1.1 確定決策變量及約束條件利用IGA算法進(jìn)行新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策時(shí),首先要確定圖書(shū)的分類(lèi),本文按照中圖分類(lèi)法,將圖書(shū)分為22個(gè)大類(lèi),每個(gè)大類(lèi)比例值的變化都會(huì)組合成不同的新購(gòu)圖書(shū)經(jīng)費(fèi)比例方案。設(shè)每類(lèi)圖書(shū)的經(jīng)費(fèi)比例為Ui(i=1,2,3,…,22),則決策變量即為ui,約束條件為∑Ui=1。
3.1.2 確定表示可行解的染色體編碼方法 一個(gè)經(jīng)費(fèi)比例方案中的某類(lèi)圖書(shū)經(jīng)費(fèi)比例對(duì)應(yīng)于遺傳算法中的一個(gè)基因,一個(gè)經(jīng)費(fèi)比例方案對(duì)應(yīng)于遺傳算法中的一個(gè)染色體個(gè)體,其編碼可以選擇二進(jìn)制編碼或浮點(diǎn)數(shù)編碼。同樣的問(wèn)題常常可以使用不同的編碼,不同的編碼對(duì)編程的方便性和程序運(yùn)行效率的影響是不同的,由于圖書(shū)經(jīng)費(fèi)比例參數(shù)屬于連續(xù)參數(shù),因此采用直接的實(shí)數(shù)編碼方案比二進(jìn)制編碼更為方便。
3.1.3 確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法 利用IGA算法進(jìn)行新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策時(shí),藏書(shū)建設(shè)委員會(huì)的專(zhuān)家對(duì)每一個(gè)大類(lèi)圖書(shū)在本大學(xué)的合適比例都有自己的主觀判斷,據(jù)此對(duì)每一個(gè)新購(gòu)圖書(shū)經(jīng)費(fèi)比例方案給出評(píng)價(jià)值(采用百分制),系統(tǒng)根據(jù)各個(gè)委員的打分,求取每一個(gè)新購(gòu)圖書(shū)經(jīng)費(fèi)比例方案的平均得分,即作為該方案的適應(yīng)度值。
3.1.4 確定遺傳算法優(yōu)化迭代停止條件若適應(yīng)度函數(shù)的最大值已知,理論上應(yīng)以找到適應(yīng)度達(dá)到最大值的個(gè)體作為遺傳算法迭代終止條件,然而圖書(shū)經(jīng)費(fèi)分配這個(gè)具體問(wèn)題,個(gè)體適應(yīng)度最大值雖然已知(100分),但當(dāng)藏書(shū)建設(shè)委員會(huì)的專(zhuān)家較多時(shí),找到這樣的個(gè)體幾乎是不可能的,所以具體實(shí)現(xiàn)遺傳算法時(shí),采用理想解迭代停止法:預(yù)先設(shè)定一個(gè)低于100分的理想分?jǐn)?shù),當(dāng)某一個(gè)體的適應(yīng)度值達(dá)到該分?jǐn)?shù)時(shí)即終止迭代。同時(shí),設(shè)定最大遺傳代數(shù)和進(jìn)化停滯判定條件(若迭代到一定代數(shù)后,連續(xù)若干代群體的最優(yōu)個(gè)體的適應(yīng)度值不再增大,則判定進(jìn)化停滯。),到了最大遺傳代數(shù)或進(jìn)化停滯時(shí),即使當(dāng)前最優(yōu)個(gè)體的適應(yīng)度值沒(méi)有達(dá)到理想值也終止迭代。
3.1.5 設(shè)計(jì)遺傳算子,即確定出選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法遺傳算法的進(jìn)化過(guò)程主要包括選擇、交叉和變異,交叉和變異算子用于產(chǎn)生新的個(gè)體,而選擇算子保證了遺傳迭代中“適者生存”的群體進(jìn)化現(xiàn)象,在本模型中體現(xiàn)了專(zhuān)家群體意見(jiàn)求同的意向。下面對(duì)本模型中的進(jìn)化算子進(jìn)行簡(jiǎn)單介紹。
?選擇。選擇操作是遺傳算法中實(shí)現(xiàn)群體優(yōu)良基因傳播的基本方式,選擇即從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成繁殖池的過(guò)程。遺傳算法中最常用 的選擇方式是輪盤(pán)賭(Roulette Wheel)選擇方式,也稱比例選擇或復(fù)制,在該方法中,各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比例。在本模型中,設(shè)每次輪盤(pán)選擇操作時(shí)候選群體規(guī)模為N,則第i個(gè)個(gè)體被選擇進(jìn)入繁殖池的概率p.為:
顯然,個(gè)體適應(yīng)度越大,其被選擇的概率越高,反之則越低。某個(gè)被選擇進(jìn)入繁殖池后的個(gè)體則從候選群體中移除。繁殖池里個(gè)體數(shù)達(dá)到種群規(guī)模M時(shí)則停止輪盤(pán)選擇操作。
?變異。實(shí)數(shù)編碼遺傳算法中常用的變異算子有:均勻變異,邊界變異,非均勻變異等。由于新購(gòu)圖書(shū)比例決策問(wèn)題中有嚴(yán)格的條件限制,即各個(gè)基因(各種圖書(shū)經(jīng)費(fèi)比例)之和必須等于1,因此,變異操作需要成對(duì)進(jìn)行,即須將每個(gè)基因作為一次變異操作對(duì)象。具體操作過(guò)程是:對(duì)繁殖池中的每一個(gè)體,依次指定個(gè)體編碼串中的相鄰兩個(gè)基因?yàn)樽儺慄c(diǎn)候選;對(duì)每一個(gè)候選變異點(diǎn),以預(yù)先確定的變異概率進(jìn)行選擇,如選中,則對(duì)一個(gè)基因增加△U,另一個(gè)基因減少△U。
?交叉。交叉操作是遺傳算法中組合出新的個(gè)體的主要操作,在串空間進(jìn)行有效搜索,同時(shí)降低對(duì)有效模式的破壞概率。一般來(lái)講,交叉操作在兩個(gè)個(gè)體之間進(jìn)行,但由于新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策問(wèn)題中嚴(yán)格的條件限制,如采用異體交叉,容易產(chǎn)生大量的無(wú)意義個(gè)體,因此,本模型中設(shè)計(jì)的交叉為自體交叉,即:對(duì)繁殖池中的每一個(gè)體,隨機(jī)指定個(gè)體編碼串中的兩個(gè)基因?yàn)榻徊婧蜻x;對(duì)每一個(gè)候選點(diǎn),以預(yù)先確定的交叉概率進(jìn)行選擇,如選中,則互換兩個(gè)基因的值。一般來(lái)講,交叉概率比變異概率要大。
3.2 基于IGA的新購(gòu)圖書(shū)經(jīng)費(fèi)比例群決策輔助系統(tǒng)流程圖
由藏書(shū)建設(shè)委員會(huì)專(zhuān)家群體進(jìn)行基于IGA模型的新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策過(guò)程如圖2所示。
Step1:顯式當(dāng)前本館圖書(shū)結(jié)構(gòu),作為藏書(shū)建設(shè)委員會(huì)專(zhuān)家們進(jìn)行新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策的參考;
Step2:根據(jù)以前的圖書(shū)經(jīng)費(fèi)比例案例庫(kù)或由各個(gè)委員提出若干初始方案,作為初始種群;
Step3:將所有個(gè)體(各個(gè)比例方案)顯式給各個(gè)專(zhuān)家;
Step4:各個(gè)專(zhuān)家綜合各種主、客觀準(zhǔn)則和自己主觀認(rèn)識(shí)給定每一個(gè)個(gè)體的評(píng)價(jià)值;
Step5:藏書(shū)建設(shè)委員會(huì)主持人判斷當(dāng)前最優(yōu)方案的平均評(píng)價(jià)值是否達(dá)到理想值,如是,則結(jié)束迭代,否則轉(zhuǎn)到Step7;
Step6:軟件系統(tǒng)根據(jù)當(dāng)前進(jìn)化代數(shù)是否達(dá)到規(guī)定值或進(jìn)化是否已停滯,如是,則結(jié)束迭代,否則轉(zhuǎn)到Step7;
Step7:系統(tǒng)進(jìn)行遺傳操作,包括選擇、交叉、變異,然后轉(zhuǎn)到Step3。
4 模擬實(shí)驗(yàn)
針對(duì)大學(xué)圖書(shū)館藏書(shū)建設(shè)中新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策這樣一個(gè)目標(biāo)難以顯式定量表達(dá)的非結(jié)構(gòu)化決策問(wèn)題,基于本文提出的交互式遺傳算法群決策系統(tǒng)模型,在VS2005環(huán)境下開(kāi)發(fā)了一個(gè)原型系統(tǒng)(為了簡(jiǎn)化開(kāi)發(fā),原型系統(tǒng)中進(jìn)化停止條件僅由最大代數(shù)確定),進(jìn)行了新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策模擬實(shí)驗(yàn)。交叉概率設(shè)為O.6,變異概率設(shè)為0.15,為了盡量降低應(yīng)用IGA時(shí)人的疲勞問(wèn)題的影響,最大進(jìn)化代數(shù)和種群規(guī)模均設(shè)置得較小,種群規(guī)模為20,最大迭代次數(shù)為20,初始方案群(第O代)由參與模擬實(shí)驗(yàn)的某圖書(shū)館lO位館員提出(每人提出2個(gè))。整個(gè)實(shí)驗(yàn)過(guò)程費(fèi)時(shí)約2小時(shí)。初始最優(yōu)方案平均評(píng)價(jià)分值為69.6分,實(shí)驗(yàn)中20次迭代結(jié)束時(shí),最優(yōu)方案平均評(píng)價(jià)分值達(dá)到了82.3分。最優(yōu)方案進(jìn)化情況如圖3所示。
分析進(jìn)化情況可以看到,在最初10代內(nèi),最優(yōu)個(gè)體評(píng)價(jià)分快速增長(zhǎng),之后總體增長(zhǎng)緩慢,甚至出現(xiàn)了評(píng)價(jià)分振蕩的情況,這可能與隨著評(píng)價(jià)次數(shù)的增多,館員的疲勞程度增大有關(guān)。因此,在實(shí)際應(yīng)用該模型開(kāi)發(fā)實(shí)用系統(tǒng)時(shí),最大進(jìn)化代數(shù)還可適當(dāng)減少,同時(shí),在遺傳操作中增加最優(yōu)保留策略,應(yīng)能避免振蕩。
5 結(jié)語(yǔ)
目前,已有一些學(xué)者進(jìn)行了將遺傳算法應(yīng)用于圖書(shū)采購(gòu)決策問(wèn)題的研究。文獻(xiàn)[6]從盡量滿足讀者采購(gòu)需求的角度出發(fā),將每位讀者要求訂購(gòu)的書(shū)目用一個(gè)集合來(lái)表示,所有讀者的采購(gòu)要求構(gòu)成一個(gè)集合簇,用遺傳算法計(jì)算該集合簇的碰集,遺傳運(yùn)算中適應(yīng)度由采購(gòu)方案?jìng)(gè)體與集合簇中的集合相“碰”的多少來(lái)確定;文獻(xiàn)[7]利用神經(jīng)網(wǎng)絡(luò)建立圖書(shū)的圖書(shū)內(nèi)容關(guān)鍵詞、圖書(shū)分類(lèi)號(hào)、圖書(shū)出版社、圖書(shū)出版日期、圖書(shū)版本號(hào)、圖書(shū)價(jià)格、圖書(shū)是否屬于重點(diǎn)學(xué)科等7種屬性(作為輸入神經(jīng)元)與是否被采購(gòu)(作為輸出神經(jīng)元)之間的非線性映射關(guān)系,采用遺傳算法對(duì)神經(jīng)網(wǎng)絡(luò)的權(quán)值、閾值等進(jìn)行優(yōu)化,遺傳運(yùn)算中適應(yīng)度由期望輸出與實(shí)際輸出的誤差來(lái)確定。這種模型中,圖書(shū)屬性與是否被采購(gòu)的映射關(guān)系實(shí)際上由訓(xùn)練樣本情況來(lái)決定的,也就是由已購(gòu)情況預(yù)測(cè)(決策)待購(gòu)情況。上述模型針對(duì)的都是具體書(shū)目的采購(gòu)決策,考慮的因素均較單一,且在利用遺傳算法時(shí),個(gè)體評(píng)價(jià)函數(shù)(適應(yīng)度函數(shù))都是能用定量數(shù)學(xué)式顯式表達(dá)的,本質(zhì)上均是傳統(tǒng)遺傳算法的應(yīng)用。而大學(xué)圖書(shū)館藏書(shū)建設(shè)中新購(gòu)圖書(shū)經(jīng)費(fèi)比例決策問(wèn)題需要考慮的影響因素眾多,如學(xué)校類(lèi)型、專(zhuān)業(yè)特色、人才培養(yǎng)定位、現(xiàn)有館藏情況、讀者層次分布等,這類(lèi)決策本質(zhì)上是一種典型的非結(jié)構(gòu)化決策,要建立有效綜合各種影響因素的定量數(shù)學(xué)評(píng)價(jià)模型是及其困難的。群體決策作為解決非結(jié)構(gòu)化決策問(wèn)題的重要手段,已越來(lái)越引起人們的重視,本文嘗試將群決策引入圖書(shū)采購(gòu)經(jīng)費(fèi)分配決策問(wèn)題求解,并采用交互式遺傳算法來(lái)解決快速高效達(dá)成群體共識(shí)這一群決策瓶頸問(wèn)題。模擬實(shí)驗(yàn)反映出該方法能以較高的效率提高最終購(gòu)書(shū)經(jīng)費(fèi)比例方案的群體共同認(rèn)可度。
相關(guān)熱詞搜索:遺傳 經(jīng)費(fèi) 算法 一種基于交互式遺傳算法的圖書(shū)經(jīng)費(fèi)分配群決策模型 圖書(shū)情報(bào) 圖書(shū)情報(bào)碩士
熱點(diǎn)文章閱讀