Jisuanji kexue yu tansuo (Nov 2023)
Resource-Constrained Project Scheduling Problems Oriented Two-Stage Imperialist Competitive Algorithm
Abstract
The resource-constrained project scheduling problem is a classic combinatorial optimization problem with a wide range of engineering applications. Since the 1960s, many optimization algorithms have been used to solve this problem, but most intelligent optimization algorithms do not perform well in the whole problem space. Aiming at this challenge, a two-stage evolutionary imperialist competitive algorithm (TSE-ICA) is proposed. Firstly, based on the block extraction strategy obtained by the critical-path method, two assimilation operators are presented for diversification and convergence, respectively. The two-stage evolution framework of TSE-ICA is constructed by selecting appropriate assimilation operators in different stages. Then, the block-based improved revolution mechanism includes two neighborhood search strategies of insertion and out-of-order, and the empire competition mechanism realizes the adaptive adjustment of parameters for each empire by collecting the convergence information of them. Lastly, the memory is used to guide the evolution of the population and improve the convergence rate. The design of experiment technique of Taguchi method is applied to determining the optimal parameter setting for TSE-ICA. In the following numerical experiment, the TSE-ICA is implemented and tested by 3 instance sets (J30, J60 and J120) from the standard instance library of PSPLIB. Moreover, the empirical statistical data of TSE-ICA are compared with 17 advanced state-of-the-art algorithms based on two evaluation criteria. Experimental results show that the TSE-ICA has well optimization performance and convergence efficiency, which proves the effectiveness of the proposed improved mechanism and the problem applicability of the TSE-ICA preliminarily.
Keywords
