[發明專利]一種基于決策概率逼近的矩陣對策近似求解方法及裝置

在審

• 申請號: 201710705959.9
• 申請日: 2017-08-17
• 公開（公告）號: CN107491418A
• 公開（公告）日: 2017-12-19
• 發明（設計）人: 何煉堅;鄭翔平;楊家偉;蔣成進;袁雙
• 申請（專利權）人: 中國電子科技集團公司第二十九研究所
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 成都九鼎天元知識產權代理有限公司51214
• 代理人: 徐靜

技術領域

本發明涉及矩陣對策中的策略確定領域，尤其是一種基于決策概率逼近的矩陣對策近似求解方法及裝置。

背景技術

當前矩陣對策中的策略確定使用以下方法計算納什均衡策略：

(1)圖解法

該方法采用平面二維畫圖的方法求解，適合于收益矩陣為2×n(n>＝2)或m×2(m>＝2)階的對策問題，對其它矩陣對策問題不適用。

(2)方程組法

該方法事先假定對策雙方的最優策略的所有分量均不為零，在此基礎上將矩陣對策問題轉化為等價的線性方程組問題進行求解。該方法有兩方面的缺點：一是上述假定有些情況下不成立，二是對于大規模的矩陣對策問題，求解方程組的開銷太大。

(3)線性規劃法

該方法將矩陣對策問題轉化為等價的線性規劃問題，利用單純形或對偶單純形法求解，屬于具有一般性的求解矩陣對策的方法，可以求解任意矩陣對策。該方法的缺點在于，對于大規模的矩陣對策問題，求解線性規劃的開銷太大。

對于大規模的矩陣對策問題，要求解納什均衡策略，圖解法完全不可用，而方程組法和線性規劃法都有開銷太大的問題，應考慮使用其它方法求解近似最優策略。

發明內容

本發明所要解決的技術問題是：針對現有技術存在的問題，提供一種基于決策概率逼近的矩陣對策近似求解方法及裝置。本發明提出一種基于決策概率逼近的矩陣對策策略確定方法。

本發明采用的技術方案如下：

一種基于決策概率逼近的矩陣對策近似求解方法包括：

步驟1：設置該局中人關于其策略集中策略的選擇概率向量初始值；該局中人所有策略選擇概率向量滿足所有分量值屬于區間[0，1]，且其總和為1；

步驟2：針對該局中人的策略選擇概率向量，計算另一局中人所有策略的期望收益；使用最新計算出的另一局中人所有策略的期望收益，計算另一局中人的策略選擇概率向量；通過歸一化，使另一局中人所有策略選擇概率向量滿足所有分量值屬于區間[0，1]，且其總和為1；

步驟3：針對另一局中人的策略選擇概率向量，計算該局中人所有策略的期望收益；使用最新計算出的該局中人所有策略的期望收益，計算該局中人的策略選擇概率向量；通過歸一化，使該局中人所有策略選擇概率向量滿足所有分量值屬于區間[0，1]，且其總和為1；

步驟4：通過步驟2及3之間的反復迭代，使得該局中人的策略選擇概率向量以及另一局中人的策略選擇概率向量收斂，結束迭代，求得該局中人與另一局中人的矩陣對策測量的近似最優策略。

進一步的，所述收斂判斷過程是：

步驟41：記錄當前與上一次的該局中人策略選擇概率向量g_cur、g_prev；同理記錄當前與上一次的另一局中人策略選擇概率向量h_cur、h_prev；

步驟42：根據上述數據，計算該局中人的前后相繼迭代輪的策略選擇概率向量的相對距離值，以及另一局中人的前后相繼迭代輪的策略選擇概率向量的相對距離值；

步驟43：將上述兩個相對距離值分別與預設精度值相比較，記錄兩個相對距離值都滿足預設精度條件的連續滿足次數L，若連續滿足次數L達到門限值，則判斷該局中人的策略選擇概率向量以及另一局中人的策略選擇概率向量收斂。

進一步的，所述步驟1具體指的是：

1)記局中人關于其策略集中策略的選擇概率向量為m維向量h，設定其初值h⁽⁰⁾，h⁽⁰⁾滿足所有分量值屬于區間[0，1]，且其總和為1；或

2)記局中人關于其策略集中策略的選擇概率向量為n維向量g，設定其初值g⁽⁰⁾，g⁽⁰⁾滿足所有分量值屬于區間[0，1]，且其總和為1。

進一步的，計算該局中人的策略選擇概率向量具體過程是：

計算m維向量f和h：

f＝Rg；

其中h⁽⁰⁾滿足所有分量值屬于區間[0，1]，且其總和為1；R是另一局中人的收益矩陣；f表示當另一局中人的策略選擇概率向量為g時，該局中人各策略的期望收益；h為該局中人的策略選擇概率向量，滿足：0≤h_i≤1，i＝1，...，m，以及函數F滿足：F(0)＝0，且F(x)關于x嚴格單調上升。

進一步的，對函數F(x)＝x，有：