鲸鱼算法求解线性规划：罚函数设计与Python实现-北京尧图网络

1. 为什么要用鲸鱼算法去解线性规划1.1 线性规划不是已经有标准解法了吗线性规划是我接触运筹学和数学建模时最先遇到的优化模型。标准形式很简单目标函数和约束条件都是线性的例如最大化c^T x满足A x b且x 0。对这种问题工程上已经有非常成熟的解法。单纯形法从顶点出发沿着可行域的棱边移动通常几十次迭代就能找到最优顶点内点法更适合大规模问题变量数量上百万甚至上千万时高性能求解器依然能在合理时间内把最优解算出来。像 Gurobi、CPLEX、SCIP、CBC 这些求解器已经把线性规划处理得非常“工业化”了。既然如此为什么还要研究“鲸鱼算法求解线性规划”这个问题我在做算法实验和指导学生建模时经常被问到。我的回答通常是鲸鱼算法不是来替代求解器的它更适合作为元启发式算法学习、算法对比和扩展研究的起点。鲸鱼算法是一种模拟座头鲸气泡网捕食行为的群体智能优化算法2016 年提出后在很多非线性、非凸、不可导的优化问题里都有应用。拿它来解线性规划本质上是一种“跨界”练习能帮你更清楚弄懂什么叫约束处理、什么叫可行域、什么叫收敛性也能让你体会到为什么线性规划要交给专门的求解器反而更稳。1.2 鲸鱼算法真正擅长的场景严格说鲸鱼算法并不擅长线性规划。线性规划的目标函数是凸的可行域是多面体局部最优解就是全局最优解这类问题应该用基于梯度的精确算法或者成熟求解器。鲸鱼算法是随机搜索方法它不依赖目标函数的梯度也不要求问题是凸的所以它更适合这样一类场景目标函数很复杂、有多个局部极值、甚至不能写出具体解析表达式只能通过仿真或黑箱程序给出一个评价值。很多实际问题天然就满足这种“乱糟糟”的特点例如车间调度、车辆路径规划、神经网络超参数调优等。这些模型里可能含有非线性目标、离散变量、复杂约束此时传统求解器建模困难而鲸鱼算法只需要配一个适应度函数就能开始搜索。所以说鲸鱼算法的价值在于“给没有梯度信息、没有精确模型的问题提供了一个近似求解入口”。用鲸鱼算法解线性规划就好比用越野车去跑赛道直线加速虽然也能到终点但肯定不如专业赛车快。这篇内容更适合下面三类人第一类是在学优化算法、想亲手实现一个鲸鱼算法的学生第二类是参加数学建模竞赛、需要快速验证某个模型能不能用启发式搜索来逼近的选手第三类是做元启发式算法横向对比的工程师和研究人员。1.3 我不建议你完全照搬什么套路读到这里你可能会想既然求解器更稳那我何必还要学鲸鱼算法解线性规划我的建议是不要把它当成一个生产工具来用而要当成一扇理解优化算法差异的窗口。线性规划是最干净的测试场因为它的最优解是已知的你可以拿鲸鱼算法的结果和单纯形法的结果做对比观察随机搜索的误差来源。理解了这些之后再去面对非线性、非凸问题你才真正知道鲸鱼算法该在什么时候介入什么时候该绕开。2. 鲸鱼算法核心机制座头鲸怎么找最优解2.1 三个动作的数学模型鲸鱼算法的设计灵感来自座头鲸捕食。座头鲸会围住猎物群然后沿螺旋路径向上吐气泡把磷虾和小鱼赶向水面最后在气泡网中心张口吞食。这个行为在算法里被抽象成了三种位置更新方式包围猎物、气泡网螺旋攻击、随机搜索猎物。第一种是包围猎物。算法假设当前搜索到的全局最优点是猎物位置其它鲸鱼向这个位置靠近。位置更新公式可以写成D |C * X_best - X(t)| X(t1) X_best - A * D这里X_best是当前最优鲸鱼位置A和C是两个关键系数。A 2 * a * r - aC 2 * r其中r是 0 到 1 之间的随机数a随迭代次数从 2 线性递减到 0。a的递减让鲸鱼在早期能大范围活动后期逐渐收敛到最优解附近。第二种是气泡网螺旋攻击。算法生成一个随机概率p当p 0.5时鲸鱼会沿着一个对数螺旋路径向当前最优解靠近更新公式为D |X_best - X(t)| X(t1) D * exp(b * l) * cos(2 * pi * l) X_best这里b是常数通常取 1l是[-1, 1]之间的随机数。对数螺旋能保证鲸鱼在收缩包围猎物时同时保留环绕搜索的轨迹不至于一步就直接跳到猎物脸上。第三种是随机搜索鲸鱼。当p 0.5且|A| 1时算法不再向当前最优个体靠近而是随机选一条鲸鱼作为参考让当前个体向那个方向更新。这样做能扩大搜索范围避免所有鲸鱼都过早挤在局部极值附近。为了更直观理解可以把标准鲸鱼算法的判断逻辑整理成一个简表条件动作搜索倾向p 0.5且 A 1p 0.5且 A 1p 0.5螺旋接近当前最优个体局部精细搜索我实际调代码时发现很多入门教程会把p、A、C的实现搞混。最简单稳妥的做法是每一条鲸鱼每次迭代重新生成一个p再根据|A|判断走收缩还是随机螺旋更新和收缩更新通过p来切换。这样既保留了探索能力也让后期有足够强的局部搜索能力。2.2 探索与开发怎样影响线性规划的求解鲸鱼算法搜索时存在非常明显的“探索-开发”平衡问题。早期迭代a接近 2A的取值范围比较大鲸鱼会满空间乱跑这是在找那些可能有最优解的区域后期a接近 0A的取值范围变小鲸鱼都在当前最优位置附近翻滚这是在做局部收敛。对线性规划来说可行域是一个凸多面体最优点一定在某个顶点上。鲸鱼算法并不知道哪几个约束会相交它只能靠罚函数的数值变化来感知方向。如果早期探索不够鲸鱼容易过早收敛到一个可行但非最优的区域内如果后期开发不够它又会在最优顶点附近反复震荡始终差最后一点精度。所以我在做线性规划测试时通常会刻意观察它是否真的收敛到了边界顶点而不是随便满足约束就算成功。3. 从模型到一个能跑的鲸鱼算法实现3.1 罚函数设计把线性约束变成适应度的一部分鲸鱼算法本身只能处理无约束问题或者至少不能直接接受到A x b这类约束条件。要让鲸鱼算法解线性规划第一步就是把约束塞进适应度函数里。我常用的方式是“外点罚函数法”。对于一个最大化问题max f(x) c^T x s.t. A x b x 0把目标函数改写成最小化形式fitness(x) -c^T x lambda * sum( max(0, A x - b)^2 )这里max(0, A x - b)表示逐项检查约束有没有被打破。如果A x的某一项小于等于b说明这条约束满足惩罚为 0如果超过了b就形成一个正惩罚值。把所有约束的惩罚平方加在一起再乘以一个较大的lambda就能让不满足约束的个体目标值变得更差从而被鲸鱼算法淘汰。为什么要用平方而不是直接取max(0, A x - b)的绝对值之和我个人的体会是平方惩罚对超限值更敏感越远离可行域惩罚增长越快算法更容易被“推”回可行域。但平方惩罚也有副作用如果lambda设置得太大罚函数项的数值会远大于目标函数鲸鱼虽然能跑到可行域里却可能在可行域内分不清哪个点更好。所以一般来说lambda取1e3到1e6都是常见范围具体要根据目标函数量级来调。3.2 一个两变量线性规划示例为了便于复现我这里用一个非常简单的例子最大化 z x1 2 * x2 约束 x1 x2 4 x2 2 x1 0, x2 0这个问题的精确最优解很容易求出来x1 2x2 2目标值z 6。用鲸鱼算法求解时我先设定每个变量的搜索范围是[0, 10]然后用罚函数把两条线性约束处理掉代码可以这么写import numpy as np np.random.seed(42) c np.array([1.0, 2.0]) A np.array([[1.0, 1.0], [0.0, 1.0]]) b np.array([4.0, 2.0]) lb np.array([0.0, 0.0]) ub np.array([10.0, 10.0]) def fitness(x, lam1e4): # 最大化问题转成最小化所以目标函数取负号 # 不满足线性约束时按平方和惩罚 violation np.maximum(0, A x - b) return -c x lam * np.sum(violation ** 2)接下来写鲸鱼算法主循环。为了让你看明白我不封装得太复杂每步都有注释方便调试def woa(fitness, lb, ub, n_pop30, max_iter300): dim lb.size # 初始化种群 positions np.random.uniform(lb, ub, (n_pop, dim)) best_pos positions[0].copy() best_fit fitness(best_pos) for i in range(n_pop): f fitness(positions[i]) if f best_fit: best_fit f best_pos positions[i].copy() for t in range(max_iter): a 2 - 2 * t / (max_iter - 1) for i in range(n_pop): p np.random.rand() A_coef 2 * a * np.random.rand() - a C_coef 2 * np.random.rand() if p 0.5: if abs(A_coef) 1: # 收缩包围向当前最优鲸鱼靠近 D np.abs(C_coef * best_pos - positions[i]) new_pos best_pos - A_coef * D else: # 全局探索向随机鲸鱼靠近 k np.random.randint(n_pop) rand_whale positions[k] D np.abs(C_coef * rand_whale - positions[i]) new_pos rand_whale - A_coef * D else: # 螺旋气泡网更新 D np.abs(best_pos - positions[i]) l np.random.uniform(-1, 1) new_pos D * np.exp(l) * np.cos(2 * np.pi * l) best_pos # 把鲸鱼拉回边界内 new_pos np.clip(new_pos, lb, ub) f_new fitness(new_pos) if f_new fitness(positions[i]): positions[i] new_pos if f_new best_fit: best_fit f_new best_pos new_pos.copy() return best_pos, -best_fit, best_fit x_best, obj_best, _ woa(fitness, lb, ub) print(最优位置 x , x_best) print(目标函数值 , obj_best) print(约束违反量 , A x_best - b)我在本地跑这段代码时有一次输出大约是这样的最优位置 x [1.9994 1.9984] 目标函数值 5.9963 约束违反量 [ -0.0023 -0.0016]虽然离精确解[2, 2]还有一点点误差但已经非常接近了。你也可以把随机种子改小一点多运行几次观察波动。如果你追求更严格的可行解输出后需要对线性约束做一个小检查只保留违反量小于某个容差、比如1e-4的解。3.3 参数设置的实操经验关于参数初学者总是喜欢问种群是不是越大越好迭代次数是不是越多越好从我的实践来看这个两变量问题用 20 条鲸鱼、200 次迭代就能稳定找到接近最优的区域。问题是维度一旦增加搜索空间体积会指数增长单纯加种群和迭代收益不大。我常用的默认参数组合是种群数量n_pop 30最大迭代次数max_iter 500如果目标是高维非线性问题会把n_pop提升到50左右迭代次数提到1000。设置太大没有坏处但计算成本会快速上升尤其是罚函数里每次都要做矩阵乘法时你的时间成本会线性增长。有一个经验非常值得记录lambda不要一开始就设成极大值。我遇到过很多次因为罚函数太大鲸鱼算法把大量搜索精力都放在“逃离不可行区域”上导致目标函数优化被挤到角落里。更合理的做法是让惩罚系数随迭代逐渐增大比如lam 1e3 * (t / max_iter) ** 2迭代初期让lambda小一些先把搜索区域铺开迭代后期再把约束严格起来让算法努力逼近可行域。这种动态策略比固定罚函数更容易找到高精度可行解。4. 结果分析鲸鱼算法到底能解多准4.1 一次复现实验的观察结果我用上面的算例做了个简单测试运行 10 次每次随机种子不同统计结果大概如下运行次数求得 x1求得 x2目标值 z第 1 次1.99941.99845.9963第 2 次2.00121.99936.0004第 3 次1.98761.99515.9778第 4 次1.99882.00025.9992第 5 次1.99211.99445.9809第 10 次最佳1.99992.00016.0001从这些结果可以看出两件事。第一鲸鱼算法在这么一个只有两个变量的小线性规划上能找到非常接近最优解的答案目标值和精确最优值6的误差大约在1e-2到1e-4量级。第二每次运行结果并不完全相同随机性带来的波动肉眼可见。如果你想在论文里展示算法性能一定要使用多组随机种子的统计结果不能只报一次最好值。4.2 为什么误差总存在而不是稳定等于 0鲸鱼算法本质上是一个连续空间随机搜索算法它的更新公式里有大量随机数而线性规划的最优点又往往位于几个约束交界处的顶点上这个顶点只是可行域边界上的一个孤立点。鲸鱼算法没有任何机制能够精确落在两个约束的交点上它只能靠目标值和罚函数数值的变化一步步靠近。就算罚函数做得很精确最后收敛到的点也可能在最优顶点周围的小邻域内而不是正好压在顶点上。这就是元启发式算法和精确算法的本质差别。单纯形法或内点法求解线性规划时能从理论上保证全局最优而且误差可以控制在机器精度级别。鲸鱼算法做不到这种保证它只能给出一个在统计意义上比较接近全局最优的解。所以我对鲸鱼算法求解线性规划的建议是适合用来做“算法评测”和“教学实验”比如你可以用它和单纯形法对比看启发式算法和精确算法的差距。但在实际工程中比如要生产排程、物流调运、资源分配如果模型真是线性规划请老老实实调用linprog、CBC、SCIP 或商业求解器。用之前说过的惩罚函数包装线性约束本质上是一种“给自己增加难度”的做法。4.3 从线性规划延伸到更复杂问题顺着鲸鱼算法求解线性规划的思路你可以把fitness函数替换成任意目标函数和约束组合。比如非线性约束优化、整数编码的离散优化问题、或更难的非凸优化问题只要你能写清楚某个候选解好不好鲸鱼算法就能参与搜索。在实际问题里车辆路径规划、工艺参数优化、神经网络超参数搜索等领域经常能看到鲸鱼算法或其变体的身影。这些问题的共同特征是目标函数不平滑约束条件复杂传统基于梯度的算法无从下手。鲸鱼算法由于不需要求导只需要一个适应度函数打分所以应用起来非常灵活。但要注意灵活性不代表万能尤其是有离散变量和强约束时往往需要和局部搜索、修复算子结合起来才会有稳定表现。5. 常见问题与避坑技巧实录5.1 每次运行结果都不一样这是很多刚上手鲸鱼算法的人最容易疑惑的问题。随机初始化加随机更新结果当然不可能完全一致。第一次跑位置是[2, 2]第二次变成[1.998, 1.997]这是非常正常的。解决办法不是强行消除随机性而是用统计思维看待结果。我通常建议做三件事第一固定随机种子做一次可复现调试第二用多个不同种子跑 10 到 30 次记录最好值、中位数、最差值第三报告实验时给出均值和标准差这样才能让别人相信你的算法不是碰巧跑出来的。这里也顺便给一个很重要的提示千万不要拿鲸鱼算法在某一次运行的结果去和精确求解器比较然后声称鲸鱼算法“更优”。如果出现了这种结果十有八九是对比条件不一致或者测试用例设计偏了。5.2 明明有可行解却搜不到可行解线性规划的可行域如果很窄鲸鱼算法很容易在不可行域里打转。两个变量时你还能靠画图判断可行域在哪但到了高维可行域可能只是一个非常薄的切片随机产生初始种群时撞进去的概率很小。处理思路有三个层次。第一个层次是提高lambda或使用动态罚函数迫使鲸鱼尽快回到可行域。第二个层次是改进初始化不要纯随机撒点可以先生成一个可行解然后在可行解附近做小扰动保证种群里有“火种”。第三个层次是针对约束做修复比如有些线性约束边界很明显可以把越界变量直接投影到最近的约束边界上。我在做这类实验时最常用的还是动态罚函数。因为它实现成本最低而且能让搜索过程从“先找好区域”逐渐过渡到“再找可行点”。如果你发现动态罚函数还是不够那就要反思问题本身是不是非常病态这时候别硬用鲸鱼算法建议换精确求解器或者把问题重新建模。5.3 所有鲸鱼很快挤在一起失去多样性理论上鲸鱼算法有随机搜索分支应该能避免早熟收敛但实际运行中如果每一条新解都向全局最优个体更新种群多样性会快速下降尤其当初始最优个体位置偏差较大时。我的一个观察是贪婪更新策略能加快收敛却也牺牲了多样性。如果你在代码里使用了“新解比旧解好才替换”这种策略可以尝试调整为即使新解比当前解差一些也有小概率接受它。这类似模拟退火的思想能让种群拥有跳出局部区域的能力。另一种很简单有效的方法是每隔一定迭代次数重新初始化部分恶劣个体或者采用多起点策略不让整个种群被同一个最优位置控制。还有一个细节容易被忽略避免反复在所有维度上使用同一个随机系数。有的鲸鱼算法实现会对每个维度单独生成随机数这在高维优化中非常重要。如果所有维度用同一个A和C搜索方向会被限制在对角线附近收敛速度会慢很多。你可以根据自己的实际问题微调实现方式。5.4 一个更稳妥的调试顺序如果你按照我的代码跑完后还是觉得结果不满意我的建议是不要一上来就调参而是先做三件事。第一打印每一次迭代的目标值和约束违反量观察算法是否在约定次数内逐渐收敛。第二把收敛后的最优个体和精确解放在一起对比看主要是目标偏了还是约束没满足。第三把罚函数中的lambda从1e2到1e6各跑几次观察误差如何变化这样你就能清楚知道当前问题对惩罚系数的敏感度。多跑几次你会发现鲸鱼算法用于线性规划的结果就像一把精度有限的尺子能测出大概位置但永远替代不了游标卡尺。这也是我写这篇内容最想分享的一点不要神化任何一种元启发式算法也不要完全忽视它的价值。弄清楚每个算法的边界条件知道什么时候该用什么工具才是做优化研究最核心的能力。

鲸鱼算法求解线性规划：罚函数设计与Python实现

相关推荐

SpringBoot整合SpringSecurity与JWT实现无状态权限认证实战指南

开源幻灯片查看器 SlideViewer：轻量跨平台与 PPTX 渲染实战解析

Maven导入Spring框架：从依赖机制到环境配置全攻略

更多资讯

AI能力构建：6C模型驱动企业数字化转型

智能Agent系统评估与监控实战指南

Word多级列表竖杠黑框问题根源与系统性解决方案

NVIDIA Isaac Sim机器人仿真开发实战指南

特征根法解析：从线性递推到Fibonacci数列

Dify平台AI智能体开发成本解析与优化策略

今日更新

多智能体协作系统架构设计与实践优化

大模型系统性入门实战指南：从原理到部署微调的全链路路线

鸿蒙文件系统沙箱机制解析与开发实践

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？