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

21.09.17

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

Пример применения генетического алгоритма для оптимизации размещения заготовок хлыстов. Программа реализована полностью на внутреннем языке 1С.

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование		По подписке [?]	Купить один файл
Оптимизация размещения заготовок генетическим алгоритмом: .epf 17,30Kb 25	25	Скачать (3 SM)	Купить за 2 450 руб.

Пример реализации генетического алгоритма. Обработка реализована на неуправляемых формах. Для запуска обработки на выполнение необходимо подключить ее через дополнительные обработки, или через меню Файл - Открыть. Обработка тестировалась на релизах конфигурации УТТ (10.3), УПП (1.3). Обработк не использует метаданные конфигураций, следовательно, должна корректно запускаться через любые конфигурации 1С. Результаты использования - применение генетического алгоритма для оптимизации размещения заготовок на хлыстах позволяет избавится от применения расчетного математического аппарата - например, такого как жадного алгоритма. В некоторых случаях генетический алгоритм более оптимален, т.к. производит более разноверкторный поиск оптимального решения, что не позволяет алгоритму застревать в локальных минимумах пространства поиска, и позволяет найти глобальный минимум (решение задачи) за более короткий промежуток времени.

Режим использования - в поле "Хлысты из чего режем" - задаем длины и идентификаторы хлыстов - или материала для порезки.

В поле "Палки - чего режем" - задает длины и идентификаторы что необходимо получить.

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

Генетический алгоритм; Оптимизация;

+20 –

См. также

Infostart Toolkit — Инструменты разработчика 1С 8.3

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

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

15500 руб.

02.09.2020 187153 1044 403

976

Database Compression Tool: Инструмент для свертки и сжатия баз данных 1С

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

Инструмент представляет собой обработку для проведения свёртки или обрезки баз данных. Работает на ЛЮБЫХ конфигурациях (УТ, БП, ERP, УНФ, КА и т.д.). Поддерживаются серверные и файловые базы, управляемые и обычные формы. Может выполнять свертку одновременно в несколько потоков. А так же автоматически, без непосредственного участия пользователя. Решение в Реестре отечественного ПО

8400 руб.

20.08.2024 26270 171 88

166

Infostart PrintWizard (конструктор печатных форм)

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

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

22200 руб.

06.10.2023 20933 55 19

Infostart DataFormWizard: Управление данными и формами 1С 8.3

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

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

15000 руб.

10.11.2023 14066 60 33

OneDebugger - инструмент для отладки кода в 1С без использования конфигуратора

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

Инструмент для написания и отладки кода в режиме «1С:Предприятие». Представляет собой консоль кода с возможностью пошаговой отладки, просмотра значений переменных любых типов, использования процедур и функций, просмотра стека вызовов, вычисления произвольных выражений на встроенном языке в контексте точки останова, синтаксического контроля и остановки по ошибке. В консоли используется удобный редактор кода с подсветкой, контекстной подсказкой, возможностью вызова конструкторов запроса и форматной строки.

9360 руб.

17.05.2024 31130 107 48

149

PowerTools: Инструменты администратора 1С 8.3

Инструментарий разработчика Инструменты администратора БД Системный администратор Программист Платформа 1С v8.3 Управляемые формы 1C:ERP 1С:УТ 1С:ДО 1С:Бухгалтерия 3.0 1С:ERP. Управление холдингом 1С:Зарплата и Управление Персоналом 3.x 1С:Управление нашей фирмой 3.0 1С:Управление торговлей 11 Россия Платные (руб)

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

4800 руб.

14.01.2013 196156 1172 0

933

Бустер Конвертации данных 3 (Infostart Toolkit)

Инструментарий разработчика Программист 8.3.14 Россия Платные (руб)

Расширение для конфигурации “Конвертация данных 3”. Добавляет подсветку синтаксиса, детальную контекстную подсказку, глобальный поиск по коду.

20000 руб.

07.10.2021 19319 8 32

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

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

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

5000 руб.

07.02.2018 105195 247 100

312

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. CyberCerber 882 28.06.17 14:27 Сейчас в теме

Интересно... А есть возможность применения данного алгоритма для оптимизации размещения в двухмерном и трехмерном случаях?

2. protexprotex 141 28.06.17 16:13 Сейчас в теме

