A Binary Particle Swarm Optimization Algorithm For Uncapacitated

自适应粒子群算法自适应粒子群算法（Adaptive Particle Swarm Optimization，APSO）是一种基于群体智能的优化算法，它模拟了鸟群觅食行为中的信息共享和合作策略，通过不断调整粒子的位置和速度来寻找最优解。

在APSO算法中，粒子代表了解的候选解，它们通过不断更新自身的位置和速度来搜索最佳解。

与传统的粒子群算法不同之处在于，APSO算法引入了自适应机制，使得粒子的搜索能力和适应度可以根据问题的特点进行调整。

APSO算法需要初始化一组粒子的位置和速度。

初始位置可以通过随机生成或根据问题的特点进行设定。

初始速度可以根据粒子的邻居粒子的位置和速度进行计算。

然后，APSO算法通过迭代更新粒子的位置和速度，直到达到停止条件。

在每次迭代中，粒子根据自身的历史最优解和全局最优解来更新速度和位置。

具体而言，粒子的速度更新公式如下：\[ V_i(t+1) = w \cdot V_i(t) + c_1 \cdot rand() \cdot (Pbest_i(t) - X_i(t)) + c_2 \cdot rand() \cdot (Gbest(t) - X_i(t)) \]其中，\(V_i(t+1)\)为粒子的速度，\(w\)为惯性权重，\(V_i(t)\)为上一次迭代的速度，\(c_1\)和\(c_2\)为学习因子，\(rand()\)为随机数函数，\(Pbest_i(t)\)为粒子的历史最优解，\(X_i(t)\)为粒子的当前位置，\(Gbest(t)\)为群体的全局最优解。

粒子的位置更新公式如下：\[ X_i(t+1) = X_i(t) + V_i(t+1) \]在更新完所有粒子的位置和速度后，需要计算粒子的适应度，并更新粒子的历史最优解和全局最优解。

适应度的计算方法根据具体问题而定。

APSO算法引入了自适应机制，通过动态调整学习因子和惯性权重来提高搜索效率。

学习因子可以根据粒子的适应度进行调整，适应度越高，学习因子越小，粒子的搜索范围越小；适应度越低，学习因子越大，粒子的搜索范围越大。

python 二进制离子群算法二进制离子群算法（Binary Particle Swarm Optimization，简称BPSO）是一种优化算法，常用于解决多维优化问题。

它基于粒子群优化算法（Particle Swarm Optimization，简称PSO）的思想，但引入了二进制编码来表示解空间中的候选解。

BPSO算法的基本思想是将每个粒子看作一个二进制向量，其中每个元素可以取0或1，代表解空间中的一个候选解。

每个粒子根据自身的历史最优解和全局最优解进行更新，以寻找更优的候选解。

更新过程中，粒子会根据一定的概率进行二进制变异，从而增加搜索空间的多样性。

具体算法步骤如下：1. 初始化粒子群的位置和速度，每个粒子的位置是一个二进制向量，速度是一个与位置相同长度的二进制向量。

2. 计算每个粒子的适应度值，并更新个体历史最优解和全局最优解。

3. 根据个体历史最优解和全局最优解，更新每个粒子的速度和位置。

4. 根据一定的概率对每个粒子的位置进行二进制变异。

5. 如果满足停止条件，结束算法；否则，返回步骤2。

BPSO算法通过不断迭代更新粒子的位置和速度，以寻找适应度更高的候选解。

相比于传统的PSO算法，BPSO算法的主要优势在于可以处理离散优化问题，并且使用二进制编码可以降低计算复杂度。

在使用BPSO算法时，需要根据具体问题进行适当的参数设置，如粒子数量、迭代次数、速度和位置的更新公式等。

同时，适应度函数的设计也是关键，需要根据具体问题的特点来定义。

下面是一个简单的Python示例代码，演示了如何实现BPSO算法：```pythonimport numpy as npdef fitness_function(position):# 计算适应度函数值return np.sum(position)def binary_mutation(position, mutation_rate):# 二进制变异mutated_position = position.copy()for i in range(len(position)):if np.random.rand() < mutation_rate:mutated_position[i] = 1 - mutated_position[i]return mutated_positiondef bpso_algorithm(num_particles, num_dimensions, max_iterations, mutation_rate):# 初始化粒子群particles = np.random.randint(2, size=(num_particles,num_dimensions))velocities = np.random.randint(2, size=(num_particles, num_dimensions))personal_best_positions = particles.copy()global_best_position = particles[np.argmax([fitness_function(p) for p in particles])]# 迭代更新for _ in range(max_iterations):for i in range(num_particles):# 更新速度和位置velocities[i] = velocities[i] + np.random.rand() * (personal_best_positions[i] - particles[i]) + np.random.rand() * (global_best_position - particles[i])particles[i] = np.round(1 / (1 + np.exp(-velocities[i])))# 更新个体历史最优解和全局最优解if fitness_function(particles[i]) > fitness_function(personal_best_positions[i]):personal_best_positions[i] = particles[i]if fitness_function(particles[i]) >fitness_function(global_best_position):global_best_position = particles[i]# 二进制变异particles[i] = binary_mutation(particles[i], mutation_rate)return global_best_position# 示例用法best_solution = bpso_algorithm(num_particles=50, num_dimensions=10, max_iterations=100, mutation_rate=0.01) print(best_solution)```这段代码演示了使用BPSO算法求解一个10维优化问题，包含50个粒子，迭代100次，二进制变异概率为0.01。

