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

Question

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

Например:

Ввод пользователя:

1) предел -i.e. количество энергии, которое можно потратить.

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

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

Выход:

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

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

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

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

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

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

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

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

Красный: Maroon: стоимость = 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

Единственная проблема, которую я вижу с вашим представлением для 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 2

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

Answer 3

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