基于交互式遺傳算法的網站信息分類體系交互設計

〔摘 要〕本文在介紹交互式遺傳算法的基礎上，提出了基于交互式遺傳算法網站信息分類體系交互設計的基本思路；并采用JSP實現了MVC模式下網站信息分類體系交互設計程序。

〔關鍵詞〕交互式遺傳算法；MVC；信息分類體系

〔中圖分類號〕TP18；G257 〔文獻標識碼〕B 〔文章編號〕1008-0821(2009)02-0123-03

Interactive Design of Websites Information Classification

Based on Interactive Genetic AlgorithmWu Sheng1，2 Zhang Zhiguang1 Zhang Changjiang1 Wu Qingqing2

(1.College of Economics and Management，Nanjing Forestry University，Nanjing 210037，China；

2.School of Computer Science and Technology，Xuzhou Normal University，Xuzhou 221116，China)

〔Abstract〕This paper introduced Interactive Design of Websites Information Classification based on Interactive Genetic Algorithm(IDWICIGA).After introducing Interactive Genetic Algorithm(IGA)，this paper introduced main idea of the method IDWICIGA.This paper implemented the IDWICIGA program with JSP in MVC model.

〔Key words〕interactive genetic algorithm；MVC；information classification

網絡信息分類問題日益受到人們的關注[1]。網絡信息分類體系編制問題是網絡信息分類研究中的熱點之一[2-3]。網站是網絡信息的重要載體，網站信息分類體系質量直接影響到網站的質量，并影響到用戶對網站的評價和訪問。對網站信息分類體系的設計方法進行研究不僅有理論意義，還有很強的應用價值。

如何根據用戶需求設計信息分類體系是網站設計時需要解決的重要問題之一[4]。一些文獻曾用遺傳算法(Genetic Algorithm，GA)來解決網站設計中的問題；文獻[5]用遺傳算法和神經網絡實現了對網站開發的優化，文獻[6]用交互式遺傳算法(Interactive Genetic Algorithm，IGA)實現了對網站樣式和布局的交互設計。

交互式遺傳算法是一種新型遺傳算法，它通過讓用戶評估個體來替代適應度函數值進行自動計算，通過交互體現了用戶的個性或用戶的興趣。交互式遺傳算法已成功地應用到服裝設計、樂曲創作、網站結構設計等領域[6-8]。于是，本文提出了基于交互式遺傳算法實現網站信息分類體系的交互設計，讓用戶和程序一起交互地完成網站信息分類體系的設計。

1 基于IGA網站信息分類體系交互設計的思路

1.1 交互式遺傳算法簡介

用遺傳算法求解問題時，需要先將問題可能解看作是群體(種群)中的個體，并將個體編碼成符號串形式(即染色體)。然后，模擬生物進化過程對個體反復進行雜交、變異等操作；并根據預定的適應度函數評價每個個體，依據優勝劣汰的進化規則不斷得到新的種群。同時，搜索種群中的最優個體，求得滿足要求的最優解。

GA采用一定的編碼技術構造染色體；染色體是GA操作的基本對象。在GA執行時，每一代有許多個體同時存在。GA程序根據個體對環境的適應能力來生成新種群中的個體，適應能力強的個體有更多機會成為新種群中的個體。適應能力的強弱通過適應度函數f(x)的值來判別。適應度函數f(x)的構成與目標函數有密切關系，往往是目標函數的變種。

GA的遺傳操作有選擇(Selection)、雜交(Crossover)和變異(Mutation)等操作。選擇是從目前種群中選擇適應能力強的個體從而產生新種群的過程。當許多個體相同或后代個體與上一代沒有太大差別時，可通過雜交來產生新一代個體。例如，有2個個體A和B，長度為6，A=a1a2a3a4a5a6，B=b1b2b3b4b5b6。經雜交后可能變為A′和B′：

A=a1a2a3|a4a5a6 A′=a1a2a3|b4b5b6

B=b1b2b3|b4b5b6B′=b1b2b3|a4a5a6

變異是以很小的概率改變個體中某個基因。變異與選擇、雜交結合在一起，能較好地保證GA的有效性。

交互式遺傳算法是在傳統遺傳算法基礎上發展起來的一種新型算法。交互式遺傳算法和一般遺傳算法的主要不同在于：IGA中使用用戶交互式評價代替傳統GA中的適應度函數來選擇個體。

1.2 網站信息分類體系交互設計的流程

根據交互式遺傳算法的特點，基于IGA的網站信息分類體系交互設計流程如圖1所示。

具體來說，網站信息分類體系交互設計的步驟包括：(1)確定信息分類體系的個體編碼方法，形成初始種群。

圖1 基于IGA網站信息分類體系交互設計流程

(2)種群內個體進行相關遺傳操作。(3)用戶對每個個體(本文中為信息分類體系)進行評分；若已經有滿意的個體，則將其滿意度設置為最高，選擇“滿意”選項，點擊“評分”按鈕；頁面如圖2所示。(4)在用戶評價的評分的基礎上，根據評分結果，顯示用戶滿意的個體(即一個網站信息分類體系)。圖2 網站信息分類體系交互設計時用戶評價個體的界面

2009年2月第29卷第2期現?代?情?報Journal of Modern InformationFeb.2009Vol.29 No.2

