阴阳平衡优化算法改进：小波精英学习与多角度搜索实践

先说我做这件事的背景。手头有个工程优化问题要解维数不低目标函数长得也不规则于是我把目光放到了阴阳平衡优化算法上。这算法全名是Yin-Yang Pair Optimization简称YYPO2016年提出核心思路是用一阴一阳两个解点一个负责大范围探索、一个负责局部开发通过交替扩展与收缩搜索区间来逼近全局最优。算法结构简单到令人怀疑人生——它不搞什么种群几十上百的套路一次迭代就维护两个主解计算量非常小特别适合目标函数昂贵、每次评估都烧时间的场景。但我实际用下来原版YYPO并没有论文里那么顺滑。跑低维单峰函数还行一到高维多峰函数收敛速度和精度就双双拉胯局部搜索那一下也偏“蛮力”缺乏方向感经常在最优解附近磨磨蹭蹭就是进不去。所以后来我做了一版改进在原始YYPO框架里引入小波精英解学习和多角度搜索两种机制把这套算法改造成更适合实际工程调度的版本。今天这篇就把整个改造过程摊开来讲从设计思路、公式推导、代码骨架到踩坑记录一条线拉完希望能给正在做元启发式算法改进或者用优化算法的朋友一点参考。1. 先看原始算法阴阳平衡优化到底在优化什么1.1 原版YYPO的两个角色阴阳平衡优化的出发点其实特别朴素。它把优化过程拆成两种互补的行为一种是“广撒网”在搜索空间里到处跑尽量避免漏掉潜在的好区域另一种是“深挖洞”锁定一个局部区域反复精修把解的质量往上推。这两个行为对应到算法里就是一阴一阳两个解点叫法不唯一有的叫Yin点和Yang点有的干脆叫Point1和Point2。每个解点除了自身位置之外还维护一个搜索半径。迭代时在这个解点周围按照半径大小做小规模采样生成几个新候选解然后留优去劣。这里出现了这套算法最核心的机制——动态扩展与收缩如果当前这一轮没找到更好的解说明这个区域的潜力可能已经挖得差不多了半径收缩收敛得更精细如果找到了更好的解说明这个方向上还有戏半径扩大继续深入搜。两个解点的半径调整策略其实可以不一样这就形成了一种天然的“探索开发”分工。这套设计的好处是内存开销近乎为零不需要像粒子群那样维护速度矩阵也不需要像遗传算法那样做完整的交叉变异群体操作。对于目标函数是有限元仿真、流体计算这类跑一次就要几秒甚至几分钟的场景YYPO这种“省钱”的架构简直是天选之子。我最早就是冲着这一点去的。1.2 原版算法的三个短板不过省钱的代价也很明显原版YYPO在实际使用中至少有三处让我觉得不顺手。第一是高维收敛慢。当维度超过30的时候单靠一个半径去整体搜索实际上是使不上力的。高维空间里大部分区域离最优解都很远而且各个维度的“地形陡峭程度”往往完全不同用一个统一半径描述整片区域等于要求一个近视眼走迷宫——看不清细节全靠运气撞。第二是局部精修太钝。原版局部搜索的扰动基本上就是均匀或高斯随机方向感很弱。哪怕已经跑到全局最优附近也需要花大量迭代逐点磨进去像用砂纸给钻石抛光理论上可行效率上感人。第三是信息利用太单薄。两个解点之间虽然名字上叫“阴阳互补”但实际的信息交互很有限基本各搜各的档案集archive的精英解也主要用来替换主解没有进一步被“学习”。这就导致一个很有价值的局部信息被白白浪费——明明已经有一个解知道某条路径能走得通另一个解却完全不知道还得自己从头去试错。这些短板就是我做改进的地基。我的整体思路很明确在不改变YYPO轻量计算这个核心优势的前提下给它装上两个新的武器——用精英解来提供“学习榜样”用小波来提供“有节奏的扰动”再用多角度搜索来补足“方向多样性”。下面分别细说。2. 小波精英解学习把“震荡”变成一种搜索武器2.1 为什么选小波而不是普通随机扰动先回答一个最直接的问题想给算法加扰动高斯变异、柯西变异不都现成吗为什么一定要用小波我给自己的解释是小波这个工具自带时频局部化特性用大白话讲就是它既能在时间轴上定位又能刻画频率特征。把它搬到优化问题里小波函数的幅值可以在搜索空间里产生一段“有大小、有方向、有节奏”的震荡而不是那种完全无规律的噪声。这种震荡更接近我们在最优解附近想要的搜索行为离得远时大幅摆动快速试探靠近时小幅抖动精细收敛。另一个实际原因是可调参数直观。小波函数往往带尺度因子和平移因子尺度因子控制波形伸缩平移因子控制波形位置。放在优化里尺度因子可以对应搜索步长平移因子可以对应扰动方向。调参的时候脑子里的物理图像非常清楚不像调高斯方差那样全凭感觉。当然还有一点很实际的考虑小波的函数形式大多数都很轻量墨西哥帽小波、Morlet小波这类计算就是几次乘法和指数运算开销比一次真实目标函数评估小几个数量级。放进YYPO这种“每次只评估少数几个解”的框架里非常合适不会喧宾夺主。2.2 精英解学习的实现设计“精英解学习”这个概念本身并不新鲜很多算法都有类似的“向最优个体学习”的操作核心就是让当前解朝精英解的方向靠近。问题是怎么靠近。直接线性插值太生硬容易把种群多样性搞没完全随机学又等于没学。我的做法是用小波函数来调制学习步长让每个解的移动轨迹带有一点“探测性”。具体流程是这样维护一个精英解集合可以取档案集archive里适应度靠前的若干解。每一轮学习阶段随机挑一个精英解( x_{best} )然后遍历当前主解附近的候选解让它们以精英解为锚点做一次小波变异。变异公式我用的形式是[ x_{new} x_{best} \lambda \cdot \psi(a, b) \cdot (x_{old} - x_{best}) ]其中( \lambda )是学习率控制整体步进强度(a, b)分别是小波的尺度因子和平移因子( \psi(a, b) )是小波函数在当前维数下的取值。( (x_{old} - x_{best}) )给出的是一个方向向量而小波函数值充当的是方向上的“节奏调制器”。这背后的小心思是如果直接用( x_{best} )替换( x_{old} )那就是纯粹复制算法很快丧失多样性容易过早收敛到一个局部区域。而用小波调制的步长既保证了解在向精英解靠拢的大方向又保留了围绕精英解附近震荡探索的能力相当于“跟着老师傅学手艺但手艺学来后自己还是要练一练”。2.3 小波函数怎么参与变异计算我在实现里用的是墨西哥帽小波形式简单、实值输出、不需要复数运算公式长这样[ \psi(x) (D - |x|^2) \cdot \exp\left(-\frac{|x|^2}{2}\right) ]其中( D )是决策变量维度( |x|^2 )是向量x的模长平方。直观上看这个小波函数在0附近是正峰往外走会变负、再衰减回0整体呈帽子形。这种形状的妙处在于它天然给变异一个“中心促进、边缘抑制”的特性——离精英解近的地方变异幅度大促进精细搜索离精英解远的地方变异迅速衰减不会盲目乱跳。尺度因子的设置我用了最土但是有效的方案随迭代次数衰减。迭代初期( a )大小波波峰覆盖范围广学习粒度粗允许大步长探索迭代后期( a )变小波峰变窄学习粒度细转为局部精修。这个衰减策略思路和退火算法是一样的前期重探索、后期重收敛。由于YYPO本身就有扩展收缩机制我把小波的尺度因子和主解的半径做了联动尺度随半径的收缩一起变小效果上比两者各自独立调整要好。平移因子b我一般直接取当前迭代代数主要作用是在不同阶段切换小波作用的位置避免每次都从同一个基准点开始学习。说人话就是让每次小波变异不是重复劳动而是不断换着角度逼近精英解。这里特别提醒一句小波变异不能每次都触发否则整个算法会退化成“绕着精英解打转”。我最后设定的是每隔L代做一次小波学习L根据问题规模在5到20之间调高频时收敛快但多样性下降低频时搜索稳但速度慢。这个频率对最终性能影响极大建议做参数敏感性实验的时候优先盯它。3. 多角度搜索放弃单行道改走立交桥3.1 单角度搜索的高维困境原版YYPO的问题是它搜索时只用“围绕当前半径随机采样”这一种姿势。这就好比在北京这种立体迷宫一样的城市里导航你手里只有一张平面地图虽然理论上每条路都能走但实际找起路来效率低到令人绝望。高维优化问题差不多就是这个状况表面上搜索空间是一个整体实际上每个维度、每个局部区域的地形完全不一样统一的搜索策略必然导致部分维度被反复搜、部分维度被冷落。我在调试时就撞到过这样的场景一个20维的Rosenbrock函数原版YYPO前500代一直在几个维度上疯狂试探另外几个维度几乎没怎么动。等我把每个维度的累计更新次数打出来才发现搜索资源分配严重不均。这种浪费在维度继续升高后会越来越严重也是很多元启发式算法在高维问题上的通病。3.2 三个具体的搜索角度与触发机制我给“多角度搜索”下的定义是不改变YYPO的主循环结构只是在每轮迭代中让两个解点有机会从三个不同维度去审视搜索空间。这三个角度我分别命名如下。第一个是坐标轮换角。把决策变量按维度拆开轮流只对单个维度做精细调整其余维度保持不动。这个操作解决的是维度间干扰问题——同时更新全部维度时某个维度的改进可能被另一个维度的劣化掩盖导致判断失准。坐标轮换本质上是把高维搜索拆成一堆一维搜索单看显得笨拙但配合全局搜索使用能有效提高单个维度的收敛质量。它不常触发每隔5到10代跑一轮每次只扫描一遍所有维度。实测下来在变量间耦合较低的问题上这个角度的提升非常明显相当于给算法加了一个“精修档位”。第二个是最优引导角。围绕档案集里当前最优的精英解做一次方向随机的Lévy飞行采样生成一个大步长候选解。Lévy飞行是那个重尾分布特点是大多数步长小、偶尔来个超大步长。动用这个角度的时机是算法陷入停滞的时候——连续多代最优解没有更新说明要么真的到顶了要么就是在局部极值里转圈。这时候一个大步长“越狱”试一下成本不高收益可能很大。我最开始在Rastrigin函数上测试原版算法跑到100代左右就停在某个局部坑里不动了加上这个机制后经常能靠一发Lévy飞行跳出坑来虽然也有跳失败的时候但整体成功率高到值得保留。第三个是阴阳互看角。让阴点参考阳点的历史位置信息生成候选解阳点也反过来参考阴点的历史位置信息。名字听着玄乎实质就是对偶信息交换——两个解点虽然分工不同但它们各自跑过的轨迹都包含了对方没见过的地形情报。每次迭代用一定概率做一次交互采样我测试时发现让两个点互相学习对方近期的最优位置能显著提升搜索的一致性尤其是其中一个点已经找到黄金区域而另一个还在远处瞎晃的时候。这三个角度的触发方式我建议做成带优先级的随机触发而不是每次都全上。每次迭代先检查是否陷入停滞如果是就先触发最优引导角用Lévy飞行探路再根据当前迭代次数决定是否轮到坐标轮换角做精修最后有一小概率执行阴阳互看角。这样既保证了多角度的多样性又不会因为同时触发太多机制导致单轮计算量翻倍。4. 融合后的完整算法流程与关键参数4.1 整体主循环设计把前面两套机制塞回YYPO框架之后完整的主循环逻辑就变成了一个五阶段的流水线初始化、常规采样、小波学习、多角度搜索、归档更新。这个结构保持了原版算法“每次迭代只评估少量解”的轻量特点同时又让每一步都有更明确的搜索意图。常规采样这一段基本沿袭原版的设计——两个主解各自按照当前半径生成P个新解评估、择优、更新位置和半径。小波学习作为一个独立的可选阶段间隔L代激活前提是档案集非空。多角度搜索则被拆成三个子操作分散触发其中坐标轮换和阴阳互看放在常规采样之后最优引导角放在归档更新之前确保它拿到的精英解信息是最新鲜的。归档更新负责把本次迭代发现的优秀解存入档案集超过容量上限时就淘汰最差的。4.2 算法伪代码与参数说明这个结构我整理成Python伪代码如下注释里写了每个关键步骤的用意方便直接照着搭骨架# 简化版主循环逻辑重点展示机制衔接 # params: 学习间隔L, 学习率lambda, 小波尺度a, 停滞代数stall_generations yin initialize_random() yang initialize_random() archive [] for gen in range(max_generations): # 阶段一常规采样与半径更新原版YYPO核心 for point in [yin, yang]: candidates sample_around(point, point.radius, P) best_candidate evaluate_and_select(candidates) if best_candidate.better_than(point): point.position best_candidate.position point.radius expand(point.radius) # 找到更好解 - 扩展 else: point.radius contract(point.radius) # 没找到更好解 - 收缩 # 阶段二小波精英解学习每隔L代触发 if gen % L 0 and len(archive) 0: x_best random_choice(archive) for point in [yin, yang]: x_old point.position psi mexican_hat_wavelet(x_old - x_best, scalecurrent_scale(gen)) x_new x_best lambda_ * psi * (x_old - x_best) if evaluate(x_new).better_than(point.position): point.position x_new # 阶段三多角度搜索的三个子操作 if is_stalled(archive, stall_generations): levy_candidate levy_flight(archive.best_position) # 角度二最优引导 archive.update_if_better(levy_candidate) if gen % 7 0: coordinate_scan(yin, yang) # 角度一坐标轮换精修 if random.random() 0.1: cross_reference(yin, yang) # 角度三阴阳互看 # 阶段四归档更新 archive.add(yin, yang) update_scale_factor(gen) # 小波尺度随迭代衰减参数设定上我一开始踩了些坑这里先给一份比较稳的初始值。P是单次采样个数低维问题取2到3高维问题取4到5再多算力消耗会明显增加但收益不明显。( L )学习间隔建议5到20之间我的经验是Rastrigin这类多峰函数倾向于小( L )让精英解更频繁地带着大家往好区域跑Sphere这类平滑函数大( L )更稳。( \lambda )学习率初始取0.5后期衰减到0.1以下主要是防止后期还大步往精英解方向冲导致在最优点附近来回跳跃。小波尺度( a )初始值我是按照搜索空间宽度的1/10来设的再随迭代次数线性衰减到初始值的1/50。直接设太大会导致小波变异幅度覆盖全空间失去“围绕精英解精修”的意义设得太小又会让变异幅度缩成一个点直接退化成精英解的复制粘贴。5. 实验设计与结果解析5.1 测试环境、基准函数与对比设定为了验证这套改进确实有效我做了两轮实验。第一轮目的是确认机制本身第二轮目的是跟原版算法和两个主流算法做对照。跑测环境就是普通笔记本Python实现每个算法独立跑30次取平均避免单次运气影响结论。基准函数选了五个经典函数Sphere单峰平滑、Rosenbrock单峰但变量强耦合、Rastrigin强多峰、Griewank多峰且维度间有微弱关联、Ackley多峰且外层平坦、中心陡峭。这些函数覆盖了从“好搜”到“难搜”的典型地形具体长相如下表。函数名类型变量范围理论最优主要难点Sphere单峰平滑[-100, 100]0维数高时收敛速度慢Rosenbrock单峰山谷[-5, 10]0变量强耦合山谷狭窄Rastrigin强多峰[-5.12, 5.12]0局部极值极多易早熟Griewank多峰弱关联[-600, 600]0搜索范围大全局结构复杂Ackley多峰平坦底[-32, 32]0中心陡峭外围平坦误导性强对比对象是原始YYPO、标准粒子群算法PSO和差分进化DE。每种算法最大评估次数统一限定在5万次维度分别测试30维和50维两档。强调一点限制评估次数而不是迭代次数是因为对实际工程问题来说目标函数评估才是最贵的操作迭代次数其实无所谓。5.2 收敛精度与稳定性实测观察实验结果可以分为三组来谈。第一组是Sphere和Ackley这类全局结构比较清晰、但收敛精度要求高的函数。加了小波精英解学习之后后期收敛精度提升非常明显尤其Sphere函数50维下最终平均值从原版YYPO的10的负3次方量级直接掉到10的负6次方量级。原因是后期半径已经缩得很小小波学习阶段的精细扰动比原始随机采样更“懂得”贴着精英解周围找缝隙。第二组是Rastrigin和Griewank这类多峰陷阱多的函数。原版YYPO在Rastrigin上几乎稳定陷入局部极值30次运行里只有三五次能找到接近全局最优的区域。加入多角度搜索的最优引导角后跳出局部极值的概率明显上升最终平均值能到10的负1次方量级虽然和DE的最终精度还有差距但已经远超原版。这个提升来自Lévy飞行的重尾步长——偶尔跳出一大截正好能越过一个局部峰顶这是小步长随机搜索做不到的。第三组是Rosenbrock。这函数很有意思它是单峰的但那个山谷又长又窄且带弯曲方向稍有偏差就会一路滑到坡底。多角度搜索里的坐标轮换角在低维时表现不错但50维下反而收益不大我的判断是维度一高每轮只调一个维度、其他维度不动相当于在54度坡上只往前挪一只脚身体早晚要失控。必须配合全局搜索来缓解维度间耦合这也说明没有万能机制多角度里的每个角度都是有适用边界的。整体稳定性方面改进版最直观的变化是30次独立运行的结果方差大幅缩小。原版YYPO有时候能找到好解有时候差得一塌糊涂方差极大而加了精英解学习后因为每个主解都有稳定的“学习标杆”算法的下限被明显抬高了差结果出现的概率降低了很多。做工程优化的时候算法的“下限”往往比“上限”更关键毕竟你不能指望每次跑都赌一次运气。5.3 调参心得与优先级排序调参这几轮下来我摸出的一个规律是参数重要性排序大约是学习间隔L大于学习率lambda大于小波初始尺度大于多角度触发频率。L直接决定了算法有多少比例的时间在“向精英学习”设得太小会让搜索被精英解牵引得太紧多样性崩掉设得太大则精英解信息又被浪费改进等于没做。相比之下lambda的作用更像一个放大器只要不设到离谱的大或小影响相对温和。多角度搜索的三个触发参数里面最优引导角的触发条件——也就是停滞代数阈值——最重要。这个阈值设得太小会频繁执行大跳搜索白白浪费评估次数设得太大又等于没这功能。我最后用的方案是连续15代最优解没有更新就触发一次。Lévy飞行的步长比例也值得调太大了容易直接飞出边界整个候选解直接报废太小了又跳不出局部盆地。小波尺度a的衰减策略我试过线性、指数和按半径比例三种。线性最简单指数衰减前期太猛、后期又没劲按半径比例最灵活但与具体问题相关性强跨问题泛化能力差点。最终选定线性衰减稳定且可解释性强。调参建议就一句话先锁定L再动lambda最后调多角度触发机制不要一口气全调。6. 踩坑实录与常见问题速查表6.1 小波参数导致的越界与崩溃我踩的第一个坑就是小波尺度因子a初始值设得过大导致小波函数在远离精英解的地方仍然有较大幅值变异生成的候选解直接飞到了搜索空间边界之外甚至出现NaN。当时算法跑着跑着突然最优解就变成NaN我一度以为是目标函数出了问题排查了半天才发现是小波变异那边把解推出边界了。这个问题处理起来其实不复杂要么在边界处做回折或截断把越界的维度拉回边界附近要么干脆预先判断小波变异后的候选解是否越界越界就直接抛弃不让它参与评估。我个人更推荐后者因为评估函数很贵你不想把评估预算花在一个明显无效的解上。另外做除法的地方一定要加个极小值判断避免尺度因子衰减到零时产生除零异常。6.2 多角度搜索“叠buff”反而降速第二个典型的坑是把三个搜索角度一股脑全塞进每一轮迭代结果单轮评估次数翻了四倍收敛速度反而更慢。这其实是个非常简单的算术问题——总评估次数是固定的你每轮花的次数多了跑的总代数就少了算法的长期搜索能力就被削弱了。更麻烦的是多个机制同时作用时你根本不知道某个候选解究竟是被哪个机制改善的导致调参时完全抓瞎。所以我的建议是严格执行“分时触发”原则每一轮最多只激活一个附加机制让不同机制在不同的迭代窗口里各司其职。这样每轮的开销可控也方便做实验时单独统计每个机制的贡献度。实测下来把总评估次数花在“更少的轮次、每轮更聚焦的搜索”上比摊大饼式的全机制开启效果好得多。6.3 高维和离散测试下的表现差异第三个值得提醒的点是机制在30维和50维下的表现差异显著。坐标轮换角在低维时收益很高到50维时基本沦为鸡肋甚至拖后腿最优引导角则在50维下价值更大因为局部极值的“势力范围”更大需要更长程的跳跃才能脱困。这提醒我真正做工程应用时多角度搜索里的角度应该根据问题维度动态启用或禁用而不是一套参数打天下。另外一点这套改进是在连续变量优化上测试的如果目标是离散优化比如组合优化里的排班、路径规划问题那就需要额外考虑怎么把连续小波变异映射到离散邻域上。我试过最粗暴的方案——用连续小波生成一个扰动值再按最近整数做取整映射——效果能用但很一般更合理的做法是重新设计离散邻域上的扰动概率这条路值得单独再写一篇这里也只做到点到即止。最后分享一个我实际使用时的习惯我会同时保存原始YYPO和改进版的代码遇到计算昂贵的新问题时先用原始YYPO快速跑一遍估一下问题的粗糙度再决定要不要启动改进版里的套机制。原因很现实不是每个问题都需要复杂机制有些问题你用原始YYPO五分钟就收敛了再套上小波学习和多角度搜索反而是杀鸡用牛刀。算法改进这件事从来不是越复杂越好而是刚刚够用最好。这套融合设计也一样——它是在为那些原始YYPO搞不定的问题兜底而不是要取代所有场景下的简单方案。