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

《遗传算法基于路径优化问题应用的改进探索研究论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法基于路径优化问题应用的改进探索研究论文.freels，简称GA）是J.Holland与1975年提出的。GA是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。二、遗传算法GA是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，其两个显著性特点是隐含并行性和全局解空间搜索。它是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地

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

3、解编码。此外，称一个解的编码为一个染色体，组成编码的元素成为基因。编码的目的主要是用于优化问题的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体就组成了一个种群，形成一个可以繁衍下一代的种群。第三是染色体的结合。双亲的遗传基因之间的结合是通过编码之间的交配（crossover）达到下一代的产生。遗传算法作为一个全局性优化算法具有很大的优越性，具体体现在：（1）遗传算法适合求解那些带有多参数、多变量、多目标和

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

5、确等问题。（2）单一的遗传编码不能全面地将优化问题的约束表示出来。（3）大量研究也表明，GA存在早熟、算法参数敏感等缺点，取得良好的性能需要依赖较大的种群并对算法进行精心设计。采用遗传算法等智能优化算法来求解带能力约束的车辆路径问题（CapacitatedVehicleRoutingProblem，即CVRP），一般能在较短的计算时间内获得质量较高的近似解。三、问题描述CVRP可描述如下:配送中心有m辆货车，每辆车的能力为q；配送中心需为n个客户提供货物配送任务，每个客户的需求量为gi（i=1，2，…，n），gi有1个配送中心和8个商店，商店0表示配送中心，配送中心有两辆载重量为

6、8吨的货车，要求合理安排车辆行驶路径，使总运输距离最小。商店之间的相互距离及各商店的商品需求量（见表1、表2）：表1各需求点对货物需求量单位：吨表2配送中心与各需求点之间的距离单位：KM四、算法改进在现有遗传算法中，个体的染色体编码还需要用到最优车辆数。这两种编码方案有三个缺点:（1）由于染色体维数变长，使组合空间变大，从而降低了搜索到最优解的几率。（2）由染色体解码后获得的子路径有可能不满足车辆的能力约束。（3）需要预先知道最优解所需车辆数。为了避免上述缺点，本文提出一种新的双层染色体编码方案DoubleLayersChromosCodingShema，DLCCS）。标准遗传算

7、法中染色体是单层的。而在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号车，其第一个