布局問(wèn)題的演化算法.pdf

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

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