問(wèn)題的數(shù)學(xué)模型與算法

2023/2/6湘潭大學(xué)信息工程學(xué)院

研究生課程：

問(wèn)題的數(shù)學(xué)模型與方法

(2011年上學(xué)期)授課：黎自強(qiáng)(教授)聯(lián)系電話：2023/2/6湘潭大學(xué)信息工程學(xué)院主要內(nèi)容：

1.目標(biāo)函數(shù)優(yōu)化問(wèn)題

1.1遺傳算法求解復(fù)雜布局問(wèn)題

1.2拉格郎日算子求解圓柱體碰撞檢測(cè)問(wèn)題

2.偏微分方程數(shù)值求解

2.1鑄件凝固過(guò)程的溫度場(chǎng)模擬

2023/2/6湘潭大學(xué)信息工程學(xué)院1.目標(biāo)函數(shù)優(yōu)化問(wèn)題1.1.1工程背景和科學(xué)問(wèn)題的提出1.1.2布局優(yōu)化問(wèn)題研究進(jìn)展1.1.3航天器布局方案設(shè)計(jì)研究進(jìn)展1.1.4用遺傳算法求解布局問(wèn)題1.1復(fù)雜布局問(wèn)題2023/2/6湘潭大學(xué)信息工程學(xué)院1.1.1工程背景和科學(xué)問(wèn)題的提出

a)發(fā)達(dá)國(guó)家航天器發(fā)展現(xiàn)狀

美國(guó)與歐洲空間局自80年代起，致力于用計(jì)算機(jī)技術(shù)解決航天器艙的待布物總體布局問(wèn)題的研究，其關(guān)鍵理論、方法、技術(shù)至今仍處于保密狀態(tài)。近年來(lái)有用協(xié)同優(yōu)化法設(shè)計(jì)航天器的保護(hù)裝置和得到NASA資助的用遺傳算法進(jìn)行航天器的設(shè)計(jì)，但很少涉及布局設(shè)計(jì)的內(nèi)容。根據(jù)我國(guó)人員出國(guó)考察獲悉，以衛(wèi)星布局設(shè)計(jì)為例，目前美國(guó)設(shè)計(jì)效率比我國(guó)快20倍以上，但是其性能和空間利用率對(duì)比不詳。2023/2/6湘潭大學(xué)信息工程學(xué)院b)國(guó)內(nèi)航天器發(fā)展現(xiàn)狀

我國(guó)航天器設(shè)計(jì)多以人工設(shè)計(jì)為主，參考樣圖或資料，用計(jì)算機(jī)輔助繪圖（二、三維），然后用國(guó)外軟件進(jìn)行三維造型模裝，再用國(guó)外軟件進(jìn)行三維動(dòng)力學(xué)驗(yàn)算。若不合適，用人工修改設(shè)計(jì)，最后建造1:1實(shí)物模型，進(jìn)行實(shí)驗(yàn)驗(yàn)證。2023/2/6湘潭大學(xué)信息工程學(xué)院c)人工設(shè)計(jì)存在的問(wèn)題：性能不易保證或非優(yōu)化；空間利用率低；設(shè)計(jì)成本高；設(shè)計(jì)周期長(zhǎng)。

過(guò)去衛(wèi)星曾因總體布局不當(dāng)，動(dòng)不平衡過(guò)大，曾造成過(guò)早報(bào)廢的惡果。況且我國(guó)還要研制更復(fù)雜的空間站，其布局設(shè)計(jì)尤為重要。

2023/2/6湘潭大學(xué)信息工程學(xué)院d)科學(xué)問(wèn)題的提出從理論上說(shuō)，航天器布局設(shè)計(jì)，可歸結(jié)出“可數(shù)學(xué)模型化”和“不可或難數(shù)學(xué)模型化”兩類問(wèn)題。前者屬很難的帶性能約束的三維布局優(yōu)化問(wèn)題；后者多屬工程復(fù)雜系統(tǒng)問(wèn)題，涉及人腦思維模型問(wèn)題，解決方法有二種：一是人工智能，基于智能的知識(shí)模型及其推理；二是人機(jī)結(jié)合(Man-MachineSynergy)或人機(jī)合作(puterCooperation)。航天器布局設(shè)計(jì)屬交叉學(xué)科前沿課題的基礎(chǔ)理論和應(yīng)用基礎(chǔ)研究，具有重要的科學(xué)意義。2023/2/6湘潭大學(xué)信息工程學(xué)院1.1.2布局優(yōu)化問(wèn)題研究進(jìn)展

布局問(wèn)題(LayoutProblem)屬于復(fù)雜的組合優(yōu)化問(wèn)題，即使最簡(jiǎn)單的一維布局也屬于NPC問(wèn)題。自1831年高斯(Gauss)研究布局問(wèn)題開(kāi)始，雖然經(jīng)過(guò)幾代人的努力，但迄今尚無(wú)成熟的理論和有效的數(shù)值計(jì)算方法。從理論上講，布局問(wèn)題可分為切段(Cutting-Stock)問(wèn)題和裝填(Packing)問(wèn)題。2023/2/6湘潭大學(xué)信息工程學(xué)院按照布局物體的布局維數(shù)分類a)一維布局問(wèn)題

b)二維布局問(wèn)題

c)三維布局問(wèn)題

2023/2/6湘潭大學(xué)信息工程學(xué)院

a)一維布局問(wèn)題

一維布局問(wèn)題中典型的例子是在給定長(zhǎng)度的棒料上，切割長(zhǎng)度不等的若干短棒，此類問(wèn)題通常稱為切段問(wèn)題(Cutting-StockProblem)。解決方法：Faggioli[5]利用啟發(fā)式算法提出了切段排序問(wèn)題的數(shù)學(xué)模型和一個(gè)三步解法；Vasko[6]和Nitsche[7]

分別利用樹(shù)搜索算法和松弛算法來(lái)解決一維切段問(wèn)題；PetridisVassilios等[8]利用遺傳算法以動(dòng)態(tài)的方式把問(wèn)題的約束合并到適應(yīng)度函數(shù)中。2023/2/6湘潭大學(xué)信息工程學(xué)院b)二維布局問(wèn)題

二維布局問(wèn)題包括：一刀切問(wèn)題

將某些不同大小的小矩形按照一刀切的原則排放在一個(gè)大矩形板材上，使面積浪費(fèi)最小，這是剪床落料、玻璃切割、紙張切割中遇到的主要問(wèn)題。所謂一刀切，是指切割總是從矩形板材的一邊開(kāi)始一直切到其對(duì)邊，即每切一刀都將一個(gè)矩形分割成兩個(gè)小矩形

底盤(pán)裝載問(wèn)題

底盤(pán)裝載問(wèn)題來(lái)源于運(yùn)輸、搬運(yùn)中的貨物擺放或裝箱。將多個(gè)相同大小的立體箱子放入一立方體容器中，且要求放入的箱子越多越好。2023/2/6湘潭大學(xué)信息工程學(xué)院矩形布局問(wèn)題(RectanglePackingProblems)

矩形布局問(wèn)題是將許多大小不同的二維矩形布置在一個(gè)大的矩形中，使面積覆蓋率最大，這是大規(guī)模集成電路設(shè)計(jì)中所碰到的主要問(wèn)題。圓布局問(wèn)題(CirclePackingProblems)圓布局問(wèn)題是將許多大小相同或不同的圓布置在一個(gè)大的圓形、三角形或矩形容器中，使面積覆蓋率最大[39]。這類問(wèn)題大量地存在于幾何、化學(xué)、生物學(xué)、工程和優(yōu)化中，已經(jīng)引起人們的很大關(guān)注[40]。

通常不等圓裝填問(wèn)題還需滿足一定的性能約束條件，譬如：慣性、平衡性、和穩(wěn)定性約束等，我們把這種問(wèn)題稱為帶性能約束的不等圓裝填問(wèn)題。2023/2/6湘潭大學(xué)信息工程學(xué)院二維不規(guī)則圖形布局問(wèn)題(2-DIrregularGraphLayoutProblems)

