基于改进鱼群算法的几何约束求解
|
摘要
几何约束求解是CAD建模中的关键技术,针对求解质量不高和求解速度慢的问题进行了研究,提出了一种鱼群算法和混沌算法相结合的几何约束求解方法。将CAD模型中的几何约束关系表示为一组代数方程组;利用代数方程组来构造目标函数,将几何约束求解问题转换为目标函数的优化问题;最后,使用混沌算法来改进鱼群算法以寻找目标函数的最优解。实验结果表明该方法可以有效地解决几何约束问题。
Geometric constraint solving is a key technique in CAD modeling. This paper researched the problem that solving quality was not high and solving speed was slow,and proposed a method of geometric constraint solving,which combined fish swarm algorithm and chaos algorithm. Firstly,this method denoted geometric constraint relations in CAD model as a group of algebraic equations. Secondly,it used the group of algebraic equations to construct objective function. It transformed a problem of geometric constraint solving into a problem of objective function optimization. Finally,it used chaos algorithm to improve fish swarm algorithm in order to find an optimal solution of objective function. Experimental results show that this proposed method can effectively solve geometric constraint problems.
Geometric constraint solving is a key technique in CAD modeling. This paper researched the problem that solving quality was not high and solving speed was slow,and proposed a method of geometric constraint solving,which combined fish swarm algorithm and chaos algorithm. Firstly,this method denoted geometric constraint relations in CAD model as a group of algebraic equations. Secondly,it used the group of algebraic equations to construct objective function. It transformed a problem of geometric constraint solving into a problem of objective function optimization. Finally,it used chaos algorithm to improve fish swarm algorithm in order to find an optimal solution of objective function. Experimental results show that this proposed method can effectively solve geometric constraint problems.
引文
[1]曹春红,唐川,赵大哲,等.量子行为粒子群优化算法在几何约束问题上的应用[J].东北大学学报:自然科学版,2011,32(9):1230-1232.(Cao Chunhong,Tang Chuan,Zhao Dazhe,et al.Application of quantum particle swarm optimization approach in geometric constraint problems[J].Journal of Northeastern University:Natural Science,2011,32(9):1230-1232.)
[2]戴春来.基于自由度分析的耦合几何约束求解[J].计算机辅助设计与图形学学报,2010,22(12):2169-2176.(Dai Chunlai.Resolving coupling geometric constraint problems with DOF analysis[J].Journal of Computer-Aided Design and Computer Graphics,2010,22(12):2169-2176.)
[3]周友行,张建勋,董银松,等.几何约束问题求解的方向可选指数进制步长优化算法[J].中南大学学报:自然科学版,2011,42(5):1327-1331.(Zhou Youhang,Zhang Jianxun,Dong Yinsong,et al.A variable step-size revisable optimization algorithm to solve geometry constraint[J].Journal of Central South University:Science and Technology,2011,42(5):1327-1331.)
[4]曹春红,王鹏,曹犁歌.基于D-tree分解的欠约束与完备约束的几何约束求解[J].东北大学学报:自然科学版,2014,35(5):627-629.(Cao Chunhong,Wang Peng,Cao Lige.Well-constrained and under-constrained geometric constraint solving based on D-tree decomposition[J].Journal of Northeastern University:Natural Science,2014,35(5):627-629.)
[5]Thierry S E.A particle-spring approach to geometric constraints solving[C]//Proc of the 26th ACM Symposium on Applied Computing.New York:ACM Press,2011:1100-1105.
[6]Mathis P,Schreck P.Coordinate-free geometry and decomposition in geometrical constraint solving[J].Computer-Aided Design,2014,50(5):51-60.
[7]Gao Xiaoshan,Lin Qiang,Zhang Guifang.A C-tree decomposition algorithm for 2D and 3D geometric constraint solving[J].ComputerAided Design,2006,38(1):1-13.
[8]De Regt R,Van der Meiden H A,Bronsvoort W F.A workbench for geometric constraint solving[J].Computer-Aided Design and Applications,2008,5(1-4):471-482.
[9]郭希娟,吴金垒.D-优化算法实现几何约束问题的重组[J].小型微型计算机系统,2011,32(9):1890-1893.(Guo Xijuan,Wu Jinlei.Restructuring of geometric constraint problem with D-optimization algorithm[J].Journal of Chinese Mini-Micro Computer Systems,2011,32(9):1890-1893.)
[10]曹春红,唐川,赵大哲,等.基于雁群启示的粒子群优化算法的几何约束求解[J].小型微型计算机系统,2011,32(11):2299-2302.(Cao Chunhong,Tang Chuan,Zhao Dazhe,et al.Geometric constraint solving based on Geese PSO optimization[J].Journal of Chinese Mini-Micro Computer Systems,2011,32(11):2299-2302.)
[11]曹春红,易荣庆,曹海龙,等.交互更新模式的量子遗传算法的几何约束求解[J].中国图象图形学报,2016,21(4):499-509.(Cao Chunhong,Yi Rongqing,Cao Hailong,et al.Solving geometric constraint based on the interactive update mode quantum genetic algorithm[J].Journal of Image and Graphics,2016,21(4):499-509.)
[12]黄学良,王蕾,王旗华,等.三维几何约束系统的在线增量求解方法[J].计算机辅助设计与图形学学报,2017,29(8):1571-1578.(Huang Xueliang,Wang Lei,Wang Qihua,et al.An online incremental solving method for 3D geometric constraint systems[J].Journal of Computer-Aided Design and Computer Graphics,2017,29(8):1571-1578.)
[13]李文辉,孙明玉,曹春红.几何约束求解的扩展C-树分解法[J].吉林大学学报:工学版,2017,47(4):1274-1279.(Li Wenhui,Sun Mingyu,Cao Chunhong.Extension C-tree decomposition method for geometric constraint solving[J].Journal of Jilin University:Engineering and Technology Edition,2017,47(4):1274-1279.)
[14]王书亭,王战江.粒子群优化算法求解非线性问题的应用研究[J].华中科技大学学报:自然科学版,2005,33(12):4-7.(Wang Shuting,Wang Zhanjiang.Study of the application of PSO algorithms for nonlinear problems[J].Journal of Huazhong University of Science and Technology:Natural Science Edition,2005,33(12):4-7.)
[2]戴春来.基于自由度分析的耦合几何约束求解[J].计算机辅助设计与图形学学报,2010,22(12):2169-2176.(Dai Chunlai.Resolving coupling geometric constraint problems with DOF analysis[J].Journal of Computer-Aided Design and Computer Graphics,2010,22(12):2169-2176.)
[3]周友行,张建勋,董银松,等.几何约束问题求解的方向可选指数进制步长优化算法[J].中南大学学报:自然科学版,2011,42(5):1327-1331.(Zhou Youhang,Zhang Jianxun,Dong Yinsong,et al.A variable step-size revisable optimization algorithm to solve geometry constraint[J].Journal of Central South University:Science and Technology,2011,42(5):1327-1331.)
[4]曹春红,王鹏,曹犁歌.基于D-tree分解的欠约束与完备约束的几何约束求解[J].东北大学学报:自然科学版,2014,35(5):627-629.(Cao Chunhong,Wang Peng,Cao Lige.Well-constrained and under-constrained geometric constraint solving based on D-tree decomposition[J].Journal of Northeastern University:Natural Science,2014,35(5):627-629.)
[5]Thierry S E.A particle-spring approach to geometric constraints solving[C]//Proc of the 26th ACM Symposium on Applied Computing.New York:ACM Press,2011:1100-1105.
[6]Mathis P,Schreck P.Coordinate-free geometry and decomposition in geometrical constraint solving[J].Computer-Aided Design,2014,50(5):51-60.
[7]Gao Xiaoshan,Lin Qiang,Zhang Guifang.A C-tree decomposition algorithm for 2D and 3D geometric constraint solving[J].ComputerAided Design,2006,38(1):1-13.
[8]De Regt R,Van der Meiden H A,Bronsvoort W F.A workbench for geometric constraint solving[J].Computer-Aided Design and Applications,2008,5(1-4):471-482.
[9]郭希娟,吴金垒.D-优化算法实现几何约束问题的重组[J].小型微型计算机系统,2011,32(9):1890-1893.(Guo Xijuan,Wu Jinlei.Restructuring of geometric constraint problem with D-optimization algorithm[J].Journal of Chinese Mini-Micro Computer Systems,2011,32(9):1890-1893.)
[10]曹春红,唐川,赵大哲,等.基于雁群启示的粒子群优化算法的几何约束求解[J].小型微型计算机系统,2011,32(11):2299-2302.(Cao Chunhong,Tang Chuan,Zhao Dazhe,et al.Geometric constraint solving based on Geese PSO optimization[J].Journal of Chinese Mini-Micro Computer Systems,2011,32(11):2299-2302.)
[11]曹春红,易荣庆,曹海龙,等.交互更新模式的量子遗传算法的几何约束求解[J].中国图象图形学报,2016,21(4):499-509.(Cao Chunhong,Yi Rongqing,Cao Hailong,et al.Solving geometric constraint based on the interactive update mode quantum genetic algorithm[J].Journal of Image and Graphics,2016,21(4):499-509.)
[12]黄学良,王蕾,王旗华,等.三维几何约束系统的在线增量求解方法[J].计算机辅助设计与图形学学报,2017,29(8):1571-1578.(Huang Xueliang,Wang Lei,Wang Qihua,et al.An online incremental solving method for 3D geometric constraint systems[J].Journal of Computer-Aided Design and Computer Graphics,2017,29(8):1571-1578.)
[13]李文辉,孙明玉,曹春红.几何约束求解的扩展C-树分解法[J].吉林大学学报:工学版,2017,47(4):1274-1279.(Li Wenhui,Sun Mingyu,Cao Chunhong.Extension C-tree decomposition method for geometric constraint solving[J].Journal of Jilin University:Engineering and Technology Edition,2017,47(4):1274-1279.)
[14]王书亭,王战江.粒子群优化算法求解非线性问题的应用研究[J].华中科技大学学报:自然科学版,2005,33(12):4-7.(Wang Shuting,Wang Zhanjiang.Study of the application of PSO algorithms for nonlinear problems[J].Journal of Huazhong University of Science and Technology:Natural Science Edition,2005,33(12):4-7.)