大规模数独问题的势博弈分布式机器学习求解方法
大规模数独问题的势博弈分布式机器学习求解方法
【技术领域】
[0001] 本发明采用一个大规模数独问题的势博弈分布式机器学习求解方法，并给出数独 问题一个物理的博弈实现，属于多代理智能协作领域。
[0002]
【背景技术】
[000引数独问题 数独曾被描述为二十一世纪的魔方。数独是一种流行的，看似容易上癒的趣题，曾经流 行于世界的许多地方。数独游戏的目标很简单；将："3的方块分为η X η个不同的宫 格，目的是为了填充每一个方块W使W下Η个条件得到满足： (1) 每一行的方块填充的数字从1到η2只能出现一次 (2) 每一列的方块填充的数字从1到η2只能出现一次 (3) 每个宫格内方块填充的数字从1到η2只能出现一次 数独问题是ΝΡ问题，本发明研究解决25 25的版本的大规模数独，要求每行、每列宫 格内填入A到Υ且不重复的字母。
[0004] 势博弈理论 博弈论是用来分析社会现象相互依赖决策过程的一个数学分支，它的基本组成包括参 与者，参与者的策略及参与者的效用，一般描述为存在一个参与者集合、齡。f嘶據|·。每个 参与者被分配一个收益函数Ui: A - R和一个策略集合Ai，其中> ...、A、，令;1| E A i 表示参与者Pi的一个策略，令a 1表示其他的参与者策略集合。整个联合策略η二J等价于 (曰1，a 1)。化sh均衡点是博弈论的一个基本概念，它描述了博弈过程的稳定状态即每个参与 者选择的策略都已是对其它参与者所选策略的最优反应，数学表示为
下面是势博弈定义的描述： 势博弈的概念由Monderer和化apley首次提出，定义如下： 势博弈存在一个势函数;、> J AM吏得： Φ (a；, a i) - Φ (a；., a ；) =11； (a；, a ；) -U； (a；., a ；) 从定义中可W看出，当参与者Pi的策略改变时，势函数的变化和参与者效用的变化是 相等的。势博弈不仅反映了整体与局部的关联，而且在每个有限的势博弈中，必定存在至少 一个纯策略化sh均衡。势博弈现有大部分研究结果限于计算机仿真，没有实现真实的物理 博弈，为此给出数独问题一个物理的博弈实现。
【发明内容】
[0005] 本发明所要解决的技术问题是针对现有势博弈理论存在的缺陷提供一种数独问 题的一个分布式的基于机器学习物理博弈求解方法。
[0006] 本发明为实现上述目的，采用如下技术方案： 上述大规模数独问题势博弈模型化后一共有625个参与者，参与者W软件代理形式在 手机中实现，将625个参与者平均分给5个an化0id手机进行处理，每个手机具有125个参 与者，手机之间的通信通过wifi。在博弈过程中要经过多次的迭代，参与者策略的不断的学 习更新，手机之间互相传递相关的信息，最终解决该数独问题。
[0007] 效用函数设计 常见的效用函数设计有化apley值，反映边际效用贡献的WLU (Wonderful Life 化ility)W及势函数定义Η种方式。送里效用函数的设计根据势函数定义和证明完成。将 数独游戏的每一个小方块作为拥有策略集合Β，、Λ;自私的参与者Pi。根据数独 游戏规则小方块中数字在一定范围（行，列和宫格）内既不重复又能全部出现即得到如下的 效用函数
上式中: ;識分别表示参与者P在行，列，宫格的邻居集合，表示
对于任何参与者集合
则有
建立如下的势函数
令参与者菊餐#的两个策略a，a"EAi满足a'^a"W及曰' i=a" 1赃有如下推导
对終(,:即!#舞做同样的分析，可W得到如下： Φ(3'）-Φ(3") =Ui(a'）-Ui(a") 由势博弈的定义可知，上面建立的效用函数使得数独问题转变为了势博弈模型。
[0008] 学习动力设计 SAP对数线性学习算法在势博弈条件下可W保证参与者策略收敛到纳什均衡点，我们 选择该学习算法作为学习动力。该算法的思想是W模拟退火为基础的，令Δ (Ai)表示在策 略集合Ai上的概率分布集合。令Pi(t) e Δ(Αι)表示参与者PiEP在时刻t策略概率分 布。在该算法中，在时刻?>〇时，参与者Pi(每个参与者W相同的概率)被随机的选择并且允 许更新自己的策略，其他的参与者送时刻必须重复他们的上次?-1时刻策略即满足a 1 (t) =a i(t-l)。
[0009] 参与者Pi在时刻对良据他的策略概率分布Pi(t) e Δ (Ai)随机的从他的策略集 合Ai中选择一个策略，而第a 1个策略概率分布A"' 由下面公式得到。
[0010] 该式中常量#.送務，并且决定了参与者Pi是否愿意更新他的策略。如果资，参 与者将等概率的从策略集合Ai中选择任意的策略a 1E A 1。如果..持*心，参与者Pi将会W 很高的概率从他的如下式的最优反应集合中选择一个策略
【具体实施方式】
[0011] (1)将5个手机编号为0，1，2, 3,4。每个手机初始化都具有125个参与者，参与者 可分为可变策略参与者和不可变策略参与者，不可变策略参与者在博弈的过程中策略是 不会发生变化的。0号手机负责1到125参与者策略更新。1号手机负责126到250参与 者策略更新。2号手机负责251到375参与者策略更新。3号手机负责376到500参与者 策略更新。4号手机负责501到625参与者策略更新。初始化不可变策略参与者的策略。
[0012] (2)每个手机都初始化建立参与者之间的邻居关系。
[0013] (3)每个手机都随机初始化负责的每个可变策略参与者的策略aiE Ai(Ai = (A, B，C，...，刊），并将策略传给其他手机。
[0014] (4)初始化0号手机，从集合*,α.βλ\ .、'巧随机选一个字母记为Λ并通知负责 第个参与者的手机执行SAP算法更新该参与者策略，将该参与者的策略发送给负责邻居 参与者的手机并通知负责下一个参与者的手机执行同样算法更新策略，重复送一策略更 新过程直至625个参与者之间的策略冲突数为0,至此一个真实的物理博弈过程展现出来。 【附图说明】 图1是25X25大规模数独问题图。
【主权项】
1.数独问题的一个分布式物理博弈求解，其特征在于包括如下步骤： 步骤（1):为其建立效用函数并证明数独问题可以转化为势博弈模型； 步骤（2):使用学习动力逐步优化参与者的状态以达到势博弈的最优状态即纳什均衡 点。
【专利摘要】本发明公布了一个博弈论优化方法分布式的求解数独问题，并给出数独问题一个物理的博弈实现。它包含以下步骤：(1)为其建立效用函数并证明数独问题可以转化为势博弈模型(2)使用学习动力逐步优化参与者的状态以达到势博弈的最优状态即纳什均衡点。
【IPC分类】G06F19/00
【公开号】CN105488318
【申请号】CN201410480045
【发明人】蔚承建, 商文喜, 于倩
【申请人】蔚承建
【公开日】2016年4月13日
【申请日】2014年9月19日
【技术领域】
[0001] 本发明采用一个大规模数独问题的势博弈分布式机器学习求解方法，并给出数独 问题一个物理的博弈实现，属于多代理智能协作领域。
[0002]
【背景技术】
[000引数独问题 数独曾被描述为二十一世纪的魔方。数独是一种流行的，看似容易上癒的趣题，曾经流 行于世界的许多地方。数独游戏的目标很简单；将："3的方块分为η X η个不同的宫 格，目的是为了填充每一个方块W使W下Η个条件得到满足： (1) 每一行的方块填充的数字从1到η2只能出现一次 (2) 每一列的方块填充的数字从1到η2只能出现一次 (3) 每个宫格内方块填充的数字从1到η2只能出现一次 数独问题是ΝΡ问题，本发明研究解决25 25的版本的大规模数独，要求每行、每列宫 格内填入A到Υ且不重复的字母。
[0004] 势博弈理论 博弈论是用来分析社会现象相互依赖决策过程的一个数学分支，它的基本组成包括参 与者，参与者的策略及参与者的效用，一般描述为存在一个参与者集合、齡。f嘶據|·。每个 参与者被分配一个收益函数Ui: A - R和一个策略集合Ai，其中> ...、A、，令;1| E A i 表示参与者Pi的一个策略，令a 1表示其他的参与者策略集合。整个联合策略η二J等价于 (曰1，a 1)。化sh均衡点是博弈论的一个基本概念，它描述了博弈过程的稳定状态即每个参与 者选择的策略都已是对其它参与者所选策略的最优反应，数学表示为
下面是势博弈定义的描述： 势博弈的概念由Monderer和化apley首次提出，定义如下： 势博弈存在一个势函数;、> J AM吏得： Φ (a；, a i) - Φ (a；., a ；) =11； (a；, a ；) -U； (a；., a ；) 从定义中可W看出，当参与者Pi的策略改变时，势函数的变化和参与者效用的变化是 相等的。势博弈不仅反映了整体与局部的关联，而且在每个有限的势博弈中，必定存在至少 一个纯策略化sh均衡。势博弈现有大部分研究结果限于计算机仿真，没有实现真实的物理 博弈，为此给出数独问题一个物理的博弈实现。
【发明内容】
[0005] 本发明所要解决的技术问题是针对现有势博弈理论存在的缺陷提供一种数独问 题的一个分布式的基于机器学习物理博弈求解方法。
[0006] 本发明为实现上述目的，采用如下技术方案： 上述大规模数独问题势博弈模型化后一共有625个参与者，参与者W软件代理形式在 手机中实现，将625个参与者平均分给5个an化0id手机进行处理，每个手机具有125个参 与者，手机之间的通信通过wifi。在博弈过程中要经过多次的迭代，参与者策略的不断的学 习更新，手机之间互相传递相关的信息，最终解决该数独问题。
[0007] 效用函数设计 常见的效用函数设计有化apley值，反映边际效用贡献的WLU (Wonderful Life 化ility)W及势函数定义Η种方式。送里效用函数的设计根据势函数定义和证明完成。将 数独游戏的每一个小方块作为拥有策略集合Β，、Λ;自私的参与者Pi。根据数独 游戏规则小方块中数字在一定范围（行，列和宫格）内既不重复又能全部出现即得到如下的 效用函数
上式中: ;識分别表示参与者P在行，列，宫格的邻居集合，表示
对于任何参与者集合
则有
建立如下的势函数
令参与者菊餐#的两个策略a，a"EAi满足a'^a"W及曰' i=a" 1赃有如下推导
对終(,:即!#舞做同样的分析，可W得到如下： Φ(3'）-Φ(3") =Ui(a'）-Ui(a") 由势博弈的定义可知，上面建立的效用函数使得数独问题转变为了势博弈模型。
[0008] 学习动力设计 SAP对数线性学习算法在势博弈条件下可W保证参与者策略收敛到纳什均衡点，我们 选择该学习算法作为学习动力。该算法的思想是W模拟退火为基础的，令Δ (Ai)表示在策 略集合Ai上的概率分布集合。令Pi(t) e Δ(Αι)表示参与者PiEP在时刻t策略概率分 布。在该算法中，在时刻?>〇时，参与者Pi(每个参与者W相同的概率)被随机的选择并且允 许更新自己的策略，其他的参与者送时刻必须重复他们的上次?-1时刻策略即满足a 1 (t) =a i(t-l)。
[0009] 参与者Pi在时刻对良据他的策略概率分布Pi(t) e Δ (Ai)随机的从他的策略集 合Ai中选择一个策略，而第a 1个策略概率分布A"' 由下面公式得到。
[0010] 该式中常量#.送務，并且决定了参与者Pi是否愿意更新他的策略。如果资，参 与者将等概率的从策略集合Ai中选择任意的策略a 1E A 1。如果..持*心，参与者Pi将会W 很高的概率从他的如下式的最优反应集合中选择一个策略
【具体实施方式】
[0011] (1)将5个手机编号为0，1，2, 3,4。每个手机初始化都具有125个参与者，参与者 可分为可变策略参与者和不可变策略参与者，不可变策略参与者在博弈的过程中策略是 不会发生变化的。0号手机负责1到125参与者策略更新。1号手机负责126到250参与 者策略更新。2号手机负责251到375参与者策略更新。3号手机负责376到500参与者 策略更新。4号手机负责501到625参与者策略更新。初始化不可变策略参与者的策略。
[0012] (2)每个手机都初始化建立参与者之间的邻居关系。
[0013] (3)每个手机都随机初始化负责的每个可变策略参与者的策略aiE Ai(Ai = (A, B，C，...，刊），并将策略传给其他手机。
[0014] (4)初始化0号手机，从集合*,α.βλ\ .、'巧随机选一个字母记为Λ并通知负责 第个参与者的手机执行SAP算法更新该参与者策略，将该参与者的策略发送给负责邻居 参与者的手机并通知负责下一个参与者的手机执行同样算法更新策略，重复送一策略更 新过程直至625个参与者之间的策略冲突数为0,至此一个真实的物理博弈过程展现出来。 【附图说明】 图1是25X25大规模数独问题图。
【主权项】
1.数独问题的一个分布式物理博弈求解，其特征在于包括如下步骤： 步骤（1):为其建立效用函数并证明数独问题可以转化为势博弈模型； 步骤（2):使用学习动力逐步优化参与者的状态以达到势博弈的最优状态即纳什均衡 点。
【专利摘要】本发明公布了一个博弈论优化方法分布式的求解数独问题，并给出数独问题一个物理的博弈实现。它包含以下步骤：(1)为其建立效用函数并证明数独问题可以转化为势博弈模型(2)使用学习动力逐步优化参与者的状态以达到势博弈的最优状态即纳什均衡点。
【IPC分类】G06F19/00
【公开号】CN105488318
【申请号】CN201410480045
【发明人】蔚承建, 商文喜, 于倩
【申请人】蔚承建
【公开日】2016年4月13日
【申请日】2014年9月19日
最新回复(0)