Эвристические алгоритмы поиска. Поиск в глубину и ширину с помощью упорядоченного перебора.

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

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

10. Эвристические алгоритмы поиска. Алгоритм поиска оптимального решения А*.

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

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

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

11. Метод редукции. Поиск решения на и/или графах. Алгоритм АО*.

Поиск необходимой совокупности данных для решения задачи сводится к решению составляющих подзадач. Задачи описываются различными способами: списки, деревья, массивы. Процесс преобразования также удобно описывать с помощью графовых структур. Процесс поиска решения исходной задачи при таком описании представляет собой направленный граф редукции задач. Этот граф называется графом И/ИЛИ. Вершины этого графа представляют описания задач и подзадач. Граф И/ИЛИ содержит вершины двух типов. Тип «И» - соответствует задаче, решаемой при условии реализации всех ее подзадач в соответствующих вершинах - преемниках. Тип «ИЛИ» - соответствует задаче, решение которой возможно получить при решении одной из альтернативных подзадач в соответствующих вершинах - преемниках. Реализация графа редукции аналогична реализации графа поиска решении в пространстве состояний. В частном случае, если вершин И нет, получается обычный граф пространства состояний. Поэтому метод редукции является в какой-то степени обобщением подхода с использованием пространства состояний. Процесс поиска на графе И/ИЛИ заключается в построении решающего графа (или дерева решений), который является подграфом графа редукции.

12. Генетические алгоритмы. Представление генетической информации. Генетические операторы.

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

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

Основные положения теории гена: все признаки организма определяются наборами генов; гены — это элементарные единицы наследственной информации, которые находятся в хромосомах; гены могут изменяться — мутировать; мутации отдельных генов приводят к изменению отдельных элементарных признаков организма.

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

Помимо кроссинговера для решения прикладных задач используются:

Мутация - изменение, приводящее к качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или линейности. Дискретность позволяет выделить отдельные фрагменты, контролирующие функции. Непрерывность означает, что определенные комбинации генов совместно контролируют некоторую функцию. Линейность проявляется в определенной последовательности генов в пределах группы сцепления.

Инверсия, транслокация, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 180°. Транслокация - перенос части одной хромосомы в другую. Делеция - выпадение отдельных участков хромосом, дупликация — повторение участка генетического материала. Селекция представляет собой форму искусственного отбора, который может быть массовым или индивидуальным. Массовый отбор по фенотипу (совокупности всех внешних и внутренних признаков) менее эффективен, чем индивидуальный, когда популяцию делят на отдельные линии, а для размножения выбирают носителей желаемых свойств. Применение селекции в генетических алгоритмах способствует ускорению процесса синтеза решения.

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

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

13. Генетические алгоритмы. Репродуктивный план Холланда. Пример его применения для определения экстремума функции.

Согласно репродуктивному плану Холланда генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции:

1. Конструируется начальная популяция. Вводится начальная точка отсчета поколений t=0. Вычисляются приспособленность хромосом популяции и средняя приспособленность всей популяции.

2. Устанавливается значение t=t+1. Выбираются два родителя для кроссинговера случайным образом пропорционально жизнеспособности хромосом.

3. Формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков A(t), который сохраняется как член новой популяции. Далее к потомку A(t) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как A'(t).

4. Обновление текущей популяции путем замены случайно выбранной хромосомы A'(t).

5. Определение приспособленности A'(t) и пересчет средней приспособленности популяции.

6. Если t=t*, где t* — заданное число шагов, то переход к этапу 7, иначе — переход к этапу 2.

7. Конец работы.

Рассмотрим пример применения простого генетического алгоритма для максимизации функции на целочисленном интервале [0, 31]. Значения аргумента функции , изменяющегося в интервале от 0 до 31, можно представить пятиразрядными двоичными числами. Первоначальная популяция, состоящая из четырех строк пятиразрядных чисел, полученная с помощью процедуры генерации случайных чисел: 01101, 11000, 01000, 10011 (в десятичном коде: 13, 24, 8, 19). Значение целевой функции для каждой хромосомы определяется путем возведения в квадрат значения двоичного числа, кодирующего решение х. Претенденты для кроссинговера могут выбираться из начальной популяции или после выполнения оператора репродукции.

Репродукция начального множества заключается в четырехкратном вращении колеса рулетки, в результате чего состав исходной популяции может измениться (вероятности рулетки: 0.31, 0.14, 0.06, 049). Вероятность выбора i-й хромосомы вычисляется по формуле: , где fi(x) - значение целевой функции i-й хромосомы в популяции; — суммарное значение целевой функции всех хромосом в популяции.

Ожидаемое число копий i-й хромосомы после оператора репродукции равно где n — число анализируемых хромосом. Число копий хромосомы, переходящих в следующее поколение:

где - среднее значение целевой функции.

Значение N для первой хромосомы будет равно 0.14 4=0.56 копий, для второй — 0.49 4=1.96 копий, для третьей - 0.06 4=0.24 и для четвертой — 0.31 4=1.23. В результате репродукции в новой популяции: 0110|1, 1100|0, 11|000, 10|011 будут присутствовать по одной копии первой и четвертой хромосомы и две копии второй, а третья хромосома будет исключена. Оператор репродукции отбирает лучших представителей популяции.

На шаге 2 с помощью колеса рулетки осуществляется выбор хромосом для кроссинговера. Поля колеса рулетки соответствуют нормированным значениям целевой функции. Случайный механизм не гарантирует выбора лучших хромосом. Оператор кроссинговера может повторяться несколько раз. Затем каждая пара хромосом пересекается. Место пересечения K выбирается случайным образом на интервале (1, L-1), где L - длина хромосомы, определяемая количеством значащих цифр в ее двоичном коде. В нашем случае L=5. Две новые хромосомы создаются путем взаимного обмена всех значений после точки пересечения, т.е. между позициями (К+1) и L. Для первых двух хромосом до применения оператора кроссинговера имеем описание: хромосома 1: 0110|1, хромосома 2: 1100|0, а после применения кроссинговера: хромосома 1: 0110|0, хромосома 2: 1100|1

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

На шаге 3 выполняется оператор мутации. Обычно выбирают одну мутацию на 1000 бит. Оператор мутации относится к унарным операциям и реализуется: В хромосоме случайным образом определяют две позиции, 2 и L-1. Гены, соответствующие выбранным позициям, меняют местами и формируют новую хромосому .

Производим случайно-направленный поиск, который может быть реализован на основе простого генетического алгоритма. Выберем третью хромосому 11011 со значением целевой функции f(х)=729 и применим операцию мутации к позициям 3 и 4: хромосома 3: 11011 хромосома 3': 11101.

У новой хромосомы 3' значение целевой функции равно (29)2=841. Сделаем еще одну перестановку 4 и 5 генов в хромосоме 3': хромосома 3': 11101 хромосома 3": 11110. Значение целевой функции для хромосомы 3" равно 900, что соответствует квазиоптимальному решению задачи нахождения максимального значения функции на интервале [0,31].