Информатика, вычислительная техника и инженерное образование 2011, №1(3) эволюционное моделирование, генетические и бионические алгоритмы
Скачать 1.19 Mb.
|
Динамически изменяемые эволюционные алгоритмы Применение эволюционных алгоритмов для решения задач с неполной информацией, и в частности задачи синтеза, сталкивается с весьма интересными требованиями к структуре эволюционных алгоритмов: неполнота описаний объекта поиска (в данном случае нечеткая постановка задачи синтеза) приводит к размытости или неопределенности как граничных параметров области поиска, так и генотипа искомого решения. Действительно, при отсутствии четкой или достоверной информации о структуре синтезируемого решения возникает необходимость поиска решений на различных вариациях фенотипического пространства, обладающего различными свойствами и характеристиками структуры. То есть, можно говорить о некотором множестве пересекающихся пространств фенотипов искомого решения, для каждого элемента которого необходимо определить представление (метод кодирования) решений, а также задать правила, согласно которым будет протекать процесс эволюции. Даже если однозначно определить процесс эволюции в рамках некоторого выбранного алгоритма (т.е. условиться, что эволюция протекает для всех индивидуумов одинаково вне зависимости от их представления), то с представлением самих индивидуумов дело обстоит несколько сложнее. Различные фенотипические пространства, получаемые при доопределении множества неизвестных или неточных параметров исходной постановки задачи, приводят к различным представлениям решений на уровне генотипа. То есть, при кодировании будет иметь место наличие множества различных генотипов с различной структурой и длиной, на основе которых необходимо выполнять эволюционный процесс. Изменение структуры генотипа при протекании эволюционного процесса будет оказывать влияние на процесс оценки критерия, усложнять проблематику принятия решений при отборе, вносить изменения в параметры основных генетических операторов (кроссинговера, мутации и др.) для генетических алгоритмов, или приводить к нарушению принципов передачи наследственной информации в вероятностных алгоритмах эволюционного поиска. По сути, возникает необходимость разработки отдельной модификации эволюционного алгоритма для каждого отдельно взятого фенотипического представления искомого решения, т.к. каждое пространство фенотипа содержит набор решений, потенциально являющихся решением поставленной задачи. С другой стороны, логично предложить более “элегантный” выход из сложившейся ситуации: т.к. специфика поставленной задачи в общем и целом известна (она вытекает из общей постановки исходной задачи) и остается неизменной, а меняются лишь некоторые параметры (качественные или количественные), характеризующие или уточняющие поставленную задачу, то необходимо разработать динамически изменяемый эволюционный алгоритм, способный подстраиваться под возникающие изменения структуры фенотипического представления входных данных. Структура динамически изменяемого эволюционного алгоритма остается постоянной, меняются лишь параметры его операторов и, возможно, параметры функционирования алгоритма: величина популяции и элитной области, коэффициенты мутации, рекомбинации, параметры оператора кроссинговера и функции вычисления критерия. Для исключения противоречивости генотипов и структуры эволюционного синтеза возможно выполнение отдельного итерационного процесса для каждого элемента множества пересекающихся пространств фенотипов, когда структура алгоритма будет соответствовать генотипу решений. Изменение фенотипа для эволюционного алгоритма отражается на изменении постановки входной задачи (исходных данных). Необходим морфологический разбор исходной постановки задачи, с помощью которого будут определяться основные параметры функционирования алгоритма: длина и структура хромосомы, метод кодировки и декодировки, параметры генетических операторов и пр. На начальном этапе необходимо охватить как можно большее пространство фенотипов для исследования максимально возможной мощности множества возможных решений, что позволит определить наиболее привлекательные области поиска и исключить тупиковые ветви развития, приводящие к нарушению легальности и законности эволюционирующих решений. Возможно последовательное или параллельное исследование пространства фенотипов, при этом отобранные области поиска могут конкурировать друг с другом в поиске наилучшего (одного или множества) пространства решении. После определения (уточнения) наиболее перспективных областей поиска дальнейший поиск решений выполняется в рамках определенных фенотипических представлений. Поддержка вычислительной нагрузки эволюционных алгоритмов Общеизвестно, что основной сложностью эффективного применения эволюционных алгоритмов является сложность выбора оптимальных параметров при настройке алгоритма. NFL-теорема [22] в частности утверждает, что в среднем, все эволюционные алгоритмы идентичны с точки зрения эффективности и, как показано в [14]: “удачное применение эволюционных алгоритмов для решения той или иной задачи, во многом определяется их удачной настройкой. Строгих правил настройки параметров ЭА и кодирования решений универсальных для всех задач, согласно NFL-теореме, нет и быть не может”. Если учесть, что структура эволюционного алгоритма остается неизменной, а меняются только параметры его настройки, то задачу подборки оптимальных параметров эволюционного алгоритма можно представить в виде задачи параметрического синтеза. Тогда при помощи внешнего алгоритма параметрического синтеза итерационно выполняется последовательный или параллельный синтез параметров эволюционного процесса. В качестве основы алгоритма параметрического синтеза возможно использование различных эволюционных алгоритмов или стратегий что позволит говорить об использовании алгоритмов эволюционного синтеза для настройки параметров динамически изменяемых эволюционных алгоритмов. Так как данный вопрос является слабоизученным, то необходимо исследовать предложенные методы, что позволит с одной стороны повысить эффективность применения эволюционных методов, с другой, рассматривать иерархические структуры организации динамически изменяемых эволюционных алгоритмов, применение которых возможно для проектирования сложных систем. Предложенный подход настройки параметров эволюционных алгоритмов может быть использован для автоматизации процесса поиска оптимальных параметров эволюционных алгоритмов для различного рода задач. В случае рассмотрения предложенных методов создания вложенных иерархических эволюционных алгоритмов для проектирования сложных систем, необходимо уделить дополнительное внимание вопросу быстродействия. Отсутствие необходимого быстродействия при поиске решения и высокая вычислительная нагрузка – одни из основных причин ограничения применения эволюционных алгоритмов. Не секрет, что производительность вычислительных систем растет с каждым годом, и выходом может выступать применение многопроцессорных вычислительных систем, способных значительно ускорить эволюционный процесс. Тем более, что в последнее время широкое распространение в развитии многопроцессорных технологий получила разработка модульных систем с изменяемым количеством процессоров (в которых заказчик может по необходимости установить требуемое количество процессоров), тем самым, подгоняя вычислительные ресурсы под поставленные задачи. В подобных системах основной упор сделан на увеличение производительности при росте вычислительной нагрузки посредством параллельного выполнения задач на наборе процессоров. Однако, как уже было отмечено, производительность многопроцессорных систем растет нелинейно при росте числа процессоров, а в некоторых случаях даже начинает падать. Эффективность распараллеливания зависит от сложности взаимодействия программной и аппаратной частей многопроцессорной вычислительной системы [2]. Под практически каждый пакет анализа, и особенно под каждую область исследований, требуется индивидуальная подборка многопроцессорной вычислительной системы. Даже в случае поиска универсальной системы всегда существует единственное оптимальное решение [23], найти которое современными способами зачастую не представляется возможным в силу высокой сложности систем. Другим недостатком многопроцессорных систем является их высокая стоимость, быстрое моральное устаревание и частая неспособность соответствовать требованиям вычислительной нагрузки, т.к. возникающие в современной науке задачи существенно опережают возможности существующих технических средств, используемых для решения. Вычислительных ресурсов не бывает слишком много, более того, такого определения просто не существует. Именно поэтому применение многопроцессорных вычислительных систем зачастую ограничивается этапами разработки и первоначального тестирования эволюционных алгоритмов на небольших тестовых задачах. Для исследования реальных задач зачастую используются кластеры, но и тут возникают временные ограничения доступа к кластеру, т.к. подобных систем не так много, и время работы и кластером обычно распределяется между несколькими проектами. На первый взгляд кажется, что выход из сложившейся ситуации кроется за переходом от программной реализации эволюционных алгоритмов к их аппаратной интерпретации. Действительно, в некоторой степени это позволяет решить ряд вопросов с быстродействием, повышая скорость работы алгоритмов на 2 или 4 порядка [24,25] и переводя их в область функционирования в рамках реального времени. Но имеющийся у автора опыт разработки систем аппаратной реализации эволюционных алгоритмов [26] или методов повышения их быстродействия [27] приводит к выводу, что простого применения методов перехода от программной реализации медлительных алгоритмов к их прямой аппаратной реализации недостаточно. Дело в том, что подобные решения ограничены в своей применимости рамками тех задач, для которых они разрабатывались. Применение разработанных аппаратных структур для новых методов поиска или доработка под новые предложенные стратегии приводит к необходимости пересмотра существующей архитектуры аппаратно реализованного алгоритма. Зачастую, дешевле и быстрее разработать все заново, нежели пытаться подогнать существующие решения под новые требования. Поэтому необходим поиск более универсальных методов решения вопросов повышения быстродействия эволюционных алгоритмов, в основе которых лежат наиболее удачные примеры существующих решений, а также применение новых методов аппаратного проектирования, позволяющих достаточно просто изменять архитектуру и параметры аппаратного комплекса, иметь возможность многокритериально исследовать и оптимизировать предложенные архитектурные решения и выбирать оптимальные по требуемым параметрам (быстродействие, качество найденного решения, степень использования вычислительных ресурсов и пр.). Другим полезным свойством является возможность оставить часть решения в виде программной реализации, в то время как наиболее ресурсоемкую и статичную (одинаковую для рассматриваемого класса задач) переложить в аппаратную часть инструментального комплекса. Данное свойство позволит использовать разработанные комплексы для множества различных алгоритмов и методов, в которых совпадающие части передаются на реализацию в специализированные аппаратные базовые блоки (предварительно настраиваемые под требуемою конфигурацию), а уникальные части алгоритмов, для которых еще не выработано аппаратных решений в силу их новизны или незначительности вычислительной нагрузки, выполнять традиционными средствами. Это позволит не только повысить быстродействие (а значит расширить область применения) существующих эволюционных алгоритмов, но и проводить исследование совершенного новых алгоритмов, включающих новые стратегии и методы, не заложенные в архитектуру разработанных инструментальных комплексов. Необходимо также иметь возможность добавлять и впоследствии использовать в подобных инструментальных комплексах новые аппаратные решения какого-либо оператора, метода или алгоритма. Очевидно, что необходимость настройки базовых аппаратных блоков под требуемые параметры или конфигурацию реализуемых ими алгоритмов (операторов) приводят к необходимости разработки основных блоков с применением методов реконфигурации аппаратных структур. Реализация описанной функциональности возможна на основе применения методов построения гетерогенных микропроцессорных вычислительных структур, положенных в основу разработки предложенных программно-аппаратных инструментальных комплексов. Эволюционные методы программно-аппаратного разделения Гетерогенные многопроцессорные архитектуры являются де-факто стандартом для встроенных систем проектирования [28]. В таких системах ускорение различных частей приложений обычно выполняется с применением систем цифровой обработки сигналов (используются специализированные процессоры или реконфигурируемые устройства на базе FPGA), объединенных через различные механизмы коммуникации. При разработке встроенных систем, проектировщик должен определить когда (задать расписание) и где (составить соответствия) группы операторов (т.е. задач) и каналов передачи данных (т.е. коммуникаций) должны быть выполнены и задействованы с учетом установленных ограничений и зависимостей, в порядке оптимизации некоторых параметров проектирования, в том числе времени выполнения программы. Основными вопросами при разработке гетерогенных систем являются вопросы программно-аппаратного разделения [7], т.е. определения, какая часть программы будет реализована аппаратно в специализированном микропроцессоре, а какая будет функционировать программно и обрабатываться стандартными методами. Доказано [29], что эффективное распределение заданий между вычислительными ресурсами оказывает большое влияние на характеристики стоимости/производительности системы. Поэтому, при распределении заданий необходимо принимать во внимание системные свойства целевого устройства, а также ограничения, связанные со средой, платформой реализации и/или системными требованиями функциональных возможностей. Гетерогенные системы относятся к классу сложных систем, а задача разделения (включающая планирование и составление соответствий) – сильно зависимая NP-полная задача [30], которая не может быть эффективно решена с помощью точных алгоритмов и эвристических методов, способных находить хорошие решения за приемлемое время. В качестве методов решения подобных задач целесообразно рассматривать эволюционные алгоритмы и алгоритмы инспирированные природными системами. Задачу разделения можно свести к задаче поиска архитектуры и параметров функционирования сложной системы при неполной информации (т.к. в процессе функционирования изменяется архитектурная составляющая системы – часть ресурсов задействуется, часть высвобождается и не все параметры решения задачи могут быть известны на этапе ее постановки). Решение данного типа задач может быть рассмотрено с позиций описанных выше эволюционных алгоритмов структурного и параметрического синтеза при неполной информации. Действительно, т.к. структура системы известна, постановка задачи определена исходными данными (как правило, это текст программы или граф) и неизменна в процессе функционирования, то необходимо определить параметры функционирования системы в рамках заданных ограничений, при которых с одной стороны задействовано минимальное количество ресурсов (а, значит, достигнуто минимальное энергопотребление или имеется возможность параллельного функционирования нескольких процессов), с другой получено максимальное быстродействие при выполнении задачи. При такой постановке задачи нет необходимости искать единственно точное решение, вполне сгодится одно из лучших, удовлетворяющих временным и архитектурным требованиям, поэтому нет ограничений для применения эволюционных методов поиска с этой точки зрения. Задача программно-аппаратного разделения использовалось при проектировании встраиваемых систем с начала 90-х годов, и теперь является широко распространенной методикой оптимизации при проектировании систем. Эта методология проектирования позволяет реализовывать различные синергизмы аппаратных средств и программного обеспечения, которые могут быть получены для встроенных систем. Такие системы обычно встраиваются вокруг основного процессора, который может быть подключен к аппаратным модулям, приспособленным для определенных приложений. Это "приспосабливание" соответствует со-разработке системы и состоит из различных этапов, как определено в [31]: разделения, cо-синтеза, cо-проверки и cо-моделирования. Поскольку эта задача не нова, необходимо рассмотреть методы решения, предложенные в прошлом. Первые работы были представлены в основном “ручными” – неавтоматизированными методиками разделения [32-34]. Среди подходов автоматизированного решения задачи разделения наиболее простой является полный перебор, позволяющий находить точное решение среди заданного множества вариантов. Примерами подобных решений являются работы [34,35]. Точные алгоритмы основаны на определении и оценке всех возможных решений. В теории они позволяют, наверняка, достигнуть всех оптимальных решений. Практически, эти подходы идеальны для простых задач, неактуальных при проектировании современных систем. Их основной недостаток - время выполнения, которое растет экспоненциально с ростом числа системных задач, предназначенных к разделению. Время поиска становится несоизмеримо большим, как только количество анализируемых параметров превосходит 20 [36]. Например, исчерпывающий поиск пространства решения для подобной задачи на двухпроцессорном ПК с частотой в 3 ГГц, при допущении, что время поиска одного решения занимает один тактовый цикл, занял бы более 12 лет. К другим недостаткам существующих методов распределения можно отнести [37] следующие:
- специализированы заданному целевому типу архитектуры и невозможно применение на других платформах. На сегодняшний день, различают два направления в решении задачи разделения: структурно-ориентированные специализированные стратегии, и общая эвристика, которая не является определенной для специфической задачи или структуры. Среди специализированных стратегий, можно выделить работы по синтезу на системном уровне при использовании репрограммируемых элементов и синтез на поведенческом уровне множества процессов для смешанных программно-аппаратных систем [36,38]. Основное преимущество применения определенных подходов состоит в том, что они "приспособлены" для рассматриваемой задачи. Однако применение решений этого типа становятся сложным или невозможным, как только в рассматриваемую задачу вносятся изменения. Методы решений на основе общей эвристики [39-42] не специализированы для решения какого-либо типа задач, и широко используется в других областях исследований при решении NP-полных задач. Преимущество этого типа эвристики состоит в том, что используемая функция оценки критерия может быть легко адоптирована к изменениям в структуре решаемой задачи (т.е. присутствует элемент гибкости, позволяющий расширить область применения алгоритмов), и время поиска решения значительно сокращается в сравнении с полным перебором. Недостатком является отсутствие гарантии, что достигнутое решение – оптимум. Фактически, этот вид алгоритмов часто сходятся к локальному экстремуму, и почти никогда не достигает глобального оптимума. Поэтому разработчики алгоритмов ищут новые и более эффективные алгоритмы, способные повысить качество найденных решений, при снижении времени поиска. Недавние работы в области разделения [43-46] доказывают, что проблема поиска эффективного разделения все еще открыта. При этом работы [46,47] затрагивает проблематику разработки алгоритмов программно-аппаратного разделения для динамически реконфигурируемых систем, что является актуальным направлением. В работе [48] в качестве алгоритма поиска использовались алгоритмы моделирования отжига, в работе [49] использовалась нечеткая логика, генетические алгоритмы представлены в работах [50,51], иерархическая кластеризация [52] или запретный поиск [48] использовались как отдельная эвристика, так и в синергизме с другими перечисленными методиками. Среди успешно продемонстрированных решении методы стохастического поиска [53-55], часто биоинспирированные, которые раскрывают пространство проектирования и используют результаты успешно продемонстрированных предыдущих работ. Тем не менее, представленные методы обычно сфокусированы отдельно на одном из аспектов, и терпят неудачу при попытке получения хороших общих характеристик решений из-за ограниченного пространства проектирования. Общие подходы, новые направления и методы проектирования, способные эффективно генерировать высококачественные решения для сложных приложений на новой стадии развития гетерогенных встраиваемых архитектур, определенно необходимы. Библиографический список 1. Н.Г. Ярушкина. Основы теории нечетких и гибридных систем: Уч. пособие. – М.: Финансы и Статистика, 2004. 2. Р. Шагалиев. HPC. Что нужно сделать? Осознание проблемы. Суперкомпьютеры. – М.: Изд-во СКР-Медиа, 2010, с.– 42-46. 3. В.П. Строгалев., И.О. Толкачева. Имитационное моделирование. – М.: МГТУ им. Баумана, 2008. – С. 697-737. 4. http://www.sarov.net/news2/?id=22880. 5. [i-russia] http://i-russia.ru/computers/articles/354/. 6. И.А. Каляев, И.И. Левин, Е.А. Семерников, В.И. Шмойлов. Руконфигурируемые мельтиконвейерыне вычислительные структуры. – Ростов-на-Дону, ЮНЦ РАН 2009. – 344 c. 7. De Micheli G. and Gupta R., "Hardware/Software Co-design", Proceedings of the IEEE, Vol.85, N°3, 1997. – pp. 349-365. 8. В.В. Гудилов, В.М. Курейчик. Алгоритмы эволюционного синтеза комбинационных схем. – Таганрог: Изд-во ТТИ ЮФУ, 2010. – 160 с. 9. М.Месарович, Д. Мако, И. Такахара. Теория иерархических многоуровневых систем. – М.: Мир, 1973. – 344 с. 10. Е.Н. Князева, С.П. Курдюмов. Законы эволюции и самоорганизации сложных систем. – М.: Наука, 1994. 11. В.П.Корячко, В.М. Курейчик, И.П.Норенков. Теоретические основы САПР. – М.: Энергоатомиздат, 1987. 12. В.М. Курейчик. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. – М.: Радио и связь, 1990. 13. И.П. Норенков, В.Б. Маничев. САПР ЭВА. – М.: Высшая школа, 1983. 14. В.В. Курейчик, С.И. Родзин. О правилах представления решений в эволюционных алгоритмах // Известия ЮФУ. – № 07, 2010. – С. 13-21. 15. В.В. Курейчик. Биоинспирированный поиск с использованием сценарного подхода // Известия ЮФУ. – 2010. – № 7. – С. 7-13. 16. И.М. Соболь. Метод Монте-Карло. – М.: Наука, 1968. – 64 с. 17. Редько В.Г. Эволюция, нейронные сети, интеллект: модели и концепции эволюционной кибернетики. – М.: Комкнига, 2005. 18. О.В. Абрамов. Методы и алгоритмы синтеза стохастических систем // Проблемы управления. – № 4, 2006. – С. 3-8. 19. Pawlak Z. Rough sets present state and further prospects // Intellegent Automation and Soft Computing. – Vol. 2, 1996. – N 2. 20. О.В. Абрамов. Параметрический синтез стохастических систем с учетом требований надежности. – М.: Наука, 1992. 21. М.А. Гайдес. Общая теория систем (системы и системный анализ). – Глобус-Пресс, 2005. – 201 с. 22. Wolpert D.H., Macready W.G. No free lunch theorems for search // Operations research: Santa Fe Institute, 1995. 23. А. Мурашов. Пакеты инженерного анализа для вычислительной гидродинамики // Суперкомпьютеры. СКР-Медиа. – М., 2010. – С. 52-58. 24. A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27-30, 2001. – pp. 624-629. 25. В.В. Гудилов, В.М. Курейчик. Устройство аппаратной реализации вероятностных генетических алгоритмов. Методы и средства обработки информации // Труды второй Всероссийской научной конференции. – М.: Изд-во МГУ им. М. В. Ломоносова. 2005. – С. 596-601. 26. В.В. Гудилов. О построении эволюционных аппаратных средств // AIS’06 CAD-2006 Интеллектуальные САПР, Том 1. – М.: Физматлит, 2005. – С. 7-15. 27. В.В. Гудилов, В.М. Курейчик. Методы повышения эффективности вероятностных алгоритмов // Перспективные информационные технологии и интеллектуальные системы. – Таганрог, 2005. – № 1. – С. 43-55. 28. W. Wolf, The future of multiprocessor systems-on-chips, in Proc. 41 st Assoc. Comput. Machinery//IEEE Design Automat, Cof. (DAC), 2004. – pp. 681-685. 29. Kumar S. Aylor J.H. Johnson B. and Wulf W.A. "The Codesign of Embedded Systems", Kluwer Academic Publishers, 1996. 30. D. Bernstein, M. Rodeh and I Gertner, On the Complexity of Scheduling Problems for Parallel//Pipelined Machines, IEEE Transactions on Computers. Vol. 38 Issue 9, September 1989, no. 9, pp.1308-1313. 31. J. Harkin, T. M. McGinnity, and L. Maguire. Genetic algorithm driven hardware-software partitioning for dynamically reconfigurable embedded systems. Microprocessors and Microsystems, 25(5), 2001.- 263–274. 32. Theissinger, M.; Stravers, P.; Veit, H.; "CASTLE: an interactive environment for HW-SW co-design", Proceedings of the Third International Workshop on Hardware/Software Codesign, GMD, St. Augustin, 1994.- pp.203-209. 33. Ismail, T.B.; Abid, M.; O'Brien, K.; Jerraya, A.; "An approach for hardware-software codesign", Proceedings of the Fifth International Workshop on Rapid System Prototyping, Shortening the Path from Specification to Prototype, 1994.- pp.73-80. 34. Edwards M.D., "A development system for hardware/software cosynthesis using FPGAs", Second IFIP International Workshop on Hw-Sw Codesign, 1993. 35. D'Ambrosio, J.G.; Xiaobo Hu; "Configuration-level hardware/software partitioning for real-time embedded systems", Proceedings of the Third International Workshop on Hardware/Software Codesign, 1994.- pp.34-41. 36. Adams, J.K.; Thomas, D.E.; "Multiple-Process behavioral synthesis for mixed hardware-software systems", in Proc. 8th Int. Symp. On System Synthesis, 1995.- pp.10-15. 37. A. Henni, M. Koudil, K. Benatchba, H. Oumsalem, K. Chaouche. A parallel environment using taboo search and genetic algorithms for solving partitioning problems in codesign, Institut National de formation en Informatique. 38 Kavalade A., Lee E.A.. "The extended partitioning problem: hardware//software mapping and implementation-bin selection", Proceedings of the Sixth International Workshop on Rapid Systems Prototyping, Chapel Hill, NC, June 1995. 39. Gupta R.K., "Co-Synthesis of Hardware and Software for digital embedded systems", Amsterdam: Kluwer, 1995. 40. Jantsch A., Ellervee P., Oberg J., HemmaniI A., Tenbunen H., "Hardware-software partitioning and minimizing memory interface traffic", Proc. of the European Design Automation Conference, Sept. 1994.- pp.226-231. 41 Gajski, D.D.; Narayan, S.; Ramachandran, L.; Vahid, F.; Fung, P.; "System design methodologies: aiming at the 100h design cycle", IEEE Trans. On VLSI Systems, Vol.4, N°1, March 1996.- pp.70-82. 42. Harenstein R., Becker J., Kress R., "Twolevel hardware/software partitioning using CoDe-X", IEEE Symposium and Workshop on Engineering of Computer-Based Systems, March 1996. 43. Chatha K.S., Vemuri R., “MAGELLAN: Multiway Hardware-Software Partitioning and Scheduling for Latency Minimization of Hierarchical Control-Dataflow Task Graphs”, Proceedings of 9th International Symposium on Hardware-Software Codesign (CODES 2001), Copenhagen, Denmark, April 25-27 2001. 44. Bolchin, C., Pomante L., Salice F., Sciuto, D. H/W embedded systems: on-line fault detection in a hardware/software codesign environment: system partitioning // Proceedings of the International Symposium on Systems Synthesis, Vol. 14, September 2001. 45. Dours S D.., "Estimations rapides pour le partitionnement fonctionnel de systemes temps-reelstricts distribues", RENPAR'14, ASF, SYMPA,Hamamet, Tunisie, 10-13 april 2002. 46. Noguera J., Badia R.M., “A hardware/software partitioning algorithm for dynamically reconfigurable architectures”, Proceedings of the International Conference on Design Automation and Test in Europe (DATE’01), March 2001. 47. J. Harkin, T. M. McGinnity, and L. Maguire. Genetic algorithm driven hardware-software partitioning for dynamically reconfigurable embedded systems. Microprocessors and Microsystems, 2001, 25(5): pp. 263-274. 48. P. Eles, K. Kuchcinski, Z. Peng, and A. Doboli. System level hardware/software partioning based on simulated annealing and tabu search. Design Automation for Embedded Systems, 1997 2:5-32. 49. V. Catania, M. Malgeri, and M. Russo. Applying fuzzy logic to codesign partitioning. IEEE Micro, 17(3):pp. 62 70, 1997. 50. R P. Dick and N.K. Jha. MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, October 1998, 17(10): pp. 920-935. 51. V. Srinivasan, S. Radhakrishnan, and R. Vemuri. Hardware/software partitioning with integrated hardware design space exploration. In DATE ’98: Proceedings of the conference on Design, automation and test in Europe, pages. 52. J. Hou and W. Wolf. Process partitioning for distributed embedded systems. In CODES ’96: Proceedings of the 4th International Workshop on Hardware/Software Co-Design, page 70. IEEE Computer Society, 1996. 53. Hidalg, J.I., Lanchares J. Functional partitioning for hardware-software codesign using genetic algorithms. in Proc/ 23rd EUROMICRO Conf, 1997, pp 631-638. 54. T. Wiangtong, P. Cheung and W. Luk, Comparing Three Heuristic Search Methods for Functional Partitioning in Hardware–Software Codesign. Design Automation for Embedded Systems, Volume 6, Number 4, pp. 425-449. 55. P. Eles, Z. Peng, K. Kuchcinski and A. Doboli. System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search, Design Automation for Embedded Systems, Volume 2, Number 1, pp. 5-32. Гудилов Виталий Витальевич. Технический директор, ООО "Инвестиционный консультант", г. Ростов-на-Дону. Е-mail vgudilov@mail.ru. 344000, г. Ростов-на-Дону, ул. Евдокимова 190 Тел.: 89198781600. Gudilov Vitaly Vitaljevich. Technical director (CTO), LTD “Investment consultant”, Rostov-on-Don. E-mail vgudilov@mail.ru. 190 Evdokimova, Rostov-on-Don, 344000, Russia. Phone.: +79198781600. УДК 681.3.001.63 М.А. Наборщиков ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПРОЕКТИРОВАНИЯ СХЕМ РАЗДЕЛЕНИЯ ТРУДА В работе предложен эволюционный метод распределения труда. Общий порядок действий описан в документе "технологическая последовательность". Диспетчирование работ осуществляется исходя из реального состояния ресурсов: материалы, оборудование, люди, время и прочее. Алгоритм апробирован на примерах работы цеха по пошиву мужской и женской защитной одежды. Планирование производственное; процесс технологический; ресурсы; диспетчирование; алгоритм генетический; локус; место рабочее. M.A. Naborschikov Work distribution by means of a genetic algorithm In the paper an evolutional method for the design of work distribution flowcharts is proposed. The general operations procedure is described in the document "technological sequence". Management of works is carried out proceeding from a real condition of resources: materials, the equipment, people, time and other. The algorithm is approved on examples of work of shop on tailoring of man's and female protective clothes. Production planning; manufacturing process; nonrenewable resource; genetic algorithm; locus; work place. В работе предлагается генетический алгоритм, осуществляющий оперативное планирование – диспетчирование работ в зависимости от наличия необходимых ресурсов на момент начала рабочего дня или недели с целью выполнения заказа в заданные сроки и обеспечения загрузки оборудования. Сущность алгоритма раскрывается на примере работы цеха по пошиву мужской и женской защитной одежды (мелкосерийное и крупносерийное производство). Некоторые термины предметной области: Заказ – список комплектов одежды с указанием количества. Модель – это комплект одежды, например, костюм, состоящий из определенного для этой модели перечня изделий. Например, модель М.02-05 (внутрифирменный код модели, утвержден в документе технического описания модели) имеет наименование «Костюм летний мужской для защиты от производственных загрязнений и от вредных биологических факторов». Изделие – элемент костюма, например, куртка, полукомбинезон, брюки. Узел – группа деталей изделия (спинка, подкладка, рукав). Технологическая последовательность – документ, содержащий описание технологического процесса изготовления швейного изделия в технологической последовательности с указанием неделимых операций и соответствующих данных о технологических параметрах каждой операции, средствах оснащения и трудовых нормативах [4]. Этап технологической последовательности – уровень обработки изделия: на начальном этапе выполняются подготовительные операции (например, застрочить верхний срез кармана полочки куртки), затем операции монтажа (например, стачать плечевые срезы спинки и полочки куртки) и заключительные операции (например, очистка готового изделия от производственного мусора и влажно-тепловая обработка). На данном производстве выделяют следующие этапы: 1. Подготовительные операции. 2. Изготовление деталей (обработка отдельных деталей). 3. Изготовление узлов. 4. Монтаж (сборка). 5. Заключительные операции. Технологическая операция – это часть технологического процесса, выполняемая непрерывно на одном рабочем месте, над одним изделием, одним или несколькими рабочими. Это технологически законченный цикл работы, расчленение которого на составные части невозможно (например, стачивание боковых срезов) или нецелесообразно (например, втачивание левого и правого рукавов в проймы) вследствие технологической связанности. Рабочее место (РМ) – это неделимое в организационном отношении (в данных конкретных условиях) звено производственного процесса, обслуживаемое одним или несколькими рабочими, предназначенное для выполнения одной или нескольких производственных или обслуживающих операций, оснащенное соответствующим оборудованием и технологической оснасткой. Организационная операция – группа технологических операций, выполняемых одним исполнителем на одном рабочем месте. Как правило, одно изделие исполняется на одном РМ, если заказ большой, то на нескольких. Если организационная операция по длительности превышает одну смену, то образуется остаток, переходящий на другой день. Технологическая схема разделения труда – описание организационных технологических операций, включая контроль и перемещение по всем видам работ, выполняемых на одном технологическом процессе в технологической последовательности с указанием данных о средствах оснащения и трудовых нормативах. Производственное задание – список комплектов одежды с указанием количества, направленных на обработку в цех. Задание может быть сформировано на определенный период времени (рабочая смена, неделя, декада, месяц) или рассчитано для выполнения всего заказа. Такт потока (конвейера) промежуток времени, через который производится запуск каждого нового комплекта кроя или выпуск каждой последующей единицы готовой продукции. Такт потока может быть определен по-разному в зависимости от способа задания мощности потока, т.е. в зависимости от заданного выпуска изделий в смену Мсм или заданного количества рабочих в потоке N. Если такт потока вычисляется как Т =  ,то получим организационную операцию, равную сменно-суточному заданию. Если такт потока Т =  ,то организационные операции будут формироваться так, чтобы все работы с изделием заканчивались в одно время [5]. Исходная информация генетического алгоритма: Популяция – множество вариантов оперативного плана. Особь (хромосома) – оперативный план. Ген – цепочка технологических операций, которые нельзя переставить местами. Длина цепочки l 1. Цепочки последовательных технологических операций выделяет технолог. Если точнее, то и технолог, и мастер, и швея знают, что нельзя, например, вначале обметать петли, а потом разметить их местоположение. Локус – рабочее место (РМ), на котором выполняется цепочка технологических операций. Локус РМ вмещает несколько генов. На участке пошива имеется множество РМ, на которых могут выполняться одинаковые функции, хотя и с различными показателями. Имеется справочник по взаимозаменяемому оборудованию. Локусы рабочих мест частично упорядочены в соответствии с вышеуказанными этапами технологического процесса. Аллель (локус, где ген занимает устойчивое состояние) – такое РМ, откуда ген (цепочку) перемещать не желательно. Организационная операция – несколько цепочек технологических операций по одному изделию на одном РМ. Представляет собой блок из нескольких генов, сформированный так, что длительность организационной операции равна или кратна такту потока. На рис. 1 показан код строки хромосомы, где gi – ген (неделимая цепочка технологических операций); РМj – локус (рабочее место, на котором выполняются технологические операции). 'свободные' гены 
 РМ1 РМJ РМm Рис. 1. Код строки хромосомы. В первых популяциях оперативные планы могут содержать «свободные» гены – такие технологические операции, которые не нашли своего места из-за нерационального распределения по рабочим местам. На рис. 2 изображен код i-того гена.
