[发明专利]基于最小生成树聚类遗传算法的交通信号配时优化方法

摘要

本发明公开一种基于最小生成树聚类遗传算法的交通信号配时优化方法，包括：进行个体编码、初始化数据，并设定参数；进行种群初始化；计算种群内个体的适应度值；对种群进行最小生成树聚类；选择种群内个体参加遗传操作；对选择的个体进行交叉和变异操作；重复迭代直到得到对应周期的最佳配时。本发明通过对种群进行最小生成树聚类，使物种内的个体具有很高的相似度，而物种间的相似度较低，利用物种间的交叉可以维持种群多样性，抑制未成熟收敛现象；将本发明应用于单交叉口信号配时优化，可以得到有效的配时时间，减少交叉口前的排队车辆数。

主权项

一种基于最小生成树聚类遗传算法的交通信号优化配时方法，包括以下步骤：步骤一，进行个体编码、初始化数据，并设定参数；所述个体表示绿灯时间的组合；用ti表示i相位的绿灯时间，为保持产生的后代个体的有效性，采用3个时间组合，个体编码形式为：＜t1 t2 t3＞，用二进制进行编码；所述初始化数据将种群大小初始化为popszie，每次后代都产生popsize大小的种群；所述设定参数包括：设定交叉概率Pc为0.8，变异概率Pm为0.01，个体长度21位；步骤二，进行种群初始化，随机产生popsize个21位个体组成的种群；步骤三，计算种群内个体的适应度值；步骤四，对种群进行最小生成树聚类；步骤五，选择种群内个体参加遗传操作；对种群内个体采用轮盘赌选择两个个体，如果两个个体不属于同一类，则两个个体被选定，参与到遗传操作中产生后代个体；如果两个个体属于同一类，判断两个个体的适应度值大小，将适应度值大的个体淘汰，重新选择，直到选到的个体属于不同类为止；步骤六，对步骤五选择的个体进行交叉和变异操作；交叉操作，采用单点交叉，随机产生交叉位，互组父代个体之间的基因位，形成两个新的个体；变异操作，对交叉后产生的两个个体，以一定的概率进行变异，0变1，或1变0，变异后产生个体还需要解码后判断是否满足ti的条件，如果满足，将其归入下一代种群，直到产生大小为popsize的后代种群，作为下一代操作的父代种群；如果不满足，则直接淘汰产生的新个体，同时计数器不进行累加，保证最后产生popsize个后代个体；步骤七，重复执行步骤四～六，得到对应周期的最佳配时；其特征在于，所述步骤四对种群进行最小生成树聚类的方法如下：（1）计算popsize个个体间的欧式距离作为两个个体建立的边的权重，构成一个有权无向图；（2）利用Prim算法求出这个无向图的最小生成树；（3）确定最小生成树的断边阈值；（4）通过切断生成树中的边进行分类：从最小生成树起点开始遍历，将权重大于阈值的边去掉，形成一个森林，属于同一个树的边就属于同一类；（5）对森林进行深度遍历，对每一类进行记录保存，同时对每类中的个体按照适应度值大小进行排序。