Генетический алгоритм - новым поколениям становится все хуже
Я реализовал простой Генетический Алгоритм для генерации коротких рассказов на основе басен Эзопа. Вот параметры, которые я использую:
Мутация: своп-мутация с одним словом с проверенной скоростью 0,01.
Кроссовер: поменяйте местами предложения в данной точке. ставка - 0,7
Выбор: выбор колеса рулетки - /questions/43628798/vyibor-ruletki-v-geneticheskih-algoritmah/43628803#43628803
Фитнес-функция: 3 разные функции. Наивысший балл каждого - 1,0. итоговый балл по фитнесу - 3,0.
Численность населения: поскольку я использую 86 басен Эзопа, я проверил численность населения с 50.
Начальная популяция: все 86 заказов на басни перетасовываются, чтобы сделать полную чушь. И моя цель - создать что-то значимое (по крайней мере, на определенном уровне) из этих утраченных басен.
Условие остановки: 3000 поколений. И результаты ниже:
Однако это все равно не дало положительного результата. Я ожидал сюжет, который идет на протяжении поколений. Есть идеи, почему у моего ГА результат хуже?
Обновление: как вы все предлагали, я использовал элитарность 10% текущего поколения, скопированного в следующее поколение. Результат остается прежним: 
Вероятно, я должен использовать выбор турнира.
5 ответов
Все вышеперечисленные ответы великолепны, и я посмотрю на них. Я добавлю свои мысли.
перегласовка
Ваша частота мутаций кажется хорошей, хотя с помощью генетических алгоритмов частота мутаций может вызвать много проблем, если это не правильно. Я уверен, что вы проверяете много других значений, чтобы быть уверенными.
С мутацией я бы использовал два типа мутаций. Тот, который заменяет слова другим из вашего словаря, и тот, который меняет два слова в предложении. Это стимулировало бы диверсификацию населения в целом и подтасовку слов.
Кроссовер
Я не знаю точно, как вы реализовали это, но одноточечный кроссовер, похоже, не будет настолько эффективным в этой ситуации. Я бы попытался реализовать кроссовер с n-точками, который намного лучше перетасовал ваши предложения. Опять же, я не уверен, как это реализовано, но просто замена не может быть лучшим решением. Например, если слово находится в первой точке, есть ли способ переместить его в другую позицию или оно всегда будет первым словом, если оно выбрано выбором?
Если порядок слов важен для выбранной вами задачи, простой кроссовер может быть не идеальным.
выбор
Опять же, это выглядит нормально, но я бы порекомендовал вам проверить другие варианты В прошлом я считал, что выбор рулетки на основе рангов намного успешнее.
фитнес
Это всегда самая важная вещь, которую следует учитывать в любом генетическом алгоритме, и, учитывая сложность вашей проблемы, я бы был вдвойне уверен, что она работает. Вы проверяли, что он работает с "известными" проблемами?
Численность населения
Ваша ценность кажется небольшой, но я видел, как генетические алгоритмы успешно работают с небольшими группами населения. Опять же, я бы поэкспериментировал с гораздо большим населением, чтобы увидеть, лучше ли ваши результаты
Пока что самое популярное предложение - реализовать элитарность, и я определенно рекомендую его. Это не должно быть много, даже просто лучшая пара хромосом в каждом поколении (хотя, как и во всем остальном, я бы попробовал разные значения).
Еще один полезный оператор для реализации - это выборка. Уничтожьте часть ваших самых слабых хромосом или ту, которая похожа на другие (или обе), и замените их новыми хромосомами. Это должно помочь предотвратить "устаревание" вашего населения, что на вашем графике выглядит так, как будто это может происходить. Мутация только делает так, чтобы разнообразить население.
Возможно, вы теряете лучшие комбинации, вы должны сохранять лучшие из каждого поколения без скрещивания (элиты). Кроме того, ваша функция выглядит достаточно стабильной, попробуйте другие типы мутаций, которые должны улучшиться.
Отбросьте от 5% до 10% своего населения, чтобы стать элитой, чтобы не потерять лучшее, что у вас есть.
Убедитесь, что ваш процесс отбора правильно настроен, если плохие кандидаты проходят через очень часто, это разрушит вашу эволюцию. Вы также можете застрять в локальном оптимуме, вам может понадобиться внести другие вещи в ваш геном, иначе вы не будете далеко ходить.
Перемещение предложений и слов, вероятно, не поможет вам продвинуться вперед, введение новых предложений или слов может быть интересным.
Если вы рассматриваете историю как точку x,y, а свою функцию оценки - как f(x,y), и вы пытаетесь найти максимум для f(x,y), но ваша мутация и перекрестный переход ограничены x -> y, y ->y, имеет смысл, что вы далеко не уедете. Конечно, в вашей задаче намного больше переменных, но без введения чего-то нового, я не думаю, что вы можете избежать локальности.
Как сказал @GettnDer, элитарность может сильно помочь.
Я бы предложил использовать другую стратегию отбора. У выбора колеса рулетки есть одна большая проблема: представьте, что лучший фитнес для индивида - это, например, 90% от суммы всех способностей. Тогда колесо рулетки вряд ли выберет других людей (см., Например, здесь). Стратегия отбора, которая мне нравится больше всего, - это выбор турнира. Это намного более устойчиво к большим различиям в значениях пригодности, и давление выбора можно очень легко контролировать.
Поиск новинок
Я также хотел бы попробовать поиск новизны. Это относительно новый подход в эволюционных вычислениях, когда вы делаете выбор не на основе фактической пригодности, а скорее на основе новизны, которая должна быть некоторой метрикой того, как человек отличается по своему поведению от других (но вы все еще вычисляете фитнес, чтобы поймать хороших). Особый интерес могут представлять комбинации классических алгоритмов, основанных на пригодности, и алгоритмов, основанных на новизне, таких как алгоритм Ж.-Б. Мура.
При работе с генетическими алгоритмами хорошей практикой является структурирование вашей хромосомы для отражения фактических знаний об оптимизируемом процессе.
В вашем случае, поскольку вы намереваетесь создавать истории, которые состоят из предложений, это может улучшить ваши результаты, если вы преобразуете свои хромосомы в структурированные фразы, строка <adjectives>* <subject> <verb> <object>* <adverbs>* (огромное упрощение здесь).
Каждому слову может быть присвоен класс. Например, Fox=subject, look =verb, grapes=object, и тогда ваш оператор кроссовера будет обмениваться элементами из той же категории между хромосомами. Кроме того, ваш оператор мутации может только вставить новые элементы соответствующей категории (например, прилагательное перед темой) или заменить слово на случайное слово в той же категории.
Таким образом, вы минимизируете количество бессмысленных хромосом (например, прекрасное виноградное дневное небо Фокса) и улучшите способность к генерации дискурса для вашего GA.
Кроме того, я согласен со всеми предыдущими комментариями: если вы используете элитарность и лучшая производительность снижается, то вы неправильно ее реализуете (обратите внимание, что в патологической ситуации она может оставаться постоянной в течение длительного периода времени).
Я надеюсь, что это помогает.