автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Генетические методы структурного синтеза проектных решений

ООЗ1776Б6

На правах рукописи

Арутюнян Нарек Микаелович

ГЕНЕТИЧЕСКИЕ МЕТОДЫ СТРУКТУРНОГО СИНТЕЗА ПРОЕКТНЫХ РЕШЕНИЙ

Специальность 05 13 12 - Системы автоматизации проектирования

Автореферат диссертации на соискание ученой степени кандидата технических наук

2 7 ДЕК 2007

МОСКВА-2007 г

003177666

Работа выполнена в Московском государственном техническом университете им НЭ Баумана

Научный руководитель: доктор технических наук, профессор

Норенков Игорь Петрович

Официальные оппоненты:

доктор технических наук Власов Сергей Евгеньевич,

кандидат технических наук, доцент Тарасов Валерий Борисович

Ведущее предприятие:

Институт конструкторско-технологической информатики РАН

Защита состоится 17 января 2008 года в 1630 на заседании диссертационного совета Д 212 141 10 в Московском государственном техническом университете им. Н Э Баумана по адресу 105005, г Москва, 2-я Бауманская ул , д 5

Отзыв на автореферат, заверенный печатью организации, просим присылать по адресу 105005, г Москва, 2-я Бауманская ул, д 5

С диссертацией можно ознакомиться в библиотеке МГТУ им Н Э Баумана.

Автореферат диссертации разослан «•/ » декабря 2007 г

Ученый секретарь

диссертационного совета к т н , доц ¿7/C, Р Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Перспективным направлением решения этой проблемы является разработка и применение генетических алгоритмов (ГА) Генетические алгоритмы, наряду с методами локальной оптимизации (Яг// Climbing) и моделирования отжига (Simulated Annealing), нейронными сетями {Neural Network), поиском с запретами (Tabu Search), входят в группу стохастических методов Основные преимущества ГА следующие 1) применимы к задачам как с числовыми, так и предметными переменными, т е позволяют осуществлять поиск в неметризуемых пространствах параметров, 2) адаптируются и «обучаются» в течение своего исполнения, 3) имеют параллельность внутренних процессов Имеются примеры применения ГА к решению задач синтеза расписаний, планирования работ и распределения ресурсов, синтеза топологии сетей различного назначения, маршрутизации транспортных средств, компоновки и размещения оборудования и др

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

Генетические алгоритмы были предложены в 1975 г профессором Джоном Холландом в Мичиганском университете Они получили широкое распространение благодаря профессору университета штата Иллинойс Дэйвиду Гольдбергу и его студентам В дальнейшем генетические алгоритмы получили развитие в трудах Э Гудмана, К ДеДжонга, JI Дэйвиса, Д Фогелья и многих других Значительный вклад в развитие теории эволюционного моделирования и стохастической оптимизации внесли Батищев Д И,

Букатова И JI, Курейчик В В , Курейчик В М , Мухачева А С , Норенков И П , Растригин JIА и др

Для повышения эффективности ГА в работах этих и других исследователей разработана совокупность алгоритмов выполнения генетических операторов, однако выделить среди них наилучшие для любых задач не представляется возможным То же следует отметить в отношении генетического метода комбинирования эвристик (НСМ - Heuristics Combination Method), в котором априорное задание вероятностей выбора эвристик не всегда оказывается удачным Ресурсом, использование которого может существенно повысить эффективность генетического ГА, является автоматический выбор типов генетических операторов и других параметров алгоритмов во время генетического поиска

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

Для достижения поставленной цели необходимо решение следующих основных задач

1 Анализ существующих подходов к решению задач структурного синтеза в проектировании и логистике

2 Определение параметров, управление которыми позволяет повысить эффективность ГА

3 Разработка новых генетических методов структурного синтеза проектных решений

4 Экспериментальная оценка эффективности разработанных методов

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

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

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

Реализация и внедрение результатов работы. Результаты диссертационной работы внедрены в ЗАО «СИНОПСИС АРМЕНИЯ», в КБ ИГ АС «Волна» (г Москва) и в учебный процесс МГТУ им Н Э Баумана

Апробация работы. Основные результаты диссертационной работы были доложены на IX Молодежной научно-технической конференции «Наукоемкие технологии и интеллектуальные системы - 2007» (ИУ-4,МГТУ им Н Э Баумана, М 2007), IV Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Россия, Коломна, 2007) и на других научно-технических и научно-практических конференциях

Публикации по работе. По материалам диссертационных исследований опубликовано 4 печатных работ

Структура и объем работы. Диссертация включает введение, четыре главы с выводами, заключение, список литературы из 71 наименований и приложения Работа изложена на 119 страницах машинописного текста, содержит 50 рисунков и 6 таблиц

СОДЕРЖАНИЕ РАБОТЫ Во введении показана актуальность темы исследования, сформулированы цель и задачи настоящей работы, отмечены ее научная новизна и практическая ценность

В первой главе исследованы проблемы структурного синтеза в проектировании и логистике В САПР используют две группы методов для решения задач структурного синтеза - экспертные методы и методы дискретной оптимизации Использование экспертных систем не получило широкого распространения в силу трудностей создания баз знаний для представительных классов проектируемых объектов В большинстве случаев задачи структурного синтеза стараются свести к задачам дискретного математического программирования

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

Анализу подвергнуты эволюционные методы базовый генетический алгоритм, метод «поведения толпы» и метод «колонии муравьев» Среди методов дискретного математического программирования для решения сложных задач автоматизированного проектирования и логистической поддержки наиболее перспективны генетические методы эволюционных вычислений в силу применимости к задачам как с числовыми, так и

предметными переменными Однако базовый генетический алгоритм при решении задач проектирования и логистики часто оказывается неэффективным

Базовый ГА в ряде случаев требует заметных затрат машинного времени Но главный его недостаток - опасность преждевременного вырождения популяции хромосом, выражающегося в потере разнообразия генного материала Это вырождение называют стагнацией Стагнация может наступить вдали от экстремальной точки, что означает низкую точность получаемых решений К сожалению, в реальных задачах отсутствуют сведения об экстремальном значении целевой функции, поэтому пользователь принимает полученный результат за оптимальный, хотя возможности дальнейшего улучшения решения далеко не исчерпаны Поэтому главная цель развития ГА, которая поставлена в данной диссертации, заключается в разработке новых генетических методов, обеспечивающих получение решений с повышенной точностью Теорема шаблонов утверждает, что

ДН, Ш) = К{Н, О A Fjn)/F0, (1)

где К(Н, () - число экземпляров схемы Н в поколении с номером t, Fav(H) - усредненная полезность экземпляров со схемой Н, Fo — усредненная полезность всех экземпляров популяции, ps~ 1 —d(l\)l(n-\) - вероятность выживания схемы Н (вероятность, с которой при простом одноточечном кроссовере в хромосому потомка попадет схема), п — длина хромосомы (число генов в хромосоме)

Следовательно, число схем из хромосом перспективных родителей (Fav(H) > Fq), имеющих лучшие значения функции полезности, увеличивается в генотипах популяции от поколения к поколению по показательному закону, пока не наступит стагнация, при которой Fav(H) = F0 Скорость роста ЛТ(Н, t) тем выше, чем больше Fav(H) и чем меньше длина ¿/(Н) и порядок и(Н) схемы Н Отметим, что в (1) кроссовер рассматривается как фактор, разрушающий шаблоны, и не учитывается возможность формирования в хромосомах потомков шаблонов, отсутствовавших в хромосомах родителей

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

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

Вторая основная тестовая задача отражает особенности задач пространственно-временного синтеза Это задача синтеза расписаний, имеющая англоязычное наименование JSSP (Job Shop Scheduling Problem)

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

Сформулированы цель работы и задачи, необходимые для достижения поставленной цели

Во второй главе рассмотрены разновидности генетических операторов В практических алгоритмах существует и используется большое число вариантов реализации генетических операторов Эффективность применения того или иного варианта зависит от характера задачи и часто от ситуации, складывающейся во время решения задачи Следовательно, априорный выбор вариантов случайным образом влияет на эффективность поиска и одним из направлений повышения эффективности ГА является разработка адаптивных генетических методов

Основные генетические операторы - селекция, кроссовер, мутация К селекции обычно относят как выбор родительских хромосом для выполнения кроссовера и/или мутации, так и отбор хромосом после кроссовера и мутации с целью формирования нового поколения (рис 1)

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

Рис 1,6 соответствует известному алгоритму Steady State, в котором результаты кроссовера (и/или мутации) сразу замещают худшие особи в текущем поколении

Рис 1,в представляет вариант турнирного отбора, в котором родители выбираются из предварительно сформированной репродукционной группы

В)

Рис 1 Варианты селекции

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

В варианте турнирного отбора рис 1,г в репродукционную группу включают всех потомков и всех родителей После выполнения g актов кроссовера в группе оказывается 4g членов Среди них для включения в новое поколение отбирается Л^ор лучших хромосом

Кроссовер - генетический оператор, в значительной мере влияющий на эффективность поиска Самым простым методом скрещивания является одноточечный кроссовер (рис 2)

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

Родители

Дети

1 1 ( 0 0 0 1

1 0 с 0 10 0

/

Точка разрыва

Кроссовер

1 1 с 0 10 0

1 0 с 0 0 0 1

Рис 2 Кроссовер одноточечный

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

В третьей главе рассмотрены предлагаемые в диссертации новые генетические методы — смешанный эволюционный метод, метагенетический метод и циклический генетический метод (ЦГМ) Смешанный эволюционный метод основан на использовании многоточечного кроссовера и селекции с участием нескольких родительских хромосом Предпочтительность многоточечного кроссовера доказана благодаря учету при выводе теоремы

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

Смешанный эволюционный метод (ММЕМ - Mixed Mode Evolution Method) является генетическим методом, характеризующимся следующими двумя свойствами: 1) многоточечный кроссовер; 2) полигамность, т.е. хромосома каждого потомка формируется из хромосом более двух или более родителей. Эффективность ММЕМ заключается в лучшем приближении к экстремуму по сравнению с обычными генетическими методами, т.е. в большей точности результатов оптимизации.

Специфика ММЕМ отражена главным образом в блоке формирования хромосом для следующего поколения. В зависимости от значений длины фрагментов, на которые разделяются родительские хромосомы, параметра у, указывающего наличие или отсутствие кроссовера внутри фрагментов (у € {да, нет}) и числа хромосом-родителей у каждой формируемой хромосомы возможны различные варианты процедуры формирования хромосом-потомков, представленные на рис.3 и рис.4.

А В Л В А В

I и I I I И I I I И I И M I I I I I I I И 1 I "ТТЛ

Фрагменты

Рис.3. Структура хромосомы в первом варианте формирования потомка

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

А В А В А В А В В А В

'II ил

11 lililí + lililí II 1

/

Точки разрыва хромосом

Рис.4. Структура хромосомы во втором варианте формирования потомка

Вариант 2 с длиной L, равной длине всей хромосомы, соответствует одноточечному генетическому алгоритму. Тот же вариант, но при L= 1, близок к GA с однородным кроссовером. Методу ACO соответствует вариант 3 при L= 1. Метод PSO имеет место, если L= 1, а в качестве родителей при формировании j-го потомка преимущественно используются две хромосомы: глобально рекордная (с лучшим значением целевой функции среди всех хромосом популяции) и локально рекордная (с лучшим значением целевой функции средиу'-х членов всех предыдущих поколений).

Теорема схем учитывает наследование схем и их возможное разрушение при кроссовере и мутациях, но не учитывает процессы появления новых схем Для учета процессов как разрушения, так и генерации схем необходимо дополнить выражение (1) для АЩ, ЯТ) слагаемым, учитывающим вероятность синтеза новых схем В результате Npop актов кроссовера, происходящего с вероятностью Рс, имеем увеличение числа схем по сравнению с результатом, вытекающим из теоремы схем, на величину

NvopPCPaPb/L (2)

Очевидно, что полученный результат для двухпозиционных схем справедлив и для многопозиционных схем, если под А и В понимать схемы, находящиеся по разные стороны от линии разрыва хромосом и длины которых не превосходят L При этом вероятность рА может быть определена как K(A)Fm(A)/Fo, аналогично определяются рв и рАц Скорректированное с учетом (2) выражение теоремы схем (1) принимает вид

^(Ндв,/+1 )= {А"(Ндв,0( 1 -PJL)Fav(H)/Fo+NfopPcрьръ/L)(1 - м(Ндв)Рм) (3)

Выражение (3) свидетельствует о немонотонном влиянии числа разрывов родительских хромосом (или длины фрагментов L) на эффективность алгоритма Следовательно, имеется некоторый оптимальный диапазон значений L Этот результат положен в основу разработанного смешанного эволюционного метода, сокращенно обозначаемого ММЕМ (Mixed Mode Evolution Method)

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

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

2 Отсутствие априорной информации о предпочтительных значениях параметров не является критичным, так как алгоритм самостоятельно определяет параметры генетического алгоритма

3 Адаптация происходит к особенностям этапа поиска На разных этапах генетического поиска те или иные операторы могут быть эффективными в различной степени Например, в период стагнации намного предпочтительнее случайные операторы выборки и кроссовера, так как они

могут вывести алгоритм из состояния стагнации А на ранних этапах поиска эффективнее такие операторы селекции, как метод рулетки, и т п Ниже приведен псевдокод данного алгоритма

META-GENETIC ALGORITHM begin

create initial population Pi, create initial population P2, do{

for l = 1 to n {

select parenti and parents from P2, offspring = crossover(parenti, parentî) mutation(offspring)

of f springflt„ess = SIMPLE_STEP (of f spring) replace (P2, of f spring) ,

}

}

GENETIC ALGORITHM STEP(select configuration from P2) } until stopping condition //report the best answer; end.

GENETIC ALGORITHM STEP( config ) begin

