Применение генетических алгоритмов для эффективного решения задачи навигации (1187414), страница 5
Текст из файла (страница 5)
Пусть задано ω = (r, d, v, rf ), и вектор cωсостоит из нулей, кроме позиций соответствующих предикатам pr , pd , pv , prf . Так какзначения каждого типа предикатов зависят только от соответствующей компоненты:Arg max (cω ⊗ p0 )(ω 0 ) =ω 0 ∈OArg max (1, 1, 1, 1) ⊗ (pr , pd , pv , prf ) (ω 0 ) =ω 0 ∈O0{ω | ωr0= r} ∩ {ω 0 | ωd0 = d} ∩ {ω 0 | ωv0 = v} ∩ {ω 0 | ωr0 f = rf } = {ω}Пусть задано отображение A : O 7→ A. Построим эквивалентный геном GA :GA = {(pω , A(ω)) | pω = cω ⊗ p0 , ω ∈ O}В силу предыдущих рассуждений:Arg max p(ω) = {(pω , A(ω))}(p,a)∈GAа в силу определения схемы принятия решений Λ (52):"#∀ω ∈ O : arg max p(ω) = (pω , A(ω)) =⇒ Λ(GA ) ≡ A(p,a)∈GAчто завершает доказательство.G0 со схемой голосования (53) покрывает только часть отображений.3.2Эволюционный подходОпределив модель, перейдем к рассмотрению алгоритмов оптимизации. Все рассматриваемые в работе генетические алгоритмы поиска можно по аналогии с эволюционнойтеорией разделить на два класса: эволюционные и адаптационные.
Простейшим примером эволюционного алгоритма является алгоритм 4, на который часто ссылаются какна классический генетический алгоритм. Каждая итерация алгоритма состоит из трехшагов:1. формирование популяции, процедура Evolve2. оценка качества каждого генома, процедура Evaluate3. отбор геномов, процедура Select22Algorithm 4 Классический генетический алгоритмRequire: Generation(), Mutation(·), Crossover(·, ·) — функции генерации, мутации искрещивания, Evaluate(·) — процедура оценки качества, populationSize — размерпопуляции, α > 0 — доля отбора, β — доля скрещивания, α + β < 11: function Select(population, quality)2:N := α|population|3:return arg topN quality4: end function5:6:7:8:9:10:function Evolve(population)Ncrossover = β|populationSize|mutated := ∅for G ∈ population domutated := mutated ∪ {Mutation(G)}end for11:12:13:14:15:16:crossovered := ∅while |crossovered| < Ncrossover ∧ |population| ≥ 2 doG := randomSample(population)G0 := randomSample(population \ {G})crossovered := crossovered ∪ {Crossover(G, G0 )}end while17:18:19:20:generated = ∅while |generated| < populationSize − |mutated| − |crossovered| dogenerated := generated ∪ {Generation()}end while21:22:return mutated ∪ crossovered ∪ generatedend function23:24:function ClassicGeneticSearch(population, n)population0 = Evolve(population)25:26:27:28:29:30:31:32:33:34:35:quality := []for G ∈ population0 doquality[G] = Evaluate(G)end forif n > 0 thenpopulation00 = Select(population0 , quality)return ClassicGeneticSearch(population00 , n − 1)elsereturn arg maxG∈population quality[G]end ifend function23Процедура Evolve определяется как минимум двумя (иначе генетический поиск вырождается в случайный), а чаще всего тремя функциями генерации, каждая из которыхзадает процедуру мутацию определенной арности, начиная с нулевой: порождение нового генома — Generation(), мутация — Mutation(·), скрещивание — Crossover(·, ·) и такдалее.
Для нашей модели соответствующие процедуры можно задать как показано влистинге 5.Процедура Evaluate соответствует выражению:Evaluate(G) = Êθ Q(θ, G)(68)где Q(θ, G) — выбранный критерий качества, Êθ — математическое ожидание качествалибо его оценка.Эксперимент с применением алгоритма 4 не дал никаких положительных результатов. Причиной этому является проблема начального приближения — попадание случайным начальным приближением в окрестность, в которой алгоритмы завершают всезадачи из набора, маловероятно, поэтому на стадии Evaluate все алгоритмы популяцииотсекались оценкой (40), превращая генетический поиск либо в случайное блуждание,либо в случайный поиск, в зависимости от способа обработки данного случая.3.3Адаптационный подходКорень проблемы предыдущего подхода заключается в том, что алгоритм абстрагируется от поведения генома на шаге Evaluate, тем самым не учитывая некоторые особенности.
Идея адаптационного похода состоит в приспособлении (адаптации) моделик наблюдениям, встречающимся при оценке качества, что легко укладывается в нашслучай, так как модель G0 строится на основе наблюдений, что позволяет оценивать еекачество более детально.Алгоритм навигации выдает последовательность команд, что позволяет пойти дальше, применяя процедуру адаптации на каждом шаге алгоритма, применяя техники изобласти обучения с подкреплением (reinforcement learning)[22], [23].Мы рассмотрим два алгоритма: алгоритм обучающейся классифицирующей системы (learning classifier system, LCS)[24] и его частный случай, на который мы будем ссылать как на однослойную LCS[2].
Так как процедура адаптации применяется на каждомшаге, требуется обратная связь (feedback) в виде оценки качества одной команды.В зависимости от типа обратной связи, алгоритм будет принадлежать к двум разнымклассам: обучение с учителем (supervised learning) и без учителя (unsupervised learning).Рассмотрение начинается с первого класса.Однослойная LCSАлгоритм 6 представляет упрощенную версию LCS, использующую модель G0 практически на прямую. Единственное отличие заключается в сопоставлению каждому генуg = (p(·), a) числового значения ρ[g] > 0 — веса, с помощью которого происходит обучение модели и определение общего ответа генома:ĝ = arg max p(ω)w(ρ[g])(69)g∈G(·, â) = ĝ(70)24Algorithm 5 Пример реализация функций генетического поиска для задачи навигацииRequire: genomeSize — размер одного генома (количество предикатов); α ∈ [0, 1] —интенсивность мутаций; DrawNormal(µ, Σ) — процедура генерации векторов, распределенных нормально: N (µ, Σ), где µ — вектор средних, Σ — матрица ковариаций; DrawUniform(X) — процедура выбора элемента из конечного множества X всоответствии с равномерным распределением на этом множестве; DrawPoisson(λ) —процедура генерации значений, распределенных по Пуассону с интенсивностью λ;pv — вектор базовых предикатов зрения.1: function GenerateGene( )2:predicate := DrawNormal(0HW , EHW ×HW ) ⊗ pv3:action := DrawUniform(A)4:return (predicate, action)5: end function6:7:8:9:10:function Generation( )G := ∅while |G| < genomeSize doG := G ∪ {GenerateGene()}end while11:12:return Gend function13:14:15:16:17:18:19:20:function Mutation(G)λ := α · |G|N := DrawPoisson(λ)G0 := Gfor i = 1, .
. . , N don := DrawUniform({1, . . . , |G|})G0 [n] := GenerateGene()end for21:22:return G0end function23:24:25:26:27:28:function Crossover(G1 , G2 )G0 := ∅for i = 1, . . . , genomeSize don = DrawUniform({1, 2})G0 := G0 ∪ {Gn [i]}end for29:30:return G0end function25где функция w — монотонно возрастающая весовая функция. В данной работе, в силунормировки p(·) ∈ [−1, 1] используется логистическая функция:w(ρ) =2−11 + exp(−ρ)(71)Для однораноговой LCS наличие весов позволяет применять схему голосования:Pg∈G I[g = (p, a)] [p(ω)]+ w(ρ[g])(72)â = arg max Pa∈Ag∈G I[g = (p, a)]I[p(ω) > 0]при которой процедуры Feedback и Response алгоритма 6 заменяются на соответствующие процедуры алгоритма 9.
Стоит обратить внимание, что суммирование ведется погенам для которых p(ω) > 0, то есть учитываются только те гены, которые считают ω«похожей» на свой шаблон.Процедура обучения похожа по своей структуре на общую схему работы алгоритманавигации и фактически является надстройкой над ней. Главное отличие состоит вдобавлении нового этапа обратной связи, Feedback идущего после вычисление ответасистемы.
На этом этапе алгоритму передается некая оценка качества действия f ∈ R, спомощью которой происходит пересчет весов после каждого действия. В формулировкеPOMDP обратная связь соответствует функции награды G, а значит в задаче навигацииэквивалентна уменьшению потенциала критерия качества.
Более подробно об обратнойсвязи в LCS описано в [24]. Заметим, что в функции EvaluateAction для 6 потенциалсчитается известным, что соответствует обучению с учителем.Детали реализации представлены в алгоритмах 6, 7, 8, 9.Заметим, что несмотря на то, что схема голосования покрывает только подмножество отображений O 7→ A, что может уменьшить качество на определенных наборахзадач, она обладает важным с практической точки зрения преимуществом: так как вформировании решения принимают участия множество генов, пересчет весов на каждом шаге происходит более, чем для одного гена, что дает большую скорость сходимостипо сравнению с схемой наибольшего отклика (52).Классическая LCSПредикаты G модели для классической обучающейся классифицирующей системы илипросто LCS отличается от стандартной модели G0 :G = Gi ∪ Gm ∪ Go ∪ GioGi ⊂ {(p, m) | p = c ⊗ p0 , m[0, 1]+ }Gm ⊂ {(m1 , m2 ) | m1 , m2 ∈ [0, 1]+ }Go ⊂ {(m, a) | m ∈ [0, 1]+ , a ∈ A}Gio ⊂ {(p, a) | p = c ⊗ p0 , a ∈ A}(|Gi | > 0 ∧ |Go | > 0) ∨ (|Gio | > 0)(73)(74)(75)(76)(77)(78)Все гены G делятся на четыре класса: входные (сенсорный слой), промежуточные,выходные (актуаторный слой), входные-выходные.
Последние соответствуют моделиG0 . Основная концепция остается прежней — каждый ген представляет в виде парыусловие-действие. Главное отличие состоит в добавлении внутренних действий и условий, которые следуя работе [24] представляются в виде не пустой последовательности26Algorithm 6 Однослойная LCSRequire: α — скорость обучения; w(·) — весовая функция; θ = (l, r0 , d0 , rf ) — текущаязадача; Uθ (·, ·) — потенциал функции качества для текущей задачи.1: function EvaluateAction(ω, a)2:(r, d, ·, ·) := ω3:(r0 , d0 ) := ϕ(l, r, d, a)4:∆U := Uθ (r, d) − Uθ (r0 , d0 )5: end function6:7:8:9:10:11:12:13:14:15:16:function Response(G, ρ, ω)maxResponse := −∞ĝ = NULLfor g ∈ G do(p, a) := gr := p(ω)w(ρ[g])if maxResponse < r thenmaxResponse := rĝ := gend ifend for17:18:return ĝend function19:20:21:22:23:24:25:function Feedback((G, ρ, ĝ, ωp ), f )(p̂, ·) = ĝρ0 = []for g ∈ G do(p, a) := gρ0 [g] := ρ[g] + I[ĝ = g] · αw(ρ[g])p(ωp )fend for26:27:28:29:(G0 , ρ00 ) := Select(G, ρ0 )(G00 , ρ000 ) := Evolve(G0 , ωp , ρ00 , f )return (G00 , ρ000 )end function30:31:32:function Act((G, ρ = 0|G| , ĝ = NULL, ωp = NULL), ω)ĝ := Response(G, ρ)(·, â) := ĝ33:34:35:36:37:f := EvaluateAction(â)(G0 , ρ0 ) := Feedback((G, ρ, ĝ, ωp ), f )s0 := (G0 , ρ0 , ĝ, ω)return (s0 , â)end function27Algorithm 7 Функция Select для алгоритма LCSRequire: ρ0 — вес отсечения1: function Select(G, ρ)2:G0 := ∅3:ρ0 := []4:for g ∈ G do5:if ρ[g] > ρ0 then6:G0 := G0 ∪ {g}7:ρ0 [g] := ρ[g]8:end if9:end for10:11:return (G0 , ρ0 )end functionчисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
