智能计算考试复习资料

第_章绪论1、 智能计算一一智能计算是信息科学、生命科学、认知科学等不同学科相互交叉的产物。它主要借鉴仿生学和拟物的思想，基于人们对生物体智能机理和某些自然规律的认识，采用数值计算的方法去模拟和实现人类的智能、生物智能、其它社会和自然规律。2、 智能计算的应用领域一一图像处理、数学计算、调度管理、市场营销、模式识别，另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。第二章演化计算1、 演化计算——演化计算是采用二进制编码或实数编码技术来表示各种复杂问题的结构，并通过对这些编码进行交叉和变异操作来实现优胜劣汰的自然选择，进而指导学习和确定搜索的方向。2、 演化计算基本概念：1、 种群(poputation)：由若干个个体组成个体的集合，称为种群(population)2、 迭代步(或演化代)3、 种群规模(poputationsize)：种群中含有的个体的数量叫做种群的规模(populationsize)。4、 个体(individual):—个二进制串叫做一个个体(individual)05、 父代(parent)6、 后代(offspring)7、 问题空间：待求解问题的所有解8、 基因空间：所有编码组合9、 染色体：问题解的编码串10、 基因(gene):染色体的每一位11、 基因位(locus)：基因在染色体中所处的位置12、 等位基因(allele)：基因的取值13、 基因型(genetype):编码空间中的点14、 表现型(phenotype):演化算法通常要将问题的解进行编码，即通过变换将问题空间映射到编码空间，这个变换要求是可逆的，称为解码变换，被称为表现型15、模式：表示 中的一些特定的子集。如果用*表示一个通配符，即在该位置既可以取0又可以取1，则空间 表示所有模式全体，如l=5时，模式H=01**1表示集合{01001，01101，01011，0111}o16、 模式的阶：出现在模式中取确定值位置的数目，如H=01**1的阶为317、 模式的长度：模式中第一个取确定值位置与最后一个取确定值位置之间的距离。3、 遗传算法基本思路(会画流程图)适应度函数的选取方式4、 演化计算的编码设计的方法（1） 二进制编码（2） 格雷（Gray）编码（3） 动态编码（4） 实数编码（5） 有序串编码（6） 结构式编码5、 遗传算法可以在哪些方面做改进？（1）控制参数的调整（2）遗传算子的改进（3）与其它启发式搜索技术结合构成的基本遗传算法的混合搜索算法6、 演化计算的主要特征一一1、智能性2、并行性3、处理对象的多样性4、群体搜索性5、稳健性6、随机性7、挑战性第三章蚁群算法1、应用领域——这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。2、算法实现步骤（下载蚁群算法求解TSP的流程图）3、蚁群算法的数学建模模型（29）

