基于导向差分进化算法的党务活动调度优化方法

Optimization method of party affairs activity scheduling based on directional differential evolution algorithm

摘要

为解决项目活动时间安排不合理、经费开销大的问题，提出了一种基于导向交叉机制的改进差分进化算法（DirDE）。导向交叉机制通过引导种群的全局搜索和局部开发方向提升算法收敛速度。同时，该机制基于父母个体的基因导向交叉帮助算法跳出局部搜索，避免陷入局部最优。实验部分设计了基准函数实验验证DirDE算法的寻优能力。实验分析结果展示，DirDE表现出更好的收敛性、精度及避免陷入局部最优的能力。最后，本文方法在真实的多项目党务活动调度优化线性规划模型上进行模拟实验，算法展现出竞争力，可作为现实党务活动调度问题求解的有效工具。

Abstract

To address the issues of unreasonable project activity scheduling and high expenditure， this paper proposes an improved differential evolution algorithm based on directional crossover mechanism （DirDE）. The mechanism enhances the algorithm's convergence speed by guiding the global exploration and local exploitation directions of the population. Meanwhile， this mechanism helps the algorithm jump out of the local search and avoid falling into the local optimum based on the gene guidance of the parent individuals. In the experimental section， benchmark function experiments are designed to verify the optimization ability of the DirDE. The experimental analysis results demonstrate that DirDE exhibits better convergence， accuracy， and the ability to avoid falling into local optima. Finally， the method proposed in this paper was tested through simulation experiments on a real-world linear programming model for multi-project party affairs activity scheduling optimization. The algorithm demonstrated its competitiveness and can serve as an effective tool for solving real-world party affairs activity scheduling problems.

Graphical abstract

关键词

人工智能技术 / 进化算法 / 差分进化算法 / 党务活动调度 / 导向交叉机制

Key words

artificial intelligence technology / evolutionary algorithm / differential evolution algorithm / party affairs activity scheduling / directional crossover mechanism

0 引　言

差分进化算法（Differential evolution algorithm， DE）^［1］是用于解决连续型问题的群智能优化算法，被广泛应用在医学图像分割^［2］、路径规划^［3］、资源调度^［4］和机器学习等领域^［5］。Cuevas等^［6］提出了一种基于DE的新颖自动图像多阈值方法，该方法利用DE计算高斯函数的系数来填充图像的一维直方图，实现自动阈值选择；Ayala等^［7］提出了一种用于确定图像分割所需的阈值组合的BDE算法，使用Otsu准则成功改善了解决方案的质量和收敛性；Liu等^［8］根据黏液菌群的觅食行为提出了一种改进的DE，即MDE，并基于MDE开发了一个多层级图像分割模型，用于乳腺癌分割，该方法的性能通过实验证明了有效性；Tarkhaneh等^［9］提出了ALDE，通过将自适应方法和新的变分策略融入DE中，以解决MRI脑图像分割问题；Xu等^［10］提出了一种基于记忆算法的蜻蜓算法（DA）和DE，利用Otsu和最小交叉熵（MCE）确定彩色图像分割的最佳阈值；Chen^［11］提出了一种改进的DE，称为AGDE，它结合了混沌游戏优化（CGO）的种子更新方法和关联策略（AS）。在CGO中提出了4种种子更新方法，使得不同位置的个体具有多次位置变化的机会，具有一定的随机性和接近最优解的特性，并将这4种种子更新方法融入DE中，增加了算法的种群多样性，并增加了算法跳出局部最优解的机会。Yang等提出将基于遗传算法应用于党务管理中的会议日程优化研究。该论文研究了如何利用遗传算法来优化党务管理中的会议日程安排，提高会议效率和资源利用率。但是，在多项目党务活动调度优化问题中，目前研究算法的收敛速度、精度和避免陷入局部最优的能力还具有提升的空间。

