并行协同进化元启发式算法：CO-SEARCH的原理与应用

### 并行协同进化元启发式算法：CO - SEARCH的原理与应用 #### 1. 引言 传统上，并行计算常被视为提高计算能力、同时运行多个任务的手段。但近年来出现了一种不同的方法，其目标不再是单纯加速处理，实现方式可以是顺序或并行的，重点在于活动的协同进化。本文提出的元启发式算法结合了并行计算的两大优势：计算能力和协同进化，旨在设计一种稳健且高效的搜索方法，让具有互补行为的基本智能体协同进化。 在设计高效启发式搜索策略时，需要平衡两个相反的标准：搜索空间的探索（多样化任务）和已找到解决方案的利用（强化任务）。有些算法更适合多样化，而有些则更擅长强化。为了设计出平衡的元启发式算法，我们提出让搜索智能体（局部搜索）、多样化智能体和强化智能体协同进化，这三个智能体通过名为自适应内存的被动协调器交换信息。 #### 2. 二次分配问题（QAP） 二次分配问题（QAP）是一个NP难问题，精确算法（如分支限界法）仅适用于小规模实例（n < 25）。因此，文献中提出了许多启发式算法。 QAP问题描述如下：给定实例规模n、n个对象集合O = {O₁, O₂, ... , Oₙ}、n个位置集合L = {L₁, L₂, ... , Lₙ}、流量矩阵c（其中每个元素Cᵢⱼ表示对象Oᵢ和Oⱼ之间的流量成本）、距离矩阵d（其中每个元素dₖₗ表示位置Lₖ和Lₗ之间的距离），找到一个对象 - 位置的双射映射U : O → L，使函数ψ最小化： \[ \psi(U)=\sum_{i = 1}^{n}\sum_{j = 1}^{n}C_{ij}\cdot d_{U(i)U(j)} \] 为表示QAP的解，我们使用基于n个整数排列的表示方法：u = (u₁, u₂, ... , uₙ)，其中uᵢ = U(i)表示对象Oᵢ的位置。两个排列之间的距离可以根据QAP常用的对换操作（swap）来定义，u和v之间的距离dist(u, v)是从u转换到v所需的最小对换操作次数。 #### 3. CO - SEARCH：并行协同进化元启发式算法 在CO - SEARCH（协同进化搜索）元启发式算法中，三个启发式智能体同时运行，并通过自适应内存（AM）交换信息。主要搜索智能体选择禁忌搜索（TS），因为它在解的质量方面是目前最有效的局部搜索方法之一。多样化任务由遗传算法（GA）负责，因其遗传操作在探索任务上非常强大。强化任务由踢操作符（KO）处理，它是一种对解进行或多或少扰乱的简单方法。 ##### 3.1 MTS：搜索智能体 我们提出的搜索智能体是多重禁忌搜索（MTS）。TS方法由Glover提出，有时TS会采用一些技术来鼓励搜索空间中某个区域的利用或新区域的探索。在本研究中，由于其他智能体的存在，TS不需要任何高级的多样化或强化技术。 我们使用多个独立的TS任务并行运行，且不同TS之间没有直接合作。选择多个短TS运行而非长运行，是因为TS不需要从初始解进化到很远的区域。在CO - SEARCH中，TS扩展了频率内存，用于存储搜索过程中访问的所有解的信息。频率内存存储搜索过程中某些事件的发生频率。对于解决QAP，考虑的事件为“对象Oᵢ被分配到位置Lⱼ”。频率内存是一个n×n的矩阵，通过累加TS搜索过程中访问的所有解（编码为矩阵）来计算。在这个频率矩阵中，任何列或行的和等于TS搜索的长度（迭代次数）。在开始TS搜索之前，频率内存初始化为零，搜索过程中通过添加访问的解进行更新。TS搜索结束后，频率内存提供了TS访问过的区域信息，然后TS将频率内存和其找到的最佳解发送到自适应内存。 ##### 3.2 自适应内存 自适应内存（AM）是CO - SEARCH协同进化元启发式算法的协调器。运行时，AM维护MTS执行的搜索历史。AM由三个主要部分组成：全局频率内存、TS的初始解集合和精英解集合。 全局频率内存和初始解集合用于GA的多样化任务，全局频率内存是TS产生的局部频率内存的总和。强化任务使用精英解集合，该集合收集TS搜索找到的最佳解，存储了搜索空间中已探索区域内高质量区域的信息。精英解的数量是该方法的一个参数。当一个TS搜索结束时，它将找到的最佳解发送到自适应内存。如果精英解集合未满，则添加该解；否则，如果新解比最差的精英解更好，则添加新解并丢弃最差的解。如果精英解集合中已有与新解质量相同的解，则不进行替换。根据此规则，保证了精英解的多样性，自适应内存代表了更多有前景的解。 下面是自适应内存的工作流程mermaid图： ```mermaid graph TD; A[TS搜索结束] --> B{精英解集合是否满}; B -- 否 --> C[添加新解到精英解集合]; B -- 是 --> D{新解是否比最差精英解好}; D -- 是 --> E[添加新解，丢弃最差解]; D -- 否 --> F[不替换]; ``` ##### 3.3 多样化遗传算法（GA） CO - SEARCH中使用的多样化智能体是遗传算法。遗传算法基于生物的自然进化，在协同混合算法中，GA的目标是根据AM在未探索区域生成个体。GA在多样化任务上本质上很高效，因为其遗传操作能生成分散的解。根据经验，GA也能适应动态环境，因为在混合算法运行时，GA所参考的AM会被TS不断更新。当GA进化出