微粒群算法研究平台设计与实现

谢俊凰，高慧敏

(1.太原科技大学系统仿真与计算机应用研究所，太原030024;2.嘉兴学院机电工程学院，浙江嘉兴314001)

微粒群算法，又称粒子群优化，是由J.Kennedy和 R.Eberhart[1-2]于1995年开发的一种演化计算技术来源于对一个简化社会模型的模拟。经过26年的探索和研究，微粒群算法以其鲁棒性好、具备分布式的特征、应用面广、算法实现简单等优点已经在很多领域得到了广泛的应用。

自微粒群算法提出以来，国内外研究者对微粒群算法进行了大量的研究，并提出了很多新型的微粒群算法[3-6]，要将算法实现并且进行性能测试。大多数研究者都是在Visual C++环境下运行算法，DOS界面下输出结果，只能看到大量数据的输出和最终结果，缺乏对微粒群算法进化过程内在了解和数据统计功能。因此，需要一个算法研究平台来辅助研究者，提高研究率。

Wall M 在1996 年提出了 GAlib[7]，GAlib 是遗传算法系统开发方面的最早成果，它不同于后期出现的一些框架，它关注遗传算法体系的设计，在操作算子和个体类型的数据结构上有着很多良好的实现，在库开发中使用了C++的面向对象技术和模板技术，并有相关数据统计分析的类[8]。

徐星、李元香[9]等人提出了基于策略模式的粒子群优化算法平台设计，将一些经典的微粒群算法写入了平台，并可以设置其参数运行之后比较各种算法的优劣。但是忽略了对进化过程的显示以及平台扩展性的研究。

1 平台整体设计

一种可扩展的微粒群算法研究平台，必须具备以下两点基本功能:第一，支持各种不同类型的微粒群算法;第二，提供算法数据统计功能。为了满足这两个基本功能，平台定义一个开放式的体系结构，各种不同的微粒群算法能够在平台中无障碍运行，前提条件是遵循平台内部的数据接口规则。研究者只需要关注算法，算法以外的留给平台完成，使得平台具有良好的扩展性。

算法的运行有两种模式:内部运行和外部导入运行。内部运行模式，将标准微粒群算法代码封装成代码类在运行时初始化类的一个对象即可。设计友好的用户界面用来设置算法的参数，将设置的参数传入代码中。外部导入模式，使用动态链接库技术实现，对动态库文件进行显式加载，动态库文件返回值作为平台其它功能的数据来源。

遵循软件设计“高内聚，低耦合”的原则，结合平台的实际情况，采用三层架构对平台进行设计，使用微软公司开发的MFC平台开发，采用 SQL 2000数据库。

为了提高平台的运行效率，采用多线程技术。MFC提供了两种线程:工作者线程和用户界面线程[10]。两种线程的主要区别在工作者线程没有消息循环，用户界面线程有消息循环和消息队列。所以，一般情况下工作者线程用来后台计算，用户界面线程用来处理用户输入、响应用户等。

图1描述了平台的总体结构，从线程角度、功能角度和架构角度进行说明。

线程角度:系统在系统初始化时，编译器自动产生一个主线程——main()函数，根据需要可以另外增加线程。平台除了使用主线程外，还添加了一个线程，工作者线程。主线程主要负责:界面显示、图形显示、响应用户消息、数据库进行交互和平台的运行控制;工作者线程只用于算法计算，它工作在三层架构的业务逻辑层。

架构角度:平台架构分为三层依次为表示层、业务逻辑层、数据访问层。

表示层主要负责用户界面的设计、接收用户对界面的响应和用户输入的数据以及界面显示和图形显示。业务逻辑层负责平台控制和算法计算。数据访问层与数据库进行交互，进行数据存储、读取、修改、添加等操作。

功能角度平台中的功能大致分为:图形显示、界面响应、算法计算、平台控制和数据库交互。图形显示主要负责图形绘制;界面响应主要负责响应用户请求;算法计算主要用于计算算法代码;平台控制主要用来控制平台的运行;数据库交互主要负责平台与数据库的数据操作。

