Практическое применение эволюционных и генетических алгоритмов
Dmitry Bessonov
статьи по эволюционным вычислениям (больше всего по генетическим
алгоритмам), узнал о разных проблемах в этой области, например,
преждевременная сходимость, способы кодирования, методы селекции и т.
д. Но никак не могу найти, где эволюционные вычисления применяются на
практике. Известно, что они решают оптимизационные задачи, пусть будет
это, нахождение кратчайшего пути в графе или настройка нейронной сети.
Все же это направление является инструментарием, которым решают какие-
то задачи на практике. Буду рад любым примерам или указанному
источнику по этой области. Еще бы хотел узнать, можно но ли
направление выдвинуть на диссертационную тему? Спасибо.
yury...@gmail.com
Собственно вы уже фактически перечислили задачи :), т.к. поиск
оптимума, кратчайшего пути и настройку ИНС обычно не делают ведь
просто так. Есть, например, задача принятия решения в производстве или
поиск параметров математической модели некоторого реального процесса и
ее очень часто сводят к одной из известных задач оптимизации, которую
можно решать в том числе и с помощью ЭА.
По источникам могу посоветовать поискать труды конференций GECCO, CEC,
PPSN, FOGA, Evo*, а также посмотреть статьи в журналах Evolutionary
Computation, IEEE Transactions on Evolutionary Computation, можно еще
полистать Sigevolution, там печатают статьи более популярного уровня
от известных ученых.
Еще посмотрите ссылки в презентациях к семинару: http://qai.narod.ru/TomskWorkshop/index.html
Что касается диссертации, то если хотите написать хорошую диссертацию
по ЭА в России, то лично я бы советовал идти в эту тему только если
есть опытный научный руководитель, который адекватно знает, что
творится в мировой науке в этой области. Иначе просто на 108-й раз
изобретете велосипед, который был уже придуман лет 15-20 назад, ибо:
"Какая бы глупость тебе ночью ни приснилась или ты ни придумал, открой
Интернет, там минимум семь публикаций на эту тему уже есть" (академик
В.М. Полтерович)
А с ЭА у нас очень часто можно увидеть статьи, в которых
рассматриваются очень простые идеи без соответствующего литературного
обзора в наивной надежде, что никому до этого в голову ничего
подобного не пришло, в то время как в 70-90-х годах уже были сделаны
основные исследования свойств эволюционных алгоритмов и предложена
львиная доля операторов и различных моделей.
На мой взгляд, более плодотворным результатом будет "поход" от
реальной практической задачи. Тогда ЭА будут использоваться в качестве
того самого инструментария, и шансов сотворить что-то новое будет
больше, т.к. частных задач великое множество. Задачу нужно либо найти
самому, либо ее может предложить научный руководитель (что чаще
случается).
Если очень хочется заняться именно ЭА, то могу посоветовать посмотреть
алгоритмы оценки распределений (Estimation of Distribution
Algorithms), алгоритмы Байесовской оптимизации (Bayesian
Optimization), это тоже ЭА но с гораздо более интенсивным
использованием математики. Собственно от ЭА часто остается только
удобная терминология и образность представления. Как следствие эти
алгоритмы требуют весьма уверенного знания математики (теор. вер. и
мат. стат., лин. алгебра, многомерный анализ). Еще одной из интересных
задач может стать адаптация алгоритма CMA-ES для задач большой
размерности (с числом параметров больше 1000).
Юрий
Ilya Loshchilov
--
Вы получили это сообщение, поскольку подписаны на группу Эволюционные вычисления.
Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу ec...@googlegroups.com.
Чтобы отменить подписку на эту группу, отправьте сообщение по адресу ecetc+un...@googlegroups.com.
О дополнительных функциях можно узнать в группе по адресу http://groups.google.com/group/ecetc?hl=ru.
Alexander CHERNYAEV
Дмитрий, 2 года назад я защитил диссертацию, основной задачей которой было решение задач оптимального проектирования авиационных конструкций из композиционных материалов (КМ) с использованием генетических алгоритмов. По сей день применяю свой ГА (правда, уже более "навороченный", чем в диссере) для решения аналогичных задач. Идея состоит в том, что конструкции из КМ дискретны по своей природе. Стандартные алгоритмы в случае дискретных ПП и нелинейных
ограничений - работают посредственно, либо не работают вообще. Правда, есть проблемы с временем решения, ибо даже одна прямая задача часто решается достаточно долго. Здесь выход - эвристики+нейронные сети или поверхности отклика. По теме есть куча информации. Достаточно набрать в sciencedirect заветные "composite genetic". Удачи! Александр. --- Пн, 29.8.11, Dmitry Bessonov <1024m...@gmail.com> пишет:
|
|
|
Dmitry Novikov
Для большого числа задач, хорошо работают классические алгоритмы, в этом случае по эффективности они "сделают" любые эвристики (т.е. потребуется гораздо меньшее время для решения задачи). Однако, для ряда задач оптимизации, к которым сводятся реальные задачи, классические алгоритмы не работают (т.е. не получается найти правильное решение) в силу различных причин. В этом случае бывает целесообразно применять ЭА.
Одной из проблем не потерявших актуальности является "проклятие размерности" - резкое увеличение времени счета при увеличении размерности минимизируемого пространства. Для стохастических алгоритмов, к которым относятся ЭА, этот рост более медленный, чем для классических детерминированных (градиентные, Ньютоновские, ect.).
Пример: (Российская статья 2011 г.) при решении обратной задачи для химической кинетики (10 реакции в системе) время расчета "классическим методом" - методом развертки Пеано составляет у авторов недели и месяцы. С помощью "эвристик" задачи такого уровня решаются за время ~1ч.
Все во многом зависит от задачи. Золотой совет Юрия - нужно идти от задачи. Для начала, так же стоит выяснить решается ли она классическим методами и на сколько эффективно (или почему не решается).
Есть, например, задача принятия решения в производстве или
поиск параметров математической модели некоторого реального процесса и
ее очень часто сводят к одной из известных задач оптимизации, которую
можно решать в том числе и с помощью ЭА.
--
Best regards, B.Sc., Novikov D.V.
Department of Physical Chemistry
Tomsk State University, Tomsk, Russia
Dmitry Novikov
По поводу нейросетей, вы имеете в виду использовать их в качестве модели, аппроксимирующей решение прямой задачи?
Есть большое число обратных задач для громоздких линейных и нелинейных ДУЧП требующих мелких сеток.
Было бы более чем заманчиво не решать каждый раз для вычисления невязки двух/трех-мерные сеточные задачи (и так трудоемкие и долгие), а получить значение из черного ящака/аппроксиматора. Однако, на сколько возможна аппроксимация, скажем, решения нелинейных нестационарных параболических уравнений, в зависимости от параметров и входных данных?
. Правда, есть проблемы с временем решения, ибо даже одна прямая задача часто решается достаточно долго. Здесь выход - эвристики+нейронные сети или поверхности отклика.
Alexander CHERNYAEV
Дмитрий, да, Вы правильно меня поняли: идея состоит в использовании НС в качестве аппроксиматора. Безусловно, могут быть задачи, где даже такой подход окажется чересчур трудоемким или неподходящим по ряду других причин. Если говорить за себя, то я вполне успешно применяю его для решения своих, чисто прикладных, задач. Кроме того, эта идея (ГА+НС) уже несколько лет как реализована в промышленном ПО для МКЭ-анализа. Возьмите, например, DesignXplorer в ANSYS. Там, правда ГА не
работает с дискретными ПП, поэтому приходится присоединять к ANSYS свою реализацию. Александр.
|
|
|
Dmitry
ситуации лучше всего отталкиваться от задачи, но не всегда легко её
подобрать по силам, чтобы довести до конечного результата. Из
источников уже составил список направлений, буду делать отбор.
Когда искал применение ГА, то мне попалась интересная статься
http://kerneltrap.org/node/4493 - там описано использование ГА при
настройки планировщика в Linux и уже достаточно давно (2005 год).
Интересно, как сейчас обстоят дела с ГА в ядре? Если что найду по этой
теме, поделюсь.