УДК 681.3.015

Д.И.Батищев, С.А.Исаев, Е.К.Ремер

Эволюционно-генетический подход к решению задач невыпуклой оптимизации

(опубликовано в сборнике статей, издаваемом ВГТУ, осень 1998) 		наверх
.
Рассматривается класс задач непрерывной оптимизации, связанный с максимизацией нелинейной функции, определенной в невыпуклой области, которая, в общем случае, может быть многосвязной. Эволюционно-генетический подход к решению данного класса задач основан на сведении нелинейных задач с помощью штрафных функций к задаче безусловной оптимизации, решение которой осуществляется с помощью генетического алгоритма.

Введение

Большинство реальных задач инженерного проектирования математически могут быть сформулированы как задачи нелинейного программирования, при этом на область варьируемых параметров обычно накладываются функциональные ограничения в виде неравенств [1]:

,

(1)
где ;
D = { | } – пространство поиска;

(2)
S = { | } – допустимое множество.

(3)
Вопросы, связанные с построением эффективных методов оптимизации для данного класса экстремальных задач, представляют значительный интерес как с теоретической, так и с практической точек зрения. С теоретической точки зрения такие исследования позволяют выяснить потенциальные возможности алгоритмов оптимизации. С точки же зрения практики, использование эффективных методов в качестве вспомогательных процедур является важным при решении сложных задач, требующих большого объема вычислений или проведения дорогостоящих экспериментов.
В статье изложен один из подходов к решению задач нелинейного невыпуклого программирования. Рассматриваемый метод относится к классу генетических алгоритмов (ГА), моделирующих основные механизмы природной эволюции. Представлен ряд методов штрафа для недопустимых решений. На классе тестовых функций проведен вычислительный эксперимент и оценена эффективность предлагаемого подхода.
В общем случае исследуемая многопараметрическая функция f(X) может быть многоэкстремальной, недифференцируемой, разрывной и т.д. Допустимая область, задаваемая нелинейными ограничениями gj(X), может быть невыпуклой или состоящей из нескольких компонент связности.

К началу документа

Генетический Алгоритм

 В основе предлагаемого подхода к решению задач нелинейного программирование лежит генетический алгоритм поиска экстремальных значений в задачах непрерывной оптимизации [2]. Применение ГА допускает возможность эффективного поиска в отсутствии дополнительной информации о свойствах функции и характере ограничений.
Принцип работы ГА основан на моделировании некоторых механизмов популяционной генетики, известных в биологических системах. Важное отличие используемого генетического алгоритма от традиционных алгоритмов состоит в построении новой символьной модели и применении новых генетических операторов. Подробнее используемый ГА описан в [2,3]. Здесь же мы рассмотрим лишь основные операторы и суть символьной модели ГА.
При построении процедуры поиска множество решений представляется в виде конечной популяции особей. Численность популяции остается неизменной на каждом этапе эволюции. Каждая особь обладает определенным набором признаков: генотипом (или хромосомным набором), фенотипом и значением приспособленности. Генотип особи – это бинарная строка фиксированной длины, описывающая номер гиперкуба в разбиении пространства параметров; фенотип – вектор, компонентами которого являются координаты точки (особи) в пространстве параметров; приспособленность особи увязывается со значением функции в этой точке. Такая модель допускает существование нескольких особей, обладающих одинаковыми хромосомными наборами, но различными фенотипическими признаками (что, кстати, имеет место в природе) и, соответственно, различными мерами приспособленности.
При формировании родительских пар используются две схемы: панмексия (создание пар из случайно выбранных особей) и генотипический аутбридинг (когда пару с большей вероятностью могут составить особи, генотипы которых максимально различны). Число пар фиксировано и является одним из параметров ГА.
В качестве кроссоверов использовались двухточечный и однородный операторы. Кроссовер проводится для заданного числа брачных пар.
При отборе особей в следующее поколение используется отбором “вытеснением”, при котором новое поколение формируется из лучших представителей хромосомных наборов [2].
Для повышения эффективности алгоритма предлагается использовать следующие три эвристических приема.

