基于支配强度的NSGA Ⅱ改进算法在研究生招生面试分组中的应用

Application of Improved NSGA Ⅱ Algorithm Based on Dominance Strength in Graduate Enrollment Interview Grouping

针对研究生招生面试分组这一NP难问题,提出了一种以分组遗传算法(GGA)和基于支配强度的改进NSGAⅡ算法为基础的混合多目标分组遗传算法。通过基于矩阵编码的多交叉/多变异算子、次精英化的初始化种群策略以及改进的帕累托支配关系,解决了经典NSGAⅡ算法在该问题中的收敛速度慢、易陷入局部最优的问题。仿真实验结果表明,该方法只需进行较少代数(不超过100代)的进化,即可获得最优解集,满足了快速分组的用户偏好。

In order to solve the NP hard problem of graduate enrollment interview grouping,a hybrid multi-objective grouping genetic algorithm is proposed.It is integrated with grouping genetic algorithm(GGA) and improved NSGA Ⅱ algorithm based on dominance strength.By using multi-crossover/multi-mutation operator based on matrix coding,sub elitist initialization population strategy and improved Pareto dominance relation,the problems of slow convergence speed and easily falling into local optimum of classical NSGA Ⅱ algorithm in this problem are solved.The simulation results show that the optimal solution sets can be obtained in only a few times of evolution(no more than 100 generations),which meets the user’s preferences of fast grouping.