Исследование эффективности коэволюционного генетического алгоритма условной оптимизации

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

Для разрешения указанной проблемы предлагаются различные подходы, одним из которых является коэволю-ционный алгоритм [2]. В коэволюционном алгоритме параллельно работают, взаимодействуя при этом между собой, индивидуальные генетические алгоритмы с различными настройками. Конкуренция и кооперация индивидуальных алгоритмов обеспечивает самонастройку эволюционного поиска на решаемую задачу в ходе ее однократного решения и снимает проблему «ручного» выбора наилучшего алгоритма.

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

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

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

• –    задача 1:

I ( x ) = 3 • ( x 1 - 4) 2 + 4 • ( x 1 - 4) x x( x 2 - 4) + 3 • ( x 2 - 4) 2 = min, x 1 + x 2 <  0, x * = (0; 0) ^T ;

• –    задача 2:

I ( x ) = 8 • ( x 1 - 3) 2 + 4 • ( x 1 - 3) x x ( x 2 - 3) + 4 • ( x 2 - 3) 2 = min, - 3 <  x <  3, - 3 <  x 2 <  3, x * = (3; 3) ^T ;

• –    задача 3:

I ( x ) = 3 • ( x 1 - 6) 2 + ( x 1 - 6) x

x ( x 2 - 6) + 3 • ( x 2 - 6) 2 = min,

• - 3 <  x <  3,

• - 3 <  x 2 <  3,

x * = (3; 3) ^T ;

– задача 4:

z = 5 • x + 0,5 • y ^ max, ^y < - 2 • ^{x +} 5, y >- x - 1,5,

« y <  2 • x + 1 x >  0, _ y >  0, 13

x = -3 = 2,166 66, 6

y = у = 0,666 66, z = 67 = 11,166 666 67;

x = 5, y = 0, z = 0, u * = 125;

– задача 9:

I ( x ) = 3 • ( x ₁ - 6)² + ( x ₁ - 6) x x ( x ₂ - 6) + 3 • ( x ₂ - 6)² = min, x ₁ + x ₂ = 0, x * = (0; 0) ^T ;

– задача 10:

I ( x ) = 3 • x 2 + 5 • x ₁ • ( x ₂ - 8) + 3 • ( x ₂ - 8)² = min,

– задача 5:

x ₁ + x ₂ = 0, x* = ( - 4; 4) ^T .

z = 10 x - 5 y ^ max,

Тестовые задачи условной оптимизации 1–3 и 9, 10 взяты из [4], задачи 4–8 – из [5].

У - 15 <  0,

< y + 2 x ² - 20 <  0,

. у ^{- y}<  0,

x

y

z

– задача 6:

3,65148371670110760,

- 6,666 666 66 666 666 696, 69,8481705003110760;

z = -x2 + y2 ^ max, y < 7 + sin (2 • x), ‘ y > 1 - sin (2 • x), . x e[0,4], x = 4, y = 7,989 358 247, z = 79,829 845 20;

– задача 7:

z = - 10 • x - 5 • y ^ min,

Г x >  0, y >^{- 15,} x ²

^y < У

_ y >  2 • x ² - 20, x = 3,651483 717, y = 6,666 666 670, z = - 69,848170 52;

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

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

– задача 8:

u = x + y + z ^ max,

Гx > 0, y > 0, z > °.

_ x ² + y ² + z ² <  25,

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

В табл. 1 представлены все три типа селекции, все три типа скрещивания и все три метода учета ограничений.

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

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

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

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

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

На этапе 3 проводится аналогичная свертка по методу учета ограничений и были получаются три коэволю-ционные комбинации по девять алгоритмов.

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

Необходимо отметить, что итоговый коэволюционный алгоритм включает не все 27 индивидуальных алгоритмов, а только 18 (отсутствуют алгоритмы с одноточечным типом скрещивания). Это объясняется тем, что по результатам исследований было выяснено следующее: алгоритмы с одноточечным и двухточечным типом скре-

Таблица 1

Наилучшие параметры индивидуального ГА для задач условной оптимизации

