基于需求度隨機算法在購車搖號中的研究

吳子珺，于重重，馬 萌，商利利

（北京工商大學 計算機與信息工程學院，北京100048）

0 引 言

由于經(jīng)濟的高速發(fā)展，車輛總數(shù)的過快增長，導致現(xiàn)有交通的承載能力趨于飽和，尤其是一些大型城市的交通問題日益突出。因此各地方政府相繼出臺了購車搖號政策，以解決交通擁堵等一系列問題。為此，如何在搖號過程中保證其公平，合理就越顯得尤為重要。

目前，使用計算機生成隨機數(shù)的方法主要有兩種:物理法和數(shù)學法[1]。由于二者工作機理的不同，數(shù)學法憑借其具有的隨機數(shù)分布均勻，統(tǒng)計性能良好等特性，在實際的抽簽、搖號活動中得到了廣泛的使用。實踐表明，現(xiàn)有的購車搖號系統(tǒng)中所采用的這種以數(shù)學法為基礎，將抽得的元素與前面以獲取的元素進行比對，除去相同項，保證抽取元素不同的傳統(tǒng)隨機抽樣方法，存在申請人員 “久搖不中”、需求度低等一系列問題。因此，本文將粗糙集理論、模糊綜合評價方法與隨機抽樣算法相結(jié)合，以此來完成申請人員需求度等級的評定，并按需求度完成分配，以達到保證其公平，合理的目的。

1 現(xiàn)行隨機算法及存在問題

在偽隨機數(shù)產(chǎn)生的算法中，最早所使用的是平方取中法和移位法，雖然這兩種算法在計算機上都易于實現(xiàn)并且占用內(nèi)存較少，但是都存在對初始值依賴性強，均勻性不好，數(shù)列長度和周期難以確定等問題。目前，在現(xiàn)有的搖號系統(tǒng)中主要使用的隨機算法是由Lehmer于1951年提出的線性同余發(fā)生器LCG（linear congruence generator）[2]。

遞推公式為

其中，M為模數(shù)，a為乘子，c為增量，xn，M，a，c均為非負數(shù)，rn為產(chǎn)生的隨機數(shù)。當式 （1）中的參數(shù)合適選取時，即可以得到統(tǒng)計意義上滿意的隨機數(shù)。通過采用這種方法生成的偽隨機數(shù)序列，雖然在給定的范圍和精度內(nèi)確實可以到達均勻分布的要求，但是其結(jié)果具有一定的周期性，這是由于計算機尾數(shù)字長的不足，其周期長度受到了限制，同時也導致了該序列擁有可辨別模式，其規(guī)律可通過少量數(shù)據(jù)反推得到。

因此，在實際的使用中，雖然致力于保證公平公正，但其也在某程度上引發(fā)了多方面的不合理。

（1）指標浪費現(xiàn)象嚴重

根據(jù)北京市公布的2011年購車指標浪費情況統(tǒng)計得出[3]，截至2011年6月申請指標人數(shù)已達577856人，其中1～6月份共配置個人指標105600個，共產(chǎn)生未使用個人配置指標總數(shù)10401個，占產(chǎn)生個人指標總數(shù)的9.85%，因此，指標浪費現(xiàn)象比較嚴重。

（2）需求度不同人群和等待時間不同人群的中簽概率相同

目前所使用的搖號隨機算法是一個應用普遍并經(jīng)過實踐證明的遞推公式，不能根據(jù)不同申請者的需求度，完成合理的調(diào)整，因此在實際的應用中存在人性化不足等問題。

（3）被抽中概率隨著等待時間而降低

通過分析從北京市小客車指標調(diào)控管理信息系統(tǒng)[3]中獲得的個人指標相關數(shù)據(jù)，得到原隨機算法搖號過程中中簽率隨時間變化趨勢，如圖1所示。

圖1 原隨機算法搖號過程中中簽率隨時間變化趨勢

由圖1可以看出，原隨機算法中申請者的中簽率隨時間呈現(xiàn)很明顯的下降趨勢，隨著等待時間的變長和搖號基數(shù)的變大，申請者被選中的概率越來越小。

因此，尋求新的算法解決上述應用中所存在的問題是十分必要和迫切的。

2 基于需求度的改進隨機算法 （demand degree－RA）

需求度，即需求強度，是指對某種商品 （物品）需求的迫切程度。因此，在搖號的過程中，為了使算法富有人性化特點，如何準確地確定申請者的需求度則成為一個關鍵步驟，其是對購車指標有效分配的重要依據(jù)。因此，針對原有隨機算法的不合理，在搖號算法中引入了需求度，并考慮綜合利用粗糙集理論和模糊綜合評價方法計算申請者的購車需求度。其基本思想是:利用粗糙集理論完成二級指標權重的求取[4，5]，然后利用模糊綜合評價方法求出需求度的隸屬度，隸屬度最大的即為判定等級結(jié)果?；具^程如下:

