370
个编辑
更改
跳到导航
跳到搜索
第50行：
第50行： − 关于遗传算法的代码实现，可以参考[[使用pythony实现遗传算法]]这一词条。+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→代码实现
== 代码实现 ==
== 代码实现 ==
下面是一个用python实现的简单遗传算法示例，要解决的问题是求下面函数在区间<math>[0, 127]</math>内的最大值点。
<math> f(x) = x^2 - 50x </math>
下面代码仅作演示目的，没有遵循严格的编程规范，且可能有各种奇奇怪怪的bug，望体谅。
<syntaxhighlight lang="python">
'''
遗传算法最简单的示例实现
本例展示了如何使用遗传算法来求解使得下面函数值在区间[0, 127]上获得最大值的x
f(x) = x^2 - 50*x
按照我们在教科书得学到的方法，我们知道当 x=25 时，f(x) 的值最大
遗传算法有许多变体，我们使用最简单的二进制遗传算法，即把候选解表示为二进制字符
串，在这些二进制表示的“染色体”上做选择、交叉、变异的操作。
:file: GA.py
:author: Ricky Zhu
:email: rickyzhu@foxmail.com
:license: MIT
'''
import random
N_bits = 8 # 我们只求f(x)在区间[0, 127]上的最优解，因此只需要8个比特
def encode(num: int) -> str:
'''
把数字编码成二进制字符串。
注意这里假设num是从零开始数的整数，该函数不能用于对于任意区间、任意精度的编码。
'''
chrom = bin(num)[2:]
chrom = chrom.zfill(N_bits-len(chrom))
return chrom
def decode(gene: str) -> int:
'''
把二进制字符串解码成数字。
注意这里假设数字是从零开始数的整数，该函数不能用于对于任意区间、任意精度的解码。
'''
return int(gene, 2)
def selection(pop: list, fitness) -> (str, str):
'''
从群体中任意选择两个个体。
注意这里先把所有个体按照适应度排序，然后只在表现最好的一半中挑选，
相当于把表现不好的一半个体淘汰掉了。
'''
pop.sort(key=lambda x:fitness(decode(x)))
return random.sample(pop[:len(pop)//2], 2)
def crossover(chrom1: str, chrom2: str) -> (str, str):
'''单点交叉'''
point = random.randint(1, len(chrom1)-1)
return chrom1[:point]+chrom2[point:], chrom2[:point]+chrom1[point:]
def mutation(chrom: str, rate=0.05) -> str:
'''变异操作，染色体上每个碱基都有rate的概率翻转：从0变1，从1变0'''
for i in range(len(chrom)-1):
if random.random() < rate:
if chrom[i] == '0':
chrom = chrom[:i] + '1' + chrom[i+1:]
else:
chrom = chrom[:i] + '0' + chrom[i+1:]
return chrom
def _GA(fitness, pop):
'''遗传算法中的一次迭代的操作，从旧的一代中产生新的一代'''
new_pop = []
for i in range(len(pop)//2):
par1, par2 = selection(pop, fitness)
kid1, kid2 = crossover(par1, par2)
kid1 = mutation(kid1)
kid2 = mutation(kid2)
new_pop.append(kid1)
new_pop.append(kid2)
return new_pop
def GA(fitness, pop, runs=100):
'''遗传算法总流程'''
for i in range(runs):
pop = _GA(fitness, pop)
print('finial population:', [decode(i) for i in pop])
pop.sort(key=lambda x:fitness(decode(x))) # 选出表现最优的个体，作为最终解
return decode(pop[0])
def main():
'''主函数'''
# 定义问题，亦即适应度函数
def fitness_func(x):
return x**2 - 50*x + 100
# 随机初始化
init_pop = [random.randint(0, 127) for i in range(10)]
print('initial population:', init_pop)
# 把数字编码成二进制字符串
encoded_init_pop = [encode(i) for i in init_pop]
solution = GA(fitness_func, encoded_init_pop, 1000)
print('solution:', solution)
if __name__ == '__main__':
main()
</syntaxhighlight>
关于遗传算法的更高阶的使用，可以参考[[使用pythony实现遗传算法]]这一词条。
== 引用 ==
== 引用 ==