布局問題的演化算法.pdf

1、布局問題來源于現(xiàn)代生產(chǎn)的許多領(lǐng)域并且表現(xiàn)為多種形式，如服裝行業(yè)，部件拼裝和超大規(guī)模集成電路(SLSI)。布局結(jié)果的好壞對行業(yè)生產(chǎn)的合理性、經(jīng)濟(jì)性和安全性等質(zhì)量指標(biāo)具有重要的影響，布局的過程也就是最優(yōu)化過程。布局問題屬于組合優(yōu)化問題而且是NP完全問題。雖然經(jīng)過幾代人的努力，但迄今尚無成熟的理論和有效的數(shù)值計算方法，因此布局問題的研究仍具有重要的理論和實際意義。演化計算是用計算機(jī)來模擬大自然的演化過程，特別是生命的進(jìn)化過程來求解復(fù)雜問題的一

2、類計算模型。在解決優(yōu)化問題的方法中，演化計算是一個強(qiáng)有力的工具。 遺傳算法是一種基于生物學(xué)進(jìn)化原理的搜索算法。文中把生物學(xué)中的遺傳、變異、交叉用于二維布局中，從多個父代個體中生成多個子代個體，根據(jù)目標(biāo)函數(shù)值的優(yōu)劣進(jìn)行淘汰。 文中通過對矩形物體基于布置點的布局方法進(jìn)行改進(jìn)，在引入新的個體表達(dá)方式和物體布局規(guī)則的基礎(chǔ)上，提出了求解矩形物體布局問題的分布估計算法并介紹了分布估計算法的主要特點。實例表明該算法優(yōu)于傳統(tǒng)的遺傳算法。