我试图解决6个离散值的最佳组合,它们取2到16之间的任何数字,这将返回函数的最小函数值= 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之间的值的组合,它返回函数的最小值,同时遵守函数不能大于0.3的约束。
对于遗传算法,执行启发式的顺序非常不寻常。通常,genetic algorithm
遵循以下步骤:
另一种稍微不同的方法叫做evolution strategy
(ES),但它也表现不同。我所知道的最近都没有使用交叉的进化算法。在ES中,交叉用于计算群体的质心个体并将其用作变异的基础。然后,质心的所有突变体都形成下一代。在ES中,下一代是使用新一代(逗号选择 - 要求您对当前父代进行过采样)或使用新旧代(加选择)形成的。 ES执行
在您实现的算法中,两者都没有,您似乎没有应用足够的选择压力来推动搜索更好的区域。只是对群体进行排序并获取精英子集不一定是遗传算法的想法。你必须从整个人口中选择父母,但对更好的个人给予一些偏见。通常,这是使用健身比例或锦标赛选择来完成的。
将随机个体引入搜索也是不标准的。您确定要为您的问题保留多样性吗?它是否提供比没有更好的结果,或者可能会给你更糟糕的结果?一个简单的替代方法是检测收敛并执行整个算法的重启,直到达到停止标准(超时,生成的个体数量等)。
交叉和变异是可以的。但是,在单点交叉中,通常会选择交叉点随机。
另一个观察结果:描述中的适应度函数与代码中实现的函数不匹配。
1/(x1 + x2 + ... + xn)
不等于
1/x1 + 1/x2 + ... + 1/xn