机器学习作业遗传算法

《机器学习作业遗传算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、近期沈阳市修路路段较多，交通拥堵，公交线路多有改动，因此,我想针对公交车辆调度时间表问题进行研究，正好运用了以前在数学建模方面学习的经验和资料，并在图书馆查阅了一定的文献资料进行了学习。公交调度优化问题实质就是研究公交公司和乘客之间的利益关系。公交公司希望发车间隔尽量大，发车次数尽量少，以减少其运营成本。而乘客则是希望等车和乘车的时间尽量少。因此，建立合理有效的公交车间隔优化模型就是在保证公交公司有较大利益的同时，也使乘客所用时间最短。建立数学模型：假设公交线路是固定的，则需要定义公交车站点元素

2、集合S={Si,S2,…,S}公交车线路元素集合L={l』2,…,1}行车吋间矩阵T°=(tij)n*m，切是从车站$到车站Sj的行驶时间。乘客分布矩阵A=(adn*m，a»是从车站Si上车到车站Sj下车的乘客数。决策变量发车间隔X=(xij),Xij表示第i线路，第j时段的发车间隔(i=l,2…,m,j=l,2…,H)。然后建立全天乘客出行总费用R和全天车辆运行总费用C的数学模型：R=Z[raDi(X,A,T°)+(l+r)aZi(X,A,T°)]C=S[cGJ(XJ°)+(l-c)bKj(X

3、,A,T0)]其屮，Di——第i位乘客等车时间，是X,A,T°的函数Zi——第i位乘客乘车时间，是X,A,T°的函数Gj——第j次班车所消耗的费用，是X的函数Kj——第j次班车行驶时间，是X,A,T°的函数r——乘客等车费用与乘车费用的权重系数C——车辆固定费用与可变费用的权重系数a每位乘客单位吋间内的平均费用b——车辆单位时间行驶费用定义W为全天乘客出行总费用和全天车辆运行总费用的权重系数，目标函数为min{wR+（l・w）C}。优化求解公交车调度模型时运用遗传算法，按遗传算法的步骤进行：1•

4、问题的编码方案：遗传算法中首耍考虑的是如何表示其问题，即如何对染色体编码，使之适用于GA操作。在经典的遗传算法中，常采用整数编码、浮点编码、DNA编码、二进制编码等方法。在此，我们将决策变量，即发车间隔进行整数编码，计算时间换算为具体时间，吋间单位可以取一分钟，半分钟等。将决策变量X二（Xij）,全天运营时间分H个运营时间，Xkj表示第k线路第i时段的发车间隔，染色体长度为H*m2•种群规模：在确定初始种群时，首先要确定种群规模，假设由N条染色体组成，随机选择N条染色体作为初始种群。3•种群适应

5、值计算：计算种群中染色体适应值£（i二12•:N）的过程通常由两个步骤组成，先是根据染色体X二（XQ按每条线路调度计算出每条线路各项总费用，再对每条线路各项总费用进行累加，并取其倒数作为染色体的适应度函数f计算适应度值。4•进行遗传操作:（1）选择：选择是依种群屮的每个个体的适应度fi的大小分配繁殖机会，fi大的个体繁殖机会高，fi小的个体将受到抑制甚至淘汰。（2）交叉：在使用遗传算法之前还应确定交叉概率pc即种群中有N*pc染色体进行操作，pc可取值在0.60-1.00Z间。交叉概率的选择决定

6、了交叉操作的频率，频率越高•可以越快地收敛到最优解区域•但过高的频率也可能导致收敛于一个解，需选取一适当值，如0.8。对于交叉算子，此处可以采用单点交叉算子，这样的算子对于我们采用的编码方案不会产生非法解。（3）变异：变异是通过赋予每个基因一个相对较小的变异概率pm来完成的。变异概率通常只取较小的数值。一般为0.005-0.1o若选取较高的变异概率，一方面会增加样本模式的多样性，另一方面也可能引起不稳定；若选取较小的变异概率.则可能难丁找到全局最优解。我们可以取P=0.01o对于变异算子，我们可

7、以采用随机选取变异点的单点变异算子，这样的变异算子同样不会产生非法解。在交叉和变异之后，合并并更新种群，再返回适应度计算，判断是否满足终止条件，如此迭代循环，直到满足终止条件则输出结果。（4）终止条件：常用的方法是固定遗传代数，到达后即终止。所以我们就采用达到遗传代数时，终止迭代。