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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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