基于QT的粒子群优化仿真演示软件设计
作者: 王随 蒋培培 王善民 吉佳红
摘要:粒子群优化(PSO)算法是一种经典群智能优化算法,为了直观显示迭代过程中适应度进化过程和粒子群位置变化趋势,文章设计了一个基于跨平台QT的粒子群优化仿真演示软件,使用图形化控件支持算法参数编辑和仿真演示。首先介绍了PSO基本原理和算法步骤,然后使用QT控件进行了界面设计,基于QT类进行了算法仿真功能设计和演示功能设计。经过实验验证,该软件支持PSO算法参数编辑,能显示适应度进化曲线和粒子群位置演变过程,满足软件设计的要求。
关键词:QT;PSO;粒子群优化;仿真演示;软件设计
中图分类号:TP311 文献标识码:A
文章编号:1009-3044(2022)29-0045-04
粒子群优化算法(Particle Swarm Optimization Algorithm,PSO)是由J.Kennedy和R.C.Eberhart[1-2]在1995年提出的一种群智能优化算法。该算法受自然界中鸟群和鱼群行为模式启发,具有结构简单、收敛速度快、计算量小等特点。经过许多学者研究,PSO目前已在学术领域和工程应用领域得到广泛应用,例如路径规划[3]、资源调度[4]、参数优化[5]、网络拓扑优化[6]、成本优化[7],成为群智能优化领域的一种经典算法,也是当今研究的热门问题之一。
本文针对在国产化平台下进行群智能优化算法仿真验证和仿真演示的需求,设计了一个基于QT的PSO仿真演示软件。该软件能动态显示每一次迭代后适应度进化曲线变化情况和种群个体位置演变过程。QT是一个开源的跨平台开发工具,由于其灵活性好、移植性强,目前QT在工程应用和模拟仿真中都得到广泛使用,例如单片机程序[8]、模拟控制系统[9]。基于QT开发的软件能方便地移植到国产化平台下。
1 PSO
在基本PSO中,用粒子群模拟优化问题在搜索空间中的解,用适应度对粒子位置进行评价。每个粒子的位置代表多维搜索空间中一个解。假设搜索空间维数为D,当前粒子位置用[Xti]表示,[Xti]表示含有D个元素的向量,其中i表示第i个粒子,t表示迭代次数。
PSO每次迭代搜索需要计算与更新粒子的速度信息和位置信息。
粒子速度更新公式为:
[Vt+1i=ωVti+c1r1pi-Xti+c2r2pg-Xti] (1)
粒子位置更新公式为:
[Xt+1i=Xti+Vt+1i] (2)
其中,i表示第i个粒子,t表示迭代次数,[Vti]表示第i个粒子在第t次迭代时的速度,[Xti]表示第i个粒子在第t次迭代时的位置。ω表示惯性权重,认知因子c1和社会因子c2统称为加速系数或学习因子,r1和r2是第t次迭代时生成的[0,1]内均匀分布的随机数,[pi]表示第i个粒子的历史最佳位置,[pg]表示全局最佳位置。
粒子速度更新方程中,速度的更新由三部分组成:惯性成分、个体认知成分和社会认知成分。其中惯性成分表示粒子当前运动状态对速度更新的影响,惯性权重决定惯性衰减程度的快慢,使算法对粒子先前迭代的惯性速度进行自适应调整;个体认知部分表示粒子个体历史最佳位置对当前速度变化趋势的指导作用;社会认知部分表示全局最佳个体位置对当前速度变化趋势的指导作用。学习因子c1和c2分别表示个体认知和社会认知对速度更新影响的比例系数。搜索初期,粒子拥有较大搜索速度,随着迭代次数增加,惯性速度逐渐减小,表示粒子全局搜索能力减弱,搜索精度提高。
粒子位置更新后,通过适应度函数计算每个粒子的适应度,更新每个粒子的个体历史最佳位置和全局最佳位置。
控制参数对PSO算法的性能具有极大影响。参数c1和r1表示粒子受个体历史最优的影响程度,c2和r2表示粒子受全局最优的影响程度。
PSO遇到两种情况终止搜索:1)迭代次数t达到最大值;2)最佳适应度满足精度要求。
基本PSO算法流程描述如下:
step 1 初始化。随机生成粒子种群,包括随机的位置和速度。
step 2 计算每个粒子适应度,更新全局最优位置和个体历史最优位置。
step 3 进化迭代。根据式(1)和(2)更新每个粒子的速度和位置。
step 4 终止条件判断。判断是否满足搜索终止条件,若满足则转入step5,否则转入step2。
step 5 迭代终止。输出结果并结束。
基本PSO算法流程图如图1所示。
2 PSO仿真演示软件设计
2.1 界面设计
Qt是一个跨平台C++应用程序开发工具,可以快速拖动控件搭建界面生成GUI程序,可视化界面编辑器Qt Designer支持多种控件的选择与布局。
PSO仿真演示软件使用Windows qt 5.6.3开发,使用Qt提供的图形界面控件,包括QLabel控件、QLineEidt控件、QListWidget控件、QComboBox控件、QPushButton控件、QChart控件、QChartView控件和QLayout控件。
通过QLineEidt控件输入PSO算法参数,包括单次迭代时间,种群规模N,最大迭代次数G,解空间维数Dim,解空间上限U,解空间下限L,学习因子c1,学习因子c2,惯性权重ω,最大速度Vmax,最小速度Vmin;通过QComboBox控件选择测试函数。通过QListWidget控件显示操控信息提示和PSO每次迭代后全局最佳适应度结果。通过QChart控件和QChartView控件显示适应度进化曲线和每次迭代后粒子种群分布情况。通过QLayout控件进行界面布局、控件对齐和控件大小自适应控制。
PSO仿真演示软件界面如图2所示。
2.2 算法仿真功能设计
初始化默认的PSO算法参数。程序启动后在PSO参数编辑界面填入默认的数值,默认数值为PSO算法常用的参数数值。
初始化测试函数选项。选取CEC2017基准测试函数作为算法仿真实验的测试函数,包括Sphere函数、Schwefel 2.22函数、Schwefel 1.2函数、Schwefel 2.21函数、Rosenbrock函数、Rastrigin函数、Ackley函数、Griewank函数。用QT实现上述基准测试函数数值计算,参数为元素个数可变的数值数组。
点击软件界面仿真开始按钮后,算法仿真实验开始。算法仿真功能流程如下:
step1:获取界面输入参数。同时进行边界值和异常值检查。当出现异常值时直接退出算法仿真流程。
step2:初始化PSO参数和测试函数参数。
step3:粒子群初始化位置和速度。采用均匀分布的随机数生成解空间内的粒子位置和速度。
step4:检查是否满足搜索终止条件。若满足,则转到step8,否则转到step5。
step5:依次更新每个粒子速度和位置。先根据式(1)更新粒子速度,当速度大于最大值或小于最小值时,重新设置为最靠近的边界值;根据式(2)更新粒子位置,同样判断粒子每一维的位置信息是否在解空间范围内,若超出解空间范围则重新设置为最靠近的边界值。
step6:依次更新每个粒子历史最佳位置和适应度。若当前粒子适应度优于该粒子历史最佳适应度,则更新该粒子历史最佳位置和适应度,否则不作处理。
step7:更新全局最佳位置和适应度。将上次搜索后的全局最佳适应度与本次搜索每个粒子适应度比较,选出本次搜索全局最佳适应度。将本次搜索获得的全局最佳适应度加入全局适应度数组中。转到step4。
step8:PSO结束,输出最终结果。
其中,粒子位置信息和速度信息用二维数组保存,粒子个体历史最佳位置用二维数组保存,粒子个体历史最佳适应度用一维数组保存,全局最佳位置用一维数组保存,全局最佳适应度用一维数组保存。
算法仿真流程step3中,粒子群初始化位置和速度,粒子位置初始化公式为:
[X0i=rand*(U-L)+L] (3)
粒子速度初始化公式为:
[V0i=rand*(Vmax-Vmin)+Vmin] (4)
其中下标i表示第i个粒子,上标0表示第0次迭代为初始化数值,U表示搜索空间上限、L表示搜索空间下限,Vmax表示最大速度、Vmin表示最小速度。
算法仿真功能流程如图3所示。
2.3 演示功能设计
算法演示功能依托于算法仿真功能,在仿真过程中同步进行数据可视化显示。在算法仿真实验运行过程中,每次搜索迭代后更新适应度进化曲线和粒子群分布情况,分别用折线图和点图形式显示。Qt5.6.3提供QChat类用于图表功能设计和显示,用QScatterSeries类存储图表数据,用QChartView类提供视图接口和视图显示,用QChat类实现图表的坐标轴范围、坐标轴刻度、坐标轴网格线、标题、数据类型、显示类型、数据点样式等显示设置。用QChartView类绑定QChat类实现图表的数据管理和视图显示功能。
在算法仿真功能流程的step4中,同步进行存储数据的图形化显示和信息提示,包括适应度进化曲线刷新显示、粒子群分布情况刷新显示和结果显示界面当前迭代结果信息打印显示。
以一维数组形式存储的全局最佳适应度信息读取数组最后一个元素,作为最新一次迭代的全局最佳适应度,写入到适应度进化曲线的数据存储QScatterSeries中,同时更新对应的QChartView,实现适应度进化曲线更新显示。在表示结果显示的QListWidget控件中,同步打印当前迭代后最佳适应度具体数值结果。
将以二维数组形式存储的粒子群位置信息取前两个维度信息形成N个点的二维坐标Pi (xi, yi),其中Pi 表示点,i表示第i个粒子,xi表示横轴坐标,yi表示纵轴坐标。每次迭代搜索结束后,将粒子群分布情况的数据存储QScatterSeries中数据清空,并写入当前迭代后新的二维坐标Pi信息,同时更新对应的QChartView,实现粒子群位置分布情况更新显示。
为了可观测算法仿真过程中种群位置动态变化过程,使用QTimer类作为算法迭代定时器,根据界面输入信息,设置触发间隔,即每当执行到算法仿真功能流程的step4,会暂停在步骤,直到定时器唤醒才会继续执行后续判断和操作。
3 实验结果与分析
PSO仿真演示软件启动后,算法参数编辑框会显示默认值。设置单次迭代时间、种群规模N、最大迭代次数G、测试函数类型、搜索空间维数Dim、搜索空间上限U、搜索空间下限L、学习因子c1、学习因子c2、惯性权重ω、最大速度Vmax、最小速度Vmin等参数后,点击仿真开始按钮,软件开始进行PSO仿真实验。
PSO仿真实验开始后,每次搜索迭代都会根据当前最佳适应度和当前粒子群位置更新软件右侧的适应度进化曲线显示和粒子群分布情况显示。
点击暂停按钮可以暂停算法仿真实验,同时暂停按钮变为继续按钮;再次点击继续按钮,仿真实验继续上次暂停处运行。点击终止按钮可以人为干涉终止算法仿真实验。
当测试函数为Shpere,搜索空间维数Dim为10,其他参数为默认情况时,进行PSO算法仿真实验。当迭代次数t分别为1、30、100、200时,粒子种群分布情况如图4所示。