Population Degeneracy Phenomena Analysis And Suppressing Methods On Genentic Algorithm

The main goal of this research is to make investigation into the population degeneracy phenomena(PDP)and design effective suppressing methods on genetic algorithms(GA)for the fixed charge transportation problem(FCTP).Firstly,That the crossover operator of GA with matrix code(GA-M)results in PDP is proved.Furthermore,three sufficient conditions for the PDP are presented from aspects of candidate solution structure,vertices' requirements in transportation graph and the total transportation fee,respectively.Meantime,that the mutation operator can not suppress the PDP caused by crossover operator is proved strictly. To enhance the performance of GA for the FCTP,suppressing method for GA-M (SM-GA)is also developed,which can suppress the PDP caused by GA-M without increasing time complexity.Moreover,the results of experiment demonstrate that the searching and suppressing capacity of SM-GA is superior to GA-M.Secondly,an analysis on the single point crossover operator appending edges to sub-tree of genetic local search algorithm(GLSA)and GA with edge set(GA-ES) is presented.It is strictly proved that the crossover operator results in population degeneracy without requirement constraints.Furthermore,a sufficient condition for population degeneracy with requirement constrains,such as fixed charge transportation problem,together with its probability are also developed.Simultaneously,that the mutation operator can suppress the PDP to some extent is also strictly proved. And,an algorithm SM-GA-ES is constructed to suppress the PDP with the strategy to restrain the number of leaves in spanning tree.The experimental results show that,compared to GA-ES,S-GA-ES can suppress the PDP and enhance the performance of GA obviously.Thirdly,to overcome the speciality of SM-GA-M and S-GA-ES,an immune genetic algorithm(IGA)for the fixed charge transportation problem is developed based on the immune theory in biology.The computational results demonstrate that IGA can not only restrain the degenerate phenomenon but improve the search capability compared to genetic algorithms with matrix code and edge-set code greatly with large instances.Finally,an conclusion and the further research direction are also proposed at last chapter.