摘要
采用改进的遗传算法求解极小碰集问题。在标准遗传算法的基础上,引入了精英策略以提高算法的搜索效率;在进化过程中加入了极小化操作,使得得到的结果都是极小碰集。同时通过实例,验证了极小化操作的有效性。最后,将此算法与其他求极小碰集的算法进行了比较。
In this paper,an improved genetic algorithm （called MGA） is used to compute minimal hitting sets. In order to improve the algorithm＇s efficiency, elite strategy was introduced based on the standard GA. At the same time,minimization operations were added during the evolution process so that the solutions gotten are all minimal hitting sets. Its validity was proved by different examples. Finally ,comparisons were made between our algorithm and other approaches for computing the minimal hitting sets.
出处
《广西师范大学学报（自然科学版）》
CAS
北大核心
2006年第4期62-65,共4页
Journal of Guangxi Normal University:Natural Science Edition
基金
国家自然科学基金资助项目(60273080
60473003)
教育部"新世纪优秀人才支持计划"
吉林省杰出青年基金资助项目(20030107)
关键词
极小碰集
遗传算法
精英策略
minimal hitting set
genetic algorithm
elite strategy
