基于圖論和數(shù)值方法的幾何約束求解新算法的研究.pdf

1、幾何約束求解技術(shù)是基于約束滿足的參數(shù)化設(shè)計方法的核心技術(shù)之一，本文在對幾何約束求解技術(shù)的圖論方法和數(shù)值方法的分析研究基礎(chǔ)上，針對經(jīng)典方法的不足，從圖論方法和數(shù)值方法兩個角度提出了兩種改進的幾何約束求解算法——基于簇劃分的幾何約束分解算法和基于改進的量子遺傳算法的幾何約束求解算法。
　　首先，針對剪枝-歸約算法對高耦合約束問題處理上的不足，提出了基于簇劃分的幾何約束分解算法。該算法首先對約束圖進行簇劃分，并通過各個簇之間的關(guān)聯(lián)結(jié)點得

2、到約束圖的架構(gòu)圖，然后對架構(gòu)圖進行剪枝-歸約，從而求得約束問題的廣義求解序列。該算法在很大程度上降低了剪枝-歸約所作用圖形的耦合程度，能夠更好的發(fā)揮剪枝-歸約算法的性能。
　　其次，針對傳統(tǒng)數(shù)值迭代算法的初值敏感等問題，建立了幾何約束問題的優(yōu)化模型，采用量子遺傳算法進行幾何約束求解。針對傳統(tǒng)量子遺傳算法個體間信息交換不足易使算法陷入局部最優(yōu)的不足，提出了基于動態(tài)種群劃分的量子遺傳算法(DPDQGA);同時針對傳統(tǒng)量子遺傳算法無法充

3、分利用種群中未成熟個體信息的不足，提出了基于交互更新模式的量子遺傳算法(IUMQGA)。在DPDQGA算法中，使用兩個種群同時對解空間進行搜索，并通過動態(tài)的種群劃分過程來增加個體間信息的交換，避免了算法陷入局部最優(yōu)。在IUMQGA算法中使用交互更新策略將遺傳算法中的交叉操作利用量子門變換來實現(xiàn)，這不僅增加了個體間信息的交換而且充分利用了種群中未成熟個體的信息，提高了算法的收斂速度。
　　最后，對DPDQGA和IUMQGA進行了幾何