非线性规划中的遗传算法基础题
字数 2567 2025-10-26 09:00:51

非线性规划中的遗传算法基础题

题目描述
考虑一个简单的非线性约束优化问题：
最小化 \(f(x) = (x_1 - 2)^2 + (x_2 - 1)^2\)
满足约束：
\(g_1(x) = x_1 + x_2 - 2 \leq 0\)
\(g_2(x) = x_1^2 - x_2 \leq 0\)
其中 \(x = (x_1, x_2)\) 是二维决策变量。

解题过程循序渐进讲解

遗传算法是一种模拟自然进化过程的元启发式优化算法。它不依赖于梯度信息，适用于处理复杂、非凸、不可微的优化问题。其核心流程包括编码、初始化、选择、交叉、变异和适应度评估。

第一步：编码与初始化

  1. 编码：将连续变量 \(x_1\) 和 \(x_2\) 编码为二进制字符串（染色体）。假设每个变量的定义域为 \([-5, 5]\)，我们使用10位二进制数表示一个变量，精度为 \((5-(-5)) / (2^{10}-1) \approx 0.01\)。一个染色体（个体）由20位二进制数组成，前10位代表 \(x_1\)，后10位代表 \(x_2\)。

    • 例如，二进制串 0000000000 0000000000 解码为 \(x_1 = -5, x_2 = -5\)。
    • 解码公式：\(x = lower + \frac{(upper - lower)}{(2^L - 1)} \times decimal\_value\)，其中 \(L\) 是二进制串长度（10），\(decimal\_value\) 是二进制串对应的十进制整数。

  2. 初始化种群：随机生成 \(N\) 个这样的20位二进制字符串，构成初始种群。设种群大小 \(N = 50\)。

第二步：适应度函数设计
遗传算法通常求解最大化问题。由于原问题是最小化 \(f(x)\)，我们需要将其转换为适应度函数 \(Fitness(x)\)。同时，必须处理约束条件。这里采用罚函数法将约束问题转化为无约束问题。

  1. 定义罚函数：\(Penalty(x) = \alpha \times [max(0, g_1(x))^2 + max(0, g_2(x))^2]\)，其中 \(\alpha\) 是罚因子（设 \(\alpha = 100\)），这是一个较大的正数，用于惩罚违反约束的个体。
  2. 定义适应度函数：\(Fitness(x) = -[f(x) + Penalty(x)]\)。
    • 对于可行解（满足所有约束），\(Penalty(x) = 0\)，\(Fitness(x) = -f(x)\)。因为 \(f(x) \geq 0\)，所以 \(-f(x) \leq 0\)。我们的目标是使适应度越大越好，即 \(-f(x)\) 越大越好，这等价于 \(f(x)\) 越小越好。
    • 对于不可行解，\(Penalty(x) > 0\)，会显著降低其适应度，使其在进化中被淘汰的概率增大。

第三步：选择操作
选择操作的目的是从当前种群中选出适应性强的个体，作为父代进行繁殖。这里采用轮盘赌选择法。

  1. 计算每个个体 \(i\) 的适应度 \(F_i\)。
  2. 计算每个个体被选中的概率：\(p_i = \frac{F_i - F_{min}}{\sum_{j=1}^{N}(F_j - F_{min})}\)。这里减去种群最小适应度 \(F_{min}\) 是为了避免负的适应度值影响概率计算。如果所有适应度都为非负，可直接用 \(p_i = F_i / \sum F_j\)。
  3. 计算累积概率 \(q_i = \sum_{j=1}^{i} p_j\)。
  4. 生成一个在 \([0, 1]\) 均匀分布的随机数 \(r\)。
  5. 选择第一个满足 \(q_i \geq r\) 的个体。
  6. 重复步骤4和5共 \(N\) 次，选出 \(N\) 个父代个体（允许重复选择，即适应度高的个体可能被选中多次）。

第四步：交叉操作
交叉操作模拟生物杂交，是产生新个体的主要方法。这里采用单点交叉。

  1. 将上一步选出的 \(N\) 个父代个体随机两两配对。
  2. 对每一对父代染色体，以预设的交叉概率 \(p_c\)（设 \(p_c = 0.8\)）决定是否进行交叉。
  3. 如果进行交叉，随机选择一个交叉点（1到19之间的整数）。将两条染色体在交叉点处切断，并交换交叉点之后的部分，生成两条新的子代染色体。
    • 例如，父代1: 0101 | 1010，父代2: 1100 | 0101，交叉点在4。子代1: 0101 0101，子代2: 1100 1010。
  4. 如果不进行交叉，则子代直接复制父代。

第五步：变异操作
变异操作以很小的概率改变基因，引入种群多样性，有助于跳出局部最优。这里采用基本位变异。

  1. 对上一步得到的所有子代染色体，遍历其上的每一个二进制位（基因）。
  2. 对每一个基因，以预设的变异概率 \(p_m\)（设 \(p_m = 0.01\)）决定是否变异。
  3. 如果发生变异，则将该基因位取反（0变1，或1变0）。

第六步：新一代种群与终止条件

  1. 经过选择、交叉、变异后，得到的新个体集合构成新一代种群。
  2. 终止条件判断：重复步骤二到五，构成一次迭代（一代）。常见的终止条件包括：
    • 达到最大迭代次数（例如，500代）。
    • 连续多代最优个体的适应度不再显著提高。
    • 找到了满足精度要求的解。
  3. 当满足终止条件时，算法停止。将历代种群中适应度最高的个体解码，得到的最优解 \(x^*\) 即为算法的近似解。

算法总结
遗传算法通过模拟“初始化种群 -> 评估适应度 -> 选择 -> 交叉 -> 变异”的循环过程，使种群朝着适应度更高的方向进化。对于本例，通过多次迭代，算法有望找到一个位于可行域内且使目标函数 \(f(x)\) 接近最小的点。理论最优解可通过其他方法验证，大约在 \(x^* \approx (1.0, 1.0)\) 附近，此时 \(f(x^*) \approx 1.0\)。遗传算法的优势在于其全局搜索能力，但参数（如种群大小、交叉率、变异率）的选择对性能影响较大，且收敛速度可能较慢。