(1) Добрый день. Да, конечно. Генетический алгоритм - как раз для таких моделей и применяется. Даже можно применить и в четырехмерном случае (с учетом времени). У Вас какая задача стоит?

3. CyberCerber 882 28.06.17 16:51 Сейчас в теме

(2) Да, была подобная задача оптимальной упаковки, решал "жадным" алгоритмом. Вот теперь стало интересно узнать о более "продвинутом" решении.

4. protexprotex 141 28.06.17 17:39 Сейчас в теме

(3) Жадный алгоритм хорош тем, что он математически строг, хотя не всегда точно верен. Т.е. если представить себе функцию вида буквы W (и где правая впадина чуть ниже будет левой), то есть вероятность, что жадный алгоритм найдет минимум левый, а не правый. А вот генетический алгоритм найдет и левый и правый - и можно будет по минимуму выбрать именно правый минимум. Т.е. ген. алгоритм менее подвержен застреванию в локальных минимумах. Но есть проблема в ген. алгоритме - это скорость (медленее чем градиентные алгоритмы), объем потребляемой памяти (каждая особь ген. алгоритма - это описание всей задачи), и с помощью ген. алгоритма нельзя найти точное решение за достаточно разумное время, хотя оно будет достаточно близко к нему.

6. CyberCerber 882 28.06.17 18:16 Сейчас в теме

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

7. protexprotex 141 28.06.17 18:45 Сейчас в теме

(6) Если задача содержит несколько решений, и одно из этих решений оптимальней (т.е. если есть несколько локальных минимумов и один глобальный), то вероятность нахождения именно глобального минимума генетическим алгоритмом существенно выше чем жадным. Даже метод имитации отжига (разновидность Монте-Карло) будет оптимальней (правда, если размерность задача очень большая, то время решения расчет очень быстро) чем жадный. Даже поиск глобального решения для задачи вида аттрактора генет. алгоритмом более вероятна чем жадным. Ну, или если стоит задача найти все (почти все, если заранее не известно их количество) решения задачи, то генет. алгоритм - самое то. Но если минимум один (что маловероятно в реальных задачах), то жадный алгоритм быстрее и выдаст большую точность. На картинке виден процесс обучения нейронной сети генетическим алгоритмом. Вот например, даже за 1-ну минуту генет. алгоритм уже хорошо приблизился к глобальному минимуму при 10-ти особях (используется спец. алгоритм перезапуска и спец. стратегия обучения).

Прикрепленные файлы:

8. CyberCerber 882 29.06.17 15:02 Сейчас в теме

(7) Скажите, а алгоритм в вашей обработке реализован запросами или встроенным языком?
Если только на встроенном, то с учетом скорости работы языка 1С и сложности ген. алгоритма, он может считать очень долго.
Например, у меня жадный алгоритм для объемной упаковки около 50 коробок может считать где-то 10 минут.

9. ildarovich 7960 29.06.17 15:22 Сейчас в теме

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

(8) Не могли бы скинуть размеры 50-ти коробок и самого короба? Хочу с реализацией из http://infostart.ru/public/267268/ сравнить.

11. CyberCerber 882 29.06.17 16:36 Сейчас в теме

(9) Да, интересно было бы сравнить. Вам куда скинуть?
Я тоже в свою очередь еще раз запущу и измерю точнее.

12. CyberCerber 882 29.06.17 17:32 Сейчас в теме

(9) Запустил сейчас еще раз. Про 10 минут я загнул... За 5 мин, 15 сек уложил 55 коробок в 5 контейнеров.
Прикрепляю исходные данные. Коробки не крутятся.

Прикрепленные файлы:

Упаковка.xlsx

16. protexprotex 141 29.06.17 21:28 Сейчас в теме

(12) Простите, но сейчас не позволяет время заняться данной задачей (отчетность на носу :-) - после июля - можно). Сможете сами написать на генет. алгоритме? - если что, я подскажу.

19. CyberCerber 882 30.06.17 09:20 Сейчас в теме

(16) Да я это больше для Сергея писал, как я понимаю, у него уже есть готовый алгоритм для таких расчетов.
Но через ген. алгоритм тоже было бы интересно посмотреть. Сейчас точно написать не смогу, надо разбираться, а у самого завал.

