王慶峰 黃克華 張立杰 李 輝 董相杰 曹玉勝 朱偉偉

（1.新疆大學(xué)，新疆烏魯木齊， 830046；2.新疆利華紡織有限公司，新疆阿克蘇， 843013；3.深圳紫光積陽科技有限公司，廣東深圳， 518100）

隨著物聯(lián)網(wǎng)、云計算、自動化和數(shù)據(jù)化等新一輪信息技術(shù)的不斷迭新，越來越多的紡紗廠開始推行紡紗過程智能化。紡紗主機設(shè)備自動化、連續(xù)化、數(shù)據(jù)化的廣泛應(yīng)用極大地提高了紡紗廠的生產(chǎn)效率和產(chǎn)品質(zhì)量，同時也大幅降低了工廠用人成本。

細(xì)紗工序作為紡紗中連接前后道工序的關(guān)鍵環(huán)節(jié)，其產(chǎn)品質(zhì)量和生產(chǎn)效率直接影響著紡紗廠的經(jīng)濟效益。在細(xì)紗工序中，細(xì)紗斷頭［1-2］是一種常見的生產(chǎn)現(xiàn)象，它會導(dǎo)致設(shè)備空錠、飛花、效率下降等問題，增加車間維護成本、設(shè)備消耗成本和原料成本，同時還會影響產(chǎn)品質(zhì)量和降低產(chǎn)量。因此，及時發(fā)現(xiàn)斷頭、準(zhǔn)確定位斷頭以及快速完成接頭是提高細(xì)紗工序效率的重要措施。

為了解決細(xì)紗斷頭監(jiān)測問題，國內(nèi)外研究人員通過不同的監(jiān)測形式和手段進行了探究。目前，市場上對于環(huán)錠紡斷頭監(jiān)測技術(shù)［3-5］主要以單錠監(jiān)測為主。單錠監(jiān)測系統(tǒng)主要分為光電式監(jiān)測和電磁式監(jiān)測兩種方式。兩種監(jiān)測系統(tǒng)都能夠通過細(xì)紗機車頭車尾的電子屏或指示燈實時監(jiān)測和定位每個錠子的斷頭、弱捻等情況。盡管單錠監(jiān)測系統(tǒng)的出現(xiàn)大大減輕了擋車工的勞動強度，提高了細(xì)紗車間的接頭效率，但擋車工仍然只能依靠單錠監(jiān)測系統(tǒng)提示完成視野范圍內(nèi)的斷頭接頭工作，無法實現(xiàn)全局高效的接頭。為了減少擋車工的勞動強度，大多數(shù)紡紗廠通過給擋車工配備接頭代步巡回小車來解決這一問題。隨著單錠監(jiān)測系統(tǒng)在細(xì)紗車間的普及［6］，利用單錠監(jiān)測系統(tǒng)錠位數(shù)據(jù)以及智能算法［7］對全局?jǐn)囝^進行算法調(diào)度，結(jié)合接頭代步巡回小車車載安卓屏進行指引工作，通過縮短整體接頭距離從而減少用工成本，以距離的最小化實現(xiàn)效率的最大化，具有很大的必要性。

目前，基于自動接頭機器［8］的不成熟性和安裝的高成本性，絕大多數(shù)的細(xì)紗車間接頭工作仍以擋車工巡回式接頭為主，國內(nèi)外對于接頭路徑調(diào)度［9］這一問題研究較少。對比傳統(tǒng)的擋車工巡回接頭模式，接頭耗時長這一問題對于車間整體生產(chǎn)效率的提升存在很大滯后性。遺傳算法［10-13］在路徑調(diào)度問題［14-15］中應(yīng)用較廣，但其對于初始種群的依賴性較強，所以傳統(tǒng)遺傳算法在個體種群較多的情況下算法迭代尋優(yōu)時間較長。針對這一問題，本研究將細(xì)紗單錠監(jiān)測系統(tǒng)與貪心算法［16］、遺傳算法相結(jié)合作比較，建立實體細(xì)紗車間的有效接頭路徑規(guī)劃模型，通過接頭代步巡回小車來減輕擋車工的勞動強度，通過巡回小車車載安卓屏路徑指引來提升車間整體斷頭的接頭效率。

