发布时间 : 星期六 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
第二章 群体智能
2.1群体智能的概念 2.1.1群体智能的定义
由群居生物的群体行为涌现的群体智能正越来越得到人们的重视。所谓群体智能指的是“无智能的主体通过合作表现出智能行为的特性”。一些受群居生物筑巢、觅食、迁徙、清扫蚁穴等行为启发而设计的算法成功地解决了组合优化、通信网络和机器人等领域的实际问题。Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置。
群体智能的特点如下：
(1)个体与个体和个体与环境的交互作用的实现是完全分布式控制，具有良好的自组织性，更能适应当前网络环境下的工作状态；
(2)没有中心的控制与数据，系统更具有鲁棒性，不会由于某一个或者某几个个体的故障而影响整个问题的求解，具有良好的健壮性；
(3)可以通过个体之间的非直接通信进行合作，这样的系统具有更好的可扩展性； (4)每个自治个体的能力十分简单，只需要最小智能，具有简单性。
2.1.2群体智能的概念及特点
群体智能这个概念来自对自然界中一些昆虫,如蚂蚁、蜜蜂等的观察。单只蚂蚁的智能并不高,它看起来不过是一段长着腿的神经节而已。几只蚂蚁凑到一起,就可以一起往蚁穴搬运路上遇到的食物。如果是一群蚂蚁,它们就能协同工作,建起坚固、漂亮的巢穴,一起抵御危险,抚养后代。这种群居性生物表现出来的智能行为被称为群体智能。Millonas M M 在1994 年提出群体智能应该遵循五条基本原则[2 ] ,分别为: (1) 邻近原则( Proximity Principle) ,群体能够进行简单的空间和时间计算； (2) 品质原则(Quality Principle) ,群体能够响应环境中的品质因子；
(3) 多样性反应原则( Principle of Diverse Response) ,群体的行动范围不应该太窄； (4) 稳定性原则(Stability Principle) ,群体不应在每次环境变化时都改变自身的行
9
山东师范大学硕士学位论文
为；
(5) 适应性原则(Adaptability Principle) ,在所需代价不太高的情况下,群体能够在适当的时候改变自身的行为。
这些原则说明实现群体智能的智能主体必须能够在环境中表现出自主性、反应性、学习性和自适应性等智能特性。但是,这并不代表群体中的每个个体都相当复杂,事实恰恰与此相反。就像单只蚂蚁智能不高一样,组成群体的每个个体都只具有简单的智能,它们通过相互之间的合作表现出复杂的智能行为。可以这样说,群体智能的核心是由众多简单个体组成的群体能够通过相互之间的简单合作来实现某一功能,完成某一任务。其中“, 简单个体”是指单个个体只具有简单的能力或智能,而“简单合作”是指个体和与其邻近的个体进行某种简单的直接通信或通过改变环境间接与其它个体通信,从而可以相互影响、协同动作。群体智能具有如下特点:
(1) 控制是分布式的,不存在中心控制。因而它更能够适应当前网络环境下的工作状态,并且具有较强的鲁棒性,即不会由于某一个或几个个体出现故障而影响群体对整个问题的求解。
(2) 群体中的每个个体都能够改变环境,这是个体之间间接通信的一种方式,这种方式被称为“激发工作”(Stigmergy) 。由于群体智能可以通过非直接通信的方式进行信息的传输与合作,因而随着个体数目的增加,通信开销的增幅较小,因此,它具有较好的可扩充性。
(3) 群体中每个个体的能力或遵循的行为规则非常简单,因而群体智能的实现比较方便,具有简单性的特点。
(4) 群体表现出来的复杂行为是通过简单个体的交互过程突现出来的智能( Emergent Intelligence) ,因此,群体具有自组织性。
2.1.3 从人工智能角度
人工智能学科正式诞生于1956 年,它是研究如何使机器(计算机) 具有智能,特别是自然智能如何在计算机上实现或再现的学科。要进行人工智能的研究,就必然涉及什么是智能以及什么产生智能的问题。关于什么是智能,麦卡锡(J McCarthy) 给出如下定义:在现实世界中智能是指能够实现目标的计算能力。但实际上,关于智能,至今还没有一个确切的公认的定义。因为人们还不能完全了解智能的所有产生机制。至于什么产生智能,
10
山东师范大学硕士学位论文
目前有三种不同的答案,分别为物质(蛋白质) 、符号和亚符号处理(信号) 。由于人们对智能本质有不同的理解,所以在人工智能长期的研究过程中形成了多种不同的研究途径和方法。其中主要包括符号主义( Symbolism) 、连接主义(Connectionism) 和行为主义(Behaviorism)。符号主义是人工智能最早的研究方法,它是以符号知识为基础,通过符号推理进行问题求解而实现的智能。符号主义认为,人类智能的基本单元是符号,智能来自于谓词逻辑与符号推理。其代表性成果是机器定理证明和各种专家系统。连接主义认为,智能产生于大脑神经元之间的相互作用及信息往来的过程中,因此它通过模拟大脑神经系统结构来实现智能行为,典型代表为神经网络。行为主义模拟了人在控制过程中的智能活动和行为特性,如自寻优、自适应、自学习、自组织等,强调智能主体与环境的交互作用。行为主义与符号主义、连接主义的最大区别在于它把对智能的研究建立在可观测的具体行为活动的基础上。
在行为主义人工智能系统中,每个智能体都是在逻辑上或物理上分离的个体,它们都是某一任务的执行者,而且都具有“开放的”接口,可以与其它智能体进行信息的交换。这些智能体能够自主适应客观环境,而不依赖于设计者制定的规则或数学模型,这种适应的实质就是该复杂系统的各要素(智能体和周围环境) 之间存在精确的联系。也就是说,在行为主义人工智能系统中必然存在一些协调机制,这些协调机制可以使智能主体与外界环境相适应,使智能主体的内部状态(即智能主体所具有的几个行为,如避障、探索等) 相互配合,并在多个智能主体之间产生协作。显然,协调机制的好坏直接影响智能系统的性能,因而寻找合理的协调机制成为行为主义人工智能的主要研究方向。群体智能是行为主义人工智能的一种代表性方法,上面所提特性也适用于群体智能。设计行为主义人工智能系统的三个基本原则同样适用于群体智能系统的设计。这三个原则是简单性原则、无状态原则和高冗余性原则。这里,简单性原则是指群体中每个个体的行为应尽量简单,以使系统便于实现,而且更加可靠;无状态原则是指设计时应该使系统的内部状态与外在环境保持同步,要求所保留的状态不能在系统中长时间起作用,这就使得系统对于环境的变化和其它失误有更强的适应能力;高冗余性原则是指设计时应该使系统能够与不确定因素共存,而不是消除不确定因素,这样可使智能系统的学习和进化过程保持多样性。
2.1.4 从复杂性科学角度
复杂性科学是研究复杂系统行为与性质的科学,其目标是解答一切常规科学范畴无
11
山东师范大学硕士学位论文
法解答的问题,如人类社会组织和制度的突变、物种的起源和灭亡等,它试图找到一种对自然和人类都适用的新科学,即复杂性理论。至于什么是复杂性,圣塔菲研究所的George A Cowan 认为[6 ] ,它往往是指一些特殊系统所具有的一些现象,这些系统都由很多子系统组成,子系统之间相互作用,通过某种目前尚不清楚的自组织过程使得整个系统变得更加有序。Cowan 对复杂性的认识有如下两个关键点:一是复杂性属于某个系统的内禀性质或特征;二是这个性质是突现的,即它是不能通过子系统的性质来预测的,是自组织过程的结果。具有此类性质的系统被称为复杂适应系统(Complex Adaptive Systems ,简称CAS) 。在CAS 中,复杂的事物是由小而简单的事物发展而来,这种现象被称为复杂系统的涌现现象,涌现的本质就是由小生大,由简入繁。我国学者用“开放的复杂巨系统”的概念来描述具有同样一些性质的系统[7 ] ,这类系统包括错综复杂的社会系统、人体系统、生态环境系统等,对这些系统关键信息特征或功能特征的研究就是复杂性研究的内容,其中包括进化和共同进化特性、适应性、自组织过程、自催化过程、临界性、多层次特性、相变及混沌的边缘等,最重要的就是宏观整体的涌现性质。与笛卡尔哲学不同,复杂系统的涌现特性代表着另一种看待世界的哲学观念。以笛卡尔哲学为基础的近现代科学以及文化传统强调从上到下的还原与分析方法,强调有一个中心控制单元的结构,是一种机械的观点。而复杂性研究则强调从下到上的集成方法,强调突现,这是非笛卡尔的观点。群体智能是对自然界中简单生物群体涌现现象的具体研究,因而它从属于复杂性研究,并且遵从非笛卡尔的哲学观念。在研究群体智能时应该采取自下而上的研究策略。
2.2群体智能算法总体模式
为得到算法模式，首先给出以下定义：
定义1：在群体智能寻优模式下, ?P代表具有一定数量智能个体的非空集合, 即
LN?P表示由N个智能个体P1，P2，?，PN 所组成的智能个体集合。
LN定义2：DETECT?P表示智能群体中智能个体检测信息的非空集合。在具体的算法模
LN式下,如果求解的问题建立在D维坐标体系下,各智能个体的坐标检测信息总和可表示为DETECT?P，其中每个智能个体Pi的D维坐标信息检测集合可表示为DETECT(Pj)。如果
LJ-1ND问题求解是在三维空间下,j可以取1，2，3，相应的坐标可表示为X、Y和Z。
12