Friday, December 18, 2009

LaTeX,WordPress и "Theory of Convex Structures"

Установил на этом блоге скрипт, который позволяет писать на LaTeX прямо в тексте поста, что очень облегчает набор формул. Оказалась, что проблема с выравниванием относительно базовой линии не только у меня, но и других пользователей.

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

Исправил с использованием нового скрипта пост с названием "Вероятность выхода за выпуклую оболочку".

Удалось заполучить основной труд современности по аксиоматической выпуклости "Theory of Convex Structures" Марселя Л. Й. ван де Веля (M.L.J. van de Vel).

Thursday, December 10, 2009

Второй раздел диссертации

Вчера мне научный руководитель озвучил задание: начать писать второй раздел диссертации.
Говоря о том, что должно войти в этот раздел, сразу же приходит идея о требованиях ВАК. В соответствующем документе "Основні вимоги до дисертацій та авторефератів дисертацій" в пункте 3.5 требуется следующее:

У  другому  розділі,  як  правило,  обґрунтовують  вибір  напряму  досліджень,  наводять  методи  вирішення задач  і  їх  порівняльні  оцінки,  розробляють  загальну  методику  проведення  дисертаційних  досліджень.  В теоретичних  роботах  розкривають  методи  розрахунків,  гіпотези,  що  розглядають,  в  експериментальних — принципи  дії  і  характеристики  розробленої  апаратури,  оцінки  похибок  вимірювання.
Таким образом, во второй раздел должно войти описание методов, используемых при проведении исследования.
Исходя из вышесказанного, могу набор методов, используемых в своей работе, разделить на две широкие группы:

  1. Теоретические. Здесь исследуется несколько упрощенная модель генетического алгоритма, для которой делаются выводы. Использовались понятия и результаты метрической теории графов, включая понятие выпуклости на графах, а также методы теории вероятностей.
  2. Экспериментальные. Здесь тестируется программная реализация генетического алгоритма, другими словами, реализуется вычислительный эксперимент. Для оценки результатов проводится сравнение со случайным поиском, другими эвристиками и метаэвристиками, а также с уже известными оптимальными решениями. Кроме того, вычислительный эксперимент используется для подтверждения или опровержения теоретических гипотез.
Второй раздел мог бы содержать, по крайней мере, два подраздела, посвященных каждому из вышеуказанных пунктов.
План раздела может быть следующий.
2. Основные теоретические сведения и методы исследования
2.1 Методика разбиения пространства
2.1.1 История
2.1.2 Теория форм и теория геометрического кроссовера
2.2 Методы теоретических исследований
2.2.1 Некоторые понятия из теории метрической выпуклости
2.2.2 Методы теории вероятностей
2.3 Методы экспериментальных исследований
2.3.1 Вычислительный эксперимент
2.3.2 Способы оценки результатов эксперимента
2.3.3 Методы математической статистики
2.4 Выводы ко второму разделу

Friday, November 27, 2009

Полнота генетического поиска

На конференции "Математичне та програмне забезпечення інтелектуальних систем", проходящей в Днепропетровске сделал доклад. Вот ссылка на текст тезисов этого доклада.

Saturday, November 7, 2009

Первая статья опубликована

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

Sunday, November 1, 2009

Wednesday, October 21, 2009

Свойства кроссовера по Рэдклиффу в рамках теории Моральо

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

Первое, что может быть замечено общего в этих двух теориях, так это такое свойство как "respect" в аналилзе форм и "геометричность" в, так скажем, анализе геометричности. Еще в своей диссертации [1] Рэдклифф вводит понятие множества подобия (similarity set) для пары хромосом, которое является ничем иным как выпуклой оболочкой этой пары.

Вообще говоря, в рамках теории Моральо [2] понятие геометричности кроссовера, или respectful кроссовера по Рэдклиффу, является центральным. В тоже время свойство "respect" в теории Рэдклиффа является одним из целого списка свойств [1].

Следующий вопрос: как такие свойства кроссовера как "assortment", "strict transmission" могут быть сформулированы на языке выпуклых оболочек.

1. Radcliffe N. J. Genetic Neural Networks on MIMD Computers. - University of Edinburgh, 1990.
2. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.

Friday, October 2, 2009

Толковая статья о сходимости метаэвристик

