Research On Improved Firefly Algorithm And Its Course Problem In Multi-constraint Environment

Timetable Scheduling is one of the fundamental tasks of university education and management.The quality of the timetable is critical to the proper functioning of the teaching mission.A reason for the unsatisfactory scheduling results is that the number of students has grown dramatically as the university increases enrollment each year.This has increased the amount of manual scheduling tasks and difficulties for staff.The timetable problem has been proven to be an NP-complete problem.One way to solve such problems is to find the approximate optimal solution.Classical metaheuristic algorithms include genetic algorithms,gray wolf optimization algorithms and firefly optimization algorithms,which are all based on iterative methods for finding optimal or feasible solutions.The Firefly Algorithm（FA）has been widely used in computer,engineering,management,and economics fields because of its good search capability.Some scholars solve the timetable problem by methods such as optimizing the step size parameter,and this operation can enhance the performance of the algorithm.However,such studies still suffer from the shortcomings of slow convergence and tend to fall into local optimality.To address the drawbacks of the existing research,this thesis improves the firefly algorithm from several perspectives and applies it to the college timetable optimization problem.The main work of this thesis is as follows.（1）To improve the parameters and models of the firefly algorithm,we propose a dynamic step size strategy and a two-way guidance model.Ideally,the step length of the firefly optimization algorithm should keep a large value in the early stage and gradually decrease in the later stage,according to which the rule uses the function evaluation times FE to design a dynamic step length adjustment strategy.The full-attraction model has an O（N~2）time complexity.To reduce its time complexity,we propose a non-elite two-way guidance model.The model not only reduces the time complexity,but also better balances the exploration and exploitation ability of the algorithm.The improved firefly algorithm is compared on a standard test function set,and the results show that both of the above improvement strategies contribute to the performance of the algorithm.（2）The modified attraction model facilitates the maintenance of population diversity.But the algorithm inevitably decreases in diversity and falls into a local optimum during the evolutionary process.Therefore,it is necessary to introduce a mechanism to increase diversity to improve the global search ability of the algorithm.To this end,a dimensional mutation strategy is introduced in Chapter 4 of this thesis to perform probabilistic variation on elite population individuals.This strategy makes elite individuals exchange dimensional information with neighboring individuals,hence jumping out of local optimum.Experiments show that the algorithm improves its global search ability and reduces the risk of falling into the local optimum after introducing the dimensional mutation strategy.（3）In order to apply the improved firefly algorithm to the timetable problem,this thesis presents a discrete encoding of individual fireflies,a way to detect and eliminate hard conflicts and two soft constraints.At the same time,we introduced a genetic algorithm to compensate for the shortcomings of the firefly algorithm.Hybridizing algorithms can improve the global and local search capability of the algorithm.Large-scale simulated data are used for the experiments,and a single-dual week design is considered in the individual coding scheme.Finally,the experiments compare the genetic algorithm with the hybrid firefly-genetic algorithm,and the results demonstrate the effectiveness of the improved algorithm for solving the college timetable problem.