遗传算法模拟退火技术介绍.ppt

文档介绍：现代优化算法
教师: 刘勇
电话:**********
电子邮箱:******@cqupt.
课件下载地址:./?id=liuyong
现代优化算法
什么是优化?就是从各种方案中选取一个最好的。从数学角度看,优化理论就是研究如何在状态空间中寻找到全局最优点。
比如水泥混凝土的性能,涉及到水、沙、石子、水泥和其他掺杂物比例。学校课程表排课问题、售票员上岗问题、公司内部人员安排出效益等。降低成本、提高效益是问题的关键。
一般的优化具有下面形式:
minf (x1, x2, …, xn) . g(x)  0,xD
其中x1, x2, …, xnΩ(即问题的可行域,代表问题参数的选择范围),即minf (X),其中XΩ(矢量形式)。f(x)是决策问题的数学模型,也是决策问题的目标函数,g(x) 0是决策问题的约束条件,D是决策问题的定义域(可行域)。问题归结为求极值。极值点非常多,需要找到全局最小点。
注:求问题的最大和最小是同一个问题,算法完全一样。<br****惯上,将优化算法分为两类:局部优化算法和全局性优化算法。前者可以称为经典优化算法,已经得到了人们广泛深入的研究。线性规划、整数规划、0–1规划、非线性规划、排队论、决策论。后者****惯上称为现代优化算法,是20世纪80年代兴起的新型全局性优化算法,主要包括禁忌搜索、模拟退火、遗传算法、神经网络等,其主要应用对象是优化问题中的难解问题,即NP–hard问题
算法比喻
为了找出地球上最高的山,一群有志气的兔子们开始想办法。
方案一:兔子们吃了失忆药片,并被发射到太空,然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是,如果你过几年就杀死一部分海拔低的兔子,多产的兔子们自己就会找到珠穆朗玛峰。
遗传算法
方案二:兔子们朝着比现在高的地方跳去,它们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。其实,它们这种做法只是自己心理上认为找到了最高的山,并不能保证局部最优值就是全局最优值。
局部搜索法
一遗传算法
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。
它最早由美国密执安大学的Holland教授提出,起源于60年代对自然和人工自适应系统的研究。70年代De. Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上。80年代由Goldberg进行总结,形成了遗传算法的基本框架。