Библиотека генетических алгоритмов - часть 1

Written on 05 Января 2014.

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

•    Скачать исходный код библиотеки - 279 Кб
•    Скачать исходный код демонстрационных приложений - 85.81 Кб
•    Скачать демонстрационные приложения - 138.83 Кб
•    Скачать документацию библиотеки - 1.03 Мб
•    Последние версии библиотеки

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

Генетические алгоритмы применяются к набору возможных решений. Из-за случайности генетических алгоритмов найденные ими решения могут быть хорошими, плохими или недопустимыми [дефектными, ошибочными], поэтому нужен способ определения пригодности решения. Это делается путем назначения значения пригодности [или просто пригодности] решению. Хромосомы представляют решения в рамках генетического алгоритма. Двумя основными частями хромосом являются закодированное решение и его значение пригодности.

Хромосомы группируются в популяцию [набор решений], к которой применяется генетический алгоритм. На каждом шаге [генерации] генетический алгоритм выбирает хромосомы из популяции [обычно выбор основан на значении пригодности хромосомы] и объединяет их для выработки новых хромосом [потомства]. Хромосомы потомства образуют новую популяцию [или заменяют некоторые из хромосом в существующей популяции] в надежде, что новая популяция будет лучше предыдущих. Популяции отслеживают худшие и лучшие хромосомы и хранят дополнительные статистические данные, используемые генетическим алгоритмом для определения критерия остановки.

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

Схема – Представления хромосом [для максимизации функции с единственным параметром]

Схема - Представления хромосом [Задача коммивояжера]

Генетические алгоритмы вырабатывают новые хромосомы [решения] путем объединения существующих хромосом. Такая операция называется кроссовером. Операция кроссовера берет части кодировок решения из двух существующих хромосом [родителей] и объединяет их в одно решение [новую хромосому]. Эта операция зависит от представления хромосомы и бывает очень сложной. Хотя общие операции кроссовера просты в реализации, построение специализированных операций кроссовера для конкретных задач может значительно повысить производительность генетического алгоритма.

Схема – Примеры операций кроссовера

Прежде чем генетический алгоритм закончит выработку новой хромосомы, после чего он выполняет операцию кроссовера, он производит операцию мутации. Операция мутации вносит случайные, но маленькие, изменения в закодированное решение. Это предотвращает попадание всех решений в локальный оптимум и расширяет область поиска алгоритма. Мутации, равно как и операции кроссовера, зависят от выбранного представления.

Схема – Примеры операций мутации [мутация перестановки производится над первой хромосомой, а над второй производится операция инвертирования]

Операции кроссовера и мутации не всегда выполняются при выработке новой хромосомы. Если кроссовер не выполняется, генетический алгоритм вырабатывает новую хромосому путем копирования одного из родителей. Проценты операций кроссовера и мутации называются вероятностью кроссовера и вероятностью мутации, соответственно. Вероятность кроссовера обычно высокая [около 80%], а вероятность мутации относительно низкая [около 3%, но для некоторых задач более высокая вероятность дает лучшие результаты]. Более высокая вероятность мутации может превратить генетический алгоритм в алгоритм случайного поиска.

Последними операциями, определяемыми генетическими алгоритмами и используемыми для манипулирования хромосомами, являются операции пригодности и сравнители пригодности. Операция пригодности измеряет качество выработанного решения [хромосомы]. Эта специфичная для задачи операция сообщает генетическому алгоритму, что оптимизировать. Сравнители пригодности [как следует из самого названия] применяются для сравнения хромосом на основе их пригодности. Сравнитель пригодности говорит генетическому алгоритму, должен ли он минимизировать или максимизировать значения пригодности хромосом.

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

У операций селекции на базе значений пригодности есть проблема. В большинстве случаев будет выбираться хромосома со старшим значением пригодности, что вызовет проблемы, сходные с существующими. Во избежание этого значения пригодности можно масштабировать [преобразовать], чтобы уменьшить разность между старшей(ими) хромосомой(ами) и остальной популяцией [это позволяет выбрать другие хромосомы]. Есть много способов преобразования значения пригодности. Обычно они заключаются в применении математического преобразования к значению пригодности, но есть другие методы типа масштабирования на базе ранжирования, использующие ранг [основанный на непосредственных значениях пригодности хромосом] хромосомы в качестве масштабированного значения пригодности.

Схема – Масштабирование значения пригодности [показывает вероятность селекции хромосом]

Операция спаривания определяет, как выбранные хромосомы [родители] спариваются для скрещивания [скрещивание осуществляется путем выполнения операции кроссовера над спаренными родителями и применения операции мутации к вновь созданной хромосоме]. Эта операция позволяет лучше контролировать создание новых хромосом, но она может быть пропущена, и новые хромосомы могут создаваться, по мере того как операция селекции выбирает родителей из популяции.

Схема – Блок-схема операции спаривания

Схема – Блок-схема операции селекции без операции спаривания

На следующем шаге генетический алгоритм вводит новые хромосомы в популяцию. Хромосомы потомства могут образовать новую популяцию и заменить всю [предыдущую] популяцию [неперекрывающаяся популяция], или они могут заменить всего несколько хромосом в текущей популяции [перекрывающаяся популяция]. Для перекрывающихся популяций операция замены определяет, какие хромосомы удаляются [обычно худшие хромосомы] из текущей популяции, и какие хромосомы потомства вставляются. При замене хромосом генетический алгоритм может потерять лучшую хромосому(ы) [найденные до сих пор]. Во избежание этого в генетические алгоритмы вводится принцип элитизма. Элитизм гарантирует, что лучшая хромосома[ы] из текущего поколения сохранится в следующей генерации.

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