基于遺傳編程和OBDD的并行裝配規(guī)劃研究.pdf

1、裝配序列規(guī)劃是產(chǎn)品裝配規(guī)劃的重要內(nèi)容,序列好壞將直接影響產(chǎn)品的可裝配性和裝配質(zhì)量。20世紀(jì)90年代以來，國內(nèi)外諸多學(xué)者基于遺傳算法來解決裝配序列規(guī)劃問題，但多見于線性序列規(guī)劃。而遺傳編程是遺傳算法的發(fā)展算法，因其個(gè)體編碼采用了層次結(jié)構(gòu)從而本質(zhì)上區(qū)別于遺傳算法，其為有效解決并行裝配序列規(guī)劃問題提供了新的途徑。同時(shí)，有序二叉決策圖(Ordinary Binary Decision Diagrams，簡稱OBDD)可以有效地緩解問題處理過程中

2、狀態(tài)組合爆炸問題，對遺傳編程個(gè)體存在著改進(jìn)與優(yōu)化的可能。
　　針對上述問題，本文對裝配序列規(guī)劃、遺傳編程和OBDD三者主要內(nèi)容和相互關(guān)系進(jìn)行了分析，開展了相關(guān)方法和技術(shù)與應(yīng)用問題領(lǐng)域結(jié)合的研究。論文取得的主要工作進(jìn)展如下：
　　(1)成功使用遺傳編程方法來解決并行裝配序列規(guī)劃問題。通過對傳統(tǒng)的遺傳編程算法進(jìn)行改進(jìn)，刪除了遺傳編程符號集內(nèi)容，保留了終端集；并對遺傳編程有關(guān)算子及參數(shù)進(jìn)行設(shè)計(jì)與改進(jìn)，使算法最終能夠處理并行裝配序列

3、規(guī)劃問題。該方法使用樹型解結(jié)構(gòu)代替串型解結(jié)構(gòu)，轉(zhuǎn)變了裝配方式，提高了零件的裝配效率和自動化裝配水平。此外，還提出了一種新的裝配適應(yīng)度衡量因子—“裝配總重”，結(jié)合其他傳統(tǒng)適應(yīng)度衡量因子，共同評判裝配解的優(yōu)劣。
　　(2)在遺傳編程初始化算子基礎(chǔ)上，加入了啟發(fā)式權(quán)重信息和基于無向圖的廣度優(yōu)先搜索策略，保證了個(gè)體的可行度和高適應(yīng)度，加快了算法逼近全局最優(yōu)解的能力。并基于以上理論開發(fā)了實(shí)驗(yàn)程序，利用C++語言在Visual C++6.0環(huán)

4、境下完成了基于遺傳編程(Genetic Programming，簡稱GP)解決裝配序列規(guī)劃(assembly sequence planning，簡稱ASP)問題的軟件的設(shè)計(jì)與實(shí)現(xiàn)，并得到實(shí)驗(yàn)數(shù)據(jù)。
　　(3)對國外學(xué)者就GP個(gè)體提出的“內(nèi)含子”、語義等價(jià)等相關(guān)概念、以及語義驅(qū)動交叉算子（Semantically Driven Crossover，簡稱SDC）和語義驅(qū)動變異算子（Semantically Driven Mutati

5、on，簡稱SDM）進(jìn)行了深入分析；在此基礎(chǔ)上，對“內(nèi)含子”的分類和影響進(jìn)行了總結(jié)概括。詳細(xì)闡述了個(gè)體通過 OBDD消除個(gè)體“內(nèi)含子”的操作原理及如何實(shí)現(xiàn)個(gè)體語義等價(jià)評判。最后還對 GP處理 ASP問題領(lǐng)域中個(gè)體可能出現(xiàn)的語義等價(jià)情況進(jìn)行了簡要分析。
　　以上研究成果證明了遺傳編程方法處理并行裝配序列規(guī)劃問題的可行性和優(yōu)勢性。且遺傳編程在針對處理不同問題領(lǐng)域的特點(diǎn)時(shí)，具有豐富的可塑性；通過加入適當(dāng)?shù)膯l(fā)式算子或?qū)ο嚓P(guān)算子進(jìn)行改進(jìn)，從