Общий алгоритм проектирования операционной технологии

Рассмотрим общий алгоритм проектирования операционной технологии [3.96].

В соответствии с характером решаемых задач и структурой критерия оптимальности проектирования синтез технологических операций расчленяется на четыре составные части. В первой определяются наиболее рациональные форма, припуски, допуски и межоперационные размеры изделия, поступившего на операцию, т.е. состояние С^.

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

Алгоритмы третьей части осуществляют синтез временной структуры операции, т. е. уточняют состав переходов, определяют порядок их выполнения и характер совмещения во времени.

В четвертую часть входят алгоритмы определения параметров и технико-экономических характеристик операции.

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

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

Итак, мы рассмотрели три уровня для автоматизированных систем проектирования ТП:

  • • проектирование принципиальной схемы;
  • • проектирование технологического маршрута;
  • • проектирование операционной технологии.

Процесс проектирования от уровня к уровню и на каждом уровне является итерационным с накоплением опыта, обобщением и корректировкой на каждом уровне [3.97, 3.98].

Эти результаты можно использовать для разработки типовых, групповых алгоритмов и технологических процессов-аналогов.

Операцией «обобщение» накопленного опыта из числа ранее спроектированных ТП формируются типовые проектные решения, типовые и групповые алгоритмы. Улучшается значение эвристических критериев самоотбора, совершенствуются структура и параметры алгоритмов синтеза, анализа и оптимизации. Обобщение накопленного опыта проводится в режиме человеко-машинного проектирования с оперативным отображением процессов-аналогов на экраны дисплеев.

В результате обучения и самообучения алгоритмы синтеза проектных решений и эвристические критерии промежуточного самоотбора становятся более эффективными. Вместо генерирования большого числа возможных вариантов - целенаправленно, с учётом положительного прошлого опыта синтезируется меньшее количество наиболее перспективных проектных решений (вариантов). За счёт улучшения значений эвристических критериев в процессе самообучения на каждой промежуточной стадии отбирается для дальнейшего проектирования меньшее, чем прежде, число наиболее рациональных вариантов.

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

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

Аналогичное положение наблюдается при автоматизации проектирования ТП - аналогов.

В результате приходим к необходимости организации итерационной модели процесса проектирования, основной чертой которой является последовательное улучшение исходного варианта до требуемой степени совершенства.

На основании анализа конструкторско-технологической документации в процессе разработки алгоритмов проектирования создают фонд информации для автоматизированного проектирования ТП изготовления элементов РЭС; этот фонд дополняют в процессе функционирования САПР.

Синтез операционного технологического процесса. Как уже отмечалось выше, синтез операционных технологий связан со многими трудностями из-за большого числа параметров. Наибольшие из них возникают при генерации схем простановки операционных размеров, число которых, даже при наличии ограничений, связанных с базированием детали, велико. Как следствие, перебор всех вариантов схем простановки операционных размеров с целью поиска оптимального из них требует длительных вычислений.

Для решения этой проблемы применим эволюционный способ решения задач оптимизации на основе генетического алгоритма [3.65- 3.67]. Его использование минимизирует время поиска оптимального решения. Суть постановки задачи синтеза рассмотрим, используя традиционно принятую в этом способе терминологию.

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

Генетический алгоритм реализует итерационный процесс. В начале его работы случайным образом генерируется первая популяция. На каждом следующем шаге алгоритм реализует оценку приспособленности, отбор лучших особей, кроссовер и мутацию. Таким образом, из поколения в поколение хорошие характеристики распространяются по всей популяции и, в конечном итоге, процесс сходится к оптимальному решению.

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лёг в основу практически всех вариантов генетических алгоритмов. Однако перед тем, как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

Представление объектов

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

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Кодирование признаков, представленных целыми числами

Для кодирования таких признаков можно использовать самый простой вариант - битовое значение этого признака. Тогда нам будет весьма просто использовать ген определённой длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так, например, числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости.

Для того, чтобы избежать эту проблему, лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма.

Кодирование признаков, которым соответствуют числа с плавающей точкой

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

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

Рассмотрим вышеописанную последовательность действий на примере:

Допустим, что значения признака лежат в интервале [0,1]. При кодировании использовалось разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется, таким образом, 8 бит. Допустим значение гена: 0010010 lbG (заглавная буква G показывает, что используется кодирование по коду Грея). Для начала, используя код Грея, найдём соответствующий ему номер интервала: 25hG- >36h->54d. Теперь посмотрим, какой интервал ему соответствует. После определённых подсчётов получили интервал [0,20703125, 0,2109375]. Значит, значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

При кодировании нечисловых данных необходимо предварительно преобразовать их в числа.

Определение фенотипа объекта по его генотипу

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих _03 яи1086 объект), нам необходимо только знать значения генов, соответствующих этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях её также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации её значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длиной в 4 элемента. Тогда длина хромосомы будет 5*4=20.

Основные генетические операторы

Как известно, в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется «скрещивание» (его также называют кроссовер или крос- синговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:

  • • из популяции выбираются две особи, которые будут родителями;
  • • определяется (обычно случайным образом) точка разрыва;
  • • потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора:

Хромосома_1:0000000000

Хромосома_2: 1111111111

Допустим, разрыв происходит после 3-го бита хромосомы, тогда

Хромосома_1: 0000000000В »В 000В 1111111В Результирую-

щая_хромосома

Хромосома_2: 1111111111В »В 111В 0000000В Результирую

щая хромосома

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111 » 1111111 000

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

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

Схема функционирования генетического алгоритма

Теперь, зная как интерпретировать значения генов, перейдём к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

  • 1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из к особей. ВО = (А1,А2,...,Ак).
  • 2. Вычислить приспособленность каждой особи FAi = fit(Ai), i=l.. .к и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет, насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  • 3. Выбрать особь Ас из популяции. Ас = Get(Bt).
  • 4. С определённой вероятностью (вероятностью кроссовера Рс) выбрать вторую особь из популяции Acl = Get(Bt) и произвести оператор кроссовера Ас = Crossing (Ac, Acl).
  • 5. С определённой вероятностью (вероятностью мутации Pm) выполнить оператор мутации Ас = mutation(Ac).
  • 6. С определённой вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ас - inversion(Ac).
  • 7. Поместить полученную хромосому в новую популяцию insert (Bt+l,Ac).
  • 8. Выполнить операции, начиная с пункта 3, к раз.
  • 9. Увеличить номер текущей эпохи t = t+1.
  • 10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой. При использовании такого метода вероятность выбора хромосомы определяется её приспособленностью, то есть PGet(Ai) ~ Fit(Ai)/Fit(Bt). Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод - турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантированно переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >