Разработка направленного оператора мутации, основанного на методе Кернигана-Лина в генетических алгоритмах

Материалы Международной конференции

“Интеллектуальные САПР”

пользовать математический аппарат нейронных сетей. В данной статье рассматривается возможность создания алгоритма осуществления семантического анализа и преобразования входной информации, типа T->t (реферирование) и t->T. Сеть синтаксического анализатора, использованная в экспериментах - Простая Рекуррентная Сеть (SRN; Elman 1990, 1991; Miikkulainen 1993), тренируемая чтобы отобразить последовательность входных текстовых представлений в статическое предло-, .

, . Выходной слой - конкатенация пяти текстовых сборок представления, соответствует контексту предложения. На каждом шаге последовательности обучения представление слова загружается во входную сборку, и активизация распространяется через скрытый слой (60 устройств шириной) к выходной сборке. Активизация в скрытом слое сохраняется в предыдущем скрытом слое и используется при следующем шаге совместно с входной сборкой, как источник сигнала для скрытого слоя. Для изменения весов и корректировки ошибок используется алгоритм обрат. -ние контекста по нескольким словам. Сеть тренировалась с уровнем обучения 0.5 в течении 100 циклов, 0.1 - 50 циклов, 0.05 - 5 циклов и окончательно с уровнем 0.01 в течении 200 циклов. На этом этапе средняя ошибка на устройство составляет 0.024.

УДК 681.3.001.63

Ю.О. Чернышев, О .Г.Ведерникова

РАЗРАБОТКА НАПРАВЛЕННОГО ОПЕРАТОРА МУТАЦИИ, ОСНОВАННОГО НА МЕТОДЕ КЕРНИГАНА-ЛИНА В ГЕНЕТИЧЕСКИХ

АЛГОРИТМАХ

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

Переспективным развитием ГА является разработка генетических операторов ( ), .

является разработка операторов мутации адаптированных к решению задачи размещения, основанных на методе Кернига-Лина и предназначенных для оптимиза-

( ), -, . -дующие обозначения. Пусть имеется КП размером nx х ny, Li - сканирующие контуры размером а ха, a^Snx ,i=1,2,...,r| где r|=(nx-a+1)(ny-a+1) - количество контуров. Контур L разделяет все множество элементов E={ei} на два подмножества Q={qi} и P={pi} , расположенных соответственно внутри контура L и вне контура. Q и P=E и Q n P=0. Q0 и P0 - рабочие подмножества элементов.

Известия ТРТУ

Тематический выпуск

Мутаиия 11 переставляет случайную пару элементов с положительным весом W и может бать описана следующим образом:

Шаг 1. Выбрать случайный контур Ь с равной вероятностью рЬ=1/т|.

Шаг 2. Выбрать случайную пару элементов qi е р и р1 е Р, вес которой W(qi,pi) - положителен:

W(qi,pi)=f(qi,P) + Др!,0) - f(qi,Q) - %1,Р),

где Дд,Р) = I S(q) п8(Р) | - количество цепей, связывающих элемент q с множеством Р. Другими словами, если W(qi,pi) >0, то элементы qi и pi сильнее связанны с , .

Шаг 3. Произвести перестановку выбранной пары элементов:

Р=Р\ и р1 , Р=Р\ р1 и

Разработанный оператор направленной мутации позволяет в процессе поиска ГА быстро улучшать структуру и качество решений задачи размещения элемен-, .

УДК 681.3.001

Ю.В. Чернухин, В.И. Протасов, Д.С. Панфилов

МЕТОД КОЛЛЕКТИВНОГО ПРИНЯТИЯ РЕШЕНИЙ ПРИ ПОСТРОЕНИИ ФОТОРОБОТА НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

В данной работе предлагается метод составления фоторобота человеческого лица на основе генетического алгоритма. Разработаны алгоритм и программный комплекс системы коллективного принятия решения данной задачи и проведены

.

Предполагается, что свидетели (эксперты) видели лицо подозреваемого и запомнили его разные фрагменты. Совместными усилиями они должны восстановить .

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

( ).

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

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

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