发布时间 : 星期六 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
NL若将上述定义模式进行推广,则可用INFORM?P表示群体中各智能个体的广义信息集合。在坐标寻优问题中,其主要信息包括位置、速度、时间等,也可包括相应的外界环境信息,如约束信息、指令序列信息等。
定义3：AIM?P表示智能群体中各智能个体所要实现的总体任务目标,任务目标可以
LN涉及寻优、控制、规划等,并针对不同的应用领域有不同的具体表达,例如:对于函数寻优问题,主要指最大值或者最小值的求解。
定义4：CHARACTER表示特定的群体智能算法的一些其它特征参数的集合。在具体的寻优算法中, 要根据具体问题考虑特征参数的影响，确定该集合中特征参数的数目。
定义5：INSTRUCTION?P为针对群体中各智能个体的输出指令集合,该指令集合对每
LN个智能个体进行有序的指令输出,体现了群体智能算法的总体优化特征。指令的性质和特征根据对象的不同而不同,也与所要实现的任务目标的性质有关。比如在图像处理领域,它可以是对图像颜色信息、灰度信息以及图像边缘信息等的操作。指令的结果，即寻优算法的效果与各研究者所定义的算法模式相关。
定义6：ALGORITHM为所采用的具体群体智能算法。该算法可以是微粒群优化算法、蚁群算法和遗传算法等。
根据上面的定义，可以将群体智能算法的模式表述为下面的伪方程：
(1)INSRUCTION（?P）=ALGORITHM（INFORM（?P），AIM（?P），DETECT（?P），CHARACTER）
这里的“ = ”表示指令集合,并不简单等同于通常意义下的赋值关系。
算法总体模式图如下：
13
山东师范大学硕士学位论文
CHARACTEAIM ALGORITHM INSRUCT?P INFORM INFORM DETECT（?P）
图 1群体智能算法总体模式图
由上面的定义和伪方程，可以得到如图 1所示的群体智能算法总体模式图。根据求解问题的特征参数和总任务目标，使用群体智能的某一算法，得到需要的指令序列。然后将得到的指令序列应用到每个智能个体上，使它们做各自相应的调整。采集新得到的智能群体的信息集合，检测是否得到满足规则需要的目标。不满足就再使用群体智能算法，进行下一次的循环；否则可以结束任务。
2.3群体智能的功能
作为群体智能的典型实现模式,模拟生物蚁群智能寻优的蚁群算法和模拟鸟群运动模式的微粒群算法正在受到学术界的广泛关注。由于其概念简明、实现方便,,在短期内迅速得到了国际演化计算研究领域的认可,并在优化问题求解[3～6 ] 、电力系统[12～13 ] 、计算机[14 ] 、冶金自动化[15] 等领域得到了有效的应用
在实际中遇到的优化问题可分为2 类: 一类是连续优化问题; 另一类是离散优化问题。用于解决优化问题的方法很多, 传统的方法有线性规划、整数规划和动态规划方法, 现在常用的方法有各种进化计算方法, 如遗传算法(GA )、进化规划(EP) 等。蚁群优化和粒子群优化方法作为最近发展起来的群体智能方法, 对这类问题的解决提供了全新的
14
山东师范大学硕士学位论文
途径。借鉴蚂蚁觅食的思想，形成了群体智能的研究分支蚁群优化，已经成功应用于许多困难的，其已成功运用于旅行推销员问题、作业调度、离散优化问题、二次分配问题、路由选择等优化系统中。
群体智能算法在电力系统优化中有着广泛的应用,例如在配电网扩展规划、检修计划、机组组合、负荷经济分配、最优潮流计算与无功优化控制、谐波分析与电容器配置、配电网状态估计、参数辨识、优化设计等方面 。电力系统优化问题存在着维数灾、局部最优和约束条件及目标函数不易处理等特点,随着系统规模的增大,待选方案将显著增多,发生“组合爆炸”现象,有的还属于典型的非凸多峰问题,除了全局最优解外,一般还存在若干局部最优解,因此用传统的优化方法解决这类问题,往往得不到满意的结果,特别在系统规模较大时更是如此。群体智能算法可以有效地进行此类问题的求解。
蚂蚁优化算法在电信网络的路由问题(ACR)上的应用已经比较成熟，HP 公司、英国电信公司都在20世纪90年代后期就展开了这方面的研究[1]。该算法也越来越多地应用于企业，如工厂生产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件，每年至少节约上千万美元开支。英国联合利华公司已率先利用这种技术改善其一家牙膏厂的运转状况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用相应技术以改善其运转的机能。近年来群体智能的应用有构建网站、优化搜索引擎、创建知识管理系统甚至进行音乐创作等。而粒子群优化主要用来解决连续优化问题。并已成功的应用于人工神经网络的训练方法[16]、分类XOR 问题的神经网络训练[17]、极大极小问题[18 ]、多目标优化[19 ]等方面.
2.4群体智能的两种模式
目前,群体智能主要有两种算法模式,分别是蚁群算法(Ant Colony System ,简称ACS) 和微粒群优化算法(Particle Swarm Optimization ,简称PSO) 。
2.4.1蚁群算法
蚁群算法是由M Dorigo 等人于1991年首先提出的[8～9 ] ,是受到自然界中蚂蚁群的社会性行为启发而产生的,它模拟了实际蚁群寻找食物的过程。在自然界中,蚂蚁群总是能够找到从巢穴到食物源之间的一条最短路径。这是因为蚂蚁在运动过程中,能够在其
15
山东师范大学硕士学位论文
所经过的路径上留下一种被称之为“外激素(pheromone) ”的物质。该物质能够被后来的蚂蚁感知到,并且会随时间逐渐挥发。每个蚂蚁根据路径上外激素的强度来指导自己的运动方向,并且倾向于朝该物质强度高的方向移动。因此,如果在某一路径上走过的蚂蚁越多,则积累的外激素就越多,强度就越大,该路径在下一时间内被其它蚂蚁选中的概率就越大。由于在一定时间内,越短的路径会被越多的蚂蚁访问,所以随着上述过程的进行,整个蚁群最终会找到从蚁穴到食物之间的最短路径。蚁群算法正是利用了生物蚁群的这一特性来对问题进行求解。由于蚂蚁寻食的过程与旅行商问题( TravelingSalesman Problem ,简称TSP) 的求解非常相似,所以蚁群算法最早的应用就是TSP 问题的求解。目前,蚁群算法已在组合优化问题求解,以及电力、通信、化工、交通、机器人、冶金等多个领域中得到应用,都表现出了令人满意的性能。
2.4.1.1基本原理
生物学家发现,每只蚂蚁在走过的路径上会留下一种称为信息素(pheromone) 的化学物质,蚂蚁之间就是靠感知这种物质的浓度进行信息传递的。蚂蚁倾向于朝浓度高的方向移动,这样就形成了一种正反馈机制。蚁群算法就是模拟了这个过程,该算法的思想是:用蚂蚁的行走路线表示待求解问题的可行解,每只蚂蚁在解空间中独立地搜索可行解,解的质量越高,在“行走路线”上留下的信息素也就越多,随着算法的推进,代表较好解的路线上的信息素逐渐增多,选择它的蚂蚁也逐渐增多,最终整个蚁群在正反馈的作用下集中到代表最优解的路线上,也就找到了最优解。
图1 是一个基于蚁群算法的人工蚁群系统寻找最短路径的例子。
E E 蚁数30 蚁数30 E 蚁数 15 蚁数15 蚁数10 蚁数20 d=1 d=0.5 D D D H C C C H H B 蚁数 15 B 蚁数 15 蚁数20 d=1 d=0.5 蚁数30 蚁数10 B 蚁数30 A A A （a）人工蚁群搜索环境 （b）时刻人工蚁群搜索情况 （c）时刻人工蚁群搜索情况 16