问题的数学模型与算法.ppt

《问题的数学模型与算法.ppt》由会员分享，可在线阅读，更多相关《问题的数学模型与算法.ppt（117页珍藏版）》请在三一办公上搜索。

1、2023/8/29,湘潭大学信息工程学院,研究生课程：问题的数学模型与方法(2011年上学期),授课：黎自强(教授),2023/8/29,湘潭大学信息工程学院,主要内容：1.目标函数优化问题 1.1 遗传算法求解复杂布局问题 1.2 拉格郎日算子求解圆柱体碰撞检测问题2.偏微分方程数值求解 2.1 铸件凝固过程的温度场模拟,2023/8/29,湘潭大学信息工程学院,1.目标函数优化问题,1.1.1 工程背景和科学问题的提出 1.1.2 布局优化问题研究进展 1.1.3 航天器布局方案设计研究进展 1.1.4 用遗传算法求解布局问题,1.1 复杂布局问题,2023/8/29,湘潭大学信息工程学院

2、,1.1.1 工程背景和科学问题的提出,a)发达国家航天器发展现状 美国与欧洲空间局自80年代起，致力于用计算机技术解决航天器舱的待布物总体布局问题的研究，其关键理论、方法、技术至今仍处于保密状态。近年来有用协同优化法设计航天器的保护装置和得到NASA资助的用遗传算法进行航天器的设计，但很少涉及布局设计的内容。根据我国人员出国考察获悉，以卫星布局设计为例，目前美国设计效率比我国快20倍以上，但是其性能和空间利用率对比不详。,2023/8/29,湘潭大学信息工程学院,b)国内航天器发展现状 我国航天器设计多以人工设计为主，参考样图或资料，用计算机辅助绘图（二、三维），然后用国外软件进行三维造型模

3、装，再用国外软件进行三维动力学验算。若不合适，用人工修改设计，最后建造1:1实物模型，进行实验验证。,2023/8/29,湘潭大学信息工程学院,c)人工设计存在的问题：性能不易保证或非优化；空间利用率低；设计成本高；设计周期长。过去卫星曾因总体布局不当，动不平衡过大，曾造成过早报废的恶果。况且我国还要研制更复杂的空间站，其布局设计尤为重要。,2023/8/29,湘潭大学信息工程学院,d)科学问题的提出 从理论上说，航天器布局设计，可归结出“可数学模型化”和“不可或难数学模型化”两类问题。前者属很难的带性能约束的三维布局优化问题；后者多属工程复杂系统问题，涉及人脑思维模型问题，解决方法有二种：一

4、是人工智能，基于智能的知识模型及其推理；二是人机结合(Man-Machine Synergy)或人机合作(Human-Computer Cooperation)。航天器布局设计属交叉学科前沿课题的基础理论和应用基础研究，具有重要的科学意义。,2023/8/29,湘潭大学信息工程学院,1.1.2 布局优化问题研究进展,布局问题(Layout Problem)属于复杂的组合优化问题，即使最简单的一维布局也属于NPC问题。自1831年高斯(Gauss)研究布局问题开始，虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法。从理论上讲，布局问题可分为切段(Cutting-Stock)问题和装

5、填(Packing)问题。,2023/8/29,湘潭大学信息工程学院,按照布局物体的布局维数分类,a)一维布局问题 b)二维布局问题 c)三维布局问题,2023/8/29,湘潭大学信息工程学院,a)一维布局问题,一维布局问题中典型的例子是在给定长度的棒料上，切割长度不等的若干短棒，此类问题通常称为切段问题(Cutting-Stock Problem)。解决方法：Faggioli 5利用启发式算法提出了切段排序问题的数学模型和一个三步解法；Vasko 6和Nitsche 7 分别利用树搜索算法和松弛算法来解决一维切段问题；Petridis Vassilios等8利用遗传算法以动态的方式把问题的约

6、束合并到适应度函数中。,2023/8/29,湘潭大学信息工程学院,b)二维布局问题,二维布局问题包括：一刀切问题 将某些不同大小的小矩形按照一刀切的原则排放在一个大矩形板材上，使面积浪费最小，这是剪床落料、玻璃切割、纸张切割中遇到的主要问题。所谓一刀切，是指切割总是从矩形板材的一边开始一直切到其对边，即每切一刀都将一个矩形分割成两个小矩形 底盘装载问题 底盘装载问题来源于运输、搬运中的货物摆放或装箱。将多个相同大小的立体箱子放入一立方体容器中，且要求放入的箱子越多越好。,2023/8/29,湘潭大学信息工程学院,矩形布局问题(Rectangle Packing Problems)矩形布局问题是

