基于遺傳算法與螞蟻算法的矩形件布局問題的研究與應用.pdf

1、布局問題來源于生產(chǎn)實際，廣泛存在于汽車制造、造船、制衣、玻璃加工、家具制造等行業(yè)。在當今各種能源材料短缺的情況下，提高板材利用率以節(jié)約原材料，降低成本，提高經(jīng)濟效益，對各行業(yè)均有重要意義。 布局問題涉及計算幾何、計算機圖形學、運籌學、邏輯推理等多學科知識，屬于具有最高計算復雜性的優(yōu)化計算問題，即NP完全問題。理論上至今仍沒有突破。由于生產(chǎn)實際的需要，人們又迫切需要利用現(xiàn)代科技得到一些能滿足生產(chǎn)規(guī)模較大的排料需要的求解方法。這些方

2、法能夠以較快的速度給出一個較好的解，雖然不是最優(yōu)解，但接近最優(yōu)解，并且比人工排樣效率高，能達到或超過人們所期望的材料利用率。 怎樣選擇若干個合適的矩形件進行優(yōu)化組合，合理確定它們的相對位置和方向，會在很大程度上影響到布局的最終效果，同時這也是矩形件優(yōu)化組合的難點所在。許多學者提出了很多的方法：遺傳算法、啟發(fā)式算法、模擬退火算法等優(yōu)化算法。本文在求解布局問題時，首先，取螞蟻算法和遺傳算法的各自長處，采用一套混合的遺傳螞蟻算法；并對

3、相應算法的改進，使新生成的混合算法搜索速度加快、優(yōu)化程度提高，基本思想是：算法前過程采用遺傳算法，充分利用遺傳算法的快速性、隨機性、全局收斂性，生成布局問題初始解，并將其轉(zhuǎn)化為蟻群算法的初始信息素分布；然后利用蟻群算法正反饋、高效收斂、的優(yōu)勢尋求最優(yōu)解。然后，針對遺傳算法和蟻群算法在矩形件布局問題中的實際特點，并分析了矩形件布局給定排放順序的排放算法，并提出了一種新的排放算法——最低水平線旋轉(zhuǎn)搜索法，并將這種算法和遺傳算法以及遺傳蟻群算