关于神经网络蚁群算法和遗传算法

[几种经典算法回顾]今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了...+阅读

关于神经网络蚁群算法和遗传算法

神经网络并行性和自适应性很强，应用领域很广，在任何非线性问题中都可以应用，如控制、信息、预测等各领域都能应用。蚁群算法最开始应用于TSP问题，获得了成功，后来又广泛应用于各类组合优化问题。但是该算法理论基础较薄弱，算法收敛性都没有得到证明，很多参数的设定也仅靠经验，实际效果也一般，使用中也常常早熟。遗传算法是比较成熟的算法，它的全局寻优能力很强，能够很快地趋近较优解。主要应用于解决组合优化的NP问题。这三种算法可以相互融合，例如GA可以优化神经网络初始权值，防止神经网络训练陷入局部极小且加快收敛速度。蚁群算法也可用于训练神经网络，但一定要使用优化后的蚁群算法，如最大-最小蚁群算法和带精英策略。...

蚁群算法在STP中有什么作用

展开全部STP(Spanning Tree Protocol)是生成树协议的英文缩写。该协议可应用于环路网络，通过一定的算法实现路径冗余，同时将环路网络修剪成无环路的树型网络，从而避免报文在环路网络中的增生和无限循环。STP的基本原理是，通过在交换机之间传递一种特殊的协议报文（在IEEE 802.1D中这种协议报文被称为“配置消息”）来确定网络的拓扑结构。配置消息中包含了足够的信息来保证交换机完成生成树计算。生成树协议STP/RSTP1. 技术原理：STP的基本思想就是生成“一棵树”，树的根是一个称为根桥的交换机，根据设置不同，不同的交换机会被选为根桥，但任意时刻只能有一个根桥。由根桥开始，逐级形成一棵树，根桥定时发送配置报文，非根桥接收配置报文并转发，如果某台交换机能够从两个以上的端口接收到配置报文，则说明从该交换机到根有不止一条路径，便构成了循环回路，此时交换机根据端口的配置选出一个端口并把其他的端口阻塞，消除循环。

当某个端口长时间不能接收到配置报文的时候，交换机认为端口的配置超时，网络拓扑可能已经改变，此时重新计算网络拓扑，重新生成一棵树。2. 功能说明：生成树协议最主要的应用是为了避免局域网中的网络环回，解决成环以太网网络的“广播风暴”问题，从某种意义上说是一种网络保护技术，可以消除由于失误或者意外带来的循环连接。STP也提供了为网络提供备份连接的可能，可与SDH保护配合构成以太环网的双重保护。新型以太单板支持符合ITU-T 802.1d标准的生成树协议STP及802.1w规定的快速生成树协议RSTP，收敛速度可达到1s。但是，由于协议机制本身的局限，STP保护速度慢（即使是1s的收敛速度也无法满足电信级的要求），如果在城域网内部运用STP技术，用户网络的动荡会引起运营商网络的动荡。

目前在MSTP 组成环网中，由于SDH保护倒换时间比STP协议收敛时间快的多，系统采用依然是SDH MS-SPRING或SNCP，一般倒换时间在50ms以内。但测试时部分以太网业务的倒换时间为0或小于几个毫秒，原因是内部具有较大缓存。SDH保护倒换动作对MAC层是不可见的。这两个层次的保护可以协调工作，设置一定的＂拖延时间＂（hold-off），一般不会出现多次倒换问题。STP还有屏蔽双绞线的意思（Shielded Twisted-Pair）在生物学，化学以及物理等学科中，STP是standard temperature and pressure的缩写.在理工实验中一般指273K,100KPa的环境；而在医学中则是指＂标准体温与脉搏＂.营销学中的STP现代市场营销理论的核心就是STP营销，它包括三要素：市场细分（market segmentation）目标市场（market targeting）市场定位（market positioning）市场细分市场细分的概念是美国市场学家温德尔·史密斯（Wendell R.Smith）于20世纪50年代中期提出来的。

市场细分的含义市场细分是指营销者通过市场调研，依据消费者的需要和欲望、购买行为和购买习惯等方面的差异，把某一产品的市场整体划分为若干消费者群的市场分类过程。每一个消费者群就是一个细分市场，每一个细分市场都是具有类似需求倾向的消费者构成的群体。市场细分的程序调查阶段分析阶段细分阶段细分消费者市场的基础地理细分：国家、地区、城市、农村、气候、地形人口细分：年龄、性别、职业、收入、教育、家庭人口、家庭类型、家庭生命周期、国籍、民族、宗教、社会阶层心理细分：社会阶层、生活方式、个性行为细分：时机、追求利益、使用者地位、产品使用率、忠诚程度、购买准备阶段、态度。市场细分的基本原理与依据市场是商品交换关系的总和，本身可以细分消费者异质需求的存在企业在不同方面具备自身优势市场细分的作用细分市场不是根据产品品种、产品系列来进行的，而是从消费者（指最终消费者和工业生产者）的角度进行划分的，是根据市场细分的理论基础，即消费者的需求、动机、购买行为的多元性和差异性来划分的。

通过市场细分对企业的生产、营销起着极其重要的作用。1、有利于选择目标市场和制定市场营销策略。市场细分后的子市场比较具体，比较容易了解消费者的需求，企业可以根据自己经营思想、方针及生产技术和营销力量，确定自己的服务对象，即目标市场。针对着较小的目标市场，便于制定特殊的营销策略。同时，在细分的市场上，信息容易了解和反馈，一旦消费者的需求发生变化，企业可迅速改变营销策略，制定相应的对策，以适应市场需求的变化，提高企业的应变能力和竞争力。联想的产品细分策略，正是基于产品的明确区分，联想打破了传统的“一揽子”促销方案，围绕“锋行” “天骄”“家悦”三个品牌面向的不同用户群需求，推出不同的“细分”促销方案。

选择“天骄”的用户，可优惠购买让数据随身移动的魔盘、可精彩打印数码照片的3110打印机、SOHO好伴侣的M700多功能机、以及让人尽享数码音乐的MP3；选择“锋行”的用户，可以优惠购买“数据特区”双启动魔盘、性格鲜明的打印机以及“新歌任我选”MP3播放器；钟情于“家悦”的用户，则可以优惠购买“电子小书包”魔盘、完成学习打印的打印机、名师导学的网校卡，以及成就...

求蚁群算法及其在路由优化中的应用

引言路由算法是网络的重要组成部分，它直接影响着网络性能，而含有多约束条件的QoS 路由是一个NP-C 问题，传统的路由算法很难解决，因此，一些学者尝试采用不同的算法相结合或者针对问题对某些算法进行改进来解决路由优化问题。其中蚁群算法是一个行之有效的方法，针对不同的网络，它在保证服务质量的前提下能够搜索到网络中的最优链路，提高了网络的传输效率。而这些研究缺乏通用的标准，如何把不同的问题归结到一个统一的框架下解决路由优化问题，如何提高寻优速度，缩短运行时间是当前的一个研究热点。1 蚁群算法的定义1.1 蚁群算法基本定义定义1 （蚁群算法）蚁群算法（ant colony optimization,ACO），又称蚂蚁算法，是一种用来在图中寻找最优路径的技术。它最早出现在1992 年Dorigo [1] 的博士论文里，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点，主要用于求解组合优化问题。定义2 （启发式算法）对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。收定义3 （信息素）蚂蚁释放一种化学物质，根据环境中的这种物质蚂蚁可以找到食物和窝之间的最短路径，我们称这种物质为信息素。定义4 （信息素更新）信息素更新是指路径上信息素量与蚂蚁数量的变化和时间的推移之间存在增加和消失的变化关系。每只蚂蚁走完一步或对所有n 个节点的遍历完成后，要对链路上的信息进行更新。因此，定义t+n 时刻在节点i 到节点j 的路径（i, j）上的信息量计算公式为+ = 1 +

(1)== 1

