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

特征选择法与蚁群算法简介简介什么叫特征选择？经典的特征选择方法是从多个特征中选取一些特征，这个方法可以说包括特征选择和特征提取两个方面。特征提取广义上指的是一种变换，将处于高维空间的样本通过映射或变换的方式转换到低维空间，达到降维的目的；特征选择指从一组特征中去除冗余或不相关的特征来降维。这两者常联合使用，一般先通过变换将高维特征空间映射成低维特征空间，然后再去除冗余和不相关的特征来进一步达到降维的目的。简介为什么要用特征选择算法?获取最优特征组合提高测试数据的效率减少系统计算时间更高的检测率更低的虚警率简介特征选择的步骤原始特征集产生特征集评估子集停止准则结果验证不满意特征组合满意特征组合通过特征算法子集优劣特征选择分类根据特征子集形成方式分类：特征选择分类根据特征集合的评价策略方式分类：基于滤波(Filter)评价策略的特征选择算法。基于嵌入式(Wrapper)评价策略的特征选择算法。常见的特征选择算法1.遗传算法3.蚂蚁算法2.粒子群算法遗传算法•遗传算法（GeneticAlgorithm）：是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现。遗传算法•遗传算法的基本运算过程如下：（1)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。（2）个体评价：计算群体P(t)中各个个体的适应度。（3）选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。（4）交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。（5）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。（6）终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。粒子群算法•粒子群算法：也称粒子群优化算法（ParticleSwarmOptimization，PSO），是由Eberhart博士和kennedy博士提出，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。这个算法基于迭代的优化算法。粒子群的每个个体都代表优化问题的候选解，每个粒子具有位置x和速度v两个特征，位置代表候选解的值，速度用于决定粒子在搜素空间迭代的位移。粒子对应的目标函数值作为粒子的适应度f，候选解的优劣程度由该适应度决定。粒子群算法•基于粒子群优化算法的特征选择的算法步骤如下：（1）粒子群初始化。（2）对粒子群每个粒子计算适应值，适应值与最优解的距离直接有关。（3）种群根据适应值进行复制。（4）如果终止条件满足的话，就停止，否则转步骤（2）。蚁群算法--蚁群算法起源•蚂蚁属于群居昆虫单个蚂蚁的行为极其简单,但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为,能够完成复杂的任务。蚁群算法起源•蚂蚁觅食蚂蚁没有发育完全的视觉感知系统，甚至很多种类完全没有视觉，他们在寻找食物的过程中是如何选择路径的呢？蚁群是如何完成这些复杂的任务的呢?人们经过大量研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递.从而能相互协作,完成复杂的任务.蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用.蚁群算法起源•蚂蚁在运动过程中,能够在它所经过的路径上留下外激素,而且蚂蚁在运动过程中能够感知外激素的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着外激素强度高的方向移动.•由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法起源•20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。•1991年意大利米兰理学院M.Dorigo提出AntSystem,用于求解TSP等组合优化问题。•1995年Gramdardella和Dorigo提出Ant-Q算法，建立了AS和Q-learning的联系。•1996年二人又提出AntColonySystem•1997年有人提出Max-MinAntSystem•1999年Dorigo等人把先前各种算法归结为AntColonyOptimizationmeta-heuristic的统一框架下，给出抽象而规范的算法描述.•目前，被较广泛的应用Dorigo蚁群算法--双桥实验最终有80%-100%的蚂蚁选择较短的桥。简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。简化的蚂蚁寻食过程本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。•假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。•寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12（4+4*2）和4（2*2），比值为3：1。•若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24（4+4*2+4*3）和6（2*3），比值为4：1。•若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线而选择ABD路线。简化的蚂蚁寻食过程简化的蚂蚁寻食过程•基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。•人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。•人工蚁群和自然蚁群的区别：人工蚁群有一定的记忆能力，能够记忆已经访问过的节点；•人工蚁群选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。自然界蚂蚁觅食行为蚁群优化算法觅食空间问题的搜索空间搜索空间的一组有效解一个有效解问题的最优解蚁群蚁巢到食物的一条路径找到的最短路径对应关系信息素信息素浓度变量蚁群优化算法基本流程•TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1信息素值也称信息素痕迹。2可见度，即先验值。•信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。•蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。•蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。蚁群优化算法基本流程•对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i)表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。h(i,j)是一个启发式信息（信息素浓度变量），通常由h(i,j)=1/dij直接计算。t(i,j)表示边(i,j)上的信息素量。()(,)(,),if()(,)(,)(,)0,otherwisekkkuJiijijjJipijiuiuthth蚁群优化算法基本流程•信息素更新初始化信息素浓度t(i,j)=C=m/Cnn(∀𝑖,𝑗)（m蚂蚁个数，Cnn贪婪算法构造的路径之和）如果C太小，算法容易早熟，蚂蚁会很快的全部集中到一条局部最优的路径上。反之，如果C太大，信息素对搜索方向的指导作用太低，也会影响算法性能。()(,)(,),if()(,)(,)(,)0,otherwisekkkuJiijijjJipijiuiuthth为了模拟蚂蚁在较短路径上留下更多的信息素，当所有蚂蚁到达终点时，必须把各路径的信息素浓度重新更新一次，信息素的更新也分为两个步骤：(1)每一轮过后，问题空间中的所有路径上的信息素都会发生蒸发(2)所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素路径构建信息素更新11(,)(1)(,)(,),(),if(,)(,)0,otherwisemkkkkkijijijCijRijtttt•m是蚂蚁个数；是信息素的蒸发率，规定0≤1，通常设置为0.5•Δ𝜏𝑘(𝑖,𝑗)是第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。•Ck表示路径长度，它是Rk中所有边的长度和。信息素更新的作用•信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。•信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问后，统一对残留信息进行更新处理。TSP问题的蚁群优化算法伪代码foreachedgesett0=m/Cnn(initialpheromonevalue)whilenotstopforeachantkrandomlychooseaninitialcityfori=1tonchoosenextcityjwithprobabilitycomputethelengthCkofthetourconstructedbythekthantforeachedgeupdatethepheromonevalueprintresultTSP举例四个城市的TSP问题，距离矩阵和城市图示如下：假设共m=3只蚂蚁，参数α=1，β=2，ρ=0.5312354152242ijWdABDC241523•步骤1首先使用贪婪算法得到路径的(ACDBA),则Cnn=1+2+4+3=10，求得τ0=m/Cnn=0.3。初始化所有边上的信息素含量。t(0)=tij(0)=00.30.30.30.300.30.30.30.300.30.30.30.30•步骤2.1为每个蚂蚁随机选择出发城市，假设蚂蚁1选择城市A，蚂蚁2选择城市B，蚂蚁3选择城市D。为每个蚂蚁选择下一访问城市，仅以蚂蚁1为例，当前城市i=A，可访问城市集合j1(i)={B,C,D}，计算蚂蚁1访问各个城市的概率。31