|
|
eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Інформатика, кібернетика та обчислювальна техніка >
Випуск 1 (17) >
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://ea.donntu.ru/handle/123456789/29697
|
| Название: | Усовершенствование метаэвристических методов для решения задачи поиска оптимального маршрута |
| Другие названия: | Удосконалення метаевристичних методів для рішення завдання пошуку оптимального маршруту
Improvement of metaheuristic methods for solving the problem of optimum route search |
| Авторы: | Федоров, Е.Е.
Мартынова, О.П.
Слесорайтите, Э.
Федоров, Є.Є.
Мартинова, О.П.
Слесорайтите, Е.
Fedorov, Ye.Ye.
Martynova, O.P.
Sliesoraityte, E. |
| Ключевые слова: | генетический алгоритм
алгоритм клонального отбора
имитация отжига
искусственная иммунная система
поиск оптимального маршрута
генетичний алгоритм
алгоритм клонального відбору
імітація відпалу
штучна імунна система
пошук оптимального маршруту
genetic algorithm
clonal selection algorithm
annealing imitation
artificial immune system
optimum route search |
| Дата публикации: | 2013 |
| Издатель: | ДонНТУ |
| Библиографическое описание: | Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка : збірник статей. Вип.1 (17) / ДВНЗ "ДонНТУ" ; редкол.: О.Є. Башков (голов. ред.) та ін. - Донецьк : ДонНТУ, 2013. |
| Аннотация: | В данной работе рассматриваются такие метаэвристические методы поиска оптимального маршрута как генетический алгоритм, который основан на механизмах естественной эволюции, и алгоритм клонального отбора, основанный на особенностях иммунных систем. Для повышения вероятности выбора оптимального маршрута и уменьшения времени поиска в статье была осуществлена модификация операторов этих алгоритмов, которая использует имитацию отжига для учета начальных и конечных стадий работы алгоритмов. Для исследования разработанных модификаций в статье проведено численное исследование. |
| Описание: | Now the city of Donetsk plays one of the key roles in transportation of various cargoes. It becomes the “air gate” between the West and the East, international automobile highways pass through this city, etc. In these conditions the important role is played by transport logistics. One of the main tasks of transport logistics is to find the optimum route between points. This task employs such artificial intelligence methods as Hopfield neural network, annealing imitation method, tabu search, ant algorithm, genetic algorithm, clonal selection algorithm, etc. The latter two have been improved in this work. The advantage of the offered genetic algorithm updating is that at early stages of its work equiprobable selection for the reproduction operator, outbreeding for the crossingover
operator and the equiprobable scheme of the reduction operator are used. That ensures examination of the entire search space (random selection of chromosomes), and at final stages linearly ordered selection for the reproduction operator, inbreeding for the crossingover operator and the selection scheme of the reduction operator are used; it makes the search guided (current best chromosomes remain). Besides, the offered updating does not require scaling and can be used in case of fitness function minimization that is important for the minimum routesearch. The advantage of the offered updating of the clonal selection algorithm is that at early stages of its work all antibodies are cloned, new antibodies are added and the equiprobable scheme is applied. It ensures examination of the entire search space and at final stages only the best antibodies are cloned, new antibodies are not added and the selection scheme is used, which makes the search guided. The both updatings have increased the speed of search by 20%, and the probability the optimum route choice by 5%. The offered improved metaheuristics can be applied in automatic and automated computer systems for optimum route calculation when solving logistic and communication problems. |
| URI: | http://ea.donntu.org/handle/123456789/29697 |
| Располагается в коллекциях: | Випуск 1 (17)
|
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.
|
