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

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

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

Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 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):

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

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

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

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

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

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

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

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

Цой Ю.Р. Один способ вычисления времени смешивания для генетических операторов скрещивания. Семинар по эволюционным вычислениям, «КИИ – 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 мутация предположительно Целочисленное (бинарное) кодирование *: -арный алфавит *:

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

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