地理信息智能化处理 课程作业蚁群算法及其应用 编程 关于数据挖掘软件weka的分析和总结

1、一、综述题以蚁群算法及其应用为题，撰写一个读书报告。要求通过广泛查阅国内外文献，撰写读书报告。蚁群算法及其应用 1 引言蚁群优化算法，简称为蚁群算法，由Marco Dorigo和他的同事首先提出来，作为一种多Agent的方法，很好地解决了一些复杂的组合优化问题，如旅行商问题（Traveling Salesman Problem）和指派问题（quadratic assignment problem），目前已经有很多种基于蚁群算法或其改进算法应用于各种不同的离散优化问题，这些研究已经涵盖了车辆路径规划（vehicle routing），顺序订货（sequential ordering），地图着色（

2、graph coloring）以及网络中的路由通信问题。2 蚁群算法的基本原理蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自组织模式。尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为，蚂蚁也不可能从这些解释中获益，但是数学及计算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法。蚁群优化，是该系统的核心内容，其原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够

3、很快地重新找到最优路径。人们通过大量的研究发现，蚂蚁个体之间是通过在其所经过的路上留下一种可称之为“ 信息素”（pheromone）的物质来进行信息传递的，随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。同时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食物源的目的。

4、图1能更具体地说明蚁群系统的原理。图1 蚁群优化系统示意图图A中设是蚁巢，E是食物源，H、C为障碍物，距离为d。由于障碍物的存在由A外出觅食或由E返回巢穴的蚂蚁只能经由H或C到达目的地。假设蚂蚁以“1单位长度/单位时间”的速度往返于A和E，每经过一个单位时间各有30只蚂蚁离开A和E到达B和D图（图1a）。初始时，各有30只蚂蚁在B和D点遇到障碍物，开始选择路径。由于此时路径上无信息素，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往C，15只选往H图（1b）。经过一个单位时间以后，路径BCD被30只蚂蚁爬过，而路径BHD上则只被15只蚂蚁爬过（因BCD距离为1而BHD距离为2），B

5、CD上的信息量是BHD上信息量的两倍。此时，又有30只蚂蚁离开B和D，于是各20只选择往C方向，而另外各10只则选往H方向图（1c）。这样，更多的信息素量被留在更短的路径BCD上。随着时间的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径。图2为通用蚁群算法的框架图2 通用蚁群算法框架3 应用3.1 旅行商（TSP）问题3.1.1 问题描述旅行商问题最常见的通俗解释为，一位推销员从自己所在城市出发，必须遍访所有城市之后又回到原来的城市，求使其旅费最少的路径。3.1.2 问题解决通常在介绍蚁群算法时都是以TSP问题为例来介

6、绍的，这里不再赘述。在多数的算法中都存在一个启发信息函数ij，称之为能见度函数。一个简明的处理方法就是令ij=1/d ij。3.2 作业调度问题3.2.1 问题描述作业调度问题(Job-shop Scheduling Problem，JSP)是一种资源分配问题。这里的资源主要是指设备资源，问题的求解目标是要找到一个将一组工件安排到设备上去，以使作业可为“最优”完成的方案。每个作业可由一些任务完成，而每个任务必须由特定的设备处理。一个调度是指按先后顺序条件将所有任务安排到设备上的一种方案。通常，约束的数目很大，其基本约束条件为：每道工序必须在它指定的机器上加工；同一时刻同一台机器只能加工一个零件

7、；每道工序必须在它前面的工序加工完毕后才能加工；每道工序一旦开始加工，在完成之前不允许中断。下面给出的是一个作业调度问题的描述：n个作业J l，J 2，J n在m台机器M1 ，M2，M m上加工，每个作业的加工路线不同。设N为工序的集合，工序的加工时间为d i，工序的开始时间为t t，在机器k上相邻工序对(表示相邻工序在机器k上加工的前后顺序)的集合为E k，具有工艺约束偏序关系的工序(作业内部工序之间的工艺要求)的集合为A。要确定满足上述约束条件的n个作业的加工顺序，使得最后完工作业的完工时间 (makespan) C max最小，C max的计算如下：3.2.2 问题解决利用析取图模型生成

8、析取图，其基本单位是“作业”，令每一只蚂蚁一次走完所有工序。蚂蚁寻找最优路径的过程是蚂蚁遍历图的过程。下面以一个3个作业2台机器的JSP问题为例来说明。结点0和结点7是虚结点，表示开始工序和结束工序。两台机器的作业结点集合分别是N1=l，4，6，N2=2，3，5。图3中的合取弧(表示为单箭头)，表示了具有工艺约束偏序关系的工序对。在机器N1上加工工序对的集合El为(l，4)，(6，4)，(l，6)，在机器N2上加工工序对的集合EZ为(2，3)，(2，5)，(3，5)。当各台机器上的工序的加工顺序确定后，最终的析取图(图4)也就确定下来了。在解的构造过程中，相对于求解TSP的过程来说，除了禁忌表

9、外，这里增添了一个“下一步允许访问的结点的集合”，这是由有工艺约束偏序关系的工序对决定的。所有的蚂蚁都从开始工序出发，终止于结束工序；相对于TSP过程来说，初始的蚂蚁则可以随机地分布在任意的结点上，并终止于该结点。其余过程均类似于TSP问题。 图3 3个作业2台机器的析取图 图4 确定机器加工工序的析取图3.3 二次分配问题二次分配问题(Quadratic Assignment Problem, QAP)是继TSP后，蚁群算法在组合优化问题领域的又一个重要应用。目前针对QAP的算法多是利用QAP和TSP的相似性而对求解TSP的蚂蚁算法的推广，并针对QAP问题的自身特点对算法做了相应的调整。QA

10、P是将n个设备指派到n个地点，地点i和j ( i , j = 1,2,n；ij)之间的距离为d ij，设备r和s( r, s=1,2,n; rs)之间的流量为a ij。记为n个非重复的自然数1,2,n的一个排列，排列中的第i个数值（i）表示设备i被指派到位置（i），记全部排列的集合为S( n)，则QAP问题就是寻找*S(n)，使得f(*)极小；在应用蚁群算法求解QAP时，首先将n个设备进行排列，然后根据排列顺序依次为每个设备选择一个地点。在蚁群算法模型中，图G中结点集合C由n个地点组成，边的集合L为所有节点的全连接，信息素浓度ij对应设备i被指派到位置j，人工蚂蚁随机地选择图G中的某个节点出发

11、，走访每个节点一次后完成一个解的构造过程。对于设备i，其选择位置j的概率计算方法如下：式中：ij的值为目标函数值下的倒数。信息素浓度ij的更新方法同蚁周算法类似，局部搜索算法采用禁忌搜索算法。3.4 车辆路径问题3.4.1 问题描述 车辆路径问题(Vehicle Routing Problem ，VRP)是一类交通运输优化问题，具体而言则存在着各种各样的VRP问题。Bullnheimer，Hartl和Strauss等人用蚂蚁算法解决了一个VRP问题，其表示如下：通过车辆的调度，使车辆的总行程最短。 G=( V, A, d)是一个完全有向权图(complete weighted directed

12、 graph)，其中V=v0，v1，v2，vn是顶点的集合，A=（vi，vj）；ij是连接顶点的弧的集合。顶点v0表示库房，而V中其余的顶点则表示为城市或客户，与弧（vi，vj）相关联的非负权值dij表示为顶点vi和vj之间的距离(或者为旅行时间，或者为旅行费用)。对每一个客户vi而言，都有一个确定的非负的需求qi和一个非负的服务时间i（q0=0，i=0）最终的目标是寻找一条最小费用的路径，同时满足：每个客户被一辆车辆访问的次数为一次仅且一次；所有的车辆都从库房出发，最后返回至库房；对每一条车辆路径，其总需求量都不能超过车辆的载重量Q；对每一条车辆路径，其路径长度(或服务时间等)不超过一个给定

13、的上界L。3.4.2 解决方法在蚁群算法中，蚂蚁在节点间的转移概率被定义为：对应的能见度启发函数则定义为：其中g和f是两个新引入的参数。信息素路径修改的方法如下:其中是路径信息素的挥发系数，其机理类似于ASrank：如果排名第µ位的蚂蚁经过弧(Vi，Vj)，则相应的信息素轨迹的增量uij等于（-）/L，否则为零。另外，如果弧属于已知的最优路径L*，则相应的还要增加信息素*ij，其中*ij等于1/L*。3.5 多选择背包问题3.5.1 问题描述多选择背包问题(Multiple Knapsack Problem, MKP)定义为有附加约束的背包问题，该问题带有互不相关的多选择约束。该问题

14、的一般性描述如下：有一个承重有限的背包，将要放入背包的物品被分为相互排斥的若干类。每类中有若干不同的项目。问题就是从每类中选择一个项目使得项目总重量在满足背包承重约束的前提下最小化费用，问题如图5所示。图5 背包问题示例3.5.2 解决方法 类似TSP问题的解决方法，首先进行图的构造。Gc= (C, L)，图中的结点C代表的是集合中的项目，边L则是集合中所有项目的全连接。每个项目的费用则赋给相应的结点。在蚂蚁行进的过程中，其释放的信息素i也是针对即将纳入解中的结点i。蚁群算法在节点间的概率转移公式为：启发函数j的选择有多种，信息素轨迹的修改方法和普通的蚁群算法相同。解的构造过程中，每只蚂蚁在根