К началу документа

Применение алгоритма для задач с ограничениями

 Специфика задач с ограничениями связана с проблемой существования недопустимых особей, т.е. особей, фенотипические признаки которых не удовлетворяют заданным ограничениям. Будем говорить, что фенотипические признаки особи не удовлетворяют заданным ограничениям, если найдется такой номер i, что gi(X)>0.
Методика решения задачи нелинейного программирования при наличии ограничений построена на использовании методов штрафа, сводящих задачу оптимизации на невыпуклой области к поиску на гиперпараллелепипеде.
Для решения новой экстремальной задачи:
, где – целевая функция Ф(х1,х2,…,хN) представлена разностью исходной функции f(х1,х2,…,хN) и штрафа Р(х1,х2,…,хN), – применялся генетический алгоритм.

(4)
В качестве штрафа выбирается некоторая функция, принимающая положительные значения на недопустимой области и нулевое значение на области, где выполняются все ограничения.
Описываемый подход предполагает сведение системы ограничений gj(X) j = 1,2,…,m к одному обобщенному ограничению G(X) с помощью преобразования.
G(X) = max {hj(X)} = max {max {gj(X), 0}}, j=1,2,...m.
При этом, если gj(X) < 0 для любогоj = 1, 2,...,m, то G(X) = 0.
Если же хотя бы для одного i (i=1,,2,…,m), gi(X) > 0, то G(X) > 0.
Довольно часто при решении реальных задач возникает ситуация, когда допустимая область S является объединением нескольких областей SP:
S = U SP, p = 1, 2,… k.
Каждая элементарная область SP задается некоторым набором ограничений: {g1P, g2P, ...gmpP}. При такой формулировке решение задачи (4) должно удовлетворять, по крайней мере, одному такому набору, при этом вовсе не обязательно, чтобы выполнялись все существующие ограничения.
Для решения такого рода задач, когда для объединения ограничений используется оператор “или”, предлагается модифицировать функцию G(X) следующим образом.
Если набор ограничений представлен в виде:
{g11(X) и g21(X) и ... и gm11(X)} или {g12(X) и g22(X) и ... и gm22 (X)}…
Тогда hjP = max {giP, 0} i = 1, 2, ...mP.
В этом случае обобщенное ограничение G(X) можно записать следующим образом:
G(X) = min {max {h11, ..., h m11}, max { h12, ..., h m22}, ... max { h1k, ..., h mkk},}
На базе обобщенного ограничения мы строим следующие штрафные функции
P1 = ,
где A - константа штрафа.
P2 = ,
где A , b- константы.
P3 = ,
где A , a, b- константы, t - номер поколения.
В отличие от первых двух штрафных функций, P3 – динамическая функция штрафа. При ее использовании величина штрафа недопустимого решения будет изменяться от поколения к поколению.

К началу документа

Тестовые примеры

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

Тестовая задача №1.

Эта задачи направлена на поиск максимума функции F1(x1, x2) = x1 + x2.
Пространство поиска ограничено параллелепипедом D = {0 < x1 < 3, 0 < x2 < 4}.
Область допустимых решений описывается двумя ограничениями:
g1(x) = x2 - 4x14 + 32x13 - 88x12 + 96x1 - 36 < 0,
g2(x) = x2 - 2x14 + 8x13 - 8x12 - 2 < 0.
Задача имеет два нелинейных ограничения, функция F1– линейная. Оба ограничения активны в глобальном оптимуме.
Глобальный оптимум в точке: X*(2.3295, 3.1787).
Значение критерия: F1* = 5.5079.
Параллелепипед пространства поиска задачи 1 изображен на рисунках 1.1-1.3. Темным цветом выделена допустимая область, состоящая из двух невыпуклых компонент связности. Единственное глобальное решение отмечено кружочком.

Тестовая задача №2.

Вторая задача состоит в отыскании максимального значения функции F2(x1, x2) = x2, при условии, что выполняются два ограничения:
g1(x) = x2 - 4x14 + 32x13 - ax12 - bx1 - с < 0,
g2(x) = x2 - 2x14 + 8x13 - 8x12 - 2 < 0,
где
a = (16*(2+V7)3 -(2+V7)4 -168*(2+V7)+153)/((2+V7)2- 4*(2+V7)+3), /V-означает квадратный корень/
b = 84 - 2a,
с = (55 - 2a - 4b)/8.
На области D = {0 < x1 < 3, 0 < x2 < 4}.
Задача имеет три глобальных решения в точках:
X1* = (0.5, 3.125),
X2* = (1.5, 3.125),
X3* = (2.32287, 3.125).
Все три решения находятся на границе допустимой области.
Задача имеет два нелинейных ограничения, функция F2–линейная. Оба ограничения активны в глобальном оптимуме.
Максимальное значение критерия: F2* = 3.125.
Параллелепипед пространства поиска задачи 2 изображен на рисунках 2.1-2.3. Темным цветом выделена допустимая область, состоящая из двух невыпуклых компонент связности. Задача имеет три оптимальных решения, причем два из них принадлежат одной компоненте связности, а третье – второй компоненте (решения задачи на рисунке отмечены кружочками).

Тестовая задача №3.

Третья задача [4]: F3(x1, x2) = x1 + x2 --- max, при условии выполнения одного из трех ограничений:
g1(x) = (x1 - 5)2 + (x2 - 5)2 - 1 < 0
или
g2(x) = (x1 - 3)2 + (x2 - 5)2 - 4 < 0
или
g3(x) = (x1 - 5)2 + (x2 - 3)2 - 4 < 0
На области D = {0 < x1 < 7, 0 < x2 < 7}
Глобальный оптимум достигается в точке: X*(5.7071, 5.7071).
Максимальное значение критерия: F3* = 11.4142.
В отличие от двух предыдущих задач, требующих обязательного выполнения всех ограничений, здесь условия сформулированы иначе. Решение задачи может удовлетворять только одному из трех ограничений. Такой постановка достаточно часто встречаются в реальных задачах проектирования.
Параллелепипед пространства поиска задачи 3 изображен на рисунках 3.1-3.3. Темным цветом выделена допустимая область. Задача имеет одно оптимальное решения, которое удовлетворяет одному ограничений (решение задачи на рисунке отмечено кружочком).

Тестовая задача №4.

Четвертая задача [4] заключается в поиске максимального значения функции F4(x1, x2) = x1 + x2,
при условии, что:
g1(x) = x1-1 < 0 и g2(x) = x2-7 < 0
или
g3(x) = x1-3 < 0 и g4(x) = x2-6 < 0
или
g5(x) = x1-4 < 0 и g6(x) = x2-4 < 0
или
g7(x) = x1-6 < 0 и g8(x) = x2-3 < 0
на области D = {0 < x1 < 7, 0 < x2 < 7}.
Задача имеет два глобальных оптимума в точках:
X1* = (3, 6), X2* = (6, 3).
Максимальное значение критерия: F4* = 9.00.
Как и в задаче 3 выполнение всех ограничений в оптимальной точке невозможно. Достаточно того, чтобы выполнилась одна из четырех пар ограничений: {g1(x) и g2(x)} или {g3(x) и g4(x)} или {g5(x) и g6(x)} или {g7(x) и g8(x)}.
Параллелепипед пространства поиска задачи 4 изображен на рисунках 4.1-4.3. Темным цветом выделена допустимая область. Задача имеет два оптимальных решения (решения задачи на рисунке отмечены кружочками).

К началу документа

Результаты эксперимента

 При проведении вычислительного эксперимента мы пользовались ГА со следующими параметрами


