遗传算法

遗传算法

1、遗传算法理论的由来

2、生物学的启发

3、遗传算法定义

4、遗传算法具体步骤

* 初始化
* 适应度函数
* 选择
* 交叉
* 变异

5、遗传算法的应用

* 特征选取

类比

我们先假设一个情景，现在你是一国之王，为了让你的国家免于灾祸，你实施了一套法案：

1. 你选出所有的好人，要求其通过生育来扩大国民数量。
2. 这个过程持续进行了几代。
3. 你将发现，你已经有了一整群的好人。

这个例子虽然不太可能，但是我用它是想帮助你理解概念。也就是说，我们改变了输入值（比如：人口），就可以获得更好的输出值（比如：更好的国家）。现在，我假定你已经对这个概念有了大致理解，认为遗传算法的含义应该和生物学有关系。那么我们就快速地看一些小概念，这样便可以将其联系起来理解。

过程

回到前面讨论的那个例子，并总结一下我们做过的事情。

1. 首先，我们设定好了国民的初始人群大小。
2. 然后，我们定义了一个函数，用它来区分好人和坏人。
3. 再次，我们选择出好人，并让他们繁殖自己的后代。
4. 最后，这些后代们从原来的国民中替代了部分坏人，并不断重复这一过程。

遗传算法实际上就是这样工作的，也就是说，它基本上尽力地在某种程度上模拟进化的过程。

因此，为了形式化定义一个遗传算法，我们可以将它看作一个优化方法，它可以尝试找出某些输入，凭借这些输入我们便可以得到最佳的输出值或者是结果。遗传算法的工作方式也源自于生物学，具体流程见下图：

算法的思想是非常简单的, 但是作用却是非常大的.

从一个实际问题来求解.

问题描述

名字\属性	重量/kg	价值
睡袋	15	15
绳子	3	7
折叠刀	2	10
火把	5	5
瓶子	9	8
葡萄糖	20	17

有一个可以装30kg的背包, 怎么装效益最高.

Code

# 背包问题求解(动态规划也是求解这种问题的一个好方法)

max_weights = 30

weights = np.array([15, 3, 2, 5, 9, 20])

values = np.array([15, 7, 10, 5, 8, 17])

## 随机初始化一个族群
features = len(weights)
# 初始样本数
init_sample_nums = np.random.randint(int(2 ** features / 3), 2 ** features)
samples = np.ones((init_sample_nums, features))
# 随机给定特性(基因)
for sample in range(init_sample_nums):
    probs = np.random.normal(0, 1, features) > 0.5
    random_sample = np.zeros((features, ))
    random_sample[probs] = 1
    samples[sample] = random_sample

# 定义函数去筛选
## 筛选, 去除超过总重量的
def remove_the_not_fitness_sample(samples):
    total_weights = np.sum(samples, axis=1)
    not_fitness = total_weights > 30
    # 保留下来的
    fitness = samples[~not_fitness]
    return fitness

# 评分函数
###  用于族内对比 
def compare_score(samples, remove=2):
    # 如果直接通过最高评分判断
    scores = np.zeros((len(samples, )))
    for sample_index in range(len(samples)):
        has_feature_index = samples[sample_index] == 1
        scores[sample_index] = np.sum(weights[has_feature_index])
    # 排分
    # 从小到大
    sort_scores = np.argsort(scores)
    # 默认剔除最小的两个
    return samples[sort_scores[2:]]
    
## 杂交
def crossover(samples, pairs=5, feature_prob=0.5):
    # 随机选取样本开始杂交
    # 每一次随机选择5对开始杂交
    features = len(samples[0])
    copy_samples = np.copy(samples)
    for pair_index in range(pairs):
        selected = np.random.choice(range(len(samples)), 2)
        # 每一个位置的Gene有多大的可能性会进行杂交
        cross_indexes = np.random.normal(0, 1, features) > feature_prob
        print(cross_indexes, selected)
        for cross_index in range(len(cross_indexes)):
            if cross_indexes[cross_index]:
                samples[selected[0]][cross_index] = samples[selected[1]][cross_index]
        copy_samples = np.append(copy_samples, samples[selected], axis=0)
    return copy_samples

## 变异
def mutation(samples, feature_unmutation_prob=0.8):
    # 每个基因(feature)的变异几率为0.2
    for sample in samples:
        for feature in range(len(sample)):
            if np.random.normal(0, 1, 1) > feature_unmutation_prob:
                sample[feature] = 0 if sample[feature] else 1
    return samples

# 执行生物论
fitness = remove_the_not_fitness_sample(samples)
filter_samples = compare_score(samples)
crossover_samples = crossover(filter_samples)
mutation_samples = mutation(crossover_samples)