基于免疫蚁群优化算法的细胞采集路径规划研究

王士信,付腾达,陈淑玲

(江西科技学院 信息工程学院,江西 南昌 330098)

0 引言

随着科技的飞速进步,计算机的普及使得它成了许多领域的重要组成部分,而且基于计算机的全自动化的医疗设备也被广泛应用。然而细胞采集仪器在临床中却很难应用,究其原因主要在于细胞采集仪器速度太慢,很难适用于临床。因此,提高细胞采集速度就成了细胞采集仪器的当务之急。影响细胞采集速度有多种原因,细胞采集的路径规划[1]就是其中一个原因。

细胞采集路径规划就是通过计算机控制显微镜把载玻片一定区域内的细胞逐个进行采集所走路线。采集路线的不同也就影响着整个标本的采集速度。

传统的细胞采集路径是按照行列方式逐行逐列进行采集。然而细胞分布并不是均匀分布的,这就造成了采集时间的浪费,因此本文采用了计算机智能算法进行细胞采集路径优化。

在进行细胞采样路线规划时,蚂蚁群算法(Ant Colony Algorithm,ACA)可以实现分布式和并发的全局搜寻[2]。然而,ACA由于没有足够的初始条件,导致运算速度较低,而且算法的收敛速度也较高,因此存在明显的局限性。由于在应用的过程中,ACA经常陷入局部最优,因此没有办法做到全局最优[3]。

当使用人工免疫算法[4](Artificial Immune Algorithm,AIA)规划细胞采集路径时,这种方法可以进行快速随机的全局搜索,但系统的反馈信息没有得到充分利用,需要在一定范围内重复,这往往会降低求解效率[5]。

通过对人工免疫算法和蚁群算法的比较,本文提出了一种新的混合免疫蚁群优化算法,它具有快速全局搜索的特性,可以有效地找到更优的解决方案,并且可以根据蚁群算法的结果,计算出细胞采集的最佳路径。

1 问题描述

细胞在载玻片中是随机分布的,并不是按照行列均匀分布的,细胞分布如图1所示,在显微镜低倍镜下把每个白细胞的坐标记录下来后,在高倍镜下还是按照传统的采集方式即按照行列方式逐行逐列进行采集,这就造成了采集时间的浪费。传统采集方式如图2所示。

图1 细胞分布图

图2 传统采集方式

把每个细胞的位置坐标(X,Y)记录下来后,假设有n个细胞,那么所有细胞的坐标为(X1,Y1),(X2,Y2),…,(Xn,Yn)。那么白细胞采集的过程,就可以转化为各个细胞坐标位置的连接过程,即从一个细胞位置到其他所有细胞位置都经过一次的过程。从一个细胞位置到下一个细胞位置的规划都有多种方式,不同的规划方式就会导致采集所有细胞的路径长度不同,也就会影响采集细胞的时间。这样细胞采集的问题就转化为路径规划问题。

2 算法及流程

2.1 传统蚁群算法

蚁群算法是一种根据蚂蚁寻找食物过程中总是按照一定的规则找到蚁窝和食物之间最短路径的方法改进而来的一种智能算法,意大利学者M.Dorigo等人把它应用到求解旅行商问题(Traveling Salesman Problem,TSP)中,得到了比较好的试验效果[6]。那么细胞的坐标位置就相当于TSP中的城市,显微镜物镜就相当于TSP中的旅行商,因此细胞采集问题可以采用蚁群算法进行路径规划。

将整个蚁群中的蚂蚁的数目定为m,将细胞的数目定为n,将细胞i与细胞j之间的距离定为dij(i,j-1,2,…,n),在t时刻,细胞i和细胞j之间的信号通道中的信息素浓度为τij(t)。在开始的时候,由于细胞之间的连接路径中的信息素的含量是一致的,因此可以将τij(0)=τ0。

(1)

