Jingcheng Xie
XieJingcheng
An undergraduate student in XDU

进化计算

一个晴天霹雳的消息，我可能下周就要开始期末考试了，虽然计算智能那些东西似乎在上学期已经覆盖过了，但是懂了会了不一定相当于会考试。同时我也是第一次尝试着用blog进行复习。

这章的主要内容其实在讲遗传算法，我复习的思路可能是先从进化计算讲起，然后简单介绍遗传算法，最后再详细地讲遗传算法里面详细的步骤和五个关键问题。

进化计算

首先捋清楚进化计算和遗传算法的关系，进化计算是一种广泛应用于解决优化和搜索问题的计算方法，而遗传算法则是进化计算的一种重要算法之一。

其次则是捋清楚进化计算要解决的是什么问题。

1，NP问题

在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、至今没有找到多项式时间算法解的一类问题，称之为NP类问题。

这里的多项式时间很容易看出这是什么东西。但是这背后的意义比较模糊，在我的理解里面多项式的时间意味着，随着n的增长，问题求解所需的步骤不会直接爆炸到极难求出。就比如旅行商问题中，如果穷举遍历的话，我们需要的次数就是 (n-1)!/2。如果有3个城市，则有3!=6种访问每个城市的次序。如果有4个城市，则有4!=24种次序。即使用计算机来计算，这种急剧增长的可能性的数目也远远超过计算资源的处理能力，这是个很大的开销。

image-20230522213200918

当然这只是穷举的算法，我们也有快速的算法，快速的算法或许会对这些有一定的改变。比如说快排和基数排序，可以把排序的时间复杂度，从\(O(n^{2})\)压到\(O(log(n))\)甚至\(O(n)\)。当然这里面关于稳定性、空间复杂度还有常数级之类的问题过于复杂，暂时不讨论。有需要的可以看看jw哥哥的奇观。

但是依然存在着一种问题，叫做hard问题。为所谓的Hard难问题,已有的快速算法与穷举算法相比较并没有明显的提高。

那么这时候，在面对无法接受的计算代价，我们可以很明智的放弃一部分精度，来换取一个可以接受的计算代价。进化计算就是这么一种方法。

准确的来说，进化计算的定义是：一种基于生物进化原理和自然选择的计算方法，用于解决复杂的优化和搜索问题。它是通过模拟生物进化的过程，通过遗传、变异和选择等操作来逐代地改进解的质量，从而逐步寻找最优解或接近最优解的解决方案。

人话来说，就是模拟生物进化的过程，一步步地优化那个近似解。在我的理解里面，类似于一个启发式搜索，根据当前种群的适应度为启发，近似去搜索它附近有可能的解。

2，新达尔文

在正式介绍进化算法前，我们还需要明白一个生物学上面的概念，虽然似乎关系不是很大，但是总算是受到了一点启发，至于有多少，我不好说。

新达尔文主义认为，只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史，这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。

这些可以和进化算法里面的算子进行对应，就拿遗传算法举例。

繁殖过程，就是遗传算法中的交叉和复制的过程。从父代中抽取一部分基因，进行交叉操作，产生一部分子代；同时直接复制一部分父代进入子代。这种算子，可以增加种群的多样性，也就是扩大搜索空间，向着目标解开始搜索。

变异过程，就是通过一个随机的过程，对基因进行一定的变异，它的目的也是增加种群的多样性扩大搜索空间。

竞争部分，则是不同解之间，通过适应度函数进行评估的竞争过程。目的则是模拟生物进化过程中，适者生存中的适者部分。

最后是选择，竞争中选取一部分解作为下一代的父代解，这里则是适者生存的生存部分，模拟竞争中处于优势的个体，拥有优先的交配权和生存机会。

3，爬山法

广义上面的进化算法主要包括遗传算法、进化策略、粒子群优化等算法，这里按下不表，我们先介绍一种简单的进化算法（为什么要介绍，简单说，就是要考……）：爬山法（Hill Climbing），爬山法是一种局部搜索算法，用于在解空间中寻找最优解或接近最优解的方法。

它的大体步骤如下:

  1. 初始化：生成一个随机解c；评估其适应度，f(c)。将c称为当前解。
  2. 对当前解进行突变 - 称其为突变体m。评估突变体的适应度，f(m)。
  3. 如果f(m)不比f(c)差，那么用m替换c；否则不做任何操作（实际上丢弃m）。
  4. 如果达到终止条件，则停止。否则，返回步骤1

image-20230522215720384

其实在这里，可以把它看成一个青春版本的遗传算法。它有突变，但是没有交叉，同时它的种群大小是一。

这样青春版的算法，就带来了一个问题：容易陷入局部最优。

局部最优，似乎就是优化问题里面一个老生常谈的问题。在这里面很好理解，由于它的种群很小，而且每一步只接受更好的点，这个点很难通过突变，跳出局部最优的空间。就像下面那个图：

image-20230522220036694

他的局部最优和全局最优之间，隔着深深的峡谷。

说的更加具体一点，主要的原因有三个：

  1. 局部最优解的吸引力：在某些问题中，解空间中存在多个局部最优解，这些解在局部范围内是最优的。爬山法在搜索过程中容易被这些局部最优解所吸引，而无法跳出局部最优解的区域。
  2. 邻域限制：爬山法只考虑当前解的邻域，并且仅选择其中最优的解作为下一步的移动方向。这限制了搜索范围，可能导致无法探索到整个解空间，错过了全局最优解的可能性。
  3. 局部搜索路径依赖：爬山法的搜索路径高度依赖于初始解。如果初始解选择不当或者陷入了局部最优解，那么爬山法将受限于这个初始点，并无法跳出局部最优解的区域。

