遗传算法多样性对最优性的影响及改进策略

### 遗传算法多样性对最优性的影响及改进策略 #### 1. 遗传算法中的多样性与收敛性 在遗传算法中，个体之间的差异主要通过欧几里得距离或汉明距离来衡量。汉明距离是指个体之间不同位的数量，在本文中被用作多样性的度量，因为它与问题无关，并且考虑了二进制空间的独特性质。当一个位在种群中处于恒定状态时，我们称其已经收敛。在搜索过程中，随着收敛进行，种群的多样性会下降；当搜索收敛时，种群将不再具有有用的多样性。 传统的变异操作以预设概率改变每个位，从而在搜索过程中概率性地中断收敛。动态改变这种收敛中断已被证明可以改善搜索结果。 #### 2. 提出的变异方法 - 连贯多样性维护（CDM） ##### 2.1 相关工作 在遗传算法中，多样性通常是所有个体之间距离度量的平均值。本文使用汉明距离作为多样性度量，因为它独立于问题，并且适用于二进制编码的遗传算法。 当一个位在种群中保持恒定状态时，它就被认为已经收敛。在搜索收敛过程中，种群的多样性会逐渐降低。传统的变异操作会以固定的概率改变每个位，从而在搜索过程中随机中断收敛。动态调整这种收敛中断已被证明可以提高搜索结果。 ##### 2.2 连贯多样性维护（CDM）方法 - **原理**：CDM 方法通过以下两种方式维护种群的多样性： - 有意针对非唯一个体，用“随机移民（RI）”替换它们。“随机移民”是随机生成的个体。 - 确保新的“随机移民”包含种群中其他部分已经收敛的位状态，从而保留位收敛。 - **与 RI 的区别**：RI 忽略收敛，从整个搜索空间提供新的样本给交叉操作；而 CDM 为交叉操作提供当前搜索空间的更多样本，因为每一代的搜索空间会通过上一代的收敛而缩小。当搜索空间显著大于种群大小时，多样化的种群可能会给组合带来更不连贯和不连续的样本。随着搜索空间的缩小，CDM 比仅使用 RI 更有益，因为 CDM 的样本更能代表收敛的搜索空间。 - **创建唯一个体的数量计算**：在长度为 n 的字符串中，通过两个不同个体的组合可以创建的距离为 d 的唯一个体数量可以通过以下组合方程确定： \[N_d = C_n^d = \frac{n!}{d!(n - d)!}\] 其中，\(N_d\) 是距离为 d 的个体数量，D 是个体之间的汉明距离，可通过以下公式计算： \[D = n - \frac{n - d}{2}\] ##### 2.3 变异率 CDM 和 RI 的变异率由种群中重复个体的数量决定。这种方法需要比较种群中的所有个体，计算成本为： \[O(\frac{N(N - 1)}{2}L)\] 其中，L 是个体的长度，N 是种群中的个体数量。 变异率由种群中的多样性自动调节。当种群多样性降低，组合产生更多相同个体时，变异率会增加。仅替换重复个体的好处是不会中断收敛，因为只有当组合产生冗余个体时，组合的结果才会被处理。这确保了收敛和发散在搜索过程中不会相互竞争。 #### 3. 实验设置与基准函数 ##### 3.1 实验设置 使用的遗传算法测试平台采用无精英策略的排名选择，在两种种群大小（50 和 100）上进行了 20 代的测试。测试使用了单点和双点交叉。变异方法在六个具有不同形状的基准函数上进行了测试，包括两个多模态函数、两个单最优函数和两个平坦函数。这些函数在 3 到 5 维上进行测试，每个维度的位分辨率为 6 到 12 位。实验结果是 100 次测试的平均值。 ##### 3.2 基准函数 | 函数类型 | 函数名称 | 函数表达式 | 变量范围 | 最小值位置 | 最小值 | | --- | --- | --- | --- | --- | --- | | 单最优函数 | Ackley 函数 | \(f(x) = 20 + e - 20\exp(-0.2\sqrt{\frac{1}{n}\sum_{i = 1}^{n}x_i^2}) - \exp(\frac{1}{n}\sum_{i = 1}^{n}\cos(2\pi x_i))\) | \(-32 \leq x_i \leq 32\) | \((0, \cdots, 0)\) | \(0\) | | 单最优函数 | Sphere 函数 | \(f(x) = \sum_{i = 1}^{n}x_i^2\) | \(-50 \leq x_i \leq 50\) | \((0, \cdots, 0)\) | \(0\) | | 多最优函数 | Rastrigin 函数 | \(f(x) = 10n + \sum_{i = 1}^{n}(x_i^2 - 10\cos(2\pi x_i))\) | \(-12.5 \leq x_i \leq 12.5\) | \((0, \cdots, 0)\) | \(0\) | | 多最优函数 | Griewank 函数 | \(f(x) = 1 + \frac{1}{4000}\sum_{i = 1}^{n}x_i^2 - \prod_{i = 1}^{n}\cos(\frac{x_i}{\sqrt{i}})\) | \(-100 \leq x_i \leq 100\) | \((0, \cdots, 0)\) | \(0\) | | 平坦最优函数 | Zakharov 函数 | \(f(x) = \sum_{i = 1}^{n}x_i^2 + (\sum_{i = 1}^{n}0.5ix_i)^2 + (\sum_{i = 1}^{n}0.5ix_i)^4\) | \(-10 \leq x_i \leq 10\) | \((0, \cdots, 0)\) | \(0\) | | 平坦最优函数 | Rosenbrock 函数 | \(f(x) = \sum_{i = 1}^{n - 1}[100(x_{i + 1} - x_i^2)^2 + (x_i - 1)^2]\) | \(-10 \leq x_i \leq 10\) | \((1, \cdots, 1)\) | \(0\) | #### 4. 实验结果分析 ##### 4.1 适应度数值结果 以下是不同变异方法在六个基准函数上的平均最终适应度结果： | 函数 | 交叉点/位数 | CDM | RI | 0.001 | 0.002 | 0.005 | 无变异 | | --- | --- | --- | --- | --- | --- | --- | --- | | Ackley 函数 | 单点/6