结合正交补空间反向学习策略的自然计算方法_黄亮.pdf

小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家自然科学基金项目（）资助；年度黑龙江省自然科学基金项目（）资助；哈尔滨市科技局科技创新人才研究专项项目（）资助；哈尔滨师范大学计算机科学与信息工程学院科研项目（）资助 作者简介：黄 亮，男，年生，硕士研究生，研究方向为群体智能；张 军（通讯作者），男，年生，硕士，教授，会员，研究方向为网络安全；季伟东，男，年生，博士，教授，研究方向为群体智能结合正交补空间反向学习策略的自然计算方法黄 亮，张 军，季伟东（哈尔滨师范大学 计算机科学与信息工程学院，哈尔滨）：摘 要：反向学习策略可以提高自然计算方法性能，然而现有策略生成的反向解多样性不足，为此提出一种反向学习策略，算法根据群体最优个体计算其正交补空间的反向解，增加种群多样性以提高找到全局最优解的概率 将所提策略应用到标准粒子群与标准遗传算法并在基准测试函数上进行验证，实验结果表明策略能提高算法在多数测试函数上的性能 最后，将策略与重心反向学习结合应用于随机拓扑粒子群算法，函数集作为测试函数，与四种经典或性能优异的反向学习粒子群算法进行对比，实验结果验证了策略的有效性关 键 词：正交补空间；反向学习；多样性；粒子群算法；自然计算中图分类号：文献标识码：文 章 编 号：（），（，）：，：；引 言自然计算（）通常代指从自然中获取灵感而发展起来的算法，主要研究领域包括人工神经网络，群体智能，进化计算，人工免疫系统等 自然计算方法具有自学习、自组织和自适应的特点，在传统优化算法难以求解的各类复杂问题中发挥重要作用 例如将粒子群算法（，）用于电力系统经济调度问题以优化燃料成本，将差分进化算法用于光电精跟踪系统以提高收敛速度与辨识准确度，将遗传算法用于求解标签印刷车间的排产问题以提高加工效率，将蚁群算法用于求解带时间窗的车辆路径规划问题以优化物流配送效率等各种自然计算方法均将候选解当作不同个体，并通过模拟不同的自然行为来设计候选解的迭代方式，以期找到问题的最优解 然而随着算法迭代进行，种群可能会陷入局部最优区域，导致算法效果变差 因次，设计有效策略使群体跳出局部极值区域仍是自然计算的重要研究方向针对自然计算陷入局部最优问题已提出许多优化策略，如将种群分组或对种群数据增加变异偏置，来增加多样性，将易陷入局部极值的算法与全局搜索能力强的算法结合来增强搜索能力，其中反向学习相关研究较多 等人将反向学习策略及柯西变异算子应用于粒子群算法，提出了基于反向学习的粒子群算法（，），算法在 个测试函数上相较原始 有所提升；在随后的研究中，等人改进反向位置的计算公式，扩大反向粒子搜索范围，实验结果表明改进算法在部分测试函数上表现优异 反向学习策略易于应用，可与多种算法结合 等人将反向学习策略应用于竞争粒子群算法，在竞争过程中部分粒子利用反向学习更新位置；钱晓宇等人由此启发，提出一种基于 局部搜索的反向学习竞争粒子群优化算法 等人将反向学习策略与 分布结合应用于差分进化以提高算法收敛速度与搜索能力；等人将反向学习策略应用于差分进化以解决多任务优化问题；等人基于反向学习差分进化提出一种二进制差分进化算法，解决多分类模型的特征选择问题 等人利用反向学习策略为萤火虫算法获得更好的初始种群并提高算法收敛速度；等人将反向学习策略应用于萤火虫算法以帮助个体跳出局部极值范围；周凌云等人将正交实验设计与反向学习结合应用于萤火虫算法，利用正交设计寻找个体与反向个体最优的维度组合 等人将随机反向学习策略应用于灰狼算法帮助种群跳出局部最优 王坚浩等人用混沌反向学习策略初始化种群解，为鲸鱼优化算法全局搜索奠定多样性基础 以上反向学习策略均用粒子关于解空间中心的对称点作为反向解，缺少探索粒子当前位置正交空间的能力，增强种群多样性能力有限本文基于线性空间的正交补空间理论，提出一种新颖的反向学习策略，增强种群多样性使算法能够探索群体最优粒子的正交空间 本策略不依赖具体的算法操作，因而具有普适性 基于正交补空间反向学习策略的自然计算方法 正交补空间为了说明策略的思想，先引入正交补空间的定义及相应定理定义 设 是欧式空间 的子空间，记 为一切与 中向量都正交的向量所成的集合，称为 在 中的正交补空间定理 设 是欧式空间 的子空间，则 有直和分解 依据定理，任何欧式空间 都可以分解为 个属于此空间的子空间 及其正交补空间 设线性方程组对应矩阵记为 ，此矩阵的行向量生成的向量空间记为（），此线性方程组的解所组成的空间记为（），则（）与（）构成 的一对正交补空间例如，设有线性方程组：|（）其对应矩阵：|，（）的行向量为 （，），由行向量生成的空间：（），（）（）共有 个线性无关向量求解线性方程组（）得到 个线性无关的解向量，由解向量生成的空间（），因为（）中所有向量均为，的线性组合，则由线性方程组可知任取（），有 ，任取（），有 （）（）其中，为 在式（）中的相应值 由式（）可得（）中的向量均正交于（）中的向量，特别的有 个（）中线性无关向量与 个（）中线性无关向量正交，则可得到 个线性无关的 维向量，并以此生成整个 空间，因此证得（）与（）构成 的一对正交补空间 策略基本原理本文提出一种反向学习策略，根据种群当前最优解，计算其正交补空间的基（），并以此生成新的个体设所求问题维度为，将问题解空间记为，种群最优解记为 （，），对应正交补空间记为 建立方程组：（）可求得 个线性无关的解向量，应用 将解向量组正交单位化，得到 内的正交单位化的解向量组，根据这组解能生成 内的任意向量，且由，可以生成 内的任意向量，即可以生成任意候选解整个解空间 的信息可分为两部分，一部分为 所在直线空间的信息，另一部分为 空间信息，当群体陷入局部最优时，可通过组合两部分信息生成新个体以跳出局部极值范围 设：（）（，）（，）（，）（）（），（，）（）（）（）（）（），（，）（）其中 表示当前迭代次数，表示总迭代次数，（，）表示在，上服从均匀分布的随机数，表示向量求模长运算，表示 空间内向量的最大模长，、分别表示解空间的取值上下限，表示当前种群的最优解，由式（）可知 位于 中，其模长服从均值从 至 变化的高斯分布 使用式（）式来计算反向解，迭代初期，生成的反向解接近 空间，随着迭代进行，反向解散布在整个空间中，充分探索潜在最优解，后期反向解靠近 所在空间 正交补空间反向学习策略分析为了说明策略有效性，设问题维数 ，解空间取值范围为，则当 分别为、及 时，根据 计算其正交补空间的正交单位化的解向量组 ，根据公式（）计算 ，根据公式（）、公式（）生成 补空间内的随机个体，最后根据公式（）计算反向解 生成的反向解（，）分布如图 所示由图 可知当 值较小时，反向解多数分布在 内，期 黄 亮 等：结合正交补空间反向学习策略的自然计算方法 且模长较长，离 位置较远；当 值适中时，反向解分布在整个解空间，模长适中，充分探索空间中潜在的最优解；当 较大时，反向解多数分布在 所在直线空间，模长与 相似，充分探索 附近的空间 可见算法前期探索远离的区域，种群多样性强，后期侧重开发区域，寻找更高精度解的同时保持多样性图 为不同值时反向解分布 算法的实现策略本节给出算法具体实现步骤，算法流程图如图 所示 其伪代码如算法 所示：算法 基于正交补空间反向学习策略的自然计算方法步骤 初始化种群数，群体位置矩阵 等参数，计算个体对应适应度值（）；步骤 ；步骤 ；步骤 根据式（）计算 的正交单位化解向量组；步骤 根据式（）、（）分别计算、；步骤 根据式（）、（）、（）计算 个当前 反向解，记为；步骤 对 中的 个反向解进行越界处理；步骤 ；步骤 计算（）；步骤 （）（）步骤 步骤 ；步骤 ；步骤 ；步骤 种群按照原始自然计算方法进化；步骤 ；步骤 ；图 算法流程图 算法 中 表示种群总迭代次数，表示在，上服从均匀分布的随机数，表示使用反向策略的概率，依据文献的实验结果，在 范围内取值可以提高反向算法寻优精度 为了更精确的对比原始反向策略与本文所提反向策略的性能差异，避免因超参数值的不同而导致的实验结果差异，采用原始反向策略的 值，即 ，对越界个体采用吸收墙的处理方式，用解空间的边界值替换越界值 步骤 的具体实现依托仿真平台，以 环境为例，可用 函数计算方程组的正交单位化解向量组 仿真实验与结果分析 经典函数测试实验 实验设置及结果分析为了验证本文策略的有效性和普适性，将其分别应用到标准 与标准遗传算法（，）中，记为正交补空间反向学习粒子群算法（，）及正交补空间反向学习遗传算法（，）仿真平台为，将 与 及 进行对比实验，比较两种反向策略的性能差异 参数设置：学习因子 ，惯性权重线性减小，将 与 进行对比实验，参数设置：交叉概率为 ，变异概率为 实验适应度函数为当前位置对应函数值 公共参数设置：种群数 ，算法迭代次数 ，维数 选取 个经典测试函数测试算法性能，其中 为多模函数，剩余函数为单模函数，因 在 维上的最小值缺乏精准数据，暂定为 作为衡量不同算法表现的标准，各函数表达式如表 所示 每个函数重复运行 次，取运行结果平均值与全局最小值的误差（）作为评价标准，计算 次运行结果的标准差（），进行 检验，结果如表 所示 碍于篇幅限制，选取算法在多模函数、及单模函数、上的收敛图比较算法性能，结果如图 所示由实验结果可知，相较、而言，在、函数上求得的解的精度较高 尤其对于、，精度提高明显 在除、以外的函数上寻得解的精度均高于标准，但精度提升相较 并不明显，这是因为 本身并不易于陷入局部极值，反向策略对其性能提升有限 对于 多模函数，应用反向策略的算法寻得解的精度普遍高于原始算法，的全局极值点靠近解空间边界，且边界上存在许多局部极值点，前期大范围探索解空间，小 型 微 型 计 算 机 系 统 年易陷入远离全局极值点的局部极值点，随着迭代进行探索范围减小，算法偏向开发当前群体最优点周边区域，因此最终找到局部极值 因此对多模函数而言，反向策略能帮助算法跳出局部极值区域继续搜寻全局最优解，而本文策略所生成的反图 算法在 个函数上的收敛曲线 表 标准测试函数 测试函数维数解空间最小值，（），()，()（）()（），（）（）（）（）（），()，（）()()()，（），（）（）()()，（）（），（）（），期 黄 亮 等：结合正交补空间反向学习策略的自然计算方法 续表 测试函数维数解空间最小值 （）（），（）（）（）（），（），向解相比 生成的反向解更加多样化，能探索更大解空间范围，因而更有可能找到全局最优解 根据“没有免费午餐”定理，反向策略算法没能在所有类型函数上都寻得最高精度的解，但在大部分函数上其解的精度高于对比算法，且剩余函数上解的精度相近，表明本文所提策略的有效性从收敛曲线图 中可以看出，在相同的迭代次数时，不论在单模函数还是多模函数上均寻得精度高于 与 的解，因此其收敛速度快于对比算法 尤其对于、而言，对比算法收敛曲线在后期趋于平缓，而 收敛曲线在后期仍有明显的下降趋势，说明正交补空间反向学习策略相比 的反向学习策略改善种群多样性能力更强，找到最优解的概率更大 在除 外的函数上收敛速度均快于，其收敛曲线在 上呈阶梯状下降，在、上末端仍有下降趋势，表明本文策略具有较强的探索能力，能加快算法收敛速度，有效提高算法寻优效率为进一步验证本文策略在高维问题下的性能，分别设置问题维数 、，对、种算法进行仿真实验 在高维度下计算适应度值溢出，因此选用剩余的 个函数作为测试函数，其他参数设置同上 取运行结果平均值与全局最小值的误差作为评价标准，如表 所示表 算法在 个标准测试函数上优化结果 函数 （）（）（）（）（）小 型 微 型 计 算 机 系 统 年表 算法在高维问题上优化结果 维数函数 由表 可知，在 、时，与、相比在除、的测试函数上均取得精度最高的解，与 相比在除、的测试函数上取得高精度解 两种问题维度下，在、上均寻得精度相似的最优解，说明本文策略能应用于高维问题求解，对其有较好的鲁棒性 时间复杂度运行时间是衡量算法性能的