Вопрос про генетическую оптимизацию

Это жесть какая-то, Википедию почитал?)

Насколько я понял из рассказа профессора на прошлой неделе:
1) Особь — набор управляющих воздействий (переменных)
2) Скрещивание или crossing-over — вероятность выбрать N-ного родителя (не понял что за бред)
3) Мутация — Вероятность изменения одной из управляющих переменных на какую-либо другую (я так понял противоположную)

Сильно не пинать, я лишь слушал лекцию :)))

Марсель, это твое имя или что? Как-то не обычно обращаться просто.
У тебя математическое образование?

мозг больно.

Основные термины, изпользуемые при генетической оптимизации, доступным языком изложены в шапке темы по ссылке support.tsresearchgroup.com/viewtopic.php?t=242

Смотри как бы под эту генетическуя оптимизацию не попали твои собственные гены. Комп тебе напишет: «Генетически для торговли на рынке Вы не пригодны.» :)))

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

Теперь нужно получить новые значения параметров. Для этого используются операторы скрещивания и мутации. Выглядит это так — каждая пара параметров представляется в двоичном виде (или его разновидности — в коде Грэя). При скрещивании параметры обмениваются произвольными небольшими участками нулей и единиц:

было 10010111-00101010
стало 10001111-00100110
(переставили в каждом группу из двух бит)

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

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

В первом приближении так.

1)Размер популяции это общее количество всевозможных вариантов решений из которых надо выбрать лучшее — ранжировать по приспособленности. Более высокая численность популяции повышает вероятность того, что мы найдем хорошее решение, но при более высокой численности требуется
большее время обработки. Варианты решений закодированы в двоичном виде в виде битовых строк
например десятичное 13 в виде 01101.
Эти значения из двоичного вида преобразуются в десятичный которые используются для задания целевой функции. Это проделывается для всех вариантов решений и значения целевой функции для них сохраняются(Важно: значения целевой функции должно быть неотрицательными)
2)Коэффициент скрещивания(вероятность кроссовера).
Как это работает и зачем это надо? Алгоритм выбирает два случайных числа в интервале от 0 до 1 нужные для определения какими будут, два родителя из популяции которые ранжированы по приспособленности(этот процесс я неописал).
Кроссовер: Последовательно формируется каждый бит ребенка(родители в двоичном коде) — нового варианта решения популяции. Начинают с копирования первого бита первого родителя в первый бит ребенка. Одновременно с этим генерируется случайное число. Если это случайное число оказывается меньше или равно вероятности кроссовера, деленной на длину гена, то переключаемся на копирование битов от другого родителя. Пример: если длина гена равна 36 и используемая нами вероятность кроссовера равна 0.6, то для переключения на копирование кода другого родителя в последующих битах, генеририруемое при каждом бите случайное число должно быть меньше 0.6/36, или 0.01667. Это продолжается до тех пор пока все биты не будут скопированы в коде ребенка. Данную операцию нужно проделать для всех новых членов популяции.Обычно вероятность кроссовера(перекрестной рекомбинации) находится в интервале от 0.6-0.9. Так, вероятность кроссовера 0.9 означает что
шансы возникновения кроссовера у ребенка будут равны 90%, в среднем; то есть 10% шансов будет за то, что ребенок будет точной копией одного из родителей.
3) Коэффициент мутации(вероятность мутации). Попутно с копированием каждого бита родителя в бит ребенка генерируется второе случайное число. Если это случайное число оказывается меньше или равно вероятности мутаций, то данный бит инвертируется. То есть, бит бывший 0 у родителя,
становится 1 у ребенка, и наоборот. Мутация помогает сохранить разнообразие в популяции.
Вероятность мутации обычно должна быть невелика(=0.001), иначе алгоритм вырождается в случайный
поиск. Однако по мере приближения алгоритма к оптимальному варианту, мутация приобретает все
большее значение, ибо кроссовер не может сохранить генетическое разнообразие в столь локализованном объеме (n+1)- мерного пространства
4)Количество поколений- то количество повторяющих вычислений, которое необходимо чтоб наилучшее
значение целевой функции не было превзойдено.

дааа… трансгенная мутация… и простидижитация :)))

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

Такая ситуация была в проге ищущую оптимальную позу,
м.б. у кого-то есть более красивое решение, чем было найдено?

А для чего Вы хотите ее применять? Если для ускорения оптимизации систем с кучей параметров, то лучше «забейте» — с вероятностью 0,999 получите подгонку.

ГА это поиск локальных экстремумов фитнесс-функции. Главный недостаток, что они локальные)) Т.е. если эксремумов несколько, то он может случайно найти один или несколько локальных. И неточно экстремум, а в окресности. Параметры 1-4 вляют на скорость поиска эктремума и возможно их кол-во.
Главное не оптимизация, а подтверждение робастности найденных параметров. Т.е. чтобы «хорошие» характеристики системы сохранялись в будущем, а нетолько на истории. Это уже неточная наука, а набор экспертных методов. И ГА может тут тоже пригодится при правильном применении.