Представлен сравнительный анализ эффективности классических моделей Голдберга и Холланда и их модификаций, использующих различные варианты поколенческой стратегии. В классических генетических алгоритмах используется концепция, предполагающая, что количество особей в поколении не изменяется. Рассмотрен подход, позволяющий повысить эффективность работы стандартных моделей Голдберга и Холланда за счёт варьирования количества особей в поколении. Различные варианты поколенческой стратегии применены для решения однородной минимаксной задачи теории расписаний, относящейся к классу NP-полных задач. Проведённый вычислительный эксперимент для различного количества процессоров и работ показал, что данный подход позволяет значительно повысить эффективность работы генетических алгоритмов путём малых изменений стандартных моделей, позволяя получать решение, более близкое к точному.
генетические алгоритмы, модель Голдберга, модель Холланда, NP-полные задачи, поколенческая стратегия, теория расписаний.
Введение. Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. Существуют различные варианты задач теории расписаний. Часть из них является NP-полными. NP-полные задачи образуют подмножество типовых задач в классе NP, к которым можно свести любую другую задачу из этого класса полиномиально быстрым алгоритмом решения [1, 8, 9]. В различных областях дискретной математики, комбинаторики и логики известно множество задач, принадлежащих к классу NP-полных задач. Для этих задач не найдены полиномиальные алгоритмы. Однако и не доказано, что таких алгоритмов не существует. Нахождение точного решения для задачи из класса NP-полных является практически невыполнимым. Поэтому для таких задач разрабатываются различные методы, позволяющие получить приближённое решение.
1. Кобак, В. Г. Сравнительные характеристики модификации модели Холланда при поко-ленческой стратегии / В. Г. Кобак, Н. И. Троцюк, Б. А. Рожковский // Тр. Сев.-Кавк. фил. Моск. техн. ун-та связи и информатики. - Ростов-на-Дону : ПЦ «Университет» Сев.-Кавк. фил. Моск. техн. ун-та связи и информатики, 2014. - Ч. 1. - С. 319-322.
2. Кобак, В. Г. Сравнительный анализ алгоритмов : генетического с элитой и Крона с гене-тическим начальным распределением / В. Г. Кобак, Н. И. Троцюк // Мат. методы в технике и тех-нологиях : сб. тр. XXVI междунар. науч. конф. - Саратов, 2013. - Т. 12, ч. 2. - С. 62-64.
3. Кобак, В. Г. Использование поколенческой стратегии модели Голдберга при решении однородной минимаксной задачи / В. Г. Кобак, Н. И. Троцюк // Аспирант. - 2014. - № 2. - С. 62-64.
4. Базы данных. Интеллектуальная обработка информации / В. В. Корнеев [и др.]. - Москва : Нолидж, 2000. - 352 с.
5. Нейдорф, Р. А. Сравнительный анализ эффективности вариантов турнирного отбора ге-нетического алгоритма решения однородных распределительных задач / Р. А. Нейдорф, В. Г. Кобак, Д. В. Титов // Вестник Дон. гос. техн. ун-та. - 2009. - Т. 9, № 3. - С. 410-418.
6. Курейчик, В. М. Генетические алгоритмы и их применение / В. М. Курейчик. - Изд. 2-е, доп. - Таганрог : Изд-во Таганрог. радиотехн. ун-та, 2002. - 242 с.
7. Курейчик, В. М. Генетические алгоритмы / В. М. Курейчик, Л. А. Гладков, В. В. Курейчик. - Москва : Физматлит, 2006. - 319 с.
8. Коффман, Э. Г. Теория расписаний и вычислительные машины / Э. Г. Коффман. - Москва : Наука, 1984. - 336 с.
9. Пашкеев, С. Д. Машинные методы оптимизации в технике связи / С. Д. Пашкеев, И. Р. Менязов, В. Д. Могилевский. - Москва : Связь, 1976. - 250 c.
10. Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Воронеж : Воронеж. гос. техн. ун-т, 1995. - 69 с.
