ЭВОЛЮЦИОННЫЙ ПОПУЛЯЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

  • Б.К. Лебедев Южный федеральный университет
  • О.Б. Лебедев Южный федеральный университет
  • Е.О. Лебедева Южный федеральный университет
Ключевые слова: Транспортная задача, метаэвристика, кристаллизация россыпи альтернатив, оптимизация, популяционный алгоритм, коллективная память, агент, направленный поиск

Аннотация

Рассматривается эволюционный популяционный метод решения транспортной за-
дачи на основе метаэвристики кристаллизации россыпи альтернатив. Исследуется за-
крытая (или сбалансированная) модель транспортной задачи: сумма груза у поставщиков
равно общей сумме потребностей в пунктах назначения. Цель оптимизации – минимизация
стоимости (достижение минимума затрат на перевозку) или расстояний и критерий вре-
мени (затрачивается минимум времени на перевозку). В основу метаэвристики кристалли-
зации россыпи альтернатив положена стратегия, основанная на запоминании и повторе-
нии прошлых успехов. Стратегия делает упор на «коллективную память», под которой
подразумевается любой вид информации, которая отражает прошлую историю развития
и хранится независимо от индивидуумов. В качестве кода решения транспортной задачи
рассматривается упорядоченная последовательность Dk маршрутов. Объектами являют-
ся маршруты, альтернативами – множество позиций P в списке, где np – число позиций в
списке Dк. Множество объектов Dк соответствует множеству всех маршрутов. Множе-
ство альтернативных состояний P объекта соответствует множеству альтернативных
вариантов размещения объекта списке Dк. Работа популяционного эволюционного алго-
ритма кристаллизации россыпи альтернатив опирается на коллективную эволюционную
память, называемую россыпью альтернатив. Под россыпью альтернатив решения в рабо-
те называется структура данных, используемая в качестве коллективной эволюционной
памяти, несущая информацию о решении, включающую сведения о реализованных альтер-
нативах агентов в данном решении и о полезности решения. Разработан конструктивный
алгоритм формирования опорного плана путем декодирования списка Dк. На каждом шаге
t решается задача выбора очередного в последовательности Dк маршрута и определения
количества груза, перевозимого из пункта отправления Ai в пункт назначения Bj по этому
маршруту. Разработанный алгоритм является популяционным, реализующим стратегию
случайного направленного поиска. Каждый агент является кодом некоторого решения
транспортной задачи. На первом этапе каждой итерации l конструктивным алгоритмом
на базе интегральной россыпи альтернатив формируется nk кодов решений
Dk.Формирование каждого кода решения Dk выполняется последовательно по шагам путем
последовательного выбора объекта и позиции. Для построенного кода решения Dk рассчи-
тывается оценка решения ξk и оценка полезности δk. Формируется индивидуальная рос-
сыпь альтернатив Rk и переход к построению следующего кода решения.
На втором этапе итерации производится суммирования интегральной россыпи альтерна-
тив, сформированной на предыдущих итерациях от l до (l-1), cо всеми индивидуальными
россыпями альтернатив, сформированных на итерации l. На третьем этапе итерации l
производится снижение всех интегральных оценок полезности r*αβ интегральной россыпи
альтернатив R*(l) на величину δ*. Алгоритм решения транспортной задачи был реализован
на языке С++ в среде Windows. Сравнение значений критерия, на тестовых примерах, сизвестным оптимумом показало, что у 90% примеров полученное решение было оптималь-
ным, у 2% примеров решения были на 5% хуже, а у 8% примеров решения отличались ме-
нее, чем на 2%. Временная сложность алгоритма, полученная экспериментальным путем,
лежит в пределах О(n2).

Литература

1. Korbut A.A., Finkel'shteyn Yu.Yu. Diskretnoe programmirovanie [Discrete programming].
Moscow: Nauka: Gl. red. fiz.-mat. lit., 1969.
2. Venttsel' E.S. Issledovanie operatsiy: zadachi, printsipy, metodologiya: uchebnik dlya vuzov
[Operations research: tasks, principles, methodology: textbook for universities]. Moscow:
Drofa, 2004, 208 p.
3. Takha Kh.A. Vvedenie v issledovanie operatsiy [Introduction to operations research]. 7th ed.
Moscow: Izd. dom «Vil'yams», 2005.
4. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons:
Chichester, UK, 2005.
5. Yudin D.B., Gol'shteyn E.G. Zadachi i metody lineynogo programmirovaniya: Zadachi
transportnogo tipa [Problems and methods of linear programming: Problems of transport type].
Moscow: Izd. 3, 2013, 184 p.
6. Rudik I.D., Velichko V.V. Ponyatie, vidy i metody resheniya transportnoy zadachi [The concept,
types and methods of solving the transport problem], Mezhdunarodnyy studencheskiy
nauchnyy vestnik [International Student Scientific Bulletin], 2017, No. 4-4.
7. Dorigo M., Stützle T. Ant Colony Optimization. MIT Press: Cambridge, MA, 2004, 154 р.
8. Poli R. Analysis of the publications on the applications of particle swarm optimization, Journal
of Artificial Evolution and Applications: Article ID 685175, 2008, pp. 10-21.
9. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: Teoriya i praktika
[Search adaptation: Theory and practice]. Moscow: Fizmatlit, 2006, 272 p.
10. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh
proektirovaniya [Models of adaptive behavior of an ant colony in design problems]. Taganrog.
Izd-vo YuFU, 2013, 199 p.
11. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2016, 448 p.
12. Gladkov L.A., Gladkova N.V. Reshenie dinamicheskikh transportnykh zadach na osnove
gibridnykh intellektual'nykh metodov i modeley [Solving dynamic transport problems based
on hybrid intelligent methods and models], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 102-107.
13. Kureychik V.M., Kazharov A.A. Murav'inye algoritmy dlya resheniya transportnykh zadach
[Ant algorithms for solving transport problems], Izvestiya RAN. Teoriya i sistemy upravleniya
[Izvestiya RAS. Theory and control systems], 2010, No. 1, pp. 32-45.
14. Kureychik V.M., Emel'yanova T.S. Reshenie transportnykh zadach s ispol'zovaniem
kombinirovannogo geneticheskogo algoritma [Solving transport problems using a combined
genetic algorithm], Odinnadtsataya natsional'naya konferentsiya po iskusstvennomu intellektu
s mezhdunarodnym uchastiem KII-2008 [Eleventh National Conference on Artificial Intelligence
with International Participation СII-2008]. Moscow: Fizmatlit, 2008, pp. 158-164.
15. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ [Optimization
by the method of crystallization of a placer of alternatives], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7, pp. 11-17.
16. Lebedev B.K., Lebedev V.B. Metod kristallizatsii rossypi al'ternativ [The method of crystallization
of a placer of alternatives], Sb. nauchnykh trudov VII Mezhdunarodnoy nauchnoprakticheskoy
konferentsii «Integrirovannye modeli i myagkie vychisleniya v iskusstvennom
intellekte» [Collection of scientific papers of the VII International Scientific and Practical Conference
“Integrated Models and Soft Computing in Artificial Intelligence”]. Moscow: Izd-vo
Fizmatlit, 2013, pp. 903-912.
17. Lebedev B.K., Lebedev V.B. Global'naya trassirovka metodom kristallizatsii rossypi al'ternativ
[Global tracing by the method of crystallization of a placer of alternatives], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 42-51.
18. Lebedev B.K., Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh soedineniy
metodom kristallizatsii rossypi al'ternativ [Construction of the shortest binding connections by
the method of crystallization of a placer of alternatives], VI Vserossiyskaya nauchnotekhnicheskaya
konferentsiya «Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh
sistem – 2014»: Sb. trudov [VI All-Russian scientific and technical conference “Problems of
developing promising micro- and nanoelectronic systems – 2014”: Collection of works], under
the total. ed. academician of the RAS A.L. Stempkovskogo. Moscow: IPPM RAN, 2014,
pp. 177-183.
19. Mourelle M. Swarm intelligent systems. Berlin: Heidelberg: Springer, 2006, 217 p.
20. Cong J., Romesis M., Xie M. UCLA Optimality Study Project. Available at:
http://cadlab.cs.ucla.edu/~pubbench. 2004.
21. MCNC Electronic and Information Technologies (Online). Available at: www.mcnc.org.
Опубликован
2022-11-01
Выпуск
Раздел
РАЗДЕЛ II. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