В роботі запропоновано адаптивний генетичний алгоритм для вирішення завдання комівояжера, на основі модифікованого оператора кросинговеру. Також представлений програмний комплекс, написаний на основі даного алгоритму.

Анотація наукової статті з математики, автор наукової роботи - Полуян А. Ю.


Adaptive algorithm for the decision of problems of optimization on the basis of strategy of elitism

In this article the adaptive genetic algorithm for the decision of postmans on the basis of the modified operator of crossingoveris offered. Also the program complex written on the basis of given algorithm is presented.


Область наук:

  • Математика

  • Рік видавництва: 2008


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Адаптивний алгоритм для вирішення завдань оптимізації на основі стратегії елітизму'

    Текст наукової роботи на тему «Адаптивний алгоритм для вирішення завдань оптимізації на основі стратегії елітизму»

    ?УДК 681.31

    А.Ю. Полуян

    АДАПТИВНИЙ АЛГОРИТМ ДЛЯ ВИРІШЕННЯ ЗАВДАНЬ ОПТИМІЗАЦІЇ НА ОСНОВІ СТРАТЕГІЇ Елітизм

    При вирішенні оптимізаційних задач успішно використовують стратегії, концепції, методи і механізми еволюційного моделювання на основі бионического пошуку. Біонічне пошук - це послідовне перетворення одного кінцевого нечіткої множини альтернативних рішень в інше. Саме перетворення називається генетичним алгоритмом (ГА). Мета ГА полягає в тому, щоб [1]:

    | Пояснити абстрактно і формально адаптацію процесів в природному середовищі і інтелектуальної інформаційної системи;

    |

    рішення оптимізаційних задач науки і техніки.

    Завдання про мінімальний шляху як одна з найважливіших оптимізаційних задач була обрана об'єктом дослідження, тому, що техніка її рішення добре відома і вивчення нового методу на цьому завданню дозволить в подальшому з його допомогою вирішувати інші, більш складні завдання, які в даний момент вирішувати важко. Відзначимо, що завдання про мінімальний шляху відноситься до класу № повних проблем [2]. Основною трудністю вирішення цих завдань, є попередня збіжність алгоритмів, тобто попадання рішення в локальний оптимум. Тому доцільно використовувати ГА для вирішення зазначеного завдання. Останнім часом в області досліджень, спрямованих на підвищення ефективності генетичних алгоритмів, велике значення придбали ідеї створення адаптивних генетичних алгоритмів, які можуть змінювати свої параметри в про. , Які в процесі роботи змінюють розмір популяції. Ідея адаптивних генетичних алгоритмів отримала своє втілення в концепції підлогу, що представляє багаторівневі генетичні алгоритми. Нижній рівень такого алгоритму безпосередньо виконує завдання поліпшення популяції рішень. Верхні рівні представляють собою генетичні алгоритми, вирішальні оптимізаційних задач щодо поліпшення параметрів алгоритму нижнього рівня. При цьому в якості цільової функції використовується зазвичай швидкість роботи алгоритму нижнього рівня і швидкість поліпшення їм популяції від покоління до покоління.

    Основна особливість генетичного алгоритму полягає в тому, що аналізується не одне рішення, а деяку підмножину квазіоптимальних рішень, які називаються хромосомами і складаються з генів. Це підмножина носить назву "популяція". У даній реалізації початкова популяція формується випадок.

    включається хромосома, яка описувала маршрут по "жадібному" алгоритму. Для даної задачі хромосома описує послідовність номерів вершин

    .

    Для хромосоми обчислюється цільова функція? (К), де до - маршрут, що описує-. -

    .

    .

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

    К1 = (1 - 80) * ЯР,

    де 80 - ступінь оновлення популяції, ЯР - розмір популяції.

    Після формування початкової популяції, здійснюється процес синтезу нових рішень (поколінь) завдання за допомогою кросинговеру і мутації. Вихідними даними для нього є хромосоми поточної популяції. Досліджувана в певний момент часу популяція називається поточної. На початку роботи алгоритму поточна популяція збігається з початковою.

    Даний генетичний алгоритм пропонує ліквідувати наявні перетину в маршрутах, використовуючи оператор інверсії, а також застосувати до кожної хромосомі операцію різноманітності. Операція різноманітності вносить деякі зміни в окрему хромосому.

    Адаптивний генетичний алгоритм підтримує таку архітектуру гені,

    новоствореним хромосомами.

    Після схрещування і мутації розмір популяції збільшується. Однак для наступних перетворень необхідно скоротити число хромосом поточної популяції. Така процедура носить назву селекції. У поточній популяції, що складається з батьків і нащадків, проводиться відбір кращих рішень, тобто хромосом з найкращим значенням ШпеББ-функції (цільової функції).

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

    ШпеББ-функції. Таким чином, для адаптивного генетичного алгоритму виділяється чотири основних етапи:

    1);

    2) ();

    3) ( -

    );

    4) селекція поточної популяції.

    ,

    , -

    лення. Тому воно змінюється від спроби до спроби. Для отримання найкращого результату роботи генетичного алгоритму рекомендується зробити кілька спроб (3-5).

    Загальну схему генетичного алгоритму можна представити таким про:

    1. .

    2. "" .

    3. .

    Крок 4. Порядковий номер спроби 1 = 1 (/ = 1, КР). (КР - кількість спроб) Крок 5. Формування початкової популяції / -ої поп иткі.

    Крок 6. Цілеспрямована зміна хромосом початкової популяції.

    Крок 7. Порядковий номер генерації / '- ой поп иткі} = 1 (} = 1, ТО).

    Крок 8. Виділення еліти і формування поточної / '- ой популяції.

    Крок 9. Схрещування хромосом в / '- ой популяції.

    Крок 10. Мутація х Ромоса в / '- ой популяції.

    11. .

    Крок 12. Додавання но вих хромосом к / '- ой популяції.

    Крок 13. Селек ція в / '- ой популяції.

    14. / - .

    Крок 15. Перехід до наступної популяції: / = / + 1.

    16. / ТО, 8, -

    маршруту / '- ой спроби. (ТО - число генерацій)

    Крок 17. Перехід до наступної спроби: 1 = 1 + 1.

    Крок 18. Якщо 1<КР, то перехід до кроку 5, інакше визначення найкращого маршруту за час роботи алгоритму.

    Крок 19. Висновок результуючого маршруту.

    У кожній популяції хромосоми можуть піддаватися діям різних операторів. При цьому відбуваються процеси, аналогічні діям, які трапляються в природному генетиці. До основних операторів відносять: оператор скре-

    , , , -.

    В даному алгоритмі реалізовані модифіковані оператори кросинги-віра і мутації. Оператор кроссинговера є модифікованим, так як в ньому передбачений механізм, що виключає виникнення "нелегальних" рішень. Такими рішеннями вважаються хромосоми, що не відповідають умові завдання.

    Загальну схему реалізованого оператора схрещування можна уявити:

    Крок 1. Вибрати хромосому з кращим значенням цільової функції Е (к) в ті, .

    Крок 2. Порядковий номер ітерації 1 = 1.

    Крок 3. Згенерувати випадкове число гпё, причому 0<Тьо<1.

    Крок 4. Якщо гпё < РБ, то вибрати / '- у хромосому в поточній популяції в якості другого з батьків, застосувати операцію схрещування до обраних хромосомами і запам'ятати одержані нащадків.

    Крок 5. Перехід до наступної ітерації: 1 = 1 + 1.

    Крок 6. Якщо / < ЯР (р ^ заходів популяції), то перейти до кроку 3.

    7. .

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

    Оператор селекції формує нове покоління з хромосом з кращими значеннями цільової функції? (К). Він знищує більшу частину популяції і освіжає генетичний матеріал, поповнюючи популяцію великою кількістю нових .

    ЯР.

    Оператор інверсії змінює характер зв'язків між компонентами хромосоми. Він бере хромосому, випадковим чином вибирає в ній дві точки розриву і

    , [3].

    Оператор різноманітності також вносить зміни в окремого індивідуума, але це дуже невеликі зміни в кожній хромосомі, а не сильна зміна

    хромосоми, як відбувається при мутації. Вони відносяться до початкової популяції. З метою поліпшення значення цільової функції кожна хромосома обробляється ітераційним алгоритмом оператора різноманітності, заснованим на методі циклічного координатного спуску. Ідея методу полягає в тому, що його ітерація (цикл) складається з послідовності кроків. В ході кроку роботи ітераційного алгоритму суміжні хромосоми попарно розглядаються і замінюються хромосомами мінімально можливої ​​довжини. Тому в процесі реалізації кожного кроку значення цільової функції Е (к) поліпшуються. Якщо зміни цільової функції Е (к) для двох останніх ітерацій не перевищили задану точність е, то ітераційний алгоритм оператора різноманітності припиняє свою роботу.

    Критерій зупинки алгоритму може бути різним. Можна задати фіксований число генерацій. Можна на кожній ітерації отримане рішення порівнювати з оптимальним, поки не буде досягнута бажана точність.

    Для підвищення швидкості роботи алгоритму пропонується паралельна обробка інформації. Існує гіпотеза, що в паралельній системі з п процесорами, продуктивність кожного з яких дорівнює одиниці, загальна продуктивність зростає як log2n [1].

    Для даного алгоритму розроблений програмний комплекс розв'язання задачі комівояжера. На рис. 1 зображений результат роботи генетичного алгоритму до, -полненія алгоритму. Менш жирна смужка - найкраще рішення, знайдене на даному етапі, а більш жирна - загальна якість популяції, тобто середньоарифметичне усіх рішень на даному етапі, посередині відображається діаграма. Якщо навести курсор на будь-який з стовпців, то з'явитися підказка про крок, до якого . ,

    .

    Аналіз отриманих даних свідчить про те, що запропонована в роботі стратегія використання генетичного алгоритму дозволяє: отримувати набір оптимальних рішень, є гнучкою, володіє високою швидкодією (15% -30%) на одних і тих же вхідних даних, в порівнянні з іншими алгоритмами. ВСА = Ю (п2).

    Мал. 1. Стовпчасті діаграма значень ЦФ на послідовних ітераціях

    СПИСОК

    1. Гладков Л.А., Курейчик В.М, Курейчик В.В. Генетичні алгоритми. - Ростов-на-Дону: Ростіздат, 2004.

    2. Ахо А., Хопкрофта Дж., Ульман Д. Побудова і аналіз обчислювальних алгоритмів. -М .: Світ, 1979.

    3. ГладкоеЛ.А. Генетичні оператори. - Таганрог Вид-во: ТРТУ, 2005

    4. ., . . .

    - М .: Мир, 1985.

    УДК 687.06

    ..

    РОЗРОБКА ГЕНЕТИЧНОМУ МОДЕЛІ ПОШУКУ ПРОСТИХ ЧИСЕЛ

    Криптоанализа RSA НА ОСНОВІ клієнт-серверних

    СТРУКТУРИ

    Вступ. Сучасні протоколи передачі даних, такі як SSL, TLS, PGP, що забезпечують захист інформації, що передається, використовують криптосистему RSA для встановлення захищеного з'єднання і розподілу ключів шифрування. Надійність криптосистеми RSA обумовлює захищеність пере.

    У сучасному світі спостерігається тенденція переходу від використання класичних детермінованих алгоритмів до інтелектуальних пошукових систем, систем автоматизованого управління та проектування. Основними напрямками в розробках інтелектуальних систем в даний час є еволюційні вероятностно-спрямовані методи. Яскравим прикладом таких методів є генетичні алгоритми (ГА), орієнтовані на пошук глобального оптимуму в просторі можливих рішень з багатоекстремального .

    Сьогодні генетичні алгоритми успішно застосовуються для вирішення класичних NP-повних задач, задач оптимізації в просторах з великим количест-, .

    Постановка задачі. Всі асиметричні криптосистеми характеризуються тим, що використовують два ключі: один для шифрування, інший для дешифрування, які мають певну залежність. В асиметричних криптосистемах

    RSA. , RSA,

    представлена ​​формулою (1):

    f: х-> xe (mod m). (1)

    Для дешифрування повідомлення a = f (x) досить вирішити рівняння (2):

    xe = a mod m. (2)

    При деяких умовах, що накладаються на m і е, це порівняння має єдине рішення х [1]. Якщо показник ступеня е в порівнянні з (2) взаємно простий з

    (M) (), (2) .

    знайти, необхідно визначити число d, що задовольняє умові (3):

    de = 1 (mod (^ (^))), (3)


    Ключові слова: ГЕНЕТИЧНИЙ АЛГОРИТМ /ПОКОЛІННЯ /Популяція /СЕЛЕКЦІЯ /ОПЕРАТОРИ /кросинговері /МУТАЦІЯ /інверсія /Завдання комівояжера /GENETIC ALGORITHM /GENERATION /POPULATION /SELECTION /OPERATORS /CROSSINGOVER /A MUTATION /INVERSION /A PROGRAM COMPLEX /A PROBLEM OF THE DIRECT-SALES REPRESENTATIVE

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

    Завантажити