Генетические алгоритмы

Генетические алгоритмы

ИО-1-95

Введение.

Генетический алгоритм - это итерационная процедура, которая обрабатывает группу хромосом (решений) называемую популяцией [8-13]. Число хромосом в популяции называется размером популяции М. Каждая хромосома состоит из генов. Гены размещены в определенных частях хромосомы, которые называются "лоци". Каждый ген-хромосом может быть в нескольких состояниях, называемых "аллелями". Терминология, использованная здесь, заимствована из естественной генетики.

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

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

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

Описание общего генетического алгоритма.

1) Создание структуры решения искомой задачи в виде массива a[i], i=1,...n, где n - максимальное число компонент структуры

Анализ потребительского рынка

Несколько лет назад фирма IBM Consulting выполнила заказ на создание нейросетевой системы, прогнозирующей свойства потребительского рынка. Заказчик - один из крупнейших производителей пищевых продуктов, имеющий огромные рынки сбыта. Одним из основных маркетинговых механизмов заказчика является распространение купонов, дающих право покупки определенного товара со скидкой. Так как затраты на рассылку купонов довольно велики, решающим фактором является эффективность рассылки, то есть доля клиентов, воспользовавшихся скидкой.

Для повышения эффективности купонной системы важно было провести предварительную сегментацию рынка, а затем адресовать клиентам каждого сегмента именно те купоны, которыми они с большей вероятностью воспользуются. В терминах анализа данных здесь требовалось решить задачу кластеризации, что и было успешно сделано с помощью сетей Кохонена. На втором этапе для потребителей каждого из кластеров подбирались подходящие коммерческие предложения, а затем строился прогноз объема продаж для каждого сегмента. http://www. /9701eds2.htm

Другой вариант решения этой же задачи избрала компания GoalAssist Corporation, исполняя заказ крупной маркетинговой фирмы. Требовалось исследовать стратегию поощрительных товаров (когда, например, присылая 5 этикеток от чипсов, клиент получает бесплатно футболку) для определенной компании, торгующей пищевыми продуктами. Обычные методы прогнозирования отклика потребителей оказались в данном случае недостаточно точны. В результате спрос на футболки оказался слишком велик и многим покупателям пришлось подолгу ждать получения приза, в то время как другие подарки остались невостребованными. Чтобы повысить точность прогнозирования, было решено использовать исторические данные и нейронные сети.

Компания GoalAssist Corporation построила две нейросети для решения этой задачи. Первая из них - это сеть с адаптивной архитектурой пакета NeuroShell Classifier компании Ward Systems Group, на входы которой подавались различные параметры товаров и рекламной политики. С помощью этой сети, предназначенной специально для классификации, было получено разделение входов на 4 класса, характеризующих отклик потребителей. Те же входы вместе с ответом первой сети подавались далее на вход пакета NeuroShell Predictor, который также содержит сложную самоорганизующуюся сеть, но приспособленную для задач количественного прогнозирования. Средняя ошибка предсказаний составила всего около 4%. Построение этой модели заняло около 120 часов, также потребовалось время на предобработку входных данных. Эксперты GoalAssist Corp. считают, что эта модель и далее будет успешно применяться для решения маркетинговых задач. http://www. /predconsum. htm

Компания Neural Innovation Ltd. использует при работе с маркетинговыми компаниями конкретную стратегию прямой рассылки. Вначале рассылается 25% от общего числа предложений и собирается информация об откликах потребителей. Затем эта информация поступает на вход нейрокомпьютера, который осуществляет поиск оптимального сегмента потребительского рынка для данного товара. Затем остальные 75% предложений рассылаются в указанный сегмент. При этом эффективность рассылки существенно возрастает.
http://www. neural. co. uk/marketing/mailshot. html

Прогнозирование объема продаж и управление закупками

Изложенные в предыдущем пункте методы хорошо зарекомендовали себя на устойчивых западных рынках. При создании подобных систем на российском рынке необходимо учитывать его нестабильность, а также особенности поведения российских потребителей (например, закупки в период высоких инфляционных ожиданий). В изменчивых условиях для торговых фирм особенно важно иметь прогноз спроса клиентов и дохода компании, чтобы осуществлять оптимальное управление закупками. В настоящее время компания "НейроПроект" совместно с маркетинговой фирмой "Конси" (Нижний Новгород) ведет разработку системы анализа потребительского рынка и прогнозирования спроса на основе российских исторических данных.
http://www. konsi. nnov. ru:8002/

Проектирование и оптимизация сетей связи

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

