Принципы построения и технология работы пакета оптимизационных программ

1. Технология работы

Рассматривается два комплекса оптимизационных программ. Один, наряду со случайно- генетической оптимизацией, содержит и комплекс программ классической численной оптимизации. Назовем его "диалоговая система оптимизации" или сокращенно ДИСО. Другой содержит различные модификации генетической оптимизации - ГЕНЕТИКА.

Оба комплекса реализованы в среде Developer Studio на языке Compag Visual Fortran 6.5 с дополнением Visual С++ (примеры построения данных систем представлены на рис.1, рис.2 в виде типовых проектов).

Рисунок 1 - Проект "ГЕНЕТИКА" - корневой модуль, модуль PROG_H - содержит ограничения-неравенства, модуль PROG_K - вычисление целевой функции. Папка Sourse Files содержит 5 модулей генетической оптимизации.

Рисунок 1 - Проект "ДИСО" включает: GEN_begin_NEPR_ZEL - корневой модуль, модуль PROG_H - содержит ограничения-неравенства, модуль PROG_K - вычисление целевой функции. Модули Qodbbd, Qodsbs, Qroblr используются для ввода дополнительной информации, структурной коррекцией модели (в случае необходимости), фиксации ограничений-равенств соответственно. Папка Sourse Files содержит 57 модулей классической и генетической оптимизации.

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

Функция HELIX имеет следующий вид:

-50<xi<50, i=1,3

Оптимальное значение:

После подготовки модели нажимается кнопка "выполнить программу" и выполняется компиляция, сборка (редактирование) системы и расчет. В определенной папке создается EXE-файл (именно EXE-файлы используются в дальнейшем для демонстрации). В ДИСО предусмотрен диалог, где вводится управляющая информация. Вход в систему единый и перепрограммирование при переходе от метода к методу не требуется. Так как методы классической оптимизации не предмет данного исследования, то специфика работы ДИСО не рассматривается !

В "ГЕНЕТИКЕ" управляющая информация задается в исходном программном коде, где даются необходимые пояснения. После подготовки модели нажимается кнопка "выполнить программу", строится EXE-файл и выполняется расчет с визуализацией основных параметров в реальном режиме времени на экране дисплея. При этом для просмотра текущего состояния нажимается клавиша "пробел", для продолжения расчета - клавиша "ENTER". Останов выполняется в любой момент при нажатии клавиши "единица". Необходимая информация, согласно заданной управляющей информации, формируется в специальных файлах, которые сразу обнаруживают себя в поддиректории, откуда запускался EXE-файл.

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

2. Управляющая и выходная информация системы

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

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

2.1. Параметры, идентифицирующие структуру оптимизационной модели

L - количество ограничений 2-го рода (функциональные ограничения)

NIC - общее количество ограничений

NX - количество оптимизируемых переменных (хромосом)

NMK5 - MIN(MAX) направление оптимизации (развития)

ParamMin - массив минимальных значений оптимизируемых переменных (ограничения 1-го рода)

ParamMax - массив максимальных значений оптимизируемых переменных (ограничения 1-го рода)

2.2. Управляющие параметры случайно-генетической оптимизаци

1. i_mutaz - режим мутации:

- каждый бит инвертируется с вероятностью (1-p0_mutaz)
- инвертируются совпадающие родительские хромосомы(координаты) с вероятностью (1-p0_mutaz)
- мутация отсутствует

2. N_pop - объем буфера "разгона" для размещения исходной популяции

3. N_pop1 - объемы последующих популяций (массивов)

4. i0 - число итераций (популяций, шагов оптимизации)

5. Nmax_pop - максимальное число проб модели для ПОЛНОЙ подготовки исходного массива подходящими особями (удовлетворяют ограничениям задачи)

6. i_ZEL - индикатор структуры модели, убирает не нужное обращение к целевой функции (модели), если это допустимо

1 - если целевую функцию и ограничения НЕОБХОДИМО считать в одной модели

0 - если ограничения МОЖНО считать отдельно от целевой функции (это желательно, так как скорость вычислений будет выше)

7. p0 - барьер наполнения координат от лучшего решения при скрещивании

8. p0_mutaz - барьер, превышение барьера приводит к мутации хромосомы (координаты), малое значение приближает к чисто случайному поиску и противоречит сохранению наследственности ПО-ДРУГОМУ! Мутация (превышение барьера) соответствует оптимизации, нарушению наследственности, высокий барьер способствует сохранению наследственности генов родителей

9. p0_x - двухуровневый барьер, превышение барьера приводит к случайному выбросу координаты в МАКСИМАЛЬНОМ диапазоне, не достижение - к случайному выбросу координаты в диапазоне изменения координат ТЕКУЩЕЙ популяции (противоречит глобальности оптимума, соответствует локальной оптимизации, целесообразность достигается вблизи оптимума)

p0_x=p0_x_1 первый высокий барьер

p0_x=p0_x_2 второй более низкий барьер

10. N_mass - размер массива памяти управления сходимостью в конце поиска, является сложной динамической характеристикой размера пространства поиска последних N_mass поколений генетической оптимизации (индикатор области поиска), влияет на реализацию стратегии мутации

11. eps0 - в массив памяти сходимости в конце поиска попадают только элементы БОЛЬШИЕ eps0

12. eps1 - второй уровень подключения, увереннее включает случайный поиск по ВСЕЙ очередной координате при наступлении события "сходимость на локальном экстремуме"

13. eps_y - не различимость по цели; с другой стороны, превышение этого барьера препятствует смене другого барьера при мутации и переходе на глобальность поиска по обрабатываемой координате (если задать очень малое значение, то глобальность отрабатывается хуже; большое значение способствует усилению глобальности; эта процедура имеет значение только в конце поиска). Работает ТОЛЬКО в режиме i_mutaz=2. Принципиальной роли этот параметр не оказывает!

14. iT - количество решений (особей) для выбора среди них лучшей при наполнении промежуточного массива (большое значение iT преждевременно усиливает сходимость поиска)

При решении конкретной задачи приходится манипулировать параметрами 1-8. Наиболее сильное влияние оказывает 7 и 8 параметр.

2.3. Параметры управления выходной информацией

1. i_SHAG_pech - шаг печати генерируемых особей при создании исходной популяции, необходимо для контроля прохождения области поиска

2. i_pech_FORMA - управление формой печати:

1 - в формате исходной информации входных переменных,

2 - в нормированном формате входных переменных (диапазоне 0-1)

3. i_otl - управление общим отладочным режимом (1-включено, 2-отключено)

4. i_otl_2 - управление дополнительным отладочным режимом на экран

5. i_otl_3 - управление дополнительным отладочным режимом в отладочные файлы

6. i_DATCHIC - управление подключением случайных датчиков

7. LPR - управление обращением к модели в оптимальной точке (для реализации возможности вывода дополнительной информации вне оптимизации)

2.4. Выходная информация случайно-генетической оптимизации

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

1 итерация значение целевой функции - 26.3165065083374

значение параметра области сходимости - 9.341728687286377E-002

2 итерация значение целевой функции - 26.3165065083374

значение параметра области сходимости - 7.838803606001932E-002

……………………………………………………

63 итерация значение целевой функции - 1.548105043405858E-006

значение параметра области сходимости - 1.488544131446797E-005

……………………………………………………

100 итерация значение целевой функции - 8.409909703025464E-012

значение параметра области сходимости - 3.964156932341941E-008

……………………………………………………

218 итерация значение целевой функции - 1.044228777457883E-027

значение параметра области сходимости - 2.775557561562891E-016

219 итерация значение целевой функции - 0.000000000000000E+000

значение параметра области сходимости - 3.700743415417188E-017

……………………………………………………

228 итерация значение целевой функции - 0.000000000000000E+000

значение параметра области сходимости - 0.000000000000000E+000

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

В зависимости от параметров управления выходной информацией в поддиректории, содержащей EXE-файл, образуются от 2х до 5ти текстовых файлов, которые дают подробную информацию о ходе поиска. Обязательными являются файлы z_ЦЕЛЬ 4(21).txt , z_РАЗГОН 0(17).txt, которые являются точной копией экрана. Вспомогательные файлы содержат подробную информацию о скрещиваемых особях по итерациям (все от лучшей до худшей) с фиксацией координат (хромосом) - это файл z_РЕЗУЛ_итер 3(20).txt. Файлы z_ПРОМЕЖ_до 1(18).txt и z_ПРОМЕЖ_после 2(19).txt содержат исходную информацию о материале, используемом для скрещивания особей и получения нового поколения по итерациям.

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