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

劉向勇

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

0 引言

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

圖1 液晶拼接屏

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

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

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

表1 三星55英寸拼接單元參數(shù)

1 安裝質(zhì)量優(yōu)化目標函數(shù)

定義裝配的優(yōu)化目標函數(shù)為：

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

其中裝配精度：

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

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

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

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

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

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

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

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

圖2 行尋優(yōu)的解構造圖模型

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

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

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

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

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

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

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

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

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

2.3 改進蟻群算法的尋優(yōu)過程

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

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

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

圖3 尋優(yōu)流程圖

3 仿真實驗

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

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

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

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

圖4 裝配路徑尋優(yōu)過程

4 結束語

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