1 問題描述與數(shù)學(xué)建模

1.1 問題描述

細(xì)紗接頭路徑指引問題是指在細(xì)紗車間中，如何安排擋車工或接頭代步巡回小車對車間內(nèi)實時已知總斷頭進行路徑規(guī)劃指引完成接頭工作。具體可描述為：1 個擋車工配備1 臺代步巡回小車管理一定區(qū)域內(nèi)的細(xì)紗機臺，此區(qū)域內(nèi)的斷頭由該擋車工進行接頭工作，擋車工通過車載安卓屏路徑指引顯示進行接頭工作，通過整體接頭路程最小化來實現(xiàn)紡紗車間的增益最大化。

1.2 基本定義與假設(shè)

考慮到接頭總路程與接頭時間和接頭速度有關(guān)，為了簡化巡回小車接頭路徑計算，作出以下定義與假設(shè)：1 個擋車工配備1 臺代步巡回小車負(fù)責(zé)管理特定區(qū)域內(nèi)的細(xì)紗接頭工作，各個擋車工無重復(fù)工作區(qū)域，接頭工作互不干擾，接頭途中小車的速度都保持勻速，且每個斷頭的接頭成功率和所需時間均相等，即該模型中滿足接頭巡回小車行駛總路程最小即可。

1.3 數(shù)學(xué)建模

1.3.1車間模型

結(jié)合國內(nèi)外大多數(shù)紡紗廠細(xì)紗車間的實體布局，將細(xì)紗機的布局分為單排式細(xì)紗車間、并排式細(xì)紗車間和組合型細(xì)紗車間等，其中以單排式細(xì)紗車間為主。

1.3.2距離模型

結(jié)合江西某紡織廠細(xì)紗車間實體布局，對單排式細(xì)紗車間中任意兩兩斷頭間的距離做算法設(shè)計。在單排式細(xì)紗車間中，以1 臺巡回小車管理6臺細(xì)紗機為例，建立如圖1 所示的坐標(biāo)系（上部為單臺細(xì)紗機錠位布局），坐標(biāo)軸比例以細(xì)紗機兩個相鄰錠位的距離長度為1 進行設(shè)計，橫縱軸比例為1∶1，且同一車弄的錠子設(shè)置相同的縱坐標(biāo)，為了模擬實際車間內(nèi)的距離，考慮到機臺本身的寬度以及車頭車尾無實際錠子，所以將這些位置用虛擬坐標(biāo)進行代替，結(jié)合實際測量值，細(xì)紗機寬度占15 錠，車尾占22 錠，車頭占38 錠。

圖1 距離模型及細(xì)紗機錠位布局

根據(jù)實體距離模型，對任意兩兩斷頭之間的距離做算法設(shè)計［17-18］，當(dāng)兩斷頭位于同一車弄時，距離值為橫坐標(biāo)差值的絕對值，當(dāng)兩斷頭位于不同車弄時，考慮到細(xì)紗機兩側(cè)都能夠通行，所以有兩種接頭方法，將這兩種方法距離作比較選取小值為距離值即可，具體設(shè)計如式（1）所示。

式中：D為任意兩兩斷頭之間的距離；w為細(xì)紗機臺長度（本例中w值為690）；（x1，y1）、（x2，y2）為車間內(nèi)任意兩個斷頭錠位實際坐標(biāo)。

1.3.3目標(biāo)函數(shù)

由于上述定義與假設(shè)，該模型中滿足巡回小車行駛總路程最小即可。即有：

式中：f為最短路徑；Path為路徑長度；di為第i-1 個斷頭到第i個斷頭之間的距離值；Di為初始位置到第i個斷頭的距離值；N為巡回小車所管理的細(xì)紗機臺的實時斷頭數(shù)。

2 算法設(shè)計

本研究分別對貪心算法、遺傳算法和改進遺傳算法接頭路徑模型做算法設(shè)計，結(jié)合傳統(tǒng)巡回式接頭路徑與3 種算法在效率、運行速度和解的質(zhì)量上的仿真測試，通過對比來驗證改進遺傳算法用于細(xì)紗接頭路徑指引方法的可行性。