ηij(t)是一个启发性的函数,ηij(t)=1/dij,它表示在t时刻蚂蚁从i到j的渴望程度,而allowk(k=1,2,…,m)则表示从蚂蚁k出发的细胞以外的所有细胞的总和,它们的总和被称为allowk,它们的值分别为1、2、m。每当被采集一个细胞,allowk中的细胞就会减少一个,直至allowk中的元素为空,代表所有细胞都已被采集。α是信息素的重要系数,α的值越大,这表明信息素的含量会对转移产生的影响越大。β可以被视为启发函数的一个重要的指标,它的值越高,说明启发函数在迁移过程中的作用就越显著,这意味着蚂蚁可以更有可能迁移到距离较近的细胞。

随着蚂蚁不断释放信息素,它们之间的联系也会变得越来越弱,ρ(0<ρ<1)可以作为一种衡量信息素挥发程度的指标。因此,一旦蚂蚁完成一次循环,就需要及时监测细胞之间的信息素浓度,以确保其正常运转。其计算公式为:

(2)

2.2 人工免疫算法基本思想

人工免疫算法是一种基于免疫学原理的智能计算方法[7],它利用免疫系统的多样性,可以有效地改善种群的多样性,从而解决“早熟”问题,并最终达到全局最优的结果。

人工免疫算法具体实现时主要有三大模块:

(1)初始化抗体,对抗原进行识别。根据需要解决的问题来寻找合适的细胞序列,以用来初始化抗体序列。

(2)克隆筛选。通过不同的免疫操作总结并实现算法中克隆选择的规律和策略。

(3)通过对抗体与抗原的亲和度进行评估,可以实时调整它们之间的匹配度,从而提高抗体与抗原的相互作用效果。

2.3 免疫蚁群算法

2.3.1 算法设计思想

本文提出了一种新的算法即免疫蚁群算法(AIA-ACA),它将人工免疫技术与蚁群算法相结合,以实现更高效的路径规划。该算法分3个阶段完成,首先,利用人工免疫算法初期的快速随机搜索能力,找到一个较为有效的解决方案。其次,经过优化的蚁群算法,能够根据人工免疫算法获取的可行解,生成出更加准确的信息素分布。最后,利用蚁群算法具有正反馈的特性和并行性,提高算法的求解效率,并且在迭代过程中,不断改善信息素挥发因子,从而获得最佳的结果。

2.3.2 人工免疫算子的构造

人工免疫算子可以用来解决细胞采集路径规划问题,包括字符换位、字符移位、字符逆转以及优质字符串的保留等几种形式,可以帮助人们更好地理解细胞采集路径,并且可以更有效地实现这些目标[8]。

(1)字符换位。

