EC Lecture 3 Constrained Optimization
目标函数 vs. 约束 Objective vs. Constraint
示例问题：
- 目标函数 Objective function：需要被最小化/最大化的函数（这里是最小化）。
- 约束 Constraint：可行解必须满足的条件（这里要求
在受约束优化中比较解 Comparing solutions in constrained optimization
例子（第 0 代/若干候选点）：
| 0 | 0 | -1.5 |
| 1 | -1 | -0.5 |
| 1.5 | -0.75 | 0 |
| 2 | 0 | 0.5 |
目标与约束的区别 Objectives and constraints
- 目标 Objective：越小越好（针对最小化问题；若是最大化，则需做相应处理）。
- 约束 Constraint：只有 可行 Feasible / 不可行 Infeasible 两类
- 可行解通常被视为"同一层级"（都满足约束）。
- 不可行解之间仍可比较"好坏"（取决于违反程度）。
受约束优化的解排序 Rank solutions
- 可行解 Feasible solutions 优于 不可行解 Infeasible solutions
- 两个可行解：目标函数值 Objective value 更优者更好（最小化时更小更好）
- 两个不可行解：约束违反 Constraint violation 更小者更好
处理约束：违反程度与惩罚函数 Handling Constraints
描述约束违反 Describe constraint violation
约束违反之和 Sum of the constraint violation
- Case 1：总重量
vs. 要求 （违反 ）； 总体积 vs. 要求 （违反 ） - Case 2：某些约束可能有 优先级 Priority
加权约束违反之和 Weighted sum of the constraint violation
- 当约束有优先级或量纲不同，使用 加权和 Weighted sum 来综合违反程度。
惩罚函数法 Penalty function method
将受约束问题：
转化为带惩罚项的无约束问题（有限惩罚系数下通常是近似处理，而不是严格等价）：
其中 惩罚函数 Penalty function：
是 惩罚系数 Penalty coefficient（标量 scalar，例如 - 约束违反越多，惩罚项越大。
- 当满足约束时（
，对目标函数无影响。
如何确定惩罚系数
一种 经验方法 Empirical method：
- Step 1：估计一个可容忍的 预期可接受违反 Intended acceptable violation
- Step 2：估计一个期望获得的 期望最优目标值 Expected optimal objective value
- Step 3：选择
，使得 的 倍：
惩罚函数法示例 Penalty function example
给定：
若取
多个约束 Multiple constraints
原问题：
Step 1：统一约束方向 Unify constraints（例如全转成
Step 2：用惩罚函数法并入目标 Integrate constraints：
Step 3：分别确定
如果是最大化 What if maximization?
只需对目标取负，把 最大化 Maximization 转成 最小化 Minimization，其余处理同前。
惩罚函数法是否遵循排序原则？
排序原则（回顾）：可行解优于不可行解 → 两个可行解比目标值 → 两个不可行解比违反程度。
结论：如果惩罚系数
例子：背包问题 Knapsack Problem
问题设置 Problem setup
五个物品（价值 value / 重量 weight / 体积 volume）：
| 物品 | 价值 | 重量 | 体积 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 |
背包容量 Capacity：
决策变量 Decision variable：
最大化总价值：
约束：
Step 1：转为最小化 Convert to minimization
Step 2：统一约束方向 Unify constraints
本例两个约束已经是
Step 3：惩罚函数并入目标 Integrate constraints
给定（示例选择）：
则：
多目标优化 Multiobjective Optimization
问题定义 Problem definition
是 决策变量 decision variables， 是维度 是 决策空间 decision space 个 目标 objectives 通常彼此冲突
示例：汽车设计 Example: automobile design
能源消耗（每百英里）应尽可能低，制造成本应尽可能低。两者相互冲突：低能耗依赖于更先进的动力单元设计，这会增加制造费用。
支配 Dominance
在任何目标上都不比 差 至少在一个目标上严格优于
对于任意两个解
支配图解 Illustration
- B 支配 A
- B 和 C 不可比较，A 和 C 也是如此
帕累托前沿 Pareto Front
帕累托前沿 PF：帕累托最优解在目标空间中的函数值集合。
帕累托集 PS：所有帕累托最优解的集合（决策空间的子集）。
帕累托最优解：不被任何其他解支配的解。一个理性的决策者不会选择非帕累托最优解。
帕累托前沿的不同形状：凸、凹、不连续、既非凸也非凹。
多目标进化算法 MOEAs
基于种群的迭代搜索 Population-based iterative search
简单 EA 的一次迭代：
- 第
代种群 → 选择 Selection → 父代集合 - 交叉 Crossover / 变异 Mutation
- 第
MOEA 的目标：生成有限数量的均匀分布的帕累托最优解，逼近 PF。
MOEA 分类
| 类型 | 代表算法 | 思路 |
|---|---|---|
| 基于分解 Decomposition | MOEA/D | 将 MOP 分解为多个单目标子问题，协同求解 |
| 基于支配 Dominance | NSGA-II | 基于帕累托支配关系和目标空间距离迭代选择 |
| 基于指标 Indicator | IBEA | 用超体积等指标评估解集质量，迭代选择 |
MOEA/D 的优势
- 小种群下具有良好的分布性和高优化质量
- 由于仿真成本，种群规模通常受限；分解思想有助于获得更均匀的最终解分布
- 在许多小种群场景下，MOEA/D 可能比 NSGA-II 更容易保持较好的分布性，但具体性能仍取决于问题和参数设置
MOEA/D：分解 + 协同
分解 Decomposition：将逼近 PF 的任务分解为
协同 Collaboration：
每个子问题的输入：分解函数
分解方法 Decomposition methods
加权和法 Weighted sum approach
适用于凸 PF。
切比雪夫法 Tchebycheff approach
其中
邻域协同 Neighborhood collaboration
- 如果两个子问题的权重向量相近，则互为邻居
- 相邻子问题目标函数相似，最优解也大概率相似
交叉示例：子问题当前最优解 [x1,...,x9] 与邻居最优解 [y1,...,y9] 交叉 → [x1,x2,x3,y4,y5,y6,y7,x8,x9]
MOEA/D 整体流程
每一代，每个子问题执行：
- 交配池选择：获取邻居的当前解（协同）
- 繁殖：交叉 + 变异生成新解
- 替换：若新解更优则替换旧解，并传递给部分邻居