ОДИН СПОСОБ ВЫЧИСЛЕНИЯ ВРЕМЕНИ СМЕШИВАНИЯ ДЛЯ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ СКРЕЩИВАНИЯ * Цой Ю.Р Кафедра вычислительной техники, Томский политехнический университет. - презентация

1 ОДИН СПОСОБ ВЫЧИСЛЕНИЯ ВРЕМЕНИ СМЕШИВАНИЯ ДЛЯ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ СКРЕЩИВАНИЯ * Цой Ю.Р Кафедра вычислительной техники, Томский политехнический университет * Работа выполнена при поддержке РФФИ (проект )

2 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Введение Рассматривается задача определения времени смешивания для 1- и 2-точечного операторов кроссовера (ОК) для целочисленного кодирования Несмешанная популяцияСмешанная популяция Строка 1: Строка 2: Строка 3: Строка 4: Строка 5: Строка 1: Строка 2: Строка 3: Строка 4: Строка 5:

3 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Содержание доклада 1. Вводные замечания 2. Вывод оценок времени смешивания 3. Результаты экспериментов 4. Анализ результатов 5. Заключение

4 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Вводные замечания Способность к смешиванию – одна из основных характеристик ОК, определяющая способности ОК к созданию различных пар хромосом потомков, отличных от хромосом родителей. Таким образом, считается, что 1-точечный кроссовер имеет наименьшие способности к смешиванию, а однородный ОК (Syswerda G. (1989)) – наибольшие. Оценки времени смешивания: Rabani Y., Rabinovich Y., Sinclair A. (1998) + Prugel-Bennett A. (2001) ( L – длина строки): 1-, и 2-точечный ОК (соответственно 1 и 2 ) O( LlnL ) однородный ОК O( lnL ) Prugel-Bennett A. (2001):

5 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Вывод оценок времени смешивания (1/4) Одна из проблем анализа эволюционных алгоритмов: необходимость рассмотрения эволюции популяции особей. В рамках решения задачи определения времени смешивания достаточно анализировать только 1 особь «Стандартный» подходПредлагаемый способ анализа XXXXX XXXXX XXXXX XXXXX Строка 1: Строка 2: Строка 3: Строка 4: Строка 5: Строка 1: Строка 2: Строка 3: Строка 4: Строка 5: Х – любой символ

6 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Вывод оценок времени смешивания (2/4) Считаем, что, – размер популяции. Рассмотрим ГА без селекции и мутации. Тогда для анализа времени смешивания для ОК достаточно вычислить время, необходимое для попадания точек разрыва ОК в каждую возможную позицию внутри строки Возможные точки разрыва Случайные точки разрыва Схема «без возврата» (случай 2-точечного ОК) Кроссовер

7 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Вывод оценок времени смешивания (3/4) 1-точечный ОК ( 1 ): Возможные точки разрыва

8 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Вывод оценок времени смешивания (4/4) 2-точечный ОК ( 2 ): Возможные точки разрыва, что совпадает с результатом Пругеля- Беннета (2001) n-точечный ОК ( n ):

9 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Результаты экспериментов (1/2) Рассматривается ГА без селекции и мутации. Начальная популяция – несмешанная. – мощность алфавита, n – размер популяции, L – длина строк Мера смешанности для строки: Инициализация Скрещивание Мера смешанности популяции:

10 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Результаты экспериментов (2/2) 1-точечный ОК2-точечный ОК Результаты усреднены по 100 запускам

11 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Анализ результатов (1/3) Если x 0 – доля строк в популяции, содержащих символы, то скорость увеличения x 0 пропорциональна x 0 (1- x 0 ) – вероятности скрестить строки, из которых только одна содержит символы из. Можно записать: Почему формулы, полученные при рассмотрении случая n >> L, оказываются верными для случая n = L ? где – коэффициент, зависящий от используемого ОК, > 0.

12 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Анализ результатов (2/3) пример Увеличение на начальных этапах компенсируется уменьшением на конечном этапе моделирования, что и позволяет рассматривать «выбывание» фиксированного числа точек разрыва по очереди. Предположение:

13 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Анализ результатов (2/2) популяция селекция t ~ nlnn t ~ n t ~ lnn кроссовер t ~ LlnL t ~ lnL мутация предположительно * ~ n ~ L ~ N ~ P m -1 популяция селекция t ~ nlnn t ~ n t ~ lnn кроссовер t ~ 1 мутация предположительно Целочисленное (бинарное) кодирование *: -арный алфавит *:

14 Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 2006». Обнинск, Заключение Представлен простой способ вычисления времени смешивания для ОК для целочисленного кодирования. Результаты совпадают по порядку с известными результатами и подтверждены экспериментально. На основе анализа результатов сделано предположение, что если ЭА сходится, то время сходимости не превышает порядка (N 4 ) A -арного алфавита, и не больше (N 3 ) для целочисленного (бинарного) кодирования

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