WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

Популяционно-генетические алгоритмы в процессе поиска работают не с решениями исходной задачи, а с их кодировками. Для того чтобы перейти от задач дискретной оптимизации к задаче генетического поиска, все решения из области допустимых решений D кодируются в виде строк в алфавите B, в S результате получаем пространство кодировок (также называемое Q пространством поиска). Значения критерия переводятся при помощи некоторого отображения, сохраняющего те же отношения предпочтения между кодировками, что и между соответствующими им решениями, в R+ - получаем функцию приспособленности (s) (критерий сравнения кодировок).

От выбора способа кодирования во многом зависит успех поиска решения.

О вычислительном эксперименте для сравнения эффективности различных методов кодирования для задачи коммивояжера будет рассказано ниже.

Рост приспособленности популяции в генетическом алгоритме происходит за счет «построения» генотипа из лучших аллелей (строительных блоков). Holland в фундаментальной теореме1 показал, что количество строительных блоков с высокой приспособленностью в популяции с течением времени будет расти экспоненциально. Эта теорема подтверждает теорию Докинза2, в которой предполагается, что при естественном отборе соревнование происходит не на уровне особей, а на уровне генов. Таким образом, выживают наиболее приспособленные аллели генов.

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

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

Holland, J.H., Adaptation in Natural and Artificial Systems/ J.H. Holland - Ann Arbor:

University of Michigan Press, 1975.

Докинз Р. Эгоистичный ген./ Р.Докинз- Пер. С англ. Пер. с англ. Н.О.Фоминой - М:

Мир – 1993 -316с.

Rudolph, G. Convergence Analysis of Canonical Genetic Algorithms./ G.Rudolph // IEEE Trans. on Neural Networks, special issue on Evolutionary Computation, vol. 5, no. 1, pages 96-101, Jan. 1994.

Потеря разнообразия мешает процессу адаптации решений при смене состояния среды. Использованные в работе методы, по-разному решают эту проблему:

метод гипермутации4 искусственно увеличивает генетическое разнообразие при смене состояния среды, методы с диплоидным5 и структурным6 представлением генотипа относятся к методам с неявным использованием памяти, в то время как метод с использованием базы опыта [2] явно использует внешнюю память.

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

Для сравнения эффективности алгоритмов в динамической среде важно знать следующее: его точность, его устойчивость (6), скорость реакции на изменения.

(t ) ( F(bestEA ) - MinFt) acc(t ) = (5) ( ( MaxFt ) - MinFt) stab(t) = max{0, acc(t-1) - acc(t)} (6) Для тестовых задач на максимум точность можно задавать формулой (5), (t) ( ( где F(bestEA) - лучшее найденное решение в поколении Pt, MaxFt ), MinFt ) - максимальное и минимальное значение критерия в текущий момент времени t. В ( ( MaxFt ), MinFt ) реальных задачах не известны, в этом случае их можно заменить верхней и нижней оценкой соответственно.

Генетические алгоритмы работают с кодировками решений исходной задачи. Часто выбор способа кодирования обусловлен особенностями задачи.

Одно из правил выбора метода кодирования основано на сохранении близости x1, x2, x3 D решений при кодировании. То есть если для решений выполняется d( xi, xj ) xi, xj d( x1, x2 ) d( x1, x3), где - расстояние между решениями, то и для i s1, s2, s3 S, si = (x ),i = 1,кодировок должно выполняться (s1, s2 ) (s1, s3 ), Cobb H. An Investigation into the Use of Hypermutation as an adaptive Operator in Genetic Algorithm Having Continuous, Time-Dependent Nonstationary Environments. / H.Cobb //Naval Research Laboratory Memorandum Report 6760. (1990).

Smith R. E. Diploidy and Dominance in Artificial Genetic Search / R. E. Smith, D. E.

Goldberg // Complex Systems, V.6, 1992, ph. 251—285.

Dasgupta,D. (1992): SGA: A Structured Genetic Algorithm./ D.Dasgupta, D. R. McGregor //Technical report no. IKBS-8-92, University of Strathclyde.

j где (si, s ) - расстояние между кодировками. Введем понятие расстояния для бинарных векторов и перестановок.

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

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

Для гарантии получения допустимых кодировок (кодировок, которым соответствуют решения из области D) существуют различные методы.

При решении задачи о ранце для гарантии допустимости получаемого решения автором предложено два метода: метод модификации генотипа и метод штрафных функций [3,8]. Метод модификации генотипа основан на приведении исходного генотипа к ближайшему допустимому генотипу при помощи алгоритма, основанного на теореме Данцига7. Метод штрафных функций основан на принципе уменьшения шансов на выживание у недопустимых решений, для этого можно понижать их приспособленность. Используя метод штрафов, на приспособленность особи, фенотип которой является недопустимым решением, налагается штраф, то есть приспособленность снижается и особь имеет меньше шансов к воспроизведению и переходу в следующее поколение.

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

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

Сигал, И.Х. Введение в прикладное дискретное программирование./ И.Х. Сигал, А.П.

Иванова - 2007г.- М. Физматлит 304с.

Lin S. An effective heuristic algorithm for the traveling salesman problem. / S.Lin, B.W.

Kernighan //Oper.Res,1973,v.21,#2,p.498-516.

В диссертации предлагается новый подход к применению генетического алгоритма для решения задач коммивояжера большой размерности. Метод основан на декомпозиционном подходе: исходная задача разбивается на подзадачи меньшей размерности – непересекающиеся регионы, число регионов 2 M. В каждом регионе при помощи популяционно-генетического метода N находится минимальный гамильтонов путь, размерность каждой из этих задач меньше исходной: 3 Ni < N,i = 1, M, где N – размерность исходной задачи, Ni - размерность регионов. Гамильтоновы пути, являющиеся решением каждой подзадачи, «сшиваются», образуя решение исходной задачи (гамильтонов цикл).

При этом не только поиск решения подзадач, но и само разбиение на подзадачи происходит при помощи генетического алгоритма.

Для реализации этого подхода предложено использование ярусного генотипа, в верхнем ярусе находятся регионы, а в нижнем города из этих регионов. Для ярусного представления разработаны специальные операторы, гарантирующие допустимое разбиение на регионы и построение гамильтонова цикла. Метод был опробован на известных тестовых задачах (в частности Oliver’s-30, Eilon’s-50, Eilon’s-759), на них получены результаты [6], повторяющие лучшие известные.

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

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

В диплоидном алгоритме5 для кодирования решений используется диплоидный генотип, состоящий из двух хромосом (против одной в гаплоидном), это позволяет дольше поддерживать разнообразие популяции (поскольку генотип содержит больше информации). В работе доказаны утверждения об изменении пропорции аллелей диплоидных алгоритмов с разными алфавитами кодирования Oliver I. A study of permutation crossover operators on the traveling salesman problems. / I.Oliver, D.Smith, J.R. Holland //Proc. оf the Second International Conf. on Genetic Algorithms, 1987,p.224- во времени, на основании которых можно сделать выводы о поведении алгоритмов на различных отрезках постоянства.

Известные в литературе диплоидные алгоритмы используют бинарный алфавит кодирования. В диссертации предлагается оригинальный диплоидный генетический алгоритм, основанный на перестановочном кодировании генотипа [13]. Для него описаны варианты операторов кроссовера и мутации. Этот алгоритм специально разработан для нестационарной задачи коммивояжера.

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

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

Рис. 2. Структура программного комплекса.

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

Для сравнения эффективности различных алгоритмов на задаче о ранце рассматривался класс задач (7), в которых от времени зависит только главное весовое ограничение Wmax (t). Рассматривались два случая: с двумя и с четырьмя различными состояниями среды. Параметрами тестовой задачи является размерность задачи - 30, 100 и 650 предметов, количество различных весовых ограничений - два весовых ограничения, составляющих 50%и 90% от суммарного веса всех предметов, и четыре, составляющих 25%, 50%, 75% и 90% от суммарного веса всех предметов, порядок следования ограничений (для 4х ограничений).

n xivi max i=n (7) xi wi Wmax (t) i=xi {0,1}, i = 1, n Для получения тестовых задач использовалась программа-генератор, для каждой размерности тестировалось задачи с некоррелированными значениями веса и ценности предметов.

Таблица 1 Задача о ранце размерности 650; два весовых ограничения.

среднее число средняя стабильность вычислений точность Подход с памятью 1715.71 0.001312 0.Структурный подход 1719.29 0.00264 0.С модификацией 1715.71 0.002683 0.Диплоидный подход 1715.71 0.002395 0.Гипермутация вероятность 0.1 1715.71 0.012458 0.Гипермутация вероятность 0.5 1785.36 0.012124 0.Метод штрафов 1715.71 0.013798 0.Подходы сравнивались по точности, среднему количеству затраченных на поиск оптимума вычислений и стабильности. Результаты эксперимента (Таблица 1) показали, что подход с использованием базы опыта (в таблице обозначен:

«Подход с памятью») имеет лучшие результаты эффективности, что обуславливается продолжением адаптации при повторении состояния среды.

Заметим, что этот алгоритм использует в качестве базового гаплоидное представление с применением штрафов для недопустимых решений («Метод штрафов»), но по показателям точности превосходит базовый алгоритм более чем в два раза.

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

Диплоидный подход занимает четвертое место по показателям эффективности. На задаче с двумя ограничениями точность алгоритма 0.7375, с четырьмя ограничениями - 0.5046, Такое поведение алгоритма соответствует его особенностям: смена доминантности позволяет из одного генотипа получить два различных решения. Остальные подходы на задачах о ранце имеют точность ниже 50%.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»