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

Ключевые слова: теория расписаний, неоднородная минимаксная задача, модифицированная модель Голдберга, генетический алгоритм, минимаксный критерий, квадратичный критерий, минимаксный критерий, кубический критерий, алгоритм Плотникова-Зверева

05.13.18 - Математическое моделирование, численные методы и комплексы программ

В статье рассматривается проблема решения неоднородной минимаксной задачи, характерной для теории расписаний. Данная задача является NP-полной и для нее не существует точного алгоритма решения, имеющего полиномиальное время для задач большой размерности. В качестве метода решения данной задачи рассматривается модифицированная модель Голдберга. Модель Годберга рассматривается с несколькими кроссоверами и наиболее эффективной мутацией. При определенных параметрах (большое количество особей и повторов) модифицированная модель Голдберга получает решение за достаточно долгое время, поэтому в статье подробно анализируется один из подходов по уменьшению времени работы без потери точности. Так как аналитически произвести расчеты крайне затруднительно и практически невозможно в работе был поставлен вычислительный эксперимент. В результате вычислительного эксперимента, в таблицах приводится сравнение эффективности работы модифицированной модели Голдберга после применения HT технологии. Применение HT технологии приводит к существенному уменьшению временных затрат. Статья опубликована в рамках реализации программы Международного Форума «Победный май 1945 года».

Ключевые слова: одноточечный кроссовер, двухточечный кроссовер генетический алгоритм, модифицированная модель Голдберга, мутация, минимаксная задача, теория расписаний, особь, поколение, hyper-threading

05.13.01 - Системный анализ, управление и обработка информации (по отраслям) , 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Ключевые слова: двухточечный кроссовер, гибридный алгоритм, модифицированная модель Голдберга, мутация, минимаксная задача, теория расписаний, сильная мутация, особь, поколение

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

В статье рассмотрено применение модифицированного двухэтапного генетического алгоритма к решению задачи коммивояжера. Задача коммивояжера является NP-сложной. При количестве городов 66 и более ее невозможно решить методом полного перебора. Для проверки предложенного подхода к решению рассматривается граф с 51 вершиной. На первом этапе работает модифицированная модель Голдберга с небольшими значениями параметров для получения первого поколения второго этапа с лучшими показателями, чем при случайном формировании особей. Второй этап работает с увеличенными значениями параметров генетического алгоритма. Эти значения варьируются от эксперимента к эксперименту, результаты которых представлены на диаграммах. Также результаты работы двухэтапного алгоритма сравниваются с результатами одноэтапного алгоритма. Используется модифицированная модель Голдберга генетического алгоритма. В генетическом алгоритме применяется путевое представление маршрута коммивояжера с двухточечным упорядоченным кроссовером и «жадной» мутацией. Результаты экспериментов показали эффективность предлагаемого подхода. Модифицированный двухэтапный алгоритм позволяет получить решение близкое к оптимальному.

Ключевые слова: задача коммивояжера, генетический алгоритм, модель Голдберга, кроссовер, мутация, особь, маршрут, гамильтонов цикл, матрица расстояний

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

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

Ключевые слова: одноточечный кроссовер, генетический алгоритм, модифицированная модель Голдберга, мутация, минимаксная задача, теория расписаний, элитная особь, особь, поколение

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

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

Ключевые слова: одноточечный кроссовер, генетический алгоритм, модифицированная модель Голдберга, мутация, минимаксная задача, теория расписаний, элитная особь, особь, поколение

05.13.18 - Математическое моделирование, численные методы и комплексы программ