Задача Селекция Скрещивание Метод учета ограничений Задача 1 Пропорциональная Равномерное «Смертельные» штрафы+«лечение» Задача 2 Турнирная Ранговая Турнирная Ранговая Турнирная Ранговая Турнирная Ранговая Одноточечное Одноточечное Одноточечное Одноточечное Двухточечное Двухточечное Двухточечное Двухточечное Адаптивные штрафы Адаптивные штрафы Динамические штрафы Динамические штрафы Адаптивные штрафы Адаптивные штрафы Динамические штрафы Динамические штрафы Задача 3 Ранговая Ранговая Одноточечное Двухточечное Адаптивные штрафы Адаптивные штрафы Задача 4 Турнирная Ранговая Турнирная Ранговая Турнирная Ранговая Турнирная Ранговая Одноточечное Одноточечное Одноточечное Одноточечное Двухточечное Двухточечное Двухточечное Двухточечное Адаптивные штрафы Адаптивные штрафы Динамические штрафы Динамические штрафы Адаптивные штрафы Адаптивные штрафы Динамические штрафы Динамические штрафы Задача 5 Турнирная Ранговая Двухточечное Двухточечное Динамические штрафы Динамические штрафы Задача 6 Турнирная Ранговая Турнирная Ранговая Одноточечное Одноточечное Двухточечное Двухточечное Динамические штрафы Динамические штрафы Динамические штрафы Динамические штрафы Задача 7 Турнирная Ранговая Турнирная Ранговая Одноточечное Одноточечное Двухточечное Двухточечное Динамические штрафы Динамические штрафы Динамические штрафы Динамические штрафы Задача 8 Турнирная Равномерное Динамические штрафы Задача 9 Турнирная Ранговая Турнирная Ранговая Одноточечное Одноточечное Двухточечное Двухточечное Динамические штрафы Динамические штрафы Динамические штрафы Динамические штрафы Задача 10 Турнирная Двухточечное Динамические штрафы Инвестиционная задача Ранговая Равномерное Адаптивные штрафы Банковская задача Ранговая Двухточечное Динамические штрафы щивания статистически незначительно отличаются друг от друга по эффективности, но при этом на некоторых задачах двухточечное скрещивание все же демонстрирует некоторое преимущество. Использование в итоговой коэволюции всех 27 алгоритмов приводит к некоторому снижению надежности и скорости на всех тестовых задачах. Вероятно, в этом случае будет превышено некоторое критическое число алгоритмов в коэволюционной комбинации, когда негативный эффект от роста числа алгоритмов начинает преобладать над положительным эффектом взаимодействия алгоритмов между собой.

Тестирование проходит при следующих общих настройках алгоритма: интервал адаптации (для коэволю-ционного алгоритма) – пять поколений; штраф для проигравших алгоритмов (для коэволюционного алгоритма) – 10 %; размер «социальной карты» (для коэволю-ционного алгоритма) – 10 %; допуск для нарушения ограничений-равенств – 0,005; процент «лечимых» индивидов в методе «смертельных штрафов» – 20 %; параметр С для динамических и адаптивных штрафов – 0,5; параметры β ₁, β ₂, k для адаптивных штрафов – 1,4; 1,2; 3. Значения всех этих параметров рекомендованы по результатам предыдущих исследований и не требуют настройки.

В тестовых задачах интервал для переменных – [–10; 10], дискретность для переменных – 0,001. В практических задачах соответствующая информация загружается из файла. Число поколений – 100, за исключением инвестици- онной задачи (30 поколений). Начальное число индивидов в алгоритмах приведено в табл. 2.

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

Результаты исследований для задач с ограничениями-неравенствами, ограничениями-равенствами и для практических задач приведены в табл. 3...6. Жирным шрифтом выделены наилучшие показатели для каждой тестовой задачи (первоочередным показателем является надежность, следующим по значимости – скорость сходимости, для банковской задачи первоочередной показатель – лучшее значение прибыли). В случае статистической неразличимости выделяется несколько показателей.

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

Начальный ресурс для алгоритмов

Таблица 2

Класс задач	Этап 1	Этап 2	Этап 3	Этап 4
С ограничениями-неравенствами	600	200	66	33
С ограничениями-равенствами, практические задачи	180	60	20	10

Результаты исследований для задач 1...4 с ограничениями-неравенствами

Таблица 3

Этап	Показатель	Задача 1		Задача 2		Задача 3		Задача 4
		Надежность, %	Скорость	Надежность, %	Скорость	Надежность, %	Скорость	Надежность, %	Скорость
Этап	Средний	24,91	64,08	66,13	63,49	67,93	62,14	73,54	59,64
1	Лучший	73,60	70,80	100,00	55,20	100,00	60,60	100,00	62,60
Этап	Средний	76,78	74,15	89,47	38,56	90,00	51,22	95,93	52,80
2	Лучший	98,80	78,00	100,00	31,20	100,00	30,20	100,00	38,20
Этап	Средний	94,93	69,60	99,87	25,07	99,80	34,40	100,00	28,20
3	Лучший	96,60	65,00	100,00	23,20	100,00	30,20	100,00	27,00
Этап 4		99,00	57,80	100,00	23,00	100,00	31,40	100,00	27,00

Таблица 4

Результаты исследований для задач 5–8 с ограничениями-неравенствами

Этап Показатель Задача 5 Задача 6 Задача 7 Задача 8 Надежность, % Скорость Надежность, % Скорость Надежность, % Скорость Надежность, % Скорость Этап Средний 6,62 73,24 54,99 61,51 8,01 70,49 41,96 78,79 1 Лучший 29,20 73,40 100,00 68,00 32,00 71,00 74,80 70,00 Этап Средний 47,29 69,43 83,49 55,93 49,04 69,44 89,13 67,82 2 Лучший 89,20 72,20 100,00 46,20 91,40 75,60 100,00 63,60 Этап Средний 97,60 51,33 98,07 41,07 98,20 54,20 100,00 48,07 3 Лучший 99,40 48,60 99,20 36,00 99,80 50,40 100,00 41,40 Этап 4 99,00 48,00 98,20 39,40 99,60 50,20 100,00 44,80 показателей эффективности на каждом этапе коэволю-ционной свертки, а для большинства задач – и наилучших показателей.

Итоговый коэволюционный алгоритм (этап 4) работает эффективнее самого лучшего индивидуального алгоритма в семи из восьми тестовых задачах с ограничениями-неравенствами, а также в обеих практических задачах. Наиболее ярко это выражено в задачах 5 и 7: надежность наилучших индивидуальных алгоритмов составляет 29,2 и 32,0 % соответственно, а итогового коэволюци-онного алгоритма – 99,0 и 99,6 % соответственно при одинаковом ресурсе. Таким образом, в задачах условной оптимизации с ограничениями-неравенствами имеет место значительный положительный эффект взаимодействия алгоритмов между собой, чего не наблюдается в такой степени в задачах безусловной оптимизации. Эти результаты, а также результаты, полученные в [2], позволяют сделать общий вывод о том, что коэволюционный алгоритм в задачах безусловной оптимизации работает лучше алгоритмов со средними настройками, но все-таки хуже алгоритма с наилучшими настройками.

В некоторых случаях на промежуточных этапах свертки алгоритмов (для задачи 6 – на этапе индивидуальных алгоритмов) встречаются коэволюционные комбинации, которые несколько превосходят итоговый коэволюцион-ный алгоритм. Так, в задачах 3 и 8 итоговая коэволюция обеспечивает максимальную надежность, однако на предыдущих этапах встречаются комбинации алгоритмов, которые дают улучшение по скорости сходимости в среднем на одно и три поколения соответственно. В задаче 6 есть промежуточная неполная комбинация алгоритмов и индивидуальный алгоритм, которые дают выигрыш по надежности на 2 % по сравнению с итоговым коэволю-ционным алгоритмом. Для инвестиционной задачи неполная комбинация на этапе 2 дает выигрыш в 2 % по надежности и в пять поколений по скорости сходимости.

Для банковской задачи на этом же этапе найдено решение, дающее выигрыш в прибыли по сравнению с решением на этапе 4 в 20 080 руб. (0,012 % от значения целевой функции). Однако эти отличия можно считать малозначительными, так как выигрыш до пяти поколений по скорости сходимости или до 2 % по надежности не сопоставим с затратами на поиск подходящей комбинации алгоритмов.

Аналогичные результаты получены в задачах с ограничениями-равенствами. Итоговый коэволюционный алгоритм значительно лучше среднего индивидуального в обеих задачах и значительного эффективнее лучшего индивидуального в задаче 9 (рост надежности с 56,8 до 80,2 %), в задаче 10 наблюдается снижение надежности на 3 % (с 37,2 до 34 %). Однако при этом в обеих задачах встречаются неполные коэволюционные комбинации, которые дают выигрыш в надежности по сравнению с итоговой коэволюцией в среднем на 13 и 11 % соответственно, что не может быть признано малозначительным.

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

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

Таблица 5

Результаты исследований для задач с ограничениями-равенствами

Этап	Показатель	Задача 9		Задача 10
		Надежность, %	Скорость	Надежность, %	Скорость
Этап 1	Средний	29,37	51,39	17,21	50,76
	Лучший	56,8	71,8	37,2	75,4
Этап 2	Средний	83,80	63,91	32,82	67,67
	Лучший	93,6	70,2	45,4	51,8
Этап 3	Средний	75,07	52,67	35,47	57,73
	Лучший	79,8	48,4	36,4	56,0
Этап 4		80,2	54,0	34,0	59,0

Таблица 6

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

Этап		Инвестиционная задача		Банковская задача
		Надежность, %	Скорость	Лучшая прибыль	Средняя прибыль	Скорость
Этап 1	Средний	55,29	18,07	199 760 935,7	199 606 449,8	60,37
	Лучший	97,0	16,6	199 843 184	199 617 408	65
Этап 2	Средний	73,36	15,64	199 840 746,7	199 673 820,4	80,22
	Лучший	100,0	12,8	199 893 440	199 672 480	82
Этап 3	Средний	98,93	16,53	199 844 565,3	199 643 189,3	81,0
	Лучший	99,6	15,6	199 870 448	199 643 520	79
Этап 4		98,2	18,2	199 869 360	199 638 544	76

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

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