顧 小 林，浦 徐 進，曹文彬

（1.江南大學(xué),江蘇 無錫 214122；2.河海大學(xué),江蘇 南京210098）

一、引言

目前食用農(nóng)產(chǎn)品采購的特點是品種繁多、批量龐大，包括交貨期限、支付形式等許多不同因素。采購模式是非信息對稱博弈過程，響應(yīng)用戶需求時間緩慢，供需關(guān)系是短期的或臨時的，且競爭多于合作，[1]對供應(yīng)商產(chǎn)品質(zhì)量無法進行事前控制，因此導(dǎo)致采購成本較高。

由此提出在食用農(nóng)產(chǎn)品采購中采用網(wǎng)上反向拍賣采購模式。這一模式不影響企業(yè)原有的供應(yīng)鏈管理模式，可以降低采購成本，防止暗箱操作，特點是買方確定采購標(biāo)準(zhǔn)，賣方進行競標(biāo)，競價過程中價格隨時間的推移不僅不上升反而下降，買方將待購物品列出，賣方通過競價獲得訂單，買賣雙方簽訂采購合同，可以對采購合同組合反向拍賣進行優(yōu)化，達到降低采購成本的目的。[2]

二、食用農(nóng)產(chǎn)品采購合同組合反向拍賣的優(yōu)化

1.建立食用農(nóng)產(chǎn)品采購合同組合反向拍賣的相關(guān)模型

（1）規(guī)定建立食用農(nóng)產(chǎn)品采購合同組合反向拍賣模型的若干前提

在此實施食用農(nóng)產(chǎn)品采購合同組合反向拍賣及建立模型的前提，需要以下幾個方面均符合。[3]第一，在規(guī)定時間內(nèi)，各投標(biāo)供應(yīng)商密封并提交其標(biāo)書，投標(biāo)供應(yīng)商中采購成本最低的中標(biāo)。第二，限制每個供應(yīng)商單項產(chǎn)品供應(yīng)量的上限、下限及供應(yīng)總量的上限、下限。第三，每種產(chǎn)品的采購數(shù)量較大，供應(yīng)商因此可以進行價格折扣。第四，每個供應(yīng)商對若干種或所有的采購合同競標(biāo)。第五，不同質(zhì)產(chǎn)品的采購合同由多個供應(yīng)商競標(biāo)。第六，同一時間拍賣多個不同質(zhì)產(chǎn)品的采購合同。第七，限制中標(biāo)的供應(yīng)商人數(shù)。第八，采購方只有一個。

（2）食用農(nóng)產(chǎn)品供應(yīng)商的供應(yīng)函數(shù)

通常供應(yīng)商供應(yīng)產(chǎn)品的單位價格是采購量的下降階梯函數(shù)，供應(yīng)函數(shù)見公式1。[4]

其中，供應(yīng)參數(shù)是{（l，Q1，Q2，Q3，h），（Z1，Z2，Z3，Z4）}。[l，h]是供應(yīng)商的供應(yīng)能力區(qū)間，Qi（i=1，2，3）、Zi（i=1，2，3，4）、l和 h 是正值常數(shù)，lZ2>Z3>Z4。

（3）食用農(nóng)產(chǎn)品采購合同組合反向拍賣最優(yōu)供應(yīng)模式的模型

假定一個食用農(nóng)產(chǎn)品采購商為了滿足采購需求以及采購價格最低，借助采購合同組合反向拍賣模式采購食用農(nóng)產(chǎn)品，在眾多供應(yīng)商提供的多種食用農(nóng)產(chǎn)品供應(yīng)情況中，采購商需要決策選擇最佳的一組供應(yīng)模式組合，由此建立食用農(nóng)產(chǎn)品采購合同組合反向拍賣的最優(yōu)組合供應(yīng)模式的數(shù)學(xué)模型，以便進行智能決策，數(shù)學(xué)模型[5]如下所示。

