论文部分内容阅读
摘 要：当代，利用计算机图形学的有关方法模拟控制人群的技术已广泛地应用于电影、游戏和部分商业活动中，但是，如何使虚拟出来的人群拥有和真人一样的动作却不是一件容易的工作。本文着重解决人群模拟中虚拟人群的移动路线产生问题：怎样才能使虚拟人群的活动路线看起来更加自然。
关键词：控制人群 移动路径的产生 复杂自适应系统 粒子群优化
计算机图形学的主要研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。许多研究领域与精密技术都被应用于获取可被世人接受的结果。在创造高质量的虚拟人物或动物的过程中，如何实现虚拟人群高质量的真实的行为活动毫无疑问是极其困难的，因为定义哪种合适行为给模拟出来的人群是很值得谨慎思考的问题。为了解决以上这些问题，许多人工智能的有关方法被应用其中。本文对粒子群优化算法进行了部分修改，让它在复杂自适应系统构建的框架中达到使模拟人群产生自然合适的路径和能够互相避让的效果。
1. PSO算法概述
粒子群优化算法（PSO）与同样是人工智能领域的遗传算法（GA）相类似，但是在粒子群优化算法中，并没有用到遗传算法中的一些操作例如：交叉（crossover）和变异（mutation）等，而是在解空间根据最优粒子进行搜索。因此它具有简单，易于实现，且并没有很多参数需要调整的优点。
粒子群优化算法是一种全局优化的算法，计算步骤如下：
Step1：初始化：
（1）选定种群规模n；
（2）设x[i]为第i个粒子的位置；
（3）设fitness[i]为第i个粒子适应值；
（4）设v[i]为第i个粒子速度；
（5）设gBest 是种群中粒子的最好位置；
（6）设pBest[i]为第i个粒子的最好位置；
（7）设pBestfitness[i]为第i个粒子自身搜索的最好位置的适应值。
Step 2： 评价每个粒子的适应值
Step 3： 对每个粒子，将其适应值与全局所经历的最好位置gBest作比较，如果较好，则重新设置gBest的索引号；
Step 4： 对每个粒子，将其适应值与其经历过的最好位置pBest作比较，如果较好，则将其作为当前的最好位置pBest；
Step 5： 根据公式2.2变化粒子的速度和位置；
Step 6： 如未达到结束条件，则返回Step 2。
2. 基于SWARM仿真平台应用研究
2.1 SWARM概述
近年来，随着科学技术的不断更新，基于Swarm仿真平台的应用研究，得以迅速发展，所涵盖的研究领域涉及经济学、金融学、政治学、社会学、生物学、生态学、物理学、地理学、军事，以及计算机科學等诸多学科，为科学研究带来了崭新的概念、思路和方法，为研究者提供了方便。
Swarm是用于研究复杂自适应系统的多智能体仿真平台。研究发现，在复杂系统中所涉及的一些基本特征，如非线性、非平衡、突变、分岔、混沌和路径依赖等，这就是复杂科学具有强大生命力的重要原因，由于这些特征具有非常强的普遍性。正所谓，万物都是有联系的，多学科交叉是各个学科发展的重要环节，Swarm为多学科交叉获得实质性进展的提供坚实基础。
2.2 基于多主体的SWARM仿真
Swarm是一个高效率、可信的、可重用的软件实验平台，他为专业领域研究人员提供了一个标准的软件工具集，即提供了一个软件实验环境，其核心是提供一个面向对象的框架，用于研究仿真中相互作用的智能体和其他对象的行为。同时，Swarm也是一款开源的软件开发包的集合，支持用户开发自己的专用库，目前已经有二维空间、遗传算法和神经网络等专用库。
Swarm对模型和模型要素之间的交互方式不做任何限制，这使得用户可以把精力集中在所研究的特定系统中，而不必受数据处理、用户界面设计以及其他纯软件工作和复杂系统编程等问题的困扰。
Swarm的建模思想是让一系列独立的主体通过独立事件进行交互，帮助科研人员研究由多个个体组成那个的复杂适应系统的行为，用户可以使用Swarm提供的类库去构建模拟系统，使系统中的主体和其他元素通过离散事件进行交互，并可以通过相应的类进行分析、控制与现实复杂自适应系统的仿真过程相比较并得到结果。由于Swarm没有对模型和模型要素之间的交互进行任何约束，所以Swarm在理论上可以模拟任何物理系统、经济系统或社会系统。
2.3 SWARM系统结构
Swarm平台的构架是基于模块化的，所以用面向对象的思维去理解Swarm的体系结构和程序仿真实现会起到事半功倍的效果。基于Swarm系统的Swarm对象就是一个顶层容器，它将各种对象封装在里面。Swarm对象可分为ModelSwarm和ObserverSwarm。ModelSwarm是真实系统的模拟，仿照真实系统运行；用户通过ObserverSwarm对ModelSwarm进行控制并观察运行结果。在仿真实现的过程中，对象ModelSwarm常常被建立在对象ObserverSwarm创建的存储空间中，以作为它的成员对象。
在Swarm的仿真系统中，需要考虑的元素主要有主体、主体生存环境和主体活动，而在Swarm框架中，他们被集成到ModelSwarm对象中。Swarm构架提供了能改变主体行动规则和改变主体的生存环境的运行参数的功能，研究者就可以自主地改变主体行动规则和主体的生存环境，同时还可以观察仿真结果。ObserverSwarm存在的意义就在于此，需要它参考的依据主要通过监测主体运行情况的探测器、与仿真系统交互的控制面板、现实主体运行环境的栅格和统计运行结果的各种图形得出。也就是说，各种模型运行在ModelSwarm中，ObserverSwarm是用户与模型交互观测运行结果的窗口。 3. 基于SWARM构架的人群模拟
粒子群优化算法仅仅对粒子的最后位置感兴趣，而并不关心粒子行走过程中走过的每一步，这与现实世界的人群模拟很不一样，一个人正常情况下也不可能踩过另外一个人。这是由于粒子群优化算法与控制人群的动作不兼容导致的。为了统一的解决这类不兼容的问题，我们首先设计求目标值的目标函数去表现特定的目标、静态的障碍物、以及群体中的所有粒子。
一个粒子的目标值受两个因素的影响：粒子的目的地与行程过程中所遇到的障碍物。因为想利用粒子群优化算法本身能力的这个目的，我把模拟人群移动看作利用一种数学方法作为搜索的机制，我把粒子的目的地定为坐标轴x-y轴上面的一点，粒子通过一种特殊的方式寻找方向，就是利用坐标定位法，寻找自己的目的地。
模拟粒子运动的成败关键就在于如何利用粒子群优化算法巧妙地计算出适宜的方向。粒子在走每一步的同时，都会得到一个目标函数值，去衡量当前的位置。与此同时，根据新获得的目标函数值，把当前粒子的局部最优值和全局最优值得到了更新。这样一种粒子群优化算法的机制。再加上合适的参数设定，会使群体中的粒子对目的地会具有较高概率的收敛性。除此以外，我们可以采用不同的目标函数来安排最后的群体的状态，例如：一条值线，一个圆圈，或者其他可能的形状。
4. 结论
文章着力于把粒子群优化算法和模拟人群移动这两方面统一成一个模型， 通过该模型可以把人群找到的一个可行走的路线并达到目标地点的过程看作利用粒子群优化算法得到最优解的过程。粒子群优化算法的优点是编程简单、快速、并且易于实现。利用粒子群优化算法，每个人可以自动地搜索到一条路径。
参考文献
[1]C.W. Reynolds， Steering behaviors for autonomous characters， in： Proceedings of Game Developers Conference 1999， 1999， pp.763-782
[2]C. W. Reynolds， Flocks， herds， and schools： A distributed behavioral model， Computer Graphics 21 （4） ，1987， pp. 25-34
[3]Paul S. Wang，杜一民，趙小燕译， Java with Object-Oriented Programming， 北京：清华大学出版社，2003
[4]刘贞，程勇军， Swarm of Java， 北京：机械工业出版社，2009
[5] 郭文忠，陈国龙，粒子群优化算法中惯性权值调整的一种新策略，计算机工程与科学，2007，01
关键词：控制人群 移动路径的产生 复杂自适应系统 粒子群优化
计算机图形学的主要研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。许多研究领域与精密技术都被应用于获取可被世人接受的结果。在创造高质量的虚拟人物或动物的过程中，如何实现虚拟人群高质量的真实的行为活动毫无疑问是极其困难的，因为定义哪种合适行为给模拟出来的人群是很值得谨慎思考的问题。为了解决以上这些问题，许多人工智能的有关方法被应用其中。本文对粒子群优化算法进行了部分修改，让它在复杂自适应系统构建的框架中达到使模拟人群产生自然合适的路径和能够互相避让的效果。
1. PSO算法概述
粒子群优化算法（PSO）与同样是人工智能领域的遗传算法（GA）相类似，但是在粒子群优化算法中，并没有用到遗传算法中的一些操作例如：交叉（crossover）和变异（mutation）等，而是在解空间根据最优粒子进行搜索。因此它具有简单，易于实现，且并没有很多参数需要调整的优点。
粒子群优化算法是一种全局优化的算法，计算步骤如下：
Step1：初始化：
（1）选定种群规模n；
（2）设x[i]为第i个粒子的位置；
（3）设fitness[i]为第i个粒子适应值；
（4）设v[i]为第i个粒子速度；
（5）设gBest 是种群中粒子的最好位置；
（6）设pBest[i]为第i个粒子的最好位置；
（7）设pBestfitness[i]为第i个粒子自身搜索的最好位置的适应值。
Step 2： 评价每个粒子的适应值
Step 3： 对每个粒子，将其适应值与全局所经历的最好位置gBest作比较，如果较好，则重新设置gBest的索引号；
Step 4： 对每个粒子，将其适应值与其经历过的最好位置pBest作比较，如果较好，则将其作为当前的最好位置pBest；
Step 5： 根据公式2.2变化粒子的速度和位置；
Step 6： 如未达到结束条件，则返回Step 2。
2. 基于SWARM仿真平台应用研究
2.1 SWARM概述
近年来，随着科学技术的不断更新，基于Swarm仿真平台的应用研究，得以迅速发展，所涵盖的研究领域涉及经济学、金融学、政治学、社会学、生物学、生态学、物理学、地理学、军事，以及计算机科學等诸多学科，为科学研究带来了崭新的概念、思路和方法，为研究者提供了方便。
Swarm是用于研究复杂自适应系统的多智能体仿真平台。研究发现，在复杂系统中所涉及的一些基本特征，如非线性、非平衡、突变、分岔、混沌和路径依赖等，这就是复杂科学具有强大生命力的重要原因，由于这些特征具有非常强的普遍性。正所谓，万物都是有联系的，多学科交叉是各个学科发展的重要环节，Swarm为多学科交叉获得实质性进展的提供坚实基础。
2.2 基于多主体的SWARM仿真
Swarm是一个高效率、可信的、可重用的软件实验平台，他为专业领域研究人员提供了一个标准的软件工具集，即提供了一个软件实验环境，其核心是提供一个面向对象的框架，用于研究仿真中相互作用的智能体和其他对象的行为。同时，Swarm也是一款开源的软件开发包的集合，支持用户开发自己的专用库，目前已经有二维空间、遗传算法和神经网络等专用库。
Swarm对模型和模型要素之间的交互方式不做任何限制，这使得用户可以把精力集中在所研究的特定系统中，而不必受数据处理、用户界面设计以及其他纯软件工作和复杂系统编程等问题的困扰。
Swarm的建模思想是让一系列独立的主体通过独立事件进行交互，帮助科研人员研究由多个个体组成那个的复杂适应系统的行为，用户可以使用Swarm提供的类库去构建模拟系统，使系统中的主体和其他元素通过离散事件进行交互，并可以通过相应的类进行分析、控制与现实复杂自适应系统的仿真过程相比较并得到结果。由于Swarm没有对模型和模型要素之间的交互进行任何约束，所以Swarm在理论上可以模拟任何物理系统、经济系统或社会系统。
2.3 SWARM系统结构
Swarm平台的构架是基于模块化的，所以用面向对象的思维去理解Swarm的体系结构和程序仿真实现会起到事半功倍的效果。基于Swarm系统的Swarm对象就是一个顶层容器，它将各种对象封装在里面。Swarm对象可分为ModelSwarm和ObserverSwarm。ModelSwarm是真实系统的模拟，仿照真实系统运行；用户通过ObserverSwarm对ModelSwarm进行控制并观察运行结果。在仿真实现的过程中，对象ModelSwarm常常被建立在对象ObserverSwarm创建的存储空间中，以作为它的成员对象。
在Swarm的仿真系统中，需要考虑的元素主要有主体、主体生存环境和主体活动，而在Swarm框架中，他们被集成到ModelSwarm对象中。Swarm构架提供了能改变主体行动规则和改变主体的生存环境的运行参数的功能，研究者就可以自主地改变主体行动规则和主体的生存环境，同时还可以观察仿真结果。ObserverSwarm存在的意义就在于此，需要它参考的依据主要通过监测主体运行情况的探测器、与仿真系统交互的控制面板、现实主体运行环境的栅格和统计运行结果的各种图形得出。也就是说，各种模型运行在ModelSwarm中，ObserverSwarm是用户与模型交互观测运行结果的窗口。 3. 基于SWARM构架的人群模拟
粒子群优化算法仅仅对粒子的最后位置感兴趣，而并不关心粒子行走过程中走过的每一步，这与现实世界的人群模拟很不一样，一个人正常情况下也不可能踩过另外一个人。这是由于粒子群优化算法与控制人群的动作不兼容导致的。为了统一的解决这类不兼容的问题，我们首先设计求目标值的目标函数去表现特定的目标、静态的障碍物、以及群体中的所有粒子。
一个粒子的目标值受两个因素的影响：粒子的目的地与行程过程中所遇到的障碍物。因为想利用粒子群优化算法本身能力的这个目的，我把模拟人群移动看作利用一种数学方法作为搜索的机制，我把粒子的目的地定为坐标轴x-y轴上面的一点，粒子通过一种特殊的方式寻找方向，就是利用坐标定位法，寻找自己的目的地。
模拟粒子运动的成败关键就在于如何利用粒子群优化算法巧妙地计算出适宜的方向。粒子在走每一步的同时，都会得到一个目标函数值，去衡量当前的位置。与此同时，根据新获得的目标函数值，把当前粒子的局部最优值和全局最优值得到了更新。这样一种粒子群优化算法的机制。再加上合适的参数设定，会使群体中的粒子对目的地会具有较高概率的收敛性。除此以外，我们可以采用不同的目标函数来安排最后的群体的状态，例如：一条值线，一个圆圈，或者其他可能的形状。
4. 结论
文章着力于把粒子群优化算法和模拟人群移动这两方面统一成一个模型， 通过该模型可以把人群找到的一个可行走的路线并达到目标地点的过程看作利用粒子群优化算法得到最优解的过程。粒子群优化算法的优点是编程简单、快速、并且易于实现。利用粒子群优化算法，每个人可以自动地搜索到一条路径。
参考文献
[1]C.W. Reynolds， Steering behaviors for autonomous characters， in： Proceedings of Game Developers Conference 1999， 1999， pp.763-782
[2]C. W. Reynolds， Flocks， herds， and schools： A distributed behavioral model， Computer Graphics 21 （4） ，1987， pp. 25-34
[3]Paul S. Wang，杜一民，趙小燕译， Java with Object-Oriented Programming， 北京：清华大学出版社，2003
[4]刘贞，程勇军， Swarm of Java， 北京：机械工业出版社，2009
[5] 郭文忠，陈国龙，粒子群优化算法中惯性权值调整的一种新策略，计算机工程与科学，2007，01