智能控制 基于博弈的控制 吴建设
第一讲 : 绪论 1 博弈与智能的关系 2 博弈与控制 3 博弈论简介
1 博弈与智能的关系 博弈需要智能 博弈的过程需要智能 博弈的结果体现出智能 博弈的策略是智能的载体 传统人工智能的研究内容 机器学习 进化计算 模糊集 专家系统 * 神经网络 * 粗糙集 * 粒度计算 * 多智能体理论, 等等
1 博弈与智能的关系 美国新墨西哥大学 Geoge F. Luger 的书 :Artificial Intelligence: structures and strategies for complex problem solving. 对 人工智能 研究范围的定义 : 人工智能研究者们研究的问题和方法的集合 最新的研究动态 : 博弈成为人工智能研究的热点 IEEE Computational Intelligence Society 新创期刊 IEEE Transactions on Computational Intelligence and AI in Games
2 博弈与控制 人工智能的发展离不开博弈 神经网络 生物的神经系统 神经控制系统 进化计算 生物的进化现象 进化控制系统 免疫计算 生物的免疫现象 免疫控制系统 专家系统 专家的知识与经验 专家控制系统 博弈计算或系统 来源于生物或人类社会的博弈现象 博弈控制系统
3 博弈论简介 1 什么是博弈论 (Game Theory) 一个经典的例子 : 囚徒困境 (Prisoner s s Dilemma) D C D C D P P T S D -5-5 0-10 S T R R C C -10 0-1 -1 T>R>P>S, 2R>T+S
3 博弈论简介 2 囚徒困境的启示 (D, D) 这个状态, 谁也不能通过单方面改变自 己的策略增加自己的收益 因此, 谁也不会主 动离开这个状态, 即改变自己的策略为 C 当然, 这两个人可以订立攻守同盟, 即合作, 这时的博弈状态是 (C, C)
3 博弈论简介 囚徒困境的启示 ( 续 ) (C, C) 这个状态是不稳定的, 任何人都能 通过单方面改变自己的策略增加自己的 收益 因此, 每个人都有意愿离开这个 状态, 即改变自己的策略为 D 囚徒困境反映了个人理性与集体利益的 矛盾
2 纳什均衡 假设有 n 个玩家 (agent, player) 参与博弈, 给定其他人策略的条件下, 每个玩家选择自己的最优策略 ( 个人最优策略可能依赖于也可能不依赖于他人的战略 ), 从而使自己效用最大化 所有局中人策略构成一个策略组合 (Strategy Profile) 各个参与人的在某个时间点的策略的有序集称为策略组合, 比如囚徒困境中的 (D, D), (C, C), (C, D) 都是策略组合
2 纳什均衡 纳什均衡指的是这样一种策略组合, 即在给 定别人策略的情况下, 没有人愿意单方面改变自 己的策略, 从而打破这种均衡
纳什均衡的数学表示 纳什均衡的定义 : 在博弈 G= { S 1,,S n :u 1,,u n } 中, 如果由各个博弈方的各一个策略组成的某个策论组合 (s 1 *,,s n *) 中, 任一博弈方 i 的策略 s i 都是对其余博弈方策略的组合 (s 1 *, s i-1 *,s i+1 *,,s n * ) 的最佳对策, 即 u i (s 1 * s,,s n *) u i (s 1,,s n *) 对任意 s i S i 都成立, 则称 (s 1 *,,s n *) 为 G 的一个纳什均衡
纳什均衡的定义 策略空间 : S, 1 S n 博弈方 i 的第 j 个策略 : s i 博弈方 i的得益 : u i 博弈 : G S, S ; u, u } { 1 n 1 n j S i 纳什均衡 : 在博弈 G { S1, Sn; u1, un} 中, 如果由各个博弈方 * * 的各一个策略组成的某个策略组合 ( si, s n ) 中, 任一博弈方 * * * * 的策略, 都是对其余博弈方策略的组合 ( si, si 1, si 1,... sn ) u ( s * * * * * *, s, s, s,... s ) u ( s, s,... s 的最佳对策, 也即 i i i 1 i i 1 n i i i 1 ij i 1 n * * 对任意 s S 都成立, 则称 ( s, s ) 为 G 的一个纳什均衡 i j i ( i n *, s, s * * i )
纳什均衡的一致预测性质 一致预测 : 如果所有博弈方都预测一个特定博弈结果会出现, 所有博弈方都不会利用该预测或者这种预测能力选择与预测结果不一致的策略, 即没有哪个博弈方有偏离这个预测结果的愿望, 因此预测结果会成为博弈的最终结果 只有纳什均衡才具有一致预测的性质 一致预测性是纳什均衡的本质属性 一致预测并不意味着一定能准确预测, 因为有多重均衡, 预测不一致的可能
3 纳什均衡的意义 纳什均衡首先对亚当 斯密的 看不见的手 的原理提出挑战 按照斯密的理论, 在市场经济中, 每一个人都从利己的目的出发, 而最终全社会达到利他的效果 富国论是法家所主张的经济政策, 代表作为荀子的 富国, 主张通过各种经济手段来增加国库收入 富国论 : 通过追求个人的自身利益, 他常常会比想做的那样更有效的促进社会利益
纳什均衡的意义 但是我们可以从 纳什均衡 中 引出 看不见的手 原理的一个悖论 : 从利己目的出发, 结果损人不利己, 既不 利己也不利他 从这个意义上说, 纳什均衡 实际上动摇了西方经济学的基石
定义 : 什么是博弈论 博弈论又称对策论, 它使用严谨的数学模型 研究冲突对抗条件下的最优决策问题 是研究竞 争的逻辑和规律的数学分支 简单的说, 博弈论是研究决策主体在给定信 息结构条件下, 如何决策以使自己的效用最大化, 以及不同决策主体之间决策的均衡 决策的均衡
定义 : 什么是博弈论 博弈的字面意思就是赌博 下棋, 赌博和下棋就 是游戏了, 所以也有人把博弈论叫做游戏理论 赌博和游戏常常要前方百计的应付对手, 所以博 弈论有人也称为对策论
4 博弈的要素 参与人 ( 玩家, Player, Agent) 是博弈的参与主体, 他通过选择自己的行动 ( 策略 ) 来使自己的收益最大化 参与人可以是 自然人, 企业, 国家等 在基于博弈的优化算法中, 参与人代表算法 中的某个元素
4 博弈的要素 参与人的策略集 是参与人可供选择的策略的集合 比如囚徒困境中的欺骗和合作 计算参与人收益的效用函数 给定所有参与人的策略, 通过这个效 用函数计算出各个参与人的收益
4 博弈的要素 行动 参与人在博弈的某个时间点的策略 变量
4 博弈的要素 行动的顺序 在动态博弈中, 行动的顺序对博弈的结果有重要影响 同样的策略集, 行动的顺序不同, 每个人的最优策略就不同, 博弈的结果就不同 尤其在不完全信息博弈中, 后行动者根据先行动者的行动来获取信息
4 博弈的要素 信息 参与人有关博弈的知识, 特别是关于其它参与人的特征和行动的知识, 以及自然的选择 完美信息是指参与人对其它参与人的行动选择有准确的掌握
4 博弈的要素 共同知识 所有参与人知道每一步的信息集步的信息集
策略 ( 战略 ) 4 博弈的要素 参与人在给定信息集情况下的行动规则, 它规定参与人在什么情况下选择什么行动 策略与行动 : 策略是行动的规则而不是行动本身 在静态博弈中, 策略和行动是相同的 策略必须是完备的 : 必须给出参与人在每一种可能的情况下的行动选择
4 博弈的要素 收益 ( 效用, 支付 ) 在给定的策略组合下, 参与人得到的确定的效用水平, 或是参与人得到的期望效用水平 收益由收益函数来计算
4 博弈的要素 均衡 指所有参与人的最优策略组合