问题的数学模型与算法

2023/2/6湘潭大学信息工程学院

研究生课程：

问题的数学模型与方法

(2011年上学期)授课：黎自强(教授)联系电话：2023/2/6湘潭大学信息工程学院主要内容：

1.目标函数优化问题

1.1遗传算法求解复杂布局问题

1.2拉格郎日算子求解圆柱体碰撞检测问题

2.偏微分方程数值求解

2.1铸件凝固过程的温度场模拟

2023/2/6湘潭大学信息工程学院1.目标函数优化问题1.1.1工程背景和科学问题的提出1.1.2布局优化问题研究进展1.1.3航天器布局方案设计研究进展1.1.4用遗传算法求解布局问题1.1复杂布局问题2023/2/6湘潭大学信息工程学院1.1.1工程背景和科学问题的提出

a)发达国家航天器发展现状

美国与欧洲空间局自80年代起，致力于用计算机技术解决航天器舱的待布物总体布局问题的研究，其关键理论、方法、技术至今仍处于保密状态。近年来有用协同优化法设计航天器的保护装置和得到NASA资助的用遗传算法进行航天器的设计，但很少涉及布局设计的内容。根据我国人员出国考察获悉，以卫星布局设计为例，目前美国设计效率比我国快20倍以上，但是其性能和空间利用率对比不详。2023/2/6湘潭大学信息工程学院b)国内航天器发展现状

我国航天器设计多以人工设计为主，参考样图或资料，用计算机辅助绘图（二、三维），然后用国外软件进行三维造型模装，再用国外软件进行三维动力学验算。若不合适，用人工修改设计，最后建造1:1实物模型，进行实验验证。2023/2/6湘潭大学信息工程学院c)人工设计存在的问题：性能不易保证或非优化；空间利用率低；设计成本高；设计周期长。

过去卫星曾因总体布局不当，动不平衡过大，曾造成过早报废的恶果。况且我国还要研制更复杂的空间站，其布局设计尤为重要。

2023/2/6湘潭大学信息工程学院d)科学问题的提出从理论上说，航天器布局设计，可归结出“可数学模型化”和“不可或难数学模型化”两类问题。前者属很难的带性能约束的三维布局优化问题；后者多属工程复杂系统问题，涉及人脑思维模型问题，解决方法有二种：一是人工智能，基于智能的知识模型及其推理；二是人机结合(Man-MachineSynergy)或人机合作(puterCooperation)。航天器布局设计属交叉学科前沿课题的基础理论和应用基础研究，具有重要的科学意义。2023/2/6湘潭大学信息工程学院1.1.2布局优化问题研究进展

布局问题(LayoutProblem)属于复杂的组合优化问题，即使最简单的一维布局也属于NPC问题。自1831年高斯(Gauss)研究布局问题开始，虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法。从理论上讲，布局问题可分为切段(Cutting-Stock)问题和装填(Packing)问题。2023/2/6湘潭大学信息工程学院按照布局物体的布局维数分类a)一维布局问题

b)二维布局问题

c)三维布局问题

2023/2/6湘潭大学信息工程学院

a)一维布局问题

一维布局问题中典型的例子是在给定长度的棒料上，切割长度不等的若干短棒，此类问题通常称为切段问题(Cutting-StockProblem)。解决方法：Faggioli[5]利用启发式算法提出了切段排序问题的数学模型和一个三步解法；Vasko[6]和Nitsche[7]

分别利用树搜索算法和松弛算法来解决一维切段问题；PetridisVassilios等[8]利用遗传算法以动态的方式把问题的约束合并到适应度函数中。2023/2/6湘潭大学信息工程学院b)二维布局问题

二维布局问题包括：一刀切问题

将某些不同大小的小矩形按照一刀切的原则排放在一个大矩形板材上，使面积浪费最小，这是剪床落料、玻璃切割、纸张切割中遇到的主要问题。所谓一刀切，是指切割总是从矩形板材的一边开始一直切到其对边，即每切一刀都将一个矩形分割成两个小矩形

底盘装载问题

底盘装载问题来源于运输、搬运中的货物摆放或装箱。将多个相同大小的立体箱子放入一立方体容器中，且要求放入的箱子越多越好。2023/2/6湘潭大学信息工程学院矩形布局问题(RectanglePackingProblems)

矩形布局问题是将许多大小不同的二维矩形布置在一个大的矩形中，使面积覆盖率最大，这是大规模集成电路设计中所碰到的主要问题。圆布局问题(CirclePackingProblems)圆布局问题是将许多大小相同或不同的圆布置在一个大的圆形、三角形或矩形容器中，使面积覆盖率最大[39]。这类问题大量地存在于几何、化学、生物学、工程和优化中，已经引起人们的很大关注[40]。

通常不等圆装填问题还需满足一定的性能约束条件，譬如：惯性、平衡性、和稳定性约束等，我们把这种问题称为带性能约束的不等圆装填问题。2023/2/6湘潭大学信息工程学院二维不规则图形布局问题(2-DIrregularGraphLayoutProblems)