二維不規(guī)則圖形布局問(wèn)題是指將許多任意形狀、大小的二維形體布置在一任意形狀的二維平面內(nèi)以使某一性能最優(yōu)，如板材下料，服裝裁剪等。處理這類問(wèn)題通常是把不規(guī)則圖形套排在一些形狀比較規(guī)則的簡(jiǎn)單圖形中，然后用這些簡(jiǎn)單的圖形在給定的平面內(nèi)排樣，以降低問(wèn)題的復(fù)雜程度。2023/2/6湘潭大學(xué)信息工程學(xué)院三維布局問(wèn)題

三維布局問(wèn)題包括：無(wú)性能約束的三維布局問(wèn)題(3-DLayoutProblemswithNon-BehavioralConstraints)無(wú)性能約束三維布局問(wèn)題是指將盡量多的不同形狀、尺寸的三維物體放入到一長(zhǎng)方體（或圓柱體）容器中，例如背包問(wèn)題、集裝箱問(wèn)題。

帶性能約束的三維布局問(wèn)題(3-DLayoutProblemswithBehavioralConstraints)

。帶性能約束三維布局問(wèn)題是指將任意形狀、大小和性能的三維實(shí)體擺放在一個(gè)任意形狀、大小的三維容器中，以滿足某些約束或使某些目標(biāo)最優(yōu)

2023/2/6湘潭大學(xué)信息工程學(xué)院例子約束底盤(pán)裝載和船舶配載問(wèn)題

汽車(chē)駕駛艙布局問(wèn)題

集成電路(VLSI)的布局規(guī)劃

航天器艙布局方案設(shè)計(jì)問(wèn)題

2023/2/6湘潭大學(xué)信息工程學(xué)院帶性能約束布局問(wèn)題的算法

啟發(fā)式算法(HeuristicAlgorithm)

擬物擬人法

擬實(shí)驗(yàn)綜合啟發(fā)式算法

八叉樹(shù)結(jié)構(gòu)與定位―定序函數(shù)相結(jié)合的啟發(fā)式算法

GENET模型

Montreuil模型

膨脹算法

2023/2/6湘潭大學(xué)信息工程學(xué)院圖論法(GraphTheory)

圖論作為組合數(shù)學(xué)的重要組成部分，在許多領(lǐng)域有著廣泛的應(yīng)用。該方法一般將帶性能約束布局問(wèn)題分兩步來(lái)求解。第一步，求出相鄰?fù)負(fù)潢P(guān)系的無(wú)尺寸的平面布局，即根據(jù)待布物之間的確定位置關(guān)系構(gòu)造一個(gè)圖，圖中節(jié)點(diǎn)代表各待布物，連接節(jié)點(diǎn)的邊表示待布物之間的確定位置關(guān)系。第二步，根據(jù)布局圖，利用優(yōu)化算法求出待布物之間的具體尺寸。

2023/2/6湘潭大學(xué)信息工程學(xué)院模擬退火算法(SimulatedAnnealingAlgorithm)演化算法(EvolutionaryAlgorithm)上述四種方法基本上是用數(shù)學(xué)方法求解數(shù)學(xué)模型問(wèn)題。人工智能(包括專家系統(tǒng))(ArtificialIntelligenceincludingExpertSystem)人機(jī)交互、人機(jī)結(jié)合與人機(jī)協(xié)同算法(puterInteraction,CombinationandCooperationAlgorithm)2023/2/6湘潭大學(xué)信息工程學(xué)院布局問(wèn)題評(píng)述及其策略和求解算法的發(fā)展前景現(xiàn)在的復(fù)雜布局研究存在如下問(wèn)題：

從布局策略上講，傳統(tǒng)的計(jì)算機(jī)輔助布局的思路，多將實(shí)際問(wèn)題化為簡(jiǎn)化的數(shù)學(xué)模型用計(jì)算機(jī)算法求解。由于數(shù)學(xué)模型過(guò)于簡(jiǎn)化，即使能求得結(jié)果，但距離解決實(shí)際問(wèn)題相差甚遠(yuǎn)，因?yàn)閷?shí)際的工程影響因素復(fù)雜，存在不可（或難以）數(shù)學(xué)模型化的問(wèn)題；

從布局問(wèn)題模型的描述上講，布局問(wèn)題的有效、精確表達(dá)是解決問(wèn)題的前提和基礎(chǔ)。目前多用數(shù)學(xué)模型，若模型簡(jiǎn)單則不能概括必要內(nèi)容，若模型過(guò)于復(fù)雜，又無(wú)法求解。另外，缺乏包含數(shù)學(xué)、仿真、符號(hào)的復(fù)合模型研究，缺乏將工程復(fù)雜布局問(wèn)題從一個(gè)復(fù)雜工程系統(tǒng)角度去研究；

2023/2/6湘潭大學(xué)信息工程學(xué)院從求解方法上講，復(fù)雜的布局問(wèn)題求解困難在于存在組合爆炸，如何解決成為關(guān)鍵。但由于以往研究人員各自研究領(lǐng)域及知識(shí)背景的不同，很難甚至無(wú)法與其他求解方法協(xié)同進(jìn)行設(shè)計(jì)求解。解決此問(wèn)題，目前常見(jiàn)的途徑是尋找好的算法或者是算法集成；從優(yōu)化布局方案的評(píng)價(jià)上講，尚未建立一套科學(xué)和有效的布局方案評(píng)價(jià)體系，這給布局優(yōu)化過(guò)程中的方案選擇和決策帶來(lái)困難；從研究難度和規(guī)模上講，存在的問(wèn)題是：對(duì)一、二維布局研究多，三維布局研究少，尤其是對(duì)三維帶性能約束布局研究少；對(duì)小型問(wèn)題研究多，對(duì)中大型問(wèn)題研究少；從實(shí)用化上講，實(shí)踐應(yīng)用深度和廣度有待提高。2023/2/6湘潭大學(xué)信息工程學(xué)院關(guān)于布局策略

布局策略的安排是問(wèn)題求解的前提或出發(fā)點(diǎn)。布局策略的表現(xiàn)形式是數(shù)學(xué)模型，然后采取相應(yīng)的算法。目前帶性能約束布局問(wèn)題中常用的布局策略大多數(shù)是采用傳統(tǒng)的計(jì)算機(jī)輔助設(shè)計(jì)的思想，即將實(shí)際問(wèn)題簡(jiǎn)化為單一的數(shù)學(xué)模型，這種單一的模型往往長(zhǎng)于描述問(wèn)題的某方面的特點(diǎn)，而不善于表達(dá)問(wèn)題的綜合屬性，也缺少科學(xué)有效的布局方案評(píng)價(jià)體系；特別是對(duì)于復(fù)雜的三維問(wèn)題這種布局策略的局限性更為突出；因此即使能算出結(jié)果，可能與實(shí)際問(wèn)題相差很遠(yuǎn)。2023/2/6湘潭大學(xué)信息工程學(xué)院求解算法的發(fā)展前景

航天器艙布局方案設(shè)計(jì)目前國(guó)外（如歐、美）主要有三種方法：一是演化算法；二是虛擬（現(xiàn)實(shí)）設(shè)計(jì)；三是協(xié)同設(shè)計(jì)。其中關(guān)鍵因素是“算法”與“人”。無(wú)論是虛擬設(shè)計(jì)還是協(xié)同設(shè)計(jì)，若無(wú)有效的布局算法，并發(fā)揮人的作用，尤其是對(duì)于如此復(fù)雜工程設(shè)計(jì)，是無(wú)法完成高質(zhì)量設(shè)計(jì)的。人機(jī)結(jié)合和人機(jī)交互的思想充分發(fā)揮了人機(jī)各自的特長(zhǎng)，將這些思想用于其它算法的求解，能夠得到生動(dòng)的用戶界面，并將人的知識(shí)實(shí)時(shí)地加入到算法中，使算法快速、有效地解決帶性能約束布局問(wèn)題。對(duì)于求解工程復(fù)雜布局問(wèn)題，對(duì)解決人機(jī)合作的“可操作性”問(wèn)題，提供了一種方法或途徑。演化算法、仿真技術(shù)、虛擬設(shè)計(jì)、人工智能、人機(jī)結(jié)合或人機(jī)交互算法的集成綜合的方法，對(duì)帶性能約束布局算法的發(fā)展將會(huì)有很大的推動(dòng)。

