改进的群搜索算法及其在群体动画中的应用研究

发布时间：2018-03-12 07:06

本文选题：群体动画　切入点：搜索优化算法　出处：《山东师范大学》2013年硕士论文　论文类型：学位论文

【摘要】：计算机图形学是在研究物理规律、实证方法、认知原则的基础上，利用不同的数学算法对二维或三维图形数据的处理，生成科学数据的可视化表现。它专注于可视化图形内容以及数字合成技术功能，是计算机应用程序和计算机科学研究领域的分支。计算机图形学经过近40年的发展，，已进入一个成熟的发展阶段，在各种各样的在计算机辅助设计和加工的电影和电视动画，军事模拟，医学图像处理，地质，气象，财务和电磁场可视化范围应用。计算机图形学已经成功实施在这些领域，尤其是在快速发展的动漫产业。目前，大多数动画制作采用传统的关键帧技术，虽然动画制作师创作了大量的优秀作品，但是随着应用领域的拓展、规模的扩大、人们需求的提高，基于关键帧技术的不足日渐明显，传统动画制作技术中动画角色的每个动作和移动细节都由动画制作师控制，随着动画时间的加长、角色数量的增多、场景复杂度的提高，动画师的劳动量显著增加，同时，由于在群体运动中的个体存在相互影响，群体运动具有个体特征和群体特征，模拟群体动画性能和真实感的提高，对动画制作师来说是非常具有挑战性的。群搜索优化算法是群体智能算法中一个新兴优化算法。模拟算法来自对群居动物如鸟类、鱼类、狮子等觅食行为的模拟。在发现者-加入者模型基础上，该算法还利用游荡者策略，避免陷入局部极值。同时，该算法利用动物视觉搜索机制，扩大搜索的范围。该算法实现简单，在处理高维问题中具有较好的全局搜索能力。但是它存在大部分寻优算法共同的问题：容易陷入局部最优点，影响算法的收敛性，降低了算法的优化性能。本文针对传统群体动画制作中存在的局限问题，对群搜索优化算法进行相应算法改进，使其在处理高维函数问题中表现出较好的全局搜索能力，同时在处理低维问题也能表现出优越的性能，并将其应用到群体动画中，增强算法的应用性与动画的真实性。本文的主要创新工作及其相关应用有以下4个方面： 1.提出一种改进的群搜索优化算法通过在收敛策略、群体智能性上对群搜索优化算法进行改进，在群体最优陷入停滞时引入差分进化算法，并根据算法自身特点，将差分计划算法进行变异，使其摆脱局部极值点的束缚，同时引入模拟退火机制，提高全局搜索能力。 2.将改进的群搜索优化算法应用人群三维动画中以VS2003+ACIS为平台，在WindowsXP操作系统下构建仿真系统，利用改进的群搜索优化算法模拟群体动画中的人群对穿现象。碰撞避免贯穿于整个群体动画过程中，群体智能行在群体个体与障碍物之间以及群体个体成员之间，都表现出较好性能。同时，将该仿真实验运用到Maya三维动画制作中，该算法在应用中产生较好的动画效果。 3.提出一种基于步长搜索的改进群搜索算法的群体路径规划方法该方法首先针对群搜索优化算法的局限性进行改进，引入模拟退火算法，放弃视觉搜索模式而采用步长搜索，使群搜索算法高效简单、易于实现。同时，为避免路径长、环境复杂，单纯使用算法规划起点到目标点之间的路径造成计算量大、耗时长等问题，引入多线程和路径随机拼接技术进行分层次路径规划。在外层全局路径规划中利用A*算法进行规划实施，在内层路径规划中利用改进的群搜索优化算法，通过多线程并行运行，实现在栅格区域间的内层并行路径规划。针对传统路径拼接技术容易出现“拉长线”、“聚集”和“跳跃”现象，本文采用随机路径拼接技术，将栅格区域内的路径进行有效拼接，进而规划出整体路径。 4.将基于改进群搜索算法的群体路径规划方法应用到化工厂逃生规划中疏散是人们在遇到危险时，迅速逃离现场的行为。将基于改进群搜索算法的群体路径规划方法应用到化工厂逃生中，不仅能够较真实的模拟化工厂发生危险时人群逃生的路径，而且在计算速度、模拟效果上都有较好的应用。
[Abstract]:Computer graphics is in the study of physical laws, empirical methods, based on cognitive principles, processing of 2D or 3D graphics data using different mathematical algorithms, visualization of scientific data generation. It focuses on the visual content and function of digital synthesis technology, is a branch of the field of computer applications and computer science computer. Graphics after nearly 40 years of development, has entered a mature stage of development, in a variety of computer aided design and processing in the film and television animation, military simulation, medical image processing, geological, meteorological, financial and electromagnetic field visualization application. Computer graphics has been successfully applied in these areas, especially in the the rapid development of the animation industry. At present, most of the traditional animation key frame technology, although the animators created a lot of excellent The show works, but with the application development, the expansion of the scale, people demand increase, lack of key frame based technology becomes more and more apparent, all motion details of traditional animation animation technology in the role by the animators, with longer animation time, increased number of characters, increase the complexity of the scene the amount of labor, the animators increased significantly, at the same time, due to the mass movement of individuals have mutual influence, population movement has the individual characteristics and group characteristics, simulation and realistic performance of group animation to improve, animators is very challenging.
Group search optimization algorithm is a new optimization algorithm of swarm intelligence algorithm. Simulation algorithm from the fish to the social animal, such as birds, lions and other simulation foraging behavior. In the discovery - join based on the model, the algorithm also uses the rogue strategy to avoid falling into local extreme value. At the same time, the algorithm uses the animal visual search the mechanism, expand the scope of the search. The algorithm is simple and has better overall in dealing with high dimensional problems in search ability. But it is common problem of most of the optimization algorithm is easy to fall into local minima, affect the convergence of the algorithm, reduces the optimization performance of the algorithm.
Aiming at the limitations of the traditional group animation, the corresponding algorithm of improved group search optimization algorithm in the high-dimensional function problem showed better global search ability, and exhibits superior performance in low dimensional problems, and its application to the group animation, augmented reality of the application of the algorithm animation. The main innovation of this paper and its application has the following 4 aspects:
1. an improved group search optimization algorithm is proposed
The convergence strategy, group intelligence on the group search optimization algorithm, the optimal population differential evolution algorithm is introduced into stagnation, and according to the algorithm's characteristics, differential planning algorithm variation, to get rid of the shackles of local extremum, and introduces the simulated annealing mechanism to improve the global search ability.
2. application of improved group search optimization algorithm in 3D animation of crowd
To VS2003+ACIS as a platform to build a simulation system under the WindowsXP operating system, using swarm optimization algorithm simulating in groupanimation people to wear phenomenon. The improved collision avoidance throughout the animation of the whole group in the process of swarm intelligence between individuals and groups of obstacles and the group of individual members, show good performance. At the same time, the simulation experiment applied to the Maya animation, this algorithm has better animation application.
3. a method of group path planning based on improved group search algorithm based on step length search
Firstly, considering the limitation of the group search optimization algorithm was improved by simulated annealing algorithm, give up visual search mode by step search, the group search algorithm is efficient and simple, easy to implement. At the same time, in order to avoid the long path, the environment is complex, simply use the algorithm starting point to the path between the target point caused by the large amount of calculation. Time is too long, hierarchical path planning to introduce random splicing technology of multi thread and path planning. The implementation of A* algorithm using in the outer layer of the global path planning, using the improved group search optimization algorithm in the inner path planning, running parallel through multi thread, realize the inner regional grid in parallel for the traditional path planning. Path splicing technology of "long line", "gathering" and "jump" phenomenon, this paper uses a random path splicing technology, the path in the region into the grid The line can be stitching effectively, and then the whole path is planned.
4. the method of group path planning based on improved group search algorithm is applied to the escape planning of chemical plant
Is the evacuation of people in the face of danger, quickly fled the scene. The behavior will be based on improved group escape path planning method of group search algorithm is applied to the chemical plant, chemical plant can not only route simulation real danger crowd escape, but also in the speed of calculation, simulation results have good application.

【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP391.41;TP18

【参考文献】