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". Произвела на меня достаточно сильное впечатление чёткостью изложения.