СодержаниеСодержание
СОДЕРЖАНИЕ 2
1. ВВЕДЕНИЕ 3
1.1. АННОТАЦИЯ 3
1.2. ГЛОССАРИЙ 3
1.3. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 3
1.4. НЕФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 6
1.5. ПРИНЦИПЫ РАБОТЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 9
1.5.1. Сущность генетических алгоритмов 9
1.5.2. Основные операции в генетических алгоритмах 12
1.5.3. Особенности представления решений и выполнения операций в задаче коммивояжера 13
1.6. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ 16
1.6.1. Аналогичные (конкурирующие) решения 16
1.6.2. Описание предшествующих работ 18
1.6.3. Вывод 19
2. ТРЕБОВАНИЯ К ОКРУЖЕНИЮ 20
2.1. ТРЕБОВАНИЯ К АППАРАТНОМУ ОБЕСПЕЧЕНИЮ 20
2.1.1. Требования для локальной версии и к серверной части 20
2.1.2. Требования к клиентской части 20
2.2. ТРЕБОВАНИЯ К ПРОГРАММНОМУ ОБЕСПЕЧЕНИЮ 20
2.2.1. Требования для локальной версии 20
2.2.2. Требования для серверной части 20
2.2.3. Требования для клиентской части 20
2.3. ТРЕБОВАНИЯ К ПОЛЬЗОВАТЕЛЯМ 20
3. АРХИТЕКТУРА СИСТЕМЫ (ОБЩИЕ ТРЕБОВАНИЯ) 22
4. СПЕЦИФИКАЦИЯ ДАННЫХ 23
4.1. ФОРМАТ ВХОДНЫХ ДАННЫХ 23
4.2. ФОРМАТ ВЫХОДНЫХ ДАННЫХ 23
5. ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ 24
5.1. ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ К ЛОКАЛЬНОЙ ВЕРСИИ 24
5.2. ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ К WEB-ВЕРСИИ 24
6. ТРЕБОВАНИЯ К ИНТЕРФЕЙСУ 26
7. ПРОЕКТ 29
7.1. СРЕДСТВА РЕАЛИЗАЦИИ 29
7.2. МОДУЛИ И АЛГОРИТМЫ 29
7.2.1. Подготовка данных из shape-файлов 30
7.2.2. Алгоритм решения задачи коммивояжера методом ветвей и границ 31
7.2.3. Генерация хромосом 31
7.2.4. Генетический алгоритм решения задачи коммивояжера 32
7.2.5. Адаптивный генетический алгоритм решения задачи коммивояжера 32
7.3. СТРУКТУРЫ ДАННЫХ 33
7.4. ПРОЕКТ ИНТЕРФЕЙСА 36
8. РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ 38
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41
1.ВведениеВведение
1.1. Аннотация
Работа посвящена исследованию генетических алгоритмов и возможностям их применения в решении транспортных задач. В работе показано преимущество генетических алгоритмов по сравнению с традиционными подходами к решению сложных задач оптимизации на примере задачи коммивояжера.
В данной работе автор предлагает модификацию генетического алгоритма, названную адаптивным генетическим алгоритмом. Адаптивный алгоритм, в отличие от обычных, подбирает наиболее эффективные представления решений и операции для каждой задачи на разных этапах ее решения, что позволяет решать задачи быстрее и точнее.
Алгоритм был реализован автором. Проведенные тесты подтвердили его эффективность. Также были получены интересные результаты о распределении операций при решении задач с помощью данного алгоритма. Имеются направления для дальнейших разработок и исследований.
1.2. Глоссарий
ГА — генетические алгоритмы. Алгоритмы, позволяющие решать многие сложные задачи оптимизации, зачастую не имея информации о специфике решения задачи. Они основаны на генетических процессах биологических организмов. Подражая этим процессам, генетические алгоритмы моделируют среду, в которой «развиваются» соответствующим образом закодированные решения реальных задач.
ЗК — задача коммивояжера. Данная задача является так называемой NP-трудной задачей, т.е. задачей, точное решение которой в общем случае может быть получено только за экспоненциальное время. Следовательно, необходим алгоритм, способный находить приблизительное решение, достаточно близкое к точному, за приемлемое время. Формулировка задачи приводится в пункте «Неформальная постановка задачи».
1.3. Описание предметной области
Современный мир состоит из огромного количества различных коммуникаций и сетей — это автомобильные и железные дороги, трубопроводы телефонные линии, линии электропередач и компьютерные сети. Целесообразно эффективное использование сетей, поэтому транспортные задачи, а точнее их решения, в современном мире находят очень широкое применение. Компаниям, занимающимся транспортировкой грузов или доставкой товаров, ежедневно необходимо выбирать оптимальные маршруты посещения сотен клиентов. Маршрутизаторы и коммутаторы телефонных линий и компьютерных сетей определяют кратчайшие пути коммутации клиентов. Системы круиз-контроля, являющиеся неотъемлемым атрибутом качественного автомобиля, способны выбрать для вас оптимальный маршрут с учетом большого количества различных параметров и ограничений.
Для решения таких задач были разработаны алгоритмы, находящие точные или приблизительные решения. Но по сей день существует большой круг задач, для которых еще не изобретены достаточно быстрые алгоритмы, которые при этом бы давали точное решение или очень близкое к нему. Например, одна из основных транспортных задач — задача коммивояжера (ЗК) — есть NP-трудная задача, и, следовательно, не имеет решения полиномиальной сложности. Алгоритмы перебора «в лоб» позволяют решить ЗК для 10–15 городов, так как для N городов потребуется проверить N! маршрутов, что для 30 пунктов составит порядка 2.65 x 1032 маршрутов. Более сложные алгоритмы перебора (например, широко известный метод ветвей и границ [26]) может решить ЗК для сотни городов, но даже и в этом случае может встретиться такой набор входных данных, на которых алгоритм не сможет решить ЗК за приемлемое время (например, алгоритм долго работает на симметричных матрицах). Введение в задачу дополнительных ограничений (временные рамки или порядок посещения для некоторых городов) также приводит к усложнению алгоритма и дальнейшему увеличению времени, требуемого для нахождения решения задачи. Подобный алгоритм уже был реализован автором, подробный отчет можно найти в [19].
Другой подход в решении таких задач — это поиск субоптимального решения, то есть некоторого локального оптимума задачи. Такие методы идеально работают, когда в задаче существует один глобальный оптимум. Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение.
Согласованность и эффективность работы элементов биологических организмов навела людей на мысль — а нельзя ли использовать принципы биологической эволюции для оптимизации практически важных для человека систем? В нескольких модификациях подобные идеи возникали у ряда авторов уже давно. В 1966 году Л. Фогель, А. Оуэнс, М. Уолш предложили схему эволюции логических автоматов, решающих задачи прогноза [31]. В 1975 г. вышла основополагающая книга Дж. Холланда «Адаптация в естественных и искусственных системах» [10], в которой был предложен генетический алгоритм, исследованный в дальнейшем учениками и коллегами Дж. Холланда в Мичиганском университете. Примерно в это же время группа немецких ученых (И. Рехенберг, Г.-П. Швефель и др.) начала разработку так называемой эволюционной стратегии. Эти работы заложили основы прикладного эволюционного моделирования или эволюционных алгоритмов. В нашей стране исследования по прикладному эволюционному моделированию, идейно близкие к работам Л. Фогеля с сотрудниками, были разносторонне развиты в работах И.Л. Букатовой [17].
Что же такое генетические алгоритмы? ГА — это адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие, например, как пища или вода. Кроме того, члены популяции одного вида часто конкурируют за привлечение брачного партнера. Те особи, которые наиболее приспособлены к окружающим условиям, будут иметь относительно больше шансов воспроизвести потомков. Слабо приспособленные особи либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространяться в увеличивающемся количестве потомков на каждом последующем поколении. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению потомка, чья приспособленность больше, чем приспособленность любого из его родителей. Таким образом, вид развивается, лучше и лучше приспосабливаясь к среде обитания.
Подражая этому процессу, генетические алгоритмы способны «развивать» решения реальных задач, если те соответствующим образом закодированы. Они работают с совокупностью «особей» — популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. Как и в биологической эволюции, в генетических алгоритмах используется механизм мутаций — случайным образом изменяются отдельные особи. Мутации позволяют исследовать новые области поверхности решенийЛитератураСписок литературы
1. ARC/INFO Data Management, Copyright © 1994 Environmental Systems Research Institute, Inc.
2. Arc View Network Analyst. Руководство пользователя, М.,1999.
3. ESRI Shapefile Technical Description, An ESRI White Paper — July 1998.
4. FAQ по мягким вычислениям. Russian FAQ Archivs (10 января 2003 года).
5. Fredman M. L., Johnson D. S., McGeocht L. A., Ostheimeri G., Data Structures for Traveling Salesmen. © ACM. искать “GA AND TSP”. (11 мая 2003 года).
6. Freisleben B., Merz P., A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems, Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, pp. 616 – 621, 1996.
(8 мая 2003 года).
7. Freisleben B., Merz P., Genetic Local Search for the TSP: New Results, Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, IEEE Press, pp. 159 – 164, Indianapolis, USA, 1997.
(8 мая 2003 года).
8. GeneBase — библиотека компонентов для Delphi, реализующая генетические алгоритмы. Лаборатория BaseGroup. (3 февраля 2003 года).
9. Goldberg D. E., Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.
10. Holland J. H., Adaptation in Natural and Artificial Systems, Ann Arbor, MI: The University of Michigan Press. 2nd edn. (1992) Boston, MA: MIT Press.
11. Julstrom B. A., Coding TSP tours as permutations via an insertion heuristic. © ACM. искать “GA AND TSP”. (11 мая 2003 года).
12. Julstrom B. A., Very Greedy Crossover in a Genetic Algorithm for the Traveling Salesman Problem, St. Cloud State University. искать “GA AND TSP”. (11 мая 2003 года).
13. Katayama K., Narihisa H., A New Iterated Local Search Algorithm using Genetic Crossover for the Traveling Salesman Problem, Okayama University of Science. искать “GA AND TSP”. (11 мая 2003 года).
14. LaLena M., Traveling Salesman Problem Using Genetic Algorithms. (3 февраля 2003 года).
15. Using ArcLogistics Route, Copyright © 1998 Environmental Systems Research Institute, Inc.
16. Батищев Д. И., Исаев С. А., "Оптимизация многоэкстремальных функций с помощью генетических алгоритмов" (опубликовано в сборнике статей, издаваемом ВГТУ, осень 1997).
17. Букатова И. Л. Эволюционное моделирование и его приложения. М.: Наука, 1979. 231 с.
18. Генетические алгоритмы: почему они работают? когда их применять? Журнал «Компьютерра» — 1999 — №11. (3 февраля 2003 года).
19. Демичев Д. А., Отчет по курсовой работе «Решение задач сетевого анализа средствами ГИС», ДВГУ, 2002.
20. Демичев Д. А., Решение транспортных задач с помощью генетических алгоритмов. XXX ЮБИЛЕЙНАЯ МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT + SE'03. МАЙСКАЯ СЕССИЯ. Украина, Крым, Ялта-Гурзуф, 19 – 28 мая, 2003 г. В печати.
21. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.
22. Журнал Hizone info новости Hi-Tech технологий, выпуск от 16 августа 2002 года. (3 февраля 2003 года).
23. Исаев С. А., Генетические алгоритмы — эволюционные методы поиска. (27 февраля 2003 года).
24. Исаев С. А., Разработка и исследование генетических алгоритмов для принятия решений на основе многокритериальных нелинейных моделей, автореферат диссертации на соискание ученой степени кандидата технических наук, Н.Новгород, 2000. (27 февраля 2003 года).
25. Компания НейроПроект, программные продукты и алгоритмы искусственного интеллекта, GeneHunter. (27 февраля 2003 года).
26. Кристофидес Н., Теория графов, Алгоритмический подход, М., «Мир», 1978.
27. Курс по генетическим алгоритмам. (29 декабря 2002 года).
28. Стариков А., Генетические алгоритмы — математический аппарат, лаборатория BaseGroup. (3 февраля 2003 года).
29. Струнков Т., Что такое генетические алгоритмы, PC Week RE, 19/99. (27 февраля 2003 года).
30. Турчанов С. В., MapControl — инструментальное средство разработки ГИС-приложений. XXIX МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT + SE'2002. МАЙСКАЯ СЕССИЯ. Украина, Крым, Ялта-Гурзуф, 20 – 30 мая, 2002 г. С.399–401.
31. Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. 230 с.
|
|
