论文笔记：A Biased Random Key Genetic Algorithm for Solving the Longest Common Square Subsequence Problem_偏置随机键遗传算法

A Biased Random Key Genetic Algorithm for Solving the Longest Common Square Subsequence Problem

论文引言中提到的几种算法

Hunt-Szymanski算法

最坏时间复杂度$O(n^{2}logn)$

问题-LCSqS

最长公共平方子序列（the longest common square subsequence）是最长公共子序列的问题变种，在寻找两个字符串的最长公共子序列（其中字符可以不连续）的同时，要求满足是平方字符串。

平方字符串的定义：$s$= $s_0$+$s_0$=$[s_0{]}^2$

在两个字符序列中，寻找一个公共子序列，并且该公共子序列还可以通过一个分割点分割成两个相同的子序列。

首先明确一点，对于原字符序列中寻找的公共子序列，可以是不连续的，即对原字符序列擦除任意数量的字符可以得到的顺序序列。

对于组合优化问题中，平方子串属于约束，平方子串的长度是目标

论文算法思路

对于输入的字符串，会智能的选择一个合适的分割点，然后将一个字符串分为两份，以输入两个字符串为例：

1. 长字符串会被分成两个字串，两个字符串s_left和s_right
2. s1=s1_left+s1_right；s2=s2_left+s2_right（通过算法可以找到一个合适的分割点：把最长公共串分割到两边）
3. 切割后的子串两两对比，寻找子串中的最长公共子串，会得到四个解集{s1_left&s2_left，s1_left&s2_right，s1_right&s2_left，s1_right&s2_right}（因为算法的分割可以保证两个子串中的最长公共串一样）
4. 对比解集中的所有最长公共子串，找到公共子串，即为解

存在两个关键的算法：

1. BRKGA找到最优的切割点
2. 波束搜索解决产生的LCS问题

主要算法

Beam Search

一种候选前K个最优解的搜索算法（逻辑树形结构）

在第一步选择样本时，选择前K个高概率的搜索样本，然后每个样本继续下一步选择（选择一个），即在第一步选择K个，后续的选择还是1个最高概率样本。

假设，集合中有N个，设置为K，输出序列长/时间步为T。则时间复杂度为$O(KNT)$

BRKGA（Bais Random Keys Genetic Algorithm）

偏置随机关键遗传算法

策略参数

• $p_m$：突变体数量，满足$p_m<p_{Size}-p_e$条件
• $p_e$：精英个体的数量，满足$2p_e<p_{Size}$条件，
• $p_{Size}$：种群的数量
• ${\rho }_e$：在偏随机算法中，继承精英父辈的概率，一般设置大于0.5

精英个体会和突变个体保留到下一代，下一代中剩下的$p_{Size}-p_e-p_m$个个体来自于父代中的亲本交配生成。

解码器

将每个个体的基因解码映射到LCS问题的可行解上

个体优化进入了停止期，表明多个个体在存在多个同样适应度的搜索区域-瓶颈期，缺乏引导搜索，会影响下一步优化性能。为了区分这些个体，引入了第二个目标函数。

1. 优先考虑那些切割点在中心位置附近的个体，$$\sum _{i=0}^n|2\times p_i^v-|s_i||$$，切割点越靠近中心，值越小
2. 更倾向于切割点两边的字符数量之间有更高的平衡（相近的数量），公式存疑
3. 更倾向于考虑哪些拥有更大的LCS长度的切割点的个体，希望且个体中的LCS长度更长

时间复杂度计算

论文中说最好费时间的操作是对于个体的解码操作。

1. greed_transformation，每一维度都需要利用设定好的贪婪信息，每一维度要在O(1)时间内计算，有三种贪婪信息的选择，这个预处理过程的总时间复杂度为O(m)、$O(m\cdot m|\sum |)$、$O(m\cdot n^2)$；分别是直接预设0.5；每个计算整个维度的最平衡的分割位置；每维计算整个维度的最大LCS空间
2. map to cut points，每一维进行计算切割位置，O(m)
3. beam search for LCS problem，

使用了三种测试基准

