思维进化计算的描述与研究成果综述*孙承意 ，周秀玲，王皖贞（北京城市学院人工智能研究所，北京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的计算效率要高于进化计算的其它方法。2. MEC算法描述MEC是一种通过迭代不断进化的计算方法。进化的每一代中所有个体的集合称为一个群体。一个群体分为若干个子群体。公告板(billboard)为个体之间和子群体之间交流信息提供了机会。子群体内的个体在局部公告板(local billboard)张贴各自的信息。全局公告板(global billboard)用于张贴各子群体信息。在局部范围内，从一个初始中心开始，子群体的个体为成为胜者而竞争的过程叫做趋同运算。一个子群体在趋同过程中，若不再产生新的胜者，则称该子群体已经成熟。当子群体成熟时，该子群体的趋同过程结束。子群体从诞生到成熟的期间叫做生命期。该操作进行局部信息的开采。在整个解空间内，个体或子群体为成为全局的胜者而竞争的过程叫做异化。该操作有两个方面的功能：异化操作I（简称：异化I），在全局散布的个体中，选择最好的一些个体作为新子群体的初始中心；异化操作II（简称：异化II），在成熟子群体得到的局部最优解中选择最好的作为当前的全局最优解。显然，这个操作进行信息的全局勘探。在MEC中，趋同和异化操作是交替工作的：异化操作I通过全局竞争，为子群体选择较好的初始解作为子群体的初始中心；每个子群体从初始中心开始，通过趋同操作找到一个局部最优解；异化操作II从趋同操作得到的最优解中选择最好的解作为全局最优解。这个交替作用就是MEC的基本原理，也是MEC具有高计算效率，并且具有好的收敛性能的原因。在MEC中，没有单独的选择操作，但是在进化操作趋同和异化中都包含有选择，这与GA是不同的。在早期MEC叫做基于思维进化的机器学习（Mind-Evolution-Based Machine Learning, MEBML）。后来接受国内外一些学者的建议，改为现在的名称，其内容完全没有变化。用伪码表示的基本的、全串行的用于数值优化的MEC算法模型如下：算法描述中使用的符号 ：第 个子群体的尺寸； ：算法中同时存在的子群体个数； ：异化操作I中的选择比例； ：被释放的子群体的个数，或叫做待创建的子群体数； ：被释放的个体数; ：第 个子群体迭代的代数; ：第 个子群体在第 代的中心。/* Procedure of MEC */1. ，全局公告板初始化2. while( 不满足终止条件 )3. if( )4. 在整个解空间均匀散布 个个体5. 计算这些个体的得分6. 选择最好的 个个体，分别作为 个子群体的初始中心 ， ， ， 7. end if8. 9. for每一个子群体的中心 10. 在 的周围，按某个分布函数散布 个个体11. 计算这些个体的得分12. 从这 个个体中选择最好个体作为子群体新的中心 13. end for14. for每个子群体 15. if(子群体 已成熟 ) 16. if(子群体 的得分优于全局公告板的一个解)17. 该子群体得到的局部最优解替代全局公告板中较差的解18. end if19. 释放该子群体的全部个体， ， ，记录被释放的子群体序号20. end if21. end for22. end while趋同操作的停止准则：某子群体的得分在连续的若干代内没有增长，我们就认为该子群体成熟，趋同操作停止。MEC的停止准则：若连续若干个成熟子群体得到的解不优于全局公告板所记录的所有的解，MEC停止。趋同操作是局部搜索，包括步骤9－13。异化操作定义为全局搜索，它包含两个功能：异化I由算法中步骤3－7实现；异化II由步骤14－21步实现。下面给出MEC形式化描述，其中IR ：实数空间； IN ：整数空间。MEC= IR目标函数 IN 算法同时存在的子群体数。 IN 被释放的子群体数。(见：说明1) IN 异化操作I选择比例（实数/整数） IR n ， 子群体的初始中心 异化操作I。(见：说明2)

MEC在许多方面获得了成功的应用。把MEC与MLCNN（最大似然聚类神经网络）结合构成混合系统，该混合系统具有优良的聚类性能，对带有强噪声的彩色图象进行聚类[45]，进行目标形状的匹配[46]和彩色图象的分割[47][48]。提出基于模型选择的经济预测系统，采用MEC动态选择最佳预测模型[49][50]，在这些应用中MEC起关键作用。7. 总结思维进化计算（MEC）是孙承意于1998年提出的一种新的进化计算方法，MEC模仿人类思维中趋同、异化两种思维模式交互作用，推动思维进步的过程。由于MEC采用“趋同”和“异化”操作代替GA的交叉和变异算子，以及MEC具有与GA不同的运行机制、记忆机制、定向机制和探测与开采功能之间的协调机制，MEC优化性能优越。本文给出MEC迄今为止最完整的描述，然后简要综述了MEC提出以来（1998-2003年）有关MEC完成的主要研究工作，其中包括：MEC计算效率与收敛率的研究、趋同和异化策略的开发、求解非数值优化问题的MEC的方法研究、MEC的收敛性研究以及MEC的部分应用。参考文献：[1] Bagley J D. The behavior of adaptive systems which employ genetic and correlation algorithms, Dissertation Abstracts International, 28(12), 1968. [2] Holland J H. 1975, Adaptation in Nature and Artificial System, Ann Arbor:Univ. of Michigan Press, 1975[3] Schwefel H P. Numerical Optimization of Computer Models. Chichester:John Wiley, 1981.[4] Dasgupta D and McGregor D R. A More Biologically Motivated Genetic Algorithm: the Model and Some Results, Cybernetics and Systems: An International Journal 25:pp.447-469, 1994.[5] Corno F M, Reorda S and Squillero G. 1998, A new Evolutionary Algorithm Inspired by the Selfish Gene Theory, ICEC'98: IEEE Inter. Conf. on Evolutionary Computation, May 1998.[6] Cavicchio D J. Adaptive search using simulated evolution. Ph. D. Dissertation, University of Michigan, 1970. [7] De Jong K A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Dissertation Abstracts International, 36(10), 1975.[8] Goldberg D E and Richardson J, Genetic algorithms with sharing for multimodal function optimization, Proc. 2nd Inter. Conf. on Genetic Algorithms, pp.41-49, 1987. [9] Sun Z and Wan Q. A Modified Genetic Algorithm: Meta-Leval Control of Migration in a Distributed GA, Proc. of IEEE Inter. Conf. on Evolutionary Computation, pp.312-316, 1995.[10] Tsutsui S, Ghosh A, Corne D and Fujimoto Y. A Real Coded Genetic Algorithm with an Explorer and an Exploiter Populations, Proc. of The Seventh International Conference on Genetic Algorithms, 238-245, 1997. [11] Jiangshe Zhang, Zunben Xu, Yi Liang[1997], "the whole annealing selection of GA and its necessary and sufficient condition of corresponding algorithm converge efficiency", Science in China ( Series E), vol. 27, No. 2 (1997), pp. 154-164.[12] Licheng Jiao, Lei Wang: A novel genetic algorithm based on immunity. IEEE Transactions on Systems, Man, and Cybernetics, Part A 30(5): pp.552-561 (2000).[13] Sun Chengyi, Sun Yan and Lijun Wei, Mind-Evolution-Based Machine Learning: Framework and The Implementation of Optimization, Proc. of IEEE Int. Conf. on Intelligent Engineering Systems (INES'98), pp.355-359, Sept. 1998. [14] Sun Chengyi, Sun Yan and Xie Keming, Mind-evolution-based machine learning: an efficient approach of evolution computation, Proc. 3rd World Congress on Intelligent Control and Automation (WCICA2000), pp.118-121. June 2000.

