Использование генетического алгоритма с целочисленным кодированием для решения задачи параметрического синтеза

Формальная постановка задачи ПС состоит в следующем. Пусть система обладает m выходными характеристиками, интересующими потребителя:

каждая из которых зависит от набора текущих значений параметров элементов системы (внутренних параметров):

в виде зависимостей:

Выражения (3) представляют собой собственно модель системы. Для достаточно сложных систем аналитическое выражение этих зависимостей практически недоступно, и они задаются в алгоритмическом виде [ 7, 8].

Качество функционирования системы определяется ограничениями на выходные параметры, которые называются условиями работоспособности (УР):

Эти ограничения определяют в пространстве значений внутренних параметров область:

которая называется областью работоспособности (ОР) системы и представляет собой множество точек пространства внутренних параметров, при которых система находится в работоспособном состоянии.

Задача оптимального параметрического синтеза состоит в выборе номинальных значений внутренних параметров, обеспечивающих максимум вероятности нахождения этих параметров внутри ОР в течение требуемого интервала времени:

где X(x0, t) - случайный процесс изменения внутренних параметров от начального значения хо в момент времени t, в пределах заданного срока эксплуатации T. Характеристики ОР зачастую неизвестны, а в случае невозможности выразить их аналитически через уравнения модели (3) построение ОР представляет собой отдельную задачу [9, 10]. В случае отсутствия характеристик ОР выражение (6) может быть записано через проверку выполнения УР (4) для каждой случайной реализации набора внутренних параметров в следующем виде:

Основной трудностью использования стохастического критерия в выражениях (6) и (7) является отсутствие вероятностных характеристик случайного процесса X(x0, t). В случае невозможности применить стохастический критерий или с целью проведения дополнительных исследований используется детерминированный критерий, - например, критерий максимального запаса работоспособности на основе построения вписанных в ОР фигур [10, 11]. При отсутствии характеристик случайного процесса дрейфа параметров задачу ОПС можно свести к выбору параметров по критерию максимальной серийнопригодности путем имитации производственного разброса параметров некоторым образом перебираемых значений номиналов, - например, полным перебором на регулярной сетке [ 12]. Предложенный в данной работе подход на базе ГА позволяет выполнять перебор точек в пространстве поиска на основе их эволюции и естественного отбора по установленному критерию оптимальности решения задачи ПС.

Критерий максимального запаса работоспособности

Определенной характеристикой возможности системы выполнять заданные функции в условиях параметрических возмущений является ОР, построенная в координатах параметров схемных элементов системы. Совокупность значений внутренних параметров может быть представлена изображающей точкой в пространстве этих параметров. Для обеспечения работоспособности системы эта точка должна находиться внутри ОР. При этом расстояние от изображающей точки до границы ОР можно рассматривать как некоторый запас работоспособности системы.

Запас работоспособности позволяет оценить степень удаленности вектора внутренних параметров от границ области работоспособности, а следовательно, пределы возможных вариаций параметров элементов, при которых не нарушаются УР (4). Задача ОПС в этом случае сводится к нахождению таких точек внутри ОР, которые находятся на максимальном в смысле выбранной меры расстояния от ее границы.

При отсутствии информации о тенденциях параметрического дрейфа часто рассматривается наихудший случай - кратчайшее расстояние от изображающей точки до границы ОР. Тогда задача оптимизации состоит в выборе точки внутри ОР, максимизирующей кратчайшее расстояние до границы ОР. Очевидно, что фигурой, обеспечивающей минимальный запас работоспособности, является вписанный в ОР шар. В этом случае (рис. 1) оптимальным решением задачи ОПС будет центр вписанного шара с максимальным объемом

Рис. 1. Критерий оптимальности значений параметров на основе вписанного в ОР шара.

В зависимости от способа представления ОР вписанными в область могут быть и другие фигуры, - например, многомерные окрестности Мура и фон Неймана для представления ОР дискретным множеством гиперпараллелепипедов на основе регулярной сетки [11].

В данной работе рассматривается упрощенный критерий оптимальности, основанный на максимизации кратчайшего расстояния до границы ОР в направлении координатных осей. В этом случае (рис. 2) для каждой точки xeDx измеряется 2п расстояний

(rf(x), r+(x)), Vi = 1, 2,..., n

до границы области, из которых выбирается минимальное.

Рис. 2. Выбор кратчайшего расстояния до границы ОР в направлении осей координат

Величина rmin(x) принимается за кратчайшее расстояние от точки x до границы ОР при рассмотрении наихудшего варианта параметрического дрейфа. Задача ПС в данном случае состоит в поиске точки xoeDx, обеспечивающей максимальное rmin(x):

Применение генетического алгоритма к задаче ПС

Генетические алгоритмы (ГА) представляют собой подход к решению оптимизационных задач на основе эволюции и селекции потенциальных решений, построенный на аналогии с биологическим механизмом эволюции и естественного отбора организмов. Каждая особь популяции в ГА представляет собой потенциальное решение задачи, закодированное в виде ее хромосом. Для каждой особи популяции вычисляется значение приспособленности, что в терминах задачи оптимизации соответствует значению критерия оптимальности для данного решения. Начальная популяция, как правило, порождается случайным образом, но и не исключены другие способы, целесообразные для конкретной задачи. Последующие популяции порождаются из текущей популяции путем комбинирования генетического материала хромосом наиболее приспособленных особей.

Одной из причин использования данного подхода к решению задачи ОПС - невозможность применения градиентных методов ввиду отсутствия явных зависимостей в модели (3). В этом случае ОР можно исследовать только поточечно, а ГА позволяют, не прибегая при этом к полному перебору, находить оптимальное решение.

В данной работе за основу взят канонический ГА с целочисленным кодированием хромосом в двоичном виде. Каждая особь (фенотип) xgDx обладает определенным генотипом, однозначно определяющим набор исходных параметров. Генотип определяется набором хромосом. В каноническом ГА в качестве хромосом используется двоичное представление параметров задачи. Оперирование двоичным представлением целых чисел вызывает меньше затруднений, чем чисел с плавающей точкой ввиду более сложного внутреннего представления последних [12]. Кодирование действительных чисел с помощью двоичного кода целых чисел осуществляется использованием регулярной сетки, наложенной на область поиска внутри интервала ,n с шагом Si. Тогда каждому значению параметра Xi соответствует целочисленный индекс узла этой сетки:

Обратная операция вычисления значения параметра может быть выполнена только с точностью шага сетки, поэтому обозначим ее как:

Таким образом, целочисленный набор индексов d = (d1, d2, dn) представляет собой генотип особи x = (x1, x2, ...,xn). Каждое значение di представляет собой отдельную хромосому, над которой выполняются генетические операции скрещивания и мутации для порождения популяции потомков. Эти операции выполняются над двоичным представлением числа, поэтому нет необходимости в их преобразовании в строку. К целочисленным значениям хромосом часто применяют операцию кодирования Грея ввиду значительного расстояния Хэмминга (количество отличающихся двоичных разрядов) между некоторыми соседними числами, - например: 710 = 01112 и 810 = 10002 отличаются четырьмя разрядами, при этом коды Грея этих чисел в двоичном представлении будут иметь вид: gray(710) = 01002, gray(8\o) = IIOO2 [5, 13]. Обозначим преобразованные с помощью кода Грея индексы:

а обратную операцию получения значения индекса по его коду Грея обозначим как:

Формирование начальной популяции. Начальная популяция особей P° = {x10, x20, ..., xK0} формируется, как правило, случайным образом, где K - количество особей в популяции. Генетический алгоритм оперирует только их генотипом, поэтому выполняется вычисление индексов сетки (10) и их кодов Грея (12), что формирует набор генотипов популяции И° = {d10, d20, ..., dK0}, где di0 = (d1g0, d2g0, ..., dng0) - генотип i-й особи, состоящий из закодированных кодом Грея (13) n хромосом.