二维不规则图形布局问题是指将许多任意形状、大小的二维形体布置在一任意形状的二维平面内以使某一性能最优，如板材下料，服装裁剪等。处理这类问题通常是把不规则图形套排在一些形状比较规则的简单图形中，然后用这些简单的图形在给定的平面内排样，以降低问题的复杂程度。2023/2/6湘潭大学信息工程学院三维布局问题

三维布局问题包括：无性能约束的三维布局问题(3-DLayoutProblemswithNon-BehavioralConstraints)无性能约束三维布局问题是指将尽量多的不同形状、尺寸的三维物体放入到一长方体（或圆柱体）容器中，例如背包问题、集装箱问题。

带性能约束的三维布局问题(3-DLayoutProblemswithBehavioralConstraints)

。带性能约束三维布局问题是指将任意形状、大小和性能的三维实体摆放在一个任意形状、大小的三维容器中，以满足某些约束或使某些目标最优

2023/2/6湘潭大学信息工程学院例子约束底盘装载和船舶配载问题

汽车驾驶舱布局问题

集成电路(VLSI)的布局规划

航天器舱布局方案设计问题

2023/2/6湘潭大学信息工程学院带性能约束布局问题的算法

启发式算法(HeuristicAlgorithm)

拟物拟人法

拟实验综合启发式算法

八叉树结构与定位―定序函数相结合的启发式算法

GENET模型

Montreuil模型

膨胀算法

2023/2/6湘潭大学信息工程学院图论法(GraphTheory)

图论作为组合数学的重要组成部分，在许多领域有着广泛的应用。该方法一般将带性能约束布局问题分两步来求解。第一步，求出相邻拓扑关系的无尺寸的平面布局，即根据待布物之间的确定位置关系构造一个图，图中节点代表各待布物，连接节点的边表示待布物之间的确定位置关系。第二步，根据布局图，利用优化算法求出待布物之间的具体尺寸。

2023/2/6湘潭大学信息工程学院模拟退火算法(SimulatedAnnealingAlgorithm)演化算法(EvolutionaryAlgorithm)上述四种方法基本上是用数学方法求解数学模型问题。人工智能(包括专家系统)(ArtificialIntelligenceincludingExpertSystem)人机交互、人机结合与人机协同算法(puterInteraction,CombinationandCooperationAlgorithm)2023/2/6湘潭大学信息工程学院布局问题评述及其策略和求解算法的发展前景现在的复杂布局研究存在如下问题：

从布局策略上讲，传统的计算机辅助布局的思路，多将实际问题化为简化的数学模型用计算机算法求解。由于数学模型过于简化，即使能求得结果，但距离解决实际问题相差甚远，因为实际的工程影响因素复杂，存在不可（或难以）数学模型化的问题；

从布局问题模型的描述上讲，布局问题的有效、精确表达是解决问题的前提和基础。目前多用数学模型，若模型简单则不能概括必要内容，若模型过于复杂，又无法求解。另外，缺乏包含数学、仿真、符号的复合模型研究，缺乏将工程复杂布局问题从一个复杂工程系统角度去研究；

2023/2/6湘潭大学信息工程学院从求解方法上讲，复杂的布局问题求解困难在于存在组合爆炸，如何解决成为关键。但由于以往研究人员各自研究领域及知识背景的不同，很难甚至无法与其他求解方法协同进行设计求解。解决此问题，目前常见的途径是寻找好的算法或者是算法集成；从优化布局方案的评价上讲，尚未建立一套科学和有效的布局方案评价体系，这给布局优化过程中的方案选择和决策带来困难；从研究难度和规模上讲，存在的问题是：对一、二维布局研究多，三维布局研究少，尤其是对三维带性能约束布局研究少；对小型问题研究多，对中大型问题研究少；从实用化上讲，实践应用深度和广度有待提高。2023/2/6湘潭大学信息工程学院关于布局策略

布局策略的安排是问题求解的前提或出发点。布局策略的表现形式是数学模型，然后采取相应的算法。目前带性能约束布局问题中常用的布局策略大多数是采用传统的计算机辅助设计的思想，即将实际问题简化为单一的数学模型，这种单一的模型往往长于描述问题的某方面的特点，而不善于表达问题的综合属性，也缺少科学有效的布局方案评价体系；特别是对于复杂的三维问题这种布局策略的局限性更为突出；因此即使能算出结果，可能与实际问题相差很远。2023/2/6湘潭大学信息工程学院求解算法的发展前景

航天器舱布局方案设计目前国外（如欧、美）主要有三种方法：一是演化算法；二是虚拟（现实）设计；三是协同设计。其中关键因素是“算法”与“人”。无论是虚拟设计还是协同设计，若无有效的布局算法，并发挥人的作用，尤其是对于如此复杂工程设计，是无法完成高质量设计的。人机结合和人机交互的思想充分发挥了人机各自的特长，将这些思想用于其它算法的求解，能够得到生动的用户界面，并将人的知识实时地加入到算法中，使算法快速、有效地解决带性能约束布局问题。对于求解工程复杂布局问题，对解决人机合作的“可操作性”问题，提供了一种方法或途径。演化算法、仿真技术、虚拟设计、人工智能、人机结合或人机交互算法的集成综合的方法，对带性能约束布局算法的发展将会有很大的推动。

