Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

IMPLEMENTATION OF INTEGRATION ALGORITHM MULTIALTERNATIVE SELECTION AND GENETIC ALGORITHMS

Andrahanov S.V. 1 Lvovich Y.E. 1 Preobrazhensky A.P. 2
1 GOU VPO «Voronezh State Technical University»
2 ANOO VPO «Vorovezh Institute of High Technologies»
При формировании структуры робота может применяться комбинированный поисковый алгоритм, который состоит в использовании процедуры многоальтернативной оптимизации. При выборе конечного варианта подключается алгоритм поиска, характеризующийся более высокой эффективностью для рассматриваемого класса объектов проектирования. В работе проведена интеграция алгоритма многоальтернативного выбора и генетического алгоритма. Для операции размножения используется рекомбинация генов двух родительских хромосом, выбранных на основе скрещивания. При этом получен новый вариант набора альтернативных переменных, определяющих конструкцию и алгоритм управления движением. Родительские хромосомы сравниваются по содержанию каждого гена. С целью проведения сокращений множества перспективных вариантов создается репродукционная группа с использованием селекционных схем. Разработанный алгоритм позволяет исследовать особенности движения ММР. Приведена структурная схема диалогового алгоритма многокритериальной оптимизации на множестве альтернативных переменных.
When forming the structure of the robot the search algorithm, which consists in the use of procedures многоальтернативной optimization can be combined. When selecting a target option search algorithm, characterized by higher efficiency for the considered class of design objects is connected. In the paper the integration algorithm multiple-choice selection and genetic algorithm is carried out. For the operation of reproduction the recombination is used of genes two parent chromosomes, selected on the basis of a cross. And thus we gets a new variant of an alternative set of variables that determine the structure and the motion control algorithm. Parental chromosomes are compared on the content of each gene. With the purpose of abbreviations many promising options a reproduction group is created using breeding schemes. The developed algorithm allows to investigate the features of the MMR. The structural scheme of the dialog algorithm for multiobjective optimization on a set of alternative variables is given.
optimization
robot
genetic algorithm
simulation
1. Andrahanov S.V., Lvovich Y.E, Preobrazhensky A.P., Integratsia algoritma mnogoaltivnoy optimizatsii I geneticheskogo algoritma v uchebno-issledovatelskoy SAPR. Vestnik Voronezhskogo institute vysokih tehnologiy. Bulletin of Voronezh institute of high technologies, 2013, no. 10, pp. 4–8.
2. Andrahanov S.V., Lvovich Y.E, Preobrazhensky A.P., Uchebno-issledovatelskaya SAPR mehatronno-modulnyhrobotov. Vestnik Voronezhskogo gosudarstvennogo tehnicheskogo universiteta. Bulletin of Voronezh state technical university, 2013, vol. 9, no. 3–1, pp. 24–27.
3. Kochetkova O.V., Kaznacheeva A.A., Razrabotka metoda I sredstv predstavleniya modeli spetsialista v uchebno-issledovatelskih SAPR (monographiya). Mezhdunarodny zhurnal prikladnyh I fundamentalnyh issledovany, 2012, no. 9, pp. 79–80.
4. Lvovich Ya.E., Mnogoalternativnaya optimizatsiya: teoriya I prilozheniya [Multialternative optimization: theory and using]: Textbook. Voronezh, Kvarta, 2006. 428 p.
5. Lvovich Ya.E., Andrahanov S.V. Integratsiya protsedur mnogoalternativnoy optimizatsii I metoda royachastits. Vestnik Voronezhskogo gosudarstvennogo tehnicheskogo universiteta. Bulletin of Voronezh state technical university. 2010, vol. 6, no. 12, pp. 17–20.
6. Makarov I.M., Lohin V.M., Manko S.V., Romanov M.P., Kadochnikov M.V. Tehnologii obrabotki v zadachah upravleniya avtonomnymi mehatronno-modulnymi robotami / Prilozheniye k zhurnalu «Informatsionnye tehnologii». Addition to journal «Information technologies», no. 8, 2010.
7. Smolnikov B.A. Problemy mehaniki i optimizatsii robotov [Problems of mechanics and optimization of robots]. Moscow, Nauka, 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.