Я реализовал вариант проблема с рюкзаком с использованием Дженетикс следующим образом:
@Value
public class Knapsack {
public static void main( final String[] args ) {
final var knapsackEngine = Engine.builder( Knapsack::fitness, Knapsack.codec() )
.constraint( Knapsack.constraint() )
.build();
final var bestPhenotype = knapsackEngine.stream()
.limit( 1000L )
.collect( EvolutionResult.toBestPhenotype() );
final var knapsack = bestPhenotype.getGenotype().getGene().getAllele();
final var profit = bestPhenotype.getFitness();
final var weight = knapsack.getWeight();
System.out.println( "Valid: " + bestPhenotype.isValid() );
System.out.println( String.format( "Solution: profit %d | weight %d", profit, weight ) );
System.out.println( String.format( "Optimum: profit %d | weight %d", Problem.OPTIMAL_PROFIT, Problem.OPTIMAL_WEIGHT ) );
}
List<Item> items;
public int getProfit() {
return items.stream()
.mapToInt( Item::getProfit )
.sum();
}
public int getWeight() {
return items.stream()
.mapToInt( Item::getWeight )
.sum();
}
private static Codec<Knapsack, AnyGene<Knapsack>> codec() {
return Codec.of(
Genotype.of( AnyChromosome.of( Knapsack::create ) ),
genotype -> genotype.getGene().getAllele() );
}
private static Knapsack create() {
final Random rand = RandomRegistry.getRandom();
final List<Item> items = Problem.ITEMS.stream()
.filter( item -> rand.nextBoolean() )
.collect( Collectors.toList() );
return new Knapsack( items );
}
private static int fitness( final Knapsack knapsack ) {
return knapsack.getProfit();
}
private static Constraint<AnyGene<Knapsack>, Integer> constraint() {
return Constraint.of( phenotype -> {
final Knapsack knapsack = phenotype.getGenotype().getGene().getAllele();
final int weight = knapsack.getItems().stream()
.mapToInt( Item::getWeight )
.sum();
return weight <= Problem.MAX_CAPACITY;
} );
}
}
@Value
является частью Ломбок и генерирует кучу кода, такого как конструктор, геттеры и т. д. Класс Problem
определяет некоторые константы для конкретной задачи о рюкзаке (P07 из https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html):
public class Problem {
public static final int MAX_CAPACITY = 750;
public static final BitChromosome OPTIMAL_SOLUTION = BitChromosome.of( "101010111000011" );
public static final int OPTIMAL_PROFIT = 1458;
public static final int OPTIMAL_WEIGHT = 749;
private static final List<Integer> profits = List.of(
135, 139, 149, 150, 156,
163, 173, 184, 192, 201,
210, 214, 221, 229, 240 );
private static final List<Integer> weights = List.of(
70, 73, 77, 80, 82,
87, 90, 94, 98, 106,
110, 113, 115, 118, 120 );
public static final List<Item> ITEMS = IntStream.range( 0, profits.size() )
.mapToObj( i -> new Item( profits.get( i ), weights.get( i ) ) )
.collect( Collectors.toList() );
}
Хотя в Jenetics гид пользователя сказано (см. раздел 2.5):
A given problem should usually encoded in a way, that it is not possible for the evolution
Engine
to create invalid individuals (Genotypes
).
Интересно, почему движок постоянно создает решения с весом, превышающим максимальную вместимость ранца. Таким образом, хотя эти решения недействительны в соответствии с заданным Constraint
, Phenotype#isValid()
возвращает true
.
Я могу решить эту проблему, изменив фитнес-функцию на:
private static int fitness( final Knapsack knapsack ) {
final int profit = knapsack.getProfit();
final int weight = knapsack.getWeight();
return weight <= Problem.MAX_CAPACITY ? profit : 0;
}
Или убедившись, что кодек может создавать только допустимые решения:
private static Knapsack create() {
final Random rand = RandomRegistry.getRandom();
final List<Item> items = Problem.ITEMS.stream()
.filter( item -> rand.nextBoolean() )
.collect( Collectors.toList() );
final Knapsack knapsack = new Knapsack( items );
return knapsack.getWeight() <= Problem.MAX_CAPACITY ? knapsack : create();
}
Но тогда в чем смысл Constraint
, если он не имеет никакого эффекта?
Я представил интерфейс Constraint
в последней версии Jenetics. Он задуман как последняя линия защиты, когда дело доходит до проверки действительности человека. В вашем примере вы использовали фабричный метод интерфейса Constraint
, который принимает только предикат валидности. Второй важный метод Constraint
— это метод repair
. Этот метод пытается исправить данного индивидуума. Без определения этого метода создается только новый случайный фенотип. Поскольку этот интерфейс новый, кажется, я недостаточно хорошо объяснил предполагаемое использование интерфейса Constraint
. Это у меня на повестке дня #541. Один из возможных примеров использования приведен в #540 во втором примере.
void constrainedVersion() {
final Codec<double[], DoubleGene> codec = Codecs
.ofVector(DoubleRange.of(0, 1), 4);
final Constraint<DoubleGene, Double> constraint = Constraint.of(
pt -> isValid(codec.decode(pt.getGenotype())),
(pt, g) -> {
final double[] r = normalize(codec.decode(pt.getGenotype()));
return newPT(r, g);
}
);
}
private static Phenotype<DoubleGene, Double> newPT(final double[] r, final long gen) {
final Genotype<DoubleGene> gt = Genotype.of(
DoubleChromosome.of(
DoubleStream.of(r).boxed()
.map(v -> DoubleGene.of(v, DoubleRange.of(0, 1)))
.collect(ISeq.toISeq())
)
);
return Phenotype.of(gt, gen);
}
private static boolean isValid(final double[] x) {
return x[0] + x[1] + x[2] == 1 && x[3] > 0.8;
}
private static double[] normalize(final double[] x) {
double[] r = x;
final double sum = r[0] + r[1] + r[2];
if (sum != 1) {
r[0] /= sum;
r[1] /= sum;
r[2] /= sum;
}
if (r[3] > 0.8) {
r[3] = 0.8;
}
return r;
}
И метод Phenotype::isValid
возвращает true
, потому что это проверка достоверности местный, которая только проверяет, являются ли все хромосомы и гены человека действительными или находятся в допустимом диапазоне.
Я надеюсь, что смог ответить на ваш вопрос, и лучшее описание с одним (или несколькими) примерами уже в пути. С другой стороны: если у вас есть идеи для хороших примеров использования интерфейса Constraint
, дайте мне знать.