智能计算导论

智能计算绪论11.1引言1.1.1优化问题1.1.2传统优化方法1.1.3现代优化方法1.2最优化问题及其分类1.2.1函数优化问题1.2.2组合优化问题1.3启发式算法1.3.1启发式算法的定义1.3.2启发式算法的分类1.3.3启发式算法的性能分析1.4计算复杂性与NP完全问题1.4.1计算复杂性的基本概念1.4.2P,NP,NP-C和NP-hard智能优化计算智能计算绪论21.1引言智能优化计算优化技术？以数学为基础，解决各种工程问题优化解优化技术的用途系统控制人工智能模式识别生产调度……1.1.1优化问题智能计算绪论31.1引言智能优化计算最优化问题的描述最优化问题的数学模型的一般描述：1.1.1优化问题Dxxgtsxf,0)(..)(min智能计算绪论41.1引言智能优化计算待解决的问题连续性问题，以微积分为基础，规模较小、多峰多谷传统的优化方法理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性、收敛速度1.1.2传统优化方法智能计算绪论51.1引言智能优化计算待解决的问题离散性、不确定性、大规模现代的优化方法启发式算法（heuristicalgorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法算法复杂性1.1.3现代优化方法智能计算绪论61.2最优化问题及其分类（函数优化和组合优化）智能优化计算数学表述难点高维多峰值1.2.1函数优化问题的定义域），上的有界子集（即变量为令nRS域上在维实值函数，所谓函数为SfnRSf:在使得全局最小化就是寻求点)(minminXfSX。域上全局最小，即)()(:minXfXfSXS智能计算绪论71.2.2常见求解方法1.一维函数优化优选法：黄金分割法、分数法、正交实验设计特点：只能解决单峰函数的最优值问题搜索法：按照某种方向（如最速下降方向、梯度方向）选取步长搜索（是一种迭代技术）2.多维函数优化特点：迭代+搜索选取初始点、按照某个方向（如最速下降方向、梯度方向）选取步长搜索最速下降法、梯度与共轭梯度法、Newton法（拟Newton法）等等一般只能解决单峰函数的最优化问题（why?)智能计算绪论8测试函数（8）GeneralizedSchwefel’sProblem2.26(multimodal)500||,))sin(()(1iniiixxxXf典型的多峰、多谷函数，确定性算法求解很可能导致局部最优智能计算绪论91.2最优化问题及其分类智能优化计算（1）SphereModel(unimodal)其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题100||,)(12iniixxXf0)0,,0,0())(min(*fXf智能计算绪论101.2最优化问题及其分类智能优化计算测试函数（2）Schwefel’sProblem2.22(unimodal)其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题0)0,,0,0())(min(*fXf10||,||||)(11ininiiixxxXf智能计算绪论111.2最优化问题及其分类智能优化计算测试函数（3）Schwefel’sProblem1.2其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题0)0,,0,0())(min(*fXf100||,)()(211iniijjxxXf智能计算绪论121.2最优化问题及其分类智能优化计算测试函数（4）Schwefel’sProblem2.21其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题0)0,,0,0())(min(*fXf100|||},{|max)(1iinixxXf智能计算绪论131.2最优化问题及其分类智能优化计算测试函数（5）GeneralizedRosenbrock’sFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题30||,])1()(100[)(112221iniiiixxxxXf0)1,,1,1())(min(*fXf智能计算绪论141.2最优化问题及其分类智能优化计算测试函数（6）StepFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题100||,)5.0()(12iniixxXf0)0,,0,0())(min(*fXf智能计算绪论151.2最优化问题及其分类智能优化计算测试函数（6）StepFunction1.2.3函数优化之常见的Benchmark问题智能计算绪论161.2最优化问题及其分类智能优化计算测试函数（7）QuarticFunctioni.e.Niose其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题28.1||,)1,0[)(14iniixrandomixXf0)0,,0,0())(min(*fXf智能计算绪论171.2最优化问题及其分类智能优化计算测试函数（8）GeneralizedSchwefel’sProblem2.26其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题500||,))sin(()(1iniiixxxXfnfXf9829.418)9687.420,,9687.420,9687.420())(min(*智能计算绪论181.2最优化问题及其分类智能优化计算测试函数（8）GeneralizedSchwefel’sProblem2.26(multimodal)1.2.3函数优化之常见的Benchmark问题智能计算绪论191.2最优化问题及其分类智能优化计算测试函数（9）GeneralizedRastrigin’sFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题12.5||,]10)2cos(10[)(12iniiixxxXf0)0,,0,0())(min(*fXf智能计算绪论201.2最优化问题及其分类智能优化计算测试函数（10）Ackley’sFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题32||,20)/)2cos(exp()/2.0exp(20)(112iniiniixenxnxXf0)0,,0,0())(min(*fXf智能计算绪论211.2最优化问题及其分类智能优化计算测试函数（10）Ackley’sFunction1.2.3函数优化之常见的Benchmark问题智能计算绪论221.2最优化问题及其分类智能优化计算测试函数（11）GeneralizedGriewankFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题600||,1cos40001)(112iininiixixxXf0)0,,0,0())(min(*fXf智能计算绪论231.2最优化问题及其分类智能优化计算测试函数（11）GeneralizedGriewankFunction1.2.3函数优化之常见的Benchmark问题智能计算绪论241.2最优化问题及其分类智能优化计算测试函数（12）GeneralizedPenalizedFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题50||,)4,100,10,()1()](sin101[)1()(sin10)(111212212iniininiixxuyyyynXf0)1,,1,1())(min(*fXf智能计算绪论251.2最优化问题及其分类智能优化计算测试函数其中，1.2.3函数优化之常见的Benchmark问题axaxkaxaaxaxkmkaxuxyimiiimiiii,)(,0,)(),,,(4/)1(1智能计算绪论261.2最优化问题及其分类智能优化计算测试函数（13）GeneralizedPenalizedFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题同上)(,50||,)4,100,5,()1()]3(sin1[)1()3(sin1.0)(111212212uxxuxxxxXfiniininii0)1,,1,1())(min(*fXf智能计算绪论271.2最优化问题及其分类智能优化计算测试函数（14）Shekel’sFoxholesFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题56.65||,)(15001)(1251216ijiijixaxjXf1)32,32())(min(*fXf智能计算绪论281.2最优化问题及其分类智能优化计算测试函数其中，1.2.3函数优化之常见的Benchmark问题3232,32,16,32,0,32,16,32,32,16,32,16,16,16,0,16,16,16,32,0,32,0,16,0,0,0,16,0,32,16,32,16,16,16,0,16,16,16,32,32,32,32,16,32,0,32,16,32,32)(ija智能计算绪论291.2最优化问题及其分类智能优化计算测试函数（15）Kowalik’sFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题5||,)()(1112432221iiiiiiixxxbbxbbxaXf0003075.0)1358.0,1231.0,1928.0,1928.0())(min(*fXf智能计算绪论301.2最优化问题及其分类智能优化计算测试函数其中，1.2.3函数优化之常见的Benchmark问题)16,14,12,10,8,6,4,2,1,5.0,25.0()/1()0246.0,0235.0,0323.0,0342.0,0456.0,0627.0,0844.0,16.0,1735.0,1947.0,1957.0()(iiba智能计算绪论311.2最优化问题及其分类智能优化计算测试函数（16）Six-HumpCamel-BackFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题5||,443/1.24)(422221614121ixxxxxxxxXf0316285.1)7126.0,08983.0()7126.0,08983.0())(min(*ffXf智能计算绪论321.2最优化问题及其分类智能优化计算测试函数（17）BraninFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题150,105,10cos811106541.5)(211212122xxxxxxXf398.0)425.2,425.9()275.2,142.3()275.2,142.3())(min(*fffXf智能计算绪论331.2最优化问题及其分类智能优化计算测试函数（18）Goldstein-PriceFunction其最优状态和最优值为1.2.3函数优化之常见的Benchmark问题2)],273648123218()32(30[)]361431419()1(1[)(2221221122122212211221ixxxxxxxxxxxxxxxxxXf3)1,0(