图形显示在主线程中实现，工作在表示层;界面响应在主线程中实现，工作在表示层;算法计算在工作者线程中实现，工作在业务逻辑层;平台控制在主线程中实现，工作在业务逻辑层;数据库交互在主线程中实现，工作在数据访问层。

通过三种角度对平台的描述，可以明显看出平台的三种设计是相通的、相互渗透、相互协作。

图1 平台架构图Fig.1 Figure of Platform structure

2 平台详细设计

微粒群算法研究平台是一个算法无关的操作台，为研究者进行不同的微粒群算法研究提供了相同的界面和一致的操作，使得平台学习周期短、操作简单。

平台主要功能有:内部算法运行、算法导入、图形显示、数据统计、数据导出、日志功能。

2.1 内部算法运行设计

内部代码运行方式，将标准微粒群算法代码用C语言实现并封装成一个算法类—PSO类。为了达到研究算法的目的，将PSO类里的某些重要参数例如:W、C1、C2、Vmax允许进行修改，每次运行的参数都是从参数设置界面中获得的。

设计适合的、友好的人工界面，用于设置算法参数。当用户点击相应的菜单后，立即弹出参数设置界面，将需要设置的数据填入到相应的区域即可。内部算法运行得到的数据保存在一个二维数组中，提供给平台其它功能。

2.2 算法导入设计

算法导入功能是平台重要的功能之一，它体现了平台的可扩展性。为了满足研究者不同的需求，平台必须具备算法导入功能。平台设计了微粒群算法接口，只要按照规定接口编写的算法代码就可以在平台中运行并且享有平台其它功能。

采用Windows动态链接库技术实现导入功能，将需要导入的算法代码写成动态库文件以显式方法进行加载[11-12]。在动态库文件中有一个导出函数，平台内部只能“看见”这个导出函数并定义一个与这个导出函数类型相同的函数用来获取该导出函数的地址。动态库文件中运算得到的数据被存储到一个Vector变量中，并返回这个Vector的地址(导出函数的返回值类型)，在平台内部定义一个与动态库文件Vector变量相同类型的Vector变量用来接收返回的数据，提供给平台其它功能。为了自由选择导入的动态库文件，平台提供相应的界面用来选择需要导入的文件。在动态库文件被选中之后，该动态库文件立即被执行。

2.3 图形显示设计

图形显示是平台重要功能之一，分三个方面进行描述。这个功能是什么?这个功能能实现什么?这个功能怎么实现?

这个功能是什么?微粒群算法的基本过程是初始化群体后，根据算法特有的选择策略进行群体进化，逐步向最优解靠近的过程。所以，进化过程是算法的核心过程，但是传统研究方法是在Visual C++的编译环境下进行，数据输出在DOS界面下，直接输出最终结果或者将中间过程的数据以研究者难以查看的方式快速显示。为了对进化过程有一个内在的了解平台设计了图形显示功能。

这个功能能实现什么?微粒群算法的个体定义中有速度、位置、适应值等数据，采用二维坐标进行，水平坐标表示时间，纵坐标表示被显示数据的值。将算法进化过程中的数据根据需要进行图形显示。

这个功能怎么实现?如何显示进化过程是很关键的问题。涉及到两个问题:在众多数据中如何确定显示数据以及高维问题。算法中涉及到的个体往往都是高维的，如何处理高维到低维过度是一个重要的问题。

易操作是平台的重要特点之一，平台提供图形显示设置对话框提供给用户用来选择需要显示的数据。在显示个体数据时，个体定义是多维情况下，采用二维坐标而且水平坐标表示时间，能够利用的只有纵坐标，只能显示个体某个属性的一维数据，为了不丢失显示数据，采用“调整显示”方法来解决。通过方向键的左右键来实现。右键是将维度提高，左键是将维度降低。

例如:一个个体的速度是N维，在初始情况下显示其0维上的数据，通过MFC机制提供的按键响应设置方向键的左右键进行维度的调整，左键将维度调低，右键将维度调高。这样，解决了高维到低维过度的问题，实质上就是选择感兴趣的数据进行显示。

为了灵活、合理地显示数据，支持纵坐标范围设置，显示类型包括单个个体显示、多个个体显示、单个个体对比显示、多个个体对比显示。

将不同个体的显示用不同的颜色进行区分，个体在该属性该维度上数据的显示是一条折线，看上去是一个连续的过程与微粒群算法进化过程的连续性相符合，而且显示效果直观、清楚。

2.4 数据统计设计

做为一个算法研究平台，目的是给算法研究者提供一个简单、方便、有效的研究环境。数据统计功能必然是不可或缺的功能之一。是否收敛、收敛代数、是否找到最优解或满意解是评价算法最关键的因素，收敛代数、平均收敛代数、最优解、最优解平均值成为平台统计工作的重点。

对收敛代数和最优解不仅提供了列表显示功能还提供了图形显示功能。设计良好的用户界面，对每次运算得到的结果显示在用户界面上，并且提供图形显示方法给予直观了解。对两次不同的运算结果，可以用二维图形方式对比显示，从不同评价角度比较出算法的优劣。

数据统计下的图形显示采用二维显示方法，水平轴代表进化代数，垂直轴代表具体显示的数据，垂直轴数据可以自由选择，显示数据都是在算法运算过程中得到，并且保存在定义好的 Vector变量中。

在显示界面上直接给出平均收敛代数和平均最优解，并提供算法运算过程数据的详细查询，可以按任一参数为检索条件进行查询，当查询条件值不确定时，可根据范围进行模糊查询，返回在该范围内所有符合的数据，提供导出功能将查询数据导出为Excel文件。

2.5 数据导出设计

传统研究模式下算法运算数据量大，数据枯燥，而且对运算得到的数据可操作性不强。这是传统研究模式的很大弊端。针对这个问题，平台支持数据导出功能，导出格式为Excel文件，将数据库中的数据、查询得到的数据直接导入为Excel文件。

Excel主要用于数据的处理、数据的统计分析以及辅助决策相关操作，被广泛地应用在管理、金融、财经等领域。Excel内部有大量的公式函数可以选择，使用非常方便。因为Excel上述的特点，平台将算法运算的数据导入到Excel中，借助Excel强大的功能做进一步的分析。

2.6 日志功能设计

大部分成熟软件产品都提供了日志功能，主要用于存储软件运行的状况，包括正常运行状态下的数据和非正常状态下产生的错误信息。平台提供日志功能包括:生成日志、日志查看、日志导入。

生成日志:算法运算的得到的数据都被存储在文本文件中，导出格式为.txt文件。平台产生的日志文件，存储算法运行产生的所有数据，以及运行的时间、次数等重要信息。为研究人员核查数据提供一种方法。日志文件以该次运行的时间命名。生成日志数据主要有两种来源:微粒群算法内部运算结果、微粒群算法动态库运算结果。

日志查看:对平台历史上生成的日志进行查看，提供查看对话框自由选择日志文件。

日志导入:微粒群算法的种群初始化工作绝大部分都是随机的，即使在相同参数情况下进化过程也不可能完全相同，所以每一次进化过程是唯一的，不可重复的。平台提供的图形显示只能对该次运行显示一次，不能进行重复显示。日志导入功能提供将进化过程重复显示的手段，对每次进化过程都可以重复显示，类似于重播功能。日志导入也成为平台数据导入的另一种方法。

3 平台应用

开发微粒群算法研究平台的目的是辅助算法研究者对算法进行研究，提高研究者的工作效率。平台具有与算法无关的特点，只要编写的算法符合平台规定的数据接口，该算法就可以在平台中运行，使用平台中的所有功能。平台运行流程如图2所示。

图2 平台运行流程图Fig.2 Flowchart of platform operation

内部运行模式下，标准微粒群算法已经被封装在平台内部，可以改变算法的参数对标准微粒群算法进行研究。对惯性权重、算法运行次数、最大迭代次数、学习因子、最大速度等参数进行修改。

