Комментарии 36
Подсветку кода сделайте пожалуйста, читать трудно. :)
0
И поправьте в статье к какому языку вы привязываетесь, видно что к Си, но… всякое бывает…
0
НЛО прилетело и опубликовало эту надпись здесь
Зачем изобретать велосипед? есть же библиотеки для этого…
вот это место непойдет:
задача бинарным поиском найти максимальный индекс элемента в массиве 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 мы никогда не выйдем
+1
«ложим их в массив.»
Неужели теперь так можно говорить/писать?
Неужели теперь так можно говорить/писать?
-1
Можете пояснить, какую роль в вашем коде играют переменные, которые вы называете innerOffset и outerOffset и во всех местах используете одинаковым способом? Почему они являются результатами операций от деления на длину лонга в битах и взятия остатка, но используются для сдвига маски и указания индекса в массиве лонгов, из которых состоит геном?
0
Биты в гене храняться в таком виде (в данном случае для простоты считаю, что кол-во бит, отведенных под 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
А бинарные сдвиги и && заменяют целочисленное деление и взятие остатка от деления, так как выполняются быстрее.
0
Насколько я знаю, в генетических алгоритмах мутация необходима, иначе в общем случае алгоритм, хоть и сходится, но не факт, что к решению. Поэтому думаю, что нет необходимости в
Поправьте меня, если не прав.
private boolean useMutation; //Использовать мутацю
Поправьте меня, если не прав.
0
Насколько я помню в 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 или я описываю нечто другое?
0
Я использую вариант проще: есть вероятность мутации, если random.nextDouble() > процентМутации, то один бит инвертируется.
Не могли бы вы подробно описать свой вариант? Или кинуть линку на описание?
Не могли бы вы подробно описать свой вариант? Или кинуть линку на описание?
0
Использовал алгоритм дифференциальной эволюции, только в качестве критерия остановки эволюции было задано число повторений. Идея в том что у нас есть некоторый вектор изменяя который нужно добиться оптимизации некоторой функции.
В процессе эволюции мы к имеющемуся вектору прибавляем еще 2 случайных вектора с некоторым потоянным смещением F
В процессе эволюции мы к имеющемуся вектору прибавляем еще 2 случайных вектора с некоторым потоянным смещением F
0
Я просто оставлю это здесь:
Ген репарации комплементарных повреждений ДНК в результате рентгеновского излучения у китайских хомячков
www.genepassport.ru/base?GenID=114
Ген репарации комплементарных повреждений ДНК в результате рентгеновского излучения у китайских хомячков
www.genepassport.ru/base?GenID=114
0
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. Терминология — откуда вы ее взяли?
Резюме — для студенческой/школьной лабораторки нормально, на пост для хабра не тянет.
+2
> Поэтому я решил, что было бы неплохо написать класс-каркас для любого ГА.
Начал читать и тоже сразу захотелось спросить: Если захотелось создать каркас для любого ГА, так почему рассматривается только бинарное кодирование генов. С вещественным кодом идут лесом все эти наработки.
Начал читать и тоже сразу захотелось спросить: Если захотелось создать каркас для любого ГА, так почему рассматривается только бинарное кодирование генов. С вещественным кодом идут лесом все эти наработки.
0
Потому что бинарными генами можно представить любые данные. Генетическому алгоритму все равно, что значат эти 0 и 1. Это важно только для фитнесс функции.
Например: первые три бита — число, следущие (14*8) бит представляют собой строку из 14 символов, и в конце еще 2 бита, которые трактуются как 2 boolean'а.
В моей реализации фитнесс функции. Каждые 8 бит составляют число, таким образом в одном лонге хранится 8 чисел.
Например: первые три бита — число, следущие (14*8) бит представляют собой строку из 14 символов, и в конце еще 2 бита, которые трактуются как 2 boolean'а.
В моей реализации фитнесс функции. Каждые 8 бит составляют число, таким образом в одном лонге хранится 8 чисел.
0
И вот тут засада. В бинарном кодировании рекомендуют использовать такое кодирование, при котором изменение одного бита не приведет к радикальному изменению свойства гена (в терминах ГА — метрика хромосомы изменится незначительно). Поэтому рекомендуют при бинарном кодировании использовать код Грея, т.к. он более стабилен в этом отношении. И поэтому же кодирование битами вещественных параметров (float/double) вообще неприемлемо — эффект от мутаций да и от кроссовера будет слишком непредсказуемым/нестабильным. Представьте себе изменение показателя степени в два раза.
В ГА важна стабильность паттернов — близкие паттерны должны давать схожее поведение особи. А при двоичном кодировании флотов получится очень нестабильная эволюция.
В ГА важна стабильность паттернов — близкие паттерны должны давать схожее поведение особи. А при двоичном кодировании флотов получится очень нестабильная эволюция.
0
кодирование битами вещественных параметров (float/double) вообще неприемлемо — эффект от мутаций да и от кроссовера будет слишком непредсказуемым/нестабильным.
очень ценное замечание. спасибо.
Хотя в принципе и любой float можно закодировать, использую код Грея. Или это будет очень ресурсоемко?
0
В литературе написано, что кодек Бин <-> Грей действительно снижает производительность. Но как я понял, это в отношении к просто бинарному кодированию. Тут главный недостаток Грея и в то же время может и достоинство — квантование значений. Т.е. кодом Грея мы по сути снижаем количество значений, снижаем разрядность вещественного числа. Если я ничего не путаю.
С другой стороны при кодировании вещественными векторами разрядность ограничивается лишь выбранным представлением вещественного типа. Тут имеем у флотов/даблов плавающее квантование (из-за представления числа в виде целой части + дробной + мантиссы), либо меньший диапазон допустимых значений при использовании предстваления с фиксированной точкой. Таким образом пространсво поиска разрастается неимоверно. К тому же кросовер и мутация становятся арифметическими. Так что вещественное кодирование легче привязывается к задачам цифровой обработки сигналов, но более ресурсоемкая при прочих ваных условиях.
Однако бывает (как в моем случае), что вещественное кодирование позволяет резко сократить количество параметров (длину хромосом), что может дать ощутимый профит.
Мое словоблудство расценивайте как очередной довод о том, что универсальный фреймворк для ГА — слишком сложно и нецелесообразно. ИМХО.
С другой стороны при кодировании вещественными векторами разрядность ограничивается лишь выбранным представлением вещественного типа. Тут имеем у флотов/даблов плавающее квантование (из-за представления числа в виде целой части + дробной + мантиссы), либо меньший диапазон допустимых значений при использовании предстваления с фиксированной точкой. Таким образом пространсво поиска разрастается неимоверно. К тому же кросовер и мутация становятся арифметическими. Так что вещественное кодирование легче привязывается к задачам цифровой обработки сигналов, но более ресурсоемкая при прочих ваных условиях.
Однако бывает (как в моем случае), что вещественное кодирование позволяет резко сократить количество параметров (длину хромосом), что может дать ощутимый профит.
Мое словоблудство расценивайте как очередной довод о том, что универсальный фреймворк для ГА — слишком сложно и нецелесообразно. ИМХО.
0
Кодирование числа с плавающей точкой давно уже описано в литературе. Если коротко, то выбирается допустимый диапазон значений float, разбивается на N интервалов таким образом, чтобы два соседних интервала давали приблизительно одинаковое значение фитнес-функции. Тогда число с плавающей точкой однозначно отображается в номер интервала. И наоборот, по номеру интервала можно вернуться к значению с плавающей точкой. Теоретически N можно сделать бесконечно большим, чтобы дискретность числа с плавающей точкой была незаметна, но тогда увеличивается длина хромосомы, что увеличивает алгоритмическую сложность задачи. Поэтому N выбирается с умом.
Теперь о практике. Я реализовывал генетический алгоритм применительно к дискретной задаче о рюкзаке. Но я его вдоль и поперек исследовал и для непрерывных функций. Результаты превзошли все мои ожидания. Для сложных целевых функций генетический алгоритм всегда выдавал абсолютный экстремум. Если попытаться решать ту же задачу градиентным спуском, то хотя и не будет потерь на кодировании/декодировании хромосомы, но гарантии нахождения абсолютного экстремума нет.
Теперь о практике. Я реализовывал генетический алгоритм применительно к дискретной задаче о рюкзаке. Но я его вдоль и поперек исследовал и для непрерывных функций. Результаты превзошли все мои ожидания. Для сложных целевых функций генетический алгоритм всегда выдавал абсолютный экстремум. Если попытаться решать ту же задачу градиентным спуском, то хотя и не будет потерь на кодировании/декодировании хромосомы, но гарантии нахождения абсолютного экстремума нет.
0
> Можно сделать останов ГА не по кол-ву поколений, а по достижении какого-то значения
> ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.
Критериев останова разных тоже много и они тоже сильно зависят от конкретных задач.
> ФитнессФункции, или когда разница средних значений ФитнессФункции поколений стала невелика.
Критериев останова разных тоже много и они тоже сильно зависят от конкретных задач.
0
Привели бы парочку примеров, думаю никто б не отказался.
0
1. Кол-во поколений.
2. Истечение какого-либо реального времени.
3. Квадрат разности фитнесс-функций лучших особей двух последних поколений меньше заданного значения.
4. Все особи в поколении отличаются друг от друга в рамках заданной погрешности.
5. Фитнесс-функция достигла некоего заданного значения (не всегда нужно оптимальное решение, иногда хватает «достаточного»).
и т. д.
2. Истечение какого-либо реального времени.
3. Квадрат разности фитнесс-функций лучших особей двух последних поколений меньше заданного значения.
4. Все особи в поколении отличаются друг от друга в рамках заданной погрешности.
5. Фитнесс-функция достигла некоего заданного значения (не всегда нужно оптимальное решение, иногда хватает «достаточного»).
и т. д.
0
А где практика, если это решение стандартной абстрактной задачи ;).
0
Копипаста вам из вики:
Генетические алгоритмы применяются для решения следующих задач:
Оптимизация функций
Оптимизация запросов в базах данных
Составление расписаний
Игровые стратегии
…
Алгоритм крайне просто применить к этим практическим задачам, надо только задать параметры алгоритма и интерпретировать результат.
Генетические алгоритмы применяются для решения следующих задач:
Оптимизация функций
Оптимизация запросов в базах данных
Составление расписаний
Игровые стратегии
…
Алгоритм крайне просто применить к этим практическим задачам, надо только задать параметры алгоритма и интерпретировать результат.
0
Вот как раз ради этого я и полез читать данную статью. Мне кажется, то, что описано тут — можно найти в других статьях/учебниках и закодить с минимальными усилиями. А вот собственно то, как генетический алгоритм помогает решить именно задачу коммивояжера (или любую другую задачу), как геном влияет на алгоритм решения — непонятно.
Ясно, что какого-то общего влгоритма не существует, и для каждой задачи параметры будут обозначать что-то свое, но мне кажется, что как раз такая привязка ГА к конкретной задаче и есть самое интересное и полезное.
Ясно, что какого-то общего влгоритма не существует, и для каждой задачи параметры будут обозначать что-то свое, но мне кажется, что как раз такая привязка ГА к конкретной задаче и есть самое интересное и полезное.
0
С вами согласен, тоже хотел бы прочесть про решение конкретной задачи с помощью этого метода на хабре
0
Вот пример моего использования ГА. Но там ГА с вещественным кодированием — сильно отличается от того что здесь изложено.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Изменить настройки темы
Генетические алгоритмы. От теории к практике