Только лучшие рефераты рунета    
 
 

Партнеры:



 
 






1.  Краткая теория

1.1  Математическая формулировка экстремальной задачи однокритериального выбора

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

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

·   — внешние параметры, характеризующие внешнюю по отношению к объекту среду и оказывающие влияние на его функционирование;

·   — внутренние параметры, характеризующие свойства отдельных элементов объекта.

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

Объединенную совокупность внешних и внутренних параметров будем называть множеством входных параметров.

Величины, характеризующие свойства объекта в целом как системы, будем называть выходными параметрами (характеристиками), которые можно только измерять или вычислять, но непосредственно изменять нельзя. Обозначим их вектором .

Управляемые переменные  и характеристики  определяют существенные свойства исследуемого объекта, а внешние параметры  являются, как правило, константами и характеризуют внешнюю среду. При этом внутренние параметры  играют роль независимых переменных, а выходные параметры  являются зависящими от них величинами. Будем считать, что соотношения, выражающие эти зависимости, заданы в виде “черного ящика”, который имеет n входов xi,

 и sвыходов i,.

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

,; ,

(1.1)

где  -нижнее и верхнее предельно-допустимые значения, соответственно, для i-ой переменной и j-ой характеристики. Область управляемых переменных, в которой выполняется система ограничений (1.1), будем называть областью поиска D, а любой вектор, принадлежащий множеству D - допустимым решением.

Для выбора из области поиска D одного или нескольких “лучших” допустимых решений часто приходится вводить критерий оптимальности Q - количественный показатель, посредством которого осуществляется объективное измерение в некоторой числовой шкале Y какого-либо одного наиболее важного для задачи принятия решения выходного параметра ji. Здесь под измерением по шкале Y понимается отображение Q, которое каждому решению  ставит в соответствие числовую оценку    таким образом, чтобы отношения между числами сохраняли бинарные отношения предпочтения между решениями:

1)   “предпочтительнее”  тогда и только тогда, когда Q());

2)    “не менее предпочтительнее”   тогда и только тогда, когда Q()  Q();

3)   “эквивалентно”   тогда и только тогда, когда Q() = Q().

 

 

(1.2)

Из соотношений (1.2) следует, что механизм выбора “лучшего” решения сводится к отбору тех и только тех решений, которые доставляют наименьшее значение критерию оптимальности Q в области поиска D :

,

(1.3)

где - оптимальное решение;  - наименьшее значение критерия оптимальности, получаемое при принятии оптимального решения .

Выражение (1.3)является математической записью модели принятия оптимального решения, называемой экстремальной задачей однокритериального выбора. В том случае, когда решение задачи (1.3) можно свести к анализу значений критерия оптимальности Q для конечного числа решений  (например, заданных числом перестановок n!, числом сочетаний  или просто дискретным множеством допустимых вариантов) экстремальная задача однокритериального выбора относится к классу экстремальных задач переборного типа [1].

1.2  Понятие “оптимальное решение”

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

 для всех .

(1.4)

В случае унимодальной функции (одно-экстремальной функции, которая может быть разрывной, не дифференцируемой и т.д.) оптимальное решение задачи (1.3) является единственным и достигается в точке локального минимума :

для всех ,

(1.5)

где  - e -окрестность точки локального минимума .

В случае многоэкстремальной функции (функции , имеющей несколько локальных минимумов  в области поиска D) оптимальное решение задачи (1.3) является глобальным минимумом - наименьшим из всех локальных минимумов:

,

(1.6)

где   - к-ый локальный минимум функции ;

l - число локальных минимумов в области поиска D.

В общем случае оптимальное решение задачи (1.3) может достигаться на некотором подмножестве допустимых решений WÍ D, удовлетворяющих условию:

=Q* для всех .

(1.7)

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

1.3  Задача синтеза стабилизатора напряжения как экстремальная задача переборного типа

Пусть имеется 4 некоторых множеств X, Y, Z, W функциональных элементов, реализующих различные части схемы стабилизаторов напряжения, Х={х1, х2, ... , хm}, Y={y1, y2, ... , yn}, Z={z1, z2, ... , zo}, W={w1, w2, ... , wp} (банк схемотехнических решений).

