Применение генетических алгоритмов для эффективного решения задачи навигации (1187414), страница 6
Текст из файла (страница 6)
При совершении внутреннего действия оно становится внутренним наблюдением.Процесс повторяется до срабатывания гена из Go , то есть гена с внешним действием.Для генов из Gi и Gio отклик p(ω) вычисляется по правилам модели G0 . Для удобствасформулируем отклик внутреннего условия µ в виде аналога предиката нечеткой логикиpµ : R+ → R:"!#XXpµ (m) =(79)|m[n + k] − µ[n]| − skn+Процедуры генерации, мутации, скрещивания как и общая процедура эволюции полностью совпадают с процедурами в однослойной LCS.Подробное описание алгоритма LCS и его свойств можно найти в [24].3.4Мета-модельВ этой части мы рассмотрим дополнение к модели G0 , основанное на следующей неформальной гипотезе: для встречающихся на практике наборов задач отображения близкиек оптимальному являются слабым возмущением «наивного» алгоритма.Вспомним, что предикаты базовой модели формулируются в виде:p=c⊗pДля того, чтобы учесть гипотезу мы рассмотрим предикаты базовой системы как отдельные эвристики, а предикаты гена как композицию эвристик.
Исходя из этой интерпретации несложно расширить модель:Определение 16. Пусть задан набор отображений {Ai ∈ AO }Ni=1 . Каждой паре (Ai , a),где a ∈ A, сопоставим предикат:paAi (ω) = 2I[Ai (ω) = a] − 1Модель Gm будем называть мета-расширением модели G эвристиками Ai :Gm = G0 ∪ paAi | a ∈ A, i = 1, . . . , N28(80)(81)Algorithm 8 Функции Evolve для алгоритма LCSRequire: ρ1 — начальный вес генов; Nmax — максимальный размер генома;Generation(), Generation(·), Mutation(·), Mutation(·, ·), Crossover(·, ·) — функции генерации, мутации, их адаптивные версии и функция скрещивания, αg , αm , αc —доли генераций, мутаций и скрещиваний, DrawDescrete(X, p) — функция генерацииреализаций случайных величин со значениями из X c распределением пропорциональным вектору p.1: function Evolve(G, ω, ρ, f )2:G0 := G3:N = Nmax − |G|4:ρ0 := ρ5:for i = 1, .
. . , αg N do6:if ω = NULL then7:g = Generation()8:else9:g = Generation(ω)10:end if11:G0 := G0 ∪ {g}12:ρ[g] = ρ113:end for14:response := []15:for g ∈ G do16:(p, ·) = g17:if ω 6= NULL then18:response[g] = [p(ω)]+19:else20:response[g] = 121:end if22:end for23:for i = 1, . . . , αm N do24:g0 = DrawDescrete(G, response)25:if ω = NULL then26:g = Mutation(g0 )27:else28:g = Mutation(g0 , ω)29:end if30:G0 := G0 ∪ {g}31:ρ[g] = ρ132:end for33:for i = 1, . . .
, αc N do34:g1 = DrawDiscrete(G, response)35:g2 = DrawDiscrete(G, response)36:g = Crossover(g1 , g2 )37:G0 := G0 ∪ {g}38:ρ[g] = ρ139:end for40:return (G0 , ρ0 )41: end function29Algorithm 9 Однослойная LCS со схемой голосованияRequire: α — скорость обучения; w(·) — весовая функция;1: function Feedback((G, ρ, ĝ, ωp ), f )2:(·, â) = ĝ3:ρ0 = []4:for g ∈ G do5:(p, a) := g6:ρ0 [g] := ρ[g] + I[a = â ∧ p(ωp ) > 0] · αw(ρ[g])p(ωp )f7:end for8:9:10:11:(G0 , ρ00 ) := Select(G, ρ0 )(G00 , ρ000 ) := Evolve(G0 , ωp , ρ00 , f )return (G00 , ρ000 )end function12:13:14:15:16:function Response(G, ρ, ω)response := []for a ∈ A doresponse[a] := 0end for17:18:19:20:21:22:23:for g ∈ G do(p, a) := gr := p(ω)w(ρ[g])if r > 0 thenresponse[a] := response[a] + rend ifend for24:25:26:27:28:29:30:31:maxResponse := −∞â := NULLfor a ∈ A doif response[a] > maxResponse thenâ := amaxResponse := response[a]end ifend for32:33:return âend function30Аналогичным образом задается расширение просто конечным набором предикатовP ⊂ [−1, 1]O .Очевидно, что расширение модели не может повлиять на предельное качество, однако может повлиять на скорость сходимости поиска.Предикаты базовой модели напрямую соответствуют шаблонам наблюдений.
По аналогии можно рассматривать алгоритмы расширения базовой системы G0 как дополнительные алгоритмические сенсоры:ω 0 = (r, d, v, rf , I[A1 (ω) = FORWARD], . . . , I[AN (ω) = TURNRIGHT])(82)Так как любой предикат p определяется вектором чисел c, p = c ⊗ pm , все сформулированные для базовой модели алгоритмы переносятся без изменений на мета-модель.Пусть задано вероятностное пространство (Θ, 2Θ , P) и критерий качества I. Рассмотрим следующую величину:K(G, ζ) = min{|G| | G ` G, I(G, Θ) ≥ ζ}(83)Величина K в некотором смысле является аналогом Колмогоровской сложности — минимальный размер генома, который достигает определенного уровня качества.С помощью величины K можно сформулировать гипотезу более строго.Гипотеза 1. Пусть ζ̂ — уровень качества, достигаемый оптимальным алгоритмом,Gm мета-расширение G0 «наивным» алгоритмом.
Тогда:∃ζ0 < ζ̂ : ∀ζ ≥ ζ0 : K(Gm , ζ) K(G0 , ζ)(84)Важным следствием выполнения этой гипотезы является ослабление проблемы начального приближения, которое уже было упомянуто при обсуждении эволюционногоподхода — несмотря на увеличение размерности гена, значительное уменьшение размера генома ведет к ощутимому увеличению вероятности попасть в область с отображениями, удовлетворяющим оценке (40) при генерации начального приближения.Более того, можно легко явно получить начальное приближении, которое заведомоудовлетворяет оценке (40). Обозначит наивный алгоритм как B, тогда геном эквивалентный B записывается как:G0 = {(paB , a) | a ∈ A}(85)В численном эксперименте помимо «наивного» алгоритма модель расширялась следующими эвристиками:kr − rf kkr0 − rf k(rf − r) · dp2 ((r, d, v, rf )) =krf − rkp3 ((r, d, v, rf )) = H[v[rf ] 6= 0]p4 ((r, d, v, rf )) = H[v[r + d] 6= 1]p6 ((r, d, v, rf )) = H[(rf − r) · TURNLEFT(d) − (rf − r) · d > 0]p7 ((r, d, v, rf )) = H[(rf − r) · TURNRIGHT(d) − (rf − r) · d > 0]p1 ((r, d, v, rf )) = 1 − 231(86)(87)(88)(89)(90)(91)(92)где H[t] = 2I[t]−1.
Первый две эвристики соответствуют расстоянию и косинусу угла доцели. Эвристика (88) показывает наличие целевой точки в области зрения. Последниетри эвристики соответствуют предсказаниям на один шаг вперед: отсутствие «стены»впереди, уменьшение угла до цели при командах TURNLEFT, TURNRIGHT.Заметим, что с практической точки зрения обычная модель уже состоит из алгоритмических сенсоров, включая алгоритм построение карты окружения, которые формально заложены в определение наблюдения.
Уже здесь можно понять, как изменениерасширение базовой модели (то есть той, которая опирается на предикаты сенсоров)может повлиять на сложность 84 — в случае некумулятивного зрения теоремы 3 и 5должны быть переформулированы для множеств отображений R × D × O+ 7→ A иR × D × O+ 7→ A, мощность которых значительно выше.3.5Обучение без учителяВернемся обратно к алгоритмам LCS.
Напомним, что в алгоритме 6 обратная связьтребует знания потенциала критерия качества для текущей задачи, что в общем случаетребует знания параметров задачи.Так как зрение дает некоторую информацию о текущем окружении (остальные параметры задачи известны), можно перейти к оценке потенциала на основе зрения.Самой простой оценкой является потенциал задаваемый «наивным» алгоритмом,то есть минимальное количество команд до целевой точки, считая неизвестные точкиокружения свободными. Однако подменяя таким образом потенциал, мы принуждаемалгоритм следовать поведению «наивного» алгоритма. Так как на практике вычислительная стоимость ответа «наивного» алгоритма меньше, чем генома (причем значительно), и более того, ответ «наивного» алгоритма включен в мета-модель, такойбессмыслен.Вместо того, чтобы получать более совершенные оценки на потенциал (что в простомслучае требует знаний набора задач и распределения на нем), предлагается пожертвовать скоростью сходимости и воспользоваться более простым методом, требующимминимальных модификаций.
Заметим, что оценка потенциала для зрения на шаге t+Nзаведомо не хуже оценки на шаге t в силу свойства функции зрения (14), то есть перерасчет весов генов эффективнее, имея знания о основе будущих наблюдениях. Эту идеюпросто осуществить отложив этап Feedback для шага t на N шагов. Так как перерасчет весов происходит для действий в прошлом, такой подход в дальнейшем называетсяретроспективным (retrospective).Такой подход имеет два недостатка. Во-первых, даже для больших N оценка потенциал не обязана соответствовать истинному потенциалу. Полностью устранить этупроблему невозможно.
Во-первых, этот подход может замедлить сходимость поиска,особенно для N сравнимых с размерами находимых путей. Однако, численные эксперименты показывают, что алгоритмы на начальных шагах имеют качество намного хуже,чем «наивный» алгоритм, поэтому различие между его потенциалом и истинным слабовлияют на скорость сходимости. К моменту же приближения качества алгоритма к «наивному», скорость сходимости существенно падает, что позволяет улучшению качестваот улучшения оценки потенциала компенсировать замедление, вызванное большими N .Поэтому в данной работе предлагается постепенно увеличивать N , начиная с N = 0 дляслучайно сгенерированных геномов.
Когда N становиться больше длины найденныхмаршрутов, алгоритм начинает напоминать эволюционный подход, в котором, оценкагенома производиться после завершения задач, однако, в отличии от последнего при32достаточно плавном увеличении N , геном к этому времени будет находиться в области,в которой алгоритмы завершают задачи.Ris. 1: Схема обобщенного генетического алгоритма с алгоритмическими сенсорами.4Численный экспериментЧисленный эксперимент проводился для всех описанных генетических алгоритмов, аименно:• классический генетический алгоритм 4.• однослойная LCS cо схемой наилучшего соответствия 6• однослойная LCS со схемой голосования 9• классическая LCSДля каждого алгоритма использовалась базовая и мета-модель.Алгоритмы были реализованы на языке Scala и находятся в открытом доступе5 .Использовались два набора задач c H, W ∼ 100.
При таких значениях провестирасчет оптимального алгоритма (например, по алгоритму policy iteration) практическиневозможно.Для первого набора задач использовался случайный генератор, который в окружении l = 1H×W (то есть все точки заняты), начиная с точки r0 = (0, W/2) и произвольного направления d, продвигался по этому направлении на N [5, 10] шагов, случайноменяя направление после, до тех пор, пока не достигнет точки rf = (H, W/2). Каждаяпосещенная точка отмечалась как свободная. Распределение на задачах определяется вероятностью получить соответствующее окружение, то есть задается генератором.Этот набор задач представляет интерес только как пример набора без структуры (определение 13), так как судя по оценке качества, «наивный» алгоритм вероятно являетсяоптимальным, либо, как минимум, близок к нему.5Git-репозиторий можно найти по адресу https://github.com/genetic-machine/genetic-machine33Ris.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
