Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 46
Текст из файла (страница 46)
Если какой-либо из этих преемников соответствует целевому состоянию, алгоритм останавливается. В противном случае алгоритм выбирает из общего списка )с наилучших преемников и повторяет цикл. На первый взгляд может показаться, что локальный лучевой поиск с )с состояниями представляет собой нс что иное, как выполнение )с перезапусков случайным образом, но не последовательно, а параллельно. Тем не менее в действительности эти два алгоритма являются полностью разными.
При поиске с перезапуском случайным образом каждый процесс поиска осуществляется независимо от других. ср- А в локальном лучевом поиске полезная информация передаеглся па )с параллельным потокам поиска. Например, если в одном состоянии вырабатывается несколько хороших преемников, а во всех других )с-1 состояниях вырабатываются плохие преемники, то возникает такой эффект, как если бы поток, контролирующий первое состояние, сообщил другим потокам: "Идите все сюда, здесь и Локальный лучевой поиск является аааптацией лучевого поиска, который представляет собой алгоритм, основанный на использовании пути.
182 Часть Н. Решение проблем трава зеленее!" Этот алгоритм способен быстро отказаться от бесплодных поисков и перебросить свои ресурсы туда, где достигнут наибольший прогресс. В своей простейшей форме локальный лучевой поиск может страдать от отсутствия разнообразия между й состояниями, поскольку все эти состояния способны быстро сосредоточиться в небольшом регионе пространства состояний, в результате чего этот поиск начинает ненамного отличаться от дорогостоягдей версии поиска с восхождением к вершине. Этот недостаток позволяет устранить вариант, называемый 'ъ стохастическим лучевым поиском, который аналогичен стохастическому поиску с восхождением к вершине. При стохастическом лучевом поиске вместо выбора наилучших й преемников из пула преемников-кандидатов происходит выбор й преемников случайным образом, притом что вероятность выбора данного конкретного преемника представляет собой возрастаюшую функцию значения его оценки.
Стохастический лучевой поиск имеет некоторое сходство с процессом естественного отбора, в котором "преемники" (потомки) некоторого "состояния" (организма) образуют следуюшее поколение в соответствии со "значением их оценки" (в соответствии с их жизненной пригодностью). Генетические алгоритмы 'а Генетический алгоритм (бепе!1с А18ог!гпш — СА) представляет собой вариант стохастического лучевого поиска, в котором состояния-преемники формируются путем комбинирования двух родительских состояний, а не посредством модификации единственного состояния.
В нем просматривается такая же аналогия с естественным отбором, как и в стохастическом лучевом поиске, за исключением того, что теперь мы имеем дело с половым, а не бесполым воспроизводством. Как и при лучевом поиске, работа алгоритмов ОА начинается с множества й сформированных случайным образом состояний, называемых ек популяцией. Каждое состояние, или Ж индивидуум, представлено в виде строки символов из конечного алфавита, чаше всего в виде строки из нулей (О) и единиц (1).
Например, состояние задачи с восемью ферзями должно определять позиции восьми ферзей, каждый из которых стоит на вертикали с 8 клетками, и поэтому для его представления требуется 8х1од,8=24 бита. Иным образом, каждое состояние может быть представлено в виде восьми цифр, каждая из которых находится в диапазоне от 1 до 8. (Как будет показано ниже, эти две копировки проявляют себя в холе поиска поразному.) На рис. 4.10, а показана популяция из четырех восьмисимвольных строк, представляющих состояния с восемью ферзями. Процесс выработки следуюшего поколения состояний показан на рис.
4.10, б — д. На рис. 4.!О, б каждое состояние классифицируется с помощью функции оценки, или (в терминологии ОА) Ъ. функции пригодности. Функция пригодности лолжна возврашать более высокие значения для лучших состояний, поэтому в задаче с восемью ферзями используется количество неатакуюших друг друга пар ферзей, которое в любом решении имеет значение 28. Для этих четырех состояний соответствующие значения равны 24, 23, 20 и 11.
В данном конкретном варианте генетического алгоритма вероятность выбора для воспроизводства прямо пропорциональна оценке пригодности; соответствующие вероятности в процентах показаны рядом с исходными оценками. ! слиы4. !Ьв~ооюц>окиипси псикл и иссиспс каис поо:пак":по с- и 1лава 4. Информированный поиск и исследование пространства состояний !85 ЭВОЛЮЦИЯ И ПОИСК Теория эволюции была изложена Чарльзом Дарвином в его книге Оа йе Ог(8уя о)' Бреоез Ьу Меапз ОГАгагига1 ое(есгтоп (Происхождение видов путем естественного отбора) [325[.
Основная идея этой теории проста: при воспроизводстве возникают вариации (известные как мутации), которые сохраняются в следующих поколениях с частотой, приблизительно пропорциональной тому, как они влияют на пригодность к воспроизводству. Дарвин разрабатывал свою теорию, не зная о том, благодаря чему происходит наследование и модификация характерных особенностей организмов. Вероятностные законы, управляющие этими процессами, бьши впервые обнаружены Грегором Менделем [1034[, монахом, проводившим эксперименты с душистым горошком с использованием метода, названного им искуссгяведяын оплодотворением.
Гораздо позже Уотсон и Крик [1559[ выявили структуру молекулы ДНК (дезоксирибонуклеиновой кислоты) и ее алфавит, состоящий из аминокислот АГТЦ (аденин, гуанин, тимин, цитозин). В предложенной ими стандартной модели вариации возникают и в результате точечных мутаций в последовательности этих аминокислот, и в результате "скрещивания" (при котором ДНК потомка формируется путем объединения длинных секций ДНК от каждого родителя). Аналогия между этим процессом и алгоритмами локального поиска уже была описана выше; принципиальное различие между стохастическим лучевым поиском и эволюцией состоит в использовании полового воспроизводства, в котором потомки формируются с участием нескольких организмов, а не только одного.
Однако фактически механизмы эволюции намного богаче по сравнению с тем, что допускает большинство генетических алгоритмов. Например, мутации могут быть связаны с обращением, дублированием и перемещением больших фрагментов ДНК; некоторые вирусы заимствуют ДНК из одного организма и вставляют в другои; кроме того, существуют взаимозаменяемые гены, которые лишь копируют самих себя в геноме много тысяч раз.
Есть даже такие гены, которые отравляют клетки потенциальных родителей, не несущие ген этого типа, повышая тем самым шансы на воспроизводство данного гена. Наиболее важным является тот факт, что гены сами кодируют те механизмы, с помощью которых геном воспроизводится и транслируется в организме. В генетических алгоритмах такие механизмы представляют собой отдельную программу, не закодированную в строках, с которыми осуществляются манипуляции. На первый взгляд может показаться, что механизм дарвиновской эволюции является неэффективным, поскольку в его рамках на Земле за многие тысячи лет было вслепую сформировано около 10" или примерно столъко организмов, притом что за такое время поисковые эвристики этого механизма не улучшились ни на йоту.
Но за пятьдесят лет до Дарвина французский натуралист Жан Ламарк [884[, получивший известность в другой области, предложил теорию эволюции, согласно которой характерные особенности организма, приобретенные в результате его адаптации на протяжении срока жизни этого организма, передаются его потомкам. Такой процесс был бы очень эффективным, но в природе, по-видимому, не происходит. Намного 186 Часть!1. Решение проблем позднее Джеймс Болдуин [64) предложил теорию, которая внешне кажется аналогичной; согласно этой теории, поведение, которому обучился организм на протяжении своей жизни, способствует повышению скорости эволюции. В отличие от теории Ламарка, теория Болдуина полностью согласуется с дарвиновской теорией эволюции, поскольку в ней учитываются давления отбора, действуюШие на индивидуумов, которые нашли локальные оптимумы среди множества возможных вариантов поведения, допустимых согласно их генетической природе.
Современные компьютерные модели подтвердили, что "эффект Болдуина" является реальным, при условии, что "обычная" эволюция способна создавать организмы, внутренние показатели производительности которых каким-то образом коррелируют с их фактической жизненной пригодностью. Как и в алгоритмах стохастического лучевого поиска, в генетических алгоритмах тенденция к стремлению к максимуму сочетается с проводимым случайным образом исследованием и с обменом информацией между параллельными поисковыми потоками. Основное преимущество генетических алгоритмов (если таковое действительно имеется) связано с применением операции скрешивания. Тем не менее можно доказать математически, что если позиции в генетическом коде первоначально устанавливаются в случайном порядке, то скрешивание не дает никаких преимушеств. На интуитивном уровне можно предположить, что преимушеством была бы способность комбинировать в результате скрещивания большие блоки символов, которые были независимо сформированы в ходе эволюции для выполнения полезных функций, что позволило бы повысить степень детализации, с которой действует этот алгоритм поиска.
Например, преимущество достигалось бы, если в качестве полезного блока была выделена строка символов, предусматривающая размешение первых трех ферзей в позициях 2, 4 и 6 (где они не атакуют друг друга), после чего можно было бы объединять этот блок с другими блоками для формирования решения. В теории генетических алгоритмов описано, как действует этот подход, в котором используется идея Ъ. схемы, представляюшей собой такую подстроку, где некоторые из позиций могут оставаться не заданными. Например, схема 246***** описывает такие состояния всех восьми ферзей, в которых первые три ферзя находятся соответственно в позициях 2, 4 и 6. Строки, соответствуюшие этой схеме (такие как 24613578), называются экземплярами схемы. Можно доказать, что если средняя пригодность экземпляров некоторой схемы находится выше среднего, то количество экземпляров этой схемы в популяции будет расти со временем.
Очевидно, что данный эффект вряд ли окажется существенным, если смежные биты полностью не связаны друг с другом, поскольку в таком случае будет лишь немного непрерывных блоков, которые предоставляли бы какое-то постоянное преимущество. Генетические алгоритмы работают лучше всего в сочетании со схемами, соответствуюшими осмысленным компонентам решения. Например, если строка представляет какую- либо радиотехническую антенну, то схемы могут соответствовать компонентам этой антенны, таким как рефлекторы и дефлекторы. Хороший компонент, по всей вероятности, будет оставаться хорошим во многих разных проектах. Из этого следует, что для успешного использования генетических алгоритмов требуется тшательное конструирование представления задачи. Глава 4.
Информированный поиск и исследование пространства состояний 187 На практике генетические алгоритмы оказали глубокое влияние на научные методы, применяющиеся при решении таких задач оптимизации, как компоновка электронных схем и планирование производства.
В настоящее время уже не так ясно, вызвана ли притягательность генетических алгоритмов их высокой производительностью или обусловлена эстетически привлекательными истоками в теории эволюции. Но все еще необходимо проделать большой объем работы для выяснения условий, при которых генетические алгоритмы обладают наиболее высокой производительностью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
