特征选择次优算法.pdf

57 特征选择的次优算法  单独最优组合  顺序前进法（SFS ），广义SFS法（GSFS ）  顺序后退法（SBS ），广义SBS法（GSBS ）  增l 减r 法（L-R 法），广义L-R 法（(Z , Z )法） l r 58 特征选择的遗传算法（Genetic Algorithms ）  随机搜索算法；  模拟生物进化的现象— 进化计算（Evolutionary Computing ）；  把优化问题比喻作在无数可能的重组和突变组合中发现 适应性最强的组合的问题；  “Genetic Algorithms are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might not otherwise find in a lifetime.” Salvatore Mangano Ref. John Henry Holland, Adaptation in Natural and Artificial Systems, MIT Press, 1975 59 特征选择的遗传算法（Genetic Algorithms ）  术语  基因链码：代表问题一个解的编码（称为“个体”）， d 编码的每位是一个“基因”；二值字符串，共 种； C D  群体：解（个体）的集合；  适应度：以给定的优化准则（如某种类别可分性判据） 评价解性能的优劣；  基本操作  交叉（crossover/recombination ）：以两个个体为双亲作基 因链码的交叉，产生两个新的个体作为后代；  变异（mutation ）：对某个体随机选取并翻转其中一位 60 特征选择的遗传算法（Genetic Algorithms ）  算法的基本框架 1. 初始化进化的代数 t = 0 ； 2. 给出初始化群体P(t) ，并令xg 为任意一个体； 3. 对P(t) 中每个个体估值，并将群体中最优解x’ 与xg 比 较，若优于x ，则令x = x’； g g 4. 如果终止条件（通常是某个体的适应度达到设定的阈值） 满足，则算法结束，x 为最终结果。否则，转步骤 5； g 5. 从P(t) 选择个体并进行交叉和变异操作，繁殖新一代 个体P(t+1) ，令t=t+1 ，转步骤3 。 61 以分类性能为准则的特征选择方法（Wrapper