Разработка и исследование алгоритмов решения транспортных задач с использованием генетических методов

В третьей главе представлены математическая модель ТЗ с ограничением по времени и новый ГА решения данной задачи, позволяющий работать как со статическими, так и с динамическими запросами клиентов. Математически ТЗ с ограничением по времени можно представить в виде графа G = (N, A), где: N – множество вершин, соответствующих набору клиентов (customers) (вершины 1, 2, …, n) и исходным депо (depot), в которых начинают и заканчивают свой маршрут все автомобили (вершины 0 и n+1); A – набор дуг, соединяющих вершины графа. Введем обозначения: C  – множество клиентов, |C| = n; i, j – i-й и j-й клиенты, , ; (i, j) A – дуга, соединяющая i-ю и j-ю вершины графа; di – спрос i-го клиента; tij  – время перемещения по дуге (i, j), состоящее из времени обслуживания клиента i и времени перемещения автомобиля от клиента i к клиенту j; cij – стоимость перемещения автомобиля от клиента i к клиенту j; V  – количество идентичных автомобилей грузоподъемностью q; k – k-й автомобиль, ; [ai, bi] – «временное окно» (time window) – промежуток времени, в течение которого должен быть обслужен i-й клиент; Sik – время прибытия k-го автомобиля к i-му клиенту; время отправления из депо для всех автомобилей равно 0 (т.е. S0k = 0 ); Xijk – переменная, принимающая значения {0, 1} и характеризующая направление движения автомобиля: Xijk = 1 – от клиента i к клиенту j, Xijk = 0 – в обратном направлении. С учетом этих обозначений математическая формулировка ТЗ с ограничением по времени такова: необходимо минимизировать целевую функцию (1) при ограничениях (2)-(9): (1) (2) (3) (4) (5) (6) (7) (8) (9) ЦФ (1) определяет цену всех маршрутов всех транспортных средств (общая цена транспортного плана). Ограничение (2) полагает, что каждый клиент обслуживается только одним транспортным средством и только один раз. Ограничение (3) определяет, что транспортное средство не может обслужить больше клиентов, чем позволяет его грузоподъемность. Ограничение (4) означает, что каждый автомобиль покидает депо один раз. Ограничение (5) показывает, что автомобиль может покинуть вершину h, только если он прибыл в эту вершину. Аналогично ограничению (4), ограничение (6) означает, что все транспортные средства возвращаются в депо, причем один раз. Это ограничение следует из ограничений (4) и (5). Ограничение (7) означает что, если автомобиль движется из вершины i в j, то время прибытия автомобиля в j не может быть меньше суммы времени прибытия автомобиля в пункт i (Sik) и времени движения автомобиля из пункта i в пункт j (tij). Ограничение (8) – это ограничение по времени, прибытие автомобиля к клиенту должно быть в пределах временного окна. Основной особенностью разработанного алгоритма является использование дополнительного оператора мутации при «застаивании» процесса поиска, т.е. дополнительный оператор не используется в регулярном цикле работы алгоритма, а применяется лишь в том случае, когда лучшее значение ЦФ в популяции решений не изменялось в течение определенного (заранее заданного) количества итераций (Countst). Алгоритм заканчивает свою работу, если выполнено заданное максимальное количество итераций (Nit) или если значение счетчика «застаивания» процесса поиска достигло определенного значения, рассчитываемого исходя из максимального количества итераций. Разработаны и подробно описаны основные ГО алгоритма. Предложен новый оператор кроссинговера (ОК), который позволяет получать из N решений-родителей одно новое решение. Разработанный ОК построен таким образом, что в качестве строительных блоков используются маршруты транспортных средств. Поскольку для оценки подобия решений-потомков с решениями-родителями (а также подобия решений в популяции) в теории ГА используют понятие шаблон (схема) решения, то для данной ТЗ шаблоном решения будут являться закрепленные в решении маршруты транспортных средств. Согласно теории ГА лучшие маршруты (шаблоны) с точки зрения критерия оптимальности при применении ОК должны выживать с большой вероятностью. Поэтому для ОК определена вероятность выживания схемы при применении данного оператора с вероятностью кроссинговера . и – вероятности, нелинейно зависящие от количества закрепленных клиентов в маршрутах и от временных ограничений, накладываемых на решение задачи. Оценить вероятности и возможно только путем экспериментов. Теоретически оценена нижняя граница выживаемости шаблонов решения в зависимости от параметров ОК и количества закрепленных маршрутов в шаблоне . где α, β и N – параметры ОК; γ – количество закрепленных маршрутов в шаблоне. Эксперименты и теоретические расчеты показали, что для выживания, с вероятностью 80%, коротких шаблонов с одним закрепленным маршрутом, нужно применять ОК с вероятностью 30%. Для решения ТЗ с ограничением по времени были разработаны два оператора мутации (ОМ) ОМ_1 и ОМ_2. ОМ ОМ_1 в качестве понятия шаблон использует, как и ОК маршруты транспортных средств, закрепленные в решении. В ОМ ОМ_2 в качестве шаблонов используются клиенты закрепленные в определенном порядке на маршруте, это позволяет при помощи ОМ ОМ_2 получать существенно новые решения, расширяя область поиска при «застаивании» алгоритма. Согласно теории ГА при применении ОМ короткие шаблоны решений должны иметь большую вероятность выживания. Найдена вероятность выживания шаблонов при применении ОМ, ОМ_1 и ОМ_2. Данные вероятности соответственно равны: где, – вероятность применения ОМ_1; m и k – параметры ОМ_1; – количество закрепленных маршрутов в шаблоне. где – вероятность применения ОМ_2; K – параметр ОМ_2; N – количество клиентов в задаче; – количество закрепленных клиентов в маршрутах в шаблоне. Из приведенных выше формул, очевидно, что с увеличением порядка шаблона существенно снижается вероятность его выживания; это подтверждает факт большей вероятности выживания коротких шаблонов решений. В результате оценки временной сложности алгоритма, которая заключалась в оценке максимального времени выполнения каждого из ГО применяемого в разработанном ГА было найдено, что время работы алгоритма не хуже чем O(n3). Рассмотрен метод, позволяющий применять разработанный ГА к решению задач с динамическими запросами клиентов. Метод приводит задачу к серии статических подзадач, различающихся между собой начальными условиями и количеством клиентов, которых необходимо обслужить. Преимущество данного метода заключается в том, что основные ГО остаются неизменными, для них лишь вводится дополнительный модуль инициализации решения начальными условиями. Данный модуль включается в оператор инициализации, используемый во всех операторах кроссинговера и мутации; сами же операторы кроссинговера и мутации остаются без изменения. Предложен метод, позволяющий уменьшить время выполнения ГА за счет выполнения его многоядерной системой. Данный метод не требует применения специальной архитектуры генетического поиска и может применяться для простого последовательного ГА. Алгоритм работы многопоточной программы, реализующий данный метод, показан на рисунке 3. Рис. 3. Алгоритм работы многопоточной программы Рис.4.Работа потока

Похожие:

	Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа		Конспект урока с использованием информационно- коммуникативных технологий... Цель: Обобщить знания о материальных основах наследственности и изменчивости, закрепить знания по решению разных типов генетических...
	Отчет о научно-исследовательской работе, выполняемой по государственному... «Разработка алгоритмов для биоинформационного анализа комплексных метаболических и молекулярно-генетических сетей»		Законов, закономерностей математики и отвечающих им методов расчета. Формирование базовой Применение основных понятий и методов математической логики и теории алгоритмов для решения конкретных задач
	Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики		Грант нш-197. 2008. 4 Роль организации и экспрессии генетического... Работа была основана на использовании обширных генетических коллекций кафедры генетики и селекции спбгу с использованием генетических,...
	Урок информатики в 9 классе Тема «Оператор цикла с параметром» Цель урока: закрепление навыков решения задач с использованием циклических алгоритмов, знакомство с циклом «Для…»		Диплом «Исследование и сравнение способов решения логических задач» Практическая часть. Разработка сайта и тестирующей программы
	Тема урока: «Составление линейных программ для решения задач на применение... Повторить и обобщить знания о свойствах, типах, способах построения алгоритмов, этапах решения задач, о работе операторов input,...		Отчет №3 о научно-исследовательской работе по теме: «Грид-технологии» Разработка методов эффективного решения задач обработки, хранения, передачи и защиты информации
	Исследование методов обработки электроэнцефалографических сигналов... Работа выполнена в таганрогском технологическом институте Южного федерального университетана на кафедре Радиоприёмных устройств и...		Реферат: Шайдуров А. Г. Исследование и разработка некоторых графических... Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению...
	Разработка и исследование алгоритмов распознавания изображений на...		Связана с актуальной проблематикой обеспечения информатизации документооборота... Разработка проектного решения информационной системы электронного документооборота на предприятиях апк с использованием методов имитационного...
	Конспект урока с использованием проблемно-диалогической технологии Составление таблицы алгоритмов для решения простейших тригонометрических уравнений		Новосибирский государственный технический университет кафедра вычислительной техники Целью работы является: изучение методов решения задач нлп, особенностей, возникающих при использовании тех или иных методов решения;...