(2)式中： ——信息素挥发系数， ——本次循环中节点i 到节点j 的路径上信息素的增量。——第k 只蚂蚁在本次循环中在节点i 到节点j 的路径上留下的信息量。定义5（链路选择概率）信息素踪迹越浓的路径，被选中的概率越大，即路径概率选择机制。设网络G = (V, E)，这里V表示图中顶点的集合，设= |V|,E 表示边的集合。蚁群优化的目的是寻找图G 中起始节点Vi到目的节点Vj 的最短路径，每条边e (i,j)∈E 都有一个信息素变量Tij,Tij 会随着迭代次数的增加而变化。Pij 表示在节点i 选择到节点j 的概率。表示节点i 处可选择的下一跳邻居节点j 的集合。则蚂蚁在选择路径时会根据可选每条链路上的选择概率进行选择，并在该节点根据概率分配蚂蚁。概率公式为=* （3）式中： ——节点i 可选的下一跳节点集合。= 1

(4)式中： ——能见度因数，它由某种启发式算法决定。，，——3 个参数，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。1.2 收敛性定义6（收敛性）设Pi(t)=P(i∈Y)表示第i 条路径在t 次迭代时得到最优路径时的概率，如果lim+= 1 则称该条路径具有收敛性（Y 是路径上所有链路集合）。1.2.1 蚁群算法收敛性证明蚂蚁通过环境中的信息素与其它蚂蚁进行交互，不断的迭代循环，最终找到最优路径，但是，由于迭代的次数会受到具体链路环境的影响，虽然能够得到最优路径但有可能会迭代好多次.这就影响了算法的效率，一些专家学者对算法的收敛性进行了研究。关于蚁群算法的收敛性，很多研究者都进行了分析证明。早期的有GutjarhWJ 最先从有向图论的角度对特定的改进蚁群算法BGAS 的收敛性进行了证明[2],GutjarhW J 提出了两种新的GBAS，即GBAS/tdev 和GBAS/tdlb，通过选择合理的参数来保证蚁群算法的收敛性并收敛到全局最优解；Stuezle T 和Dorigo M 提出了一类改进蚁群算法——ACOgb 算法[3]并在理论上分析了它的收敛性，得出当迭代次数无限增大时，算法收敛到全局最优解。Yoo J H 等对一类分布式蚂蚁路由算法的收敛性进行了深入的理论研究[4]。1.2.2 对蚁群算法的改进蚁群系统由Dorigo 和Gambardella 于96 年提出，能够在一个合适的时间找出好的解决方案。但只限小规模的问题。由于此限制，专家学者们针对不同的问题对蚁群算法进行了改进，典型的蚁群算法的改进有：带精英策略的蚁群系统；基于优化排序蚂蚁系统；蚁群系统；最大-最小蚂蚁系统；最优-最差蚂蚁系统。带精英策略的蚁群系统类似于遗传算法的精英策略。在此系统中，为了使得当前找到的最有解对下一次迭代循环中更能增加蚂蚁选择的概率，在每次循环迭代完以后对最有解增加额外的信息素量。缺点：虽然使用精英策略可以使蚂蚁系统可以较早的找出最优的解，但是，由于使用的精英蚂蚁过多，搜索容易集中在最优值周围，从而不能找出更好的解来。基于优化排序的蚂蚁系统借助遗传算法中排序的概念，根据每只蚂蚁走过的路径的长短进行大小排序，并根据大小顺序进行加权，在这里只考虑几只最好的蚂蚁，从而避免局部极优路径被很多蚂蚁过分重视的情况发生。最大-最小蚂蚁系统[5] 是把集中到最优解的附近与避免早熟收敛行为结合在一起。该方法主要做了3 方面改进：①在每次循环迭代以后，只允许一只蚂蚁进行信息素更新，这只蚂蚁既有可能是找出此次循环中最优解的蚂蚁也可能是从一开始以来最优解的蚂蚁。②为了避免搜索的停滞，把路径上信息素轨迹...