Поведение ГА можно наглядно продемонстрировать на примерах от двух переменных. На двумерной области можно легко проследить динамику сходимости особей популяции. На рисунках 1.1-1.3 изображена популяция особей (точками) задачи 1 на 1-ом, 5-ом и 10-ом поколениях.

Поколение 1

Поколение 5

Поколение 10

рис 1.1

рис 1.2

рис 1.3

Генетический алгоритм достаточно стабильно функционирует даже на невыпуклых и многосвязных областях. Применение штрафных функций довольно быстро исключает из популяции почти все недопустимые особи. Однако исключать все недопустимые решения из популяции, видимо, не следует. Иными словами, константа штрафа А не должна быть слишком большой. Эффективность поиска повышается при приближении к решению с двух сторон, когда к качестве родителей выступают как допустимые, так и недопустимые особи. Генетический кроссовер, специфика которого состоит в наследовании потомками характеристик родителей, позволяет в этом случае генерировать новые особи максимально близко к границе с недопустимой областью. В связи с этим константа штрафной функции А выбиралась таким образом, чтобы в процессе эволюции в популяции оставались несколько недопустимых особей.
Генетические алгоритмы, построенные на пропорциональном, ранговом или ином вероятностном отборе, не обладают достаточно быстрой сходимостью. Зачастую это приводит к тому, что на поиск оптимального решения затрачиваются большие вычислительные ресурсы. Предлагаемая нами символьная модель, допускающая существование множества особей с различными фенотипами, но с одинаковыми генотипами в сочетании со сравнительно короткими хромосомными наборами, позволяет использовать более жесткие отборы при формировании популяции следующего поколения. В своих экспериментах мы обычно используем отбор вытеснением. Применение этого отбора гарантирует “выживание” лучших представителей различных генотипов, поддерживая при этом на достаточном уровне генетическое разнообразие популяции. Бикритериальность такого отбора позволяет локализовать несколько решений многоэкстремальных задач. На рисунках 2.1- 2.3 представлены популяции особей задачи 2 (с тремя экстремумами) на 1-ом, 5-ом и 10-ом поколениях. Из рисунков видно, что применение соответствующего оператора достаточно равномерно распределяет особей по всем трем решениям, причем вне зависимости от того, принадлежат ли они одной компоненте связности, или нет.

Поколение 1

Поколение 5

Поколение 10

рис 2.1

рис 2.2

рис 2.3

Аналогичным образом можно продемонстрировать поведение генетического алгоритма при поиске в задачах с составными допустимыми областями (задача 3 и 4 – рисунки 3.1-3.3 и 4.1-4.3 соответственно).

Поколение 1

Поколение 5

Поколение 10

рис 3.1

рис 3.2

рис 3.3

рис 4.1

рис 4.2

рис 4.3

Применяемое обобщенное ограничение G(X), позволяет унифицировать процедуру поиска для достаточно широкого класса задач, при этом не теряется способность алгоритма локализовать несколько глобальных решений (рис. 4.1 - 4.3), принадлежащих различным элементарным допустимым областям, объединение которых и составляет допустимую область задачи.

К началу документа

Литература
  1. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация В САПР. Воронеж, ВГТУ. 1997.
  2. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов / Межвуз. сб.“Высокие технологии в технике, медицине и образовании” Часть 3; Воронеж, ВГТУ. 1997.
  3. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.
  4. Батищев Д.И. Методы оптимального проектирования. М: Радио и связь, 1984.
  5. Батищев Д.И., Исаев С.А., Ремер Е.К. Решение задач нелинейного программирования с помощью генетических алгоритмов. /Тез.докл. на Всеросс. совещании-семинаре “Высокие информационные технологии в региональной информатике” Часть 1: Воронеж, ВГТУ. 1998.



Нижегородский государственный университет им.Лобачевского

Исаев Сергей
e-mail: saisa@mail.ru
web: http://saisa.chat.ru