基于移民策略与优势基因的遗传算法的改进

赵恒昌（四川大学计算机学院，成都　610065）

基于移民策略与优势基因的遗传算法的改进

赵恒昌
（四川大学计算机学院，成都610065）

0　引言

遗传算法是由美国的Holland教授与1975年在他的专著《自然界和人工系统的适应性》[1]中首先提出的。遗传算法是一种进化算法。它的具体定义，很多文章给了不同的解释[2]。可是公认的，遗传算法的基本原理，是相同的，它借鉴了自然进化论中“物竞天演,适者生存,不适者淘汰”的思想 ,在诸多工程领域得到了实效性的应用。旅行商问题的时间复杂度为O（n!），遗传算法面对这类问题，一般可以得到较优的解。但是，随着n的增多，遗传算法也暴露出了诸多不足，过早收敛于局部解（表现不好的局部解），或者收敛太慢。

1　遗传算法概述

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按问题所要求的个性选出一部分个体，同时也淘汰一部分个体，利用选出来的个体进行杂交、变异等演化，产生新一代的种群，重复此过程，直到满足某种收敛指标为止。与传统的启发式优化搜索算法相比，遗传算法的主要本质特征在于群体搜索策略和简单的遗传算子。

遗传算法中，杂交、变异、选择，方式多种多样。文章的实验均采用了较为常规的方法。文章重点放在了寻找优势基因，由优势基拼接出优秀个体，在结合移民策略来改进遗传算法。

经典遗传算法流程图如图1。

图1　

2　旅行商问题

旅行商问题 （Travelling Salesman Problem，TSP）是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现已归入所谓的NP完全问题。经典提法为:有一货物推销员要去若干个城市推销货物，从某个城市出发,经其余各城市至少一次,然后回到那个城市,选择怎样的行走路线,才能使总行程最短（各城市间距离为已知）[3]。

TSP问题可以采用如下数学描述：

城市集合C（C_1，C_2，C_3，…，CN）；距离矩阵Distance（N*N），Distance（i，j）表示城市i与城市j之间的距离；要求找到一条访问路径T（T（1），T（2），…，T （n）），T（i）表示第i个访问城市的编号。令f（T）最小。

TSP问题实际上是一个优化问题。

3　针对经典遗传算法的改进

在经典遗传算法中，变异率是固定的。大多数情况下，种群经过多代更新以后，种群的素质趋于一致，特别是种群中保留的精英群体，几乎完全一样，造成了种群的“近亲繁殖”[4]。近亲繁殖不利于后代个体的继续完善，导致种群多样性下降，这样很可能导致算法收敛于一个较差的局解。为了改善这种不足，本文提出了移民策略。

移民策略：在种群进化过程中，保留一定的比例（一般只有百分之几）给“移民”。“移民”是指不是有上一代种群“繁殖”（上一代种群经过杂交、变异、自然选择产生的新一代）而来，而是由外部迁移而来，在本文中“移民”有随机算法生成，然后加入种群。

在遗传算法中，评价系统是基于个体的。在针对TSP问题时，评价系统即是：访问所有城市，距离最短的顺序。这样，虽然极好地适应了问题的要求与目的，但是城市数量较多时，问题的候选解空间是巨大的，极大地增加了寻找最优解的难度。

经过分析，每一个个体都是由一个一个的“基因”链接而成的。“基因”即是构成个体的小的组成部分。针对不多的问题，解的个体“基因”的含义也是多种多样的。在TSP问题中，本文采用的“基因”定义如下：一个紧密连接的城市访问顺序。举例来讲，六个城市（城市编号依次为1，2，3，…6）的访问顺序多种多样，假设一个个体解为6 2 3 1 4 5，它的基因即是 “62”，“23”，“31”，“14”，“45”“56”六个基因。举例来讲基因“62”，就是旅行商在访问所有城市中，由城市6直接到达城市2的简单路径。当然基因的具体定义，虽然问题以及目的的不同，自然也是千差万别。为了便于研究，本文采用了这种相对简单的定义。

基因优势：每个基因各有各自的优势，但是优势的评估是基于个体的。如果大量含有特定基因的个体，表现良好，可以认为该基因为优势基因；反之，如果大量含有这一基因的个体，表现糟糕，可以认为该基因为劣势基因。为了便于描述本文的数学公式，文章采用下面符号。

GeneAdvantage（i，j）表示基因（i，j）的优劣，具体含义是包含该基因的个体的平均表现，在TSP问题中即是访问完所有城市的距离的平均值。该值越小，说明该基因优势越大。

C（i，j）包含基因（i，j）的个体的集合。

Number_C（i，j）包含基因（i，j）的个体集合的大小

基因拼接，基于优势基因本文提出了基因拼接的技术（或者基因合成，但是拼接一词，更贴切本文的描述）。基本原理如下：

