广义优化课件

1、第一章 广义优化/工程优化 1-3 智能优化方法 1-1 广义优化概念 1-2 工程优化设计1-1 广义优化概念优化分析设计方法 广义优化(包括优化对象、优化范围和优化准则)是现代设计的宗旨 优化设计是把最优化数学原理应用于工程设计问题，在众多的设计方案中寻到尽可能完善的或最适宜的设计方案的一种现代设计方法。优化设计为工程设计提供了一种重要的科学设计方法，采用优化设计方法能大大提高设计效率和设计质量。 优化是合理化、科学化、满意化，是一个系统分析、系统综合、系统检验的反复交叉过程，是一个永无止境的过程。在优化设计过程中，常常需要根据产品设计的要求，合理确定各种参数，以期达到最佳的设计目标。优化

2、分析设计方法有：优化设计法、广义优化设计法、方案优化法、图论及网络优化、离散优化、交叉优化、模糊优化等。 优化设计的发展阶段：人类智能优化：凭人类直觉或逻辑思维功能，不一定建立数学模型，无严格数学背景。如：“设计-评价-再设计”法，黄金分割法、穷举法、瞎子爬山法等直接寻优法。数学规划方法优化：工程优化：不放映广义优化目前，优化设计领域已从数学规划阶段进入 了工程优化和人工智能优化阶段。机械产品广义优化是面向产品全系统、全过程和全性能的优化设计，是以数值与非数值集成优化、人机合成优化和多计算机协同优化为主要特征的优化设计，是从优化全过程上研究如何提高优化效率与效果的优化设计。全系统优化 现代机械

3、产品的系统性、综合性和规模化导致设计模型的横向扩展。把研究对象由传统优化的简单零部件扩展到复杂零部件、整机、系列产品和组合产品的整体优化，由单学科领域的优化发展到机、液、光、电、信息的集成优化。统称为。全性能优化 客户要求的多样化导致基于全性能的多目标优化。把优化准则由传统优化的单方面性能优化扩展到技术性、经济性和社会性的综合评估和优化。技术上追求实现目的性能、约束性能、使用性能和结构性能的综合优化；结构上追求静态性能和动态性能的组合优化。称为。全设计过程优化 对产品寿命周期优化的市场需求导致设计模型的纵向扩展。把优化范围由传统优化的产品技术设计阶段的优化扩展到包含功能、原理方案和参数、结构方

4、案、参数和形状，以及工艺和公差优化的全设计过程，进而面向制造、经销、使用和用后处置的寿命周期设计过程。全寿命周期优化优化适应性/模式/手段的拓展(融入新技术)：优化适应性：数值优化数值与非数值综合人工智能/计算机技术搜索策略：以数学规划为主模型：数值型搜索策略：数学工具、人工智能等模型：数值与非数值方法集成建模优化模式：计算机自动优化人机一体优化可视化/多媒体/虚拟现实技术优化手段：单模型单机串行优化分解模型分配任务多机分布式并行协同优化多机协同优化计算机技术/网络通信技术单机优化广义优化与传统优化特征体系间的比较优化设计进程传统设计广义设计结构方案已经确定1-2 工程优化设计一、总论1、现代

5、工程优化设计研究方向 现代工程优化设计理论和方法 支持工程优化设计的集成平台 优化设计的工程应用2、现代工程优化设计目标 着重解决：大型、复杂产品 (工程) 全系统、全性能、全过程、全生命周期的优化问题大规模的组合优化设计问题大构件的结构优化、拓朴优化问题大型复杂机械系统方案优化问题复杂机械系统动态设计的优化问题复杂工程系统的优化布局问题复杂工程系统的优化调度问题大型、复杂机械产品的稳健设计问题追求更好而不是追求最好3、工程优化设计的范畴 工程优化设计技术过程的优化设计技术产品的优化设计电子系统的优化设计机械系统的优化设计机械零件优化设计机械部件优化设计优化调度和管理4、发展概况和存在的问题

6、现状：优化方法取得了较多的成果仍以数学规划方法为主零部件的优化设计已在实际设计中得到应用处理复杂系统的广义优化设计、多学科协同优化设计、智能优化设计等的研究，取得了较多的研究成果理论研究还有待深入建模技术的研究还很不充分结果分析及评价的研究还相对落后复杂系统“全系统、全性能、全过程”优化设计的研究才刚刚开始对于大型、复杂和难解问题仍有许多问题有待进一步研究 优化设计和CAD技术的结合还有待进一步研究 存在的主要问题：发展概况经验型的优化设计(人工判断寻优) 基于数学规划的优化方法 (线性规划、非线性规划、动态规划 )人工智能优化 广义优化设计和多学科协同优化设计基于进化机制的优化设计 协同寻优

