学文网摘要:为了解决传统智能方法无法突破的问题,推进机器智能化的进程,计算智能应运而生。计算智能的兴起引起了机器智能领域广泛的关注。该文系统阐述了几种主要计算智能算法的发展历程,分析了算法的基本原理,并对算法的特点和实际应用做了简单介绍,最后展望了计算智能将来的发展方向。
关键词:计算智能;人工神经网络;模糊系统;遗传算法;免***算法
中***分类号:TP18 文献标识码:A文章编号:1009-3044(2010)09-2207-04
Overview of the Main Algorithm for Intelligent Computing
ZHOU Hong-mei
(Huaihua Technical School, Huaihua 418000, China)
Abstract: In order to resolve some problems that the traditional intelligent method can not breakthrough,and promote the process of intelligentizing machines, Computational Intelligence is presented.The development of Computational Intelligence has given rise to considerable concerns in the machine intelligence field.This paper summarizes several main Computational Intelligence algorithms'developing process,analyzes its'basic theories,and simply introduces its'characters and practical applications.At last,the paper looks ahead the direction of Computational Intelligence's advance.
Key words: computational intelligence; artificial neural network; fuzzy system; genetic algorithm; immune algorithm
众所周知,人们对于生活中遇到的各种复杂的情况可以不假思索的做出决策判断,然而这对于先进的电子计算机却相当的困难,这是由于电子计算机的体系结构所决定的。要想使电子计算机具有较强的形象思维能力,必须突破冯・诺依曼的体系结构,另辟蹊径。近年来,随着人工智能应用领域的不断扩展,传统的基于符号处理机制的人工智能方法碰到的问题越来越突出,特别是在知识表示、处理模式信息及解决组合爆炸等方面[5]。因此,寻求一种适合大规模并行且具有智能特征如自适应、自学习、自组织等的算法已经成为有关学科的一个研究目标。计算智能(CI,Computational Intelligence)在这种背景下应运而生。
早在1988年,计算智能这个概念是加拿大的一本刊物的名字。1992年,美国学者James C.Bezdek在论文《计算智能》中将智能分为生物智能(BI,Biological Intelligence)、人工智能(AI,Artificial Intelligence)和计算智能(CI,Computational Intelligence)三个层次,并讨论了人工智能与计算智能的区别[1]。CI的主要处理对象是应用人员提供的数据材料,包括数字、信号等,它并不依赖于知识;而AI则必须用知识进行处理各种数据信息。计算智能的目标是模仿人的智能,包括模拟人脑的结构和模仿人脑的逻辑思维。
目前主要的计算智能方法有人工神经网络(ANN,Artificial Neural Network)、模糊逻辑(FL,Fuzzy Logic)、进化算法(EA,Evolution Algorithm)、免***算法(IA,Immune Algorithm)、人工内分泌系统(AES,Artificial Endocrine System)、模拟退火、禁忌搜索算法、粒子群算法、蚁群算法等。其中进化算法又包括遗传算法(GA, genetic algorithm)、进化规划(EP, evolution plan)、进化策略(ES, evolution strategy)。本文分别从算法的产生和发展、算法的基本原理、算法的特点及其应用和发展趋势等方面对几种具有代表性的计算智能算法进行了总结和分析,希望能让读者对计算智能的发展有一个大致的了解。
1 人工神经网络
1.1 人工神经网络的发展
人工神经网络(Artificial Neural Network,ANN)是脑科学、神经心理学和信息科学等多学科的交叉研究领域,是近年来高科技领域的一个研究热点。它的研究目标是通过研究人脑的组成机理和思维方式,进而通过模拟人脑的结构和工作模式使机器具有类似人类的智能。人工神经网络的发展已有60多年的历史。早在1943年,美国心理学家McCulloch和数学家Pitts联合提出了形式神经元的数学模型,即经典的M-P模型,从此开创了神经科学理论的新纪元。其后,Rosenblatt、Widrow和Hoff等学者又先后提出了感知器模型[1,3],使得人工神经网络技术得以蓬勃发展。20世纪六七十年代是人工神经网络发展的低谷期,直到1982年加州大学的物理学家Hopfield提出了Hopfield网络模型并用电路实现,人工神经网络的研究重新进入了兴盛时期。
1.2 人工神经元的工作过程
人工神经网络是由大量处理单元经广泛互连而组成的人工网络,用来模拟人脑神经系统的结构和功能。而这些处理单元称为人工神经元。人工神经元的形式化模型种类很多,最常见的有M-P模型、线性加权模型和阈值逻辑模型。下面通过M-P模型来简单的介绍人工神经元的工作过程。***1为M-P神经元模型***。
人工神经网络中的每一个神经元都可以接受一组来自该网络中其他神经元的输入信号,并且每个输入信号有一定的强度,用连接权值来表示,所有输入信号的加权和决定该神经元的激活状态。假设来自其他处理单元(神经元)i的输入信息为xi,它们与该处理单元的相互作用强度即连接权值为wi(i=0,1,...,n-1),处理单元的内部阈值为θ 。那么该处理单元的输入为:,输出为:。此式中f 称为激发函数或作用函数,它决定了神经元的输出。该输出为1或0取决于其输入和大于或小于内部阈值θ 。激发函数一般具有非线性特性。常用的非线性激发函数有阈值型、分段线性型、Sigmoid函数型(简称S型)和双曲正切型[3]。
1.3 人工神经网络的应用
人工神经网络能较好的模拟人的形象思维,对信息具有很好的隐藏性,还具有容错性强、鲁棒性强和自学习性强等特点,是一个大规模自组织、自适应且具有高度并行协同处理能力的非线性动力系统。人工神经网络理论的应用已经渗透到各个领域[2]。
信息处理领域:包括信号处理、模式识别和数据压缩等方面的应用。
自动化领域:包括系统辨识、神经控制器和智能检测等方面的应用。
工程领域:包括在汽车工程、***事工程、化学工程和水利工程等方面的应用。
经济领域:包括在微观经济领域的应用、在宏观经济领域的应用、在证券市场中的应用、在金融领域的应用和在社会经济发展评价和辅助决策中的应用。
医学领域:包括检测数据分析、生物活性研究和医学专家系统等应用。
2 模糊系统
2.1 模糊理论的发展
模糊概念在生活中普遍存在,如“高”,“大”等。这些模糊概念蕴含了许多不确定信息,人脑可以很容易的通过这些不完整不精确信息做出判断和决策。然而,对于精确的电子计算机而言,处理含糊不清的信息却是相当困难的。基于这个原因,美国控制论专家扎德(Zadeh.L.A)于1965年提出了模糊集合的概念,发表了开创性论文《模糊控制论(Fuzzy sets)》,为模糊系统的研究奠定了坚实的基础。1973年,扎德教授又提出了模糊逻辑(Fuzzy Logic)的理论,并积极倡导将模糊理论向人工智能方向发展。经过众多研究者的不断努力,模糊逻辑理论已经得到进一步发展,并在专家系统不确定推理模型的设计中显示了很强的生命力。另一方面,模糊理论在学术界也得到了普遍的认同和重视。1992年IEEE召开了第一届关于模糊系统的国际会议(FUZZ-IEEE),1993年IEEE创办了专刊IEEE Transaction on Fuzzy System。当前,模糊理论和应用正在向深度和广度进一步发展,发展的速度越来越快,涌现出了大量的研究成果,已经成为了世界各国高科技竞争的重要领域之一。
2.2 模糊系统的原理
模糊系统(Fuzzy System, FS)基于模糊数学理论,能够对事物进行模糊处理。模糊数学基础包括模糊集合、模糊逻辑、模糊规则、模糊推理和隶属度等。在模糊系统中,元素与模糊集合之间的关系是不确定的,即在传统集合论中元素与集合“非此即彼”的关系不适合模糊逻辑。元素与模糊集合的隶属关系是通过隶属度函数来度量的。当一个元素确定属于某个模糊集合,则这个元素对该模糊集合的隶属度为1;当这个元素确定不属于该模糊集合时,则此时的隶属度值为0;当无法确定该元素是否属于该模糊集合时,隶属度值为一个属于0到1之间的连续数值。在模糊系统中,知识是以模糊规则的形式存储的,如:IF E THEN H (CF, λ ),其中E表示模糊规则的条件,H表示模糊规则的结论,它们都是模糊的。CF表示这个规则的可信度,它既可以是一个确定值,也可以是模糊数或语言值,λ 是阈值,用于确定这条知识是否能被应用。模糊推理引擎运用这些模糊规则进行模糊逻辑推理,完成对不确定性问题的求解。***2是模糊系统的基本结构***。
2.3 模糊系统的应用
模糊系统能够很好处理人们生活中的模糊概念,清晰地表达知识,而且善于利用学科领域的知识,具有很强的推理能力。模糊系统主要应用在自动控制、模式识别和故障诊断等领域并且取得了令人振奋的成果,但是大多数模糊系统都是利用已有的专家知识,缺乏自学习能力,无法对自动提取模糊规则和生成隶属度函数。针对这一问题,可以通过与神经网络算法、遗传算法等自学习能力强的算法融合来解决[9,16]。目前,很多学者正在研究模糊神经网络和神经模糊系统,这是对传统算法研究和应用的创新。
3 遗传算法
3.1遗传算法的基本原理
遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国Michigan大学的Holland教授及其学生和同事共同发展起来的,是一种模拟生物界的自然进化规律而形成的一种基于全局的直接优化搜索算法,是一种进化算法。
遗传算法的基本思想源于达尔文(C.R.Darwin)的进化论和孟德尔(G.J.Mendel)的遗传学说。达尔文进化论的最基本原理是适者生存。在生物进化的过程中,只有那些能适应环境的一些个体特征才能得以保留。遗传学说的最基本原理是基因遗传原理,遗传以基因的形式包含在染色体中,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可以产生更适应于环境的后代。经过存优去劣的自然选择,适应性高的基因结构得以保存[3]。
遗传算法用“染色体”来表示问题的解。在执行遗传算法之前,首先给定一个“染色体”群,称为假设解。然后,把这些假设解置于问题的“环境”之中,通过适者生存原则,选择对环境适应度高的“染色体”进行复制,交换和突变等操作。如此逐代进化,最后算法收敛到一个适应度最高的“染色体”,此为问题的最优解。***3为遗传算法的基本流程***。
3.2 遗传算法的特点
遗传算法是一个不断寻找最优点的过程,它始终让整个群体保持进化状态。与传统优化方法比较,遗传算法主要有以下几个特点。
智能性:遗传算法具有自适应、自组织和自学习性等。在求解问题时,在确定编码方案、适应度函数和遗传算子之后,算法将根据自然选择的策略自组织进行搜索。
并行性:遗传算法的操作对象是一个可行解集合,而非单个可行解。它采用同时处理多个可行解,基于全局搜索优化[14]。这使得遗传算法减少了陷入局部最优解的可能性,同时体现了遗传算法良好的并行性。
不确定性:遗传算法的主要步骤都含有随机性,如交换操作、突变操作等,因此在算法的搜索方向具有很大的不确定性[4]。
通用性:遗传算法的处理对象不是参数本身,而是对参数集进行了编码的个体。这种编码操作,使得遗传算法可直接对结构对象进行操作[15];同时,该算法只需要适应度函数来评估个体,无需其他辅助信息。以此,它几乎可以处理任何问题。
作为一种搜索算法,遗传算法在各种问题求解和应用中展现出了它的特点和魅力,同时也暴露出了不足和缺陷。由于遗传算法的处理对象是编码的个体,因此编码方式很大程度上影响了算法的效率和结果;算法本身参数的设置无法定量表示;对于数量较大的群体,算法的收敛速度慢等。目前出现了很多基于上述问题的遗传算法的改进算法[10],如一种快速收敛的遗传算法,通过改变初始化群体的生成方式,较好地解决了算法收敛速率的问题。
3.3 遗传算法的应用
由于遗传算法具有的优点众多,因此其应用范围也极其广泛。遗传算法主要应用于神经网络、模式识别、组合优化、机器学习、***形处理等。下面介绍遗传算法作为一种机器学习技术在分类系统中的应用。
遗传算法在分类系统中主要是对分类系统中的分类器[3],即规则进行学习,用以产生更好的分类规则。其主要步骤如下:
1)根据分类器(规则)的适应度成正比的概率,选择复制出N个规则。
2)对选出的规则,利用遗传算法中的遗传操作(交叉、突变),重新生成N个新规则。
3)用产生的“后代”(新规则)取代分类器中适应度小的规则。
当一次遗传算法学习过程结束之后,如果得到群体中的规则和其父代完全相同,且各规则的适应度值已连续多次保持不变,则认为算法收敛,学习过程结束。
4 免***算法
4.1 免***算法的发展
1974年,诺贝尔奖得主,生物学家、医学家、免***学家Jerne提出了免***系统的第一个数学模型,为免***算法的研究奠定了基础。之后Farmer,Perelson,Bersini,Varela等学者先后于1986年,1989年和1990年发表了相关论文,为免***算法在实际工程中的应用做出了突出贡献,同时他们的研究工作为建立基于免***理论的计算系统和智能系统开辟了道路。目前,免***算法已经成为国际智能计算领域关注的热点和前沿课题。2002年,IEEE Transaction on Evolution Computation首次出专刊报到了有关人工免***系统(Artificial Immune System)的研究进展。在国内,免***优化算法的理论研究和应用具有鲜明的特色。中国科学技术大学王煦法教授在国内较早开展对免***优化算法方面的研究,并把它应用到了人工生命和硬件领域。西安电子科技大学焦李成教授提出了比较完备的免***克隆算法的理论基础以及一些改进算法,并较早地在国际上创造性地提出了免***算法与遗传算法的结合――免***遗传算法[6,13]。免***算法正以朝气蓬勃的姿态发展。
4.2 免***算法基本原理
免***是生物体的特异性生理反应。生物免***系统由具有免***功能的器官、组织、细胞和免***效应分子及其基因组成,通过分布在全身的各类淋巴细胞识别和清除侵入生物体的抗原性异物。当抗原入侵生物免***系统时。首先与抗原亲和力高的抗体受刺激产生克隆和高频变异,生成新抗体种类,然后亲和力更高的抗体结合抗原后引起更强的反应,经过不断循环筛选出匹配抗体。人工免***系统就是研究、借鉴和利用生物免***系统的原理和机制发展起来的处理各种工程问题和信息计算问题的智能系统。免***算法是基于免***系统的学习算法,它具有良好的应答性和主动性,善于学习记忆,具有较强的模式分类能力。尤其在处理多模态问题时体现出了较高的智能性和鲁棒性。下面简单介绍一般免***算法的原理。
首先,要对所求问题进行分析,找出待求解的目标函数,把它看成是生物免***系统中的抗原,把问题的优化解看成是生物系统中的抗体,问题解的正确性或匹配性用抗体和抗原的亲和力来表示。亲和力指抗原和抗体的识别程度或者两个抗体之间的相似度,一般亲和力的公式为:,其中tk为抗体与抗原的结合强度,结合强度可以有各种距离公式求得,如欧几里得距离(ED,Euclidean distance),曼哈坦距离(MD,Manhattan distance)和明考斯基(MD,Minkowski distance)等。
免***算法的流程如***4所示。免***算法的步骤如下:
1)抗原的识别,免***系统确定是否抗原入侵;
2)产生初始化抗体,同时激活记忆细胞,利用先前记忆的抗体消除先前出现过的抗原;
3)计算亲和力。计算所有抗体与入侵抗原的亲和力,选择亲和力最大的抗体,即它对入侵抗原的抵抗力最强,这是一个选择过程;
4)记忆细胞分化,把亲和力最大的抗体加给记忆细胞,以便抵御相同的抗原再次入侵;
5)抗体的促进和抑制;
6)抗体的产生,也就是问题优化解的产生。
4.3 免***算法的应用进展
免***系统是一种新型仿生智能算法,综合了分类器、神经网络和机器推理等学习系统的优点,是一种突现计算。免***算法具有全局优化、鲁棒性强、并行性高和智能度高等特点[7],主要应用于计算机网络安全、智能控制和优化计算等领域[12]。此外,免***算法在数据挖掘与分析、机器学习和异常与故障检测等方面取得了很大进展。尽管如此,目前对于免***算法的研究只是处于起步阶段,理论研究和实际应用的深度还不够,而且免***机理复杂,系统庞大,免***学家对一些免***现象也无法清楚的表述,而且免***算法可以借鉴的成果也不多,所以免***算法的研究存在着一定的困难。免***算法和神经网络算法,进化算法一样都是模拟生物智能的算法,因此免***算法的研究可以参照神经网络算法和进化算法的研究方法,借助其相关研究成果,这将是研究免***算法的一个新方向。
5 结束语
目前关于计算智能的研究和应用处于蓬勃发展时期,其应用范围遍及各个科学领域。虽然计算智能是一门新兴的综合型学科,而且各种智能方法的发展历史也不是很长,但是其发展却是相当迅猛。当前除了对单一的算法进行研究和应用之外,很多学者开始对各种算法的融合进行研究,针对各个算法的特点,有目的的进行取长补短的算法综合。典型的融合方案有:人工神经网络与模糊逻辑、人工神经网络与免***算法、人工神经网络与遗传算法、模糊逻辑与免***算法、模糊逻辑与遗传算法和遗传算法与免***算法[11]。融合之后的算法可以提高算法的性能,增强了算法的适应性,同时还克服了算法选择的盲目性。另外,还有学者提出了计算智能的新框架――生物网络结构,即神经内分泌免***网络(NEIN, neuro-endocrine-immune networks)。它由人工神经网络(ANN)、人工内分泌系统(AES)和人工免***系统(AIS)组成[8]。新框架的提出为人们研究其理论和应用技术提供了新平台。这些研究都为计算智能今后的发展指明了方向。
参考文献:
[1] 周春光,梁艳春.计算智能[M].长春:吉林大学出版社,2009:3-9.
[2] 韩力群.人工神经网络理论,设计与应用[M],北京:化学化工出版社,2007:16-18.
[3] 张仰森,黄改娟.人工智能教程[M].北京:高等教育出版社,2008:322-324.
[4] 王宏生,孟国艳.人工智能及其应用[M].北京:国防工业出版社,2009:139-141.
[5] 尹朝天.人工智能方法与应用[M].武汉:华中科技大学出版社,2007:169-175.
[6] 王磊,潘进,焦李成.免***算法[J].电子学报,2000,28(7):74-78.
[7] 高家全,何桂霞,王雨顺.典型的人工免***算法性能比较与分析[J].计算机工程与应用,2009,45(10):208-210.
[8] 丁永生.计算智能的新框架:生物网络结构[J].智能系统学报,2007,2(2):26-30.
[9] 罗熊,孙增圻.计算智能方法优化设计模糊控制系统:现状与展望[J].控制与决策,2007,22(9):961-966.
[10] 董聪,郭晓华.计算智能中若干热点问题的研究与进展[J].控制理论与应用,2000,17(5):691-698.
[11] 苏建元.智能计算主要算法的比较与融合[J].中国电子科学研究院学报,2007,2(1):52-56.
[12] 胡风新,郭红瑾,孙运芳.免***算法理论及应用研究[J].计算机与数字工程,2009,37(7):46-49.
[13] 高彬彬,杨孔雨.免***算法研究[J].计算机技术与发展,2009,19(7):249-252.
[14] 王煦法.遗传算法及其应用[J].小型微型计算机系统,1995,16(2):59-64.
[15] 席裕庚,柴天佑.遗传算法综述[J].控制理论与应用,1996,13(6):697-708.
[16] 卢奕南,张弘.遗传模糊系统的研究概述[J].仪器仪表学报2004,25(4):587-590.
转载请注明出处学文网 » 智能计算主要算法的概述