2023/2/6湘潭大学信息工程学院1.1.3航天器布局设计研究进展

航天器（卫星、飞船、空间站）(如图1.5)是由有效载荷、结构、热控制、姿态与轨道控制、电源、跟踪遥测与遥控、数据管理等分系统所组成，分系统又由各自的仪器、设备和部件组成；组件（部件）形式多样、数量繁多；设备与设备之间、分系统与分系统之间有各种不同的机、电、液、气接口，并有传动、管线、缆线相连；所以航天器是一个复杂工程系统[126-128]。其布局方案设计是研究如何充分利用航天器有限的空间，布置尽可能多的组件和仪器、设备，并满足其内部和周围环境的各种约束要求的问题,这是一个多学科交叉课题。2023/2/6湘潭大学信息工程学院1.5礼炮号空间站2023/2/6湘潭大学信息工程学院航天器总体布局方案设计航天器总体布局方案设计的目的是在选定构型（组件或子系统）基础上将航天器上的仪器设备布置在各舱段的合适位置（如图1.6和1.7）。对于载入过程中使用的和需要返回地面的仪器设备应当布置在返回舱，仅在载入前使用的设备可以布置在轨道舱或仪器设备舱，以降低卫星或飞船的结构质量。在进行总体布局方案设计之前，要对航天器的功能要求进行分析，选择组件或子系统，然后确定组件或子系统之间的相互位置关系，并使总系统具有一个协调完善的造型；最后从多个布局方案中择优选取。航天器的总体布局是全局性的重要问题，不但要考虑到航天器各组件或子系统之间的各种约束，而且还要考虑航天器同各种外部因素（如空间环境）之间的约束，尽量达到功能合理、结构紧凑、层次清晰、比例协调等要求。总体上要符合航天器总体设计的要求。

2023/2/6湘潭大学信息工程学院图1.6联盟号飞船2023/2/6湘潭大学信息工程学院图1.7空间站各舱段示意图2023/2/6湘潭大学信息工程学院图1.8空间站实验舱标准柜2023/2/6湘潭大学信息工程学院图1.9标准柜待布物优化图2023/2/6湘潭大学信息工程学院航天器舱布局方案设计

航天器舱布局方案设计是研究在满足各种工程技术条件的前提下，如何将各种仪器和设备最优地布置在航天器舱体内（或外）(如图1.7和1.8)，使得布局评价指标达到最优或满足工程结束准则。它属于带性能约束的三维布局优化问题，具有不确定性、高度非线性、知识不完备性、既需定性计算又需定量分析等特点。布局问题的NP-困难性和航天器设计本身的工程系统复杂性使得该问题的解决既存在理论上的开拓性和挑战性，又存在工程实践上的艰难性和复杂性。Ferebee等介绍了一种系统方法（Systematicmethod）来确定地球轨道卫星上观测设备的优化布局问题。Braun等将协同优化算法用于单级轨道运载火箭的布局设计。滕弘飞等在文[136]中以返回式卫星舱布局方案设计为背景，提出所谓的转动圆桌平衡摆盘问题，并建立了该问题的数学模型。同时提出了模式迭换法、主布模法等方法求解。2023/2/6湘潭大学信息工程学院图1.10联盟号返回舱2023/2/6湘潭大学信息工程学院图1.11返回式卫星2023/2/6湘潭大学信息工程学院航天器天线布局方案设计

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

Coulomb等以BOPSAT卫星的有效载荷的设计为背景，对移动连接天线的布局进行了探讨。比较了几种控制辐射矩阵的组态，分析了其优缺点，最后采用了混合（主动＋被动）组态设计方法进行布局设计。Boissonnat等介绍了怎样把一些物理布局约束转化为几何模型和怎样利用Minkowski操作放置某些设备，特别是天线的布局。

2023/2/6湘潭大学信息工程学院航天器其它组件的布局方案设计

航天器帆布局方案设计

航天器稳定平台布局方案设计

航天器姿控发动机布局方案设计

航天器气动外形布局方案设计

航天器复杂插座板插孔布局方案设计

航天器电路板布局方案设计

2023/2/6湘潭大学信息工程学院太阳帆利用太阳光的压力产生能量，保证航天器进行太空飞行。太阳光子不停地撞击太阳帆，使得太阳帆所获得的动量不断增加。

Genta等介绍了一种可以变动的太阳帆的结构布局。它是一种可膨胀的桁架结构，经过展开以后依旧保持压力以缓解所有的压缩力。帆的表面是一个圆形的薄膜，有效载荷趋于薄膜的中心。为了计算有效载荷距离中心的距离，采用蛛网组态分割的方法来解决，用一定数量的圆形电缆依附在外桁架上以支撑太阳帆。Pillow太阳帆结构示意图如图1.13所示。

图1.13Pillow太阳帆示意图[13]Fig.1.13Pillowsolarsail[23]外波束有效载荷太阳光2R02023/2/6湘潭大学信息工程学院空间太阳探测器的标准稳定平台（UnifiedStabilizedPlatform，USP）作用是使面向太阳的各种探测设备稳定地指向太阳。

Astafourov等介绍了标准稳定平台（USP）的布局，考虑了平台同科学设备（分光计和辐射计）之间的不干涉性。设计控制结构的原则主要是在考虑有效载荷的外形尺寸和重量的前提下，满足USP操作的精确性要求。建立了一个模块化的系统，可以有效的处理带有各种载荷的稳定平台，以增加其有效负载，减小项目的花费。

图1.14带有稳定平台的空间太阳探测器有效载荷的布局[25]1-分光计；2－辐射计；3－太阳能传感器；4驱动B；5－驱动YFig.1.14Layoutforpayloadofspacesolarpatrolintegratedwithstabilizedplatform[25]spectrometer;2-radiometers;3-solarsensor;4-drivesB;5-drivesY2023/2/6湘潭大学信息工程学院航天器为了具有良好的稳定性、精确的速度和姿态控制，动力系统质量的大小至关重要。在推进剂及其输送系统选定之后，通过对推力系统的设计变量进行参数分析，即可初步确定满足飞行任务的动力系统的质量。

胡小平，王中伟等在液体推进剂动力系统质量模型的基础上，针对采用双组元推进剂姿控发动机的空间飞行器,在总有效冲量和有效冲量矩一定的条件下,提出了优选动力系统总质量最轻的姿控发动机布局方案的一种方法。

图1.15空间飞行器姿态控制发动机布局方案Fig.1.15Localityarrangementofattitudecontrolengine2023/2/6湘潭大学信息工程学院

所谓的气动优化布局是指优化航天器气动外形，使之满足航天器对升阻比、静稳定度、配平攻角等性能方面的要求。

潘腾、安复兴讨论了垂直起飞、垂直降落（VTVL）飞行器（一种先进的、能重复使用的航天飞行器）的选型和气动优化布局。对各参数（如削面角、球头半径等）的气动性能曲线进行分析，并综合考虑了各参数的相互制约作用，利用设计师的经验给出了气动优化布局，其示意图如图1.16所示。最后通过风洞实验验证了布局的正确性。

图1.16优化气动布局外形及尺寸参数Fig.1.16Shapeandsizeparametersofaerodynamiclayoutoptimization2023/2/6湘潭大学信息工程学院航天器复杂插座板插孔布局方案设计

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

2023/2/6湘潭大学信息工程学院航天器电路板布局方案设计

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

基本遗传算法的框架按照Goldberg提出的框架，基本遗传算法(Simplegeneticalgorithm,SGA)只包括交叉、变异和选择三种基本遗传算子，可用式(1)所描述的一个8元组表示。

SGA＝｛C,E,P0,M,Φ,Γ,Ψ,Τ｝(1)其中C为个体编码方法，E为个体适应度评价函数，P0为初始群体，M为群体规模大小尺寸，Φ为选择算子，Γ为交叉算子，Ψ为变异算子，Τ遗传运算终止条件。

2023/2/6湘潭大学信息工程学院基本遗传算法的主要步骤如下：Step1

随机产生P0个初始种群，并对每一个种群，求出适应度函数的值。Step2判断最优个体是否满足要求，如果满足则输出结果后转Step6，否则执行下一步。

Step3

按交叉概率Pc对个体作交叉运算产生新一定量的个体。Step4按变异概率Pm对个体作交叉运算产生新一定量的个体，通过交叉和变异后种群的规模为M。Step5

对M个种群求出其适应度函数的值，按适应度大小选取其中的P0个种后转Step2。Step6算法结束。

(2)基本遗传算法的几个重要的概念

①问题的编码将一个问题的解空间转换为遗传算法所能处理的搜索空间的方法。问题的编码方法直接决定着遗传算法的性能和求解的效率。编码方法有二进制编码、十进制编码、序号编码和符号编号等。布局遗传算法算例都采用十进制编码。

②

适应度函数适应度是度量种群个体在优化计算中可能达到或接近于找到最优解的程度。度量种群个体适应度的函数则称为适应度函数。一般要求适应度函数f(x)>0。适应度大的种群个体遗传到下一代的概率就越大，适应度小的种群个体遗传到下一代的概率就越小。2023/2/6湘潭大学信息工程学院③

遗传算子遗传算子包括选择算子、交叉算子和变异算子。选择是为了避免有效基因损失，使性能较优的个体得以更高的概率生存，从而加快收敛速度和提高计算效率。选择算子有比例选择、排序选择、最优保存、确定式采样选择、期望值选择、无回放余数随机选择和随机联赛选择。比例选择算子是以正比于个体适应度的概率来选择个体，而排序选择算子是按适应度大小顺序对群体中的所有个体进行排序，然后把事先计算好的概率表依次分配给每个个体作为各自的选择概率。其中最常用的是比例选择和排序选择，本文遗传算法算例采用最优保存策略，因为根据标准遗传算法的收敛性可知：使用最优保存策略可使遗传算法收敛于最优解的概率为1。2023/2/6湘潭大学信息工程学院交叉是在种群中的两个个体进行。通过交叉产生新的个体，以致遗传算法能在解空间中进行有效的搜索，同时降低对有效模式的破坏概率。常用的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉和算术交叉。本文遗传算法算例都采用两点交叉。变异是个体中某些基因位上的基因值加以改变。种群个体通过变异产生新的个体，常用的变异算子有基本变异、均匀变异、非均匀变异和高斯变异等。变异算子在遗传算法中的作用是使形遗传算法具有局部搜索能力和维持群体的多样性，防止出现未成熟收敛现象。2023/2/6湘潭大学信息工程学院(3)基本遗传算法的几个参数设定

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

