Software & Systems

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

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

-    выбор индивидуальных алгоритмов;

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

-    независимая работа выбранных алгоритмов в течение интервала адаптации (обычно около 5 поколений);

-    оценка алгоритмов;

-    перераспределение ресурсов;

-    миграция лучших индивидов во все подпопуляции.

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

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

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

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

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

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

При решении задач многокритериальной оптимизации использовался единственный метод решения таких задач эволюционными алгоритмами SPEA 2, который в настоящее время признан наиболее эффективным [5]. Адаптация коэволюционного алгоритма к классу задач многокритериальной оптимизации сопряжена с существенными изменениями. Алгоритм SPEA 2 направлен на поиск наиболее репрезентативной аппроксимации множества Парето, поэтому на каждом поколении осуществляется поиск недоминируемых точек, при этом наиболее удаленных друг от друга в пространстве критериев. Наличие в стандартном коэволюционном алгоритме изолированных друг от друга подпопуляций в течение интервала адаптации приводит, во-первых, к высокой вероятности появления повторяющихся или близких друг к другу индивидов и, во-вторых, к появлению значительного числа индивидов, доминируемых индивидами из других подпопуляций. Решением проблем является использование единой популяции для всех индивидуальных алгоритмов. При этом закрепленная за каждым идивидуальным алгоритмом часть потомков генерируется согласно его настройкам. Формирование новой популяции из родителей и потомков на каждом поколении осуществляется на основе результатов работы всех алгоритмов.

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

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

При тестировании задач многокритериальной оптимизации не используются различные типы селекции, так как авторами алгоритма SPEA 2 предусмотрено использование только турнирной селекции [5]. Таким образом, число индивидуальных алгоритмов (равное числу алгоритмов в коэволюции) для задач безусловной многокритериальной оптимизации составляет 3 (3 типа скрещивания), а для задач условной многокритериальной оптимизации – 9 (3 типа скрещивания, 3 типа метода учета ограничений). Критерием эффективности работы алгоритма для многокритериальной оптимизации является процент паретовских решений в множестве недоминируемых решений, генерируемых алгоритмом. В случае статистической неразличимости этого параметра сравнивается средний разброс в пространстве критериев (показатель репрезентативности аппроксимации множества Парето).

Результаты исследований приведены в таблицах 1–4. Жирным шрифтом выделены наилучшие показатели.

Таблица 1

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

Таблица 2

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

Таблица 3

Результаты исследований на задачах безусловной многокритериальной оптимизации (процент паретовских решений)

Таблица 4

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

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

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

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

Литература

1.   Eiben A.E., Smith J.E. Introduction to evolutionary computing.  Berlin: Springer-Verlag, 2003.

2.   Schlierkamp-Voosen D., Mühlenbein H. Strategy Adaptation by Competing Subpopulations // Parallel Problem Solving from Nature III. Lecture Notes in Computer Science 866. Springer-Verlag, 1994.

3.   Жукова М.Н. Коэволюционный алгоритм решения сложных задач оптимизации: дисс. … канд. техн. наук. Красноярск: СибГАУ, 2004. 126 с.

4.   Сергиенко Р.Б. Коэволюционный алгоритм условной оптимизации: разработка и приложения // Интеллектуальные системы (AIS'08): Интеллектуальные САПР (CAD-2008): тр. Междунар. науч.-технич. конф. М.: Физматлит, 2008. Т. 1. С. 33–40.

5.   Zitzler E. Laumanns M., Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Zurich, Switzerland: Swiss Federal Institute of Technology, 2001. 19 p.