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

研究生课程：研究生课程：研究生课程：研究生课程：问题的数学模型与方法问题的数学模型与方法 (2011年上学期) 授课：黎自强( (教授教授) )2024/9/172024/9/17主要内容：1. 目标函数优化问题　 1.1 遗传算法求解复杂布局问题　 1.2 拉格郎日算子求解圆柱体碰撞检测问题2. 偏微分方程数值求解　 2.1 铸件凝固过程的温度场模拟2024/9/172024/9/171. 1. 目标函数优化问题目标函数优化问题1.1.1 1.1.1 工程背景和科学问题的提出工程背景和科学问题的提出 1.1.2 1.1.2 布局优化问题研究进展布局优化问题研究进展 1.1.3 1.1.3 航天器布局方案设计研究进展航天器布局方案设计研究进展 1.1.4 1.1.4 用遗传算法求解布局问题用遗传算法求解布局问题1.1 1.1 复杂布局问题复杂布局问题2024/9/172024/9/171.1.1 1.1.1 工程背景和科学问题的提出工程背景和科学问题的提出 a) 发达国家航天器发展现状                      美国与欧洲空间局自美国与欧洲空间局自8080年代起，致力于用计算机技术年代起，致力于用计算机技术解决航天器舱的待布物总体布局问题的研究，其关键理论、解决航天器舱的待布物总体布局问题的研究，其关键理论、方法、技术至今仍处于保密状态。

近年来有用协同优化法方法、技术至今仍处于保密状态近年来有用协同优化法设计航天器的保护装置和得到设计航天器的保护装置和得到NASANASA资助的用遗传算法进资助的用遗传算法进行航天器的设计，但很少涉及布局设计的内容根据我国行航天器的设计，但很少涉及布局设计的内容根据我国人员出国考察获悉，以卫星布局设计为例，目前美国设计人员出国考察获悉，以卫星布局设计为例，目前美国设计效率比我国快效率比我国快2020倍以上，但是其性能和空间利用率对比不倍以上，但是其性能和空间利用率对比不详2024/9/172024/9/17b) 国内航天器发展现状 我国航天器设计多以人工设计为主，参考样我国航天器设计多以人工设计为主，参考样图或资料，用计算机辅助绘图（二、三维），然图或资料，用计算机辅助绘图（二、三维），然后用国外软件进行三维造型模装，再用国外软件后用国外软件进行三维造型模装，再用国外软件进行三维动力学验算若不合适，用人工修改设进行三维动力学验算若不合适，用人工修改设计，最后建造计，最后建造1:11:1实物模型，进行实验验证实物模型，进行实验验证2024/9/172024/9/17c) 人工设计存在的问题：v 性能不易保证或非优化；性能不易保证或非优化；v 空间利用率低；空间利用率低；v 设计成本高；设计成本高；v 设计周期长。

设计周期长 过去卫星曾因总体布局不当，动不平衡过大，过去卫星曾因总体布局不当，动不平衡过大，曾造成过早报废的恶果况且我国还要研制更复曾造成过早报废的恶果况且我国还要研制更复杂的空间站，其布局设计尤为重要杂的空间站，其布局设计尤为重要 2024/9/172024/9/17d) 科学问题的提出 从理论上说，航天器布局设计，可归结出从理论上说，航天器布局设计，可归结出““可数学模型化可数学模型化””和和““不可或难数学模型化不可或难数学模型化””两类两类问题前者属很难的带性能约束的三维布局优化问题前者属很难的带性能约束的三维布局优化问题；后者多属工程复杂系统问题，涉及人脑思问题；后者多属工程复杂系统问题，涉及人脑思维模型问题，解决方法有二种：维模型问题，解决方法有二种：v 一是人工智能，基于智能的知识模型及其推理；一是人工智能，基于智能的知识模型及其推理；v 二是人机结合二是人机结合( (Man-Machine Synergy)Man-Machine Synergy)或人机合作或人机合作( (Human-Computer Cooperation)Human-Computer Cooperation)。

航天器布局设计属交叉学科前沿课题的基础航天器布局设计属交叉学科前沿课题的基础理论和应用基础研究，具有重要的科学意义理论和应用基础研究，具有重要的科学意义 2024/9/172024/9/171.1.2 1.1.2 布局优化问题研究进展布局优化问题研究进展 布局问题(Layout Problem)属于复杂的组合优化问题，即使最简单的一维布局也属于NPC问题自1831年高斯(Gauss)研究布局问题开始，虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法从理论上讲，布局问题可分为切段(Cutting-Stock)问题和装填(Packing)问题2024/9/172024/9/17按照布局物体的布局维数分类按照布局物体的布局维数分类a) 一维布局问题 b) 二维布局问题 c) 三维布局问题 2024/9/172024/9/17 a) a) 一维布局问题一维布局问题 一维布局问题中典型的例子是在给定长度的棒料一维布局问题中典型的例子是在给定长度的棒料上，切割长度不等的若干短棒，此类问题通常称上，切割长度不等的若干短棒，此类问题通常称为切段问题为切段问题( (Cutting-Stock Problem)Cutting-Stock Problem)。

解决方法：解决方法：FaggioliFaggioli [5] [5]利用启发式算法提出了切段排序问题利用启发式算法提出了切段排序问题的数学模型和一个三步解法；的数学模型和一个三步解法； Vasko Vasko [6][6]和和NitscheNitsche [7] [7] 分别利用树搜索算法和松分别利用树搜索算法和松弛算法来解决一维切段问题；弛算法来解决一维切段问题；Petridis VassiliosPetridis Vassilios等等[8][8]利用遗传算法以动态的利用遗传算法以动态的方式把问题的约束合并到适应度函数中方式把问题的约束合并到适应度函数中2024/9/172024/9/17b) b) 二维布局问题二维布局问题 二维布局问题包括：二维布局问题包括：一刀切问题一刀切问题 将某些不同大小的小矩形按照一刀切的原则排放在一个大将某些不同大小的小矩形按照一刀切的原则排放在一个大矩形板材上，使面积浪费最小，这是剪床落料、玻璃切割、矩形板材上，使面积浪费最小，这是剪床落料、玻璃切割、纸张切割中遇到的主要问题所谓一刀切，是指切割总是纸张切割中遇到的主要问题所谓一刀切，是指切割总是从矩形板材的一边开始一直切到其对边，即每切一刀都将从矩形板材的一边开始一直切到其对边，即每切一刀都将一个矩形分割成两个小矩形一个矩形分割成两个小矩形 底盘装载问题底盘装载问题       底盘装载问题来源于运输、搬运中的货物摆放或装箱。

将底盘装载问题来源于运输、搬运中的货物摆放或装箱将多个相同大小的立体箱子放入一立方体容器中，且要求放多个相同大小的立体箱子放入一立方体容器中，且要求放入的箱子越多越好入的箱子越多越好2024/9/172024/9/17矩形布局问题矩形布局问题( (Rectangle Packing Problems)Rectangle Packing Problems)                           矩形布局问题是将许多大小不同的二维矩形布置在一矩形布局问题是将许多大小不同的二维矩形布置在一个大的矩形中，使面积覆盖率最大，这是大规模集成电路个大的矩形中，使面积覆盖率最大，这是大规模集成电路设计中所碰到的主要问题设计中所碰到的主要问题圆布局问题圆布局问题( (Circle Packing Problems)Circle Packing Problems) 圆布局问题是将许多大小相同或不同的圆布置在一个圆布局问题是将许多大小相同或不同的圆布置在一个大的圆形、三角形或矩形容器中，使面积覆盖率最大大的圆形、三角形或矩形容器中，使面积覆盖率最大[39][39]这类问题大量地存在于几何、化学、生物学、工程和优化这类问题大量地存在于几何、化学、生物学、工程和优化中，已经引起人们的很大关注中，已经引起人们的很大关注[40][40]。