2009年2月第29卷第2期基于交互式遺傳算法的網站信息分類體系交互設計Feb.2009Vol.29 No.2

2 用JSP在MVC模式下的程序實現

2.1 實現思路

考慮到模型——視圖——控制器(Model-View-Controller，MVC)模式的優勢，本文用JSP實現網站信息分類體系交互設計程序時采用了MVC模式。MVC的原理是將系統分解為模型、視圖、控制器3個部分。其中，模型表示數據和處理數據的業務邏輯，視圖顯示數據，控制器負責接受請求并交付處理。實現交互設計程序的主要文件信息如表1所示。

表1 主要文件相關信息

模式的要素主要文件的文件名文件的主要作用模型ModelWebBean.java

DBBean.java對遺傳算法相關參數的封裝

對數據庫訪問的封裝控制器ControllerYichuanServlet.java實現對文件的調用、分配視圖ViewtitleSel.jsp

titleOutput.jsp顯示個體信息，以便用戶交互評價

最優個體(網站信息分類體系)的顯示

MVC模式下的模型要訪問數據庫，本程序中主要有biaoti、generation、temp三張表。biaoti表存儲分類體系的標題，generation表存儲一個種群中每個個體的基因及其對應的適應值(用戶對各個個體的滿意度)，temp表存儲一個種群中每個個體的基因。

2.2 關鍵代碼

2.2.1 titleOutput.jsp關鍵代碼：

geneStr=webbean.getBestGeneStr()；

titleNum=webbean.getTitleNum()；

……

int webId = webbean.getWebId()；

for(int j=0；j＜titleNum；j++){

str[j]=geneStr.substring(3*j，3*j+3)；

sql=″select*from biaoti where id=′″+webId+(j+1)+str[j]+″′″；

rs=dbbean.executeQuery(sql)；

if(rs.next())str[j]=rs.getString(″name″)；

}

2.2.2 titleSel.jsp關鍵代碼：

＜form action=″YiChuanServlet″method=″post″name=″tiltemain″id=″tiltemain″onSubmit=″return check()；″＞

＜% titleNum=webbean.getTitleNum()；

String[]str=new String[titleNum]；

for(i=0；i＜4；i++){

for(int j=0；j＜titleNum；j++){

str[j]=geneStr[i].substring(3*j，3*j+3)；

sql=″select*from biaoti where id=′″+webId+(j+1)+str[j]+″′″；

rs=dbbean.executeQuery(sql)；

if(rs.next())str[j]=rs.getString(″name″)；

}

}

for(i=0；i＜4；i++){

for(int j=0；j＜titleNum；j++){

str[j]=geneStr[i+4].substring(3*j，3*j+3)；

sql=″select*from biaoti where id=′″+webId+(j+1)+str[j]+″′″；

rs=dbbean.executeQuery(sql)；

if(rs.next()){

str[j]=rs.getString(″name″)；

}

%＞

2.2.3 YichuanServlet.java關鍵代碼：

this.getServletContext().setAttribute(″SaveTitleNum″，new TitleSelectCommand1(″∥titleSel.jsp″))；

this.getServletContext().setAttribute(″TitleSelect″，new TitleSelectCommand2(″∥titleSel.jsp″))；

……

this.getServletContext().setAttribute(″GA″，new GACommand(″∥showGAResult.jsp″))；

2.2.4 WebBean.java屬性：

private int[] fitness=new int[8]；

private String[] geneStr=new String[8]；

private String[] tempStr=new String[8]；

private String bestGeneStr=1；

private static String[] titlename=new String[40]；

private int len=0；

private int titleNum=1；

private int webId=1；

private int daiShu=1；

private final double pc=0.5；∥雜交率

private final double pm=0.05；∥變異率

3 結 論

本文提出了基于交互式遺傳算法的網站信息分類體系交互設計，并采用JSP實現了MVC模式下的網站信息分類體系交互設計程序；為設計網站信息分類體系提供了一種新的思路。

參考文獻

[1]吳禮志.網絡信息分類體系研究進展[J].圖書館學研究，2004，(2)：54-57.

[2]謝琳惠.網絡信息分類組織研究的重點、熱點及其他[J].大學圖書館學報，2006，(2)：103-106.

[3]狄九風.網絡信息分類組織研究的六大熱點[J].現代情報，2005，(10)：64-66.

[4]石曉華，王春芳.網絡信息分類與傳統分類法的優劣分析——兼談構建《中國網絡信息分類法》[J].圖書館理論與實踐，2001，(1)：43-45.

[5]閔惜琳.人工神經網絡結合遺傳算法對網站開發優化的應用[J].系統工程，2007，25(2)：22-26.

[6]Oliver A，Monmarché N，Venturini G.Interactive design of web sites with a genetic algorithm[C].Proceedings of the IADIS International Conference WWW/Internet，2002.http：∥citeseer.ist.psu.edu/556162.html[EB/OL].2007-12-13.

[7]Takagi H.Interactive evolutionary computation：Fusion of the capabilities of EC optimization and human evolution[C].San Diego：Proceedings of the IEEE，2001，89(9)：1275-1296.

[8]Kim H S，Cho S B.Application of interactive genetic to fashion design[J].Engineering Applications of Artificial Intelligence，2000，13(6)：635-644.