Оптимизация поиска деревьев Штейнера в потоковой задаче Штейнера
Аннотация
Для потоковой задачи Штейнера на транспортной сети ранее был разработан двухуровневый композитный эволюционный алгоритм: на верхнем уровне ищется топология дерева, на нижнем – оптимальные координаты точек Штейнера для дерева с заданной топологией. В настоящей статье для решения задачи нижнего уровня предлагается вещественный эволюционный алгоритм, использующий модель онтогенеза. В нем применяется специальный оператор развития, основанный на случайной модификации метода покоординатного спуска, адаптированного для потоковой задачи.
Ключевые слова
Полный текст:
PDFЛитература
Гилберт Э.Н., Поллак Г.О. Минимальные деревья Штейнера. Кибернетический сборник, новая серия. Вып. 8. М.: Мир, 1971. C. 19–49.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982. 416c.
Кукин В.Д. Генетические операторы эволюционной модели для потоковой задачи Штейнера. Известия РАН. ТиСУ. 2010. №2. С. 74–80.
Кукин В.Д. Гипотеза о «большой долине» для потоковой задачи Штейнера. Известия РАН. ТиСУ. 2015. №1. С. 72–78. doi: 10.7868/S0002338815010096
Кукин В.Д. Локальная оптимизация лесотранспортной сети с помощью аналога задачи Штейнера. Системы автоматизированного проектирования лесотранспорта и лесомелиорации. Петрозаводск: Карельский филиал АН СССР. 1984. С. 12–17.
Кукин В.Д. Эволюционная модель для задачи Штейнера с потоками и зависящими от них весами. Известия РАН. ТиСУ. 2008. №3. С. 115–123.
Кластер КарНЦ РАН: cluster.krc.karelia.ru.
Лотарев Д.Т., Супрун А.В., Уздемир А.П. Локальная оптимизация в задаче Штейнера на евклидовой плоскости. Автоматика и телемеханика. 2004. Вып.7. С. 60–70.
Оре О. Теория графов. М.: Наука, 1980. 336с.
Растригин Л.А. Системы экстремального управления. М.: Наука, 1974. 630c.
Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society. 1990. Vol. 41, iss. 11. P. 1069–1072. doi: 10.1057/jors.1990.166
Herrera F., Lozano M., Verdegay J.L. Tackling Real-coded Genetic Algorithms: Operators and Tools for Behavioural Analysis. Artificial Intelligence Review. 1998. Vol.12, iss. 4. P. 265–319. doi: 10.1023/A:1006504901164
Michalewicz Z., Logan T.D., Swaminathan S. Evolutionary operators for continuous convex parameter space. Proceedings of the 3rd Annual Conference on Evolutionary Programming. 1994. P. 84–97. doi: 10.1142/9789814534116
REFERENCES
Gilbert E.N., Pollak H.O. Steiner minimal trees. SIAM J. Appl. Math. 1968. Vol. 16, iss. 1, P. 1–29.
Garey M.R., Johnson D.S. Computers and Interactability: A Guide to the Theory of NP completeness. Freeman, San Francisco, 1979; Mir,
Moscow, 1982. 416p.
Kukin V.D. Genetic operators of an evolutionary model for the Steiner flow problem. Journal of Computer and Systems Sciences International. 2010. Vol. 49, iss. 2. P. 227–233. doi: 10.1134/S1064230710020085
Kukin V.D. The Big Valley conjecture for the flow Steiner tree problem. Journal of Computer and Systems Sciences International. 2015. Vol. 54, iss. 1. P. 69–76. doi: 10.1134/S1064230715010098
Kukin V.D. Lokalnaya optimizatsiaya lesotransportnoy seti s pomoschju analoga zadachi Shteinera [Local optimization of a forest transportation network with the help of an analogue of the Steiner problem]. CAD Systems for forest transport and forest reclamation.
Petrozavodsk. 1984. P. 12-17.
Kukin V.D. Evolutionary model for the Steiner tree problem with flow-dependent weights. Journal of Computer and Systems Sciences
International. 2008. Vol. 47, iss. 3. P. 447–454. doi: 10.1134/S1064230708030143
Link for the KarRC RAS cluster: http://cluster.krc.karelia.ru/index.php?plang=e.
Lotarev D.T., Suprun A.V., Uzdemir A.P. Local optimization in the Steiner problem on the Euclidean plane. Automation and Remote Control. 2004. Vol. 65, iss. 7. P. 1089–1098. doi: 10.1023/B:AURC.0000038715.76668.83
Ore O. Theory of Graphs. Am. Math. Soc., Providence, RI.1962: 279p.
Rastrigin L.A. Sistemi ekstremalnogo upravleniya [Systems of extremal control]. Nauka, Moscow, 1974. 630p.
Beasley J.E. OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society. 1990. Vol. 41,
iss. 11. P. 1069–1072. doi: 10.1057/jors.1990.166
Herrera F., Lozano M., Verdegay J.L. Tackling Real-coded Genetic Algorithms: Operators and Tools for Behavioural Analysis. Artificial Intelligence Review. 1998. Vol.12, iss. 4. P. 265–319. doi: 10.1023/A:1006504901164
Michalewicz Z., Logan T.D., Swaminathan S. Evolutionary operators for continuous convex parameter space. Proceedings of the 3rd Annual Conference on Evolutionary Programming. 1994. P. 84–97. doi: 10.1142/9789814534116
DOI: http://dx.doi.org/10.17076/mat816
Ссылки
- На текущий момент ссылки отсутствуют.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
© Труды КарНЦ РАН, 2014-2019