基于合作技能博弈的单任务联盟结构生成算法-计算机应用研究.pdfVIP

第２９卷第７期 计 算 机 应 用 研 究 Ｖｏｌ．２９Ｎｏ．７ ２０１２年７月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｊｕｌ．２０１２ 基于合作技能博弈的单任务联盟结构生成算法 史　强，夏　阳，王　磊 （中国矿业大学计算机科学与技术学院，江苏徐州２２１１１６） 摘　要：提出一种用于单任务最优联盟结构生成算法ＳＴＣＳＧ。利用合作技能博弈（ＣＳＧｓ）模型和超图生成合作 技能超图（ｓｋｉｌｌｈｙｐｅｒｇｒａｐｈ），根据ＳＴＳＧ中最优联盟结构特性，具体讨论了当每个ａｇｅｎｔ最多只能拥有一个技能和 一个技能最多被两个ａｇｅｎｔ共同拥有两种情况下有哪些信誉好的足球投注网站合作技能超图的策略，从而求得最优联盟结构。实验结果 ２ 表明该算法有哪些信誉好的足球投注网站效率较高，时间复杂度为Ｏ（ｎ）。 关键词：多智能体系统；联盟结构；合作技能博弈；超图；单任务技能博弈；合作技能超图 中图分类号：ＴＰ１８　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１２）０７２５０９０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１２．０７．０２８ ＳｉｎｇｌｅｔａｓｋｃｏａｌｉｔｉｏｎｓｔｒｕｃｔｕｒｅｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＣＳＧｓ ＳＨＩＱｉａｎｇ，ＸＩＡＹａｎｇ，ＷＡＮＧＬｅｉ （ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ，ＸｕｚｈｏｕＪｉａｎｇｓｕ２２１１１６，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｅｄｓｉｎｇｌｅｔａｓｋｃｏａｌｉｔｉｏｎｓｔｒｕｃｔｕｒｅｇｅｎｅｒａｔｉｏｎ（ＳＴＣＳＧ）ａｌｇｏｒｉｔｈｍｔｏｇｅｎｅｒａｔｅｏｐｔｉｍａｌｓｉｎｇｌｅｔａｓｋ ｃｏａｌｉｔｉｏｎｓｔｒｕｃｔｕｒｅ．ＩｔｕｓｅｄＣＳＧｓｍｏｄｅｌａｎｄｈｙｐｅｒｇｒａｐｈｔｏｇｅｎｅｒａｔｅｓｋｉｌｌｈｙｐｅｒｇｒａｐｈ．Ａｃｃｏｒｄｉｎｇｔｏｔｈｅｏｐｔｉｍａｌｃｏａｌｉｔｉｏｎｓｔｒｕｃ ｔｕｒｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆＳＴＳＧ，ｓｐｅｃｉｆｉｃａｌｌｙｉｎｂｏｔｈｃａｓｅｓｗｈｅｎｅａｃｈａｇｅｎｔｈａｄｏｎｌｙｏｎｅｓｋｉｌｌａｎｄａｓｋｉｌｌｗａｓａｔｍｏｓｔｓｈａｒｅｄｂｙ ｔｗｏａｇｅｎｔ，ｉｔｄｉｓｃｕｓｓｅｄｔｈｅｓｅａｒｃｈｓｔｒａｔｅｇｙｏｆｓｋｉｌｌｈｙｐｅｒｇｒａｐｈｔｏｏｂｔａｉｎｔｈｅｏｐｔｉｍａｌｃｏａｌｉｔｉｏｎｓｔｒｕｃｔｕｒｅ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓ ２ ｓｈｏｗｔｈａｔｓｅａｒｃｈｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｓｈｉｇｈ，ａｎｄｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｉｓＯ（ｎ）． Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉａｇｅｎｔｓｙｓｔｅｍ；ｃｏａｌｉｔｉｏｎｓｔｒｕｃｔｕｒｅ（ＣＳ）；ｃｏａｌｉｔｉｏｎａｌｓｋｉｌｌｇａｍｅｓ（ＣＳＧｓ）；ｈｙｐｅｒｇｒａｐｈ；ｓｉｎｇｌｅｔａｓｋｓｋｉｌｌｇａｍｅ （ＳＴＳＧ）；ｓｋｉｌｌｈｙｐｅｒｇｒａｐｈ 地降低了有哪些信誉好的足球投注网站空间。梁军等人［７］针对混合蚁群遗传算法进化 　引言 代数多、效率低等问题，提出基于混合蚁群遗传算法的 ａｇｅｎｔ联盟求解算法。 在多ａｇｅｎｔ系统（ｍｕｌｔｉａｇｅｎｔｓｙｓｔｅｍ，ＭＡＳ）中智能体之间的