Спосіб розмітки плоского матеріалу

Спосіб розмітки плоского матеріалу, що включає автоматичне формування розмітки за допомогою простих геометричних фі гур у вигляді контурів, який відрізняється тим, що задають множину фрагментів розмітки, які нумерують у заданому 3 37839 го алгоритму та апарату гр уп перетворень для побудови розмітки. Відмінними від прототипу ознаками способу є: визначення певного порядку нумерації, використання критерію симетрії відносно стандартних груп перетворень, використання фрагментарного алгоритму, який включає виділення послідовності точок на прямокутній матриці-основі з такою властивістю: будь-яка початкова частина цієї послідовності точок максимально або мінімально симетрична щодо заданої групи симетрії; визначення умов приєднання фрагмента до вже побудованої множини фрагментів; перебір фрагментів у заданому порядку, причому, на кожному етапі здійснюють спробу приєднання фрагмента до точки послідовності з мінімальним номером і з виконанням умов приєднання до закінчення перебору фрагментів. Як правило в задачах розмітки при створенні автоматизованих систем розкрою критерієм якості є критерій мінімуму відходів. На відміну від цього в запропонованому способі використовують критерій, що важко формалізувати, - критерій симетричного розміщення і процедуру автоматичного вирішення проблеми. Проблема прийняття рішень у такій задачі є, по суті, проблемою штучного інтелекту й повинна вирішуватися шля хом використання баз знань, що накопичуються. Ця проблема виявляється настільки неформальною, настільки складною для алгоритмічного підходу, що єдиною ланкою системи, яка може поставити крапку при прийнятті рішень залишається людина - особа приймаюче рішення (ОПР). З іншого боку при підготовці рішення необхідно обробити такі обсяги інформації, з якими не під силу впоратися не тільки людині, але й складним комп'ютерним системам. Якщо в системі прийняття рішень присутня людина, то це накладає певні вимоги на процеси, що протікають на всіх рівнях рішення задачі. Відповідно й алгоритми, які застосовують для пошуку оптимальних рішень або пошуку альтернативних варіантів у таких системах повинні мати низку властивостей, що дозволяють з одного боку максимально автоматизувати процес ухвалення рішення, з іншого боку дати можливість людині втручатися в процес ухвалення рішення практично на кожному етапі, конкретизуючи поняття оптимуму й відтинаючи сторонні альтернативи. Задачу формулюють таким чином: на прямокутній матриці-основі розмістити заданий набір контурів найбільш або найменш симетричним образом. Задачі симетричного розміщення може бути вирішена лише наближено. Тому в першу чергу необхідно визначити критерії якості рішення. Без формального критерію якості автоматизація процесу розміщення буде просто неможлива. Друга проблема - сам алгоритм розміщення, що давав би симетричні рішення. До числа основних вимог до алгоритму такого типу відносяться: а) невелике число кроків алгоритму з можливістю корекції процесу пошуку рішення на кожному кроці; б) висока швидкість виконання алгоритму. Низька швидкість для діалогу «Людина-машина» є 4 неприємною, тому що при великому часі очікування відгуку міняються цільові функції виконавця. Критерій швидкості виконання розрахунку може відігравати ключову роль на відміну від інши х критеріїв якості; в) можливість реалізації різних варіантів розрахунку. На будь-якому кроці можуть змінитися як первісна система обмежень, так і цільова функція ОПР. Тому необхідно передбачити можливість переходу, як на попередні кроки розрахунку, так і на нові правила пошуку рішення, починаючи з поточного кроку. Ефективними алгоритмами такого класу є «жадібні» алгоритми (Greedy algorithms) і побудовані на їхній основі фрагментарні алгоритми, які за невелике число кроків приводять до квазіоптимального рішення оптимізаційних задач. Для дискретизації задачі використовують прямокутні решітки, які розглядають як граф P=(V,E) певного типу. Кожному осередку решітки відповідає вершина графа - елемент множини V. Дві вершини графа з'єднані ребром (пари вершин належить множині Е) у тому і тільки в тому випадку, коли відповідні їм осередки решітки мають спільну сторону. Ізоморфізмом графа називають таке взаємно однозначне відображення його вершин, при якому зберігається відношення суміжності вершин. Повну груп у перетворень решітки визначають як групу G ізоморфізмів її графа. Нейтральним (одиничним) елементом цієї групи служить тотожний ізоморфізм id(x) = x" x Î V . Підмножина перетворень, яка є замкнутою щодо операції суперпозиції й операції зворотного перетворення, є підгрупою групи G. Таку підгруп у називають групою перетворень. Нехай G - довільна група перетворень решітки. Дію елемента g Î G на елемент x Î V визначають таким чином: g·х=g(x). Дію елемента g Î G на підмножину A Í V визначають за аналогією, а саме: g= = g(x), x Î A . ×A yy { } Для кожного елемента x Î V визначають множину O x = {y : y = g × x g Î G}. Цю множину називають орбітою елемента х при дії групи G. Очевидно, орбіти будь-яких двох елементів множини V або не перетинаються, або збігаються. Таким чином, вся множина V виявляється розбитою на класи попарно непересічних між собою орбіт. Множину A Í V називають інваріантною або G-симетричною щодо дії гр упи перетворень G (або G-інваріантною), якщо "x Î A и " g Î G g × x Î A . Інакше кажучи, множина А інваріантна щодо дії групи G, якщо орбіта будь-якого елемента цієї множини при дії групи G є підмножиною множини А, або " g Î G, g × A = A . Множину A Í V називають G-асиметричною щодо дії групи перетворень G, якщо "x Î A и " g Î G g × x Ï A . Інакше кажучи, множина А є Gасиметричною, у тім і тільки в тому випадку, коли " g Î G, g × A Ç A = Æ . 5 37839 Мірою симетрії непустої підмножини A Í V називають число μG(A), що визначають за формулою: m G (A) = A (1) U g× A gÎ G де μG(А) - міра симетрії підмножини А, (безрозмірна величина),; |Х| - число елементів у множині X., G - гр упа симетрії, g - елемент групи G. З (1) випливає, що " A Í V 0≤μG(A)≤1. Причому для G-симетричної множини А її міра симетрії μG(А)=1. Наприклад, верхньотрикутне розміщення визначають як підмножину A Í V , асиметричну щодо групи перетворення, що породжується діагональним відбиттям решітки (діагональ, що з'єднує лівий нижній із правим верхнім кутом), периметричне розміщення - підмножина інваріантна щодо групи всі х осьових відбитків решітки. Тобто кожне розміщення характеризують його мірою симетрії щодо певної групи перетворень. У системі підтримки прийняття рішень передбачені ефективні евристичні алгоритми, які задовольняють практично всім вимогам, що наведено вище. Загальна схема побудови таких алгоритмів: а) Визначають множину фрагментів рішень {f} і зовнішню операцію Å з'єднання фрагментів (з'єднання фрагментів, як правило, фрагментом не є). Кожне припустиме рішення задачі складається з кінцевого числа фрагментів із заданої множини фрагментів, з'єднаних шляхом зовнішньої операції. б) Задають ряд відносин лінійного порядку {p} на множині фрагментів й ефективну процедуру впорядкування фрагментів, що дозволяє одержувати впорядкування фрагментів за різними порядками відносно до обраних правил. в) Задають умови приєднання фрагмента, які можуть бути як детермінованими, так і динамічними, мінливими на кожному кроці. Для вже обраної підмножини фрагментів задають ефективну процедуру перевірки можливості приєднання фрагмента, що не належить обраній підмножині. Алгоритми, які будують за зазначеною вище схемою, називають фрагментарними. Кожен крок фрагментарного алгоритму полягає в такому: вибирають відношення порядку із заданої множини відносин. Проглядають усі ще не обрані фрагменти, впорядковані за обраним відношенням лінійного порядку. Вибирають перший із фрагментів, що задовольняє умовам приєднання, й додають до множини. Умова зупинки алгоритму - не вдалося знайти черговий фрагмент. Фрагментарний алгоритм не передбачає умови оптимальності. Визначення поняття оптимальності переноситься на ОПР. Причому умови вибору чергового фрагмента можуть мінятися на окремих етапах роботи алгоритму залежно від побудованої множини фрагментів. 6 Спосіб розмітки плоского матеріалу здійснюють таким чином: а) задають множину фрагментів для розмітки, які нумерують в певному порядку (наприклад за зростанням висоти, ширини, площі, периметра тощо); б) вибирають критерій симетрії для оцінки якості розмітки відносно деякої стандартної групи перетворень; в) автоматизоване використання фрагментарного алгоритму і апарату груп перетворень виконують таким чином: виділяють послідовність точок на прямокутній матриці-основі з такою властивістю: будь-яка початкова підпослідовність цієї послідовності точок максимально або мінімально симетрична щодо заданої групи симетрії; задають умову приєднання фрагмента до вже побудованої множини фрагментів; фрагменти перебирають у заданому порядку, на кожному етапі здійснюють спробу приєднання фрагмента до точки послідовності з мінімальним номером і з виконанням умов приєднання; розмітку вважають побудованою після того, як вичерпані всі фрагменти. Наприклад, для задачі розміщення прямокутних блоків має місце природна фрагментація. Фрагментом рішення є розміщення одного прямокутного блоку. Як порядок на множині фрагментів можна, наприклад, використовувати такі правила упорядкування: а) за зростанням (убуванням) площі блоків; б) за зростанням (убуванням) периметрів блоків; в) за зростанням (убуванням) ширини блоків; г) за зростанням (убуванням) висоти блоків. Для конкретної реалізації алгоритмів розміщення можна використовувати й інші правила, пов'язані з особливостями прикладної задачі. Умови приєднання блоку до вже наявного набору фрагментів такі: а) відсутність перетинань із кожним з уже обраних фрагментів; б) максимум (або мінімум) міри симетрії щодо обраної групи перетворень. Додатковою умовою може бути умова загальної границі хоча б з одним із уже існуючих блоків. Групи перетворень решітки, які можуть бути застосовані в цій задачі: а) група G1 - гр упа осьової симетрії щодо вертикальної осі; б) група G2 - гр упа осьової симетрії щодо вертикальної осі; в) гр упа G3 - група центральної симетрії щодо центру решітки. Для окремих видів решіток можуть бути й інші групи. Фрагментарний алгоритм був реалізований в інформаційній системі "Медіа", призначеної для прийому заявок на рекламу та розміщення рекламних блоків на сторінках рекламних видань. Впровадження цього алгоритму дозволить підняти продуктивність праці в декілька разів порівняно з існуючими технологіями. Крім вказаних вище властивостей алгоритм 7 37839 дозволяє закріплювати при розміщенні окремі блоки на фіксованих місцях, упорядковувати блоки за тематикою, номерами замовлень та ін., вручну робити переміщення блоків після закінчення роботи алгоритму. Реалізовано автоматизовану систему розмітки, в якій присутні алгоритми таких типів розміщень: верхньопрямокутне, нижньопрямокутне, лівопрямокутне, правопрямокутне, верхньоправотрикутне верхньолівотрикутне, нижньоправотрикутне, ижньолівотрикутне, периметричне, центральне й випадкове. Послідовність дій у реалізованій системі при формуванні розмітки така: по-перше, вибирають прямокутники, як елементи розмітки; по-друге, визначають критерій симетрії для оцінки якості розмітки відносно стандартних груп симетрій. На Фіг.1 наведено піктограми для вибору стандартної групи симетрій. Автоматизоване використання фрагментарного алгоритму дозволяє побудувати розмітки, приклади яких наведено на Фіг.2-4, а саме: на Фіг.2 наведено приклад верхньоправотрикутного розміщення блоків; на Фіг.3 - периметричне розміщення блоків; на Фіг.4 - нижньопрямокутне розміщення блоків. У фрагментарному алгоритмі можуть бути використані такі правила упорядкування блоків рек 8 лами: за шириною блоку, за висотою блоку, за площею блоку, за номером блоку, за відношенням ширини до висоти блоку, за тематикою реклами. Упорядкування можуть бути за зростанням й за убуванням критерію. Умовою приєднання блоку є можливість його розміщення на матриці-основі без перетинань з іншими блоками. Перевірку цієї можливості здійснюють шляхом простого перебору вільних осередків у напрямку "по" або "проти" годинної стрілки. Цікавою властивістю алгоритму виявилося те, що він, як правило, дозволяє вирішити й іншу задачу - задачу максимально щільного розміщення блоків із заданого набору на матриці-основі. Фрагментарний алгоритм залишає ОПР два основних механізми втручання в процес пошуку оптимального рішення - це спосіб упорядкування фрагментів й умова приєднання. Завдяки цьому можна в процесі прийняття рішень використовувати нечіткі, «лінгвістичні» вимоги, такі як «найкращий», «найбільш підходящий», «гарний з погляду ОПР» та інші. У фрагментарних алгоритмах нечіткість і розмитість деяких формулювань може бути поєднана із твердими правилами упорядкування й приєднання фрагментів. Таким чином, спосіб розмітки може бути застосований при створенні автоматизованих систем для багатьох задач розмітки та розкрою в різних галузях промисловості, де раніш застосування алгоритмічного підходу було неможливим. 9 Комп’ютерна в ерстка А. Крулевський 37839 Підписне 10 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601