为解决多项目党务活动的调度复杂和困难的问题，本文提出了基于导向交叉机制的差分进化算法（DirDE）应用于多项目党务活动调度优化问题。其中，导向交叉机制在DirDE中增强了算法的开发和探索的平衡能力、种群的多样性以及算法跳出局部最优能力。进一步，本文设计了基于IEEE Congress on Evolutionary Computation（CEC）基准函数集的性能测试实验验证DirDE的性能。实验结果经过标准差、均值、威尔逊排名检验^［12］和弗瑞德曼检测^［13］等统计性方法分析。无论在哪种统计性方法的分析下，DirDE都展示了出色的优化能力。同时，本文将DirDE应用到多项目党务活动调度优化模拟实验。

1 基于导向交叉机制的差分进化算法

1.1　导向交叉机制的原理

参考文献［14］发现，根据最优个体的信息，导向交叉策略（DX）可以获得强大的搜索能力。受该文献的启发，将DX策略引入原始的差分进化算法可以提高收敛速度和准确性。DX策略的原理如下。

DX策略中的关键参数包括交叉概率（p_{\mathrm{c}\mathrm{v}}）、方向概率（p_d）和乘法因子（\mathrm{\alpha }）。p_{\mathrm{1}}和 p_{\mathrm{2}}表示两个随机个体。p_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}}^j和p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^j是第j个随机个体的平均值和最佳值。DX的公式如下所示。

\mathrm{v}\mathrm{a}\mathrm{l}=\left\{\begin{array}{l}\mathrm{1}-\mathrm{0}.{\mathrm{5}}^{e^{\left[\frac{\left|p_{\mathrm{1}}^j-p_{\mathrm{2}}^j\right|}{\left(y_u^j-y_l^j\right)}\right]}},p_{\mathrm{1}}^j\ne p_{\mathrm{2}}^j\\ \mathrm{1}-\mathrm{0}.{\mathrm{5}}^{e^{\left[\frac{\left|p_{best}^j-p_{mean}^j\right|}{\left(y_u^j-y_l^j\right)}\right]}},p_{\mathrm{1}}^j=p_{\mathrm{2}}^j,p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^j\ne p_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}}^j\end{array}\right.（1）

\beta =\frac{r}{{\alpha }^{\mathrm{2}}}（2）

式中：\mathrm{v}\mathrm{a}\mathrm{l}和\beta为随迭代而变化的两个变量；r为一个随机变量，且r\in \left(\mathrm{0,1}\right)；y_{\mathrm{u}}^j和y_{\mathrm{l}}^j分别为第j个维度中目标函数的上界和下界。

c_{\mathrm{1}}^j=\mathrm{v}\mathrm{a}\mathrm{l}\times \left(p_{\mathrm{1}}^j\pm p_{\mathrm{2}}^j\right)\pm

{\alpha }^{r_{\mathrm{1}}}{\mathrm{e}}^{\left(\mathrm{1}-\beta \right)}\left(\mathrm{1}-\mathrm{v}\mathrm{a}\mathrm{l}\right)\times \left|p_{\mathrm{1}}^j-p_{\mathrm{2}}^j\right|（3）

c_{\mathrm{2}}^j=\left(\mathrm{1}-\mathrm{v}\mathrm{a}\mathrm{l}\right)\times \left(p_{\mathrm{1}}^j\pm p_{\mathrm{2}}^j\right)\pm

{\alpha }^{(\mathrm{1}-r_{\mathrm{1}})}{\mathrm{e}}^{\left(-\beta \right)}\mathrm{v}\mathrm{a}\mathrm{l}\times \left|p_{\mathrm{1}}^j-p_{\mathrm{2}}^j\right|（4）

c_{\mathrm{1}}^j=\mathrm{v}\mathrm{a}\mathrm{l}\times \left(p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^j+p_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}}^j\right)\pm

