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

PDF-файл Шпора (Шпоры к первому коллоквиуму), страница 11 Искусственный интеллект (52959): Ответы (шпаргалки) - 7 семестрШпора (Шпоры к первому коллоквиуму) - PDF, страница 11 (52959) - СтудИзба2019-09-18СтудИзба

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

Файл "Шпора" внутри архива находится в папке "Шпоры к первому коллоквиуму". 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. Вподобных случаях свойство, которому должно удовлетворять целевое состояние, должно бытьописано исчерпывающим образом, к примеру, путем задания булевской функции, реализующейпроверку нужного свойства состояния задачи.Итак, для представления задачи в пространстве состояний необходимо определитьследующее:• форму описания состояний задачи и описание начального состояния;• множество операторов и их воздействий на описания состояний;• множество целевых состояний или же описание их свойств.Перечисленные составляющие задают неявно граф-пространство состояний, в котором требуетсяпровести поиск решения задачи.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее