基于最优保留的CGA及其在TSP欺骗问题中的应用  

CGA Based on Optimum Retention and Its Application in TSP Deceptive Problems

作　　者：武晓今[1] 朱仲英[1] 

机构地区：[1]上海交通大学自动化系

出　　处：《微型电脑应用》2005年第4期43-45,57,共4页Microcomputer Applications

摘　　要：本文在对CGA算法分析说明的基础上,运用改进CGA的方法来解决TSP欺骗问题。虽然CGA能够“快速、简单”的解决一些优化问题,但是由于其概率向量中基因的独立性,使得它在进化计算中会丢失基因之间的关联信息,从而可能无法解决如欺骗函数等复杂、困难问题。文中通过对CGA在TSP算法上的改进,以一定遗传尺度保留竞争最优个体,从而有效地解决TSP欺骗问题,并通过仿真结果验证了该算法,给出解决该类组合优化问题的一个有效例证。This paper illustrates and analyzes the Compact Genetic Algorithm (CGA) and proposes to use the improved CGA to solve TSP deceptive problems. Though CGA can'quickly and simply'solve some optimal problems, the operation of each gene is independent, which may lose linkage information, thus not being able to solve such difficult and complex problems as deceptive fuction. This article improves the CGA algorithm in TSP to solve the decetive problems effectively and its performance has been verified by emulation results, which can also be used to solve similar combinational optimization problems.

关 键 词：CGA 欺骗 最优保留 应用 组合优化问题 TSP算法 算法分析 概率向量 关联信息 进化计算 最优个体 仿真结果 独立性 基因 丢失 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP309[自动化与计算机技术—计算机科学与技术]