{\alpha }^{r_{\mathrm{1}}}{\mathrm{e}}^{\left(\mathrm{1}-\beta \right)}\left(\mathrm{1}-\mathrm{v}\mathrm{a}\mathrm{l}\right)\times \left(p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^j-p_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}}^j\right)（5）

c_{\mathrm{2}}^j=\left(\mathrm{1}-\mathrm{v}\mathrm{a}\mathrm{l}\right)\times \left(p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^j+p_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}}^j\right)\pm

{\alpha }^{(\mathrm{1}-r_{\mathrm{1}})}{\mathrm{e}}^{\left(-\beta \right)}\mathrm{v}\mathrm{a}\mathrm{l}\times \left(p_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^j-p_{\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}}^j\right)（6）

方程式（3）~（6）将根据p_{\mathrm{d}}确定式中的±。c_{\mathrm{1}}和c_{\mathrm{2}}是由DX策略生成的新个体，其中\alpha =\mathrm{0.95}，r_{\mathrm{1}}\in \left(\mathrm{0,1}\right)。假设个体的维度为d。

1.2　DirDE算法及复杂性分析

DirDE的结构主要包括种群初始化、基因变异、基因交叉和基于导向交叉机制的种群更新策略。其中，基因交叉策略是随机性地对两个体位置进行交流。导向交叉机制则利用种群最优个体作为父母个体，基于父母个体的位置信息结合缩放因子进行导向交叉，引导算法收敛到最优值。随后，DirDE利用贪婪选择机制对种群的个体进行筛选，提高算法的收敛速度。其中，图1展示了DirDE算法的优化流程，导向交叉机制作为算法的关键策略，帮助算法更智能地在搜索空间进行搜索。本文提出结合导向交叉机制的DirDE，通过引导种群进行基因的交叉和变异操作提升了种群多样性、搜索能力以及避免陷入局部最优的能力。

附录表A1中的算法1是DirDE的伪代码，详细解释了本文提出的基于导向交叉机制的差分进化算法的改进结构。假设算法的种群大小为N，评估次数为\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{f}\mathrm{e}\mathrm{s}，个体维度为D。原始DE算法的算法复杂度是O(N+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{f}\mathrm{e}\mathrm{s}(N\bullet D))。其中，DirDE算法的复杂度由种群初始化策略、差分进化策略和导向交叉机制的复杂度组成。因此，DirDE的总体复杂度为O(N+\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{f}\mathrm{e}\mathrm{s}(N\bullet \mathrm{2}D))，与DE算法的算法复杂度相似，可近似为O(\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{f}\mathrm{e}\mathrm{s}(N\bullet \mathrm{2}D))。

2 实验仿真及分析

2.1　实验设置

基于IEEE Congress on evolutionary computation（CEC）的基准函数集，本文设计了DirDE与其他优秀的群智能优化算法进行了性能的验证和对比。函数实验中的对比算法包括DE^［1］、SCA、PSO^［15］、CS、MFO、ACOR等优秀的群智能优化算法。实验分析结果通过标准差（STD）、平均值（mean）、威尔逊排名检验（WSRT）和弗瑞德曼检测（FT）等统计分析方法评估。

为确保实验公平，所有算法在相同条件下测试。对比算法使用评估原理（FEs）限制循环次数，在计算个体适应度时，评估次数增加。评估原则保证实验的有效性和确定性，MaxFEs为30万。算法种群规模为30，为降低随机性，将随机测试30次。

2.2　基准函数优化分析及平衡性分析

表1为本次实验的威尔逊排名检验结果，DirDE威尔逊排名第一，“Mean”是弗瑞德曼检测结果，指示DirDE在弗瑞德曼检测中表现最优秀（1.588）。相对其他算法，DirDE具有明显的求解优势。

