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

УДК 681.3+681.5

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКОМ МОДЕЛИ ПРИ ИСПОЛЬЗОВАНИИ РАЗЛИЧНЫХ ВИДОВ МУТАЦИИ

© 2012 г. В.Г. Кобак*, А.Ю. Чижов**, Д.В. Плешаков *

Донской государственный технический университет, г. Ростов-на-Дону

Южно-Российский государственный технический университет

Donskoy State Technical University, Rostov-on-Don

"South-Russian State Technical University

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

Ключевые слова: генетические алгоритмы; минимаксный критерий; однородная система; неоднородная система; мутация; модель СНС.

In this paper was considered effectiveness of including different types of mutations into standard CHC model for resolving homogeneous and heterogeneous minimax task. Was considered pointed, dual-pointed, strong mutation and inversion. Derived by this mutations types results was compared as between themselves for revelation of most effectiveness mutation type, so between standard CHC model for comparing standard and modified model.

Keywords: genetic algorithm; the minimax criterion; homogeneous system; heterogeneous system; mutation; CHC model.

Введение

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

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

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

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

Целью данной работы является исследование эффективности модели СНС, модифицированной различными видами мутации и кроссовера.

Постановка задачи

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

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

стве, время выполнения определяется значением 'l(tipj) [1]. В каждый момент времени отдельный

процессор обрабатывает не более одного задания, и выполнение задания не прерывается для передачи на другой процессор. Требуется найти такое распределение заданий по процессорам, при котором суммарное время выполнения заданий на каждом из процессоров было бы минимальным [2, 3].

Модель СНС

Данная модель была предложена Эшельманом в 1991 г. [4]. Она характеризуется следующими особенностями:

- особи для скрещивания должны предельно отличаться (Яга"-кроссовер);

- кроссовер проводится для всех особей;

- новое поколение формируется выбором особей как из потомков, так и из родителей;

Таблица 1

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

№ M Вид мутации Классический СНС ЯЫ-кроссовер Классический кроссовер

Точечная 427 427

31 Двухточечная 427 427 427

Инверсия 427 427

Сильная 427 427

Точечная 1800 1800

2 131 Двухточечная 1800 1800 1800

Инверсия 1800 1800

Сильная 1800 1800

Точечная 3174 3174

231 Двухточечная 3174 3174 3174

Инверсия 3174 3174

Сильная 3174 3174

Точечная 286 286

31 Двухточечная 286 285 284

Инверсия 285 285

Сильная 286 285

Точечная 1200 1200

3 131 Двухточечная 1200 1200 1200

Инверсия 1200 1200

Сильная 1200 1200

Точечная 2119 2119

231 Двухточечная 2119 2119 2119

Инверсия 2119 2119

Сильная 2119 2119

Точечная 215 215

31 Двухточечная 217 215 215

Инверсия 215 215

Сильная 216 216

Точечная 902 901

4 131 Двухточечная 903 902 901

Инверсия 902 902

Сильная 904 904

Точечная 1589 1588

231 Двухточечная 1591 1589 1589

Инверсия 1589 1589

Сильная 1591 1591

Точечная 179 179

31 Двухточечная 181 178 177

Инверсия 178 178

Сильная 179 179

Точечная 723 721

5 131 Двухточечная 726 722 721

Инверсия 722 722

Сильная 727 726

Точечная 1272 1270

231 Двухточечная 1275 1271 1270

Инверсия 1271 1271

Сильная 1277 1277

- после формирования нового поколения для всех особей, кроме лучшей, проводится сильная мутация (мутирует до 30 % генов);

Генетический алгоритм на базе модели СНС работает по следующему принципу:

1. Создается начальная популяция. Определяется текущее значение критерия. Задается счетчик повторов.

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

Результаты для не

3. Из промежуточной популяции, в соответствии с размером начальной популяции, выбирается нужное количество наиболее приспособленных особей. Худшие особи отбрасываются.

4. Оценивается новое состояния критерия. Если критерий изменился, переходим к пункту 4 а, если не изменился, то к пункту 4 Ь.

a) сброс счетчика повторов, новая популяция становится текущей, переход к пункту 2;

b) уменьшаем счетчик повторов на 1, переходим к пункту 5.

Таблица 2

нородной системы

№ M Вид мутации Классический СНС ЯЫ-кроссовер Классический кроссовер

Точечная 417 416

31 Двухточечная 415 415 415

Инверсия 417 415

Сильная 418 416

Точечная 1753 1742

2 131 Двухточечная 1750 1746 1739

Инверсия 1768 1760

Сильная 1774 1770

Точечная 3095 3073

231 Двухточечная 3087 3084 3068

Инверсия 3132 3116

Сильная 3139 3134

Точечная 281 280

31 Двухточечная 280 280 279

Инверсия 281 281

Сильная 282 281

Точечная 1169 1147

3 131 Двухточечная 1174 1173 1156

Инверсия 1183 1180

Сильная 1187 1184

Точечная 2061 2020

231 Двухточечная 2077 2073 2039

Инверсия 2092 2087

Сильная 2097 2095

Точечная 209 206

31 Двухточечная 210 210 208

Инверсия 211 210

Сильная 212 210

Точечная 882 856

4 131 Двухточечная 888 886 875

Инверсия 890 889

Сильная 895 894

Точечная 1554 1510

231 Двухточечная 1570 1565 1544

Инверсия 1573 1570

Сильная 1580 1579

Точечная 177 176

31 Двухточечная 179 176 176

Инверсия 177 176

Сильная 178 177

Точечная 710 689

5 131 Двухточечная 717 713 705

Инверсия 715 714

Сильная 723 721

Точечная 1251 1211

231 Двухточечная 1263 1258 1241

Инверсия 1262 1260

Сильная 1271 1270

5. Проверяем состояние счетчика повторов. Если счетчик равен нулю, то переходим к пункту 6, иначе переходим к пункту 2.

6. Для всех особей, кроме лучшей, проводим сильную мутацию, переходим к пункту 7.

7. Полученное решение сравнивается с предыдущим. Если решение отличается, то перезапускаем алгоритм (переходим к пункту 2), иначе выводим результат и выходим из алгоритма.

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

Рассмотренные виды мутации

Теперь рассмотрим виды мутации, которые применялись для модификации модели СНС:

1. Точечная мутация.

При точечной мутации для случайно выбранного гена выполняется его изменение.

2. Двухточечная мутация.

При двухточечной мутации выбираются два случайных гена и меняются местами.

3. Инверсия.

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

4. Сильная мутация.

При сильной мутации мутирует до 30 % генов особи. При этом каждый ген изменяется по принципу точечной мутации.

Поступила в редакцию

Результаты исследований

Расчеты проводились для однородной и неоднородной задачи на 100 различных матрицах. Были взяты следующие параметры:

- число устройств N 2-5, как наиболее часто применяемое на практике [5];

- число заданий М 31, 131 и 231;

- временной интервал от 25 до 30 включительно;

- вероятность мутации и кроссовера были взяты за 100 %;

- число особей в популяции 100;

- число повторов 100.

Для сравнения также были проведены расчеты для классической модели СНС. Результаты представлены в табл. 1 для однородной системы и табл. 2 для неоднородной.

Выводы

Как непосредственно видно из табл. 1, 2, введение мутаций повышает точность решения как однородной, так и неоднородной задач. Однако, если в однородной системе лучшие результаты показывает двухточечная мутация, то в неоднородных системах простейшая одноточечная мутация сильно улучшает результаты решения минимаксной задачи.

Литература

1. Алексеев О.Т. Комплексное применение методов дискретной оптимизации. М., 1987.

2. Коффман Э.Г. Теория расписаний и вычислительные машины. М., 1987.

3. Романовский И.В. Алгоритмы решения экстремальных задач. М., 1977.

4. Шаффер Дж.Д., Эшельман Л.Дж. Комбинаторная оптимизация с использованием генетического алгоритма // Обозрение прикладной и промышленной математики. 1996. Т. 3. № 5.

5. Плотников В.Н., Зверев В.Ю. Методы быстрого распределения алгоритмов в вычислительных системах // Изв. АН СССР. Техническая кибернетика. 1974. № 3. С. 136 - 143.

23 апреля 2012 г.

Кобак Валерий Григорьевич - д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет. Тел. 8-918-580-21-89.

Чижов Александр Юрьевич - канд. техн. наук, заведующий кафедрой «Информационная безопасность», Южно-Российский государственный технический университет (Новочеркасский политехнический институт). Тел. 8-918-503-67-89.

Плешаков Денис Валерьевич - аспирант Донского государственного технического университета. Тел. 8-904446-99-64. E-mail: denispleshakov@inbox.ru

Kobak Valeriy Grigorievich - Doctor of Technical Sciences, professor, department «The software of computers and automated systems», Donskoy State Technical University. Ph. 8-918-580-21-89.

Chizhov Alexander Jurievich - Candidate of Technical Sciences, head of department «Information Security», South-Russia State Technical University (Novocherkassk Polytechnic Institute). Ph. 8-918-503-67-89.

Pleshakov Denis Valerievich - post-graduate student, Donskoy State Technical University. Ph. 8-904-446-99-64. E-mail: denispleshakov@inbox.ru_