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

• Автор: Полуян, Анна Юрьевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ростов-на-Дону
• Количество страниц: 196 с. : ил.

Оглавление
Введение
Глава 1.

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

1.1. Прикладные задачи транспортного типа как объект математического моделирования

1.2. Математические модели и анализ классических алгоритмов решения задач о кратчайшем и длиннейшем пути на графе

1.3. Математическая модель и алгоритмы решения задачи коммивояжера

1.4. Анализ методов эволюционного моделирования

1.5. Выводы Глава 2.

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

2.1. Построение решения задач

2.1.1. Кодирование решений задач
2.2. Стратегии формирования и развития начальной популяции
2.3. Построение модифицированных генетических операторов для моделирования задачи нахождения экстремального пути
2.4. Организация процедур моделирования бионического и параллельного бионического поиска
2.4.1. Разработка бионического алгоритма
2.4.2. Разработка модифицированной базисной структуры оптимизационного процесса, основанной на принципах бионического поиска
2.4.3. Построение структурной схемы параллельного
бионического алгоритма
2.5. Выводы
Глава 3.
Организация процедур моделирования бионического и
параллельного бионического поиска для решения задачи коммивояжера
3.1. Анализ особенностей моделей
3.2. Моделирование начальной популяции
3.3. Моделирование модифицированных генетических операторов для решения задачи коммивояжера
3.4. Разработка структуры бионического поиска на основе эволюционных стратегий
3.4.1. Построение модифицированного генетического алгоритма для формирования бионического поиска
3.4.2. Разработка модифицированного эволюционного алгоритма
3.5. Построение структурной схемы параллельного бионического поиска
3.6. Выводы 3 Глава 4.
Экспериментальное исследование программного комплекса,
разработанных алгоритмов
4.1. Цель и средства экспериментальных исследований
4.2. Краткие сведения об инструментальной
среде программного комплекса
4.3. Результаты экспериментальных исследований 9 задачи о кратчайшем пути
4.4. Результаты экспериментальных исследований 7 задачи коммивояжера
4.5. Выводы
Заключение
Список используемой литературы


Эксперименты проводились с целью определения вычислительной сложности и качества получаемых решений, разработанных алгоритмов для сравнительной оценки с существующими. Определены оптимальные значения управляющих параметров для разработанных бионических алгоритмов. В заключении представлены основные результаты и выводы по диссертационной работе. В приложении приведены акты об использовании результатов работы и листинг программы. Глава 1. Среди приложений информационных технологий большое место занимают проблемы решения задач транспортного типа. Это задачи чаще всего встречаются при исследовании разнообразных процессов на транспорте и системах связи: эффективного обеспечения прохождение грузов между сетями различных транспортных агентов, распределения заказов между предприятиями с учетом транспортных издержек; проектирования сложных сетей и объектов (дорог, продуктопроводов, тепловых и электрических сетей); рационального распределения грузопотоков между различными видами транспорта. Временные сложности, возникающие при решении задач транспортного типа, зачастую связаны с их большой размерностью. Рассмотрим граф, вершинам которого соответствуют производства или потребители продукции, а также пункты перевалки и просто развилки транспортных магистралей. Дуги соответствуют длинам отрезков дорог, транспортных магистралей, коммуникациям, автомобильным, водным или железнодорожным путям, расположенным на рассматриваемой территории, и связывают вершины графа. Тогда типичной задачей транспортного типа является задача нахождения некоторого пути из пункта А в пункт В. Например, стоимость проезда по избранному пути известна, требуется определить наиболее экономичный путь в соответствии с избранным критерием оптимальности. А и пункт В. Это в полной мере относится к задачам об экстремапьном пути на графе и задачи коммивояжера. Пусть дан граф С=(Х,Ц) дугам которого приписаны веса (стоимости), задаваемые матрицей С = су ]. X до заданной конечной вершины /еХ, при условии, что такой путь существует, т. I принадлежит множеству, достижимому из вершины Б. Единственное ограничение состоит в том, чтобы в в не было циклов с отрицательным суммарным весом []. Для заданной начальной вершины б найти кратчайшие пути между б и всеми другими вершинами х еХ. Найти кратчайшие пути между всеми парами вершин. С(х)= I с(х) —>тт, (1. Х.=1> (1. Ограничение (1. Ограничение (1. Любое решение системы неравенств (1. Пусть все контуры имеют строго положительную длину, т. Тогда решение задачи (1. Аналогично задаче о кратчайшем пути формулируется и решается задача о максимальном (длиннейшем) пути - достаточно изменить знаки дуг на противоположные и условие (1. С(х) = ? Для существования решения задачи о максимальном пути необходимо и достаточно отсутствия контуров положительной длины. Проведем краткий анализ наиболее применяемых классических алгоритмов решения задач данного типа. Известно, что наименьшая сложность нахождения всех кратчайших путей от истока к прочим узлам орграфа без циклов равна О(гп), где ш — число дуг в орграфе [6,7,]. Метод Флойда, непосредственно основывается на том факте, что в графе с положительными весами ребер или дуг всякий, содержащий более одного ребра, кратчайший путь состоит из других кратчайших путей []. Сложностью формирования исходных матриц можно пренебречь, так как очевидна большая сложность трёхкратного цикла О(п ’). Этот метод применим в случае, если матрица весов не имеет контуров отрицательной длины. У метода Флойда одно несомненное преимущество - концептуальная простота и вытекающий из неё лаконизм алгоритмической реализации. Утверждение о том, что метод Флойда - лучший по производительности, легко опровергнуть, обратившись к лучшим реализациям иных методов, что и будет сделано ниже [,]. Естественно, различия в области применения методов должны учитываться пользователем, а метод Флойда имеет наименьшие ограничения. Ллгорипш Дейкстры. Для начала приведём классический алгоритм Дейкстры нахождения кратчайшего пути между вершиной в и всеми остальными вершинами графа [7,,].