15、据由信息素所决定的概率来选择下一个节点，每次循环添加一个节点，直到在满足约束条件的情况下不能再添加节点时才结束。这将导致蚂蚁所经过的路径长度是不等的，不同的蚂蚁所产生的解的长度也可能是不等的。3.6 网络路由问题蚁群算法在动态组合优化问题中的应用主要集中在网络通信方面，特别是网络路由选择问题(Network Routing Problem ，NRP)上。网络路由选择问题可以简单描述为在一个代表通信网络的全连接图中求解任何两个节点的最短路径问题。虽然在静态环境下该问题可以通过多项式算法求解，但在节点间流量(边的权重)随时间变化情况下，该问题的求解变得非常困难。针对网络路由问题设计了算法AntNe

16、t。与一般蚁群算法不同，在AntNet中，对于任一有向弧(i , j)，有N-1个信息素浓度值ijd0，1，d=1,2,N且di与之对应，ijd代表从节点i到达目的节点d时有向弧(i，j)上的信息素浓度。与弧(i，j)相对应的还有启发优先权系数ij ,其值可以根据当前时刻由节点i向节点j待发送的数据队列长度计算，等待队列越短，ij值越大。算法中每个蚂蚁有一个源节点s和目的节点d,在转移过程中，处于节点i的蚂蚁k根据由ijd和ij计算的概率值选择下一节点j。在构造由s到d的路径过程中，蚂蚁经历与数据转移同样的延迟时间。因此，蚂蚁由s到达d所经历的时间Tsd可以用作对该路径质量的评价。当蚂蚁k完成

17、一次路径构造过程后，根据该路径的质量对其所经过弧上的信息素浓度进行更新，而对于在路径构造过程中未经过弧的信息素浓度进行挥发计算。前面所述的主要是针对蚁群算法本身进行的研究，下面介绍的是将成熟的方法应用于各自不同特定的领域。电力系统优化是一个复杂的系统工程，它包括无功优化、经济负荷分配、电网优化及机组最优投入等一系列问题，其中很多是高维、非凸、非线性的优化问题。Hou等人将蚁群算法成功地用于解决经济负荷分配问题；王志刚等则解决了该算法在配电网优化规划中的初步设计问题。混流装配线是JIT (Just In Time )生产方式的具体应用之一，它可以在不增加产品库存条件下满足用户多样化的需求。混流装

18、配线有时也特指混合车型组装线，即在一定时间内，在一条生产线上根据顾客需求的变化生产出各种不同型号的产品这一类问题同属生产调度问题。孙新宇等人用蚁群算法解决了混流装配线调度问题。机器人路径规划就是在障碍有界空间内找到一条从出发点到目标位置的无碰撞且能满足一些特定要求的满意路径。近几年许多学者开始用蚁群算法在这方面进行了一系列出色的研究工作。为有效地解决机器人避障问题，并扩展其对具体问题的适应性，在蚁群算法中通过调整避障系数，可以得到不同的优化轨迹。樊晓平等对复杂环境下的机器人路径规划进行了初步尝试，但更多的工作有待进一步展开。电缆管线敷设问题与TSP问题类似。要求每一根电缆在从电缆连接起点设备开

19、始，通过不同的通道、竖井至电缆连接终端，连接起来的电缆所经路径最合理且总长度最短。鉴于整个电厂电缆路径所形成的网络相互交叉，敷设系统纷繁复杂，为此将互相独立又相关的树分解一个个小的蚁群系统，用于解决发电厂计算机电缆敷设系统的复杂性等问题，获得了比较理想的结果。在动态组合优化问题中，网络路由是一个典型的应用示例。国际上Schoonder-werd等人首先将蚁群算法应用于路由问题，国内张素兵、刘泽民等人提出了基于蚂蚁算法的QoS ( Quality of Service)路由调度方法及分段QoS路由调度方法。在分析路由问题时，顾军华等人用蚂蚁算法研究解决包含带宽、延时、延时抖动、包丢失率和最小花费

