《思维进化计算的描述与研究成果综述》.docVIP

思维进化计算的描述与研究成果综述* 孙承意，周秀玲，王皖贞（北京城市学院人工智能研究所，北京100083） 摘 要：思维进化计算（Mind Evolutionary Computation, MEC）是孙承意于1998年提出的一种新的进化计算方法。它模仿人类思维中趋同、异化两种思维模式交互作用，推动思维进步的过程。MEC多方面的性能优越，这是由于采用“趋同”和“异化”操作代替GA的选择、交叉和变异算子以及MEC与GA不同的运行机制：记忆机制、定向机制和探测与开采功能之间的协调机制。本文给出MEC迄今为止最完整的描述。由于篇幅所限，本文仅简单介绍MEC的主要研究成果。 关键词：进化计算；思维进化计算；趋同；异化 1. 引 言 上个世纪六十年代，美国密歇根大学的J. Holland教授和他的学生们提出了遗传算法(Genetic Algorithms, GA)并逐渐为人们所接受[1][2]。德国柏林工业大学的I. Rechenberg和H. P. Schwefel采用生物变异的思想优化物体形状并逐渐形成进化策略 (Evolutionary Strategies, ES) [3]。以后又出现了进化规划（Evolutionary Programming, EP）、遗传编程（Genetic Programming, GP）。后来，把这一类算法统称进化计算（Evolutionary Computation, EC）或进化算法（evolutionary algorithms (EA)）。 进化计算与其它众多的算法相比，具有鲜明的特色，这就是“群体”和“进化”，它们给研究人员以广阔的想象空间。EC模拟生物的进化过程，发展了一类通用的算法。由于它的独特的原理和极强的解决问题能力，获得了许多学者的重视与研究。 EC的主要特点是：1随机性，随机优化算法可以解决非线性系统的全局最优化问题；2自适应性，自适应方法可以解决机器学习问题；3并行性，并行算法具有高的计算效率。这三个特点使得EC的研究和应用迅速成为国际学术界和工程界关注的热点。 在上个世纪的90年代，EC被关注的程度非常高。其原因是EC与众不同的特色、广阔的发展前景；也是因为EC存在的缺陷及发展余地。不断有EC的各种算法的改进算法提出，EC一直没有停止发展的脚步。 但是，EC存在的问题和缺陷也不能忽视。在早期人们就注意到早熟问题[1]，也是许多学者关注、研究的问题。另一个重要问题是EC的计算效率的问题。 针对这些问题，提出了许多改进的算法，如结构遗传算法[4]采用层次结构对染色体进行编码，并允许冗余基因存在，因而使GA具有避免早熟的能力和适应时变环境的性能；自主基因进化算法 (selfish gene algorithm) [5]强调进化的基本单位是基因而不是个体。 在生物学或生态学中，小生境(Niche)或小生态是指特定环境下的一种生活环境。借鉴此概念可以让遗传算法中的个体在一个特定的生存环境中进化，即在遗传算法中可以引进小生境的概念。发展了两类方法，它们是基于预选择（Preselection）的小生境实现方法[6]，以及据此所发展出来的基于排挤机制（crowding）的小生境实现方法[7]，基于共享机制（sharing）的小生境实现方法等[8]。小生境GA是一类重要的GA，明显改善了GA的性能。 采用多个群体，可以提高计算效率[9]，缓解早熟问题[10]。改进的GA还有很多, 如模拟退火与GAs结合 [11]，遗传算法与免疫相结合[12]等，无法一一列出。针对EC存在的问题并受到EC的新研究进展的启发，孙承意于1998年提出思维进化计算 (Mind Evolutionary Computation, MEC) [13]。 尽管人们的思维在不同的领域有不同的特点和规律，根据我们的观察，有两种思维模式普遍存在于各个领域的思维活动中，它们称之为趋同和异化。趋同指的是采用现有的、他人的思维方式或方法解决问题。但可能不是完全机械地模仿别人，其中关注的角度可能有所不同、处理的方法可能有小的变化或改进，使现有的思维方式和方法更为成熟。异化指的是摆脱常规的思维方式和方法，提出新的观点、新的思考方法、新的解决问题的途径或提出新的问题、开拓新的领域。这种与常规思维方式有明显区别的思维模式，能够对思维的进步有较大的推动。这两种不同思维模式的交互作用推动了人类的思维越来越快的前进。最近几十年，科学、经济的之所以能够得到前所未有的迅速发展的原因之一就是人类更自觉地把握趋同与异化的互动。 MEC就是模仿人的这种趋同与异化两种思维模式交互作用，推动思维进步的过程。而进化计算的其它方法，如GA，模仿的是生物的进化过程。可以期望，MEC的计算效率要高于进化计算的其它方法。 MEC是一种通过迭代不断进化的计算方法。进