演化算法及其在工程布局設(shè)計(jì)中的應(yīng)用.pdf

1、本文研究演化算法及其在布局問題中的應(yīng)用，其工程背景是返回式衛(wèi)星回收艙布局設(shè)計(jì)和城市環(huán)境區(qū)域噪聲測量布點(diǎn)優(yōu)化問題。該課題在理論上，屬帶性能約束的具有NP難度的復(fù)雜問題，涉及機(jī)械工程、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、自動(dòng)化和系統(tǒng)工程、航天器設(shè)計(jì)、環(huán)境科學(xué)等學(xué)科，為交叉學(xué)科前沿課題的基礎(chǔ)理論和應(yīng)用基礎(chǔ)研究，具有挑戰(zhàn)性。在實(shí)踐上，具有廣泛的工程應(yīng)用前景，如航天器艙、車輛船舶、高速列車、水下懸浮工程、海上鉆井平臺(tái)、組合機(jī)床多軸箱、機(jī)器人等的布局方案設(shè)計(jì)問題。研

2、究的演化算法還可推廣應(yīng)用于求解多種復(fù)雜工程系統(tǒng)的優(yōu)化問題之中。因此，無論從理論上還是工程實(shí)踐上，該問題都是一個(gè)亟待較好解決的重要問題。 求解復(fù)雜工程布局問題的難點(diǎn)是存在計(jì)算復(fù)雜性的組合爆炸和工程實(shí)用化的復(fù)雜性。目前，針對(duì)復(fù)雜布局問題的主要求解方法有：數(shù)學(xué)規(guī)劃和準(zhǔn)則法、啟發(fā)式算法、圖論法、專家系統(tǒng)及演化算法等。數(shù)學(xué)規(guī)劃和準(zhǔn)則法有較為成熟的理論基礎(chǔ)，但存在局部收斂性質(zhì)，求解大規(guī)模問題較困難。啟發(fā)式算法可得到較好的解，然而它只能解決一

3、類限定的問題。圖論法利用“相鄰”、“距離”等關(guān)系，剪切了一些搜索分枝，卻也帶來了解空間不完備的問題。另外，它對(duì)空間的描述顯得較復(fù)雜。專家系統(tǒng)對(duì)于求解復(fù)雜布局問題的局限性在于專家知識(shí)的獲取和推理機(jī)制的設(shè)計(jì)較難。從算法的發(fā)展趨勢和求解效果而言，通用、穩(wěn)健、模擬自然法則的演化算法，如遺傳算法等，具有一定的求解優(yōu)勢，它們尤其適合于求解大型復(fù)雜問題。本文以演化算法中的遺傳算法為基礎(chǔ)，對(duì)其缺陷加以改進(jìn)，提出一種混合的智能并行演化算法，以便于更好地求

4、解工程布局設(shè)計(jì)問題。論文的主要內(nèi)容如下。 (1)給出本文研究課題的工程背景和意義，然后綜述了布局問題的求解算法及其國內(nèi)外有代表性的研究工作，并在其基礎(chǔ)上明確了本文使用混合演化算法求解復(fù)雜布局設(shè)計(jì)問題的這一求解思路。 (2)對(duì)演化算法進(jìn)行了較為深入的闡述，包括演化算法的理論基礎(chǔ)，各種算法的基本內(nèi)容和實(shí)現(xiàn)等。 (3)提出了混合粒子群免疫算法(HPSO-IA)。該算法以粗粒度并行遺傳算法(PGA)為基礎(chǔ)，針對(duì)其早熟和收

5、斂速度慢等缺陷，給出一系列相應(yīng)的改進(jìn)措施，主要有：a.依據(jù)改進(jìn)的自適應(yīng)交叉、變異算子對(duì)子群體分類，實(shí)行多種群的并行演化；b.根據(jù)不同類型子群體的特點(diǎn)，引入不同模式的個(gè)體PSO更新算子，其主要目的是充分利用粒子群算法收斂快的特點(diǎn)；c.加入免疫的思想可起到雙重效果，一方面基于提出的可調(diào)等差排序的免疫選擇算子能有效防止早熟，另一方面模擬免疫記憶和接種過程的子群體信息交換策略可加快收斂速度；d.對(duì)于優(yōu)秀個(gè)體的單純形和混沌搜索能顯著改善混合算法的

6、局部搜索性能。HPSO-IA有連續(xù)型和0-1離散型兩種版本，可同時(shí)用于解決上述兩類問題，是一種通用的混合演化算法。文中的算例(包括典型函數(shù)優(yōu)化問題和背包問題)表Ⅰ明了HPSO-IA是可行和有效的，確實(shí)優(yōu)于傳統(tǒng)的并行遺傳算法。 (4)將提出的演化算法應(yīng)用于工程布局設(shè)計(jì)問題，包括印刷電路板(PCB)設(shè)計(jì)為背景的加權(quán)圓集布局設(shè)計(jì)問題和圓容器裝填布局問題。重點(diǎn)以返回式衛(wèi)星回收艙的布局方案設(shè)計(jì)和城市環(huán)境區(qū)域噪聲測量布點(diǎn)優(yōu)化問題為實(shí)例，建立