20、等约束条件在内的QoS组播路由问题，效果优于模拟退火算法及遗传算法。此外，蚁群算法还在数据挖掘、图像处理、分析化学、岩石力学等领域的应用取得了很大进展。4 结语蚁群算法是一种原理相对简单的新兴仿生进化算法，在许多领域已展现出它的优势和魅力。首先，它易于控制陷入局部最优的情况，能以最大的概率找到全局最优解；其次，具有贪婪启发算法的特征使系统在搜索过程的早期就可以找到接收的解答；再次，由于其本质上的并行性，一群算法并行实现成为一个研究方向，这将非常适用于巨量并行机。一群算法把每个个体看作一个Agent，体现的是“群体智能”的模式，每个个体具有相同的特性和能力，并通过信息素彼此通讯，有些研究已在考虑

21、给个体赋予一定的智能，例如赋予学习能力，或者对蚂蚁进行分工，这是蚁群算法的一个发展方向。另外，由于蚁群算法是以分布式的同优化计算方式为特征的，所以，对算法的并行机实现和协同计算也已应该是一个研究的方向。总之，蚁群算法作为一种新兴研究领域，处于人工生命与运筹学的交叉位置，将会得到不断深入的研究，其模型将会更丰富，也将会得到更加广泛的应用。二、编程题编程实现宽度优先搜索、深度优先搜索、等代价搜索、启发式搜索中的一种搜索方法，并实现八数码难题的求解。要求提交伪代码形式的算法说明及实验步骤和结果说明。深度优先搜索与八数码求解主函数 Chess * Begin,Target,* T; 设定目标棋盘Tar

22、get：1 2 3,8 0 4,7 6 5 获取初始棋盘Begin：Begin=RandomChess(&Target);判断Begin 和Target有几处不同：Appraisal(Begin,&Target); Begin->Parent=NULL; Begin->BelockDirec=None; Target.Value=0; 打印目标棋盘；打印初始棋盘；调用图深度搜索T=Search(Begin,&Target); If搜索成功 把搜索路径倒序 打印搜索结果Else搜索不成功打印“搜索不到结果.深度为Max_Step”深度搜索函数Struct Ch

23、ess * Search(struct Chess* Begin,struct Chess * Target) ；Chess * p1,*p2,*p;深度Step=0； p=NULL;queue<struct Chess *> Queue1; 存储初始棋盘节点到待处理队列Queue1.push(Begin);搜索： do p1=(struct Chess *)Queue1.front(); Queue1.pop(); 分别从四个方向推导出新子节点 跳过屏蔽方向：if(Direct=p1->BelockDirec) ；继续; 调用移动数码函数： p2=MoveChess(p1,

24、Direct,true) if(p2!=p1) 调用估价函数对新节点估价Appraisal(p2,Target) if p2是为优越节点 p2->Parent=p1; 设置屏蔽方向,防止往回推switch(Direct) case Up:p2->BelockDirec=Down;break; case Down:p2->BelockDirec=Up;break; case Left:p2->BelockDirec=Right;break; case case Right:p2->BelockDirec=Left;break; 存储节点到待处理队列Queue1.pu

25、sh(p2) If p2为0，则搜索完成 else p2不为0，则将p2作为劣质节点抛弃 深度step加1 If Step>Max_Step，则返回NULL; while(p=NULL | Queue1.size()<=0); 返回 p;估价函数int Appraisal(struct Chess * TheChess,struct Chess * Target) 初始化Value为0; 逐行逐列逐元素比较TheChess与目标棋盘的不同 if一个不同；Value+; TheChess->Value=Value; 返回Value值移动棋盘数码 struct Chess * M

26、oveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) struct Chess * NewChess; 获取空闲格位置，得到空格位置的行列号i，j移动数字初始化t_i=i,t_j=j; switch(Direct) case 往上： t_i加1； if(t_i>=3) 则AbleMove=false; break； case 往下： t_i减1； if(t_i<0) 则 AbleMove=false; break； case 往左： t_j加1； if(t_j>=3) 则AbleMove=

27、false; break； case 往右： t_j减1； if(t_j<0) 则 AbleMove=false; break； if(!AbleMove) 不可以移动则返回原节点TheChess; if(CreateNewChess)建立移动后的新棋盘NewChess 返回NewChess;初始化一个初始棋盘struct Chess * RandomChess(const struct Chess * TheChess) M=40随机移动棋盘步数 struct Chess * NewChess ; NewChess=new Chess();复制TheChess 到NewChess，fo

28、r(int i=0;i<M;i+) 随机移动棋盘 返回 NewChess;结果如图所示：（由于篇幅所限，只提供两次程序运行的结果） (1)(2)图1 最上方打印出的是目标棋盘，0代表棋盘中的空格 然后初始化一个棋盘，并调用估价函数显示与目标棋盘的差距 深度搜索成功 则倒序显示路径（每步都调用估价函数显示与目标棋盘的差距）图2 同 初使棋盘的不同，则搜索路径不同。 三、软件题任选一种数据挖掘软件进行操作使用，并进行分析和总结。关于数据挖掘软件WEKA的分析和总结WEKA的全名是怀卡托智能分析环境（Waikato Environment for Knowledge Analysis），同时W

