Генетический алгоритм
Что человечество научилось делать хорошо, так это заимствовать. В этот раз заимствование произошло у самой природы. Есть класс алгоритмов, которые называются метаэвристическими - это те, которые подглядели у природы и хорошо зашло в применении. Так появился генетический алгоритм в основе которого лежат целые популяции особей - решений. Этот алгоритм по праву считается универсальным, т.к. справляется с задачами из различных областей. Давайте решим вашу задачу (скажу сразу, что в разных источниках можно найти небольшие отклонения в именовании). Для начала сформируйте решение вашей задачи в виде вектора (набор цифр, например), такой вектор называется набором генов (каждая цифра вектора - это значение спрятанное в гене). Вектор - это хромосома, хромосом может быть несколько, но если ваш вектор целиком описывает решение, то хромосома всего одна. Хромосомы определяются генотипом, т.е. генотип обладает одной или более хромосом. В генетическом алгоритме на первом шаге создается первое поколение или популяция, которое представляет из себя набор особей с разнообразными генотипами. Из каждого, в том числе и первого, поколения выбираются лучшие особи. Способов выбора множество, список их вы найдете по запросу GA Selection. В зависимости от выбранного подхода к селекции (отбору), в дополнение к выбраным особям поколение допополняется либо их копиями, либо особями со случайным генотипом. Затем из обновленноного поколения мы случайным образом выбираем пары и выполняем операцию скрещивания. Полный список скрещиваний вы найдете по запросу GA Crossover. Вариантов масса, всё зависит от вашей задачи. От двух родителей получается два потомка, в некоторых случаях особь переходит в следующее поколение без изменений, иногда, с небольшой вероятностью особь может немного мутировать (GA Mutation), так мы обеспечиваем "метод иммитации отжига", когда благодаря случайным изменениям мы вырываемся из локального экстремума и исследуем поле значений более широко, т.к. скрещивания эталонных особей может загнать нас в локальный максимум или минимум целевой функции, которая оценивает особь. В итоге, спустя много поколений селекции, скрещивания и мутаций случайных решений вашей проблемы вы получаете отличное решение для абсолютно разных задач. Хотите статью на эту тему?
Что человечество научилось делать хорошо, так это заимствовать. В этот раз заимствование произошло у самой природы. Есть класс алгоритмов, которые называются метаэвристическими - это те, которые подглядели у природы и хорошо зашло в применении. Так появился генетический алгоритм в основе которого лежат целые популяции особей - решений. Этот алгоритм по праву считается универсальным, т.к. справляется с задачами из различных областей. Давайте решим вашу задачу (скажу сразу, что в разных источниках можно найти небольшие отклонения в именовании). Для начала сформируйте решение вашей задачи в виде вектора (набор цифр, например), такой вектор называется набором генов (каждая цифра вектора - это значение спрятанное в гене). Вектор - это хромосома, хромосом может быть несколько, но если ваш вектор целиком описывает решение, то хромосома всего одна. Хромосомы определяются генотипом, т.е. генотип обладает одной или более хромосом. В генетическом алгоритме на первом шаге создается первое поколение или популяция, которое представляет из себя набор особей с разнообразными генотипами. Из каждого, в том числе и первого, поколения выбираются лучшие особи. Способов выбора множество, список их вы найдете по запросу GA Selection. В зависимости от выбранного подхода к селекции (отбору), в дополнение к выбраным особям поколение допополняется либо их копиями, либо особями со случайным генотипом. Затем из обновленноного поколения мы случайным образом выбираем пары и выполняем операцию скрещивания. Полный список скрещиваний вы найдете по запросу GA Crossover. Вариантов масса, всё зависит от вашей задачи. От двух родителей получается два потомка, в некоторых случаях особь переходит в следующее поколение без изменений, иногда, с небольшой вероятностью особь может немного мутировать (GA Mutation), так мы обеспечиваем "метод иммитации отжига", когда благодаря случайным изменениям мы вырываемся из локального экстремума и исследуем поле значений более широко, т.к. скрещивания эталонных особей может загнать нас в локальный максимум или минимум целевой функции, которая оценивает особь. В итоге, спустя много поколений селекции, скрещивания и мутаций случайных решений вашей проблемы вы получаете отличное решение для абсолютно разных задач. Хотите статью на эту тему?