搜索请求语义扩展与动态旅行商问题并行算法研究

### 搜索请求语义扩展与动态旅行商问题并行算法研究 #### 1. 搜索请求语义扩展的AOS引擎 在处理搜索请求时，为了实现高效的搜索，设计了一种名为AOS Engine（面向方面的搜索引擎）的程序综合体。其架构的核心思想是组件的最大可用性、独立性以及可独立使用性。 搜索请求的处理过程如下： ```mermaid graph LR A[搜索请求] --> B[子系统1：请求分析器] B --> C[数据结构1：请求分析结果] C --> D[子系统2：请求扩展组件] D --> E[数据结构2：转换后的请求集合] E --> F[子系统3：与搜索系统交互组件] F --> G[数据结构3：检索到的文档集合] G --> H[子系统4：排序组件] H --> I[数据结构4：检索到的相关文档集合] ``` - **子系统1（请求分析器）**：与词干提取组件和词汇表交互，分析请求的类型和感兴趣的对象。使用词干提取组件将单词转换为词干形式，输出是输入请求的扩展形式，包含请求类型、感兴趣的对象以及可能的额外感兴趣对象（如时间间隔）。 - **子系统2（请求扩展组件）**：与目标库、集合变化知识库、语言数据库（LDB）和面向方面的知识库（AOKB）交互，生成转换后的请求集合。 - **子系统3（与搜索系统交互组件）**：连接到特定的句法搜索系统（基于关键词搜索），将生成的搜索请求发送给它，并聚合接收到的文档。 - **子系统4（排序组件）**：与LDB和AOKB交互，对检索到的文档进行排序。 AOS Engine由三个主要子系统组成：AOS引擎系统、LDB和AOKB。所有与数据库和知识库交互的子系统都使用对象关系映射系统（ORM）和数据库连接池（DBCP），以减少设计 - 实现周期的时间和创建新数据库连接的时间，从而减少数据访问时间。 为了实现该架构，选择了Java SE 6作为编程环境。对AOS Engine的代码进行了整体测试，所有组件和子系统都能正确交互。使用JUnit测试库以白盒自动方式测试查找输入搜索请求类型和感兴趣对象的算法，形成了包含300多个不同类型唯一搜索请求的集合。大多数情况下，使用构建的知识库获得详细信息的检索文档数量超过50%。 #### 2. 动态旅行商问题及相关算法 动态优化问题（DOPs）包含目标函数的时间相关变化，常用于建模现实生活中的关键过程，如车辆路由、负载平衡和资金投资等。旅行商问题（TSP）是一个常见的NP难组合问题，其动态版本（DTSP）更难解决，因为它引入了时变环境变化。 ##### 2.1 动态旅行商问题定义 经典TSP可描述为在完全加权图中寻找哈密顿回路的问题。设图$G = (U, V)$，其中$U$是边的集合，$V$是$n > 0$个顶点的集合。对于每对$(v_1, v_2) \in U$，$\delta(v_1, v_2) > 0$表示从顶点$v_1$到$v_2$的距离。若$(v_1, v_2) = (v_2, v_1)$，则TSP为对称的，否则为不对称的。目标是找到访问所有$n$个顶点恰好一次的最短路径，即一个排列$\sigma : \{1, ..., n\} \to \{1, ..., n\}$，使下式最小化： $$\sum_{i = 1}^{n - 1} \delta(v_{\sigma(i)}, v_{\sigma(i + 1)}) + \delta(v_{\sigma(n)}, v_{\sigma(1)})$$ 在DTSP中，考虑了时间域内的非确定性环境变化，如添加新顶点、删除现有顶点和修改$\delta(\cdot, \cdot)$的值。 ##### 2.2 计算统一设备架构（CUDA） CUDA的计算平台由顺序平台（标准处理器）和并行平台（多核图形处理器）组成。顺序平台执行单线程主流程序，并在并行平台上调用多线程子程序。并行平台由多个多线程流式多处理器组成，以单指令多线程（SIMT）架构运行，允许进一步并行化。 当调用多线程子程序时，计算平台将所有线程分成多个块并分配给多处理器，多处理器将每个块的线程分成32个线程的warp并依次处理。实验在配备Intel Core i7 950处理器和nVidia GeForce GTX 580显卡的计算平台上进行，硬件平台规格如下表所示： | 参数 | 值 | | ---- | ---- | | 多线程流式多处理器数量 | 16 | | 每个多处理器的逻辑核心数 | 32 | | 总逻辑核心数 | 512 | | 每个多处理器的寄存器数量 | 16384 | | 每个块的最大线程数 | 512 | | 每个warp的线程数 | 32 | | 每个多处理器的共享内存 | 64 kB | | 常量内存 | 64 kB | | 每个线程的本地内存 | 16 kB | | 每个多处理器的最大活动块数 | 8 | | 每个多处理器的最大活动warp数 | 32 | | 每个多处理器的最大活动线程数 | 1024 | 在实验中，使用cuRAND库在多个线程中独立生成随机数。 ##### 2.3 算法设计 提出的算法是基于CUDA的并行CHC算法的扩展，用于解决DTSP。 - **保持种群多样性**：DTSP的进化方法需要保持种群的多样性。CHC通过两种机制实现：一是只允许根据给定度量足够远的个体交配；二是反复重新初始化种群，仅保留一个个体（具有最高适应度）不变。 - **距离计算**：对于个体$p = (p_1, p_2, ..., p_L) \in P_t$，定义函数$\phi_p(i)$确定旅行商路径上的下一个顶点： $$\phi_p(i) = \begin{cases} p_{i + 1}, & i + 1 \leq L \\ p_1, & \text{otherwise} \end{cases}$$ 个体对$(l, r) \in P_t$的相互距离$\Delta(l, r)$计算如下： $$\Delta(l, r) = \#\{1 \leq i \leq L; \phi_l(i) = \phi_r(i)\}$$ 设$0 \leq d \leq L$为交配距离阈值（初始设置为固定值$d_{start}$）。 - **算法伪代码**： ```plaintext Algorithm 1. Modified CHC algorithm with parameters: r – divergence rate (0 < r < 1), L – chromosome length (L ∈ N), dstart – initial difference threshold (0 ≤ dstart ≤ L) d = dstart P1 = InitPopulation() Evaluate(P1) while not termination condition do if the function has changed then Pt = ReinitializeKernel(Pt, r) end if Pt+1 = EvolutionaryKernel(Pt, d) if Pt+1 = Pt then d = max(0, d - 1) else d = dstart end if end while ``` ```plaintext Algorithm 2. ReinitializeKernel(Pt, r) where: Pt – population at time step t > 1, r – divergence rate (0 < r < 1), L – chromosome length, N – population size (L, N ∈ N) pbest = BestIndividual(Pt) in parallel for all p ∈ Pt \ {pbest} do in parallel p = LocalClone(pbest) ```