遺傳算法在政府采購(gòu)系統(tǒng)中的應(yīng)用

李春梅，劉海雄

（青海大學(xué) 現(xiàn)代教育技術(shù)中心，青海 西寧 810016）

在政府采購(gòu)業(yè)務(wù)[1-6]中，評(píng)審專(zhuān)家委員會(huì)是整個(gè)評(píng)標(biāo)過(guò)程的關(guān)鍵，他們的結(jié)論將直接決定采購(gòu)結(jié)果的公平、公正，因此評(píng)標(biāo)專(zhuān)家的建立、管理是政府采購(gòu)業(yè)務(wù)重要的環(huán)節(jié)之一。政府采購(gòu)部門(mén)通過(guò)推薦、審批、考核等方式建立評(píng)審專(zhuān)家?guī)臁２⒃谇捌谠u(píng)標(biāo)工作結(jié)束后，通過(guò)招投標(biāo)監(jiān)管機(jī)構(gòu)、駐場(chǎng)監(jiān)察員和招標(biāo)單位對(duì)評(píng)標(biāo)專(zhuān)家的工作態(tài)度、業(yè)務(wù)水平和公正合理性等進(jìn)行評(píng)議打分，同時(shí)定期或不定期地組織參與招標(biāo)投標(biāo)的主體各方對(duì)評(píng)標(biāo)等家進(jìn)行測(cè)評(píng)，評(píng)議打分和測(cè)評(píng)的結(jié)果等作為年度考核管理的重要依據(jù)。為了確保政府采購(gòu)行為的透明、公正、公平，文中通過(guò)改變傳統(tǒng)手工的專(zhuān)家抽取過(guò)程，解決抽取方法不合理、抽取機(jī)會(huì)不均等、抽取與通知各自獨(dú)立、人工干預(yù)多、保密性差、間隔時(shí)間過(guò)長(zhǎng)等弊端，采用遺傳算法來(lái)實(shí)現(xiàn)評(píng)標(biāo)專(zhuān)家的抽取，以達(dá)到評(píng)審抽取的公正性和公平性的目的。

1 專(zhuān)家隨機(jī)抽取的要求及抽取的條件

1.1 專(zhuān)家隨機(jī)抽取的要求

評(píng)標(biāo)專(zhuān)家抽取[2]的過(guò)程，首先授權(quán)給專(zhuān)家抽取的工作人員并憑證書(shū)登錄系統(tǒng)，在監(jiān)督人員的監(jiān)督下進(jìn)行現(xiàn)場(chǎng)抽取，整個(gè)抽取過(guò)程如圖1所示。

1.2 專(zhuān)家隨機(jī)抽取的條件設(shè)置

圖1 評(píng)審專(zhuān)家抽取過(guò)程Fig.1 The extraction process of evaluation experts

按照每次評(píng)標(biāo)的實(shí)際情況，要求抽取符合條件的評(píng)審專(zhuān)家進(jìn)行參加評(píng)標(biāo)活動(dòng)。條件可包括：專(zhuān)業(yè)類(lèi)別、每組人數(shù)、學(xué)歷、職稱(chēng)和組數(shù)等。但有時(shí)因特殊需要，對(duì)專(zhuān)家條件需要更進(jìn)步一步的限制：如1）同組專(zhuān)家成員要求：不能有多個(gè)專(zhuān)家是來(lái)自同一單位；2）學(xué)歷要求：比如，10個(gè)專(zhuān)家中博士要有5人以上，碩士 3人以上；3）職稱(chēng)要求：職稱(chēng)必須為正高 6人以上，副高2人以上等。

2 遺傳算法在專(zhuān)家隨機(jī)抽取中應(yīng)用

為了實(shí)現(xiàn)抽取過(guò)程的公正性和合理性，本論文將采用遺傳算法對(duì)評(píng)標(biāo)專(zhuān)家進(jìn)行抽取。

