Выбор независимых переменных 7 страница. Например, для оптимизируемой функции подпрограмма М3 имеет вид:

Например, для оптимизируемой функции подпрограмма М3 имеет вид:

SUBROUTINE M3

COMMON/A2/X(150),Q

COMMON/H2/N

Q1=0.

DO 263 I=1,N

a. Q1=Q1+(X(I)-I)**2

Q=Q1

RETURN

END

– модуль реализует алгоритм случайного поиска (Растригин - Рипа)

Для обмена данными с вызывающими и вызываемыми модулями в М211А содержатся следующие операторы:

COMMON/A2/ X(150),Q

COMMON/B211/ JCN, JCP, EPSD, EPSQ, DX, DXMIN, G1, G2, K1, R8

COMMON/C2/ X0(50), DEX (50)

COMMON/D2/ BX(50), XB(50), XT(50)

COMMON/E2/ RAN(50), KEYR

COMMON/F2/ QN1, QN2, QN

COMMON/G2/ JC4, JC5, JC5

COMMMON/H2/ N

Помимо вышеописанных операторы содержат следующие переменные:

QN1, QN2 – текущие значения критерия качества;

X0(50) – координаты начальной точки ;

RAN(50) – массив случайных чисел, распределённых по равномерному закону в интервале [-1, 1] в модуле М28;

KEYR – ключ, задающий вариант формирования RAN(50);

BX(50), XB(50) – текущие значения независимых переменных.

Используемые подпрограммы:

М3, М721, M722, M28, M25, M29, M24

Аналогичные операторы содержатся и в других модулях пакета, реализующих те или иные алгоритмы оптимизации.

4.6 Состав библиотеки методов оптимизации

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

1) Прямые методы случайного поиска, которые используют только значения функции ;

2) Градиентные методы первого порядка, которые используют значение функции и ее производных;

3) квазиньютоновские методы;

4) Овражные методы поиска;

5) Методы поиска глобального экстремума.

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

Где - псевдослучайное число, равномерно распределенное в интервале (-1; 1);

j-1, j – номера этапов поиска.

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

Состав библиотеки методов оптимизации

Таблица 4.1

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

1) Методы нулевого порядка;

2) Методы первого порядка;

3) Методы второго порядка;

4) Методы случайного поиска;

Для того, чтобы воспользоваться этими программами, пользователю необходимо составить подпрограмму вычисления значений и, при необходимости ее производных (в случае использования методов первого и второго порядков).

Перечень стандартных программ оптимизации

Таблица 4.2

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

SUBROUTINE M27 (N, XG, QG, SG)

где XG – массив текущих значений аргументов оптимизируемой функции;

QG – текущее значение оптимизируемой функции;

SG – массив текущих значений градиента функции;

Подпрограмма M27 имеет вид:

SUBROUTINE M27 (N, XG, QG, SG)

COMMON/A2/X(150), Q

COMMON/B219/NNG, DLX(50)

COMMON/B27/K271, K272

REAL K271, K272

DIMENSION SG(N), XG(N)

DO 3 I=1, N

i. X(I)=XG(I)

CALL M3

QG=Q

12) S=0

DO 2 I=1, N

DLX(I)=K271+K272*(ABS(XG(I)))

X(I)=X(I)+DLX(I)

CALL M3

QN1=Q

SG(I)=(QN1-QG)/DLX(I)

X(I)=X(I)-DLX(I)

13) CONTINUE

RETURN

END

Точность вычисления градиента регулируется коэффициентами К271 и К272 в формуле для пробных перемещений DLX(I) в пространстве независимых переменных.

4.7 Критерии останова, аварийные ситуации,

вывод на печать результатов счёта

Критерием останова для каждой программы минимизации служит одновременное выполнение N раз подряд следующих условий:

(4.1)

(4.2)

где , , , - входные параметры

, - текущие значения независимых переменных и критерия оптимальности на k -ой итерации;

, - текущие значения независимых переменных и критерия оптимальности на (k-1) итерации;

Независимо от выполнения вышеуказанных условий, пакет программ оптимизации закончит свою работу в случае исчерпания ресурса JM2, т.е. если JC6>JM2. В этом случае IER=8, в отличие от вышеприведённых условий (4.1), (4.2), когда IER=6.

Возможны также остановы в аварийных ситуациях:

1) Начальная точка, задаваемая пользователем, лежит вне области определения. В этом случае IER=16 и печатается сообщение «Начальная точка x(I) – вне области поиска».

2) За K4 вычисления функции качества число неудачных шагов поиска JC4 превысило число удачных шагов JC2. в этом случае IER=10.

3) Количество вычислений превысило допустимое значение JCN, задаваемое пользователем. В этом случае IER=7.

При останове по любой из этих причин работа комплекса заканчивается и управление через оператор RETURN передаётся в вызывающую программу M2. Если не исчерпан ресурс по числу итераций, то начинается работа следующей процедуры оптимизации.

Вывод на печать результатов работы процедур оптимизации производится в соответствии с входными параметрами через JCP итераций. На печать выводится:

JC6, JC4, JC2 – соответственно общее число неудачных и удачных шагов поиска;

QN – значение функции качества, минимальное за JC6 шагов поиска;

XT(I) – массив текущих значений независимых переменных, соответствующих QN;

DX – текущее значение шага поиска.

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

Управление печатью можно осуществить в M7221 с использованием параметра IPR, как это, например, сделано в [8 ].

5. Примеры практического применения

алгоритмов поисковой оптимизации

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

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

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

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

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

5.1 Тестовые результаты работы программ оптимизации

В данном разделе приведён анализ тестовых проверок алгоритмов оптимизации.

В качестве тестовых использовались функции, наиболее часто встречающиеся в литературе [4, 6, 8, 16, 34].

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

Успех машинного проектирования во многом определяется выбором поискового метода. Этот выбор обуславливается природой задачи: степенью нелинейности, топологией гиперповерхностей, размерностью и т.д. Эффективность поиска в не меньшей мере зависит от «деталей» алгоритма и машинной программы.

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

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

Алгоритмы поиска должны легко реализовываться на ЭВМ, требовать минимальный объём памяти. Предварительная поисковая работа должна быть минимальной. Нас в сопоставительном анализе будет интересовать скорость и точность сходимости поиска.

Ниже в таблицах приведены результаты оптимизации тестовой функции вида различными поисковыми методами.

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

1) метод параллельных касательных;

2) метод наискорейшего спуска;

3) метод Гаусса – Зейделя;

4) метод конфигурации;

5) метод квадратичной аппроксимации.

В расчётах, результаты которых приведены ниже принимались:

1) размерность задачи n=10;

2) начальные значения независимых переменных =100;

3) начальный шаг поиска =100;

4) границы области поиска .

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

N, J – число вычислений функции качества ;

- найденное экстремальное значение функции;

- вектор оптимальных значений независимых переменных.

Результаты расчётов показали, что высокой скоростью сходимости обладает метод наискорейшего спуска. Очень низкая скорость сходимости у метода случайного поиска.

Таблица 5.1

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

Оптимизируемая функция	Число шагов	Независимые переменные
	J
–
		86,75	86,89	87,02	87,16	87,3	87,42	87,56	87,69	87,82	87,96
		70,2	70,5	70,8	71,1	71,4	71,7	72,0	72,3	72,62	72,91
		56,95	57,4	57,82	58,26	58,7	59,13	59,56	60,0	60,43	60,87
		40,4	41,0	41,6	42,2	42,8	43,42	44,01	44,61	45,21	45,81
4557,7		23,84	24,61	25,38	26,15	26,92	27,69	28,46	29,22	30,0	30,77
839,6		10,59	11,5	12,41	13,3	14,21	15,11	16,01	16,92	17,82	18,72
0,1614		0,867	1,868	2,87	3,87	4,87	5,87	6,87	7,88	8,88	9,88
0,000124		0,997	1,997	2,997	3,297	4,995	5,996	6,996	7,996	8,996	9,996

Таблица 5.2

Результаты оптимизации тестовой функции

методом случайного поиска

Оптимизи- руемая функция	Число шагов	Независимые переменные
	J
–
172,40		1,421	1,498	0,1	0,1	0,1	1,804	1,88	8,72	0,1	10,87
14,65		2,028	3,391	0,870	3,587	4,34	4,371	6,339	6,625	8,737	8,787
4,775		1,871	3,571	3,374	3,983	4,834	6,507	7,354	7,22	9,62	9,8
0,3188		1,001	1,955	3,153	3,587	5,003	5,783	6,824	7,897	8,944	10,175
0,1251		0,9672	2,013	3,036	3,741	4,884	5,965	7,095	8,071	8,873	10,103

Таблица 5.3

Результаты оптимизации тестовой функции

методом параллельных касательных

Оптимизируемая функция	Число шагов	Независимые переменные
	J
–
1486,3		13,7	14,6	15,5	16,4	17,25	18,12	18,99	19,86	20,73	21,6
19,75		2,47	3,46	4,44	5,436	6,411	7,395	8,381	9,366	10,351	11,337
0,0151		1,04	2,039	3,049	4,038	5,038	6,037	7,037	8,037	9,036	10,036
		0,997	1,997	2,997	4,007	4,997	5,997	6,997	7,997	8,997	9,997
		0,999	1,999	2,999	3,999	4,999	5,999	6,999	7,999	9,000	10,000

Таблица 5.4

Результаты оптимизации тестовой функции

методом наискорейшего спуска

Оптимизируемая функция	Число шагов	Независимые переменные
	J
–
186,5		5,52	6,47	7,43	8,38	9,34	10,29	11,24	12,2	13,2	14,1
0,0256		1,05	2,05	3,06	4,05	5,05	6,06	7,05	8,,05	9,05	10,05
		1,001	2,001	3,001	4,001	5,001	6,001	7,000	8,000	9,000	10,000

Не нашли, что искали? Воспользуйтесь поиском: