多策略自适应群智能算法及其在大规模生产调度中的应用

In most swarm intelligence algorithms and their improved variants, all individuals in the population exhibit the same search behavior (global or local) because of using the same evolutionary strategy. For this problem, this project proposes an adaptive multi-strategy swarm intelligence algorithm, which constructs a multi-strategy set and assigns a strategy to each individual. During the evolutionary process, the search behaviors of individuals are adaptively adjusted according to the current search status of the population. Therefore, the approach can make a good balance between the global and local search, and improve the generality of the algorithm. At present, swarm intelligence algorithms are mainly applied to small and medium scale production scheduling problems. For large-scale scheduling problems, the computation time of most algorithms can be hardly acceptable. To solve large-scale scheduling problems, this project constructs a GPU based adaptive multi-strategy swarm intelligence scheduling algorithm on the basis of existing scheduling algorithms. By the GPU parallel processing technology, we can reduce the computation time and make the algorithm find satisfactory solutions under the condition of limited time and hardware resources (ordinary PC). The research of this project provides important references for improving the generality of swarm intelligence algorithms, and new methods for solving large-scale scheduling problems on ordinary PC. It has important theoretical significance and application value for practical production.

在大部分群智能算法及其改进的算法中，群体中所有个体由于采用相同的进化策略而表现出相同的搜索行为(全局或局部)。针对这个问题，本项目提出了多策略自适应群智能算法。该方法构造了一个多策略集，并为每个个体分配一种进化策略。在进化过程中，个体根据当前的搜索状态自适应地调整自身的搜索行为。因此，该方法能较好地平衡算法的全局和局部搜索，提升算法的普适性。 目前，群智能算法主要应用于中小规模的生产调度问题。对于大规模调度问题，大多数算法在计算时间上很难让人接受。针对大规模调度问题的求解，本项目在已有调度算法的基础上，构造了基于GPU的多策略自适应群智能调度算法。通过GPU并行处理技术，缩短计算时间，使得算法能够在有限的时间和硬件资源条件下(普通PC机)找到满意的解。 本项目的研究为提高群智能算法的普适性提供了重要的参考，并为在普通PC机上解决大规模调度问题提供了新的方法，具有重要的理论意义和应用价值。

群智能算法作为一种有效的优化技术，已被广泛地应用于不同优化问题的求解。然而，随着问题复杂性的增加，群智能算法的性能面临着极大的挑战。虽然很多学者提出了一些改进策略以提高原算法的性能，但这些改进仍具有一定的局限性，如依赖于问题、参数敏感和只在某个进化阶段有效。生产调度问题是一种离散优化问题，它具有计算复杂性和多约束性等特点。目前，群智能算法已被成功地应用于中小规模调度问题，但对于大规模调度问题的求解，存在一定的困难。针对上述问题，本项目的主要研究内容包括：1）提出了多策略自适应集成的人工蜂群算法，该算法在运行过程中能根据群体当前的搜索状态，自适应地选择不同的搜索策略来产生后代个体，以平衡算法的全局和局部搜索，提升算法的普适性；2）改进的布谷鸟算法在流水车间调度问题上的应用；3）多策略自适应集成的人工蜂群算法在大规模流水车间调度问题上的应用；4）基于GPU的并行萤火虫算法求解大规模全局优化问题；5）基于GPU的多策略自适应集成的人工蜂群算法在大规模流水车间调度问题上的应用。项目的研究发表论文21篇（含4篇在线发表），其中国际SCI期刊论文8篇，其它国际期刊论文5篇，国际会议论文5篇，国内核心期刊论文3篇。项目的研究成果在多策略自适应集成算法和大规模优化问题的求解等研究方面具有重要的理论意义。