1、作者簡(jiǎn)介：翟紅巖（1979），女，講師，研究方向：CAD/CAM/PDM，現(xiàn)代優(yōu)化技術(shù)蘇傳生（1984），男，碩士研究生，研究方向：現(xiàn)代優(yōu)化技術(shù)基于神經(jīng)網(wǎng)絡(luò)的不規(guī)則件排樣技術(shù)研究翟紅巖，蘇傳生，張瑩，史俊友(青島科技大學(xué) 機(jī)電工程學(xué)院，山東 青島 266061)摘要：提出一種利用人工神經(jīng)網(wǎng)絡(luò)求解不規(guī)則件排樣問(wèn)題的方法。對(duì)于二維不規(guī)則零件在排樣區(qū)域上的優(yōu)化排列問(wèn)題，采用自組織特征映射模型(SOM)和Hopfield人工神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法，尋找排樣件在排樣時(shí)的最優(yōu)位置及各自的旋轉(zhuǎn)角度，實(shí)現(xiàn)二維不規(guī)則件自動(dòng)排樣，得到滿意的優(yōu)化排樣結(jié)果，實(shí)例證明了該算法的有效性和實(shí)用性。關(guān)鍵詞：自組織特征映射模型；

2、Hopfield人工神經(jīng)網(wǎng)絡(luò)；不規(guī)則件；優(yōu)化排樣 中圖分類號(hào)：TP 391.7 文獻(xiàn)標(biāo)識(shí)碼：AThe optimal Layout technology research of irregular parts based on Artificial Neural NetworksZHAI Hong-yan，SU Chuan-sheng，ZHANG Ying，SHI Jun-you(College of Mechanical and Electrical Engineering，Qingdao University of Science and Technology，Qingdao266061，

3、China )Abstract：An irregular parts layout method based on artificial neural networks is proposed in this paper. For the irregular shapes nesting problem in the given nest region of two-dimensional irregular parts, Self-Organizing Map(SOM)and Hopfield artificial neural networks are integrated to look

4、 for the best position of the shaped parts and each parts optimum rotating angle, complete the automatic layout of two dimensional irregular parts, the satisfactory results of optimal layout have been obtained. Examples indicate that our algorithm is effective and practical.Key words：Self-Organizing

5、 Map；Hopfield artificial neural networks；irregular parts；optimal layout最大限度地節(jié)約材料，提高材料利用率是實(shí)際生產(chǎn)中的一個(gè)基本原則，由于在工業(yè)生產(chǎn)中排樣問(wèn)題廣泛存在，因而解決它具有很深遠(yuǎn)的理論意義和現(xiàn)實(shí)意義。尋找通用性好、求解質(zhì)量和效率高、易于實(shí)現(xiàn)的排樣問(wèn)題求解算法一直是該領(lǐng)域所追求的目標(biāo)1。人工神經(jīng)網(wǎng)絡(luò)具有自適應(yīng)性、自學(xué)習(xí)性、強(qiáng)容錯(cuò)性和并行性等特性，已為模式識(shí)別、優(yōu)化技術(shù)和其它領(lǐng)域提供了新的技術(shù)2。利用人工神經(jīng)網(wǎng)絡(luò)求解組合優(yōu)化問(wèn)題是一個(gè)既新穎又有前途的研究領(lǐng)域。黃兆龍3采用SOM神經(jīng)網(wǎng)絡(luò)尋求各排樣零件在排樣板材上的最優(yōu)位

6、置；李建勇4等人采用Hopfield神經(jīng)網(wǎng)絡(luò)對(duì)待排矩形零件進(jìn)行分組，通過(guò)恰當(dāng)選取分組數(shù)目，從而使排料對(duì)象放置到板材中。用神經(jīng)網(wǎng)絡(luò)解決優(yōu)化問(wèn)題的主要難點(diǎn)在于很難找到問(wèn)題模型與神經(jīng)網(wǎng)絡(luò)之間的映射關(guān)系。本研究將SOM神經(jīng)網(wǎng)絡(luò)和Hopfield神經(jīng)網(wǎng)絡(luò)引入排樣求解中，運(yùn)用SOM神經(jīng)網(wǎng)絡(luò)對(duì)初始隨機(jī)排布的零件進(jìn)行平移，尋求各零件的最優(yōu)位置，運(yùn)用Hopfield神經(jīng)網(wǎng)絡(luò)尋求各排樣零件的最優(yōu)旋轉(zhuǎn)角度組合，最后得到較好的排樣方案，并進(jìn)行了相應(yīng)的分析和軟件模擬計(jì)算，驗(yàn)證算法的可行性和有效性。1 模型分析1.1 數(shù)學(xué)模型一個(gè)零件在板材上的定位實(shí)際上只需3個(gè)參數(shù)即可完全確定。這3個(gè)參數(shù)是該零件的一個(gè)給定點(diǎn)在板材上的坐

7、標(biāo)(X，Y)和該零件的排放角度。當(dāng)這3個(gè)參數(shù)確定后，該零件的其它各頂點(diǎn)坐標(biāo)都可由這3個(gè)參數(shù)計(jì)算。設(shè)Gj(jJ，J為零件集合)為零件j的圖形，(xj，yj)為該零件的給定點(diǎn)的坐標(biāo)，則該零件在板材上的定位可以表示為下述過(guò)程：先將該零件以該定點(diǎn)為軸旋轉(zhuǎn)角度j，然后再將定點(diǎn)(xj，yj)在板材作位移(xj，yj)。這時(shí)零件j在板材上的方位可表示為Gj(xj，yj，j)。零件的數(shù)量為n，Sj為零件j的面積。L為板材的長(zhǎng)，D為板材的寬，排樣圖形外接矩形高度為H，寬度為W。定義排樣布局的原材料利用率，為排樣零件的面積和與排樣圖形外接矩形的面積的比值。零件優(yōu)化排樣的模型為5： (1)Gj (xj，yj，j )

8、Gk(xk，yk，k ) = ， jk (2)S.t. 0 Yji (xj，yj，j )L ji = 0，1， nj (3)0 Xji (xj，yj，j )D ji = 0，1， nj (4)式(2)表示零件j與零件k互不重疊；和為零件j的第i個(gè)頂點(diǎn)的坐標(biāo)，式(3)和式(4)表示零件不能排在板材之外。1.2 零件預(yù)處理使排樣問(wèn)題復(fù)雜化的主要原因是重疊性的計(jì)算，而重疊性計(jì)算的復(fù)雜性主要由零件的表達(dá)方式?jīng)Q定。因此，零件的表達(dá)方式是影響排樣問(wèn)題復(fù)雜程度的一個(gè)重要因素。加之考慮存儲(chǔ)和提取信息的方便，對(duì)實(shí)體的端點(diǎn)進(jìn)行排序處理，將零件表達(dá)成外輪廓逆時(shí)針走向、內(nèi)輪廓順時(shí)針走向的實(shí)體的集合。針對(duì)零件圖形內(nèi)部有

9、空白區(qū)域的情況，必須在不發(fā)生干涉的前提下，選擇合適的零件對(duì)內(nèi)空白區(qū)域進(jìn)行填充，以獲得優(yōu)化的排樣方案。另外，如果有多個(gè)零件都可以填充到一個(gè)空白區(qū)域中，則采用最佳面積適配法。設(shè)區(qū)域面積為SE，各零件面積為Si，且SiSE，計(jì)算S=min(SE - Si)，則S所對(duì)應(yīng)的零件即為填充的零件。圖1 SOM網(wǎng)絡(luò)結(jié)構(gòu)模型6Fig.1 The structure of SOM 62 算法描述2.1 自組織輔助排樣算法自組織輔助排樣算法使用Kohonen提出的自組織特征映射模型(SOM)進(jìn)行優(yōu)化排樣。SOM具有無(wú)監(jiān)督的學(xué)習(xí)結(jié)構(gòu)，是單層前饋網(wǎng)絡(luò)，所以它的學(xué)習(xí)速度很高。應(yīng)用自組織特征映射神經(jīng)網(wǎng)絡(luò)進(jìn)行排樣的網(wǎng)絡(luò)結(jié)構(gòu)模

