51 (Вопросы по разным темам с ответами (программирование))

Билет № 51. Эволюционное моделирование. Генетическое программирование.

Генетический алгоритм (¹).

Эволюционное моделирование.

В 1966 году Л. Фогель, А. Оуэне, М. Уолш предложили схему эволюции логических автоматов, решающих задачи прогноза. В 1975 г. вышла основополагающая книга Дж. Холланда "Адаптация в естественных и искусственных системах", в которой был предложен генетический алгоритм.

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

Основные эволюционные алгоритмы (ЭА):

• генетический алгоритм, предназначенный для оптимизации функций дискретных переменных и акцентирующий внимание на рекомбинациях геномов;

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

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

• генетическое программирование, использующее эволюционный метод дляоптимизации компьютерных программ

Особенности ЭА как алгоритмов оптимизации:

• параллельный поиск,

• случайные мутации и рекомбинации уже найденных хороших решений.

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

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

Одна из основных областей применения генетического алгоритма - решение задач комбинаторной оптимизации (например, задача о коммивояжере).

Из пособия “Системы искусственного интеллекта” Тельнов Ю.Ф, Трембач В.М.

Группа алгоритмов, использующих в своей основе идею эволюции Дарвина, называется эволюционными алгоритмами.

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

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

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

Природный механизм

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

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

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

Изредка происходит мутация: некоторый случайный нуклеотид цепи ДНК особи может измениться на другой. Если полученная цепь будет использоваться для создания потомства, то возможно появление у детей совершенно новых качеств.

Естественный отбор, скрещивание и мутация обеспечивают развитие популяции. Каждое новое поколение в среднем более приспособлено, чем предыдущее, т. е. оно лучше удовлетворяет требованиям внешней среды. Этот процесс называется эволюцией.

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

Практические моменты применения ГА.

В генетических алгоритмах никак не используются такие свойства функции, как непрерывность, дифференцируемость и т. д. Она подразумевается как “черный ящик”, который на вход получает параметры, а на выход выводит результат.

Для применения генетического метода необходимо:

• Выделить совокупность свойств объекта, характеризуемых внутренними параметрами и влияющих на его приспособленность;

• Сформулировать критерий оценки приспособленности особей объекта;

• Разработать математическую модель объекта, представляющую собой алгоритм вычисления F для заданного набора параметров;

• Закодировать набор параметров для представления им некоторой особи.

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

Функция приспособленности. Пусть есть задача нахождения оптимального размещения. Варьируя некоторые параметры (координаты размещаемых элементов), нужно найти такую их комбинацию, чтобы минимизировать занимаемую площадь. Такую задачу можно переформулировать как задачу нахождения максимума некоторой функции f(x₁, x₂, …, x_n). Эта функция и есть функция приспособленности. Она используется для вычисления приспособленности особей и должна принимать неотрицательные значения, а область определения параметров должна быть ограничена.

Кодировка набора параметров. Закодируем каждый параметр строкой битов. Если он принимает непрерывное множество значений, то выберем длину строки в соответствии с требуемой точностью. Таким образом, параметр сможет принимать только дискретные значения (этих значений будет степень 2), в некотором заданном диапазоне.

Например, пусть переменная x_k принадлежит отрезку [x_min, x_max]. Закодируем ее бинарной строкой из l битов. Тогда строка s_k обозначает следующее значение переменной x_k:

x_k = x_min + s_k(x_max − x_min) ⁄ 2^l

если в формуле s_k обозначает значение бинарного числа, кодируемого этой строкой.

Особью будет называться битовая строка (хромосома), являющаяся конкатенацией строк всего упорядоченного набора параметров:

101100 11001011 01101100 1100 1 11101

| x₁ | x₂ | | | | x_n |

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

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

Шаблоном называется строка длины L (т. е. той же длины, что и любая строка популяции), состоящая из символов {0, 1, *} (где * — какой-то символ). Строка является представителем данного шаблона, если в позициях, где знак шаблона равен 0 или 1, она имеет тот же символ. Например, у шаблона 01*0*110 следующие представители: 01000110, 01001110.

Алгоритм работы

На рисунке изображена схема работы любого генетического алгоритма:

1. Создание популяции.

На этом этапе случайным образом создается начальная популяция особей. Фиксируется размер популяции (количество особей в ней - N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.

1. Селекция

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

Также существует такой метод отбора как элитизм – при нем самая приспособленная особь всегда переходит в следующее поколение. Элитизм обычно внедряют в другие методы отбора – сохраняют “элитную особь” вне зависимости от других условий селекции.

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

Турнирный отбор осуществляется следующим образом: из популяции случайным образом выбирается t особей, и лучшая из них помещается в промежуточную популяцию. Этот процесс повторяется N раз, пока промежуточная популяция не будет заполнена. Наиболее распространен вариант при t = 2.

Отбор усечением: популяция сортируется по приспособленности, затем берется заданная доля лучших, и из них случайным образом N раз выбирается особь для дальнейшего развития.

1. Скрещивание или кроссовер.

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

Родители: 11000011 и 10001001

Потомки: 11001001 и 10000011

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

Однородный кроссовер осуществляется следующим образом: один из детей наследует каждый бит с вероятностью p₀ у первого родителя, а иначе у второго. Второй ребенок получает все остальные не унаследованные биты. Обычно p₀ = 0.5.

1. Мутация.

Э тот этап ГА с заданной (обычно очень маленькой, порядка 1%) вероятностью случайным образом изменяет случайный ген особи.

До мутации: 011001100101101 После: 1011001101101101

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

1. 1Подготовила: Даша Д.

2. Литература: Пособие “Системы искусственного интеллекта” Тельнов Ю.Ф, Трембач В.М.

4