7、将许多大小不同的二维矩形布置在一个大的矩形中，使面积覆盖率最大，这是大规模集成电路设计中所碰到的主要问题。圆布局问题(Circle Packing Problems)圆布局问题是将许多大小相同或不同的圆布置在一个大的圆形、三角形或矩形容器中，使面积覆盖率最大39。这类问题大量地存在于几何、化学、生物学、工程和优化中，已经引起人们的很大关注40。通常不等圆装填问题还需满足一定的性能约束条件，譬如：惯性、平衡性、和稳定性约束等，我们把这种问题称为带性能约束的不等圆装填问题。,2023/8/29,湘潭大学信息工程学院,二维不规则图形布局问题(2-D Irregular Graph Layout Pr

8、oblems)二维不规则图形布局问题是指将许多任意形状、大小的二维形体布置在一任意形状的二维平面内以使某一性能最优，如板材下料，服装裁剪等。处理这类问题通常是把不规则图形套排在一些形状比较规则的简单图形中，然后用这些简单的图形在给定的平面内排样，以降低问题的复杂程度。,2023/8/29,湘潭大学信息工程学院,三维布局问题,三维布局问题包括：无性能约束的三维布局问题(3-D Layout Problems with Non-Behavioral Constraints)无性能约束三维布局问题是指将尽量多的不同形状、尺寸的三维物体放入到一长方体（或圆柱体）容器中，例如背包问题、集装箱问题。带性能

9、约束的三维布局问题(3-D Layout Problems with Behavioral Constraints)。带性能约束三维布局问题是指将任意形状、大小和性能的三维实体摆放在一个任意形状、大小的三维容器中，以满足某些约束或使某些目标最优,2023/8/29,湘潭大学信息工程学院,例子,约束底盘装载和船舶配载问题 汽车驾驶舱布局问题 集成电路(VLSI)的布局规划 航天器舱布局方案设计问题,2023/8/29,湘潭大学信息工程学院,带性能约束布局问题的算法,启发式算法(Heuristic Algorithm)拟物拟人法 拟实验综合启发式算法 八叉树结构与定位定序函数相结合的启发式算法 G

10、ENET模型 Montreuil模型 膨胀算法,2023/8/29,湘潭大学信息工程学院,图论法(Graph Theory)图论作为组合数学的重要组成部分，在许多领域有着广泛的应用。该方法一般将带性能约束布局问题分两步来求解。第一步，求出相邻拓扑关系的无尺寸的平面布局，即根据待布物之间的确定位置关系构造一个图，图中节点代表各待布物，连接节点的边表示待布物之间的确定位置关系。第二步，根据布局图，利用优化算法求出待布物之间的具体尺寸。,2023/8/29,湘潭大学信息工程学院,模拟退火算法(Simulated Annealing Algorithm)演化算法(Evolutionary Algori

11、thm)上述四种方法基本上是用数学方法求解数学模型问题。人工智能(包括专家系统)(Artificial Intelligence including Expert System)人机交互、人机结合与人机协同算法(Human-Computer Interaction,Combination and Cooperation Algorithm),2023/8/29,湘潭大学信息工程学院,布局问题评述及其策略和求解算法的发展前景,现在的复杂布局研究存在如下问题：从布局策略上讲，传统的计算机辅助布局的思路，多将实际问题化为简化的数学模型用计算机算法求解。由于数学模型过于简化，即使能求得结果，但距离解决

12、实际问题相差甚远，因为实际的工程影响因素复杂，存在不可（或难以）数学模型化的问题；从布局问题模型的描述上讲，布局问题的有效、精确表达是解决问题的前提和基础。目前多用数学模型，若模型简单则不能概括必要内容，若模型过于复杂，又无法求解。另外，缺乏包含数学、仿真、符号的复合模型研究，缺乏将工程复杂布局问题从一个复杂工程系统角度去研究；,2023/8/29,湘潭大学信息工程学院,从求解方法上讲，复杂的布局问题求解困难在于存在组合爆炸，如何解决成为关键。但由于以往研究人员各自研究领域及知识背景的不同，很难甚至无法与其他求解方法协同进行设计求解。解决此问题，目前常见的途径是寻找好的算法或者是算法集成；从优

13、化布局方案的评价上讲，尚未建立一套科学和有效的布局方案评价体系，这给布局优化过程中的方案选择和决策带来困难；从研究难度和规模上讲，存在的问题是：对一、二维布局研究多，三维布局研究少，尤其是对三维带性能约束布局研究少；对小型问题研究多，对中大型问题研究少；从实用化上讲，实践应用深度和广度有待提高。,2023/8/29,湘潭大学信息工程学院,关于布局策略,布局策略的安排是问题求解的前提或出发点。布局策略的表现形式是数学模型，然后采取相应的算法。目前带性能约束布局问题中常用的布局策略大多数是采用传统的计算机辅助设计的思想，即将实际问题简化为单一的数学模型，这种单一的模型往往长于描述问题的某方面的特点

14、，而不善于表达问题的综合属性，也缺少科学有效的布局方案评价体系；特别是对于复杂的三维问题这种布局策略的局限性更为突出；因此即使能算出结果，可能与实际问题相差很远。,2023/8/29,湘潭大学信息工程学院,求解算法的发展前景 航天器舱布局方案设计目前国外（如欧、美）主要有三种方法：一是演化算法；二是虚拟（现实）设计；三是协同设计。其中关键因素是“算法”与“人”。无论是虚拟设计还是协同设计，若无有效的布局算法，并发挥人的作用，尤其是对于如此复杂工程设计，是无法完成高质量设计的。人机结合和人机交互的思想充分发挥了人机各自的特长，将这些思想用于其它算法的求解，能够得到生动的用户界面，并将人的知识实时

15、地加入到算法中，使算法快速、有效地解决带性能约束布局问题。对于求解工程复杂布局问题，对解决人机合作的“可操作性”问题，提供了一种方法或途径。演化算法、仿真技术、虚拟设计、人工智能、人机结合或人机交互算法的集成综合的方法，对带性能约束布局算法的发展将会有很大的推动。,2023/8/29,湘潭大学信息工程学院,1.1.3 航天器布局设计研究进展 航天器（卫星、飞船、空间站）(如图1.5)是由有效载荷、结构、热控制、姿态与轨道控制、电源、跟踪遥测与遥控、数据管理等分系统所组成，分系统又由各自的仪器、设备和部件组成；组件（部件）形式多样、数量繁多；设备与设备之间、分系统与分系统之间有各种不同的机、电、

16、液、气接口，并有传动、管线、缆线相连；所以航天器是一个复杂工程系统126-128。其布局方案设计是研究如何充分利用航天器有限的空间，布置尽可能多的组件和仪器、设备，并满足其内部和周围环境的各种约束要求的问题,这是一个多学科交叉课题。,2023/8/29,湘潭大学信息工程学院,1.5礼炮号空间站,2023/8/29,湘潭大学信息工程学院,航天器总体布局方案设计,航天器总体布局方案设计的目的是在选定构型（组件或子系统）基础上将航天器上的仪器设备布置在各舱段的合适位置（如图1.6和1.7）。对于载入过程中使用的和需要返回地面的仪器设备应当布置在返回舱，仅在载入前使用的设备可以布置在轨道舱或仪器设备舱

17、，以降低卫星或飞船的结构质量。在进行总体布局方案设计之前，要对航天器的功能要求进行分析，选择组件或子系统，然后确定组件或子系统之间的相互位置关系，并使总系统具有一个协调完善的造型；最后从多个布局方案中择优选取。航天器的总体布局是全局性的重要问题，不但要考虑到航天器各组件或子系统之间的各种约束，而且还要考虑航天器同各种外部因素（如空间环境）之间的约束，尽量达到功能合理、结构紧凑、层次清晰、比例协调等要求。总体上要符合航天器总体设计的要求。,2023/8/29,湘潭大学信息工程学院,图1.6 联盟号飞船,2023/8/29,湘潭大学信息工程学院,图1.7空间站各舱段示意图,2023/8/29,湘潭

18、大学信息工程学院,图1.8空间站实验舱标准柜,2023/8/29,湘潭大学信息工程学院,图1.9标准柜待布物优化图,2023/8/29,湘潭大学信息工程学院,航天器舱布局方案设计,航天器舱布局方案设计是研究在满足各种工程技术条件的前提下，如何将各种仪器和设备最优地布置在航天器舱体内（或外）(如图1.7和1.8)，使得布局评价指标达到最优或满足工程结束准则。它属于带性能约束的三维布局优化问题，具有不确定性、高度非线性、知识不完备性、既需定性计算又需定量分析等特点。布局问题的NP-困难性和航天器设计本身的工程系统复杂性使得该问题的解决既存在理论上的开拓性和挑战性，又存在工程实践上的艰难性和复杂性。

19、Ferebee 等介绍了一种系统方法（Systematic method）来确定地球轨道卫星上观测设备的优化布局问题。Braun等将协同优化算法用于单级轨道运载火箭的布局设计。滕弘飞等在文136中以返回式卫星舱布局方案设计为背景，提出所谓的转动圆桌平衡摆盘问题，并建立了该问题的数学模型。同时提出了模式迭换法、主布模法等方法求解。,2023/8/29,湘潭大学信息工程学院,图1.10 联盟号返回舱,2023/8/29,湘潭大学信息工程学院,图1.11 返回式卫星,2023/8/29,湘潭大学信息工程学院,航天器天线布局方案设计,一般说来，航天器天线在电气性能、机械结构、温度控制以及总体布局之间，

