一种并行多目标遗传邻域搜索算法

A Parellel Multi-Objective Genetic Local Search Algorithm

现有的多目标遗传算法在解决大规模多目标生产调度问题时虽然有效,但往往非常耗时,难以应用于实际。为了提高求解效率,提出了一种并行多目标遗传邻域搜索算法来求解Pareto边界。该算法将多目标遗传算法的进化方向划分为若干范围,然后同时对每个进化方向的范围使用多目标遗传邻域搜索算法,并行地搜索各方向范围内的Pareto边界;在各进化方向范围内进化的子种群会定期交流各自进化成果。多目标遗传邻域搜索算法的并行化在不增加求解时间的前提下,提高了求解精度,加快了算法的收敛速度。仿真实验结果验证了算法的可行性与有效性。

The problem of multi-objective genetic algorithms in solving large-scale multi-criteria scheduling problems is discussed. To improve the efficiency, a parallel multi-objective genetic local search algorithm is presented to generate Pareto boundary. The direction of evolvement of the multi-objective genetic algorithm is divided into several domains. For each domain, a multi-objective genetic local search algorithm is applied simultaneously to obtain Pareto boundary in the directions of each domain. The sub-populations in each domain communicate with each other to exchange their achievement regularly. Without increasing the computing time, the parallelization improves the precision of the solution and increases the convergence speed. Numerical experiments demonstrate the effectiveness of this algorithm.