求解社区项目博弈的一种改进贪婪算法研究

摘要

针对社区项目博弈的一般模型,应用贪婪算法求解项目博弈的近似社会最优指派,给出参与者重加权分配机制,证明贪婪算法求得的指派恰好是非合作项目博弈的一个纳什均衡.定义控制参数,给出边际效益后悔值定义,利用后悔值改进了贪婪算法,证明基于后悔值贪婪算法求得的指派是非合作项目博弈的一个纳什均衡.通过数值仿真实验发现,与模拟退火算法比较,贪婪算法能够得到更好的社会效益,而且基于后悔值贪婪算法比贪婪算法得到更好的社会效益.