【作者】 张军；

【导师】 公茂果；

【作者基本信息】 西安电子科技大学 ， 电路与系统， 2013， 硕士

【摘要】 多目标优化问题(Multi-objective Optimization Problem, MOP)是科学研究和工程实践中的基本问题形式之一。近年来，利用进化算法处理多目标优化问题逐渐成为进化计算领域的一个研究热点。本文以其前沿研究方向之一——人工免疫多目标优化模型为基准，针对加快算法收敛速度和高效的多样性保持策略进行了深入的研究。以基于人工免疫系统的多目标优化算法，即非支配邻域免疫算法(Nondominated Neighbor Immune Algorithm, NNIA)为基础，提出改进的免疫多目标优化算法并将其成功应用于解决柔性作业车间调度问题。本文的主要工作包括：（1）收敛速度和非支配解集的多样性是多目标进化算法(Multi-ObjectiveEvolutionary Algorithms, MOEAs)的两个重要指标。为此，本文提出了基于博弈论的资源配置模型和基于动态选择的双超球体拥挤度方法分别用于加快NNIA的收敛速度和改善NNIA非支配解的多样性。将改进后的算法EMIA(EnhancedMulti-Objective Immune Algorithm)与NSGA-II(Non-Dominated Sorting GeneticAlgorithm II)和NNIA在12个标准测试问题和有实际背景的WBD(Welded BeamDesign)问题进行实验对比，实验结果显示EMIA在收敛性和多样性方面具有优势。（2）柔性作业车间调度问题(Flexible Job shop Scheduling Problem, FJSP)是经典作业车间调度问题的扩展，它不仅需要确定工序的加工顺序，还要给每个工序分配机器，也是最困难的组合优化问题之一。本文考虑的目标是同时优化最大完工时间和总加工成本，提出了基于NNIA的密母算法(Memetic algorithm, MA)处理两目标FJSP问题。本算法采用NNIA框架与多种模拟退火搜索算子相结合的方法。通过4组测试实例对设计的调度算法进行仿真，结果验证了该算法的有效性。（3）将EMIA算法框架应用于两目标FJSP问题中，并与NSGA-II、MOEA/D(Multi-objective Evolutionary Algorithm Based on Decomposition)和NNIA算法框架进行对比，通过8个测试问题验证了EMIA相比于其它算法具有更好的解决两目标FJSP问题的能力。更多还原

【Abstract】 Multi-objective optimization problem (MOP) is a fundamental issue in currentscientific research and engineering practice. Recently, dealing with multi-objectiveoptimization problems by evolutionary algorithm has become a hot topic in the area ofevolutionary computation. This thesis is to focus on the building of the model andtheory of artificial immune system based on multi-objective optimization, which is theleading and promising field in the area of MOP. The intensive study has beenimplemented in improved convergence speed and efficient techniques in diversitymaintaining. Based on the artificial immune system’s multi-objective optimizationalgorithm, i.e. Nondominated Neighbor Immune Algorithm (NNIA), the proposedimmune multi-objective optimization algorithms are successfully applied into dealingwith flexible job shop scheduling problem. The main works in this paper are as follows:(1) Convergence speed and diversity of nondominated solutions are two importantperformance indicators for Multi-Objective Evolutionary Algorithms (MOEAs). Wepropose a Resource Allocation (RA) model based on game theory to accelerate theconvergence speed of NNIA, and a novel Double-Sphere Crowding Distance (DSCD)measure to improve the diversity of nondominated solutions of NNIA. The improvedalgorithm of NNIA is called EMIA (Enhanced Multi-Objective Immune Algorithm).Comparison results on twelve benchmark problems and the real-world WBD (WeldedBeam Design) problem show that EMIA is better than NSGA-II (Non-DominatedSorting Genetic Algorithm II) and NNIA in convergence and diversity of nondominatedsolutions.(2) Flexible job shop scheduling problem (FJSP) is an extension of the classicaljob scheduling which is concerned with the determination of a sequence of jobs,consisting of many operations, on different machines, satisfying parallel goals, and it isalso one of the most difficult combinatorial optimization problems. This paper addressesthe FJSP with two objectives: Minimize makespan, Minimize total operation cost. Weintroduce a memetic algorithm based on the Nondominated Neighbor ImmuneAlgorithm (NNIA), to tackle this bi-FJSP. The proposed algorithm adopts thecombination of the NNIA framework and a variety of simulated annealing operators.The experimental results of four groups of test instances show that the proposedalgorithm is effective. (3) The algorithms frame of EMIA, NSGA-II, MOEA/D (Multi-objectiveEvolutionary Algorithm Based on Decomposition) and NNIA are applied into bi-FJSP,and experimental results of eight problems demonstrate that the EMIA can solve thebi-FJSP successfully compared with other algorithms.更多还原