遗传算法基于路径优化问题应用的改进探索研究
来源:用户上传
作者: 张立营
摘要：遗传算法是一种应用很广泛的智能优化算法，对遗传算法进行了分析研究，针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上，基于遗传算法，研究了物流系统中的库存优化问题及车辆路径问题。将车辆路径问题看做是组合优化问题，并应用遗传算法进行求解。
关键词：路径优化；遗传算法；禁忌搜索算法
中图分类号：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
转载注明来源:https://www.xzbu.com/2/view-395002.htm
