Software & Systems

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

Подавляющее большинство возникающих на практике оптимизационных задач может быть представлено в виде  gi(x)=0, i=1, …, m; hj(x)³0, j=1, …, k, где множество XÍÂn – область поиска глобального экстремума (допустимая область); f – целевая функция; gi – ограничения-равенства; hj – ограничения-неравенства.

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

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

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

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

Графический интерфейс был реализован с помощью кросс-платформенной библиотеки wxWid­gets. В отличие от большинства других кросс-платформенных средств разработки приложения на основе wxWidgets имеют вид, привычный для пользователей каждой конкретной платформы.

Кроме того, при разработке программной системы использовалась библиотека Boost, в частности, генераторы псевдослучайных чисел (компонент Boost.Random).

Для компиляции программной системы использовался компилятор TDM-GCC версии 4.5.0.

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

В текущей версии системы использован третий подход – загрузка функций из динамически загружаемых библиотек (DLL в операционной системе Windows). Программная система определяет бинарный интерфейс, позволяющий загружать целевые функции и функции ограничений из динамически загружаемых библиотек. Преимуществами этого подхода являются возможность использования языка программирования высокого уровня (С++, а также любого языка, к функциям которого можно обратиться из программы на С++) и библиотек для задания целевых функций и ограничений, а также высокое быстродействие (не уступающее подходу с фиксированным набором функций). К недостаткам этого подхода можно отнести более высокие требования к навыкам программирования пользователя. Этот недостаток компенсируется наличием в программной системе примера динамической библиотеки, в которую пользователь может добавлять свои функции.

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

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

Второй подход заключается в использовании эволюционных алгоритмов с самонастройкой параметров: пользователь выбирает только метод оптимизации, а значения параметров подбираются программной системой в процессе решения задачи оптимизации. При использовании такого подхода успех решения задачи оптимизации зависит от квалификации пользователя в значительно меньшей степени, но, тем не менее, вопрос выбора метода оптимизации остается открытым. В данном контексте отметим, что коллективом авторов (В.Б. Звонков, Е.С. Семёнкин, С.Н. Ефимов) создана система IT-SAGA (Intelligent Technologies – Self-Adapting Genetic Algorithm) и зарегистрирована в реестре программ для ЭВМ в Роспатенте, № госрегистрации 2011611120 от 3.02.2011.

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

Для упрощения работы с программной системой настройки методов оптимизации сохраняются между запусками программы в реестре (для системы Microsoft Windows) или в файле конфигурации (для системы GNU/Linux).

Программная система включает приложение для просмотра отчетов о результатах решения задачи оптимизации, которое может использоваться независимо от основного приложения системы GOLEM-SA.

Рассмотрим методы глобальной оптимизации, реализованные в GOLEM-SA.

Мультистарт локального поиска. Данный метод – один из первых методов глобальной оптимизации, заключающийся в многократном решении задачи оптимизации некоторым локальным методом оптимизации, начиная из случайно выбранной стартовой точки. В системе GOLEM-SA конкретный алгоритм локального спуска выбирается автоматически в зависимости от типов переменных. Если переменные задачи вещественные, будет использоваться метод поиска по образцу (метод Хука–Дживса); если переменные дискретные, применяется метод локального спуска для дискретных переменных. Если задача имеет смешанные переменные, будет использоваться подходящая комбинация описанных методов локального поиска.

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

В общем виде работу ГА можно представить следующим образом.

1.   Инициализировать случайным образом популяцию решений.

2.   С помощью оператора селекции выбрать часть популяции (родителей) для порождения потомков.

3.   Применить оператор скрещивания и получить потомков.

4.   Подвергнуть мутации новые решения (потомков).

5.   Сформировать новую популяцию: выбрать решения из родителей и потомков.

6.   Повторять шаги 2–5 до выполнения условия остановки.

Вероятностный ГА. В процессе своей работы ГА накапливают и обрабатывают некоторую ста­тистическую информацию о пространстве поиска, однако в явном виде эта статистика отсутствует. В вероятностном ГА [1] предложен следующий способ представления накопленной ГА статистики: на текущей итерации в соответствие популяции решений ставится вектор вероятностей  , где  – вероятность присвоения i-й компоненте вектора решения Xk значения 1; k – номер итерации.

В общем виде работу вероятностного ГА можно представить следующим образом.

1. Инициализировать случайным образом популяцию решений.

2. С помощью оператора селекции выбрать r наиболее пригодных инди­видов текущей популяции (родителей). Вычислить вектор вероятностей по формуле ,  , где n – длина хромосомы;  – j-й бит i-го индивида.

3. В соответствии с распределением  сформировать популяцию потомков.

4. Применить оператор мутации к популяции потомков.

5. Из популяции родителей и потомков сформировать новую популяцию.

6. Повторять шаги 2–5 до выполнения условия остановки.

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

Метод оптимизации роем частиц (Particle swarm optimization, PSO). Метод основан на имитации стайного (общественного) поведения: рассматривают коллектив решений, называемых частицами, и перемещают частицы в пространстве поиска по траекториям, определяемым простыми математическими формулами [3]. Перемещение частицы определяется лучшим ее положением и лучшим известным положением среди всех частиц.

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

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

Пусть N – количество заемщиков; kj – сумма кредита, запрашиваемая j-м заемщиком; tj – срок, на который j-й заемщик берет кредит; xj – булева переменная, принимающая значение 1, если кредит kj выдается, и 0, если заявка на получение кредита отклоняется банком; yj – целочисленная переменная, показывающая, в какой промежуток времени будет выдан j-й кредит; dj – проценты за пользование j-м кредитом; Pj – вероятность невыполнения заемщиком обязательств по возврату кредита и процентов по нему. В предлагаемой постановке задачи принимаются два варианта обслуживания долга заемщиком: 100 %-ный возврат суммы кредита и процентов по нему в установленный срок либо полное отсутствие платежей в погашение кредита и процентов по нему; Rmax – ограничение на суммарную рискованность кредитного портфеля.

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

Средняя рискованность кредитного портфеля должна быть меньше некоторой заданной величины: .

Еще одним ограничением является наличие средств у банка в каждый промежуток времени. Пусть B0 – собственные средства банка в начале срока, на который ведется планирование. Тогда для собственных средств банка в i-й период может быть получена следующая формула:  , где Oj,i – сумма, выплачиваемая банком j-му заемщику в i-й промежуток времени; Ij,i – сумма, выплачиваемая j-м заемщиком банку в i-й промежуток времени. Должно иметь место следующее неравенство: .

Задача была решена с помощью программной системы GOLEM-SA и методом PBIL (Population Based Incremental Learning). Результаты приведены в таблице, из которой видно, что время работы алгоритмов практически не отличается (в обоих случаях выполняется одинаковое количество вычислений целевой функции), а по качеству решений PBIL уступает предложенному подходу.

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

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

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

Среднее время завершения всех работ после прекращения их поступления на вход системы массового обслуживания при настройках, полученных с помощью GOLEM-SA, составило 3,5 мин., а метода PBIL – 3,8 мин.

По t-критерию Стьюдента различие между результатами является статистически значимым на уровне 0,01 (выборочное стандартное отклонение среднего равно 0,054).

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

Литература

1.  Семёнкин Е.С., Сопов Е.А. Вероятностные эволюционные алгоритмы оптимизации сложных систем // Интеллектуальные системы (AIS'05); Интеллектуальные САПР (CAD-2005): тр. Междунар. науч.-технич. конф. М.: Физматлит, 2005. Т. 1. 452 с.

2.  Галушин П.В., Семёнкин Е.С. Асимптотический вероятностный генетический алгоритм // Вестн. СибГАУ им. акад. М.Ф. Решетнева. 2009. Вып. 4 (25). С. 37–42.

3.  Kennedy J., Eberhart R. Particle Swarm Optimization // Proceedings of IEEE International Conference on Neural Networks-IV (Perth, Australia, 1995). IEEE Service Center, Piscataway, NJ, pр. 1942–1948.