ОПТИМИЗАЦИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ КОМБИНАТОРНОГО ТИПА С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Д.И.Батищев, Е.А.Неймарк, Н.В. Старостин 200

Задача нестационарной дискретной оптимизации

Вид целевой функции

F1*
F2*
x1*
x2*
F(x,t)
x
S1*
S2*
t
a
b
S

Стационарная задача об одномерном ранце

Нестационарная задача об одномерном ранце

Стационарная задача коммивояжера

Нестационарная задача коммивояжера

Методы решения нестационарных задач
методы увеличения генетического разнообразия при изменении среды [2,10],
методы постоянного поддержания генетического разнообразия [4,5],
методы, использующие дополнительную память [3,8,9],
методы, использующие дополнительные популяции [1,6].

Методы, использующие дополнительную память: диплоидное представление
μ(s)
генотип
фенотип
приспособленность

Схемы доминирования :
триаллельная
Алфавит А={0,1,i} – возможные аллели
Матрица доминирования:

Схемы доминирования :
четырехаллельная
Алфавит А={0,1,i,o} Матрица доминирования:

Методы, использующие дополнительную память: структурное представление
генотип
Уровень регулирующих генов
Уровень
простых
генов

Структурное представление
Допустимые решения
Уровень регулирующих генов
Уровень простых генов

Алгоритм с памятью
Формируется начальная
популяция
Состояние среды
изменилось
Генетический поиск
Состояние среды
индикатор среды Ik
Индикатор Ik
найден в базе
Популяция загружается
из базы
индикатор среды Ik
НЕТ
ДА
НЕТ
ДА
k:=0
k:=k+1

Алгоритм с памятью
F(x,t)
x
Индекс состояния среды: I2
Память
Индекса I2 в памяти нет
Индекс I2 найден в памяти
Формируется новая популяция
Популяция берется из памяти

Пример решения нестационарной задачи о ранце

Пример решения нестационарной задачи о ранце

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

Сравнение эффективности алгоритмов