Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

РЕАЛИЗАЦИЯ ИНТЕГРИРОВАННОГО АЛГОРИТМА МНОГОАЛЬТЕРНАТИВНОГО ВЫБОРА И ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Андраханов С.В. 1 Львович Я.Е. 1 Преображенский А.П. 2
1 ГОУ ВПО «Воронежский государственный технический университет»
2 АНОО ВПО «Воронежский институт высоких технологий»
При формировании структуры робота может применяться комбинированный поисковый алгоритм, который состоит в использовании процедуры многоальтернативной оптимизации. При выборе конечного варианта подключается алгоритм поиска, характеризующийся более высокой эффективностью для рассматриваемого класса объектов проектирования. В работе проведена интеграция алгоритма многоальтернативного выбора и генетического алгоритма. Для операции размножения используется рекомбинация генов двух родительских хромосом, выбранных на основе скрещивания. При этом получен новый вариант набора альтернативных переменных, определяющих конструкцию и алгоритм управления движением. Родительские хромосомы сравниваются по содержанию каждого гена. С целью проведения сокращений множества перспективных вариантов создается репродукционная группа с использованием селекционных схем. Разработанный алгоритм позволяет исследовать особенности движения ММР. Приведена структурная схема диалогового алгоритма многокритериальной оптимизации на множестве альтернативных переменных.
оптимизация
робот
генетический алгоритм
моделирование.
1. Андраханов С.В., Львович Я.Е., Преображенский А.П. Интеграция алгоритма многоальтернативной оптимизации и генетического алгоритма в учебно-исследовательской САПР // Вестник Воронежского института высоких технологий. – 2013. – № 10. – С. 4–8.
2. Андраханов С.В., Львович Я.Е., Преображенский А.П. Учебно-исследовательская САПР мехатронно-модульных роботов // Вестник Воронежского государственного технического университета. – 2013. – Т. 9. – № 3–1. – С. 24–27.
3. Кочеткова О.В., Казначеева А.А. Разработка метода и средств представления модели знаний специалиста в учебно-исследовательских САПР (монография) // Международный журнал прикладных и фундаментальных исследований. – 2012. – № 9. – С. 79–80.
4. Львович Я.Е. Многоальтернативная оптимизация: теория и приложения. – Воронеж: Кварта, 2006. – 428 с.
5. Львович Я.Е., Андраханов С.В. Интеграция процедур многоальтернативной оптимизации и метода роя частиц // Вестник Воронежского государственного технического университета. – 2010. – Т. 6. – № 12. – С. 29–31.
6. Макаров И.М., Лохин В.М., Манько С.В., Романов М.П., Кадочников М.В. Технологии обработки в задачах управления автономными мехатронно-модульными реконфигурируемыми роботами // Приложение к журналу «Информационные технологии». – 2010. – № 8.
7. Смольников Б.А. Проблемы механики и оптимизации роботов. – М.: Наука, 1991.

Управление сложными техническими системами определяет необходимость разработки соответствующих алгоритмов. В качестве примера таких систем, активно используемых на практике, могут быть приведены мехатронно-модульные роботы (ММР). В настоящее время многие предприятия, которые создают роботов, применяют системы автоматизированного проектирования (САПР) для того, чтобы формировать роботов на основе виртуальной среды. В основе указанных САПР находятся специальные приложения, предназначенные для того, чтобы моделировать геометрические, кинематические и эргономические характеристики робота [2]. При этом могут формироваться различные варианты робототехнического устройства проектировщиком на основе применения средств геометрического моделирования.

Методика решения задачи

При формировании структуры робота может применяться комбинированный поисковый алгоритм, который состоит в использовании процедуры многоальтернативной оптимизации для получения некоторого набора хороших вариантов, которые достаточно полно отвечают требованиям оптимизируемой функции F [1, 7]. При выборе конечного варианта подключается алгоритм поиска, характеризующийся более высокой эффективностью для рассматриваемого класса объектов проектирования. В [3, 5] на основе модельных экспериментов показана возможность применения генетических алгоритмов для структурного синтеза ММР.

Используется определенная структура хромосомы, кодирующей порядок сборки и алгоритм управления ММР.

В случае алгоритма многоальтернативного выбора будем рассматривать значения альтернативных переменных xj, Eqn1.wmf, принимающих значения 1 или 0 как коды соответствующих генов хромосомы.

В отличие от формата хромосомы, предложенном в [6], формат хромосомы, являющийся аналогом перспективного варианта решения задачи многоальтернативной оптимизации, в соответствии с оптимизируемой функцией F включает ряд блоков хромосом в следующей последовательности:

1) подхромосома, состоящая из четырех генов и определяющая количество N модулей ММР;

2) N – 1-подхромосома, состоящая из пяти генов и определяющая размещение модуля (2 гена – сторона крепления, 3 гена – номер площадки, выбранной для стыковки);

3) N-подхромосомы, состоящие из четырех генов и определяющие параметры управления первой степенью подвижности модуля (по обобщенной координате y);

4) N-подхромосомы, состоящие из четырех генов и определяющие параметры управления второй степени подвижности модуля (по обобщенной координате z).

На первом этапе осуществляется переформатирование блоков 2–4 в формат, когда последовательно для каждого модуля располагаются гены xj, Eqn1.wmf, характеризующие размещение модуля и алгоритм управления. Обозначим хромосомы в этом формате xℓ = (xjℓ), Eqn1.wmf, Eqn2.wmf, где ℓ – число перспективных доминирующих вариантов (L обычно ≤ 7 [3]).

На втором этапе используются основные операции генетических алгоритмов, апробированные для ММР [6]: скрещивания и размножения. Учебно-исследовательская составляющая предусматривает выбор из нескольких схем скрещивания.

Для выполнения скрещивания все хромосомы xℓ, Eqn2.wmf, принадлежащие популяции X, делят на локальные популяции Xm ≠ 0, Eqn4.wmf (M ≤ J), в любой из которых равны нулю Хемминговы расстояния между любой парой генов xjℓ, xjt, Eqn3.wmf. Локальные популяции для скрещивания выбираются случайным образом. Для этого определяется численность локальных популяций Lm и для случайного выбора используется распределение вероятностей

pm = Lm/L, Eqn4.wmf. (1)

Определяются реализации случайного дискретного числа Eqn5.wmf. В качестве родительской пары (xℓ, xt) ∈ X выбираются хромосомы xℓ ∈ Xm1 и xt ∈ Xm2.

Вторая схема скрещивания определяется расстоянием Хемминга между значениями xjℓ, xjt, Eqn1.wmf двух хромосом xℓ, xt, Eqn3.wmf, Eqn6.wmf.

В случаях h ≤ h0, где h0 – заданное положительное число, исследуется схема имбридинга. Если h ≥ h0, исследуется третья схема – аутбридинга.

Кроме приведенных схем исследуются схемы ассортативного скрещивания. В этом случае используется количественная оценка степени приспособления, которая определяется по значению оптимизируемой функции для каждой хромосомы xℓ – F(xjℓ). В первой схеме хромосомы для скрещивания выбираются из распределения вероятностей

Eqn7.wmf (2)

Во второй схеме при проведении отрицательного ассортативного скрещивания делают случайный выбор одной из хромосом из (2), а вторая берется из вероятностей

Eqn8.wmf (3)

Третья схема основана на селективном скрещивании. С этой целью из набора хромосом xℓ, Eqn2.wmf исключаются те, которые обладают степенью приспособленности меньшей, чем средняя степень приспособленности на множестве хромосом xℓ, Eqn2.wmf:

Eqn9.wmf

Далее осуществляется случайный выбор по распределению (2).

Особенности реализации генетического алгоритм

Для операции размножения используется рекомбинация генов двух родительских хромосом, выбранных на основе скрещивания. При этом получаем новый вариант набора альтернативных переменных, определяющих конструкцию и алгоритм управления движением. Родительские хромосомы сравниваются по содержанию каждого гена. В учебно-исследовательской составляющей УИ САПР целесообразно рассмотреть возможные реализации операции размножения. Далее переходят к одной из схем скрещивания для подбора вариантов xℓ, xt, Eqn3.wmf, в родительскую пару. При этом происходит завершение процесса после осуществления перебора всех возможных родительских пар. С целью проведения сокращений множества перспективных вариантов создается репродукционная группа с использованием селекционных схем. Здесь исследуются две основные схемы. В первой схеме происходит упорядочение всех Eqn2.wmf в том порядке, в котором идет убывание для значений, характеризующих их степени приспособленности. Задают размер для репродукционной группы Lp, с ограничением перспективных вариантов. Для второго случая определяют среднюю степень приспособленности Eqn2.wmf вариантов

Eqn10.wmf

В репродукционную группу происходит включение только тех вариантов xlp, у которых степень приспособленности выше или равна средней величине

F(xℓ) ≥ Fср, Eqn2.wmf.

Поскольку алгоритм многоальтернативной оптимизации [1, 7] основан на организации поиска для рандомизированной среды, следует размещать в этой среде и процедуру, которая дает выбор свертки. При этом в рандомизированной среде используют случайную величину Eqn11.wmf, которая принимает значение номеров, относящихся к функциям Eqn12.wmf c вероятностью Pd, Eqn13.wmf. На k-м шаге одновременно c проведением настройки вероятностей, характеризующих альтернативные переменные, вероятностей, характеризующих значимости критериев ψi(x) при формировании оптимизируемых функций, идет настройка вероятностей Pd на основе такой последовательности шагов.

1. Исходя из распределения Eqn14.wmf происходит генерация значений дискретного случайного числа Eqn15.wmf.

2. В том случае, когда dk = 1, то исходя из распределения Eqn16.wmf происходит генерация дискретного случайного числа Eqn17.wmf.

3. Происходит определение четырех значений Eqn18.wmf для различных комбинаций по альтернативным переменным хj, Eqn1.wmf, которые соответствуют первой Δ1jψik и второй Δ2jψik вариациям в алгоритме многоальтернативной оптимизации.

4. В том случае, когда Eqn19.wmf, то, исходя из вариаций Δ1jFdkΔ2jFdk алгоритма многоальтернативной оптимизации, происходит вычисление четырех значений оптимизируемой функции

Eqn20.wmf

5. Происходит вычисление для таких же комбинаций по альтернативным переменным на основе четырех значений для других критериев ψi, i ≠ ik.

6. Среди всех критериев ψi и функций Fdk, Eqn19.wmf из четырех значений происходит выбор рекорда (максимального значения Eqn21.wmf, Eqn22.wmf, Eqn19.wmf).

7. Полученные рекордные значения предъявляют для эксперта с целью оценивания с вопросом: «Какое из предъявленных значений по критериям Eqn21.wmf и Eqn22.wmf не приводит к удовлетворению условий в максимальной степени?».

8. В том случае, если подходит один из данных критериев ψi то происходит настройка по вероятностям Eqn23.wmf и Eqn24.wmf, когда не устраивает Eqn25.wmf, то проводится настройка только для Eqn24.wmf.

9. Происходит формализация ответа эксперта таким образом

Eqn26.wmf

Eqn27.wmf

Eqn28.wmf

pic_1.tif

Структурная схема диалогового алгоритма многокритериальной оптимизации на множестве альтернативных переменных

10. Происходит определение нового распределения для случайных дискретных величин Eqn29.wmf, Eqn11.wmf исходя из информации, которая получена из диалога с экспертом и для которой есть формализация по правилам п. 9, и с ориентацией на условия п. 8,

Eqn30.wmf

Eqn31.wmf

где εk+1 > 0 – размер шага при получении значений вероятностей Pi на k + 1-й итерации; γk+1 > 0 – размер шага при получении значений вероятностей Pd на k + 1-й итерации,

Eqn32.wmf

11. Отмечаются установившиеся значения Eqn33.wmf исходя из того, как зависит Pi от номера итерации Eqn34.wmf Eqn35.wmf Eqn36.wmf

12. С итерации k = K происходит переход от проведения поиска по выбранным критериям ψi, Eqn35.wmf к проведению поиска на основе аддитивной свертки, ориентируясь на следующее условие:

Eqn37.wmf

считая, что

Eqn38.wmf Eqn35.wmf,

где Mi – математическое ожидание реализаций значения ψi(x) по случайному дискретному числу Eqn29.wmf.

13. Происходит сравнение значений, определенных в п. 10 для k-й итерации. По следующему шагу в алгоритме многоальтернативной оптимизации происходит выбор оптимизируемой функции Fd с наибольшим значением pd.

Структурная схема диалогового алгоритма многокритериальной оптимизации приведена на рисунке.

Выводы

Таким образом, в работе проведена интеграция алгоритма многоальтернативного выбора и генетического алгоритма. Разработанный алгоритм позволяет исследовать особенности движения ММР. Приведена структурная схема диалогового алгоритма многокритериальной оптимизации на множестве альтернативных переменных.

Рецензенты:

Разинкин К.А., д.т.н., профессор Воронежского государственного технического университета, г. Воронеж.

Чопоров О.Н., д.т.н., профессор, проректор по научной работе Воронежского института высоких технологий, г. Воронеж.

Работа поступила в редакцию 06.11.2013.


Библиографическая ссылка

Андраханов С.В., Львович Я.Е., Преображенский А.П. РЕАЛИЗАЦИЯ ИНТЕГРИРОВАННОГО АЛГОРИТМА МНОГОАЛЬТЕРНАТИВНОГО ВЫБОРА И ГЕНЕТИЧЕСКОГО АЛГОРИТМА // Фундаментальные исследования. – 2013. – № 10-11. – С. 2391-2395;
URL: http://www.fundamental-research.ru/ru/article/view?id=32801 (дата обращения: 13.11.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074