通常不等圆装填问题还需满足一定的性能约束条件，通常不等圆装填问题还需满足一定的性能约束条件，譬如：惯性、平衡性、和稳定性约束等，我们把这种问题譬如：惯性、平衡性、和稳定性约束等，我们把这种问题称为带性能约束的不等圆装填问题称为带性能约束的不等圆装填问题2024/9/172024/9/17二维不规则图形布局问题二维不规则图形布局问题(2-(2-D Irregular D Irregular Graph Layout Problems)Graph Layout Problems) 二维不规则图形布局问题是指将许多任意形二维不规则图形布局问题是指将许多任意形二维不规则图形布局问题是指将许多任意形二维不规则图形布局问题是指将许多任意形状、大小的二维形体布置在一任意形状的二维平状、大小的二维形体布置在一任意形状的二维平状、大小的二维形体布置在一任意形状的二维平状、大小的二维形体布置在一任意形状的二维平面内以使某一性能最优，如板材下料，服装裁剪面内以使某一性能最优，如板材下料，服装裁剪面内以使某一性能最优，如板材下料，服装裁剪面内以使某一性能最优，如板材下料，服装裁剪等。

处理这类问题通常是把不规则图形套排在一等处理这类问题通常是把不规则图形套排在一等处理这类问题通常是把不规则图形套排在一等处理这类问题通常是把不规则图形套排在一些形状比较规则的简单图形中，然后用这些简单些形状比较规则的简单图形中，然后用这些简单些形状比较规则的简单图形中，然后用这些简单些形状比较规则的简单图形中，然后用这些简单的图形在给定的平面内排样，以降低问题的复杂的图形在给定的平面内排样，以降低问题的复杂的图形在给定的平面内排样，以降低问题的复杂的图形在给定的平面内排样，以降低问题的复杂程度 2024/9/172024/9/17三维布局问题三维布局问题 三维布局问题包括：v无性能约束的三维布局问题(3-3-D Layout Problems D Layout Problems with Non-with Non-Behavioral ConstraintsBehavioral Constraints) 无性能约束三维布局问题是指将尽量多的不同形状、尺寸的三维物体放入到一长方体（或圆柱体）容器中，例如背包问题、集装箱问题 v带性能约束的三维布局问题(3-(3-D Layout Problems D Layout Problems with Behavioral with Behavioral Constraints)Constraints) 。

带性能约束三维布局问题是指将任意形状、大小和性能的三维实体摆放在一个任意形状、大小的三维容器中，以满足某些约束或使某些目标最优 2024/9/172024/9/17例子例子Ø 约束约束底盘装载和船舶配载问题底盘装载和船舶配载问题底盘装载和船舶配载问题底盘装载和船舶配载问题 Ø 汽车驾驶舱布局问题汽车驾驶舱布局问题 Ø 集成电路集成电路( (VLSI)VLSI)的布局规划的布局规划 Ø 航天器舱布局方案设计问题航天器舱布局方案设计问题 2024/9/172024/9/17带性能约束布局问题的算法带性能约束布局问题的算法 启发式算法启发式算法( (Heuristic Algorithm)Heuristic Algorithm) v 拟物拟人法拟物拟人法拟物拟人法拟物拟人法 v 拟实验综合启发式算法拟实验综合启发式算法拟实验综合启发式算法拟实验综合启发式算法 v 八叉树结构与定位八叉树结构与定位八叉树结构与定位八叉树结构与定位――定序函数相结合的启发式算法定序函数相结合的启发式算法定序函数相结合的启发式算法定序函数相结合的启发式算法 v GENET GENET模型模型模型模型 v Montreuil Montreuil模型模型模型模型 v 膨胀算法膨胀算法膨胀算法膨胀算法 2024/9/172024/9/17图论图论法法( (Graph Theory)Graph Theory) 图论作为组合数学的重要组成部分，在许多图论作为组合数学的重要组成部分，在许多图论作为组合数学的重要组成部分，在许多图论作为组合数学的重要组成部分，在许多领域有着广泛的应用。

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

布物之间的具体尺寸布物之间的具体尺寸 2024/9/172024/9/17模拟退火算法模拟退火算法模拟退火算法模拟退火算法( ( ( (Simulated Annealing Algorithm)Simulated Annealing Algorithm)Simulated Annealing Algorithm)Simulated Annealing Algorithm) 演化算法演化算法演化算法演化算法( ( ( (Evolutionary Algorithm)Evolutionary Algorithm)Evolutionary Algorithm)Evolutionary Algorithm) 上述四种方法基本上是用数学方法求解数学模型问上述四种方法基本上是用数学方法求解数学模型问题 人工智能人工智能人工智能人工智能( ( ( (包括专家系统包括专家系统包括专家系统包括专家系统)()()()(Artificial Artificial Artificial Artificial Intelligence including Expert System)Intelligence including Expert System)Intelligence including Expert System)Intelligence including Expert System)人人人人机机机机交交交交互互互互、、、、人人人人机机机机结结结结合合合合与与与与人人人人机机机机协协协协同同同同算算算算法法法法( ( ( (Human-Human-Human-Human-Computer Computer Computer Computer Interaction, Interaction, Interaction, Interaction, Combination Combination Combination Combination and and and and Cooperation Algorithm)Cooperation Algorithm)Cooperation Algorithm)Cooperation Algorithm) 2024/9/172024/9/17布局问题评述及其策略和求解算布局问题评述及其策略和求解算法的发展前景法的发展前景 现在的复杂布局研究存在如下问题： vv从布局策略上讲，传统的计算机辅助布局的思路，多从布局策略上讲，传统的计算机辅助布局的思路，多将实际问题化为简化的数学模型用计算机算法求解。

将实际问题化为简化的数学模型用计算机算法求解由于数学模型过于简化，即使能求得结果，但距离解由于数学模型过于简化，即使能求得结果，但距离解决实际问题相差甚远，因为实际的工程影响因素复杂，决实际问题相差甚远，因为实际的工程影响因素复杂，存在不可（或难以）数学模型化的问题；存在不可（或难以）数学模型化的问题； vv从布局问题模型的描述上讲，布局问题的有效、精确从布局问题模型的描述上讲，布局问题的有效、精确表达是解决问题的前提和基础目前多用数学模型，表达是解决问题的前提和基础目前多用数学模型，若模型简单则不能概括必要内容，若模型过于复杂，若模型简单则不能概括必要内容，若模型过于复杂，又无法求解另外，缺乏包含数学、仿真、符号的复又无法求解另外，缺乏包含数学、仿真、符号的复合模型研究，缺乏将工程复杂布局问题从一个复杂工合模型研究，缺乏将工程复杂布局问题从一个复杂工程系统角度去研究；程系统角度去研究； 2024/9/172024/9/17vv从求解方法上讲，复杂的布局问题求解困难在于存在从求解方法上讲，复杂的布局问题求解困难在于存在组合爆炸，如何解决成为关键但由于以往研究人员组合爆炸，如何解决成为关键。

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

布局策略的安排是问题求解的前提或出发点布局策略的表现形式是数学模型，然后采取相应布局策略的表现形式是数学模型，然后采取相应的算法目前带性能约束布局问题中常用的布局的算法目前带性能约束布局问题中常用的布局策略大多数是采用传统的计算机辅助设计的思想，策略大多数是采用传统的计算机辅助设计的思想，即将实际问题简化为单一的数学模型，这种单一即将实际问题简化为单一的数学模型，这种单一的模型往往长于描述问题的某方面的特点，而不的模型往往长于描述问题的某方面的特点，而不善于表达问题的综合属性，也缺少科学有效的布善于表达问题的综合属性，也缺少科学有效的布局方案评价体系；特别是对于复杂的三维问题这局方案评价体系；特别是对于复杂的三维问题这种布局策略的局限性更为突出；因此即使能算出种布局策略的局限性更为突出；因此即使能算出结果，可能与实际问题相差很远结果，可能与实际问题相差很远 2024/9/172024/9/17求解算法的发展前景 航天器舱布局方案设计目前国外（如欧、美）主要航天器舱布局方案设计目前国外（如欧、美）主要有三种方法：一是演化算法；二是虚拟（现实）设计；三有三种方法：一是演化算法；二是虚拟（现实）设计；三是协同设计。

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

束布局算法的发展将会有很大的推动 2024/9/172024/9/171.1.3 航天器布局设计研究进展 航天器（卫星、飞船、空间站）航天器（卫星、飞船、空间站）( (如图如图1.5)1.5)是由有效载荷、是由有效载荷、结构、热控制、姿态与轨道控制、电源、跟踪遥测与遥控、结构、热控制、姿态与轨道控制、电源、跟踪遥测与遥控、数据管理等分系统所组成，分系统又由各自的仪器、设备和数据管理等分系统所组成，分系统又由各自的仪器、设备和部件组成；组件（部件）形式多样、数量繁多；设备与设备部件组成；组件（部件）形式多样、数量繁多；设备与设备之间、分系统与分系统之间有各种不同的机、电、液、气接之间、分系统与分系统之间有各种不同的机、电、液、气接口，并有传动、管线、缆线相连；所以航天器是一个复杂工口，并有传动、管线、缆线相连；所以航天器是一个复杂工程系统程系统[126-128][126-128]其布局方案设计是研究如何充分利用航天器其布局方案设计是研究如何充分利用航天器有限的空间，布置尽可能多的组件和仪器、设备，并满足其有限的空间，布置尽可能多的组件和仪器、设备，并满足其内部和周围环境的各种约束要求的问题内部和周围环境的各种约束要求的问题, ,这是一个多学科交这是一个多学科交叉课题。

叉课题2024/9/172024/9/171.5礼炮号空间站2024/9/172024/9/17航天器总体布局方案设计航天器总体布局方案设计 航天器总体布局方案设计的目的是在选定构型（组件或子系统）基础上将航天器上的仪器设备布置在各舱段的合适位置（如图1.6和1.7）对于载入过程中使用的和需要返回地面的仪器设备应当布置在返回舱，仅在载入前使用的设备可以布置在轨道舱或仪器设备舱，以降低卫星或飞船的结构质量在进行总体布局方案设计之前，要对航天器的功能要求进行分析，选择组件或子系统，然后确定组件或子系统之间的相互位置关系，并使总系统具有一个协调完善的造型；最后从多个布局方案中择优选取航天器的总体布局是全局性的重要问题，不但要考虑到航天器各组件或子系统之间的各种约束，而且还要考虑航天器同各种外部因素（如空间环境）之间的约束，尽量达到功能合理、结构紧凑、层次清晰、比例协调等要求总体上要符合航天器总体设计的要求 2024/9/172024/9/17                                                                  图图1.6 1.6 联盟号飞船联盟号飞船2024/9/172024/9/172024/9/172024/9/172024/9/172024/9/172024/9/172024/9/17航天器舱布局方案设计航天器舱布局方案设计 )，使得布局评价指标达到最优或满足工程结束准则。

它属于带性能约束的三维布局优化问题，具有不确定性、高度非线性、知识不完备性、既需定性计算又需定量分析等特点布局问题的NP-困难性和航天器设计本身的工程系统复杂性使得该问题的解决既存在理论上的开拓性和挑战性，又存在工程实践上的艰难性和复杂性vFerebee 等介绍了一种系统方法（Systematic method）来确定地球轨道卫星上观测设备的优化布局问题 vBraun等将协同优化算法用于单级轨道运载火箭的布局设计v滕弘飞等在文[136]中以返回式卫星舱布局方案设计为背景，提出所谓的转动圆桌平衡摆盘问题，并建立了该问题的数学模型同时提出了模式迭换法、主布模法等方法求解 2024/9/172024/9/17图1.10 联盟号返回舱2024/9/172024/9/17图1.11 返回式卫星2024/9/172024/9/17航天器天线布局方案设计航天器天线布局方案设计 一般说来，航天器天线在电气性能、机械结构、温度控制以及总体布局之间，往往互相矛盾，需统筹兼顾、折衷考虑一系列问题天线布局受航天器结构形状和表面位置所限，但由于天线的功能、工作频率和航天器的轨道姿态，天线又必须放在特定位置；多种天线相互为邻，在电气性能上各种天线又不可互相妨碍；天线同航天器上的突起、伸长物件不应互相干涉；因此，航天器天线的布局相当复杂，直接关系到卫星性能的好坏。

2024/9/172024/9/17图1.12天线结构总体示意图Fig1.12  Diagram  of  antenna  general structurevLinden 等讨论了使用遗传算法求解的卫星结构方面的金属天线的优化布局问题 vCoulomb等以BOPSAT卫星的有效载荷的设计为背景，对移动连接天线的布局进行了探讨比较了几种控制辐射矩阵的组态，分析了其优缺点，最后采用了混合（主动＋被动）组态设计方法进行布局设计vBoissonnat 等介绍了怎样把一些物理布局约束转化为几何模型和怎样利用Minkowski 操作放置某些设备，特别是天线的布局 2024/9/172024/9/17航天器其它组件的布局方案设计航天器其它组件的布局方案设计 航天器帆布局方案设计航天器帆布局方案设计航天器帆布局方案设计航天器帆布局方案设计 航天器稳定平台布局方案设计航天器稳定平台布局方案设计航天器稳定平台布局方案设计航天器稳定平台布局方案设计 航天器姿控发动机布局方案设计航天器姿控发动机布局方案设计航天器姿控发动机布局方案设计航天器姿控发动机布局方案设计 航天器气动外形布局方案设计航天器气动外形布局方案设计航天器气动外形布局方案设计航天器气动外形布局方案设计 航天器复杂插座板插孔布局方案设计航天器复杂插座板插孔布局方案设计航天器复杂插座板插孔布局方案设计航天器复杂插座板插孔布局方案设计 航天器电路板布局方案设计航天器电路板布局方案设计航天器电路板布局方案设计航天器电路板布局方案设计 2024/9/172024/9/17vv太阳帆利用太阳光的压力产生能量，太阳帆利用太阳光的压力产生能量，保证航天器进行太空飞行。

太阳光保证航天器进行太空飞行太阳光子不停地撞击太阳帆，使得太阳帆子不停地撞击太阳帆，使得太阳帆所获得的动量不断增加所获得的动量不断增加 Genta Genta等介绍了一种可以变动的太阳等介绍了一种可以变动的太阳帆的结构布局它是一种可膨胀的帆的结构布局它是一种可膨胀的桁架结构，经过展开以后依旧保持桁架结构，经过展开以后依旧保持压力以缓解所有的压缩力帆的表压力以缓解所有的压缩力帆的表面是一个圆形的薄膜，有效载荷趋面是一个圆形的薄膜，有效载荷趋于薄膜的中心为了计算有效载荷于薄膜的中心为了计算有效载荷距离中心的距离，采用蛛网组态分距离中心的距离，采用蛛网组态分割的方法来解决，用一定数量的圆割的方法来解决，用一定数量的圆形电缆依附在外桁架上以支撑太阳形电缆依附在外桁架上以支撑太阳帆PillowPillow太阳帆结构示意图如图太阳帆结构示意图如图1.131.13所示 图1.13 Pillow太阳帆示意图[13]Fig.1.13 Pillow solar sail[23]外波束有效载荷太阳光2R02024/9/172024/9/17vv空间太阳探测器的标准稳定平台空间太阳探测器的标准稳定平台（（Unified Stabilized PlatformUnified Stabilized Platform，，USPUSP））作用是使面向太阳的各种探测设作用是使面向太阳的各种探测设备稳定地指向太阳。

备稳定地指向太阳 AstafourovAstafourov等介绍了标准稳定平等介绍了标准稳定平台（台（USPUSP））的布局，考虑了平台同科学的布局，考虑了平台同科学设备（分光计和辐射计）之间的不干设备（分光计和辐射计）之间的不干涉性设计控制结构的原则主要是在涉性设计控制结构的原则主要是在考虑有效载荷的外形尺寸和重量的前考虑有效载荷的外形尺寸和重量的前提下，满足提下，满足USPUSP操作的精确性要求建操作的精确性要求建立了一个模块化的系统，可以有效的立了一个模块化的系统，可以有效的处理带有各种载荷的稳定平台，以增处理带有各种载荷的稳定平台，以增加其有效负载，减小项目的花费加其有效负载，减小项目的花费 图1.14 带有稳定平台的空间太阳探测器有效载荷的布局[25]1-分光计；2－辐射计；3－太阳能传感器；4驱动B；5－驱动YFig.1.14    Layout  for    payload  of space  solar  patrol  integrated  with stabilized platform[25]1spectrometer; 2-radiometers; 3-solar sensor; 4 -drives B; 5-drives Y2024/9/172024/9/17vv航天器为了具有良好的稳定性、精航天器为了具有良好的稳定性、精确的速度和姿态控制，动力系统质确的速度和姿态控制，动力系统质量的大小至关重要。

在推进剂及其量的大小至关重要在推进剂及其输送系统选定之后，通过对推力系输送系统选定之后，通过对推力系统的设计变量进行参数分析，即可统的设计变量进行参数分析，即可初步确定满足飞行任务的动力系统初步确定满足飞行任务的动力系统的质量 胡小平，王中伟等在液体推进胡小平，王中伟等在液体推进剂动力系统质量模型的基础上，针剂动力系统质量模型的基础上，针对采用双组元推进剂姿控发动机的对采用双组元推进剂姿控发动机的空间飞行器空间飞行器, ,在总有效冲量和有效在总有效冲量和有效冲量矩一定的条件下冲量矩一定的条件下, ,提出了优选提出了优选动力系统总质量最轻的姿控发动机动力系统总质量最轻的姿控发动机布局方案的一种方法布局方案的一种方法 图1.15 空间飞行器姿态控制发动机布局方案Fig.1.15 Locality arrangement of attitude control engine2024/9/172024/9/17vv所谓的气动优化布局是指优化航天器气所谓的气动优化布局是指优化航天器气动外形，使之满足航天器对升阻比、静动外形，使之满足航天器对升阻比、静稳定度、配平攻角等性能方面的要求。

稳定度、配平攻角等性能方面的要求 潘腾、安复兴讨论了垂直起飞、垂潘腾、安复兴讨论了垂直起飞、垂直降落（直降落（VTVLVTVL））飞行器（一种先进的、飞行器（一种先进的、能重复使用的航天飞行器）的选型和气能重复使用的航天飞行器）的选型和气动优化布局动优化布局对对各参数（如削面角、球各参数（如削面角、球头头半径等）的气半径等）的气动动性能曲性能曲线进线进行分析，行分析，并并综综合考合考虑虑了各参数的相互制了各参数的相互制约约作用，作用，利用利用设计师设计师的的经验给经验给出了气出了气动优动优化布局，化布局，其示意其示意图图如如图图1.161.16所示最后通所示最后通过风过风洞洞实验验证实验验证了布局的正确性了布局的正确性 图1.16 优化气动布局外形及尺寸参数Fig.1.16 Shape and size parameters of aerodynamic layout optimization2024/9/172024/9/17vv航天器复杂插座板插孔布局方案设计航天器复杂插座板插孔布局方案设计航天器复杂插座板插孔布局方案设计航天器复杂插座板插孔布局方案设计 唐飞等研究了航天器中一种能够在火工螺栓作用下自唐飞等研究了航天器中一种能够在火工螺栓作用下自动拔脱的复杂插座板上插孔的布局设计问题，简化为在圆动拔脱的复杂插座板上插孔的布局设计问题，简化为在圆形插板上，根据给定的形插板上，根据给定的n n个插头，考虑电、液、气各种管个插头，考虑电、液、气各种管线插头的插座板（非凸的可布空间）和插头的拔脱力、插线插头的插座板（非凸的可布空间）和插头的拔脱力、插座板的紧固螺栓力、边缘弹簧的弹簧力等约束情况下，布座板的紧固螺栓力、边缘弹簧的弹簧力等约束情况下，布置其插孔位置。

它属于带作用力约束的二维装填置其插孔位置它属于带作用力约束的二维装填 ( (Packing)Packing)问题给出了该问题的数学模型，并用给出的问题给出了该问题的数学模型，并用给出的复数编码的遗传算法进行求解复数编码的遗传算法进行求解[154][154]，提供一个设计参考方，提供一个设计参考方案 2024/9/172024/9/17vv航天器电路板布局方案设计航天器电路板布局方案设计航天器电路板布局方案设计航天器电路板布局方案设计             Hirt            Hirt等介绍了将虚拟样机技术等介绍了将虚拟样机技术（（Virtual Prototyping,VPVirtual Prototyping,VP））应用到航天应用到航天器上含有转换器的电路板的布局设计器上含有转换器的电路板的布局设计将将VPVP作为一种系统化的分析和选择合作为一种系统化的分析和选择合适结构的方法适结构的方法, ,以花费为评价准则，并以花费为评价准则，并行的分析几种可能的方案使用基于行的分析几种可能的方案使用基于JavaCADJavaCAD平台的平台的JavaJava语言完成系统的设语言完成系统的设计。

计图1.17  含有5:4转换器的电路板]Fig. 1.17  PCB containing a 5:4  switch2024/9/172024/9/171.1.4 1.1.4 用遗传算法求解布局问题用遗传算法求解布局问题(1)(1)        基本遗传算法的框架基本遗传算法的框架                        按按照照GoldbergGoldberg提提出出的的框框架架，，基基本本遗遗传传算算法法( (Simple Simple genetic genetic algorithm,SGA)algorithm,SGA)只只包包括括交交叉叉、、变变异异和和选选择择三三种种基基本本遗遗传传算算子，可用式子，可用式(1)(1)所描述的一个所描述的一个8 8元组表示元组表示 SGASGA＝｛＝｛C C, ,E E, ,P P0 0, ,MM, ,ΦΦ, ,Γ Γ, ,Ψ Ψ, ,Τ Τ｝　｝　 (1) (1)               其其中中C C为为个个体体编编码码方方法法，，E E为为个个体体适适应应度度评评价价函函数数，，P P0 0为为初初始始群群体体，，MM为为群群体体规规模模大大小小尺尺寸寸，，ΦΦ为为选选择择算算子子，，ΓΓ为为交叉算子，交叉算子，ΨΨ为变异算子，为变异算子，ΤΤ遗传运算终止条件。

遗传运算终止条件                        2024/9/172024/9/17   基本遗传算法的主要步骤如下：基本遗传算法的主要步骤如下： Step1Step1　　随随机机产产生生P P0 0个个初初始始种种群群，，并并对对每每一一个个种种群群，，求求出适应度函数的值出适应度函数的值 Step2 Step2　　判断最优个体是否满足要求，如果满足则输判断最优个体是否满足要求，如果满足则输出结果后转出结果后转Step6Step6，，否则执行下一步否则执行下一步 Step3Step3　　按交叉概率按交叉概率P Pc c对个体作交叉运算产生新一定量对个体作交叉运算产生新一定量的个体 Step4 Step4　　按变异概率按变异概率P Pm m对个体作交叉运算产生新一定对个体作交叉运算产生新一定量的个体，通过交叉和变异后种群的规模为量的个体，通过交叉和变异后种群的规模为M M Step5 Step5　　对对M M个种群求出其适应度函数的值，按适应度个种群求出其适应度函数的值，按适应度大小选取其中的大小选取其中的P P0 0个种后转个种后转Step2Step2。

Step6 Step6　　算法结束算法结束 2024/9/172024/9/17       (2)        (2) 基本遗传算法的几个重要的概念基本遗传算法的几个重要的概念    ① ① 问题的编码　问题的编码　 将一个问题的解空间转换为遗传算法所能处理的搜索空将一个问题的解空间转换为遗传算法所能处理的搜索空间的方法问题的编码方法直接决定着遗传算法的性能和间的方法问题的编码方法直接决定着遗传算法的性能和求解的效率编码方法有二进制编码、十进制编码、序号求解的效率编码方法有二进制编码、十进制编码、序号编码和符号编号等布局遗传算法算例都采用十进制编码编码和符号编号等布局遗传算法算例都采用十进制编码 ②② 适应度函数　适应度函数　 适应度是度量种群个体在优化计算中可能达到或接近适应度是度量种群个体在优化计算中可能达到或接近于找到最优解的程度度量种群个体适应度的函数则称为于找到最优解的程度度量种群个体适应度的函数则称为适应度函数一般要求适应度函数适应度函数一般要求适应度函数f f( (x x) )>0>0。

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

其其中中最最常常用用的的是是比比例例选选择择和和排排序序选选择择，，本本文文遗遗传传算算法法算算例例采采用用最最优优保保存存策策略略，，因因为为根根据据标标准准遗遗传传算算法法的的收收敛敛性性可可知知：：使使用用最最优优保保存存策策略略可可使使遗遗传传算算法法收收敛敛于于最最优解的概率为优解的概率为1 1 2024/9/172024/9/17                                       交交叉叉是是在在种种群群中中的的两两个个个个体体进进行行通通过过交交叉叉产产生生新新的的个个体体，，以以致致遗遗传传算算法法能能在在解解空空间间中中进进行行有有效效的的搜搜索索，，同同时时降降低低对对有有效效模模式式的的破破坏坏概概率率常常用用的的交交叉叉算算子子有有单单点点交交叉叉、、两两点点交交叉叉、、多多点点交交叉叉、、均均匀匀交交叉叉和和算算术术交交叉叉本本文文遗遗传传算算法算例都采用两点交叉法算例都采用两点交叉 变异是个体中某些基因位上的基因值加以改变种群个变异是个体中某些基因位上的基因值加以改变种群个体通过变异产生新的个体，常用的变异算子有基本变异、体通过变异产生新的个体，常用的变异算子有基本变异、均匀变异、非均匀变异和高斯变异等。

变异算子在遗传算均匀变异、非均匀变异和高斯变异等变异算子在遗传算法中的作用是使形遗传算法具有局部搜索能力和维持群体法中的作用是使形遗传算法具有局部搜索能力和维持群体的多样性，防止出现未成熟收敛现象的多样性，防止出现未成熟收敛现象 2024/9/172024/9/17        (3)        (3)基本遗传算法的几个参数设定基本遗传算法的几个参数设定 基本遗传算法的参数有编码长度、种群规模、交叉概率、变异概率和终止代数         ①　编码长度　         用二进制编码表示个体时，编码的长度l与求解问题的要求精度有关；用实数编码表示个体时，编码的长度l与决策问题的变量个数n相等；用符号编码表示个体时，编码的长度l由问题的编码方式来确定        ②　群体规模　 群体规模M表示群体中个体的数量当M取值较小，能一定程度提高遗传算法的计算速度，但降低了群体的多样性，可能引起遗传算法的早熟现象；当M取值较大，则遗传算法的效率降低一般M的取值在20~100之间 2024/9/172024/9/17               ③③　交叉概率　　交叉概率　                  遗传算法通过交叉产生新的个体，因此，交叉概率不能遗传算法通过交叉产生新的个体，因此，交叉概率不能取得太小，也不能取得过大，若取得过大，会破坏群体中取得太小，也不能取得过大，若取得过大，会破坏群体中的优良模式，对进化计算产生不利的影响；若取得过小，的优良模式，对进化计算产生不利的影响；若取得过小，则产生新的个体的速度较慢。

一般则产生新的个体的速度较慢一般交叉概率取值在之间交叉概率取值在之间                              ④④变异概率　变异概率　 变异概率直接决定产生新的个体的多少变异概率越大，变异概率直接决定产生新的个体的多少变异概率越大，由于产生新的个体就越多，增加了群体的多样性，但也破由于产生新的个体就越多，增加了群体的多样性，但也破坏更多优良的个体，使遗传算法的性能接近于随机搜索算坏更多优良的个体，使遗传算法的性能接近于随机搜索算法；变异概率取得过小，则产生新的个体和抑制早熟现象法；变异概率取得过小，则产生新的个体和抑制早熟现象的能力都会较差的能力都会较差一般一般变异概率取值在变异概率取值在0.05~0.40.05~0.4之间 2024/9/172024/9/17              ⑤　终止代数　 终止代数T是遗传算法运行终止的一个主要参数，它表示遗传算法运行到指定代数就终止这时，群体中的最优个体被作为所求问题的最优解输出一般终止代数取值在100~20000之间这里需要说明的是遗传算法还可以使用别的终止条件来终止运行，如群体中所有个体适应度的方差均小于某一较小的阀值。

          2024/9/172024/9/17        (4)          (4)  约束条件的处理约束条件的处理 由于求解的优化问题都带有一定的约束条件，因此，应用遗传算法求解时都必须对约束条件进行处理一般的处理方法有搜索空间限定法、可行解变换法和罚函数法  搜索空间限定法的基本思想是对遗传算法的搜索空间的大小加以限制，使搜索空间的表示一个个体的点与解空间中表示一个解的点存在一一对应的关系可行解变换法的基本思想是在由个体基因型到个体表现型的变换中，寻找出一种由个体基因型与个体表现型之间的多对一的变换关系，使进化过程中所产生的个体总能够通过这个变换而转化成解空间中满足约束条件的一个可行解罚函数法的基本思想是对在解空间中无对应可行解的个体，计算其适应行解的个体，计算其适应度时处以一个罚函数，从而降低该个体适应度值，使该个度时处以一个罚函数，从而降低该个体适应度值，使该个2024/9/172024/9/17 体体被被遗遗传传到到下下一一代代群群体体中中的的机机会会减减少少随随着着遗遗传传算算法法的的运运行行，，不不可可行行解解在在解解群群占占的的比比例例总总体体上上越越来来越越少少，，可可行行解解逐逐步步占占住住主主导导地地位位并并逐逐步步趋趋向向最最优优解解。

只只要要罚罚函函数数形形式式得得当当，，一一般般都都可可得得到到好好的的结结果果罚罚函函数数法法是是目目前前最最常常用用的的一一种种方方法法例例如如：：约约束束优优化化问问题题式式(2)(2)加加入入罚罚函函数数可可描描述述为为式式(3)(3)的的形式 其中X＝(x1, x2,…,xn)，n为设计变量的个数，函数G和H为罚函数，λi和λj为惩罚系数 (2) (3) 2024/9/172024/9/17                                    问问题题1 1　　该问问题题是一个带静平衡性能约束，且有等价待布物的约束布局优化问题圆容器的半径R＝70mm，待布物为6 个圆盘，它们的半径r1~r6mm，设静不平衡量J的允许值为δJ，每个圆盘的质量mi＝ri2(g)要求给出满足不干涉、静平衡约束条件下，各待布物向容器中心高度聚集的布局方案 以容器中心为原点，向右且与容器和圆盘的表面重合的射线为x 正半轴建立直角坐标系不计圆盘的厚度，其布局优化模型如下：　求 X＝(xi,yi)，i=1,2,…,n 使 min f(X)=max{( xi2+yi2)½ + ri }　s.t g1(X) = ( xi2+yi2)½ –(R– ri)≤0　g2(X) = ri + rj –(( xi– xj)2+(yi– yj)2)½≤0 g3(X) = ((m1x1+ … + mnxn )2+( m1y1+ … + mnyn )2)½ -δJ ≤02024/9/172024/9/17 给出初始点X0，如图1.18(a)所示，其中待布物OBJ1和OBJ2mm，向量函数＝89.903，用文献的方法和准边界直线法分别构造15个同构和15个非同构初始点，并采取罚函数法求出布局最优解。

表1.1是采用的两种算法的计算结果比较，表中R为外包络圆半径，J为静平衡量，t为计算时间两种方法的最优布局方案如图1.18(b)和(c)所示 　(a) (b) (c) 图1.18　问题1的两种布局方案 2024/9/172024/9/17表表1.11.1　问题　问题1 1的计算结果比较 2024/9/172024/9/17                                    问问题题2 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,102024/9/172024/9/17(4) 2024/9/172024/9/17(a) PHAIA(b)H CIGA(C) HDCLDM(a) CBRHGA图 问题2的4种布局方案2024/9/172024/9/17表表1.21.2　问题　问题2 2的4种计算结果比较 2024/9/172024/9/17表表1.31.3　问题　问题2 2的4种布局方案的性能指标 　　从表和表来看，CBRHGA的计算效率比HDCLDM方法提高了7倍，而包络矩形的面积和权距，CBRHGA比HDCLDM方法分别减少了0.12%和1.17%；CBRHGA的计算效率比PHAIA方法提高了倍，包络矩形的面积和权距，CBRHGA比PHAIA方法分别减少了7.68%和10.72%；CBRHGA的计算效率比HCIGA方法提高了倍，包络矩形的面积 和 权 距 ，C B R H G A比 H C I G A方 法 分 别 减 少 了4.79%和16.79%。

2024/9/172024/9/17问题问题3 3　　图 (b)是一种棱台型卫星的简化模型，舱体用厚度均匀的壳体制成一回转体，空腔用于各仪器的布局空间；腔体中的底部承载板基面用以安装各仪器，除此以外的地方均不能安装任何仪器；承载板的厚度均匀，基面与旋转体轴线垂直图1.20(a)是7.10(b)的二维平面布局图 图1.20　卫星舱布局设计问题2024/9/172024/9/17　　以旋转轴为z轴，以承载板中心为原点建立直角坐标系如图1.21(a)，卫星舱及部件在xoz坐标平面上的正投影图如图1.21(b)，其中， Rt、R0和Ht分别是圆台上、下底面圆半径和圆台的高度，T是承载板厚度给定一组待安装的仪器(待布物)，每个待布物的几何尺寸、质量、质心位置均已知，布局完毕后整个舱体和保仪器以固定的角速度ω转动，要求布局满足如下条件： 图1.21　卫星舱的三维图和xoz平面的投影图2024/9/172024/9/17(1) 各仪器不得发生干涉，即互不重叠(实际工程中保证不小于规定的充许空间距离)；　　(2) 各仪器的任何部分不得超出给定的布局空间，即不得与舱体发生干涉；　　(3)  各仪器尽可能地布局在舱体中心轴(z轴)附近，即各仪器的外包络圆半径应尽量小，提高空间利用率；　　(4)  在满足上述各项要求的前提下，应使系统绕舱体中心轴(z轴)转动时产生的动不平衡量和质心偏移量都小于充许值，并且尽量小。

　　　根据上述条件和图的结构，设舱内待布物中，固定位置长方体数为N1，固定位置圆柱体数为N2，可自由布局位置长方体数为N3，可自由布局位置圆柱体数为N4，N＝N1＋N2＋N3＋N4建立数学优化模型的表达式如式(5)和(6)所示 2024/9/172024/9/17求：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) 2024/9/172024/9/17s.t  int OBJi∩int OBJj=Ф 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个待布物，要求所有待布物尽量向中心2024/9/172024/9/17集中其中固定位置长方体数为N1＝0，固定位置圆柱数为N,2＝1，可自由布局位置长方体数为N3＝5，可自由布局位置圆柱体数为N4＝4，舱体的动不平衡力的充许值[εj]＝20N，舱体的质心偏移量的充许值[εm]＝，其它初始数据见表，建立式(5) ～(10)的数学模型 表表1.41.4　问题　问题3 3的待布物的初始数据 2024/9/172024/9/17表表1.51.5　问题　问题2 2的4种布局方案的性能指标 图 问题3的3种布局方案2024/9/172024/9/17　　从表表和表来看，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.61.6　问题　问题3 3的3种计算结果比较 2024/9/172024/9/171. 1. 多目标优化问题多目标优化问题1.2 1.2 机器人手臂碰撞检测机器人手臂碰撞检测1.2.1 1.2.1 拉格郎日乘子求解优化问题拉格郎日乘子求解优化问题1.2.2 1.2.2 机器人手臂的建模机器人手臂的建模 1.2.3 1.2.3 手臂间最小距离表达手臂间最小距离表达1.2.4 1.2.4 最小距离的优化计算最小距离的优化计算 1.2.5 1.2.5 机器人手臂碰撞检测算法机器人手臂碰撞检测算法2024/9/172024/9/171.2.11.2.1　　拉格郎日乘子求解优化问题(1)  (1)  等式约束非线性优化问题等式约束非线性优化问题                      min min f f( (X X) )                          s s. .t t.  . g gi i( (X X)=0, )=0, i i=1,2,…,=1,2,…,m m　　求解方法：　将个方程分别乘以　　求解方法：　将个方程分别乘以λ λ1 1, ,λ λ   2 2 , … , , … , λ λ m m，，然后然后把它们的和加到目标函数中去得到式把它们的和加到目标函数中去得到式(11)(11)。

　　　　L L＝＝   f f( (x x1 1,  , x x2 2, ,…, , ,…, x xn n)+                                         (11))+                                         (11)对上述式对上述式() ()两边求两边求m+nm+n个变量的偏导数得方程组个变量的偏导数得方程组(12)(12)，解方，解方程程组组(12)(12)得到问题的解得到问题的解12)(12)2024/9/172024/9/17 　　例如：现需设计一个废水沉淀箱(如图1.23)但限定各个面壁加底板的总面积不得超过288m2 ，应如何设计尺寸使沉淀箱的容积最大　解：它的目标函数是：maxV=xyz 约束条件是　S＝3yz＋xy＋2 xz＝288m2　即约束优化问题： maxV=xyz　s.t. 3yz＋xy＋2xz-288=0　　 L= xyz-λ λ( (3yz＋xy＋2xz-288) ) ，两边对4个变量求偏导得式(13)　　　　　　　　　                    解方程组解方程组(13)(13)得得x:y:z=3:2:1 ,x:y:z=3:2:1 ,从而从而x=12x=12m，，y=8y=8m，，z=4z=4m。

13)(13)废水沉淀箱2024/9/172024/9/17(2)  (2)  不等式约束非线性优化问题不等式约束非线性优化问题                      min min f f( (X X) )                          s s. .t t.  . g gi i( (X X)  ) ≤≤ 0,  0, i i=1,2,…,=1,2,…,m m　　　　　　求解方法：　将不等式约束转化为等式约束，则得到：求解方法：　将不等式约束转化为等式约束，则得到： min min f f( (X X) ) s s. .t t. . g gi i( (X X)  ) ＋＋z zi i2= = 0,  0, i i=1,2,…,=1,2,…,m m　　　　        例如：求　例如：求　   min min f f( (X X) )＝＝2 2x x1 12 -2-2x x1 1 x x2 2   ＋＋ 2  2x x2 22 -6 -6x x1 1                                                              s s. .t t. . g g1 1 ( (X X) ) =  = 3 3x x1 1 ＋＋ 4  4x x2 2 -6  -6 ≤≤ 0  0                                                                        g g2 2 ( (X X) ) = - = -x x1 1 ＋＋ 4  4x x2 2 - -   2 2≤≤ 0  0                          解：不等式约束转化为等式约束有：解：不等式约束转化为等式约束有：　　　　　　　　　　　　　　　　　　g g1 1 ( (X X) ) =  = 3 3x x1 1 ＋＋ 4  4x x2 2 -6  -6 ＋＋x x3 32＝＝ 0  0　　　　　　　　　　　　　　　　　　g g2 2 ( (X X) ) = - = -x x1 1 ＋＋ 4  4x x2 2 - -   2  2 ＋＋x x4 42   ＝＝ 0  02024/9/172024/9/17引进拉格朗日函数引进拉格朗日函数　　　　L L＝＝   f f( (x x1 1,  , x x2 2,  , x x3 3,  , x x4 4)-                          )-                                    =  (2          =  (2x x1 12 -2-2x x1 1 x x2 2   ＋＋ 2  2x x2 22 -6 -6x x1 1)  )           -          -λ λ1 1 (3 (3x x1 1 ＋＋ 4  4x x2 2 -6  -6 ＋＋x x3 32) – ) – λ λ2 2 (  (- -x x1 1 ＋＋ 4  4x x2 2 - -   2  2 ＋＋x x4 42 )  )                                                                                (14)                                                                                (14)                     对对上上述述式式(14)(14)两两边边求求6 6个个变变量量的的偏偏导导数数得得方方程程组组，，解方程组解方程组(14)(14)得到问题的解。

但其求解是比较繁重的得到问题的解但其求解是比较繁重的2024/9/172024/9/17(3)  (3)  用库恩－塔克条件求解约束非线性优化问题用库恩－塔克条件求解约束非线性优化问题                      min min f f( (X X) )                          s s. .t t.  . g gi i( (X X)  ) ≤≤ 0,  0, i i=1,2,…,=1,2,…,m m　　　　　　求解方法：　若求解方法：　若X X *是问题是问题(15)(15)的极小值点，而且在的极小值点，而且在X X *点的各起作用约束的梯度线性无关，则存在向量点的各起作用约束的梯度线性无关，则存在向量Γ Γ *＝＝( (γ γ1 1 *   ,  , γ γ2 2 * ,…,  ,…, γ γl l   * )  )T T使得式使得式(16)(16)成立　　成立　　(15)(15)(16)(16)　　　　条条件件(16)(16)称称为为简简称称为为K K- -T T条条件件，，满满足足这这个个条条件件的的点点( (当当然然它它也也满满足足非非线线性性优优化化问问题题的的所所有有约约束束条条件件) )称称为为库库恩恩- -塔克点或称为塔克点或称为K K- -T T点。

点γ γ1 1 *, ,γ γ2 2 *,…,,…,γ γl l   *为拉格朗日乘子为拉格朗日乘子2024/9/172024/9/17　对于约束非线性优化问题　对于约束非线性优化问题       min min f f( (X X) )　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   s s. .t t.   .  h hi i( (X X)  ) = = 0 ,  0 , i i=1,2,…,=1,2,…,m m                        　　　　　　　　　　　　　　　　　　　　　　　　　　　　   g gj j( (X X)  ) ≤≤ 0,  0, j j=1,2,…,=1,2,…,l l　　　　　　求解方法：　若求解方法：　若X X *是问题是问题(15)(15)的极小值点，而且在的极小值点，而且在X X *点的各起作用约束的梯度点的各起作用约束的梯度▽▽h hi i( (X X *)( )(i i=1,2,…,=1,2,…,m m) )和和▽▽g gj j( (X X *)( )(j j ∈∈J J) )   线性无关，则存在向量线性无关，则存在向量∧∧ *＝＝( (λ λ1 1 * ,   , λ λ2 2 * ,…,  ,…, λ λl l   * )  )T T   和和Γ Γ *＝＝( (γ γ1 1 * ,   , γ γ2 2 * ,…,  ,…, γ γl l   * )  )T T使得式使得式(17)(17)成立。

　　成立　　满满足足式式(17)(17)的的点点( (当当然然它它也也满满足足非非线线性性优优化化问问题题的的所所有有约约束束条条件件) )也也称称为为库库恩恩- -塔塔克克点点或或称称为为K K- -T T点点λ λ1 1*, ,λ λ2 2*,…, ,…, λ λ*m m和和γ γ1 1 *, ,γ γ2 2 *,…,,…,γ γl l   *称为广义拉格朗日乘子称为广义拉格朗日乘子17)(17)2024/9/172024/9/17　例如：用库恩－塔克条件求解约束非线性优化问　例如：用库恩－塔克条件求解约束非线性优化问                                 题题       min min f f( (X X) )＝＝( (x x-3) -3) 2　　　　　　　　　　     0      0 ≤≤   x x   ≤≤ 5  5 　　　　　　解：　将问题改写成：解：　将问题改写成：　　　　　　　　　　　　   min min f f( (X X) )＝＝( (x x-3) -3) 2   　　　　　　　　　　　　　　g g1 1( (x x)  ) = =x x≥≥  0  0                        　　　　　　　　g g2 2( (X X) =5-x ) =5-x ≥≥ 0  0                  目标函数和约束函数的梯度分别为目标函数和约束函数的梯度分别为: :　　　　　　 ▽▽f f( (x x) )＝＝ 2( 2(x x-3)-3)，，   ▽▽g g1 1( (x x) )＝＝1  1 ，，   ▽▽g g2 2( (x x) )＝＝-1-1              设设x x *为为K K- -T T点，引入广义拉格朗日乘子点，引入广义拉格朗日乘子γ γ1 1 *   和和γ γ2 2 *   则该问题则该问题的的K K- -T T点条件为式点条件为式(18)(18)。

　　　　2024/9/172024/9/17(18)(18)　　　　对于方程组对于方程组(18)(18)，考虑如下情形：，考虑如下情形：         (1)          (1) γ γ1 1 *   ≠0≠0，，γ γ2 2 *   ≠≠ 0  0，此时优化问题无解；，此时优化问题无解；         (2)          (2) γ γ1 1 *   ≠0≠0，，γ γ2 2 *   ＝＝ 0  0，解之得，解之得x x *   ＝＝0 0，，   γ γ1 1 *   ＝－＝－6 6，　　　，　　　但它们不是但它们不是K K- -T T点，故不是优化问题的解；点，故不是优化问题的解；　　　　(3) (3) γ γ1 1 *   ＝＝0 0，，γ γ2 2 *   ≠≠ 0  0，解之得，解之得x x *   ＝＝5 5，，   γ γ2 2 *   ＝－＝－4 4，　　　　，　　　　但它们不是但它们不是K K- -T T点，故不是优化问题的解；点，故不是优化问题的解；　　　　(4) (4) γ γ1 1 *   ＝＝0 0，，γ γ2 2 *   ＝＝ 0  0，解之得，解之得x x *   ＝＝3 3，它是，它是K K- -T T点，目　　　点，目　　　标函数值标函数值f f ( (x x *)=0 )=0 。

　　　　因此，本优化问题的解为因此，本优化问题的解为x x *   ＝＝3  3 　2024/9/172024/9/171.2.21.2.2　　机器人手臂建模　　　机器人和障碍可以用圆柱体、长方体、球和球台的组合、多面体建模，而对于多机器人系统而言，使用这种建模会使计算量大大增加为了兼顾精确度和计算量，机器人手臂的每个连杆用两端带半球的圆柱建模，而手腕、手爪以及被抓物体由一个球体建模，如图所示这样，虽然会使机器人的实际体积有所增加，但是却减少了计算的复杂性图1.24  机器人臂简化图2024/9/172024/9/17　　最小距离计算　　以线段为例计算2连杆之间的距离, 设空间任意线段AB、CD的4个端点分别为　　　　　　　　　，　　　　　　　　，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　令则 　， 　　 ，则由式(14)为：线段AB、CD任意两点间距离的平方可以用式(15)表示14)其中a,b , c , d , e , f是常数，它与线段AB、CD的4个端点坐标有关 dAB的最小值就是两线段间的最小距离。

15)2024/9/172024/9/171.2.4 1.2.4 最小距离的优化计算下面采用下面采用LagrangeLagrange乘子和乘子和Kuhn-TuckerKuhn-Tucker条件求条件求dAB的最小值的最小值记式(15)为：　　　　　　　　　　　　　　　　　　　并且将0≤ x1≤1 , 0≤ x2 ≤1改为下面不等式约束条件：引入松驰变量Sj，j=1,2,3,4将不等式约束转化为等式约束：2024/9/172024/9/17构造lagrange函数式中λ λ为为lagrange乘子而含有不等式约束的Kuhn-Tucker条件可以表示为：结合2连杆之间的几何性质，共有9中情况需要考虑，如2024/9/172024/9/17图1.25所示通过不同情况的组合可以分别求出在f(x1, x2)为最小时x1, x2 的取值图1.25  连杆距离的9种情况2024/9/172024/9/172024/9/172024/9/17　最小距离就是9种不同情况下f(x1, x2)的最小值最后，将求得的最小距离与模型中两圆柱体的半径之和进行比较，以判断机器人手臂在运动过程中是否存在潜在的碰撞。

2024/9/172024/9/172. 2. 偏微分方程数值解偏微分方程数值解2.1　抛物型方程的差分方法其中φ (x),μ1(t), μ2 (t)都是已知的连续函数，并且满足相容性条件： φ (0)＝μ1 (0)， φ (l)＝μ2 (0)　　该模型用于研究热传导和热扩散问题，如铸件凝固过程中温度场模拟1)(1) 热传导方程的第一边值问题如式(1)所示2024/9/172024/9/17 为了用有限差分方法求解式(1)，我们将求解区域G： 0 < x < l，0

用二族平行于坐标轴的直线分割成矩形网格Gh,τ两直线分别是：　　 x＝ xj ＝ jh,　 j j=1,2,…,=1,2,…,N N 　 t＝tn ＝ nτ,　 n n=1,2,…,=1,2,…,J J其其中中h＝ l/ N N，， τ ＝ T / J J分分别别为为x方方向向和和时时间间t方方向向的的步步长长，，交点交点( (xj ,   , tn) )称为节点称为节点                     另另外外，，我我们们有有时时还还用用到到分分节节点点   ( (xj＋½    ,  , tn ＋½ ) )，，这这里里，，   xj＋½ ＝ xj + +h /2 /2，，   tn ＋½ ＝ tn + +τ /2 /2 　　　　   t   ＝＝   tn上上的的全全体体节节点点   {  { ( (xj,  , tn)| )|j j=0,2,…,=0,2,…,N N } }称称为为差差分分网网格的第格的第n层2024/9/172024/9/17显显式式差差分分格格式式　假定边值问题式(1)的解u( (x, ,t ) )有足够的光滑性，用Ujn,  ,                                  　　　　分分别别表表示示边边值值问问题题式(1)的解u( (x, ,t ) )及及其其导导数数　　　　　　　　　　　　在节点处的值，上标n表示第n层，不表示n次方。

由泰勒展开公式有式(2)成立2)由式(2)可得到式(3)(3)2024/9/172024/9/17由泰勒展开公式有式(4)和式(5)成立4)(5)由式(4)和式(5)可得到式(6)6)2024/9/172024/9/17将式(3)和式(6)代入式(1)并舍去误差项可得到式(7)7)式(7)的差分方程的逼近误差为O(τ +h 2)，称此逼近关于τ是一阶的，关于h是2阶的对初始条件和边界条件作相应逼近逼近，如式(8)8)式(7)和式(8)构成边值问题式(1)的显式差分格式2024/9/172024/9/17由式(7)和式(8) 可得到差分方程的解式(9)9)其中　　　由式(9)可知：第n+1层任意一个内节点处的值Ujn＋1可以由第n层的3个相邻节点处的值Uj-1n, Ujn, Uj+1n决定由于式(9)的右边不含Ujn＋1，故称之为显示格式隐隐式式差差分分格格式式　　由泰勒展开公式可得式(10)和式(11)10)2024/9/172024/9/17(11)由式(10)和式(11)可得到式(12)将式(3)和式(12)代入式(1)并舍去误差项可得到式(13)12)(13)2024/9/172024/9/17式(13)和式(8)构成边值问题式(1)的隐式差分格式(14)。

14) 式(14)是关于第n+1层上内节点处的值U1n＋1, U2n＋1, …,…,UN-1n＋1的线性方程组我们可以用追赶法或迭代法解此方程组求第n+1层上的值由于不能直接解出Ujn＋1，故式(14)称之为隐式格式2024/9/172024/9/17六点对称格式　六点对称格式　式(7)两边乘以(1-θ)得到式(15)15)式(14)两边乘以θ得到式(16)16)式(15)+式(16)得到式(17) 17)式(17)用到相邻两层六个点处的函数值，故称为六点格式 2024/9/172024/9/17当θ＝1/2时，式(17)被简化为式(18)，它称为六点对称格式它可以看作对点( (xj, ,tn＋½ ) )作中心差商的结果由于(18)因此格式(18)的截断误差为O(τ2+h2) ，即对的逼近阶提高了一次由后面的证明可知：该格式是无条件稳定的2024/9/172024/9/17　　式(18)和式(8)构成边值问题式(1)的六点对称差分格式(19)其中：　　　式( (19 ) )对对n n=0,1,2,…,=0,1,2,…,J J可逐次用追赶法求解19)2024/9/172024/9/17李查逊格式　李查逊格式　由泰勒展开公式有式(20)和式(21)成立。

20)(21)式(20)-式(21)的差 除以2τ可得到式(22)22)2024/9/172024/9/17由泰勒展开公式可得式(23)和式(24)23)(24)(25)式(23)+式(24)的和除以h2可得到式(25)2024/9/172024/9/17将式(22)和式(25)代入(1)得到式(26)，其截断误差为O(τ 2 +h 2) 26)(27)式(27)称为李查孙格式 前3种格式只要知道第n层上的已知值Ujn通过解方程(方程组)就可以第n+1层上内节点处的值Ujn＋1而李查孙格式前二层的值Ujn－1 , Uj-1n , Ujn , Uj+1n才能求第n+1层上的值2024/9/172024/9/172.2　差分方法的稳定性和收敛性稳定性问题的提出　　对于第一边值问题其中采用如下的显式格式求解2024/9/172024/9/17对h=π /20,分别取τ1和τ2使r1=τ1 /h2 =5/11, r2=τ2/h2 =5/9,求得的解如图2.2和图2.3所示其中线段为边界，曲线为精确解，圆点为差分方程解图 2.2 h=π /20, r1=5/11时边界和解曲线图2024/9/172024/9/17图 2.3 h=π /20, r1=5/9时边界和解曲线图2024/9/172024/9/17稳定性定义　　对于给定的ε＞0，总存在与h,τ无关只依赖于ε的正数δ，使当||U0- U0||= ||V0||<δ时，依差分格式得到的解Un,Un满足不等式||Un- Un||＝ ||Vn||<ε 对于任意的n(0≤n≤T)都成立，则该差分格式是稳定的。

设Un ＝(U1n   U2n …  UN－1n )T， Un ＝(U1n   U2n …  UN－1n )T， φ＝(φ (h) φ(2h ) … φ((N-1)h)T，V0 ＝(V1n   V2n …  VN－1n )T， 稳定性等阶定义　　对于给定的ε＞0，总存在与h,τ无关只依赖于ε的正数δ，使当||U0||<δ时，解Un满足不等式||Un||<ε 对于0≤n≤T，则该差分格式是稳定的2024/9/172024/9/17定理　　差分格式(9)、(14)、(19)和(27)是稳定的充要条件为r满足不等式r ≤1/22024/9/172024/9/172.3　铸件凝固过程的温度场模拟 数值模拟方法已被广泛应用于铸造生产的许多领域研究铸件凝固过程的关键在于确定正在冷却凝固的铸件中的温度场按照实用中不同情况的要求，铸件的温度场计算通常包含四个程序：直角坐标三维程序、柱坐标三维程序、轴对称二维程序、直角坐标二维程序本文仅讨论轴对称二维程序轴对称传热方程如下： 一、数值模拟的应用情况一、数值模拟的应用情况 (29)2024/9/172024/9/172.3　铸件凝固过程的温度场模拟二、变换后热传导方程的推导二、变换后热传导方程的推导2024/9/172024/9/172.3　铸件凝固过程的温度场模拟同理同理：：(30)(31)2024/9/172024/9/172.3　铸件凝固过程的温度场模拟将式将式(30)和式和式(31)代入式代入式(29)得：得：(32)2024/9/172024/9/172.3　铸件凝固过程的温度场模拟令令(33)将它们代入式将它们代入式(32)得得选取适当的选取适当的就可以将铸件和铸型的边界化为规则形状。

因为只需要对一些离散点进行变换，因此这是容易做到的初始条件及边界条件也可类似地进行变换 2024/9/172024/9/172.3　铸件凝固过程的温度场模拟三、差分格式的推导三、差分格式的推导 (33)将各阶偏导数在（将各阶偏导数在（i，，j））处用差商代替得处用差商代替得 当2024/9/172024/9/172.3　铸件凝固过程的温度场模拟同理：同理： (33)当同理：同理： 2024/9/172024/9/172.3　铸件凝固过程的温度场模拟所以当有2024/9/172024/9/172.3　铸件凝固过程的温度场模拟(34)整理后得到差分格式：并且满足：并且满足： 其中：(35)2024/9/172024/9/172.3　铸件凝固过程的温度场模拟(36)所以当有整理后得到差分格式：2024/9/172024/9/172.3　铸件凝固过程的温度场模拟并且满足：并且满足： 其中：(37)2024/9/172024/9/172.3　铸件凝固过程的温度场模拟也是稳定的也是稳定的四、差分格式的稳定性四、差分格式的稳定性 首先可取充分小的使式(4)中的 只要网格不倾斜得很严重则有较小，从而使 又由 有 因此有(38)由式由式(35)和和(38)可知：可知：差分格式差分格式(34)(34)是稳定的。

同样差分格式是稳定的同样差分格式(36)(36)2024/9/172024/9/172.3　铸件凝固过程的温度场模拟五、算例五、算例 图2.4是计算区域及网格，阴影部分是铸件，其余部分是铸型，对铸件部分，取C= ，，，，初温 ，对于铸型取C= ；，气温及铸型初温为 ，边界上热交换系数为 图2.5是通过计算得到的凝固图凝固线从外向里推移，两条凝固线之间的时间间隔是相同的从图2.4 可以看出曲线网格方法能很好地适应不规则形状的边界及沿边界进行加密该算法在网格是规则矩形时退化为通常的差分方法，在图2中可以看出：网格规则部分和不规则部分的凝固进程是相似的，分布也合理可见该方法处理不规则部分的计算效果达到了通常差分法在规则网格的效果2024/9/172024/9/172.3　铸件凝固过程的温度场模拟由上述可见，曲线网格差分法既能象有限元那样能适应不规则边界，又象古典差分法那样具有公式简单、计算速度快、稳定性好等优点，较好地解决了上述四个难点是一个实用的好方法 图 2.4 计算区域图 2.5 凝固进程2024/9/172024/9/17。