Найдена статья по сходимости метаэвристик, достаточно четко расставляющая все точки над i.

W. J. Gutjahr Convergence Analysis of Metaheuristics // Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Springer, 2009. Качать здесь.

Число перестановок порядка n с k инверсиями и вопрос об эффективности мутации

Каким образом может быть оценена эффективность мутации? Мутация является невыпуклым оператором в эволюционном алгоритме [1, с. 322, Theorem 15.4.4.]. При условии, что остальные операторы являются выпуклыми, только оператор мутации может ввести решения за выпуклой оболочкой текущей популяции в следующую популяцию. Тогда возникает вопрос о том, насколько же эффективен в этой своей функции оператор мутации. Если взять пространство генотипов, с введенной на нем метрикой, то вероятность, большую нуля, выхода за пределы выпуклой оболочки текущей популяции имеют только точки на границе выпуклой оболочки. Таким образом, вопрос может быть поставлен следующим образом: какова вероятность того, что как минимум m точек выйдет за границу выпуклой облочки. Следует учесть, что текущая популяция может как содержать, так и не содержать все точки на границе своей выпуклой оболочки.

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

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.

Friday, August 28, 2009

Доказательство существования двух классов кроссоверов

Такое доказательство, как оказалось, было проведено для различных представлений в работе, упоминаемой в предыдущем сообщении. Вот цитата: "... there are two non-empty classes of representation-independent recombination operators: geometric crossovers and non-geometric crossovers. (с. 297 )"
Перед тем как представить определение геометрического кроссовера могут быть введены следующие соглашения:
C - пространство конфигураций(генотипов);
d - метрика, заданная на C;
(C;d) - метрическое пространство, в котором ведется поиск алгоритмом;
Im[...] - множество образа (множество значений отображения);
[...]d - отрезок (закрытый интервал) в метрике d.
Теперь (барабанная дробь) определение геометрического кроссовера (опять цитата):
"Definition 3.3.3. A binary operator CX is a geometric crossover on the search space (C; d) if Im[CX(p1; p2)] &sube [p1; p2]d.
This simply means that in a geometric crossover offspring lay between parents. (с. 36)"
Поскольку, это определение напоминает определение выпуклого множества, я бы назвал этот класс кроссоверов выпуклыми.

Продолжая тему о классах кроссоверов

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

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

Wednesday, August 26, 2009

Критика постановки вопроса о двух классах кроссоверов

Вся полученная в адрес этой постановки критика может быть распределена по таким трем пунктам:
1. Два класса: один выделен при помощи одного конкретного правила, а второй - все остальное. Поддается критике описание второго класса, точнее его отсуствие.
2. Критерий сравнения и способ сравнения. Под способом сравнения понимается сравнение эксперимантально и теоретически. В постановке не указан как способ, так и критерий(-ии) сравнения.
3. Критика постановки в виде сравнения двух классов. При этом предлагается как альтернатива анализ и доказательство свойств четко выделенного класса кроссоверов.

Вопрос о двух классах кроссоверов на перестановках

Могут быть выделены два класса кроссоверов на решениях, представленных перестановками. Первый класс описывается следующим образом. Дано две хромосомы и управляющая бинарная последовательность по длине равная длине хромосомы. Управляющая она в том смысле, что в зависимости от того какой бит занимает рассматриваемую позицию, такой аллель (значение элемента перестановки) переходит в хромосому потомка. При этом, если некоторый аллель переходит к потомку, то он удаляется как у родителя-источника, так и у второго родителя.
Во второй класс кроссоверов на перестановках отнесем все такие, которым вышеуказанное описание не подходит. Эти кроссоверы, вообще говоря, являютя первыми, которые были предложены для работы с перестановками, в т.ч. частично-соответствующий кроссовер (partially-mapped crossover)[1].
Вопрос стоит таким образом: можно ли доказать превосходство одного класса кроссоверов над другим?

1. Goldberg D.E. Alleles, loci, and the traveling salesman problem // D.R. Goldberg, R. Lingle / Proceedings of the of the International Conference on Genetic Algorithms and Their Applications, 1985. - pp.162-164

Saturday, August 15, 2009

Моя переписка с редакцией одного журнала