其中相關(guān)符號定義如下：M定義為需要采購的農(nóng)產(chǎn)品種類數(shù)量；Qm定義為每種農(nóng)產(chǎn)品的需求量；V=（a1v，a2v，…，amv）定義為對 M 種農(nóng)產(chǎn)品的供應(yīng)數(shù)量為v的供應(yīng)模式；N定義為供應(yīng)商的數(shù)目；Vn定義為供應(yīng)商n的供應(yīng)模式集合；定義為第n個供應(yīng)商對第m個農(nóng)產(chǎn)品供應(yīng)量的下限；定義為第n個供應(yīng)商對第m個農(nóng)產(chǎn)品供應(yīng)量的上限。

則供應(yīng)商n提供農(nóng)產(chǎn)品總量的限制定義為：

對第n個供應(yīng)商提供數(shù)量為v的采購成本定義為：

相關(guān)決策變量定義如下：

式（2）目標(biāo)函數(shù)表明采購成本需達到極小，式（3）約束限制了食用農(nóng)產(chǎn)品的采購需求，式（4）限制了每個食用農(nóng)產(chǎn)品供應(yīng)商對某個食用農(nóng)產(chǎn)品的供應(yīng)數(shù)量，式（5）限定每個食用農(nóng)產(chǎn)品供應(yīng)商有且只有一種供應(yīng)模式，式（6）限制了符合標(biāo)的的食用農(nóng)產(chǎn)品供應(yīng)商人數(shù)，式（7）約束了食用農(nóng)產(chǎn)品供應(yīng)商的模式選擇。上述式（2）~（7）表明需求解0-1整數(shù)規(guī)劃問題。

由式（2）~（7）模型分析可以得出，隨著供應(yīng)商數(shù)量N及采購食用農(nóng)產(chǎn)品數(shù)量M的增加，食用農(nóng)產(chǎn)品多物品采購合同供應(yīng)模式的組合數(shù)呈現(xiàn)指數(shù)增長。為了滿足食用農(nóng)產(chǎn)品的采購需求以及實現(xiàn)采購價格最低，食用農(nóng)產(chǎn)品多個供應(yīng)商的供應(yīng)模式組合具備組合意義，理論上最優(yōu)組合供應(yīng)模式存在并可解。[6]

2.基于OO競爭策略的自適應(yīng)遺傳算法確定食用農(nóng)產(chǎn)品組合供應(yīng)模式的最優(yōu)解

求解食用農(nóng)產(chǎn)品最優(yōu)組合供應(yīng)模式的問題可轉(zhuǎn)化為兩個層面的優(yōu)化問題，[7]如圖1所示。

圖中，上層是求解食用農(nóng)產(chǎn)品供應(yīng)商的組合優(yōu)化問題，下層是求解在限定供應(yīng)商范圍內(nèi)的多種物品最優(yōu)組合的供應(yīng)問題。通過對一個食用農(nóng)產(chǎn)品最優(yōu)組合供應(yīng)模式確定的動態(tài)規(guī)劃算法的多次循環(huán)調(diào)用，來求解下層優(yōu)化問題，下層優(yōu)化問題的計算結(jié)果用于解決上層優(yōu)化問題。[8]但是在求解上層優(yōu)化問題時存在NP難題，因為如果食用農(nóng)產(chǎn)品的供應(yīng)商人數(shù)N太大，則從N中選取b（L≤b≤H）的組合數(shù)過大，于是求解0-1整數(shù)規(guī)劃模型形成NP難題。[9]自適應(yīng)遺傳算法可用于求解變長染色體的離散組合優(yōu)化問題，且求解組合優(yōu)化問題較傳統(tǒng)算法效果較為明顯，[10]在此采取基于OO競爭策略的自適應(yīng)遺傳算法對上述0-1規(guī)劃模型求解。[11]

（1）基于OO競爭策略的自適應(yīng)遺傳算法

OO（One to One）競爭策略的自適應(yīng)遺傳算法的主要思想，是在遺傳算法中借助Player Killing賽式的競爭篩選尋找全局最優(yōu)解。執(zhí)行變異操作前即時檢測全程最優(yōu)解，并且配合交叉率自適應(yīng)地動態(tài)調(diào)整個體粒度，以避免算法陷入局部極值點，而且減少退化現(xiàn)象，同時引入復(fù)活賽機制，提高算法收斂到全局最優(yōu)解的概率。[12]

