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

29.09.15

Разработка - Инструментарий разработчика

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

Скачать файлы

Наименование Файл Версия Размер
ГенетическийАлгоритмV01.epf
.epf 16,67Kb
34
.epf 16,67Kb 34 Скачать

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

Оптимизация генетический алгоритм задача коммивояжера многомерная оптимизация

См. также

SALE! 20%

Infostart Toolkit: Инструменты разработчика 1С 8.3 на управляемых формах

Инструментарий разработчика Роли и права Запросы СКД Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

10000 8000 руб.

02.09.2020    122363    673    389    

716

SALE! 25%

Infostart PrintWizard

Пакетная печать Печатные формы Инструментарий разработчика Платформа 1С v8.3 Запросы 1С:Зарплата и кадры бюджетного учреждения 1С:Конвертация данных 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 Платные (руб)

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

18000 15300 руб.

06.10.2023    7337    22    6    

39

SALE! 20%

Infostart УДиФ: Управление данными и формами

Инструменты администратора БД Инструментарий разработчика Роли и права Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

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

10000 8000 руб.

10.11.2023    3626    11    1    

34

SALE! 30%

PowerTools

Инструментарий разработчика Инструменты администратора БД Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Россия Платные (руб)

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

3600 2520 руб.

14.01.2013    177821    1074    0    

851

Многопоточность. Универсальный «Менеджер потоков» 2.1

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Россия Платные (руб)

Восстановление партий или взаиморасчетов, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

5000 руб.

07.02.2018    99375    239    97    

296

[ЕХТ] Фреймворк для Расширений 1С

Инструментарий разработчика Платформа 1С v8.3 Управляемые формы Платные (руб)

"Фреймворк для Расширений 1С" это универсальное и многофункциональное решение, упрощающее разработку и поддержку создаваемых Расширений. Поставляется в виде комплекта из нескольких Расширений с открытым исходным кодом. Работает в любых Конфигурациях в режиме Управляемого приложения с режимом совместимости 8.3.12 и выше без необходимости внесения изменений в Конфигурацию.

3000 руб.

27.08.2019    18136    6    8    

40

1С HTML Шаблоны / HTML Templates

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Платные (руб)

Быстрая и удобная обработка для работы с шаблонами HTML. Позволяет легко и быстро формировать код HTML.

2040 руб.

27.12.2017    28119    3    10    

15

Выполнение произвольного кода или запроса с параметрами через Web-сервис (замена COM-подключений)

Инструментарий разработчика Обмен между базами 1C Платформа 1С v8.3 Платные (руб)

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

2400 руб.

24.09.2019    23607    15    15    

32
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. unpete 577 29.09.15 15:26 Сейчас в теме
Возможно, стоило дать читателям ссылку на PGAPACK - там много полезного.

Однако качество самого решения, далеко от идеала
Для получения качественного решения, необходима достаточно длительная эволюция. Триллионы циклов внутри 1С будут рассчитаны неприемлемо долго. Качество кроссовера и мутатора, так же, имеют значение.
IMHO, критиковать генетику на основании 1С-ной реализации не совсем справедливо.
9322304@gmail.com; +1 Ответить
2. dusha0020 1104 29.09.15 16:08 Сейчас в теме
(1) unpete, Триллионы поколений это да. Но с другой стороны где критерии "качественности" решения? Разве они объективны? Задумайтесь над тем, что сформулировать критерии окончания работы генетического алгоритма это как сформулировать критерии прекращения эволюции потому что мы вывели идеальную особь. Приемлемость решения как и качество получившихся в процессе эволюции особей вещь сугубо субъективная.
С другой стороны раз уж мы на инфостарте то и задачи описываем применительно к 1С. Вот и моя критика это субъективное видение способности генетического алгоритма решать прикладные задачи на платформе 1С за приемлемое время.
Но с другой стороны не могу не согласиться с Вами. 1С это вообще не платформа для решения сложных вычислительных задач, поэтому критиковать с точки зрения соотношения качество решения / быстродействие на 1С можно вообще все. Методы оптимизации от этого, естественно, не становятся хуже, как и 1С не начинает считать быстрее:)
Так что все мои выводы, естественно, с оговорками на производительность желто-красной платформы и практической реализуемости задач оптимизации на ней.
4. unpete 577 29.09.15 19:37 Сейчас в теме
(2)
1С это вообще не платформа для решения сложных вычислительных задач
К сожалению, идеальной платформы для параллельных вычислений пока не придумали. В MPI большие потери на синхронизацию потоков и задействованы только CPU, в OpenMP нет поддержки кластеров и так же, как в MPI нельзя задействовать процессоры видеокарты, OpenCL вариант интересный, но готовой реализации генетики для него не нашел. Написать __kernel для целевой функции не проблема, но вопрос, как эффективно загрузить несколько тысяч процессоров видеокарты остается открытым.
Генетической оптимизацией занимаюсь с 2009-го года. Первый оптимизатор линейного раскроя был на чистом 1С. Результат среднего качества получался минут за 30. Через полгода переписали на delphi, с прозрачным вызовом из 1С. Аналогичное качество стало достижимо секунд за 20. Еще через полгода задействовали многопоточность и изменили работу с памятью, что позволило увеличить количество итераций на 2 порядка. В результате, без хитрых алгоритмов на примитивной однополой мутации получаем результат, превосходящий по качеству дорогие специализированные аналоги.
как сформулировать критерии прекращения эволюции потому что мы вывели идеальную особь
Сожалею, что открыл для себя PGAPACK (библиотека для C + MPI) только в 2012-м году. Новые оптимизаторы (задач много) рисую на базе этой библиотеки. Для прекращения эволюции PGAPACK предлагает несколько вариантов "из коробки": по прекращению роста целевой функции в течение N поколений и по достижении некого приемлемого значения, по количеству итераций или по времени решения. В случае с раскроем, критерий очень прост: если получился процент обрези менее, например 1%, считаем решение оптимальным.

(3) ivanov660, Для подгона себестоимости генетика не нужна. Эта задача легко решается алгоритмически за один проход.
3. ivanov660 4332 29.09.15 17:26 Сейчас в теме
Что если применить этот и подобные методы для расчета себестоимости вместо РАУЗ? Бух ставит критерий нужна себестоимость в таких-то рамках и нажимает кнопку "подогнать" ))))
pridecom; +1 Ответить
5. mootriskoff 30.09.15 13:28 Сейчас в теме
Генетика генетикой, а информация ещё записывается ну уровне сущности, которая воплотилась в эту генетику. А там этой информации на порядок больше чем в генетике.
Этот метод тупиковый.
6. rsergio 80 02.10.15 16:12 Сейчас в теме
Скачал, посмотрел.

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

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

В целом неплохой пример с внешним хорошим оформлением.
7. 9322304@gmail.com 8 25.05.16 23:47 Сейчас в теме
8. RustIG 1382 18.01.19 11:00 Сейчас в теме
поддерживаю любое развитие мат.методов в 1с
9. pridecom 791 25.05.21 14:06 Сейчас в теме
А как реализуется задача, если то же самое, но одновременно надо спланировать не один, а два (например) рейса из точки 1?
10. Global__IT 264 28.12.22 02:54 Сейчас в теме
Буду разбираться. Хотел применить для решения линейного неравенства с несколькими переменными, но пока не въехал как это интерпритировать на мою задачу. Буду разбираться
Оставьте свое сообщение