基于穿越沙漠问题的相关研究--中国期刊网

字体：大中小

首页> 原创作品> 正文

基于穿越沙漠问题的相关研究

发表时间：2020/12/30 来源：《论证与研究》2020年11期作者：陆国通1 黄永灵2 李子文2

[导读] 摘要：本文主要针对“穿越沙漠游戏”玩家在面临不同情况下的决策进行了相关研究。利用图论的思路构建邻接点矩阵，并给路径赋权值，运用遗传算法对最大利益进行求解。首先使用博弈论的方法对未知情况下的行进方式进行规划，其次利用图论的原理建立了一个邻接点矩阵，并对路径赋以一个随时间变化的消耗值作为权重。最后通过遗传算法构建两个基因组，分别以行动矩阵C和挖矿矩阵R为染色体,使用轮盘赌的方式选择算子，以路径约束为主

                                                           陆国通1 黄永灵2 李子文2
      （1.武警海警学院舰艇指挥系浙江宁波 315000；2.武警海警学院学员二大队浙江宁波 315000）
        摘要：本文主要针对“穿越沙漠游戏”玩家在面临不同情况下的决策进行了相关研究。利用图论的思路构建邻接点矩阵，并给路径赋权值，运用遗传算法对最大利益进行求解。首先使用博弈论的方法对未知情况下的行进方式进行规划，其次利用图论的原理建立了一个邻接点矩阵，并对路径赋以一个随时间变化的消耗值作为权重。最后通过遗传算法构建两个基因组，分别以行动矩阵C和挖矿矩阵R为染色体,使用轮盘赌的方式选择算子，以路径约束为主要环境约束，对两串染色体同时向最优解优化,进行遗传、变异、交叉运算，进行十万次遗传并求出剩余资金的最大值。
        关键词：图论；遗传算法；博弈论
        引言：
        游戏开始前，玩家将获得一定数量的初始资金来购进生活必需品。游戏时，玩家需凭借地图，在规定的时间内顺利到达终点并保留尽可能多的资金。若不能按时抵达终点或者途中必需品耗尽，则视为游戏失败。游戏过程中，玩家可多次回到起点，但在起点处只有一次购买必需品的机会，途径村庄时购买必需品价格为起点处基准价格的两倍。玩家是否能继续前进由每天的天气决定，沙暴日必须在原地停留。因此，受自然环境及游戏规则的限制，玩家能否赢得游戏受到多方面因素的影响：天气状况、矿藏的收益、资源消耗量等。
        1、问题分析
        第一关和第二关中，所有天气状况事先已知，且所有参数也已知，根据地图可将玩家通过游戏的玩法分为挖矿与不挖矿两种。根据天气不同计算出不同情况下的挖矿收益并与额外开销进行比较，若挖矿收益高于额外开销，则选择挖矿；反之则不挖矿。在第三关中，由于挖矿一天基础收益及不同天气基础消耗量可得一天获得的最低收益。当不挖矿的情况下收益最大，由于天气情况，收益不确定。在第五关中，根据其分布状态预测天气情况以及资源的耗费，首先构建一个博弈矩阵，并进行求解，找到矩阵的鞍点，达到Nash均衡。在第六关中，由于天气情况未知且当天可以知道对方的行进情况，可以构建一个动态的博弈矩阵，每次行动后，矩阵随着双方所处位置发生变化，矩阵缩短。即可得到每天行即可得到每天行动的最佳方式。
        2、模型的建立与求解
        第一关：根据地图建立邻接矩阵，随后使用遗传算法，首先以日期为染色体对其进行二进制编码，其中0为该天不行动，1为该天行动。由此可以得到一个行动矩阵A。之后建立一个天气限制矩阵B，矩阵中元素代表当天天气是否可以行进：当天气为晴朗或高温时，旅客可以行进，值为1；反之值为0。将染色体与天气限制矩阵点乘，可以得到最终的行动矩阵C：
        C=A·B
        使用轮盘赌的方式选择算子，建立函数Ps(i)，该函数与适应度函数成正比，如此，Ps(i)较大时，串i被选中的概率也较大，但同时也可以选中其他的串，可以保持种族的多样性。然后根据地图建立出各点的邻接矩阵Y。根据行动矩阵C和地图邻接矩阵L，可以得到位置矩阵K，随后建立新的染色体S表示其是否挖矿。根据位置矩阵K建立矩阵G判断位置是否在矿场上；随后得到新的矩阵R=S·G判断玩家是否在矿场上挖矿。因此可以得到行动矩阵C和挖矿矩阵R。随后对两串染色体进行遗传、变异、交叉运算，可以得到一个多种情况下剩余资金的矩阵sy，进行十万次遗传并求出矩阵sy中的最大值TT即为剩余资金的最大值。第二关是从起点直接到终点，若不挖矿则剩余资金等于初始资金减去行程消耗的水总花费与行程消耗的食物总花费之和得到：
        SY=10000-WWW-WFF
        第三关玩家路线可分为两种：
        不挖矿，行走三天，到达终点
        挖矿，行走五天，其余时间可挖矿，由第三关参数设定可知
        晴朗时，挖矿收益为200-55×3=35元，高温时，挖矿收益为负，挖矿比不挖矿多耗费两天行走的路程，最少耗资W=220元，但假设天气晴朗，挖矿一天最多收益35元，挖矿四天收益140元，小于耗资，故第三关应选择不挖矿最短路线。第四关直接从起点行走8天到达终点，路线为1，2，3, 4, 5, 10, 15, 25若不挖矿则剩余资金等于初始资金减去行程消耗的水总花费与行程消耗的食物总花费之和得到：
        SY=10000-WWW-WFF
        假设天气情况满足泊松分布并且发生沙暴的天数不超过三天，发生沙暴的概率不大于十分之一，可以得到三种情况的剩余资源和的区间。由于天气无法确定，应保障携带尽量多的物资以保障旅行完成并在结尾售卖。通过播送分布判断出三种天气情况约为：14天晴朗，14天高温，2天沙暴，并计算得到消耗总量以及挖矿总量，最终甲上其资源余量的返还资金，得到最优规划为：1 2 3 4 9 14 13 18 18 18 13 14 18 18 19 20 25
        在第五关中经过第三关中的计算，得到了集中相对剩余资金较多的路线作为玩家行动的惨况路线，具体路线如下：