2.1 貪心算法設(shè)計

貪心算法是一種常見的用于路徑調(diào)度的智能算法。其基本思想是在每一步中都采取當(dāng)前狀態(tài)下最優(yōu)選擇，而不考慮之后的影響。盡管它是一種局部最優(yōu)算法，但由于代碼復(fù)雜度低、運算速率高等優(yōu)點，使用貪心算法可以在較短時間內(nèi)為目標(biāo)函數(shù)找到一個較優(yōu)的可行解。

本研究首先使用貪心算法來解決細(xì)紗接頭路徑指引問題。通過單錠監(jiān)測系統(tǒng)讀取斷頭數(shù)據(jù)，根據(jù)兩兩斷頭間的距離模型計算公式對數(shù)據(jù)進行預(yù)處理。制定貪心策略：首先初始化斷頭列表并選擇第一個斷頭點，將其添加到列表中；接著，在剩余的斷頭點中，找到距離當(dāng)前斷頭點最近的目標(biāo)點，并將其添加到已遍歷過的列表中；在遍歷過程中，根據(jù)斷頭之間的實際距離更新當(dāng)前路徑的總長度，然后重復(fù)上述步驟直至遍歷完所有斷頭點，最后輸出最優(yōu)路徑與最優(yōu)距離即可。貪心算法流程圖如圖2 所示。

圖2 貪心算法流程圖

2.2 遺傳算法設(shè)計

遺傳算法是一種基于生物進化理論的優(yōu)化算法，其核心思想是通過模擬基因的遺傳、交叉和變異等過程來實現(xiàn)優(yōu)化問題的最優(yōu)解。遺傳算法具有全局搜索能力強、適應(yīng)性強、并行性強等優(yōu)點，因此在路徑規(guī)劃、機器學(xué)習(xí)、優(yōu)化設(shè)計等領(lǐng)域中都有著廣泛的應(yīng)用和研究。

鑒于遺傳算法的這些優(yōu)點，本研究的第二種算法設(shè)計將利用遺傳算法來解決細(xì)紗接頭路徑指引問題，該遺傳算法的流程設(shè)計圖如圖3 所示。

圖3 遺傳算法流程圖

2.2.1編碼及初始種群設(shè)計

基于單錠監(jiān)測系統(tǒng)的錠位識別功能，本研究遺傳算法的編碼方式采用實數(shù)編碼規(guī)則，以錠子為單位對提取的斷頭數(shù)據(jù)進行1 至N順序排列（N為總斷頭個數(shù)，表示染色體長度），即1 至N的亂序排列表示個體基因，一條染色體對應(yīng)一種接頭指引路徑；根據(jù)初始染色體隨機生成多個1 至N 的亂序排列作為遺傳算法的初始種群。

2.2.2適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)在遺傳算法中用來評價每個個體在解決問題中的優(yōu)劣，以此來評估算法性能。本研究對應(yīng)數(shù)學(xué)模型的目標(biāo)函數(shù)為最小值問題，所以適應(yīng)度函數(shù)的構(gòu)造如式（5）所示。

式中：fm為第m個個體的適應(yīng)度函數(shù)；minPath為第m個個體對應(yīng)的最短路徑值。

2.2.3遺傳操作設(shè)計

選擇算子：根據(jù)選擇概率，采用隨機遍歷抽樣法選擇一定數(shù)量的優(yōu)良個體，并將其存儲到下一代群體中。

交叉算子：根據(jù)交叉概率，采用部分匹配交叉，通過交叉概率在父代中隨機選擇一對染色體中幾個基因的起止位置（兩染色體被選位置相同），然后交換選中的兩組基因片段，根據(jù)兩基因片段之間的映射關(guān)系對父代依次做基因沖突檢測，保證生成的子代基因無沖突。

變異算子：根據(jù)變異概率，對群體中的每個個體將某一個或某一些基因的基因值改變?yōu)槠渌牡任换蛑怠?/p>

2.3 改進遺傳算法設(shè)計

