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

李春梅，劉海雄

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

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

1 專家隨機抽取的要求及抽取的條件

1.1 專家隨機抽取的要求

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

1.2 專家隨機抽取的條件設(shè)置

圖1 評審專家抽取過程Fig.1 The extraction process of evaluation experts

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

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

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

2.1 遺傳算法介紹

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

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

2.2 遺傳算法設(shè)計

2.2.1 基因和染色體的定義

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

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

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

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

2.2.3 種群的定義

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

2.3 遺傳算法各算子的定義

2.3.1 選擇算子的定義

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

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

2.3.2 交叉算子

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

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

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

交叉計算的結(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

計算結(jié)束后檢查編碼為108和082兩位專家的第3、4、5部分?jǐn)?shù)據(jù)以及適應(yīng)度是否與原來庫中的所在單位、學(xué)歷和職稱是否相同，若不同，則將其所在單位、學(xué)歷和職稱以及適應(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 變異算子

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

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

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

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

2.3.4 終止條件

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

3 實驗數(shù)據(jù)分析

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

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

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

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

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

4 結(jié)束語

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

[1]邢新嶺，唐明.工程項目的招標(biāo)專家抽取系統(tǒng)的設(shè)計[J].軟件開發(fā)與設(shè)計，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]牛勇，劉海雄.青海省政府采購專家管理系統(tǒng)中專家?guī)斓某槿》椒?[J].青海大學(xué)學(xué)報：自然科學(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è)備采購專家抽取和語音通知系統(tǒng)的構(gòu)建[J].實驗技術(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)度問題研究[D].武漢：湖北工業(yè)大學(xué)，2014.

[5]王巍，劉云.鐵路工程招標(biāo)專家抽取系統(tǒng)設(shè)計[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]覃奕.評標(biāo)專家系統(tǒng)設(shè)計[J].廣西科學(xué)院學(xué)報，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]宋駿豪.一種基于遺傳算法的保險方案智能推薦方法[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]周云端，何志勇，趙瑞國.基于遺傳算法的加速度控制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.