原创 遗传算法与交通信号控制

首先讲讲什么是遗传算法（GA）

遗传算法是模拟DNA的遗传方式设计出来的算法。

首先，对于一个问题划定一个解空间，也就是许多可能的解组成的一个阵列，每一个解都可以当做一个基因，这样我们就得到了一组基因。

然后，对于一个问题我们考量解是否合适的方法有很多种，为了简化理解，可以设置一个判别器（Filter），看这个解和问题拟合的程度如何，拟合的程度越高说明解的效果越好。

遗传算法的主要步骤有三个

  1：选择

     也就是选择两个基因（解）作为父本。为了方便理解假设解的形式都是二进制的，例如1001100之类的代码串。

  2：交叉

     交叉的方式有很多种，例如将父本切成两段，然后头交换或者尾交换，这样就得到了一组后代。当然，也可以切成多段，交换其中的一些。

  3：变异

     可以选择其中的一些位，改变值。

经过了这三个步骤得到的新的解，在去匹配判别器，一般来说，得到的最优解的拟合度都好与父本的最优解，或者可以继续以得到的基因做父本来实现遗传算法。

   当然，交叉和变异的方法都是随意的，没有什么规则可寻，这也是遗传算法的一个缺点，就是不确定性。

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

在来说交通信号控制，这里主要讲讲路网优化的问题

  提几个概念，路网的表示这里采用路口和路段来组合而成。

  对一个十字路口而言，车辆的行驶规则可以有12种情况，每个路口包括直行，左转和右转。对交通信号控制优化而言，右转对交通是没有影响的，所以可以简化模型成8规则。

  描述路网可以采用四个参数，

C 周期，相邻两个路口绿灯变换的周期

G 绿灯时间

P 相序，也就是8个规则（方向）的通行顺序，顺序具有随意性但是又受约束，例如，相对面的两个路口放行顺序一般相一致

θ 相位差，将每个放行方向规定为一个相位

为了将问题具体化，即用各种参数和方程来描述问题，我们需要将8规则分别编上号，编号方式美国有一种通用的编号方式，做交通信号控制的都采用这种编制，叫做NEMA TS2规范。

具体编法是，对十字路口而言，右路的左转编为1，顺时针转，左转依次编3，5，7.然后左路的直行编2，顺时针转，直行依次编4，6，8.

有了以上的准备工作，就可以将路网问题模型化和代数化了，可以利用这些参数建模，针对不同的优化目标进行优化，遗传算法的优势在这种场景的优化中就可以得到体现。