2023/2/6湘潭大學(xué)信息工程學(xué)院1.1.3航天器布局設(shè)計(jì)研究進(jìn)展

航天器（衛(wèi)星、飛船、空間站）(如圖1.5)是由有效載荷、結(jié)構(gòu)、熱控制、姿態(tài)與軌道控制、電源、跟蹤遙測(cè)與遙控、數(shù)據(jù)管理等分系統(tǒng)所組成，分系統(tǒng)又由各自的儀器、設(shè)備和部件組成；組件（部件）形式多樣、數(shù)量繁多；設(shè)備與設(shè)備之間、分系統(tǒng)與分系統(tǒng)之間有各種不同的機(jī)、電、液、氣接口，并有傳動(dòng)、管線、纜線相連；所以航天器是一個(gè)復(fù)雜工程系統(tǒng)[126-128]。其布局方案設(shè)計(jì)是研究如何充分利用航天器有限的空間，布置盡可能多的組件和儀器、設(shè)備，并滿足其內(nèi)部和周?chē)h(huán)境的各種約束要求的問(wèn)題,這是一個(gè)多學(xué)科交叉課題。2023/2/6湘潭大學(xué)信息工程學(xué)院1.5禮炮號(hào)空間站2023/2/6湘潭大學(xué)信息工程學(xué)院航天器總體布局方案設(shè)計(jì)航天器總體布局方案設(shè)計(jì)的目的是在選定構(gòu)型（組件或子系統(tǒng)）基礎(chǔ)上將航天器上的儀器設(shè)備布置在各艙段的合適位置（如圖1.6和1.7）。對(duì)于載入過(guò)程中使用的和需要返回地面的儀器設(shè)備應(yīng)當(dāng)布置在返回艙，僅在載入前使用的設(shè)備可以布置在軌道艙或儀器設(shè)備艙，以降低衛(wèi)星或飛船的結(jié)構(gòu)質(zhì)量。在進(jìn)行總體布局方案設(shè)計(jì)之前，要對(duì)航天器的功能要求進(jìn)行分析，選擇組件或子系統(tǒng)，然后確定組件或子系統(tǒng)之間的相互位置關(guān)系，并使總系統(tǒng)具有一個(gè)協(xié)調(diào)完善的造型；最后從多個(gè)布局方案中擇優(yōu)選取。航天器的總體布局是全局性的重要問(wèn)題，不但要考慮到航天器各組件或子系統(tǒng)之間的各種約束，而且還要考慮航天器同各種外部因素（如空間環(huán)境）之間的約束，盡量達(dá)到功能合理、結(jié)構(gòu)緊湊、層次清晰、比例協(xié)調(diào)等要求。總體上要符合航天器總體設(shè)計(jì)的要求。

2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.6聯(lián)盟號(hào)飛船2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.7空間站各艙段示意圖2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.8空間站實(shí)驗(yàn)艙標(biāo)準(zhǔn)柜2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.9標(biāo)準(zhǔn)柜待布物優(yōu)化圖2023/2/6湘潭大學(xué)信息工程學(xué)院航天器艙布局方案設(shè)計(jì)

航天器艙布局方案設(shè)計(jì)是研究在滿足各種工程技術(shù)條件的前提下，如何將各種儀器和設(shè)備最優(yōu)地布置在航天器艙體內(nèi)（或外）(如圖1.7和1.8)，使得布局評(píng)價(jià)指標(biāo)達(dá)到最優(yōu)或滿足工程結(jié)束準(zhǔn)則。它屬于帶性能約束的三維布局優(yōu)化問(wèn)題，具有不確定性、高度非線性、知識(shí)不完備性、既需定性計(jì)算又需定量分析等特點(diǎn)。布局問(wèn)題的NP-困難性和航天器設(shè)計(jì)本身的工程系統(tǒng)復(fù)雜性使得該問(wèn)題的解決既存在理論上的開(kāi)拓性和挑戰(zhàn)性，又存在工程實(shí)踐上的艱難性和復(fù)雜性。Ferebee等介紹了一種系統(tǒng)方法（Systematicmethod）來(lái)確定地球軌道衛(wèi)星上觀測(cè)設(shè)備的優(yōu)化布局問(wèn)題。Braun等將協(xié)同優(yōu)化算法用于單級(jí)軌道運(yùn)載火箭的布局設(shè)計(jì)。滕弘飛等在文[136]中以返回式衛(wèi)星艙布局方案設(shè)計(jì)為背景，提出所謂的轉(zhuǎn)動(dòng)圓桌平衡擺盤(pán)問(wèn)題，并建立了該問(wèn)題的數(shù)學(xué)模型。同時(shí)提出了模式迭換法、主布模法等方法求解。2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.10聯(lián)盟號(hào)返回艙2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.11返回式衛(wèi)星2023/2/6湘潭大學(xué)信息工程學(xué)院航天器天線布局方案設(shè)計(jì)

一般說(shuō)來(lái)，航天器天線在電氣性能、機(jī)械結(jié)構(gòu)、溫度控制以及總體布局之間，往往互相矛盾，需統(tǒng)籌兼顧、折衷考慮一系列問(wèn)題。天線布局受航天器結(jié)構(gòu)形狀和表面位置所限，但由于天線的功能、工作頻率和航天器的軌道姿態(tài)，天線又必須放在特定位置；多種天線相互為鄰，在電氣性能上各種天線又不可互相妨礙；天線同航天器上的突起、伸長(zhǎng)物件不應(yīng)互相干涉；因此，航天器天線的布局相當(dāng)復(fù)雜，直接關(guān)系到衛(wèi)星性能的好壞。2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.12天線結(jié)構(gòu)總體示意圖Fig1.12DiagramofantennageneralstructureLinden等討論了使用遺傳算法求解的衛(wèi)星結(jié)構(gòu)方面的金屬天線的優(yōu)化布局問(wèn)題。

Coulomb等以BOPSAT衛(wèi)星的有效載荷的設(shè)計(jì)為背景，對(duì)移動(dòng)連接天線的布局進(jìn)行了探討。比較了幾種控制輻射矩陣的組態(tài)，分析了其優(yōu)缺點(diǎn)，最后采用了混合（主動(dòng)＋被動(dòng)）組態(tài)設(shè)計(jì)方法進(jìn)行布局設(shè)計(jì)。Boissonnat等介紹了怎樣把一些物理布局約束轉(zhuǎn)化為幾何模型和怎樣利用Minkowski操作放置某些設(shè)備，特別是天線的布局。

2023/2/6湘潭大學(xué)信息工程學(xué)院航天器其它組件的布局方案設(shè)計(jì)

航天器帆布局方案設(shè)計(jì)

航天器穩(wěn)定平臺(tái)布局方案設(shè)計(jì)

航天器姿控發(fā)動(dòng)機(jī)布局方案設(shè)計(jì)

航天器氣動(dòng)外形布局方案設(shè)計(jì)

航天器復(fù)雜插座板插孔布局方案設(shè)計(jì)

航天器電路板布局方案設(shè)計(jì)

2023/2/6湘潭大學(xué)信息工程學(xué)院太陽(yáng)帆利用太陽(yáng)光的壓力產(chǎn)生能量，保證航天器進(jìn)行太空飛行。太陽(yáng)光子不停地撞擊太陽(yáng)帆，使得太陽(yáng)帆所獲得的動(dòng)量不斷增加。

Genta等介紹了一種可以變動(dòng)的太陽(yáng)帆的結(jié)構(gòu)布局。它是一種可膨脹的桁架結(jié)構(gòu)，經(jīng)過(guò)展開(kāi)以后依舊保持壓力以緩解所有的壓縮力。帆的表面是一個(gè)圓形的薄膜，有效載荷趨于薄膜的中心。為了計(jì)算有效載荷距離中心的距離，采用蛛網(wǎng)組態(tài)分割的方法來(lái)解決，用一定數(shù)量的圓形電纜依附在外桁架上以支撐太陽(yáng)帆。Pillow太陽(yáng)帆結(jié)構(gòu)示意圖如圖1.13所示。

