人工智能与模式识别论文文档格式.doc
- 文档编号:340380
- 上传时间:2023-04-28
- 格式:DOC
- 页数:13
- 大小:62.50KB
人工智能与模式识别论文文档格式.doc
《人工智能与模式识别论文文档格式.doc》由会员分享,可在线阅读,更多相关《人工智能与模式识别论文文档格式.doc(13页珍藏版)》请在冰点文库上搜索。
物流配送;
路径优化;
蚁群算法;
蚁群系统
Applicationofantcolonyalgorithmanditsresearchinlogisticsandimprovedalgorithm
Abstract:
Thisarticledescribestheantcolonyalgorithmanddistributionofrelevantbackgroundtooptimizethecharacteristicsoftheproblemaccordingtothedistributionpath,pathalgorithmisproposedbasedontheantcolonyoptimizationalgorithm.Thealgorithmbyintroducinggeneticoperators,thelocalsearchprocesscanavoidprematurity,stagnation,whileimprovingthewaypheromoneupdate,customerspointselectionstrategiestoenhancethepositivefeedbackeffectofantcolonyalgorithmtoimprovetheconvergencespeedandglobalsearchcapability.
Keywords:
logisticdistribution;
optimizingrouting;
antcolonyalgorithm(ACA);
antsystem(AS)
1.研究背景
在经济全球化快速发展的进程中,物流作为“第三利润源”对经济活动的影响越来越强,而它作为当前经济最重要的竞争领域,在优化国内外两个市场的资源配置中起着尤为重要的作用。
随着电子商务的发展,出现了一些新的配送模式,使得储存不再是必然的环节,国外有巨头如ebay,国内也有阿里巴巴这样的电子商务帝国,他们的崛起,彻底改变了人们的生活方式。
而电子商务的发展,离不开物流配送行业的快速发展。
物流配送在美国、日本和西欧发展较快,已经形成了比较成熟的理论体系,不论是硬件方面还是软件方面都达到了相当高的水准。
近年来,国内配送业务也得到了长足发展,并形成了自身的特点
2.物流综述
2.1物流的概念
物流(Logistic)就是由货物的运输、贮藏、装卸、搬运、流通加工、配送、情报处理等一系列功能所组成的一个行业或者部门。
物流是一个跨部门的交叉行业,涉及面非常的广,其他行业的发展也会对物流业产生正面或者负面的影响。
物流业的具体策略设计工作包括:
(1)企业物流的诊断和分析,包括物流成本、物流流程、物流资源配置、人力资源配置以及物流职能机构设置等的诊断和分析。
(2)企业物流策略的分析和设计,包括物流供应链和物流运作模式的分析和重新设计。
(3)企业全面物流设计,包括资源整合、物流流程优化、物流管理、资源配置、物流技术、电子化物流等的规划和设计。
(4)企业物流实施策略的规划和设计,包括企业物流网络管理、总仓和异地仓储管理、运输管理、库存控制、成本和风险控制、物流实施指标、评估等物流实施过程中实施手段和物流各环节的规划和设计。
2.2供应链与物流供应链
一般认为,供应链是物流、信息流、资金流三个流的统一,物流贯穿供应链的全过程,从供应商到核心企业的供应物流,核心企业的内部物流,再到分销商与最终客户的分销物流,以及伴随而生的废弃物物流、回收物流等,形成了以核心企业为集散中心的物流体系。
物流连接供应链的各个企业,是企业间相互合作的纽带。
供应链物流的特点可以用如下几个术语简要概括:
信息共享;
过程同步;
合作互利;
交货淮时;
响应敏捷;
服务满意。
而物流是供应链管理体系的重要组成部分,供应链的其他两个部分对物流起着指导和启发作用。
2.3国内外物流学的发展状况
2.3.1国外物流发展概况
国外对于物流学的研究历史要比国内起步早很多,至少已有70余年的历史。
但是物流的发展和经济的发展也是密切相关,当一个行业基本没有什么大的利润可以实现的时候,关于该行业的研究仅仅是浮于纸上。
直到本世纪70年代以后,物流业突然随着各种相关行业的发展而受到越来越多的关注。
很多新的名词出现:
MRP(物流需求计划)、MRPn(制造资源计划)、ERP(企业资源计划)等;
但是成功的依然不多,最主要是受到通信能力的限制。
但是时间到今天,我国物流业刚刚正式起步的同时,信息产业的巨大发展使得人们可以在任何地方得到需要的信息,物流业的最后一个客观障碍被扫除了。
有些大型的物流企业,例如沃尔玛公司甚至拥有自己的商业通讯卫星。
虽然国外的物流业发展比国内早,但是由于客观因素的制约,正好使我国搭上了国际物流业迅猛发展的末班车。
国际上第三方物流业有20年历史,虽然它是处在成长成熟期的年轻行业,但在国民经济中己起着相当重要的作用。
据统计,1997一2000年,世界500强企业对第三方物流的需求由40%增加到了56%。
在欧洲的物流服务市场,2002年约有28%由第三方物流完成。
其中,德国99%的运输业务和50%以上的仓储业务交给了第三方物流。
通过第三方,德国物流成本可以下降到商品总成本的10%。
英国的第三方物流,在商业领域己从货物配送发展到店内物流。
美国从1990年出现第三方物流后,2000年的市场规模约600美元,前20名第三方物流服务企业净收入达到93.4亿美元,被称作玫瑰色的新产业。
日本在近20年内,物流业每增长.26%,经济总量就增加1%[1]。
自1996年开始,日本开始出现第三方物流公司,而且有众多公司己成为或表示要成为第三方服务提供者。
纵观国际上第三方物流发展的特点,基本上的做法是首先由政府制定各种物流相关的法律法规,例如日本政府制定的《仓库法》、《综合物流实施大纲》等等;
在游戏规则确定之后,第三方物流部门一方面加强自身的管理建设,降低成本,另一方面不断拓展服务内容,提高服务质量。
例如德国物流正在提出“五星级货物旅馆”的口号,实际上是对物流中心的管理和运作提出更高的要求。
物流中心的货物配送应该做到加工更方便、物审更快捷、服务更周到、运作成本更低,这样才能吸引更多的客户。
2.3.2国内物流发展概况
人尽其才,物尽其流。
物流学在我国的兴起是上世纪70年代末,政府和企业都为我国物流业的发展倾注了很多的心血和精力,但是几十年过去了,不但第三方物流没有出现,作为试点的配送站最后也名存实亡。
直到90年代中期,随着经济的发展,第三方物流业却悄悄从我国沿海地区自发的发展起来,直到今日,形成了一股“第三方物流热”。
今天作为与能源、信息流并列的物流,己经被看成是继资源、劳动力之后的第三利润源泉,在国民经济中正发挥着重要作用。
中国物流学会的前身是1980年成立的中国物资经济学会和1984年成立的中国物流研究会。
1984年8月,中国物流研究会第一次学术会议在北京召开,大会收到各地提交的论文150多篇。
1995年,中国物资流通协会成立。
协会是行业组织,学会是学术组织,协会和学会利用各自优势,在物流领域做了大量工作,对中国物流的理论研究与实际推动做出了新的贡献。
从1999年下半年开始第三方物流配送系统在中国得到了较快发展。
我国己经初步具备了发展物流管理和配送技术的经济环境和市场条件。
初步形成了供求平衡或供过于求的买方市场格局。
同时现代物流管理和配送体系中的先进理念和技术,由西方开始进入并得到越来越广泛的应用。
全球经济一体以及产品融合趋势的加强,使企业从传统对单纯仓储、运输的需求开始发展到综合物流服务。
人们消费观念的变化,使传统商业由原来的店式经营逐渐向无柜台、无铺面经营方式转变,出现多种新型商业形态,客观上促进了物流的发展,例如2003年中国电子商务的市场规模达到近9.9万【2】亿美元,就为物流创造了巨大的市场。
我国的第三方物流尚处于初级阶段,国际流行的物流网络设计、预测、存订货管理等服务只有少数企业才能提供。
第三方物流在日本占总物流量的80%,美国57%,我国只占18%【3】。
所以第三方物流是我国现阶段物流行业的发展重点。
2.4物流所面对的实践难题
从前面的分析看出,当前物流业所涉及的领域是广泛的,遍及管理学、经济学、运筹学、数学、信息学、计算机科学等多个学科的内容。
但是如果从最实际的角度出发,就是要完成两个大的目标1.降低成本;
2.满足客户需求。
换句话说,就是在满足某些“约束条件”的基础上实现“最节约成本”的配送方案。
物流业的最主要成本投入就是两大块,一块是前期投入,就是建立仓库、配送中心,安排配送工具,如卡车;
另一大块就是实际运行中的管理和配送消耗。
2.4.1物流配送路径寻优问题
思考前面叙述的物流业长期发展所形成的一些通用经验,发现物流配送的一个重要目标就是要在满足客户要求(一般是时间)的前提下,能够投入最少的配送成本(主要是各种运输线路上的损耗)。
在网络化的今天,由于信息流通便捷,各部门协同工作的能力越来越强,实现诸如“整合运输”、“最低库存”、“快速反应”的客观条件越来越充实;
因此,如何充分利用现有条件,达到物流配送的最小成本消耗已经成为一个越来越受到重视的问题。
特别是“整合运输”等一系列新的货物运输概念的提出,更使得原来的单线的,仓库一>
单个客户一>
仓库的配送模式被完全推翻,取而代之的是每个运输单位运输不同的货物到不同的客户手中;
而不是像往常那样,每个配送单位分配单名客户,把货物运到客户手中就立即返回,造成路程上的大量浪费。
这一问题可以描述为:
如何选择最优配送路
径,使得投入的运输成本最低,又能满足客户的要求。
实际上,由于客户数 目的巨大,这一问题的可行解数目非常巨大,甚至不可能用类似于枚举法 的方法在能够接受的时间范围内得到最优解或者较优解,因此该问题已 经成为一个公认的物流难题。
2.4.2物流配送其他问题
前期的资金投入,最大的成本投资就是配送中心的建设;
一组好的配送中心,应该能够对各种因素对将来物流配送造成的影响作好综合的考虑和权衡。
事实上,这样的因素非常多,例如:
城市和城区的政策、文化经济氛围、各类市场的位置、劳动力供给和成本、能源通讯状况、企业的目标、税收、公共设施的成本和供应、环境管理政策、优惠鼓励性政策、离中心仓库和潜在客户的距离、土地及其建设成本、铁路,公路水上运输条件和能力、供应设施的位置、环境气候条件等等。
这些因素不但数量众多,而且很多还是互相矛盾,关系复杂。
因此,物流配送中心的选址和建设问题是一个需要综合考虑的难题。
物流配送所面对的实际情况是复杂的,货物的流动方向也很可能是随机的,或者互逆的,如何处理这方面的关系也是物流将面对的一个实际问题。
同样,随着配送中心的不断涌现、物流配送的基础设施的不断完备,更为灵活的全局性的多级或者网形配送方式不断被采用。
与此同时,物流配送问题的复杂度也大大增加。
3.物流配送的优化问题以及蚁群算法的研究状况
3.1物流配送的优化方法
随着物流配送向集约化、一体化方向发展,常将配送的各环节综合考虑,其核心部分是配送车辆的集货、配货和送货过程。
配送系统优化,主要是配送车辆的优化调度(包括集货路线优化、货物装配和送货路线优化),以及集货、配货和送货一体化优化。
车辆路径问题(VehicleRoutingProblem,VRP)是配送环节的重要组成部分。
合理安排车辆数和车辆路线是减少浪费、提高经济效益的重要手段,不但可以降低商品的物流成本,还可以提高客户的满意度,扩大潜在市场,这对于整个物流运输速度、成本、效益有着重要的影响。
近年来,国内外专家对VRP问题的研究日趋深入,但多数集中于对某个单一目标的优化研究,并假设满足某些约束条件。
而在实际车辆调度过程中,经常涉及到时间或空间各方面的约束。
因此,多目标问题比单目标问题就更常见。
VRP问题有多种模型,其中:
带时间窗的车辆路径问题(VehicleRoutingProbtemwithTimeWindows,VRPTW)是一个具有代表性的带约束多目标问题。
与典型的旅行商问题(TravelingSalesmanProblem,TSP)相比,增加了车容量、时间窗等约束条件,其中两个目标维度分别为车辆数与总时间耗费(或总路径长度当速度定义每单位时间耗费为1时),其目标是在满足空间容量限制和时间限制的条件下,求使总成本最小的最优解。
目前,VRP问题的求解算法很多,可大致分为精确算法和启发式算法两大类。
精确算法的计算量一般随着问题规模的增大而呈指数增长,所以多用于规模较小的问题。
而对于求解大规模的NP(Non-deterministicPolynomialProblem)难题,则较常用模拟退火算法(SA)、禁忌搜索算法(TS)、遗传算法(GA)、神经网络(NN)、蚂蚁算法(AS)等现代启发式算法。
蚁群算法最初由意大利科学家Dorigo.M于1991年提出,是一种基于群体、用于求解复杂组合优化问题的通用搜索技术。
该方法首先被应用于TSP,并在一系列阃题中得到应用,诸如二次分配、Job—shop、图着色问题、VRP问题、集成电路设计以及通信网络负载等离散优化问题等。
但蚁群算法搜索时间长、易于停滞(即搜索到一定程度后所有个体所发现的解完全一致),存在不能扩大对解空间继续搜索的缺陷。
3.2蚁群算法研究现状
蚁群算法(AntSystem,AS)是一种新生算法,具有很强的通用性和鲁棒性。
从提出到现在,仅短短十余年的时间,但其在离散型组合优化问题的求解中,表现出强大的优越性,所以引起人们的关注。
目前蚁群算法的研究学者主要集中在比利时、意大利、德国等国家,美国和日本在近几年也开始了对蚁群算法的研究。
国内的研究始于1998年末,主要在上海、北京、东北少数几个学校和研究所开展了此项工作。
蚁群算法作为一种新型的智能优化算法,与其它优化算法相比,具有正反馈、分布式计算以及贪婪的启发式搜索等主要特点。
正反馈过程使得该算法能够发现较好解;
分布式计算使得该算法易于并行实现,更快得到较好解;
与启发式算法相结合,使得该算法易于发现较好解,这些特点为更好解决复杂的组合优化问题提供了可能。
由于在蚁群算法中所有个体都要进行信息素更新,造成了信息素分配的浪费和分配畸形,所以蚁群算法的性能并不很理想。
Dorigo.M等人在蚁群算法又提出了改进的蚁群系统(AntColonySystem,简称ACS),在蚂蚁选择下一城市时使用的转移概率中加入伪随机分配概率,以避免出现蚁群算法中的信息素分配畸形。
尽管蚁群系统与蚁群算法相比提高了算法的性能,但它仍然使用蚁群算法中的全局信息素更新原则和局部信息素更新原则,即对所有
个体进行信息素更新,造成了信息素的大量冗余,弱化了好信息素的强度。
目前,所有蚁群算法的改进基本上都是建立在蚁群算法基础之上。
自1998年,第一届蚂蚁优化国际研讨会召开以来,已经是第三届了,大大推动了蚁群算法的发展。
蚁群算法已经引起越来越多的关注,尽管还缺乏完善的理论分析,对它的有效性也没有给出严格的数学解释,但回顾模糊控制的发展历史,理论的不完善并不妨碍应用,有时应用是超前于理论的,并推动理论的研究,伴随着研究的不断深人,蚁群算法必将迎来一个光明的前景
3.3蚁群算法求解VRPTW研究现状
近年来,许多学者利用蚁群算法对各种VRP问题进行了大量的研究,设计了各种类型的蚁群算法,而对VRPTW研究不是很多,具体有:
刘志硕、申金生、柴跃廷为求解VRPHTW,提出了一种基于可行解的两阶段构造策略的自适应混合蚁群算法。
实验结果表明,自适应混和蚁群算法性能优良,能够有效地求解VRPHTW。
陈幼林、王劲恺提出一种求解VRPTW问题的改进蚁群算法,通过增加虚拟配送中心的数量,将VRPTW转化为TSP进行求解,使每只蚂蚁都可以构建一条可行路径,避免在该问题中多只蚂蚁协同合作来构造解的低效性,通过实验计算表明该方法是可行的。
万旭、林健良、杨晓伟利用最大-最小策略改进信息素,该算法减小了蚂蚁算法陷入局部陷阱的可能性。
基于对最大.最小信息素策略和信息素更新方式的改进,结合快速产生初始解的算法,提出了一种新方法。
把该方法应用于VRPTW问题,试验结果表明该算法是有效的。
刘哲、李建国提出了一种并行多蚁群算法(PMACS-VRPTW),首先利用
QUICK-ACS生成初始解,然后利用ACS—VEI和ACS-TIME分别优化车辆数和行程距离,试验表明该算法是可行的。
4.蚁群算法的改进
4.1遗传算法对蚁群算法的改进
遗传算法的操作算子是遗传算法的核心内容,我们将复制、交叉、变异这些遗传算子引入蚁群算法中,以提高算法的收敛速度和全局搜索能力。
复制
遗传算法中,复制的主要思想是认为父代中的优质个体可能更接近全局最优解,应该在子代中继承并继续进化。
复制操作使得父代中优质的个体能够在子代中得以保存,避免交叉变异等操作导致优质个体在种群中丢失。
蚁群算法中,在每一代搜索完成后,我们将当前父代中最优的解复制到子代中,使得最优的个体能在子代中继续积累信息素,这样能加快算法的收敛速度。
编码
遗传算法中的交叉和变异操作是建立在基因编码上的,因此在引入交叉和变异操作之前,我们首先对物流配送模型进行编码。
假设有L个客户点,K辆配送车辆,本文采用的编码方式是将这L个客户点分别用1到L这L个自然数标识;
第一辆车从配送中心出发时用0标识,其他车辆则分别用L+1,L+2,…,L+K-1表示。
由于同一辆车可以多次配送,所以,2次以上配送的车辆出发时,依次用L+K,L+K+1,……表示。
新的一辆车从配送点出发,或者编码结束,就表示前一辆的路线结束,返回配送中心。
这样就将一次配送表示为一组由0和自然数 组成的编码。
例如,有6个客户点,我们分别用1至6表示,3辆车负责,那么编码:
0,1,2,3,7,4,5,8,6
表示3辆车的配送线路分别是:
车辆1[0à
1à
2à
3à
0],车辆2[0à
4à
5à
0],车辆 3[0à
6à
0]。
又如编码:
0,1,2,3,8,4,5,9,6
表示的配送线路为:
0],车辆3[0à
0],车辆1第二次配送 [0à
交叉
交叉操作是遗传算法中增加种群多样性,防止算法早熟、停滞的操作。
在蚁群算法中引入交叉操作,可以有效地扩大搜索空间,避免算法陷入局部最优解。
在蚁群算法每一代搜索完成之后,我们将其中的最优解和次优解进行编码交叉操作,交叉规则如下:
1)假设两组编码分别是S1和S2,首先随机生成交叉段的长度和交叉段起始位置;
2)找出S1和S2中的交叉段,假设S1:
P1|P2|P3,S2:
Q1|Q2|Q3,P2和Q2分别是S1和S2的交叉段;
将Q2插入S1中,位于P2前面,这样形成新的编码S3:
P1|Q2|P2|P3;
3)在S3中,删除P1、P2、P3中与Q2重复的编码。
形成交叉编码S3;
4)同样的方法用在S2上,生成新的编码S4;
5)比较S1、S2、S3、S4的结果,选出最优的两组编码并保存。
变异
变异操作也是增加种群多样性的一种进化手段。
适度的变异,既能保持种群内个体的多样化,又能提高算法的效率。
在蚁群算法中,我们在完成交叉操作后,对种群中最优个体进行变异操作,操作方法为:
1)随机生成变异次数N;
2)随机生成两个不同的自然数n1,n2>
1(第一位不变,保证编码以物流中心为起 点);
3)在最优个体的编码S中,将第n1位和第n2位的编码对调;
4)重复2)、3)N次,生成新的编码S’;
3)比较S和S’的结果,保存较优解[4]。
4.2蚁群算法的其他改进策略
在引入遗传算法对蚁群算法进行改进后,算法的收敛速度和全局搜索能力得到了提高。
我们下面还将从信息素的更新方式、客户点选择策略进行改进,以提高蚁群算法的自适应性。
信息素传递参数r的选取
按照基本蚁群算法,r是一个常量,如果r过大,则会使未搜索过的路径被选择的概率相对减小,影响全局搜索能力;
而如果r过小,又会影响算法的收敛速度。
因此我们在改进算法中将对r作适当调整。
在算法初期,我们希望算法能尽快找到较优解,因此r要比较大,增大信息浓度的影响,加快算法收敛速度;
而当算法停滞不前时,我们要减小r,从而减小信息素对蚁群的影响,增大蚁群对解空间的搜索,以脱离局部最优解的束缚。
4-1式中,r表示连续没有进化的循环的次数,rmax是一个常量,lÎ
(0,1)是一个常量,控制r衰减速度,rmin是r的最小值,防止r过小影响收敛速度。
当r达到预先设置的一个数值rmax时,我们就减小r,r重新计数,如此反复,直至r达到预设最小值rmin为止[5]。
确定性搜索和探索性搜索的选则
加速收敛就是要在已得到的较优解的基础上,尽量快的进化,以得到更优解。
由于蚁群算法是一种启发式算法,不断地“探索”是蚁群算法进化的必要手段,而正是这种“探索”限制了蚁群算法收敛速度。
例如,当算法得到一个较优解,而且该解有可能进一步优化,但由于“探索”范围很大,使得蚂蚁选择该路径的概率相对减小,从而使得路径上的信息量浓度逐渐衰减,该路径也逐渐被“遗忘”了。
为了解决这一问题,我们引入一个新的常量:
q0Î
[0,1),蚂蚁k在每次选择路径之前,先随机产生一个qÎ
[0,1),蚂蚁k选择路径s将根据下式:
[6]
式子中,当q³
q0时,是基本蚁群算法中的探索性搜索;
当q<
q0时,是从已得的结果中,找出概率最大的路径作为选择,是对已得成果的“利用”,为确定性搜索。
确定性搜索弥补了探索性搜索在收敛速度上受限制的缺陷,通过适当调整q0,能够使得确定性搜索和探索性搜索合理搭配,加快蚁群算法的收敛速度。
我们还要对q0的取值进行讨论。
q0时,算法是采用确定性搜索,此时蚂蚁以概率q0选择距离最短的路径;
当q≥q0时,算法是采用探索性搜索,此时蚂蚁以概率l-q0随机选择路径。
在算法迭代的初期q0选取较大的初始值,以较大的概率进行确定性搜索,这样可以加快寻找局部较优路径的速度;
在算法的中期q0选取较小的值,增大探索性搜索的概率,从而扩大搜索空间;
在算法的后期,恢复q0的初始值,加快收敛的速度。
结合改进后的蚁群算法,我们可以得到基于改进后蚁群算法的物流配送路径优化问题的 算法流程图:
开始
G=0,初始化信息C,设置进化代数G_MAX,对每只蚂蚁初始化车辆序列
G=G_MAX吗
随机产生qÎ
[0,1)
tabu满了吗
更新最佳路径,清空tabu,G=G+1,更新q0,若连续未进化代数r=rmax,r=MAX[lr,rmin]
得到最优路径,输出结果
结束
N
Y
更新ta
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 模式识别 论文
![提示](https://static.bingdoc.com/images/bang_tan.gif)