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

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

Лекция №1

Литература

Основная

1.  , ,

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

2.  , ,

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

3.  ,

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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; m1=3; m2=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’=xi; k=n.

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

Zk=(d mod 2)(mk-2(d’ mod (mk+1)))+d’ mod (mk+1).

Шаг 3. k=k-1; d’=d.

Если k1, то перейти к шагу 2. Иначе завершить вычисления.

В алгоритме операция a mod b означает остаток от деления a на b.

Пример 1.

6 mod 4 = 2

8 mod 5 = 3

0 mod 2 = 0

1 mod 3 = 1

4 mod 2 = 0

Пример 2.

Рассмотрим пересчет , представленного в таблице. Пусть .

Шаг 1. d’=14; k=n=2.

Шаг 2. d=[14/(3+1)]=[3 ]=3;

Z2=(3 mod 2)(3-2(14 mod (3+1)))+14 mod (3+1)=1(3-22)+2=1;

Z2=1.

Шаг 3. k=k-1=1 1; d’=3. Переходим к шагу 2.

Шаг 4. d=[3/(3+1)]=[ ]=0;

Z1=(0 mod 2)(3-2(3 mod (3+1)))+3 mod (3+1)=3 mod 4=3;

Z1=3.

Пример 3.

Построим таблицу МКГ для случая: n=4; m1=1; m2=2; m3=1; m4=2.

Т. е. , где

Это количество комбинаций:

Построим в координатном пространстве гиперкуб (точнее его проекцию на подмножество )

Таблица 2.

0	0000	12	0200	24	1100
1	0001	13	0201	25	1101
2	0002	14	0202	26	1102
3	0012	15	0212	27	1112
4	0011	16	0211	28	1111
5	0010	17	0210	29	1110
6	0110	18	1210	30	1010
7	0111	19	1211	31	1011
8	0112	20	1212	32	1012
9	0102	21	1202	33	1002
10	0101	22	1201	34	1001
11	0100	23	1200	35	1000

На рисунке изображена последовательность обхода вершин гиперкуба в пространстве при z1=0.

Данная последовательность обхода охватывает точки: 0xi17.

Для того, чтобы закодировать оставшиеся точки: 18xi35, можно использовать алгоритм пересчета.

Другой геометрический способ состоит в следующем. Необходимо изменить координату z1 на 1, т. е. положить z1=1. Это означает, что мы переходим в следующее сечение гиперкуба: при z1=1. После этого необходимо осуществить обход следующего сечения в обратном порядке. Это означает, что в таблице устанавливаем z1=1 для всех 18xi35, а остальные коды перезаписывать зеркально в ячейки, расположенные после xi=17.

Пример 4. Рассмотрим пересчет xi → МКГ(xi).

Шаг 1. d’=22; k=4; m4=2.

Шаг 2. d=[22/(2+1)]=[7]=7;

z4=(7 mod 2)(2-2(22 mod (2+1)))+22 mod (2+1)=1(2-21)+1=1;

z4=1.

Шаг 3. k=4-1=3 1; d’=7.

Шаг 4. d=[7/(1+1)]=[3]=3; m3=1;

z3=(3 mod 2)(1-2(7 mod (1+1)))+7 mod (1+1)=1(1-21)+1=0;

z3=0.

Шаг 5. k=3-1=2 1; d’=3; m2=2.

Шаг 6. d=[3/(2+1)]=1;

z2=(1 mod 2)(2-2(3 mod (2+1)))+3 mod (2+1)=1(2-20)+0=2;

z2=2;

Шаг 7. k=2-1=1 1; d’=1; m1=1;

Шаг 8. d=[1/(1+1)]=[]=0.

z1=(0 mod 2)(1-2(1 mod (1+0)))+1 mod (1+1)=1 mod 2=1;

z1=1;

В итоге получаем: Xi=22 z=[1201]

Что соответствует таблице.

Для обратного пересчета их z в xi можно использовать следующее соотношение:

 

 

Обозначим слагаемые через SⅠ, SⅡ, SⅢ, SⅣ.

Пример 5. Выполним пересчет:

z1 z2 z3 z4

z=[] xi=22;

m1=1; m2=2; m3=1; m4=2;

xi=SⅠ+SⅡ+SⅢ+SⅣ.

SⅠ=1(2+1)(1+1)(2+1)=1*3*2*3=18;

SⅠ=18;

SⅡ= ((z1 mod 2)(m2-2z2)+z2)(m3+1)(m4+1) + при j=2

+ (((z1+z2) mod 2)(m3-2z3)+z3)(m4+1) = при j=3

= ((1 mod 2)(2-2*2)+2)(1+1)(2+1) +

+ (((1+2) mod 2)(1-2*0)+0)(2+1) =

= (1*(-2)+2)*2*3 + (1*1+0)*3 = 0*2*3 + 1*3 = 0 + 3 = 3;

SⅡ=3;

SⅢ=((z1+z2+z3) mod 2)(m4-2z4)=((1+2+0) mod 2)(2-2*1)=1*0=0;

SⅢ=0;

SⅣ=z4=1;

SⅣ=1;

xi=18+3+0+1=22;

xi=22.

Таким образом, имеем:

xi z – оператор кодирования

z xi – оператор декодирования

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

xi= [ ]

Q(t)

Хромосомы генерируются случайным образом путем последовательного заполнения разрядов (генов) в соответствии с равномерным законом распределения.

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