2.1 遺傳算法介紹

遺傳算法[4，7]是在達(dá)爾文的“優(yōu)勝劣汰”的生物進(jìn)化理論得到啟發(fā)，利用簡(jiǎn)單的編碼技術(shù)和繁殖機(jī)制來(lái)表現(xiàn)復(fù)雜的現(xiàn)象，從而解決一些最優(yōu)解等問(wèn)題。其基本流程圖如圖2所示。本文中，對(duì)于流程圖中的pt，pm，pc賦予了新的含義。Pt是在第i代染色體中，每次隨機(jī)選擇出10個(gè)染色體作為交叉和變異的個(gè)體；pc是將對(duì)選擇后的染色體中依照其適應(yīng)值查找出最高值和最低值，將最低值淘汰，將最高值取出將其出現(xiàn)的次數(shù)設(shè)置為2其余染色體不變，隨機(jī)抽取出50%染色體，與剩下的染色體兩兩進(jìn)行交叉計(jì)算；pm的值完全是視抽取評(píng)審專(zhuān)家的條件決定的，由1.2所述的1）2）3）3個(gè)特殊條件決定是否發(fā)生變異。

圖2 遺傳算法基本流程圖Fig.2 The basic flow chart of genetic algorithm

2.2 遺傳算法設(shè)計(jì)

2.2.1 基因和染色體的定義

我們假定一個(gè)專(zhuān)家個(gè)體就是一個(gè)染色體，若考慮到特殊要求，比如考慮專(zhuān)家的學(xué)歷、職稱(chēng)以及來(lái)自同一單位的人數(shù)的限制等情況時(shí)，染色體可以定義為，領(lǐng)域編碼+專(zhuān)家編碼+單位編碼+學(xué)歷+職稱(chēng)。本論文中，所有基因的定義均采用十進(jìn)制來(lái)表示。對(duì)領(lǐng)域編碼是按照國(guó)家對(duì)學(xué)科領(lǐng)域的編碼進(jìn)行編碼，用3位數(shù)來(lái)編碼，如110為數(shù)學(xué)領(lǐng)域，150為化學(xué)領(lǐng)域，210為農(nóng)學(xué)，220為林學(xué)等；專(zhuān)家編碼采用3位領(lǐng)域數(shù)+3位專(zhuān)家在本領(lǐng)域中的編碼共6位數(shù)來(lái)表示；專(zhuān)家所在單位用3位數(shù)來(lái)表示，如078表示青海大學(xué)；專(zhuān)家學(xué)歷用1位數(shù)來(lái)表示，如1表示博士，2表示碩士，3表示本科；職稱(chēng)用1位數(shù)來(lái)表示，1表示正高，2表示副高，3表示講師。例如430+430102+078+1+1是一個(gè)完整的染色體個(gè)體，表示材料學(xué)科的李某專(zhuān)家來(lái)自青海大學(xué)，學(xué)歷為博士，職稱(chēng)為正高。在以上染色體定義中，領(lǐng)域編碼和專(zhuān)家編碼兩個(gè)基因是決定染色體的主要基因，單位編碼、學(xué)歷和職稱(chēng)3個(gè)基因是決定染色體發(fā)生變異的主要基因，而發(fā)生變異的基因依然是專(zhuān)家編碼。

2.2.2 適應(yīng)度函數(shù)的定義

針對(duì)宿州市特色農(nóng)產(chǎn)品銷(xiāo)售管理系統(tǒng)，從功能需求分析、系統(tǒng)架構(gòu)設(shè)計(jì)、 系統(tǒng)功能實(shí)現(xiàn)等三個(gè)方面對(duì)面向區(qū)域特色的農(nóng)產(chǎn)品銷(xiāo)售管理系統(tǒng)進(jìn)行了系統(tǒng)化、科學(xué)化試驗(yàn)。目前，已經(jīng)實(shí)現(xiàn)了基于移動(dòng)端銷(xiāo)售管理系統(tǒng)App的基本功能，但是在大數(shù)據(jù)分析和挖掘功能方面，仍需要作進(jìn)一步的完善。

每個(gè)評(píng)審專(zhuān)家在入庫(kù)時(shí)都需要經(jīng)過(guò)資格評(píng)審和專(zhuān)業(yè)評(píng)審，并且每年均進(jìn)行年度考核評(píng)審，因此各自具有一個(gè)評(píng)審分?jǐn)?shù)，采用百分制，如98分。同時(shí)，參加過(guò)投標(biāo)評(píng)審的專(zhuān)家均有投標(biāo)方、被投標(biāo)方和監(jiān)督方三方從專(zhuān)業(yè)水平、評(píng)審態(tài)度和是否公正等三方面以百分制方式進(jìn)行打分，這些也都成為每個(gè)評(píng)審專(zhuān)家的個(gè)人成績(jī)。我們將入庫(kù)時(shí)的打分標(biāo)準(zhǔn)和參加評(píng)標(biāo)活動(dòng)后對(duì)專(zhuān)家的打分標(biāo)準(zhǔn)一致化，將所有成績(jī)的平均分作為這個(gè)專(zhuān)家的最后分?jǐn)?shù)。在遺傳算法中，將專(zhuān)家的最后分?jǐn)?shù)除以 100 定義為該專(zhuān)家的影響因子 p（i），即 p（i）=avg（評(píng)審分?jǐn)?shù)+年度考核分?jǐn)?shù)+投標(biāo)方打的分?jǐn)?shù)+被投標(biāo)方打的分?jǐn)?shù)+監(jiān)督方打的分?jǐn)?shù)）/100。未參加過(guò)投標(biāo)評(píng)審的專(zhuān)家，其影響因子是 p（i）=avg（評(píng)審分?jǐn)?shù)+年度考核分?jǐn)?shù)）/100；多次參加評(píng)審的專(zhuān)家其投標(biāo)方打的分?jǐn)?shù)、被評(píng)標(biāo)方打的分?jǐn)?shù)及監(jiān)督方打的分?jǐn)?shù)均為多次參加評(píng)審時(shí)多得分?jǐn)?shù)的平均分。

2.2.3 種群的定義

我們假定本次評(píng)標(biāo)所需的一組專(zhuān)家為一個(gè)種群。評(píng)審專(zhuān)家抽取之前，按照輸入的評(píng)審專(zhuān)家領(lǐng)域條件的要求，把專(zhuān)家?guī)焖性擃I(lǐng)域的專(zhuān)家抽取出來(lái)，然后在這些專(zhuān)家中按照輸入的評(píng)審專(zhuān)家人數(shù)的要求，隨機(jī)抽取出指定的人數(shù)，這個(gè)人數(shù)就是遺傳算法的規(guī)模M，將這些隨機(jī)抽取出來(lái)的專(zhuān)家進(jìn)行數(shù)字化后形成了染色體定義格式的初始種群。在此基礎(chǔ)上經(jīng)過(guò)一系列的復(fù)制、雜交和變異最終產(chǎn)生符合條件的一組專(zhuān)家，將獲得的最終目標(biāo)種群，將染色體格式翻譯成專(zhuān)家?guī)熘械挠涗浶问健⒈敬螌?zhuān)家信息進(jìn)行保存記錄并顯示在輸出設(shè)備上，然后進(jìn)行語(yǔ)音通知，最終確定本次的評(píng)審專(zhuān)家。

2.3 遺傳算法各算子的定義

2.3.1 選擇算子的定義

選擇是對(duì)那些適應(yīng)值高的染色體進(jìn)行選擇，通過(guò)選擇算子將種群中適應(yīng)值高的染色體被選中到交配池中。適應(yīng)值的計(jì)算按如下方法計(jì)算：

