张超等：基于自适应搜索的免疫粒子群算法 ·127· 方式：一种是基于矢量矩的浓度机制，另一种是基于海 质粒子，对这些劣质粒子进行疫苗接种，将记忆细胞中 明距离的浓度机制 好的粒子进行繁殖代替这些劣质粒子 基于海明距离是以抗体为出发点，比较抗体之间 这里使用粒子最大浓度值来控制子种群数量，子 的相似度从而判断相似抗体浓度，计算方法如式(4) 种群A和B的种群数分别由式(7)和式(8)计算得出. 和式(5)所示 popA =dM. (7) 1,0.95≤≤1.01， popB =M-popA. (8) p(x）= 式中，popA是子种群A的个体数量；popB是子种群B 0,其他. 的个体数量；M是初始种群个体数量，也是子种群A j=1,2,…,M (4) 和B的总和；d是粒子最大浓度值 d(x)=P() 当粒子分散时，整个粒子群多样性好，不容易陷入 ,i=1,2,…,M (5) 局部最优，这个时候子种群A数量大些，子种群B数 式中，P(x,)是代表种群中有多少粒子与第i个粒子相 量少些，使整个粒子群朝着最优解进化.当粒子群过 似的相似度值.当粒子与某个粒子各个维度都相近 于集中时，整个粒子群多样性差，容易陷入局部最优， 时，判定二者相近，取值为1，否则为0.d(x)是第i个 这个时候则子种群B数量大些，子种群A少些，确保 粒子的浓度 一部分优秀粒子进化的同时，另一部分劣质粒子去周 基于矢量矩是从抗体对抗原的抵抗力为出发点， 围搜寻，增大整个种群的多样性 比较各个抗体对抗体的抗原反应，从而判断相似抗体 动态改变子种群数目相当于控制两种算法的作用 浓度，计算方法如下式所示： 大小.这样可以使种群过于拥挤时改善其多样性，使 三)-1 种群始终朝着更好的方向进化 2.2自适应搜索的实现 d(x:）= i=1,2,…,M 传统免疫粒子群算法的接种方式都有所欠缺，如 If(x;)-f(x)I 果能将两种方式结合，在保证优秀粒子的情况下增加 (6) 随机性，这样能够在提高种群质量的同时，改善其多 两种浓度机制都可以提高种群多样性，基于海明 样性. 距离的浓度机制比基于矢量矩的浓度机制更准确，但 自适应免疫粒子群算法采用两种接种方式相结合 也会消耗更多的时间. 的方式，在继承优秀粒子的基础上，添加一些随机范围 1.2.3浓度调节机制 搜索.结合方式是以记忆库中存入的gbest为中心，在 当需要大量优秀抗体来代替劣质抗体时，疫苗接 其周围随机范围搜索 种机制会将记忆库中的优秀抗体取出进行繁殖进化来 Vaccine(x)gbest range(t),i=1,2,...,popB. 代替种群中的劣质抗体，提高种群质量. (9) 2自适应搜索免疫粒子群算法 range(t)rand x R(t). (10) 式中，Vaccine是接种疫苗，range(t)是第t代搜索范 2.1算法基本思想 围，R()是第t代搜索半径.可见每一个接种疫苗都 传统免疫粒子群算法通常采用串联方式，即在种 是落在群体极值周围的一个随机值. 群更新时，先通过人工免疫算法对种群进行优劣选择， 这样在优秀粒子周围可变范围内产生一些随机粒 再通过标准粒子算法进行种群更新.虽然在种群多样 子，保证继承优秀的基础上又不缺乏多样性.这里可 性方面提高了很多，但是在进化初期粒子群种群多样 变范围也需要粒子最大浓度控制，当粒子最大浓度比 性充足时引入浓度机制和疫苗接种反而会降低种群的 较高时，需要增加搜索范围，使疫苗接种的粒子分散在 多样性.因此，需要在种群进化初期即多样性充足时 群体极值周围大范围内，增加种群多样性.当粒子最 减少人工免疫算法的作用，提高算法效率：在进化后期 大浓度比较低时，说明粒子群不缺乏多样性，需要减少 加大人工免疫算法作用，防止早熟停滞 搜索范围，使疫苗粒子在群体极值周围小范围寻找最 本文提出的自适应免疫粒子群算法采用并联方 优解 式，即在种群更新时，经典粒子群算法和人工免疫算法 具体实现方法是以群体极值为圆心，初始搜索范 是同时进行的.它将种群分为两个数目可变的子种群 围是以粒子群速度极V为半径的圆，之后在上一代 A和B.子种群A是保留那些适应度高浓度低的优秀 搜索范围的基础上改变，根据当前粒子最大浓度来控 粒子的种群，进行速度和位置更新，使整个种群朝着最 制搜索半径范围.搜索规则采用先验经验知识设置. 优解进化：子种群B是含有一些适应度差浓度高的劣 R(1)=Vs, (11)张 超等: 基于自适应搜索的免疫粒子群算法 方式:一种是基于矢量矩的浓度机制,另一种是基于海 明距离的浓度机制. 基于海明距离是以抗体为出发点,比较抗体之间 的相似度从而判断相似抗体浓度,计算方法如式(4) 和式(5)所示. 籽(xi) = 移 M j = 1 1, 0郾 95臆 xi xj 臆1郾 01, 0, 其他 { . j = 1,2,…,M. (4) d(xi) = 籽(xi) M , i = 1,2,…,M. (5) 式中,籽(xi)是代表种群中有多少粒子与第 i 个粒子相 似的相似度值. 当粒子与某个粒子各个维度都相近 时,判定二者相近,取值为 1,否则为 0. d(xi)是第 i 个 粒子的浓度. 基于矢量矩是从抗体对抗原的抵抗力为出发点, 比较各个抗体对抗体的抗原反应,从而判断相似抗体 浓度,计算方法如下式所示: d(xi) = 移 M j = 1 | f(xi) - f(xj) | 移 M i = 1 移 M j = 1 | f(xi) - f(xj) | , i = 1,2,…,M. (6) 两种浓度机制都可以提高种群多样性,基于海明 距离的浓度机制比基于矢量矩的浓度机制更准确,但 也会消耗更多的时间. 1郾 2郾 3 浓度调节机制 当需要大量优秀抗体来代替劣质抗体时,疫苗接 种机制会将记忆库中的优秀抗体取出进行繁殖进化来 代替种群中的劣质抗体,提高种群质量. 2 自适应搜索免疫粒子群算法 2郾 1 算法基本思想 传统免疫粒子群算法通常采用串联方式,即在种 群更新时,先通过人工免疫算法对种群进行优劣选择, 再通过标准粒子算法进行种群更新. 虽然在种群多样 性方面提高了很多,但是在进化初期粒子群种群多样 性充足时引入浓度机制和疫苗接种反而会降低种群的 多样性. 因此,需要在种群进化初期即多样性充足时 减少人工免疫算法的作用,提高算法效率;在进化后期 加大人工免疫算法作用,防止早熟停滞. 本文提出的自适应免疫粒子群算法采用并联方 式,即在种群更新时,经典粒子群算法和人工免疫算法 是同时进行的. 它将种群分为两个数目可变的子种群 A 和 B. 子种群 A 是保留那些适应度高浓度低的优秀 粒子的种群,进行速度和位置更新,使整个种群朝着最 优解进化;子种群 B 是含有一些适应度差浓度高的劣 质粒子,对这些劣质粒子进行疫苗接种,将记忆细胞中 好的粒子进行繁殖代替这些劣质粒子. 这里使用粒子最大浓度值来控制子种群数量,子 种群 A 和 B 的种群数分别由式(7)和式(8)计算得出. popA = dmaxM. (7) popB = M - popA. (8) 式中,popA 是子种群 A 的个体数量;popB 是子种群 B 的个体数量;M 是初始种群个体数量,也是子种群 A 和 B 的总和;dmax是粒子最大浓度值. 当粒子分散时,整个粒子群多样性好,不容易陷入 局部最优,这个时候子种群 A 数量大些,子种群 B 数 量少些,使整个粒子群朝着最优解进化. 当粒子群过 于集中时,整个粒子群多样性差,容易陷入局部最优, 这个时候则子种群 B 数量大些,子种群 A 少些,确保 一部分优秀粒子进化的同时,另一部分劣质粒子去周 围搜寻,增大整个种群的多样性. 动态改变子种群数目相当于控制两种算法的作用 大小. 这样可以使种群过于拥挤时改善其多样性,使 种群始终朝着更好的方向进化. 2郾 2 自适应搜索的实现 传统免疫粒子群算法的接种方式都有所欠缺,如 果能将两种方式结合,在保证优秀粒子的情况下增加 随机性,这样能够在提高种群质量的同时,改善其多 样性. 自适应免疫粒子群算法采用两种接种方式相结合 的方式,在继承优秀粒子的基础上,添加一些随机范围 搜索. 结合方式是以记忆库中存入的 gbest 为中心,在 其周围随机范围搜索. Vaccine(xi) = gbest + range(t), i = 1,2,…,popB. (9) range(t) = rand 伊 R(t). (10) 式中,Vaccine 是接种疫苗,range( t) 是第 t 代搜索范 围,R(t)是第 t 代搜索半径. 可见每一个接种疫苗都 是落在群体极值周围的一个随机值. 这样在优秀粒子周围可变范围内产生一些随机粒 子,保证继承优秀的基础上又不缺乏多样性. 这里可 变范围也需要粒子最大浓度控制,当粒子最大浓度比 较高时,需要增加搜索范围,使疫苗接种的粒子分散在 群体极值周围大范围内,增加种群多样性. 当粒子最 大浓度比较低时,说明粒子群不缺乏多样性,需要减少 搜索范围,使疫苗粒子在群体极值周围小范围寻找最 优解. 具体实现方法是以群体极值为圆心,初始搜索范 围是以粒子群速度极 Vmax为半径的圆,之后在上一代 搜索范围的基础上改变,根据当前粒子最大浓度来控 制搜索半径范围. 搜索规则采用先验经验知识设置. R(1) = Vmax, (11) ·127·