Материал: 1831

Ynp(i,k)=8,0 УЛЕ - при (49<i<51) и (50<k<100);

Ynp(i,k)=8,0 УЛЕ - при (79</<81) и (1<k<50);

Ynp(i,k)=0,0 УЛЕ - в остальных случаях.

Груз в форме цилиндра с габаритными размерами: габаритный диаметр 0,5 УЛЕ, и высота 2,0 УЛЕ, был представлен в виде набо­ ра точек (сг=12) на поверхности объемного те­ ла с координатами в УЛЕ: {Rig}={[0,25;0;1;1]; [0,25;0;0;1]; [0,25;0;-1;1]; [-0,25;0;1;1]; [- 0,25;0;0;1]; [-0,25;0;-1;1]; [0;0,25;1;1]; [0;0,25;0;1]; [0;0,25;-1;1]; [0;-0,25;1;1]; [0; - 0,25;0;1]; [0;-0,25;-1;1]}.

Для каждой траектории объекта, найденной в отдельном независимом эксперименте (рису¬ нок 2),определялись собственные значения целевой функции (L до локальной оптимиза­ ции, L* после локальной оптимизации), инфор­ мационной длины исследуемого алгоритма Me и времени поиска 7"р.

Проведение вычислительных эксперимен¬ тов на тестовом примере с детерминирован¬ ным расположением препятствий позволило обосновать рациональные значения основных внутренних параметров соответствующих ал¬ горитмов с элементами вероятностного выбора для решения поставленной задачи и для по¬ следующего сравнения с детерминированными алгоритмами. Ввиду ограниченного объема статьи результаты вычислительных экспери¬ ментов на тестовом примере с детерминиро¬ ванным расположением препятствий не приво¬ дятся.

Была проведена серия из 10000 компью¬ терных экспериментов, моделирующих про¬ цесс поиска оптимальной траектории переме¬ щения объекта в среде с полидистантными поверхностями, построенными вокруг реаль¬ ных поверхностей препятствий [Ynp], сформи¬ рованных случайным образом из сочетания нескольких параллелепипедов, каждый из ко¬ торых имел случайные размеры.

Число параллелепипедов n в каждом экс¬ перименте генерировалось по равномерному закону распределения случайной величины в интервале от 1 до 15. Размеры каждого парал¬ лелепипеда формировались в пределах (xxyxz) от 0x0x0 УЛЕ до 4x5x4 УЛЕ также по равномерному закону распределения. Допус¬ калось перекрытие объемов и поверхностей параллелепипедов при их наложении.

Для каждого эксперимента определялись пу¬ тем непосредственных вычислительных измере¬ ний, реализованных программно, значения 7p и

10

б)

Рис. 2. Примеры найденной алгоритмом на основе генетического подхода (№ 3)

траектории: а) до локальной оптимизации (L); б) после локальной оптимизации (L*)

Me, и рассчитывалось по результатам вычисли­ тельных измерений значение 8Lycn:

8Lyci= ^*^усл)-100%,где Lycn - условный глобаль¬ ный оптимум решения задачи, определяемый как минимальное значение из множества значений целевой функции, полученных при использова¬ нии различных методик, но для одних и тех же численных значений исходных данных задачи

[Yn p]:

L^minUL*)}, ie [1; 5],где i - номер применяе¬ мой методики на основе: 1 - направленного волнового алгоритма; 2 - алгоритма роевого интеллекта; 3 - генетического подхода; 4 - ал¬ горитма декомпозиции линейных и угловых координат; 5 - алгоритма вероятностной до¬ рожной карты.

Некоторые результаты сравнительного анализа методик и алгоритмов по принятым критериям оценки эффективности приведены на рисунке 3. Исследования проводились на программных реализациях методик и алгорит-

мов в среде MS Visual C++ на ПК средней про­ изводительности (AMD Athlon 64 X2 Dual Core Processor 5600+ 2.90 GHz, RAM 4,00 ГБ).

Поскольку использовалось 3 самостоятель­ ных критерия оценки алгоритмов и методик, ре-

Рис. 3. Результаты сравнительного анализа мето­ дик и алгоритмов по принятым критериям оценки эффективности: 1 - направленный волновой алго­ ритм; 2 - алгоритм роевого интеллекта; 3 - алго­ ритм на основе генетического подхода; 4 - алго­ ритм декомпозиции линейных и угловых координат; 5 - алгоритм вероятностной дорожной карты; Ш - математическое ожидание значения времени рас¬ четов распараллеленных алгоритмов 2 и 4, верх¬ ний пределДля этого было проведено масштаби­ рование отображаемых результатов экспери­ ментов по максимальным полученным значе-

зультаты анализа были интерпретированы гра¬ фически в удобном для восприятия и нагляд¬ ном виде, как совокупность векторов в трехмер¬ ном пространстве координат [ Тр Me 8Lycn ].

ниям каждого критерия. Векторное представ¬ ление разработанных алгоритмов и методик по принятым критериям эффективности как компонентам векторов, а также проекции векто¬ ров на три плоскости ([ Тр Me], [ Тр дЕусл ], [Me

8L ]) приведены на рисунке 4.

Мб

Рис. 4. Векторное представление критериев эффективности

разработанных алгоритмов и методик

При сравнении алгоритмов по принятым критериям оценки эффективности, в трех¬ мерном пространстве положений векторного критерия эффективности могут быть выделе¬ ны отдельные области, соответствующие оп­ тимальному значению какого-либо одного, двух или всех трех компонент вектора, определяе¬ мые условиями вида:

