Comments 20
Хотелось бы уточнить, эта библиотека помогает найти «узкое горлышко» в алгоритме и указать на него? Из примера не совсем понятно, как именно указывается на узкое горлышко.
Если я не правильно понял предназначение библиотеки, прошу прощения.
Здорово, мне понравилось. Единственное, немного удивило, то что у вас мутации подвергаются только особи, полученные в результате скрещивания, причем судя по всему, без вариантов, то есть мутируют всегда. Не рассматривали вариант с мутацией произвольных особей?
И ещё, я думаю, надо уточнить, что ГА можно использовать не только собственно для минимизации функций, но и для решения других задач, где качество решения можно представить как функцию. Например, если говорить о прикладных задачах, можно оптимизировать какой-нибудь выпуск продукции нескольких видов для оптимизации прибыли.
Я так сделал по двум причинам. Во-первых, потому что так происходит в природе — в процессе жизни особи не мутируют (хотя я не биолог, может быть эта фраза не совсем корректна).
Во-вторых, когда-то давно на другом языке реализовывал генетический алгоритм, и там случайным образом могли мутироваться все особи. И тогда могла быть неприятная ситуация, когда мутировала лучшая особь, и тогда значение целевой функции ухудшалось.
> то есть мутируют всегда.
Не совсем так. Структура VecMutation мутирует каждую хромосому с заданной вероятностью, которая задается в конструкторе. Эта структура использует другие структуры, которые описывают, каким именно образом будет происходить мутация. Есть еще структура BitwiseMutation, которая мутирует хромосомы всегда, но она предназначена для использования вместе с VecMutation. Но, пожалуй, для ясности стоит сделать так, чтобы и BitwiseMutation мутировала с какой-то вероятностью.
> И ещё, я думаю, надо уточнить, что ГА можно использовать не только собственно для минимизации функций, но и для решения других задач, где качество решения можно представить как функцию. Например, если говорить о прикладных задачах, можно оптимизировать какой-нибудь выпуск продукции нескольких видов для оптимизации прибыли.
Я это и имел в виду, когда писал абзац про нейронные сети и применение в CAD. Может быть стоило описать более подробно примеры.
Во-первых, потому что так происходит в природе — в процессе жизни особи не мутируют (хотя я не биолог, может быть эта фраза не совсем корректна).
Насколько я понял (я тоже не биолог), мутацией называется любое изменение, которое может быть унаследовано. При этом википедия пишет, что
Спонтанные мутации возникают самопроизвольно на протяжении всей жизни организма в нормальных для него условиях окружающей среды с частотой около 10^{-9} — 10^{-12} на нуклеотид за клеточную генерацию организма.
Так что мутации бывают не только в результате скрещивания.
Во-вторых, когда-то давно на другом языке реализовывал генетический алгоритм, и там случайным образом могли мутироваться все особи. И тогда могла быть неприятная ситуация, когда мутировала лучшая особь, и тогда значение целевой функции ухудшалось.
Обычно ставять очень небольшую вероятность мутации, порядка 0,03. Кроме того, есть элитизм, когда мы можем "отложить" несколько хороших особей и не трогать их, а затем перенести их в следующее поколение.
Структура VecMutation мутирует каждую хромосому с заданной вероятностью, которая задается в конструкторе.
Теперь ясно, у вас оператор мутации выбирает, кого мутировать а кого нет. Здесь немного смущает то, что если мне понадобится поменять сам принцип отбора особей для мутации, то мне придется менять тот компонент, который отвечает за саму мутацию. Я бы, если честно, вынес выбор будущих мутантов как отдельный компонент.
Я это и имел в виду, когда писал абзац про нейронные сети и применение в CAD.
Теперь увидел, да. Кстати, думаю, стоит сказать, что особь не обязательно является числом. Это может быть какой-то сложный объект. Тогда процедура мутации у нас окажется сложнее, чем часто вспоминаемый метод смены одного бита на противоположный.
Например, их можно использовать для подбора весовых коэффициентов в нейронных сетях.
А у вас есть какие-нибудь ссылки на эту тему? А то те работы, что я находил сводились к тому, чтобы подобрать начальные веса сети, а затем учить её как обычно, обратным распространением. Причем здесь возникает вопрос о том, как считать приспособление для такого набора весов? Если мы дообучаем сеть каждый раз, чтобы оценить веса, то получается, что мы учим множество сетей, что не очень тянет на оптимизацию, а если мы проверяем выход сети на случайных весах не обучая её, то нет гарантий того, что сеть, обученная начиная с оптимальных весов в итоге окажется "оптимальной".
Да, это сделано так специально, потому что функции для мутации более-менее стандартные, а вот в том, кого мутировать, а кого нет, могут быть варианты. Поэтому так сделал, чтобы можно было этот алгоритм при желании менять. Самый простой вариант уже реализовал в библиотеке.
> Кстати, думаю, стоит сказать, что особь не обязательно является числом. Это может быть какой-то сложный объект. Тогда процедура мутации у нас окажется сложнее, чем часто вспоминаемый метод смены одного бита на противоположный.
Да, в библиотеке это подразумевается, поэтому те методы мутации, которые сейчас реализованы требуют числовые типы хромосом. Для более сложных типов нужно будет сделать свои операторы мутации, скрещивания и т.д.
> А у вас есть какие-нибудь ссылки на эту тему? А то те работы, что я находил сводились к тому, чтобы подобрать начальные веса сети, а затем учить её как обычно, обратным распространением.
Постараюсь найти дома книгу, где я об этом читал. Но по памяти там это упоминалось вскользь без особых подробностей.
Меня еще в свое время впечатлило другое применение ГА — подбор параметров самого ГА (размер популяции, вероятности скрещивания, мутации т.п.) для того, чтобы он сходился быстрее. То есть каждый расчет целевой функции — это запуск отдельного ГА со своими параметрами.
Да, это сделано так специально, потому что функции для мутации более-менее стандартные, а вот в том, кого мутировать, а кого нет, могут быть варианты. Поэтому так сделал, чтобы можно было этот алгоритм при желании менять. Самый простой вариант уже реализовал в библиотеке.
Так я вам и предлагаю, распилить это на две части: сама мутация и выбор того, кто мутирует. Из-за того, что мутации стандартны, их может предоставить библиотека. Выбор того, кто мутирует тоже может быть стандартным (случайный с некоторой веротяностью), так что и это библиотека может предоставить. Но у пользователя в этом случае появляется возможность менять одну часть не трогая другую.
Меня еще в свое время впечатлило другое применение ГА — подбор параметров самого ГА (размер популяции, вероятности скрещивания, мутации т.п.) для того, чтобы он сходился быстрее. То есть каждый расчет целевой функции — это запуск отдельного ГА со своими параметрами.
Как мне кажется, подобрать параметры некоторого алгоритма с помощью ГА идея довольно банальная. Точно также часто встречаются работы о выборе парамтеров нейронки (количество слоёв, количество нейронов и т.п. с ГА, суть та же самая). Здесь есть затык: предположим, мы для рассчёта приспособления запускаем ГА целиком и смотрим на результат, то получаеся, что получив оптимальные параметры ГА мы запускаем его снова, чтобы уже решить задачу, которая нам поставлена. При этом из-за вероятностной природы ГА нет гарантий, что мы получим в этом "эксплуатационном" запуске результаты, которые были получены на этапе выбора параметров, и которые как раз и сделали набор параметров победителем. Мы можем это оптимизировать, сохраняя те особи, которые были получены во время рассчёта приспособления ГА, чтобы, если окажется, что этот ГА оказался победителем, просто взять полученные им особи. Но тогда нам придётся где-то хранить эту историю особей, а если у нас очень много особей, мы можем упереться в ограничения по объёму. Так что тут не всё так просто :)
Сейчас как раз так и сделано. Создается структура VecMutation, которая определяет, будет ли мутироваться данная особь или нет. А конструктору VecMutation передается структура, которая определяет, каким образом будет мутироваться особь (если будет).
Сейчас как раз так и сделано. Создается структура VecMutation, которая определяет, будет ли мутироваться данная особь или нет. А конструктору VecMutation передается структура, которая определяет, каким образом будет мутироваться особь (если будет).
А. Теперь понял. А то я вот это:
Структура VecMutation мутирует каждую хромосому с заданной вероятностью, которая задается в конструкторе.
как то, что стуктура и выбирает, и мутирует, а оказалось, что она просто объединяет две разные чсти (выбор и мутацию) в одно целое.
Я имел в виду книгу, изданную в Бауманке: Комарцова Л.Г., Максимов А. В. «Нейрокомпьютеры: Учеб. пособие для вузов». Изд-во МГТУ им. Баумана, 2004.
Там есть глава, которая называется «Обучение нейронных сетей на основе генетического алгоритма». Хотя по сути в этой главе описываются генетические алгоритмы в общем виде и про применение к нейронным сетям сказано мало.
Полезная библиотека, спасибо!
Но есть вопросы по части реализации:
- Так ли необходимы типажи-объекты, нельзя было обойтись параметрическим полиморфизмом?
- Так ли необходимы именно упакованные типажи-объекты?
Если подправить эти моменты, то производительность может неплохо возрасти.
Хотелось оставить возможность в процессе работы менять объекты, которые отвечают за разные этапы алгоритма.
> Так ли необходимы именно упакованные типажи-объекты?
Изначально они были не упакованные, сейчас уже не помню, почему перешел на упакованные. Надо подумать, насколько это нужно.
> Если подправить эти моменты, то производительность может неплохо возрасти.
Для ускорения в первую очередь надо распараллелить алгоритм, а параллелиться по идее он должен достаточно легко.
Хотелось оставить возможность в процессе работы менять объекты, которые отвечают за разные этапы алгоритма.
А что подразумевается под "в процессе работы"? В процессе работы метода find_min?
А в более общем виде да, может быть даже удастся делать такие замены в процессе работы алгоритма. Хотя это уже скорее экзотика.
Optlib. Реализация генетического алгоритма оптимизации на Rust