Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Подсветку кода сделайте пожалуйста, читать трудно. :)
И поправьте в статье к какому языку вы привязываетесь, видно что к Си, но… всякое бывает…
Зачем изобретать велосипед? есть же библиотеки для этого…
вот это место непойдет:
задача бинарным поиском найти максимальный индекс элемента в массиве wheel, значение которого меньше переменной index
а вы находите непонятно что, вы смотрите только элементы в середине отрезков, и если значение элемента в середине предыдущего отрезка меньше, а в середине следующего отрезка больше index, вы считаете, что середина предыдущего отрезка это наш искомый элемент и берете его индекс… но это неправильно, это не рулетка.
а еще эта штука иногда зацикливается, например если:
wheel = [1; 1000];
r = 1; l =0; index = 900; c =0;
то из вашего while мы никогда не выйдем
вот это место непойдет:
while (l!=r){
c = (l+r) >> 1;
if (wheel[c]<index){
l=c;
}else{
r=c;
}
}
задача бинарным поиском найти максимальный индекс элемента в массиве wheel, значение которого меньше переменной index
а вы находите непонятно что, вы смотрите только элементы в середине отрезков, и если значение элемента в середине предыдущего отрезка меньше, а в середине следующего отрезка больше index, вы считаете, что середина предыдущего отрезка это наш искомый элемент и берете его индекс… но это неправильно, это не рулетка.
а еще эта штука иногда зацикливается, например если:
wheel = [1; 1000];
r = 1; l =0; index = 900; c =0;
то из вашего while мы никогда не выйдем
«ложим их в массив.»
Неужели теперь так можно говорить/писать?
Неужели теперь так можно говорить/писать?
Можете пояснить, какую роль в вашем коде играют переменные, которые вы называете innerOffset и outerOffset и во всех местах используете одинаковым способом? Почему они являются результатами операций от деления на длину лонга в битах и взятия остатка, но используются для сдвига маски и указания индекса в массиве лонгов, из которых состоит геном?
Биты в гене храняться в таком виде (в данном случае для простоты считаю, что кол-во бит, отведенных под long, равно 8):
Если нам нужно получить доступ к 15 биту, то outerOffset будет указывать в каком long'е хранится бит, а innerOffset в какой позиции в long'e стоит этот бит.
А бинарные сдвиги и && заменяют целочисленное деление и взятие остатка от деления, так как выполняются быстрее.
Если нам нужно получить доступ к 15 биту, то outerOffset будет указывать в каком long'е хранится бит, а innerOffset в какой позиции в long'e стоит этот бит.
int index = 15;
outerOffset = index / LENGTH_OF_LONG; // == 15/8 == 1
innerOffset = index % LENGTH_OF_LONG - 1; // == 15 % 8 - 1 == 7 - 1 == 6 (!)нумерация начинается с 0А бинарные сдвиги и && заменяют целочисленное деление и взятие остатка от деления, так как выполняются быстрее.
Насколько я знаю, в генетических алгоритмах мутация необходима, иначе в общем случае алгоритм, хоть и сходится, но не факт, что к решению. Поэтому думаю, что нет необходимости в
Поправьте меня, если не прав.
private boolean useMutation; //Использовать мутацюПоправьте меня, если не прав.
Насколько я помню в DE алгоритмах у нас 3 вероятности:
probability pi_1: z1[i] < — N(0, sigm1) else z1[i] < — 0
probability pi_2: z2[i] < — N(0, sigm2) else z2[i] < — 0
probability pi: NEW_POPULATION(p, i) = POPULATION(c1, i) + (F + z1) * (POPULATION(c2, i) — POPULATION(c3, i) + z2) else NEW_POPULATION(p, i) = POPULATION(c1, i)
тоесть с вероятностями pi_1, pi_2 генерируются вектора характеризающие мутацию, и с вероятностью pi мутация переносится в следующее поколение, собственно вопрос:
Подскажите, где у вас pi_1, pi_2 или я описываю нечто другое?
probability pi_1: z1[i] < — N(0, sigm1) else z1[i] < — 0
probability pi_2: z2[i] < — N(0, sigm2) else z2[i] < — 0
probability pi: NEW_POPULATION(p, i) = POPULATION(c1, i) + (F + z1) * (POPULATION(c2, i) — POPULATION(c3, i) + z2) else NEW_POPULATION(p, i) = POPULATION(c1, i)
тоесть с вероятностями pi_1, pi_2 генерируются вектора характеризающие мутацию, и с вероятностью pi мутация переносится в следующее поколение, собственно вопрос:
Подскажите, где у вас pi_1, pi_2 или я описываю нечто другое?
Я использую вариант проще: есть вероятность мутации, если random.nextDouble() > процентМутации, то один бит инвертируется.
Не могли бы вы подробно описать свой вариант? Или кинуть линку на описание?
Не могли бы вы подробно описать свой вариант? Или кинуть линку на описание?
Использовал алгоритм дифференциальной эволюции, только в качестве критерия остановки эволюции было задано число повторений. Идея в том что у нас есть некоторый вектор изменяя который нужно добиться оптимизации некоторой функции.
В процессе эволюции мы к имеющемуся вектору прибавляем еще 2 случайных вектора с некоторым потоянным смещением F
В процессе эволюции мы к имеющемуся вектору прибавляем еще 2 случайных вектора с некоторым потоянным смещением F
Я просто оставлю это здесь:
Ген репарации комплементарных повреждений ДНК в результате рентгеновского излучения у китайских хомячков
www.genepassport.ru/base?GenID=114
Ген репарации комплементарных повреждений ДНК в результате рентгеновского излучения у китайских хомячков
www.genepassport.ru/base?GenID=114
1. Количество орфографических и грамматических ошибок зашкаливает. «Ложим в массив», блин. Курите учебники русского языка.
2. Хромосома — это абсолютно не обязательно вектор из нулей и единиц.
3. Из п. 2 — операции селекции, скрещивания и мутации сильно зависят от конкретной задачи и стандартизированы быть не могут.
4. Перечисления и свитчи по ним для изменения поведения класса — «эта пять». Курите «Рефакторинг» Фаулера и SOLID.
5. index1, index2, fr1, fr2 — вообще без комментариев. Использовать именования типа target, source и так далее не судьба?
6. Терминология — откуда вы ее взяли?
Резюме — для студенческой/школьной лабораторки нормально, на пост для хабра не тянет.
2. Хромосома — это абсолютно не обязательно вектор из нулей и единиц.
3. Из п. 2 — операции селекции, скрещивания и мутации сильно зависят от конкретной задачи и стандартизированы быть не могут.
4. Перечисления и свитчи по ним для изменения поведения класса — «эта пять». Курите «Рефакторинг» Фаулера и SOLID.
5. index1, index2, fr1, fr2 — вообще без комментариев. Использовать именования типа target, source и так далее не судьба?
6. Терминология — откуда вы ее взяли?
Резюме — для студенческой/школьной лабораторки нормально, на пост для хабра не тянет.
> Поэтому я решил, что было бы неплохо написать класс-каркас для любого ГА.
Начал читать и тоже сразу захотелось спросить: Если захотелось создать каркас для любого ГА, так почему рассматривается только бинарное кодирование генов. С вещественным кодом идут лесом все эти наработки.
Начал читать и тоже сразу захотелось спросить: Если захотелось создать каркас для любого ГА, так почему рассматривается только бинарное кодирование генов. С вещественным кодом идут лесом все эти наработки.
Потому что бинарными генами можно представить любые данные. Генетическому алгоритму все равно, что значат эти 0 и 1. Это важно только для фитнесс функции.
Например: первые три бита — число, следущие (14*8) бит представляют собой строку из 14 символов, и в конце еще 2 бита, которые трактуются как 2 boolean'а.
В моей реализации фитнесс функции. Каждые 8 бит составляют число, таким образом в одном лонге хранится 8 чисел.
Например: первые три бита — число, следущие (14*8) бит представляют собой строку из 14 символов, и в конце еще 2 бита, которые трактуются как 2 boolean'а.
В моей реализации фитнесс функции. Каждые 8 бит составляют число, таким образом в одном лонге хранится 8 чисел.
И вот тут засада. В бинарном кодировании рекомендуют использовать такое кодирование, при котором изменение одного бита не приведет к радикальному изменению свойства гена (в терминах ГА — метрика хромосомы изменится незначительно). Поэтому рекомендуют при бинарном кодировании использовать код Грея, т.к. он более стабилен в этом отношении. И поэтому же кодирование битами вещественных параметров (float/double) вообще неприемлемо — эффект от мутаций да и от кроссовера будет слишком непредсказуемым/нестабильным. Представьте себе изменение показателя степени в два раза.
В ГА важна стабильность паттернов — близкие паттерны должны давать схожее поведение особи. А при двоичном кодировании флотов получится очень нестабильная эволюция.
В ГА важна стабильность паттернов — близкие паттерны должны давать схожее поведение особи. А при двоичном кодировании флотов получится очень нестабильная эволюция.
кодирование битами вещественных параметров (float/double) вообще неприемлемо — эффект от мутаций да и от кроссовера будет слишком непредсказуемым/нестабильным.
очень ценное замечание. спасибо.
Хотя в принципе и любой float можно закодировать, использую код Грея. Или это будет очень ресурсоемко?
В литературе написано, что кодек Бин <-> Грей действительно снижает производительность. Но как я понял, это в отношении к просто бинарному кодированию. Тут главный недостаток Грея и в то же время может и достоинство — квантование значений. Т.е. кодом Грея мы по сути снижаем количество значений, снижаем разрядность вещественного числа. Если я ничего не путаю.
С другой стороны при кодировании вещественными векторами разрядность ограничивается лишь выбранным представлением вещественного типа. Тут имеем у флотов/даблов плавающее квантование (из-за представления числа в виде целой части + дробной + мантиссы), либо меньший диапазон допустимых значений при использовании предстваления с фиксированной точкой. Таким образом пространсво поиска разрастается неимоверно. К тому же кросовер и мутация становятся арифметическими. Так что вещественное кодирование легче привязывается к задачам цифровой обработки сигналов, но более ресурсоемкая при прочих ваных условиях.
Однако бывает (как в моем случае), что вещественное кодирование позволяет резко сократить количество параметров (длину хромосом), что может дать ощутимый профит.
Мое словоблудство расценивайте как очередной довод о том, что универсальный фреймворк для ГА — слишком сложно и нецелесообразно. ИМХО.
С другой стороны при кодировании вещественными векторами разрядность ограничивается лишь выбранным представлением вещественного типа. Тут имеем у флотов/даблов плавающее квантование (из-за представления числа в виде целой части + дробной + мантиссы), либо меньший диапазон допустимых значений при использовании предстваления с фиксированной точкой. Таким образом пространсво поиска разрастается неимоверно. К тому же кросовер и мутация становятся арифметическими. Так что вещественное кодирование легче привязывается к задачам цифровой обработки сигналов, но более ресурсоемкая при прочих ваных условиях.
Однако бывает (как в моем случае), что вещественное кодирование позволяет резко сократить количество параметров (длину хромосом), что может дать ощутимый профит.
Мое словоблудство расценивайте как очередной довод о том, что универсальный фреймворк для ГА — слишком сложно и нецелесообразно. ИМХО.
Кодирование числа с плавающей точкой давно уже описано в литературе. Если коротко, то выбирается допустимый диапазон значений float, разбивается на N интервалов таким образом, чтобы два соседних интервала давали приблизительно одинаковое значение фитнес-функции. Тогда число с плавающей точкой однозначно отображается в номер интервала. И наоборот, по номеру интервала можно вернуться к значению с плавающей точкой. Теоретически N можно сделать бесконечно большим, чтобы дискретность числа с плавающей точкой была незаметна, но тогда увеличивается длина хромосомы, что увеличивает алгоритмическую сложность задачи. Поэтому N выбирается с умом.
Теперь о практике. Я реализовывал генетический алгоритм применительно к дискретной задаче о рюкзаке. Но я его вдоль и поперек исследовал и для непрерывных функций. Результаты превзошли все мои ожидания. Для сложных целевых функций генетический алгоритм всегда выдавал абсолютный экстремум. Если попытаться решать ту же задачу градиентным спуском, то хотя и не будет потерь на кодировании/декодировании хромосомы, но гарантии нахождения абсолютного экстремума нет.
Теперь о практике. Я реализовывал генетический алгоритм применительно к дискретной задаче о рюкзаке. Но я его вдоль и поперек исследовал и для непрерывных функций. Результаты превзошли все мои ожидания. Для сложных целевых функций генетический алгоритм всегда выдавал абсолютный экстремум. Если попытаться решать ту же задачу градиентным спуском, то хотя и не будет потерь на кодировании/декодировании хромосомы, но гарантии нахождения абсолютного экстремума нет.
> Можно сделать останов ГА не по кол-ву поколений, а по достижении какого-то значения
> ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.
Критериев останова разных тоже много и они тоже сильно зависят от конкретных задач.
> ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.
Критериев останова разных тоже много и они тоже сильно зависят от конкретных задач.
Привели бы парочку примеров, думаю никто б не отказался.
1. Кол-во поколений.
2. Истечение какого-либо реального времени.
3. Квадрат разности фитнесс-функций лучших особей двух последних поколений меньше заданного значения.
4. Все особи в поколении отличаются друг от друга в рамках заданной погрешности.
5. Фитнесс-функция достигла некоего заданного значения (не всегда нужно оптимальное решение, иногда хватает «достаточного»).
и т. д.
2. Истечение какого-либо реального времени.
3. Квадрат разности фитнесс-функций лучших особей двух последних поколений меньше заданного значения.
4. Все особи в поколении отличаются друг от друга в рамках заданной погрешности.
5. Фитнесс-функция достигла некоего заданного значения (не всегда нужно оптимальное решение, иногда хватает «достаточного»).
и т. д.
А где практика, если это решение стандартной абстрактной задачи ;).
Копипаста вам из вики:
Генетические алгоритмы применяются для решения следующих задач:
Оптимизация функций
Оптимизация запросов в базах данных
Составление расписаний
Игровые стратегии
…
Алгоритм крайне просто применить к этим практическим задачам, надо только задать параметры алгоритма и интерпретировать результат.
Генетические алгоритмы применяются для решения следующих задач:
Оптимизация функций
Оптимизация запросов в базах данных
Составление расписаний
Игровые стратегии
…
Алгоритм крайне просто применить к этим практическим задачам, надо только задать параметры алгоритма и интерпретировать результат.
Вот как раз ради этого я и полез читать данную статью. Мне кажется, то, что описано тут — можно найти в других статьях/учебниках и закодить с минимальными усилиями. А вот собственно то, как генетический алгоритм помогает решить именно задачу коммивояжера (или любую другую задачу), как геном влияет на алгоритм решения — непонятно.
Ясно, что какого-то общего влгоритма не существует, и для каждой задачи параметры будут обозначать что-то свое, но мне кажется, что как раз такая привязка ГА к конкретной задаче и есть самое интересное и полезное.
Ясно, что какого-то общего влгоритма не существует, и для каждой задачи параметры будут обозначать что-то свое, но мне кажется, что как раз такая привязка ГА к конкретной задаче и есть самое интересное и полезное.
С вами согласен, тоже хотел бы прочесть про решение конкретной задачи с помощью этого метода на хабре
Вот пример моего использования ГА. Но там ГА с вещественным кодированием — сильно отличается от того что здесь изложено.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Генетические алгоритмы. От теории к практике