問題的數學模型與算法

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

研究生課程：

問題的數學模型與方法

(2011年上學期)授課：黎自強(教授)聯系電話：2023/2/6湘潭大學信息工程學院主要內容：

1.目標函數優(yōu)化問題

1.1遺傳算法求解復雜布局問題

1.2拉格郎日算子求解圓柱體碰撞檢測問題

2.偏微分方程數值求解

2.1鑄件凝固過程的溫度場模擬

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

a)發(fā)達國家航天器發(fā)展現狀

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

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

過去衛(wèi)星曾因總體布局不當，動不平衡過大，曾造成過早報廢的惡果。況且我國還要研制更復雜的空間站，其布局設計尤為重要。

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

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

b)二維布局問題

c)三維布局問題

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

a)一維布局問題

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

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

二維布局問題包括：一刀切問題

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

底盤裝載問題

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

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

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

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

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

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

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

2023/2/6湘潭大學信息工程學院例子約束底盤裝載和船舶配載問題

汽車駕駛艙布局問題

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

航天器艙布局方案設計問題

2023/2/6湘潭大學信息工程學院帶性能約束布局問題的算法

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

擬物擬人法

擬實驗綜合啟發(fā)式算法

八叉樹結構與定位―定序函數相結合的啟發(fā)式算法

GENET模型

Montreuil模型

膨脹算法

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

圖論作為組合數學的重要組成部分，在許多領域有著廣泛的應用。該方法一般將帶性能約束布局問題分兩步來求解。第一步，求出相鄰拓撲關系的無尺寸的平面布局，即根據待布物之間的確定位置關系構造一個圖，圖中節(jié)點代表各待布物，連接節(jié)點的邊表示待布物之間的確定位置關系。第二步，根據布局圖，利用優(yōu)化算法求出待布物之間的具體尺寸。

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

從布局策略上講，傳統的計算機輔助布局的思路，多將實際問題化為簡化的數學模型用計算機算法求解。由于數學模型過于簡化，即使能求得結果，但距離解決實際問題相差甚遠，因為實際的工程影響因素復雜，存在不可（或難以）數學模型化的問題；

從布局問題模型的描述上講，布局問題的有效、精確表達是解決問題的前提和基礎。目前多用數學模型，若模型簡單則不能概括必要內容，若模型過于復雜，又無法求解。另外，缺乏包含數學、仿真、符號的復合模型研究，缺乏將工程復雜布局問題從一個復雜工程系統角度去研究；

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

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

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

2023/2/6湘潭大學信息工程學院1.1.3航天器布局設計研究進展

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

2023/2/6湘潭大學信息工程學院圖1.6聯盟號飛船2023/2/6湘潭大學信息工程學院圖1.7空間站各艙段示意圖2023/2/6湘潭大學信息工程學院圖1.8空間站實驗艙標準柜2023/2/6湘潭大學信息工程學院圖1.9標準柜待布物優(yōu)化圖2023/2/6湘潭大學信息工程學院航天器艙布局方案設計

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

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

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

2023/2/6湘潭大學信息工程學院航天器其它組件的布局方案設計

航天器帆布局方案設計

航天器穩(wěn)定平臺布局方案設計

航天器姿控發(fā)動機布局方案設計

航天器氣動外形布局方案設計

航天器復雜插座板插孔布局方案設計

航天器電路板布局方案設計

2023/2/6湘潭大學信息工程學院太陽帆利用太陽光的壓力產生能量，保證航天器進行太空飛行。太陽光子不停地撞擊太陽帆，使得太陽帆所獲得的動量不斷增加。

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

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

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

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

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

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

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

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

圖1.16優(yōu)化氣動布局外形及尺寸參數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為群體規(guī)模大小尺寸，Φ為選擇算子，Γ為交叉算子，Ψ為變異算子，Τ遺傳運算終止條件。

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

隨機產生P0個初始種群，并對每一個種群，求出適應度函數的值。Step2判斷最優(yōu)個體是否滿足要求，如果滿足則輸出結果后轉Step6，否則執(zhí)行下一步。

Step3

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

對M個種群求出其適應度函數的值，按適應度大小選取其中的P0個種后轉Step2。Step6算法結束。

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

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

②

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

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

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

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

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

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

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

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

(2)