小型微型计算机系统Journal of Chinese Computer Systems 2021年1月第1期Vol.42 No.12021针对W SN异常数据检测改进的孤立森林方法吴志强、张胜li2,包晓玲2,田纪彪\戴维凯\张士进1y南昌航空大学信息工程学院，南昌330063)2(南昌航空大学物联网研究所，南昌330063)E-mail ：zwxzsl68 @ 126. com摘要•.异常数据检测一直是无线传感器网络安全的重要防护手段.针对现有方案计算复杂度高和检测精度低等问题，提出一 种离散二进制粒子群优化孤立森林算法（BPSO-i F o r e s t).依据选择性集成思想，利用离散二进制粒子群算法改进由孤立森林算 法生成的初始森林，选取初始森林中精度高、差异性大的隔离树，构建最优孤立森林,提升异常数据的检测精度和算法的执行效 率•在无线传感器网络数据集上，与传统孤立森林、随机森林算法及其改进算法进行对比实验，结果表明本算法的检测精度和执 行效率有明显的提升.关键词：异常数据检测;孤立森林;选择性集成;B P S O-i F o r e s t中图分类号.■TP391 文献标识码:A文章编号：1000-1220(2021)01~0127>05Improved Isolation Forest Method for WSN Anomaly Data DetectionW U Z h i-q i a n g1,ZHANG S h e n g1,2,BAO X i a o-l i n g2,TIA N J i-b i a o1,D AI Wei-k a i1.ZHANG S h i-j i n11 (School of Inform ation Engineering,Nanchang Hangkong University,Nanchang 330063.China)2 (Internet of Things Institute,Nanchang Hangkong University,Nanchang 330063 .China)A b s t r a c t：A b n o r m a l d a t a d e t e c t i o n h a s a l w a y s b e e n a n i m p o r t a n t m e a n s o f p r o t e c t i o n f o r w i r e l e s s s e n s o r n e t w o r k s e c u r i t y.A i m i n g a t t h e p r o b l e m s o f h i g h c o m p u t a t i o n a l c o m p l e x i t y a n d l o w d e t e c t i o n a c c u r a c y o f t h e e x i s t i n g s c h e m e s,a d i s c r e t e b i n a r y p a r t i c l e s w a r m o p t i m i z a t i o n i s o l a t i o n f o r e s t a l g o r i t h m(BPSO-i F o r e s t)w a s p r o p o s e d.B a s e d o n t h e i d e a o f s e l e c t i v e i n t e g r a t i o n,t h e d i s c r e t e b i n a r y p a r-t i c l e s w a r m a l g o r i t h m i s u s e d t o i m p r o v e t h e i n i t i a l f o r e s t g e n e r a t e d b y t h e i s o l a t i o n f o r e s t a l g o r i t h m，t h e i s o l a t i o n t r e e w i t h h i g h a c c u-r a c y a n d l a r g e d i f f e r e n c e i n t h e i n i t i a l f o r e s t i s s e l e c t e d t o c o n s t r u c t t h e o p t i m a l i s o l a t i o n f o r e s t t o i m p r o v e t h e a c c u r a c y o f a b n o r m a l d a t a d e t e c t i o n a n d a l g o r i t h m e x e c u t i o n e f f i c i e n c y.T h e w i r e l e s s s e n s o r n e t w o r k d a t a s e t i s c o m p a r e d w i t h t r a d i t i o n a l i s o l a t i o n f o r e s t,r a n­dom f o r e s t a l g o r i t h m s a n d i t s r e v i s e d m e t h o d.T h e r e s u l t s s h o w t h a t t h e d e t e c t i o n a c c u r a c y a n d e x e c u t i o n e f f i c i e n c y o f t h e a l g o r i t h m h a v e b e e n s i g n i f i c a n t l y i m p r o v e d.Key w o r d s：a b n o r m a l d a t a d e t e c t i o n；i s o l a t e d f o r e s t；s e l e c t i v e e n s e m b l e；B P S O-i F o r e s ti引言无线传感器网络（w i r e l e s s s e n s o r n e t w o r k，W S N)在关键 军事、基础设施状态、生态环境和医疗系统等监测方面起着不 可或缺的作用[1].针对W S N开放性和分布式的性质及传感 器节点资源受限、能量较低等特点，攻击者可能会对节点监听 节点、控制节点更改数据的完整性并浪费网络资源甚至毁坏 节点，因此保障无线传感器网络的通信和数据安全是网络正 常运作的一个必要前提.现阶段,W S N的网络安全研究在密 钥管理、身份验证、隐私、安全路由等方向都有着长足的发展[2].但是一方面，传感器节点无法长久的支撑一些复杂的 加密算法导致寿命降低;另一方面，当传感器节点遭到人侵或 者破坏后，密码学等安全机制的有效性将大大降低，因此需要 引人其他可以保障W S N的信息安全的机制.异常数据检测 是对W S N网络安全的一种补足，它可以根据对传感器节点的状态数据进行分析来检测和识别网络中已知的和未知的攻 击行为，对携带异常数据的节点进行响应处理来保障W S N 的信息安全_现阶段国内外提出的W S N异常数据的检测的方法大致 可以分为5类:基于近邻和聚类的方法、基于分类的方法、基 于统计的方法、基于机器学习的方法及基于信息论的方法[3].L i G等人[<]提出了一种在广域无线传感器网络中的异 常检测方法，作者利用k u l l b a c k-l e i b l e r散度通过簇头将簇中每个传感器的测量值与其他传感器进行比较,实验表明对该 方法有很好的检测效果,但是随着数据维度变高算法的复杂 度呈指数增长.E m a d i H S等人[5]介绍了一种密度空间聚类 算法（DBSCAN)与S V M相结合的W S N异常检测模型，模型 先通过DBSCAN算法对网络数据进行聚类，将低密度区域中 的点设为异常点，再用正常数据训练S V M.文中只选用温度、湿度和电压3个特征进行检测,用较低的算法复杂度得到比收稿日期：202(M)1>06 收修改稿日期：202(M)3>04基金项目：国家自然科学基金项目（61661037 )资助；江西省教育厅科技项目 (GJJ170575)资助.作者简介：吴志强，男，1995年生，硕士研究生，研究方向为无线传感器网络信息安全;张胜，男，1968年生，博士，副教授，CCF高级会员，研究方向为无线传感器网络、复杂网络与数据挖掘;包晓玲，女，1973年生,工程师，研究方向为无线传感器网络；田纪彪，男，1995 年生，硕士研究生，研究方向为无线传感器网络;戴维凯，男，1994年生，硕士研究生，研究方向为复杂网络；张士进，男，1992年生，硕士研究生，研究方向为复杂网络.128小型微型计算机系统2021 年较好的检测精度，并没有证明算法在髙维数据上的有效性.费 欢等人[6]提出了一种基于K -meam 算法思想的W SN 异常数 据检测算法，文章中以欧式距离为指标计算实例的相似度来 聚类，实验证明在数据量大于1000时算法的检测效果较好， 但是当数据量级增大时，算法效率大大降低.连超等人[7]提 出了一种基于深度置信网络（DBN)集成学习的异常检测模 型,模型中时序数据进行降维处理通过D B N 实现，异常数据 的检测通过结合逻辑回归和受限玻尔兹曼机来实现，最后通 过弱分类器投票判断数据集中的异常数据.顾晓勇等人[8]利 用NMEA 算法全局搜索能力对BPNN 的参数进行优化从而 获得最优权阈值来提高异常检测的准确性，提出了一种有效 应用于WSN 异常数据检测的算法NMEA-BP. Zamry N M 等 人[9]提出了一种针对WSN 异常的SVM 改进检测模型，模型 中直观无协方差增量主成分分析（CCIPCA)算法对数据降 维，居中超椭球面支持向量机（CESVM)被用作分类器，实验 表明该模型对W SN 异常数据的检测能力优于其他方法，但 是CCIPCA 算法对于不同类型数据的普适性不强.许欧阳[1°] 提出了一种利用变异二进制萤火虫（MBGSO)算法对随机森 林（RF)进行选择性集成寻优的W SN 异常检测算法（MBG-SO-ARF ),实验结果表明模型的适应能力有了一定提高，集成分类器的泛化能力和准确度有所提髙，但是其算法时间复 杂度较高.针对上述文献中出现的问题，本文将孤立森林（I s o l a t i o nF o r e s t 或i F o r e s t )引入W S N 异常数据的检测，并对原始孤立森林的不足进行了改进.孤立森林由Liu 等[n ]首次提出，该 算法的不同之处在于，现有的大部分异常检测方法是根据正 常数据来构建模型，再将与模型不符合的数据划分为异常，而 孤立森林则是利用异常数据占比少且偏离群体的特点，将其 与正常数据快速分割，所以算法本身具有较低的线性时间复 杂度和内存需求低等优点.尽管孤立森林在异常检测算法中有一定的优越性，但仍存在一些需要改进的问题：1) 孤立森林的高检测精度依赖大规模隔离树（i T r e e )的集成，训练大量i T r e e 会造成算法效率的降低和更多的内存消耗；2) 在孤立森林中每棵隔离树的检测能力不同，但是它们所具有的投票权重是一样的，所以一些检测能力不足的树可能会对最终检测结果产生负作用.为此,本文提出了一种新的BPSO -i F o r e s t 的数据异常检测算法,该算法利用二进制粒子群优化算法（BPSO )优化i F ­o r e s t 来增强对 W SN 异常数据的检测精度和执行效率.2孤立森林算法孤立森林与其他集成选择方法一样，由多个基分类器构建，孤立森林里的基分类器就是i T r e e .在i T r e e 构建过程中， 先随机选取数据集D = K ,d 2 ,•••1中的一个特征v v ,然后随机选择一个切割值P ,切割值的取值范围在所选特征的上 下界之间，数据则被切割值划分为左右两部分，若c /, (w ) >P , 数据r f ,被划分在右子树,反之则划分在左子树，如此递归，直 到将每个数据与其他数据完全分割或者达到设定树的最大高 度则停止划分.由于异常值远比正常值要少且在某个或多个 维度上的值与正常值存在明显差异，异常值往往更靠近树的根节点，所以将一个“异常值”与其余数据分割开比将一个 “正常值”与其他数据分割开要容易的多.由于i T r e e 的结构与二分查找树（BST )相同，所以i T r e e 的路径长度相当于BST 中查询失败的路径长度，下面引人路 径长度的定义.定义1.(路径长度）从根节点遍历i T r e e 直到外部节点处 终止，其中所经历的边长为路径长度，记为A U ).参照二分査找树査询失败的路径长度，实例x 的路径长 度公式如公式（1)所示：- \ ) -2(f/r - 1 )/i /r ,i f / >2c ((/r ) = I1， 中=2(1)L 0，otherwise其中,H (f ) =!«(〇 +y 为谐波数;少为叶子节点数;C (<A )为当少确定时A U )的平均值，用来标准化A U ).任何异 常检测的方法都需要异常分数，实例X 的异常分数是根据遍 历X 在所有i T r e e 中的路径长度来确定的，其异常分数如公式 (2)所示：, ,E l h l x ))^=2(2)其中£()是A U )在隔离树集合上的平均值，当：£(A (j c ))-K ：(n ),s —0_5,样本可能没有明显的异常点；£(A (;c ))—0 j —l ,可以被认为是异常点；£(/i (;c ) )—/I - l ,n >1,5—0,可以被认为是正常点•3离散二进制粒子群优化算法粒子群算法表示在一个初始化的粒子群中，每个粒子的位置与速度随机产生，粒子位置代表着当前的解，而速度代表 着粒子当前解与下一个解的矢量方向，在解空间中，粒子根据 自己和群体以往移动的经验不断调整速度搜索最优解.在D维解空间随机构建一组粒子M ,当前迭代次数为K =(<，4 …,4D )表示粒子群中的一个粒子.粒子|当前的速度表示为= …，V f 0);在算法迭代过程中粒子i 与种群经历过的最好位置分别表示为P , = ，…,P ,D )和A =…,Ps D ),其中个体最好位置记为个体极值，种群则记为群体极值.个体极值与群体极值始终影响着粒子的速度与位置，牵引着粒子不断向最优解靠近[12].粒子速度和位置更新公式如下：= id "*■ ^"l ( P id^id ) ^2 ^2 ( Pgd ~ ^) ( 3 )4+，=4+v L +，,(l ^i ^M ,l ^^D ) (4)其中，口^和/V 分别代表个体极值（沖M )和群体极值(沙咖）.〇>是训练过程中调整的惯性权重[13] ,C l ，c 2是经验设定的常量，/^在[0,1 ]的取值随机.本文中i F o r s e s t 的集成选择问题属于离散性问题，而标 准PSO 算法主要针对的是连续性问题,因此对于这类离散型 问题,K e n n e d y J 等人[1<1提出了离散二进制粒子群优化BPSO(B i n a r y P a r t i c l e Swarm O p t i m i z a t i o n )算法.在BPSO 中，速度的更新公式与标准PSO —样,但是每 个粒子的位置只能由二进制数〇或1来表示•粒子下一次位置是否更新取决于速度在s i g m o i d (5)函数映射下的值是否 达到更新的条件：吴志强等:针对WSN异常数据检测改进的孤立森林方法129 1期J(v w)是一个在[0，1]之间的数，它表示位置心取1的概率.(■1幻（v w)〜 = ,(6)L〇o t h e r w i s er a«d()是取自[0,1]之间的随机数，粒子的速度需要被限制在v a e[ - V…… ,].针对BPSO算法后期搜索能力不足难以跳出当前局部最优解的问题，本文引用王越等人[15]的非线性惯性权重w来增强算法的后期寻优能力#公式如公式(7)所示.fw— + 一a r c t a n[7r t(c-]0.4 9〇0.9(7)其中f代表当前迭代次数，r代表最大迭代次数.〇>在 [0.4,0. 9]的范围内呈非线性增长，初始值为0.4,在达到 0.9时值保持不变，后期较大w值可以易于算法跳出当解区 域寻找全局最优解.4改进后的孤立森林算法根据21〇1!116]提出的“部分或许优于整体”的选择性集成 (s e l e c t i v e e n s e m b l e,SEN)思想，在集成模型中，选择出其中更 优秀的个体子集可以达到甚至超过整体集合的效果.基于BP-S O对i F o r s e t进行改进的方法思想是:对在训练集D中已产生 的i T r e e集合T中,通过BPSO算法寻找最优子集r来达到在 降低基分类器数置的同时提升分类精度和执行效率的需求.在选取基分类器上一般遵守两个原则：1)选择精度较高 的;2)选择差异度大的.选择精度髙的基分类器是因为i F o r e s t 是一种采取基分类器投票选择的集成分类器，低精度的i T r e e 可能对最终判断产生误导作用.而选择差异度大的基分类器 可以互补基分类器之间得到的不同信息可以增加i F o r e s t的泛化能力.在孤立森林中，每棵树的构造方式相同但是由于训练的 数据或者参数不同会导致每棵树的检测能力不同，对于检测 能力的区分，本文采用交叉验证法来计算每棵树的检测能力.所有的异常数据被分成份，每棵i T r e e随机在f l份中进 行训练，然后在未训练的数据中进行测试，记录每次当前i T r e e的精度值并取平均精度值A,其中A越大代表精确度越 好.使用交叉验证法计算i T r e e的精度值可以更公平客观的反 应每颗i T r e e的检测能力.其次,用公式(8)和公式(9)来计算 每颗i T r e e之间的差异度和所有i T r e e之间的平均差异度：Qu W2〜(8)Q i =(9)其中A.和' 表示树和7}分别在样本空间D中正确 检验的样本个数,\表示r,和7；重合正确检测的样本个数. 2,，[0,1],5,£[0,1].%和立.的值与i T r e e之间的差异度 呈正相关.综合考虑精度和差异度需求,寻找出一个可以平衡 这两点因素的适应度函数如公式（10)所示：F{r) =,i a I\Q'(10)A=l M(11)Q f-1M-=¥,?〗e‘(12)M和A分别表示精度和差异度的权重,M代表当前所选 出i T r e e数量,^表示当前参与集成的i T r e e的平均精度，计算公式如公式（11)所示，表示当前参与集成的i T r e e的平均差异度，计算公式如公式（12)所示.本文使用BPSO算法对I-s o l a t i o n F o r e s t进行选择性集成，将i F o r e s t中的所有i T r e e进行二进制编码,'r表示当前为选中状态，'〇'表示未选中，具体算法步骤如下：算法.B P S O-i F o r e s t输入:样本集D;粒子个数W;迭代次数C;Step 1.设置i T r e e的初始参数；Step 2.构建L棵iTree组成初始森林r;Step 3.初始化粒子速度、位置、个体和全体极值等参数.每个粒子含有i维元素，其中每个元素对应T中的一棵i T r e e,元素的取值非0即1.T代表当前i T r e e参与集成，'0'表示不参与；Step 4.样本集D对参与集成的iTree进行训练,分别用 交叉验证和统计法计算当前子集的平均精度值和平均差异值，并计算粒子当前适应度值；Step 5.根据适应度值，更新粒子群和Step 6.根据公式(7)对惯性权重进行更新；Step 7.根据公式(3)和公式（6)来更新粒子的速度和位 置；Step 8.当粒子群极值迭代到最优解或者迭代次数> C,输出最优解，否则返回S t e p2.输出：历史寻优过程中的最优解冲和最优子集合r.此时的最优子集合r即需要寻找的同时满足高精度值与髙差异度的森林,训练好的森林r'可以直接用于待检测的数据的异常分数计算.5实验结果及分析为了验证BPSO-i F o r e s t对W S N中的异常数据划分的精 确度,本文引人异常检测常用指标A U C(A r e a U n d e r C u r v e)对算法检测性能进行检验，并画出一些典型实验的R〇C曲线对比图.A U C等于R O C曲线与坐标轴围成的面积，其值越接近1说明分类精度越高.表1异常数据集T a b l e 1A b n o r m a l d a t a s e t异常类型元素数目Blackhole10049Grayhole14596Flooding3312Scheduling6838Normal340066本文的实验数据集W S N-D S来自Al momani I等人[n],作者等人利用NS2仿真软件模拟一组在L EA CH协议下运行的无线传感器网络，并在网络中添加4种DoS攻击模型，分别是 B l a c k h o l e、F l o o d i n g、S c h e d u l i n g 和 G r a y h o l e .并在每运行130小型微型计算机系统2021 年AUC--R F---M B G SO -A RF —iForest-----BPSO-iForest0.2 0.4 0.6 0.8 1.0False positive rate 6结论本文结合孤立森林和离散二进制粒子群优化算法，依据由实验结果可得知，BPSO -i F o r e s t 对W S N 异常数据f 的效果十分显著.由图1和图2可得知，检测同一类型异1 据的时候，检测的准确度与数据规模大小有很大关系.在赛 规模数据集 S a m p l e -F D 中 B P S O -i F o r e s t 和 MBGSO-ARF { i F o r e s 和RF ,总的来看差别很小，这是因为较小数据集中j 数据分布较为稀疏所以易于划分.而对于较大的数据集，E 异常数据量大且较密集,RF 算法精度下降较多，i F o r e s t 由= 原理特性是把异常数据进行隔离而不是对常规实例进行5 再检测不符合模型的数据，在大数据集上的处理比R F 更J 势,BPSO -i F o r e s t 和MBGSO -A R F 由于其精度高差异度大^分类器使其在处理较大异常数据上表现更好，而BPSO -i F (的基分类器的分类效果强于MBGSO-ARF 所以集成分类.在处理效率上差距明显，i F o r e s t 系列算法由于省去了基于距离 或者密度方法的计算消耗，执行效率远大于R F 和MBGSO -ARF 算法.从时间复杂度来看，R F 在训练阶段与测试阶段的时间复杂度分别为 ^ l o g m )和 <9(Lm l o g m )，MBGSO-ARF相较R F 降低了时间复杂系数，一定程度上提升了算法效率.i F o r e s t 在训练阶段与测试阶段的时间复杂度分别为l o g(m ))和（?( M l o g (m )). R F 和MBGSO -ARF 在构建过程中需 要计算基尼系数来选取特征，消耗了大量时间,所以在执行效率方面远不如i F o r e s t . BPSO -i F o r e s t 在训练阶段与测试阶段的 时间复杂度分别为〇a (h l 〇g (m ) +1))和0(”/l o g (m )). 在大规模数据集中,BPSO -i F o r e s t 较i F o r e s t 在处理时间上都有 大幅的缩减.由于在计算复杂度方面BPSO -i F o r e s t 具有更小的 常数，它在原始规模为/■的森林中选出了/棵精度高且差异度 大的数组成最优子森林，缩小了森林的规模，提升了算法的执 行效率，证实了算法在W S N 异常数据检测上的优越性.图 1 Sa mp l e -G H ROC 曲线图 2 F i g . 1 S a mp le -G H ROC c u r v eF i g . 2一段时间后收集当前时刻所有节点的数据,每组数据含有23 种有效特征,特征中包含节点消耗的能量、当前节点与族头 (C H )的距离、C H 广播的消息数量、节点与C H 之间的通信消 息数等.W S N -D S 数据集中数据属性分布见表1.实验条件为 载有 I n t e l ( R ) C o r e ( T M ) i 7-7800X CPU @ 3. 50Hz 主频， 128G 内存的主机，搭配64位Windows 10操作系统，实验使 用P y t h o n 3.6在Pycharm 环境中实现.BPSO -i F o r e s t 参数：粒 子个数设置《 = 1〇〇,迭代次数C = 100,树的高度限制/ = 100,采样大小m = 256.5.1算法精度对比为了从多个角度探讨本实验方案的优劣，我们先从数i中等比例随机选出800个包含正常数据和G r a y h o l e 类型异常 数据样本数据，随机选取样本中的60%为训练集，剩下的40% 样本为测试集，再对此样本数据中的G r a y h o l e 类型异常数据进 行检测，将此小样本数据集称为S a m p l e -G H .分别用BPSO -i F ­o r e s t , i F o r e s t 和随机森林 （RF ) 及文献 [10] 中的 MBGSO-ARF算法对S a m p l e -G H 进行精度测试.图1给出了测试的R O C 曲 线.随后对4种攻击产生的所有异常数据进行检测.实验过程 中随机选取的训练集与测试集分配比例与S a m p l e -G H 方案一 致.将所有数据集用4种算法分别求4种类型攻击的A U C 值, 10次实验后取平均值,得出结果如表2所示，并画出的F l o o d -最好.分析图3和表2,在检测G r a y h o l e 和B l a c k h o l e 这两种异 常数据更多更密集的攻击中,4种算法的检测率都有不同程度 的降低，而BPSO -i F o r e s t 算法仍具有较高的检测率，说明其在 处理含有大量异常数据的数据集中会更具优势.表2 4种算法对不同异常类型下检测的A U C 值T a b l e 2 AUC v a l u e s d e t e c t e d b y f o u r a l g o r i t h m su n d e r d i f f e r e n t t y p e s o f e x c e p t i o n s异常类型BPSO-iForestiForest MBGSO-ARFRF Blackhole 0.940.830.870.76Grayhole 0.970.850.880.75Flooding 0.980.900.930.87Scheduling 0.970.860.910.80Sample-GH10.9910.995.2算法执行效率对比为了验证算法的执行效率，用4种算法分别检测这4种 异常的攻击类型，综合实验10次完成检测的时间.表3列出 了 BPSO -i F o r e s t 、i F o r e s t 、RF 和 MBGSO-ARF 对不同类型异常 的检测时间.居集 i n g 和G r a y h o l e 类型异常的R O C 曲线如图2和图3.AUC，—R F---M BGSO-ARF—iForest----BPSO-iForest0. 2 0. 4 0. 6 0. 8 1. 0False positive rateF l o o d i n g ROC 曲线F l o o d i n g ROC c u r v el 〇a 〇p 〇AUC°0,,••• -----MBGSO-ARF—iForest-----BPSO-iForest0. 2 0. 4 0. 6 0. 8 1. 0False positive rate图 3 G r a y h o l e ROC 曲线F i g . 3G r a y h o l e ROC c u r v e金测 ■ 交小 t 于 羊常 &于 F 其 *模m k i 基)r e s t 汝果分析表3可以得出，在较小规模数据集S a m p l e -G H 中，BPSO -i F o r e s t 和i F o r e s t 在处理时间上处于一个量级均优于 RF 和MBGSO -ARF ，但是差距较小;将数据集扩大，4种算法表3 4种算法对不同类型异常数据的检测时间T a b l e 3 D e t e c t i o n t i m e o f f o u r a l g o r i t h m sf o r d i f f e r e n t t y p e s o f a b n o r m a l d a t a异常类型BPSO-iForest/siForest/s MBGSO-ARF/s R F/s Blackhole 42.62125.32896.53264.82Grayhole 46.85147.64665.22725.54Flooding 22.6363. 16242.9942.31Scheduling 29.0283.28314.61765.25Sample-GH0.210.430.741. 16l .o .o .o .o .3J S u >5s o d3I U H l .o .o .o .o .3J 2 3A l J l s o d o 2H吴志强等:针对WSN异常数据检测改进的孤立森林方法131 1期选择性集成思想提出了一种无线传感器网络异常数据的检验 方法BPSO-i F o r e s t.该方法针对原始孤立森林检测能力不足 和执行效率较低等问题，将基分类器进行选优后再组合的处 理，通过多种实验进行验证并与i F〇r e s t、R F和MBGSO-ARF 算法进行对比，得出实验结论，BPSO-i F o r e s t算法在对WSN 异常数据的检测上具有更高精度和更快效率的显著效果.本 文已对四种DoS攻击产生的W S N异常数据进行检测，而针 对W S N的攻击类型多种多样，今后考虑在对更多类型攻击 产生的异常数据的检测方向进行算法改进.References ：[1] Mairiwala N, Rathee P. An approach to increase the wireless sensornetwork lifetime [ C ] //W orld Congress on Information and Com­munication Technologies, IEEE ,2012 ：495-499.[2] Sun B,Osborne L,X iao Y,e t al. Intrusion detection techniques inmobile ad hoc and wireless sensor networks [ J ]. IEEE WirelessCommunications,2007,14(5) ：56-63.[3] Zhang Y, Meratnia N, Havinga P J M. Outlier detection techniquesfor wireless sensor networks ： a survey [ J ]. IEEE CommunicationsSurveys and Tutorials,2010,12(2) ：159-170.[4] Li G,Wang Y. Sketch based anomaly detection scheme in wireless sen­sor networks [ C ]//International Conference on Cyber-Enabled Dis­tributed Computing and Knowledge Discovery,IEEE,2013：344-348. [5] Emadi H S，Mazinani S M A novel anomaly detection algorithm u­sing DBSCAN and SVM in wireless sensor networks [ J ]. WirelessPersonal Communications, 2018,98 (2)： 2025 -2035.[6]Fei H uan,Li Guang-hui. WSN anomaly data detection algorithmbased on K-means clustering [ J]. Computer Engineering,2015,41(7) ：124-128.[7] Lian Chao,Li Hua,Liu Y a,et al. Anomaly detection model basedon DBN-LR integrated learning [ J ]. Journal of Chinese Computer Systems,2019,40(12) ：2637-2643.[8] Gu Xiao-yong,Li Guang-hui. Anomaly detection algorithm of WSNdata stream based on NMEA-BP [ J ]. Journal of Transduction Technology,2018,31(5) ：746-752.[9] Zamry N M,Zainal A,Rassam M A. Unsupervised anomaly detec­tion for unlabelled wireless sensor networks data [ J ]. International Journal of Advances in Soft Computing &Its Applications,2018,10(2)：173-191.[10] Xu Ou-yang,Li Guang-hui. Optimization of firefly and detection ofWSN anomaly data in random forests [ J ]. Computer Science and Exploration ,2018,12(10)： 1633-1644.[11 ] Liu F T,T ing K M,Zhou Z H. Isolation-based anomaly detection[J].ACM Transactions on Knowledge Discovery from Data,2012,6(1 )：l-39.[12] Mannila H,Toivonen H,Verkamo A I. Discovery o f frequent epi­sodes in event sequences [ J ]. Data Mining and Knowledge Discov­ery, 1997,1(3) ：259-289.[13] Jin N, Rahmat-Samii Y. Advances in particle swarm optimizationfor antenna designs：real-number,binary,single-objective and multi­objective implementations [ J]. IEEE Transactions on Antennas and Propagation ,2007,55(3) ：556-567.[14] Kennedy J,Eberhart R C. A discrete binary version o f the particleswarm optimization [ C ] //IE E E International Conference on Cy­bernetics and Simulation,Piscataway,NJ, 1997：4104-4108.[15] Wang Yue,Q iu Fei-yue,Guo Hai-dong. Adaptive inertia weight bi­nary particle swarm optimization algorithm with mutation operator [J]. Journal o f Chinese Computer System s,2019,40(4) ：733-737.[16] Zhou Z H, Wu J, Tang W. Ensembling neural networks：manycould be better than all [ J]. Artificial Intelligence,2CX)2,137(1-2) ：239-263.[17 ] Almomani I, Al-Kasasbeh B, Al-Akhras M. WSN-DS ： a dataset forintrusion detection systems in wireless sensor networks [ J ]. Journal of Sensors,2016,2016：736-751.附中文参考文献：[6]费欢，李光辉.基于K-m eans聚类的W S N异常数据检测算法[J] •计算机工程，2015，41 (7):124-128.[7]连超，李华，刘亚，等.一种基于D BN-L R集成学习的异常检测模型[J].小型微型计算机系统，2019，40( 12) :2637-2643. [8 ]顾晓勇，李光辉.基于N M EA-BP的W S N数据流异常检测算法[J].传感技术学报,2018,31 (5) :746-752.[10]许欧阳，李光辉.萤火虫优化和随机森林的W S N异常数据检测[J].计算机科学与探索，2018,12(10) :1633-1644.[15]王越，邱飞岳，郭海东.一种带变异算子的自适应惯性权重二进制粒子群优化算法[J].小型微型计算机系统，2019,40(4):733-737.。

粒⼦群优化算法粒⼦群优化算法属于群智能(swarm intelligence)优化算法。

群智能分两种，⼀种是粒群优化，另⼀种是蚁群优化。

群智能概念假设你和你的朋友正在寻宝，每个⼈有个探测器，这个探测器可以知道宝藏到探测器的距离。

你们⼀群⼈在找，每个⼈都可以把信息共享出去，就跟打dota时你可以有你队友的视野，你可以知道其他所有⼈距离宝藏的距离，这样，你看谁离宝藏最近，就向谁靠近，这样会使你发现宝藏的机会变⼤，⽽且，这种⽅法⽐你单⼈找要快的多。

这是⼀个群⾏为(swarm behavior)的简单实例，群中各个体交互作⽤，使⽤⼀个⽐单⼀个体更有效的⽅法求解全局⽬标。

可以把群(swarm)定义为某种交互作⽤的组织或Agent之结构集合，在群智能计算研究中，群的个体组织包括蚂蚁，⽩蚁，蜜蜂，黄蜂，鱼群，鸟群等。

在这些群体中，个体在结构上是很简单的，⽽它们的集体⾏为却可能变得相当复杂。

研究⼈员发现，蚂蚁在鸟巢和⾷物之间的运输路线，不管⼀开始多随机，最后蚂蚁总能找到⼀条最短路径。

粒群优化概念粒群优化(particle swarm optimization,PSO)算法是⼀种基于群体搜索的算法，它建⽴在模拟鸟群社会的基础上。

粒群概念的最初含义是通过图形来模拟鸟群优美和不可预测的舞蹈动作，发现鸟群⽀配同步飞⾏和以最佳队形突然改变飞⾏⽅向并重新编队的能⼒。

这个概念已经被包含在⼀个简单有效的优化算法中。

在粒群优化中，被称为“粒⼦”(particle)的个体通过超维搜索空间“流动”。

粒⼦在搜索空间中的位置变化是以个体成功地超过其他个体的社会⼼理意向为基础的，因此，群中粒⼦的变化是受其邻近粒⼦（个体）的经验或知识影响的。

⼀个粒⼦的搜索⾏为受到群中其他粒⼦的搜索⾏为的影响。

由此可见，粒群优化是⼀种共⽣合作算法。

算法描述先通过⼀个形象的场景来描述⼀下：5只鸟觅⾷，每个鸟都知道⾃⼰与⾷物的距离，并将此信息与其他鸟共享。

⼀开始，5只鸟分散在不同的地⽅，假设没只鸟每秒钟更新⾃⼰的速度和⽅向，问题是怎么更新呢？每只鸟记下⾃⼰离⾷物最近的位置，称为pbest，pbest0,pbest1,..分别表⽰5只鸟的pbest，从这⾥⾯选⼀个gbest，组⾥最好的。

二进制粒子群算法
二进制粒子群算法（BinaryParticleSwarmOptimization，BPSO）是一种优化算法，其主要思想来源于粒子群优化算法（Particle Swarm Optimization，PSO）。

与传统的PSO算法不同，BPSO算法中每个粒子的位置和速度都是由二进制编码表示的。

这种编码方式可以减小存储空间和计算复杂度，同时也使得算法更加容易应用于离散问题。

BPSO算法的核心思想是通过粒子的位置和速度等参数来模拟群体智能的行为，从而寻找问题的最优解。

在优化过程中，粒子通过不断地更新自身的位置和速度来搜索最优解，同时也能够利用其他粒子的经验来指导自己的搜索过程。

BPSO算法的优点在于其适用于各种类型的优化问题，特别是那些需要考虑离散因素的问题。

同时，由于其简单的编码方式和高效的搜索机制，BPSO算法也被广泛应用于图像处理、机器学习和信号处理等领域。

总的来说，BPSO算法是一种非常有前景的优化算法，它不仅能够提高问题的求解效率和精度，还能够帮助人们更好地理解和掌握群体智能的本质。

- 1 -。

粒子群优化算法及其在多目标优化中的应用一、什么是粒子群优化算法粒子群优化算法（Particle Swarm Optimization，PSO）是一种智能优化算法，源自对鸟群迁徙和鱼群捕食行为的研究。

通过模拟粒子受到群体协作和个体经验的影响，不断调整自身的位置和速度，最终找到最优解。

PSO算法具有简单、易于实现、收敛速度快等优点，因此在许多领域中得到了广泛应用，比如函数优化、神经网络训练、图像处理和机器学习等。

二、PSO在多目标优化中的应用1.多目标优化问题在现实中，多个优化目标相互制约，无法同时达到最优解，这就是多目标优化问题。

例如，企业在做决策时需要考虑成本、效益、风险等多个因素，决策的结果是一个多维变量向量。

多目标优化问题的解决方法有很多，其中之一就是使用PSO算法。

2.多目标PSO算法在传统的PSO算法中，只考虑单一目标函数，但是在多目标优化问题中，需要考虑多个目标函数，因此需要改进PSO算法。

多目标PSO算法（Multi-Objective Particle Swarm Optimization，MOPSO）是一种改进后的PSO算法。

其基本思想就是将多个目标函数同时考虑，同时维护多个粒子的状态，不断优化粒子在多个目标函数上的表现，从而找到一个可以在多个目标函数上达到较优的解。

3.多目标PSO算法的特点与传统的PSO算法相比，多目标PSO算法具有以下特点：（1）多目标PSO算法考虑了多个目标函数，解决了多目标优化问题。

（2）通过维护多个粒子状态，可以更好地维护搜索空间的多样性，保证算法的全局搜索能力。

（3）通过优化粒子在多个目标函数上的表现，可以寻找出在多目标情况下较优的解。

三、总结PSO算法作为一种智能优化算法，具备搜索速度快、易于实现等优点，因此在多个领域有广泛的应用。

在多目标优化问题中，多目标PSO算法可以通过同时考虑多个目标函数，更好地寻找在多目标情况下的最优解，具有很好的应用前景。

4.4 群智能进化计算在生物界，蚂蚁、蜜蜂等社会昆虫和鸟群、鱼群等动物呈现出有趣的现象：单个的个体智能并不高，但依靠群体的能力，却发挥出超出个体的智能。

这种现象揭示了简单智能的主体通过合作可以表现出复杂智能行为的特性。

通过对这种集体行为的人工模拟，用于解决组合优化问题和其它一些实际应用问题的新方法相继产生。

对这些新方法的研究可将其称之为群智能（Swarm intelligence ）的研究。

1999年Bonabeau 、Dorigo 等人给出群智能的定义：群智能是指任何受到社会昆虫群体和其它动物群体的集体行为的启发而设计的算法和分布式问题解决装置。

很多实际问题可以转化为最优化问题来解决。

按计算的复杂度来划分，这些问题可分为P 问题和NP 问题。

目前对于NP 完全问题的解决尚没有很好的方法。

启发于蚁群、鸟群和鱼群的蚁群优化（Ant Colony Optimization ，ACO ）、粒子群优化（Particle Swarm Optimization ，PSO ）和鱼群优化（Fish Swarm Optimization ，FSO ）等方法对这类问题的解决提供了全新的途径，它们是计算智能领域中三种典型的群智能算法。

因此，研究群智能具有十分重要的理论和实践意义。

本节主要介绍三种典型群智能算法，以及其改进形式。

4.4.1 粒子群优化算法1、基本原理与算法粒子群优化算法（PSO ）最早是由Eberhart 和Kennedy 于1995年提出的，它的基本概念源于对人工生命和鸟群捕食行为的研究。

设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但是它们知道当前的位置离食物还有多远。

那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO 算法就是从这种生物种群行为特性中得到启发并用于求解优化问题。

在PSO 算法中，每个优化问题的潜在解都可以想象成d 维搜索空间的一个点，我们称之为“粒子”。

自适应粒子群优化算法自适应粒子群优化算法（Adaptive Particle Swarm Optimization，简称APSO）是一种基于粒子群优化算法（Particle Swarm Optimization，简称PSO）的改进算法。

PSO算法是一种群体智能优化算法，模拟鸟群觅食行为来求解优化问题。

与传统PSO算法相比，APSO算法在粒子个体的位置和速度更新方面进行了优化，增强了算法的鲁棒性和全局能力。

APSO算法的关键改进之一是引入自适应策略来调整个体的速度和位置更新。

传统PSO算法中，个体的速度与当前速度和历史最优位置有关。

而在APSO算法中，个体的速度与自适应权重有关，该权重能够自动调整以适应不同的空间和优化问题。

自适应权重的调整基于个体的历史最优位置和整个粒子群的全局最优位置。

在每次迭代中，根据粒子群的全局情况来动态调整权重，使得速度的更新更加灵活和可靠。

另一个关键改进是引入自适应的惯性因子（inertia weight）来调整粒子的速度。

传统PSO算法中，惯性因子是一个常数，控制了速度的更新。

在APSO算法中，惯性因子根据粒子群的性能和进程进行自适应调整。

对于空间广阔、优化问题复杂的情况，惯性因子较大以促进全局；对于空间狭窄、优化问题简单的情况，惯性因子较小以促进局部。

通过调整惯性因子，粒子的速度和位置更新更具有灵活性和针对性，可以更好地适应不同的优化问题。

此外，APSO算法还引入了自适应的局域半径（search range）来控制粒子的范围。

传统PSO算法中，粒子的范围是固定的，很容易陷入局部最优解。

而在APSO算法中，根据全局最优位置和当前最优位置的距离进行自适应调整，当距离较大时，范围增加；当距离较小时，范围减小。

通过自适应调整范围，可以提高算法的全局能力，减少陷入局部最优解的风险。

综上所述，自适应粒子群优化算法（APSO）是一种改进的PSO算法，通过引入自适应策略来调整个体的速度和位置更新，增强了算法的鲁棒性和全局能力。

An adaptive mutation binary particle swarm
optimization algorithm
作者： 姜磊[1,2];刘建华[1,2];张冬阳[1,2];卜冠南[1,2]
作者机构： [1]福建工程学院信息科学与工程学院,福建福州350118;[2]福建省大数据挖掘与应用技术重点实验室,福建福州350118
出版物刊名： 福建工程学院学报
页码： 273-279页
年卷期： 2020年 第3期
主题词： 数据预处理;特征选择;二进制粒子群算法;自适应变异;惯性权重
摘要：针对二进制粒子群算法(BPSO)具有过早收敛的缺陷,在粒子位置更新后提出变异概率自适应从大到小的变异操作。

同时对算法惯性权重参数采用递增的设置方案,从而得到一种自适应变异BPSO算法(AMBPSO),将其应用于特征选择问题。

实验结果表明,提出的新算法前期具有较强的全局搜索能力,后期具有较强的局部搜索能力,能使平均选择特征数量最多从27.6个减少到20.2个,平均分类准确率最多从91.346%提升到94.135%。

粒子群算法的多目标优化粒子群算法（Particle Swarm Optimization，PSO）是一种启发式优化算法，最初由Eberhart和Kennedy在1995年提出，灵感来自鸟群觅食行为。

它通过模拟鸟群中鸟的飞行行为，实现对多个目标的优化求解。

在传统的PSO算法中，只针对单个目标进行优化。

但在实际问题中，经常存在多个目标需要同时优化。

多目标优化问题具有复杂性、多样性和冲突性等特点，往往不能简单地通过将多个目标融合为一个综合目标进行求解，因此需要专门的多目标优化算法。

多目标粒子群算法（Multi-objective Particle Swarm Optimization，MOPSO）是一种扩展的PSO算法，可以解决多目标优化问题。

它通过改进传统PSO的算法机制，使得粒子在过程中能够维持一组非劣解集合（Pareto解集合），从而得到一系列最优解，满足不同领域的需求。

MOPSO算法的具体步骤如下：1.初始化粒子的位置和速度，并随机分布在空间内。

2.根据多个目标函数值计算每个粒子的适应度，用以评估其优劣程度。

3.更新粒子的速度和位置。

速度的更新包括惯性权重、自我认知因子和社会认知因子等参数。

位置的更新采用基本PSO的方式进行。

4.根据更新后的位置，重新计算粒子的适应度。

5.更新全局最优解集合，将非劣解加入其中。

采用非劣解排序方法来实现。

6.判断终止条件是否满足，若满足则输出所有非劣解；否则返回第3步。

MOPSO算法相对于传统的PSO算法，主要的改进在于更新全局最优解集合的方法上。

非劣解排序方法可以帮助保持解的多样性，避免陷入局部最优解。

多目标粒子群算法在多目标优化问题中具有一定的优势和应用价值。

它能够同时考虑多个目标的优化需求，并提供一系列的最优解供决策者选择。

在实际应用中，MOPSO算法已经成功应用于控制系统设计、图像处理、机器学习等多个领域。

总结起来，多目标粒子群算法是一种有效的多目标优化算法。