布局知識(shí)圖矩形檢測(cè)與加權(quán)圓集裝填的啟發(fā)式搜索算法研究.pdf

1、容器裝填問題是將若干裝填物互不沖突地放進(jìn)一個(gè)容器中，要求容器的利用率最優(yōu)且滿足給定的約束。該問題的應(yīng)用背景包括：建筑設(shè)計(jì)、服裝行業(yè)、電子工業(yè)、航空航天、交通運(yùn)輸、機(jī)械制造、城市規(guī)劃等諸多領(lǐng)域。裝填方案的好壞直接影響著它們的生產(chǎn)效率、經(jīng)濟(jì)效益和系統(tǒng)的安全性等性能指標(biāo)。
　　容器裝填問題是眾多的裝填問題當(dāng)中最典型的一類，基于知識(shí)的求解方法是目前研究的熱點(diǎn)。本文討論布局知識(shí)的獲取與基于知識(shí)的帶性能約束裝填問題的求解方法。它具體包括：(i

2、)以印刷電路板的設(shè)計(jì)為背景討論圓形容器加權(quán)圓集裝填問題；(ii)以衛(wèi)星艙布局問題為背景討論圓容器布局知識(shí)圖的矩形檢測(cè)問題。對(duì)于(i)，由于其NP-hard屬性，難以在多項(xiàng)式時(shí)間內(nèi)求解。許多學(xué)者基于該問題的模型提出了各自的求解算法，它包括：?jiǎn)l(fā)式算法、免疫算法、人機(jī)交互、演化算法，如遺傳算法、蟻群算法和文化算法及粒子群算法等、混合算法等。目前的研究熱點(diǎn)是基于知識(shí)的求解算法。對(duì)于(ii)，目前的檢測(cè)方法包括：基于線段檢測(cè)的方法，窗口Houg

3、h變換方法和鏈碼檢測(cè)方法。但如何利用矩形的特征有效而快速檢測(cè)出矩形，特別是殘缺矩形，仍然需要進(jìn)一步研究。本文在國(guó)家自然科學(xué)基金項(xiàng)目、湖南省教育廳重點(diǎn)科學(xué)研究項(xiàng)目的資助下，分別對(duì)上述問題(i)和(ii)進(jìn)行了許多探索，并取得了一些研究成果。
　　其創(chuàng)新點(diǎn)如下：
　　(1)針對(duì)布局知識(shí)解參數(shù)計(jì)算問題，本文提出一種布局知識(shí)解的多個(gè)矩形檢測(cè)方法。它先隨機(jī)采樣兩個(gè)圖像點(diǎn)，并在以此兩點(diǎn)間的線段為直徑的圓周上搜索第3個(gè)圖像點(diǎn)來(lái)確定侯選矩形

4、，然后快速的確認(rèn)該候選矩形是否為真矩形。在隨機(jī)獲取兩個(gè)圖像點(diǎn)時(shí)，通過縮小樣本大?。ㄌ蕹铝ⅰ脒B續(xù)噪聲）減少無(wú)效采樣；在確定矩形時(shí)，利用矩形的特征確定它的另外兩個(gè)頂點(diǎn)，并給出了確認(rèn)侯選矩形為真矩形的方法，該方法快速有效能夠減少大量的無(wú)效計(jì)算。數(shù)值實(shí)驗(yàn)結(jié)果表明：本文提出的算法能快速檢測(cè)多矩形，對(duì)帶殘缺邊和對(duì)角的矩形檢測(cè)也非常有效。
　　(2)針對(duì)啟發(fā)算法搜索效率問題，本文提出一種加權(quán)圓集裝填的知識(shí)啟發(fā)式搜索算法。它以權(quán)矩陣各行和的絕