衛(wèi)星艙布局的若干圖形學(xué)問題研究.pdf

1、衛(wèi)星艙布局設(shè)計(jì)問題屬于NP-Hard或NP-Complete問題，它既存在計(jì)算復(fù)雜性又具有工程復(fù)雜性，求解困難，達(dá)到工程應(yīng)用要求更難。衛(wèi)星艙布局設(shè)計(jì)屬于衛(wèi)星總體布局設(shè)計(jì)的重要內(nèi)容，關(guān)系到衛(wèi)星性能、壽命、可靠性等問題。本課題組多年來從事衛(wèi)星艙布局設(shè)計(jì)研究，其中存在若干圖形學(xué)問題需要解決。為此，本文做了如下3個(gè)問題的研究：(1)由于布局與布局模式密切相關(guān)，研究了布局模式問題，并將它與遺傳算法相結(jié)合構(gòu)成基于布局模式的遺傳算法(Layout P

2、attern Based Genetic Algorithm，LPBGA)，用于求解2-D帶性能約束的布局問題；(2)在本課題給出的人機(jī)結(jié)合的遺傳算法中，需檢索先驗(yàn)布局圖作為參考圖，并轉(zhuǎn)化為數(shù)值解。為此研究了規(guī)則圖形檢測，又稱為圖形的形數(shù)轉(zhuǎn)換；(3)研究了圓柱體-圓柱體、長方體-長方體和凸多面體-凸多面體的快速干涉計(jì)算問題。在基于演化算法的衛(wèi)星艙復(fù)雜布局優(yōu)化過程中，每次迭代需要對待布物之間作干涉計(jì)算，因此，如何尋求迭代過程中快速3-D干

3、涉計(jì)算法是一個(gè)待解決的問題。將上述研究成果做為衛(wèi)星艙布局優(yōu)化的支撐方法和技術(shù)，也期望具有一定普遍性。 本文主要工作如下： 1.本文給出了基于完全關(guān)聯(lián)圖的布局模式構(gòu)造算法，它包括最小多邊形法和準(zhǔn)邊界直線法。本文的布局模式構(gòu)造方法不論待布物分布稀疏或密集都是適用的，并且準(zhǔn)邊界直線方法的計(jì)算復(fù)雜度也較低。進(jìn)而給出基于布局模式的遺傳算法，用于求解2-D帶性能約束的布局問題。其關(guān)鍵是在優(yōu)化迭代過程中的每一代，都自動構(gòu)造最優(yōu)個(gè)體的布

4、局模式解(個(gè)體)替代種群中較差的個(gè)體，跳出局部最優(yōu)，避免早熟以提高求解效率和解的質(zhì)量。經(jīng)2-D帶性能約束的布局設(shè)計(jì)的數(shù)值實(shí)驗(yàn)表明：本文方法與遺傳算法(GA)、人機(jī)交互遺傳算法(HCIGA)和并行混合螞蟻免疫算法(PHAIA)等相比，具有較高的精度和效率。 2.本文提出了一種3類圖形的快速檢測(圖形至數(shù)值變換)的廣義Hough變換方法。包括：(1)多個(gè)圓檢測；(2)多個(gè)矩形檢測；(3)混合多個(gè)圓、多個(gè)矩形檢測。由于減少了無效采樣和

5、無效計(jì)算，經(jīng)簡化衛(wèi)星艙布局的2-D規(guī)則圖形檢測等算例驗(yàn)證，提高了其檢測效率。 3.本文給出了圓柱體-圓柱體、長方體-長方體和凸多面體-凸多面體的快速不干涉檢測算法。先將3-D問題投影為2-D問題，然后基于不適合多邊形(no-fit polygon,NFP)對2-D問題實(shí)現(xiàn)快速不干涉檢測，凸多面體不干涉檢測算法還采用了向中心線正投影作不干涉加速檢測。經(jīng)遺傳天線布局問題等算例驗(yàn)證，表明了其有效性。 本文以衛(wèi)星艙布局問題為背景