计算智能第1章 绪论
第1章 绪论,Contents,最优化问题,1,计算智能的分类与理论 计算智能的研究与发展 计算智能的特征与应用,1.1 最优化问题,最优化问题的求解模型如下公式所示 Min f(X), XD 其中D是问题的解空间，X是D中的一个合法解。一般可将X表示为X = (x1, x2, , xn)，表示一组决策变量 最优化问题就是在解空间中寻找一个合法的解X（一组最佳的决策变量），使得X对应的函数映射值f(X)最小（最大） 最优化问题的分类,1.1 最优化问题,根据决策变量xi的取值类型，我们可以将最优化问题分为函数优化问题和组合优化问题两大类,1.1.1 函数优化问题,例如： 其中，n=30表示问题空间的维数，xi -100,100是定义域，这个函数的最小值为0 这是一个最简单的函数优化问题,1.1.1 函数优化问题,很多科学实验参数配置和工农业生产实践都需要面临这种类型的最优化问题 例如设计神经网络的过程中，需要确定神经元节点间的网络连接权重，从而使得网络性能达到最优 在这种问题中，需要优化的变量的取值是某个连续区间上的值，是一个实数。各个决策变量之间可能是独立的，也可能是相互关联、相互制约的，它们的取值组合构成了问题的一个解 由于决策变量是连续值，因此对每个变量进行枚举是不可能的。在这种情况下，必须借助最优化方法对问题进行求解,1.1.2 组合优化问题,组合优化问题的决策变量是离散取值的 例如整数规划问题，0-1规划问题等等 很多离散组合优化问题都是从运筹学（Operations Research，OR）中演化出来的 组合优化其所研究的问题涉及到信息技术、经济管理、工业工程、交通运输、通信网络等众多领域，在科学研究和生产实践中都起着重要的作用,1.1.2 组合优化问题,经典组合优化问题： 旅行商问题（Traveling Salesman Problem，TSP） 0-1背包问题（Zero/one Knapsack Problem，ZKP/0-1KP/KP） 当问题规模n比较大时，用枚举方法所需时间太大，我们借助智能优化计算方法，可以在合理的时间内求解得到令人满意的解，从而满足实践的需要,1.2.1 计算复杂性,计算复杂性（Computational Complexity）描述求解问题的难易程度或者算法的执行效率 对于算法的计算复杂性，我们一般很容易进行判断，例如使用蛮力法去枚举旅行商问题或者0-1背包问题的算法，就是具有指数计算复杂性的算法 对于某问题的计算复杂性进行判断却不是一件简单的事情,1.2.1 计算复杂性,问题的计算复杂性是问题规模的函数，故需要首先定义问题的规模 例如对于矩阵运算，矩阵的阶数可被定义为问题的规模 如果求解一个问题需要的运算次数或步骤数是问题规模n的指数函数，则称该问题有指数时间复杂性 如果所需的运算次数是n的多项式函数，则称它有多项式时间复杂性 对于某个具体问题，其复杂性上界是已知求解该问题的最快算法的复杂性，而复杂性下界只能通过理论证明来建立 证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多,1.2.2 NP理论,P类问题（Polynomial Problem） P类问题是指一类能够用确定性算法在多项式时间内求解的判定问题。其实，在非正式的定义中，我们可以把那些在多项式时间内求解的问题当作P类问题。,1.2.2 NP理论,NP类问题（Non-deterministic Polynomial Problem） NP类问题是指一类可以用不确定性多项式算法求解的判定问题。例如旅行商问题的判定版本就是一个NP类问题。我们虽然还不能找到一个多项式的确定性算法求解最小的周游路线，但是可以在一个多项式时间内对任意生成的一条“路线”判定是否是合法（经过每个城市一次且仅仅一次）。比较P类问题和NP类问题的定义，我们很容易得到一个结论：PNP。,1.2.2 NP理论,NP完全问题（NP Complete Problem） 我们称一个判定问题D是NP完全问题，条件是： （1）D属于NP类； （2）NP中的任何问题都能够在多项式时间内转化为D。,1.2.2 NP理论,NP完全问题（NP Complete Problem） 另外，一个满足条件（2）但不满足条件（1）的问题被称为NP难问题。也就是说，NP难问题不一定是NP类问题，例如图灵停机问题。正式地说，一个NP难问题至少跟NP完全问题一样难，也许更难！例如在某些任意大的棋盘游戏走出必胜的下法，就是一个NP难的问题，这个问题甚至比那些NP完全问题还难。,1.3 计算智能方法,计算智能算法是人工智能的一个分支，是联结主义的典型代表，又称为仿生学派或生理学派。,计算智能,1.3 计算智能方法,随着技术的进步、工程实践问题变得 越来越复杂，传统的计算方法面临着 计算复杂度高、计算时间长等问题,计算智能方法采用启发式的随机搜索 策略，在问题的全局空间中进行搜索 寻优，能在可接受的时间内找到全局 最优解或者可接受解,计算智能算法在处理优化问题的时候， 对求解问题不需要严格的数学推导，而 且有很好的全局搜索能力，具有普遍的 适应性和求解的鲁棒性,1.3 计算智能方法,计算智能是人工智能的重要领域， 也是近几十年来研究的热点问题。 计算智能的兴起和快速发展，为 人工智能提供了新的出路,计算智能技术在国内得到了广泛的 重视。由于这个领域的研究涉及到 的硬件要求不高，国内的研究已经 达到国际认可的水平,计算智能技术的进一步发展和完善， 以及应用的进一步拓展，都将对计 算机技术和各个相关的应用领域带 来深刻的变革,1.3.1 计算智能的分类与理论,1.3.1 计算智能的分类与理论,计算智能主要研究方向及其特点,1.3.1 计算智能的分类与理论,计算智能有关理论基础,1.3.2 计算智能的研究与发展,遗传算法(GA) Genetic Algorithm,神经网络(NN) （感知器）,1950s Rosenblatt等人,1950s 美国学者Holland,进化策略(ES) Evolution Strategy,进化规划(EP) Evolutionary Programming,1960s 德国人Rechenberg Schwefel,1960s 美国学者Fogel,模糊逻辑理论(FL) Fuzzy Logic,1960s 美国学者Zadeh,1.3.2 计算智能的研究与发展,遗传算法、进化策略、进化规划 的理论基础不断完善（模式定理） 算法之间的区别越来越不明显,禁忌搜索算法（1986年） 模拟退火算法（1983年） 的提出提供了新的优化手段,Hopfield前馈型神经网络结构（1982年） Rumelhart后向传播学习算法（1986年） 的提出将神经网络的研究推向一个新的高潮,1.3.2 计算智能的研究与发展,1.3.2 计算智能的研究与发展,计算智能相关的学术期刊和国际会议,1.3.3 计算智能的特征与应用,1.3.3 计算智能的特征与应用,计算智能的应用,Thank You !,
