Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Лекция'
Трехфазная цепь является частным случаем многофазных электрических систем, представляющих собой совокупность электрических цепей, в которых действуют ...полностью>>
'Документ'
С конца XVIII в. открываются проявления благотворительности в виде меценатства1 - покровительства искусству, наукам, собирания больших библиотек, кол...полностью>>
'Конкурс'
Принимаются проекты, направленные на проведение мероприятий для различных групп жителей, соисполнителями которых являются не менее двух общественных ...полностью>>
'Автореферат'
Защита диссертации состоится «__» 2010г. в часов на заседании диссертационного совета Д 050.005.01 при Институте экономики сельского хозяйства Таджик...полностью>>

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

Главная > Документ
Сохрани ссылку в одной из сетей:

ФРАГМЕНТНЫЕ ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

Норенков И.П., д.т.н., профессор

МГТУ им. Н.Э. Баумана

e-mail: norenkov@wwwcdl.bmstu.ru

1. ВВЕДЕНИЕ

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

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

Подробный анализ разновидностей генетических операторов выполнен в работе [1]. Одним из основных операторов, определяющих эффективность генетического поиска, является кроссовер (кроссинговер), его исследованию посвящено большое число работ. Среди них необходимо отметить разработку алгоритма с однородным кроссовером [2], исследование вероятности разрыва шаблонов разных порядков при многоточечном кроссовере [3], исследование его поисковых и смешивающих возможностей [4, 5], применение кроссовера с многими родительскими хромосомами [6] и др. Способы выполнения других операторов рассматривались в ряде работ, например, в [7, 8] описан алгоритм изменения вероятности мутации в процессе поиска экстремума. Детальное описание алгоритмов селекции приведено в [9].

Данный доклад посвящен изложению результатов исследования генетических методов, выполненных в МГТУ им. Н.Э. Баумана с целью повышения точности ГА. Основу полученных результатов составляют, во-первых, метод кодирования хромосом, названный методом комбинирования эвристик и разработанный еще в 90-годы [10, 11], и методы выполнения генетических операторов, основанные на специальном фрагментировании хромосом [12]. В докладе излагается суть методов с фрагментными кроссовером и макромутациями и приведены результаты экспериментальной оценки их эффективности.

2. ФРАГМЕНТНЫЙ КРОССОВЕР

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

Рис. 1. Структура хромосомы в ММЕМ

Специфика фрагментного кроссовера (ФК) проявляет себя при формировании хромосом для следующего поколения. Параметром, от которого зависит эффективность ФК, является длина L фрагментов, на которые разделяются родительские хромосомы длиной D. При L=D имеем генетический алгоритм (ГА) с одноточечным кроссовером, при L=1 – с однородным кроссовером. На рис.2 показаны результаты применения ФК при решении некоторых тестовых задач:

– синтез многостадийных расписаний (рис.2а);

VRPTW – маршрутизации транспортных средств с временными окнами (рис. 2б);

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

– синтез топологии вычислительной сети (рис. 2г).

Данные, представленные на рис.2, позволяют заключить, что имеется некоторое оптимальное значение L, лежащее в зависимости от характера задачи в диапазоне 2…10.

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

3. ФРАГМЕНТНЫЕ МАКРОМУТАЦИИ

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

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

  1. Сохранение накопленного генного материала;

  2. Начальные полезности у всех хромосом после макромутаций должны быть соизмеримыми.

Эти условия выполняются в случае фрагментных макромутаций (ФМ). При ФМ процесс генетического поиска разбивается на участки, называемые циклами, каждый протяженностью C поколений. Макромутации выполняются по окончании каждого цикла и заключаются в переносе нечетных фрагментов очередной хромосомы текущего поколения в хромосому первого потомка, а четных фрагментов – в хромосому второго потомка. Остальные фрагменты потомков заполняются случайными значениями (аллелями) соответствующих управляемых параметров.

Сущность ФМ поясняет рис.3.

Рис.3. Фрагментные макромутации

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

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