圖1.13Pillow太陽(yáng)帆示意圖[13]Fig.1.13Pillowsolarsail[23]外波束有效載荷太陽(yáng)光2R02023/2/6湘潭大學(xué)信息工程學(xué)院空間太陽(yáng)探測(cè)器的標(biāo)準(zhǔn)穩(wěn)定平臺(tái)（UnifiedStabilizedPlatform，USP）作用是使面向太陽(yáng)的各種探測(cè)設(shè)備穩(wěn)定地指向太陽(yáng)。

Astafourov等介紹了標(biāo)準(zhǔn)穩(wěn)定平臺(tái)（USP）的布局，考慮了平臺(tái)同科學(xué)設(shè)備（分光計(jì)和輻射計(jì)）之間的不干涉性。設(shè)計(jì)控制結(jié)構(gòu)的原則主要是在考慮有效載荷的外形尺寸和重量的前提下，滿足USP操作的精確性要求。建立了一個(gè)模塊化的系統(tǒng)，可以有效的處理帶有各種載荷的穩(wěn)定平臺(tái)，以增加其有效負(fù)載，減小項(xiàng)目的花費(fèi)。

圖1.14帶有穩(wěn)定平臺(tái)的空間太陽(yáng)探測(cè)器有效載荷的布局[25]1-分光計(jì)；2－輻射計(jì)；3－太陽(yáng)能傳感器；4驅(qū)動(dòng)B；5－驅(qū)動(dòng)YFig.1.14Layoutforpayloadofspacesolarpatrolintegratedwithstabilizedplatform[25]spectrometer;2-radiometers;3-solarsensor;4-drivesB;5-drivesY2023/2/6湘潭大學(xué)信息工程學(xué)院航天器為了具有良好的穩(wěn)定性、精確的速度和姿態(tài)控制，動(dòng)力系統(tǒng)質(zhì)量的大小至關(guān)重要。在推進(jìn)劑及其輸送系統(tǒng)選定之后，通過(guò)對(duì)推力系統(tǒng)的設(shè)計(jì)變量進(jìn)行參數(shù)分析，即可初步確定滿足飛行任務(wù)的動(dòng)力系統(tǒng)的質(zhì)量。

胡小平，王中偉等在液體推進(jìn)劑動(dòng)力系統(tǒng)質(zhì)量模型的基礎(chǔ)上，針對(duì)采用雙組元推進(jìn)劑姿控發(fā)動(dòng)機(jī)的空間飛行器,在總有效沖量和有效沖量矩一定的條件下,提出了優(yōu)選動(dòng)力系統(tǒng)總質(zhì)量最輕的姿控發(fā)動(dòng)機(jī)布局方案的一種方法。

圖1.15空間飛行器姿態(tài)控制發(fā)動(dòng)機(jī)布局方案Fig.1.15Localityarrangementofattitudecontrolengine2023/2/6湘潭大學(xué)信息工程學(xué)院

所謂的氣動(dòng)優(yōu)化布局是指優(yōu)化航天器氣動(dòng)外形，使之滿足航天器對(duì)升阻比、靜穩(wěn)定度、配平攻角等性能方面的要求。

潘騰、安復(fù)興討論了垂直起飛、垂直降落（VTVL）飛行器（一種先進(jìn)的、能重復(fù)使用的航天飛行器）的選型和氣動(dòng)優(yōu)化布局。對(duì)各參數(shù)（如削面角、球頭半徑等）的氣動(dòng)性能曲線進(jìn)行分析，并綜合考慮了各參數(shù)的相互制約作用，利用設(shè)計(jì)師的經(jīng)驗(yàn)給出了氣動(dòng)優(yōu)化布局，其示意圖如圖1.16所示。最后通過(guò)風(fēng)洞實(shí)驗(yàn)驗(yàn)證了布局的正確性。

圖1.16優(yōu)化氣動(dòng)布局外形及尺寸參數(shù)Fig.1.16Shapeandsizeparametersofaerodynamiclayoutoptimization2023/2/6湘潭大學(xué)信息工程學(xué)院航天器復(fù)雜插座板插孔布局方案設(shè)計(jì)

唐飛等研究了航天器中一種能夠在火工螺栓作用下自動(dòng)拔脫的復(fù)雜插座板上插孔的布局設(shè)計(jì)問(wèn)題，簡(jiǎn)化為在圓形插板上，根據(jù)給定的n個(gè)插頭，考慮電、液、氣各種管線插頭的插座板（非凸的可布空間）和插頭的拔脫力、插座板的緊固螺栓力、邊緣彈簧的彈簧力等約束情況下，布置其插孔位置。它屬于帶作用力約束的二維裝填(Packing)問(wèn)題。給出了該問(wèn)題的數(shù)學(xué)模型，并用給出的復(fù)數(shù)編碼的遺傳算法進(jìn)行求解[154]，提供一個(gè)設(shè)計(jì)參考方案。

2023/2/6湘潭大學(xué)信息工程學(xué)院航天器電路板布局方案設(shè)計(jì)

Hirt等介紹了將虛擬樣機(jī)技術(shù)（VirtualPrototyping,VP）應(yīng)用到航天器上含有轉(zhuǎn)換器的電路板的布局設(shè)計(jì)。將VP作為一種系統(tǒng)化的分析和選擇合適結(jié)構(gòu)的方法,以花費(fèi)為評(píng)價(jià)準(zhǔn)則，并行的分析幾種可能的方案。使用基于JavaCAD平臺(tái)的Java語(yǔ)言完成系統(tǒng)的設(shè)計(jì)。圖1.17含有5:4轉(zhuǎn)換器的電路板]Fig.1.17PCBcontaininga5:4switch2023/2/6湘潭大學(xué)信息工程學(xué)院1.1.4用遺傳算法求解布局問(wèn)題(1)

基本遺傳算法的框架按照Goldberg提出的框架，基本遺傳算法(Simplegeneticalgorithm,SGA)只包括交叉、變異和選擇三種基本遺傳算子，可用式(1)所描述的一個(gè)8元組表示。

SGA＝｛C,E,P0,M,Φ,Γ,Ψ,Τ｝(1)其中C為個(gè)體編碼方法，E為個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，P0為初始群體，M為群體規(guī)模大小尺寸，Φ為選擇算子，Γ為交叉算子，Ψ為變異算子，Τ遺傳運(yùn)算終止條件。

2023/2/6湘潭大學(xué)信息工程學(xué)院基本遺傳算法的主要步驟如下：Step1

隨機(jī)產(chǎn)生P0個(gè)初始種群，并對(duì)每一個(gè)種群，求出適應(yīng)度函數(shù)的值。Step2判斷最優(yōu)個(gè)體是否滿足要求，如果滿足則輸出結(jié)果后轉(zhuǎn)Step6，否則執(zhí)行下一步。

Step3

按交叉概率Pc對(duì)個(gè)體作交叉運(yùn)算產(chǎn)生新一定量的個(gè)體。Step4按變異概率Pm對(duì)個(gè)體作交叉運(yùn)算產(chǎn)生新一定量的個(gè)體，通過(guò)交叉和變異后種群的規(guī)模為M。Step5

對(duì)M個(gè)種群求出其適應(yīng)度函數(shù)的值，按適應(yīng)度大小選取其中的P0個(gè)種后轉(zhuǎn)Step2。Step6算法結(jié)束。

(2)基本遺傳算法的幾個(gè)重要的概念

①問(wèn)題的編碼將一個(gè)問(wèn)題的解空間轉(zhuǎn)換為遺傳算法所能處理的搜索空間的方法。問(wèn)題的編碼方法直接決定著遺傳算法的性能和求解的效率。編碼方法有二進(jìn)制編碼、十進(jìn)制編碼、序號(hào)編碼和符號(hào)編號(hào)等。布局遺傳算法算例都采用十進(jìn)制編碼。

②

