随铭的博客

6: Genetic Algorithm What are the different types of EAs EA 有哪些不同类型？ Historically different flavors of EAs have been associated with different representations 从历史上看，不同流派/形式的 EA 通常与不同的表示方式（representations）联系在一起 Binary strings: Genetic Algorithms 二进制字符串：遗传算法（Genetic Algorithms, GA） Real-valued vectors: Evolution Strategies 实数向量：进化策略（Evolution Strategies, ES） Finite state machines: Evolutionary Programming 有限状态机：进化规划（Evolutionary Programming, EP） Trees: Genetic Programming 树结构：遗传编程（Gen...

2: Evolution -From biology to algorithms进化—从生物学到算法 Why Biology?为什么选择生物学？ Biology provides metaphors, not mechanisms 生物学提供的是比喻和启发，而不是需要被完整复制的真实机制。 We borrow principles, not molecular details 们借用的是生物学中的基本原则，而不是分子层面的细节 Our goal: understand how population + variation + selection become algorithms 我们的目标是理解 population + variation + selection 如何转化成算法。 EC design principles EC uses the principles of (EC 使用了以下原理） Darwinian evolution (macroscopic view) - survival of the fittest达尔文进化论（宏观视角）——适者...

1: Introduction to Evolutionary Computing 进化计算导论 Positioning of Evolutionary Computation进化计算的定位 EC is part of computer science - computational intelligence - bio-inspired computing EC 是计算机科学的一部分，属于计算智能（computational intelligence），也属于受生物启发的计算（bio-inspired computing） Biology delivered inspiration and terminology 生物学为 EC 提供了灵感和术语。 EC can be used as a tool for biological research EC 也可以作为生物学研究的工具。 4.Systematic trial-and-error (generate-and-test) problem solving 系统化的试错式（生成并测试）问题求解方法。 Motivat...

5: EA Behaviors EA for 8-Queens 用于八皇后问题的 EA Why do we sometimes prohibit certain constraint violations (e.g., horizontal or vertical) but allow others (e.g., diagonal), when designing representation and variation operators? 在设计表示方式和变异算子时，为什么有时禁止某些约束违反（例如水平方向或垂直方向的冲突），但允许其他约束违反（例如对角线冲突）？ How large should the population be? How can we reason about an appropriate or effective population size? 种群应该多大？我们如何判断一个合适或有效的种群规模？ Do we need both crossover and mutation? In which order should they be a...

4-EightQueens The eight queens puzzle 八皇后问题 Task: place 8 queens on an 8 by 8 chessboard 任务：将 8 个皇后放置在一个 8×8 的国际象棋棋盘上。 Goal: no two queens attack each other 目标：任意两个皇后都不能相互攻击。 Brute force: 64636261605958*57 = 178,462,987,637,760 暴力搜索：64×63×62×61×60×59×58×57 = 178,462,987,637,760 8765432*1 = 40,320 利用每行/每列仅放一个皇后的限制：8×7×6×5×4×3×2×1 = 40,320 The eight queens puzzle: EA 八皇后问题 Represent the problem solution? phenotype? genotype? 如何表示问题的解？ phenotype？genotype？ Evaluate fitness? 评估fit...

3-EAbasics Main components of the design of an EA EA 设计的主要组成部分 How does an EA turn trial-and-error into a systematic adaptive search? EA 如何把试错（trial-and-error）变成一种系统性的自适应搜索（systematic adaptive search）？ Representation (definition of individuals) - What can we try? 表示方式（individual 的定义）——我们可以尝试什么？ Evaluation function (or fitness function) - How do we know they are good? 评价函数（或 fitness function）——我们怎么知道这些 solution 好不好？ Population and initialization - How do we start? 种群和初始化——我们怎么开始？ Par...

4.1 - Recursion WHAT IS RECURSION? A statement that refers to itself一个指代自身的陈述 OR：一个句子中，相同的谓语(predicate)出现在头部和身体中 递归是计算机编程中的一种强大工具。 Example: Ancestors 什么是祖先？ • 父母parent • 祖父母grandparent • 曾祖父母great-grandparent • 曾曾祖父母great-great-great-great • 等等 12ancestor(X,Y) :- X is directly above Y, in the family tree, by any number of generations.(X在家族谱系中直接位于Y之上，无论经过多少代。) 我们如何向Prolog解释这个？ Brute Force Version 12345ancestor (X,Y):-parent (X,Y). ancestor (X,Y):-grandparent (X,Y). ancestor (X,Y):-greatGrand...

Week4 Minimax Types of Games General Games Agents具有独立的效用(utilities) 合作、冷漠、竞争等都是可能的 我们不让AI独自地行动，它应当 a) 与人协同工作 b) 帮助人类 这意味着每个AI agents理都需要解决game Zero-Sum Games Agents具有相反的效用(utility)（即对结果的价值） A 觉得越好，B 就越坏 让我们设想一个单一的数值，一个代理最大化(maximizes)而另一个最小化(minimizes) 可以把结果用一个分数/价值表示：A 想把它变大，B 想把它变小。 对抗性的(Adversarial,)，纯竞争(competition) Deterministic Games with Terminal Utilities Many possible formalizations, one is: States: S (start at [s_0])（状态集合，起点 [s_0]） [S] 是所有可能局面的集合。 [s_0] 是初始状态（...

2 - Introduction to Prolog VARIABLE NAMES 考虑：parent(X,luke), + male(X). Prolog首先将变量替换为新名称 parent(G312,luke), + male(G312). • 这样在遇到其他句子中名为X的变量时，就不会产生混淆。 TRACING TRACING A QUERY There are 4 types of actions Call（调用） 含义： 逻辑引擎开始尝试解决一个查询或子目标。 动作： 它会进入程序数据库，寻找能与当前查询匹配（合一）的第一条规则或事实。 Exit（成功退出） 含义： 查询成功，找到了匹配项。 动作： Prolog 暂时满足了这个目标，并返回 true。如果查询中包含变量，此时变量会被赋予特定的值（绑定）。 Fail（失败退出） 含义： 无法找到能满足查询的匹配项。 动作： 这一步返回 false。这通常会触发 Redo，让程序回头去寻找其他的可能性。 Redo（重试） 含义： 回溯（Backtracking）。 动作： 当之前的某个分支失败...

Week1 Search Search Problems（搜索问题） 组成: **状态空间（state space）:**所有可能出现的“情况/局面”（比如游戏里每一种棋盘摆法、迷宫里每个位置等 后继函数（successor function）(包含动作与代价）: 从当前状态出发，你能做哪些动作（actions），做完会到达哪些新状态； 每个动作可能还有代价/成本（cost）（图里示例动作 N/E，代价 1.0）。 起始状态 + 目标测试（start state & goal test） 从哪里开始（start state） 怎么判断“到目标了”（goal test：是否满足目标条件） State Space 和 Search state World state（世界状态） 包含环境的所有细节, 例如整张地图里：墙、豆子、怪物、角色位置……每一个细节都算进去。 Search state（搜索状态） 只保留“为了规划/解题需要”的信息（抽象 abstraction） State Space Graph（状态空间图）/Search Trees（搜索树...