论文部分内容阅读
摘 要： 通过对基本PSO算法进行分析研究，发现PSO是一种有效的全局寻优算法。它操作简单，使用方便，但是极易陷入局部最优。通过对PSO进行改进应用到入侵检测系统中，大大提高检测率。
关键词： 粒子群优化算法；入侵检测系统；应用
中图分类号：TP393 文献标识码：A 文章编号：1671－7597（2012）1110113-02
0 引言
入侵检测方法分为误用检测和异常检测两种。相比较而言，入侵检测系统中使用误用检测技术会多一些。所谓的误用检测技术是一种把入侵信息的特征首先输入到入侵信息特征库中，当有入侵行为发生的时候再将其与入侵信息特征库中的数据进行比对，如果发现有很大的相似性就认为是入侵可疑数据，此种技术大大提高了入侵检测的准确程度。但是由于它必须与入侵信息特征库中的数据进行比较，所以就无法对特征库以外的可疑入侵数据进行识别、检测与分析，从而导致误报和漏报现象，给用户及信息网络带来了很大的危险。相对而言，异常检测却是把用户的当前操作与特征数据库中的正常数据进行比对，假如二者存在很大的差异，就认为发生了可疑入侵行为。它与误用检测相比，特征数据库中的正常数据要比入侵数据容易得到，随着各种入侵行为的快速发展，难免有新的入侵行为没有被放入可疑入侵数据库中，异常检测更容易检测出未知的可疑入侵行为，有效解决了漏报现象。通常我们又把异常入侵检测技术划分为需要指导的异常检测，它是在准确取得正常数据的基础上建立起来的数据模型，用偏离正常数据值来判断是否存在可疑入侵数据。但是它要求有一组完全正常的数据来训练获得正常数据模型，如果训练数据中掺杂了入侵数据的话，一方面可能会把与攻击数据存在很大的差异的正常数据误认为是入侵数据，另一方面会把与入侵数据相似的可疑数据认为是正常数据，进而给计算机及其网络带来更大的危险。而且要想获得一组纯粹正确的训练数据也是很不容易的。如今在入侵检测技术的研究中，网络安全研究人员仍然会把无需指导的异常检测作为重点，无需指导的异常检测技术则是利用一组完全没有标记的数据作为输入信息，去寻找可疑入侵数据。它只需要找到一些未加工过的原始数据便可，不需要找到纯粹正确的训练数据。
与很多算法一样，粒子群算法也是一种全局寻优的算法，它是在群体智能理论的基础上建立起来的优化算法。它的基本理论是通过群体中粒子间的异同去产生群体智能指导进而优化搜索。比较进化算法而言，PSO在种群的全局搜索策略的基础上，更进一步地采用了速度位移模型，方便易行，它将特有的记忆用于动态跟踪当前的搜索情况再去调整搜索策略，有效地避免了遗传操作。但是它易陷入局部最优，本文我们将基本PSO算法进行了改进[1]。
1 基本PSO算法原理
PSO受鸟群捕食行为的启发，在一个固定的区域中只存在一块食物，一群鸟在随机捕获，而且任何一只都不知道食物的具体位置，但它清楚自己所处的位置以及离食物的距离，那么怎样才是找到食物的最优策略呢？我们首先应该找到离食物最近的鸟的周围区域，再去准确地找到食物。PSO就是从此种模型提练出来的，并把它运用到解决最优问题上面。在PSO中，我们把所有的优化问题的解都看成是一个“粒子”，对应搜索空间中的一只鸟。每一个粒子都是搜索空间中没有体积和质量的点，且对应一个适应值，被优化的函数来确定这个适应值。其中，速度决定每个粒子飞翔的距離和方向，速度值并根据自己和同伴的飞行经验来确定。PSO中优化问题的解被初始化为一群随机粒子，通过不断地迭代找到最优解。在每一次迭代操作过程中，粒子都要用两种经验来不断地调整更新自己。若认为本身的飞行经验便是粒子经历过的最好位置，就认为其是最好的适应值，把它设定为最优解，这个解也称作为个体极值。如果同伴的飞行经验是群体所有粒子经历过的最好位置，便把此飞行经验设定为整个种群目前找到的最优解，找到的解就是全局极值。需要说明的是群体不一定是整个群体，也可以是其中的一部分，那么在部分群体中寻到的最优解就看作是局部极值班[2]。
若目标搜索空间是M维，一个群体中包含N个粒子，其中第i
示为第i个粒子在搜索空间中的位置是 ，可以认为 是一个不确定的潜在解，通过目标函数便可以确定其适应值，根据其适应值的大小从而进一步确定其优劣。把 表示为经历过的最好位置，
表示为粒子i的速度。
PSO的基本算法步骤描述如下：
1）首先确定一群随机粒子，将其初始化；
2）通过目标函数确定每个粒子适应度的值；
3）将适应度的值与以往经历过的最好位置相比较，若认为此适应度的值优于先前所有的值，便更新 ；
4）将适应度的值与以群体以往经历过的最好位置相比较，若认为此适应度的值优于群体中所有的适应度的值班，便更新 ；
5）根据1）2）式对粒子的速度和位置进行不断的调整；
6）迭代中止条件：把最大迭代次数或全局最优位置满足预定最小适应阈值事先确定。
从上面的算法步骤看来，基本PSO算法中需要确定的参数很少，而且方便易行、操作简单，但最大的缺点就是极易陷入局部最优，在这里我们将基本PSO算法进一步改进[3]。
2 基本PSO算法改进
模拟退火算法（SA）是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。SA是先赋予搜索过程一种时变，通过调整适应值寻找最优且最终趋于零的概率突跳性，这样就解决了局部最优的问题。在基本PSO算法中最大的缺点就是容易陷入局部最优，在这里我们把SA与PSO相结合，利用SA在高温下的概率强突跳性的特性使PSO在陷入局部最优时跳出来，再度进行迭代搜索，在低温时便进行趋化性寻优，这样就大大提高了局部搜索能力。
改进PSO算法流程：
1）首先确定一群随机粒子，并确定随机位置和速度；初始化各个参数、初始温度和终止温度、最大迭代次数 并把降温速率也确定下来；
2）先给每个粒子 一个随机扰动，并进一步评价其适应值；
3）将每个粒子 的值与以往经历过的最好位置 的适应值作比较，若认为此适应度的值优于先前所有的值，则更新
若认为不好，以一定的概率接受 ，也将 作为当前最好位置更新 ；
4）将每个粒子 的值与所有粒子以往经历过的最好位置
作比较，若认为较好，则将其作为当前所有粒子的最好位置，更新 ；
5）根据1）2）式调整粒子的速度和位置，并退温；
6）如没有达到终止条件，则返回2）式进一步迭代。
改进PSO算法中的参数，要根据入侵检测系统中的实际问题具体确定，要合理设计最大速度，如果速度太大，粒子很可能在没有找到最好位置的时候便飞过去了；如果速度太小，粒子很容易就陷入局部最优。初始温度和终止温度也要在最大迭代次数的基础上合理设计。
3 结果与分析
实验中我们采用一组原始的网络数据作为测试数据，异常数据分为5类：A，B，C和D。前4组数据集分别对应的是只包含A，B，C和D入侵的数据，第5组数据集包括所有四类入侵数据。
为了很好的评价分析结果，我们采用入侵攻击误报率FAR和检测率DR来衡量：
FAR=被误检测为入侵的正常数据/总测试中的正常记录数
DR=检测出来的入侵记录数/总测试中的入侵记录数
基于PSO算法的入侵检测数据如表1所示。
基于改进的PSO算法的入侵检测数据如表2所示。
通过表1和表2我们可以看出，改进的PSO算法在入侵检测中无论是从误报率还是检测率方面考虑都优于基本的PSO算法[4]，能更加准确地检测出可疑入侵数据。
4 结论
基本PSO算法是一种使用简单、操作方便的算法，只需很少的代码和参数，在各种问题的求解和实际应用中体现出了它独有的特点和魅力。虽然有易陷入局部最优的缺点，但经过把基本的PSO算法进一步改进，再应用到入侵检测系统中，这样大大减少了误报率，并同时提高了检测率，为网络安全作出了应有的贡献。
参考文献：
[1]王德广、姚鹏、黄明，K-PSO聚类算法在入侵检测中的研究：科学技术与工程，2009年，第9卷第8期.
[2]田东平、徐成虎，改进的粒子群优化算法的研究和分析，计算机工程与应用，2008年，第44卷第34期.
[3]谷保平、许孝元、郭红艳，基于粒子群优化的K均值算法在网络入侵檢测中的应用，计算机应用，2007年，第27卷第3期.
[4]刘靖明、韩丽川、侯立文，基于粒子群的K均值算法，系统工程理论与实践，2005年，第25第6期.
关键词： 粒子群优化算法；入侵检测系统；应用
中图分类号：TP393 文献标识码：A 文章编号：1671－7597（2012）1110113-02
0 引言
入侵检测方法分为误用检测和异常检测两种。相比较而言，入侵检测系统中使用误用检测技术会多一些。所谓的误用检测技术是一种把入侵信息的特征首先输入到入侵信息特征库中，当有入侵行为发生的时候再将其与入侵信息特征库中的数据进行比对，如果发现有很大的相似性就认为是入侵可疑数据，此种技术大大提高了入侵检测的准确程度。但是由于它必须与入侵信息特征库中的数据进行比较，所以就无法对特征库以外的可疑入侵数据进行识别、检测与分析，从而导致误报和漏报现象，给用户及信息网络带来了很大的危险。相对而言，异常检测却是把用户的当前操作与特征数据库中的正常数据进行比对，假如二者存在很大的差异，就认为发生了可疑入侵行为。它与误用检测相比，特征数据库中的正常数据要比入侵数据容易得到，随着各种入侵行为的快速发展，难免有新的入侵行为没有被放入可疑入侵数据库中，异常检测更容易检测出未知的可疑入侵行为，有效解决了漏报现象。通常我们又把异常入侵检测技术划分为需要指导的异常检测，它是在准确取得正常数据的基础上建立起来的数据模型，用偏离正常数据值来判断是否存在可疑入侵数据。但是它要求有一组完全正常的数据来训练获得正常数据模型，如果训练数据中掺杂了入侵数据的话，一方面可能会把与攻击数据存在很大的差异的正常数据误认为是入侵数据，另一方面会把与入侵数据相似的可疑数据认为是正常数据，进而给计算机及其网络带来更大的危险。而且要想获得一组纯粹正确的训练数据也是很不容易的。如今在入侵检测技术的研究中，网络安全研究人员仍然会把无需指导的异常检测作为重点，无需指导的异常检测技术则是利用一组完全没有标记的数据作为输入信息，去寻找可疑入侵数据。它只需要找到一些未加工过的原始数据便可，不需要找到纯粹正确的训练数据。
与很多算法一样，粒子群算法也是一种全局寻优的算法，它是在群体智能理论的基础上建立起来的优化算法。它的基本理论是通过群体中粒子间的异同去产生群体智能指导进而优化搜索。比较进化算法而言，PSO在种群的全局搜索策略的基础上，更进一步地采用了速度位移模型，方便易行，它将特有的记忆用于动态跟踪当前的搜索情况再去调整搜索策略，有效地避免了遗传操作。但是它易陷入局部最优，本文我们将基本PSO算法进行了改进[1]。
1 基本PSO算法原理
PSO受鸟群捕食行为的启发，在一个固定的区域中只存在一块食物，一群鸟在随机捕获，而且任何一只都不知道食物的具体位置，但它清楚自己所处的位置以及离食物的距离，那么怎样才是找到食物的最优策略呢？我们首先应该找到离食物最近的鸟的周围区域，再去准确地找到食物。PSO就是从此种模型提练出来的，并把它运用到解决最优问题上面。在PSO中，我们把所有的优化问题的解都看成是一个“粒子”，对应搜索空间中的一只鸟。每一个粒子都是搜索空间中没有体积和质量的点，且对应一个适应值，被优化的函数来确定这个适应值。其中，速度决定每个粒子飞翔的距離和方向，速度值并根据自己和同伴的飞行经验来确定。PSO中优化问题的解被初始化为一群随机粒子，通过不断地迭代找到最优解。在每一次迭代操作过程中，粒子都要用两种经验来不断地调整更新自己。若认为本身的飞行经验便是粒子经历过的最好位置，就认为其是最好的适应值，把它设定为最优解，这个解也称作为个体极值。如果同伴的飞行经验是群体所有粒子经历过的最好位置，便把此飞行经验设定为整个种群目前找到的最优解，找到的解就是全局极值。需要说明的是群体不一定是整个群体，也可以是其中的一部分，那么在部分群体中寻到的最优解就看作是局部极值班[2]。
若目标搜索空间是M维，一个群体中包含N个粒子，其中第i
示为第i个粒子在搜索空间中的位置是 ，可以认为 是一个不确定的潜在解，通过目标函数便可以确定其适应值，根据其适应值的大小从而进一步确定其优劣。把 表示为经历过的最好位置，
表示为粒子i的速度。
PSO的基本算法步骤描述如下：
1）首先确定一群随机粒子，将其初始化；
2）通过目标函数确定每个粒子适应度的值；
3）将适应度的值与以往经历过的最好位置相比较，若认为此适应度的值优于先前所有的值，便更新 ；
4）将适应度的值与以群体以往经历过的最好位置相比较，若认为此适应度的值优于群体中所有的适应度的值班，便更新 ；
5）根据1）2）式对粒子的速度和位置进行不断的调整；
6）迭代中止条件：把最大迭代次数或全局最优位置满足预定最小适应阈值事先确定。
从上面的算法步骤看来，基本PSO算法中需要确定的参数很少，而且方便易行、操作简单，但最大的缺点就是极易陷入局部最优，在这里我们将基本PSO算法进一步改进[3]。
2 基本PSO算法改进
模拟退火算法（SA）是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。SA是先赋予搜索过程一种时变，通过调整适应值寻找最优且最终趋于零的概率突跳性，这样就解决了局部最优的问题。在基本PSO算法中最大的缺点就是容易陷入局部最优，在这里我们把SA与PSO相结合，利用SA在高温下的概率强突跳性的特性使PSO在陷入局部最优时跳出来，再度进行迭代搜索，在低温时便进行趋化性寻优，这样就大大提高了局部搜索能力。
改进PSO算法流程：
1）首先确定一群随机粒子，并确定随机位置和速度；初始化各个参数、初始温度和终止温度、最大迭代次数 并把降温速率也确定下来；
2）先给每个粒子 一个随机扰动，并进一步评价其适应值；
3）将每个粒子 的值与以往经历过的最好位置 的适应值作比较，若认为此适应度的值优于先前所有的值，则更新
若认为不好，以一定的概率接受 ，也将 作为当前最好位置更新 ；
4）将每个粒子 的值与所有粒子以往经历过的最好位置
作比较，若认为较好，则将其作为当前所有粒子的最好位置，更新 ；
5）根据1）2）式调整粒子的速度和位置，并退温；
6）如没有达到终止条件，则返回2）式进一步迭代。
改进PSO算法中的参数，要根据入侵检测系统中的实际问题具体确定，要合理设计最大速度，如果速度太大，粒子很可能在没有找到最好位置的时候便飞过去了；如果速度太小，粒子很容易就陷入局部最优。初始温度和终止温度也要在最大迭代次数的基础上合理设计。
3 结果与分析
实验中我们采用一组原始的网络数据作为测试数据，异常数据分为5类：A，B，C和D。前4组数据集分别对应的是只包含A，B，C和D入侵的数据，第5组数据集包括所有四类入侵数据。
为了很好的评价分析结果，我们采用入侵攻击误报率FAR和检测率DR来衡量：
FAR=被误检测为入侵的正常数据/总测试中的正常记录数
DR=检测出来的入侵记录数/总测试中的入侵记录数
基于PSO算法的入侵检测数据如表1所示。
基于改进的PSO算法的入侵检测数据如表2所示。
通过表1和表2我们可以看出，改进的PSO算法在入侵检测中无论是从误报率还是检测率方面考虑都优于基本的PSO算法[4]，能更加准确地检测出可疑入侵数据。
4 结论
基本PSO算法是一种使用简单、操作方便的算法，只需很少的代码和参数，在各种问题的求解和实际应用中体现出了它独有的特点和魅力。虽然有易陷入局部最优的缺点，但经过把基本的PSO算法进一步改进，再应用到入侵检测系统中，这样大大减少了误报率，并同时提高了检测率，为网络安全作出了应有的贡献。
参考文献：
[1]王德广、姚鹏、黄明，K-PSO聚类算法在入侵检测中的研究：科学技术与工程，2009年，第9卷第8期.
[2]田东平、徐成虎，改进的粒子群优化算法的研究和分析，计算机工程与应用，2008年，第44卷第34期.
[3]谷保平、许孝元、郭红艳，基于粒子群优化的K均值算法在网络入侵檢测中的应用，计算机应用，2007年，第27卷第3期.
[4]刘靖明、韩丽川、侯立文，基于粒子群的K均值算法，系统工程理论与实践，2005年，第25第6期.