含元启发式算子的进化算法与并行GNG算法研究

### 含元启发式算子的进化算法与并行GNG算法研究 在当今的科技领域，数据处理和优化问题一直是研究的热点。对于时间依赖定向问题（TDOP），一种含元启发式算子的进化算法展现出了良好的性能。同时，在处理高维大数据集的聚类问题时，并行化的Growing Neural Gas（GNG）算法也有着独特的优势。本文将详细介绍这两种算法的实验结果和相关技术。 #### 含元启发式算子的进化算法在TDOP中的应用 1. **实验参数设置** - 实验在配备Intel Core i7 3.5 GHz处理器的计算机上进行，算法使用C++实现。 - 进化算法的参数设置如下表所示： | Param. | Value | Description | Param. | Value | Description | | --- | --- | --- | --- | --- | --- | | Psize | 100/30 | Population size | mp | 1 | Mutation probab. | | Ng | 5000/1500 | Max. generations number | cp | 1 | Crossover probab. | | Cg | 500/150 | Max. generations number without improvement | dp | 0.01 | Disturb probab. | | mh | 1 | Mutation heuristic coeff. | α | 90 | Max. percentage of infeasible solutions | | ch | 0.8 | Crossover heuristic coeff. | dh | 0.8 | Disturb heuristic coeff. | - 种群大小设置为100或30。Psize = 100源于原始的定向问题（OP）算法，适用于较大网络的计算；Psize = 30则是为了减少较小TDOP实例的执行时间。与代数相关的参数会根据种群大小进行调整，以确保算法能够完全收敛。其余参数通过自动调优过程确定，使用了Parameters ILS元算法进行校准。 2. **测试实例** - TDOP基准实例由Verbeeck等人引入，模拟街道交通情况。这些实例包含7个网络，顶点数量在21 - 102之间，最大旅行时间在5 - 14小时之间，所有路径均从早上7点在节点1出发，结束于最后一个节点N。 - 基准网络分为三类： - **Class I**：包含最小的网络（21 - 32个顶点），是原始的TDOP实例，已由基准作者进行了最优求解。 - **Class II**：包含所有基准网络，经过轻微修改，使得最优结果与静态OP网络相同。 - **Class III**：通过对前两类应用时间离散化得到，用于将作者的算法与Gunawan的元启发式算法进行比较。 3. **实验结果** - 作者在这些实例上测试了进化算法（EVO），并将其与最优解、蚁群元启发式算法（ACS）和Adaptive ILS进行了比较。差距以百分比表示，计算公式为$100 \cdot (1 - \frac{res}{opt})$，其中res是元启发式算法获得的结果（EVO为30次运行的平均值），opt是最优解的利润。执行时间以秒为单位。 - **Class I实例结果**： | N | Tmax | EVO100 Time | EVO100 Gap | EVO30 Time | EVO30 Gap | ACS gap | Opt. result | | --- | --- | --- | --- | --- | --- | --- | --- | | 32 | 5 | 0.8 | 0 | 0.1 | 0 | 0 | 115 | | 32 | 6 | 1.0 | 0 | 0.1 | 0 | 0 | 135 | |... |... |... |... |... |... |... |... | | avg. | - | 1.0 | 0 | 0.1 | 0.1 | 0.8 | 322.5 | - EVO100在所有测试用例中都获得了最优解，平均比ACS好0.8%，最大差距超过4%。EVO30仅比EVO100差0.1%，但速度要快得多，仅在一种情况下比EVO100差超过1.5%。 - **Class II实例结果**： | N | Tmax | EVO100 Time | EVO100 Gap | EVO30 Time | EVO30 Gap | ACS gap | Opt. result | | --- | --- | --- | --- | --- | --- | --- | --- | | 32 | 5 | 0.9 | 0 | 0.1 | 0 | 0 | 135 | | 32 | 6 | 1.0 | 0 | 0.1 | 0 | 0 | 165 | |..