一种基于改进萤火虫搜索算法的DNA存储编码集构建方法

一种基于改进萤火虫搜索算法的dna存储编码集构建方法
技术领域
1.本发明涉及dna编码集构建的技术领域，尤其涉及一种基于改进萤火虫搜索算法的dna存储编码集构建方法。


背景技术：

2.dna编码集的构建是dna存储的关键步骤。dna数据存储技术作为一种新型存储方式，在节约存储能源、推动大数据存储发展方面发挥着重要作用。编码是dna存储中的关键技术，其结果直接影响存储的性能和数据读写的完整性。合理高效的编码对于整个dna存储系统非常重要。对于dna编码问题，目前的研究内容主要分为编码质量和编码数量两个方面。在解决实际问题时，需要根据问题的重点选择编码方向：1)在编码量充足的条件下，研究目标是提高编码质量；2)在编码质量达到要求的前提下，研究目标是提高代码数量。一般来说，质量优化和dna编码数量往往无法实现双赢。没有好的方法来解决这个np完全问题，因为dna代码的数量总是随着约束的增加而减少。
3.2001年，marath等人提出了使用编码理论构造满足约束条件的dna编码集的下界。2002年，tulpan等人使用随机局部搜索算法生成可靠的dna编码集，所用的约束条件有汉明距离约束、反汉明距离约束、反补汉明距离约束和gc含量约束。kobayashiet等人提出了模板映射策略，虽然编码长度和距离约束不能太大，但模板方法很容易构建特定序列的dna编码集。2003年，tulpan等人将随机局部搜索算法中的单一领域搜索替换成多领域搜索，并产生了高质量的dna编码集合，实验结果证明了改进之后算法的有效性。2005年，gaborit等人通过线性构造和随机搜索相结合的方法研究dna编码集合的下界和下界。2006年，kawashimoet等人提出动态邻域搜索(dns)算法来设计dna编码集，该方法很容易构造满足类似基于汉明距离约束的编码集。2020年，zhang等人使用组合约束筛选dna存储代码，并使用clgbo和nol-hho等启发式算法构建dna存储代码集；lenz等人提出了一种无序序列表示的存储模型，在纠错码可到达基础上推导出gilbert-varshamov下界，在球形包装器上推导出上限。dna存储编码问题可以等价于满足组合约束的dna编码筛选问题。但是，由于约束的计算过程复杂度高，使用传统算法的效率太低。
4.传统的电子存储块都由引导区(地址位)、数据位和其他校验位组成。dna存储系统也类似地分为这些部分，其中dna单链存储结构通常包括有效载荷位(payload)和非有效载荷位(non-payload)。这些非有效载荷位包括地址位、校验位和引物等，它们非常重要，是正确寻址和读取完整数据的关键。然而，在以往的研究中，对非有效载荷位，尤其是地址位的编码重视程度不够。因此，该项工作主要集中在构建dna存储编码集合，以针对非有效载荷位。
5.启发式算法可以为组合优化问题的每个实例提供可行的解决方案，dna存储编码问题可以等价于满足组合约束的dna编码筛选问题。但是，由于约束的计算过程复杂度高，使用传统算法的效率太低。


技术实现要素：