实验结果显示，DirDE相对差分进化算法（DE），在6个函数中获得更好的优化结果，且在4个函数上表现类似。在整个函数集中，DirDE的表现均优于SCA和PSO。综合分析，DirDE在函数集上收敛精度更高。附录表A2为对比实验结果，含标准差（STD）和平均值（AVG）。STD代表算法在函数求解中的稳定性，AVG表现准确性。STD越小，算法性能越稳定；AVG越小，算法性能越准确。表中指出每个函数上表现最优秀的算法。在F1至F10上，DirDE均获得最佳或并列最佳STD和AVG。因而，DirDE是表现最精确、稳定的函数集算法。

图2中展示了对比算法的收敛曲线。本文给出F1和F3上的算法收敛曲线。在F1的收敛曲线中，DirDE展示了跳出局部最优的能力，而且基于导向交叉机制的DirDE能够在搜索前期两次跳出局部最优，获得最好的结果。在F3的收敛曲线中， DirDE能够更快速地找到基准函数的最优值。同时，算法展现出更好的收敛速度和精度。其中，DirDE在搜索初段的收敛速度最快。在DE、MFO、PSO和SCA等算法收敛前，DirDE已经收敛。总之，收敛曲线展示了DirDE在函数集上更好的收敛速度、精度和跳出局部最优的能力。

进一步，本部分为了测试DirDE的稳定性和平衡性，测试了DirDE和原算法DE的算法平衡性。图3展示了DirDE在基准函数集的F1和F3函数上算法的全局探索和局部开发的平衡结果。图3中展示在函数F1上原始算法的全局探索能力是10.815 2%，局部开发能力是89.184 8%；DieDE法的全局探索能力是7.485 8%，局部开发能力是92.514 2%。DirDE通过提升算法的局部开发能力提升了算法跳出局部最优的能力。综合函数实验的评估结果，DirDE结合导向交叉机制提升了种群多样性，拥有更好的函数优化能力。DirDE是有效的函数优化工具。

2.3　DirDE的参数敏感性实验

DirDE的关键参数是变异率（p_{\mathrm{c}\mathrm{r}}），算法的性能受p_{\mathrm{c}\mathrm{r}}值的影响。在本节中，设计了关于不同变异率值对DirDE性能影响的参数敏感性实验。理论上，参数p_{\mathrm{c}\mathrm{r}}的范围是（0，1］。在实际实验中，p_{\mathrm{c}\mathrm{r}}的取值分别设为0.2、0.4、0.6、0.8和1。表2显示了不同变异率值下DirDE的性能表现。表2中的值为排名。当p_{\mathrm{c}\mathrm{r}}=\mathrm{0.8}时，DirDE在10个函数（如F3、F5和F7）上均排名第一，整个函数集中平均排名也是第一。综上所述，当变异率为0.8时，DirDE在优化函数时表现更好。为确保算法的稳定性，本工作中DirDE的p_{\mathrm{c}\mathrm{r}}取值为0.8。

2.4　基于IEEECEC 2017实验分析

为测试DirDE算法在函数表现中的迁移能力，本部分在IEEE CEC2017的多类型函数集上进行了DirDE和其他优秀群智能算法之间的比较实验。表3展示了多类型函数集中的函数，包含多模态函数、单模态函数、组合函数和混合函数。

表4为本次实验的威尔逊排名检验结果，DirDE威尔逊排名第一，“Mean”是1.922。相对其他算法，DirDE具有明显的求解优势。其中，DirDE算法比ACOR算法在函数集上有7个函数表现更优秀。

附录表A3展示了在IEEE CEC2017函数集对比实验结果的AVG和STD分析。在F1至F9上，DirDE均获得最佳或并列最佳AVG和STD，表现出最精确、稳定的优化能力。进一步，表5显示了WSRT得到的P-value值。DirDE在IEEE CEC2017的大多数函数上获得的P-value值小于0.05，这表明该消融实验结果在统计意义上具有显著的可靠性。

图4展示了对比算法的收敛曲线。根据本文给出在IEEE CEC 2017函数集F2和F8上的算法收敛曲线，DirDE都展示了比SCA、PSO、BA等算法更好的全局收敛能力。DirDE能够在搜索前期迅速地搜索到搜索空间的最优值区域，进而展开局部开发，而且算法始终保持最小的目标值。

基于IEEE CEC 2017函数集的DirDE比较实验结果分析，DirDE算法在面对多类型函数时，如多模态函数、单模态函数和组合函数等，都表现出更加稳定的优秀优化能力。最后，实验结果也通过P-value的统计性分析得到可靠性的验证。

2.5　党务活动调度优化应用

随着党员增加和党务工作发展，党务活动优化问题已成研究重点。调度优化需同时考虑约束条件和目标函数，其中约束条件包含控制变量、等式/不等式以及线性/非线性形式。

传统解决多项目党务调度优化问题的方法包括梯度信息和线性规划模型，但存在精度低和效率问题。近年来，群智能算法逐渐成为热门优化方法，可处理不可微分和大数据问题。因此，本文采用DirDE解决党务活动调度优化问题，并进行实验。党务活动调度的优化问题的优化目标是最小化成本问题。总活动时长假设是早9点到晚16点（x_{\mathrm{1}}）、总活动项目数量（x_{\mathrm{2}}）、各项目花费（x_{\mathrm{3}}）和各项目时长（x_{\mathrm{4}}）是党务活动调度优化问题中的4个关系变量。

本实验基于真实的多项目党务活动调度线性规划模型，其中，式（7）给出了党务活动线性规划模型中的4个优化变量；式（8）展示了求解多项目党务活动优化最小活动经费的目标函数。进一步，在该线性规划模型中，还根据真实多项目党务活动约束条件分别建立的约束模型。如g_{\mathrm{1}}\left(\vec{x}\right)=x_{\mathrm{1}}-{\displaystyle \sum _{j=\mathrm{0}}^{\mathrm{6}}}{x}_j\le \mathrm{0}代表所有活动的总用时要小于党务活动的时间限制。

为了验证DirDE的党务活动调度能力，表6给出了多项目党务活动的相关数据。式（7）~（9）展示了该优化问题的线性关系模型。

\vec{x}=\left[x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}}\right]（7）

\mathrm{m}\mathrm{i}\mathrm{n}f\left(\vec{x}\right)=ic\times x_{\mathrm{1}}+{\displaystyle \sum _{j=\mathrm{0}}^{x_{\mathrm{2}}}}{x}_{\mathrm{3},j}\times x_{\mathrm{4}}（8）

\mathrm{s}.\mathrm{t}.\left\{\begin{array}{l}{g}_{\mathrm{1}}\left(\vec{x}\right)=x_{\mathrm{1}}-{\displaystyle \sum _{j=\mathrm{0}}^{\mathrm{6}}}{x}_j\le \mathrm{0}\\ g_{\mathrm{2}}\left(\vec{x}\right)=\left[\frac{\mathrm{m}\mathrm{a}\mathrm{x}\left(x_i\right)}{\mathrm{20}}\right]\le \mathrm{0}\\ g_{\mathrm{3}}\left(\vec{x}\right)=-\left[\mathrm{30}\times t+\left({\displaystyle \sum _{j=\mathrm{0}}^{\mathrm{6}}}{x}_j-\mathrm{20}\times t\right)\right]\le \mathrm{0}\\ \mathrm{0}\le x_{i,\left(\mathrm{1}\dots \mathrm{6}\right)}\end{array}\right.（9）

表7展示了DirDE算法在党务活动调度优化模拟实验的5个优化求解结果。其中，实验设置的算法种群大小为30，算法的优化迭代次数为300，模拟的党务活动项目数为6个。在5种实验结果中，DirDE在方案二和方案五分别获得的最小成本是4 020元，是用了最少的时间完成所有项目并取得最小的成本，党务活动的项目执行顺序是CFADEB。实验结果证明本文提出的方法获得优异的党务活动调度优化结果。

3 结束语

本文研究了多项目党务活动调度问题优化方法，提出一种基于导向交叉机制的差分进化算法，并命名为DirDE。DirDE通过增强种群的多样性和算法的开发及探索的平衡性提升了收敛速度和跳出局部最优的能力，随后，基于IEEE CEC的基准函数集验证了DirDE的性能。同时，DirDE进行了党务活动调度优化模拟实验，并获得优秀的经济和时间计算成本。因此，DirDE可作为基准函数优化和党务活动调度优化的有效求解工具。

4 附　录

参考文献

[1] Storn R, Price K. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359.

[2] Zhao D. Ant colony optimization with horizontal and vertical crossover search: fundamental visions for multi-threshold image segmentation[J]. Expert Systems with Applications,2021, 167: 114122.

[3] 赵鑫, 杨雄飞, 钱育蓉. 改进的蚁群优化算法求解旅行商问题[J]. 计算机工程与设计, 2022, 43(4): 962-968.

[4] Zhao Xin, Yang Xiong-fei, Qian Yu-rong. Improved ant colony optimization algorithm for TSP[J]. Computer Engineering and Design, 2022, 43(4): 962-968.

[5] 肖耀涛. 基于改进蚁群优化算法的云计算资源调度 [J]. 微型电脑应用, 2022, 38(2): 160-163.

[6] Xiao Yao-tao. Cloud computing resource scheduling based on improved ant colony optimization algorithm[J]. Microcomputer Applications, 2022, 38(2): 160-163.

[7] 朱显辉, 于越, 师楠, 等. BP神经网络的分层优化研究及其在风电功率预测中的应用[J]. 高压电器, 2022, 58(2): 158-163.

[8] Zhu Xian-hui, Yu Yue, Shi Nan, et al. Research on hierarchical optimization of BP neural network and its application in wind power prediction[J]. High Voltage Apparatus, 2022, 58(2): 158-163.

[9] Cuevas E, Zaldivar D, Pérez C M. A novel multi-threshold segmentation approach based on differential evolution optimization[J]. Expert Systems with Applications, 2010, 37(7): 5265-5271.

[10] Ayala H V H, Santos F M, Mariani V C, et al. Image thresholding segmentation based on a novel beta differential evolution approach[J]. Expert Systems with Applications, 2015, 42(4): 2136-2142.

[11] Liu L. Performance optimization of differential evolution with slime mould algorithm for multilevel breast cancer image segmentation[J]. Computers in Biology and Medicine, 2021, 138: 104910.

[12] Tarkhaneh O, Shen H. An adaptive differential evolution algorithm to optimal multi-level thresholding for MRI brain image segmentation[J]. Expert Systems with Applications, 2019,138: 112820.

[13] Xu L, Jia H, Lang C, et al. A novel method for multilevel color image segmentation based on dragonfly algorithm and differential evolution[J]. IEEE Access, 2019, 7: 19502-19538.

[14] Chen J. Multi-threshold image segmentation based on an improved differential evolution: case study of thyroid papillary carcinoma[J]. Biomedical Signal Processing and Control, 2023, 85: 104893.

[15] García S, Fernández A, Luengo J, et al. Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: experimental analysis of power[J]. Information Sciences, 2010, 180(10): 2044-2064.

[16] Derrac J, García S, Molina D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2021, 1(1): 3-18.

[17] Das A K, Pratihar D K. Solving engineering optimization problems using an improved real-coded genetic algorithm (IRGA) with directional mutation and crossover[J]. Soft Computing, 2021, 25(7): 5455-5481.

[18] Kennedy J, Eberhart R. Particle swarm optimization[C]∥ICNN'95-international conference on neural networks, Perth, Australia, 1995: 1942-1948.

基金资助

吉林省重点研发项目(20190302027GX)