下载文档原格式
课程设计报告设计题目：基于进化算法的车辆路径问题求解学院：电子工程学院专业：电子信息工程班级： 020915 学号：学生姓名：电子邮件：时间： 20012年9月成绩：指导教师：刘静西 安 电 子 科 技 大 学 电 子 工 程 学 院 课 程 设 计（报告）任 务 书 学生姓名 指导教师 职称 教授 学生学号 专业 电子信息工程 题目 基于进化算法的车辆路径问题求解 任务与要求 了解进化算法（Evolutionary Algorithms ），介绍其基本思想、主要分支于基本流程。
了解车辆路径问题（Vehicle RoutingProblems ），介绍其基本分类、各类问题的具体模型与异同点。
最后给出一种进化算法求解某类车辆路径问题的基本方法。
开始日期 2012 年 8 月 27 日 完成日期 2012年 9 月 7 日 课程设计所在单位 智能信息处理所研究所 2102年 9月 7 日…………………………装………………………………订………………………………线………………………………………………………………摘要随着社会主义市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，物流配送业得到了迅速发展。
物流车辆路径优化调度，是物流配送中的关键环节，对企业提高服务质量、降低物流成本、增加经济效益的影响也较大。
在现实生产和生活中，邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、机器人路径规划、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调度问题。
物流配送车辆路径调度问题作为一个NP难题，可选的配送路径方案计算量将随着客户数量的增加以指数速度急剧增长。
进化算法是基于生物进化机制的搜索算法，适合于求解复杂系统优化问题，特别是组合优化问题有明显的优势。
因此，用进化算法求解该问题就成为人们研究的一个重要方向。
本文在对国内外物流配送车辆调度现状及其实现技术对比的基础上，结合vRP(vehieleRoutingProblem)问题模型，研究了进化算法解决车辆路径问题的方法，并开发了基于进化算法的智能物流配送系统。
一、发展背景1.生物进化“自然选择，适者生存”是达尔文进化理论的核心。
根据这一理论，生物的发展和进化有三种主要形态:遗传，变异和选择。
生物进化的可归纳如下几点：(1)生物的性状具有可遗传性。
子代的生物会继承父代个体的一些性状，但是，后天对生物体性状的改造，不会遗传到下一代中，即获得性不能遗传。
(2)成功适应环境的个体有更多的机会将自己的特性遗传给下一代。
(3)染色体能产生突变。
使得子代个体和父代不同。
发生这种现象的概率虽然很低，但它为环境突变时产生新物种埋伏了物质基础。
(4)进化过程是没有记忆的。
下一代的进化过程和上一代的进化过程是没有关系的。
2.生物遗传上世纪初，Morgan通过遗传学和细胞学的结合，奠定了基因理论。
1952年，Hershey 等通过实验成功地证实DNA(Desxoyribont;eleieAeid、脱氧核糖核酸)是遗传物质。
作为一种指令密码封装在每一个细胞中，并以基因的形式排列在染色体上。
每个基因有特殊的位置.并控制着生物的某些特性。
生物在产生后代的时候，后代染色体是从亲代复制过来的。
对于有性生物，还会对双亲的染色体进行重组，综合，使得双亲的基因都有机会得到延续。
3.遗传算法在数量众多的进化计算算法中，使用最广泛，研究最彻底的是遗传算法。
机器学习中，为了获得一个好的学习算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候选策略的群体的繁殖，其特色是高度并行，随机，自适应，健壮，特别适合于处理复杂问题(如NP问题的近似解)和非线性问题。
标准遗传算法涉及：个体的染色体（二进制位串遗传编码与对象定义域）、重组算子或杂交或交叉算子（遗传操作、大概率）、变异算子（获取新基因、小概率）、选择算子（适应度）。
4.相关的其他算法遗传编程、进化规划、进化策略等。
这些算法和遗传算法或多或少有一些相似之处，但各自强调的侧重点又各不相同，都有一些自己的优势应用领域。
遗传编程广泛应用于优化控制，符号回归，公式发现等领域。
变异因子改进的进化策略算法摘要进化策略是借鉴生物进化的思想，在现代遗传学的启发下，发展起来的一种启发式随机搜索优化方法。
进化策略作为一个新的交叉学科，目前已发展成一种自组织、自适应的综合技术，广泛用于计算机科学、工程技术、管理科学和社会科学等领域，尤其在信号处理领域受到高度重视。
目前，由于进化策略产生下一子代的方法是通过变异方式实现的，对父代的继承性较差，因此目前进化策略的应用主要是配合遗传算法或其它智能算法使用，单独使用进化策略解决问题的例子较少。
针对于此，本文提出改进后的进化策略算法，该算法能够有效地继承父代的优点，能够得到更快、更优的收敛结果。
本文的主要研究内容包括：1. 对传统进化策略进行分析，剖析其收敛过程，掌握制约收敛速度和收敛全局最优解的基本要素，通过对传统进化策略的改进，进而得到一种更快、更好的进化策略寻优算法。
2. 提出改进后的进化策略算法，论述其实现方法，并与传统进化策略进行实例仿真对比。
3. 通过实例说明改进后收敛算法比传统进化策略具有更好的收敛速度和更加稳定的收敛特征，能够有效的收敛到全局最优点。
本课题是以传统进化策略为基础，所做的探索性研究尝试提供一种新的进化策略方法，改进传统进化策略。
本文证明了改进进化策略的收敛性，并且通过多个实例验证了改进后的进化策略，证明其具有更快的收敛速度和更好的稳定性。
关键词：进化策略，变异因子，优化算法IAbstractThe evolution strategy profits from the biological evolution theory, and it is a heuristic stochastic search optimization method in the inspiration of the modem genetics. As a new interdisciplinary study, the evolution strategy has developed as an self-organized, auto-adapted comprehensive technology, which is widely used in the field of computer science, project technology, management science，social sciences and so on, particularly in the signal processing.At present，the evolution strategy neglects the characteristic of father generation, so the evolution strategy application is not independent. Mostly, it is used to coordinate with the genetic algorithms or other intelligent algorithm. Accordingly, we propose the improvement evolution strategy. This algorithm can effectively inherit the meritorious character of father generation, which can obtain a result quickly and precisely. This article main research content includes:1. By analyzing the traditional evolution strategy, we grasp the basic essential factor of restricting convergence rate and the overall situation optimal solution. At last we obtain a quicker and the better evolution strategy algorithm.2. We propose the improvement evolution strategy. We elaborate its implementation method, and contrasts with the traditional evolution strategy by the example simulation.3. The improvement evolution strategy has a better character compared to the traditional evolution strategy.Key words：Evolutionary strategy, Mutation operator, Optimization algorithm目录摘要 (I)Abstract (II)1绪论 (1)1.1课题研究的来源与意义 (1)1.1.1进化计算的研究来源 (1)1.1.2进化策略的研究来源 (1)1.1.3进化算法简介 (2)1.1.4进化算法的应用简介 (4)1.1.5进化策略的意义 (5)1.2进化算法的发展历程 (6)1.2.1萌芽期(50年代后期至70年代初期) (6)1.2.2成长期(70年代中期至80年代末期) (6)1.2.3发展期(90年代以后) (7)1.3进化策略的发展历程 (9)1.4课题研究的内容和结构 (10)2进化策略简介 (12)2.1(1+1)—ES (12)2.2(μ+1)—ES (13)2.3(μ+λ)—ES及(μ，λ)—ES (13)3进化策略的基本技术 (15)3.1进化策略的生物学背景 (15)3.2问题的表达 (16)3.3初始群体的产生 (18)3.4适应度计算 (19)3.5重组 (19)3.6突变 (21)3.7选择 (23)3.8终止 (24)4进化策略的表述 (25)5变异因子的改进及其分析 (28)5.1ES的改进研究 (28)5.2ES的步长控制 (29)5.2.1变异步长控制概述 (29)5.2.2变异步长与局部搜索性能的关系 (30)5.3变异因子的改进及其实现 (31)5.3.1改进变异因子的说明 (31)5.3.2进化策略算法的仿真实现 (32)6数据结果与性能评价 (34)6.1测试函数1 (35)6.2测试函数2 (37)6.3测试函数3 (40)6.4测试函数4 (42)6.5测试函数5 (45)6.6本章小结 (47)结论 (49)参考文献 (50)致谢.......................................................................................................... 错误！未定义书签。
原始粒子群算法的基本原理摘要：随着决策环境的复杂化，群体决策变得越来越重要，在此基础上研究粒子群优化算法，详细介绍其基本原理并进行分析显得十分重要。
关键词：粒子群优化算法种群大小最大速度1.1优化算法的分类随着现代科学技术的飞速发展，目前解决优化问题的方法主要分为两大类：一是模拟自然进化过程而发展起来的进化算法，目前研究的进化算法主要有三种典型的类别：遗传算法，进化规划和进化策略，这三种算法是彼此独立发展起来的；二是基于群智能的智能优化算法，目前主要有粒子群算法和蚁群算法两大类。
1.2粒子群算法的基本模型粒子群优化算法是兼有进化计算和群智能特点的一种优化算法，起初只是设想模拟鸟类捕食的过程，但后来发现粒子群算法是一种很好的优化工具。
与其他的进化算法相类似，PSO进化算法也是通过个体间的协作与竞争来实现最优解的搜索。
PSO算法为每个粒子制定了类似于鸟类运动的简单的行为规则，从而使粒子群的运动表现出与鸟类觅食相类似的特性，进而用于求解复杂的优化问题。
PSO算法中的每一个粒子，即解空间中的一个解，它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行，所有的粒子都有一个被优化的函数决定的适应值，适应值用来评价粒子当前位置的好坏；每个粒子还有一个速度决定他们的飞行方向和距离，然后粒子们就追寻当前的最优粒子在解空间中进行搜寻。
每个粒子在飞行过程中所经历过的最好位置，就是粒子本身找到的最优解；整个种群所经历过的最优位置，就是整个种群目前为止找到的最优解。
前者叫做个体极值，后者叫做全局极值。
每个粒子都通过上述两个极值不断的更新自己的位置和速度，从而产生新一代群体。
从以上分析可以看出在用粒子群算法解决问题的时候，我们首先要弄清楚什么是“鸟”，有了对象，然后才能确定该对象所谓的“位置”和“速度”是代表什么意思，粒子群算法的核心就是适应度函数的确定，不同的问题有不同的适应度函数，我们通过适应度函数来评价粒子当前的位置是好是坏，适应度函数体现了当前位置与最优位置的关系，即鸟类捕食模型中“鸟”和“食物”之间的距离所代表的含义，我们通过它来确定当前位置与最优位置之间的差距，然后通过分析适应度函数的指标，确定与最优解的接近程度。
进化策略与进化规划的异同
摘要：进化策略与进化规划同属于模拟进化优化方法中的重要分支，它们以特有的运算方式在求解复杂的、常规优化方法难以处理的优化问题上显示了一定的优势。
进化策略与进化规划在很多方面存在着相似性，为了更好地挖掘、理解两种方法的优化本质，有必要对这两种方法的异同之处加以阐述。
关键词：模拟进化优化方法；进化策略；进化规划
0引言
最优化技术在电力系统的规划、运行和控制中得到了广泛的应用——负荷预测、最优潮流、发电计划、自动电压控制(A VC)、机组组合等都是最优化问题。
由于线性规划和非线性规划在处理电容/电抗器和变压器变比之类的离散变量时效果不大理想，上世纪90年代中后期出现了进化策略与进化规划方法,并被用于电力系统的优化计算,比如遗传算法用于地区电网的无功优化。
进化策略与进化规划方法都是模拟自然界中生物的进化规律,理论基础是达尔文的进化论。
“物竞天演，优胜劣汰”实际上就描述了一种强壮的搜索、竞争与优化机理。
生物进化的历史可以用群体和种族内部或其之间所发生的物理过程来解释。
从大的方面来讲，包括：繁殖、变异、竞争和选择。
因此，在对生物进化过程进行模拟时，就应在总体上抽象地描述这几个过程。
20世纪60年代初期，一些学者开展了这方面的研究工作，并逐渐形成了一类具有鲜明特色的优化方法，即模拟进化优化方
法（optimization method by simulated evolution）或进化算法。
目前，此类方法已发展了很多分支。
其中，进化策略和进化规划以其特有的运算方式在解决复杂的、高度非线性、不可微的实值优化问题上具有一定的优势。
两种方法有很多的相似之处，但也有区别，需进一步加以了解。
1进化策略与进化规划基本流程
1.1进化策略
进化策略由德国学者I.Rechenberg 和H.P.Schwefel提出，对极值优化问题的求解有一定的优势。
进化策略的主要执行步骤为：①编码：对要求解的问题以数字串的方式进行编码（由目标参数和策略参数组成），计算适合度值；②判断是否满足终止条件。
如满足则输出结果；否则执行下述步骤：③选择n个父代参与繁殖；④按给定的方式执行交叉操作（可选）；⑤按基于高斯分布的扰动执行变异操作；⑥产生m个子代，并计算适合度值（m>n）；⑦返回步骤(b)。
1.2进化规划
进化规划由美国学者L.J. Fogel提出，同进化策略类似，适用于解决目标函数或约束条件不可微的复杂的非线性实值连续优化问题。
进化规划与进化策略在原理上相似，但在具体实现方面有差别。
其中最为显著的区别是进化规划中不采用交叉算子，仅通过变异操作来维持两代之间的联系。
其基本步骤为：①编码：对要求解的问题以数字串的方式进行编码（由目标参数和策略参数组成），计算适合度值；
②判断是否满足终止条件。
如满足则输出结果；否则执行下述步骤；
③选择n个父代参与繁殖；④按基于高斯分布的扰动执行变异操作；
⑤产生n个子代，并计算适合度值；⑤返回步骤(b)。
2进化策略与进化规划的关系
单从进化策略与进化规划的解题步骤就能看出，它们有很多的相似之处。
进化策略与进化规划在编码方面，不像传统遗传算法那样需要对要求解的问题进行0-1编码和解码，而是直接对所要求解的问题进行编码，即直接将优化问题的解表示为数字串的形式，不需要特定的编码和译码。
进化策略和进化规划均采用同样的变异操作方式，即变异时，对父代中的个体加上一个服从均值为0，标准差为的高斯分布随机变量。
标准差是变化的，编码时属于染色体串中的一部分。
由高斯分布曲线可知，高斯分布的方差反映了分布分散的程度，对适合度越大的个体，其变异量应越小，而适合度越小的个体，其变异量应越大，这符合生物进化过程。
进化策略与进化规划因其直接的编码方式以及特别的种群变异方式，使得该两种方法求解复杂的优化问题，特别是实值优化问题时，速度快，求解高效。
3进化策略与进化规划的差别
实际应用时，进化策略与进化规划的差别主要体现在以下几个方面：①进化策略中的交叉算子是可选的；如需要进行交叉运算时，采用类似遗传算法的处理方法，如离散交叉或中值交叉方式。
进化规划本身就没有交叉算子，这也是该两种方法最本质的区别；②在父代选
择方面：进化策略采用概率选择的方式形成父代，通常根据均与随机分布的方式抽取父代个体，这样每一个父代个体都能以同样的概率被选中。
进化规划则采用确定性的方式，即当前种群中的每一个父代都要经过变异来产生子代；③在具体变异表达式方面，进化策略与进化规划也存在差别，主要体现在：
设染色体编码结构为
X1,X2,……,Xn,σ1,σ2,……,σn
对于进化策略，其父代变异过程为：
σ'i=σi•exp(τ’•N(0,1) +τ•Ni (0,1))
X'i=Xi+σ'i•Ni (0,1)
其中，τ’和τ为学习率参数，通常τ∞1/(2 n)1/2and τ'∞1/(2n1/2)1/2
而对于进化规划，其父代变异过程为：
σ'i=σi•(1+a•N(0,1))
X'i=Xi +σ'•N(0,1)
通常α≈0.2
④在生存选择方面，即新的子代生成后，如何和父代共同形成新的父代。
对于进化策略，在经过变异和和交叉操作后，从n个父代中产生m个子代个体（通常m≈7n），这m个子代可直接作为新的父代，或将n个父代和m个子代混合，然后根据适合度大小直接去掉认为不好的个体。
对于进化规划，当n个父代生成n个子代后，采用一种循环竞争的策略来生成n个新的父代，即将n个父代和已生成的n个
子代合并，然后随机从中选取p个（一般p=10）个体，并与已合并的2n个个体逐个进行比较。
对每一次比较，性能好的该个体做一个‘胜者’的标记，如此重复，直到选出n个带有‘胜者’标记且性能最好的个体作为新的父代。
总的来说，进化策略在解算时表现的要灵活一些，而进化规划则更为精简。
在具体的实际应用时，这两种算法都有很大的改进空间，如变异机制、生存选择参数的选取以及适合度函数的制定等。
4结束语
本文探讨了进化策略与进化规划的相似与不同之处。
从编码、父代选取变异机制以及生存选择等方面阐述了两种的关系与差别之处。
在某种程度上，这有助于进一步理解、认识该两种方法的内在优化机制、提高算法的解题效率以及有效进行算法改进。
参考文献：
[1]李文沅.电力系统安全经济运行模型与方法[M].重庆：重庆大学出版社,1988.
[2]J H HOLLAND.Adaptation in Natural and Artificial Systems[M].Michigan:The University of Michigan Press,1975.
[3]H P SCHWEFEL.Evolution and Optimum Seeking[M].New York:John Wiley&Sons,1994.
[4]DA VID B FOGEL.An Introduction to Simulated Evolutionary Optimization[J].IEEE Trans on Neural Networks,1994(1).
[5]D E GOLDBERG.Genetic algorithms in search, optimization and machine learning[M].Boston: Addison Wesley,1989.。
