Таким образом, чтобы найти кратчайший путь от s к t с помощью алгоритма Дейкстры, достаточно начать поиск с вершины s и закончить его, когда вершина t добавится в очередь [12].

Алгоритм обхода препятствий А*. Предлагаемый алгоритм обхода препятствий основан на алгоритме Дейкстры. В англоязычной литературе он называется алгоритмом A* ("а"-звездочка) [14, 15].

Алгоритм реализуется в ряде предположений:

1) карта разбита на квадратные части, называемыми клетками (ячейками);

2) каждая клетка имеет несколько показателей:

* стоимость прохождения по этой клетке,

* предыдущая клетка - клетка, из которой пришли в эту клетку,

* статус клетки (нерассмотренная, граничная, отброшенная),

* оценка пройденного пути,

* оценка оставшегося пути;

3) имеются две клетки - начальная и конечная;

4) сосед клетки - клетка, в которую можно попасть из рассматриваемой за 1 шаг.

Общий принцип: на каждой итерации из всех граничных точек выбирается та, для которой сумма уже пройденного пути и пути до конца по прямой является минимальной, и от нее осуществляется дальнейшее продвижение.

Алгоритм итерационный. Опишем реализацию алгоритма пошагово. Начальные данные: Start - начальная клетка, Finish - конечная клетка.

1 шаг. Помечаем Start как граничную точку.

2 шаг. Среди всех граничных точек находим Клетку 1 - клетку с минимальной суммой оценки пройденного пути g и оценки оставшегося пути h.

3 шаг. Для Клетки 1 рассматриваем соседей. Если сосед имеет статус нерассмотренного, то мы обозначаем его как граничную клетку, и указываем Клетку 1 как предыдущую для него. Оценку g для соседа принимаем равной g+p, где p-стоимость прохождения по клетке-соседу, а g - оценка пройденного пути для Клетки 1. Оценка h для любой клетки равна длине кратчайшего пути (количеству ячеек на пути по прямой от рассматриваемой клетки до клетки Finish). Рассматриваемую Клетку 1 помечаем как отброшенную.

4 шаг. Если на предыдущем шаге один из соседей оказался равен клетке Finish, то путь найден. Если ни одного нового соседа не существует, то нет и пути.

5 шаг. Переход на шаг 2.

Алгоритм достаточно прост и в тоже время быстр. Он превосходит по скорости алгоритм Дейкстры (в общем случае) благодаря направленному поиску [14, 15].

Генетический алгоритм. Нейронные сети и генетические алгоритмы в настоящее время находят огромное число разнообразных применений. Действительно, в любой области человеческой деятельности есть задачи, для решения которых не существует определенного алгоритма или существующие алгоритмы очень сложны и требуют значительных вычислительных затрат, которые выходят за рамки возможностей современных ЭВМ. Нейронные сети и генетические алгоритмы являются универсальным средством для решения подобных задач, а также практически любых задач, которые возникают в человеческой деятельности [13].

В некоторых задачах, таких как прогнозирование, проектирование или распознавание образов, нейронные сети стали уже привычным инструментом. Ниже приведены некоторые из многочисленных способов использования нейронных сетей и генетических алгоритмов в различных областях [16]:

* обслуживание кредитных карточек;

* медицинская диагностика;

* распознавание речи;

* обнаружение фальсификаций;

* анализ потребительского рынка;

* прогнозирование объема продаж и управление закупками;

* проектирование и оптимизация сетей связи;

* прогнозирование изменений котировок;

* управление ценами и производством;

* разработка месторождений;

* исследование факторов спроса;

* прогнозирование потребления энергии.

Естественный отбор в природе. Эволюционная теория утверждает, что каждый биологический вид целенаправлен-но развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. В процессе эволюции многие виды насекомых и рыб приобрели защитную окраску, еж стал неуязвимым благодаря иглам, человек стал обладателем сложнейшей нервной системы. Можно сказать, что эволюция - это процесс оптимизации всех живых организмов. Рассмотрим, какими же средствами природа решает эту задачу оптимизации.

Основной механизм эволюции - это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом, благодаря передаче генетической информации (генетическому наследованию), потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает [16].

Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (дезоксирибонуклеиновая кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой. Каждое врожденное качество особи (цвет глаз, наследственные болезни, тип волос и т. д.) кодируется определенной частью хромосомы, которая называется геном этого свойства. Например, ген цвета глаз содержит информацию, кодирующую определенный цвет глаз. Различные значения гена называются его аллелями.

Рисунок 2.1 - Блок-схема работы генетического алгоритма

При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over - скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками. При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида [16].

Понятие и особенности генетического алгоритма. Пусть дана некоторая сложная функция (целевая функция), зависящая от нескольких переменных, и требуется найти такие значения переменных, при которых значение функции максимально. Задачи такого рода называются задачами оптимизации и встречаются на практике очень часто.

Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде. Вот как моделируется генетическое наследование:

* хромосома - вектор (последовательность) из нулей и единиц. Каждая позиция (бит) называется геном;

* индивидуум (генетический код) - набор хромосом, вариант решения задачи;

* кроссовер - операция, при которой две хромосомы обмениваются своими частями;

* мутация - случайное изменение одной или нескольких позиций в хромосоме.

Чтобы смоделировать эволюционный процесс, сгенерируем вначале случайную популяцию - несколько индивидуумов со случайным на-бором хромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания индивидуумов и смены поколений.

Жизненный цикл популяции - это несколько случайных скрещиваний (посредством кроссовера) и мутаций, в результате которых к популяции добавляется какое-то количество новых индивидуумов. Отбор в генетическом алгоритме - это процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее (рис. 2.1).

Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе. Приспособленность индивидуума - значение целевой функции на этом индивидууме. Популяция следующего поколения формируется из наиболее приспособленных особей. Чем больше приспособленность индивидуума, тем больше вероятность его участия в кроссовере, то есть размножении.

Таким образом, модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. Часто используется так называемая стратегия элитизма, при которой несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе. В любом случае каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов [16].

Итак, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм - это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время.

Алгоритм решения задачи коммивояжера. Рассмотрим применение генетических алгоритмов в классической задаче коммивояжера (TSP - travelling salesman problem). Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие новых различных методов (в том числе нейросетей и генетических алгоритмов).

Каждый вариант решения такой задачи - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче столько параметров, сколько городов в сети, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода. Но такой подход к решению задачи абсолютно невозможен при современных ЭВМ. Если в задаче все города связаны с каждым из остальных, то количество разных вариантов решения задачи (N?1)!/2, где N - количество городов в сети. При N=30 число вариантов решения 4,4Ч10³⁰. Для перебора этих вариантов понадобится много времени! И это только при 30 городах, когда как в практике задачи такого рода насчитывают сотни, и даже тысячи городов. В таких ситуациях на помощь приходят генетические алгоритмы, которые, хотя и не гарантируют нахождение оптимального решения, но позволяют найти одно из приемлемых решений задачи [16].

Построение генетического алгоритма начинается с конструирования двоичной хромосомы, представляющей возможные решения этой задачи. Традиционно генетические алгоритмы используют для этого двоичные строки фиксированной длины. Предположим, что задана сеть из 4-х городов, для кодирования каждого из которых понадобится 2 бита. Таким образом, хромосома будет иметь длину 1 байт. Например: "01_10_11_00".

Если следовать справа налево, то данная хромосома предполагает маршрут 0-3-2-1. Очевидно, что такой подход к построению хромосомы не из лучших, потому что может получиться так, что один город окажется в маршруте не один раз, что противоречит задаче. Подойдем к этой проблеме несколько иначе. Пусть число на j-ом месте означает не номер следующего города в маршруте, а номер города из оставшихся (не пройденных) городов. Так для нашего примера сначала 0-вой город, затем число 3 (11) показывает номер следующего города из оставшихся 1,2,3 (для 1-ого города номер 0, для 2-1 и для 3-2), так как число 3 превышает максимальный номер из оставшихся, то будем использовать вместо него остаток от деления его же на число оставшихся городов: 3 mod 3 = 0, то есть следующим городом в маршруте будет оставшийся город с номером 0, то есть 1-ый город, и так далее. Таким образом, при данном подходе не будет иметь место ситуация, когда один город окажется в маршруте не один раз. Заметим, что число на последнем месте хромосомы (самое левое) вовсе не нужно, так как остается один город (после прохождения трех), кодировать который нет необходимости. И еще важная поправка к хромосоме, заключается в том, что для кодирования очередного города необходимо не то количество бит, которое необходимо для хранения общего числа городов, а то, которое достаточно для кодирования числа оставшихся городов. Например, хромосома "01_10_11_00" преобразуется к виду (для того же маршрута) "1_10_00".

В результате мы уменьшили размер хромосомы с 8 бит до 5, что, во-первых, позволяет сэкономить оперативную память, во-вторых, уменьшить число возможных вариантов решения задачи (а также исключить невозможные "решения"). Второе качество является очень важным, так как эффективность генетического алгоритма тем выше, чем ниже число вариантов решения. Если одни города не имеют связи с некоторыми другими, то это также сокращает число вариантов решения.

Следующий этап построения генетического алгоритма - разработка так называемой фитнес-функции. Эта функция является единственной частью программы, которая должна понимать то, что действительно кодирует хромосома, и возвращать число, которое можно сопоставить с выживаемостью индивидуума в природе. Используя эту функцию, мы можем определить, насколько хорошо приспособлен индивидуум (насколько длинный маршрут). Так как количественной характеристикой решения в нашей задаче является длина пути, то примем в качестве значения фитнес-функции выражение "1/длина пути" (чем выше длина маршрута, тем ниже приспособленность).

Сначала генерируется определенное количество хромосом со случайными значениями (это количество обычно несколько сотен или тысяч). Результатом данного этапа является создание начальной популяции. Далее реализуется жизненный цикл популяции (случайное скрещивание, мутация) и отбор. Продолжать это нужно либо определенное количество раз (сотни, тысячи раз), или до тех пор, пока приспособленность не будет значительно изменяться.

Для каждой пары хромосом определяется случайным образом, будут ли они скрещиваться. Операция кроссовера предполагает выбрать также случайным образом, точку кроссовера. После этого две хромосомы обмениваются старшими частями (слева от точки кроссовера).

Например, даны две хромосомы: "10111" и "01100". Точка кроссовера может быть 1, 2, 3 или 4 (исходя из размера хромосомы - 5 бит). Пусть случайным образом определена точка 2, таким образом, хромосомы преобразуются в другие (рис. 2.2).

Рисунок 2.2 - Кроссовер хромосом

Дальнейший этап - это мутация. Частота мутации обычно очень низкая - отвечающая за нее виртуальная монетка должна падать орлом вверх один раз за сто или тысячу бросаний. А суть мутации заключается в том, что в некоторой хромосоме инвертируется некоторый бит.

И, наконец, происходит отбор индивидуумов в следующее поколение. Для реализации этой операции представим себе виртуальную рулетку, но такую, у которой секторы неодинаковые по ширине. Каждый сектор будет соответствовать какой-либо хромосоме, а ширина его будет пропорциональна приспособленности индивидуума. Теперь запустим рулетку столько раз, сколько индивидуумов в популяции. Та особь, на которую укажет остановившийся шарик, переходит в следующее поколение. Таким образом, шансы у наиболее приспособленных выше, чем у других, и в среднем число "хороших" решений будет расти с каждым очередным поколением.

Далее снова выполняем скрещивание, мутацию и отбор, и так далее до определенного условия. Этим условием может быть малое изменение приспособленности с каждым поколением или его отсутствие, либо процесс эволюции продолжается определенное количество раз (сотни, тысячи, возможно миллионы). И в самом конце выбираем особь с наибольшей приспособленностью. Это решение и будет максимально близким среди найденных к оптимальному решению задачи [16].

Важно отметить, что во всех этих операциях присутствует случайность, что необходимо для генетического алгоритма. Это повышает вариабельность решений.

2.2 Сценарий деятельности водителя-экспедитора на основе оптимизированной графовой модели и выбор способов его осуществления