基于混合分布估計算法的智能配鈔策略

羅攀峰,梁添才,徐俊

(廣州無線電集團,廣州廣電運通金融電子股份有限公司,ATM研究院,廣東 廣州510663)

基于混合分布估計算法的智能配鈔策略

羅攀峰,梁添才,徐俊

(廣州無線電集團,廣州廣電運通金融電子股份有限公司,ATM研究院,廣東 廣州510663)

目前金融自助設備采用鈔箱或者鼓存放現鈔,每一個鈔箱或者鼓只存放一種面額,為減少鈔箱數量和節省硬件制造成本,實現一個鈔箱或鼓存放多個面額,是鈔箱設計技術的發展趨勢之一,因而實現自助設備存在一個或多個鈔箱或存儲鼓同時存放有多種不同的面額情況下的配鈔是一個組合優化問題。針對該組合優化問題,本文建立了相應組合優化問題的線性規劃數學模型,并提出了一種基于混合分布估計算法(HEDA)的智能配鈔策略。通過實驗仿真表明新的智能配鈔算法的有效性。

金融自助設備；分布估計；鈔箱；配鈔策略

目前鼓式循環機芯只針對人民幣采取1種面額的紙幣需要1個鼓的配置方法,而對于混存及鼓少于幣種面額方案沒有加于考慮,鼓本預研計劃考慮面額數量大于鼓個數的情況,比如歐元有7個面額,如只用4個鼓如何處理,及需要考慮混存和配置緩存區的情況,并提出幾種方案的優劣勢對比分析。提出多種鼓式循環機芯配鈔方案,考慮多種應用環境。

為減少鈔箱數量,節省硬件制造成本,實現一個鈔箱或鼓存放多個面額,是鈔箱設計技術的發展趨勢之一,因而實現自助設備存在一個或多個鈔箱或存儲鼓同時存放有兩種不同的面額情況下的配鈔是必要的。

本文提出了基于混合分布估計算法的多種智能配鈔方案,考慮多種應用環境,能提供取款的多種數額,考慮多種應用環境。該智能配鈔策略是基于混合粒子群算法的優化策略,通過引入分布估計算法（EDA）的建立概率模型和隨機采樣的思想,保證算法整體算法收斂性,另外通過引入遺傳算法的交叉和變異操作思想來避免算法陷入局部最優解。最終通過實驗仿真結果表明,在混合分布估計算法在求解鈔箱混合面額配鈔優化問題具有很好的效果。

1 鈔箱混合面額配鈔優化問題

鈔箱混合面額配鈔優化問題是一個復雜的組合優化問題。為了描述方便,先對鈔箱混合面額配鈔優化數學建模。首先設定的自助設備配備有m個混合面額鈔箱和n個單一面額鈔箱,K表示鈔箱能裝鈔票的張數上限。給定取款數額C,aij表示第i個混合面額鈔箱中第j張鈔票的面額,bij表示第i個單個面額鈔箱中第j張鈔票面額,如何選擇出鈔方案,使得出鈔的總額度最接近取款額度？其目標函數為:

約束條件為出鈔的累積面額不能超過取款額度，即

2 本文算法描述

分布估計算法（EDA）［1-3］是遺傳算法［4-7］和概率統計的相互結合,根據進化過程中優質解信息的概率分布模型產生新解,具有概率分析的數學理論基礎。本文混合分布估計算法（HEDA）的基本框架如下:

第一步:選擇,初始種群是通過隨機產生的解中挑選出優良解組成；

第二步:建模,利用建立數學的概率模型來計算出種群的優劣并產生新解；

第三步:變異,采用隨機選取某位進行變異操作；

第四步:替換,將產生的新解加入新種群替換舊解；

第五步:判斷是否滿足終止條件。若滿足則結束,新種群的解即為所求解；否則轉至第二步；

分布估算法的核心算子是概率模型的建立。在分布估計算法中,表示解空間分布的概率模型是一個概率向量即p（x）=（p（x1），p（x2），…，p（xn）），其中p（xi）表示位置i上取值1的概率。概率模型的計算公式如下:

其中,pj（x）表示第j次種群解空間的概率向量,表示N個優質解,表示位置i上的取值,a表示學習因子。