1. RANDOM 基准测试集:

   来源: 从之前的工作 [33] 中获得，用于评估 RVNS 算法。

   特点: 由均匀随机生成的字符串组成，包括 450 个测试实例和 135 个调整实例。

   字符串长度: n ∈ {100, 500, 1000}

   字符串数量: m ∈ {10, 50, 100, 150, 200}

   字母表大小: |Σ| ∈ {4, 12, 20}

2. NON-RANDOM 基准测试集:
   来源: 新生成的基准测试集，用于测试算法在不同分布的实例上的性能。
   特点: 由非均匀字符串组成，包括 90 个测试实例和 45 个调整实例。
   字符串长度: n ∈ {100, 500, 1000}
   字符串数量: m ∈ {10, 50, 100, 150, 200}
   字符串类型: type ∈ {1, 2}，分别表示不同的模式植入方式。
   字母表大小: 根据字符串长度设置，n = 100 时为 12，n = 500 时为 15，n = 1000 时为 18。

3. BACTERIA 基准测试集:
   来源: 从 [17] 中获得，用于测试算法在真实世界实例上的性能。
   特点: 由细菌 DNA 分子组成，包括 35 个测试实例。
   字符串数量: m ∈ [2, 383]
   字符串长度: 455 ≤ |s_i| ≤ 1847
   字母表大小: |Σ| = 4

策略参数设置

• $p_{Size}$ 种群大小
• $p_e$ 精英数量
• $p_m$ 随机变异数量（变异）
• ${\rho }_e$ 精英和普通交叉的精英继承概率
• $\gamma$ 贪婪率
• $\beta$ BS搜索的宽度
• $h$ 启发式函数
• $gv$ 贪婪信息设计
• $of2$ 次级目标函数

算法流程

BRKGA流程

1. 初始化随机生成指定数量的个体（实数向量）
2. 解码+BS+计算LCSqS与适应度值
3. 划分elite和no-elite个体，elite进入下一代，种群选择一部分进行突变
4. elite与no-elite进行偏随机交配
5. 继续步骤2

BRKGA-gv

1. gv=1,所有的贪婪信息都设置为0.5，设置为中间位置

2. gv=2,依次找出左右字符差距最小的分割点，切割点能够最大化切割两侧每种字符数量的总体平衡

   使用两个数组，分别统计，然后求差

3. gv=3,找一个字符串的切点的两层的LCS最长，寻找这个切点，其最大化每个字符串切割后两部分之间的LCS长度

BRKGA-of2

1. 偏好于那些切割点更集中于输入字符串中心位置的个体
2. 偏好于那些切割点使得切割两侧每种字符的数量更加均衡的个体
3. 偏好于那些切割点实现切割两侧LCS（最长公共子序列）距离更高的个体

of2的值越小，越符合期望。

BS-搜索的流程

1. 初始化节点
2. 选择A*/广度/深度搜索策略，构建相关数据结构
3. 遍历集合中的节点的启发式值，选择前$\beta$个
4. 构建下一层集合，迭代

BS-构建搜索节点集合的流程

1. 扩展当前节点：从当前节点开始，考虑所有可能的扩展（新）字符；
2. 字符选择：对于每个可能的字符（左位置向量右边的字符）；
3. 全列表匹配：尝试将所选字符与所有输入字符串的当前未匹配部分进行匹配，检测全列表的左位置向量的后面的字符中是否都有
4. 更新左位置向量：如果字符在所有输入字符串中都找到了匹配，则更新左位置向量。这涉及到增加每个字符串的索引位置，以便下一次可以继续从这个新位置开始搜索。
5. 生成新节点：对于每个成功的匹配，生成一个新的节点，这个节点代表了问题的一个更进一步的解。
6. 计算启发式值：为每个新生成的节点计算启发式函数值，这个值用于评估节点的“好性”，并决定它是否应该被包括在下一步的束中。
7. 从步骤1开始

BS-状态节点的启发函数

UB1

这个启发式函数提供了一个简单上界，用于估计解的期望长度。它计算每个字符在所有输入字符串剩余部分的最大出现次数的总和。

具体来说，对于字符集 Σ中的每个字符