Пример минимизации с ограничениями в форме нелинейных неравенств

Генетические алгоритмы – это адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной и структурной оптимизации. Попытаемся разобраться в технологии генетических алгоритмов применительно к сложным задачам параметрической оптимизации. С этой целью рассмотрим задачу оптимального распределения ресурсов на примере оптимального проектирование боевой части (БЧ) ракеты. Оптимальное проектирование БЧ может осуществляться в два этапа: сначала оптимизируется поле поражающих элементов (ПЭ) по критерию эффективности действия, а на втором этапе создается конструкция, реализующая оптимальное распределение ПЭ по различным участкам поля. Важно, чтобы на этапе оптимизации поля учитывались существенные ограничения. В самом простом виде задачу оптимального распределения известного количества ПЭ можно записать как максимизацию полной вероятности поражения. Для этого, разделив область поля на n зон, определив вероятность p_i поражения цели одним попавшим ПЭ в i -й зоне, выразим условную вероятность поражения цели при попадании в нее x_i ПЭ в i -й зоне:

, где q_i = 1 – p_i.

Вероятности R_i нахождения цели в i -й зоне при накрытии ее полем также зависят от условий встречи. В результате находим оптимальное распределение данного количества ПЭ:

Это дискретная задача оптимизации, альтернативами которой являются последовательности целых чисел(x ₁, x ₂, … x_n), x_i Î [0, n ], ∑ x_i = N. Количество таких альтернатив (по схеме выборки с возвратом) составляет n^N. Если n имеет порядок 10, а N – тысячи, полный перебор вариантов немыслим. Необходимо найти эффективный метод выбора оптимальной альтернативы.

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

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

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

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

Механизмы рекомбинации могут быть реализованы разными способами, общим для них является наследование генов m родителей (m = 1, 2, 3, …), то есть новая хромосома так или иначе представляет популяцию. На рис. 7 показан возможный вид оператора рекомбинации (2 родителя, 2 потомка), так называемый одноточечный кроссовер: хромосомы родителей разрываются на границе двух соседних генов, а затем происходит обмен частями хромосом родителей и «склеивание» их в новые хромосомы.

Рис. 7. Возможная схема рекомбинации хромосом

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

Сформируем популяцию из L хромосом одинаковой длины M, равной числу зон поля ПЭ. Целочисленными генами хромосом являются количества ПЭ, распределяемых в i -ю зону, (считая позиции гена в хромосоме перенумерованными так же, как и зоны поля ПЭ). Популяция – массив ячеек Pop, хромосомы – элементы этого массива, их гены вначале имеют случайное значение в интервале [0, 50]:

L=30; N=50; M=4; for i=1:L Pop{i} = fix(rand(1,M)*N); end

Pop{1}

ans = 47 11 30 24

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

Goal = 'sum(R.*(1-q.^Pop{j}))'; Penalty = 'max([0,sum(Pop{j})/N-1])*0.35';

После ввода исходных данных, приспособленность первой особи популяции можно вычислить так:

R=[0.2 0.3 0.4 0.1]; p=[0.04 0.05 0.03 0.05]; q=1-p;

j=1; F=eval(Goal)-eval(Penalty)

F = 0.1764

Чтобы осуществить механизм эволюции, назначим его основные параметры. Порог стабильности – число потомков, передаваемых в следующее поколение, установим на уровне 0,2 от объема популяции. Постоянную точку разрыва хромосомы при скрещивании установим в середине гена D=M/2+1. Зададим вероятность мутации 0,6 и максимальное число поколений 60:

Elit=fix(L*0.2); D=M/2+1; Pmut=0.6; Ngen=80;

Следующий скрипт-файл осуществляет эволюцию заданного числа поколений популяции:

%GeneticA

Npop = length(Pop);

for k=1:Ngen

for j=1:Npop G(j)=eval(Goal)-eval(Penalty);end

[Y,I] = sort(G); I=I(Npop:-1:1);

PopOld = Pop; Pop={};

[Par, n] = SelPair(I,Elit);

for j=1:n

Pop{j}=CrossOver(PopOld, 3, Par(j,:));

g(j)=eval(Goal)-eval(Penalty);

end

[y,i] = sort(g);

PP=find(G(I)<g(i)); if isempty(PP) continue, end

j= PP(1);

PP=[PopOld(I(1:j)), Pop(i(j+1:Npop))];

for ii = 1:Npop if rand>Pmut PP{ii}=Mutation(PP{ii}); end; end

Pop = PP;

end

for j=1:Npop G(j)=eval(Goal);end % оценка последнего поколения

[y,i] = min(G); [Y,j] = max(G); % элементы с min и max оценками

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

function [out, k]=SelPair_(N,Elit)

n=length(N); if nargin>1 n=Elit; end

k=n*(n-1); out=zeros(n,2);

A=rand(n); A=A-diag(diag(A)-1);

[V, I] = sort(A(:));

for i=1:k

T=fix((I(i)-1)/n);

out(i,:)=[N(I(i)-T*n),N(T+1)];

end

Мутацию – случайное изменение генов хромосомы – можно осуществить суммированием хромосомы с вектором такой же длины, элементами которого являются случайные комбинации чисел 1 и –1:

function X = Mutation(X)

Rnd=ones(size(X));

Rnd(rand(size(X))>0.5)=-1;

X=X+Rnd;

X(X<0)=0;

Такая схема мутации вполне подходит для случайных изменений распределения элементов по зонам (последним оператором предусмотрено, что число элементов в зоне не сможет стать отрицательным).

Механизмы рекомбинации определяются функцией CrossOver:

function [N1, N2] = CrossOver(X,D,Prnt)

N1 = X{Prnt(1)};N2 = X{Prnt(2)};

Rnd=rand(size(N1));Ind1=find(Rnd<0.5);Ind2=find(Rnd>0.5);

N1(Ind1) = X{Prnt(2)}(Ind1);

N2(Ind1) = X{Prnt(1)}(Ind1);

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

GeneticA, x=Pop{j}, W=sum(R.*(1-q.^x))

x = 8 21 24 0 W = 0.4610

Результатом выполнения алгоритма будет оптимальное распределение ПЭ по n зонам и полная вероятность поражения W.