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

Question

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

Например:

Пользовательский ввод:

1) ограничить количество энергии, которую можно потратить.

2) типы "хромосом" - синий (подтипы - индиго и т. Д.), Красный (подтипы - бордовый и т. Д.), Желтый (подтипы - светло-желтый и т. Д.) - у каждого основного атрибута, такого как синий, есть "пул", из которого можно выбрать состоят из разных подтипов, таких как индиго, светло-голубой, морской синий независимо - каждый подтип цвета имеет различную стоимость, связанную с ним.

3) процент типов, требуемых для "идеального" решения (может ввести +/- %, чтобы обеспечить большее разнообразие). - 10% красного, 30% синего, 60% желтого.

Выход:

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

Так например.

Это очень простой пример, очевидно, что это будет сложнее, чем это на самом деле.

Пользователь указывает стоимость должна быть следующей 95 <= стоимость <= 105.

Пользователь выбирает 25% синего, 25% желтого, 50% красного. с отклонением +/- 5%

Доступные бассейны для каждого цвета

Синий: индиго: стоимость = 25; Море синее: стоимость = 30; Темно-синий: стоимость = 75;

Желтый: светло-желтый: стоимость = 20; Темно-желтый: стоимость = 30; Супер темно-желтый (смеется): стоимость = 75;

Красный: бордовый: стоимость = 20; Кроваво-красный: стоимость = 45; Ярко-красный: стоимость = 55;

Таким образом, алгоритм будет работать и возвращать различные комбинации.

Комбинация 1: индиго, темно-желтый, кроваво-красный: стоимость = 100: синий = 25%, желтый = 30%, красный = 55%.

Комбинация 2: морской синий, светло-желтый, кроваво-красный: стоимость = 105: синий = ~30%, желтый = ~20%, красный = ~50%

Комбинация 3: и так далее, и тому подобное.

РЕДАКТИРОВАТЬ: Второе редактирование

Выход будет состоять из наборов различных комбинаций.

Например, одно решение может состоять из таких комбинаций, как:

Одно решение будет представлено этим:

Комбинация 1: Стоимость = 20; 50% синий, 25% желтый, 25% красный;

Комбинация 2: Стоимость = 30; 10% синий, 50% желтый, 40% красный;

Комбинация 3: Стоимость = 50; 25% синий, 25% желтый, 50% красный;

Решение: = (комбинация 1, комбинация 2, комбинация 3) общая стоимость = 100, и она состоит из x% синего, y% желтого, z% красного;

сравнить решение с требованиями, если оно близко, оставить его, если не отказаться от него.

КОНЕЦ РЕДАКТИРОВАНИЯ

Итак, мой вопрос. Я знаю, что генетический алгоритм будет работать. Но сработает ли реализация ACO? Например, синий, желтый и красный будут равны "местоположениям", тогда их подтипы будут представлять разные "дороги".

Просто интересно, что может быть более эффективным решением или, может быть, каким-то другим алгоритмом. Я довольно новичок в этом и только начал читать об этом чуть более недели назад.

РЕДАКТИРОВАТЬ: Первое редактирование

Я хочу указать, что я хочу иметь 5 хороших уникальных решений (5 - произвольное число, может быть 3, может быть 20).

Answer 1

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

Answer 2

Единственная проблема, которую я вижу с вашим представлением в ACO, это +/- X% .

С фиксированным процентом каждого цвета, вы можете просто продолжить, как вы сказали:

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

Затем вы просто применяете свой метод AOC, как для TSP, но немного меняете то, как двигаются муравьи:

1. добавление феромонов к одному пути только в том случае, если оно полностью удовлетворяет ограничениям стоимости
2. Выбор длины пути, ближайшей к "оптимальной длине" = N% от оптимальной стоимости (в примере выше, для желтого пути, самый близкий к 25%*95)

Если вы хотите добавить плавающее процентное ограничение, тогда:

скажем, вы лучшая цена:

Cost = X1*light yellow +X2*sea blue+X3*blood red for example.

если эта стоимость не является оптимальной, вы можете работать с небольшими изменениями на X1 X2 и X3, чтобы оптимизировать ваши затраты:

например, X1-e и X2+e изменят ваши расходы на e*(costseablue-costLightYellow)

Например, учитывая один маленький эпсилон, для каждой пары Xi,Xj такой, что costi<costj (стоимость цвета связана с i и j) вы можете попробовать добавить эпсилон в Xi и удалить его из Xj, пока вы не сможете улучшить стоимость для всех пар Xi,Xj.

Answer 3

Если ваш график удовлетворяет неравенству треугольника, я предлагаю вам попробовать минимальное остовное дерево и алгоритм двойного сопоставления с идеальным весом. Christofides et al. гарантировать вам решение в пределах 3/2 от оптимального. AOC может дать вам хороший и быстрый результат, но вы должны оптимизировать его для многих проблем. Я написал алгоритм Christofides в php (phpclasses.org). Вы можете попробовать это. Я не уверен, что это работает. Это дает иногда странные результаты. Это может быть моя реализация алгоритма Флери?