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

21.09.17

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

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

Скачать файл

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

Наименование		По подписке [?]	Купить один файл
Оптимизация размещения заготовок генетическим алгоритмом: .epf 17,30Kb 24	24	Скачать (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С.

12000 руб.

02.09.2020 171873 962 403

924

Database Compression Tool (DCT) Универсальный инструмент сжатия, свертки и конвертации баз данных 1С

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

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

8400 руб.

20.08.2024 14367 109 46

108

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

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

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

22200 руб.

06.10.2023 17312 43 15

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

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

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

9360 руб.

17.05.2024 27301 96 48

138

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

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

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

15000 руб.

10.11.2023 11914 45 27

SALE! %

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

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

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

~~4800~~ 3840 руб.

14.01.2013 191279 1152 0

920

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

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

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

20000 руб.

07.10.2021 18098 7 32

Конструктор АРМ

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

Разработка Конструктор автоматизированных рабочих мест "Конструктор АРМ" реализована в виде расширения и является универсальным инструментом для создания АРМ любой сложности в пользовательском режиме.

3600 руб.

27.12.2024 1134 2 0

Комментарии

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

Свернуть все

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Упаковка.xlsx

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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