XiaoMaColtAI/math-modeling-skill / dsh-plugin/math-modeling-agent/skills/math-modeling
math-modeling
Verified当用户要求数学建模、建模竞赛、建模分析、代码求解、结果可视化或生成数学建模论文时使用。支持完整三阶段流程、单独执行任一角色,以及在关键节点使用独立 Subagent 进行阶段内质检;默认只启用质检 Subagent,用户可明确选择额外协作。
| File | Kind | Size |
|---|---|---|
| SKILL.md | skill md | 10.5 KB |
| assets/01-优化算法说明.md | markdown | 79.1 KB |
| assets/02-预测类算法说明.md | markdown | 67.4 KB |
| assets/03-评价类算法说明.md | markdown | 81.6 KB |
| assets/04-图论与网络分析算法说明.md | markdown | 38.8 KB |
| assets/05-统计分析与数据处理算法说明.md | markdown | 60.7 KB |
| assets/06-综合类算法说明.md | markdown | 35.6 KB |
| assets/07-机器学习算法说明.md | markdown | 51.9 KB |
| assets/README.md | markdown | 9.1 KB |
| references/README.md | markdown | 2.1 KB |
| references/Subagent调度.md | markdown | 7.4 KB |
| references/交付与截止时间协议.md | markdown | 4.4 KB |
| references/算法索引.md | markdown | 1021 B |
| 使用指南.md | markdown | 3.4 KB |
assets/01-优化算法说明.md
View on GitHub# 优化算法说明文档
## 概述
优化算法是数学建模中最常用的算法类型之一,用于求解在约束条件下使目标函数达到最优(最大或最小)的决策变量值。优化问题广泛存在于生产调度、资源分配、路径规划、参数优化等领域。
---
## 1. 线性规划 (Linear Programming, LP)
### 算法介绍
线性规划是一种数学方法,用于在满足线性约束条件下,求取线性目标函数的最大值或最小值。其标准形式为:
**目标函数**:
$$
\min Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n
$$
**约束条件**:
$$
\begin{cases}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \\
\vdots \\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m \\
x_i \geq 0, \quad i=1,2,\ldots,n
\end{cases}
$$
**求解方法**:单纯形法、内点法
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 资源分配 | 生产计划、物资调配 | 线性目标函数 + 线性约束 |
| 运输问题 | 物资运输、最小费用流 | 供需平衡约束 |
| 指派问题 | 任务分配、人员安排 | 0-1变量约束 |
| 配料问题 | 饲料配方、化学混合 | 比例约束 |
### 可视化图表类型
- **可行域图**:二维问题的约束区域可视化
- **等值线图**:目标函数等值线与可行域关系
- **灵敏度分析图**:参数变化对最优解的影响
- **单纯形表**:单纯形法迭代过程表格
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Linear Programming and Extensions | George Dantzig | 1963 | Princeton University Press |
| Interior-point polynomial algorithms in convex programming | Nesterov & Nemirovski | 2002 | SIAM |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import linprog
import warnings
warnings.filterwarnings('ignore')
# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
def solve_linear_programming():
"""
线性规划求解示例:生产计划优化
目标:最大化利润 = x1 + 2*x2
约束:2*x1 + x2 <= 10 (资源A)
x1 + 3*x2 <= 15 (资源B)
x1, x2 >= 0
"""
# 目标函数系数(scipy默认求最小值,所以取负号求最大值)
c = [-1, -2]
# 不等式约束:A_ub @ x <= b_ub
A_ub = [[2, 1], [1, 3]]
b_ub = [10, 15]
# 变量边界
bounds = [(0, None), (0, None)]
# 求解
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
if result.success:
x1_opt, x2_opt = result.x
max_profit = -result.fun
print(f"最优解:x1 = {x1_opt:.4f}, x2 = {x2_opt:.4f}")
print(f"最大利润:{max_profit:.4f}")
return x1_opt, x2_opt, max_profit, A_ub, b_ub
else:
print("求解失败:", result.message)
return None
def visualize_lp_solution(x1_opt, x2_opt, max_profit, A_ub, b_ub):
"""可视化线性规划的可行域和最优解"""
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
# 图1:可行域和最优解
ax1 = axes[0]
x1 = np.linspace(0, 8, 400)
# 约束线:2*x1 + x2 = 10 -> x2 = 10 - 2*x1
x2_const1 = np.maximum(0, 10 - 2*x1)
# 约束线:x1 + 3*x2 = 15 -> x2 = (15 - x1)/3
x2_const2 = np.maximum(0, (15 - x1)/3)
# 可行域边界(取最小值)
x2_boundary = np.minimum(x2_const1, x2_const2)
x2_boundary = np.maximum(x2_boundary, 0)
# 填充可行域
ax1.fill_between(x1, 0, x2_boundary, where=(x2_boundary >= 0),
alpha=0.3, color='blue', label='可行域')
# 绘制约束线
ax1.plot(x1, x2_const1, 'r-', linewidth=2, label='2x₁ + x₂ = 10')
ax1.plot(x1, x2_const2, 'g-', linewidth=2, label='x₁ + 3x₂ = 15')
# 绘制等利润线
for profit in [5, 10, max_profit]:
x2_profit = np.maximum(0, (profit - x1) / 2)
ax1.plot(x1, x2_profit, '--', alpha=0.7, label=f'利润 = {profit}' if profit == max_profit else '')
# 标记最优解
ax1.plot(x1_opt, x2_opt, 'r*', markersize=20, label=f'最优解 ({x1_opt:.2f}, {x2_opt:.2f})')
ax1.set_xlim(0, 8)
ax1.set_ylim(0, 8)
ax1.set_xlabel('x₁ (产品A产量)', fontsize=12)
ax1.set_ylabel('x₂ (产品B产量)', fontsize=12)
ax1.set_title('线性规划可行域与最优解', fontsize=14)
ax1.legend(loc='upper right')
# 图2:单纯形法迭代过程示意图
ax2 = axes[1]
vertices = [(0, 0), (5, 0), (3, 4), (0, 5)]
vertices.append(vertices[0]) # 闭合多边形
xs = [v[0] for v in vertices]
ys = [v[1] for v in vertices]
ax2.plot(xs, ys, 'b-', linewidth=2, marker='o', markersize=8)
# 标记顶点
labels = ['(0,0)', '(5,0)', '(3,4)\n最优解', '(0,5)']
for i, (x, y, label) in enumerate(zip(xs[:-1], ys[:-1], labels)):
ax2.annotate(label, (x, y), textcoords="offset points", xytext=(0, 10), ha='center', fontsize=10)
# 标记最优解
ax2.plot(3, 4, 'r*', markersize=20)
ax2.set_xlim(-0.5, 6)
ax2.set_ylim(-0.5, 6)
ax2.set_xlabel('x₁', fontsize=12)
ax2.set_ylabel('x₂', fontsize=12)
ax2.set_title('可行域顶点(单纯形法搜索路径)', fontsize=14)
ax2.set_aspect('equal')
plt.tight_layout()
plt.savefig('linear_programming_solution.png', dpi=150, bbox_inches='tight')
plt.show()
print("\n图表已保存为 'linear_programming_solution.png'")
# 运行示例
if __name__ == "__main__":
result = solve_linear_programming()
if result:
x1_opt, x2_opt, max_profit, A_ub, b_ub = result
visualize_lp_solution(x1_opt, x2_opt, max_profit, A_ub, b_ub)
```
---
## 2. 整数规划 (Integer Programming, IP)
### 算法介绍
整数规划是线性规划的扩展,要求部分或全部决策变量取整数值。根据变量取值特点分为:
- **纯整数规划**:所有变量均为整数
- **混合整数规划**:部分变量为整数,部分为连续
- **0-1规划**:变量只能取0或1
**求解方法**:分支定界法、割平面法、分支定价法
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 设备选址 | 工厂选址、仓库布局 | 0-1选址变量 |
| 车辆路径 | 配送路线规划 | 逻辑约束 |
| 调度问题 | 作业调度、排班 | 时间离散化 |
| 背包问题 | 资源选择、投资组合 | 0-1选择变量 |
### 可视化图表类型
- **分支树图**:分支定界法搜索过程
- **甘特图**:调度问题的时间安排
- **网络图**:路径问题的可视化
- **解空间图**:整数解与连续解对比
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Integer Programming | Laurence Wolsey | 1998 | Wiley |
| Branch and bound: A survey | Lawler & Wood | 1966 | Operations Research |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from pulp import LpProblem, LpVariable, LpMaximize, LpStatus, value
import warnings
warnings.filterwarnings('ignore')
# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
def solve_knapsack_ip():
"""
0-1背包问题整数规划求解
问题:在重量限制下选择物品使价值最大
"""
# 物品数据
items = ['物品A', '物品B', '物品C', '物品D', '物品E']
weights = [2, 3, 4, 5, 9] # 重量
values = [3, 4, 5, 8, 10] # 价值
capacity = 15 # 背包容量
# 创建问题
prob = LpProblem("0-1背包问题", LpMaximize)
# 创建0-1决策变量
x = [LpVariable(f"x_{i}", cat='Binary') for i in range(len(items))]
# 目标函数:最大化总价值
prob += sum(values[i] * x[i] for i in range(len(items)))
# 约束:总重量不超过容量
prob += sum(weights[i] * x[i] for i in range(len(items))) <= capacity
# 求解
prob.solve()
# 提取结果
selected = [i for i in range(len(items)) if value(x[i]) > 0.5]
total_weight = sum(weights[i] for i in selected)
total_value = sum(values[i] for i in selected)
print("=" * 50)
print("0-1背包问题求解结果")
print("=" * 50)
print(f"选中物品: {[items[i] for i in selected]}")
print(f"总重量: {total_weight}/{capacity}")
print(f"总价值: {total_value}")
print(f"求解状态: {LpStatus[prob.status]}")
return items, weights, values, selected, total_weight, total_value, capacity
def solve_production_planning_ip():
"""
生产计划整数规划:设备选址与生产决策
"""
# 工厂数据
factories = ['工厂1', '工厂2', '工厂3']
setup_costs = [100, 150, 120] # 开设成本
unit_costs = [10, 8, 12] # 单位生产成本
capacities = [500, 600, 400] # 产能
demand = 800 # 总需求
prob = LpProblem("生产计划", LpMinimize)
# 决策变量
y = [LpVariable(f"y_{i}", cat='Binary') for i in range(len(factories))] # 是否开设
x = [LpVariable(f"x_{i}", lowBound=0, cat='Integer') for i in range(len(factories))] # 产量
# 目标函数:最小化总成本
prob += sum(setup_costs[i] * y[i] + unit_costs[i] * x[i] for i in range(len(factories)))
# 约束1:满足需求
prob += sum(x[i] for i in range(len(factories))) >= demand
# 约束2:产能限制(只有开设的工厂才能生产)
for i in range(len(factories)):
prob += x[i] <= capacities[i] * y[i]
prob.solve()
print("\n" + "=" * 50)
print("生产计划整数规划求解结果")
print("=" * 50)
for i in range(len(factories)):
if value(y[i]) > 0.5:
print(f"{factories[i]}: 开设,生产 {value(x[i]):.0f} 单位")
else:
print(f"{factories[i]}: 不开设")
total_cost = value(prob.objective)
print(f"总成本: {total_cost:.2f}")
return factories, setup_costs, unit_costs, capacities, demand
def visualize_knapsack_solution(items, weights, values, selected, total_weight, total_value, capacity):
"""可视化背包问题解决方案"""
fig, axes = plt.subplots(2, 2, figsize=(14, 10))
# 图1:物品价值重量比
ax1 = axes[0, 0]
ratios = [v/w for v, w in zip(values, weights)]
colors = ['green' if i in selected else 'gray' for i in range(len(items))]
bars = ax1.bar(items, ratios, color=colors, edgecolor='black', alpha=0.7)
ax1.set_ylabel('价值/重量比', fontsize=12)
ax1.set_title('物品性价比分析(绿色=选中)', fontsize=14)
# 在柱子上标注数值
for bar, ratio in zip(bars, ratios):
height = bar.get_height()
ax1.text(bar.get_x() + bar.get_width()/2., height,
f'{ratio:.2f}', ha='center', va='bottom', fontsize=10)
# 图2:重量和价值对比
ax2 = axes[0, 1]
x_pos = np.arange(len(items))
width = 0.35
bars1 = ax2.bar(x_pos - width/2, weights, width, label='重量', color='skyblue', edgecolor='black')
bars2 = ax2.bar(x_pos + width/2, values, width, label='价值', color='lightcoral', edgecolor='black')
ax2.set_xlabel('物品', fontsize=12)
ax2.set_ylabel('数值', fontsize=12)
ax2.set_title('物品重量与价值对比', fontsize=14)
ax2.set_xticks(x_pos)
ax2.set_xticklabels(items)
ax2.legend()
# 高亮选中的物品
for i in selected:
bars1[i].set_color('darkblue')
bars2[i].set_color('darkred')
# 图3:背包容量使用
ax3 = axes[1, 0]
usage_data = [total_weight, capacity - total_weight]
labels = [f'已使用\n{total_weight}', f'剩余\n{capacity - total_weight}']
colors_pie = ['#ff9999', '#66b3ff']
explode = (0.05, 0)
wedges, texts, autotexts = ax3.pie(usage_data, labels=labels, colors=colors_pie,
autopct='%1.1f%%', explode=explode, startangle=90)
ax3.set_title(f'背包容量使用情况(总容量: {capacity})', fontsize=14)
# 图4:选中物品详情
ax4 = axes[1, 1]
selected_items = [items[i] for i in selected]
selected_weights = [weights[i] for i in selected]
selected_values = [values[i] for i in selected]
y_pos = np.arange(len(selected_items))
# 创建堆叠条形图
ax4.barh(y_pos, selected_weights, color='lightblue', label='重量', edgecolor='black')
ax4.barh(y_pos, [v*0.5 for v in selected_values], left=selected_weights,
color='lightgreen', label='价值(缩放)', edgecolor='black')
ax4.set_yticks(y_pos)
ax4.set_yticklabels(selected_items)
ax4.set_xlabel('数值', fontsize=12)
ax4.set_title('选中物品详情', fontsize=14)
ax4.legend()
# 添加总价值和总重量标注
ax4.text(0.95, 0.05, f'总重量: {total_weight}\n总价值: {total_value}',
transform=ax4.transAxes, ha='right', va='bottom',
bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5),
fontsize=11)
plt.tight_layout()
plt.savefig('integer_programming_solution.png', dpi=150, bbox_inches='tight')
plt.show()
print("\n图表已保存为 'integer_programming_solution.png'")
# 运行示例
if __name__ == "__main__":
# 求解背包问题
items, weights, values, selected, total_weight, total_value, capacity = solve_knapsack_ip()
# 求解生产计划问题
solve_production_planning_ip()
# 可视化
visualize_knapsack_solution(items, weights, values, selected, total_weight, total_value, capacity)
```
---
## 3. 动态规划 (Dynamic Programming, DP)
### 算法介绍
动态规划是求解多阶段决策过程最优化的数学方法。其核心思想是将复杂问题分解为重叠子问题,通过保存子问题的解避免重复计算。
**基本要素**:
- **最优子结构**:问题的最优解包含子问题的最优解
- **重叠子问题**:子问题被重复计算
- **边界条件**:问题的初始状态
**状态转移方程**:
$$
dp[i] = \max_{j \in \text{choices}} \{dp[j] + cost(j, i)\}
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 最短路径 | 多阶段路径规划 | 无后效性 |
| 资源分配 | 多阶段投资决策 | 阶段性决策 |
| 背包问题 | 物品装载组合 | 最优子结构 |
| 生产计划 | 多阶段生产调度 | 状态可转移 |
| 设备更新 | 最优更换策略 | 时间阶段划分 |
### 可视化图表类型
- **状态转移图**:各阶段状态之间的关系
- **决策树图**:不同决策路径的可视化
- **阶段图**:多阶段决策的时间轴
- **填表过程图**:DP表填充过程
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Dynamic Programming | Richard Bellman | 1957 | Princeton University Press |
| Optimal Capital Allocation | Merton | 1971 | Journal of Financial Economics |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
import warnings
warnings.filterwarnings('ignore')
# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
def knapsack_dp(weights, values, capacity):
"""
0-1背包问题动态规划求解(带路径记录)
返回:最大价值、DP表、选中物品
"""
n = len(weights)
# DP表:dp[i][w]表示前i个物品,容量为w时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# 记录选择路径
keep = [[False] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
# 比较:不选第i个物品 vs 选第i个物品
not_take = dp[i-1][w]
take = dp[i-1][w-weights[i-1]] + values[i-1]
if take > not_take:
dp[i][w] = take
keep[i][w] = True
else:
dp[i][w] = not_take
else:
dp[i][w] = dp[i-1][w]
# 回溯找出选中的物品
selected = []
w = capacity
for i in range(n, 0, -1):
if keep[i][w]:
selected.append(i-1)
w -= weights[i-1]
return dp[n][capacity], dp, selected[::-1]
def longest_common_subsequence(seq1, seq2):
"""
最长公共子序列(LCS)问题
"""
m, n = len(seq1), len(seq2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if seq1[i-1] == seq2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 回溯找出LCS
lcs = []
i, j = m, n
while i > 0 and j > 0:
if seq1[i-1] == seq2[j-1]:
lcs.append(seq1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(lcs)), dp
def visualize_knapsack_dp(dp, weights, values, capacity, selected):
"""可视化背包问题的DP表和解决方案"""
fig = plt.figure(figsize=(16, 10))
gs = fig.add_gridspec(2, 2, height_ratios=[1, 1])
# 图1:DP表热力图
ax1 = fig.add_subplot(gs[0, :])
dp_array = np.array(dp)
im = ax1.imshow(dp_array, cmap='YlOrRd', aspect='auto')
# 标注数值
for i in range(dp_array.shape[0]):
for j in range(dp_array.shape[1]):
text = ax1.text(j, i, int(dp_array[i, j]),
ha="center", va="center", color="black", fontsize=8)
ax1.set_xlabel('背包容量', fontsize=12)
ax1.set_ylabel('物品数量', fontsize=12)
ax1.set_title('动态规划表(最大价值)', fontsize=14)
plt.colorbar(im, ax=ax1, label='价值')
# 图2:DP过程动画帧(选择路径)
ax2 = fig.add_subplot(gs[1, 0])
# 绘制选中路径
w = capacity
path_points = [(capacity, len(weights))]
for i in range(len(weights), 0, -1):
if i-1 in selected:
path_points.append((w - weights[i-1], i-1))
w -= weights[i-1]
else:
path_points.append((w, i-1))
# 绘制DP网格
ax2.imshow(dp_array, cmap='Blues', alpha=0.3, aspect='auto')
# 绘制路径
for k in range(len(path_points)-1):
x1, y1 = path_points[k]
x2, y2 = path_points[k+1]
ax2.plot([x1, x2], [y1, y2], 'r-', linewidth=3, alpha=0.7)
ax2.plot(x1, y1, 'ro', markersize=10)
ax2.plot(path_points[-1][0], path_points[-1][1], 'go', markersize=12, label='起点')
ax2.set_xlabel('背包容量', fontsize=12)
ax2.set_ylabel('物品数量', fontsize=12)
ax2.set_title('最优解路径(从终点回溯)', fontsize=14)
ax2.legend()
# 图3:物品选择可视化
ax3 = fig.add_subplot(gs[1, 1])
n = len(weights)
y_pos = np.arange(n)
# 绘制所有物品
colors = ['green' if i in selected else 'lightgray' for i in range(n)]
bars = ax3.barh(y_pos, weights, color=colors, edgecolor='black', alpha=0.8)
# 添加标签
for i, (w, v) in enumerate(zip(weights, values)):
label = f'重量:{w}, 价值:{v}'
if i in selected:
label += ' ✓'
ax3.text(w + 0.3, i, label, va='center', fontsize=10)
ax3.set_yticks(y_pos)
ax3.set_yticklabels([f'物品{i+1}' for i in range(n)])
ax3.set_xlabel('重量', fontsize=12)
ax3.set_title(f'物品选择结果(总容量:{capacity})', fontsize=14)
ax3.axvline(x=capacity, color='r', linestyle='--', label='容量限制')
ax3.legend()
plt.tight_layout()
plt.savefig('dynamic_programming_solution.png', dpi=150, bbox_inches='tight')
plt.show()
print("\n图表已保存为 'dynamic_programming_solution.png'")
def visualize_lcs_dp(dp, seq1, seq2, lcs):
"""可视化LCS的DP表"""
fig, ax = plt.subplots(figsize=(12, 10))
dp_array = np.array(dp)
im = ax.imshow(dp_array, cmap='Greens', aspect='auto')
# 标注数值和字符匹配
for i in range(dp_array.shape[0]):
for j in range(dp_array.shape[1]):
if i > 0 and j > 0 and seq1[i-1] == seq2[j-1]:
color = 'red'
weight = 'bold'
else:
color = 'black'
weight = 'normal'
text = ax.text(j, i, int(dp_array[i, j]),
ha="center", va="center", color=color,
fontsize=10, fontweight=weight)
# 设置刻度标签
ax.set_xticks(range(len(seq2) + 1))
ax.set_yticks(range(len(seq1) + 1))
ax.set_xticklabels([''] + list(seq2))
ax.set_yticklabels([''] + list(seq1))
ax.set_xlabel(f'序列2: {seq2}', fontsize=12)
ax.set_ylabel(f'序列1: {seq1}', fontsize=12)
ax.set_title(f'最长公共子序列DP表(LCS: {lcs})', fontsize=14)
plt.colorbar(im, ax=ax, label='LCS长度')
plt.tight_layout()
plt.savefig('lcs_dp_table.png', dpi=150, bbox_inches='tight')
plt.show()
print("LCS图表已保存为 'lcs_dp_table.png'")
# 运行示例
if __name__ == "__main__":
print("=" * 60)
print("动态规划算法示例")
print("=" * 60)
# 示例1:0-1背包问题
print("\n【示例1】0-1背包问题")
items = ['A', 'B', 'C', 'D', 'E']
weights = [2, 3, 4, 5, 9]
values = [3, 4, 5, 8, 10]
capacity = 15
max_value, dp_table, selected = knapsack_dp(weights, values, capacity)
print(f"物品: {items}")
print(f"重量: {weights}")
print(f"价值: {values}")
print(f"背包容量: {capacity}")
print(f"最大价值: {max_value}")
print(f"选中物品: {[items[i] for i in selected]}")
visualize_knapsack_dp(dp_table, weights, values, capacity, selected)
# 示例2:最长公共子序列
print("\n【示例2】最长公共子序列")
seq1 = "ABCDGH"
seq2 = "AEDFHR"
lcs, lcs_dp = longest_common_subsequence(seq1, seq2)
print(f"序列1: {seq1}")
print(f"序列2: {seq2}")
print(f"最长公共子序列: {lcs}")
print(f"LCS长度: {len(lcs)}")
visualize_lcs_dp(lcs_dp, seq1, seq2, lcs)
```
---
## 4. 遗传算法 (Genetic Algorithm, GA)
### 算法介绍
遗传算法是一种模拟自然进化过程的全局优化算法。通过选择、交叉、变异等操作,在解空间中搜索最优解。
**基本步骤**:
1. **初始化**:生成初始种群
2. **适应度评估**:计算每个个体的适应度值
3. **选择**:根据适应度选择父代个体
4. **交叉**:父代个体交叉产生子代
5. **变异**:子代个体发生随机变异
6. **终止判断**:满足终止条件则输出结果
**参数设置**:
- 种群大小:50-200
- 交叉概率:0.6-0.9
- 变异概率:0.001-0.1
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 复杂优化 | 多峰函数优化 | 非凸、非线性 |
| 调度问题 | 车间调度、课程表 | 组合优化 |
| 路径规划 | 旅行商问题 | NP-hard |
| 参数优化 | 神经网络参数 | 高维搜索空间 |
### 可视化图表类型
- **收敛曲线**:适应度随代数变化
- **种群分布图**:种群在解空间的分布
- **家族树图**:个体遗传关系
- **参数敏感性图**:参数对性能的影响
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Adaptation in Natural and Artificial Systems | John Holland | 1975 | University of Michigan Press |
| Genetic Algorithms in Search, Optimization | Goldberg | 1989 | Addison-Wesley |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import warnings
warnings.filterwarnings('ignore')
# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
class GeneticAlgorithm:
"""
遗传算法实现(不依赖DEAP,纯NumPy实现)
"""
def __init__(self, pop_size=100, n_generations=200,
crossover_rate=0.8, mutation_rate=0.1,
elitism=2, bounds=(-5, 5)):
self.pop_size = pop_size
self.n_generations = n_generations
self.crossover_rate = crossover_rate
self.mutation_rate = mutation_rate
self.elitism = elitism # 保留的最优个体数
self.bounds = bounds
def objective_function(self, x):
"""
目标函数:Rastrigin函数(多峰函数,用于测试优化算法)
f(x) = 10*n + sum(xi^2 - 10*cos(2*pi*xi))
全局最小值在 x = 0 处,f(0) = 0
"""
n = len(x)
return 10 * n + np.sum(x**2 - 10 * np.cos(2 * np.pi * x))
def initialize_population(self, dim):
"""初始化种群"""
return np.random.uniform(self.bounds[0], self.bounds[1],
(self.pop_size, dim))
def evaluate_fitness(self, population):
"""评估适应度(目标函数值越小,适应度越高)"""
fitness = np.array([self.objective_function(ind) for ind in population])
return fitness
def selection(self, population, fitness):
"""锦标赛选择"""
selected = []
tournament_size = 3
for _ in range(self.pop_size):
# 随机选择tournament_size个个体
tournament_idx = np.random.choice(self.pop_size, tournament_size, replace=False)
tournament_fitness = fitness[tournament_idx]
# 选择适应度最好的(目标函数值最小的)
winner_idx = tournament_idx[np.argmin(tournament_fitness)]
selected.append(population[winner_idx].copy())
return np.array(selected)
def crossover(self, parent1, parent2):
"""模拟二进制交叉(SBX)"""
if np.random.rand() > self.crossover_rate:
return parent1.copy(), parent2.copy()
eta = 20 # 分布指数
child1, child2 = parent1.copy(), parent2.copy()
for i in range(len(parent1)):
if np.random.rand() <= 0.5:
if abs(parent1[i] - parent2[i]) > 1e-14:
if parent1[i] < parent2[i]:
y1, y2 = parent1[i], parent2[i]
else:
y1, y2 = parent2[i], parent1[i]
beta = 1.0 + (2.0 * (y1 - self.bounds[0]) / (y2 - y1))
alpha = 2.0 - beta ** (-(eta + 1))
rand = np.random.rand()
if rand <= 1.0 / alpha:
beta_q = (rand * alpha) ** (1.0 / (eta + 1))
else:
beta_q = (1.0 / (2.0 - rand * alpha)) ** (1.0 / (eta + 1))
c1 = 0.5 * ((y1 + y2) - beta_q * (y2 - y1))
beta = 1.0 + (2.0 * (self.bounds[1] - y2) / (y2 - y1))
alpha = 2.0 - beta ** (-(eta + 1))
if rand <= 1.0 / alpha:
beta_q = (rand * alpha) ** (1.0 / (eta + 1))
else:
beta_q = (1.0 / (2.0 - rand * alpha)) ** (1.0 / (eta + 1))
c2 = 0.5 * ((y1 + y2) + beta_q * (y2 - y1))
child1[i] = np.clip(c1, self.bounds[0], self.bounds[1])
child2[i] = np.clip(c2, self.bounds[0], self.bounds[1])
return child1, child2
def mutate(self, individual):
"""多项式变异"""
eta_m = 20 # 变异分布指数
for i in range(len(individual)):
if np.random.rand() <= self.mutation_rate:
y = individual[i]
delta1 = (y - self.bounds[0]) / (self.bounds[1] - self.bounds[0])
delta2 = (self.bounds[1] - y) / (self.bounds[1] - self.bounds[0])
rand = np.random.rand()
mut_pow = 1.0 / (eta_m + 1.0)
if rand <= 0.5:
xy = 1.0 - delta1
val = 2.0 * rand + (1.0 - 2.0 * rand) * (xy ** (eta_m + 1))
delta_q = val ** mut_pow - 1.0
else:
xy = 1.0 - delta2
val = 2.0 * (1.0 - rand) + 2.0 * (rand - 0.5) * (xy ** (eta_m + 1))
delta_q = 1.0 - val ** mut_pow
individual[i] = y + delta_q * (self.bounds[1] - self.bounds[0])
individual[i] = np.clip(individual[i], self.bounds[0], self.bounds[1])
return individual
def evolve(self, dim=2, verbose=True):
"""
执行遗传算法进化
"""
# 初始化种群
population = self.initialize_population(dim)
# 记录历史
history = {
'best_fitness': [],
'avg_fitness': [],
'best_individual': [],
'population': []
}
for generation in range(self.n_generations):
# 评估适应度
fitness = self.evaluate_fitness(population)
# 记录统计信息
best_idx = np.argmin(fitness)
best_fitness = fitness[best_idx]
avg_fitness = np.mean(fitness)
history['best_fitness'].append(best_fitness)
history['avg_fitness'].append(avg_fitness)
history['best_individual'].append(population[best_idx].copy())
if generation % 10 == 0:
history['population'].append(population.copy())
if verbose and generation % 20 == 0:
print(f"Generation {generation}: Best = {best_fitness:.6f}, Avg = {avg_fitness:.6f}")
# 精英保留
sorted_idx = np.argsort(fitness)
new_population = [population[idx].copy() for idx in sorted_idx[:self.elitism]]
# 选择
selected = self.selection(population, fitness)
# 交叉和变异
offspring = []
for i in range(0, self.pop_size - self.elitism, 2):
parent1 = selected[i]
parent2 = selected[i+1] if i+1 < len(selected) else selected[0]
child1, child2 = self.crossover(parent1, parent2)
child1 = self.mutate(child1)
child2 = self.mutate(child2)
offspring.append(child1)
offspring.append(child2)
# 更新种群
new_population.extend(offspring[:self.pop_size - self.elitism])
population = np.array(new_population)
# 最终评估
final_fitness = self.evaluate_fitness(population)
best_idx = np.argmin(final_fitness)
return population[best_idx], final_fitness[best_idx], history
def visualize_ga_results(ga, history, dim=2):
"""可视化遗传算法结果"""
fig = plt.figure(figsize=(16, 12))
gs = fig.add_gridspec(3, 2, height_ratios=[1, 1, 1])
# 图1:收敛曲线
ax1 = fig.add_subplot(gs[0, :])
generations = range(len(history['best_fitness']))
ax1.semilogy(generations, history['best_fitness'], 'b-', linewidth=2, label='最优适应度')
ax1.semilogy(generations, history['avg_fitness'], 'r--', linewidth=1.5, alpha=0.7, label='平均适应度')
ax1.set_xlabel('迭代次数', fontsize=12)
ax1.set_ylabel('适应度(对数尺度)', fontsize=12)
ax1.set_title('遗传算法收敛曲线', fontsize=14)
ax1.legend()
# 图2:种群分布演化(2D情况)
if dim == 2:
ax2 = fig.add_subplot(gs[1, 0])
# 绘制目标函数的等高线
x = np.linspace(ga.bounds[0], ga.bounds[1], 100)
y = np.linspace(ga.bounds[0], ga.bounds[1], 100)
X, Y = np.meshgrid(x, y)
Z = np.zeros_like(X)
for i in range(X.shape[0]):
for j in range(X.shape[1]):
Z[i, j] = ga.objective_function(np.array([X[i, j], Y[i, j]]))
contour = ax2.contour(X, Y, Z, levels=20, cmap='viridis', alpha=0.5)
ax2.clabel(contour, inline=True, fontsize=8)
# 绘制初始种群
if len(history['population']) > 0:
initial_pop = history['population'][0]
ax2.scatter(initial_pop[:, 0], initial_pop[:, 1],
c='blue', alpha=0.5, s=30, label='初始种群')
# 绘制最终种群
if len(history['population']) > 0:
final_pop = history['population'][-1]
ax2.scatter(final_pop[:, 0], final_pop[:, 1],
c='red', alpha=0.7, s=30, label='最终种群')
# 绘制最优解轨迹
best_path = np.array(history['best_individual'])
ax2.plot(best_path[:, 0], best_path[:, 1], 'g-', linewidth=2, alpha=0.7, label='最优解轨迹')
ax2.scatter(best_path[-1, 0], best_path[-1, 1], c='green', s=200, marker='*',
edgecolors='black', linewidths=2, label='全局最优解', zorder=5)
ax2.set_xlabel('x₁', fontsize=12)
ax2.set_ylabel('x₂', fontsize=12)
ax2.set_title('种群分布与最优解轨迹', fontsize=14)
ax2.legend()
# 图3:适应度分布箱线图
ax3 = fig.add_subplot(gs[1, 1])
sample_generations = [0, len(history['best_fitness'])//4,
len(history['best_fitness'])//2,
3*len(history['best_fitness'])//4,
len(history['best_fitness'])-1]
# 重新计算这些代的适应度分布
fitness_distributions = []
labels = []
for gen in sample_generations:
if gen < len(history['population']):
pop = history['population'][gen // 10] if gen // 10 < len(history['population']) else history['population'][-1]
fitness = [ga.objective_function(ind) for ind in pop]
fitness_distributions.append(fitness)
labels.append(f'Gen {gen}')
if fitness_distributions:
bp = ax3.boxplot(fitness_distributions, labels=labels, patch_artist=True)
for patch in bp['boxes']:
patch.set_facecolor('lightblue')
ax3.set_ylabel('适应度', fontsize=12)
ax3.set_xlabel('代数', fontsize=12)
ax3.set_title('适应度分布演化', fontsize=14)
# 图4:最优解各维度变化
ax4 = fig.add_subplot(gs[2, :])
best_individuals = np.array(history['best_individual'])
for d in range(dim):
ax4.plot(best_individuals[:, d], linewidth=2, label=f'维度 {d+1}')
# 添加理论最优值参考线
ax4.axhline(y=0, color='r', linestyle='--', linewidth=1, alpha=0.7, label='理论最优值 (0)')
ax4.set_xlabel('迭代次数', fontsize=12)
ax4.set_ylabel('变量值', fontsize=12)
ax4.set_title('最优解各维度收敛过程', fontsize=14)
ax4.legend()
plt.tight_layout()
plt.savefig('genetic_algorithm_results.png', dpi=150, bbox_inches='tight')
plt.show()
print("\n图表已保存为 'genetic_algorithm_results.png'")
# 运行示例
if __name__ == "__main__":
print("=" * 60)
print("遗传算法优化示例")
print("=" * 60)
print("目标函数:Rastrigin函数(多峰函数)")
print("全局最优解:f(0, 0, ...) = 0")
print()
# 创建GA实例
ga = GeneticAlgorithm(
pop_size=100,
n_generations=200,
crossover_rate=0.8,
mutation_rate=0.1,
elitism=2,
bounds=(-5.12, 5.12)
)
# 运行优化(2维便于可视化)
print("开始优化...")
best_solution, best_fitness, history = ga.evolve(dim=2, verbose=True)
print("\n" + "=" * 60)
print("优化结果")
print("=" * 60)
print(f"最优解:{best_solution}")
print(f"最优适应度:{best_fitness:.10f}")
print(f"理论最优值:0")
print(f"相对误差:{abs(best_fitness) * 100:.6f}%")
# 可视化结果
visualize_ga_results(ga, history, dim=2)
```
---
## 5. 粒子群优化算法 (Particle Swarm Optimization, PSO)
### 算法介绍
粒子群优化算法模拟鸟群觅食行为,通过个体之间的信息共享来搜索最优解。每个粒子根据自身历史最优位置和群体全局最优位置更新速度和位置。
**速度更新公式**:
$$
v_{id}^{t+1} = w \cdot v_{id}^t + c_1 \cdot r_1 \cdot (pbest_{id} - x_{id}^t) + c_2 \cdot r_2 \cdot (gbest_d - x_{id}^t)
$$
**位置更新公式**:
$$
x_{id}^{t+1} = x_{id}^t + v_{id}^{t+1}
$$
**参数**:
- $w$:惯性权重(0.4-0.9)
- $c_1, c_2$:学习因子(通常取2.0)
- $r_1, r_2$:随机数(0-1之间)
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 连续优化 | 函数极值求解 | 连续变量 |
| 神经网络训练 | 权重参数优化 | 梯度信息不足 |
| 多目标优化 | 帕累托前沿搜索 | 多个冲突目标 |
| 工程优化 | 结构设计优化 | 复杂约束 |
### 可视化图表类型
- **粒子轨迹图**:粒子在解空间的运动轨迹
- **收敛曲线**:全局最优适应度变化
- **速度分布图**:粒子速度的统计分布
- **拓扑结构图**:粒子邻域关系
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Particle Swarm Optimization | Kennedy & Eberhart | 1995 | IEEE ICNN |
| A modified particle swarm optimizer | Shi & Eberhart | 1998 | IEEE ICEC |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import FancyArrowPatch
import warnings
warnings.filterwarnings('ignore')
# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False
class ParticleSwarmOptimization:
"""
粒子群优化算法实现
"""
def __init__(self, n_particles=50, n_iterations=100,
w=0.9, c1=2.0, c2=2.0, w_decay=0.99,
bounds=(-10, 10)):
self.n_particles = n_particles
self.n_iterations = n_iterations
self.w = w # 惯性权重
self.c1 = c1 # 认知系数
self.c2 = c2 # 社会系数
self.w_decay = w_decay # 惯性权重衰减
self.bounds = bounds
def objective_function(self, x):
"""
目标函数:Ackley函数(多峰函数)
全局最小值在 x = 0 处,f(0) = 0
"""
a = 20
b = 0.2
c = 2 * np.pi
n = len(x)
sum1 = np.sum(x**2)
sum2 = np.sum(np.cos(c * x))
term1 = -a * np.exp(-b * np.sqrt(sum1 / n))
term2 = -np.exp(sum2 / n)
return term1 + term2 + a + np.exp(1)
def initialize_swarm(self, dim):
"""初始化粒子群"""
# 随机初始化位置
positions = np.random.uniform(self.bounds[0], self.bounds[1],
(self.n_particles, dim))
# 随机初始化速度
v_max = (self.bounds[1] - self.bounds[0]) * 0.5
velocities = np.random.uniform(-v_max, v_max, (self.n_particles, dim))
return positions, velocities
def optimize(self, dim=2, verbose=True):
"""执行PSO优化"""
# 初始化
positions, velocities = self.initialize_swarm(dim)
# 初始化个体最优和全局最优
pbest_positions = positions.copy()
pbest_fitness = np.array([self.objective_function(p) for p in positions])
gbest_idx = np.argmin(pbest_fitness)
gbest_position = pbest_positions[gbest_idx].copy()
gbest_fitness = pbest_fitness[gbest_idx]
# 记录历史
history = {
'positions': [positions.copy()],
'velocities': [velocities.copy()],
'gbest_fitness': [gbest_fitness],
'gbest_position': [gbest_position.copy()],
'pbest_fitness': [pbest_fitness.copy()]
}
w = self.w
for iteration in range(self.n_iterations):
for i in range(self.n_particles):
# 评估当前位置
fitness = self.objective_function(positions[i])
# 更新个体最优
if fitness < pbest_fitness[i]:
pbest_fitness[i] = fitness
pbest_positions[i] = positions[i].copy()
# 更新全局最优
if fitness < gbest_fitness:
gbest_fitness = fitness
gbest_position = positions[i].copy()
# 更新速度
r1, r2 = np.random.rand(2)
velocities[i] = (w * velocities[i] +
self.c1 * r1 * (pbest_positions[i] - positions[i]) +
self.c2 * r2 * (gbest_position - positions[i]))
# 速度限制
v_max = (self.bounds[1] - self.bounds[0]) * 0.5
velocities[i] = np.clip(velocities[i], -v_max, v_max)
# 更新位置
positions[i] += velocities[i]
# 边界处理(反弹)
for d in range(dim):
if positions[i, d] < self.bounds[0] or positions[i, d] > self.bounds[1]:
positions[i, d] = np.clip(positions[i, d], self.bounds[0], self.bounds[1])
velocities[i, d] *= -0.5 # 反弹并减速
# 衰减惯性权重
w *= self.w_decay
# 记录历史
if iteration % 5 == 0:
history['positions'].append(positions.copy())
history['velocities'].append(velocities.copy())
history['gbest_fitness'].append(gbest_fitness)
history['gbest_position'].append(gbest_position.copy())
history['pbest_fitness'].append(pbest_fitness.copy())
if verbose and iteration % 10 == 0:
print(f"Iteration {iteration}: Best Fitness = {gbest_fitness:.10f}, w = {w:.4f}")
return gbest_position, gbest_fitness, history
def visualize_pso_results(pso, history, dim=2):
"""可视化PSO优化结果"""
fig = plt.figure(figsize=(16, 12))
gs = fig.add_gridspec(3, 2, height_ratios=[1, 1, 1])
# 图1:收敛曲线
ax1 = fig.add_subplot(gs[0, :])
iterations = range(len(history['gbest_fitness']))
ax1.semilogy(iterations, history['gbest_fitness'], 'b-', linewidth=2, label='全局最优适应度')
# 绘制平均适应度
avg_fitness = [np.mean(f) for f in history['pbest_fitness']]
ax1.semilogy(iterations, avg_fitness, 'r--', linewidth=1.5, alpha=0.7, label='平均个体最优')
ax1.set_xlabel('迭代次数', fontsize=12)
ax1.set_ylabel('适应度(对数尺度)', fontsize=12)
ax1.set_title('PSO收敛曲线', fontsize=14)
ax1.legend()
# 图2:粒子轨迹(2D情况)
if dim == 2:
ax2 = fig.add_subplot(gs[1, 0])
# 绘制目标函数等高线
x = np.linspace(pso.bounds[0], pso.bounds[1], 100)
y = np.linspace(pso.bounds[0], pso.bounds[1], 100)
X, Y = np.meshgrid(x, y)
Z = np.zeros_like(X)
for i in range(X.shape[0]):
for j in range(X.shape[1]):
Z[i, j] = pso.objective_function(np.array([X[i, j], Y[i, j]]))
contour = ax2.contour(X, Y, Z, levels=15, cmap='viridis', alpha=0.6)
ax2.clabel(contour, inline=True, fontsize=8)
# 绘制粒子轨迹(每隔几代)
for i in range(0, len(history['positions']), max(1, len(history['positions'])//5)):
positions = history['positions'][i]
alpha = 0.3 + 0.7 * (i / len(history['positions']))
size = 20 + 30 * (i / len(history['positions']))
ax2.scatter(positions[:, 0], positions[:, 1],
c='blue', alpha=alpha, s=size, edgecolors='black', linewidths=0.5)
# 绘制全局最优轨迹
gbest_path = np.array(history['gbest_position'])
ax2.plot(gbest_path[:, 0], gbest_path[:, 1], 'r-', linewidth=2, alpha=0.8, label='全局最优轨迹')
ax2.scatter(gbest_path[-1, 0], gbest_path[-1, 1], c='red', s=300, marker='*',
edgecolors='black', linewidths=2, label='最终最优解', zorder=5)
ax2.set_xlabel('x₁', fontsize=12)
ax2.set_ylabel('x₂', fontsize=12)
ax2.set_title('粒子运动轨迹', fontsize=14)
ax2.legend()
# 图3:速度分布
ax3 = fig.add_subplot(gs[1, 1])
# 计算各代的速度大小
velocity_magnitudes = []
for velocities in history['velocities']:
magnitudes = np.linalg.norm(velocities, axis=1)
velocity_magnitudes.append(magnitudes)
# 绘制速度分布的箱线图
sample_indices = range(0, len(velocity_magnitudes), max(1, len(velocity_magnitudes)//8))
sample_velocities = [velocity_magnitudes[i] for i in sample_indices]
labels = [f'Gen {i*5}' for i in sample_indices]
if sample_velocities:
bp = ax3.boxplot(sample_velocities, labels=labels, patch_artist=True)
for patch in bp['boxes']:
patch.set_facecolor('lightgreen')
ax3.set_ylabel('速度大小', fontsize=12)
ax3.set_xlabel('代数', fontsize=12)
ax3.set_title('粒子速度分布演化', fontsize=14)
# 图4:最优位置各维度变化
ax4 = fig.add_subplot(gs[2, :])
gbest_positions = np.array(history['gbest_position'])
for d in range(dim):
ax4.plot(gbest_positions[:, d], linewidth=2, label=f'维度 {d+1}')
# 添加理论最优值参考线
ax4.axhline(y=0, color='r', linestyle='--', linewidth=1, alpha=0.7, label='理论最优值 (0)')
ax4.set_xlabel('迭代次数', fontsize=12)
ax4.set_ylabel('位置值', fontsize=12)
ax4.set_title('全局最优位置收敛过程', fontsize=14)
ax4.legend()
plt.tight_layout()
plt.savefig('pso_results.png', dpi=150, bbox_inches='tight')
plt.show()
print("\n图表已保存为 'pso_results.png'")
# 运行示例
if __name__ == "__main__":
print("=" * 60)
print("粒子群优化算法示例")
print("=" * 60)
print("目标函数:Ackley函数(多峰函数)")
print("全局最优解:f(0, 0, ...) = 0")
print()
# 创建PSO实例
pso = ParticleSwarmOptimization(
n_particles=50,
n_iterations=100,
w=0.9,
c1=2.0,
c2=2.0,
w_decay=0.99,
bounds=(-5, 5)
)
# 运行优化
print("开始优化...")
best_position, best_fitness, history = pso.optimize(dim=2, verbose=True)
print("\n" + "=" * 60)
print("优化结果")
print("=" * 60)
print(f"最优位置:{best_position}")
print(f"最优适应度:{best_fitness:.10f}")
print(f"理论最优值:0")
print(f"相对误差:{abs(best_fitness) * 100:.6f}%")
# 可视化结果
visualize_pso_results(pso, history, dim=2)
```
---
## 6. 模拟退火算法 (Simulated Annealing, SA)
### 算法介绍
模拟退火算法模拟固体退火过程,通过概率性接受劣解来避免陷入局部最优。算法从高温开始,随着温度下降,接受劣解的概率逐渐降低。
**Metropolis准则**:
$$
P(accept) = \begin{cases}
1, & \Delta E < 0 \\
\exp(-\Delta E / T), & \Delta E \geq 0
\end{cases}
$$
**降温策略**:
- 线性降温:$T_{k+1} = \alpha \cdot T_k$
- 指数降温:$T_{k+1} = T_0 / (1 + \ln(k))$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 组合优化 | 旅行商问题 | 离散解空间 |
| 调度问题 | 生产调度 | 复杂约束 |
| 图着色 | 地图着色、频率分配 | 约束满足 |
| VLSI设计 | 电路布局 | 大规模优化 |
### 可视化图表类型
- **温度曲线**:温度随迭代次数变化
- **能量曲线**:目标函数值变化
- **接受率图**:新解接受概率变化
- **解空间探索图**:解的搜索轨迹
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Optimization by Simulated Annealing | Kirkpatrick et al. | 1983 | Science |
| Equation of State Calculations by Fast Computing Machines | Metropolis et al. | 1953 | J. Chem. Phys. |
### 代码实现要点
```python
# 常用库:simanneal, scipy.optimize
from simanneal import Annealer
class TSPProblem(Annealer):
def __init__(self, state, distance_matrix):
self.state = state
self.distance_matrix = distance_matrix
def move(self):
# 交换两个城市的位置
a, b = random.sample(range(len(self.state)), 2)
self.state[a], self.state[b] = self.state[b], self.state[a]
def energy(self):
# 计算总距离
return sum(self.distance_matrix[self.state[i], self.state[i+1]]
for i in range(len(self.state)-1))
```
---
## 7. 蚁群算法 (Ant Colony Optimization, ACO)
### 算法介绍
蚁群算法模拟蚂蚁觅食过程中的信息素沟通机制。蚂蚁在路径上释放信息素,后续蚂蚁根据信息素浓度选择路径,正反馈机制使算法收敛到最优路径。
**状态转移概率**:
$$
P_{ij}^k = \begin{cases}
\frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{s \in allowed_k} [\tau_{is}]^\alpha [\eta_{is}]^\beta}, & j \in allowed_k \\
0, & \text{otherwise}
\end{cases}
$$
**信息素更新**:
$$
\tau_{ij} = (1 - \rho) \cdot \tau_{ij} + \sum_{k=1}^m \Delta \tau_{ij}^k
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 路径规划 | 旅行商问题、车辆路径 | 图结构 |
| 调度问题 | 作业调度、项目调度 | 组合优化 |
| 网络路由 | 通信网络路由 | 动态环境 |
| 资源分配 | 任务分配、负载均衡 | 分配问题 |
### 可视化图表类型
- **路径图**:蚂蚁移动路径可视化
- **信息素热力图**:信息素浓度分布
- **收敛曲线**:最优解质量变化
- **蚂蚁分布图**:蚂蚁在解空间的分布
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Ant system: optimization by a colony | Dorigo & Gambardella | 1997 | IEEE Transactions on Systems, Man, and Cybernetics |
| The Ant System | Dorigo, Maniezzo & Colorni | 1991 | European Conference on Artificial Life |
### 代码实现要点
```python
# 常用库:aco, networkx
import numpy as np
def ant_colony_optimization(distance_matrix, n_ants=20, n_iterations=100,
alpha=1, beta=2, evaporation_rate=0.1):
n_cities = len(distance_matrix)
pheromone = np.ones((n_cities, n_cities)) / n_cities
for iteration in range(n_iterations):
# 所有蚂蚁构建路径
paths = []
for ant in range(n_ants):
path = construct_path(pheromone, distance_matrix, alpha, beta)
paths.append(path)
# 更新信息素
pheromone *= (1 - evaporation_rate)
for path in paths:
for i in range(len(path) - 1):
pheromone[path[i], path[i+1]] += 1 / path_length(path, distance_matrix)
```
---
## 8. 差分进化算法 (Differential Evolution, DE)
### 算法介绍
差分进化算法是一种基于群体差异的进化算法,通过差分变异操作产生新个体。算法简单高效,特别适合连续优化问题。
**基本操作**:
1. **变异**:$V_i = X_{r1} + F \cdot (X_{r2} - X_{r3})$
2. **交叉**:$U_{ij} = \begin{cases} V_{ij}, & \text{rand} \leq CR \text{ or } j = j_{rand} \\ X_{ij}, & \text{otherwise} \end{cases}$
3. **选择**:贪心选择更优个体
**参数**:
- $F$:缩放因子(0.4-1.0)
- $CR$:交叉概率(0.1-0.9)
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 连续优化 | 函数优化 | 连续变量 |
| 参数估计 | 模型参数拟合 | 非线性优化 |
| 信号处理 | 滤波器设计 | 多维优化 |
| 控制系统 | PID参数整定 | 实时优化 |
### 可视化图表类型
- **进化曲线**:适应度随代数变化
- **种群分布图**:个体在解空间的分布
- **差异向量图**:变异操作示意图
- **参数敏感性图**:参数F和CR的影响
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Differential Evolution - A Simple and Efficient Heuristic for Global Optimization | Storn & Price | 1997 | Journal of Global Optimization |
| Differential Evolution: A Practical Approach to Global Optimization | Price, Storn & Lampinen | 2005 | Springer |
### 代码实现要点
```python
# 常用库:scipy.optimize.differential_evolution, DEAP
from scipy.optimize import differential_evolution
def objective_function(x):
return sum(x**2)
bounds = [(-10, 10), (-10, 10), (-10, 10)]
result = differential_evolution(objective_function, bounds,
strategy='best1bin',
maxiter=1000,
popsize=15,
tol=1e-6)
```
---
## 9. 禁忌搜索算法 (Tabu Search, TS)
### 算法介绍
禁忌搜索算法通过记忆机制避免循环搜索,使用禁忌表记录最近访问的解,在指定迭代次数内不允许重复访问。
**核心要素**:
- **禁忌表**:存储禁忌对象
- **禁忌长度**:对象被禁忌的迭代次数
- **特赦规则**:某些情况下可解除禁忌
- **候选集**:邻域中的候选解
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 调度问题 | 作业调度、排班 | 组合优化 |
| 路径问题 | 旅行商问题、车辆路径 | 图搜索 |
| 设施选址 | 仓库选址、服务点布局 | 离散优化 |
| 图着色 | 地图着色、时间表问题 | 约束满足 |
### 可视化图表类型
- **搜索轨迹图**:解在搜索过程中的变化
- **禁忌表状态**:禁忌对象的变化
- **邻域结构图**:当前解的邻域
- **最优解更新图**:全局最优的更新过程
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Tabu Search - Part I | Fred Glover | 1989 | ORSA Journal on Computing |
| Tabu Search - Part II | Fred Glover | 1990 | ORSA Journal on Computing |
### 代码实现要点
```python
def tabu_search(initial_solution, objective_func, neighborhood_func,
tabu_tenure=10, max_iterations=1000):
current_solution = initial_solution
best_solution = initial_solution
tabu_list = []
for iteration in range(max_iterations):
# 生成候选解
candidates = neighborhood_func(current_solution)
# 过滤禁忌解
non_tabu_candidates = [c for c in candidates if c not in tabu_list]
# 选择最优候选解
best_candidate = max(non_tabu_candidates, key=objective_func)
# 更新当前解和禁忌表
current_solution = best_candidate
tabu_list.append(best_candidate)
if len(tabu_list) > tabu_tenure:
tabu_list.pop(0)
if objective_func(best_candidate) > objective_func(best_solution):
best_solution = best_candidate
return best_solution
```
---
## 10. 灰狼优化算法 (Grey Wolf Optimizer, GWO)
### 算法介绍
灰狼优化算法模拟灰狼的社会等级和狩猎行为。算法将种群分为四个等级:α、β、δ和ω,通过前三个等级的个体引导种群向猎物(最优解)移动。
**位置更新公式**:
$$
\vec{X}(t+1) = \frac{\vec{X}_1 + \vec{X}_2 + \vec{X}_3}{3}
$$
其中:
$$
\vec{X}_1 = \vec{X}_\alpha - \vec{A}_1 \cdot |\vec{C}_1 \cdot \vec{X}_\alpha - \vec{X}|
$$
$$
\vec{X}_2 = \vec{X}_\beta - \vec{A}_2 \cdot |\vec{C}_2 \cdot \vec{X}_\beta - \vec{X}|
$$
$$
\vec{X}_3 = \vec{X}_\delta - \vec{A}_3 \cdot |\vec{C}_3 \cdot \vec{X}_\delta - \vec{X}|
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 函数优化 | 多模态函数优化 | 非凸、非线性 |
| 参数优化 | 神经网络参数 | 高维搜索 |
| 工程优化 | 结构设计优化 | 复杂约束 |
| 能源系统 | 发电调度 | 非线性系统 |
### 可视化图表类型
- **等级位置图**:α、β、δ在解空间的位置
- **收敛曲线**:适应度随代数变化
- **三维轨迹图**: wolves在三维空间的移动轨迹
- **等级变化图**:个体等级的变化历史
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Grey Wolf Optimizer | Mirjalili, Mirjalili & Lewis | 2014 | Advances in Engineering Software |
| The Grey Wolf Optimizer | Sareh, Mirjalili & Lewis | 2014 | 2014 IEEE Congress on Evolutionary Computation |
### 代码实现要点
```python
import numpy as np
def grey_wolf_optimizer(objective_func, dim, bounds, n_wolves=30, max_iter=100, seed=42):
"""
灰狼优化算法(完整可运行)
:param objective_func: 目标函数 f(x) -> 标量(最小化)
:param dim: 维度
:param bounds: 边界 (lower, upper),可每维不同
:param n_wolves: 种群大小
:param max_iter: 最大迭代次数
:param seed: 随机种子
:return: 最优解位置, 最优值
"""
rng = np.random.default_rng(seed)
lower, upper = np.atleast_1d(bounds[0]), np.atleast_1d(bounds[1])
lower = np.full(dim, lower[0]) if lower.size == 1 else lower
upper = np.full(dim, upper[0]) if upper.size == 1 else upper
# 初始化狼群位置
wolves = rng.uniform(lower, upper, (n_wolves, dim))
scores = np.array([objective_func(w) for w in wolves])
# 前三个最优个体:alpha(最优)、beta、delta
order = np.argsort(scores)
alpha_pos, alpha_score = wolves[order[0]].copy(), scores[order[0]]
beta_pos, beta_score = wolves[order[1]].copy(), scores[order[1]]
delta_pos, delta_score = wolves[order[2]].copy(), scores[order[2]]
for t in range(max_iter):
a = 2 - 2 * t / max_iter # 线性递减的收敛因子
for i in range(n_wolves):
# 分别以 alpha/beta/delta 为目标更新位置,取三者的加权
new_pos = np.zeros(dim)
for leader_pos in (alpha_pos, beta_pos, delta_pos):
A = 2 * a * rng.random(dim) - a
C = 2 * rng.random(dim)
D = np.abs(C * leader_pos - wolves[i])
new_pos += leader_pos - A * D
new_pos /= 3
# 边界裁剪
wolves[i] = np.clip(new_pos, lower, upper)
# 更新最优三头
s = objective_func(wolves[i])
if s < alpha_score:
delta_pos, delta_score = beta_pos.copy(), beta_score
beta_pos, beta_score = alpha_pos.copy(), alpha_score
alpha_pos, alpha_score = wolves[i].copy(), s
elif s < beta_score:
delta_pos, delta_score = beta_pos.copy(), beta_score
beta_pos, beta_score = wolves[i].copy(), s
elif s < delta_score:
delta_pos, delta_score = wolves[i].copy(), s
return alpha_pos, alpha_score
```
---
## 11. 免疫算法 (Immune Algorithm, IA)
### 算法介绍
免疫算法模拟生物免疫系统的抗原识别、抗体产生、克隆选择、免疫记忆等机制。算法通过抗体与抗原的亲和度以及抗体之间的抑制关系维持种群多样性。
**核心操作**:
1. **抗原识别**:识别待优化问题
2. **抗体产生**:生成候选解
3. **亲和度计算**:评估解的质量
4. **克隆选择**:优质抗体克隆扩增
5. **亲和突变**:克隆抗体高频变异
6. **免疫抑制**:相似抗体相互抑制
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 函数优化 | 多峰函数优化 | 需要维持多样性 |
| 组合优化 | 旅行商问题 | NP-hard |
| 机器学习 | 特征选择 | 高维搜索 |
| 异常检测 | 网络入侵检测 | 模式识别 |
### 可视化图表类型
- **抗体分布图**:抗体在解空间的分布
- **亲和度热力图**:抗体与抗原的亲和度
- **克隆扩增图**:克隆过程可视化
- **多样性曲线**:种群多样性变化
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Artificial Immune Systems: A Novel Computational Intelligence Approach | de Castro & Timmis | 2002 | Springer |
| The Clonal Selection Algorithm with Engineering Applications | de Castro & Von Zuben | 2000 | GECCO |
### 代码实现要点
```python
import numpy as np
def immune_algorithm(objective_func, dim, bounds, n_antibodies=50,
clone_factor=5, mutation_rate=0.1, max_iter=100, seed=42):
"""
免疫算法(完整可运行,克隆选择 + 免疫抑制)
:param objective_func: 目标函数 f(x) -> 标量(最小化)
:param dim: 维度
:param bounds: 边界 (lower, upper)
:param n_antibodies: 抗体种群规模
:param clone_factor: 克隆倍数
:param mutation_rate: 变异强度(高斯扰动标准差)
:param max_iter: 最大迭代次数
:param seed: 随机种子
:return: 最优抗体位置, 最优亲和度
"""
rng = np.random.default_rng(seed)
lower, upper = bounds[0], bounds[1]
antibodies = rng.uniform(lower, upper, (n_antibodies, dim))
best_antibody = antibodies[0].copy()
best_affinity = objective_func(best_antibody)
for t in range(max_iter):
# 亲和度(越小越好,最小化)
affinity = np.array([objective_func(ab) for ab in antibodies])
# 更新全局最优
j = int(np.argmin(affinity))
if affinity[j] < best_affinity:
best_affinity = affinity[j]
best_antibody = antibodies[j].copy()
# 变异幅度随迭代衰减:先大步探索,后小步精细搜索
sigma = mutation_rate * (1 - t / max_iter) + 1e-6
# 选择优质抗体(亲和度前一半)进行克隆
selected_indices = np.argsort(affinity)[:n_antibodies // 2]
selected = antibodies[selected_indices]
# 克隆扩增:优质抗体按克隆倍数复制,高斯变异(幅度衰减)
clones = [best_antibody.copy()] # 精英保留,保证收敛
for ab in selected:
for _ in range(clone_factor):
clone = ab + rng.normal(0, sigma, dim)
clones.append(np.clip(clone, lower, upper))
# 免疫抑制:对克隆池按亲和度择优,重组成与种群相同规模
clone_pool = np.array(clones)
clone_aff = np.array([objective_func(c) for c in clone_pool])
keep = np.argsort(clone_aff)[:n_antibodies]
antibodies = clone_pool[keep]
return best_antibody, best_affinity
```
---
## 12. 鲸鱼优化算法 (Whale Optimization Algorithm, WOA)
### 算法介绍
鲸鱼优化算法是Mirjalili等人于2016年提出的一种新型元启发式算法,模拟座头鲸的泡泡网捕食行为。算法通过座头鲸包围猎物、螺旋更新位置和随机搜索三种机制实现全局优化。
**位置更新公式**:
**包围猎物**:
$$
\vec{D} = |\vec{C} \cdot \vec{X}^*(t) - \vec{X}(t)|
$$
$$
\vec{X}(t+1) = \vec{X}^*(t) - \vec{A} \cdot \vec{D}
$$
**螺旋更新**:
$$
\vec{X}(t+1) = \vec{D}' \cdot e^{bl} \cdot \cos(2\pi l) + \vec{X}^*(t)
$$
其中 $\vec{D}' = |\vec{X}^*(t) - \vec{X}(t)|$ 表示鲸鱼与猎物的距离
**参数**:
- $\vec{A}$:收敛系数,随迭代从2线性递减到0
- $\vec{C}$:摇摆系数,[0, 2]随机数
- $b$:对数螺旋形状常数(通常取1)
- $l$:[-1, 1]随机数
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 连续优化 | 函数极值求解 | 连续变量、多维 |
| 工程优化 | 结构设计、参数优化 | 非线性约束 |
| 电力系统 | 经济调度、无功优化 | 复杂约束 |
| 机器学习 | 神经网络训练 | 参数优化 |
### 可视化图表类型
- **收敛曲线**:适应度随迭代次数变化
- **位置轨迹图**:鲸鱼在解空间的移动轨迹
- **螺旋包围图**:泡泡网捕食行为可视化
- **参数敏感性图**:参数b对算法性能的影响
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| The Whale Optimization Algorithm | Mirjalili, Lewis | 2016 | Advances in Engineering Software |
| Whale Optimization Algorithm: A comprehensive review | Abdel-Basset et al. | 2023 | Expert Systems with Applications |
### 代码实现要点
```python
import numpy as np
def whale_optimization(objective_func, dim, bounds, n_whales=30, max_iter=100):
# 初始化鲸鱼位置
whales = np.random.uniform(bounds[0], bounds[1], (n_whales, dim))
best_whale = whales[0].copy()
best_fitness = objective_func(best_whale)
for iteration in range(max_iter):
# 线性递减a从2到0
a = 2 - iteration * (2 / max_iter)
for i in range(n_whales):
r1 = np.random.rand()
r2 = np.random.rand()
A = 2 * a * r1 - a
C = 2 * r2
p = np.random.rand()
if p < 0.5:
# 包围机制
if abs(A) < 1:
D = abs(C * best_whale - whales[i])
whales[i] = best_whale - A * D
else:
# 随机搜索
random_whale = whales[np.random.randint(n_whales)]
D = abs(C * random_whale - whales[i])
whales[i] = random_whale - A * D
else:
# 螺旋更新
D_prime = abs(best_whale - whales[i])
b = 1
l = (np.random.rand() * 2 - 1)
whales[i] = D_prime * np.exp(b * l) * np.cos(2 * np.pi * l) + best_whale
# 边界处理
whales[i] = np.clip(whales[i], bounds[0], bounds[1])
# 更新最优解
fitness = objective_func(whales[i])
if fitness < best_fitness:
best_fitness = fitness
best_whale = whales[i].copy()
return best_whale, best_fitness
```
---
## 13. 麻雀搜索算法 (Sparrow Search Algorithm, SSA)
### 算法介绍
麻雀搜索算法是Xue等人于2020年提出的新型元启发式算法,模拟麻雀种群的觅食和反捕食行为。算法将麻雀分为发现者、跟随者和预警者三类,通过协同搜索实现快速收敛。
**发现者位置更新**:
$$
X_{i,j}^{t+1} = \begin{cases}
X_{i,j}^t \cdot \exp(-\frac{i}{\alpha \cdot iter_{max}}), & R_2 < ST \\
X_{i,j}^t + Q \cdot L, & R_2 \geq ST
\end{cases}
$$
**跟随者位置更新**:
$$
X_{i,j}^{t+1} = \begin{cases}
Q \cdot \exp(\frac{X_{worst} - X_{i,j}^t}{i^2}), & i > n/2 \\
X_{p}^{t+1} + |X_{i,j}^t - X_{p}^{t+1}| \cdot A^+ \cdot L, & \text{otherwise}
\end{cases}
$$
**预警者位置更新**:
$$
X_{i,j}^{t+1} = \begin{cases}
X_{best}^t + \beta \cdot |X_{i,j}^t - X_{best}^t|, & f_i > f_g \\
X_{i,j}^t + K \cdot \frac{|X_{i,j}^t - X_{worst}^t|}{f_i - f_w + \epsilon}, & f_i = f_g
\end{cases}
$$
**参数**:
- $ST$:安全阈值(0.2-0.8)
- $\alpha$:[0, 1]随机数
- $R_2$:预警值,[0, 1]随机数
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 函数优化 | 多模态函数优化 | 快速收敛 |
| 参数辨识 | 系统参数估计 | 高精度 |
| 调度优化 | 生产调度、资源分配 | 组合优化 |
| 工程设计 | 结构优化设计 | 实际约束 |
### 可视化图表类型
- **角色分布图**:发现者、跟随者、预警者的分布
- **收敛曲线**:适应度快速变化过程
- **位置更新图**:三类麻雀的位置更新轨迹
- **警戒值变化图**:安全阈值影响分析
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Sparrow search algorithm: A novel efficient algorithm | Xue & Shen | 2020 | Journal of Computational Design and Engineering |
| Improved sparrow search algorithm | Ouyang et al. | 2021 | Expert Systems with Applications |
### 代码实现要点
```python
import numpy as np
def sparrow_search_algorithm(objective_func, dim, bounds, n_sparrows=50,
max_iter=100, ST=0.8):
# 初始化麻雀种群
sparrows = np.random.uniform(bounds[0], bounds[1], (n_sparrows, dim))
fitness = np.array([objective_func(s) for s in sparrows])
# 排序并确定最佳和最差位置
sorted_idx = np.argsort(fitness)
best_pos = sparrows[sorted_idx[0]].copy()
worst_pos = sparrows[sorted_idx[-1]].copy()
best_fitness = fitness[sorted_idx[0]]
worst_fitness = fitness[sorted_idx[-1]]
# 发现者数量(前20%)
n_discoverers = int(0.2 * n_sparrows)
for iteration in range(max_iter):
for i in range(n_sparrows):
R2 = np.random.rand()
if i < n_discoverers:
# 发现者更新
if R2 < ST:
sparrows[i] *= np.exp(-i / (np.random.rand() * max_iter))
else:
sparrows[i] += np.random.randn()
else:
# 跟随者更新
if i > n_sparrows / 2:
sparrows[i] = np.random.randn() * np.exp(
(worst_pos - sparrows[i]) / i**2)
else:
A = np.floor(np.random.randn() * dim)
AA = A.T @ (A @ A.T)**-1 if A.shape else 0
sparrows[i] = best_pos + abs(sparrows[i] - best_pos) * AA
# 边界处理
sparrows[i] = np.clip(sparrows[i], bounds[0], bounds[1])
# 预警者更新(适应度最差的10%)
worst_indices = sorted_idx[-int(0.1 * n_sparrows):]
for i in worst_indices:
if fitness[i] > best_fitness:
sparrows[i] = best_pos + np.random.randn() * abs(sparrows[i] - best_pos)
else:
sparrows[i] += np.random.randn() * abs(
sparrows[i] - worst_pos) / (fitness[i] - worst_fitness + 1e-10)
# 更新适应度和最优解
fitness = np.array([objective_func(s) for s in sparrows])
current_best_idx = np.argmin(fitness)
if fitness[current_best_idx] < best_fitness:
best_fitness = fitness[current_best_idx]
best_pos = sparrows[current_best_idx].copy()
return best_pos, best_fitness
```
---
## 14. 多目标优化 (Multi-Objective Optimization, MOO)
### 算法介绍
多目标优化问题涉及多个相互冲突的目标函数,需要找到一组折衷解(Pareto最优解集)。
**标准形式**:
$$
\min F(x) = [f_1(x), f_2(x), \ldots, f_k(x)]^T
$$
$$
\text{s.t. } g_i(x) \leq 0, h_j(x) = 0, x \in \Omega
$$
**Pareto支配关系**:
- 解 $x_1$ 支配 $x_2$:$\forall i, f_i(x_1) \leq f_i(x_2)$ 且 $\exists i, f_i(x_1) < f_i(x_2)$
- Pareto最优解:不被任何其他解支配的解
- Pareto前沿:所有Pareto最优解在目标空间中的投影
### 常用算法
#### NSGA-II (Non-dominated Sorting Genetic Algorithm II)
**核心机制**:
1. **快速非支配排序**:将种群分为多个Pareto等级
2. **拥挤度距离**:保持解集分布均匀性
3. **精英策略**:保留优秀个体到下一代
**拥挤度计算**:
$$
D_{i,d} = \sum_{d=1}^{k} \frac{|f_d^{i+1} - f_d^{i-1}|}{f_d^{max} - f_d^{min}}
$$
#### MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition)
**核心思想**:将多目标优化分解为多个单目标子问题
**分解方法**:
- 加权求和法:$\min \sum_{i=1}^k \lambda_i f_i(x)$
- Tchebycheff法:$\min \max_{i} \{\lambda_i |f_i(x) - z_i^*|\}$
- 边界交集法
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 工程设计 | 结构优化、参数设计 | 多冲突目标 |
| 资源分配 | 预算分配、投资组合 | 效益与成本权衡 |
| 调度问题 | 生产调度、任务分配 | 时间与成本 |
| 路径规划 | 物流路径、网络设计 | 距离与风险 |
### 可视化图表类型
- **Pareto前沿图**:多目标解的分布(二维/三维)
- **收敛曲线**:超体积指标随迭代变化
- **散点图**:解集在目标空间的分布
- **平行坐标图**:高维目标的可视化
- **热力图**:解集密度分布
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| A fast and elitist multiobjective genetic algorithm: NSGA-II | Deb et al. | 2002 | IEEE TEVC |
| MOEA/D: A multiobjective evolutionary algorithm based on decomposition | Zhang & Li | 2007 | IEEE TEVC |
| Multi-Objective Optimization Using Evolutionary Algorithms | Deb | 2001 | Wiley |
### 代码实现要点
```python
# 常用库:pymoo, DEAP, platypus
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.optimize import minimize
from pymoo.problems import get_problem
# 定义问题
problem = get_problem("zdt1")
# 创建NSGA-II算法
algorithm = NSGA2(pop_size=100)
# 执行优化
result = minimize(problem,
algorithm,
('n_gen', 200),
seed=1,
verbose=True)
# 获取Pareto前沿
pareto_front = result.F
pareto_set = result.X
```
---
## 15. 鲁棒优化 (Robust Optimization, RO)
### 算法介绍
鲁棒优化处理参数不确定性的优化问题,寻找在所有可能的不确定性实现下都能保持可行性和良好性能的解。
**不确定性集类型**:
1. **盒子不确定性集**:
$$
U = \{\xi : |\xi_j - \bar{\xi}_j| \leq \hat{\xi}_j, \forall j\}
$$
2. **椭球不确定性集**:
$$
U = \{\xi : (\xi - \bar{\xi})^T \Sigma^{-1} (\xi - \bar{\xi}) \leq \Gamma^2\}
$$
3. **多面体不确定性集**(Bertsimas-Sim模型):
$$
U = \{\xi : \xi_j = \bar{\xi}_j + \eta_j \hat{\xi}_j, \|\eta\|_1 \leq \Gamma, \|\eta\|_\infty \leq 1\}
$$
**鲁棒对应问题**:
$$
\min_x \max_{\xi \in U} f(x, \xi)
$$
$$
\text{s.t. } g(x, \xi) \leq 0, \forall \xi \in U
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 供应链优化 | 网络设计、库存管理 | 需求不确定性 |
| 金融投资 | 投资组合优化 | 收益率波动 |
| 能源系统 | 发电调度 | 可再生能源波动 |
| 工程设计 | 结构设计 | 参数偏差 |
### 可视化图表类型
- **不确定性集图**:参数不确定性的范围
- **鲁棒解与名义解对比**:解的性能对比
- **情景分析图**:不同情景下的解表现
- **敏感度分析图**:鲁棒性水平与目标关系
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Robust Optimization | Ben-Tal, El Ghaoui, Nemirovski | 2009 | Princeton University Press |
| The Price of Robustness | Bertsimas & Sim | 2004 | Operations Research |
| Robust optimization – a comprehensive review | Gabrel et al. | 2014 | European Journal of Operational Research |
### 代码实现要点
```python
import numpy as np
from scipy.optimize import minimize
def robust_optimization_nominal(objective_func, constraint_func,
nominal_params, uncertainty_budgets,
bounds, method='SLSQP'):
"""
鲁棒优化:使用Bertsimas-Sim模型
uncertainty_budgets: 每个参数的不确定性预算Gamma
"""
def robust_objective(x):
# 最坏情况目标(保守策略)
worst_obj = objective_func(x, nominal_params)
# 考虑参数扰动
for i, (param, budget) in enumerate(zip(nominal_params, uncertainty_budgets)):
perturbation = budget * np.sign(x[i]) if budget > 0 else 0
worst_obj = max(worst_obj, objective_func(x, nominal_params + perturbation))
return worst_obj
def robust_constraint(x):
# 鲁棒约束:满足所有不确定性实现
return constraint_func(x, nominal_params)
result = minimize(robust_objective,
x0=np.random.rand(len(nominal_params)),
bounds=bounds,
constraints={'type': 'ineq', 'fun': robust_constraint},
method=method)
return result.x
```
---
## 优化算法选择指南
### 按问题规模选择
| 规模 | 推荐算法 | 说明 |
|------|---------|------|
| 小规模(<10变量) | 线性规划、分支定界 | 可求得精确解 |
| 中规模(10-100变量) | 整数规划、差分进化 | 平衡精度与效率 |
| 大规模(>100变量) | 启发式算法(GA、PSO、ACO) | 快速获得满意解 |
### 按问题类型选择
| 问题特征 | 推荐算法 |
|---------|---------|
| 线性目标+线性约束 | 线性规划 |
| 需要整数解 | 整数规划、分支定界 |
| 多阶段决策 | 动态规划 |
| 非凸、多峰 | 遗传算法、粒子群优化 |
| 图结构问题 | 蚁群算法、禁忌搜索 |
| 连续优化 | 差分进化、灰狼优化 |
### 按约束类型选择
| 约束类型 | 推荐算法 |
|---------|---------|
| 无约束 | 梯度下降、牛顿法、PSO、DE |
| 线性约束 | 线性规划、投影梯度法 |
| 非线性约束 | 序列二次规划、罚函数法 |
| 逻辑约束 | 整数规划、约束GA |
| 动态约束 | 动态规划、模型预测控制 |
---
## 参考文献
1. Dantzig, G. B. (1963). *Linear Programming and Extensions*. Princeton University Press.
2. Bellman, R. (1957). *Dynamic Programming*. Princeton University Press.
3. Holland, J. H. (1975). *Adaptation in Natural and Artificial Systems*. University of Michigan Press.
4. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. *IEEE ICNN*, 1942-1948.
5. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. *Science*, 220(4598), 671-680.
6. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. *IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)*, 26(1), 29-41.
7. Storn, R., & Price, K. (1997). Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. *Journal of Global Optimization*, 11(4), 341-359.
8. Glover, F. (1989). Tabu search – Part I. *ORSA Journal on Computing*, 1(3), 190-206.
9. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. *Advances in Engineering Software*, 69, 46-61.
10. Mirjalili, S., & Lewis, A. (2016). The whale optimization algorithm. *Advances in Engineering Software*, 95, 51-67.
11. Xue, J., & Shen, B. (2020). A novel swarm intelligence optimization approach: sparrow search algorithm. *Systems Science & Control Engineering*, 8(1), 22-34.
12. Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. *IEEE Transactions on Evolutionary Computation*, 6(2), 182-197.
13. Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. *IEEE Transactions on Evolutionary Computation*, 11(6), 712-731.
14. Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). *Robust Optimization*. Princeton University Press.
15. de Castro, L. N., & Timmis, J. (2002). *Artificial Immune Systems: A Novel Computational Intelligence Approach*. Springer.
Related skills
| Skill | Stars | Updated | Works with | Status | Install |
|---|---|---|---|---|---|
| reverse-engineer-anythingmorluto/reaReverse engineer native, managed, Electron/JavaScript, packaged, firmware, and browser targets with REA, and build agent environments (AgentEnv bundles) of web applications from a live instance or a capture, and of Linux desktop apps with a task from a request. Use shipped-artifact or requested runtime evidence to explain features, compare versions, decompile code, or guide a reconstruction. Skip REA for ordinary source-repository architecture analysis. | Stars: 472k | Updated | Claude CodeCodex | Verified | Install |
| diagnosing-superpowersobra/superpowersUse when a superpowers session went wrong and your human partner wants to know why — repeated work, ignored plans, stumbles, poor results, a skill that didn't fire, "it took too long", "why is it so expensive", "what is it doing" — or wants to build a bug report for the superpowers maintainers, for the current session or a past one identified by id or path, on any harness. | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |
| dispatching-parallel-agentsobra/superpowersUse when facing 2+ independent tasks that can be worked on without shared state or sequential dependencies | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |
| executing-plansobra/superpowersUse when executing an implementation plan in the current session as the implementer yourself — your human partner chose inline execution, or no subagent tool is available | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |