Содержание к диссертации
Введение
1. Современное состояние проблемы определения оптимальных маршрутов прокладки газопроводов 9
1.1. Подход к поиску оптимального маршрута прокладки газопровода как к оптимизационной задаче 9
1.2. Модели представления данных и алгоритмы для поиска оптимального маршрута прокладки газопровода 11
1.3. Выводы по первой главе и постановка задачи исследования 22
2. Прогнозирование развития сети газопроводов газораспределительной организации на примере г.Воронежа 25
2.1. Структура газопроводов 25
2.1.1. Распределительные сети высокого давления 27
2.1.2. Распределительные сети среднего давления 30
2.1.3. Распределительные сети низкого давления 33
2.2. Методика прогнозирования развития сети газопроводов газораспределительной организации на основе технологий нейронных сетей 36
2.3. Прогноз развития сети газопроводов управление Воронеж-газ 41
2.4. Выводы по второй главе 46
3. Построение оптимального маршрута прокладки трассы газопровода с учетом нескольких влияющих факторов 47
3.1. Карты стоимости 47
3.1.1. Метод экспертных оценок 50
3.1.2. Методы, основанные на анализе имеющихся данных 52
3.2. Модели интеграции поверхностей стоимости влияющих факторов 54
3.3. Построение поверхности накопленной стоимости 57
3.4. Алгоритм расчета маршрута с наименьшей стоимостью по поверхности накопленной стоимости 66
3.5. Выводы по третьей главе 75
4. Использование эволюционных алгоритмов для выбора оптимального маршрута прокладки трассы газопровода 76
4.1. Особенности использования эволюционных алгоритмов для выбора оптимальной трассы 76
4.2. Применение эволюционных алгоритмов для выбора оптимальной трассы 84
4.3. Выводы по четвертой главе 93
5. Реализация программы построения оптимального маршрута прокладки трассы газопровода 94
5.1. Средства создания программы построения оптимального маршрута прокладки трассы газопровода 94
5.2. Структура программы построения оптимального маршрута прокладки трассы газопровода 96
5.3. Выводы по пятой главе 110
Выводы 111
Литература 113
Приложение
- Модели представления данных и алгоритмы для поиска оптимального маршрута прокладки газопровода
- Методика прогнозирования развития сети газопроводов газораспределительной организации на основе технологий нейронных сетей
- Модели интеграции поверхностей стоимости влияющих факторов
- Применение эволюционных алгоритмов для выбора оптимальной трассы
Введение к работе
Актуальность темы. Газоснабжение, представляющее собой совокупность процессов транспортировки, распределения и потребления природного газа, формирует энергетическую основу экономики. Газовые сети — это капиталоемкие проекты, при проектировании которых одной из основных задач является обеспечение функционирования в течение длительного периода времени.
Газопроводы затрагивают больше субъектов инфраструктуры, чем другие технические комплексы и сооружения. До последнего времени маршрут прокладки газопроводов выбирался вручную на топографических картах. Выбор маршрута — это первый существенный шаг в процессе проектирования и строительства газопровода, этот шаг может оказать значительное влияние на строительство и функционирование газопровода в целом, поэтому оптимизация этого процесса может существенно повлиять на финансовые и материальные ресурсы, необходимые для строительства газопровода. Таким образом, эффективный процесс выбора маршрута прокладки важен для минимизации экономических потерь.
Необходимость выбора маршрута прокладки при проектировании газопроводов определяет, в свою очередь, необходимость стратегического планирования, предварительной оценки и эффективной организации управленческих работ. Сам процесс выбора оптимального маршрута прокладки неразрывно связан с эффективным сбором, хранением и анализом пространственных данных.
В связи с этим становится очевидным, что для эффективного выбора маршрута прокладки газопровода необходимо прогнозирование развития существующих газовых сетей, разработка методов и алгоритмов, позволяющих производить многокритериальную оптимизацию маршрута прокладки, и использование современных достижений геоинформационных технологий.
Таким образом, определение оптимального маршрута прокладки газопровода является актуальной научно-технической задачей.
Цель работы: Определение оптимального маршрута прокладки газопровода.
Для достижения указанной цели решались следующие задачи исследования:
анализ состояния и разработка методики прогнозирования развития газораспределительных сетей;
разработка метода определения относительной значимости факторов, влияющих на прокладку газопровода;
разработка методов, позволяющих производить одновременную оптимизацию трасс прокладки газопроводов по нескольким критериям;
разработка алгоритма поиска оптимального маршрута прокладки газопровода;
разработка программы расчета оптимального маршрута прокладки газопровода, реализующей полученные методы и алгоритмы.
Научная новизна. Предложена методика прогнозирования развития газораспределительных сетей, использующая неиросетевые технологии. На примере г. Воронежа получен прогноз развития газораспределительных сетей на 5 лет.
Разработан метод определения весовых коэффициентов карт стоимости факторов, влияющих на прокладку газопровода, в основе которого лежат метод Байеса и метод экспертных оценок. В отличие от известных предложенный метод позволяет наиболее полно учесть всю совокупность факторов, в том числе наличие застройки, характеристики грунта, блуждающие токи, наличие грунтовых вод и др.
Для интеграции поверхностей стоимостей влияющих факторов разработана новая модель с использованием нечеткой логики.
Разработан алгоритм расчета поверхности накопленной стоимости, учитывающий исходные карты стоимости, топографию местности, направление прокладки и ограничения существующей застройки.
Разработан алгоритм поиска оптимального маршрута газопровода на основе поверхностей накопленной стоимости. Предложенный алгоритм реализует целевую функцию минимальной стоимости прокладки газопровода; в качестве исходных данных используется поверхность накопленной стоимости и поверхность направлений газопроводов.
Разработана программа расчета оптимального маршрута прокладки газопровода, предоставляющая инструментарий для проектирования газопроводов. Программа позволяет вычислять коэффициенты относительной значимости карт влияющих факторов, задавать произвольные функции интеграции карт влияющих факторов, строить оптимальный маршрут и маршруты, близкие к оптимальному, и выполнять визуализацию результатов.
Достоверность результатов. Теоретическая часть работы базируется на методах теории вероятностей и математической статистики, топологии, теории графов и эволюционных вычислений. Основные допущения, принятые при построении алгоритмов, широко используются в работах других авторов.
Практическое значение и реализация результатов. Практическое значение диссертации состоит в получении универсальных по характеру методик, системно увязывающих факторы, влияющие на стоимость прокладки газопровода. Они могут быть использованы в производственной практике предприятий газоснабжения, водоснабжения и водоотведения.
Результаты диссертационной работы используются в проектной практике управления Воронежгаз при обосновании выбора трассировки прокладки сетей газоснабжения.
На защиту выносятся:
методика прогнозирования развития газораспределительных сетей;
метод определения весовых коэффициентов карт стоимости факторов, влияющих на прокладку газопровода;
модель с использованием нечеткой логики для интеграции поверхностей стоимости влияющих факторов;
алгоритм расчета поверхности накопленной стоимости;
алгоритм поиска оптимального маршрута газопровода;
программа расчета оптимального маршрута прокладки газопровода.
Апробация работы. Основные положения и результаты работы
докладывались и обсуждались на региональном межвузовском семинаре «Моделирование процессов тепло- и массообмена» (Воронеж 2007—2009 гг.), на 62-й—64-й научных конференциях и семинарах Воронежского государственного архитектурно-строительного университета (Воронеж 2007— 2009 гг.).
Публикации. По материалам диссертационной работы опубликовано 5 научных работ общим объемом 34 стр. Личный вклад автора составляет 20 стр.
Три статьи опубликованы в изданиях, включенных в перечень ВАК ведущих рецензируемых журналов, в которых должны быть опубликованы основные научные результаты диссертации: «Приволжский научный журнал», «Научный вестник Воронежского государственного архитектурно-строительного университета. Строительство и архитектура».
В статьях, опубликованных в рекомендованных ВАК изданиях, изложены основные результаты диссертации: в работе [37] приведен метод определения весовых коэффициентов карт стоимости факторов, влияющих на прокладку газопровода; в работе [39] опубликован алгоритм, позволяющий рассчитывать близкие к оптимальному маршруты прокладки; в работе [38] представлены алгоритм расчета поверхности накопленной стоимости, корректно учитывающий топографию местности, и алгоритм поиска оптимального маршрута газопровода по поверхности накопленной стоимости.
Объем и структура диссертации. Диссертация состоит из введения, пяти глав, основных выводов и списка литературы.
Диссертация изложена на 125 страницах и содержит 88 страниц машинописного текста, 58 рисунков, список используемых источников из 115 наименований и приложение.
Модели представления данных и алгоритмы для поиска оптимального маршрута прокладки газопровода
Для решения задачи определения оптимального маршрута прокладки газопровода исходные данные представляются в виде одной из двух пространственных моделей - векторной или растровой. Исходные данные, такие как водные преграды, дорожная сеть и данные о почве, типично хранятся в векторном виде, в то время как топографические данные обычно представлены в растровом виде [87]. Для анализа данных, часть которых представлена в векторном виде, а часть - в растровом, необходимо привести все данные в один формат.
Сетевая модель может быть определена как граф, состоящий из ребер, представляющих собой линейные каналы потока, и вершин, представляющих собой точки соединения [90]. Другими словами, сеть принимает вид ребер, соединяющих пары вершин. Для использования в задаче поиска оптимального маршрута ребрам ставится в соответствие направление и сопротивление, определяющее стоимость движения по сети. Поскольку сети используют простейшую структуру вершины-ребра, то, с учетом того, как хранятся данные, векторная сеть уже имеет топологическую структуру, объединяющую все элементы. Остается только реализовать факторы, влияющие на стоимость движения, как таблицы атрибутов для ребер и вершин. Направления - это явная часть топологии векторной сети. В практических задачах вершины и узлы индексируются по координатам. Вершины и узлы, вместе со специальными узлами сети, такими как «остановки, центры, повороты», формируют модель сети в векторных геоинформационных системах. Остановки могут быть пунктами доставки или складами, центры используются для распределения служб, повороты используются для определения направлений и потоков в сети. Характеристики любой системы, моделируемой в виде сети, должны абстрагироваться в форму, которая может быть представлена одним из этих элементов. В [59, 70, 83] детально описан процесс нахождения пути, оптимизируемого по нескольким критериям.
Алгоритмы нахождения пути делятся на две основных категории -матричные алгоритмы и алгоритмы построения дерева [55, 92, 104], из которых последние наиболее часто используются в геоинформационных системах. Матричные алгоритмы находят кратчайшее расстояние между всеми парами узлов итеративными шагами, убирая наименее подходящие узлы [59]. Этот подход основывается на том, что сеть можно представить как матрицу. Алгоритмы построения деревьев ищут кратчайший путь от исходного узла до других узлов, продуцируя дерево кратчайших путей с ветвями, расходящимися из исходной точки [86]. Наиболее часто используемая методика построения дерева - это классический метод, разработанный Дейкстрой [69] и многие его улучшения и модификации для специфических применений. Для нахождения пути алгоритм строит древовидную структуру данных, которая представляет собой специфические пути в сети. Часто это называют поиском в ширину, который захватывает максимальное количество узлов перед углублением в дерево [70].
Растровое моделирование сетей использует совершенно другой подход, нежели топографически связанная векторная модель. Ячейки сетки являются аппроксимацией точных форм линий сети. В отличие от векторной модели, в которой направления движения заданы явно, в растровой модели направления указываются неявно. Атрибуты вершин и ребер хранятся в отдельном слое, причем для каждого атрибута выделяется отдельный слой. В результате сеть, использующая растровую модель, обычно состоит из достаточно большого числа слоев. Даже если это явно не указано, сетка, образуемая растровой моделью, представляет собой граф. Граф строится из тех соображений, что каждая ячейка сетки связана с восемью соседними. Поскольку у сетки есть определенное разрешение, ячейки только приблизительно повторяют точные формы сети. Алгоритм поиска пути по растровой модели близок к алгоритму на векторной сетке. Для нахождения пути с наименьшей стоимостью необходимо рассчитать поверхность накопленной стоимости, основывающуюся на стоимости движения по поверхности от ячейки к ячейке. С. Tomlin [103] описывает процесс движения от исходной точки к конечной в терминах картографической алгебры как функцию распространения, использую в качестве аналогии волны и рефракцию. Аналогичный подход использовал D. Douglas [71].
Исторически сложилось, что анализ и обработка растровых данных отличаются более высоким быстродействием, в то время как работа с векторными данными отличается более высокой точностью [84]. В прошлом, исследования на уровне ландшафта велись с использованием растровых методов, поскольку вычислительные мощности не позволяли использовать векторные методы. R. Lunetta рассмотрел погрешности, связанные с интеграцией данных дистанционного зондирования в геоинформационные системы [89]. S. Walsh количественно оценил погрешности от наложения данных дистанционного зондирования на данные ГИС [107]. Были опубликованы несколько работ, посвященных погрешностям, возникающим при преобразовании данных из векторного формата в растровый и обратно [60, 105]. Большая часть этих работ была направлена на исследование преобразования областей в многоугольники и взаимного влияния размера и формы многоугольников и размеров ячейки в растровой модели данных [109].
Данные в растровой модели дискретны по своей природе, поэтому они не могут полностью представить непрерывные поверхности реального мира. Для того, чтобы увеличить точность при работе с растровой моделью, необходимо учитывать в расчетах значения, находящиеся вне центров ячеек. Это может быть осуществлено путем увеличения числа ячеек в шаблоне соседних ячеек. J. van Bemmelen предложил для этого использовать шаблон, состоящий из 32 ячеек [53]. Проблема при таком подходе заключается в том, что при рассмотрении шаблона из большого числа ячеек могут быть допущены ошибки при определении направления движения. Кроме того, трудности могут возникнуть при рассмотрении линейных объектов на анизотропных поверхностях. D. Douglas предложил метод, применимый для изотропных поверхностей, основывающийся на расчете дополнительных точек пересечения на границах ячеек сетки [71].
Кроме указанных методов, для повышения точности возможно использование деревьев квадрантов [106]. Однако, если ячейки дерева квадрантов слишком велики, то возможно возникновение существенных погрешностей [53].
В целом, в зависимости от разрешения сетки, растровые и векторные модели могут осуществлять одни и те же операции пространственного анализа. В обоих случаях поток либо от узла к узлу, либо от ячейки к соседней ячейке на сетке подвержен некоторому сопротивлению, определяющему направление и скорость потока. Отличается лишь представление сопротивления в модели.
Методика прогнозирования развития сети газопроводов газораспределительной организации на основе технологий нейронных сетей
Основная цель изучения временных показателей динамики развития газораспределительной сети заключается в прогнозировании их развития. Использование нейронных сетей в анализе временных рядов имеет смысл в тех случаях, когда исходный ряд представлен достаточно большим количеством переменных и необходимы как можно более точные результаты анализа [48].
Предварительный анализ исходного временного ряда показывает, что вероятность того, что он является детерминированным, весьма низка. Исходный ряд сформировался более чем за 50 лет и характеризуется достаточным периодом развития и отслеживания во времени и неустойчивыми колебаниями в рассматриваемом периоде. Все это затрудняет построение прогноза классическими методами прогнозирования [3, 14].
Была сформулирована задача анализа реального временного ряда: построение модели временного ряда, оценка адекватности этой модели и на основе наблюдаемых значений прогнозирование развития элементов газораспределительной сети г. Воронежа на 5 лет вперед.
Для реализации этой цели был использован механизм построения и обучения нейронной сети, моделирующей исходный временной ряд [45].
Искусственные нейронные сети - математические модели, построенные по принципам функционирования биологических нейронных сетей. Нейронная сеть представляет собой систему взаимодействующих искусственных нейронов. Ключевой особенностью искусственных нейронных сетей и одним из преимуществ над традиционными алгоритмами является возможность их обучения, в процессе которого нейронная сеть выявляет зависимости между входными и выходными данными [21].
Искусственный нейрон представляет собой единицу обработки информации, использующуюся в узлах искусственной нейронной сети. В модели нейрона можно выделить три основных элемента: 1. Связи, каждая из которых характеризуется своим синаптическим весовым коэффициентом. Каждый вес искусственного нейрона может принимать как положительные, так и отрицательные значения; 2. Сумматор, который производит суммирование взвешенных входных сигналов; 3. Функция активации, назначение которой состоит в ограничении амплитуды выходного сигнала нейрона.
Математическая модель нейрона может быть представлена следующими уравнениями: где Xj - входные сигналы; wkj - синаптические веса нейрона с индексом к; щ -линейная комбинация входных воздействий;/ - функция активации нейрона; Ьк - пороговая величина; у к — выходной сигнал нейрона.
В зависимости от способа преобразования сигнала и характера активации возникают различные виды нейронных структур. Структура нейронных сетей тесно связана с используемыми алгоритмами обучения [22]. Для прогнозирования была выбрана сеть с архитектурой многослойного персептрона (МП). Сеть такой архитектуры позволяет моделировать функции практически любой сложности. При прогнозировании применялись многослойные персептроны различной топологии, использующие различное количество входных, скрытых и выходных нейронов.
Многослойные сети характеризуются наличием одного или нескольких скрытых слоев. В скрытые слои входят так называемые скрытые нейроны, функция которых заключается в преобразовании сигналов между входом и выходом нейронной сети. Использование одного или нескольких скрытых слоев позволяет выделить статистики высокого порядка. Благодаря использованию дополнительных синаптических связей между нейронами и повышению уровня их взаимодействия, сети многослойной архитектуры позволяют выделять глобальные свойства данных. Пример сети с одним Наиболее важным свойством искусственных нейронных сетей является их способность к обучению на основе внешних данных. Обучение нейронной сети происходит посредством процесса корректировки синаптических весовых коэффициентов и пороговых величин.
Обучение многослойных персептронов происходит с помощью так называемого «обучения с учителем». При этом применяется алгоритм обратного распространения ошибки. При обучении этот алгоритм обрабатывает примеры из обучающего множества. Обработка происходит в несколько этапов.
Первым этапом является инициализация, при которой с помощью равномерно распределенных чисел со средним значением 0 производится установка начальных синаптических весовых коэффициентов и пороговых величин. Далее происходит подача примеров из обучающего множества в нейронную сеть. Каждый из обучающих примеров обрабатывается в два этапа, называемые прямым и обратным проходом.
При прямом проходе обучающий пример представляется в виде {х(п), d(n)}, где х(п) - входной вектор, a d{n) - желаемый выход нейронной сети. Производится послойный проход по нейронной сети в прямом направлении; при этом с помощью формул 2.15-2.18 вычисляются выходные сигналы сети и индуцированные локальные поля. Индуцированное локальное поле для нейрона j из слоя / рассчитывается по следующей формуле: где у \п) - выходной сигнал нейрона с номером /, расположенного в слое 1-І на итерации п; wlfl{n) - синаптический весовой коэффициент связи нейрона/ слоя / с нейроном і слоя 1-І.
Модели интеграции поверхностей стоимости влияющих факторов
Для поверхностей стоимости влияющих факторов могут использоваться различные модели. Рассмотрим некоторые из них: 1. Булева модель
В булевой модели входные карты интегрируются с использованием логических операторов, таких как И, ИЛИ, исключающее ИЛИ и НЕТ. Несмотря на то, что булевы операторы являются простыми и исключительно быстрыми при исполнении, для этой модели характерен ряд проблем. Так как все входные карты влияющих факторов имеют один и тот же вес, нет возможности ввести разные приоритеты для разных точек на карте. Эта модель может применяться для карт ограничений, для которых характерно строгое задание проходимости местности, однако для карт влияющих факторов с различными весовыми коэффициентами она неприменима. 2. Взвешенная модель
В этой модели карты факторов интегрируются с использованием следующего уравнения:
где Wj — весовой коэффициент /-й карты факторов; Уу- - значение у -го пространственного элемента на /-й карте влияющих факторов; Vj - итоговое значениеу -го пространственного элемента на выходной карте.
При сравнении взвешенной и булевой моделей, несложно отметить, что взвешенная модель обладает большей гибкостью и дает возможность учитывать весовые коэффициенты карт влияющих факторов и величину каждого пространственного элемента на этих картах. С учетом указанных характеристик, эта модель может использоваться в анализе моделей интеграции при расчете поверхности стоимости. 3. Модель с использованием нечеткой логики
В модели с использованием нечеткой логики значение каждого пространственного элемента карт факторов и весовые коэффициенты карт факторов представляют собой величину принадлежности к нечеткому множеству [29]. Величина принадлежности к нечеткому множеству должна лежать в диапазоне от 0 до 1. Однако на величину принадлежности не накладывается более никаких ограничений. Эти величины обозначают степень принадлежности к множеству на базе субъективных суждений, то есть каждая величина представляет собой пригодность пространственного элемента для прокладки газопровода, определенную на основе выбранных критериев [1].
Для интеграции карт факторов применяются операции, такие как нечеткое И, нечеткое ИЛИ, нечеткое произведение, нечеткая сумма и нечеткий гамма-оператор. Нечеткое И подобно обычным операциям в классической теории множеств:
Операция нечеткого И выделяет минимальное значение в одном узле выходной карты и создает карту консервативной оценки влияющих факторов. Эта операция используется, когда существуют два или более факторов, которые могут помочь в решении задачи. Однако эта операция обладает недостатками, такими как невозможность использования значений всех влияющих факторов, из-за которых она не использовалась. Нечеткое ИЛИ также подобно обычным операциям в классической теории множеств:
Нечеткая операция ИЛИ выделяет максимальное значение в одном узле выходной карты, и создавая оптимистичную карту оценки влияющих факторов. Нечеткий оператор ИЛИ используется, когда имеется достаточное число положительных факторов в области изучения.
При использовании нечеткой операции ИЛИ, так же как и при использовании нечеткой операции И, в определении итоговой величины используется только один из влияющих факторов, что неприемлемо.
Операция нечеткого произведения умножает величины принадлежности факторов входной карты: где \i - единичное значение в выходной карте; \i} - вес z -й карты влияющих факторов.
Поскольку все величины принадлежности лежат в интервале [0,1], в результате данной операции величины принадлежности неизбежно уменьшаются. Эта операция используется, когда входные карты факторов ослабляют влияние друг друга.
Операция нечеткой суммы является дополнительной к операции нечеткого произведения: где \i - единичное значение в выходной карте; р,; - вес /-й карты влияющих факторов.
При использовании операции нечеткой суммы величины принадлежности стремятся к 1, а эффект влияния карт факторов друг на друга увеличивается. Благодаря этим свойствам, этот оператор использовался при анализе методов интеграции карт стоимости влияющих факторов.
Применение эволюционных алгоритмов для выбора оптимальной трассы
Для операторов вероятностного изменения и рекомбинации создается временное множество потенциальных решений, состоящее из решений, выбранных из общего набора в результате отбора и предназначенных для преобразования эволюционными операторами с целью формирования нового набора потенциальных решений.
Оператор рекомбинации производит: 1. Формирование пар, состоящих из отобранных потенциальных решений. Пары формируются случайным образом в соответствии с вероятностью выполнения оператора рекомбинации; 2. Выбор точки рекомбинации пары решений; 3. Формирование результатов.
Оператор скрещивания классического эволюционного алгоритма подразумевает, что используется бинарное представление аргументов и что решения, представленные векторами, в парах имеют фиксированную длину. Однако в случае, когда решение представляет собой маршрут прокладки газопровода, все решения могут иметь различную длину. Это накладывает определенные ограничения на действие оператора рекомбинации. Для рекомбинации двух векторов-маршрутов различной длины необходимо, чтобы в паре векторов было как минимум одно общее значение (представляющее собой узел в регулярной сетке, по которой идет трассировка газопровода), не считая начальной и конечной точки маршрута. В случае, если общих значений в векторах больше одного, предлагается случайно выбрать один из них в качестве точки рекомбинации решений. Рассмотрим действие предложенного оператора рекомбинации на базе пары решений (см. рис. 4.5, 4.6):
Первый вектор представляет собой маршрут, состоящий из следующих ячеек: 27, 28, 29, 42, 55, 67, 79, 80, 81, 82; второй состоит из следующий ячеек: 27, 39, 52, 65, 54, 55, 56, 57, 70, 82.
Кроме начальной и конечной точек прокладки, в обоих векторах есть общая ячейка с индексом 55.
Для формирования результатов в рамках оператора рекомбинации предлагается использовать метод одноточечного скрещивания [39]. Пусть потенциальное решение 1 содержит L\ элементов, а потенциальное решение 2 — L2 элементов. Обозначим позицию элемента, являющегося точкой скрещивания в решении 1 как /ь а точку скрещивания в решении 2 как /2. В результате действия метода одноточечного скрещивания будет получена следующая пара решений: 1) решение, которое на позициях [1 .. 1{\ состоит из элементов первого исходного решения, а на позициях [/j+1 .. Lr-h+l\\ - из элементов второго исходного решения; 2) решение, которое на позициях [1 .. /2] состоит из элементов второго исходного решения, а на позициях [/2+1 .. Lrh+k] - из элементов первого исходного решения.
Действие одноточечного метода скрещивания на векторах-решениях различной длины проиллюстрировано на рис. 4.7:
В случае, когда элементы вектора представляют собой номера пространственных элементов, а сам вектор представляет собой маршрут, действие оператора рекомбинации может быть проиллюстрировано следующим примером (см. рис. 4.8): Точкой скрещивания выбрана общая ячейка с индексом 55. В результате применение одноточечного метода скрещивания, получены следующие векторы:
Вектор 1, состоящих из следующих ячеек: 27,28,29,42,55,56,57,70; и вектор 2, состоящих из следующих ячеек: 27, 39, 52, 65, 54, 55, 67, 79, 80, 81, 82. Для улучшения производительности полученного эволюционного алгоритма можно видоизменить оператор рекомбинации следующим образом: точки скрещивания можно искать не только как совпадающие узлы сетки, но и как соседние узлы сетки (см рис. 4.9).
В результате работы оператора рекомбинации в маршруте могут образовываться циклы, что недопустимо. Для удаления циклов предлагается удаление элементов из решений между узлами-дубликатами.
Оператор вероятностного изменения используется для внесения случайных изменений в потенциальные решения для достижения разнообразия множества решений, а также для предотвращения преждевременной сходимости решений. В классическом эволюционном алгоритме оператор вероятностного изменения с некоторой вероятностью меняет элемент в бинарном представлении решения на противоположный. Однако в случае, когда решение представляет собой маршрут, такой оператор неприменим, так как решение после применения к нему оператора вероятностного изменения может не являться непрерывным маршрутом от начальной точки до конечной. Для применения оператора вероятностного изменения к потенциальным решениям предлагается использовать следующий алгоритм:
