关键词: 遗传算法, 拉丁超立方体抽样, 人工免疫系统, 旅行商问题, 最大子团问题

Abstract: Concerning the defects of Genetic Algorithm (GA) in the deficiency of keeping population diversity, prematurity, low success rate and so on, the crossover operation in GA was redesigned by Latin hypercube sampling. Combined with immune mechanism, chromosome concentration was defined and selection strategy was designed, thus an improved genetic algorithm was given based on Latin hypercube sampling and immune mechanism. The Traveling Salesman Problem (TSP) and the Maximum Clique Problem (MCP) were used to verify the new algorithm. The results show, in terms of solution quality, convergence speed, and other indicators, the new algorithm is better than the classical genetic algorithm and good-point-set genetic algorithm.

Key words: Genetic Algorithm (GA), Latin Hypercube Sampling (LHS), Artificial Immune System (AIS), Traveling Salesman Problem (TSP), Maximum Clique Problem (MCP)