Применение генетических алгоритмов для эффективного решения задачи навигации (1187414), страница 7
Текст из файла (страница 7)
3: Алгоритм однослойной LCS со схемой голосования. Сравнение сходимости дляразличных типов обратной связи: supervised — истинный потенциал (обучение с учителем), classical — потенциал «наивного» алгоритма, retrospective — ретроспективныйс повышением шага задержки на 2 каждое поколение (generation), начиная с нулевой задержки. Приведены типичные кривые качества. Вертикальная ось соответствует−I(Θ, A). Эксперимент на одной задаче, generation соответствует одному проходу окружения.Второй набор состоял из 20 предварительно сгенерированных и отобранных окружений, напоминающий план одного этажа здания — по сторонам главного широкогокоридора расположены «комнаты», начальные и конечные точки находятся на разныхконцах коридора, причем любой путь заходя в комнату, выходит через ту же точку(или окрестность в несколько точек). Вероятностное распределение на задачах равномерное.
Интуитивно понятно, что такой набор обладает структурой — простое правило,сдерживающее прокладку маршрута по комнатам, может дать значительный прироств качестве.В качестве функции зрения использовалась (10) c радиусом в 5 клеток.Так как разброс длин оптимальных маршрутов относительно велик π̂ ∈ [150, 200],для результатов представленных в данной роботе использовался нормированный критерий качества (28). Качественных выводов, отличных от представленных, анализ значений других критериев не дает. Качество «наивного» алгоритма I(Θ, An ) ≈ −1.8, дляконкретных задач находится в пределах Q(θ, An ) ∈ [−2.0, −1.7].Положительным результатом считалось, во-первых, нахождение отображения, способного завершить все задачи из набора, во-вторых, предельное качество превосходящее«наивный» алгоритм.34Ris.
5: Алгоритм однослойной LCS со схемой голосования. Сравнение сходимости дляразличных типов обратной связи: supervised — истинный потенциал (обучение с учителем), classical — потенциал «наивного» алгоритма, retrospective — ретроспективныйс повышением шага задержки на 2 каждое поколение (generation), начиная с нулевойзадержки. Вертикальная ось соответствует −I(Θ, A). Эксперимент на втором наборезадач, generation соответствует завершению всех 20 задач, приведены усредненные значения и стандартное отклонение.Классический генетический алгоритм, как уже было упомянуто, столкнулся с проблемой начального приближения — даже для мета-модели, в которой начальное приближение указано явно, поиск не смог найти отображение завершающее хотя бы однузадачу, все попытки были отброшены оценкой (40).Другие алгоритмы находили отображения, которые были способны завершить хотя бы одну задачу.
Однако низкая скорость сходимости однослойной LCS со схемойнаилучшего соответствия за время (как реальное, так и по количеству задач) превышающее время, понадобившееся LCS с мета-моделью со схемой голосования для опережения «наивного» алгоритма по качеству, не позволила найти отображение (даже вмета-модели), которое способно завершить все задачи набора, поэтому была вычеркнута из рассмотрения.
Аналогичное поведение демонстрирует классический алгоритмLCS, который к удивлению по субъективной оценке автора (объективная оценка практически невозможна) показал скорость ниже, чем однослойная LCS.Алгоритмы использующие обычную модель, начиная с некоторого момента, не показывали признаков заметного улучшения даже на задачах, для которых находилиотображение завершающее задачу.Только один из алгоритмов показал положительные результаты — однослойная LCSс мета-моделью со схемой голосования. Для этого алгоритма был проведен эксперимент35Ris.
6: Пример окружения из второго набора. Для демонстрации наличия структуры,показан путь совершаемый «наивным алгоритмом».по сравнению различных типов обратной связи. Результаты показаны на графиках 2 и 4(на графике для удобства показана функция −I(Θ, A)). Как можно заметить, обучениес учителем приблизилось по качеству к абсолютному максимуму, при этом алгоритмс обратной связью на основе потенциала «наивного» алгоритма, как и предсказывалось, не превзошло качество характерное для «наивного алгоритма». Самым главнымрезультатом является то, что ретроспективная обратная связь, начиная с уровня потенциала «наивного» наивного алгоритма, постепенно достигла уровня обучения с учителем.
Это демонстрирует возможность успешного самообучения для задачи навигации,без необходимости в предварительной оценке/разведке окружений. Ценой этому былинезначительные потери в скорости сходимости.5ЗаключениеВ результате данного исследования, проведя анализ задачи была выбрана модель алгоритма навигации и доказаны ее свойства, позволяющие проводить поиск приближение коптимальному алгоритму в этой модели. Была также сформулировано ее расширение —мета-модель, дополняющая наблюдения результатами эвристик/алгоритмических сенсоров.
Было проведено исследование четырех различных генетических алгоритмов, сре-36(a) 1-ый проход(b) 10-ый проход(c) Кратчайший маршрутRis. 7: Демонстрация скорости сходимости. Набор состоял из единственной задачи.ди которых был выбран один, дающие положительные результаты в численном эксперименте. В результате, получен адаптационный алгоритм навигации способный к самообучению по описанной технике, с одной стороны доступный для применения на практикес вычислительной точки зрения, с другой стороны показывающий результаты близкиек оптимальным.6Дальнейшая работаМета-модельЕдинственный алгоритм, продемонстрировавший положительный результаты, был построен на основе мета-модели, которая расширяет наблюдения результатами эвристик.По гипотезе автора, для широкого с точки зрения практики класса наборов задач существует набор эвристик, позволяющих полностью заменить базовую модель, фактическипревращая метод в boosting алгоритм в классическом определении. Если мощность этонабора значительно меньше длины гена в стандартной модели, то возможно значительное ускорение сходимости описанных алгоритмов.
Более того, существенное понижениеразмерности делает возможным применение классических алгоритмов оптимизации иboosting методов машинного обучения, что может повысить как вычислительную эффективность, так и качество итоговых отображений.Определить эффективно полные системы эвристик можно анализируя близкие к оптимальным отображения полученные в результате обучения модели, которая включаетв себя обычную (в том числе, описанную мета-модель).Проблема начального приближенияАлгоритм однослойной LCS может переобучаться (излишне адаптироваться к текущейзадаче), что негативно сказывается на качестве. Классический генетический алгоритм374 при адекватной оценке качества лишен такого недостатка, но страдает от проблемы начального приближения. При этом по результатам эксперимента LCS достигаеткачества близкого к максимальному, а значит велика вероятность, что для других похожих наборов задач как минимум находит хорошее начальное приближение.
Более того, регулировкой параметра скорости обучения, можно добиться быстрого достиженияположительных результатов ценой их большего разброса. Возможно, последовательноприменение этих алгоритмов может дать результаты лучше, чем показала однослойнаяLCS.Другой возможный подход состоит в использовании алгоритмов приближенных решений POMDP для той же цели.Проблема похожих геновСхема принятие решения голосованием имеет один недостаток по сравнению со схемойлучшего соответствия, а именно слабый механизм борьбы с похожими генами, которыевсегда присутствуют как результат процедур мутации и скрещивания.
С одной стороны, схема голосования, в отличии от схемы наилучшего соответствия, за счет пересчетавесов всех генов, которые принимали участие в голосовании, позволяет быстро наращивать веса эффективных генов вне зависимости от наличия похожих. С другой стороны,то же свойство удерживает менее эффективные похожие гены от потери веса. Выявляя такие группы генов и оставляя только наиболее эффективные, можно повыситьскорость сходимости и предел качества.Анализ близости генов по их численным представлениям крайне затруднителен, таккак близость коэффициентов в общем случае не означает близость поведения и наоборот. Было начато исследование методов выявления таких групп.
Предлагаемый методосновывается на метрике близости поведения, которая выражается через относительную энтропию Кульбака-Лейблера. Изначально разрабатываемый для данной работы,упрощенный метод продемонстрировал высокие результаты в похожей задаче для рекомендательных систем[25], однако для применения в алгоритме однослойной LCS требуетдоработки.38Spisok literatury[1] Борисяк М.А.
Устюжанин А.Е. Применение генетических алгоритмов для эффективного решения задачи навигации. Труды 57-ой научной конференции МФТИ, 2,2014.[2] Amanda Whitbrook, Uwe Aickelin, and Jonathan Garibaldi. Genetic-algorithm seedingof idiotypic networks for mobile-robot navigation. arXiv preprint arXiv:0803.1626, 2008.[3] Ashwin Ram, Gary Boone, Ronald Arkin, and Michael Pearce. Using genetic algorithmsto learn reactive control parameters for autonomous robotic navigation.
Adaptivebehavior, 2(3):277–305, 1994.[4] Dilip Kumar Pratihar, Kalyanmoy Deb, and Amitabha Ghosh. A genetic-fuzzyapproach for mobile robot navigation among moving obstacles. International Journalof Approximate Reasoning, 20(2):145–172, 1999.[5] Richard Szabo. Topological navigation of simulated robots using occupancy grid.
arXivpreprint cs/0411022, 2004.[6] Alberto Elfes. Using occupancy grids for mobile robot perception and navigation.Computer, 22(6):46–57, 1989.[7] Alberto Elfes. Occupancy grids: A stochastic spatial representation for active robotperception. arXiv preprint arXiv:1304.1098, 2013.[8] Muhammad Zohaib, Syed Mustafa Pasha, Nadeem Javaid, and Jamshed Iqbal.Intelligent bug algorithm (iba): A novel strategy to navigate mobile robotsautonomously. arXiv preprint arXiv:1312.4552, 2013.[9] David Kortenkamp and Terry Weymouth. Topological mapping for mobile robots usinga combination of sonar and vision sensing.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