表1 剩余资金较多路线表

对A有：

当玩家A选择路线①玩家B也选择路线①时,玩家A耗资W=980元
以此类推，构建玩家A耗资矩阵以此作为博弈矩阵

表2 耗资矩阵表

        由矩阵可知，考虑B每种路线A的不同耗资，当玩家A选择路线①时，总耗资最少，故玩家采取的一般策略应为路线A。第六关中首先建立邻接矩阵，随后分别列出A、B、C、三个人第i天可能出现的位置。其中Tan带表a在第你天时出现的位置，矩阵内的symin表示该情况下剩余金额的最小值，得到博弈矩阵。如第五关，找到该矩阵的鞍点，并使其达到Nash平衡，可以得到下一个点a人员应当前进的位置。第二天过后，得知了前一天三人的运动状态，删去不满足前一天运动状态的矩阵，得到新的博弈矩阵。随后求出新的鞍点作为下一天的运动方向。根据时间的变化，矩阵博弈矩阵将不断缩小，并由此得到每一步的最优行动方式。
         结论：
        首先玩家仅已知当天的天气状况，从第1天起，玩家可在当天行动结束后知道其余玩家当天的行动方案和剩余资源数量，随后确定各自第二天的行动方案。游戏每天天气状况事先已知，每名玩家行动方案第0天已确定且不能再更改。穿越沙漠中原始携带和额外补给的资源配置和最优路径、最短路径的确定以获得最大利益。本文利用图论的思路构建邻接点矩阵，并给路径赋权值，运用遗传算法对最大利益进行求解。根据题目所给条件，将各因素与路线规划相结合解决核心问题。
        参考文献：
        [1]姜启源，谢金星，叶俊.《数学模型[M].第三版》高等教育出版社.2003
        [2]许国根,贾瑛韩启龙.《模式识别与智能计算的MATLAB 实现[M]第二版》.北京航空航天大学出版社2017
        [3]周凯，邬学军，宋军全、《数学建模[M]》浙江大学出版社2017(12).
        [4]刘帅奇李会雅赵杰《MATLAB 程序设计基础与应用[M]》,清华大学出版社,2016(10).