一、问题引入

        下面看一个求最优解的函数问题，这里告诉我们x的范围为(-1,2)，需要我们找到使f函数取得最大值的x，拿到这个方程，直接解还是比较困难的，所以我们使用遗传算法，找到尽可能接近最优解的值。

二、遗传算法的步骤

1.初始化

        设置进化代数计数器t=0，设置最大进化代数T，随机选择M个个体作为初始群体P(0)

2.个体评价

        计算群体P(t)中各个个体的适应度

3.选择运算

        将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

4.交叉运算

        将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子

5.变异运算

        将变异算子作用于群体。即是对群体中的个体串的某些基因作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

6.终止条件判断

        若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算

三、实现思路

1.编码的设计

        我们所需要求的x值是十进制的小数，我们要将其转换为类似基因的编码来作为遗传算法的个体，所以我的思路是将十进制的小数转换为二进制数，便于对其进行选择、交叉和变异。需要实现的是编码函数和解码函数。

2.适应度函数

        适应度函数即问题中给出的方程，只需要将二进制数解码为十进制小数带入方程中即可得到该个体的适应度。

3.选择函数

        选择函数是要选出群体中适应度高的，为了符合遗传的规律也不都是适应度高的，只是适应度高的被选择的概率大。为了实现选择我使用了轮盘赌的方法，何为轮盘赌呢，就是将所有个体放到一个轮盘上，适应度高的所占的轮盘面积大，然后转动轮盘，指针指到哪个个体就将其选择进入到下一轮交叉运算，直到选择出种群规模M个（这里要注意整个遗传算法自始至终种群规模是不变的都为M），这就导致选择到下一轮的个体会有重复的，即适应度高的个体可能被选择多次而适应性差的可能没有被选择。
        选择是遗传算法中选择到优异个体的关键步骤。

4.交叉函数

        交叉函数和变异函数都是为了保证种群个体的多样性，因为初始种群是随机选择的，可能并没有好的个体，如果没有交叉和变异仅仅是选择的话，最后也只是得到了初始种群的最优个体，所以需要交叉和变异产生更多样的个体才更可能在算法结束后得到优秀的个体。交叉是得到多样性个体的关键步骤。
        交叉函数主要实现思路是将选择出的M个个体中的某些个体（并不是所有的 ，需要设置交叉的概率，符合自然规律）进行两两的交叉，因为前面是将个体编码为二进制码，所以只需要随机确定一个交叉点，将交叉点后的片段进行交换（这只是一种方法，还可以将交叉 点前的进行交换，还可以确定两个交叉点，将交叉点中间的片段进行交换等），这里要注意编码是有编码空间的，交叉之后可能会超出编码空间，这里需要一个判断，如果超出了变量空间则重新进行交叉（这个可以视为自然界中基因进行交叉后个体死亡）。选择后的种群进入变异操作。

5.变异函数

        变异也是有一定变异概率的，这里我的做法是随机选择变异个体的一位，然后将其取反，如果超出了编码空间则重新进行变异直到落在编码空间中。

6.迭代

        将前五步不断迭代到T轮后，再选择该种群的最优个体，即可得到此最优问题的近似解

四、具体实现

下面是完整代码的连接，可以直接运行：
链接：https://pan.baidu.com/s/18c1Dw62I43Hrghhi0sZhzw
提取码：8ki9

1.编码解码函数

        为了代码的可移植性，我写了一个获得二进制位数的代码，只需要输入十进制的左右端点和有效位数，即可得到所需二进制编码的位数，这样这个代码就可以扩展到其他问题，而不仅仅局限于该问题

# 得到所需二进制的位数
def get_bit(start,end,decimal):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:return: 所需二进制的位数'''# 求所需要的二进制数的位数need = (end - start) * pow(10, decimal + 1)# 对2取对数，向上取整得到位数bit = int(math.log(need, 2)) + 1return bit

---

        将十进制的小数转换为二进制数，因为python中存不下22位的数，所以使用字符串进行表示

# 编码函数
def encode(start,end,decimal,bit,num):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param bit: 所需二进制的位数:param num: 需要转化的十进制数:return: 22位二进制数'''# # 求所需要的二进制数的位数# need = (end - start) * pow(10,decimal + 1)# # 对2取对数，向上取整得到位数# bit = int(math.log(need,2)) + 1# print(int(bit)+1)# 将数转化为二进制binary = bin(int((num + 1) * pow(10,decimal + 1)))# 除去前面的0bbinary = str(binary)[2:]# 将其补为22位while len(binary) < 22:binary = "0" + binaryreturn binary

