基于主成分分析改进遗传算法的交通信号配时优化方法

摘要

基于主成分分析改进遗传算法的交通信号配时优化方法，通过分析遗传算法与图像处理和模式识别间的内在联系而提出了这种算法，可以用于求解各种函数优化问题。此算法利用对种群个体进行主成分分析分析设计交叉和变异算子。交叉算子能够根据PCA统计的父代个体的相似基因位避开容易产生无效交叉的交叉位置，减少无用的交叉，提高算法的搜索效率；变异算子根据PCA统计的相似基因位进行自适应的变异概率调节，从而保护优秀模式，提高算法的局部搜索效率。将本算法应用于单交叉口信号配时优化问题，通过和现有的算法进行测试对比说明了算法的通用性和有效性，得到了有效的配时时间，减少了交叉口前的排队车辆数。

主权项

基于主成分分析改进遗传算法的交通信号配时优化方法，其特征在于：该方法包括如下步骤，S1进行个体编码、初始化数据，并设定参数所述个体表示绿灯时间的组合；用g_i表示i相位的绿灯时间，为保持产生的后代个体的有效性，采用3个时间组合，个体编码形式为：＜g₁ g₂ g₃＞，用二进制进行编码；所述初始化数据将种群大小初始化为popszie，每次后代都产生popsize大小的种群；所述设定参数包括：设定交叉概率Pc为0.8，变异概率Pm为0.01，个体长度21位；S2种群初始化随机产生popsize个个体长度为21位的初始种群pop0；S3交叉操作S3.1以轮盘赌的方式从pop0中选择两个个体p₁和p₂；即设p₁＝(p_1,1,p_1,2,...,p_1,N)，p₂＝(p_2,1,p_2,2,...,p_2,N)为参与交叉操作的两个父代个体，将p₁和p₂组成一个矩阵P，形式如下：$P=\left\{\begin{array}{c}{p}_{1,1},p_{1,2},...,p_{1,N}\\ p_{2,1},p_{2,2},...,p_{2,N}\end{array}\right\}$N为个体长度；S3.2对S3.1中的P进行主成分分析，设定降维维数为m，得到特征矩阵W＝[w₁,w₂,...w_m]；S3.3取出W中第一个特征值对应的特征向量w₁，找出w₁中第一个不为0的位置设为first和最后一个不为0的位置last；S3.4利用以下公式算出交叉位置pispis＝first+rand()％(last‑first)S3.5利用S3.4中的pis对p₁和p₂进行单点交叉，得到p′₁和p′₂；S4变异算子S4.1设p₁'＝(p_1,1',p_1,2',...,p_1,N')，p₂'＝(p_2,1',p_2,2',...,p_2,N')为参与完交叉操作后将要执行变异操作的两个个体；S4.2根据交叉算子中W中第一个特征值对应的特征向量w₁，将其中的基因位分为等于0的和不等于0的；S4.3将w₁中对应为0的p₁′和p₂′的基因位采用较小的变异概率Pml，其他位置采用较大的变异概率Pmh；S4.4对p₁′和p₂′进行变异，得到p″₁和p″₂，并放入到种群pop1中；S5终止条件判断：若达到规定的代数，则结束并输出结果，由此得到有效的交通信号优化配时，否则转S6；S6进入下一遗传循环：从pop0和pop1中的个体进行适应度排序，挑选popsize个适应度高的个体进入pop2中，用pop2将S3中的pop0替换掉，转S3。