То, что предлагается вниманию читателя далее, следует читать с конца сообщения, т.к. это копия переписки по email, поэтому последние сообщения идут первыми. Название и реквизиты журнала не указываются, правда, при желании, вводом некоторых фраз из этой переписки в Google вы можете узнать о секретаре редакции какого журнала идет речь.
-------------------------------------------------------------------------------------
Ну, во-первых, здравствуйте!

Что касается требований, то четко написано

Требования к рукописям
...

6. Статья должна быть подготовлена с помощью издательской системы LATEX с использованием стилевого пакета [...].sty (желательно статья должна соответствовать шаблону).

А касательно

5. Рукопись, которая поступила в редакцию с нарушением указанных правил оформления, не регистрируется и не рассматривается, а возвращается автору ( ам) для доработки.

Регистрации и рассмотрения Вашей статьи еще не было, поэтому и не была отправлена Вам обратно. Вместе с этим, если будут еще какие-то замечания, то мы обязательно Вам сообщим!

с уважением
секретарь редакции журнала ...



----- Original Message -----
From: buenasdiaz@gmail.com
To: ...
Sent: Saturday, August 15, 2009 1:24 AM
Subject: Re: Статья от Бондаренко и Козина


Цитирую ваш сайт:
1.Автору(-ам) необходимо предоставлять следующие документы:
...
Файл статьи на дискете 3,5", или CD или присланный по электронной почте на адрес редакции

2.Работа редакции с авторами
...
Рукопись, которая поступила в редакцию с нарушением указанных правил оформления, не регистрируется и не рассматривается, а возвращается автору ( ам) для доработки.

По первому пункту: из ваших слов и написанного на сайте я делаю вывод, что фраза "Файл статьи" означает файл статьи и tex файл статьи. В любом случае, вы требуете выслать два файла.
Вопрос: чья здесь ошибка?

По второму пункту: из ваших слов и написанного на сайте я делаю вывод, что "Рукопись ... поступила в редакцию с нарушением указанных правил оформления". Из чего следует - "Рукопись ... не рассматривается, а возвращается автору ( ам) для доработки". Первая часть выполнена, а вторая нет.
Вопрос: правильно ли я понимаю ситуацию?

Жду скорейшего ответа

2009/8/15
Tex файл статьи находится в прикрепленном файле.
Кроме tex файла статьи, есть ли еще требования, без выполнения которых эта статья не будет рассматриваться?


2009/8/14 ...

Здравствуйте, уважаемые коллеги!

Статья не рассматривается, так как она не удовлетворяет (нет, например, tex файла статьи) требования журнала ...(Название журнала) См. [Адрес сайта журнала]!

с уважением
секретарь редакции журнала ...

----- Original Message -----
From: buenasdiaz@gmail.com
To: ...
Sent: Thursday, July 30, 2009 11:35 AM
Subject: Статья от Бондаренко и Козина


Здраствуйте коллеги,

хотелось бы узнать на каком этапе рассмотрения находится статья Бондаренко и Козина "EVOLUTIONARY FRAGMENTARY ALGORITHM FOR
PERMUTATION FLOW SHOP PROBLEM".

С уважением,

Бондаренко Александр

Monday, July 27, 2009

Завершена еще одна статья

Статья на тему отыскания множеств альтернатив для двухкритериальной задачи теории расписаний завершена. Теперь дело за руководителем, от которого я в данный момент ожидаю комментариев. Это моя самая объемная статья - 21 с половиной тысяча символов вместе с пробелами (по данным Word 2003). Таким образом, верхняя грань на объем статьи слегка превышена: требование - 0,5*1 авторский лист - 0,5*40 тысяч печатных символов. Предполагается, что статья пойдет в "Радиоэлектроника. Информатика. Управление". Теперь я могу (да просто обязан) вернуться к диссертации.

Thursday, July 16, 2009

(Собственно) Начало диссертации

Начал писать текст первой главы диссертации. Набираю сразу в TeX.

Sunday, July 5, 2009

Двухкритериальная задача о выполнении работ на параллельных машинах 3

Реализовал эволюционный алгоритм с переменным размером популяции. Он начинает свою работу с 1 решения и в конце концов может выдать множество из 47 решений. Впрочем это всё равно недостаточное разнообразие в популяции, не содержатся целые области решений.
Самые простые два механизма поддержки разнообразия - это один механизм, который не допускает повторения решений, другой - повторения целевых значений.

Friday, July 3, 2009

Двухкритериальная задача о выполнении работ на параллельных машинах 2

Удалось реализовать два различных эволюционных алгоритма (ЭА). Один из - это классический однокритериальный ЭА, помещённый в цикл с числом итераций, равным числу машин и одновременно числу работ.
Другой - это классический многокритериальный ЭА, который от однокритериального отличается по крайней мере алгоритмом удаления (схема отбора выживших или в терминологии де Джонга survival selection) и расчётом многих критериев (в моём случае двух).
Первый достаточно сильно доминирует случайный поиск, а вот второй имеет один существенный недостаток - популяция содержит решение из одного ограниченного региона с большим числом одинаковых значений целевого вектора.
Знаю, что есть некоторые механизмы поддержки разнообразия (diversity mechanisms). Над их реализацией сейчас начну работу.

Thursday, July 2, 2009

Профиль

Расширил свой профиль

Критерии для сравнения решений многокритериальных задач

Если многокритериальная задача (МКЗ) решается эволюционным алгоритмом, то нет никаких гарантий, что найденное множество недоминируемых решений (МНР) является глобальным оптимумом. Это будет всего лишь приближенное решение.
Если сравнивать два приближенных решения, то первое, что приходит в голову, это объединить два или более множеств решений, отсеять доминируемые, и посчитать число недоминируемых для различных решений. В котором больше последних, то и является лучшим.
Но есть ещё один критерий, которому желательно соответствие полученных решений. Это критерий равномерности распределения МНР на множестве допустимых решений (МДР) данной задачи.

Wednesday, July 1, 2009

Новости

1. Отправил статью в "Исскуственный интеллект".
2. Работаю над следующей статьёй. Она будут посвящена многокритериальной задаче теории расписаний (см. предыдущее сообщение) и эволюционным алгоритмам для её решения.
3. Прочитал 6-ую и некоторые другие главы книги Кеннета де Джонга "Evolutionary Computation: A Unified Approach". Произвела на меня достаточно сильное впечатление чёткостью изложения.

Thursday, June 18, 2009

Двухкритериальная задача о выполнении работ на параллельных машинах

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

Monday, June 1, 2009

Vector Packing Problem

Задача о минимуме максимальной загрузки может быть сформулирована как задача упаковки векторов (vector packing problem). В задаче упаковки векторов имеется n m-координатных векторов. Требуется упаковать эти векторы в контейнеры с m ограничениями для каждой координаты вектора, соответственно, при этом использовав минимальное количество контейнеров. Задача упаковки векторов является обобщением задачи упаковки контейнеров (bin packing problem).
Задача о минимуме максимальной загрузки может быть описана как обобщение задачи упаковки в полосу (strip packing problem) до задачи упаковки векторов в полосу (strip vector packing problem).
Таким образом, название задачи упаковки векторов может быть уточнено до задачи упаковки векторов в контейнеры (bin vector packing problem).

Sunday, May 31, 2009

Задача о минимуме максимальной загрузки

Задача о минимуме максимальной загрузки (ЗММЗ) содержит семейство векторов, которые требуется разместить таким образом на ограниченной с трех сторон плоскости, чтобы максимум суммы по всем координатам x был минимален. Без потери общности предположим, что каждый вектор может занимать некоторую одну координатуу y. Эти векторы мы можем двигать вправо и влево по занимаемой ими координате. Эта задача напоминает мне полиомино (одним из видов которого является тетрис) и различные задачи упаковки. При этом ЗММЗ несколько от них отличается.

Saturday, May 30, 2009

Нас пригласили в Омск

Я получил email с приглашением нас с моим научным руководителем в Омск на конференцию "Проблемы оптимизации и экономические приложения". Теперь можно начинать готовиться, складывать чемоданы (шутка, что касается чемоданов).

Процесс работы над статьёй

Процесс работы над статьёй подходит к завершению. На вторник заплонировано утверждение статьи на заседании кафедры. В понедельник необходимо подписать рецензию. Статья получилась на 9 страниц. Причём она сейчас ещё не завершена.

N.B. Желательно все прогоны алгоритмов делать заранее.

Thursday, May 28, 2009

Задача о расписании с критерием равномерной нагрузки