非线性规划中的遗传算法基础题 题目描述 考虑一个简单的非线性约束优化问题： 最小化 \( f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \) 满足约束： \( g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0 \) \( g_ 2(x) = x_ 1^2 - x_ 2 \leq 0 \) 其中 \( x = (x_ 1, x_ 2) \) 是二维决策变量。 解题过程循序渐进讲解 遗传算法是一种模拟自然进化过程的元启发式优化算法。它不依赖于梯度信息，适用于处理复杂、非凸、不可微的优化问题。其核心流程包括编码、初始化、选择、交叉、变异和适应度评估。 第一步：编码与初始化 编码 ：将连续变量 \(x_ 1\) 和 \(x_ 2\) 编码为二进制字符串（染色体）。假设每个变量的定义域为 \([ -5, 5]\)，我们使用10位二进制数表示一个变量，精度为 \((5-(-5)) / (2^{10}-1) \approx 0.01\)。一个染色体（个体）由20位二进制数组成，前10位代表 \(x_ 1\)，后10位代表 \(x_ 2\)。 例如，二进制串 0000000000 0000000000 解码为 \(x_ 1 = -5, x_ 2 = -5\)。 解码公式：\(x = lower + \frac{(upper - lower)}{(2^L - 1)} \times decimal\_value\)，其中 \(L\) 是二进制串长度（10），\(decimal\_value\) 是二进制串对应的十进制整数。 初始化种群 ：随机生成 \(N\) 个这样的20位二进制字符串，构成初始种群。设种群大小 \(N = 50\)。 第二步：适应度函数设计 遗传算法通常求解最大化问题。由于原问题是最小化 \(f(x)\)，我们需要将其转换为适应度函数 \(Fitness(x)\)。同时，必须处理约束条件。这里采用 罚函数法 将约束问题转化为无约束问题。 定义罚函数：\(Penalty(x) = \alpha \times [ max(0, g_ 1(x))^2 + max(0, g_ 2(x))^2 ]\)，其中 \(\alpha\) 是罚因子（设 \(\alpha = 100\)），这是一个较大的正数，用于惩罚违反约束的个体。 定义适应度函数：\(Fitness(x) = -[ f(x) + Penalty(x) ]\)。 对于可行解（满足所有约束），\(Penalty(x) = 0\)，\(Fitness(x) = -f(x)\)。因为 \(f(x) \geq 0\)，所以 \(-f(x) \leq 0\)。我们的目标是使适应度越大越好，即 \(-f(x)\) 越大越好，这等价于 \(f(x)\) 越小越好。 对于不可行解，\(Penalty(x) > 0\)，会显著降低其适应度，使其在进化中被淘汰的概率增大。 第三步：选择操作 选择操作的目的是从当前种群中选出适应性强的个体，作为父代进行繁殖。这里采用 轮盘赌选择法 。 计算每个个体 \(i\) 的适应度 \(F_ i\)。 计算每个个体被选中的概率：\(p_ i = \frac{F_ i - F_ {min}}{\sum_ {j=1}^{N}(F_ j - F_ {min})}\)。这里减去种群最小适应度 \(F_ {min}\) 是为了避免负的适应度值影响概率计算。如果所有适应度都为非负，可直接用 \(p_ i = F_ i / \sum F_ j\)。 计算累积概率 \(q_ i = \sum_ {j=1}^{i} p_ j\)。 生成一个在 \([ 0, 1 ]\) 均匀分布的随机数 \(r\)。 选择第一个满足 \(q_ i \geq r\) 的个体。 重复步骤4和5共 \(N\) 次，选出 \(N\) 个父代个体（允许重复选择，即适应度高的个体可能被选中多次）。 第四步：交叉操作 交叉操作模拟生物杂交，是产生新个体的主要方法。这里采用 单点交叉 。 将上一步选出的 \(N\) 个父代个体随机两两配对。 对每一对父代染色体，以预设的交叉概率 \(p_ c\)（设 \(p_ c = 0.8\)）决定是否进行交叉。 如果进行交叉，随机选择一个交叉点（1到19之间的整数）。将两条染色体在交叉点处切断，并交换交叉点之后的部分，生成两条新的子代染色体。 例如，父代1: 0101 | 1010 ，父代2: 1100 | 0101 ，交叉点在4。子代1: 0101 0101 ，子代2: 1100 1010 。 如果不进行交叉，则子代直接复制父代。 第五步：变异操作 变异操作以很小的概率改变基因，引入种群多样性，有助于跳出局部最优。这里采用 基本位变异 。 对上一步得到的所有子代染色体，遍历其上的每一个二进制位（基因）。 对每一个基因，以预设的变异概率 \(p_ m\)（设 \(p_ m = 0.01\)）决定是否变异。 如果发生变异，则将该基因位取反（0变1，或1变0）。 第六步：新一代种群与终止条件 经过选择、交叉、变异后，得到的新个体集合构成新一代种群。 终止条件判断 ：重复步骤二到五，构成一次迭代（一代）。常见的终止条件包括： 达到最大迭代次数（例如，500代）。 连续多代最优个体的适应度不再显著提高。 找到了满足精度要求的解。 当满足终止条件时，算法停止。将历代种群中适应度最高的个体解码，得到的最优解 \(x^* \) 即为算法的近似解。 算法总结 遗传算法通过模拟“初始化种群 -> 评估适应度 -> 选择 -> 交叉 -> 变异”的循环过程，使种群朝着适应度更高的方向进化。对于本例，通过多次迭代，算法有望找到一个位于可行域内且使目标函数 \(f(x)\) 接近最小的点。理论最优解可通过其他方法验证，大约在 \(x^* \approx (1.0, 1.0)\) 附近，此时 \(f(x^* ) \approx 1.0\)。遗传算法的优势在于其全局搜索能力，但参数（如种群大小、交叉率、变异率）的选择对性能影响较大，且收敛速度可能较慢。