DEVELOPMENT AND EVALUATION OF EVOLUTIONARY ALGORITHMS FOR DISCRETE OPTIMIZATION

Resumo

This paper proposes a modification of evolutionary optimization algorithms, which can be used to solve optimiza- tion problems with discrete variables without transformation of original problem into pseudo-boolean problem. It also evaluates efficiency of proposed methods applied for solution of problem of bank credit portfolio building.

Texto integral

Задачи оптимизации постоянно возникают в прак- тической деятельности человека. Действительно, если существует возможность выбирать параметры техни- T N E( x, y) = ∑∑ i =1 j =1 (Income( x j , y j , i, k j , t j , d j ) − ческой или экономической системы, то разумно сде- лать это самым лучшим (в смысле некоторого крите- рия) образом. Все более актуальными становятся сложные задачи оптимизации, т. е. задачи, в которых целевая функция не обладает свойствами гладкости, унимодальности, выпуклости, позволяющими эффек- тивно применять классические методы оптимизации. Зачастую для целевой функции не существует даже аналитического выражения. В качестве примера задач такого типа можно на- звать задачу формирования кредитного портфеля бан- ка [1], заключающуюся в формировании кредитного портфеля, максимизирующего прибыль банка, при наличии жестких ограничений по суммам имеющихся в наличии свободных кредитных ресурсов, процент- ным ставкам на выдаваемые кредиты, срокам привле- чения ресурсов и максимальному размеру кредита на одного заемщика. − Outcome( x j , y j , i, k j )), где T – количество промежутков времени (месяцев), на которых осуществляется планирование; N – коли- чество кредитных заявок; Income( ) – сумма, выпла- чиваемая j-м заемщиком банку в i-й промежуток вре- мени; Outcome( ) – сумма, выплачиваемая банком j-му заемщику в i-й промежуток времени. Переменная Outcome принимает следующие зна- чения: если xj = 1 и yj = i, то нужно вернуть сумму кредита kj, в противном случае вернуть 0. Переменная Income вычисляется следующим образом. Шаг 1. Если xj = 0, то Income = 0. Выйти из проце- дуры. Шаг 2. Если yj > i, то Income = 0. Выйти из проце- дуры. Шаг 3. Вычислить количество оставшихся дней до истечения срока кредита по формуле i −1 Пусть N – количество заемщиков; kj – сумма кре- дита, запрашиваемая j-м заемщиком; tj – срок, на ко- торый j-й заемщик берет кредит; xj – булева перемен- rest = t j − ∑ s = y j Ts . ная, принимающая значение: 1, если кредит kj выдает- ся, и 0, если заявка на получение кредита отклоняется банком; yj – целочисленная переменная, показываю- щая, в какой промежуток времени будет выдан j-й кредит; dj – проценты за пользование j-м кредитом; Pj – вероятность невыполнения заемщиком обязательств по возврату кредита и процентов по нему; Ti – коли- чество дней в i-м промежутке времени (месяце); ρ – ограничение на суммарную рискованность кредитно- Шаг 4. Если Rest < 0, то Income = 0. Выйти из про- цедуры. Шаг 5. Вычислить количество дней в текущем i-м промежутке времени для уплаты кредита по формуле Period = min {Ti , Rest}. Шаг 6. Вычислить количество денежных средств, которые выплачивает j-й заемщик банку в текущий i- й промежуток времени: period period го портфеля. В предлагаемой постановке задачи предполагается два варианта обслуживания долга за- Income = k j ⋅ 0, 01⋅ d j ⋅ 365 + k j ⋅ . j емщиком: 100%-й возврат суммы кредита и процен- тов по нему в установленный срок либо полное отсут- ствие платежей в погашение кредита и процентов по нему. Средняя рискованность кредитного портфеля должна быть меньше некоторой заданной величины: N ∑ x j ⋅ Pj j =1 Целевая функция прибыли банка после выдачи и погашения всех кредитов будет выглядеть следую- щим образом: R( x ) = N ∑ x j j =1 ≤ ρ. *Работа выполнена при финансовой поддержке ФЦП «Исследования и разработки по приоритетным направлениям раз- вития научно-технологического комплекса России на 2007–2013 годы» (НИР 2011-1.9-519.-005-042) и ФЦП «Научные и научно-педагогические кадры России» (НИР 2011-1.2.1-113-025, 2011-1.2.2-215-021). 25 Математика, механика, информатика Еще одним ограничением является неотрицатель- ность наличных средств у банка в каждый промежу- ток времени. Пусть B0 – собственные средства банка в начале срока, на который ведется планирование. То- гда собственные средства банка в i-й период можно определить по формуле Bi ( x, y) = N = Bi −1 + ∑(I ( x j , y j , s, k j , t j , d j ) − O( x j , y j , s, k j ) ) j =1 и должно иметь место следующее неравенство: min {Bi } ≥ 0. i =1...T Для решения сложных задач оптимизации, как правило, применяются методы прямого поиска. Од- ним из важнейших классов этой группы методов яв- ляются генетические алгоритмы (ГА) [2], имитирую- щие эволюционные и генетические процессы, проис- ходящие в популяциях живых организмов. Генетиче- ский алгоритм работает на каждой итерации не с единственным решением, а с целым коллективом ре- шений, или популяцией (в терминологии ГА). Среди решений текущий популяции производится отбор (селекция) перспективных особей в промежу- точную популяцию, которая затем используется для порождения особей новой популяции. Существует несколько основных методов селекции: пропорцио- нальная, ранговая и турнирная. При пропорциональ- ной селекции вероятность прохождения решением отбора пропорциональна значению целевой функции для этого решения, а поскольку вероятность не может быть отрицательной величиной, то данный метод тре- бует, чтобы значения целевой функции были преобра- зованы в неотрицательные величины. При примене- нии ранговой селекции вероятности прохождения отбора зависят не от значений целевой функции, а от их ранга в популяции. Метод турнирной селекции заключается в том, что турнирная группа формирует- ся случайным образом и лучшее в смысле значения целевой функции решение становится победителем турнира и проходит отбор. На основе отобранных в ходе этапа селекции ре- шений с помощью генетических операторов скрещи- вания и мутации формируются новые решения. В ходе скрещивания два родительских решения используются для формирования нового решения. Основными методами скрещивания являются одното- чечное, двухточечное и равномерное скрещивание. При одноточечном скрещивании векторы родитель- ских решений делятся случайным образом на две час- ти, порождаемое решение получает первую часть от первого родителя, вторую – от второго. В процедуре двухточечного скрещивания векторы родительских решений разделяются на три части, а порождаемое решение получает начальную и конечную часть от первого решения, а среднюю – от второго. Равномер- ное скрещивание заключается в том, что каждый ген порождаемого решения переходит от случайно вы- бранного родительского решения. В ходе мутации компоненты решения с небольшой вероятностью, которую называют вероятностью му- тации, заменяются на противоположные. Основное предназначение оператора мутации – предотвращение преждевременной сходимости алгоритма. На псевдокоде генетический алгоритм можно опи- сать следующим образом. Шаг 1. Создать и оценить начальную популяцию с равномерным распределением генов. Шаг 2. Если выполнен критерий останова, то пре- кратить работу. Шаг 3. Сформировать промежуточную популяцию с помощью выбранного метода селекции. Шаг 4. Создать новую популяцию на основе про- межуточной с использованием выбранного оператора скрещивания и мутации. Шаг 5. Перейти к шагу 2. Вероятностный генетический алгоритм (ВГА) – это попытка создать процедуру оптимизации, имею- щую схему, похожую на схему стандартного генети- ческого алгоритма [3]. В вероятностном генетическом алгоритме явным образом (в отличие от традиционно- го ГА) вычисляются компоненты вектора вероятно- стей и отсутствует оператор скрещивания (вместо него используется оператор порождения случайного решения с заданным распределением вероятностей компонент), но сохранены генетические операторы мутации и селекции. На псевдокоде ВГА можно представить следую- щим образом. Шаг 1. Создать и оценить начальную популяцию с равномерным распределением генов. Шаг 2. Если выполнен критерий останова, то пре- кратить работу. Шаг 3. Сформировать промежуточную популяцию с помощью выбранного метода селекции. Шаг 4. Оценить распределение вероятностей зна- чений генов в промежуточной популяции. Шаг 5. Создать популяцию потомков с получен- ным распределением вероятностей. Шаг 6. Применить к полученным решениям опе- ратор мутации. Шаг 7. Создать новую популяцию на основе попу- ляции потомков. Шаг 8. Перейти к шагу 2. Дальнейшим развитием идей ВГА стал асимпто- тический вероятностный генетический алгоритм (АВГА) [4], название которого связано с тем, что его операторы являются предельным случаем операторов вероятностного генетического алгоритма (при стрем- лении размера промежуточной популяции к беско- нечности). В частности, процедура мутации, приме- няемая в АВГА, заключается в корректировке распре- деления (асимптотической мутации), а распределение значений генов для новой популяции вычисляется непосредственно по текущей популяции с учетом ве- роятностей прохождения селекции (асимптотической селекции) без статистического моделирования селек- ции по методу Монте-Карло. Работа АВГА осуществ- ляется следующим образом. 26 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Шаг 1. Создать и оценить начальную популяцию с равномерным распределением генов. Шаг 2. Если выполнен критерий останова, то пре- кратить работу. Шаг 3. Построить распределение с помощью опе- ратора асимптотической селекции. Шаг 4. Скорректировать распределение с помо- щью оператора асимптотической мутации. Шаг 5. Создать новую популяцию с полученным распределением вероятностей. Оценить новую попу- ляцию. Шаг 6. Перейти к шагу 2. Описанные выше алгоритмы являются методами псевдобулевой оптимизации, т. е. оптимизации функ- ций с булевыми переменным и вещественными зна- чениями. Однако ГА (или любой другой алгоритм псевдобулевой оптимизации) можно использовать для оптимизации функций дискретных и/или веществен- ных переменных, если совместить его с методом би- наризации, основанном на том, что дискретные и ве- щественные переменные кодируются (с некоторой погрешность в случае вещественных переменных) с помощью стандартного бинарного кода или грей- кода [5], а генетические операторы мутации и скре- щивания действуют на бинарное представление ре- шений. Таким образом, метод бинаризации позволяет решать задачи оптимизации со смешанными пере- менными с помощью методов псевдобулевой оптими- зации. Двоичная кодировка обладает еще одним преиму- ществом: бинарное представление решения имеет наибольшую возможную длину среди всех неизбы- точных представлений данного числа, а следователь- но, наибольшую возможную мощность точек, отли- чающихся от заданной точки одним разрядом (одно- соседних точек). Если использовать для кодирования грей-код, то однососедние точки естественного пред- ставления переменных перейдут в однососедние точ- ки двоичного кода, поэтому новые локальные экстре- мумы у функции с двоичным представлением пере- менных не появятся. С другой стороны, поскольку мощность системы окрестностей будет увеличена, то некоторые локальные экстремумы могут исчезнуть. Эволюционные алгоритмы дискретной опти- мизации. Если дискретная переменная может прини- мать N различных значений, то для хранения ее дво- ном порождении будут появляться чаще, чем другие. Подобные неоднородности могут уменьшить надеж- ность алгоритма в тех случаях, когда у оптимума бу- дет одно бинарное представление, а у большой части малоперспективных точек – два; – для хранения бинарного решения будет требо- ваться больше памяти, чем это теоретически необхо- димо. Конечно, избыток в 1 бит может показаться незначительным, но в современных ЭВМ бит не явля- ется адресуемой единицей, поэтому если не использо- вать побитовые операции, то дополнительные затраты памяти составят не менее байта. Если же служебная информация хранится для каждого гена (как, напри- мер, в вероятностном генетическом алгоритме), то дополнительных затрат памяти избежать не удастся даже с использованием манипуляций с отдельными битами, которые также увеличивают размер кода про- граммы [6]; – большее количество генов увеличивает не только затраты памяти, но и время, затрачиваемое на работу алгоритма, так как генетические операторы мутации (при прямолинейной реализации этих операторов) и скрещивания требуют обхода всех битов бинарного представления, т. е. их сложность пропорциональна количеству генов. Кроме того, в современных вычис- лительных машинах увеличение затрат памяти само по себе может стать причиной уменьшения быстро- действия. Таким образом, для решения задач дискретной оп- тимизации перспективной является идея разработки генетического алгоритма без предварительной бина- ризации. Рассмотрим, каким образом для этого нужно модифицировать основные этапы эволюционных ал- горитмов: порождение решений с заданным распре- делением, селекцию, скрещивание и мутацию. Селекция не требует каких-либо модификаций, так как на этом этапе роль играют только значения целе- вой функции (или их ранги), а не представления ре- шений. Процедуры случайного порождения решений, скрещивания и мутации, напротив, действуют на кон- кретное представление решения, поэтому их необхо- димо модифицировать. При проектировании этих операторов следует учитывать, что дискретные пере- менные могут быть измерены в различных шкалах: номинальной или ранговой [7]. В данной статье мы ограничимся случаем номи- нальных переменных, так как любую шкалу можно ичного представления потребуется n = ⎡⎣log2 ( N )⎤⎦ рассматривать как номинальную (с соответствующим двоичных разрядов. И если при использовании метода бинаризации количество возможных значений дис- кретной переменной не является целой степенью двойки, то некоторым дискретным значениям будут соответствовать две различные бинарные строки. Эта особенность метода бинаризации приводит к сле- дующим проблемам: – так как некоторым дискретным значениям будет соответствовать одна бинарная строка, а некоторым – две, то отдельные дискретные значения при случай- огрублением результата). Кроме того, в случае не очень большого количества возможных значений раз- личия между номинальной и ранговой шкалами будут несущественными. Оператор мутации для номинальных переменных разумно определить следующим образом: с некоторой вероятностью (вероятностью мутации) переменной присваивается случайно выбранное значение, причем все значения выбираются с одной и той же вероятно- стью, так как номинальная шкала не позволяет судить 27 Математика, механика, информатика о степени близости двух значений. Оператор мутации должен вносить небольшие изменения в решения, поэтому вероятность мутации, так же как и в случае булевых переменных, следует выбирать достаточно малой. В случае номинальных дискретных переменных можно определить аналоги всех трех основных опера- торов скрещивания стандартного генетического алго- ритма: так как значения номинальных переменных можно только проверять на равенство, то каждый компонент решения должен переходить от одного из родительских решений. Предложенный подход можно распространить и на вероятностный генетический алгоритм. Оценка распределения и генерация решений в соответствии с построенным распределением является довольно прямолинейной задачей, а операторы селекции и му- тации ВГА не отличаются от соответствующих опера- торов ГА. Исследование исходных алгоритмов и их модифи- каций на тестовых функциях, взятых из [3], показало преимущество эволюционных алгоритмов, исполь- зующих небинарное кодирование. Кроме небольшого увеличения средней надежности это преимущество выражалось в более точном представлении решения: в некоторых случаях этими алгоритмами было получе- но точное (без погрешности) решение, в то время как бинарные эволюционные алгоритмы останавливались в точках, достаточно близких к истинному оптими- муму, но не совпадающих с ним. Численные данные для апробации на практиче- ской задаче формирования кредитного портфеля бан- ка были взяты из [1]. В качестве альтернативы ГА и ВГА был рассмотрен мультистарт локального поиска: алгоритм локального поиска дискретной оптимизации запускался заданное число раз из случайно выбранной точки. Численные эксперименты производились при следующих настройках: размер популяции – 100; чис- ло итераций – 100; число запусков для усреднения результатов – 100; селекция – турнирная (размер тур- нирной группы – 2); мутация – слабая; скрещивание (в генетическом алгоритме) – равномерное. В алго- ритмах, которым необходима бинаризация перемен- ных задачи, использовался грей-код. Для учета огра- ничений применялся следующий метод: если доля допустимых решений в популяции была меньше оп- ределенного порога, то выполнялась минимизация по степени нарушения ограничений; если же допусти- мых решений было достаточно, то в качестве значе- ния пригодности использовалось значение целевой функции, а недопустимые решения не переходили в новую популяцию. Результаты решения задач, полученные различны- ми методами дискретной оптимизации, приведены в таблице. Для ГА, ВГА и АВГА в скобках указан способ кодирования: двоичные гены – стандартный генетический алгоритм, троичные и десятичные гены – предложенные модификации, использующие для ко- дирования целочисленных переменных соответствен- но троичную и десятичную систему счисления. Задача формирования кредитного портфеля банка также была решена с помощью методов PBIL (Population Based Incremental Learning – последова- тельное популяционное обучение) [8] и PSO (Particle Swarm Optimization – оптимизация роем частиц) [9]. Анализ данных таблицы показывает, что и генети- ческий алгоритм, и вероятностный генетический ал- горитм дискретной оптимизации по эффективности решения задачи и быстродействию превосходят свои аналоги, использующие бинаризацию. Кроме того, оба эти метода существенно эффективнее мульти- старта локального поиска и метода PSO. Наилучшие результаты показал АВГА, использующий троичное кодирование. Полученные результаты позволяют сде- лать вывод о том, что предложенные подход к реше- нию задач дискретной оптимизации без предвари- тельной бинаризации объектных переменных являет- ся состоятельным. Результаты решения задачи формирования кредитного портфеля банка АлгоритмСреднее значениеВыборочное среднеквадратическое уклонение значения целевой функцииВремя работы, с Локальный поиск5 855206,190,20 ГА (двоичные гены)6 28527,477,18 ГА (троичные гены)6 29021,786,85 ГА (десятичные гены)6 28725,467,16 ВГА (двоичные гены)6 30619,347,19 ВГА (троичные гены)6 30820,157,60 ВГА (десятичные гены)6 30722,398,10 АВГА (двоичные гены)6 31618,137,60 АВГА (троичные гены)6 31818,707,38 АВГА (десятичные гены)6 31819,817,81 PBIL6 30916,977,33 PSO (дискретный)6 26721,277,85 28 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева