Решебник_МО

материалов от места i к месту k, а также bψ(i)ψ(k) – объем продукции передаваемой от j-й машины к m-й машине (i, j, k, m = 1,…, n). Тогда для некоторой перестановки ψ необходимо минимизировать целевую

Пространство решений составляет n! Каждое отдельное решение (перестановка) кодируется, например, в виде вектора (2,6,1,3,5,4), где внутри перестановки указан номер машины, а место ее установки определяется порядковым номером внутри вектора. Пусть применяется (1, 100)-селекция, т.е. из каждого родителя образуется путем мутации 100 потомков без всякой рекомбинации. Мутация заключается в случайной взаимной перестановке двух машин. Потомок с минимальным значением целевой функции образует новую родительскую популяцию, а родитель участия в отборе больше не принимает.

С помощью программного счетчика нетрудно установить, как часто вновь образованный потомок имеет худшее значение функции пригодности, нежели родитель. После того как счетчик достигнет некоторого граничного значения (мы эмпирически установили, что граница составляет величину около (n/10+2)), необходимо начать процедуру дестабилизации. Она заключается в проведении от трех до восьми парных мутаций и завершается в момент обнуления счетчика. После завершения дестабилизации процесс оптимизации продолжается по прежней схеме. Моделирование эволюции прекращается по достижении tmax – максимального числа шагов эволюции. В качестве решения выбирается лучшее из найденных в ходе эволюции решений. Начальная перестановка выбирается случайно.

ЭВОЛЮЦИОННОЕ ПРОГРАММИРОВАНИЕ

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

101

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

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

Рассмотрим алгоритм ЭП на примере задачи минимизации функции F(а1,…, аn), зависящей от n непрерывных переменных, которые представляются в виде вектора Ā = (а1,…, аn). Вектор Ā в ЭП соответствует отдельному артефакту. Шаги алгоритма следующие.

Ш а г 1. Инициализация. На этапе инициализации случайным образом

функцию Φ(Āi), которая зачастую равна значению целевой функции (Φ = F, хотя в общем случае они могут и не совпадать). В общем

случае считаем, что Φ(Āi) = Ω(F(Āi), ξi). Ш а г 3. Генерация потомков.

102

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

Здесь S0 это стартовое состояние, входом которого являлось решение узника говорить («г»), а, например, запись в столбце S4 (г,г/м, S2) означает, что узник на очередном ходе принял решение говорить, на предыдущем ходе использовалась стратегия г/м, автомат из состояния S4 переходит в состояние S2.

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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ И ТЕСТЫ

1.Что такое эволюционные алгоритмы?

2.Какова структура эволюционных алгоритмов?

3.Каковы особенности генетического программирования?

4.Какие действия предусматривает настройка алгоритма генетического программирования?

5.Какие элементы в алгоритме генетического программирования фигурируют в качестве множества function set ?

6.Какие элементы в алгоритме генетического программирования фигурируют в качестве множества terminal set ?

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

104

8.Что собой представляет процесс генетического программирования?

9.Что собой представляет оператор мутации в генетическом программировании?

10.Что собой представляет оператор пермутации в генетическом программировании?

11.Что собой представляет оператор кроссинговера в генетическом программировании?

12.Что собой представляет оператор редактирования путем замены в генетическом программировании?

13.Что собой представляет унарный оператор инкапсуляции в генетическом программировании?

14.Что собой представляет унарный оператор упаковки в генетическом программировании?

15.Что собой представляет унарный оператор лифтинга в генетическом программировании?

16.Что собой представляет концепция автоматически определяемых функций?

17.Что собой представляет эффект «компрессионного давления» в генетическом программировании?

18.Сформулируйте практические рекомендации по применению алгоритмов ГП.

19.Как применить генетическое программирование для решения задачи символьной регрессии?

20.В чем состоят основные особенности эволюционных стратегий?

21.Охарактеризуйте основные элементы модели эволюционных стратегий.

22.Перечислите основные этапы эволюционных стратегий.

23.Каковы критерии остановки алгоритма эволюционных стратегий?

24.В чем состоят основные особенности эволюционного программмирования?

25.Охарактеризуйте основные элементы модели эволюционного программирования.

26.Перечислите основные этапы эволюционного программирования.

27.В чем состоит «дилемма узников»?

28.Как представить процесс эволюционного программирования в виде однородной цепи Маркова?

105

29.На каких бенчмарках тестировались алгоритмы эволюционного программирования?

30.Сравните ГА, ГП, ЭС и ЭП между собой.

31.Каковы критерии того, насколько подходящим является

эволюционный алгоритм для решения тех или иных задач?

Тесты

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

2.Способность системы изменять свое состояние и поведение (параметры, структуру, алгоритм функционирования) в зависимости от изменения условий внешней среды путём накапливания и использования информации о ней: а) абдукция, б) адаптация, в) генерация, г) когерентность, д) прогнозирование.

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

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

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

106

а) генетический алгоритм, б) генетическое программирование, в) градиентный алгоритм, г) эволюционное программирование, д) эволюционные стратегии.

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

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

8.Упорядоченная последовательность команд, подлежащая обработке: а) иерархия, б) кластер, в) метод, г) программа, д) шаблон.

9.Основные элементы эволюционного алгоритма: а) генотип; б) композиция операторов; в) критерий качества; г) начальная популяция; д) правило резолюции; е) селективный отбор; ж) сумматор; з) фаззификация; и) фенотип.

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

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

закономерность, г) правило, д) теорема.

13. Ключевым элементом алгоритмов эволюционных вычислений, инспирированных природными системами, является построение начальной модели, правил, по которым она эволюционирует, подходов к представлению (кодированию) решений, Это: а) гипотеза, б) дилемма, в) закономерность, г) правило, д) теорема.

107

14.Модели эволюционных вычислений применимы к решению задач,

укоторых переменные могут быть лингвистическими и не иметь количественного выражения, Это: а) гипотеза, б) дилемма, в) закономерность, г) правило, д) теорема.

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

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

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

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

19.Элементами function set в генетическом программировании могут быть: а) арифметические операции; б) булевы операции, в) константы, г) переменные, д) циклы.

20.Элементами terminal set в генетическом программировании могут быть: а) арифметические операции; б) булевы операции, в) константы, г) переменные, д) циклы.

21.Записи вида +( / (a,+(b, c)), *(x, – (y, z))) в префиксной форме древовидной структуры в генетическом программировании соответствует: а) (((b + c) /a) + (x*(z – y))); б) (((b + c) /a) + (x*(y –

108

z))), в) ((a / (b + c)) + (x * (y – z))), г) ((a / (b + c)) * (x + (y – z))), д)

((a * (b + c)) / (x * (y – z))).

22.В алгоритме генетического программирования используются операторы: а) кроссинговера; б) лифтинга, в) миграции, г) пермутации, д) сегрегации.

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

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

25.В алгоритме эволюционных стратегий пропорция μ / λ (число родителей к числу потомков) указывает на степень «суровости» селекции. Установлено, что максимальное быстродействие алгоритма эволюционных стратегий достигается при соотношении

μ/λ из интервала: а) [2,3]; б) [5,7], в) [1/5, 1/7], г) [1/2, 1/3], д) [1, 10].

26.Эволюционные алгоритмы являются: а) ассоциативными; б) детер-

минированными, в) недетерминированными, г) стационарными, д) транзитивными.

27.Для оценки того, трудной или легкой для эволюционного алгоритма является прикладная проблема необходимо оценить коэффициент: а) гетерогенности; б) интерференции, в) корреляции, г) неопределенности, д) релевантности.

28.Процесс, посредством которого альтернативные решения с

«лучшим» значением целевой функции имеют больше

109

возможностей для воспроизводства потомков, называется: а) мутация; б) отбор, в) репродукция, г) селекция, д) эволюция.

29. Процедура, устанавливающая порядок обмена хромосом между популяциями называется: а) диффузия; б) миграция, в) мутация, г) сегрегация, д) транслокация.

УПРАЖНЕНИЯ

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

2 ((x 3) y /(5 1)) .

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

(x & true) ((x y) (z (x & y))) .

3.Представить в виде древовидной структуры для работы алгоритма генетического программирования следующую программу:

i=1

While (i<20)

{

i=i+1

}

4.Найти с помощью алгоритма генетического программирования

функцию y = f(xi), i = 1,…, n. Алгоритм имеет следующие параметры. Множество function set F={+, -, /, sin, cos}. Множество terminal set T R {x}. Функция качества – среднеквадратичная

ошибка, Размер популяции равен 1000. Останов алгоритма если достигнуто заданное число шагов эволюции или f (xi ) yi 0,0001.

5.Создать у напитка цветовую гамму, похожую на вишневое бренди. Ингридиенты: вода+красный, желтый и синий красители. Хромосома <w, r, g, b>. Объем напитка 30 мл. Селекция (1/8). Функцию качества определяют студенты, которые смешивают ингридиенты и сравнивают цвет напитка на степень его совпадения с целевым цветом. Критерий останова – студент доволен цветом созданного напитка.

110