N57_4 (1108551)
Текст из файла
УДК 519.856В.А. МоровПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА К ЗАДАЧАМ ОПТИМИЗАЦИИ.РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ЗАДАЧИ КОММИВОЯЖЕРАВ статье рассматриваются применение генетического алгоритма кзадачам оптимизации и реализация его для задачи коммивояжера.Описаны основные элементы алгоритма и построенная программа длядостижения поставленной цели.Application of genetic algorithm to the optimization problems and algorithm’srealization for the Traveling Salesman Problem (TSP) is considered in thisarticle.
There are described common elements of the algorithm andconstructed program of solution of the problem.ВведениеЗадачей оптимизации в математике, информатике и исследовании операций называетсязадача нахождения экстремума (минимума или максимума) целевой функции в некоторой областиконечномерного векторного пространства, ограниченной набором линейных и/или нелинейныхравенств и/или неравенств.В процессе проектирования обычно ставится цель определить в некотором смысленаилучшие структуру или значения параметров объектов. Такая задача называетсяоптимизационной. Если оптимизация связана с расчетом оптимальных значений параметров призаданной структуре объекта, то ее именуют параметрической оптимизацией. Задача выбораоптимальной структуры является структурной оптимизацией.Стандартная математическая задача оптимизации формулируется таким образом. Средиэлементов x, образующих множество X, найти такой элемент x*, который доставляет минимальноезначение f(x*) заданной функции f(x).
Чтобы корректно поставить задачу оптимизации,необходимо задать: допустимое множество X; Целевую функцию — отображение f : X → R;критерий поиска (max или min).Если минимизируемая функция не является выпуклой, то часто ограничиваются поискомлокальных минимумов и максимумов – точек x0 таких, что всюду в некоторой их окрестностиf ( x) ≥ f ( x0 ) для минимума и f ( x) ≤ f ( x0 ) – для максимума.Если допустимое множество X =Rn, то такая задача называется задачей безусловнойоптимизации, в противном случае – задачей условной оптимизации.В зависимости от природы множества X задачи математического программированияклассифицируются как:задачи дискретного программирования (или комбинаторной оптимизации), если X конечноили счетно;задачи целочисленного программирования, если X – подмножество множества целыхчисел;задачи нелинейного программирования, если ограничения или целевая функция содержатнелинейные функции и X является подмножеством конечномерного векторного пространства.Если же все ограничения и целевая функция содержат лишь линейные функции, то этозадача линейного программирования.Существует множество методов оптимизации, которые можно разделить на три группы:детерминированные; случайные (стохастические); комбинированные.В частности, большой интерес представляют собой эволюционные методы, являющиесястохастическими.
Упоминания о применении генетических алгоритмов для решения задачиоптимизации относятся к концу 1960-х гг. Эволюционные методы основываются на примереработы эволюции и обучения, к таким методам относят нейронные сети, генетическиеалгоритмы[1].Генетический алгоритм – это эвристический алгоритм поиска, используется для решениязадач оптимизации и моделирования путем случайного подбора, комбинирования и вариацииискомых параметров с применением механизмов, напоминающих биологическую эволюцию,является разновидностью эволюционных вычислений. Отличительная особенность генетическогоалгоритма – акцент на использовании оператора «скрещивания», производящего операциюрекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живойприроде[1]. Схематически алгоритм представлен на рис. 1.Для применения алгоритма задачи приводятся к виду, при котором решение может бытьпредставлено как набор более мелких составных частей (аналог генотипа и его составных частей –генов).
Длина генотипа может быть как фиксированной, так и переменной.Сам алгоритм состоит из нескольких шагов.0. Подготовительный шаг – формирование начальной популяции (начального наборарешений). Алгоритм для формирования может быть различным, но чаще всего используютслучайный процесс с целью охватить большее разнообразие для поиска решений. Возможноприменение других способов формирования, – например, с заранее известными свойствами, носледует иметь в виду, что это может повлиять на ход развития системы в дальнейшем.1. Отбор – важный этап в алгоритме, отвечает за выбор направления развития популяций,чаще всего отбрасываются решения с низким значением функции приспособленности (fitnessfunction), что способствует улучшениесредней приспособленности всей популяции.2.
Скрещивание – этап, на которомпроисходит образование новых решений впопуляции, прошедшей через отбор, длявосстановления численности. Особенностьего в том, что при использованиискрещивания берутся два или болеесуществующих решений в популяции, а изних – составные части (гены) и соединяются вновом решении, которое остается впопуляции.3. Скрещивание не позволяет в полноймере охватить все возможные вариантысочетаний и значений генов, поэтому неменее важен процесс мутации. Он состоит втом, что в некоторых решениях из популяциипроисходят случайные изменения в генах.Рис. 1.
Схема работы генетического алгоритма.Этот процесс способствует увеличениюразнообразия в популяции.4. Оценка решений и остановка алгоритма – в большинстве случаев; если для решениязадачи необходимо применять генетический алгоритм, то нет критерия останова, основанного насамих решениях, вместо него применяется подход с числом вычислений (числом создаваемыхпопуляций).
Иногда останов можно производить заранее, если возможен случай вырожденияпопуляций.Основными шагами алгоритма являются шаги с 1 по 4, один проход по которым «создаетновую популяцию».Эвристические алгоритмы позволяют решать практически любые задачи оптимизации. Ноих эффективность ниже, чем у локальных методов. Таким образом, фактически данныеалгоритмы, хотя и могут использоваться для решения любых задач, чаще всего применяются кзадачам, для которых не разработаны специальные локальные методы или решение такимиметодами является при заданных параметрах неэффективным [2].К подобным задачам можно отнести очень популярную задачу оптимизации – задачукоммивояжера. При определенных условиях решение ее с помощью известных точных методовстановится невозможным из-за большого числа вариантов.
Рассмотрим эту задачу подробнее.Задача коммивояжера – одна из самых известных задач комбинаторной оптимизации,заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные городахотя бы по одному разу, с последующим возвратом в исходный город. В условиях задачиуказываются критерий выгодности маршрута (кратчайший, самый дешевый, совокупный критерийи т.п.) и соответствующие матрицы расстояний, стоимости и т.д. Как правило, указывается, чтомаршрут должен проходить через каждый город только один раз – в таком случае выборосуществляется среди гамильтоновых циклов[3].Существует несколько частных случаев общей постановки задачи, в частности:геометрическая задача коммивояжера (также называемая планарной или евклидовой, когдаматрица расстояний отражает расстояния между точками на плоскости);треугольная задача коммивояжера (когда на матрице стоимостей выполняется неравенствотреугольника);симметричная и асимметричная задачи коммивояжера.Существует и так называемая обобщенная задача коммивояжера[3].Решим данную задачу с помощью генетического алгоритма.Постановка задачи коммивояжераРассмотрим метрическую задачу коммивояжера, когда расстояния между городами можновычислить (аналог точек на плоскости).
При данной постановке задачи мы имеем: число городов,координаты каждого города на плоскости:{g = (x, y )}, i = 1, n.Таким образом, расстояние между городами можно находить как расстояние между двумяточками:() (xS gi , g j =i− xj) + (y2i− yj)2Необходимо найти такой путь через города g i , чтобы суммарное расстояние былиминимальным.Построение генетического алгоритма для задачи коммивояжераДля применения генетического алгоритма необходимо определить основные структурныеэлементы: вид элемента популяции, процесс скрещивания, мутации и вид фитнесс-функции.За элемент популяции (одно возможное решение) принимаем маршрут через все города.Каждый такой маршрут является возможным решением и не противоречит условиям задачи, хотяможет быть совсем не оптимальным. Предполагаем, что все элементы популяции корректны, т.е.все они – потенциальные решения поставленной задачи и не являются противоречивыми.В качестве фитнесс-функции мы принимаем функцию вида:S=∑ S (g , g ),iji , j∈Pгде Р – множество всех связей в маршруте.Данная функция определяет минимизируемый параметр и позволяет оцениватьполучаемые решения.Метод мутации реализуется следующим образом: выбираем случайный город; находимсвязи соответствующие этому городу; соединяем соседние города прямой связью (исключаемвыбранный город из этой связи); вставляем город в случайное место.Пример.Предположим, что решение до мутации имеет вид, представленный на рис.
2.Рис. 2. Решение до мутации.Применяя к нему алгоритм мутации, можем получить решение в виде представленном нарис. 3.Рис. 3. Решение, но после мутации.Метод скрещивания реализуется сложнее, так как требует дополнительных проверок накорректность получаемого маршрута.Алгоритм метода скрещивания:выбираем два маршрута из популяции, которые будут выступать в роли родителей;в образуемые маршруты переносим связи, которые существуют в обоих маршрутах-родителях;при несовпадающих связях предпочтение отдается связи в первом родителе для городов счетными номерами; если ее применить невозможно, то берем связи из второго родителя(предпочитаются связи из второго маршрута для городов с нечетными номерами), если это такженевозможно, то берем из первого маршрута.При таком задании скрещивания для получения двух решений можно применять данныйметод дважды, меняя маршруты-родители местами.
Тогда второй потомок будет получен приусловии, что при несовпадении связей предпочтение будет отдаваться второму маршруту.Пример. На рис. 4 представлен пример применения данного алгоритма скрещивания кдвум решениям:Р1:123451Р2:14254533Рис. 4. Пример «скрещивания».Анализ полученных результатовПрименяя данный алгоритм при различных начальных условиях (размер популяций,процент мутаций, вес ближайших городов), получаем различные результаты.1) 15 городов.Размер популяции 1000, 15% мутации, вес ближайших городов 0%.Результаты:число итераций до вырождения: 1200,время выполнения: 0.321 с,погрешность от оптимального (если возможно посчитать): <5%.2) 40 городов.Размер популяции 10000, 15% мутации, вес ближайших городов 0%.Результаты:число итераций до вырождения: 143000 / 375000,время выполнения: 4.3 с / 9 с.3) 40 городов.Размер популяции 10000, 5% мутации, вес ближайших городов 50%.Результаты:число итераций до вырождения: 101000,время выполнения: 3.7 с.Последние два примера: первое минимально найденное значение с погрешностью междуними в 3% было найдено менее чем за 5 сек.
Последующие решения отличаются погрешностьюменьше 1%. При правильном задании размеров начальной популяции и процента мутации можноускорить работу алгоритма.1. Гладков, Л.А. Генетические алгоритмы: Учебное пособие / Л.А. Гладков, В.В. Курейчик, В.М.Курейчик.
– Изд. 2-е. – М.: Физматлит, 2006. – 320 с.22. Курейчик, В.М. Поисковая адаптация: теория и практика / В.М. Курейчик, Б.К. Лебедев, О.К.Лебедев. – М.: Физматлит, 2006. – С. 272.3. Johnson, D.S., McGeoch, L.A. The traveling salesman problem: a case study. Local search in combinatorialoptimization / D.S.
Johnson, L.A. McGeoch. – Chichester: Wiley. – Р. 215-310..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
