基于遺傳算法與螞蟻算法的矩形件布局問(wèn)題的研究與應(yīng)用.pdf

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

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

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