Большая коллекция рефератов

Счетчики

Опросы

Оцените наш сайт?

	Хорошо
	Отлично
	Полезно было посетить
	Добавил в закладки
	Еще зайду не раз
	Теперь я здесь постоянный

Генетические алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

,; ,

(1.1)

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

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

1) “предпочтительнее” тогда и только тогда, когда Q()<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. Краткая теория

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

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