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

Исаев С.А. (contact@galgorithms.com)

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

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

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

/= f(x1, x2, — *N )= ( min ) f(xu x2,••• xn ), где X* G S n D(1)

X=(х1,x2,„.xn)) D

D = {х = (х1, x2,...xn ) at < xt < bt, 1 < i < N} - пространство поиска;(2)

S = {x = (x1, x2,...xn ) gj (X) < 0, j = 1,2, •.., к} - допустимое множество. (3)

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

из нескольких компонент связности.

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

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

F* = F(x1,x2*x*N) = min ) F(x^x2,...xN), где X" e D(4)

X=(x1,x2,...xN)e D

F (X ) = f (X )+^( X) - новая целевая функция

Г= 0, X e D n 5 X) = i- функция штрафа

^V \> 0, X e D \5 ^F *

Для решения задачи (4) был разработан и реализован генетический алгоритм [1], [2], [3], в основу которого положены основные механизмы, моделирующие основные элементы эволюции в Природе:

1генерация начальной популяции решений,

2воспроизводство решений-«потомков»:

2.1выбор родительской пары,

2.2выбор и реализация одного из операторов кроссовера,

2.3выбор и реализация одного из операторов мутации,

3создание репродукционной группы,

4процедура отбора и формирование на его основе нового поколения,

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

недопустимых особей, т. е. особей, фенотипические признаки которых не удовлетворяют заданным ограничениям. Будем говорить, что фенотипические признаки особи не удовлетворяют заданным ограничениям, если найдется такой номер j, что g j (X) > 0 .

В качестве функций штрафа в работе были использованы две хорошо известные [4] свертки цг1 (X) = A о max max {0, gj (X)},

j=1,2,...£ k

Wl{ X) = A о £ max {0, g} (X)}

j=1

В обоих свертках A - коэффициент функции штрафа. В большинстве случаев,

как правило, это константа, величина которой задается перед началом поиска и не изменяется в процессе решения задачи. Обычно, значение этой константы определяется на основе предварительных исследований или экспертных оценок.

Для проведения вычислительного эксперимента были выбраны следующие тестовые примеры [5]:

№ f (X)= 5 £хг -5 £x2 -£хг ,

i=1i=1i=1

xt e[0,1] i = 1,2,...9,13; xi e [0,100] i = 10,11,12

g1/ (X) = 2x1 + 2x2 + x10 + x11 -10 < 0;

g2 (X) = 2x1 + 2x3 + x10 + x12 -10 < 0; g3 (X) = 2x2 + 2 x3 + x11 + x12 -10 < 0;

Задача имеет 9 линейных ограничений; функция f1 (X) - квадратичная с глобальным минимумом в X2 = (1,1,1,1,1,1,1,1,1, 3, 3, 3,1),

где f1 (х2)=-19. Шесть (из девяти) ограничений активны в глобальном оптимуме, все, за исключением g4 (X), g5 (X) и g 6 (X).

№2 f1 (X) = x + x2 + x3 x1 e [100,10000];

xi e 1000, 10000]i = 2, 3 ;

xi e [10,1000] i = 4, 5, 6, 7, 8 g1 (X) = 0.0025 (x4 + x6)-1 < 0; g21 (X) = 0.0025 (x5 + x7 - x4)-1 < 0 ; g331 (X) = 0.01 (xi -x5)-1 < 0;

g41 (X) = - x1 x6 + 833.33252 x4 + 100 x1 - 83333.33 < 0; g51 (X) = - x2 x7 + 1250 x5 + x2 x4 -1250 x4 < 0; g61 (X) = - x3 x8 + 1250000 + x3 x5 - 2500 x5 < 0 .

Эта задача имеет 3 линейные и 3 нелинейные ограничения; функция f11 (X) линейная и имеет глобальное решение в точке

X2 = (579.31,1359.94, 5110.07, 182.01, 295.59, 217.97, 286.41, 395.59),

где f11 (х 2)= 7049.33. Все шесть ограничений активны в глобальном

оптимуме.

№3 f111 (х)= (x1 -10)2 + 5 (x2 -12)2 + x34 + 3 (x4 -11)2 + + 10x56 + 7x2 + x4 - 4x6x7 -10x6 - 8x7 xi e[-10,10] i = 1, 2,...7 g11 (X) = 2x2 + 3x24 + x3 + 4x42 + 5x5 -127 < 0 ; g211 (X) = 7x1 + 3x2 +10x32 + x4 - x5 - 282 < 0 ; g311 (X) = 23x1 + x2 + 6x62 - 8x7 -196 < 0; g411 (X) = 4x2 + x22 - 3x1 x2 + 2x32 + 5x6 - 11x7 < 0;