Содержание к диссертации
Введение
Глава 1. Анализ перегрузочных процессов морского порта 12
1.1. Описание перегрузочных процессов в морских портах 12
1.2. Характеристика и особенность перегрузочных процессов в морских портах 14
1.3. Обзор моделей управления перегрузочными процессами морского порта...
1.3.1. Модели управления организационными системами 19
1.3.2. Модели управления перегрузочными процессами в морских портах Вьетнама 23
1.3.3. Модель транспортной задачи и ее виды
1.4. Решение многоиндексной транспортной задачи с помощью эволюционных методов 29
1.5. Информационная система управления перегрузочными процессами морского порта 34
1.6. Постановка задачи исследования 36
Глава 2. Повышение эффективности управления перегрузочными процессами морского порта на основе системного анализа 40
2.1. Системный анализ перегрузочных процессов 40
2.2. Формирование системы критериев
2.2.1. Мониторинг качества перегрузочных процессов 49
2.2.2. Описание системы критериев 51
2.2.3. Формирование семантической модели перегрузочных процессов
2.3. Модель управления перегрузочными процессами г...: 55
2.4. Разработка граф-модель перегрузочных процессов 56
2.5. Анализ факторов, влияющих на перегрузочные процессы морских портов СРВ 59
Глава 3. Математическое моделирование управления перегрузочными процессами
3.1. Разработка модели управления перегрузочными процессами 62
3.2. Метод решения задач 64
3.3. Алгоритм решения поставленной задачи 66
3.3.1. Общая схема генетического алгоритма 66
3.3.2. Кодирование решений 68
3.3.3. Модели формирования начальной популяции 69
3.3.4. Процедура выбора особей для генетических операторов 72
3.3.5. Процедура скрещивания 72
3.3.6. Процедура мутации 3.4. Процедура создания новой популяции 78
3.5. Применение гибридного генетического алгоритма 79
3.6. Аппробация алгоритма алгоритма и результаты вычислений 81
Глава 4. Решение прикладной задач на основе предложенных алгоритмов 89
4.1. Описание прикладной задачи 89
4.2. Настройки генетического алгоритмы для решения поставленной задачи 92
4.3. Информационная система управления перегрузочными процессами морского порта Хайфон (ИСУПП)
4.3.1. Разработка архитектуры информационной системы управления перегрузочными процессами морского порта 93
4.3.2. Разработка ИСУПП 96
4.3.3. Структура программы 96
4.3.4. Функциональная модель 98
4.4. Программа реализации информационной системы управления перегрузочными процессами порта Хайфон 101
4.5. Проверка адекватности ИСУПП порта Хайфон 106
Заключение 112
Библиографический список использованной литературы
- Модели управления организационными системами
- Формирование системы критериев
- Алгоритм решения поставленной задачи
- Информационная система управления перегрузочными процессами морского порта Хайфон (ИСУПП)
Введение к работе
Актуальность темы. В 2010 г. на долю морского транспорта Вьетнама приходилось более 90% объема экспортно-импортных перевозок страны. Эффективность работы морского транспорта во многом зависит от работы морских портов, в связи с чем в настоящее время во Вьетнаме широко развертывается работа по строительству и развитию сети морских портов. Особое внимание уделяется внедрению новейших технологий, расширению и модернизации действующих портов, строительству глубоководных и перевалочных портов международного масштаба для обслуживания крупных судов.
В настоящее время требуется значительное ускорение транспортного процесса и снижение затрат на перевозки. Поэтому большое значение в решении стоящих перед морскими портами задач имеет совершенствование организации управления перегрузочным процессом, проводимое в портах по линии оптимизации режима работы. Такая постановка вопроса особенно актуальна для оперативного управления перегрузочными процессами, так как именно в этой области эксплуатационной работы имеются наибольшие возможности оптимизации плановых и управленческих решений, что обеспечивает повышение эффективности и пропускной способности портов. В решении этой задачи важная роль принадлежит проблеме оперативного управления по перевалке грузов с применением информационных технологий.
Большой вклад в решение вопросов совершенствования организации деятельности и перегрузочных процессов морских портов, повышения эффективности их работы внесли российские ученые В.З. Ананьина, Л.Д. Ветренко, А.С. Фролов, А.Р. Магамадов, Н.Ф. Лазарев, А.В. Степанец, Н.Е. Воевудский, Э.П. Громовой, М.М. Горбатый, А.А. Смехов и др. Важные исследования выполнены вьетнамскими учеными с целью развития системы морских портов и повышения уровня организации работы флота: Нгуен Чонга, Нгуен Као Тханг, Данг Ван Уи, Нгуен Нгок Хуэ и др. Вопросам совершенствования информационных систем управления деятельностью морского порта посвящены работы В.З.Ананьиной, Л.Д.Ветренко, Е.Н.Воевудского, А.Е.Суколенова, А.С.Фромова, Е.П. Громовой, А.Р.Магамадова, Данг Ван Уи, Нгуен Нгок Хуэ и др.
Вместе с тем, морские порты Вьетнама под руководством государственных предприятий используют устаревшие модели управления, которые не соответствуют сегодняшней тенденции развития. В портах существует проблема неэффективного управления перегрузочным процессом, который осуществляется без использования современных эффективных методик с применением информационных технологий. Коммунистическая партия Вьетнама уделяла и уделяет большое внимание задачам, поставленным перед морскими портами, и требует внедрения новейших технологий и новых методов управления, позволяющих повысить эффективность производственной деятельности.
Объектом исследования являются перегрузочные процессы морского порта.
Предмет исследования – методы, модели и алгоритмы обработки информации и правила принятия решений в управлении перегрузочными процессами морского порта.
Целью исследования является повышение эффективности управления перегрузочными процессами морского порта на взаимосвязанной системной, математической, алгоритмической и программной основе.
Для достижения поставленной цели решаются следующие задачи:
-
Проведение системного анализа перегрузочных процессов морского порта для выявления структуры целей и функций системы управления перегрузочными процессами и значимых задач с точки зрения сокращения комплексных расходов перегрузочных процессов.
-
Формирование системы критериев, отображающих технические характеристики перегрузочных комплексов, позволяющей определить набор параметров, предназначенных для управления перегрузочными процессами.
-
Разработка семантической модели для формирования предметной области перегрузочных процессов в морском порте и представления его в виде граф-модели.
-
Разработка граф-модели перегрузочных процессов и модели управления перегрузочными процессами морского порта.
-
Разработка метода и алгоритма решения задачи управления перегрузочными процессами морского порта на основе генетических алгоритмов.
-
Создание и практическая реализация информационной системы управления перегрузочными процессами морского порта Вьетнама.
Методы исследования. Для решения поставленных задач использованы методы системного анализа, математического моделирования, теории графов, теории вероятностей, оптимального управления, эволюционные методы.
Научная новизна:
-
Выполнена систематизация перегрузочных процессов морского порта на основе метода дерева целей, позволяющая структурировать цели и функции системы управления перегрузочными процессами, и выявить наиболее значимые задачи с целью сокращения комплексных расходов на перевалку. Разработана система критериев, отображающих технические характеристики перегрузочных комплексов, позволяющая определить набор параметров перегрузочного процесса.
-
Созданы граф-модель перегрузочных процессов, позволяющая определить направления передвижения грузов внутри порта и изменение состояний системы управления, и модель для решения задачи управления перегрузочными процессами морского порта в виде многоиндексных транспортных задач, позволяющая осуществлять оперативное распределение грузопотоков между складскими, причальными и транспортными ресурсами порта.
-
Разработаны и реализованы модернизированный генетический и гибридный алгоритмы, отличающиеся тем, что представление хромосомы, процедура создания начальной популяции и генетические операторы выполняются над многоразмерными матрицами для управления перегрузочными процессами морского порта.
Практическая ценность диссертационной работы заключается в разработке информационной системы управления перегрузочными процессами порта Хайфон, позволяющей автоматизировано обрабатывать данные, оперативно планировать перевозку грузов, упростить процесс составления плана перевозок грузов и повысить эффективность управления перегрузочными процессами.
Результаты работы используются в учебном процессе ФГБОУ ВПО «Астраханский государственный технический университет».
Достоверность и обоснованность научных положений обусловлена корректным применением использованных в работе методов и подтверждена результатами экспериментальных исследований, показавших, что модернизированный генетический и гибридный алгоритмы позволяют реализовать поиск оптимального решения лучше, чем классические методы решения транспортных задач, проверкой адекватности разработанной модели на основе сравнения данных разработанной информационной системы и статистических данных морского порта Хайфон.
Личный вклад автора. В работах, выполненных в соавторстве, автору принадлежат формализация задачи, построение модели управления и методов, разработка алгоритмов, проектирование и реализация программного обеспечения.
Апробация научных результатов. Результаты диссертационной работы докладывались и обсуждались на: конференции молодых ученых и инноваторов «Инно-Каспий (Астрахань, 2009)», Международных научных конференциях Инновационные технологии в управлении, образовании, промышленности «АСТИНТЕХ-2009» и «АСТИНТЕХ-2010» (Астрахань, 2009, 2010), 7-й Всероссийской конференции по теоретическим основам проектирования и разработке распределенных информационных систем (Красноярск, 2009), II Всероссийской межвузовской научной конференции «Зворыкинские чтения» (Муром, 2010), XXIII Международных научных конференциях «Математические методы в технике и технологиях» (Саратов, 2010).
Публикации. Основные положения диссертационной работы отражены в 10 опубликованных научных работах, в том числе в 2 статьях в научно-технических изданиях, в которых ВАК рекомендует публикацию основных научных результатов диссертаций и 1 свидетельстве о регистрации программы для ЭВМ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав основного текста, заключения, списка литературы. Основной объем работы – 123 страницы машинописного текста, который включает 37 рисунков, 8 таблиц, 10 приложений.
Модели управления организационными системами
На схеме также указаны погрузочно-разгрузочные пункты, через которые выполняются варианты прохождения грузов внутри порта. Это такие погрузочно-разгрузочные пункты как: причал, площадка, склад, место обработки автомобилей и железнодорожная станция.
Перегрузочные комплексы, предназначенные для выполнения перегрузочных процессов порта должны быть достаточно мощными, для того чтобы они успешно функционировали.
Сложность управления перегрузочными процессами определяется рядом специфических особенностей [16, 17, 44].
1. По своему характеру и трудоемкосіи перегрузочные работы довольно разнообразны. Это обуславливается многочисленной номенклатурой грузов со значительным числом, различием вариантов работ, конструктивными особенностями судов, железнодорожных вагонов и грузового автотранспорта, непрерывно изменяющейся производственной обстановкой в порту, физическим состоянием и расположением грузов на судне и складе. Трудоемкость и интенсивность перегрузки различных родов грузов колеблется в широком диапазоне.
2. Интенсивность перегрузочных процессов, также как и время нахождения транспортных средств в порту, зависит от множества факторов, большая часть которых неуправляема портом. Это, например, такие факторы, как: наличие груза и его комплектность, готовность судна к приему или выдаче груза, наличие свободных складских площадей для приема груза, обеспеченность железнодорожным или автотранспортом для вывоза груза, наличие рабочей силы, метеорологическая обстановка.
3. Особенностью перегрузочных работ является их непрерывность. Работы ведутся круглосуточно и без перерывов на выходные и праздничные дни. В незамерзающих портах, а также в замерзающих при наличии ледокольного флота, перегрузочная деятельность производится круглогодично, но в зимне-весенний период объем перегрузочных работ по некоторым грузопотокам может уменьшаться.
4. Перегрузочная деятельность порта, ее ритмичность и эффективность находятся в органической связи с движением транспортного флота. Прибытие каждого судна в порт подчинено графику движения флота, но фактически время прибытия, как правило, отличается от ожидаемого и порой значительно. Нередки случаи одновременного прибытия в порт нескольких судов с однородным грузом. Для успешной грузовой обработки судов порту необходимы экономически обоснованные резервы пропускной способности перегрузочных комплексов.
Важной особенностью порта как комплексного транспортного узла является взаимодействие его элементов: судов, железнодорожного транспорта, автомобилей, грузов, перегрузочной техники и обслуживающего персонала, стохастически реагирующих на управляющие воздействия.
Сложность и трудоемкость перегрузочных работ в портах обусловлены одновременным участием в них значительного количества людей, различных технических средств для обработки и обслуживания судов, вагонов и автомобилей, уровнем оперативного управления грузопотоками различных направлений. Современное развитие морского транспорта, характеризуется появлением новой техники, вводом в эксплуатацию новых механизированных перегрузочных комплексов, улучшением их качественных характеристик: скорости, грузоподъемности, технической производительности и надежности [43].
Для успешного функционирования порту необходимо оперативное управление его работой, которое включает оперативное планирование работы транспортного узла, диспетчерское руководство, учет, анализ и регулирование производственных процессов порта.
Характеристика и особенность перегрузочных процессов в морских портах СРВ
Перегрузочные процессы любых морских портов имеют очень важную роль в производственной деятельности и влияют на эффективность работы порта.
Основной производственной деятельности вьетнамских портов, как и морских портов других стран, являются перегрузочные процессы, а также связанная с ними полная обработка и комплексное обслуживание судов, прием и хранение грузов и др. Однако среди них перегрузочные операции являются главными и наиболее трудоемкими. В других странах морские порты связывают с транспортной инфраструктурой, где грузы на судах после выгрузки перевозятся автомобилями, по железнодорожным или внутренними водным путям. Во Вьетнаме в морских портах осуществляется перевозка грузов в основном на автомобилях [61, 63]. Так как, железные дороги еще не оснащены внутри порта, поэтому грузы будут перевозиться на грузовых автомобилях, а за тем доставляются в пункт погрузки/разгрузки поездов. Поэтому характеристикой транспортных средств в морских портах СРВ является то, что перевозкой грузов занята большая часть автотранспорта внутри порта. В главных портах численность автотранспорта, непосредственно занятого в перегрузочных процессах, составляет 70 - 75% всех транспортных средств порта [104, 117]. Портовая инфраструктура морских портов Вьетнама является слабой по качеству и устаревшей по сравнению с технологическими требованиями. Большинство морских портов использует несовременное перегрузочное оборудование и имеет модели управления по погрузке, разгрузке, хранению с не эффективной технологией. Морской порт Хайфон - самый большой порт севера Вьетнама - средняя мощность погрузки/разгрузки грузов общего вида достигает только 2000 - 3000 Т/м, а грузы контейнерах 12-15 коитейнер/кран/ч. Это значит, что она составляет 50 - 60% по сравнению с современными морскими портами других стран в Южно-Китайском море [120].
В морских портах существует проблема высоких расходов на перевозку и большого стояночного времени судов в порту. В крупных портах (Хайфон, Дананг, Сайгон) для судов более 20 тысяч тонн затраты за стоянку в порту составляет 5000 - 6000 USD в сутки. Обычно, время ожидания погрузки и разгрузки судов составляет 5-7 дней, когда судно заходит в порт с большим количеством груза, тогда они ждут в очереди 15-20 дней, в результате его затраты на стоянку в порту увеличиваются до 100000 USD. Снижение простоя судов на стоянке в порту позволяет существенно снизить эксплуатационные затраты по судну и порту. Так, например, сокращение стояночного времени судов с грузовместимостью 36000-45000 тонн на 1 день в порту, позволит экономить около 15000 долларов США [119].
Основными показателями, характеризующими перегрузочные процессы в морских портах СРВ, являются показатели удельных комплексных расходов перегрузочных работ по порту и флоту, связанные с расходами на впутрипортовое перемещение грузов и затратами за стоянку судна.
Для перегрузочных работ морских портов СРВ характерно, что порты имеют в основном небольшой грузооборот. Порты первой категории занимаются главным образом переработкой каботажных углей, лесных грузов и продовольствия. Главные морские порты Вьетнама Хайфон, Хошимин, Дананг переработают не только каботажные, но и импортно-экспортные грузы как навалочные, и так и генеральные
Формирование системы критериев
С целью повышения эффективности перегрузочных процессов (снижения эксплуатационных затрат на перевозку грузов), рассмотрим основные этапы перевалки грузов с момента прибытия к причалам до момента отправлении из порта.
Процесс транспортировки грузов начинается и заканчивается погрузочно-разгрузочными операциями. Кроме того, в процессе перевозки грузы могут передаваться с одного вида транспорта на другой, временно храниться на складах, где также выполняются погрузочно-разгрузочные работы. Объекты, где осуществляется передача грузов, сопровождаемая погрузочно-разгрузочными работами, называют погрузочно-разгрузочными пунктами. Погрузочно-разгрузочные пункты порта включают причал, площадку, место обработки автотранспорта, склад и железнодорожную станцию [95].
Как мы видим, в перегрузочном процессе присутствуют повторяющиеся погрузочно-разгрузочныс операции и действия по передвижению грузов. Они встречаются в перегрузочном процессе несколько раз. В морском порте каждый день осуществляется процесс перевалки большого количества различных видов грузов. Судно, приходящее в порт необходимо распределить к причалу, подготовить его к погрузке/разгрузке и вариантам перевозки грузов. Перегрузка этих грузов осуществляется на универсальных перегрузочных комплексах морских портов. Железнодорожные вагоны, грузовые автомобили, плавсредства, используемые для внутрипортового перемещения груза по одному из вариантов, рассматриваются как средства внутрипортового транспорта [91].
Проведем на основе метода дерева целей системный анализ перегрузочных процессов морского порта. Для этого, разработаем структуру дерева целей на основе пирамиды Сагатовского [6, 21, 22, 62], которая требует анализа взаимодействия системы со средой. В разработанной методике проведены два этапа: формирование структуры целей и функций, состоящей из семи уровней пирамиды; и оценка этой структуры, с использованием экспертных оценок (система критериев) и формированием семантической модели перегрузочных процессов.
Структура дерева целей на основе пирамиды Сагатовского представлена на рис.2.2. Пирамида состоит из семи уровней: формирование глобальной цели системы, декомпозиция по признаку «виды конечного продукта», декомпозиция по признаку «пространство инициирования целей», декомпозиция по признаку «жизненный цикл», декомпозиция по основным элементам системы, декомпозиция по признаку «управленческий цикл» и декомпозиция по признаку «делегирование полномочий». Первые четыре уровня представляют собой детализацию целей до уровня конкретных подцелей. С пятого по шестой уровпеь это фукции, поскольку к процессу реализации глобальных целей подключаются ресурсы системы. Здесь под функцией управления понимается организационная совокупность средств, методов реализуемых в системе с целью повышения эффективности управления перегрузочных процессов. Такая структура, которая на протяжении какого-то периода времени мало изменялась бы при неизбежных изменениях, происходящих в любой развивающейся системе [62].
В соответствии с методикой Сагатовского каждую цель следует уточнять по типу конечного продукта. Может представлять конечные продукты в следующие: 1. Увеличение объема перевозимых грузов (Qn). 2. Повышение эффективности процесса перевалки грузов (Q"
Это позволяет ускорить процесс перевалки грузов и сокращает стояночное время судов в порту, снизить затраты труда, электроэнергии топлива и др. [46, 47]. В порту необходимо осуществлять обеспечения, которые перечислены ниже.
Решение задачи оперативного планирования обработки грузов (Q211) Задача оперативного планирования обработки грузов является специализацией перегрузочных комплексов по грузопотокам с разными типами. В работе Магамадова [47] проведен анализ задачи распределения и использования ресурсов порта при обработке судов. Ее решение состоит в определении причалов, использующихся для разгрузки грузов на суднах и определении величин, фиксирующих складские емкости (площади), необходимые для их размещения. Эти задачи, связанные с планированием прохождения грузов через порт, заключаются в оптимальном распределении грузопотоков между причалами и установлении оптимальной специализации причалов, складов, транспортных средств порта. Эти задачи также проведены в работах Флорова [83], Ананьина [3, 4, 5]. Авторами указано, что специализация эксплуатируемых причалов, складов по специфике освоения грузопотоков является одной из задач оптимизации режима работы порта.
Специализация упрощает и облегчает планирование и организацию перегрузочного процесса, диспетчерское руководство погрузочо-разгрузочными работами и учет их выполнения. Она позволяет лучше использовать технические средства порта, повысить его пропускную способность, добиться высоких производственных показателей и приводит к снижению затрат на перегрузку и перевозку грузов[44].
В числе критериев оптимального управления перегрузочными процессами наибольшей общностью обладает критерий минимума суммарных эксплуатационных расходов перегрузочных процессов. Из содержательного смысла показателя суммарных расходов видно, что на его величину наибольшее влияние оказывает составляющая затрат по судну и порту. Минимизация этой составляющей является поиском оптимального плана перевозок грузов внутри порта. Это соответствует задаче внутрипортового оперативного планирования обработки грузопотоков. Потому решение поставленной задачи способствует сокращению стояночного времени судов, увеличению объемов грузов, проходящих через порт и обеспечению минимальных расходов порта на перевалку грузов [47, 83].
Алгоритм решения поставленной задачи
Как указано выше перевозка внутри поріа является сложной транспортной задачей. В морских портах происходит обработка грузопотоков различных видов и значительных объёмов. Кроме этого, более сложной задачей перевозки в портах является распределение разнородного транспорта различной грузоподъемности. Например, для обеспечения перевозок могут быть использованы различные типы автомашин. При этом машины разных типов, обладая различными эксплуатационными характеристиками и разной скоростью, могут доставлять любой из грузов, находящихся на причалах. Таким образом, задачей управления становится задача перевозки внутри пор і а неоднородного грузопотока па разнородном транспорте от причалов до складов [94, 96]. При известных затратах на перевозку единицы грузопотока по разному варианту маршрута передвижения грузов, необходимо найти план перевозок, обеспечивающий минимальные затраты.
Постановка задачи оптимизации С целью рационального распределения грузопотоков по причалам необходимо разработать возможные варианты «закрепления» грузов за причалами, складами и транспортными средствами, сравнить варианты между собой и выбрать из них оптимальный вариант, дающий наибольший эффект. Задача оптимизации плана распределения грузопотоков между причалами, складами и транспортными средствами формируется следующим образом.
В порте имеется система причалов, складов и некоторые типы транспортных средств, предназначеные для освоения некоторого количества грузов. Необходимо распределить грузопотоки на разном транспорте между причалами и складами, чтобы обеспечить минимум комплексных расходов по порту и судну [88, 96].
При планировании варианта перевозки, в котором осуществляется фиксирование А:-го грузопотока на определенном причале, связанном с ним 5-го склада на транспорте h-то типа. В соответствии с этими данными представлены известные показатели удельных комплексных расходов по данному маршруту перевозки грузов Скуъ , удельных расходов бюджета времени причала тhjh, удельных расходов полезной площади склада wkljh . Пусть {xhjh}, к = \,g,i = \,n,h = 1, l,j = \,s, есть количество груза к-то рода, планируемое для перевозки из /-го причала в у -й склад потребления транспортным средством /г-го типа. Стоимость перевозки х и единиц груза равна Необходимо минимизировать: (1) 2) к=\ i=] j=\ h=\ При ограничениях: /=1,и j=\,s h=\,l (3) (4) (5) (6) k=\,g i=\,n h=\J A=l,g i=\,n j=\,s Ограничение (2) обозначает что, количество перевозимых грузов по маршрутам одного варианта равно объему обязательного освоения грузопотока. Ограничение (3) показывает что, потребность площади склада для сохранения количества всех перевозимых грузов по маршрутам не должно превышать его полезную площадь. Ограничение (4) показывает использование причала в пределах планового бюджета времени. Ограничение (5) определяет, что транспортное средство не может перемещать количество грузов больше, чем позволяют его возможности.
Задача (1) - (6) называется четырехиидексной транспортной задачей. Величины Qk, Wj, Dh, Сщ, tkih} wkihj являются параметрами данной задачи, а набор {Хщ} называется набором переменных. Набор {Xkihj), удовлетворяющий условиям (2)-(6), является допустимым планом, причем каждому плану соответствует определенное значение целевой функции (1). Допустимый план, который обеспечивает минимальное значение - это оптимальный план задачи.
Разработанный метод представляет собой модернизированный генетический алгоритм (МГА), в котором в отличие от стандартного генетического алгоритма для данной задачи используется новая процедура инициализации начальной популяции, ориентированная на получения решений, удовлетворяющих системе ограничений. Хромосома - эта четырехразмерная матрица, содержащая действительные числа. Хромосомы представляют собой матрицы перевозок, в качестве них служат четырехразмерные массивы, описывающие варианты решений; два генетических оператора воспроизводства - мутация и кроссовер, их операции выполняются над четырехразмерными матрицами [88].
При создании начальной популяции используется алгоритм получения опорного плана. Поиск начинается из множества допустимых решений, критерием останова в данном случае является полное распределение всего объема грузопотоков по создаваемой хромосоме.
Генетические операторы представлены для работы с матрицами и порождают только решения удовлетворяющие ограничениям [92, 94, 95]. В процессе эволюции действует известный принцип, когда выживает (процветает) наиболее приспособленная особь. Популяция постоянно обновляется при помощи генерации новых особей и уничтожения старых или менее приспособленных индивидов.
Информационная система управления перегрузочными процессами морского порта Хайфон (ИСУПП)
В результате выполнения оператора мутации все глобальные ограничения сохраняются. Таким образом, в предложенном операторе мутации порождаются из родительских хромосом потомки, являющиеся допустимыми решениями [9, 33, 100, 107, 113, 115]. Процедура создания новой популяции Процедурой создания новой популяции является отсев неудачных особей. Так как размер популяции в данном алгоритме поддерживается постоянным, то есть после скрещивания и мутации размер популяции увеличивается и в результате мы получаем текущую популяцию POP1 = { R[, R -Коразмерности U = (и +uj). Вычисляются функцию пригодности для каждой хромосомы и сортируются по возрастаниюлриЕодности_[38,_65, 68]. ы_шлуыаем_последовательность: mi) mi) ... mi) mLi ) ...mb) Создается новая популяция POP 2 = { R?ew, R%ew , ..., Rw)размерности и.
Это значит, что для последующих преобразований необходимо сократить число хромосом с помощью опера юра селекции. В текущей популяции, состоящей из родителей и потомков, производится отбор лучших решений, т. е. хромосом с наилучшим значением целевой функции. В результате оператора селекции последние iii отсеваются из популяции. Таким образом, отсев неудачных особей формирует из общего множества родителей и потомков популяцию следующего поколения более высокого качества и направляет весь процесс эволюции.
Основная особенность генетического алгоритма состоит в том, что анализируется не одно решение, а некоторое подмножество субоптимальпых решений. В данной реализации начальная популяция формируется случайным образом, координаты элемента матрицы - хромосомы. Для увеличения скорости сходимости генетического алгоритма представляется гибридный генетический алгоритм (ГГА)[35]. В качестве ГГА используется в предложенном генетическом алгоритме метод локального оптимума - минимального элемента матрицы для создания начальной популяции [67]. Метод минимального элемента при нахождении опорного плана учитывает стоимости перевозок, и осуществляется таким образом: очередность распределения грузов в клетках на пересечении линий к-го грузопотока, /-го причала, у-го склада и s-ro автотранспорта определяется величиной удельных комплексных расходов, начиная с минимума и следуя в порядке возрастания.
Таким образом, метод минимального элемента матрицы заключается в том, что на каждом шаге осуществляется выбор координат (к, i, j, к) ведущего элемента на основе матрицы удельных комплексных расходов, значение которого -минимум значений правых частей ограничений.
Миїаіїоп2г В-данной-работе оператор-мутации-вьтбирается-с использованием значений компонентов целевой функции с целью уменьшения значений комплексных расходов [9]. Пусть для мутации выбрана особь R. Из R выбираются элементы, у которых произведения его значением и соответствующих затрат наибольшие.
В результате выполнения оператора мутации все глобальные ограничения сохраняются. Таким образом, для гибридного генетического алгоритма выделяется три основных этапа: формирование начальной популяции с помощью метода минимального элемента матрицы; синтез новых хромосом (скрещивание, мутация). При выполнении оператора скрещивания выбирается арифметический тип, а оператор мутации - Mutation 1 или Mutation2. селекция текущей популяция и формирование новой популяции.
Проведение экспериментальных исследований включало в себя: Исследование механизмов эволюционного поиска, разработанных генетических алгоритмов, таких как размер разработанной задачи, тип скрещивания и мутации на качество получаемых решений. Исследование эффективности предложенных алгоритмов, как сравнение их результатов по минимуму целевой функции.
Для проверки работы предложенных алгоритмов разработана программа в на языке программирования С# в среде Visual Studio 2008. Интерфейс программы предназначен для ввода значения параметров алгоритма и размера разработанной задачи; инициализации исходных данных задачи; выбора механизма скрещивания и мутации; выбора генетического алгоритма поиска оптимального решения задачи. _ Лрограммное-обеспечение-расположено-в-Population.cs в среде VisuabStudio 2008, в котором Public class Population включается: моделирующая функция; параметры генетического алгоритма; генетические операторы (скрещивание и мутация) и оператор селекции.
Для проверки эффективности работы ГГА и МГА проведено сравнение наилучших решений, полученных из ГГА, МГА и КТЗ. В качестве КТЗ использован метод последовательного распределения па основе метода северно-западного угля [88].
Похожие диссертации на Моделирование и алгоритмы управления перегрузочными процессами морского порта