圖1 食用農(nóng)產(chǎn)品多物品最優(yōu)組合供應(yīng)模式兩層優(yōu)化

基于OO競爭策略的自適應(yīng)遺傳算法有以下特點：

①從算法內(nèi)部解決遺傳算法的局部搜索能力不足問題。傳統(tǒng)上均從外部引入優(yōu)化算法，[13]基于OO競爭策略的自適應(yīng)遺傳算法不從外部引入任何方法，而是在算法中首先設(shè)置較大的交叉率與變異率，可以提高全局及局部的搜索能力。[14]其次，變異算子僅當(dāng)算法檢測到當(dāng)前代種群的最佳適應(yīng)度和父代對比未改進時，才參與執(zhí)行變異并進行局部搜索。

②提高了算法搜索到全局最優(yōu)解的概率。此算法采取兩種方式，首先設(shè)定較大的種群規(guī)模，有利于提高全局搜索效率。其次采用復(fù)活賽機制，復(fù)活賽機制中借助選擇算子配合替換算子來實現(xiàn)，在算法執(zhí)行過程中，每一代的最優(yōu)個體取代最劣個體，在算法結(jié)束的前一代剩下一優(yōu)一劣兩個個體，兩個個體執(zhí)行替換操作后變得相同，當(dāng)進行選擇操作時，兩個個體都進入下一代的進化并進行下一輪的競賽。引入復(fù)活賽機制提高了全局最優(yōu)解與全程最優(yōu)個體吻合的概率。[15]

③交叉率與變異率的自適應(yīng)調(diào)整細化到了個體粒度上。傳統(tǒng)方法交叉率與變異率的自適應(yīng)調(diào)整局限在種群粒度上，而在此算法中，每一代每一種群中的每一個體的交叉率及變異率，均依據(jù)自身的適應(yīng)度和當(dāng)前種群的平均適應(yīng)度進行自適應(yīng)的動態(tài)調(diào)整。在此是求適應(yīng)度函數(shù)的最小值，則交叉率與變異率分別按式（14）設(shè)置，即當(dāng)本代平均適應(yīng)度小于被選中進行交叉的兩個個體的適應(yīng)度時，則交叉率自動升高，反之則自動降低，減少進化過程中的退化現(xiàn)象。

④適應(yīng)度函數(shù)不再局限于非負的范圍，在此將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，避免了目標(biāo)函數(shù)和適應(yīng)度函數(shù)相互轉(zhuǎn)化時產(chǎn)生的映射誤差，不僅降低了轉(zhuǎn)換計算的復(fù)雜度，而且提高了算法的效率。[16]

⑤采用不同于傳統(tǒng)的方法設(shè)定初始種群規(guī)模。種群規(guī)模會影響傳統(tǒng)遺傳算法的運算效率，過大的種群規(guī)模會導(dǎo)致程序運行時間太長及算法收斂非常緩慢，而過小的種群規(guī)模會導(dǎo)致搜索能力不足及找不到全局最優(yōu)解。而在此算法中，初始種群規(guī)模越大，算法的搜索能力越強，因為種群規(guī)模幾乎以減半的速度隨算法的運行不斷減小。[17]

⑥總體的進化策略與傳統(tǒng)遺傳算法不同。此算法在進化過程中，不再固定種群規(guī)模，同時不再限定進化代數(shù)，系統(tǒng)通過個體的競爭，自動選擇更符合優(yōu)化目標(biāo)的個體進入下一代。采用這種選擇策略結(jié)合最優(yōu)個體保存策略，隨著進化代數(shù)的增加種群規(guī)模不斷減小，直至最后只剩下一個全程最優(yōu)個體，即為全程最優(yōu)解。此進化篩選策略保證算法能夠以極快的速度收斂。

（2）基于OO競爭策略的自適應(yīng)遺傳算法的編碼方法

基于OO競爭策略的自適應(yīng)遺傳算法的編碼方法采取二元組編碼，[18]一個染色體個體可用X=[（i1，d1），（i2，d2），…，（im，dm）]表示。其中im代表基因座編號，對應(yīng)的基因值是dm。其值的選取需符合染色體兩個方面的要求：

