Главная arrow Поиск arrow Генетические алгоритмы
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Генетические алгоритмы Печать
Генетический алгоритм (Genetic Algorithm — GA) представляет собой вариант стохастического лучевого поиска, в котором состояния-преемники формируются путем комбинирования двух родительских состояний, а не посредством модификации единственного состояния. В нем просматривается такая же аналогия с естественным отбором, как и в стохастическом лучевом поиске, за исключением того, что теперь мы имеем дело с половым, а не бесполым воспроизводством.

Как и при лучевом поиске, работа алгоритмов GA начинается с множества k сформированных случайным образом состояний, называемых популяцией. Каждое состояние, или индивидуум, представлено в виде строки символов из конечного алфавита, чаще всего в виде строки из нулей (0) и единиц (1). Например, состояние задачи с восемью ферзями должно определять позиции восьми ферзей, каждый из которых стоит на вертикали с 8 клетками, и поэтому для его представления требуется 8 x log28 = 24 бита. Иным образом, каждое состояние может быть представлено в виде восьми цифр, каждая из которых находится в диапазоне от 1 до 8. (Как будет показано ниже, эти две кодировки проявляют себя в ходе поиска поразному.) На рисунке, а показана популяция из четырех восьмисимвольных строк, представляющих состояния с восемью ферзями.

Процесс выработки следующего поколения состояний показан на рисунке, б— д. На рисунке, б каждое состояние классифицируется с помощью функции оценки, или (в терминологии GA) функции пригодности. Функция пригодности должна возвращать более высокие значения для лучших состояний, поэтому в задаче с восемью ферзями используется количество неатакующих друг друга пар ферзей, которое в любом решении имеет значение 28. Для этих четырех состояний соответствующие значения равны 24, 23, 20 и 11. В данном конкретном варианте генетического алгоритма вероятность выбора для воспроизводства прямо пропорциональна оценке пригодности; соответствующие вероятности в процентах показаны рядом с исходными оценками.


Генетический алгоритм: начальная популяция (а); функция пригодности (б); отбор (в); скрещивание (г); мутация (д). Начальная популяция классифицируется с помощью функции пригодности, в результате чего формируются пары для скрещивания. Эти пары производят потомков, которые в конечном итоге подвергаются мутации

Как показано на рисунке, для воспроизводства случайным образом выбираются две пары в соответствии с вероятностями, показанными на рисунке. Обратите внимание на то, что один индивидуум выбирается дважды, а один вообще остается не выбранным. Для каждой пары, предназначенной для воспроизводства, среди позиций в строке случайным образом выбирается точка скрещивания. Точки скрещивания находятся после третьей цифры в первой паре и после пятой цифры во второй паре.

Как показано на рисунке, сами потомки создаются путем перекрестного обмена подстроками родительских строк, разорванных в точке скрещивания. Например, первый потомок первой пары получает три первые цифры от первого родителя, а остальные цифры — от второго родителя, тогда как второй потомок получает первые три цифры от второго родителя, а остальные — от первого родителя. Состояния задачи с восемью ферзями, участвующие в этом этапе воспроизводства. Данный пример иллюстрирует тот факт, что если два родительских состояния являются весьма различными, то операция скрещивания способна выработать состояние, которое намного отличается и от одного, и от другого родительского состояния. Часто происходит так, что популяция становится весьма разнообразной на самых ранних этапах этого процесса, поэтому скрещивание (как и эмуляция отжига) в основном обеспечивает выполнение крупных этапов в пространстве состояний в начале процесса поиска и более мелких этапов позднее, когда большинство индивидуумов становятся весьма похожими друг на друга.

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

Состояния задачи с восемью ферзями, соответствующие первым двум родительским состояниям, и первому потомку. Затененные столбцы на этапе скрещивания теряются, а незатененные сохраняются

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


function Genetic-Algorithm{population, Fitness-Fn) returns индивидуум
individual
  inputs: popuiation, множество индивидуумов (популяция)
  Fi tness-Fn, функция, которая измеряет пригодность
  индивидуума
  repeat
    new_jDopulation <— пустое множество
    loop for i from 1 to Size{population) do
    x <r- Random-Selection {population, Fitness-Fn)
    у <r- Random-Sel ection {population, Fitness-Fn)
    child <— Reproduce(x, y)
    if (небольшое случайно выбранное значение вероятности)
    then child <— Mutate(child)
    добавить дочерний индивидуум child
    к множеству new_population
    population <— new_jpopulation
  until некоторый индивидуум не станет достаточно пригодным
  или не истечет достаточное количество времени
  return наилучший индивидуум individual в популяции population,
  в соответствии с функцией Fitness~Fn
function Reproduce(х, у) returns индивидуум individual
  inputs: х, у, индивидуумы-родители
  п <— Length(х)
  с <г~ случайное число от 1 до п
return Append(Substring(х, 1, с), Substring(y, с+1, л))


Как и в алгоритмах стохастического лучевого поиска, в генетических алгоритмах тенденция к стремлению к максимуму сочетается с проводимым случайным образом исследованием и с обменом информацией между параллельными поисковыми потоками. Основное преимущество генетических алгоритмов (если таковое действительно имеется) связано с применением операции скрещивания. Тем не менее можно доказать математически, что если позиции в генетическом коде первоначально устанавливаются в случайном порядке, то скрещивание не дает никаких преимуществ.

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

В теории генетических алгоритмов описано, как действует этот подход, в котором используется идея ^ схемы, представляющей собой такую подстроку, где некоторые из позиций могут оставаться не заданными. Например, схема 246***** описывает такие состояния всех восьми ферзей, в которых первые три ферзя находятся соответственно в позициях 2, 4 и 6. Строки, соответствующие этой схеме (такие как 24613578), называются экземплярами схемы. Можно доказать, что если средняя пригодность экземпляров некоторой схемы находится выше среднего, то количество экземпляров этой схемы в популяции будет расти со временем. Очевидно, что данный эффект вряд ли окажется существенным, если смежные биты полностью не связаны друг с другом, поскольку в таком случае будет лишь немного непрерывных блоков, которые предоставляли бы какое-то постоянное преимущество.

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

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