Рис. 4. Сравнение траекторий поиска при применении (X=1111) и без применения (X=1011) фрагментных макромутаций в одной из тестовых задач

4. ТЕСТОВЫЕ ЗАДАЧИ

В качестве тестовых задач использовались NP-трудные задачи дискретной оптимизации:

  • многостадийная задача синтеза расписаний (SP – Scheduling Problem);

  • задача коммивояжера (TS – Traveling Salesman);

  • задача компоновки элементов в блоки (PP – Partitioning Problem).

В задаче SP требуется составить расписание минимальной стоимости Z при соблюдении временных ограничений для обслуживания n работ с их распределением во времени и по имеющимся машинам. Каждая работа проходит q стадий обслуживания, на каждой стадии для работы выбирается одна из mk машин, k=1,…q, общее число машин равно M. Заданы матрица P=[pij], где pij – время обслуживания i-й работы на j-й машине. Заданы также времена и стоимости переналадок машин, цены одного часа работы каждой машины, временные ограничения на завершение обслуживания каждой работы. Исходные данные тестовой SP: n=105, M=15, q=4. Для кодирования решений в SP использовался метод комбинирования эвристик. Эвристики различались правилами выбора работы и обслуживающей ее машины на очередном шаге синтеза расписания. Хромосома состояла из nq=420 генов.

В тестовой задаче TS заданы число городов n=120, представляемых в виде точек, и координаты каждого города, по которым определяется матрица D=[dij] расстояний между городами. Хромосомы имеют длину, равную n. Значениями генов были приоритеты городов на включение в маршрут, при кодировании частично использовался метод комбинирования эвристик.

В задаче PP заданы множества элементов и блоков и матрица D межэлементных связей. Требуется распределить элементы по блокам с минимизацией числа Z межблочных связей и соблюдением ограничения ekV, где ek – число элементов в k-м блоке, V – максимально допустимая загрузка одного блока. В тестовой задаче было принято V=25. К исходным данным относятся также число элементов n=200, число блоков m=10. Решения PP кодировались следующим образом. Хромосома состоит из n генов, i-й ген соответствует i-му элементу, значением (аллелем) i-го гена является номер блока, в который этот элемент помещен.

5. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

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

Результаты численных экспериментов представлены в таблице, в которой исследуемые методы обозначены четырехразрядным двоичным кодом x1,x2,x3,x4, причем x1 =1, если используется ФК; x2 =1, если применяется МР; x3=1 при применении ФМ; x4=1, если выполняется ФХ.

В задаче SP достигнутое минимальное значение F целевой функции фиксировалось после 480 смен поколений, что соответствует приблизительно T=100…120 тысячам вычислений целевой функции. Длина цикла C принималась равной 80 поколениям, размер популяции N=100, длина фрагментов L=7.

В задаче TS расчеты заканчивались после выполнения 200 тысяч оценок целевой функции, размер популяции N=60, Т=150, L=5.

В задаче PP были приняты следующие данные: длительность расчетов T=200000, N=100, C=80, L=4.

По полученным оценкам F целевой функции, представленным в колонках 6-9 таблицы, рассчитывались нормированные показатели полезности Kij исследуемых методов для задач SP, TS, PP:

Kij=(Fmaxi-Fij)/( Fmaxi-Fmini),

где Fmaxi, Fmini и Fij – максимальное, минимальное и полученное с помощью j-го метода значение целевой функции в i-й задаче, i=1,2,3. Общая полезность метода оценивалась усреднением показателей полезности по трем задачам. Полученные таким образом значения общей полезности методов в виде значений коэффициента Kfit приведены в последнем столбце таблицы.

Таблица

x1

x2

x3

x4

Целевая функция F

Kij

КГМ в задаче:

Kfit

SP

TS

PP

SP

TS

PP

1

1

1

1

1

21800

549

443

1

1

1

1

2

1

0

1

1

21878

554

549

0,79

0,81

0,50

0,70

3

1

1

0

1

21887

557

584

0,77

0,61

0,33

0,57

4

1

1

1

0

21990

557

559

0,49

0,69

