优化--光彩夺目的领域--.ppt

Y. C. Ho 优化--光彩夺目的领域-- 美国哈佛大学 何毓琦 中国北京IFAC世界大会 1999年7月5日 优化 世纪可溯的历史 第一个基因算法 优化 世纪可溯的历史 人类进化的基础 文明的柱石 优化 世纪可溯的历史 人类进化的基础 文明的柱石 随着计算机的问世而成为现实 ~40年前 历史回顾 卡斯帕洛夫对“深蓝”(1997) - 人、数学、及机器智能的结合 - 历史学的目的 人类历史上发表的关于优化的论文总数 -- （大约） -- 优化概念一览 静态 相对于 动态 标量 相对于 向量 确定 相对于 随机 集中 相对于 分布 连续 相对于 离散 方位 相对于 序位 完美 相对于 满意 严格 相对于 启发 优化方法一览 迭代 相对于 解析 串行 相对于 并行 局部 相对于 全局 定量 相对于 定性 求导 相对于 有哪些信誉好的足球投注网站 确定 相对于 随机 预设 相对于 与过程有关(非自适应) (自适应) 点到点 相对于 集到集 启发 相对于 解析 举例 多目标 多人 分散 随机 动态 迭代 集到集 有哪些信誉好的足球投注网站 并行 在SIMD计算机上用基因算法求多人随机微分对策问题的数值解 简单静态优化 约束与拉氏松驰 凸优化与非凸优化 凸 = 相对最优与全局最优之间无区别 非凸 = 一切皆可能, 也许如大海捞针般困难。 已知寥寥! (待续) 凸 + 线性 线性规划的成功 动态约束 q ? [xT,...,xo, uT-1,...,uo] f(q)?0 = xt+1=f(xt, ut); xo 给定; t=0,1,2, .. . , T 短期与长期的综合考量 动态规划 将长期决策问题转换为一系列互相关联的短期决策问题 拉氏乘子服从最优控制理论中的协状态方程 信息的价值 = 有信息情况下的作为 -无信息情况下的作为 = MinqE[L(q,x)] - E[MinqL(q,x)] 对偶控制或优化: 多些信息少些优化还是相反? 多人 (2) 优化- 结盟的可能性 - 核心值 能保证个人得到什么(min我max他人) 结盟能带来什么好处(min盟友max他人) Shapley值 所有可能盟友的平均贡献 从优化的观点看对策论 非协作对策: 简化成多个关联的单人优化问题 - 每个单人最优。 协作对策:简化成全组或分组效益的优化，即， 将多目标标量化。 分布或多代理优化 简单、局部互动 = 复杂、全局行为 整体大于部分和 “浮现现象”的稳定性、最优性、平衡点问题 个体适应或整体进化行为 （待续） 组合优化 缺乏结构信息: 离散、整数、或 符号变量 巨维有哪些信誉好的足球投注网站空间: 例如 |决策空间维数||信息空间维数| ==NP-完备复杂性(非多项式-完备复杂性) 情景分析(Landscape)的概念: 性能的统计描述(匹配度)与解邻域 “情景分析” 带来的问题 试图找回“连续”和“实数变量” 多半取决于求解算法而非问题的性质 通常导致非凸分析 尚未解决优化问题的基本难点之续文 举例说明无免费午餐定理 因此, . . . 包罗万象的优化方法看来不可能 结构知识和针对问题求解绝对必要, 即有哪些信誉好的足球投注网站必须有针对性或受到指引 启发、学习、人的才智及软优化在求解方法中占有很重要的地位 自然、分析与计算智能 人 - 高层次学习和创造，如特征选择， 模式检测，模糊逻辑，新思想，等等 分析与计算 - 低层学习和处理，如非线性回归，数据挖掘，神经元-动态规划，基因算法，逻辑验证，等等 适当接口和分工 启发与 随机化有哪些信誉好的足球投注网站 令 ? = 一次随机有哪些信誉好的足球投注网站成功的概率，则N次随机有哪些信誉好的足球投注网站成功的概率 ? P = 1-(1-e)N ? N e 给定 e=0.05, N=20, P=1 若上述有哪些信誉好的足球投注网站成本不太高则值得做 = 启发式 + 随机化 = 高级启发式或超级启发式 (基因算法、模拟退火) 正如 . . . 可量化启发式 相对于 严格分析 边学边做 相对于 一步到位 自组织 相对于 集中控制 软计算 相对于 精确解 满意 相对于 寻找最优 序位分析 相对于 方位分析 增广优化 将“最好”扩展为 “满意” G - 软化目标 将G的定义模糊化 以不同方式选择G的估计，记为S 变点到点迭代到集到集迭代 序优化的优点 序位(O