ALPS-GA求解柔性作业车间调度问题

Solving Flexible Job-Shop Scheduling Problem Using ALPS-GA

针对传统遗传算法在求解柔性作业车间调度问题时容易陷入局部最优、寻优率低的问题,提出一种将年龄分层人口结构和遗传算法相结合的算法ALPS-GA。构建具有层次结构的ALPS系统,使用Logistic混沌序列初始化种群,填入第一层;通过GA的选择、交叉、变异等操作,使种群中个体的遗传物质发生改变,并且将自适应概率方法加入ALPS-GA;定时重启第一层的GA,补全第一层缺失的个体并将种群个体向上跃迁,达到终止条件时停止进化。将算法在Benchmark实例上仿真,结果表明:ALPS-GA同时运行多个GA时全局搜索能力强,寻优率高,算法跳出局部最优的概率较大,在解决最大加工时间的最小值和平均值时都能取得较好结果,验证了ALPS-GA算法的有效性。

Aiming at the problem that traditional genetic algorithm is easy to fall into local optimum and low optimization rate when solving flexible job shop scheduling problem,an ALPS-GA algorithm combined with Age-Layered population structure and genetic algorithm was proposed.The paper constructed a hierarchical ALPS system,initialized the population with Logistic chaotic sequence,filled in the first layer;changed the genetic material of the individual in the population through GA selection,crossover,mutation,etc.,and added the adaptive probability method to ALPS-GA.Then we periodically restarted the first layer of GA,complemented the first layer of missing individuals,jumped the population individuals upwards,and stopped evolution when the termination condition was reached.The algorithm was simulated with the Benchmark example.The results show that ALPS-GA has a strong global search ability when running multiple GAs at the same time,and the search rate is high.The probability of the algorithm jumping out of local optimum is large,and good results can be achieved when the minimum and average values of the maximum processing time are solved.These verify the effectiveness of the ALPS-GA algorithm.