適應(yīng)度函數(shù)適應(yīng)度是度量種群個(gè)體在優(yōu)化計(jì)算中可能達(dá)到或接近于找到最優(yōu)解的程度。度量種群個(gè)體適應(yīng)度的函數(shù)則稱為適應(yīng)度函數(shù)。一般要求適應(yīng)度函數(shù)f(x)>0。適應(yīng)度大的種群個(gè)體遺傳到下一代的概率就越大，適應(yīng)度小的種群個(gè)體遺傳到下一代的概率就越小。2023/2/6湘潭大學(xué)信息工程學(xué)院③

遺傳算子遺傳算子包括選擇算子、交叉算子和變異算子。選擇是為了避免有效基因損失，使性能較優(yōu)的個(gè)體得以更高的概率生存，從而加快收斂速度和提高計(jì)算效率。選擇算子有比例選擇、排序選擇、最優(yōu)保存、確定式采樣選擇、期望值選擇、無(wú)回放余數(shù)隨機(jī)選擇和隨機(jī)聯(lián)賽選擇。比例選擇算子是以正比于個(gè)體適應(yīng)度的概率來(lái)選擇個(gè)體，而排序選擇算子是按適應(yīng)度大小順序?qū)θ后w中的所有個(gè)體進(jìn)行排序，然后把事先計(jì)算好的概率表依次分配給每個(gè)個(gè)體作為各自的選擇概率。其中最常用的是比例選擇和排序選擇，本文遺傳算法算例采用最優(yōu)保存策略，因?yàn)楦鶕?jù)標(biāo)準(zhǔn)遺傳算法的收斂性可知：使用最優(yōu)保存策略可使遺傳算法收斂于最優(yōu)解的概率為1。2023/2/6湘潭大學(xué)信息工程學(xué)院交叉是在種群中的兩個(gè)個(gè)體進(jìn)行。通過(guò)交叉產(chǎn)生新的個(gè)體，以致遺傳算法能在解空間中進(jìn)行有效的搜索，同時(shí)降低對(duì)有效模式的破壞概率。常用的交叉算子有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、均勻交叉和算術(shù)交叉。本文遺傳算法算例都采用兩點(diǎn)交叉。變異是個(gè)體中某些基因位上的基因值加以改變。種群個(gè)體通過(guò)變異產(chǎn)生新的個(gè)體，常用的變異算子有基本變異、均勻變異、非均勻變異和高斯變異等。變異算子在遺傳算法中的作用是使形遺傳算法具有局部搜索能力和維持群體的多樣性，防止出現(xiàn)未成熟收斂現(xiàn)象。2023/2/6湘潭大學(xué)信息工程學(xué)院(3)基本遺傳算法的幾個(gè)參數(shù)設(shè)定

基本遺傳算法的參數(shù)有編碼長(zhǎng)度、種群規(guī)模、交叉概率、變異概率和終止代數(shù)。①編碼長(zhǎng)度用二進(jìn)制編碼表示個(gè)體時(shí)，編碼的長(zhǎng)度l與求解問(wèn)題的要求精度有關(guān)；用實(shí)數(shù)編碼表示個(gè)體時(shí)，編碼的長(zhǎng)度l與決策問(wèn)題的變量個(gè)數(shù)n相等；用符號(hào)編碼表示個(gè)體時(shí)，編碼的長(zhǎng)度l由問(wèn)題的編碼方式來(lái)確定。②群體規(guī)模群體規(guī)模M表示群體中個(gè)體的數(shù)量。當(dāng)M取值較小，能一定程度提高遺傳算法的計(jì)算速度，但降低了群體的多樣性，可能引起遺傳算法的早熟現(xiàn)象；當(dāng)M取值較大，則遺傳算法的效率降低。一般M的取值在20~100之間。2023/2/6湘潭大學(xué)信息工程學(xué)院

③交叉概率遺傳算法通過(guò)交叉產(chǎn)生新的個(gè)體，因此，交叉概率不能取得太小，也不能取得過(guò)大，若取得過(guò)大，會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化計(jì)算產(chǎn)生不利的影響；若取得過(guò)小，則產(chǎn)生新的個(gè)體的速度較慢。一般交叉概率取值在0.4~0.99之間。

④變異概率變異概率直接決定產(chǎn)生新的個(gè)體的多少。變異概率越大，由于產(chǎn)生新的個(gè)體就越多，增加了群體的多樣性，但也破壞更多優(yōu)良的個(gè)體，使遺傳算法的性能接近于隨機(jī)搜索算法；變異概率取得過(guò)小，則產(chǎn)生新的個(gè)體和抑制早熟現(xiàn)象的能力都會(huì)較差。一般變異概率取值在0.05~0.4之間。2023/2/6湘潭大學(xué)信息工程學(xué)院

⑤終止代數(shù)終止代數(shù)T是遺傳算法運(yùn)行終止的一個(gè)主要參數(shù)，它表示遺傳算法運(yùn)行到指定代數(shù)就終止。這時(shí)，群體中的最優(yōu)個(gè)體被作為所求問(wèn)題的最優(yōu)解輸出。一般終止代數(shù)取值在100~20000之間。這里需要說(shuō)明的是遺傳算法還可以使用別的終止條件來(lái)終止運(yùn)行，如群體中所有個(gè)體適應(yīng)度的方差均小于某一較小的閥值。

2023/2/6湘潭大學(xué)信息工程學(xué)院(4)約束條件的處理由于求解的優(yōu)化問(wèn)題都帶有一定的約束條件，因此，應(yīng)用遺傳算法求解時(shí)都必須對(duì)約束條件進(jìn)行處理。一般的處理方法有搜索空間限定法、可行解變換法和罰函數(shù)法。

搜索空間限定法的基本思想是對(duì)遺傳算法的搜索空間的大小加以限制，使搜索空間的表示一個(gè)個(gè)體的點(diǎn)與解空間中表示一個(gè)解的點(diǎn)存在一一對(duì)應(yīng)的關(guān)系?？尚薪庾儞Q法的基本思想是在由個(gè)體基因型到個(gè)體表現(xiàn)型的變換中，尋找出一種由個(gè)體基因型與個(gè)體表現(xiàn)型之間的多對(duì)一的變換關(guān)系，使進(jìn)化過(guò)程中所產(chǎn)生的個(gè)體總能夠通過(guò)這個(gè)變換而轉(zhuǎn)化成解空間中滿足約束條件的一個(gè)可行解。罰函數(shù)法的基本思想是對(duì)在解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體，計(jì)算其適應(yīng)度時(shí)處以一個(gè)罰函數(shù)，從而降低該個(gè)體適應(yīng)度值，使該個(gè)2023/2/6湘潭大學(xué)信息工程學(xué)院體被遺傳到下一代群體中的機(jī)會(huì)減少。隨著遺傳算法的運(yùn)行，不可行解在解群占的比例總體上越來(lái)越少，可行解逐步占住主導(dǎo)地位并逐步趨向最優(yōu)解。只要罰函數(shù)形式得當(dāng)，一般都可得到好的結(jié)果。罰函數(shù)法是目前最常用的一種方法。例如：約束優(yōu)化問(wèn)題式(2)加入罰函數(shù)可描述為式(3)的形式。其中X＝(x1,x2,…,xn)，n為設(shè)計(jì)變量的個(gè)數(shù)，函數(shù)G和H為罰函數(shù)，λi和λj為懲罰系數(shù)。

(2)

(3)

2023/2/6湘潭大學(xué)信息工程學(xué)院?jiǎn)栴}1該問(wèn)題是一個(gè)帶靜平衡性能約束，且有等價(jià)待布物的約束布局優(yōu)化問(wèn)題。圓容器的半徑R＝70mm，待布物為6個(gè)圓盤(pán)，它們的半徑r1~r6分別為16.5、16.5、16.5、12.0、20.0和24.5mm，設(shè)靜不平衡量J的允許值為δJ，每個(gè)圓盤(pán)的質(zhì)量mi＝ri2(g)。要求給出滿足不干涉、靜平衡約束條件下，各待布物向容器中心高度聚集的布局方案。以容器中心為原點(diǎn)，向右且與容器和圓盤(pán)的表面重合的射線為x正半軸建立直角坐標(biāo)系。不計(jì)圓盤(pán)的厚度，其布局優(yōu)化模型如下：求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湘潭大學(xué)信息工程學(xué)院給出初始點(diǎn)X0，如圖1.18(a)所示，其中待布物OBJ1和OBJ2的形心重合。對(duì)應(yīng)局部最優(yōu)解的目標(biāo)函數(shù)＝63.976mm，向量函數(shù)＝89.903，用文獻(xiàn)的方法和準(zhǔn)邊界直線法分別構(gòu)造15個(gè)同構(gòu)和15個(gè)非同構(gòu)初始點(diǎn)，并采取罰函數(shù)法求出布局最優(yōu)解。表1.1是采用的兩種算法的計(jì)算結(jié)果比較，表中R為外包絡(luò)圓半徑，J為靜平衡量，t為計(jì)算時(shí)間。兩種方法的最優(yōu)布局方案如圖1.18(b)和(c)所示。

