Нелинейная многомерная оптимизация — это просто. Часть 2. Генетический алгоритм




Генетический алгоритм поиска решения. Описание и пример реализации. Функция нахождения решения как всегда универсальна — можете, не допиливая, брать и пользоваться.

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

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

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

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

Когда количество возможных размножений достигнуто и родилось ровно назначенное количество детей, популяцию нужно сократить. Процесс очень простой — сортируем особи по целевой функции и всех лишних … теряем. Без похорон и салютов.

Дальше при необходимости можно устроить нашим особям мутацию — то есть взять случайное число случайных генов (переменных) у случайных особей и инициировать их заново случайными значениями. Интенсивность мутаций — также один из параметров алгоритма.

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

 

Теперь сформулирую этапы работы алгоритма:

1. Формирование случайной начальной популяции возможных решений.

2. Оценка «приспособленности особей» — вычисление целевой функции.

3. Оценка вероятностей размножения в популяции.

4. Размножение путем случайной рекомбинации частей геномов двух особей. Количество размножений фиксировано параметром поиска решения. Вероятность участия в размножении особи тем больше, чем ближе значение целевой функции к оптимальному.

5. Рассчитываем целевые функции для вновь рожденных особей.

6. Уменьшаем размер популяции до заданного сортировкой по значению целевой функции и отсечением «лишних», наименее приспособленных.

7. Проверяем сходимость решения и количество поколений. Если условие прекращения алгоритма достигнуто — выход и возврат лучшей «особи». Если нет — переход к следующему шагу.

8. Если необходимо по параметрам решения — проводим мутации, изменяя случайное количество генов в случайном количестве особей на случайные значения из ОДЗ. Вычисляем целевые функции для мутировавших особей.

9. Возврат к шагу 3.

 

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

Лично я применяю генетический алгоритм там, где ОДЗ переменных выражено дискретными рядами чисел и целевая функция имеет прерывистый характер. Классический пример — задача коммивояжера. Решение всегда состоит из одинакового числа ребер графа, по которым должен пройти коммивояжер, а набор возможных маршрутов для каждого этапа пути (переменной) ограничен возможными вершинами графа, еще не посещенными на предыдущих шагах. Целевая же функция (затраты на передвижение), очевидно, также дискретна, так как состоит из возможных оценок возможных путей коммивояжера, а не определена непрерывно на каком-либо отрезке. В таком случае ее невозможно продифференцировать и нет функциональных критериев спуска в минимум.

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

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

Функция для поиска решения в приложенной обработке, как обычно универсальна. Можете копипастить и пользоваться. Описание аргументов в комментах к функции. Ну и пример решения!:)

Теперь использованная литература и что вообще почитать:

Т.В. Панченко «Генетические алгоритмы». Издательский дом «Астраханский университет» 2007 

Предложения, замечания, пожелания и критику прошу, как обычно, в комментарии.

8 Comments

  1. unpete

    Возможно, стоило дать читателям ссылку на PGAPACK — там много полезного.

    Однако качество самого решения, далеко от идеала

    Для получения качественного решения, необходима достаточно длительная эволюция. Триллионы циклов внутри 1С будут рассчитаны неприемлемо долго. Качество кроссовера и мутатора, так же, имеют значение.

    IMHO, критиковать генетику на основании 1С-ной реализации не совсем справедливо.

    Reply
  2. dusha0020

    (1) unpete, Триллионы поколений это да. Но с другой стороны где критерии «качественности» решения? Разве они объективны? Задумайтесь над тем, что сформулировать критерии окончания работы генетического алгоритма это как сформулировать критерии прекращения эволюции потому что мы вывели идеальную особь. Приемлемость решения как и качество получившихся в процессе эволюции особей вещь сугубо субъективная.

    С другой стороны раз уж мы на инфостарте то и задачи описываем применительно к 1С. Вот и моя критика это субъективное видение способности генетического алгоритма решать прикладные задачи на платформе 1С за приемлемое время.

    Но с другой стороны не могу не согласиться с Вами. 1С это вообще не платформа для решения сложных вычислительных задач, поэтому критиковать с точки зрения соотношения качество решения / быстродействие на 1С можно вообще все. Методы оптимизации от этого, естественно, не становятся хуже, как и 1С не начинает считать быстрее:)

    Так что все мои выводы, естественно, с оговорками на производительность желто-красной платформы и практической реализуемости задач оптимизации на ней.

    Reply
  3. ivanov660

    Что если применить этот и подобные методы для расчета себестоимости вместо РАУЗ? Бух ставит критерий нужна себестоимость в таких-то рамках и нажимает кнопку «подогнать» ))))

    Reply
  4. unpete

    (2)

    1С это вообще не платформа для решения сложных вычислительных задач

    К сожалению, идеальной платформы для параллельных вычислений пока не придумали. В MPI большие потери на синхронизацию потоков и задействованы только CPU, в OpenMP нет поддержки кластеров и так же, как в MPI нельзя задействовать процессоры видеокарты, OpenCL вариант интересный, но готовой реализации генетики для него не нашел. Написать __kernel для целевой функции не проблема, но вопрос, как эффективно загрузить несколько тысяч процессоров видеокарты остается открытым.

    Генетической оптимизацией занимаюсь с 2009-го года. Первый оптимизатор линейного раскроя был на чистом 1С. Результат среднего качества получался минут за 30. Через полгода переписали на delphi, с прозрачным вызовом из 1С. Аналогичное качество стало достижимо секунд за 20. Еще через полгода задействовали многопоточность и изменили работу с памятью, что позволило увеличить количество итераций на 2 порядка. В результате, без хитрых алгоритмов на примитивной однополой мутации получаем результат, превосходящий по качеству дорогие специализированные аналоги.

    как сформулировать критерии прекращения эволюции потому что мы вывели идеальную особь

    Сожалею, что открыл для себя PGAPACK (библиотека для C + MPI) только в 2012-м году. Новые оптимизаторы (задач много) рисую на базе этой библиотеки. Для прекращения эволюции PGAPACK предлагает несколько вариантов «из коробки»: по прекращению роста целевой функции в течение N поколений и по достижении некого приемлемого значения, по количеству итераций или по времени решения. В случае с раскроем, критерий очень прост: если получился процент обрези менее, например 1%, считаем решение оптимальным.

    (3) ivanov660, Для подгона себестоимости генетика не нужна. Эта задача легко решается алгоритмически за один проход.

    Reply
  5. mootriskoff

    Генетика генетикой, а информация ещё записывается ну уровне сущности, которая воплотилась в эту генетику. А там этой информации на порядок больше чем в генетике.

    Этот метод тупиковый.

    Reply
  6. rsergio

    Скачал, посмотрел.

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

    Нашел не оптимальность — в алгоритме мутации переменная КоличествоМутирующихГенов может быть равна нулю, но все-равно проходит пустой цикл мутации и вычисления целевой функции, которая собственно не меняется.

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

    В целом неплохой пример с внешним хорошим оформлением.

    Reply
  7. 9322304@gmail.com

    +1

    Reply
  8. Rustig

    поддерживаю любое развитие мат.методов в 1с

    Reply

Leave a Comment

Ваш адрес email не будет опубликован. Обязательные поля помечены *