29、EKA也是新西兰的一种鸟名，而WEKA的主要开发者来自新西兰。WEKA作为一个公开的数据挖掘工作平台，集合了大量能承担数据挖掘任务的机器学习算法，包括对数据进行预处理，分类，回归、聚类、关联规则以及在新的交互式界面上的可视化。1 安装  我安装的是WEKA3-5-5。安装方法很简单，并且继承了java 运行环境，不用担心任何配置。版本提供了function接口，并且支持反编译。用户可用性以及扩展性很强。2 操作环境 安装完成，运行WEKA图标，出现一个小型的图形用户接口（Graphical User Interface，GUI）（见图1），它的MDI（多文档界面）外观，让所有打开的窗

30、口更加明了。这个菜单包括五个部分（Program、Application、Tools、 Visualization、Help）提供了四种操作环境（见图2）图1 图形用户接口图2 四种操作环境这四种操作的基本原理都大同小异，只是提供的环境不一样。主要是看用户平时熟悉使用什么，比如喜欢直接用代码的一定热衷于SimpleCLI（见图3）；喜欢图标的更热衷于Knowledgeflow（见图4）。一般用户通常使用Explorer；Experiment和Explorer类似，只是支持格式不一样。Experimenter运行算法试验、管理算法方案之间的统计检验的环境。 图3 SimpleCLI环境 图4 K

31、nowledgeFlow环境3 一般用户重点适用Explorer图5 Explorer3.1 标签页 在窗口的顶部，标题栏下是一排标签。当 Explorer 首次启动时，只有第一个标签页是活动的；其他均是灰色的。这是因为在探索数据之前，必须先打开一个数据集(可能还要对它进行预处理)。 所有的标签页如下所示： Preprocess 选择和修改要处理的数据； Classify 训练和测试关于分类或回归的学习方案； Cluster 从数据中学习聚类； Associate 从数据中学习关联规则； Select attributes 选择数据中最相关的属性； Visualize. 查看数据的交互式二维图

32、像。 这些标签被激活后，点击它们可以在不同的标签页面上进行切换，而每一个页面上可以执行对应的操作。不管位于哪个页面，窗口的底部区域(包括状态栏、log按钮和WEKA鸟) 仍然可见。3.2 状态栏 状态（Status）栏出现在窗口的最底部。它显示一些信息让你知道正在做什么。3.3 Log 按钮 点击这个按钮，会出现一个单独的窗口，包含一个可拖动的文本区域。文本的加了一个时间戳，显示了它进入日志（log）的时间，一旦在WEKA 中执行某种操作时，该日志就会记录发生了什么。3.4 WEKA 状态图标 状态栏的右边是 WEKA 状态图标。当不运行任何进程时，WEKA鸟会坐下并打一个小盹。×符

33、号旁的数字显示了正运行的并发进程的数量。当系统空闲时，它是零，而当进程的数量增长时，它也会增长。在标签页preprocess里面有个open控件，是用来打开source file的，WEKA支持的文档格式为*.arff，其实是一个文本数据集。也支持URL或者DB打开方式，并且支持数据转换。 打开数据文件后，可以使用Filter进行一下过滤，此操作相当于“预处理的预处理”。Filter提供了许多算法来过滤数据，比如 filters/unsupervised/instance/normalize应该是一个标准化的算法（用户也可以编写自己的算法）。 这时窗体上已经给出这个数据集的一些基本特

34、征了，比如有多少属性，各属性的一些简单统计量，右下方还给出一些可视化效果比如柱状图。通过这些可以初步了解这个数据集了。接下来的两个标签页是classify(分类)和cluster(聚类)，接触数据挖掘的人对它们一定不会陌生。同样WEKA有许多分类和聚类算法可供选择（见图6），在这里面称为clasifier和clusterer。对cluster更加准确的翻译应该是“簇”。聚类的任务是把所有的实例分配到若干的簇，使得同一个簇的实例聚集在一个簇中心的周围，它们之间距离的比较近；而不同簇实例之间的距离比较远。对于由数值型属性刻画的实例来说，这个距离通常指欧氏距离。不过WEKA提供的classify功能似乎还不够灵活，只能定长度和定频率地分类。但这个关系不大，现在很多数据处理软件都可以做到这个