①染色體長度的要求。在此設(shè)定常規(guī)染色體的長度為H，最短染色體的長度為L。用im∈I={1，2，…，H}表示基因座編號，用 dm∈D={1，2，…，N}表示某一標(biāo)書的編號，即是對應(yīng)的基因值。

②染色體中基因座對應(yīng)基因值的要求。因為L表示染色體的最短長度，所以對某個單項農(nóng)產(chǎn)品假定有L個供應(yīng)商，采購商對該項農(nóng)產(chǎn)品的需求，通過L個供應(yīng)商對該項農(nóng)產(chǎn)品的總供應(yīng)能夠得到滿足。為了符合染色體的要求，在基因值對應(yīng)供應(yīng)商的供應(yīng)模式中，對每種農(nóng)產(chǎn)品至少有L個供應(yīng)商進行供應(yīng)。

（3）適應(yīng)度函數(shù)

此算法把適應(yīng)度函數(shù)作為目標(biāo)函數(shù)。[19]因為在實際應(yīng)用中的優(yōu)化問題大多數(shù)都可以轉(zhuǎn)化為數(shù)值函數(shù)的優(yōu)化問題。

給定一個染色體等于給定了一組固定的供應(yīng)商集合，由此可以用動態(tài)規(guī)劃算法算出該組供應(yīng)商的最優(yōu)組合供應(yīng)目標(biāo)函數(shù)值。

對于求最小值的問題，目標(biāo)函數(shù)f（X）可為如下適應(yīng)度函數(shù)F（X）：

其中，Cmax是本代染色體中目標(biāo)函數(shù)的最大值。

（4）設(shè)定交叉率和變異率

在基于OO競爭策略的自適應(yīng)遺傳算法中，遺傳操作的控制變量是根據(jù)個體的評估賦值情況隨時修正的。交叉率與變異率根據(jù)優(yōu)化目標(biāo)分別按如下公式計算。[20]

（5）基于OO競爭策略自適應(yīng)遺傳算法的計算步驟

第一步：初始化。設(shè)置種群規(guī)模SP、交叉率pc、變異率 pm，置 m=0；隨機生成初始種群 POP（0）={X1，X2，…，Xm}；對于第二層優(yōu)化， 用動態(tài)規(guī)劃算法精確求解，對每個個體解碼，計算每個個體目標(biāo)函數(shù)值，設(shè)置初始歷史最好解 X（*），最優(yōu)目標(biāo)值 F（*）=F（X（*））。

第二步：m=m+1。當(dāng)種群規(guī)模大于1時，用動態(tài)規(guī)劃算法精確求解進行第二層優(yōu)化，對每個個體解碼，計算每個個體的適應(yīng)度函數(shù)F（Xj），按由大到小順序排列。

第三步：執(zhí)行雜交操作。由上面給出的雜交算子產(chǎn)生中間后代，用動態(tài)規(guī)劃算法精確求解進行第二層優(yōu)化，求出中間后代的適應(yīng)度以及所有中間后代中的最優(yōu)個體。

第四步：記錄到當(dāng)前代為止最符合優(yōu)化目標(biāo)個體的最小適應(yīng)度。如果新的最優(yōu)目標(biāo)值與歷史最優(yōu)目標(biāo)值相等，則執(zhí)行變異操作。由上面給出的變異算子對每一個被選的后代進行變異，產(chǎn)生后代。用動態(tài)規(guī)劃算法精確求解進行第二層優(yōu)化，求出變異后代的適應(yīng)度。

第五步：當(dāng)?shù)趇個個體的適應(yīng)度小于等于當(dāng)前代種群的平均適應(yīng)度時，進行選擇操作。由上面給出的選擇算子，在當(dāng)前種群和所有后代中選出最優(yōu)個體。記錄新的最優(yōu)目標(biāo)值、最劣值，用歷史最優(yōu)目標(biāo)值代替最劣值。

第六步：當(dāng)種群規(guī)模大于SP時，輸出最優(yōu)解X（*）及最優(yōu)目標(biāo)值 F（X（*）），進化結(jié)束。

否則結(jié)束本次循環(huán)，轉(zhuǎn)第二步。

3.基于OO競爭策略自適應(yīng)遺傳算法組合招標(biāo)的仿真實例

在計算機上對此問題進行仿真，實驗環(huán)境是Windows XP，編程語言為Java，編制基于OO競爭策略自適應(yīng)遺傳算法，此問題用“標(biāo)書數(shù)/待組合反向拍賣采購的食用農(nóng)產(chǎn)品數(shù)/允許中標(biāo)的食用農(nóng)產(chǎn)品供應(yīng)商人數(shù)區(qū)間”描述，在此列舉一個由20/8[3，6]組成的多食用農(nóng)產(chǎn)品最優(yōu)組合供應(yīng)模式說明，其中20是供應(yīng)商的標(biāo)書個數(shù)，8是待組合反向拍賣采購的食用農(nóng)產(chǎn)品種類數(shù)，[3，6]是允許中標(biāo)的食用農(nóng)產(chǎn)品供應(yīng)商人數(shù)區(qū)間。

在此食用農(nóng)產(chǎn)品供應(yīng)商的標(biāo)書標(biāo)號分別用1～20表示，食用農(nóng)產(chǎn)品種類分別用英文字母S1~S8表示。表1是食用農(nóng)產(chǎn)品采購合同的信息，其中規(guī)定了食用農(nóng)產(chǎn)品供應(yīng)商對每種產(chǎn)品提供數(shù)量的下限和上限，基于OO競爭策略自適應(yīng)遺傳算法的參數(shù)Pc=0.95，Pm=1，SP=1000，表 2 給出食用農(nóng)產(chǎn)品采購合同最優(yōu)組合供應(yīng)模式的計算結(jié)果。

表2中的后五列單元格內(nèi)的括號外數(shù)字表示此單元格所在列對應(yīng)的食用農(nóng)產(chǎn)品供應(yīng)商采購此單元格所在行對應(yīng)食用農(nóng)產(chǎn)品的采購量，括號內(nèi)的數(shù)字表示此單元格括號外的食用農(nóng)產(chǎn)品供應(yīng)商采購量的采購價格。

表1 食用農(nóng)產(chǎn)品采購合同的信息

表2 最優(yōu)組合供應(yīng)模式的計算結(jié)果

最后中標(biāo)的食用農(nóng)產(chǎn)品供應(yīng)商的標(biāo)號為（4，7，10，16，18）。 采購總支出的計算過程如下：

采購總支出=130*21+105*12+100*14+90*22+70*17+50*21+45*12+113*20+82*15+60*23+60*16+70*20+45*13+130*20+100*11+85*13+90*20+60*23+100*22+110*11+60*11+107*12+88*16+80*15=32782（元）。

綜上所述，一個由20/8[3，6]組成的多食用農(nóng)產(chǎn)品最優(yōu)組合供應(yīng)模式的采購總支出為32782元。

三、結(jié)語

在食用農(nóng)產(chǎn)品供應(yīng)采購中采用網(wǎng)上反向拍賣采購模式，從根本上對采購方式及其交易模式進行了變革，通過對食用農(nóng)產(chǎn)品供應(yīng)采購合同的組合反向拍賣優(yōu)化降低了采購成本，解決了目前供應(yīng)采購中存在的問題。

在食用農(nóng)產(chǎn)品采購合同組合反向拍賣的優(yōu)化中，建立了食用農(nóng)產(chǎn)品最優(yōu)組合供應(yīng)模式的模型，設(shè)計了求解此模型的算法，算法包括第一層優(yōu)化采取動態(tài)規(guī)劃算法精確求解，第二層優(yōu)化采取OO競爭策略的自適應(yīng)遺傳算法求解，并通過仿真實例證明了設(shè)計算法的有效性和模型的普適性。

食用農(nóng)產(chǎn)品采購合同組合反向拍賣的優(yōu)化還需要進一步完善，今后的研究可以從以下兩方面進行：

在現(xiàn)有算法基礎(chǔ)上改進算法。進一步提高算法的收斂速度以及運算效率。

