Пример реализации генетического алгоритма. Обработка реализована на неуправляемых формах. Для запуска обработки на выполнение необходимо подключить ее через дополнительные обработки, или через меню Файл — Открыть. Обработка тестировалась на релизах конфигурации УТТ (10.3), УПП (1.3). Обработк не использует метаданные конфигураций, следовательно, должна корректно запускаться через любые конфигурации 1С. Результаты использования — применение генетического алгоритма для оптимизации размещения заготовок на хлыстах позволяет избавится от применения расчетного математического аппарата — например, такого как жадного алгоритма. В некоторых случаях генетический алгоритм более оптимален, т.к. производит более разноверкторный поиск оптимального решения, что не позволяет алгоритму застревать в локальных минимумах пространства поиска, и позволяет найти глобальный минимум (решение задачи) за более короткий промежуток времени.
Режим использования — в поле "Хлысты из чего режем" — задаем длины и идентификаторы хлыстов — или материала для порезки.
В поле "Палки — чего режем" — задает длины и идентификаторы что необходимо получить.
В обработке реализован одноточечный кроссинговер, Турнирная селекция, элитарная стратегия не используется (небольшая доработка в коде позволит включить этот механизм). Точковый оператор мутации. Количество особей принято = 100 (с возможность изменения).
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Интересно… А есть возможность применения данного алгоритма для оптимизации размещения в двухмерном и трехмерном случаях?
(1) Добрый день. Да, конечно. Генетический алгоритм — как раз для таких моделей и применяется. Даже можно применить и в четырехмерном случае (с учетом времени). У Вас какая задача стоит?
(2) Да, была подобная задача оптимальной упаковки, решал «жадным» алгоритмом. Вот теперь стало интересно узнать о более «продвинутом» решении.
(3) Жадный алгоритм хорош тем, что он математически строг, хотя не всегда точно верен. Т.е. если представить себе функцию вида буквы W (и где правая впадина чуть ниже будет левой), то есть вероятность, что жадный алгоритм найдет минимум левый, а не правый. А вот генетический алгоритм найдет и левый и правый — и можно будет по минимуму выбрать именно правый минимум. Т.е. ген. алгоритм менее подвержен застреванию в локальных минимумах. Но есть проблема в ген. алгоритме — это скорость (медленее чем градиентные алгоритмы), объем потребляемой памяти (каждая особь ген. алгоритма — это описание всей задачи), и с помощью ген. алгоритма нельзя найти точное решение за достаточно разумное время, хотя оно будет достаточно близко к нему.
(3) Но для оптимальной упаковки — ген. алгоритм — самое то. Особенно если использовать перезапуск ген. алгоритма + элитарную стратегию и турнирный метод отбора.
(4) Да, знаю, что жадный ищет на каждом шаге локальный оптимум, и считаем, что так мы достигнем и общего оптимума. Вот захотелось сравнить, будет ли генетический находить более оптимальные решения задачи упаковки.
(6) Если задача содержит несколько решений, и одно из этих решений оптимальней (т.е. если есть несколько локальных минимумов и один глобальный), то вероятность нахождения именно глобального минимума генетическим алгоритмом существенно выше чем жадным. Даже метод имитации отжига (разновидность Монте-Карло) будет оптимальней (правда, если размерность задача очень большая, то время решения расчет очень быстро) чем жадный. Даже поиск глобального решения для задачи вида аттрактора генет. алгоритмом более вероятна чем жадным. Ну, или если стоит задача найти все (почти все, если заранее не известно их количество) решения задачи, то генет. алгоритм — самое то. Но если минимум один (что маловероятно в реальных задачах), то жадный алгоритм быстрее и выдаст большую точность. На картинке виден процесс обучения нейронной сети генетическим алгоритмом. Вот например, даже за 1-ну минуту генет. алгоритм уже хорошо приблизился к глобальному минимуму при 10-ти особях (используется спец. алгоритм перезапуска и спец. стратегия обучения).
(7) Скажите, а алгоритм в вашей обработке реализован запросами или встроенным языком?
Если только на встроенном, то с учетом скорости работы языка 1С и сложности ген. алгоритма, он может считать очень долго.
Например, у меня жадный алгоритм для объемной упаковки около 50 коробок может считать где-то 10 минут.
Хотелось бы поподробнее узнать о постановке задачи. Узкоспециальная терминология типа «хлысты» смущает. Какой критерий оптимизации? Либо более подробно свою область опишите, либо поподробнее саму задачу, если нетрудно.
(8) Не могли бы скинуть размеры 50-ти коробок и самого короба? Хочу с реализацией из сравнить.
Как-то реализовывал подобный алгоритм для резки багета (1,5д-упаковка, можно сказать). По сути там применялось два алгоритма: «жадный» для первичной выборки палок и «рюкзак», который уже за вполне приемлемое время выдавал оптимальный вариант. В принципе тоже описывал тут:
Но там (в конкретной организации) проблема упиралась не в алгоритм, а в распильщика, который сначала пилил самые длинные ребра из самых длинных реек, что в итоге давало до 25% отходов, а у конкурентов оптимизация доводила до 18%. У Вас на картинках 23%, что, в среднем, уже не мало…
(9) Да, интересно было бы сравнить. Вам куда скинуть?
Я тоже в свою очередь еще раз запущу и измерю точнее.
(9) Запустил сейчас еще раз. Про 10 минут я загнул… За 5 мин, 15 сек уложил 55 коробок в 5 контейнеров.
Прикрепляю исходные данные. Коробки не крутятся.
(8)Добрый день. Нет, запросы для генетического алгоритма не подойдут — т.к. запрос — это ЧТО надо получить, а не КАК надо получить — тут только встроенным языком. На 1С я написал более для примера как использовать можно данный эволюционный мат. аппарат для платформы 1С. Больше для этого. Т.к. посерьезному решаю подобные задачи (генетические алгоритмы, сверточные нейронные сети, автоэнкодеры и пр.) на C++ — там и мощь ОПП и SSE и шредеры на OPEN GL для визуализации и аппарат. ускорения (типа CUDA для NVIDIO) и т.д. На 1С этого не написать (я не ставлю это в минус 1С — т.к. 1С для своей области — это просто классная и удачная оболочка программирования). А по поводу скорости — генет. алгоритм может и сделает все быстрее жадного, т.к. пространство поиска генет. алгоритмом анализируется более полно — тут все зависит от удачной инициализации весовых коэффициентов — чем ближе старт поиска к глобальному минимуму (искомому решению) — тем быстрее генет. алгоритм его найдет — тут можно использовать для нач. инициализации метод Монтер-Карло — например, имитации отжига.
(8) Ну, и еще от правильного выбора оператора мутации, кроссинговера, селекции. Обязательно (лучше всего в большинстве случаев) использовать элитарную стратегию, и анализ дисперсии по популяции — при достижении ее малых значений — делать рестарт по все популяции. Ну, и еще хорошо использовать островную стратегию.
(10) Это же не программа для — «возьми и внедряй» — это пример алгоритма реализации — если кому нужно — пусть берет себе, оптимизирует и делает себе 10% отхода. Вы, наверное, не прочитали главное про генет. алгоритм — для нахождения глобального минимума (оптимального решения нужно больше шагов — итераций) — на картинке я сделал немного — чтобы просто сделать картинку 🙂 — ну, и элитарную стратегию включить надо. А вот в точных методах — там и решение не примерное, а точное, но не обязательно оптимальное — тут разницу, надеюсь, Вы понимаете.
(12) Простите, но сейчас не позволяет время заняться данной задачей (отчетность на носу 🙂 — после июля — можно). Сможете сами написать на генет. алгоритме? — если что, я подскажу.
(9) Добрый день. Постановка задачи следующая — есть заготовки (хлысты) — разной длины — это из чего режем. И есть палки — что хотим нарезать (тоже разной длины) — надо нарезать так, чтобы был минимальный отход — это критерий оптимизации — или фитнес — функция в терминах генет. алгоритма. Ну а по поводу «хлысты» — мне один раз назвали заготовки один раз, так и привязалось это сорное слово. Тут извиняюсь.
(14) Вы пишете много интересных и красивых слов, но с ген. алгоритмом я не разбирался, поэтому почти все они мне не понятны. 🙂
(16) Да я это больше для Сергея писал, как я понимаю, у него уже есть готовый алгоритм для таких расчетов.
Но через ген. алгоритм тоже было бы интересно посмотреть. Сейчас точно написать не смогу, надо разбираться, а у самого завал.