第1章绪论
本章介绍智能计算和挖掘方法各领域的经典算法。首先讨论以神经网络、进化、遗传、免疫、生态等为主的智能计算方法的特点，然后介绍以数据处理为核心的十大经典智能挖掘方法。
1.1智能计算方法
智能是个体有目的的行为、合理的思维，以及有效地适应环境的综合性能力。人工智能相对人的自然智能，用人工方法和技术，模仿、延伸和扩展人的智能(钟珞等，2009)。长期以来，人们从人脑思维的不同层次出发，对人工智能进行研究，形成符号主义、连接主义和行为主义。
传统的人工智能是符号主义，以Newell和Simon提出的物理符号系统假设为基础(吕品等，2012；史忠植，1998)。物理符号系统假设认为，物理符号系统是智能行为充分和必要条件。物理符号系统由一组符号实体组成，它们都是物理模式，可在符号结构的实体中作为组分出现。该系统可以进行建立、修改、复制、删除等操作，以生成其他符号结构。连接主义，或计算智能与分布式人工智能(Distributed Artificial Intelligence，DAI)是密不可分的。人们在研究人类智能行为中发现，大部分人类活动都涉及多个人构成的社会团体，大型复杂问题的求解需要多个专业人员或组织协作完成。“协作”是人类智能行为的主要表现形式之一，分布式人工智能正是为适应这种需要而兴起的。尤其是随着计算机网络、计算机通信和并发程序设计的发展，分布式人工智能逐渐成为人工智能领域的一个新的研究热点，作为人工智能的一个分支，DAI主要研究在逻辑上或物理上分散的智能动作者如何协调其行为，即协调它们的知识、技能和规划，求解单目标或多目标问题，为设计和建立大型复杂的智能系统或计算机支持协同工作提供有效途径。分布式系统的本质决定了它是复杂的、非线性的、通过各子系统间的协同达到更高有序态的系统，因此，分布式人工智能的主要研究方法是连接主义的而不是符号主义的。
20世纪50年代以后一段时间，符号智能体系取得了巨大的成功，但80年代中期以来，这种经典人工智能的发展由辉煌转入相对停滞状态，而计算智能在神经网络的带动下异军突起(石纯一等，1993)。与生命科学、系统科学密切联系是计算智能的突出特点，正是由于这个特点，不仅计算机科学家，而且众多其他学科的学者也加入计算智能的研究中来，极大地促进了它的发展。
1.1.1神经网络
神经网络是连接主义的经典代表。神经网络是由大量神经元广泛互连而成的复杂网络系统，诞生于1943年(吕品等，2012)。单一神经元可以有许多输入、输出。神经元之间的相互作用通过连接的权值体现。神经元输出是其输入的函数。常用的函数类型有线性函数、S型函数和阈值型函数。虽然单个神经元的结构和功能极其简单和有限，但大量神经元构成的网络系统的行为是极其丰富的。单个神经元、Hopfield网络模型和前向神经网络的结构如图1.1所示。
图1.1神经网络
智能方法及应用第1章绪论神经网络的基本特点如下。
(1) 大规模并行处理:神经网络能同时处理与决策有关的信宿，例如，虽然单个神经元的动作速度不快，但网络的总体处理速度极快。
(2) 容错性:由于神经网络包含的信息是分布存储的，即使网络某些单元和连接有缺陷，它仍然可以通过联想得到全部或大部分信息。
(3) 自适应和自组织性:神经网络系统可以通过学习不断适应环境，增加知识的容量。
1.1.2遗传算法与演化计算
1. 遗传算法
遗传算法(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是由Holland于1975 年首先提出的(Holland，1975)。其主要特点是群体搜索策略和群体之间的信息交换。与解析法、穷举法、随机法等传统搜索方法相比，遗传算法具有不需搜索空间的知识、并行爬峰、编码方法适应性广等特点。遗传算法是所谓“演化计算”的一种。遗传算法的基本流程和要素如图1.2所示。
图1.2遗传算法
根据模式定理(Schemata Theorem)，遗传算法中串的运算实际上是模式的运算，遗传的进化实际上是模式的进化。低阶、短定义距及平均适应度高于群体适应度的模式(积木块)在子代中将以指数级增长，积木块在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，可最终生成全局最优解。
遗传算法具有隐并行性，在对n个串个体进行运算时隐含处理了O(n3)个模式。实际上，在自然进化过程的任何时刻，总是同时有大量的物种在彼此独立地向前进化。在同一物种内部，也同时存在着大量的个体在通过自然选择、交配和基因突变而进化。显然，自然界的进化过程本身就是一个并行过程。遗传算法源于自然进化，自然也就继承了自然进化过程所固有的并行性。
标准遗传算法是生物遗传过程的一个非常简化的模拟。事实上，由于遗传以及更广泛的进化与生态的关系是密不可分的，在遗传算法中引入生态因素是非常重要的。这方面经典的有小生境(Niche) 技术(史忠植，1998；Futuyma，1986)。
2. 演化计算
演化计算(Evolutionary Computation)，又称进化计算，是遗传算法的超集，其特点是群体搜索策略和群体中个体之间的信息交换。目前研究的进化算法主要有遗传算法、进化规划(Evolutionary Programming，EP)和进化策略(Evolutionary Strategies，ES)(Futumyma，1986)。尽管它们之间很相似，但历史上这三种算法是彼此独立发展起来的。
遗传算法由美国Holland创建，后由DeJong等进行了改进；进化规划最早由美国的Gfogel、Owens和Walsh提出；进化策略由德国的Rechenberg和Schwefel建立。三种算法既有许多相似之处，同时也有很大的不同:①进化规划和进化策略都把变异作为主要的搜索算子，而在标准遗传算法中，变异只处于次要地位；②交叉在标准遗传算法中起着重要作用，而在进化规划中完全省去，在进化策略中与自适应结合在一起使用非常重要；③标准遗传算法和进化规划都强调随机选择机制的重要性，而从进化策略的角度看，选择是完全确定的，没有合理的根据表明随机选择原则的重要性；④进化规划和进化策略确定地把某些个体排除在选择复制之外，而标准遗传算法一般对每个个体都指定一个非零选择概率(Robert，2006)。
此外，在所谓的“智能进化”中，除了考虑遗传因素外，还考虑到学习，这就是进化的强化学习(ERL)(Futumyma，1986)。在ERL中，评价网络的结构和结合强度均由遗传决定，而行动网络的结合强度则有可能通过学习决定。而且这种学习信号的源泉，也仅限于评价网络的报酬信号。这是通过遗传决定的评价网络的报酬信号对行动网络结合强度实行最优化的一种强化学习方法。
1.1.3免疫信息处理
人体免疫系统是一个高度进化、复杂的生理机制，免疫系统通过高度复杂的网络结构来识别和排除抗原性异物，维护体内环境的稳定。免疫过程中所具有的识别能力、学习和免疫记忆功能，以及自适应调节机制等特性具有重要的工程应用价值。1994年以来，免疫信息处理成为国际上新的研究热点。从工程应用的角度，可抽取出免疫反应的概念化模型，如图1.3所示。图中免疫识别能够识别自我(Self)和非我(Non.Self)，对模式识别和计算机病毒防治等都具有重要的的意义。
图1.3免疫反应模型
在免疫调节中，一个比较成功的学说是Jerne网络模型。这种高度联结的网络具有非线性动力系统所具有的稳定平衡点(该点对应于免疫记忆)，当抗原侵入时，扰动网络的平衡，通过内部节点间的作用关系而形成新的平衡点。该网络学说能较好地解释免疫记忆、免疫学习及免疫耐受等重要特点。基于该网络学说的思想和模型已在组合优化问题、自适应控制等方面取得了较好的效果。
免疫系统与脑神经系统在系统行为上具有很多相似性，如识别、学习和记忆性能等，但是它们却有着不同的信息处理机制。免疫细胞间呈现着一种相互刺激和抑制的对称作用关系，这不同于脑时间元之间的作用关系。免疫系统广泛分布于全身，它们通过在时间和空间上分布式的网络结构来实现各种免疫功能，并且这种网络结构和作用关系是随着环境的不同而不断变化的。而经典人工神经网络是一种固定连接的网络模型。
免疫与遗传系统之间也是相互区别和联系的，由于抗原、抗体的特性是通过基因编码体现的，体内多样性抗体的产生也是基于免疫细胞分裂时进行的基因交叉和变异而实现的，这种基于遗传交叉的多样性操作，以及基于变异和选择等自适应群体层次的操作，对构成免疫识别和记忆具有重要的作用。但免疫系统与遗传系统有着本质的区别:遗传算法是一种单一功能个体的进化，对于每个个体，只能适应某个问题或环境，一旦环境变化，进化将前功尽弃；而免疫系统是将环境(非己)和自己相互作用直接考虑的。和遗传算法相比，免疫系统还有如下特征。
(1) 不是独立地对每个个体进行评价和选择，而是以共同作用为前提，考虑共生关系与系统化。
(2) 自我与非我的识别是一种特殊的模式识别，因此有特殊的多样性和选择操作。
(3) 自适应性体现在包括结构层次在内的各种层次中。
(4) 更能在线适应变动的环境。
(5) 免疫与生态系统具有某些联系。在博弈生态系统中，博弈可产生抗体\[6\]。
1.1.4生态计算
生态计算或计算生态学(the Ecology Computation)，是神经网络、遗传算法、演化计算、免疫信息处理等在更高层次的概括——尽管其发展与上述各分支是相互独立的(曹先彬等，1999；Robert，2006)。
从历史的角度，生态计算具有几个相对独立的来源。而这些相对独立的来源却得到了类似的结论，这无疑从一个侧面反映了生态计算作为计算智能的集大成者，其产生是在智能计算发展到一定阶段后的必然结果。其发展可描述如下:
(1) 开放信息系统→计算生态学；
(2) 博弈论→博弈生态系统→生态动力学；
(3) 反馈与控制理论→生态学模型；
(4) 非平衡态统计物理学→非平衡相变→反应扩散方程和序参量方程→进化方程。
生态系统中的自组织可从几个方面考察。从博弈论的角度考察，生态系统中的各种策略(如K策略、R策略)，根据其适应度、淘汰、变异等，缓慢地进化。那些能够适应环境的策略类型或者相互依存的策略集团自发地形成具有新的秩序的组织。从协同的角度，计算的过程可以看成一种相变，是系统处在一种非线性结构下产生新的更有序的空间结构和时间结构的过程。
生态计算的关键不是设计一种新的方法直接解决实际问题，它更多是面向智能计算的一般原理，说明智能计算中的某些基本原则的。在这个意义上，也可以把它称为“广义生态学”。下面还要详细地讨论这个问题。
1.1.5各领域的内在联系
智能计算的各领域之间不是相互独立的，而是有着深刻的内在联系。连接主义的思维方式与传统的符号主义不同，智能计算的各领域用不同方式实现了连接主义的计算，即研究简单个体如何在简单交互规则指导下，构成具有复杂智能行为的高层系统。由此带来各种算法的统一特点，如社会性、并行性、单元的智能性、开放性等。
各领域服从统一的模型，即“开放式计算系统”模型。智能计算是多个简单个体通过生态行为，或者说是社会行为，自组织地形成智能的过程。系统是由异构的、分布的、动态的、大规模的、自主的成分构成的计算系统，一个复杂的计算任务由大量的计算单元非同时的计算行为完成；执行这些任务的单元的全部特性对其他单元甚至系统本身也是未知的；大量的单元的行为决定是基于它们对系统的不完全知识和延迟的甚至是矛盾的信息做出的。
遗传算法是进化计算的特例，而进化实际上是一种特殊的生态行为(曹先彬等，1999)。进化包含遗传的因素，但进化不能只从遗传的角度出发来考察问题，同样演化计算也不能仅以遗传变异机制为限(如经典演化计算所做的)。进化是非生物环境和生态系统共同作用的结果，而且环境通常通过生态系统对物种的进化起作用；物种在进化中相互作用，形成所谓的“协同进化”(Coevolution )。因此，如果把以遗传算法为代表的演化计算作为“微观演化”或“基因进化计算”，那么，演化计算的进一步研究将导致“生态进化计算”的产生。
生态模型具有共性
展开
