Генетический алгоритм

[profrotter]

Следуя современным тенденциям разработал модуль многопараметрической оптимизации на основе генетического алгоритма 16 бит на параметр. При первом тестировании пытался найти отсчёты, соответствующие отсчётам некоторой известной функции на основе критерия минимума суммы квадратов отклонений и был искрене расстроен тем, что генетический алгоритм совершенно не спешит сходится при решении столь тривиальной задачи всего лишь на 100 отсчётов.
Ситуацию спасло применение элитарной стратегии. Была введена элитная особь, на которую не распространялась никакая селекция и которая забирала всякие значения параметров оптимизации, при условии, что это увеличивало функцию приспособленности. Был искренне расстроен тем, что о плохой сходимости генетического алгоритма в литературе предпочитают умалчивать. Генетический алгоритм с элитарной стратегией был применён для формирования реализаций эргодического случайного процесса по заданной плотности распределения вероятностей и корреляционной функции:

Для примера на рисунке: 300 отсчётов в реализации (параметров оптимизации), участвуют 6 особей и одна элитная, вероятность мутации 7%, среднее количество итераций 10, среднее время выполнения 4 секунды, условием остановки является превышение показателем качества уровня 95%.
Дальнейшие размышления привели меня к мысли о том, что использование элитарной стратегии ничем не отличается от элементарного подбора параметров оптимизации: действительно, случайно выбранные массивы данных ввергаются в ПСП - мясорубку, где трудно-предсказуемым образом изменяются, а элитарная особь выполняет функции отслеживания и сохранения хороших значений, которые в этой мясорубке могут появиться. Для подтверждения этой мысли я вообще исключил все операторы скрещивания и селекции, оставил только одну особь, которая в мутировала с большой вероятностью. Фактически такой подход означает случайный подбор параметров оптимизации. Такой алгоритм оказалася вполне работоспособным:

Для примера на рисунке: 300 отсчётов в реализации (параметров оптимизации), участвуют одна элитная особь, вероятность мутации 45%, среднее количество итераций 16, среднее время выполнения 4 секунды, условием остановки является превышение показателем качества уровня 95%.
Применение метода случайного подбора оказалось более эффективным в плане экономии временного ресурса и памяти при расчётах с более сложными функциями приспособленности, несмотря на бОльшее количество итераций.

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

Поделитесь практикой применения генетических алгоритмов для решения задач многопараметрической оптимизации.

Кто-нибудь сравнивал эффективность генетического алгоритма и простейший ПСП- подбор параметоров?

[xcislav]

Боже мой как классно это знать, непередаваемо! Я бы Вам обязательно ответил, если бы знал, но я лишь только бедный сисадмин живущий в мечтах)

[Toucan]

xcislav,
замечание за бессодержательное сообщение.

[Sayid]

Здравствуйте, я занимаюсь применением генетического алгоритма для построения расписания в многопроцессорной системе с частичным порядком. У меня есть некоторые соображения на счет Вашей задачи. Кроме того, я сравнивал эффективность ГА и алгоритма критического пути. Могу поделиться наблюдениями. Если Вы заинтересовались, пишите на адрес [e-mail] или в скайп dmitry kober

[profrotter]

Sayid в сообщении #418243 писал(а):

Здравствуйте, я занимаюсь применением генетического алгоритма для построения расписания в многопроцессорной системе с частичным порядком. У меня есть некоторые соображения на счет Вашей задачи. Кроме того, я сравнивал эффективность ГА и алгоритма критического пути. Могу поделиться наблюдениями. Если Вы заинтересовались, пишите на адрес [e-mail] или в скайп dmitry kober

Здравствуйте!
Что мешает рассказать здесь?
С алгоритмом критического пути не знаком. Если надумаете написать - о нём тоже кратко, если можно.

[Утундрий]

profrotter
Подробнее о первом алгоритме (до введения элитарных особей), пожалуйста. Он точно у Вас плодит потомков из "удачных" особей? Как у Вас реализован кроссинг?

[profrotter]

