Технологии ИИ1 ТЕХНОЛОГИИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Лекция 4. Генетические алгоритмы

Технологии ИИ2 Введение ГА – это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом в 1975 году. Считается, что они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином. ГА работают с совокупностью (популяцией) особей, каждая из которых представляет возможное решение данной проблемы. Классический ГА требует кодирования параметров или переменных, представляющих собой решение некоторой задачи, в виде двоичной строки - хромосомы.

Технологии ИИ3 Суть ГА Каждая особь оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Иногда происходят мутации появление новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей Из поколения в поколение, хорошие характеристики распространяются по всей популяции. В конечном итоге популяция будет сходиться к субоптимальному решению задачи. Полагается, что преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.

Технологии ИИ4 Компоненты ГА Хромосома. Вектор (последовательность) генов, представляющее решение рассматриваемой задачи. Начальная популяция хромосом. Набор операторов для генерации новых решений из предыдущей популяции. Целевая функция для оценки пригодности (fitness) решений. Соответствие терминологии естественного отбора в природе и ГА

Технологии ИИ5 Алгоритм работы ГА Работа ГА - итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой- либо иной критерий останова. На каждом поколении ГА реализуется отбор (пропорционально приспособленности), скрещивание и мутация.

Технологии ИИ6 Алгоритм /* генетический алгоритм */ НАЧАЛО Создать начальную популяцию Оценить приспособленность каждой особи останов := FALSE ПОКА НЕ останов ВЫПОЛНЯТЬ /* создать популяцию нового поколения */ ПОВТОРИТЬ (размер_популяции/2) РАЗ /* цикл воспроизводства */ Выбрать две особи с высокой приспособленностью из предыдущего поколения Скрестить выбранные особи и получить двух потомков Оценить приспособленности потомков Поместить потомков в новое поколение КОНЕЦ ЦИКЛА ЕСЛИ популяция сошлась, ТО останов := TRUE КОНЕЦ ЦИКЛА КОНЕЦ

Технологии ИИ7 Операторы ГА Стандартные операторы для всех типов ГА: Селекция (reproduction). Отбор хромосом в соответствии со значениями их функции пригодности. Скрещивание (crossover). Обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Мутация (mutation). Стохастическое изменение части хромосом.

Технологии ИИ8 Селекция (отбор) Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2. Пропорциональный отбор (fitness proportionate selection). Иногда называется методом рулетки (roulette-wheel selection) Основан на включении особи в новую популяцию по вероятностному принципу - отбирает особей с помощью N «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален соответствующей величине P sel (i) : Здесь f(i) – значение функции приспособленности i-й особи. При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью. Обычно дает плохие результаты.

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

Технологии ИИ10 Скрещивание Кроссовер Одноточечный Многоточечный

Технологии ИИ11 Выбор родительской пары Случайный выбор родительской пары («панмиксия» - свободное скрещивание). Любая особь может стать членом нескольких пар. Селективный способ. «Родителями» могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции. Такой подход обеспечивает более быструю сходимость алгоритма. Инбридинг и аутбридинг. Оба метода построены на формировании пары на основе близкого и дальнего «родства» соответственно. Инбридинг. Первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Концентрация поиска в локальных узлах, что приводит к разбиению популяции на отдельные локальные группы локальных экстремумов. Аутбридинг. Формирует пары из максимально далеких особей. Направлен на предупреждение сходимости алгоритма к уже найденным решениям.

Технологии ИИ12 Мутации Основой появления новых видов хромосом является кроссовер. Мутации в ГА носят вспомогательный характер. Они заключаются в случайном изменении разрядов битовых строк. Мутации могут носить и более сложный характер – быть кратными, циклическими и проч.

Технологии ИИ13 Количественные оценки параметров ГА Эффективность поиска чаще всего определяется как отношение среднего значения приспособленности популяции к максимальному значению после некоторого количества вычислений. Обычно исследуются несколько десятков поколений. Численность популяции должна быть достаточно большой – от нескольких десятков до нескольких сотен особей. Формирование генотипов особей начальной популяции желательно проводить по принципу максимального разнообразия. Максимальное побитовое разнообразие призвано обеспечить максимальное богатство генетического материала в начальной популяции.

Технологии ИИ14 Типичные задачи ГА 3 класса задач, типичных для ГА: 1.задача быстрой локализации одного экстремума, 2.задача определения нескольких (или всех) глобальных экстремумов, 3.задача описания ландшафта исследуемой функции, которая может сопровождаться выделением не только глобальных, но и локальных максимумов.

Технологии ИИ15 Тестовые задачи Овражные и многоэкстремальные функции

Технологии ИИ16 Функции

Технологии ИИ17 Функции 5-7

Технологии ИИ18 Недостатки ГА В ГА декларируется: 1.Способность простого представления (битовых строк) для кодирования сложных структур. 2.Мощность простого преобразования для улучшения таких структур. 3.ГА - простая модель эволюции в природе. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. 4.Генотип определяет все. Но: Каждому генотипу может соответствовать целое множество фенотипов. И наоборот. Мутации в ГА - это лишь дополнительный механизм. На самом деле именно мутации являются основой генетического механизма эволюции. Более того, как раз принципы размножения оказываются вторичными по сравнению с общим принципом вариабельности экземпляров вида, основанной на случайных мутациях. Основная техническая проблема ГА заключается в форме представления решения задачи. Язык описания в виде цепочек символов является слишком ограниченным и негибким для того, что бы можно было описать на нем сколько-нибудь сложные понятия. Это слишком сужает область применения ГА. Код Грея предпочтительнее обычного двоичного тем, что обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде.

Технологии ИИ19 Код Грея Особенность кода Грея - высокая помехозащищенность, т.к. при его использовании соседние целые числа отличаются друг от друга только на один бит (в одном разряде).

Технологии ИИ20 Генетическое программирование Коза (Koza),1992 г. В отличие от ГА в ГП все операции производятся не над строками, а над деревьями. При этом используются такие же операторы, как и в ГА: селекция, скрещивание и мутация. В ГП хромосомами являются программы. Программы представлены в виде деревьев с функциональными (промежуточными) и терминальными (конечными) элементами. Функция (программа) 2+x*4/7

Технологии ИИ21 Решение задачи в ГП Необходимо определить: Множество терминальных элементов. Множество функциональных элементов. Меру приспособленности (fitness). Параметры, контролирующие эволюцию. Критерий останова эволюции.

Технологии ИИ22 Особенности ГП Размер хромосомы меняется. Для предотвращения чрезмерного разрастания дерева вводят максимальное количество функциональных элементов в дереве или максимальную глубину дерева. В случае превышения лимита при скрещивании вместо конфликтного дерева копируется родительское дерево.

Технологии ИИ23 Пример 1. МИРЕ НАУКИ. (Scientific American) 1988 No4. стр А.К. Дьюдни «Моделирование эволюции в мире биоморфов» Взаимозависимая эволюция шипофита и гнутозавра

Технологии ИИ24 Программа

Технологии ИИ25 Пример 2. Задача о роботе, собирающем еду На поле - пища, стена или мина По краям мир огорожен стеной. Задача робота – собрать всю еду за наименьшее количество шагов

Технологии ИИ26 Устройство робота