不規(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ī)則件排樣問(wèn)題的混合優(yōu)化方法。該方法首先把排樣和制造工藝聯(lián)系起來(lái)，將多邊形各邊向外擴(kuò)充，為零件預(yù)留加工余量；然后采用自組織特征映射模型(SOM)和 Hopfield 人工神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法，運(yùn)用 SOM 神經(jīng)網(wǎng)絡(luò)對(duì)初始在板材內(nèi)隨機(jī)排布

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

3、91.7 文獻(xiàn)標(biāo)識(shí)碼 文獻(xiàn)標(biāo)識(shí)碼：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é)約材料，提高材料利用率是實(shí)際生產(chǎn)中的一個(gè)基本原則，由于在工業(yè)生產(chǎn)中排樣問(wèn)題廣泛存在，因而解決它具有很深遠(yuǎn)的理論意義和現(xiàn)實(shí)意義。尋找通用性好、求解質(zhì)量和效率高、易于實(shí)現(xiàn)的排樣問(wèn)題求解算

8、法一直是該領(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)位置；李建勇[4]等人采用 Hopfield 神經(jīng)網(wǎng)絡(luò)對(duì)待排矩形零件進(jìn)行分組，通過(guò)恰當(dāng)選取分組數(shù)目，從而使排料對(duì)象放置到板材中，此方法運(yùn)用到不規(guī)則件排樣中需先

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

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

11、2i }表示。其中 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)生新的輸入向

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

13、，零件 Pi 的位置可根據(jù)以下公式來(lái)進(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í)率，隨時(shí)間 t 而減小，αk 的選取由零件 i 和其它零件的重疊面積最小這個(gè)條件來(lái)決定，其取值范圍為：0<αk≤1。鄰域隨時(shí)間 t 而減小，最后趨近于

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

15、并且這些神經(jīng)元按 M 行 N 列排列一個(gè) M*N 矩陣(稱為置換矩陣)，用 V 表示。當(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 次，故取 7 ? ? ? 9

16、? ? ? 360?M=40。根據(jù)拉格朗日乘子法構(gòu)造神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，將有約束的排樣優(yōu)化問(wèn)題轉(zhuǎn)化為非約束問(wè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