（1）根據(jù)分析建立評價指標體系；

（2）粗糙集理論為各個評價指標分配權重；

（3）模糊綜合評價方法判定需求的等級。

2.1 評價指標體系建立

根據(jù)申請搖號人員對汽車的需求度設定申請者對汽車的需求度為一級指標；家中已有車輛、等待時間和家庭特殊人員為二級指標。其中，家中已有車輛指的是申請者家中當前已有車輛數(shù)量；等待時間為迄今為止，申請者搖號等待時間 （以月為單位）；家庭特殊人員指的是申請者家中特殊人員的數(shù)量，包括殘疾人、行動不便的老人或是嬰幼兒。其具體取值為其對應的數(shù)量值。3個二級指標中主要包括了如下6類特殊申請者:急需用車家庭、申請首車家庭、申請非首車家庭、等待時間10個月以上、等待時間15個月之上和等待時間20個月之上的申請者。

2.2 基于粗糙集理論的評價指標權重分配

由于各個條件屬性的重要程度的不一致性，因此需要通過計算權重來完成各個屬性的量化。在粗糙集中，采用逐次去掉一個屬性觀察分類結(jié)果變化程度的方法，觀察該屬性的影響力大小。若去除該屬性后其分類結(jié)果變化較大，則認為該屬性的影響力較大，若其分類結(jié)果變化較小，則認為該屬性的影響力較小。通過此種方法，即可完成屬性權重的計算，其因素權重獲取流程如下所示:

（1）導出指標因素具體數(shù)據(jù)；

（2）SOM神經(jīng)網(wǎng)絡聚類[6]；

（3）連續(xù)數(shù)據(jù)離散化；

（4）粗糙集理論分配權重[7，8]。

其中，粗糙集分配權重的計算過程如下:

（1）定義:

對象集U＝｛u1，u2，…，ul｝；

條件屬性C＝｛c1，c2，…，cn｝；

決策屬性D＝｛d1，d2，d3，d4｝。

（2）刪除條件屬性Ci（i＝1，2，…，n），并確定刪除條件屬性Ci后的最佳分類集Yl。

（3）求解決策屬性的各等價集的正域

（4）計算兩個屬性集的依賴程度

（5）求解屬性Ci的重要程度

（6）計算每個條件屬性的權重

2.3 基于模糊綜合評價方法的需求等級判定

該方法的基本思想是利用模糊綜合評價方法[9－11]來評估一個申請者的需求度級別，隸屬度最高的級別即為最后的判定結(jié)果。目前，模糊綜合評價方法主要分為兩步:第一步先按每個因素單獨評價；第二步再按所有的因素綜合評價。其具體步驟如下所示:

（1）確定模糊綜合評價因素組成的集合U，給出評價因素的評語集V；

（2）進行單因素評價，建立模糊關系矩陣珟R，并確定評價因素的模糊權向量，即

（3）利用合適的合成算子將W與被評價事物珟R合成得到各被評價事物的模糊綜合評價結(jié)果向量珟B；對模糊綜合評價結(jié)果向量進行分析。

在購車搖號過程中利用模糊綜合評價判別需求度的具體過程如下:

（1）建立評語集

V＝｛V1（一級需求），V2（二級需求），V3（三級需求），V4 （四級需求）｝。

（2）計算因素權重

因素權重根據(jù)上述粗糙集理論方法來計算。

（3）構(gòu)建隸屬函數(shù)

為了簡化并統(tǒng)一隸屬函數(shù)，用歸一化的方法構(gòu)建隸屬函數(shù)模型。

歸一化公式:對于區(qū)間（m，n）上的數(shù)值，將其歸一化到區(qū)間（0，1）上之后，區(qū)間上的一個數(shù)值x對應的區(qū)間（0，1）上的數(shù)值為。隸屬度函數(shù)類型較多，經(jīng)過反復實驗比較和理論分析，我們認為三角函數(shù)是較為合適的隸屬度函數(shù)。3個指標中，家中已有車輛越多，需求度越低；家庭特殊人員越多，需求度越高；等待時間越長，需求度越高。為此，我們定義兩個隸屬度函數(shù)。家中已有車輛指標隸屬度函數(shù)如圖2所示，等待時間和家庭特殊人員指標隸屬度函數(shù)如圖3所示。

圖4所示4條直線a，b，c，d分別代表二級指標對 “一級、二級、三級、四級”的隸屬度函數(shù)。圖4所示四條直線a，b，c，d分別代表二級指標對 “四級、三級、二級、一級”的隸屬度函數(shù)。其直線方程分別為

