基于改進遺傳算法的細紗接頭路徑指引方法

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

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

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

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

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

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

1 問題描述與數學建模

1.1 問題描述

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

1.2 基本定義與假設

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

1.3 數學建模

1.3.1車間模型

結合國內外大多數紡紗廠細紗車間的實體布局，將細紗機的布局分為單排式細紗車間、并排式細紗車間和組合型細紗車間等，其中以單排式細紗車間為主。

1.3.2距離模型

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

圖1 距離模型及細紗機錠位布局

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

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

1.3.3目標函數

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

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

2 算法設計

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

2.1 貪心算法設計

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

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

圖2 貪心算法流程圖

2.2 遺傳算法設計

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

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

圖3 遺傳算法流程圖

2.2.1編碼及初始種群設計

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

2.2.2適應度函數設計

適應度函數在遺傳算法中用來評價每個個體在解決問題中的優劣，以此來評估算法性能。本研究對應數學模型的目標函數為最小值問題，所以適應度函數的構造如式（5）所示。

式中：fm為第m個個體的適應度函數；minPath為第m個個體對應的最短路徑值。

2.2.3遺傳操作設計

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

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

變異算子：根據變異概率，對群體中的每個個體將某一個或某一些基因的基因值改變為其他的等位基因值。

2.3 改進遺傳算法設計

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

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

圖4 改進遺傳算法流程圖

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

3 仿真試驗與數據分析

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

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

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

試驗仿真環境為Intel（R） Core（TM）i7-8750H CPU @ 2.20 GHz 2.21 GHz，內存24.0 GB，操作系統為Windows10，編程語言環境為Python3.10，集成開發環境為PyCharm2020。

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

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

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

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

表2 不同算法響應時間及算法效率提升值

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

4 結語

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

（1）相比傳統巡回式接頭方法，遺傳算法和改進遺傳算法在接頭路徑尋優上表現較好，其所得解明顯優于巡回式路徑和貪心算法路徑。由于貪心算法其結果只考慮局部最優，且實體細紗車間斷頭分布具有很大的隨機性，導致貪心算法在接頭路徑指引算法中的效果不佳，甚至會比傳統巡回式路徑結果更差。

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

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

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