字符换位算子可以分为两种:一种是单对字符换位算子,另一种是多对字符换位算子。单对字符换位操作是随机取两个不相等的正整数i、j,然后以一定的概率pc交换抗体A=(c1,c2,…,cn)中的一对字符ci,cj的位置;多对字符换位操作是通过预先确定一个正整数uc,在抗体A=(c1,c2,…,cn)中随机取r(1

(2)字符串移位算子。

字符串移位算子,包括单个字符串移动算子和多个字符串移动算子。单个字符串移位操作是随机选取两个不相等的正整数i,j,在抗体A=(c1,c2,…,cn)中选取一个字符串A1,A1是从ci为始点,cj为终点,长度为j-i的字符串。然后按照一定的概率ps在抗体A中依次往右移动字符串A1,最右边的则移动到最左边的位置。多个字符串移位操作是指多个字符串按照一定的规则同时做字符串移位的操作。这种规则就是先确定一个正整数us,然后在抗体A中随机选取小于us的个字符子串进行移位操作。

(3)逆转算子。

逆转算子是一种用于处理字符串的方法,它可以用于处理单独的字符串或者多个字符串的转换。单个字符串逆转算子是随机选取两个不相等的正整数i、j,在抗体A=(c1,c2,…,cn)中选取一个字符串A1,A1是从ci为始点,cj为终点,长度为j-i的字符串。然后把字符串A1中的字符逆序。多个字符串逆转算子是指多个字符串按照一定的规则同时做字符串逆转操作。这种规则就是先确定一个正整数ui,然后在抗体A中随机选取小于us的个字符子串进行逆序操作。

(4)优质字符串的保留。

优质字符串是指亲和力很大的若干个抗体中包含的相同的字符子串。如果抗体中存在优质字符串,那么就想办法保护这些字符串并且把优质字符串作为一个字符来处理,这种方法就称为优质字符串的保护。

2.3.3 算法基本步骤

根据算法的基本思想,免疫蚁群优化算法的具体流程如图3所示。

图3 免疫蚁群优化算法流程

具体步骤如下:

(1)初始化抗原、抗体、初始参数以及环境条件,以达到最佳效果。

(2)生成初始种群。

(3)计算每个抗体的亲和力。

(4)通过测量抗体的浓度,可以有效地激活或减弱具有较强亲和力的抗体,而对于具有较弱亲和力的抗体,则可以通过降低其浓度来实现调节。

(5)通过采用交叉、变异等技术,可以有效地改善群体的状态,实现群体的更新。

(6)如果求得的结果符合要求,则继续按照(7)的步骤进行,否则重新返回(2)的程序。

(7)使用蚁群算法来构建数据集,并记录其中的元素分布。

(8)重新调整初始参数,以确定状态转换的可能性。

(9)更新信息素。

(10)如果条件被满足,则输出最佳解,并完成搜索。否则,重新进入步骤(8)。

3 仿真实验

为了验证算法的可行性和效果,首先使用通用的TSPLIB中的数据进行仿真实验来验证混合算法的可行性,然后再用真实的细胞数据进行实验来验证混合算法的效果。

3.1 TSP数据实验

在实验开始之前,AIA初始化参数设置为:pc=0.2,ps=0.3,pi=0.4,p0=0.5,uc=us=ui=[n1/4],uc=us=ui=[n1/4]。在每次抗体筛查过程中,将会优先考虑那些能够和抗原相互匹配得更加完美的抗体,然后将这些随机抽取出来的初始抗体经过20次递归迭代进行预处理。在ACA中,将m值调整至3,ρ值调整至0.7,α值调整至0.5,β值调整至0.9,Q值调整至100。数据采用att48和st70两个数据,分别使用AIA、ACA及AIA-ACA 3个算法实验30次,测试结果如表1所示。

表1 3种算法对TSP数据实验结果比较

从表1实验结果可以明显看出免疫蚁群混合算法(AIA-ACA)的精度更高,在att48的实验中,平均解比蚁群算法提高了1.2%,比人工免疫算法提高了2.6%;在st70的实验中,平均解比蚁群算法提高了1.7%,比人工免疫算法提高了3.4%。从标准差的比较也可以看出混合算法的鲁棒性更好,从而证明混合算法是可行的。

3.2 细胞采集数据实验

根据实际情况选择了细胞个数不同的两个标本:A标本31个细胞,B标本100个细胞,分别使用AIA、ACA及AIA-ACA3个算法对A和B两个标本数据进行验证测试,测试结果如表2所示。

从表2实验结果可以看出,免疫蚁群优化算法(AIA-ACA)在两个标本的测试中都可以取得更优解,从平均解可以看出,在31个细胞A标本的实验中,平均解比蚁群算法提高了0.8%,比人工免疫算法提高了3.3%;在100个细胞的B标本的实验中,平均解比蚁群算法提高了0.2%,比人工免疫算法提高了1.0%。同时鲁棒性也更好。

4 结语

在蚁群算法中,蚂蚁会运用一种特殊的正向传播机制以及一种相互促进的相关激励,来加快搜索的进度,但也会导致搜索结果的不稳定,甚至会发生早熟的情况,从而导致种群的局限性。相比之下,免疫算法的免疫算子更加灵活,可以有效地维护种群的多元性,并且可以有效地预防种群的衰落。通过将蚁群与免疫算法相结合,人们可以更好地发挥它们的优势,从而构建一种新的免疫蚁群优化算法,并通过对TSP经典数据的测试来验证免疫蚁群算法的可行性,最后把混合算法应用到细胞采集路径规划中也取得了良好的效果,从而验证了算法的有效性。