應(yīng)用于貼片機(jī)貼裝順序優(yōu)化的遺傳算法的比較和改進(jìn)

羅愛玲　龍緒明

摘 要： 元件貼裝順序優(yōu)化是決定貼片機(jī)生產(chǎn)效率的關(guān)鍵問題，傳統(tǒng)的解決貼裝順序優(yōu)化問題的方法有遺傳算法，蟻群算法，SS（傘布搜索法）等。使用較多的還是遺傳算法。遺傳算法中包含選擇算子、交叉算子、變異算子，且編程思想簡單，但容易出現(xiàn)局部最優(yōu)，過早收斂等情況。在此，通過對遺傳算法在貼裝順序優(yōu)化應(yīng)用的結(jié)果比較找到一種更適合的遺傳算法，使之擁有較快的收斂速度和全局優(yōu)化性。

關(guān)鍵詞： 元件貼裝順序優(yōu)化； 貼片機(jī)； 遺傳算法； 交叉算子

中圖分類號： TN919?34； TP202.7 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2014）06?0129?03

0 引 言

隨著電子產(chǎn)品裝配技術(shù)日新月異的發(fā)展，表面組裝技術(shù)（SMT），這一集電子元器件、組裝裝備和焊接技術(shù)為一體的綜合性技術(shù)得到了越來越廣泛的應(yīng)用[1]。表面組裝生產(chǎn)線的使用，加快了電子產(chǎn)品的生產(chǎn)效益，增強(qiáng)了產(chǎn)品的可靠性，與此同時大大降低了生產(chǎn)成本，使得電子產(chǎn)品裝配較之手工裝配發(fā)生了質(zhì)的飛躍。為進(jìn)一步地提高貼片機(jī)的性能，其關(guān)鍵因素之一就是提高貼片機(jī)的效率：即貼片機(jī)送料器的位置分配優(yōu)化和元器件的貼裝優(yōu)化。

這里假設(shè)送料器位置固定，來解決元器件的貼裝優(yōu)化問題。對于單臺貼片機(jī)而言，這個問題都屬于NP?Hard 問題，一般被規(guī)劃為旅行商問題（ Traveling Salesman Problem，TSP）[2]， 已有一些學(xué)者成功地用傳統(tǒng)的遺傳算法（GA）解決。但是，由于貼片機(jī)的發(fā)展， 它的結(jié)構(gòu)已經(jīng)變得更為復(fù)雜，其頭數(shù)已多達(dá)12頭， 甚至更多，解決貼裝順序優(yōu)化問題的方法近年來主要有：遺傳算法、蟻群算法、傘布搜索法以及差分算法。遺傳算法是進(jìn)化算法，主要通過選擇變異和交叉算子完成；蟻群算法是基于圖論的算法，通過信息素選擇交換信息；傘布搜索法屬于比較新的應(yīng)用于貼裝順序優(yōu)化的算法，目前國內(nèi)的研究報道少之又少，國外尚未有關(guān)此算法在貼裝優(yōu)化方面的研究應(yīng)用；差分算法是在遺傳算法的基礎(chǔ)上增加了遷徙進(jìn)化過程，使算法擁有更好的全局性，但較之遺傳算法編程思想比較麻煩。所以本文只討論遺傳算法的應(yīng)用，并對其進(jìn)行改進(jìn)，使貼裝優(yōu)化不僅編程簡便且擁有較好的全局性和收斂性。

1 遺傳算法的基本原理

20世紀(jì)50—60年代，一些科學(xué)家獨(dú)立開展了旨在可以成為工程問題優(yōu)化工具的進(jìn)化系統(tǒng)的研究。80年代以后，經(jīng)過相關(guān)領(lǐng)域?qū)＜覍W(xué)者的交流和共同努力，遺傳算法、ES、EP走向融合，構(gòu)成了進(jìn)化計(jì)算的思想和主要算法形式[3]。由于其不受搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性、倒數(shù)存在和單峰等假設(shè)，以及其固有的并行性，遺傳算法在最優(yōu)化、機(jī)器學(xué)習(xí)和并行處理領(lǐng)域得到了越來越廣泛的應(yīng)用。遺傳算法GA把問題的解表示成 “染色體”，在執(zhí)行遺傳算法之前，給出一群“染色體”，即假設(shè)解。然后把這些假設(shè)解放置于問題的“環(huán)境”中，按照適者生存的原則，較適應(yīng)環(huán)境的“染色體”被挑選出來進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。

