Генетические алгоритмы: нужна помощь

[BE1]

Уважаемые господа, требуется Ваша помощь! Крайне необходимы примеры заданий по теме «генетические алгоритмы»: лабораторные работы, примеры, задачи, одним словом – все, что найдется! Тематика ограничивается следующими разделами:

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

Буду крайне признателен за ссылки, примеры, образцы, рекомендации!

[незваный гость]

Введение (с примером) — была статья в DDJ. Вполне неплохой разбор.

Коды Грея встречались в "Numerical recipes in ..." (глава 20.2)

[Macavity]

BE1 писал(а):

Буду крайне признателен за ссылки, примеры, образцы, рекомендации!

Можно посмотреть статью в MSDN Magazine:
http://msdn.microsoft.com/msdnmag/issue ... fault.aspx

[reader_st]

А вот я откопал и на русском

Рутковская Д., Пилиньский М., Рутковский Л.
Нейронные сети, генетические алгоритмы и нечеткие
системы: Пер. с польск. И. Д. Рудинского. - М.: Горячая линия -
Телеком, 2004. - 452 с: ил.

[maxal]

Вот тут куча материалов: http://www.basegroup.ru/neural/materials.htm

[Yuri Gendelman]

Насколько я понял, основной вопрос - это задачи и упражнения по теме.

1) Гладков Л.А., В.В.Курейчик, В.М.Курейчик. Генетические алгоритмы // М:Физматлит,2006.-320с.
(Я лично эту книгу не видел)

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

2) Лекция: Эволюционное моделирование и генетические алгоритмы:
http://www.intuit.ru/department/expert/intsys/12/3.html
Есть несколько вопросов для самоконтроля, задач и упражнений.

[незваный гость]

Вопрос в тему — встречалось ли кому-нибудь кодирование перестановок для генетического алгоритма? (Например, как представить клавиатуру?)

[Егор]

незваный гость писал(а):

Вопрос в тему — встречалось ли кому-нибудь кодирование перестановок для генетического алгоритма?

Очень многие решали генетическим алгоритмом задачу коммивояжёра.
google даёт 300 тысяч ссылок на запрос "genetic algorithms traveling salesman".

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

Конечно, можно в качестве генотипа взять просто разложение на транспозиции: каждый из $\frac{n(n-1)}{2}$ генов показывает, участвует ли в разложении соответствующая транспозиция. Но тогда близким фенотипам могут соответствовать далёкие генотипы.

[незваный гость]

Егор писал(а):

Очень многие решали генетическим алгоритмом задачу коммивояжёра.
google даёт 300 тысяч ссылок на запрос "genetic algorithms traveling salesman".

Коммивояжер может повторять путь, не так ли? Поэтому это не совсем кодирование перестановки.

Егор писал(а):

Конечно, можно в качестве генотипа взять просто разложение на транспозиции: каждый из $\frac{n(n-1)}{2}$ генов показывает, участвует ли в разложении соответствующая транспозиция. Но тогда близким фенотипам могут соответствовать далёкие генотипы.

Любопытно, об это я не думал. Но плотность такого представления мала по сравнению с минимально необходимой, ${\rm O}(n \log n)$. Есть и фундаментальный недостаток — в связи с неоднозначностью представления некоторые перестановки будут иметь «генетическую предрасположенность» к появлению, что нежелательно.

~~~~

Можно упростить задачу — рассмотреть вопрос о равномерном кодировании целого числа в диапазоне $0 .. n$, $n$ не степень двойки. После ее решения можно было бы воспользоваться «кнутовским» алгоритмом генерирования перестановки.

[Егор]

незваный гость писал(а):

Коммивояжер может повторять путь, не так ли? Поэтому это не совсем кодирование перестановки.

Задачу коммивояжёра понимаю как построение гамильтонова пути минимальной длины (товар такого качества, что встреча с прежними покупателями опасна).

незваный гость писал(а):

Можно упростить задачу — рассмотреть вопрос о равномерном кодировании целого числа в диапазоне $0 .. n$, $n$ не степень двойки. После ее решения можно было бы воспользоваться «кнутовским» алгоритмом генерирования перестановки.

Интересная задача.

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

Добавление. Видимо, в одну сторону связь просто необходима: близкие геномы должны приводить к близким значениям целевой функции. Иначе получим не генетический алгоритм, а Монте-Карло какое-то.

[fuzzy2006]

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

Документация к тулбуксу:
http://www.mathworks.com/access/helpdes ... ads_tb.pdf
+немного на русском:
http://matlab.exponenta.ru/genalg/index.php

И еще: avaxhome есть книженции на English по ГА, в некоторых из них есть готовые коды программ для написания ГА.

[fuzzy2006]

Цитата:

Генетические алгоритмы/Гладков Л.А., Курейчик В.В., Курейчик В.М.I

Оглавление здесь http://www.fml.ru/pdf/0510_c.pdf.
Если кто читал книгу, поделитесь впечатлениями. На каком языке программирования реализован ГА?