Пророки из своего отечества

Осуществил несколько небольших поисковых сессий с использованием русскоязычных запросов по MOCO+CSP, просмотрел около полутора десятков найденных статей. Многие авторы используют термин «многокритериальный» применительно к рассматриваемым в их работах задачам, но до построения внятной математической формулировки частной задачи упаковки дело дошло только в публикации [1]. В данном случае недостаток осмысленных тематических статей скорее радует, чем печалит.

Заодно попалась статья [2], в первой части которой сделан небольшой обзор советских и постсоветских школ, занимающихся решением задач раскроя и упаковки. К известному уже списку (Л. В. Канторович, В. А. Залгаллер, Ф. В. Бабаев, Э. А. Мухачева, Ю. Г. Стоян) добавились фамилии В. С. Михалевича и И. В. Сергиенка. В [2] автор упоминает целый ряд российских (или советских) ученых, занимавшихся решением задач раскроя в лесопильной и деревообрабатывающей промышленности (не моя предметная область, поэтому воспроизводить не стал). Формально моя работу характеризует преемственность, продолжается советская и украинская научная традиция. В той же работе [3, с. 333—346] академика Ивана Васильевича Сергиенко есть небольшой раздел по MOCO. В дальнейшем я подробно уточню эти моменты при подготовке текста диссертации.

***

1. Ляпин М. Г. Многоцелевая комбинаторная оптимизация и управление процессом технологической подготовки упаковки объектов в контейнеры / М. Г. Ляпин // Вести высших учебных заведений Черноземья. — 2008. — № 4. — С. ***—***.
2. Грицюк Ю. І. Проблема моделювання карт і оптимізації плану розкрою плитних деревних матеріалів на меблеві заготовки / Ю. І. Грицюк // Збірник науково-технічних праць. – Львів : НЛТУ України. – 2006. – Вип. 16.7. — С. 102—110. — Бібліогр.: с. 109—110.
3. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации / И. В. Сергиенко. — 2-е изд., доп. и перераб. — К. : Наук. думка, 1988. — 472 с. — Библиогр.: с. 459—471.

Наборное поле научной новизны

В сентябре я планировал написать пост с подобным названием. Хотел поделиться своими сомнениями по поводу научной новизны собственного исследования. Признаться, я довольно поверхностно знаком с работами «уфимской» школы, но уже после нескольких прочитанных статей, авторами которых являются представителями этой самой школы, у меня возникло ощущение, что какое бы сочетание <encoding> + <guided low-level heuristics> + <master strategy | high-level metaheuristics> для существующих способов представления раскройных планов, разработанных низкоуровневых эвристик и метаэвристических методов я не выбрал, оно все равно уже будет в полной мере освоено жителями столицы Башкирии.

В начале августа я попытался сформировать концепцию своего исследования несколько иначе и абстрагироваться от конкретного метода решения раскройной задачи того или иного вида:

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

Сэнсэй воспринял эти начинания довольно прохладно, и мне пришлось продолжить свой поиск. Тем не менее идея эта по-прежнему остается актуальной, с той лишь поправкой, что подобное исследование больше соответствует специальности 05.13.05 «Компьютерные системы и компоненты». Предварительно освоив предметную область посредством создания программной реализации одного из существующих метаэвристических методов решения одномерной раскройной задачи, я перешел к рассмотрению задачи 1.5-мерного раскроя, возникающей в одном из цехов завода, активное сотрудничество с которым предполагалось в самом начале моего аспирантского пути.

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

Изучив типовую структуру задач 1.5-мерного раскроя, я приступил к работе над формальной постановкой задачи и предварительному выбору метаэвристического метода, реализации и тестированию которого применительно к рассматриваемой раскройной задаче, и будет в итоге посвящено мое диссертационное исследование. Дальнейшая работа будет полностью связана с многокритериальной комбинаторной оптимизацией с использованием метаэвристических методов — сделанный обзор позволяет мне ответственно заявить, что применительно к задачам раскроя и упаковки эта ниша все еще остается более-менее свободной.

Примечательно, что ранее моим познания в многокритериальной оптимизации ограничивались пятью страницами раздела 5.2 работы [1, pp. 97 — 101]. Сейчас я занят чтением весьма достойной работы [2], из более чем шести сотен страниц осмысленного текста пока освоены только первые полторы сотни. Параллельно я изучая методические пособия [3 — 4], в которых изложены основные требования к оформлению диссертаций.

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

***

