融合模拟退火的遗传算法研究与应用——以行程规划问题为例

杨 刚，余 顺

（安徽职业技术学院 信息工程系，合肥 安徽 230011）

融合模拟退火的遗传算法研究与应用
——以行程规划问题为例

杨 刚，余 顺

（安徽职业技术学院 信息工程系，合肥 安徽 230011）

遗传算法具有较强的全局搜索能力，但容易陷入局部最优.把模拟退火算法的思想融入到遗传算法中，在选择、交叉和变异的过程中加入退火过程，并使用改进后的算法求解行程规划问题，实验结果证明设计的算法是有效的.

遗传算法；模拟退火算法；行程规划

0 引言

优化算法的典型应用场景是存在大量可能的解以至于无法对其进行一一尝试的情况.最简单也是最低效的求解方法，莫过于去尝试随机猜测的上千个解，并从中找出最佳解来.而更有效的方法，则是以一种对题解可能有改进的方式来对其进行智能化修正.

近年常用于优化问题的智能算法主要有遗传算法与模拟退火算法两种.这两种智能算法有各自的优缺点.遗传算法的全局搜索能力较强，由于其内部具有并行性，因此可以方便地进行分布式计算，从而得以快速地搜索出解空间中的全体解，而不会陷入局部最优解的快速下降陷阱.但是遗传算法的缺点也很明显，即局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低.在具体应用中，如何在保留优良个体的同时维持群体的多样性，一直是遗传算法中较难解决的问题[1].与遗传算法相比，模拟退火算法的优势在于摆脱局部最优解的能力，它能够以随机搜索技术从概率的意义上找出目标函数的全局最优解.但是，由于模拟退火算法对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，使得模拟退火算法的运算效率不高[2].本研究通过将模拟退火算法的思想融入遗传算法中，并根据所要解决的问题对选择算子、交叉算子和变异算子进行了设计，增强了遗传算法的全局收敛性.

1 问题描述

为来自不同地方去往同一地点的人们安排一次会面是一件极富挑战性的事情.假设有一些毕业多年的同学想要来一次聚会，他们来自全国各地，并且他们希望在北京会面.他们将在同一天乘坐飞机到达并在机场集合.他们还将在同一天离开，而且他们将一同到达机场乘坐各自的航班.每天有许多航班从任何一个人所在的城市地飞往北京，每天也有许多航班从北京飞往任何一个人所在的城市.这些航班的价格和起飞时间也都不尽相同.现在需要帮助他们规划他们去和回时的航班，使得总体成本最小.需要考虑两个方面的成本，一是价格，一是等待时间.

设共有 n 个来自不同地方人 Pi(i=1，2，3，…，n)，用 Gi(i=1，2，3，…，n)表示每个人所在城市飞往北京的航班价格，用 Ci(i=1，2，3，…，n)表示从北京返回每个城市的航班价格，用 GTi(i=1，2，3，…，n)表示每个人到达北京的时间，用CTi(i=1，2，3，…，n)表示每个人离开时航班起飞的时间.为方便计算，GTi和CTi的值用某一个时间在当天的分钟数来表示.例如：早上的“00∶30”用30来表示，早上的“08∶30”用510来表示.同时把每1 min等同于1元钱.这样就可把价格和时间联系在一起.对问题分析后可得到以下公式：

所有人的航班的总价格：

所有人的等待时间：

因此，成本函数为：

F的值越小，则成本越低.

2 遗传算法简介

遗传算法是受自然科学启发的一种智能算法[1，2].遗传算法的运行过程是先随机产生一组被成为初始种群的解，然后对种群中的所有个体进行评价以及遗传操作，生成下一代种群，然后继续对种群中个体进行评价，这个过程将不断被重复，直到满足结束条件为止.

在种群进化的过程中，最重要的操作是选择，选择方法有很多，但都会有一个核心的思想，选择适应度值较高的个体.因此新的种群可以被称为较优解.新种群中的余下部分可通过修改种群中的个体产生.修改的方法主要有两种.一种方法被称为交叉.这种方法是从种群中随机选取个体a和b，然后将他们按照某种方式进行结合，形成一个新的个体c，或者a和b按照某种方式互换基因，形成两个新的个体a'和b'.另外一种是较为简单的方法，被称为变异，通常的做法是随机的选择个体a，然后对a进行微小的随机改变以产生一个新的个体a'.

