使用离散值最小化函数的遗传算法
Genetic Algorithm to Minimize Function using Discrete Values
我正在尝试求解 6 个离散值的最佳组合，这些值取 2 到 16 之间的任意数字，这对我来说 return 函数的最小函数值 = 1/x1 + 1/x2 + 1/x3 ... 1/xn
约束是函数值必须小于 0.3
我遵循了描述如何针对此类问题实施 GA 的在线教程，但我得到了错误的结果。没有约束，最佳值应该是最大值，在这个问题中是 16，但我没有得到
import random
from operator import add
def individual(length, min, max):
'Create a member of the population.'
return [ random.randint(min,max) for x in xrange(length) ]
def population(count, length, min, max):
"""
Create a number of individuals (i.e. a population).
count: the number of individuals in the population
length: the number of values per individual
min: the minimum possible value in an individual's list of values
max: the maximum possible value in an individual's list of values
"""
##print 'population',[ individual(length, min, max) for x in xrange(count) ]
return [ individual(length, min, max) for x in xrange(count) ]
def fitness(individual, target):
"""
Determine the fitness of an individual. Higher is better.
individual: the individual to evaluate
target: the target number individuals are aiming for
"""
pressure = 1/sum(individual)
print individual
return abs(target-pressure)
def grade(pop, target):
'Find average fitness for a population.'
summed = reduce(add, (fitness(x, target) for x in pop))
'Average Fitness', summed / (len(pop) * 1.0)
return summed / (len(pop) * 1.0)
def evolve(pop, target, retain=0.4, random_select=0.05, mutate=0.01):
graded = [ (fitness(x, target), x) for x in pop]
print 'graded',graded
graded = [ x[1] for x in sorted(graded)]
print 'graded',graded
retain_length = int(len(graded)*retain)
print 'retain_length', retain_length
parents = graded[:retain_length]
print 'parents', parents
# randomly add other individuals to
# promote genetic diversity
for individual in graded[retain_length:]:
if random_select > random.random():
parents.append(individual)
# mutate some individuals
for individual in parents:
if mutate > random.random():
pos_to_mutate = random.randint(0, len(individual)-1)
# this mutation is not ideal, because it
# restricts the range of possible values,
# but the function is unaware of the min/max
# values used to create the individuals,
individual[pos_to_mutate] = random.randint(
min(individual), max(individual))
# crossover parents to create children
parents_length = len(parents)
desired_length = len(pop) - parents_length
children = []
while len(children) < desired_length:
male = random.randint(0, parents_length-1)
female = random.randint(0, parents_length-1)
if male != female:
male = parents[male]
female = parents[female]
half = len(male) / 2
child = male[:half] + female[half:]
children.append(child)
parents.extend(children)
return parents
target = 0.3
p_count = 6
i_length = 6
i_min = 2
i_max = 16
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
p = evolve(p, target)
print p
fitness_history.append(grade(p, target))
for datum in fitness_history:
print datum
预期结果是 2 到 16 之间的值的组合，return是函数的最小值，同时遵守函数不能大于 0.3 的约束。
您执行试探法的顺序对于遗传算法来说是非常不寻常的。通常，genetic algorithm 遵循以下步骤：
- Select N*2 Parents 使用 roulette-wheel 或锦标赛选择
- 使用交叉
将 N*2 parent 减少到 N children
- 稍微改变其中一些 N children
- 使用世代更替构建下一代，可能采用精英主义（保留旧人口的最佳解决方案）
- 重复 1
另一种略有不同的方法称为 evolution strategy (ES)，但其执行方式也不同。 None 我所知道的进化算法在最后使用交叉。在 ES 中，交叉用于计算种群的质心个体，并将其用作变异的基础。然后质心的所有突变体形成下一代。在 ES 中，下一代也是仅使用新一代（逗号选择 - 要求您对当前 parent 代进行过采样）或使用旧一代和新一代（加上选择）形成的。 ES 执行
- 从总体计算质心解
- 通过改变质心生成 lambda 后代解决方案（通常，在 ES 中，您会在搜索过程中调整 "mutation strength"）
- 使用 lambda 后代或 lambda 后代 + mu 解决方案通过排序和取最好的替换下一代（mu 解决方案）
- 重复 1
在您实施的算法中，两者都不是，您似乎没有施加足够的选择压力来将搜索推向更好的区域。仅仅对种群进行排序并取一个精英子集并不一定是遗传算法的思想。你必须从整个人群中选择 parents，但要给更好的个体一些偏见。通常这是使用适应度比例或锦标赛选择来完成的。
将随机个体引入搜索也不符合标准。您确定您的问题需要多样性保护吗？它会提供比没有更好的结果还是可能给你更差的结果？一个简单的替代方法是检测收敛并重新启动整个算法，直到达到停止标准（超时、生成的个体数量等）。
交叉和变异都可以。但是，在 single-point 交叉中，您通常会随机选择交叉点。
另一个观察：您描述的适应度函数与您代码中实现的适应度函数不匹配。
1/(x1 + x2 + ... + xn)
不等于
1/x1 + 1/x2 + ... + 1/xn
我正在尝试求解 6 个离散值的最佳组合，这些值取 2 到 16 之间的任意数字，这对我来说 return 函数的最小函数值 = 1/x1 + 1/x2 + 1/x3 ... 1/xn
约束是函数值必须小于 0.3
我遵循了描述如何针对此类问题实施 GA 的在线教程，但我得到了错误的结果。没有约束，最佳值应该是最大值，在这个问题中是 16，但我没有得到
import random
from operator import add
def individual(length, min, max):
'Create a member of the population.'
return [ random.randint(min,max) for x in xrange(length) ]
def population(count, length, min, max):
"""
Create a number of individuals (i.e. a population).
count: the number of individuals in the population
length: the number of values per individual
min: the minimum possible value in an individual's list of values
max: the maximum possible value in an individual's list of values
"""
##print 'population',[ individual(length, min, max) for x in xrange(count) ]
return [ individual(length, min, max) for x in xrange(count) ]
def fitness(individual, target):
"""
Determine the fitness of an individual. Higher is better.
individual: the individual to evaluate
target: the target number individuals are aiming for
"""
pressure = 1/sum(individual)
print individual
return abs(target-pressure)
def grade(pop, target):
'Find average fitness for a population.'
summed = reduce(add, (fitness(x, target) for x in pop))
'Average Fitness', summed / (len(pop) * 1.0)
return summed / (len(pop) * 1.0)
def evolve(pop, target, retain=0.4, random_select=0.05, mutate=0.01):
graded = [ (fitness(x, target), x) for x in pop]
print 'graded',graded
graded = [ x[1] for x in sorted(graded)]
print 'graded',graded
retain_length = int(len(graded)*retain)
print 'retain_length', retain_length
parents = graded[:retain_length]
print 'parents', parents
# randomly add other individuals to
# promote genetic diversity
for individual in graded[retain_length:]:
if random_select > random.random():
parents.append(individual)
# mutate some individuals
for individual in parents:
if mutate > random.random():
pos_to_mutate = random.randint(0, len(individual)-1)
# this mutation is not ideal, because it
# restricts the range of possible values,
# but the function is unaware of the min/max
# values used to create the individuals,
individual[pos_to_mutate] = random.randint(
min(individual), max(individual))
# crossover parents to create children
parents_length = len(parents)
desired_length = len(pop) - parents_length
children = []
while len(children) < desired_length:
male = random.randint(0, parents_length-1)
female = random.randint(0, parents_length-1)
if male != female:
male = parents[male]
female = parents[female]
half = len(male) / 2
child = male[:half] + female[half:]
children.append(child)
parents.extend(children)
return parents
target = 0.3
p_count = 6
i_length = 6
i_min = 2
i_max = 16
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
p = evolve(p, target)
print p
fitness_history.append(grade(p, target))
for datum in fitness_history:
print datum
预期结果是 2 到 16 之间的值的组合，return是函数的最小值，同时遵守函数不能大于 0.3 的约束。
您执行试探法的顺序对于遗传算法来说是非常不寻常的。通常，genetic algorithm 遵循以下步骤：
- Select N*2 Parents 使用 roulette-wheel 或锦标赛选择
- 使用交叉 将 N*2 parent 减少到 N children
- 稍微改变其中一些 N children
- 使用世代更替构建下一代，可能采用精英主义（保留旧人口的最佳解决方案）
- 重复 1
另一种略有不同的方法称为 evolution strategy (ES)，但其执行方式也不同。 None 我所知道的进化算法在最后使用交叉。在 ES 中，交叉用于计算种群的质心个体，并将其用作变异的基础。然后质心的所有突变体形成下一代。在 ES 中，下一代也是仅使用新一代（逗号选择 - 要求您对当前 parent 代进行过采样）或使用旧一代和新一代（加上选择）形成的。 ES 执行
- 从总体计算质心解
- 通过改变质心生成 lambda 后代解决方案（通常，在 ES 中，您会在搜索过程中调整 "mutation strength"）
- 使用 lambda 后代或 lambda 后代 + mu 解决方案通过排序和取最好的替换下一代（mu 解决方案）
- 重复 1
在您实施的算法中，两者都不是，您似乎没有施加足够的选择压力来将搜索推向更好的区域。仅仅对种群进行排序并取一个精英子集并不一定是遗传算法的思想。你必须从整个人群中选择 parents，但要给更好的个体一些偏见。通常这是使用适应度比例或锦标赛选择来完成的。
将随机个体引入搜索也不符合标准。您确定您的问题需要多样性保护吗？它会提供比没有更好的结果还是可能给你更差的结果？一个简单的替代方法是检测收敛并重新启动整个算法，直到达到停止标准（超时、生成的个体数量等）。
交叉和变异都可以。但是，在 single-point 交叉中，您通常会随机选择交叉点。
另一个观察：您描述的适应度函数与您代码中实现的适应度函数不匹配。
1/(x1 + x2 + ... + xn)
不等于
1/x1 + 1/x2 + ... + 1/xn