1. R. L. Haupt. Practical genetic algorithms / R. L. Haupt, S. E. Haupt. — [2-nd ed.]. — Wiley-Interscience, 2004. — 272 p.
2. C. A. Coello Coello. Evolutionary algorithms for solving multi-objective problems / C. A. Coello Coello, G. B. Lamont, D. A. Van Veldhuizen. — [2-nd ed.]. — Springer, 2007. — 800 p.
3. Як підготувати і захистити дисертацію на здобуття наукового ступеня : методичні поради / [упоряд. Л. А. Пономаренко] ; Редакція «Бюл. ВАК України». — 3-тє вид., виправ. та доповн. — К. : Толока, 2005. — 80 с. — Бібліогр.: с. 80.
4. Як правильно оформити дисертацію та документи атестаційної справи : зб. нормат. док. з питань наук. кадрів вищої кваліфікації / [упоряд. Ю. І. Цеков] ; Редакція «Бюл. ВАК України». — К. : Толока, 2004. — 80 с.

Конец второго сезона

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

Формально второй сезон окончен, а третий — начнется 1 декабря, но для меня это ровным счетом ничего не меняет, я продолжаю старательно изучать материал по многокритериальной комбинаторной оптимизации и разрабатывать проблемно-ориентированную метаэвристику для решения 1.5-мерной раскройной задачи.

Аттестация на факультете

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

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

Полировать лавку мне пришлось довольно долго — целых 2 часа. Хорошо, что ожидание подписей удалось скрасить общением с аспирантом из Иордании. Араб оказался нормальным чуваком, русский язык он освоил весьма и весьма прилично. Когда же заседание ученого совета наконец-то закончилось, я забрал выписки и бланки аттестации у Фонотова, быстро просмотрел их. Оказалось, что подписи появились только в бланках аттестации, облагородить своими росчерками выписки декан забыл. Пришлось просить его расписаться в выписках, затем искать секретаря ученого совета, ставить подписи и у нее. В итоге все необходимые подписи я собрал, но поставить печати мне так и не удалось — рабочий день закончился, в деканате никого не было. Завтра придется еще раз идти в университет, ставить печати и сдавать все бумажки в аспирантуру.

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

Многокритериальная комбинаторная оптимизация

На днях я адаптировал формальную постановку задачи 1.5-мерного раскроя из [1] для нужд собственного исследования и будущей статьи. Наличие трех слагаемых в целевой функции позволяет отнести рассматриваемую задачу к multiobjective combinatorial optimization (MOCO), многокритериальной комбинаторной оптимизации. Возможно, последовательное усложнение разрабатываемого метаэвристического метода, предложенное мною ранее, является если и не ошибочным, то явно не самым быстрым путем, ведущим к достижению поставленной цели — получению приемлемых решений раскройной задачи.

Времени остается немного, поэтому мне, вероятно, придется сразу заняться многокритериальной оптимизацией. Удалось найти цикл обзорных тематических работ [2 — 5] по MOCO, чтением которых я сейчас, собственно, и занят. Содержание этих публикаций поможет мне сделать выбор в пользу той или иной метаэвристики. Слепо полагаться на генетические алгоритмы я в данном случае не готов.

***

1. R. W. Haessler. Selection and design of heuristic procedures for solving roll trim problems / R. W. Haessler // Management Science. — 1988. — Vol. 34, No. 12. — pp. 1460—1471.
2. M. Ehrgott. A survey and annotated bibliography of multiobjective combinatorial optimization / M. Ehrgott, X. Gandibleux // OR Spectrum. — 2000. — Vol. 22, No. 4. — pp. 425—460.
3. M. Ehrgott. Approximative solution methods for multiobjective combinatorial optimization / M. Ehrgott, X. Gandibleux // TOP. — 2004. — Vol. 12, No. 1. — pp. 1—63.
4. X. Gandibleux. 1984—2004 — 20 years of multiobjective metaheuristics. But what about the solution of combinatorial problems with multiple objectives? / X. Gandibleux, M. Ehrgott // Lecture notes in computer science. — 2005. — Vol. 3410. — pp. 33—46.
5. M. Ehrgott. Hybrid metaheuristics for multi-objective combinatorial optimization / M. Ehrgott, X. Gandibleux // Studies in Computational Intelligence. — 2008. — Vol. 114. — pp. 221—259.

Аттестация на кафедре

Аттестовался сегодня на заседании кафедры. Нормально выступил, рассказал о текущем состоянии дел, космосы оставил в покое. Комментарии некоторых преподавателей, услышанные после выступления, меня не шокировали, но отрезали очередной лоскут от хрупкой университетской пуповины:

— А он вообще «наш»?

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

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