(a)

(b)

(c)

圖1.18問(wèn)題1的兩種布局方案

2023/2/6湘潭大學(xué)信息工程學(xué)院表1.1問(wèn)題1的計(jì)算結(jié)果比較

2023/2/6湘潭大學(xué)信息工程學(xué)院?jiǎn)栴}2印刷電路板設(shè)計(jì)問(wèn)題，它是一個(gè)要求待布物滿足一定鄰接關(guān)系的布局問(wèn)題，在二維空間放置15個(gè)待布物，待布物間的權(quán)值Wij(表示待布物在位置空間上的親密度)，要求待布物擺放時(shí)滿足下述條件：(1)待布物之間不干涉，(2)具有較大權(quán)重值的待布物應(yīng)相互聚集。即C＝的數(shù)值最小，其中dij為兩待布物之間的距離，(3)待布物的外包絡(luò)矩形面積最小。數(shù)學(xué)模型如下：式中S表示外包絡(luò)矩形的面積，λ為C相對(duì)于S的權(quán)重，

Ai和Aj分別待布物i和j

的面積，待布物間的權(quán)重矩陣如式(4)所示，半徑分別為12,3,12,3,9,10,7,8,4,12,6,10,9,9,10。2023/2/6湘潭大學(xué)信息工程學(xué)院(4)

2023/2/6湘潭大學(xué)信息工程學(xué)院(a)

PHAIA(b)H

CIGA(C)

HDCLDM(a)

CBRHGA圖

1.19問(wèn)題2的4種布局方案2023/2/6湘潭大學(xué)信息工程學(xué)院表1.2問(wèn)題2的4種計(jì)算結(jié)果比較

2023/2/6湘潭大學(xué)信息工程學(xué)院表1.3問(wèn)題2的4種布局方案的性能指標(biāo)

從表1.2和表1.3來(lái)看，CBRHGA的計(jì)算效率比HDCLDM方法提高了7倍，而包絡(luò)矩形的面積和權(quán)距，CBRHGA比HDCLDM方法分別減少了0.12%和1.17%；CBRHGA的計(jì)算效率比PHAIA方法提高了1.38倍，包絡(luò)矩形的面積和權(quán)距，CBRHGA比PHAIA方法分別減少了7.68%和10.72%；CBRHGA的計(jì)算效率比HCIGA方法提高了8.26倍，包絡(luò)矩形的面積和權(quán)距，CBRHGA比HCIGA方法分別減少了4.79%和16.79%。

2023/2/6湘潭大學(xué)信息工程學(xué)院?jiǎn)栴}3圖1.20

(b)是一種棱臺(tái)型衛(wèi)星的簡(jiǎn)化模型，艙體用厚度均勻的殼體制成一回轉(zhuǎn)體，空腔用于各儀器的布局空間；腔體中的底部承載板基面用以安裝各儀器，除此以外的地方均不能安裝任何儀器；承載板的厚度均勻，基面與旋轉(zhuǎn)體軸線垂直。圖1.20(a)是7.10(b)的二維平面布局圖。

圖1.20衛(wèi)星艙布局設(shè)計(jì)問(wèn)題2023/2/6湘潭大學(xué)信息工程學(xué)院以旋轉(zhuǎn)軸為z軸，以承載板中心為原點(diǎn)建立直角坐標(biāo)系如圖1.21(a)，衛(wèi)星艙及部件在xoz坐標(biāo)平面上的正投影圖如圖1.21(b)，其中，

Rt、R0和Ht分別是圓臺(tái)上、下底面圓半徑和圓臺(tái)的高度，T是承載板厚度。給定一組待安裝的儀器(待布物)，每個(gè)待布物的幾何尺寸、質(zhì)量、質(zhì)心位置均已知，布局完畢后整個(gè)艙體和保儀器以固定的角速度ω轉(zhuǎn)動(dòng)，要求布局滿足如下條件：

圖1.21衛(wèi)星艙的三維圖和xoz平面的投影圖2023/2/6湘潭大學(xué)信息工程學(xué)院(1)各儀器不得發(fā)生干涉，即互不重疊(實(shí)際工程中保證不小于規(guī)定的充許空間距離)；(2)各儀器的任何部分不得超出給定的布局空間，即不得與艙體發(fā)生干涉；(3)

各儀器盡可能地布局在艙體中心軸(z軸)附近，即各儀器的外包絡(luò)圓半徑應(yīng)盡量小，提高空間利用率；(4)

在滿足上述各項(xiàng)要求的前提下，應(yīng)使系統(tǒng)繞艙體中心軸(z軸)轉(zhuǎn)動(dòng)時(shí)產(chǎn)生的動(dòng)不平衡量和質(zhì)心偏移量都小于充許值，并且盡量小。根據(jù)上述條件和圖1.21的結(jié)構(gòu)，設(shè)艙內(nèi)待布物中，固定位置長(zhǎng)方體數(shù)為N1，固定位置圓柱體數(shù)為N2，可自由布局位置長(zhǎng)方體數(shù)為N3，可自由布局位置圓柱體數(shù)為N4，N＝N1＋N2＋N3＋N4。建立數(shù)學(xué)優(yōu)化模型的表達(dá)式如式(5)和(6)所示。

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

(5)

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

(6)

其中：(xi,yi)T∈R

2，xi,yi分別為各待布物質(zhì)心的x,y坐標(biāo)，設(shè)待布物為剛體，待布物的質(zhì)心與形重合，αi表示長(zhǎng)方體正投影矩形的轉(zhuǎn)角，它是以x正半軸為始邊，矩形的長(zhǎng)邊或其延長(zhǎng)線為終邊所成的角(αi∈[0,π])。F為艙體的動(dòng)不平衡力，M為艙體的質(zhì)心偏移量，其值由式(7)和(8)計(jì)算。

其中：mi為待布物i的質(zhì)量，ω為衛(wèi)星艙旋轉(zhuǎn)的角速度，hi為待布物i的質(zhì)心高度。

(7)

(8)

2023/2/6湘潭大學(xué)信息工程學(xué)院s.tintOBJi∩intOBJj=Ф

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

R*=min{(xi2+yi2)?+ri}其中：R*為各待布物的外包絡(luò)圓。結(jié)束準(zhǔn)則為式(9)和(10)。

(9)

(10)

其中：[εj]和[εm]分別為艙體的動(dòng)不平衡力和艙體的質(zhì)心偏移量的充許值。如圖1.21(b)所示的衛(wèi)星艙模型，艙旋轉(zhuǎn)的角速度為40r/min，Rt＝750mm，Ht＝800mm，T＝20mm。要在承載板上放置10個(gè)待布物，要求所有待布物盡量向中心2023/2/6湘潭大學(xué)信息工程學(xué)院集中。其中固定位置長(zhǎng)方體數(shù)為N1＝0，固定位置圓柱數(shù)為N,2＝1，可自由布局位置長(zhǎng)方體數(shù)為N3＝5，可自由布局位置圓柱體數(shù)為N4＝4，艙體的動(dòng)不平衡力的充許值[εj]＝20N，艙體的質(zhì)心偏移量的充許值[εm]＝10N.mm，其它初始數(shù)據(jù)見(jiàn)表1.4，建立式(5)～(10)的數(shù)學(xué)模型。

表1.4問(wèn)題3的待布物的初始數(shù)據(jù)