10、型如圖1所示。其中，輸出神經(jīng)元對(duì)應(yīng)于零件的參考點(diǎn)；輸出神經(jīng)元之間的連接對(duì)應(yīng)于零件在板材上的重疊面積；輸入節(jié)點(diǎn)的數(shù)目與排料的維數(shù)相等。在算法中，每個(gè)零件的位置由向量wi=w1i, w2i 表示。其中w1i，w2i分別表示第i個(gè)零件參考點(diǎn)的x，y坐標(biāo)值。在學(xué)習(xí)過(guò)程中，輸入向量對(duì)應(yīng)于排樣區(qū)域中的隨機(jī)選擇點(diǎn)。自組織排樣的具體算法如下：Step1初始化，t = 0(t為迭代次數(shù))，通過(guò)給所有零件的位置向量設(shè)定很小的隨機(jī)值，使零件隨機(jī)分布在板料的中心附近；Step2隨機(jī)選擇兩個(gè)零件，交換它們的位置，比較交換前后的兩個(gè)方案，如果新方案的面積矩不小于原方案的面積矩，則不交換；Step3產(chǎn)生一個(gè)新的輸入向量x(

11、t) = x1(t)，x2(t)。輸入向量應(yīng)均勻分布在板料區(qū)域內(nèi)；Step4確定與輸入向量歐幾里得(Euclidean)距離最小的零件pj*；Step5計(jì)算學(xué)習(xí)率(t)及pj*鄰域大小nb(t)，對(duì)位于pj*鄰域之內(nèi)的零件的位置進(jìn)行更新，以使這些零件更加靠近當(dāng)前的輸入；Step6如果重疊面積小于a或t = tmax，則停止；否則，增加t，轉(zhuǎn)步驟2。2.2 優(yōu)化排樣問(wèn)題到Hopfield人工神經(jīng)網(wǎng)絡(luò)的映射利用Hopfield人工神經(jīng)網(wǎng)絡(luò)求解優(yōu)化問(wèn)題，將優(yōu)化問(wèn)題的目標(biāo)函數(shù)和限制條件映射為神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，使優(yōu)化解對(duì)應(yīng)于能量函數(shù)的極小值點(diǎn)，然后利用神經(jīng)網(wǎng)絡(luò)動(dòng)態(tài)特性，求出優(yōu)化問(wèn)題的解。要保證極小值是

12、合法的，能量函數(shù)取極小值時(shí)問(wèn)題的約束條件被滿足7。假設(shè)選擇N個(gè)不規(guī)則件在板材上排布，每個(gè)零件可以通過(guò)旋轉(zhuǎn)或鏡像而產(chǎn)生M種位置方式，則神經(jīng)網(wǎng)絡(luò)使用N*M個(gè)神經(jīng)元，并且這些神經(jīng)元按M行N列排列一個(gè)M*N矩陣，用表示。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)時(shí)，此矩陣滿足如下條件：每列中有且只有一個(gè)神經(jīng)元的輸出為“1”,其余神經(jīng)元的輸出為“0”，表示每個(gè)零件只能被使用一次；每行中可有不定數(shù)目的神經(jīng)元的輸出為“1”，其它神經(jīng)元輸出為“0”，表示不同的零件可以有相同的排樣方式。研究表明，零件旋轉(zhuǎn)角度時(shí)，各數(shù)據(jù)變換很小，取旋轉(zhuǎn)角度，則在內(nèi)零件可以旋轉(zhuǎn)40次，故取M=40。根據(jù)拉格朗日乘子法構(gòu)造神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，將有約束的排樣

13、優(yōu)化問(wèn)題轉(zhuǎn)化為非約束問(wèn)題。能量函數(shù)為： (5)圖2 不規(guī)則零件排樣過(guò)程流程圖Fig.2 The flow chart of the layout for irregular parts式(5)中x，y表示每個(gè)零件的不同位置，i，j表示不同的零件，Vxi表示矩陣中(x，i)單元的值；fov表示零件i，j的重疊面積，fhv表示排樣圖形外接矩形面積；式中A、B、D為正數(shù)，第1項(xiàng)為約束項(xiàng)，該項(xiàng)為0當(dāng)且僅當(dāng)每一列中只有一個(gè)神經(jīng)元的輸出為1，表示每個(gè)零件只能被使用一次且確保僅使用N個(gè)零件排樣；第2項(xiàng)為約束項(xiàng)，該項(xiàng)為0時(shí)，表示零件間的重疊面積為零；第3項(xiàng)為優(yōu)化項(xiàng)，保證原材料的利用率最高。2.3 神經(jīng)網(wǎng)絡(luò)應(yīng)用

14、于不規(guī)則件的求解過(guò)程首先用自組織輔助排樣算法對(duì)隨機(jī)排布的零件進(jìn)行平移，然后使用Hopfield神經(jīng)網(wǎng)絡(luò)進(jìn)行迭代運(yùn)算，對(duì)平移后的各個(gè)零件進(jìn)行旋轉(zhuǎn)，當(dāng)網(wǎng)絡(luò)狀態(tài)穩(wěn)定時(shí)，得到各零件的最佳旋轉(zhuǎn)角度。排樣過(guò)程流程圖如圖2所示。算法的具體步驟如下：Step1初始化，t = 0(t為迭代次數(shù))，零件隨機(jī)分布在板料的中心附近；Step2隨機(jī)選擇兩個(gè)零件，交換它們的位置，比較交換前后的兩個(gè)方案，如果新方案的面積矩不小于原方案的面積矩，則不交換；Step3產(chǎn)生一個(gè)新的輸入向量x(t) = x1(t)，x2(t)；Step4確定最接近輸入向量的零件j*，并計(jì)算學(xué)習(xí)率(t)及j*鄰域大小nb(t)；Step5對(duì)位于j*

15、鄰域之內(nèi)的零件的位置進(jìn)行更新；Step6如果重疊面積a或t = tmax，則轉(zhuǎn)步驟7。否則，增加t，轉(zhuǎn)步驟2；Step7 初始化Hopfield神經(jīng)元初始狀態(tài)和網(wǎng)絡(luò)參數(shù)A、B、D；Step8 計(jì)算能量函數(shù)的值。計(jì)算神經(jīng)元?jiǎng)討B(tài)方程，更新神經(jīng)元狀態(tài)；Step9 若相鄰兩次能量函數(shù)差小于給定值，如果輸出解合法，則輸出排樣結(jié)果，排樣結(jié)束；如果輸出解不合法，且迭代次數(shù)小于給定值，轉(zhuǎn)步驟8，否則計(jì)算失敗。圖3為神經(jīng)網(wǎng)絡(luò)算法的流程圖。圖3 神經(jīng)網(wǎng)絡(luò)算法流程圖Fig.3 The flow chart of neural networks algorithm3 軟件模擬計(jì)算及結(jié)果分析基于上述算法，筆者開(kāi)發(fā)了不規(guī)

16、則件優(yōu)化排樣系統(tǒng)。已證明系統(tǒng)能有效地解決任意二維不規(guī)則零件的最優(yōu)排樣問(wèn)題。以下算例可以證明此算法的有效性。在進(jìn)行模擬計(jì)算時(shí)，設(shè)置基本運(yùn)行參數(shù)：SOM神經(jīng)網(wǎng)絡(luò)最大迭代次數(shù)為tmax=10000、學(xué)習(xí)率=1/(t+1)、初始鄰域?yàn)榘宀膶挾鹊囊话?，以后每次迭代中鄰域減小為上次的一半；Hopfield最大迭代次數(shù)為1000，能量函數(shù)E參數(shù)A0.5， B0.8，D0.5；板材寬為600mm，排料零件數(shù)目為33，它們由計(jì)算機(jī)在零件庫(kù)中隨機(jī)選取。排樣結(jié)果如圖4(a)所示。 (a) (b)圖 4 排樣結(jié)果圖(a) 神經(jīng)網(wǎng)絡(luò)算法排樣結(jié)果 (b) NGSA算法排樣結(jié)果Fig.4 Layout drawing (a

17、) Layout drawing of neural networks algorithm (b) Layout drawing of NGSA神經(jīng)網(wǎng)絡(luò)算法與文獻(xiàn)8采用NGSA算法相比，系統(tǒng)運(yùn)行時(shí)間相對(duì)較短，同時(shí)由圖4a、b排樣結(jié)果圖可以看出神經(jīng)網(wǎng)絡(luò)算法在尋找排樣件最優(yōu)(排列最緊密)的排樣次序及各自的旋轉(zhuǎn)角度方面,均比NGSA好，可以獲得材料利用率更高的排樣方案，這也進(jìn)一步證明了采用神經(jīng)網(wǎng)絡(luò)算法的有效性。無(wú)論從定性分析還是運(yùn)行過(guò)程中的數(shù)值分析方面, 神經(jīng)網(wǎng)絡(luò)混合算法在搜索能力、優(yōu)化效率、魯棒性和多樣性等方面都具有明顯的優(yōu)越性；且能夠在很短的時(shí)間內(nèi)較精確地尋找到問(wèn)題的近似最優(yōu)解。 4 結(jié)語(yǔ)實(shí)踐證

18、明，本研究采用的神經(jīng)網(wǎng)絡(luò)混合優(yōu)化策略結(jié)合了SOM神經(jīng)網(wǎng)絡(luò)和Hopfield神經(jīng)網(wǎng)絡(luò)的特點(diǎn)，是一種優(yōu)化能力、效率和可靠性較高的優(yōu)化方法，能夠明顯地提高材料的利用率，帶來(lái)顯著的經(jīng)濟(jì)效益，它的研究對(duì)智能優(yōu)化理論的發(fā)展與應(yīng)用也很有意義。參考文獻(xiàn)1 Julia A Ben Nell，Kathryn A Downs-land，William B Downs-landThe irregular cutting-stock problem-a new procedure for deriving the no-fit polygonJComputers and Operations Research，2001，28：271-2872 王宏達(dá)，尚久浩，樊養(yǎng)余智能排樣算法分析與展望J機(jī)電工程技術(shù)，2004，33(10)：9-113 黃兆龍用啟發(fā)算法和神經(jīng)網(wǎng)絡(luò)法解決二維不規(guī)則零件排樣問(wèn)題