---

        将二进制数解码转换为十进制数

# 解码函数
def decode(start,end,decimal,num):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要解码的二进制数:return: 原十进制数'''num = "0b" + numnum = int(num,2)num = num / pow(10,decimal + 1) -1# print(num)return num

2.适应度函数

        我的做法是先将二进制数解码然后带入函数中得到适应度

# 适应度函数
def fitness(start,end,decimal,num):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要求适应度函数值的二进制数:return: 适应度函数值'''# 首先解码x = decode(start,end,decimal,num)# 计算适应度函数值f = x * math.sin(10 * math.pi * x) + 2.0return f

3.选择函数

        这里使用适应度函数来设置轮盘，整个轮盘大小为1，每个个体在轮盘的起始位置为前面所有个体适应度求和再除以所有个体适应度的和，终止位置为包括该个体在内的前面所有个体适应度求和再除以所有个体适应度的和，这样该个体在轮盘所占的大小与其适应度成正比，通过随机生成(0,1)的小数来作为转盘的指针，落在哪个个体的区域就选择该个体。

# 选择函数
def select(start,end,decimal,population):""":param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要求适应度函数值的二进制数:param population: 种群，规模为M:return: 返回选择后的种群"""# 按照population顺序存放其适应度all_fitness = []for i in population:all_fitness.append(fitness(start,end,decimal,i))# print(fitness(start,end,decimal,i))# 适应度函数的总和sum_fitness = sum(all_fitness)# 以第一个个体为0号，计算每个个体轮盘开始的位置，position的位置和population是对应的all_position = []for i in range(0,len(all_fitness)):all_position.append(sum(all_fitness[:i+1])/sum_fitness)# print(all_position)# 轮盘赌进行选择# 经过选择后的新种群next_population = []for i in range(0,len(population)):# 生成0-1之间的随机小数ret = random.random()for j in range(len(all_position)):# 根据轮盘赌规则进行选择if all_position[j] > ret:# print(ret)# print(all_position[j])next_population.append(population[j])breakreturn next_population

4.交叉函数

        这里为了防止交叉和变异后的个体超出编码空间，所以写了一个判断交叉变异后的个体是否超出范围的函数

# 判断是否超出范围的函数
def whether_out(start,end,decimal,num):if start <=decode(start,end,decimal,num) <= end:return Trueelse:return False

---

        这里根据交叉概率选择需要交叉的个体数，因为选择出来的种群顺序本来就是随机的，所以只需要从第一个开始交叉，直到达到交叉的数目即可。

# 交叉函数
def cross(M,Pc,bit,start,end,decimal,next_population1):''':param M: 种群规模:param Pc: 交叉概率:param bit: 二进制的位数:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param next_population1: 选择后的种群:return: 交叉后的种群'''num = M * Pc# 计数器，判断是否交换次数达到num次count = 0i = 0# # 交叉后的种群# next_population2 = []# 由于选择后的种群本来就是随机的，所以让相邻两组做交叉，从第一组开始直到达到交叉概率停止while(i < M):# while(count < num):# 随机产生交叉点position = random.randrange(0,bit-1)# print(position)# print(position)# 将两个个体从交叉点断开tmp11 = next_population1[i][:position]tmp12 = next_population1[i][position:]tmp21 = next_population1[i+1][:position]tmp22 = next_population1[i+1][position:]# 重新组合成新的个体# print(next_population1[i])next_population1[i] = tmp11 + tmp22# print(next_population1[i])next_population1[i+1] = tmp21 + tmp12# 判断交叉后的个体是否超出范围，如果每超出则count+1，否则i不加，count不加if (whether_out(start,end,decimal,next_population1[i]) and whether_out(start,end,decimal,next_population1[i+1])):i += 2count += 1else:continueif count > num:break# print(count)return next_population1

5.变异函数

        这个函数是用来将指定位置的字符取反，即变异操作

# 取反字符串指定位置的数
def reverse(string,position):string = list(string)if string[position] == '0':string[position] = "1"else:string[position] = "0"return ''.join(string)

---

        这里判断是否变异是每个个体都产生一个(0,1)的随机小数，如果小于变异概率则对该个体进行变异

# 变异函数
def variation(M,Pm,start,end,decimal,bit,next_population2):''':param M: 种群规模:param Pm: 变异概率:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param bit: 二进制的位数:param next_population2: 交叉后的种群:return: 变异后的种群'''# i = 0for i in range(M):ret = random.random()# 生成0-1的随机数，如果随机数if ret < Pm:# 随机产生变异点position = random.randrange(0, bit)next_population2[i] = reverse(next_population2[i],position)# if (whether_out())while(whether_out(start,end,decimal,next_population2[i]) == False):# 如果超出范围则重新随机产生变异点，直到满足范围position = random.randrange(0, bit)next_population2[i] = reverse(next_population2[i], position)else:continuereturn next_population2

