遗传算法解决vrp问题_遗传算法（Python）#3从零开始解决
OneMax问题
上⼀期
1. OneMax问题(OneMax Problem)
OneMax问题是遗传算法的⼊门问题，其内容是：如何使⼀段长度固定的⼆进制字符串所有位置上数字之和最⼤。
让我们⽤⼀个长度为5的⼆进制字符串为例：
10010 -> 和为2
00111 -> 和为3
11111 -> 和为5(最⼤值)
对⼀般⼈，显⽽易见，当所有位数都为1时，该字符串的和最⼤，但在我们⽤遗传算法解决该问题时，遗传算法本⾝并没有这样的知识。接
下来我们将不依靠任何遗传算法的包，从头开始⽤遗传算法解决OneMax问题。
2.问题的解决思路
⾸先，我们得把这个问题转换成⼀个遗传算法问题，即：我们得定义个体、种，选择、杂交、突变⽅法、适应度函数等。假设有⼀个长度为100的字符串，我们可以做出以下定义：
个体：个体即为问题的解，这个问题中个体可以直观的定义为⼀个长度为100列表(List)，列表上每个元素为0或1.
种：种即所有个体的合集，我们可以把种定义为所有个体组成的列表。
选择：使⽤锦标赛法(Tournament Selection)
杂交：使⽤单点杂交法(Singe-Point Crossover)
突变：使⽤位翻转突变法(Flip Bit Mutation)
适应度函数： 我们的⽬标是使字符串上所有数字之和最⼤，适应度函数可以直观的定义为列表中所有数字之和。
若对上述定义不太了解的，可以回看遗传算法系列的第⼆期。
3.⽤Python实现遗传算法
以下将分步骤解释每⼀部分的代码，完整代码在本⽂的最后可见。
3.0.准备⼯作
import randomimport matplotlib.pyplot as pltrandom.seed(39)
导⼊所有需要的包：
random pythonrandom： ⽤于⽣成随机数
matplotlib： ⽤于画图
random.seed: 确定种⼦(即随机状态)，这样每次运算我们都能得到同样的结果
3.1.定义个体和种
# 1. define individual and populationdef CreateIndividual(): return([random.randint(0,1) for _ in range(100)])def CreatePopulation(size): return([CreateI
CreateIndividual：个体即为⼀个长度为100的列表，每个元素(基因)为0或1。
CreatePopulation： 种即多个个体组成的列表。
3.2.定义选择、杂交、突变⽅法和适应度函数
3.2.1.选择
# 2.1. define select functiondef tournament(population,size): participants = random.sample(population,size) # evaluate function is defined in 3.4 winn
tournament：从种中随机抽取size个个体，从中选取适应度最⾼的个体。注意使⽤.copy以防同⼀个列表被多次引⽤。
select：为了保持种的⼤⼩不变，锦标赛的次数应与种中个体的数量相同
3.2.2.杂交
# 2.2. define mate functiondef SinglePointCrossover(ind1,ind2): loc = random.randint(0,len(ind1)-1) genes1 = ind1[loc:] genes2 = ind2[loc:] ind1[loc
SinglePointCrossover：单点杂交法的实现，两个个体交换随机位置及其后⾯的基因
mate：对种进⾏杂交，按⼀定概率每两个相邻的个体进⾏杂交probability参数：每次⽣成⼀个0⾄1之间的随机数，若随机数⼩于该概率，则进⾏杂交，否则对应的两个个体被克隆。
3.2.3.突变
# 2.3. define mutate functiondef flipOneGene(ind): loc = random.randint(0,len(ind)-1) ind[loc] = 1 - ind[loc] # 0->1 or 1->0 py())def mutat
flipOneGene：位翻转突变，个体上的⼀个随机基因进⾏突变。
mutate: 每个个体都以⼀定概率突变，若不突变，则该个体被克隆。
3.2.
4.适应度函数
# 2.4. define evaluate functiondef evaluate(individual): return(sum(individual))
OneMax的适应度函数就是列表中所有数字之和。
3.2.5.统计种数据
# 2.5. define statistical metrics to monitor algorithm performancedef population_score_max(population): return(max([evaluate(ind) for ind in population])
为了追踪算法的进度和发现算法中可能出现的错误，我们可以统计每次迭代中种适应度的最⼤值与均值。
3.3.运⾏遗传算法
# 3. Run genetic algorithmdef main( POPULATION_SIZE = 100, TOURNAMENT_SIZE = 3, CROSSOVER_PROB = 0.9, MUTATE_PROB = 0.1, M 在运⾏算法前，我们⾸先得定义⼀些参数：
种⼤⼩(Population Size):⼀般⽽⾔种越⼤，越容易在较⼩的代数内获得最优解，但代价是每⼀代的运算量会变⼤。
锦标赛⼤⼩(Tournament Size): 锦标赛的⼤⼩⼀般不要取的太⼤，否则种容易因过早地失去多样性⽽过早收敛。举⼀个极端例⼦，当种⼤⼩为100且锦标赛⼤⼩也为100时，第⼀次选择后所有的个体都会变成同⼀个个体，算法便很难再有改善的空间。
杂交概率(Crossover Probability)：杂交的概率应取⼀个较⼤的值，⽐如0.7,0.8,0.9等，具体数值应视具体情况⽽定。
突变概率(Mutate Probability)：突变概率应取⼀个较⼩的值，如0.05，0.1，0.2等，若取值太⼤，则种的随机性太强，不利于保存适应度⾼的个体，从⽽使遗传算法变成完全随机的搜索。
最⼤代数(Max Generation)：遗传算法不可能⽆⽌尽的运⾏下去，⼀般⽽⾔，我们都会设置终⽌条件，这个问题中，我们以最⼤代数为终⽌条件，当迭代进⾏到⼀定次数时算法终⽌。
在迭代过程中，每⼀代⾥我们都进⾏选择(select)，杂交(mate)，突变(mate)运算，并收集种的最⼤和平均适应度数据，⽤以追踪算法的进度，或发现算法中存在的问题。视问题⽽定，我们还可以记录下每代中适应度最⾼的个体(best individual)，以防⽌其因杂交和突变⽽消失。
最后，我们观察最优解与种的数据。
4.算法结果
我们成功获得了OneMax的最优解(所有位置上都是1)：[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1]
种的进化过程如下图所⽰，我们可以观察到种的进化速度由快到慢，且在61代左右停⽌进化，且在第58代时已经产⽣了最优解。
5. 完整代码
import randomimport matplotlib.pyplot as pltrandom.seed(39)# 1. define individual and populationdef CreateIndividual(): return([random.randint(0,1) for
4.⼩结
为了深⼊的解释遗传算法，本⽂中没有使⽤任何的遗传算法包来解决OneMax问题。⽽下⼀期，我们会介绍DEAP(Distributed Evolutionary Algorithm in Python)包，并在之后的⽂章⾥⽤DEAP框架来解决遗传算法问题。
本⼈近期刚开始写⽂章，欢迎交流学习！
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论