shkolageo.ru 1


К ВЫБОРУ РАЗМЕРА ПОПУЛЯЦИИ

  • Цой Ю.Р., Спицын В.Г.

  • Кафедра Вычислительной техники

  • Институт «Кибернетический центр»

  • Томский политехнический университет

  • neuroevolution@mail.ru


Содержание

  • 1. Введение

  • 2. Связь размера популяции с параметрами генетического алгоритма

  • 2.1. Неопределенность приспособленности строительных блоков

  • 2.2. Распределение относительной приспособленности

  • 2.3. Стратегия селекции

  • 2.4. Генетические операторы

  • 2.5. Поисковые способности ГА

  • 3. Гипотезы

  • 4. Заключение



1. Введение (1/2)

  • Де Джонг (1975):

  • увеличение размера популяции позволяет уменьшить потерю аллелей.

  • определение вероятности мутации для канонического ГА через размер популяции.

  • Де Джонг, Спирс (1990), Спирс (1998):

  • исследуется взаимное влияние размера популяции и генетических операторов



1. Введение (2/2)

  • Голдберг, Деб, Кларк (1991):

  • уделяется внимание неопределенности приспособленности строительных блоков

  • связь размера популяции и стратегий селекции

  • Бликле, Тиеле (1995):

  • связь между размером популяции и параметрами селекции.




2. Связь размера популяции с параметрами ГА (1/5)

  • В малых популяциях оценка приспособленности шаблона производится при неоднозначности статистических данных, т.к. доля приспособленных шаблонов, содержащих строительный блок, может меняться довольно значительно от поколения к поколению. Это обстоятельство, в свою очередь, мешает сделать однозначный вывод о полезности самого блока. Увеличение размера популяции будет способствовать более точному определению приспособленности блока (Goldberg, Deb, Clark1991).


2. Связь размера популяции с параметрами ГА (2/5)

  • Приспособленность:

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

  • 2. Относительная - определяется в каждом поколении по результатам оценки особей.

  • Выбор особей для скрещивания определяется на основе информации об относительной приспособленности.



2. Связь размера популяции с параметрами ГА (2/5)

  • Причины искажения графика относительной приспособленности:

  • увеличение неоднородности распределения точек в пространстве поиска (“скопление” особей в экстремумах);

  • теряется информация о точках, лежащих вне диапазона, охватываемого текущей популяцией;

  • с ходом эволюции в популяции появляется все больше одинаковых особей.







2. Связь размера популяции с параметрами ГА (3/5)

  • Размер популяции влияет на (Blickle, Tiele (1995)):

  • интенсивность отбора (selection intensity) - изменение средней приспособленности в результате селекции

  • разброс селекции (selection variance) - разброс значений приспособленности после селекции

  • потеря разнообразия (loss of diversity) - утрата разнообразия генотипа в результате селекции


2. Связь размера популяции с параметрами ГА (4/5)

  • - определение вероятности

  • мутации (De Jong, 1975)

  • Для малых популяций лучше подходят более разрушающие операторы, в то время как для популяций больших размеров лучше использовать операторы со средней разрушающей способностью (De Jong, Spears (1990), Spears (1998)).


2. Связь размера популяции с параметрами ГА (5/5)

  • Поисковые способности - эффективность исследования пространства поиска.





Гипотезы (1/2)

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

  • 1.1. Следствие из гипотезы 1. Если принять конечный результат и вычислительные затраты за комплексную меру оценки работы ГА, то процесс поиска оптимального размера популяции можно свести к задаче оптимизации и воспользоваться “стандартными” средствами для ее решения (напр., метод “золотого сечения”).



Гипотезы (2/2)

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

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




4. Заключение

  • Адаптивная, динамическая, не зависящая от задачи стратегия выбора размера популяции:

  • улучшение показателей работы ГА;

  • создание более гибких моделей генетического алгоритма.

  • Методика улучшения работы ГА:

  • определение размера популяции, при котором генетический алгоритм дает наилучшие решения;

  • изменение одного из параметров ГА.



Спасибо за внимание!

  • Ваши вопросы