Вычисление функции приспособленности. Каждой особи присваивается значение ее функции приспособленности. В данной работе в качестве такой функции выступает выражение (10) вычисления кратчайшего расстояния rmin(xi0) до границы ОР для каждой особи xi0 популяции. Для начальной популяции могут быть использованы исходные значения параметров P0 = {x10, Х 20, ..., хк 0}, но для всех последующих итераций необходимо восстановить декодированием кода Грея (1 3) индексы элемента сетки и по ним вычислить значения параметров xsi = {x1si, x2si, ...,xnsi} (11). Обозначим множество значений функции приспособленности для i-й популяции:

Для начальной популяции множество значений приспособленности имеет вид F° = {/1°,/20, ...,fk0}. Эти значения используются не только для отбора наилучшего решения популяции:

но и выполнения одной из важных процедур в ГА - селекции особей.

Селекция. Селекция представляет собой процедуру, имитирующую естественный отбор наиболее приспособленных особей для порождения популяции потомков. Одним из распространенных способов выбора особи для порождения потомков в соответствии с ее значением приспособленности (14) является так называемый "метод рулетки", состоящий в разбиении круга на сектора, центральные углы которых пропорциональны значениям приспособленности (14) каждой особи популяции. Выбор особи осуществляется на случайном выпадении соответствующего ей сектора [5].

В качестве реализации "метода рулетки" в данной работе используется отрезок [0,1], разбитый на K интервалов, длина каждого вычисляется по формуле:

где i - номер популяции; j - номер особи в популяции. Производится генерирование случайного числа с равномерным распределением и вычисление индекса v интервала, в который попала эта точка. Очевидно, что при равномерном распределении у особи с наибольшим значением приспособленности шанс отбора выше, поскольку ей будет соответствовать более длинный интервал.

Для выбранной особи с генотипом dvi по такому же принципу выбирается особь с генотипом dui так, чтобы и?v. Выбранная пара особей участвует в порождении пары потомков путем скрещивания.

Скрещивание (кроссовер). Оператор скрещивания (кроссовера) в ГА представляет собой процедуру порождения новых особей следующей популяции путем комбинирования генетического материала двух родительских особей. Под комбинированием генетического материала в каноническом ГА понимается обмен частями родительских хромосом, разрезанных по случайно выбранной позиции (локусу) гена.

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

Для каждой к-й пары скрещиваемых родительских хромосом выбирается случайная позиция 1к, 1 < lk < B гена, по которому производится разрезание хромосомы обоих родителей на две части, где B - количество двоичных разрядов в хромосоме. Хромосома с номером к первого родителя с индексом и в популяции делится на левую часть pku, состоящую из (B - lk) разрядов (нумерация двоичных разрядов выполняется справа налево), и правую часть qku, состоящую из lk двоичных разрядов. Аналогично разбивается k-я хромосома второго родителя с номером v в текущей популяции: pkv и qkv соответственно.

Порождаемые две особи следующего поколения будут иметь k-е хромосомы, составленные из попарно перемешанных фрагментов родительских хромосом: pku u qkV и pk u qku. Если в случае вероятностного определения скрещиваемых хромосом для текущей пары операция кроссовера не требуется, то состояния этих хромосом неизменно передаются потомкам.

На рис. 3 схематически проиллюстрирована операция скрещивания для одной хромосомы двух особей.

Рис. 3. Скрещивание родительских хромосом.

Мутация. Генетический оператор мутации применяется к отдельным хромосомам особей нового поколения с вероятностью Pmut и заключается в инверсии случайного двоичного разряда.

Например, состояние k-й хромосомы особи равно 010010112 = 75ю. Тогда в случае мутации случайного гена lk = 3 будет произведена инверсия этого разряда, и значение хромосомы станет 010011112 = 7910.

Алгоритм поиска оптимального решения. Описанные выше процедуры выполняются циклически в указанной последовательности до тех пор, пока не будет достигнуто условие остановки. Остановкой главного цикла ГА является либо получение одинакового с точностью заданной погрешности s решения (15) в двух последовательных итерациях, либо достижение максимального количества шагов цикла. Алгоритм поиска оптимального решения задачи ОПС (6) с помощью ГА состоит из следующих этапов:

1) порождение начальной популяции Н 0;

2) вычисление функции приспособленности (9) для каждой особи;

3) селекция: отбор наиболее приспособленных особей и порождение новой популяции Н 1;

4) переход к этапу 2, если не выполнены условия остановки алгоритма.

Схематически алгоритм представлен блок-схемой на рис. 4.

Рис. 4. Блок-схема решения задачи ПС с помощью ГА .

Пример

Рассматривается делитель напряжения, принципиальная схема которого изображена на рис. 5 [9].

Рис. 5. Принципиальная схема делителя напряжения.

Внутренними параметрами делителя являются: x1 = R1 - сопротивление резистора Ri, Ом; Х 2 = R2 - сопротивление резистора R2, Ом; хз = C - емкость конденсатора C, Ф; х 4 = ивх - входное напряжение, В.

Выходными характеристиками этого делителя являются: y1 = т - постоянная времени перезаряда конденсатора C; y = P - мощность рассеяния, Вт; у 3 = ивых - напряжение на выходе делителя, В.

Выходные характеристики связаны с параметрами элементов выражениями [9]:

На выходные характеристики налагаются условия работоспособности:

Кодирование параметров осуществлялось с помощью регулярной сетки из 256 интервалов. Таким образом, каждая хромосома состояла из 8 генов - двоичных разрядов. В качестве значения хромосомы выступало двоичное представление не самого индекса сетки, соответствующего значению параметра, а его кода Грея. Начальная популяция состояла из 54=625 точек регулярной сетки (по 5 на каждый параметр) внутри описанного гиперпараллелепипеда: параметрический дрейф детерминированный

В пределах установленного ограничения в 20 итераций (поколений) было найдено оптимальное решение задачи ПС по критерию максамальной удаленности от границы ОР по направлениям координатных осей (рис. 6).

Оптимальные значения параметров составляют:

Рис. 6. Сечение ОР с отображением найденного с помощью ГА решения.

Заключение

Литература

1. Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. - М.: Наука, 1965.

2. Абрамов О.В. Возможности и перспективы функционально-параметрического направления теории надежности // Информатика и системы управления. - 2014. - №4(42). - С. 53-66.

3. Parkinson D.B. Robust Design Employing a Genetic Algorithm // Quality and Reliability Engineering International. - 2000. - 16. - P. 201-208.

4. Chatsirirungruang P. Application of Genetic Algorithm and Taguchi Method in Dynamic Robust Parameter Design for Unknown Problems // International Journal of Andvanced Manufacturing Technology. - 2010. - Vol. 47. - P. 993-1002.

5. Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning. - Addi- son-Wesley, 1989.

6. Абрамов О.В., Назаров Д.А. Программно-алгоритмический комплекс построения, анализа и использования областей работоспособности // Информационные технологии и вычислительные системы. - 2015. - №2. - С. 3-13.

7. Норенков И.П. Основы автоматизированного проектирования. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

8. Черноруцкий И.Г. Оптимальный параметрический синтез: Электротехнические устройства и системы. - Л.: Энергоатомиздат. Ленингр. отд., 1987.

9. Саушев А.В. Области работоспособности электротехнических систем. - СПб.: Политехника, 2013.

10. Назаров Д.А. Использование областей работоспособности для оптимального выбора номиналов параметров // Информатика и системы управления. - 2011. - №2(28). - С. 59-69.

11. Катуева Я.В., Назаров Д.А. Методы параметрического синтеза на основе сеточного представления области работоспособности // Информационные технологии. - 2015. - №9. - С. 651-656.

12. Лагунова А.Д., Назаров Д.А. Параллельный алгоритм решения задачи оптимального параметрического синтеза на основе метода сеток // Труды Международного симпозиума "Надежность и качество". - 2018. - Т.1. - С. 255-258.

13. Budin L., Golub M,. Budin A. Traditional Techiques of Genetic Algorithms Applied to Floating-Point Chromosome Representations // Proceedings of the 41st Annual Conference KoREMA, Opatija. - 1996. - Р. 93-96.

Размещено на Allbest.ru