當(dāng)涉及到路徑調(diào)度問題時，遺傳算法雖然應(yīng)用較廣，但存在許多的局限性。例如遺傳算法對初始種群的依賴性較強，導(dǎo)致算法容易陷入局部最優(yōu)，從而生成的結(jié)果具有很大的隨機性。此外，遺傳尋優(yōu)的能力與初始種群和迭代次數(shù)的設(shè)定有很大關(guān)聯(lián)，當(dāng)兩者值較大時，迭代尋優(yōu)所需時間也會相應(yīng)增長，這對于需要數(shù)據(jù)實時響應(yīng)這類問題存在很大的弊端（例如接頭指引），同時也非常消耗服務(wù)器資源；當(dāng)兩者值較小時，會使得迭代尋優(yōu)結(jié)果較差。

為了解決這些問題，本研究第三種算法設(shè)計將結(jié)合貪心算法思維復(fù)雜度低、代碼量小、運行效率高等優(yōu)點對遺傳算法做改進，算法具體流程設(shè)計如圖4 所示。具體而言：由于貪心算法生成的接頭路徑在實際車間中本就是一條較優(yōu)的唯一指引路徑，因此在遺傳算法初始種群的設(shè)計中，將20%的初始種群用貪心路徑替換，并隨機打亂整個初始種群，這就大幅降低了初始種群的隨機性。由于初始種群的較優(yōu)性，可以降低遺傳算法中初始種群和迭代次數(shù)的設(shè)定值，從而使遺傳算法的迭代尋優(yōu)能力大幅提高，并且更加高效、快速地進行計算。

圖4 改進遺傳算法流程圖

由于遺傳算法對于遺傳算子的依賴性較強，本研究在傳統(tǒng)遺傳算子的基礎(chǔ)上加入了進化逆轉(zhuǎn)操作和插入操作，以進一步改進算法。進化逆轉(zhuǎn)操作：對于每個子代，隨機選擇兩個位置，并將這兩個位置之間的染色體片段進行翻轉(zhuǎn)，如果翻轉(zhuǎn)后的適應(yīng)度更高，則替換原染色體，否則保持不變。插入操作：將父代按照適應(yīng)度函數(shù)從高到低進行排序，然后選擇適應(yīng)度高的子代替換適應(yīng)度低的父代，得到相同規(guī)模的新種群。

3 仿真試驗與數(shù)據(jù)分析

為了驗證改進遺傳算法對于細(xì)紗接頭指引方法的性能與可行性，以數(shù)學(xué)建模中的紡紗廠為例，根據(jù)建立的目標(biāo)函數(shù)分別對3 種算法進行仿真測試。以實體紡紗廠單錠監(jiān)測系統(tǒng)實時斷頭數(shù)據(jù)為試驗測試數(shù)據(jù)，隨機截取10 組不同規(guī)模的斷頭數(shù)據(jù)，分別對3 種算法進行仿真測試，并將測試結(jié)果與傳統(tǒng)巡回式路徑進行數(shù)據(jù)對比分析。

為了將巡回式路線簡單化，本研究將每組數(shù)據(jù)的接頭起點均固定，即根據(jù)圖1，選取y值最小前提下x值最小的點為接頭起始點。由于遺傳算法的結(jié)果具有一定的隨機性，因此在使用遺傳算法求解問題模型時，為了確保求得解的質(zhì)量，分別對每組數(shù)據(jù)進行5 次仿真，并求取平均值作為遺傳算法求解模型的結(jié)果。進行仿真測試的紗線品種為JC 18.5 tex，平均千錠時斷頭為19 根。

參數(shù)設(shè)置：遺傳算法中種群個數(shù)設(shè)置為160，最大迭代次數(shù)設(shè)置為300，選擇概率、交叉概率和變異概率依次設(shè)置為0.8、0.9、0.1；在改進遺傳算法中，由于對初始種群的改進，種群個數(shù)設(shè)置為60，最大迭代次數(shù)設(shè)置為160，選擇概率、交叉概率和變異概率依次設(shè)置為0.8、0.9、0.1。

試驗仿真環(huán)境為Intel（R） Core（TM）i7-8750H CPU @ 2.20 GHz 2.21 GHz，內(nèi)存24.0 GB，操作系統(tǒng)為Windows10，編程語言環(huán)境為Python3.10，集成開發(fā)環(huán)境為PyCharm2020。