7、理论与方法组合优化设计的理论与方法结构优化、拓朴优化的理论与方法系统方案优化的理论与方法系统动态设计优化的理论与方法复杂工程系统的优化布局的理论与方法复杂工程系统的优化调度问题的理论与方法机械产品稳健设计问题的理论与方法建模理论与方法寻优求解算法优化过程和优化结果的可视化和分析评价二、现代工程优化设计理论和方法现代优化理论和方法的研究重点仿生演化设计理论与方法多学科协同优化设计理论与方法结构优化、拓朴优化设计理论与方法工程优化设计建模理论与方法寻优求解算法与求解过程控制优化结果智能处理与评价仿生演化设计理论与方法仿生演化设计理论和方法 面向设计全过程的仿生演化设计支持的是创新性的优化设计 面向

8、全过程的仿生演化设计是研究生物在进化过程中的寻优机制，是探讨特征空间中的寻优方法，是真正意义上的全过程设计，即带有迭代反馈的过程优化设计 仿生演化设计强调问题本身的动态变化，是针对两种空间共同进化而提出的设计方法学 研究仿生演化设计的机理及其对产品设计创新性的支持 按生物进化的机理和寻优机制，探讨特征空间中的寻优方法 根据问题本身的动态性，探讨问题空间和解空间的共同进化及相应的设计方法学 仿生演化设计理论和方法研究重点 对产品设计的问题空间和解空间的耦合关系进行描述和衡量，形成这种描述的表示方式，并建立与此相匹配的演化模型，这是仿生演化设计的基础 借鉴生物进化特征，探讨特征空间中演化设计的基本

9、原理。 问题的描述空间和解空间的产生是交互式的进化过程，在此过程中，有可能产生“突现”，这与生物的某些特征非常类似。因此，探讨描述这种现象的本质，揭示了这些“突现”行为的机理，以把握创新设计的实质，是研究的重点之一 模仿生物进化的趋优机制，研究设计对象在问题空间和解空间都变化的情况下的寻优策略，建立相应的形式化描述模型和求解算法，并运用于产品包括概念设计的全过程演化设计问题。 研究粗集理论在概念设计阶段的应用，来处理不完整数据和不精确、不确定性问题。由于现代产品和制造系统的复杂性，各种传统的优化方法往往无能为力。迄今所采用 的各种优化方法都是在数量空间中进行的，而产品及其制造系统的优化却往往需

10、要在特征空间（或语义空间）中进行。须摹仿生物进化过程中的自组织机制，研究特征空间中的寻优策略，及其在设计优化和工艺优化中的应用。需要解决的关键问题如下：生物在进化过程中的寻优机制，抵御“组合爆炸”和防止陷入“局部最优”的策略，及其在产品优化与工艺优化中的应用。特征空间中的寻优方法与基因（GA）算法。基于进化机制的优化设计多学科协同优化设计理论与方法 将复杂系统按其所涉及的不同性能、设计阶段的不同过程、设计对象的不同子结构进行划分，称每一部分为一个领域，交由熟悉该领域的专家进行处理，即进行任务分配； 各领域可以在不需要知道其它领域属性的情况下，选择该领域的处理方法和求解工具，可在不同的处理机上或

11、异地进行求解； 由于各领域之间往往存在相互耦合的关系（通常耦合关系主要有变量耦合和函数耦合），这些关系的存在常导致各领域求解过程出现混乱现象，因此，需要构造一个协同模块，对耦合进行协同处理。多学科协同优化设计(广义优化设计)全系统、全性能、全过程、全生命周期的优化设计国家研究机构研究对象与成果英国Sheffield大学进化计算；使MDO应用同现存工业结构相协调Durham大学发展模仿骨骼生成来进行结构优化的MDO方法Southampton大学在涡轮叶片和低振动人造卫星结构设计等方面进行MDO方法研究Synaps,DASA和Airbus利用MDO技术改善飞行器机翼的形状设计U.K. Defenc

