基于改進蟻群算法的液晶拼接屏選擇裝配

劉向勇

（中山市技師學院，廣東中山 528400）

0 引言

液晶拼接屏廣泛用于視頻監控中心、電力調度監控中心、大型演出背景、電視臺演播中心等場所，如圖1（a）所示。拼接縫的大小是衡量液晶拼接屏好壞的最直接標準，如圖1（b）所示。近5年，液晶拼接縫從6.7 mm到5.5 mm，再到3.5 mm、1.8 mm、1.4 mm等，整個行業開始逐步進入微拼接時代。

圖1 液晶拼接屏

拼接縫大小主要取決于2個方面：（1）拼接單元邊框，目前市場出現了非顯示區域僅為1.4 mm的超窄邊顯示屏；（2）現場安裝質量，拼接單元物理尺寸存在偏差（公差范圍內），如表1所示。在安裝拼接單元時，首先應精密測量各拼接單元物理尺寸，然后進行排列組合，以保證橫向縫隙和縱向縫隙的均勻性和直線性。如何科學選擇拼接單元進行裝配，是一個非常重要的課題。

如果一個液晶拼接項目為m行n列，那么這m×n臺拼接單元共有(m×n)!種組合方式。若廠家同批次生產了C臺拼接單元，且此次所接訂單均為m×n方案，則出廠時共有C/(m×n)個包裝，有 C×(C-1)×(C-2)×… ×(C-m×n-1)×(m×n)!種包裝方案，其中有一種組合包裝方案為最優組合（即組裝后的拼接屏橫向和縱向縫隙均勻性和直線性均最優）。實際裝中希望能獲得最優組合方案，但是如果采用窮舉試配方法，當m、n、C等數據不斷增大，存在的組合方案呈級數倍增長，運算時間趨于極限。為解決此問題，本文提出對智能蟻群算法進行改進，利用改進的優化算法進行輔助選擇裝配，能夠達到理想效果。

隨著計算機技術的飛躍發展，利用計算機進行輔助選擇裝配，以提高裝配精度和裝配質量，成為專家學者研究的熱點問題。如徐知行、劉向勇等[1-3]建立了計算機輔助選擇裝配質量目標函數模型。為更有效提升裝配質量，許多學者嘗試將智能優化算法引入計算機輔助裝配中，如葉小麗等[4]研究將蟻群算法用于電梯導軌選擇裝配。宋建軍等[5]探索利用改進蟻群算法進行邊緣連接的方法。

表1 三星55英寸拼接單元參數

1 安裝質量優化目標函數

定義裝配的優化目標函數為：

式中：η=S/N稱為裝配率；N為所有拼接單元使用完畢的總裝配數目；S為利用優化算法進行輔助選擇裝配所得到的合格的裝配數目[1]。

其中裝配精度：

式中：yl為裝配后的封閉環實際偏差；ES0、EI0分別為裝配設計時封閉環的上偏差和下偏差；Δ0=(ES0+EI0)/2為整條封閉環的中心偏差；T0=ES0-EI0為整條封閉環的公差。

由定義可知，Q越大裝配質量越高，而裝配率和裝配精度是互相矛盾的，需要找到1個平衡點。定義λ、μ∈[0,1]，為2個常數，分別表示裝配精度以及裝配率對整個裝配質量好壞的影響程度，λ越大，則裝配精度對裝配質量的影響越小，μ的作用同λ。

2 改進蟻群算法（ACO）在液晶屏選擇拼接中的應用

蟻群算法（ACO）在用于解決旅行商（TSP）問題時，蟻群的信息素設定是與螞蟻走過的路徑相關聯的[5-9]。但是在實際應用過程中，有時要解決特殊組合優化問題，采用將蟻群算法的信息素分布在節點模式時，其性能會更優于信息素分布在路徑模式，例如在解決流水作業（Flowshop）問題時。為此，本文在蟻群算法的整體框架內，提出建立一種將信息素分布為節點模式的算法模型，以解決液晶顯示屏拼接的問題。

2.1 基于改進蟻群算法拼接裝配的解構造圖建立

液晶拼接時存在橫向縫隙和縱向縫隙，本文提出一種帶約束的雙層螞蟻遍歷尋優方法，行、列進行分層尋優。在進行行尋優（匹配拼接單元的左右尺寸，即長）過程中，螞蟻應選擇寬偏差相同或相近的拼接單元進行裝配，此為約束。

首先進行行尋優，將m×n中的每行看作一個裝配鏈，則此裝配尺寸鏈的組成環數為n，節點aij表示裝配鏈O的第j個組成環的第i個要裝配的拼接單元，即O(j)=i，C臺拼接單元一共可以組成C/n個裝配鏈。詳細的構造方法和過程如下：首先建立1個C/n行n列矩陣，如圖2所示。把第j列的節點集合記為 Aj，弧（路徑）僅存于節點aij∈Aj和節點al(j+1)∈Aj+1間，且方向從aij指向al(j+1)。對虛擬起始點相應地有A0={a0}。

按照圖2所示進行行尋優結束后，再進行列尋優，即將每個行裝配鏈（共C/n個）當做1個部件（列裝配環），進行拼接裝配，此裝配尺寸鏈的組成環數為m，共組成C/(m×n)個裝配鏈，尋優方法如上所述。

圖2 行尋優的解構造圖模型

2.2 基于改進蟻群算法拼接裝配的數學描述

在對行進行尋優的過程中，在t時刻每只螞蟻將選擇下一個拼接單元，t+1時刻螞蟻將到達那里。定義由X只螞蟻在區間（t，t+1）內做的X次移動稱為蟻群算法的1次迭代，因此當算法進行n次迭代后，每只螞蟻都將完成1次完整的遍歷[3]。

