上周开始接触遗传算法时，我确实被这个概念震了一下——用模拟进化的方式解决复杂优化问题，听起来聪明得不太真实。于是我想找个真正有难度的场景来验证，最后盯上了车辆路径问题：如何让一队车辆高效访问多个地点后返回仓库。

这篇记录整个实现过程。

打开网易新闻 查看精彩图片

什么是遗传算法

核心思想直接借自达尔文进化论。自然界中，更适应环境的生物存活繁殖，将性状传递给后代，种群随时间越来越擅长生存——"适者生存"。

遗传算法对解决方案做同样的事。基本循环如下：先随机生成一批解作为种群；评估每个解的好坏（适应度）；挑选表现更好的解进行"繁殖"；将两个解组合产生新解；随机微调部分解以保持多样性；重复多代。通常每代过后，种群整体会稍微变好。不保证找到完美解，但出奇擅长快速找到相当不错的解——这就是它的魔力。

车辆路径问题

假设经营一家配送公司：一个中央仓库、一队车辆、一批待配送地点。任务是确定哪辆车去哪些地点、按什么顺序，使得总行驶距离最小，同时各车辆工作量大致均衡。

这就是车辆路径问题（VRP），无处不在——亚马逊配送路线、外卖平台、垃圾清运、甚至校车调度。难点在于可能路线数随地点增加而组合爆炸：40个地点、4辆车时，暴力枚举所有组合完全不现实，需要更聪明的办法。

我用这个例子贯穿全文解释思路。

实现过程

用Python和DEAP库搭建，它提供了进化算法的基础组件。

表示一个解

首要设计决策是如何编码解。我采用地点索引的排列——将0到39的数字打乱，顺序决定每辆车访问哪些地点。车辆按轮询方式分配停靠点：车1拿索引0、4、8……车2拿1、5、9……车3拿2、6、10……车4拿3、7、11……这样表示方式简洁，也便于后续的交叉和变异操作。