for 1 = 1 to n {

config-*select parenti and parent2 from population Pi, offspring = config-crossover(parenti, parent2> config-^mutation (of f spring) if suited(offspnng) then

replace(Pi, offspring),

}

end

Рассматриваются два множества хромосом В генах хромосом первого множества (Pi) хранятся номера эвристик для выполнения очередного шага синтеза решения Вторая популяция (Р2) состоит из хромосом, в генах которого хранятся конфигурационные параметры для основного генетического алгоритма При формировании исходной популяции аллели всех хромосом выбираются случайным образом

После очередной генерации метагенетического алгоритма с помощью метода турнирной селекции из популяции Р2 выбирается хромосома и с данной конфигурацией формируется очередное поколение с помощью основного генетического алгоритма Как видно на графике (рис 5), данный подход выбора конфигурации намного эффективнее, чем просто выбор наилучшего решения из популяции Р2 Это объяснятся тем, что «плохая» конфигурация, которая на ранних этапах была наилучшей в популяции, может привести к стагнации

4000

US

о

2300

2600

60

120

180

(омер популяции

— TS RS — RWS US

Рис.5. Результаты сравнительной оценки эффективности различных методов выбора конфигурации из популяции Рг для популяции Рг

Метагенетический алгоритм использует Simple Genetic Algorithm (Simple GA), где реализован принцип всеобщего изменения.

Чтобы объяснить применение непересекающихся популяций, рассмотрим кривую схождения к наилучшему решению генетических алгоритмов (рис.6).

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

Оценка

->

Время работы Рис.6. Кривая конвергенции GA

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

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

В четвертой главе проведена экспериментальная оценка эффективности новых генетических методов

Для экспериментальной оценки эффективности новых генетических алгоритмов использован пакет программ GAlib, который является динамически подключаемой библиотекой Данная библиотека разработана Массачусетсом Технологическим Институтом (MIT) и свободно распространяется под лицензией GNU Библиотека содержит набор базовых функций для работы с генетическими структурами кроссовер, мутации, сравнения На основе данной библиотеки были реализованы новые генетические методы и операторы

Было принято следующее лаконичное обозначение методов

имя метода — число точек разрыва хромосом при кроссовере (число родителей) Если именем одноточечного базового ГА является CGA (Classic Genetic Algorithm), то его обозначение будет CGA-1(2) В смешанном эволюционном методе фигурируют m точек разрыва (multipoint crossover) и m родителей (multi parents), поэтому ММЕМ будет обозначаться CGA-т(т), если гены непосредственно являются искомыми параметрами задачи, или НСМ-т(т), если гены обозначают номера эвристик для расчета искомых параметров

На рис 8 представлены результаты решения задачи синтеза многостадийных расписаний с 4 стадиями, 200 работами и 15 машинами с помощью метода HCM-m(m) Точки соответствуют отдельным вариантам решения, кривая отображает усредненную зависимость целевой функции от размера фрагмента L Из выражения (3) очевидно что длина фрагментов L немонотонно влияет на эффективность генетического поиска, что подтверждает справедливость (3) Параметр L может рассматриваться как конфигурационный параметр для метагенетического алгоритма

FCS.')

/

г

"Г *

•

Рис.8. Зависимость результатов решения задачи синтеза расписаний от длины фрагментов Ь

Аналогичные результаты были получены при решении других тестовых задач - задачи маршрутизации транспортных средств с временными окнами и задачи синтеза топологии и распределения трафика в вычислительной сети с хромосомами длиной в 276 генов. В обоих случаях использовался метод НСМ-т(т).

Результаты решения задачи компоновки с помощью метода CGA-т(т) представлены в виде точек на графике рис.9. Отдельные точки графика отображают значения максимизируемой функции полезности F(X), полученные после 2000 смен поколений (около 100000 обращений к процедуре расчета функции полезности) при разных значениях длин фрагментов. Показанная на рисунке кривая - сглаженная зависимость усредненных значений F(X) от log2L. Крайние правые точки соответствует одноточечному кроссоверу, крайние левые точки - однородному кроссоверу. Как и в предыдущих примерах, одноточечный кроссовер оказывается малоэффективным.

г«)

1650 1600 1550

ism

1450 14ß0 1350

! 3 i 1 5 S 7 я log, L

Рис.9. Зависимость результатов компоновки от длины фрагментов L

Для исследования эффективности метагенетического алгоритма использовалась следующая методика: было произведено несколько расчетов с одинаковыми исходными данными, и из результатов было выбрано лучшее и худшее значения. Эти значения отличаются, как правило, не более чем на 12%. Расчеты проводились при размере популяции А^р = 200, так как дальнейшее увеличение Npop не приводит к значительному улучшению

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

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

1. Результат лучше по сравнению с обычными генетическими алгоритмами в среднем на 7-10%.

2. Намного раньше входит в фазу стагнации, по сравнению с обычным генетическим алгоритмом.

В качестве еще одной тестовой задачи для метагенетического алгоритма была принята задача размещения разногабаритных элементов. В качестве тестовой задачи была рассмотрена GSRC(nlOO). Кривая схождения к наилучшему решению для данной задачи приведена на рис. 11. Результаты однозначно показали применение метагенетического алгоритма повышает эффективность генетического поиска.

13800

12600

- ис — ТРС ОРС — ACO — MetGA — ММЕМ Числ° °"""ок ,„„„

целевой функции х1000

Рис.10. Кривая схождения к наилучшему peineHHio(JSSP)

Рис.11. Кривая схождения к наилучшему решению (размещения)

Для исследования эффективности ЦГМ были выполнены эксперименты с тестовой задачей синтеза расписаний со следующими исходными данными: число работ 105, число стадий 4, число машин на стадиях {4, 4, 4, 3}. На рис.11 представлены результаты расчетов - зависимости целевой функции ДХ) от номера поколения при применении смешанного эволюционного метода НСМ-т(т) и ЦГМ с макромутациями через 120 поколений. Как видно на рис.11, на первых четырех циклах происходило улучшение целевой функции. Причем стагнация в случае НСМ-т(т) наступила на уровне ,Р(Х)=21751, а в случае ЦГМ на втором, третьем и четвертом циклах достигнуты значения ^(Х) 21734, 21716 и 21676.

ЦОЛЫЯЯ фл-ххвяя

Рис.11. Результаты решения задачи синтеза расписаний Полученные результаты позволили сделать ряд выводов. На классе рассмотренных задач: 14

Во-первых, однородный и одноточечный кроссоверы не относятся к лучшим вариантам ГА Смешанный генетический метод с многими родителями превосходит по эффективности классический ГА, в котором при кроссовере происходит скрещивание генов только двух родителей

Во-вторых, подтверждено, что метод комбинирования эвристик превосходит по эффективности генетический метод с обычным кодированием хромосом

В-третьих, показано, что эффективность разработанного метагенетического алгоритма, в котором автоматически настраиваются параметры алгоритма и выбираются вероятности применения эвристик, превосходит эффективность неадаптивных методов

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Главным научным результатом работы является разработка и обоснование эффективности новых генетических методов структурного синтеза и дискретной оптимизации для систем автоматизированного проектирования и логистической поддержки

Основные научные теоретические и практические результаты работы состоят в следующем

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

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

3 Разработан смешанный эволюционный метод, основанный на использовании многоточечного кроссовера и селекции с участием нескольких родительских хромосом

4 Автоматический выбор значений параметров и типов генетических операторов в процессе генетического поиска реализован в метагенетическом алгоритме Как и для определения значений управляемых параметров исходной оптимизационной задачи, для выбора значений параметров и типов операторов использованы генетические алгоритмы К числу адаптируемых параметров в разработанном алгоритме также относятся длина фрагмента Ь для смешанного эволюционного метода, а также глубина и частота применения макромутаций в циклическом генетическом методе

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

6 Экспериментальная оценка эффективности новых генетических методов — смешанного эволюционного метода и метода комбинирования эвристик — показала, что однородный и одноточечный кроссоверы не относятся к лучшим вариантам ГА При этом метод комбинирования эвристик НСМ-ти(от) превосходит по эффективности метод ССЛ-т(т) с обычным кодированием хромосом Смешанный генетический метод НСМ-т{т) с многими родителями превосходит по эффективности метод НСМ-т{2), в котором при кроссовере происходит скрещивание генов только двух родителей

Результаты диссертационной работы внедрены в ЗАО «СИНОПСИС АРМЕНИЯ», в КБ ИГ АС «Волна» (г Москва) и в учебный процесс МГТУ им Н Э Баумана

Основные положения диссертации опубликованы в следующих работах

1 Норенков И П , Арутюнян Н М Состояние проблемы структурного синтеза в проектировании и логистике //Наука и образование Инженерное образование Электронный журнал - 2007 - № 9

2 Норенков И П, Арутюнян Н М Метагенетический алгоритм оптимизации и структурного синтеза //Информационные технологии - 2007 - № 3 -С 10-13

3 Норенков И П, Арутюнян Н М Смешанный эволюционный метод //Информационныетехнологии -2007 -№1 -С 17-20

4 Норенков И П , Арутюнян Н М , Бондаренко А А , Сравнительный анализ эффективности эволюционных методов на примере задачи синтеза расписаний //Информационныетехнологии - 2006 -№5 —С 6-11

Подписано к печати 10 12 07 Заказ № 909 Объем 1,0 печ л Тираж 100 экз Типография МГТУ им Н Э Баумана 105005, Москва, 2-я Бауманская ул , д 5 263-62-01

ВВЕДЕНИЕ.

ГЛАВА 1. СОСТОЯНИЕ ПРОБЛЕМЫ СТРУКТУРНОГО СИНТЕЗА В

ПРОЕКТИРОВАНИИ И ЛОГИСТИКЕ.

1.1. Задачи структурного синтеза проектных решений.

1.1.1. Задачи пространственного синтеза.

1.1.2. Задачи пространственно-временного синтеза.

1.2. Подходы к решению задач структурного синтеза проектных решений

1.2.1. Интеллектуальные системы и методы структурного синтеза.

1.2.2. Методы дискретного математического программирования.

1.3. Эволюционные методы.

1.3.1. Базовый генетический алгоритм.

1.3.2. Метод «поведения толпы».

1.3.3. Метод «колонии муравьев».

1.4. Тестовые задачи.

Выводы.

ГЛАВА 2. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ.

2.1. Разновидности генетических операторов.

2.2. Многоточечный и однородный кроссовер.

2.3. Параллельные и гибридные генетические методы.

2.4. Метод комбинирования эвристик.

Выводы.

ГЛАВА 3. НОВЫЕ ГЕНЕТИЧЕСКИЕ МЕТОДЫ.

3.1. Смешанный эволюционный метод.

3.1.1. Обоснование предпочтительности многоточечного кроссовера.

3.1.2. Варианты смешанного эволюционного метода.

3.2. Метагенетический метод.

3.3. Циклический генетический метод.

Выводы.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ЭФФЕКТИВНОСТИ

НОВЫХ ГЕНЕТИЧЕСКИХ МЕТОДОВ.

Программное обеспечение генетического поиска.

4.2. Многоточечность и полигамность.

4.2.1. Оценка эффективности смешанного эволюционного метода.

4.2.2. Оценка эффективности метода комбинирования эвристик.

4.3. Адаптивность.

4.4. Предотвращение преждевременной стагнации.

Выводы.

В настоящее время весьма актуальными являются проблемы создания и разработки новых высокоточных и быстрых методов для синтеза проектных решений[18,23]. Маршруты проектирования сложных изделий в САПР машиностроения и радиоэлектроники состоят из чередующихся процедур синтеза и анализа проектных решений. В современных САПР преимущественно развиты математическое и программное обеспечения процедур анализа. Принятие проектных решений охватывает широкий круг задач, однако эти задачи трудно формализуемы. Но и в случае формализации их практическая реализация не всегда очевидна. Для многих формализуемых задач структурного синтеза применение известных математических методов не представляется возможным вследствие проблем NP-полноты и большого размера задач. Именно по этой причине структурный синтез обычно выполняется в интерактивном режиме при определяющей роли человека. В первую очередь, это относится к структурному синтезу, при котором выбираются принципиальные конструктивные и схемные решения. Однако по мере усложнения проектируемых изделий возможности человека в решении задач сужаются, растут затраты времени на проектирование, зачастую принимаются решения, далекие от оптимальных. Поэтому поиск новых эффективных методов структурного синтеза проектных решений относится к актуальным проблемам развития математического обеспечения САПР.

Методы локальной оптимизации (Hill Climbing), моделирование отжига (Simulated Annealing) [55,56], генетические алгоритмы (Genetic Algorithms), [35,51,54], нейронные сети (Neural Network) [57,63,66] и поиск с запретами (Tabu Search)[47,48,49,50] - только часть стохастических алгоритмов, которые применяются при решении задач проектирования. Все эти методы, за исключением генетических алгоритмов (ГА), в каждый момент поиска рассматривают только одно решение, и оно неоднократно улучшается во время работы алгоритма.

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

Генетические алгоритмы были предложены в 1975 г. профессором Джоном Холландом [54] в Мичиганском университете. Они получили широкое распространение благодаря профессору университета штата Иллинойс Дэйвиду Гольдбергу [51] и его студентам [35]. В дальнейшем генетические алгоритмы получили развитие в трудах: Э.Гудмана, Л.Дэйвиса, Д.Фогелья и многих других. Значительный вклад в развитие теории эволюционного моделирования и стохастической оптимизации внесли Курейчик В.В.[9,10,59], Курейчик В.М.[5,10,11,12], Батищев Д.И.[2], Мухачева А.С. [16], Де Янг[35,36], Букатова ИЛ.[3], Растригин Л.А.[27], НоренковИ.П. [17,18,19,20,23].

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

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

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

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

Для повышения эффективности ГА разрабатываются новые алгоритмы выполнения генетических операторов. Разработан ряд алгоритмов кроссовера, селекции и мутации [21,32,36,40,64,65,68].

Другой подход к повышению эффективности ГА основан на применении метода комбинирования эвристик (НСМ) [17], в котором гены представляют не сами искомые проектные параметры, а некоторые эвристические алгоритмы их выбора. Эффективность НСМ зависит от правильности выбора совокупности используемых при поиске эвристических правил.

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

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

В работе показано, что достижение поставленной цели требует решения следующих основных задач:

1. Анализ существующих подходов к решению задач структурного синтеза в проектировании и логистике.

2. Определение параметров, управление которыми позволяет повысить эффективность ГА.

3. Разработка новых генетических методов структурного синтеза проектных решений.

4. Экспериментальная оценка эффективности разработанных методов.

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

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

Диссертация включает введение, четыре главы с выводами, заключение, список литературы и приложения.

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

6. Экспериментальная оценка эффективности новых генетических методов - смешанного эволюционного метода и метода комбинирования эвристик - показала, что однородный и одноточечный кроссоверы не относятся к лучшим вариантам ГА. При этом метод комбинирования эвристик HCM-m(m) превосходит по эффективности метод CGA-w(m) с обычным кодированием хромосом. Смешанный генетический метод HCM-m(m) с многими родителями превосходит по эффективности метод НСМ-т(2), в котором при кроссовере происходит скрещивание генов только двух родителей.

Результаты диссертационной работы внедрены в ЗАО «СИНОПСИС АРМЕНИЯ», в КБ ИГАС «Волна» (г. Москва) и в учебный процесс МГТУ им. Н.Э. Баумана.

113

1. Автоматизированный синтез сооружений биохимической очистки сточных вод /ОАО «Пигмент», http://www.gaps.tstu.ru/win-251/lab/sreda/ope/ob ecol html/avtom.html

2. Батищев Д.И., Власов С.Е., Булгаков И.В. Решение задачи «слепого» упорядочения при помощи генетических алгоритмов. М.: Научное издательство «ТВП», 1996. - С. 143-155.

3. Букатова И.Л. Обучающиеся, адаптивные и самоорганизующиеся эволюционные вычисления. М.: Научное издательство «ТВП», 1996. -С. 169-181.

4. Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки //Информационные технологии. 2005. -№10.-С. 36-43.

5. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционных вычислений. М.: ФИЗМАТЛИТ, 2003. -432с.

6. Ермаченко А. И., Сиразетдинов Т.М. Рекурсивный метод для решения задачи гильотинного раскроя//Принятие решений в условиях неопределенности. Сб. научн. статей. -Уфа: УГАТУ, 2000. С. 35-39.

7. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения /А.С. Мухачева, А. В. Чиглинцев, М. А. Смагин, Э.А. Мухачева //Информационные технологии. -2001. № 9, приложение. - 46с.

8. Кукин В.Д. Эволюционная модель для решения потоковой задачи Штейнера // Методы математического моделирования и информационные технологии. Труды ИПМИ КарНЦ РАН. -Петрозаводск, 2004. С. 200 - 211.

9. Курейчик В.В. Перспективные архитектуры генетического поиска //Программные продукты и системы. 1998. - № 3. - С. 47-48.

10. Курейчик В.М. Зинченко JI.A. Синергетическое эволюционное проектирование// 8 национальная конференция по искусственном интеллекту с международным участием, г.Коломна, 7-12 октября, 2002г. М., 2002. - С.876-884.

11. Курейчик В.М. Курейчик В.В. Фрактальный алгоритм разбиения графов// Теория и системы управления(М.). -2002. № 4. - С. 65-75.

12. Курейчик В.М. Мелихов А.Н. Берштейн JLC. Применение графов для проектирования дискретных устройств. М.: Главная редакция физико-математической литературы издательства "Наука", 1974. - 304 с.

13. Ли К. Основы САПР (CAD/CAV/CAE). СПб: Питер, 2006. - 580 с.

14. Мартынов В. В., Валиуллин А.М. Регулярное размещение двумерных геометрических объектов сложной формы/Прикладная геометрия: электронный журнал(М.). -1999. -Вып. 3. -№ 4. -11с.

15. Модели и методы решения задач ортогонального раскроя и упаковки / Э.А. Мухачева, А.Ф. Валеева, В.М. Картак, А.С. Мухачева //Приложение к журналу «Информационные технологии», -2004 № 5. -32 с.

16. Мухачева А. С., Мухачева Э. А. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя //Информационные технологии. 2002. -№ 6. - С. 25-30.

17. Норенков И. П. Эвристики и их комбинации в генетических методах дискретной оптимизации //Информационные технологии. 1999. -№1. -С. 2-7.

18. Норенков И.П. Основы автоматизированного проектирования. М.: Издательств МГТУ им. Баумана, 2000. - 336 с.

19. Норенков И.П., Арутюнян Н.М. Смешанный эволюционный метод // Информационные технологии. 2007. - № 1. - С. 17-20.

20. Норенков И.П., Арутюнян Н.М. Метагенетический алгоритм оптимизации и структурного синтеза //Информационные технологии. -2007. -№3.- С. 10-13.

21. Норенков И.П., Арутюнян Н.М. Состояние проблемы структурного синтеза в проектировании и логистике //Наука и образование. Инженерное образование: Электронный журнал. 2007. - № 9. -37с.

22. Норенков И.П., Арутюнян Н.М., Бондаренко А.А., Сравнительный анализ эффективности эволюционных методов на примере задачи синтеза расписаний // Информационные технологии. 2006. - № 5. -С.6-11.

23. Норенков И.П., Кузьмик П.К. Информационная поддержка наукоемких изделий. М.: Издательств МГТУ им. Баумана, 2002. - 320 с.

24. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.-288 с.

25. Овчинников В.А. Эволюционно-генетический подход к синтезу передней части кузова легкового автомобиля //Информационные технологии. 2005. - № 9. - С. 36-38.

26. Писаренко Г.К. Алгоритмы частотного планирования в телекоммуникационных системах радиосвязи // Информационные технологии. 2000. - № 7. - С. 14-17.

27. Растригин JI.A. Случайный поиск в эволюционных вычислениях. -М.: Научное издательство «ТВП», 1996. С. 135-142.

28. Скурихин А. Генетические алгоритмы// Новости искусственного интеллекта. 1995. - № 4. - С. 6-17.

29. Системы автоматизированного проектирования в радиоэлектронике: Справочник /Под ред. И.П. Норенкова. М.: Радио и связь, 1986. - 368 с.

30. Стоян Ю. Г. Размещение геометрических объектов. Киев: Наукова думка, 1975.-234 с.

31. Теория и методы автоматизации проектирования вычислительных систем / Под ред. М.Брейера. М.: Мир, 1977. -282 с.

32. Baker J. Reducing Bias and Inefficiency in the Selection Algorithm Genetic Algorithms and Their Applications// Proc. Second International Conf. J. Grefenstette /Ed. Lawrence Erlbaum. Massachusetts(MIT),1987. -P. 14-21.

33. Blanton J., Wainwright R. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms// Proc. of 5th Int. Conf. on GA. Massachusetts(MIT), 1993. - P. 452-460.

34. Colorni A., Dorigo M., V. Maniezzo. Distributed Optimization by Ant Colonies //Proceedings of the First European Conference on Artificial Life, Paris, 1992.-P. 134-142.

35. De Jong K. An Analysis of the Behavior of a Class of Genetic Adaptive Systems: PhD thesis. Ann Arbor, 1975. - 126 p.

36. De Jong K.A., Spears W.M. A Formal Analysis of the Role of Multipoint Crossover in Genetic Algorithms //Annals of Mathematics and Artificial Intelligence. -Florida, 1992. -V5. P. 1-26.

37. Deb K. and Agrawal, S. Understanding interactions among genetic algorithm parameters //Foundations of Genetic Algorithms, 1999. V. - P. 265-286.

38. Deneubourg J., Goss S., Pasteels J.M. Self-organization mechanisms in ant societies (II): learning in foraging and division of labor. //From Individual to Collective. Behavior in Social Insects. Basel: Birkhauser, 1987.-267 p.

39. Devis L., Cox A. A genetic algorithm for survivable network designtV»

40. Proc. of 5 International Conference on Genetic Algorithms, San Mateo (California), 1993.-P. 408-415.

41. Dorigo M. Optimization, Learning and Natural Algorithms: PhD thesis. -Milan, 1992.-109 p.

42. Dorigo M., Caro G., Gambardella L. Ant Algorithms for Discrete Optimization //Artificial Life, V.5. Brussels, 1999. -№ 3. -96 p.

43. Dorigo M., Gambardella L. Ant Colony for Traveling Salesman Problem. Bruxelles,1996. - P. 53-66.

44. Eberhart R.C. and Kennedy J. A New Optimizer Using Particles Swarm Theory //Proc. Sixth International Symposium on Micro Machine and Human Science, Piscataway, 1995. -P. 39-43.

45. Eberhart R.C., Dobbins R.W., Simpson P. Computational Intelligence PC Tools. Boston: Academic Press, 1996. - 464 p.

46. Giffler В., Tompson G.L. Algorithms for Solving Production-Scheduling problems // Operational Research. 1964. - № 2. - P. 305-324.

47. Glover F. Future paths for integer programming and links to artificial intelligence// Computers and Operations Research. 1986. - Vol. 13. - P. 533-549.

48. Glover F. Tabu search: Part 1// ORSA Journal on Computing. 1989. -Vol. l.-P.l90-206.

49. Glover F. Tabu search: Part 2 // ORSA Journal on Computing. 1990. -Vol. 2. - P.4-32.

50. Glover F. Tabu search methods for optimization. Feature Issue of Europen J. Oper. Res. -1998. V106, № 2. - P. 4-32

51. Glover F., Laguna. M. Tabu search. -Boston: Kluwer Acad. Publ, 1997. -382 p.

52. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989. - 412 p.

53. Goodman E., Punch W. New Technologies to Improve Coarse-Grain Parallel GA Performance // CAD-95 XXII Int. School and Conf. on CAD. Yalta-Gurzuff, 1995. Part 2. - P. 29-40.

54. Holland J. Adaptation in Natural and Artificial Systems. Ann Arbor. Univ. of Michigan Press, 1975.-228 p.

55. Holland J. Some practical aspects of adaptive systems theory// Electronic Information Handling. London, 1965. - P. 209 - 217.

56. Kirkpatrick S. Optimization by simulated annealing: quantitative studies //Statistical Physics. -1984. Vol. 34. - P. 975-986.

57. Kirkpatrick S., Vecchi M. P. Optimization by simulated annealing. //Science. 1983.-Vol. 220.-P. 671-680.

58. Kohonen T. Self-organization and associative memory. New York: Springer-Verlag, 1997, - 428 p.

59. Koza J.R., Riccardo Poli. A Genetic Programming Tutorial. Fairchild, 2004.-819p.

60. Kureichik V.M. Kureichik V.V. Zinchenko L.A. Greedy genetics in memory optimization of reconfigurable computing in wireless //Advances in concurrent engineering. -Lisse, 2002. P. 771-777.

61. Lis J. Parallel Genetic Algorithm with Dynamic Control Parameter. //Proceedings of the 1996 IEEE Conference on Evolutionary Computation. -Piscataway, 1996. -P.324-329.

62. Lodi A., Martello S., Vigo D. Heuristic algorithms for the three-dimensional bin packing problem //European Journal of Operational Research. -2002. № 141. - P. 410-420.

63. Martynov V. Geometrical objects regular placement onto a stock sheet or strip//Pesquisa Operacional(BRAZIL). -1999. -Vol. 19. № 2. - P. 211222.

64. McClelland J. L., Rumelhart D. E. Parallel distributed processing: explorations in the microstructures of cognition. Volume 2: psychological and biological models. Cambridge(Mass.): MIT Press., - 1986. - 454 p.

65. Muhlenbein J. How genetic algorithms really work: Mutation and Hill climbing, Parallel Problem Solving from Nature -2- R / Manner and B. Manderick eds. Amsterdam, 1994. - P. 15-26.

66. Pinaki Mazumder, Rudnick Elizabeth M. GENETIC ALGORITHMS for VLSI Design, Layout & Test Automation. -Upper Saddle River: Hall PTR, 1999.-335 p.

67. Rumelhart D. E., McClelland J. L. Parallel distributed processing: explorations in the microstructures of cognition. Volume 1: foundations. -Cambridge(Mass.): MIT Press,. 1986. - 516p.

68. Shahookar K.,Mazmunder P. A Genetic Approach to standart Cell Placement Using Meta-Genetic Parameter Optimization //IEEE Trans, on CAD. 1990. - Vol.9, No.5, May. - P. 500 - 511.

69. Spears W., DeJong K. An Analysis of Multipoint Crossover Foundations of Genetic Algorithms. -G. Rawlins, /ed. Morgan-Kaufmann. -Bloomington, 1991.-P. 301-315.

70. Syswerda G. Uniform Crossover in Genetic Algorithms //Proc. 3rd Int. Conf. on Genetic Algorithms. -LA, 1989. P. 2-9.

71. The Radio-link Frequency Assignment Problem: a Case Study Using GA./ A. Kapsalis, P. Chardaire, V. Rayward-Smith, G.Smith //AISB Workshop on Evolutionary Computing. -Washington, 1995. P. 117-131.

72. Tulai A.F. and Oppacher F. Parallel Genetic Algorithm with Strategy Parameters Encoded as Chromosomes //Artificial and Computational Intelligence. Tokyo, 2002. -№ 3. - P 34-47.