(3)

2023/2/6湘潭大學信息工程學院問題1該問題是一個帶靜平衡性能約束，且有等價待布物的約束布局優(yōu)化問題。圓容器的半徑R＝70mm，待布物為6個圓盤，它們的半徑r1~r6分別為16.5、16.5、16.5、12.0、20.0和24.5mm，設靜不平衡量J的允許值為δJ，每個圓盤的質量mi＝ri2(g)。要求給出滿足不干涉、靜平衡約束條件下，各待布物向容器中心高度聚集的布局方案。以容器中心為原點，向右且與容器和圓盤的表面重合的射線為x正半軸建立直角坐標系。不計圓盤的厚度，其布局優(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湘潭大學信息工程學院給出初始點X0，如圖1.18(a)所示，其中待布物OBJ1和OBJ2的形心重合。對應局部最優(yōu)解的目標函數＝63.976mm，向量函數＝89.903，用文獻的方法和準邊界直線法分別構造15個同構和15個非同構初始點，并采取罰函數法求出布局最優(yōu)解。表1.1是采用的兩種算法的計算結果比較，表中R為外包絡圓半徑，J為靜平衡量，t為計算時間。兩種方法的最優(yōu)布局方案如圖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)是一種棱臺型衛(wèi)星的簡化模型，艙體用厚度均勻的殼體制成一回轉體，空腔用于各儀器的布局空間；腔體中的底部承載板基面用以安裝各儀器，除此以外的地方均不能安裝任何儀器；承載板的厚度均勻，基面與旋轉體軸線垂直。圖1.20(a)是7.10(b)的二維平面布局圖。

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

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

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

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

在滿足上述各項要求的前提下，應使系統繞艙體中心軸(z軸)轉動時產生的動不平衡量和質心偏移量都小于充許值，并且盡量小。根據上述條件和圖1.21的結構，設艙內待布物中，固定位置長方體數為N1，固定位置圓柱體數為N2，可自由布局位置長方體數為N3，可自由布局位置圓柱體數為N4，N＝N1＋N2＋N3＋N4。建立數學優(yōu)化模型的表達式如式(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的質量，ω為衛(wè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)所示的衛(wèi)星艙模型，艙旋轉的角速度為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.多目標優(yōu)化問題1.2機器人手臂碰撞檢測1.2.1拉格郎日乘子求解優(yōu)化問題1.2.2機器人手臂的建模1.2.3手臂間最小距離表達1.2.4最小距離的優(yōu)化計算1.2.5機器人手臂碰撞檢測算法2023/2/6湘潭大學信息工程學院1.2.1拉格郎日乘子求解優(yōu)化問題(1)等式約束非線性優(yōu)化問題

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

即約束優(yōu)化問題：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)不等式約束非線性優(yōu)化問題

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)用庫恩－塔克條件求解約束非線性優(yōu)化問題

minf(X)

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

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

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

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

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)的點(當然它也滿足非線性優(yōu)化問題的所有約束條件)也稱為庫恩-塔克點或稱為K-T點。λ1*,λ2*,…,λ*m和γ1*,γ2*,…,γl

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

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，此時優(yōu)化問題無解；(2)γ1*

≠0，γ2*

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

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

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

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

＝0，解之得x*＝3，它是K-T點，目標函數值f(x*)=0。

因此，本優(yōu)化問題的解為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最小距離的優(yōu)化計算下面采用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)都是已知的連續(xù)函數，并且滿足相容性條件：φ

(0)＝μ1(0)，φ

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

為了用有限差分方法求解式(1)，我們將求解區(qū)域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)稱為節(jié)點，(xj＋?,tn＋?

)稱為分節(jié)點。圖2.1求解網格區(qū)域2023/2/6湘潭大學信息工程學院為了用有限差分方法求解式(1)，我們將求解區(qū)域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)稱為節(jié)點。另外，我們有時還用到分節(jié)點(xj＋?,tn＋?

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

＝

tn+τ/2

。

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

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

)及其導數在節(jié)點處的值，上標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層任意一個內節(jié)點處的值Ujn＋1可以由第n層的3個相鄰節(jié)點處的值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層上內節(jié)點處的值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)，即對的逼近階提高了一次。由后面的證明可知：該格式是無條件穩(wěn)定的。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)