特征选择法与蚁群算法简介

1、特征选择法与蚁群算法简介简介什么叫特征选择？ 经典的特征选择方法是从多个特征中选取一些特征，这个方法可以说包括特征选择和特征提取两个方面。特征提取广义上指的是一种变换，将处于高维空间的样本通过映射或变换的方式转换到低维空间，达到降维的目的；特征选择指从一组特征中去除冗余或不相关的特征来降维。这两者常联合使用，一般先通过变换将高维特征空间映射成低维特征空间，然后再去除冗余和不相关的特征来进一步达到降维的目的。简介为什么要用特征选择算法为什么要用特征选择算法? ? 获取最优特获取最优特征组合征组合提高测试数据提高测试数据的效率的效率减少系统计减少系统计算时间算时间更高的检测率更高的检测率更低的虚警

2、率更低的虚警率简介特征选择的步骤特征选择的步骤原始特征集原始特征集产生特征集产生特征集评估子集评估子集停止准则停止准则结果验证结果验证不满意特征组合满意特征组合通过特征算法子集优劣特征选择分类根据特征子集形成方式分类：根据特征子集形成方式分类：特征选择分类根据特征集合的评价策略方式分类：根据特征集合的评价策略方式分类：基于滤波(Filter)评价策略的特征选择算法。基于嵌入式(Wrapper)评价策略的特征选择算法。常见的特征选择算法1.1.遗传算法遗传算法 3 3. .蚂蚁算法蚂蚁算法2 2. .粒子群算法粒子群算法遗传算法 遗传算法（Genetic Algorithm）： 是模拟达尔文生物

3、进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现。遗传算法 遗传算法的基本运算过程如下： （1)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 （2）个体评价：计算群体P(t)中各个个体的适应度。 （3）选择运算:将选择算子作用于群体。选择的目的是把优化的

4、个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 （4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。 （5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。 （6）终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。粒子群算法粒子群算法：也称粒子群优化算法（Particle Swarm Optimization，PSO），是由Eberhart 博士和kennedy 博士

5、提出，源于对鸟群捕食的行为研究 。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。这个算法基于迭代的优化算法。粒子群的每个个体都代表优化问题的候选解，每个粒子具有位置x和速度v两个特征，位置代表候选解的值，速度用于决定粒子在搜素空间迭代的位移。粒子对应的目标函数值作为粒子的适应度f，候选解的优劣程度由该适应度决定。粒子群算法 基于粒子群优化算法的特征选择的算法步骤如下： （1）粒子群初始化。 （2）对粒子群每个粒子计算适应值，适应值与最优解的距离直接有关。 （3）种群根据适应值进行复制。 （4）如果终止条件满足的话，就停止，否则转步骤（2）。蚁群算法蚁群算法-蚁群

6、算法起源蚁群算法起源 蚂蚁属于群居昆虫单个蚂蚁的行为极其简单,但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为,能够完成复杂的任务。蚁群算法起源蚁群算法起源 蚂蚁觅食蚂蚁没有发育完全的视觉感知系统，甚至很多种类完全没有视觉，他们在寻找食物的过程中是如何选择路径的呢？蚁群是如何完成这些复杂的任务的呢? 人们经过大量研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone) 的物质进行信息传递. 从而能相互协作,完成复杂的任务. 蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用.蚁群算法起源蚁群算法起源蚂蚁在运动过程中, 能够在它所经过的路径上留下外

7、激素,而且蚂蚁在运动过程中能够感知外激素的存在及其强度,并以此指导自己的运动方向, 蚂蚁倾向于朝着外激素强度高的方向移动.由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象: 某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大. 蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法起源蚁群算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些 实际问题。1991年意大利米兰理学院M. Dorigo提出Ant System, 用于求解TSP等组合优化问题。

8、1995年Gramdardella和Dorigo提出Ant-Q算法，建立了AS和Q-learning的联系。1996年二人又提出Ant Colony System1997年有人提出Max-Min Ant System1999年Dorigo等人把先前各种算法归结为Ant Colony Optimization meta-heuristic的统一框架下，给出抽象而规范的算法描述.目前，被较广泛的应用DorigoDorigo蚁群算法-双桥实验最终最终有有80%-100%的蚂蚁选择较短的桥。的蚂蚁选择较短的桥。简化的蚂蚁寻食过程蚂蚁从A A点出发，速度相同，食物在D D点，可能随机选择路线ABDABD

9、或ACDACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步， 本图为经过9 9个时间单位时的情形：走ABDABD的蚂蚁到达终点，而走ACDACD的蚂蚁刚好走到C C点，为一半路程。简化的蚂蚁寻食过程本图为从开始算起，经过1818个时间单位时的情形：走ABDABD的蚂蚁到达终点后得到食物又返回了起点A A，而走ACDACD的蚂蚁刚好走到D D点。 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过3636个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D D点取得了食物，此时ABDABD的路线往返了2 2趟，每一处的信息素为4 4个单位，而ACDACD的路线往返了一趟，每一处的信息