圖2 隸屬函數(shù)1

圖3 隸屬函數(shù)2

根據(jù)上述隸屬度函數(shù)，可得到各個因素對語集中評語的隸屬度。

（4）選擇模糊合成算子

模糊合成算子的類型有很多種，常用的兩種是加權平均型和主因素突出型。該模型中選用了加權平均型，因為它是對各因素的相對權重和模糊關系矩陣的綜合處理，可以避免信息丟失?，F(xiàn)實問題的實際性質(zhì)決定了模糊算子的選擇。

2.4 Demand degree－RA 算法流程

整體流程如圖4所示。

設定搖號基數(shù)為N，預配置指標數(shù)為n。Demanddegree－RA算法流程如下:

（1）確定申請者樣本

申請者＝｛序號，搖號基數(shù)，申請編號，姓名，家中已有車輛，等待時間，家庭特殊人員｝。

（2）根據(jù)粗糙集理論和模糊綜合評價法估計樣本集中每個申請者的需求度等級。

（3）指標預抽取

利用偽隨機數(shù)抽取算法隨機抽取三倍于預配置指標數(shù)量的指標，即數(shù)量為3n。

（4）計算指標分配情況

按照需求度等級，對抽取結(jié)果進行分類，并計算預抽取結(jié)果中需求度分別為一、二、三和四級的數(shù)量a，b，c和d。設4個級別的權重優(yōu)先比為4:3:2:1，則應從4個級別中分別抽出的申請編號數(shù)量為X1、X2、X3和X4。則有

且

從而有

（5）搖號結(jié)果

根據(jù)上述計算結(jié)果分別從一、二、三和四級需求度中抽取相應數(shù)量的申請編號，最后的搖號結(jié)果由X1、X2、X3和X4共同組成。

3 仿真分析

根據(jù)上述算法，利用WPF核心技術完成了小客車指標配置管理系統(tǒng)仿真軟件的開發(fā)工作。其旨在通粗糙集理論和模糊綜合評價方法來優(yōu)化目前搖號過程中所使用的隨機算法，從而完成配置小客車指標的抽取。該仿真系統(tǒng)可以模擬搖號過程，跟蹤多個申請者在多次搖號過程中的中選情況。主要根據(jù)如下指標比較新舊兩種算法的優(yōu)劣:

（1）多個申請者的平均等待時間；

（2）每個申請者在第n輪沒被選中的情況下，在第n＋1輪被選中的概率；

3.1 改進算法在購車搖號中的使用

在仿真系統(tǒng)中用戶可進行隨機算法的選擇，主要顯示申請者 （包括急需用車家庭、申請首車家庭、申請非首車家庭、等待時間10個月以上、等待時間15個月之上和等待時間20個月之上）中的不同類別在原始算法和新算法下指標配置的具體數(shù)量以及所占總體配置指標的百分比。本文以900個數(shù)據(jù)樣本進行實驗，采用兩種算法的實驗結(jié)果如表1所示。

表1 新舊算法結(jié)果對比

利用實際購車搖號的數(shù)據(jù)，首次申請有效數(shù)量為17600，隨機選擇100個申請者，在進行10期搖號過程中，跟蹤其在原隨機算法和改進的隨機算法中下的等待時間，如圖5所示。

圖5 100個申請者在兩隨機算法下的等待時間對比

依然利用實際購車搖號的數(shù)據(jù)，首次申請有效數(shù)量為17600，從第1期的搖號開始，第一期中的，在進行10期搖號過程中，跟蹤不同類別的申請者在原隨機算法和改進的隨機算法中下的平均等待時間，如圖6所示。

圖6中，橫軸7個類別分別指的是特殊申請者6個類別和非特殊情況的申請者?？v軸的基本單位是月，因每月進行一次搖號。

3.2 結(jié)果分析比較

（1）表1的比較結(jié)果可以看出，原隨機算法中，每個申請者本次沒被搖中的情況下，下次被搖中的概率由搖號基數(shù)確定，而改進的隨機算法在申請者隨著等待時間的增加，搖號中簽的概率逐漸增加，從而從根本上解決 “久搖不中”的現(xiàn)象；

圖6 兩種隨機算法不同類別的申請者平均等待時間對比

（2）由圖5中的比較結(jié)果可以看出，兩系統(tǒng)中被跟蹤的100個申請者的平均等待時間明顯縮短；

（3）由圖6中的比較結(jié)果可以看出，改進算法在搖號的過程中，重點考慮了申請者需求度的關鍵作用，因此需求度高的申請者搖到號的可能性更大，這樣指標浪費的現(xiàn)象能夠得到明顯的抑制。從圖中可以得到兩個結(jié)論:針對不同類別的申請者，改進的隨機算法中，需求度越高的申請者平均等待時間越短，而原隨機算法則無此特點；針對同一類別的申請者，改進的隨機算法的平均等待時間明顯低于原隨機算法。

