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

### 遗传算法中多样性对最优性的影响及改进策略 #### 1. 引言 在实际应用中，遗传算法存在一些问题，如过早收敛、参数选择鲁棒性差以及后期收敛速度慢等，这些不足严重限制了其应用范围。为了克服这些缺点，众多科学家致力于改进遗传算法，近年来出现了许多改良算法，但仍未达到理想状态。 #### 2. 相关概念与方法 ##### 2.1 衡量个体差异的方法 在遗传算法中，个体之间的差异主要通过欧几里得距离或汉明距离来衡量。汉明距离是指个体之间不同位的数量，在本文中被用作多样性的度量，因为它与问题无关，并且考虑了二进制空间的独特性质。当种群中某一位的状态保持恒定时，就称该位已经收敛。随着搜索的进行，种群多样性会逐渐下降，当搜索收敛时，种群将不再具有有用的多样性。 ##### 2.2 提出的变异方法 - 相干多样性维护（CDM） - **原理**：该方法通过以下两种方式维护种群多样性： - 故意针对非唯一个体，用“随机移民（RI）”替换它们，“随机移民”是随机生成的个体。 - 确保新的“随机移民”包含种群中其他个体已经收敛的位状态，从而保留位收敛。 - **与RI的区别**：CDM与仅使用RI不同，RI忽略收敛，为交叉操作提供来自整个搜索空间的新样本，而CDM为交叉操作提供来自当前搜索空间的更多样本，因为每一代的搜索空间会通过上一代的收敛而缩小。当搜索空间减小时，CDM比单独使用RI更有益，因为CDM的样本更能代表收敛的搜索空间。 ##### 2.3 变异率 - **确定方式**：CDM和RI的变异率由种群中重复个体的数量决定，这需要比较种群中的所有个体，计算成本为\((2/L)×(N×(N - 1))\)，其中\(L\)是个体的长度，\(N\)是种群中个体的数量。 - **自我调节**：变异率由种群中的多样性量自我调节。当种群多样性降低，组合产生更多相同个体时，变异率会增加。只替换重复个体的好处是不会中断收敛，因为只有当组合产生冗余个体时，才会对组合结果进行处理。不过，这种方法不能保证避免找到的局部最优解。 #### 3. 实验设置与基准函数 ##### 3.1 实验设置 使用无精英策略的排名选择，在两种种群大小（50和100）上进行20代的测试，采用单点和双点交叉。对六种不同形状的基准函数进行测试，包括两个多模态函数、两个单最优函数和两个平坦函数，函数在3到5维上进行测试，每个维度的分辨率为6到12位。对不同的变异方法（CDM、RI、不同概率的标准De - Jong变异和无变异的GA）进行比较，结果取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πx_{i}))\)，\(-32\leq x_{i}\leq32\)，最小值点为\((0, \cdots, 0)\)，\(f(x)_{min}=0\)。 - **Sphere函数**：\(f(x)=\sum_{i = 1}^{n}x_{i}^{2}\)，\(-50\leq x_{i}\leq50\)，最小值点为\((0, \cdots, 0)\)，\(f(x)_{min}=0\)。 - **两个多最优函数**： - **Rastrigin函数**：\(f(x)=10n+\sum_{i = 1}^{n}(x_{i}^{2}-10cos(2πx_{i}))\)，\(-12.5\leq x_{i}\leq12.5\)，最小值点为\((0, \cdots, 0)\)，\(f(x)_{min}=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}\leq100\)，最小值点为\((0, \cdots, 0)\)，\(f(x)_{min}=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}\leq10\)，最小值点为\((0, \cdots, 0)\)，\(f(x)_{min}=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}\leq10\)，最小值点为\((1, \cdots, 1)\)，\