遗传节约综合算法在配送路线优化中的应用（共9篇）
篇1：遗传节约综合算法在配送路线优化中的应用
遗传节约综合算法在配送路线优化中的应用
文章针对配送路线问题进行研究,首先提出配送路线优化的原则,在此基础上提出了解决配送路线问题的`遗传节约综合算法的流程和步骤,最后通过一个算例实现了本文提出的算法,并与其它方法的计算结果进行了比较,从而证实了遗传节约综合算法的优越性.
作 者：喻伟 何其超 张增 YU Wei HE Qi-chao ZHANG Zeng-qi 作者单位：长沙理工大学,湖南,长沙,410114刊 名：物流科技英文刊名：LOGISTICS SCI-TECH年，卷(期)：32(3)分类号：U116.2关键词：物流 配送路线 遗传算法 节约算法
篇2：遗传节约综合算法在配送路线优化中的应用
研究在造价、体积和重量约束条件下,多级串联系统和桥式网络系统可靠性优化问题.使用遗传算法对该问题进行求解,利用基于排名的选择方法和最优保存策略,改善了遗传算法的收敛性能.计算机仿真实验结果表明,用遗传算法求解该问题是有效的.
作 者：张铁柱 滕春贤 韩志刚 作者单位：张铁柱,滕春贤(哈尔滨理工大学,系统工程研究所,黑龙江,哈尔滨,150080)
韩志刚(黑龙江大学,应用数学研究所,黑龙江,哈尔滨,150080)
篇3：遗传节约综合算法在配送路线优化中的应用
在物流配送领域,配送成本费用是配送运输成本、分拣成本、配装成本以及流通加工成本的总和。配送运输成本是成本费用中较大开支,尤其是配送点多、路线较长时,配送路径的选择直接决定运输成本的大小。因此,在配送点及配送点需求量已知的情况下,如何通过科学的方法选择最优路径是物流配送中最关键的抉择。
车辆路径问题(Vehicle Routing Problem,简称VRP)[1],又称为车辆调度问题,通常是在配送中心及配送点之间,选择适当的路线,使车辆有序地通过,在满足一定的约束条件(如货物需求量、发送量、交货时间、车辆容量限制、行使里程限制、时间限制等)下,达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等),并返回配送中心。
配送车辆路径问题是世界公认的NP难题,国内外很多学者都进行了研究,并提出了多种路线选择及路径优化方法。Bodin(1983)等人将VRP求解方法划分为七种,分别是:先分群再派路线、先排路线再分群、节省法或插入法、改善与交换法、数学规划法、人机互动法以及最佳解法[2]。国内对配送车辆路径问题的研究,肖鹏等[3]利用单亲遗传算法解决车辆调度问题;张涛[4]等用禁忌搜索算法和遗传算法相结合的混合算法求解了不确定车辆数的VRP;方跃建等[5]用自适应遗传算法解决非满载车辆调度问题;吕雄伟[6]等采用遗传算法求解了随机需求下带时间窗的库存-运输一体化问题;宋康等[7]等提出了改进的遗传算法来解决多目标车辆路径问题;霍佳震[8]等提出了基于节约值比较的解决带有时间窗的满载车辆调度问题的节约法;张景玲[9]等用量子进化算法和改进的蚁群算法、两阶段算法相结合的混合策略对动态车辆路径问题进行了求解。
2 节约算法及改进节约算法
2.1 节约算法及其优缺点
节约算法是路径优化中的一种启发式算法。节约算法(The Savings Method)是由Clarke和Wright提出的一种经典启发式算法,该算法实现过程如下所述:
设配送中心是P0,N个零售商分别是P1,P2,P3......PN,已知任意两个节点Pi和Pj之间的最短距离为di j(i,j=0,1,2,…,N)。从配送中心为两个配送点Pi和Pj送货的路线方案有两个。一是连接这两个零售商合并送货,二是直接往返分别为两个零售商送货,前者比后者节约的运输距离为:
公式(1)就是著名的节约量公式。根据三点的位置关系,节约量Sij≥0。
节约法求解路线安排问题采用的是典型的启发式思路。首先,以所有配送点均采用直接往返的送货作为初始的可行安排。计算每两个配送点连接带来的节约量,按节约量由大到小的顺序,在初始安排的基础上进行调整:如果两个配送点连接后,所在线路的货运量之和不超过车辆的载重限制,连接这两个配送点;如果所在线路的货运量之和超过车辆的载重限制,不连接这两个配送点,转而判断节约量稍小的另两个配送点之间能否连接。直到所有可能连接的配送点全部连接完成后,得到路线安排[10]。
节约算法在速度和实现的简易性方面特别有优势,能够灵活调整算法,处理许多现实中的约束条件,是应用最广泛的一种车辆路径优化算法。但节约算法在算法上有一定的缺陷,即节约法不允许订货量分割。节约法进行调整的判断条件是连接后的订货量之和是否超过车辆载重限制,这样可能导致某条线路的车辆并未满载,但连接任何其他配送点都会超重而不能连接,这会影响路线安排结果的效率。
2.2 改进节约算法
改进节算法是在节约算法的基础上,做出一些修改,允许订货量分割,改进节约算法思路如下:
以所有配送点均采用直接往返的送货作为初始的可行安排,寻找节约量最大的两个配送点:(1)如果它们连接后,所在线路上的货运量之和不超过车辆的载重限制,连接这两个配送点;并进一步寻找与这两个配送点进行连接带来节约量最大的配送点,把这个配送点也连接到这条线路上,直到该线路上的所有配送点的货运量之和等于或超过车辆的载重限制,连接使总货运量超过车辆载重的最后一个配送点,本线路为该配送点提供的货运量刚好使车辆满载。(2)如果它们连接后,所在线路上的货运量之和等于车辆的载重限制,连接这两个配送点。(3)如果它们连接后,所在线路上的货运量之和超过车辆的载重限制,连接这两个配送点,并使车辆刚好满载。将剩余的配送点和配送向量组成一个新的配送线路规划问题,重复采用上述方法,直到所有可能连接的配送点全部连接完成后,结果作为路线安排的最优解[10]。
本文提出的算法在上述改进节约算法基础之上,提出了单位距离载重的概念,增加了一个判断条件,即:如果之前车辆未满载,增加下一节约量大的配送点后车辆刚好满载,则连接这两个配送点;如果车辆超载,则计算配送使车辆满载部分的单位距离载重,比较满载前和使车辆满载部分的单位距离载重,若满载前单位距离载重小于使车辆满载部分的单位距离载重,则连接这个配送点进行配送,使车辆满载。若满载前单位距离载重大于使车辆满载部分的单位距离载重,则放弃此配送点,车辆未满载。
其中,单位距离载重=载重量/配送距离。满载前单位距离载重=满载前的载重量/已有的配送距离;使车辆满载部分的单位距离载重=使车辆满载的剩余载重量/即将配送的距离。图1所示为改进节约算法在加入单位距离载重判断后的流程。
通过比较发现,改进的节约算法与传统的节约法有以下不同:(1)改进节约算法允许货运量分割。(2)货运量之和超过车辆的载重限制的情况下,计算单位距离载重,若满载前单位距离载重小于使车辆满载部分的单位距离载重,则连接这个配送点进行配送,直到车辆满载。若满载前单位距离载重大于使车辆满载部分的单位距离载重,则放弃此配送点。(3)连接完一条线路后,剩余的配送点和配送向量和节约量矩阵组成一个新的配送路线安排问题。
3 改进节约算法在电表配送路径优化中的应用
江苏省电力公司电力科学研究院计量中心电能表配送业务,需要按照各配送点的需求订单来决定配送数量及配送路线,由此可以看出,每个阶段的配送方案是变化的,最优配送路线随之变化,这就需要计量中心根据配送点及配送数量的变化及时制定最优配送方案,在提高配送效率的同时减少配送成本。
3.1 车辆路径优化问题的一些基本假设
在物流配送车辆调度的实际运作中,情况十分复杂,需要考虑的因素很多,影响目标优化因素变动也很大,因此为了方便建模和求解,需要对现实情况各种要素进行抽象,在一定的范围和框架内,来研究物流配送路径优化问题。结合具体工作流程和实际情况,对所研究的物流配送车辆调度问题进行如下的界定及说明:
(1)从省公司计量中心配送中心向多个配送点送货,配送中心和各配送点的位置一定。
(2)每台配送车辆的最大载重量一定,不允许超载;而且配送点有一定的工作时间范围,必须在其工作时间内进行;配送的每台车辆都是从配送中心出发,向配送点提供配送服务后,最终返回配送中心,车辆也有工作时间的限制,车辆的配送工作必须在工作时间里进行。
(3)各个配送点需求的物资可以混装,即可以装载于同一辆配送车辆内,每台车辆从配送中心出发,经过若干个配送点配送后,回到配送中心,在这个过程中,车辆所经过配送点的需求量总和不超过该车辆的最大载重量;每个配送点的送货需求必须得到满足。
(4)配送车辆在配送中心装车,在配送点所在地装卸有一定的时间成本。
(5)每辆车的行驶距离不超过预定的该车的最大行驶距离。
根据以上的界定,现研究的物流配送车辆调度问题属于单配送中心、单车型、非满载、路段旅行时间不固定、车辆封闭的车辆路径优化问题。
3.2 改进节约算法的应用
在江苏省电力公司电力科学研究院计量中心电能表配送方案中,将配送区域划分为六条线路。然而在区域内部即每条线路内部进行配送时,配送路径的长短直接决定配送成本。因此,选择最短、最合理的配送路线显得至关重要。现通过改进节约算法选择最短路径,实现配送路径的优化。
以线路“宁-镇-常-锡-苏”为例,随机选择其中9个配送点,其需求量以其8天的需求为例(配送周期为8天,需求量的量值以其与车载量的比例为需求量值,车载辆按4800只电能表计算)。算例中以线路“宁-镇-常-锡-苏”的9个配送点需求为例,各配送点及其需求量见下表:
图2所示为配送路径的初始解。可以看出,初解的线路数为9条;总里程为2082公里;车辆数为9辆。
由表3计算分析可知,常熟与无锡连接后的节约里程为319.1公里,为最大节约量,连接常熟与无锡,其货运量之和为0.96,未超出车载量,因此连接常熟与无锡。第二大节约量为259.6公里,常州的需求量为0.7,超出车载量,如果往常州配送剩余0.04,其单位距离载重为0.04*4800/99.4=1.93只/公里,远小于0.96*4800/(183+86.9)=17.07只/公里。因此,放弃常州路线,“计量中心-无锡-常熟-计量中心”构成第一条配送线路,满载率为0.96。
经第一次优化后,线路数变为8条,配送里程为1762.9公里,车辆数为8辆。将表3中常熟与无锡所在行、列删除,得到表4:
表4中最大节约里程为221.3公里,连接宜兴与常州,配载量为0.85,下一最大节约量为191.6公里,溧阳需求量为0.17,超出了车载辆。如果往溧阳配送剩余0.15,其单位距离载重为0.15*4800/44.4=16.21只/公里,小于0.85*4800/(183+50.7)=17.46只/公里,因此,放弃溧阳点的配送,配载率为0.85。因此“计量中心-常州-宜兴-计量中心”够成第二条配送线路。
经第二次优化后,线路数变为7条;总的配送里程为1541.6公里;车辆数为7辆。将表4中常州与宜兴所在行、列删除,得到表5:
表中最大节约量为137.4公里,连接溧阳与金坛,配载量为0.24。下一个最大节约量为113.9公里,连接金坛与丹阳,单个配送点总的配送量为0.32,在车载量范围内,因为每辆车配送点设置最多为3个点,因此将“计量中心-溧阳-金坛-丹阳-计量中心”最为第三条配送线路。
经第三次优化后,线路数变为5条;总的配送里程为1365.1公里;车辆数为5辆。将表5中溧阳、金坛与丹阳所在行、列删除,得到表6:
经三次优化后,9个配送点只剩溧水和句容的配送,两者配送总量为0.22,未超出配载量限制,因此“计量中心-溧水-句容-计量中心”构成第四条配送线路。
经第四次优化后,线路数变为4条,配送总里程为1344.5公里,配送车辆数为4辆。
具体配送路线图如下图所示。
本例中,由于实际因素限制,每辆车配送点规定最多为3个点,因此车辆配载率部分并未达到较高水平。但已经从初始配送距离2082公里,配送车辆数9辆优化为配送距离1344.5公里,配送车辆数4辆,大大减少了配送成本。
4 总结
改进节约算法解决了订货量分割问题,能够使车辆满载,提高运输效率,同时单位距离配载的引入也避免了为少量货物进行的不经济的运输问题,使运输路线的选择更为合理,在提高配载率的同时考虑了配载的经济性。
摘要：车辆路径问题是物流配送中的决策难题,车辆路径优化方法层出不穷,节约算法作为启发式算法,由于其简单实用性,得到了较为广泛的应用,改进节约算法提高了配载率,应用也较为广泛。文中在改进节约算法中提出了单位距离配载的概念,并在是否满载方面加以判断,使改进节约算法更为合理,更符合实际;并以江苏省电力公司电力科学研究院计量中心电能表配送业务为基础,运用改进节约算法进行路线选择。
关键词：节约算法,改进节约算法,单位距离配载
参考文献
[1]Dantzing G,Ramser J.The truck dispatching problem[J].Management Science,1959,10,(6):80-91.
[2]肖建辉.车辆路径优化文献综述[J].广东技术师范学院学报(自然科学),2010,(2):31-37.
[3]肖鹏,李茂军,张军平,叶涛.单亲遗传算法及其在物流配送系统中的应用[J].系统工程,2000,(1):64-66.
[4]张涛,王梦光,杨建夏.不确定计划数的轧制批量计划的模型和算法[J].系统工程学报,2000,15,(1):54-60.
[5]方跃建,杨春节,李平,曹柬.一种新的非满载车辆调度的遗传算法[J].江南大学学报(自然科学版),2007,(2):136-139.
[6]吕雄伟,孙斌峰,李军.随机需求下带时间窗IRP问题的遗传算法研究[J].商业研究,2008,(9):8-10.
[7]宋康,蔡延光张敏捷等.多目标车辆路径的遗传算法[J].微计算机信息,2010,26,(4):221-223.
[8]霍佳震,张磊.用节约法解决带有时间窗的满载车辆调度问题[J].工业工程与管理,2006,(4):38-42.
[9]张景玲,赵燕伟,王海燕等.多车型动态需求车辆路径问题建模及优化[J].计算机集成制造系统,2010,16(3):543-550.
篇4：遗传节约综合算法在配送路线优化中的应用
关键词：遗传算法网架结构配电网优化
1 问题的提出
配电系统中的网架结构优化问题主要有两个特点：非线性和整数性，这也正是解决问题的困难所在。用非线性规划方法解题常常会遇到搜索方向错误，迭代不收敛，逼近速度慢等问题。当变量和约束条件数目较多时，这些问题更加突出。另外，线路都是按整回和确定的电压等级来架设的，若变量取线路的某电气量，则变量应是整数值或某种离散值。对于这样的非线性整数规划问题，目前还没有理想的优化算法。若试图严格地解决这种问题，将会遇到一个典型的组合数目以指数形式增长，即所谓“组合爆炸”问题。综观以前的各种传统优化方法，各有优势，要么容易偏离最优解陷入局部最优，要么受到维数的限制而难以达到实用的目的。为了解决这两个方面的问题，下面把遗传算法引入城市电力网网架结构的优化中来，以欺得到一个较满意的解决问题的办法。
2 遗传算法介绍
遗传算法是一种搜索算法，是通过模拟自然进化过程来搜索最优解的方法。其目的是解释自然界的自适应过程而设计的一个体现自然界进化机理的软件系统。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择决定了群体中哪些个体能够存活并繁殖，即适者生存，不适者淘汰；有性生殖保证了后代基因中的混合与重组，加快了进化过程。由于该方法隐含并行性和全局信息的有效利用能力，尤其适合于处理传统搜索方法解决不了的复杂问题，近十多年來在各领域得到广泛应用。
遗传算子：一个简单的遗传算法由复制、杂交和变异三个遗传算子组成。其中复制算子是把当前群体中的个体按与适应值成正比的概率复制到新群体中去。这样，低适应值的个体趋向于被淘汰，高适应值的个体趋向于被复制，复制算子的作用效果提高了群体的平均适应值，也充分体现了“优胜劣汰”这种自然进化机制；杂交算子是模拟生物界的有性繁殖，可以产生新的个体，使其比它的两个父代有更高的适应值。杂交算子是遗传算法的重要组成部分；变异算子是用一个很小的概率随机地改变染色体串上的位置，其效果是增加群体的多样性，扩大搜索空间。
主要特点：遗传算法与传统的优化算法相比，主要体现在它不是直接作用参变量集上，而是利用参变量集的某种编码；不是从单个点，而是从一个点的群体开始搜索，因而能够快速全局收敛；它还利用了概率转移规则，而非确定性规则，因而能够搜索离散的有噪声的多峰值复杂空间；以及利用适应值信息，无须导数或辅助信息，具有广泛的适应性；在解空间内进行充分的搜索，但并不是盲目地穷举或瞎碰，因此在其搜索时间和效率上往往优于其他优化方法。首先，它在搜索过程中不容易陷入局部最优，即使在所定义的适应函数是不连续的、非规则的或有噪声情况下，它也能以很大的概率找到整体最优解。为了寻找最优解，传统方法是用启发式策略，在单个猜测解的领域寻找，即使算法中允许偶尔地跳到解空间中更远的部分，这些启发式算法也往往趋于局部最优。理论上遗传算法像撒网一样，通过保持在参变量的解空间区域中的多个点的搜索可以以很大的概率找到全局最优解。其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。由于遗传算法的操作主要是在单个位串上，至多是一对位串之间的杂交，所以可让每个处理机负责处理单个位串，从而可以并行处理整个群体。
计算步骤：在进行个体遗传算法之前，需要作好如下准备工作。首先是选择编码；一般编码选择由多个二进制串（0，1）构成，其中“0”、“1”分别表示支路不连通和连通。应注意的是编码不局限于二进制，根据对象不同也可选其他的数来编码。其次是确定适应值函数；相当于确定数学规划中的目标函数。然后在选择控制算法的参数；最后确定停止运行的准则。
3 网架结构优化的遗传算法
网络结构优化的目标函数：网络结构优化问题是基于现有网架结构，在已知水平年电源及负荷需求下，并假定变电站的扩建或新建的时间、地点和容量都已确定，决定在规划期内何时何地架设多少回输电线路，以使得线路年费用最小。这里采用考虑了贴现的线路建设投资费用和运行费用的最小年费用法，即。其中Z为方案总的线路建设投资费用，为方案第年的运行费用。
编码的选择：遗传算法是一个搜索特征串空间的过程，其目的是找到具有相对高适应值的串。在应用遗传算法求解特殊问题之前，第一步就要确定用类似于染色体的串来表示问题的办法，即染色体的编码形式。这里采用二进制编码形式，直接对待选线路进行编码，反映其是否架设，以及选用多大截面等。这种编码形式非常直观，便于规划方案和染色体之间的编码和解码。若只考虑线路架设与否，则可将各待选线路排序，然后按此顺序将每条待选线路作为染色体串中的一个基因，每个基因是一个一位的二进制数。当基因值为1时，表示其对应的待选线路被选中加入系统，当基因值为0时，则相反。但考虑到对方案进行评估时需对方案所表示的网络进行潮流分析，这样的染色体解码成规划方案时应能得到线路参数，所以需在基因中加入线路截面的信息。
城网优化遗传算法的计算过程：首先输入原始数据；其中包括网络拓扑，即节点数、已有和待架线路数、各线路的首末节点号和线路的有关参数。节点的发电出力及负荷，遗传算数本身所需参数，即群体大小、基因位数、最大遗传代数、变异率和计算适应函数时用到的有关参数等。然后形成初始方案，接着计算适应值，进行遗传操作，最后输出计算结果。
适应函数的建立：在编码方案选定以后，接着就是要确定适应函数以检测由特定位串所表示的规划方案的好坏程度，从而指引遗传操作的正常进行。适应函数应该反映电网规划的目的和要求，即要使规划方案在满足正常运行要求和安全运行要求的情况下，使电网的建设和运行费用最小。建设费用和运行费用最小的目标函数，在考虑约束条件后的增广函数数学模型为。其中为方案的年费用，为惩罚因子，为方案的约束条件。电网规划的目的是希望电网的建设和运行费用最小，为符合遗传算法最大值的特点，适应函数可表示为。其中的选取以保证为非负数为准。由的表达式可知适应函数是一个非线性的、不连续和非凸的，这对于严格的数学规划方法是难以求解的，而遗传算法则是在解码得到一个解之后才对适应函数进行计算评估的，因此对适应函数形式无任何限制，这充分显示了遗传算法的优越性。
参考文献：
[1]孙杰.基于单亲遗传算法的配电网络优化规划[D].华北电力大学（河北）.2005年.
[2]闫大威.基于遗传算法的城市中压配电网规划自动布线[D].天津大学；2005年.
篇5：遗传节约综合算法在配送路线优化中的应用
车间物流配送采用动态规划模型,总体描述为:从配送中心用多辆搬运设备向多个加工点送货,每个加工点的位置和需求量一定,每辆搬运设备的载重量一定,要求合理安排搬运设备路线,使总运距最短,并满足以下条件:
(1)每条配送路径上各加工点的需求量之和不超过搬运设备载重量;
(2)每条配送路径的长度不超过搬运设备一次配送的最大行驶距离;
(3)每个加工点的需求必须满足只能由一辆搬运设备送货。
考虑了上述车间物流配送优化问题的约束条件和优化目标后,开始建立车间物流配送优化问题的数学模型,描述如下:
假设配送中心有K辆搬运设备,每辆搬运设备的载重量为Qkk=k1,2,…,Kk,其一次配送的最大行驶距离为Dk,需要向L个加工点送货,每个加工点的需求量为qii=k1,2,…,Lk,加工点i到j的运距为dij,配送中心到各加工点的距离为d0jij=k1,2,…,Lk。再设nk为第k辆搬运设备配送的加工点数nkk=0表示未使用第k辆搬运设备k,用集合Rk表示第k条路径,其中的元素rki表示加工点rki在路径k中的顺序为i,令rk0=0表示配送中心,则可建立如下车间物流配送优化问题的数学模型:
上述模型中,式(1)为目标函数;式(2)保证每条路径上各加工点的需求量之和不超过搬运设备的载重量;式(3)保证每条配送路径的长度不超过搬运设备一次配送的最大行驶距离;式(4)表明每条路径上的加工点数不超过总加工点数;式(5)表明每个加工点都得到配送服务;式(6)为每条路径的加工点的组成;式(7)限制每个加工点仅能由一辆搬运设备送货;式(8)为当第k辆搬运设备服务的客户数≥1时,说明该辆搬运设备参加了配送,则取sign nk,,=1,当第k辆搬运设备服务的客户数<1时,表示未使用该辆搬运设备,因此取sign nk,,=0。
2 车间物流配送优化问题的遗传算法
遗传算法以群体中的所有个体为操作对象,每个个体对应研究问题的一个解。选择、交叉和变异是遗传算法的三个主要操作算子,另外还有编码方法、初期群体的确定和适应性评估等因素,针对车间物流配送优化问题的特点,构造出求解该问题的遗传算法。
(1)编码方法的确定。根据车间物流配送优化问题的特点,笔者采用了简单直观的自然数编码方法,用0表示配送中心,用1、2、…、L表示各加工点。由于在配送中心有K辆搬运设备,则最多存在K条配送路径,每条配送路径都始于配送中心,也终于配送中心。为了在编码中反映车辆配送的路径,采用了增加K-1个虚拟配送中心的方法,分别用L+1、L+2、…、L+K-1表示。这样,1、2、…、L+K-1,这L+K-1个互不重复的自然数的随机排列就构成一个个体,并对应一种配送路径方案。例如,对于一个有7个加工点,用3辆搬运设备完成配送任务的问题,则可用1、2、…、9(8、9表示配送中心),这9个自然数的随机排列,表示物流配送路径方案。如个体129638547表示的配送路径方案为:路径1:0-1-2-9,路径2:9-6-3-8,路径3:8-5-4-7-0,共有3条配送路径;个体573894216表示的配送路径方案为:路径1:0-5-7-3-8,路径2:9-4-2-1-6-0,共有2条配送路径。
(2)初始群体的确定。随机产生一种1～L+K-1,这L+K-1个互不重复的自然数的排列,即形成一个个体。设群体规模为N,则通过随机产生N个这样的个体,即形成初始群体。
(3)适应度评估。对于某个个体所对应的配送路径方案,要判定其优劣,一是要看其是否满足配送的约束条件;二是要计算其目标函数值(即各条配送路径的长度之和)。根据配送路径优化问题的特点所确定的编码方法,隐含能够满足每个加工点都得到配送服务及每个加工点仅由一辆搬运设备配送的约束条件,但不能保证满足每条路径上各加工点需求量之和不超过搬运设备载重量及每条配送路线的长度不超过搬运设备一次配送的最大行驶距离的约束条件。为此,对每个个体所对应的配送路径方案,要对各条路径逐一进行判断,看其是否满足上述两个束条件,若不满足,则将该条路径定为不可行路径,最后计算其目标函数值。对于某个个体j,设其对应的配送路径方案的不可行路径数为Mj(Mj=0表示该个体对应一个可行解),其目标函数值为Zj,则该个体的适应度Fj可用下式表示:
式中,G为对每条不可行路径的惩罚权重,可根据目标函数的取值范围取一个相对较大的正数。
(4)选择操作。将每代群体中的N个个体按适应度由大到小排列,排在第一位的个体性能最优,将它复制一个直接进入下一代,并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度,采用赌轮选择法产生。具体地说,就是首先计算上代群体中所有个体适应度的总和,∑Fj,,再计算每个个体的适应度所占的比例,Fj/∑Fj,,以此作为其被选择的概率。这样的选择方法既可保证最优个体生存至下一代,又能保证适应度较大的个体以较大的机会进入下一代。
(5)交叉操作。对通过选择操作产生的新群体,除排在第一位的最优个体外,另N-1个个体要按交叉概率Pc进行配对交叉重组。笔者采用了一种类似OX法的交叉方法,现举例说明:(1)随机在父代个体中选择一个交配区域,如两父代个体及交配区域选定为:A=47|8563|921,B=83|4691|257;(2)将B的交配区域加到A的前面,A的交配区域加到B的前面,得:A′=4691|478563921|,B′=8563|834691257|;(3)在A′、B′中自交配区域后依次删除与交配区相同的自然数,得到最终的两个个体为:A″=469178532,B″=856349127。与其他交叉方法相比,这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。
(6)变异操作。由于在选择机制中采用了保留最佳样本的方式,为保持群体内个体的多样化,采用了连续多次对换的变异技术,使个体在排列顺序上有较大变化。变异操作是以概率Pm发生的,一旦变异操作发生,则用随机方法产生交换次数J,对所需变异操作的个体的基因进行J次对换(对换基因的位置也是随机产生的)。
3 用matlab程序进行实验计算和结果分析
根据上述遗传算法编制了matlab程序,并对一个某配送中心使用2辆搬运设备对8个加工点进行送货的车间物流配送优化问题实例进行了实验计算。设搬运设备的载重量为8×103kg,每次配送的最大行驶距离为40km,配送中心与各加工点之间、各加工点相互之间的距离及各加工点的需求量见表1。根据上述实例的特点,在实验计算中采用了以下参数:群体规模取20,交叉概率和变异概率分别取0195和0105,进化代数取50,变异时基因换位次数取5,对不可行路径的惩罚权重取100km。对上述问题,利用计算机随机求解10次,得到的计算结果见表2。
从表中数据可以看出,10次运行得到的结果均优于节约法所得的结果79.5km。而且第5次还得到了该问题的最优解67.5km,其对应的配送路径方案为:路径1:0-4-7-6-0;路径2:0-2-8-5-3-1-0。可见,利进遗传算法可以方便有效地求得车间物流配送优化问题的近似最优解。
4 结论
合理确定车间物流配送是提高服务质量、降低配送成本、增加经济效益的重要手段,而采用启发式算法求解是车间物流配送优化问题重要的研究方向。因此,笔者构造了求解车间物流配送优化问题的遗传算法模型,而且实验结果也表明,遗传算法是一种性能优良的启发式搜索算法,利用该方法可以方便有效地求得物流配送路径优化问题的近似最优解。同时对解决类似的组合优化问题具有一定的参考价值。
参考文献
[1]陈国良,王煦法,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[2]姜大立,杨西龙,杜文.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,19(6):40-44.
篇6：遗传算法在GIS中的应用
关键词：GIS技术；遗传算法；地理空间问题
引言
随着GIS应用水平的不断提高，人们逐渐开始关注地理数据的模糊性、不确定性及其分析方法，显然，传统基于确定型数据分析模型已经不能有效地解答这一问题。同时，越来越多的复杂应用问题也对GIS空间分析功能提出了更高的要求。因此，把数学、计算机科学和信息科学领域的智能计算机技术引入地学研究，将模糊数学、神经网络、遗传算法等人工智能技术与GIS相结合，把不确定性的数据处理转换成可靠的、精确的知识和信息分析，把具有高度复杂性的客观世界的本质特征加以抽象和建模，以提高GIS空间数据分析和空间问题模拟的准确度。遗传算法算是其中一种较常用的方法，利用遗传算法模拟或求解地理空间问题可以解决GIS工程中的许多難题，提高GIS对非线性问题的解决能力，可以对多方面地理问题进行优化决策，最终得出较为可靠的结果。遗传算法是实现地理空间问题决策自动化的有力工具。
1.遗传算法介绍
遗传算法是根据达尔文的进化论模仿自然界生物进化得到的一种全局优化方法。与传统的搜索方法不同，遗传 算法是基于自然选择和种群基因的一种随机搜索算法[1]。
遗传算法在实现上有两种方法：一种是种群杂交，即选择一定数量的父代，不管王与后，任何两个个体都可以杂交，任何两个父代X个体杂交后产生一个相对优生的Y个体，第二代的Y个体再如同其父代一样进行杂交，一代一代地遗传下去，直至达到最优解；另一种是一王数后的杂交，在父代个体中，选择一个最优的父个体X，分别与其他的母个体Y杂交，优生子个体Y1，再在Y1中选择一个最优的个体X1作为王，丢弃不良的一个个体后，再新娶一个后Z。新王与后Z再进行杂交，一代一代进行下去，直至产生最优解。这两种方法各有其优缺点，对于选择范围较小的优化问题，种群杂交的收敛速度更快些，而对于选择范围较大的优化问题，一王数后的杂交更有利于人工控制，并且易于收敛[1]。
2.遗传算法在GIS中的应用
2.1并行遗传算法在软件可靠性优化中的应用
对于软件的可靠性优化，也就是在完全固定的资源模式之下，找出一种能够将软件的各方面性能进行更完善分配的对策，从而使得运行的系统有更高的稳定性和可靠度，为企业在生产过程中提供更高的经济利益。而遗传算法在这个过程中，能够很好地将软件运用模拟生物化的方法来进行搜索，从而优化使用方案，在解决这个问题上，遗传算法显示出了自身强大的优势[2]。
并行遗传算法是在传统遗传算法的基础上进行改进以提高其运算速度。一般而言，它通过运用迁移策略和适应度函数可以有效地抑制早熟现象，在接近收敛时能够继续优化，并获得局部最优解。
2.2混合 DNA 遗传算法在实际应急救援路径方案设计中的应用
由于 DNA 计算和遗传算法有着诸多的相似之处，将 DNA 计算引入遗传算法进行改进，提出几种新型的交叉算子和几种新型的变异算子，并通过TSP 问题验证了该算法的有效性。TSP 问题是目前研究最为广泛的组合优化问题之一，其问题复杂性方面属于 NP 难题，对于其近似算法的研究一直是一个世界性的重要课题。遗传算法解答的有效性和全局最优的概率都明显高于早期的启发性算法，因而值得探索和研究，但标准遗传算法存在收敛速度缓慢，容易早熟的问题，针对这一问题，提出了一类新的混合遗传求解该类 NP 问题。仿真结果表明，该算法能够快速收敛到问题的近似最优解，并能很好地维持种群的多样性。因此，该方法对实际应急救援路径方案的设计具有一定的参考价[3]值。
应急物资配送问题的研究是一项复杂的系统工程，通过研究多个配送点和多个需求点之间配送一次即可满足需求的情形，将应急物资指挥中心的物资发放问题转换成为了多旅行商的问题，并应用了混合 DNA 遗传算法和新提出的交叉算子和变异算子，最后通过计算机的 Matlab 软件进行仿真求出应急物资配送的最优解，同时印证本算法的合理性和可行性。但是不考虑道路约束以及应急点的时间限制性等，有待进步加强研究[3]。
2.3基于改进的遗传算法的航空运输系统的设计与实现
研究国内外航空运输业的发展历程，尤其是航空运输系统的发展历程，对主流航空运输系统的设计模式有一定的了解后重点研究配送过程中飞行路线的优化问题。飞行路线的优化是航空运输业最需要解决、优化的问题，为了有效解决飞行路线的优化，使系统适合国内用户使用习惯及行业现状。
对遗传算法进行改进，设计并实现了一个基于 B/S 结构的航空运输系统。该系统包含了前台登录、后台管理、航班信息管理、客户信息管理、发货管理、报表管理等功能。其中发货管理部分将遗传算法应用并实现到本系统上，最终给出一个合理、有效的基于遗传算法的航空运输系统。这样一个系统对于减少企业运营成本、改善经营状况有着很大的帮助[4]。
2.4基于遗传算法的动态路径优化
随着我国社会的不断发展，交通环境不断恶化，这都成为影响社会发展的消极因素。路径优化可以帮助出行者寻找出合适的行驶路径，实现交通流在整个城市路网中各路段上的最优分配，这对于解决城市交通拥挤、提高运行效率和行车安全系数、减少能源消耗以及改善交通环境等来说都具有非常积极的意义。
对路网的建立和动态路径优化算法进行了深入研究，将道路上的实时交通流信息转化为路权，并用改进的遗传算法动态地进行路径优化，建立动态路网模型。改进的遗传算法避免了车辆在行驶中进入拥挤区域，减少了车辆的排队等候时间，提高了路径优化的动态性和实时性[5]。
2.5优化遗传算法的模糊聚类在图像分割算法中的应用
图像分割是需要进度对多种像素进行对比分割，将图形中的像素进行归类分布，采用聚类的方法分析得出图形的分割阈值，这种模糊类聚的计算方法在图形分割中是一种常用的算法。将遗传算法应用到各种图形的分割计算中，对于模糊C均值 （FCM） 迭代计算，运用遗传算法，能够有效的解决这一问题。在一般的图形分割中，运用遗传算法能够提高 FCM 算法的计算速度，图形分割的有效性，但不能有效的对变异率 Pm 和交叉率Pc进行控制，不能够自行调节像素搜索和分割的结果，影响分割的准确性和结果的正确性，需要遗传算法进行优化，改变计算的约束条件，提高算法的准确性[6]。
在图像分割时，采用优化遗传算法，能够有效的对图像分割的约束条件和相关的交叉参数进行设置，通过对对 FCM图像分割算法的分析，最终得出函数的优化条件，说明了遗传算法的模糊聚类在图像分割有效性[6]。
3.总结
通过对遗传算法的研究，发现遗传算法与传统的搜索算法不同，主要表现在以下几个方面：（1）遗传算法作用于一个参数集的编码而不是参数本身，二进制和十进制是两种广泛采用的遗传算法编码方式；（2）遗传算法是一种多解并行搜索机制，使其能以较大的概率找到整体最优解；（3）遗传算法用一个适应度函数来引导搜索，因而能应用到不同的问题中而不要求该问题受到某些特殊约束，入系统的连续性和可微性等；（4）遗传算法使用随即转移规则而不是确定性的转移规则。因此，遗产算法被应用于各行各业，尤其是地理问题的空间分析中，可以解决很多传统算法无法解决的问题。
参考文献
[1] 王平刘湘南黄方. GIS空间分析原理与方法， 科学出版社， 284-323.
[2] 周政. 并行遗传算法在软件可靠性优化中的应用[J]. 华章. 2013（19）： 323.
[3] 闻玉刚. 混合DNA遗传算法及其在组合优化中的应用[D]. 辽宁科技大学， 2013.
[4] 高慶. 基于改进的遗传算法的航空运输系统的设计与实现[D]. 吉林大学， 2013.
[5] 李云. 基于遗传算法的动态路径优化[D]. 太原理工大学， 2013.
篇7：遗传节约综合算法在配送路线优化中的应用
物流配送作为一种专业化、社会化的服务模式,适应了经济一体化的需要和社会化大生产的发展,所以越来越受到人们的重视配送是物流的关键环节,配送方法的好坏直接影响物流效益。合理选择配送路径,对加快配送速度、提高服务质量、降低配送成本以及增加经济效益都有很大影响,因此建立科学、合理、高效的物流配送体系显得尤为重要,需要在物流配送的各个环节加以优化和改进。
配送路线选择问题是在配送中心的配送区域确定以后,对某个配送中心每次配送的要求所制定的配送路线的选择方案.模型建立的原则是使得确定的配送路线总费用最低。求解物流配送路径优化问题的方法有很多,常用的有旅行商法、动态规划法、节约法、扫描法、分区配送法、方案评价法等。这些方法的缺点是当问题的规模较大时,很难得到全局最优解或满意解,而且随着问题规模的增大,算法的计算时间将以指数速度增加。因此研究的重点就转移到各种启发式算法上。
本文将在串行模拟退火的基础上使用多线程(Multithreading)并行求解物流配送的最短路径———MTSA。
2 物流配送的基本模型
选择最优配送路线的问题可以描述如下:设有n个配送点,用数码1,…,n代表。配送点i和配送点j之间的距离为d(i,j),i,j=1,…,n。要找遍访每个配送点恰好一次的一条回路,且其路径总长度为最短,这条回路就是最优的配送路线.求解最优配送路线的模拟退火算法模型可描述如下:
解空间:解空间S是遍访每个配送点恰好一次的所有回路,是{1,…,n}的所有循环排列的集合,S中的成员记为(X1,X2,…,Xn,并记Xn+1=X1。初始解可选为(1,…,n)。
新解的产生:新路径的产生:随机产生1和n之间的两相异数k和m,不妨假设k
变为新路径:(X1,X2,…,Xm,Xk+1,…,Xk,Xm+1,…,Xn)上述变换方法就是将k和m对应的两个配送点在路径序列中交换位置,称为2-opt映射。
目标函数:目标函数为访问访问所有配送点的路径总长度或称为代价函数,其值最小:
3 标准模拟退火算法实现过程
(1)初始化:初始温度T(T为足够大),初始解状态S,每个T值的迭代次数L;
(2)对k=1,2,…,L作(3)～(6)步;
(3)对当前状态S随机扰动产生一个新解S';
(4)计算增量Δt'=C(S')-C(S),其中C(S)为评价函数;
(5)若Δt'<0,则接受S'作为新的当前解,否则以概率exp(-Δt'/T)接受S'作为新的当前解;
(6)如果满足终止条件,则输出当前解作为最优解,结束程序。终止条件通常取为连续;
若干个新解都没有被接受时终止算法;
(7)T逐渐减少,且T→0,然后转第(2)步。
以上步骤称为Metropolis过程。按照一定的退火方案逐步降低温度,重复Metropolis过程,就构成了模拟退火优化算法。当系统温度足够低时,可认为达到了全局最优状态。
4 基于多线程的模拟退火算法方法
标准模拟退火算法求解最优路径的算法比较耗时,很难在短时间内就求出最优解。主要体现在温度的控制以及迭代次数的设置。例如初始温度高,则算法搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。从模拟退火的原理可以知道,是否接收新解是与上次解以及当前温度有关,这些决定了标注的模拟退火是一个串行方式,不可能采用并行的方式;故在适当的降低初始温度,减少迭代次数,而又不影响搜索全局最优解,采用多线程方式(MT-SA),在同一台服务器上,同时执行多个串行模拟退火,达到并行搜索运行的效果。
4.1 MTSA算法过程
Step 1:根据配送点的数目确定线程数目,取threadCount=(int)n/10;启动线程;
Step 2:每一线程启动一个完成的串行模拟退火过程。
(1)初始化:初始温度T(T为足够大),初始解状态S,每个T值的迭代次数L;
(2)k=1,2,…,L作(3)～(6)步;
(3)对当前状态S随机扰动产生一个新解S';
(4)计算增量Δt'=C(S')-C(S),其中C(S)为评价函数;
(5)若Δt'<0,则接受S'作为新的当前解,否则以概率exp(-Δt'/T)接受S'作为新的当前解;
(6)如果满足终止条件,则输出当前解作为最优解,结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法;
(7)T逐渐减少,且T→0,然后转第(2)步。
Step 3:比较计算每个线程最终搜索到的最优解,得到该次的全局最优解。
4.2 MTSA算法流程图
图1为MTSA算法流程图。
5 算法应用
根据本算法步骤,采用J2SE1.6分别编写了标准模拟退火算法以及基于多线程模拟退火算法的配送路线求解程序,并随机生成了10个和51个、99个配送点作为实验对象。线程数目threadCount=配送点数目除以10取整;初始温度T0=20*(配送点数目*(配送点之间距离最大值-配送点之间距离最小值))[12];迭代次数Iterative=配送点数目*配送点数目*10;计算结果见表1。
6 结束语
物流配送中,配送路线的选择对于企业配送车辆的调度是非常重要的,优化的配送路线能够最大程度的提高车辆利用率,降低运输成本,提高配送效率,是企业利润的源泉之一。本文在传统模拟退火方法的基础上采用基于多线程模式,它的优点主要表现在传统的串行搜索模式转变为并行模式,即在同一台服务器上,同时进行多个串行模拟退火算法,达到更高的搜索效率,同时也避免在初始温度不够高的情况下陷入局部收敛,提高整体的搜索效率。但是过多的线程会使整台机子的性能急速下降,这样采用分布式并行模拟退火可能更好的处理这个问题。
参考文献
[1]王之泰.现代物流学[M].北京:中国地质出版社,2003.
[2]刘凯.现代物流技术基础[M].北京:清华大学出版社,北京交通大学出版社,2004.
[3]王丰元,潘福全.基于交通限制的路网最优路径算法[J].交通运输工程学报,2005(1):92-95.
[4]高国华,沈林成,常文森.求解TSP的空间锐化模拟退火算法[J].自动化学报,1999,25(3):425-428.
[5]高尚.求解旅行商问题的模拟退火算法[J].华东船舶工业学院学报,2003,17(3):13-16.
[6]张霖斌,姚振兴,纪晨,等.快速模拟退火算法及其应用[J].石油地球物理勘探,1997,32(5):654-660.
[7]张德富,顾卫刚,沈平.一种解旅行商问题的并行模拟退火算法[J].计算机研究与发展,1995,32(2):1-4.
篇8：遗传节约综合算法在配送路线优化中的应用
关 键 词：MOS器件；模型参数；参数提取；器件模型
1 引言
器件的模型和模型参数提取是电子设计自动化（EDA）领域的关键工作[1]。采用遗传算法进行半导体器件模型参数提取是近年来兴起并被广泛使用的一种参数提取方法[2-3]。遗传算法全局搜索能力强、不需进行繁琐的求导运算，不依赖参数初始值等特点，理论上来说只要有足够的迭代次数种能找到最优解[4]。但是，由于遗传算法是一种搜索类算法,较之传统的基于梯度进行迭代计算的解析算法, 每进行一次迭代所需要的时间较长，计算量有了显著增加, 而且对许多复杂问题而言，例如采用的全局优化策略提取复杂模型的大量参数时，标准遗传算法的求解效果往往不是解决这个问题的最有效的方法，必须对算法进行修改与优化，这些因素无疑大大增加了遗传算法的计算量，为此必须考虑算法的耗时问题。本文针对遗传算法自身的耗时问题，讨论了并行遗传算法的特点，并以主从式遗传算法为例，证实了并行计算在参数提取工作中的可行性。
2 并行遗传算法
为了有效的解决遗传算法（GA）在模型参数提取过程中的耗时问题, 提高GA的运行速度，采用并行遗传算法（PGA）是提高搜索效率的方法之一。并行遗传算法[5-6]主要有主从式并行遗传算法、粗粒度并行遗传算法和细粒度并行遗传算法。
2.1 全局PGA模型－主从式模型（master-slave model）
如图1所示，主从式模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器。
主从式模型的优点是简单，保留了串行GA 的搜索行为，对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。如果适应度估值操作比其他遗传算子计算量大的多时，这是一种非常有效的并行化方法。
2.2 粗粒度PGA模型－分布式模型（distributed model）
该模型又称分布式、MIMD、岛屿模式遗传算法模型。在处理器个数较少的情况下，我们可以将群体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器，让它们相互独立地并行执行进化。为了防止子群体早熟，每经过一定的间隔(即若干进化代)，各子群体间会交换部分个体以引入其他子群体的优秀基因，丰富各子群体的多样性。除了基本的遗传算子外，粗粒度模型引入了“迁移”算子，负责管理区域之间的个体交换。如图2所示，通常存在两种迁移实现:岛屿模型、踏脚石模型。
2.3 细粒度PGA模型－分散型 (fine-grained model)
细粒度模型又称为邻域模型(neighborhood model)或细胞模型(cellular model)模型。如果并行计算机系统的规模很大，理想情况下处理器多到可以与染色体一一对应，则我们可以将每个个体分配一个处理器，让它们相互独立地并行执行进化，这样就能获得并行遗传算法的最大可能的并发性。如图3所示，在细粒度模型中，通常处理器被连接成平面网格(grid)，每个处理器上仅分配一个个体，选择和交叉只在网格中相邻个体之间进行，所以网格上的邻域关系就限定了个体空间上的关系。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广。
3 基于MPI的主从式遗传算法的的实现
3.1 总体构想
我们采用的主从式并行模型分为一个主处理器(master)和若干个从处理器(slaves)。主处理器监控整个染色体种群，并基于全局统计执行选择等全局操作；从处理器接收来自主处理器的个体进行适应度评估等局部操作，再把计算结果传给主处理器，其个体的分配过程是这样的：假设种群规模为N, 优化模型参数变量个数为M。适应度评估时，程序传给评价函数N个长度为M的向量。并行的任务是master处理器将这个N个长度为M的向量平均分配到各slaves处理器做适应度计算，计算结束后，评价函数返回N个适应度给master处理器。计算各处理器分得的染色体个数的方法是，首先计算出每个处理器至少分配到的染色体个数为AveNum=N/Size，如果处理器个数不能整除行数，这样将有部分处理器分得到（AveNum+1）个染色体，规定多余的染色体分配到编号小的处理器上。
3.2 并行中的消息传递机制
另外，需要注意的是，仅仅依靠例如C，C++，java等编程语言所编写的程序是无法实现上面叙述的染色体在各处理器之间的传递任务。因为，在并行计算环境中，每个进程均有自己独立的地址空间，一个进程不能直接访问其它进程中的数据，因而，在进行并行计算的任务之间进行的数据传输必须通过消息传递机制。消息传递机制，是指用户必须显式地通过发送和接收消息来实现处理器之间的数据交换。
本文采用的是MPI(Massage Passage Interface)消息传递接口。MPI是一个很好的数据传递软件平台，可以通过调用MPI库函数来进行进程调度以及任务间的通信。它实际上是一个消息传递函数库的标准说明，吸取了众多消息传递系统的优点，是目前国际上最流行的并行编程环境之一，其特点是通用性强(只要求网络支持TCP/IP网络协议)、系统规模小、技术比较成熟。本文通过调用MPI的库程序来达到程序员所要达到的并行目的，使异构的计算机群体作为一个紧凑、灵活、经济的计算机资源来使用的并行环境。
3.3 共享内存多处理器主从式并行环境搭建
全局并行化模型并不限定计算机体系结构，它可以在共享内存和分布式内存计算机中高效实现。现在简单介绍一下两种并行编程的方法：分布式内存方法和共享式内存方法。
对于分布式内存的并行计算机，各个处理器拥有自己独立的局部存储器，不存在公用的存储单元，显然，这种方法的问题就产生于分布式内存的组织。由于每个节点都只能访问自己的内存，如果其他节点需要访问这些内存中的数据，就必须对这些数据结构进行复制并通过网络进行传送，这会导致大量的网络负载。他的优点是拥有很好的扩展性，有利于快速构造超大型的计算系统。
在共享内存多处理器计算机中构成并行环境，在共享式内存方法中，内存对于所有的处理器来说都是通用的。这种方法并没有分布式内存方法中所提到的那些问题。而且对于这种系统进行编程要简单很多，因为所有的数据对于所有的处理器来说都是可以使用的，这与串行程序并没有太多区别。这些系统的一个大问题是扩展性差，不容易添加其他处理器。
为了在微机环境下使用MPI构成分布式内存并行环境，只要将PC机联接局域网，然后在每台PC机上安装相应操作系统，并安装MPI软件包即可。分布式内存即种群被一个处理器存储。这个主处理器负责将个体发送给其它从处理器进行评估，并收集计算结果，进行遗传操作来生成下一代。
对于本文所采用的在共享内存多处理器计算机中构成主从式并行环境就更为简单，只要在PC机上安装操作系统（本文安装linux操作系统）和MPI软件包就可以实现并行环境了。在共享内存多处理器计算机中，种群可以保存在共享内存中，每个处理器可以读取被分配到的个体信息并将适应度写回，不会有任何冲突。
4 实验结果分析
将以上方法实现的基于MPI的主从式遗传算法应用于1.2um SOI MOS器件的阈值电压模型参数提取工作中。如图4所示，实验结果表明曲线拟合的效果很好，转移特性曲线最大误差都低于5%。采用并行计算后，参数提取的速度提高了接近2.5倍。
5 结论
从实际的测试效果来看，以上方法实现的程序的简洁有效，智能化程度很高，且具有较高的精确度。因此，本文提出的基于MPI的主从式遗传算法可以解决遗传算法在器件参数提取过程中的耗时问题。该方法简单易用，适合推广使用。
参考文献
[1] J.Liou A,Analysis and Design of MOSFETS: Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.
[2] Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.
[3] Yang P, Chatterjee P K, An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.
[4] Li Yiming. An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4): 1309-1321.
[5] 康立山，非数值并行算法(第一册)-并行遗传算法[M].科学出版社,2003.
篇9：遗传节约综合算法在配送路线优化中的应用
关键词：遗传算法,物流配送,车辆路径优化
随着物流业的快速发展,如何降低成本消耗,提高企业效益成了众多物流配送企业面临的问题。国内外众多学者已经开始配送系统的优化研究,研究主要集中在配送设施选址、配送路线优化等方面,但涉及从多目标的角度进行配送活动优化研究的方法甚少。
物流配送车辆路径问题(Vehicle Routing Problem,VRP),最早是由Dantzig 和Ramser于1959年首次提出的[1]。该问题的研究目标是对一系列的客户需求点设计适当的路线,使得每个客户都能被服务一次,同时在满足一定的约束条件下,达到一定的优化目标。由于物流配送要求在车辆容量和里程的限制下,要达到车辆总里程短,车辆利用率高等特点,因此,物流配送车辆路径优化问题是一个多目标约束优化问题。
国内外用于解决优化的方法主要分为以下四类:精确算法、启发式算法、模拟方法和交互优化法[2]。其中,启发式算法中免疫遗传算法具有寻优能力强,而且具有自调节和自记忆等优点,近年来,被广泛用来求解VRP问题,在工程上也得到了迅速的应用推广,但在应用中还避免了免疫遗传算法的早熟、收敛速度慢等缺点。
基于此,提出了一种基于自适应免疫遗传算法(Adaptive Immune Genetic Algorithm,AIGA)和并列选择法的多目标物流配送车辆路径优化方案。
1 AIGA在多目标物流配送路径优化
免疫遗传算法[4,5]在传统遗传算法基础上增加抗原识别,记忆功能和调节功能,通过细胞分裂和分化作用,免疫系统可产生大量的抗体抵御各种抗原,同时免疫系统具有维持免疫平衡的机制,通过对抗体的抑制和促进作用,能自我调节产生适当数量的必要抗体。
本文,引入一种新的免疫疫苗选择策略和免疫操作方法下提出自适应免疫遗传算法(AIGA),兼顾了搜索速度,全局搜索能力和局部搜索能力。
1.1 抗体编码及种群初始化
设物流中心有k台配送车辆,每台车的载重为Qk(k=1,2,...,k),向L位客户送货。客户i的需求为qi(i=1,2,…,L), nk为第k台车辆配送的客户数 (nk=0表示未使用第k台车辆)。集合Rk表示第k条路径其中元素rk表示客户rk在路径k中的顺序为i(不含物流中心)。
针对多目标路径优化(MVRP)问题,选择自然数编码方式解决MVRP问题。每一个基因位由一个自然数代表一个客户点, 在初始化种群时,通过随机方法产生符合规定的初始种群的数量,并每当一辆汽车装满时换下一辆汽车,即满足
1.2 适应度函数选择及多目标优化
采用权重变换法对三个子目标函数线性加权,作为疫苗选择的评价函数,设配送总里程的权重为α,配送车辆数的权重为β,配送车辆总利用率的权重为γ ,α,β,γ的取值视各权重对具体问题的影响程度而定,且满足α+β+γ=1,个体适应度
并列选择法[7]解决多目标优化问题, 如图1所示。
1.3 遗传算子
1.3.1 选择算子
采用的是轮盘赌策略选择法[6]。
1.3.2 交叉算子
采用改进型顺序交叉方法对个体进行交叉,在双亲染色体上生成两个随机点i,j,将i与j之间的区域作为交换区,将对方交换区内的子串加到自身染色体前面作为前缀,然后删除染色体中与前缀相同的基因序号,即交叉完成。
1.3.3 变异算子
随机在选中变异的个体X=(x1,x2,…,xi,…,xj,…,xn)上生成两个随机点i和j,用以xi为起点和xj为终点的另一条路径代替原先xi与xj之间的路径,同时为了避免出现环路,应将变异后染色体中可能产生的重复基因位予以消除,保证了新个体的可行性,同时为了保持种群多样性,设计出如下自适应变异率
式(4)中t表示当前代数;pm表示预先设定的突变率,一般取值0.01到0.1之间;f(t-1)表示上一代种群的最佳适应度值;f(t)表示当代种群的最佳适应度值;ne表示自上次进化以来至当前代为止连续未进化的代数,即当f(t-1)=f(t)时,ne=ne+1。
1.4 AIGA疫苗的选取
由于适应度相同或相差不大的个体其包含的模式可能相差极大,一般情况下,仅选择当代最优个体作为疫苗,在对种群进化方向进行指导的同时,会以较大的概率带来误导作用,易使种群搜索陷入局部最优解。针对其不足,提出选取当代种群中两个较优个体作为注射疫苗,可以使得接种后的个体即抗体包含有用的模式,使其向优良个体的方向靠拢,对搜索具有一定的指导作用,从而能够加快收敛速度,有效抑制由于单个疫苗带来的误差作用,为抗体的进化提供多个方向,具体步骤如下:
(1) 计算种群X(t)=(x1(t),x2(t),…,xn(t))中个体xi(t)的适应度f(xi(t));
(2) 令X(t)中最优个体的下标为k1,即f[xk1(t)]取得最大值;
(3) 遍历整个种群X(t),令p=f[xk1(t)]-f[xi(t)],记使p的值取得最小且不为0的个体下标为k2,则xk2(t)为种群X(t)中的次优解;
(4) 选取xk1(t)和xk2(t)为两个疫苗。
1.5 AIGA免疫操作[7]
免疫操作将选出的优良疫苗对种群中的个体进行接种,以增强种群的整体性能,分为全免疫和目标免疫。本文选用目标免疫,即考虑局部最佳调整,在某一处或几处发生免疫反应。
1.5.1 接种个体的选择
对种群X(t)中的个体适应度f[xi(t)]排序,计算种群平均适应度
1.5.2 接种个体数和接种点数的选择
接种个体数
式(5)中,t表示当前代数,N表示当前代种群的个体数。
接种点数:
式(6)中,t表示当前代数,L表示个体编码长度,显然式(5)和式(6)都满足自适应的要求,都能随着进化代数的变化而变化。
1.5.3 接种后抗体的选择方法
1.4节中选取了xk1(t)和xk2(t)为两个疫苗,设选取的待接种个体为xm(t),通过在接种点的周围选取路径最近的点注入疫苗, 接种后产生两个抗体分别为xmk0(t)和xmk1(t),取f[xm(t)],f[xmk0(t)],f[xmk1(t)]中大者为抗体。
2 AIGA在VRP多目标优化中的实现过程
AIGA算法步骤如下:
(1) 取进化代数t=1,按照1.1节中的方法产生初始种群,并输入控制参数( 交叉概率Pc,变异概率Pv,群体规模N,最大运行代数G等等),算法的终止条件是进化代数等于最大运行代数;
(2) 计算个体适应度;并按轮盘赌策略选择M个个体;
(3) 对选中的个体M个个体按照1.3节中的交叉和变异方法进行交叉和变异操作;
(4) 按1.4节中的疫苗选取方法选取两个疫苗,按式(5)和式(6)选取待接种个体数和接种点数进行免疫操作,并做出接种后的免疫选择,同时,对接种后的种群采用最优个体保留策略;
(5) t<G,t=t+l,否则转步骤(2);否则算法终止,并输出优化结果。
AIGA在VRP多目标优化中流程图如图2。
3 实例分析
windowsxp操作系统下,使用visual C++6.0实现对自适应免疫遗传算法在多目标物流配送路径优化的仿真实验,证明该算法在路径优化中是高效而稳定的。客户点距离及各客户点的需求量见表1,自适应免疫遗传算法(IAGA)与免疫遗传算法(IGA)的结果见表2,图3显示了自适应免疫遗传算法与免疫遗传算法的结果对比。
实验结果计算得出最优路径为:0—2—8—5—3—1—0;0—4—7—6—0。实验采用的参数为:最大进化代数G=100,种群规模N=30,交叉概率=0.95,变异概率=0.05,适应度权重因子α=β=γ=1/3。从图3中可以清晰地看出AIGA的优势,不仅高效地收敛到最优解,而且精细度比IGA也要更好。
4 结论
通过研究将自适应免疫遗传算法与多目标并列选择法相结合, 引入一种新的免疫疫苗选择策略和免疫操作方法,使得优化过程随进化代数自适应改变,从而求解多目标物流配送路径优化问题,对比自适应免疫遗传算法与一般免疫遗传算法的求解结果,得到如下结论:自适应免疫遗传算法实现了复杂物流配送的路径优化处理,可以较好地改变原免疫遗传算法的全局搜索性能,大大提高了算法收敛速度,能够在实际应用中取得良好效果。
参考文献
[1] Danting R.The truck dispatching problem.Mgt Sci,1959;(6):81—89
[2]高鹏.物流配送线路优化的改进遗传算法研究.交通运输系统工程与信息,2006;(6):
[3]尚华艳.物流配送中车辆路径问题研究.武汉理工大学硕士学位论文,2005:29—30
[4]刘敬宇.改进自适应遗传模拟退火算法的结构优化设计[J].徐州工程学院学报(自然科学版),2011;26(2):14—17
[5] Jiao L C,Wang L.A novel genetic algorithm based on immuni-ty.IEEE Trans on System,Man,and Cybernetics,Part A:Systemsand Humans,2000;30(5):552—561
[6]雷英杰,张善文,等.MATLABA遗传算法工具箱及应用.西安:西安电子科技大学出版社,2005:31—33
[7]巩敦卫,潘凤萍.自适应遗传算法理论及应用.徐州:中国矿业大学出版社,120—125
【遗传节约综合算法在配送路线优化中的应用】相关文章：
遗传算法在水利土木工程中的应用09-11
遗传算法在高校排课系统中的应用研究09-11
应用遗传算法的齿轮传动优化设计09-11
遗传算法在面试问题方面的应用12-14
基于遗传算法的优化设计论文04-28
遗传算法原理和应用05-16
应用遗传算法求解约束P-中值问题09-10