文档介绍：智能优化算法
杨圣洪
******@
346260267(qq)
绪论----最优化的历史
微积分中函数极值，最早的无约束函数优化。
拉格朗日乘子法是最早的约束优化方法。
二战时运筹学(Operation Research)，解决受多个约束条件限制时，目标函数值的最大化(最小化).
其方法有线性规划(单纯型法)、动态规划、博弈论、排队论、存储论等，
这些方法在二次世界大战后，被运用到了经济等诸多领域。
传统最优化的解法
1、选择一个初始解
该解必须是一个可行解。
2、判断停止准则是否满足
一般为最优性条件。如单纯型方法是最下一行的值均为非负。
3、向改进方向移动
由于采用迭代方法，当不满足停止条件时，需要不断修改当前解。
传统最优化的解法的缺陷
1、单点运算方式，一个初始解出发，迭代只对一个点进行计算，无法并行计算、多核计算。
崽多好打架！无法群狼战略！
2、向改进方向移动,限制了跳出局部最优的能力,都使得目标函数降低，即不具备“爬山”能力,没有全局搜索能力.
3、停止条件只是局部最优性的条件, 只有当解的可行域凸集、目标函数凸函数时才全局最优。
4、目标函数、约束函数必须连续可微，甚至还要高阶可微
一些新现象
1、目标函数与约束条件不连续，可能离散，可能含有规则、条件和逻辑关系。
2、计算的效率优先, 如TSP问题，本身是一个NP完全问题，更关注算效率，而非最优解。
3、传统方法计算终止可能得到的解,连可行解都不是。但问题要求达到限定迭代次数后就停机，希望此时得到的解是比较优化的解。
4、优化计算中的数据可能不精确，初始解可能不是可行解，甚至远离可行解。数据可能是随机变量、模糊集合。
智能优化方法的历史
1975年、Holland、Genetic Algorithms(遗传算法)：模仿生物种群中优胜劣汰适者生成机制，通过种群中优势个体的繁殖进化来实现优化。通过选择、交叉、变异来寻优，常用于非线性最优化和复杂的组优化或整数规划问题、管道优化设计(网络流)、通风网络的设计、飞机外形设计、图像处理、VLSI设计。
1977年、Glover、Tabu Search(禁忌搜索算法)：将记忆功能引入到最优解的搜索过程中，通过设置禁忌区阻止搜索过程中的重复，这在图论中最短路径的disjktra算法等都用过，从而大大提高寻优过程的搜索效率。
智能优化方法的历史
197X年、Jerne、Artificial immune System(人工免疫系统)。通过进化学习辨别危险的外部物体(细菌、病毒等)和体内自身的细胞(或分子)，通过从不同种类的抗体中，构造处理外部物体的方法或物质。具有并行、分布、自适应性、学忆和特征提取能力。
用于模式识别、信息安全、智能优化、机器学习、数据挖掘、自动控制、故障诊断等领域。
1999年、Hunt、Clone(克隆选择算法)，只有识别抗原的细胞的能进行clone扩增，同时克隆产生的细胞又高频变异，满足生物的多样性要求，使之具有爬山的能力，全局搜索呀！。
智能优化方法的历史
1983年、Kirkpatrick、Simulated Annealing(模拟退火算法)。热力学中退火使金属原子达到能量最低状态的机制，按Boltzmann方程计算状态向量间的转移概率，来引导搜索，从而使算法具有很好的全局搜索能力。
199X年、Dorigo、Ant Colony Optimization(蚁群算法)，模拟蚂蚁群体利用信息素来实现路径优化的机理，通过忘记路径将信息素的变化来解决离散数据的最优化(函数是离散的，约束条件也是离散的，称为组合优化问题，如TSP、0-1背包问题、生产调度问题等)。
智能优化方法的历史
1995年、Kenedy、Eberhart、Particle Swarm Optimization(粒子群优化)，模拟鸟群、渔群集体觅食迁徙中，个体与群体协调一致的机理，群过群体最优化方向、个体最优方法和惯性方向协调来实现最优化。
1999年、Linhares、Predatory Search(捕食搜索)，模拟猛兽捕食中大范围搜索(大步确定大体范围)和局部蹲守(小碎步寻优)的特点，通过设置全避搜索和局部搜索间变换的阈值，来协调两种不同的搜索方式，从而实现对全局搜索与局部搜索的兼顾。
智能优化方法的历史
2000年、Passino、Bacteria Foraging (细菌觅食算法)。模拟大肠杆菌的觅食过程。(1)寻找可能存在食物源的区域；(2)决定是否进入此区域；(3)在所选定的区域中寻找食物源；(4)消耗掉一定的量的食物后，决定是否继续在此区域寻找食物或迁移到另一个更