带平衡约束的圆和矩形正交packing问题的拟物拟人算法研究

《带平衡约束的圆和矩形正交packing问题的拟物拟人算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、符号说明表ECPP带平衡约束的圆形Packing问题(CirclePackingProblemWithEquilibriumConstraints)EORPP帀平衡约束的正父矩形Packing问题(OrthogonalRectanglePackingProblemWithEquilibriumConstraints)ECROPP带平衡约束的圆和矩形止交Packing问题(CircleandRectangleOrthogonalPackingProblemWithEquilibriumConstrai

2、nts)SMLD卫星舱布局设计(SatelliteModuleLayoutDesign)QPQH拟物拟人算法(Quasi-physicalQuasi-humanAlgorithm)GA遗传算法(GeneticAlgorithm)CA-PSLS带压缩步骤的粒子群算法(CompactAlgorithm-ParticleSwarmLocalSearch)第1章绪论1.1引言1945年10月，英国人A.C.克拉克提出静止卫星通信的设想。他在英国《WirelessWorld》（无线电世界）杂志第10期发表了题

3、为《地球外的中继——卫星能提供全球范圉的无线电覆盖吗?》的文章，首次揭示了人类使用卫星进行通信的可能性。1970年4月24口在酒泉卫星发射中心成功的发射第一颗人造地球卫星“东方红1号”，标志着中国成功地迈向了太空的第一步。随着中国综合实力的增强，中国的航天事业取得了飞速发展，如“神州”系列的飞船、“嫦娥”系列月球探测器一次次的实验成功和“神州八号”与“天宫一号”的太空对接等，中国所取得的一系列的航天硕果（见图1.1）标志着屮国已经迈入了航天强国的行列。面向21世纪，我国要全方位、多层次、多渠道地开展

4、国际空间技术交流与合作，努力与国际空间技术接轨，加强与各国空间技术机构和空间工业界的交往，学习吸收国际上的先进技术和管理经验，加快发展中国的空间技术。图1.1.神州1号飞船外型图人们对卫星舱布局这样比较复杂问题进行研究时，通常首先是对卫星舱里的各种电子元件进行一系列的简化，并对其数学建模，将实际的问题转换成数学问题，然后用一些数学方法对其进行求解，最后回到现实屮，指导并解决实际问题。研究人造卫星舱内仪器、设备的空间布局问题是为了进一步地改善卫星总体质量分布特性山。人造卫星总体质量分布特性包括质心偏移

5、、静不平衡量、转动惯量、惯量夹角和干涉量等。这些参数是卫星与运载工具协调的重要数据，它们直接影响人造卫星的飞行稳定性、扰动特性和使用寿命。在满足各种技术要求的前提下，我们通过对卫星舱内的仪器、设备等元件进行布局优化，进而改善人造卫星的总体质量分布特性。因此，研究卫星舱布局具有非常重要的工程应用意义。布局(Packing)问题忆引属于NP困难问题，其布局优化函数具有非连续、非线性、多峰等特点，在数学理论上它是一类非常经典的组合优化问题，而在工程应用上它又属于概念设计和方案设计问题。它有着非常巨大的工程

6、需求和非常高的求解时间复杂性。迄今为止，尚无一个有效的数值计算方法。其存在的主要困难为：布局问题一般规模都比较大且复杂，对布局问题进行数学建模和求解也是比较困难的。研究人员要从理论和实际两方面解决复杂布局问题，并最终完成工程应用。Packing问题广泛地存在于许多实际的工程应用问题中，例如：超大规模集成电路/芯片布局设计⑷叭造船、报纸/网页版面设计⑺、建筑平面布局设计&刃、材料加工"°川」和航天器(卫星舱)设计I。⑶等。其具体的描述如下：二维空间中，在满足几何约朿的条件下将若干个待布物放置在给定一个

7、给定半径的圆容器里，使这个容器的静不平衡量不大于允许值£,且使整个布局的外包络圆半径尽可能的小I⑷。若从有无性能约束的角度来划分，目前讨论的Packing问题包括无性能约束Packing问题“5,⑹和带性能约束Packing问题。其中带性能约束Packing问题又有加权Packing问题和带平衡约束Packing问题的等等。在后者的求解中，一般情形下布局物被简化为竖直放置圆柱体和长方体。因此，该问题可以归结为带平衡约束圆形Packing问题320】或带平衡约束矩形Packing问题⑵切或带平衡约束圆

8、矩形Packing问题㈡］。目前，国内外众多学者对布局问题进行了非常深入的研究和探讨。为了有效地解决此类问题，国内外大批的学者研究探索出了一些有效的算法，主要包括3个方面：1、启发式算法：滕弘飞等a】对三维动态约束布局问题提出了一种敏度分析技术和启发式方法构造相结合的拟实验启发式方法。刘景发等提出了一种带有预放置矩形块的启发式算法，利用占角和最大穴度优先的摆放策略，能快速求解矩形Packing问题。翟金刚等门引提出了一种基于极大平而图，并通过迭代逐渐降低布局图的边连通