17. protexprotex 141 29.06.17 21:32 Сейчас в теме

(9) Добрый день. Постановка задачи следующая - есть заготовки (хлысты) - разной длины - это из чего режем. И есть палки - что хотим нарезать (тоже разной длины) - надо нарезать так, чтобы был минимальный отход - это критерий оптимизации - или фитнес - функция в терминах генет. алгоритма. Ну а по поводу "хлысты" - мне один раз назвали заготовки один раз, так и привязалось это сорное слово. Тут извиняюсь.

13. protexprotex 141 29.06.17 21:14 Сейчас в теме

(8)Добрый день. Нет, запросы для генетического алгоритма не подойдут - т.к. запрос - это ЧТО надо получить, а не КАК надо получить - тут только встроенным языком. На 1С я написал более для примера как использовать можно данный эволюционный мат. аппарат для платформы 1С. Больше для этого. Т.к. посерьезному решаю подобные задачи (генетические алгоритмы, сверточные нейронные сети, автоэнкодеры и пр.) на C++ - там и мощь ОПП и SSE и шредеры на OPEN GL для визуализации и аппарат. ускорения (типа CUDA для NVIDIO) и т.д. На 1С этого не написать (я не ставлю это в минус 1С - т.к. 1С для своей области - это просто классная и удачная оболочка программирования). А по поводу скорости - генет. алгоритм может и сделает все быстрее жадного, т.к. пространство поиска генет. алгоритмом анализируется более полно - тут все зависит от удачной инициализации весовых коэффициентов - чем ближе старт поиска к глобальному минимуму (искомому решению) - тем быстрее генет. алгоритм его найдет - тут можно использовать для нач. инициализации метод Монтер-Карло - например, имитации отжига.

14. protexprotex 141 29.06.17 21:17 Сейчас в теме

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

18. CyberCerber 882 30.06.17 09:18 Сейчас в теме

(14) Вы пишете много интересных и красивых слов, но с ген. алгоритмом я не разбирался, поэтому почти все они мне не понятны. :-)

5. protexprotex 141 28.06.17 17:40 Сейчас в теме

(3) Но для оптимальной упаковки - ген. алгоритм - самое то. Особенно если использовать перезапуск ген. алгоритма + элитарную стратегию и турнирный метод отбора.

20. andrey314 14 02.06.20 11:31 Сейчас в теме

(2) Можете посоветовать доступную литературу для изучения генетических алгоритмов?

21. CyberCerber 882 02.06.20 11:32 Сейчас в теме

(20) Вы, наверное, ошиблись сообщением. Я не большой спец по ген алгоритмам :-)

22. andrey314 14 02.06.20 11:37 Сейчас в теме

(21) Я вроде как писал комментарий к посту 2. Возможно ошибся

23. CyberCerber 882 02.06.20 11:39 Сейчас в теме

(22) А, да, прошу прощения. У меня была подписка включена на сообщения, поэтому оповещение пришло, думал, ко мне обращаетесь

24. protexprotex 141 02.06.20 12:11 Сейчас в теме

(20) Добрый день. Да куча в инете всего. Например, вот тут: https://coderlessons.com/tutorials/akademicheskii/izuchite-geneticheskie-algoritmy/geneticheskie-algoritmy-kratkoe-rukovodstvo
Достаточно хорошее введение в тему. Есть еще книга - Генетические алгоритмы, Гладков Л.А., Курейчик В.В., Курейчик В.М., 2006 - достаточно полное руководство

10. starik-2005 3173 29.06.17 15:53 Сейчас в теме

Как-то реализовывал подобный алгоритм для резки багета (1,5д-упаковка, можно сказать). По сути там применялось два алгоритма: "жадный" для первичной выборки палок и "рюкзак", который уже за вполне приемлемое время выдавал оптимальный вариант. В принципе тоже описывал тут: http://infostart.ru/public/437890/

Но там (в конкретной организации) проблема упиралась не в алгоритм, а в распильщика, который сначала пилил самые длинные ребра из самых длинных реек, что в итоге давало до 25% отходов, а у конкурентов оптимизация доводила до 18%. У Вас на картинках 23%, что, в среднем, уже не мало...

15. protexprotex 141 29.06.17 21:23 Сейчас в теме

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