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

（北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京100048）

0 引 言

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

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

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

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

遞推公式為

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

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

（1）指標(biāo)浪費(fèi)現(xiàn)象嚴(yán)重

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

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

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

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

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

圖1 原隨機(jī)算法搖號過程中中簽率隨時(shí)間變化趨勢

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

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

2 基于需求度的改進(jìn)隨機(jī)算法 （demand degree－RA）

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

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

（2）粗糙集理論為各個(gè)評價(jià)指標(biāo)分配權(quán)重；

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

2.1 評價(jià)指標(biāo)體系建立

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

2.2 基于粗糙集理論的評價(jià)指標(biāo)權(quán)重分配

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

（1）導(dǎo)出指標(biāo)因素具體數(shù)據(jù)；

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

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

（4）粗糙集理論分配權(quán)重[7，8]。

其中，粗糙集分配權(quán)重的計(jì)算過程如下:

（1）定義:

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

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

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

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

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

（4）計(jì)算兩個(gè)屬性集的依賴程度

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

（6）計(jì)算每個(gè)條件屬性的權(quán)重

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

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

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

（2）進(jìn)行單因素評價(jià)，建立模糊關(guān)系矩陣珟R，并確定評價(jià)因素的模糊權(quán)向量，即

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

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

（1）建立評語集

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

（2）計(jì)算因素權(quán)重

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

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

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

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

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

圖2 隸屬函數(shù)1

圖3 隸屬函數(shù)2

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

（4）選擇模糊合成算子

模糊合成算子的類型有很多種，常用的兩種是加權(quán)平均型和主因素突出型。該模型中選用了加權(quán)平均型，因?yàn)樗菍Ω饕蛩氐南鄬?quán)重和模糊關(guān)系矩陣的綜合處理，可以避免信息丟失。現(xiàn)實(shí)問題的實(shí)際性質(zhì)決定了模糊算子的選擇。

2.4 Demand degree－RA 算法流程

整體流程如圖4所示。

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

（1）確定申請者樣本

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

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

（3）指標(biāo)預(yù)抽取

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

（4）計(jì)算指標(biāo)分配情況

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

且

從而有

（5）搖號結(jié)果

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

3 仿真分析

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

（1）多個(gè)申請者的平均等待時(shí)間；

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

3.1 改進(jìn)算法在購車搖號中的使用

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

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

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

圖5 100個(gè)申請者在兩隨機(jī)算法下的等待時(shí)間對比

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

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

3.2 結(jié)果分析比較

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

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

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

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

4 結(jié)束語

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

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

[1]FU Ning.The methods for generating the random numbers:Linear congruence generator[D].Jilin:Jilin University，2007（in Chinese）.[符寧.均勻隨機(jī)數(shù)的線性同余生成方法[D].吉林:吉林大學(xué)，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隨機(jī)數(shù)的產(chǎn)生及其在產(chǎn)品質(zhì)量抽樣檢驗(yàn)中的應(yīng)用程序[S].北京:中國國家標(biāo)準(zhǔn)化管理委員會，2008.]

[3]Beijing indicators regulation of small passenger management information system.[EB／OL].[2012－11－27].http:／／www.b＃yd.gov.cn（in Chinese）.[北京市小客車指標(biāo)調(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）.[周鑫，張化詳.基于相似粗糙集合模糊認(rèn)知圖的文本分類研究[J].計(jì)算機(jī)工程與設(shè)計(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）.[黎永壹，王遠(yuǎn)干，曹婧華.基于粗糙集屬性約簡的海洋數(shù)據(jù)融合算法[J].計(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)絡(luò)的文本聚類方法[J].計(jì)算機(jī)應(yīng)用，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）.[柳炳祥，李海林.基于模糊粗糙集的因素權(quán)重分配方法[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ìn)的粗糙集權(quán)重方法[J].計(jì)算機(jī)工程與應(yīng)用，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)站綜合評價(jià)方法研究[J].科學(xué)技術(shù)與工程，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ìn)模糊綜合評價(jià)方法[J].計(jì)算機(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）.[張濤，洪文學(xué).基于模糊度的計(jì)算幾何分類器權(quán)重分配[J].控制與決策，2013 （4）:569－573.]