遗传算法[1,2]是由教授于年首先提出JohnH.Holland1975来的。这种算法是受达尔文的生物进化论启发而创建的,是基于生物进化中自然选择、适者生存和物种遗传思想的搜索算法。它是一种非数值并行优化算法。近年来,遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时所表现出的鲁棒性、全局最优性、隐含并行性和自适应性而使其成为目前应用较为广泛的一种智能优化方法[1,2]。但在传统的遗传算法中[1],算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。针对上述矛盾,我们提出了一种改进现有寻优性能的综合控制策略:GA(1杂交、变异的并行处理;基于适应值密度的变异操作;(2自调整父代迁移策略与父代与子代竞争策略。并通过求(3解问题验证了算法的有效性。TSP遗传算法简介1设待优化的函数为,是一个向量,它是所有的可能f(xx的取值构成的该优化问题的变量空间。首先,由构造出f(x一个适应值函数,该适应值函数必须满足其下面g(x=F[f(x]两个条件:的值域g(xVR+(R+表示全体非负实数的集合;在取得最优值的点时取得最大值。g(x遗传算法的实现步骤如下[1,2]:确定遗传算法的参数:种群大小,交叉概(1POPSIZE率Pc,变异概率Pm。初始化:随机产生一个规模为的初始种(2POPSIZE群,其中每个个体为二进制位串的形式。并计算每个个体的适应值Gi。杂交:从种群中随机选择两个染色体,按一定的杂(3交概率Pc进行基因交换,交换的位置随机产生。变异:从种群中随机选择一个染色体,按一定的变(4异概率Pm进行基因变异。繁殖:计算当前代每个个体的适应值;根据其相对(5适应值,计算每个个体(也即染色体的再生次数,并进行繁殖操作。繁殖后保持种群个数不变。POPSIZE如果满足停止规则,则返回当前代适应值最高的个(6体所对应的变量空间的点,作为优化的结果;否则,回到x继续繁衍下去。(3遗传算法研究的主要目标是既要使算法的质量提高,又要求算法具有高的计算效率。一方面,由于遗传算法是一种随机搜索,所以好的解往往需要大的计算量;另一方面,收敛速度高的算法通常导致早熟,使解的质量降低。在传统的中,主要通过变异率来调节收敛速度和解的质量之间的GA矛盾[3]。变异率太小,则算法容易陷入局部最优值,导致早熟,使解的质量降低;反之,变异率太大,则遗传算法退化为随机搜索法。因此,我们针对遗传算法的演化步骤,从多方面入手,提出了一种改进遗传算法的综合控制策略。改进遗传算法的控制策略2好的算法使计算效率和解的质量之间的平衡。可以从遗传算法的选择操作来理解收敛速度与解的质量间的关系。从个体选择方面来讲,高的收敛速度通常通过采用高选择压力,即给予当前代中的具有较高适应值的个体较高的再生概率来实现。另一方面,由于群体规模不变,使得当前代中的具有较低适应值的个体降低了群体中个体的信息含量,使算法搜索新解区域的能力降低,即降低了算法搜索全局最优解的能力。因此,容易导致早熟收敛。既要使算法有较快的收敛速度,又要获得令人满意的解。我们提出的改进遗传算法从以下几方面对传统进行了改进。GA杂交、变异的并行处理2.1传统的计算结构模拟生物的遗传进化过程,即采用GA一种改进遗传算法及其在问题中的应用TSP陈斌,徐华中(武汉理工大学自动化学院,武汉430070摘要:传统遗传算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。文章针对上述矛盾,提出了改进遗传算法的控制策略—杂交、变异的并行处理、基于适应值密度的变异操作、自调整父代迁移策略和父代与子代竞争策略。并应用于问题中,验证了算法TSP的有效性。关键词:遗传算法;改进遗传算法;控制策略;旅行商问题AnImprovedGeneticAlgorithmandItsApplicationinTSP,CHENBinXUHuazhong,(SchoolofAutomation,WuhanUniversityofTechnologyWuhan430070【】AbstractTheconvergencespeedofgeneticalgorithmandthequalityofproblemresultarethemaininconsistencywhichaffectstheperformanceofGA.ThepaperproposesthecontrolstrategiesofimprovedGA,whichareparalleloperationofcrossoverandmutation,mutationbasedonthedensityoffitness,theadaptivemigrationoffathergenerationandcompetitionoffathergenerationandfilialgenera...