并行算法求解动态旅行商问题与手语表达建模识别研究

### 并行算法求解动态旅行商问题与手语表达建模识别研究 #### 1. 并行CHC算法求解DTSP结果分析 在动态旅行商问题（DTSP）的求解中，为了评估算法的性能，使用了两个指标：平均偏差和最大偏差。设 $F_X^t(p)$ 表示在时间步 $t$ 时，使用算法 $X$ 对个体 $p \in P_t$ 的评估值，$F_{ref}^t$ 是第 $t$ 个参考算法找到的最佳个体的评估值。 - **平均偏差**：计算公式为 $\frac{\sum_{i = 1}^{R} \left[\min_{p \in P_t} \left(F_X^t(p) - F_{ref}^t\right)\right]}{R \cdot F_{ref}^t} \cdot 100\%$ 。 - **最大偏差**：计算公式为 $\max_{1 \leq i \leq R} \left[\frac{\min_{p \in P_t} \left(F_X^t(p) - F_{ref}^t\right)}{F_{ref}^t} \cdot 100\%\right]$ ，其中 $R$ 是运行次数。 在 $R = 10$ 次运行的情况下，不同算法的平均偏差（avg dev）、最大偏差（max dev）以及平均计算时间如下表所示： | 算法 | 平均偏差 | 最大偏差 | 平均计算时间 | | --- | --- | --- | --- | | CHC + 2 - opt | 最优 | 最优 | 慢 | | P - CHC + 2 - opt/1 | 稍差 | 稍差 | 较快 | | PS - CHC + 2 - opt/2 | 较优 | 较优 | 极快 | 从表中可以看出，CHC 算法结合 2 - opt 局部搜索在所有测试算法中表现最好，但计算速度非常慢。而其并行版本 P - CHC + 2 - opt/1 表现稍差，推测可能是由于 PCHC 算法中使用的伪随机数生成器 cuRAND 导致的。另外，PS - CHC 结合 2 - opt/2 局部搜索在所有测试用例中都能在较短的计算时间内得到令人满意的结果，与 CHC + 2 - opt 相比，速度提升了 6 倍到 60 倍。不过，当 $\delta \in \{2, 3\}$ 时，2 - opt/$\delta$ 虽然能带来更高的速度提升，但得到的最短路径质量一般。 下面是不同算法求解 DTSP 的流程 mermaid 图： ```mermaid graph LR A[开始] --> B[初始化种群] B --> C{选择算法} C -->|CHC + 2 - opt| D[进行 CHC 迭代和 2 - opt 局部搜索] C -->|P - CHC + 2 - opt/1| E[并行进行 CHC 迭代和 2 - opt/1 局部搜索] C -->|PS - CHC + 2 - opt/2| F[并行进行 PS - CHC 迭代和 2 - opt/2 局部搜索] D --> G[评估结果] E --> G F --> G G --> H{是否满足终止条件} H -->|否| B H -->|是| I[输出结果] I --> J[结束] ``` #### 2. 手语表达建模与识别背景 在社会交往中，听力损失等沟通障碍是一个重要问题。因此，研究基于视觉的自动手语识别系统，将手势转换为口语或书面语言具有重要意义。传统的手语识别系统通常用一个单词模型表示一个手势，这种方法在小词汇量的情况下表现良好，但随着词汇量的增加，训练语料和训练复杂度也会相应增加。为了解决这个问题，需要使用比单词更小的单元（亚单元）来建模手语表达，这类似于用音素建模语音。 #### 3. 波兰手语（PSL）特征分析 PSL 手势分为静态和动态，大多是双手操作