3.2.4蚁群算法与TSP问题1/3TSP问题表示为一个N个城市的有向^G=（N;A）,其中N={1,2,…刀}A={（i,j）NjeV}城市之间距离（日^）…目标函数为 f3）=文d心山，1=1W二其中 y="为城市1?•••「的4、公式（34）用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。 \ \（i,j）为W上的一条孤（i,j）不是W上的一条孤JT(k)=(1-P )T(k-1)+海ij k-1ij |w|k-1ij、T(k)=(1-P )T(k-1) k-1ijij得到新的 号k），k：=k+15、 会写算法6、 优缺点优点：1、无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性2、以非直接的信息交流方式确保了系统的扩展性3、并行分布式算法模型，可充分利用多处理器4、对问题定义的连续性无特殊要求5、算法实现简单缺点：1、搜索时间长2、易陷于局部最优解3、收敛速度慢7、 改进（为什么、如何）（1） 状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法（2） 全局更新规则应用于最优的蚂蚁路径上（3） 在建立问题解决方案的过程中，应用局部信息素更新规则第四章模拟退火算法1、基本思想和步骤（14）（三个函数、两个准则）415 必退北募注狗基本忌恩剥步骤,影响优化结果的主要因素给定初温仁°随机产生初始状态$=%,令40；RepeatRepeat产生新状态铲Genete($)；ifmin [0J]$=亏;Until拙程稳定准则满足；退温4+亍叩曲龙傀)并令A^fc+i； 二函数两准MP准则 一出Metropolis准则(1953) 以概率接受新状态温度固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法(计算机随机模拟方法)加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。•Metropolis出Metropolis准则(1953) 以概率接受新状态温度固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法(计算机随机模拟方法)加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。固体在恒定温度下i•….若在温度乙当前状态i一新状态j若与＜瓦，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。p=exp[-(E/-Ei)/kBT]在高温下，可接受与当前状态能量差较大的新状态;在低温下，只接受与当前状态能量差较小的新状态。第五章神经网络1、工作原理(图、能想到的函数(5))OutputArtivsticnfunctjQO(moreonthislater)Output激活函数：S形函数2、2种神经网络的拓扑结构(1)感知器：W-H激活函数：S形函数2、2种神经网络的拓扑结构(1)感知器：W-H学习规则(2)BP网：构造一个函数E(W，B)=1/2(wx-B)3、 例子(数字)思路：1、2、3、4、5……4、 学习规则(12)感知器学习规则的实质为：权值的变化量等于正负输入矢量。对于所有的i和j，i=l，2，…，s；j=1，2，…，r，感知器修正权值公式为:AW.=(o.-y.)*尤Ab.=(o-y.)*15、 异或问题一一一个只有两个输入和一个输出，且输入输出都只取1和0两个值的问题。线性不可分问题一一单层感知器不能表达的问题被称为线性不可分问题。6、 网络模型（可只标大小写）会写学习规则第六章贪心算法1、 贪心算法一一从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：-1.不能保证求得的最后解是最佳的；-2.不能用来求最大或最小解问题；-3.只能求满足某些约束条件的可行解的范围2、 举例常见例子，如构造哈弗曼树，求最小生成树第七章分治法1、 分治一一所谓分治，就字面意思而言，就是分而治之，将一个问题分解成为若干个与原有问题相似但规模较小的子问题，然后递归的求解这些子问题，最后合并这些子问题的结果就得到原问题的解了。一个问题能否用分治法解决，关键是看该问题是否能将原问题分成n个规模较小而结构与原问题相似的子问题。递归的解决这些子问题，然后合并其结果就得到原问题的解。2、 二分一一当n=2时的分治法又称二分法。第八章动态规划1、思想一一具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。动态规划是一种分段最优化方法，它既可以用来求解约束条件下的函数极值问题，也可以用来求解约束条件下的泛函极值问题。它与极小值原理一样，是处理控制矢量被限制在一定的闭集内，求解最优控制问题的有效数学方法之一。动态规划的核心是最优性原理，它首先将一个多段决策问题转化为一系列单段决策问题，然后从最后一段状态开始逆向递推到初始状态为止的一套求解最优策略的完整方法。动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。2、设计一个标准的动态规划算法，通常可按以下几个步骤进行：（1） 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。（2） 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。第九章灰色预测1、了解一一灰色理论认为系统的行为现象尽管是朦胧的，数据是复杂的，但它毕竟是有序的，是有整体功能的。灰数的生成，就是从杂乱中寻找出规律。同时，灰色理论建立的是生成数据模型，不是原始数据模型，因此，灰色预测的数据是通过生成数据的gm（1,1）模型所得到的预测值的逆处理结果。第十章专家系统1、专家系统一一专家系统是一种模拟人类专家解决领域问题的计算机程序系统。-具有大量的专门知识与经验-根据某领域一个或多个专家提供的知识和经验，进行推理和判断-需要解决的问题要足够的复杂2、组成部分、体系结构3、知识表达的方一一1、基于规则的表达方法2、基于框架的表