Занялся написанием статьи. Рассматриваю в статье задачу равномерного распределения учебной нагрузки для студента. Критерий $\min\max$, т.е. требуется минимизировать максимальную нагрузку за неделю. Представление для хромосом этой задачи. Декартово произведение $n$ множеств $X_i$, где элементом каждого множества является номер позиции в расписании, которую может занять первое занятие данного учебного предмета с номером $i$.

Friday, May 22, 2009

Два экзамена сданы

Английский и философия сданы (оба на пять).

Tuesday, May 19, 2009

Задача составления расписания для ВУЗа как задача теории расписаний

Аудиторное время:одновременно не более &xi студентов
Преподавательское время:одновременно не более одной аудитории
Студенческое время:одновременно не более одной аудитории
Дано множества аудиторий, студентов и преподавателей. Пускай аудитории и преподаватели будут машинами, а студенты работами.
Для выполнения любой работы требуется два ресурса: преподаватель и аудитория.
Кроме того, мы можем рассмотреть студентов также в качестве машин, поскольку одним из ограничений является равномерная загрузка студентов дисциплинами (предметами). Тогда предметы будут рассматриваться как работы, т.е. дополнительно определяется множество дисциплин (предметов), а занятия по данному предмету будут операциями данной работы.
Исходя из этого каждой операции данной работы ставится в соответствие множество подмножеств множества машин, на которых допустимо выполнение этой операции.
Таким образом задача составления расписания для ВУЗа представлена как задача теории расписаний.
Особенностями данной задачи являетя то, что все операции длятся одинаковое время и имеют заранее известное множество возможных времён их начала; одно множество машин может одновременно выполнять одну операцию; поскольку длина расписания задана условием, то критерием может быть распределение операций в расписании, отвечающее определённым требованиям, например равномерная загрузка машин работами; традиционно операции в таком расписании повторяются с заранее заданной периодичностью, например одно занятие в две недели.

Monday, May 18, 2009

Алгоритм Сторера, Ву, Ваккари

Работаю над реализацией названного в заголовке алгоритма. Он является обобщением алгоритмов Гиффлера-Томпсона, которые используются для генерации активных(active) и плотных(non-delay) расписаний для задачи Job Shop.

Wednesday, May 6, 2009

Публикации Александра Бондаренко




Материалы конференций



Статьи в журналах и сборниках


  • Козин И.В., Бондаренко А.С., Полюга С.И.
    Об оценке шарового покрытия пространства перестановок
    // Вісник Запорізького національного університету: Збірник наукових статей. Фізико-математичні науки. - 2009. - № 1. - С. 134-138.
  • Bondarenko O.S., Kozin I.V.
    Evolutionary fragmentary algorithm for permutation flow shop problem
    // Таврический вестник информатики и математики. - 2009. - №2. - С. 47-51.
  • Бондаренко А.С., Козин И.В.
    Эволюционный и фрагментарный подходы к задаче о равномерной нагрузке
    // Искусственный интеллект. - 2009. - № 4. - С. 248-253.

Monday, May 4, 2009

Репродуктивный план Де Джонга R1

Во второй и третьей главах рассматрвается упомянутый в заголовке план R1 (так в те времена называли генетические алгоритмы). В начале четвёртой главы на стр.96 говорится, что для выбора плана из класса планов R1, требуется указать следующие четыре параметра: размер популяции, уровень мутации, уровень кроссовера и разрыв между поколениями (generation gap). Под разрывом между поколениями понимается доля следующего поколения, порождаемая генетическими операторами (стр. 78).

PhD Thesis Де Джонга

Хочу разобраться каким является стандартный набор параметров для генетического алгоритма в PhD Thesis Де Джонга, как выразились Деб и Голдберг в своей статье об обманчивых бинарных функциях.

Задача Job Shop

Занялся написанием кода для данной данной задачи. Выбрал кодировку для своего эволюционного алгоритма, в аглоязычной литературе она называется "operation-based". Автор на которого обычно ссылаются при её использовании Christian Bierwirth (вторая статья в списке). Выражается кодировка в том, что каждый ген представлен номером работы, который повторяется столько раз, сколько данная данная работа имеет операций в задаче, обычно число операций равняется числу машин. Хромосома в результате имеет длину n× m, где n-число работ в задаче, и m-число машин.
Есть ещё такой алгоритм Гиффлера-Томпсона (первая статья), который считается наиболее эффективным для генерации активных расписаний для данной задачи.