10、素为2 2个单位，其比值为2 2：1 1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABDABD路线上增派一只蚂蚁（共2 2只），而ACDACD路线上仍然为一只蚂蚁。再经过3636个时间单位后，两条线路上的信息素单位积累为1212（4+44+4* *2 2）和4 4（2 2* *2 2），比值为3 3：1 1。 若按以上规则继续，蚁群在ABDABD路线上再增派一只蚂蚁（共3 3只）， 而ACDACD路线上仍然为一只蚂蚁。再经过3636个时间单位后，两条线路上的信息素单位积累为2424（4+44+4* *2+42+4* *3 3）和6 6（2 2* *3 3），比值为4 4：1 1。 若

11、继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACDACD路线而选择ABDABD路线。简化的蚂蚁寻食过程简化的蚂蚁寻食过程 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 人工蚁群和自然蚁群的区别：人工蚁群有一定的记忆能力，能够记忆已经访问过的节点； 人工蚁群选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目

12、的地的距离。自然界蚂蚁觅食行为自然界蚂蚁觅食行为蚁群优化算法蚁群优化算法觅食空间觅食空间问题的搜索空间问题的搜索空间搜索空间的一组搜索空间的一组有效解有效解一个有效解一个有效解问题的最优解问题的最优解蚁群蚁群蚁巢到食物的一条路径蚁巢到食物的一条路径找到的最短路径找到的最短路径对对应应关关系系信息素信息素信息素浓度变量信息素浓度变量蚁群优化算法基本流程 TSPTSP问题的人工蚁群算法中，假设m m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 1 信息素值也称信息素痕迹。2 2 可见度，即先验值。 信息素的更新方式有2 2种，一是

13、挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”( (有蚂蚁走过) )的边增加信息素。 蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。 蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。蚁群优化算法基本流程 对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。J

14、k(i)表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。h(i, j)是一个启发式信息（信息素浓度变量），通常由 h (i, j)=1/dij直接计算。t(i, j)表示边(i, j)上的信息素量。 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui uthth蚁群优化算法基本流程 ( )( , )( , ), if ( )( , )( , )( , ) 0, otherwisekkku Jii ji jjJipi ji ui uthth为了模拟蚂蚁在较短路径上留下更多的信

15、息素，当所有蚂蚁到达终点时，必须把各路径为了模拟蚂蚁在较短路径上留下更多的信息素，当所有蚂蚁到达终点时，必须把各路径的信息素的信息素浓度浓度重新更新一次，信息素的更新也分为重新更新一次，信息素的更新也分为两个步骤：两个步骤： (1) (1)每每一轮过后，问题空间中的所有路径上的信息素都会发生一轮过后，问题空间中的所有路径上的信息素都会发生蒸发蒸发 (2) (2)所有所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素11( , )(1)( , )( , ),(), if ( , ) ( , ) 0, otherwisemkkk

16、kki ji ji jCi jRi jtttt信息素更新的作用信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，这个挥发过程主要用于避 免算法过快地向局部最优区域集中，有助于搜索区域的扩展。信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现 由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是 在蚁群中的m只蚂蚁全部完成n城市的访问后，统一对残留信息进行更新处理。TSPTSP问题的蚁群优化算法伪代码for for each edgeset t0 = m/

17、Cnn (initial pheromone value )while while not stopfor for each ant krandomly choose an initial cityfor for i = 1 to nchoose next city j with probabilitycompute the length Ck of the tour constructed by the kth antfor for each edge update the pheromone valueprint resultTSP举例四个城市的TSPTSP问题，距离矩阵和城市图示如下：假

18、设共m m=3=3只蚂蚁，参数=1=1，=2=2，=0.5=0.5312354152242ijWdABDC241523步骤1首先使用贪婪算法得到路径的(ACDBA), 则Cnn =1+2+4+3=10，求得0 =m/Cnn =0.3。初始化所有边上的信息素含量。步骤2 .1为每个蚂蚁随机选择出发城市，假设蚂蚁1选择城市A，蚂蚁2选择城市B，蚂蚁3选择城市D。为每个蚂蚁选择下一访问城市，仅以蚂蚁1为例，当前城市i=A，可访问城市集合j1 (i)=B,C,D，计算蚂蚁1访问各个城市的概率。312354152242ijWdABDC241523121212:0.3(1/3)0.033:0.3(1/1)0.3:0.3(1/2)0.075ABABACACADADBACDththth3123