0,44

0,54

5

1

0

1

0

21993

556

575

0,48

0,70

0,38

0,52

6

1

0

0

1

21959

557

613

0,57

0,69

0,20

0,47

7

1

1

0

0

22019

557

610

0,41

0,69

0,21

0,44

8

1

0

0

0

22063

560

612

0,30

0,58

0,20

0,36

9

0

0

1

0

22035

562

636

0,37

0,50

0,09

0,32

10

0

0

0

0

22049

567

654

0,33

0,31

0

0,21

11

0

0

1

1

22085

566

653

0,24

0,35

0,01

0,20

12

0

0

0

1

22174

575

655

0

0

0

0

6. ЗАКЛЮЧЕНИЕ

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

Литература

  1. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – Ростов-на-Дону: ООО «Ростиздат», 2004.

  2. Syswerda G. Uniform Crossover in Genetic Algorithms// Proceedings of the 3rd International Conference on Genetic Algorithms.  San Mateo Ca: Morgan Kaufmann Publications, 1989.

  3. De Jong K.A., Spears W.M. A Formal Analysis of the Role of Multi-Point Crossover in Genetic Algorithms// Annals of Mathematics and Artificial Intelligence, 1992.

  4. Prugel-Bennett A. The Mixing Rate of Different Crossover Operators// Foundations of Genetic Algorithms.  №6.  2001.

  5. Sastry K., Goldberg D., Kendall G. Genetic Algorithms. – http://citeseer.ist.psu.edu/cache/papers/cs2/258/

  6. Eiben A.E., Raue P-E., Ruttkay Zs. Genetic Algorithms with Multi-parent Recombination// In Proceedings of the 3d Conference on Parallel Problem Solving from Nature, Springer Verlag, 1994.

  7. Back T. Optimal Mutation Rates in Genetic Search// Proceedings 5th International Conference on Genetic Algorithms.  San Mateo Ca: Morgan Kaufmann Publications, 1993.

  8. Fogarty T. Varying the Probability of Mutation in Genetic Algorithm// Proceedings 3rd International Conference on Genetic Algorithms.  San Mateo Ca: Morgan Kaufmann Publications, 1989.

  9. Blickle T., Thiele L. A Comparison of Selection Schemes Used in Genetic Algorithms// TIK Report

/Papers/blickle_95.pdf

  1. Norenkov I.P., Goodman E.D. Solving Scheduling Problems via Evolutionary Methods for Rule Seqience Optimization// Soft Computing in Engineering Design and Manufacture, Springer Verlag, 1998.

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

  3. Норенков И.П. Исследование эффективности генетического метода с фрагментным кроссовером// Информационные технологии. – 2008. – №5. – С.26-29.



Скачать документ

Похожие документы:

  1. На правах рукописи (141)

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

    Исследование
    Федеральное государственное бюджетное учреждение науки «Институт биохимической физики им. Н.М.Эмануэля» Российской академии наук, заведующий лабораторией постгеномных молекулярно-биологических исследований
  3. На правах рукописи (163)

    Документ
    Федеральное государственное бюджетное учреждение «Медико-генетический научный центр» Российской академии медицинских наук, заведующий лабораторией ДНК-диагностики
  4. Балаганская Ольга Алексеевна полиморфизм y хромосомы у тюркоязычного населения алтая, саян, тянь-шаня и памира в контексте взаимодействия генофондов западной и восточной евразии 03. 02. 07 генетика автореферат

    Автореферат
    Защита состоится «14» июня 2011 г. в часов на заседании Диссертационного ученого совета Д 001.016.01 при Учреждении Российской академии медицинских наук Медико-генетическом научном центре РАМН (115478, Москва, ул.
  5. Краткий отчет о научной деятельности Учреждения Российской академии наук Уфимского научного центра ран за 2010 год Уфа-2011 г

    Публичный отчет
    В отчетном году институты Центра продолжали фундаментальные научные исследования в рамках 2 федеральных целевых научно-технических программ: «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы» (ИНК, ИБГ,

Другие похожие документы..