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

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

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

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

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

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