PhD Project blog

Papers accepted to SODA 2012

2011-09-18T08:37:00.002+03:00

Recently the list of papers accepted to SODA 2012 has appeared. In it there is a paper on progress in TSP "A Proof of the Boyd-Carr Conjecture". According to its abstract, "Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9."

Making further Progress in Approximating graphic TSP

2011-08-06T09:43:00.002+03:00

Another work concerning approximation of graphic TSP appeared recently. It improves analysis of Moemke and Svensson from $1.461$ to $1.458$ and makes it cleaner.

NP-complete problem which is neither NP-complete in the strong sense nor solvable by pseudopolynomial algorithms?

2011-07-17T10:38:00.004+03:00

Recently I've posted on cstheory a question that is described in the title of this post. Since then I've received only one comment and one answer. I think the possible answer to it can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.

Another approximation for Graphic TSP below 3/2

2011-04-17T14:51:00.003+03:00

Today I've found out that T. Moemke and O. Svensson have made available on the net preprint "Approximating Graphic TSP by Matchings" with new approximation for Graphic TSP below 3/2. It should be mentioned that nearly 5 months ago there have appeared similar result: "A Randomized Rounding Approach to the Traveling Salesman Problem".

Multiobjective Optimization Complexity

2011-04-12T19:55:00.008+03:00

Yesterday, there was uploaded an interesting paper on Multiobjective Optimization Complexity, called "The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions". Authors of the paper describe results concerning complexity of different notions of "what it means to 'solve the problem'". For all this notions they define corresponding complexity classes and prove results on (non)equivalence of some of these new classes to such classes as $\mathbb{NP}$ or $\mathbb{NPMV}_g$, where $\mathbb{NPMV}_g$ is the complexity "class of multivalued functions whose graph is in $\mathbb{P}$".

People sometimes say “X is true.” A rule to discover if this statement makes any sense is ...

2011-02-26T21:43:00.003+02:00

Though Richard Lipton wanted to tell eventually about that it's unknown whether Euclidean TSP is NP-complete/belongs to NP I liked the rule of his advisor:

People sometimes say “X is true.” A rule to discover if this statement makes any sense is to think about the statement: “X is false.” If the later is silly or obvious, then the original statement made no sense.

[1102.3766] Derandomizing HSSW Algorithm for 3-SAT

2011-02-21T13:42:00.001+02:00

In their paper the authors write: "we obtain an $O(1.3303^n)$-time deterministic algorithm for 3-SAT, which is currently fastest."

Timeline of computer science

2011-02-11T19:41:00.004+02:00

In the above-named post by Scott Aaronson I've found some (many?) new things for myself, especially I liked the mention of the first paper on nondeterminism.

NEXP does not have non-uniform quasi-polynomial-size ACC circuits of $o(\log\log n)$ depth

2011-02-09T13:32:00.006+02:00

The author, Fengming Wang, a third year Ph.D. student at Rutgers, states his result as:

In this paper, we show that Williams’ lower bound result can be extended to
a broader class of ACC circuits with non-constant depth. A function $f$ is a quasipolynomial if $f = n^{\log^{O(1)}n}$.

How do you get a “Physical Intuition” for results in TCS?

2011-02-09T03:53:00.002+02:00

Nice answers for a nice question. I especially liked the ones by Ryan Williams, Hsien-Chih Chang 張顯之 and Jukka Suomela.

A CS Professor's blog: Some old advice from Andy Yao

2011-01-31T19:12:00.003+02:00

A very helpful advice from Andrew Yao.

Dominance rules and combinatorial optimization

2011-01-29T22:34:00.005+02:00

Today I've found a very interesting review by Antoine Jouglet and Jacque Carlier about dominance rules. The paper gives definition and a thorough classification of dominance rules. Essentialy, a dominance rule can be viewed as any rule which allows cut off some part of solution space guaranteeing that at least one optimum is left. Dominant subset is a subset obtained by applying some dominance rule. Widely-known dominant subsets of schedules in schedulig theory are semiactive, active and nondelay schedules. One example of nondelay schedules is the schedules generated by well-known list scheduling algorithm for $P|prec|C_{max}$.

New lower bounds for one dimensional bin packing

2011-01-28T21:44:00.013+02:00

Today the paper on lower bounds for bin packing from the last WAOA has been published. The authors of the paper improve on the old (good?) lower bound of van Vliet $1.54014\dots$ to $\frac{248}{161}=1.54037\dots$. They also give a combinatorial proof of van Vliet's bound. Other case they consider is improved lower bounds for decreasing list online bin packing. The technique used in proofs is packing pattern technique from [1], additionally, new series of instances is introduced instead of Sylvester sequence.

