ПОИСК Статьи Чертежи Таблицы Алгоритмические способы повышения эффективности метода комбинирования эвристик из "Информационная поддержка наукоемких изделий. CALS-технологии " Приведенные далее результаты численных экспериментов в случае марщру-тизации транспортных средств получены в тестовых задачах VRP 37 и VRP 80. Исходные данные для VRP 80 число узлов транспортной сети w = 80, число заказов g = 25, число узлов - источников продуктов г = 40, число серверов (единиц транспортных средств) т = 12, число типов перевозимых продуктов р = 2 (для VRP 37 соответственно и = 37, g = 10, z = 20, т= I2,p = 2). [c.230] В известных генетических алгоритмах при решении сложных задач большой размерности типичным является характер приближения к решению, в котором скорость улучшения значений целевой функции в процессе поиска экстремума постепенно уменьшается и может наступить стагнация популяции при значениях целевой функции, существенно отличаюшихся от оптимальных. Поэтому необходимо использовать различные способы как ускорения сходимости, так и преодоления стагнации на уровнях, далеких от экстремума. [c.230] Наиболее радикальным направлением преодоления ранней стагнации является применение многопопуляционных генетических алгоритмов и/или гибридных алгоритмов. [c.230] Схемы межпопуляционного обмена могут быть довольно разнообразными. Например, популяция с номером i передает своих к представителей в популяцию с номером i + 1 (последняя популяция при этом посылает своих представителей в первую популяцию). Чаще всего эти к представителей выбираются среди лучших экземпляров хромосом. Числа La. к могут варьироваться. [c.230] Под гибридным алгоритмом понимают сочетание алгоритмов двух типов первый тип представлен генетическим алгоритмом, ко второму типу отнесены алгоритмы локальной оптимизации, оперирующие единственной хромосомой (или популяцией хромосом, но без применения кроссовера). Поэтому гибридные алгоритмы назьшают также локально-генетическими. [c.231] Здесь К - глубина локального поиска, т.е. максимально допустимое число идущих подряд безуспешных попыток улучшить результат локального поиска R - размер макромутации, т.е. число изменяемых генов на данном шаге локального спуска. [c.231] Для иллюстрации преимуществ локально-генетического подхода сравнивались результаты решения задач с помощью генетических алгоритмов простого однопопуляционного (ОГА), многопопуляционного (МГА) и локально-генетического алгоритма (ЛГА). Сопоставление ОГА и ЛГА на задаче синтеза расписаний N21 при ограничении числа вычислений целевой функции Р в проводимых экспериментах значением 10 000 дало значения Р, приведенные в табл. 2.1, где N - размер популяции. Отметим, что в этой задаче синтеза расписаний Р есть цена расписания, которая минимизируется. [c.232] В то же время десять вариантов решения той же задачи N105 с помощью ЛГА при использовании локально-генетического алгоритма LGA1 сК = 120 и размером популяции 13 дало значения целевой функции Г в диапазоне 21 956.. .22 053 со средним значением 22 005. [c.232] Эффективность локально-генетических алгоритмов существенно зависит от ряда факторов. Основными среди них следует назвать используемый набор эвристик, вероятности их выбора в операторах мутации и формирования начального поколения, глубину локального поиска, размер макромутаций. [c.232] Управление эвристиками включает, во-первых, формирование рабочего набора эвристик из числа возможных сочетаний правил для разных частей задач, во-вторых, выбор вероятностей использования эвристик в процессе решения задачи. [c.232] Часто первоначальное включение эвристик в рабочий набор выполняется по субъективным предпочтениям. Однако в выбор эвристик можно вложить и объективное содержание. В частности, можно руководствоваться результатами применения приведенного далее алгоритма А , т.е. сравнением результатов автономного использования эвристик (см. такие результаты для задачи N25 в табл. 2.2, а для задачи - в табл. 2.3). [c.233] Если прогнозируется получение решения с нарушением ограничений, приводящим к незначительным штрафам, то отбор эвристик в задачах синтеза расписаний следует проводить, ориентируясь на значения 2 (табл. 2.2). В противном случае нужно усиливать роль эвристик с временной ориентацией. В задаче N25 прогноз благоприятен, и в набор были включены эвристики Э , и Э . При этом целесообразно для более перспективных эвристик увеличивать вероятности их выбора в операторах мутаций и генерации начального поколения. В экспериментах в случае задачи N25 вероятности выбора эвристик Э,, Э , и взяты в отношениях 2 1 1 4. При этом средний по нескольким вариантам результат применения простого генетического алгоритма оказался Е = 5371. вто время как равновероятное использование всех восьми эвристик дало F = 5536. [c.233] Аналогичные результаты получены и при решении задачи N105. Равновероятное применение всех восьми эвристик в простом генетическом алгоритме дало после 100 смен поколений значение целевой функции Р, усредненное по нескольким вариантам расчета, равное 22 607, а использование набора из трех перспективных эвристик - значение 22 424. [c.233] Таким образом, необходимо иметь алгоритм определения рациональных значений вероятностей использования эвристик в процедурах мутации и генерации начального поколения. На роль такого алгоритма претендуют следующие варианты. [c.234] Как показали результаты численных экспериментов, в случае синтеза расписаний этот алгоритм можно использовать в задачах с нежесткими ограничениями, причем при выборе штрафы за нарушение ограничений в Р. учитываться не должны. [c.234] Ау Самонастраивающийся алгоритм, при котором q. для Л-го поколения определяется по формуле (2.6), в которой /, подсчитано по лучшей хромосоме к - 1)-го поколения. [c.234] Результаты расчетов целевой функции с помощью алгоритма Л соответствующие использованию каждой эвристики в отдельности, приведены в табл. 2.3, где Р. и 2 - значения целевой функции при использовании г-й эвристики с учетом и без учета штрафов соответственно. [c.234] Вернуться к основной статье