Эволюционный алгоритм достигает постоянного значения пригодности

Недавно я решил заняться эволюционным программированием и, следуя задаче, опубликованной на Rosetta Code, в которой говорится которые получают целевую строку, изменяют случайно сгенерированную строку, пока она не будет соответствовать цели. Мне удалось сделать мутации просто отлично, но я получаю неправильное значение для моей фитнес-функции, но я понятия не имею, почему. Моя фитнес-функция:

int
closeness (char* string, char* target, int n)
{
  int fit = 0, i, j;

  if (n == 0) return 0;

  if (!strcmp (string, target)) return 99999999; //if strings match, no need to iterate

    for (i = n - 1; i > 0; i--)
      {
        if ((string[i] == target[i])) fit++; //fit gets increased by each matching letter.
      }

  return fit;

И, чтобы не загромождать весь пост, вот полный код (Pastebin).
Приветствуется любая помощь, ребята .

Пример вывода (для целевой строки «meinks»):

best match: ecskyzfjh in generation 1, specimen 0 with fitness 0
best match: ecsuyzfjh in generation 2, specimen 0 with fitness 0
best match: ecsuyzfjh in generation 3, specimen 0 with fitness 0
best match: vc uyzfjh in generation 4, specimen 0 with fitness 0
best match: vc uyzfjh in generation 5, specimen 0 with fitness 0
best match: ve uyzfjh in generation 6, specimen 4 with fitness 1
best match: ve lyzfjh in generation 7, specimen 4 with fitness 1
best match: ve lyzfjh in generation 8, specimen 4 with fitness 1
best match: ve lyzfjh in generation 9, specimen 4 with fitness 1
best match: ve lyzfjh in generation 10, specimen 4 with fitness 1
best match: vg lyzfjh in generation 11, specimen 4 with fitness 1
best match: vgalyzfjh in generation 12, specimen 4 with fitness 1
best match: vgalyzfjh in generation 13, specimen 4 with fitness 1
best match: vgalyzfjh in generation 14, specimen 4 with fitness 1
best match: ugalyzfjh in generation 15, specimen 4 with fitness 1
best match: ugalyzrjh in generation 16, specimen 4 with fitness 1
best match: ugalyhtjh in generation 17, specimen 4 with fitness 1
best match: ugalyhtjh in generation 18, specimen 4 with fitness 1
best match: ugalyhtjh in generation 19, specimen 4 with fitness 1
best match: ugalyhtjz in generation 20, specimen 4 with fitness 1
best match: ugalyhtjz in generation 21, specimen 4 with fitness 1
best match: ugalyht l in generation 22, specimen 4 with fitness 1
best match: ugalyht l in generation 23, specimen 4 with fitness 1
best match: ugalyht l in generation 24, specimen 4 with fitness 1
best match:  galyyt l in generation 25, specimen 4 with fitness 1
best match:  galyyt l in generation 26, specimen 4 with fitness 1
best match:  yalyyt l in generation 27, specimen 4 with fitness 1
best match:  yalyytil in generation 28, specimen 4 with fitness 1
best match:  yalqytil in generation 29, specimen 4 with fitness 1
best match: pyajqytil in generation 30, specimen 4 with fitness 1
best match: pyajqytil in generation 31, specimen 4 with fitness 1
best match: pyajqytio in generation 32, specimen 4 with fitness 1
best match: pyajqytio in generation 33, specimen 4 with fitness 1
best match: pyazqytio in generation 34, specimen 4 with fitness 1
best match: pyazqytio in generation 35, specimen 4 with fitness 1
best match: pyazqytio in generation 36, specimen 4 with fitness 1
best match: pyazqptio in generation 37, specimen 4 with fitness 1
best match: pyazoztuo in generation 38, specimen 4 with fitness 1
best match: pyazoztuo in generation 39, specimen 4 with fitness 1
best match: pyazoztux in generation 40, specimen 4 with fitness 1
best match: hyazont x in generation 41, specimen 4 with fitness 1
best match: hyazont y in generation 42, specimen 4 with fitness 1
best match: hyazontay in generation 43, specimen 4 with fitness 1
best match: hyuzoltay in generation 44, specimen 4 with fitness 1
best match: hyuyoltay in generation 45, specimen 4 with fitness 1
best match: hyuyoltay in generation 46, specimen 4 with fitness 1
best match: hyuyoltay in generation 47, specimen 4 with fitness 1
best match: hvuyoltay in generation 48, specimen 4 with fitness 1
best match: hvuyoltay in generation 49, specimen 4 with fitness 1
best match: hvlyoltly in generation 50, specimen 4 with fitness 1
best match: hvlyoltly in generation 51, specimen 4 with fitness 1
best match: hvlynltlv in generation 52, specimen 4 with fitness 1
best match: hvlynltlv in generation 53, specimen 4 with fitness 1
best match: hvlynltlv in generation 54, specimen 4 with fitness 1
best match: hvlexltxv in generation 55, specimen 4 with fitness 1
best match: hvlexltev in generation 56, specimen 4 with fitness 1
best match: hvlexltev in generation 57, specimen 4 with fitness 1
best match: hvlexltev in generation 58, specimen 4 with fitness 1
best match: lvlexltev in generation 59, specimen 4 with fitness 1
best match: lvlexltem in generation 60, specimen 4 with fitness 1
best match: lvlexltem in generation 61, specimen 4 with fitness 1
best match: lqlexlpem in generation 62, specimen 4 with fitness 1
best match: lqlexdpem in generation 63, specimen 4 with fitness 1
best match: lylaxdpem in generation 64, specimen 4 with fitness 1
best match: lylaxdqem in generation 65, specimen 4 with fitness 1
best match: lylsxdqxm in generation 66, specimen 4 with fitness 1
best match: lylsidqxm in generation 67, specimen 4 with fitness 1
best match:  in generation 68, specimen 4 with fitness 1
best match:  in generation 69, specimen 4 with fitness 1
best match:  in generation 70, specimen 4 with fitness 1
best match:  in generation 71, specimen 4 with fitness 1
best match:  in generation 72, specimen 4 with fitness 1
best match: ynldqxq q in generation 73, specimen 4 with fitness 1
best match: ynhdqxq q in generation 74, specimen 4 with fitness 1
best match: znhdqxqkq in generation 75, specimen 4 with fitness 1
best match: znhdqxqqq in generation 76, specimen 4 with fitness 1
best match: znbdqxqqq in generation 77, specimen 4 with fitness 1
best match: znbjqxqqq in generation 78, specimen 4 with fitness 1
best match: zbbjqxqqq in generation 79, specimen 4 with fitness 1
best match: zbbjqxqpq in generation 80, specimen 4 with fitness 1
best match: zbbjqxqpq in generation 81, specimen 4 with fitness 1
best match:  bbjqxqpq in generation 82, specimen 4 with fitness 1
best match:  bbjqxqpq in generation 83, specimen 4 with fitness 1
best match:  bbjqxlpq in generation 84, specimen 4 with fitness 1
best match:  brjqxaaq in generation 85, specimen 4 with fitness 1
best match:  brjqxaaq in generation 86, specimen 4 with fitness 1
best match:  prfqmaaq in generation 87, specimen 4 with fitness 1
best match: xprfqmaaq in generation 88, specimen 4 with fitness 1
best match: xprfrzaad in generation 89, specimen 4 with fitness 1
best match: xpzfrxaad in generation 90, specimen 4 with fitness 1
best match: xpefrxaad in generation 91, specimen 4 with fitness 1
best match: xgefrxaad in generation 92, specimen 4 with fitness 1
best match: xgefruaod in generation 93, specimen 4 with fitness 1
best match: dgefruaod in generation 94, specimen 4 with fitness 1
best match: dgefruaod in generation 95, specimen 4 with fitness 1
best match: dge in generation 96, specimen 4 with fitness 1
best match:  in generation 97, specimen 4 with fitness 1
best match:  in generation 98, specimen 4 with fitness 1
best match:  in generation 99, specimen 4 with fitness 1
best match:  in generation 100, specimen 4 with fitness 1

Ожидаемая пригодность для большинства из них будет равна 0.


c evolutionary-algorithm fitness
person Pedro    schedule 22.07.2015    source источник
comment
Укажите образец входных данных, какое значение пригодности вы ожидаете и какое значение пригодности вы фактически получаете.   -  person Eric J.    schedule 22.07.2015
comment
Я не могу, потому что функция находится внутри цикла, который повторяется до тех пор, пока совпадающая строка не станет такой же, как исходная строка.   -  person Pedro    schedule 22.07.2015
comment
Значит, вы не можете использовать printf, чтобы распечатать его по мере его изменения, и вы также не можете использовать отладчик?   -  person Cobusve    schedule 22.07.2015
comment
Я подумал, что он имел в виду что-то вроде написанного. Я опубликую образец вывода   -  person Pedro    schedule 22.07.2015
comment
Использование n и strcmp() подозрительно. Зачем нужен n? Генерирует ли код нулевые символы в случайно сгенерированной строке?   -  person chux - Reinstate Monica    schedule 22.07.2015
comment
n необходим, чтобы убедиться, что я не превышаю размер строки, а также чтобы убедиться, что позиция мутации находится в пределах диапазона строки. Код не генерирует нулевые символы, а только те, которые входят в набор = abcdefghijklmnopqrstuvwxyz (это пробел в конце)   -  person Pedro    schedule 22.07.2015
comment
Попробуйте изменить цикл на: for (i=n; i--;)   -  person Pynchia    schedule 22.07.2015
comment
@Pynchia, это не сработало. Я все еще получаю те же ложные значения пригодности.   -  person Pedro    schedule 22.07.2015
comment
В порядке. Просто имейте в виду, что ваш цикл не рассматривал первый символ (индекс ноль)   -  person Pynchia    schedule 22.07.2015
comment
@Pynchia Большое спасибо, я не знал об этом. Я мог бы оставить симуляцию на ночь, чтобы посмотреть, есть ли улучшения.   -  person Pedro    schedule 22.07.2015
comment
Неа. Распечатайте строки и поместите их в цикл и посмотрите, что происходит в каждом цикле.   -  person Pynchia    schedule 22.07.2015
comment
@Pynchia Я получаю случайные строки, пригодность которых увеличивается случайным образом. Это то же самое, что и пример вывода, который я разместил выше.   -  person Pedro    schedule 23.07.2015
comment
В вашем коде есть несколько странных/неправильных деталей. Я не знаю, в чем проблема, но я могу сказать вам, что это будет глупо.   -  person Pynchia    schedule 23.07.2015
comment
@Pynchia, не могли бы вы пояснить, где я ошибся?   -  person Pedro    schedule 24.07.2015
comment
Почему вы повторяетесь в обратном порядке? Это просто вызывает путаницу ... Я бы отказался от логики n = 0 strcmp и просто зациклил от 0 до n-1, подсчитывая совпадения. Случай n=0 покрывается, потому что цикл сразу завершается. Если строки совпадают, вы вернете n, что является максимальным значением — нет необходимости в значении 999999. Вы можете полностью исключить n, просто выполняя цикл, пока не увидите нулевой символ — я предполагаю, что, поскольку вы использовали strcmp, они должны заканчиваться нулем.   -  person Katie    schedule 07.08.2015

Ответы (2)


arrow_upward
0
arrow_downward

Вызов вашей функции:

пригодность[i] = близость (образец[i], цель, размер);

и размер:

char target[] = "мне кажется"; размер = размер (цель);

Каждая строка в c заканчивается символом '\0', поэтому все строковые функции знают, где заканчиваются строки. Если вы начнете сравнивать две строки в позиции sizeof(target)-1, она сначала сравнит оба '\0' (которые логически равны), а затем сравнит остальные.

Кроме того, я бы изменил цикл на:

для (i = n - 1; i >= 0; i--)

В противном случае первый символ не будет сравниваться.

Дайте мне знать, если это решило вашу проблему. ;)

person dubi    schedule 07.08.2015

arrow_upward
0
arrow_downward

Вот быстрая реализация того, что я упомянул в своем комментарии выше. Это устраняет специальные проверки, потому что цикл все равно позаботится об этом. Нет необходимости в n, потому что ваше использование strcmp подразумевает, что строки заканчиваются нулем. Он не проверяет равенство и не выдает магическое значение, потому что вы уже знаете, что точное совпадение вернет максимальное значение.

Единственная потенциальная ошибка, о которой я могу думать, - это если вы не завершаете строки нулем в случаях, когда вы передали n = 0 раньше - у этого нет шансов спастись. Но если ваши пустые строки начинаются с нуля, тогда это безопасно.

Осторожно, я на самом деле не пытался компилировать или тестировать код.

int closeness(char* string, char* target)
{
    int fit = 0;
    int index = 0;
    while(string[index] && target[index])
    {
        if(string[index] == target[index])
            fit++;
        index++;
    }
    return fit;
}
person Katie    schedule 07.08.2015