时间戳

首页 > 解决方案 > 使用离散值最小化函数的遗传算法

python - 使用离散值最小化函数的遗传算法

问题描述

我正在尝试求解 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 的约束。

标签： pythonoptimizationgenetic-algorithmminimizationevolutionary-algorithm

解决方案

执行启发式的顺序对于遗传算法来说是非常不寻常的。通常，agenetic algorithm遵循以下步骤：

  1. 使用轮盘赌或锦标赛选择选择 N*2 家长
  2. 使用交叉将 N*2 个父母减少为 N 个孩子
  3. 稍微改变其中的一些 N 个孩子
  4. 使用代际更替构建下一代，可能带有精英主义（保留来自老年人口的最佳解决方案）
  5. 重复 1

另一种略有不同的方法称为evolution strategy(ES)，但它的性能也不同。我所知道的所有进化算法最后都没有使用交叉。在 ES 中，交叉用于计算种群的质心个体并将其用作变异的基础。然后质心的所有突变体形成下一代。在 ES 中，也可以使用仅新一代（逗号选择 - 要求您对当前父代过采样）或使用新旧一代（加上选择）形成下一代。ES 执行

  1. 从总体计算质心解
  2. 通过改变质心生成 lambda 后代解决方案（通常，在 ES 中，您将在搜索过程中调整“突变强度”）
  3. 使用 lambda 后代或 lambda 后代 + mu 解决方案替换下一代（mu 解决方案），方法是排序并取最好的
  4. 重复 1

在您实现的算法中（两者都不是），您似乎没有施加足够的选择压力来将搜索推向更好的区域。仅对总体进行排序并获取精英子集不一定是遗传算法的想法。您必须从整个人口中选择父母，但对更好的个人有一些偏见。通常这是使用适应度比例或锦标赛选择来完成的。

将随机个体引入搜索也是不标准的。你确定你的问题需要多样性保护吗？它是否比没有提供更好的结果，或者可能给你带来更糟糕的结果？一个简单的替代方法是检测收敛并重新启动整个算法，直到达到停止标准（超时、生成的个体数量等）。

交叉和突变都可以。但是，在单点交叉中，您通常会随机选择交叉点。

另一个观察结果：您描述中的适应度函数与代码中实现的适应度函数不匹配。

1/(x1 + x2 + ... + xn)

不相等

1/x1 + 1/x2 + ... + 1/xn

推荐阅读