Материал: 2426
Дальнейшие пункты алгоритма (пп. 7–12) выполняются многократно в итерационном цикле g [1; G].
7. Отбираются траектории из множества {Sq} по возрастанию значений целевой функции Lq. После сортировки
L1<L2<…<LC–1<LC; L*=L1; S*=S1. (3.74)
8. Осуществляется подбор траекторий для рекомбинации. Используется наиболее распространенный, простой для алгоритмической реализации и универсальный оператор отбора – панмиксия с
предварительной селекцией и отбором усечения (Truncation selection)
на определенном отрезке траекторий множества с наименьшим значением функции приспособленности [155], например [1; C/2]. В данном примере количество отбираемых для рекомбинации траекторий из исходного полного множества траекторий E= C/2. Значение E может быть задано произвольно в пределах E [2; C/2].
Селекция состоит в том, что для рекомбинации выбираются траектории, значение приспособленности которых не меньше пороговой величины, например значения приспособленности «срединной» особи SC/2. Число траекторий для рекомбинации выбирается в соответствии с порогом [1; E]. Порог определяет, какое число траекторий, начиная с самой первой (самой оптимальной), будет принимать участие в рекомбинации. Такой подход обеспечивает более быструю сходимость алгоритма [61, 81, 91, 155, 226].
Каждому члену промежуточного множества траекторий, отобранных для рекомбинации {Sr}, r [1; E], соответствует случайное целое число dr на отрезке [1; E], которое будет номером второй траектории из этого же промежуточного множества, принимающей участие в рекомбинации:
dr= Rand∙E . |
(3.75) |
9. Дискретная рекомбинация (Discrete recombination) траекторий промежуточного множества {Sr} осуществляется путем случайного обмена точками траектории по оригинальной модели, заимствующей некоторые специфические свойства модели генитор (Genitor) [155, 249, 252]. Исследования, проведенные рядом зарубежных авторов, показали, что поиск гиперплоскостей при использовании генитора происходит лучше, а сходимость быстрее, чем у классического ГА
[249, 252].
В предлагаемой модели, так же как в модели генитор, из пары случайных исходных траекторий синтезируется только одна новая
105
траектория. Эта новая траектория заменяет не одну из исходных, а одну из худших по значению целевой функции траекторий. Отличие предлагаемой модели от модели генитор заключается в том, что при гениторе на каждом шаге ГА в множестве обновляется только одна траектория, а в предлагаемой модели для ускорения сходимости на каждом шаге обновляется (C–E) неоптимальных траекторий исходного множества [249, 252].
Введены обозначения: ap – точка первой исходной траектории, отобранной для рекомбинации, с номером r из промежуточного множества, ap = sp , где (sp Sr ); bp – точка второй исходной траектории с
номером dr из промежуточного множества, bp = sp , где (sp Sdr ); cp –
точка вновь полученной траектории с номером Er из полного множества траекторий, cp = sp , где (sp SEr ); Er=E+r.
Рекомбинации подвергаются все точки отобранных в {Sr} исходных траекторий, кроме первой и последней: p [2; (imax–1)]. Выбор исходной траектории, точка с номером p которой переходит в новую траекторию, определялся случайным образом с равной вероятностью:
ìbp |
при Rand > 0,5; |
|
|
cp = í |
при Rand £ |
0,5. |
(3.76) |
îap |
|
||
Траектория, полученная в результате рекомбинации траектории с номером r с траекторией с номером dr, занимает в исходном множестве место траектории с номером Er, не участвующей в рекомбинации.
10. Осуществляется отбор части траекторий полного множества для случайных изменений. Отбор членов промежуточного множества {Sev}, v [2; M] для случайных изменений производится способом
случайной выборки среди всех членов полного множества, за исключением самой первой оптимальной траектории (S*=S1), по закону равномерного распределения. Номер ev каждой траектории из полного множества, входящей в промежуточное множество {Sev}, подвергае-
мое случайным изменениям, определяется по зависимости
ev=1+ Rand∙M , v [2; M]. |
(3.77) |
11. Осуществляется случайное изменение траекторий промежуточного множества {Sev} путем вставки сформированных случайным
образом по (3.67), (3.68) с проверкой условия (3.69) точек траектории на место исходных точек:
106
sp=smp, p [2; (imax–1)], |
(3.78) |
где smp=(xmp, ymp, zmp, γmp, ωmp) – сформированная случайным образом по (3.67), (3.68) с проверкой выполнения условия (3.69) точка траектории.
Случайное изменение траекторий в ГА предотвращает преждевременное схождение алгоритма к локальному оптимуму (субоптимальному решению).
12. Осуществляется переход к следующей итерации алгоритма:
g=g+1, g [1; G]. |
(3.79) |
Если выполняется условие завершения работы алгоритма
g≥G, |
(3.80) |
осуществляется переход к п. 13, в противном случае – к п. 7.
13. Выполняется локальная оптимизация лучшей траектории S* по методике, изложенной в разделе 3.5. При этом траектория обновляется.
|
Пуск |
1 |
|
2 |
|
||
|
|
|
|
|
|
|
|
Ввод исходных данных: (xн0, yн0, zн0, сн0, ωн0); (xк0, yк0, zк0, γк0, ωк0); G; C; E; M; |
|
||||||
|
imax; jmax; kmax; lmax; mmax; { R }; [YПР]; cγω; u; δopt; lзап_г; lзап_в |
|
|
||||
|
ig |
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
Построение массива гиперповерхности [Ymin] по методике раздела 3.4 |
|
|
||||
|
|
|
|
q=1:С |
4 |
|
1 |
|
|
|
|
5 |
|
||
|
|
|
|
|
|
|
|
|
|
|
s1=sнач=(xн0, yн0, zн0, γн0, ωн0) |
|
|
||
|
|
|
|
|
6 |
|
|
|
|
|
|
p=2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
jp=
Rand∙jmax
; kp=
Rand∙kmax
; lp=
Rand∙lmax
; mp=
Rand∙mmax
; xp=p∙Δl; yp= jp∙Δl; zp=kp∙Δl; γp=(lp–0,5∙lmax)∙Δu; ωp=(mp–0,5∙mmax)∙Δu
8 yp≥Ymin(p,kp,lp,mp) Нет
Да 9 p=p+1
|
11 |
Да |
10 |
Нет |
|
si |
=sкон=(xк0, yк0, zк0, γк0, ωк0) |
p>(imax–1) |
|||
|
|
||||
|
max |
|
|
|
Рис. 3.17. Блок-схема модифицированного алгоритма на основе генетического подхода для пяти учитываемых обобщенных координат груза (начало)
107
1
11
Локальная оптимизация траекторий {Sq}, q [1;С] по методике раздела 
3.4
13
g=1:G
14
Сортировка траекторий {Sq} по возрастанию Lq. Выделение S*, L*
15 r=1:E
16
dr=
Rand∙E
; Er=E+r
17 p=2:(imax–1) 18
ìbp |
при Rand > 0,5; |
cp = í |
при Rand £ 0,5; |
îap |
ap Î Sr ; bp Î Sdr ; cp SEr
12
Определение множества значений функции приспособленности {Lq} множества траекторий по (3.19)
19
v=2:M
20 ev=1+ Rand∙M
p=2 21
22
jp=
Rand∙jmax
; kp=
Rand∙kmax
;
lp=
Rand∙lmax
; mp=
Rand∙mmax
; xmp=p∙Δl; ymp=jp∙Δl; zmp=kmp∙Δl;
γmp=(lp–0.5∙lmax)∙Δu; ωmp=(mp– –0,5∙mmax)∙Δu
23 ymp≥Ymin(p,kp,lp,mp) Нет
|
Да |
24 |
|
|
p=p+1 |
|
|
Да |
p>(imax–1) |
25 |
|
|
|
|
|
|
Нет |
26 |
|
sp=smp=(xmp, ymp, zmp, γmp, ωmp)
28 |
27 |
Вывод результатов (лучшая |
|
Останов |
траектория S*, L*) |
Рис. 3.17. Блок-схема модифицированного алгоритма на основе генетического подхода для пяти учитываемых обобщенных координат груза (окончание)
14.Определяется уточненное значение целевой функции L* оптимизированной лучшей траектории S* по (3.19).
15.Вывод результатов: L*, S*. Окончание работы алгоритма. Блок-схема модифицированного алгоритма на основе генетиче-
ского подхода приведена на рис. 3.17. Вычислительные реализации модифицированного алгоритма и описанной методики на его основе в средах Microsoft Visual C++ и MATLAB показали работоспособность и эффективность алгоритма для решения поставленной задачи [61, 81, 91].
108
3.7. Методика планирования траектории на основе модифицированного алгоритма роевого интеллекта
Алгоритмы роевого интеллекта относятся к современному направлению искусственного интеллекта – природным вычислениям (Natural Computing) и отличаются высокой эффективностью [62, 85,
110, 199, 217].
Эти алгоритмы доказали свою применимость при решении различных комбинаторных задач на графах. В основу любого алгоритма положена вероятностная эвристическая функция. Каждый агент перемещается по графу независимо от других агентов, руководствуясь при выборе пути достаточно простыми правилами. В то же время происходит косвенный обмен информацией между агентами за счет феромона, оставляемого каждым агентом на ребрах графа или в его вершинах при прохождении. В результате вершины или ребра, входящие в более краткие маршруты, будут накапливать большее коли-
чество феромона [62, 85, 110, 199, 217].
Проведенный анализ состояния вопроса показал целесообразность применения данного вида алгоритмов для решения задачи планирования траектории груза.
Для поставленной в разделе 3.1 задачи предлагается две модификации алгоритма роевого интеллекта на взвешенном графе, адаптированном для поиска кратчайшего пути перемещения ГПК груза с учетом его координат угловой ориентации в трехмерном пространстве с препятствиями: последовательная и с распараллеливанием.
Для описания пространства состояний груза на равномерной дискретной решетке координат формируется граф Gr=(Sr, Er), где Sr={s1,
s2,…, sng} – множество вершин графа; Er = {(s |
, s |
j1 |
) ng |
– множество |
i1 |
|
i1, j1=1 |
|
ребер. Общее количество вершин графа определяется количеством рассматриваемых точек равномерной сетки координат:
ng=imax∙jmax∙kmax∙lmax∙mmax.
Необходимо найти оптимальную траекторию с минимальным значением целевой функции L* из начальной вершины sнач в конечную вершину sкон, представляющую собой последовательность из смежных
вершин на равномерной решетке S={sp}ipmax=1 . Каждой вершине графа
соответствует определенное пространственное линейно-угловое положение груза.
Модифицированный алгоритм роевого интеллекта в последовательном исполнении [62, 85, 110].
109