Я работал над проблемой комбинаторной оптимизации, которая, как я подозреваю, является NP-сложной, и генетический алгоритм хорошо работал с нашим набором данных. Мы являемся исследовательской группой и планируем публиковать наши результаты в нашей области (не по математике или CS), и я хотел бы изучить сложный вопрос, прежде чем отправлять рукопись на рецензию.
Есть два основных вопроса:
1) Я хотел бы знать, изучалась ли эта конкретная проблема оптимизации. Я интенсивно обыскивал освещенную, но не видел ничего такого же.
2) Если проблема не была изучена, я мог бы попытаться сделать доказательство приводимости и хотел бы, чтобы некоторые указатели указывали на хороших NP-полных кандидатов для сокращения.
Проблема может быть описана двумя способами, как вариант подпоследовательности и как проблема двудольного графа.
В аромате подпоследовательности я хочу найти «расслабленную» подпоследовательность, которая позволяет перестановки и оптимизировать, чтобы минимизировать количество перестановок. Например: (. = Любой другой символ)
Запрос: abc, Цель: ..b.a.b.c., Результат: abc (нормальная подпоследовательность)
Запрос: abc, Цель: ..b.a.c.a., Результат: bac (подпоследовательность с одной перестановкой)
Двухсторонняя формулировка - это проблема согласования или линейного назначения, когда график разбивается на символьные узлы запроса и целевые символьные узлы. Ребра соединяют символы запроса с целевыми символами, так что существует ровно одно ребро от каждого символа запроса до целевого символа. Задача состоит в том, чтобы свести к минимуму количество пересечений краев (также называемое «число пересечений» в освещенном). Это похоже на алгоритмы компоновки двудольных графов, которые переупорядочивают размещение узлов, чтобы минимизировать пересечения ребер, но моя проблема требует, чтобы оба порядка узлов оставались фиксированными.
Есть какие-нибудь мысли экспертов по вопросам 1 или 2?
Заранее спасибо!