ИССЛЕДОВАНИЕ ОСНОВНЫХ ПАРАМЕТРОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ПРИМЕНИТЕЛЬНО К ЗАДАЧЕ ПОИСКА ОПТИМАЛЬНОГО МАРШРУТА
Аннотация
Статья посвящена развитию и улучшению точности работы систем автоматизированного управления морскими судами, использующих генетический алгоритм. Любая система автоматизированного управления начинается с решения задачи, с которой повсеместно сталкивается судоводитель в ходе своей деятельности - поиску оптимального маршрута. Данная задача является глобальной, содержит множество решений и не требует абсолютной точности. Для решения подобной задачи наилучшим образом подходит генетический алгоритм, представляющий собой эвристический алгоритм глобального поиска. Данный алгоритм оперирует различными генетическими операторами, такими как скрещивание, мутация, селекция, генерация популяций и поколений. Данные операторы могут быть адаптированы под нужды судовождения - поиска оптимального маршрута. Таким образом, генотип как оперируемая алгоритмом величина может быть представлен в виде маршрута, состоящего из отстоящих друг от друга путевых точек. Далее посредством применения генетических операторов маршруты создаются и преобразуются до тех пор, пока не будет найден оптимальный маршрут, избегающий всякого рода навигационные опасности. Однако сам механизм поиска сильно зависит от коэффициентов, которые задают режим работы генетических операторов. Эффективность данного способа решения навигационной задачи напрямую зависит от выбранных коэффициентов, делающих решение задачи быстрым и надежным либо полностью лишающих алгоритм работоспособности. Т. е. перед непосредственным применением алгоритма в условиях судовождения необходимо выявить основные закономерности между используемыми коэффициентами, а также определить оптимальные значения, при которых работа алгоритма будет наиболее эффективной.
Ключевые слова
генетический алгоритм, поиск оптимального пути, размер популяции, коэффициент скрещивания, коэффициент мутации
Читать полный текст статьи: PDF
Список литературы
Chauvin C. Human and organisational factors in maritime accidents: Analysis of collisions at sea using the HFACS / C. Chauvin, S. Lardjane, G. Morel, J.-P. Clostermann, B. Langard // Accident Analysis & Prevention. - 2013. - Vol. 59. - Pp. 26-37. DOI: 10.1016/j.aap.2013.05.006.
Tsou M. C. The study of ship collision avoidance route planning by ant colony algorithm / M. C. Tsou, C. K. Hsueh // Journal of Marine Science and Technology. - 2010. - Vol. 18. - № 5. - Pp. 746-756. DOI: 10.6119/JMST.
Goldberg D. E. Genetic algorithms and machine learning / D. E. Goldberg, J. H. Holland // Machine learning. - 1988. - Vol. 3. - Is. 2-3. - Pp. 95-99. DOI: 10.1023/A:1022602019183.
Курейчик В. М. Генетические алгоритмы / В. М. Курейчик // Известия ЮФУ. Технические науки. - 1998. - № 2 (8). - С. 4-7.
Федоренко К. В. Поиск оптимального маршрута с применением генетических алгоритмов / К. В. Федоренко // Материалы VII Межвузовской научно-практической конференции аспирантов, студентов и курсантов. - СПб., 2017. - C. 344-347.
Басова А. В. Генетические методы решения задачи оптимального планирования грузовых морских перевозок / А. В. Басова, П. Г. Белявский // Вестник Донского государственного технического университета. - 2011. - Т. 11. - № 5 (56). - С. 630-632.
Шейкин Т. Ю. Генетический и муравьиный алгоритмы для задачи размещения шлюзов в сети навигационных знаков / Т. Ю. Шейкин // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2013. - № 3 (22). - С. 14-19.
Кузнецов А. Л. Метод генетических химер для решения задачи рационализации маршрутов морской транспортировки / А. Л. Кузнецов, А. В. Кириченко, Г. Б. Попов // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. - 2017. - Т. 9. - № 3. - С. 456-467. DOI: 10.21821/2309-5180-2017-9-3-456-467.
Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence / J. H. Holland. - MIT press, 1992. - 207 p.
Melanie M. An introduction to genetic algorithms / M. Melanie. - Fifth printing. - The MIT Press, 1999. - 158 p.
Back T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms / T. Back. - Oxford university press, 1996. - 307 p.
Гладков Л. Генетические алгоритмы / Л. Гладков, В. Курейчик, В. Курейчик. - М.: Физматлит, 2006. 2017. - 320 с.
Еремеев А. В. Генетические алгоритмы и оптимизация / А. В. Еремеев. - Омск: Изд-во Омского гос. ун-та, 2008. - 48 с.
Об авторах
Федоренко Кирилл Владимирович - аспирант
Морской государственный университет имени адмирала Г.И. НевельскогоОловянников Аркадий Львович - кандидат технических наук, доцент
Морской государственный университет имени адмирала Г.И. Невельского
