多目标免疫算法研究及其在柔性车间调度问题上的应用

发布时间：2018-10-24 14:37

【摘要】：在工程应用和科学研究领域中,存在许多比较复杂的优化问题。由于其复杂性、动态性和建模困难等一系列的问题,传统的运筹学方法已经无法很好的解决这类优化问题。基于启发式的智能算法对处理这类问题表现出了一定的优越性,其中人工免疫系统是通过模仿生物免疫系统的信息处理机制而发展的一种新兴智能系统,提供了噪声忍耐、无监督学习、自组织和记忆等进化学习机理,为解决这类复杂优化问题提供了新颖的方法和思路。因此,免疫算法受到各个领域学者们的广泛关注。本文主要从优化问题的角度去研究免疫算法。首先介绍了免疫算法研究现状、生物学基础理论及其算法原理以及柔性车间调度现状及其问题描述。接着对多目标优化问题进行分析,提出改进的多目标免疫算法,然后在21个测试问题上验证其性能。之后根据柔性车间调度问题特性将提出的算法进行改进,并将其应用到柔性车间调度问题上,进一步验证了提出的算法在实际应用中也有较好的性能。本文的主要工作如下:(1)在解决多目标优化问题上,本文在多目标免疫算法的基础上研究分析,提出了动态种群策略免疫算法(MOIA-DPS)。该算法主要创新点在于提出了动态种群策略(DPS),通过外部存档状态控制种群的大小,从而合理地利用计算资源、避免早熟收敛并且增加种群的多样性。另外,设计了一个双模式差分算子(TDE),结合了rand/2/bin和rand/1/bin的优势,提高了算法的鲁棒性。之后在21个测试问题上进行仿真实验,与5个经典算法以及近年来新提出的5个免疫算法进行实验对比,以及验证提出算子DPS和TDE的有效性,实验结果表明提出的算法MOIA-DPS在多目标优化问题上具有明显的优势。(2)在解决柔性车间调度问题上,本文提出了一个动态克隆种群策略免疫算法(DCPS-MOIA)。DCPS-MOIA提出了一个动态克隆种群策略,当种群的整体提升率小于设定的值时,增大克隆种群的数量以增加基因的多样性,从而平衡了多样性和收敛性。并且运用第三章提出的TDE进行变异,提高算法的局部搜索能力和增加种群多样性。之后分别在3个问题实例上测试算法的有效性。
[Abstract]:In the field of engineering application and scientific research, there are many complex optimization problems. Because of its complexity, dynamic and modeling difficulties, the traditional operational research method can not solve this kind of optimization problem well. The intelligent algorithm based on heuristic has some advantages in dealing with this kind of problem. The artificial immune system is a new intelligent system developed by imitating the information processing mechanism of the biological immune system, which provides noise tolerance. Evolutionary learning mechanisms such as unsupervised learning, self-organization and memory provide novel methods and ideas for solving such complex optimization problems. Therefore, the immune algorithm is widely concerned by scholars in various fields. In this paper, immune algorithm is studied from the point of view of optimization problem. Firstly, the current situation of immune algorithm, the basic theory of biology and its algorithm principle, the current situation of flexible job shop scheduling and its problem description are introduced. Then the multi-objective optimization problem is analyzed, and an improved multi-objective immune algorithm is proposed, and then its performance is verified on 21 test problems. Then the proposed algorithm is improved according to the characteristics of the flexible job shop scheduling problem and applied to the flexible job shop scheduling problem. It is further verified that the proposed algorithm has good performance in practical application. The main work of this paper is as follows: (1) on the basis of multi-objective immune algorithm, a dynamic population strategy immune algorithm (MOIA-DPS) is proposed. The main innovation of the algorithm is that the dynamic population strategy, (DPS), is proposed to control the population size through the external archival state, so as to make rational use of computational resources, avoid premature convergence and increase the diversity of the population. In addition, a double mode differential operator (TDE), is designed to improve the robustness of the algorithm by combining the advantages of rand/2/bin and rand/1/bin. Then the simulation experiments are carried out on 21 test problems, compared with 5 classical algorithms and 5 new immune algorithms proposed in recent years, and the validity of the proposed operators DPS and TDE is verified. Experimental results show that the proposed algorithm MOIA-DPS has obvious advantages in multi-objective optimization problems. (2) in order to solve the flexible job-shop scheduling problem, a dynamic clonal population strategy immune algorithm (DCPS-MOIA) is proposed in this paper. DCPS-MOIA proposes a dynamic clonal population strategy. When the overall lifting rate of the population is less than the set value, increasing the number of cloned populations to increase the diversity of genes, thus balancing diversity and convergence. The TDE proposed in Chapter 3 is used to improve the local search ability and population diversity of the algorithm. Then the effectiveness of the algorithm is tested on three problem examples.
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TB497

【参考文献】