• / 7
  • 下載費用:30 金幣  

大規模數獨問題的勢博弈分布式機器學習求解方法.pdf

摘要
申請專利號:

CN201410480045.3

申請日:

2014.09.19

公開號:

CN105488318A

公開日:

2016.04.13

當前法律狀態:

撤回

有效性:

無權

法律詳情: 發明專利申請公布后的視為撤回IPC(主分類):G06F 19/00申請公布日:20160413|||實質審查的生效IPC(主分類):G06F 19/00申請日:20140919|||公開
IPC分類號: G06F19/00(2011.01)I 主分類號: G06F19/00
申請人: 蔚承建
發明人: 蔚承建; 商文喜; 于倩
地址: 210019江蘇省南京市建鄴區樂山路189號4幢4單元507室
優先權:
專利代理機構: 代理人:
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201410480045.3

授權公告號:

||||||

法律狀態公告日:

2018.07.20|||2016.05.11|||2016.04.13

法律狀態類型:

發明專利申請公布后的視為撤回|||實質審查的生效|||公開

摘要

本發明公布了一個博弈論優化方法分布式的求解數獨問題,并給出數獨問題一個物理的博弈實現。它包含以下步驟:(1)為其建立效用函數并證明數獨問題可以轉化為勢博弈模型(2)使用學習動力逐步優化參與者的狀態以達到勢博弈的最優狀態即納什均衡點。

權利要求書

1.數獨問題的一個分布式物理博弈求解,其特征在于包括如下步驟:步驟(1):為其建立效用函數并證明數獨問題可以轉化為勢博弈模型;步驟(2):使用學習動力逐步優化參與者的狀態以達到勢博弈的最優狀態即納什均衡點。

說明書

大規模數獨問題的勢博弈分布式機器學習求解方法

技術領域

本發明采用一個大規模數獨問題的勢博弈分布式機器學習求解方法,并給出數獨問題一個物理的博弈實現,屬于多代理智能協作領域。

背景技術

數獨問題

數獨曾被描述為二十一世紀的魔方。數獨是一種流行的,看似容易上癮的趣題,曾經流行于世界的許多地方。數獨游戲的目標很簡單:將的方塊分為nn個不同的宮格,目的是為了填充每一個方塊以使以下三個條件得到滿足:

(1)每一行的方塊填充的數字從1到n2只能出現一次

(2)每一列的方塊填充的數字從1到n2只能出現一次

(3)每個宮格內方塊填充的數字從1到n2只能出現一次

數獨問題是NP問題,本發明研究解決2525的版本的大規模數獨,要求每行、每列宮格內填入A到Y且不重復的字母。

勢博弈理論

博弈論是用來分析社會現象相互依賴決策過程的一個數學分支,它的基本組成包括參與者,參與者的策略及參與者的效用,一般描述為存在一個參與者集合。每個參與者被分配一個收益函數Ui:A→R和一個策略集合Ai,其中。令ai∈Ai表示參與者Pi的一個策略,令a-i表示其他的參與者策略集合。整個聯合策略等價于(ai,a-i)。Nash均衡點是博弈論的一個基本概念,它描述了博弈過程的穩定狀態即每個參與者選擇的策略都已是對其它參與者所選策略的最優反應,數學表示為

U i ( a i * , a - i * ) = max a i A i U i ( a i , a - i * ) ]]>

下面是勢博弈定義的描述:

勢博弈的概念由Monderer和Shapley首次提出,定義如下:

勢博弈存在一個勢函數使得:

φ(ai,a-i)-φ(ai',a-i)=Ui(ai,a-i)-Ui(ai',a-i)

從定義中可以看出,當參與者Pi的策略改變時,勢函數的變化和參與者效用的變化是相等的。勢博弈不僅反映了整體與局部的關聯,而且在每個有限的勢博弈中,必定存在至少一個純策略Nash均衡。勢博弈現有大部分研究結果限于計算機仿真,沒有實現真實的物理博弈,為此給出數獨問題一個物理的博弈實現。

發明內容

本發明所要解決的技術問題是針對現有勢博弈理論存在的缺陷提供一種數獨問題的一個分布式的基于機器學習物理博弈求解方法。

本發明為實現上述目的,采用如下技術方案:

上述大規模數獨問題勢博弈模型化后一共有625個參與者,參與者以軟件代理形式在手機中實現,將625個參與者平均分給5個android手機進行處理,每個手機具有125個參與者,手機之間的通信通過wifi。在博弈過程中要經過多次的迭代,參與者策略的不斷的學習更新,手機之間互相傳遞相關的信息,最終解決該數獨問題。

效用函數設計

常見的效用函數設計有Shapley值,反映邊際效用貢獻的WLU(WonderfulLifeUtility)以及勢函數定義三種方式。這里效用函數的設計根據勢函數定義和證明完成。將數獨游戲的每一個小方塊作為擁有策略集合自私的參與者Pi。根據數獨游戲規則小方塊中數字在一定范圍(行,列和宮格)內既不重復又能全部出現即得到如下的效用函數

U i ( a ) = Σ P j N i R I { a i = a j } + Σ P j N i C I { a i = a j } + Σ P j N i B I { a i = a j } ]]>

上式中分別表示參與者Pi在行,列,宮格的鄰居集合,表示 I { a i = a j } = 0 a i = a j 1 a i a j ]]>

對于任何參與者集合,令則有

建立如下的勢函數

φ ( a ) = 1 2 Σ P i P U i ( a ) ]]>

其中 φ R ( a ) = 1 2 Σ P i P n i ( a , N i R ) , φ C ( a ) = 1 2 Σ P i P n i ( a , N i C ) , φ B ( a ) = 1 2 Σ P i P n i ( a , N i B ) ]]>

令參與者的兩個策略a',a”∈Ai滿足a'≠a”以及a'-i=a”-i則有如下推導

φ R ( a ) - φ R ( a ) = 1 2 ( Σ P i P n i ( a , N i R ) - n i ( a , N i R ) ) = 1 2 ( n i ( a , N i R ) - n i ( a , N i R ) + Σ P j N i R n j ( a , N i R ) - n j ( a , N i R ) ) = 1 2 ( n i ( a , N i R ) - n i ( a , N i R ) + Σ P j N i R n j ( a , P i ) - n j ( a , P i ) ) = 1 2 ( n i ( a , N i R ) - n i ( a , N i R ) + Σ P j N i R n i ( a , P j ) - n i ( a , P j ) ) = 1 2 ( n i ( a , N i R ) - n i ( a , N i R ) + n i ( a , N i R ) - n i ( a , N i R ) ) = n i ( a , N i R ) - n i ( a , N i R ) ]]>

對和做同樣的分析,可以得到如下:

φ(a')-φ(a”)=Ui(a')-Ui(a”)

由勢博弈的定義可知,上面建立的效用函數使得數獨問題轉變為了勢博弈模型。

學習動力設計

SAP對數線性學習算法在勢博弈條件下可以保證參與者策略收斂到納什均衡點,我們選擇該學習算法作為學習動力。該算法的思想是以模擬退火為基礎的,令Δ(Ai)表示在策略集合Ai上的概率分布集合。令pi(t)∈Δ(Ai)表示參與者Pi∈P在時刻t策略概率分布。在該算法中,在時刻t>0時,參與者Pi(每個參與者以相同的概率)被隨機的選擇并且允許更新自己的策略,其他的參與者這時刻必須重復他們的上次t-1時刻策略即滿足a-i(t)=a-i(t-1)。

參與者Pi在時刻t根據他的策略概率分布pi(t)∈Δ(Ai)隨機的從他的策略集合Ai中選擇一個策略,而第ai個策略概率分布由下面公式得到。

p i a i ( t ) = exp { β U i ( a i , a - i ( t - 1 ) ) } Σ a i A i exp { β U i ( a i , a - i ( t - 1 ) ) } ]]>

該式中常量,并且決定了參與者Pi是否愿意更新他的策略。如果,參與者將等概率的從策略集合Ai中選擇任意的策略ai∈Ai。如果,參與者Pi將會以很高的概率從他的如下式的最優反應集合中選擇一個策略

{ a i A i : U i ( a i , a - i ( t - 1 ) ) = max a i A i U i ( a i , a - i ( t - 1 ) ) } ]]>

具體實施方式

(1)將5個手機編號為0,1,2,3,4。每個手機初始化都具有125個參與者,參與者可分為可變策略參與者和不可變策略參與者,不可變策略參與者在博弈的過程中策略是不會發生變化的。0號手機負責1到125參與者策略更新。1號手機負責126到250參與者策略更新。2號手機負責251到375參與者策略更新。3號手機負責376到500參與者策略更新。4號手機負責501到625參與者策略更新。初始化不可變策略參與者的策略。

(2)每個手機都初始化建立參與者之間的鄰居關系。

(3)每個手機都隨機初始化負責的每個可變策略參與者的策略ai∈Ai(Ai={A,B,C,...,Y}),并將策略傳給其他手機。

(4)初始化0號手機,從集合隨機選一個字母記為i,并通知負責第i個參與者的手機執行SAP算法更新該參與者策略,將該參與者的策略發送給負責鄰居參與者的手機并通知負責下一個參與者的手機執行同樣算法更新策略,重復這一策略更新過程直至625個參與者之間的策略沖突數為0,至此一個真實的物理博弈過程展現出來。

附圖說明

圖1是25×25大規模數獨問題圖。

關 鍵 詞:
大規模 問題 博弈 分布式 機器 學習 求解 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:大規模數獨問題的勢博弈分布式機器學習求解方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6341703.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图