4.3.1. Эффективность применения генетических алгоритмов и средства ее повышения. Эффективность генетического алгоритма при решении конкретной задачи зависит от многих факторов и, в частности, от таких, как генетические операторы и выбор соответствующих значений параметров, а также способа представления задачи на хромосоме. Тщательный подбор этих факторов приводит к повышению скорости и устойчивости поиска, что существенно для применения генетических алгоритмов.
Скорость генетического алгоритма оценивается временем, необходимым для выполнения заданного пользователем числа итераций. Если критерием останова является качество популяции или ее сходимость, то скорость оценивается временем достижения генетическим алгоритмом одного из этих событий.
Устойчивость поиска оценивается степенью устойчивости алгоритма к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению.
Два этих фактора: скорость и устойчивость - и определяют эффективность генетического алгоритма для решения каждой конкретной задачи.
Основным способом повышения скорости работы генетических алгоритмов является распараллеливание. Причем этот процесс можно рассматривать с двух позиций. Распараллеливание может осуществляться на уровне организации работы генетического алгоритма и на уровне его непосредственной реализации на вычислительной машине.
Во втором случае используется следующая особенность генетических алгоритмов. В процессе работы многократно приходится вычислять значения целевой функции для каждой особи, осуществлять преобразования оператора скрещивания и мутации для нескольких пар родителей и т.д. Все эти процессы могут быть реализованы одновременно на нескольких параллельных системах или процессорах, что пропорционально повысит скорость работы алгоритма.
В первом же случае применяется структурирование популяции решений на основе одного из двух подходов [7,102,103]:
1. Популяция разделяется на несколько различных подпопуляций (демосов), которые впоследствии развиваются параллельно и независимо. То есть скрещивание происходит только между членами одного демоса. На каком-то этапе работы происходит обмен частью особей между подпопуляциями на основе случайной выборки. И так может продолжаться до завершения работы алгоритма. Данный подход получил название концепции островов.
2. Для каждой особи устанавливается ее пространственное положение в популяции (например, с помощью матрицы расстояний между особями). Скрещивание в процессе работы происходит между ближайшими особями. Такой подход получил название концепции скрещивания в локальной области.
Оба подхода, очевидно, также могут эффективно реализовываться на параллельных вычислительных машинах. Кроме того, практика показала, что структурирование популяции приводит к повышению эффективности генетического алгоритма даже при использовании традиционных вычислительных средств.
Еще одним средством повышения скорости работы является кластеризация. Суть ее состоит, как правило, в двухэтапной работе генетического алгоритма. На первом этапе генетический алгоритм работает традиционным образом с целью получения популяции более "хороших" решений. После завершения работы алгоритма из итоговой популяции выбираются группы наиболее близких решений. Эти группы в качестве единого целого образуют исходную популяцию для работы генетического алгоритма на втором этапе. Размер такой популяции будет, естественно, значительно меньше, и, соответственно, алгоритм будет далее осуществлять поиск значительно быстрее. Сужения пространства поиска в данном случае не происходит, потому что применяется исключение из рассмотрения только ряда очень похожих особей, существенно не влияющих на получение новых видов решений.
Рассмотрим теперь влияние генетических операторов (операторов отбора, скрещивания и мутации) на устойчивость поиска. Как правило, диапазон такого влияния можно оценить, рассматривая вырожденные случаи указанных операторов.
Вырожденными формами операторов скрещивания являются, с одной стороны, точное копирование потомками своих родителей, а с другой, порождение потомков, в наибольшей степени отличающихся от них. Преимуществом первого варианта является скорейшее нахождение лучшего решения, а недостатком, в свою очередь, тот факт, что алгоритм не сможет найти решения лучше, чем уже содержится в исходной популяции, поскольку в данном случае алгоритм не порождает принципиально новых особей, а лишь копирует уже имеющиеся. Чтобы все-таки использовать достоинства этой формы операторов скрещивания в реальных генетических алгоритмах, применяют элитизм.
Во втором случае алгоритм рассматривает наибольшее число различных особей, расширяя область поиска, что, естественно, приводит к получению более качественного результата. Недостатком в данном случае является значительное замедление поиска. Одной из причин этого, в частности, является то, что потомки, значительно отличаясь от родителей, не наследуют их полезных свойств.
В качестве реальных операторов скрещивания используются промежуточные варианты. В частности, родительское воспроизводство с мутацией и родительское воспроизводство с рекомбинацией и мутацией. Родительское воспроизводство означает копирование строк родительских особей в строки потомков. В первом случае после этого потомки подвергаются воздействию мутации. Во втором случае после копирования особи-потомки обмениваются подстроками, этот процесс называется рекомбинацией. После рекомбинации потомки также подвергаются воздействию мутации. Последний подход получил наибольшее распространение в области генетических алгоритмов.
Наиболее распространенными при этом являются одноточечный, двухточечный и равномерный операторы скрещивания. Свои названия они получили от принципа разбиения кодовой строки на подстроки. Строка может, соответственно, разбиваться на подстроки в одном или двух местах. Или строки могут образовывать особи-потомки, чередуя свои элементы.
Основным параметром оператора мутации является вероятность его воздействия. Обычно она выбирается достаточно малой, чтобы, с одной стороны, обеспечивать расширение области поиска, а с другой, не привести к чересчур серьезным изменениям потомков, нарушающим наследование полезных параметров родителей. Сама же суть воздействия мутации обычно определяется фенотипом и на эффективность алгоритма особого воздействия не оказывает.
Существует также дополнительная стратегия расширения поискового пространства, называемая стратегией разнообразия. Если генетический алгоритм использует данную стратегию, то каждый порожденный потомок подвергается незначительному случайному изменению. Отличие разнообразия и мутации в том, что оператор мутации вносит в хромосому достаточно значительные изменения, а оператор разнообразия - наоборот. В этом заключается основная причина стопроцентной вероятности применения разнообразия. Ведь если часто вносить в хромосомы потомков незначительные изменения, то они могут быть полезны, с точки зрения, как расширения пространства поиска, так и наследования полезных свойств. Отметим, что стратегия разнообразия применяется далеко не во всех генетических алгоритмах, поскольку является лишь средством повышения эффективности.
Еще одним важнейшим фактором, влияющим на эффективность генетического алгоритма, является оператор отбора. Слепое следование принципу "выживает сильнейший" может привести к сужению области поиска и попаданию найденного решения в область локального экстремума целевой функции, с другой стороны, слишком слабый оператор отбора может привести к замедлению роста качества популяции, а значит, и к замедлению поиска. Кроме того, популяция при этом может не только не улучшаться, но и ухудшаться. Самыми распространенными операторами отбора родителей являются:
• случайный равновероятный отбор;
• рангово-пропорциональный отбор;
• отбор пропорционально значению целевой функции.
Одним из параметров, также влияющих на устойчивость и скорость поиска, является размер популяции, с которой работает алгоритм. Классические генетические алгоритмы предполагают, что размер популяции должен быть фиксированным. Такие алгоритмы называют алгоритмами стационарного состояния. В этом случае оптимальным считается размер 21og2(n), где n - количество решений задачи.
Однако практика показала, что иногда бывает полезно варьировать размер популяции в определенных пределах. Подобные алгоритмы получили название поколенческих. В данном случае после очередного порождения потомков усечения популяции не происходит. Таким образом, на протяжении нескольких итераций размер популяции может расти, пока не достигнет определенного порога. После чего популяция усекается до своего исходного размера. Такой подход способствует расширению области поиска, но вместе с тем не ведет к значительному снижению скорости, поскольку усечение популяции хотя и реже, но все же происходит.
В последнее время в области исследований, направленных на повышение эффективности генетических алгоритмов, большое значение приобрели идеи создания адаптивных генетических алгоритмов, которые могут изменять свои параметры в процессе работы. Они стали продолжением развития идеи поколенческих алгоритмов, которые в процессе работы изменяют размер популяции. Адаптивные алгоритмы способны изменять не только этот параметр, но и суть генетических операторов, вероятность мутации и даже генотип алгоритма. Как правило, данные изменения происходят путем выбора параметров из нескольких вариантов, определенных перед началом работы алгоритма.
Идея адаптивных генетических алгоритмов получила свое воплощение в концепции nGA, представляющей многоуровневые генетические алгоритмы. Нижний уровень такого алгоритма непосредственно выполняет задачу улучшения популяции решений. Верхние уровни представляют собой генетические алгоритмы, решающие оптимизационную задачу по улучшению параметров алгоритма нижнего уровня. При этом в качестве целевой функции используется обычно скорость работы алгоритма нижнего уровня и скорость улучшения им популяции от поколения к поколению.
В настоящее время генетические алгоритмы представляют одну из интенсивно развивающихся областей науки, исследования в которой ведут к постоянному повышению эффективности их использования, а также выдвижению все новых подходов к построению конкретных алгоритмов. Отметим, что до недавнего времени в качестве критерия качества большинства конкретных генетических алгоритмов использовалась эффективность решения задачи получения битового вектора с максимальным числом единичных разрядов. Чем быстрее алгоритм находил наилучшее решение, тем он считался эффективнее. Сейчас эта задача уже не является объективным средством тестирования алгоритмов, что свидетельствует об их бурном развитии не только с точки зрения применимости к тем или иным классам задач, но и с точки зрения их внутреннего построения и принципов работы.
Практическая деятельность человека ставит перед наукой все новые исследовательские задачи. Область применения генетических алгоритмов постоянно расширяется, что требует их совершенствования и исследования. Перечислим несколько новых задач, которые могут решаться с использованием генетических алгоритмов, и связанные с ними направления исследований в этой области.
Традиционные оптимизационные задачи имеют целевую функцию с фиксированной областью значений, называемой также ландшафтом [8,9]. В последнее время потребовалось решение задач, в которых ландшафт со временем может изменяться. То есть целевая функция при одних и тех же значениях аргументов в разные моменты времени может принимать различные значения. Создание алгоритмов, способных работать с такими задачами, является сейчас одной из актуальных и одновременно сложных проблем в области генетических алгоритмов. До сих пор продолжается дискуссия между сторонниками универсальных и проблемно-ориентированных представлений задач при использовании эволюционных вычислений. Можно говорить, что в этом вопросе чаша весов склоняется в сторону универсальных представлений, поскольку осуществлять изменения на уровне генотипа значительно проще и эффективнее, чем на уровне фенотипа.
Перспективным направлением развития является добавление к генетическим операторам ламарковских операторов, которые позволяют вводить в рассмотрение признаки, приобретенные особью не в результате наследования, а в течение своего жизненного цикла. Это еще более приближает модель генетических алгоритмов к природным процессам и, по мнению ученых, способно повысить их эффективность. Идея приближения генетических алгоритмов к реальному эволюционному процессу нашла свое отражение и в предложениях ввести в рассмотрение такие понятия, как вид и пол, учитывать взаимодействие особей в популяции в процессе "жизни", причем особей как одного вида, так и различных. Это позволит моделировать процессы сотрудничества, отношений хозяев и паразитов и т.д.
Помимо этих новых течений, в области исследования генетических алгоритмов ведутся работы и в традиционных направлениях. Создаются все новые разновидности операторов отбора, скрещивания и мутации. Конструируются адаптивные алгоритмы, совершенствуются методы распараллеливания вычислений и структурирования популяций. Одновременно разрабатываются методики оценки эффективности и тестирования генетических алгоритмов.
Таким образом, генетические алгоритмы представляют собой одну из важных и активно развивающихся парадигм обширной области алгоритмов поиска оптимальных решений. И в последнее время, с развитием методов компьютерной поддержки принятия решений, они приобретают все большее значение.
4.3.2. Применимость метода генетических алгоритмов к решению организационных и операционных задач. Область применения генетических алгоритмов в настоящее время достаточно обширна. Они успешно применяются для решения ряда больших и экономически значимых задач в бизнесе и инженерных разработках [7,95,100,101,102,103,109]. С их помощью были разработаны промышленные проектные решения, позволившие сэкономить многомиллионные суммы. Финансовые компании широко используют методы ГА для прогнозирования развития финансовых рынков при управлении пакетами ценных бумаг. Наряду с другими методами эволюционных вычислений генетические алгоритмы обычно используются для оценки значений непрерывных параметров моделей большой размерности, для решения комбинаторных задач, для оптимизации моделей, включающих одновременно непрерывные и дискретные параметры. Другая область применения - использование в системах извлечения новых знаний из больших баз данных, создание и обучение стохастических сетей, обучение нейронных сетей, оценка параметров в задачах многомерного статистического анализа, получение исходных данных для работы других алгоритмов поиска и оптимизации.
Генетические алгоритмы используются не только в задачах комбинаторного типа (таких как задача коммивояжера), но и в тех случаях, когда подбираемые параметры могут быть любыми действительными числами. Такова, например, задача оптимального распределения инвестиций. Пусть имеется некоторый капитал R, который нужно распределить между несколькими проектами с целью получения максимального дохода через определенный срок. Для каждого проекта задана функция дохода, приносимого проектом за этот срок, в зависимости от вложенной суммы. Используется также диверсификация, т. е. необходимо развивать параллельно несколько проектов и запрещается вкладывать в любой проект слишком большую сумму. В данной задаче целевой функцией является суммарная прибыль от инвестиций, а управляемыми параметрами — объемы вложений в каждый из проектов. Подобные модели являются стандартными для экономистов, но в них рассматриваются только линейные функции доходности. В этом случае точное решение можно получить с помощью линейного программирования (симплекс-метод). Однако в реальных задачах нет оснований считать все функции линейными — более того, они могут быть даже разрывными. При этом целевая функция имеет сложный вид и не является унимодальной. В такой нелинейной ситуации стандартные методики работают плохо — в частности, симплекс-метод неприменим принципиально, а градиентный метод чаще всего приводит к неоптимальному решению.
ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере. Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling [101] для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы.
Генетические алгоритмы в различных формах применились ко многим научным и техническим проблемам. Генетические алгоритмы использовались при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они использовались при проектировании нейронных сетей или управлении роботами. Они также применялись при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальный (такие как экономика и политические системы) и когнитивные системы.
Тем не менее, возможно наиболее популярное приложение генетических алгоритмов - оптимизация многопараметрических функций. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от некоторых входных параметров. В некоторых случаях, представляет интерес найти те значения параметров, при которых достигается наилучшее точное значение функции. В других случаях, точный оптимум не требуется - решением может считаться любое значение, которое лучше некоторой заданное величины. В этом случае, генетические алгоритмы - часто наиболее приемлемый метод для поиска "хороших" значений. Сила генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами, эта особенность ГА использовалось в сотнях прикладных программ, включая проектирование самолетов, настройку параметров алгоритмов к поиску устойчивых состояний систем нелинейных дифференциальных уравнений, создание расписаний движения транспортных средств и т.д.
Однако нередки случаи, когда ГА работают, не так эффективно, как ожидалось. Предположим, есть реальная задача, сопряженная с поиском оптимального решения, как узнать, является ли ГА хорошим методом для ее решения? До настоящего времени не существует строгого ответа, однако, многие исследователи разделяют предположения, что если пространство поиска, которое предстоит исследовать, - большое, и предполагается, что оно не совершенно гладкое и унимодальное (т.е. содержит один гладкий экстремум) или не очень понятно, или если функция приспособленности с шумами, или если задача не требует строго нахождения глобального оптимума - т.е. если достаточно быстро просто найти приемлемое "хорошее" решения (что довольно часто имеет место в реальных задачах) - ГА будет иметь хорошие шансы стать эффективной процедурой поиска, конкурируя и превосходя другие методы, которые не используют знания о пространстве поиска.
Если же пространство поиска небольшое, то решение может быть найдено методом полного перебора, и можно быть уверенным, что наилучшее возможное решение найдено, тогда как ГА мог с большей вероятностью сойтись к локальному оптимуму, а не к глобально лучшему решению. Если пространство гладкое и унимодальное любой градиентный алгоритм, такой как, метод скорейшего спуска будет более эффективен, чем ГА. Если о пространстве поиска есть некоторая дополнительная информация (как, например, пространство для хорошо известной задачи о коммивояжере), методы поиска, использующие эвристики, определяемые пространством, часто превосходят любой универсальный метод, каким является ГА. При достаточно сложном рельефе фитнесс функции методы поиска с единственным решением в каждый момент времени, такой как простой градиентный метод, могли сходиться к локальному решению, однако считается, что ГА, так как они работают с целой "популяцией" решений, имеют меньше шансов сойтись к локальному оптимуму и робастно функционируют при многоэкстремальном рельефе фитнесс функции.
Конечно, такие предположения не предсказывают строго, когда ГА будет эффективной процедурой поиска, конкурирующей с другими процедурами. Эффективность ГА сильно зависит от таких деталей, как метод кодировки решений, операторы, настройки параметров, частный критерий успеха. Теоретическая работа, отраженная в литературе, посвященной ГА, не дает оснований говорить о выработке каких-либо строгих механизмов для четких предсказаний.
Однако, для решения объемных операционных и организационных задач, методы ГА хорошо подходят. Их практически абсолютная гибкость позволяет моделировать всевозможные комбинации факторов и ограничений, причем не требует со стороны пользователя обширных знаний в области высшей математики.
4.3.3 Использование методов генетических алгоритмов к решению организационных задач на условных примерах. В рамках этого раздела были решены три задачи:
- проектирования гибких производственных систем, на основе групповых технологий;
- проектирования подразделений организационной структуры;
- создания транспортного расписания.
1. Решение задачи по проектирования гибких производственных систем, на основе групповых технологий. Построение гибких производственных систем связано с групповыми технологиями (группирование деталей в семейства), основанными в 1959 году Митрофановым [52],[58]. В последние два десятилетия они особенно тщательно изучаются различными исследователями и практиками. Основа концепции - метод, который определяет и использует схожесть между признаками некоторого набора объектов. Групповое производство - приложение групповых технологий на практике, для организации производственных групп, которые содержат набор машин, обрабатывающих семейство деталей. Важные области приложения групповых технологий - классификация и кодирование, планирование производственного процесса, проектирование семейства деталей и наборов машин, размещение групп и планирование групп. В области автоматизации производства, проектирование групп является первичным объектом исследований. Гибкие производственные системы (ГПС), компьютеризированное производство (КП), и концепция точно-в-срок (JIT) - примеры автоматизированных групп. Веммерлов и Джонсон (Wemmerlov, Johnson) суммировали причины, почему компании используют групповые технологии [119]:
·Сокращение времени производственного цикла
·Сокращение времени на инвентаризацию незавершенного производства
·Улучшение качества изделия
·Снижение времени реагирования на заказы клиента
·Снижение времени простоев и времени перемещения деталей между станками
·Увеличивается гибкость производства
Выгодность применения групповых технологий для рабочих выражается в увеличенной гибкости работы, во взаимодействии в рабочей группе, в снижении фрустрации планирования и повышение безопасности жизнедеятельности. Процедура формирования групп из наборов машин и семейств деталей называется в групповых технологиях проектированием производственных ячеек (ППЯ), (Manufacturing Cell Design – MCD). Чтобы решить ППЯ задачу, было разработано множество методов в течение прошедших двух десятилетий [97,98,104,105,106,108,110,112,113,116,118]. Было сделано множество попыток применить эволюционные поисковые алгоритмы к ППЯ проблеме. Среди них, генетические алгоритмы имеют наибольшую гибкость и необходимую комплексность для решения этой сложной проблемы.
Концепция групповых технологий отличается от традиционных методов организации производства. Если номенклатура изделий маленькая, а объем производства велик, то рациональная организация рабочего пространства - наиболее эффективный путь к массовому производству изделий. Организация производства упорядочивает набор различных машин в линейном потоке и выделяет один поток на каждое специфическое изделие. Как только для конкретного изделия организована производственная линия, и машины размещены в правильном порядке, время переналадки оборудования становиться равно нулю, а количество изделий в незавершенном производстве (НП), (work-in-progress (WIP)), общее время производственного цикла и время погрузочно-разгрузочных работ, сильно сокращаются. Как только номенклатура начинает расти и производство каждого наименования уменьшается, выделение отдельной производственной линии прекращает быть эффективным средством организации производства, вследствие того, что это потребовало бы большого количества дублирующихся станков и дополнительного пространства. Поэтому там, где используются одинаковые станки и персонал со взаимнопересекающимися навыками, организация производства носит функциональный характер. Число идентичных станков сокращается, так как загрузка каждого увеличивается, благодаря равному распределению рабочей мощности среди всех видов изделий. Функциональное размещение дает самую большую гибкость при производстве большого ассортимента изделий. Новые изделия могут быть введены в производство без проблем, так как изделие может легко посещать каждую из необходимых функциональных групп. Типичные недостатки функционального размещения включают в себя [101]:
·увеличенное время переналадки оборудования, вследствие разнообразия изделий, которые производятся;
·большое количество погрузочно-разгрузочных работ, так как изделия должны теперь перемещаться по всему цеху;
·трудности планирования, из-за числа изделий и распределения ограниченных производственных ресурсов среди этих изделий;
·большой объем продукции находиться в состоянии незавершенного производства, потому что многие различные изделия требуют одинаковых станков, таким образом, вызывая задержки.
Чтобы преодолеть недостатки функционального размещения при сохранении гибкости производства для создания разнообразия ассортимента изделий в маленьком и среднем размерах партий, может использоваться метод групповых технологий, основанный на принципах группирования изделий и станков в семейства и наборы. Размещение групп может рассматриваться как комбинация размещения станков и размещения изделий по станкам, где набор различных машин сгруппирован вместе, чтобы обработать семейство схожих изделий. Станки внутри группы размещаются в линейном или U-образном порядке. Поэтому, семейство изделий, производится на очень небольшом участке, где существует один основной производственный поток.
Решение ППЯ задачи - важный шаг в разработке и воплощении групповых и гибких систем производства. Семейство изделий может состоять из групп изделий, требующих подобных, а иногда идентичных, производственных процессов, материалов и инструментальных средств. Станки, требующиеся чтобы произвести семейство изделий, сгруппированы так, чтобы сформировать производственную ячейку. Проиллюстрировать ППЯ задачу можно с помощью матрицы станков/изделий, показанной в таблице 15. Каждый (j,k)-ый элемент матрицы = 1, если j-ое изделие обрабатывается k-ым станком; иначе, этот элемент = 0.
После рекомбинации строк и столбцов в таблице 15 конечные группы представлены в таблице 16. Эти конечные группы, соответствующие производственным группам (участкам) формируют производственную систему. Как результат, могут быть сформированы три производственных ячейки из соответствующих машинных наборов - C1 = {2,5}, C2 = {3,4,6}, C3 = {1,7), и соответствующих семейств изделий - F1 = {1,7}, F2 = {3,4,6), F3 = {2,5}.
Таблица 15
Матрица станки/изделие до рекомбинации
| Станки | Изделия | ||||||
Таблица 16
Матрица станки/изделия после рекомбинации
| Станки | Изделия | |||||
ППЯ задача, может быть классифицирована как комбинаторная задача оптимизации, потому что матрица станки/изделия содержит n строк и m столбцов, предлагая n! и m! различных перестановок, соответственно. Большинство методов для ППЯ задачи было разработано на основе методов коэффициентов подобия, методов массивов, методов математического программирования, графо-сетевых методов, или других эвристических подходов. Целью в большинстве этих методов должна быть или минимизация передвижений между группами, или максимизация независимости группы, с учетом таких факторов как, объем выпуска, размер группы, альтернативные производственные планы, или размер машинного времени. Однако, большинство алгоритмов в литературе использует только матрицу инцидентностей станков/изделий, которая подразумевает единственное определенное решение. Относительно немного исследователей рассматривают проблемы использования альтернативных операций, полностью фиксированных альтернативных маршрутизаций, или машинной статической неопределимости в формировании групп и семейств. Эти фиксированные маршрутизации часто оптимизируются скорее с целью максимизации использования станков при их функциональном размещении, чем для использования выгод от групповой организации производства. Большая часть методов, которые включают альтернативные действия и множественные маршруты, использует математическое программирование, что ограничивает их полноценность для решения крупномасштабных проблем. Также, большинство этих методов предполагает, что спрос равен для всех изделий. Однако когда спрос среди изделий различен, что является наиболее вероятным, машинные группы и семейства изделий, сформированные при обратном допущении становятся неэффективными при использовании. Хотя некоторые из этих методов дают хорошие результаты, никакая единственная методика не имеет явного преимущества, чтобы обеспечить лучшее решение в широких областях применения. Эти подходы обычно работают с однокритериальными целевыми функциями и не позволяют изменять оценочные функции или применять выборочное использование ограничений. Также, большинство ППЯ алгоритмов не может идентифицировать все естественно встречающиеся кластеры, также как и не могут давать решения с заранее определенным числом кластеров. Большая часть методов не способна включить другую производственную информацию, типа спроса на изделия, альтернативные операции и избыточное оборудование.
1. Метод коэффициентов подобия. Метод коэффициентов подобия использует коэффициент подобия между каждой парой объектов и некоторого указанного порогового значения, чтобы группировать их в совокупности. Пороговое значение - уровень подобий, на котором два или больше кластера соединены вместе. Пример коэффициента подобия Sij между двумя машинами, i-ой и j-ой, выглядит так:
Sij = Nij/(Ni+Nj-Nij),
где Ni - число изделий, посещающих машину i и Nij – число общих изделий, посещающих машину и i и j.
Мак-Оули (McAuley) [114] был первый, кто использовал односвязный кластерный анализ (single linkage cluster analysis (SLCA)), метод, основанный на коэффициентах подобия, чтобы сформировать группы из наборов станков и семейств деталей. Коэффициент определялся как "число изделий, посещающих обе машины, деленное на число изделий посещающих любую из этих двух машин". Последующие модификации и более продвинутые варианты коэффициентов подобия были предложены Сейфоддини (Seifoddini) и Вульфом (Wolfe) [117], Гаптой (Gupta) и Сейфоддини [106]. Эти методы предлагали иерархии решений, из которых выбиралась лучшая альтернатива.
2. Методы антенны. Методы антенны используют матрицу инцидентностей станки/изделия как вводную и проводят перегруппировку матричных строк и столбцов, пока не сформируют заключительные группы. Мак-Кормик (McCormick) [115] и другие предложили квадратичный метод группировки называемый алгоритмом энергии связи (bond energy algorithm (BEA)). Они определили энергию связи, сумму прочности связи, между любыми двумя смежными элементами в матрице инцидентности. Целью является максимизация энергии связи матрицы, результируемая в блочной диагональной матрице, если решение найдено. Бхат (Bhat) и Хаупт (Haupt) [101] расширили основание этой модели, чтобы улучшить ее вычислительную эффективность. Кинг (King) [110] представляет метод массивов называемый поранговой кластеризацией (rank order clustering (ROC)). Метод описан следующим образом:
Шаг 1. Назначьте двоичные веса на каждую строку и столбец матрицы инцидентности.
Шаг 2. Конвертируйте веса для каждой строки и столбца матрицы к их десятичным эквивалентам.
Шаг 3. Перестройте строки и столбцы поочередно в уменьшающемся порядке величины, пока не появится конечная матрица групп станков/изделий.
При этом полученный результат выглядит в виде похожем диагональную матрицу, отсюда общее название – метод антенны.
Кинг и Накорнче (Nakornchai) [111] предлагают укрупненную модификацию основной модели ROC, чтобы решать большие проблемы. Последующие уточнения ROC были разработаны Ченом (Chan) и Милнером (Milner) [98], Чандразкхараном (Chandrasekharan) и Раджагопэлэном (Rajagopafan) [99], Кьюзиаком (Kusiak) и Чоу (Chow) [112].
3. Методы Математического программирования. Один из лучших, известных методов для проектирования производственных групп - модели математического программирования. Йенсен (Jensen) [101] разработал p-медианную модель динамического программирования. Критерием группировки в этой модели выступает максимизация общей суммы значений подобия для объектов, помещенных вместе в одну группу, при условии, что каждый объект назначен только в одну группу, и с условием, что число групп (p) известно. Кьюзиак (Kusiak) и Херагу (Heragu) снабдили p-медианную модель с помощью целочисленного программирования возможностью проектирования групп и показали важность рассмотрения альтернативных производственных планов [101]. Однако p-медианная модель не позволяет задавать размер группы. Продвинутая p-медианная модель была предложена Сринивасаном (Srinivasan), Нарендраном (Narendran), и Махадеваном (Mahadevan) [118]. Хэм (Ham) и Хэн (Han) [108] предложили целочисленную целевую модель для формирования семейств изделий в классификации и кодировании. Цель модели, которая использует абсолютное расстояние Минковского, состоит в том, чтобы минимизировать эти расстояния лексикографически. Касилингем (Kasilingam) и Лашкари (Lashkari) [101] предложили нелинейную 0-1 модель целочисленного программирования для проектирования производственных ячеек, рассматривающую альтернативные производственные планы. Цель модели состоит в том, чтобы максимизиро