close

Вход

Забыли?

вход по аккаунту

?

ИНСТРУКЦИЯ.254

код для вставкиСкачать
УДК 681.513.6
К ВЫБОРУ РАЗМЕРА ПОПУЛЯЦИИ
Ю.Р. Цой1, В.Г. Спицын2
В работе рассматривается связь размера популяции с другими параметрами генетического алгоритма. Описана найденная зависимость относительной приспособленности особей в различных поколениях для некоторых задач оптимизации. Высказано предположение о значимости величины средней относительной приспособленности в первом поколении.
Введение
Размер популяции является одним из основных параметров генетического алгоритма. Выбор размера популяции, при котором алгоритм показывает наилучшие результаты, является, в общем случае, нетривиальной задачей, поскольку комплексно зависит от других параметров генетического алгоритма, а также от поставленной проблемы.
Решение проблемы выбора размера популяции позволит в частности создать эффективную модель генетического алгоритма с динамически изменяющимся размером популяции. Это потенциально может дать выигрыш по количеству вычислений целевой функции по сравнению с алгоритмами с фиксированным размером популяции.
1. Связь размера популяции с другими параметрами генетического алгоритма
1.1. Неопределенность приспособленности строительных блоков. Теория строительных блоков была предложена Д.Голдбергом [Goldberg, 1989] и является расширением анализа генетических алгоритмов с использованием шаблонов. При анализе генетического алгоритма понятие особи удобно заменять строкой, представляющей ее бинарную, в большинстве случаев, хромосому. При этом часть строк в популяции будет иметь одинаковые значения в некоторых разрядах. Маска, содержащая заданные значения в таких разрядах, называется шаблоном (schema) популяции. Считается, что в процессе эволюции "выживают" те шаблоны, которые соответствуют более приспособленным особям [Holland, 1975]. Согласно теории строительных блоков успешность шаблона определяется наличием в его составе меньших структурных единиц с высокой приспособленностью - строительных блоков.
Определение приспособленности данного строительного блока всегда производится с некоторой погрешностью, т.к. сам блок может входить также и в состав плохо приспособленного шаблона. В малых популяциях оценка приспособленности шаблона производится при неоднозначности статистических данных, т.к. доля приспособленных шаблонов, содержащих строительный блок, может меняться довольно значительно от поколения к поколению. Это обстоятельство, в свою очередь, мешает сделать однозначный вывод о полезности самого блока. Увеличение размера популяции будет способствовать более точному определению приспособленности блока [Goldberg et al., 1991].
1.2. Распределение относительной приспособленности. Распределение приспособленности в данном поколении отражает состояние процесса поиска решения. Можно выделить два способа подсчета приспособленности:
* абсолютная приспособленность. Подсчитывается с использованием некоторой глобальной функции, зависящей только от решаемой задачи.
* относительная приспособленность. Вычисляется в каждом поколении по результатам оценки особей.
Поскольку абсолютная приспособленность обладает рядом очевидных преимуществ и дает возможность сравнивать результаты различных запусков алгоритма и временных срезов, она наиболее часто используется для анализа работы алгоритма. Кроме этого по значению абсолютной приспособленности можно судить о таких характеристиках, как сходимость популяции [Goldberg et al., 1991], потеря разнообразия, интенсивность отбора [Blickle et al., 1995].
Тем не менее по относительной приспособленности можно более корректно анализировать особенности работы ГА. Дело в том, что сам алгоритм "не знает" о существовании некоторой глобальной функции, и выбор особей для скрещивания определяется тем, насколько они лучше или хуже других особей в популяции.
График функции абсолютной приспособленности подобен графику целевой функции и не изменяется с ходом эволюции. Вид графика относительной приспособленности, напротив, зависит от многих параметров, в том числе и от размера популяции. Можно сделать предположение, что при увеличении числа особей в популяции он будет приближаться по виду к графику абсолютной приспособленности. В случае малой популяции вид графика может довольно значительно искажаться в силу неоднородности распределения точек, соответствующих особям, в пространстве поиска. При этом, с ходом эволюции искажение может быть все сильнее из-за следующих факторов:
* Увеличивается неоднородность распределения точек в пространстве ("скопление" особей в экстремумах).
* Так как происходит сужение пространства поиска, то информация о точках, лежащих вне диапазона, охватываемого текущей популяцией, теряется,
* С течением эволюционного поиска в популяции появляется все больше одинаковых особей, что уменьшает количество точек, по которым можно было бы восстановить график функции приспособленности.
В результате экспериментов по оптимизации сферической функции и функции Растригина была замечена интересная особенность. График относительной функции приспособленности в каждом следующем поколении повторяет некоторые характерные изломы графика приспособленности в предыдущем поколении. Пример для функции Растригина от одной переменной представлен на рис.1. а)
б)Рис. 1. Средние приспособленности в различных поколениях; а) n=1, поколение 1 и 2; б) n=1, поколение 2 и 3. При этом можно приближенно получить график относительной приспособленности в следующем поколении, если "отсечь" от текущего графика точки с приспособленностью меньше средней. Т.е. несмотря на то, что относительная приспособленность определяется только на основании данных из текущего поколения, обнаруживается связь между приспособленностью на различных этапах работы генетического алгоритма. Данный факт позволяет сделать предположение, что наибольшую роль играет вид графика относительной приспособленности в первом поколении, который напрямую зависит от размера популяции.
Необходимо отметить, что результаты получены по одному запуску алгоритма и, поэтому, не могут претендовать на общность. Тем не менее, они уже интересны и открывают новые возможности для исследования. Данные для первой переменной не уменьшают степень общности, т.к. переменные в хромосоме не зависят друг от друга, т.е. порядок их следования не важен, и генетические операторы работают независимо от числа переменных и их характеристик. Таким образом, можно предположить, что эффект зависимости графиков приспособленностей наблюдается как для других переменных, так и для произвольных участков хромосомы вообще. Также можно предположить, что с увеличением числа поколений зависимость будет все сильнее, ввиду постепенного вырождения популяции. Увеличение количества переменных, напротив, ослабит зависимость, т.к. растет число не учитываемых параметров.
1.3. Стратегия селекции. Применение различных стратегий отбора особей для скрещивания по-разному влияет на интенсивность отбора (selection intensity) и потерю разнообразия (diversity loss) в генетическом материале в популяции [Blickle et al., 1995]. Интенсивность отбора показывает, насколько сильно при выборе особей для скрещивания, будет отдаваться предпочтение более приспособленным особям. Чем выше интенсивность отбора, тем меньше шансы "плохих" особей. Потеря разнообразия характеризует скорость вырождения популяции. Стратегии с большой интенсивностью отбора способствуют более "решительному" и, как следствие, более быстрому поиску решения, однако в них значительна потеря разнообразия. Стоит отметить, что излишняя "робость" при отбрасывании плохо приспособленных особей может привести к тому, что для правильного выбора для скрещивания особей с высокой приспособленностью будет необходима избыточность в популяции. Т.е. необходимо большее число хорошо приспособленных особей, чтобы исключить из генетического поиска плохих особей. Иными словами, стратегии селекции со слабой интенсивностью отбора предположительно обладают достаточно малой эффективностью. Возможно из-за этого для удовлетворительной работы им необходима популяция большего размера, чем в случае с "решительными" стратегиями селекции.
1.4. Генетические операторы. Довольно важным является тот факт, что выбор приспособленных особей еще не гарантирует нахождение решения. Определяющую роль здесь играет разнообразие генетического материала и то, каким образом генетические операторы распределяют (map) особей в пространстве поиска.
Известно, что условно генетические операторы можно классифицировать по степени "разрушения" (смешивания) хромосом родителей на этапе репродукции. Так, например, одноточечные операторы считаются слаборазрушающими, в то время как однородный кроссовер является сильно разрушающим генетическим оператором. При этом, с точки зрения возможностей конструирования шаблонов, имеют преимущество более разрушающие операторы [Spears, 1998].
Взаимное влияние различных операторов скрещивания и размера популяции было исследовано в [De Jong et al., 1990, Spears, 1998]. Сделан вывод о том, что для малых популяций лучше подходят более разрушающие операторы, в то время как для популяций больших размеров лучше использовать операторы со средней разрушающей способностью, например, двухточечный кроссовер. Данный вывод можно объяснить тем, что различные операторы отличаются по возможности исследования пространства поиска. Иными словами, как много различных точек может быть получено с применением одного и того же оператора при скрещивании родительских особей. В малых популяциях наблюдается довольно быстрое вырождение, поэтому необходимо увеличить разнообразие получаемых особей с помощью сильноразрушающих операторов. В больших популяциях, напротив, генетического материала достаточно для ведения эффективного поиска, но важно по возможности максимально использовать найденные приспособленные шаблоны и составляющие их строительные блоки. Поэтому более целесообразно применять операторы со средней степенью разрушения.
1.5. Поисковые способности. Способность к исследованию пространства поиска с целью нахождения экстремумов можно считать совокупной характеристикой генетического алгоритма. Сюда же относятся возможности ГА выбираться из локальных оптимумов. Чем выше поисковые способности, тем больше вероятность, что алгоритм успешно решит поставленную задачу. Как упоминалось выше, поисковые способности можно "нарастить" за счет применения сильно разрушающих генетических операторов, стратегий отбора с малой интенсивностью отбора и увеличением размера популяции. При этом не должно существенно увеличиваться количество исследуемых точек с малой приспособленностью.
2. Гипотезы
В результате анализа результатов экспериментов по применению генетического алгоритма для различных задач оптимизации и собственных исследований был сформулирован ряд гипотез. В силу ограниченности размера статьи приводятся лишь их общие формулировки.
1. Существует оптимальный размер популяции (диапазон размеров популяции), при котором алгоритм показывает наилучшие результаты, и с точки зрения приспособленности полученного решения, и с точки зрения вычислительных затрат.
1.1. Следствие из гипотезы 1. Если принять конечный результат и вычислительные затраты за комплексную меру оценки работы ГА, то процесс поиска оптимального размера популяции можно свести к задаче оптимизации и воспользоваться "стандартными" средствами для ее решения (напр., метод "золотого сечения").
2. При найденном оптимальном размере популяции улучшение показателей работы алгоритма в большей степени возможно за счет других параметров (стратегия селекции, тип и вероятность генетических операторов и т.д.).
3. Чем меньший размер популяции необходим той или иной модели генетического алгоритма для решения некоторой задачи, тем более развитыми поисковыми способностями он обладает.
Заключение
На основании вышеизложенных гипотез можно предложить итерационную методику улучшения показателей работы генетического алгоритма. Сначала определяется оптимальный размер популяции, затем изменяется какой-либо параметр ГА. После этого снова определяется оптимальный размер популяции, и если он меньше предыдущего, то изменения можно считать успешными, в противном случае необходимо либо комплексное изменение параметров, либо использованная модификация генетического алгоритма признается хуже первоначальной.
Список литературы
[Goldberg, 1989] Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley, 1989.
[Holland, 1975] Holland J. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 1975.
[Goldberg et al., 1991] Goldberg D. E., Deb K. and Clark J. H. Genetic Algorithms, Noise and Sizing of Populations (IlliGAL Report No. 91010). Urbana, IL: University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, 1991.
[Blickle et al., 1995] T. Blickle, L. Thiele. A Comparison of Selection Schemes used in Genetic Algorithms (2nd Edition). TIK-Report No. 11. Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, 1995.
[Spears, 1998] Spears W. M. The Role of Mutation and Recombination in Evolutionary Algorithms. PhD Thesis. George Mason University, Fairfax, Virginia, 1998.
[De Jong et al., 1990] De Jong K. A., Spears W. M. An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms. // Proceedings of the Int'l Workshop Parallel Problem Solving from Nature.1990.
1 634034, Томск, ул. Советская 84, Институт "Кибернетический центр" Томского политехнического университета, neuroevolution@mail.ru 2 634034, Томск, ул. Советская 84, Институт "Кибернетический центр" Томского политехнического университета, spitsyn@ce.cctpu.edu.ru
---------------
------------------------------------------------------------
---------------
------------------------------------------------------------
Автор
manydocs12
Документ
Категория
Другое
Просмотров
361
Размер файла
62 Кб
Теги
инструкция, 254
1/--страниц
Пожаловаться на содержимое документа