Т р < ( Т р ) m a x ; Me<(Me)max; Щсл < ( Щсл ) m a x ^

(Тр )max; (Me)max; ( d ^ * , )max - максимальные пре¬ дельно допустимые (заданные) значения кри¬

териев.

Соответственно можно выделить область условно быстрых алгоритмов, область ус¬ ловно точных алгоритмов и область условно компактных (т.е. занимающих малый объем в памяти ПК) алгоритмов (рисунок 5, а, б, в).

Вкачестве примера, при (Тр )max=5 с;

(Me)max=2 Мб; (дЕусл )max=5% К условно быстрым

алгоритмам могут быть отнесены 1, 3 и 5 алго­ ритмы, к условно точным 1 и 4 алгоритмы, к условно компактным 2, 3 и 5 алгоритмы. В слу­ чае распараллеливания алгоритмов 2 и 4, они также попадают в область условно быстрых.

Заключение

Ни один из разработанных алгоритмов не удовлетворяет условию оптимальности по всем трем критериям одновременно, т.е. не входит в область пересечения условно быст¬ рых, условно точных и условно компактных ал¬ горитмов (см. рисунок 5, г), однако отдельные алгоритмы оптимальны по двум критериям. В частности, алгоритмы 3 и 5 одновременно бы¬ стрые и компактные, причем алгоритм 3 в большей степени. Алгоритмы 1 и распаралле­ ленный 7 одновременно быстрые и точные, причем алгоритм 1 в большей степени.

Результаты сравнения алгоритмов под­ тверждают предположение о том, что сущест¬ вует взаимосвязь между оптимальностью ал¬ горитма, которая в данном случае выражается

его точностью 8 Lу с л , и сложностью алгоритма (временной или пространственной), которая в

данном случае выражается через критерии Тр

и Me . Т.е. невозможно упростить алгоритм (временную либо пространственную слож¬ ность, которые также взаимосвязаны между собой), не жертвуя при этом его оптимально¬ стью, что хорошо иллюстрируется алгоритмом на основе генетического подхода (№ 3).

Учитывая, что при современном уровне развития компьютерной техники требование компактности не является критичным в диапа¬ зоне значений всех рассматриваемых алго¬ ритмов (не более 6 Мб), следует отметить на¬ правленный волновой алгоритм (№ 1) как наи¬ более точный и в то же время достаточно бы¬ стрый. В пользу его перспективности для ре¬ шения поставленной задачи говорит и тот факт, что это детерминированный алгоритм в отличие от всех остальных, кроме алгоритма № 7. Этот алгоритм находит единственно воз¬ можное и постоянное решение задачи при од¬ них и тех же численных значениях исходных данных.

Библиографический список

1. Щербаков, В.С. Использование алгоритмов поиска пути перемещения груза автокраном на гра­ фах / В.С. Щербаков, М.С. Корытов // Вестник Воро­ нежского государственного технического университе­ та, 2009. - Т.5. - № 5. - С. 37-41.

2.Щербаков, В.С. Поиск оптимальной траекто¬ рии груза, перемещаемого автокраном, в среде с произвольными препятствиями, с учетом координат угловой ориентации в трехмерном пространстве / В.С. Щербаков, М.С. Корытов // Вестник Брянского государственного технического университета, 2009. -

№4 (24). - С. 48-51.

3.Щербаков, В.С. Методика поиска субопти¬ мальной траектории движения объекта в трехмерной среде с произвольными препятствиями с учетом ко¬ ординат угловой ориентации / В.С. Щербаков, М.С. Корытов // Вестник СибАДИ, 2009. - Вып. 4 (14). - С. 5-10.

4.Корытов, М.С. Декомпозиция обобщенных ко¬ ординат при решении задач оптимизации траектории перемещения груза // Вестник МАДИ (ГТУ), 2010. - Вып. 3(22). - С. 32-35.

5.Щербаков, В.С. Использование генетических алгоритмов для поиска оптимальной траектории пе¬ ремещения груза / В.С. Щербаков, М.С. Корытов // Вестник КГТУ им. А.Н. Туполева, 2010. - № 3. - С. 155-158.

6.Щербаков, В.С. Об одной модификации алго¬ ритма муравьиных колоний для планирования траек¬ тории перемещения груза в пространстве с препятст¬ виями с учетом угловой ориентации / В.С. Щербаков, М.С. Корытов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2010. - №

3.- С. 143-151.

9.Щербаков, В.С. Влияние стохастических па¬ раметров пространства с препятствиями на длину траектории груза, перемещаемого грузоподъемным краном / В.С. Щербаков, М.С. Корытов // Вестник СибАДИ, 2009. - Вып. 3 (13). - С. 13-17.

10.Корытов, М.С. Использование полидистант¬ ных поверхностей в задаче поиска пути перемещения груза в среде с препятствиями // Материалы 64-й на¬ учно-технической конференции ГОУ «СибАДИ». - Омск: СибАДИ, 2010. - Кн. 1. - С. 302-306.

A comparative analysis of scheduling algorithms trajectory of an object given its angular coordinates in three-dimensional space with obstacles

V.S. Shcherbakov, M.S. Korytov

Some results of comparative analysis of algo­ rithms for planning optimal trajectories move an object of arbitrary shape, given its angular orien¬ tation in three-dimensional space with arbitrary obstacles, given in a discrete form.

Щербаков Виталий Сергеевич - доктор техн. наук, профессор, декан факультета «Нефтега­ зовая и строительная техника» Сибирской госу­ дарственной автомобильно-дорожной академии. Основное направление научных исследований -