参数惯性权重设置为1.0、算法运行次数设置为10、最大迭代次数设置为500、学习因子设置为1.6、最大速度设置为2、最小速度设置为 -2、种群规模设置为20，如图3所示。

图3 算法参数设置图Fig.3 Diagram of parameter setting

运行平台图形显示功能，在图形显示参数设置界面中，将Y轴范围设置为:-10至10，显示内部算法运算数据、显示单个1号个体的速度，显示如图4，从微观角度直观、清楚展现了算法进化内在过程。

图4 单个个体图形显示Fig.4 Graphic display of single individual

图5 数据统计图Fig.5 Diagram of data statistics

图6 数据统计图形显示Fig.6 Graphic display of data statistics

运行数据统计功能，结果如图5所示。从图5中清楚地看出，本次内部算法运算得到平均适应值为3.000 004，平均收敛代数为144，运算10次收敛10次，每次运行具体统计结果也很清楚、明了。将本次运算统计结果通过二维图形显示如图6所示，从图6中可以明显观察到最优解变化趋势图一目了然，位于平均适应值上下波动，其中 1、2、3、6、7、10次运算得到最优解高于平均值，4、5、8、9次运算得到最优解低于平均值。将动态库文件导入到平台中，运行动态库文件。将两次运行得到最优解情况进行统计，并对比显示得到图7.从图7可以看出，1、2、3、6、7、8 次运算得到最优解相同，高于平均值;第4、5、9次最优解处于平均值之下，从宏观角度清楚、直观地展现了两次运算得到的最优解情况。

图7 数据统计对比图形显示Fig.7 Graphic comparisons display of data statistics

4 总结

本文提出了一种通用的、可扩展的微粒群算法研究平台，使用动态链接库技术支持不同类型的微粒群算法，使得平台具有良好的扩展性。内部算法运行、图形显示、数据统计、数据导出、日志功能使得平台具有良好的实用性，从微观角度展现了算法进化内在过程，从宏观角度展现了算法数据统计信息，与传统研究模式相比具有明显优势。但是，平台还有一些需要改进之处:(1)支持微粒群算法求解优化问题;(2)支持其它经典的优化算法例如:遗传算法、模拟退火算法等。

[1]KENNEDY J，EBERHART R.Particle Swarm Optimization[C]//Proc IEEE Int Conf on Neural Networks.Piscectaway，NJ，1995:1942-1948.

[2]Eberhart R，Kennedy J.A New Optimizer Using Particle Swarm Theory[C]//Proc 6th Int Symposium on Micro Machine and Human Science.Nagoya，1995:39-43.

[3]赵亚敏，许家栋.一种改进的微粒群优化算法[J].计算机工程与应用，2010，46(2):31-33.

[4]王慧，刘希玉，李田来.基于流形的微粒群优化[J].计算机科学，2009，36(3):212-214.

[5]肖健梅，李军军，王锡淮.梯度微粒群优化算法及其收敛性分析[J].控制与决策，2009，24(4):560-564.

[6]谭瑛，高慧敏，曾建潮.求解约束优化问题的微粒群算法[J].太原重型机械学院学报，2004，25(2):94-97.

[7]WALL M.GAlib:A C++Library of Genetic Algorithm Components，Technical Report，Mechanical Engineering Department，Massachusetts Institute of Technology，1996.

[8]孔亮.面向对象的遗传算法平台设计与应用[D].上海:上海交通大学，2008.

[9]徐星，李元香，吴昱，胡豪.基于策略模式的粒子群优化算法平台设计[J].武汉大学学报:工学版，2010，43(3):361-374.

[10]姚领田.精通MFC程序设计[M].北京:人民邮电出版社，2006.

[11]张世禄，彭磊.利用动态链接库提高代码可重用性[J].计算机应用，2001，21(8):239-240.

[12]张冠茂，王芳.基于动态链接库模块视窗菜单外部控制的软件开发[J].计算机应用，2003，23(11):118-121.