2023/2/6湘潭大學(xué)信息工程學(xué)院表1.5問(wèn)題2的4種布局方案的性能指標(biāo)

圖

1.22問(wèn)題3的3種布局方案2023/2/6湘潭大學(xué)信息工程學(xué)院從表表1.5和表1.6來(lái)看，CBRHGA方法的求解效率比HCIGA提高了35.50%，而包絡(luò)圓半徑減少了0.71%，動(dòng)不平衡力減少了9.43%，在x方向和y方向上的質(zhì)心偏移量則分別減少56.98%和12.56%；CBRHGA方法的求解效率比SGA提高了42.38%，而包絡(luò)圓半徑減少了1.19%，動(dòng)不平衡力減少了98.67%，在x方向和y方向上的質(zhì)心偏移量則分別減少99.43%和98.32%。

表1.6問(wèn)題3的3種計(jì)算結(jié)果比較

2023/2/6湘潭大學(xué)信息工程學(xué)院1.多目標(biāo)優(yōu)化問(wèn)題1.2機(jī)器人手臂碰撞檢測(cè)1.2.1拉格郎日乘子求解優(yōu)化問(wèn)題1.2.2機(jī)器人手臂的建模1.2.3手臂間最小距離表達(dá)1.2.4最小距離的優(yōu)化計(jì)算1.2.5機(jī)器人手臂碰撞檢測(cè)算法2023/2/6湘潭大學(xué)信息工程學(xué)院1.2.1拉格郎日乘子求解優(yōu)化問(wèn)題(1)等式約束非線性優(yōu)化問(wèn)題

minf(X)

s.t.gi(X)=0,i=1,2,…,m求解方法：將個(gè)方程分別乘以λ1,λ

2,…,λm，然后把它們的和加到目標(biāo)函數(shù)中去得到式(11)。

L＝f(x1,x2,,…,xn)+(11)對(duì)上述式()兩邊求m+n個(gè)變量的偏導(dǎo)數(shù)得方程組(12)，解方程組(12)得到問(wèn)題的解。(12)2023/2/6湘潭大學(xué)信息工程學(xué)院例如：現(xiàn)需設(shè)計(jì)一個(gè)廢水沉淀箱(如圖1.23)。但限定各個(gè)面壁加底板的總面積不得超過(guò)288m2

，應(yīng)如何設(shè)計(jì)尺寸使沉淀箱的容積最大。

解：它的目標(biāo)函數(shù)是：maxV=xyz

約束條件是S＝3yz＋xy＋2xz＝288m2

即約束優(yōu)化問(wèn)題：maxV=xyzs.t.3yz＋xy＋2xz-288=0

L=xyz-λ(3yz＋xy＋2xz-288)，兩邊對(duì)4個(gè)變量求偏導(dǎo)得式(13)

解方程組(13)得x:y:z=3:2:1,從而x=12m，y=8m，z=4m。(13)圖1.23廢水沉淀箱2023/2/6湘潭大學(xué)信息工程學(xué)院(2)不等式約束非線性優(yōu)化問(wèn)題

minf(X)

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

求解方法：將不等式約束轉(zhuǎn)化為等式約束，則得到：

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解：不等式約束轉(zhuǎn)化為等式約束有：

g1

(X)=3x1＋4x2-6＋x32＝0g2

(X)=-x1＋4x2-

2＋x42

＝02023/2/6湘潭大學(xué)信息工程學(xué)院引進(jìn)拉格朗日函數(shù)

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

2＋x42)(14)對(duì)上述式(14)兩邊求6個(gè)變量的偏導(dǎo)數(shù)得方程組，解方程組(14)得到問(wèn)題的解。但其求解是比較繁重的。2023/2/6湘潭大學(xué)信息工程學(xué)院(3)用庫(kù)恩－塔克條件求解約束非線性優(yōu)化問(wèn)題

minf(X)

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

求解方法：若X*是問(wèn)題(15)的極小值點(diǎn)，而且在X*點(diǎn)的各起作用約束的梯度線性無(wú)關(guān)，則存在向量Γ*＝(γ1*,γ2*,…,γl

*)T使得式(16)成立。(15)(16)條件(16)稱為簡(jiǎn)稱為K-T條件，滿足這個(gè)條件的點(diǎn)(當(dāng)然它也滿足非線性優(yōu)化問(wèn)題的所有約束條件)稱為庫(kù)恩-塔克點(diǎn)或稱為K-T點(diǎn)。γ1*,γ2*,…,γl

*為拉格朗日乘子。2023/2/6湘潭大學(xué)信息工程學(xué)院對(duì)于約束非線性優(yōu)化問(wèn)題

minf(X)

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

gj(X)≤0,j=1,2,…,l

求解方法：若X*是問(wèn)題(15)的極小值點(diǎn)，而且在X*點(diǎn)的各起作用約束的梯度▽hi(X*)(i=1,2,…,m)和▽gj(X*)(j∈J)線性無(wú)關(guān)，則存在向量∧

*＝(λ1*,λ2*,…,λl

*)T和Γ*＝(γ1*,γ2*,…,γl

*)T使得式(17)成立。滿足式(17)的點(diǎn)(當(dāng)然它也滿足非線性優(yōu)化問(wèn)題的所有約束條件)也稱為庫(kù)恩-塔克點(diǎn)或稱為K-T點(diǎn)。λ1*,λ2*,…,λ*m和γ1*,γ2*,…,γl

*稱為廣義拉格朗日乘子。(17)2023/2/6湘潭大學(xué)信息工程學(xué)院例如：用庫(kù)恩－塔克條件求解約束非線性優(yōu)化問(wèn)題

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

x

≤5

解：將問(wèn)題改寫(xiě)成：

minf(X)＝(x-3)2

g1(x)=x≥

0

g2(X)=5-x≥0

目標(biāo)函數(shù)和約束函數(shù)的梯度分別為:

▽f(x)＝2(x-3)，▽g1(x)＝1，▽g2(x)＝-1設(shè)x*為K-T點(diǎn)，引入廣義拉格朗日乘子γ1*

和γ2*

則該問(wèn)題的K-T點(diǎn)條件為式(18)。2023/2/6湘潭大學(xué)信息工程學(xué)院(18)

對(duì)于方程組(18)，考慮如下情形：(1)γ1*

≠0，γ2*

≠0，此時(shí)優(yōu)化問(wèn)題無(wú)解；(2)γ1*

≠0，γ2*

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

＝－6，但它們不是K-T點(diǎn)，故不是優(yōu)化問(wèn)題的解；(3)γ1*＝0，γ2*

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

＝－4，但它們不是K-T點(diǎn)，故不是優(yōu)化問(wèn)題的解；(4)γ1*＝0，γ2*

＝0，解之得x*＝3，它是K-T點(diǎn)，目標(biāo)函數(shù)值f(x*)=0。

因此，本優(yōu)化問(wèn)題的解為x*＝3。2023/2/6湘潭大學(xué)信息工程學(xué)院1.2.2機(jī)器人手臂建模機(jī)器人和障礙可以用圓柱體、長(zhǎng)方體、球和球臺(tái)的組合、多面體建模，而對(duì)于多機(jī)器人系統(tǒng)而言，使用這種建模會(huì)使計(jì)算量大大增加。為了兼顧精確度和計(jì)算量，機(jī)器人手臂的每個(gè)連桿用兩端帶半球的圓柱建模，而手腕、手爪以及被抓物體由一個(gè)球體建模，如圖1.24所示。這樣，雖然會(huì)使機(jī)器人的實(shí)際體積有所增加，但是卻減少了計(jì)算的復(fù)雜性。圖1.24機(jī)器人臂簡(jiǎn)化圖2023/2/6湘潭大學(xué)信息工程學(xué)院1.2.3

