Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра електронних обчислювальних машин Звіт про виконання лабораторної роботи №3(4) з курсу „ Дослідження комп'ютерних систем штучного інтелекту ” Тема: Застосування генетичних алгоритмів для вирішення задачі комівояжера Львів – 2007 Мета: ознайомитись з методами вирішення задач за допомогою генетичних алгоритмів та використати даний алгоритм для вирішення задачі комівояжера. Теоретичні відомості Задача комівояжера у стандартній постановці виглядає так: є набір міст, потрібно відвідати найкоротшим шляхом всі міста, але кожне місто відвідується лише раз і повернутись до відправного пункту. Формально TSP можна вирішити наступним чином: Даними є: натуральні числа n ≥ 3 i маршрут C =(cij), де cij - ітераційний підрахунок, що циклічно змінюється. EMBED Equation.3
 TSP є відносно старою проблемою. Вперше вона була сформульована Ейлером в 1759 році (але під іншою назвою), якій хотів розв”язати проблему шахового коня. Правильне розв”язання повинно містити шлях шахового коня по всіх 64 шахових клітинах, так щоб на кожній клітині поля кінь побував лише один раз. Термін ‘travelling salesman’ вперше був застосований в 1932 році у німецькій книзі, присвяченій вирішенню задачі комівояжера. Після багатьох років, проблема комівояжера дочекалась на багато способів розв”язання. Існує декілька причин цього. По перше TSP є дуже простим в описуванні, але важким у розв’язанні. Не знаємо жодного алгоритму, що розв’язує це завдання миттєво в баготовимірному часі. Цей недолік алгоритму, що розв’язує завдання багатовимірному часі є характерним для проблем, відомих під назвою NP – повних, для яких проблема комівояжера є класичним прикладом. По друге, TSP має застосування в багатьох різних проблемах, що зачіпають різного роду шляхи і пункти. По трете, по мірі отримання багато інформації на тему проблеми комівояжера, згодом її можна використовувати як свого роду тестову задачу, нові комбанаторні методи часто тестуються на TSP, з метою переконання в їх приктичній здатності. І зрештою велика кількість проблем, в яких маємо відповідно до завдань штучного інтелекту, призводять до знаходження найкращої permutacji n елементів. Представлення і оператори Відомо багато різних способів представлення здатних до розв”язування проблеми комівояжера за допомогою генетичних алгоритмів. Деякі з них як бінарі рішення чи маршрутне рішення використовують бінарні значення для представлення даного шляху. Хоча таке рішення є стандартом в світі генетичних алгоритмів, однак для задачі комівояжера проблемою є те, що оператори схрещуваня і мутації можуть давати погані наслідки. Для того мусимо залишити сформульовані оператори виправлень. Найкращим природнім способом представлення шляху є вигляд представлення. В цьому представленні n міст, які мають розмістити пункти відвідувань в n-елементний ланцюжок таким чином, що якщо і-те місто знаходиться в j-ій позиції за рахунком, це означає, що і-те місто відвідане як j-те. Таке представлення дозволяє сформулювати велику кількість різних операторів схрещування і мутації. Можна стверджувати, що на даний час більшість генетичних алгоритмів, що заходять приблизне розв”язання задачі комівояжера вживають таке представлення. Вагомою причиною для того є інтуїтивна простота і природність представлення, а також добрі наслідки, отримані при його застосуванні Бінарне представлення В бінарному представленні задачі комівояжера для n-міст, кожне місто закодовано у ланцюжок довжиною [log2 n] бітів. Одиночне рішення зрештою є ланцюжком, довжиною n*[log2 n] бітів. Наприклад, при шістьох містах кожне місто представлено ланцюжком довжиною у 3 біти Шлях 1-2-3-4-5-6 представлятиметься: 000 001 010 011 100 101 Зауважимо, що існують 3-бітові ланцюжки. З них не кодують жодного міста: 110 і 111 Класичне схрещування (Classical Crossover) Оператор класичного схрещування був запропонований Голандом (1975). Нижще розглянемо для прикладу два шляхи, кожен з яких складаться з шістьох міст 000 001 010 011 100 101 101 100 011 010 001 000 Потім випадковим чином вибираємо точку схрещування, я якій кожен з ланцюжків буде поділено на дві частини. Припустимо наприклад, що точка схрещування вибрана між 9 та 10 бітом, тобто 000 001 010 | 011 100 101 101 100 011 | 010 001 000 З’єднавши дві різні частини кожного з ланцюжків, отримуємо нащадків 000 001 010 010 001 000 101 100 011 011 100 101 Які не представляють виправляючих шляхів. Щоб змінити створених нащадків потребуємо певного роду корегуючі алгоритми(repair algorithm). Загалом алгоритм має за мету трансформацію особин, що не належать до простору пошуків в особини, які до неї належать Класична мутація (Classical Mutation) Оператор класичної мутації також був запропонований Голандом, Neguje він один або декілька бітів особини до правдоподібної мутації, яка є наближеною до нуля. Наприклад розірвемо поновлений ланцюг, який представляє шлях 1-2-3-4-5-6: 000 001 010 011 100 101 Припустимо, що 1 та 2 біт були вибрані для мутації. Вибрані біти поміняємо на протилежні. В наслідок цього отримуємо ланцюг: 110 001 010 011 100 101 Який знов не представляє власний шлях. Згодом знов треба врахувати в скеровуючому алгоритмі. Виконання роботи void FindMinWay(int level) { int other,prevP; for(int i=0;i<size;i++) { int j=0; other=1; while ((j<level)&& other) { if(matTmp[j]==i) other=0; j++; }; if (other) { matTmp[level]=i; if (level==0){LengthTmp=0;} else { prevP=matTmp[level-1]; LengthTmp=LengthTmp+mat[prevP][i]; }; level++; if(level<size)FindMinWay(level); if ((level==size)&&(LengthTmp<=LengthMin)) { if(LengthTmp == LengthMin) {amount++;} else {LengthMin = LengthTmp; amount = 1;}; for(int k=0;k<size;k++)matMin[amount][k]=matTmp[k]; }; if (level==size) { printf( "Pointers:"); for (int z = 0; z < size; z++) printf( "%d ",matTmp[z]); printf("TmpLength is %d\n",LengthTmp); } ; level--; if (level!=0)LengthTmp=LengthTmp-mat[prevP][i]; }; }; } Висновок: в даній лабораторній роботі я ознайомився з рішенням задач класифікації методом генетичних алгоритмів. Написав програму по рішенню задачі комівояжера з використанням генетичних алгоритмів.