Недавно я познакомился с генетическими алгоритмами в этой статье MSDN , в которой он называет их комбинаторной эволюцией, но, похоже, это одно и то же, и я пытаюсь понять, как объединение двух потенциальных решений всегда приведет к новому решению, которое по крайней мере хорошо, как его родители.
Почему это так? Конечно, объединение может привести к чему-то худшему.
Насколько я понимаю, алгоритм основан на концепции, согласно которой, когда мужские и женские особи какого-либо вида дают потомство, эти потомки будут иметь характеристики обоих родителей. Некоторые комбинации будут лучше, некоторые хуже, а некоторые так же хороши. Те, кто лучше (для любого определения «лучше» уместно), имеют больше шансов выжить и произвести потомство, которые имеют улучшенные характеристики. Тем не менее, будут комбинации, которые являются более слабыми. Почему это не проблема с GA?
источник
However, there will be combinations that are weaker. Why isn't this an issue with GA?- Потому что более слабые комбинации отбрасываются.Why isn't this an issue with GA?Ну, это так, или, точнее, это может быть. Одним из многих (многих) параметров для оптимизации с использованием GA является размер популяции: если он слишком мал, вы можете производить только более слабых особей, но если он слишком высок, время вычислений, связанных с функцией пригодности, может быть слишком высоким.Ответы:
Генетический алгоритм пытается улучшить в каждом поколении путем отбора населения. Каждый член оценивается в соответствии с функцией пригодности, и только большая часть из них имеет право воспроизводить.
Вы правы, однако: нет никаких гарантий, что следующее поколение улучшит результаты своего предшественника.
Рассмотрим программу ласки Докинза : «эволюционирование» струны
"Methinks it is like a weasel". Начиная с совокупности случайных строк, функция пригодности оценивает наиболее близкое текстовое совпадение, которое возмущается для создания следующего поколения. При простом кроссоверном воспроизведении две строки с высокими показателями, которые объединены, могут очень легко произвести потомство с более низким результатом. Даже «бесполая» случайная мутация одной строки с высокой физической подготовкой может снизить физическую форму ребенка.Стоит отметить, я думаю, что это не обязательно недостаток. При таком виде поиска возникает идея локальных максимумов . Член населения может представлять решение, которое не является оптимальным результатом, но является лучшим, которое может быть достигнуто без ухудшения ситуации.
Представьте, что функция пригодности для программы ласки не только находит расстояние редактирования, но имеет некоторое понятие «слово» и проверяет, является ли последнее слово строки именем животного. Любое имя животного хорошо, но
"weasel"получает большой бонус.Теперь, что происходит, если
"Methinks it is like a walrus"развивается? Это хорошо. Не так хорошо, как конечная целевая строка, но лучше"Methinks it is like a walrut"или другие близкие вариации, которые могут быть достигнуты за один шаг мутации.Строка моржа является локальным максимумом, и поиск может застрять там, если программа не позволит ухудшить оценку следующего поколения.
источник
Мы не знаем, что станет лучше, мы знаем, что не станет хуже.
В каждом поколении состоит не только из лучших элементов, но и из лучших элементов - клонов, если хотите. Поскольку они все еще присутствуют, они получат те же очки, что и раньше. Это означает, что если ни одно из потомков не станет лучше, победители предыдущих поколений снова победят - и будут повторно видоизменены / размножены.
Подумайте: если индивид-прародитель представляет собой букву, например,
Aмутировавший ребенок определяется как добавление числа, напримерA1, перекрестные решения пишутся в скобках вокруг родителя, например,(A1B2)и пригодность любого индивидуального написанного после него - чем выше, тем лучше[12]Для демонстрации рассмотрим пул из 5, где мы оставляем лучшие 2. и заполняем 1 мутатом каждого, плюс кросс-порода
Поколение 1
A[10]B[5]C[4]D[3]E[1]Сохраните
A,Bпоскольку они являются лучшими двумя, и пополните остальные 3 слота потомкамиПоколение 2
A[10]B[5](AB)[7]A1[12]B1[4]Держите
A, и(AB), поскольку они лучшие 2 - это означает, что дедушкаAвсе еще будет в бассейне, так как большинство детей работают слабее3 поколение
A[10](AB)[12](A(AB))[14]A2[8](AB)1[13]Держите
(AB)1и(A(AB))- на этот раз бабушек и дедушек не содержали, так как двое их детей избивали их. Но если(AB1)бы выступил чуть хуже, мы бы сохранили(AB).Это продолжается до тех пор, пока счет не стабилизируется. Что означает, что вы достигли какого-то локального максимума (потенциально глобального максимума). Одна из причин, по которой это можно обнаружить, заключается в том, что одни и те же люди продолжают «клонироваться» в следующее поколение. (хотя для крупногабаритных задач, которые могут занять слишком много времени, лучше просто проверить улучшение <определенный допуск)
источник
В целом, генетические алгоритмы работают путем создания ряда (случайных) вариаций родителей в каждом поколении. Затем применяется некоторая функция выбора, и потомство, наиболее подходящее по этой функции, выживает. Таким образом, потомство не обязательно лучше, так как изменение является случайным, но в сочетании с отбором вы получаете улучшение с течением времени.
источник
Когда я изучал генетические алгоритмы в колледже, это объяснялось так:
Представьте, что решение - это комбинация «генов», где каждый ген влияет на то, насколько хорошим является решение в целом. Когда два решения связаны, их гены выбираются случайным образом от каждого родителя.
Теперь, если ген приводит, как правило, к хорошему решению, его частота в генофонде увеличивается. В крайнем случае, ген будет доминировать в популяции.
Поэтому, когда вы думаете о генетических алгоритмах (и об эволюции в целом), вы не должны думать о людях. Вы должны думать о генах и популяциях в целом. Даже если одно «лучшее» решение потеряно, это не значит, что его гены потеряны.
Существует также идея элитарности в генетических алгоритмах. Это означает, что лучшие решения всегда сохраняются между поколениями. Это может ускорить сходимость алгоритма, но алгоритму легче застрять в локальной оптимуме.
источник
Алгоритмы GA не являются детерминированными, они не гарантируют улучшения в каждом поколении, и они также не гарантируют, что найдут общий оптимум. Однако этап выбора ГА с использованием функции пригодности повышает вероятность того, что "хорошие решения" выживут.
источник