Шпора (Шпоры к первому коллоквиуму), страница 11
Описание файла
Файл "Шпора" внутри архива находится в папке "Шпоры к первому коллоквиуму". PDF-файл из архива "Шпоры к первому коллоквиуму", который расположен в категории "". Всё это находится в предмете "искусственный интеллект" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 11 страницы из PDF
Скрещивание наиболее приспособленных особей приводит к тому, чтоисследуются наиболее перспективные участки пространства поиска. В конечном итогепопуляция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том,что он находит приблизительные оптимальные решения за относительно короткое время.ГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемойпроблемы. Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов длягенерации новых решений из предыдущей популяции; 4) Целевая функция для оценкиприспособленности (fitness) решений.Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в видестроки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможныхбинарных строк представляет возможное решение задачи.Стандартные операторы для всех типов генетических алгоритмов это: селекция,скрещивание и мутация.СелекцияОператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии созначениями их функции приспособленности.
Существуют как минимум два популярных типаоператора селекции: рулетка и турнир.• Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков"рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции.Размер i-ого сектора пропорционален некоторой величине вычисляемой по формуле.При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться,чем особи с низкой приспособленностью.•Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей.Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особисреди них.
Наиболее распространен турнирный отбор с k=2.СкрещиваниеОператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (можетбыть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным.Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбираетсяодна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Оберодительские структуры разрываются на два сегмента по этой точке.
Затем, соответствующиесегменты различных родителей склеиваются и получаются два генотипа потомков.01##101#1010010100#1МутацияМутация (mutation) - стохастическое изменение части хромосом. Каждый ген строки, котораяподвергается мутации, с вероятностью Pmut (обычно очень маленькой) меняется на другой ген.010#1011#1Схема работы ГАРабота ГА представляет собой итерационный процесс, который продолжается до тех пор, пока невыполнятся заданное число поколений или какой-либо иной критерий останова. На каждомпоколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.Схема работы простого ГА выглядит следующим образом:НачальнаяотборпопуляцияскрещиваниемутацияПовторение цикла сновой популяциейоценкарезультатаЗадача решена.ВыходКритерии остановки алгоритма:нахождение глобального, либо субоптимального решения;исчерпание числа поколений, отпущенных на эволюцию;исчерпание времени, отпущенного на эволюцию.Генетические алгоритмы служат, главным образом, для поиска решений в оченьбольших, сложных пространствах поиска.
Примеры реальных областей применения:• оптимизация запросов в базах данных;• задачи на графах (задача коммивояжера, раскраска);• задачи компоновки;• составление расписаний.Замечание: Генетические алгоритмы и «метод проб и ошибок».•••Решение задач и искусственный интеллектДвумя составными элементами процесса решения задач в теории искусственногоинтеллекта являются представление (формализация) задач и собственно решение – поиск.
Мырассмотрим два подхода к решению задач и, соответственно, два способа представления – подходс использованием пространства состояний и подход, основанный на редукции задач. Для обоихподходов описываются используемые алгоритмы поиска решения. Важной особенностьюбольшинства этих алгоритмов является использование эвристической информации. Эвристикойобычно принято называть любое правило (стратегию, прием), существенно помогающее врешении некоторой задачи.Представление задач в пространстве состоянийОсновные понятияТипичным представителем класса задач, для которых подходит представление впространстве состояний, является головоломка, известная как игра в пятнадцать – см. рис.
1(а). Вней используется пятнадцать пронумерованных (от 1 до 15) подвижных фишек, расположенных вклетках квадрата 4×4. Одна клетка этого квадрата остается всегда пустой, так что одну изсоседних с ней фишек можно передвинуть на место этой пустой клетки, изменив тем самымместоположение пустой клетки. Заметим, что более простым вариантом этой головоломкиявляется квадрат 3×3 и восемь фишек на нем – пример соответствующей задачи показан нарис.1(б).На рис.1(а) изображены две конфигурации фишек.
В головоломке требуется преобразоватьпервую, или начальную, конфигурацию во вторую, или целевую конфигурацию. Решением этойзадачи будет подходящая последовательность сдвигов фишек, например: передвинуть фишку 8вверх, фишку 6 влево и т.д.111713Рис.193524g8101512614а)⇒159132610143711154812g2 8 31 6 47 g 5⇒1 2 38 g 47 6 5б)Важной особенностью класса задач, к которому принадлежит рассмотренная головоломка,относится наличие в задаче точно определенной начальной ситуации и точно определенной цели.Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию вдругую.
Именно из таких ходов состоит искомое решение задачи, которое можно в принципеполучить методом проб и ошибок. Действительно, отправляясь от начальной ситуации, можнопостроить конфигурации, возникающие в результате выполнения возможных в этой ситуацииходов, затем построить множество конфигураций, получающихся после применения следующегохода, и так далее – пока не будет достигнута целевая конфигурация.Введем теперь основные понятия, используемые при формализации задачи в пространствесостояний. Центральным из них является понятие состояния, характеризующего некоторыймомент решения задачи.
Например, для игры в пятнадцать (или в восемь) состояние – это простонекоторая конкретная конфигурация фишек.Среди всех состояний задачи выделяются начальное состояние и целевое состояние, всовокупности определяющие задачу, которую надо решить − примеры их приведены на рис.1.Другим важным понятием является понятие оператора, т.е. допустимого хода в задаче.Оператор преобразует одно состояние в другое, являясь по сути функцией, определенной намножестве состояний и принимающей значения из этого множества. Для игры в пятнадцать или ввосемь удобнее выделить четыре оператора, соответствующие перемещениям пустой клетки(можно считать ее фишкой-«пустышкой») влево, вправо, вверх, вниз.
В некоторых случаяхоператор может оказаться неприменимым к какому-то состоянию: например, операторы сдвигавправо и вниз неприменимы, если пустая клетка расположена в правом нижнем углу. Значит, вобщем случае оператор является частично определенной функцией отображения состояний.В терминах состояний и операторов решение задачи есть определеннаяпоследовательность операторов, преобразующая начальное состояние в целевое. Решение задачиищется в пространстве состояний – множестве всех состояний, достижимых из начальногосостояния при помощи заданных операторов.
Например, в игре в пятнадцать или в восемьпространство состояний состоит из всех конфигураций фишек, которые могут быть образованы врезультате возможных перемещений фишек.Пространство состояний можно представить в виде направленного графа, вершиныкоторого соответствуют состояниям, а дуги (ребра) – применяемым операторам. Указанные в видестрелок направления соответствуют движению от вершины-аргумента применяемого оператора крезультирующей вершине. Тогда решением задачи будет путь в этом графе, ведущий отначального состояния к целевому. На рис.2 показана часть пространства состояний для игры впятнадцать.
Каждая вершина соответствует некоторой конфигурации фишек. Все дуги междувершинами являются двунаправленными, поскольку в этой головоломке для любого оператораесть обратный ему (точнее, множество операторов состоит из двух пар взаимно-обратныхоператоров: влево-вправо, вверх-вниз).Пространства состояний могут быть большими и даже бесконечными, но в любом случаепредполагается счетность множества состояний.Таким образом, в подходе к решению задачи с использованием пространства состоянийзадача рассматривается как тройка ( SI , O , SG ) , гдеSI – начальное состояние;O – конечное множество операторов, действующих на не более чем счетном множестве состояний;SG – целевое состояние.Дальнейшая формализация решения задачи с использованием пространства состоянийпредполагает выбор некоторой конкретной формы описания состояний задачи. Для этого могутприменяться любые подходящие структуры – строки, массивы, списки, деревья и т.п.
Например,для игры в пятнадцать или восемь наиболее естественной формой описания состояния будетсписок положений фишек или же двумерный массив. Заметим, что от выбора формы описаниясостояния зависит в общем случае сложность задания операторов задачи, которые должны бытьтакже определены при формализации задачи в пространстве состояний.Если для игры в пятнадцать средством формализации выступает язык программированияЛисп или Паскаль, то операторы задачи могут быть описаны в виде четырех соответствующихфункций языка. При использовании же продукционного языка, эти операторы задаются в видеправил продукций вида: «исходное состояние → результирующее состояние».В рассмотренных выше примерах (игры в пятнадцать и восемь) искомое целевоесостояние задавалось явно, т.е.
известно было местоположение каждой фишки в целевойконфигурации. В более сложных случаях игры может быть несколько целевых состояний, либо жецелевое состояние может быть определено неявно, т.е. охарактеризовано некоторым свойством,например, как состояние, в котором сумма номеров фишек в верхнем ряду не превосходит 10. Вподобных случаях свойство, которому должно удовлетворять целевое состояние, должно бытьописано исчерпывающим образом, к примеру, путем задания булевской функции, реализующейпроверку нужного свойства состояния задачи.Итак, для представления задачи в пространстве состояний необходимо определитьследующее:• форму описания состояний задачи и описание начального состояния;• множество операторов и их воздействий на описания состояний;• множество целевых состояний или же описание их свойств.Перечисленные составляющие задают неявно граф-пространство состояний, в котором требуетсяпровести поиск решения задачи.