Galambos, G.: A 1.6 Lower Bound for the Two-dimensional On-line Rectangle Bin Packing. Acta Cybernetica 10, 21–24 (1991).

Fixed Job Sequence problems

2011-01-22T02:47:00.006+02:00

I've found a very interesting paper "Coupled-Task Scheduling on a Single Machine Subject
to a Fixed Job Sequence". The essence of their study is about how hard is it to find an optimum if on the jobs of the instance the linear order is fixed. Interestingly, the authors propose only algorithms but no proofs of NP-hardness. In the paper precedence relation is defined as follows:

"given a fixed job sequence, if job $J_i$ precedes job $J_j$ in the specified sequence, then it is required to schedule the tasks such that $a_i$ precedes $a_j$, and $b_i$ precedes $b_j$."

Speed-Price Equilibrium « Algorithmic Game-Theory/Economics

2011-01-20T16:16:00.001+02:00

I think that's a good idea to tell students about such applications of economics and algorithmic game theory, in particular.

The Geomblog: The 5+5 Commandments of a Ph.D.

2011-01-12T17:44:00.002+02:00

Some advice on pusuing Ph.D.

[1011.1157] Sorting by Transpositions is Difficult

2011-01-05T03:20:00.002+02:00

Sorting by Transpositions is Hard.

11011110: Top ten algorithms preprints of 2010

2010-12-31T23:08:00.002+02:00

Top ten algorithms preprints of 2010 from the point of view of David Eppstein.

Hitler and P = NP

2010-12-29T16:37:00.001+02:00

Computational Complexity: Complexity Year in Review 2010

2010-12-29T16:25:00.002+02:00

Major happenings in Complexity Theory this (2010) year.

The paper on "Improved Algorithm for Metric TSP" is available now!

2010-12-25T17:53:00.003+02:00

Here.

Computational Complexity: BREAKTHROUGH in algorithms: Improved algorithm for Metric TSP!!!!!!!!

2010-12-20T19:46:00.004+02:00

I'm looking forward to see this in arxiv asap.

The short description of the result by one of the authors can be found here.

[1012.3319] A note about a partial no-go theorem for quantum PCP

2010-12-16T04:53:00.002+02:00

Interesting paper on the possibility of quantum PCP.

The Recognition of Triangle Graphs

2010-12-16T03:02:00.003+02:00

Interesting to note is that: "since triangle and simple-triangle graphs lie naturally between permutation and trapezoid graphs, and since they share a very similar structure with them, it was expected that the recognition of triangle and simple-triangle graphs is polynomial, as it is also the case for permutation and trapezoid graphs. In this article we surprisingly prove that the recognition of triangle graphs is NP-hard, even in the case where the input graph is known to be a trapezoid graph."

Dr. Wortman’s top resources for trends in Computer Science — The Pollak Library Blog

2010-12-09T03:56:00.003+02:00

Basic information resources for CS scientist.

Theory Group @ University of Toronto : Postdoc Opportunities

2010-12-07T02:14:00.002+02:00

I like this opportunity.

Do Uniform Lower Bounds Matter?

2010-12-06T23:26:00.003+02:00

The question about the citation from Ryan Williams paper have interested me as well.

Quite interesting paper

2010-11-12T01:10:00.003+02:00

By quite interesting I mean the paper that came up yesterday and is titled "Reductions Between Expansion Problems". Why is it so interesting? It proposes "the Small-Set Expansion Hypothesis" which "is in fact equivalent to a variant of the Unique Games Conjecture".
In turn, the Unique Games Conjecture is very famous one for if being true then some well-known problems obtain almost tight hardness of approximation results. In turn, assuming truth of the first hypothesis authors of the paper prove the results which weren't known "assuming the Unique Games Conjecture."

Reading "Non-Uniform ACC Circuit Lower Bounds"

2010-11-08T21:16:00.004+02:00

Today Ryan Williams have published on his web page a paper titled "Non-Uniform ACC Circuit Lower Bounds" which Scott Aaronson called "a breakthrough in circuit lower bounds".

On the usefulness of news feeds, changedetection, google scholar et al.

2010-11-05T20:02:00.006+02:00

Yesterday Ola Svensson published on his web page a new paper "Santa Claus Schedules Jobs on Unrelated Machines". I know that because of changedetection.com, a service, sending me a message everytime the site I subscribed on has changed.

Also yesterday, I got feeds from Terence Tao's blog on "self-defeating object" argument.

Now when I know the title of the new paper by Ola, I can subscribe on it in Google Scholar, and get messages on new papers anytime Scholar has indexed them.

Thus, net provides plenty of possibilities to anyone ready to embark on studying more deeply such subject as mathematics.

What I especially appreciate in studying is that you never know everything in your area (if you do then this area is unnaturaly restricted). Now when I started my third PhD year, it seems to me I started to see what will be in my thesis.

Recently I opened interesting for me relation between graph coloring problems and packing problems. First of all, it concerns the relation between coloring of interval graphs and bin packing.

At last! The opportunity to read the thesis by David Stifler Johnson

2010-10-29T21:27:00.005+03:00

This link has made possible for everyone to read very important PhD thesis in combinatorial optimization and worst-case analysis. Namely, the thesis by David Stifler Johnson named "Near-optimal bin packing algorithms". I hope in the near future we'll be able to take a look at such important papers in bin packing theory as:

The performance of a memory allocation algorithm by Jeffrey David Ullman
A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms by Donna J Brown

Not on bin packing, however, important and not available on the net paper is

The Intrinsic Computational Difficulty of Functions by Alan Cobham.

Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума 2

2010-07-24T02:02:00.007+03:00

Пока искал информацию о свойстве реставрации упаковки, нашел следующую очень интересную работу:

(1) Залюбовский В.В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Труды XIII Байкальской школы-семинара. Иркутск. Том 1. 2005. С. 461-468.

В этой работе на странице 462 ставится вопрос, вынесенный в заголовок этого поста:

"4. Наилучший элемент в пространстве решений соответствует оптимальному решению

исходной задачи."

и на него дается ответ на стр. 463 в духе [1]:

"Лемма 2. Для любой допустимой упаковки $\mathcal{P}$ множества предметов $L$ существует $NF$-активная упаковка $\mathcal{P}'$ такая что