Кроме управления маршрутизацией потоков, нейросети используются и для проектирования новых телекоммуникационных сетей. При этом удается получить очень эффективные решения. http://www. cbu. edu/~pong/624kep2.htm

Прогнозирование изменений котировок

Компания Alela Corp. занимается прогнозированием изменения биржевых индексов. Для предсказания знаков изменения индексов применяется нейронная сеть, использующая РБФ (радиальные базисные функции).

На сайте компании можно бесплатно получить прогнозы изменения индексов Dow Jones, S&P500 и Merval, а также убедиться, что доля верных предсказаний составляет не менее 80%. Создатели сайта предлагают всем желающим использовать эти прогнозы в качестве дополнительных индикаторов.

http://. ar/~alela/index. htm

Управление ценами и производством

Руководители предприятий часто недооценивают потери от неоптимального планирования производства. Так как спрос и условия реализации зависят от времени, сезона, курсов валют и многих других факторов, то и объем производства следует гибко варьировать с целью оптимального использования ресурсов. Уже существуют примеры нейросетевых систем планирования, которые применяются совместно со стандартными методами исследования операций, динамического программирования, а также с методами нечеткой логики.
http://www. cbu. edu/~pong/624twg2.htm

Крупное английское издательство, выпускающее газеты, приобрело у фирмы Neural Innovation Ltd. систему планирования цен и затрат, основанную на нейросети с использованием генетических алгоритмов. На основе исторических данных система обнаруживает сложные зависимости между затратами на рекламу, объемом продаж, ценой газеты, ценами конкурентов, днем недели, сезоном и т. д. После этого возможен подбор оптимальной стратегии с точки зрения максимизации объема продаж или прибыли.
http://www. neural. co. uk/marketing/news. html

Исследование факторов спроса

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

Нейронные сети идеально подходят для решения этой задачи. Существующие нейросетевые методы позволяют выявлять сложные зависимости между факторами спроса, прогнозировать поведение потребителей при изменении маркетинговой политики, находить наиболее значимые факторы и оптимальные стратегии рекламы, а также очерчивать сегмент потребителей, наиболее перспективный для данного товара.
http://www. /examples. htm
http://www. /Marketing/marketingpaper. htm

Анализ страховых исков

Фирмой Neural Innovation Ltd. создана нейросетевая система Claim Fraud Analyser, позволяющая мгновенно выявлять подозрительные страховые иски, относящиеся к поврежденным автомобилям. На входы системы подаются такие параметры, как возраст и опыт водителя, стоимость автомобиля, наличие подобных происшествий в прошлом и другие. В результате обработки выдается число - вероятность того, что данный иск связан с мошенничеством. Такая система позволяет не только сэкономить за счет выявления фальсификаций, но и улучшить отношения с клиентами за счет более быстрого удовлетворения честных исков. http://www. neural. co. uk/finance/fraud. html

Как нейросети могут помочь в работе?

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

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

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

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

·  негладкая зависимость оптимизируемого критерия от подбираемых параметров;

·  слишком большое число параметров;

·  невозможность вычислить производные по параметрам.

Эти ситуации возникают, например, при

·  подгонке к данным сложной модели, например модели рассеяния загрязнителей;

·  подборе степени и набора независимых переменных для регрессии.

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

·  эволюция - сдвиг варианта в направлении ожидаемого оптимума с использованием, вообще говоря, как производных критерия по пааметрам, так и стохастических "скачков";

·  отсеивание "неудачливых" вариантов;

·  скрещивание "удачливых" вариантов: порождение вариантов - "потомков", сочетающих удачные значения параметров "родителей".

Название "генетические алгоритмы" связано с тем, что они воспроизводят современные представления об естественном отборе: скрещивание генотипов - определение удачности порожденных фенотипов - отсев неудачников из набора партнеров для следующего скрещивания.
Скрещивание является наиболее критичным этапом генетического алгоритма. Оно существенно зависит от того, можно ли установить степень удачности не только варианта в целом, но и его отдельных частей - "генов" (в нашем случае - отдельных координатных интервалов или параметров модели). В рассматриваемой системе это возможно, когда вариант имеет иерархическую структуру и для нее можно построить дерево вкладов (имеются в виду вклады в значение критерия оптимальности). Также и для нейросетевых структур возможно распределение ошибки целого между частями. В прочих же случаях части, которыми обмениваются скрещиваемые варианты, выбираются стохастически. В работе рассматривается применение генетического алгоритма, базирующегося на алгоритме Холланда - Simple Genetic Algorithm, для синтеза структур вычислительных систем реального времени (ВС РВ). Основное внимание уделяется проблемам настройки этого алгоритма на задачу синтеза структур ВС РВ и обоснованию принятых решений, приводятся результаты его исследования.

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

