001/* 002 * Java Genetic Algorithm Library (jenetics-8.2.0). 003 * Copyright (c) 2007-2025 Franz Wilhelmstötter 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 * Author: 018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com) 019 */ 020package io.jenetics.ext.grammar; 021 022import java.util.function.Function; 023 024import io.jenetics.BitChromosome; 025import io.jenetics.BitGene; 026import io.jenetics.Genotype; 027import io.jenetics.IntegerChromosome; 028import io.jenetics.IntegerGene; 029import io.jenetics.engine.Codec; 030import io.jenetics.util.IntRange; 031 032import io.jenetics.ext.grammar.Cfg.Rule; 033 034/** 035 * This class defines factories for different CFG ↔ Chromosome mappings 036 * (encodings). The classical mapping codec, with a bit-chromosome can be created 037 * in the following way. 038 * {@snippet lang="java": 039 * final Cfg<String> cfg = null; // @replace substring='null' replacement="..." 040 * final Codec<List<Terminal<String>>, BitGene> codec = singleBitChromosomeMapper( 041 * cfg, 042 * 1000, 043 * index -> new SentenceGenerator<>(index, 1000) 044 * ); 045 * } 046 * This codec creates a mapping for the given grammar {@code cfg} and uses 047 * bit-chromosomes with length {@code 1000}. The result of the mapping will be a 048 * list of terminal symbols which has been created by the given 049 * {@link SentenceGenerator}. The sentence generator creates sentences with a 050 * maximal length of {@code 1000}. If no sentence could be created within this 051 * limit, an empty list of terminal symbols is returned. 052 * 053 * @see <a href="https://www.brinckerhoff.org/tmp/grammatica_evolution_ieee_tec_2001.pdf"> 054 * Grammatical Evolution</a> 055 * 056 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 057 * @since 7.1 058 * @version 7.1 059 */ 060public final class Mappers { 061 private Mappers() { 062 } 063 064 /** 065 * Return a classic mapping codec. It uses a bit-chromosome for creating the 066 * grammar results. The codons are created by dividing the chromosome in 067 * 8-bit junks, as described in <a href="https://www.brinckerhoff.org/tmp/grammatica_evolution_ieee_tec_2001.pdf"> 068 * Grammatical Evolution</a> by Michael O’Neill and Conor Ryan. 069 * {@snippet lang="java": 070 * final Cfg<String> cfg = null; // @replace substring='null' replacement="..." 071 * final Codec<List<Terminal<String>>, BitGene> codec = singleBitChromosomeMapper( 072 * cfg, 073 * 1000, 074 * index -> new SentenceGenerator<>(index, 1000) 075 * ); 076 * } 077 * 078 * @see #singleIntegerChromosomeMapper(Cfg, IntRange, IntRange, Function) 079 * 080 * @param cfg the encoding grammar 081 * @param length the length of the bit-chromosome 082 * @param generator sentence generator function from a given 083 * {@link SymbolIndex} 084 * @param <T> the terminal token type of the grammar 085 * @param <R> the result type of the mapper 086 * @return a new mapping codec for the given {@code cfg} 087 */ 088 public static <T, R> Codec<R, BitGene> 089 singleBitChromosomeMapper( 090 final Cfg<? extends T> cfg, 091 final int length, 092 final Function<? super SymbolIndex, ? extends Generator<T, R>> generator 093 ) { 094 return Codec.of( 095 Genotype.of(BitChromosome.of(length)), 096 gt -> generator 097 .apply(Codons.ofBitGenes(gt.chromosome())) 098 .generate(cfg) 099 ); 100 } 101 102 /** 103 * Create a mapping codec, similar as in {@link #singleBitChromosomeMapper(Cfg, int, Function)}. 104 * The only difference is that the codons are encoded directly, via an 105 * integer-chromosome, so that no gene split is necessary. 106 * {@snippet lang="java": 107 * final Cfg<String> cfg = null; // @replace substring='null' replacement="..." 108 * final Codec<List<Terminal<String>>, IntegerGene> codec = singleIntegerChromosomeMapper( 109 * cfg, 110 * IntRange.of(0, 256), // Value range of chromosomes. 111 * IntRange.of(100), // Length (range) ot the chromosome. 112 * index -> new SentenceGenerator<>(index, 1000) 113 * ); 114 * } 115 * 116 * @param cfg the encoding grammar 117 * @param range the value range of the integer genes 118 * @param length the length range of the integer-chromosome 119 * @param generator sentence generator function from a given 120 * {@link SymbolIndex} 121 * @param <T> the terminal token type of the grammar 122 * @param <R> the result type of the mapper 123 * @return a new mapping codec for the given {@code cfg} 124 */ 125 public static <T, R> Codec<R, IntegerGene> 126 singleIntegerChromosomeMapper( 127 final Cfg<? extends T> cfg, 128 final IntRange range, 129 final IntRange length, 130 final Function<? super SymbolIndex, ? extends Generator<T, R>> generator 131 ) { 132 return Codec.of( 133 Genotype.of(IntegerChromosome.of(range, length)), 134 gt -> generator 135 .apply(Codons.ofIntegerGenes(gt.chromosome())) 136 .generate(cfg) 137 ); 138 } 139 140 /** 141 * Create a mapping codec, similar as in {@link #singleBitChromosomeMapper(Cfg, int, Function)}. 142 * The only difference is that the codons are encoded directly, via an 143 * integer-chromosome, so that no gene split is necessary. 144 * {@snippet lang="java": 145 * final Cfg<String> cfg = null; // @replace substring='null' replacement="..." 146 * final Codec<List<Terminal<String>>, IntegerGene> codec = singleIntegerChromosomeMapper( 147 * cfg, 148 * IntRange.of(0, 256), // Value range of chromosomes. 149 * 100, // Length (range) ot the chromosome. 150 * index -> new SentenceGenerator<>(index, 1000) 151 * ); 152 * } 153 * 154 * @param cfg the encoding grammar 155 * @param range the value range of the integer genes 156 * @param length the length range of the integer-chromosome 157 * @param generator sentence generator function from a given 158 * {@link SymbolIndex} 159 * @param <T> the terminal token type of the grammar 160 * @param <R> the result type of the mapper 161 * @return a new mapping codec for the given {@code cfg} 162 */ 163 public static <T, R> Codec<R, IntegerGene> 164 singleIntegerChromosomeMapper( 165 final Cfg<? extends T> cfg, 166 final IntRange range, 167 final int length, 168 final Function<? super SymbolIndex, ? extends Generator<T, R>> generator 169 ) { 170 return singleIntegerChromosomeMapper( 171 cfg, range, IntRange.of(length), generator 172 ); 173 } 174 175 /** 176 * Codec for creating <em>results</em> from a given grammar. The creation of 177 * the grammar result is controlled by a given genotype. This encoding uses 178 * separate <em>codons</em>, backed up by a {@link IntegerChromosome}, for 179 * every rule. The length of the chromosome is defined as a function of the 180 * encoded rules. This means that the following CFG, 181 * 182 * <pre>{@code 183 * (0) (1) 184 * (0) <expr> ::= (<expr><op><expr>) | <var> 185 * (0) (1) (2) (3) 186 * (1) <op> ::= + | - | * | / 187 * (0) (1) (2) (3) (4) 188 * (2) <var> ::= x | 1 | 2 | 3 | 4 189 * }</pre> 190 * 191 * will be represented by the following {@link Genotype} 192 * {@snippet lang="java": 193 * Genotype.of( 194 * IntegerChromosome.of(IntRange.of(0, 2), length.apply(cfg.rules().get(0))), 195 * IntegerChromosome.of(IntRange.of(0, 4), length.apply(cfg.rules().get(1))), 196 * IntegerChromosome.of(IntRange.of(0, 5), length.apply(cfg.rules().get(2))) 197 * ) 198 * } 199 * 200 * The {@code length} function lets you defining the number of codons as 201 * function of the rule the chromosome is encoding. 202 * {@snippet lang="java": 203 * final Cfg<String> cfg = Bnf.parse(null); // @replace substring='null' replacement="..." 204 * final Codec<List<Terminal<String>>, IntegerGene> codec = multiIntegerChromosomeMapper( 205 * cfg, 206 * // The chromosome length is 25 times the 207 * // number of rule alternatives. 208 * rule -> IntRange.of(rule.alternatives().size()*25), 209 * // Using the standard sentence generator 210 * // with a maximal sentence length of 500. 211 * index -> new SentenceGenerator<>(index, 500) 212 * ); 213 * } 214 * 215 * @param cfg the encoding grammar 216 * @param length the length of the chromosome which is used for selecting 217 * rules and symbols. The input parameter for this function is the 218 * actual rule. This way it is possible to define the chromosome 219 * length dependent on the selectable alternatives. 220 * @param generator sentence generator function from a given 221 * {@link SymbolIndex} 222 * @param <T> the terminal token type of the grammar 223 * @param <R> the result type of the mapper 224 * @return a new mapping codec for the given {@code cfg} 225 */ 226 public static <T, R> Codec<R, IntegerGene> 227 multiIntegerChromosomeMapper( 228 final Cfg<? extends T> cfg, 229 final Function<? super Rule<?>, IntRange> length, 230 final Function<? super SymbolIndex, ? extends Generator<T, R>> generator 231 ) { 232 return new MultiIntegerChromosomeMapper<>(cfg, length, generator); 233 } 234 235 236}