假設螞蟻在t=0時從a0（虛擬起始點）出發，按遍歷的規則，分步為裝配鏈內的每個組成環選擇一個合適的拼接單元，并將此拼接單元的編號放入禁忌表R[X -1][n -1]中，便可以構造出一個完整的裝配鏈O。算法在進行解構造的第i步，當螞蟻x行進至節點aij時，且定義前面已構造好的部分節點序列（稱為可行部分解）為O′=O(j)時，螞蟻在約束條件（根據實際問題要求定）下將選擇訪問節點aij的可行鄰域，則：

式中：l?O′表示還沒被螞蟻x訪問的節點內的下一個節點ai(j+1)（ai(j+1)∈Aj+1）。

約束條件：螞蟻x應先判斷此拼接單元ai(j+1)寬偏差是否與aij一致（即應同為正偏差或同為負偏差），以此確保橫向縫隙的直線性，然后再進行下一步選擇。

定義Pi(j+1)(t)表示螞蟻x位于在按約束條件下已構造好的部分節點序列（可行部分解） O′=O(j)內，從節點aο(j)j移動到節點ai(j+1)的概率，其表達式如下：

式中：ηij(t)為能見度，是基于問題的啟發式信息。其計算公式如下：

式中：yx為本次迭代中截至t時刻第m只螞蟻訪問的所有拼接單元偏差和（此處偏差指的是拼接單元橫向尺寸偏差（即長偏差），下同）；yi(j+1)為t+1時刻第m只螞蟻在將要訪問的拼接單元 ai(j+1)的偏差；c為（0，1）間的常數；規定若|yx+yi,j-Δ0|=0，則Pix(j+1)(t)=1； τij(t)為節點 aij在t時刻的信息素濃度，為第j個組成環選擇第i個拼接單元的期望程度，其更新方法如下：

式中：ρ為信息素的余量系數；1-ρ則表示在t到t+n時刻之間節點信息素的揮發程度；Φ是常數；yx表示為第x只螞蟻完成的遍歷長度，yx的計算方法為：yx=，為到t+n時刻第x只螞蟻所經過的拼接單元的偏差，規定若|yx-Δ0|=0，則Δ=1。

2.3 改進蟻群算法的尋優過程

尋優過程如圖3所示。n次迭代完成之后，計算出每只螞蟻遍歷的長度yx，選取其中可用的。選取原則：選取 滿 足 EI0≤ys≤ES0，ES0表示封閉環的上偏差、EI0表示封閉還的下偏差。假設一共有S個符合要求，將滿足的ys從小到大排列，若 S≤C/n，則全部選用，否則，只選取前C/n個。

將 ys、S求出之后，將其代入目標優化函數求出Q值，便完成算法的1次循環。此迭代過程不斷重復，直到計數器達到由用戶自己定義的最大值NCmax。所有的Q值進行比較，最大的那個即表示一組較優的裝配組合。

行尋優完成之后再進行列尋優，列尋優方法與行尋優方法相同，只是每個項目只需1個列裝配鏈即可。在列尋優過程中，也需要進行約束，螞蟻在選擇1個行裝配鏈作為列裝配環時，首先需要比較相鄰兩個行裝配鏈中對應行裝配環長偏差是否相同或相近，確保縱向縫隙的直線性，然后再進行尋優。

圖3 尋優流程圖

3 仿真實驗

以1個4×6的液晶拼接屏項目為例進行仿真試驗，拼接單元尺寸如表1所示，由表1可知拼接單元上、下極限偏差分別為+1.0 mm和-1.0 mm。廠家共生產240臺拼接單元，需裝配10臺拼接屏，出廠時實測了每臺拼接單元的尺寸。建立以各拼接單元的實際偏差尺寸為元素的矩陣，作為節點模式的解構造圖。

若按照人工隨機選擇的方法進行裝配，先組裝40個行裝配鏈，然后再分別選擇4個行裝配鏈組裝成一臺4×6的拼接屏，共組裝10臺拼接屏。最終組裝質量為：裝配率η=100%，裝配精度ε=0.295，裝配質量Q=0.295，其中λ=μ=1。此時，寬偏差的均方差為0.549（此值表示橫向縫隙的直線性，0表示直線性最好）。

按照本文所闡述的基于改進蟻群算法的智能擇優方法計算，定義最大迭代次數NCmax=200，同樣λ=μ=1。在VC環境下進行編程，實現蟻群尋優過程，最終尋優結果為：η=100%，ε=0.797，Q=0.797。寬偏差的均方差為0.087，直線性接近最好。

將2種算法的結果進行對比可知，使用本文所提出的基于改進蟻群算法的智能選擇裝配方法，裝配質量遠優于人工隨機裝配。蟻群算法的尋優過程如圖4所示，可以看出改進蟻群算法收斂速度較快，能夠快速找到最優解。同時在尋優過程中，算法并沒有陷入局部尋優的困局。

圖4 裝配路徑尋優過程

4 結束語

文中所提出的方法適合液晶生產廠商使用，廠家在生產液晶拼接單元時，測量記錄各拼接單元的偏差尺寸。工作人員將偏差尺寸輸入計算機，經過算法的自主計算，將仿真模擬出最優的組裝方案。工人在出廠包裝時，將最優組合對應的各拼接單元進行編號，統一包裝在一起。現場安裝時，施工人員須按著編號將包裝匹配好的拼接單元進行安裝。按照本文方法進行操作，將會大大提高液晶拼接屏的裝配質量，減少返工及維修費用，節約安裝成本。