1.项目背景

l演化计算的基本原理

达尔文理论在1859年是最能解释生物之为生物的理论, 而且直到现在仍然是. 达尔文的生物进化理论指出, 物种的创造者是自然. 自然用她的左手----变异, 为众多物种的形成创造了条件. 自然用她的右手----自然选择, 选择了那些有利于在生存斗争中取胜的变异的新物种, 淘汰了那些不适应环境的物种, 使物种的数量增多, 质量提高, 由低级向高级发展,且产生了人类这样有思维、有智力高级生命体. 生物界的自然演化过程实际上是生物种群相应环境的优化过程。这一优化过程是可以用计算机来进行模拟的。而且“演化”这个优化思想并不仅仅局限于生命科学的研究中, 还可以更为广泛地应用于工程领域 演化算法就是用计算机模拟大自然的演化过程,特别是生物演化过程来求解复杂问题的一类计算模型. 未来信息技术的一个必然发展趋势是智能化, 而这种智能化实现的有效途径应是向自然界智能产生过程学习. 因此演化计算变成了信息技术未来智能化的基础. 实际上,演化计算正在使以人脑的逻辑和知识为基础的传统人工智能向以自然为基础的现代人工智能转变.

l演化计算的主要模型

演化计算起源于二十世纪五六十年代. 在对模拟演化的研究中, 大致上有三种类似的方法:遗传算法(Genetic Algorithm)、演化策略(Evolution Strategies)和演化规划(Evolutionary Programming)。这三种方法都是从所求解问题的一些相互竞争的候选解开始, 通过随机地对现有的解产生改变来得到新的解, 并用性能的一个目标测度来对每个候选解进行评价,得到每个候选解的“符合度”, 然后再由某种选择机制来确定哪些解被保留下来作为后续子代的“父代”。这三种方法的不同之处首先在于对生物进化空间不同层次的模拟,其次是选择新的父代的方法各不相同。每一种方法实际上是强调了自然演化过程的一个侧面。由于遗传算法、演化规划和演化策略是不同领域的研究人员分别独立提出的,在相当长的时间里相互之间没有正式的沟通. 直到1990年,遗传算法才开始与演化规和演化策略有所交流.1992年,演化规划和演化策略这两个不同领域的研究人员首次接触到对方的研究工作,通过交流,他们发现彼此在研究中所依赖的基本思想都是基于生物界的自然遗传和自然选择等生物进化的思想,具有惊人的相似之处.于是他们提出将这类方法称为”演化计算”.1993年演化计算这一专业领域的第一份国际杂志《Evolutionary computation》在美国创刊.1994年,IEEE神经网络委员会主持召开了第一届演化计算国际会议, 以后每年举行一次.1997年,IEEE Transactions on Evolutionary computation问世.

l新一代演化模型

随着计算机计算速度与内存容量的提高,演化计算有了更好的发展平台. 1992年, J.R. Koza将遗传算法应用于计算机程序的自动生成, 提出了遗传编程(Genetic Programming)的概念,成为第一个新一代演化模型.最近几年又出现了一些来源于自然界、人类社会和生命系统新的其他新型演化算法，例如，概率建模的演化算法,蚁群系统，粒子群优化，自组织生长计算模型, 免疫算法等。概率建模的演化算法是一种在演化搜索过程中建立问题空间的优化解的概率模型且用于指导搜索过程的演化算法，主要代表有基于人口的增量学习（Baluja, 1994） 、分布估计算法（Muehlenbein & Paass 1996） 、紧遗传算法（Harik et al., 1997） 、概率增量程序演化（Rafal Salustowcz et al, 1997） 、自私的基因算法（Corno et. al, 1998）和贝叶斯优化算法（Pelikan et al, 1998）。蚁群系统是受到人们对自然界中真实的蚁群集体搜索行为的研究成果的启发而提出的一种基于蚁群搜索行为的演化算法，由意大利学者M. Dorigo等人首先提出. 粒子群优化由R.C.Eberhart和Jim Kennedy提出，他们在人口空间搜索过程中引入社会学的自适应机理。自组织生长计算模型由Richard Tateson提出，利用生命系统由单细胞成长为复杂的多系胞组织完成计算。免疫算法是人们从生物的免疫系统得到的启发而建立的计算模型,可看作带记忆的演化算法.这些算法不仅增大了演化算法的问题求解规模，而且表现了更强的鲁棒性。

l演化算法的研究领域

演化算法中,无论是经典的遗传算法、演化规划、演化策略,还是新一代演化模型本质上是一种集群搜索寻优的方法. 它用于求解传统优化方法不能求接或难以求解的困难优化问题, 而与计算机通信相关的问题, 如卫星广播调度、移动通信信道分配等时间、空间、频率资源管理、计算机网络安全管理、密码设计、网络安全协议设计问题是传统方法难以解决的,演化算法却可有效地求解.

