第2卷第5期 智能系统学报 Vol.2 Na 5 2007年10月 CAAI Transactions on Intelligent Systems 0ct.2007 基于群体智能框架理念的遗传算法总体模式描述 康琦，汪镭，刘小莉，吴启迪 (同济大学电子与信息工程学院，上海200092) 摘要：在各类群体智能算法中，不同的智能体群往往具有不同的外在表现形式，但他们所表现出来的智能计算模 式具有相对的统一性.为了验证这一理念并从宏观的视角来研究群体智能理论，对群体智能中各类智能计算模式进 行总结提炼，提出了群体智能计算的一种内在统一的总体框架模型，并以遗传算法为例加以具体论述与验证，给出 了基于群体智能框架理念的遗传算法总体模式描述 关键词：群体智能；框架描述；总体模式；遗传算法 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)050042-06 General mode description genetic algorithms based on a frame work of swarm intelligence KANG Qi,WANGLei,LIU Xiao-li,WU Qi-di (College of Electronics and Information Engineering,Tongji University,Shanghai 200092,China) Abstract:Different computational modes of agents take on relatively uniform characteristics in different kinds of swarm intelligence algorithms,though they usually have different extrinsic forms.To verify this idea and make further systematic study of swarm intelligence from a more macroscopic angle,various kinds of intelligent computational modes in the field of swarm intelligence were identified and are summarized in this paper.Based on this work,a uniform framework describing swarm intelligence is proposed,dis- cussed,and then shown to be valid using a genetic algorithm.Finally,a general description of genetic al- gorithms is presented based on the idea of a framework of swarm intelligence. Key words:swarm intelligence;framework description;general mode;genetic algorithm 在人工智能研究领域随着对各类智能计算模 种模拟自然界遗传机制和生物进化的并行随机优化 式研究的深入进行，群体智能这个主题理念及相关 方法，也可以看作群体智能的一种典型实现模式.本 研究领域开始引起了人们的注意.群体智能是一 文首先提出一种群体智能内在的统一框架模型，然 种在自然界生物群体所表现出的智能现象启发下提 后在此基础上，针对遗传算法给出其群体智能框架 出的人工智能模式，是对简单生物群体的智能涌现 模式，并给出遗传算法的形式化模型。 现象的具体模式研究2引.该种智能模式需要以相 当数目的智能个体来实现对某类问题的求解功能. 1 群体智能的统一框架理念 群体智能自提出以来，由于其在解决复杂的组合优 一般而言，群体智能以自然界中生物系统行为 化类问题方面所具有的优越性能，在诸如优化问题 为参照基础，研究其中所蕴含的丰富的信息处理机 求解、机器人领域、电力系统领域、网络及通讯领域、 制，在所需求解问题特征的相关目标导引下，提取相 计算机领域、半导体制造领域和工程设计领域等取 应的计算模型，设计相应的智能算法，通过相关的信 得了较为成功的应用4.遗传算法是由美国 息感知积累、知识方法提升、任务调度实施、定点信 Michigan大学的John Holland教授首先提出的一 息交换等模块的协同工作，得到智能化的信息处理 收稿日期：200612-05. 效果，并在各相关领域加以应用 基金项目：国家重点基础研究发展计划资助项目(2002CB312202);因 在群体智能中，信息处理模式均是模拟自然界 家自然科学基金资助项目(70531020,50408034)：国家发 改委CNGI计划资助项目(CNG041子5A-2) 相关生物组织和生物系统智能特征的.这是进化计 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
第 2 卷第 5 期 智 能 系 统 学 报 Vol. 2 №. 5 2007 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2007 基于群体智能框架理念的遗传算法总体模式描述 康 琦 ,汪 镭 ,刘小莉 ,吴启迪 (同济大学 电子与信息工程学院 ,上海 200092) 摘 要 :在各类群体智能算法中 ,不同的智能体群往往具有不同的外在表现形式 ,但他们所表现出来的智能计算模 式具有相对的统一性. 为了验证这一理念并从宏观的视角来研究群体智能理论 ,对群体智能中各类智能计算模式进 行总结提炼 ,提出了群体智能计算的一种内在统一的总体框架模型 ,并以遗传算法为例加以具体论述与验证 ,给出 了基于群体智能框架理念的遗传算法总体模式描述. 关键词 :群体智能 ;框架描述 ;总体模式 ;遗传算法 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0520042206 General mode description genetic algorithms based on a framework of swarm intelligence KAN G Qi ,WAN G Lei , L IU Xiao2li , WU Qi2di (College of Electronics and Information Engineering , Tongji University , Shanghai 200092 , China) Abstract :Different comp utational modes of agents take on relatively uniform characteristics in different kinds of swarm intelligence algorit hms , though t hey usually have different extrinsic forms. To verify this idea and make f urt her systematic st udy of swarm intelligence from a more macroscopic angle , various kinds of intelligent comp utational modes in t he field of swarm intelligence were identified and are summarized in t his paper. Based on t his work , a uniform framework describing swarm intelligence is proposed , dis2 cussed , and t hen shown to be valid using a genetic algorit hm. Finally , a general description of genetic al2 gorithms is p resented based on t he idea of a framework of swarm intelligence . Keywords :swarm intelligence ; framework description ; general mode ; genetic algorit hm 收稿日期 :2006212205. 基金项目 :国家重点基础研究发展计划资助项目(2002CB312202) ;国 家自然科学基金资助项目 (70531020 ,50408034) ;国家发 改委 CN GI 计划资助项目(CN GI20421525A22) . 在人工智能研究领域 ,随着对各类智能计算模 式研究的深入进行 ,群体智能这个主题理念及相关 研究领域开始引起了人们的注意[1 ] . 群体智能是一 种在自然界生物群体所表现出的智能现象启发下提 出的人工智能模式 ,是对简单生物群体的智能涌现 现象的具体模式研究[ 2 - 3 ] . 该种智能模式需要以相 当数目的智能个体来实现对某类问题的求解功能. 群体智能自提出以来 ,由于其在解决复杂的组合优 化类问题方面所具有的优越性能 ,在诸如优化问题 求解、机器人领域、电力系统领域、网络及通讯领域、 计算机领域、半导体制造领域和工程设计领域等取 得了较 为 成 功 的 应 用[4 - 5 ] . 遗 传 算 法 是 由 美 国 Michigan 大学的 John Holland 教授首先提出的一 种模拟自然界遗传机制和生物进化的并行随机优化 方法 ,也可以看作群体智能的一种典型实现模式. 本 文首先提出一种群体智能内在的统一框架模型 ,然 后在此基础上 ,针对遗传算法给出其群体智能框架 模式 ,并给出遗传算法的形式化模型. 1 群体智能的统一框架理念 一般而言 ,群体智能以自然界中生物系统行为 为参照基础 ,研究其中所蕴含的丰富的信息处理机 制 ,在所需求解问题特征的相关目标导引下 ,提取相 应的计算模型 ,设计相应的智能算法 ,通过相关的信 息感知积累、知识方法提升、任务调度实施、定点信 息交换等模块的协同工作 ,得到智能化的信息处理 效果 ,并在各相关领域加以应用. 在群体智能中 ,信息处理模式均是模拟自然界 相关生物组织和生物系统智能特征的. 这是进化计 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第5期 康琦，等：基于群体智能框架理念的遗传算法总体模式描述 。43· 算最本质的特征.例如遗传算法主要模拟了自然界 本质，也有利于各种算法之间进行合理融合，发展出 中生物体普遍存在的遗传进化过程：人工神经网络 各种混合算法，提高相关算法的性能 主要模拟了人脑的生理结构和信息处理模式，是对 群体智能的各种算法及模型，在具体的计算动 人脑的简化和抽象，蚁群算法和微粒群算法则模拟 态过程中，均具有一定的分布式自主寻优特征，但是 了自然界中群居性生物在种群中的信息处理模式和 这一切都是在客观统一的总体模式框架约束下进行 表现出来的群体智能行为模式.一般认为，可以在群 的.群体智能统一框架可看作是一个分层的模式，统 体智能理念的基础上，建立一个群体智能内在的统 一框架针对具体的问题可以分成4个层次，分别为 一框架来描述其中的各计算模型.通过对统一框架 宏观设计及方法提升层、任务分解协调层、计算调度 的研究，有利于理解群体智能各种智能模型的内在 及信息感知层、被控实体运动过程层，如图1所示. 宏观知识模型 模型已有的 模型读 知识方法 用户及模型选择 宏观知识评估 取指令 宏观设计及 知识库方法库 设计过程 方法提升层 模型宏观 宏观知识预测优化 信息知识 摸型提升的 和方法 识方法 型 左观知识学习进化 模型提取指令 相应参数设计模型 目标指令决议 模型及总体参数 任务宏观描述 决策分 】宏观指令 任务分解 协调层 模块 任务分解描述 分解指令 任务分配协调 局部任务 指令及参数 局部任务指令及参数L山 二二二二二二 系统化存 知 实时任务规划 信息配置 知识系统化 实际导写 日标 调 实时运动规划 信息接收 知识积累提升 息感 计算调度及 信息感知层误 信息检验 具体知识提取建模 积 实时运动控制 模 1 实时运园 控制指令 信息转换 信号处理优化 实时指令驱动 实时运 量控 信息发送 信号知识转换 信 信号定点感知 信息交换模块(1)》 卖时参数制悟号（二 被控实体 运动过程层 被控运动过程 原始对象信总 被控实体对象 传感器系统 原始环境信息」 问题求解环境 求解内容方法约束对象实体环境 图1群体智能总体框架模型 Fig 1 General framework mode of swarm intelligence 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. hp:/小pi.cnki.e
算最本质的特征. 例如遗传算法主要模拟了自然界 中生物体普遍存在的遗传进化过程 ;人工神经网络 主要模拟了人脑的生理结构和信息处理模式 ,是对 人脑的简化和抽象 ;蚁群算法和微粒群算法则模拟 了自然界中群居性生物在种群中的信息处理模式和 表现出来的群体智能行为模式. 一般认为 ,可以在群 体智能理念的基础上 ,建立一个群体智能内在的统 一框架来描述其中的各计算模型. 通过对统一框架 的研究 ,有利于理解群体智能各种智能模型的内在 本质 ,也有利于各种算法之间进行合理融合 ,发展出 各种混合算法 ,提高相关算法的性能. 群体智能的各种算法及模型 ,在具体的计算动 态过程中 ,均具有一定的分布式自主寻优特征 ,但是 这一切都是在客观统一的总体模式框架约束下进行 的. 群体智能统一框架可看作是一个分层的模式 ,统 一框架针对具体的问题可以分成 4 个层次 ,分别为 宏观设计及方法提升层、任务分解协调层、计算调度 及信息感知层、被控实体运动过程层 ,如图 1 所示. 图 1 群体智能总体框架模型 Fig11 General framework mode of swarm intelligence 第 5 期 康 琦 ,等 :基于群体智能框架理念的遗传算法总体模式描述 ·43 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·44 智能系统学报 第2卷 在宏观设计及方法提升层中，包括用户过程设 信息，并传送给上层信息感知积累模块 计模块、知识方法提升模块及相关知识库和方法库 总之，在上述的总体群体智能模型框架中，决策 知识方法提升模块经常性地从知识库和方法库中提 分配模块、知识方法提升模块以及各智能体的调度 取智能算法模型库中已有的知识和方法，通过知识 实施、信息交换、信息感知等模块之间具有一定的独 方法提升模块进行提升，上升为体系结构，并把经过 立性.在设计和任务分配工作完成之后，智能体群的 提升的知识方法存放到知识方法库中，以备宏观设 运动基本上可以在一定的计算环境下分布式地独立 计和决策分配模块调用.用户过程设计模块则针对 进行，这同时体现了群体智能理念中所包含的分布 实际所需解决的问题，向知识方法库发出模型提取 式人工智能的本质特征.当然，这里也可以看出，群 指令，并在现有的群体智能的知识方法库中提取所 体智能并不能等同于完全的自主式物理系统或生物 选用的智能计算宏观模型信息和相关知识.经过用 群体，而是在对相关模型深入研究和所需求解问题、 户过程设计模块之后就给定了相应的具体模型框 所使用方法进行详细考察设计后，基于所定义的模 架及总体参数 型框架使相关智能体所表现出的一种相对统一的智 在任务分解协调层中，主要进行的是决策分配 能计算模式 操作.决策分配模块依据上层给出的模型框架和总 2遗传算法的基本描述 体参数的信息，通过宏观任务描述、任务分解描述及 任务分配协调过程，总体的目标指令和决策参量就 遗传算法(genetic algorithm,GA)是20世纪 被分解为相应的局部任务指令，传输给下层的调度 70年代由美国的Holland提出的模拟生物进化过 实施模块.这一部分的任务是将宏观的参数分解成 程的优化方法，它的主要思想是基于C.R.Darwin 局部的任务和指令 的生物进化论和G.Mendel的遗传学o.遗传算法 在计算调度及信息感知层中，包括调度实施模 结合了Darwin的适者生存和随机交换理论.适者 块、信息交换模块和信息积累感知模块.依据上层传 生存理论消除了解中的不适应因素，而随机交换理 递下来的局部任务指令，由各智能体的调度实施模 论利用了原有解中的已有知识，从而加速了对优化 块来加以分布式实现.每个智能体可以是一个逻辑 解的搜索过程.遗传算法不需要对象的特定知识，也 概念，也可以是一个实体概念，这根据所需解决的具 不需要对象空间连续可微，具有全局寻优的能力.目 体问题来决定，其所需的实时运动参量控制信号由 前，遗传算法的应用涉及了许多互相联系的广阔领 各局部任务指令经实时任务规划运动规划、指令驱 域，如规划、仿真与辨识控制与分类等 动程序运动控制而产生.调度模块所需的实时信 遗传算法是将问题的求解表示成“染色体”，从 息，由信息感知积累模块通过对原始对象信息和原 而构成一群“染色体”.将它们置于问题的“环境”中， 始环境信息等传感器所输出的初始采集信息进行定 根据适者生存的原则，从中选择出适应环境的“染色 点感知、辨识转换，并经信号优化处理、具体知识提 体”进行复制，即选择，通过交叉、变异操作产生出更 取建模、知识积累提升、知识系统化而产生.而产生 适应环境的新一代“染色体”群，这样一代一代地不 的实时信息则通过信息交换模块，经过信息配置、信 断进化，最后收敛到一个最适合环境的个体上，即求 息接收、信息检验、信息转换、信息发送各部分传递 得问题的最优解 给各智能体的调度实施模块 遗传算法的运动过程为一个典型的迭代过程， 被控对象实体运动过程层包括被控运动过程或 其基本步骤简述如下： 被控实体对象以及相应的传感器系统.在被控运动 1)选择编码策略，把参数集合X和域转换为位 过程中，被控实体对象接收由上层计算调度及信息 串结构空间S: 感知层中调度实施模块提供的实时运动控制参量实 2)定义适应值函数f(X): 现实体的运动.传感器系统则采集实体对象的初始 3)确定遗传策略，包括选择群体规模n,选择、 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
在宏观设计及方法提升层中 ,包括用户过程设 计模块、知识方法提升模块及相关知识库和方法库. 知识方法提升模块经常性地从知识库和方法库中提 取智能算法模型库中已有的知识和方法 ,通过知识 方法提升模块进行提升 ,上升为体系结构 ,并把经过 提升的知识方法存放到知识方法库中 ,以备宏观设 计和决策分配模块调用. 用户过程设计模块则针对 实际所需解决的问题 ,向知识方法库发出模型提取 指令 ,并在现有的群体智能的知识方法库中提取所 选用的智能计算宏观模型信息和相关知识. 经过用 户过程设计模块之后 ,就给定了相应的具体模型框 架及总体参数. 在任务分解协调层中 ,主要进行的是决策分配 操作. 决策分配模块依据上层给出的模型框架和总 体参数的信息 ,通过宏观任务描述、任务分解描述及 任务分配协调过程 ,总体的目标指令和决策参量就 被分解为相应的局部任务指令 ,传输给下层的调度 实施模块. 这一部分的任务是将宏观的参数分解成 局部的任务和指令. 在计算调度及信息感知层中 ,包括调度实施模 块、信息交换模块和信息积累感知模块. 依据上层传 递下来的局部任务指令 ,由各智能体的调度实施模 块来加以分布式实现. 每个智能体可以是一个逻辑 概念 ,也可以是一个实体概念 ,这根据所需解决的具 体问题来决定 ,其所需的实时运动参量控制信号由 各局部任务指令经实时任务规划、运动规划、指令驱 动程序、运动控制而产生. 调度模块所需的实时信 息 ,由信息感知积累模块通过对原始对象信息和原 始环境信息等传感器所输出的初始采集信息进行定 点感知、辨识转换 ,并经信号优化处理、具体知识提 取建模、知识积累提升、知识系统化而产生. 而产生 的实时信息则通过信息交换模块 ,经过信息配置、信 息接收、信息检验、信息转换、信息发送各部分传递 给各智能体的调度实施模块. 被控对象实体运动过程层包括被控运动过程或 被控实体对象以及相应的传感器系统. 在被控运动 过程中 ,被控实体对象接收由上层计算调度及信息 感知层中调度实施模块提供的实时运动控制参量实 现实体的运动. 传感器系统则采集实体对象的初始 信息 ,并传送给上层信息感知积累模块. 总之 ,在上述的总体群体智能模型框架中 ,决策 分配模块、知识方法提升模块以及各智能体的调度 实施、信息交换、信息感知等模块之间具有一定的独 立性. 在设计和任务分配工作完成之后 ,智能体群的 运动基本上可以在一定的计算环境下分布式地独立 进行 ,这同时体现了群体智能理念中所包含的分布 式人工智能的本质特征. 当然 ,这里也可以看出 ,群 体智能并不能等同于完全的自主式物理系统或生物 群体 ,而是在对相关模型深入研究和所需求解问题、 所使用方法进行详细考察设计后 ,基于所定义的模 型框架使相关智能体所表现出的一种相对统一的智 能计算模式. 2 遗传算法的基本描述 遗传算法 ( genetic algorit hm , GA) 是 20 世纪 70 年代由美国的 Holland 提出的模拟生物进化过 程的优化方法 ,它的主要思想是基于 C. R. Darwin 的生物进化论和 G. Mendel 的遗传学[ 6 ] . 遗传算法 结合了 Darwin 的适者生存和随机交换理论. 适者 生存理论消除了解中的不适应因素 ,而随机交换理 论利用了原有解中的已有知识 ,从而加速了对优化 解的搜索过程. 遗传算法不需要对象的特定知识 ,也 不需要对象空间连续可微 ,具有全局寻优的能力. 目 前 ,遗传算法的应用涉及了许多互相联系的广阔领 域 ,如规划、仿真与辨识、控制与分类等. 遗传算法是将问题的求解表示成“染色体”,从 而构成一群“染色体”. 将它们置于问题的“环境”中 , 根据适者生存的原则 ,从中选择出适应环境的“染色 体”进行复制 ,即选择 ,通过交叉、变异操作产生出更 适应环境的新一代“染色体”群 ,这样一代一代地不 断进化 ,最后收敛到一个最适合环境的个体上 ,即求 得问题的最优解. 遗传算法的运动过程为一个典型的迭代过程 , 其基本步骤简述如下 : 1) 选择编码策略 ,把参数集合 X 和域转换为位 串结构空间 S ; 2) 定义适应值函数 f ( X) ; 3) 确定遗传策略 ,包括选择群体规模 n ,选择、 ·44 · 智 能 系 统 学 报 第 2 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第5期 康琦，等：基于群体智能框架理念的遗传算法总体模式描述 ·45· 交叉、变异方法以及确定交叉概率P、变异概P。 通过群体之间直接的协作来完成优化问题的求解， 率等遗传参数： 但其基本原理仍然是通过交叉等算子来实现间接的 4)随机初始化生成群体P: 协同进化，同样具有群体智能的典型特点，属于群体 5)计算群体中每个个体位串解码后的适应值 智能算法的范畴，因此，可以按照群体智能的理念框 f(x): 架来加以理解，构建遗传算法的群体智能框架模式 6)按照遗传策略，运用选择、交叉和变异算子作 在群体智能计算的总体框架理念下，构建的遗 用于群体，形成新一代群体 传算法的群体智能框架模型如图3所示 7)判断群体性能是否满足某一指标，或已完成 为了便于描述，把框架模型总体简化为任务分 设定的迭代次数，不满足则返回步骤6)，或者修改 解协调与模型方法提升层和计算调度及信息感知层 遗传策略再返回步骤6)；否则算法结束 2个层次.该简化模式总体上与群体智能计算总体 遗传算法的基本流程如图2所示 框架中的宏观设计及方法提升、任务分配协调、计算 调度及信息感知和被控实体运动过程的4层结构是 确定实际问题参数巢 一致的 确定表示问题求解的 GA计算框架中的上层是任务分解协调及模型 染色体（参数编码） 方法提升层，包括问题求解GA设计模块、知识方法 生成初始染色体群 P() 提升模块以及知识库方法库等；下层为计算调度及 适应度评价 信息感知层，主要包括染色体进化模式设定模块组、 (计算个体的适应度函数值) 与求解问题相对应的合理的约束交配模式和相关信 息定时感知和通讯等3个主要模块 生成新一代 收敛于问题 染色体群 、的最优解（或终止 与群体智能计算的总体框架一致，在GA计算 P+1) 、条件)？ 框架中，决策分配模块具体可称为问题求解GA设 N 计模块，而知识库和方法库存储的是GA这类模型 选择 结束 (根据染色体适应值 输出最优解 的相关知识方法，相应知识方法提升模块也提升 进行复制) GA相关的知识方法，调度实施模块具体可称为染 交叉(P) 色体进化模式设定模块，信息交换模块和信息感知 积累模块作为一个相互联系的整体结构，被简化为 变异(P) 求解问题相对应的合理的约束交配模式和相关信息 遗传操作」 定时感知及通讯模块，其中的约束交配模式等效为 一个信息互联传递及反馈网络，被控实体—染色 图2遗传算法的流程图 体种群正是在这样的问题求解环境中遗传进化的 Fig 2 Flowchart of genetic algorithm 问题求解GA设计模块针对具体问题设计GA 在采用遗传算法求解实际的组合优化问题时， 时，在知识方法库中提取GA的求解方法和己知的 首先需要对问题进行参数编码（确定表示问题求解 约束模式，最后得到GA的具体参数设定和局部运 的染色体)，然后确定适应度函数，并进行遗传操作 动模式.这些信息传递给染色体进化模式设定模块， (复制、交叉和变异等).经过多次迭代进化，最终得 这个模块不是唯一的，数目应该和染色体种群的规 到问题的最优解或近似最优解 模保持一致.每个模块只控制一个染色体或一个子 群，通过所有这些模块的进化，GA进行问题的寻优 3遗传算法的群体智能框架模式 过程.染色体进化模式设定模块之间需要进行信息 遗传算法虽然不像蚁群算法和微粒群算法那样 的交叉（染色体以一定的概率进行交配），这需要通 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
交叉、变异方法 ,以及确定交叉概率 Pc 、变异概 Pm 率等遗传参数; 4) 随机初始化生成群体 P; 5) 计算群体中每个个体位串解码后的适应值 f ( X) ; 6) 按照遗传策略 ,运用选择、交叉和变异算子作 用于群体 ,形成新一代群体; 7) 判断群体性能是否满足某一指标 ,或已完成 设定的迭代次数 ,不满足则返回步骤 6) ,或者修改 遗传策略再返回步骤 6) ;否则算法结束. 遗传算法的基本流程如图 2 所示. 图 2 遗传算法的流程图 Fig12 Flowchart of genetic algorithm 在采用遗传算法求解实际的组合优化问题时 , 首先需要对问题进行参数编码 (确定表示问题求解 的染色体) ,然后确定适应度函数 ,并进行遗传操作 (复制、交叉和变异等) . 经过多次迭代进化 ,最终得 到问题的最优解或近似最优解. 3 遗传算法的群体智能框架模式 遗传算法虽然不像蚁群算法和微粒群算法那样 通过群体之间直接的协作来完成优化问题的求解 , 但其基本原理仍然是通过交叉等算子来实现间接的 协同进化 ,同样具有群体智能的典型特点 ,属于群体 智能算法的范畴 ,因此 ,可以按照群体智能的理念框 架来加以理解 ,构建遗传算法的群体智能框架模式. 在群体智能计算的总体框架理念下 ,构建的遗 传算法的群体智能框架模型如图 3 所示. 为了便于描述 ,把框架模型总体简化为任务分 解协调与模型方法提升层和计算调度及信息感知层 2 个层次. 该简化模式总体上与群体智能计算总体 框架中的宏观设计及方法提升、任务分配协调、计算 调度及信息感知和被控实体运动过程的 4 层结构是 一致的. GA 计算框架中的上层是任务分解协调及模型 方法提升层 ,包括问题求解 GA 设计模块、知识方法 提升模块以及知识库方法库等 ;下层为计算调度及 信息感知层 ,主要包括染色体进化模式设定模块组、 与求解问题相对应的合理的约束交配模式和相关信 息定时感知和通讯等 3 个主要模块. 与群体智能计算的总体框架一致 ,在 GA 计算 框架中 ,决策分配模块具体可称为问题求解 GA 设 计模块 ,而知识库和方法库存储的是 GA 这类模型 的相关知识方法 ,相应知识方法提升模块也提升 GA 相关的知识方法 ,调度实施模块具体可称为染 色体进化模式设定模块 ,信息交换模块和信息感知 积累模块作为一个相互联系的整体结构 ,被简化为 求解问题相对应的合理的约束交配模式和相关信息 定时感知及通讯模块 ,其中的约束交配模式等效为 一个信息互联传递及反馈网络 ,被控实体 ———染色 体种群正是在这样的问题求解环境中遗传进化的. 问题求解 GA 设计模块针对具体问题设计 GA 时 ,在知识方法库中提取 GA 的求解方法和已知的 约束模式 ,最后得到 GA 的具体参数设定和局部运 动模式. 这些信息传递给染色体进化模式设定模块. 这个模块不是唯一的 ,数目应该和染色体种群的规 模保持一致. 每个模块只控制一个染色体或一个子 群 ,通过所有这些模块的进化 , GA 进行问题的寻优 过程. 染色体进化模式设定模块之间需要进行信息 的交叉(染色体以一定的概率进行交配) ,这需要通 第 5 期 康 琦 ,等 :基于群体智能框架理念的遗传算法总体模式描述 ·45 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·46 智能系统学报 第2卷 问题求解GA 考察所需求解问题 知识方法提升模块 设计模块 在GA框架下建立相关数 设计宏观知识总结 学模型，并设计相应评价 模式及评价函数 GA优化模式，求解方法 及已知约束模式 知识、方法 确定表示问题求解的 知识库 提升指令 运行效果评估优化 染色体（参数编码） 方法库 各类相关 知识、方法 模型总结优化 根据问题类型确定群 任务分解协调及模型方法提升层 体进化模式（选择，交 叉、变异策略) 应用领域拓展 染色体N的相关参数设定(P,P.…) 确定相关GA参数设置 染色体1的相关参数设定(P,P) 染色体1的相 问题求解种群的分解运动莫式及约束 关参数设定 (P.P。 色体进化模式 实时染色体适应 实时染色体适应 实时染色体适应 度函数求解 度函数求解 染色体进 度函数求解 根据运算结果设定 进化模 根据运算结果设定 根据运算结果设定 染色体1的进化，消 染色体的进化.消 染色体V的进化.消 定模块 除或生成新个体 除或生成新个体 除或生成新个体 (遗传操作) (遗传操作) (遗传操作) 进化结果分析 相关实时信息 定模块 式设定模块 ( 相关实时 N 进化结果分析 进化结果分析 相关实时信息 计算调度及信息感知层 进化控制信总1 进化控制信息 进化控制信息N 与求 P ☑ 约束 P P 式 相关信息定时感知 相关信息定时感知 相关信息定时感知 及通讯 及通讯 及通讯 问题求解环境 图3遗传算法的群体智能框架模型 Fig 3 Swarm intelligent framework model of genetic algorithm 过求解问题相对应的合理的约束交配模式来完成， 体种群的进化模式（包括选择、交叉、变异策略等）， 具体来讲，任务分解协调及模型方法提升层中 并确定GA相关的各参数设置，如交叉概率、变异概 的问题求解设计模块中所做的工作是，先考察所需 率Pm等 求解的优化问题，然后在GA框架下建立相应的数 在问题求解GA的分解运动模式和相关参数设 学模型，并设计相应的评价模式及评价函数.然后在 定好之后，可进入下层的计算调度及信息感知层.在 此基础上确定表示问题求解的染色体，即参数编码 此层中，主要执行的是染色体的遗传进化操作，即首 过程；待确定编码方式之后根据问题类型确定染色 先进行实时染色体适应度函数求解，然后根据计算 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 3 遗传算法的群体智能框架模型 Fig13 Swarm intelligent framework model of genetic algorithm 过求解问题相对应的合理的约束交配模式来完成. 具体来讲 ,任务分解协调及模型方法提升层中 的问题求解设计模块中所做的工作是 ,先考察所需 求解的优化问题 ,然后在 GA 框架下建立相应的数 学模型 ,并设计相应的评价模式及评价函数. 然后在 此基础上确定表示问题求解的染色体 ,即参数编码 过程 ;待确定编码方式之后根据问题类型确定染色 体种群的进化模式 (包括选择、交叉、变异策略等) , 并确定 GA 相关的各参数设置 ,如交叉概率、变异概 率 Pm 等. 在问题求解 GA 的分解运动模式和相关参数设 定好之后 ,可进入下层的计算调度及信息感知层. 在 此层中 ,主要执行的是染色体的遗传进化操作 ,即首 先进行实时染色体适应度函数求解 ,然后根据计算 ·46 · 智 能 系 统 学 报 第 2 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第5期 康琦，等：基于群体智能框架理念的遗传算法总体模式描述 。47。 结果分别对染色体进行遗传进化操作（选择、交叉、 [4]康琦，张燕，汪镭，等.群体智能应用综述[卩].冶 变异)，生成新的染色体，并进行进化结果分析，给出 金自动化，2005,29(5)：7-10. 遗传进化控制信息，实时设定各染色体在解空间中 KANG Qi,ZHAN G Yan,WANGLei,et al.Application 的进化增量.当然，染色体的联系主要通过交叉算子 overview on swarm intelligence[J ]Metallurgical Indus- (以一定的概率P.进行)来实现，相应的进化信息需 try Automation,2005,29(5):7-10. [5]吴启迪，汪镭.群体智能计算模式及应用[M].南京： 要通过相关的感知与通讯模块对染色体进行定时感 江苏教育出版社，2006 知和通讯及时获取并处理」 [6]李敏强.遗传算法的基本理论与应用[M].北京：科学出 4结束语 版社，2002. 作者简介： 通过具体的研究工作，对群体智能理念有了一 康琦，男，1980年生，博士研究 定的理解，总结并提出了群体智能计算的统一的框 生，IEEE会员，主要研究方向为计算智 架模型，并以遗传算法为例加以具体论述，给出了基 能群体智能和自然计算等，发表论文 于群体智能框架理念的遗传算法总体模式描述，以 20余篇 此来说明所建群体智能总体框架的有效性.将具有 E mail kangqi tj @163.com. 此类特征的智能算法用一种统一的框架来进行描 述，对于智能计算的系统化研究具有重要的意义 汪镭，男，1970年生，教授、博士 生导师.IEEE上海分会委员，中国人工 参考文献： 智能学会理事.主要研究方向为智能自 [1]KENNEDY J,EBERHART R C.Swarm intelligence 动化理论与应用，发表论文60余篇，其 中已被SCI、E1检索30余篇.出版学术专 [M].San Francisco:Morgan Kaufmann,2001 [2]张燕，康琦，汪镭，等.群体智能卫].治金自动化， 著4部. 2005,29(2):1-4. 吴启迪，女，1947年生，教授、博士生 ZHANG Yan,KANG Qi,WANGLei,et al.Swarm im 导师，教育部副部长.主要研究方向为 telligence[J ]Metallurgical Industry Automation,2005, 控制理论与应用、计算机集成制造系统 29(2):1-4. 及智能自动化理论与应用.已出版多部 「3彭宇.群智能优化算法及理论研究[D].哈尔滨：哈尔 滨工业大学，2004. 学术专著和译著，发表论文200余篇， 荣获国家级、教育部、上海市等科技进 PENG Yu.Swarm intelligence optimization algorithm 步奖多项 and theory study [D].Harbin:Harbin Institute of Tech- nology,2004. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
结果分别对染色体进行遗传进化操作 (选择、交叉、 变异) ,生成新的染色体 ,并进行进化结果分析 ,给出 遗传进化控制信息 ,实时设定各染色体在解空间中 的进化增量. 当然 ,染色体的联系主要通过交叉算子 (以一定的概率 Pc 进行) 来实现 ,相应的进化信息需 要通过相关的感知与通讯模块对染色体进行定时感 知和通讯及时获取并处理. 4 结束语 通过具体的研究工作 ,对群体智能理念有了一 定的理解 ,总结并提出了群体智能计算的统一的框 架模型 ,并以遗传算法为例加以具体论述 ,给出了基 于群体智能框架理念的遗传算法总体模式描述 ,以 此来说明所建群体智能总体框架的有效性. 将具有 此类特征的智能算法用一种统一的框架来进行描 述 ,对于智能计算的系统化研究具有重要的意义. 参考文献 : [1 ] KENN ED Y J , EBERHART R C. Swarm intelligence [ M]. San Francisco :Morgan Kaufmann , 2001. [2 ]张 燕 ,康 琦 ,汪 镭 ,等. 群体智能[J ]. 冶金自动化 , 2005 , 29 (2) : 1 - 4. ZHAN G Yan , KAN G Qi , WAN G Lei , et al. Swarm in2 telligence[J ]. Metallurgical Industry Automation , 2005 , 29 (2) :1 - 4. [3 ]彭 宇. 群智能优化算法及理论研究[D ]. 哈尔滨 :哈尔 滨工业大学 , 2004. PEN G Yu. Swarm intelligence optimization algorithm and theory study [D]. Harbin : Harbin Institute of Tech2 nology , 2004. [4 ]康 琦 ,张 燕 ,汪 镭 ,等. 群体智能应用综述[J ]. 冶 金自动化 , 2005 ,29 (5) :7 - 10. KAN G Qi , ZHAN G Yan , WAN G Lei ,et al. Application overview on swarm intelligence[J ]. Metallurgical Indus2 try Automation , 2005 ,29 (5) :7 - 10. [5 ]吴启迪 ,汪 镭. 群体智能计算模式及应用[ M ]. 南京 : 江苏教育出版社 , 2006. [6 ]李敏强. 遗传算法的基本理论与应用[ M ]. 北京 :科学出 版社 , 2002. 作者简介 : 康 琦 ,男 , 1980 年生 ,博士研究 生 ,IEEE 会员. 主要研究方向为计算智 能、群体智能和自然计算等 ,发表论文 20 余篇. E2mail :kangqi_tj @163. com. 汪 镭 ,男 ,1970 年生 ,教授、博士 生导师. IEEE 上海分会委员 ,中国人工 智能学会理事. 主要研究方向为智能自 动化理论与应用 ,发表论文 60 余篇 ,其 中已被 SCI、EI 检索 30 余篇. 出版学术专 著 4 部. 吴启迪 ,女 ,1947 年生 ,教授、博士生 导师 ,教育部副部长. 主要研究方向为 控制理论与应用、计算机集成制造系统 及智能自动化理论与应用. 已出版多部 学术专著和译著 ,发表论文 200 余篇 , 荣获国家级、教育部、上海市等科技进 步奖多项. 第 5 期 康 琦 ,等 :基于群体智能框架理念的遗传算法总体模式描述 ·47 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