2 貼片機(jī)的工作過程及數(shù)學(xué)模型

無論是全自動貼片機(jī)還是手動貼片機(jī)，無論是高速貼片機(jī)還是中低速貼片機(jī)，它的總體結(jié)構(gòu)均有類似之處。圖1是一種通用貼片機(jī)的內(nèi)部結(jié)構(gòu)示意圖，所示為12個吸嘴，其工作過程：PCB由傳送帶入口送入，傳送帶將PCB送到工作位置停板，定位針進(jìn)行夾緊，通過相機(jī)識別MARK點(diǎn)對PCB板完成定位后，PCB板固定，貼裝頭吸取元件通過x/y軸及R軸和Z軸的移動以一定的壓力把元件貼裝在有粘性的已經(jīng)印刷焊錫的焊盤上，即吸取?位移?定位?放置功能[4]，貼裝頭不斷地重復(fù)這樣的貼裝循環(huán)，直到所有元件貼裝完畢即完成貼裝。貼片機(jī)貼裝路徑優(yōu)化問題描述如下：已知印制板上各個元器件的裝配位置，尋求一個貼片機(jī)頭遍歷這些裝配位置的路徑，尋求開銷最小。

該問題與經(jīng)典的TSP問題有相似之處，即都是遍歷整個集合，求最小值問題。不同的是，貼片機(jī)貼裝要分批進(jìn)行，如一個4吸嘴的貼片頭一個貼裝循環(huán)內(nèi)只能貼裝4個元器件，一次循環(huán)結(jié)束后貼片頭要返回工料站進(jìn)行取料再開始下一個循環(huán)。所以整體來說，貼片機(jī)的貼裝優(yōu)化并不屬于TSP問題。貼片機(jī)貼裝時間需包括：取料時間、貼裝時間、循環(huán)間吸取原料的時間及棄料拋料時間等。整個貼片機(jī)的貼裝過程是一個比較復(fù)雜的過程，為使模型的建立稍微簡單些，必須犧牲掉一些不必要的環(huán)節(jié)，故參照文獻(xiàn)[5]做以下假設(shè)：

（1） 假設(shè)供料器位置為原點(diǎn)；

（2） 將整個貼裝過程中只做一次的動作例如PCB MARK點(diǎn)的定位省略；

（3） 假設(shè)每次貼片式貼裝頭在x，y方向運(yùn)動的時間均大于其貼裝頭的旋轉(zhuǎn)對中時間；

（4） 假設(shè)吸嘴吸片時間固定，為90 ms；貼片時間固定，為90 ms；

故類似文獻(xiàn)[6]，一個完整的貼裝時間可以表示為：

式中：[T1i]表示第i個循環(huán)內(nèi)總共的貼片頭移動時間；[T2i]表示貼片頭從第i個循環(huán)的最后一個元件貼裝完畢移動到下一個循環(huán)的第一個元件的貼裝位置所需要的時間；[ti]表示第i個元件的貼片時間，如上文所假設(shè)，一般每個元件的貼片時間一定；s表示總循環(huán)次數(shù)；n表示總元件個數(shù)。按距離遠(yuǎn)近x，y方向的運(yùn)動有加速?減速（短距離）、加速?恒速?減速（長距離）兩種形式。按給定運(yùn)動距離S、加速度a、恒速度v可得到對應(yīng)的運(yùn)動時間t的計(jì)算公式：

短距離：[t=4Sa]；長距離：[t=Sv+va]

式中v，a都是設(shè)定值。故求上式的最小值可簡化為[i=1sd1i+i=1s-1d2i]的最小值，d1表示貼裝循環(huán)內(nèi)貼片頭要移動的距離，d2表示循環(huán)間貼片頭要移動的距離。

3 算法

3.1 遺傳算法

遺傳算法在群體進(jìn)化過程中發(fā)生繁殖、雜交和突變現(xiàn)象，不斷發(fā)現(xiàn)重要基因[7]。尋找較好模式的過程中，高適應(yīng)度的個體被選擇的概率大于低適應(yīng)度的個體，則好的基因得以遺傳下來，不好的基因被剔除，隨著迭代次數(shù)的增加逐漸創(chuàng)造出更好的個體，同時也漸漸趨近于全局最優(yōu)解。

主要包括3部分：多樣性初始解集的產(chǎn)生；解集的改良更新，其中的算子包括復(fù)制算子、交叉算子和變異算子；最優(yōu)解的出現(xiàn)。

3.2 初始解集的產(chǎn)生

初始解集的特性對計(jì)算結(jié)果和計(jì)算效率有重要的影響，要實(shí)現(xiàn)全局最優(yōu)，初始解集在解空間上應(yīng)盡量分散，若按照隨機(jī)方法產(chǎn)生一組原始解集，可能會導(dǎo)致初始解集在解空間的分布不均進(jìn)而影響算法的性能。在遺傳算法中初始種群的各個個體間應(yīng)保持一定的距離，這樣的分布能使解在解空間上含有較豐富的模式，進(jìn)而增加搜索收斂全局最優(yōu)的可能性[8]。

3.3 復(fù)制算子

遺傳算法中通過個體的適應(yīng)值反映群體中個體的好壞程度，復(fù)制算子把當(dāng)前群體中的個體按照與適應(yīng)值成比例的概率復(fù)制到新的群體中。一般選用賭盤選擇的方法完成復(fù)制。

3.4 交叉算子

交叉算子是對整個染色體操作的，所以在遺傳算法中起核心作用，遺傳算法的收斂性主要取決于交叉算子的收斂性[9]。經(jīng)典的交叉算子包括： 單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、融合交叉、均勻交叉等。

3.5 變異算子

按概率對染色體的某一基因位（自變量的某一維）進(jìn)行一個微擾動或是取反。

4 算法的比較和改進(jìn)

以一個PCB板子上的20個元器件為例，其各個元件坐標(biāo)如下表所示，假設(shè)貼片頭上有4個吸嘴。這里初始染色體中有10個體，迭代次數(shù)為200，交叉概率為定值0.8，變異概率為定值0.2，采用多種遺傳算法的貼裝距離分別如表1所示。

如圖2所示，其中（a）結(jié)果收斂性和全局優(yōu)化性都差；（b）雖然收斂速度快，但全局性不好；（c）雖然獲得了好的全局性，但收斂速度慢；相比之下（d）的收斂速度和全局性都比較優(yōu)秀。

圖2（d）是在前3種遺傳算法上的改進(jìn)，算法步驟為：

（1） 初始化染色體，這里取染色體的個體為10；

（2） 按照賭盤選擇和適應(yīng)值的大小進(jìn)行復(fù)制。即將染色體中前5個適應(yīng)值高的個體直接復(fù)制給新的群體，剩下的5個解則按照賭盤選擇的方法進(jìn)行選擇，這樣不僅提高了群體的平均適應(yīng)值，也加快了算法的整體收斂速度；

（3） 對染色體按適應(yīng)度大小進(jìn)行排列，適應(yīng)度大的排在前面，小的排在后面；

（4） 從第一個染色體開始選取概率為Pc個染色體，每兩個進(jìn)行組合形成一對父代雙親，隨機(jī)產(chǎn)生一個交叉點(diǎn)k，并隨機(jī)產(chǎn)生一個小于從交叉點(diǎn)到最后節(jié)點(diǎn)個數(shù)的隨機(jī)數(shù)r，進(jìn)行交叉。

如假設(shè)P1=[1，4，3，7，2，5，6]，P2=[2，4，7，3，6，5，1]；

若隨機(jī)產(chǎn)生k=2，r=3；則P1′=[7，3，6，1，4，3，7，2，5，6]，P2′=[3，7，2， 2，4，7，3，6，5，1]；依次刪去重復(fù)的數(shù)得到新的子代個體：p1=[7，3，6，1，4，2，5]，p2=[3，7，2，4，6，5，1]；

（5） 分別比較2個父代和子代的適應(yīng)值，選擇適應(yīng)值最大的遺傳下來，作為最終的子代個體。這樣保證了每次都遺傳最好的基因，加快了最優(yōu)解出現(xiàn)的速度。

5 結(jié) 論

本文提出的遺傳算法，是在傳統(tǒng)遺傳算法基礎(chǔ)上的完善，通過改善復(fù)制算子和交叉算子并加入最后選擇算子，使新的交叉算子有更大的全局優(yōu)化性和更快的收斂性。相比于文獻(xiàn)[2]，文獻(xiàn)[2]是改進(jìn)過交叉算子的應(yīng)用，但迭代結(jié)果仍然上下波動，收斂效果不好；相比于文獻(xiàn)[10]雖然效果相似，但卻比其有著更簡便的編程思想。該方法得到最優(yōu)解更具有全局性，且速度也比較快。

參考文獻(xiàn)

[1] SRIHARI K， RAGHAVAN Sundarraman. A process planning system for PCB assembly using TAB and SMT [J]. Advanced Manufacturing Technology， 1994， 9： 311?318.

[2] 曾又姣，金燁.基于遺傳算法的貼片機(jī)貼裝順序優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2004，10（2）：205?208.

[3] 韓瑞鋒.遺傳算法原理與應(yīng)用實(shí)例[M].北京：兵器工業(yè)出版社，2009.

[4] 王燕.水平旋轉(zhuǎn)式貼片機(jī)貼裝過程優(yōu)化研究[D].西安：西安電子科技大學(xué)，2010.

[5] 袁鵬，劉海明，胡躍明.高速高精度多功能貼片機(jī)及產(chǎn)業(yè)化關(guān)鍵技術(shù)研究[D].廣州：華南理工大學(xué)，2005.

[6] 朱光宇，羅哲，陳志錦.基于差分算法的貼裝順序優(yōu)化問題求解[J].中國工程機(jī)械學(xué)報，2012，10（4）：391?397.

[7] 俞國燕，鄭時雄，劉桂雄，等.復(fù)雜工程問題全局優(yōu)化算法研究[J].華南理工大學(xué)學(xué)報，2000，28（8）：104?110.

[8] 袁鵬，劉海明，胡躍明.基于傘布搜索法的貼片機(jī)貼裝順序優(yōu)化算法[J].電子工藝技術(shù)，2007，28（6）：316?320.

[9] 翟梅梅.基于交叉算子改進(jìn)的遺傳算法求解TSP問題[J].淮南師范學(xué)院學(xué)報，2009，11（5）：114?119.

[10] 杜軒，李宗斌，高新勤，等.基于遺傳算法的轉(zhuǎn)塔式貼片機(jī)貼裝過程優(yōu)化[J].西安交通大學(xué)學(xué)報，2008，42（3）：295?299.

主要包括3部分：多樣性初始解集的產(chǎn)生；解集的改良更新，其中的算子包括復(fù)制算子、交叉算子和變異算子；最優(yōu)解的出現(xiàn)。

3.2 初始解集的產(chǎn)生

初始解集的特性對計(jì)算結(jié)果和計(jì)算效率有重要的影響，要實(shí)現(xiàn)全局最優(yōu)，初始解集在解空間上應(yīng)盡量分散，若按照隨機(jī)方法產(chǎn)生一組原始解集，可能會導(dǎo)致初始解集在解空間的分布不均進(jìn)而影響算法的性能。在遺傳算法中初始種群的各個個體間應(yīng)保持一定的距離，這樣的分布能使解在解空間上含有較豐富的模式，進(jìn)而增加搜索收斂全局最優(yōu)的可能性[8]。

3.3 復(fù)制算子

遺傳算法中通過個體的適應(yīng)值反映群體中個體的好壞程度，復(fù)制算子把當(dāng)前群體中的個體按照與適應(yīng)值成比例的概率復(fù)制到新的群體中。一般選用賭盤選擇的方法完成復(fù)制。

3.4 交叉算子

交叉算子是對整個染色體操作的，所以在遺傳算法中起核心作用，遺傳算法的收斂性主要取決于交叉算子的收斂性[9]。經(jīng)典的交叉算子包括： 單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、融合交叉、均勻交叉等。

3.5 變異算子

按概率對染色體的某一基因位（自變量的某一維）進(jìn)行一個微擾動或是取反。

4 算法的比較和改進(jìn)

以一個PCB板子上的20個元器件為例，其各個元件坐標(biāo)如下表所示，假設(shè)貼片頭上有4個吸嘴。這里初始染色體中有10個體，迭代次數(shù)為200，交叉概率為定值0.8，變異概率為定值0.2，采用多種遺傳算法的貼裝距離分別如表1所示。

如圖2所示，其中（a）結(jié)果收斂性和全局優(yōu)化性都差；（b）雖然收斂速度快，但全局性不好；（c）雖然獲得了好的全局性，但收斂速度慢；相比之下（d）的收斂速度和全局性都比較優(yōu)秀。

圖2（d）是在前3種遺傳算法上的改進(jìn)，算法步驟為：

（1） 初始化染色體，這里取染色體的個體為10；

（2） 按照賭盤選擇和適應(yīng)值的大小進(jìn)行復(fù)制。即將染色體中前5個適應(yīng)值高的個體直接復(fù)制給新的群體，剩下的5個解則按照賭盤選擇的方法進(jìn)行選擇，這樣不僅提高了群體的平均適應(yīng)值，也加快了算法的整體收斂速度；

（3） 對染色體按適應(yīng)度大小進(jìn)行排列，適應(yīng)度大的排在前面，小的排在后面；

（4） 從第一個染色體開始選取概率為Pc個染色體，每兩個進(jìn)行組合形成一對父代雙親，隨機(jī)產(chǎn)生一個交叉點(diǎn)k，并隨機(jī)產(chǎn)生一個小于從交叉點(diǎn)到最后節(jié)點(diǎn)個數(shù)的隨機(jī)數(shù)r，進(jìn)行交叉。

如假設(shè)P1=[1，4，3，7，2，5，6]，P2=[2，4，7，3，6，5，1]；

若隨機(jī)產(chǎn)生k=2，r=3；則P1′=[7，3，6，1，4，3，7，2，5，6]，P2′=[3，7，2， 2，4，7，3，6，5，1]；依次刪去重復(fù)的數(shù)得到新的子代個體：p1=[7，3，6，1，4，2，5]，p2=[3，7，2，4，6，5，1]；

（5） 分別比較2個父代和子代的適應(yīng)值，選擇適應(yīng)值最大的遺傳下來，作為最終的子代個體。這樣保證了每次都遺傳最好的基因，加快了最優(yōu)解出現(xiàn)的速度。

5 結(jié) 論

本文提出的遺傳算法，是在傳統(tǒng)遺傳算法基礎(chǔ)上的完善，通過改善復(fù)制算子和交叉算子并加入最后選擇算子，使新的交叉算子有更大的全局優(yōu)化性和更快的收斂性。相比于文獻(xiàn)[2]，文獻(xiàn)[2]是改進(jìn)過交叉算子的應(yīng)用，但迭代結(jié)果仍然上下波動，收斂效果不好；相比于文獻(xiàn)[10]雖然效果相似，但卻比其有著更簡便的編程思想。該方法得到最優(yōu)解更具有全局性，且速度也比較快。

參考文獻(xiàn)

[1] SRIHARI K， RAGHAVAN Sundarraman. A process planning system for PCB assembly using TAB and SMT [J]. Advanced Manufacturing Technology， 1994， 9： 311?318.

[2] 曾又姣，金燁.基于遺傳算法的貼片機(jī)貼裝順序優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2004，10（2）：205?208.

[3] 韓瑞鋒.遺傳算法原理與應(yīng)用實(shí)例[M].北京：兵器工業(yè)出版社，2009.

[4] 王燕.水平旋轉(zhuǎn)式貼片機(jī)貼裝過程優(yōu)化研究[D].西安：西安電子科技大學(xué)，2010.

[5] 袁鵬，劉海明，胡躍明.高速高精度多功能貼片機(jī)及產(chǎn)業(yè)化關(guān)鍵技術(shù)研究[D].廣州：華南理工大學(xué)，2005.

[6] 朱光宇，羅哲，陳志錦.基于差分算法的貼裝順序優(yōu)化問題求解[J].中國工程機(jī)械學(xué)報，2012，10（4）：391?397.

[7] 俞國燕，鄭時雄，劉桂雄，等.復(fù)雜工程問題全局優(yōu)化算法研究[J].華南理工大學(xué)學(xué)報，2000，28（8）：104?110.

[8] 袁鵬，劉海明，胡躍明.基于傘布搜索法的貼片機(jī)貼裝順序優(yōu)化算法[J].電子工藝技術(shù)，2007，28（6）：316?320.

[9] 翟梅梅.基于交叉算子改進(jìn)的遺傳算法求解TSP問題[J].淮南師范學(xué)院學(xué)報，2009，11（5）：114?119.

[10] 杜軒，李宗斌，高新勤，等.基于遺傳算法的轉(zhuǎn)塔式貼片機(jī)貼裝過程優(yōu)化[J].西安交通大學(xué)學(xué)報，2008，42（3）：295?299.

主要包括3部分：多樣性初始解集的產(chǎn)生；解集的改良更新，其中的算子包括復(fù)制算子、交叉算子和變異算子；最優(yōu)解的出現(xiàn)。

3.2 初始解集的產(chǎn)生

初始解集的特性對計(jì)算結(jié)果和計(jì)算效率有重要的影響，要實(shí)現(xiàn)全局最優(yōu)，初始解集在解空間上應(yīng)盡量分散，若按照隨機(jī)方法產(chǎn)生一組原始解集，可能會導(dǎo)致初始解集在解空間的分布不均進(jìn)而影響算法的性能。在遺傳算法中初始種群的各個個體間應(yīng)保持一定的距離，這樣的分布能使解在解空間上含有較豐富的模式，進(jìn)而增加搜索收斂全局最優(yōu)的可能性[8]。

3.3 復(fù)制算子

遺傳算法中通過個體的適應(yīng)值反映群體中個體的好壞程度，復(fù)制算子把當(dāng)前群體中的個體按照與適應(yīng)值成比例的概率復(fù)制到新的群體中。一般選用賭盤選擇的方法完成復(fù)制。

3.4 交叉算子

交叉算子是對整個染色體操作的，所以在遺傳算法中起核心作用，遺傳算法的收斂性主要取決于交叉算子的收斂性[9]。經(jīng)典的交叉算子包括： 單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、融合交叉、均勻交叉等。

3.5 變異算子

按概率對染色體的某一基因位（自變量的某一維）進(jìn)行一個微擾動或是取反。

4 算法的比較和改進(jìn)

以一個PCB板子上的20個元器件為例，其各個元件坐標(biāo)如下表所示，假設(shè)貼片頭上有4個吸嘴。這里初始染色體中有10個體，迭代次數(shù)為200，交叉概率為定值0.8，變異概率為定值0.2，采用多種遺傳算法的貼裝距離分別如表1所示。

如圖2所示，其中（a）結(jié)果收斂性和全局優(yōu)化性都差；（b）雖然收斂速度快，但全局性不好；（c）雖然獲得了好的全局性，但收斂速度慢；相比之下（d）的收斂速度和全局性都比較優(yōu)秀。

圖2（d）是在前3種遺傳算法上的改進(jìn)，算法步驟為：

（1） 初始化染色體，這里取染色體的個體為10；

（2） 按照賭盤選擇和適應(yīng)值的大小進(jìn)行復(fù)制。即將染色體中前5個適應(yīng)值高的個體直接復(fù)制給新的群體，剩下的5個解則按照賭盤選擇的方法進(jìn)行選擇，這樣不僅提高了群體的平均適應(yīng)值，也加快了算法的整體收斂速度；

（3） 對染色體按適應(yīng)度大小進(jìn)行排列，適應(yīng)度大的排在前面，小的排在后面；

（4） 從第一個染色體開始選取概率為Pc個染色體，每兩個進(jìn)行組合形成一對父代雙親，隨機(jī)產(chǎn)生一個交叉點(diǎn)k，并隨機(jī)產(chǎn)生一個小于從交叉點(diǎn)到最后節(jié)點(diǎn)個數(shù)的隨機(jī)數(shù)r，進(jìn)行交叉。

如假設(shè)P1=[1，4，3，7，2，5，6]，P2=[2，4，7，3，6，5，1]；

若隨機(jī)產(chǎn)生k=2，r=3；則P1′=[7，3，6，1，4，3，7，2，5，6]，P2′=[3，7，2， 2，4，7，3，6，5，1]；依次刪去重復(fù)的數(shù)得到新的子代個體：p1=[7，3，6，1，4，2，5]，p2=[3，7，2，4，6，5，1]；

（5） 分別比較2個父代和子代的適應(yīng)值，選擇適應(yīng)值最大的遺傳下來，作為最終的子代個體。這樣保證了每次都遺傳最好的基因，加快了最優(yōu)解出現(xiàn)的速度。

5 結(jié) 論

本文提出的遺傳算法，是在傳統(tǒng)遺傳算法基礎(chǔ)上的完善，通過改善復(fù)制算子和交叉算子并加入最后選擇算子，使新的交叉算子有更大的全局優(yōu)化性和更快的收斂性。相比于文獻(xiàn)[2]，文獻(xiàn)[2]是改進(jìn)過交叉算子的應(yīng)用，但迭代結(jié)果仍然上下波動，收斂效果不好；相比于文獻(xiàn)[10]雖然效果相似，但卻比其有著更簡便的編程思想。該方法得到最優(yōu)解更具有全局性，且速度也比較快。

參考文獻(xiàn)

[1] SRIHARI K， RAGHAVAN Sundarraman. A process planning system for PCB assembly using TAB and SMT [J]. Advanced Manufacturing Technology， 1994， 9： 311?318.

[2] 曾又姣，金燁.基于遺傳算法的貼片機(jī)貼裝順序優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2004，10（2）：205?208.

[3] 韓瑞鋒.遺傳算法原理與應(yīng)用實(shí)例[M].北京：兵器工業(yè)出版社，2009.

[4] 王燕.水平旋轉(zhuǎn)式貼片機(jī)貼裝過程優(yōu)化研究[D].西安：西安電子科技大學(xué)，2010.

[5] 袁鵬，劉海明，胡躍明.高速高精度多功能貼片機(jī)及產(chǎn)業(yè)化關(guān)鍵技術(shù)研究[D].廣州：華南理工大學(xué)，2005.

[6] 朱光宇，羅哲，陳志錦.基于差分算法的貼裝順序優(yōu)化問題求解[J].中國工程機(jī)械學(xué)報，2012，10（4）：391?397.

[7] 俞國燕，鄭時雄，劉桂雄，等.復(fù)雜工程問題全局優(yōu)化算法研究[J].華南理工大學(xué)學(xué)報，2000，28（8）：104?110.

[8] 袁鵬，劉海明，胡躍明.基于傘布搜索法的貼片機(jī)貼裝順序優(yōu)化算法[J].電子工藝技術(shù)，2007，28（6）：316?320.

[9] 翟梅梅.基于交叉算子改進(jìn)的遺傳算法求解TSP問題[J].淮南師范學(xué)院學(xué)報，2009，11（5）：114?119.

[10] 杜軒，李宗斌，高新勤，等.基于遺傳算法的轉(zhuǎn)塔式貼片機(jī)貼裝過程優(yōu)化[J].西安交通大學(xué)學(xué)報，2008，42（3）：295?299.