羅攀峰,梁添才,徐俊

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

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

羅攀峰,梁添才,徐俊

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

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

金融自助設(shè)備；分布估計(jì)；鈔箱；配鈔策略

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

為減少鈔箱數(shù)量,節(jié)省硬件制造成本,實(shí)現(xiàn)一個鈔箱或鼓存放多個面額,是鈔箱設(shè)計(jì)技術(shù)的發(fā)展趨勢之一,因而實(shí)現(xiàn)自助設(shè)備存在一個或多個鈔箱或存儲鼓同時存放有兩種不同的面額情況下的配鈔是必要的。

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

1 鈔箱混合面額配鈔優(yōu)化問題

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

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

2 本文算法描述

分布估計(jì)算法（EDA）［1-3］是遺傳算法［4-7］和概率統(tǒng)計(jì)的相互結(jié)合,根據(jù)進(jìn)化過程中優(yōu)質(zhì)解信息的概率分布模型產(chǎn)生新解,具有概率分析的數(shù)學(xué)理論基礎(chǔ)。本文混合分布估計(jì)算法（HEDA）的基本框架如下:

第一步:選擇,初始種群是通過隨機(jī)產(chǎn)生的解中挑選出優(yōu)良解組成；

第二步:建模,利用建立數(shù)學(xué)的概率模型來計(jì)算出種群的優(yōu)劣并產(chǎn)生新解；

第三步:變異,采用隨機(jī)選取某位進(jìn)行變異操作；

第四步:替換,將產(chǎn)生的新解加入新種群替換舊解；

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

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

其中,pj（x）表示第j次種群解空間的概率向量,表示N個優(yōu)質(zhì)解,表示位置i上的取值,a表示學(xué)習(xí)因子。

3 實(shí)驗(yàn)仿真及結(jié)果分析

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

表1 鈔箱現(xiàn)有鈔票信息Tab.1 a1jbanknotes information

表2 a2j鈔箱現(xiàn)有鈔票信息Tab.2 a2jbanknotes information

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

圖1 算法尋優(yōu)能力比較Fig.1 Search capability comparison

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

4 結(jié)論

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

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

［2］周樹德，孫增炘.分布估計(jì)算法綜述［J］.自動化學(xué)報(bào)，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］劉明芳.基于分布估計(jì)算法的整數(shù)規(guī)劃研究［D］.武漢:武漢理工大學(xué)，2008.

［4］云慶夏,黃光球,王站權(quán).遺傳算法和遺傳規(guī)劃［M］.北京:冶金工業(yè)出版社，1997.

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

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

［7］蔣磊，鄒兵，吳明.基于改進(jìn)免疫遺傳算法的含分布式電源配電網(wǎng)規(guī)劃［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計(jì)劃重大項(xiàng)目智能云服務(wù)與管理平臺核心軟件及系統(tǒng)（2013AA01A212）；國家科技支撐計(jì)劃課題電子信息產(chǎn)業(yè)集群質(zhì)量保障服務(wù)平臺應(yīng)用示范(2012BAH27F05）；廣東省自然基金團(tuán)隊(duì)研究項(xiàng)目云計(jì)算核心技術(shù)及云服務(wù)應(yīng)用研究(S2012030006242)

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