面向大规模调度问题的并行参数自适应萤火虫优化算法研究

In order to solve the problem that most existing scheduling algorithms cannot be directly applied to large-scale production scheduling, this project will construct parallel firefly optimization algorithm for large-scale scheduling problems. The main contents include: 1) Through the analysis of the iterative nature of firefly optimization algorithm to further explore the effect of parameters on firefly movement mechanism, explore the relationship between historical information and parameters in the process of group evolution, and design a new adaptive model of parameters, so as to balance the development and exploration ability of firefly optimization algorithm and improve its universality. 2) Based on random bond theory and disjunctive graph theory, a new efficient coding and decoding method is designed, which makes the firefly optimization algorithm suitable for solving production scheduling problem.3) On the basis of analyzing the inherent natural parallelism of firefly optimization algorithm and the hardware programming characteristics of GPU, a reasonable and efficient parallel firefly scheduling optimization algorithm is designed on GPU software platform and applied to solving the large-scale production scheduling problem. . This project is a research of swarm intelligence optimization method and scheduling technology on the new computing platform. It is a new computational model. It has important theoretical significance and application for promoting the development of production scheduling method and swarm intelligence optimization technology.

为解决大多数已有调度算法无法直接应用于大规模生产调度的问题,本项目将构建面向大规模调度问题的并行萤火虫优化算法。主要内容包括:1)通过分析萤火虫优化算法迭代本质进一步探索参数对萤火虫移动机制的作用和影响,发掘群体进化过程中产生的历史信息与参数之间的关系,以期形成新的参数自适应调节模型,从而平衡萤火虫优化算法的开发与探索能力,提高算法的普适性;2)借鉴随机键思想和析取图理论,设计一套新的高效编码和解码的方式,进而使得萤火虫优化算法适合于求解生产调度问题;3)在分析萤火虫优化算法的内在天然并行性的特点和GPU的硬件编程特征的基础上,在GPU软件平台上设计合理高效的并行萤火虫调度优化算法,并将其应用于大规模生产调度问题的求解。. 本项目是在全新的计算平台上对群体智能优化方法和调度技术展开探索研究,是个崭新的计算模型,对于推动生产调度方法和群体智能优化技术的发展有着重要理论意义和应用前景。

萤火虫算法同大多数已有的群体智能优化算法一样面临着一个普遍问题，即算法的时间计算复杂性随着问题规模的增大成指数倍增长。项目组根据研究计划，面向大规模生产优化问题对萤火虫算法及相关群体智能优化算法开展了研究工作，主要研究内容包括：. (1)研究了如何在保持萤火虫高多样性的情况下，调节吸引力步长参数以增强萤火虫的局部搜索能力。同时分析了随机步长参数α和吸引参数β对萤火虫全局寻优能力的影响，以及历史信息中的经验知识对萤火虫群体进化过程的影响因子。为了提高萤火虫算法的效率和性能，设计了一种可以根据当前环境变化和历史影响因子进行自适应调节参数的萤火虫优化算法。. (2)在对萤火虫算法搜索优化过程的分析的基础上，为了减少一次迭代中的吸引次数，提出了一种称为非精英双向吸引模型的方法。该模型的核心思想在于，在一次移动过程中，萤火虫会受到精英萤火虫和种群内随机一个个体的引导，并根据新的萤火虫移动公式进行移动，这种模型较好地平衡了全局搜索和局部搜索，并大大减少了时间复杂度。此外，基于这一思路，进一步设计了群体引导和弹性调整策略，并将其应用于人工蜂群算法，取得了较显著的改进效果。. (3)在研究GPU硬件的特性的基础上，利用萤火虫优化算法的天然并行性，设计出了一种高效的并行萤火虫算法。为了解决萤火虫优化算法每代群体中参数众多的问题，研究了如何合理地分配每个个体的值和相关参数到GPU的存储空间，根据GPU硬件的性能合理地设计了“块”和“线程”的数量，以最大化地利用GPU上的硬件资源，并设计了基于CUDA平台的并行萤火虫算法框架。. 本项目的实施对，对提高萤火虫算法的普适性，完善萤火虫算法理论，推动智能优化技术的发展有着重要理论意义和应用前景。