В качестве базовой рассматривается задача синтеза структур ВС РВ в следующей постановке. Для заданных: наиболее сложной истории поведения прикладной программы - частично упорядоченное множество рабочих интервалов процессов, составляющих историю выполнения программы (ациклический ориентированный размеченный граф), и директивного срока ее выполнения; требуется определить: минимальное число процессоров в ВС необходимое для выполнения директивного срока, распределение процессов по процессорам ВС. Другие варианты задачи синтеза структур ВС РВ получаются как расширение базовой путем изменения набора оптимизируемых характеристик ВС и критериев оценки качества решений.

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

Исследование алгоритма показало его высокую эффективность с точки зрения:

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

2.  сложности получения решения - сложность алгоритма растет практически линейно с ростом размера задачи и числа оптимизируемых параметров;

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

Fujitsu разрабатывает программную поддержку генетических алгоритмов

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

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

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

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

Генетический алгоритм для канальной трассировки

Генетический алгоритм - это итерационная процедура, которая обрабатывает группу хромосом (решений) называемую популяцией [8-13]. Число хромосом в популяции называется размером популяции М. Каждая хромосома состоит из генов. Гены размещены в определенных частях хромосомы, которые называются "лоци". Каждый ген-хромосом может быть в нескольких состояниях, называемых "аллелями". Терминология, использованная здесь, заимствована из естественной генетики. Приведем соответствие терминов ГА и классической задачи канальной трассировки.

Фенотип - топология расположения цепей на кристалле.

Генотип - генетическая схема кодирования топологии.

Хромосома - кодированное представление одного варианта топологии. Хромосома состоит из генов.

Ген - элемент хромосомы, задающий некоторый фрагмент топологии.

Популяция - набор хромосом (закодированных решений задачи трассировки).

Фитнесс - целевая функция, определяющая качество решения задачи.

Генерация - один цикл работы генетического алгоритма.

Генетический алгоритм требует, чтобы хромосомы оценивались с точки зрения целевой функции задачи. Целевая функция оценивает какие-либо качества решения соответствующего данной хромосоме (длину цепей, число магистралей и т. д.). Как было указано выше, генетический алгоритм обрабатывает популяцию решений, закодированных в хромосомы. В процессе обработки популяции, к ней последовательно применяются различные генетические операторы, такие как кроссинговер, мутация с заданными вероятностями (PC и PM соответственно) и другие операторы. Затем проводится редукция увеличившейся популяции для отбора лучших решений, которые составят следующее поколение, после чего цикл (генерация) повторяется. Число таких циклов называется числом генераций T. Отметим, что может быть построена большое число архитектур реализации генетического поиска. В нашем подходе выбрана стандартная схема генетического поиска.

Структура алгоритма

Для нашего генетического алгоритма принята следующая схема.

Шаг 1. Определение размера популяции M, числа генераций T, вероятности кроссинговера PC и вероятности мутации PM.

Шаг 2. Задание случайным образом начальной популяции П(0) размером M.

Шаг 3. t=0 ( t = 1,2, ..., T ).

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

Шаг 5. Применение операции мутации к каждой хромосоме популяции П(t) с заданной вероятностью PM.

Шаг 6. Отбор M хромосом с наилучшим значением целевой функции из получившейся популяции П(t) в новую популяцию П(t+1).

Шаг 7. t=t+1.

Шаг 8. Если t<T, то переход к шагу 4.

Шаг 9. Вывод хромосомы с наилучшим значением целевой функции.

Далее в статье рассмотрены генетические операции, применяемые в нашем генетическом алгоритме.

Кодирование хромосомы

Таблица 1
Цепь m	1	1	1	1	1	2	2	2	2	3	3	3	4	4	5
Цепь n	2	3	4	5	6	3	4	5	6	4	5	6	5	6	6
Ген	*	0	0	*	0	0	*	0	*	1	0	0	*	0	*

В данной работе используется представление хромосомы, основанной на топологическом описании канала, т. е. хромосома описывает взаимное расположение цепей. Для этого каждой паре цепей (m, n), где m ё n, ставится в соответствие ген, который может принимать три состояния: 0 - если цепь m должна располагаться выше n, 1 - если цепь m должна располагаться ниже n и * - если их взаимное расположение не имеет значения или определяется из взаимного расположения остальных цепей (это происходит, если цепи не имеют горизонтальных ограничений). Для нашего примера (см. рис.1) хромосома будет иметь вид, показанный в табл.1.

Как мы видим, длина хромосомы получается достаточно большой (для примера на рис. 1 она равна 15), что не приемлемо. Поэтому для уменьшения длины хромосомы используется анализ РГВО и ГГО. Уменьшение длины получается за счет того, что взаимное расположение некоторых пар цепей уже зафиксировано в РГВО, и изменение этого расположения приводит к образованию нарушений в канале, т. е. к наложению вертикальных сегментов цепей в канале, что ведет к образованию "мертвой" хромосомы (т. е. такой, из которой не может быть получено решение, удовлетворяющее заданным требованиям). Второй прием, позволяющий уменьшить длину хромосомы, основывается на том, что если цепи не имеют горизонтальных ограничений, то их взаимное положение либо не важно, либо определяется из соотношений с остальными цепями. Такие соотношения отмечены знаком "*". Следовательно, длина хромосомы

L=NGO-NRVO,

где NGO - число горизонтальных ограничений; NRVO - число вертикальных ограничений в РГВО.

В примере для пар цепей (1,6), (2,5), (3,4), (3,5), (3,6), (4,6) взаимное расположение жестко задано РГВО, а взаимное расположение цепей в парах (1,2), (1,5), (2,4), (2,6), (4,5), (5,6)

Цепь m	1	1	2
Цепь n	3	4	3
Ген	0	0	0

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

Ее длина будет равна 3.

Получение из хромосомы эскиза канала с разведенными цепями

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

GT = ( Nеt, ET ),

где Net - множество цепей; ET - множество направленных ребер, описывающих взаимное расположение цепей в канале.

Ребро ( m, n ) e ET, существует тогда и только тогда, когда цепь m должна быть расположена в канале выше цепи n, т. е. на магистрали с меньшим номером. ГТ строится из хромосомы по следующему алгоритму.

Шаг 1. Преобразуем РГВО GRV в ГТ GT.

Шаг 2. i=1.

Шаг 3. Если ребро ( mi, ni ) не принадлежит GT, то это ребро добавляется к GT.

Шаг 4. Проверяем для всех вершин k существование пути из вершины mi к вершине k, при условии, что k = 1, ... , N, k ё mi и k ё ni и не существует ребра ( mi, k ) в GT. Если такой путь существует, то добавляем ребро ( mi, k ) к GT.

Шаг 5. Если i # L, то увеличиваем i на 1 и переходим к Шагу 3.

Шаг 6. Считаем построение ГТ завершенным.

Канал восстанавливается из хромосомы следующим образом.

Шаг 1. Строим по хромосоме ГТ GT.

Шаг 2. i=0.

Шаг 3. Находим вершины, у которых есть только исходящие дуги. Размещаем их на магистрали с номером i или на магистрали с меньшим номером, если это возможно, и удаляем эти вершины из графа.

Шаг 4. i = i + 1.

Шаг 5. Если граф топологии GT не пустой возвращаемся к Шагу 3.

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

Шаг 7. Возвращаем полученный образец размещения цепей в канале шириной i.

Например, пусть задана хромосома А=000. Рис. 1 показывает полученный образец трассировки, который является оптимальным решением для примера. Если A=010 (отличие от предыдущего решения заключается в том, что цепь 4 располагается выше цепи 1), то эскиз канала с разведенными цепями для такой хромосомы показан на рис. 3.

Целевая функция оценки хромосомы

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

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

F(A)=(UsedTrаck(A)+2)*С+

TоtаlVertSeg(A),

где C - число контактов.

Программная функция UsedTrаck(A) определяет число магистралей, занимаемых каналом, полученным при восстановлении из хромосомы A, а программная функция TоtаlVertSeg(A) определяет длину вертикальных сегментов цепей в полученном решении.

Длина вертикальных сегментов цепи определяется как расстояние между контактами и переходными отверстиями, которые соединяют вертикальные и горизонтальные сегменты. Например, для канала на рис.1 число занятых магистралей равно 4, длина вертикальных сегментов равна 22. Таким образом целевая функция хромосомы F(A)=(4+2)*8+22=70, а для канала, показанного на рис. 3, F(A)=72.

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

Экспериментальные результаты

Генетический алгоритм канальной трассировки реализован на языке Си++ для IBM-совместимых PC.

Теоретическая временная сложность алгоритма составляет:

T*(M*PC*2)*PM*O(N2),

где T - число поколений; M - размер популяции; PC - вероятности кроссинговера; PM - вероятность мутации; O(N2) - временная сложность декодирования хромосомы; N - число цепей.

