Шпора-small (Шпоры к первому коллоквиуму), страница 11

Описание файла

Файл "Шпора-small" внутри архива находится в папке "Шпоры к первому коллоквиуму". PDF-файл из архива "Шпоры к первому коллоквиуму", который расположен в категории "контрольные работы и аттестации". Всё это находится в предмете "искусственный интеллект" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 11 страницы из PDF

Курс: Генетические алгоритмы, 2002)Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационныеметоды, впервые предложенные Джоном Генри Холландом в книге «Адаптация в естественныхи искусственных системах» (1975). Они основываются на идее эволюции с помощьюестественного отбора, выдвинутой Дарвином.ГА работают с совокупностью "особей" - популяцией, каждая из которых представляетвозможное решение данной проблемы. Каждая особь оценивается мерой ее"приспособленности" согласно тому, насколько "хорошо" соответствующее ей решениезадачи. В природе это эквивалентно оценке того, насколько эффективен организм приконкуренции за ресурсы. Наиболее приспособленные особи получают возможность"воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особямипопуляции. Это приводит к появлению новых особей, которые сочетают в себе некоторыехарактеристики, наследуемые ими от родителей.

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

Скрещивание наиболее приспособленных особей приводит к тому, чтоисследуются наиболее перспективные участки пространства поиска. В конечном итогепопуляция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том,что он находит приблизительные оптимальные решения за относительно короткое время.СелекцияГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемойпроблемы.

Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов длягенерации новых решений из предыдущей популяции; 4) Целевая функция для оценкиприспособленности (fitness) решений.Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в видестроки.

Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможныхбинарных строк представляет возможное решение задачи.Стандартные операторы для всех типов генетических алгоритмов это: селекция,скрещивание и мутация.Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии созначениями их функции приспособленности. Существуют как минимум два популярных типаоператора селекции: рулетка и турнир.• Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков"рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции.Размер i-ого сектора пропорционален некоторой величине вычисляемой по формуле.•При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться,чем особи с низкой приспособленностью.Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей.Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особисреди них.

Наиболее распространен турнирный отбор с k=2.Скрещивание10010#1#0110010##110Оператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (можетбыть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным.Одноточечный кроссовер работает следующим образом.

Сначала, случайным образом выбираетсяодна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Оберодительские структуры разрываются на два сегмента по этой точке. Затем, соответствующиесегменты различных родителей склеиваются и получаются два генотипа потомков.Мутация010#1011#1Мутация (mutation) - стохастическое изменение части хромосом. Каждый ген строки, котораяподвергается мутации, с вероятностью Pmut (обычно очень маленькой) меняется на другой ген.отборскрещиваниемутацияоценкарезультатаЗадача решена.ВыходСхема работы ГАРабота ГА представляет собой итерационный процесс, который продолжается до тех пор, пока невыполнятся заданное число поколений или какой-либо иной критерий останова.

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

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

1(а). Вней используется пятнадцать пронумерованных (от 1 до 15) подвижных фишек, расположенных вклетках квадрата 4×4. Одна клетка этого квадрата остается всегда пустой, так что одну изсоседних с ней фишек можно передвинуть на место этой пустой клетки, изменив тем самымместоположение пустой клетки. Заметим, что более простым вариантом этой головоломкиявляется квадрат 3×3 и восемь фишек на нем – пример соответствующей задачи показан нарис.1(б).На рис.1(а) изображены две конфигурации фишек.

В головоломке требуется преобразоватьпервую, или начальную, конфигурацию во вторую, или целевую конфигурацию. Решением этойзадачи будет подходящая последовательность сдвигов фишек, например: передвинуть фишку 8вверх, фишку 6 влево и т.д.111713Рис.193521512614а)4g810⇒159132610143711154812g2 8 31 6 47 g 5б)⇒1 2 38 g 47 6 5Важной особенностью класса задач, к которому принадлежит рассмотренная головоломка,относится наличие в задаче точно определенной начальной ситуации и точно определенной цели.Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию вдругую.

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

Центральным из них является понятие состояния, характеризующего некоторыймомент решения задачи. Например, для игры в пятнадцать (или в восемь) состояние – это простонекоторая конкретная конфигурация фишек.Среди всех состояний задачи выделяются начальное состояние и целевое состояние, всовокупности определяющие задачу, которую надо решить − примеры их приведены на рис.1.Другим важным понятием является понятие оператора, т.е. допустимого хода в задаче.Оператор преобразует одно состояние в другое, являясь по сути функцией, определенной намножестве состояний и принимающей значения из этого множества. Для игры в пятнадцать или ввосемь удобнее выделить четыре оператора, соответствующие перемещениям пустой клетки(можно считать ее фишкой-«пустышкой») влево, вправо, вверх, вниз.

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

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

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

Свежие статьи
Популярно сейчас