Материал: 2426

um=Индекс(min({(Lp1)u})). (3.61)

Функцией Индекс обозначено выполнение известного алгоритма определения номера минимального элемента одномерного массива

[74].

Рис. 3.15. Блок-схема алгоритма дискретной локальной оптимизации траектории

всреде с препятствиями для пяти учитываемых обобщенных координат груза

8.Оптимальные значения координат yp, zp, γp, ωp точки sp восстанавливаются по значению um из массива [tgu]:

yp=yum; zp=zum; γp=γum; ωp=ωum. (3.62)

Координата xp принимается равной

100

xp=xp1. (3.63)

9. Оптимизация по текущей точке sp завершается, и начинается оптимизация по следующей точке sp+1:

p=p+1. (3.64)

После выполнения п. 9. начинается выполнение с п. 1 с новым значением индекса p, который для каждой траектории изменяется в диапазоне p [2; (imax–1)]. После того, как p достигает значения (imax–1), по (3.19) определяется значение целевой функции Lopt для траектории Sopt на итерации opt.

Затем начинается следующий цикл оптимизации: p=2, 3,…, (imax–1) и.т.д. Оптимизация отдельной траектории прекращается при выполнении условия окончания расчета, которое заключается в снижении относительного убывания значения целевой функции на текущей итерации ниже заданного порогового значения δopt:

((Lopt–1)–Lopt)/(Lopt–1)≤δopt. (3.65)

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

тимизации: {Sq}Cq=1 .

Блок-схема алгоритма дискретной локальной оптимизации отдельной траектории приведена на рис. 3.15.

Алгоритм локальной дискретной оптимизации может быть применен в составе различных алгоритмов планирования траектории при сохранении постановки задачи.

3.6. Методика планирования траектории на основе генетического подхода

Генетические алгоритмы (ГА) хорошо зарекомендовали себя при решении широкого круга оптимизационных задач, особенно обладающих большой размерностью. Это обусловило целесообразность разработки модификации ГА, позволяющей решить поставленную в разделе 3.1 задачу планирования траектории движения груза в среде с препятствиями с учетом угловой ориентации.

101

Предлагаемая методика отличается от известных реализаций ГА тем, что генетические операции производятся над линейными и угловыми координатами груза в пространстве, образованном сочетанием всех его обобщенных координат, функция приспособленности – целевая функция произвольного вида, зависящая от всех обобщенных координат груза в узловых точках траектории (как частный случай целевой функции рассматривалась длина линейно-угловой траектории или СВД). Производится проверка возможности перемещений груза из начальной точки траектории в конечную с учетом препятствий произвольной формы, заданных дискретно в трехмерном евклидовом пространстве в виде набора точек на равномерной решетке.

Это обуславливает ряд отличий в терминологии предлагаемой методики от терминологии традиционных реализаций ГА, работающих с битовыми строками [61, 81, 91, 155]. В качестве генов рассматриваются вещественные значения линейных и угловых обобщенных координат груза в узловых точках траектории движения груза из начального положения в конечное. Индивидуумы (наборы хромосом) – траектории груза, описываемые как последовательные наборы координат узловых точек груза в пространстве его линейных и угловых обобщенных координат. При этом хромосома – вектор-строка из вещественных чисел-генов, задающая все обобщенные координаты груза в отдельной узловой точке на траектории. Популяция индивидуумов представляет собой набор траекторий, удовлетворяющих ограничениям на непересечение с препятствиями и на предельные значения линейных и угловых координат груза. Препятствия – это не только физические тела, но и определенная свободная область пространства, запрещенного для движения груза, примыкающая к физическим препятствиям. Отбор элитных особей подразумевает отбор наилучших траекторий по величине целевой функции.

Предлагается модифицированный алгоритм для поиска кратчайшего пути перемещения ГПК груза с учетом координат угловой ориентации в трехмерном пространстве с препятствиями. В качестве примера рассматривается 5 координат, определяющих положение груза в пространстве: 3 линейных координаты и 2 угла поворота груза. Данное сочетание координат описывает довольно распространенный частный случай положения груза в форме цилиндра. Предлагаемый алгоритм на основе генетического подхода для постановки задачи, изложенной в разделе 3.1, заключается в следующей последовательности шагов.

102

Описание алгоритма перемещения груза, положение которого определяют 3 линейные и 2 угловые обобщенные координаты [61, 81, 91]. Обобщенная блок-схема ГА представлена на рис. 3.16.

Рис. 3.16. Обобщенная блок-схема ГА

Предложенный алгоритм на основе генетического подхода заключается в следующей последовательности шагов:

1. Задание численных значений исходных данных: sнач=(xн0, yн0,

zн0, γн0, ωн0); sкон=(xк0, yк0, zк0, γк0, ωк0); { Rig }; imax; jmax; kmax; lmax; mmax;

[YПР]; G; C; E; M; cγω; u; δopt; lзап_г; lзап_в.

Параметры соответствуют описанным при постановке задачи в разделе 3.1, за исключением следующих собственных параметров алгоритма на основе генетического подхода, задаваемых эмпирически: G – количество итераций алгоритма; C – количество траекторий множества; E – количество наилучших отбираемых траекторий для рекомбинации; M – количество отбираемых траекторий для случайных изменений [155].

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i [1; imax]; k [1; kmax]; l [1; lmax]; m [1; mmax].

3. Генерируется случайным образом начальное множество траекторий. Для создания отдельной траектории при помощи генератора случайных чисел создается (imax–2) точек траектории с координатами:

103

где Rand – случайное число в интервале [0;1] с равномерным законом распределения.

Значения xp, yp, zp, γp, ωp, полученные для каждого значения p, должны удовлетворять условию непересечения груза с эквидистантной (полидистантной) поверхностью [YЭ], что через массив гиперповерхности Ymin описывается следующим условием:

yp≥Ymin(p,kp,lp,mp). (3.69)

При выполнении этого условия значение p увеличивается на 1, в противном случае генерация отдельной точки траектории по (3.67), (3.68) повторяется.

Первая (p=1) и последняя (p=imax) точки траектории будут совпадать с начальной и конечной заданными точками:

s1=sнач=(xн0, yн0, zн0, γн0, ωн0); simax=sкон=(xк0, yк0, zк0, γк0, ωк0). (3.70)

Отдельная траектория S компонуется как последовательность то-

чек

4.Оптимизируется начальное множество траекторий путем ло-

кальной оптимизации отдельных траекторий множества {Sq} при выполнении условия непересечения груза с эквидистантной (полидистантной) поверхностью вокруг препятствий по методике, изложенной

вразделе 3.4.

5.Определяется множество значений целевой функции {Lq} для каждой траектории множества {Sq} по (3.19).

6.Инициализируется значение переменной g счетчика итераций алгоритма:

g=1. (3.73)

104