20、往往互相矛盾，需统筹兼顾、折衷考虑一系列问题。天线布局受航天器结构形状和表面位置所限，但由于天线的功能、工作频率和航天器的轨道姿态，天线又必须放在特定位置；多种天线相互为邻，在电气性能上各种天线又不可互相妨碍；天线同航天器上的突起、伸长物件不应互相干涉；因此，航天器天线的布局相当复杂，直接关系到卫星性能的好坏。,2023/8/29,湘潭大学信息工程学院,图1.12天线结构总体示意图Fig1.12 Diagram of antenna general structure,Linden 等讨论了使用遗传算法求解的卫星结构方面的金属天线的优化布局问题。Coulomb等以BOPSAT卫星的有效载荷的设

21、计为背景，对移动连接天线的布局进行了探讨。比较了几种控制辐射矩阵的组态，分析了其优缺点，最后采用了混合（主动被动）组态设计方法进行布局设计。Boissonnat 等介绍了怎样把一些物理布局约束转化为几何模型和怎样利用Minkowski 操作放置某些设备，特别是天线的布局。,2023/8/29,湘潭大学信息工程学院,航天器其它组件的布局方案设计,航天器帆布局方案设计 航天器稳定平台布局方案设计 航天器姿控发动机布局方案设计 航天器气动外形布局方案设计 航天器复杂插座板插孔布局方案设计 航天器电路板布局方案设计,2023/8/29,湘潭大学信息工程学院,太阳帆利用太阳光的压力产生能量，保证航天器进

22、行太空飞行。太阳光子不停地撞击太阳帆，使得太阳帆所获得的动量不断增加。Genta等介绍了一种可以变动的太阳帆的结构布局。它是一种可膨胀的桁架结构，经过展开以后依旧保持压力以缓解所有的压缩力。帆的表面是一个圆形的薄膜，有效载荷趋于薄膜的中心。为了计算有效载荷距离中心的距离，采用蛛网组态分割的方法来解决，用一定数量的圆形电缆依附在外桁架上以支撑太阳帆。Pillow太阳帆结构示意图如图1.13所示。,2023/8/29,湘潭大学信息工程学院,空间太阳探测器的标准稳定平台（Unified Stabilized Platform，USP）作用是使面向太阳的各种探测设备稳定地指向太阳。Astafourov

23、等介绍了标准稳定平台（USP）的布局，考虑了平台同科学设备（分光计和辐射计）之间的不干涉性。设计控制结构的原则主要是在考虑有效载荷的外形尺寸和重量的前提下，满足USP操作的精确性要求。建立了一个模块化的系统，可以有效的处理带有各种载荷的稳定平台，以增加其有效负载，减小项目的花费。,图1.14 带有稳定平台的空间太阳探测器有效载荷的布局251-分光计；2辐射计；3太阳能传感器；4驱动B；5驱动YFig.1.14 Layout for payload of space solar patrol integrated with stabilized platform25spectrometer;2-

24、radiometers;3-solar sensor;4-drives B;5-drives Y,2023/8/29,湘潭大学信息工程学院,航天器为了具有良好的稳定性、精确的速度和姿态控制，动力系统质量的大小至关重要。在推进剂及其输送系统选定之后，通过对推力系统的设计变量进行参数分析，即可初步确定满足飞行任务的动力系统的质量。胡小平，王中伟等在液体推进剂动力系统质量模型的基础上，针对采用双组元推进剂姿控发动机的空间飞行器,在总有效冲量和有效冲量矩一定的条件下,提出了优选动力系统总质量最轻的姿控发动机布局方案的一种方法。,图1.15 空间飞行器姿态控制发动机布局方案Fig.1.15 Locali

25、ty arrangement of attitude control engine,2023/8/29,湘潭大学信息工程学院,所谓的气动优化布局是指优化航天器气动外形，使之满足航天器对升阻比、静稳定度、配平攻角等性能方面的要求。潘腾、安复兴讨论了垂直起飞、垂直降落（VTVL）飞行器（一种先进的、能重复使用的航天飞行器）的选型和气动优化布局。对各参数（如削面角、球头半径等）的气动性能曲线进行分析，并综合考虑了各参数的相互制约作用，利用设计师的经验给出了气动优化布局，其示意图如图1.16所示。最后通过风洞实验验证了布局的正确性。,图1.16 优化气动布局外形及尺寸参数Fig.1.16 Shape