12、e Evaluation and research Agency利用MDO技术进行飞行器机翼和机体的综合设计法国Ecole Tech 大学开发不确定性、可制造性及成本等方面综合MDO方法Pierre et Marie Curie 大学汽车防撞性MDO应用Nice 大学利用图象处理技术在拓扑优化方面取得显著成果多学科协同优化设计国内外研究概况国家研究机构研究对象与成果德国Siegen 大学MDO的研究用于亚毫米级望远镜及铁路运输工具Braunschweig大学MDO应用于裂缝及裂纹识别、质量控制、结构可靠性监控等方面Stuttgart大学开发用于自适应结构设计的MDO方法澳大利亚Sydney大学

13、开发薄壁及冷色结构的MDO软件葡萄牙Porto大学预制梁方面的MDO方法瑞典Saab Ericsson 空间中心设计初期和设计后期MDO软件的成功应用国家研究机构研究对象与成果波兰科学研究院MDO用于发展仿生机制，探讨骨头内部结构及外部特征，并应用于骨植入技术印度科学研究院进化优化方法，并应用于VLSI芯片设计日本Osaka Prefecture大学卡车架脉冲分配器手柄MDO方法的应用Toronto 大学开发用于焊接单元优化的专家系统Laval 大学利用MDO设计飞机样机静平衡运动系统印度尼西亚Teknologi Bandung研究院利用MDO技术设计高级水泥材料，其成果应用于Dassault

14、 Aviation、Renault等公司中国大连理工大学声结构耦合设计优化国家研究机构研究对象与成果美国Boeing公司描述诸如行为、性能、人机因素、可靠性和系统成本等多样性、多目标MDO公理化方法；其防撞性工业软件的成功实施带来可观经济效益；开发出带有起博器的双向通讯天线Altair工程公司OptiStruct软件成功用于带有制造工艺约束的拓扑优化Northeastern大学开发可执行程序和可视化方法以支持设计决策Arizona大学探讨利用MDO进行敏捷型复合机翼的设计方法，用于改善颤动特性、气流响应和其它性能Virginia Tech和Florida大学应用MDO开发支柱撑杆结构机翼的超音

15、速飞机，与传统悬臂梁结构机翼飞机相比，能节省近20%燃料Iowa大学开发出MDO设计过程程序并融入机械多体动力学ADAMS软件Georgia Tech空间飞行器及火箭概念设计阶段的MDO方法；并联合Lockheed Martin Tactical 飞行器系统及空军武器实验室进行MDO不同设计阶段的不确定性建模芝加哥Illinois大学将MDO研究与3D沉浸式虚拟现实技术结合，改观设计输入、输出信息的界面；其MDO方法对诸如快速成型、铸造、焊接、聚合体挤压与注入模具等制造工艺影响很大国家研究机构研究对象与成果美国Buffalo大学研究产品及设计空间可视MDO方法，以支持设计决策Rice大学,Bo

16、eing和Mobil Oil公司它们在近似模型方面进行合作研究，以加强不同学科的计算机仿真技术Pennsylvania大学开发自适应机构拓扑优化的MDO方法，并用于微电子机械系统Ohio州立大学获得能够解决非连续性约束和大系统优化问题的鲁棒性算法专利Sandia国家实验室对存储设计问题进行并行优化NASA-Langley实验室将MDO的基本知识应用于工程问题；从系统和心理行为角度检验机组的动力特征空军工业研究院及其智能中心开发GA算法用以从不完整信息反求导弹武器系统结构结构优化、拓朴优化设计理论和方法结构优化、拓朴优化设计理论和方法 结构优化问题已经涉及到结构设计的各个方面 ,除了结构的最小重

17、量、最大性能以及形状与拓扑优化、结构元件的优化布置与定位等传统结构优化问题以外 ,还涉及到结构美学、微观力学中的分子结构优化等问题 结构优化问题在数学上归结为带约束的函数优化问题 ,大型结构的整体优化问题一般具有多目标、多约束和多混合变量的特点最小重量与最大性能设计 最小重量与最大性能设计是结构优化设计的经典问题 ,前者要求在结构安全和完整性的条件下使结构的重量(或体积 , 或费用)最小, 后者要求在结构重量或其它条件的限制下使结构的性能(如刚度等)最大 .这类问题一般可归结于几何不变的单一目标的多变量约束优化问题 ,利用传统的优化准则和数学规划法可有效地进行求解 例如珩架的最小重量设计;较多

