基于Python实现的特征选择的遗传算法（GA）

模式识别 特征选择的遗传算法

目录
模式识别 特征选择的遗传算法 0
一、特征选择的遗传算法介绍 1
1.1 特征选择 1
1.2 遗传算法（Genetic Algorithm） 1
二、实验数据集介绍 4
2.1 Iris数据集介绍 4
2.2 Sonar数据集介绍 4
三、实验设置 4
3.1 算法流程 4
1、读取数据集，按照一定比例随机分为测试集、训练集 5
2、编码及种群的初始化： 5
3、开始迭代，直至达到指定的迭代次数： 5
3.2 在数据集上验证遗传算法 6
四、实验结果展示与分析 7
4.1 在iris数据集上验证遗传算法 7
4.2 在sonar数据集上验证遗传算法 8
4.3 总结 10
五、Python代码 10
三、实验设置
3.1 算法流程
本次实验选用的是K近邻法作为分类器，来评价所选特征的好坏，用来计算种群的适应度函数。由于上述算法流程较为简略，在实际编程实现对编码、选择、交叉、变异又使用了一些其他方法，下面具体说明整体流程（由于iris数据集维度较低，故使用sonar数据集具体说明）：
1、读取数据集，按照一定比例随机分为测试集、训练集
2、编码及种群的初始化：
对所有特征描述为一个由60个0/1元素组成的列表，代表染色体，0代表该特征没有被选中，1代表该特征被选中。
用户给定选择的数据维度d和种群数目p，将染色体（列表）初始化全0，然后随机将染色体中的d位变为1，这样就从60维特征中随机选择了d维。重复上述过程p次，则可以得到一个有p条染色体的初代种群P(0)，并且每条染色体都不尽相同。并随机选定一个最优个体。
3、开始迭代，直至达到指定的迭代次数：
1） 更新每个个体的适应度函数，并更新最优个体、统计种群的平均适应度。计算每个个体的适应度时，根据个体的染色体情况，将没有选中的特征删除（包括训练集和测试集），将数据送入分类器，计算分类准确率作为该个体的适应度函数。分类器使用之前实现的K近邻，根据之前的经验，K取2。
2） 根据适应度函数，对种群进行轮盘赌选择。对种群中的染色体进行采样，由采样出的染色体经过一定的操作繁殖出下一代染色体，组成下一代的种群。这里实用的是轮盘赌的方式进行选择：首先将种群中所有个体的适应度归一化，，将这些适应度值累加起来，得到p个区间，每个区间的长度代表对应染色体的适应度值。从0-1之间取随机数，该数落到哪个区间，就选用哪条染色体。本文转载自http://www.biyezuopin.vip/onews.asp?id=15003为保证种群的染色体数目不变，重复p次，就得到了基于上一代种群适应度的新子代种群。
3）交叉。对一条染色体，按照一定的概率（交叉概率设为0.4），选择是否进行交叉操作。再从种群中随机寻找到另外一条父代染色体，与之进行交叉，为了使交叉之后的染色体特征维数不变，采用了如下方法：
先从一个父代染色体中随机选取一个片段（长度为60/2=30），统计该片段中有几个为1的基因，再从与之匹配的父代染色体中寻找长度相同、1基因数目相同的片段，若找到，则进行交叉操作；若未找到，则寻找下一对父代染色体，直到将所有父代种群遍历完毕。
4） 变异。同样的，对一条染色体，按照一定的概率（变异概率设为0.01），选择是否进行变异操作。为了使变异之后染色体中特征数量不变，又采用了以下方法：
随机从种群中选择一个个体，再随机地选择一个基因进行反转，若该基因由1变为了0，则再随机选一个0变成1，反之也执行同样的操作。直至遍历完种群中所有的个体。
5）重复迭代。在进行完选择、交叉、和变异操作之后，上一代的种群已经变成了新一代的种群。重复上述过程1-4，在遗传算法迭代的过程中，种群中的染色体会趋于所选特征数中的最优解，达到一定的迭代次数 t 后，算法停止，输出最终种群中适应度值最大的染色体，和每次迭代过程中的种群平均适应度，即完成了在 D 维特征中选择d个最优的特征。

# -*- coding: utf-8 -*

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

sonar = pd.read_csv('sonar.all-data',header=None,sep=',')
sonar1 = sonar.iloc[0:208,0:60]
sonar2 = np.mat(sonar1) 


pc = 0.02                            # pc为变异的概率
t = 150   #遗传算法迭代的次数
n = 60    #种群的个体数,要求大于20以保证具有随机性
# d = 30    # d为要选择的特征个数

#遗传算法
def GA(d):
    population = np.zeros((n,60))     # 初始化种群
    for i in range(n):                # 定义种群的个体数为 n
        a = np.zeros(60-d)
        b = np.ones(d)                # 将选择的d维特征定义为个体c中的1
        c = np.append(a,b)
        c = (np.random.permutation(c.T)).T    # 随机生成一个d维的个体
        population[i] = c             # 初代的种群为 population，共有n个个体
        
    #遗传算法的迭代次数为t
    fitness_change = np.zeros(t)
    for i in range(t):
        fitness = np.zeros(n)             # fitness为每一个个体的适应度值
        for j in range(n):
            fitness[j] = Jd(population[j])          # 计算每一个体的适应度值   
        population = selection(population,fitness)  # 通过概率选择产生新一代的种群
        population = crossover(population)          # 通过交叉产生新的个体
        population = mutation(population)           # 通过变异产生新个体
        fitness_change[i] = max(fitness)      #找出每一代的适应度最大的染色体的适应度值
        
    # 随着迭代的进行，每个个体的适应度值应该会不断增加，所以总的适应度值fitness求平均应该会变大
    best_fitness = max(fitness)
    best_people = population[fitness.argmax()]
    
    return best_people,best_fitness,fitness_change,population
    
    


#轮盘赌选择
def selection(population,fitness):
    fitness_sum = np.zeros(n)
    for i in range(n):
        if i==0:
            fitness_sum[i] = fitness[i]
        else:
            fitness_sum[i] = fitness[i] + fitness_sum[i-1]
    for i in range(n):
        fitness_sum[i] = fitness_sum[i] / sum(fitness)
    
    #选择新的种群
    population_new = np.zeros((n,60))
    for i in range(n):
        rand = np.random.uniform(0,1)
        for j in range(n):
            if j==0:
                if rand<=fitness_sum[j]:
                    population_new[i] = population[j]
            else:
                if fitness_sum[j-1]