模糊非合作博弈的算法研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇模糊非合作博弈的算法研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

该文在一个求解Stackelberg-Nash均衡解的模糊模拟的二层遗传算法基础上，为模糊非合作博弈设计了一个基于模糊优先关系求解模糊均衡的的遗传算法，并给出了求解最优模糊均衡的改进遗传算法，并用一个实例验证了算法的可行性。

自20世纪90年代以来，科学技术和经济快速发展，市场开始全球化，企业面临的竞争日趋激烈。技术的进步和需求的多样化，使产品寿命周期不断缩短，因而企业面临着缩短交货期、提高产品质量、降低成本和改进服务的压力。如何以更高的产品价值、更优的产品质量、更低廉的成本、更快捷的市场反应速度和更满意的服务与竞争者抗衡；如何占领尽可能大的市场份额，成为企业经营战略的核心，也成为企业面临的重要问题。供应链的产生改变了现代企业的竞争方式，使得企业间通过加强合作来提高竞争力，共同将利益蛋糕做大，建立一种“共赢”的战略合作伙伴关系。在建立合作伙伴关系中，由于利益的原因，双方之间往往存在着策略的对抗和竞争，或对某一种局面的对策选择，因此须对建立供应链合作伙伴关系采用非合作博弈的方法去分析。

现在非合作博弈在经济管理中已得到了广泛的应用，Nash均衡作为非合作博弈的一个重要概念，是所有应用领域中希望得到的最优状态。虽然理论上已经证明了它的存在性，但是并没有给出求解Nash均衡的一般性算法。尤其是对规模较大的问题，现有的方法很难给出解。随着现代优化算法的发展，人们开始把遗传算法引入到均衡求解中来。2001年，陈士俊等[1]提出了一种求解Nash均衡解的遗传算法。仝凌云等[2]运用双种群自适应遗传算法解决了虚拟企业伙伴选择的问题。王成山等[3]以改进的遗传算法为基础，提出了一种适用于输电网投资博弈的均衡分析方法。以上这些算法都是对经典的Nash均衡设计的。2004年，曾玲等[4]针对产品价格为模糊变量的一般递阶资源分配问题，设计了一个求解Stackelberg-Nash均衡解的基于模糊模拟的二层遗传算法。本文将在此基础上为模糊非合作博弈设计一个求解模糊均衡的基于模糊优先关系的遗传算法，并通过一个实例进行验证。

一、模糊非合作博弈

定义1局中人的集合为，局中人的策略集为，当每个局中人选定一个策略（）后，就形成了博弈的一个局势；对于每一个局势 ，局中人 有一个模糊支付函数，则为一个模糊非合作博弈。

定义2设是模糊非合作博弈的一个局势，如果

，

则称为的一个均衡局势。

定义3对于模糊非合作博弈，为局中人的模糊占优策略的隶属度为

.

定义4对于模糊非合作博弈，局势S为的模糊均衡的隶属度为

.

定义5对于模糊非合作博弈，如果对隶属函数有

，

则称局势为的最优模糊均衡。

二、求解模糊均衡的遗传算法

对于模糊非合作博弈，其最优模糊均衡满足。显然这是一个组合最优化问题，随着局中人数量以及策略集元素的增加，求解最优模糊均衡的计算量是指数增长的。这是一个NP-hard问题。

我们将每个局势看作自然界中的一个生物体，每个局中人的策略看作是生物体的不同染色体。正如生物体的生存性质与染色体组的基因关系，最优解也将是算法过程中的最优模糊均衡，从而获得有限n人非合作模糊博弈的最优模糊均衡。在此我们假设所有局中人均有m个策略。

首先我们对问题进行编码。根据非合作模糊博弈的特点，本文采用常规码，对于局中人，其策略集为，向量是局中人的决策向量，其中表示局中人没有选取第个策略，表示局中人选择了第个策略。所有局中人的选择构成了博弈的一个局势，则局势可以用向量表示。

随机选择个局势作为初始群体，

由定义4，可知衡量最优模糊均衡的指标函数为：

又由定义2，3，局势为模糊均衡的隶属度是：

现在问题转化为求的最大值。作适应函数：

计算概率

并以此概率分布从中随机选一些染色体构成一个种群（集中可能重复选中的一个元素）。

因为前面采用了常规编码，而局势的变化随每一个局中人策略选择的变化而变化，所以选择规则时，我们采用单亲遗传法。

从1到中随机选取个数，对于每一个，将第个分量与第个分量交换当时，；得到新的，组成新的局势。将中所有染色体进行上述，得到。

以某个较小的概率p发生变异，得到，令，，形成新的群体，循环计算。

当或者迭代次数达到某个次数时，终止程序。

简单遗传算法有可能不收敛到全局最优解，因此需要简单遗传算法作一点改动，每次记下当前最优解并在群体状态最前增加一维存放当前最优解，则遗传算法收敛到最优解。

改进后的遗传算法其主要特征是：进化的每一代，记录前面各代遗传的最优解并存放在群体的第一位，这个染色体只起到一个记录的功能不参加遗传运算。

现将模糊均衡的改进遗传算法叙述如下：

步骤一：给定群体规模，初始群体；

步骤二：对群体中的每一个染色体计算它的适应函数

，；

步骤三：若停止规则满足，则算法停止；否则，计算概率

，

以此概率分布从中随机选一些染色体构成一个种群；

步骤四：通过单亲遗传法进行，概率为，得到；

步骤五：以一个较小的概率p，使得一个染色体的一个基因发生变异，形成；在中记录当前最优解，，形成一个新的群体；

返回步骤二。

三、实际应用

下面通过一个具体的实例来验证一下算法的有效性。

假设现有同行业的两个制造商甲和乙，他们希望建立供应链的方式来提高自身的竞争力，在建立合作伙伴关系的过程中，各自有3个可供选择的供应商，他们的选择结果是互相影响的，根据不同的情况，甲和乙的收益矩阵如下：

遗传算法的参数选择：群体规模=3；概率为0.5；变异概率为0.2；算法终止条件为：迭代次数达到100或者当均衡隶属度高于0.5算法停止。通过计算，我们得到上述问题的最优均衡局势为甲选择策略3，乙选择策略3，即局势（3，3）为模糊均衡的隶属度为0.214。

四、小结

本文先给出了具有模糊支付的非合作博弈的定义，以及求解模糊均衡的定义，但是发现当局中人数量较多，或策略较多时，依靠枚举法进行求解是非常繁琐的，这是一个NP-hard问题。为了求得最优模糊均衡，在一个求解Stackelberg-Nash均衡解的基于模糊模拟的二层遗传算法的基础上，为模糊非合作博弈设计了一个求解模糊均衡的基于模糊优先关系的遗传算法，并给出了求解最优模糊均衡的改进遗传算法，最后通过一个实例进行了验证。

[1]陈士俊，孙永广，吴宗鑫.一种求解Nash均衡解的遗传算法[J].系统工程，2001.19

[2]仝凌云，陈增强，袁著祉，安利平.虚拟企业伙伴选择的双种群自适应遗传算法[J].计算机工程，2006.32

[3]王成山，吉兴全.输电网投资规划的Nash均衡分析（二）[J].电力系统自动化，2002.26

[4]曾 玲，高金伍.带模糊参数的递阶资源分配问题[J].系统工程理论与实践，2004.11