Утундрий в сообщении #419416 писал(а):

profrotter
Подробнее о первом алгоритме (до введения элитарных особей), пожалуйста. Он точно у Вас плодит потомков из "удачных" особей? Как у Вас реализован кроссинг?

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

[profrotter]

Утундрий в сообщении #419416 писал(а):

profrotter
...Он точно у Вас плодит потомков из "удачных" особей?...

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

Я даже готов заранее признать, что до введения элитарной стратегии мною было что - либо неправильно запрограммировано, дабы исключить попытки коллег направить усилия на поиск ошибок в моей программе. Как я писал программу - совершенно не суть. Суть в том, что те же самые результаты можно получить случайным подобором параметров оптимизации: Генерируем ПС-число и пробуем заменить им первый параметр, рассчитываем показатель качества. Если имело место улучшение - принимаем новое значение параметра. То же самое делаем и с другими параметрами. Это одна итерация алгоритма.

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

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

[nestoklon]

profrotter в сообщении #420499 писал(а):

Суть в том, что те же самые результаты можно получить случайным подобором параметров оптимизации: Генерируем ПС-число и пробуем заменить им первый параметр, рассчитываем показатель качества. Если имело место улучшение - принимаем новое значение параметра.

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

[kolas]

profrotter в сообщении #417827 писал(а):

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

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

[profrotter]

kolas в сообщении #431084 писал(а):

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

Давайте представим что у нас есть функция $N=500$ переменных:

$$F(y_0,...,y_{N-1})=\sum\limits_{n=0}^{N-1}(f(x_n)-y_n)^2$$

и мы ищем её глобальный минимум (фактически ищем набор чисел $y_n=f(x_n)$). И посмотрим на результаты, получаемые при 10 особях с селекцией методом колеса рулетки (чёрным показана сама функция $f(x)$, синим элитная особь, красным - самая сильная особь в текущей популяции(исключая элитную естественно)):

Думаете взято слишком малое количество особей? Возможно. Однако элитная особь уже дала решение задачи на 58 итерации. А что такое элитная особь? - Особь которая из ПС-процесса выхватывала хорошие значение. Тогда спрашивается какая разница как будет организован сам ПС - процесс?

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

Вам доводилось где-нибудь встречать рекомендации по выбору количества особей в зависимости от количества параметров задачи оптимизации?

[kolas]

profrotter в сообщении #432791 писал(а):

Вам доводилось где-нибудь встречать рекомендации по выбору количества особей в зависимости от количества параметров задачи оптимизации?

Рекомендаций не встречал, но по личному опыту это десяток особей на ген. Если у нас хромосома, как в Вашем случае, состоит из 500 генов, то размер популяции будет 5000. Памяти это займет 8*500*5000 = 20000000 байт или 20 Мбайт, не так уж и много как кажется.

[profrotter]

kolas в сообщении #434256 писал(а):

Рекомендаций не встречал, но по личному опыту это десяток особей на ген. Если у нас хромосома, как в Вашем случае, состоит из 500 генов, то размер популяции будет 5000. Памяти это займет 8*500*5000 = 20000000 байт или 20 Мбайт, не так уж и много как кажется.

У меня 16 бит на параметр: $16\cdot 500\cdot 5000\approx 40$МБ. Когда то у меня был жёсткий диск всего 60МБ и это считалось очень и очень приличным И ещё на каждой итерации алгоритма (для каждого поколения) функцию приспособленности придётся вычислить 5000 раз. Вообще впечатляющая плата за то, чтобы потом громко сказать, мол, я крут и моя программа использует генетический алгоритм, а вот он (показать пальцем) не крут, так как его программа использует ПС-подбор параметров.

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

[kolas]

profrotter в сообщении #434275 писал(а):

У меня 16 бит на параметр: $16\cdot 500\cdot 5000\approx 40$МБ

16 бит это 2 байта, соответственно 5 Мбайт, не так много.

Еще нужно правильно применять генетический алгоритм, и знать где он лучше подходит, а где лучше использовать градиентные методы.