随着，这些问题的出现，我们自然而然可以推导出我们的下一步，也就是正经的遗传算法。

遗传算法

后面我们即将开始简单的介绍一下基础的遗传算法，这是一个不那么实用的通用版本。至于为什么不实用，下一节再说。

面对的问题

遗传算法所要面对的问题，一般都是多峰性（Multimodality）、非连续性（Discontinuity）和多目标性（Multi-objectiveness）的。这几个词描述的就是问题空间中的不同特征和要求。

多峰性问题指的是问题空间中存在多个局部最优解，而优化目标是找到全局最优解。那这里需要算法可以跳出局部最优解，也就是需要算法可以有一个很大的跨越，或者是可以接受非单步最优（是这个意思，说法不准确）。

image-20230523160504284

非连续性问题指的是问题空间中存在离散或间断的解空间，其中某些解之间没有直接的过渡或连接。这就需要我们的算法，可以处理非连续问题，就比如用离散编码对问题进行编码。

多目标性，指的就是问题中存在多个冲突的优化目标，需要一种方法使得目标同时最优（当然这似乎是不可能的，但是可以选取到相对最优）同时，遗传算法中可以使用多目标适应度函数和多目标选择策略。

基本思想

最开始我们要明白的就是性状在表现型空间，基因在编码形空间，这是两个对应，但是不同的空间。这不仅意味着，我们需要进行编码工作，也意味着，在表现型空间中相邻的两个点，在编码空间不一定相邻。同时这种以决策变量的编码作为操作对象的方式，可以更好地引入遗传算子。

其次遗传算法的一些基本思想，其实就是可以和上面的问题进行一定的对应的。

首先对应的是他的多峰性，由于遗传算法是以种群为单位的，因此它的搜索是多点搜索。相对于传统优化算法的单点搜索，它可以更好地避开局部最小值。

同时面对问题的非连续性，遗传算法往往只利用目标值函数作为搜索信息（作为适应度函数之类的）。而传统算法中，总是会遇到利用函数的一阶甚至二阶导数信息，这对于很多不可导甚至不连续的函数是很麻的。当然，不利用导数信息也容易使得收敛速度更加感人。

最后一点是比较玄学的，概率搜索。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。这里的灵活性，在我的理解里面，就是他往往不是一直按照最优的方向前进，因此在牺牲掉一部分的收敛速度的同时，避免它陷入局部最小值。

image-20230528155125824

一个简单的GA算法示例

这个简单的GA算法示例，更加接近我们在上学期人工智能概论中学到的遗传算法。他给出了一个大体的框架，但是在实际应用中，对它里面的几个算子进行修补。

def simple_genetic_algorithm():
    t = 0  # 代数编号
    population = initialize_population()

    while t < generation_limit:
        # 评估适应度
        fitness_values = [evaluate_fitness(chromosome) for chromosome in population]

        # 选择和交叉操作
        offspring = []
        for _ in range(population_size):
            parent1 = random.choices(population, weights=fitness_values)[0]
            parent2 = random.choices(population, weights=fitness_values)[0]

            if random.random() < crossover_rate:
                child = crossover(parent1, parent2)
            else:
                child = parent1

            offspring.append(child)

        # 变异操作
        for i in range(population_size):
            if random.random() < mutation_rate:
                offspring[i] = mutation(offspring[i])

        # 更新种群
        population = selection(population, offspring)
        t += 1

    # 输出最佳解决方案
    best_chromosome = max(population, key=evaluate_fitness)
    best_solution = decode(best_chromosome)
    return best_solution

它的大致流程图如下：

image-20230528161203096

这里面的编码、解码、适应度评估、选择、交叉和变异的具体实现全部留下了空白。这就是我们后面要讲的几个关键问题。

五个关键问题

遗传算法的五个关键问题分别是：

  1. 遗传表示（Genetic Representation）：确定如何将问题的潜在解决方案进行遗传表示，通常使用染色体或个体来表示。
  2. 种群初始化（Population Initialization）：确定如何创建初始的种群，即一组潜在解决方案的初始集合。
  3. 适应度评估（Fitness Evaluation）：确定如何通过评估函数对每个个体的适应度进行评价，以衡量其在问题中的优劣程度。
  4. 遗传操作（Genetic Operators）：包括选择（Selection）、交叉（Crossover）、变异（Mutation）等遗传算子，用于改变后代个体的基因组成。
  5. 参数选择（Parameter Selection）：确定遗传算法使用的参数值，如种群大小、应用遗传操作的概率等。

1，遗传表示

遗传表示其实就是包括上面的编码解码的过程，在前面有简单的提过一嘴。遗传算法的一个特点就是个体存在码空间和解空间。遗传表示的解码和编码就是，基因在码空间和解空间之间的相互转化。遗传算子的操作在码空间中进行，评估和选择在解空间中进行。

决策变量的编码解码方式，直接影响了后面的几步，尤其是遗传操作算子的实现。我们先简单介绍一下二进制的编码问题。当然也可以是离散的取值或连续的数值。

二进制编码

二进制编码其实就是简单的01编码，首先我们要注意的一个问题就是编码精度问题。

Table of Contents