演化计算大体上包括演化计算的理论、演化优化、演化学习和演化设计. 演化计算的理论是对演化计算机理的研究，回答演化计算为什么能或不能工作。演化优化利用演化计算的自适应并行搜索机制求解用传统的优化方法难以解决的问题，包括数值优化和组合优化, 是演化计算最活跃的研究领域. 演化学习指用一种演化搜索的办法获得一种策略或使机器产生智能, 包括合作演化、演化神经网络、复杂系统的演化建模等. 演化设计是用演化的办法实现设计目标, 包括创造性设计、演化硬件、演化软件、演化密码、演化网络安全协议.

2.研究工作

本项目研究了演化计算的模型、理论及应用。信息技术中大量问题在数学上表现为困难的优化问题.本项目从演化计算的搜索本质入手,为加快演化算法的搜索速度, 对演化规划模型引入了集群方向, 改进了概率指引的人口增量学习算法和自组织生长指引.先对数学上困难的数值优化和组合优化问题研究了演化求解方法,提出了有效的解决方案,然后对通信技术中的困难问题---卫星广播调和信道分配问题进行了研究,结合混沌和神经网络理论,同样提出了有效的解决方案.具体所做的研究工作如下：

l 演化规划收敛性分析及性能改进

最初的演化规划工作在有限自动机上, 后来开始使用浮点编码并依赖变异算子搜索空间。 最近演化规划已成功地解决了许多数值和组合优化问题。 然而, 演化规划对某些函数的搜索是相当费时的, 姚新和刘勇提出了快速演化规划。 我们在对快速演化规划分析的基础上, 借鉴粒子群思想提出了嵌入集群方向的快速演化规划, 获得了一种更加有效的演化搜索过程。嵌入集群方向的快速演化规划的特征在于对演化搜索中引入了社会认知结构。 这种方法的有效性通过求解困难函数优化和带性能约束的布局问题时得到了验证。

l 集值人口增量基因学习算法

概率建模的演化计算是一种新一代演化模型, 它通过对搜索空间建立概率模型指引搜索过程。 人口增量学习算法解的表达使用固定长度的二元字符串, 每个基因位只能取一个品质值。 这是对自然演化系统的过强简化。我们在对人口增量学习算法分析的基础上, 通过对其概率选择引入轮盘赌方法 提出了集值人口增量学习算法。 集值人口增量学习算法反映了生物的基因多效性。 进一步又对概率分布引入熵概念获得了系统可演化性的简单判别方法。 接着应用该方法简单而有效地解决了并行多机调度问题、对称和反对称旅行商问题, 最后与蚁群算法作了比较。

l 自组织鲁棒生长计算模型

自组织生长计算同样是演化计算发展的新方向, 它在基型到表型的映射不是直接译码, 而是有一个生长过程。 我们通过对果蝇刚毛自组织生长机理的分析, 用随机竞争选择排序替换了其中的确定性选择排序方法, 得到了一种自组织鲁棒生长模型。 接着用这种方法自然而简单地求解了卫星广播调度问题。 卫星广播调度问题是一种寻找无冲突的约束满意问题。 移动通信信道分配是一种寻找最小冲突的约束满意问题。 最后用自组织鲁棒生长和暂态混沌神经网络结合求解了移动通信信道分配问题。 自组织鲁棒生长用于限制搜索空间并给出初步解, 暂态混沌神经网络用于寻找最小冲突。

3.应用范围

本项目演化计算的应用范围是信息技术中数学上困难的优化问题(NPC或NPH问题). 这些问题可表现为连续或离散、单目标或多目标、静态或动态、有无约束等属性, 而传统的优化方法对这些问题往往难以求解. 因此, 研究这类问题的演化求解, 其中前面4 个已完成,后面4个正在进行中.

l 布局问题

l 并行多机调度问题

l 移动通信信道分配

l 卫星广播调度

l 计算机网络安全管理

l 移动IP

l 演化密码

l 演化网络安全协议

4.技术水平

本演化计算研究课题曾得到国家自然科学基金重点项目: 混沌神经网络模型及智能信息处理理论与实现技术(已结题), 演化计算的理论、方法及应用(正在进行)的资助.获2002年度江苏省科技进步一等奖一项. 近五年发表论文30余篇. 论文被收录和引用30篇次，其中SCI、EI、ISTP收录20篇次，SCI引用3篇次，国内核心期刊等引用9篇次. 另外,有的论文被作为1998世界计算智能大会的特邀论文,有的论文获得2000年IEEE亚太地区国际电路和系统学术大会的最佳论文. 两次应邀去美国在国际学术大会上作报告. 演化计算研究已获得的成果正应用于863项目“公共无线局域网络(PWLAN)安全体系及其应用研究（2002AA143010）”.