專(zhuān)家的適應(yīng)值由3部分構(gòu)成：專(zhuān)家入庫(kù)時(shí)的資格考核成績(jī)、專(zhuān)家每年的考核平均分、專(zhuān)家參加評(píng)標(biāo)項(xiàng)目后由評(píng)標(biāo)單位、被評(píng)標(biāo)單位和監(jiān)管單位進(jìn)行的評(píng)分的平均分[8]。最終值為這三項(xiàng)分?jǐn)?shù)的平均分，對(duì)于未參加過(guò)評(píng)標(biāo)的專(zhuān)家的適應(yīng)值是由（1）和（2）的平均分。按照定義的遺傳算法的規(guī)模M，隨機(jī)選擇的初始群體，依照找出適應(yīng)值最高和最低的評(píng)審專(zhuān)家，進(jìn)行“優(yōu)勝劣汰”，將分?jǐn)?shù)最低的專(zhuān)家首先淘汰。

2.3.2 交叉算子

如：兩個(gè)被選擇的染色體為，包括5部分?jǐn)?shù)據(jù)：領(lǐng)域編碼，專(zhuān)家編碼，單位編碼，學(xué)歷編碼和職稱(chēng)編碼。

1）430 430102 078 1 2 ，其適應(yīng)值 p（1）=98/100

2）430 430088 078 1 2， 其適應(yīng)值 p（2）=96/100

交叉計(jì)算的結(jié)果為：

3）430 430082 078 1 2， 其適應(yīng)值 p（3）=94/100

4）430 430108 078 1 2， 其適應(yīng)值 p（4）=99/100

計(jì)算結(jié)束后檢查編碼為108和082兩位專(zhuān)家的第3、4、5部分?jǐn)?shù)據(jù)以及適應(yīng)度是否與原來(lái)庫(kù)中的所在單位、學(xué)歷和職稱(chēng)是否相同，若不同，則將其所在單位、學(xué)歷和職稱(chēng)以及適應(yīng)度修正為正確的信息。1）和2）交叉的結(jié)果最終是：

3）’430 430082 067 1 3 其適應(yīng)值 p（3）為 98/100 4）’430 430108 067 2 2 其適應(yīng)值 p（4）為 97/100

2.3.3 變異算子

變異是針對(duì)特殊要求而產(chǎn)生的計(jì)算。在文中，引發(fā)變異的條件是2.2中提及的1）2）3）3條特殊條件。個(gè)體是由專(zhuān)家編碼決定的，而變異的基因是由3個(gè)條件決定，即，變異是由專(zhuān)家的單位編碼、學(xué)歷編碼和職稱(chēng)編碼決定的。因此，專(zhuān)家編碼是決定遺傳的主要基因，而單位編碼、學(xué)歷編碼和職稱(chēng)編碼作為變異時(shí)的主要基因，決定著染色體個(gè)體是否發(fā)生變異，但變異的發(fā)生點(diǎn)不是發(fā)生在單位編碼、學(xué)歷編碼和職稱(chēng)編碼上，而是發(fā)生在專(zhuān)家編碼及對(duì)應(yīng)的其他信息上。

比如，針對(duì)條件1），在上述交叉計(jì)算結(jié)束后產(chǎn)生的種群中，檢查第3組數(shù)據(jù)是否有多組數(shù)據(jù)是相同的，即是否有多個(gè)專(zhuān)家均來(lái)自同一單位，若是，則要在第2組數(shù)據(jù)，即對(duì)專(zhuān)家編碼進(jìn)行變異操作，并將其他的響應(yīng)信息也進(jìn)行修改，以保證專(zhuān)家信息的一致性。計(jì)算過(guò)程如下：

