[关闭]
@illuz 2015-01-13T08:11:25.000000Z 字数 4943 阅读 2369

人工智能 复习

复习

个人复习，一些仅是给自己的复习提示，具体请自己查书(=w=)。请勿乱传

知识点

  1. 移动

    • Bresenham,视线（略）,拦截

      1. // Bresenham
      2. if (deltaCol > deltaRow) {
      3.     fraction = deltaRow * 2 - deltaCol;
      4.     while (nextCol != endCol) {
      5.         if (fraction >= 0) {
      6.             nextRow = nextRow + stepRow;
      7.             fraction = fraction - deltaCol;
      8.         }
      9.         nextCol = nextCol + stepCol;
      10.         fraction = fraction + deltaRow;
      11.         pathRow[currentStep] = nextRow;
      12.         pathCol[currentStep] = nextCol;
      13.         currentStep++;
      14.     }
      15. } else {
      16.     fraction = deltaCol * 2 - deltaRow; 
      17.     while (nextRow != endRow) { 
      18.         if (fraction >= 0) { 
      19.             nextCol = nextCol + stepCol; 
      20.             fraction = fraction - deltaRow; 
      21.         }
      22.         nextRow = nextRow + stepRow;
      23.         fraction = fraction + deltaCol;
      24.         pathRow[currentStep] = nextRow;
      25.         pathCol[currentStep] = nextCol;
      26.         currentStep++;
      27.     } 
      28. }
      1. // 拦截，类似视线
      2. void     DoIntercept(void) {
      3.     Vector   u, v;
      4.     Bool     left = false;
      5.     Bool     right = false;
      6.     Vector   Vr, Sr, St;
      7.     Double   tc;
      9.     Vr = Prey.vVelocity - Predator.vVelocity;
      10.     Sr = Prey.vPosition - Predator.vPosition;
      11.     tc = Sr.Magnitude() / Vr.Magnitude();
      12.     St = Prey.vPosition + (Prey.vVelocity * tc);
      14.     u = VRotate2D(-Predator.fOrientation, (St - Predator.vPosition));
      15.     u.Normalize();
      16.     if (u.x < -_TOL)
      17.         left = true;
      18.     else if (u.x > _TOL)
      19.         right = true;
      20.     Predator.SetThrusters(left, right);
      21. }
    • 移动模式：
      • 矩形
      • 巡逻
      • 仿真物理中的
    • 群聚
      • Reynolds基本群聚算法核心：凝聚规则、对齐规则、分隔规则。
      • 邻近单位多少是由视野角度及视野半径为参数的函数决定的
      • 避开障碍物思路：替每个单位在前方安装虚拟触角(feeler)，当触角碰到东西，则需要转向。
      • 领头者
    • 势函数
      • Lenard-Jones势函数: U = - A / (r^n) + B / (r^m)
      • 导数后： F = - nA / (r^(n+1)) + nB / (r^(m+1))
      • A、B可以分别作为引力和斥力的强度，n、m则分别代表这两个分力的衰减
      • 应用:追逐/闪躲 避开障碍物 成群结队
    • 路径寻找
      • 基本路径寻找（略）
      • 随机移动避开障碍物：优势
      • 绕行障碍物：线段绕行，视线绕行
      • 面包屑（breadcrumb） 1、初始化足迹数组 2、记录玩家位置 3、丢下面包屑 4、跟随面包屑
      • 沿着道路走:根据权重走
      • 航点寻径：节点表
    • A* 听说A*不考
      • BFS + priority_queue (Open list & Closed list)
      • 地形成本
      • 影响力对应
  2. 脚本AI及组成
    • 脚本概述：为了简化某种特定程序的复杂任务而设计的一种编程语言。
    • 组成：语言和引擎
    • 堆栈机是脚本语言虚拟机技术中普遍采用的一种基本形式：虚拟机，堆栈和指令指针
    • 实例：描述属性、行为、事件等。
  3. 有限状态机
    • 基本概念
      • 有限状态机是由状态（State）、变换（Transition）和行动（Action）组成的行为模型。有限状态机在初始状态（Start State）接收输入事件（Input Event）后转移到下一个状态。通过条件（Guard）判断是否符合转移条件。可以把一个有限状态机看成一个特殊的有向图。
    • 图与程序转化
    • 状态与转移函数：switch
  4. 模糊逻辑
    • 含义与本质
      • 建立模糊性对象的数学模型，在[0，1]区间上取无穷多值的模糊集合
    • 步骤
      • 模糊化
      • 通过模糊规则产生模糊输出
      • 反模糊化
    • 和布尔逻辑在运算时的不同：定义 步骤 归属函数 模糊公理 评估运算
      • 在模糊化中运用
      • 藩篱函数：改变归属度函数的形状
    • 模糊公理
      • 交集\联集\补集
    • 反模糊化
      • 寻找输出模糊集合所占面积的几何中心
      • 单值输出归属度函数
  5. 规则式AI
    • 规则系统的定义及其组成
      • 把一组产生式放在一起, 让它们互相配合, 协同作用, 一个产生式生成的结论可以供另一个产生式作为前提使用, 以这种方式求得问题的解决, 这就叫规则（产生式）系统
      • 产生式系统也可以算作是一种演绎系统。
      • 形式:由一连串的if-then规则组成，用来做推论或行动决策。
      • 规则系统有两个主要部分：工作记忆（事实和断言）和规则记忆
      • 由三个部分组成: 一个综合数据库(数据基) 一组产生式规则(规则库) 一个控制系统(规则解释器)
    • 演绎法
      • 把规则和储存在工作记忆里的事实配对，做法是检查每条规则的if部分，是否和工作记忆里的某组事实和断言吻合。
      • 冲突解决，检查所有吻合的规则，按照某种方式找出想要启动的规则。
      • 当某种规则被选取后，启动该规则，即执行其then部分
    • 归纳法
      • 配对then部分
    • 专家系统

  6. 概率论及贝叶斯技术

    • 标准概率
      • 就是古典概率：p=P(E)=n/N
    • 贝叶斯网络及其组成
      • 基于概率推理的图形化网络，可以替特定问题简明表示出随机变量间的关系。
      • 贝叶斯网络由网络结构和条件概率表两部分组成。网络结构是一个有向无环图，由代表随机变量的节点，以及代表阴机变量间因果关系的弧或连线组成。
    • 先验概率、后验概率和条件概率(癌症阴阳型)
      • 先验概率：根据历史的资料或主观判断所确定的各种时间发生的概率
      • 后验概率：通过贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率修正后得到的更符合实际的概率
      • 条件概率：某事件发生后该事件的发生概率
    • 条件概率公式、贝叶斯公式
      • 条件概率公式：P(B|A)= P(B)P(A|B)/P(A)
      • 贝叶斯公式：P(Bi|A)= P(Bi)P(A|Bi)/sum_(i=1~n){P(Bi)P(A|Bi)}
      • 考点 癌症
    • 推理方式
      • 因果链 预测推理
      • 共通成因网络 诊断推理
      • 共通结果网络 解释消除

    • 预测算法和诊断算法

      1. 预测算法
      2. 输入：给定贝叶斯网络B（包括网络结构m个节点以及某些节点间的连线、原因节点到中间节点的条件概率或联合条件概率），给定若干个原因节点发生与否的事实向量F（或者称为证据向量）；给定待预测的某个节点t。
      3. 输出：节点t发生的概率。
      4. （1）把证据向量输入到贝叶斯网络B中；
      5. （2）对于B中的每一个没处理过的节点n，如果它具有发生的事实（证据），则标记它为已经处理过；否则继续下面的步骤；
      6. （3）如果它的所有父节点中有一个没有处理过，则不处理这个节点；否则，继续下面的步骤；
      7. （4）根据节点n的所有父节点的概率以及条件概率或联合条件概率计算节点n的概率分布，并把节点n标记为已处理；
      8. （5）重复步骤（2）-（4）共m次。此时，节点t的概率分布就是它的发生/不发生的概率。算法结束。
      1. 诊断算法
      2. 输入：给定贝叶斯网络B（包括网络结构m个节点以及某些节点间的连线、原因节点到中间节点的条件概率或联合条件概率），给定若干个结果节点发生与否的事实向量F（或者称为证据向量）；给定待诊断的某个节点t。
      3. 输出：节点t发生的概率。
      4. （1）把证据向量输入到贝叶斯网络B中；
      5. （2）对于B中的每一个没处理过的节点n，如果它具有发生的事实（证据），则标记它为已经处理过；否则继续下面的步骤；
      6. （3）如果它的所有子节点中有一个没有处理过，则不处理这个节点；否则，继续下面的步骤；
      7. （4）根据节点n所有子节点的概率以及条件概率或联合条件概率，根据条件概率公式，计算节点n的概率分布，并把节点n标记为已处理；
      8. （5）重复步骤（2）-（4）共m次。此时，原因节点t的概率分布就是它的发生/不发生的概率。算法结束。
  7. 神经网络
    • 含义及结构
      • 是对人脑或自然神经网络若干基本特性的抽象和模拟。
      • “人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入的状态相应的进行信息处理。”
      • 特点：逼近非线性关系，鲁棒性和容错性，并行分布处理，学习和自适应，同时处理定量、定性知识。
      • 结构：分为输入层(预测变量)、输出层(目标变量)和隐含层(处理)。
    • 前馈神经网络
      • 后一节点的值通过它前面相连的节点传过来，然后把值按照各个连接权重的大小加权输入活化函数再得到新的值，进一步传播到下一个节点。
      • 发生错误时，神经网络就要 “学习”
      • 可以把节点间连接的权重看成后一节点对前一节点的“信任” 程度
      • 采用惩罚的方法进行权重的调整。
      • 节点总输入值 = sum(前面节点的输入值 * 连接的权重) + 偏差项
      • 用活化函数让输出更加非线性：logistic函数(S型函数),阶跃函数,双曲正切函数,线性活化函数
      • 偏差项 = 偏差值 * 偏差权重。水平移动总输入值，有效改变神经元活化的阈值。
    • 监督式学习网络和非监督式学习网络
      • 监督式学习网络，从问题领域中提供训练范例，包含输入资料与输出资料。
      • 无监督式学习网络，在学习时并不知道其分类结果是否正确
    • 训练
      • 训练的目标是找出连接所有神经元之值的权重，让输入层可以产生所需的输出值。
      • 首先，需要一个训练数据集，由输入数据（和对应的输出数据）组成；
      • 接着，利用某种技术，不断重复地替整个网络找出一组权重值，使得该网络可以产生符合训练数据集内，每组数据所要的输出结果；
      • 最后，让网络启动，提供不在训练数据集内的新数据，使其产生合理的输出结果。
    • 倒传递法及其过程
      • 倒传递法的实质是用试误法把误差最小化。有了输入值以及产生的输出值后，把产生的输出值和已知想要的输出值作比较，用均方差量化二者之间的吻合度。
        1. 训练数据集
        1. 权重初值设为某些较小的随机数
        1. 算出输出值
        1. 与希望值比较，算出误差(圴方误差)
        1. 调整权重（校正值 = 学习率 * 神经元误差 * 神经元输出值），重复

  8. 遗传算法

    • 概念
      • 种群：生物的进化以群体的形式进行，这样的一个群体称为种群。
      • 种群规模：即种群中染色体个体的数目。
      • 个体：组成种群的单个生物，即优化问题的解。
      • 基因：一个遗传因子。 
      • 染色体：包含一组的基因。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。
      • 生存竞争，适者生存：对环境适应度高的的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。
      • 遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。
      • 交叉概率：控制着交叉算子的使用频率。 
      • 变异概率：控制着变异算子的使用频率。
    • 机理
      • 首先，算法随机生成一定数量的个体，计算适应度，排序
      • 下一步是产生下一代个体并组成种群，这个过程是通过选择和演化完成的
      • 选择常用“比例选择”：“轮盘赌算法”
      • 演化包括交叉和变异。
      • 终止条件：次数限制，资源限制，最优值，适应度饱和，人为干预

    • 简单算法

      • 轮盘赌算法

        1. /* 按设定的概率，随机选中一个个体， P[i]表示第i个个体被选中的概率*/
        2. int RWS() {
        3.     m = 0;
        4.     r = Random(0, 1); //r为0至1的随机数
        5.     for (i = 1; i <= N; i++) {
        6.         /* 产生的随机数在m~m+P[i]间则认为选中了i，因此i被选中的概率是P[i]*/
        7.         m = m + P[i];
        8.         if (r <= m) return i;
        9.     }
        10. }

      • 简单遗传算法-伪代码 

        1. /*Pc：交叉发生的概率， Pm：变异发生的概率， M：种群规模，G：终止进化的代数， Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程*/
        2. 初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Pop;
        3. do {
        4.     计算种群Pop中每一个体的适应度F(i);
        5.     初始化空种群newPop;
        6.     do {
        7.         根据适应度以比例选择算法从种群Pop中选出2个个体;
        8.         if (random(0, 1) < Pc) {
        9.             对2个个体按交叉概率Pc执行交叉操作;
        10.         }
        11.         if (random(0, 1) < Pm) {
        12.             对2个个体按变异概率Pm执行变异操作;
        13.         }
        14.         将2个新个体加入种群newPop中;
        15.     } until(M个子代被创建);
        16.     用newPop取代Pop;
        17. } until(任何染色体得分超过Tf， 或繁殖代数超过G);
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注