Таблица 2
Номер теста	Число контактов	Число цепей	Оптималь- ное число магистралей	Оптимальная длина цепей	Среднее отклонение от оптимального результата в %
0	80	51	8	773	0.0006%
1	80	38	10	1072	0.0000%
2	80	36	9	1076	0.0005%
3	80	37	10	1134	0.0000%
4	100	66	10	1282	0.9204%

В экспериментах, проведенных для оценки существующих канальных трассировщиков, решающих задачу в аналогичной постановке [2,4,17,18], оценивалось только минимальное число магистралей, полученных алгоритмом, а такой параметр, как длина соединений, не учитывался. Для определения оптимальной длины соединений нами использовался динамический алгоритм [7], который находит оптимальное решение по числу магистралей и длине соединений. Алгоритм [7] для решения стандартных тестов использоваться не может из-за его большой пространственной и временной сложности. Поэтому для экспериментальной проверки алгоритма были разработаны примеры. Для этих примеров были найдены оптимальные результаты по числу магистралей и длине соединений. Параметры выбранных тестов (число контактов, число цепей, оптимальное число магистралей и оптимальная длина цепей) представлены в табл. 2.

Затем к этому же набору тестов был применен генетический алгоритм. Было проведено по 100 испытаний для каждого примера с различными начальными установками генератора случайных чисел. Испытания проводились при следующих установках генетических параметров: M=50, T=20, PC=1,00 и PM=0,10, которые были выбраны после соответствующего анализа. В экспериментах был применен "элитный" отбор, т. е. из популяции, полученной после проведения ОК и ОМ, выбирается M хромосом с наименьшим значением ЦФ.

Во всех случаях были получены оптимальные решения по числу магистралей. Среднее отклонение от оптимального результата по длине соединений составило менее 1%. Результаты представлены в табл. 2 в графе "Среднее отклонение от оптимального результата".

Затем был проведен ряд экспериментов для выбора таких генетических параметров, как PM (вероятность мутации) и PC (вероятность кроссинговера), при которых среднее отклонение от оптимального результата будет минимально. Подбор параметров осуществлялся на тесте 4, для которого было получено наибольшее отклонение от оптимального результата (см. табл.2). Первоначально был проведен подбор оптимального значения PC. Для этого PM была зафиксирована равной 0,1, а PС изменялась от 0 до 1 с шагом 0,1. Наименьшее среднее отклонение от оптимального результата (0,9204%) было получено при вероятности кроссинговера равной 1.

После этого, была зафиксирована PС равная 1, а PM изменяла значение от 0 до 1 с шагом 0,10. Полученные результаты показаны на рис. 6. Эксперименты показали, что наименьшее среднее отклонение от оптимального результата (0,80%), полученное в результате 100 испытаний для каждого значения PM, были при PM равной 0,3.

Таблица 3
Тест	EA	EP	GA1	GA2
Ex1	12	12	12	12
Ex3b	17	17	17	17
Ex3c	18	18	18	18
Ex4b	17	17	17	17
Ex5	20	20	20	20

Для сравнения нашего алгоритма с аналогичными были использованы стандартные тесты Ex1, Ex3b, Ex3c, Ex4b и Ex5 из работы [2]. Для всех этих тестов были найдены оптимальные решения по числу магистралей алгоритмом. Минимальное число магистралей, найденное различными алгоритмами канальной трассировки, представлено в табл.3. Сравнение по длине соединений провести не представляется возможным, т. к. эти алгоритмы не оптимизируют этот параметр.

В табл.3 EA - алгоритм канальной трассировки, описанный в работе [2], EP - эволюционный алгоритм, описанный в - [7], GA1 - генетический алгоритм, описанный в - [11], GA2 - представленный алгоритм.

Заключение

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

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

http://www. tvp. ru/mathem3.htm

http://www. cs. /labs/lvk/materials/tez_sapr99_1.html

http://www. iki. rssi. ru/ehips/Genetic. htm

http://parallel. ru/news/fujitsu_genetic. html

http://www. nestor. /kg/kg9907/kg92905.html

http://www. neuralbench. ru/RUS/THEORY/GENETIC. HTM

http://www. cio. ru/ap/1999/01/08.htm

http://www. chat. ru/~nurtakar/genetic. htm

http://www. /Marketing/marketingpaper. htm

http://www. /9701eds2.htm

http://www. /predconsum. htm

http://www. neural. co. uk/marketing/mailshot. html

http://www. konsi. nnov. ru:8002/