4 結(jié)束語

本文的主要工作在于通過對當前汽車搖號過程中存在的個別不夠公平的因素的分析研究，而對其中用到的隨機算法進行了改進，并在此基礎上開發(fā)完成了模擬系統(tǒng)，通過仿真實驗來驗證本文算法的合理性和公平性。

通過實驗結(jié)果的分析和說明，本文算法和所建立的模擬系統(tǒng)得到的搖號結(jié)果在平均等待時間和多次搖號過程中的搖中概率方面均有明顯的優(yōu)勢，從而說明本文算法更為考慮全面和人性化。

[1]FU Ning.The methods for generating the random numbers:Linear congruence generator[D].Jilin:Jilin University，2007（in Chinese）.[符寧.均勻隨機數(shù)的線性同余生成方法[D].吉林:吉林大學，2007.]

[2]ZHANG Yuzhu，YU Zhenmin，CHEN Min，et al.GB／T1011－2008generation of random numbers and procedures applied to sampling inspection for product quality[S].Beijing:Standardization Administration of the People＇s Republic of China，2008 （in Chinese）.[張玉柱，于振凡，陳敏，等.GB／T10111－2008隨機數(shù)的產(chǎn)生及其在產(chǎn)品質(zhì)量抽樣檢驗中的應用程序[S].北京:中國國家標準化管理委員會，2008.]

[3]Beijing indicators regulation of small passenger management information system.[EB／OL].[2012－11－27].http:／／www.b＃yd.gov.cn（in Chinese）.[北京市小客車指標調(diào)控管理信息新系統(tǒng)[EB／OL].[2012－11－27].http:／／www.b＃yd.gov.cn.]

[4]ZHOU Xin，ZHANG Huaxiang.Research on text categorization based on similar rough set and fuzzy cognitive map[J].Computer Engineering and Design，2008，29 （21）:5537－5539（in Chinese）.[周鑫，張化詳.基于相似粗糙集合模糊認知圖的文本分類研究[J].計算機工程與設計，2008，29 （21）:5537－5539.]

[5]LI Yingyi，WANG Yuangan，CAO Jinghua.Attribute reduction fusion algorithm of marine data based on rough set[J].Computer Simulation，2012，29 （8）:222－226 （in Chinese）.[黎永壹，王遠干，曹婧華.基于粗糙集屬性約簡的海洋數(shù)據(jù)融合算法[J].計算機仿真，2012，29 （8）:222－226.]

[6]QIN Xiao，YUAN Changan.Text clustering method based on genetic algorithm and SOM network[J].Journal of Computer，2008 （3）:757－760 （in Chinese）.[覃曉，元昌安.基于遺傳算法和自組織特征映射網(wǎng)絡的文本聚類方法[J].計算機應用，2008 （3）:757－760.]

[7]LIU Bingxiang，LI Haolin.Method of factor weights allocation based on combination of fuzzy and rough set[J].Contol and Decision，2007，22 （12）:1437－1440 （in Chinese）.[柳炳祥，李海林.基于模糊粗糙集的因素權重分配方法[J].控制與決策，2007，22 （12）:1437－1440.]

[8]TAN Zongfeng，XU Zhangyan，WANG Shuai.Improved method of attribute weight based on rough sets theory[J].Computer Engineering and Applications，2012，48 （18）:115－118（in Chinese）.[譚宗鳳，徐章艷，王帥.一種改進的粗糙集權重方法[J].計算機工程與應用，2012，48 （18）:115－118.]

[9]WANG Jianlong.Research on comprehensive evaluation method for library website based on Rough set theory[J].Science Technology and Engineering，2010，10（18）:4453－4458 （in Chinese）.[王建龍.基于Rough集理論的圖書館網(wǎng)站綜合評價方法研究[J].科學技術與工程，2010，10（18）:4453－4458.]

[10]LIU Li，ZHOU Jianzhong，YANG Junjie，et al.Improved fuzzy comprehensive assessment method based on information entropy[J].Computer Engineering，2009，35（18）:4－6 （in Chinese）.[劉力，周建中，楊俊杰，等.基于信息熵的改進模糊綜合評價方法[J].計算機工程，2009，35（18）:4－6.]

[11]ZHANG Tao，HONG Wenxue.Weight calculation for computational geometry combining classifier using fuzzy of class space[J].Control and Decision，2013 （4）:569－573 （in Chinese）.[張濤，洪文學.基于模糊度的計算幾何分類器權重分配[J].控制與決策，2013 （4）:569－573.]