Область наук:
  • Математика
  • Рік видавництва: тисяча дев'ятсот дев'яносто дев'ять
    Журнал: Известия Південного федерального університету. Технічні науки
    Наукова стаття на тему 'Кроссинговер для вирішення завдання двовимірної упаковки і розміщення прямокутних елементів на площині'

    Текст наукової роботи на тему «Кроссинговер для вирішення завдання двовимірної упаковки і розміщення прямокутних елементів на площині»

    ?ЛІТЕРАТУРА

    1. Курейчик В. М. Навчальний посібник «Методи генетичного пошуку». Частина 1.Таганрог, 1998, ТРТУ.

    2. Курейчик В.М. Генетичні алгоритми. Монографія. Таганрог: ТРТУ, 1998, мул.

    3. Брікелл Е.Ф., Діффі У. Захищеність і імітостойкость. // ТІІЕР, т. 67, № 3, березень 1979. С. 86-90.

    4. Смід М.Е., Бранстед Д.К. Стандарт шифрування даних: Минуле і майбутнє. // ТІІЕР, т. 76, № 5, травень 1988. С. 43-53.

    5. Брікелл Е.Ф., Одлижко Е.М. Криптоаналіз: Огляд новітніх результатів. // ТІІЕР, т. 67, №5, травень 1988. С. 88-91.

    6. Введення в сучасну криптології. // ТІІЕР, т. 76, № 5, травень 1988. С. 33-35.

    7. Ростовцев А.Г., Михайлова Н.В. Методи криптоаналізу класичних шифрів .// http: //security.lgg.rU//psw/crypto/cryptoanalysis.htrnl

    8. Водолазький В. Комерційні системи шифрування: Основні алгоритми і їх реалізації. Монітор, № 6-8, 1992.

    9. Бабенко Л.К., Макаревич О. Б., Шилов А. К. Введення в криптографічні методи захисту інформації. Навчальний посібник, Таганрог: ТРТУ, 1996..

    УДК 658.512

    І.В. Мухлаева

    Кросинговері ДЛЯ ВИРІШЕННЯ ЗАВДАННЯ двовимірних УПАКОВКИ І РОЗМІЩЕННЯ ПРЯМОКУТНИХ ЕЛЕМЕНТІВ НА ПЛОЩИНІ.

    В роботі розглядається задача упаковки і розміщення прямокутних елементів на площині за допомогою генетичного пошуку. Метою ставиться найбільш щільне розміщення елементів.

    Зазвичай хромосома в такому випадку містить список розміщуваних елементів, причому порядковий номер елемента в списку визначає чергу його розміщення на площині. Є п! варіантів розміщення.

    Кожен прямокутний елемент et в разі, якщо його довжина і ширина не рівні (widi М len,), може мати як горизонтальну (wid < len), так і вертикальну (wid > len) орієнтацію. Це вносить в рішення додаткову комбинативную мінливість. Таким чином, орієнтація елемента може бути задана змінної (orient), здатної приймати два значення: горизонтальна (orient = 1) або вертикальна (orient = 0). Тому для обліку двох видів орієнтації елементів при розміщенні пропонується використовувати диплоїдний (подвійний) набір хромосом.

    У такому випадку кожен батько містить не одну, дві хромосоми. При цьому нчльня популяція создется ТКІМ обрзом, що в пре хромосом одн з них містить послідовність елементів горизонтальної оріетнтаціі, друга - вертикальної. Таке жорстке розділення по орієнтації між хромосоммі одного з батьків не є принциповим; більш важливо те умова, щоб кожен з елементів мав обидва типи орієнтації в межах пари хромосом одного з батьків.

    Розглянемо приклад. Хромосома 3 2 5 4 1 0 Попереднє задає порядок розміщення елементів не площині: елемент 3 розміщується першим, за ним размещется елемент 2, за ним - 5 і т.д. Але так як всі ці елементи можуть бути орієнтовані двома названими способами, хромосома дублюється з урахуванням цієї обставини:

    000000 111111

    3 254 1 0 3 2 54 1 0

    chO chi

    Известия ТРТУ

    Тематичний випуск

    Нулі і одиниці, відповідні записаним в тих же позиціях елементів, вказують, відповідно, на горизонтальну і вертикальну орієнтацію цих елементів. Набір хромосом батька СН включає, таким чином, дві хромосоми: chO і chl.

    Кроссинговер в такому випадку пропонується проводити за наступною схемою.

    За основу взято кроссинговер, встановлений Поттером і дресслери в живій природі. Цей тип кросинговеру об'єднує одноточковий і двоточковий оператори кросинговеру і частково зберігає батьківські хромосоми, що робить його досить гнучким і універсальним. Не розглядаючи схему кросинговеру повністю, встановимо правила формування хромосом-нащадків з хромосом-батьків.

    Вихідними є два батьки, які містять по парі хромосом кожен, chl: 1111111 chi: 0000000

    ch2: 1111111 ch2: 0 0 0 0 0 0 0

    сні CH2

    В випадкової позиції встановлюється точка кросинговеру: chl: 11 11111 chl: 0 0 0 0 000

    ch2: 11 111 11 ch2: 00 000 00

    сні CH2

    Рспределения точок між хромосоммі проведено наступним обрзом. У CHl (chl) обрана точка кросинговеру. Їй відповідає така ж точка в CH2 (chl). У CHl (ch2) встановлюються дві точки кросинговеру: така ж, як в попередніх хромосомах, і інверсна, позиція якої дорівнює позиції вже встановленої точки, але отсчітивется справа. В СН2 (Сі2) точки кросинговеру ті ж, що в CHl (ch2). Обмін генетичним мтеріапом відбувається між хромосомами, в яких точки кросинговеру мають однакові позиції: CHl (chl) - CH2 (chI), CHl (ch2) - CH2 (ch2). Нащадки в цьому випадку виявляються наступними: chl: 1111111 chl: 1111111

    ch2: 1 1 0 0 0 0 0 ch2: 1 1 0 0 0 11

    СНЗ CH5

    chl: 00 1 1111 chl: 00 1 1100

    ch2: 0 0 0 0 0 0 0 ch2: 0 0 0 0 0 0 0

    CH4 CH6

    Так як хромосоми CH3 (chl) і CH5 (chl), а так само CH4 (ch2) і CH6 (ch2), мають такі самі генетичну інформцію, при вирішенні завдання будь-якої з двох хромосом в цих парах можна було б знехтувати. Однак, проведемо кроссинговер по розглянутій схемі Стосовно орієнтованим в двох напрямках елементам.

    Маємо два батька - Р1 і Р2 \

    11 1111 1 + 1 1111

    99 99 99 88 .888 8

    Р1 Р2

    00 0000 00 .00 00

    99 999 9 88 88 88

    або

    1 1 1111 1 1 1111

    32 54 10 3 2 54 1 0

    Р1 Р2

    00 0000 00 00 .00

    32 .54 10 3 2 .54 .1 0

    Цифри 9 і 8 использовния для наочності обміну генетичним матерьялом у відповідних рядках, як було сказано вище, знаходиться список елементів. Таким чином, в рядку, де записані «8», міститься один список елементів, в рядку з «9»-другий варіант розміщення.

    Точка кросинговеру вибирається випадково з позиції 1 до I /, де?, Довжина хромосоми. Друга, інверсна точка кросинговеру, встановлюється в тій же позиції, але при відліку справа.

    Після кросинговеру виходять такі нащадки (01 і 02) \

    00 1111 110011

    998888 998899

    01 02

    110000 00 1100

    8 8 9999 889988

    АБО

    001111 110011

    3 254 10 3 254 1 0

    01 02

    110000 00 1100

    3254 10 3254 10

    Можна бачити, що в хромосомах-нащадках елементи мають смішно орієнтацію, як вертикальну, так і горизонтальну. Слід, однак, врахувати, що при вирішенні такого завдання, як рзмещеніе, не використовується бінарне кодування: тут кожному елементу відповідає свій номер (ім'я), який записується в хромосому, причому номери Лемента в списку повторюватися не можуть. Ця проблема вирішується шляхом використання двох варіантів упорядкованого оператора кросинговеру: одноточечного і двухточечного Обмін

    генетичним матеріалом йде за відомими правилами з врахуй

    у Равіль з урахуванням орієнтації, як показано

    вище.

    В результаті виконання кросинговеру за запропонованою схемою отримані чотири

    різні хромосоми. При генетичному пошуку вони включаються в популяцію по

    певними правилами, отримавши попередньо оцінку. Надалі для проведення

    кросинговеру, всі хромосоми в популяції стають незалежними, щоб по

    певними правилами сформувати нові пари. Кожна з таких пао Є потенційним батьком. Р і мулисті-


    Завантажити оригінал статті:

    Завантажити