[33] R. Battiti and M. Protasi, “Reactive Local Search for the Maximum Clique Problem”, Technical Report, TR-95-025, ICSI, Berkeley, 1995.[34] E. Marchiori,“Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem”, EvoWorkshops 2002:pp.112-121.[35] E. Marchiori, “A Simple Heuristic Based Genetic Algorithm for the Maximum Clique Problem”, Proceedings of the ACM Symposium on Applied Computing 1998, pp.366-373.[36] Sun Chengyi, Zhang Jianqing and Wang Junli, The analysis of searching efficiency of similartaxis，Joint 9th IFAS World Congress and 20th NAFIPS International Conference, pp.35-40, July 25-28, 2001, Canada.[37] Sun Chengyi, Zhang Jianqing and Wang Junli, The influence of the probability density function on similartaxis in MEC, Proc. of 10th IEEE Int. Conf. on Fuzzy System, December 2-5, 2001, the University of Melbourne, Australia. [38] 孙承意，张建卿，王俊丽，求解数值最优化问题的MEC收敛性能分析，《智能计算机研究进展》863计划智能计算机主题学术会议论文集，pp.491-500，2001年3月8-9日，清华大学出版社，北京。[39] Chuan-long Wang and Cheng-yi Sun, A study of convergence of mind-evolution-based machine learning (in Chinese), Journal of Computer Research & Development, 37(7):pp. 838-842,July 2000.[40] Chuan-long Wang and Ke-ming Xie, Convergence of a new evolutionary computation algorithm in continuous state space. International Journal of Computer Mathematics, Vol. 79(1): pp.27-37, 2002.[41] Xiuling Zhou and Chengyi Sun. Convergence of MEC in bounded and continuous search space, to appear in proceedings of 2004 IEEE International Conference on Systems, Man and Cybernetics, IEEE SMC2004.[42] Sun Chengyi, Sun Yan and Xie Keming, Mind-evolution-based machine learning and applications, Proc. 3rd World Congress on Intelligent Control and Automation (WCICA2000), pp. 112-117, June 28-July 2, 2000, Hefei, P. R. China. [43] 孙承意, 王皖贞, 贾鸿雁, 思维进化计算的产生与进展, 2001年中国智能自动化会议(CIAC2001)，pp. 80-86, 2001年8月13-16，昆明。[44] Chengyi Sun, Ru Wang and Junli Wang, A New Evolutionary Algorithm Simulating Human Mind Progress, in Proc. of Asia Simulation Conference/5th Int. Conf. on System, Simulation and Science Computation, pp. 248-256, Shanghai, China, Nov. 3-6, 2002.[45] Sun Yan, Sun Yu and Sun Chengyi, Clustering and Reconstruction of Color images Using MEBML, Proc. of Inter. Conf. on Neural Nertworks & Brain (ICNN&B'98), pp.361-365, Oct. 1998. [46] Sun Chengyi, Sun Yan, Wang Jianzheng and Xie Keming, Shape Matching of Small Objects Using MEBML, Proc.of 1999 IEEE Int. Conf. on Intelligent Engineering Systems (INES'99), pp.99-104, Nov. 1999.[47] Sun Yan, Sun Chengyi and Wang Wanzhen, Color Images Segmentation by Using New Definition for Connected Components, Proc. of 5th Int. Conf. On Signal Processing (ICSP2000), pp.863-868, 2000. [48] Sun Chengyi, Sun Yan, and Guo Xiaohong, Perceptually Uniform Color Models for Tasks in Computer Vision, Journal of Image and Graphics, 5(Supplement):pp.74-78, 2000.[49] Sun Chengyi, Sun Yan and Sun Yu, Model-Selection-Based Economic Prediction System using MEBML, Proc. of 1999 IEEE Int. Conf. on Systems, Man, and Cybernetics, (SMC'99), Oct. 1999.[50] Sun Chengyi, Sun Yan and Sun Yu, Economic Prediction System Using Double Models, 2000 IEEE Inter. Conf. on Systems, Man, and Cybernetics (SMC2000)，2000. Mind Evolutionary Computation and ApplicationsSUN Chengyi, ZHOU Xiuling, WANG Wanzhen（Beijing City University, Artificial Intelligence Institute, Beijing 100083, China) Abstract: Mind Evolutionary Computation (MEC) is a new approach of Evolutionary Computation (EC) proposed by Chengyi Sun in 1998. MEC simulates the process of mind-progress which is made by the interaction between similartaxis and dissimilation. MEC has excellent performances on various aspects because operations of similartaxis and dissimilation are employed in MEC rather than crossover and mutation operators in GAs. The excellent performances are accomplished also due to three mechanisms of MEC, which are evolutionary directionality mechanism, memory mechanism and harmony mechanism between exploitation and exploration. A complete description of MEC is given in this paper. Then the achievement on study of MEC is summarized simply because of the paper length limit. Key words: evolutionary computation; mind evolutionary computation; similartaxis; dissimilation