26、and size parameters of aerodynamic layout optimization,2023/8/29,湘潭大学信息工程学院,航天器复杂插座板插孔布局方案设计 唐飞等研究了航天器中一种能够在火工螺栓作用下自动拔脱的复杂插座板上插孔的布局设计问题，简化为在圆形插板上，根据给定的n个插头，考虑电、液、气各种管线插头的插座板（非凸的可布空间）和插头的拔脱力、插座板的紧固螺栓力、边缘弹簧的弹簧力等约束情况下，布置其插孔位置。它属于带作用力约束的二维装填(Packing)问题。给出了该问题的数学模型，并用给出的复数编码的遗传算法进行求解154，提供一个设计参考方案。,2023/

27、8/29,湘潭大学信息工程学院,航天器电路板布局方案设计 Hirt等介绍了将虚拟样机技术（Virtual Prototyping,VP）应用到航天器上含有转换器的电路板的布局设计。将VP作为一种系统化的分析和选择合适结构的方法,以花费为评价准则，并行的分析几种可能的方案。使用基于JavaCAD平台的Java语言完成系统的设计。,图1.17 含有5:4转换器的电路板Fig.1.17 PCB containing a 5:4 switch,2023/8/29,湘潭大学信息工程学院,1.1.4 用遗传算法求解布局问题,(1)基本遗传算法的框架 按照Goldberg提出的框架，基本遗传算法(Simpl

28、e genetic algorithm,SGA)只包括交叉、变异和选择三种基本遗传算子，可用式(1)所描述的一个8元组表示。SGAC,E,P0,M,(1)其中C为个体编码方法，E为个体适应度评价函数，P0为初始群体，M为群体规模大小尺寸，为选择算子，为交叉算子，为变异算子，遗传运算终止条件。,2023/8/29,湘潭大学信息工程学院,基本遗传算法的主要步骤如下：Step1随机产生P0个初始种群，并对每一个种群，求出适应度函数的值。Step2判断最优个体是否满足要求，如果满足则输出结果后转Step6，否则执行下一步。Step3按交叉概率Pc对个体作交叉运算产生新一定量的个体。Step4按变异概率

29、Pm对个体作交叉运算产生新一定量的个体，通过交叉和变异后种群的规模为M。Step5对M个种群求出其适应度函数的值，按适应度大小选取其中的P0个种后转Step2。Step6算法结束。,(2)基本遗传算法的几个重要的概念 问题的编码 将一个问题的解空间转换为遗传算法所能处理的搜索空间的方法。问题的编码方法直接决定着遗传算法的性能和求解的效率。编码方法有二进制编码、十进制编码、序号编码和符号编号等。布局遗传算法算例都采用十进制编码。适应度函数 适应度是度量种群个体在优化计算中可能达到或接近于找到最优解的程度。度量种群个体适应度的函数则称为适应度函数。一般要求适应度函数f(x)0。适应度大的种群个体遗

30、传到下一代的概率就越大，适应度小的种群个体遗传到下一代的概率就越小。,2023/8/29,湘潭大学信息工程学院,遗传算子 遗传算子包括选择算子、交叉算子和变异算子。选择是为了避免有效基因损失，使性能较优的个体得以更高的概率生存，从而加快收敛速度和提高计算效率。选择算子有比例选择、排序选择、最优保存、确定式采样选择、期望值选择、无回放余数随机选择和随机联赛选择。比例选择算子是以正比于个体适应度的概率来选择个体，而排序选择算子是按适应度大小顺序对群体中的所有个体进行排序，然后把事先计算好的概率表依次分配给每个个体作为各自的选择概率。其中最常用的是比例选择和排序选择，本文遗传算法算例采用最优保存策略

31、，因为根据标准遗传算法的收敛性可知：使用最优保存策略可使遗传算法收敛于最优解的概率为1。,2023/8/29,湘潭大学信息工程学院,交叉是在种群中的两个个体进行。通过交叉产生新的个体，以致遗传算法能在解空间中进行有效的搜索，同时降低对有效模式的破坏概率。常用的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉和算术交叉。本文遗传算法算例都采用两点交叉。变异是个体中某些基因位上的基因值加以改变。种群个体通过变异产生新的个体，常用的变异算子有基本变异、均匀变异、非均匀变异和高斯变异等。变异算子在遗传算法中的作用是使形遗传算法具有局部搜索能力和维持群体的多样性，防止出现未成熟收敛现象。,2023/8/

32、29,湘潭大学信息工程学院,(3)基本遗传算法的几个参数设定 基本遗传算法的参数有编码长度、种群规模、交叉概率、变异概率和终止代数。编码长度 用二进制编码表示个体时，编码的长度l与求解问题的要求精度有关；用实数编码表示个体时，编码的长度l与决策问题的变量个数n相等；用符号编码表示个体时，编码的长度l由问题的编码方式来确定。群体规模 群体规模M表示群体中个体的数量。当M取值较小，能一定程度提高遗传算法的计算速度，但降低了群体的多样性，可能引起遗传算法的早熟现象；当M取值较大，则遗传算法的效率降低。一般M的取值在20100之间。,2023/8/29,湘潭大学信息工程学院,交叉概率 遗传算法通过交叉

33、产生新的个体，因此，交叉概率不能取得太小，也不能取得过大，若取得过大，会破坏群体中的优良模式，对进化计算产生不利的影响；若取得过小，则产生新的个体的速度较慢。一般交叉概率取值在0.4 0.99之间。变异概率 变异概率直接决定产生新的个体的多少。变异概率越大，由于产生新的个体就越多，增加了群体的多样性，但也破坏更多优良的个体，使遗传算法的性能接近于随机搜索算法；变异概率取得过小，则产生新的个体和抑制早熟现象的能力都会较差。一般变异概率取值在0.050.4之间。,2023/8/29,湘潭大学信息工程学院,终止代数 终止代数T是遗传算法运行终止的一个主要参数，它表示遗传算法运行到指定代数就终止。这时

34、，群体中的最优个体被作为所求问题的最优解输出。一般终止代数取值在10020000之间。这里需要说明的是遗传算法还可以使用别的终止条件来终止运行，如群体中所有个体适应度的方差均小于某一较小的阀值。,2023/8/29,湘潭大学信息工程学院,(4)约束条件的处理 由于求解的优化问题都带有一定的约束条件，因此，应用遗传算法求解时都必须对约束条件进行处理。一般的处理方法有搜索空间限定法、可行解变换法和罚函数法。搜索空间限定法的基本思想是对遗传算法的搜索空间的大小加以限制，使搜索空间的表示一个个体的点与解空间中表示一个解的点存在一一对应的关系。可行解变换法的基本思想是在由个体基因型到个体表现型的变换中，

35、寻找出一种由个体基因型与个体表现型之间的多对一的变换关系，使进化过程中所产生的个体总能够通过这个变换而转化成解空间中满足约束条件的一个可行解。罚函数法的基本思想是对在解空间中无对应可行解的个体，计算其适应度时处以一个罚函数，从而降低该个体适应度值，使该个,2023/8/29,湘潭大学信息工程学院,体被遗传到下一代群体中的机会减少。随着遗传算法的运行，不可行解在解群占的比例总体上越来越少，可行解逐步占住主导地位并逐步趋向最优解。只要罚函数形式得当，一般都可得到好的结果。罚函数法是目前最常用的一种方法。例如：约束优化问题式(2)加入罚函数可描述为式(3)的形式。,其中X(x1,x2,xn)，n为设

36、计变量的个数，函数G和H为罚函数，i和j为惩罚系数。,(2),(3),2023/8/29,湘潭大学信息工程学院,问题1该问题是一个带静平衡性能约束，且有等价待布物的约束布局优化问题。圆容器的半径R70mm，待布物为6 个圆盘，它们的半径r1r6分别为16.5、16.5、16.5、12.0、20.0和24.5mm，设静不平衡量J的允许值为J，每个圆盘的质量miri2(g)。要求给出满足不干涉、静平衡约束条件下，各待布物向容器中心高度聚集的布局方案。以容器中心为原点，向右且与容器和圆盘的表面重合的射线为x 正半轴建立直角坐标系。不计圆盘的厚度，其布局优化模型如下：求 X(xi,yi)，i=1,2,

37、n 使 min f(X)=max(xi2+yi2)+ri s.t g1(X)=(xi2+yi2)(R ri)0g2(X)=ri+rj(xi xj)2+(yi yj)2)0 g3(X)=(m1x1+mnxn)2+(m1y1+mnyn)2)-J 0,2023/8/29,湘潭大学信息工程学院,给出初始点X0，如图1.18(a)所示，其中待布物OBJ1和OBJ2的形心重合。对应局部最优解的目标函数63.976mm，向量函数89.903，用文献的方法和准边界直线法分别构造15个同构和15个非同构初始点，并采取罚函数法求出布局最优解。表1.1是采用的两种算法的计算结果比较，表中R为外包络圆半径，J为静平衡

38、量，t为计算时间。两种方法的最优布局方案如图1.18(b)和(c)所示。,(a),(b),(c),图1.18问题1的两种布局方案,2023/8/29,湘潭大学信息工程学院,表1.1问题1的计算结果比较,2023/8/29,湘潭大学信息工程学院,问题2印刷电路板设计问题，它是一个要求待布物满足一定邻接关系的布局问题，在二维空间放置15个待布物，待布物间的权值Wij(表示待布物在位置空间上的亲密度)，要求待布物摆放时满足下述条件：(1)待布物之间不干涉，(2)具有较大权重值的待布物应相互聚集。即C的数值最小，其中dij为两待布物之间的距离，(3)待布物的外包络矩形面积最小。数学模型如下：,式中S表

39、示外包络矩形的面积，为C相对于S的权重，Ai和Aj分别待布物i和j 的面积，待布物间的权重矩阵如式(4)所示，半径分别为12,3,12,3,9,10,7,8,4,12,6,10,9,9,10。,2023/8/29,湘潭大学信息工程学院,(4),2023/8/29,湘潭大学信息工程学院,(a)PHAIA,(b)H CIGA,(C)HDCLDM,(a)CBRHGA,图 1.19问题2的4种布局方案,2023/8/29,湘潭大学信息工程学院,表1.2问题2的4种计算结果比较,2023/8/29,湘潭大学信息工程学院,表1.3问题2的4种布局方案的性能指标,从表1.2和表1.3来看，CBRHGA的计算

40、效率比HDCLDM方法提高了7倍，而包络矩形的面积和权距，CBRHGA比HDCLDM方法分别减少了0.12%和1.17%；CBRHGA的计算效率比PHAIA方法提高了1.38倍，包络矩形的面积和权距，CBRHGA比PHAIA方法分别减少了7.68%和10.72%；CBRHGA的计算效率比HCIGA方法提高了8.26倍，包络矩形的面积和权距，CBRHGA比HCIGA方法分别减少了4.79%和16.79%。,2023/8/29,湘潭大学信息工程学院,问题3图1.20(b)是一种棱台型卫星的简化模型，舱体用厚度均匀的壳体制成一回转体，空腔用于各仪器的布局空间；腔体中的底部承载板基面用以安装各仪器，除

41、此以外的地方均不能安装任何仪器；承载板的厚度均匀，基面与旋转体轴线垂直。图1.20(a)是7.10(b)的二维平面布局图。,图1.20卫星舱布局设计问题,2023/8/29,湘潭大学信息工程学院,以旋转轴为z轴，以承载板中心为原点建立直角坐标系如图1.21(a)，卫星舱及部件在xoz坐标平面上的正投影图如图1.21(b)，其中，Rt、R0和Ht分别是圆台上、下底面圆半径和圆台的高度，T是承载板厚度。给定一组待安装的仪器(待布物)，每个待布物的几何尺寸、质量、质心位置均已知，布局完毕后整个舱体和保仪器以固定的角速度转动，要求布局满足如下条件：,图1.21卫星舱的三维图和xoz平面的投影图,202

42、3/8/29,湘潭大学信息工程学院,(1)各仪器不得发生干涉，即互不重叠(实际工程中保证不小于规定的充许空间距离)；(2)各仪器的任何部分不得超出给定的布局空间，即不得与舱体发生干涉；(3)各仪器尽可能地布局在舱体中心轴(z轴)附近，即各仪器的外包络圆半径应尽量小，提高空间利用率；(4)在满足上述各项要求的前提下，应使系统绕舱体中心轴(z轴)转动时产生的动不平衡量和质心偏移量都小于充许值，并且尽量小。根据上述条件和图1.21的结构，设舱内待布物中，固定位置长方体数为N1，固定位置圆柱体数为N2，可自由布局位置长方体数为N3，可自由布局位置圆柱体数为N4，NN1N2N3N4。建立数学优化模型的表

43、达式如式(5)和(6)所示。,2023/8/29,湘潭大学信息工程学院,求：Xi(xi,yi,i)T，iIn1,2,N(5)minf(X)=1F2M(6)其中：(xi,yi)TR 2，xi,yi分别为各待布物质心的x,y坐标，设待布物为刚体，待布物的质心与形重合，i表示长方体正投影矩形的转角，它是以x正半轴为始边，矩形的长边或其延长线为终边所成的角(i0,)。F为舱体的动不平衡力，M为舱体的质心偏移量，其值由式(7)和(8)计算。,其中：mi为待布物i的质量，为卫星舱旋转的角速度，hi为待布物i的质心高度。,(7),(8),2023/8/29,湘潭大学信息工程学院,s.t int OBJiin

44、t OBJj=i,jIn1,2,N,ij R*=min(xi2+yi2)+ri其中：R*为各待布物的外包络圆。结束准则为式(9)和(10)。,(9),(10),其中：j和m分别为舱体的动不平衡力和舱体的质心偏移量的充许值。如图1.21(b)所示的卫星舱模型，舱旋转的角速度为40r/min，Rt750mm，Ht800mm，T20mm。要在承载板上放置10个待布物，要求所有待布物尽量向中心,2023/8/29,湘潭大学信息工程学院,集中。其中固定位置长方体数为N10，固定位置圆柱数为N,21，可自由布局位置长方体数为N35，可自由布局位置圆柱体数为N44，舱体的动不平衡力的充许值j20N，舱体的质

