遗传算法基于路径优化问题应用的改进探索研究

摘要：遗传算法是一种应用很广泛的智能优化算法，对遗传算法进行了分析研究，针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上，基于遗传算法，研究了物流系统中的库存优化问题及车辆路径问题。将车辆路径问题看做是组合优化问题，并应用遗传算法进行求解。

关键词：路径优化；遗传算法；禁忌搜索算法

中图分类号：F25文献标志码：A文章编号：1673-291X（2011）04-0199-02

引言

随着经济快速发展、信息化时代的来临，尤其是网络购物等新型购物方式的发展壮大使得物流业迅速成为人们日常所不可缺少的行业。与此同时物流业之间的竞争也迅速加剧。而物流业也与其他服务业一样除了服务质量的竞争以外关键在于成本的竞争。物流企业成本绝大部分在于运输过程中产生，有效地路径优化能够帮助物流企业很好的解决成本节约问题。从而遗传算法等高效简洁的优化算法成为人们越来越关注的对象。

一、研究背景

近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理的人工智能方法在知识表示、信息处理和解决组合爆炸等方面遇到的困难越来越明显，从而使得寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的算法成为有关学科的一个研究目标。遗传算法（genetic algorithms，简称GA）是J.Holland与1975年提出的。GA是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。

二、遗传算法

GA是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，其两个显著性特点是隐含并行性和全局解空间搜索。它是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。

遗传算法主要借鉴了生物进化的一些特征，它的主要生物进化特征体现在：（1）进化发生在解的编码上。这些编码用生物术语称为染色体。由于一开始要进行编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。（2）自然选择规律决定哪些染色体产生超过平均数的后代。而在遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。（3）当染色体结合时，双亲的遗传基因结合使得子女保持有父母的特征。（4）染色体结合以后，随机的变异会造成子代与父代产生不同的特征。

遗传算法主要包含以下处理步骤：第一是对优化问题的解编码。此外，称一个解的编码为一个染色体，组成编码的元素成为基因。编码的目的主要是用于优化问题的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体就组成了一个种群，形成一个可以繁衍下一代的种群。第三是染色体的结合。双亲的遗传基因之间的结合是通过编码之间的（crossover）达到下一代的产生。

遗传算法作为一个全局性优化算法具有很大的优越性，具体体现在：（1）遗传算法适合求解那些带有多参数、多变量、多目标和在多区域但连通性较差的NP难（非多项式确定性问题）优化问题。对多参数、多变量的NP难优化问题，通过解析求解或计算求最优解的可能性很小，主要依赖于数值求解。遗传算法就是一种数值求解的算法，具有普遍性并且对目标函数的性质几乎没有要求，并且它可以一次记录多个解。（2）遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深入的了解。如路线调度问题、排序等。遗传算法再给这些问题的决策变量编码后，起计算过程是比较简单的，并且可以较快的得到一个满意解。（3）遗传算法同求解问题的其他启发式算法有较好的兼容性。

当然遗传算法也不可避免地存在着它的不足之处：（1）存在编码不规范及表示不准确等问题。（2）单一的遗传编码不能全面地将优化问题的约束表示出来。（3）大量研究也表明，GA存在早熟、算法参数敏感等缺点，取得良好的性能需要依赖较大的种群并对算法进行精心设计。

采用遗传算法等智能优化算法来求解带能力约束的车辆路径问题 （Capacitated Vehicle Routing Problem，即CVRP），一般能在较短的计算时间内获得质量较高的近似解。

三、问题描述

CVRP可描述如下:配送中心有m辆货车，每辆车的能力为q；配送中心需为n个客户提供货物配送任务，每个客户的需求量为gi（i=1，2，…，n），gi

有1个配送中心和8个商店，商店0表示配送中心，配送中心有两辆载重量为8吨的货车，要求合理安排车辆行驶路径，使总运输距离最小。商店之间的相互距离及各商店的商品需求量（见表1、表2）：

表1 各需求点对货物需求量 单位：吨

表2配送中心与各需求点之间的距离单位：KM

四、算法改进

在现有遗传算法中，个体的染色体编码还需要用到最优车辆数。这两种编码方案有三个缺点:（1）由于染色体维数变长，使组合空间变大，从而降低了搜索到最优解的几率。（2）由染色体解码后获得的子路径有可能不满足车辆的能力约束。（3）需要预先知道最优解所需车辆数。

为了避免上述缺点，本文提出一种新的双层染色体编码方案Double Layers Chromos Coding Shema，DLCCS）。标准遗传算法中染色体是单层的。而在DLCCS中，染色体是两层的，其构成为：第一层是n维向量L1，代表n个客户的一种排列。第二层是一个维数可变的向量L2，在L2中存放的元素代表每辆车所服务的第一个客户在Ll中的顺序号，需根据车辆的能力限制计算得出。以上节的例为例，用自然数1～8代表8个客户，其需求量分别为（1，2，1，2，1，4，2，2），车辆的能力约束为8个单位。假定某个体的第一层染色体为L1（4，l，3，7，2，6，5，8），第二层染色体的计算过程如下:（1）第一辆车编为0号车，其第一个客户为客户4，在L1中的顺序号为0，因此第二层染色体暂时为LZ（0）。编号顺序都从0开始，这便于编程实现，因为在很多编程语言中，都将数组的起始编号设为0。（2）继续让0号车服务后面的客户，直到超出车辆的能力约束，在本例中，0号车可以服务前5个客户，到第6个客户，由于违反车辆的能力约束，需派出1号车（第二辆车）。1号车所服务的第一个客户为客户6，其在Ll中的顺序号为5，将其加入LZ，第二层染色体变成L2（0，5）。（3）继续应用步骤2，直到所有的客户都得到服务为止。

设置遗传算法的种群规模为60，交叉概率为0.8，变异概率为0.05。在计算机上用MATLAB优化软件求得标准遗传算法与改进后的遗传算法结果（如表3所示）。

由表3可以看出，改进后的遗传算法比标准的遗传算法收敛性要好得多，并且在运算速度以及占用内存方面也有很大优势。

参考文献：

[1]张远昌.物流运输与配送管理[M].北京:中国纺织出版社，2004.

[2]荣耀华.传统物流与现代物流[M].北京:中国物资出版社，2007.

[3]叶耀华，陈霖，朱晓梅.一种带时间窗口和在前约束的车辆路线问题及其算法[J].系统工程理论与实践，2000，(3).

[4]程世平.物流管理[M].合肥:合肥工业大学出版社，2007.

[5]王凌.智能优化算法及其应用[M].北京:清华大学出版社，施普林格出版社，2001.

[6]邢文训，谢金星，等.现代优化计算方法:第2版[M].北京:清华大学出版社，2005.

[7]Dantizg G，Ramser J.The truck dispatching problem，Management Science，1959，(6):80-91.

[8]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社，2001:11.

[9]Holland J H.Adaption in natural and artificial systems.MIT Press，1975.[责任编辑 安世友]