父代种群参与竞争遗传算法几乎必然收敛  

ALMOST SURE STRONG CONVERGENCE OF A CLASS OF GENETIC ALGORITHMS WITH PARENT-OFFSPRINGS COMPETITION

作　　者：徐宗本[1] 聂赞坎[1] 张文修[1] 

机构地区：[1]西安交通大学理学院,西安710049

出　　处：《应用数学学报》2002年第1期167-175,共9页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(69975016号);863(2001AA113182号)基金资助项目.

摘　　要：熟知，标准遗传算法如不采用“杰出者记录策略”则必不收敛．本文发现：允许父 代种群参与竞争是标准遗传算法几乎必然收敛的充要条件．特别地，我们运用鞅收敛定理 证明：允许父代种群参与竞争型遗传算法能以概率１确保在有限步内达到全局最优解，且 收敛与种群规模无关．所获结果对该类遗传算法的应用奠定了可靠基础．It is well known that if the cononical genetic algorithm(CGA) does not adopt the 'elitist record strategy' , it can not guarantee its convergence. In this paper, we consider a class of genetic algorithms(GAs) with the strategy that parents are always put into com- petition with their offsprings. It is shown that such strategy is the necessary and sufficient condition for CGA to converge. Especially by applying submartingale theory and measure theory, we prove that after a finite number of iterations, the parents population will be settled in the set of global optimal solutions with probility one. Different from other GA convergence results, no restriction is imposed on the population size of the proposed model. The obtained results lie a reliable foundation for application of the con-sidered GAs.

关 键 词：父代种群参与竞争遗传算法 遗传算法 MARKOV链 下鞅 依概率收敛 几乎必然收敛 

分 类 号：O242.23[理学—计算数学]