Алгоритмы формирование функции пригодности (Лекции ТСМ)

Алгоритмы формирование функции пригодности

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

, (1)

где - множество подсистем («игроков»);

- показатель эффективности i-ой подсистемы, определенный на декартовом произведении ;

набор объединяет допустимые управления (управляющие параметры) подсистем (игроков) ;

- множество допустимых значений вектора .

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

Задачи, которые необходимо решить:

1. Построение множества Парето-оптимальных решений.

2. Поиск равновесия по Нэшу.

3. Поиск гарантирующих решений.

1. Задача скалярной оптимизации

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

(2)

Шаг 1. В популяции размером полагаем

Шаг 2. Для всех , проверяем выполнение условия:

(3)

Обозначим - количество точек , в котором выполняется условие (3).

Шаг 3. Сформулируем функцию :

(4)

Шаг 4. Полагаем . Если i ≤ N, то переходим к шагу 2, иначе переходим к шагу 5.

Шаг 5. STOP

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

Здесь q – параметр, влияющий на скорость сходимости ГА к оптимальному решению

2. Задача многокритериальной оптимизации.

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

где ;

(6)

Шаг 1. В популяции размером полагаем .

Шаг 2. Для всех , проверяем выполнение условия:

, (7)

или, что то же самое:

, (8)

При этом хотя бы одно из неравенств (8) – строгое.

Обозначим - количество точек , в которых выполняется условие (7).

Шаг 3. Сформируем функцию пригодности вида:

(9)

Шаг 4. Полагаем . Если , то переходим к шагу 2, иначе переходим к шагу 5.

Шаг 5. STOP.

Свойства функции пригодности вида (4)

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

2. Если , то . Это означает, что в точке функция достигает своего максимального значения относительно текущей популяции . То есть точка обладает минимальной степенью приспособленности в популяции .

3. Если , то .

Здесь q – параметр, влияющий на скорость сходимости ГА к оптимальному решению.

Свойства функции пригодности вида (9)

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

2. Если , то . Точка не принадлежит Парето-области. Чем больше , тем дальше от Парето-области.

3. Бескоалиционное взаимодействие между подсистемами. Поиск равновесия по Нэшу.

Рассмотрим теоретико-игровую модель бескоалиционного взаимодействия между управляющими подсистемами в виде:

, (1)

где - множество подсистем («игроков»);

- показатель эффективности i-ой подсистемы, определенный на декартовом произведении ;

набор объединяет допустимые управления (управляющие параметры) подсистем (игроков) ;

- множество допустимых значений вектора .

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

При решении задачи (1) будем использовать принцип равновесия по Нэшу.

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

, (2)

где

Алгоритм для формирования функции пригодности для ГА поиска равновесия по Нэшу

Шаг 1. Пусть - множество ТТО. Декодируем популяцию ТТО

,

с помощью бинарного кода Грея, где t – номер поколения.

Шаг 2. Фиксируем . Вычисление .

Шаг 3. Для каждого , вычисляем значения всех показателей эффективности в соответствующих точках:

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

, (3)

,

где - i-ый компонент s-ого элемента множества U(t).

Если точка является равновесием по Нэшу задачи (1), то для таблицы будет выполняться система неравенств:

, (4).

Если же хотя бы для одного в таблице существует подмножество

для элементов которого выполняется система неравенств:

, (5)

то не является равновесием по Нэшу в задаче (1).

Шаг 4. Каждому , поставим в соответствие функцию пригодности вида:

, (6)

где - количество точек , для которых выполняется система неравенств (5).

Таким образом векторному показателю соответствует векторная функция пригодности , обладающая следующим свойством:

1*)Если - равновесие по Нэшу, то

, (7)

2*) Если не является равновесием по Нэшу, то :

, (8)

Чем ближе к точке в пространстве функции пригодности , тем дальше расположена от , то есть тем является менее равновесной.

Шаг 5. Поставим в соответствие векторной функции скалярную функцию пригодности

, (9)

где - множество, для элементов которого выполняется условие (система неравенств):

, (10)

1) - точка, ближе всех расположенная к равновесию по Нэшу.

2) - точка, дальше всех расположенная к равновесию по Нэшу.

Функция далее используется для популяции «родителей». Для определения вероятности выбора ТТО в родителе строим интервал на основе рекуррентных соображений:

, (11)

Пример.

Таблица 1

1	10	10
2	40	30
3	30	60
4	60	65
	70	70

Таблица 1.1

2
3
4

Таблица 1.2

2
3
4

Построим векторную функцию пригодности :

; Таблица 2.1

;

1
3
4

; Таблица 2.2

;

1
3
4

Вычислим :

; Таблица 3.1

;

1
2
4

; Таблица 3.2

;

1
2
4

Вычислим :

; Таблица 4.1

;

1
2
3

; Таблица 4.2

;

1
2
3

Вычислим :