18、的研究集中于复合材料梁和板结构的刚度或阻尼性能的优化设计 结构的尺寸、形状和拓扑优化是几何设计的三个层次 ,通称为布局 (Layout)优化问题 .其中尺寸与形状优化问题可以用数学规划法求解 .优化拓扑的选择是一个困难的结构优化问题 :设计变量很多 ,几何构型的变化导致病态的有限元方程等 .在结构拓扑优化问题中 ,可以根据所取目标函数和约束条件的不同组合 ,演义出不同的拓扑优化问题:目标函数为结构柔度 ,约束条件为材料重量 ;目标函数为结构频率 ,约束条件为材料重量 ;目标函数为材料重量 ,约束条件为结构柔度 ;目标函数为指定点位移 ,约束条件为材料重量等结构形状与拓扑优化 在大型空间结构的控

19、制问题中 ,需要安装大量的传感器和驱动器 ,以实现对结构的现场性能监测和主动控制 .为了不增加结构的重量 ,提高主动控制系统的结构性能 ,必须使系统具有良好的鲁棒稳定性 .如果驱动器 /传感器的位置是空间离散的 ,则优化布置问题就转化为组合优化问题 .其目标函数一般有: f1: 结构的重量最小; f2:二次性能指标最小; f3:二次控制的费力最小; f4:鲁棒稳定性最大; f5:耗散能量最大 .设计变量一般取为驱动器的位置和结构元件的体积 。 类似的问题还有智能结构中的压电驱动器或阻尼器的定位和优化布置问题 ;灵巧材料中的噪声控制问题 ;弹性结构中的损伤识别与定位问题等结构元件的优化布置与定位

20、问题 由于结构的外形设计成为越来越重要的设计条件,结构的美学设计也成为结构优化问题的研究焦点。从美学的观点评价结构的造型、色彩等视觉效果和与周围环境的协调性,是结构美学设计的主要内容。但是,这些美学指标往往受设计者自身的美学观点和偏好的影响 ,所以建立一套客观的结构美学评价体系并非易事。有文献在对大坝上下游两侧的颜色进行优化设计时,引入了反映每个设计者偏好的评价矩阵,通过对视觉偏差的统计分布假设,得到一种可靠的美学效果估计值。结构的美学设计 结构的共振调谐与动力学平衡问题经常导致病态的优化问题,共振极限状态的分析将导致求解非线性优化问题。其目标函数有可能是离散的、非凸的、多模态或平坦形状(fl

21、at in shape),被认为是求解这类非线性问题的非常有前途的工具。的可能应用领域是有应力和位移约束的多工况频率约束问题和振动控制智能结构的频率优化问题结构动力学性能设计工程优化设计中的建模理论与方法直接建模柔性建模自适应建模建模类型根据优化算法的需要，并按其规定格式，将设计问题的参数和函数直接表达为优化数学模型。特定优化对象在事先编好拓朴结构描述子程序的情况下，实现设计参数、设计函数在线交互式灵活修改。在求解过程中，自动修改和完善优化数学模型，使问题空间和解空间同步变化。根据以往优化设计的经验，建立不同系列、整机及零部件优化模型，需要时选择调用并组合。建立一个能充分表达设计思想的过渡模型

22、（非数学模型，如描述设计问题的物理产品模型及符号模型等），然后，系统自动将其转化为相应算法所需的最终优化设计模型。过渡建模利用模型库建模柔性建模的功能是让设计师交互地确定优化模型中的三大部分-设计参数、约束数和目标函数的属性。编辑设计参数属性编辑不等距离散设计参数取值域编辑价值函数曲线编辑约束函数权重结构编辑目标函数权重结构编辑设计函数属性柔性建模建立图形模型图形建模模块的功能是让设计师实现同一产品的设计图形和优化数学模型的双向驱动。进行优化搜索由设计方案确定图形形状图形的交互修改图形建模领域建模结构优化建模拓朴优化建模动力学优化建模其它领域设计建模辅助建模工具 要解决机械优化设计存在的问题，

23、其中之一是需要用计算机辅助建立优化数学模型和计算机辅助优化方法程序选择，完成这些工作需要有建模专家系统、模型库管理系统、优化方法程序评价系统和优化方法程序库。 这几个系统独立运行还不能很好地满足要求,最好的情况是将它们协调组合，集成为一个优化设计智能建模系统，使之成为智能CAD/CAM的重要资源 建立辅助建模工具的必要性国外几种智能建模系统及其特点 OMBMS是模型库管理系统；MB是模型库；OBMES是建模专家系统；MAR是模型分析器；OGRAP是求解过程的图形显示模块；OPB是优化方法程序库；OPEVS是优化方法程序的测试与评价系统 一种智能建模系统的总体结构寻优求解算法与求解过程控制线性规

24、划线性规划和非线性规划的典型算法非线性规划 非光滑优化方法 基本算法:单纯形法具有多项式时间复杂度算法(内点法)： 投影算法、均衡仿射尺度法、对偶均衡仿射尺度法、原对偶算法、探测矫正算法、原对偶势函数算法等无约束非线性规划算法 :计算梯度的DFP法、BFGS法；不计算梯度的Powell共轭梯度法等约束非线性规划算法：序列线性逼近方法、序列无约束极小化方法、二次逼近方法等 针对特殊问题设计的算法 针对复合非光滑优化问题的信赖域方法 针对极大极小问题的极大熵方法 求解一般非光滑问题的算法 次梯度法、捆集法 非光滑优化方法前处理法：主要有评价理论算法和目的规划算法。直观、简单，但带有一定的盲目性;

25、后处理法(后置衔接法)：通过求得其全部或一部分有效解、然后由决策者选出合适的有效解作为最优解 ; 渐进衔接法(交互式算法)：构造出评价标准的单目标问题，求出这一单目标问题的最优解，再提交决策者评判。实际上是一个将多目标问题转化为一系列单目标问题求解的过程。多目标问题的求解策略 人工智能两大分支：知识工程 计算智能 基于人工智能的优化设计问题的求解策略基于符号知识的推理技术(专家系统)、基于实例的推理技术等在优化设计中，有关方案优化设计问题，可通过人工智能、专家系统等求解人工神经网络算法遗传基因算法模拟退火算法蚂蚁算法等是一个带有智能的计算系统，具有高速、并行处理、高效的知识获取、自学习、自适应

26、等能力 可处理各种优化设计的问题，通过启发式的随机搜索，可以获得全局最优解，基因算法采用并行计算，多解并存，求解效率很高。可视化处理方法主要有：事后处理法：把计算和计算结果可视法分成两个阶段，两者不发生交互作用。跟踪处理法：要求实时显示中间结果，以便于监视当前情况，确定是否继续当前计算或开始一个新的计算。驾驭处理法：不仅能使研究者实时地观察到当前的计算状态，而且能对计算过程进行实时的交互控制(增大或减少步长，修改参数等)；可视化过程步骤：计算数据采集、组织与变换；几何图元提取和可视模型构造；图形绘制与显示。 求解过程的可视化跟踪优化结果智能处理与评价目的：分析优化结果的合理性和可靠性，从而判断

27、模型的正确性，给出修改的信息，以便进一步完善所建立的模型 定义：在某点处，设计变量或起作用约束的微小变化所引起的设计函数(目标函数或约束函数)的变化程度 用灵敏度判断结果的合理性 用灵敏度判断结果的可靠性 敏度分析通过三维图形，显示最优点处目标函数的性态；通过三维图形，显示目标函数与设计变量间的空间关系；通过三维图形，显示各约束函数与设计变量间的空间关系；通过三维图形，显示设计方案的实体结构、动态仿真：根据优化设计所得参数，生成设计对象的实体结构并进行动态仿真。 优化结果图形显示评价指标 目标函数值的大小 不稳定度的大小 可靠度的大小评价方法 层次方法评价 模糊数学评价 人工智能、专家系统评价

28、 评价决策三、支持工程优化设计的集成平台集成平台的功能需求集成平台开发的关键技术集成平台的体系结构设计过程数据管理产品模型 优化设计拓朴优化参数优化结构优化分析常规分析有限元分析应力分析动力学分析数据库实体造型二维三维 算法库 图形库集成平台示例机械零部件的参数优化设计大型、复杂产品（工程）全系统、全性能、全过程、全生命周期的优化设计大构件的结构优化和拓朴优化设计大型复杂机械系统的方案优化设计复杂机械系统动态设计的优化复杂工程系统的优化布局生产过程的优化调度大型、复杂机械产品的稳健优化设计7机械优化设计建模与优化方法评价（国家自然科学基金和中国科学院计算所CAD开放实验室资助课题）耀青 黄心渊

29、 王文清等1995年10月第1版四、优化设计的工程应用五、工程优化设计研究方向优化设计方法学：优化设计哲理/优化设计的体系/优化设计进程/优化设计的本质及其内在规律优化设计的设计对象：概念设计中的优化设计问题/组合优化中的NP问题/复杂大系统工程优化设计中的多学科协同优化设计问题/结构(形状、拓朴)优化设计问题/动态设计中的优化设计问题优化设计的策略、理论和方法：优化设计中建模理论和方法/优化设计中的灵敏度分析/优化设计中的可控可视技术/优化算法优化设计支持工具：单元工具(建模工具、算法库、模型库、数据库及其管理系统)/集成工具智能算法导言遗传算法 (GA)禁忌搜索(TS)模拟退火(SA)人工

30、神经网络在优化中的应用(ANN)1-3 智能优化方法智能算法导言一、传统优化方法的基本步骤：. 选初始解 2. 停止准则 LP: 检验数为正; NLP: f ( x ) = 0 | f ( x )| | 2 f ( x ) 03. 向改进点移动 LP: 转轴变换; NLP: 选一个移动方向: 负梯度方向，牛顿方向，共轭梯度方向 确定移动步长: 线性搜索，黄金分割,二、传统优化方法特点与缺陷：1. 一个初始点运算只对一个点进行;2. 向改进方向移动不能跳出局部最优解;3. 只有在凸集凸函数条件下才能找到全局最优解;4. 模型必须是连续可微，甚至是二阶可微。三、实际对新优化方法的要求：1. 实际中

31、希望模型的描述方法更宽松2. 计算效率3. 不一定要找最优解4. 希望方法能模糊四、智能优化方法的产生与发展：1. 1975年Holland提出GA 随机实验法模拟生物遗传机制 一点多点(种群)遗传可并行计算2. 1977年Glover提出Tabu Search 禁忌搜索有记忆功能 用TABU表封锁搜索过的区域3. 1983年Kirkpatrick提出成熟的模拟退火方法 模拟物理的退火过程 目标能量函数，在退火过程中达到最小4. 80年代重新兴起的ANN，用于优化遗传算法(Genetic Algorithm)一、导言1. 遗传算法的产生 1975年Holland提出, 第一本书: “Adapt

32、ation in Natural and Artificial Systems” GA以前的工作: 随机算法随机产生点,迭代,无遗传机制。 网格试验法不断细化网格，找最优解。 可变容量法(单纯形法则)每次替换掉一个最差点。2. 遗传学的基本思想 优胜劣汰，子代继承父代的特征 定向育种产生一个大的种群; 根据需要的特征选种; 用选出的种子繁殖下一代； 经过若干代后得到具有以上特征的品种。3. 遗传算法的基本要素与构成 基本思想: 根据问题的目标确定一个适应度函数，按适应度函数的好坏对种群进行选择，繁殖，经若干代后，获得最好的种群和个体。 要素: 种群大小; 基因表达方式;选择策略; 遗传算子;停

33、止准则。 流程:二、Holland的最初的遗传算法1. 种群大小 N: 每代中个体的个数； 一般来说，越大越好。2. 基因表达方式 用二进制串表达 精度 1/2n 1; 1 - 06. 停止准则 达到最大代数停止。计算实例: max f ( x ) = x3 60 x2 + 900 x +100 f ( x ) = 3x2 120 x +900 = 0 X1 = 30, X2 =10 min f(x) = 100 max f(x) = 4100用5位二进制表达(0 32) j 编码 x F(x) Pj 1 10011 19 2399 0.206 2 00101 5 3255 0.227 3 1

34、1010 26 516 0.044 4 10101 21 1801 0.155 5 01110 14 3684 0.317 F = 2325 P1 0 1 0 1 0 P1 0 1 1 1 0 P2 1 1 0 1 0 P2 1 1 1 1 0j P1 P2 交叉点 变异 子串 F ( x ) 1 1 2 4 N 10011 23992 5 3 2 N 01010 4100 *3 5 2 3 N 01101 38574 4 2 1 N 10101 18015 2 5 4 N 00100 2804 F = 2992一次遗传:三、应用举例-机器布置问题1. 描述 n 台机器要布置在n个位置，机器i

35、, j 间物流为fij。运价Cij，位置i, j间距离为dij。问:如何布置?2. 一般0-1规划 1 机器i 放在位置j 0 else xij = 可用二次0-1规划求解3. 把问题变为排序问题 位置: 1 2 n 机器: 3 4 1 P( i ) = j 表示机器i 排在位置j 上 4. GA求解 适应度函数: F( x ) = kylny四、几点体会1. 分散性与收敛性一对矛盾 分散性避免局部最优; 收敛性加快计算速度，提高最优率 希望: 开始分散，最后收敛快2. 收敛理论上无重大突破待解决禁忌搜索(Tabu Search)一、导言1. 禁忌搜索的产生 1977年F.Glover提出，主

36、要用于组合优化 特点：计算速度快，可解大型问题2. 主要思想 避免算法在局部循环 只进不退的原则：用Tabu锁住退路； 不以局部最优为停止条件； 模仿了人的记忆功能Tabu表，频数表 二、禁忌搜索的基本概念1. 问题描述 minC( x ) s. t. xXRn X是Rn上的一个离散空间; 定义：对于一个变量x ，通过一步移动s 达到的点的集合，称为邻域移动， S( x ) = s( x ) | x X2. 禁忌表(Tabu list) T 阻止搜索过程循环，记录前若干次的移动，禁止这些移动在近期返回； T表: 1 前一次移动 2 前二次移动 3 Tabu size 4 5 3. 渴望水平函数

37、/破禁水平(Aspiration level function) 若A(x,s)C(s(x) , 则s(x)不受Tabu表的限制，即sT ，仍可取: xk+1=s(x)4. 移动规则 若sk(x)=sOpt(s), xS(x)T , 令x = sk(x) 即在不被禁忌的邻域中挑最优移动.5. 选择规则 若C( x ) NG, stop; Step3. 若sk(x)=Opts(x),sS(x)T, 令x=sk(x); Step4. 若C(sL(x)A(s,x),且sLT, 令A(x, s)=C( sL(x), x=sL(x); Step5. 若C(x)作为能量函数，模拟温度T缓慢下降, 按Bol

38、tzman方程计算分布概率；当温度达到最低，能量函数达最低=目标函数达到最低。二、退火过程和Boltzman方程1. 热力学的退火过程 设热力学系统S，有N个状态，状态i 的能量为Ei，在温度Tk下经过一段时间达到热平衡，这时处在状态i 的概率为 Pi(Tk)=Ckexp(Ei /Tk)2. Boltzman方程 Ei,Pi Tk, (Tk);Tk0, min三、模拟退火算法1. 模拟要求: 初始温度足够高转移总能成功; 降温过程足够慢某温度下迭代次数足够多; 终止温度足够低不可能转到差状态。2. SA算法: 问题: minf(i), iS , S-离散状态空间 算法步骤: Step1: 初始

39、化 任选一初始解 iS ; 给定初始温度T0和终止温度Tf ； 令迭代指标k = 0，Tk= T0 Step2: 随机产生一个邻域解j, f = f (j) f (i) ;Step3: 若,则 i=j / fStep4:若达到热平衡(内循环次数达n(Tk), 转Step5,否则转Step2.Step5: k=k+1, Tk= Tk+ T , 或Tk= Tk r (r1 ) 若Tk0, exp(-f /Tk)=0.80158 i=j 3. (2)(3): j=4-2-3-1, f(j)=132 , f 0, exp(-f /Tk)=0.878 i=jTk= 80 1. (3)(4): j=4-2

40、-1-3, f(j)=135 , 2. (2)(4): j=4-3-1-2, f(j)=109 ,Tk= 60 i=3-1-4-2, f(i)=92五、SA的收敛性 模拟退火算法是一种具有一定随机性的启发式算法，它可以向目标函数增加的方向转移，从而逃出局部最优解。 M.Geman和Geman已从理论上证明，当搜索次数足够多时，模拟退火法将以概率1达到全局最优解。六、几点体会1. Tk大时, exp(-f /Tk)大, 转移概率高, 分散性好; Tk小时，收敛性好。2. 仅是理论上可保证最优。3. 控制好Tk，可取得较好的收敛性和分散性。人工神经网络(ANN)在优化中的应用一、导言1. ANN的产生*Von Neuman机：集中式, 速度快, 精度高, 寻址记忆; 非模糊量; 耗能大, 推理能力差串行处理;*人脑：分布式, 速度慢, 精度低, 联想记忆; 可处理模糊量; 耗能低, 推理能力强可并行。 Von Neuman曾提出设计并