多蚁群算法信息交换与表面基DNA算法解决符号行列式展开问题

### 多蚁群算法信息交换与表面基DNA算法解决符号行列式展开问题 #### 多蚁群算法中的信息交换 在多蚁群算法里，信息交换是一个关键的研究点。研究了不同的信息交换方法，发现具有多个蚁群且信息交换量不过多的蚁群算法能够有效地进行并行化处理。而且，当蚁群间的信息交换量不过多时，甚至可以提高解决方案的质量。 下面是局部最优解循环交换的相关数据表格： | | l = 5 | l = 10 | l = 50 | | --- | --- | --- | --- | | N = 5 | 642.30 | 638.90 | 637.10 | | N = 10 | 642.90 | 638.55 | 637.10 | | N = 20 | 639.35 | 638.20 | 640.45 | 从这些数据可以看出，不同的迁移间隔（l）和蚁群数量（N）组合下，局部最优解的数值有所不同。 另外，还对不同迁移间隔下的矩阵差异（δ）和平均替代方案数量（D）进行了研究，分别给出了迁移间隔为10和50时的相关图像。 在信息交换方式方面，相较于频繁且在所有蚁群间交换局部最优解，更好的方式是仅在有向环中与相邻蚁群进行局部最优解的交换，并且交换频率不宜过高。 以下是不同蚁群设置下的最佳找到解的情况： - 1个包含100只蚂蚁的蚁群 - 5个包含20只蚂蚁的蚁群 - 10个包含10只蚂蚁的蚁群 - 20个包含5只蚂蚁的蚁群 通过对比无信息交换和迁移间隔为50的局部最优解循环交换两种情况，可以发现信息交换对算法性能有显著影响。 #### 表面基DNA算法解决符号行列式展开问题 ##### 背景与动机 自Adleman开创性地使用基于DNA的计算机解决哈密顿路径问题（HPP）以来，许多用于解决NP问题的算法被设计出来。然而，大多数算法是基于溶液中的DNA链，需要一些纠错或容错技术来获得良好和正确的结果。 表面基DNA计算技术具有极低的错误率，相较于基于溶液的DNA计算有明显优势，但在DNA计算机算法设计中尚未得到广泛应用。这主要是因为表面基技术存在一定限制，例如当寡核苷酸附着在表面时，由于其不能在附着方向上生长，导致灵活性降低。 为了充分利用表面基DNA计算机低错误率的特性，提出了一种用于解决符号行列式展开问题的表面基DNA计算算法。该问题以其指数级的难度而闻名，甚至比计算仅含数值元素的行列式更具挑战性。 ##### 表面基DNA计算机的操作 - **抽象模型操作** 1. **reset(S)（重置/初始化）**：生成用于后续操作的所有链，集合S中的链可根据需求表示相同或不同的值。 2. **mark(C, S)（标记）**：将集合S中满足约束C的所有链标记出来。若没有给定约束，则标记所有链。 3. **unmark()（取消标记）**：取消所有已标记链的标记。 4. **delete(C)（删除）**：从集合S中移除满足条件C（C为“标记”或“未标记”）的所有链。 5. **append(C, X)（追加）**：将由链段表示的单词X追加到满足约束C的所有链上。C可以定义为标记或未标记的链。 6. **readout(C, S)（读出）**：根据标准C选择集合S中的一个元素。若未给定C，则随机选择一个元素，用于获取预期答案。 - **生物实现操作** 1. **reset(S)（重置/初始化）**：与常见的生物DNA操作不