现代优化算法简介.pptVIP

现代优化算法简介 安徽师范大学数学计算机科学学院 优化问题概述 组合优化问题优化模型 组合优化（combinatorial optimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。 数学模型： 组合优化问题 组合优化问题的三参数表示： 经典的计算方法 传统运筹学面临新挑战 现代问题的特点 离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础 不确定性问题——随机性数学模型 半结构或非结构化的问题——计算机模拟、决 策支持系统 大规模问题——并行计算、大型分解理论、近似理论 现代优化方法 追求满意——近似解 实用性强——解决实际问题 现代优化算法的评价方法 算法复杂性 背 景 传统实际问题的特点 连续性问题——主要以微积分为基础，且问题规模较小 传统的优化方法 追求准确——精确解 理论的完美——结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等） 启发式计算方法 启发式算法_优点 优点： （1）有可能比简化数学模型解的误差小； （2）对有些难题，计算时间可接受； （3）可用于某些最优化算法（如分支定界算 法）之中的估界； （4）直观易行； （5）速度较快； （6）程序简单，易修改。 启发式算法_不足 不足： （1）不能保证求得全局最优解； （2）解的精度不稳定，有时好有时坏； （3）算法设计与问题、设计者经验、技术 有关，缺乏规律性； （4）不同算法之间难以比较。 可应用那些问题 可应用那些问题 NP问题 ………不存在多项式算法的问题,典型问题如背包问题,周游问题,选址问题等 某些高阶多项式算法问题 ……….如对应算法时间复杂度超过4阶以上,此时利用普通算法在有效时间内可能不能得到结果 那些问题不适合使用 ……..求解为精确解 …….不是优化模型问题 ……..有低阶多项式算法 当前进化算法新进展 多目标优化 动态环境下优化 大规模超大规模优化 不确定环境下优化 ……………………………….. 遗传算法 遗传算法 神经计算 神经计算 模糊逻辑 其它生物启发式计算技术 鱼群觅食模型 鸟群的飞行行为 避免碰撞 速度匹配 中心聚集 鸟群觅食模型 谢谢大家 Q/A 遗传算法的思想来源于达尔文的自然进化论和孟德尔、摩根的群体遗传学说，由美国Michigan大学的John Holland教授于1975年提出。 遗传算法的核心思想：求解问题时，将问题的求解过程视为染色体适者生存的过程，通过染色体一代一代的不断进化（包括选择、交叉、变异等操作），保留优良个体，淘汰劣质个体，最终收敛到“最适应环境”的个体，从而找到问题的最优解或满意解。 遗传算法的思想来源于达尔文的自然进化论和孟德尔、摩根的群体遗传学说，由美国Michigan大学的John Holland教授于1975年提出。 遗传算法的核心思想：求解问题时，将问题的求解过程视为染色体适者生存的过程，通过染色体一代一代的不断进化（包括选择、交叉、变异等操作），保留优良个体，淘汰劣质个体，最终收敛到“最适应环境”的个体，从而找到问题的最优解或满意解。 受生物神经系统的启发，人们提出了一种新型的非算法信息处理方法—人工神经网络。 轴突是一根长神经纤维，其主要功能是将神经冲动由胞体传至其它神经元。每个神经元只有一根轴突。 突触：神经元与神经元之间的连接点。它是神经元之间的传递信息关键性结构。可以分为两类：化学性突触和电突触。 神经元之间的信息是通过突触完成的。当神经冲动传至突触前膜时，突触中的神经递质与突触后膜上的相应受体结合，于是 后膜两侧的离子分布发生改变，呈兴奋性或抑制变化。 因为一个神经元通常有许多突触，其中有些是兴奋性的，有些是抑制性的，如果兴奋性突触活动强度总和超过抑制性突触活动强度总和，并达到一定的阈值，就能使使该神经元的轴突起始发生动作电位，产生神经冲动。出现神经冲动时则该神经元呈现兴奋，反之则表现为抑制。 神经元的每个突触的活动强度用一个固定的实数即权值模拟。 1943 年，心理学家 McCulloch 和数学家 Pitts提出的神经元二元阈值单元(Binary threshold unit)，即著名的 M-P 模型[15]。该模型的基本思想是：神经细胞的工作方式是兴奋或者是抑制。基于这个思想，McCulloch 和