\[|\mathcal{P}'|\leq |\mathcal{P}|."\]

Приведем основные понятия в порядке их упоминания в работе (1) с авторскими комментариями.

Понятие NF-активной упаковки. Собственно говоря, именно для алгоритма Next Fit и доказывается о принадлежности оптимума множеству кодов.
Понятие регулярной перестановки и упаковки. Для регулярной упаковки доказывается лемма, аналогичная Лемме 2.
Понятие максимальной упаковки. Для этой упаковки лемма, аналогична Лемме 2 не приводится, хотя из Теоремы 3 можно сделать вывод, что ее доказательство неявно предполагается.

Библиография

Giffler J., Thompson G.L., “Algorithms for solving production scheduling problems,” Operations Research, Vol. 8, 1960, pp. 487–503.

Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума

2010-07-22T23:31:00.003+03:00

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

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

Если говорить об одномерной упаковке, то для задачи одномерной упаковки и для алгоритмов Any Fit классики такими вопросами не задавались. Объясняется это тем, что легко доказать, что для Any Fit алгоритмов всегда существует такой порядок.

В то же время в первой работе об алгоритмах с оценками в худшем случае для упаковки в полосу этот вопрос рассматривался для алгоритма "bottom-up left-justified" (BL) [1], эта же работа и вводит в оборот этот алгоритм. Там было доказано, что существуют примеры, где BL не дает оптимального решения.

BS Baker, EG Coffman and RL Rivest, Orthogonal packings in two dimensions. SIAM Journal on Computing 9/4 (1980), pp. 846–855.

DOOR-2010

2010-07-07T20:20:00.000+03:00

Сегодня утром мы с моим научным руководителем приехали из России, где были на конференции "Дискретная оптимизация и исследование операций". Было достаточно интересно. Появились новые знакомства.

Идея

2010-06-19T02:41:00.004+03:00

Как я раньше к этому не пришел не понимаю. Идея заключается в том, чтобы Google Scholar (далее - GS) проиндексировал мой список публикаций. Чтобы GS это сделал необходимо выполнить условия со страницы "Inclusion Guidelines for Webmasters". В данный момент из вышеупомянутого списка публикаций GS находит все-лишь одну статью.

Web Based LaTeX Editors

2010-06-18T13:01:00.009+03:00

Чтобы не случилось с исходными текстами на LaTeX (далее тех-файлы) твоих статей в оффлайне, или с твоим техом, при использовании онлайн редакторов и хранении исходников где-нибудь онлайн, ты застрахован от таких неприятностей. Хранить онлайн можно было что-угодно и раньше, только вот не было возможности компилировать онлайн тех-файлы. Теперь же этa возможность имеется и даже как минимум в четырех следующих вариантах:

http://docs.latexlab.org/ (скомпилировать удалось, но не поддерживается кириллица, пока все бесплатно, )
http://www.scribtex.com/ (здесь кириллица поддерживается, бесплатно 3 проекта, 1 сотрудник, 50 Мб места, скомпилировать удалось)

http://www.verbosus.com/ (интерфейс неприятный, есть ограничения на бесплатное пользование сервисом, хотя скомпилировать удалось)
http://monkeytex.bradcater.webfactional.com/ (скомпилировать у меня здесь не вышло, каких-либо ограничений я не нашел)

Первая защита

2010-05-30T13:45:00.003+03:00

В пятницу, 28 мая, наблюдал за первой защитой. Защита состоялась в том же совете, в котором предстоит защищаться и мне. Примечательна она была тем, что диссертант был расхвален со всех сторон, включая оппонентов. Кроме того, один из авторитетных членов совета призвал голосовать всех остальных "за", никто, впрочем, и не возражал. Презентации не было. Были плакаты, прикрепленные к деревянным стендам. Буквы на которых не были видны уже с первого ряда. Можно сказать, что все прошло гладко. Единственное место, где будущий кандидат застопорился, это вопрос о сути предлагаемого комплексного метода. Я сразу смоделировал эту ситуация на себя, и получился вопрос о сути эволюционно-фрагментарного метода. Кроме того, был вопрос о правильности работы программы и как она проверялась. Мой руководитель в таком случае посоветовал не выносить на защиту программы. Можно сказать, что это был образец хорошей защиты.

Любопытная статья

2010-05-19T16:38:00.001+03:00

Нашел сейчас статью под названием "On The Number of Condoms at a Cheap Safe-Sex Orgy". Начал читать, и первый абзац оправдал ожидания:
"Let M and F be finite sets. A straight orgy is a series of interactions between each pair in $M\times F$ ... We give an exact formula for the minimal number of condoms required to realize such an orgy, up to an additive factor of 1."

Ранг частично упорядоченного множества

2010-05-14T21:34:00.002+03:00

Понятие ранга у-множества было введено в [1] и развито в [2]. Оно определяется аналогично размерности Душника-Миллера [3], только вместо мощности наименьшого минимального реализатора нас интересует мощность наибольшего минимального реализатора (= множество линейных расширений у-множества, пересечение которых совпадает с самим у-множеством).

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

Maurer S. Large Minimal Realizers of a Partial Order / Stephen B. Maurer, I. Rabinovitch // Proceedings of the American Mathematical Society, Vol. 66, No. 2 (Oct., 1977), pp. 211-216.
Maurer S. Large Minimal Realizers of a Partial Order II / Stephen B. Maurer, I. Rabinovitch, William T. Trotter // Discrete Mathematics. - Vol. 31. - 1980. - P. 297-313.
Dushnik B. Partially Ordered Sets / Ben Dushnik and E. W. Miller // American Journal of Mathematics, Vol. 63, No. 3 (Jul., 1941), pp. 600-610.

Что может быть включено в диссертацию

2010-05-11T22:34:00.004+03:00

Группа результатов по графам линейных расширений
Группа результатов по задаче с периодическим работами

Что может быть доработано и включено в диссертацию:

Разбиение пермутоэдров графами линейных расширений
Вероятность генерации максимальной популяци
Результаты о сжатии-расширении популяции (псевдовыпуклый поиск по Моральо)

Как издаются диссертации нашими швейцарскими коллегами

2010-03-13T23:22:00.001+02:00

Йоханнес Бадер защитился и издал свою диссертацию. Ничего особенного... Если не учитывать, что издана его диссертация издательством с названием "Йоханнес Бадер". Это значит, Йоханнес воспользовался услугами самиздата, в его случае подразделения Амазон - CreateSpace. Тем, кто интересуется генетическим программированием известно, что "A Field Guide to Genetic Programming" была издана самиздатовской компанией Lulu.com.

Как проводится защита диссертации в Португалии

2010-03-04T01:14:00.001+02:00

Вот такие вот фотографии с защиты Сары Силва. Был поражен обстановкой. Я так понимаю, что это университетское, с позволения, помещение, хотя больше напоминает культовое сооружение в мавританском стиле. Насколько я понял по фотографиям, кандидат провела презентацию стоя, а отвечала на вопросы членов жюри сидя за столиком. Также привлекает внимание костюм. Интересно положение, занимаемое научным руководителем Сары, причем как физически, так и в жюри (он его председатель).

Математическии студии

2010-02-11T22:53:00.002+02:00

Во Львове издается журнал "Математичні студії". Мне он интересен тем, что

входит в список ваковских изданий по физ.-мат. наукам
рецензируемый
издается 6 раз в год
рукописи статей принимаются только в TeX.

Сегодня отослал свою статью "Regular subgraphs of linear extension graphs" в редакцию. Статья является переработанной версией препринта, который предполагалось отослать в Вестник Киевского университета. Поскольку для того, чтобы получить рецензию в Вестник, необходимо быть знакомым с членом редколлегии, было решено выбрать другой журнал.

Дополнительные экзамены по специальности

2010-02-06T11:33:00.004+02:00

Вчера побывал на заседании совета, в котором предполагается моя защита. Узнал, что дополнительные экзамены по специальности (специальность полученная мной до аспирантуры не математическая, кроме того, специальности "математическое мод-ние и выч. методы" на уровнях до аспирантуры нет, поэтому, наверное и моим коллегам математикам придется сдавать дополнительные экзамены) могут быть назначены только после того, как будет подана диссертация в совет.

3-хслойные посеты

2010-01-28T19:37:00.008+02:00

3-хслойные посеты (авторский перевод термина "3-layer posets") это тот класс частично упорядоченных множеств, которому принадлежат почти все из них [1]. Из чего следует, если вы докажите некоторое свойство об этом классе, значит докажите о почти всех.

"Графы линейных расширений (ГЛР) инвариантны относительно операции последовательной альтерации на порождающем его посете". Так звучит следствие теоремы, доказанной в [2]. В связи с этим результатом возникает следующие вопросы:

Относительно какой (-их) операции (-ий) остается неизменным данное свойство некоторого класса ГЛР.
Какое (-ие) свойство (-ва) некоторого класса ГЛР инвариантно (-ы) относительно данного набора операций.

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

D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a ﬁnite set, Trans. Amer. Math. Soc., 205 (1975), pp. 205–220. (114)
Massow M. Linear Extension Graphs and Linear Extension Diameter. PhD Dissertation, Technischen Universität Berlin. - Berlin: 2009.

Две статьи и диссертация

2010-01-27T19:06:00.017+02:00

Где-то в начале этого января удалось узнать о двух статьях, в которых были рассмотрены вопросы, над которыми я тогда работал. Сегодня, благодаря профессору Стефану Фельснеру, удалось получить доступ к их электронным версиям. Дело в том, что это препринты, которые нигде не публиковались. Стефан отсканировал эти препринты и теперь они доступны в сети:

Reuter K. The Comparability Graph and the Graph of Linear Extensions of a Poset. Hamburger Beiträge zur Mathematik, Heft 57 (1996).
Reuter K. Linear Extensions of a Poset as Abstract Convex Sets. Hamburger Beiträge zur Mathematik, Heft 56 (1996).

Кроме того, стала доступна электронная версия диссертации, которая явлется последним, если так можно выразиться, словом в исследованиях графов линейных расширений:

Massow M. Linear Extension Graphs and Linear Extension Diameter. PhD Dissertation, Technischen Universität Berlin. - Berlin: 2009.

В данный момент читаю диссертацию, а препринты Ройтера оставил на десерт.

Наибольший интерес вызвали результаты об операциях на частично упорядоченных множествах (посетах) относительно которых графы линейных расширений (ГЛР) инвариантны. Также интересно было увидеть контрпример гипотезе о том, что ГЛР зависят только от графа сравнимости.

Интересно заметить, что диссертация защищена 11 декабря прошлого (2009) года, а опубликована при этом на текущую дату одна статья и еще одна статья подана на рассмотрение. Больше статей у автора по теме диссертации нет.

Перелік наукових фахових видань з фізико-математичних наук

2010-01-26T19:32:00.001+02:00

В Википедии соорудил список ваковских изданий по физ.-мат. наукам.

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

Со временем, думаю, стоит добавить комментарии и какую-то статистику к этому списку.

Список является копией оригинала с сайта ВАК Украины, включая все ошибки, которые там содержатся, например: дублирование изданий, неправильные названия.

Вторая статья

2010-01-26T17:37:00.001+02:00

В номере 2 за 2009 год журнала "Таврический вестник информатики и математики" напечатана статья моего руководителя и вашего покорного слуги. Эта статья была отослана в редакцию год назад.

Bondarenko O.S., Kozin I.V. Evolutionary fragmentary algorithm for permutation flow shop problem // Таврический вестник информатики и математики. - 2009. - №2. - С. 47-51.

Препринт

2010-01-22T18:55:00.005+02:00

В некоторых университетах принято результаты научной работы распространять в виде препринтов. Чтобы это было характерно для украинских ВУЗов, утверждать не готов.

Удивила одна диссертация 2008 года, написанная в математическом институте им. Стеклова, а именно: список из трех статей, опубликованных по теме диссертации. Две из которых депонированы в ВИНИТИ. Вероятно, результаты работы этого молодого человека достаточно серьёзны, что и с одной публикацией он смог защититься.

Так вот о препринтах. Что-то похожее на препринт собирается разместить здесь и ваш покорный слуга. При этом не ожидая, что ему хватит для защиты одной опубликованной статьи и списка препринтов, депонированных куда-либо.

Как это следует из оформления статьи, ее планируется отправить в Вестник Киевского университета.

Бондаренко О.С. Розбиття пермутоедра.

Теория частичных порядков 2

2010-01-06T11:22:00.008+02:00

В статье [1] упоминается о том, что граф линейных расширений $G(P)$ не является инвариантом сравнимости, при этом дается ссылка на [2].

Удалось найти работу [3], в которой отыскивается число линейных расширений с минимильным числом скачков.

В работе [1] приводится интересная теорема о том, что диаметр $G(P)$ равен числу несравнимых пар в минимальном двухмерном расширении $P$.

Felsner S. The Linear-Extension-Diameter of a Poset / S. Felsner, K. Reuter // SIAM Journal on Discrete Mathematics, 1999.
K. Reuter Linear Extensions of a Poset as Abstract Convex Sets, Preprint, Universitaet Hamburg, 1996.
H.C. Jung Counting jump optimal linear extensions of some posets // Recent progress in algebra, AMS, 1999.

Теория частичных порядков

2010-01-04T22:26:00.006+02:00

Изучаю последние несколько дней теорию частичных порядков [1] с ударением на следующие вопросы:

Линейные расширения частичных порядков и их число для различных классов порядков.
Инварианты графов сравнимости для соответствующих порядков.

Число линейных расширений данного линейного порядка является инвариантом графа сравнимости, также как и размерность Душника-Миллера.
Искал, но пока не нашел какие-либо описания такого параметра множества линейных расширений, как число линейных расширений с числом скачков (jump (setup) number) [2] или числом cтупенек (bump (stair) number) в заданном интервале. Известны задачи о нахождении перестановки с минимальным числом скачков (ступенек). Меня интересует число линейных расширений данного порядка с нулевым числом ступенек.

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

1. Graham R.L. et al. Handbook of combinatorics Vol. 1.
2. Лозин В.В. E-свободные двудольные графы / Дискретный анализ и исследование операций, 2000.

LaTeX,WordPress и "Theory of Convex Structures"

2009-12-18T19:35:00.009+02:00

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

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

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

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

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

2009-12-10T14:31:00.006+02:00

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

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

Таким образом, во второй раздел должно войти описание методов, используемых при проведении исследования.
Исходя из вышесказанного, могу набор методов, используемых в своей работе, разделить на две широкие группы:

Теоретические. Здесь исследуется несколько упрощенная модель генетического алгоритма, для которой делаются выводы. Использовались понятия и результаты метрической теории графов, включая понятие выпуклости на графах, а также методы теории вероятностей.
Экспериментальные. Здесь тестируется программная реализация генетического алгоритма, другими словами, реализуется вычислительный эксперимент. Для оценки результатов проводится сравнение со случайным поиском, другими эвристиками и метаэвристиками, а также с уже известными оптимальными решениями. Кроме того, вычислительный эксперимент используется для подтверждения или опровержения теоретических гипотез.

Второй раздел мог бы содержать, по крайней мере, два подраздела, посвященных каждому из вышеуказанных пунктов.

План раздела может быть следующий.

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 Выводы ко второму разделу

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

2009-11-27T08:52:00.001+02:00

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

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

2009-11-07T16:58:00.005+02:00

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

"Введение в аксиоматическую теорию выпуклости" В. П. Солтана

2009-11-01T13:37:00.003+02:00

Отсканировал классику по абстрактной выпуклости. Качать здесь.

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

2009-10-21T18:24:00.005+03:00

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

Первое, что может быть замечено общего в этих двух теориях, так это такое свойство как "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.

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

2009-10-02T14:49:00.001+03:00

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

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

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

2009-10-02T14:40:00.000+03:00

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

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

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

2009-09-16T23:43:00.005+03:00

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

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

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

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

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

2009-09-15T22:25:00.003+03:00

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

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

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

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

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

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

Pure Crossovers

2009-09-14T21:56:00.000+03:00

В работе [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

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

2009-09-14T21:08:00.002+03:00

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

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

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

2009-09-13T21:28:00.002+03:00

В работе [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.

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

2009-09-12T23:51:00.003+03:00

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

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

2009-09-11T19:21:00.025+03:00

В 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 Artiﬁcial Intelligence - Italian worshop on Evolutionary Computation, 2006.

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

2009-09-10T07:35:00.006+03:00

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

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

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

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

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

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

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

2009-09-09T19:59:00.006+03:00

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 ﬂowshop problems. Evolutionary Computation, 6(1):25–44, 1998.

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

2009-09-08T23:46:00.000+03:00

В работе [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.

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

2009-09-07T22:55:00.005+03:00

Нашел статью [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.

Convex Search

2009-09-06T23:17:00.005+03:00

Именно такое название дал 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.

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

2009-09-05T19:36:00.006+03:00

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

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

2009-09-03T19:59:00.000+03:00

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

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

2009-08-28T11:52:00.001+03:00

Такое доказательство, как оказалось, было проведено для различных представлений в работе, упоминаемой в предыдущем сообщении. Вот цитата: "... 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.
Теперь (барабанная дробь) определение геометрического кроссовера (опять цитата):
"Deﬁnition 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)"
Поскольку, это определение напоминает определение выпуклого множества, я бы назвал этот класс кроссоверов выпуклыми.

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

2009-08-28T08:18:00.002+03:00

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

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

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

2009-08-26T16:59:00.001+03:00

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

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

2009-08-26T13:43:00.003+03:00

Могут быть выделены два класса кроссоверов на решениях, представленных перестановками. Первый класс описывается следующим образом. Дано две хромосомы и управляющая бинарная последовательность по длине равная длине хромосомы. Управляющая она в том смысле, что в зависимости от того какой бит занимает рассматриваемую позицию, такой аллель (значение элемента перестановки) переходит в хромосому потомка. При этом, если некоторый аллель переходит к потомку, то он удаляется как у родителя-источника, так и у второго родителя.
Во второй класс кроссоверов на перестановках отнесем все такие, которым вышеуказанное описание не подходит. Эти кроссоверы, вообще говоря, являютя первыми, которые были предложены для работы с перестановками, в т.ч. частично-соответствующий кроссовер (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

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

2009-08-15T12:34:00.000+03:00

То, что предлагается вниманию читателя далее, следует читать с конца сообщения, т.к. это копия переписки по 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".

С уважением,

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

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

2009-07-27T00:52:00.000+03:00

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

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

2009-07-16T05:46:00.000+03:00

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

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

2009-07-05T02:03:00.000+03:00

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

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

2009-07-03T16:58:00.000+03:00

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

Профиль

2009-07-02T11:54:00.002+03:00

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

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

2009-07-02T11:54:00.001+03:00

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

Новости

2009-07-01T16:12:00.000+03:00

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

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

2009-06-18T13:49:00.000+03:00

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

Vector Packing Problem

2009-06-01T12:11:00.000+03:00

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

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

2009-05-31T21:06:00.000+03:00

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

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

2009-05-30T19:25:00.000+03:00

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

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

2009-05-30T19:17:00.000+03:00

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

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

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

2009-05-28T20:20:00.003+03:00

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

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

2009-05-22T13:09:00.000+03:00

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

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

2009-05-19T02:50:00.000+03:00

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

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

2009-05-18T23:29:00.000+03:00

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

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

2009-05-06T13:15:00.090+03:00

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

Бондаренко А.С., Козин И.В.
Эволюционные метаэвристики в задачах комбинаторной оптимизации с критерием симметрии
Российская конференция "Дискретная оптимизация и исследование операций", Республика Алтай, Гостиница Ареда, 27 июня-3 июля 2010 г. Принято в программу конференции
Исследованы простейшие задачи с критерием симметрии на конечных множествах. Установлен класс сложности этих задач. Рассмотрен ряд задач теории расписаний, упаковки контейнеров, раскроя с критериями симметрии.
Бондаренко А.С.
Графы линейных расширений и их регулярные подграфы // Дев’ятий Міжвузівський науково-практичний семінар "Комбінаторні конфігурації та їх застосування", 16-17 квітня 2010 року, Кіровоград.
Бондаренко А.С.
Эволюционная метаэвристика для задач упаковки / А.С. Бондаренко, С.И. Полюга // Матеріали всеукраїнської науково-практичної конференції "Інформатика та системні наук", 18-20 березня 2010 р. - Полтава : ПУСКУ, 2010. - С. 29-30.
Бондаренко А.С.
О задачах эволюционного моделирования в задачах теории расписаний / А.С. Бондаренко, И.В. Козин, С.И. Полюга // Матеріали всеукраїнської науково-практичної конференції "Системний аналіз. Інформатика. Управління", 4-5 березня 2010 р. - Запоріжжя: Класичний приватний університет, 2010. - С. 20-21.
А.С. Бондаренко
Полнота генетического поиска // VII міжнародна науково-практична конференція "Математичне та програмне забезпечення інтелектуальних систем", 25-27 листопада 2009 року, Дніпропетровськ. - с. 47-48.
Козин И.В., Бондаренко А.С., Полюга С.И.
Об объёме шара в пространстве перестановок // Матеріали Восьмого Міжвузівського науково-практичного семінару "Комбінаторні конфігурації та їх застосування", 16-17 жовтня 2009 року, Кіровоград. - С. 51-53.
А.С.Бондаренко, И.В.Козин.
Эволюционные метаэвристики на множестве перестановок // Матеріали Восьмого Міжвузівського науково-практичного семінару "Комбінаторні конфігурації та їх застосування", 16-17 жовтня 2009 року, Кіровоград. - С. 10-12.
А.С.Бондаренко, И.В.Козин.
Применение ЭВФ-алгоритмов для задач теории расписаний // Праці міжнародного симпозіуму Питання оптимізації обчислень (ПОО–ХХХV), Т.1, 24-29 вересня 2009 року. - с. 73-77.
Т. В. Заховалко
Эволюционно-фрагментарный подход к решению задачи о максимально симметричном покрытии / Т. В. Заховалко, А. С. Бондаренко, Н. К. Максишко // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", 29 июня - 4 июля 2009. - Омск, 2009. - С. 128.
В. А. Перепелица
Эволюционные модели в задачах теории расписаний / В. А. Перепелица, И. В. Козин, А. С. Бондаренко // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения", 29 июня - 4 июля 2009. - Омск, 2009. - С. 155.
Козин И. В., Бондаренко А. С.
Эволюционные методы в задаче об оптимальных перестановках // Сьомий Міжвузівський науково-практичний семінар "Комбінаторні конфігурації та їх застосування", 17-18 квітня 2009 року, Кіровоград. - с. 33-37.
А. С. Бондаренко, И. В. Козин
Об оценке качества ЭВФ-алгоритмов для задачи равномерной загрузки // VI міжнародна науково-практична конференція "Математичне та програмне забезпечення інтелектуальних систем", 12-14 листопада 2008 року, Дніпропетровськ. - с. 52-53.
Abstract. In the paper we consider the subject of evaluating evolutionary fragmentary algorithms performance for indentical parallel machine problem with the criteria of uniform loading.
Аннотация. В работе рассматривается вопрос оценки эффективности ЭВФ-алгоритмов для задачи равномерной загрузки идентичных параллельных машин.
А. С. Бондаренко, И. В. Козин
Об оценке качества ЭВФ-алгоритмов для простейших экстремальных комбинаторных задач // Шостий Міжвузівський науково-практичний семінар "Комбінаторні конфігурації та їх застосування", 17-18 жовтня 2008 року, Кіровоград. - c. 16-18.
Abstract. In the paper we consider the subject of evaluating evolutionary fragmentary algorithms performance for some combinatorial problems.
Аннотация. В работе рассматривается проблема оценки эффективности ЭВФ-алгоритмов для некоторых комбинаторных задач.

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

Козин И.В., Бондаренко А.С., Полюга С.И.
Об оценке шарового покрытия пространства перестановок // Вісник Запорізького національного університету: Збірник наукових статей. Фізико-математичні науки. - 2009. - № 1. - С. 134-138.
В статье рассмотрена задача вычисления объема шара в дискретном пространстве перестановок из n элементов, получен ряд рекуррентных соотношений, связывающих число элементов сфер и шаров произвольных радиусов, установлена нижняя граница мощности покрытия множества перестановок шарами заданного радиуса.
Ключевые слова: число инверсий, инверсная метрика, пространство перестановок, сфера и шар в пространстве перестановок, покрытие.
Bondarenko O.S., Kozin I.V.
Evolutionary fragmentary algorithm for permutation flow shop problem // Таврический вестник информатики и математики. - 2009. - №2. - С. 47-51.
The article tackles the strongly NP-hard permutation ﬂow shop problem. The fragmentary structure of the problem is pointed out. The evolutionary fragmentary approach for optimal solution is proposed.
The testing of evolutionary fragmentary algorithm on instances’ set from the ORLib [1] library is conducted.
Keywords: permutation ﬂow shop problem, fragmentary structure, evolutionary fragmentary approach, NP-hardness.
Бондаренко А.С., Козин И.В.
Эволюционный и фрагментарный подходы к задаче о равномерной нагрузке // Искусственный интеллект. - 2009. - № 4. - С. 248-253.
В работе представлены результаты исследования задачи о равномерной нагрузке. Подобная задача возникает, в частности, при моделировании структурных элементов учебного процесса в высшем учебном заведении. Проблема заключается в распределении учебных дисциплин во времени таким образом, чтобы максимум нагрузки на студента был минимален. Предложены эволюционный подход для поиска оптимального решения и фрагментарный подход для построения допустимого решения задачи о равномерной нагрузке. Предложенные методы протестированы на наборе случайных задач.

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

2009-05-04T23:32:00.001+03:00

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

PhD Thesis Де Джонга

2009-05-04T22:44:00.000+03:00

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

Задача Job Shop

2009-05-04T02:50:00.000+03:00

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