[科普中国]-种群初始化

大规模优化问题

当今很多优化问题已经从简单问题发展成为复杂问题，许多科学和工程应用问题都可以设计成大规模优化问题来进行求解，例如大型电力系统、大量的资源调度问题、大规模交通网络的车辆路径规划等。然而随着优化问题越来越复杂，一些经典的算法已经不能满足实际需要，最近几年进化优化在许多实值和组合优化问题上取得了很大的成功，但是大多数的随机优化算法都会遭受“维数灾难”。因此，近些年学者们利用进化算法进行了多种有价值的尝试，并且针对大规模优化问题组织了特别会议，显示出此研究领域的重要性。

数学表述大规模优化问题可以用数学式表述，介绍的解决方案主要针对该问题中最小化问题进行求解。在算法开始阶段，给出了针对大规模问题的初始化方法，可以更加有效的寻找极点。而对于算法的主体部分，一般来说主流的策略可以分为两大类协同进化策略和不分组策略。协同进化策略是由分治策略进化而来，主要思想是把大规模复杂问题分解成单变量或低维简单问题逐一解决。而不分组策略是运用一些特殊的策略或联合其它有效的算法来改进它们在解决大规模问题时的性能。

种群初始化算法在开始时都要进行种群的初始化，根据初始化方法的不同形式可以将其分成M类随机方法、定值设定法、两步式方法、混合方法和具体应用法，随机数生成器是最常用的方法，然而，在面对大规模优化问题（决策变量超过100）时，这种初始化方法效果不佳。在随机方法中，比较常用的是RNG。而定值设定法则比较偏向于在搜索空间中产生均匀分布的点。在缺乏问题先验知识的情况下，一个比较均匀的种群可以促进算法在迭代早期的探索能力。近些年，两步式初始化方法在文献中较为常用，此方法分为前期产生初始点，后期根据条件改进这些点，混合方法一般来说是一些基础方法的组合，具体应用法则是指根据一些特殊的实值问题专门设计的初始化方法1。

不分组策略学者们一般根据算法不同阶段的特性设置不同的策略来解决低维问题，所以，针对大规模优化问题改进这些策略是一种比较常用的方法。

子代产生策略一般来说，每种进化算法都有固定的子代产生策略。但是，对于大规模问题，使个体广泛分布在高维空间中比较困难，在每次迭代过程中，算法不断的收敛，因此下一代的产生策略很重要，不仅要向好的方向进化还要在搜索空间中广泛探索。这种产生策略具有空间的导向性，可以增加种群的多样性，将其插入算法来解决大规模优化问题。

新的进化策略在解决大规模优化问题上，除了在原有的算法中加入新的策略，提出了一些新的群集智能算法用于解决此类问题。提出了社会学习的粒子群优化算法，不同于经典的粒子群优化算法，利用历史信息（包括整个种群的最优位置和每个粒子的历史最优位置）更新粒子新算法中，粒子向当前种群中比它优秀的个体学习。

种群初始化流程种群的初始化就是依据编码规则给出种群的初始解。传统的遗传算法求解VRP问题时,初始种群多半采取随机生成法,即从所有的配送点中随机选取点直到满足一定的条件或接近满足一定条件后停止,形成一条子路径,乃至形成一条染色体(一套配送方案)。但这种方式使初始种群的形成过于随意,以致于一开始就可能形成许多不可行的方案,之后要进行大量的计算后才能得到优化的方案,这样很大程度上降低了算法的运算效率。

扫描法求解VRP初始种群的思路是:通过扫描法形成一套路径配送的完整方案,将其作为遗传操作中的一条染色体;重复这个过程,得到种群数量为N的染色体。具体流程如下：

(1)过配送中心与某配送点生成射线顺时针转动。

(2)累计扇面覆盖的配送点需求量之和,直至满足运量约束停止构成一个客户分群。

(3)采用节约插入算法将该客户群形成优化为一条有序的子路径。

（4）以原射线末位置为新射线的初始位重复上述过程。直至形成一条包含所有子路径的染色体序列。

(5)将射线顺位偏移某一角度,同样按以上方法产生第二染色体。最终形成N/2条染色体的种群。

(6)为保证种群多样性,上述方法逆时针做同样操作,再形成N/2条染色体。子路径内部是一个路径优化的序列组合,子路径之间同样按序列编号排列2。