Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. К ВЫБОРУ РАЗМЕРА ПОПУЛЯЦИИ Цой Ю.Р., Спицын В.Г. Кафедра Вычислительной техники Институт «Кибернетический центр» Томский политехнический университет

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Содержание 1. Введение 2. Связь размера популяции с параметрами генетического алгоритма 2.1. Неопределенность приспособленности строительных блоков 2.2. Распределение относительной приспособленности 2.3. Стратегия селекции 2.4. Генетические операторы 2.5. Поисковые способности ГА 3. Гипотезы 4. Заключение

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 1. Введение (1/2) Де Джонг (1975): увеличение размера популяции позволяет уменьшить потерю аллелей. определение вероятности мутации для канонического ГА через размер популяции. Де Джонг, Спирс (1990), Спирс (1998): исследуется взаимное влияние размера популяции и генетических операторов

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 1. Введение (2/2) Голдберг, Деб, Кларк (1991): уделяется внимание неопределенности приспособленности строительных блоков связь размера популяции и стратегий селекции Бликле, Тиеле (1995): связь между размером популяции и параметрами селекции.

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Содержание 1. Введение 2. Связь размера популяции с параметрами генетического алгоритма 2.1. Неопределенность приспособленности строительных блоков 2.2. Распределение относительной приспособленности 2.3. Стратегия селекции 2.4. Генетические операторы 2.5. Поисковые способности ГА 3. Гипотезы 4. Заключение

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (1/5) В малых популяциях оценка приспособленности шаблона производится при неоднозначности статистических данных, т.к. доля приспособленных шаблонов, содержащих строительный блок, может меняться довольно значительно от поколения к поколению. Это обстоятельство, в свою очередь, мешает сделать однозначный вывод о полезности самого блока. Увеличение размера популяции будет способствовать более точному определению приспособленности блока (Goldberg, Deb, Clark1991) Неопределенность приспособленности строительных блоков

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (2/5) Приспособленность: 1. Абсолютная - подсчитывается с использованием некоторой глобальной функции, зависящей от решаемой задачи 2. Относительная - определяется в каждом поколении по результатам оценки особей. Выбор особей для скрещивания определяется на основе информации об относительной приспособленности Распределение относительной приспособленности (1/4)

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (2/5) Причины искажения графика относительной приспособленности: увеличение неоднородности распределения точек в пространстве поиска (скопление особей в экстремумах); теряется информация о точках, лежащих вне диапазона, охватываемого текущей популяцией; с ходом эволюции в популяции появляется все больше одинаковых особей Распределение относительной приспособленности (2/4)

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (2/5) 2.2. Распределение относительной приспособленности (3/4)

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (2/5) 2.2. Распределение относительной приспособленности (4/4) Функция Растригина (n=1, N=20) Функция Растригина (n=10, N=20)

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (3/5) Размер популяции влияет на (Blickle, Tiele (1995)): интенсивность отбора (selection intensity) - изменение средней приспособленности в результате селекции разброс селекции (selection variance) - разброс значений приспособленности после селекции потеря разнообразия (loss of diversity) - утрата разнообразия генотипа в результате селекции 2.3. Стратегия селекции

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (4/5) - определение вероятности мутации (De Jong, 1975) Для малых популяций лучше подходят более разрушающие операторы, в то время как для популяций больших размеров лучше использовать операторы со средней разрушающей способностью (De Jong, Spears (1990), Spears (1998)) Генетические операторы

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 2. Связь размера популяции с параметрами ГА (5/5) Поисковые способности - эффективность исследования пространства поиска Поисковые способности ГА Размер популяции Интенсивность отбора Генетические операторы Поисковые способности

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Содержание 1. Введение 2. Связь размера популяции с параметрами генетического алгоритма 2.1. Неопределенность приспособленности строительных блоков 2.2. Распределение относительной приспособленности 2.3. Стратегия селекции 2.4. Генетические операторы 2.5. Поисковые способности ГА 3. Гипотезы 4. Заключение

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Гипотезы (1/2) 1. Существует оптимальный размер популяции (диапазон размеров популяции), при котором алгоритм показывает наилучшие результаты, и с точки зрения приспособленности полученного решения, и с точки зрения вычислительных затрат Следствие из гипотезы 1. Если принять конечный результат и вычислительные затраты за комплексную меру оценки работы ГА, то процесс поиска оптимального размера популяции можно свести к задаче оптимизации и воспользоваться стандартными средствами для ее решения (напр., метод золотого сечения).

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Гипотезы (2/2) 2. При найденном оптимальном размере популяции улучшение показателей работы алгоритма в большей степени возможно за счет других параметров (стратегия селекции, тип и вероятность генетических операторов и т.д.). 3. Чем меньший размер популяции необходим той или иной модели генетического алгоритма для решения некоторой задачи, тем более развитыми поисковыми способностями он обладает.

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Содержание 1. Введение 2. Связь размера популяции с параметрами генетического алгоритма 2.1. Неопределенность приспособленности строительных блоков 2.2. Распределение относительной приспособленности 2.3. Стратегия селекции 2.4. Генетические операторы 2.5. Поисковые способности ГА 3. Гипотезы 4. Заключение

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. 4. Заключение Адаптивная, динамическая, не зависящая от задачи стратегия выбора размера популяции: улучшение показателей работы ГА; создание более гибких моделей генетического алгоритма. Методика улучшения работы ГА: определение размера популяции, при котором генетический алгоритм дает наилучшие решения; изменение одного из параметров ГА. Наши планы

Цой Ю.Р., Спицын В.Г. К выбору размера популяции Интеллектуальные системы (AIS04), Россия, Дивноморское, 3-10 сентября, 2004г. Спасибо за внимание! Ваши вопросы