作　　者： ; ;

机构地区： 贵州大学计算机科学与信息学院计算机科学系

出　　处： 《计算机学报》 2005年第7期1146-1152,共7页

摘　　要： 通过分析影响并行遗传算法性能的诸多因素,以避免人为设置迁移代频、迁移率及迁移方向为问题的突破口,以减少通信量提高算法效率为主旨,提出一种基于渗透原理的迁移策略(MigrationSchemeBasedOnPenetration,PMS).PMS迁移策略源于渗透模型,引入渗透阈值控制相邻子群体的迁移,应用渗透原理自适应地确定迁移代频、迁移率及迁移方向,从而解决人为设置迁移代频、迁移率及迁移方向的关键问题,有效降低通信代价,进而提高算法效率.文中首先依据有限群体马尔可夫链模型对基于渗透原理的迁移策略算法的可行性进行了探讨,然后从理论角度给出了迁移代频期望、迁移率期望及通信代价,同时用实例验证了PMS在降低通信代价方面的巨大潜力. Analyzed several main factors that affect the performances of parallel genetic algorithms, and in order to solve the hard problem that migration interval and migration rate and migration direction must be set manually, and also in order to increase the performances of parallel genetic algorithms, authors propose a new migration scheme based on penetration theory. Introducing a threshold to control migration between any two sub-populations, authors use the penetration theory to set migration interval and migration rate and migration direction adaptively. The feasibility of this new migration scheme is discussed according to Markov Chain of finite population model. The expectation of migration interval and the expectation of migration rate are formalized then, the formalizing of communication costs is at the last, at the same time authors verify the PMS (Migration Scheme Based on Penetration) could greatly decrease the cost of communication by examples.

关 键 词： 并行遗传算法 渗透原理 迁移策略 马尔可夫链 多种群模型

领　　域： [自动化与计算机技术] [自动化与计算机技术]