6.针对现有dna存储编码集构建方法存在碱基利用率低、编码质量低的技术问题，本发明提出一种基于改进萤火虫搜索算法的dna存储编码集构建方法，将改进的萤火虫搜索算法应用于解决dna编码集的构建，可以构建满足组合约束的dna存储编码集，且保证了编码效率和编码质量。
7.为了达到上述目的，本发明的技术方案是这样实现的：一种基于改进萤火虫搜索算法的dna存储编码集构建方法，其步骤如下：
8.步骤一：根据dna存储编码集的特点，将dna编码组合约束建模为目标约束优化问题；
9.步骤二：将dna序列进行编码，应用改进的基于金字塔结构和方向调整机制的萤火虫搜索算法求解步骤一中的目标约束优化问题，得到最优萤火虫个体；将最优萤火虫个体转换为dna序列，得到满足约束条件的dna储存编码集。
10.优选地，所述步骤一中的目标约束优化问题的目标函数为序列间汉明距离之和且：
11.目标函数：fitness(s)＝∑h(x,y)，其中，x,y属于编码集合s的任意两个dna序列；
12.dna序列x和y的约束条件为：gc含量为50％、无运行长度约束和地址不相关约束；
13.其中，h(x,y)为dna序列x和y的汉明距离。
14.优选地，所述汉明距离为：
[0015][0016][0017]
其中，h(x，y)表示dna序列x(x1、x2、x3…
xn)和dna序列y(y1、y2、y3…yn
)之间的汉明距离；h(xi,yi)用于判断两个碱基是否相同，不同取值为1，相同取值为0；n表示dna序列的长度，xi、yi分别dna序列x和y中的第i个碱基；
[0018]
所述gc含量为：
[0019][0020]
其中，|g|和|c|分别表示dna序列x中g和c的个数；
[0021]
所述无运行长度约束是dna序列不包含重复的碱基：对于长度为n的dna序列x(x1、x2、x3…
xn)：
[0022]
xi≠x
i+1 i∈[1,n-1]；
[0023]
所述地址不相关约束是一个dna序列没有足够长的后缀是另一个dna序列的前缀，反之亦然：对于一对dna序列x(x1、x2、x3…
xn)和y(y1、y2、y3…yn
)，dna序列x的后缀不能作为y的前缀，反之亦然；序列(x1、x2...xs)≠序列(y
n-s+1
,y
n-s+2
...yn)且序列(y1,y2...ys)≠序列(y
n-s+1
,y
n-s+2
...yn)，s为前后缀长度。
[0024]
优选地，所述改进的基于金字塔结构和方向调整机制的萤火虫搜索算法的步骤如下：
[0025]
(1)初始化所需的参数并随机生成初始种群，每个个体表示一个编码集合，编码集
合的大小为问题的维度；dna序列中碱基的编码方式为：0-a，1-t，2-c，3-g；
[0026]
(2)计算每个个体的适应度值fitness，根据适应度值，对种群进行升序排列，建立金字塔种群拓扑结构；
[0027]
(3)竞争与协同合作策略：在金字塔种群拓扑结构中，每层中的萤火虫个体都可以进行协同合作，在层与层之间也存在着信息的传递；萤火虫个体在尝试朝着更好的方向移动时，向着比自身更好的个体学习；光强最高的萤火虫位于顶层；
[0028]
(4)方向调整机制：判断是否陷入了局部最优中；当调整概率大于生成的随机值时，种群将继续向着每层中的最优个体学习；当调整概率小于生成的随机值时，生成候选个体，种群将转为向着候选个体学习，尝试跳出局部最优；
[0029]
(5)得到新的萤火虫种群，完成一次迭代后，重新计算每一个个体的适应度值，更新最大适应度值、最小适应度值及相关位置，对金字塔种群拓扑结构进行更新；
[0030]
(6)优化结果将在达到最大迭代次数或精度条件时输出最优萤火虫个体，否则，返回步骤(3)。
[0031]
优选地，所述建立金字塔种群拓扑结构的方法为：初始化所需的参数并随机生成初始种群种群大小n，最大迭代次数t和搜索空间的维度d；随机产生n个萤火虫个体，并给萤火虫个体一个初始位置x＝[x1,x2,x3,
…
,xn,]，计算每个个体xi的适应度值；
[0032]
根据各层间的比例关系，确定每层上的个体数量是nu，u＝1,2,3,
…
,l，其中l是金字塔的层数；
[0033]
根据种群中个体的适应度值按升序排序，获得相应的个体x
′
＝[x1′
,x2′
,x3′
,
…
,xn′
]，个体x
′
中的第一层中的粒子n1被分配到金字塔的顶端，接下来的粒子n2被分配到第二层，以此类推；直到个体x
′
中的最后一个层的粒子n
l
被放置在金字塔的底部；
[0034]
对于每一层：u
dx2
＝u
dx1
+n
u-1
；
[0035]
生成的第floor层的金字塔结构p
floor，1：ni
＝x
′
udx1：udx2
；
[0036]udx1
＝u
dx2
+1；
[0037]
其中，x
′
udx1：udx2
表示升序排列后种群中第u
dx1
到u
dx2
的个体，u
dx1
、u
dx2
表示为每层分配个体的索引值。
[0038]
优选地，所述竞争与协同合作策略的实现方法为：
[0039]
同层协同合作，第l层中萤火虫个体的更新方式为：
[0040][0041]
式中，决策参数p＝q+h，决策参数p＝q+h，x
l.i
(t)表示第t次迭代中第l层中第i个萤火虫个体，x
l
.
best
(t)表示第t次迭代中第l层中最佳个体，x
l.j
(t)第t次迭代中第l层中第j个萤火虫个体，x
l.i
(t)第t次迭代中第l层中第i个萤火虫个体，β表示两个个体间的相互吸引力，αb是布朗运动随机步长，α
l
是莱维飞行随机步长，函数sign提供了一个随机的方向，表示莱维飞行，表示布朗运动；学习因子c2的更新公式为其中，学习因子c1＝1-c2，t表示最大迭代次数；rand1为[0，1]上均匀分布的随机数，rand2为[-1，1]上均匀分布的随机数，rand3为[-2，2]间
均匀分布的随机数，符号表示逐项乘法；rand为[0，1]上均匀分布的随机数；
[0042]
每层中亮度最高的萤火虫个体更新方式为：
[0043]
x
l.best
＝r1·
x
l.best
+r2·
x
l-1.best
+r3·
x
1.best
[0044]
式中，r1、r2、r3为[0，1]间的常数。
[0045]
优选地，布朗运动在x点的随机模型如下：
[0046][0047]
式中，微粒运动的步长是由零均值μ＝0和单位方差σ2＝1的高斯分布定义的概率函数计算得出；
[0048]
基于莱维分布的随机数用mantegna的方法生成：
[0049][0050]
式中，x和y是两个正态分布的变量，y＝normal(0，1)，
[0051]
其中α＝1.5。
[0052]
优选地，根据位置更新，萤火虫个体xj调整自己在解空间中的位置：
[0053][0054]
式中，xj(t+1)代表在第t+1次迭代时萤火虫个体xj的位置；t为当前的迭代次数，步长因子α为常数，取[0，1]；rand代表随机数，在[0，1]上服从均匀分布；
[0055]
萤火虫个体xi对萤火虫个体xj的吸引力β0表示光源对萤火虫的吸引力；
[0056]
萤火虫个体xi相对萤火虫个体xj的亮度为：
[0057][0058]
式中，ii是萤火虫个体xi的绝对亮度；γ表示光强吸收系数，r
ij
为萤火虫个体xi到萤火虫个体xj的欧式距离。
[0059]
优选地，所述方向调整机制的实现方法为：
[0060]
种群陷入局部最优的次数num用作计数器并初始化为0；
[0061]
当所有萤火虫个体的最佳位置在一次迭代中没有得到改善的情况为：f(x
l.best
)
t-f(x
l.best
)
t-1
＝0时，种群陷入了局部最优；则参数次数num更新为：num＝num+1；其中f(x
l.best
)
t
为第t次迭代时、第l层中最优萤火虫个体的最优位置的适应度值；
[0062]
种群调整其搜索方向的概率为调整概率，调整概率
[0063]
调整概率的值小于生成的随机数时，种群仍会从当前的最优个体x
l.best
中学习；
[0064]
调整概率的值大于生成的随机数时，种群通过学习候选个体来调整它的搜索方向。
[0065]
优选地，所述候选个体不仅将根据前群体的全局最佳个体x
l.best
来生成，而且还根据其他萤火虫的优秀结构来生成；生成候选个体为：
[0066][0067][0068][0069]
式中，candidated表示生成的候选者个体d维上的值；和分别表示随机选出的k和m两个萤火虫个体在d维上的值；gaussian(σd)根据标准差计算的高斯偏移值；f(x
l.k
)和f(x
l.m
)分别表示k和m两个个体的适应度值；表示第i个个体在d维度上的值；averaged表示种群在d维度上的平均值；n表示种群个体数量；σd是反映萤火虫子群中个体分布的标准差变量。
[0070]
与现有技术相比，本发明的有益效果：通过改进的萤火虫搜索算法(fapda)构建满足组合约束的dna存储编码集，保证编码效率和编码质量，改进的萤火虫搜索算法降低了原算法陷入局部最优的可能性，提高了算法的收敛速度，在一定的碱基长度内可以构建更多满足约束条件的dna存储代码集。本发明构造的编码集满足汉明距离约束、gc内容约束和无运行长度约束，具有一定的纠错能力，还具有许多编码优势，例如高鲁棒性、低编码复杂性和更短的编码时间。
附图说明
[0071]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0072]
图1为本发明的流程图。
[0073]
图2为金字塔结构的示意图。
[0074]
图3为种群在复杂搜索空间中的进化状态示意图，其中，(a)为个体x
l.best
接近局部最优，(b)为个体x
l.best
接近全局最优。
[0075]
图4为本发明调整概率的曲线图。
[0076]
图5为在随机两个维度上的进化状态示意图，其中，(a)为在第一维度，(b)为在第二维度。
[0077]
图6为各算法在12个函数上适应度值收敛曲线对比图。
具体实施方式
[0078]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0079]
如图1所示，一种基于改进萤火虫搜索算法的dna存储编码集构建方法，考虑在多种群萤火虫搜索算法的基础上建立金字塔模型，通过金字塔模型每层中、以及层与层之间
的竞争与协同合作，来改善子群中个体的质量，并加入方向调整机制，让算法具备跳出局部的能力，当判断种群陷入局部最优时，生成候选个体，通过让种群个体向候选个体学习，使种群具备跳出局部的能力。为此，提出一种基于金字塔结构和方向调整机制的萤火虫搜索算法(fapda)。通过将提出的fapda算法构建满足组合约束的dna存储编码集，保证编码效率和编码质量；提出的fapda算法降低了原算法陷入局部最优的可能性，提高了算法的收敛速度，保证编码效率和编码质量。本发明通过将dna编码问题转化为目标约束优化问题，在一定的碱基长度内可以构建更多满足约束条件的dna存储代码集，构造的编码集满足汉明距离约束、gc内容约束和无运行长度约束，具有一定的纠错能力，还具有许多编码优势，例如高鲁棒性、低编码复杂性和更短的编码时间。本发明的具体实现方法为：
[0080]
步骤一：根据dna存储编码集的特点，将dna编码组合约束建模为目标约束优化问题，为了计算方便，用0、1、2、3表示dna序列中的碱基a、t、c、g。
[0081]
对dna序列进行有效的编码，不仅可以提高吞吐率增加存储容量，而且可以降低在存储过程中发生错误的概率。合理的编码对数据的完整性、dna存储系统的鲁棒性有难以替代的支撑作用。dna编码中的组合约束问题首先被garzon等人提出，随后，虽然学者们使用了多种不同的dna编码约束组合，但是在近几年的研究文献中，选用的编码约束组合常用的是碱基连续性、汉明距离约束、g-c含量约束和无运行长度约束这四个指标。
[0082]
对于集合中的任意一对长度为n的dna序列x(x1、x2、x3…
xn)和y(y1、y2、y3…yn
)，汉明距离约束表示为h(x，y)≥d，其中h(x，y)表示对应序列在dna序列x和y之间不同的位置数。汉明距离的计算方法为：
[0083][0084][0085]
其中，h(x，y)表示dna序列x(x1、x2、x3…
xn)和dna序列y(y1、y2、y3…yn
)之间的汉明距离；h(xi,yi)用于判断两个碱基是否相同，不同取值为1，相同取值为0；n表示序列的长度，xi、yi分别dna序列x和y中的第i个碱基。汉明距离用于描述两个序列的相似度的大小，且其值越小，相似度越高。这意味着两个dna编码之间不同碱基的数量越少，相同碱基的数量越多；因此，在dna序列之间发生非特异性杂交的可能性就越大。
[0086]
gc含量是一条dna链中碱基g、c所占总碱基数的比例。一般gc含量约在50％左右不易出错和稳定。长度为n的dna序列x的gc含量记为gc(x)。使用以下公式来计算gc含量：
[0087][0088]
其中，|g|和|c|分别表示dna序列x中g和c的个数，n为dna序列x的长度。
[0089]
无运行长度约束是dna序列不应包含重复的碱基，长时间运行相同的核苷酸会导致dna编码出现不期望的二级结构，影响dna存储的可靠性。例如，在atttac中，t是重复的，所以在合成和测序中，很容易将多个t解读为少量的t，增加了dna信息的丢失率，减少了读写覆盖率。对于长度为n的dna序列x(x1、x2、x3…
xn)：
[0090]
xi≠x
i+1 i∈[1,n-1]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)
[0091]
地址不相关约束指的是在dna存储中，为了恢复dna存储的数据信息，反应池中的
分子必须以特定地址为前缀。地址序列不得相似，以避免检索数据块信息失败。因此，地址位需要一种特殊的编码，可以通过地址不相关约束来施加编码约束。地址不相关约束的结果是一个序列没有足够长的后缀是另一个序列的前缀，反之亦然。通过不相关地址约束得到的编码集不仅可以消除地址之间的交叉杂交，还可以避免测序过程中的序列选择错误。对于一对dna序列x(x1、x2、x3…
xn)和y(y1、y2、y3…yn
)，x的后缀不能作为y的前缀，反之亦然。前后缀长度被定义为s，序列(x1、x2...xs)≠序列(y
n-s+1
,y
n-s+2
...yn)并且序列(y1,y2...ys)≠序列(y
n-s+1
,y
n-s+2
...yn)。这里定义s＝3。
[0092]
本发明中，使用一个约束的汉明距离之和作为dna约束编码过程的适应度函数，其它约束条件作为目标函数约束。dna编码优化模型中使用dna编码集合中序列间汉明距离之和作为dna约束编码过程的适应度函数，约束条件包括gc含量为50％、无运行长度约束和地址不相关约束：
[0093]
目标函数：fitness(s)＝∑h(x,y)，其中x,y属于编码集合s的任意两个dna序列
[0094]
dna存储中编码集合设计的目的是构建给定长度为n的dna序列的集合。通过采用给定的优化算法构建dna编码序列集合，用于对地址的编码。为了更经济而高效的利用dna序列，尽可能的使给定长度的集合更大、编码的dna更稳定、反应中产生的错误更少。对于dna存储代码的构建，旨在进一步提高相同约束要求下的编码集大小和编码率。
[0095]
步骤二：将每个个体表示为一个编码集合，应用改进的基于金字塔结构和方向调整机制的萤火虫搜索算法(fapda)求解目标约束优化问题，得到最优萤火虫个体；将最优萤火虫个体转换为dna序列，筛选满足约束条件的dna储存编码集。
[0096]
步骤如下：
[0097]
(1)初始化所需的参数并随机生成初始种群，每个个体表示一个编码集合，编码集合的大小为问题的维度。dna序列中碱基的编码方式为：0-a，1-t，2-c，3-g。
[0098]
(2)计算每个个体的适应度值fitness，根据适应度值，对种群进行升序排列，建立起金字塔种群拓扑结构。
[0099]
(3)竞争与协同合作策略：金字塔种群拓扑结构中，每层中的萤火虫个体都可以进行协同合作，在层与层之间也存在着信息的传递。具体来说，萤火虫个体在尝试朝着更好的方向移动时，还可以向着比自身更好的个体学习。光强最高的萤火虫位于顶层，将影响下面各层的萤火虫个体。
[0100]
(4)方向调整机制：判断算法是否陷入了局部最优中，用计数器记录陷入局部的次数，随着计数值的增大，种群更有可能进入局部最优，这意味着种群应该调整其搜索方向。当调整概率大于生成的随机值时，种群将继续向着每层中的最优个体学习；当调整概率小于生成的随机值时，生成候选个体，种群将转为向着候选个体学习，尝试跳出局部最优。
[0101]
(5)得到新的萤火虫种群，完成一次迭代后，重新计算每一个个体的适应度值，更新最大适应度值、最小适应度值及相关位置，对金字塔种群拓扑结构进行更新。
[0102]
(6)优化结果将在达到最大迭代次数或精度条件时输出最优的dna存储编码集，否则，返回步骤(3)。
[0103]
英国剑桥大学的yang受到萤火虫用荧光亮度交流和聚集的行为的启发，提出了一种新的群智能优化算法，萤火虫搜索算法，该算法具有独特的进化机制，强大的局部搜索能力，在各种优化问题和应用领域的优化性能都可以和其他群智能优化算法相媲美。同时为
了使算法的流程更加清晰，数学模型更加简单，采取了以下几条规则：
[0104]
(1)无论是雌性还是雄性，萤火虫都会朝着最亮和最近的萤火虫移动，如果周围没有这样的萤火虫，它们就会在原来的位置上做无目标的运动。
[0105]
(2)光强和距离决定了萤火虫相互吸引的程度。萤火虫发出的荧光越明亮，就越能让其他萤火虫向它移动。这种吸引力随着光强增加而增加，随着距离增加而减少。
[0106]
(3)优化函数在萤火虫搜索算法中代表了萤火虫的亮度。目标函数适应度值越好的萤火虫越亮，它们的位置就是优化函数的解。种群通过进化和相互吸引来更新，其他萤火虫会朝着最亮的个体移动，从而更新种群。
[0107]
在萤火虫搜索算法中，亮度和相互吸引力决定了个体的特性。个体根据亮度判断位置并选择移动方向；而吸引力则控制了它们移动的范围。个体亮度在种群进化的过程中不断变化，最终达到迭代终止条件并获得目标函数最优解。在萤火虫搜索算法中，个体i到j的距离表示为r
ij
，计算时通常使用欧氏距离，即：
[0108][0109]
式中，d表示搜索空间的维度。xi和xj分别表示种群中第i个个体和第j个个体，x
i,k
和x
j,k
分别表示个体i和个体j在k维度上的值。
[0110]
萤火虫之间的相互吸引是基于其发光强度不同所引起的。萤火虫i对萤火虫j的吸引力大小可以用描述，与萤火虫个体j的相对亮度成正比。式中，β0表示光源对萤火虫的吸引力，在光源位置有r
ij
＝0，这时候萤火虫最有吸引力，一般选择β0＝1，γ为光强吸收系数。
[0111]
萤火虫i相对萤火虫j的亮度为：
[0112][0113]
式中，ii是萤火虫i的绝对亮度，表示萤火虫i所代表的潜在解的目标函数值；γ表示光强吸收系数，介质对光波有折射率和散射系数，导致光波在其中传播时强度逐渐衰减，一般情况下对γ取常量。
[0114]
根据位置更新，萤火虫j会调整自己在解空间中的位置，这个调整取决于萤火虫i和j之间的亮度、距离和吸引力。
[0115][0116]
式中，xj(t+1)代表萤火虫j在第t+1次迭代的位置；β
ij
表示萤火虫i对萤火虫j的吸引力；t为算法当前的迭代次数，步长因子α为常数，取[0,1]；rand代表随机数，在[0,1]上服从均匀分布。
[0117]
萤火虫搜索算法中，个体只受到光强影响而做出向光的运动，它缺乏多样性，容易过早收敛或陷入局部最优。受现实世界中“多层”现象的激励，使用金字塔拓扑来组织种群个体。如图2所示，金字塔按照它的名字的形状运作，顶部有一个或几个领导，下面有多个领导团队，具体来说，顶层的萤火虫个体可以引导金字塔中的所有萤火虫个体，而其他层的萤火虫个体只能引导下面各层的萤火虫个体。这种拓扑能够比传统的拓扑为每个个体更均匀地分配责任。同时，个体的质量决定了个体所在的位置。一个萤火虫个体质量越好，它在金
字塔中的层级就越高。
[0118]
假定优化问题是最小化问题，并根据种群中个体的适应度来划分其层。假设这个种群中有n个个体x＝[x1,x2,x3,
…
,xn]，根据各层间的比例关系，确定每层上的个体数量是nu，u＝1,2,3,
…
,l，其中l是金字塔的层数，可以根据种群中个体的适应度值f＝[f(x1),f(x2),f(x3),
…
,f(xn)]按升序排序，获得相应的个体x
′
＝[x1′
,x2′
,x 3
′
,
…
,xn′
]，然后个体x
′
中的第一层中的粒子n1被分配到金字塔的顶端，接下来的粒子n2被分配到第二层，以此类推。这个过程会重复进行，直到个体x
′
中的最后一个层的粒子n
l
被放置在金字塔的底部。最后，金字塔就完成了，该构建过程可以在算法1中进行描述。
[0119][0120][0121]
算法1的第9行，p
u,j
表示金字塔第u层的第j个萤火虫个体。p(x
′
,l,nu)在伪代码中表示搭建金字塔的一个函数，u
dx1
、u
dx2
表示为每层分配个体的索引值，p
floor,1:nu
表示生成的第floor层的金字塔结构，x
′
udx1:udx2
表示升序排列后种群中第u
dx1
到u
dx2
的个体。可以看到，这个金字塔具有以下属性：
[0122]
(1)每个萤火虫个体都被分配到一个特定的图层中；
[0123]
(2)萤火虫个体所在层越高，其适应度值越好；全局最好的萤火虫个体位于顶层，而最差的萤火虫个体位于底层；
[0124]
(3)同一层的萤火虫个体具有接近的适应度值。
[0125]
萤火虫搜索算法中，个体之间的交互是通过互相吸引来实现的，而不是通过直接
的竞争机制。在萤火虫搜索算法中，每个萤火虫个体根据自身的发光亮度对不同距离的萤火虫个体产生吸引，萤火虫更加倾向于朝着对自身造成更强的光强吸引方向移动。个体的移动方向和距离也会根据周围萤火虫的亮度和距离来调整。这种位置更新是基于互相吸引的关系，而不是通过竞争来实现。
[0126]
萤火虫搜索算法运行时，存在萤火虫个体比较分散，或萤火虫个体比较集中两种情况。这两种情况的存在，可能会导致萤火虫种群产生不同的结果。当萤火虫种群中个体比较分散时，萤火虫种群可能是由于吸引力计算和移动方式的局限性，导致搜索陷入局部最优，无法跳出。当萤火虫种群相对集中时，这些解的萤火虫可能会互相吸引，导致种群个体的多样性降低。同时，因为萤火虫搜索算法需要计算所有萤火虫个体之间的距离和吸引力，这可能会导致计算成本较大，尤其是在搜索空间较大的情况下。
[0127]
为了解决这个问题，在萤火虫搜索算法中引入更具竞争力的策略。除了增加随机性或者多样性的操作来保持种群的多样性，还可以选择适当的萤火虫个体对其产生的吸引来进行位置更新，可以大量的减小计算造成的成本，提高计算速度。
[0128]
首先，在建造金字塔时，所有的萤火虫个体都参与排序来决定它们在金字塔中的层数。由于排序涉及到所有的萤火虫个体，称之为全局竞争策略。其次，将每个萤火虫个体放置在特定的层中，对同一层的萤火虫个体可以进行不同的处理，以提高效率。根据这一想法，引入了针对一层萤火虫个体的学习策略。在每一层中，所有萤火虫个体将受到同层的萤火虫个体的光强吸引，同时，向着同层中亮度最高的萤火虫个体学习，除了每层的亮度最高的萤火虫个体，其他萤火虫个体将不受到来自其它层萤火虫个体的影响，称之为局部协同合作策略。而对于每层中亮度最高的个体，则将受到来自上一层亮度最高的萤火虫个体的影响。
[0129]
受上述分析的启发，提出了一种新的合作策略，即在建造的金字塔中，每层中的萤火虫都可以进行协同合作，在层与层之间也存在着信息的传递。具体来说，萤火虫在尝试朝着更好的方向移动时，还可以向着比自身更好的个体学习，光强最高的萤火虫个体位于顶层将影响下面各层的萤火虫个体。而不是仅仅是通过个体之间相吸引来更新位置。从数学上看，第l层中萤火虫个体的更新方式为：
[0130][0131]
式中，p＝q+h，p＝q+h，x
l.i
(t)表示第t次迭代中、第l层中第i个萤火虫个体，x
l.best
(t)表示第t次迭代中第l层中最佳个体，x
l.j
(t)第t次迭代中第l层中第j个萤火虫个体，x
l.i
(t)第t次迭代中第l层中第i个萤火虫个体，β表示两个个体间的相互吸引力，αb是布朗运动随机步长，α
l
是莱维飞行随机步长，函数sign提供了一个随机的方向，表示莱维飞行，表示布朗运动，p表示决策参数；学习因子c2的更新公式为其中，学习因子c1＝1-c2，t表示最大迭代次数。rand1为[0,1]上均匀分布的随机数，rand2为[-1,1]上均匀分布的随机数，rand3为[-2,2]间均匀分布的随机数，t为当前迭代次数，符号表示逐项乘法，t为设置的最
大迭代次数。
[0132]
布朗运动是一种模拟悬浮在液体或者气体中微粒做不停息无规则运动的随机策略。在布朗运动中微粒的运动是随机的，每一步的方向和距离都是由正态分布随机数决定的。在连续时间的布朗运动中，微粒的位置随时间变化而变化，其轨迹呈现出无规则的波动。每个时间步长中，微粒的运动只与当前的位置有关，与之前的位置无关，因此布朗运动是一种马尔可夫过程。布朗运动在不同的时间段内，移动距离的分布均服从正态分布，具有尺度不变性。布朗运动在x点的随机模型如下：
[0133][0134]
式中，微粒运动的步长是由零均值μ＝0和单位方差σ2＝1的高斯分布定义的概率函数计算得出。
[0135]
莱维飞行是一种具有指数方差和长尾分布特点的概率分布，在随机行走过程中有相对较高的概率出现较大的跨步。为了更好的度量莱维飞行的运动轨迹，mantegna提出了一种可以在0.3到1.99范围内生成莱维轨迹稳定过程的精确快速的方法。基于莱维分布的随机数用mantegna的方法生成如下。
[0136][0137]
式中，x和y是两个正态分布的变量，y＝normal(0,1)，
[0138]
其中
[0139]
在算法前期采用布朗运动的随机性来代替萤火虫搜索算法中传统的均匀分布可以更好的发挥性能。同理，在算法的后期用莱维飞行的随机性来代替萤火虫搜索算法中传统的均匀分布，以发挥莱维飞行小步长和偶尔跳远的行为的特性，来平衡算法的全局搜索能力和局部开发能力。
[0140]
每层中亮度最高的萤火虫个体更新方式为：
[0141]
x
l.best
＝r1·
x
l.best
+r2·
x
l-1.best
+r3·
x
1.best
ꢀꢀꢀ
(11)
[0142]
式中，r1、r2、r3为[0,1]间的常数。
[0143]
竞争与协同合作策略可以被描述为算法2。
[0144][0145][0146]
在复杂空间中搜索时，萤火虫种群有可能陷入局部最优。对于某层金字塔中的萤火虫，进化状态可以用图3来描述，其中萤火虫x
l.best
是该层金字塔中亮度最高的个体，曲线表示该维度内适应度值的变化趋势。在图3的(a)中，每个萤火虫，如x
l.1
和x
l.2
都可以沿着x
l.best
方向搜索，经过多次迭代后进入局部最优。假设f(x
l.best
)
t
表示第t次迭代时、第l层中最优萤火虫个体的最优位置的适应度值。每次迭代后，将xi与x
l.best
进行比较，将更新个体x
l.best
和适应度值f(x
l.best
)
t
。当所有萤火虫个体的最佳位置在一次迭代中没有得到改善的情况可以被描述为：
[0147]
f(x
l.best
)
t-f(x
l.best
)
t-1
＝0
ꢀꢀ
(12)
[0148]
式中，t为迭代次数。显然，所有萤火虫的最佳位置在一次迭代后没有得到改善的特征可能反映了群体陷入了局部最优。为了避免群落入局部最优状态，保证算法的效率，可以在等式成立时调整群的搜索方向。然而，不能仅仅依靠上述情况来调整群的搜索方向的决定，特别是当种群在复杂解空间中搜索时。如图3的(b)所示，该层萤火虫的最佳值x
l.best
是接近全局最优的萤火虫。在第t次迭代中，种群中的萤火虫，例如x1(t)和x2(t)可以沿着x
l.best
的方向搜索，这些萤火虫个体的最佳位置在第1次迭代中不会得到改善，在这种情况下，等式f(x
l.best
)
t-f(x
l.best
)
t-1
＝0也是满足的。频繁的信息交换可能会加速错误信息的交换，而零星的信息交换则会损害多群的交换性能。因此，为了充分发挥个体x
l.best
的进化能力和避免群落入局部最优，提出一种基于延迟的搜索方向调整机制，用来检查一个子群是否已经停滞，激活停滞的子群再次进化，在适当的时间调整搜索方向，防止子群落入局部最优当中。
[0149]
事实上，随着所有萤火虫的最佳位置没有得到改善的情况出现次数增加，种群陷入局部最优的概率也会增加，然后个体需要及时的调整它的搜索方向。用num表示种群陷入局部的次数，num被用作计数器并初始化为0。如果所有萤火虫在一次迭代后没有改进，可以将参数num更新为：
[0150]
num＝num+1
ꢀꢀ
(13)
[0151]
显然，随着参数num值的增大，个体更有可能进入局部最优，这意味着种群应该调整其搜索方向。将种群调整其搜索方向的概率表示为调整概率，调整概率prob
adjust
根据经验取：
[0152][0153]
这里的调整概率会在每次迭代后进行更新。图4显示了调整概率随迭代次数t的变化，如果调整概率大于1，种群将停止从当前最优个体x
l.best
学习，并将其搜索方向调整为新的萤火虫个体所在位置。基于延迟的搜索方向调整机制的具体的过程如算法3所示。
[0154]
如图4所示，当种群的陷入局部的次数num较小时，调整概率由num决定，并且很可能小于生成的随机数，那么种群仍会从当前的最优个体x
l.best
中学习。最优个体x
l.best
的潜在领先能力将在接下来的几次迭代中得到充分利用，特别是当最优个体x
l.best
接近如图3(b)所示的全局最优值时。如果所有萤火虫在接下来的几个迭代中仍然没有改进，参数num的值将不断增加，种群更有可能陷入局部最优中，那么调整概率的值将大于1，种群将通过学习一个新的萤火虫来调整它的搜索方向。新的萤火虫被称为候选个体，然后，在从候选个体那里学习一段时间的迭代后，种群可以跳出当前的局部最优。综上所述，该策略可以充分利用最优个体x
l.best
的潜在领先能力，来帮助种群跳出局部最优。
[0155][0156]
在方向调整策略中，所有的萤火虫在一开始从最优个体x
l.best
中学习，种群使用计数器来判断它是否需要调整其搜索方向。当种群可能被困在局部最优状态时，将通过学习一个候选的新萤火虫个体来调整搜索方向。在搜索空间中生成随机的候选个体，种群可以从生成的候选中学习，跳出当前的局部最优。然而，随机生成的候选者引导种群进化的能力
难以得到保证，特别是在复杂空间中搜索时，候选者更有可能引导种群进入另一个局部当中。为了有效地生成候选个体，提出了一种基于自学习的候选生成策略来充分利用每层中优秀的萤火虫历史最优解结构。
[0157]
显然，当前x
l.best
的适应度值仍然是最好的，并且x
l.best
在大部分维度上仍然保持着良好的解结构。因此，在生成候选个体时，x
l.best
的解决方案结构值得学习。此外，由于一个萤火虫的适应度值是由该个体的所有维度解的结构决定的，被表示为：
[0158][0159]
因此，适应度值稍差的萤火虫个体在某些特定维度上可能具有较好的解结构，在这种情况下也值得学习。
[0160]
图5显示了种群在随机两个维度上的进化状态，萤火虫在维度中搜索最大值，曲线显示了每个维度中适应度值的变化趋势。x
l.best
是当前群体的全局最佳个体，x
l.1
和x
l.2
分别是同层中随机的两个个体。可以看出，x
l.best
在第一维度上解的结构最好，而个体x
l.1
在第二维上解的结构优于最优个体x
l.best
。因此，候选个体不仅将根据x
l.best
来生成，而且还将根据其他萤火虫的优秀结构来生成。
[0161]
在同层中随机挑选两个萤火虫个体x
l.k
和x
l.m
，并以σd的高斯偏移值来选择更优秀的一个。由于选择过程是随机的，理论上种群中的所有萤火虫都可以将自己的搜索信息提供给候选萤火虫个体。候选个体可能获得优于当前个体x
l.best
的解决方案结构，并且更有可能接近全局最优，因此，种群可以通过将其搜索调整为候选个体方向而跳出局部最优，经过一段时间的迭代后，可以找到全局最优。生成候选个体为：
[0162][0163][0164][0165]
式中，candidated表示生成的候选者个体d维上的值；和表示随机选出的k和m两个个体在d维上的值；gaussian(σd)根据标准差计算的高斯偏移值；f(x
l.k
)和f(x
l.m
)表示k和m两个个体的适应度值；表示第i个个体在d维度上的值；averaged表示种群在d维度上的平均值；n表示种群个体数量；σd是反映萤火虫子群中个体分布的标准差变量。随着候选概率的增加，生成的候选者将更类似于x
l.best
，同样，候选者可能与x
l.best
有很大的不同，并有能力引导群体从当前的局部最优中跳出。基于自我学习的候选个体成策略具体的过程如算法4所示
[0166]
[0167][0168]
提出的fapda搜索算法是提出的参数自适应策略的基础上，对萤火虫搜索算法的种群重新进行了划分，构建起金字塔模型，在金字塔层与层之间、各层之间加入协同合作策略；同时，也加入了基于延迟的方向调整机制，来避免算法陷入到局部。fapda搜索算法的具体步骤如下：
[0169]
步骤一：初始化种群大小n，迭代次数t，个体维度d等相关参数。
[0170]
步骤二：随机产生n个萤火虫个体，并给它们一个初始位置x＝[x1,x2,x3,
…
,xn,]，计算每个个体xi的适应度值f(xi)，根据适应度的值，对种群进行升序排列，建立起金字塔种群拓扑结构。
[0171]
步骤三：竞争与协同合作策略：金字塔拓扑结构中，每层中的萤火虫个体都可以进行协同合作，在层与层之间也存在着信息的传递。具体来说，萤火虫个体在尝试朝着更好的方向移动时，还可以向着比自身更好的个体学。每层中的萤火虫，根据公式(8)对位置进行更新。光强最高的萤火虫位于顶层，将影响下面各层的萤火虫个体。每层中最优的萤火虫个体根据公式(11)对位置进行更新。
[0172]
步骤四：方向调整：根据公式(12)，判断算法是否陷入了局部最优中，用计数器记录陷入局部的次数，随着计数值的增大，种群更有可能进入局部最优，这意味着种群应该调整其搜索方向。当调整概率大于生成的随机值时，种群将继续向着每层中的最优个体学习；当调整概率小于生成的随机值时，将根据公式(16)生成候选个体，种群将转为向着候选个体学习，尝试跳出局部最优。
[0173]
步骤五：得到新的萤火虫种群，完成一次迭代后，重新计算每一个个体的适应度值，更新最大适应度值、最小适应度值及相关位置，根据步骤二生成新的金字塔结构。
[0174]
步骤六：优化结果将在达到最大迭代次数或精度条件时输出，否则，将返回步骤三。
[0175]
算法伪代码如算法5所示。
[0176]
[0177][0178]
为了验证fapda的寻优能力和鲁棒性，与改进的萤火虫搜索算法(fabmla)、萤火虫搜索算法(fa)、自适应萤火虫搜索算法(gdfa)、哈里斯鹰算法(hho)以及粒子群算法(pso)进行综合性对比分析。为实验的公平性，比较算法的规模大小(n)和最大迭代次数(t)分别设置为50和1000。具体参数设置如表1，每种算法在每个基准函数上独立运行30次。实验室环境为matlab2020b，windows10操作系统，运行内存为4g。
[0179]
为了评估提出的改进后萤火虫搜索算法的性能，仿真实验使用了12个基准测试函数，它们分为三类：包括单峰函数(f
1-f6)和多峰函数(f
7-f
12
)来评估改进后萤火虫搜索算法的性能。单峰基准函数来测试算法在收敛速度和局部开发能力方面的表现。多峰函数含有多个局部最优解，并且维度越高，解的个数越多。所以，这些多峰函数可以进一步测试算法的探索能力和全局优化性能。表2展示了实验中所用到的基准测试函数。同时，为了进一步检测各种算法的搜索能力，将各测试函数的维度提高到30维。
[0180]
表1各算法的参数设置
[0181]
[0182][0183]
表2基准测试函数
[0184][0185]
表3记录了每种算法运行30次后的平均值、标准差、最佳和最差适应度值(用粗体突出显示最佳结果)。从表3中可以看出，所提出的fapda算法在所有的单峰函数上都找到了最优解。此外，fapda算法能够在大多数单峰函数上取得比其他竞争对手更好的结果。例如在测试函数f1、f2、f3和f4上，fapda找到了理论上的最佳适应度值，在收敛速度和最终的收敛精度上与算法fabmla、gdfa、pso、fa和hho相比都有较大的提升。对于函数f5，fapda算法的性能与fabmla算法基本相同，但是远远优于其他算法。对于函数f6，fapda算法最终的收敛精度同样远超对比算法。
[0186]
在多峰函数中，函数f7的测试中，fabmla算法寻优结果远超其他算法，除函数f7外，算法fapda在f8、f9、f
10
、f
11
和f
12
的最优值和平均值明显优于其他算法。值得注意的是，fapda算法在f8上能够获得全局最优值，而其他算法不能得到全局最优。在f
11
和f
12
上，fabmla算法仅次于fabmla，在所有算法中排名第二。
[0187]
图6显示了12个基准测试函数上6种算法的收敛性能对比。在大多数单峰函数上，fapda算法比其他算法具有更快的收敛速度。尽管fabmla通过参数自适应变化，hho通过四种捕食方式的结合，但仍输给了fapda。根据单峰函数的特点，可以说fapda具有很好的开发能力。在大多数多峰函数中，fapda具有更好的收敛速度和足够的精度。fabmla算法只在函数f7上优于fapda。该实验表明fapda算法在探索能力上仍具有卓越的表现，这得益于在金字塔的框架下，种群间的协同合作策略带来的高种群多样性，基于延迟的搜索方向调整机制具有避免陷入局部最优能力。综上，基于金字塔结构和方向调整机制的加入，有效提高了算法的探索性能。此外，方向调整机制能够有效的跳出局部最优。
[0188]
表3 30维的12个基准测试函数上各算法的统计结果
[0189]
[0190][0191]
为了证明提出的算法与其他算法之间是否有显著性差异，除了已经验证了fapda在平均值、标准差、收敛性和稳定性方面的优势之外，还需要进行显著性检验。wilcoxon’s秩和检验是一种用来比较两组数据是否有差异的方法。它不需要假设数据服从某种特定的分布，只需要假设两组数据是独立的，并且有相似的变化程度。它的基本思想是将两组数据合并起来，然后按照大小顺序给每个数据一个排名。然后计算每组数据的排名之和，看看它们是否相近。如果两组数据很相近，那么它们的排名之和也应该很接近。如果两组数据有明显的差异，那么它们的排名之和也会有较大的差距。从表4中可以看出，fapda算法在除函数f7外的11个测试函数上显著优于fabmla算法。fapda在12个基准测试函数上与gdfa有显著差异。fapda与pso在12个测试函数上均有显著性差异。对于fa、fapda在12个基准测试函数上存在差异显著。fapda与hho在12个测试函数上均有显著性差异。总而言之，fapda在绝大多数测试函数上都显著优于其他五种算法。因此，可以说明fapda算法具有更好的性能。
[0192]
表4在12个基准测试函数上fapda与其他五种算法的对比结果
[0193][0194]
表5在12个基准测试函数上的mae平均排名
[0195][0196]
最后，为了定量分析算法的性能，对各种算法的平均绝对误差(mean absolute error,mae)值进行计算和排序。mae是一种有效的统计方法，可以显示结果与实际值的差距。mae公式如下：
[0197][0198]
式中，mi是算法的最佳值，ki表示基准函数的相应实际值，n是基准函数的数量。表5展示出实验算法的mae值和排名，很明显，fapda的性能优于其他算法。
[0199]
dna存储代码的界限：长度为n、汉明距离d并满足汉明距离约束、gc含量约束、地址不相关约束且无重复碱基约束的dna编码集定义为a
gc-nl-ul
(n，d，w)。表6中的结果为4≤n≤10、3≤d≤n满足约束的下界值。与已有文献结果对比，可知，在相同约束条件下、序列长度一定的情况下，构造更大的编码集合，有助于编码更大的地址空间，意味着可以用更短的序列寻址更多的有效信息，进而降低了成本。
[0200]
表6.dna存储编码集下界
[0201][0202]
本发明提出了基于金字塔结构和方向调整机制的萤火虫搜索算法来改善萤火虫搜索算法搜索能力不足的问题，首先搭建起金字塔模式的拓扑结构，为每个个体更均匀地分配责任，提高算法的多样性；其次，在迭代过程中，引入更具竞争力的策略，选择适当的萤火虫个体对其它个体产生的吸引来进行位置更新，使种群间进行更好的竞争与协同合作，提高了计算速度。最后，为了避免种群陷入到局部最优中，使用基于延迟策略的方向调整机制，当种群陷入局部时，生成候选解，使种群具有跳出局部的能力。在12个具有不同特征的单峰、多峰和复杂的基准函数上进行了实验，并与其他几种优化算法进行了比较。实验结果表明，本发明fapda算法在搜索能力、开发强度和跳出局部最优的能力方面都有较好的表现。此外，还将fapda算法应用于压力容器设计问题中，并得到了满意的结果。这说明fapda算法是一种有效的优化技术。本发明通过将改进的萤火虫算法、应用于dna存储中的编码问题中，得到了满意的结果。
[0203]
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，其步骤如下：步骤一：根据dna存储编码集的特点，将dna编码组合约束建模为目标约束优化问题；步骤二：将dna序列进行编码，应用改进的基于金字塔结构和方向调整机制的萤火虫搜索算法求解步骤一中的目标约束优化问题，得到最优萤火虫个体；将最优萤火虫个体转换为dna序列，得到满足约束条件的dna储存编码集。2.根据权利要求1所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述步骤一中的目标约束优化问题的目标函数为序列间汉明距离之和且：目标函数：fitness(s)＝∑h(x,y)，其中，x,y属于编码集合s的任意两个dna序列；dna序列x和y的约束条件为：gc含量为50％、无运行长度约束和地址不相关约束；其中，h(x,y)为dna序列x和y的汉明距离。3.根据权利要求2所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述汉明距离为所述汉明距离为其中，h(x，y)表示dna序列x(x1、x2、x3…
x
n
)和dna序列y(y1、y2、y3…
y
n
)之间的汉明距离；h(x
i
,y
i
)用于判断两个碱基是否相同，不同取值为1，相同取值为0；n表示dna序列的长度，x
i
、y
i
分别dna序列x和y中的第i个碱基；所述gc含量为：其中，|g|和|c|分别表示dna序列x中g和c的个数；所述无运行长度约束是dna序列不包含重复的碱基：对于长度为n的dna序列x(x1、x2、x3…
x
n
)：x
i
≠x
i+1 i∈[1,n-1]；所述地址不相关约束是一个dna序列没有足够长的后缀是另一个dna序列的前缀，反之亦然：对于一对dna序列x(x1、x2、x3…
x
n
)和y(y1、y2、y3…
y
n
)，dna序列x的后缀不能作为y的前缀，反之亦然；序列(x1、x2...x
s
)≠序列(y
n-s+1
,y
n-s+2
...y
n
)且序列(y1,y2...y
s
)≠序列(y
n-s+1
,y
n-s+2
...y
n
)，s为前后缀长度。4.根据权利要求1-3中任意一项所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述改进的基于金字塔结构和方向调整机制的萤火虫搜索算法的步骤如下：(1)初始化所需的参数并随机生成初始种群，每个个体表示一个编码集合，编码集合的大小为问题的维度；dna序列中碱基的编码方式为：0-a，1-t，2-c，3-g；(2)计算每个个体的适应度值fitness，根据适应度值，对种群进行升序排列，建立金字塔种群拓扑结构；
(3)竞争与协同合作策略：在金字塔种群拓扑结构中，每层中的萤火虫个体都可以进行协同合作，在层与层之间也存在着信息的传递；萤火虫个体在尝试朝着更好的方向移动时，向着比自身更好的个体学习；光强最高的萤火虫位于顶层；(4)方向调整机制：判断是否陷入了局部最优中；当调整概率大于生成的随机值时，种群将继续向着每层中的最优个体学习；当调整概率小于生成的随机值时，生成候选个体，种群将转为向着候选个体学习，尝试跳出局部最优；(5)得到新的萤火虫种群，完成一次迭代后，重新计算每一个个体的适应度值，更新最大适应度值、最小适应度值及相关位置，对金字塔种群拓扑结构进行更新；(6)优化结果将在达到最大迭代次数或精度条件时输出最优萤火虫个体，否则，返回步骤(3)。5.根据权利要求4所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述建立金字塔种群拓扑结构的方法为：初始化所需的参数并随机生成初始种群种群大小n，最大迭代次数t和搜索空间的维度d；随机产生n个萤火虫个体，并给萤火虫个体一个初始位置x＝[x1,x2,x3,
…
,x
n
,]，计算每个个体x
i
的适应度值；根据各层间的比例关系，确定每层上的个体数量是n
u
，u＝1,2,3,
…
,l，其中l是金字塔的层数；根据种群中个体的适应度值按升序排序，获得相应的个体x
′
＝[x1′
,x2′
,x3′
,
…
,x
n
′
]，个体x
′
中的第一层中的粒子n1被分配到金字塔的顶端，接下来的粒子n2被分配到第二层，以此类推；直到个体x
′
中的最后一个层的粒子n
l
被放置在金字塔的底部；对于每一层：u
dx2
＝u
dx1
+n
u-1
；生成的第floor层的金字塔结构p
floor,1:ni
＝x
′
udx1:udx2
；u
dx1
＝u
dx2
+1；其中，x
′
udx1:udx2
表示升序排列后种群中第u
dx1
到u
dx2
的个体，u
dx1
、u
dx2
表示为每层分配个体的索引值。6.根据权利要求5所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述竞争与协同合作策略的实现方法为：同层协同合作，第l层中萤火虫个体的更新方式为：式中，决策参数式中，决策参数x
l.i
(t)表示第t次迭代中第l层中第i个萤火虫个体，x
l.best
(t)表示第t次迭代中第l层中最佳个体，x
l.j
(t)第t次迭代中第l层中第j个萤火虫个体，x
l.i
(t(第t次迭代中第l层中第i个萤火虫个体，β表示两个个体间的相互吸引力，α
b
是布朗运动随机步长，α
l
是莱维飞行随机步长，函数sign提供了一个随机的方向，表示莱维飞行，表示布朗运动；学习因子c2的更新公式为其中，学习因子c1＝1-c2，t表示最大迭代次数；rand1为[0,1]上均匀分布的随机数，rand2为[-1,1]上均匀分布的随机数，rand3为[-2,
2]间均匀分布的随机数，符号表示逐项乘法；rand为[0,1]上均匀分布的随机数；每层中亮度最高的萤火虫个体更新方式为：x
l.best
＝r1·
x
l.best
+r2·
x
l-1.best
+r3·
x
1.best
式中，r1、r2、r3为[0,1]间的常数。7.根据权利要求6所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，布朗运动在x点的随机模型如下：式中，微粒运动的步长是由零均值μ＝0和单位方差σ2＝1的高斯分布定义的概率函数计算得出；基于莱维分布的随机数用mantegna的方法生成：式中，x和y是两个正态分布的变量，y＝normal(0,1)，其中8.根据权利要求7所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，根据位置更新，萤火虫个体x
j
调整自己在解空间中的位置：式中，x
j
(t+1)代表在第t+1次迭代时萤火虫个体x
j
的位置；t为当前的迭代次数，步长因子α为常数，取[0,1]；rand代表随机数，在[0,1]上服从均匀分布；萤火虫个体x
i
对萤火虫个体x
j
的吸引力β0表示光源对萤火虫的吸引力；萤火虫个体x
i
相对萤火虫个体x
j
的亮度为：式中，i
i
是萤火虫个体x
i
的绝对亮度；γ表示光强吸收系数，r
ij
为萤火虫个体x
i
到萤火虫个体x
j
的欧式距离。9.根据权利要求1-3、5-8中任意一项所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述方向调整机制的实现方法为：种群陷入局部最优的次数num用作计数器并初始化为0；当所有萤火虫个体的最佳位置在一次迭代中没有得到改善的情况为：f(x
l.best
)
t-f(x
l.best
)
t-1
＝0时，种群陷入了局部最优；则参数次数num更新为：num＝num+1；其中f(x
l.best
)
t
为第t次迭代时、第l层中最优萤火虫个体的最优位置的适应度值；种群调整其搜索方向的概率为调整概率，调整概率调整概率的值小于生成的随机数时，种群仍会从当前的最优个体x
l.best
中学习；
调整概率的值大于生成的随机数时，种群通过学习候选个体来调整它的搜索方向。10.根据权利要求9所述的基于改进萤火虫搜索算法的dna存储编码集构建方法，其特征在于，所述候选个体不仅将根据前群体的全局最佳个体x
l.best
来生成，而且还根据其他萤火虫的优秀结构来生成；生成候选个体为：生成候选个体为：生成候选个体为：式中，candidate
d
表示生成的候选者个体d维上的值；和分别表示随机选出的k和m两个萤火虫个体在d维上的值；gaussian(σ
d
)根据标准差计算的高斯偏移值；f(x
l.k
)和f(x
l.m
)分别表示k和m两个个体的适应度值；表示第i个个体在d维度上的值；average
d
表示种群在d维度上的平均值；n表示种群个体数量；σ
d
是反映萤火虫子群中个体分布的标准差变量。

技术总结
本发明提出了一种基于改进萤火虫搜索算法的DNA存储编码集构建方法，用以解决现有DNA存储编码集构建方法存在碱基利用率低、编码质量低等问题。本发明的步骤为：建立以序列间汉明距离之和为目标函数的DNA编码集的数学模型；结合金字塔结构和方向调整机制构建改进的萤火虫搜索算法；采用改进的萤火虫搜索算法构建满足组合约束的DNA存储编码集，保证编码效率和编码质量。本发明改进的萤火虫搜索算法降低了原算法陷入局部最优的可能性，提高了算法的收敛速度；在一定的碱基长度内可以构建更多满足约束条件的DNA存储代码集。本发明构造的编码集满足汉明距离约束、GC内容约束和无运行长度约束，具有一定的纠错能力和许多编码优势。势。势。


技术研发人员：张勋才 申超楠 牛莹 张强 郭丹蕾 王时达 刘冠鹤 王延峰 何艳 张凯
受保护的技术使用者：郑州轻工业大学
技术研发日：2023.07.04
技术公布日：2023/10/7