Генетические Алгоритмы Оптимизации

[none 51]

Всем привет !

Может быть кто-нибудь может в двух словах объяснить суть генетических алгоритмов оптимизации? Как они примерно работают и какие классы задач позволяют решать ?

[GOLF_stream 309]

может, сначала имеет смысл расшифоровать термин "генетические алгоритмы оптимизации"? Генетика - это целая наука, считавшая одно время "продажной девкой империализма". Таким образом этот термин можно расшифровать как "продажные алгоритмы оптимизации". Но опять же остаётся неясным оптимизации ЧЕГО конкретно? Или не важно чего - доходов, материала, электроэнергии, маршрута транспорта?

[Islander 2]

может, сначала имеет смысл расшифоровать термин "генетические алгоритмы оптимизации"?

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

...

<noindex>http://articles.mql4.com/ru/133</noindex>

Или не важно чего - доходов, материала, электроэнергии, маршрута транспорта?

ИМХО, это второстепенно... главное уловить смысл (суть) алгоритма. А дальше уже можно примеряться к реальным объектам, например оптимизировать геометрию какой-нибудь деталюхи по каким-нить заявленым параметрам... причем получая экономию как по времени, так и по компьютерным ресурсам... (Хотя с другой стороны понятно желание коллег сделать разговор более предметным, обозначив интересующую область применения алгоритма...)

[none 51]

Спасибо. После обеда почитаю :) Мне так представляется, что это катастрофически полезная штука.

[none 51]

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

[SVB 188]

Судя по вашему профилю у вас должен быть опыт в Pro/E.

Там есть модуль BMX: <noindex>http://www.pts-russia.com/products/wildfire_bmx.htm</noindex>

Вам приходилось разбирать его возможности? Очень полезный модуль.

Вот тут есть простенькие примеры по решению задач с помощью BMX (правда по старой версии Pro/E): <noindex>http://sual.narod.ru/ProE/BehavModel/BehavModel.htm</noindex>

[vl 327]

Генетические алгоритмы предназначены для решения задач оптимизации.

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

Но есть сложность: большое число расчетов целевой функции.

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

Основные же принципы простые:

- ф-я должна быть однокритериальной

- не должно быть ограничений

- лишние критерии желательно превратить в ограничения

- ограничения желательно сверныть в ф-ю за счет штрафных ф-й

- чем меньше параметров, тем лучше

- если область поиска будет выпуклой, это хорошо

- если ф-я имеет только один экстремум - это хорошо

[vl 327]

Как я уже писал, ГА лучше работают для решения дискретных задач. Для непрерывных задач используем дискретизацию.

Основные особенности базового метода:

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

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

- вообще не гарантируют сходимости к оптимому (даже теоретически сходимость доказана только для одного вида ГА)

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

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

- вообще, когда параметров становиться много ГА становиться безразличным к их числу. Т.е. 100 пар-в или 200 уже имеет малое значение для сходимости, не как в классических методах, когда сложность растет линейно или хуже.

- целевая ф-я записывается как ф-я максимизации (ищем максимум), хотя преобразованиями можно переделать, но изначально так

- решение представляется в виде флагов 1 или 0 (есть свойство или нет) или кодируется этими 1 и 0 в более сложный код. Например при параметрическом поиске число может разбиваться на 16 вариантов, т.е. по 4 бита на число.

- область поиска может быть сколь угодно сложной, это легко учесть в целевой ф-и

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