Влияет ли определение точки остановки генетического алгоритма на цель алгоритма?

Википедия определяет точку окончания GA для этого:

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

Теперь, если он заканчивается, когда достигнут удовлетворительный уровень пригодности, и вы сами определяете этот уровень пригодности, почему бы вам просто не создать «идеальный» геном с самого начала, поскольку вы уже знаете характеристики этого идеального генома?

Я думаю, я просто немного запутался здесь. Я думал, что цель GA состоит в том, чтобы постоянно развиваться и показывать нам, возможно, даже лучшее решение, чем то, о чем мы думали, и наша фитнес-функция была просто чем-то, что помогло ему на этом пути, а не тем, что мы поставили на пьедестал в качестве завершения » идеальное "состояние. Разве это не разрушает смысл?

Функция пригодности оценивает вывод вашего алгоритма. Вполне возможно распознать идеальный вывод, когда вы его видите, но не знаете шагов для получения этого вывода из любого заданного ввода. Вот где генетические алгоритмы наиболее полезны.

Например, одно общее забавное приложение GA заключается в создании анимации, которая может эффективно перемещать виртуальное существо. Легко сказать, движется ли существо с определенной скоростью по относительно прямой линии. Это ваша фитнес-функция. Гораздо сложнее определить точную последовательность «мышечных» движений, чтобы заставить это сделать это.

Часто бывает, что вы можете определить пригодность решения, но не можете непосредственно определить само решение. Скажем, вы пытаетесь развить быстрых кроликов, и есть несколько генов, которые влияют на скорость кролика. Вы можете проверить скорость кролика, но перечислять все комбинации генов, связанных со скоростью, было бы нецелесообразно. В таком случае у вас может быть GA, который гонит кроликов и выводит самых быстрых. Вы можете сделать это навсегда, но вы, вероятно, предпочли бы остановиться, когда:

• Вы нашли кролика, который быстрее, чем X, или
• постепенное улучшение за n поколений упало ниже некоторого порога, или
• Вы разводили кроликов через m поколений

Весь смысл GA состоит в том, чтобы дать вам решение проблемы, которая имеет этот уровень пригодности. Это решение было бы очень трудно найти, используя другие более традиционные алгоритмы поиска, поэтому обычно вы используете GA в первую очередь.

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

Является ли ваше условие остановки определенным приемлемым уровнем пригодности или определенным ограничением по времени (запуск GA в течение максимального периода времени или ограниченное число поколений для критичных ко времени приложений, таких как поиск пути или приложения AI), обычно определяется вашей проблемой домен.

Интуитивно понятно, что цель генетического алгоритма - сформулировать алгоритмическое решение проблемы, которое не поддается прямому логическому анализу. Как только эта цель будет достигнута, ГА не нужно будет продолжать дальше.

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

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

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

Вот типичный пример из моего собственного опыта: при разработке одной из первых систем голосового набора нам было трудно найти алгоритм, позволяющий сопоставить произносимое имя с сохраненной копией того же имени. Нам сказали, что 95% точности выбора одного имени из 25 было достаточно. У нас был сохраненный корпус людей, произносящих 25 имен по 10 раз каждый.

Во-первых, мы разработали систему ввода, которая измеряла длину произносимого слова и частоту энергии в нескольких его нормированных кусках. Затем мы разработали алгоритм, который назначал веса для совпадений по этим параметрам и сравнивал два набора параметров по этим весам.

Теперь у нас был последний шаг - каким должно быть значение этих весов?

Мы создали 1000 случайных наборов весов и проверили их на корпусе. Мы выбросили 500, которые показали худшие результаты. Для оставшихся 500 мы дублировали каждый и в одном из них случайным образом подняли или опустили один из весов.

Мы повторяли этот процесс на компьютере около двух недель, пока он, наконец, не получил набор весов, отвечающий критерию точности 95%. Затем мы проверили это на данных не в корпусе. Это было примерно на 92%. Таким образом, мы потратили больше времени, чтобы достичь 98% точности в корпусе, и этот набор весов обеспечил 95% точности для данных, не входящих в корпус.

Итак, суть в том, что у вас должна быть функция пригодности для запуска генетического алгоритма. Если у вас нет возможности отличить хорошие гены от плохих, как вы можете убедиться, что хорошие гены размножаются, а плохие - нет?

Итерируйте, пока решение не будет сильно отличаться от предыдущей итерации. Для очень много, пожалуйста, поймите фиксированный допуск.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

В этом примере, если ваш фиксированный допуск был 0,01, тогда (n + 1) говорит вам остановиться, потому что abs (решение (n + 1) -разрешение (n)) <0,01.

Возобновление, вот когда ваш алгоритм может сказать: это не станет лучше!

Для быстрого ответа на главный вопрос: существует большая разница между знанием того, чего вы хотите достичь, и знанием того, как этого достичь.

Более подробно, например, с одной из самых популярных проблем, решаемых с помощью генетических / эволюционных алгоритмов, обычно на примере учебного примера в классе, нахождения оптимального маршрута на графике. Это часто используется в сети, чтобы найти самый дешевый маршрут от одного конца до другого. Определяя затраты (количество прыжков, стоимость каждого прыжка и т. Д.), Вы также определяете целевую стоимость (уровень физической подготовки), при которой вы довольны результатом. Ваш алгоритм может не найти лучшего, но он найдет алгоритмически приемлемый оптимум. Под этим я подразумеваю, что соотношение затрат и выгод при поиске лучшего ответа запрещено.

С GA / EA вы обнаружите, что это нормальное поведение, когда вы очень быстро находите 95% + оптимальный ответ, но сужение последних 5% экспоненциально дороже. Таким образом, теория заключается в том, что вы определяете приемлемый оптимум для достижения наилучшего результата за наименьшее количество времени. Поскольку стоимость поиска, скажем, верхних 1%, может перевесить его преимущества над верхними 5%, вы определяете свой приемлемый оптимум.

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

Есть некоторые исследования по исправлению ошибок в C с помощью генетических алгоритмов путем предоставления отрицательных и положительных тестовых случаев в качестве функций пригодности, а также неработающего кода в качестве входных данных. Это пример проблемы, которая может быть решена человеком, но проще для генетического алгоритма. Важно отметить:

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

Тем не менее, новые программы были эволюционировали с нуля, но только не в С. несколько нетривиальных программ , написанных в Malbolge эзотерического языка программирования имеют все (насколько мне известно) эволюционировали, не написано. Язык слишком сложен для использования программистом и слишком сложен, чтобы эффективно выводить программы из одной логики, поэтому большинство программ, написанных на нем, были созданы генетическими алгоритмами. Функция пригодности - это, как правило, расстояние редактирования до ожидаемого результата.

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