Рис. 2. Представление подстроки гена. A – номер рабочего места; G –длина цепочки; B – номер заказа; H –номер организационной операции; C – номер модели; I – время начала операции; D – номер изделия; J – длительность операции; E – номер узла; K – качество исполнения F – номер цепочки; организационной операции; L – этап технологического процесса. Ген переходит на другое рабочее место, меняя параметр качества и инициируя новую (под) цепочку, которая может притягивать «родственные» гены из той же технологической последовательности. Мутация – это случайный выбор генов и перестановка местами с соседними в пределах хромосомы. Оператор мутации Случайным образом выбирается ген цепочки технологических операций и меняется местами с геном на ближайшем РМ, совместимом по оборудованию. При этом проверяется возможность перестановки по длительности такта потока. Задается вероятность выполнения оператора мутации. В первую очередь мутируют гены длиной 1, потом 2 и т.д. Оператор скрещивания Скрещивание осуществляется между парой родительских хромосом так, что потомку передаются блоки из генов, по длительности равные такту потока, т.е. скрещивание многоточечное, при котором потомку передаются заполненные локусы – загруженные рабочие места. Задачей программы является формирование такого плана распределения всех заданных работ, в котором суммарное отклонение длительностей организационных операций (производственных заданий) от такта потока было минимальным:  , (1)где Tj – отклонение j-ой организационной операции от такта потока. Укрупненный алгоритм 1. Классификация действий по признаку взаимозаменяемости с целью ограничить генетический поиск в пределах классов действий. 2. Формирование множества генов технологических операций и вычисление их параметров для каждого возможного РМ. 3. Формирование начальной популяции, состоящей из единственной особи в виде строки из таких генов, которые в совокупности образуют некий вариант схемы распределения труда, обеспечивающей выполнение заказа при имеющихся ресурсах. Для этого множество генов разбивается на подмножества генов, принадлежащих одной технологической последовательности, изделию, этапу. Внутри подмножеств осуществляется сортировка по времени, качеству и другим критериям. 4. Пока не выполнено условие останова алгоритма, т.е. результат формулы (1) перестанет увеличиваться, выполнять генетический поиск, иначе перейти к пункту 12. 5. Мутация. 6. Отбор из текущего поколения двух особей, обладающих одинаковыми признаками (этапом технологической последовательности, типом оборудования, оборудованием) с наиболее высокой приспособленностью. 7. Скрещивание. 8. Вычислить значение функции приспособленности потомков. Создать аллель в случае, когда потомок удовлетворяет условию:  где Tj – отклонение от такта потока j-ой организационной операции. 9. Поместить потомков в новое поколение. 10. Редукция – сокращение наименее приспособленных особей по количеству «свободных» (не распределенных) генов технологических операций. 11.Возврат к пункту 4. 12. Вывод результата работы на экран. Пример работы программы Требуется с помощью генетического алгоритма распределить работы для заказа, состоящего из 100 зимних курток модели М.02-20. На рис. 3 показаны результаты работы программы.  Рис. 3. Фрагмент итоговой схемы разделения труда Количество исполнителей на швейном участке 30 человек. Время, затрачиваемое на изготовление одного изделия – 14664,8 сек. Технологический процесс состоит из 202 технологических операций. Допустимое отклонение от такта потока 15%. Такт потока – 488,83 ± 73,32 сек. Количество итераций – 231. Расчетное время выполнения заказа – 51 рабочая смена. Всего организационных операций – 36. Выпуск в смену – 59 шт. В полученной схеме разделения труда присутствуют организационные операции с трудоемкостью менее 1. Это часто происходит на специфичном оборудовании. Например, орг. операция № 35 включает одну технологическую операцию (рисунок 3) «Наметить месторасположение петли на пластроне, на поясе, обметать 2 петли». Технолог указал на нее оборудование JUKI-782, которое нигде больше не встречается. Заключение Таким образом: 1. Сформирована схема разделения труда исходя из реального состояния (наличия), а также с учетом особенностей трудовых ресурсов. Благодаря такому подходу естественным образом выявляется нехватка или излишек ресурсов, что позволяет оперативно корректировать планы поставок. 2. Код хромосомы – варианта оперативного плана состоит из генов, отображающих последовательные операции, выполняемые на одном рабочем месте. Соответственно построены операторы скрещивания и мутации. 3. Локусом является рабочее место и в нем может разместиться несколько генов неделимых технологических операций. Библиографический список
Наборщиков Михаил Александрович ГОУ ВПО "Ижевский государственный технический университет" в г. Ижевске. E-mail: kuchuganov@istu.ru. 426034, УР, г. Ижевск, ул. Студенческая, д. 7. Тел.: 8(3412)588-910. Кафедра "Автоматизированные системы обработки информации и управления"; аспирант. Naborschikov Mikhail Alexandrovich State Educational Institution of Higher Professional Education “Izhevsk State Technical University”, Izhevsk. E-mail: kuchuganov@istu.ru 7 Studencheskaya Street, Izhevsk, Udmurt Republic, 426034 Russia. Phone: 8(3412)588-910. Automated Information Processing and Control Systems Department; post-graduate student. |
Похожие:
 | В настоящем выпуске размещены работы по проблемам филологии, педагогики и методике обучения иностранным языкам, а в следующем выпуске... |  | Учебное пособие предназначено для студентов вузов, обучающихся по направлениям подготовки Информатика и вычислительная техника; Прикладная... |
| Б90 Использование субд для создания программных систем и их компонентов: Методические указания к практическим занятиям для студентов... | | «Информатика и вычислительная техника» 2 курс (заочное обучение, платные места) |
| ... | | Методические указания по выполнению междисциплинарной курсовой работы студентами образовательной программы «Информатика и вычислительная... |
| Правильный ответ помечается знаком × в бланке ответов. Исправления в бланке ответов не допускаются | | Федерального государственного образовательного стандарта по специальности среднего профессионального образования, входящей в состав... |
| Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования | | Федеральное государственное автономное образовательное учреждение высшего профессионального образования «национальный исследовательский... |