计算智能算法的研究现状

计算智能算法的研究现状1引言计算智能是什么？它是建立在神经计算、模糊计算、进化计算三大智能算法分支发展相对成熟的基础上，通过不同算法之间的有机融合而形成的新的科学算法，是智能理论和技术发展的崭新阶段。高效的优化性能、无需问题特殊信息等优点使得智能优化算法广泛应用于工程优化、模式识别、智能控制、网络智能自动化等领域。随着计算机的飞速发展，一系列新的计算方法，如神经网络、模拟退火、遗传算法、演化算法和禁忌搜索算法等应运而生。它们能较好的解决大规模复杂系统中出现的组合爆炸问题，不仅具有通用、稳健、简单、便于并行处理等优点，而且有望成为将数值计算与语义表达、形象思维等高级智能行为联系的桥梁。因而，它们被认为是对21世纪的计算技术有重大影响的关键技术。2几种算法的特点各种智能计算方法有一些共同的特点：（1）它们大都引人了随机因素,因此具有不确定性。不少计算过程实际上是在计算机上作随机过程的模拟。（2）它们大都具有自适应机制的动力体系或随机动力体系，有时在计算过程中体系结构还在不断调整。（3）这些算法都是针对通用的一般目标而设计的,它们不同于针对特殊问题而设计的算法。（4）其中不少算法在低维或简单的情况下显得很笨,但是到了高维复杂情形具有很强的竞争力。各种智能计算方法大都是20世纪60年代末开始流行起来的，如人工神经网络、遗传算法、模拟退火算法和禁忌搜索算法等。开始时是人们从自然过程和生物的生存竞争与遗传变异等过程的模仿和简化而来的。各种智能计算方法强调数值计算；又往往不是通过公理和公式来描述,而是以数据及其分布来描述对象。模拟退火算法（SA）包括三函数两准则,即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则,这些环节的设计将决定SA算法的优化性能。此外,初温的选择对SA算法性能也有很大的影响。特点如下：(l)理论上,SA算法的参数只有满足算法的收敛条件,才能保证实现的算法以概率l收敛到全局最优解。然而,由SA算法的收敛条件理论知,某些收敛条件无法严格实现,如时齐马氏链的内循环终止准则,即使某些收敛条件可以实现,如非时齐马氏链的更新函数,但也常常会因为实际应用的效果不理想而不被采用。因此,至今SA算法的参数选择依然是一个难题,通常只能依据一定的启发式准则或大量的实验加以选取。(2)SA算法的状态产生和接受操作每一时刻仅保留一个解,缺乏冗余和历史搜索信息,并行性较差。禁忌搜索算法的主要特点如下:(l)在搜索过程中可以接受劣解,因此具有较强的“爬山”能力;（2）新解不是在当前解的邻域中随机产生,而或是优于“bsetsofor”的解,或是非禁忌的最佳解,因此选取优良解的概率远远大于其他解;(3)由于TS算法具有灵活的记忆功能和藐视准则,并且在搜索过程中可以接受劣解,所以具有较强的“爬山”能力,搜索时能够跳出局部最优解,转向解空间的其他区域,从而增强获得更好的全局最优解的概率,所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。遗传算法的特点如下:(l)遗传算法是以决策变量的编码作为运算对象。在优化过程中借鉴生物学中染色体和基因等概念,模拟自然界中生物的遗传和进化等机理,应用遗传操作,求解无数值概念或很难有数值概念的优化问题;(2)遗传算法直接以目标函数作为搜索信息。它仅使用由目标函数变换来的适应度函数值就可确定进一步搜索的方向和范围,而不需要目标函数的导数值等信息;(3)遗传算法同时在多点进行信息搜索,具有天生的并行性,由多个个体组成一个初始群体开始搜索,对群体进行选择、交叉、变异等运算,产生出新一代的群体,继续搜索;(4)遗传算法使用概率搜索技术.它属于一种自适应概率搜索技术,其选择、交叉、变异等运算都是以一定的概率进行的,增加了其搜索过程的灵活性。实践和理论证明了在一定条件下传算法总是以概率1收敛于问题的最优解。神经网络特点：由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大,使得它具有很强的不确定性信息处理能力。即使输人信息不完全、不准确或模糊不清,神经网络仍然能够联想思维存在于记忆中的事物的完整图像。只要输人的模式接近于训练样本,系统就能给出正确的推理结论。正是因为人工神经网络的结构特点和其信息存储的分布式特点,使得它相对于其它的判断识别系统,如:专家统等,具有另一个显著的优点:健壮性。生物神经网络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是,当一个人的大脑因意外事故受轻微损伤之后,并不会失去原有事物的全部记忆。人工神经网络也有类似的情况。因某些原因,无论是网络的硬件实现还是软件实现中的某个或某些神经元失效,整个网络仍然能继续工作。人工神经网络是一种非线性的处理单元。只有当神经元对所有的输人信号的综合处理结果超过某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模连续时间动力学系统。3几种智能算法的概念与研究现状3.1模拟退火算法（SA）模拟退火算法是一种高效的全局优化方法,其基本思想来源于固体的退火过程，1982年kirkpatrick等将退火过程引入组合优化领域而提出该算法,并在大规模组合优化问题中得到了成功的应用。模拟退火算法将优化问题比拟成一个物理系统,将优化问题的目标函数比拟为物理系统的能量,通过模拟物理系统逐步降温以达到最低能量状态的退火过程而获得优化问题的全局最优解。模拟退火算法的数学模型可以描述为在给定邻域结构后,模拟退火过程是从一个状态到另一个状态不断的随机游动过程。3.2禁忌搜索算法(TS)禁忌搜索算法是一种高效的全局优化算法,是对人类智力过程的一种模拟,近年来已成功应用于各个领域。禁忌搜索算法的形式灵活多变,在函数优化问题中,不需要目标函数的梯度向量,所有的参数都是用实数进行编码,使程序更直观、清晰,同时也避免了编解码带来的延时;作为一种全局优化方法,仆具有较强的爬山能力,能根据其独有的记忆机制引导搜索程序跳出局部最优解,从而向全局最优靠近。所谓禁忌就是禁止重复前面达到局部最优的状态。飞中,邻域函数沿用局部邻域搜索的思想,用于实现邻域搜索;禁忌表和禁忌对象的设置,体现了算法避免迂回搜索的特点;特赦准则,则是对优良状态的奖励,它是对禁忌策略的一种放松。禁忌搜索算法在邻域构造、禁忌对象和特赦准则等的选择上具有很大的灵活性,这给我问题带来了方便。但是由于其理论研究还不完善,与遗传算法相比禁忌搜索算法还没有一个完型,其中参数选择(如禁忌长度,邻域大小等)在很大程度上还依靠经验来选择。目前,禁忌搜索算法的研究主要集中在两个方面:第一是其理论研究;另一方面就是其应用的研究。禁忌搜索思想最早由Glover(1986年)提出的,，它是模拟人的思维的一种只能搜索算法。即人们对己搜索的地方不会立即去搜索,而去对其它地方进行搜索。若没能找到可再搜索已去的地方，禁忌搜索算法从一个初始可能解出发,选择一系列的特定搜索方向（移动）作为试探，选择实现使目标函数值，减少最多的移动。为了避免陷入局部最优解，禁忌搜索中采用了一种灵活“记忆”技术，,即对己经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是tabu表的建立。tabu表中保存了最近若干次迭代过程中所实现的移动，凡是处于tabu表中的移动，,在当前迭代过程中是不允许实现的。,这样可以避免算法重新访问在最近若干次迭代过程中已经访问的解群，从而防止了循环，帮助算法摆脱局部最优解。另外，,为了尽可能不错过产生最优解的“移动”,,禁忌搜索还采用“释放准则”的策略。禁忌搜索算法应用领域非常广泛,目前主要应用领域包括:车辆路径问题(VRP);作业调度;大学排课问题；旅行商问题(TsP)；背包问题。此外,禁忌搜索算法还渗透到电力系统、检测系统、通讯路由、航天、航海,交通,化工,水资源利用等领域。可见,该算法的研究是非常有价值的。3.3遗传算法（GA）遗传算法是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法【1】。遗传算法是全局优化自适应概率搜索算法，是模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，其解的质量越好。而适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。遗传算法所使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大。选择操作就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。基本遗传算法（SGA）中采用的选择算子是轮盘赌选择方法。遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须有保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率[2]。3.4神经网络算法（BP）1943年,Meeulloeh和Pitts利用神经元的脑科学研究结果提出了“M一P神经元”模型和“M一P神经网络”模型。这是已知最早的神经元抽象模型,它能实现一些简单的逻辑功能,但它并不是一个真实神经细胞的生理学模型,而只是一个神经细胞中逻辑处理功能的简单表示。当兴奋型输入的总和等于或大于神经元的门限值,而且又无抑制型输入存在,则该神经元将激活布尔逻辑函数可以很容易地由此模型来实现。另一种M一P模型的变形模型—线性加权M一P模型得到更为广泛的应用此模型与基本M一P模型的重要不同之处在于:抑制型输入具有“-1”的数值干是当兴奋型输入的总和与抑制型输入的总和之差等于或大于神经元的阂值时,该神经元将激活。50年代末至60年代初,神经网络系统已开始作为人工智能的一条途径得到研究1958年,Rosenblatt提出了著名的Pereeptron模型,它是根据对人脑及神经细胞的初步观察及研究而提出的。人脑中各神经元之间的广泛连续表现出一种无规律性,也可以说这种连续具有随机性,各神经元之间的连续强度(权重)可以通过学习加以改变。另一种Perceptron的变化形式即连续取值的线性网络Adaline是Widrow和Hoff于1960年提出的,它主要用于连续可调过程的控制1969年,Mlnsky和Parpert以Pereeptron为代表,对简单神经网络的功能和局限性从数学上作了深入分析,出版了影响很大的PercotPron一书他们指出简单神经网络只能求解一阶谓词问题,而不能解决高阶谓词问题。与高阶谓词问题相应的,应该是具有隐层的多层神经网络,而这种复杂网络又难以找到一种有效的学习算法。从此,神经网络的研究进入了低潮。1979年,日本的福岛邦彦提出了Cognltorn模型,随后又提出了改进型Neocogintorn模型。他采用的突触修正规则是“择优修正法”基本思想是:当某一神经元N兴奋时,在与其相连的各神经元中.找出兴奋性最大的那个神经元N,给它们的突触连接强度以一个正的修正增量。与此同时,另一位日本学者中野馨,提出了有名的联想记忆模型Assoicotron。80年代末期,神经网络的研究又出现了新的热潮。在这个时期,首推Hopfield的突破性工作。1982年他提出了HoPifedl网络模型,并在权值对称情况下引入了Lyapunov函数。Hopfield网络是由非线性映射关系为Sigmiod型函数的神经元相互连结组成的网络。它有离散和连续两种模型。但已证明,Hopifeld在这里错误地把一非正定的函数当作Lyapunov函数,以为网络的稳定性问题已解决,其实远非如此。网络的稳定性问题虽经Miehel(1989)、Li(1988)的研究有了一些进展,但至今未得到彻底解决。总之在神经网络研究方面,主要是在神经元模型本身结构、逼近非线性函数和学习算法等方面还需要做大量的工作:在逼近非线性函数问题上,现有的理论只解决了存在性问