作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (2): 185-187. doi: 10.3969/j.issn.1000-3428.2011.02.064

• 人工智能及识别技术 • 上一篇    下一篇

一种生成最优联盟结构的任意时间算法

张振荣,刘惊雷,张 伟   

  1. (烟台大学计算机学院,山东 烟台 264005)
  • 出版日期:2011-01-20 发布日期:2011-01-25
  • 作者简介:张振荣(1984-),女,硕士研究生,主研方向:多Agent联盟;刘惊雷,副教授;张 伟,教授、博士
  • 基金资助:
    国家自然科学基金资助项目(60496323);山东省教育厅科技计划基金资助项目(J07JY24)

Anytime Algorithm for Generating Optimal Coalition Structure

ZHANG Zhen-rong, LIU Jing-lei, ZHANG Wei   

  1. (School of Computer, Yantai University, Yantai 264005, China)
  • Online:2011-01-20 Published:2011-01-25

摘要: 提出一种用于生成最优联盟结构的任意时间算法LVAA。利用分支限界技术和剪枝函数搜索联盟结构图的L1、L2和最顶层后,根据整数拆分对剩余的搜索空间进行横向剪枝,并在横向剪枝剩余的子空间内进行纵向剪枝,从而求得最优联盟结构。实验结果表明,该算法的剪枝效率较高,并能在任意时间点上找到最优值。

关键词: LVAA算法, 最优联盟结构, 任意时间算法, 分支限界技术, 剪枝函数

Abstract: This paper proposes Lateral and Vertical Anytime Algorithm(LVAA) to generate optimal coalition structure. It uses a branch and bound technique and pruning function to search L1, L2 and top layers of the coalition structure graph. According to the conception of the integer partition, it prunes the space horizontally, and then prunes in the remaining subspace vertically and finds the optimal coalition structure value. Experimental results show that pruning efficiency of the algorithm is high, and it can find the current optimal value at anytime.

Key words: Lateral and Vertical Anytime Algorithm(LVAA), optimal coalition structure, anytime algorithm, branch and bound technique, prune function

中图分类号: