ТСМ-1 (1088236)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Технологии системного моделирования

Лекция №1

Литература

Основная

1. Емельянов В.В., Курейчик В.М., Курейчик В.В.

Теория и практика эволюционного моделирования. - Москва: Физматлит, 2003-432 с.

1. Гладков Л.А., Курейчик В.М., Курейчик В.В.

Генетические алгоритмы. – Москва: Физматлит, 2006-320 с.

1. Вороновский Г.К., Махотило К.В.

Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. – Харьков: Основа, 1997-112 с.

Дополнительная

1. Воронов Е.М. Методы оптимизации управления многообъектными многокритериальными системами на основе стабильно-эффективных игровых решений. – Москва: Изд. МГТУ им. Н.Э. Баумана 2001-576 с.

Введение

Одной из актуальных научно-технических проблем в настоящее время является разработка математических методов и моделей для исследования структурно-сложных систем (ССС) управления и обработки информации.

Наиболее адекватным математическим аппаратом для построения моделей ССС является теоретико-игровой подход, позволяющий учесть такие важные в системном аспекте их признаки, как иерархичность, многообъектность наличие неопределенных факторов.

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

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

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

Суть стратегии ЭМ состоит в построении вычислительных алгоритмов, в основе которых лежат целенаправленные процессы гибели-размножения, при которых размножению соответствует появление новых объектов, а гибели – удаление объектов в соответствии с определенными критериями отбора.

Генетические алгоритмы (ГА)

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

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

Механизм генетики основан на следующих положениях:

1. Все признаки организмов (особей) находятся под контролем генов, т.е. элементарных структурных единиц наследственной информации.

2. Гены объединяются в хромосомы и составляют генотип особи – общая совокупность наследственных факторов. В естественных системах организм, формируется (его облик, отдельные признаки, свойства) посредством связи генотипа с окружающей средой и называется фенотипом.

3. Гены могут изменяться – мутировать.

4. Мутации отдельных генов приводят к изменению отдельных внешних (фенотипических) признаков или фенов.

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

Таким образом, ГА, в отличии от численных методов оптимизации, заимствуют из биологии:

• Понятийный аппарат;

• Идею коллективного поиска экстремума при помощи популяции особей;

• Способы представления генетической информации;

• Способы передачи генетической информации от поколения к поколению (генетические операторы);

• Идею о преимущественном размножении наиболее приспособленных особей.

На основе вышесказанных особенностей можно представить ГА структурно в виде следующей последовательности основных шагов (репродуктивный план Холланда).

Репродуктивный план Холланда (ГА)

Шаг 1. Инициализация начальной популяции. Ввести точку отсчета поколений тестовых точек–особей (ТТО) . Инициализировать случайным образом начальную переменную генотипов ТТО . Сформулировать на основе популяцию ТТО . Т.е. выполнить преобразование: .

Шаг 2. Оценка приспособленности каждой TTO .

Шаг 3. Выбор из популяции массива родителей (n – четное), для скрещивания с учетом их приспособленности.

Шаг 4. Формирование массива генотипов потомков на основе воздействия на генотипы родителей генетических операторов. Размещение в . Если новая популяция заполнена, то перейти к шагу 5. Иначе перейти к шагу 3.

Шаг 5. Выполнить преобразование . Положить

Шаг 6. Проверить критерий останова алгоритма. Если критерий не выполняется, то перейти к шагу 2. Иначе перейти к шагу 7.

Шаг 7. Считать множеством субоптимальных решений. Остановить алгоритм.

Рассмотрим содержание основных шагов ГА более подробно. Итак, исследуется оптимизационная задача вида:

Определить min , , (1)

где (2)

Представление генетической информации

В определенном смысле можно увидеть, что понятие «вектор переменных» играет в технике ту же роль, что и понятие «генотип» в биологии. Группируя оптимизируемые параметры объекта в вектор переменных, мы, по существу, придаем им статус генетической информации. Действительно, с одной стороны этой информации достаточно, чтобы построить сам объект (вычислить целевую функцию), а с другой стороны она служит походным материалом при генерации генотипов объектов следующего поколения (координат новых пробных точек в пространстве параметров).

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

• Целочисленное кодирование на основе многозначности кода Грея (ген принимает значение из множества натуральных чисел)

• Бинарное кодирование на основе бинарного кода Грея (ген принимает значение 0 и 1)

• Вещественное кодирование (ген принимает значение из множества вещественных чисел)

• Символьное кодирование (ген принимает значение из некоторого алфавита символов)

Многозначный код Грея

Рассмотрим целочисленный вектор

, (1)

где . (2)

Обозначим как множество всех векторов вида (1)(2). Тогда мощность множества , количество элементов (комбинаций), можно вычислить по формуле: .

Рассмотрим случай: n=2; m₁=3; m₂=3.

В данном случае |Z|=(3+1)(3+1)=16. Расположим векторы (т.е. с помощью данного кода можно закодировать числа ) в следующем порядке.

Таблица 1.

0	0 0
1	0 1
2	0 2
3	0 3
4	1 3
5	1 2
6	1 1
7	1 0
8	2 0
9	2 1
10	2 2
11	2 3
12	3 3
13	3 2
14	3 1
15	3 0

Порядок расположения многозначных кодов Грея (МКГ) объясняется следующим образом. Построим в координатном пространстве гиперкуб, узлы которого соответствуют всем возможным комбинациям МКГ с указанными характеристиками.

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

Особенность МКГ состоит в том, что любые два числа , записанные в десятичной системе счисления, имеют

МКГ, различающийся между собой на 1 только в одном каком-либо разряде, т.е. мало отличающиеся друг от друга.

Например, для соседними точками в гиперкубе являются: 9; 11. Все они имеют МКГ, отличающийся от МКГ на 1 в каком-либо разряде. Соответственно единичным изменениям соответствуют малые изменения МКГ (единица разряда).

Обратное, вообще говоря, не взаимно (числа ). Тем не менее, указанное свойство улучшает обходимость ГА и opt(?). Пересчет от в МКГ( ) осуществляется с помощью следующего алгоритма.

Алгоритм пересчета ( )

Шаг 1. d’=x_i; k=n.

Шаг 2. d=[d’/(m_k+1)].

Z_k=(d mod 2) (m_k-2 (d’ mod (m_k+1)))+d’ mod (m_k+1).

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций