遗传算法

Question

我有一个简单的遗传算法，它必须达到陷阱函数的最佳点，定义如下：

def R(x):
    n = len(x)
    m = int(math.ceil(n/3))
    s = sum(x)

    if (s==n):
        return 2*n*n,
    elif (s<(n-m)):
        return n*s-B(x),
    else:
        return 0,

def B(x):
    i = 0
    n = len(x)
    mbs = 0

    # loops over all the variables
    while (i<n):

        k = i
        while (k<n and x[k]==0):
            k = k + 1

        #print("k="+str(k))

        j = k
        while (j<n and x[j]==1):
            j = j + 1

        if (j-k>mbs):
            mbs = j-k

        #print("j="+str(j))

        i = j

    return mbs

我想过要增加很多pop的大小，并“希望”用random.seed()在第一代生成最优的个体，然后只传播它的副本数量。为了做到这一点，我只会考虑一个锦标赛的选择，为锦标赛提供一个“大”窗口。

此解决方案仅适用于5和10个属性，但不适用于30个属性。关键是我不知道如何解决30个属性的情况。希望有人能帮助我。

Answer 1

我只能使用带有一些精英主义的简单GA ...

有了这个约束，你可以在不使用精英主义的情况下增加人口规模，但它不会很好地扩展。

zegkljan使用新奇搜索的想法似乎更好，而且可以在不改变搜索引擎的情况下使用。

只需更改适应度函数：

score(i) = (1 − ρ) · fit(i) + ρ · nov(i)

fit(i)是归一化的R函数：

fit(i) = (R(i) - Rmin) / (Rmax - Rmin)

nov(i)是标准化的新奇功能(你必须保存一个已经见过的人的档案，但这不需要修改‘引擎’)。

ρ ∈ [0,1]控制着适合性和新颖性的相对重要性。

有关这项技术的更多细节，请访问：When Novelty is not Enough (Giuseppe Cuccu，Faustino Gomez)

Answer 2

陷阱函数和类似函数对于GAs来说只是一个问题。

一种可能的解决方法可能是使用多目标进化算法(MOEA)，例如NSGA-II，并添加第二个目标，该目标将是个体的“唯一性”，例如与群体中其他个体的平均汉明距离，或a。这将迫使(某种)进化探索搜索空间的其他领域。

看看novelty search吧。它是关于完全放弃目标(为了推动进化，但你仍然使用它来寻找最佳解决方案)，而只使用“唯一性”(称为)新颖性来驱动搜索。