在按需應(yīng)變環(huán)境下改進模型及算法。為了適應(yīng)動態(tài)環(huán)境的多變性，增強現(xiàn)有模型和算法的普適性和靈活性，需要改造現(xiàn)有模型和算法，構(gòu)建下層的仿真模型、設(shè)計上層的優(yōu)化算法以及提高仿真優(yōu)化的計算效率等。

[1]陳培友，汪定偉．多物品最優(yōu)組合供應(yīng)模式確定問題的模型研究[J]．中國管理科學(xué)，2006，14（4）：35-39．

[2]Wurman P．R．，Walsh W．E．，Wellman M．P．.Flexible Double Auctions for Electronic Commerce：Theory and Implementation[J]．Decision Support Systems，1998，24（1）：17-27.

[3]Emiliani M．L.．Business to Business Online Auctions:Key Issues for Purchasing Process Improvement[J]．Supply Chain Management，2000，5（4）：305-315.

[4]高鴻業(yè)．西方經(jīng)濟學(xué)（微觀部分）[M]．北京：中國人民大學(xué)出版社，2011：24-26．

[5]尹伯成．西方經(jīng)濟學(xué)簡明教程[M]．上海：格致出版社，2011：65-66．

[6]于春田，李法朝，惠紅旗．運籌學(xué)[M]．北京：科學(xué)出版社，2011：143-145．

[7]王旭，葛顯龍，林云．供應(yīng)商選擇的雙層規(guī)劃模型及求解分析[J]．計算機工程與應(yīng)用，2009，45（23）：11-14．

[8]唐立新，孫德剛．單一品種項目的生產(chǎn)批量問題的動態(tài)規(guī)劃算法[J]．東北大學(xué)學(xué)報（自然科學(xué)版），1999，20（4）：373-375．

[9]Cohen L.，K.Diether C.Malloy.Supply and Demand Shift in the Shorting Market[J]．Journal of Finance，2007，59：1845-1875.

[10]Lebrun B..A Continuity of the First Price Auction Nash Equilibrium Correspondence [J]．Economic Theory，2002，20（3）：435-453.

[11]諸克軍，李蘭蘭，郭海湘．一種融合遺傳算法和粒子群算法的改進模糊C-均值算法[J]．系統(tǒng)管理學(xué)報，2011（6）：728-733．

[12]N.van Hoom J.Togelius D.Wierstra，J.Schmidhuber.Robust Player Imitation Using Multiobjective Evolution[M]．//Proceedings of IEEE Congress on Evolutionary Computation，2009：652-659.

[13]J.Wu，L.Chen，L.Yang，Q.Zhang，L.Peng.A Collision Detection Algorithm based on Self-adaptive Genetic Method in Virtual Environment[M]．//Proceedings of the 1st International Conference on Swarm Intelligence，2010：461-468.

[14]B.B.Li，Z.H.Zhao.Fitness Function Optimized in Genetic Algorithm for Fabric Dynamic Simulation[M]．//Proceedings of IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application，2008：59-63.

[15]謝安世，周傳華，徐新衛(wèi)，張芬．基于PK模型的一種自適應(yīng)遺傳算法研究 [J]．計算機工程與應(yīng)用，2010，46（7）：52-56．

[16]江中央，蔡自興，王勇．用于全局優(yōu)化的混合正交遺傳算法[J]．計算機工程，2009，35（4）：204-206．

[17]張思才，張方曉．一種遺傳算法適應(yīng)度函數(shù)的改進方法[J]．計算機應(yīng)用與軟件，2006，23（2）：108-110．

[18]徐文婷，李承鵬．基于自適應(yīng)遺傳算法的離散化方法[J]．合肥師范學(xué)院學(xué)報，2011（3）：14-17．

[19]郭華芳，劉海利，李海生，張嚴(yán)林．用變長度染色體遺傳算法優(yōu)化加工路徑的方法[J]．計算機工程與應(yīng)用，2009，45（6）：207-209．

[20]黃江波，付志紅．基于自適應(yīng)遺傳算法函數(shù)優(yōu)化與仿真[J]．計算機仿真，2011（5）：237-240．