③交叉概率遗传算法通过交叉产生新的个体，因此，交叉概率不能取得太小，也不能取得过大，若取得过大，会破坏群体中的优良模式，对进化计算产生不利的影响；若取得过小，则产生新的个体的速度较慢。一般交叉概率取值在0.4~0.99之间。

④变异概率变异概率直接决定产生新的个体的多少。变异概率越大，由于产生新的个体就越多，增加了群体的多样性，但也破坏更多优良的个体，使遗传算法的性能接近于随机搜索算法；变异概率取得过小，则产生新的个体和抑制早熟现象的能力都会较差。一般变异概率取值在0.05~0.4之间。2023/2/6湘潭大学信息工程学院

⑤终止代数终止代数T是遗传算法运行终止的一个主要参数，它表示遗传算法运行到指定代数就终止。这时，群体中的最优个体被作为所求问题的最优解输出。一般终止代数取值在100~20000之间。这里需要说明的是遗传算法还可以使用别的终止条件来终止运行，如群体中所有个体适应度的方差均小于某一较小的阀值。

2023/2/6湘潭大学信息工程学院(4)约束条件的处理由于求解的优化问题都带有一定的约束条件，因此，应用遗传算法求解时都必须对约束条件进行处理。一般的处理方法有搜索空间限定法、可行解变换法和罚函数法。

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

(2)

(3)

2023/2/6湘潭大学信息工程学院问题1该问题是一个带静平衡性能约束，且有等价待布物的约束布局优化问题。圆容器的半径R＝70mm，待布物为6个圆盘，它们的半径r1~r6分别为16.5、16.5、16.5、12.0、20.0和24.5mm，设静不平衡量J的允许值为δJ，每个圆盘的质量mi＝ri2(g)。要求给出满足不干涉、静平衡约束条件下，各待布物向容器中心高度聚集的布局方案。以容器中心为原点，向右且与容器和圆盘的表面重合的射线为x正半轴建立直角坐标系。不计圆盘的厚度，其布局优化模型如下：求X＝(xi,yi)，i=1,2,…,n使minf(X)=max{(xi2+yi2)½+ri

}s.tg1(X)=(xi2+yi2)½–(R–ri)≤0g2(X)=ri

+rj

–((xi–xj)2+(yi–yj)2)½≤0g3(X)=((m1x1+…

+mnxn

)2+(m1y1+…

+mnyn

)2)½-δJ

≤02023/2/6湘潭大学信息工程学院给出初始点X0，如图1.18(a)所示，其中待布物OBJ1和OBJ2的形心重合。对应局部最优解的目标函数＝63.976mm，向量函数＝89.903，用文献的方法和准边界直线法分别构造15个同构和15个非同构初始点，并采取罚函数法求出布局最优解。表1.1是采用的两种算法的计算结果比较，表中R为外包络圆半径，J为静平衡量，t为计算时间。两种方法的最优布局方案如图1.18(b)和(c)所示。

(a)

(b)

(c)

图1.18问题1的两种布局方案

2023/2/6湘潭大学信息工程学院表1.1问题1的计算结果比较

2023/2/6湘潭大学信息工程学院问题2印刷电路板设计问题，它是一个要求待布物满足一定邻接关系的布局问题，在二维空间放置15个待布物，待布物间的权值Wij(表示待布物在位置空间上的亲密度)，要求待布物摆放时满足下述条件：(1)待布物之间不干涉，(2)具有较大权重值的待布物应相互聚集。即C＝的数值最小，其中dij为两待布物之间的距离，(3)待布物的外包络矩形面积最小。数学模型如下：式中S表示外包络矩形的面积，λ为C相对于S的权重，

Ai和Aj分别待布物i和j

的面积，待布物间的权重矩阵如式(4)所示，半径分别为12,3,12,3,9,10,7,8,4,12,6,10,9,9,10。2023/2/6湘潭大学信息工程学院(4)

2023/2/6湘潭大学信息工程学院(a)

PHAIA(b)H

CIGA(C)

HDCLDM(a)

CBRHGA图

1.19问题2的4种布局方案2023/2/6湘潭大学信息工程学院表1.2问题2的4种计算结果比较

2023/2/6湘潭大学信息工程学院表1.3问题2的4种布局方案的性能指标

从表1.2和表1.3来看，CBRHGA的计算效率比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/2/6湘潭大学信息工程学院问题3图1.20

(b)是一种棱台型卫星的简化模型，舱体用厚度均匀的壳体制成一回转体，空腔用于各仪器的布局空间；腔体中的底部承载板基面用以安装各仪器，除此以外的地方均不能安装任何仪器；承载板的厚度均匀，基面与旋转体轴线垂直。图1.20(a)是7.10(b)的二维平面布局图。

图1.20卫星舱布局设计问题2023/2/6湘潭大学信息工程学院以旋转轴为z轴，以承载板中心为原点建立直角坐标系如图1.21(a)，卫星舱及部件在xoz坐标平面上的正投影图如图1.21(b)，其中，

Rt、R0和Ht分别是圆台上、下底面圆半径和圆台的高度，T是承载板厚度。给定一组待安装的仪器(待布物)，每个待布物的几何尺寸、质量、质心位置均已知，布局完毕后整个舱体和保仪器以固定的角速度ω转动，要求布局满足如下条件：

图1.21卫星舱的三维图和xoz平面的投影图2023/2/6湘潭大学信息工程学院(1)各仪器不得发生干涉，即互不重叠(实际工程中保证不小于规定的充许空间距离)；(2)各仪器的任何部分不得超出给定的布局空间，即不得与舱体发生干涉；(3)

各仪器尽可能地布局在舱体中心轴(z轴)附近，即各仪器的外包络圆半径应尽量小，提高空间利用率；(4)

在满足上述各项要求的前提下，应使系统绕舱体中心轴(z轴)转动时产生的动不平衡量和质心偏移量都小于充许值，并且尽量小。根据上述条件和图1.21的结构，设舱内待布物中，固定位置长方体数为N1，固定位置圆柱体数为N2，可自由布局位置长方体数为N3，可自由布局位置圆柱体数为N4，N＝N1＋N2＋N3＋N4。建立数学优化模型的表达式如式(5)和(6)所示。

2023/2/6湘潭大学信息工程学院求：Xi＝(xi,yi,αi)T，i∈In＝{1,2,…,N}

(5)

minf(X)=λ1F＋λ2M

(6)

其中：(xi,yi)T∈R

2，xi,yi分别为各待布物质心的x,y坐标，设待布物为刚体，待布物的质心与形重合，αi表示长方体正投影矩形的转角，它是以x正半轴为始边，矩形的长边或其延长线为终边所成的角(αi∈[0,π])。F为舱体的动不平衡力，M为舱体的质心偏移量，其值由式(7)和(8)计算。

其中：mi为待布物i的质量，ω为卫星舱旋转的角速度，hi为待布物i的质心高度。

(7)

(8)

2023/2/6湘潭大学信息工程学院s.tintOBJi∩intOBJj=Ф

i,j∈In＝{1,2,…,N},i≠j

R*=min{(xi2+yi2)½+ri}其中：R*为各待布物的外包络圆。结束准则为式(9)和(10)。

(9)

(10)

其中：[εj]和[εm]分别为舱体的动不平衡力和舱体的质心偏移量的充许值。如图1.21(b)所示的卫星舱模型，舱旋转的角速度为40r/min，Rt＝750mm，Ht＝800mm，T＝20mm。要在承载板上放置10个待布物，要求所有待布物尽量向中心2023/2/6湘潭大学信息工程学院集中。其中固定位置长方体数为N1＝0，固定位置圆柱数为N,2＝1，可自由布局位置长方体数为N3＝5，可自由布局位置圆柱体数为N4＝4，舱体的动不平衡力的充许值[εj]＝20N，舱体的质心偏移量的充许值[εm]＝10N.mm，其它初始数据见表1.4，建立式(5)～(10)的数学模型。

表1.4问题3的待布物的初始数据

2023/2/6湘潭大学信息工程学院表1.5问题2的4种布局方案的性能指标

图

1.22问题3的3种布局方案2023/2/6湘潭大学信息工程学院从表表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.67%，在x方向和y方向上的质心偏移量则分别减少99.43%和98.32%。

表1.6问题3的3种计算结果比较

2023/2/6湘潭大学信息工程学院1.多目标优化问题1.2机器人手臂碰撞检测1.2.1拉格郎日乘子求解优化问题1.2.2机器人手臂的建模1.2.3手臂间最小距离表达1.2.4最小距离的优化计算1.2.5机器人手臂碰撞检测算法2023/2/6湘潭大学信息工程学院1.2.1拉格郎日乘子求解优化问题(1)等式约束非线性优化问题

minf(X)

s.t.gi(X)=0,i=1,2,…,m求解方法：将个方程分别乘以λ1,λ

2,…,λm，然后把它们的和加到目标函数中去得到式(11)。

L＝f(x1,x2,,…,xn)+(11)对上述式()两边求m+n个变量的偏导数得方程组(12)，解方程组(12)得到问题的解。(12)2023/2/6湘潭大学信息工程学院例如：现需设计一个废水沉淀箱(如图1.23)。但限定各个面壁加底板的总面积不得超过288m2

，应如何设计尺寸使沉淀箱的容积最大。

解：它的目标函数是：maxV=xyz

约束条件是S＝3yz＋xy＋2xz＝288m2

即约束优化问题：maxV=xyzs.t.3yz＋xy＋2xz-288=0

L=xyz-λ(3yz＋xy＋2xz-288)，两边对4个变量求偏导得式(13)

解方程组(13)得x:y:z=3:2:1,从而x=12m，y=8m，z=4m。(13)图1.23废水沉淀箱2023/2/6湘潭大学信息工程学院(2)不等式约束非线性优化问题

minf(X)

s.t.gi(X)≤0,i=1,2,…,m

求解方法：将不等式约束转化为等式约束，则得到：

minf(X)

s.t.gi(X)＋zi2=0,i=1,2,…,m例如：求minf(X)＝2x12-2x1x2＋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

＝02023/2/6湘潭大学信息工程学院引进拉格朗日函数

L＝f(x1,x2,x3,x4)-=(2x12-2x1x2＋2x22-6x1)-λ1(3x1＋4x2-6＋x32)–λ2(-x1＋4x2-

2＋x42)(14)对上述式(14)两边求6个变量的偏导数得方程组，解方程组(14)得到问题的解。但其求解是比较繁重的。2023/2/6湘潭大学信息工程学院(3)用库恩－塔克条件求解约束非线性优化问题

minf(X)

s.t.gi(X)≤0,i=1,2,…,m

求解方法：若X*是问题(15)的极小值点，而且在X*点的各起作用约束的梯度线性无关，则存在向量Γ*＝(γ1*,γ2*,…,γl

*)T使得式(16)成立。(15)(16)条件(16)称为简称为K-T条件，满足这个条件的点(当然它也满足非线性优化问题的所有约束条件)称为库恩-塔克点或称为K-T点。γ1*,γ2*,…,γl

*为拉格朗日乘子。2023/2/6湘潭大学信息工程学院对于约束非线性优化问题

minf(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*,…,λ*m和γ1*,γ2*,…,γl

*称为广义拉格朗日乘子。(17)2023/2/6湘潭大学信息工程学院例如：用库恩－塔克条件求解约束非线性优化问题

minf(X)＝(x-3)20≤

x

≤5

解：将问题改写成：

minf(X)＝(x-3)2

g1(x)=x≥

0

g2(X)=5-x≥0

目标函数和约束函数的梯度分别为:

▽f(x)＝2(x-3)，▽g1(x)＝1，▽g2(x)＝-1设x*为K-T点，引入广义拉格朗日乘子γ1*

和γ2*

则该问题的K-T点条件为式(18)。2023/2/6湘潭大学信息工程学院(18)

对于方程组(18)，考虑如下情形：(1)γ1*

≠0，γ2*

≠0，此时优化问题无解；(2)γ1*

≠0，γ2*

＝0，解之得x*＝0，γ1*

＝－6，但它们不是K-T点，故不是优化问题的解；(3)γ1*＝0，γ2*

≠0，解之得x*＝5，γ2*

＝－4，但它们不是K-T点，故不是优化问题的解；(4)γ1*＝0，γ2*

＝0，解之得x*＝3，它是K-T点，目标函数值f(x*)=0。

因此，本优化问题的解为x*＝3。2023/2/6湘潭大学信息工程学院1.2.2机器人手臂建模机器人和障碍可以用圆柱体、长方体、球和球台的组合、多面体建模，而对于多机器人系统而言，使用这种建模会使计算量大大增加。为了兼顾精确度和计算量，机器人手臂的每个连杆用两端带半球的圆柱建模，而手腕、手爪以及被抓物体由一个球体建模，如图1.24所示。这样，虽然会使机器人的实际体积有所增加，但是却减少了计算的复杂性。图1.24机器人臂简化图2023/2/6湘潭大学信息工程学院1.2.3

最小距离计算以线段为例计算2连杆之间的距离,设空间任意线段AB、CD的4个端点分别为，，。令则，，则由式(14)为：线段AB、CD任意两点间距离的平方可以用式(15)表示。(14)其中a,b,c,d,e,f是常数，它与线段AB、CD的4个端点坐标有关。dAB的最小值就是两线段间的最小距离。(15)2023/2/6湘潭大学信息工程学院1.2.4最小距离的优化计算下面采用Lagrange乘子和Kuhn-Tucker条件求dAB的最小值。记式(15)为：并且将0≤

x1≤1

,0≤

x2≤1改为下面不等式约束条件：引入松驰变量Sj，j=1,2,3,4将不等式约束转化为等式约束：2023/2/6湘潭大学信息工程学院构造lagrange函数式中λ为lagrange乘子。而含有不等式约束的Kuhn-Tucker条件可以表示为：结合2连杆之间的几何性质，共有9中情况需要考虑，如2023/2/6湘潭大学信息工程学院图1.25所示。通过不同情况的组合可以分别求出在f(x1,

x2)为最小时x1,

x2的取值。图1.25连杆距离的9种情况2023/2/6湘潭大学信息工程学院2023/2/6湘潭大学信息工程学院

最小距离就是9种不同情况下f(x1,

x2)的最小值。最后，将求得的最小距离与模型中两圆柱体的半径之和进行比较，以判断机器人手臂在运动过程中是否存在潜在的碰撞。2023/2/6湘潭大学信息工程学院2.偏微分方程数值解2.1抛物型方程的差分方法其中φ

(x),μ1(t),μ2(t)都是已知的连续函数，并且满足相容性条件：φ

(0)＝μ1(0)，φ

(l)＝μ2(0)。该模型用于研究热传导和热扩散问题，如铸件凝固过程中温度场模拟。(1)(1)热传导方程的第一边值问题如式(1)所示。2023/2/6湘潭大学信息工程学院

为了用有限差分方法求解式(1)，我们将求解区域G：0<x<l，0<t<T。用二族平行于坐标轴的直线分割成矩形网格Gh,τ如图2.1所示。两直线分别是：

x＝xj

＝jh,

j=1,2,…,N

t＝tn

＝nτ,

n=1,2,…,J其中h＝l/N，τ＝T/J分别为x方向和时间t方向的步长，交点(xj,tn)称为节点，(xj＋½,tn＋½

)称为分节点。图2.1求解网格区域2023/2/6湘潭大学信息工程学院为了用有限差分方法求解式(1)，我们将求解区域G：0<x<l，0<t<T。用二族平行于坐标轴的直线分割成矩形网格Gh,τ如图2.1所示。两直线分别是：

x＝xj

＝jh,

j=1,2,…,N

t＝tn

＝nτ,

n=1,2,…,J其中h＝l/N，τ＝T/J分别为x方向和时间t方向的步长，交点(xj,tn)称为节点。另外，我们有时还用到分节点(xj＋½,tn＋½

)，这里，xj＋½＝xj+h/2，tn＋½

＝

tn+τ/2

。

t＝tn上的全体节点{(xj,tn)|j=0,2,…,N}称为差分网格的第n层。2023/2/6湘潭大学信息工程学院显式差分格式假定边值问题式(1)的解u(x,t

)有足够的光滑性，用Ujn,分别表示边值问题式(1)的解u(x,t

)及其导数在节点处的值，上标n表示第n层，不表示n次方。由泰勒展开公式有式(2)成立。(2)由式(2)可得到式(3)(3)2023/2/6湘潭大学信息工程学院由泰勒展开公式有式(4)和式(5)成立。(4)(5)由式(4)和式(5)可得到式(6)。(6)2023/2/6湘潭大学信息工程学院将式(3)和式(6)代入式(1)并舍去误差项可得到式(7)。(7)式(7)的差分方程的逼近误差为O(τ+h2)，称此逼近关于τ是一阶的，关于h是2阶的。对初始条件和边界条件作相应逼近逼近，如式(8)。(8)式(7)和式(8)构成边值问题式(1)的显式差分格式。2023/2/6湘潭大学信息工程学院由式(7)和式(8)可得到差分方程的解式(9)。(9)其中。由式(9)可知：第n+1层任意一个内节点处的值Ujn＋1可以由第n层的3个相邻节点处的值Uj-1n,

Ujn,

Uj+1n决定。由于式(9)的右边不含Ujn＋1，故称之为显示格式。隐式差分格式由泰勒展开公式可得式(10)和式(11)。(10)2023/2/6湘潭大学信息工程学院(11)由式(10)和式(11)可得到式(12)。将式(3)和式(12)代入式(1)并舍去误差项可得到式(13)。(12)(13)2023/2/6湘潭大学信息工程学院式(13)和式(8)构成边值问题式(1)的隐式差分格式(14)。(14)式(14)是关于第n+1层上内节点处的值U1n＋1,U2n＋1,…,UN-1n＋1的线性方程组。我们可以用追赶法或迭代法解此方程组求第n+1层上的值。由于不能直接解出Ujn＋1，故式(14)称之为隐式格式。2023/2/6湘潭大学信息工程学院六点对称格式式(7)两边乘以(1-θ)得到式(15)。(15)式(14)两边乘以θ得到式(16)。(16)式(15)+式(16)得到式(17)。(17)式(17)用到相邻两层六个点处的函数值，故称为六点格式。2023/2/6湘潭大学信息工程学院当θ＝1/2时，式(17)被简化为式(18)，它称为六点对称格式。它可以看作对点(xj,tn＋½

)作中心差商的结果。由于(18)因此格式(18)的截断误差为O(τ2+h2)，即对的逼近阶提高了一次。由后面的证明可知：该格式是无条件稳定的。2023/2/6湘潭大学信息工程学院式(18)和式(8)构成边值问题式(1)的六点对称差分格式(19)。其中：式(19

)对n=0,1,2,…,J可逐次用追赶法求解。(19)2023/2/6湘潭大学信息工程学院李查逊格式由泰勒展开公式有式(20)和式(21)成立。(20)(21)式(20)-式(21)的差除以2τ可得到式(22)。(22)2023/2/6湘潭大学信息工程学院由泰勒展开公式可得式(23)和式(24)。(23)(24)(25)式(23)+式(24)的和除以h2可得到式(25)。2023/2/6湘潭大学信息工程学院将式(22)和式(25)代入(1)得到式(26)，其截断误差为O(τ2

+h2)

。(26)