细胞进化算法与人工自复制结构研究

### 细胞进化算法与人工自复制结构研究 #### 1. 细胞进化算法性能对比 细胞进化算法（CEAs）在解决离散优化问题时，同步算法和异步算法展现出不同的性能特点。 在平均最终适应度和找到解决方案的概率方面，除了ECC问题，异步算法在平均最终适应度上略有优势，在找到最优解的概率上优势明显。 可以将问题分为两类：一类是所有方法都能达到100%命中率的问题，这类问题适合直接使用直连细胞遗传算法（CGAs）；另一类是无法达到100%命中率的问题，这类问题可能需要借助局部搜索等方法。 为了总结大量结果并得出有用结论，按照平均最佳最终解、成功所需的平均代数和命中率这三个不同指标对算法进行了最终排名，具体排名如下表所示： | 指标 | 排名情况 | | --- | --- | | 平均解 | 1. Narrow<br>2. Rectangular<br>2. FRS<br>3. FRS<br>4. NRS<br>5. UC<br>5. LS<br>6. Square<br>7. Square | | 平均代数 | 1. NRS<br>2. LS<br>2. FRS<br>2. FRS<br>4. UC<br>5. Rectangular<br>5. UC<br>5. LS<br>7. Narrow | | 命中率 | 1. Narrow<br>2. Rectangular<br>2. FRS<br>4. NRS<br>5. Square<br>5. UC<br>5. LS<br>7. Narrow | 从排名可以看出，在平均最佳最终适应度和命中率标准下，具有“窄”和“矩形”形状的同步算法通常比所有异步算法更准确，尤其是窄种群网格表现突出。而在平均代数方面，异步算法明显优于同步算法，NRS在测试套件中是排名最佳的CGA类型。 总体而言，对于P - PEAKS、ECC和MAXCUT问题，异步算法在数值计算上比同步算法更快，但对于MMDP问题并非如此。在命中率方面，同步算法优于异步算法，这在许多应用中可能是一个重要问题。窄种群结构的探索性特征在大多数情况下似乎允许更精确的搜索。但需要注意的是，这些结果不能直接推广到其他问题或问题类型。 #### 2. 细胞进化算法在实际问题中的应用与改进 虽然细胞进化算法不如其他类型的进化算法受欢迎，但它已成功用于解决现实生活中的困难优化问题。不过，基本的细胞进化算法效率不足以与成熟的问题解决技术竞争。普通的细胞进化算法一旦找到个体的表示方法，就很容易应用于几乎任何问题，但要成功解决复杂的工程问题，需要在算法中融入更多知识。可以通过以下几种方式增强细胞进化算法： - **模因和混合算法**：将基于种群的方法与局部搜索方法相结合，或者在启发式搜索中加入特定问题的知识。在细胞进化算法中，通常会在进化场景中补充一种在种群中最佳成员中搜索局部最优解的技术。 - **元启发式算法**：一种通用的问题解决技术，其中高级启发式方法指导或控制底层特定问题的启发式方法。这些技术与模因算法有一定重叠，并且没有普遍接受的定义。 - **多目标优化**：在需要同时考虑多个目标（而不仅仅是最大化或最小化特定适应度函数）的约束下进行优化。由于这些目标通常相互矛盾，因此需要考虑资源分配的权衡。许多现实世界的问题都属于这种类型。 下面介绍两个细胞进化算法成功应用的实际问题： - **车辆路径规划问题（VRP）**：该问题包含大量可视为多个旅行商问题的子问题，是NP难问题，在工业应用中非常重要，找到更好的解决方案意味着大量资源的节省。最近，基于细胞进化算法的方法能够超越以往的结果。具体操作步骤如下： - 结合标准的细胞进化算法框架，使用专门的路线和交付表示方法。 - 采用针对该表示方法定制的交叉和变异算子。 - 在应用变异算子后添加局部搜索阶段，应用特殊的旅行算子（2 - opt和1 - exchange）以进一步改进解决方案。 - 将该方法应用于VRP的多个实例，找到了许多目前为止的最佳解决方案，其他情况下找到的解决方案也与已知的最佳解决方案相等或非常接近。 - **移动自组织网络（MANET）中的信息扩散问题**：MANET是一种无线网络，由移动路由器和相关主机通过无线链路连接而成，网络拓扑结构可能快速且不可预测地变化。研究人员应用多目标细胞进化算法来寻找在大都市地区MANET中进行信息传输和扩散的良好策略，目标通常包括最小化扩散过程的持续时间