45、心偏移量的充许值m10N.mm，其它初始数据见表1.4，建立式(5)(10)的数学模型。,表1.4问题3的待布物的初始数据,2023/8/29,湘潭大学信息工程学院,表1.5问题2的4种布局方案的性能指标,图 1.22问题3的3种布局方案,2023/8/29,湘潭大学信息工程学院,从表表1.5和表1.6来看，CBRHGA方法的求解效率比HCIGA提高了35.50%，而包络圆半径减少了0.71%，动不平衡力减少了9.43%，在x方向和y方向上的质心偏移量则分别减少56.98%和12.56%；CBRHGA方法的求解效率比SGA提高了42.38%，而包络圆半径减少了1.19%，动不平衡力减少了98.

46、67%，在x方向和y方向上的质心偏移量则分别减少99.43%和98.32%。,表1.6问题3的3种计算结果比较,2023/8/29,湘潭大学信息工程学院,1.多目标优化问题,1.2 机器人手臂碰撞检测,1.2.1 拉格郎日乘子求解优化问题1.2.2 机器人手臂的建模 1.2.3 手臂间最小距离表达1.2.4 最小距离的优化计算 1.2.5 机器人手臂碰撞检测算法,2023/8/29,湘潭大学信息工程学院,1.2.1拉格郎日乘子求解优化问题,(1)等式约束非线性优化问题 min f(X)s.t.gi(X)=0,i=1,2,m求解方法：将个方程分别乘以1,2,m，然后把它们的和加到目标函数中去得到

47、式(11)。L f(x1,x2,xn)+(11)对上述式()两边求m+n个变量的偏导数得方程组(12)，解方程组(12)得到问题的解。,(12),2023/8/29,湘潭大学信息工程学院,例如：现需设计一个废水沉淀箱(如图1.23)。但限定各个面壁加底板的总面积不得超过288m2，应如何设计尺寸使沉淀箱的容积最大。解：它的目标函数是：maxV=xyz 约束条件是S3yzxy2 xz288m2即约束优化问题：maxV=xyzs.t.3yzxy2xz-288=0 L=xyz-(3yzxy2xz-288)，两边对4个变量求偏导得式(13)解方程组(13)得x:y:z=3:2:1,从而x=12m，y=

48、8m，z=4m。,(13),图1.23废水沉淀箱,2023/8/29,湘潭大学信息工程学院,(2)不等式约束非线性优化问题 min f(X)s.t.gi(X)0,i=1,2,m求解方法：将不等式约束转化为等式约束，则得到：min f(X)s.t.gi(X)zi2=0,i=1,2,m 例如：求 min f(X)2x12-2x1 x2 2x22-6x1 s.t.g1(X)=3x1 4x2-6 0 g2(X)=-x1 4x2-2 0 解：不等式约束转化为等式约束有：g1(X)=3x1 4x2-6 x32 0g2(X)=-x1 4x2-2 x42 0,2023/8/29,湘潭大学信息工程学院,引进拉格

49、朗日函数L f(x1,x2,x3,x4)-=(2x12-2x1 x2 2x22-6x1)-1(3x1 4x2-6 x32)2(-x1 4x2-2 x42)(14)对上述式(14)两边求6个变量的偏导数得方程组，解方程组(14)得到问题的解。但其求解是比较繁重的。,2023/8/29,湘潭大学信息工程学院,(3)用库恩塔克条件求解约束非线性优化问题 min f(X)s.t.gi(X)0,i=1,2,m求解方法：若X*是问题(15)的极小值点，而且在X*点的各起作用约束的梯度线性无关，则存在向量*(1*,2*,l*)T使得式(16)成立。,(15),(16),条件(16)称为简称为K-T条件，满足

50、这个条件的点(当然它也满足非线性优化问题的所有约束条件)称为库恩-塔克点或称为K-T点。1*,2*,l*为拉格朗日乘子。,2023/8/29,湘潭大学信息工程学院,对于约束非线性优化问题 min f(X)s.t.hi(X)=0,i=1,2,m gj(X)0,j=1,2,l求解方法：若X*是问题(15)的极小值点，而且在X*点的各起作用约束的梯度hi(X*)(i=1,2,m)和gj(X*)(j J)线性无关，则存在向量*(1*,2*,l*)T 和*(1*,2*,l*)T使得式(17)成立。,满足式(17)的点(当然它也满足非线性优化问题的所有约束条件)也称为库恩-塔克点或称为K-T点。1*,2*