遗传算法java-遗传bp算法预测双色球软件

各位读者大家好，今天小编给大家分享如何用遗传算法求解带时间窗的车辆路径规划问题。算法的主要思想来自于论文：A simple and effective evolutionary algorithm for the vehicle routing problem。在实现用遗传算法解VRPTW的过程中，小编一直在被生成了很多不可行解修复很困难而困扰，而这篇论文中所提出的算法恰好就避免了不可行解的处理，那么究竟是如何实现避免讨论不可行解的呢？接着读完这篇推文就能明白了~

1.遗传算法

1

遗传算法简介

遗传算法（GeneticAlgorithm，简称GA）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的基于种群的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。遗传算法是现代智能计算中的关键技术之一。

2

遗传算法基本思想

在现实生活中，生物的染色体通过基因控制了生物的性状，而生物的性状决定了生物在环境中的适应度，适应度高的生物，其基因更容易流传下来，随着时间的不断流逝，整个种群的适应度随之提高。

遗传算法和现实非常类似，首先将问题的解通过一定的方法，编码到染色体中，通过适应度函数，得到每个个体的适应度，通过选择，将适应度高的个体保留到下一代中，不断迭代，即可获得满意解。

3

遗传算法流程

对遗传算法的详细介绍见：

2.带时间窗的车辆路径规划问题介绍

1

车辆路径规划问题介绍

车辆路径规划问题，经过60年来的研究与发展，研究的目标对象，限制条件等均有所变化，已经从最初的简单车辆安排调度问题转变为复杂的系统问题。最初的车辆路径规划问题可以描述为：有一个起点和若干个客户点,已知各点的地理位置和需求,在满足各种约束的条件下,如何规划最优的路径,使其能服务到每个客户点,最后返回起点。通过施加不同的约束条件遗传算法java，改变优化的目标，可以衍生出不同种类的车辆路径规划问题。同时车辆路径规划问题属于典型的NP-hard问题，其精确算法能求解的规模很小，故启发式算法也就成了研究热点。

2

VRPTW简介

VRPTW(Vehicle routing problem with time windows)即带时间窗的车辆路径规划问题，其对于每一需求点加入了时间窗的约束，即对于每一个需求点，设定服务开始的最早时间和最晚时间，要求车辆在时间窗内开始服务顾客。

需求点的时窗限制可以分为两种，一种是硬时间窗(Hard Time Window)，即要求车辆必须在时间窗内开始服务顾客遗传算法java，早到必须等待，迟到就拒收，另一种是软时间窗(Soft Time Window)，不一定要在时间窗内开始服务顾客，但是在时间窗外开始服务必须要惩罚，以惩罚代替等待与拒收是软时间窗和硬时时间窗的最大的区别。

VRPTW的数学模型如下：

（2.2）保证了每个顾客只被访问1次

（2.3）保证了装载的货物不超过容量

（2.4）（2.5）（2.6）确保了每辆车从depot出发最后回到depot

（2.7）（2.8）确保在时间窗内开始服务

在中详解介绍了如何用禁忌搜索（Tabu Search）算法求解VRPTW。

3.算法具体实现

1

染色体设计

在论文：A simple and effective evolutionary algorithm for the

vehicle routing problem中，作者提出了在用GA解决VRP时的几点注意事项，如下图所示：

简单来说染色体的设计可以遵循以下两点：

使用和TSP问题中类似的染色体、编码，没有分隔符

2.使用split方法将染色体转化为问题的解

在使用GA求解VRPTW的过程中，常见的问题就在于交叉后产生的大量不可行解，这里采用分割的思想，一个染色体所存的解是split函数操作后所产生的最优分割。这样所得到的解都为可行解，大大减少了无效搜索。

在所有分割里，能最小化目标函数的即为最优分割。其实这就是一个编码和解码的过程。

下面我们来具体介绍一下这个split方法:

大家可能会觉得获得最优分割是一个很困难的事情，其实引入图论的思想，利用Bellman-Ford算法，在O(n^2)内就能获得最优分割。

上面两个图展示了如何把原问题转化为一个图论中的问题：

将每个基因位设为一个点，假如将i到j连接，其路径满足容量约束和时间窗约束，则视为从i到j存在一条权值为路径长度的边。则最优分割即为从染色体开头的基因的点到结尾的基因的点的最短路。利用Bellman-Ford算法，可在O(n^2)中求出最优分割。

流程图如下：

2

群体多样性

遗传算法中常见的问题就是早熟，过早收敛。为了避免这种情况的发生，就要保证子代个体中各个个体的不同。

如何判断个体之间是否相同有很多算法，小编这里采用通过适应度的不同来判断的方法：

即两个个体的适应度相差大于一个值，即视为不同的个体。

3

crossover

crossover，即交叉操作，这里使用实数编码中常用的OX（Order Crossover）交叉算子。

OX 交叉算子的过程如图：

随机选择两个点i,j，其中0