计算智能第1章 绪论.pptVIP

Company Logo 第1章 绪论 Contents 最优化问题 1 计算复杂性及NP理论 2 计算智能算法 3 计算智能的分类与理论 计算智能的研究与发展 计算智能的特征与应用 1.1 最优化问题 最优化问题的求解模型如下公式所示 Min f(X), X?D 其中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类问题的定义，我们很容易得到一个结论：P?NP。 1.2.2 NP理论 NP完全问题（NP Complete Problem） 我们称一个判定问题D是NP完全问题，条件是： （1）D属于NP类； （2）NP中的任何问题都能够在多项式时间内转化为D。 1.2