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

21.09.17

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

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

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

Наименование Файл Версия Размер
Оптимизация размещения заготовок генетическим алгоритмом:
.epf 17,30Kb
22
.epf 17,30Kb 22 Скачать

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

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

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

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

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

См. также

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

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

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

13000 руб.

02.09.2020    119932    656    389    

701

Infostart PrintWizard

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

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

18000 руб.

06.10.2023    7011    20    6    

37

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

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

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

10000 руб.

10.11.2023    3250    10    1    

31

SALE! 30%

PowerTools

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

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

3600 2520 руб.

14.01.2013    177344    1070    0    

846

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

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

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

5000 руб.

07.02.2018    99205    239    97    

296

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

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

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

3000 руб.

27.08.2019    17914    6    8    

38

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

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

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

2040 руб.

27.12.2017    27945    3    10    

14

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

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

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

2400 руб.

24.09.2019    23491    15    15    

31
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. CyberCerber 851 28.06.17 14:27 Сейчас в теме
Интересно... А есть возможность применения данного алгоритма для оптимизации размещения в двухмерном и трехмерном случаях?
2. protexprotex 126 28.06.17 16:13 Сейчас в теме
(1) Добрый день. Да, конечно. Генетический алгоритм - как раз для таких моделей и применяется. Даже можно применить и в четырехмерном случае (с учетом времени). У Вас какая задача стоит?
3. CyberCerber 851 28.06.17 16:51 Сейчас в теме
(2) Да, была подобная задача оптимальной упаковки, решал "жадным" алгоритмом. Вот теперь стало интересно узнать о более "продвинутом" решении.
4. protexprotex 126 28.06.17 17:39 Сейчас в теме
(3) Жадный алгоритм хорош тем, что он математически строг, хотя не всегда точно верен. Т.е. если представить себе функцию вида буквы W (и где правая впадина чуть ниже будет левой), то есть вероятность, что жадный алгоритм найдет минимум левый, а не правый. А вот генетический алгоритм найдет и левый и правый - и можно будет по минимуму выбрать именно правый минимум. Т.е. ген. алгоритм менее подвержен застреванию в локальных минимумах. Но есть проблема в ген. алгоритме - это скорость (медленее чем градиентные алгоритмы), объем потребляемой памяти (каждая особь ген. алгоритма - это описание всей задачи), и с помощью ген. алгоритма нельзя найти точное решение за достаточно разумное время, хотя оно будет достаточно близко к нему.
6. CyberCerber 851 28.06.17 18:16 Сейчас в теме
(4) Да, знаю, что жадный ищет на каждом шаге локальный оптимум, и считаем, что так мы достигнем и общего оптимума. Вот захотелось сравнить, будет ли генетический находить более оптимальные решения задачи упаковки.
7. protexprotex 126 28.06.17 18:45 Сейчас в теме
(6) Если задача содержит несколько решений, и одно из этих решений оптимальней (т.е. если есть несколько локальных минимумов и один глобальный), то вероятность нахождения именно глобального минимума генетическим алгоритмом существенно выше чем жадным. Даже метод имитации отжига (разновидность Монте-Карло) будет оптимальней (правда, если размерность задача очень большая, то время решения расчет очень быстро) чем жадный. Даже поиск глобального решения для задачи вида аттрактора генет. алгоритмом более вероятна чем жадным. Ну, или если стоит задача найти все (почти все, если заранее не известно их количество) решения задачи, то генет. алгоритм - самое то. Но если минимум один (что маловероятно в реальных задачах), то жадный алгоритм быстрее и выдаст большую точность. На картинке виден процесс обучения нейронной сети генетическим алгоритмом. Вот например, даже за 1-ну минуту генет. алгоритм уже хорошо приблизился к глобальному минимуму при 10-ти особях (используется спец. алгоритм перезапуска и спец. стратегия обучения).
Прикрепленные файлы:
8. CyberCerber 851 29.06.17 15:02 Сейчас в теме
(7) Скажите, а алгоритм в вашей обработке реализован запросами или встроенным языком?
Если только на встроенном, то с учетом скорости работы языка 1С и сложности ген. алгоритма, он может считать очень долго.
Например, у меня жадный алгоритм для объемной упаковки около 50 коробок может считать где-то 10 минут.
9. ildarovich 7846 29.06.17 15:22 Сейчас в теме
Хотелось бы поподробнее узнать о постановке задачи. Узкоспециальная терминология типа "хлысты" смущает. Какой критерий оптимизации? Либо более подробно свою область опишите, либо поподробнее саму задачу, если нетрудно.

(8) Не могли бы скинуть размеры 50-ти коробок и самого короба? Хочу с реализацией из http://infostart.ru/public/267268/ сравнить.
11. CyberCerber 851 29.06.17 16:36 Сейчас в теме
(9) Да, интересно было бы сравнить. Вам куда скинуть?
Я тоже в свою очередь еще раз запущу и измерю точнее.
12. CyberCerber 851 29.06.17 17:32 Сейчас в теме
(9) Запустил сейчас еще раз. Про 10 минут я загнул... За 5 мин, 15 сек уложил 55 коробок в 5 контейнеров.
Прикрепляю исходные данные. Коробки не крутятся.
Прикрепленные файлы:
Упаковка.xlsx
16. protexprotex 126 29.06.17 21:28 Сейчас в теме
(12) Простите, но сейчас не позволяет время заняться данной задачей (отчетность на носу :-) - после июля - можно). Сможете сами написать на генет. алгоритме? - если что, я подскажу.
19. CyberCerber 851 30.06.17 09:20 Сейчас в теме
(16) Да я это больше для Сергея писал, как я понимаю, у него уже есть готовый алгоритм для таких расчетов.
Но через ген. алгоритм тоже было бы интересно посмотреть. Сейчас точно написать не смогу, надо разбираться, а у самого завал.
17. protexprotex 126 29.06.17 21:32 Сейчас в теме
(9) Добрый день. Постановка задачи следующая - есть заготовки (хлысты) - разной длины - это из чего режем. И есть палки - что хотим нарезать (тоже разной длины) - надо нарезать так, чтобы был минимальный отход - это критерий оптимизации - или фитнес - функция в терминах генет. алгоритма. Ну а по поводу "хлысты" - мне один раз назвали заготовки один раз, так и привязалось это сорное слово. Тут извиняюсь.
13. protexprotex 126 29.06.17 21:14 Сейчас в теме
(8)Добрый день. Нет, запросы для генетического алгоритма не подойдут - т.к. запрос - это ЧТО надо получить, а не КАК надо получить - тут только встроенным языком. На 1С я написал более для примера как использовать можно данный эволюционный мат. аппарат для платформы 1С. Больше для этого. Т.к. посерьезному решаю подобные задачи (генетические алгоритмы, сверточные нейронные сети, автоэнкодеры и пр.) на C++ - там и мощь ОПП и SSE и шредеры на OPEN GL для визуализации и аппарат. ускорения (типа CUDA для NVIDIO) и т.д. На 1С этого не написать (я не ставлю это в минус 1С - т.к. 1С для своей области - это просто классная и удачная оболочка программирования). А по поводу скорости - генет. алгоритм может и сделает все быстрее жадного, т.к. пространство поиска генет. алгоритмом анализируется более полно - тут все зависит от удачной инициализации весовых коэффициентов - чем ближе старт поиска к глобальному минимуму (искомому решению) - тем быстрее генет. алгоритм его найдет - тут можно использовать для нач. инициализации метод Монтер-Карло - например, имитации отжига.
14. protexprotex 126 29.06.17 21:17 Сейчас в теме
(8) Ну, и еще от правильного выбора оператора мутации, кроссинговера, селекции. Обязательно (лучше всего в большинстве случаев) использовать элитарную стратегию, и анализ дисперсии по популяции - при достижении ее малых значений - делать рестарт по все популяции. Ну, и еще хорошо использовать островную стратегию.
18. CyberCerber 851 30.06.17 09:18 Сейчас в теме
(14) Вы пишете много интересных и красивых слов, но с ген. алгоритмом я не разбирался, поэтому почти все они мне не понятны. :-)
starik-2005; +1 Ответить
5. protexprotex 126 28.06.17 17:40 Сейчас в теме
(3) Но для оптимальной упаковки - ген. алгоритм - самое то. Особенно если использовать перезапуск ген. алгоритма + элитарную стратегию и турнирный метод отбора.
20. andrey314 14 02.06.20 11:31 Сейчас в теме
(2) Можете посоветовать доступную литературу для изучения генетических алгоритмов?
21. CyberCerber 851 02.06.20 11:32 Сейчас в теме
(20) Вы, наверное, ошиблись сообщением. Я не большой спец по ген алгоритмам :-)
22. andrey314 14 02.06.20 11:37 Сейчас в теме
(21) Я вроде как писал комментарий к посту 2. Возможно ошибся
23. CyberCerber 851 02.06.20 11:39 Сейчас в теме
(22) А, да, прошу прощения. У меня была подписка включена на сообщения, поэтому оповещение пришло, думал, ко мне обращаетесь
andrey314; +1 Ответить
24. protexprotex 126 02.06.20 12:11 Сейчас в теме
(20) Добрый день. Да куча в инете всего. Например, вот тут: https://coderlessons.com/tutorials/akademicheskii/izuchite-geneticheskie-algoritmy/geneticheskie-algoritmy-kratkoe-rukovodstvo
Достаточно хорошее введение в тему. Есть еще книга - Генетические алгоритмы, Гладков Л.А., Курейчик В.В., Курейчик В.М., 2006 - достаточно полное руководство
andrey314; +1 Ответить
10. starik-2005 3031 29.06.17 15:53 Сейчас в теме
Как-то реализовывал подобный алгоритм для резки багета (1,5д-упаковка, можно сказать). По сути там применялось два алгоритма: "жадный" для первичной выборки палок и "рюкзак", который уже за вполне приемлемое время выдавал оптимальный вариант. В принципе тоже описывал тут: http://infostart.ru/public/437890/

Но там (в конкретной организации) проблема упиралась не в алгоритм, а в распильщика, который сначала пилил самые длинные ребра из самых длинных реек, что в итоге давало до 25% отходов, а у конкурентов оптимизация доводила до 18%. У Вас на картинках 23%, что, в среднем, уже не мало...
ildarovich; +1 Ответить
15. protexprotex 126 29.06.17 21:23 Сейчас в теме
(10) Это же не программа для - "возьми и внедряй" - это пример алгоритма реализации - если кому нужно - пусть берет себе, оптимизирует и делает себе 10% отхода. Вы, наверное, не прочитали главное про генет. алгоритм - для нахождения глобального минимума (оптимального решения нужно больше шагов - итераций) - на картинке я сделал немного - чтобы просто сделать картинку :-) - ну, и элитарную стратегию включить надо. А вот в точных методах - там и решение не примерное, а точное, но не обязательно оптимальное - тут разницу, надеюсь, Вы понимаете.
Оставьте свое сообщение