【基于遗传算法的公交调度优化分析案例4300字】

PAGE21基于遗传算法的公交调度优化分析案例目录TOC\o"1-3"\h\u17400基于遗传算法的公交调度优化分析案例 1109411.1遗传算法概述 1224471.2公交线路调度优化算法 3256061.2.1经典遗传算法介绍 383611.2.2编码和解码 4133651.2.3适应度函数 545771.2.4遗传算子 545751.2.5基于进化策略的改进遗传算法 6遗传算法是一种通过模拟自然进化过程搜索最优解的方法，它在搜索过程中无需从单解开始搜索，而是从中集直接开始搜索，避免了传统算法容易陷入局部最优解的问题，因此更有利于全局择优，得到更接近真实值的解。本章通过分析与研究遗传算法的原理，深入了解其工作过程后分别将遗传算法和基于进化策略改进遗传算法应用于公交系统的调度优化。1.1遗传算法概述（1）遗传算法思路：遗传算法（GeneticAlgorithm）是通过借鉴进化论的思想，将自然进化与算法搜索相结合而提出的一种寻求最优解的原理。它不是从某单个解开始搜索，而是从问题解的中集开始，这是区别于传统优化算法的最大特点。比起传统算法，遗传算法更加有利于从全局择优，它从中集开始搜索，所得结论更逼近于真实值。使用遗传算法的简要步骤如下：首先选取规模为n的群体（QUOTEn∈N+n∈N+），根据一定的规则产生一组n个可行解QUOTEXi(k)(1≤i≤n)Xi(k)(1≤i≤n)组成初始群体，k成为代数，初始值接着给定每个个体的适合度值QUOTEf(Xi(k))f(X再给定每个个体的生存概率QUOTE，对不同个体以一定的方式进行配种产生配种个体QUOTEXi(k)Xi(k)；最后根据一定的选择策略，如轮盘赌抽样法或者随机遍历抽样法等方法选取配种个体QUOTEX1(k)X1(k)，QUOTEX2(k)X2(k)，并根据交叉概率和变异概率对配种个体组成初始群体QUOTEX1(k)X1(k)，QUOTEX2(k)X2(k)进行交换和变异操作，构成新一代个体QUOTEX1(k+1)X1(k+1)，QUOTEX2(k+1)重复以上迭代步骤，直到满足终止条件要求，如解的质量达到满意的范围、迭代次数或到达时间限制等。（2）算法构成要素遗传算法是一种针对全局的高效搜索方法。它的核心操作包括三个：选择、交叉和变异；而核心内容则包括参数编码、设定初始群体、设计适应度函数、设计遗传操作以及设定控制参数。①参数编码：转换问题解和算法搜索空间的方式。编码方式在很大程度上决定了计算效率。因此，在实际求解过程中，首先要明确对求解问题的编码和解码方式。一般分为实数编码和二进制编码，实数编码容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优；二进制编码更稳定，对电脑内存要求高，，需要解码且难以理解。②适应度函数：判定遗传算法中每个个体与问题目标符合程度的一个函数，一般依问题改变而改变，是遗传算法个体选取的核心。常用的选择方法有：排位次法、期望值法、适应度比例法、精华保存法等。③设计遗传操作：即根据一定的交叉方法，设定交叉概率P，随机对两两或者多个个体携带的信息进行组合，从而配种产生新个体的操作。交叉概率P通常来说取值在0.25—0.75之间。常用单点交叉或多点交叉[32]。变异算子，以变异概率QUOTE对某些个体的某些位置执行变异，从而形成一个新的个体，一般取0.01-0.2。当全部个体一样，新个体不能通过交叉产生，而只能通过变异产生，变异能够实现全局优化特质。④运行参数：在算法运行过程中可以自定义的参数，比如交叉和变异概率，种群初始大小，个体编码串的长度，算法终止迭代的次数等等。根据具体情况，参考建议的取值范围，进行运行参数的设定，如终止代数为100-1000；变异概率为0.0001-0.1等。问题描述确定变量、目标和约束条件建立优化模型问题描述确定变量、目标和约束条件建立优化模型适应度转换方法约束条件处理方法确定编码、解码方法适应度转换方法约束条件处理方法确定编码、解码方法确定运行参数计算遗传算子计算适应度F(k)确定运行参数计算遗传算子计算适应度F(k)输出最优解编程进行遗传算法输出最优解编程进行遗传算法图1.1遗传算法求解流程图遗传算法进行程序编码时，当达到给定的阀值的，达到最优个体的适应度或者群体适应度保持不变或下降时，算法停止。否则返回到评价阶段执行再一次循环[33]。其求解过程上图1.1所示。1.2公交线路调度优化算法将遗传算法应用于公交车调度模型，使用python语言编写模型算法程序求解车辆调度问题，程序框架如下：首先进行相关参数设定，定义数量分析函数、初始化函数及适应度函数，按照设定条件要求进行程序循环，直到满足终止条件，最终获得编制行车时刻数据[34]。根据上文分析，公交车辆调度是一个多目标问题，因此本节首先介绍了经典的针对多目标问题的遗传算法，然后基于进化策略提出了用于公交调度系统的改进遗传算法，对公交车辆调度问题进行求解。1.2.1经典遗传算法介绍将经典遗传算法应用于公交车辆调度问题中的步骤如图1.2所示：适应度函数初始化函数数量分析函敷适应度函数初始化函数数量分析函敷参数设定适应度函数变异操作函数交叉操作函数选择操作函数适应度函数变异操作函数交叉操作函数选择操作函数适应度函数满足终止条件适应度函数满足终止条件?编制发车时刻编制时刻表编制发车时刻编制时刻表图1.2使用遗传算法求解车辆调度问题其主要步骤包括编码解码，设定适应度函数，选择、交叉和变异等。1.2.2编码和解码染色体编码：这是使用遗传算法对问题进行求解的基础。本节使用二进制编码方式对遗传算法进行编码，使得群体中的每个个体携带如人体染色体遗传信息中的碱基对信息，运用0和1替代ACGT四种碱基序列[35]。基于这一原则，根据本文模型特点，确定周期长度T为编码串长度，假设本文调度时间精确到分钟，那么每个编码位置对应调度周期内的每一分钟。各个编码位置的值表示相应时刻的发车状态，该时刻发车时值为1，否则为0，如长度为T的编码串：1,0,0,0,1,0,0,0,0,1,1,0,表示在第1分钟、第5分钟，，在第T-1分钟发车，其他为不发车。染色体解码。根据编码串，计算值为1的位置数量，可以得到第i辆车的发车时刻QUOTEtiti应该与编码串中第i个1的位置对应，如编码串1,0,0,0,1,0,0,0,0，1,1,0，对应的解码为QUOTEt1=1,t3=10,…,tn约束条件处理。本文模型存在约束条件，因此使用遗传算法求解时，需要对约束条件进行处理，本文将约束条件加入到目标函数中，利用罚函数方法调整个体的适应度：QUOTEt2=1t2=1(1.1)z是问题的目标函数值；Z是添加约束条件后的目标函数值；系数QUOTEa1,a2,..,a6a1,a2,..,1.2.3适应度函数适应度函数：是判定遗传算法中每个个体与问题目标符合程度的一个函数。由于适应度函数总是一个非负数，目标函数既可是正数也可以是负数，因此在目标函数和适应度函数之间需要进行一定的转换。本文目标函数是求解最小化问题，使用如下适应度函数QUOTEFkFkQUOTE：(1.2)上式中，QUOTEFkFk为染色体QUOTEvkvk的适应度，QUOTEZmaxZmax为相对较大的数值，只要可以保证QUOTEFkFk的值为正，QUOTEZkZk为染色体QUOTEvkvk的目标函数值。评价个体适应度的一般过程为：首先对群体中的单个个体进行解码，获得对应的个体值；再处理获得的值从而可得相应的目标函数值；最后依据问题类型以一定的转换方法将目标函数值转换为适应度[37]。进行程序编码时，初始群体中各个个体的基因值通过使用启发式方法获得，初始群体按照规则挑选M个染色体，使用的规则如下：约束发车时刻间隔的上下限，寻找最优发车时刻；按照整个调度周期内的最高断面通过量确定一个染色体；随机确定。1.2.4遗传算子（1）选择方式本节使用确定式的遗传算子选取方法，即根据给定的选取方式对每一代群体中的个体进行选择。步骤如下：进行程序编码时，初始群体中各个个体的基因值通过使用启发式方法获得，初始群体按照规则挑选M个染色体，使用的规则如下：约束发车时刻间隔的上下限，寻找最优发车时刻；按照整个调度周期内的最高断面通过量确定一个染色体；随机确定。首先计算群体中每代个体的期望生存数目QUOTENkNkQUOTE，(1.3)再对QUOTENkNk取整，得期望个体的下代生存数；最后将QUOTENkNk余下小数从大到小列序，取前M个个体放入k+1代群体中。（2）交叉算子遗传算法的交叉操作，是指对配对的染色体携带的信息以一定的交叉规则进行交换，从而在下一代产生新的染色体个体。交叉操作可以在同代任意的两个染色体之间发生，在本节中，交叉操作只发生在相邻个体之间。在交叉过程中，对相邻个体之间随机生成一个实数QUOTE0≤r≤10≤r≤1，如果QUOTEr<cross_mater<cross_mate，QUOTE0<corss_mate<10<corss_mate<1为交叉概率，当交叉概率大于0小于1则对这两个个体进行交叉，否则不进行交叉操作，只调换二进制字符串位置。本节选取单点交叉方法，即在一对相邻交叉个体中只选取一个交叉点进行交叉。单点交叉方式包括两个步骤，首先以随机的方式将群体中的M个个体配对成QUOTE[M/2][M/2]对个体组实现染色体配对，相同的两个染色体进行交叉后产生的后代与父代相同，交叉后染色体不优于父代。所以本节将逐个配对交叉染色体，并与该染色体之间的差异性进行比较，最终配对的染色体要选择差异性最大的来进行。交叉点位置的选取则按照给定概率QUOTEPcPc确定[38]。（3）变异算子遗传算法中变异操作主要用于增加种群遗传的多样性，通过在遗传过程中使部分个体发生突变，避免算法陷入局部最优解。本节采用OS变异方法，设定每代群体中的每个个体变异概率为QUOTEPmPm，在每代交叉产生新个体前首先进行变异操作，然后再交叉产生下一代个体。（4）运行参数遗传算法中的运算速度和群体多样性受到运行参数的影响较大，因此运行参数的选择取一般建议范围内的中间值[39]。用M表示的值群体大小，取值为50；P表示终止代数，取值500；QUOTEPcPc表示交叉概率，取值0.6；QUOTEPmPm表示变异概率，取值0.005。根据问题情况可知道调度周期T就是编码串长度l。在遗传算法开始计算之前，还需要初始化种群设置。分别设置遗传种群数量为QUOTEpop_sizepop_size，个体编码长度为QUOTEchromo_sizechromo_size。种群初始数量越大，则产生个体种类越丰富，但计算量也相应指数增长；QUOTEchromo_sizechromo_size则由参数编码方式确定。初始种群的产生方式既可以自定义，也可以随机生成。最后，还需要设置遗传算法迭代的次数。本节设置终止迭代数为500代，若连续产生10代符合条件的染色体，同样终止迭代。1.2.5基于进化策略的改进遗传算法针对于城市公交调度的优化问题，分别从乘客的利益、公交企业利益的角度出发，引入公交车行驶成本和乘客候车成本概念，以保证乘客乘车体验感和尽量增加公交公司利益为目标，以发车时间间隔为标的建立了相应的双目标优化模型，针对双目标优化模型，采用线性加权的方式设定不同目标的权重指数，将双目标函数转化为单目标函数。由于目标函数在约束条件下具有多个峰值，用传统的优化算法很容易陷入局部最优解，于是本文采用进化策略算法对目标函数进行优化。与传统遗传算法相比，该算法最大的特点就是具有实数编码的方式，可以简化算法设计的过程，大幅度减少了编码的时间与空间，在扩大搜索范围和寻找最优解的同时，达到快速收敛的效果。公交车调度问题的研究十分复杂，因此利用线性加权法把乘客利益与公交公司成本统一为单目标函数，较好地简化了问题，模型求解结果是基于北京市实际指标得到的，兼顾了公交公司与乘客双方的利益，具有良好的实用性。引入权重后，转化的单目标规划模型如式1.4所示：&(1.4)其中QUOTEα、βα、β为权重系数，且QUOTEα+β=1α+β=1；QUOTEωω为运营总成本；QUOTEC1、C2C1、C2分别为公交车每公里运营成本和乘客每分钟等待成本；第i个时间段发车间隔为QUOTEtiti，时长为QUOTETiTi，第i个时间段第j个站上车人数为QUOTEuij基于进化策略的实数编码遗传算法，编码成本相对较低，编码简单方便。在此小节计算中，设定初始的种子数200，适应度函数同样为转换后的