不規(guī)則零件優(yōu)化排樣的神經(jīng)網(wǎng)絡(luò)混合優(yōu)化算法

1、不規(guī)則零件優(yōu)化排樣的神經(jīng)網(wǎng)絡(luò)混合優(yōu)化算法 不規(guī)則零件優(yōu)化排樣的神經(jīng)網(wǎng)絡(luò)混合優(yōu)化算法史俊友，蘇傳生，翟紅巖(青島科技大學(xué) 機(jī)電工程學(xué)院，山東 青島 266061)摘要： 摘要：提出一種利用人工神經(jīng)網(wǎng)絡(luò)求解不規(guī)則件排樣問題的混合優(yōu)化方法。該方法首先把排樣和制造工藝聯(lián)系起來，將多邊形各邊向外擴(kuò)充，為零件預(yù)留加工余量；然后采用自組織特征映射模型(SOM)和 Hopfield 人工神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法，運用 SOM 神經(jīng)網(wǎng)絡(luò)對初始在板材內(nèi)隨機(jī)排布

2、的不規(guī)則零件進(jìn)行平移，尋求各零件的最優(yōu)位置，然后運用 Hopfield 神經(jīng)網(wǎng)絡(luò)進(jìn)行迭代運算，尋求各排樣零件的最優(yōu)旋轉(zhuǎn)角度組合，實現(xiàn)自動排樣。算法可以解決不規(guī)則件和矩形件在規(guī)則板材以及不規(guī)則板材上的排樣問題，實例證明了該算法的有效性和實用性。關(guān)鍵詞： 關(guān)鍵詞：自組織特征映射模型； 自組織特征映射模型；Hopfield 人工神經(jīng)網(wǎng)絡(luò)；加工余量；不規(guī)則件；優(yōu)化排樣 人工神經(jīng)網(wǎng)絡(luò)；加工余量；不規(guī)則件；優(yōu)化排樣 中圖分類號 中圖分類號：TP 3

3、91.7 文獻(xiàn)標(biāo)識碼 文獻(xiàn)標(biāo)識碼：ANeural Networks Hybrid Algorithm for Irregular Parts Optimal Layout SHI Jun-you，SU Chuan-sheng，ZHAI Hong-yan (College of Mechanical and Electrical Engineering，Qingdao University of Science and Technol

4、ogy，Qingdao 266061，China )Abstract：An irregular parts layout method based on artificial neural networks is proposed in this paper. Firstly we link nesting problem with manufacturing process, every side of polygons is exp

5、anded in consideration of the machining allowance. Then Self-Organizing Map (SOM) and Hopfield artificial neural networks are integrated to look for the best position of the shaped parts and each part's optimum rotat

6、ing angle, complete the automatic layout. The algorithm can solve irregular parts nesting problem and rectangular parts nesting problem in the given nest region. Examples indicate that our algorithm is effective and prac

7、tical.Key words： Self-Organizing Map；Hopfield artificial neural networks；machining allowance；irregular parts；optimal layout最大限度地節(jié)約材料，提高材料利用率是實際生產(chǎn)中的一個基本原則，由于在工業(yè)生產(chǎn)中排樣問題廣泛存在，因而解決它具有很深遠(yuǎn)的理論意義和現(xiàn)實意義。尋找通用性好、求解質(zhì)量和效率高、易于實現(xiàn)的排樣問題求解算

8、法一直是該領(lǐng)域所追求的目標(biāo)[1]。人工神經(jīng)網(wǎng)絡(luò)具有自適應(yīng)性、自學(xué)習(xí)性、強容錯性和并行性等特性，已為模式識別、優(yōu)化技術(shù)和其它領(lǐng)域提供了新的技術(shù)[2]。利用人工神經(jīng)網(wǎng)絡(luò)求解組合優(yōu)化問題是一個既新穎又有前途的研究領(lǐng)域。黃兆龍[3]等人采用 SOM 神經(jīng)網(wǎng)絡(luò)尋求各排樣零件在排樣板材上的最優(yōu)位置；李建勇[4]等人采用 Hopfield 神經(jīng)網(wǎng)絡(luò)對待排矩形零件進(jìn)行分組，通過恰當(dāng)選取分組數(shù)目，從而使排料對象放置到板材中，此方法運用到不規(guī)則件排樣中需先

9、將不規(guī)則件進(jìn)行矩形外包絡(luò)再進(jìn)行排樣。用神經(jīng)網(wǎng)絡(luò)解決優(yōu)化問題的主要難點在于很難找到問題模型與神經(jīng)網(wǎng)絡(luò)之間的映射關(guān)系。本文將對這一問題進(jìn)行研究，將排樣和制造工藝聯(lián)系起來，將多邊形各邊向外擴(kuò)充，為零件預(yù)留加工余量，然后將 SOM 神經(jīng)網(wǎng)絡(luò)和 Hopfield 神經(jīng)網(wǎng)絡(luò)引入不規(guī)則零件排樣求解中，運用 SOM 神經(jīng)網(wǎng)絡(luò)對初始隨機(jī)排布的不規(guī)則零件進(jìn)行平移，尋求各零件的最優(yōu)位置，運用 Hopfield 神經(jīng)網(wǎng)絡(luò)尋求各排樣零件的最優(yōu)旋轉(zhuǎn)角度組合，最后得

10、到不規(guī)則件和矩形件在規(guī)則板材以及不規(guī)則板材上的排樣方案，并進(jìn)行了相應(yīng)的分析和軟件模擬計算，驗證算法的可行性和有效性。1 模型分析 模型分析零件在板材上的定位實際上只需 3 個參數(shù)即可完成。這 3 個參數(shù)是該零件的一個給定點在板材行排樣的網(wǎng)絡(luò)結(jié)構(gòu)模型[8]如圖 2 所示。其中，輸出神經(jīng)元對應(yīng)于零件的參考點；輸出神經(jīng)元之間的連接對應(yīng)于零件在板材上的重疊面積；輸入節(jié)點的數(shù)目與排料的維數(shù)相等。在算法中，每個零件的位置由向量 wi={w1i, w

11、2i }表示。其中 w1i，w2i 分別表示第 i 個零件參考點的 x，y 坐標(biāo)值。在學(xué)習(xí)過程中，輸入向量對應(yīng)于排樣區(qū)域中的隨機(jī)選擇點。自組織排樣的具體算法如下： Step1 初始化，t = 0(t 為迭代次數(shù))，通過給所有零件的位置向量設(shè)定很小的隨機(jī)值，使零件隨機(jī)分布在板料的中心附近；Step2 隨機(jī)選擇兩個零件，交換它們的位置，比較交換前后的兩個方案，如果新方案的面積矩不小于原方案，則不交換；Step3 產(chǎn)生新的輸入向

12、量 x(t) = {x1(t)，x2(t)}。輸入向量應(yīng)均勻分布在整個板料區(qū)域內(nèi)；Step4 確定最接近輸入向量的零件 j*，即與輸入向量歐幾里得距離最小的零件 pj*；Step5 計算學(xué)習(xí)率η(t)及 j*鄰域大小 nb(t)，對位于 j*鄰域之內(nèi)的零件的位置進(jìn)行更新，以使這些零件更加靠近當(dāng)前的輸入；Step6 如果重疊面積<εa 或 t = tmax，則停止；否則，增加 t，轉(zhuǎn)步驟 2。如果零件 Pi 位于零件 pj*的鄰域內(nèi)

13、，零件 Pi 的位置可根據(jù)以下公式來進(jìn)行更新：w1i,t= w1i,t-1+αk ηi,t(x1,t－w1i,t-1) (5)w2i,t= w2i,t-1+αk ηi,t(x2,t－w2i,t-1)其中，ηi,t 表示學(xué)習(xí)率，隨時間 t 而減小，αk 的選取由零件 i 和其它零件的重疊面積最小這個條件來決定，其取值范圍為：0<αk≤1。鄰域隨時間 t 而減小，最后趨近于

14、 0。3.2 優(yōu)化排樣問題到 優(yōu)化排樣問題到 Hopfield 人工神經(jīng)網(wǎng)絡(luò)的映射 人工神經(jīng)網(wǎng)絡(luò)的映射利用 Hopfield 人工神經(jīng)網(wǎng)絡(luò)求解優(yōu)化計算問題的思想是：首先把優(yōu)化的問題映射到一種神經(jīng)網(wǎng)絡(luò)的特定組態(tài)上，此組態(tài)相應(yīng)于優(yōu)化問題的可能解，然后構(gòu)造一個適合于待優(yōu)化問題的能量函數(shù)E，E 正比于優(yōu)化問題的代價函數(shù)。假設(shè)選擇 N 個不規(guī)則的零件在板材上排布，每個零件可以通過旋轉(zhuǎn)或鏡像而產(chǎn)生 M 種位置方式，則神經(jīng)網(wǎng)絡(luò)使用 N*M 個神經(jīng)元，

15、并且這些神經(jīng)元按 M 行 N 列排列一個 M*N 矩陣(稱為置換矩陣)，用 V 表示。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)時，此矩陣滿足如下條件：每列中有且只有一個神經(jīng)元的輸出為“1”,其余神經(jīng)元的輸出為“0”，表示每個零件只能被使用一次；每行中可有不定數(shù)目的神經(jīng)元的輸出為“1”，其它神經(jīng)元輸出為“0”，表示不同的零件可以有相同的排樣方式。研究表明，零件旋轉(zhuǎn)角度 時，各數(shù)據(jù)變換很小，取旋轉(zhuǎn)角度 ，則在 內(nèi)零件可以旋轉(zhuǎn) 40 次，故取 7 ? ? ? 9

16、? ? ? 360?M=40。根據(jù)拉格朗日乘子法構(gòu)造神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，將有約束的排樣優(yōu)化問題轉(zhuǎn)化為非約束問題。能量函數(shù)為：2, 1 , 11 1 1 1( 1) ( ) 2 2N m N m mxi xi y i y i ovi x i x y xA B E V V V V f ? ?? ? ? ? ?? ? ? ? ? ? ???(6) , 1 , 11 1( ) 2m m Nxi y i y i hvx y x iD V V V