6.选择群体中最优个体

        在迭代T代的个体中选择适应度最高的个体

# 寻找群体中的最优个体
def search(start,end,decimal,population):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param population: 最终迭代后的群体:return: 最优个体'''# 记录函数值fit = []for i in population:fit.append(fitness(start,end,decimal,i))# 求出最大值所在的位置position = fit.index(max(fit))return decode(start,end,decimal,population[position])

7.主函数

        首先从(-1,2)的个体空间中随机选择M个个体作为初始种群，然后进行T次选择、交叉、变异得到最终的种群，然后选择出该种群中最优的个体

# 主函数
def main(M,T,Pc,Pm,start,end,decimal):""":param M: 种群规模:param T: 遗传运算的终止进化代数:param Pc: 交叉概率:param Pm: 变异概率:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:return:"""bit = get_bit(start,end,decimal)# 全集，包括所有编码后的个体all = []for i in range(-1 * pow(10,6), 2 * pow(10,6) + 1):all.append(encode(start,end,decimal,bit,i / pow(10,6)))i += 1# 第一次随机选择种群，规模为Tpopulation = random.sample(all, M)for i in range(T):# 进行选择操作population = select(start,end,decimal,population)# 进行交叉操作population = cross(M,Pc,bit,start,end,decimal,population )# 进行变异操作population  = variation(M,Pm,start,end,decimal,bit,population )# 最优个体final = search(start,end,decimal,population)print('%.5f' % final)

---

        入口函数，需要指定初始种群规模，遗传运算的终止进化代数，交叉概率，变异概率，左端点值，右端点值和有效位数这些参数也很重要，如果指定的参数不好则得不到好的结果。

if __name__ == '__main__':# test()main(200,200,0.6,0.005,-1,2,5)

        下面是运行的结果，大概在1.85左右，运行时间13秒，还能接受，说明整体复杂度还可以

一、问题引入

        下面看一个求最优解的函数问题，这里告诉我们x的范围为(-1,2)，需要我们找到使f函数取得最大值的x，拿到这个方程，直接解还是比较困难的，所以我们使用遗传算法，找到尽可能接近最优解的值。

二、遗传算法的步骤

1.初始化

        设置进化代数计数器t=0，设置最大进化代数T，随机选择M个个体作为初始群体P(0)

2.个体评价

        计算群体P(t)中各个个体的适应度

3.选择运算

        将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

4.交叉运算

        将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子

5.变异运算

        将变异算子作用于群体。即是对群体中的个体串的某些基因作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

6.终止条件判断

        若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算

三、实现思路

1.编码的设计

        我们所需要求的x值是十进制的小数，我们要将其转换为类似基因的编码来作为遗传算法的个体，所以我的思路是将十进制的小数转换为二进制数，便于对其进行选择、交叉和变异。需要实现的是编码函数和解码函数。

2.适应度函数

        适应度函数即问题中给出的方程，只需要将二进制数解码为十进制小数带入方程中即可得到该个体的适应度。

3.选择函数

        选择函数是要选出群体中适应度高的，为了符合遗传的规律也不都是适应度高的，只是适应度高的被选择的概率大。为了实现选择我使用了轮盘赌的方法，何为轮盘赌呢，就是将所有个体放到一个轮盘上，适应度高的所占的轮盘面积大，然后转动轮盘，指针指到哪个个体就将其选择进入到下一轮交叉运算，直到选择出种群规模M个（这里要注意整个遗传算法自始至终种群规模是不变的都为M），这就导致选择到下一轮的个体会有重复的，即适应度高的个体可能被选择多次而适应性差的可能没有被选择。
        选择是遗传算法中选择到优异个体的关键步骤。

4.交叉函数

        交叉函数和变异函数都是为了保证种群个体的多样性，因为初始种群是随机选择的，可能并没有好的个体，如果没有交叉和变异仅仅是选择的话，最后也只是得到了初始种群的最优个体，所以需要交叉和变异产生更多样的个体才更可能在算法结束后得到优秀的个体。交叉是得到多样性个体的关键步骤。
        交叉函数主要实现思路是将选择出的M个个体中的某些个体（并不是所有的 ，需要设置交叉的概率，符合自然规律）进行两两的交叉，因为前面是将个体编码为二进制码，所以只需要随机确定一个交叉点，将交叉点后的片段进行交换（这只是一种方法，还可以将交叉 点前的进行交换，还可以确定两个交叉点，将交叉点中间的片段进行交换等），这里要注意编码是有编码空间的，交叉之后可能会超出编码空间，这里需要一个判断，如果超出了变量空间则重新进行交叉（这个可以视为自然界中基因进行交叉后个体死亡）。选择后的种群进入变异操作。

5.变异函数

        变异也是有一定变异概率的，这里我的做法是随机选择变异个体的一位，然后将其取反，如果超出了编码空间则重新进行变异直到落在编码空间中。

6.迭代

        将前五步不断迭代到T轮后，再选择该种群的最优个体，即可得到此最优问题的近似解

四、具体实现

下面是完整代码的连接，可以直接运行：
链接：https://pan.baidu.com/s/18c1Dw62I43Hrghhi0sZhzw
提取码：8ki9

1.编码解码函数

        为了代码的可移植性，我写了一个获得二进制位数的代码，只需要输入十进制的左右端点和有效位数，即可得到所需二进制编码的位数，这样这个代码就可以扩展到其他问题，而不仅仅局限于该问题

# 得到所需二进制的位数
def get_bit(start,end,decimal):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:return: 所需二进制的位数'''# 求所需要的二进制数的位数need = (end - start) * pow(10, decimal + 1)# 对2取对数，向上取整得到位数bit = int(math.log(need, 2)) + 1return bit

---

        将十进制的小数转换为二进制数，因为python中存不下22位的数，所以使用字符串进行表示

# 编码函数
def encode(start,end,decimal,bit,num):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param bit: 所需二进制的位数:param num: 需要转化的十进制数:return: 22位二进制数'''# # 求所需要的二进制数的位数# need = (end - start) * pow(10,decimal + 1)# # 对2取对数，向上取整得到位数# bit = int(math.log(need,2)) + 1# print(int(bit)+1)# 将数转化为二进制binary = bin(int((num + 1) * pow(10,decimal + 1)))# 除去前面的0bbinary = str(binary)[2:]# 将其补为22位while len(binary) < 22:binary = "0" + binaryreturn binary

---

        将二进制数解码转换为十进制数

# 解码函数
def decode(start,end,decimal,num):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要解码的二进制数:return: 原十进制数'''num = "0b" + numnum = int(num,2)num = num / pow(10,decimal + 1) -1# print(num)return num

2.适应度函数

        我的做法是先将二进制数解码然后带入函数中得到适应度

# 适应度函数
def fitness(start,end,decimal,num):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要求适应度函数值的二进制数:return: 适应度函数值'''# 首先解码x = decode(start,end,decimal,num)# 计算适应度函数值f = x * math.sin(10 * math.pi * x) + 2.0return f

3.选择函数

        这里使用适应度函数来设置轮盘，整个轮盘大小为1，每个个体在轮盘的起始位置为前面所有个体适应度求和再除以所有个体适应度的和，终止位置为包括该个体在内的前面所有个体适应度求和再除以所有个体适应度的和，这样该个体在轮盘所占的大小与其适应度成正比，通过随机生成(0,1)的小数来作为转盘的指针，落在哪个个体的区域就选择该个体。

# 选择函数
def select(start,end,decimal,population):""":param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param num: 需要求适应度函数值的二进制数:param population: 种群，规模为M:return: 返回选择后的种群"""# 按照population顺序存放其适应度all_fitness = []for i in population:all_fitness.append(fitness(start,end,decimal,i))# print(fitness(start,end,decimal,i))# 适应度函数的总和sum_fitness = sum(all_fitness)# 以第一个个体为0号，计算每个个体轮盘开始的位置，position的位置和population是对应的all_position = []for i in range(0,len(all_fitness)):all_position.append(sum(all_fitness[:i+1])/sum_fitness)# print(all_position)# 轮盘赌进行选择# 经过选择后的新种群next_population = []for i in range(0,len(population)):# 生成0-1之间的随机小数ret = random.random()for j in range(len(all_position)):# 根据轮盘赌规则进行选择if all_position[j] > ret:# print(ret)# print(all_position[j])next_population.append(population[j])breakreturn next_population

4.交叉函数

        这里为了防止交叉和变异后的个体超出编码空间，所以写了一个判断交叉变异后的个体是否超出范围的函数

# 判断是否超出范围的函数
def whether_out(start,end,decimal,num):if start <=decode(start,end,decimal,num) <= end:return Trueelse:return False

---

        这里根据交叉概率选择需要交叉的个体数，因为选择出来的种群顺序本来就是随机的，所以只需要从第一个开始交叉，直到达到交叉的数目即可。

# 交叉函数
def cross(M,Pc,bit,start,end,decimal,next_population1):''':param M: 种群规模:param Pc: 交叉概率:param bit: 二进制的位数:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param next_population1: 选择后的种群:return: 交叉后的种群'''num = M * Pc# 计数器，判断是否交换次数达到num次count = 0i = 0# # 交叉后的种群# next_population2 = []# 由于选择后的种群本来就是随机的，所以让相邻两组做交叉，从第一组开始直到达到交叉概率停止while(i < M):# while(count < num):# 随机产生交叉点position = random.randrange(0,bit-1)# print(position)# print(position)# 将两个个体从交叉点断开tmp11 = next_population1[i][:position]tmp12 = next_population1[i][position:]tmp21 = next_population1[i+1][:position]tmp22 = next_population1[i+1][position:]# 重新组合成新的个体# print(next_population1[i])next_population1[i] = tmp11 + tmp22# print(next_population1[i])next_population1[i+1] = tmp21 + tmp12# 判断交叉后的个体是否超出范围，如果每超出则count+1，否则i不加，count不加if (whether_out(start,end,decimal,next_population1[i]) and whether_out(start,end,decimal,next_population1[i+1])):i += 2count += 1else:continueif count > num:break# print(count)return next_population1

5.变异函数

        这个函数是用来将指定位置的字符取反，即变异操作

# 取反字符串指定位置的数
def reverse(string,position):string = list(string)if string[position] == '0':string[position] = "1"else:string[position] = "0"return ''.join(string)

---

        这里判断是否变异是每个个体都产生一个(0,1)的随机小数，如果小于变异概率则对该个体进行变异

# 变异函数
def variation(M,Pm,start,end,decimal,bit,next_population2):''':param M: 种群规模:param Pm: 变异概率:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param bit: 二进制的位数:param next_population2: 交叉后的种群:return: 变异后的种群'''# i = 0for i in range(M):ret = random.random()# 生成0-1的随机数，如果随机数if ret < Pm:# 随机产生变异点position = random.randrange(0, bit)next_population2[i] = reverse(next_population2[i],position)# if (whether_out())while(whether_out(start,end,decimal,next_population2[i]) == False):# 如果超出范围则重新随机产生变异点，直到满足范围position = random.randrange(0, bit)next_population2[i] = reverse(next_population2[i], position)else:continuereturn next_population2

6.选择群体中最优个体

        在迭代T代的个体中选择适应度最高的个体

# 寻找群体中的最优个体
def search(start,end,decimal,population):''':param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:param population: 最终迭代后的群体:return: 最优个体'''# 记录函数值fit = []for i in population:fit.append(fitness(start,end,decimal,i))# 求出最大值所在的位置position = fit.index(max(fit))return decode(start,end,decimal,population[position])

7.主函数

        首先从(-1,2)的个体空间中随机选择M个个体作为初始种群，然后进行T次选择、交叉、变异得到最终的种群，然后选择出该种群中最优的个体

# 主函数
def main(M,T,Pc,Pm,start,end,decimal):""":param M: 种群规模:param T: 遗传运算的终止进化代数:param Pc: 交叉概率:param Pm: 变异概率:param start: 区间左端点值:param end: 区间右端点值:param decimal: 有效位数:return:"""bit = get_bit(start,end,decimal)# 全集，包括所有编码后的个体all = []for i in range(-1 * pow(10,6), 2 * pow(10,6) + 1):all.append(encode(start,end,decimal,bit,i / pow(10,6)))i += 1# 第一次随机选择种群，规模为Tpopulation = random.sample(all, M)for i in range(T):# 进行选择操作population = select(start,end,decimal,population)# 进行交叉操作population = cross(M,Pc,bit,start,end,decimal,population )# 进行变异操作population  = variation(M,Pm,start,end,decimal,bit,population )# 最优个体final = search(start,end,decimal,population)print('%.5f' % final)

---

        入口函数，需要指定初始种群规模，遗传运算的终止进化代数，交叉概率，变异概率，左端点值，右端点值和有效位数这些参数也很重要，如果指定的参数不好则得不到好的结果。

if __name__ == '__main__':# test()main(200,200,0.6,0.005,-1,2,5)

        下面是运行的结果，大概在1.85左右，运行时间13秒，还能接受，说明整体复杂度还可以