2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Генетический алгоритм
Сообщение27.02.2011, 01:01 
Модератор
Аватара пользователя


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

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

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

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

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

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение27.02.2011, 03:55 


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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение27.02.2011, 11:46 
Админ форума
Аватара пользователя


19/03/10
8952
 !  xcislav,
замечание за бессодержательное сообщение.

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение28.02.2011, 11:18 


06/11/09
35
Каир, но родом из России
Здравствуйте, я занимаюсь применением генетического алгоритма для построения расписания в многопроцессорной системе с частичным порядком. У меня есть некоторые соображения на счет Вашей задачи. Кроме того, я сравнивал эффективность ГА и алгоритма критического пути. Могу поделиться наблюдениями. Если Вы заинтересовались, пишите на адрес dmitry.kober@gmail.com или в скайп dmitry kober

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение28.02.2011, 16:36 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Sayid в сообщении #418243 писал(а):
Здравствуйте, я занимаюсь применением генетического алгоритма для построения расписания в многопроцессорной системе с частичным порядком. У меня есть некоторые соображения на счет Вашей задачи. Кроме того, я сравнивал эффективность ГА и алгоритма критического пути. Могу поделиться наблюдениями. Если Вы заинтересовались, пишите на адрес dmitry.kober@gmail.com или в скайп dmitry kober

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение03.03.2011, 22:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение06.03.2011, 16:15 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Утундрий в сообщении #419416 писал(а):
profrotter
Подробнее о первом алгоритме (до введения элитарных особей), пожалуйста. Он точно у Вас плодит потомков из "удачных" особей? Как у Вас реализован кроссинг?

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение08.03.2011, 00:19 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Утундрий в сообщении #419416 писал(а):
profrotter
...Он точно у Вас плодит потомков из "удачных" особей?...

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

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

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

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение08.03.2011, 09:33 
Заслуженный участник


19/07/08
1266
profrotter в сообщении #420499 писал(а):
Суть в том, что те же самые результаты можно получить случайным подобором параметров оптимизации: Генерируем ПС-число и пробуем заменить им первый параметр, рассчитываем показатель качества. Если имело место улучшение - принимаем новое значение параметра.
Как-то по работе разбирался в генетических алгоритмах. Основное, что вынес (и это по-моему достаточно чётко оговаривается во всех статьях, во всех мануалах) что на относительно простых функциях и небольшом наборе параметров генетические алгоритмы как правило хуже чем все "стандартные" методы. А потом приговаривают про то, что если параметров очень много или целевая функция очень плохая, то генетические алгоритмы могут работать лучше.
Хотя по работе, как через некоторое время выяснили те товарищи что этим генетическим алгоритмом неважно что искали, последовательный подбор параметров чтобы оказаться поближе к минимуму и потом тривиальная минимизация всех параметров сразу (когда мы уже знаем что недалеко от глобального минимума) чем-то типа сопряжённых градиентов даёт результаты намного лучше чем генетический алгоритм. Так что самому с ним играться не пришлось.

 Профиль  
                  
 
 
Сообщение04.04.2011, 13:35 


18/11/10
381
Мюнхен
profrotter в сообщении #417827 писал(а):
В связи с чем я пришёл к выводу, что генетические алгоритмы - это лишь яркая упаковка в которой преподносится банальная идея о случайном подборе параметров оптимизации.

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

 Профиль  
                  
 
 Re:
Сообщение09.04.2011, 13:00 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
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 итерации. А что такое элитная особь? - Особь которая из ПС-процесса выхватывала хорошие значение. Тогда спрашивается какая разница как будет организован сам ПС - процесс?

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

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение13.04.2011, 07:04 


18/11/10
381
Мюнхен
profrotter в сообщении #432791 писал(а):
Вам доводилось где-нибудь встречать рекомендации по выбору количества особей в зависимости от количества параметров задачи оптимизации?

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение13.04.2011, 10:19 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
kolas в сообщении #434256 писал(а):
Рекомендаций не встречал, но по личному опыту это десяток особей на ген. Если у нас хромосома, как в Вашем случае, состоит из 500 генов, то размер популяции будет 5000. Памяти это займет 8*500*5000 = 20000000 байт или 20 Мбайт, не так уж и много как кажется.
У меня 16 бит на параметр: $16\cdot 500\cdot 5000\approx 40$МБ. Когда то у меня был жёсткий диск всего 60МБ и это считалось очень и очень приличным :mrgreen: И ещё на каждой итерации алгоритма (для каждого поколения) функцию приспособленности придётся вычислить 5000 раз. Вообще впечатляющая плата за то, чтобы потом громко сказать, мол, я крут и моя программа использует генетический алгоритм, а вот он (показать пальцем) не крут, так как его программа использует ПС-подбор параметров. :mrgreen:

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

 Профиль  
                  
 
 Re: Генетический алгоритм
Сообщение14.04.2011, 13:02 


18/11/10
381
Мюнхен
profrotter в сообщении #434275 писал(а):
У меня 16 бит на параметр: $16\cdot 500\cdot 5000\approx 40$МБ

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group