Практический курс по дисциплине «Системы искусственного интеллекта» (стр. 7 )

Предлагаются характеристики для оценки состояния популяции:

1.  Разнообразие генотипа: дисперсия значений генов, хеммингово или евклидово расстояние особей i-й генерации , гистограмма частотности генов.

2.  Разнообразие фенотипа , где , – соответственно среднее и лучшее значение ФП .

3.  Приращение лучшего фенотипа как разность лучшего значения ФП достигнутого в генерациях и .

4.  Приращение среднего фенотипа .

Можно также использовать пиковую характеристику близости к экстремуму:

, (49)

как отношение доли особей, обладающих минимальным расстоянием до оптимального решения к данному расстоянию.

Такая характеристика позволяет оценивать работу алгоритма в «оврагах» и «локальных ямах» (знаменатель характеристики), одновременно учитывая степень разнообразия в популяции (числитель характеристики).

4.4.3.  Теорема шим

Пусть гены годируются бинарно, тогда генотип особи представляется бинарной строкой.

Шима – это строка длины l (как и длина любой строки популяции), состоящая из знаков алфавита {0; 1; *}, где {*} – неопределенный символ. Каждая шима определяет множество всех бинарных строк длины l, имеющих в соответствующих позициях либо 0, либо 1, в зависимости от того, какой бит находится в соответствующей позиции самой шимы. Например, шима, 10**1, определяет собой множество из четырех пятибитовых строк {10001; 10011; 10101; 10111}. У шим выделяют два свойства – порядок и определенная длина.

Порядок шимы – это число определенных битов («0» или «1») в шиме.

Определенная длина – расстояние между крайними определенными битами в шиме. Например, вышеупомянутая шима имеет порядок o(10**1) = 3, а определенная длина (10**1) = 4. Каждая строка в популяции является примером 2l шим.

Строящие блоки (Goldberg, 1989) – это шимы, обладающие:

−  высокой приспособленностью,

−  низким порядком,

−  короткой определенной длиной.

Приспособленность шимы определяется как среднее приспособленностей примеров, которые ее содержат.

После процедуры отбора остаются только строки с более высокой приспособленностью. Следовательно, строки, которые являются примерами шим с высокой приспособленностью, выбираются чаще. Кроссинговер реже разрушает шимы с более короткой определенной длиной, а мутация реже разрушает шимы с низким порядком. Поэтому такие шимы имеют больше шансов переходить из поколения в поколение. Холланд (1992) показал, что, в то время, как ГА явным образом обрабатывает n строк на каждом поколении, параллельно неявно обрабатываются порядка таких коротких шим малой длины и с высокой приспособленностью (полезных шим, «useful schemata»). Он называл это явление неявным параллелизмом. Для решения реальных задач присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей.

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

Пусть m(H, t) – число примеров шимы H в t-ом поколении. Вычислим ожидаемое число примеров H в следующем поколении или m(H, t + 1) в терминах m(H, t). Простой ГА каждой строке ставит в соответствие вероятность ее «выживания» при отборе пропорционально ее приспособленности. Ожидается, что шима H может быть выбрана

раз,

где – средняя пригодность популяции, а f(H) – средняя пригодность тех строк в популяции, которые являются примерами H.

Вероятность того, что одноточечный кроссинговер разрушит шиму, равна вероятности того, что точка разрыва попадет между определенными битами. Вероятность же того, что H «переживает» кроссинговер, не меньше:

.

Эта вероятность – неравенство, поскольку шима сможет выжить, если в кроссинговере участвовал также пример похожей шимы. Вероятность того, что H переживет точечную мутацию:

.

Это выражение можно аппроксимировать как 1 – o(H) для малого и o(H). Произведение ожидаемого число отборов и вероятностей выживания известно как теорема шим:

.

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

4.5.  Реализация моделей генетического алгоритма

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

4.5.1.  Постановка задачи

1.  Изучить устройство и работу канонического, CHC, островного ГА и модели Genitor.

2.  Выбрать тестовую функцию и модель ГА по согласованию с преподавателем.

3.  Составить программу, реализующую оптимизацию выбранной функции с помощью заданной модели ГА.

4.  Испытать программное обеспечение для различных значений параметров выбранной модели ГА и используемых генетических операторов.

5.  Произвести оценку скорости и качества процесса сходимости для различных случаев, систематизировав полученные результаты в таблицы. Сделать выводы.

6.  Результаты работы оформить в виде отчета в текстовом редакторе.

4.5.2.  Рекомендации по созданию программного обеспечения

После изучения теоретического материала и выбора исходной функции и модели ГА необходимо определиться с кодированием хромосом. Желательно при создании программного обеспечения использовать объектно-ориентированный язык, чтобы была возможность динамически варьировать параметры генетических операторов – порождать популяции разных размеров.

4.5.3.  Рекомендации по исследованиям

Отметим ряд условий объективности экспериментов по анализу эффективности моделей ГА.

Во-первых, учитывая вероятностно-детерминированный характер исследуемых алгоритмов, получаемые в программном комплексе характеристики работы ГА необходимо усреднять по большому числу испытаний алгоритма. Для интегральных статистик (вычисляемых усреднением по популяции) достаточное число испытаний определено порядка 100 (размер популяции ), при этом относительные отклонения получаемых интегральных статистик ГА (на примере ) не превосходят 0.05. Достоверность получаемых характеристик растет с увеличением размера популяции. Для статистик пиковых величин (наибольшее значение ФП внутри популяции, близость лучшей особи к оптимуму и др.) достаточное количество испытаний для усреднения статистики порядка 2000 и мало зависит от размера популяции.

Во-вторых, необходимо проводить эксперименты в различных ситуациях исходных данных ГА. Для этого в работе используются две тестовые функции:

1)  параболоид, легко поддающийся оптимизации:

2)  овражная функция Розенброка, для случая функций двух и многих переменных:

.

Предлагается провести семь экспериментов.

Эксперимент № 1. Определение достаточного числа испытаний для оценки интегральных статистик по популяции; рассматривается модификация ПГА для наихудшего (с позиции детерминизма процесса реализации) случая (малая популяция, много мутаций).

Параметры эксперимента:

−  исходные данные: f – функция Розенброка, n = 2, , пространство поиска точность вычисления ФП ,

−  параметры ГА: l = 20, , , пропорциональный отбор.

Необходимо реализовать ГА и рассчитать:

−  нормированное среднее значение интегральной статистики a) q = 100, b) q = 2000;

−  величину относительного отклонения интегральных статистик a) q = 100, b) q = 2000.

Эксперимент № 2. Определение зависимости сходимости простого ГА от соотношения участия ГО формирования пулов .

Параметры эксперимента:

−  исходные данные: f – параболоид, n = 2,

−  параметры ГА: l = 20, , пропорциональный отбор, 0, 0.025, , 0, 0.1, ... 1.

Необходимо реализовать ГА и рассчитать:

−  зависимости результата сходимости от доли участия в ГА операторов кроссинговера и мутаций для различных значений доли участия оператора репродукции;

−  зависимости результата сходимости от доли участия в ГА операторов кроссинговера и репродукции для различных значений доли участия оператора мутации;

−  три характерных зависимости качества сходимости в процессе работы ГА.

Эксперимент № 3. Определение зависимости сходимости ПГА от формы ФП.

Параметры эксперимента:

−  исходные данные: f – функция Розенброка, n = 2,

−  параметры ГА: l = 20, 0, 0.025, , 0, 0.1, ... 1.

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

Эксперимент № 4. Определение зависимости сходимости ПГА от размера популяции l.

Параметры эксперимента:

−  исходные данные: f параболоид, функции Розенброка, n = 2,

−  параметры ГА: l 5,10, =1, 0, 0.025, , 0, 0.1, ... 1.

Необходимо реализовать ГА и рассчитать:

−  зависимости результата сходимости от доли участия в ГА операторов кроссинговера и мутаций для различных значений численности популяции для функции Розенброка;

−  характерные зависимости качества сходимости в процессе ГА для различных значений численности популяции функции Розенброка;

−  качество сходимости на i-м шаге работы ГА с оптимальными параметрами с наличием и отсутствием мутаций: a) , б)

Аналогичный эксперимент необходимо произвести для параболоида.

Эксперимент № 5. Сравнение оператора мутации с улучшенным оператором мутации.

Параметры эксперимента:

−  исходные данные: f параболоид, функция Розенброка, n = 2,

−  параметры ГА: l = 20, 0, 0.1, ...1,

Необходимо реализовать ГА и рассчитать:

−  результаты использования улучшенного оператора мутации для ФП параболоид,

−  результаты для ФП Розенброка.

Эксперимент № 6. Зависимость сходимости от размерности пространства поиска.

Параметры эксперимента:

−  исходные данные: f – функция Розенброка, n = 3, 5, 10,

−  параметры ГА: l = 10, 0, 0.1, ... 1,

Необходимо реализовать ГА и рассчитать: максимальную сходимость, максимальную сходимость без мутаций: а) n = 3, б) n = 5, в) n = 10.

Эксперимент № 7. Зависимость процесса сходимости от интенсивности отбора.

Параметры эксперимента:

−  исходные данные: fпараболоид, функция Розенброка, n = 2,

−  параметры ГА: l = 20, отбор с нелинейной плотностью вероятности селекции

Необходимо реализовать ГА для тестовой функции коэффициента интенсивности отбора и привести типовой процесс сходимости для данной функции отбора.

4.5.4.  Оформление результатов

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

Таблица 5

Численные значения экспериментов

Модель ГА	Тестовая функция	Варьируемый параметр	Оптимальное значение параметра	Число тактов сходимости к оптимуму	Минимальное достигнутое отклонение особи от оптимума в процессе сходимости

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.  Кузин, кибернетики: учеб. пособие для вузов / ; – М.: Энергия, 1979. – 584 с.

2.  Фор, А. Восприятие и распознавание образов / А. Фор. – М.: Машиностроение, 1989. – 272 с.

3.  Фу, К. Последовательные методы в распознавании образов и обучении машин / К. Фу; перев. с англ. – М.: Наука, 1971. – 256 с.

4.  Уоссерман, Ф. Нейрокомпьютерная техника. Теория и практика / Ф. Уоссерман; перев. с англ. – М.: Мир, 1992. – 240 с.

5.  Маккаллок,  исчисление идей, относящихся к нервной активности / , В. Питтс // Автоматы: сборник / Под. ред. К. э. шеннона и Дж. Маккарти. – М.: Изд-во иностр. лит., 1956. – С. 365–384.

6.  Минский, М. Л. Персептроны / , С. Пейперт; перев. с англ. – М.: Мир, 1971. – 261 c.

7.  Розенблатт, Ф. Принципы нейродинамики / Ф. Розенблатт; перев. с англ. – М.: Мир, 1965. – 480 с.

8.  Grossberg, S. Some networks that can learn, remember and reproduce any number of complicated space-time patterns / S. Grossberg; Journal of Mathematics and Mechanics, 1969. 19:53-91.

9.  Kohonen, Т. Self-organization and associative memory / T. Kohonen; – 2d ed. – New-York, 1988. Springer-Verlag.

10.  Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / [и др.]. – Харьков: ОСНОВА, 1997. – 112 с.

11.  Батищев, многоэкстремальных функций с помощью генетических алгоритмов: сб. науч. тр. / , // Высокие технологии в технике, медицине и образовании. – Воронеж, ВГТУ, 1997. – C. 4–17.

12.  Методы генетического поиска: науч. издание / [и др.]. под ред. . – Таганрог: Изд-во ТРТУ, 2002. – 122 с.

13.  Оптимизационные структуры при проектировании на основе методов гомеостатики, эволюционного развития и самоорганизации: науч. издание / [и др.]. Часть 2. под ред. . – Таганрог: Изд-во ТРТУ, 2003. – 150 с.

14.  Голубин, параметров генетического алгоритма с помощью программного комплекса «gensearch»: сб. науч. трудов / // Международная научно-техническая конференция «Интеллектуальные системы» (AIS’05) и «Интеллектуальные САПР» (CAD-2005); в 3-х томах. Т. 1. – М.: ФИЗМАТЛИТ, 2005. – С. 42.

15.  Голубин, генетические алгоритмы: сб. науч. трудов / , // Международная научно-техническая конференция «Интеллектуальные системы» (AIS’05) и «Интеллектуальные САПР» (CAD-2005); в 3-х томах. Т. 1. – М.: ФИЗМАТЛИТ, 2005. – С. 39–45.

Электронный аналог печатного издания:

Степанченко, курс по дисциплине «Системы искуственного интеллекта»: учеб. пособие / , ; ВолгГТУ, Волгоград, 2010. – 104 с.

Редактор

Темплан 2010 г., поз. № 41К.

Подписано в печать г. Формат 60×84 1/16.

Бумага листовая. Печать офсетная.

Усл. печ. л. 6,5. Усл. авт. л. 6,31.

Тираж 21 экз. Заказ № 22

Волгоградский государственный технический университет

г. Волгоград, пр. Ленина, 28, корп. 1.

Отпечатано в КТИ

, каб. 4.5

2,57 Мб

1 компакт-диск

Системные требования:

Требования к компьютеру: процессор не ниже Pentium III; оперативная память не менее 128 Мб; жёсткий диск: свободное место на диске не менее 5 Мб; экран: монитор Super VGA с разрешением 800×600 точек или более, поддерживающий 256 цветов; периферийные устройства: клавиатура, мышь; дисковод: дисковод для компакт-дисков; операционная система: Microsoft Windows XP или более поздняя версия; установленное программное обеспечение: Microsoft Word 2000.