遗传算法模仿了生物遗传进化的过程,可以在给定范围内搜索最优解。遗传算法的设计一般包括参数编码、初始群体的设定、适应度函数的设计、遗传操作设计(选择、交叉、变异)、控制参数设定等。
0.问题
在这里,我们基于python使用遗传算法尝试搜索函数
\(y = -x^2+2x+5\)
在区间\([0,63]\)内的最大值,简便起见只取区间内的整数。
1.参数编码
对于本问题,用6个二进制位即可表示0~63的所有整数,其中每组编码可视为一条染色体或个体,具体编码如下:
\([0,0,0,0,0,0,0]\)
...
\([1,1,1,1,1,1,1]\)
2.初始群体的设定
在这里假设种群一直维持有4条染色体,随机初始化后如下:
\([0,0,1,0,1,0,0]\)
\([1,0,0,1,0,0,0]\)
\([0,0,1,0,0,0,1]\)
\([0,1,0,0,0,1,0]\)
3.适应度函数的设计
适应度函数在这里直接取函数的值,即函数值越大其适应度越高。
4.遗传操作设计
4.1选择
在这个阶段直接舍弃掉适应度低的两条染色体,选择适应度高的两条染色体来产生新的染色体。
4.2交叉
假设上一步选择的两条染色体为:
\([0,0,0,0,0,0,0]\)
\([1,1,1,1,1,1,1]\)
交叉时首先随机选择交叉点,比如为第三个,则交叉后产生的的染色体为:
\([0,0,0,1,1,1,1]\)
\([1,1,1,0,0,0,0]\)
4.1变异
对上一步新产生的染色体,首先以一定的变异率来决定是否变异,然后同样的随机选择变异点,将该位置基因反转。最后再将产生的两条新染色体添加进种群中,这样就完成了一次遗传迭代操作,反复进行迭代就有可能搜索到最优解。
5.python代码参考
import random
class Chromosome(object):
def __init__(self, chrom=None):
# 随机初始化一个染色体
if chrom == None:
self.chrom = []
for _ in range(6):
_num = random.randint(0, 1)
self.chrom.append(_num)
# 直接赋值一个染色体
else:
self.chrom = chrom
# 适应度函数
def fit_score(self):
_str = ''
for i in self.chrom:
_str += str(i)
_num = int(_str, 2)
return 5 - _num * _num + _num * 2
# 交叉函数
def cross(self, Chrom, cross_rate):
cross_idx = random.randint(0, 5)
child_chrom1 = self.chrom[:cross_idx] + Chrom.chrom[cross_idx:]
child_chrom2 = Chrom.chrom[:cross_idx] + self.chrom[cross_idx:]
return Chromosome(child_chrom1), Chromosome(child_chrom2)
# 变异函数
def vary(self, vary_rate):
_num = random.randint(1, 10)
if _num <= 10*vary_rate: # 模拟变异率
cross_idx = random.randint(0, 5)
if self.chrom[cross_idx] == 0:
self.chrom[cross_idx] = 1
else:
self.chrom[cross_idx] = 0
def one_iter(population, cross_rate=0.8, vary_rate=0.2):
# 选择使用排序法 取适应度最高值
# 交叉使用随机单点交叉 cross_rate=交叉率 (暂未开启)
# 变异使用随机反转变异 vary_rate=变异率
population.sort(key=lambda x:x.fit_score(), reverse=True)
population.pop()
population.pop()
child_chrom1, child_chrom2 = population[0].cross(population[1], cross_rate)
child_chrom1.vary(vary_rate)
child_chrom2.vary(vary_rate)
population.append(child_chrom1)
population.append(child_chrom2)
def main():
population = [Chromosome(), Chromosome(), Chromosome(), Chromosome()]
for _ in range(50):
one_iter(population)
population.sort(key=lambda x: x.fit_score(), reverse=True)
print(population[0].chrom, population[0].fit_score())
if __name__ == '__main__':
main()
6.结语
上述内容只是对遗传算法最浅显的解释,每种操作都尽可能简化,如需深入了解,还请参考其他内容。