對于10 組斷頭數(shù)據(jù)，分別計算其巡回式路徑、貪心算法路徑、遺傳算法路徑以及改進遺傳算法路徑長度值。為了驗證算法的可行性，分別對應(yīng)傳統(tǒng)巡回式路徑求其算法效率提升百分比，不同算法對應(yīng)接頭路徑長度值和算法效率提升值如表1 所示。

表1 不同算法對應(yīng)接頭路徑長度值和算法效率提升值

由表1 可以看出，貪心算法用于接頭路徑指引算法所得到的結(jié)果具有很大的隨機性，解的質(zhì)量很不穩(wěn)定，甚至在有些情況下比傳統(tǒng)巡回式路徑得到的結(jié)果更差，如數(shù)據(jù)5、數(shù)據(jù)6 和數(shù)據(jù)10。相比之下，遺傳算法和改進遺傳算法在接頭路徑尋優(yōu)上有著較好的表現(xiàn)，其所得解明顯優(yōu)于傳統(tǒng)巡回式路徑和貪心算法路徑。改進遺傳算法的效率提升百分比最高，平均效率提升為11.8%；其次是遺傳算法，平均效率提升為8.8%；貪心算法的效率提升百分比最小，平均效率提升為5.3%。改進遺傳算法可行性最好。

為了進一步評估改進遺傳算法的性能對于遺傳算法的性能提升，通過算法執(zhí)行到終端響應(yīng)總時間來評估算法的運行效率，并計算改進遺傳算法對遺傳算法響應(yīng)時間的效率提升百分比。不同算法響應(yīng)時間及算法效率提升值結(jié)果如表2所示。

表2 不同算法響應(yīng)時間及算法效率提升值

通過表2 可以看出，由于兩種算法對應(yīng)的遺傳參數(shù)值不同，改進遺傳算法響應(yīng)時間相比遺傳算法響應(yīng)時間縮短較多，平均為1.25 s。另外，可以看到遺傳算法的響應(yīng)時間波動較大，最短時間為3.72 s，最長時間為8.43 s；而改進遺傳算法響應(yīng)時間波動較小，最短時間為0.42 s，最長時間為1.50 s。對比兩種算法在響應(yīng)時間上的效率提升值，可得改進遺傳算法相比遺傳算法的平均時間效率提升為80.3%。由于硬件差別，表2 中的求解時間還受到計算機性能的影響。

4 結(jié)語

本研究基于細(xì)紗單錠監(jiān)測系統(tǒng)與啟發(fā)式智能算法，結(jié)合紡紗廠實體布局建模，針對細(xì)紗接頭路徑指引做了算法設(shè)計，并通過仿真試驗測試來驗證改進遺傳算法的性能和可行性，得到以下結(jié)論。

（1）相比傳統(tǒng)巡回式接頭方法，遺傳算法和改進遺傳算法在接頭路徑尋優(yōu)上表現(xiàn)較好，其所得解明顯優(yōu)于巡回式路徑和貪心算法路徑。由于貪心算法其結(jié)果只考慮局部最優(yōu)，且實體細(xì)紗車間斷頭分布具有很大的隨機性，導(dǎo)致貪心算法在接頭路徑指引算法中的效果不佳，甚至?xí)葌鹘y(tǒng)巡回式路徑結(jié)果更差。

（2）由于改進遺傳算法的參數(shù)設(shè)置值更小，且算法所得解相比遺傳算法5 次仿真平均值更小，相較于傳統(tǒng)巡回式路徑平均效率提升11.8%，說明改進遺傳算法具有較強的穩(wěn)定性和尋優(yōu)性。

（3）在響應(yīng)時間方面，遺傳算法的響應(yīng)時間波動較大，平均為6.35 s；而改進遺傳算法的響應(yīng)時間要比遺傳算法縮短較多，平均為1.25 s，且波動較小，相較于遺傳算法時間效率提升了80.3%，能夠大幅提升終端路徑顯示頁面的實時刷新速率。

綜上所述，由于改進遺傳算法在效率、運行速度和解的質(zhì)量上都優(yōu)于其他算法，所以改進遺傳算法在接頭路徑尋優(yōu)問題中可作為一種可行的較優(yōu)算法選擇。