Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа
Скачать 290.55 Kb.
|
1 2
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫВ результате выполненных теоретических и практических исследований получены следующие результаты: 1. Определены основные направления области использования задач транспортного типа, которые могут быть представлены в виде моделей задач об экстремальном пути на графе. Исследованы математические модели задач транспортного типа, адекватно отражающие сущность задач, проведен анализ и сравнительная характеристика существующих методов решения задач об экстремальном пути и задачи коммивояжера. Отмечены достоинства, недостатки и перспективы развития этих алгоритмов. Предложен новый подход к кодированию решений, учитывающий статусы генов, который достаточно эффективный для решения задач об экстремальных путях. 2. Предложенны новые и модифицированные эволюционные и генетические операторы мутации, кроссинговера, сегрегации, инверсии, селекции, миграции, для решения задач транспортного типа, которые увеличивают вероятность «выживания» альтернативных решений с лучшим значением ЦФ на 10% -15%. Разработана модифицированная базисная структура оптимизационного процесса, основанная на принципах бионического поиска и структурная схема параллельного бионического поиска, преимущество которых, состоит в том, что все строительные блоки связаны как с блоком адаптации, предназначенным для выбора и реализации различных стратегий и механизмов адаптации, так и между собой. 3. Построены модифицированные алгоритмы бионического и параллельного бионического поиска с применением адаптации, в которых предложена совместная реализация эволюций Дарвина и Ламарка, эволюционная адаптация, предназначенная для выбора и реализации различных стратегий и механизмов адаптации. Разработаны модифицированные генетические и эволюционные алгоритмы основанные на «жадных» стратегиях и эвристиках, ориентированные на решение задач транспортного типа, которые позволяют получать оптимальные результаты за приемлемое время работы алгоритма. Разработана реализация общей стратегии адаптации размера популяции, позволяющая адаптироваться к характеристикам бионического поиска. Временная сложность разработанных алгоритмов составляет O(αN2). 4. Разработан комплекс программ на основе бионического и параллельного бионического поиска. Экспериментальные исследования параллельного бионического алгоритма показали, что наиболее качественные решения были получены при числе итераций NG= 1000 и размере популяции Nр от 400 до 500, для задачи об экстремальном пути, и при NG = 1500, Nр = 500 для задачи коммивояжера. По результатам экспериментов, для каждого алгоритма и операторов даны рекомендации оптимальных параметров, обеспечивающих возможность получения набора локально – оптимальных решений: вероятность оператора кроссинговера для задачи об экстремальном пути должны быть в пределах 0,7-0,8, для задачи коммивояжера - 0,6 – 0,7; вероятность оператора мутации для задачи об экстремальном пути – 0,4, для задачи коммивояжера 0,3 – 0,4, оператора миграции – 0,7. При данных значениях параметров обеспечиваются наилучшие условия для нахождения оптимального решения. 5. Бионические и параллельные бионические алгоритмы для решения задач транспортного типа показали преимущество по качеству решений, по сравнению с существующими методами на 10% - 15%. Управление процессом бионического и параллельного бионического поиска, позволяет находить оптимальные параметры и повысить качество решений ориентировочно на 15% - 20%. Параллельный бионический алгоритм улучшил решение задачи на 12% - 20% при больших (n>1500) размерностях задачи. Основные положения диссертации изложены в 16 работах, из них в изданиях, входящих в перечень ВАК – 5 работ. Работы, опубликованные в изданиях из перечня ВАК: 1. Касаткин Г.М., Таможникова А.Ю. Приближенное решение задачи о коммивояжере.// Известия ТРТУ. Таганрог. ТРТУ. – 2006. – № 8. 2. Чернышев Ю.О., Полуян А.Ю. Адаптивный генетический алгоритм для решения задачи оптимизации на основе стратегии элитизма. .// Известия ТРТУ. Таганрог. ТРТУ. – 2008. – № 4. 3. Чернышев Ю.О., Белявский П.Г, Полуян А.Ю. Эволюционный подход к решению задачи о назначении через определение кратчайшего пути.// Известия ТРТУ. Таганрог. ТРТУ. – 2008. – № 9. 4. Полуян А.Ю. Адаптивный генетический алгоритм задач оптимизации на основе стратегии элитизма. // Известия ТРТУ. Таганрог. ТРТУ. – 2008. – № 9. 5. Чернышев Ю.О., Полуян А.Ю. Решение задачи оптимизации на основе параллельного бионического поиска.// Известия ТРТУ. Таганрог. ТРТУ. – 2009. – № 4. Публикации в других изданиях: 6. Таможникова А.Ю. Решение задачи о нахождении кратчайшего пути в графе с использованием генетического алгоритма. Труды международных научно-технических конференций «Интеллектуальные системы (IEE AIS’05)» и «Интеллектуальные САПР (CAD-2005)» Научное издание в 4-х томах. М.: Изд-во «Физматлит», 2005.- Т. 4. 7. Чернышев Ю.О., Посупонько Н.В., Таможникова А.Ю. Генетический алгоритм выбора оптимального варианта системы обнаружения ошибок по критерию достоверности. Труды международных научно-технических конференций «Интеллектуальные системы (IEE AIS’05)» и «Интеллектуальные САПР (CAD-2005)» Научное издание в 4-х томах. М.: Изд-во «Физматлит», 2005.- Т. 2. 8. Смирнова О.В. Таможникова А.Ю. Генетический алгоритм решения задачи коммивояжера.// Научные труды Ростовской-на-Дону Государственной академии сельскохозяйственного машиностроения: сборник научных трудов – Ростов н/Д, 2006. 9. Смирнова О.В. Таможникова А.Ю. Алгоритм решения задач коммивояжера с использованием эволюционных методов.// Безопасность жизнедеятельности. Охрана труда и окружающей среды: межвузовский сборник научных трудов /РГАСХМ. - Ростов н/Д, 2007. - Вып. 11. 10. Чернышев Ю.О., Полуян А.Ю., Демчук Г.В. Выбор оптимального варианта системы обнаружения ошибок по критерию достоверности. Труды международных научно-технических конференций «Интеллектуальные системы (IEE AIS’07)» и «Интеллектуальные САПР (CAD-2007)» М.: Изд-во «Физматлит», 2007.- Т. 2. 11. Чернышев Ю.О., Басова А.В., Полуян А.Ю. Решение задач транспортного типа генетическими алгоритмами. Монография. Ростов н/Д: Изд-во ЮФУ, 2008 12. Полуян А.Ю.Эволюционный подход к решению задач о нахождении кратчайшего пути в графе.// Информационные технологии в профессиональной деятельности и научной работе: сборник материалов всероссийской научно-практической конференции с международным участием / МГТУ. - Йошкар-Ола, 2008. – Т.2. 13. Смирнова О.В., Полуян А.Ю. Анализ алгоритмов для решения комбинаторных задач.// Безопасность жизнедеятельности. Охрана труда и окружающей среды: межвузовский сборник научных трудов /РГАСХМ. - Ростов н/Д, 2008. 14. Смирнова О.В., Полуян А.Ю. Эволюционный подход к выбору решения задач о нахождении кратчайшего пути в графе.// Новые технологии, конструкции и процессы производства: сборник научных трудов /РГАСХМ ГОУ. – Ростов н/Д, 2008. 15. Полуян А.Ю. Адаптивный генетический алгоритм для решения задач максимальном пути в графе на основе стратегии элитизма.// Модели и алгоритмы для имитации физическо-химических процессов: сборник материалов международной научно-технической конференции / ТГПИ. - Таганрог, 2008. 16. Чернышев Ю.О., Полуян А.Ю. Решение задачи о потоке минимальной стоимости на основе параллельного бионического поиска.// Сборник научных трудов «Проблемы создания информационных технологий» Вып.2, международное научно общественное объединение «МАИТ», М.: 2010. В работах опубликованных в соавторстве, А.Ю. Полуян принадлежат следующие результаты: в [1] разработан приближенный метод решения задачи коммивояжера; в [2,3,7,8] разработаны модифицированные генетические алгоритмы и операторы для решения поставленных задач; в [5,9,13,14,16] разработаны алгоритмы последовательного и параллельного бионического поиска, на основе эволюционной адаптации, проведены сравнительные оценки полученных методов; в [11] исследованы математические модели задач транспортного типа, проведен анализ существующих методов и алгоритмов для решения задач данного типа, разработаны модифицированные генетический и эволюционный алгоритмы для решения задач о кратчайшем пути и коммивояжера. Соискатель А.Ю. Полуян |
1 2
Похожие:
 | Разработка и исследование алгоритмов решения транспортных задач с... Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге |  | Законов, закономерностей математики и отвечающих им методов расчета. Формирование базовой Применение основных понятий и методов математической логики и теории алгоритмов для решения конкретных задач |
| Problems of transport type, optimizing problems, computer mathematical... В работе рассматривается технология построения компьютерных моделей оптимизационных задач транспортного типа в ms excel и проводится... | | Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики |
| Программное обеспечение для решения задач линейного программирования... Граничениями типа меньше или равно. Основой программы служит алгоритм симлекс метода с возможностью вывода результата в виде графического... | | Тема урока: «Составление линейных программ для решения задач на применение... Повторить и обобщить знания о свойствах, типах, способах построения алгоритмов, этапах решения задач, о работе операторов input,... |
| Диплом «Исследование и сравнение способов решения логических задач» Практическая часть. Разработка сайта и тестирующей программы | | Отчет №3 о научно-исследовательской работе по теме: «Грид-технологии» Разработка методов эффективного решения задач обработки, хранения, передачи и защиты информации |
| Исследование методов обработки электроэнцефалографических сигналов... Работа выполнена в таганрогском технологическом институте Южного федерального университетана на кафедре Радиоприёмных устройств и... | | Реферат: Шайдуров А. Г. Исследование и разработка некоторых графических... Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению... |
| Разработка и исследование алгоритмов распознавания изображений на... | | Новосибирский государственный технический университет кафедра вычислительной техники Целью работы является: изучение методов решения задач нлп, особенностей, возникающих при использовании тех или иных методов решения;... |
| Урок информатики в 9 классе Тема «Оператор цикла с параметром» Цель урока: закрепление навыков решения задач с использованием циклических алгоритмов, знакомство с циклом «Для…» | | Разработка и исследование методов определения видимости полигонов... Целью диссертации является разработка метода, который бы позволил отрисовывать сцены, геометрическая сложность которых, в настоящее... |
| Рефераты №3 (2012 г.) Разработка, исследование и реализация методов совершенствования теплообменных аппаратов турбоустановок | | Решение теоретических задач (первая половина семестра, 7-8 заданий) Цель заданий — проверка усвоения знаний и получение навыка применения этих знаний для решения практических задач в области криптографических... |