最小距離計(jì)算以線段為例計(jì)算2連桿之間的距離,設(shè)空間任意線段AB、CD的4個(gè)端點(diǎn)分別為，，。令則，，則由式(14)為：線段AB、CD任意兩點(diǎn)間距離的平方可以用式(15)表示。(14)其中a,b,c,d,e,f是常數(shù)，它與線段AB、CD的4個(gè)端點(diǎn)坐標(biāo)有關(guān)。dAB的最小值就是兩線段間的最小距離。(15)2023/2/6湘潭大學(xué)信息工程學(xué)院1.2.4最小距離的優(yōu)化計(jì)算下面采用Lagrange乘子和Kuhn-Tucker條件求dAB的最小值。記式(15)為：并且將0≤

x1≤1

,0≤

x2≤1改為下面不等式約束條件：引入松馳變量Sj，j=1,2,3,4將不等式約束轉(zhuǎn)化為等式約束：2023/2/6湘潭大學(xué)信息工程學(xué)院構(gòu)造lagrange函數(shù)式中λ為lagrange乘子。而含有不等式約束的Kuhn-Tucker條件可以表示為：結(jié)合2連桿之間的幾何性質(zhì)，共有9中情況需要考慮，如2023/2/6湘潭大學(xué)信息工程學(xué)院圖1.25所示。通過(guò)不同情況的組合可以分別求出在f(x1,

x2)為最小時(shí)x1,

x2的取值。圖1.25連桿距離的9種情況2023/2/6湘潭大學(xué)信息工程學(xué)院2023/2/6湘潭大學(xué)信息工程學(xué)院

最小距離就是9種不同情況下f(x1,

x2)的最小值。最后，將求得的最小距離與模型中兩圓柱體的半徑之和進(jìn)行比較，以判斷機(jī)器人手臂在運(yùn)動(dòng)過(guò)程中是否存在潛在的碰撞。2023/2/6湘潭大學(xué)信息工程學(xué)院2.偏微分方程數(shù)值解2.1拋物型方程的差分方法其中φ

(x),μ1(t),μ2(t)都是已知的連續(xù)函數(shù)，并且滿足相容性條件：φ

(0)＝μ1(0)，φ

(l)＝μ2(0)。該模型用于研究熱傳導(dǎo)和熱擴(kuò)散問(wèn)題，如鑄件凝固過(guò)程中溫度場(chǎng)模擬。(1)(1)熱傳導(dǎo)方程的第一邊值問(wèn)題如式(1)所示。2023/2/6湘潭大學(xué)信息工程學(xué)院

為了用有限差分方法求解式(1)，我們將求解區(qū)域G：0<x<l，0<t<T。用二族平行于坐標(biāo)軸的直線分割成矩形網(wǎng)格Gh,τ如圖2.1所示。兩直線分別是：

x＝xj

＝j(luò)h,

j=1,2,…,N

t＝tn

＝nτ,

n=1,2,…,J其中h＝l/N，τ＝T/J分別為x方向和時(shí)間t方向的步長(zhǎng)，交點(diǎn)(xj,tn)稱為節(jié)點(diǎn)，(xj＋?,tn＋?

)稱為分節(jié)點(diǎn)。圖2.1求解網(wǎng)格區(qū)域2023/2/6湘潭大學(xué)信息工程學(xué)院為了用有限差分方法求解式(1)，我們將求解區(qū)域G：0<x<l，0<t<T。用二族平行于坐標(biāo)軸的直線分割成矩形網(wǎng)格Gh,τ如圖2.1所示。兩直線分別是：

x＝xj

＝j(luò)h,

j=1,2,…,N

t＝tn

＝nτ,

n=1,2,…,J其中h＝l/N，τ＝T/J分別為x方向和時(shí)間t方向的步長(zhǎng)，交點(diǎn)(xj,tn)稱為節(jié)點(diǎn)。另外，我們有時(shí)還用到分節(jié)點(diǎn)(xj＋?,tn＋?

)，這里，xj＋?＝xj+h/2，tn＋?

＝

tn+τ/2

。

t＝tn上的全體節(jié)點(diǎn){(xj,tn)|j=0,2,…,N}稱為差分網(wǎng)格的第n層。2023/2/6湘潭大學(xué)信息工程學(xué)院顯式差分格式假定邊值問(wèn)題式(1)的解u(x,t

)有足夠的光滑性，用Ujn,分別表示邊值問(wèn)題式(1)的解u(x,t

)及其導(dǎo)數(shù)在節(jié)點(diǎn)處的值，上標(biāo)n表示第n層，不表示n次方。由泰勒展開(kāi)公式有式(2)成立。(2)由式(2)可得到式(3)(3)2023/2/6湘潭大學(xué)信息工程學(xué)院由泰勒展開(kāi)公式有式(4)和式(5)成立。(4)(5)由式(4)和式(5)可得到式(6)。(6)2023/2/6湘潭大學(xué)信息工程學(xué)院將式(3)和式(6)代入式(1)并舍去誤差項(xiàng)可得到式(7)。(7)式(7)的差分方程的逼近誤差為O(τ+h2)，稱此逼近關(guān)于τ是一階的，關(guān)于h是2階的。對(duì)初始條件和邊界條件作相應(yīng)逼近逼近，如式(8)。(8)式(7)和式(8)構(gòu)成邊值問(wèn)題式(1)的顯式差分格式。2023/2/6湘潭大學(xué)信息工程學(xué)院由式(7)和式(8)可得到差分方程的解式(9)。(9)其中。由式(9)可知：第n+1層任意一個(gè)內(nèi)節(jié)點(diǎn)處的值Ujn＋1可以由第n層的3個(gè)相鄰節(jié)點(diǎn)處的值Uj-1n,

Ujn,

Uj+1n決定。由于式(9)的右邊不含Ujn＋1，故稱之為顯示格式。隱式差分格式由泰勒展開(kāi)公式可得式(10)和式(11)。(10)2023/2/6湘潭大學(xué)信息工程學(xué)院(11)由式(10)和式(11)可得到式(12)。將式(3)和式(12)代入式(1)并舍去誤差項(xiàng)可得到式(13)。(12)(13)2023/2/6湘潭大學(xué)信息工程學(xué)院式(13)和式(8)構(gòu)成邊值問(wèn)題式(1)的隱式差分格式(14)。(14)式(14)是關(guān)于第n+1層上內(nèi)節(jié)點(diǎn)處的值U1n＋1,U2n＋1,…,UN-1n＋1的線性方程組。我們可以用追趕法或迭代法解此方程組求第n+1層上的值。由于不能直接解出Ujn＋1，故式(14)稱之為隱式格式。2023/2/6湘潭大學(xué)信息工程學(xué)院六點(diǎn)對(duì)稱格式式(7)兩邊乘以(1-θ)得到式(15)。(15)式(14)兩邊乘以θ得到式(16)。(16)式(15)+式(16)得到式(17)。(17)式(17)用到相鄰兩層六個(gè)點(diǎn)處的函數(shù)值，故稱為六點(diǎn)格式。2023/2/6湘潭大學(xué)信息工程學(xué)院當(dāng)θ＝1/2時(shí)，式(17)被簡(jiǎn)化為式(18)，它稱為六點(diǎn)對(duì)稱格式。它可以看作對(duì)點(diǎn)(xj,tn＋?

)作中心差商的結(jié)果。由于(18)因此格式(18)的截?cái)嗾`差為O(τ2+h2)，即對(duì)的逼近階提高了一次。由后面的證明可知：該格式是無(wú)條件穩(wěn)定的。2023/2/6湘潭大學(xué)信息工程學(xué)院式(18)和式(8)構(gòu)成邊值問(wèn)題式(1)的六點(diǎn)對(duì)稱差分格式(19)。其中：式(19

)對(duì)n=0,1,2,…,J可逐次用追趕法求解。(19)2023/2/6湘潭大學(xué)信息工程學(xué)院李查遜格式由泰勒展開(kāi)公式有式(20)和式(21)成立。(20)(21)式(20)-式(21)的差除以2τ可得到式(22)。(22)2023/2/6湘潭大學(xué)信息工程學(xué)院由泰勒展開(kāi)公式可得式(23)和式(24)。(23)(24)(25)式(23)+式(24)的和除以h2可得到式(25)。2023/2/6湘潭大學(xué)信息工程學(xué)院將式(22)和式(25)代入(1)得到式(26)，其截?cái)嗾`差為O(τ2

+h2)

。(26)