①城市均以数字（1-n）编号。初始队列T为空，T为旅行商的访问顺序；L为数字1-n的集合，L为旅行商下一个要访问的城市的集合。

②任意选择一个城市作i为旅行商的起点城市，加入队列T，同时L中减去i。

③选出T中最后加入的城市i，然后选出i与L中城市形成最优的基因（i，j）的城市j，然后将j加入队列T，同时把j从L中去除。

④如果L为空，输出T；否则继续执行③。

基因拼接方法可以较经典遗传算法，迅速地求得较好地解。我们以美国48个城市的旅行商问题（数据来源于网站TSPLIB，压缩包att48.tsp.gz），为实验数据，以MATLAB 2015a为平台，来阐述实践结果。

经典遗传算法：种群个数2000，繁殖1000代，计算两百万个候选解，耗时254秒，得到的最优解：45218，旅行商路径如图2。

基因拼接算法：分析二十万个候选解，再合成1000个解，耗时35秒，得到最优解：35974，旅行商路径如图3。

事实上的最优解为33524，旅行商路径如图4。该数据由网站TSPLIB提供。

图2　

图3　

遗传算法简单通用，具有很强的全局搜索能力。正因为此，遗传算法在各个领域得到了广泛的应用。而大量数据表明遗传算法局部搜索能力差，容易陷入早熟收敛：进化中群体多样性迅速下降，个体间的竞争力度急剧下降，进化能力基本丧失[5]。相关种群问题的研究，1989年Whitley提出，GA（Genetic Algorithm，即遗传算法）最重要的两个因素就是“种群多样性”和选择压力[6]，本文主要从种群多样性的角度出发，研究遗传算法的改进。本文实验数据，表明了基因拼接方法的优势，基因拼接方法是基于优势基因，而优势基因的获得，需要在候选解空间中充分抽样个体，统计后获得。基于以上讨论，本文对遗传算法做了如下改进，如图5。

改进后的算法：种群个数1000，繁殖300代；因为移民策略，要额外评估30万个个体。总共计算了110万个候选解，耗时175秒，得到最优解：34374（与事实上的最优解，有2%的误差）。旅行商路径如图6。

4　结语

基因拼接的方法，可以在短时间内拼接处较为优秀的个体。把这些个体加入遗传算法的种群中，极大地加速了遗传算法的收敛速度，并且同时增大了种群的多样性。本文中，遗传算法的变异、杂交、选择，都是采用了较为常规的方法。至于本文重点研究的优势 “基因”，它们的合成与拼接，本文采用较为简单的方法，但这种方法有很多不足，诸如在拼接过程中，很可能舍弃了更具优势的基因。

图4　

图5　

图6　（最优路线）

[1]HOLLAND J H.Adaptation in Natural and Artificial Systems:an Introductory Analysis with Applications to Biology，Control，and Artificial Intelligence[M].2nd.Cambridge:MIT Press[M]，1992.

[2]Jeff Heaton.Artificial Intelligence for Humans，Volume 2:Nature-Inspired Algorithms.Heaton Research，Inc[M]，May 28，2014.

[3]黄厚生.求解旅行商问题的新方法研究[D]，2005，1.

[4]李军.基于最优基因的遗传算法研究[D]，2007，4.

[5]崔珊珊.遗传算法的一些改进及其应用[D]，2010，5.

[6]Darrell Whitley.The GENITOR Algorithm and Selection Pressure:Why Rank-Based Allocation of Reproductive Trials is Best.1989[J]

Genetic Algorithm;Immigration Policy;Gene Advantage;TSP;Permutations Optimization

Genetic Algorithm Improvement Based on Immigration and Better Genes

ZHAO Heng-chang
（College of Computer Science，Sichuan University，Chengdu，610065）

1007-1423（2016）07-0036-04

10.3969/j.issn.1007-1423.2016.07.008

赵恒昌（1988-），男，，山东新泰人，硕士，研究方向为人工智能、最优化理论、算法设计与分析

2016-01-26

2016-02-26

遗传算法在解决候选解空间巨大的问题时，可以比较有效地找到最优解或者次优解。但是遗传算法也存在诸多不足，例如收敛速度慢，早熟收敛。基于特定基因的优势，构想出基因拼接的方法；同时为了拓展算法的搜索空间和增加种群多样性，改进算法引入移民策略。以旅行商问题（TSP）为例，实践验证所提出的算法思想。

遗传算法；移民策略；基因优势；旅行商问题；排列优化

Genetic algorithms dealing with problem with huge solution space of the candidate,can be more effective in finding an optimal solution or suboptimal solutions.But there are also many defects,such as slow convergence,premature convergence.Based on the advantages of spe-cific genes,creates gene-joint technique.In order to expand the search space and increase the diversity of the population,the improved algorithm introduced immigration policy.Takes the traveling salesman problem(TSP)as an example,to practice the algorithm thought.