通过对较优解进行随机的变异和交叉处理，将会构造出一个新的种群，它的规模通常与初始种群相同.这一过程会一直重复进行，直到到达指定的迭代次数，或者连续经过数代后，个体的适应度值变化很小或者不再改变，整个过程就结束了.

3 模拟退火算法简介

模拟退火算法也是受自然科学启发的智能算法[2，3].退火是指当合金停止加热后，温度开始慢慢降低，一直到温度不再改变的过程.在模拟退火算法开始时，需要设定两个变量，一个用于表示温度的变量，该变量的值非常大，一个用于表示解的变量，该变量的值是问题的一个随机解.在算法的整个迭代过程中，每迭代一次，温度就会以一定的系数逐渐变小，同时算法会随机选中解中的某个位置，然后随机变化.

在模拟退火算法的迭代过程中，如果新的解比当前解更优秀，则新的解成为当前的解.不过如果新的解没有当前解优秀的话，新的解也可能成为当前解.这是为了避免陷入局部最优的一种尝试.在某些情况下，在能够得到一个更优的解之前转向一个更差的解是很有必要的.模拟退火算法之所以管用，不仅仅因为它总是接受一个更优的解，而且还因为它在退火过程中的开始阶段会接受表现较差的解.随着迭代次数的增加，算法越来越不可能接收较差的解，因为接受较差解的概率越来越小，最后它将接受更优的解.算法运行过程中接受更差解的概率由下列公式给出：

式中，temperature表示温度，highcost表示较优的解，lowcost表示较差的解.因为temperature开始非常之高，指数将总是接近于0，所以概率几乎为1.随着temperature的递减，较优解和差解之间的差异越来越重要——差异越大，概率越低，因此该算法只倾向于稍差的解而不会是非常差的解.

4 混合遗传算法与模拟退火算法求解行程规划问题

遗传算法的优点是把握总体的能力较强，但它也有很明显的缺点：局部搜索能力较差以及容易发生“早熟”现象.所以应用遗传算法求解行程规划问题时，实验的结果并不能令人完全满意.为达到较好的效果，本研究利用对遗传算法进行改进，把模拟退火算法的思想融入进来.具体求解过程如下：

1）编码方式、适应度函数和种群的初始化

①编码方式

应用遗传算法求解问题时，首先要将问题的解映射成染色体，本研究采用实数编码方式[4].用数字表示某个城市到北京（或北京到某个城市）的第几号航班，如0表示某个城市到北京当天的第1个航班，1表示第2个航班，依次类推.因为每个人都需要返航，所以染色体的长度是人数的两倍.假设有5个来自不同城市的人，则一个解映射成一个染色体，表示为：1，4，3，3，7，5，6，1，0，9.

②适应度函数

遗传算法在对问题求解的过程中，考察个体的唯一指标就是适应度值.一般而言，适应度值高，则说明个体好，反之说明个体坏，容易被淘汰.所以适应度函数的选取是十分关键的，要能把个体的好坏区分开来.

在生成初始种群后，可以使用目标函数式（3）求解每个染色体的成本.因为成本越低越好，但个体的适应度值越高表示该个体越好.因此适应度函数可由目标函数做如下变换得到：

式中，C为一个较大的整数.

③种群的初始化

随机产生种群规模为PopSize的初始种群，为保证种群中个体的多样性，种群中的个体不尽相同.

2）选择退火算子

生成初始种群后，算法进入迭代过程，首先是对初始种群中的个体进行选择，选择的方法有多种，但不管采用什么方法，目的都是选出适应度值较大的个体，从进化的角度来说，适应度值大的个体更容易生存.本研究设计的选择过程如下：

①从种群中随机选择个体Zi和Zj，然后分别计算它们的适应度值f（Zi）和f（Zj）；

②如果f（Zi）＜f（Zj），则个体Zi遗传到下一代；否则，个体Zj以概率m遗传到下一代；

③重复①，②操作直到选出TopSize个个体.TopSize小于PopSize.

3）交叉退火算子

经过选择操作，种群的规模由PopSize降为TopSize，现在需要对个体进行修改以产生新的个体来扩大种群规模.首先进行的是交叉操作，本研究设计的交叉过程如下：

①随机选取个体Zi和个体Zj；

②将个体Zi和Zj进行交叉，生成新的个体Z'，计算个体适应度f（Zi），f（Zj），f（Z'）；

③进行退火操作，如果max[f（Zi），f（Zj）]＜f（Z'），则把个体Z'加入种群，否则，以概率m把个体Z'加入种群；

④循环步骤①，②，③，直到种群的规模达到PopSize.

4）变异退火算子

交叉操作之后是变异操作.本研究设计的变异过程如下：

①在种群中随机选择个体Z；

②在Z中随机选择3个位置，然后在该位置随机选择方向进行改变以产生一个新个体Z'；

③计算个体适应度值f（Z）和f（Z'）.如果f（Z'）＜f（Z），则用Z'代替Z；否则，以概率m接受Z'；

④随机重复步骤①、②、③n次，n是一个比较小的整数.

5）更新群体

选择、交叉和变异产生了下一代种群，该种群将重复选择、交叉和变异的过程.

6）结束条件

设定了以下两个结束条件，当满足任意条件之一时，算法运行结束.

①群体进化的代数已经达到设定的最大值；

②随着种群的不断进化，最优的适应度值不再发生变化时.

5 实验和结果

为了能够验证混合算法的有效性和稳定性，本研究通过数据实验对改进的混合算法与传统的遗传算法进行对比. 实验环境：CPU-INTER（R）Pentium（R）2 Dual CPU@2.4 GHz，内存 3 GB；操作系统为 Windows 7（32位）；开发程序python 3.5.实验中假定有6个来自不同城市的人，每个城市和北京之间的航班数据如表1所示.

表1 航班时刻表

对算法的参数做如下设置：初始种群规模：40；初始温度：500 000；降温系数：0.985；退火终止温度：0.1；最大进化代数：500；变异概率：0.2.分别用基本遗传算法和本研究提出的改进算法进行计算500次，结果如表2所示.从表2可以看出，本研究设计的遗传退火算法与基本遗传算法相比，可以更快速地寻找到最优解，同时，所得到的解也比基本遗传算法的解更优.

表2 基本遗传算法与遗传退火算法的运行结果

6 结束语

遗传算法是同时对问题的多个可能解进行评价，因此运行速度快，但容易陷入局部极优，而且不容易跳出局部极优，所以本研究把模拟退火算法的思想融入到遗传算法中，帮助遗传算法克服了传统遗传算法的早熟收敛问题，具有更强的通用性、稳健性和精确性.实验结果表明，将遗传退火算法应用于行程规划问题，能够得到更优的解，为这类问题提供了一种新的有效方法.

[1]杨元峰.基于模拟退火遗传算法的多车场车辆调度问题的研究与应用[D].苏州：苏州大学，2006.

[2]朱文坚，陈东，刘建素.遗传算法在多目标优化设计中的应用研究[J].机械工程师，2001，（12）：7-9.

[3]申巍.基于模拟退火的混合遗传算法在变电站选址中的应用[D].保定：华北电力大学，2007.

[4]张晋，李冬黎，李平.遗传算法编码机制的比较研究[J].中国矿业大学学报，2002，31（6）：637-640.

The Application of Genetic Algorithm Fusing Simulated Annealing in Itinerary Planning Problem

YANG Gang,YU Shun
(Department of Information Engineering,Anhui Vocational College,Hefei,Anhui 230011,China)

Genetic algorithm has strong global search ability,but easy to fall into local optimum.In this paper,the simulated annealing algorithm thinking is incorporated into the genetic algorithm,and the annealing process joins the selection,crossover and mutation.The improved algorithm is used to solve the itinerary planning problem.The experimental results show that the algorithm is effective.

genetic algorithm;simulated annealing algorithm;itinerary planning

TP391

A

1673-1972（2017）06-0040-05

2017-10-17

2014年度安徽省质量工程项目；计算机多媒体教学团队项目（2014jxtd076）

杨刚（1982-），男，安徽五河人，副教授，主要从事算法分析与设计和软件工程研究.

（责任编辑 王颖莉）