Wednesday, September 16, 2009

Две вычислительные способности простого генетического алгоритма

Продолжая чтение диссертации Бурджорджи [1], следующим пунктом плана идут вычислительные способности (Computational Competencies) ПГА.

Рассматривается задача определения квантитативных локусов в нитях ДНК. Под квантитативными локусами понимаются такие, которые определяют фенотипичексие черты во взаимодествие с другими локусами нити. Черты же, которые соотвествуют этим локусам, то есть изменения в которых определяются группой локусов, называются комплексными. Вообще говоря, одней из наиболее важных задач современной генетики является выявлении групп квантитативных локусов, отвечающих за данную черту. Популярным методом для решения этой задачи является сканирование генома (genome scanning). При данных нескольких последовательностях генотипов и известных значениях рассматриваемой черты, проводится сканироваение геномов, и определяется статистически значимые зависимости. Выделяют главный эффект локуса и эффект взаимодействия с другими локусами. Основное внимание исследователей было сконцентрировано на исследовании первого.

Причиной этого оказалось отсутствие эффективного алгоритма для такой задачи. Очевидно, в исследованиях Кеки таким алгоритмом оказался ПГА.

1. Burjorjee K. Generative Fixation. - Brandeis University, 2009.

Tuesday, September 15, 2009

Гипотеза строительных блоков

В начале приведем некоторые определения. Пусть даны два подмножества Б и В множества А. Для популяции размера Н будем говорить, что выборочный фитнесс (sampling fitness) Б больше выборочного фитнесса (ВБ) В, если средний фитнесс Н выборок мощностью один из Б больше среднего фитнесса Н выборок мощностью один из В.

Пусть дано семейство подмножеств множества А с непустым пересечением. Будем говорить, что пересечение антагонистическое (синергетическое, консонантное), если с высокой вероятностью ВБ пересечения меньше (больше, равно), чем ВБ участвующих в пересечении множеств.

Определим базовый строительный блок как короткую схему, которая с высокой вероятностью имеет больший ВБ, чем ВБ множества А. Синергетическое пересечение семейства малой мощности близко размещенных базовых (н-1-ого уровня) строительных блоков называется строительным блоком второго (н-того) уровня.

Теперь переходим к предположениям в основании гипотезы строительных блоков.
1. Существует большое число базовых строительных блоков.
2. Синергетические пересечения между семействами небольшой мощности близко размещенных строительных блоков одинакового уровня часты.

Кеки Бурджорджи [1] считает, что эти два предположения настолько сильны, что не могут быть приняты без дополнительного подтверждения.

1. Burjorjee K. Generative Fixation. - Brandeis University, 2009.

Monday, September 14, 2009

Pure Crossovers

В работе [1] описываются функции трех основных операторов эволюционного алгоритма: отбора, рекомбинации и мутации. Говорится, что, в чистом виде, каждый из них выполняют уникальную функцию. Отбор отвечает за сходимость популяции, мутация - за расходимость, а кроссовер - за смешивание генетического материала. При этом, только рекомбинация может выполнять также функцию селекции и мутации. Чистыми, при этом, называются кроссоверы, выполняющие только свою функцию. Под чистотой при этом понимается, говоря о примере в пространстве Хэмминга, постояноство в популяции пропорций схем первого порядка. Если говорить с позиции определений, независимых от представления (representation-independent), то чистыми кроссоверами являются:

Класс кроссоверов, сохраняющих отрезки (segment-preserving crossovers), с замещением родителей. При этом кроссоверы являются фиксированными по отношению к соответствующему им множеству полупространств. Это подкласс геометрических кроссоверов.

Практическая значимость таких кроссоверов заключается в том, что в таком случае за сходимость и расходимость отвечают исключительно отбор и мутация, т.е. условия эксперимента становится контролированными.

С точки зрения теории, применение таких кроссоверов дает возможность точнее изучить эффекты всех трех операторов: рекомбинативный, селективный и мутационный.

1. Cervantes, J., Moraglio, A. , "Pure Crossovers: definition, their relation to Geiringer's theorem for finite populations and practical value", Technical Report, Universidad Autónoma Metropolitana, Mexico, 2008

Свежая диссертация

Найдена свежая диссертация. В ней автор заявляет о новой гипотезе, пришедшей на смену гипотезе строительных блоков, "generative fixation hypothesis". Обращает на себя внимание также блог новоиспеченного доктора философии, и сама диссертация в двух вариантах, один из которых весит 120 мегабайт, с анимацией.

P.S. У меня в версии диссертации с анимацией собственно анимация и не работает.

Sunday, September 13, 2009

N-арный геометрический кроссовер

В работе [1] дается определение геометрического кроссовера с N-родителями такое, что потомки содержатся в выпуклой метрической облочке своих родителей для некоторой метрики d. В классе этих кроссоверов выделяется подкласс разложимых рекомбинаций с тремя родителями, т.е. таких, которые могут быть разложены на последовательность бинарных геометрических кроссоверов относительно одной метрики.

Для определения свойств выпуклости используются понятие выпуклой структуры (convex structure, algebraic closure ), оператор создания выпуклой оболочки ВО (convex hull operator). Оператор ВО, примененный к множеству мощностью два называется оператора создания отрезка (segment operator). Также определяется понятие геодезической выпуклости (geodesic convexity).

Определение N-арного кроссовера интересно тем, что дает возможность рассмотреть его как оператор, выводящий или не выводящий за пределы мультимножества с мощностью больше 2.

1. A. Moraglio, C. Di Chio, and R. Poli. Geometric Particle Swarm Optimisation / Proceedings of European Conference on Genetic Programming, 2007.

Saturday, September 12, 2009

Параллели между анализом форм и геометричностью кроссоверов 2

Одной из предпосылок для создания анализа форм была недостаточность существующих методов для изучения неортогональных представлений. Под неортогональным представлением понимается то, что не всякая комбинация форм допустима. Классическим примером такого представления являются перестановки и деревья в генетическом программировании. Примерами ортогональных представлений являются бинарные и вещественнозначные векторы.

Friday, September 11, 2009

Параллели между анализом форм и геометричностью кроссоверов

В 1990 Николасом Рэдклиффом [1] были предложены следующие принципы разработки кроссоверов:
1. Minimal redundancy. Одному фенотипу должно соответствовать как можно меньше генотипов.
2. Correlation within formae. Как можно больше форм, особенно низкой точности, должны содержать коррелированные решения.
3. Closure. Пересечение двух форм само должно быть формой.
4. Respect. Рекомбинация двух примеров любой формы дожна производить пример той же формы.
5. Proper assortment. Для примеров любых двух данных совместимых форм должны существовать такие параметры кроссовера, которые производят пример на пересечении этих форм.
6. Ergodicity. Должна существовать возможность конечным числом применений генетических операторов достигнуть любое решение в пространстве хромосом из произвольной популяции.

Первое свойство напоминает основное свойство геометрического кроссовера, то, что потомок лежит в замкнутом интервале, с концами в виде родителей. Для кроссоверов, передающих относительный порядок, второе свойство вытекает из первого.

В [2] введен седьмой принцип:
7. Strict Transmission. При данном полном ортогональном базисе из множества отношений эквивалентности на пространстве поиска (множестве хромосом), для каждого отношения эквивалентности, каждый потомок, произведенный рекомбинацией, должен быть эквивалентен одному из своих родителей. Другими словами, каждый аллель потомок получает от одного из своих родителей.

Альберто Моральо и Риккардо Поли [3,4] были выведены следующие свойства геометрического кроссовера:
1. Свойство чистоты (Property of Purity). Рекомбинация родителя с самим собой производит этого родителя.
2. Свойство сходимости (Property of Convergence). Рекомбинация одного родителя с его потомком не может произвести другого родителя, если только этот другой родитель не совпадают.
3. Свойство разбиения (Property of Partition). Рекомбинация одного родителя со своим потомком и другого родителя с этим же потомком производит одинакового внука только в том случае, если он является этим потомком.

Свойства, прдложенные Рэдклиффом, являются с его точки зрения желательными для кроссоверов. В тоже время свойства геометрического кроссовера уже есть у него в наличии и логически выведены из его определения.

Обобщением схем для геометрического кроссовера являются метрические выпуклые множества. Потомок на замкнутом интервале между своими родителями принадлежит всем выпуклым множествам, общим для его родителей.

Моральо пишет, что, хотя и классы эквивалентности, и выпуклые множества, покрывают пространство целиком, в отличии от первых выпуклые множества не разбивают пространство поиска, поскольку они пересекаются. Следует заметить, что классы эквивалентности пересекаются, если они индуцированы разными отношениями эквивалентности. Такие классы эквивалентности (формы) Рэдклифф называет совместимыми.

Таким образом, если рассматривать дополнения выпуклых множеств относительно всего пространства поиска и сами соответствующие множества, как классы эквивалентности, индуцированные одним отношением, то мы получим то, что у Рэдклиффа называется отношением эквивалентности точности (precision - число индуцированных классов данным отношением) 2. Это значит, что теория геометрического кроссовера является частным случаем теории форм. Кроме того, не всякое отношение эквивалентности точности 2 может быть представлено как разбиение пространства поиска на выпуклое множество и его дополнение, поскольку последнее является частным случаем отношений такой точности.

1. Radcliffe N. Genetic neural networks on MIMD computers. - University of Edinburgh, 1990.
2. Radcliffe N. Forma analysis and random respectful recombination / Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 31–38, 1991.
3. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.
4. Moraglio A., Poli R. Inbreeding properties of geometric crossover and non-geometric recombinations / Proceedings of the European Conference on Artificial Intelligence - Italian worshop on Evolutionary Computation, 2006.

Thursday, September 10, 2009

Конференция в Кацивели: научные результаты

С 24 по 29 сентября сего года в Кацивели (поселок под Ялтой) состоится международный симпозиум "Питання оптимізації обчислень". Мой руководитель и я получили приглашение. Название наших с ним тезисов "Применение ЭВФ-алгоритмов в задачах теории расписаний". Основным результатом этих тезисов является утверждение об универсальности эволюционно-фрагментарных (ЭВФ) алгоритмов.

Под эволюционно-фрагментарным алгоритмом для некоторой задачи понимается эволюционный алгоритм, в котором процедура вычисления критерия рассматривается как фрагментарный алгоритм, а сама задача обладает фрагментарной структурой.

Фрагментарная структура - это упорядоченная тройка (X,Y,R), где X - множество элементарных фрагментов, Y - семейство допустимых фрагментов, R - правило присоединения элементарных фрагментов и/или допустимых фрагментов.

Например, в задаче Джонсона элементарными фрагментами являются работы, а допустимыми фрагментами любые непустые подмножества множества работ без повторений. То есть, в данном случае, правилом присоединения работ является отсутствие повторений.

Таким образом, чтобы решить задачу на перестановке, необходимо поменять всего лишь фрагменртарный алгоритм, вычисляющий критерий. В этом и заключается универсальность предлагаемого ЭВФ-алгоритма.

Поскольку в области эволюционных вычислений для того, чтобы проверить эффективность алгоритма, применяется в основном тестирование (в концов концов единственный способ узнать об эффективности ЭА на практике - это проверить его на практике), предлагается провести вычислительный эксперимент. Для тестирования берется набор задач из OR-Library и вычисляется среднее отклонение от известного лучшего значения критерия. Кроме того, проводится сравнение со случайным поиском.

Wednesday, September 9, 2009

Анализ кроссоверов на основании форм Рэдклиффа

1. В статье [1] на задаче flow shop с критерием длины расписания проводится исследование того, какая интерпретация перестановки дает результаты лучше. Интересно то, что методика может быть распространена и на другие задачи. Для этого используется такое обощение схем Холланда (Holland's schemata) (другие варианты: шаблоны, шимы) как формы Рэдклиффа (Radcliffe's formae) или предикаты Воуза (Vose's predicates).

Формами называют классы эквивалентности, порожденные некоторым отношением эквивалентности, заданным на, например, множестве допустимых решений задачи Джонсона (flow shop с критерием длины расписания).

Под интерпретацией перестановки понимается то, какое отношение эквивалентности мы хотим, чтобы потомок унаследовал от своих родителей (не обязательно от обоих). А наследовались в данной статье четыре отношения:
- предшествования(Пр);
- порядка(П);
- смежности(С);
- совпадения блоков(Б).
Лучшее же из этих четырех по критерию дисперсии фитнесса внутри формы оказалось Б, затем П, Пр и С. Следует заметить, что этот результат относится к задаче Джонсона.

Для существующих в литературе кроссоверов было описано какие формы они передают от родителей потомкам. Лучшим оказался частично-соотвествующий кроссовер (PMX). Затем были предложены новые кроссоверы, которые оказались не хуже, а некоторых индивидуальных задачах и превзошли его.

Ставится вопрос следующий: каким образом могут быть объединены теория геометрических кроссоверов и анализ кроссоверов на основании форм Рэдклиффа?

1. C. Cotta and J.M. Troya. Genetic forma recombination in permutation flowshop problems. Evolutionary Computation, 6(1):25–44, 1998.

Tuesday, September 8, 2009

Гипотеза гладких ландшафтов

В работе [1] высказана гипотеза, что различные метаэвристики дают наилучшие результаты на гладких ландшафтах фитнесс-функции (fitness landscapes). Признаться, гипотеза не нова, и до него она не раз озвучивалась. Теперь этот автор предлагает, основываясь на теории геометрических кроссоверов, развить теорию гладких ландшафтов, которую он видит как то, что может объединить теорию и практику эволюционных вычислений.

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

В работе [2] предложена модель гладких ландшафтов на основе гауссовых случайных полей, заданных на произвольных метрических пространствах. Гладкость ландшафта в этой модели контролируема, соответственно, для различной гладкости в данной модели может быть проведено тестирование, например эволюционных алгоритмов. Что и было проделано авторами для пространства Хэмминнга и их гипотеза была подтверждена. Опять возникает вопрос, какие результаты даст данная модель для, например, множества перестановок.

1. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.
2. Moraglio A. A gaussian random field model of smooth fitness landscapes / Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, 171-182, 2009.

Monday, September 7, 2009

Два класса кроссоверов: негеометрический лучше

Нашел статью [1], в которой говорится, что негеометрический кроссовер дает результаты лучше, чем такой представитель класса геометрических кроссоверов, как равномерный кроссовер (uniform crossover), причем как для однокритериальной, так и для двухкритериальной постановки. Тестирование проводилось на задаче о рюкзаке с бинарными переменным, т.е. в пространстве Хэмминга. Было бы интересно провести подобные "испытания" и для других пространств генотипов.

1. Ishibuchi H. Effects of the use of non-geometric binary crossover on evolutionary multiobjective optimization / Proceedings of the 9th annual conference on Genetic and evolutionary computation, 829--836, 2007.

Sunday, September 6, 2009

Convex Search

Именно такое название дал A. Moraglio тому свойству эволюционных алгоритмов, что алгоритм "based on geometric crossover leads to a form of search that cannot extend beyond the convex hull of the initial population. Mutation can be used to allow non-
convex search" [1, с. 250]. Таким образом единственный оператор, который позволяет выйти за выпуклую оболочку начальной популяции - мутация. Интересным является то, что понятие схемы, на самом деле, совпадает с понятием выпуклой оболочки для пространства Хэмминга.

1. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.

Saturday, September 5, 2009

Литература по теории сложности: из последнего

Насколько я понимаю, по теории сложности опубликованы в этом и прошлом годах две книги, которые со временем могут стать классикой жанра, если еще не стали, учитывая, что до публикации их издательством (а издательство у них одно), предварительные версии были размещены авторами в свободном доступе. Теперь же в свободном доступе есть опубликованные версии. Это "Computational Complexity: A Conceptual Perspective" (Oded Goldreich) и "Computational Complexity: A Modern Approach" (Sanjeev Arora and Boaz Barak).
Еще одна известная мне книга последних нескольких лет о вычислительной сложности, которая, между прочим, касается эволюционных алгоритмов (глава 9), это монография Инго Вегенера (Ingo Wegener) "Complexity Theory".

Thursday, September 3, 2009

Свежая книжка о метаэвристиках

Только что скачал вот эту книгу. Автор обещает, что она подойдет как учебник для студентов уровня undergraduate.