檢查 3）4）兩個(gè)染色體，其第3部分?jǐn)?shù)據(jù)均為 067，說(shuō)明他們均來(lái)自青海師范大學(xué)，這不符合“專(zhuān)家不能來(lái)自同一單位”的條件，因此需發(fā)生變異。在3）4）兩組數(shù)據(jù)中隨機(jī)抽取一組數(shù)據(jù)進(jìn)行變異計(jì)算。因?yàn)椴徽摋l件怎么變化，我們最終抽取的專(zhuān)家是由專(zhuān)家號(hào)來(lái)決定，因此，雖然發(fā)生變異的條件由“單位編碼”來(lái)決定，但發(fā)生變異的基因依然是“專(zhuān)家編碼”。假設(shè)，抽取3）組數(shù)據(jù)，變異發(fā)生在082這三位數(shù)中的任何一位，變異的候選值是專(zhuān)家編碼中各位的最大數(shù)以?xún)?nèi)。假設(shè)，本領(lǐng)域?qū)＜揖幋a最大為138，則發(fā)生變異時(shí)的規(guī)則時(shí)，若發(fā)生在第 1位，則由 0變?yōu)?，此時(shí)，第2位變?yōu)?，1，或 2，第3位變?yōu)?0，1，2，3，4，5，6，7，8，9；若發(fā)生在第 2 位或第 3 位，則由 8變?yōu)?0，1，2，3，4，5，6，7，9 均可。 總之，發(fā)生變異后的專(zhuān)家編碼不能大于本領(lǐng)域中的最大專(zhuān)家編碼。編碼發(fā)生變異后，對(duì)應(yīng)的單位號(hào)、學(xué)歷和職稱(chēng)等其他信息也隨著發(fā)生變化，以確保專(zhuān)家信息的正確性。因此，變異后的染色體為:5）430 430109 056 2 2。變異操作結(jié)束后，再檢查其余染色體的單位是否滿足條件，若不滿足繼續(xù)變異，直到滿足條件為止。

同理，針對(duì)2）和3）特殊條件，采用此方法進(jìn)行變異。

2.3.4 終止條件

當(dāng)評(píng)審專(zhuān)家的3個(gè)特殊條件1）2）3）滿足并且循環(huán)T次數(shù)達(dá)到300次時(shí)，循環(huán)終止。

3 實(shí)驗(yàn)數(shù)據(jù)分析

當(dāng)條件中不要求學(xué)歷和職稱(chēng)時(shí)，只要求專(zhuān)家領(lǐng)域?yàn)椴牧峡茖W(xué)時(shí)，在篩選出材料科學(xué)領(lǐng)域所有專(zhuān)家的前提下，隨機(jī)抽取出10名專(zhuān)家，作為初始群體，其個(gè)體的染色體表示及其適應(yīng)值如表1所示。

表1 第0代群體Tab.1 The zeroth generation group

在上表的基礎(chǔ)上進(jìn)行一次選擇計(jì)算之后，將適應(yīng)值最高的個(gè)體在交配池中出現(xiàn)2次，而適應(yīng)值最小的個(gè)體則被淘汰。雜交計(jì)算的結(jié)果如表2所示。

表2 第1代群體Tab.2 The first generation group

在表2中，依據(jù)特殊條件 1）2）3）依次進(jìn)行變異，經(jīng)過(guò) T次的選擇、交叉和變異，最終實(shí)現(xiàn)“優(yōu)勝劣汰”，生成符合條件的10名評(píng)審專(zhuān)家的信息。通過(guò)交叉計(jì)算的結(jié)果，將“優(yōu)”的個(gè)體被選入了交配池，“差”的個(gè)體被淘汰了，但是交叉計(jì)算的結(jié)果并不一定產(chǎn)生“更優(yōu)”的個(gè)體。只是將每一代中相對(duì)“優(yōu)”的個(gè)體生存下去，相對(duì)“差”的個(gè)體被淘汰。經(jīng)過(guò)T次循環(huán)后得到相對(duì)“優(yōu)”的個(gè)體“生存下來(lái)”，所有“劣”的個(gè)體均被淘汰。體現(xiàn)遺傳算法的公正性、公平性和合理性。