Пусть каждый элемент содержит 4 характеристики, закодированные двоичным кодом:

1.Влияние на петлевое усиление (1 - хорошее, 0 - плохое);

2.Влияние на КСТ.ИОН. (1 - хорошее, 0 - плохое);

3.Мощность множества узлов (1 - большая, 0 - малая);

4.Мощность множества связей (1 - большая, 0 - малая);

1.8

Стабилизатором напряжения (Х1, Y2, Z3, W4) будем называть регулярную структуру (1.8), в которой элементы x, y, z и w описывают источник опорного напряжения, сравнивающее устройство, регулирующий элемент, датчик соответственно.

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

Тогда оптимальный стабилизатор является оптимальным решением (Х1, Y2, Z3, W4) следующей экстремальной задачи однокритериального выбора:

,

(1.12)

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

Задача 1.12 относится к экстремальным задачам переборного типа, т.к. общее число допустимых решений равно произведению количества элементов множеств X, Y, Z, W.

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

2.  СИМВОЛЬНАЯ МОДЕЛЬ И ИНТЕРПРЕТАЦИЯ ЕЕ ЭЛЕМЕНТОВ В ТЕРМИНАХ ПОПУЛЯЦИОННОЙ ГЕНЕТИКИ

2.1  Представление допустимых решений экстремальной задачи в виде бинарных строк

Допустимое решение   экстремальной задачи однокритериального выбора (1.3) является n-мерным вектором  . В том случае, когда задача (1.3) принадлежит классу задач переборного типа, имеется конечное множество допустимых решений, в которых каждая компонента  вектора  может быть закодирована с помощью целого неотрицательного числа:

(2.1)

где (Ki+1)- число возможных дискретных значений i-ой управляемой переменной в области поиска D. Это позволяет поставить во взаимно однозначное соответствие каждому вектору  вектор   с целочисленными компонентами:

(x1, ..., xn)«(b1,..., bn),

(2.2)

где для каждой компонентыbi, областью возможных значений являются целые числа от 0 до Кi .

Введем алфавит В2, содержащий только два символа 0 и 1: В2={0,1}. Для того, чтобы представить целочисленный вектор =(b1,...,bn) в алфавите В2 необходимо определить максимальное число двоичных символов q, которое достаточно для представления в двоичном коде любого значения bi из области его допустимых значений [0,Ki]. Нетрудно видеть, что параметр символьной модели q должен удовлетворять неравенству:

Кq,

(2.3)

где  .

Запись произвольного целого неотрицательного числа  с помощью q двоичных символов определяется соотношением :

,

(2.4)

где al-двоичное число, равное 0 или 1;

q-длина двоичного слова, кодирующего целое число bi .

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

еq(bi):

a1

a2

...

aq

 

(2.5)

 

¬¾¾¾  q  ¾¾¾®

 

 

где al ,  - двоичные символы (0 или 1), полученные из соотношения (2.4).

Пример 2.1.

Пусть  q=5 и bi=19. Тогда согласно соотношения (2.4) можем записать: 1910 = 1´24 + 0´23 + 0´22 + 1´21 + 1´20 = 100112 , т.е., бинарная комбинация е5(19)целого числа 19 в алфавите В2 будет иметь вид: 10011.

Для представления допустимого решения   экстремальной задачи (1.3) в алфавите В2 объединим символьные записи еq(bi), описывающие все n компонент вектора  , в виде линейной последовательности из бинарных комбинаций (2.5):

(2.6)

Записи (2.6) соответствует (n´q)-битовая строка из двоичных символов (0,1):

eq(b1)

eq(b2)

 

eq(bn)

 

 

...

...

...

...

 

(2.7)

n´q

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Представим дихотомическое разбиение (X1,X2) графа G(X,V,W) порядка n в виде бинарной строки E (X1,X2), состоящей из n бит, расположенных в порядке возрастания их номеров. Каждому номеру бита поставим в взаимнооднозначное соответствие номер вершины графа (1-ый бит соответствует вершине x1, 2-ой бит - вершине x2, ... , n-ый бит - вершине xn). Потребуем, чтобы бинарное значение al

1-ого бита указывало, какому подмножеству вершин (X1 или X2) принадлежит вершина xl :

 

1, если l-ая вершина xlÎX входит в состав подмножества вершин X1;

 

al =

 

 

(2.8)

 

0, если l-ая вершина xlÎX входит в состав подмножества вершин X2

 

При этом каждая бинарная строка E(X1,X2) должна удовлетворять дополнительному требованию, связанному с сутью дихотомического разбиения: “число битов, содержащих “1” в бинарной строке E (X1,X2), должно равняться мощности подмножества вершин подграфа G1(X1,V1,W1), равной порядку этого подграфа n1”.

Так, разбиения (X1,X2) и , приведенные в Таблице 1.1., имеют следующие представления в виде бинарных строк:

E(X1,X2):

1

0

0

0

0

0

1

1

0

1

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E(X1*,X2*):

0

1

1

1

1

1

0

0

0

0

0

0

 

 

1

2

3

4

5

6

7

8

9

10

11

12

-номер бита

 

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

-номер

 вершины

Сравнивая построенную символьную модель экстремальной задачи (1.12) с общей символьной моделью (2.7), видим, что допустимый вектор  включает в качестве компонент все вершины графа G, каждой из которых соответствует целое число bi, принимающее только два значения 0 или 1 (т.е. Кi =1 для всех ).

Это приводит к тому, что бинарная комбинация еq(bi) состоит из единственного бита, т.к. неравенство (2.3) выполняется при q=1. Однако, линейная последовательность (2.6) принимается в качестве бинарной строки , соответствующей допустимому разбиению (X1,X2), только в том случае, если число “1” в ней равно порядку n1 графа G1.

2.2  Особи и их вариабиальные признаки

Наименьшей неделимой единицей биологического вида, подверженной действию факторов эволюции, является особь  (индекс k обозначает номер особи, а индекс t - некоторый момент времени эволюционного процесса). В качестве аналога особи  в экстремальной задаче однокритериального выбора (1.3) примем произвольное допустимое решение , которому присвоено имя . Действительно, вектор управляемых переменных (x1, ..., xn) - это наименьшая неделимая единица, характеризующая в экстремальной задаче (1.3) внутренние параметры на каждом t-ом шаге поиска оптимального решения, которые изменяют свои значения в процессе минимизации критерия оптимальности  Q().

В задаче оптимального дихотомического разбиения (1.12) в качестве особи  выступает конкретное дихотомическое разбиение (X1,X2), удовлетворяющее условиям (1.8) - (1.9), что позволяет интерпретировать сам процесс решения экстремальной задачи (1.12) как эволюционный процесс, связанный с перераспределением вершин xiÎX графа G по двум подграфам G1 и G2, соответственно, порядка n1 и n2, с целью отыскания глобального минимума критерия оптимальности (1.11). В этом и заключается в данном случае цель эволюционного развития (эволюции) особей.

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

·  качественные признаки- признаки, которые позволяют однозначно разделять совокупность особей на четко различимые группы;

·  количественные признаки - признаки, проявляющие непрерывную изменчивость, в связи с чем степень их выраженности можно охарактеризовать числом.

Качественные признаки особи  определяются из символьной модели экстремальной задачи (1.3) как соответствующая точке  с именем  бинарная строка E() и составляющие ее бинарные комбинации eq(b1), ..., eq(bn).

Приведем интерпретацию этих признаков в терминах хромосомной теории наследственности [4].

В качестве гена - единицы наследственного материала, ответственного за формирование альтернативных признаков особи, примем бинарную комбинацию eq(bi) из (2.5), которая определяет фиксированное значение целочисленного кода bi управляемой переменной xi в обычном двоичном коде. Одна особь  будет характеризоваться n генами, каждый из которых отвечает за формирование целочисленного кода соответствующей управляемой переменной. Тогда структуру бинарной строки E() из (2.7) можно интерпретировать хромосомой, содержащей n сцепленных между собой генов, которые расположены в линейной последовательности “слева - направо”. Согласно хромосомной теории наследственности передача качественных признаков eq(bi), , закодированных в генах, будет осуществляться через хромосомы от “родителей” к “потомкам”.

 

Следующая страница



 
     
 

2021 © Copyright, Abcreferats.ru
E-mail:

 

Яндекс.Метрика