Sub-population Evolutionary Algorithm Based On Linkage Learning For Multi-objective Scheduling Problem

The essence of the multi-objective optimization problem is to achieve balance between objective functions under certain constraints,permutation flow shop scheduling problem as one of applications is challenging because of itself high complexity,objective function conflicts and inconsistent test data.Based on multi-objective evolutionary algorithm,sub-population,Chebyshev's partition method and linkage learning technique,sub-population evolutionary based on linkage learning algorithm is proposed for multi-objective permutation flow-shop scheduling problem,by the summarized work,this paper does the following improvements:(1)Considering the sub-population in the distribution of the solution space,H is set up to do the solution space segmentation which can guarantee space full division of sub-population to ensure uniform distribution,Chebyshev 's method is to control weight which can find better solutions.(2)Construct dominance matrix and dependence matrix in the sub-population evolutionary algorithm using the relation between job and its position and relative position relation between jobs in the evolution process,bi-variance probability model is the core for block mining and block competition,then blocks are stored into the temporary database for linkage learning technique to combine artificial chromosomes and inject them into the evolution process which can improve the quality of the solution,the crossover of selected non-dominated solutions and the competitive dominated solution is going at the same time,the non-dominated solutions are for mutation and set a certain number of crossover and mutation operators for more solutions to be selected.To prove SEABLL performance,firstly Chebyshev is compared with linear weight on Taillard instance in the number of efficient solutions and average distance to reference sets which prove that Chebyshev 's weight is better.Secondly,to prove that bi-variance probability model is efficitive,SEABLL is compared with SPGAII on ta010,ta020,ta050,ta060,ta080 for generation 100 and 200,SEABLL is more evenly distributed.Finally SEABLL is compared with SPGAII in performance indicators — the number of the non-dominated solutions,efficient solutions and the average distance to the reference sets on 92% instances among ta001 to ta092 39 instances,further more the larger problem size,the more advantages.