4 結(jié)束語(yǔ)

文中采用遺傳算法對(duì)評(píng)標(biāo)項(xiàng)目的評(píng)審專(zhuān)家進(jìn)行抽取，整個(gè)過(guò)程簡(jiǎn)單、方便，一方面比傳統(tǒng)的手工抽取更具有隨機(jī)性、科學(xué)性，另一方面整個(gè)抽取過(guò)程交給計(jì)算機(jī)去實(shí)現(xiàn)，減少人為干擾，體現(xiàn)了公平性、公正性。遺傳算法不但實(shí)現(xiàn)了對(duì)評(píng)審專(zhuān)家的隨機(jī)抽取，也實(shí)現(xiàn)了對(duì)投標(biāo)單位的隨機(jī)抽取。科學(xué)合理的進(jìn)行優(yōu)勝劣汰，使得電子化政府采購(gòu)系統(tǒng)可以發(fā)揮更有效的作用。

[1]邢新嶺，唐明.工程項(xiàng)目的招標(biāo)專(zhuān)家抽取系統(tǒng)的設(shè)計(jì)[J].軟件開(kāi)發(fā)與設(shè)計(jì)，2013（8）:33-35.XING Xin-ling，TANG Ming.Design of the bidding evaluation expert system[J].Software Development and Design，2013（8）:33-35.

[2]牛勇，劉海雄.青海省政府采購(gòu)專(zhuān)家管理系統(tǒng)中專(zhuān)家?guī)斓某槿》椒?[J].青海大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，26（4）：27-31.NIU Yong，LIU Hai-xiong.Extractionm ethod of expert database in the expert managem ent system of Qinghai provincial government[J].Journal of Qinghai University：Nature Science，2008，26（4）：27-31.

[3]童吉.高校設(shè)備采購(gòu)專(zhuān)家抽取和語(yǔ)音通知系統(tǒng)的構(gòu)建[J].實(shí)驗(yàn)技術(shù)與管理，2013，30（5）:221-223.TONG Ji.Construction an expert-choosing and voice-notification system for equipment procurement in colleges and universities[J].Experimental Technology and Management，2013，30（5）:221-223。

[4]杜浩.基于遺傳算法的FMS調(diào)度問(wèn)題研究[D].武漢：湖北工業(yè)大學(xué)，2014.

[5]王巍，劉云.鐵路工程招標(biāo)專(zhuān)家抽取系統(tǒng)設(shè)計(jì)[J].鐵路計(jì)算機(jī)應(yīng)用，2011，20（4）:34-36.WANG Wei，LIU Yun.Design of experts extracting smart system in tender of railway construction[J].Railway Computer Application.2011，4.20（4）:34-36.

[6]覃奕.評(píng)標(biāo)專(zhuān)家系統(tǒng)設(shè)計(jì)[J].廣西科學(xué)院學(xué)報(bào)，2014，30（1）:1-4.Tang Yi.Designofthe Bidding Evaluation Expert System[J].Journal of Guangxi Academy of Sciences.2014，30（1）:1-4

[7]宋駿豪.一種基于遺傳算法的保險(xiǎn)方案智能推薦方法[J].計(jì)算機(jī)與現(xiàn)代化，2013（215）:80-83.SONG Jun-hao.An intelligent recommendation approach for insurance scheme based on genetic algorithm[J].Jisuanji Yu Xiandaihua，2013（215）:80-83.

[8]周云端，何志勇，趙瑞國(guó).基于遺傳算法的加速度控制PID參數(shù)自整定研究[J].火箭推進(jìn)，2012（4）:68-71.ZHOU Yun-duan，HE Zhi-yong，ZHAO Rui-guo.Study on genetic algorithm based auto-tuning of acceleration control PID parameters[J].Journal of Rocket Propulsion，2012（4）:68-71.