Низкая автокорреляционная проблема двоичной последовательности? Устранение неполадок Python

Question

Я пытаюсь смоделировать эту проблему (подробнее об этом http://www.mpi -hd.mpg.de / personalhomes / bauke / LABS / index.php )

Я видел, что проверенный минимум для последовательности из 10 цифр равен 13. Однако мое приложение, похоже, получает 12 довольно часто. Это подразумевает какую-то ошибку в моей программе. Есть ли очевидная ошибка в том, как я смоделировал эти суммирования в этом коде?

def evaluate(self):
    self.fitness = 10000000000 #horrible practice, I know..
    h = 0

    for g in range(1, len(self.chromosome) - 1):
        c = self.evaluateHelper(g)
        h += c**2
    self.fitness = h

def evaluateHelper(self, g):
    """
    Helper for evaluate function.  The c sub g function.
    """
    totalSum = 0
    for i in range(len(self.chromosome) - g - 1):
        product = self.chromosome[i] * self.chromosome[(i + g) % (len(self.chromosome))]
        totalSum += product
    return totalSum

Answer 1

Я не могу заметить очевидную ошибку, но вы делаете вещи действительно сложными, так что, возможно, ошибка скрывается и прячется где-то. Как насчет

def evaluateHelper(self, g):
  return sum(a*b for a, b in zip(self.chromosome, self.chomosome[g:]))

это должно вернуть те же значения, которые вы вычисляете в этом тонком цикле (где я думаю, что часть % len... доказуемо избыточна). Точно так же метод evaluate кажется созревшим для аналогичного 1-го слоя. Но все равно ...

Существует потенциальная нечетная проблема: формулы в статье, на которую вы указываете, суммируют для g от 1 до N-1 , включая - вы используете range(1, len(...)-1), причем N-1 это исключено . Может ли это быть корнем проблемы, которую вы наблюдаете?

Answer 2

Ваш баг был здесь:

for i in range(len(self.chromosome) - g - 1):

Максимальное значение для i будет len(self.chromosome) - g - 2, поскольку диапазон является исключительным. Таким образом, вы не учитываете последнюю пару. Это в основном то же самое, что и ваша другая ошибка, просто в другом месте.