3 實驗仿真及結果分析

假設出鈔機芯有3個混合鈔箱:a1j（面額值為2和5）、a2j（面額值為10和20）、b1j（面額值為50）。二個混合鈔箱依次存放鈔票的信息為:

表1 鈔箱現有鈔票信息Tab.1 a1jbanknotes information

表2 a2j鈔箱現有鈔票信息Tab.2 a2jbanknotes information

用本文提出的混合分布估計算法來求解該問題，含有交叉操作的分布估計算法（HEDA）和傳統的分布估計算法作了性能比較,各算法在計算機上迭代40次,當要求出鈔額度1 029時,目標函數收斂曲線如圖1所示。

圖1 算法尋優能力比較Fig.1 Search capability comparison

從圖1基本能看出本文的混合分布估計算法能更開的尋找到更佳的近似最優解。并且在算法的整個迭代過程中,HEDA算法由于引入交叉等操作使得算法保持較好的種群多樣性,從而使得HEDA算法比EDA算法具有更好的尋優能力。

4 結論

文中針對智能配鈔的組合優化問題建立了相應組合優化問題的線性規劃數學模型,并提出了一種基于混合分布估計算法（HEDA）的智能配鈔策略。通過實驗仿真表明新的智能配鈔算法提供更好的資源利用率和尋優能力,充分地說明了算法的有效性和可靠性。

［1］Shapiro J L.Drift and scaling in estimation of distribution algorithms［J］.Evolutionary Computation，2005，13（1）:99-123.

［2］周樹德，孫增炘.分布估計算法綜述［J］.自動化學報，2007，33（2）:113-124.ZHOU Shu-De，SUN Zeng-Qi.A survey on estimation of distribution algorithm［J］.Acta Automatic Sinica，2007，33（2）: 113-124.

［3］劉明芳.基于分布估計算法的整數規劃研究［D］.武漢:武漢理工大學，2008.

［4］云慶夏,黃光球,王站權.遺傳算法和遺傳規劃［M］.北京:冶金工業出版社，1997.

［5］周明,孫樹棟.遺傳算法原理及應用［M］.北京:國防工業出版社，2000.

［6］張文修、梁怡編.遺傳算法的數學基礎［M］.西安:西安交通大學出版社，2003.

［7］蔣磊，鄒兵，吳明.基于改進免疫遺傳算法的含分布式電源配電網規劃［J］.陜西電力,2012(10):26-30.JIANG Lei，ZOU Bing，WU Ming.Distribution network planning with distributed generation based on improved immune genetic algorithm ［J］.Shaanxi Electric Power,2012 (10):26-30.

Intelligent allocation strategy of currency based on estimation of distribution algorithm

LUO Pan-feng，LIANG Tian-cai，XU Jun
（ATM Research Institute,GRGBanking,Guangzhou Radio Group,Guangzhou 510663，China）

The current financial self-service equipment using money box or drum storage notes，each note box or drum store only one denomination，in order to reduce the cash box number and save hardware cost，the realization of a cash box or drum store multiple denominations，is the development trend of the design technology of money box，thus realizing self-service equipment there one or more cash box or storage drum at the same time deposit with bank note denomination of a variety of different conditions is a combinatorial optimization problem.In view of this combinatorial optimization problem，the paper establishes the mathematical model of linear programming corresponding combinatorial optimization problems，and propose a hybrid estimation of distribution algorithm based on（HEDA）smart with money policy.Simulation results show that the effectiveness of the new algorithm intelligent allocation of money.

hadoop；estimation of distribution；particle swarm optimization；mapreduce

TN18

：A

：1674-6236（2015）18-0004-02

2014-12-16稿件編號：201412128

國家863計劃重大項目智能云服務與管理平臺核心軟件及系統（2013AA01A212）；國家科技支撐計劃課題電子信息產業集群質量保障服務平臺應用示范(2012BAH27F05）；廣東省自然基金團隊研究項目云計算核心技術及云服務應用研究(S2012030006242)

羅攀峰（1976—）,男,湖南株洲人。研究方向:ATM智能配鈔,企業信息化等。