第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