Полная версия

Главная arrow Строительство arrow Актуальные направления научных исследований XXI века: теория и практика: Сборник научных трудов по материалам международной заочной научно-практической конференции, 2015, №6, (17) -

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

УДК 519.688

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПОИСКА ОПТИМАЛЬНЫХ ПАРАМЕТРОВ ТЕХНИЧЕСКИХ СИСТЕМ ДЛЯ САПР

GENETIC SEARCH ALGORITHM OPTIMAL PARAMETERS FOR CAD OF TECHNICAL SYSTEMS

Моисеев Г.Д., кандидат технических наук, доцент, ФГБОУ ВО «Брянский государственный

инженерно - технологический

университет», Россия, Брянск.

Прусс Б.Н., кандидат технических наук, доцент, ФГБОУ ВО «Брянский государственный

инженерно - технологический

университет», Россия, Брянск.

Колесников П.Г., кандидат технических наук, доцент, ФГБОУ ВО «Сибирский государственный

технологический университет»,

Россия, Красноярск.

Шерстюк Е.А., магистрант, ФГБОУ ВО «Брянский

государственный инженернотехнологический университет»,

Россия, Брянск.

Moiseev G.D., Candidate of Technical Sciences, assistant professor, FGBOU VO «The Bryansk state engineering and technological University», Russia, Bryansk.

Pruss B.N., Candidate of Technical Sciences, assistant professor, FGBOU VO «The Bryansk state engineering and technological University», Russia, Bryansk.

Kolesnikov P.G., Candidate of Technical Sciences, assistant professor, FGBOU VO «The Krasnoyarsk state technological University», Russia, Krasnoyarsk.

Sherstiuk E.A., master student, FGBOU VO «The Bryansk state engineering and technological University», Russia, Bryansk.

DOI: 10Л2737/16385

Аннотация: приведён генетический алгоритм оптимизации технических систем.

Summary: genetic algorithm optimization of technical systems.

Ключевые слова: оптимизация, алгоритм, скрещивание, мутация.

Keywords: optimization, algorithm, crossover, mutation.

Определение оптимальных параметров технических систем в различных САПР является одной из наиболее актуальных задач проектирования. Задача определения оптимальных параметров технической системы при однокритериальной оптимизации в общей постановке сводится к определению допустимых значений параметров, при которых функция цели F минимальна, т.е. определить Xi, х2,...,хп , п>1,

где хь х2, ... хп - параметры оптимизации; F- функция цели (приспособленности- Fitness); п- размерность пространства параметров (количества параметров); lj, qj _ функции ограничений, выраженные равенствами и неравенствами. В общем случае функции F, 1ь qj _ нелинейные и негладкие, параметры Xj, х2,...,хпкак непрерывны, так и дискретны.

Для решения задачи (А), являющейся общей задачей нелинейного программирования, известны аналитические, численные, графические экспериментальные и другие методы [1]. Особый интерес представляют методы, основанные на случайном поиске, способные при многоэкстремальной функции цели определить глобальный экстремум.

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

где i- номер точки; j- номер параметра; п- число параметров. Все параметры Ху закодированы, т.е. нормализованы и находятся в диапазоне [0,1], что позволяет задать их значения как случайные числа, равномерно распределенные в этом диапазоне. Переход от кодированных значений к заданным Ху11 и наоборот осуществляется в соответствии с формулой:

где и границы естественных вариаций j-oro параметра.

Поскольку соблюдение m неравенств (3) эквивалентно проверке равенства

где G- свёртка неравенств, то далее происходит генерация дополнительных точек до тех пор , пока все К точек не окажутся допустимыми по ограничениям , т.е. будут удовлетворять условию (4). Поскольку несколько ограничений равенств можно свести к единственному ограничению, то вычисляется значение свертки равенств (2) для каждой из К точек

Далее вычисляется функция цели F и штрафная функция С, которая в дальнейшем используется в качестве критерия оптимизации:

Затем точки ранжируются по критерию С и отбирается заданное количество L лучших точек и образуется новое поколение Н точек путем рекомбинирования (скрещивания) параметров Р родителей (Р<К) и параметров L родителей, причём за j-й признак потомка принимают с равной вероятностью численное значение j-oro признака любого родителя. Далее вычисляются значения G, Е, С для Н точек и происходит при необходимости отбор новых L лучших точек.

Для моделирования взаимосвязи между интенсивностью мутаций и взаимодействием среды в алгоритме интенсивность мутаций зависит от отношения минимального значения критерия Cmjn , достигнутого в лучшей точке поколения , к значения критерия С[ для рассматриваемой точки

где Im - коэффициент интенсивности мутаций. Нетрудно убедится в том, что Im также принадлежит интервалу [0,1], причём чем меньше отношение Cmin/ Q), тем большее значение будет иметь коэффициент мутации Im.

Мутация точек осуществляется в сторону, соответствующую уменьшению функции С, что ускоряет достижение ее минимума

где S- случайное число в интервале [0,1]. Если, например, предыдущее значение параметра меньше текущего, а предыдущее значение критерия С больше текущего, то мутация параметра происходит в сторону его увеличения по формуле (8). Затем происходит редукция (сужение) интервала вариации параметров при сближении параметров первых двух из L лучших точек на наперёд заданную величину. Выход из оптимизации осуществляется либо при уменьшении интервала вариации параметров менее, чем на заранее заданную величину, либо при прекращении улучшения значения критерия оптимизации, т.е. нахождении глобального или субоптимального экстремума.

Тестирование алгоритма осуществлялось путём минимизации функций Розенброка, Шекеля, Растригина, Катникова, Гриванка, Де Йонга и др. Так функция безусловной оптимизации Розенброка имеет ярко выраженный овражный характер

Решение теста F* = 0; х{ = х = 1. При числе родителей К = 15, детей Н=15 на четвёртом поколении получено F = 0.000637; х± = 0994; х2 = 0.985.

Задача условной оптимизации требовала оптимизировать тест-функцию

При К = 20;Р = 15;кх2 [0.5;/]; Ер = 0.005; ее = 0.01 на 21-М поколении получено F =1.389; С=1,391; *1=0.8229; *2=0.9107. Несоблюдение ограничения

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

Список литературы

1. Holland J. Н. Adaptation in natural and artificial systems [Text] / J. H. Holland. - Ann Arbor. MI: University of Michigan Press, 1975.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>