Решение проблем с помощью генетических алгоритмов

Автор:Alex Allain

Перевод: Струг С.С.

Генетические алгоритмы полезны для решения задач, имеющих решения, представимых в виде строки (отсюда и название генетического алгоритма - модель программирования основана на ДНК). С точки зрения практической ценности, генетические алгоритмы полезны для решения задач, в которых решения трудно найти, следуя специальному алгоритму, предназначенному для решения задачи (с помощью генетических алгоритмов вместо предварительно разработанных алгоритмов, таких как алгоритм Djikstra для поиска пути просто неимело бы смысла). Он функционирует как своего рода систематизированной грубой силе подхода. Проблемы генетических алгоритмов являются ценными для решения, включают в себя задачи планирования, задачи удовлетворения ограничений, а также другие проблемы, которые требуют поиска большого количества возможностей. Генетические алгоритмы могут быть применены к сворачиванию белка или, даже, настройки производительности ядра Linux. Более простой пример только, чтобы получить точку, через пять цифр, которые являются лучшим решением для выражения; например, если вы хотите, найти номер, что делает выражение х ^ 2 + 2x-11, равным 0, можно использовать грубую силу, чтобы решить уравнение, но генетический алгоритм также может быть использован, и если у вас есть очень сложное выражение, оно может иметь большое значение, чтобы использовать генетический алгоритм, особенно если принять во внимание время. В некотором смысле, все генетические проблемы алгоритма сводятся к решению сложных выражений или наборов выражений, так как все проблемы представлены в том же духе.

Компоненты генетических алгоритмов

Генетические алгоритмы работают с той же основой эволюционной теории. Генетический алгоритм состоит из нескольких компонентов:

- пул решений;

- метод оценки эффективности каждого решения;

- функции размножения, которые сочетают в себе лучшие решения и новые решения;

- функции мутации.

Пул решений не конкурирует за ресурсы; скорее, каждое решение проверяется с помощью оценочной функции (называемой функцией "фитнес"), который затем дает ему ранжирование на основе его эффективности при решении задачи по сравнению с другими решениями.

Лучшие значения решения являются те, которые занимает самое высокое место (что наиболее «подходят»); функция размножения принимает два из более эффективных решений и объединяет их вместе в новое решение. Функции размножения следует повторить процесс случайного выбора двух решений и их разводом; тем лучше исполнительской функции следует дать более высокий процентный шанс быть выбранной.

Функция размножения обычно работает принимая кусочки каждого раствора и наращивания их вместе в новую. Решения часто представляются в виде строк, так что, как правило, функция размножения будет принимать фрагменты произвольной длины из каждой строки и объединять их вместе, чтобы сформировать новую строку. Каждый фрагмент должен быть помещен в ячейку в новой строке, которая соответствует его местоположению в старой строке. Например, если фрагмент строки с позиций от 5 до 8 в первой строке разводится, он должен быть помещен в позицию с 5 по 8 в новом растворе ребенка.

После того, как строки были выведены, а множество возможных решений было пополнено, важно иметь функцию мутации. Функция мутации важна, поскольку она вносит элемент случайности, которая позволяет вариации быть в наборах решений, которые в противном случае будут стагнировать и не иметь преимущества по сравнению с ручным раствором. Мутации могут уменьшить силу некоторых решений, но в целом это увеличит общую стоимость набора решений; путем включения очень малой частоты мутаций, вы выведите новые черты, которые возможно б никогда не существовали в пределах пула решений. Это позволяет исследовать большую группу возможностей и избежать застоя. На самом деле, много других методов ИИ отказываеться от идеи разведения решений и работает просто - делая небольшие "мутации" или изменения в качестве потенциального решения проблемы.

Вывод

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